एक दूरी मैट्रिक्स के समानांतर निर्माण

Question

मैं बड़ी मात्रा में बहुआयामी वैक्टरों पर पदानुक्रमित agglomerative क्लस्टरिंग पर काम करते हैं, और मैंने देखा कि सबसे बड़ी बाधा दूरी मैट्रिक्स का निर्माण है।

''' 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) 

एक्स अजगर समारोह sokalsneath का उपयोग कर में वैक्टर के बीच जोड़ी के लिहाज से दूरी की गणना होगी। इसके परिणामस्वरूप सोक्लसेनाथ को 2 बार चुना जा सकता है, जो अक्षम है। इसके बजाय, अनुकूलित सी संस्करण अधिक कुशल है, और हम निम्न सिंटैक्स .:

dm = pdist(X, 'sokalsneath') 

तो कोई अजगर समारोह प्रयोग किया जाता है का उपयोग कर इसे कहते हैं, अगर आप pdist(X, 'cosine') का उपयोग करें। जब मैं इसे चलाता हूं, तो ऐसा लगता है कि यह केवल एक कोर का उपयोग करता है, इसलिए यदि आपके पास बहुत सारे कोर हैं, तो आप इसे तेज़ी से प्राप्त कर सकते हैं। लेकिन ध्यान रखें, कि इसे प्राप्त करने के लिए, आपके मूल कार्यान्वयन को साइपी के जितना तेज़ होना चाहिए। वह तुच्छ नहीं होगा। आप बल्कि धैर्य रखें या एक अलग क्लस्टरिंग विधि के लिए जाओ, ई। जी। एक एल्गोरिदम जो स्थानिक सूचकांक का समर्थन करता है।

Answer 2

लगता scikit-learnpairwise_distances

from sklearn.metrics.pairwise import pairwise_distances 

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

कहा जाता है जहां n_jobs = -1 निर्दिष्ट करता है कि सभी सीपीयू उपयोग किया जाएगा pdist के एक समानांतर संस्करण है की तरह।

Answer 3

देखें @agartland — का जवाब आप sklearn.metrics.pairwise.pairwise_distances में n_jobs तैयार करें या n_jobs पैरामीटर के साथ sklearn.cluster पर एल्गोरिथ्म क्लस्टरिंग के लिए देख सकते हैं। ई जी sklearn.cluster.KMeans।

फिर भी, यदि आप साहसी महसूस करते हैं, तो आप अपनी गणना को कार्यान्वित कर सकते हैं। उदाहरण के लिए, यदि आप scipy.cluster.hierarchy.linkage के लिए 1 डी दूरी मैट्रिक्स की जरूरत है आप का उपयोग कर सकते हैं:

#!/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 कार्यान्वयन समानांतर नहीं है और इसकी जटिलता कम से कम हे (एन * एन) है। मुझे यकीन नहीं है कि scipy में इस फ़ंक्शन के समानांतर कार्यान्वयन हैं।

Answer 4

यदि आप अपने द्वारा मल्टीप्रोसेसिंग को ऑर्केस्ट्रेट करने का निर्णय लेते हैं तो आप सीपीयू के बीच समान रूप से गणनाओं की संख्या को विभाजित करना चाहते हैं ताकि गणना को अधिकतम रूप से छोटा कर दिया जा सके। फिर this question on equally splitting the diagonal matrix का जवाब आसान हो सकता है।