Numpy - Нахождение ближайших соседей умножения матриц - PullRequest
Новая
       17

Numpy - Нахождение ближайших соседей умножения матриц

1 голос
/ 05 мая 2019

У меня есть набор данных из тысячи 128 пространственных объектов в форме, например, (1000,128).

Я хочу найти отсортированных ближайших соседей 128-мерного объекта в форме (128,1).

Расстояние, рассчитанное с помощью умножения матриц между набором данных (1000,128) и признаком (128,1), которое дает массив сходств в форме (1000,1):

DATASET (1000,128) x FEATURE (128,1) = СРАВНЕНИЯ (1000,1)

Это делается с помощью: 

# features.shape=(1000,128) ; feature.shape=(128,1) ; similarities.shape=(1000,1)
similarities = features.dot(feature)

После вычисления расстояния (сходства), Iнахожу ближайших соседей, используя код ниже: 

# The n Nearest Neighbors Indexes (But Not Sorted)
nearest_neighbours_indexes_unsorted = np.argpartition(similarities, kth=-n)[-n:]

# The n Nearest Neighbors (But Not Sorted)
nearest_neighbours_similarities_unsorted = similarities[nearest_neighbours_indexes_unsorted]

# The Indexes of n Nearest Neighbors Sorted
nearest_neighbours_indexes_sorted = np.flip(nearest_neighbours_indexes_unsorted[np.argsort(nearest_neighbours_similarities_unsorted)], axis=0)

Этот код работает очень быстро для миллионов данных (мне интересно, если у кого-то есть совет, чтобы сделать это быстрее) Но я хочу иметь возможностьчтобы найти ближайших соседей более чем одной функции за один раз:

DATASET (1000,128) x FEATURE (128, n) = ПОДОБНЫЕ (1000, n)

Один из способов заключается вРассчитайте приведенный выше код для каждой функции в цикле (что медленно), а другой способ - изменить код, чтобы приспособить его к многомерной индексации, и вот где я застрял: я не знаю, как написать приведенный выше код для функцийв форме (128, n), а не (128,1).

1 Ответ

2 голосов
/ 05 мая 2019

Вспомогательные функции для получения наибольших, наименьших n-индексов, элементов по оси

Вот вспомогательная функция для выбора верхних n-largest индексов по общей оси из универсального ndarray, использующего np.argpartition и np.take_along_axis - 

def take_largest_indices_along_axis(ar, n, axis):    
    s = ar.ndim*[slice(None,None,None)]
    s[axis] = slice(-n,None,None)
    idx = np.argpartition(ar, kth=-n, axis=axis)[tuple(s)]
    sidx = np.take_along_axis(ar,idx, axis=axis).argsort(axis=axis)
    return np.flip(np.take_along_axis(idx, sidx, axis=axis),axis=axis)

Расширение этого значения для получения n-наименьших индексов - 

def take_smallest_indices_along_axis(ar, n, axis):    
    s = ar.ndim*[slice(None,None,None)]
    s[axis] = slice(None,n,None)
    idx = np.argpartition(ar, kth=n, axis=axis)[tuple(s)]
    sidx = np.take_along_axis(ar,idx, axis=axis).argsort(axis=axis)
    return np.take_along_axis(idx, sidx, axis=axis)

И расширение этих значений для выбора наибольшегоили самые маленькие n сами элементы, это было бы с простым использованием np.take_along_axis, как указано далее - 

def take_largest_along_axis(ar, n, axis):
    idx = take_largest_indices_along_axis(ar, n, axis)
    return np.take_along_axis(ar, idx, axis=axis)

def take_smallest_along_axis(ar, n, axis):
    idx = take_smallest_indices_along_axis(ar, n, axis)
    return np.take_along_axis(ar, idx, axis=axis)

Образцы прогонов 

# Sample setup
In [200]: np.random.seed(0)
     ...: ar = np.random.randint(0,99,(5,5))

In [201]: ar
Out[201]: 
array([[44, 47, 64, 67, 67],
       [ 9, 83, 21, 36, 87],
       [70, 88, 88, 12, 58],
       [65, 39, 87, 46, 88],
       [81, 37, 25, 77, 72]])

Takeсамые большие n индексы, элементы по оси - 

In [202]: take_largest_indices_along_axis(ar, n=2, axis=0)
Out[202]: 
array([[4, 2, 2, 4, 3],
       [2, 1, 3, 0, 1]])

In [203]: take_largest_indices_along_axis(ar, n=2, axis=1)
Out[203]: 
array([[4, 3],
       [4, 1],
       [2, 1],
       [4, 2],
       [0, 3]])

In [251]: take_largest_along_axis(ar, n=2, axis=0)
Out[251]: 
array([[81, 88, 88, 77, 88],
       [70, 83, 87, 67, 87]])

In [252]: take_largest_along_axis(ar, n=2, axis=1)
Out[252]: 
array([[67, 67],
       [87, 83],
       [88, 88],
       [88, 87],
       [81, 77]])

Возьмите самые маленькие n индексы, элементы по оси - 

In [232]: take_smallest_indices_along_axis(ar, n=2, axis=0)
Out[232]: 
array([[1, 4, 1, 2, 2],
       [0, 3, 4, 1, 0]])

In [233]: take_smallest_indices_along_axis(ar, n=2, axis=1)
Out[233]: 
array([[0, 1],
       [0, 2],
       [3, 4],
       [1, 3],
       [2, 1]])

In [253]: take_smallest_along_axis(ar, n=2, axis=0)
Out[253]: 
array([[ 9, 37, 21, 12, 58],
       [44, 39, 25, 36, 67]])

In [254]: take_smallest_along_axis(ar, n=2, axis=1)
Out[254]: 
array([[44, 47],
       [ 9, 21],
       [12, 58],
       [39, 46],
       [25, 37]])

Решение нашего случая здесь

В нашем случае предположим, что входное значение равно similarities и имеет форму (1000,128), представляющее 1000 точек данных и 128 объектов, и мы хотим найти самые большие, скажем, n=10 объекты для каждой из этих точек данных, затембудет - 

take_largest_indices_along_axis(similarities, n=10, axis=1) # indices
take_largest_along_axis(similarities, n=10, axis=1) # elements

Конечный массив индексов / значений будет of shape (1000, n).

Пробный прогон с заданной формой набора данных - 

In [257]: np.random.seed(0)
     ...: similarities = np.random.randint(0,99,(1000,128))

In [263]: take_largest_indices_along_axis(similarities, n=10, axis=1).shape
Out[263]: (1000, 10)

In [264]: take_largest_along_axis(similarities, n=10, axis=1).shape
Out[264]: (1000, 10)

Если вместо этого вы хотели получить n наибольших точек данных для каждой из этих функций, этоесли окончательный массив индексов / значений будет иметь форму (n, 128), тогда используйте axis=0.

...