Building a Concept Hierarchy by Hierarchical Clustering with Join/Merge Decision

Abstract

Concept hierarchies are important for generalization in many data mining applications. We propose a method to automatically build a concept hierarchy from a provided distance matrix. The method is a modification of traditional agglomerative hierarchical clustering algorithm. When two closest clusters are selected for combining into a new cluster, the algorithm either creates a new cluster with the two original clusters as its sub-clusters, or let a cluster join the other without creating a new cluster at the higher level of the hierarchy. For the purpose of algorithm evaluation, a distance matrix is derived from the concept hierarchy built by algorithm. Root mean squared error between the provided distant matrix and the derived distance matrix is used as evaluation criterion. Empirical results show that the traditional algorithm under complete link strategy performs better than the other strategies, our algorithms perform almost the same under the three strategies, and our algorithms perform better than the traditional algorithms under various situations.