距離矩陣的並行構造

Question

我在大量的多維向量上進行層次凝聚聚類，我注意到最大的瓶頸是構建距離矩陣。完成這個任務，幼稚的做法是以下（在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個處理器，請爲i的不同範圍創建10個不同的作業，然後連接結果。然而，這種「水平」解決方案看起來不太正確。是否有任何其他並行算法（或現有庫）用於此任務？任何幫助將不勝感激。

Answer 1

我懷疑你會在scipy模塊中得到比pdist更快的速度。也許這就是爲什麼它說

需要注意的是，你應該避免將一個參考的 一個在該庫中定義的距離函數。例如，：

dm = pdist(X, sokalsneath) 

將X使用Python函數sokalsneath計算 向量之間的逐對距離。這會導致被稱爲n的選擇2次，其中 效率低下。相反，優化的C版本更 高效，我們稱之爲使用以下語法：

dm = pdist(X, 'sokalsneath') 

所以不使用Python的功能，如果你使用 pdist(X, 'cosine')。當我運行它時，對我來說似乎只使用一個內核，所以如果你有很多內核，你可能會更快。但要記住，要實現這一點，您的本機實現必須與SciPy一樣快。這不會是微不足道的。你寧願耐心或者採用不同的聚類方法，例如， G。一種支持空間索引的算法。

Answer 2

看起來scikit-learn具有pdist的並行版本稱爲pairwise_distances

from sklearn.metrics.pairwise import pairwise_distances 

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

其中n_jobs = -1規定，所有的CPU將被使用。

Answer 3

見@agartland回答—您可以在sklearn.metrics.pairwise.pairwise_distances指定n_jobs或n_jobs參數尋找聚類算法在sklearn.cluster。例如， sklearn.cluster.KMeans。

不過，如果你覺得冒險，你可以實現自己的計算。例如，如果你需要一維距離矩陣爲scipy.cluster.hierarchy.linkage你可以使用：

#!/usr/bin/env python3 
from multiprocessing import Pool 
import numpy as np 
from time import time as ts 


data = np.zeros((100,10)) # YOUR data: np.array[n_samples x m_features] 
n_processes = 4   # YOUR number of processors 
def metric(a, b):   # YOUR dist function 
    return np.sum(np.abs(a-b)) 


n = data.shape[0] 
k_max = n * (n - 1) // 2 # maximum elements in 1D dist array 
k_step = n ** 2 // 500 # ~500 bulks 
dist = np.zeros(k_max) # resulting 1D dist array 


def proc(start): 
    dist = [] 
    k1 = start 
    k2 = min(start + k_step, k_max) 
    for k in range(k1, k2): 
     # get (i, j) for 2D distance matrix knowing (k) for 1D distance matrix 
     i = int(n - 2 - int(np.sqrt(-8 * k + 4 * n * (n - 1) - 7)/2.0 - 0.5)) 
     j = int(k + i + 1 - n * (n - 1)/2 + (n - i) * ((n - i) - 1)/2) 
     # store distance 
     a = data[i, :] 
     b = data[j, :] 
     d = metric(a, b) 
     dist.append(d) 
    return k1, k2, dist 


ts_start = ts() 
with Pool(n_processes) as pool: 
    for k1, k2, res in pool.imap_unordered(proc, range(0, k_max, k_step)): 
     dist[k1:k2] = res 
     print("{:.0f} minutes, {:,}..{:,} out of {:,}".format(
      (ts() - ts_start)/60, k1, k2, k_max)) 


print("Elapsed %.0f minutes" % ((ts() - ts_start)/60)) 
print("Saving...") 
np.savez("dist.npz", dist=dist) 
print("DONE") 

只要你知道，scipy.cluster.hierarchy.linkage執行不平行和它的複雜性至少是O（N * N）。我不確定scipy是否具有此功能的並行實現。

Answer 4

如果您決定親自協調多處理，您可能需要在CPU之間平均分配計算次數，以最大限度地縮短計算時間。然後回覆this question on equally splitting the diagonal matrix可能會得心應手。