Hi, and welcome to this second lecture,
of the series on clustering.
In this video, we'll talk about one
of the most used partitional methods,
k-means, and
we'll go through the algorithm.
We'll see how it works, and how to
choose all the parameters involved in
the clustering, depending what
your problem is, and the shape.
Of your points.
Now, K-Means is an unsupervised
clustering method.
It's a partitioning algorithm, where
we want to assign the data in clusters
defined by the centroids, and the goal is
to minimize the sum of the squared errors.
So let's start with some definitions.
A centroid is the middle of the cluster.
And points are assigned to the cluster
with the nearest centroid.
Medoid are similar to the centroid but
the end they are actual points.
Some times they are preferred to the
centroid, and there is a funny way to say
that a centroid can locate any
item in the middle of a lake.
Now, distances between
clusters can be seen as
the distances between their centroids,
or their medoids as we see in a moment.
Now, an important quantity is
the sum of the squared error,
SSE, and
it's just used to make partitions.
It is the sum of the squared differences
between each observation, and
its cluster's centroid, or
error all the k clusters.
As trivial case, if four cases
within a clusters are identical,
the SSE would be then equal to zero.
Now let's see how it works,
and this is a four steps
schematic representation on why,
on how the K mean algorithms work.
In this example, the data points are shown
in grey in the first figure, and
we want to partition them in
three non empty clusters.
So, the first step is the initialization,
and
so we randomly choose
the three initial means and
they have shown in red, green,
and blue in the first figure.
In the second steps,
clusters are created associating
each object with the nearest mean.
In the third step, the centroid of
each of the clusters is recomp,
is computed again and
becomes the new mean.
Then step two and step three are repeated.
Until convergence.
So in this case the fundamental step is
also referred to as expectation step.
The update step as a maximization step,
making this
algorithm a variant of the generalized
expectation maximization algorithm.
Now note that the partition
in the second step
represent the Voronoi diagram
generated by the means.
Just as a quick reminder to you,
a Voronoi tessellation is a way of
dividing space into a number of regions.
A set of seeds is specified,
and for each seed.
There will be a corresponding
region consisting of
all points closer to that
seed than to any other.
So in the case of k means
the seeds are the means.
Now the 2 figures show two
different Voronoi tessellations for
the same data, but based on different.
Metrics.
Euclidian distance the left and
Monatin distance on the right.
So that's why that choosing
the right distance also is
crucial when apply these methods.
Now results may also vary depending
on the, on the initialization.
And this is an example where you can see,
where you can see that suppose we
have a three original clusters generated
as in the first figure on the top.
And then there are two answer.
Done with different initialization point,
and
they produce an optimal and
a sub-optimal clustering, as you can see.
Of course, a sub-optimal clustering
at some points are misclassified.
Like if you,
if you notice in the optimal clusterings,
there are two blue dots
that actually should be.
Green dots.
But these are just two points in this,
in this sample of over a hundred.
Now k means is a heuristic algorithm, so
there is no guarantee that it will
converge to the global optimum, and
the results may depend on initial
clusters as we have just seen.
But as we did for classification,
we can use early termination criteria to,
to, to stop the con, to stop the,
the algorit, the algorithm.
For example, we can choose
a fixed number of iterations.
This condition limit, limits the run time.
But in some cases can lead
to a poor clustering beca,
because of its inefficient
number of iterations.
Or we can stop when the assignment
of points to clusters does not
change between iterations, except for
cases with the bare local minimum.
This produce.
A good clustering.
But also in this case
runtime can be very long.
Or we can stop when centroids do not
change anymore between iterations.
Now, changing the initialization as
we've already stressed two times,
may change the cluster results.
So, instead of choosing initially
random points as centroids,
there are some model alternatives
that can speed up the computation.
And also lead to better results.
For example, we can place the first
centroid on a data point.
Then the second on a data point that is as
far away as possible from the first and
so on.
A variant to this solution is to
select more than k centroids and
you surely the k must widely spread.
When dealing with categorical
variables remember that we need to
change the means with the modes.
Now, as we have seen in
the previous lectures,
distances are very
important in clustering.
So this, on this slide there is a list
of distances implemented in math lab for
the k-means functions.
So it's the square Euclidian city block or
Manhattan.
Cosine.
Correlation in the hammock
distance that can be used for
binary data, and where the distance
is a percentage of it's, that differ.
And we have similarly talked about
distances in the previous lesson.
Now.
Other choices you need to make when
running a k-means clustering are what to
do with empty sets and
if user not and online updates.
With empty cluster you can
usually treat them as errors, or
you may choose to remove any
cluster that becomes empty.
Or you can choose to create
a new cluster consisting of
the one point farthest from
its centroid if you want to
keep the same number of clusters
during the whole process.
Now the line up date can be
computationally intense for
very large data sets, but guarantees
a solution that is a local minimum.
Now, let's see some some strength and
weakness of K means.
Its a simple algorith, but
can be powerful and for
this it is often used as benchmark or
as a starting point.
It is relatively efficient.
Since the usual, the computational time,
is o of t by k n, where
k is the number of clusters,and the number
of objects, and t the number of iteration.
And usually t is much smaller than n.
On the other hand, it is very
unstable with noisy data, and and
we need to specify K and
also we can have a problem with clusters
of different, of very different sizes.
With the, clusters with the non-globular
shapes, and cluster, and
clusters differing in density.
Now this figure shows the results of
with clusters of different sizes.
And you can tell that, that if, if the,
the clustering is not really that good.
And one solution to this problem could be,
choose a more than three centroids and
then merge the clusters.
These are other two example, where
the standard k-means can perform poorly.
The first one is a,
is a clusters with a different density.
And the second one are non-global
error shapes of clusters.
And that's why we may need the sum pre and
post-processing when applying k means.
The processing involves
the usual processing steps,
feature selection, normalization and we
may also want to try and remove outliers.
In post-processing we may want
to remove small clusters or
split clusters with high SSE or
merge clusters with lower SSE.
Now, let's see a useful measure to
assess the quality of the clustering.
Now the silhouette shows how well
a point is assigned to each cluster, and
the smaller the value
the better is the assignment.
The formula takes into account
the average dissimilarity of
the point with all the other
within its cluster.
And the lowest average dissimilarity
between point and the,
and any other cluster which
the point is not part of.
Now silhouette values range
from minus 1 to plus 1.
And then highs silhouette
value indicates that
the point is well matched
to its own cluster.
And poorly match them to neighboring
clusters and that's what we want.
If most points have a,
a high silhouette, then we can see
that the clustering is appropriate.
If, many points have a low, or
negative silhouette, mind you,
than the clustering solution
may able too many or too few.
Clusters.
So, this criterium can be used
with any distance metric.
And, and as a reminder, for a given point,
the neighboring cluster is
the cluster with the lowest average.
Basically, it's the second
cluster of choice for that point.
Now we have also say,
that determining the number of clusters in
a data set is a frequent problem
in data clustering and it is,
and actually it's a very well
distinct issue from the, from the.
Actual for, from the actual clustering.
So the correct choice of
(K) is often ambiguous.
And can depend for example for, to on
the shape and scale of the distribution.
And in.
Roughly speaking the ultimate
choice of K will balance
between maximum compression of the data,
using a single cluster and
maximum accuracy by assigning each
little point to it's own cluster.
Of course, if we already have
a prior knowledge of number of.
On the number of the clusters
we can just use that.
Even though we have seen that sometimes
it's better to add more centroids and
then merge the clusters, like when
the clusters are of very different sizes.
In this slide are listed some
criteria that can be used to learn k.
We can use the information
criteria approaches
like the Akaike information criteria, or
the Bayesian information criteria or
the Deviance information criteria.
And this, this, we can use those and
it is possible to make a likelihood
function for the class setting model.
That's because these models
are used to do, are used for
constraining the complexity of a range of
models competing to explain the same data.
The Calinski-Harabasz, criteria is based
on the fact that well defined clusters.
Have, a large between cluster variance,
and this mole within cluster variance.
And also the Davis-Bouldin Criterion is
based on a ratio of inter-cluster and
intra-cluster variances.
When applying this index
remember that the optimal
clustering solution is
the smallest Davies-Bouldin index.
Like and
this is an example usually, OK, so
on the left there are, there are,
there is our data set generated.
From three multivariable distributions
with different parameters values.
And the plot on the right shows
the Davies-Bouldin index and
there, there, on the x axis
there is the number of clusters.
And as you can see the,
the minimum is reached when the cluster,
the number of clusters is three.
That's actually the number of
clusters that we want to, to have.
Now K-means is an example of
expectation maximization algorithm.
And lets briefly point out
other alternatives, so for
example, we can use fuzzy c-means.
In fuzzy clustering there
is a fuzzy clustering and
whether every point is a degree
belonging to clusters,
rather than belonging to
completely just one cluster.
Now the K-Medoids or
PAM uses medoids instead of centroids.
And and CLARA also uses medoids and
actually draws multiple samples of the
data set and applies PAM on each sample.
And the output is the best algorithm.
The advantage is it can deal with
the larger data sets than time.
So, finally, in this video,
we will be seeing, in detail,
the K-Means, that is a simple, but
effective, partitioning algorithm, and
we will be seeing how to choose parameters
involved when running an experiment,
like how to initialize the centroids.
What to do with the empty sets?
What distance metric to use?
How to, to choose K.
Then we also very briefly introduce
some alternatives and in the next video.
I'll talk more about a powerful
clustering algorithm that is
the self organizing maps.