最近傍探索

最近傍探索（NNS ）は、近接探索の一種であり、与えられた集合内において、与えられた点に最も近い（または最も類似する）点を見つける最適化問題です。近さは通常、非類似度関数で表されます。つまり、物体間の類似性が低いほど、関数の値は大きくなります。

正式には、最近傍探索問題（NN）は次のように定義されます。空間M内の点集合Sとクエリ点が与えられたとき、 S内でqに最も近い点を見つけます。ドナルド・クヌースは『 The Art of Computer Programming』（1973年）第3巻の中で、住宅に最も近い郵便局を割り当てる問題に当てはめて、これを郵便局問題と呼びました。この問題を直接一般化するとk -NN探索となり、 k個の最近傍点を 見つける必要があります。q∈M{\displaystyle q\in M}

最も一般的には、 Mは計量空間であり、非類似度は距離計量として表されます。距離計量は対称であり、三角不等式を満たします。さらに一般的には、Mはd次元ベクトル空間とされ、非類似度はユークリッド距離、マンハッタン距離、またはその他の距離計量を用いて測定されます。ただし、非類似度関数は任意です。一例として、非対称ブレグマンダイバージェンスが挙げられますが、この場合には三角不等式は成立しません。[ 1 ]

アプリケーション

最近傍探索問題は、次のようなさまざまな応用分野で発生します。

方法

NNS問題には様々な解決策が提案されています。アルゴリズムの品質と有用性は、クエリの時間計算量と、維持しなければならない検索データ構造の空間計算量によって決まります。「次元の呪い」と呼ばれる非公式な観察によると、高次元ユークリッド空間において、多項式前処理と多重対数的な探索時間を用いたNNSの汎用的な厳密解は存在しません。

正確な方法

NNS問題に対する最も単純な解法は、クエリ点からデータベース内の他のすべての点までの距離を計算し、「これまでの最良」の点を追跡し続けることである。このアルゴリズムは、ナイーブアプローチと呼ばれることもあり、実行時間はO ( dN )である。ここで、 NはSの基数、dはSの次元数である。維持すべき検索データ構造がないため、線形探索はデータベースのストレージ容量を超える空間計算量を持たない。ナイーブ探索は、平均して、高次元空間において空間分割アプローチよりも優れた性能を示す。[ 5 ]

距離の比較には絶対距離は不要で、相対距離のみが必要です。幾何座標系では、2つの座標間の距離計算から平方根計算を省略することで、距離計算を大幅に高速化できます。距離の比較は、依然として同じ結果となります。

空間分割

1970 年代以来、分枝限定法がこの問題に適用されてきました。ユークリッド空間の場合、このアプローチには空間インデックスまたは空間アクセス メソッドが含まれます。NNS 問題を解決するために、いくつかの空間分割法が開発されました。おそらく最も単純なのはkd ツリーで、これは検索空間を、親領域のポイントの半分を含む 2 つの領域に反復的に分割します。クエリは、各分割でクエリ ポイントを評価することにより、ルートからリーフへのツリーのトラバーサルによって実行されます。クエリで指定された距離によっては、ヒットを含む可能性のある隣接ブランチも評価する必要がある場合があります。定数次元のクエリ時間の場合、平均複雑度はO (log  N ) [ 6 ]で、ポイントがランダムに分布している場合は、最悪の場合の複雑度はO ( kN ^(1-1/ k )) [ 7 ]です。 また、R ツリーデータ構造は、R* ツリーなどの挿入と削除の効率的なアルゴリズムを備えているため、動的コンテキストでの最近傍検索をサポートするように設計されています。[ 8 ] R木はユークリッド距離だけでなく他の距離に対しても最近傍を生成することができる。

一般計量空間の場合、分枝限定法は計量木アプローチとして知られています。具体的な例としては、vp木法やBK木法などが挙げられます。

3 次元空間から取得されBSP ツリーに配置された点のセットを使用し、同じ空間から取得されたクエリ ポイントが与えられた場合、クエリ ポイントに最も近いポイント クラウド ポイントを見つける問題に対する可能な解決策を、次のアルゴリズムの説明に示します。

(厳密に言えば、そのような点は存在しない可能性があります。一意でない可能性があるためです。しかし実際には、通常、特定のクエリ ポイントまでの最短距離に存在するすべてのポイント クラウド ポイントのサブセットのいずれか 1 つを見つけることだけが重要です。) アイデアは、ツリーの分岐ごとに、クラウド内の最も近いポイントがクエリ ポイントを含む半空間に存在すると推測することです。これが当てはまらない場合もありますが、優れたヒューリスティックです。推測された半空間の問題を再帰的に解決した後、この結果によって返された距離を、クエリ ポイントから分割平面までの最短距離と比較します。後者の距離は、クエリ ポイントと、検索されていない半空間に存在する可能性のある最も近いポイントとの間の距離です。この距離が前の結果で返された距離よりも大きい場合、明らかに他の半空間を検索する必要はありません。そのような必要がある場合、もう一方の半空間について問題を解き、その結果を以前の結果と比較し、適切な結果を返すという手間をかける必要があります。このアルゴリズムのパフォーマンスは、クエリポイントがクラウドの近くにある場合、線形時間よりも対数時間に近くなります。これは、クエリポイントと最も近いポイントクラウドポイント間の距離がゼロに近づくにつれて、アルゴリズムはクエリポイントをキーとして検索するだけで正しい結果が得られるためです。

近似法

近似最近傍探索アルゴリズムは、クエリからの距離が、クエリからその最近傍点までの距離の最大倍であるような点を返すことができます。このアプローチの利点は、多くの場合、近似最近傍点が正確な最近傍点とほぼ同等の精度を持つことにあります。特に、距離の尺度がユーザーの質の概念を正確に捉えている場合、距離の小さな差は問題にならないはずです。[ 9 ]c{\displaystyle c}

近傍グラフにおける貪欲探索

近接グラフ法（ナビゲート可能なスモールワールドグラフ[ 10 ]やHNSW [ 11 ] [ 12 ]など）は、近似最近傍探索の現在の最先端技術と考えられている。

この方法は、すべてのポイントが頂点 に一意に関連付けられている近接近傍グラフの貪欲なトラバースに基づいています。セットS内のクエリqに最も近い近傍の検索は、グラフ 内の頂点の検索という形を取ります。基本的なアルゴリズムである貪欲検索は、次のように機能します。検索は、エントリポイントの頂点から開始し、クエリ q からその近傍 の各頂点までの距離を計算し、距離値が最小の頂点を見つけます。クエリと選択された頂点間の距離値が、クエリと現在の要素間の距離値よりも小さい場合、アルゴリズムは選択された頂点に移動し、その頂点が新しいエントリポイントになります。アルゴリズムは、局所的最小値、つまり近傍にその頂点自体よりもクエリに近い頂点が含まれない頂点に達すると停止します。 G（V、E）{\displaystyle G(V,E)}×私∈S{\displaystyle x_{i}\in S}v私∈V{\displaystyle v_{i}\in V}G（V、E）{\displaystyle G(V,E)}v私∈V{\displaystyle v_{i}\in V}{vj:（v私、vj）∈E}{\displaystyle \{v_{j}:(v_{i},v_{j})\in E\}}

近接近傍グラフのアイデアは、AryaとMountによる画期的な論文[ 13 ]をはじめ、平面におけるVoroNetシステム[ 14 ] 、平面におけるRayNetシステム[ 15 ]、そして距離関数を持つ空間の一般ケースにおけるNavigable Small World [ 10 ] 、 Metrized Small World [ 16 ]、そしてHNSW [ 11 ] [ 12 ]アルゴリズムなど、複数の論文で活用されています。これらの研究に先立ち、Toussaintは相対近傍グラフの概念を導入した先駆的な論文を発表しました[ 17 ] 。En{\displaystyle \mathbb {E} ^{n}}

局所性に敏感なハッシュ

局所性感知ハッシュ（LSH）は、空間内の点を、点に作用する何らかの距離指標に基づいて「バケット」にグループ化する手法です。選択された指標に基づいて互いに近い点は、高い確率で同じバケットにマッピングされます。[ 18 ]

小さな固有次元を持つ空間における最近傍探索

被覆木には、データセットの倍加定数に基づく理論的な限界があります。探索時間の限界はO ( c 12  log  n ) です。ここで、cはデータセットの 拡張定数です。

データが幾何学的点の密集した3Dマップである特殊なケースでは、センシング技術の投影幾何学を用いることで探索問題を大幅に簡素化することができる。このアプローチでは、3Dデータが2次元グリッドへの投影によって構成されている必要があり、物体の境界を除いて隣接するグリッドセル間でデータが空間的に滑らかであると仮定する。これらの仮定は、測量、ロボット工学、ステレオビジョンなどのアプリケーションで3Dセンサーデータを扱う場合には有効だが、一般には非組織化データには当てはまらない可能性がある。実際には、この技術を現実世界のステレオビジョンデータに適用した場合、 k近傍問題の平均探索時間はO ( 1 )またはO ( K )である。 [ 4 ]

ベクトル近似ファイル

高次元空間では、いずれにせよノードの割合が増加するため、木構造のインデックス構造は役に立たなくなります。線形探索を高速化するために、最初の実行では、RAMに保存された特徴ベクトルの圧縮版を用いてデータセットを事前フィルタリングします。最終候補は、ディスクから取得した非圧縮データを用いて距離計算を行い、第2段階で決定されます。[ 19 ]

VAファイルアプローチは、圧縮ベースの検索の特殊なケースであり、各特徴コンポーネントが均一かつ独立に圧縮されます。多次元空間における最適な圧縮技術はベクトル量子化（VQ）であり、クラスタリングによって実装されます。データベースはクラスタリングされ、最も「有望な」クラスターが取得されます。VAファイル、ツリーベースのインデックス、シーケンシャルスキャンと比較して、大幅なパフォーマンス向上が観測されています。[ 20 ] [ 21 ]また、クラスタリングとLSHの類似点にも注目してください。

変種

NNS 問題にはさまざまなバリエーションがありますが、最もよく知られているのはk最近傍探索とε 近似 最近傍探索の2 つです。

k近傍法

k近傍探索は、クエリの上位k近傍点を特定します。この手法は、予測分析において、近傍点のコンセンサスに基づいて点を推定または分類するためによく使用されます。k近傍グラフは、すべての点がk近傍点 と接続されたグラフです

近似最近傍

アプリケーションによっては、最近傍点の「適切な推測」を取得することが許容される場合があります。そのような場合、速度向上やメモリ節約と引き換えに、必ずしもすべてのケースで実際の最近傍点を返すことを保証しないアルゴリズムを使用できます。多くの場合、このようなアルゴリズムは大多数のケースで最近傍点を見つけますが、これはクエリ対象のデータセットに大きく依存します。

近似最近傍探索をサポートするアルゴリズムには、局所性に敏感なハッシュ法、ベストビンファースト法、バランスのとれたボックス分解木に基づく探索などがある。[ 22 ]

最近傍距離比

最近傍距離比は、元の点から挑戦者近傍点までの直線距離ではなく、前の近傍点までの距離に応じた比率に基づいて閾値を適用します。これは、CBIRにおいて、局所特徴間の類似性を用いた「例によるクエリ」によって画像を検索するために使用されます。より一般的には、いくつかのマッチング問題 に関係しています。

固定半径の近隣

固定半径近傍法は、ユークリッド空間において、指定された点から一定の距離内にあるすべての点を効率的に見つける問題です。距離は固定であると仮定しますが、クエリ点は任意です。

最も近い隣人全員

一部のアプリケーション（例えばエントロピー推定）では、 N 個のデータポイントがあり、それら N 個のポイントそれぞれについて、どのポイントが最近傍であるかを知りたい場合があります。もちろん、これは各ポイントに対して最近傍検索を1回実行することで実現できますが、より効率的な検索を行うために、これらN個のクエリ間の情報の冗長性を活用するアルゴリズムの方が改善策となります。簡単な例として、ポイントXからポイントYまでの距離を求めると、ポイントYからポイントXまでの距離もわかるため、同じ計算を2つの異なるクエリで再利用できます。

固定次元、半定正ノルム（すべてのLpノルムを含む）、およびこの空間内のn点が与えられた場合、すべての点の最近傍はO（n  log  n）時間で見つけられ、すべての点のm最近傍はO（mn  log  n）時間で見つけることができます。[ 23 ] [ 24 ]

参照

参考文献

引用

  1. ^ Cayton, Lawerence (2008). 「ブレグマンダイバージェンスのための高速最近傍探索」.第25回国際機械学習会議論文集. pp.  112– 119. doi : 10.1145/1390156.1390171 . ISBN 9781605582054. S2CID  12169321 .
  2. ^ Qiu, Deyuan, Stefan May, Andreas Nüchter.「3DレジストレーションのためのGPU高速最近傍探索」国際コンピュータビジョンシステム会議. Springer, ベルリン, ハイデルベルク, 2009.
  3. ^ Becker, Ducas, Gama, Laarhoven.「最近傍探索の新たな方向性と格子ふるい分けへの応用」第27回ACM-SIAM離散アルゴリズムシンポジウム議事録（pp. 10-24）。応用数学協会。
  4. ^ a b Bewley, A.; Upcroft, B. (2013).高密度3D点群のセグメント化における投影構造活用の利点(PDF) . オーストラリアロボット工学・オートメーション会議.
  5. ^ Weber, Roger; Schek, Hans-J.; Blott, Stephen (1998). 「高次元空間における類似性検索手法の定量分析と性能評価」(PDF) . VLDB '98 Proceedings of the 24rd International Conference on Very Large Data Bases . pp.  194– 205.
  6. ^ Andrew Moore. 「KDツリー入門チュートリアル」(PDF) 。 2016年3月3日時点のオリジナル(PDF)からアーカイブ。 2008年10月3日閲覧。
  7. ^ Lee, DT ; Wong, CK (1977). 「多次元二分探索木とバランス四分木における領域探索と部分領域探索の最悪ケース解析」. Acta Informatica . 9 (1): 23– 29. doi : 10.1007/BF00263763 . S2CID 36580055 . 
  8. ^ Roussopoulos, N.; Kelley, S.; Vincent, FDR (1995). 「最近傍クエリ」. 1995 ACM SIGMOD 国際データ管理会議 (SIGMOD '95 ) の議事録. p. 71. doi : 10.1145/223784.223794 . ISBN 0897917316。
  9. ^ Andoni, A.; Indyk, P. (2006-10-01). 「高次元における近似最近傍探索のための準最適ハッシングアルゴリズム」. 2006 第47回IEEEコンピュータサイエンス基礎シンポジウム (FOCS'06) . pp.  459– 468. CiteSeerX 10.1.1.142.3471 . doi : 10.1109/FOCS.2006.49 . ISBN  978-0-7695-2720-8。
  10. ^ a bマルコフ, ユーリ; ポノマレンコ, アレクサンダー; ログヴィノフ, アンドレイ; クリロフ, ウラジミール (2012), ナバロ, ゴンザロ; ペストフ, ウラジミール (編), 「高次元一般距離空間における近似最近傍探索問題のためのスケーラブルな分散アルゴリズム」 ,類似性探索と応用, vol. 7404, ベルリン, ハイデルベルク: シュプリンガー・ベルリン・ハイデルベルク, pp.  132– 147, doi : 10.1007/978-3-642-32153-5_10 , ISBN 978-3-642-32152-8、2024年1月16日取得{{citation}}: CS1 maint: ISBNによる作業パラメータ（リンク）
  11. ^ a bマルコフ, ユーリ; ヤシュニン, ドミトリー (2016). 「階層的ナビゲート可能スモールワールドグラフを用いた効率的かつ堅牢な近似最近傍探索」arXiv : 1603.09320 [ cs.DS ].
  12. ^ a b Malkov, Yu A.; Yashunin, DA (2020-04-01). 「階層的ナビゲート可能なスモールワールドグラフを用いた効率的かつ堅牢な近似最近傍探索」. IEEE Transactions on Pattern Analysis and Machine Intelligence . 42 (4): 824– 836. arXiv : 1603.09320 . Bibcode : 2020ITPAM..42..824M . doi : 10.1109/TPAMI.2018.2889473 . ISSN 0162-8828 . PMID 30602420 .  
  13. ^ Arya, Sunil; Mount, David (1993). 「固定次元における近似最近傍クエリ」.第4回離散アルゴリズムシンポジウム（ACM/SIGACT-SIAM）議事録, 1993年1月25～27日, テキサス州オースティン. : 271–280 .
  14. ^ Olivier, Beaumont; Kermarrec, Anne-Marie; Marchal, Loris; Rivière, Etienne (2006). 「Voro Net : Voronoi tessellations に基づくスケーラブルなオブジェクトネットワーク」(PDF) . 2007 IEEE International Parallel and Distributed Processing Symposium . Vol. RR-5833. pp.  23– 29. doi : 10.1109/IPDPS.2007.370210 . ISBN 1-4244-0909-8. S2CID  8844431 .
  15. ^ Olivier, Beaumont; Kermarrec, Anne-Marie; Rivière, Etienne (2007). 「ピアツーピア多次元オーバーレイ：複雑な構造の近似」.分散システムの原理. コンピュータサイエンス講義ノート. 第4878巻. pp.  315– 328. CiteSeerX 10.1.1.626.2980 . doi : 10.1007/978-3-540-77096-1_23 . ISBN  978-3-540-77095-4。
  16. ^マルコフ, ユーリ; ポノマレンコ, アレクサンダー; クリロフ, ウラジミール; ログヴィノフ, アンドレイ (2014). 「ナビゲート可能なスモールワールドグラフに基づく近似最近傍アルゴリズム」.情報システム. 45 : 61–68 . doi : 10.1016/j.is.2013.10.006 . S2CID 9896397 . 
  17. ^ Toussaint, Godfried (1980). 「有限平面集合の相対近傍グラフ」.パターン認識. 12 (4): 261– 268. Bibcode : 1980PatRe..12..261T . doi : 10.1016/0031-3203(80)90066-7 .
  18. ^ A. Rajaraman & J. Ullman (2010). 「大規模データセットのマイニング、第3章」。
  19. ^ Weber, Roger; Blott, Stephen. 「類似性検索のための近似値ベースのデータ構造」(PDF) . S2CID 14613657 . 2017年3月4日時点のオリジナル(PDF)からアーカイブ。 {{cite journal}}:ジャーナルを引用するには|journal=（ヘルプ）が必要です
  20. ^ Ramaswamy, Sharadh; Rose, Kenneth (2007). 「画像データベースにおける類似性検索のための適応型クラスター距離境界」ICIP .
  21. ^ Ramaswamy, Sharadh; Rose, Kenneth (2010). 「高次元インデックスのための適応型クラスター距離境界」TKDE .
  22. ^ Arya, S.; Mount, DM ; Netanyahu, NS ; Silverman, R.; Wu, A. (1998). 「近似最近傍探索のための最適アルゴリズム」(PDF) . Journal of the ACM . 45 (6): 891– 923. CiteSeerX 10.1.1.15.3125 . doi : 10.1145/293347.293348 . S2CID 8193729. 2016年3月3日時点のオリジナル(PDF)からのアーカイブ。 2009年5月29日閲覧。  
  23. ^クラークソン、ケネス・L. (1983)、「全近傍問題に対する高速アルゴリズム」、第24回IEEEシンポジウム、コンピュータサイエンスの基礎 (FOCS '83)、pp.  226– 232、doi : 10.1109/SFCS.1983.16、ISBN 978-0-8186-0508-6、S2CID  16665268。
  24. ^ Vaidya, PM (1989). 「全近傍問題に対するO ( nlogn )アルゴリズム」 .離散幾何 学 と計算幾何学. 4 (1): 101– 115. doi : 10.1007/BF02187718 .

出典

さらに読む

  • シャシャ、デニス (2004).時系列データにおける高性能発見. ベルリン: シュプリンガー. ISBN 978-0-387-00857-8。
ウィキメディア コモンズには、最近傍検索に関連するメディアがあります。
  • 最近傍法と類似性検索– NN検索に関する教育資料、ソフトウェア、文献、研究者、未解決問題、イベントを紹介するウェブサイト。Yury Lifshitsが管理。
  • 類似検索Wiki – 近傍検索に関するリンク、人物、アイデア、キーワード、論文、スライド、コード、データセットのコレクション
「 https://en.wikipedia.org/w/index.php?title=Nearest_neighbor_search&oldid=1332656761」より取得