查找3D歐氏空間中的10個最近點，對於500萬個元素目錄中的每個元素

假設我有一個500萬個點的目錄，其3D空間中的x，y，z位置。對於這500萬個點中的每一個，我想找到最接近它的10個點（直接的3D歐幾里得距離公式）。在Python中，如果我對錶中的每個元素執行一個簡單的for循環，並在for循環中執行一個數組操作（而不是循環的第二個操作）以查找當前點和所有其他點之間的距離在目錄中，這將需要幾天/周。我試過一些涉及排序和計算點之間距離的東西，每個表格元素周圍只有+/-幾千行，但這仍然需要幾天時間。查找3D歐氏空間中的10個最近點，對於500萬個元素目錄中的每個元素

什麼是在Python中做到這一點的更快的方法？有沒有辦法將for循環變成某種向量化的操作？任何機器學習技術（例如scikit-learn）會有幫助嗎？或者以某種方式並行化代碼有幫助？

來源

2017-09-12 quantumflash

鑑於你的數據，即維3d的歐幾里德空間，試圖找到最近的10個鄰居，這聽起來像[空間分區]（https://en.wikipedia.org/wiki/Nearest_neighbor_search#Space_partitioning）的一個很好的候選者，它涉及到將數據放入kd-樹，它可以給你真正的好表現！ 'scikit-learn'已經有kd-tree實現。這種方法具有*精確*而不是近似的附加好處。 –

我在R中使用了一個名爲RANN的包，它查找「近似」最近的鄰居。我用幾分鐘的時間用25M觀察值和8個維度運行它，結果足以滿足我的用例。

我不知道是否有我用包的Python版本，但我發現這個鏈接，有很多替代品：Benchmark of ANN Libraries

Benchmark of ANN Libraries

來源

2017-09-12 18:27:29 Dustin

查找3D歐氏空間中的10個最近點，對於500萬個元素目錄中的每個元素

回答

相關問題