8 K means, K medoids

What does clustering aim to find?

Groups of similar observations without using target labels to define the fit.

What is the K-means objective?

Minimize WSS = sum_k sum_(i in C_k) norm(x_i-mu_k)².

What are the two alternating K-means steps?

Assign each observation to its nearest centroid; recompute each centroid as the mean of its assigned observations.

Why is the mean the K-means centroid?

For a fixed cluster, it minimizes the sum of squared Euclidean distances to the center.

Does K-means guarantee the global minimum?

No. It can converge to a local optimum that depends on initialization.

Why use several random K-means starts?

To reduce sensitivity to a poor initialization and choose a better attained solution.

What does nstart control in R's kmeans()?

The number of random initial configurations tried.

Why does K-means favor roughly compact spherical groups?

Its assignment and objective use squared Euclidean distance to point centroids.

Why is K-means sensitive to outliers?

Squared distances make distant observations contribute strongly and can pull the centroid.

Why should K be chosen rather than simply maximizing it?

WSS usually decreases as K increases, even if the extra clusters are not meaningful.

What does the elbow heuristic look for?

A point where adding clusters yields diminishing reductions in within-cluster variation.

Does the elbow guarantee a true number of clusters?

No. It is a heuristic and a clear elbow may not exist.

For data (1,3,6,8) and initial centers 1 and 6, what is the first K-means assignment?

{1,3} joins center 1; {6,8} joins center 6.

What are the updated means for clusters {1,3} and {6,8}?

2 and 7.

What is the updated WSS for clusters {1,3} and {6,8}?

1+1+1+1=4.

What is a medoid?

An actual observed object chosen to represent a cluster.

How does K-medoids differ from K-means?

It uses observed representatives and can use suitable dissimilarities beyond squared Euclidean distance.

Why is K-medoids often more robust to extreme observations?

A representative must be an observed object and is chosen by its aggregate dissimilarity rather than an unrestricted squared-distance mean.

What does PAM stand for?

Partitioning Around Medoids.

What is agglomerative hierarchical clustering?

Start with singletons and repeatedly merge the pair of clusters selected by a linkage rule.

What is a dendrogram?

A tree showing the sequence of hierarchical merges and their associated merge levels.

How is a flat partition obtained from a dendrogram?

Cut the tree at a chosen height or to obtain a chosen number of groups.

What is single linkage?

The minimum pairwise dissimilarity between points in the two clusters.

What is complete linkage?

The maximum pairwise dissimilarity between points in the two clusters.

What is average linkage?

The average of all pairwise dissimilarities across the two clusters.

What does Ward's merge criterion minimize?

The increase in within-cluster sum of squared deviations for appropriate Euclidean data.

What is Ward's SSE increase for merging clusters A and B?

Delta SSE = n_A n_B/(n_A+n_B) times norm(mu_A-mu_B)².

For clusters {0,4} and {5,9}, what are single, complete and average linkage distances?

Single=1; complete=9; average=(5+9+1+5)/4=5.

For clusters {0,4} and {5,9}, what is Ward's SSE increase?

Each has size 2 and means 2 and 7; Delta SSE=(2*2/4)*25=25.

Can an ordinary agglomerative method undo an early merge?

No. The merge sequence is normally irreversible.

Why can hierarchical results change after scaling?

Scaling changes distances, which can change both the merge order and the resulting groups.

What causes the single-linkage chaining effect?

Clusters can connect through sequences of close point pairs even when their overall shapes are elongated.