画像検索システムやウェブサイト分析など、
あらゆる場面で、データごとの類似度を測定する手法が必要になります。
しかし、検索する対象が多いと、検索に時間がかかってしまうなど、
意外とその問題を解くのは難しいです。
今回は、そんな類似度マッチングの基礎をまとめていきます。
近似類似度マッチング
ユーザーのあるデータと似た情報を検索できるようにするためには、
事前に他のデータを検索しやすい形にし、それを最近傍探索用に整理し、格納する必要があります。
つまり、インデックスを作ります。
しかし最近傍を求めようとすると、計算コストが大きくなります。
そこで、リアルタイムで検索、取得、提供するには類似度マッチングが必要で、
近似最近傍アルゴリズムを使用してインデックスを作成し、
類似データの探索プロセスを高速化するのが実用的です。
2種類の近傍類似度マッチングアルゴリズム
近似最近傍アルゴリズムには、大きく2種類の方法があります。
ツリーベースの方法
1つは、ツリーベースの手法です。
これは、インデックスの作成時に、探索用のツリーを作成します。
これにより、検索時に高速に探索を行うことができます。
ただしツリーの作成は、大量のメモリを必要とするため、
データの次元数が多くなると、パフォーマンスが低下します。
代表的なアルゴリズムは、以下の通りです。
- KD-Tree
- バンテージ ポイントツリー
- （ランダム）プロジェクション ツリー
- ボールツリー
ハッシングベースの方法
2つ目は、ハッシュを用いる方法です。
その名の通り、各データをハッシュ化し、ハッシュ値を用いて検索を行います。
この方法では、必要なメモリが大幅に少なくなります。
一方で、検索時はなんの工夫もしなければ、
データ量に対して検索時間が線形で増加します。
代表的なアルゴリズムは、以下の通りです。
- 局所性鋭敏型ハッシュ（LSH）
- PCA ハッシュ
- 最小ハッシュ
- スペクトル ハッシュ
ベンチマークデータ
ここまで、いろいろなアルゴリズムを紹介しましたが、
「結局どれがいいの？」という疑問がありますね。
アプリケーションによって、その正解は変わりますが、
一つの指標として、ベンチマークが公開されています。
ここでは、近似類似度マッチングを実装するオープンソースライブラリのほぼ全てを比較してくれています。
性能だけではなく、メモリ使用量なども比較しているので、
自分の用途にあったものを選ぶことができます。
まとめ
いかがだったでしょうか？
今回は、類似度マッチングに関して、網羅的にまとめてくれているサイトが見つからなかったので、
自分でまとめてみました。
ちなみに、僕はYahoo!JAPANが開発したNGTというライブラリを利用した経験があります。
性能も高いし、比較的使いやすいインターフェースなのでおすすめです。
