关键词: 无监督学习, 基于图松弛优化聚类, 数据量化, 高维数据, 快速近似

Abstract: Due to its easy implementation, the graph-based relaxed optimization indeed provides an effective analytical solution for non-approximation iterative methods. However, due to the inverse of the matrix, such an optimization will run slowly and even become impractical for large-scale data. This paper develops two general approaches for fast graph-based relaxed optimization clustering. One is based on k-means clustering, and the other is based on random projection tree. Extensive experiments show that these two proposed approaches can achieve significant acceleration without degrading the clustering accuracy a lot. In particular, the approaches have better clustering performance than the classical k-mean algorithm on large-scale data, and run faster than the graph-based relaxed optimization clustering algorithms, with comparable accuracy. It is worth noting that the proposed approaches in this paper allow a single machine to cluster millions of data samples within minutes.

Key words: unsupervised learning, graph-based clustering, data quantization, high dimensional data, fast approximate