sparse_dot_topn

sparse_dot_topn 提供了一种快速执行稀疏矩阵乘法后选择前n个乘法结果的方法。

比较非常大的特征向量并选择最佳匹配，在实践中通常会导致执行稀疏矩阵乘法后选择前n个乘法结果。

sparse_dot_topn 提供了一个（并行化的）稀疏矩阵乘法实现，它集成了选择前n个值的功能，从而显著降低内存占用并提高性能。在 Apple M2 Pro 上，对于两个 20k x 193k 的 TF-IDF 矩阵，当保留每行前10个值并利用8个核心时，sparse_dot_topn 可以快6倍。详情请参阅基准目录。

用法

sp_matmul_topn 支持 {CSR, CSC, COO} 矩阵，具有 {32, 64}bit {int, float} 数据。请注意，COO 和 CSC 输入将被转换为 CSR 格式，因此速度较慢。有两个选项可以进一步减少内存需求：threshold 和 density。可选地对值进行排序，以便给定行的第一列包含最大的值。请注意，sp_matmul_topn(A, B, top_n=B.shape[1]) 等于 sp_matmul(A, B) 和 A.dot(B)。

如果您正在从 v0.* 迁移，请参阅下面的迁移指南以获取详细信息。

import scipy.sparse as sparse
from sparse_dot_topn import sp_matmul, sp_matmul_topn

A = sparse.random(1000, 100, density=0.1, format="csr")
B = sparse.random(100, 2000, density=0.1, format="csr")

# Compute C and retain the top 10 values per row
C = sp_matmul_topn(A, B, top_n=10)

# or paralleslised matrix multiplication without top-n selection
C = sp_matmul(A, B, n_threads=2)
# or with top-n selection
C = sp_matmul_topn(A, B, top_n=10, n_threads=2)

# If you are only interested in values above a certain threshold
C = sp_matmul_topn(A, B, top_n=10, threshold=0.8)

# If you set the threshold we cannot easily determine the number of non-zero
# entries beforehand. Therefore, we allocate memory for `ceil(top_n * A.shap[0] * density)`
# non-zero entries. You can set the expected density to reduce the amount pre-allocated
# entries. Note that if we allocate too little an expensive copy(ies) will need to hapen.
C = sp_matmul_topn(A, B, top_n=10, threshold=0.8, density=0.1)

安装

sparse_dot_topn 为 CPython 3.8 至 3.12 提供了 wheels

• Windows (64位)
• Linux (64位)
• MacOS (x86 和 ARM)

pip install sparse_dot_topn

sparse_dot_topn 依赖于用于计算密集型乘法例程的 C++ 扩展。**请注意，wheels 供应商/提供的扩展与 OpenMP 一起使用，以提供开箱即用的并行化。**这可能在使用像 PyTorch 这样的也提供 OpenMP 的库时引起问题。如果您遇到任何与 OpenMP 相关的问题，请参阅 INSTALLATION.md 获取帮助或在不指定 n_threads 参数的情况下运行函数。

从源代码安装需要 C++17 兼容的编译器。如果您有可用的编译器，建议不使用 wheel 安装，因为这可以启用特定于架构的优化。

您可以使用以下方法从源代码安装：

pip install sparse_dot_topn --no-binary sparse_dot_topn

构建配置

sparse_dot_topn 在从源代码构建时提供了一些配置选项。从源代码构建可以启用特定于架构的优化，并建议那些已安装 C++ 编译器的人使用。有关详细信息，请参阅 INSTALLATION.md。

在集群上分配两个大型 O(10M+) 稀疏矩阵的前n个乘法

两个大型 O(10M+) 稀疏矩阵的前n个乘法可以分解为更小的块。例如，可以将稀疏矩阵分解为仅包含 1M 行的矩阵，然后对所有这些矩阵对执行（前n个）乘法。这样做的原因是为了减少每个对的内存占用，并利用可用的分布式计算能力。

可以将这些对分配到集群中（例如，我们使用 spark 集群）进行计算。然后对结果矩阵产品进行压缩并堆叠，以重现完整的矩阵乘积。

以下是一个示例，其中我们正在将稀疏矩阵 A 中的 1000 行与稀疏矩阵 B 中的 600 行进行匹配，并且 A 和 B 都被拆分为块。

import numpy as np
import scipy.sparse as sparse
from sparse_dot_topn import sp_matmul_topn, zip_sp_matmul_topn

# 1a. Example matching 1000 rows in sparse matrix A against 600 rows in sparse matrix B.
A = sparse.random(1000, 2000, density=0.1, format="csr", dtype=np.float32, random_state=rng)
B = sparse.random(600, 2000, density=0.1, format="csr", dtype=np.float32, random_state=rng)

# 1b. Reference full matrix product with top-n
C_ref = sp_matmul_topn(A, B.T, top_n=10, threshold=0.01, sort=True)

# 2a. Split the sparse matrices. Here A is split into three parts, and B into five parts.
As = [A[i*200:(i+1)*200] for i in range(5)]
Bs = [B[:100], B[100:300], B[300:]]

# 2b. Perform the top-n multiplication of all sub-matrix pairs, here in a double loop.
# E.g. all sub-matrix pairs could be distributed over a cluster and multiplied there.
Cs = [[sp_matmul_topn(Aj, Bi.T, top_n=10, threshold=0.01, sort=True) for Bi in Bs] for Aj in As]

# 2c. top-n zipping of the C-matrices, done over the index of the B sub-matrices.
Czip = [zip_sp_matmul_topn(top_n=10, C_mats=Cis) for Cis in Cs]

# 2d. stacking over zipped C-matrices, done over the index of the A sub-matrices
# The resulting matrix C equals C_ref.
C = sparse.vstack(Czip, dtype=np.float32)

迁移到 v1。

sparse_dot_topn v1 是从 v0.* 中的一个重大变化，具有新的绑定和 API。新版本支持 CPython 3.12，现在支持整数和浮点数。内部，我们切换到最大堆来收集前n个值，这显著减少了内存占用。前一个实现的前n个选择具有 O(n_columns) 的复杂度，而我们现在具有 O(top-n) 的复杂度。awesome_cossim_topn 已弃用，将在未来的版本中删除。

用户应切换到 sp_matmul_topn，它大致兼容

例如

C = awesome_cossim_topn(A, B, ntop=10)

可以使用以下方法进行复制

C = sp_matmul_topn(A, B, top_n=10, threshold=0.0, sort=True)

API 更改

1. ntop 已重命名为 topn
2. lower_bound 已重命名为 threshold
3. use_threads 和 n_jobs 已合并为 n_threads
4. 已删除 return_best_ntop 选项
5. test_nnz_max 选项已被移除
6. 当其形状不兼容但转置兼容时，B 会自动转置。

return_best_ntop 的输出可以通过以下方式复制：

C = sp_matmul_topn(A, B, top_n=10)
best_ntop = np.diff(C.indptr).max()

默认更改

1. threshold 已不再是 0.0，而是默认禁用。

这使包含负值的矩阵能够正常工作。此外，在收集非零结果时，内部使用了一个不同的数据结构，其内存占用比以前低得多。这意味着 threshold 参数对性能和内存需求的影响可以忽略不计。如果 threshold 为 None，则预先计算非零条目的数量，这可以显著减少所需的内存，同时性能损失轻微（约10%）。

2. sort = False，结果矩阵不再默认排序。

返回的矩阵列顺序与未进行 top-n 结果过滤时相同。这意味着当您将 top_n 设置为 B 的列数时，您将获得与正常乘法相同的结果，即 sp_matmul_topn(A, B, top_n=B.shape[1]) 等于 A.dot(B)。

贡献

非常欢迎贡献，请参阅 CONTRIBUTING 以获取详细信息。

贡献者

此包是由（以前）与 ING Analytics Wholesale Banking Advanced Analytics 有关联的作者开发和维护的。原始实现基于 Scipy 的 CSR 乘法实现的修改版本。您可以在由 Zhe Sun 撰写的博客 https://medium.com/@ingwbaa/https-medium-com-ingwbaa-boosting-selection-of-the-most-similar-entities-in-large-scale-datasets-450b3242e618 中了解相关信息 （镜像）。

• Zhe Sun
• Ahmet Erdem
• Stephane Collot
• Particular Miner（无 ING 关联）
• Ralph Urlus
• Max Baak