原創(chuàng ) | 一文讀懂K均值（K-Means）聚類(lèi)算法

眾所周知，機器學(xué)習算法可分為監督學(xué)習(Supervised learning)和無(wú)監督學(xué)習(Unsupervised learning)。
監督學(xué)習常用于分類(lèi)和預測。是讓計算機去學(xué)習已經(jīng)創(chuàng )建好的分類(lèi)模型，使分類(lèi)（預測）結果更好的接近所給目標值，從而對未來(lái)數據進(jìn)行更好的分類(lèi)和預測。因此，數據集中的所有變量被分為特征和目標，對應模型的輸入和輸出；數據集被分為訓練集和測試集，分別用于訓練模型和模型測試與評估。常見(jiàn)的監督學(xué)習算法有Regression(回歸)、KNN和SVM(分類(lèi))。
無(wú)監督學(xué)習常用于聚類(lèi)。輸入數據沒(méi)有標記，也沒(méi)有確定的結果，而是通過(guò)樣本間的相似性對數據集進(jìn)行聚類(lèi)，使類(lèi)內差距最小化，類(lèi)間差距最大化。無(wú)監督學(xué)習的目標不是告訴計算機怎么做，而是讓它自己去學(xué)習怎樣做事情，去分析數據集本身。常用的無(wú)監督學(xué)習算法有K-means、 PCA(Principle Component Analysis)。
聚類(lèi)算法又叫做“無(wú)監督分類(lèi)”，其目的是將數據劃分成有意義或有用的組（或簇）。這種劃分可以基于業(yè)務(wù)需求或建模需求來(lái)完成，也可以單純地幫助我們探索數據的自然結構和分布。比如在商業(yè)中，如果手頭有大量的當前和潛在客戶(hù)的信息，可以使用聚類(lèi)將客戶(hù)劃分為若干組，以便進(jìn)一步分析和開(kāi)展營(yíng)銷(xiāo)活動(dòng)。再比如，聚類(lèi)可以用于降維和矢量量化，可以將高維特征壓縮到一列當中，常常用于圖像、聲音和視頻等非結構化數據，可以大幅度壓縮數據量。
聚類(lèi)算法與分類(lèi)算法的比較:

K-Means詳解
1. K-Means的工作原理
作為聚類(lèi)算法的典型代表，K-Means可以說(shuō)是最簡(jiǎn)單的聚類(lèi)算法，那它的聚類(lèi)工作原理是什么呢？

在K-Means算法中，簇的個(gè)數K是一個(gè)超參數，需要人為輸入來(lái)確定。K-Means的核心任務(wù)就是根據設定好的K，找出K個(gè)最優(yōu)的質(zhì)心，并將離這些質(zhì)心最近的數據分別分配到這些質(zhì)心代表的簇中去。具體過(guò)程可以總結如下：
a.首先隨機選取樣本中的K個(gè)點(diǎn)作為聚類(lèi)中心；b.分別算出樣本中其他樣本距離這K個(gè)聚類(lèi)中心的距離，并把這些樣本分別作為自己最近的那個(gè)聚類(lèi)中心的類(lèi)別；c.對上述分類(lèi)完的樣本再進(jìn)行每個(gè)類(lèi)別求平均值，求解出新的聚類(lèi)質(zhì)心；d.與前一次計算得到的K個(gè)聚類(lèi)質(zhì)心比較，如果聚類(lèi)質(zhì)心發(fā)生變化，轉過(guò)程b，否則轉過(guò)程e；e.當質(zhì)心不發(fā)生變化時(shí)（當我們找到一個(gè)質(zhì)心，在每次迭代中被分配到這個(gè)質(zhì)心上的樣本都是一致的，即每次新生成的簇都是一致的，所有的樣本點(diǎn)都不會(huì )再從一個(gè)簇轉移到另一個(gè)簇，質(zhì)心就不會(huì )變化了），停止并輸出聚類(lèi)結果。K-Means算法計算過(guò)程如圖1 所示：

圖1  K-Means算法計算過(guò)程

圖2  K-Means迭代示意圖
例題：
1. 對于以下數據點(diǎn)，請采用k-means方法進(jìn)行聚類(lèi)（手工計算）。假設聚類(lèi)簇數k=3，初始聚類(lèi)簇中心分別為數據點(diǎn)2、數據點(diǎn)3、數據點(diǎn)5。

解：

正在進(jìn)行第1次迭代初始質(zhì)心為B、C、EAB = 2.502785AC = 5.830635AE = 7.054443DB = 3.819911DC = 1.071534DE = 7.997158因此，第一簇：{A，B}；第二簇：{C，D}；第三簇：{E}即[array([-5.379713, -3.362104]), array([-3.487105, -1.724432])][array([ 0.450614, -3.302219]), array([-0.39237, -3.963704])][array([-3.45368, 3.424321])]所以第一簇的質(zhì)心為F：[-4.433409 -2.543268]第二簇的質(zhì)心為G：[ 0.029122 -3.6329615]第三簇的質(zhì)心為H：[-3.45368 3.424321]###########################################################正在進(jìn)行第2次迭代AF = 1.251393AG = 5.415613AH = 7.054443BF = 1.251393BG = 4.000792BH = 5.148861CF = 4.942640CG = 0.535767CH = 7.777522DF = 4.283414DG = 0.535767DH = 7.997158EF = 6.047478EG = 7.869889EH = 0.000000因此，第一簇：{A，B}；第二簇：{C，D}；第三簇：{E}即[array([-5.379713, -3.362104]), array([-3.487105, -1.724432])][array([ 0.450614, -3.302219]), array([-0.39237, -3.963704])][array([-3.45368, 3.424321])]所以第一簇的質(zhì)心為：[-4.433409 -2.543268]第二簇的質(zhì)心為：[ 0.029122 -3.6329615]第三簇的質(zhì)心為：[-3.45368 3.424321]###########################################################由于三個(gè)簇的成員保持不變，聚類(lèi)結束

3. K-Means算法的時(shí)間復雜度
眾所周知，算法的復雜度分為時(shí)間復雜度和空間復雜度，時(shí)間復雜度是指執行算法所需要的計算工作量，常用大O符號表述；而空間復雜度是指執行這個(gè)算法所需要的內存空間。如果一個(gè)算法的效果很好，但需要的時(shí)間復雜度和空間復雜度都很大，那將會(huì )在算法的效果和所需的計算成本之間進(jìn)行權衡。
K-Means算法是一個(gè)計算成本很大的算法。K-Means算法的平均復雜度是O(k*n*T)，其中k是超參數，即所需要輸入的簇數，n是整個(gè)數據集中的樣本量，T是所需要的迭代次數。在最壞的情況下，KMeans的復雜度可以寫(xiě)作O(n(k+2)/p)，其中n是整個(gè)數據集中的樣本量，p是特征總數。
4. 聚類(lèi)算法的模型評估指標
不同于分類(lèi)模型和回歸，聚類(lèi)算法的模型評估不是一件簡(jiǎn)單的事。在分類(lèi)中，有直接結果（標簽）的輸出，并且分類(lèi)的結果有正誤之分，所以需要通過(guò)使用預測的準確度、混淆矩陣、ROC曲線(xiàn)等指標來(lái)進(jìn)行評估，但無(wú)論如何評估，都是在評估“模型找到正確答案”的能力。而在回歸中，由于要擬合數據，可以通過(guò)SSE均方誤差、損失函數來(lái)衡量模型的擬合程度。但這些衡量指標都不能夠用于聚類(lèi)。
聚類(lèi)模型的結果不是某種標簽輸出，并且聚類(lèi)的結果是不確定的，其優(yōu)劣由業(yè)務(wù)需求或者算法需求來(lái)決定，并且沒(méi)有永遠的正確答案。那如何衡量聚類(lèi)的效果呢？K-Means的目標是確?！按貎炔町愋?，簇外差異大”，所以可以通過(guò)衡量簇內差異來(lái)衡量聚類(lèi)的效果。前面講過(guò)，Inertia是用距離來(lái)衡量簇內差異的指標，因此，是否可以使用Inertia來(lái)作為聚類(lèi)的衡量指標呢？
「肘部法（手肘法）認為圖3的拐點(diǎn)就是k的最佳值」

手肘法核心思想：隨著(zhù)聚類(lèi)數k的增大，樣本劃分會(huì )更加精細，每個(gè)簇的聚合程度會(huì )逐漸提高，那么Inertia自然會(huì )逐漸變小。當k小于真實(shí)聚類(lèi)數時(shí)，由于k的增大會(huì )大幅增加每個(gè)簇的聚合程度，故Inertia的下降幅度會(huì )很大，而當k到達真實(shí)聚類(lèi)數時(shí)，再增加k所得到的聚合程度回報會(huì )迅速變小，所以Inertia的下降幅度會(huì )驟減，然后隨著(zhù)k值的繼續增大而趨于平緩，也就是說(shuō)Inertia和k的關(guān)系圖是一個(gè)手肘的形狀，而這個(gè)肘部對應的k值就是數據的真實(shí)聚類(lèi)數。例如下圖，肘部對于的k值為3(曲率最高)，故對于這個(gè)數據集的聚類(lèi)而言，最佳聚類(lèi)數應該選3。

圖3  手肘法
那就引出一個(gè)問(wèn)題：Inertia越小模型越好嗎？答案是可以的，但是Inertia這個(gè)指標又有其缺點(diǎn)和極限：
a.它的計算太容易受到特征數目的影響。b.它不是有界的，Inertia是越小越好，但并不知道何時(shí)達到模型的極限，能否繼續提高。c.它會(huì )受到超參數K的影響，隨著(zhù)K越大，Inertia必定會(huì )越來(lái)越小，但并不代表模型效果越來(lái)越好。d.Inertia 對數據的分布有假設，它假設數據滿(mǎn)足凸分布，并且它假設數據是各向同性的，所以使用Inertia作為評估指標，會(huì )讓聚類(lèi)算法在一些細長(cháng)簇、環(huán)形簇或者不規則形狀的流形時(shí)表現不佳。
那又可以使用什么指標來(lái)衡量模型效果呢？
（1）輪廓系數
在99%的情況下，是對沒(méi)有真實(shí)標簽的數據進(jìn)行探索，也就是對不知道真正答案的數據進(jìn)行聚類(lèi)。這樣的聚類(lèi)，是完全依賴(lài)于評價(jià)簇內的稠密程度（簇內差異?。┖痛亻g的離散程度（簇外差異大）來(lái)評估聚類(lèi)的效果。其中輪廓系數是最常用的聚類(lèi)算法的評價(jià)指標。它是對每個(gè)樣本來(lái)定義的，它能夠同時(shí)衡量：
a）樣本與其自身所在的簇中的其他樣本的相似度a，等于樣本與同一簇中所有其他點(diǎn)之間的平均距離。b）樣本與其他簇中的樣本的相似度b，等于樣本與下一個(gè)最近的簇中的所有點(diǎn)之間的平均距離。根據聚類(lèi)“簇內差異小，簇外差異大”的原則，我們希望b永遠大于a，并且大得越多越好。單個(gè)樣本的輪廓系數計算為：

公式進(jìn)行展開(kāi)為：

很容易理解輪廓系數范圍是(-1,1)，其中值越接近1表示樣本與自己所在的簇中的樣本很相似，并且與其他簇中的樣本不相似，當樣本點(diǎn)與簇外的樣本更相似的時(shí)候，輪廓系數就為負。當輪廓系數為0時(shí)，則代表兩個(gè)簇中的樣本相似度一致，兩個(gè)簇本應該是一個(gè)簇。
如果一個(gè)簇中的大多數樣本具有比較高的輪廓系數，簇會(huì )有較高的總輪廓系數，則整個(gè)數據集的平均輪廓系數越高，表明聚類(lèi)是合適的；如果許多樣本點(diǎn)具有低輪廓系數甚至負值，則聚類(lèi)是不合適的，聚類(lèi)的超參數K可能設定得太大或者太小。
輪廓系數有很多優(yōu)點(diǎn)，它在有限空間中取值，使得我們對模型的聚類(lèi)效果有一個(gè)“參考”。并且，輪廓系數對數據的分布沒(méi)有限定，因此在很多數據集上都表現良好，它在每個(gè)簇的分割比較清晰時(shí)表現最好。但輪廓系數也有缺陷，它在凸型的類(lèi)上表現會(huì )虛高，比如基于密度進(jìn)行的聚類(lèi)，或通過(guò)DBSCAN獲得的聚類(lèi)結果，如果使用輪廓系數來(lái)衡量，則會(huì )表現出比真實(shí)聚類(lèi)效果更高的分數。
（2）卡林斯基-哈拉巴斯指數
除了最常用的輪廓系數，還有卡林斯基-哈拉巴斯指數（Calinski-Harabaz Index，簡(jiǎn)稱(chēng)CHI，也被稱(chēng)為方差比標準）、戴維斯-布爾丁指數（Davies-Bouldin）以及權變矩陣（Contingency Matrix）可以使用。在這里不多介紹，感興趣的讀者可以自己學(xué)習。
5. 初始質(zhì)心的問(wèn)題
在K-Means中有一個(gè)重要的環(huán)節，就是放置初始質(zhì)心。如果有足夠的時(shí)間，K-means一定會(huì )收斂，但Inertia可能收斂到局部最小值。是否能夠收斂到真正的最小值很大程度上取決于質(zhì)心的初始化。
初始質(zhì)心放置的位置不同，聚類(lèi)的結果很可能也會(huì )不一樣，一個(gè)好的質(zhì)心選擇可以讓K-Means避免更多的計算，讓算法收斂穩定且更快。在之前講解初始質(zhì)心的放置時(shí)，是采用“隨機”的方法在樣本點(diǎn)中抽取k個(gè)樣本作為初始質(zhì)心，這種方法顯然不符合“穩定且更快”的需求。
為此，在sklearn中使用random_state參數來(lái)實(shí)現控制，確保每次生成的初始質(zhì)心都在相同位置，甚至可以畫(huà)學(xué)習曲線(xiàn)來(lái)確定最優(yōu)的random_state參數。
一個(gè)random_state對應一個(gè)質(zhì)心隨機初始化的隨機數種子。如果不指定隨機數種子，則sklearn中的K-Means并不會(huì )只選擇一個(gè)隨機模式扔出結果，而會(huì )在每個(gè)隨機數種子下運行多次，并使用結果最好的一個(gè)隨機數種子來(lái)作為初始質(zhì)心。
在sklearn中也可以使用參數n_init來(lái)選擇（每個(gè)隨機數種子下運行的次數），可以增加這個(gè)參數n_init的值來(lái)增加每個(gè)隨機數種子下運行的次數。
另外，為了優(yōu)化選擇初始質(zhì)心的方法，“k-means ++”能夠使得初始質(zhì)心彼此遠離，以此來(lái)引導出比隨機初始化更可靠的結果。在sklearn中，使用參數init =‘k-means ++'來(lái)選擇使用k-means++作為質(zhì)心初始化的方案。
6. 聚類(lèi)算法的迭代問(wèn)題
大家都知道，當質(zhì)心不再移動(dòng)，Kmeans算法就會(huì )停下來(lái)。在完全收斂之前，sklearn中也可以使用max_iter（最大迭代次數）或者tol兩個(gè)參數來(lái)讓迭代提前停下來(lái)。有時(shí)候，當n_clusters選擇不符合數據的自然分布，或者為了業(yè)務(wù)需求，必須要填入n_clusters數據提前讓迭代停下來(lái)時(shí)，反而能夠提升模型的表現。
max_iter：整數，默認300，單次運行的k-means算法的最大迭代次數；tol：浮點(diǎn)數，默認1e-4，兩次迭代間Inertia下降的量，如果兩次迭代之間Inertia下降的值小于tol所設定的值，迭代就會(huì )停下。
7. K-Means算法的優(yōu)缺點(diǎn)
（1）K-Means算法的優(yōu)點(diǎn)

• 原理比較簡(jiǎn)單，實(shí)現也是很容易，收斂速度快；
• 聚類(lèi)效果較優(yōu)，算法的可解釋度比較強。

（2）K-Means算法的缺點(diǎn)

• K值的選取不好把握；
• 對于不是凸的數據集比較難收斂；
• 如果各隱含類(lèi)別的數據不平衡，比如各隱含類(lèi)別的數據量嚴重失衡，或者各隱含類(lèi)別的方差不同，則聚類(lèi)效果不佳；
• 采用迭代方法，得到的結果只是局部最優(yōu)；
• 對噪音和異常點(diǎn)比較的敏感。

結論
K均值（K-Means）聚類(lèi)算法原理簡(jiǎn)單，可解釋強，實(shí)現方便，可廣泛應用在數據挖掘、聚類(lèi)分析、數據聚類(lèi)、模式識別、金融風(fēng)控、數據科學(xué)、智能營(yíng)銷(xiāo)和數據運營(yíng)等多個(gè)領(lǐng)域，有著(zhù)廣泛的應用前景。