文章目錄

• 1. 層次聚類
• • 1.1 凝聚聚類
  • 1.2 層次圖
  • 1.3 不同凝聚算法比較
• 2. Sklearn 實現
• • 2.1 層次圖可視化
• 參考文獻

相關文章：

機器學習 | 目錄

機器學習 | 聚類評估指標

機器學習 | 距離計算

無監督學習 | KMeans 與 KMeans++ 原理

無監督學習 | DBSCAN 原理及Sklearn實現

無監督學習 | GMM 高斯混合聚類原理及Sklearn實現

1. 層次聚類

層次聚類（hierarchical clustering）試圖在不同層次對數據集進行劃分，從而形成樹形的聚類結構。數據集的劃分可采用“自底向上”的聚合策略，也可采用“自頂向下”的分拆策略。^[1]

因此其優點是可以層次化聚類，將聚類結構視覺化；而缺點是計算量大，我們將在后面提到這一點。

1.1 凝聚聚類

凝聚聚類（Agglomerative Clustering）是一種采用自底向上聚類策略的層次聚類算法。它先將數據集中的每個樣本看作一個初始聚類簇，然后在算法運行的每一步中找出距離最近的兩個聚類簇進行合并。該過程不斷重復，直到達到預設的聚類簇個數。這里的關鍵是如何計算聚類簇之間的距離。實際上，每個簇是一個樣本集合，因此，只需要采用關于集合的某種距離即可。例如，給定聚類簇 $C_i$ 與 $C_j$，可通過下面的式子來計算距離：

$$最小距離：d_{\min }\left(C_i,C_j\right)=\underset{\mathbf{x}\in C_i,\mathbf{z}\in C_j}{\min }\mathrm{dist}(\mathbf{x},\mathbf{z})\text{\hspace{1em}(1)}$$

$$最大距離：d_{\max }\left(C_i,C_j\right)=\underset{\mathbf{x}\in C_i,\mathbf{z}\in C_j}{\max }\mathrm{dist}(\mathbf{x},\mathbf{z})\text{\hspace{1em}(2)}$$

$$平均距離：d_{\mathrm{avg}}\left(C_i,C_j\right)=\frac{1}{\left|C_i\right|\left|C_j\right|}\sum _{\mathbf{x}\in C_i}\sum _{\mathbf{z}\in C_j}\mathrm{dist}(\mathbf{x},\mathbf{z})\text{\hspace{1em}(3)}$$

顯然，最小距離由兩個簇的最近樣本決定，最大距離由兩個簇的最遠樣本決定，而平均距離則由兩個簇的所有樣本共同決定。

此外，也可以使用離差平方和 ESS（Error Sum of Squares）來進行聚類，通過最小化聚類前后的離方平方和之差 $\Delta (C_i,C_j)$，來尋找最近的簇。^[2]

$$離差平方和：ESS=\sum _{i=1}^n{x}_i^2?\frac{1}{n}(\sum _{i=1}^n{x}_i{)}^2\text{\hspace{1em}(4)}$$

$$\Delta (C_i,C_j)=ESS(C_i\cup C_j)?ESS(C_i)?ESS(C_j)\text{\hspace{1em}(5)}$$

---

當聚類簇距離由 $d_{min}$、$d_{max}$、$d_{avg}$ 或 $\Delta (C_i,C_j)$ 計算時，凝聚聚類算法被相應地稱為單鏈接（single-linkage）、全鏈接（complete-linkage）)、均鏈接（average-linkage）和 Ward-linkage 算法。

凝聚聚類算法描述如下圖所示：

• 在第 1-9 行，算法先對僅包含一個樣本的初始聚類簇和相應的距離矩陣進行初始化；

• 在第 11-23 行，凝聚算法不斷合并距離最近的聚類簇，并對合并得到的聚類簇的距離矩陣進行更新；

上述過程不斷重復，直到達到預設的聚類簇數。

圖1 凝聚聚類算法

1.2 層次圖

下面以單鏈接為例子，介紹層次聚類的層次圖（系統圖，dendrogram）。假設我們有以下八個點，使用單鏈接聚為 3 個類。

首先將每個點設為一個單獨的簇類，因此此時有 8 個簇，大于預期 3 個簇，故需要繼續進行聚類。

圖2 初始化聚類簇

因此我們重復算法 11-23 行 3 次，每次將距離最近的兩個樣本聚為同一簇，對應右圖的層次圖。此時仍剩下 5 個簇，因此需要繼續進行聚類。

圖3 5個聚類簇

可以看到，此時樣本 7 與簇 {6,8} 的距離（$dis{t}_{min}=dist(6,7)$）最近，因此可以將他們聚為一簇，如下圖所示：

圖4 4個聚類簇

同理，繼續進行聚類，考慮各個簇之間的距離，可以看出，樣本 3 與簇 {4,5} 的距離（$dis{t}_{m}in=dist(3,4)$）最近，因此有：

圖5 3個聚類簇

此時已經達到了我們所要求的聚類簇數，故算法停止，對應的層次圖如右方所示。

---

1.3 不同凝聚算法比較

通過下面圖片，我們可以看到各類凝聚算法在不同類型數據上的聚類效果，

需要注意的是，由于單鏈接和全鏈接只考慮簇中兩個代表性的點，故受噪聲和異常點影響大；而單鏈接容易出現一個簇囊括大多數樣本（左下方圖），而全鏈接則比單鏈接更緊湊些。

圖6 不同凝聚算法比較

2. Sklearn 實現

sklearn.cluster.AgglomerativeClustering(n_clusters=2, affinity=‘euclidean’, memory=None, connectivity=None, compute_full_tree=‘auto’, linkage=‘ward’, distance_threshold=None)

n_clusters：聚類簇數

affinity： string or callable, default: “euclidean” 【距離計算參數】

Metric used to compute the linkage. Can be “euclidean”, “l1”, “l2”, “manhattan”, “cosine”, or “precomputed”. If linkage is “ward”, only “euclidean” is accepted. If “precomputed”, a distance matrix (instead of a similarity matrix) is needed as input for the fit method.

linkage： {“ward”, “complete”, “average”, “single”}, optional (default=”ward”)

Which linkage criterion to use. The linkage criterion determines which distance to use between sets of observation. The algorithm will merge the pairs of cluster that minimize this criterion.

• ward minimizes the variance of the clusters being merged.

• average uses the average of the distances of each observation of the two sets.

• complete or maximum linkage uses the maximum distances between all observations of the two sets.

• single uses the minimum of the distances between all observations of the two sets.

2.1 層次圖可視化

由于 Sklearn 中并不支持可視化層次圖，因此我們使用 Scipy：

from scipy.cluster.hierarchy import dendrogram, ward, single from sklearn.datasets import load_iris import matplotlib.pyplot as pltX = load_iris().data[:10]linkage_matrix = ward(X)dendrogram(linkage_matrix)plt.show <function matplotlib.pyplot.show(*args, **kw)> 圖7 層次樹可視化

參考文獻

[1] 周志華. 機器學習[M]. 北京: 清華大學出版社, 2016: 214.

[2] Ward J H , Jr. Hierarchical Grouping to Optimize an Objective Function[J]. Journal of the American Statistical Association, 1963, 58(301):236-244.

總結

以上是生活随笔為你收集整理的无监督学习 | 层次聚类 之凝聚聚类原理及Sklearn实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。