Large Scale Correlation Clustering Optimization
arXiv:1112.2903
Abstract
Clustering is a fundamental task in unsupervised learning. The focus of this paper is the Correlation Clustering functional which combines positive and negative affinities between the data points. The contribution of this paper is two fold: (i) Provide a theoretic analysis of the functional. (ii) New optimization algorithms which can cope with large scale problems (>100K variables) that are infeasible using existing methods. Our theoretic analysis provides a probabilistic generative interpretation for the functional, and justifies its intrinsic "model-selection" capability. Furthermore, we draw an analogy between optimizing this functional and the well known Potts energy minimization. This analogy allows us to suggest several new optimization algorithms, which exploit the intrinsic "model-selection" capability of the functional to automatically recover the underlying number of clusters. We compare our algorithms to existing methods on both synthetic and real data. In addition we suggest two new applications that are made possible by our algorithms: unsupervised face identification and interactive multi-object segmentation by rough boundary delineation.
9 pages, 6 figures, 1 table
References in corpus (1)
Cited by in corpus (14)
- Unifying Sparsest Cut, Cluster Deletion, and Modularity Clustering Objectives with Correlation Clustering
- Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach
- Clustering using Max-norm Constrained Optimization
- Moral Lineage Tracing
- Tracking with multi-level features
- Efficient Decomposition of Image and Mesh Graphs by Lifted Multicuts
- A Multiscale Framework for Challenging Discrete Optimization
- Learning Features and their Transformations by Spatial and Temporal Spherical Clustering
- Next Generation Multicuts for Semi-Planar Graphs
- A Unified Multiscale Framework for Discrete Energy Minimization
- Planar Ultrametric Rounding for Image Segmentation
- Efficient Algorithms for Moral Lineage Tracing
- Correlation Clustering in Data Streams
- Multicuts and Perturb & MAP for Probabilistic Graph Clustering