3

5 つのポイントがあり、これらからデンドログラムを作成する必要があります。以下に示すように、関数「デンドログラム」を使用して、これらの点の順序を見つけることができます。ただし、樹状図は遅く、多数のポイントでエラーが発生するため、使用したくありません (この質問は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']
>>>
4

2 に答える 2

10

scipy で線形化された葉の注文を計算するための専用関数があります。ここにあります。scipy.cluster.hierarchy.leaves_list .

于 2015-05-26T21:44:07.763 に答える
3

なぜ遅いのですか？確かに、リンケージ クラスタリングを計算する単純な方法は次のとおりです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 に)

ただし、視覚化のための 1 次元の順序付けではなく、リンク距離によって順序付けられる場合があります (リンケージ クラスタリングを使用する誰もが後でデンドログラムの視覚化を実行したいとは思わないため)。しかし、いずれにせよ、樹状図の計算は、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)それを複雑にするための非常にトリッキーなアルゴリズム (SLINK) がいくつかあります。しかし、より複雑ではない、より最新で強力なクラスタリング アルゴリズムがあります。実際、OPTICS (ウィキペディア)は非常によく似たものを計算し (minPts=2 を設定した場合)、適切なインデックス構造がある場合は で実行されO(n log n)ます。さらに、minPts を増やして、より意味のあるクラスターを取得できます。(しかし、Weka で OPTICS を使用したり、周りに出回っているその python バージョンを使用したりしないでください - どちらも不完全またはバグがあることを知ってください!)

于 2012-09-25T06:18:55.107 に答える