k-means: A clustering algorithm

Loading...

来自 University of Washington 的课程

机器学习基础：案例研究

8156 个评分

Explore Related Videos

At Coursera, you will find the best lectures in the world. Here are some of our personalized recommendations for you

University of Washington

机器学习基础：案例研究

8156 个评分

课程 1（共 4 门，Specialization Machine Learning）

你是否好奇数据可以告诉你什么？你是否想在关于机器学习促进商业的核心方式上有深层次的理解？你是否想能同专家们讨论关于回归，分类，深度学习以及推荐系统的一切？在这门课上，你将会通过一系列实际案例学习来获取实践经历。在这门课结束的时候，

从本节课中

Clustering and Similarity: Retrieving Documents

A reader is interested in a specific news article and you want to find a similar articles to recommend. What is the right notion of similarity? How do I automatically search over documents to find the one that is most similar? How do I quantitatively represent the documents in the first place?<p>In this third case study, retrieving documents, you will examine various document representations and an algorithm to retrieve the most similar subset. You will also consider structured representations of the documents that automatically group articles by similarity (e.g., document topic).</p>You will actually build an intelligent document retrieval system for Wikipedia entries in an iPython notebook.

Clustering documents task overview2:27

Clustering documents: An unsupervised learning task4:39

k-means: A clustering algorithm3:59

Other examples of clustering6:01

与讲师见面

Carlos Guestrin
Amazon Professor of Machine Learning
Computer Science and Engineering
Emily Fox
Amazon Professor of Machine Learning
Statistics

[MUSIC]

Well let's look at an algorithm for doing clustering that uses this

metric of just looking at the distance to the cluster center.

Okay, so here, we see the data that we're gonna wanna cluster.

And this algorithm, which is called the k-means algorithm,

starts by assuming that you are gonna end up with k clusters.

So you specify the number of clusters ahead of time.

So the reason the algorithm is called k-means is we have k clusters, and

we're looking at the means of the clusters, just the cluster centers,

when we're assigning points to the different clusters.

Okay, so let's talk about how we initialize the algorithm.

So the first thing we do is we just one example.

There are many ways to initialize where we put the cluster centers.

We will talk about these things more in-depth later.

But for now,

let's just assume that we randomly assigned three different cluster centers.

If we're going to assume some, three means algorithm here.

And then the first step is we're going to assign every observation

to the closest cluster center.

So this observation here gets assigned to the red cluster.

These observations are all closest to the green cluster, or this green center here.

And these are all closest to the blue center.

And a way to do this is something that's just called a Voronoi tessellation.

So we look at the cluster centers and well, we can do our define,

let me switch again to this magenta color.

So here the cluster centers.

And we can just define these regions here.

And these regions represent areas where any observation we might get,

so any new observation, that's a very bad color on red.

What other colors do I have?

How about white?

Cool, white.

So some new observation I get here, if it falls within this red region,

I know it's closest to this red cluster center.

So that's what these colored regions are representing.

Okay so, that's the first step of the algorithm.

So, what I end up with are observations that are assigned to clusters.

But I just randomly initialize those clusters centers, so I probably don't

believe that that really represents the structure underlying the data.

So what I wanna do is I wanna iterate this process, where I then wanna update what my

definition is of the cluster center based on the observations that I've assigned.

So if you remember this red cluster here,

it just had one observation assigned to it.

So when I go to revise the cluster center for that cluster,

it just moves to the previous observation.

But for this green cluster, if I look at the previous cluster center here,

well I'm gonna move it to the center of mass of all

these observations that have been assigned to the green cluster.

And the center of mass of all of them is here,

so this becomes the new cluster center.

And likewise, I do this for all of the blue observations.

This is the new cluster center for this blue observation.

Okay, so now I have a new set of cluster centers.

And what I can do is redraw this Voronoi tessellation, and

reassign my observations to the nearest cluster center.

And then I iterate this process until convergence.

[MUSIC]

探索我们的目录

免费加入并获得个性化推荐、更新和优惠。

Coursera 致力于普及全世界最好的教育，它与全球一流大学和机构合作提供在线课程。

© 2019 Coursera Inc. 保留所有权利。

通过 App Store 下载

通过 Google Play 获取