最近傍探索のソースを表示

'''最近傍探索'''（{{lang-en-short|Nearest neighbor search, NNS}}）は、[[距離空間]]における最も近い点を探す[[最適化問題]]の一種、あるいはその解法。'''近接探索'''（{{lang-en-short|proximity search}}）、'''類似探索'''（{{lang-en-short|similarity search}}）、'''最近点探索'''（{{lang-en-short|closest point search}}）などとも呼ぶ。問題はすなわち、距離空間 ''M'' における点の集合 ''S'' があり、クエリ点 ''q'' ∈ ''M'' があるとき、''S'' の中で ''q'' に最も近い点を探す、という問題である。多くの場合、''M'' には ''d''次元の[[ユークリッド空間]]が採用され、距離はユークリッド距離か[[マンハッタン距離]]で測定される。低次元の場合と高次元の場合で異なるアルゴリズムがとられる。

[[ドナルド・クヌース]]は、''[[The Art of Computer Programming]]'' Vol.3（1973年）で、これを郵便局の問題で表した。これはすなわち、ある住所に最も近い郵便局を求める問題である。

== 解法 ==
最近傍探索問題の解法としては、様々なものが提案されている。そのアルゴリズムの品質と利便性は、[[クエリ]]への応答にかかる時間と[[データ構造]]が使用するメモリ量で判断される。直観的には、[[次元の呪い]]と呼ばれる特徴があるため、あらゆる場合に最適な解法は存在しないと言われている。

=== 線形探索 ===
最も単純な解法は、クエリで示された点と[[データベース]]内の他の全ての点との距離を全部計算して、最も近いものを探すことである。データベースが小さい場合は問題ないが、その大きさや次元が増大すると急激に遅くなる。線形探索の処理時間は O(''Nd'') であり、''N'' は ''S'' の[[濃度 (数学)|基数]]、''d'' は ''S'' の次元である。検索時にデータ構造は特に必要ないので、データベース以外の余分なメモリ消費はない。

=== 空間分割 ===
1970年代から、この問題に[[分枝限定法]]が適用されるようになった。ユークリッド空間の場合、この手法は[[空間索引]]または空間アクセス法として知られている。NNS問題を解くための空間分割法もいくつか考案された。最も単純な手法としては[[kd木]]がある。これは、探索空間を再帰的に半分に2分割していくものである。クエリは、この木を根から葉に向かって辿っていくことで処理される（各ノードでどちらに行くかをクエリの内容と比較して判断する）。一定次元でのクエリ処理時間は O(log ''N'') となる。[[R木]]というデータ構造も最近傍探索用に設計された。

一般の距離空間における分枝限定法の適用例として、[[:en:VP-tree|VP木]]や[[:en:Bk-tree|Bk木]]がある。

=== 局所性鋭敏型ハッシュ ===
[[局所性鋭敏型ハッシュ]]（LSH）は、距離空間内の各点に距離空間的操作を施すことで、グループ分けする技法である。ある距離尺度で互いに近い点は同じグループになる確率が高くなる。

== 派生 ==
*[[k近傍法]] は、クエリに最も近い方から ''k'' 個の近傍を特定する。 
*'''近似最近傍探索''' ({{lang-en-short|approximate nearest neighbor, ANN}}) は、[[次元の呪い]]への対策として最近特に人気がある。
*'''最近傍距離比''' ({{lang-en-short|nearest neighbor distance ratio}}) とは、距離の絶対値ではなく距離と距離の比を用いる方式。内容に基づく画像検索（[[:w:Content-based image retrieval|CBIR]]）で使われることがある。より一般的には、いくつかの[[マッチング (グラフ理論)|マッチング]]問題と関連する。
*'''最近点対問題''' ({{lang-en-short|closest pair problem}})とは、点集合の中から最も近い距離の点のペアを1組捜すアルゴリズムであり、<math>O(n \log n)</math> で求められる。低次元空間のアルゴリズムは『アルゴリズムイントロダクション』(T. コルメン)や『アルゴリズムC』(R. セジウィック)などの本に掲載されている。
*'''全最近傍問題''' ({{lang-en-short|all nearest neighbors, ANN}}) とは、点集合の中から各点の最も距離の近い点を探すアルゴリズムであり、近傍点1つを探すならば <math>O(n \log n)</math> 、近傍点m個を探す問題ならば <math>O(m n \log n)</math> で求まる<ref name=Vaidya>{{Cite journal |doi=10.1007/BF02187718 |last1=Vaidya | first1=P. M. |year=1989 |title=An ''O''(''n''&nbsp;log&nbsp;''n'') Algorithm for the All-Nearest-Neighbors Problem  |journal=Discrete and Computational Geometry |volume=4 |issue=1 |pages=101–115 |url=http://www.springerlink.com/content/p4mk2608787r7281/?p=09da9252d36e4a1b8396833710ef08cc&pi=8 |postscript=. }}</ref>。

== 応用 ==
最近傍探索は、以下のような様々な分野で使われている。
*[[パターン認識]] - 特に[[光学文字認識]]
*[[統計分類]]- [[K近傍法]]参照
*[[コンピュータビジョン]]
*[[データベース]] - 例えば、内容に基づく画像検索（[[CBIR]]）など
*[[符号理論]] - [[復号手法|最尤復号]]参照
*[[データ圧縮]] - [[MPEG-2]]参照
*[[レコメンデーションシステム]]
*[[インターネットマーケティング]] - [[コンテンツ連動広告]]、[[行動ターゲティング]]
*[[DNAシークエンシング]]
*[[スペルチェッカ]]
*[[盗用検出]]

== 脚注 ==
{{脚注ヘルプ}}
{{Reflist}}

== 参考文献 ==
* 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

== 関連項目 ==
*[[k近傍法]]
*[[ボロノイ図]]

== 外部リンク ==
*[http://simsearch.yury.name Nearest Neighbors and Similarity Search] - 最近傍探索を中心としたウェブサイト
*[http://sisap.org/?f=library Metric Spaces Library] - 距離空間インデクシングのための[[C言語]]ライブラリ（オープンソース）
*[http://www.cs.umd.edu/~mount/ANN/ ANN] - 近似最近傍探索のためのライブラリ
*[http://www.compgeom.com/~stann/ STANN] - スレッドセーフな近似最近傍探索ライブラリ（[[C++]]）
*[http://lsd.fi.muni.cz/trac/messif MESSIF] - 距離類似探索実装フレームワーク（Metric Similarity Search Implementation Framework）

{{DEFAULTSORT:さいきんほうたんさく}}
[[Category:検索]]
[[Category:近似アルゴリズム]]
[[Category:検索アルゴリズム]]
[[Category:最適化]]
[[Category:最適化アルゴリズム]]
[[Category:画像処理]]
[[Category:分類アルゴリズム]]
[[Category:数値解析]]
[[Category:数学に関する記事]]