Xây dựng song song ma trận khoảng cách

Question

Tôi làm việc trên phân cụm kết tụ phân cấp trên số lượng lớn vectơ đa chiều, và tôi nhận thấy rằng nút cổ chai lớn nhất là việc xây dựng ma trận khoảng cách. Một thực hiện ngây thơ cho nhiệm vụ này là như sau (ở đây trong 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 

tôi đã tự hỏi đó là cách tốt nhất để thêm một số xử lý song song để thói quen này. Một cách dễ dàng là phá vỡ và gán vòng lặp ngoài cho một số công việc, ví dụ: nếu bạn có 10 bộ vi xử lý, hãy tạo 10 công việc khác nhau cho các phạm vi khác nhau của i và sau đó ghép nối các kết quả. Tuy nhiên giải pháp "ngang" này có vẻ không đúng. Có bất kỳ thuật toán song song nào khác (hoặc các thư viện hiện có) cho tác vụ này không? Bất cứ sự giúp đỡ nào cũng được đánh giá cao.

Answer 1

Tôi nghi ngờ bạn sẽ nhận được nó nhanh hơn pdist trong mô-đun scipy. Có lẽ đây là lý do tại sao nó nói

Lưu ý rằng bạn nên tránh đi qua một tham chiếu đến một trong các chức năng khoảng cách quy định tại thư viện này. Ví dụ ,:

dm = pdist(X, sokalsneath) 

sẽ tính toán khoảng cách cặp-khôn ngoan giữa các vectơ trong X sử dụng chức năng Python sokalsneath. Điều này sẽ dẫn đến sokalsneath được gọi là n chọn 2 lần, trong đó không hiệu quả. Thay vào đó, phiên bản C tối ưu hóa là hơn hiệu quả, và chúng tôi gọi nó bằng cách sử dụng cú pháp sau .:

dm = pdist(X, 'sokalsneath') 

Vì vậy, không có chức năng Python được sử dụng, nếu bạn sử dụng pdist(X, 'cosine'). Khi tôi chạy nó, với tôi có vẻ như, nó chỉ sử dụng một lõi, vì vậy nếu bạn có rất nhiều lõi, bạn có thể làm cho nó nhanh hơn. Nhưng nhớ rằng, để đạt được điều này, việc thực hiện bản địa của bạn phải nhanh như SciPy. Điều đó sẽ không tầm thường. Bạn muốn kiên nhẫn hơn hoặc đi theo một phương pháp phân cụm khác, e. g. một thuật toán hỗ trợ chỉ mục không gian.

Answer 2

Hình như scikit-learn có một phiên bản song song của pdist gọi pairwise_distances

from sklearn.metrics.pairwise import pairwise_distances 

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

nơi n_jobs = -1 quy định rằng tất cả các CPU sẽ được sử dụng.

Answer 3

Xem @agartland trả lời — bạn có thể chỉ định n_jobs trong sklearn.metrics.pairwise.pairwise_distances hoặc tìm kiếm thuật toán phân nhóm tại sklearn.cluster với n_jobs tham số. Ví dụ. sklearn.cluster.KMeans.

Tuy nhiên, nếu bạn cảm thấy mạo hiểm, bạn có thể thực hiện tính toán của riêng mình. Ví dụ, nếu bạn cần ma trận khoảng cách 1D cho scipy.cluster.hierarchy.linkage bạn có thể sử dụng:

#!/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") 

Chỉ cần để bạn biết, scipy.cluster.hierarchy.linkage thực hiện được không song song và tính phức tạp của nó là ít nhất O (N * N). Tôi không chắc chắn nếu scipy có thực hiện song song chức năng này.

Answer 4

Nếu bạn quyết định tự dàn xếp quá trình đa xử lý, bạn có thể muốn chia số phép tính đồng đều giữa các CPU để rút ngắn tối đa các phép tính. Sau đó, các câu trả lời cho this question on equally splitting the diagonal matrix có thể hữu ích.