查看“︁层次聚类”︁的源代码

{{机器学习导航栏}}

在[[数据挖掘]]和[[统计学]]中，'''层次聚类'''（{{Lang-en|Hierarchical clustering}}）是一种旨在建立聚类的层次结构的[[聚类分析]]方法。层次聚类的策略通常有两种：

* 凝聚（Agglomerative clustering）：一种自底向上方法，从小集群开始，逐渐将其合并，形成更大的集群；
* 分裂（Divisive clustering）：一种自顶向下方法，从单个集群开始，递归地将其拆分成更小的集群。

凝聚和分离的操作通常用[[贪心算法]]实现，结果通常用{{Link-en|树状图|Dendrogram}}展示。<ref>{{cite book|first=Frank|last=Nielsen|title=Introduction to HPC with MPI for Data Science|year=2016|publisher=Springer|isbn=978-3-319-21903-5|pages=195–211|chapter=8. Hierarchical Clustering|url=https://www.springer.com/gp/book/9783319219028|chapter-url=https://www.researchgate.net/publication/314700681|access-date=2023-03-05|archive-date=2021-04-17|archive-url=https://web.archive.org/web/20210417175448/https://www.springer.com/gp/book/9783319219028|dead-url=no}}</ref>

标准的凝聚层次聚类（Hierarchical agglomerative clustering，HAC）算法的时间复杂度为<math>\mathcal{O}(n^3) </math>，空间复杂度为<math>\Omega(n^2) </math>，这使它甚至难以应用于中等规模的数据集中。对于一些特殊情况，效率最优的算法（复杂度为<math>\mathcal{O}(n^2) </math>）包括SLINK（用于单连接聚类，Single-linkage clustering）<ref name="SLINK">{{cite journal |author=R. Sibson |year=1973 |title=SLINK: an optimally efficient algorithm for the single-link cluster method |url=http://www.cs.gsu.edu/~wkim/index_files/papers/sibson.pdf |journal=The Computer Journal |publisher=British Computer Society |volume=16 |issue=1 |pages=30–34 |doi=10.1093/comjnl/16.1.30 |doi-access=free |access-date=2023-03-05 |archive-date=2014-09-24 |archive-url=https://web.archive.org/web/20140924182923/http://www.cs.gsu.edu/~wkim/index_files/papers/sibson.pdf |dead-url=no }}</ref>和CLINK（用于全连接聚类，Complete-linkage clustering）<ref name="CLINK">{{cite journal |author=D. Defays |year=1977 |title=An efficient algorithm for a complete-link method |journal=The Computer Journal |publisher=British Computer Society |volume=20 |issue=4 |pages=364–6 |doi=10.1093/comjnl/20.4.364 |doi-access=free}}</ref>。当使用[[堆]]（Heap）时，一般情况下的时间复杂度降至<math>\mathcal{O}(n^2 \log n)</math>，该改进以更多的内存需求为代价。这种改进方法的内存开销很多时候大到难以实际使用。

除了单连接聚类的特殊情况，除了穷举算法（复杂度<math>\mathcal{O}(2^n) </math>）外，没有算法可以保证找到最优解。

使用穷举算法的分裂方法的复杂度为<math>\mathcal{O}(2^n) </math>，不过可以通过更快的启发式方法（例如[[K-平均算法|k-均值算法]]）进行分裂。

层次聚类的优点是可以采用任何有效的距离测量。当给定[[距离矩阵]]时，观测本身是没有必要的。

== 聚集层次聚类 ==
[[File:Clusters.svg|none|frame|原始数据]]
本节将对上图所示的原始数据进行聚集层次聚类（Agglomerative clustering），采取[[欧几里得距离]]度量距离。

下图展示了聚类结果的树状图：
[[File:Hierarchical_clustering_simple_diagram.svg|none|frame|聚类结果]]
在给定高度切割树，会得到一个特定精度的聚类结果。例如，在从上往下数的第二行切割会得到四个集群：{a}、{b, c}、{d, e}和{f}；在第三行切割会得到{a}、{b, c}、{d, e, f}，相比之前，这是一个更粗糙（coarser）的聚类结果，集群的数量更少但集群更大。

该方法合并单独的元素形成集群并得到层次（Hierarchy）。本例有六个元素（{a}、{b}、{c}、{d}、{e} 、{f}），第一步确定哪些元素合并到一个集群，判定标准通常是元素间的距离，选取两个最近的形成集群。

也可以在该步构建[[距离矩阵]]（矩阵的第i行第j列的数值为i-j元素之间的距离）。在聚类过程中，行、列被合并并形成新的距离。该方法为实现聚集层次聚类的通用方法，同时对缓存集群之间的距离有益。{{Link-en|单连接聚类|Single-linkage_clustering}}是一个简单的聚集层次聚类方法。

在完成对距离最短元素''b''和''c''的合并后，形成的集群为：{''a''}、{''b'', ''c''}、{''d''}、{''e''} 、{''f''}，对其进行进一步的合并需要度量集群{a}和{b, c}之间的距离（即两个集群间的距离）。通常将集群<math>\mathcal{A}</math>和<math>\mathcal{B}</math>之间的距离定义为：

* 两个集群的元素间的最大距离（又称{{Link-en|全连接聚类|Complete-linkage_clustering}}）：

:: <math> \max \{\, d(x,y) : x \in \mathcal{A},\, y \in \mathcal{B}\,\}. </math>

* 两个集群的元素间的最小距离（又称{{Link-en|单连接聚类|Single-linkage_clustering}}）：

:: <math> \min \{\, d(x,y) : x \in \mathcal{A},\, y \in \mathcal{B} \,\}. </math>

* 两个集群的元素间的平均距离（又称平均连接聚类（Average linkage clustering），在[[UPGMA]]方法中有应用）：

:: <math> {1 \over {|\mathcal{A}|\cdot|\mathcal{B}|}}\sum_{x \in \mathcal{A}}\sum_{ y \in \mathcal{B}} d(x,y). </math>

* 所有聚类内方差的总和
* 被合并的集群方差的增加量 （{{Link-en|Ward法|Ward%27s_method}}<ref name="wards method2">{{cite journal |last=Ward |first=Joe H. |year=1963 |title=Hierarchical Grouping to Optimize an Objective Function |url=https://archive.org/details/sim_journal-of-the-american-statistical-association_1963-03_58_301/page/236 |journal=Journal of the American Statistical Association |volume=58 |issue=301 |pages=236–244 |doi=10.2307/2282967 |jstor=2282967 |mr=0148188}}</ref>）
* 候选聚类从同一分布函数生成的概率（V-linkage）

当若干对组合具有同样的距离且为最小时，可以随机选取一对形成集群（生成不同的树状图）；也可以同时形成不同的集群（生成唯一的树状图）。<ref>{{cite journal |last1=Fernández |first1=Alberto |last2=Gómez |first2=Sergio |year=2008 |title=Solving Non-uniqueness in Agglomerative Hierarchical Clustering Using Multidendrograms |journal=Journal of Classification |volume=25 |issue=1 |pages=43–65 |arxiv=cs/0608049 |doi=10.1007/s00357-008-9004-x |s2cid=434036}}</ref>

聚类算法的停止准则可以取决于数量（当形成足够少的集群时停止）；也可以取决于距离（当两个集群之间的距离足够远，以至于不能形成新集群时停止）。

== 分裂层次聚类 ==
DIANA（DIvisive ANAlysis Clustering）是分裂层次聚类的基础算法。<ref>{{cite book|first1=L.|last1=Kaufman|first2=P.J.|last2=Rousseeuw|chapter=6. Divisive Analysis (Program DIANA)|title=Finding Groups in Data: An Introduction to Cluster Analysis|chapter-url=https://books.google.com/books?id=YeFQHiikNo0C&pg=PA253|orig-year=1990|date=2009|publisher=Wiley|isbn=978-0-470-31748-8|pages=253–279|access-date=2023-03-06|archive-date=2023-03-06|archive-url=https://web.archive.org/web/20230306064518/https://books.google.com/books?id=YeFQHiikNo0C&pg=PA253|dead-url=no}}</ref> 首先，所有元素归属同一个集群，然后分裂集群，直到所有元素都独立成群。由于存在<math>O(2^n)</math>种方法进行分裂，因此需要启发式（Heuristics）算法实现。DIANA选择平均异同度（Average dissimilarity）最大的元素，然后将所有与新集群相似度高于其余集群的元素划分到该集群。

== 软件 ==

=== 开源软件 ===

* ALGLIB用C++和C#实现了多种层次聚类算法
* ELKI实现了多种层次聚类算法
* [[Julia (编程语言)|Julia]]在Clustering.jl包中实现了层次聚类<ref>{{Cite web|title=Hierarchical Clustering · Clustering.jl|url=https://juliastats.org/Clustering.jl/stable/hclust.html|access-date=2022-02-28|website=juliastats.org|language=en|archive-date=2023-03-05|archive-url=https://web.archive.org/web/20230305093641/https://juliastats.org/Clustering.jl/stable/hclust.html|dead-url=no}}</ref>
* [[GNU Octave|Octave]]（GNU对MATLAB的兼容实现）实现了层次聚类（函数linkage）
* Orange（一个数据挖掘软件套件）实现了带有交互式树状图可视层次聚类
* [[R语言|R]]有内置的函数和包<ref>{{Cite web|title=hclust function - RDocumentation|url=https://www.rdocumentation.org/packages/stats/versions/3.6.2/topics/hclust|access-date=2022-06-07|website=www.rdocumentation.org|language=en|archive-date=2023-03-15|archive-url=https://web.archive.org/web/20230315104353/https://www.rdocumentation.org/packages/stats/versions/3.6.2/topics/hclust|dead-url=no}}</ref>，提供层次聚类的函数
* [[SciPy]]在Python中实现了层次聚类
* [[Scikit-learn]]也在Python中实现了层次聚类
* [[Weka]]实现了层次聚类

=== 商业软件 ===

* [[MATLAB]]中有层次聚类分析
* [[統計分析系統|SAS]]在PROC CLUSTER中包含层次聚类分析
* [[Wolfram Mathematica|Mathematica]]有一个层次聚类包
* NCSS中实现了层次聚类分析
* [[SPSS]]中包括层次聚类分析
* Qlucore Omics Explorer中包括分层聚类分析
* [[Stata]]中包括层次聚类分析
* CrimeStat中实现了近邻层次聚类算法

== 参考文献 ==
{{Reflist}}
[[Category:数据挖掘]]
[[Category:聚类分析]]
[[Category:机器学习]]