原創 | 一文讀懂K均值（K-Means）聚類算法

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

K-Means詳解
1. K-Means的工作原理
作為聚類算法的典型代表，K-Means可以說是最簡單的聚類算法，那它的聚類工作原理是什么呢？

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

圖1  K-Means算法計算過程

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

解：

正在進行第1次迭代初始質心為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])]所以第一簇的質心為F：[-4.433409 -2.543268]第二簇的質心為G：[ 0.029122 -3.6329615]第三簇的質心為H：[-3.45368 3.424321]###########################################################正在進行第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])]所以第一簇的質心為：[-4.433409 -2.543268]第二簇的質心為：[ 0.029122 -3.6329615]第三簇的質心為：[-3.45368 3.424321]###########################################################由于三個簇的成員保持不變，聚類結束

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

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

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

公式進行展開為：

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

• 原理比較簡單，實現也是很容易，收斂速度快；
• 聚類效果較優，算法的可解釋度比較強。

（2）K-Means算法的缺點

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

結論
K均值（K-Means）聚類算法原理簡單，可解釋強，實現方便，可廣泛應用在數據挖掘、聚類分析、數據聚類、模式識別、金融風控、數據科學、智能營銷和數據運營等多個領域，有著廣泛的應用前景。