K-means: Build and Check the Clusters

October 2026 · 9 min read

Expanded from Clustering.pdf · View a handwritten page

Clustering groups observations without using target labels. The handwritten notes focus on K-means: choose a few representative centers, assign each point to its closest center, and move the centers to match their assigned points. We will run the whole procedure on six numbers before discussing how to choose the number of groups.

Six points and two starting centers

Choose $K=2$ groups. Start with centers at 1 and 3. A point's squared distance to a center is $(x-\mu)^2$. In more dimensions, add the squared coordinate differences. K-means minimizes the total squared distance from each point to its assigned center.

$C_k$ is the set of points assigned to group $k$, and $\mu_k$ is its center. This objective is called within-cluster sum of squares, WCSS or WSS, and often inertia.

Alternate assignment and averaging

First assign points to their nearest starting center. The point at 2 is tied; we will consistently assign ties to the first center. That gives group 1 the points 1 and 2, and group 2 the points 3, 8, 9, and 10.

Now assign again using centers 1.5 and 7.5. The point at 3 switches to the first group: it is 1.5 away from that center and 4.5 away from the other. Recompute the means and we get 2 and 9.

The third round changes nothing, so we stop. The final objective is:

The assignment step chooses the lowest squared distance with centers fixed. The update step chooses the best center with memberships fixed: differentiating $\sum_i(x_i-\mu)^2$ gives $\mu=\sum_i x_i/n$. Each step therefore cannot increase the objective. It can still settle at a local solution; different initial centers can produce different outcomes.

Implementations can stop when assignments stabilize, center movement becomes small, or an iteration limit is reached. An empty group needs a defined recovery rule, such as reinitializing its center to a data point. Multiple initializations help find a lower objective.

Time and space complexity

Let $n$ be the number of points, $K$ the number of groups, $d$ the number of measurements per point, and $I$ the number of assignment-and-update rounds.

Each round compares all $n$ points with all $K$ centers across $d$ measurements, which takes $O(nKd)$ time. Updating the centers takes $O(nd)$. The space bound stores the data ($nd$ values), the centers ($Kd$ values), and one group label per point ($n$ values). Excluding the already stored data, extra space is $O(Kd+n)$.

K-means++ initialization adds $O(nKd)$ time in a standard implementation that updates each point's nearest-center distance as each center is chosen. If at least one refinement round runs, this is included in the overall $O(nKdI)$ time bound.

Why not keep adding groups?

With one group, the center is 5.5 and WCSS is 77.5. With two groups, it is 4. With three, we can reach 2.5, and with six singleton groups it is zero.

WCSS by itself rewards more groups. The elbow method looks for a point where extra groups bring much smaller improvements. Here the large drop from one to two groups makes two a natural candidate. Real data may have no clear elbow, and independently fitted runs can miss the best solution at some K values.

Check whether a point fits its group

Silhouette compares two average distances for each point. Let $a(i)$ be its mean distance to the other points in its own group. Let $b(i)$ be the smallest mean distance to any other group. The second quantity averages over a whole candidate group; it is not just distance to a center or to the nearest outside point.

For the point at 2 in our final grouping:

Here we use ordinary Euclidean distances, not the squared distances in WCSS. The score lies between −1 and 1. A value near 1 means a point is much closer to its own group; near 0 means the two distances are similar; a negative score means another group is closer on average.

Our six points have an average silhouette of about 0.8065. A singleton is conventionally assigned score 0. The overall silhouette requires at least two groups and fewer groups than observations. It is useful evidence for a grouping, but its preference for well-separated compact groups may not match every application.

Compare separation with cluster diameter

The notes also introduce the Dunn index. We must specify its distance convention. Use the smallest distance between points in different groups as separation, and the largest within-group point-to-point distance as diameter:

Here $\delta(C_r,C_s)=\min_{x\in C_r,\,y\in C_s}d(x,y)$ is the closest cross-group distance, and $\Delta(C_t)=\max_{x,y\in C_t}d(x,y)$ is group $t$'s diameter. We use Euclidean distance $d$ for both.

Larger values indicate more separation relative to spread under this definition. Because it uses extreme distances, one unusual point can strongly affect it. Other Dunn variants use different separation or diameter definitions, so compare like with like.

Use K-means++ to spread out the starting centers

A common K-means setup starts with $K$ randomly selected centers. K-means++ changes only this initialization; after it picks the centers, it uses the same objective and refinement steps as ordinary K-means:

1. Choose the first center uniformly at random from the data points.
2. For each point $x$, calculate $D(x)$, its distance to the closest already chosen center.
3. Select the next center with probability proportional to $D(x)^2$. Repeat steps 2–3 until $K$ centers are chosen.

If the first center is 1, the squared distances are:

The point at 10 has probability $81/199\approx0.4070$ of being selected next. It is the most likely choice, but is not guaranteed: K-means++ samples by squared distance rather than always choosing the farthest point.

Once $K$ centers are chosen, refinement is ordinary Lloyd K-means: assign each point to its nearest center, recompute each center as the mean of its assigned points, and repeat until assignments or centers stop changing. Compared with random initialization, K-means++ makes poor or bunched starting centers less likely, so its refined solution often has lower WCSS and may require fewer restarts to find a good solution. This is not a guarantee that every K-means++ run beats every random-start run. The seeding has an expected $O(\log K)$-factor bound on squared-error WCSS relative to the optimal $K$-cluster solution; Lloyd refinement can only decrease WCSS. See the original K-means++ analysis.

When Euclidean distance makes sense

Euclidean distance is the straight-line distance between two data points. If each point has $p$ numeric measurements, the distance between points $x$ and $y$ is:

For each measurement, subtract one point's value from the other's, square that difference, add all the squared differences, then take the square root. K-means minimizes the sum of squared distances. To assign a point to a center, comparing squared distances gives the same answer as comparing distances.

Before using this distance to group similar points, check these things:

• Each column means the same thing. A column must record the same measurement for every data point. Numbers used only as category labels, such as 1, 2, and 3, do not have meaningful distances. Category 3 is not automatically closer to category 2 than to category 1.
• The units make sense. Equal-sized differences in different columns count the same. If one column can differ by thousands while another differs by tens, the first can dominate because the formula squares each difference.
• Avoid counting the same information twice. If you copy a column, its differences count twice. Two columns that carry similar information can also give that information extra weight. The columns do not need to be unrelated, but overlapping columns can count the same signal more than once.
• Straight-line distance fits the values. With angles, 359° and 1° are close around a circle but look far apart as ordinary numbers.

The data do not need a bell-shaped (normal) distribution, and columns do not have to vary by the same amount. Euclidean distance uses the numbers you give it, so those numbers should reflect what “similar” means for your problem. See the Euclidean formula.

Put features on meaningful scales

Suppose two features are annual income and age. A difference of 10,000 income units contributes 100,000,000 to squared Euclidean distance; a difference of 10 years contributes 100. The raw units make the income coordinate dominate.

Standardization subtracts a feature's training mean and divides by its training standard deviation. It measures differences in standard-deviation units. This can help when equal relative variation is a sensible starting point. A feature with zero variance needs separate handling.

A change in mean alone is different: adding 1,000 to every value in one coordinate leaves all pairwise distances unchanged. Also, equal feature variances do not imply equal contributions to every pair's distance. They describe average spread, while individual pairs can differ in very different directions.

Assumptions behind K-means

K-means represents each group by one mean and assigns each observation to one group. Its main requirements and practical assumptions follow from that choice:

• Numeric means are meaningful. Averaging the chosen features should produce a useful center. Missing values need to be handled before ordinary K-means can calculate distances and means.
• You choose $K$ before fitting. The algorithm finds a partition into that many groups; it does not establish that the data naturally contain that many groups.
• Clusters are compact and roughly round. K-means works best when each group gathers around one center. In two dimensions, that means a roughly circular shape; in higher dimensions, roughly spherical. Long, curved, or interlocking groups can be split or merged incorrectly.
• Differences in spread and population are manageable. A broad or heavily populated group can dominate WCSS, so K-means may split it while merging a smaller nearby group. Similar spreads and sizes are favorable conditions, not strict requirements.

These are assumptions about the usefulness of the grouping, not a requirement for Gaussian data or independent features. The scikit-learn examples show how shape, spread, and group size can change the result.

Advantages and disadvantages of K-means

Use a distance representation that matches the problem, examine the resulting groups, and check whether they remain similar across runs. When many features overlap, a lower-dimensional representation can make distances easier to inspect. That leads to the PCA guide.

From the handwritten notes

This guide expands Clustering.pdf with worked tables and intermediate steps. The PDF contains all the original pages.

View original page 2

Further reading:

• scikit-learn: K-means and clustering evaluation
• scikit-learn: K-means assumptions and limitations
• SciPy: Euclidean distance
• Arthur and Vassilvitskii: K-means++ seeding