層次聚類算法原理總結(jié)

點(diǎn)擊上方“小白學(xué)視覺”，選擇加"星標(biāo)"或“置頂”

重磅干貨，第一時(shí)間送達(dá)

層次聚類(hierarchical clustering)基于簇間的相似度在不同層次上分析數(shù)據(jù)，從而形成樹形的聚類結(jié)構(gòu)，層次聚類一般有兩種劃分策略：自底向上的聚合（agglomerative）策略和自頂向下的分拆（divisive）策略，本文對層次聚類算法原理進(jìn)行了詳細(xì)總結(jié)。

目錄

1. 層次聚類算法原理

2. 簇間相似度的計(jì)算方法

3. 層次聚類算法的復(fù)雜度計(jì)算

4. 層次聚類算法的優(yōu)化方法

5. 層次聚類算法的優(yōu)缺點(diǎn)

層次聚類根據(jù)劃分策略包括聚合層次聚類和拆分層次聚類，由于前者較后者有更廣泛的應(yīng)用且算法思想一致，因此本節(jié)重點(diǎn)介紹聚合層次聚類算法。

聚合層次聚類算法假設(shè)每個(gè)樣本點(diǎn)都是單獨(dú)的簇類，然后在算法運(yùn)行的每一次迭代中找出相似度較高的簇類進(jìn)行合并，該過程不斷重復(fù)，直到達(dá)到預(yù)設(shè)的簇類個(gè)數(shù)K或只有一個(gè)簇類。

聚合層次聚類的基本思想：

1）計(jì)算數(shù)據(jù)集的相似矩陣；

2）假設(shè)每個(gè)樣本點(diǎn)為一個(gè)簇類；

3）循環(huán)：合并相似度最高的兩個(gè)簇類，然后更新相似矩陣；

4）當(dāng)簇類個(gè)數(shù)為1時(shí)，循環(huán)終止；

為了更好的理解，我們對算法進(jìn)行圖示說明，假設(shè)我們有6個(gè)樣本點(diǎn){A,B,C,D,E,F}。

第一步：我們假設(shè)每個(gè)樣本點(diǎn)都為一個(gè)簇類（如下圖），計(jì)算每個(gè)簇類間的相似度，得到相似矩陣；

第二步：若B和C的相似度最高，合并簇類B和C為一個(gè)簇類?，F(xiàn)在我們還有五個(gè)簇類，分別為A，BC，D，E，F(xiàn)。

第三步：更新簇類間的相似矩陣，相似矩陣的大小為5行5列；若簇類BC和D的相似度最高，合并簇類BC和D為一個(gè)簇類?，F(xiàn)在我們還有四個(gè)簇類，分別為A，BCD，E，F(xiàn)。

第四步：更新簇類間的相似矩陣，相似矩陣的大小為4行4列；若簇類E和F的相似度最高，合并簇類E和F為一個(gè)簇類?，F(xiàn)在我們還有3個(gè)簇類，分別為A，BCD，EF。

第五步：重復(fù)第四步，簇類BCD和簇類EF的相似度最高，合并該兩個(gè)簇類；現(xiàn)在我們還有2個(gè)簇類，分別為A，BCDEF。

第六步：最后合并簇類A和BCDEF為一個(gè)簇類，層次聚類算法結(jié)束。

樹狀圖是類似樹（tree-like）的圖表，記錄了簇類聚合和拆分的順序。我們根據(jù)上面的步驟，使用樹狀圖對聚合層次聚類算法進(jìn)行可視化：

也可用下面的圖記錄簇類聚合和拆分的順序：

拆分層次聚類算法假設(shè)所有數(shù)據(jù)集歸為一類，然后在算法運(yùn)行的每一次迭代中拆分相似度最低的樣本，該過程不斷重復(fù)，最終每個(gè)樣本對應(yīng)一個(gè)簇類。簡單點(diǎn)說，拆分層次聚類是聚合層次聚類的反向算法，讀者可通過樹狀圖去加強(qiáng)理解，一個(gè)是自底向上的劃分，一個(gè)是自頂向下的劃分。

由上節(jié)知道，合并或拆分層次聚類算法都是基于簇間相似度進(jìn)行的，每個(gè)簇類包含了一個(gè)或多個(gè)樣本點(diǎn)，通常用距離評價(jià)簇間或樣本間的相似度，即距離越小相似度越高，距離越大相似度越低。因此我們首先假設(shè)樣本間的距離為：dist(Pi,Pj)，其中Pi，Pj為任意兩個(gè)樣本，下面介紹常用的簇間相似度計(jì)算方法：

• 最小距離

• 最大距離

• 平均距離

• 中心距離

• 最小方差法

最小距離：也稱為單鏈接算法（single linkage algorithm），含義為簇類C1和C2的距離由該兩個(gè)簇的最近樣本決定，數(shù)學(xué)表達(dá)式寫為：

算法也可用下圖表示，其中紅色線表示簇類C1和C2的距離。

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

只要兩個(gè)簇類的間隔不是很小，單鏈接算法可以很好的分離非橢圓形狀的樣本分布。

如下圖的兩個(gè)聚類例子，其中不同顏色表示不同的簇類：

例1

例2

缺點(diǎn)：

單鏈接算法不能很好的分離簇類間含有噪聲的數(shù)據(jù)集，如下圖：

最大距離：也稱為全鏈接算法（complete linkage algorithm），含義為簇類C1和C2的距離由該兩個(gè)簇的最遠(yuǎn)樣本決定，與單鏈接算法的含義相反，數(shù)學(xué)表達(dá)式寫為：

算法也可用如下圖表示，其中紅色線表示簇類C1和C2的距離。

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

全鏈接算法可以很好的分離簇類間含有噪聲的數(shù)據(jù)集，如下圖：

缺點(diǎn)：

全鏈接算法對球形數(shù)據(jù)集的分離會產(chǎn)生偏差，如下圖：

平均距離：也稱為均鏈接算法（average-linkage algorithm），含義為簇類C1和C2的距離等于兩個(gè)簇類所有樣本對的距離平均，數(shù)學(xué)表達(dá)式為：

其中|C1|，|C2|分別表示簇類的樣本個(gè)數(shù)。

均鏈接算法也可用如下圖表示：

所有連線的距離求和平均即為簇類C1和C2的距離。

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

均鏈接算法可以很好的分離簇類間有噪聲的數(shù)據(jù)集。

缺點(diǎn)：

均鏈接算法對球形數(shù)據(jù)集的分離會產(chǎn)生偏差。

中心距離：簇類C1和C2的距離等于該兩個(gè)簇類中心間的距離，如下圖：

其中紅色點(diǎn)表示簇類的中心，紅色線表示簇類C1和C2的距離。這種計(jì)算簇間距離的方法非常少用，個(gè)人不建議使用這一算法。

離差平方和：簇類C1和C2的距離等于兩個(gè)簇類所有樣本對距離平方和的平均，與均鏈接算法很相似，數(shù)學(xué)表達(dá)式為：

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

離差平方和可以很好的分離簇間有噪聲的數(shù)據(jù)集。

缺點(diǎn)：

離差平方和對球形數(shù)據(jù)集的分離會產(chǎn)生偏差。

我們已經(jīng)知道了如何通過樣本間的距離來評估簇間的距離，本節(jié)只剩下最后一個(gè)問題了，如何計(jì)算樣本間的距離，假設(shè)樣本是n維，常用的距離計(jì)算方法有：

1）歐拉距離（Euclidean distance）：

2）平方歐式距離（Squared Euclidean distance）：

3）曼哈頓距離（Manhattan distance）：

4）切比雪夫距離（Chebyshev distance）:

5）馬氏距離（Mahalanobis distance）：

其中S為協(xié)方差矩陣。

對于文本或非數(shù)值型的數(shù)據(jù)，我們常用漢明距離（Hamming distance）和編輯距離（Levenshtein distance）表示樣本間的距離。

不同的距離度量會影響簇類的形狀，因?yàn)闃颖揪嚯x因距離度量的不同而不同，如點(diǎn)（1.1）和（0,0）的曼哈頓距離是2，歐式距離是sqrt(2)，切比雪夫距離是1。

空間復(fù)雜度：當(dāng)樣本點(diǎn)數(shù)目很大時(shí)，層次聚類需要較大的空間存儲相似矩陣，相似矩陣的大小是樣本個(gè)數(shù)的平方，因此空間復(fù)雜度是n的平方階次，即空間復(fù)雜度=O(n^2)。

?

時(shí)間復(fù)雜度：層次聚類算法需要進(jìn)行n次迭代，每次迭代都需要更新并存儲相似矩陣，所以時(shí)間復(fù)雜度是樣本個(gè)數(shù)n的立方階次，即時(shí)間復(fù)雜度=O(n^3)。

上節(jié)介紹數(shù)據(jù)量較大時(shí)，層次聚類算法的空間復(fù)雜度和時(shí)間復(fù)雜度較高，我們可以通過連通性約束（connectivity constraint）降低算法復(fù)雜度，甚至提高聚類結(jié)果。

連通性約束是通過連通性矩陣（connectivity matrix）實(shí)現(xiàn)的，連通性矩陣的元素只有1和0兩種結(jié)果，1表示兩個(gè)樣本是連通的，0表示兩個(gè)樣本不連通，我們只對連通性的樣本進(jìn)行距離計(jì)算并融合，這一過程大大降低了計(jì)算量，常采用sklearn.neighbors.kneighbors_graph來構(gòu)建連接矩陣。

我們構(gòu)建了容量為15000的瑞士卷（swiss roll dataset）數(shù)據(jù)集：

# 生成瑞士卷數(shù)據(jù)集，容量為15000
n_samples = 15000
noise = 0.05
X, _ = make_swiss_roll(n_samples, noise)
# 減小瑞士卷的厚度
X[:, 1] *= .5

用離差平方和的層次聚類算法建模，可視化聚類結(jié)果并輸出算法運(yùn)行時(shí)間。

print("Compute unstructured hierarchical clustering...")
st = time.time()
ward = AgglomerativeClustering(n_clusters=6, linkage='ward').fit(X)
elapsed_time = time.time() - st
label = ward.labels_
# 運(yùn)行時(shí)間
print("Elapsed time: %.2fs" % elapsed_time)
print("Number of points: %i" % label.size)

# #############################################################################
# 可視化結(jié)果
fig = plt.figure()
ax = p3.Axes3D(fig)
ax.view_init(7, -80)
for l in np.unique(label):
    ax.scatter(X[label == l, 0], X[label == l, 1], X[label == l, 2],
               color=plt.cm.jet(np.float(l) / np.max(label + 1)),
               s=20, edgecolor='k')
plt.title('Without connectivity constraints (time %.2fs)' % elapsed_time)

結(jié)果：

我們在構(gòu)建層次聚類算法模型前，先定義數(shù)據(jù)集的連通矩陣：

# 定義不包含樣本點(diǎn)在內(nèi)的10個(gè)最近鄰的連通樣本點(diǎn)
from sklearn.neighbors import kneighbors_graph
connectivity = kneighbors_graph(X, n_neighbors=10, include_self=False)

用離差平方和的層次聚類算法建模，可視化聚類結(jié)果并輸出算法運(yùn)行時(shí)間：

print("Compute structured hierarchical clustering...")
st = time.time()
ward = AgglomerativeClustering(n_clusters=6, connectivity=connectivity,
                               linkage='ward').fit(X)
elapsed_time = time.time() - st
label = ward.labels_
print("Elapsed time: %.2fs" % elapsed_time)
print("Number of points: %i" % label.size)

# #############################################################################
# Plot result
fig = plt.figure()
ax = p3.Axes3D(fig)
ax.view_init(7, -80)
for l in np.unique(label):
    ax.scatter(X[label == l, 0], X[label == l, 1], X[label == l, 2],
               color=plt.cm.jet(float(l) / np.max(label + 1)),
               s=20, edgecolor='k')
plt.title('With connectivity constraints (time %.2fs)' % elapsed_time)

plt.show()

結(jié)果：

由上面例子可知：大數(shù)據(jù)量的情況下，增加連通性約束矩陣可以降低算法的運(yùn)行時(shí)間，若只關(guān)注數(shù)據(jù)集的局部信息，連通性約束也能提高算法性能。

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

算法簡單，易于理解

樹狀圖包含了整個(gè)算法過程的信息；

?

缺點(diǎn)：

選擇合適的距離度量與簇類的鏈接準(zhǔn)則較難；

高的時(shí)間復(fù)雜度和空間復(fù)雜度；

參考：

https://towardsdatascience.com

https://scikit-learn.org/stable/

交流群

歡迎加入公眾號讀者群一起和同行交流，目前有SLAM、三維視覺、傳感器、自動駕駛、計(jì)算攝影、檢測、分割、識別、醫(yī)學(xué)影像、GAN、算法競賽等微信群（以后會逐漸細(xì)分），請掃描下面微信號加群，備注：”昵稱+學(xué)校/公司+研究方向“，例如：”張三?+?上海交大?+?視覺SLAM“。請按照格式備注，否則不予通過。添加成功后會根據(jù)研究方向邀請進(jìn)入相關(guān)微信群。請勿在群內(nèi)發(fā)送廣告，否則會請出群，謝謝理解~