聚類是機器學習中一種重要的無監(jiān)督算法，可以將數(shù)據(jù)點歸結(jié)為一系列的特定組合。歸為一類的數(shù)據(jù)點具有相同的特性，而不同類別的數(shù)據(jù)點則具有各不相同的屬性。

11.1 聚類算法介紹

人們將物理或抽象對象的集合分成由類似 的對象組成的多個類的過程被稱為聚類。

11.1.1 聚類是什么

聚類和降維之間有著共通性， 某種意義上聚類就是降維，聚成 K 類就意味著將原來的數(shù)據(jù)降為 K 維。分類與聚類雖然名稱較為接近但兩者截然不同，分類是有監(jiān)督學習中的典型問題，而聚類則是無監(jiān)督學習中的典型問題。

11.1.2 聚類算法應(yīng)用場景

11.2 通俗講解聚類算法過程

聚類算法是無監(jiān)督學習的典型算法，其中 K-means 算法又是聚類算法中的經(jīng)典算法。 K-means 算法要求預先設(shè)定聚類的個數(shù)，然后不斷更新聚類中心，通過多次迭代最終使得所有數(shù)據(jù)點到其聚類中心距離的平方和趨于穩(wěn)定。

一般來說，K-means 聚類過程如下所示。

(1)從 n 個向量對象中任意選擇 K 個對象作為初始聚類中心。

(2)根據(jù)步驟(1)中設(shè)置的 K 個聚類中心，分別計算每個對象與這 K 個聚類中心對象的距離。

(3)經(jīng)過步驟(2)后，任何一個對象與這 K 個聚類中心都有一個距離值。這些距離有的遠， 有的近，將對象與距離它最近的聚類中心歸為一類。

(4)重新計算每個類簇的聚類中心。 (5)重復步驟(3)和步驟(4)，直到對象歸類變化量極小或者完全停止變化。例如，某次

迭代后只有不到 1% 的對象還會出現(xiàn)類簇之間的歸類變化，就可以認為聚類算法實現(xiàn)了。

有兩個需要注意的關(guān)鍵點:一是對象距離如何度量;二是聚類效果如何評估，也就是性能如何度量。

11.2.1 相似度如何度量

“相似度”就是通過距離來表示。最常見的距離是“閔可夫斯基距離”：

除了常用的閔可夫斯基距離之外，還有雅卡爾相似系數(shù)、余弦相似度、相對熵、黑林格距

離等多種距離計算方法。

11.2.2 聚類性能如何度量

(1)數(shù)據(jù)含有標記信息。使用調(diào)整蘭德系數(shù)(Adjusted Rand Index，ARI)指標。ARI 指標和分類問題中的準確率指標比較類似，在 sklearn 的 metrics 里面就可以調(diào)用。

(2)數(shù)據(jù)不含標記信息。使用輪廓系數(shù)來度量聚類效果。輪廓系數(shù)具有兼顧聚類的凝聚度和分離度的優(yōu)點，數(shù)值為 [-1,1]。一般來說，輪廓系數(shù)越大，聚類效果越好。輪廓系數(shù)可以通過在 sklearn 的 metrics 中調(diào)用 silhouette_score 來實現(xiàn)。

11.2.3 具體算法介紹:K-means算法

對于 K-means 算法 中 K 的選取，目前有一種稱為“Elbow Method”的方法來處理:通過繪制 K-means 代價函數(shù)與 聚類數(shù)目 K 的關(guān)系圖，選取直線拐點處的 K 值作為最佳的聚類中心數(shù)目。

但實際中更為常見和提倡的做法還是算法工程師從實際問題出發(fā)人工指定合理的 K 值，通過多次隨機初始化聚類中心選取比較滿意的結(jié)果。

K-means 算法是初值敏感的，也就是起始時選擇不同的點作為質(zhì)心，最后得到的聚類結(jié)果 可能是不同的。K-means++ 算法就此問題進行了改進。

11.2.4 具體算法介紹:K-means++算法

K-means++ 算法的核心思想是，初始質(zhì)心并不隨機選取，而是希望這 K 個初 始質(zhì)心相互之間分得越開越好。

計算每個樣本點與當前已有質(zhì)心的最短距離(即與最近一個質(zhì)心的距離)，用表示;接著計算每個樣本點被選中作為下一個質(zhì)心的概率，用表示。值越大表示該點被選為質(zhì)心的概率越大。這個用概率選取質(zhì)心的方法就是輪盤法。

輪盤法

我們來看一下如何根據(jù)權(quán)重來確定概率，實現(xiàn)這點的算法有很多，其中比較簡單的是輪盤法。這個算法應(yīng)該源于賭博或者是抽獎，原理也非常相似。

我們或多或少都玩過超市或者是其他場景下的轉(zhuǎn)盤抽獎，在抽獎當中有一個指針一直保持不動。我們轉(zhuǎn)動轉(zhuǎn)盤，當轉(zhuǎn)盤停下的時候，指針所指向的位置就是抽獎的結(jié)果。

我們都知道命中結(jié)果的概率和輪盤上對應(yīng)的面積有關(guān)，面積越大抽中的概率也就越大，否則抽中的概率越小。

我們用公式表示一下，對于每一個點被選中的概率是：

其中是每個點到所有類簇的最短距離，表示點被選中作為類簇中心的概率。

輪盤法其實就是一個模擬轉(zhuǎn)盤抽獎的過程，只不過我們用數(shù)組模擬了轉(zhuǎn)盤。我們把轉(zhuǎn)盤的扇形拉平，拉成條狀，原來的每個扇形就對應(yīng)了一個區(qū)間。扇形的面積就對應(yīng)了區(qū)間的長度，顯然長度越長，抽中的概率越大。然后我們來進行抽獎，我們用區(qū)間的長度總和乘上一個0-1區(qū)間內(nèi)的數(shù)。

我們找到這個結(jié)果落在的區(qū)間，就是這次輪盤抽中的結(jié)果。這樣我們就實現(xiàn)了控制隨機每個結(jié)果的概率。

在上面這張圖當中，我們隨機出來的值是0.68，然后我們一次減去區(qū)間，最后落到的區(qū)間。

11.3 編程實踐:手把手教你寫代碼

參考：

詳解Kmeans的兩大經(jīng)典優(yōu)化，mini-batch和kmeans++-騰訊云開發(fā)者社區(qū)-騰訊云