Spring 2009 CSC 466: Knowledge Discovery from Data Alexander Dekhtyar Data Mining: Clustering/Unsupervised Learning Hierarchical Clustering Hierarchical Clustering

Hierarchical Clustering. Hierarchical clustering methods construct a dendro-gram of the input dataset. Unlike partitional clustering methods, hierarchical clustering methods do not produce specific partitions of data into disjoint clusters. Rather, the data is organized in the dendrogram by percieved similarity. By cutting the dendrogram horizontaly, we obtain clusters. The clusters are associated with the specific cut. The cuts are typically guided by a threshold on the similarity of data points within the cluster. Dendrogram. A dendrogram of a dataset is a labeled binary tree with the fol-lowing properties: • The leaves of the dendrogram are individual datapoints from the input dataset D. Each point of the dataset is associated with exactly one leaf. • The internal nodes of the dendrogram are labeled. Typically, labels are real numbers. • Each internal node represents a cluster of data points assembled at a specific threshold. The label of the node represents the threshold (similarity betwee