linkage#
- scipy.cluster.hierarchy.linkage(y, method='single', metric='euclidean', optimal_ordering=False)[源代码]#
执行分层/凝聚式聚类。
输入 y 可以是 1-D 凝聚距离矩阵，也可以是 2-D 观测向量数组。
如果 y 是 1-D 凝聚距离矩阵，则 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\) x \(n\) 数组。压缩距离矩阵的所有元素必须是有限的，即没有 NaN 或 inf。- methodstr，可选
要使用的连锁算法。有关完整说明，请参阅下面的
连锁 方法部分。- metricstr 或函数，可选
当 y 是观测向量的集合时要使用的距离度量；否则将其忽略。有关有效距离度量的列表，请参阅
pdist函数。还可以使用自定义距离函数。- optimal_orderingbool，可选
如果为 True，将重新排列连锁矩阵，以便连续叶之间的距离最小。当可视化数据时，这将生成更直观的树形结构。默认为 False，因为此算法可能很慢，尤其是在处理大型数据集时 [2]。另请参阅
optimal_leaf_ordering函数。1.0.0 版本中添加。
- 返回:
- Zndarray
以连锁矩阵形式编码的层次聚类。
请参阅
注释
对于“single”方法，实现了基于最小生成树的优化算法。它的时间复杂度为\(O(n^2)\)。对于“complete”、“average”、“weighted”和“ward”方法，实现了一个称为最近邻链的算法。它还具有 \(O(n^2)\) 的时间复杂度。对于其他方法，实现了一个具有 \(O(n^3)\) 时间复杂度的朴素算法。所有算法均使用 \(O(n^2)\) 内存。有关算法的详细信息，请参阅[1]。
仅当使用欧氏成对度量时，才正确定义“centroid”、“median”和“ward”方法。如果y传入的为预先计算的成对距离，则用户有责任确保这些距离实际上为欧氏距离，否则产生的结果将不正确。
参考
[1]Daniel Mullner，“现代层次聚类算法”，arXiv:1109.2378v1.
[2]Ziv Bar-Joseph、David K. Gifford、Tommi S. Jaakkola，“层次聚类的快速最优叶级排序”，2001。生物信息学DOI:10.1093/bioinformatics/17.suppl_1.S22
实例
>>> 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()
