機器學習 | 關於聚類演算法，你知道多少？
本文筆者將對聚類演算法的基本概念以及常見的幾類基本的聚類演算法的運作邏輯以及思路，還有優缺點進行分析。
基本概念
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）思路
- 將所有樣本資料作為一個簇放到一個佇列中。
- 從佇列中選擇一個簇進行K-means演算法劃分，劃分為兩個子簇，並將子簇新增到佇列中。
- 迴圈迭代第二步操作，直到中止條件達到(主要是聚簇數量)。
- 佇列中的簇就是最終的分類簇集合。
2）如何選擇簇進行劃分
a. 對所有簇計算誤差和SSE，選擇SSE最大的聚簇進行劃分操作：
b. 選擇樣本資料量最多的簇進行劃分操作。
3. K-Means++
也是解決K-means初值敏感問題，問題產生原因是K-means演算法一個簇中間選擇了兩個中心點，K-Means++演算法優化初始的K箇中心點的方式，避免上述情況的發生。
1）思路
- 從資料集中任選一個節點作為第一個聚類中心。
- 對資料集中的每個點x，計算x到所有已有聚類中心點的距離和D(X)，基於D(X)採用線性概率選擇出下一個聚類中心點（距離較遠的一個點成為新增的一個聚類中心點）。
- 重複步驟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）步驟
- 首先抽取部分資料集，使用K-Means演算法構建出K個聚簇點的模型。
- 繼續抽取訓練資料集中的部分資料集樣本資料，並將其新增到模型中，分配給距離最近的聚簇中心點。
- 更新聚簇的中心點值（每次更新都只用抽取出來的部分資料集）。
- 迴圈迭代第二步和第三步操作，直到中心點穩定或者達到迭代次數，停止計算操作。
衡量指標
混淆矩陣、均一性、完整性、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協議