A fast graph-based data classification method with applications to 3D sensory data in the form of point clouds

摘要

Data classification, where the goal is to divide data into predefined classes, is a fundamental problem in machine learning with many applications, including the classification of 3D sensory data. In this paper, we present a data classification method which can be applied to both semi-supervised and unsupervised learning tasks. The algorithm is derived by unifying complementary region-based and edge-based approaches; a gradient flow of the optimization energy is performed using modified auction dynamics. In addition to being unconditionally stable and efficient, the method is equipped with several properties allowing it to perform accurately even with small labeled training sets, often with considerably fewer labeled training elements compared to competing methods; this is an important advantage due to the scarcity of labeled training data. Some of the properties are: the embedding of data into a weighted similarity graph, the in-depth construction of the weights using, e.g., geometric information, the use of a combination of region-based and edge-based techniques, the incorporation of class size information and integration of random fluctuations. The effectiveness of the method is demonstrated by experiments on classification of 3D point clouds; the algorithm classifies a point cloud of more than a million points in 1-2 min.