Correlation Clustering Methodologies and their Fundamental Results

Abstract

Correlation clustering possibly represents the most intuitive form of clustering construction. It gives solutions that can be approximated while automatically selecting the number of clusters. This approach handles scenarios where the focus is on relationships between the objects instead of on actual representations of the objects. The suitability of this method extends to the structured objects for which feature vectors are not easy to obtain. Given the increasing scale of data these days, correlation clustering has become a powerful addition to the fields of data mining and agnostic learning. Correlation clustering considers a weighted graph G = (V;E), where the edge weight indicates whether two nodes are similar (positive edge weight) or different (negative edge weight). The task is to find a clustering that either maximizes agreements or minimizes disagreements. Unlike other clustering algorithms this does not require choosing the number of clusters(k) in advance. The objective to minimize the sum of weights of the cut edges is independent of the number of clusters. Many methodologies, such as approximations and linear programming formulations, have been used to approach this problem.