WEBVTT

00:00:00.046 --> 00:00:04.018
Clustering looks for useful groups
when the data has no group label.

00:00:04.214 --> 00:00:09.077
K-means is often the first method
an analyst tries because its loop is fast,

00:00:09.160 --> 00:00:11.820
concrete, and easy to inspect.

00:00:12.016 --> 00:00:14.595
But its answer contains assumptions.

00:00:14.791 --> 00:00:16.578
Today we will run that loop,

00:00:16.661 --> 00:00:21.491
break those assumptions on purpose,
and then see what a Gaussian mixture adds.

00:00:23.143 --> 00:00:28.926
Think of each dot as one row of a data
set and each axis as one measured feature.

00:00:29.378 --> 00:00:31.096
Clustering asks whether rows

00:00:31.096 --> 00:00:35.322
that sit near one another should be
treated as members of the same group.

00:00:36.235 --> 00:00:38.639
K-means gives a hard answer.

00:00:38.836 --> 00:00:44.049
Each observation belongs to exactly
one cluster, represented by one centre.

00:00:44.246 --> 00:00:47.532
The rule is simply:
choose the nearest centre.

00:00:48.445 --> 00:00:51.487
A Gaussian mixture
can give a softer answer.

00:00:51.684 --> 00:00:56.746
Instead of one cluster label, it gives
one probability for every component.

00:00:56.943 --> 00:01:02.075
Those probabilities express uncertainty
about observations near an overlap.

00:01:03.290 --> 00:01:06.066
That distinction matters operationally.

00:01:06.262 --> 00:01:10.315
A hard label is convenient
for routing or summarizing records.

00:01:10.512 --> 00:01:15.016
A probability is useful when a borderline
case should remain borderline rather than

00:01:15.016 --> 00:01:17.502
being forced across a sharp boundary.

00:01:18.716 --> 00:01:22.688
We will not treat the more flexible
model as automatically better.

00:01:23.001 --> 00:01:28.121
K-means has fewer parameters
and is often exactly the right baseline.

00:01:28.318 --> 00:01:32.751
The point is to know what geometry it
can represent, what failures to expect,

00:01:32.834 --> 00:01:37.316
and when extra probability and covariance
parameters have a real job to do.

00:01:38.378 --> 00:01:40.187
Here is our concrete problem.

00:01:40.271 --> 00:01:45.833
We have twelve observations, two features,
and a requested value k equals two.

00:01:46.029 --> 00:01:49.037
The algorithm must return two clusters.

00:01:49.950 --> 00:01:52.064
First put the data on the plane.

00:01:52.260 --> 00:01:55.721
At this stage the points
have no fitted cluster identity.

00:01:56.518 --> 00:01:59.363
K-means needs starting centres.

00:01:59.560 --> 00:02:02.765
These two are deliberately away
from the middle of the groups.

00:02:03.077 --> 00:02:07.269
They are guesses,
not observations and not yet fitted means.

00:02:08.066 --> 00:02:11.457
The assignment step
examines every observation.

00:02:11.653 --> 00:02:15.691
For each centre, compute squared
Euclidean distance across the features,

00:02:15.775 --> 00:02:19.282
then give the observation
to the centre with the smaller total.

00:02:20.079 --> 00:02:21.481
After that comparison,

00:02:21.565 --> 00:02:26.276
these six points belong to the red centre
and these six belong to the green centre.

00:02:26.360 --> 00:02:29.321
The colour is the hard cluster label z.

00:02:30.025 --> 00:02:33.764
Now freeze the assignments
and update one centre at a time.

00:02:33.960 --> 00:02:39.209
The new red centre is the coordinate-wise
mean of the six red observations.

00:02:40.005 --> 00:02:44.778
The green centre is calculated in exactly
the same way from the green observations.

00:02:44.975 --> 00:02:47.317
A centre is therefore a fitted average,

00:02:47.401 --> 00:02:50.745
not necessarily a row
that actually occurs in the data.

00:02:51.449 --> 00:02:53.749
Move both centres to those means.

00:02:54.061 --> 00:02:58.230
As the centres travel,
the assigned observations stay fixed.

00:02:58.333 --> 00:03:02.560
When the centres arrive,
one full k-means pass is complete.

00:03:03.357 --> 00:03:04.670
Then repeat.

00:03:04.866 --> 00:03:06.733
With the centres in their new positions,

00:03:06.817 --> 00:03:09.824
calculate every
nearest-centre assignment again.

00:03:10.528 --> 00:03:13.524
In this example every
point keeps its colour.

00:03:13.976 --> 00:03:18.377
Recomputing the two means
therefore returns the same two centres.

00:03:18.573 --> 00:03:22.847
The second pass changes neither
the assignments nor the centres.

00:03:23.643 --> 00:03:25.583
That is convergence.

00:03:25.780 --> 00:03:29.785
Implementations may stop when
assignments are identical, when centre

00:03:29.785 --> 00:03:34.615
movement is below a tolerance, or when
a maximum iteration count is reached.

00:03:35.528 --> 00:03:38.280
The loop is alternating optimization.

00:03:38.732 --> 00:03:40.262
With centres fixed,

00:03:40.346 --> 00:03:44.619
nearest-centre assignment cannot increase
the within-cluster sum of squares.

00:03:44.816 --> 00:03:46.160
With assignments fixed,

00:03:46.244 --> 00:03:49.960
replacing each centre
by its mean cannot increase it either.

00:03:50.872 --> 00:03:54.329
So the objective falls
or stays level on every pass.

00:03:54.413 --> 00:03:57.383
Because only finitely
many hard assignments exist,

00:03:57.467 --> 00:03:59.813
the procedure eventually stops.

00:04:00.009 --> 00:04:03.640
What this does not prove is that it
found the best possible clustering.

00:04:03.724 --> 00:04:06.616
It may have stopped
at a merely local solution.

00:04:07.746 --> 00:04:11.693
K-means can finish at different answers
on the same data because its objective

00:04:11.693 --> 00:04:15.595
is not generally convex in all
assignments and centres together.

00:04:15.791 --> 00:04:18.544
Here are two runs with k equal to three.

00:04:19.456 --> 00:04:23.869
On the left, the starting centres
are spread across the visible groups.

00:04:24.065 --> 00:04:24.898
On the right,

00:04:24.982 --> 00:04:29.476
an unlucky draw crowds all three
starting centres into the left-hand group.

00:04:30.273 --> 00:04:33.641
Run the same assignment
and update loop on both sides.

00:04:33.837 --> 00:04:38.087
The favourable start settles
with one centre in each visible group.

00:04:38.883 --> 00:04:42.599
The unlucky run spends two
centres splitting the left group.

00:04:42.796 --> 00:04:45.731
Its remaining centre
absorbs both right-hand groups,

00:04:45.815 --> 00:04:48.172
even though they are visibly separated.

00:04:48.969 --> 00:04:51.698
Another pass changes neither answer.

00:04:51.895 --> 00:04:55.006
Both are local solutions,
but the right-hand solution

00:04:55.006 --> 00:05:00.208
has a larger within-cluster sum of squares
and a much less useful interpretation.

00:05:01.005 --> 00:05:04.489
The practical remedy is not
to trust one random start.

00:05:04.685 --> 00:05:07.216
K-means++ spreads seeds

00:05:07.216 --> 00:05:11.129
by favouring observations far
from centres already chosen.

00:05:11.233 --> 00:05:15.286
It reduces bad starts,
but does not abolish local minima.

00:05:16.682 --> 00:05:21.292
For routine analysis, make
initialization part of the specification.

00:05:21.396 --> 00:05:25.890
Use a dispersed seeding rule,
then run many independent starts.

00:05:26.687 --> 00:05:31.273
Retain the run with the lowest
objective, but still inspect its groups.

00:05:31.377 --> 00:05:34.045
A numerical improvement can be immaterial,

00:05:34.129 --> 00:05:38.564
and several nearly tied runs
can imply genuine ambiguity in the data.

00:05:39.616 --> 00:05:45.143
Record the number of starts, the random
seed, and the spread of objective values.

00:05:45.340 --> 00:05:48.414
Reproducibility here
is not clerical detail.

00:05:48.498 --> 00:05:52.493
It is evidence about how strongly
the data supports the fitted partition.

00:05:53.612 --> 00:05:56.733
The nearest-centre rule
creates Voronoi cells:

00:05:56.816 --> 00:05:59.557
regions separated by straight boundaries.

00:05:59.754 --> 00:06:03.481
That simple geometry explains
several important failures.

00:06:04.278 --> 00:06:07.481
First, consider two long natural groups.

00:06:07.564 --> 00:06:11.361
Their gray outlines run
diagonally across the feature space.

00:06:12.274 --> 00:06:17.383
With these fitted centres, nearest-centre
assignment makes a nearly vertical cut.

00:06:17.579 --> 00:06:19.205
Red and green divide both long

00:06:19.205 --> 00:06:23.977
groups across their length rather than
following the two elongated densities.

00:06:25.378 --> 00:06:27.640
K-means has a centre for location,

00:06:27.723 --> 00:06:32.414
but no parameter for orientation or
different spread in different directions.

00:06:32.610 --> 00:06:35.709
Squared Euclidean distance
therefore prefers compact,

00:06:35.792 --> 00:06:37.812
roughly spherical clusters.

00:06:38.609 --> 00:06:43.486
Second, place one small dense cluster
beside one large diffuse cluster.

00:06:43.682 --> 00:06:46.887
The gray circles show
the intended populations.

00:06:47.684 --> 00:06:51.748
The large group contributes many more
squared distances to the objective.

00:06:51.945 --> 00:06:56.090
A centre can reduce that cost by moving
toward it, while the boundary gives part

00:06:56.090 --> 00:06:58.564
of the large group to the small cluster.

00:06:59.360 --> 00:07:01.415
The result is mathematically consistent

00:07:01.415 --> 00:07:05.398
with the objective, but unfair
to the smaller group as a density.

00:07:05.595 --> 00:07:10.089
K-means does not model cluster
population or variance separately.

00:07:10.885 --> 00:07:15.553
Third, this is one connected cloud
without three clear density peaks.

00:07:15.657 --> 00:07:18.641
We nevertheless request k equals three.

00:07:19.438 --> 00:07:23.293
K-means does not answer
that the data contains one group.

00:07:23.397 --> 00:07:26.321
It returns exactly
three nonempty partitions

00:07:26.404 --> 00:07:28.762
because three centres were requested.

00:07:29.559 --> 00:07:31.951
This is not a software defect.

00:07:32.055 --> 00:07:37.721
The value k is an input to the problem,
not a conclusion reached by the algorithm.

00:07:37.825 --> 00:07:42.191
A tidy colour map does not prove
that the corresponding groups exist.

00:07:43.588 --> 00:07:46.221
Before believing a k-means result,

00:07:46.304 --> 00:07:50.354
ask whether compact clusters
are plausible in the scaled feature space,

00:07:50.437 --> 00:07:53.759
and whether their spreads
and populations are comparable.

00:07:54.555 --> 00:07:58.875
Then test stability across
initializations and resampled data.

00:07:59.071 --> 00:08:03.658
Finally, ask what k means
in the business or scientific setting.

00:08:03.854 --> 00:08:08.067
If it has no interpretation, treat it
as a modelling choice to validate,

00:08:08.150 --> 00:08:10.566
not a fact discovered by the colours.

00:08:11.680 --> 00:08:16.417
To relax hard assignment, keep one
membership number for every component.

00:08:16.614 --> 00:08:22.884
For observation i and component j,
call that number the responsibility r i j.

00:08:23.681 --> 00:08:26.619
Consider this observation
near the overlap.

00:08:26.722 --> 00:08:29.405
A hard rule must choose one side.

00:08:29.509 --> 00:08:33.143
The mixture instead evaluates
how plausible the observation

00:08:33.143 --> 00:08:35.721
is under both fitted components.

00:08:36.518 --> 00:08:37.540
Suppose the resulting

00:08:37.540 --> 00:08:42.231
responsibilities are zero point
three five and zero point six five.

00:08:42.335 --> 00:08:46.875
The second component is more plausible,
but the first remains credible.

00:08:47.071 --> 00:08:49.498
The two values add to one.

00:08:50.411 --> 00:08:55.404
These are model-based probabilities,
not calibrated truth supplied by the data.

00:08:55.508 --> 00:08:59.616
They depend on the fitted component
shapes, their population weights,

00:08:59.699 --> 00:09:02.405
and the Gaussian mixture assumptions.

00:09:04.057 --> 00:09:07.784
A Gaussian mixture says that the
observed density is a weighted sum

00:09:07.784 --> 00:09:10.035
of Gaussian component densities.

00:09:10.118 --> 00:09:13.787
The extra parameters each
answer a distinct question.

00:09:14.491 --> 00:09:18.636
The mixture weight pi records the
expected share of observations generated

00:09:18.636 --> 00:09:20.100
by a component.

00:09:20.296 --> 00:09:22.224
Unlike k-means, the model

00:09:22.224 --> 00:09:26.880
can explicitly represent one large
component and one small component.

00:09:27.584 --> 00:09:32.182
The mean mu gives location,
much like a k-means centre.

00:09:32.379 --> 00:09:36.664
Here the two means sit near
the middle of their respective densities.

00:09:37.460 --> 00:09:41.362
The covariance matrix Sigma
is the crucial addition.

00:09:41.466 --> 00:09:44.288
Its overall scale controls spread.

00:09:44.391 --> 00:09:47.942
Its unequal directional
variances create elongation,

00:09:48.025 --> 00:09:52.055
and its off-diagonal
relationship rotates that elongation.

00:09:52.851 --> 00:09:56.056
These ellipses are equal-density contours.

00:09:56.369 --> 00:09:59.038
They can follow the long
axes of the two groups,

00:09:59.121 --> 00:10:03.858
which is exactly the geometric freedom
missing from nearest-centre k-means.

00:10:05.371 --> 00:10:09.366
The usual fitting procedure
alternates two weighted steps.

00:10:09.562 --> 00:10:12.184
In the E step, use the current weights,

00:10:12.267 --> 00:10:16.401
means, and covariances
to compute every responsibility.

00:10:17.314 --> 00:10:21.680
In the M step, treat those
responsibilities as fractional counts.

00:10:21.877 --> 00:10:25.360
Update each mixture weight
from its total responsibility.

00:10:25.556 --> 00:10:29.075
Update each mean
as a responsibility-weighted average.

00:10:29.988 --> 00:10:34.215
Then update each covariance
from weighted deviations around that mean.

00:10:34.411 --> 00:10:39.613
Repeat the two steps until log
likelihood no longer improves materially.

00:10:39.926 --> 00:10:44.092
Like k-means, this alternating
fit can reach local optima,

00:10:44.175 --> 00:10:46.207
so restarts still matter.

00:10:47.120 --> 00:10:49.640
Return to the elongated example.

00:10:49.837 --> 00:10:53.643
On the left, k-means uses
a straight nearest-centre boundary

00:10:53.726 --> 00:10:56.513
and slices across both natural groups.

00:10:57.310 --> 00:11:01.711
On the right, the Gaussian mixture
learns two covariance ellipses.

00:11:01.908 --> 00:11:06.295
Their orientations follow the groups,
and observations in the overlap can retain

00:11:06.378 --> 00:11:10.198
intermediate responsibilities
instead of being treated as certain.

00:11:11.111 --> 00:11:13.953
The gain is real, but so is the cost.

00:11:14.036 --> 00:11:16.264
More parameters require more data,

00:11:16.347 --> 00:11:21.281
covariance estimates can become unstable,
and a Gaussian component can chase a tiny

00:11:21.281 --> 00:11:24.126
group unless the fit
is regularized and checked.

00:11:25.309 --> 00:11:30.186
K-means and Gaussian mixtures answer
related but different modelling questions.

00:11:30.383 --> 00:11:35.295
K-means asks for a hard partition that
minimizes squared distance to centres.

00:11:36.207 --> 00:11:37.937
A Gaussian mixture asks

00:11:37.937 --> 00:11:41.839
for a probability density
assembled from weighted components.

00:11:42.152 --> 00:11:46.505
It returns probabilistic membership
and can learn a different covariance shape

00:11:46.505 --> 00:11:48.201
for every component.

00:11:48.998 --> 00:11:52.376
Choose k-means when a fast,
interpretable hard partition

00:11:52.376 --> 00:11:56.917
is useful and compact groups
are plausible after sensible scaling.

00:11:57.229 --> 00:12:01.628
Choose a Gaussian mixture
when overlap, unequal populations,

00:12:01.711 --> 00:12:05.090
or elliptical covariance
structure is part of the question.

00:12:06.003 --> 00:12:08.743
Neither model determines
the scientifically correct number

00:12:08.743 --> 00:12:10.380
of groups by itself.

00:12:10.577 --> 00:12:13.492
K-means returns the k requested.

00:12:13.804 --> 00:12:17.483
A mixture with k components
also fits the requested count,

00:12:17.566 --> 00:12:21.201
even if some fitted components
become tiny or redundant.

00:12:22.597 --> 00:12:25.605
A defensible workflow
begins before fitting.

00:12:25.802 --> 00:12:28.738
Scale features according
to what distance should mean,

00:12:28.821 --> 00:12:32.931
then use several starts
and check whether the result is stable.

00:12:33.844 --> 00:12:36.631
Compare several credible values of k.

00:12:36.828 --> 00:12:41.496
For k-means, inspect objective
curves and resampling stability.

00:12:41.948 --> 00:12:46.487
For mixtures, likelihood criteria
such as B I C can help penalize

00:12:46.487 --> 00:12:50.853
unnecessary parameters, but none
of these replaces domain judgment.

00:12:51.650 --> 00:12:54.310
Inspect the fitted objects themselves.

00:12:54.762 --> 00:12:57.674
Look for clusters
created only by one scale,

00:12:57.757 --> 00:13:02.550
uncertain responsibilities, tiny
components, extreme covariance estimates,

00:13:02.633 --> 00:13:05.943
and solutions that change
sharply across restarts.

00:13:06.856 --> 00:13:10.281
Finally, judge the clustering
by the decision it supports.

00:13:10.385 --> 00:13:14.820
A useful segment, anomaly group,
or population subtype must remain

00:13:14.820 --> 00:13:18.327
interpretable and stable
where it will actually be used.

00:13:19.240 --> 00:13:21.342
The durable lesson is simple.

00:13:21.538 --> 00:13:25.426
K-means alternates nearest-centre
assignment with mean updates,

00:13:25.509 --> 00:13:29.945
and that simplicity creates both
its speed and its geometric limits.

00:13:30.141 --> 00:13:34.194
Gaussian mixtures replace certainty
with responsibilities and add weights

00:13:34.194 --> 00:13:38.687
and covariance, but those extra freedoms
deserve validation because they can fit

00:13:38.687 --> 00:13:40.708
both real structure and noise.