TagGridのデータ配置アルゴリズムの簡単な解説

はじめに

TagGridでは16000毎のFlickrの写真を、写真のタグにしたがって格子状に配置しています。この配置アルゴリズムについて簡単に説明したいと思います。

基本的なアイデア

まず、入力となるのはN個のタグ付きデータとします。また、K種類のタグがあるとします。 TagGridでは、このN個のデータとK種類のタグがそれぞれ平面上に配置されるとします。 データだけでなく、タグも2次元平面上に配置するのが大事な点です。

基本的な考え方としては、あるデータのタグが例えばseaとsunの場合、このデータの位置がseaタグと sunタグの近くになるようにデータとタグを配置します。データは複数のタグを持つので、一番良い配置方法というのは簡単には決定できません。そこで、なるだけ良さそうな配置を求めてみます。

フォーマルな問題定義

基本的なアイデアを、もう少しフォーマルに定義します。 n番目のデータの平面上の位置を 、 k番目のタグの平面上の位置を とします。 この時、n番目のデータとq番目のタグ間の距離を とすると、この距離は次のようになります。



例えば、あるデータのタグが3個あった場合、このデータと3個のタグとの間の距離の合計が小さくなればよいわけです。ただし、データによってはタグが10個もあったりするので、各データの重みを等しくするため、タグの個数でこの距離の合計を割ることにします。

つまり、n番目のデータのタグを とした場合(T(n)はタグの個数)、次の値がなるだけ小さくなるようにします。



最終的に小さくしたい値はnについて総和をとった次の値になります。



後は、このL(このような値を目的関数値と呼びます。)が最小になるように、データとタグを配置します。
この時、TagGridではデータを格子上に配置したいので、データの位置は整数値のみをとるようにします。

最適化アルゴリズム

上で定義した問題は離散最適化問題と呼ばれ、このような問題を解くアルゴリズムは色々とあるのですが、現在のところ一番シンプルな貪欲法を用いています。詳しく知りたい方は組合せ最適化 - Wikipediaなどを参照すると良いと思います。

貪欲法による解法を簡単に説明します。

1. まず、ランダムにタグとデータを配置します。
2. その後、タグとデータの位置を順番に更新していきます。タグの位置を更新するときには、データの位置を固定して、タグの位置が一番良くなるように、タグを配置します。最適なタグの位置は、そのタグを持っているデータのちょうど重心になります。
3. タグの再配置の後、データの位置を更新します。この時は、あるデータと別のデータの位置を交換した場合の目的関数値を計算して、目的関数値が交換する前よりも良くなるならば、データの位置を交換します。この交換するか否かの判定処理を全てのデータの組み合わせにたいして行います。

以下、このタグの再配置とデータの再配置を適当な回数繰り返します。つまり、次のような処理の流れになります。

ランダムな初期配置 → タグの再配置 → データの再配置 → タグの再配置 → データの再配 → ・・・ → 計算終了

データの再配置にの計算量が必要となるので、データ数が16000ですと数時間程度の計算が必要でした。ただ、アルゴリズムも実装も効率化の余地はかなりあるので、頑張れば数分程度までは短縮できそうです。

まとめ

TagGridのデータ配置アルゴリズムについて簡単な説明しました。アルゴリズムの実装については少しまとめてから公開したいと思っています。なお、このようなアルゴリズムの実装はスクリプト言語には向かないので、コアはC++で実装して、Rubyのラッパー経由で利用する形で実装しています。