Ensemble Clustering Using Maximum Relative Density Path

摘要

Ensemble clustering aims to obtain a better partition by aggregating different basic clustering results. Although many ensemble clustering algorithms have been proposed, they face two limitations. First, they often assume that basic clusterings were independent with each other and ignore their latent relationship. Second, they do not incorporate local information with global relationship when reconstructing point-to-point similarity matrix from basic clusterings. Accordingly, this paper presents a novel ensemble clustering approach, named Maximum Relative Density Path Accumulation (MRDPA). In this method, Relative k-nearest Neighbor Kernel Density (RNKD) and Higher Density nearest-Neighbor (HDN) are firstly applied to generate basic clusterings. These basic clusterings embody multi-scale characteristics for an input dataset with the changing of k in RNKD. Then, the maximum relative density path is defined to explore the global information in a constructed K-Nearest Neighbor (KNN) graph, and the point-to-cluster similarity and point-to-point similarity are derived from maximum relative density paths. Lastly, a final clustering is generated by a consensus function. MRDPA is evaluated on 2 synthetic datasets and 5 real datasets, and experiment results demonstrate that it outperforms established ensemble clustering algorithms.