本文筆者將對聚類算法的基本概念以及常見的幾類基本的聚類算法的運作邏輯以及思路，還有優缺點進行分析。

基本概念

1. 定義

聚類就是對大量未知標注的數據集，按照數據內部存在的數據特征將數據集劃分為多個不同的類別，使類別內的數據比較相似。類別之間的數據相似度比較小，屬于無監督學習。

聚類算法的重點是計算樣本項之間的相似度，有時候也稱為樣本間的距離。

2. 相似度

距離計算公式：

閔可夫斯基距離(Minkowski)：

當p為1的時候是曼哈頓距離(Manhattan)：

當p為2的時候是歐式距離(Euclidean）：

當p為無窮大的時候是切比雪夫距離(Chebyshev)：

夾角余弦相似度(Cosine)：

余弦相似度用向量空間中兩個向量夾角的余弦值，作為衡量兩個個體間差異的大小。相比距離度量，余弦相似度更加注重兩個向量在方向上的差異，而非距離或長度上。

假設兩個向量a，b：

杰卡德相似系數(Jaccard)：

Pearson相關系數：

3. 與分類算法的區別

相同點：

聚類算法和分類算法一樣，都是用于樣本的類別劃分的

不同點：

分類算法是有監督的算法，也就是算法找到是特征屬性x和類別屬性y之間的關系，基于這樣的關系，對樣本數據x做類別的劃分預測

聚類算法是無監督的算法，也就是說訓練數據中只有特征屬性x，沒有類別屬性y，模型是通過找x的特征信息，將數據劃分為不同的類別，基于這樣的劃分，對于樣本數據x認為和那個類別最接近來產生預測。

分類算法的效果要比聚類算法的好，如果可以的情況下，一般選擇分類算法。

4. 常用的聚類算法

KMeans、GMM高斯混合聚類、LDA（主題模型，非聚類算法，但是可以用到聚類中）

5. 聚類算法應用場景

作為前期的數據處理過程的一種數據標注的方式。

基本的聚類算法

主體思想：有M個對象的數據集，構建一個具有k個簇（類別）的模型，其中k<=M。

首先給定初始劃分，通過迭代改變樣本和簇的隸屬關系，使的每次處理后得到的劃分方式比上一次的好(總的數據集之間的距離和變小了)

1. K-means

K-means是一種使用廣泛的最基礎的聚類算法。

1）思路

• 假設輸入樣本為T=X1,X2,…,Xm
• 選擇初始化的k個類別中心a1,a2,…ak
• 對于每個樣本Xi，計算Xi到aj的距離，并將Xi標記為里類別中心aj最近的類比j
• 更新每個類別的中心點aj，用每個類比的所有樣本的均值代替
• 重復上面兩步操作，直到達到某個中止條件
• 終止條件（迭代次數、最小平方誤差MSE(樣本到中心的距離平方和)、簇中心點變化率）

2）計算步驟

記K個簇中心分別為a1,a2,…ak；每個簇的樣本數量為N1,N2,…,NK

使用平方誤差作為目標函數(使用歐幾里得距離)，計算當前劃分情況下，所有樣本到所有中心的距離平方和公式如下：

求解目標函數，我們希望的是在當前劃分情況下，有一組新的a1,a2,…ak，使得MSE最小，對J進行求偏導：

3）優缺點

缺點：

K值是用戶給定的，在進行數據處理前，K值是未知的，不同的K值得到的結果也不一樣；對初始簇中心點是敏感的。

不適合發現非凸形狀的簇或者大小差別較大的簇特殊值（離群值）對模型的影響比較大。

優點：

理解容易，聚類效果不錯處理大數據集的時候，該算法可以保證較好的伸縮性和高效率當簇近似高斯分布的時候，效果非常不錯。

4）K-means存在的問題

問題：K-means算法在迭代的過程中使用所有點的均值作為新的質點(中心點)，如果簇中存在異常點，將導致均值偏差比較嚴重。

初始解決方案：使用中位數6可能比使用均值的想法更好，使用中位數的聚類方式叫做K-Mediods聚類（K中值聚類）。

問題：K-means算法是初值敏感(K值的給定和K個初始簇中心點的選擇)的，選擇不同的初始值可能導致不同的簇劃分規則。

初始解決方案：為了避免這種敏感性導致的最終結果異常性，可以采用初始化多套初始節點構造不同的分類規則，然后選擇最優的構造規則。

2. 二分K-Means

解決K-means初值敏感問題，二分K-Means算法是一種弱化初始質心的一種算法。

1）思路

1. 將所有樣本數據作為一個簇放到一個隊列中。
2. 從隊列中選擇一個簇進行K-means算法劃分，劃分為兩個子簇，并將子簇添加到隊列中。
3. 循環迭代第二步操作，直到中止條件達到(主要是聚簇數量)。
4. 隊列中的簇就是最終的分類簇集合。

2）如何選擇簇進行劃分

a. 對所有簇計算誤差和SSE，選擇SSE最大的聚簇進行劃分操作：

b. 選擇樣本數據量最多的簇進行劃分操作。

3. K-Means++

也是解決K-means初值敏感問題，問題產生原因是K-means算法一個簇中間選擇了兩個中心點，K-Means++算法優化初始的K個中心點的方式，避免上述情況的發生。

1）思路

1. 從數據集中任選一個節點作為第一個聚類中心。
2. 對數據集中的每個點x，計算x到所有已有聚類中心點的距離和D(X)，基于D(X)采用線性概率選擇出下一個聚類中心點（距離較遠的一個點成為新增的一個聚類中心點）。
3. 重復步驟2直到找到k個聚類中心點。

2）缺點

第k個聚類中心點的選擇依賴前k-1個聚類中心點的值，拓展性差。

4. K-Means||

解決K-Means++依賴問題，主要思路是：改變每次遍歷時候的取樣規則，并非按照K-Means++算法每次遍歷只獲取一個樣本，而是每次獲取K個樣本，重復該取樣操作O(logn)次，然后再將這些抽樣出來的樣本聚類出K個點。最后使用這K個點作為K-Means算法的初始聚簇中心點。實踐證明：一般5次重復采用就可以保證一個比較好的聚簇中心點。

5. MiniBatchK-Means

解決K-means算法中每一次都需要計算所有樣本到簇中心的距離。

1）思想

MiniBatchK-Means算法是K-Means算法的一種優化變種，采用小規模的數據子集(每次訓練使用的數據集是在訓練算法的時候隨機抽取的數據子集)減少計算時間，同時試圖優化目標函數；MiniBatchK-Means算法可以減少K-Means算法的收斂時間，而且產生的結果效果只是略差于標準K-Means算法

2）步驟

1. 首先抽取部分數據集，使用K-Means算法構建出K個聚簇點的模型。
2. 繼續抽取訓練數據集中的部分數據集樣本數據，并將其添加到模型中，分配給距離最近的聚簇中心點。
3. 更新聚簇的中心點值（每次更新都只用抽取出來的部分數據集）。
4. 循環迭代第二步和第三步操作，直到中心點穩定或者達到迭代次數，停止計算操作。

衡量指標

混淆矩陣、均一性、完整性、V-measure、蘭德系數(ARI)、互信息(AMI)、輪廓系數(Silhouette)

均一性

一個簇中只包含一個類別的樣本，則滿足均一性；其實也可以認為就是正確率（每個聚簇中正確分類的樣本數占該聚簇總樣本數的比例和）

完整性

同類別樣本被歸類到相同簇中，則滿足完整性；每個聚簇中正確分類的樣本數占該類型的總樣本數比例的和：

V-measure

均一性和完整性的加權平均：

Rand index(蘭德指數)(RI)

其中C表示實際類別信息，K表示聚類結果，a表示在C與K中都是同類別的元素對數。

b表示在C與K中都是不同類別的元素對數，表示數據集中可以組成的對數。

調整蘭德系數(ARI，Adjusted Rnd Index)

ARI取值范圍[-1,1]，值越大，表示聚? 類結果和真實情況越吻合。從廣義的角度來將，ARI是衡量兩個數據分布的吻合程度：

本文由 @SincerityY 原創發布于人人都是產品經理。未經許可，禁止轉載

題圖來自Unsplash，基于CC0協議