Hierarchical Clustering Compared with K-Means

Two Different Ways to Form Clusters

Hierarchical clustering and k-means both organize observations into groups, but they do so through different processes. An agglomerative hierarchical method repeatedly merges clusters to build a nested sequence of partitions. K-means instead starts with a chosen number of clusters and repeatedly reassigns observations and updates cluster centers. These differences matter: the methods can give different answers on the same data, and each is sensitive to different modeling choices.

The main comparison is not simply “which method is better?” Ask what output is needed, whether the observations have a meaningful centroid geometry, how much the results should depend on initialization, and whether extreme observations may dominate the analysis. Both methods can be affected by variable scaling, but their mechanisms and assumptions differ.

What Must Be Chosen in Advance?

For standard k-means, the number \(K\) of clusters must be specified before fitting. The algorithm returns a partition with exactly \(K\) nonempty clusters, provided the data and implementation permit such a solution. Choosing \(K\) is therefore part of using the method; k-means itself does not produce a full hierarchy of solutions for every possible cluster count.

Agglomerative hierarchical clustering can build a complete merge tree without selecting the final number of clusters in advance. A user may then choose a number of clusters by cutting the tree, or use a dissimilarity threshold. This postpones the choice, rather than eliminating it: interpreting a particular partition still requires deciding where or how to cut.

The distinction is useful when the analysis needs a record of how groups combine at multiple levels. A dendrogram provides that nested history. K-means provides a single fitted partition for the selected \(K\), not a sequence of nested partitions. Its solution for \(K=3\) need not contain the solution for \(K=4\) as a refinement.

K-Means: Reassignment and Centroid Geometry

Suppose the observations are vectors \(x_1,\ldots,x_n\), with each \(x_i\) having \(p\) numerical features. For a partition into \(K\) nonempty clusters \(C_1,\ldots,C_K\), the mean of cluster \(C_j\) is \(\bar{x}_j\). The standard k-means objective is the within-cluster sum of squares:

The standard iterative algorithm alternates two operations. Given current centers, it assigns each observation to a nearest center using squared Euclidean distance. Given those assignments, it replaces each center by the mean of its assigned observations. Each operation does not increase the objective: nearest-center assignment minimizes each observation’s squared distance among the current centers, and the mean minimizes the sum of squared distances within a fixed cluster. The process stops when assignments or centers no longer change, or when a specified stopping rule is met.

The cross-product term vanishes because \(\sum_i(x_i-\bar{x})=0\). The second term on the right is nonnegative and is zero only when \(c=\bar{x}\). Therefore the mean minimizes the sum of squared distances. This explains why updating a cluster center to its mean cannot increase the k-means objective while assignments are fixed.

The objective is tied to Euclidean geometry and squared distances. A numerical feature measured on a much larger scale can dominate the distance unless features are appropriately scaled for the application. Standard k-means is not a general method for arbitrary dissimilarity matrices: it needs meaningful numerical means and Euclidean distances to those means.

Hierarchical Clustering: Merges Are Retained

In agglomerative hierarchical clustering, once two clusters have merged, that merge is not undone at a later step. The rule for choosing the next pair depends on the specified linkage and dissimilarity. As established in the earlier material on linkage rules, single, complete, average, and Ward linkage can favor different merge sequences and cluster shapes. A dendrogram records those successive merges and allows a later cut to produce a partition.

This creates a different kind of dependence from k-means initialization. A hierarchical algorithm does not need initial centers, but its tree depends on the chosen distance and linkage. Tied distances can also allow nonunique merge sequences. In contrast, k-means can change assignments after each center update, but the final partition can depend on the starting centers. Neither process guarantees that every plausible modeling choice leads to the same groups.

Initialization and Local Solutions

K-means reduces its objective through alternating steps, but the objective is not generally minimized globally by every run. Different initial centers can lead to different final assignments and different values of WSS. Multiple starts can help reveal this sensitivity, but they do not turn a single run into a proof of a global minimum.

Hierarchical clustering does not have this particular dependence on starting centers because it starts with singleton clusters. It is not thereby free of choices: the selected distance, linkage, tie handling, and cut all matter. In particular, because merges are retained, a locally appealing early merge can constrain all later partitions in that tree.

Distance Geometry and Outliers

K-means favors groups that can be represented by means and judged by squared Euclidean distance. It is therefore most interpretable when the features are quantitative and a mean is meaningful. A very distant observation can have a large effect: squared distance gives large residuals disproportionate weight, and the mean itself can move toward the extreme value.

Hierarchical clustering can use different dissimilarities and linkage rules, subject to the requirements of the particular method. Its response to an outlier is not uniform. A distant observation may remain a separate branch until a large merge height, while other linkages can let it affect cluster-to-cluster distances differently. The earlier material on outliers under different linkage rules is important here: “hierarchical clustering is robust to outliers” is not a general conclusion.

Both approaches are affected by feature scaling when distance calculations are used. For example, if one feature is measured in thousands and another in tenths, the first may dominate ordinary Euclidean distances. Rescaling should reflect the meaning and purpose of the analysis, not be applied mechanically; standardizing variables changes the geometry and can change the resulting clusters.

Choosing Between the Methods

Choose hierarchical clustering when a nested merge history or a flexible dissimilarity-and-linkage specification is central to the task, and when the cost of building and storing the hierarchy is acceptable for the data size. Choose k-means when a specified number of compact, mean-representable groups is useful and squared Euclidean distance is appropriate. These are modeling considerations, not guarantees that either method will discover uniquely “true” groups.

A practical comparison should hold the observations and feature preprocessing fixed, then examine whether the resulting partitions answer the intended question. With k-means, compare multiple initializations and inspect the resulting WSS and assignments. With hierarchical clustering, state the dissimilarity, linkage, and cutting rule. In both cases, assess whether scaling and extreme observations are driving the result.

• Use k-means only when cluster means and the squared Euclidean objective are meaningful for the features.
• Use a hierarchical tree when nested groupings or a choice of cut after fitting is valuable.
• Do not equate “no starting centers” with “no modeling choices”; linkage and distance define the hierarchical procedure.
• Do not equate “the algorithm converged” with “the k-means solution is globally optimal.”