Name: 6 3 k均值算法 12 49． (6 3 The k Means Algorithm 12 49)
Uploaded: 2021-01-14T07:02:44.000Z
Duration: 12 min 50 s
Description: 【看影片學英語】數萬部 YouTube 影片，搭配英漢字典即點即查，輕鬆掌握單字發音與用法，長久累積看電影不必再看字幕。

Welcome back to Mining of Massive Datasets.

We're going to continue our discussion of Clustering today,

Recall that we previously, looked at another means,

way of doing clustering called Agglomerative Hierarchical Clustering.

Now, that algorithm worked very well in terms of producing clusters, but

unfortunately, it doesn't work very well for

large da, datasets because of its computational complexity.

The k-Means Algorithm, or the k-Means family of Algorithms actually,

is a way of addressing that problem, of creating Algorithms that

are computational tractable and work with very large datasets.

Now the k-means Algorithm assumes, a Euclidean space and

And the first step, is to pick k, the number of clusters.

Now, for now let's assume that we pick a number k, and

say that's the number of clusters that we finally want.

Towards the end, I'll ca, I'll show you how to actually, pick this this value k.

For now, let's just assume that k is the given.

Now, we're going to initialize k clusters, by picking one point per cluster.

For example, we could just pick k points at random, one, and

And that would be the one way of picking the points.

Later on we'll examine other ways of doing this much better.

Now that we have clusters populated with these k-points picked at random,

We're really go through all the points in our datasets.

And for each point, we're going to place it in the cluster.

So, you're going to find the cluster with the closest centroid to the data point,

and then we'll assign that data point to that cluster.

Now, when we assign a whole bunch of new data points to a cluster,

Because of all the new data points that have been added with the cluster.

update the locations of the centroids of each of the k clusters,

by taking into account the new data points that have been added to those clusters.

Now, once we do this, we'll find that the centroids of,

now a point that was close to one cluster may be closer to another cluster.

So, we need to go through and reassign all points to their closest centroid.

And sometimes this moves points between the clusters.

And notice that we, we may have to do poi, you know, steps 2 and 3 again and again.

And it, thi, this is exactly, what we're going to do.

We're going to repeat steps 2 and 3, until Convergence.

And what we mean by Convergence, is that the k centroids don't move any further,

and the point don't move en, any further across the across the centroids.

At that point, we have a stable k-means clustering.

So, here's a set of points and we are going to do obviously,

say that k is equal to 2, so we're looking to find two clusters in this dataset.

Now in, in Round 1, I'm at random going to pick two points since k equal 2 and

the, the point that I've highlighted with the in pink here and

the point that I've highlighted in blue here as the two centroids.

I've picked this totally arbitrarily and at random.

Now, what I'm going to do is I'm going to go through, all the data points and for

each data point, I'm going to assign it to the centroid that it's closest to.

So, observe that this point for example here, is close to the red cluster.

So, I'm going to assign it to the red cluster.

Whereas, this point here is closer to the blue cluster than to the red cluster, so

I'm going to assign it to the blue cluster.

And, you know, when I go through all the data points and do this.

Here is the clustering that I end up with.

These two points here end up in the you know, in, in the pink cluster here and

this set of points are closer to the the blue point here, and so

So, that's round 1 of k-means clustering.

Now, what I'm going to do now is, because I've

created these two new clusters I'm going to compute the new centroids.

And when I compute the new centroids, the the centroid of

the pink cluster moves over a little bit to the left to this new position here.

And the centroid of the blue cluster moves to that new position.

Now, is because I have new centroids, I'm going to go through in round 2, I'm

going to go through each data point again and assign it to it's closest centroid.

And when I do that,observe that, point for example this point here

is now closer to the the pink cluster than it is to the blue cluster.

And so it moves from the blue cluster to the pink cluster.

[SOUND] And so we have this new clustering and the end of round 2.

Now that, we have the new clustering, I'm going to recompute the centroids once

again, and when I recompute the centroids, the the centroids migrate further.

And because the centroids are migrated further,

I have to recompute the, the assignment of points to the centroids again.

And when I do that these two points here are then

are closer to the the pink cluster, so they move to the to the pink cluster and

and we end up with the clustering show here at the end of Round 3.

Now, as it turns out, in this case, Round 3 is the last round.

the, points don't migrate any further, and we have a stable clustering.

So, what we have here is the, clustering, the k-means clustering for

Observe that I started from a completely random assignment of you know, of,

of centroids and actually migrated the centroids to where they finally ended up.

Now, the important question here is, how to we pick the right value of k?

In the previous example, we arbitrarily picked k is equal to 2 and

字幕列表影片播放

6 3 k均值算法 12 49． (6 3 The k Means Algorithm 12 49)

assume

approach

obvious

bunch