データマイニングしてみた - 当面C#と.NETな記録

数日前、オレンジニュースで「2008年度人工知能学会の発表資料「頻出パターン発見アルゴリズム入門 −アイテム集合からグラフまで−」(PDF)が紹介されてました。データマイニングに興味があったので読んでみると、タイトルどおりのわかりやすい入門記事だったのでコードを書いて遊んでみました。
3000件ちょいのデータを使って頻出集合を求めてみたところ、はじめは5分もかかってげんなりしたけど、入門記事の高速化の方法をいくつか試していくと3分40秒になり、あるところで突然1秒を切り、現在は0.1秒程度にまで速くなりました！これは楽しすぎ！プログラマにとって中毒性ありですｗ

頻出集合

データマイニングは紙おむつを買った人はビールも一緒に買う人が多いという神話でおなじみのあれ。頻出集合とはデータマイニングの基本で、例えば一人一人の買った物のデータからある回数以上一緒に買われたものの集合のことです。{1,2,3,4}, {1,2,4}, {1,3,4}, {2,3,4}のデータがあるとき、3つ以上に含まれるアイテム集合は{1},{2},{3},{4},{1,4},{2,4},{3,4}となります。閾値を3として3回以上出てくる組み合わせを見つけたわけです。入門記事はこのアルゴリズムの初心者向け解説です。処理の中心は何度も何度も比較する部分で、そこをアルゴリズムの工夫によって劇的に比較回数を減らすことができ、実に面白いです。ループのループのループの…中の処理を改善するので、効果が半端なく大きく波及します。

以下、これまでやったことのリポート。
はじめに、扱うデータが集合ではなく多重集合、つまり{1,2,2,3}みたいにアイテムが重複しているものだったので、記事の「6.1 マルチセットの発見」に従って重複アイテムの番号を振り直しました。アイテムには一意のID番号が振ってあったので、今回はそれを利用。なければ番号を振るなり、一意のハッシュ値を使うなりすればOK。
入門記事ではデータのレコードをトランザクションと呼んでいるのがどうも違和感を感じます。トランザクションというと一連の処理のイメージを持っているので、レコードと呼ぶほうが好みです。まあ、こまけぇことはいいんだよ！！ｗ

次に頻出集合を求める主なアルゴリズムが2つ、アプリオリ法とバックトラック法が載ってます。データベースがメモリに入る場合はバックトラック法が速いそうなのでこちらを選択。再帰により、ある道を試して行き止まりになったら戻ってまた別の道を試すという定番の探索法。入門記事のバックトラック法の図5が欠けているようですが、図4を読み替えることができたりします。アルゴリズムが載っているので実装はすぐできましたが、実行してみると計算に5分もかかりました…。

次は高速化。まずはデータベース縮約を追加。前処理で多重集合を集合に変換していたので、そのついでに縮約。この時点で実行時間は3分40秒程度。次に、ダウンプロジェクトなんだか振り分けなんだか条件付データベースなんだかよくわかりませんが、そのような再帰のたびに探索範囲を絞り込む処理を入れたところ、突然1秒を切るまでに高速化！毎回3000件程度のレコードの比較をしていたのが、絞り込むたびに探索範囲が小さくなるので木の葉のほうに行くほど比較回数が減ります。バックトラックは葉のほうへ末広がりな木の形になり、深いレベルでの計算時間が全体の大部分を占めるので、深い部分の計算量を減らすと計算時間の劇的な改善につながると入門記事にもあります。3分40秒が突然1秒未満になったときは、何が起きたかわけがわからず、プチフリーズしましたｗ
ダウンプロジェクト、振り分け、条件付データベース、再帰的データベース縮約はいずれも似たようなことの微妙な違いだと思いますが、違いがよくわかりません。自分が書いたものがどれなのかわかりませんｗいずれにせよ、すばらしい効果がありました。この後、さらに全体のコードを精査しているうちに無駄をいくつか見つけ、ついに0.1秒程度の実行時間になりました。また、2つの集合の部分集合判定処理が、はじめはそれぞれのほとんどの値を比較していたのが、絞込みにより、一方の集合に一つの値があるか探すだけにまで効率化できました。二重の効率化効果があったわけです。

ここまでの実行時間はすべて最小サポートが5のときの時間です。最小サポートとは頻度の閾値のこと。最小サポートが2の場合でも、現在は0.15秒程度。閾値が小さいと見つけ出すものが増え、時間がかかります。

ちなみに、見つかった頻出集合が本当に正しいものか検証するのはものすごく大変です…。別の実装を用意して結果を突き合わせるのが現実的か。

飽和集合

頻出集合を求めてすぐに気づいたことが一つ。{1,2,3}が10件見つかったときに、{1,2}が10件、{1,3}が10件という結果も同時に見つかったりします。後ろ2つは余計で、{1,2,3}が10件という結果だけが欲しい。このとき、{2,3}が20件あるというのならそれは別のレコードも含むので必要な情報です。
この{1,2,3}を飽和集合とよびます。最初の入門記事と同じ、宇野先生と有村先生によるこの論文(PDF)やこの論文(PDF)に定義があります。最初の入門記事にも飽和集合の言葉が出てきますが、定義が書いてないのでちょっとイラっときますｗ

というわけで、ここからは、目標が頻出集合を求めることから、頻出飽和集合を求めることに変わります。

頻出飽和集合の求め方は宇野先生と有村先生による LCM という実装があり、高速なようですが、論文をいくつか読んでもよくわかりません(^^; スミマセン、オバカで…

なのでより単純で遅い方法ですが、頻出集合をすべて求めて、その中から飽和集合だけを見つける方法をとりました。はじめの実装は頻度ごとの Lookup (LINQ とともに導入された新しいデータ構造で、Dictionary の Value がコレクションになっているもの。ただし、追加削除変更はできない)を作り、各頻度ごとに一つ集合を取り出して他の集合と一つ一つ比較する単純なもの。集合が他の集合の上位集合であれば、部分集合である小さい集合のほうを消していきます。{1,2,3}が10件、{1,2}が10件、{1,3}が10件という頻出集合のデータがあれば、後ろの2件を消します。最小サポートが5のときは、この単純な実装でも0.3秒程度で終わりますが、最小サポートが3になると頻出集合が増えるので2秒程度の時間がかかり、最小サポート2になると3分もかかります…。

よく考えてみると、頻出集合から飽和集合を見つける問題も、頻出集合を見つける問題とそっくりです。そうとわかれば枝に分配するデータを絞り込めば高速化できそうというわけで実装してみたところ、この問題も劇的に高速化できました。頻度でわけたデータをさらに含んでいるアイテムごとにわけて比較したところ、3分かかっていた最小サポート2の場合の実行時間が0.8秒にまで縮みました！前処理、頻出集合探索、頻出飽和集合探索の合計で約1.2秒です。まあなんということでしょう、のんびりネット徘徊できるほど時間がかかっていたのに(^^;、実用的なスピードになってきました。

感想と今後

実は最初は PLINQ や TPL を試してみるのにちょうどいいネタかなと思ってはじめたのに、アルゴリズムの力を思い知ることになりました。5分が0.1秒に縮んだり、3分が0.8秒に縮むのを体感できたのが最高！珠玉のプログラミングみたい。
LINQ に Lookup に HashSet (これも LINQ と同時期に導入された集合を扱うクラス。集合演算が用意されているので、部分集合を求めたりするのが配列を使うより楽) が大活躍してくれたので、コードが単純で短いのも楽で◎。

今後はさらに論文を理解したいところです。閉包がわかりません…。論文を読みつつ、手を動かしているうちに理解できるといいかな。