机器学习中有两类的大问题,一个是分类,一个是聚类。
分类是根据一些给定的已知类别标号的样本,训练某种学习机器,使它能够对未知类别的样本进行分类。这属于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
五、参考
领取专属 10元无门槛券
私享最新 技术干货