Как реализовать поиск координат точек из матрицы расстояний в python на основе грамм-матрицы? - PullRequest
Новая
       104

Как реализовать поиск координат точек из матрицы расстояний в python на основе грамм-матрицы?

1 голос
/ 07 мая 2020

Я хочу изучить проблему оптимизации автобусной остановки. Однако теперь я застрял в том, как преобразовать матрицу расстояний в реальные координаты точек.

Я просмотрел много ресурсов и знаю, используя формулу ： M (i, j) = 0,5 (D (1, j) ^ 2 + D (i, 1 ) ^ 2 - D (i, j) ^ 2) * для решения проблемы введите здесь описание ссылки . Я плохо разбираюсь в математике, и я просто хочу ее реализовать.

Во-первых, я пытаюсь понять принцип математики, и вот мое решение. введите здесь описание ссылки .

Затем я хочу внедрить алгоритм, используя python, для следующего примера. Вот моя матрица, которая представляет различное расстояние для каждой автобусной станции. Я хочу перенести его в координаты точек.

enter image description here

Вот мой код для внедрения: 

import csv
import numpy as np
import math

class csv_util():

    def generate_coordinate_point(self):
        '''transfer the distance matrix to the real coordinate points'''
        sqrt_result = 2*math.sqrt(2)

        matrix = np.array([[0,2,2,sqrt_result],[2,0,sqrt_result,2],[2,sqrt_result,0,2],[sqrt_result,2,2,0]])

        gram_matrix = self.calculate_gram_matrix(matrix)

        a, b = np.linalg.eig(gram_matrix)

        #b = b.astype(np.int16)
        a = a.astype(np.int16)


        eigen_vector = format(b)

        length = a.size
        tmp_matrix = np.zeros(length * length)
        random_point_matrix = tmp_matrix.reshape(length, length)

        for item1 in range(length):
            random_point_matrix[item1][item1] = a[item1]

        print("the eigen-value is: " + format(random_point_matrix))
        print("the eigen-vector is: " + eigen_vector)

        new_matrix = (np.sqrt(random_point_matrix))*b

        print("the coordinate points: "+format(new_matrix))



    def calculate_gram_matrix(self,matrix):
        '''get the gram matrix for transfer to the coordinate points'''

        length = matrix[0].size
        tmp_matrix = np.zeros(length*length)
        gram_matrix = tmp_matrix.reshape(length,length)

        for item1 in range(length):
            for item2 in range(length):
                gram_matrix[item1][item2] = (math.pow(matrix[0][item2],2)+math.pow(matrix[0][item1],2)-math.pow(matrix[item1][item2],2))/2
                if gram_matrix[item1][item2]<0.1 and gram_matrix[item1][item2]>-0.1:
                    gram_matrix[item1][item2] = 0

        return gram_matrix

Однако, результат окончательной матрицы неверен. Результат такой: 

the eigen-value is: [[12.  0.  0.  0.]
 [ 0.  0.  0.  0.]
 [ 0.  0.  4.  0.]
 [ 0.  0.  0.  0.]]
-------------
the eigen-vector is: [[ 0.00000000e+00  0.00000000e+00  0.00000000e+00  1.00000000e+00]
 [ 4.08248290e-01 -5.77350269e-01 -7.07106781e-01  0.00000000e+00]
 [ 4.08248290e-01 -5.77350269e-01  7.07106781e-01  0.00000000e+00]
 [ 8.16496581e-01  5.77350269e-01  1.57009246e-16  0.00000000e+00]]
-------------
the coordinate points: [[ 0.          0.          0.          0.        ]
 [ 0.         -0.         -0.          0.        ]
 [ 0.         -0.          1.41421356  0.        ]
 [ 0.          0.          0.          0.        ]]

Конечные точки вроде этого: [0,0], [- 0,0, -0,0], [- 0,0,1.414421], [0,0,0.0]. Их не может удовлетворить матрица расстояний в этом примере. Пожалуйста, помогите мне получить правильные баллы. Спасибо!

1 Ответ

1 голос
/ 09 мая 2020

Построение матрицы Грама точечных произведений, связанных с матрицей расстояний, и ее дальнейшая факторизация, как правило, является отличным методом, который также позволяет вывести размерность реализации координат матрицы расстояний. Однако, если в вашем случае реализация плоская (двумерная), то я думаю, что (возможно) проще (и, возможно, быстрее) просто подойти к ней немного более геометрически (опять же, вы должны быть уверены, что матрица расстояний предназначена для точек в 2D): 

import numpy as np
import math

def x_coord_of_point(D, j):
    return ( D[0,j]**2 + D[0,1]**2 - D[1,j]**2 ) / ( 2*D[0,1] )

def coords_of_point(D, j):
    x = x_coord_of_point(D, j)
    return np.array([x, math.sqrt( D[0,j]**2 - x**2 )])
    
def calculate_positions(D):
    (m, n) = D.shape
    P = np.zeros( (n, 2) )
    tr = ( min(min(D[2,0:2]), min(D[2,3:n])) / 2)**2
    P[1,0] = D[0,1]
    P[2,:] = coords_of_point(D, 2)
    for j in range(3,n):
        P[j,:] = coords_of_point(D, j) 
        if abs( np.dot(P[j,:] - P[2,:], P[j,:] - P[2,:]) - D[2,j]**2 ) > tr:
            P[j,1] = - P[j,1]
    return P 
    
sqrt_result = 2*math.sqrt(2)
D = np.array([[0, 2, 2, sqrt_result],
              [2, 0, sqrt_result, 2], 
              [2, sqrt_result, 0, 2], 
              [sqrt_result, 2, 2, 0]])

P = calculate_positions(D)
print(P)

Вы можете добавить некоторые проверки и улучшения, чтобы убедиться, что векторы P [1 ,:] и P [2 ,:] не выровнены, что эквивалентно проверка того, что 

abs( P[1,0]*P[2,1] - P[1,1]*P[2,0] ) < 0.0001 (or some more appropriate threshold)

Если они есть, просто выполните while l oop, пока не найдете первый вектор P[j0, :], который не выровнен с P[1,0]. Роль этого первого вектора P[j0,:], не выровненного с начальным вектором P[1,:], позволяет вам иметь полезное предложение if в function vector(D). Я не включил его, чтобы не затруднить понимание кода.

...