我有五个点，我需要从这些点创建树状图。函数"树状图"可用于查找这些点的顺序，如下所示。然而，我不想使用树状图，因为它很慢，会导致大量点的错误(我在这里问了这个问题，Python是找到树状图的另一种方法)。有人能告诉我如何将"链接"输出(Z)转换为"树状图(Z)['ivl']"值吗。
>>> from hcluster import pdist, linkage, dendrogram
>>> import numpy
>>> from numpy.random import rand
>>> x = rand(5,3)
>>> Y = pdist(x)
>>> Z = linkage(Y)
>>> Z
array([[ 1. , 3. , 0.11443378, 2. ],
[ 0. , 4. , 0.47941843, 2. ],
[ 5. , 6. , 0.67596472, 4. ],
[ 2. , 7. , 0.79993986, 5. ]])
>>>
>>> dendrogram(Z)['ivl']
['2', '1', '3', '0', '4']
>>>
scipy中有一个用于计算线性化叶序的专用函数。这是.scipy.cluster.hierarchy.leaves_list.
为什么速度慢？当然，计算链接聚类的天真方法是O(n^3)，但对于n=5来说，这是最便宜的。。。
有关scipy链接矩阵的格式，请参阅此问题：scipy链接格式
请注意，您可能仍然需要对数据进行最佳排序。上面的链接矩阵编码给出
- 元素1和簇3在高度0.1144处连接(成为一个2元素簇，#5)
- 元素0和簇4在高度0.7999处连接(成为一个2元素簇，#6)
- 簇5和簇6在高度0.6759处连接(形成一个4元素簇，#7)
- 元素2和簇7在高度0.7999处连接(形成一个5元素簇，#8)
但它可能是按链接距离排序的，而不是按可视化的1d排序(因为不是每个使用链接聚类的人都想在之后运行树状图可视化)。但无论如何，如果您确实需要排序，那么计算树状图的数量级应该是O(n log n)，与实际聚类相比相当便宜。
沿着这些路线的东西应该能起到作用：
n = len(Z) + 1
cache = dict()
for k in range(len(Z)):
c1, c2 = int(Z[k][0]), int(Z[k][1])
c1 = [c1] if c1 < n else cache.pop(c1)
c2 = [c2] if c2 < n else cache.pop(c2)
cache[n+k] = c1 + c2
print cache[2*len(Z)]
这可能看起来是线性的，但数组的预期大小是log n，因此根据您的列表类型，它可能仍然是O(n log n)，而对于链表，它在O(n)中确实是可行的。
但最终，您可能希望避免分层集群。它是聚类分析的一个流行的入门示例，因为它在概念上很容易理解。有一些相当棘手的算法(SLINK)可以将其降低到O(n^2)的复杂性。但是，还有更现代、更强大的聚类算法具有更低的复杂性。事实上，OPTICS(维基百科)计算的内容非常相似(当你设置minPts=2时)，当你有一个好的索引结构时，它将在O(n log n)中运行。此外，您可以增加minPts以获得更有意义的簇。(但不要在Weka中使用OPTICS，也不要使用四处浮动的python版本，因为它们都不完整或有缺陷！)