我正在尝试在diffrent数据集中的新点数组中为每个元素找到最近的邻居，这将是快速的，而且不占用内存。我更关心的是将代码适应更多的邻居，而不是更多的维度。
基于https://glowingpython.blogspot.com/2012/04/k-nearest-neighbor-search.html?showComment=1355311029556#c8236097544823362777我写过k近邻搜索，但记忆力很强。在我的实际问题中，我有100万个值要搜索，需要匹配的10万个点，1万个x 10万个阵列估计为600GiB。
有更好的方法吗？
我尝试过使用平分(基于整数列表，获取最接近给定值的数字(，但我必须循环100k次，这需要一些时间，尤其是我必须进行多次搜索。
适用于小型数据集的好代码-能够找到K个最近的邻居，并可用于许多数据转换(按维度循环(：
def knn_search(search_for, search_in, K = 1,
return_col = ["ID"],
col = 'A'):
#print(col)
a_search_in = array(search_in[col])
a_search_for = array(search_for[col])
#print('a')
a = np.tile(a_search_for, [a_search_in.shape[0], 1]).T
#print('b')
b = np.tile(a_search_in, [a_search_for.shape[0], 1])
#print('tdif')
t_diff = a - b
#print('suma')
diff = np.square(t_diff)
# sorting
idx = argsort(diff)
# return the indexes of K nearest neighbours
if search_for.shape[0] == 1:
return idx[:K]
elif K == 1:
return search_in.iloc[np.concatenate(idx[:,:K]), :][return_col]
else:
tmp = pd.DataFrame()
for i in range(min(K, search_in.shape[0])):
tmp = pd.concat([tmp.reset_index(drop=True),
search_in.iloc[idx[:,i], :][[return_col]].reset_index(drop=True)],
axis=1)
return tmp
一维和一维邻居的好代码：
def knn_search_1K_1D(search_for, search_in,
return_col = ["ID"],
col = 'A'):
sort_search_in = search_in.sort_values(col).reset_index()
idx = np.searchsorted(sort_search_in[col], search_for[col])
idx_pop = np.where(idx > len(sort_search_in) - 1, len(sort_search_in) - 1, idx)
t = sort_search_in.iloc[idx_pop , :][[return_col]]
search_for_nn = pd.concat([search_for.add_prefix('').reset_index(drop=True),
t.add_prefix('nn_').reset_index(drop=True)],
axis=1)
K个最近邻居的当前工作解决方案>1和1维，但在上述的真实情况下计算需要一个多小时
def knn_search_nK_1D(search_for, search_in, K = 1,
return_col = ["ID"],
col = 'A'):
t = []
#looping one point by one
for i in range(search_for.shape[0]):
y = search_in[col]
x = search_for.iloc[i, :][col]
nn = np.nanmean(search_in.iloc[np.argsort(np.abs(np.subtract(y, x)))[0:K], :][return_col])
t.append(nn)
search_for_nn = search_for
search_for_nn['nn_' + return_col] = t
示例数据：
search_for = pd.DataFrame({'ID': ["F", "G"],
'A' : [-1, 9]})
search_in = pd.DataFrame({'ID': ["A", "B", "C", "D", "E"],
'A' : [1, 2, 3, 4, 5 ]})
t = knn_search(search_for = search_for ,
search_in = search_in,
K = 1,
return_col = ['ID'],
col = 'A')
print(t)
# ID
#0 A
#4 E
您想拥有自己的实现吗？如果是这样的话，你可以在KNN中使用k-d树，它会更有效率，否则，你可以使用KNN库支持GPU，比如knn_cuda
更新
你可以试试，cuml。