Towards Efficient and Improved Hierarchical Clustering With Instance and Cluster Level Constraints
Ian Davidson, Sujith Ravi · 2005
Many clustering applications use the computationally efficient non-hierarchical clustering techniques such as k-means. However, less efficient hierarchical clustering is desirable as by creating a dendrogram the user can choose an appropriate value of k (the number of clusters) and in some domains cluster hierarchies (i.e. clusters within other clusters) naturally exist. In many situations apriori constraints/information are available such as in the form of a small amount of labeled data. In this paper we explore using constraints to improve the e#- ciency of agglomerative clustering algorithms. We show that just finding feasible (satisfying all constraints) solutions for some constraint combinations is NP-complete and should be avoided. For a given set of constraints we derive upper (kmax ) and lower bounds (kmin ) on the value of k where feasible solutions exist. This allows a restricted dendrogram to be created but its creation is not straight-forward. For some combinations of constraints, starting with a feasible clustering solution (k = r) and joining the two closest clusters results in a "dead-end" feasible solution which cannot be further refined to create a feasible solution with r - 1 clusters even though kmin - 1 kmax . For such situations we introduce constraint driven hierarchical clustering algorithms that will create a complete dendrogram. When traditional algorithms can be used, we illustrate the use of the triangle inequality and a newly defined # constraint to further improve performance and use the Markov inequality to bound the expected performance improvement. Preliminary results indicate that using constraints can improve the dendrogram quality.