kNN在高朦度空間動態插入

我正在尋找一種方法來做高維點（通常〜11-13維）的快速最近鄰（有希望O（log n））。在初始化結構後，我希望它在插入期間表現最佳。 KD樹出現在我的腦海裏，但如果你不做批量加載但是做動態插入，那麼kd樹不再是平衡的，而且afaik平衡是一個昂貴的操作。kNN在高朦度空間動態插入

所以，我想知道什麼樣的數據結構，你喜歡這種設置。你有高維點，你想插入和查詢最近的鄰居。

來源

2012-04-02 I J

Curse of Dimensionality阻礙了這裏。您可能會考慮應用主成分分析（PCA）來降低維度，但據我所知，沒有人對此有很好的答案。

我在處理這種類型的問題之前（在音頻和視頻指紋識別中），有時最多有30個維度。分析通常顯示某些維度沒有包含搜索相關信息（實際上是模糊搜索，我的主要目標），所以我從用於訪問數據的索引結構中省略了它們，但將它們包含在邏輯中以確定來自搜索過程中找到的候選人列表。這有效地將維度降低到易於理解的水平。

我通過嚴格量化其餘維度來進一步簡化事情，使整個多維空間被映射爲一個32位整數。我用它作爲STL地圖（紅黑樹）中的關鍵字，儘管我可以使用散列表。我能夠在一兩分鐘內動態地將數百萬條記錄動態地添加到這種結構（當然是基於RAM）中，並且搜索平均花費了大約1毫秒，儘管數據並不是均勻分佈的。搜索需要仔細枚舉映射到32位密鑰的維度中的值，但其可靠性足以用於商業產品。如果我的消息來源正確，我相信它在iTunes Match中用到了這一天。 :)

底線是，我建議你看看你的數據，並做一些自定義的利用它的功能，使快速索引和搜索。找出變化最大的維度，並且彼此最獨立。將這些量化並將它們用作索引中的關鍵字。索引中的每個存儲桶都包含共享該密鑰的所有項目（可能會有多個）。要查找最近的鄰居，請查看「附近」鍵並在每個桶內查找附近的值。祝你好運。

p.s.我寫了一篇關於我的技術的論文，可用here。抱歉關於付費牆。也許你可以在別處找到免費的副本。如果您對此有任何疑問，請告知我們。

來源

2012-04-02 07:25:09

謝謝，但我不想降低數據的維數，因爲我想在原始空間中使用精確的kNN。 – 2012-04-03 01:37:59

夠公平的，儘管我從未看到在不同距離搜索固定數量的鄰居的價值。在固定距離搜索可變數量的鄰居對我來說似乎更實用。 – 2012-04-03 06:18:24

@Randall，很好。「STL地圖中的32位密鑰」是指完全匹配，還是32個1位nighhbors？任何想法[bit-string-nearest-neighbor-searching]（http://stackoverflow.com/questions/9959728/bit-string-nearest-neighbour-searching） - 看起來是NP完全的？ – denis 2012-04-15 10:31:11

想到的另一個數據結構是封面樹。與最初開發用於回答範圍查詢的KD樹不同，此數據結構對於最近鄰查詢是最佳的。它已被用於涉及計算所有數據點的k個最近鄰居的n體問題。在密度估算方案（Parzen窗口）中也會出現這樣的問題。我不太瞭解您的具體問題，但我確實知道這個數據結構有在線版本。查看Alexander Gray的頁面，並且這個link

來源

2012-04-02 19:47:55 killogre

謝謝。將檢查出 – 2012-04-04 01:51:14

我不知道封面樹。感謝您的提示，@ killogre。 – 2012-04-10 22:36:02

如果您使用具有相當大的桶大小的桶Kd樹，它可以讓樹更好地瞭解當葉子太滿時分割的位置。 Robocode中的傢伙在極其苛刻的時間限制下做到了這一點，隨機插入發生在飛行中，kNN在1ms以下k> 80，d> 10和n> 30k。看看這個kD-Tree Tutorial，它解釋了一堆kD-Tree增強功能以及如何實現它們。

來源

2012-10-23 20:44:42 jkflying

根據我的經驗，11-13尺寸不是太差 - 如果你批量加載。批量加載的R樹（與k-d樹相比保持平衡！）和k-d樹應該仍然比線性掃描更好。

一旦你完全充滿活力，我的經驗會變得更糟。粗略地說：對於批量加載的樹木，我看到20倍的加速，增量式構建R樹只有7倍。所以它確實還清經常重建樹。取決於你如何組織你的數據，它可能比你想象的要快得多。我使用的k-d-tree的批量負載是O(n log n)，我讀到也有O(n log log n)變體。低常數因子。對於R-tree，Sort-Tile-Recursive是目前爲止我見過的最好的批量加載，並且也是O(n log n)，具有低常數因子。

所以是的，在高維度，我會考慮不時重新加載樹。

來源

2012-12-23 23:01:47

kNN在高朦度空間動態插入

回答

相關問題