层次聚类

在数据挖掘和统计中，层次聚类（也称为层次聚类分析或HCA）是一种聚类分析的方法，旨在建立聚类的层次。层次集群的策略通常分为两种：^[1]

• 聚集的：这是一种“ 自下而上 ”的方法：每个观察都从其自己的群集开始，并且随着一个群集向上移动，群集对将合并。
• 分开的：这是一种“ 自上而下 ”的方法：所有观察都在一个簇中开始，并且随着一个人在层次结构中向下移动，递归执行拆分。

通常，合并和拆分以贪婪的方式确定。层次聚类的结果^[2]通常以树状图表示。

分层聚集聚类（HAC）的标准算法的时间复杂度为${\ displaystyle {\ mathcal {O}}（n ^ {3}）}$ 并要求 ${\ displaystyle {\ mathcal {O}}（n ^ {2}）}$内存，这对于中等大小的数据集来说也太慢了。但是，在某些特殊情况下，最佳有效的凝聚方法（复杂${\ displaystyle {\ mathcal {O}}（n ^ {2}）}$）是已知的：SLINK ^[3]用于单链接，CLINK ^[4]用于全链接群集。使用堆可以将一般情况的运行时间减少到${\ displaystyle {\ mathcal {O}}（n ^ {2} \ log n）}$以进一步增加内存需求为代价。在许多情况下，这种方法的内存开销太大，无法实际使用。

除了单链接的特殊情况外，没有一种算法（除了 ${\ displaystyle {\ mathcal {O}}（2 ^ {n}）}$）可以保证找到最佳解决方案。

带有详尽搜索的分裂聚类是 ${\ displaystyle {\ mathcal {O}}（2 ^ {n}）}$，但是通常使用更快的启发式方法来选择拆分，例如k-means。

聚类差异

为了确定应合并的群集（对于聚集），或应在何处拆分的群集（对分裂），需要测量一组观察值之间的差异。在大多数分层聚类方法中，这是通过使用适当的度量标准（观测对之间的距离的度量）和将集的不相似性指定为集合中观测对的成对距离的函数的链接标准来实现的。

公制

适当度量的选择将影响群集的形状，因为某些元素根据一个距离可能彼此接近，而根据另一个距离可能更远。例如，在二维空间中，根据常规规范，点（1,0）与原点（0,0）之间的距离始终为1，而点（1,1）与原点（0,0）之间的距离始终为1原点（0,0）可以是曼哈顿距离下的2，${\ displaystyle \ scriptstyle {\ sqrt {2}}}$ 在欧几里得距离下，或在最大距离下为1。

分层聚类的一些常用指标是：^[5]

名字	式
欧氏距离	${\ displaystyle \ | ab \ | _ {2} = {\ sqrt {\ sum _ {i}（a_ {i} -b_ {i}）^ {2}}}}$
平方欧几里德距离	${\ displaystyle \ | ab \ | _ {2} ^ {2} = \ sum _ {i}（a_ {i} -b_ {i}）^ {2}}$
曼哈顿距离	${\ displaystyle \ | ab \ | _ {1} = \ sum _ {i} | a_ {i} -b_ {i} |}$
最大距离	${\ displaystyle \ | ab \ | _ {\ infty} = \ max _ {i} | a_ {i} -b_ {i} |}$
马氏距离	${\ displaystyle {\ sqrt {（ab）^ {\ top} S ^ {-1}（ab）}}}$其中S是协方差矩阵

对于文本或其他非数字数据，通常使用汉明距离或Levenshtein距离等度量。

对健康心理学研究中的聚类分析进行的审查发现，该研究领域中最常见的距离度量是欧几里得距离或平方欧几里得距离。^[]

链接标准

链接标准根据观测值之间的成对距离确定观测值集之间的距离。

两组观测值A和B之间的一些常用链接标准是：^{[6] [7]}

名字	式
最大或完全链接群集	${\ displaystyle \ max \，\ {\，d（a，b）：a \ in A，\，b \ in B \，\}。}$
最小链接或单链接群集	${\ displaystyle \ min \，\ {\，d（a，b）：a \ in A，\，b \ in B \，\}。}$
未加权平均链接聚类（或UPGMA）	${\ displaystyle {\ frac {1} {| A | \ cdot | B |}} \ sum _ {a \ in A} \ sum _ {b \ in B} d（a，b）。}$
加权平均连锁聚类（或WPGMA）	${\ displaystyle d（i \ cup j，k）= {\ frac {d（i，k）+ d（j，k）} {2}}。}$
重心链接聚类或UPGMC	${\ displaystyle \ | c_ {s} -c_ {t} \ |}$ 哪里 ${\ displaystyle c_ {s}}$ 和 ${\ displaystyle c_ {t}}$分别是簇s和t的质心。
最小能量聚类	${\ displaystyle {\ frac {2} {nm}} \ sum _ {i，j = 1} ^ {n，m} \ | a_ {i} -b_ {j} \ | _ {2}-{\ frac {1} {n ^ {2}}} \和_ {i，j = 1} ^ {n} \ | a_ {i} -a_ {j} \ | _ {2}-{\ frac {1} { m ^ {2}}} \ sum _ {i，j = 1} ^ {m} \ | b_ {i} -b_ {j} \ | _ {2}}$

其中d是所选度量。其他链接标准包括：

• 所有集群内方差的总和。
• 要合并的群集的方差增加（沃德准则）。^[8]
• 候选群集从同一分布函数（V链接）产生的概率。
• k最近邻图上的度数和度数的乘积（图形度链接）。^[9]
• 合并两个聚类后，某个聚类描述符的增量（即，定义用于测量聚类质量的数量）。^{[10] [11] [12]}

讨论区

分层聚类具有明显的优势，即可以使用任何有效的距离度量。实际上，不需要观察本身：所使用的只是距离矩阵。

聚集聚类示例

例如，假设要对该数据进行聚类，并且欧几里得距离是距离度量。

分层聚类树状图将如下所示：

以给定的高度切割树将以选定的精度进行分区聚类。在此示例中，从树状图的第二行开始（从顶部开始）剪切将产生簇{a} {bc} {de} {f}。在第三行之后剪切将产生簇{a} {bc} {def}，这是一个较粗糙的簇，数量较少但簇较大。

该方法通过逐步合并群集，从单个元素构建层次结构。在我们的示例中，我们有六个元素{a} {b} {c} {d} {e}和{f}。第一步是确定要在集群中合并的元素。通常，我们要根据所选距离取两个最接近的元素。

任选地，还可以构造一个距离矩阵在此阶段，其中在数我个行Ĵ第列之间的距离我和第Ĵ个元素。然后，随着聚类的进行，合并聚类并更新距离时，行和列将合并。这是实现这种类型的群集的常用方法，并且具有在群集之间缓存距离的优势。单链接聚类页面中描述了一种简单的聚类聚类算法；它可以轻松地适应不同类型的链接（请参见下文）。

假设我们已经合并了两个最接近的元素b和c，我们现在具有以下群集{ a }，{ b，c }，{ d }，{ e }和{ f }，并希望进一步合并它们。为此，我们需要取{a}和{bc}之间的距离，从而定义两个聚类之间的距离。通常两个集群之间的距离${\ displaystyle {\ mathcal {A}}}$ 和 ${\ displaystyle {\ mathcal {B}}}$ 是以下之一：

• 每个群集的元素之间的最大距离（也称为完全链接群集）：

${\ displaystyle \ max \ {\，d（x，y）：x \ in {\ mathcal {A}}，\，y \ in {\ mathcal {B}} \，\}。}$

• 每个群集的元素之间的最小距离（也称为单链接群集）：

${\ displaystyle \ min \ {\，d（x，y）：x \ in {\ mathcal {A}}，\，y \ in {\ mathcal {B}} \，\}。}$

• 每个聚类元素之间的平均距离（也称为平均链接聚类，例如在UPGMA中使用）：

${\ displaystyle {1 \ over {| {\ mathcal {A}} | \ cdot | {\ mathcal {B}} |}}} \ sum _ {x \ in {\ mathcal {A}}} \ sum _ {y \ in {\ mathcal {B}}} d（x，y）。}$

• 所有集群内方差的总和。
• 被合并集群的方差增加（Ward方法^[8]）
• 候选群集从同一分布函数（V链接）产生的概率。

如果绑在一起的最小距离是随机选择的，则可以生成几个结构上不同的树状图。或者，所有捆绑对可以同时连接，生成唯一的树状图。^[13]

当群集数量足够少时（数量标准），您总是可以决定停止群集。某些链接还可以确保团簇之间的聚集比以前的团聚发生在更大的距离，然后当团簇之间的距离太远而无法合并时，可以停止团聚（距离标准）。但是，例如质心链接就不是这种情况，其中可能会发生所谓的逆转^[14]（反转，偏离超测量性）。

分裂聚类

分裂聚类的基本原理以DIANA（分裂聚类分析聚类）算法发布。^[15]最初，所有数据都在同一群集中，并且最大的群集被拆分，直到每个对象都分离。因为存在${\ displaystyle O（2 ^ {n}）}$分割每个集群的方法，需要启发式。DIANA选择平均差异最大的对象，然后将所有与新群集相似的对象移至该群集，而不是其余对象。

软件

开源实现

• ALGLIB在C ++和C＃中使用O（n²）内存和O（n³）运行时间实现了几种分层聚类算法（单链接，完整链接，Ward）。
• ELKI包括多个分层聚类算法，各种链接策略，还包括高效的SLINK，^[3] CLINK ^[4]和Anderberg算法，从树状图灵活提取聚类以及其他各种聚类分析算法。
• Octave是MATLAB的GNU类似物，它在函数“链接”中实现了分层聚类。
• 数据挖掘软件套件Orange包含具有交互式树状图可视化功能的分层聚类。
• R有许多提供分层聚类功能的软件包。
• SciPy在Python中实现了分层群集，包括高效的SLINK算法。
• scikit-learn还使用Python实现了分层集群。
• Weka包括层次聚类分析。

商业实施

• MATLAB包括层次聚类分析。
• SAS在PROC CLUSTER中包括层次聚类分析。
• Mathematica包含一个层次聚类程序包。
• NCSS包括层次聚类分析。
• SPSS包括层次聚类分析。
• Qlucore Omics Explorer包括层次聚类分析。
• Stata包括层次聚类分析。
• CrimeStat包含一个最近邻层次聚类算法，该算法具有地理信息系统的图形输出。

也可以看看

参考文献

进一步阅读

• 考夫曼湖；Rousseeuw，PJ（1990）。在数据中查找组：聚类分析简介（第1版）。纽约：约翰·威利（John Wiley）。书号 0-471-87876-6。
• Hastie，Trevor；罗伯特·蒂布希拉尼（Tibshirani）；弗里德曼，杰罗姆（2009）。“ 14.3.12层次聚类”。统计学习的要素（第二版）。纽约：施普林格。第520–528页。书号 978-0-387-84857-0。（原始内容 存档于（PDF） 2009-11-10）。检索2009-10-20。