14

私は大量の多次元ベクトルに対する階層的凝集クラスタリングに取り組んでいますが、最大のボトルネックは距離行列の構築であることに気付きました。このタスクの単純な実装は次のとおりです (ここでは Python)。

''' v = an array (N,d), where rows are the observations
and columns the dimensions'''
def create_dist_matrix(v):
   N = v.shape[0]
   D = np.zeros((N,N))
   for i in range(N):
      for j in range(i+1):
          D[i,j] = cosine(v[i,:],v[j,:]) # scipy.spatial.distance.cosine()
   return D

このルーチンにいくつかの並列処理を追加する最良の方法はどれだろうと考えていました。簡単な方法は、外側のループを分割して多数のジョブに割り当てることです。たとえば、プロセッサが 10 個ある場合、さまざまな範囲の 10 個の異なるジョブを作成しi、結果を連結します。ただし、この「水平」ソリューションはまったく正しくないようです。このタスク用の他の並列アルゴリズム (または既存のライブラリ) はありますか? どんな助けでも大歓迎です。

4

5 に答える 5

19

pairwise_distancesscikit-learnと呼ばれる pdist の並列バージョンがあるように見えます

from sklearn.metrics.pairwise import pairwise_distances

D = pairwise_distances(X = v, metric = 'cosine', n_jobs = -1)

wheren_jobs = -1は、すべての CPU が使用されることを指定します。

于 2015-04-15T00:06:04.173 に答える
2

モジュールよりpdistも速く取得できるとは思えません。scipyと言われているのはおそらくこのためです。

このライブラリで定義されている距離関数のいずれかに参照を渡さないようにする必要があることに注意してください。例えば、：

dm = pdist(X, sokalsneath)

Python 関数 sokalsneath を使用して、X のベクトル間のペアごとの距離を計算します。これにより、sokalsneath が n choose 2 回呼び出されることになり、非効率的です。代わりに、最適化された C バージョンの方が効率的であり、次の構文を使用して呼び出します。

dm = pdist(X, 'sokalsneath')
したがって、を使用する場合、Python 関数は使用されませんpdist(X, 'cosine')。実行すると、1つのコアしか使用しないように見えるので、コアが多い場合は高速になる可能性があります. ただし、これを実現するには、ネイティブ実装が SciPy と同じくらい高速でなければならないことに注意してください。それは些細なことではありません。我慢するか、空間インデックスをサポートするアルゴリズムなど、別のクラスタリング方法を使用することをお勧めします。

于 2014-01-31T13:30:35.813 に答える