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 回答
4

请参阅@agartland 答案-您可以在 sklearn.metrics.pairwise.pairwise_distances 中指定或n_jobs在sklearn.cluster中查找带有n_jobs参数的聚类算法。例如。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有此功能的并行实现。

于 2017-08-14T13:14:40.787 回答
2

我怀疑你会比pdist在scipy模块中更快地获得它。可能这就是为什么它说

请注意，您应该避免传递对此库中定义的距离函数之一的引用。例如，：

dm = pdist(X, sokalsneath)

将使用 Python 函数 sokalsneath 计算 X 中向量之间的成对距离。这将导致 sokalsneath 被调用 n 次选择 2 次，这是低效的。相反，优化后的 C 版本效率更高，我们使用以下语法调用它：

dm = pdist(X, 'sokalsneath')
因此，如果您使用pdist(X, 'cosine'). 当我运行它时，在我看来，它只使用一个核心，所以如果你有很多核心，你可能会更快。但请记住，要实现这一点，您的本机实现必须与 SciPy 的一样快。这不会是微不足道的。您宁愿耐心等待或采用不同的聚类方法，例如支持空间索引的算法。

于 2014-01-31T13:30:35.813 回答
2

除了@agartland 提出的建议之外，我还喜欢使用pairwise_distances或pairwise_disances_chunked使用numpy.triu_indices来获得压缩距离向量。这是由提供的确切输出scipy.spatial.distance.pdist

重要的是要注意用于控制对角线偏移的kkwarg 。triu_indices默认值k=0将返回零的对角线以及实际距离值，应设置k=1为避免这种情况。

对于大型数据集，我遇到了从工作线程返回值时pairwise_distances引发ValueErrorfrom的问题。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，因为文档在某一时刻表明用户可以传递一个压缩的或方形的距离向量/矩阵（linkage() 函数将距离矩阵错误为观察向量#2614）。事实上并非如此，传递给链接的值应该是压缩距离向量或原始观测值的 mxn 数组。

于 2019-05-01T17:46:54.863 回答
0

如果您决定自己编排多处理，您可能希望在 CPU 之间平均分配计算数量，以便最大限度地缩短计算时间。然后回答这个关于等分对角矩阵的问题可能会派上用场。

于 2018-01-22T16:23:47.340 回答