疑似頻出アイテム集合の 多項式遅延列挙アルゴリズム

Presentation on theme: "疑似頻出アイテム集合の 多項式遅延列挙アルゴリズム"— Presentation transcript:

1 疑似頻出アイテム集合の 多項式遅延列挙アルゴリズム
宇野 毅明 （情報学研究所） 有村 博紀 （北海道大学） 2007年7月26日 人工知能学会DMSM研究会

2 頻出パターン列挙 ・ データベースの中に多く現れるパターンを全て見つける問題を 頻出パターン列挙（あるいは発見、マイニング）問題という
　データベース： トランザクション、ツリー、グラフ、多次元ベクトル 　パターン： 部分集合、木、パス・サイクル、グラフ、図形 データベース 頻出する パターンを抽出 ・ 実験1● ,実験3 ▲ ・ 実験2● ,実験4● ・ 実験2●, 実験3 ▲, 実験4● ・ 実験2▲ ,実験3 ▲ 　　　　． 実験1 実験2 実験3 実験4 　● 　▲ ATGCGCCGTA TAGCGGGTGG TTCGCGTTAG GGATATAAAT GCGCCAAATA ATAATGTATTA TTGAAGGGCG ACAGTCTCTCA ATAAGCGGCT ・ ATGCAT ・ CCCGGGTAA ・ GGCGTTA ・ ATAAGGG 　　　　． 実験結果 ゲノム情報

3 アイテム集合に対して、あいまいな包含関係を考え、
本研究では ・ いわゆる頻出集合列挙をターゲットにする 入力：　トランザクションデータベース： 各トランザクション T がアイテム集合 E の部分集合 になっているようなデータベースD 　つまり、D, ∀T ∈D, T ⊆ E ・ 解が多い　（大きくて面白いものは少ない） ・ 包含関係が厳密 　 「多くの項目になんとなく含まれている」ものを見つけたい アイテム集合に対して、あいまいな包含関係を考え、 頻出集合の列挙アルゴリズムを提案する

4 アルゴリズム的な観点からモデルと解法を見つめたい
既存研究 ・ fault-tolerant pattern、degenerate pattern、soft occurrence などとよばれて、研究されている － 包含関係を一般化する場合、アイテムの含有率が閾値異常のとき、含まれると定義 － あるいは、アイテム集合・トランザクションの組で、アイテムが項目に含まれない回数が小さいようなもの － 文字列などでは、もっと一般的に「類似」を包含関係に使う － 完全性を保証した列挙型の解法は少ない アルゴリズム的な観点からモデルと解法を見つめたい

5 まずは通常の頻出集合 集合K に対して： K の出現： K を含む D のトランザクション K の出現集合 Occ(K)： K の出現の集合
K の頻出度 frq(K)：　 K の出現集合の大きさ 　{1,2}の出現集合 ＝　{ {1,2,5,6,7,9}, {1,2,7,8,9} } 1,2,5,6,7,9 2,3,4,5 1,2,7,8,9 1,7,9 2,7,9 2 D ＝ 　{2,7,9}の出現集合 ＝　{ {1,2,5,6,7,9}, 　　　　{1,2,7,8,9}, {2,7,9} }

6 与えられたトランザクションデータベースと最小サポートσに対して、頻出集合を全て見つける問題が頻出集合列挙
・ 頻出集合： D の閾値σ個以上のトランザクションに含まれる集合 　（頻出度がσ以上の集合）（ σを最小サポートとよぶ） 例） データベース D の3つ以上のトランザクションに含まれる集合 ３つ以上に含まれるもの {1} {2} {7} {9} {1,7} {1,9} {2,7} {2,9} {7,9} {1,7,9} {2,7,9} 1,2,5,6,7,9 2,3,4,5 1,2,7,8,9 1,7,9 2,7,9 2 D ＝ 与えられたトランザクションデータベースと最小サポートσに対して、頻出集合を全て見つける問題が頻出集合列挙

7 擬似包含関係 ・ アイテム集合 P がトランザクション T 含まれる、の定義
・ 良く使われる方法：　閾値θ<1 に対して |P∩T| ／ |P| ≧ θ 　 頻出集合の単調性がなくなる 　 「空集合以外の部分集合は全て頻出でない」頻出集合もある 　 難しい ・ 代わりに「含まないでいいアイテムの数」を使う 閾値θ≧1 に対して |P＼T| ≦θ （k 擬似包含関係とよぶ） 　 単調性は保持 　 多くの項目が P のうち３個のアイテムを含む、といったルールが見つかる

8 ・ k 頻出集合： D のσ個以上のトランザクションに k 擬似包含の意味で含まれるアイテム集合
σ=3での1擬似頻出集合 {1,2,3} {1,2,4} {1,2,5} {1,2,7} {1,2,9} {1,3,7} {1,3,9} {1,4,7} {1,4,9} {1,5,7} {1,5,9} {1,6,7} {1,6,9} {1,7,8} {1,7,9} {1,8,9} {2,3,7} {2,3,9} {2,4,7} {2,4,9} {2,5,7} {2,5,8} {2,5,9} {2,6,7} {2,6,9} {2,7,8} {2,7,9} {2,8,9} {3,7,9} {4,7,9} {5,7,9} {6,7,9} {7,8,9} {1,2,7,9} {1,3,7,9} {1,4,7,9}{1,5,7,9} {1,6,7,9} {1,7,8,9} {2,3,7,9} {2,4,7,9} {2,5,7,9} {2,6,7,9} {2,7,8,9} 1,2,5,6,7,9 2,3,4,5 1,2,7,8,9 1,7,9 2,7,9 2 D ＝ 自明なパターンがたくさんある 効率良い列挙アルゴリズムを考える

9 擬似頻出パターンの単調性 ・ 擬似頻出集合は単調なのでバックトラック法で多項式時間列挙できる 111…1
・ 各末尾拡張のk 擬似頻出度を振り分けで計算することで、1反復の計算時間は O(||D||) 時間になる ・ データの構造・計算の内容が 頻出集合と同じなので、 同じテクニックがそのまま使える －ビットマップ －ダウンプロジェクト －データベース縮約、FP-tree 頻出 111…1 000…0 φ 1,3 1,2 1,2,3 1,2,4 1,3,4 2,3,4 1 2 3 4 3,4 2,4 1,4 2,3 1,2,3,4

10 k 擬似出現集合の計算 ・ Occ=k(P) = {T∈D| |P＼T|=k } とする
－ Occ≦k(P) = ∪Occ=i(P) ・ Occ=h(P∪i) = Occ=h(P)∩Occ(i) ∪ Occ=h-1(P∪i)＼Occ(i)  通常の出現と性質が同じ  更新に同じ技術が使える （ダウンプロジェクト、振り分け…） ・ データベースの圧縮も可能 ・ 再帰が深くなり、頻出度が 小さくなると、計算が速くなる A B C D E F G A B C D E F G A B E F G B A C D F A B C D F A B C D A B C D A B C F A B C D B C F C D

11 ・ バックトラックは、各反復で複数の再帰呼び出しをする  計算木は、下に行くほど大きくなる  計算時間を支配するのは一番下の数レベル
末広がり性 ・ バックトラックは、各反復で複数の再帰呼び出しをする 　 計算木は、下に行くほど大きくなる  計算時間を支配するのは一番下の数レベル ・・・ 計算時間長 計算時間短 計算時間の短縮が期待される

12 最小サポートが大きい場合も ・ θが大きいと、下のレベルでも多くの出現を見ることになる  末広がり性による高速化はいまひとつ
 末広がり性による高速化はいまひとつ ・ データベースの縮約により、下のレベルの高速化をはかる （１） 前回追加したアイテムより小さいアイテムは消す （２） 現在の出現集合からできるデータベースの中で、頻出になっていないアイテムは消去する 　（再帰呼び出しの中で加えられることが無いから） （３） まったく同一のトランザクションは、１つにまとめる ・ 実データだと、下のほうのレベルでは だいたい大きさが定数になる １ ３ ４ ５ ２ ６ ７ σ小さいときと速度の大きな差はない

13 小さくて自明なパターン ・ k 擬似包含関係では、大きさ k 以下のアイテム集合は全てのトランザクションに含まれる
　 多くの小さくて自明な頻出集合が存在する ・ 実用上は、これらを無視したい 　 ある程度 (l とする）の大きさを持つ頻出集合を直接的に見つける方法を考える

14 部分頻出度条件 ・ 大きさ l の集合を工夫なく調べると、指数的な時間がかかる  ある程度絞込みをしたい
　 ある程度絞込みをしたい 　 特徴を持つ部分構造を基にしよう ・ 大きさ l の k 擬似頻出集合 P を考える ・ 一般性を失うことなく、 P={1,…,l} かつ |Occ=k(P)＼Occ({i})| の大きい順に並んでいるとする ・ アイテム集合 {1,…,y} の頻出度を考える ・ Occ=k(P)＼Occ({i}), i>y のトランザクションは 　 {1,…,y} を k-1 擬似包含関係の意味で含む i=2 {1,2,3,4,5} ⊆2 {1,3,5,6,7,10,15}

15 k-1擬似頻出度に関する条件を満たすアイテム集合の列がある
部分頻出度条件 ・ Occ=k(P)＼Occ({i}), i>y のトランザクションは 　 {1,…,y} を k-1 擬似包含関係の意味で含む  |Occk-1({1,…,y})| ≧ |∪j=y+1,...,|P| (Occk(P)＼Occ({i}))| ・ |Occk(P)＼Occ({i})| の平均は (k / |P|) |Occ=k (P)| 以上 ・ 1,…,y は|Occk(P)＼Occ({i})| の昇順で並んでいる  |Occk-1({1,…,y})| ≧ |Occk(P)|×(|P|-y)/|P| P までたどり着く k-1擬似頻出度に関する条件を満たすアイテム集合の列がある

16 部分頻出度条件による探索経路 ・ 大きさ l の k 擬似頻出集合は |Occk-1(P)|＞σ(l-|P|) /l を満たすP のみを経由して見つけられる  この条件を満たすk 擬似頻出集合を全部見つけよう ・ 末尾拡張は使えない（条件を満たさないものが拡張元になる） ・ 逆探索を使う  条件を満たすパターン P は、P＼{i} の中で |Occk-1(P＼{i})| を最大にするものから見つける ・ |Occk-1(P＼{i})| の計算は、振り分けで効率良くできる １反復 O(|P|×||D||) 時間になる

17 部分頻出度を満たす擬似頻出集合 ・ k=1 で最小サポート =3 の場合 1,2,5,6,7,9 部分頻出度条件を満たす頻出集合
2,3,4,5 1,2,7,8,9 1,7,9 2,7,9 2 部分頻出度条件を満たす頻出集合 {1} {2} {5} {7} {9} {1,2} {1,5} {1,6} {1,7} {1,8} {1,9} {2,3} {2,4} {2,5} {2,6} {2,7} {2,8} {2,9} {3,4} {3,5} {4,5} {5,6} {5,7} {5,9} {6,7} {6,9} {7,8} {7,9} {8,9} D ＝ 数が減るので、効率良い探索が期待できる

18 まとめ ・ 「高々 k 個のアイテムが含まれない」という条件を利用したあいまいな包含関係 ・ その包含関係での頻出集合列挙
・ 逆探索による固定サイズの頻出集合を直接的に見つける 　　アルゴリズム 今後の課題 ・実装と計算実験 ・ 他のパターンへの列挙技術の活用 ・ 「r % は含まれる」とした包含関係への取り組み