A new algorithm for clustering aggregation
Li Qing-feng · 2011
In this article, we propose a new clustering algorithm for large datasets, that is the circle algorithm. The idea of the algorithm is to find a set of vertices that are close to each other and far from other vertices. Our algorithms make use of the connection between clustering aggregation and the problem of correlation clustering. Our work provides the best deterministic approximation algorithm for the variation of the correlation clustering problem we consider. We also show how sampling can be used to scale the algorithms for large datasets. We give an extensive empirical evaluation demonstrating the usefulness of the problem and of the solutions.