最鄰近搜索

最鄰近搜索（Nearest Neighbor Search, NNS）又稱為「最近點搜索」（Closest point search），是一個在尺度空間中尋找最近點的優化問題。問題描述如下：在尺度空間M中給定一個點集S和一個目標點q ∈ M，在S中找到距離q最近的點。很多情況下，M為多維的歐幾里得空間，距離由歐幾里得距離或曼哈頓距離決定。

高德納在《計算機程序設計藝術》（1973）一書的第三章中稱之為郵局問題，即居民尋找離自己家最近的郵局。

應用

最鄰近搜索問題在很多領域中都有應用，包括：

模式識別，特別是光學字符識別
統計分類，參見KNN（k-nearest neighbor algorithm）
計算機視覺
數據庫，如基於內容的圖像檢索
編碼理論，見最大似然編碼
數據壓縮，見MPEG-2標準
嚮導系統
網絡營銷
DNA測序
拼寫檢查，建議正確拼寫。
剽竊偵查
相似比分算法，用來推斷運動員的職業表現。

方法

最鄰近搜索問題有若干種解決方案，這些算法的優劣決定於他們求解的時間複雜度和用來查找的數據結構的空間複雜度。一種通常的說法表述為「維數災難」（curse of dimensionality），指對於在大維數的歐幾里得空間裡用最鄰近搜索的話，無法找到多項式的算法和多對數的查找時間。

線性查找

最簡單的最鄰近搜索便是遍歷整個點集，計算它們和目標點之間的距離，同時記錄目前的最近點。這樣的算法較為初級，可以為較小規模的點集所用，但是對於點集的尺寸和空間的維數稍大的情況不適用。線性查找所需時間為O（Nd），其中N是S的勢，d是S的維。由於不需要建立數據結構，所以線性查找沒有存儲空間複雜度的問題。

空間分割

從七十年代起分支限界方法被應用於這個問題。對歐幾里得空間來說，這個方法被稱為空間索引或者空間訪問方法。目前已發展出好幾種分支限界方法。恐怕最簡單的當屬K-d樹，它將查找空間不斷將父節點包含的區域分為相鄰的兩部分，每部分包含原來區域中的一半點。求解時，從根節點開始在每個分叉點上對目標點進行計算，直到葉節點。對於給定的維度，查找時間複雜度為O（log N）。R樹數據結構能高效插入和刪除節點，用來解決動態環境下的最鄰近搜索。

對於一般的度量空間，分支限界方法被稱為度量樹，特別的例子有VP樹和Bk樹。

LSH

LSH（Locality sensitive hashing）通過對點進行某種度量操作後將點分組散列在不同的次點集中。在這種度量下相互間距離較近的點被分在同一個次點集的可能性較高。

具有小內部維數的空間最鄰近搜索

覆蓋樹有一個基於點集倍常量的理論界限。這個查找時間的界限是O（c¹² log n），其中c是點集的膨脹常數。

變化

在最鄰近搜索的幾個變化中，最著名的是KNN（K-nearest neighbor algorithm）和ε近似最鄰近查找（ε-approximate nearest neighbor search）。

KNN

KNN查找最鄰近的K個點。這種方法常被用在預測分析中，用某點的一些臨近點來對它估計和分類。

近似最鄰近查找

在一些應用中指需要有個對最鄰近的猜測。這種情況下，我們可以用一個不保證能每次都返回絕對正確的最近點的算法，用來提高運算速度或節約存儲空間。常常這樣的算法大都能找到正確的最近點，但這大大取決於採用點集的分布。

採用近似查找的算法包括Best Bin First和Balanced Box-Decomposition Tree。

ε近似最鄰近查找是目前流行的打破維數災難的工具。

最鄰近距離比

最鄰近距離比不直接用目標點和鄰近點的距離作為閾值，而是將與到前一個鄰近點的距離相關的比值來作為閾值。這被用在基於內容的圖像檢索中，通過基於本地特徵的相似性的「例子查找」來得到圖像。更廣泛的用途是在一些匹配問題中。

全局最近點

有時，我們需要找到在整個點集中距離所有點都最近的那個點。把最鄰近搜索在所有點上運行一次自然能解決問題，但改進的策略能避免點集中距離信息的冗餘，從而更高效地查找。比如：當我們算出了X到Y的距離，我們也同時得到了Y到X的距離，於是結果就能被以後的一次求解直接利用。

參考文獻

Arya, S., D. M. Mount, N. S. Netanyahu, R. Silverman, and A. Y. Wu. An Optimal Algorithm for Approximate Nearest Neighbor Searching in Fixed Dimensions. Journal of the ACM, vol. 45, no. 6, pp. 891-923.
Zezula, P., Amato, G., Dohnal, V., and Batko, M. Similarity Search - The Metric Space Approach. Springer, 2006. ISBN 0-387-29146-6.

外部連結

Nearest Neighbors and Similarity Search （頁面存檔備份，存於網際網路檔案館） - a website dedicated to educational materials, software, literature, researchers, open problems and events related to NN searching. Maintained by Yury Lifshits.
Metric Spaces Library （頁面存檔備份，存於網際網路檔案館） - An open-source C-based library for metric space indexing by Karina Figueroa, Gonzalo Navarro, Edgar Chávez.
ANN （頁面存檔備份，存於網際網路檔案館） - A Library for Approximate Nearest Neighbor Searching by David M. Mount and Sunil Arya.
STANN - A Simple Threaded Approximate Nearest Neighbor Search Library in C++ by Michael Connor and Piyush Kumar.
MESSIF - Metric Similarity Search Implementation Framework by Michal Batko and David Novak.
OBSearch （頁面存檔備份，存於網際網路檔案館） - Metric Similarity Search（distributed, GPL）. Implementation by Arnoldo Muller, developed during Google Summer of Code 2007.