層次聚類
機器學習與資料探勘 |
---|
在數據挖掘和統計學中,層次聚類(英語: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元素之間的距離)。在聚類過程中,行、列被合併並形成新的距離。該方法為實現聚集層次聚類的通用方法,同時對緩存集群之間的距離有益。單連接聚類是一個簡單的聚集層次聚類方法。
在完成對距離最短元素b和c的合併後,形成的集群為:{a}、{b, c}、{d}、{e} 、{f},對其進行進一步的合併需要度量集群{a}和{b, c}之間的距離(即兩個集群間的距離)。通常將集群和之間的距離定義為:
- 兩個集群的元素間的最大距離(又稱全連接聚類):
- 兩個集群的元素間的最小距離(又稱單連接聚類):
- 兩個集群的元素間的平均距離(又稱平均連接聚類(Average linkage clustering),在UPGMA方法中有應用):
當若干對組合具有同樣的距離且為最小時,可以隨機選取一對形成集群(生成不同的樹狀圖);也可以同時形成不同的集群(生成唯一的樹狀圖)。[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中實現了近鄰層次聚類算法
參考文獻
[編輯]- ^ 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).
- ^ R. Sibson. SLINK: an optimally efficient algorithm for the single-link cluster method (PDF). The Computer Journal (British Computer Society). 1973, 16 (1): 30–34 [2023-03-05]. doi:10.1093/comjnl/16.1.30 . (原始內容存檔 (PDF)於2014-09-24).
- ^ D. Defays. An efficient algorithm for a complete-link method. The Computer Journal (British Computer Society). 1977, 20 (4): 364–6. doi:10.1093/comjnl/20.4.364 .
- ^ 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.
- ^ 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.
- ^ 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).
- ^ Hierarchical Clustering · Clustering.jl. juliastats.org. [2022-02-28]. (原始內容存檔於2023-03-05) (英語).
- ^ hclust function - RDocumentation. www.rdocumentation.org. [2022-06-07]. (原始內容存檔於2023-03-15) (英語).