并行构造距离矩阵

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个处理器,则为不同的范围创建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)

where n_jobs = -1指定将使用所有CPU.

Answer 2

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

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

dm = pdist(X, sokalsneath)

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

dm = pdist(X, 'sokalsneath')

因此，如果您使用pdist(X, 'cosine'). 当我运行它时，对我来说，它似乎只使用一个核心，所以如果你有很多核心，你可能会更快。但请记住，要实现此目标，您的本机实现必须与 SciPy 一样快。这绝非小事。您宁愿耐心等待或选择不同的聚类方法，例如支持空间索引的算法。