Timezone: »
We formulate clustering aggregation as a special instance of MaximumWeight Independent Set (MWIS) problem. For a given dataset, an attributed graph is constructed from the union of the input clusterings generated by different underlying clustering algorithms with different parameters. The vertices, which represent the distinct clusters, are weighted by an internal index measuring both cohesion and separation. The edges connect the vertices whose corresponding clusters overlap. Intuitively, an optimal aggregated clustering can be obtained by selecting an optimal subset of nonoverlapping clusters partitioning the dataset together. We formalize this intuition as the MWIS problem on the attributed graph, i.e., finding the heaviest subset of mutually nonadjacent vertices. This MWIS problem exhibits a special structure. Since the clusters of each input clustering form a partition of the dataset, the vertices corresponding to each clustering form a maximal independent set (MIS) in the attributed graph. We propose a variant of simulated annealing method that takes advantage of this special structure. Our algorithm starts from each MIS, which is close to a distinct local optimum of the MWIS problem, and utilizes a local search heuristic to explore its neighborhood in order to find the MWIS. Extensive experiments on many challenging datasets show that: 1. our approach to clustering aggregation automatically decides the optimal number of clusters; 2. it does not require any parameter tuning for the underlying clustering algorithms; 3. it can combine the advantages of different underlying clustering algorithms to achieve superior performance; 4. it is robust against moderate or even bad input clusterings.
Author Information
Nan Li (Temple University)
Longin Jan J Latecki (Temple University)
More from the Same Authors

2012 Poster: Fusion with Diffusion for Robust Visual Tracking »
Yu Zhou · Xiang Bai · Wenyu Liu · Longin Jan J Latecki 
2011 Poster: Maximal Cliques that Satisfy Hard Constraints with Application to Deformable Object Model Learning »
Xinggang Wang · Xiang Bai · Xingwei Yang · Wenyu Liu · Longin Jan J Latecki 
2010 Poster: Robust Clustering as Ensembles of Affinity Relations »
Hairong Liu · Longin Jan J Latecki · shuicheng yan 
2008 Poster: Multiscale Random Fields with Application to Contour Grouping »
Longin Jan J Latecki · ChengEn Lu · Marc J Sobel · Xiang Bai