搜索k个最近的点

Question

我有很多看起来像这样的功能：

id1 28273 20866 29961 27190 31790 19714 8643 14482 5384 ....  upto 1000
id2 12343 45634 29961 27130 33790 14714 7633 15483 4484 ....  
id3 ..... ..... ..... ..... ..... ..... .... ..... .... .... .   .   .
...
id200000 .... .... ... ..  .  .  .  .

我想为每个id欧几里得距离进行计算，并对它们进行排序以找到5个最近点。因为我的数据集非常大。最好的方法是什么

Answer 1

scikit-learn具有nearest neighbor search。示例：

1. 将数据加载到NumPy数组中。

   >>> import numpy as np
   >>> X = np.array([[28273, 20866, 29961, 27190, 31790, 19714, 8643, 14482, 5384, ...],
                     [12343, 45634, 29961, 27130, 33790, 14714, 7633, 15483, 4484, ...], 
                     ...
                     ])
   

   （仅显示两点。）

2. 适合NearestNeighbors对象。

   >>> from sklearn.neighbors import NearestNeighbors
   >>> knn = NearestNeighbors(n_neighbors=5)
   >>> knn.fit(X)
   NearestNeighbors(algorithm='auto', leaf_size=30, n_neighbors=5, p=2,
            radius=1.0, warn_on_equidistant=True)
   

   p=2表示欧几里得（L2）距离。 p=1表示曼哈顿（L1）距离。

3. 执行查询。要获取X[0]的邻居，您的第一个数据点：

   >>> knn.kneighbors(X[0], return_distance=False)
   array([[0, 1]])
   

   因此，X[0]的最近邻居是X[0]本身和X[1]（当然）。

请确保您设置了n_neighbors=6，因为设置中的每个点都将是其自己最近的邻居。

免责声明：我参与了scikit-learn开发，因此这不是公正的建议。

Answer 2

根据您的问题，尚不清楚您的问题具体是什么。到目前为止，我已经了解到，您需要计算大量数据点之间的欧几里得距离。 Python中最快的解决方案可能是使用scipy.spatial.distance模块。请看看

http://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.distance.pdist.html

和

http://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.distance.cdist.html

您将必须熟悉numpy数据类型，为这些功能之一开发输入数据，并进一步评估结果数据。您可能最终会尝试获取数组的一些最大/最小N值，这时How to get indices of N maximum values in a numpy array?可能会有所帮助。