計算樹狀圖樹葉的排序

Question

我有五點，我需要從這些樹狀圖創建樹狀圖。可以使用「樹形圖」功能來查找這些點的排序，如下所示。但是，我不想使用樹形圖，因爲它很慢，並導致大量的點錯誤（我在這裏問這個問題Python alternate way to find dendrogram）。有人能指出我如何將「聯動」輸出（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 linkage format

請注意，您可能仍然需要優化分類數據。上述聯動矩陣編碼給出

• 元素1和第3組在高度0.1144加入（成2元件簇，＃5）
• 元0和羣4加入在高度0.7999（成2元件簇， ＃6）
• 羣集5和第6組加入在高度0.6759（入4元件簇，＃7）
• 元件2和第7組在高度0.7999（加入到一個5元簇，＃8）

但它可能是通過鏈接dist命令ance，而不是用於可視化的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 (Wikipedia)計算的東西非常相似（當您設置minPts = 2時），並且當您具有良好的索引結構時，它將在O(n log n)中運行。另外，您可以增加minPts以獲得更有意義的羣集。 （但是不要在Weka中使用OPTICS，也不要在Python中使用OPTICS，因爲它們都是不完整的或者錯誤的！）

Answer 2

在scipy中有一個用於計算線性化葉命令的專用函數。這裏是。 scipy.cluster.hierarchy.leaves_list。