python - 稀疏性降低

Question

我必须分解一个大的稀疏矩阵（代表用户的 650 万行 * 代表项目的 650 万列）来查找用户和项目的潜在向量。我在 spark 框架（pyspark）中选择了 als 算法。为了提高质量，我必须将矩阵的稀疏性降低到 98%。（当前值为 99.99%，因为我只有 3.56 亿个已填写条目）。我可以通过删除行或列来做到这一点，但我必须找到最大化行数（用户）的最佳解决方案。主要问题是我必须找到一些用户和项目集的子集，删除一些行可以删除一些列，反之亦然，第二个问题是评估稀疏性的函数不是线性的。我可以通过哪种方式解决这个问题？python中的哪些库可以帮助我？谢谢你。

Answer 1

这是一个组合问题。没有简单的方法可以删除一组最佳列以在减少稀疏性的同时实现最大用户数。一种正式的方法是将其表述为一个混合整数程序。考虑以下 0-1 矩阵，该矩阵源自原始矩阵 C。

A(i,j) = 1 if C(i,j) is nonzero, 
A(i,j) = 0 if C(i,j) is zero

参数：

M : a sufficiently big numeric value, e.g. number of columns of A (NCOLS)
N : total number of nonzeros in C (aka in A)

决策变量是

x(j) : 0 or 1  implying whether column j is dropped or not
nr(i): number of nonzeros covered in row i
y(i) : 0 or 1 implying whether row i is dropped or not

约束：

A(i,:) x  = nr(i)         for i = 1..NROWS
nr(i)    <= y(i) * M      for i = 1..NROWS
@sum(nr(i)) + e = 0.98 * N  # explicit slack 'e' to be penalized in the objective
y(i) and x(j) are 0-1 variables (binary variables) for i,j

客观的：

maximize @sum(y(i)) - N.e

这样的模型将极难作为整数模型来求解。然而，障碍方法应该能够解决线性规划松弛 (LP) 可能的求解器是 Coin/CLP（开源）、Lindo（商业）等......然后可以使用 LP 解决方案来计算近似整数通过简单的四舍五入解决。

最后，您肯定需要一种迭代方法，每次都需要多次求解 MF 问题，并分解使用上述方法计算的 C 的不同子矩阵，直到您对解决方案感到满意为止。