скупой придурок получает только двух ближайших соседей - PullRequest
Новая
       11

скупой придурок получает только двух ближайших соседей

1 голос
/ 29 января 2020

Я вычислял попарные расстояния с помощью scipy, и я пытаюсь найти расстояния до двух ближайших соседей. Мое текущее рабочее решение: 

dists = squareform(pdist(xs.todense()))
dists = np.sort(dists, axis=1)[:, 1:3]

Однако метод квадратной формы является пространственно очень дорогим и несколько избыточным в моем случае. Мне нужны только два ближайших расстояния, а не все. Есть ли простой обходной путь?

Спасибо!

1 Ответ

1 голос
/ 30 января 2020

Соотношение между линейным индексом и (i, j) матрицы расстояний верхнего треугольника не является прямым или легко обратимым (см. Примечание 2 в квадратной форме до c).

Однако, перебирая все индексы, можно получить обратное соотношение: 

import numpy as np
import matplotlib.pyplot as plt

from scipy.spatial.distance import pdist

def inverse_condensed_indices(idx, n):
    k = 0
    for i in range(n):
        for j in range(i+1, n):
            if k == idx:
                return (i, j)
            k +=1
    else:
        return None

# test
points = np.random.rand(8, 2)
distances = pdist(points)
sorted_idx = np.argsort(distances)
n = points.shape[0]
ij = [inverse_condensed_indices(idx, n)
      for idx in sorted_idx[:2]]

# graph
plt.figure(figsize=(5, 5))
for i, j in ij:
    x = [points[i, 0], points[j, 0]]
    y = [points[i, 1], points[j, 1]]
    plt.plot(x, y, '-', color='red');

plt.plot(points[:, 0], points[:, 1], '.', color='black');
plt.xlim(0, 1); plt.ylim(0, 1);

Кажется, это немного быстрее, чем при использовании squareform: 

%timeit squareform(range(28))
# 9.23 µs ± 63 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

%timeit inverse_condensed_indices(27, 8)
# 2.38 µs ± 25 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
...