Fast hierarchical clustering and its validation

Manoranjan Dash, Huan Liu, Peter Scheuermann, Kian Lee Tan

Research output: Contribution to journalArticlepeer-review

67 Scopus citations


Clustering is the task of grouping similar objects into clusters. A prominent and useful class of algorithm is hierarchical agglomerative clustering (HAC) which iteratively agglomerates the closest pair until all data points belong to one cluster. It outputs a dendrogram showing all N levels of agglomerations where N is the number of objects in the dataset. However, HAC methods have several drawbacks: (1) high time and memory complexities for clustering, and (2) inefficient and inaccurate cluster validation. In this paper we show that these drawbacks can be alleviated by closely studying the dendrogram. Empirical study shows that most HAC algorithms follow a trend where, except for a number of top levels of the dendrogram, all lower levels agglomerate clusters which are very small in size and close in proximity to other clusters. Methods are proposed that exploit this characteristic to reduce the time and memory complexities significantly and to make validation very efficient and accurate. Analyses and experiments show the effectiveness of the proposed method.

Original languageEnglish (US)
Pages (from-to)109-138
Number of pages30
JournalData and Knowledge Engineering
Issue number1
StatePublished - Jan 2003


  • Clustering
  • Large and high-dimensional datasets
  • Validation
  • Voronoi diagram

ASJC Scopus subject areas

  • Information Systems and Management


Dive into the research topics of 'Fast hierarchical clustering and its validation'. Together they form a unique fingerprint.

Cite this