Hierarchical and k ‐Means Clustering
Daniel T. Larose · 2004
Chapter Eight begins with a review of the clustering task, and the concept of distance. Good clustering algorithms seek to construct clusters of records such that the between-cluster variation is large compared to the within-cluster variation. First, hierarchical clustering methods are examined. In hierarchical clustering, a treelike cluster structure (dendrogram) is created through recursive partitioning (divisive methods) or combining (agglomerative) of existing clusters. Single-linkage, complete-linkage, and average-linkage methods are discussed. The single-linkage and complete-linkage clustering algorithms are walked-through, using a small univariate data set. Differences in the resulting dendrogram structure are discussed. The average-linkage algorithm is shown to produce the same dendrogram as the complete-linkage algorithm, for this data set, though not necessarily in general. Next, we turn to the k-means clustering algorithm, beginning with the definition of the steps involved in the algorithm. Cluster centroids are defined. The k-means algorithm is walked-through, using a tiny bivariate data set, showing graphically how the cluster centers are updated. An application of k-means clustering to the large churn data set is undertaken, using SAS Enterprise Miner. The resulting clusters are profiled. Finally, the methodology of using cluster membership for further analysis downstream is illustrated, with the clusters identified by SAS Enterprise Miner helping to predict churn. The exercises include challenges to readers to construct single-linkage, complete-linkage, and k-means clustering solutions for small univariate and bivariate data sets. The hands-on analysis problems include generating k-means clusters using the cereals data set, and applying these clusters to help predict nutrition rating.