PHP中的奇异值分解（SVD）

Question

PHP中的奇异值分解（SVD）

phpsvdeigenvectoreigenvalue

9

我希望在PHP中实现奇异值分解（SVD）。我知道有几个外部库可以为我完成这项工作。但是我有两个关于PHP的问题： 1）您认为编写SVD在PHP中是否可能和/或合理？ 2）如果（1）是肯定的：您能帮我在PHP中编写它吗？

我已经自己编写了SVD的一些部分。这里是代码，我对其中的行动过程进行了注释。其中的一些部分不完全正确。

如果您能帮助我，那将非常好。非常感谢您提前的帮助！

- caw

3

您在德语中的评论非常有帮助。为什么您需要在PHP中实现如此复杂的算法？ - Artem Barger

如果有人需要英文评论，我当然可以翻译。由于我无法在我的网络空间上安装外部库，因此我必须在PHP中实现它。 - caw

1

不，这不是作业。我在学校里没有计算机科学课程，也没有学习它。;) 这只是一种爱好... - caw

6个回答

5

当你说“我不在乎时间限制”时要小心。SVD是一个O(N^3)操作（或者如果是一个矩形m*n矩阵，则为O(MN^2)），这意味着你很容易陷入问题需要很长时间的情况。如果100*100的情况需要一分钟，那么1000*1000的情况将需要10^3分钟，或近17个小时（实际上可能更糟，因为你可能会出现缓存失效的情况）。对于像PHP这样的语言，前置因子--用于计算所需的FLOP计数的N^3的乘数，可能非常非常大。

话虽如此，当然可以用PHP编写它--该语言具有所需的数据结构和操作。

- Andrew Jaffe

非常感谢这个！那么你认为用PHP编写它是可能的，但PHP并不是很适合，是吗？ - caw

嗯，PHP并不是理想的数值线性代数工具，但在你的情况下能否使用它取决于具体细节。你将在其上运行的矩阵有多大？你需要做什么具体的操作？你可能希望参考《Numerical Recipes》这样的书籍，了解相关实现的信息。 - Andrew Jaffe

我想使用SVD进行潜在语义分析。因此，100x100的矩阵不足以容纳数据，它们将会非常庞大... - caw

2

Marco，我已经完成了LSA，可以肯定地告识你，PHP在处理矩阵时无论大小都会提供不可接受的响应时间，更不用说巨大的矩阵了。省点时间试图解决这个问题，找到一种与C进行接口的方法吧。对我来说，svdlibc非常好用：http://tedlab.mit.edu/~dr/svdlibc/ - llimllib

谢谢你，llimllib。一旦我在我的Web服务器上拥有C，我就会使用它。但是目前我没有它，也无法使用控制台安装任何东西。 - caw

3

我知道这是一个老问题，但以下是我的看法:

1) 真正的SVD比在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项目。”

- Jay Julian Payne

2

关于问题1：这是完全可能的。是否合理取决于您的场景：矩阵有多大？您打算运行代码多少次？它是在网站上运行还是从命令行运行？如果您关心速度，我建议编写一个简单的扩展来包装对GNU科学库的调用。

- rodion

感谢您的回答。我想在网站上运行它，并且脚本应该由cronjob调用。我不太在意速度。如果脚本始终为一个单独的文本执行SVD，则足以。我总是需要的大型矩阵也可以被缓存。为GNU科学库编写扩展是一个问题，因为我无法通过命令行在我的网络空间安装库。 - caw

如果您拥有shell访问权限并且可以安装二进制文件并使用cron，那么您应该考虑编写独立的（可能是静态链接的）二进制文件，而不是PHP脚本。即使对于相同的算法，这也将更加CPU和内存高效。 - drdaeman

1

是的，这是可能的，但在php中实现SVD并不是最优的方法。正如您在此处所见，PHP比C和C++更慢，因此也许最好使用其中一种语言来执行它，并将其作为函数调用以获取结果。您可以在此处找到算法的实现，以便指导自己。

关于函数调用，可以使用：

exec()函数

system函数非常有用和强大，但它的最大问题之一是所有程序生成的文本都直接进入输出流。有时您可能希望格式化生成的文本并以某种不同的方式显示它，或者根本不显示它。

system()函数

PHP中的system函数接受一个字符串参数，其中包含要执行的命令以及您希望传递给该命令的任何参数。此函数执行指定的命令，并将任何生成的文本转储到输出流（在Web服务器情况下为HTTP输出，或者如果您正在运行PHP作为命令行工具，则为控制台）。如果程序发出文本输出，则此函数的返回值是程序的最后一行输出。

passthru()函数

PHP提供的一个非常有趣的函数类似于我们迄今为止看到的函数是passthru函数。这个函数像其他函数一样执行您告诉它要执行的程序。但是，它随后立即将此程序的原始输出发送到PHP当前正在使用的输出流（即Web服务器场景下的HTTP，或者是PHP命令行版本中的shell）。

- Luis Yanes

1

你应该提到你直接从ChipmunkNinja复制了函数描述。 - TachyonVortex

0

是的，这在PHP中完全可以实现。我不知道执行的合理时间范围和它可以计算多大。我可能需要实现算法来获得一个大致的想法。
是的，我可以帮助您编写代码。但是为什么需要帮助？您编写的代码不起作用吗？

顺便问一下，您使用的PHP版本是什么？

- thomas.han

非常感谢！我和很多人交流过，他们告诉我PHP完全不适合SVD。我不在乎时间限制，我只想实现它。我的代码无法获取特征值，所以它不能正常工作。我尝试了一些近似处理方法，但效果不佳。如果您能帮助我就太好了。我使用的是PHP 5。 - caw

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- si28719e · Accepted Answer

SVD-python是SVD的非常清晰且简洁的实现。它几乎可以被看作是伪代码，应该很容易理解并与您的PHP实现进行比较/借鉴，即使您不熟悉Python。

SVD-python

话虽如此，正如其他人所提到的，在一个听起来相当有限的Web主机上使用php实现进行非常重度的LSA可能不太现实。

干杯

编辑：以上模块本身并没有做任何事情，但在开头的注释中包含了示例。假设您下载了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' 包含了您奇异值列表。
当然，这只是让您了解潜在语义分析及其相关内容的一部分。通常您需要减少奇异值的数量，然后采用适当的距离度量来衡量文档、单词或文档和单词等之间的相似性。向量余弦值是非常流行的度量方法。

潜在语义映射 (pdf)

迄今为止，这是我读过的最清晰、最简洁、最有信息量的论文，介绍了在进行奇异值分解后需要解决的剩余步骤。

备注2：请注意，如果您正在处理非常大的术语-文档矩阵（我假设您正在这样做），那么以离线模式执行分解几乎肯定会更有效，然后仅根据请求以实时方式执行比较。虽然 svd-python 很棒，但 svdlibc 更适合进行如此重的计算。

最后，如上所述的bellegarda论文中提到，记住你不必每次获取新文档或请求时都重新计算svd。根据你想要做什么，你可能可以在离线模式下每周执行一次svd，使用本地机器，然后上传结果（大小/带宽问题除外）。

无论如何，祝好运！