Hierarchical Agglomerative Clustering with Ordering Constraints

Many previous researchers have converted background knowledge as constraints to obtain accurate clustering. These clustering methods are usually called constrained clustering. Previous ordering constraints are instance level non-hierarchical constraints, like must-link and cannot-link constraints, which do not provide hierarchical information. In order to incorporate the hierarchical background knowledge into agglomerative clustering, we extend instance-level constraint to hierarchical constraint in this paper. We name it as ordering constraint. Ordering constraints can be used to capture hierarchical side information and they allow the user to encode hierarchical knowledge such as ontologies into agglomerative algorithms. We experimented with ordering constraints on labeled newsgroup data. Experiments showed that the dendrogram generated by ordering constraints is more similar to the pre-known hierarchy than the dendrogram generated by previous agglomerative clustering algorithms. We believe this work will have a significant impact on the agglomerative clustering field.