PHP中的奇异值分解(SVD)

Question

我想用PHP实现奇异值分解(SVD)。我知道有几个外部库可以帮我做到这一点。但是我有两个关于PHP的问题: 1)你认为用PHP编写SVD是可能的和/或合理的吗? 2)如果(1)是:你能帮我用PHP编写它吗？

我已经自己编写了SVD的一些部分。Here's the code，我在其中对操作过程进行了评论。这段代码的某些部分并不完全正确。

如果你能帮我，那就太好了。非常感谢您的提前！

Answer 1

SVD-python是SVD的一个非常清晰、简洁的实现。它实际上是psuedocode，即使你不太了解python，也应该很容易理解和比较/借鉴你的php实现。

SVD-python

也就是说，正如其他人提到的那样，我不指望能够用php实现非常强大的LSA，这听起来像是一个非常有限的web主机。

干杯

编辑:上面的模块本身不会做任何事情，但在开头的评论中有一个例子。假设您下载了python模块，并且可以访问它(例如，在相同的文件夹中)，您可以实现一个简单的示例，如下所示：

#!/usr/bin/python
import svd
import math

a = [[22.,10., 2.,  3., 7.],
     [14., 7.,10.,  0., 8.],
     [-1.,13.,-1.,-11., 3.],
     [-3.,-2.,13., -2., 4.],
     [ 9., 8., 1., -2., 4.],
     [ 9., 1.,-7.,  5.,-1.],
     [ 2.,-6., 6.,  5., 1.],
     [ 4., 5., 0., -2., 2.]]

u,w,vt = svd.svd(a)
print w

这里'w‘包含您的奇异值列表。

当然，这只是潜在语义分析及其相关部分的一部分。你通常想要减少奇异值的数量，然后使用一些适当的距离度量来衡量文档之间的相似性，或者词，或者文档和词等等。结果向量之间的夹角的余弦是很常见的。

Latent Semantic Mapping (pdf)

到目前为止，这是我读过的最清晰、最简洁、内容最丰富的论文，介绍了在SVD之后需要完成的剩余步骤。

Edit2:还要注意，如果您正在处理非常大的术语文档矩阵(我假设您正在做的就是这个)，那么几乎可以肯定的是，以离线模式执行分解，然后仅以实时方式执行比较以响应请求。虽然svd-python非常适合学习，但svdlibc更适合您处理如此繁重的计算。

最后，正如上面的bellegarda论文中所提到的，请记住，您不必在每次获得新文档或请求时都重新计算svd。根据您正在尝试做的事情，您可能会在脱机模式下每周执行一次svd，然后在本地计算机上上传结果(尽管存在大小/带宽问题)。

无论如何，祝你好运！

Answer 2

当你说“我不在乎时间限制是什么”时要小心。SVD是一种O(N^3)操作(如果是矩形m*n矩阵，则为O(MN^2) )，这意味着您很容易处于问题可能需要很长时间的情况下。如果100*100用例需要一分钟，那么1000*1000用例需要10^3分钟，或者将近17个小时(实际上，可能更糟，因为您很可能没有缓存)。对于PHP这样的东西，前置因素--为了计算所需的FLOP计数而乘以N^3的数字--可能非常非常大。

话虽如此，当然也可以用PHP对其进行编码--该语言具有所需的数据结构和操作。

Answer 3

我知道这是一个古老的问题，但这是我的两个比特：

1)真正的奇异值分解比微积分启发的近似方法慢得多，例如在Netflix奖中。请参阅：http://www.sifter.org/~simon/journal/20061211.html

这里有一个实现(用C编写)：http://www.timelydevelopment.com/demos/NetflixPrize.aspx

2) C会更快，但PHP当然可以做到。

PHP Architect作者Cal Evans："PHP是一种web脚本语言……但我使用PHP作为脚本语言来编写DOS版的批处理文件或Linux版的shell脚本。我发现我需要做的大部分工作都可以在PHP中完成。甚至有一个项目允许您通过PHP构建桌面应用程序，PHP-GTK项目。“