层次聚类

本节将对上图所示的原始数据进行聚集层次聚类（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）是一个简单的聚集层次聚类方法。

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

• 两个集群的元素间的最大距离（又称全连接聚类（英语：Complete-linkage_clustering））：

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

• 两个集群的元素间的最小距离（又称单连接聚类（英语：Single-linkage_clustering））：

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

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

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

• 所有聚类内方差的总和
• 被合并的集群方差的增加量 （Ward法（英语：Ward%27s_method）^[4]）
• 候选聚类从同一分布函数生成的概率（V-linkage）

当若干对组合具有同样的距离且为最小时，可以随机选取一对形成集群（生成不同的树状图）；也可以同时形成不同的集群（生成唯一的树状图）。^[5]

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

DIANA（DIvisive ANAlysis Clustering）是分裂层次聚类的基础算法。^[6] 首先，所有元素归属同一个集群，然后分裂集群，直到所有元素都独立成群。由于存在${\displaystyle O(2^{n})}$ 种方法进行分裂，因此需要启发式（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中实现了近邻层次聚类算法