scipy.cluster.hierarchy.linkage¶
- scipy.cluster.hierarchy.linkage(y, method='single', metric='euclidean', optimal_ordering=False)[源代码]¶
执行分层/聚集群集。
输入y可以是一维浓缩距离矩阵或观察向量的二维阵列。
如果y是一维凝聚距离矩阵，则y一定是 \(\binom{{n}}{{2}}\) 调整大小的向量，其中n是距离矩阵中成对的原始观测值的数量。此函数的行为与MATLAB链接函数非常相似。
A \((n-1)\) 乘以4矩阵
Z返回。在 \(i\) -第4次迭代，带索引的群集Z[i, 0]和Z[i, 1]组合成簇 \(n + i\) 。索引小于 \(n\) 对应于 \(n\) 原始的观察结果。群集之间的距离Z[i, 0]和Z[i, 1]由以下人员提供Z[i, 2]。第四个值Z[i, 3]表示新形成的簇中的原始观测值的数量。以下链接方法用于计算距离 \(d(s, t)\) 在两个群集之间 \(s\) 和 \(t\) 。该算法以尚未在层级结构中使用的簇林开始。当两个群集 \(s\) 和 \(t\) 从这个林中组合成一个单独的集群 \(u\) ， \(s\) 和 \(t\) 从森林中被移走，而且 \(u\) 被添加到森林中。当林中只剩下一个群集时，算法将停止，此群集将成为根。
在每次迭代中维护距离矩阵。这个
d[i,j]条目对应于群集之间的距离 \(i\) 和 \(j\) 在原始森林里。在每次迭代中，该算法必须更新距离矩阵以反映新形成的群集u与林中剩余群集的距离。
假设有 \(|u|\) 原始观测 \(u[0], \ldots, u[|u|-1]\) 在群集中 \(u\) 和 \(|v|\) 原始对象 \(v[0], \ldots, v[|v|-1]\) 在群集中 \(v\) 。回想一下， \(s\) 和 \(t\) 组合成簇 \(u\) 。让我们 \(v\) 是林中不是的任何剩余群集 \(u\) 。
以下是计算新形成的群集之间距离的方法 \(u\) 而且每个人 \(v\) 。
method=‘Single’赋值
\[D(u，v)=\min(距离(u [i] ，v [j] ))\]对于所有积分 \(i\) 在群集中 \(u\) 和 \(j\) 在群集中 \(v\) 。这也称为最近点算法。
method=‘Complete’赋值
\[D(u，v)=\max(距离(u [i] ，v [j] ))\]对于所有积分 \(i\) 在群集u中，并且 \(j\) 在群集中 \(v\) 。这也被称为最远点算法或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=‘加权’赋值
\[D(u，v)=(dist(s，v)+dist(t，v))/2\]其中群集u与群集s和t形成，并且v是林中剩余的群集(也称为WPGMA)。
method=‘centroid’赋值
\[距离(s，t)= ||c_s-c_t||_ 2\]哪里 \(c_s\) 和 \(c_t\) 是星团的质心 \(s\) 和 \(t\) ，分别为。当两个群集 \(s\) 和 \(t\) 组合成一个新的群集 \(u\) ，则对群集中的所有原始对象计算新质心 \(s\) 和 \(t\) 。然后，该距离就变成了…的质心之间的欧几里得距离。 \(u\) 以及剩余群集的质心 \(v\) 在森林里。这也称为UPGMC算法。
method=‘Medium’赋值 \(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 -\crc{ |v| } {T}d(s，t)^2}\]哪里 \(u\) 是由群集组成的新加入的群集 \(s\) 和 \(t\) ， \(v\) 是森林中的一个未使用的簇， \(T=|v|+|s|+|t|\) ，以及 \(|*|\) 是它的论点的基数。这也称为增量算法。
警告：选择林中的最小距离对时，可能有两个或更多对具有相同的最小距离。此实现可能选择与MATLAB版本不同的最小值。
- 参数
- yndarray
凝聚距离矩阵。压缩距离矩阵是包含距离矩阵的上三角形的平面阵列。这是一张表格，上面写着
pdist返回。或者，还可以使用 \(m\) 中的观测矢量 \(n\) 维度可以作为 \(m\) 通过 \(n\) 数组。压缩距离矩阵的所有元素必须是有限的，即没有NAN或INF。- method字符串，可选
要使用的链接算法。请参阅
Linkage Methods有关详细说明，请参阅下面的部分。- metric字符串或函数，可选
在y是观测向量集合的情况下使用的距离度量；否则忽略。请参阅
pdist函数获取有效距离度量列表。也可以使用自定义距离函数。- optimal_ordering布尔值，可选
如果为True，则链接矩阵将重新排序，以便连续叶之间的距离最小。当数据可视化时，这会产生更直观的树形结构。默认为FALSE，因为此算法可能会很慢，尤其是在大数据集上 [2]. 另请参阅
optimal_leaf_ordering功能。1.0.0 新版功能.
- 退货
- Zndarray
该分层聚类被编码为链接矩阵。
参见
注意事项
对于“单一”方法，实现了一种基于最小生成树的优化算法。它具有时间复杂性 \(O(n^2)\) 。对于“完全”、“平均”、“加权”和“Ward”方法，实现了最近邻链算法。它还具有时间复杂性。 \(O(n^2)\) 。对于其他方法，用以下方式实现朴素算法 \(O(n^3)\) 时间复杂性。所有算法都使用 \(O(n^2)\) 记忆。请参阅 [1] 有关算法的详细信息。
只有在使用欧几里得成对度量的情况下，才能正确定义方法“质心”、“中值”和“Ward”。如果 y 如果作为预先计算的成对距离传递，则用户有责任确保这些距离实际上是欧几里得距离，否则产生的结果将是不正确的。
参考文献
- 1
丹尼尔·穆尔纳，“现代分层凝聚聚类算法”， 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()
