層次聚類

在數據挖掘和統計學中，層次聚類（英語：Hierarchical clustering）是一種旨在建立聚類的層次結構的聚類分析方法。層次聚類的策略通常有兩種：

• 凝聚（Agglomerative clustering）：一種自底向上方法，從小集群開始，逐漸將其合併，形成更大的集群；
• 分裂（Divisive clustering）：一種自頂向下方法，從單個集群開始，遞歸地將其拆分成更小的集群。

凝聚和分離的操作通常用貪心算法實現，結果通常用樹狀圖展示。

標準的凝聚層次聚類（Hierarchical agglomerative clustering，HAC）算法的時間複雜度為${\mathcal {O}}(n^{3})$，空間複雜度為$\Omega (n^{2})$，這使它甚至難以應用於中等規模的數據集中。對於一些特殊情況，效率最優的算法（複雜度為${\mathcal {O}}(n^{2})$）包括SLINK（用於單連接聚類，Single-linkage clustering）和CLINK（用於全連接聚類，Complete-linkage clustering）。當使用堆（Heap）時，一般情況下的時間複雜度降至${\mathcal {O}}(n^{2}\log n)$，該改進以更多的內存需求為代價。這種改進方法的內存開銷很多時候大到難以實際使用。

除了單連接聚類的特殊情況，除了窮舉算法（複雜度${\mathcal {O}}(2^{n})$）外，沒有算法可以保證找到最優解。

使用窮舉算法的分裂方法的複雜度為${\mathcal {O}}(2^{n})$，不過可以通過更快的啟發式方法（例如k-均值算法）進行分裂。

層次聚類的優點是可以採用任何有效的距離測量。當給定距離矩陣時，觀測本身是沒有必要的。

聚集層次聚類

原始數據

本節將對上圖所示的原始數據進行聚集層次聚類（Agglomerative clustering），採取歐幾里得距離度量距離。

下圖展示了聚類結果的樹狀圖：

聚類結果

在給定高度切割樹，會得到一個特定精度的聚類結果。例如，在從上往下數的第二行切割會得到四個集群：{a}、{b, c}、{d, e}和{f}；在第三行切割會得到{a}、{b, c}、{d, e, f}，相比之前，這是一個更粗糙（coarser）的聚類結果，集群的數量更少但集群更大。

該方法合併單獨的元素形成集群並得到層次（Hierarchy）。本例有六個元素（{a}、{b}、{c}、{d}、{e} 、{f}），第一步確定哪些元素合併到一個集群，判定標準通常是元素間的距離，選取兩個最近的形成集群。

也可以在該步構建距離矩陣（矩陣的第i行第j列的數值為i-j元素之間的距離）。在聚類過程中，行、列被合併並形成新的距離。該方法為實現聚集層次聚類的通用方法，同時對緩存集群之間的距離有益。單連接聚類是一個簡單的聚集層次聚類方法。

在完成對距離最短元素b和c的合併後，形成的集群為：{a}、{b, c}、{d}、{e} 、{f}，對其進行進一步的合併需要度量集群{a}和{b, c}之間的距離（即兩個集群間的距離）。通常將集群${\mathcal {A}}$和${\mathcal {B}}$之間的距離定義為：

• 兩個集群的元素間的最大距離（又稱全連接聚類）：

$\max\{\,d(x,y):x\in {\mathcal {A}},\,y\in {\mathcal {B}}\,\}.$

• 兩個集群的元素間的最小距離（又稱單連接聚類）：

$\min\{\,d(x,y):x\in {\mathcal {A}},\,y\in {\mathcal {B}}\,\}.$

• 兩個集群的元素間的平均距離（又稱平均連接聚類（Average linkage clustering），在UPGMA方法中有應用）：

${1 \over {|{\mathcal {A}}|\cdot |{\mathcal {B}}|}}\sum _{x\in {\mathcal {A}}}\sum _{y\in {\mathcal {B}}}d(x,y).$

• 所有聚類內方差的總和
• 被合併的集群方差的增加量 （Ward法）
• 候選聚類從同一分布函數生成的概率（V-linkage）

當若干對組合具有同樣的距離且為最小時，可以隨機選取一對形成集群（生成不同的樹狀圖）；也可以同時形成不同的集群（生成唯一的樹狀圖）。

聚類算法的停止準則可以取決於數量（當形成足夠少的集群時停止）；也可以取決於距離（當兩個集群之間的距離足夠遠，以至於不能形成新集群時停止）。

分裂層次聚類

DIANA（DIvisive ANAlysis Clustering）是分裂層次聚類的基礎算法。 首先，所有元素歸屬同一個集群，然後分裂集群，直到所有元素都獨立成群。由於存在$O(2^{n})$種方法進行分裂，因此需要啟發式（Heuristics）算法實現。DIANA選擇平均異同度（Average dissimilarity）最大的元素，然後將所有與新集群相似度高於其餘集群的元素劃分到該集群。

軟體

開源軟體

• ALGLIB用C++和C#實現了多種層次聚類算法
• ELKI實現了多種層次聚類算法
• Julia在Clustering.jl包中實現了層次聚類
• Octave（GNU對MATLAB的兼容實現）實現了層次聚類（函數linkage）
• Orange（一個數據挖掘軟體套件）實現了帶有交互式樹狀圖可視層次聚類
• R有內置的函數和包，提供層次聚類的函數
• SciPy在Python中實現了層次聚類
• Scikit-learn也在Python中實現了層次聚類
• Weka實現了層次聚類

商業軟體

• MATLAB中有層次聚類分析
• SAS在PROC CLUSTER中包含層次聚類分析
• Mathematica有一個層次聚類包
• NCSS中實現了層次聚類分析
• SPSS中包括層次聚類分析
• Qlucore Omics Explorer中包括分層聚類分析
• Stata中包括層次聚類分析
• CrimeStat中實現了近鄰層次聚類算法