Hatena::ブログ(Diary)

当面C#と.NETな記録 このページをアンテナに追加 RSSフィード

2009/6/26 (金)

[] 頻出飽和集合とかのメモ2  頻出飽和集合とかのメモ2を含むブックマーク  頻出飽和集合とかのメモ2のブックマークコメント

2つやったことの記録。ビットマップ化と振り分け処理の改良失敗。

振り分け処理の改造は、ハッシュ(Dictionary)を使っているところを、マージ(マージソートのマージ。併合)にしてみたけど遅くなった。もう少し改造してみるけど早くなりそうな気はしない…。

ビットマップ化は、アイテムが疎なら遅くなるって最初の入門PDFにも書いてあるけど、ビット黒魔術で遊びたかった。そして、遅くなっただけだったw

ビットマップ化はグラフの隣接行列表現

グラフ理論のグラフを表現する方法として、主に隣接行列と隣接リストの2つがある。隣接行列は頂点と頂点の間に辺があれば1、なければ0とした行列で表現する方法。メモリの都合上、密なグラフでは隣接行列がよく、疎なグラフでは隣接リストがよい。

レコード(トランザクション)とアイテムを頂点とした2部グラフ(前回のメモ参照)と考えたときに、それをあらわす隣接行列がビットマップ。

A {1,2,3,4}
B {1,2,3,5}
C {1,2,3,6}

とあれば、アイテムを各ビット位置であらわし、1 => 00 0001, 2 => 00 0010, ... ,6 => 10 0000とすると

  | 654321
A | 001111
B | 010111
C | 100111

となる。列が654321のアイテムで、行がABCのレコードの行列になる。64個以下のアイテムしかなければ、1レコードが64bitで表現できる。あとはANDを取るだけで共通アイテムが求められる。

ちなみに、ビットマップ化してないときは配列でレコードを持ち、さらにレコードの配列でデータベース全体を表現している。ごくごく普通。リンクリストを使って隣接リスト表現してたりはしません。

アイテムの種類が多く、グラフが疎なときには、隣接行列が大きくなってしまう。1000種類のアイテムがあれば、1レコード1000bitになって、配列でレコードを持つよりデカイかもしれない。なので、アイテムが64個以下のときだけビットマップ化して計算するようにしてみたけど、ビットマップ化してはすぐビットマップでの計算が終わり、またビットマップ化しては(以下ry の繰り返しで、むしろ遅くなりましたとさ。ビットマップ化する際の条件を厳しくしても遅いまま。密なデータなら効果的らしい。

頻出集合を求めるのも、頻出飽和集合を求めるのも、上のABCのレコードの行列を縦に見て横に見てってことの繰り返し。

MJが亡くなったと聞いてここで書く気が失せたので、またいずれ。

トラックバック - http://d.hatena.ne.jp/siokoshou/20090626

2009/6/18 (木)

[] 頻出飽和集合とかのメモ   頻出飽和集合とかのメモを含むブックマーク   頻出飽和集合とかのメモのブックマークコメント

前回のデータマイニングの続き。ちゃんと書きたいけど、まだよくわかってないので今はちょっとだけメモ。

宇野先生の研究業績のページで頻出集合や頻出飽和集合関連のわかりやすい資料を見つけた。超大作パワポ「いいプログラムはコーディング技術だけではない」。中身とタイトルはあまりあってないですw 言いたいことはわかるけど・・・

前回冒頭に挙げた頻出集合アルゴリズムの入門PDFあわせて読みたい

あの後、LCM のコードはほとんどみてないけど(論文を読んでまねしてコードを書く部分を楽しんでるのと、ぱっと見てわかんなかったから)、頻出飽和集合が一発で求められるようになりました。後処理で削除してた部分がいらなくなり、前回1.2秒と言ってた処理が今や0.3秒で終わります。前処理も除けば0.15秒ほど。LCM と答えあわせをしてみると、答えの件数が一致するのであってるっぽい。

とりあえず、宇野先生の飽和集合関連のいくつかの論文に出てくる極大2部クリークって何さ?ってところをまとめた。

http://docs.google.com/Presentation?id=dqf99wm_1632cn22mpd7

極大2部クリークよりも頻出飽和集合のほうが具体的なんで、わかりやすい。

2部グラフって小学生のテストとかに出てくる「線で結びなさい」ってやつを思い浮かべるといいかもw

トラックバック - http://d.hatena.ne.jp/siokoshou/20090618

2009/6/3 (水)

[] LINQで頻度を求める  LINQで頻度を求めるを含むブックマーク  LINQで頻度を求めるのブックマークコメント

昨日の関連の話題。コード成分が足りなかったので補給に。

Dictionary<T> を使って頻度を求めるのは定番中の定番の使い方だと思います。たとえば、"the quick brown fox jumps over the lazy dog" の文字列の中で、a が何回使われてて、b が何回使われているかっていう数え上げ処理のこと。頻繁に使うってほどでもないけど、これまで、何回も何回も何回も書きましたw

昔、Perl をよく使ったのはこれがやりたかったからでした。Perl に慣れてからは正規表現のほうが Perl の重要な機能になったけど、それまではハッシュが使いたくて Perl してました。まだ C# もないころで、ハッシュをスマートに使える言語をほかに知らなかったから。

これを LINQ にしてみた。

まずは LINQ なしで。多少違いはあってもだいたいこんなコードになるはず。

static Dictionary<T, int> ToFrequency<T>( this IEnumerable<T> source )
{
    var dic = new Dictionary<T, int>();

    foreach ( var item in source )
    {
        if ( dic.ContainsKey( item ) )
        {
            dic[ item ]++;
        }
        else
        {
            dic[ item ] = 1;
        }
    }
    return dic;
}

一度 ContainsKey で調べる処理が入るのが無駄っぽくてイヤだ。キーがない場合の初期値を式でわたせればいいのに。

LINQ 版。

source.GroupBy( x => x ).ToDictionary( g => g.Key, g => g.Count() );

おっ?こんなに短く書けるとは。でもわかりづらいかも…?

比べてみる。

static void Main()
{
    var str = "the quick brown fox jumps over the lazy dog";

    var dic = str.ToFrequency();

    var dic2 = str.GroupBy( c => c )
        .ToDictionary( g => g.Key, g => g.Count() );

    Console.WriteLine(
      dic.OrderBy( x => x.Key )
      .SequenceEqual( dic2.OrderBy( x => x.Key ) ) );

    foreach ( var item in dic2 )
    {
                Console.WriteLine( item.Key + " : " +  item.Value );
    }
    Console.ReadKey();
}

同じ!

トラックバック - http://d.hatena.ne.jp/siokoshou/20090603

2009/6/2 (火)

[] データマイニングしてみた  データマイニングしてみたを含むブックマーク  データマイニングしてみたのブックマークコメント

数日前、オレンジニュース「2008年度人工知能学会の発表資料「頻出パターン発見アルゴリズム入門 −アイテム集合からグラフまで−」(PDF)が紹介されてました。データマイニングに興味があったので読んでみると、タイトルどおりのわかりやすい入門記事だったのでコードを書いて遊んでみました。

3000件ちょいのデータを使って頻出集合を求めてみたところ、はじめは5分もかかってげんなりしたけど、入門記事の高速化の方法をいくつか試していくと3分40秒になり、あるところで突然1秒を切り、現在は0.1秒程度にまで速くなりました!これは楽しすぎ!プログラマにとって中毒性ありですw

頻出集合

データマイニングは紙おむつを買った人はビールも一緒に買う人が多いという神話でおなじみのあれ。頻出集合とはデータマイニングの基本で、例えば一人一人の買った物のデータからある回数以上一緒に買われたものの集合のことです。{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秒未満になったときは、何が起きたかわけがわからず、プチフリーズしましたw

ダウンプロジェクト、振り分け、条件付データベース、再帰的データベース縮約はいずれも似たようなことの微妙な違いだと思いますが、違いがよくわかりません。自分が書いたものがどれなのかわかりませんw いずれにせよ、すばらしい効果がありました。この後、さらに全体のコードを精査しているうちに無駄をいくつか見つけ、ついに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)に定義があります。最初の入門記事にも飽和集合の言葉が出てきますが、定義が書いてないのでちょっとイラっときますw

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

頻出飽和集合の求め方は宇野先生と有村先生による 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 と同時期に導入された集合を扱うクラス。集合演算が用意されているので、部分集合を求めたりするのが配列を使うより楽) が大活躍してくれたので、コードが単純で短いのも楽で◎。

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

しましましましま 2009/06/04 08:58 宇野先生のアルゴリズムはここにコードがあります
http://research.nii.ac.jp/~uno/codes.htm

siokoshousiokoshou 2009/06/04 13:10 ありがとうございます!ついでに日本語版も見つけてしまいました。
http://research.nii.ac.jp/~uno/codes-j.htm

トラックバック - http://d.hatena.ne.jp/siokoshou/20090602
2005 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 11 | 12 |
2006 | 01 | 02 | 03 | 04 | 06 | 09 | 11 | 12 |
2007 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2008 | 01 | 02 | 03 | 04 | 05 | 06 | 08 | 09 | 10 | 12 |
2009 | 01 | 03 | 04 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2010 | 07 |
2011 | 04 | 07 | 10 |
2012 | 04 | 12 |
2013 | 08 |
2014 | 03 | 08 |
2017 | 09 |