Найти ближайшее / похожее значение (вектор) внутри матрицы

Question

допустим, у меня есть следующая матрица (упрощенно):

matrix = np.array([[1, 1],
               [2, 2],
               [5, 5],
               [6, 6]]
              )

А теперь я хочу получить вектор из матрицы, ближайшей к вектору "поиска":

search_vec = np.array([3, 3])

Что я сделал, так это:

min_dist = None
result_vec = None
for ref_vec in matrix:
    distance = np.linalg.norm(search_vec-ref_vec)
    distance = abs(distance)
    print(ref_vec, distance)
    if min_dist == None or min_dist > distance:
        min_dist = distance
        result_vec = ref_vec

Результат работает, но Есть ли нативное решение, чтобы сделать его более эффективным? Моя проблема в том, что чем больше, тем большеМатрица становится тем медленнее будет весь процесс.Существуют ли другие решения, которые решают эти проблемы более элегантно и эффективно?

Answer 1

Подход № 1

Мы можем использовать Cython-powered kd-tree для быстрого поиска ближайшего соседа , что очень эффективно как с точки зрения памяти, так и с производительностью -

In [276]: from scipy.spatial import cKDTree

In [277]: matrix[cKDTree(matrix).query(search_vec, k=1)[1]]
Out[277]: array([2, 2])

Подход № 2

С SciPy's cdist -

In [286]: from scipy.spatial.distance import cdist

In [287]: matrix[cdist(matrix, np.atleast_2d(search_vec)).argmin()]
Out[287]: array([2, 2])

Подход № 3

С Scikit-learn's Ближайшие соседи -

from sklearn.neighbors import NearestNeighbors

nbrs = NearestNeighbors(n_neighbors=1).fit(matrix)
closest_vec = matrix[nbrs.kneighbors(np.atleast_2d(search_vec))[1][0,0]]

Подход № 4

С Scikit-learn's kdtree -

from sklearn.neighbors import KDTree
kdt = KDTree(matrix, metric='euclidean')
cv = matrix[kdt.query(np.atleast_2d(search_vec), k=1, return_distance=False)[0,0]]

Подход № 5

Из пакета eucl_dist (отказ от ответственности: я его автор) и следуя wiki contents, мы можем использовать matrix-multiplication -

M = matrix.dot(search_vec)
d = np.einsum('ij,ij->i',matrix,matrix) + np.inner(search_vec,search_vec) -2*M
closest_vec = matrix[d.argmin()]