计算树状叶序(Calculate ordering of dendrogram leaves )

我有五点，我需要从这些创造树状图。函数“树状图”可以用来找到这些点的顺序如下图所示。不过，我并不想用树状图，因为它是缓慢而导致错误的大量点（我在这里问这个问题， 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']
>>>

Answer 1:

为什么慢？当然，计算联动聚类的幼稚的方法是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）

但它可能会通过将距离在可视化一维顺序进行排序，而不是（因为使用联动群集不感到沉沦将要运行之后树状viusalization）。但是，以任何方式，计算树状应的量级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)

但最终，你可能希望避免分层聚类 。这是一个受欢迎的入门例子，聚类分析，因为这是很容易理解概念。有一些相当棘手的算法（偷偷）给它弄下来到O(n^2)的复杂性。但也有更现代和强大的聚类算法有更低的复杂性。事实上，光学（维基百科）计算颇为类似的东西（当你设置minPts = 2），当你有一个良好的索引结构将在运行O(n log n) 。另外，您还可以增加minPts获得更有意义的集群。（但不要在Weka中，或者是周围漂浮了Python版本中使用光学 - AFAICT它们是不完整或者有缺陷！）

Answer 2:

有在SciPy的计算线性叶订单的专用功能。这里是。 scipy.cluster.hierarchy.leaves_list 。