距离矩阵的并联结构(Parallel construction of a distance matr

我对分层合并聚类工作在大量的多维矢量的，我注意到，最大的瓶颈是距离矩阵的建设。完成这个任务，幼稚的做法是下面的（这里在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 ，然后将结果连接。然而这个“水平”的解决方案似乎并不完全正确。是否有任何其他的并行算法（或现有的库）完成这个任务？任何帮助将高度赞赏。

Answer 1:

看起来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 2:

见@agartland答案-你可以指定n_jobs在sklearn.metrics.pairwise.pairwise_distances或寻找聚类算法sklearn.cluster与n_jobs参数。 E.克。 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 3:

我怀疑你会得到比任何更快pdist中scipy模块。也许这就是为什么它说

需要注意的是，你应该避免将一个参考的在这个库中定义的距离函数之一。例如，：

dm = pdist(X, sokalsneath)

使用Python函数sokalsneath将计算在X向量之间的逐对距离。这将导致sokalsneath被称为ň选择2倍，这是低效的。相反，优化的C版本更有效，我们称它为使用的语法如下：
  DM = pdist（X， 'sokalsneath'） 
因此，没有Python的功能时，如果你使用pdist(X, 'cosine') 当我运行它，我看来，它并只使用一个核心，所以如果你有很多核心的，你可能会更快地得到它。但要记住，是实现这一目标，您的本机实现必须以最快的速度SciPy的公司。这不会是微不足道的。你宁愿耐心等待或去一个不同的聚类方法，例如，它支持空间索引的算法。

Answer 4:

除了@agartland提出什么，我喜欢用pairwise_distances或pairwise_disances_chunked与numpy.triu_indices得到冷凝距离向量。这是通过提供的确切输出scipy.spatial.distance.pdist

要注意这一点很重要k为kwarg triu_indices控件对角线的偏移量。默认值为k=0将返回对角线零以及真正的距离值和应设置为k=1至避免这种情况。

对于大型数据集我也遇到过，其中一个问题pairwise_distances提出了一个ValueError从struct.unpack从工作线程返回值时。因此，我使用的pairwise_distances_chunked以下。

gen = pairwise_distances_chunked(X, method='cosine', n_jobs=-1)
Z = np.concatenate(list(gen), axis=0)
Z_cond = Z[np.triu_indices(Z.shape[0], k=1)

对我来说，这比使用快得多pdist和可用内核的数量比例很好。

注：我觉得这也是值得指出的是，有一个在过去关于赞成一些混乱scipy.cluster.hierarchy.linkage ，该文档在一个点上表示，用户可以通过一个压缩或squareform距离向量/矩阵（联动（）函数的错误距离矩阵作为观察矢量＃2614 ）。这实际上并非如此，并传递到连杆的值应为冷凝的距离矢量或原始观测的M×N阵列。