データ抽象化に対する既存のアプローチ
データの抽象化、たとえば集まったものや関連の強いものを一つにして抽象化したい、という場合、クラスタリングを使えばできそうに見えます。クラスタリングは、データをいくつかのまとまりにあるグループ（クラスタ）に分ける、あるいは小さなまとまりをたくさん見つけるデータ処理です。データ解析の中でもとても基礎的な技術で昔から多くの方法が研究されてきています。データを大まかに分割するのはうまくいくこおが多いのですが、データ粒子化のように、まとまりある細かい構造を見つけたい場合にはあまりうまくいかないことが多いのです。以下で、著名な方法がなぜうまくいかないのか、見てみましょう。
昔からあるクラスタリングの方法に、階層化クラスタリングというものがあります。データ全体を２つ、あるいは複数に分け、それぞれをまた複数に分け、というように繰り返し細かくしていき、これ以上分かれないだろうな、と思われるところでストップするというものです。この方法、生物の分類のように、背後に明らかな階層構造があって、海に住む生物と陸に住む生物、あるいは細菌と昆虫など、明らかに種別間の異なりがわかるような場合にはうまくいきます。しかし、人の顔の違いや趣味の傾向など、明確な大分類がないものではうまくいきません。「大きめで柔道をやってそうな顔」「小柄で目が小さくて内気な感じのする顔」など、いろいろなタイプの顔があると思いますが、最初に「髪の毛の色」や「めがねをかけているか」などでざっくり分類してしまうと、このタイプの人たちは分断されてしまいます。分類を繰り返すたびに分断されるグループは増え、最後には分断されたグループのかけらからなる小さなグループができてしまい、まとまりのないものになってしまいます。趣味や顔つきなどは、ぼんやりとした、あまり明確でない分かれかたをするため、明確な分類をしようとすると失敗してしまうのです。
有名なクラスタリング手法の一つに k-means があります。means は真ん中という意味で、真ん中を k 個見つけてデータを k 個に分割する方法です。図を見ながら読んでください。最初にデータの中に適当な真ん中を k 個選びます(シードと呼びます)。次にデータの各項目に対して、選んだ k個シードの中でどれが一番近いか計算し、一番近いシードのグループに入れます。そうすると、データはk個のグループに分かれます。次に、分かれた各グループのシードを、グループに入っている項目の真ん中（項目の平均などで計算）に移動します。この操作を動きがなくなるまで繰り返して得られたグループをクラスタとして出力します。これが k-means のやり方です。真ん中があって、それに近いものが集まってグループを形成して、とうまくデータが分割できるように思えます。しかし、最初にシードを上手に選べないと、図のようにおかしな分割からスタートすることになります。この場合、青が右下に移動して落ち着きそうに見えますが、 図のようにたくさんのクラスタがあると、多くのクラスタを含むもの、一つのクラスタをわけたもの、に落ち着いてしまいます。k-meansは、シードの最初の位置が各クラスタにある程度近い位置にないとうまく動かないのですが、クラスタがたくさんあるデータでは、そのような初期配置を求めることがそもそもクラスタリングをしていることと同じなわけで、本末転倒です。適当に初期位置を決めると、ばらばらに、あるいはまざりあったクラスタばかりが出来てしまいます。
同じような難しさは、グラフカットによるクラスタリングでも起こります。グラフカットは、グループ間のリンクがなるべく少なくなるようにネットワークの頂点（節点）をグループ分けをするものです。データの各項目を節点として、似ている、近い、あるいは関連のある節点同士をリンク（枝）で結んであげると、ネットワーク（グラフ）ができます(例：図neighborgraph)。もとのデータのクラスタは、ある程度似たものが集まっているはずなので、作ったネットワークの中で、クラスタの節点はお互い密に連結され、外部とはあまりつながっていないはずです。そこで、お互いリンクが密に張られている節点の集まりや、外部とあまりリンクが張られていない節点の集まりを見つけることで、クラスタを見つけるのです(図graphcuut)。グラフカットも、まず最初に適当に節点を分割し、グループ間をまたぐリンク数が減るようにグループを組み替えていきます。やはり、最初の分割がある程度正確でないといくらグループの組み替えをしても、たくさんのクラスタが集まった大きなグループと、クラスタを分割した小さなグループができてしまいます。
このようにネットワークを作ってからクラスタリングする方法として、モジュラリティを大きくするようにグループ分けするものがあります。モジュラリティとは、ネットワークのクラスタの良さをはかる指標で、クラスタの中のリンク密度を、クラスタとクラスタの外部を結ぶリンクの密度で割ったものです。クラスタ内部が多くのリンクで結ばれていれば結ばれているほど、外部との結ばれていなければいないほど、モジュラリティは大きくなります。すべてのクラスタのモジュラリティの平均をとれば、どれほど上手にわけられているかがわかります。この平均が大きくなるよう、グループを組み替え混ぜ合わせます。最終的には良いクラスタが得られるはずです。
ただ、モジュラリティにも欠点があります。それは大きさを考慮していないこと。実は、モジュラリティは、ネットワークをリンク一つずつに分割すると、とても値が大きくなります(内部の枝密度が100%になるので)。値は良いのですが、このような分割はとても良いクラスタとはいえないでしょう。そこで、通常は大きさに対してご褒美を用意します。つまり各クラスタの良さを、モジュラリティ＋クラスタサイズ、で評価するのです。これで、大きなクラスタが生成されるようになります。しかし、なかなかうまくいかないもので、今度は少しでも大きなクラスタができると、そのクラスタに他のクラスタを付け足して大きくすると効率よく得できるようになるので、小さいクラスタがたくさん集まった大きなクラスタを作ってしまいます。その結果、巨大クラスタが複数と、大量の小さい、2個か3個の項目からなるクラスタが作られてしまいます(図newman)。
ネットワークには、ビリーフプロパゲーションやページランキングと言った、ランダムウォークに基づいたクラスタ発見方法もあります。出発点を決め、そこからリンクをたどっていく。複数のリンクがあるときには、どれも同じ確率で選ぶようにします(図randomwalk)。こうしてたどっていったときに、それぞれの節点にいる確率を計算してみます。もし節点がクラスタに入っているなら、その中は密に結ばれているはず、つまりその中をぐるぐる移動する確率が高くなるはずで、つまりは出発点と同じクラスタに属する節点にたどり着く確率が高くなるはずです。到着確率が高い節点だけを集めれば、出発点を含むクラスタが見つかるだろう、というものです。
この方法もいくつか弱点があります。まずは計算コストが大きいこと。すべての節点を出発点にして計算すると、ばくだいな時間がかかります。また、出発点のそばに大きなクラスタがあると、大きなクラスタの中にいったん入ってそこをぐるぐる回る確率が高くなり、結果として出発点はそのクラスタに入っていると判定されてしまいます。つまり、大きいクラスタは不必要に周りの頂点を含んでしまい、もっと大きくなり、本来その出発点を含んでいる小さいクラスタは見つからない、ということになります。また、計算時間を短縮するため、確率を厳密に計算せず、実際にサイコロ振ってランダムに動き回ってしらべる、という方法もあるのですが、これだと毎回計算結果が変わり、似たような、しかし異なるクラスタがたくさん出てきてしまい、どれを残してどれを捨てればいいのかわからなくなります。
クラスタ一つ一つを正確に求めるのではなく、クラスタの芯となる部分だけを見つけ、それを膨らませることでクラスタを求めよう、という方法もあります。コミュニティマイニング、パターンマイニングなどとよばれるものです。理想的には、ネットワークの中で、クラスタのすべての節点は結ばれていてほしいものです（図manycliquesの左の赤い部分のように、すべての節点が結ばれているものをクリークと言います）。クラスタは、互いに似ているもの、互いに関連あるもののあつまりなので、本来こうなるべきです。しかし、現実のデータはノイズやエラーがありなかなかこうはなりません。しかし、クラスタの一部には、理想的になっているところがあるでしょう。 そのようなクリークが理想的な部分がクラスタの芯だと考えて、それを全部見つけてしまおうというものです。
この方法、良さそうですが、やはり弱点があります。一つのクラスタが大量の芯を含むことがあり、それを全部見つけてしまうと大変なことになるというところです。たとえば50人のグループがあって、2人ずつのペアを作っているとしましょう。すべての人同士がリンクされているのですが、各ペアだけは結ばれていないとします。すると、各ペアから一人ずつ選んで作るグループは、これ以上大きくできないクリークになります。つまり、2の25乗、3200万のクリークがあり、これが全部解として出てきてしまうわけです。似たものがたくさん出てきて困るので、代表的なものだけ残しましょう、となると、これはクラスタリングと似た問題になってしまいます。適当に捨ててしまっては、ほんとは小さなクラスタの芯であったものが、似た大きなクラスタの芯だと勘違いされ、捨てられてしまうかもしれません。部分的なものを見つけようとすると、必ずと言っていいほど、この問題に突き当たってしまいます。
まとめると、たくさんの小さなクラスタを見つけるクラスタリングには、いろいろな難しさがあり、今ある方法はあまりうまくいってないものが多いです。
- 部分的にはっきりしたものを見つけようとすると、大量に解が見つかる
- クラスタの評価値を良くしようとすると、一つがよくなりすぎて偏る
- そもそも、クラスタの良さを数理を使って上手に表すのが難しい
これらを解決するために、このプロジェクトで開発したのが、次に解説するデータ研磨です。