頻出・飽和・極大頻出集合の効率的な列挙アルゴリズムとその実装

Presentation on theme: "頻出・飽和・極大頻出集合の効率的な列挙アルゴリズムとその実装"— Presentation transcript:

1 頻出・飽和・極大頻出集合の効率的な列挙アルゴリズムとその実装
宇野 毅明 清見 礼 有村 博紀 国立情報学研究所 北海道大学 2004年 9月30日 データマイニングワークショップ

2 トランザクションデータベース トランザクションデータベース： 各トランザクション T がアイテム集合 E の部分集合になっているようなデータベース 　つまり、　T , ∀T ∈T , T ⊆ E ・ POSデータ（各項目が、客1人の購入品目） ・ アンケートのデータ（1人がチェックした項目） ・ web log （1人が1回のwebサーフィンで見たページ） ・ オプション装備 （車購入時に1人が選んだオプション） 1,2,5,6,7 2,3,4,5 1,2,7,8,9 1,7,9 2,7,9 2 T ＝ 実際のデータは、疎であり大きいものが多い

3 集合K に対して： K のオカレンス： K を含むT の項目 K のオカレンス集合 Occ(K)： K を含むT の項目全ての集合
集合のオカレンス 集合K に対して： K のオカレンス：　 K を含むT の項目 K のオカレンス集合 Occ(K)：　 K を含むT の項目全ての集合 1,2,5,6,7,9 2,3,4,5 1,2,7,8,9 1,7,9 2,7,9 2 　{1,2}のオカレンス集合 ＝　{ {1,2,5,6,7,9}, {1,2,7,8,9} } T ＝

4 頻出集合 ・ 頻出集合：T の定数α個以上のトランザクションに含まれる集合 （オカレンス集合のサイズがα以上の集合）（α：最小サポート）
　（オカレンス集合のサイズがα以上の集合）（α：最小サポート） 極大頻出集合：他の頻出集合に含まれない頻出集合 例） データベースT の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} {7} {9} {1,7} {1,9} {2,7} {2,9} {7,9} {2,7,9} T ＝

5 飽和集合 ・ 頻出集合をオカレンス集合が等しいものでグループにわける （これを同値類と見なす） ・ 飽和集合： グループの中の極大元
・ 頻出集合をオカレンス集合が等しいものでグループにわける　　　　　（これを同値類と見なす） ・ 飽和集合： グループの中の極大元 　 （＝ オカレンス集合の共通部分） 　⇒　ユニークに定まる ・ アイテム集合に対して、 そのオカレンス集合の 共通部分を閉包という 極大頻出集合 頻出飽和集合

6 問題 ・ 本発表で扱う問題： 与えられたデータベース T と α に対して、その １．頻出集合を全て見つける ２．頻出飽和集合を全て見つける
　 １．頻出集合を全て見つける 　 ２．頻出飽和集合を全て見つける 　 ３．極大頻出集合を全て見つける ・それぞれ多くの研究がある ・実装の研究も多くある これらの問題に対して、アルゴリズム LCM （Linear time Closed itemset Miner）を提案

7 各レベルを順に計算（apriori） （既存）
・ 最初に大きさ1の頻出集合を全て見つけ、メモリに蓄える ・ 次に大きさ2の頻出集合を、大きさ1の頻出集合を組合せて全て見つけ、メモリに蓄える ・ 以後、１つずつ大きさを増やす メリット：　　 オカレンス計算の高速化 デメリット：　メモリを大量消費＆既発見解検索時間の増加

8 バックトラック法 （既存） ・ 空集合から出発し、分枝限定法的に探索するアルゴリズム
バックトラック法　（既存） ・ 空集合から出発し、分枝限定法的に探索するアルゴリズム ・ 現在の解に、１つアイテムを加えた各解に対し、再帰呼び出し ・ 重複を避けるため、現在の解の末尾より大きなアイテムのみ追加 Backtrack　(K) 1 Output K 2 For each e > K の末尾（ K の最大のアイテム） If K ∪{e}が頻出 call Backtrack　(K ∪{e}) 1,2,3 1,2,4 1,3,4 2,3,4 1,2 1,3 1,4 2,3 2,4 3,4 1 2 3 4 φ 計算時間 ＝ O( 頻出度のチェック時間×|E| )

9 頻出度計算 （既存） ・ 集合 K∪{e} のオカレンスを求める際、素直に行うと、 データベースの全ての項目を調べる必要がある
頻出度計算　（既存） ・ 集合 K∪{e} のオカレンスを求める際、素直に行うと、 　　　データベースの全ての項目を調べる必要がある ・ Occ( K∪{e} ) 　⊆　 Occ(K) という性質を用いる 　⇒ K のオカレンスで e を含むものを見つければよい ⇒ Occ(K) ∩ Occ({e}) を計算すればよい （ダウン･プロジェクト、という） O( | Occ(K)| ＋ | Occ({e})|) 時間

10 検索用のデータ構造 （既存） FP-tree： 今までに発見した頻出集合を蓄えるデータ構造
検索用のデータ構造　（既存） FP-tree：　今までに発見した頻出集合を蓄えるデータ構造 prefix tree、trie とよばれるものと同じ ・ FP-treeは入力したデータベースを保管するのにも使われる （同一項目の縮約などの操作が楽なため） ・圧縮したprefixの分だけ、 頻出度の計算が速くなる ・圧縮率は通常1/2-1/3倍、 最良でも1/6倍程度 ・2分木操作のため、 計算時間は増大 　 ／｜＼ ／｜＼ 　　｜ 　｜ ｜｜ ／｜ 　　 ｜ ｜ 　　

11 各 e について O( |Occ(K∪{e}|) ) 時間
オカレンスの配布　（新規） ・各 e = K の末尾, …, |E| について、Occ(K ∪{e}) を 　　一度に全て計算する K = {1,2} のオカレンス A{1,2,4,5}　B{1,2,3} C{1,2,3,4} ・バックトラック法は、末尾以降のアイテムを追加 ⇒ {1,2,3}, {1,2,4}, {1,2,5} のオカレンス集合を計算 　⇒ 疎な行列の転置を求めているのと同じ 　⇒ 非ゼロ要素数の線形時間で求められる A B C 4 5 3 A B C 1,2,3 1,2,4 1,2,5 B C A 各 e について O( |Occ(K∪{e}|) ) 時間

12 実際の計算では （新規） ・ 頻出度計算では、生成した集合 K∪{e} が非頻出なら、
実際の計算では　（新規） ・ 頻出度計算では、生成した集合 K∪{e} が非頻出なら、 それは無駄な計算 （うまくすれば省略できる可能性がある） ・ しかし、そのような無駄は、計算全体の1/3 以下 　　 （ただし、アイテムを「含まれる項目数」の小さい順でソート） K∪ α 3 4 5 6 7 8 9 AD ELM ABCEFGH JKLN ABDEFGI JKLMSTW BEGILT MTW ABCDFGH IKLMNST 検索の手間がない分 オカレンス配布が 有利と思われる

13 データベースの縮小 （既存＆新規） ・ 入力したデータべースを縮小して、計算を高速化する ◆ e を含むトランザクションがα個未満
データベースの縮小　（既存＆新規） ・ 入力したデータべースを縮小して、計算を高速化する 　　　　◆ e を含むトランザクションがα個未満 　　　　　　 or 全てのトランザクションに含まれる 　　　　　　　　⇒ e をデータベースから削除 　　　　◆ 等しいトランザクションは１つにまとめる ・サポートが大きいと劇的に小さくなる（データベース縮約とよぶ） さらに、バックトラック法なら、各反復で 　　　　 ◆ 末尾以前のアイテムを消去 してからデータベース縮約をすると、反復的に縮約され、 さらなる高速化が行われる（反復型データベース縮約とよぶ）

14 極大＆飽和頻出集合の列挙 （既存） ・ 頻出集合列挙のアルゴリズムに限定操作を加える 極大用、限定操作： １つ極大解が見つかったら、
極大＆飽和頻出集合の列挙　（既存） ・ 頻出集合列挙のアルゴリズムに限定操作を加える 極大用、限定操作： １つ極大解が見つかったら、 　　　　　　　　　その部分集合は極大解の候補からはずす 飽和用、限定操作： 同一のオカレンス集合を持つ集合の中で、 　　　　　　　　　極大でないものを候補からはずす ・ メモリに解を保持して実装する

15 飽和拡張 （既存） ・ 飽和集合 K に対して、 K の飽和拡張 ＝ （K + アイテム） の閉包
飽和拡張　 （既存） ・ 飽和集合 K に対して、 　　K の飽和拡張　＝　（K + アイテム） の閉包 　－ 任意の飽和集合は、他の飽和集合の飽和拡張になる 　－ （ K の頻出度） ＞（ K の飽和拡張の頻出度）なので、 　　　　　飽和拡張が導出する関係は、閉路を含まない ・ 飽和拡張をもとに列挙アルゴリズムを構築すると、 　計算時間が飽和集合数の線形になる

16 Prefix保存飽和拡張 （新規） ・ prefix保存飽和拡張は、飽和拡張のバリエーション 定義： 飽和集合K の閉包末尾
　 ⇔　　K ＝閉包 （K ∩{1,…,j}） が成り立つ最小の j 定義：　飽和拡張 H ＝ 閉包 （K ∪{i}）が K のprefix保存飽和拡張 　 ⇔ i > j かつ H ∩{1,…,i-1} ＝ K ∩{1,…,i-1} が成立 ・ prefix保存飽和拡張には閉包の操作のみ必要 （既発見解は不要） ・ 任意の飽和集合は、他の唯一の飽和集合のPrefix保存飽和拡張 　 ⇒ 　メモリを使うことなく、飽和集合を重複なく探索できる

17 ・ 飽和拡張 ⇒ 非閉路グラフ ・ prefix保存飽和拡張 ⇒ 木
φ ・ 飽和拡張 ⇒ 非閉路グラフ ・ prefix保存飽和拡張 ⇒ 木 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 1,7,9 T ＝ 2,5 2,7,9 1,2,7,9 2,3,4,5 飽和拡張 prefix保存飽和拡張 1,2,7,8,9 1,2,5,6,7,9

18 頻出集合の列挙 ・ 頻出集合列挙のボトルネックは、頻出度計算 ・ 同値類内は、オカレンス集合が等しい ⇒ 頻出度計算が省略できる
　⇒　頻出度計算が省略できる ・ 閉包を取らない解と閉包を取った解を保持 　⇒　両者は、同値類中の超立方体を導出 　⇒　超立方体内の解を列挙 同値類が大きければ効率が良い

19 極大頻出集合の列挙 （新規） ・ バックトラック法による頻出集合列挙を考える K ： 現在の解 ⇒ H： K を含む閉包 ⇒
極大頻出集合の列挙　（新規） ・ バックトラック法による頻出集合列挙を考える K ： 現在の解　　　⇒ H： K を含む閉包 ⇒ ・ H に含まれるアイテムが 最後に来るよう、並び替える ・ H のアイテムを追加した再帰呼び出しでは、 極大頻出集合は見つからない 　　⇒ 再帰呼び出しを省略 1 2 3 4 5 6 7 8 9 10 並び替え 6 8 10 4 5 7 9 反復数が劇的に減少

20 閉包・極大性判定 （新規） ・ 閉包の計算や、極大性の判定を素直に行うと、 データベース縮約を用いない頻出度計算と、
閉包・極大性判定 （新規） ・ 閉包の計算や、極大性の判定を素直に行うと、 データベース縮約を用いない頻出度計算と、 同程度、あるいはそれ以上の手間がかかる ・ 閉包・極大性判定にもデータベース縮約を使う 　－閉包末尾以後が等しいトランザクションを１つにまとめる 　　ただし、閉包末尾以前は以下を保存 　　　　 ・ 閉包計算　 　 ⇒　共通部分 　　　　 ・ 極大性判定　 ⇒　各アイテムの含まれる数 頻出度計算と同程度、データベースが縮小される

21 計算機実験 ・ 計算機環境： CPU、メモリ: AMD Athron XP 1600+ 、 224MB
OS、言語、コンパイラ: Linux 、C言語、gcc ・比較アルゴリズム FP-growth, afopt, MAFIA, PATRICIAMINE, kDCI （どれも、実装コンテスト FIMI03 で優秀な成績をおさめたもの） ・データセット FIMI03、KDD-cupなどで使われた、人工データ、実データ

22 結果

23 観察と考察 ・ prefix保存飽和拡張・超立方体分解は、同値類が大きいと効果的 ・ 極大性の判定は、他のアルゴリズムも優秀
・ データベースの縮小は 　 αが大きいとき ＆ Occ(K) が大きいとき、とても良く効くようだ ・ apriori はそれほど効果がないようだ ・ オカレンス配布は、α、Occ(K) が小さいとき、効くようだ ・逆に FP-treeは、α、Occ(K) が大きいとき、効くようだ 大きいサポート、疎なデータベースでは全勝。Closed でほぼ全勝。 all,maximal ＋ 小さなサポート、密なデータベースで半々。 我々のアルゴリズムは、構造があり、解が多い場合に強い

24 まとめと今後の課題 ・ prefix保存飽和拡張と、それを用いた、線形時間・多項 式メモリの飽和集合列挙アルゴリズムLCM を提案した
・ 計算を高速化するアルゴリズムを提案した ・ 多くの問題において既存手法より良い結果を出した ・ FP-tree 的な手法を加味した、さらなる高速化が課題

25 FIMI '03 ・ Frequent Itemset Mining Interpretation 頻出集合列挙アルゴリズムの実装コンテスト
　　頻出集合列挙アルゴリズムの実装コンテスト ・ 20ほどのアルゴリズムが参加した 　　　（我々も参加）

26 他のアルゴリズムの特徴 ・ 基本は、頻出集合列挙。apriori が主流 ・ がんばった人は FP-treeを使用
・ 前処理によるデータベースの縮小がさかん 　(long の代わりに short を使い、キャッシュ効率を良くする、 　　という重箱隅的なものまである） ・ 極大頻出集合列挙には、限定操作を多用 ・ diffset はよく使われるが、オカレンス配布は使ってないようだ これらを丁寧にじっくり実装したアルゴリズムが高速 奇抜なアイディアもあったが、全部遅い

27 実験に使われたデータベース － web log － POS － 機械学習用の問題 － 事故処理のデータ － リテール － 人工データ
・ 問題規模は大きく、項目数は 1万-100万 　　　台集合の大きさも500-5万