大型稀疏矩阵的快速非负矩阵分解

Question

使用Scikit-learn (v0.15.2)对大型稀疏矩阵(小于1%的值> 0)进行非负矩阵分解。我希望通过最小化矩阵的非零值的误差来找到因子(即，不计算为零的条目的误差)，并支持稀疏性。我不确定我正在尝试的东西是否出了什么问题。scikit learn包的NMF和ProjectedGradientNMF以前对我来说工作得很好。但似乎当矩阵大小增加时，因子分解非常慢。

我说的是大于10^10个单元的矩阵。对于大约有10^7个单元的矩阵，我发现执行时间很好。

我使用的参数如下：nmf_model = NMF(n_components = 100, init='nndsvd', random_state=0, tol = 0.01, sparseness='data')。

当我尝试略微不同的参数(更改为init=random)时，我得到以下警告。在该警告之后，脚本的执行将停止。

/lib/python2.7/site-packages/sklearn/decomposition/nmf.py:252: UserWarning: Iteration limit reached in nls subproblem.
  warnings.warn("Iteration limit reached in nls subproblem.")

有没有办法更快地解决上面的问题呢？我试过使用numpy稀疏矩阵(列和行稀疏)，但令人惊讶的是-在我使用较小的矩阵(~10^7个单元)进行的测试中，速度较慢。

考虑到必须运行这种因子分解的多次迭代(选择理想的因子数量和k重交叉验证)，解决此问题的更快方法是非常可取的。

我也对不是基于sklearn或Pyhon的包/工具的建议持开放态度。我理解关于包/工具选择的问题是不鼓励的，但对于这样一个特定的用例，知道该领域的其他人使用什么技术将非常有帮助。

Answer 1

也许关于初始问题的几句话可以让我们给出更好的答案。

由于问题的性质，在非常大的矩阵上进行矩阵分解总是会很慢。

建议:将n_components降低到< 20将在一定程度上加快速度。然而，只有通过限制矩阵的大小才能真正提高速度。有了你所描述的矩阵，人们可能会认为你正在尝试分解一个词频矩阵。如果是这样，您可以尝试使用scikit-learn中的矢量化函数来限制矩阵的大小。它们中的大多数都有一个max_features参数。示例：

vectorizer = TfidfVectorizer(
    max_features=10000,
    ngram_range=(1,2))
tfidf = vectorizer.fit_transform(data)

这将大大加快问题的解决速度。

如果我完全错了，这不是一个词频问题，我仍然会寻找方法来限制您试图分解的初始矩阵。

Answer 2

您可能想看看本文，其中讨论了有关NMF的更多最新技术：http://www.cc.gatech.edu/~hpark/papers/nmf_blockpivot.pdf

这个想法是只对非零项进行因子分解，这减少了计算时间，特别是当涉及的矩阵/矩阵非常稀疏时。

此外，同一篇文章中的一位作者在github上创建了NMF实现，包括他们的文章中提到的那些实现。这里有个链接：https://github.com/kimjingu/nonnegfac-python

希望这能有所帮助。

Answer 3

老问题，新答案。

OP请求“零掩码”NMF，其中零被视为缺失值。这永远不会比普通的NMF更快。通过交替最小二乘来考虑NMF，这里方程系统的左侧通常是恒定的(它只是W或H的tcrossprod )，但在零掩码NMF中，它需要为每个单独的样本或特征重新计算。

我已经在RcppML R包中实现了零掩码NMF。您可以从CRAN安装它，并使用将mask_zeros参数设置为TRUE的nmf函数

install.packages("RcppML")
A <- rsparsematrix(1000, 1000, 0.1) # simulate random matrix
model <- RcppML::nmf(A, k = 10, mask_zeros = TRUE)

我的NMF实现比没有掩蔽零的scikit-learn更快，对于99%的稀疏矩阵来说，应该不会太慢。