图解数据挖掘K-means算法

 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）

原文链接：http://blog.nlogn.cn/%E6%95%B0%E6%8D%AE%E6%8C%96%E6%8E%98-k-means-%E7%AE%97%E6%B3%95/