頻出集合列挙アルゴリズムに対する 実用的高速化技術について

Presentation on theme: "頻出集合列挙アルゴリズムに対する 実用的高速化技術について"— Presentation transcript:

1 頻出集合列挙アルゴリズムに対する 実用的高速化技術について
宇野 毅明 浅井 達哉 有村 博紀 内田 雄三 国立情報学研究所 九州大学 2004年 3月19日 アルゴリズム研究会

2 本日の発表内容 頻出集合列挙アルゴリズムに対する 「実用的な高速化を行う技法」の議論をする ・ 既存の頻出集合列挙アルゴリズムの技術
・ Closed itemset の線形列挙と 　　同値類を用いた頻出集合の列挙 ・ 実装コンテストFIMI'03での結果を紹介 ・ 結果から、高速化に必要な技術を考察 今日は　報告　と　考察　がメインです

3 トランザクションデータベース トランザクションデータベース： 各項目 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 ＝ 実際のデータは、疎であり大きいものが多い

4 集合K に対して： K のオカレンス： K を含むT の項目 K のオカレンス集合T(K)： K を含むT の項目全てからなる集合
集合のオカレンス 集合K に対して： K のオカレンス：　K を含むT の項目 K のオカレンス集合T(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 ＝

5 頻出集合 ・ 頻出集合： 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 ＝

6 Closed itemset ・ 頻出集合をオカレンス集合が等しいもので グループにわける （これを同値類と見なす）
　　グループにわける　　（これを同値類と見なす） ・ closed itemset： グループの中の極大元 　 オカレンス集合の共通部分 　⇒　ユニークに定まる ・ オカレンス集合の共通部分 を閉包という 極大頻出集合 closed itemset

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

8 オカレンス集合の計算（既存研究） ・ 集合 X∪{e} のオカレンス計算は、素直に行うと、データベースの全ての項目を調べる
・ T( X∪{e} ) 　⊆　T(X) 　⇒ X のオカレンスで e を含むものを見つければよい Occurrence (X, e) 1 For each T ∈ T(X) If T が e を含む output T O( |T(X)| ) 時間

9 有利な方法で計算しよう（既存研究） ・ 集合 Y={1,2,3,4,5} のオカレンス計算は、
　－{1,2,3,4 } のオカレンスで 5 を含むもの 　－{1,2,3, 5} のオカレンスで 4 を含むもの 　－{1,2, 4,5} のオカレンスで 3 を含むもの 　－{1, 3,4,5} のオカレンスで 2 を含むもの 　－{ 2,3,4,5} のオカレンスで 1 を含むもの どの方法で計算しても良い （バックトラックの場合は一通りしかできないが．．．） ・ オカレンス集合が小さいものを使うと高速 ・ そもそも、これらの中に非頻出なものがあれば 「Yは非頻出」

10 各レベルを順に計算（apriori）（既存研究）
・ 最初に大きさ1の頻出集合を全て見つけ、メモリに蓄える ・ 次に大きさ2の頻出集合を全て見つけ、メモリに蓄える ・ 以後１つずつ大きさを増やす ・ 大きさ k の頻出集合は、大きさ k-1 の頻出集合に要素を１つ加えたもの 　⇒ 大きさ k-1 の頻出集合に各要素を加えて、候補を作る ・ このとき、オカレンス計算が有利な作り方選ぶ メリット：　　 オカレンス計算の高速化 デメリット：　メモリを大量消費＆既発見解検索時間の増加

11 検索用のデータ構造（既存研究） FP-tree： 今までに発見した頻出集合を蓄えるデータ構造
Suffix tree、trie とよばれるものと同じ ・ FP-treeは入力したデータベースを保管するのにも使われる （同一項目の縮約などの操作が楽なため） 　 ／｜＼ ／｜＼ 　　｜ 　｜ ｜｜ ／｜ 　　 ｜ ｜ 　　

12 オカレンスの配布（既存研究？） X = {1,2} Xのオカレンス A{1,2,3,4} B{1,2,5} C{1,2,4,5}
　のオカレンス集合を求めたい Occ[3]: Occ[4]: Occ[5]: A C B O( T(X∪e) )時間

13 ・ T(X) と T(X∪{e}) がそれほど異ならない場合 T(X)＼T(X∪{e}) が計算できれば、オカレンス計算は速い
diffset（既存研究） ・ T(X) と T(X∪{e}) がそれほど異ならない場合 T(X)＼T(X∪{e}) が計算できれば、オカレンス計算は速い T(X) : Occ[3]: Occ[4]: Occ[5]:

14 Hybrid （新規） ・ diffset を使うと高速になるかどうかは、状況しだい
　　有利なほうを選択する ・ ある反復でdiffset が有利なら、子孫では必ずdiffset が有利 ⇒ 切り替えは「通常」 －> 「diffset」 のみを考えればよい

15 オカレンス計算のまとめ（既存＆新規） ・ X∪{e} のオカレンス集合を計算するのにかかる時間 工夫無し： O（ データベースサイズ ）
工夫あり：　O（|T(X)| ） apriori： O（ 1つ小さい部分集合の最小オカレンス集合サイズ 　　　　　　　　＋検索時間、　非頻出の場合は、検索時間のみ ） オカレンス配布： O（ |T(X∪{e})| ） diffset： O（ |T(X)＼T(X∪{e})| ) ） hybrid： O（ min{ オカレンス配布, diffset ） ・ Apriori とオカレンス配布が競合 ・ diffset は問題によっては速い

16 実際の計算では（新規） ・ X∪{e}のオカレンス集合のサイズの合計を比べる 頻出のもの全部 ： 非頻出のもの全部 ＝ ２～３ ： １
頻出のもの全部 ： 非頻出のもの全部　　＝ ２～３ ： １ （ただし、要素を「含まれる項目数」の小さい順でソート） X∪ α 3 4 5 6 7 8 9 AD ELM ABCEFGH JKLN ABDEFGI JKLMSTW BEGILT MTW ABCDFGH IKLMNST 検索の手間がない分 オカレンス配布が 有利と思われる

17 データベースの縮小（既存研究） ・ αが大きければ、データベースを小さくして計算時間を短縮できる ◆ e を含む項目がα個未満
◆ 等しい項目は１つにまとめる ・ 10分の1程度になることもある

18 極大＆closeditemsetの列挙（既存研究）
・ 頻出集合列挙のバックトラックアルゴリズムやapriori に限定操作を加える 限定操作： １つ極大解が見つかったら、その部分集合は極大解(closed itemset)の候補からはずす ・ aoriori タイプのアルゴリズムだと簡単に実装できる ・ その場合、1レベルごとの計算は行わない

19 極大2部クリーク列挙 ・ closed itemset の列挙は極大2部クリークの列挙と等価
・ 入力したデータベース T に対してあるグラフ G を作ると、そのグラフの極大2部クリークとclosed itemset が対応 ・ クリーク列挙のアルゴリズムでclosed itemset が列挙できる － 築山 et.al. '77 O( 頂点数×枝数 ) 時間 － 宇野 ' O( 最大次数 3 ) 時間

20 列挙木を深さ優先探索して全ての解を出力する
逆探索 ・ closed itemset 上に、非巡回的な親子関係を定義する （各closed itemset に親を定義する） ・ 非巡回的なので、親子関係は木を導出する（列挙木） 列挙木を深さ優先探索して全ての解を出力する ・ 子供を見つけるアルゴリズムがあれば十分

21 closed itemset の親 ・ 集合 K の閉包 ： K を含む項目の共通部分
　　　⇒ K が属する同値類の極大元であるclosed itemset ・ closed itemset K の親添え字 i(K) ： 　　　　 K∩{1,…,i} の閉包が K であるような最小のi ・ closed itemset K の親 　　　　 K∩{1,…,i(K)-1} の閉包 例） {2,7,8,9} の親添え字： 7 {2,7,8,9} の親： {2,8} 1,2,6,7,8,9 2,5,8 1,7,9 2,7,8,9 2,8 T ＝ ・ φ 以外には必ず親が存在 ・ 親はサイズが真に小さいので非巡回的

22 closed itemset の子 K の子供を求めるには、親を求める作業の逆をすればよい
・ K[i] ：K∪iの閉包。ただし i > i(K) ・K'= K[i] ＆ K[i]とK の i 以下の部分が等しい 　　　　 ⇔ K' はK の子供 例） {2,4,7,8,9} の親添え字： 7 {2,4,7,8,9} の親： {2,4,8} ・ K[i] は親を求める操作の逆 ・ i > i(K) でなければ i(K')≠i ・K[i]とK の i 以下の部分が異なると、K' の親はK でない 1,2,4,6,7,8,9 2,4,5,8 1,7,9 2,4,7,8,9 2,4,8 T ＝

23 全ての子供を見つける ・K の全ての子供を求める ⇒ 全ての i > i(K) に対して K[i]（K∪iの閉包）を計算
closed itemset １つあたり多項式時間 出力線形アルゴリズム

24 子供を見つける計算時間 1 オカレンス配布で、各K[i] のオカレンス集合を計算 ⇒ 各々 O（ |T(K[i])| ） 時間
　⇒ 最小サイズのK[i]のオカレンスT*の各要素 e について 　 全てのK[i]のオカレンスに含まれるか調べる 　⇒ O（ |T*＼K|×|T(K[i])| ） 時間 　 （含まないものが１つでも見つかればその時点で終了。 　　　実際はO（ |T(K[i])| ） より小さい） ・ 隣接行列を用いるとチェックが速い （メモリ節約のため、大きなサイズの項目に対してのみ行を構築）

25 全ての子供を見つける K の全ての子供を求める ⇒ 全ての i > i(K) に対して K[i]（K∪iの閉包）を計算
・ 2 のチェックは最小サイズのオカレンスに含まれるものだけでよい ・ 隣接行列を用いるとチェックが速い （メモリ節約のため、大きなサイズの項目に対してのみ行を構築）

26 極大頻出集合の列挙 ・ 極大頻出集合ならばclosed itemset ⇒ closed itemset を列挙して、極大性をチェックする
・ オカレンス配布、あるいは diffset で、 　　簡単に判定できる

27 頻出集合の列挙 ・ 頻出集合列挙のボトルネックは、オカレンス計算 ・ closed itemset の同値類内は、オカレンス集合が等しい
　⇒　オカレンス計算が省略できる ・ 閉包を取らない解と閉包を取った解を保持 　⇒　両者は、同値類中の超立方体を導出 ・ 全ての組 　⇒　全ての同値類を超立方体に分割

28 FIMI '03 ・ Frequent Itemset Mining Interpretation 頻出集合列挙アルゴリズムの実装コンテスト
　　頻出集合列挙アルゴリズムの実装コンテスト ・ 20ほどのアルゴリズムが参加した 　　　（我々も参加） ・ この結果を簡単に解説

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

30 ・ 他のアルゴリズム －apriori －diffset －データベースの縮小 －FP-tree
使用技術の比較 ・ 我々のアルゴリズム 　　－closed itemset の 　　　　　出力線形時間列挙 　　－オカレンス配布 　　－diffset と hybrid 　　－rightmost sweep 　　－hypercube decomposition ・ 他のアルゴリズム 　　－apriori 　　－diffset 　　－データベースの縮小 　　－FP-tree

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

32 問題の分類 ・ 計算にかかる手間は － オカレンス集合の大きさ （αの大きさ） － closed itemset の同値類の大きさ
　　－ オカレンス集合の大きさ　（αの大きさ） 　　－ closed itemset の同値類の大きさ に依存するだろう ・ これらで問題を分類 それぞれのカテゴリで アルゴリズムの効率を比較 T(X)小 T(X)大 同値類 大きい Weblog リテール 機械学習 　　データ 小さい POS 人工データ 事故処理

33 頻出集合 closed itemset 極大頻出集合
結果 T(X)小 T(X)大 α小 α大 同値類大 我々 両方 同値類小 他 頻出集合 closed itemset 極大頻出集合 T(X)小 T(X)大 α小 α大 同値類大 我々 他 同値類小

34 観察と考察 ・ 出力線形アルゴリズム＆hypercuve decomposition は
　　closed itemset の同値類が大きいと効率良いようだ ・ データベースの縮小は 　 αが大きいとき ＆ T(X) が大きいとき、とても良く効くようだ ・ apriori、FP-treeはそれほど効果がないようだ ・ オカレンス配布＆rightmost sweep は、 　　　　αが小さいとき ＆ T(X) が小さいとき、効くようだ ・ αが大きいとき ＆ T(X) が大きいときは、hybrid が効くようだ 我々のアルゴリズムは、 構造があり、解が多い場合に強い