层次聚类
机器学习与数据挖掘 |
---|
![]() |
在数据挖掘和统计学中,层次聚类(英語:Hierarchical clustering)是一种旨在建立聚类的层次结构的聚类分析方法。层次聚类的策略通常有两种:
- 凝聚(Agglomerative clustering):一种自底向上方法,从小集群开始,逐渐将其合并,形成更大的集群;
- 分裂(Divisive clustering):一种自顶向下方法,从单个集群开始,递归地将其拆分成更小的集群。
凝聚和分离的操作通常用贪心算法实现,结果通常用树状图展示。[1]
标准的凝聚层次聚类(Hierarchical agglomerative clustering,HAC)算法的时间复杂度为,空间复杂度为,这使它甚至难以应用于中等规模的数据集中。对于一些特殊情况,效率最优的算法(复杂度为)包括SLINK(用于单连接聚类,Single-linkage clustering)[2]和CLINK(用于全连接聚类,Complete-linkage clustering)[3]。当使用堆(Heap)时,一般情况下的时间复杂度降至,该改进以更多的内存需求为代价。这种改进方法的内存开销很多时候大到难以实际使用。
除了单连接聚类的特殊情况,除了穷举算法(复杂度)外,没有算法可以保证找到最优解。
使用穷举算法的分裂方法的复杂度为,不过可以通过更快的启发式方法(例如k-均值算法)进行分裂。
层次聚类的优点是可以采用任何有效的距离测量。当给定距离矩阵时,观测本身是没有必要的。
聚集层次聚类
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/b/b5/Clusters.svg/250px-Clusters.svg.png)
本节将对上图所示的原始数据进行聚集层次聚类(Agglomerative clustering),采取欧几里得距离度量距离。
下图展示了聚类结果的树状图:
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/a/ad/Hierarchical_clustering_simple_diagram.svg/418px-Hierarchical_clustering_simple_diagram.svg.png)
在给定高度切割树,会得到一个特定精度的聚类结果。例如,在从上往下数的第二行切割会得到四个集群:{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) (英语).