轉(zhuǎn)自 http://www.cnblogs.com/jerrylead/archive/2011/04/06/2006910.html
K-means也是聚類算法中最簡(jiǎn)單的一種了镰绎，但是里面包含的思想?yún)s是不一般兰怠。最早我使用并實(shí)現(xiàn)這個(gè)算法是在學(xué)習(xí)韓爺爺那本數(shù)據(jù)挖掘的書中赞厕，那本書比較注重應(yīng)用≈匕撸看了Andrew Ng的這個(gè)講義后才有些明白K-means后面包含的EM思想米奸。
聚類屬于無監(jiān)督學(xué)習(xí)毙籽，以往的回歸役首、樸素貝葉斯、SVM等都是有類別標(biāo)簽y的掺逼，也就是說樣例中已經(jīng)給出了樣例的分類吃媒。而聚類的樣本中卻沒有給定y，只有特征x吕喘，比如假設(shè)宇宙中的星星可以表示成三維空間中的點(diǎn)集[![clip_image002[10]](http://upload-images.jianshu.io/upload_images/2761157-22636e5b2f5ff352.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)](http://images.cnblogs.com/cnblogs_com/jerrylead/201104/201104061601448600.png)赘那。聚類的目的是找到每個(gè)樣本x潛在的類別y，并將同類別y的樣本x放在一起氯质。比如上面的星星募舟，聚類后結(jié)果是一個(gè)個(gè)星團(tuán)，星團(tuán)里面的點(diǎn)相互距離比較近病梢，星團(tuán)間的星星距離就比較遠(yuǎn)了胃珍。
在聚類問題中梁肿，給我們的訓(xùn)練樣本是[](http://images.cnblogs.com/cnblogs_com/jerrylead/201104/201104061601448982.png)，每個(gè)[](http://images.cnblogs.com/cnblogs_com/jerrylead/201104/201104061601453159.png)觅彰，沒有了y吩蔑。
K-means算法是將樣本聚類成k個(gè)簇（cluster），具體算法描述如下：
1填抬、 隨機(jī)選取k個(gè)聚類質(zhì)心點(diǎn)（cluster centroids）為
烛芬。
2、 重復(fù)下面過程直到收斂 {
對(duì)于每一個(gè)樣例i飒责，計(jì)算其應(yīng)該屬于的類
對(duì)于每一個(gè)類j赘娄，重新計(jì)算該類的質(zhì)心
}
K是我們事先給定的聚類數(shù)，C(i)代表樣例i與k個(gè)類中距離最近的那個(gè)類宏蛉，C(i)的值是1到k中的一個(gè)遣臼。質(zhì)心ui代表我們對(duì)屬于同一個(gè)類的樣本中心點(diǎn)的猜測(cè)，拿星團(tuán)模型來解釋就是要將所有的星星聚成k個(gè)星團(tuán)拾并，首先隨機(jī)選取k個(gè)宇宙中的點(diǎn)（或者k個(gè)星星）作為k個(gè)星團(tuán)的質(zhì)心揍堰，然后第一步對(duì)于每一個(gè)星星計(jì)算其到k個(gè)質(zhì)心中每一個(gè)的距離，然后選取距離最近的那個(gè)星團(tuán)作為C(i)嗅义，這樣經(jīng)過第一步每一個(gè)星星都有了所屬的星團(tuán)屏歹；第二步對(duì)于每一個(gè)星團(tuán)，重新計(jì)算它的質(zhì)心ui（對(duì)里面所有的星星坐標(biāo)求平均）之碗。重復(fù)迭代第一步和第二步直到質(zhì)心不變或者變化很小蝙眶。
下圖展示了對(duì)n個(gè)樣本點(diǎn)進(jìn)行K-means聚類的效果，這里k取2褪那。
K-means面對(duì)的第一個(gè)問題是如何保證收斂幽纷，前面的算法中強(qiáng)調(diào)結(jié)束條件就是收斂，可以證明的是K-means完全可以保證收斂性武通。下面我們定性的描述一下收斂性霹崎，我們定義畸變函數(shù)（distortion function）如下：
J函數(shù)表示每個(gè)樣本點(diǎn)到其質(zhì)心的距離平方和珊搀。K-means是要將J調(diào)整到最小冶忱。假設(shè)當(dāng)前J沒有達(dá)到最小值，那么首先可以固定每個(gè)類的質(zhì)心ui境析，調(diào)整每個(gè)樣例的所屬的類別C(i)來讓J函數(shù)減少囚枪，同樣，固定C(i)劳淆，調(diào)整每個(gè)類的質(zhì)心ui也可以使J減小链沼。這兩個(gè)過程就是內(nèi)循環(huán)中使J單調(diào)遞減的過程。當(dāng)J遞減到最小時(shí)沛鸵，u和c也同時(shí)收斂括勺。（在理論上缆八，可以有多組不同的u和c值能夠使得J取得最小值，但這種現(xiàn)象實(shí)際上很少見）疾捍。
由于畸變函數(shù)J是非凸函數(shù)奈辰，意味著我們不能保證取得的最小值是全局最小值，也就是說k-means對(duì)質(zhì)心初始位置的選取比較感冒乱豆，但一般情況下k-means達(dá)到的局部最優(yōu)已經(jīng)滿足需求奖恰。但如果你怕陷入局部最優(yōu)，那么可以選取不同的初始值跑多遍k-means宛裕，然后取其中最小的J對(duì)應(yīng)的u和c輸出瑟啃。
下面累述一下K-means與EM的關(guān)系，首先回到初始問題揩尸，我們目的是將樣本分成k個(gè)類蛹屿，其實(shí)說白了就是求每個(gè)樣例x的隱含類別y，然后利用隱含類別將x歸類岩榆。由于我們事先不知道類別y蜡峰，那么我們首先可以對(duì)每個(gè)樣例假定一個(gè)y吧，但是怎么知道假定的對(duì)不對(duì)呢朗恳？怎么評(píng)價(jià)假定的好不好呢湿颅？我們使用樣本的極大似然估計(jì)來度量，這里是就是x和y的聯(lián)合分布P(x,y)了粥诫。如果找到的y能夠使P(x,y)最大油航，那么我們找到的y就是樣例x的最佳類別了，x順手就聚類了怀浆。但是我們第一次指定的y不一定會(huì)讓P(x,y)最大谊囚，而且P(x,y)還依賴于其他未知參數(shù)，當(dāng)然在給定y的情況下执赡，我們可以調(diào)整其他參數(shù)讓P(x,y)最大镰踏。但是調(diào)整完參數(shù)后，我們發(fā)現(xiàn)有更好的y可以指定沙合，那么我們重新指定y奠伪，然后再計(jì)算P(x,y)最大時(shí)的參數(shù)，反復(fù)迭代直至沒有更好的y可以指定首懈。
這個(gè)過程有幾個(gè)難點(diǎn)绊率，第一怎么假定y？是每個(gè)樣例硬指派一個(gè)y還是不同的y有不同的概率究履，概率如何度量滤否。第二如何估計(jì)P(x,y)，P(x,y)還可能依賴很多其他參數(shù)最仑，如何調(diào)整里面的參數(shù)讓P(x,y)最大藐俺。這些問題在以后的篇章里回答炊甲。
這里只是指出EM的思想，E步就是估計(jì)隱含類別y的期望值欲芹，M步調(diào)整其他參數(shù)使得在給定類別y的情況下蜜葱，極大似然估計(jì)P(x,y)能夠達(dá)到極大值。然后在其他參數(shù)確定的情況下耀石，重新估計(jì)y牵囤，周而復(fù)始，直至收斂滞伟。
上面的闡述有點(diǎn)費(fèi)解揭鳞，對(duì)應(yīng)于K-means來說就是我們一開始不知道每個(gè)樣例X(i)對(duì)應(yīng)隱含變量也就是最佳類別c(i)。最開始可以隨便指定一個(gè)c(i)給它梆奈，然后為了讓P(x,y)最大（這里是要讓J最幸俺纭），我們求出在給定c情況下亩钟，J最小時(shí)的u(i)（前面提到的其他未知參數(shù)）乓梨，然而此時(shí)發(fā)現(xiàn)，可以有更好的c(i)（質(zhì)心與樣例x(i)距離最小的類別）指定給樣例x(i)清酥，那么c(i)得到重新調(diào)整扶镀，上述過程就開始重復(fù)了，直到?jīng)]有更好的c(i)指定焰轻。這樣從K-means里我們可以看出它其實(shí)就是EM的體現(xiàn)臭觉，E步是確定隱含類別變量c，M步更新其他參數(shù)u來使J最小化辱志。這里的隱含類別變量指定方法比較特殊蝠筑，屬于硬指定，從k個(gè)類別中硬選出一個(gè)給樣例揩懒，而不是對(duì)每個(gè)類別賦予不同的概率什乙。總體思想還是一個(gè)迭代優(yōu)化過程已球，有目標(biāo)函數(shù)臣镣，也有參數(shù)變量，只是多了個(gè)隱含變量和悦，確定其他參數(shù)估計(jì)隱含變量退疫，再確定隱含變量估計(jì)其他參數(shù)，直至目標(biāo)函數(shù)最優(yōu)鸽素。
**Part 2 — K-Means中K的選擇
對(duì)這個(gè)問題一直很陌生，1到正無窮亦鳞，肯定有那么幾個(gè)k能夠使得數(shù)據(jù)有比較好的聚類結(jié)果馍忽，怎么找一下呢棒坏？
先把一些 已經(jīng)存在的比較經(jīng)典的方法收藏下
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,...)
各輸入輸出參數(shù)介紹：X：N*P的數(shù)據(jù)矩陣K：表示將X劃分為幾類坝冕，為整數(shù)Idx：N*1的向量，存儲(chǔ)的是每個(gè)點(diǎn)的聚類標(biāo)號(hào)C：K*P的矩陣瓦呼，存儲(chǔ)的是K個(gè)聚類質(zhì)心位置sumD： 1*K的和向量喂窟，存儲(chǔ)的是類間所有點(diǎn)與該類質(zhì)心點(diǎn)距離之和D：N*K的矩陣，存儲(chǔ)的是每個(gè)點(diǎn)與所有質(zhì)心的距離即：K-means聚類算法采用的是將N*P的矩陣X劃分為K個(gè)類央串，使得類內(nèi)對(duì)象之間的距離最大磨澡，而類之間的距離最小。
最后的：[…] = kmeans(…,param1 val1,param2,val2,…)质和，這其中的參數(shù)param1稳摄、param2等，主要可以設(shè)置為如下：1饲宿、distance（距離測(cè)度） sqEuclidean 歐式距離（默認(rèn)時(shí)厦酬，采用此距離方式） cityblock 絕度誤差和，又稱：L1 cosine針對(duì)向量 correlation 針對(duì)有時(shí)序關(guān)系的值 Hamming 只針對(duì)二進(jìn)制數(shù)據(jù)2瘫想、start（初始質(zhì)心位置選擇方法） sample從X中隨機(jī)選取K個(gè)質(zhì)心點(diǎn) uniform根據(jù)X的分布范圍均勻的隨機(jī)生成K個(gè)質(zhì)心 cluster 初始聚類階段隨機(jī)選擇10%的X的子樣本（此方法初始使用sample方法） matrix 提供一K*P的矩陣仗阅，作為初始質(zhì)心位置集合3、replicates（聚類重復(fù)次數(shù)）整數(shù) 使用案例：
[plain] view plain copy
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)
運(yùn)行結(jié)果：
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
