一、聚類思想
????????所謂聚類算法是指將一堆沒(méi)有標(biāo)簽的數(shù)據(jù)自動(dòng)劃分成幾類的方法，屬于無(wú)監(jiān)督學(xué)習(xí)方法，這個(gè)方法要保證同一類的數(shù)據(jù)有相似的特征，如下圖所示：
????????根據(jù)樣本之間的距離或者說(shuō)是相似性（親疏性），把越相似、差異越小的樣本聚成一類（簇），最后形成多個(gè)簇，使同一個(gè)簇內(nèi)部的樣本相似度高，不同簇之間差異性高。
二、k-means聚類分析算法
相關(guān)概念：
K值：要得到的簇的個(gè)數(shù)
質(zhì)心：每個(gè)簇的均值向量，即向量各維取平均即可
距離量度：常用歐幾里得距離和余弦相似度（先標(biāo)準(zhǔn)化）
算法流程：
1、首先確定一個(gè)k值，即我們希望將數(shù)據(jù)集經(jīng)過(guò)聚類得到k個(gè)集合。
2、從數(shù)據(jù)集中隨機(jī)選擇k個(gè)數(shù)據(jù)點(diǎn)作為質(zhì)心。
3、對(duì)數(shù)據(jù)集中每一個(gè)點(diǎn)，計(jì)算其與每一個(gè)質(zhì)心的距離（如歐式距離），離哪個(gè)質(zhì)心近，就劃分到那個(gè)質(zhì)心所屬的集合。
4、把所有數(shù)據(jù)歸好集合后，一共有k個(gè)集合。然后重新計(jì)算每個(gè)集合的質(zhì)心。
5、如果新計(jì)算出來(lái)的質(zhì)心和原來(lái)的質(zhì)心之間的距離小于某一個(gè)設(shè)置的閾值（表示重新計(jì)算的質(zhì)心的位置變化不大，趨于穩(wěn)定，或者說(shuō)收斂），我們可以認(rèn)為聚類已經(jīng)達(dá)到期望的結(jié)果，算法終止。
6、如果新質(zhì)心和原質(zhì)心距離變化很大，需要迭代3~5步驟。
三、數(shù)學(xué)原理
K-Means采用的啟發(fā)式方式很簡(jiǎn)單，用下面一組圖就可以形象的描述:
????????上圖a表達(dá)了初始的數(shù)據(jù)集，假設(shè)k=2。在圖b中，我們隨機(jī)選擇了兩個(gè)k類所對(duì)應(yīng)的類別質(zhì)心，即圖中的紅色質(zhì)心和藍(lán)色質(zhì)心，然后分別求樣本中所有點(diǎn)到這兩個(gè)質(zhì)心的距離，并標(biāo)記每個(gè)樣本的類別為和該樣本距離最小的質(zhì)心的類別，如圖c所示，經(jīng)過(guò)計(jì)算樣本和紅色質(zhì)心和藍(lán)色質(zhì)心的距離，我們得到了所有樣本點(diǎn)的第一輪迭代后的類別。此時(shí)我們對(duì)我們當(dāng)前標(biāo)記為紅色和藍(lán)色的點(diǎn)分別求其新的質(zhì)心，如圖d所示，新的紅色質(zhì)心和藍(lán)色質(zhì)心的位置已經(jīng)發(fā)生了變動(dòng)。圖e和圖f重復(fù)了我們?cè)趫Dc和圖d的過(guò)程，即將所有點(diǎn)的類別標(biāo)記為距離最近的質(zhì)心的類別并求新的質(zhì)心。最終我們得到的兩個(gè)類別如圖f。
四、實(shí)例
坐標(biāo)系中有六個(gè)點(diǎn)：
1、我們分兩組，令K等于2，我們隨機(jī)選擇兩個(gè)點(diǎn)：P1和P2
2、通過(guò)勾股定理計(jì)算剩余點(diǎn)分別到這兩個(gè)點(diǎn)的距離：
3、第一次分組后結(jié)果：
????????組A：P1
????????組B：P2、P3、P4、P5、P6
4、分別計(jì)算A組和B組的質(zhì)心：
? ? ? ? A組質(zhì)心還是P1=（0，0）
????????B組新的質(zhì)心坐標(biāo)為：P哥=（（1+3+8+9+10）/5，（2+1+8+10+7）/5）=（6.2，5.6）
5、再次計(jì)算每個(gè)點(diǎn)到質(zhì)心的距離：
6、第二次分組結(jié)果：
????????組A：P1、P2、P3
????????組B：P4、P5、P6
7、再次計(jì)算質(zhì)心：
????????P哥1=（1.33，1）?
????????P哥2=（9，8.33）
8、再次計(jì)算每個(gè)點(diǎn)到質(zhì)心的距離：
9、第三次分組結(jié)果：
????????組A：P1、P2、P3
????????組B：P4、P5、P6
可以發(fā)現(xiàn)，第三次分組結(jié)果和第二次分組結(jié)果一致，說(shuō)明已經(jīng)收斂，聚類結(jié)束。
五、K-Means的優(yōu)缺點(diǎn)
優(yōu)點(diǎn)：
1、原理比較簡(jiǎn)單，實(shí)現(xiàn)也是很容易，收斂速度快。
2、當(dāng)結(jié)果簇是密集的，而簇與簇之間區(qū)別明顯時(shí), 它的效果較好。
3、主要需要調(diào)參的參數(shù)僅僅是簇?cái)?shù)k。
缺點(diǎn)：
1、K值需要預(yù)先給定，很多情況下K值的估計(jì)是非常困難的。
2、K-Means算法對(duì)初始選取的質(zhì)心點(diǎn)是敏感的，不同的隨機(jī)種子點(diǎn)得到的聚類結(jié)果完全不同 ，對(duì)結(jié)果影響很大。
3、對(duì)噪音和異常點(diǎn)比較的敏感。用來(lái)檢測(cè)異常值。
4、采用迭代方法，可能只能得到局部的最優(yōu)解，而無(wú)法得到全局的最優(yōu)解。
六、細(xì)節(jié)問(wèn)題
1、K值怎么定？
????????答：分幾類主要取決于個(gè)人的經(jīng)驗(yàn)與感覺(jué)，通常的做法是多嘗試幾個(gè)K值，看分成幾類的結(jié)果更好解釋，更符合分析目的等?；蛘呖梢园迅鞣NK值算出的E做比較，取最小的E的K值。
2、初始的K個(gè)質(zhì)心怎么選？
????????答：最常用的方法是隨機(jī)選，初始質(zhì)心的選取對(duì)最終聚類結(jié)果有影響，因此算法一定要多執(zhí)行幾次，哪個(gè)結(jié)果更reasonable，就用哪個(gè)結(jié)果。 當(dāng)然也有一些優(yōu)化的方法，第一種是選擇彼此距離最遠(yuǎn)的點(diǎn)，具體來(lái)說(shuō)就是先選第一個(gè)點(diǎn)，然后選離第一個(gè)點(diǎn)最遠(yuǎn)的當(dāng)?shù)诙€(gè)點(diǎn)，然后選第三個(gè)點(diǎn)，第三個(gè)點(diǎn)到第一、第二兩點(diǎn)的距離之和最小，以此類推。第二種是先根據(jù)其他聚類算法（如層次聚類）得到聚類結(jié)果，從結(jié)果中每個(gè)分類選一個(gè)點(diǎn)。
3、關(guān)于離群值？
????????答：離群值就是遠(yuǎn)離整體的，非常異常、非常特殊的數(shù)據(jù)點(diǎn)，在聚類之前應(yīng)該將這些“極大”“極小”之類的離群數(shù)據(jù)都去掉，否則會(huì)對(duì)于聚類的結(jié)果有影響。但是，離群值往往自身就很有分析的價(jià)值，可以把離群值單獨(dú)作為一類來(lái)分析。
4、單位要一致！
????????答：比如X的單位是米，Y也是米，那么距離算出來(lái)的單位還是米，是有意義的。但是如果X是米，Y是噸，用距離公式計(jì)算就會(huì)出現(xiàn)“米的平方”加上“噸的平方”再開(kāi)平方，最后算出的東西沒(méi)有數(shù)學(xué)意義，這就有問(wèn)題了。
5、標(biāo)準(zhǔn)化
????????答：如果數(shù)據(jù)中X整體都比較小，比如都是1到10之間的數(shù)，Y很大，比如都是1000以上的數(shù)，那么，在計(jì)算距離的時(shí)候Y起到的作用就比X大很多，X對(duì)于距離的影響幾乎可以忽略，這也有問(wèn)題。因此，如果K-Means聚類中選擇歐幾里德距離計(jì)算距離，數(shù)據(jù)集又出現(xiàn)了上面所述的情況，就一定要進(jìn)行數(shù)據(jù)的標(biāo)準(zhǔn)化（normalization），即將數(shù)據(jù)按比例縮放，使之落入一個(gè)小的特定區(qū)間。
