類似度マッチングの基礎

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

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

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

近似類似度マッチング

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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