尋找K最近點

我有一個大的功能集，看起來像這樣：尋找K最近點

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最近點。因爲我的數據集非常大。什麼是最好的方式來做到這一點。

來源

2012-09-11 Rafaelopasa

歡迎來到Stack Overflow！我們鼓勵你[研究你的問題]（http://stackoverflow.com/questions/how-to-ask）。如果你已經[嘗試了某些東西]（http://whathaveyoutried.com/），請將其添加到問題中 - 如果沒有，請先研究並嘗試您的問題，然後再回來。 – 2012-09-11 12:15:59

是否有不同的位置（即，您計算的是1000維空間）。如果是這樣，當你說「歐幾里德距離」到哪個點時？如果它是一個團體，請你可以定義「k-nearest」......這並不明顯。 –

例如，如果我將一個輸入作爲id2給腳本。我期望結果：關於id2的5個最近點。我想計算從id2到數據集中所有點的歐幾里德距離，對它們進行排序並返回5個最近點。 – Rafaelopasa

從你的問題，它不是完全清楚你的問題的具體細節。到目前爲止，我的理解是，你需要計算大量數據點之間的歐氏距離。 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?可能會提供幫助。

來源

2012-09-11 12:24:41

如果總和超出限制（也就是說，如果結果明顯比其他已經計算的結果大），則可能會中止計算，從而加速該過程。不過，不知道這是否可以在scipy中完成。 – Alfe

例如，如果我將一個輸入作爲「id2」和上面的「feature-set file.txt」給腳本。我期望得到與「id2」相關的5個最近點的結果。我想計算從「id2」到數據集中所有點的歐幾里得距離，對它們進行排序並返回5個最近點。感謝您的輸入 – Rafaelopasa

scikit-learn有nearest neighbor search。例如：

將您的數據加載到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]])

（只是兩個點示出。）

安裝一個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）的距離。

執行查詢。要獲得X[0]的鄰居，你的第一個數據點：
```
>>> knn.kneighbors(X[0], return_distance=False) 
array([[0, 1]]) 
```
所以，X[0]最近的鄰居是X[0]本身X[1]（當然）。

確保你設置了n_neighbors=6，因爲你的集合中的每個點都將是它自己的最近鄰居。

免責聲明：我參與了scikit-learn的開發，所以這不是沒有偏見的建議。

來源

2012-09-11 13:31:11

例如，如果我將一個輸入作爲「id2」給腳本。我期望得到與「id2」相關的5個最近點的結果。我想計算從「id2」到數據集中所有點的歐幾里得距離，對它們進行排序並返回5個最近點。感謝您的輸入。我看到你從數據集中分離出了「身份證號碼」。但是，我想將'idn'與它們的值一起保存在同一個數組中。所以當我排序5個最近的點時，我可以知道它們屬於哪個ID。 – Rafaelopasa

@Rafaelopasa：那麼？將一個添加到索引並在前面粘貼'id'。或者如果它們不連續，請保留一組ID。 –

回答

相關問題