最鄰近搜尋（NNS）又稱為“最近點搜尋”（Closest point search），是一個在尺度空間中尋找最近點的最佳化問題。問題描述如下：在尺度空間M中給定一個點集S和一個目標點q ∈ M，在S中找到距離q最近的點。很多情況下，M為多維的歐幾里得空間，距離由歐幾里得距離或曼哈頓距離決定。
基本介紹
- 中文名：最鄰近搜尋
- 外文名：Closest point search
- 又稱為：最近點搜尋
- 縮寫：NNS
定義,套用,方法,線性查找,空間分割,LSH,具有小內部維數的空間最鄰近搜尋,變化,KNN,近似最鄰近查找,最鄰近距離比,全局最近點,
定義
高德納在《電腦程式設計藝術》（1973）一書的第三章中稱之為 郵局問題，即居民尋找離自己家最近的郵局。
套用
最鄰近搜尋問題在很多領域中都有套用，包括：
方法
最鄰近搜尋問題有若干種解決方案，這些算法的優劣決定於他們求解的時間複雜度和用來查找的數據結構的空間複雜度。一種通常的說法表述為“維數災難”（curse of dimensionality），指對於在大維數的歐幾里得空間裡用最鄰近搜尋的話，無法找到多項式的算法和多對數的查找時間。
線性查找
最簡單的最鄰近搜尋便是遍歷整個點集，計算它們和目標點之間的距離，同時記錄目前的最近點。這樣的算法較為初級，可以為較小規模的點集所用，但是對於點集的尺寸和空間的維數稍大的情況不適用。線性查找所需時間為O（Nd），其中N是S的勢，d是S的維。由於不需要建立數據結構，所以線性查找沒有存儲空間複雜度的問題。
空間分割
從七十年代起分支限界方法被套用於這個問題。對歐幾里得空間來說，這個方法被稱為空間索引或者空間訪問方法。目前已發展出好幾種分支限界方法。恐怕最簡單的當屬K-d樹，它將查找空間不斷將父節點包含的區域分為相鄰的兩部分，每部分包含原來區域中的一半點。求解時，從根節點開始在每個分叉點上對目標點進行計算，直到葉節點。對於給定的維度，查找時間複雜度為O（logN）。R樹數據結構能高效插入和刪除節點，用來解決動態環境下的最鄰近搜尋。
對於一般的度量空間，分支限界方法被稱為度量樹，特別的例子有VP樹和Bk樹。
LSH
LSH（Locality sensitive hashing）通過對點進行某種度量操作後將點分組散列在不同的次點集中。在這種度量下相互間距離較近的點被分在同一個次點集的可能性較高。
具有小內部維數的空間最鄰近搜尋
覆蓋樹有一個基於點集倍常量的理論界限。這個查找時間的界限是O（clog 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的距離，於是結果就能被以後的一次求解直接利用。
