1、K-means聚類算法基本思想聚類分析以相似性為基礎(chǔ)，在一個聚類中的模式之間比不在同一聚類中的模式之間具有更多的相似性K-means也是聚類算法中最簡單的一種。以星團(tuán)劃分為例，首先隨機(jī)選取k個宇宙中的點(diǎn)（或者k個星星）作為k個星團(tuán)的質(zhì)心，然后第一步對于每一個星星計(jì)算其到k個質(zhì)心中每一個的距離，然后選取距離最近的那個星團(tuán)作為-，這樣經(jīng)過第一步每一個星星都有了所屬的星團(tuán)；第二步對于每一個星團(tuán)，重新計(jì)算它的質(zhì)心（對里面所有的星星坐標(biāo)求平均）。重復(fù)迭代第一步和第二步直到質(zhì)心不變或者變化很小。K-means也是聚類算法中最簡單的一種了，但是里面包含的思想?yún)s是不一般。最早我使用并實(shí)現(xiàn)這個算法是在學(xué)習(xí)韓爺爺

2、那本數(shù)據(jù)挖掘的書中，那本書比較注重應(yīng)用。看了AndrewNg的這個講義后才有些明白K-means后面包含的EM思想。聚類屬于無監(jiān)督學(xué)習(xí)，以往的回歸、樸素貝葉斯、SVM等都是有類別標(biāo)簽y的，也就是說樣例中已經(jīng)給出了樣例的分類。而聚類的樣本中卻沒有給定y，只有特征x,比如假設(shè)宇宙中的星星可以表示成三維空間中的點(diǎn)集。聚類的目的是找到每個樣本x潛在的類別y，并將同類別y的樣本x放在一起。比如上面的星星，聚類后結(jié)果是一個個星團(tuán)，星團(tuán)里面的點(diǎn)相互距離比較近，星團(tuán)間的星星距離就比較遠(yuǎn)了。在聚類問題中，給我們的訓(xùn)練樣本是、，每個，沒有了y。K-means算法是將樣本聚類成k個簇（cluster），具體算法描述

3、如下：1、隨機(jī)選取k個聚類質(zhì)心點(diǎn)（clustercentroids）為一:_2、重復(fù)下面過程直到收斂對于每一個樣例i,計(jì)算其應(yīng)該屬于的類決）：=argminfij|3.對于每一個類j,重新計(jì)算該類的質(zhì)心機(jī)i*i%K是我們事先給定的聚類數(shù)，代表樣例i與k個類中距離最近的那個類，的值是1到k中的一個。質(zhì)心-代表我們對屬于同一個類的樣本中心點(diǎn)的猜測，拿星團(tuán)模型來解釋就是要將所有的星星聚成k個星團(tuán)，首先隨機(jī)選取k個宇宙中的點(diǎn)（或者k個星星）作為k個星團(tuán)的質(zhì)心，然后第一步對于每一個星星計(jì)算其到k個質(zhì)心中每一個的距離，然后選取距離最近的那個星團(tuán)作為-，這樣經(jīng)過第一步每一個星星都有了所屬的星團(tuán)；第二步對于每

4、一個星團(tuán)，重新計(jì)算它的質(zhì)心（對里面所有的星星坐標(biāo)求平均）。重復(fù)迭代第一步和第二步直到質(zhì)心不變或者變化很小。下圖展示了對n個樣本點(diǎn)進(jìn)行K-means聚類的效果，這里k取2。K-means面對的第一個問題是如何保證收斂，前面的算法中強(qiáng)調(diào)結(jié)束條件就是收斂，可以證明的是K-means完全可以保證收斂性。下面我們定性的描述一下收斂性，我們定義畸變函數(shù)（distortionfunction）如下：mJ函數(shù)表示每個樣本點(diǎn)到其質(zhì)心的距離平方和。K-means是要將J調(diào)整到最小。假設(shè)當(dāng)前J沒有達(dá)到最小值，那么匚（訂匚（訂lj首先可以固定每個類的質(zhì)心，調(diào)整每個樣例的所屬的類別來讓J函數(shù)減少，同樣，固定，調(diào)整每個類

5、的質(zhì)心U也可以使J減小。這兩個過程就是內(nèi)循環(huán)中使J單調(diào)遞減的過程。當(dāng)J遞減到最小時，和c也同時收斂。（在理論上,P可以有多組不同的和c值能夠使得J取得最小值，但這種現(xiàn)象實(shí)際上很少見）。由于畸變函數(shù)J是非凸函數(shù)，意味著我們不能保證取得的最小值是全局最小值，也就是說k-means對質(zhì)心初始位置的選取比較感冒，但一般情況下k-means達(dá)到的局部最優(yōu)已經(jīng)滿足需求。但如果你怕陷入局部最優(yōu)，那么可以選取不同的初始值跑多遍k-means，然后取其中最小的J對應(yīng)的和c輸出。下面累述一下K-means與EM的關(guān)系，首先回到初始問題，我們目的是將樣本分成k個類，其實(shí)說白了就是求每個樣例x的隱含類別y,然后利用隱

6、含類別將x歸類。由于我們事先不知道類別y,那么我們首先可以對每個樣例假定一個y吧，但是怎么知道假定的對不對呢？怎么評價假定的好不好呢？我們使用樣本的極大似然估計(jì)來度量，這里是就是x和y的聯(lián)合分布P(x,y)了。如果找到的y能夠使P(x,y)最大，那么我們找到的y就是樣例x的最佳類別了，x順手就聚類了。但是我們第一次指定的y不一定會讓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ù)，反復(fù)迭代直至沒有更好的y可以指定。這個過程有幾

7、個難點(diǎn)，第一怎么假定y?是每個樣例硬指派一個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)解，對應(yīng)于K-means來說就是我們一開始不知道每個樣例對應(yīng)隱含變量也就是最佳類別。最開始可以隨便指定一個給它，然后為了讓P(x,y)最大(這里是要讓J最小)，我們求出在給定c情況下，J最小時的(前面提到的其他未知參數(shù))，然而此時發(fā)現(xiàn)，可以有更好的(質(zhì)心與樣例距離最小的類別)指定給樣例，那么得到重新調(diào)整，上述過程就開始重復(fù)了，直到?jīng)]有更好的指定。這樣從K-means里我們可以cp看出它其實(shí)就是EM的體現(xiàn)，E步是確定隱含類別變量，M步更新其他參數(shù)來使J最小化。這里的隱含類別變量指定