随机投影算法伪代码

Question

我正在尝试在一个非常稀疏的数据集上应用随机投影方法。我找到了关于Johnson-Lindenstrauss方法的论文和教程，但它们每一篇都充斥着方程式，对我来说毫无意义的解释。例如，这篇关于Johnson-Lindenstrauss的文件。

不幸的是，从这个文件中，我没有任何关于算法实现步骤的想法。这很遥远，但有人能告诉我该算法的纯英语版本或非常简单的伪代码吗？或者我可以从哪里开始挖掘这些方程？ 任何建议？

例如，通过阅读这篇关于Johnson-Lindenstrauss的论文，我理解的算法是：

1. 假设我们有一个AxB矩阵，其中A是样本数量，B是维数，例如100x5000。我想将其降低到500维，这将产生一个100x500矩阵。

据我所知：首先，我需要构建一个100x500矩阵，并用+1和-1随机填充条目（以50％的概率）。

编辑：
好的，我想我开始明白了。所以我们有一个矩阵A，它是mxn。我们想将其减少到E，它是mxk。

我们需要做的是构建一个具有nxk维度的矩阵R，并根据2/3，1/6和1/6的概率用0，-1或+1填充它。

构建完成R后，我们只需进行矩阵乘法AxR即可找到我们的缩减矩阵E。但我们不需要进行完整的矩阵乘法，因为如果Ri中的元素为0，我们无需进行计算，只需跳过它。但如果遇到1，则只需将其加入列中；如果是-1，则从计算中减去。因此，我们只需使用求和而不是乘法来找到E。这就是使该方法非常快速的原因。

尽管我感觉太愚蠢以至于不能理解这个想法，但它被证明是一种非常巧妙的算法。

- Ahmed

---

嗯，不行。你提醒了我为什么没有继续读研究生，以及为什么数学专业的人赚大钱。祝好运。 - Philip

你测试过使用真实数据的rp了吗？我想保留内积，但结果很糟糕...我必须缩放R的列还是只需除以sqrt(k)？ - xunzhang

尝试使用(1-sqrt(n), 1/2sqrt(n), 1/2sqrt(n))代替(2/3, 1/6, 1/6)。 - Zach

Answer 1

你的想法是正确的。然而，据我了解，随机项目中矩阵R的行应该具有单位长度。我相信这大约就是通过1/sqrt(k)进行归一化的原因，以消除它们不是单位向量的事实。

它不是一个投影，但它几乎是一个投影；R的行不是正交的，但在一个更高维度的空间内，它们非常接近正交。事实上，你选择的任意两个向量的点积都会非常接近于0。这就是为什么它通常是找到投影的适当基础的很好的近似方法。

- Sean Owen

---

Sean：我终于实现了，但是我遇到了一个问题。也许你有什么想法：https://dev59.com/nlvUa4cB1Zd3GeqPtXDs - Ahmed

Answer 2

在后一篇论文的定理1.1陈述中，高维数据A到低维数据E的映射是给出的。它只是一个标量乘法，然后是矩阵乘法。数据向量是矩阵A和E的行。正如作者在第7.1节中指出的那样，您不需要使用完整的矩阵乘法算法。

- han

Answer 3

如果您的数据集是稀疏的，那么稀疏随机投影将不起作用。您有几个选择：

选项A： 步骤1. 应用结构化的密集随机投影（通常使用快速哈达玛变换）。这是一种特殊的投影，计算非常快，但具有正常的密集随机投影的属性。 步骤2. 对“致密数据”应用稀疏投影（稀疏随机投影仅适用于密集数据）

选项B： 对稀疏数据应用SVD。如果数据是稀疏的但具有某些结构，则SVD更好。随机投影保留所有点之间的距离。 SVD更好地保留密集区域之间的距离-在实践中，这更有意义。此外，人们使用随机投影来计算巨大数据集上的SVD。随机投影可以提高效率，但不一定能获得低维嵌入的最佳质量。如果您的数据没有结构，则使用随机投影。

选项C： 对于误差较小的数据点，请使用SVD；对于其余数据点，请使用随机投影。

选项D： 基于数据点本身使用随机投影。这很容易理解正在发生什么。它看起来像这样：

create a n by k matrix (n number of data point, k new dimension)
for i from 0 to k do #generate k random projection vectors  
   randomized_combination = feature vector of zeros (number of zeros = number of features) 
   sample_point_ids = select a sample of point ids
   for each point_id in sample_point_ids do:
       random_sign = +1/-1 with prob. 1/2
       randomized_combination += random_sign*feature_vector[point_id] #this is a vector operation
    normalize the randomized combination
    #note that the normal random projection is:
    # randomized_combination = [+/-1, +/-1, ...] (k +/-1; if you want sparse randomly set a fraction to 0; also good to normalize by length]
    to project the data points on this random feature just do
    for each data point_id in dataset:
        scores[point_id, j] = dot_product(feature_vector[point_id], randomized_feature)

如果您仍在寻求解决此问题的方法，请在此处留言，我可以为您提供更多的伪代码。

思考这个问题的方式是，随机投影只是一个随机模式，数据点和模式之间的点积（即将数据点投影）给出它们之间的重叠。因此，如果两个数据点与许多随机模式重叠，则这些点相似。因此，随机投影保留相似性，同时使用更少的空间，但它们也会在成对相似性中添加随机波动。JLT告诉您，要使波动为0.1（eps），您需要约100 * log（n）维度。

祝好运！

- Stefan Savev

Answer 4

一个 R 包，使用 Johnson-Lindenstrauss 引理执行随机投影 RandPro

- Siddhu