—

Data Mining

K-Means and Hierarchical Clustering

Published: 2026-08-05

Level: postgraduate

Audience: Postgraduate students in Data Mining

Prerequisite Knowledge

This lecture builds on the following concepts from earlier lectures. If any feel unfamiliar, review the linked notes before proceeding.

Previously Covered in This Subject

What clustering is: intra- and inter-cluster similarity — covered in Lecture 13 (Clustering and K-Means)
Why clustering is subjective: the "how many clusters" question — covered in Lecture 13 (Clustering and K-Means)
Types of clustering: hard vs soft, flat vs hierarchical, agglomerative vs divisive — covered in Lectures 2 and 13
Types of clusters: center-based, well-separated, continuous, density-based — covered in Lecture 13 (Clustering and K-Means)
K-means overview: inputs, four steps, convergence, complexity — covered in Lecture 13 (Clustering and K-Means)
Choosing the number of clusters and measuring cluster quality — covered in Lecture 13 (Clustering and K-Means)
Data transformation and normalization for distance-based algorithms — covered in Lecture 4 (Data Preprocessing: Noise, Integration, Transformation, and Reduction)
Outlier analysis — covered in Lecture 4 (Data Preprocessing: Noise, Integration, Transformation, and Reduction)

This session continues the clustering topic: after a quick revision of the basics, it takes K-means apart in detail — centroid initialization, stopping criteria, the centroid-versus-medoid distinction, time complexity, the SSE objective, finding K, empty clusters, pre- and post-processing, limitations — and then builds the bridge to hierarchical clustering: coarser-to-finer hierarchies, agglomerative versus divisive methods (AGNES and DIANA), bisecting K-means, and the elbow method for estimating K.

Exam note: everything discussed in the course until the last class is part of the comprehensive exam. This session's content — K-means mechanics, SSE, complexity, limitations, hierarchical clustering, and the elbow method — is all examinable material.

14.1 Recap: What Clustering Is

Your eyes can already spot groups in a picture — rows of students, clusters of stars, clumps of customers on a scatter plot. So why is clustering one of the hardest problems in data mining? Because a machine has no eyes: it needs a definition of similarity and a measure of group quality. This section rebuilds those definitions, because every algorithm in the rest of the session (K-means, bisecting K-means, hierarchical clustering) is a different way to turn them into a concrete procedure.

14.1.1 Natural Groups and Homogeneity

Clustering is the task of finding natural groups in the data. Given a set of data points, we want to find groups or clusters such that data points inside one cluster are more similar to each other than they are to points outside it. In the class's words: one cluster is homogeneous in nature, and data points in two separate clusters are less similar to each other. That is how you divide the data. These basics were established in the previous session, where clustering was introduced as the unsupervised counterpart of classification — here they are restated because the whole lecture rests on them.

The aim of clustering is captured by two phrases that will come back again and again:

High intra-cluster similarity — inside the cluster, two different points should have high similarity. This is the cohesiveness of a cluster.
Low inter-cluster similarity — two points taken from two different clusters should have less similarity. This is the distinctness between clusters.

So a good cluster is one where points inside it are cohesive and clusters are distinct from one another. The quality of a cluster depends on how we define similarity (distance, density, connectivity, and so on) and how we implement that definition.

Concrete picture of intra- versus inter-cluster similarity.

Imagine a classroom scatter plot of two attributes per student, say study hours per week on the $X$ axis and exam score on the $Y$ axis. Suppose the points visually form two blobs: a high-scoring group on the top right and a low-scoring group on the bottom left.

Two students inside the top-right blob have a small distance between them — that small distance is their high intra-cluster similarity, their cohesiveness.
A student in the top-right blob and a student in the bottom-left blob are far apart — that large distance is their low inter-cluster similarity, their distinctness.

A clustering that keeps the blobs intact scores well on both phrases; a clustering that mixes the two blobs violates both.

14.1.2 Clustering Is Subjective and Ill-Posed

Clustering is a very subjective, ill-posed problem. Two images (or two data points) might be similar in some sense and dissimilar in another sense; it depends entirely on the question you ask. The class example used two images: if you ask whether the eyes are similar, the answer is yes; if you ask whether the hairs are similar, again yes; but if you ask whether the noses are similar, the answer is no. So based on the question being asked, the same two data points can count as similar or dissimilar.

Q: But similarity is similarity — how can the same two points be both similar and dissimilar?

A: Because "similar" is not a single measurement; it is always similar with respect to some question. Two portraits share eyes and hair (similar) but differ in noses (dissimilar). Clustering inherits this ambiguity: there is no ground-truth answer key that says which grouping is correct. This is what "ill-posed" means — the problem statement does not uniquely determine the answer.

The same subjectivity appears in counting clusters. If you hand a data set to different people and ask "how many clusters are there?", some will say two, some will say four, some will say six — and all of them are correct, because the answer depends on the question. The questions you can ask of a clustering include: how many clusters are in the data set? What is the size of each cluster? Are there any sub-clusters? Can we further aggregate or divide some clusters? How do we handle outliers?

These questions return throughout the session: the "how many clusters?" question is exactly the problem of finding $K$ (Section 14.8), the aggregate-or-divide question is exactly hierarchical clustering (Section 14.12), and the outlier question is exactly the pre-processing debate (Section 14.9).

14.1.3 Applications

Real-world: Google News is one example of clustering in production — different news articles, based on their similarity, are put into buckets so it is convenient for the reader to read or get information about a particular news in a broader fashion. Real-world: market segmentation is another application of clustering; other examples exist as well.

The previous session added more applications to this list: labeling data for classification (cluster first, then hand-label the clusters instead of the individual points), data reduction (replace a cluster by its representative, shrinking the data set), and organizing search results or a music library into coherent groups. The pattern across all of them: clustering turns a pile of unlabeled objects into a small set of meaningful categories.

14.1.4 Types of Clustering

Clustering methods differ along several axes, and the class reviewed the main ones:

Hard versus soft clustering. In hard clustering, one point can only be associated with one cluster. In soft clustering, one point can be associated with two or more clusters (with some membership degree).
Flat versus hierarchical clustering, distinguished by partitioning criteria. In flat clustering, we partition the data set into multiple disjoint partitions. In hierarchical clustering, we build nested clusters in a tree-like structure: cluster C1 can be part of cluster C2, and C1 and C2 can both be part of C3 — we are not physically partitioning the data, we are building nested clusters. We will spend most of this session on this distinction.
Two ways of developing the hierarchy: agglomerative and divisive (covered in detail below).
Similarity measure: how do you define similarity? One way is distance — if two points are close to each other they are similar, if far they are dissimilar. K-means is a distance-based (similarity-based) clustering algorithm. Another way is connectivity-based similarity — you find the connectivity between two points and build clusters on that basis.
Sequential versus simultaneous: if all the steps of the clustering algorithm have to be done one by one, it is called sequential; otherwise it is called simultaneous.

A useful way to read this list: each axis is a choice the algorithm designer makes. K-means, the next section's topic, is the conjunction of four such choices — flat, hard, distance-based, and sequential. When a later section says "K-means is a flat, hard, distance-based clustering algorithm," it is simply naming the boxes it ticks in this taxonomy.

14.1.5 Types of Clusters

Depending on the method, clustering produces different kinds of clusters:

Center-based cluster: a cluster is a set of data objects such that each point in the cluster is closer to the center of its own cluster than to the center of any other cluster.
Well-separated cluster: a cluster is a set of points such that any point in the cluster is closer to every other point in its own cluster than to any single point not in the cluster.
Continuous cluster: a cluster is a set of data points such that a point in the cluster is closer to one or more points in its own cluster than to any other point not in the cluster — the cluster grows in a continuous fashion.
Density-based cluster: the data set is divided based on density (to be discussed in detail when we reach the DBSCAN algorithm).
Shared-property cluster: clusters defined by a property shared among the members.

Cluster type	What defines membership	Example shape
Center-based	Closeness to the cluster's center	Spherical blob around a mean
Well-separated	Closeness to all members of the cluster	Compact, isolated ball
Continuous	Closeness to at least one member	Chains or elongated strands
Density-based	Density of the neighborhood	Any shape, as long as it is dense
Shared-property	A common property or label	Any set sharing a value

One consequence worth remembering now: the type of cluster an algorithm produces is fixed by its definition, not by the data. K-means produces center-based clusters by construction — which is why, in Section 14.10, it silently fails on clusters of other shapes. The mismatch between the cluster type the data actually contains and the cluster type the algorithm can produce is the root of most clustering failures.

14.1.6 What Makes a Good Cluster

We want to produce high-quality clusters: high intra-cluster similarity (cohesiveness — points inside are very similar) and low inter-cluster similarity (distinctness — points from different clusters are dissimilar). The quality of the cluster depends on the similarity measure we pick — distance, density, connectivity — and on how we implement it. These are the requirements every clustering algorithm must satisfy, and the rest of the session examines K-means against them.

Exam note: clustering groups points so that intra-cluster similarity is high (cohesion) and inter-cluster similarity is low (distinctness); the task is subjective and ill-posed because similarity depends on the question asked. K-means is a flat, hard, distance-based clustering algorithm that produces center-based clusters — this taxonomy sentence is a standard exam question, and it explains why K-means struggles with non-spherical, unequal, or differently dense clusters later in this session.

The next section takes the first algorithm built on this foundation — K-means — and walks through its four steps on a concrete example.

14.2 The K-Means Algorithm

14.2.1 Inputs, Outputs, and the Nature of the Algorithm

Purpose. K-means answers a single question: given $n$ unlabeled points and a requested number of groups $k$ , divide the points into $k$ disjoint groups so that points in the same group are close together. It is the workhorse of flat, center-based clustering — simple, fast, and still one of the most used clustering algorithms in practice.

K-means takes two inputs. First, all the data points $x_{1}, x_{2}, \dots, x_{n}$ , each of which can be $d$ -dimensional (defined by five attributes means $d = 5$ , by two tuples means $d = 2$ ). Second, the number of clusters $k$ — how many clusters you want to find in the data set. The output is the $k$ clusters themselves.

Inputs & Outputs.

Input 1: the data set $X = {x_{1}, x_{2}, \dots, x_{n}}$ , where each point $x_{i} \in R^{d}$ is a vector of $d$ attribute values. $n$ is the number of points, $d$ the number of attributes.
Input 2: the number of clusters $k$ , a positive integer chosen by the user (how to choose it is the subject of Section 14.8).
Output: $k$ disjoint clusters $C_{1}, C_{2}, \dots, C_{k}$ that together cover all $n$ points — every point belongs to exactly one cluster.

K-means is a flat clustering algorithm (it partitions the data set into disjoint partitions), a hard clustering algorithm (each point belongs to exactly one cluster), a distance-based clustering algorithm, and all its steps are sequential in nature. Each label restates one of the taxonomy choices from Section 14.1.4: flat (not hierarchical), hard (no membership degrees), distance-based (similarity means proximity), sequential (steps execute one after another).

14.2.2 The Four Steps

The algorithm has four steps:

Randomly initialize the centroid(s) — choose the initial cluster centers.
Cluster assignment phase — assign each point to its nearest centroid (nearest cluster).
Recompute the centroid — update each cluster center based on its assigned points.
Iterate steps 2 and 3 repetitively until you converge.

The professor's plain-language description: "First step is randomly initializing the centroid. Second step is something called cluster assignment phase — here each point will be assigned to its nearest centroid on nearest cluster. Third is recomputation of centroid, and fourth step is you iterate step number two and three repetitively till you converge."

Steps with rationale.

Initialize. Pick $k$ starting centroids (Section 14.3 studies how). Why: the centroids need somewhere to start, and their starting position influences the final clustering.
Assign. For each point, compute its distance to every centroid and attach it to the nearest one. Why: this realizes "points close together should share a cluster" — with the current centroids, each point is placed as close to its cluster center as possible.
Recompute. Move each centroid to the mean of its assigned points (the formula is given in Section 14.5). Why: after assignment, each cluster center is updated so it better represents its points; the centroid becomes the true center of its group.
Repeat. Go back to step 2 with the new centroids, then 3 again, until convergence (Section 14.4 defines the stopping rules). Why: the first assignment was based on provisional centers; reassignment lets points migrate as centers improve, and the loop continues until the picture stops changing.

14.2.3 Worked Example: Two Clusters from Scratch

The class walked through K-means on a simple example. We pass $k = 2$ . All the green points on the screen are the data points, and we want to divide this data set into two partitions, two clusters.

Step 1: randomly initialize two centroids $c_{1}$ and $c_{2}$ .
Step 2 (cluster assignment): partition the data set into two parts, assigning every point to whichever of $c_{1}, c_{2}$ is closer.
Step 3 (recomputation): the centroids are recomputed and move to new positions — $c_{1}$ here, $c_{2}$ there.
Step 2 again: reassign all the points to their nearest centroid; the cluster boundaries shift.
Repeat until convergence.

Worked example with real numbers: $n = 6$ points, $k = 2$ .

Take six two-dimensional points:

$A (1, 1), B (1, 2), C (2, 2), D (7, 7), E (8, 7), F (8, 8)$

Two natural clumps are visible — the bottom-left group ${A, B, C}$ and the top-right group ${D, E, F}$ — but the algorithm must discover them without knowing this.

Step 1 (initialize). Pick two random centroids, say $c_{1} = A = (1, 1)$ and $c_{2} = F = (8, 8)$ .

Step 2 (assign). Compute the Euclidean distance of every point to both centroids. For $B = (1, 2)$ :

$dist (B, c_{1}) = (1 - 1)^{2} + (2 - 1)^{2} = 0 + 1 = 1$ $dist (B, c_{2}) = (1 - 8)^{2} + (2 - 8)^{2} = 49 + 36 = 85 \approx 9.22$

So $B$ joins $c_{1}$ 's cluster. Checking all six points the same way:

Point	dist to $c_{1}$	dist to $c_{2}$	Assigned to
A (1,1)	0.00	9.90	$C_{1}$
B (1,2)	1.00	9.22	$C_{1}$
C (2,2)	1.41	8.49	$C_{1}$
D (7,7)	8.49	1.41	$C_{2}$
E (8,7)	9.22	1.00	$C_{2}$
F (8,8)	9.90	0.00	$C_{2}$

Step 3 (recompute). The centroid of $C_{1} = {A, B, C}$ averages the $x$ - and $y$ -coordinates separately:

$c_{1} = (\frac{1 + 1 + 2}{3}, \frac{1 + 2 + 2}{3}) = (\frac{4}{3}, \frac{5}{3}) \approx (1.33, 1.67)$

Similarly $c_{2} = (\frac{7 + 8 + 8}{3}, \frac{7 + 7 + 8}{3}) = (\frac{23}{3}, \frac{22}{3}) \approx (7.67, 7.33)$ . Both centroids have moved inward toward the middle of their groups — they are no longer actual data points.

Step 2 again (reassign). Redo the assignment with the moved centroids. For $A = (1, 1)$ :

$dist (A, c_{1}) = (1 - 1.33)^{2} + (1 - 1.67)^{2} \approx 0.75, dist (A, c_{2}) = (1 - 7.67)^{2} + (1 - 7.33)^{2} \approx 9.32$

$A$ still goes to $C_{1}$ . Every point stays in its current cluster — the recomputed centroid of each group is closer to its own members than to the other group's members, so no point migrates.

Convergence. Since a second recomputation would reproduce the same centroids, nothing can change: the final answer is the blue cluster $C_{1} = {A, B, C}$ centered at $(1.33, 1.67)$ and the red cluster $C_{2} = {D, E, F}$ centered at $(7.67, 7.33)$ .

Sense-check: the two natural clumps we spotted by eye are exactly the two clusters the algorithm found, and every point's distance to its own centroid is far smaller than to the other one — a good clustering by the intra/inter criterion of Section 14.1.

At the end, the data set is split into two clusters — one blue cluster and one red cluster. The lesson of the example: K-means keeps alternating assignment and recomputation, and the clusters stop changing when it converges. Notice the sequence of updates — centroids move, boundaries shift, centroids move again — is exactly the "iterative relocation" that Section 14.1 called the definition of K-means.

Pitfalls for first runs of K-means.

A point is assigned using all $d$ dimensions of the distance, not just one coordinate — forgetting a dimension changes the assignment.
The first assignment is only as good as the initial centroids; a bad start can converge to a bad final clustering (Section 14.3).
K-means always returns $k$ clusters, even if the data has a different number of natural groups — the algorithm never protests (Section 14.8).

The natural next questions are the ones the class asked: where do the initial centroids come from, and when exactly do we stop? Sections 14.3 and 14.4 answer them in turn.

14.3 Initializing the Centroids

14.3.1 Random Initialization and Nondeterminism

How do we initialize the centroid? The naive version of K-means, proposed in the 1950s, initializes the centroids randomly — and subsequent versions also initialize randomly. The problem with random initialization is that the algorithm becomes nondeterministic: based on the centroid location, you might get different clusters. If you choose different initial centroids for the same data set, you end up with different clusters.

This is one of the limitations of K-means: it is dependent on how we initialize the initial centroids. An algorithm should be deterministic — but K-means is not, because based on the initial centroid position, you may get different clusters for the same data set.

Why randomness creeps in. The first step of K-means needs $k$ starting positions, but nothing in the problem tells us where the true clusters are yet — that is exactly what the algorithm is supposed to discover. The 1950s solution was to place the $k$ centroids at random. The randomness is not a bug in the sense of an error; it is a choice the algorithm is forced to make, and the choice influences everything after it. Different starting points are like different starting guesses in a climbing problem: the algorithm climbs to a peak, but not necessarily the highest one, and which peak it reaches depends on where it started.

14.3.2 Making K-Means Deterministic

To make the initialization more deterministic, you have something called K-means++. K-means++ handles the initialization of centroids in a more deterministic way, instead of doing it randomly, using a sort of questioning procedure to find or estimate the position of the initial centroids; after that, all the remaining steps run exactly as before — there is no change in the rest of the algorithm.

The standard K-means++ procedure. The textbook description of K-means++ (Arthur and Vassilvitskii, 2007) works as follows. Pick the first centroid uniformly at random from the data points. For every remaining point, compute its squared distance to the nearest centroid already chosen. Then pick the next centroid at random from the data points, with probability proportional to that squared distance — points far from the existing centroids are much more likely to be chosen. Repeat until $k$ centroids are selected. The effect: the initial centroids are spread out across the data instead of being bunched together, because points that are already well covered by a chosen centroid have almost no chance of being picked next. This is the "questioning procedure" behind the lecture's description: each new centroid is chosen by asking which points the existing centroids represent most poorly. Note that the standard treatment is still probabilistic — it makes results far more consistent and the final SSE far lower on average, but a fixed seed or multiple runs are still needed for exact reproducibility. The rest of the K-means loop (assignment, recomputation, iteration) is unchanged.

Note the goal: making initialization "efficient" is not the point — making the algorithm more deterministic is. That means if you run K-means 50 times, you end up with the same type of clusters. You are not looking for efficiency here; you are looking for determinism.

What "more deterministic" means. The professor's framing of K-means++ is: run K-means 50 times and get the same kind of clusters. Determinism here is a practical goal — reproducibility of results — rather than a mathematical guarantee. Even with K-means++ or any other seeding scheme, most implementations still leave some randomness in the process; the fixes below are the ways to close the gap completely.

Practical ways to fix the nondeterminism, listed in the class:

Run K-means multiple times and keep the version with the least SSE (discussed below).
Initialize the initial centroids with the help of any other algorithm — for example, run hierarchical clustering first, and use its output to find good initial centroids, then converge from there.
Use K-means++ for the initialization.
Pass a fixed value of the seed again and again, so the initial positions of the centroids are more or less the same across multiple runs.
Sometimes post-processing can also help fix the initial-centroid problem.

Scope and pitfalls.

Scope of the fixes: the multi-run-with-least-SSE strategy and the fixed-seed strategy make the output reproducible; K-means++ and hierarchical initialization improve the quality of the starting positions. They solve different halves of the problem, and they can be combined.
Pitfall 1: running K-means once, with random initialization, and treating the result as the answer — the result is one draw from many possible clusterings.
Pitfall 2: expecting a single run of K-means++ to be deterministic — the standard method still samples randomly; only the seed makes it repeatable.
Pitfall 3: confusing "efficient initialization" with "deterministic initialization" — the class was explicit that efficiency is not the point here.

14.3.3 Example: Same Data, Different Clusters

The class showed the same data set twice. In the first run, the centroids were initialized here, here, and here, and the algorithm converged to one set of clusters. In the second run, the same data set was initialized with a different set of centroid positions — one here, one here, one here, another here — and the algorithm ended up with different clusters. So for the same data set, different initial centroid positions produce three different clusters $C_{1}, C_{2}, C_{3}$ . This visualizes the nondeterminism problem directly.

Worked example: the same six points, two different starts.

Reuse the six points from Section 14.2: $A (1, 1), B (1, 2), C (2, 2), D (7, 7), E (8, 7), F (8, 8)$ , with $k = 3$ .

Run 1 — sensible starts: initialize $c_{1}$ near the bottom-left group (say at $A$ ), $c_{2}$ near the middle (say at $(4, 4)$ ), $c_{3}$ near the top-right group (say at $F$ ). Assignment puts ${A, B, C}$ around $c_{1}$ , $D$ around $c_{2}$ , ${E, F}$ around $c_{3}$ . Recomputing and re-assigning converges to the stable clusters $C_{1} = {A, B, C}$ , $C_{2} = {D}$ , $C_{3} = {E, F}$ — a clean, interpretable grouping.

Run 2 — unlucky starts: initialize $c_{1}$ at the bottom-left corner $(0.5, 0.5)$ , $c_{2}$ at $(3, 3)$ , and $c_{3}$ at $(4, 4)$ , both middles bunched together. The two middle centroids compete for the same points: after assignment, $c_{2}$ may capture $C (2, 2)$ and $D (7, 7)$ while $c_{3}$ captures nothing but strays, and the recomputation pulls the centers around. The final clusters can end up as $C_{1} = {A, B}$ , $C_{2} = {C, D}$ , $C_{3} = {E, F}$ — mixing a point from the left group with a point from the right group.

Same data set, same $k = 3$ , two different final clusterings — the only difference is where the centroids started.

Sense-check: both runs minimized SSE locally, but they converged to different local minima. That is the entire problem: K-means finds a local optimum, and the initial centroids decide which one.

Exam note: random initialization makes K-means nondeterministic — the same data can yield different clusters depending on the initial centroids. The goal is determinism, not efficiency. Fixes: multiple runs keeping least SSE, K-means++, initialization from another algorithm (e.g., hierarchical clustering), a fixed random seed, and post-processing. K-means++ seeds centroids far apart by sampling points with probability proportional to their squared distance from the nearest chosen centroid.

The determinism problem interacts with the next question: if K-means converges to different places, how do we even know when to stop? That is the subject of stopping criteria.

14.4 Stopping Criteria

14.4.1 When to Stop Iterating

When do we stop in K-means? You can stop based on your criteria — there are multiple criteria, and the basic idea is: till you converge, you should iterate. The question is how to define convergence. The class listed several ways:

Few points change cluster. If you compare the last two steps and the points in each cluster are more or less the same — there is very little movement of points from one cluster to another — you can stop. You can define the threshold as zero points changed, or five points, etc. "Until relatively few points change the cluster" is one criterion.
No change of centroid. If you have three clusters and the centroids stop moving, you can stop.
Minimum decrease in SSE (sum of squared error). Whenever the decrease in SSE falls below a threshold, stop. (SSE is defined in the next section.)

There can be multiple such criteria; based on your requirement, you can choose one or many.

Why stopping is not automatic. Nothing in K-means "knows" it is done — the algorithm has no concept of a correct answer, only of whether the picture changed. Each stopping rule is a proxy for the same underlying idea: the current clustering is stable enough that another round would not change the answer meaningfully. The three criteria measure stability in three different places: the clusters' membership (points), their geometry (centroids), or their cost (SSE).

How the criteria behave in practice.

Few points change cluster: a natural and commonly used criterion; the threshold is a user choice (zero points changed is the strictest version). Note that even a single point migrating can still change a centroid noticeably in later rounds.
No change of centroid: centroids moving less than some tiny distance $ϵ$ (a tolerance) is the practical implementation; measuring exact zero movement is numerically fragile on a computer.
Minimum decrease in SSE: the strictest and most direct — it checks the objective function the algorithm is actually optimizing (Section 14.7). If the error is barely dropping, more iterations buy nothing.

Any combination of the three can be used (for example, stop when both few points change AND the SSE drop is small). In most implementations, K-means converges quickly in practice — most movement happens in the first few iterations — so the loop rarely runs long.

Exam note: convergence in K-means is user-defined via stopping criteria — few points changing cluster, centroids not moving, or a minimal SSE decrease. The default practical choice is iterating until the assignments stop changing, and the SSE criterion is the most direct because it monitors the objective being optimized.

With the loop's stopping rule settled, the next sections examine what each iteration does in detail — the centroid formula (Section 14.5) and how much each full pass costs (Section 14.6).

14.5 Recomputing the Centroid: Centroid versus Medoid

14.5.1 The Centroid Formula

Step 3 of K-means says "recompute the cluster centroid". How do we find the centroid of a cluster? Very simple — this is the formula the professor gave:

$c_{j} = \frac{1}{n _{j}} x \in C_{j} \sum x$

The verbal description: "inside one cluster, you will do summation of all the points, that means if it is a two-dimensional data point, P1, P2 are all two-dimensional points, you're going to do summation of X coordinate, summation of Y coordinate and divided by the number of points in my cluster. So this will give you centroid position of the cluster."

Here $C_{j}$ is cluster $j$ , $n_{j} = ∣ C_{j} ∣$ is the number of points in the cluster, $x \in C_{j}$ are the points (each possibly $d$ -dimensional), and $c_{j}$ is the resulting centroid. For two dimensions, this is coordinate-wise:

$c_{j} = \frac{1}{n _{j}} x \in C_{j} \sum x_{coord}, \frac{1}{n _{j}} x \in C_{j} \sum y_{coord}$

i.e., average the X coordinates and average the Y coordinates separately.

Why the mean is the right center. The centroid is not an arbitrary choice: of all possible centers, the mean of the cluster's points is the one that minimizes the sum of squared distances from the points to the center. This is exactly what the SSE objective (Section 14.7) needs — recomputing the centroid as the mean is the step that makes the error as small as it can be for the current membership. The two ideas, centroid formula and SSE, are two sides of the same operation.

Worked example: centroid of a five-point cluster.

Take the cluster $C_{1} = {(1, 2), (2, 4), (3, 1), (4, 3), (5, 5)}$ . Here $n_{1} = 5$ . Sum the $x$ -coordinates and the $y$ -coordinates separately:

$\sum x_{coord} = 1 + 2 + 3 + 4 + 5 = 15, \sum y_{coord} = 2 + 4 + 1 + 3 + 5 = 15$

Then divide each sum by $n_{1} = 5$ :

$c_{1} = (\frac{15}{5}, \frac{15}{5}) = (3, 3)$

The centroid is $(3, 3)$ .

Sense-check: $(3, 3)$ sits roughly in the middle of the five points — no coordinate extreme; it is the point that balances the cluster in both dimensions. Note that $(3, 3)$ is not one of the original data points, which is exactly the "imaginary point" property discussed next.

14.5.2 What a Centroid Is

The centroid is the center of the cluster — the average of all the points. It might be a real point or an imaginary point; most likely it is imaginary, because there is no guarantee that a real point of the data set sits exactly at the center of the cluster. The centroid of a cluster is not counted as a point of the cluster — a cluster's centroid can be an imaginary point.

Imaginary, not imaginary-numbers. "Imaginary" here means not actually present in the data set — the centroid is a calculated position, not a sampled one. In the example above, $(3, 3)$ is a perfectly real coordinate pair, but no data point sits there; the centroid is a synthetic representative of the cluster. This matters for cluster counting: a cluster with one point at $(3, 3)$ has its centroid at $(3, 3)$ , but that centroid is not an extra member of the cluster.

14.5.3 Centroid versus Medoid

There are two versions of K-means-style algorithms, distinguished by what "center" means:

Centroid: the center of the cluster is the average of all the points; it can be a real point or an artificial point at the center of the cluster (most likely imaginary).
Medoid: you find the point which is closest to the centroid, and that real point is considered the center of the cluster. In other words, the medoid is a real point; the center of the cluster is forced to be an actual data point.

K-means is a centroid-based clustering algorithm. There are variants of K-means which treat the center of the cluster as a medoid instead, but this distinction does not impact the clustering algorithm too much — K-means will almost remain the same.

Why a medoid is useful. Forcing the center to be a real data point matters when an "average" is meaningless — for example, when points are non-numeric (a cluster of documents has no meaningful average document), or when outliers make the mean unrepresentative (a mean is pulled by extreme values; a medoid, being an actual point, is not). The family of algorithms built on medoids (k-medoids, PAM) exists precisely for these cases. The professor's point stands: within the K-means framework, swapping centroid for medoid changes the algorithm very little mechanically.

Worked example: medoid of the same cluster.

Cluster $C_{1} = {(1, 2), (2, 4), (3, 1), (4, 3), (5, 5)}$ , centroid $(3, 3)$ . Compute the Euclidean distance from each point to the centroid:

$dist ((1, 2), (3, 3)) = (1 - 3)^{2} + (2 - 3)^{2} = 4 + 1 \approx 2.24$ $dist ((2, 4), (3, 3)) = 1 + 1 \approx 1.41, dist ((3, 1), (3, 3)) = 0 + 4 = 2$ $dist ((4, 3), (3, 3)) = 1 + 0 = 1, dist ((5, 5), (3, 3)) = 4 + 4 \approx 2.83$

The closest real point is $(4, 3)$ at distance 1. The medoid of the cluster is $(4, 3)$ — the actual data point nearest the imaginary center $(3, 3)$ .

Sense-check: the medoid is always a member of the data set, unlike the centroid; here the two almost coincide because $(4, 3)$ lies close to the true center.

14.5.4 Student Questions and Answers

Q: What is the difference between a centroid and a medoid?

A: A centroid is the average of all the points in the cluster, and it can be a real point or an imaginary point — most likely imaginary, because there is no guarantee that a real point of the data set sits at the center of the cluster. A medoid is a real point: you find the centroid first, then pick the real point closest to the centroid, and treat that point as the center of the cluster. K-means is a centroid-based algorithm; variants of K-means treat the center as a medoid, but the algorithm itself barely changes.

Exam note: the centroid is $c_{j} = \frac{1}{n _{j}} \sum_{x \in C_{j}} x$ — the coordinate-wise mean of the cluster's points, usually an imaginary (non-data) point. The medoid is the real data point closest to the centroid. K-means is centroid-based; k-medoids variants use the medoid. Be ready to compute a centroid by hand (sum coordinates, divide by cluster size) and to name which point is the medoid.

The next section looks at how expensive this whole loop really is — the time complexity of K-means.

14.6 Time Complexity of K-Means

14.6.1 The Complexity per Step

Let $I$ be the number of iterations (how many times the loop rotates), $K$ the number of clusters we want to find, $N$ the number of data points in the data set, and $D$ the number of attributes that define each point (if a point is defined by five tuples or five attributes, then $D = 5$ ; if by two tuples, $D = 2$ ). The complexity of K-means is derived step by step:

Step 1 (random initialization of centroids): this is a constant operation — you can run a random number predictor which produces the two (or K) values, and it is done. So the cost is $O (1)$ — roughly some constant, not very complex.
Step 2 (cluster assignment phase): each point's distance to each centroid is calculated. Take point $P_{1}$ and centroids $c_{1}, c_{2}$ : you have to calculate the distance between $P_{1}$ and $c_{1}$ , and between $P_{1}$ and $c_{2}$ , and assign $P_{1}$ to whichever distance is minimum. The cost for one point is the number of clusters, $K$ . Doing this for all the points multiplies by $N$ , giving $N \times K$ . But there is one more factor: the distance computation itself. When you compute the distance between two points, you compare them dimension by dimension — first X1, then Y1 — and there are $D$ dimensions between two points, so you multiply by $D$ as well. The assignment step then costs $N \times K \times D$ . (The diagrams in class use $D = 2$ for easy visualizing, but a point can be defined with 10 dimensions, and then the distance must be computed using all 10.)
Step 3 (recomputation of centroid): inside one cluster you add all the points and divide by the number of points — this will be very less, in terms of $N$ or something.
Iterate: all of this is repeated $I$ times, the number of iterations the loop runs.

Where each factor comes from.

$N$ : every data point must be processed — one point cannot be skipped.
$K$ : each point compares itself against every centroid to find the nearest one.
$D$ : a single distance between two $D$ -dimensional points needs $D$ per-dimension differences (one per attribute), e.g., $dist (P_{1}, c_{1}) = \sum_{j = 1}^{D} (P_{1 j} - c_{1 j})^{2}$ .
$I$ : the whole assignment-plus-recomputation cycle repeats once per iteration.

Worked example: counting the work on concrete numbers.

Suppose $N = 1000$ points, $K = 5$ clusters, $D = 10$ dimensions, and $I = 20$ iterations.

Initialization: one random-number step per centroid — a handful of operations, $O (1)$ .
One assignment pass: for each of the 1000 points, compute 5 distances; each distance costs about 10 arithmetic differences. That is $1000 \times 5 \times 10 = 50, 000$ distance-computation operations per pass.
One recomputation pass: each of the 1000 points is added into exactly one cluster sum, so this costs on the order of $N$ operations — roughly 1000, negligible next to 50,000.
Total over all iterations: $20 \times 50, 000 = 1, 000, 000$ operations — one million basic distance computations, all from $I \times K \times N \times D = 20 \times 5 \times 1000 \times 10$ .

Sense-check: the assignment term dominates the recomputation term at every realistic scale ( $K \cdot D ≫ 1$ ), so the formula $I \cdot K \cdot N \cdot D$ is the right headline number.

14.6.2 The Final Complexity

Combining the steps, the final complexity of the K-means clustering algorithm is:

$O (I \cdot K \cdot N \cdot D)$

where $I$ is the number of iterations, $K$ the number of clusters, $N$ the number of data points, and $D$ the number of attributes per point. The dominant term is the assignment step, iterated: $I \times K \times N \times D$ .

The reference textbooks state the same result in their own letters — $O (nk t)$ with $n$ points, $k$ clusters, $t$ iterations — and add the practical note that $K ≪ N$ and $I ≪ N$ normally, so the algorithm scales almost linearly in the number of points. The professor's version $O (I \cdot K \cdot N \cdot D)$ simply makes the per-dimension factor $D$ explicit.

14.6.3 Student Questions and Answers

Q: Where does the D factor come from in the complexity?

A: When we compute the distance between two points, we compare them dimension by dimension — first X1, then Y1, and so on. There are D dimensions between two points, so the distance computation multiplies by D. That is why the assignment step costs N times K times D.

Q: Is this clustering algorithm efficient or not?

A: From experience, K-means is one of the most efficient clustering algorithms. We will compute the same complexity measure for the other clustering algorithms as well — for example, when we do DBSCAN or another clustering algorithm, we will compute the complexity in a similar fashion — and then you can compare how K-means behaves in terms of complexity against the others and decide which one is efficient.

Exam note: be able to derive $O (I \cdot K \cdot N \cdot D)$ step by step: initialization is constant $O (1)$ ; assignment costs $N \times K \times D$ (every point against every centroid, each distance over $D$ dimensions); recomputation is cheap (order of $N$ ); the whole loop repeats $I$ times. K-means is one of the most efficient clustering algorithms, and the same cost analysis is how other algorithms (e.g., DBSCAN) will be compared.

The complexity question is settled, but it only makes sense if we know what the loop is trying to optimize — that is the SSE objective, the next section.

14.7 SSE: The Objective Function of K-Means

14.7.1 What K-Means Optimizes

What we want to minimize is something called intra-cluster distance: inside the cluster, the distance should be minimized, and we do it for all the clusters. If the data set is passed with $K = 3$ , we get three clusters, and inside each cluster we minimize the distance — for all the clusters. This is what the K-means clustering algorithm is optimizing: the sum of squared error, SSE, which is based on Euclidean distance.

Why an objective function at all. The four steps of Section 14.2 describe how K-means moves, but not what it wants. Every clustering algorithm needs a way to say "this clustering is better than that one" — that is the objective function. SSE is K-means's scorecard: it quantifies how tightly the points are packed around their cluster centers, and the algorithm's assignment and recomputation steps are precisely the moves that drive this score down.

14.7.2 The SSE Formula

The professor's plain-language description of the formula: "there are two parts. Part one says go to one cluster, take all the points and compute the distance between the point and its centroid, subtract, and then of course you square it. And you do it for all the k clusters." The formula:

$SSE = i = 1 \sum k x \in C_{i} \sum ∥ x - μ_{i} ∥^{2}$

where $k$ is the number of clusters, $C_{i}$ is cluster $i$ , $x$ runs over every point in cluster $C_{i}$ , and $μ_{i}$ is the centroid of cluster $i$ (the audio says "square mu one X" while describing the formula, so the centroid is denoted $μ$ ). The notation matches the standard treatment in the reference book (Tan et al.), which defines SSE as the sum over clusters and points of $dist (c_{i}, x)^{2}$ — the squared Euclidean distance between each point and its cluster centroid. The professor's $μ_{i}$ is the same object as the book's centroid $c_{i}$ : the cluster mean. The two sums read "for each cluster, for each point in that cluster, square the distance from the point to the cluster's center, and add everything up."

So the sum of squared error takes one cluster at a time, computes the squared distance of every point from its centroid, and adds these up over all $k$ clusters.

14.7.3 Why We Square

Why do we square the distance? Because you do not want to handle negative values: if you square, everything becomes positive, and your graph is also nicer — an exponential fashion. A squared value that is high becomes even higher, so it is easy to identify when SSE is low and when SSE is high. The square forces a nonlinear relationship between the distance and the error term: with just a linear relationship you cannot separate low and high SSE as sharply, but with the square you tie down high values to a higher state. The alternative is a mod (absolute value) operation, which also removes signs but stays linear — you can use mod, or square, or both; the class uses the square.

The math behind the curve. Compare the two candidate error terms for a single point at distance $r$ from its centroid:

$mod: ∣ r ∣ vs. square: r^{2}$

Both remove the sign (negative $r$ and positive $r$ give the same error), which is why either works. But they grow differently: $∣ r ∣$ grows linearly, while $r^{2}$ grows quadratically. A point twice as far away contributes twice the linear error but four times the squared error. The quadratic penalty is what makes bad clusters (large distances) stand out sharply and good clusters (small distances) look cleanly separated — the class's "easy to identify low SSE and high SSE". This squaring is also why the optimal center of a cluster is the mean rather than the median: the mean minimizes the sum of squared errors, while the median minimizes the sum of absolute errors.

14.7.4 Student Questions and Answers

Q: When will the SSE value be zero?

A: When each point is essentially a centroid. If each point is a centroid, and the number of points equals the number of clusters you want to find, then every distance between a point and its centroid is zero, and the sum over all clusters is zero. For example, take four points and pass $k = 4$ : if the first point becomes its own centroid $C_{1}$ , the second point becomes centroid $C_{2}$ , the third centroid $C_{3}$ , and the fourth centroid $C_{4}$ , then each cluster has one point and the distance between the point and the cluster center is zero for every cluster — the SSE value is zero. Can you visualize it? When the points coincide with the centroids and the number of clusters equals the number of data points, SSE = 0.

Worked example: SSE = 0 with four points and $k = 4$ .

Data set $X = {(1, 1), (2, 5), (4, 2), (7, 6)}$ and $k = 4$ . K-means can converge to four single-point clusters: $C_{1} = {(1, 1)}$ , $C_{2} = {(2, 5)}$ , $C_{3} = {(4, 2)}$ , $C_{4} = {(7, 6)}$ . Each centroid equals its only point: $μ_{1} = (1, 1)$ , and so on. Then every distance is zero:

$SSE = cluster C_{1} (0)^{2} + cluster C_{2} (0)^{2} + cluster C_{3} (0)^{2} + cluster C_{4} (0)^{2} = 0$

SSE = 0 — the smallest possible value.

Sense-check: with one point per cluster there is no spread to measure; the "best" score a clustering can have is achieved exactly when $k = n$ .

Q: When will the SSE value be one?

A: That is a trick question — think about it. One student guessed: all the points in one cluster, that is $k = 1$ . Close, but the value will not be one — it will be maximum. The SSE value is maximum when you pass $k$ equals to one, because every point is measured against a single centroid for the whole data set. So SSE is not going to be one; at $k = 1$ SSE is maximum, and as $k$ grows toward $n$ , SSE falls toward zero.

Worked example: why $k = 1$ means maximum SSE, not SSE = 1.

Same data set $X = {(1, 1), (2, 5), (4, 2), (7, 6)}$ , now with $k = 1$ . The single centroid is the mean of all four points:

$μ_{1} = (\frac{1 + 2 + 4 + 7}{4}, \frac{1 + 5 + 2 + 6}{4}) = (\frac{14}{4}, \frac{14}{4}) = (3.5, 3.5)$

The SSE adds the squared distances of every point from $(3.5, 3.5)$ :

$SSE = (1 - 3.5)^{2} + (1 - 3.5)^{2} + (2 - 3.5)^{2} + (5 - 3.5)^{2} + (4 - 3.5)^{2} + (2 - 3.5)^{2} + (7 - 3.5)^{2} + (6 - 3.5)^{2}$ $SSE = 6.25 + 6.25 + 2.25 + 2.25 + 0.25 + 2.25 + 12.25 + 6.25 = 38$

SSE = 38, the largest value this data set can produce — not one.

Sense-check: with a single cluster, every point is measured against the same distant center, so the total error is maximal; the number 1 only appears in the formula as the cluster count, not as the SSE value.

Exam note: everything discussed in the course until the last class is part of the comprehensive exam, including SSE. The formula is $SSE = \sum_{i = 1}^{k} \sum_{x \in C_{i}} ∥ x - μ_{i} ∥^{2}$ , with the sums running over all $k$ clusters and all points in each cluster, and $μ_{i}$ the centroid of cluster $i$ . Two boundary behaviors are classic questions: SSE = 0 when every point is its own centroid ( $k = n$ ), and SSE is maximum at $k = 1$ — not "one".

The SSE is not just an exam formula; it is the lens through which the next several sections inspect K-means — how to choose $k$ (Section 14.8), what happens when clusters come out empty (Section 14.9), and what the objective silently cannot see (Section 14.10).

14.8 Finding the Value of K

14.8.1 An Ill-Posed Problem with No Formula

How do you find the value of $K$ ? If the data is two-dimensional you can look at the scatter plot and see the clusters. But for the same set of data points, if you pass different values of $K$ — $k = 1$ , $k = 2$ , $k = 3$ — the algorithm will behave differently, and if the data is high-dimensional, most likely you will not be able to visualize it. Then how do you find the value of $K$ ?

The hook. K-means demands the one number you almost never know in advance: how many groups the data contains. If the data has only two dimensions, your eyes can count the blobs — but real data sets routinely have dozens or hundreds of attributes, and no human can see blobs in 50 dimensions. The algorithm will not help either: it needs $k$ as an input before it runs. So the question — where does $k$ come from? — becomes a problem in itself.

Finding the value of $K$ in K-means is an ill-posed problem. There is no thumb rule, and there is absolutely no formula available in the literature which says: use this formula and you will always get the optimal number of clusters in the data set. There is no such formula — but there are a lot of hints available:

The elbow method (covered in detail below), which can help you estimate the value of $K$ .
Hierarchical clustering (covered next), which removes the need to guess $K$ at all — you build a hierarchy and cut it at the desired level.
Performance measures, which can also help estimate $K$ .

Why no formula exists. Recall from Section 14.1 that clustering is subjective and ill-posed: different people, answering different questions, legitimately count different numbers of clusters in the same data. If the "right answer" itself is question-dependent, no closed-form formula can produce a universally correct $k$ . What exists instead is a toolbox of estimators — methods that suggest a reasonable $k$ for the question at hand. This is why the class presented them as hints, not rules.

14.8.2 K-Means Works Even with a Bad K

An important behavioral point: does K-means still work if you pass a bad value of $K$ ? Yes, it works. The class showed five data sets, each containing two natural clusters, and ran K-means with different values of $k$ . With $k = 2$ , K-means found the two clusters irrespective of the initial centroid position — it converged properly. With $k = 1$ , it returned one cluster even though there are essentially two clusters in the data set. With $k = 3$ , it still divided the data into three clusters and handed it back. The algorithm does not give you an error for a bad $K$ ; it just finds some clustering and gives it back to you. Whether the quality of the clusters is good or bad, you have to determine — that is not the algorithm's job.

Worked example: the same data, three different $k$ values.

Take one data set that visibly contains two natural clusters, say the two clumps $X = {(1, 1), (1, 2), (2, 1), (2, 2)}$ and $Y = {(7, 7), (7, 8), (8, 7), (8, 8)}$ . Run K-means with different values of $k$ :

$k = 2$ : K-means returns the two natural clusters — the clump $X$ as one cluster, the clump $Y$ as the other — and converges to this clean split no matter where the initial centroids land.
$k = 1$ : K-means returns one cluster containing all eight points. The answer is "wrong" against the natural structure (SSE is maximum, Section 14.7), but the run completes normally — no error, no warning.
$k = 3$ : K-means returns three clusters — for example, it carves the $X$ clump into two small clusters plus the $Y$ clump as the third. Again, no error; the program simply does what it was told.

In all three cases K-means hands back a clustering. The only difference between the runs is the value of $k$ the user supplied.

Sense-check: the algorithm's contract is "produce $k$ clusters," not "produce the right clusters" — which is why the class's warning follows: the quality of the output is the user's responsibility.

The warning that comes with this: never treat K-means as a black box. If you are given a data set and asked to do clustering, do not run K-means at a random $K$ value and give the output back. That does not make sense at all. What you want is to find proper clusters — where the similarity inside one cluster can be useful for answering your question. The K-means clustering algorithm does not say anything about cluster quality; it is up to you to judge whether the output is useful.

Pitfall: the black-box habit. K-means never errors out. Feed it $k = 1$ on data with three natural groups and it returns one cluster; feed it $k = 10$ on two groups and it splits both. The program runs "successfully" every time — and every time it hands you a clustering whose usefulness only you can judge. Treating the output as truth because the program did not complain is the classic K-means mistake. Quality control is the analyst's job, not the algorithm's.

14.8.3 Student Questions and Answers

Q: If $k$ equals to one, what does that mean? How do we find the value of $K$ in K-means?

A: Finding the value of $K$ is an ill-posed problem. There is no thumb rule and no formula in the literature that always gives the optimal number of clusters in a data set. But there are hints: the elbow method, hierarchical clustering, and performance measures can all help you estimate $K$ . If the data is two-dimensional you can visualize it; otherwise you have to take help of these measures.

Exam note: finding $K$ is an ill-posed problem with no formula — but the estimator toolbox is examinable: elbow method, hierarchical clustering (cut the tree), and performance measures. And a bad $K$ does not stop K-means: it always returns some clustering, so never treat K-means as a black box that rejects bad inputs; quality judgment is the user's responsibility.

The next section continues with the practicalities of running K-means well — what to do about empty clusters, and how pre- and post-processing protect the result.

14.9 Empty Clusters and Pre-/Post-Processing

14.9.1 Empty Clusters and How to Handle Them

Sometimes K-means clustering might give you empty clusters. Suppose the data set is passed with $K = 5$ and the algorithm returns five clusters $C_{1}, C_{2}, C_{3}, C_{4}, C_{5}$ — but $C_{5}$ is an empty cluster: there is no point in it. (Remember, the centroid is not counted as a point; the centroid can be an imaginary point.) How do we handle an empty cluster? Two post-processing strategies were given:

Find the point in the whole data set which is contributing the maximum to the SSE value of some cluster, and break that cluster into two parts. Concretely: if the point under discussion contributes maximum to the SSE value of cluster $C_{4}$ , split $C_{4}$ into two clusters — the max-SSE point becomes the new cluster $C_{5}$ , and the remaining points of $C_{4}$ stay as they are. Now $C_{5}$ is no longer empty.
Alternatively, choose the cluster which has the highest SSE overall, and divide that cluster into two parts — this becomes one cluster, that becomes another.

If there are several empty clusters, you iterate: do this step again and again until every cluster is populated. These are all post-processing steps.

Why empty clusters happen. During the assignment step, some centroid can end up with no points at all — every point found another centroid closer. The empty centroid is then in a loop with nothing to average: it has no points, so it cannot move, and its empty state persists. This is a structural outcome of the algorithm, not a data error, and it must be repaired by hand — K-means will not fix it by itself.

Worked example: rescuing the empty cluster $C_{5}$ .

Suppose $k = 5$ and the run returns $C_{1}, C_{2}, C_{3}, C_{4}, C_{5}$ with $C_{5}$ empty. Cluster $C_{4}$ contains five points:

$C_{4} = {(1, 1), (2, 2), (3, 3), (4, 4), (9, 4)}$

with centroid $μ_{4} = (3.8, 2.8)$ . Compute the squared distance of each point from the centroid (its SSE contribution):

$(1, 1) : (1 - 3.8)^{2} + (1 - 2.8)^{2} = 7.84 + 3.24 = 11.08$ $(2, 2) : (2 - 3.8)^{2} + (2 - 2.8)^{2} = 3.24 + 0.64 = 3.88$ $(3, 3) : (3 - 3.8)^{2} + (3 - 2.8)^{2} = 0.64 + 0.04 = 0.68$ $(4, 4) : (4 - 3.8)^{2} + (4 - 2.8)^{2} = 0.04 + 1.44 = 1.48$ $(9, 4) : (9 - 3.8)^{2} + (4 - 2.8)^{2} = 27.04 + 1.44 = 28.48$

The point $(9, 4)$ contributes the maximum, 28.48 — it is the outlier pulling the cluster's SSE up. Strategy 1: split $C_{4}$ at this point. The max-SSE point $(9, 4)$ becomes the new, populated cluster $C_{5} = {(9, 4)}$ , and the remaining four points stay as $C_{4} = {(1, 1), (2, 2), (3, 3), (4, 4)}$ . Every one of the five clusters now has at least one point, and the total SSE drops — the outlier no longer pollutes $C_{4}$ 's centroid.

Strategy 2 (same idea, coarser): pick the cluster with the highest total SSE — whichever cluster that is — and split it into two, again giving the empty centroid a new home.

Sense-check: both strategies use the same principle — an empty cluster is filled by breaking up the cluster that suffers most from a bad fit (highest per-point or total SSE), which simultaneously reduces the overall error.

14.9.2 Pre-Processing: Normalization

Before we run K-means we must normalize the data. Why is normalization important? Because K-means is a distance-based clustering algorithm. If one dimension of a point has dominating numbers, it will dominate the other dimensions as well, and then you will not find the proper center of the cluster. The class example: take a two-dimensional data point whose X coordinate is a dominant number compared to the Y coordinate — since distance is computed across both dimensions, the X dimension will dominate the distance, and the clustering will be wrong. Since it is a distance-based metric, you have to normalize all the dimensions before running K-means on the data.

This normalization problem happens with any distance-based algorithm, whether it is classification or clustering: if one dimension's absolute numbers dominate, the whole algorithm will be skewed and will not work properly.

Worked example: why scale differences corrupt distances.

Two points: $p_{1} = (1000, 1)$ and $p_{2} = (1010, 2)$ . On the raw scale, the distance is

$dist (p_{1}, p_{2}) = (1010 - 1000)^{2} + (2 - 1)^{2} = 100 + 1 \approx 10.05$

The $x$ -dimension contributes 100 of the 101 squared units — over 99% of the distance. The $y$ -dimension is practically invisible: a clustering run on this data would behave as if $y$ did not exist. Normalize each dimension (for example, subtract the mean and divide by the standard deviation of that dimension, or rescale to $[0, 1]$ ), and the two dimensions contribute comparably, so both genuinely matter to the cluster centers. Without normalization, the dimension with bigger numbers silently owns the clustering.

Sense-check: distance is blind to units; only relative scale inside the data matters, which is why normalization is a mandatory pre-processing step for any distance-based algorithm.

14.9.3 Pre-Processing: Outliers

In pre-processing you also have to eliminate the outliers. If you do not remove an outlier, you will find one point which contributes heavily to the SSE of the cluster — the example on the screen showed an outlier contributing heavily to the SSE value of cluster $C_{4}$ . K-means is vulnerable to outliers: an outlier will shift your centroid, and so shift the cluster center and the cluster itself. So you have to first identify the outliers, remove them, and then run K-means on the remaining data set.

Whether to remove outliers depends on the question:

If you want to build an anomaly detection system, the outliers are the anomalies — they are exactly what you want to find, so outliers are important and you keep them.
If you ask how many clusters are in the data set and what the majority groups look like, the outliers distort the story, so you remove them before clustering.

There is no fixed formula; it depends on the question being asked. Real-world: anomaly detection is a case where the outliers themselves are the target of the analysis.

The outlier squeeze. An outlier pulls the centroid toward itself — the centroid is the mean, and means are sensitive to extreme values. In the $C_{4}$ example above, the point $(9, 4)$ moved the centroid from where the four real members sit toward $(3.8, 2.8)$ , stretching the cluster and inflating SSE. So one distant point can rewrite the boundary of a whole cluster. Whether that is a disaster or the whole point depends on the question: anomaly detection wants the outliers found; group discovery wants them gone before the run.

14.9.4 Post-Processing Steps

After K-means runs, there are post-processing steps you may apply:

Eliminate small clusters that might represent outliers — sometimes there are clusters with only one or two points; you might treat them as outliers and remove them.
Split a loose cluster. A loose cluster is one with a higher SSE value — if the cluster has higher SSE, that means it is loose; you can break it into multiple clusters.
Merge clusters which are really close and have relatively low SSE — if two clusters are close to each other, you can merge them.

You can use all these steps in tandem with each other. A recurring theme: K-means usually needs a lot of pre-processing and post-processing together — post-processing to merge similar clusters, pre-processing to do some other type of balancing.

The pre/post pipeline in one picture.

Pre-process: normalize all dimensions; identify and remove (or keep, for anomaly detection) outliers.
Run K-means.
Post-process: drop tiny clusters that are really outliers; split loose (high-SSE) clusters; merge close clusters with low SSE — repeating until the clustering answers the question.

The professor's emphasis: these steps are used in tandem. A real analysis usually needs both halves — for example, post-processing to merge the small clusters produced by an over-large $k$ , combined with pre-processing to keep dimensions balanced.

14.9.5 Student Questions and Answers

Q: If the data points are continuously fed to the clustering algorithm, will the centroid keep changing? Can K-means work that way?

A: In K-means clustering, we have to give all the points at one go. It is not an incremental clustering algorithm — before we run K-means, we should have access to all the data points, only then K-means will work. There are other clustering algorithms where you can continuously feed the data points over ten days, fifty days, or one year, and the algorithm keeps incorporating them into one or more clusters — but K-means does not fall into that category. You have to give all the points up front for K-means to work.

Q: Why do we use the square operation in the SSE formula? Could we use a mod operation instead? The formula might give a negative value.

A: Yes, the distance might come out positive or negative, so you can handle it with a mod operation, or with a square operation, or use both. If you square the value, what is the impact? It gives you a proper exponential curve: a high value becomes even higher, so you can identify when there is low SSE and when there is higher SSE. The square forces a nonlinear relationship — the plain distance is a linear relationship, and you want a square relationship so that high errors are pushed to a higher state. Using mod alone keeps the relationship linear; combining mod with square keeps the signs fixed and the curve exponential.

Q: If we eliminate the outlier, is the purpose lost, like in classification? In classification, outliers tell a different story.

A: No, the purpose is not lost. Sometimes outliers are the story: if you want to build an anomaly detection system, the outliers are the two anomalies you are looking for — in that case outliers are important. But if you ask how many clusters there are and what the different groups look like, the outliers only distort the majority groups. It depends on the question we are asking; there is no fixed formula.

Exam note: three mechanisms to remember: (1) an empty cluster is refilled by splitting the cluster whose point contributes maximum SSE (or the cluster with highest total SSE); (2) normalization is mandatory for distance-based algorithms because a dimension with larger absolute numbers dominates the distance; (3) outlier handling depends on the question — anomaly detection keeps outliers (they are the target), group discovery removes them. K-means is not incremental: all points must be provided up front.

The next section collects the deep weaknesses behind all these workarounds — what the SSE objective structurally cannot handle.

14.10 Limitations of K-Means

14.10.1 What the Objective Function Cannot See

K-means has a few limitations. First, it cannot handle outliers — they shift the center and the cluster. Second, there is nothing in K-means which handles the size, the density, or the shape of the cluster. The reason is visible in the objective function:

$SSE = i = 1 \sum k x \in C_{i} \sum ∥ x - μ_{i} ∥^{2}$

The professor's reading of the formula: "for K equals to one, two K, sum of square mu one X" — summing over the clusters and over the points, the squared distance of each point from its cluster mean. In this formula, there is nothing which talks about the size of the cluster, nothing about density, nothing about shape. The formula silently assumes that all the natural clusters in the data set are of the same size and the same density. So when the true clusters have different sizes, densities, or non-spherical shapes, K-means can produce wrong clusters even when the value of $k$ is exactly right — and the value of $k$ being three while the data has three natural clusters is not the problem; the objective function is.

You can modify the algorithm so that the number of points in each cluster becomes almost the same, but the original formula, the original objective function, does not talk about the number of points or the size of the cluster at all.

Reading the formula like an auditor. The SSE adds three ingredients only: a point $x$ , its centroid $μ_{i}$ , and the squared distance between them. Ask what a "size" or "density" or "shape" term would look like — a count of members, a variance of distances, a covariance matrix — and search for it in the formula. There is none. The objective cannot even see that cluster $A$ has 10,000 points and cluster $B$ has 10, because it never counts them. Every consequence in this section — cutting big clusters, merging dense clusters, straight-line splits — is a symptom of that blind spot.

14.10.2 Worked Examples: Size, Density, and Shape

Size. A data set with three clusters of unequal sizes, passed with $k = 3$ : there is a chance you do not get the three natural clusters. Instead, the large natural cluster tends to be cut across by a boundary, because the SSE objective balances distances and effectively expects equal-sized clusters. The value $k = 3$ is correct — nothing is wrong with $k = 3$ — but the objective does not handle clusters of various sizes.

Worked example: three natural clusters, very unequal sizes.

Two dense little clusters of 20 points each sit at $(0, 0)$ and $(10, 0)$ , and one huge spread-out cluster of 200 points surrounds them. With $k = 3$ the "obvious" answer — the three natural groups — is not what SSE wants. The huge cluster's points are far from any single centroid, so their squared distances are large. SSE is reduced by splitting the big cluster into two halves (each half gets its own centroid and much smaller distances), even though that means one of the small clusters gets absorbed into the other. Result: K-means returns two halves of the big cluster plus one small cluster, instead of the three natural groups.

The mechanism: SSE penalizes distance, not mixing. Cutting a big cluster removes lots of large squared distances; merging a small cluster into a big one barely changes the sum. The objective is effectively trading sizes to equalize distances — the class's "expects equal-sized clusters."

Sense-check: with $k = 3$ and three natural groups, K-means can still "work" and produce three clusters — but they are the wrong three.

Density. A data set with three natural clusters of different densities, passed with $k = 3$ : the algorithm may return weird clusters, because there is nothing in the formula which measures the density of each cluster. The objective assumes all clusters have the same density.

Worked example: three natural clusters, different densities.

Cluster $A$ : 100 points packed tightly (radius 1). Cluster $B$ : 100 points spread loosely (radius 5). Cluster $C$ : 100 points, medium. A centroid inside dense cluster $A$ gets tiny distances; the same centroid would produce large distances inside loose cluster $B$ . To shrink SSE, K-means is tempted to carve the loose cluster $B$ into several pieces and hand parts of it to $A$ and $C$ — the centroid of $A$ , placed at the rim of the dense cloud, can capture nearby loose points with smaller total error than they contribute to their own loose centroid. The result: "weird clusters" mixing dense and loose regions.

The mechanism: density never appears in the formula, so the algorithm cannot know that a sparse region is its own legitimate group.

Sense-check: different densities are invisible to SSE, so the returned clusters follow distance geometry, not true group structure.

Shape. A data set with two non-spherical clusters (red and blue in the example): if you get a centroid in the middle, K-means will split the data along a straight-line boundary — this becomes one cluster, that becomes another — cutting right through the natural elongated clusters. Again, nothing in the formula talks about shape.

Worked example: two crescent-shaped clusters.

Two natural clusters shaped like crescent moons, interlocked. Any single centroid inside a crescent is close to only part of it; the other arm of the crescent is far away and drags the squared distances up. K-means's only tool is a centroid, and the boundary between two centroids is always a straight line (each point joins the nearer center). Cutting a crescent with a straight line splits its arms — parts of the red crescent and parts of the blue crescent end up on the same side of the line. The result is two clusters that each contain a mix of both natural groups.

The mechanism: a straight-line decision boundary cannot follow a curved shape; center-based clusters are spherical by construction (Section 14.1.5).

Sense-check: the failure is geometric — the objective penalizes distance, and distance geometry only produces round clusters.

14.10.3 Workaround: Higher K plus Merging

Even with these limitations, you can still use K-means: pass a higher value of $K$ and then do post-processing.

For the size example: instead of passing $k = 2$ or $k = 3$ , pass $k = 10$ — you get much smaller clusters of the same size, and then you do post-processing and merge them into one big cluster.
The same recipe works for density and for non-granular shapes: pass $k = 10$ instead of $k = 2$ , get smaller clusters, and based on post-processing merge similar clusters together to form one big cluster, another big cluster, and so on.

How do we determine which clusters are similar, so that we know what to merge? The class explicitly deferred this — "that is an absolutely correct question; hold this thought, I am going to talk about how you find similarity between two clusters" — and it is answered in the hierarchical-clustering discussion and in the cluster-similarity measures that follow.

Scope of the workaround. Passing a larger $k$ works only because small clusters are pure: when K-means over-splits a natural group, each small piece still contains only points from that one group (this is the reference book's observation about over-segmentation). The recipe then succeeds in three stages: (1) over-split with a large $k$ ; (2) merge small clusters that are close and have low SSE; (3) keep merging until the groups you want emerge. The catch: merging requires a definition of "similar clusters," which is exactly the question the class deferred to the hierarchical-clustering section.

14.10.4 Student Questions and Answers

Q: How do we determine the similar clusters that should be merged in post-processing?

A: That is an absolutely correct question — hold that thought. We will discuss how to define similarity between two clusters in a moment (it comes up with hierarchical clustering and with the cluster-similarity measures). What we can say now is the plan: pass a higher value of K, get small clusters, and in post-processing merge clusters which are really close and have relatively low SSE — the similarity between clusters decides what gets merged.

Exam note: K-means's objective SSE contains nothing about cluster size, density, or shape — it silently assumes equal-sized, equal-density, globular clusters. Consequences: large clusters get cut, dense/sparse mixtures return weird clusters, and crescent/elongated shapes get straight-line splits. The standard workaround is to over-split (higher $k$ , e.g., $k = 10$ ) and merge similar clusters in post-processing — with cluster similarity defined later via hierarchical clustering and performance measures.

The class's deferred question — how to measure similarity between clusters — is answered next: first through performance measures for judging cluster quality, then through hierarchical clustering, which is built entirely on cluster similarity.

14.11 Cluster Quality and Performance Measures

14.11.1 No Single Performance Measure

How do we determine the quality of the clusters? In classification, accuracy is a performance measure that works almost everywhere — F1 and AUC are also more or less acceptable. But in clustering, there is no one performance measure: there are many, and based on your requirement you can choose one or many. There is no single formula for cluster quality.

The measures named in the class (the audio is noisy, so several names were transcribed roughly and have now been confirmed against the standard literature and the course's reference books):

Rand index (transcribed as "land index") — a label-based measure: counts pairs of points that are grouped consistently (same cluster in both clusterings, or different clusters in both) against all pairs.
Mutual information score — how much knowing one clustering tells you about the other, borrowed from information theory.
Homogeneity score — each cluster contains only points of a single ground-truth class.
Completeness score — all points of each ground-truth class are in the same cluster.
Silhouette coefficient (transcribed as "shirioid score" / "schilloid coefficient") — for each point, compares its average distance to its own cluster with its average distance to the nearest other cluster; ranges from -1 to +1, higher is better.
Calinski–Harabasz score (transcribed as "Kaleski score" and garbled as "aimed cliff category") — the ratio of between-cluster dispersion to within-cluster dispersion, also called the variance ratio criterion; higher is better.
Davies index (Davies–Bouldin index) — the average ratio of within-cluster scatter to between-cluster separation, computed over all clusters; lower is better.
Contingency matrix — a table crossing cluster labels with ground-truth labels, the raw material from which many of the other measures are computed.

Why no single measure. Each measure encodes a different idea of "good": the Rand index rewards agreement with a reference labeling; homogeneity and completeness separately check for pure clusters and complete clusters; the silhouette checks geometric compactness and separation without any reference; Calinski–Harabasz rewards large between-cluster variance; Davies–Bouldin rewards separation relative to scatter. No single number can serve all these jobs, because they answer different questions about the same clustering — exactly the subjectivity of Section 14.1, now at the evaluation level.

Real-world: these are implemented in scikit-learn; you can look at the scikit-learn documentation section on cluster performance evaluation (the class cites the section 2.3.10, "Cluster performance evaluation") to determine the quality of a clustering. The link was shared in the course chat. Read about these measures — they are pretty easy to understand, and this reading was explicitly assigned as homework. The hint given in the class: it is very interesting, and you will be able to connect a lot of things once you understand them.

Exam note: this reading was explicitly assigned as homework. Read the clustering performance measures in scikit-learn's cluster performance evaluation documentation (section 2.3.10): Rand index, mutual information score, homogeneity, completeness, silhouette coefficient, Calinski–Harabasz score, Davies index, and contingency matrix. They are easy to understand, and connecting them is the point.

14.11.2 Match the Measure to the Algorithm

The most important idea in this section: your performance measure should match the algorithm family. K-means is a center-based clustering algorithm — you find the center of the cluster, the points around the center are part of the cluster, and points far from the center belong to other clusters. So your performance measure should also be center-based. You cannot use a density-based performance measure to evaluate a K-means clustering. Conversely, for a density-based algorithm you cannot use a center-based evaluation criterion. Some performance measures are center-based, some are density-based, some are label-based, some are homogeneity-based — you must pick the one whose assumptions match the clustering method you ran.

Pitfall: mismatched evaluation. Evaluating a center-based clustering (K-means) with a density-based measure asks a question the algorithm never tried to answer — the score will be meaningless, and worse, it may look like a fair verdict. The same applies in reverse: a density-based clustering (like DBSCAN, coming later in the course) must be judged with a density-compatible measure. The rule of thumb: the measure's assumptions must match the algorithm family — center-based measures for center-based algorithms, density-based for density-based, and label-based measures wherever ground truth exists.

14.11.3 Student Questions and Answers

Q: How do we determine the quality of the clusters?

A: There are many ways and no single formula. In classification, accuracy, F1, and AUC work almost everywhere, but clustering has no one accepted measure. There are performance measures like the Rand index, mutual information score, homogeneity score, completeness score, silhouette coefficient, Calinski–Harabasz score, Davies index, and the contingency matrix — read about them; they are easy to understand, and this is assigned as homework. And match the measure to the algorithm: a center-based algorithm like K-means needs a center-based measure, not a density-based one.

Exam note: clustering has no universal performance measure — unlike classification's accuracy/F1/AUC. The named measures are the Rand index, mutual information, homogeneity, completeness, silhouette coefficient, Calinski–Harabasz score, Davies–Bouldin index, and contingency matrix; the key rule is that the measure must match the algorithm family (center-based for K-means, never density-based).

The deferred question from Section 14.10 — how to measure similarity between clusters — now gets its proper answer, because hierarchical clustering is built entirely on merging similar clusters.

14.12 Hierarchical Clustering

14.12.1 Why Build a Hierarchy Instead of Partitioning

Finding the value of $K$ is always hard. And clustering is an ill-posed problem — if you ask how many clusters are in a data set, some people will say one, some four, some many more; it depends on the question you ask. So instead of partitioning the data set once, can we create a hierarchy and, based on the question, cut the hierarchy at a level — go to the level that answers the question? That is the idea of hierarchical clustering.

This is also the answer to a question raised earlier: instead of guessing $K$ , build the hierarchy, and the value of $K$ becomes whatever number of clusters you find at the level you cut. The class stressed that hierarchical clustering is very natural — animal kingdom, plant kingdom, and much of how we structure data in real life are hierarchies — which is why hierarchical clustering is extremely important.

The hook. Every flat algorithm forces you to commit to one $k$ before you see any result — the ill-posed commitment from Section 14.8. Hierarchical clustering refuses the commitment: it builds all resolutions at once and lets the question pick the level. If the same hierarchy serves three different questions with three different answers ( $k = 1$ , $k = 3$ , $k = 32$ ), the hierarchy has done its job — you only pay for what you ask.

14.12.2 Coarser to Finer: Cutting the Tree

The hierarchy ranges from a coarser effect to a finer effect. Coarser means $k = 1$ : if you have to cluster all the points into only one cluster, you get one big cluster, and the similarity between all the points inside is low, but there is only one cluster. Moving finer, you divide this cluster into smaller clusters: with four clusters in the data set you get four finer clusters; push further and you get 32 small clusters. You can do this either top-down or bottom-up.

The advantage: based on the question, you can cut the tree at any level and get the proper answer. For the same hierarchy, one question gives $k = 3$ , another gives $k = 1$ , another gives 32 — you do not have to estimate the value of $K$ ; you cut at the desired level and read off the clusters there. You do not have to look at other levels.

The cutting operation. A hierarchy is a nested family of clusterings. Any horizontal cut through the tree gives one complete partition of the data: the root of the tree is the coarsest cut ( $k = 1$ , everything together), the leaves are the finest cut ( $k = n$ , every point alone), and every intermediate level is a valid clustering with its own $k$ . The user does not choose $k$ in advance; they choose a level, and the tree supplies the $k$ at that level. This is precisely why the problem of Section 14.8 evaporates: instead of estimating the number of clusters, you inspect levels.

14.12.3 Agglomerative versus Divisive (with the Correction)

There are two versions of hierarchical clustering: agglomerative and divisive. The class initially misspoke and then corrected itself — and the correction is worth recording, because this is exactly where people get confused.

Agglomerative (bottom-up): initially, all the points are considered as individual clusters — each single point is a cluster. Then, based on the similarity measure, you start merging the closest or most similar clusters, until you find one big cluster.
Divisive (top-down): you start with one big cluster which has all the data points, and based on the similarity measure you start splitting that one big cluster into smaller and smaller clusters.

So the mnemonics: one big cluster divided into smaller parts is the divisive method; smaller clusters combined into bigger clusters is the agglomerative method. The top-down approach assumes one big cluster and breaks it on the basis of a notion of similarity into smaller clusters, tree-like, again and again — that is divisive. The bottom-up approach starts with each point as its own cluster and merges — that is agglomerative.

Q: Which method is which? Is one big cluster divided into smaller parts agglomerative?

A: No — one big cluster divided into smaller parts is the divisive method. Merging small clusters into bigger ones is the agglomerative method. The instructor said it wrong initially, then corrected it: top down (one big cluster, split into smaller and smaller clusters) is divisive; bottom up (each point as its own cluster, merge closest clusters repeatedly) is agglomerative. That is how it works.

Pitfall: the direction confusion. This is the exact spot where the class itself stumbled and corrected: "one big cluster → smaller parts" is divisive (top-down), and "small clusters → one big cluster" is agglomerative (bottom-up). The mnemonic that sticks: agglomerate = glue things together (bottom-up); divide = break things apart (top-down).

14.12.4 Worked Example: Cities, States, Country, Continent

The class built an agglomerative (bottom-up) hierarchy with cities:

At the bottom level, every data point is a cluster: Jaipur, Jodhpur, Lucknow, Kanpur, Bhopal, Indore — at this level we are talking about cities.
Based on similarity, merge the clusters: Jaipur and Jodhpur merge into a Rajasthan cluster; Lucknow and Kanpur merge into a UP cluster; Bhopal and Indore merge into an MP cluster. At this level we are talking about states.
Merge the three state clusters: Rajasthan, UP, and MP merge into India. At this level we are talking about a country.
Further levels: India merges into Asia (continent level), Asia into Earth, and so on.

Now, based on the question, cut the tree at any level. If you ask "how many states are in the data set?", you cut at the state level and get three clusters — you do not have to look at the city level or the country level. If you ask how many countries, you look at the country level and get $k = 1$ . This is exactly how the animal kingdom or the plant kingdom works — homo sapiens has a hierarchy there; based on the question, you cut at any level and get the proper answer.

Worked example: the six-city tree, level by level.

Start: 6 leaves — Jaipur, Jodhpur, Lucknow, Kanpur, Bhopal, Indore (each its own cluster, $k = 6$ , city level).

Merge by similarity (geography): Jaipur + Jodhpur → Rajasthan; Lucknow + Kanpur → UP; Bhopal + Indore → MP. Now 3 clusters, $k = 3$ , state level.

Merge again: Rajasthan + UP + MP → India. Now 1 cluster at the country level, $k = 1$ .

Continue: India + other countries → Asia (continent level) → Earth (world level).

Now ask questions against the same tree:

"How many states?" → cut at the state level → 3 clusters (Rajasthan, UP, MP).
"How many countries represented?" → cut at the country level → 1 cluster (India).
"How many cities?" → cut at the leaf level → 6 clusters.

One hierarchy, three questions, three answers — and no value of $K$ was ever estimated.

Sense-check: the tree's levels correspond exactly to real-world levels of granularity, which is why the class calls hierarchical clustering "very natural": taxonomy (kingdom, phylum, genus, species) works the same way.

14.12.5 AGNES and DIANA

The algorithm name for agglomerative clustering is AGNES; the algorithm name for divisive clustering is DIANA. In AGNES you initially consider all the points as clusters, start merging clusters based on similarity measures, and in the end get one big cluster — you move from left to right in the diagram. In DIANA (divisive) you move from right to left: one big cluster is divided into smaller and smaller parts.

There was a second correction in the class about the direction: "divisive means bottom up, not top down" was initially said, and then corrected — no: divisive means one big cluster divides, so it is top-down. The corrected version stands: divisive is top down; agglomerative is bottom up.

Q: Does divisive clustering go bottom-up?

A: No — divisive means one big cluster divides into smaller and smaller parts, so it is top-down, not bottom-up. You were correct: divisive is top down. Agglomerative is the bottom-up one: each point starts as its own cluster and clusters merge until one big cluster remains. AGNES is the agglomerative algorithm, DIANA is the divisive algorithm.

Two algorithms, one tree. AGNES (AGglomerative NESting) and DIANA (DIvisive ANAlysis) build the same kind of nested structure from opposite ends: AGNES starts at the leaves and merges (bottom-up, left-to-right in the class diagram); DIANA starts at the root and splits (top-down, right-to-left). Both produce a hierarchy of nested clusters, so both answer the same "cut at any level" question — they just build the tree in different directions.

14.12.6 Why Hierarchical Clustering Is Natural

Hierarchical clustering is very natural to what we do in real life: the animal kingdom, the plant kingdom, taxonomy — how we structure data. And K-means can actually be used to help build hierarchical clustering — which brings us to bisecting K-means.

Exam note: hierarchical clustering builds nested clusters so you can cut the tree at any level and read off $k$ — no estimation needed. The direction vocabulary is the classic trap, and the class corrected it explicitly: divisive (DIANA) = one big cluster split into smaller parts = top-down; agglomerative (AGNES) = small clusters merged into bigger ones = bottom-up.

The bridge between K-means and hierarchies — running K-means with $k = 2$ recursively — is the next section's algorithm.

14.13 Bisecting K-Means

14.13.1 The Algorithm

Can we use K-means in hierarchical clustering? Yes — the algorithm is called bisecting K-means. Initially you have one big cluster; you run K-means with $k = 2$ (or some $k$ value you feel feasible — the class used $k = 2$ but you can pass any value) and divide the data set into parts. Then you get smaller clusters, and you run K-means on the smaller clusters iteratively: for the blue cluster, pass $k = 2$ to further divide it; for the red cluster, pass $k = 2$ again; repeat until you find the clusters you want. This builds a tree where every split is a K-means run — a hierarchical version of K-means built by repeated splitting.

Purpose and position. Bisecting K-means is the answer to the bridge question from Section 14.12.6: yes, K-means can build a hierarchical clustering — by using itself as the splitting subroutine. Each node of the tree is produced by running K-means with $k = 2$ on the current cluster, so the tree is divisive in spirit (top-down splitting) even though it is built out of a flat algorithm. The reference book frames the same algorithm as: to produce $K$ clusters, split all points into two, keep splitting selected clusters until $K$ clusters exist.

14.13.2 Worked Example

Start with one big data set. Pass $k = 2$ , get two clusters. For the blue cluster, pass $k = 2$ again: it splits into a dark-green cluster and a blue cluster. For the red cluster, pass $k = 2$ : it splits further. Continue iteratively — you can take any $k$ value you feel feasible, there is no restriction — until you end up with the final set of small clusters. The result is a tree of clusters, exactly like a hierarchy built by splitting.

Worked example: building the split tree on paper.

Start with all 8 points as one cluster, $S_{0}$ . Run K-means with $k = 2$ :

Split 1: $S_{0}$ divides into $B_{1}$ (blue, 4 points) and $R_{1}$ (red, 4 points). Level 1 of the tree.

Run K-means with $k = 2$ on each child:

Split 2a: $B_{1}$ divides into a dark-green cluster $G_{1}$ (2 points) and a lighter blue $B_{2}$ (2 points).
Split 2b: $R_{1}$ divides into two red sub-clusters $R_{2}$ (2 points) and $R_{3}$ (2 points). Level 2 of the tree.

Stop here — the four clusters $G_{1}, B_{2}, R_{2}, R_{3}$ are the desired grouping.

        S0 (8 points)
        /            \
      B1 (blue)      R1 (red)
     /       \        /       \
   G1(2)   B2(2)   R2(2)   R3(2)

Every internal node is the output of a $k = 2$ K-means run; the leaves are the final answer. The hierarchy is complete: four clusters produced by repeated splitting.

Sense-check: this is hierarchical clustering in the divisive direction (Section 14.12.5) — except that DIANA splits by similarity analysis while bisecting K-means splits by running K-means.

14.13.3 The Greedy Problem

There is one issue with hierarchical (bisecting) K-means: the division might not be correct, because we use a greedy strategy. Example from the class: one big cluster is split with $k = 2$ into two parts; each part is split again. But look carefully — two blue points that actually belong to one natural cluster end up in different branches of the tree, because at each split K-means only sees the local structure of the current cluster. The greedy strategy cannot find the global optimum: local optima say "this green cluster should break into these two", even though the surrounding points belong together. The result: another post-processing step is needed in bisecting K-means — you have to look into the surrounding and merge similar-looking clusters as well. The top-down approach is: take big cluster, break, break, break — but sometimes you also have to merge similar clusters so that you get proper natural clusters toward the end. Why does this happen? Bisecting K-means is greedy and it is trying to optimize SSE: it breaks clusters into two parts without looking at the surroundings, without checking whether two similar-looking clusters could be merged. So post-processing to merge similar clusters is part of making bisecting K-means work well.

Why greedy splitting goes wrong. A greedy decision is one made with only local information. When K-means splits the blue cluster, it knows only the blue cluster's points — it cannot see that the dark-green piece it creates actually belongs with points outside. Example: one natural cluster of points strung along a diagonal. The first $k = 2$ split cuts it into two pieces (fine so far). The second split cuts one piece again — and that third piece is now separated from its natural partners across the first split's boundary. Two points that belong to one natural cluster end up in different branches of the tree. The professor's lesson: bisecting K-means finds local optima at every node, never the global optimum, so merging similar-looking clusters in post-processing is part of the recipe — the same merge step as Section 14.10.3.

14.13.4 Complexity of Bisecting K-Means

The complexity of one K-means run is the same as before: $I \times K \times N \times D$ . But bisecting K-means runs K-means many times — once per split. How many times? That depends on the height of the tree. If the tree is balanced and binary, the height of the tree is $lo g_{2}$ of something (the number of leaves), and the total cost is the per-run complexity times the tree height:

$O (lo g_{2} N \cdot I \cdot K \cdot N \cdot D)$

Reconciling the log factor. The lecture states the total complexity as the per-run cost times the height of a balanced binary tree, $lo g_{2}$ of the number of leaves. The professor's slide reads the factor as $lo g_{2}$ of the data size — written above as $lo g_{2} N$ , which is the tree height when splitting continues down to the individual points. If the tree stops at $K$ final clusters instead, the same argument gives $lo g_{2} K$ — the number of leaves is $K$ , not $N$ . Both forms appear in the literature; the mechanics are identical, and the exam form is the lecture's $lo g_{2} N$ version above. Note also that the reference book (Tan et al.) highlights a practical subtlety: because each split is a $k = 2$ run and each node processes only its own subset of points, bisecting K-means can run faster than a direct K-means run at the same $K$ — the log factor comes from the number of splits, not from per-split cost.

So when we said earlier that K-means is one of the most efficient clustering algorithms in terms of complexity, note that bisecting K-means has a higher complexity, because it runs K-means again and again to find natural clusters.

Exam note: bisecting K-means builds a divisive tree where every split is a K-means run with $k = 2$ . Total complexity is the per-run cost $I \times K \times N \times D$ times the balanced-tree height, giving $O (lo g_{2} N \cdot I \cdot K \cdot N \cdot D)$ — higher than plain K-means because K-means runs repeatedly. The method is greedy: it splits with local information only, so it finds local optima and needs post-processing to merge similar clusters.

The session's last stop returns to the very first estimation problem: the elbow method, the most famous practical hint for choosing $K$ .

14.14 The Elbow Method

14.14.1 How the Elbow Plot Works

The elbow method is one way to find or estimate the value of $K$ . It is not foolproof: with this method you cannot always say that the number of natural clusters in your data set is exactly this — it is a suggestive method which can help you in estimating the value of $K$ . The professor repeated this caution several times.

How it is done. On the X axis of the graph we put the number of clusters; on the Y axis we put the value of SSE. Run K-means with $k = 1$ : the SSE value is extremely high. Repeat the exercise with $k = 2, 3, 4, 5, 6$ , and so on — each run gives some SSE value. If you pass $k = n$ (one cluster per point), the SSE value becomes zero — each point is its own cluster, so all distances are zero — and the curve meets the X axis.

Why SSE falls with $k$ . Each new cluster gives the points a closer centroid to grab, so the squared distances shrink: $k = 1$ gives the maximum SSE (Section 14.7), $k = n$ gives zero. The interesting information is not that SSE falls — it always does — but how fast. When you split a genuinely separate natural group, the error drops a lot (its points were far from the old centroid). When you keep splitting a group that was already cohesive, each extra cluster buys very little error reduction. The change of pace in this curve is the signal.

14.14.2 Reading the Elbow

The elbow method says: when you start with $k = 1$ , there is a sudden drop in the SSE value — a sharp drop — and then the curve stabilizes. Just like an elbow. Where the sudden drop ends and the stabilization begins, there is a point — the knee of the curve — and that knee is the candidate optimal number of clusters. In the class example, the elbow appears around $k = 3$ , so the estimate is that the data set has three natural clusters. In practice: run K-means for $k = 1, 2, 3, 4, \dots$ , plot SSE against the number of clusters, find the elbow, and say the number of natural clusters is maybe three, four, five, whatever the elbow shows.

Worked example: reading a table of SSE values.

Suppose K-means runs give these SSE values for $k = 1, \dots, 7$ :

$k$	1	2	3	4	5	6	7
SSE	520	210	95	80	71	66	62

The drops are: $520 \to 210$ (310), $210 \to 95$ (115), $95 \to 80$ (15), then 9, 5, 4. The first two drops are large — each added cluster was splitting a real group. From $k = 3$ onward the drops are tiny: the extra clusters are cutting cohesive groups and buying almost nothing. The elbow sits at $k = 3$ — the estimate is three natural clusters.

Sense-check: the big-drop/big-drop/small-drop pattern is the geometric "sharp drop then stabilization" the professor described; the knee at the boundary between large and small drops is the candidate $K$ .

Visual intuition. Picture the plot: the $X$ axis is the number of clusters $k$ (running from 1 to $n$ ); the $Y$ axis is SSE (running from its maximum at $k = 1$ down to 0 at $k = n$ ). The curve starts high on the left, plunges steeply for the first few $k$ , then bends sharply and flattens into a long, shallow glide toward the $X$ axis, which it touches only at the far right end ( $k = n$ ). The bend — like the bend of a bent arm — is the elbow. The one-sentence takeaway: the steep part is the signal (real groups being found), the flat part is the noise (arbitrary over-splitting), and the bend marks where the signal ends.

14.14.3 Not Foolproof

Again: this is not foolproof. The elbow method is only a suggestive method for estimating $K$ — it can help you estimate or predict the value of $K$ , but you cannot always conclude that the number of natural clusters in the data set is exactly the elbow point. This caution was repeated in the class.

Where the elbow lies. Real data often has no clean knee: the curve can fall smoothly with no visible bend (leaving no elbow to read), or the bend can sit at a misleading position. That is why the professor calls it suggestive, not a proof — it is a hint in the toolbox from Section 14.8, to be combined with hierarchical clustering and performance measures, not a substitute for judgment.

Exam note: the elbow method plots SSE (Y axis) against the number of clusters (X axis); the sharp drop followed by stabilization marks an elbow, and the knee of the curve is the candidate optimal $K$ . SSE = 0 at $k = n$ . The method is a suggestive estimator, not foolproof — expect this caution to matter.

Exam Guidance Summary

Exam note: everything discussed in the course until the last class is part of the comprehensive exam — including the mechanics of K-means (four steps, SSE objective, complexity $I \times K \times N \times D$ ), the centroid-versus-medoid distinction, empty-cluster handling, pre- and post-processing steps, the limitations (outliers, size, density, shape), hierarchical clustering (agglomerative/divisive, AGNES/DIANA), bisecting K-means, and the elbow method.

Study advice: the clustering performance measures — Rand index, mutual information score, homogeneity score, completeness score, silhouette coefficient, Calinski–Harabasz score, Davies index, contingency matrix — were assigned as reading/homework. Read about them in scikit-learn's cluster performance evaluation documentation (section 2.3.10); they are easy to understand.
Exam note: be ready for conceptual questions that separate K-means behavior from cluster quality — a bad value of $K$ still returns clusters, and quality is the user's job, not the algorithm's.
Exam note: the elbow method is a suggestive estimator of $K$ , not a proof — expect the "not foolproof" framing to matter.
Exam note: expect the agglomerative-versus-divisive direction question — top-down splitting is divisive (DIANA), bottom-up merging is agglomerative (AGNES); the class explicitly corrected a misstatement on exactly this point.
Exam note: the complexity derivation pattern matters — be able to derive $O (I \cdot K \cdot N \cdot D)$ step by step (constant initialization, $N \times K \times D$ assignment, linear recomputation, $I$ iterations), and the bisecting-K-means version with the tree-height log factor.

Key Industry Applications

Real-world: Google News — news articles are bucketed by similarity so readers can get information about a particular news in a broader fashion; the bucketing is a live clustering service over an incoming stream of articles.
Real-world: market segmentation — clustering customers into groups is a classic industry application; each segment is then targeted (or studied) as a unit.
Real-world: anomaly detection — when the question is about anomalies, outliers are the target (the two anomalies in the example); this is the case where you must NOT remove outliers before clustering. Fraud detection and network intrusion detection run on this principle.
Real-world: hierarchical structures in everyday life — animal kingdom, plant kingdom, taxonomy (homo sapiens), and the city → state → country → continent → Earth hierarchy show why hierarchical clustering is natural; biological taxonomy is a working hierarchical clustering of species.
Real-world: scikit-learn implements cluster performance evaluation (documentation section 2.3.10) — the practical place to compute homogeneity, completeness, silhouette, Calinski–Harabasz, Davies, Rand index, mutual information, and contingency-matrix scores.

DM Lecture 14 notes · K-Means and Hierarchical Clustering

Data Mining· postgraduate· 2026-08-05

Sections Breakdown

114.1 Recap: What Clustering Is

Natural groups, intra- versus inter-cluster similarity, subjectivity and ill-posedness, types of clustering and clusters, and what makes a good cluster.

214.2 The K-Means Algorithm

Inputs and outputs, the four steps (initialize, assign, recompute, iterate), and a fully worked two-cluster example with six points.

314.3 Initializing the Centroids

Random initialization and nondeterminism, the K-means++ seeding procedure, and the practical fixes for reproducibility.

414.4 Stopping Criteria

User-defined convergence: few points changing cluster, centroids not moving, or a minimal SSE decrease.

514.5 Recomputing the Centroid: Centroid versus Medoid

The centroid formula, the imaginary-point property, the centroid-medoid distinction, and worked examples of both.

614.6 Time Complexity of K-Means

Step-by-step derivation of O(I x K x N x D) with a concrete counting example over real numbers.

714.7 SSE: The Objective Function of K-Means

The SSE formula, why squaring beats absolute value, and the boundary cases: SSE = 0 at k = n and maximum at k = 1.

814.8 Finding the Value of K

An ill-posed problem with no formula; the estimator toolbox, and why a bad K still returns clusters.

914.9 Empty Clusters and Pre-/Post-Processing

Refilling empty clusters by splitting at the max-SSE point, mandatory normalization, question-dependent outlier handling, and post-processing.

1014.10 Limitations of K-Means

Why the SSE objective ignores size, density, and shape, with worked failures and the higher-K-plus-merge workaround.

1114.11 Cluster Quality and Performance Measures

The named measures (Rand index, silhouette, Calinski-Harabasz, Davies-Bouldin, and more) and matching the measure to the algorithm family.

1214.12 Hierarchical Clustering

Cutting the tree instead of choosing K; agglomerative versus divisive (AGNES and DIANA) with the class corrections, and the six-city worked example.

1314.13 Bisecting K-Means

K-means as a k=2 splitting subroutine, the complexity O(log2 N x I x K x N x D), and the greedy local-optima problem.

1414.14 The Elbow Method

Plotting SSE against the number of clusters, reading the knee of the curve, and why the method is suggestive, not foolproof.

15Exam Guidance Summary

Comprehensive-exam coverage of the session: K-means mechanics, SSE, complexity derivation, directions trap, and the estimator caveats.

16Key Industry Applications

Google News bucketing, market segmentation, anomaly detection, taxonomy-like hierarchies, and scikit-learn performance evaluation.

Postgraduate students in Data Mining

Exam Revision Notes

Below is the distilled, exam-ready core. Every entry comes from the full explanation above. Use this section for rapid review; return to the main notes when a point needs more context.

What Clustering Is

Must-know: Clustering maximizes intra-cluster similarity and minimizes inter-cluster similarity; it is subjective and ill-posed. K-means is flat, hard, distance-based, sequential, and produces center-based clusters.

⚠️ Top pitfall: Thinking similarity is a single objective measurement; similarity is always relative to the question asked, which is why different people legitimately count different numbers of clusters.

Self-check: Why can the same two data points be both similar and dissimilar? (Similarity is always with respect to a question: same eyes, same hair, different noses.)

Connects to: 14.2, 14.10

The K-Means Algorithm

Must-know: K-means is a flat, hard, distance-based, sequential algorithm with four steps: random centroid initialization, assignment of each point to the nearest centroid, centroid recomputation as the mean of cluster points, and iteration until convergence.

$c_{j} = \frac{1}{n _{j}} x \in C_{j} \sum x$

⚠️ Top pitfall: Trusting the first run: the initial centroids influence the final clusters, and K-means always returns k clusters even for a bad k — convergence says nothing about quality.

Self-check: In the worked example with A(1,1), B(1,2), C(2,2), D(7,7), E(8,7), F(8,8) and k=2, which points end up in the same cluster? (A, B, C in one; D, E, F in the other.)

Connects to: 14.3, 14.4, 14.5

Initializing the Centroids

Must-know: Random initialization makes K-means nondeterministic; the goal is determinism, not efficiency. Fixes: multiple runs with least SSE, K-means++, initializing from another algorithm, fixed seed, post-processing. K-means++ seeds centroids far apart by sampling with probability proportional to squared distance from the nearest chosen centroid.

⚠️ Top pitfall: Expecting one random run to be the answer: K-means converges to a local optimum, and the initial centroids decide which one. Also confusing efficiency with determinism as the goal of initialization.

Self-check: Why can the same data set with the same k produce different clusters? (Different initial centroid positions lead to different local optima of SSE.)

Connects to: 14.2, 14.7

Stopping Criteria

Must-know: Convergence is user-defined: stop when few points change cluster, when centroids stop moving, or when the SSE decrease falls below a threshold; criteria may be combined. K-means converges quickly in practice.

⚠️ Top pitfall: Assuming K-means stops because it found the correct clustering; the stopping criteria only measure stability, not quality.

Self-check: Name two stopping criteria for K-means. (Few points change cluster; centroids stop moving; minimal SSE decrease.)

Connects to: 14.5, 14.7

Recomputing the Centroid: Centroid versus Medoid

Must-know: Centroid formula $c_{j} = \frac{1}{n _{j}} \sum_{x \in C_{j}} x$ , computed coordinate-wise; the centroid is usually an imaginary point. The medoid is the real data point closest to the centroid. K-means is centroid-based.

$c_{j} = \frac{1}{n _{j}} x \in C_{j} \sum x$

⚠️ Top pitfall: Treating the centroid as a member of the cluster or assuming it must be a real data point; the centroid is a computed (usually imaginary) position.

Self-check: Given cluster points (1,2),(2,4),(3,1),(4,3),(5,5), what is the centroid? ((3,3); medoid is (4,3).)

Connects to: 14.2, 14.7

Time Complexity of K-Means

Must-know: K-means complexity is $O (I \cdot K \cdot N \cdot D)$ : initialization $O (1)$ , assignment $N \times K \times D$ , recomputation cheap (order $N$ ), repeated $I$ times. K-means is one of the most efficient clustering algorithms.

$O (I \cdot K \cdot N \cdot D)$

⚠️ Top pitfall: Forgetting the D factor: a distance between two points requires D per-dimension comparisons, so the assignment step multiplies by D.

Self-check: Why does the assignment step cost N x K x D? (Every point computes its distance to every centroid, and each distance costs D dimension-by-dimension comparisons.)

Connects to: 14.2, 14.13

SSE: The Objective Function of K-Means

Must-know: SSE sums the squared Euclidean distance of each point from its cluster centroid over all k clusters. SSE = 0 when k = n (each point its own centroid); SSE is maximum at k = 1 (not one).

$SSE = i = 1 \sum k x \in C_{i} \sum ∥ x - μ_{i} ∥^{2}$

⚠️ Top pitfall: Answering "one" for the k=1 SSE question: at k=1 the SSE is maximum, since every point is measured against one global centroid.

Self-check: With four points and k=4, why is SSE zero? (Each point is its own centroid, so every distance is zero.)

Connects to: 14.5, 14.8, 14.10

Finding the Value of K

Must-know: Choosing K is ill-posed with no formula; estimators include the elbow method, hierarchical clustering, and performance measures. A bad K still yields clusters (K-means never errors), so the user must judge quality — never use K-means as a black box.

⚠️ Top pitfall: Running K-means at a random K and handing the output back: the algorithm always returns clusters and never complains, so quality judgment is the user's job.

Self-check: What happens if you pass k=1 to K-means on data with two natural clusters? (It returns one cluster — no error — with maximum SSE.)

Connects to: 14.7, 14.12, 14.14

Empty Clusters and Pre-/Post-Processing

Must-know: Empty cluster fix: split the cluster whose max-SSE point (or highest total SSE) is used to populate it. Normalize all dimensions before running (distance-based). Outliers: keep for anomaly detection, remove for group discovery. K-means is not incremental — all points must be given up front.

⚠️ Top pitfall: Assuming outliers should always be removed: for anomaly detection the outliers are the target, so they must be kept.

Self-check: Why must data be normalized before K-means? (A dimension with larger absolute numbers dominates the distance computation, skewing the clustering.)

Connects to: 14.10, 14.7

Limitations of K-Means

Must-know: SSE has no size, density, or shape term, so K-means assumes equal-sized, equal-density clusters and fails on unequal sizes, mixed densities, and non-spherical shapes. Workaround: over-split with higher K and merge similar clusters in post-processing.

$SSE = i = 1 \sum k x \in C_{i} \sum ∥ x - μ_{i} ∥^{2}$

⚠️ Top pitfall: Blaming the choice of k when K-means fails: with k exactly right, the objective function still fails when clusters differ in size, density, or shape.

Self-check: Why does K-means cut a large natural cluster even when k is correct? (SSE penalizes distance, not mixing: splitting the big cluster removes many large squared distances.)

Connects to: 14.7, 14.12, 14.11

Cluster Quality and Performance Measures

Must-know: No single clustering performance measure exists. Named measures: Rand index, mutual information, homogeneity, completeness, silhouette coefficient, Calinski-Harabasz, Davies index, contingency matrix (homework reading, scikit-learn 2.3.10). The measure must match the algorithm family — center-based for K-means.

⚠️ Top pitfall: Using a density-based performance measure to evaluate a center-based algorithm like K-means (and vice versa): the measure must match the algorithm family.

Self-check: Why can't accuracy be used to evaluate clustering the way it evaluates classification? (Clustering has no universal measure; accuracy/F1/AUC work almost everywhere only in classification.)

Connects to: 14.10, 14.12

Hierarchical Clustering

Must-know: Hierarchical clustering builds nested clusters; cut the tree at any level to get k without estimation. Divisive (DIANA) = one big cluster split top-down; agglomerative (AGNES) = merge small clusters bottom-up. The direction correction is examinable.

⚠️ Top pitfall: Reversing the directions: divisive splits one big cluster into smaller parts (top-down); agglomerative merges small clusters into bigger ones (bottom-up) — the class corrected exactly this confusion.

Self-check: In the six-city example, cutting the tree at the state level gives how many clusters? (Three: Rajasthan, UP, MP.)

Connects to: 14.8, 14.13

Bisecting K-Means

Must-know: Bisecting K-means runs K-means with k=2 on each cluster to build a divisive tree; total complexity is per-run $I \cdot K \cdot N \cdot D$ times tree height $lo g_{2} N$ , giving $O (lo g_{2} N \cdot I \cdot K \cdot N \cdot D)$ . Greedy splits find local optima; post-processing merges similar clusters.

$O (lo g_{2} N \cdot I \cdot K \cdot N \cdot D)$

⚠️ Top pitfall: Forgetting the log factor: bisecting K-means is more expensive than plain K-means because K-means runs once per split; also trusting greedy splits that separate points of one natural cluster.

Self-check: Why does bisecting K-means have higher complexity than plain K-means? (It runs K-means again and again, once per split, up to the tree height.)

Connects to: 14.6, 14.12

The Elbow Method

Must-know: Elbow method: plot SSE against k; sharp drop then stabilization; the knee is the candidate K. SSE maximum at k=1, zero at k=n. Suggestive estimator, not foolproof.

⚠️ Top pitfall: Treating the elbow point as the exact number of natural clusters: the method is suggestive only and can fail when no clean bend exists.

Self-check: Where does the SSE curve meet the X axis? (At k = n, where every point is its own cluster and SSE = 0.)

Connects to: 14.8, 14.7

Exam Guidance Summary

Must-know: Everything from the session is examinable: four K-means steps, SSE, complexity $O (I \cdot K \cdot N \cdot D)$ derivation, centroid vs medoid, empty clusters, pre/post-processing, limitations, hierarchical clustering directions (AGNES agglomerative bottom-up, DIANA divisive top-down), bisecting K-means, elbow method (suggestive only).

$O (I \cdot K \cdot N \cdot D)$

⚠️ Top pitfall: Reversing agglomerative and divisive directions; treating the elbow as proof; treating K-means output as quality-assured.

Self-check: Which direction does divisive clustering take? (Top-down: one big cluster splits into smaller parts.)

Key Industry Applications

Must-know: Clustering applications: Google News buckets articles by similarity; market segmentation groups customers; anomaly detection keeps outliers as the target; hierarchical clustering mirrors taxonomy and geography; scikit-learn implements the performance measures.

Self-check: When should outliers NOT be removed before clustering? (When the question is anomaly detection and the outliers are the target.)

Previous LectureLecture 13 · Clustering and K-Means

Next LectureLecture 15 · Hierarchical Clustering and Density-Based Clustering

Was this lecture useful?

Loading comments…

🤖

BitsNotes AI Assistant

Subject Notes Assistant

Configure AI Chat

Choose how to access the chatbot

Have your own API key?

Switch to "Bring Your Own Key" tab above for unlimited access with any OpenAI-compatible provider.

AI Provider Preset

API Endpoint URL (OpenAI-Compatible)

API Key

Model Name

🔑 Enter API key above to fetch live models from provider, or enter model name manually.

Remember key for this session (until tab closes)

OpenAI-Compatible API Support

Choose any provider preset (Gemini, DeepSeek, Kimi, GLM, MiniMax, Qwen, OpenAI, Groq, Ollama, etc.) or enter a custom endpoint URL.

Security & Privacy First

Your API key is sent directly from your browser to your specified provider. BitsNotes servers never store or see your key.