Correlation clustering

Abstract

Abstract Correlation Clustering addresses clustering problems in which the algorithm has access to some information regarding whether pairs of items should be grouped together or not. Such problems arise in areas like database consistency and natural language processing. Traditional clustering problems such as k-means assume that there is some type of distance measure (metric) on the data items, and often specify the number of clusters that should be formed. In Correlation Clustering, however, the number of clusters to be built need not be specified in advance: it can be an outcome of the objective function. Furthermore, instead of a distance function we are given advice as to which pairs of ..