聚类算法及实例

第10章 K-means聚类算法及实例

10.1 K-means简介

机器学习中有两类的大问题,一个是分类,一个是聚类。
分类是根据一些给定的已知类别标识的样本,训练某种学习机器,使它能够对未知类别的样本进行分类。这属于监督学习。而聚类指事先并不知道任何样本的类别标识,希望通过某种算法来把一组未知类别的样本划分成若干类别,这在机器学习中被称作无监督学习。在本章,我们关注其中一个比较简单的聚类算法:k-means算法。

10.2 K-means 算法

k-means算法是一种很常见的聚类算法,它的基本思想是:
(1)适当选择k个类的初始中心
(2)在第i次迭代中,对任意一个样本,求其到K个中心的距离,将该样本归到距离 最短的中心所在的类
(3)利用均值等方法更新该类的中心值
(4)对于所有的K个聚类中心,如果利用(2)(3)的迭代法更新后,值保持不变, 则迭代结束,否则继续迭代。
最后结果是同一类簇中的对象相似度极高,不同类簇中的数据相似度极低。

10.3 K-means简单实例

假定我们有如下9个点:
A1(2, 10) A2(2, 5) A3(8, 4) A4(5, 8) A5(7, 5) A6(6, 4) A7(1, 2) A8(4, 9)
现希望分成3个聚类(即k=3)
初始化选择 A1(2, 10), A4(5, 8) ,A7(1, 2)为聚类中心点,假设两点距离定义为ρ(a, b) = |x2 – x1| + |y2 – y1| . (当然也可以定义为其它格式,如欧氏距离)
第一步:选择3个聚类中,分别为A1,A4,A7

这些点的分布图如下:

第二步:计算各点到3个类中心的距离,那个点里类中心最近,就把这个样本点
划归到这个类。选定3个类中心(即:A1,A4,A7),如下图:

对A1点,计算其到每个cluster 的距离
A1->class1 = |2-2|+|10-10}=0
A1->class2 = |2-5|+|10-8|=5
A1->class3 = |2-1|+|10-2|=9
因此A1 属于cluster1,如下图:

按照类似方法,算出各点到聚类中心的距离,然后按照最近原则,把样本点放在那个族中。如下表格:

根据距离最短原则,样本点的第一次样本划分,如下图:

第三步:求出各类中样本点的均值,并以此为类的中心。
cluster1只有1个点,因此A1为中心点
cluster2的中心点为 ( (8+5+7+6+4)/5,(4+8+5+4+9)/5 )=(6,6)。注意:这个点并非样本点。
cluster3的中心点为( (2+1)/2, (5+2)/2 )= (1.5, 3.5),
新族的具体请看下图中x点:

第四步:计算各样本点到各聚类中心的距离,重复以上第二、第三步,把样本划分到新聚类中,如下图:

持续迭代,