Clustering: K-means

转自 http://www.cnblogs.com/jerrylead/archive/2011/04/06/2006910.html
K-means也是聚类算法中最简单的一种了，但是里面包含的思想却是不一般。最早我使用并实现这个算法是在学习韩爷爷那本数据挖掘的书中，那本书比较注重应用。看了Andrew Ng的这个讲义后才有些明白K-means后面包含的EM思想。

   聚类属于无监督学习，以往的回归、朴素贝叶斯、SVM等都是有类别标签y的，也就是说样例中已经给出了样例的分类。而聚类的样本中却没有给定y，只有特征x，比如假设宇宙中的星星可以表示成三维空间中的点集[![clip_image002[10]](https://img.haomeiwen.com/i2761157/22636e5b2f5ff352.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)](http://images.cnblogs.com/cnblogs_com/jerrylead/201104/201104061601448600.png)。聚类的目的是找到每个样本x潜在的类别y，并将同类别y的样本x放在一起。比如上面的星星，聚类后结果是一个个星团，星团里面的点相互距离比较近，星团间的星星距离就比较远了。
 在聚类问题中，给我们的训练样本是[![clip_image004](https://img.haomeiwen.com/i2761157/3aa161e5ae212b96.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)](http://images.cnblogs.com/cnblogs_com/jerrylead/201104/201104061601448982.png)，每个[![clip_image006](https://img.haomeiwen.com/i2761157/417f48df2b247be5.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)](http://images.cnblogs.com/cnblogs_com/jerrylead/201104/201104061601453159.png)，没有了y。
 K-means算法是将样本聚类成k个簇（cluster），具体算法描述如下：

1、 随机选取k个聚类质心点（cluster centroids）为

clip_image008[6] 。
2、 重复下面过程直到收敛 {
对于每一个样例i，计算其应该属于的类
clip_image009
对于每一个类j，重新计算该类的质心
clip_image010[6]
}

K是我们事先给定的聚类数，C⁽ⁱ⁾代表样例i与k个类中距离最近的那个类，C⁽ⁱ⁾的值是1到k中的一个。质心u_i代表我们对属于同一个类的样本中心点的猜测，拿星团模型来解释就是要将所有的星星聚成k个星团，首先随机选取k个宇宙中的点（或者k个星星）作为k个星团的质心，然后第一步对于每一个星星计算其到k个质心中每一个的距离，然后选取距离最近的那个星团作为C⁽ⁱ⁾，这样经过第一步每一个星星都有了所属的星团；第二步对于每一个星团，重新计算它的质心u_i（对里面所有的星星坐标求平均）。重复迭代第一步和第二步直到质心不变或者变化很小。

下图展示了对n个样本点进行K-means聚类的效果，这里k取2。

clip_image015

K-means面对的第一个问题是如何保证收敛，前面的算法中强调结束条件就是收敛，可以证明的是K-means完全可以保证收敛性。下面我们定性的描述一下收敛性，我们定义畸变函数（distortion function）如下：

clip_image016[6]

J函数表示每个样本点到其质心的距离平方和。K-means是要将J调整到最小。假设当前J没有达到最小值，那么首先可以固定每个类的质心u_i，调整每个样例的所属的类别C⁽ⁱ⁾来让J函数减少，同样，固定C⁽ⁱ⁾，调整每个类的质心u_i也可以使J减小。这两个过程就是内循环中使J单调递减的过程。当J递减到最小时，u和c也同时收敛。（在理论上，可以有多组不同的u和c值能够使得J取得最小值，但这种现象实际上很少见）。

由于畸变函数J是非凸函数，意味着我们不能保证取得的最小值是全局最小值，也就是说k-means对质心初始位置的选取比较感冒，但一般情况下k-means达到的局部最优已经满足需求。但如果你怕陷入局部最优，那么可以选取不同的初始值跑多遍k-means，然后取其中最小的J对应的u和c输出。

下面累述一下K-means与EM的关系，首先回到初始问题，我们目的是将样本分成k个类，其实说白了就是求每个样例x的隐含类别y，然后利用隐含类别将x归类。由于我们事先不知道类别y，那么我们首先可以对每个样例假定一个y吧，但是怎么知道假定的对不对呢？怎么评价假定的好不好呢？我们使用样本的极大似然估计来度量，这里是就是x和y的联合分布P(x,y)了。如果找到的y能够使P(x,y)最大，那么我们找到的y就是样例x的最佳类别了，x顺手就聚类了。但是我们第一次指定的y不一定会让P(x,y)最大，而且P(x,y)还依赖于其他未知参数，当然在给定y的情况下，我们可以调整其他参数让P(x,y)最大。但是调整完参数后，我们发现有更好的y可以指定，那么我们重新指定y，然后再计算P(x,y)最大时的参数，反复迭代直至没有更好的y可以指定。

这个过程有几个难点，第一怎么假定y？是每个样例硬指派一个y还是不同的y有不同的概率，概率如何度量。第二如何估计P(x,y)，P(x,y)还可能依赖很多其他参数，如何调整里面的参数让P(x,y)最大。这些问题在以后的篇章里回答。

这里只是指出EM的思想，E步就是估计隐含类别y的期望值，M步调整其他参数使得在给定类别y的情况下，极大似然估计P(x,y)能够达到极大值。然后在其他参数确定的情况下，重新估计y，周而复始，直至收敛。

上面的阐述有点费解，对应于K-means来说就是我们一开始不知道每个样例X⁽ⁱ⁾对应隐含变量也就是最佳类别c⁽ⁱ⁾。最开始可以随便指定一个c⁽ⁱ⁾给它，然后为了让P(x,y)最大（这里是要让J最小），我们求出在给定c情况下，J最小时的u⁽ⁱ⁾（前面提到的其他未知参数），然而此时发现，可以有更好的c⁽ⁱ⁾（质心与样例x⁽ⁱ⁾距离最小的类别）指定给样例x⁽ⁱ⁾，那么c⁽ⁱ⁾得到重新调整，上述过程就开始重复了，直到没有更好的c⁽ⁱ⁾指定。这样从K-means里我们可以看出它其实就是EM的体现，E步是确定隐含类别变量c，M步更新其他参数u来使J最小化。这里的隐含类别变量指定方法比较特殊，属于硬指定，从k个类别中硬选出一个给样例，而不是对每个类别赋予不同的概率。总体思想还是一个迭代优化过程，有目标函数，也有参数变量，只是多了个隐含变量，确定其他参数估计隐含变量，再确定隐含变量估计其他参数，直至目标函数最优。

**Part 2 — K-Means中K的选择

对这个问题一直很陌生，1到正无穷，肯定有那么几个k能够使得数据有比较好的聚类结果，怎么找一下呢？

File:DataClustering ElbowCriterion.JPG
先把一些 已经存在的比较经典的方法收藏下
1、stackoverflow上面的答案：
You can maximize the Bayesian Information Criterion (BIC):
BIC(C|X)=L(X|C)−(p/2)∗log n

where L(X|C) is the log-likelihood of the dataset X according to model C, p is the number of parameters in the model C, and n is the number of points in the dataset. See "X-means: extending K-means with efficient estimation of the number of clusters" by Dan Pelleg and Andrew Moore in ICML 2000.

Another approach is to start with a large value for k and keep removing centroids (reducing k) until it no longer reduces the description length. See "MDL principle for robust vector quantisation" by Horst Bischof, Ales Leonardis, and Alexander Selb in Pattern Analysis and Applications vol. 2, p. 59-72, 1999.

Finally, you can start with one cluster, then keep splitting clusters until the points assigned to each cluster have a Gaussian distribution. In "Learning the k in k-means" (NIPS 2003), Greg Hamerly and Charles Elkan show some evidence that this works better than BIC, and that BIC does not penalize the model's complexity strongly enough.
Bayesian k-means may be a solution when you don't know the number of clusters. There's a related paper given in the website and the corresponding MATLAB code is also given.

2、wiki上有专题：
Determining the number of clusters in a data set
Part 3 — Matlab中K-means的使用方法：K-means clustering - MATLAB kmeans - MathWorks China
Matlab中的使用方法如下：
[plain] view plain copy

IDX = kmeans(X,k)
[IDX,C] = kmeans(X,k)
[IDX,C,sumd] = kmeans(X,k)
[IDX,C,sumd,D] = kmeans(X,k)
[...] = kmeans(...,param1,val1,param2,val2,...)

各输入输出参数介绍：X：N*P的数据矩阵K：表示将X划分为几类，为整数Idx：N*1的向量，存储的是每个点的聚类标号C：K*P的矩阵，存储的是K个聚类质心位置sumD： 1*K的和向量，存储的是类间所有点与该类质心点距离之和D：N*K的矩阵，存储的是每个点与所有质心的距离即：K-means聚类算法采用的是将N*P的矩阵X划分为K个类，使得类内对象之间的距离最大，而类之间的距离最小。

最后的：[…] = kmeans(…,param1 val1,param2,val2,…)，这其中的参数param1、param2等，主要可以设置为如下：1、distance（距离测度） sqEuclidean 欧式距离（默认时，采用此距离方式） cityblock 绝度误差和，又称：L1 cosine针对向量 correlation 针对有时序关系的值 Hamming 只针对二进制数据2、start（初始质心位置选择方法） sample从X中随机选取K个质心点 uniform根据X的分布范围均匀的随机生成K个质心 cluster 初始聚类阶段随机选择10%的X的子样本（此方法初始使用sample方法） matrix 提供一K*P的矩阵，作为初始质心位置集合3、replicates（聚类重复次数）整数 使用案例：

[plain] view plain copy

在CODE上查看代码片 派生到我的代码片

data=
5.0 3.5 1.3 0.3 -1
5.5 2.6 4.4 1.2 0
6.7 3.1 5.6 2.4 1
5.0 3.3 1.4 0.2 -1
5.9 3.0 5.1 1.8 1
5.8 2.6 4.0 1.2 0

[Idx,C,sumD,D]=Kmeans(data,3,'dist','sqEuclidean','rep',4)

运行结果：
Idx =
1
2
3
1
3
2
C =
5.0000 3.4000 1.3500 0.2500 -1.0000
5.6500 2.6000 4.2000 1.2000 0
6.3000 3.0500 5.3500 2.1000 1.0000
sumD =
0.0300
0.1250
0.6300
D =
0.0150 11.4525 25.5350
12.0950 0.0625 3.5550
29.6650 5.7525 0.3150
0.0150 10.7525 24.9650
21.4350 2.3925 0.3150
10.2050 0.0625 4.0850