類似度マッチングの基礎

アルゴリズム

画像検索システムやウェブサイト分析など、
あらゆる場面で、データごとの類似度を測定する手法が必要になります。

しかし、検索する対象が多いと、検索に時間がかかってしまうなど、
意外とその問題を解くのは難しいです。

今回は、そんな類似度マッチングの基礎をまとめていきます。

近似類似度マッチング

ユーザーのあるデータと似た情報を検索できるようにするためには、
事前に他のデータを検索しやすい形にし、それを最近傍探索用に整理し、格納する必要があります。
つまり、インデックスを作ります。

しかし近傍を求めようとすると、計算コストが大きくなります。
そこで、リアルタイムで検索、取得、提供するには類似度マッチングが必要で、
近似最近傍アルゴリズムを使用してインデックスを作成し、
類似データの探索プロセスを高速化するのが実用的です。

2種類の近傍類似度マッチングアルゴリズム

近似最近傍アルゴリズムには、大きく2種類の方法があります。

ツリーベースの方法

1つは、ツリーベースの手法です。

これは、インデックスの作成時に、探索用のツリーを作成します。
これにより、検索時に高速に探索を行うことができます。

ただしツリーの作成は、大量のメモリを必要とするため、
データの次元数が多くなると、パフォーマンスが低下します。

代表的なアルゴリズムは、以下の通りです。

  • KD-Tree
  • バンテージ ポイントツリー
  • (ランダム)プロジェクション ツリー
  • ボールツリー

ハッシングベースの方法

2つ目は、ハッシュを用いる方法です。

その名の通り、各データをハッシュ化し、ハッシュ値を用いて検索を行います。

この方法では、必要なメモリが大幅に少なくなります。
一方で、検索時はなんの工夫もしなければ、
データ量に対して検索時間が線形で増加します。

代表的なアルゴリズムは、以下の通りです。

  • 局所性鋭敏型ハッシュ(LSH)
  • PCA ハッシュ
  • 最小ハッシュ
  • スペクトル ハッシュ

ベンチマークデータ

ここまで、いろいろなアルゴリズムを紹介しましたが、
「結局どれがいいの?」という疑問がありますね。

アプリケーションによって、その正解は変わりますが、
一つの指標として、ベンチマークが公開されています。

ANN-Benchmarks

ここでは、近似類似度マッチングを実装するオープンソースライブラリのほぼ全てを比較してくれています。
性能だけではなく、メモリ使用量なども比較しているので、
自分の用途にあったものを選ぶことができます。

まとめ

いかがだったでしょうか?

今回は、類似度マッチングに関して、網羅的にまとめてくれているサイトが見つからなかったので、
自分でまとめてみました。

ちなみに、僕はYahoo!JAPANが開発したNGTというライブラリを利用した経験があります。
性能も高いし、比較的使いやすいインターフェースなのでおすすめです。

コメント

タイトルとURLをコピーしました