K-means Clustering Algorithm 中文名也许叫“K均值聚类算法”,是统计学和数据挖掘领域中常用的一种算法。维基百科上是这样介绍的:k-means clustering is a method of cluster analysis which aims to partition n observations into k clusters in which each observation belongs to the cluster with the nearest mean(将n个观察值分成k个类,使得每一类中的观察值与该类的均值最接近,与其他的类的均值较远)。

先来看一个最简单、最直观的图示。

上图有很多点,现在想将他们分成3个cluster,怎么办? 作为人,一眼就看出来了,但是计算机就没那么容易分类了,我们必须借助一些算法,而k-means就是其中的一种。K-means不仅可以处理二维空间的聚类,还可以扩展到n维向量空间,还可以处理字符、图像、声音等等。

以上图为例,K-means算法的基本步骤如下:
输入:一个要处理的数据集(例如上图的点集),分成cluster的个数(比如3个),一个mean的计算方法(比如两点之间的距离函数,)
Step1. 首先随机的给每个点标上一种颜色,并计算同种颜色点坐标的算术平均值,表示出相 应的均值点。
Step2. 根据目前算出的均值点,将所有的点集分成3类,为每一类中的每个点,标上与离它最近的均值点相同的颜色。怎么分呢?这里要介绍一种“泰森多边形法”,英文名叫“Voronoi diagram”(见文章最后维基百科链接)。于是就有了下面这张图。

Step3.重复step2,直到所有点的颜色不再变化为止。
算法结束,输出如下结果。

上面的例子在简单的二维空间里,如果放在三维空间那么mean的计算方法就要修改了。事实上在处理多维空间、字符、图像等问题时,不同的问题有不同的计算公式,这时mean的意思可能就不是“均值”了,也许用“相似度”和“相异度”来衡量个体之间的关系会更好,详见参考文章一。

按照惯例,下面应该贴上我自己写的k-means算法代码了,不过很遗憾的是我现在还在摸索用python的numpy库和matplotlib库画图的方法,在参考文章二中有一个python语言的代码。

最后要感谢一下数据挖掘老师  Devert Alexandre,因为本文的图片都是从他的slides里截出来的。^_^

参考文章一
参考文章二
维基百科k-means链接
泰森多边形法维基百科链接(Voronoi diagram)

16,641 views
Home

13 Comments so far

Leave a comment

Name(required)
Mail (required),(will not be published)
Website(recommended)

Fields in bold are required. Email addresses are never published or distributed.

Some HTML code is allowed:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
URLs must be fully qualified (eg: http://blog.nlogn.cn),and all tags must be properly closed.

Line breaks and paragraphs are automatically converted.

Please keep comments relevant. Off-topic, offensive or inappropriate comments may be edited or removed.