Charta is on Google Play: practise on the go. Get the app
Charta

Outline how K-means assigns the observations in a sample to separate clusters.

FRM® Part I · Quantitative Analysis · Machine-Learning Methods · FRM1.QA.14.f

The idea

K-means is an unsupervised method that splits observations into a chosen number K of clusters. The analyst first sets K, which the algorithm cannot choose itself. K starting centroids are picked, often at random. Every observation is then assigned to the nearest centroid, usually by Euclidean distance. Each centroid is recomputed as the mean of the observations assigned to it. Assignment and centroid updates repeat until the assignments stop changing. The result can depend on the starting centroids, so the algorithm is often run several times. Features should be rescaled first because distance is dominated by large-scale variables. The total within-cluster distance always falls as K rises, so K is chosen with methods such as the elbow plot, not by minimising that total.

A practice question

From the question bank, with the reason each wrong option is wrong.

Which input must the analyst specify before running K-means?

  1. The cluster label of each observation.Why not: K-means is unsupervised and creates labels itself.
  2. The number of clusters, K. - correct
  3. The target variable to be predicted.Why not: There is no target in K-means.
  4. The number of principal components to retain.Why not: That is a PCA setting, not a K-means input.

K-means needs K in advance. It cannot determine the number of clusters from the data on its own.

A harder one

A point at (3, 4) is to be assigned using Euclidean distance. The centroids are C1 (1, 1), C2 (5, 6) and C3 (6, 1). What is the distance from the point to the centroid it is assigned to?

  1. 3.61Why not: Distance to C1, which is not the nearest centroid.
  2. 8.00Why not: Squared distance to C2, without taking the square root.
  3. 4.00Why not: Manhattan (sum of absolute differences) distance to C2.
  4. 2.83 - correct

Distances: C1 = sqrt(13) = 3.61, C2 = sqrt(8) = 2.83, C3 = sqrt(18) = 4.24. The nearest is C2, at 2.83.

The hardest tier

One-dimensional data are 1, 2, 4, 9, 11 and 12. K-means with K = 2 starts with centroids at 2 and 4, and iterates to convergence using absolute distance. What are the final centroids?

  1. 1.50 and 9.00Why not: The centroids after the first update only; the point 4 is still reassigned in the next pass.
  2. 2.33 and 9.00Why not: Updates only one centroid after the reassignment.
  3. 2.00 and 10.67Why not: Uses the median of the lower cluster instead of its mean.
  4. 2.33 and 10.67 - correct

First pass: {1, 2} and {4, 9, 11, 12} give 1.5 and 9.0. Second pass: 4 moves to the lower cluster, giving {1, 2, 4} = 2.33 and {9, 11, 12} = 10.67. No further moves occur.

In the app: 6 practice questions on this outcome, spaced review that brings it back before you forget it.

Start free →

More in Machine-Learning Methods