稀疏度降低

Question

我必须分解一个大的稀疏矩阵（6.5mln行代表用户*6.5mln列代表项目）来找到用户和项目的潜在向量。我选择了spark框架中的als算法（pyspark）。 为了提高质量，我必须将矩阵的稀疏性降低到98%。（当前值是99.99%，因为我有356mln的填充条目）。 我可以通过删除行或列来做到这一点，但我必须找到最大化行（用户）数的最佳解决方案。 主要的问题是我必须找到一些用户和项目集的子集，删除一些行可以删除一些列，反之亦然，第二个问题是计算稀疏性的函数不是线性的。 我怎样才能解决这个问题？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，计算与上述方法，直到你满意的解决方案。你知道吗