Constrained clustering by a novel graph-based distance transformation

In this work we present a novel method to model instance-level constraints within a clustering algorithm. Thereby, both similarity and dissimilarity constraints can be used coevally. The proposed extension is based on a distance transformation by shortest path computations in a constraint graph. With a new technique cannot-links are consistently supported and the dissimilarity is extended to their neighbourhoods. We quantitatively compare the results achieved by our COPGB-K-Means algorithm with the state-of-the-art algorithms on standard databases and show that qualitatively good results and a fast realisation are not mutually exclusive.