解包稀疏矩阵性能调优

Question

我正在使用由 ING 的数据科学家创建的 sparse_dot_topn 库来搜索大量公司名称（近 150 万条记录）中的近似重复项。该库的最新更新现在可以使用多个线程来计算两个矩阵之间的叉积（即余弦相似度）。我运行一个快速基准测试，性能提升显着（取决于一个人可以在他的 machine/remote 服务器上使用多少个内核）：

+-----------+--------------+
| # threads | time (%M:%S) |
+-----------+--------------+
| 32        | 03:43:12     |
+-----------+--------------+
| 16        | 05:16:97     |
+-----------+--------------+
| 8         | 08:11:69     |
+-----------+--------------+
| 4         | 13:32:72     |
+-----------+--------------+
| 2         | 24:02:28     |
+-----------+--------------+
| 1         | 47:11:30     |
+-----------+--------------+

为了轻松探索结果，我需要解包生成的稀疏矩阵。幸运的是，我发现了以下由 Chris van den Berg 编写的辅助函数，它正是这样做的（link 至 Chris 的博客 post here）：

def get_matches_df(sparse_matrix, name_vector, top=100):
    non_zeros = sparse_matrix.nonzero()

    sparserows = non_zeros[0]
    sparsecols = non_zeros[1]

    if top:
        nr_matches = top
    else:
        nr_matches = sparsecols.size

    left_side = np.empty([nr_matches], dtype=object)
    right_side = np.empty([nr_matches], dtype=object)
    similairity = np.zeros(nr_matches)

    for index in range(0, nr_matches):
        left_side[index] = name_vector[sparserows[index]]
        right_side[index] = name_vector[sparsecols[index]]
        similairity[index] = sparse_matrix.data[index]

    return pd.DataFrame(
        {"left_side": left_side, "right_side": right_side, "similairity": similairity}
    )

上述函数有一个可选参数，仅查看第一个 n 个值，但我必须运行它查看完整数据。我目前的问题是这需要很长时间才能完成（大约 1 小时）。

问：我想知道如何提高此处的性能（如果可能）？特别是因为我有很多核心我没有用于这项工作。

我不是性能调优方面的专家。我探索的一种选择是 Numba。我用 @njit(parallel=True) 修饰函数并使用 Numba 的 prange 而不是 range 来指定循环可以并行化，但这失败了。我的理解是 Numba 无法处理字符串值（即我的公司名称）。

对于提高性能的可能方法的任何帮助，我们将不胜感激。

Answer 1

没有一些示例，我无法确定这就是您要查找的内容，但我认为这就是您想要的。我对您的示例中的 top 感到困惑，因为它只采用第一个结果而不是具有最大值的结果。

import pandas as pd
from scipy import sparse
import random
import string

arr = sparse.random(100,100,density=0.02).tocoo()
name_vec = pd.Series(''.join(random.choice(string.ascii_uppercase + string.digits) for _ in range(6)) for _ in range(100))

pd.DataFrame({"left_side": name_vec[arr.row].tolist(), 
              "right_side": name_vec[arr.col].tolist(), 
              "similairity": arr.data})

就运行时而言，您可以通过避免系列 -> 列表 -> 系列步骤来进一步清理它。

Answer 2

我假设 sparse_matrix 是一个相关矩阵，所以 sparse_matrix 是对称的。

首先，创建一个 name_vector 和 sparse_matrix 来使用

import string

N = 10

# create an array of names
name_vector = np.array(list(string.ascii_lowercase)[:N])
# create a correlation matrix (which is obviously symmetric)
sparse_matrix = np.random.rand(N,N)
sparse_matrix = (sparse_matrix + sparse_matrix.T)/2
zeros_mask = np.where(np.random.rand(N,N)>=0.5,False,True)
sparse_matrix[zeros_mask] = 0.

如你所见，name_vector 是一个数组

array(['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'], dtype='<U1')

对应10家公司的名称。 sparse_matrix 在结构上是对称的，它的一些条目被 sparse_matrix[zeros_mask] = 0. 赋值为 0。

有了这两种成分，这是我的解决方案

top = None 

non_zeros = sparse_matrix.nonzero()
sparserows = non_zeros[0]
sparsecols = non_zeros[1]
sparse_idx = sparserows*sparse_matrix.shape[1]+sparsecols

if top:
    nr_matches = top
else:
    nr_matches = sparsecols.size

left_side = name_vector[sparserows[:nr_matches]]
right_side = name_vector[sparsecols[:nr_matches]]
similairity = np.take(sparse_matrix,sparse_idx[:nr_matches])

pd.DataFrame({"left_side": left_side, 
              "right_side": right_side, 
              "similairity": similairity})

并且返回的 DataFrame 看起来像

left_side   right_side  similairity
0   a   c   0.760297
1   a   d   0.441365
2   a   g   0.669365
3   b   a   0.221993
4   b   c   0.840993
...

因为使用了advanced indexing而不是for循环，所以会快很多。

解包稀疏矩阵性能调优

Unpacking sparse matrix performance tuning

python

performance

numpy

sparse-matrix