TagGridのデータ配置アルゴリズムの簡単な解説
基本的なアイデア
まず、入力となるのはN個のタグ付きデータとします。また、K種類のタグがあるとします。 TagGridでは、このN個のデータとK種類のタグがそれぞれ平面上に配置されるとします。 データだけでなく、タグも2次元平面上に配置するのが大事な点です。
基本的な考え方としては、あるデータのタグが例えばseaとsunの場合、このデータの位置がseaタグと sunタグの近くになるようにデータとタグを配置します。データは複数のタグを持つので、一番良い配置方法というのは簡単には決定できません。そこで、なるだけ良さそうな配置を求めてみます。
フォーマルな問題定義
基本的なアイデアを、もう少しフォーマルに定義します。 n番目のデータの平面上の位置を 、 k番目のタグの平面上の位置を
とします。 この時、n番目のデータとq番目のタグ間の距離を
とすると、この距離は次のようになります。
例えば、あるデータのタグが3個あった場合、このデータと3個のタグとの間の距離の合計が小さくなればよいわけです。ただし、データによってはタグが10個もあったりするので、各データの重みを等しくするため、タグの個数でこの距離の合計を割ることにします。
つまり、n番目のデータのタグを とした場合(T(n)はタグの個数)、次の値がなるだけ小さくなるようにします。
最終的に小さくしたい値はnについて総和をとった次の値になります。
後は、このL(このような値を目的関数値と呼びます。)が最小になるように、データとタグを配置します。
この時、TagGridではデータを格子上に配置したいので、データの位置は整数値のみをとるようにします。
最適化アルゴリズム
上で定義した問題は離散最適化問題と呼ばれ、このような問題を解くアルゴリズムは色々とあるのですが、現在のところ一番シンプルな貪欲法を用いています。詳しく知りたい方は組合せ最適化 - Wikipediaなどを参照すると良いと思います。
貪欲法による解法を簡単に説明します。
- まず、ランダムにタグとデータを配置します。
- その後、タグとデータの位置を順番に更新していきます。タグの位置を更新するときには、データの位置を固定して、タグの位置が一番良くなるように、タグを配置します。最適なタグの位置は、そのタグを持っているデータのちょうど重心になります。
- タグの再配置の後、データの位置を更新します。この時は、あるデータと別のデータの位置を交換した場合の目的関数値を計算して、目的関数値が交換する前よりも良くなるならば、データの位置を交換します。この交換するか否かの判定処理を全てのデータの組み合わせにたいして行います。
以下、このタグの再配置とデータの再配置を適当な回数繰り返します。つまり、次のような処理の流れになります。
ランダムな初期配置 → タグの再配置 → データの再配置 → タグの再配置 → データの再配 → ・・・ → 計算終了
データの再配置にの計算量が必要となるので、データ数が16000ですと数時間程度の計算が必要でした。ただ、アルゴリズムも実装も効率化の余地はかなりあるので、頑張れば数分程度までは短縮できそうです。
