Research On Fast Clustering Algorithm Based On Anchor Graph

In unsupervised machine learning,clustering play an important role in data partition.Because graph theory-based clustering can deal with different data distribution types data,it has been widely studied by researcher.However,graph theory-based clustering usually have high time and space complexity because of the need for graph construction and eigenvalue decomposition in the clustering process.The cluster analysis process cannot be completed quickly when the amount of data is large and the dimension is high.To improve the clustering result and speed up the clustering process,fast spectral clustering based on anchor graph have put forwarded by researcher.Fast spectral clustering construct the graph matrix by bipartite graph between data and its anchors.Then,singular value decomposition is used in fast spectral embedded data obtaining.Usually,the clustering result of fast spectral clustering are obtained throught k-means clustering on fast spectral embedded data.However,the result of k-means discretization are unstable and suboptimal.To improved the clustering result,fast clustering algorithm based on two different anchor graphs are put forward.The first one is an improved fuzzy clustering method based on conventional anchor graph.In the first method,the graph similarity of anchor graph can be embedded into the fuzzy membership matrix.However,it require the complete anchor graph during fuzzy membership matrix updating.The time and space complexity of conventional anchor graph are proportional to the square of the amount of data.Therefore,To decrease the time and space complexity,the second one use block diagonal anchor graph.The improved fuzzy clustering algorithm require the similarity description between data points while the block diagonal anchor graph only describe the relationship of data with its anchors.Therefore,block diagonal anchor graph cannot apply in improved fuzzy clustering framework.Here,we study the structured graph learning method of block diagonal anchor graph such that the clustering result can be directly obtain from the structured graph.During clustering,the time and space complexity of block diagonal anchor graph structured learning is only related to the product of the number of data and the number of anchors which can reduce the time and space complexity.The main content of this paper are listed as follows:(1)Research on improved fuzzy clustering method and use in fast spectral embedded data discretization.Based on fuzzy clustering,the improved fuzzy clustering method assign different degree between fast spectral embedded data cluster centers.We set the value of fuzzy weight to 1 and add the anchor graph constraint to fuzzy clustering objective function as the regularization item.By the regularization,the similarity of graph can be embedded in fuzzy membership matrix.(2)Research on data co-embedded method and fast adaptive neighbor structured graph learning method.The new method select anchors from data and construct the block diagonal anchor graph.The block diagonal anchor graph only describe the relationship between the data and its anchors.The co-embedded data can be obtained by using block diagonal anchor graph.Then,a new block diagonal anchor graph is constructed by embedded data and its anchors and structured graph learning.Comparing with the traditional adaptive neighbors clustering method,the proposed method avoid the high dimension data influence of structured graph learning by co-embedded processing.In the same time,it only learns the block matrix such that the new method can accelerate the speed of adaptive neighbors clustering and reduce the time and space complexity.