python - 获取 k 倒数最近邻

Question

我的问题的背景信息:

如果两个对象在彼此的 k-最近邻之间，则它们被称为彼此的 k-倒数最近邻。我只对属于不相交组的对象感兴趣。例如，考虑两组数字 S = {0, 1, 2}，T = {0.1, 1.1, 1.9} 和 k=2。
对于 S 组，

T 中 0 的 k 最近邻为 0.1、1.1。

T 中 1 的 k 最近邻为 1.1、1.9。

T 中 2 的 k 最近邻为 1.9、2.1。

而对于T组，

S 中 0.1 的 k 最近邻为 0, 1。

S 中 1.1 的 k 最近邻是 1, 2。

S 中 1.9 的 k 最近邻为 1, 2。

因此 k 倒数最近邻对是 (0, 0.1), (1, 1.1), (1, 1.9), (2, 1.9)。

设 {A, B, C, D, E} 和 {W, X, Y, Z} 是一些对象的两个不相交的组。假设欧几里得度量在这些组之间有意义，并且我们有以下 5x4 距离矩阵:

distmat = np.array([[5,   1,   4, 7.5], 
                    [3,  10,   2,  11], 
                    [9, 2.5,   8,   3], 
                    [1,   3, 5.5,   5],
                    [4,   6, 3.5,   8]])

五行分别代表物体A、B、C、D、E到W、X、Y、Z的距离。

问题:获得 A 和 B 的 k 倒数最近邻的有效方法是什么？

获得k-最近邻是可以的，我用了 np.argsort(distmat)然后检索索引小于 k 的对象。

这是我为互惠部分所做的尝试。 wlog 考虑对象 A。对于 A 的每个 k 最近邻 N，转置 distmat并检查第 N 行。如果 A 是 N 的 k 最近邻，则它们是倒数；否则他们不是。一些粗略的代码:

for index_N, N in enumerate(knn_A): 
    knn_N = get_knn(distmat.T[index_N]
    if A in knn_N: 
        print("{} and {} are {}-reciprocals".format(A, N, k))

有什么改进建议吗？这很慢，因为我已经有很多嵌套的 for 循环，而且这两个组的大小可能很大。

Answer 1

您将不得不检查这是否更快，因为我在您提供的代码中没有看到任何嵌套的 for 循环。使用您的示例(我认为由于“T 中 2 的 k 最近邻居是 1.9, 2.1”这一行，我认为它的倒数邻居是错误的。 - 其中 2.1 不在集合中，如果您的意思是 1.1，则 (2, 1.1) 也是互惠邻居。

import numpy as np 
import itertools 

# set k and make the example set
k = 2
s1 = [0, 1, 2]
s2 = [.1, 1.1, 1.9]

#create the distance matrix 
newarray = [ [ abs(s2j-s1i) for s2j in s2] for s1i in s1]
distmat = np.array( newarray )

#get the nearest neighbors for each set 
neighbors_si = np.argsort( distmat )
neighbors_sj = np.argsort( distmat.T )

#map element of each set to k nearest neighbors
neighbors_si = { i: neighbors_si[i][0:k] for i in range(len(neighbors_si)) }
neighbors_sj = { j: neighbors_sj[j][0:k] for j in range(len(neighbors_sj)) }

#for each combination of i and j determine if they are in each others neighbor list
for i, j in itertools.product( neighbors_si.keys(), neighbors_sj.keys() ):
    if j in neighbors_si[i] and i in neighbors_sj[j]:
        print( '{} and {} are {}-reciprocals'.format( s1[i], s2[j], k ))