已解決430363個問題，去搜搜看，總會有你想問的

高維數據中的最近鄰居？

首頁猿問高維數據中的最近鄰居？

高維數據中的最近鄰居？

算法算法與數據結構

幕布斯7119047 2019-10-14 10:54:12

我幾天前問了一個問題，該問題是如何找到給定向量的最近鄰居。我的向量現在是21維，在繼續下一步之前，因為我既不是機器學習也不是數學領域的專家，所以我開始問自己一些基本問題：歐幾里得距離是一個很好的度量標準，可以用來首先找到最近的鄰居？如果沒有，我有什么選擇？另外，如何確定用于確定k個鄰居的正確閾值？是否可以進行一些分析以找出該值？以前，有人建議我使用kd-Trees，但Wikipedia頁面上明確指出，對于高維，kd-Tree幾乎等同于蠻力搜索。在那種情況下，有效地找到一百萬個點數據集中的最近鄰居的最佳方法是什么？有人可以澄清以上部分（或全部）問題嗎？

查看完整描述

3 回答

Smart貓小萌

TA貢獻1911條經驗獲得超7個贊

我目前正在研究此類問題-分類，最近鄰居搜索-以獲取音樂信息。

您可能對近似最近鄰（ANN）算法感興趣。這個想法是讓算法允許返回足夠近的鄰居（也許不是最近的鄰居）。這樣可以減少復雜性。您提到了kd-tree；那是一個例子。但是正如您所說，kd-tree在高維度上效果不佳。實際上，所有當前的索引技術（基于空間劃分）都降級為對足夠高的尺寸進行線性搜索[1] [2] [3]。

在最近提出的ANN算法中，也許最流行的是局部敏感哈希（LSH），它將高維空間中的一組點映射到一組bin中，即哈希表[1] [3]。但是與傳統的哈希不同，對位置敏感的哈希將附近的點放置在同一容器中。

LSH具有一些巨大的優勢。首先，它很簡單。您只需為數據庫中的所有點計算哈希，然后根據它們創建哈希表。要進行查詢，只需計算查詢點的哈希值，然后從哈希表中檢索同一bin中的所有點。

其次，有一個嚴格的理論可以支持其性能?？梢钥闯?，查詢時間在數據庫大小上是次線性的，即比線性搜索快?？於嗌偃Q于我們可以忍受的近似程度。

最后，LSH與的任何Lp規范兼容0 < p <= 2。因此，要回答第一個問題，您可以將LSH與歐幾里德距離度量標準結合使用，或者將其與曼哈頓（L1）距離度量標準結合使用。漢明距離和余弦相似度也有變體。

Malcolm Slaney和Michael Casey在2008年為IEEE Signal Processing Magazine撰寫了不錯的綜述[4]。

LSH似乎已在所有地方得到應用。您可能需要嘗試一下。

[1] Datar，Indyk，Immorlica，Mirrokni，“基于p穩定分布的局部敏感散列方案”，2004年。

[2] Weber，Schek，Blott，“高維空間中相似性搜索方法的定量分析和性能研究”，1998年。

[3] Gionis，Indyk，Motwani，“通過散列在高維中進行相似性搜索”，1999年。

[4] Slaney，Casey，“對位置敏感的哈希，用于尋找最近的鄰居”，2008年。

反對回復 2019-10-14

3 回答
0 關注
1028 瀏覽

關注

添加回答

舉報

0/150

提交

取消

亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

熱搜

最近搜索清空

高維數據中的最近鄰居？

高維數據中的最近鄰居？

3 回答

添加回答

高維數據中的最近鄰居？

高維數據中的最近鄰居？