Voisins les plus proches avec des points incertains

J'ai deux ensembles de points 2D A et B. Je veux trouver le premier voisin le plus proche dans A pour chaque point dans B. Cependant, j'ai affaire à des points incertains (c'est-à-dire qu'un point a une matrice de covariance moyenne (vecteur 2D) et une matrice de covariance 2 * 2). Je voudrais donc utiliser la distance de Mahalanobis, mais en scikit-learn (par exemple), je ne peux pas passer une matrice de covariance pour chaque point, car elle attend une seule matrice de covariance.Voisins les plus proches avec des points incertains

Actuellement, on ne considère que les emplacements moyens (c.-à-dire de ma distribution 2D normale), j'ai:

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

Avec mes points incertains, au lieu d'utiliser la norme L2 comme une distance, je préférerais calculer (entre un point a dans A et un point b en B, la distance de Mahalanobis:

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

où C = inv(cov_a + cov_b)

où mu_a (resp mu_b) et cov_a (resp. cov_b) sont la matrice de covariance moyenne et 2 * 2 du point incertain a (respectivement b).

Source

2017-01-05 floflo29

nous montrer votre tentative, entrée code, et les résultats escomptés – depperm

La seule idée qui me vient à l'esprit est d'utiliser les vecteurs 6D comme entrées (pour stocker les emplacements et les quatre composantes de leur matrice de covariance) et de définir ma propre fonction de distance. – floflo29

je me suis retrouvé à l'aide d'une distance personnalisée:

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:])))

Ainsi un point a 4 caractéristiques:

x et y coordonnées
x et y écarts (matrice de covariance est diagonale dans mon cas)

Source

2017-01-09 09:06:39 floflo29

Vous pouvez implémenter une solution KNN en utilisant votre propre fonction de distance en utilisant simplement la compréhension de liste. Ceci est un exemple en utilisant la mise en œuvre de la distance de Mahalanobis intégrée dans la bibliothèque 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]))

Dans le premier cas, j'utilise une variante d'insertion en prenant genre en compte le paramètre K. Qui peut être plus efficace lorsque N >> K

Source

2017-01-06 21:23:59 jperezmartin

Voisins les plus proches avec des points incertains

Répondre

Questions connexes