14

我有一个有限度量空间，作为（对称）k x k 距离矩阵给出。我想要一种算法来（大约）等距地将其嵌入欧几里得空间 R^(k-1) 中。虽然并不总是可以通过求解距离给出的方程组来精确地做到这一点，但我正在寻找一个嵌入一些（非常小的）可控误差的解决方案。

我目前使用输出维度设置为 (k-1) 的多维缩放 (MDS)。我突然想到，通常 MDS 可能会针对您试图将环境嵌入维度减少到小于 (k-1)（通常为 2 或 3）的情况进行优化，并且可能有更好的算法来解决我的受限问题案子。

问题：使用欧几里得距离在 R^{k-1} 中实现大小为 k 的度量空间的好/快速算法是什么？

一些参数和指针：

(1) 我的 k 相对较小。说 3 < k < 25

(2) 我实际上并不关心我是否嵌入 R^{k-1}。如果它简化了事情/使事情变得更快，任何 R^N 也可以，只要它是等距的。如果我增加到 R^k 或 R^(2k+1)，如果有更快的算法或错误更少的算法，我会很高兴。

(3) 如果你能指出一个 python 实现，我会更开心。

(4) 任何比 MDS 更好的东西都可以。

4

2 回答 2

1

为什么不试试 LLE，你也可以在那里找到代码。

于 2012-03-02T17:49:10.053 回答
0

好的，正如这里所承诺的一个简单的解决方案：

符号：让d_{i,j}=d_{j,i}表示点和之间的平方距离。设点数。让表示该点和该点的-th 坐标。ijNp_iip_{i,k}k

让我们希望我现在正确地推导出算法。之后会有一些解释，以便您检查推导（当出现许多索引时我讨厌它）。

该算法使用动态规划来得出正确的解决方案

Initialization:
p_{i,k} := 0 for all i and k

Calculation:
for i = 2 to N do
   sum = 0
   for j = 2 to i - 1 do
     accu = d_{i,j} - d_{i,1} - p_{j,j-1}^2
     for k = 1 to j-1 do
       accu = accu + 2 p_{i,k}*p_{j,k} - p_{j,k}^2
     done
     p_{i,j} = accu / ( 2 p_{j,j-1} )
     sum = sum + p_{i,j}^2
   done
   p_{i,i-1} = sqrt( d_{i,0} - sum )
done

如果我没有犯任何严重的索引错误（我通常会这样做），这应该可以解决问题。

这背后的想法：

我们将第一个点任意设置在原点，以使我们的生活更轻松。并不是说我们从来没有在 时p_i设置坐标。即对于第二个点我们只设置第一个坐标，对于第三个点我们只设置第一个和第二个坐标等等。kk > i-1

现在让我们假设我们有所有点 p_{k'}k'<i的坐标，我们想要计算坐标p_{i}以便满足所有d_{i,k'}点（我们还不关心点的任何约束k>k'）。如果我们写下我们有的方程组

d_{i,j} = \sum_{k=1}^N (p_{i,k} - p_{j,k} )^2

因为两者p_{i,k}和p_{j,k}都等于零，k>k'我们可以将其简化为：

d_{i,j} = \sum_{k=1}^k' (p_{i,k} - p_{j,k} )^2

另请注意，p_{j,k}当 时，循环不变量 all 将为零k>j-1。所以我们拆分这个方程：

d_{i,j} = \sum_{k=1}^{j-1} (p_{i,k} - p_{j,k} )^2 + \sum_{k=j}^{k'} p_{i,j}^2

对于第一个方程，我们得到：

d_{i,1} = \sum_{k=1}^{j-1} (p_{i,k} - p_{j,k} )^2 + \sum_{k=j}^{k'} p_i{i,1}^2

这个稍后需要一些特殊处理。

现在，如果我们求解正规方程中的所有二项式，我们得到：

d_{i,j} = \sum_{k=1}^{j-1} p_{i,k}^2 - 2 p_{i,k} p_{j,k} + p_{j,k}^2 + \sum_{k=j}^{k'} p_{i,j}^2

从中减去第一个等式，剩下的是：

d_{i,j} - d_{i,1} = \sum_{k=1}^{j-1} p_{j,k}^2 - 2 p_{i,k} p_{j,k}

对于所有 j > 1。

如果你看这个，你会注意到 p_i 坐标的所有正方形都消失了，我们需要的唯一正方形是已知的。这是一组线性方程，可以使用线性代数的方法轻松求解。实际上这组方程还有一个特别之处：方程已经是三角形的，所以你只需要传播解的最后一步。对于最后一步，我们只剩下一个二次方程，我们可以通过取一个平方根来求解。

我希望你能按照我的推理。有点晚了，我的头从这些索引中有点旋转。

编辑：是的，有索引错误。固定的。当我有时间测试它时，我会尝试在 python 中实现它。

于 2011-09-29T22:05:07.353 回答