聚類的概念
對于有標(biāo)簽的數(shù)據(jù)，我們進(jìn)行有監(jiān)督學(xué)習(xí)，常見的分類任務(wù)就是監(jiān)督學(xué)習(xí)；而對于無標(biāo)簽的數(shù)據(jù)，我們希望發(fā)現(xiàn)無標(biāo)簽的數(shù)據(jù)中的潛在信息，這就是無監(jiān)督學(xué)習(xí)。聚類，就是無監(jiān)督學(xué)習(xí)的一種，它的概念是：將相似的對象歸到同一個簇中，使得同一個簇內(nèi)的數(shù)據(jù)對象的相似性盡可能大，同時不在同一個簇中的數(shù)據(jù)對象的差異性也盡可能地大。即聚類后同一類的數(shù)據(jù)盡可能聚集到一起，不同數(shù)據(jù)盡量分離。

聚類算法的分類
聚類算法有很多種分法，體系也很大，這里舉例幾種分法：

基于劃分的聚類：聚類目標(biāo)是使得類內(nèi)的點足夠近，類間的點足夠遠(yuǎn)，常見的如k-means及其衍生算法

基于密度的聚類：當(dāng)鄰近區(qū)域的密度超過某個閾值，則繼續(xù)聚類，如DBSCAN; OPTICS

層次聚類：這個下面會具體介紹到，包括合并的層次聚類，分裂的層次聚類，實際上可以看作是二叉樹的生成和分裂過程。下面會介紹實際應(yīng)用中常用的HDBSCAN

基于圖的聚類： 通過建圖來進(jìn)行聚類，這是聚類算法中的大頭，很多較新的聚類算法都有圖聚類的思想。這篇文章會介紹以Chinese Whisper，譜聚類兩大具有代表性的圖聚類算法

基于GCN（圖神經(jīng)網(wǎng)絡(luò)）的聚類：實際上這個本質(zhì)上也是基于圖的聚類，然而基于GCN的聚類算法會有深度學(xué)習(xí)中的訓(xùn)練的概念，而傳統(tǒng)的聚類算法則是通過人工設(shè)定閾值來決定的，所以這里也分開列了一類， 這篇文章會介紹《Learning to Cluster Faces on Affinity Graph》、CDP兩篇論文的思想

…

其實還有很多分類，但這里不再列舉了，有興趣的同學(xué)可以參考sklearn文檔中關(guān)于聚類的劃分 https://scikit-learn.org/stable/modules/clustering.html#clustering

K-Means
這個可以說是最基礎(chǔ)的聚類算法了，它的輸入需要簇的個數(shù)k，這個k是用戶指定的，也就是說需要提前確定類別，其算法流程是：

隨機(jī)確定k個初始點u1, u2…uk作為聚類質(zhì)心
重復(fù)以下過程直到收斂：
對于每一個樣例，找到離它最近的質(zhì)心作為label：

對于每一個類j, 更新其質(zhì)心：
[公式]

優(yōu)點: 速度快

缺點:

必須提前知道"k"， 也就是有多少個簇
容易陷入局部最優(yōu)
數(shù)據(jù)必須符合“數(shù)據(jù)之間的相似度可以使用歐式距離衡量”，這個是什么意思呢，看下圖，這種數(shù)據(jù)的分布，樣本點的距離不能簡單地用歐式距離來衡量，否則分類效果會非常差。這里的距離衡量應(yīng)該是“測地距離”，也就是樣本沿著曲面到達(dá)另一個樣本點的距離。如果在這種數(shù)據(jù)空間想要使用kmeans，必須先進(jìn)行空間的轉(zhuǎn)化

k-means有一些改進(jìn)算法，多是針對k-means會受異常點的影響這一點來改進(jìn)的，比如K-Means++, K-Medians…

基于密度的算法-DBSCAN
基于密度的算法，要求聚類空間的一定區(qū)域所包含的對象的數(shù)目不小于某一給定閾值，先了解一些基本概念：

（1）Eps鄰域：給定對象半徑Eps內(nèi)的鄰域稱為該對象的Eps鄰域;

（2）核心對象（core point）：如果對象的Eps鄰域至少包含最小數(shù)目MinPts的對象，則稱該對象為核心對象;

（3）直接密度可達(dá)(directly density-reachable)：若某點p在點的q的Eps領(lǐng)域內(nèi)，且q是一個核心對象，則p-q直接密度可達(dá)

（4）密度可達(dá)(density-reachable)：如果存在一個對象鏈 p1, …,pi,…, pn，如果對于任意pi, pi-1都是直接密度可達(dá)的，則稱pi到pi-1密度可達(dá)，實際上是直接密度可達(dá)的傳播鏈

（5）密度相連(density-connected)：如果從某個核心對象p出發(fā)，點q和點k都是密度可達(dá)的，則稱點q和k是密度相連的。

（6）邊界點（edge point）：邊界點不是核心對象，但落在某個核心對象的鄰域內(nèi);

（7）噪音點（outlier point）：既不是核心點，也不是邊界點的任何點;

看看上圖，紅色點是所謂的核心對象，以它為圓心，Eps為半徑去畫圓，在圓內(nèi)樣本點數(shù)目大于MinPts的就是核心對象；被包含在核心對象的范圍內(nèi)，但是自身不是核心對象的點是樣本點；即不被包含在核心對象內(nèi)，自身也不是核心對象的點為噪音點，將被拋棄。

DBSCAN的核心思想是從某個核心點出發(fā)，不斷向密度可達(dá)的區(qū)域擴(kuò)張，從而得到一個包含核心點和邊界點的最大化區(qū)域，區(qū)域中任意兩點密度相連。現(xiàn)在我們來看看DBSCAN的一個算法流程，會更容易理解：

輸入：給定點在領(lǐng)域內(nèi)成為核心對象的最小領(lǐng)域點數(shù)(MinPts), 領(lǐng)域半徑: Eps

輸出：簇集合

首先將數(shù)據(jù)集D中所有的對象標(biāo)記為未處理狀態(tài)：
對數(shù)據(jù)集D中的每個對象p：
if p已經(jīng)歸入了某個簇:
continue
else:
檢查對象p的Eps領(lǐng)域 NEps§
if NEps§包含的對象數(shù)小于MinPts:
標(biāo)記對象p為邊界點或者噪聲點；
else:
標(biāo)記對象p為核心點，并建立新簇C，將p領(lǐng)域內(nèi)的所有點加入C
for (NEPs§中所有尚未處理的對象q):
檢查對象q的領(lǐng)域NEps(q), 若NEps(q)包含至少MInPts個對象，則將NEps(q)中未歸入
任何一個簇的對象加入C
優(yōu)點：

不需要指定簇的數(shù)目（不需要 k）
可以發(fā)現(xiàn)任意形狀的聚類簇
對噪聲不敏感

從這張圖中kmeans和DBSCAN的對比可以看出DBSCAN對這種數(shù)據(jù)分布的擬合更好
缺點：

需要設(shè)置半徑Eps和MinPts, 空間聚類密度不均勻時難以設(shè)置參數(shù)，所以有一個問題就是，在數(shù)據(jù)集A上挑好的參數(shù)很可能到數(shù)據(jù)集B上就不能用了
隨著數(shù)據(jù)量的增大，計算量顯著增大，反正大規(guī)模數(shù)據(jù)集用DBSCAN很可能會崩的
層次密度聚類 HDBSCAN
這是一個對DBSCAN的改進(jìn)算法，結(jié)合了密度聚類和層次聚類。它的優(yōu)化點主要如下：

使用相互可達(dá)距離替換歐氏距離，該距離可以使得密度低的點離密度高的區(qū)域更遠(yuǎn)，減少dbscan對Eps閾值的依賴性
使用最小生成樹構(gòu)建層次聚類模型，引入層次聚類思想
對最小生成樹的最小子樹做了限制，減少計算量，同時保證生成的類簇不要過小
使用“簇穩(wěn)定性”的度量方式自動劃分類簇，不需要自行設(shè)定閾值
這里面有一些專業(yè)術(shù)語可能一看起來不太能明白，我們來逐一解釋。

可達(dá)距離

可達(dá)距離是對DBSCAN中核心距離的一個改進(jìn)版，也是DBSCAN的改進(jìn)算法OPTICS的主要核心思想，也就是通過改變距離的度量方式減少dbscan對閾值Eps的敏感性；該距離可以讓稀疏的點離密度高的區(qū)域更遠(yuǎn)。了解可達(dá)距離之前，我們先看看核心距離：

核心距離：對于給定的樣本點，使得該點成為核心點的最小Eps為該點的核心距離。假設(shè)樣本點為p, 找到以p為圓心，剛好滿足minPts的最外層的點q，則p和q的距離為核心距離；看下圖，加入我們的MinPts設(shè)為3，那么找到以紅色點P為圓心，MinPts正好為3的半徑 [公式] 即為核心距離

可達(dá)距離：對于樣本點p周圍的點q1,q2…,1n,如果這些點到點p的距離大于p的核心距離，則可達(dá)距離為該點到p的實際距離；如小于，則可達(dá)距離為點x的核心距離。我們繼續(xù)看上圖，點1,2，3的可達(dá)距離均為核心距離，而在核心距離之外的點4， 5， 它們到點P的距離仍然是歐式距離。那么為什么要用可達(dá)距離替換歐氏距離呢？我們看看下面這張圖就知道了，下圖中，藍(lán)色核心點和綠色核心點原本的距離應(yīng)該是兩點的歐氏距離，但是因為藍(lán)色核心點在綠色核心點的核心距離內(nèi)，所以此時它們的可達(dá)距離為綠色核心點的半徑>兩點的歐氏距離，相當(dāng)于把藍(lán)色核心點和綠色核心點區(qū)分開了；紅色核心點到藍(lán)色核心點的距離一樣，它們的可達(dá)距離要大于藍(lán)色核心點和紅色核心點的實際距離，這樣以藍(lán)色核心點為代表的高密度區(qū)域與紅色核心點、綠色核心點的低密度區(qū)域就被推開了；而綠色核心點和紅色核心點的距離則依舊是它們的歐氏距離。

層次聚類

要理解HDBSCAN，首先要搞清楚層次聚類到底是什么。層次聚類有自上而下的方式和自下而上的方式。在這里我們只介紹自下而上的方式，也就是HDBSCAN算法中用到的方式。

假設(shè)有 n 個待聚類的樣本
（初始化）將每個樣本都視為一個簇；
計算各個聚類之間的相似度；
尋找最近的兩個聚類，將他們歸為一類；
重復(fù)步驟二，步驟三；直到所有樣本歸為一類。

其實就是一個不斷歸一化最后歸成一類的過程。實際上層次不同的層次聚類算法考慮的主要是相似度的衡量方式和終止聚類的條件的不同。相似度的衡量方式?jīng)Q定了哪些樣本將被聚到一起，而中止聚類的條件決定了選擇哪一層級的類別作為最終的聚類輸出。

而HDBSCAN是以可達(dá)距離作為領(lǐng)接邊權(quán)重，對所有節(jié)點構(gòu)建最小生成樹，之后進(jìn)行層次聚類

簇壓縮

我們將HDBSCAN的樣本點進(jìn)行層次聚類，構(gòu)造成上面的生成樹圖之后，HDBSCAN會進(jìn)行一個壓縮樹的過程。它的原理是，對于我們生成的最小生成樹，從上往下遍歷，在一個簇被劃分為兩個子簇的過程中，如果子簇的樣本點數(shù)量小于設(shè)定的最小值（也就是前面可達(dá)距離的概念中設(shè)置的MinPts，那么這個小于MinPts的子簇將會不會被保留，子簇中的樣本將作為-1類被刪除。

簇選擇

在聚類的簇完成簇壓縮的過程后，此時我們得到了一個更小的最小生成樹，此時，我們需要開始決定保留那些簇作為我們的類。對于DBSCAN算法來說，實際上是在某個閾值下畫了一條線，來決定選取哪些類作為聚類類別。

DBSCAN的簇選擇方式
而HDBSCAN使用了一個簇穩(wěn)定性的概念。

定義s為簇穩(wěn)定性，其計算方式如下：

實際上是說，我們可以將 [公式] 看作是一個相似度，而簇穩(wěn)定性則是說，在不同的 [公式] 的取值下，有一些簇會被合并為一個更大的簇，此時我們說這些被合并的簇“消失了”，而在一個 [公式] 值更小的時候，也就是相似度更低，不那么嚴(yán)格的情況下，這些簇剛剛被它們的子簇合并出來。也就是說，簇穩(wěn)定性定義的是這些簇從第一次出現(xiàn)到被合并進(jìn)更高層次的的簇的范圍，代表著這個簇的生存周期。在做簇選擇的時候，實際上要選擇那些簇穩(wěn)定性最高的簇。那么選擇原則就是：

如果當(dāng)前節(jié)點的穩(wěn)定性大于兩個子節(jié)點的簇穩(wěn)定性，將當(dāng)前節(jié)點作為提取簇，不再提取其子節(jié)點；如果當(dāng)前節(jié)點的穩(wěn)定性小于兩個子節(jié)點的穩(wěn)定性總和，將該節(jié)點設(shè)置為其子節(jié)點的穩(wěn)定性之和

上圖中，只選擇了簇穩(wěn)定性最高的簇
到這里，整個HDBSCAN的算法就介紹完了。

優(yōu)點：

不需要自行設(shè)置閾值，只需定義最小簇的數(shù)量

計算消耗相對小，速度較快（使用最小生成樹建圖，并使用了簇壓縮)

參數(shù)敏感度較低

基于Graph的聚類算法–Chinese Whisper
下面說到基于Graph的聚類算法，這種類型的算法實際應(yīng)用效果比較好，還挺重要的。其中代表的基礎(chǔ)算法Chinese Whisper還挺簡單的：

初始化：將所有的樣本點初始化為不同的類，自下而上的進(jìn)行聚類

建圖：根據(jù)樣本點之間的距離，設(shè)定相似度，低于相似度閾值的兩個樣本點之間建立邊，高于閾值則無邊，由此構(gòu)建加權(quán)無向圖，邊的權(quán)重為相似度

迭代：

隨機(jī)選取一個節(jié)點i開始，在其相連節(jié)點中選取邊權(quán)重最大者j, 并將i歸為節(jié)點j類（若相連節(jié)點中有多個節(jié)點屬于同一類，則將這些權(quán)重相加再做比較）

遍歷所有節(jié)點后，重復(fù)迭代至滿足迭代次數(shù)

優(yōu)點：不用設(shè)定k，只需指定相似度閾值

缺點：

對向量的要求度較高，需要向量能夠增大類間距離，減小類內(nèi)距離

由于隨機(jī)初始化，每次聚類的結(jié)果有可能不一致

中間的節(jié)點可能被歸到任何一類，由于隨機(jī)初始化
改進(jìn)：

CW需要自行設(shè)置相似度閾值，且該閾值敏感度較高，后續(xù)優(yōu)化方向是自動選擇閾值，有興趣可以參考下面這篇論文：

Linkage Based Face Clustering via GCN（CVPR2019）

譜聚類是相對來說比較復(fù)雜的一個聚類算法，所以這里也不詳細(xì)展開說了，大概說一下它的原理：它解決的問題是kmeans中無法對非歐式空間的分布進(jìn)行聚類的問題，主要原理是對聚類數(shù)據(jù)進(jìn)行變換，然后進(jìn)行k-means聚類，之后再還原到原空間。

算法思路：它的主要思想是把所有的數(shù)據(jù)看做空間中的點，這些點之間可以用邊連接起來。距離較遠(yuǎn)的兩個點之間的邊權(quán)重值較低，而距離較近的兩個點之間的邊權(quán)重值較高，通過對所有數(shù)據(jù)點組成的圖進(jìn)行切圖，讓切圖后不同的子圖間邊權(quán)重和盡可能的低，而子圖內(nèi)的邊權(quán)重和盡可能的高，從而達(dá)到聚類的目的。

譜聚類的流程是：

輸入：n個樣本, 類別k

根據(jù)輸入的相似度的衡量方式對樣本建圖，根據(jù)相似圖建立鄰接矩陣W
計算出拉普拉斯矩陣L, 其中L=D-W， D為度矩陣
計算L的最小的k個特征向量u1, u2,…,uk（此步相當(dāng)于降維),將這些向量組成為n*k維的矩陣U
將U中的每一行作為一個樣本，共n個樣本，使用k-means對這n個樣本進(jìn)行聚類
得到簇劃分C(c1,c2,…ck).
這里的拉普拉斯、度矩陣的推斷都需要一定篇幅，之前寫過一篇譜聚類的算法原理，有興趣可移步至：

譜聚類的原理和優(yōu)化目標(biāo)

這里只簡單介紹幾個概念：

鄰接矩陣：

鄰接矩陣是聚類中經(jīng)常聽到的一個概念，實際上是表示定點之間相鄰關(guān)系的矩陣，也就是其實可以看作一個表格，每個元素代表兩個點的關(guān)聯(lián)程度

最小割

最小割是指去掉圖中的一些帶權(quán)邊，在使得圖從聯(lián)通圖變?yōu)椴宦?lián)通圖的前提下，盡可能的讓去掉的邊權(quán)值之和盡可能小。對于數(shù)據(jù)的相似性圖來說，最小割就是要去除一些很弱的相似性，把數(shù)據(jù)點從一個互相連接的整體分為兩個或者多個獨立的部分，這其實就是一個聚類的過程

具體的最小割的優(yōu)化可參見：譜聚類的原理和優(yōu)化目標(biāo)

優(yōu)點：在算法中使用了降維，對于高維空間效果較好

缺點：

如果向量維度過高，而降維的幅度不夠，則最后的聚類效果與運行速度均不好

需要提前知道k

不同的領(lǐng)接矩陣的聚類結(jié)果可能不一樣

最新
這里再介紹兩篇比較新的論文，也可以看作是未來聚類的一個發(fā)展趨勢。在現(xiàn)在萬物皆可深度學(xué)習(xí)的潮流下，如今的聚類也開始向GNN（圖神經(jīng)）網(wǎng)絡(luò)的方向去發(fā)展了。

基于GNN的聚類
GNN這塊的話，其實簡單來說，我們知道CNN的輸入是圖片，RNN的輸入是文本或者語音等序列，而GNN的輸入則是圖。實際上走的都是深度學(xué)習(xí)梯度下降的優(yōu)化路線， 只是不同網(wǎng)絡(luò)的輸入不一樣而已。

Learning to Cluster Faces on Affinity Graphy(CVPR2019)
第一篇paper就是基于圖神經(jīng)網(wǎng)絡(luò)（GCN）的聚類算法

算法流程（級聯(lián)式的算法流程，類似mtcnn)：

將樣本點建圖(如何建圖可以參照前面圖聚類算法，實際上有很多種構(gòu)建方式，主要取決于相似度如何衡量以及如何建邊）

Cluster Proposal:從前面建好的圖中選擇出多個sub-graph，也就是proposal，就是子圖的概念。（這里其實和Faster RCNN等檢測網(wǎng)絡(luò)有些像），這一步實際上主要是為了降低計算消耗，我們不在一整幅圖上去做聚類，而是在子圖上去做。每一個cluster proposal里的向量數(shù)是比較少的。比如說一個包含1M向量的全圖可以轉(zhuǎn)化為50K包含20向量的proposal

Cluster Detection: 將上面的Cluster Proposal利用GCN提取特征后聚類，計算預(yù)測類別與gt的差異，評價指標(biāo)為：

這個IoU目標(biāo)檢測的同學(xué)應(yīng)該很熟了，原理是類似的，總之是用這個指標(biāo)來進(jìn)行訓(xùn)練

Cluster Segmentation: 上面那個模塊是檢測，這個模塊是剔除負(fù)樣本點，評價指標(biāo)和上面那一步是一樣的。使用的loss均為MSE，訓(xùn)練然后梯度下降

這篇文章中還用到了Ablation Study，這也算是近年來Paper必備的一個部分吧。可以參考

Affinity Graph: Graph在半監(jiān)督學(xué)習(xí)和聚類上經(jīng)常出現(xiàn)。Affinity graph的節(jié)點是數(shù)據(jù)樣本，邊代表數(shù)據(jù)之間的相似度。

標(biāo)題的Affinity Graphy也是在半監(jiān)督學(xué)習(xí)中經(jīng)常出現(xiàn)的一個術(shù)語，實際上就是指節(jié)點代表數(shù)據(jù)樣本，邊代表數(shù)據(jù)之間相似度的圖。

CDP(ECCV2018)
這一篇是針對人臉識別提出的優(yōu)化算法，解決的是在大數(shù)據(jù)集下傳統(tǒng)算法聚類性能過差的問題

級聯(lián)模型的思想，想象一下mtcnn。

流程：

該算法有3個部分，base model, committe model(決策者模型)和Mediator(融合模型), 其實就是base model建一個大圖，多個簡單的committe model對大圖進(jìn)行斷邊，Mediator根據(jù)多個committe的結(jié)果來判斷兩個節(jié)點之間的邊是保留還是斷開。

base model： 建knn圖

Committe model: 多個committe model對base model建的圖，對每一條邊，判斷其是否應(yīng)該斷開，輸出多個子圖

Mediator: 集成committe輸出的pairs的關(guān)系，最終輸出聚類結(jié)果。看下圖，假設(shè)我們有6個committe model, 對于節(jié)點1和節(jié)點2的邊，所有的committe model均判斷其有邊，則保留邊；對于節(jié)點4,8，6個model中有四個committe model將其斷開，則mediator將其斷開，最后就會是節(jié)點4和節(jié)點8在不同的cluster中。

各個模塊都是使用GCN來訓(xùn)練，而非設(shè)置閾值

優(yōu)點： 只探索局部關(guān)系，因為它的主要計算量集中在兩個節(jié)點組成的pairs的關(guān)系，而不是整個圖的關(guān)系，計算效率較高，可以用于大規(guī)模數(shù)據(jù)集

聚類算法選型
下面是一點個人經(jīng)驗，如何進(jìn)行聚類算法選型

?特征：聚類算法達(dá)到瓶頸時，應(yīng)該優(yōu)化特征，減少類內(nèi)距離，增大類間距離；對于雜質(zhì)較多的特征，需要采取一定的過濾措施：如根據(jù)圖像質(zhì)量、光照、模糊、內(nèi)容識別等進(jìn)行過濾

?參數(shù)配置：實際應(yīng)用中能否知道“k”，如果不能，k-means和譜聚類就不能用

?性能: 聚類算法往往涉及兩兩計算相似度，如果算法不做優(yōu)化時間消耗可能很大，常見優(yōu)化如使用向量運算替換循環(huán)；像一些沒有經(jīng)過計算效率優(yōu)化的算法，如DBSCAN，其實在大規(guī)模數(shù)據(jù)集上是用不了的

?參數(shù)敏感度：聚類時需要考慮參數(shù)敏感度的分析，如果算法對參數(shù)過于敏感，可以尋找是否有基于當(dāng)前算法的參數(shù)自調(diào)整算法；

總結(jié)

以上是生活随笔為你收集整理的常用聚类算法综述的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。