本文筆者將對聚類算法的基本概念以及常見的幾類基本的聚類算法的運(yùn)作邏輯以及思路，還有優(yōu)缺點(diǎn)進(jìn)行分析。

基本概念

1. 定義

聚類就是對大量未知標(biāo)注的數(shù)據(jù)集，按照數(shù)據(jù)內(nèi)部存在的數(shù)據(jù)特征將數(shù)據(jù)集劃分為多個不同的類別，使類別內(nèi)的數(shù)據(jù)比較相似。類別之間的數(shù)據(jù)相似度比較小，屬于無監(jiān)督學(xué)習(xí)。

聚類算法的重點(diǎn)是計(jì)算樣本項(xiàng)之間的相似度，有時候也稱為樣本間的距離。

2. 相似度

距離計(jì)算公式：

閔可夫斯基距離(Minkowski)：

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

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

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

夾角余弦相似度(Cosine)：

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

假設(shè)兩個向量a，b：

杰卡德相似系數(shù)(Jaccard)：

Pearson相關(guān)系數(shù)：

3. 與分類算法的區(qū)別

相同點(diǎn)：

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

不同點(diǎn)：

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

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

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

4. 常用的聚類算法

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

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

作為前期的數(shù)據(jù)處理過程的一種數(shù)據(jù)標(biāo)注的方式。

基本的聚類算法

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

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

1. K-means

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

1）思路

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

2）計(jì)算步驟

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

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

求解目標(biāo)函數(shù)，我們希望的是在當(dāng)前劃分情況下，有一組新的a1,a2,…ak，使得MSE最小，對J進(jìn)行求偏導(dǎo)：

3）優(yōu)缺點(diǎn)

缺點(diǎn)：

K值是用戶給定的，在進(jìn)行數(shù)據(jù)處理前，K值是未知的，不同的K值得到的結(jié)果也不一樣；對初始簇中心點(diǎn)是敏感的。

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

優(yōu)點(diǎn)：

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

4）K-means存在的問題

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

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

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

初始解決方案：為了避免這種敏感性導(dǎo)致的最終結(jié)果異常性，可以采用初始化多套初始節(jié)點(diǎn)構(gòu)造不同的分類規(guī)則，然后選擇最優(yōu)的構(gòu)造規(guī)則。

2. 二分K-Means

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

1）思路

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

2）如何選擇簇進(jìn)行劃分

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

b. 選擇樣本數(shù)據(jù)量最多的簇進(jìn)行劃分操作。

3. K-Means++

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

1）思路

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

2）缺點(diǎn)

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

4. K-Means||

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

5. MiniBatchK-Means

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

1）思想

MiniBatchK-Means算法是K-Means算法的一種優(yōu)化變種，采用小規(guī)模的數(shù)據(jù)子集(每次訓(xùn)練使用的數(shù)據(jù)集是在訓(xùn)練算法的時候隨機(jī)抽取的數(shù)據(jù)子集)減少計(jì)算時間，同時試圖優(yōu)化目標(biāo)函數(shù)；MiniBatchK-Means算法可以減少K-Means算法的收斂時間，而且產(chǎn)生的結(jié)果效果只是略差于標(biāo)準(zhǔn)K-Means算法

2）步驟

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

衡量指標(biāo)

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

均一性

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

完整性

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

V-measure

均一性和完整性的加權(quán)平均：

Rand index(蘭德指數(shù))(RI)

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

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

調(diào)整蘭德系數(shù)(ARI，Adjusted Rnd Index)

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

本文由 @SincerityY 原創(chuàng)發(fā)布于人人都是產(chǎn)品經(jīng)理。未經(jīng)許可，禁止轉(zhuǎn)載

題圖來自Unsplash，基于CC0協(xié)議