層次聚類

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

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

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

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

除了單連接聚類的特殊情況,除了窮舉算法(複雜度)外,沒有算法可以保證找到最優解。

使用窮舉算法的分裂方法的複雜度為,不過可以通過更快的啟發式方法(例如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元素之間的距離)。在聚類過程中,行、列被合併並形成新的距離。該方法為實現聚集層次聚類的通用方法,同時對緩存集群之間的距離有益。單連接聚類英語Single-linkage_clustering是一個簡單的聚集層次聚類方法。

在完成對距離最短元素bc的合併後,形成的集群為:{a}、{b, c}、{d}、{e} 、{f},對其進行進一步的合併需要度量集群{a}和{b, c}之間的距離(即兩個集群間的距離)。通常將集群  之間的距離定義為:

 
 
  • 兩個集群的元素間的平均距離(又稱平均連接聚類(Average linkage clustering),在UPGMA方法中有應用):
 
  • 所有聚類內方差的總和
  • 被合併的集群方差的增加量 (Ward法英語Ward%27s_method[4]
  • 候選聚類從同一分佈函數生成的概率(V-linkage)

當若干對組合具有同樣的距離且為最小時,可以隨機選取一對形成集群(生成不同的樹狀圖);也可以同時形成不同的集群(生成唯一的樹狀圖)。[5]

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

分裂層次聚類

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

軟件

開源軟件

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

商業軟件

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

參考文獻

  1. ^ Nielsen, Frank. 8. Hierarchical Clustering. Introduction to HPC with MPI for Data Science. Springer. 2016: 195–211 [2023-03-05]. ISBN 978-3-319-21903-5. (原始內容存檔於2021-04-17). 
  2. ^ Ward, Joe H. Hierarchical Grouping to Optimize an Objective Function. Journal of the American Statistical Association. 1963, 58 (301): 236–244. JSTOR 2282967. MR 0148188. doi:10.2307/2282967. 
  3. ^ Fernández, Alberto; Gómez, Sergio. Solving Non-uniqueness in Agglomerative Hierarchical Clustering Using Multidendrograms. Journal of Classification. 2008, 25 (1): 43–65. S2CID 434036. arXiv:cs/0608049 . doi:10.1007/s00357-008-9004-x. 
  4. ^ Kaufman, L.; Rousseeuw, P.J. 6. Divisive Analysis (Program DIANA). Finding Groups in Data: An Introduction to Cluster Analysis. Wiley. 2009: 253–279 [1990] [2023-03-06]. ISBN 978-0-470-31748-8. (原始內容存檔於2023-03-06). 
  5. ^ Hierarchical Clustering · Clustering.jl. juliastats.org. [2022-02-28]. (原始內容存檔於2023-03-05) (英語). 
  6. ^ hclust function - RDocumentation. www.rdocumentation.org. [2022-06-07]. (原始內容存檔於2023-03-15) (英語).