Ближайшие соседи с неопределенными точками

Question

У меня есть два набора 2D точек A а также B, Я хочу найти первого ближайшего соседа в A для каждой точки в B, Однако я имею дело с неопределенными точками (то есть точка имеет среднее значение (2D вектор) и ковариационную матрицу 2*2).

Таким образом, я хотел бы использовать расстояние Махаланобиса, но в scikit-learn (например), я не могу передать ковариационную матрицу для каждой точки, так как она ожидает единственную ковариационную матрицу.

В настоящее время, учитывая только средние местоположения (т.е. среднее из моего нормального 2D-распределения), я имею:

nearest_neighbors = NearestNeighbors(n_neighbors=1, metric='l2').fit(A)
distance, indices = nearest_neighbors.kneighbors(B)

С моими неопределенными точками вместо использования нормы L2 в качестве расстояния я бы предпочел вычислить (между точкой a в A и точка b в Б их расстояние махаланобисов:

d(a, b) = sqrt( transpose(mu_a-mu_b) * C * (mu_a-mu_b))

где C = inv(cov_a + cov_b)

где mu_a (соответственно mu_b) а также cov_a (Соотв. cov_b) являются средним 2D и 2*2 ковариационной матрицей неопределенной точки a (Соотв. b).

Answer 1

Я в конечном итоге использовал пользовательское расстояние:

def my_mahalanobis_distance(x, y):
    '''
    x: array of shape (4,) x[0]: mu_x_1, x[1]: mu_x_2, 
                            x[2]: cov_x_11, x[3]: cov_x_22
    y: array of shape (4,) y[0]: mu_ y_1, y[1]: mu_y_2,
                            y[2]: cov_y_11, y[3]: cov_y_22 
    '''     



    return sp.spatial.distance.mahalanobis(x[:2], y[:2], 
                                           np.linalg.inv(np.diag(x[2:]) 
                                           + np.diag(y[2:])))

Таким образом, точка имеет 4 особенности:

• x а также y координаты
• x а также y дисперсии (в моем случае ковариационная матрица диагональна)

Answer 2

Вы можете реализовать решение KNN, используя свою собственную функцию расстояния, используя простое понимание списка. Это пример использования дистанционной реализации Махаланобиса, встроенной в библиотеку OpenCV.

import numpy as np
import cv2

np_gallery=np.array(gallery)
np_query=np.array(query)

K=12

ids=[]

def insertionsort(comp_list):
    for i in range( 1, len(comp_list)):
    tmp = comp_list[i]
    k = min(i,K)
    while k > 0 and tmp[1] < comp_list[k - 1][1]:
        comp_list[k] = comp_list[k - 1]
        k -= 1
    comp_list[k] = tmp

def search():
    for q in np_query:
        c = [(i,cv2.Mahalanobis(q, x, icovar)) for i, x in enumerate(np_gallery)]
        insertionsort(c)
        ids.append(map(lambda tup: tup[0], c[0:K]))

или же

def search():
    for q in np_query:
        c = [(i,cv2.Mahalanobis(q, x, icovar)) for i, x in enumerate(np_gallery)]
        ids.append(map(lambda tup: tup[0], sorted(c, key=lambda tup: tup[1])[0:K]))

В первом случае я использую вариант вставки сортировки с учетом параметра K. Что может быть более эффективным, когда N >> K