Graph Based Multi-Layer K-Means++ (G-MLKM) for Sensory Pattern Analysis in Constrained Spaces

Abstract

In this paper, we focus on developing a novel unsupervised machine learning algorithm, named graph based multi-layer k-means++ (G-MLKM), to solve the data-target association problem when targets move on a constrained space and minimal information of the targets can be obtained by sensors. Instead of employing the traditional data-target association methods that are based on statistical probabilities, the G-MLKM solves the problem via data clustering. We first develop the multi-layer k-means++ (MLKM) method for data-target association at a local space given a simplified constrained space situation. Then a p-dual graph is proposed to represent the general constrained space when local spaces are interconnected. Based on the p-dual graph and graph theory, we then generalize MLKM to G-MLKM by first understanding local data-target association, extracting cross-local data-target association mathematically, and then analyzing the data association at intersections of that space. To exclude potential data-target association errors that disobey physical rules, we also develop error correction mechanisms to further improve the accuracy. Numerous simulation examples are conducted to demonstrate the performance of G-MLKM, which yields an average data-target association accuracy of 92.2%.

Keywords

• graph theory
• sensor networks
• data-object association
• machine learning