scipy.cluster.hierarchy.

链接

scipy.cluster.hierarchy.linkage(y, method='single', metric='euclidean', optimal_ordering=False)

执行层次/凝聚聚类。

输入 y 可以是一个一维的压缩距离矩阵，或者是一个二维的观测向量数组。

如果 y 是一个一维的压缩距离矩阵，那么 y 必须是一个大小为 \(\binom{n}{2}\) 的向量，其中 n 是距离矩阵中配对的原始观测值的数量。这个函数的行为与 MATLAB 的 linkage 函数非常相似。

返回一个 \((n-1)\) 行 4 列的矩阵 Z。在第 \(i\) 次迭代中，索引为 Z[i, 0] 和 Z[i, 1] 的簇被合并以形成簇 \(n + i\)。索引小于 \(n\) 的簇对应于 \(n\) 个原始观测值之一。簇 Z[i, 0] 和 Z[i, 1] 之间的距离由 Z[i, 2] 给出。第四个值 Z[i, 3] 表示新形成的簇中的原始观测值数量。

以下链接方法用于计算两个簇 \(s\) 和 \(t\) 之间的距离 \(d(s, t)\)。算法从一个尚未用于形成层次结构的簇森林开始。当森林中的两个簇 \(s\) 和 \(t\) 被合并成一个单一的簇 \(u\) 时，\(s\) 和 \(t\) 从森林中移除，并且 \(u\) 被添加到森林中。当森林中只剩下一个簇时，算法停止，这个簇成为根。

在每次迭代中都维护一个距离矩阵。d[i,j] 条目对应于原始森林中簇 \(i\) 和 \(j\) 之间的距离。

在每次迭代中，算法必须更新距离矩阵，以反映新形成的集群 u 与森林中剩余集群之间的距离。

假设在簇 \(u\) 中有 \(|u|\) 个原始观测值 \(u[0], \ldots, u[|u|-1]\)，在簇 \(v\) 中有 \(|v|\) 个原始对象 \(v[0], \ldots, v[|v|-1]\)。回顾一下，\(s\) 和 \(t\) 被合并形成簇 \(u\)。设 \(v\) 是森林中除 \(u\) 以外的任意剩余簇。

以下是计算新形成的簇 \(u\) 与每个 \(v\) 之间距离的方法。

• method=’single’ 分配

  \[d(u,v) = \min(dist(u[i],v[j]))\]

  对于簇 \(u\) 中的所有点 \(i\) 和簇 \(v\) 中的所有点 \(j\)。这也被称为最近点算法。

• method=’complete’ 分配

  \[d(u, v) = \max(dist(u[i],v[j]))\]

  对于簇 u 中的所有点 \(i\) 和簇 \(v\) 中的所有点 \(j\)。这也被称为最远点算法或 Voor Hees 算法。

• method=’average’ 分配

  \[d(u,v) = \sum_{ij} \frac{d(u[i], v[j])} {(|u|*|v|)}\]

  对于所有点 \(i\) 和 \(j\) ，其中 \(|u|\) 和 \(|v|\) 分别是簇 \(u\) 和 \(v\) 的基数。这也被称为 UPGMA 算法。

• method=’weighted’ 分配

  \[d(u,v) = (dist(s,v) + dist(t,v))/2\]

  其中簇 u 是由簇 s 和 t 形成的，而 v 是森林中剩余的簇（也称为 WPGMA）。

• method=’centroid’ 分配

  \[dist(s,t) = ||c_s-c_t||_2\]

  其中 \(c_s\) 和 \(c_t\) 分别是簇 \(s\) 和 \(t\) 的质心。当两个簇 \(s\) 和 \(t\) 合并成一个新的簇 \(u\) 时，新的质心是计算在簇 \(s\) 和 \(t\) 中的所有原始对象上的。距离则变为 \(u\) 的质心与森林中剩余簇 \(v\) 的质心之间的欧几里得距离。这也被称为 UPGMC 算法。

• method=’median’ 分配 \(d(s,t)\) 类似于 centroid 方法。当两个簇 \(s\) 和 \(t\) 合并成一个新的簇 \(u\) 时，质心 s 和 t 的平均值给出新的质心 \(u\)。这也被称为 WPGMC 算法。

• method=’ward’ 使用 Ward 方差最小化算法。新的条目 \(d(u,v)\) 计算如下，

  \[d(u,v) = \sqrt{\frac{|v|+|s|}{T}d(v,s)^2 + \frac{|v|+|t|}{T}d(v,t)^2 - \frac{|v|}{T}d(s,t)^2}\]

  其中 \(u\) 是新加入的由簇 \(s\) 和 \(t\) 组成的簇，\(v\) 是森林中未使用的簇，\(T=|v|+|s|+|t|\)，而 \(|*|\) 是其参数的基数。这也被称为增量算法。

警告：当选择森林中的最小距离对时，可能存在两个或更多对具有相同的最小距离。此实现可能选择与 MATLAB 版本不同的最小值。

参数:

yndarray

一个压缩的距离矩阵。压缩的距离矩阵是一个包含距离矩阵上三角部分的扁平数组。这是 pdist 返回的形式。或者，可以传递一个包含 \(m\) 个观测向量在 \(n\) 维空间中的 \(m\) 乘以 \(n\) 的数组。压缩距离矩阵中的所有元素必须是有限的，即没有 NaNs 或 infs。

方法str, 可选

要使用的链接算法。有关完整描述，请参见下面的 链接方法 部分。

指标str 或 function，可选

在 y 是观测向量集合的情况下使用的距离度量；否则忽略。查看 pdist 函数以获取有效的距离度量列表。也可以使用自定义距离函数。

optimal_orderingbool, 可选

如果为True，链接矩阵将被重新排序，使得连续叶子之间的距离最小化。这使得数据在可视化时具有更直观的树结构。默认为False，因为此算法可能会很慢，特别是在大型数据集上 [2]。另请参见 optimal_leaf_ordering 函数。

Added in version 1.0.0.

返回:

Zndarray

编码为链接矩阵的层次聚类。

参见

scipy.spatial.distance.pdist

成对距离度量

注释

1. 对于方法 ‘single’，实现了一个基于最小生成树的优化算法。它的时间复杂度为 \(O(n^2)\)。对于方法 ‘complete’、’average’、’weighted’ 和 ‘ward’，实现了一个称为最近邻链的算法。它的时间复杂度也是 \(O(n^2)\)。对于其他方法，实现了一个时间复杂度为 \(O(n^3)\) 的朴素算法。所有算法都使用 \(O(n^2)\) 的内存。有关算法的详细信息，请参阅 [1]。

2. 方法 ‘centroid’、’median’ 和 ‘ward’ 只有在使用欧几里得成对度量时才能正确地定义。如果将 y 作为预计算的成对距离传递，那么用户有责任确保这些距离实际上是欧几里得的，否则产生的结果将是不正确的。

参考文献

[1]

Daniel Mullner, “现代层次聚类算法”, arXiv:1109.2378v1.

[2]

Ziv Bar-Joseph, David K. Gifford, Tommi S. Jaakkola, “快速最优叶序排列用于层次聚类”, 2001. Bioinformatics DOI:10.1093/bioinformatics/17.suppl_1.S22

示例

Try it in your browser!

>>> from scipy.cluster.hierarchy import dendrogram, linkage
>>> from matplotlib import pyplot as plt
>>> X = [[i] for i in [2, 8, 0, 4, 1, 9, 9, 0]]

>>> Z = linkage(X, 'ward')
>>> fig = plt.figure(figsize=(25, 10))
>>> dn = dendrogram(Z)

>>> Z = linkage(X, 'single')
>>> fig = plt.figure(figsize=(25, 10))
>>> dn = dendrogram(Z)
>>> plt.show()

Go BackOpen In Tab