Correlation Clustering

We consider the following clustering problem: we have a complete graph on n vertices (items), where each edge (u, /spl upsi/) is labeled either + or - depending on whether a and /spl upsi/ have been deemed to be similar or different. The goal is to produce a partition of the vertices (a clustering) that agrees as much as possible with the edge labels. That is, we want a clustering that maximizes the number of + edges within clusters, plus the number of - edges between clusters (equivalently, minimizes the number of disagreements: the number of - edges inside clusters plus the number of + edges between clusters). This formulation is motivated from a document clustering problem in which one has a pairwise similarity function f learned from past data, and the goal is to partition the current set of documents in a way that correlates with f as much as possible; it can also be viewed as a kind of "agnostic learning" problem. An interesting feature of this clustering formulation is that one does not need to specify the number of clusters k as a separate parameter, as in measures such as k-median or min-sum or min-max clustering. Instead, in our formulation, the optimal number of clusters could be any value between 1 and n, depending on the edge labels. We look at approximation algorithms for both minimizing disagreements and for maximizing agreements. For minimizing disagreements, we give a constant factor approximation. For maximizing agreements we give a PTAS. We also show how to extend some of these results to graphs with edge labels in [-1, +1], and give some results for the case of random noise.

Authors

• Nikhil Bansal 0001
• Avrim Blum
• Shuchi Chawla 0001

Keywords

• Clustering algorithms
• Approximation algorithms
• Computer science
• Training data
• Databases
• Correlation Clustering
• Random Noise
• Estimation Algorithm
• Constant Factor
• Separate Parameters
• Clustering Problem
• Constant Approximation
• Edge Labels
• Number Of Disagreements
• Triangular
• Running Time
• Cluster Size
• Edge Weights
• Optimal Clustering
• Number Of Agreements
• Edge Density
• Negative Edges
• Number Of Mistakes