高維最近鄰搜索的最佳數據結構

我實際上正在研究高維數據（〜50.000-100.000特徵），並且必須對其執行最近鄰居搜索。我知道，隨着維度的增長，KD-Tree的性能很差，而且我也讀到過，一般來說，所有空間分割數據結構都傾向於使用高維數據執行窮舉搜索。高維最近鄰搜索的最佳數據結構

此外，還有要考慮的兩個重要的事實（按相關性排序）：

精密：最近的鄰居必須要找到（不近似值）。
速度：搜索必須儘可能快。（創建數據結構的時間並不重要）。

所以，我需要的一些建議：

的數據結構來執行K-NN。
如果使用aNN（近似最近鄰居）方法會更好，請儘可能準確地設置它？

來源

2015-08-22 mavillan

對這兩個答案沒有什麼可說的？ – gsamaras

我不認爲在這樣的高維度數據中進行聚類是不明智的。有尺寸問題的詛咒。

距離的概念變得維數的增長不太精確，因爲在給定的數據集的任意兩點之間的距離收斂

我建議你找的距離的一個很好的措施，而不是高維空間上的直接歐幾里得距離。

的一些可能的解決方案在此頁中列出， https://en.wikipedia.org/wiki/Clustering_high-dimensional_data

2.1子空間聚類

2.2投影聚類

2.3混合方法

2.4關聯聚類

來源

2015-08-22 03:52:52 William

我沒有做，也不想做羣集。我正在實現一個對象識別系統，每個類只有一個樣本。所以這種情況最好的方法是最近鄰搜索。 – mavillan

我認爲你正在尋找的是一次性學習，https://en.wikipedia.org/wiki/One-shot_learning。您還可以執行深度學習算法以減小維度。 – William

我可以在高維空間執行NN搜索嗎？

號因爲維數災難的，其執行在較低維度的最近鄰搜索良好的數據結構，不能在高維的地方表現良好。事實上，查詢時間幾乎與強力的查詢時間相同，因此它是毫無價值的。

其結果是，在高維空間，一個應該去近似最近鄰（ANN）搜索。說實話，這是一個必須。

要執行ANN的數據結構是什麼？

我會建議LSH，或一些RKD樹。在我的answer這裏，我提到了一些在C++中執行ANN的好庫。但是請注意，LSH解決了R最近鄰問題，因此您可以指定參數R，該參數實際上是半徑。然後，LSH將從查詢點查找該R內的NN，因此您不能真正請求NN的。

另一方面，RKD樹可以做到這一點，並返回您的NN。我有一個項目，它建立了RKD樹的森林，並用C++執行ANN搜索，但它僅針對高維。它可以在1秒鐘內處理960個維度的10^6個圖像的GIST數據集，其中約90％的輸出是最近的鄰居。名字是kd-GeRaF。它將在下個月以分佈式版本進行更新，但它已經過測試並可以使用。它也有一個可愛的標誌。 :)

我也覺得你應該看過我answer，它說，最佳的數據結構依賴於數據。

來源

2015-08-22 19:34:52 gsamaras

您是否必須在每次插入後重新構建樹？這就是我現在要在工作中避免使用kd-tree的問題。 Tks –

No @TaxiNoiBaiHaNoi。但是，對於如何插入數據，您需要小心謹慎，因爲它可能會使樹不平衡（因爲它已經平衡）。閱讀更多[Wikipedia]（https://en.wikipedia.org/wiki/K-d_tree#Adding_elements）。 – gsamaras

高維最近鄰搜索的最佳數據結構

回答

相關問題