1

给定一个距离矩阵和一组点，如何计算这些点的坐标？

编辑：这是在飞机上。

这个问题在这里得到了回答，但是在尝试不同的距离矩阵时，我真的不能使用这个答案，因为 M 矩阵有负值，我的特征向量也是如此。因此，当您取平方根时，程序（在 R 中）为这些相关条目输出“NaN”。我猜每次 D(i,j)^2 大于 D(1,j)^2 + D(i,1)^2 时都会发生这种情况。

例如，假设我有一个距离矩阵：

0    73   102  496  432  184
73    0   303  392  436  233
102  303    0  366  207  353
496  392  366    0  172  103
432  436  207  172    0  352
184  233  353  103  352    0

使用方程 M(i,j) = (0.5)(D(1,j)^2+D(i,1)^2-D(i,j)^2)，我得到 (它已经有负条目):

0      0.0      0.0      0.0      0.0      0.0
0   5329.0 -38038.0  48840.5    928.5  -7552.0
0 -38038.0  10404.0  61232.0  77089.5 -40174.5
0  48840.5  61232.0 246016.0 201528.0 134631.5  
0    928.5  77089.5 201528.0 186624.0  48288.0
0  -7552.0 -40174.5 134631.5  48288.0  33856.0

然后我得到非零特征值和特征向量：

477718.27  101845.63   16474.30  -13116.72 -100692.49


        [,1]       [,2]        [,3]        [,4]        [,5]
 0.00000000  0.0000000  0.00000000  0.00000000  0.00000000
-0.05928626  0.3205747  0.84148945  0.04869546 -0.42806691
-0.16650486 -0.5670946 -0.04507520 -0.58222690 -0.55647098
-0.73371713  0.2827320  0.07386302 -0.45957443  0.40627254
-0.59727407 -0.4623603  0.07806418  0.64968004 -0.03617241
-0.27144823  0.5309625 -0.52755471  0.15920983 -0.58372335

由于有负特征值和特征向量，当我们计算 sqrt(eigenvector(i)*eigenvalue(i)) 时，我们将有负值。这是我的最终输出：

[,1]     [,2]      [,3]     [,4]      [,5]
   0   0.0000   0.00000  0.00000   0.00000
 NaN 180.6907 117.74103      NaN 207.61291
 NaN      NaN       NaN 87.38939 236.71174
 NaN 169.6910  34.88326 77.64089       NaN
 NaN      NaN  35.86158      NaN  60.35139
 NaN 232.5429       NaN      NaN 242.43877

这是不使用角度计算坐标点的唯一清晰方法吗？如果是，我们是否必须修复距离矩阵，使 D(i,j)^2 不大于 D(1,j)^2 + D(i,1)^2。

谢谢。

4

3 回答 3

6

您的数据不一致

您的坐标与ℝ⁴中点的位置不一致，更不用说低维空间了。您可以通过计算平方距离矩阵的门格尔行列式来判断这一事实：

D <- as.matrix(read.table(textConnection("\
0    73   102  496  432  184
73    0   303  392  436  233
102  303    0  366  207  353
496  392  366    0  172  103
432  436  207  172    0  352
184  233  353  103  352    0")))
n <- nrow(D)
det(rbind(cbind(D^2, 1), c(rep(1, n), 0)))
# Result: 3.38761e+25

如果您的坐标确实来自维度小于 5 的空间中的点，那么该行列式必须为零。事实并非如此，您的距离不一致，或者这些点在足够高维度的空间中形成单纯形。

但无论维度如何，您的数据仍然不一致，因为它在几种情况下违反了三角不等式：

a b c   ac   abc    ab    bc
1 2 4: 496 > 465 =  73 + 392
1 3 4: 496 > 468 = 102 + 366
1 3 5: 432 > 309 = 102 + 207
1 6 4: 496 > 287 = 184 + 103
2 1 3: 303 > 175 =  73 + 102
2 6 4: 392 > 336 = 233 + 103
3 1 6: 353 > 286 = 102 + 184
5 4 6: 352 > 275 = 172 + 103

直接从 a 到 c 永远不会比通过 b 花费更长的时间，但根据您的数据，确实如此。

简单的平面方法

如果您的数据与平面中的点一致（即所有四个点组合的门格尔行列式计算为零），您可以使用以下方法获取坐标：

distance2coordinates <- function(D) {
  n <- nrow(D)
  maxDist <- which.max(D)
  p1 <- ((maxDist - 1) %% n) + 1
  p2 <- ((maxDist - 1) %/% n) + 1
  x2 <- D[p1, p2]
  r1sq <- D[p1,]^2
  r2sq <- D[p2,]^2
  x <- (r1sq - r2sq + x2^2)/(2*x2)
  y <- sqrt(r1sq - x^2)
  p3 <- which.max(y)
  x3 <- x[p3]
  y3 <- y[p3]
  plus <- abs(D[p3,]^2 - (x3 - x)^2 - (y3 - y)^2)
  minus <- abs(D[p3,]^2 - (x3 - x)^2 - (y3 + y)^2)
  y[minus < plus] <- -y[minus < plus]
  coords <- data.frame(x = x, y = y)
  return(coords)
}

这个想法是你选择两个距离最大的点作为起点。您将一个放在原点上，另一个放在正 x 轴上。然后，您可以根据方程式计算所有其他 x 坐标，作为两个圆的交点

I:     x²       + y² = r₁²
II:   (x - x₂)² + y² = r₂²
I-II:  2*x*x₂ = r₁² - r₂² + x₂²

给定这些 x 坐标，您也可以获得 y 坐标，直到 sign。然后，您选择离这两个起点中的任何一个足够远的第三个点来决定标志。

这种方法根本不尝试处理不精确的输入。它假定准确的数据，并且只会使用距离矩阵的一部分来查找点。它不会找到与所有输入数据最匹配的点集。

在您的数据上，这将失败，因为平方根的某些参数将是负数。这意味着所涉及的两个圆根本不相交，因此违反了三角不等式。

如果是，我们是否必须修复距离矩阵，使 D(i,j)^2 不大于 D(1,j)^2 + D(i,1)^2。

D(i,j) ≤ D(i,k) + D(k,j) 会有所帮助，即适用于所有三元组且没有正方形。这将确保三角不等式在任何地方都成立。结果仍然不必是平面的；为此，您必须修复所有门格尔行列式。

于 2013-08-07T17:09:02.623 回答
2

在此处输入图像描述 在此处输入图像描述

这是一个简单的python函数来计算你需要什么，解决超球面。

import sympy
import numpy as np
def give_coords(distances):
    """give coordinates of points for which distances given

    coordinates are given relatively. 1st point on origin, 2nd on x-axis, 3rd 
    x-y plane and so on. Maximum n-1 dimentions for which n is the number
    of points

     Args:
        distanes (list): is a n x n, 2d array where distances[i][j] gives the distance 
            from i to j assumed distances[i][j] == distances[j][i]

     Returns:
        numpy.ndarray: cordinates in list form n dim

     Examples:
        >>> a = sympy.sqrt(2)
        >>> distances = [[0,1,1,1,1,1],
                         [1,0,a,a,a,a],
                         [1,a,0,a,a,a],
                         [1,a,a,0,a,a],
                         [1,a,a,a,0,a],
                         [1,a,a,a,a,0]]
        >>> give_coords(distances)
        array([[0, 0, 0, 0, 0],
               [1, 0, 0, 0, 0],
               [0, 1, 0, 0, 0],
               [0, 0, 1, 0, 0],
               [0, 0, 0, 1, 0],
               [0, 0, 0, 0, 1]], dtype=object)

        >>> give_coords([[0, 3, 4], [3, 0, 5], [4, 5, 0]])
        array([[0, 0],
        [3, 0],
        [0, 4]], dtype=object)        

    """
    distances = np.array(distances)

    n = len(distances)
    X = sympy.symarray('x', (n, n - 1))

    for row in range(n):
        X[row, row:] = [0] * (n - 1 - row)

    for point2 in range(1, n):

        expressions = []

        for point1 in range(point2):
            expression = np.sum((X[point1] - X[point2]) ** 2) 
            expression -= distances[point1,point2] ** 2
            expressions.append(expression)

        X[point2,:point2] = sympy.solve(expressions, list(X[point2,:point2]))[1]

    return X
于 2017-09-25T09:06:17.330 回答
0

这是可解决的

如果您想查看满足您在问题中提供的距离矩阵的笛卡尔坐标，请查看下图。
距离矩阵和坐标 您的输入矩阵给出了 6 个节点之间的距离，我们称之为 a、b、c、d、e 和 f。总共需要 5 个维度才能将坐标分配给满足您的距离矩阵的所有六个节点。其中两个维度是虚值的——这是打破三角形规则的结果。结果是通过使用余弦定律和一些数字运算得出的。

  • 一 (0, 0, 0, 0, 0)
  • b (73, 0, 0, 0, 0)
  • c (-521.07, 510.99i, 0, 0, 0)
  • d (669.05, -802.08i, 664.62, 0, 0)
  • e (12.72, -163.83i, 488.13, 158.01i, 0)
  • f (-103.45, 184.11i, 84.52, 138.06i, 262.62)
于 2016-07-28T23:31:39.793 回答