机器学习（三）：K均值聚类

机器学习中有两类的大问题，一个是分类，一个是聚类。

分类是根据一些给定的已知类别标号的样本，训练某种学习机器，使它能够对未知类别的样本进行分类。这属于supervised learning（监督学习）。

而聚类指事先并不知道任何样本的类别标号，希望通过某种算法来把一组未知类别的样本划分成若干类别，这在机器学习中被称作 unsupervised learning （无监督学习）。

k均值（k-means）算法就是一种比较简单的聚类算法。

一、k-means基本思想

K-means算法是聚类分析中使用最广泛的算法之一。它把n个对象根据他们的属性分为k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。

比如下图中的n个点，就可以分为3个聚类，用不同的颜色表示。

image1.jpg

k-means算法的基础是最小误差平方和准则。其代价函数是：

formula1.png

式中，μc(i)表示第i个聚类的均值。我们希望代价函数最小，直观的来说，各类内的样本越相似，其与该类均值间的误差平方越小，对所有类所得到的误差平方求和，即可验证分为k类时，各聚类是否是最优的。

上式的代价函数无法用解析的方法最小化，只能有迭代的方法。k-means算法是将样本聚类成 k个簇（cluster），其中k是用户给定的，其求解过程非常直观简单，具体算法描述如下：

（1）随机选取 k个聚类质心点

（2）重复下面过程直到收敛

{

对于每一个样例 i，计算其应该属于的类：

formula2.png

对于每一个类 j，重新计算该类的质心：

formula3.png

}

下图从(a)到(f)演示了对n个样本点进行K-means聚类的过程和效果，这里k取2。

image2.jpg

二、伪代码

三、程序

编写此程序使用的是python 3，并且需要安装Numpy和matplotlib库。

安装方法可参考 https://www.jianshu.com/p/717521015940

（一）

为了方便理解，咱们第一次只准备了四组数据，放在testSet.txt里

在程序里，可以逐步打印出执行结果

运行结果：

result1.png

result2.png

（二）

为了观察到更好的效果，这次准备了多一点（80行）数据，放在testSet2.txt里

代码与上面的几乎一样，只是做了少量修改

运行结果：

result3.png

result4.png

四、Github源码下载

https://github.com/zhenghaishu/MachineLearning/tree/master/KMeans

五、参考