Cluster Analysis: K-Means and Hierarchical Clustering

What Is Cluster Analysis?

Cluster analysis is an unsupervised learning technique that groups observations into clusters so that observations within the same cluster are more similar to each other than to those in other clusters. Unlike supervised methods (regression, classification), there is no response variable. The goal is to discover natural groupings or structure in the data.

Clustering differs fundamentally from classification. In classification, the groups are known in advance and the task is to predict group membership. In clustering, the groups are discovered from the data itself. This makes clustering inherently more subjective, because there is no "correct" answer to evaluate against.

Two critical preprocessing steps apply to all clustering methods. First, standardize all variables (subtract the mean, divide by the standard deviation) so that each variable contributes equally to the distance calculations. Without standardization, variables measured in large units (e.g., premium in dollars) dominate variables measured in small units (e.g., number of claims). Second, choose an appropriate distance metric. Euclidean distance is the most common choice, but Manhattan distance or other metrics may be appropriate depending on the data.

K-Means Clustering

K-means partitions n observations into exactly K clusters by minimizing the total within-cluster sum of squares (WCSS): minimize sum_{k=1}^{K} sum_{i in C_k} ||x_i - mu_k||^2, where C_k is the set of observations in cluster k and mu_k is the centroid (mean) of cluster k.

The algorithm proceeds iteratively. Step 1: Initialize K centroids (randomly selected observations, or by the K-means++ method which spreads initial centroids apart). Step 2: Assign each observation to the nearest centroid. Step 3: Recompute each centroid as the mean of the observations assigned to it. Repeat Steps 2 and 3 until assignments no longer change (convergence).

K-means always converges, but to a local minimum that depends on the initial centroids. Different initializations can produce different clusterings. To mitigate this, run the algorithm with multiple random starts (e.g., 20 or 50) and keep the solution with the lowest WCSS.

A worked example: given 6 observations in two dimensions, {(1,2), (1.5,1.8), (5,8), (8,8), (1,0.6), (9,11)}, and K = 2. After initialization and several iterations, K-means might produce clusters {(1,2), (1.5,1.8), (1,0.6)} with centroid (1.17, 1.47) and {(5,8), (8,8), (9,11)} with centroid (7.33, 9.0). The within-cluster SS quantifies how tight each cluster is.

Choosing the Number of Clusters

K-means requires specifying K in advance, which is often the hardest decision. Several methods help guide this choice.

The elbow method plots the total WCSS against K for K = 1, 2, 3, ..., and looks for a "bend" or "elbow" where adding another cluster provides diminishing returns in reducing WCSS. The WCSS always decreases as K increases (it equals zero when K = n), so you look for the point where the rate of decrease markedly slows.

The silhouette score measures how well each observation fits its assigned cluster relative to the next-best cluster. For observation i, the silhouette value s(i) = (b(i) - a(i)) / max(a(i), b(i)), where a(i) is the average distance to other points in the same cluster and b(i) is the average distance to points in the nearest other cluster. Values range from -1 to 1; higher is better. The average silhouette score across all observations summarizes the overall clustering quality. Choose K to maximize the average silhouette score.

The gap statistic compares the WCSS of the actual data to the WCSS of data uniformly distributed over the data range (no cluster structure). The optimal K maximizes the gap between the actual and reference WCSS.

Hierarchical Clustering

Hierarchical clustering builds a nested sequence of clusters represented as a tree diagram called a dendrogram. Unlike K-means, it does not require specifying K in advance. The dendrogram can be cut at any height to produce any number of clusters.

Agglomerative (bottom-up) clustering is the most common approach. It starts with each observation as its own cluster (n clusters) and repeatedly merges the two closest clusters until only one cluster remains. The sequence of merges defines the dendrogram.

The linkage method defines how the distance between two clusters is measured. Single linkage uses the minimum distance between any pair of observations (one from each cluster). It can find elongated clusters but is sensitive to noise ("chaining"). Complete linkage uses the maximum distance, producing compact clusters but sensitive to outliers. Average linkage uses the mean distance between all pairs. Ward's method merges the pair that produces the smallest increase in total WCSS, tending to produce compact, roughly equally sized clusters. Ward's method is the most commonly used in practice.

To obtain K clusters from the dendrogram, cut the tree at the height that produces K groups. The height at which clusters merge reflects the dissimilarity between them. Large jumps in merge height suggest a natural number of clusters.

Comparing K-Means and Hierarchical Clustering

K-means is computationally efficient (O(n * K * iterations)) and scales well to large datasets. It produces spherical, equally sized clusters because it minimizes the sum of squared Euclidean distances. It requires specifying K and is sensitive to initialization.

Hierarchical clustering is more computationally expensive (O(n^2) for distance computation and O(n^2 log n) for the algorithm) and does not scale well beyond a few thousand observations. However, it provides the full dendrogram (allowing exploration of different numbers of clusters), can discover non-spherical clusters (depending on the linkage), and does not require specifying K in advance.

In practice, you might use hierarchical clustering to explore the data and determine a reasonable range for K, then use K-means (which is faster and often gives tighter clusters) for the final clustering.

Actuarial Applications

Clustering is valuable in insurance for several tasks. Market segmentation groups policyholders with similar characteristics to develop targeted products and marketing strategies. Risk classification identifies natural risk groups that may inform rating plans. Fraud detection clusters claims and looks for observations that fall into unusual or isolated clusters. Loss development analysis groups claims with similar settlement patterns.

When using clustering results for actuarial purposes, it is important to validate the clusters by examining whether they correspond to meaningful business distinctions and whether they are stable across different samples of the data.

Study Tips for Exam SRM

For Exam SRM, focus on these key concepts. First, understand the K-means algorithm step by step and know that it converges to a local minimum (hence multiple random starts). Second, know the methods for choosing K (elbow, silhouette, gap statistic). Third, understand the four common linkage methods and their properties. Fourth, be able to read and interpret a dendrogram. Fifth, always remember to standardize variables before clustering. Exam questions may present a small dataset and ask you to perform one iteration of K-means, interpret a dendrogram, or choose between methods based on the characteristics of the data.