Document

頻出パターンの高速計算
宇野毅明
Joint work
with
国立情報学研究所
有村博紀（北大）
佐藤健（情報研）
牧野和久（阪大）
中野眞一（群馬大）
清見礼（情報研）
浅井達哉（富士通研）
内田雄三（九州大）
2004年 12月10日コンピューテーション研究会
本日の内容
・頻出集合列挙問題の紹介
・既存アルゴリズム・新規アルゴリズムの紹介
・プログラミングコンテスト(FIMI04)の結果紹介
実際にプログラムを作るときに、
アルゴリズム的な知見はどのように役立つか
（3乗時間のアルゴリズムは動かない世界で）
FIMI03優勝： FP-growth （Grahne, Zhu ）
FIMI04優勝： LCM ver2 （宇野,清見,有村）
トランザクションデータベース
トランザクションデータベース：各トランザクション T がアイ
テム集合 E の部分集合になっているようなデータベース
1,2,5,6,7
つまり、 T , ∀T ∈T , T ⊆ E
2,3,4,5
T ＝ 1,2,7,8,9
1,7,9
・ POSデータ（各項目が、客1人の購入品目）
2,7,9
・アンケートのデータ（1人がチェックした項目）
2
・ web log （1人が1回のwebサーフィンで見たページ）
・オプション装備（車購入時に1人が選んだオプション）
実際のデータは、大きくて疎なものが多い
集合の出現
集合K に対して：
K の出現： K を含むT のトランザクション
K の出現集合 I(K)： K を含むT のトランザクション全ての集合
K の頻出度 frq(K)： K の出現集合の大きさ
1,2,5,6,7,9
2,3,4,5
T ＝ 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 の定数α個以上のトランザクションに含まれる集合
（頻出度がα以上の集合）（αを最小サポートとよぶ）
例）データベースT の3つ以上のトランザクションに含まれる集合
1,2,5,6,7,9
2,3,4,5
T ＝ 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}
{1,7,9} {2,7,9}
バスケット分析
・スーパーなどの小売店舗で、同時に購入される事の多い品物
の組を知りたい
・客が購入した品目 ⇒ トランザクション
・品目の組で、多くの客が購入したもの
⇒ 多くのトランザクションに含まれるアイテム集合
⇒ （あるαに対する）頻出集合
「おむつとビールの組合せが良く売れる」
という解析結果が有名
その他、分類ルールなどを見つけるなどに使われる
頻出集合の問題点
・面白そうなアイテムの組を見つけようとすると、
αを小さくする必要がある
⇒ 大量の頻出集合が出てくる
・情報を失わずに、頻出集合的な、数の少ないものを
見つけるようにモデルを変えたい
極大頻出集合：他の頻出集合に含まれない頻出集合
飽和集合：次に解説
飽和集合 (closed itemset)
・アイテム集合を頻出集合が等しいものでグループ分けする
（各グループを同値類と見なす）
123…n
・飽和集合：グループ（同値類）の中の極大元
（＝出現集合の共通部分）
1,2,4,5
⇒ ユニークに定まる
1,2,5,6,7,9
2,3,4,5
T ＝ 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}
{1,7,9} {2,7,9}
3,5,7,9
φ
飽和集合 (closed itemset)
・飽和集合 ⇔ あるαに対して
極大頻出集合となる
123…n
・アイテム集合Pの、出現集合の
共通部分をPの閉包という
1,2,4,5
3,5,7,9
・ Pの閉包 ⇔ Pを含む極小（最小）な
飽和集合
極大頻出集合
頻出飽和集合
φ
問題
・本発表で扱う問題：
与えられたデータベース T と α に対して、その
１．頻出集合を全て見つける
２．頻出飽和集合を全て見つける
３．極大頻出集合を全て見つける
・それぞれ多くの研究がある
・実装の研究も多くある
これらの問題の既存研究と、我々のアルゴリズム
LCM （Linear time Closed itemset Miner）を解説
問題の困難さ（頻出集合）
・頻出集合の部分集合は頻出集合
⇒ 頻出集合は、アイテム束上で
空集合を含む連結な領域を構成する
⇒ 空集合を出発地点とし、
アイテムを１つずつ加える、
という方法で、任意の頻出集合が
頻出集合しか通らずに作れる
頻出集合は、バックトラックなどのグラフ探索手法で、
1つあたり入力の多項式時間で列挙できる
問題の困難さ（頻出飽和集合）
・飽和集合は、アイテム束上で連結な領域を作らない
⇒ 単純なバックトラックでは（効率良く）列挙できない
・飽和集合は、2部グラフの
極大2部クリークと等価
⇒ 築山らのアルゴリズムで列挙できる
・この列挙アルゴリズムの列挙木は
葉のほうが頻出度が小さい
頻出飽和集合は極大2部クリーク列挙アルゴリズム
で、1つあたり入力の多項式時間で列挙できる
大
小
問題の困難さ（極大頻出集合）
・極大頻出集合は、アイテム束上で連結な領域を作らない
⇒ 単純なバックトラックでは（効率良く）列挙できない
⇒ 現在、多項式時間で
列挙できるかどうか不明
・実際には、枝狩りなどのヒューリ
スティックがうまくいくので、
実験上は１つあたり多項式時間
問題の困難さ（実際には）
・実際の計算では、頻出、飽和、極大、どれも１つ当たり入力多
項式時間で列挙できる
・計算コストがかかっているところは、むしろ多項式時間ででき
る頻出度の計算
・その他、メモリ使用量の減少も課題
アルゴリズム技術の解説
・列挙法
－アプリオリ (apriori)
－バックトラック
－枝狩り (pruning) (飽和・極大)
－prefix保存飽和拡張 (飽和)
－省メモリ枝狩り (極大)
・データベース管理
－ビットマップ
－ FP-tree
－データベース縮約
－反復型
データベース縮約
・極大・飽和性判定
・頻出度計算
－解の保存
－アプリオリ型
－データベース縮約
－ダウンプロジェクト (down project)
－出現配布
頻出集合列挙
・列挙法
・データベース管理
－アプリオリ (apriori)
－ビットマップ
－バックトラック
－ FP-tree
・頻出度計算
－データベース縮約
－アプリオリ型
－反復型
－ダウンプロジェクト (down project)
データベース縮約
－出現配布
列挙法：バックトラック
・空集合から出発し、分枝限定法的に探索するアルゴリズム
・現在の解に、１つアイテムを加えた各解に対し、再帰呼び出し
・重複を避けるため、現在の
1,2,3
1,2,4
1,3,4
2,3,4
解の末尾より大きな
アイテムのみ追加
1,4
2,3 2,4
3,4
1,3
1,2
Backtrack (P)
1
1 Output P
2 For each e > P の末尾（P の最大のアイテム）
If P ∪{e}が頻出 call Backtrack (P ∪{e})
計算時間＝ O( 頻出度計算×|E| )
メリット：
メモリ使用量が小さい
2
3
φ
4
頻出度計算：ダウンプロジェクト
・集合 P∪{e} の出現集合を求める際、素直に行うと、
データベースの全ての項目を調べる必要がある
・ I (P∪{e}) ⊆ I (P) という性質を用いる
⇒ P の出現で e を含むものを見つければよい
⇒ I (P) ∩ I ({e}) を計算すればよい
123 ⊆ A,B,C,D
4 ⊆ B,D,E,F
↓
1234 ⊆ B,D
O( |I(P)| ＋ |I({e})|) 時間
メリット：密すぎず、疎す
ぎないデータで速い
列挙法：アプリオリ
・最初に大きさ１の頻出集合を全て見つけ、メモリに蓄える
・次に大きさ２の頻出集合を、大きさ１の頻出集合を
組合せて全て見つけ、メモリに蓄える
・以後、１つずつ大きさを増やす
計算時間＝ O( 頻出度計算×|E| )
・出現集合計算の工夫
123 ⊆ A,B,C,D
⇒
124 ⊆ B,D,E,F
234 ⊆ B,D
1234 ⊆ B,D
メリット：
出現集合計算の高速化
デメリット：メモリを大量消費＆既発見解検索に手間がかかる
頻出度計算：出現配布
・各 e = P の末尾, …, |E| について、I (P∪{e}) を
一度に全て計算する
P = {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} の出現集合を計算
⇒ 疎な行列の転置を求めているのと同じ
⇒ 非ゼロ要素数の線形時間で求められる
各 e について O( |I(P∪{e}|) ) 時間
A
B
C
3 4 5
4 5
5
3
3
A B C
1,2,3
B C
1,2,4 A
1,2,5 A B
実際の計算では
・ダウンプロジェクトは、出現配布よりも計算量が大きいが、
キャッシュヒット効率が良いので、場合によっては（密なら）速い
・アプリオリ頻出度計算が省略できる計算は、実験的には1/4
程度（ただし、アイテムを含まれる項目の少ない順にソート）
P∪
3
4
5
6
7
8
9
α
AD
ELM
ABCEFGH JKLN
ABDEFGI JKLMSTW
BEGILT
MTW
ABCDFGH IKLMNST
どっちもどっち？？？
データ保持：データベース縮約
・入力したデータべースを縮小して、
メモリの節約と計算の高速化を行う
◆ e を含むトランザクションがα個未満
or 全てのトランザクションに含まれる
⇒ e をデータベースから削除
◆ 等しいトランザクションは１つにまとめる
・サポートが大きいと劇的に小さくなる（データベース縮約とよぶ）
データ保持：反復的縮約
・バックトラック法の各反復は、現在の解 P に
e = P の末尾, …, |E| を追加
⇒再帰呼び出しで呼び出される反復の中では、
P を含むトランザクションの末尾以降の部分しか必要でない
・必要な部分のみ取り出したデータベースを作り、
それを再帰呼び出しに渡す
・さらにこれに、データベース縮約を適用すると
再帰呼び出し内の計算が高速化される
データ保持：ビットマップ
・通常、トランザクションデータベースは巨大なので、データの保
持に工夫を加えると、省メモリ＆高速化が行える
・データベースを行列だと考え、それをビットマップ形式で保持
A
B
C
D
1
1
0
0
0
2
0
1
1
0
3
0
1
0
0
4
1
0
0
1
5
0
1
1
1
メリット：
・密な場合効率が良い
・ 32個ずつ共通部分を取れる
デメリット：
・疎な場合、効率が悪い
データ保持：FP-tree
FP-tree： prefix tree、trie とよばれるものと同じ
・さらに、同一のアイテムをポインタで結ぶ
（アイテムを１つ加えたときの頻出度計算のため）
1
／｜＼
2 3 5
｜｜
4 5
｜
5
2
／｜＼
2 3 4
／｜
4 5
｜
5
3
｜
5
4 5
｜
5
・共有されるprefixの分だけ、
圧縮される
・圧縮率は通常1/2-1/3倍、
最良でも1/6倍程度
(ポインタ部分を除く)
・2分木操作のため、
計算時間は増大
・反復型縮約操作が速い
頻出集合列挙：まとめ
列挙法と頻出度計算：
・アプリオリは頻出度計算を1/4程度省略できる
・バックトラックはメモリ使用量が小さい
－ダウンプロジェクトは中間の密度に強い
－出現配布は疎なデータに強い
● 多くの実装は、バックトラック＋ダウンプロジェクト
● LCMは、バックトラック＋出現配布
データベース保持：
・ビットマップは密なデータに強い
・ FP-treeは密な部分があるデータに強い
● 多くの実装は、データベース縮約＋（ビットマップ or FP-tree）
● LCMは、反復型データベース縮約＋配列
極大頻出集合列挙
・列挙法
－アプリオリ (apriori)
－バックトラック
－枝狩り (pruning) (飽和・極大)
－省メモリ枝狩り (極大)
・極大・飽和性判定
－解の保存
－データベース縮約
極大列挙：解保存法
限定操作：現在の解 P に対して、P ∪ {i,i+1,...,|E|} を含む頻出
集合がすでに見つかっていたら、 i 以降のアイテムを加えた再
帰呼び出しでは極大頻出集合は見つからない
・メモリに暫定の極大解を全て保持する
メモリを消費する＆包含関係の検索に時間がかかる
⇒ P を含む既発見解のみからなるデータベースを随時保持
⇒ P の末尾以降のアイテムを頻出度順でソート
1,2,3
1,2
1,2,4
1,3
1
1,3,4
1,4
2,3,4
2,3
2,4
2
3
φ
3,4
4
極大列挙：バックトラック型枝狩り
・バックトラック法による頻出集合列挙を考える
P ：現在の解
⇒
1 2 3 4 5
Q： P を含む極大解 ⇒
・ Q に含まれるアイテムが
最後に来るよう、並び替える
6
7
8
9
10
並び替え
6
8
10
4
5
7
9
・ Q のアイテムを追加した再帰呼び出しでは、
極大頻出集合は見つからない
メリット：メモリ使用量が小さい
⇒ 再帰呼び出しを省略
デメリット：解保存法の枝狩りより
効率が悪い？
極大性判定
・極大性の判定を素直に行うと、データベース縮約を用いない
頻出度計算以上の手間がかかる
・現在の解 P が極大頻出集合
⇔ 任意の e に対して P∪ {e} が非頻出集合
⇒ 最大 |E| 回の頻出度計算が必要
・解保存法の場合は、包含関係の検索だけですむ
極大性判定：重みつきデータベース
・極大性判定にも縮約したデータベースを使う
ただし、各要素に重みをつける
・縮約操作は、末尾以降が等しい
トランザクションを合併する
・このとき、末尾以前の
各アイテム e に対しても、
e を包むトランザクション数
を記録（これが重み）
1
A1
B 0
C 0
2
0
1
1
3
0
1
0
4
1
0
0
5
1
1
1
6
0
0
0
7
1
1
1
8
0
0
0
9
1
1
1
1 2 3 4 5 6 7 8 9
A 1 2 1 1 3 0 3 0 3
’
極大性判定：重みつきデータベース
・重みが合計が α 以上になるアイテムが存在
⇔ 極大頻出集合ではない
⇒ 縮約データベースを作り、
各アイテムの重み和を
計算することで
極大性が判定できる
1 2 3 4
A’ 1 2 1 1
B 0 1 4 0
’
C 0 1 0 0
’
5 6 7 8 9
3 0 3 0 3
3 0 4 4 0
1 0 1 1 1
メリット：解保存用のメモリ使用量が小さい
デメリット：データベース保持用のメモリ使用量が大きい
計算速度はどっこいどっこい？？
極大頻出集合列挙：まとめ
・解保存＋枝狩り（既存手法）
－計算効率は良い
－解保存のためにメモリを使用するが、頻出集合列挙
ほどは計算時間に対するメモリ使用量が大きくない
・バックトラック型枝狩り＋データベース縮約（LCM）
－計算効率はまあまあ
－解保存用のメモリは不要だが、
重みつきデータベースが2倍のメモリを要する
飽和集合列挙
・列挙法
－アプリオリ (apriori)
－バックトラック
－枝狩り (pruning) (飽和・極大)
－prefix保存飽和拡張 (飽和)
・極大・飽和性判定
－解の保存
－データベース縮約
飽和集合列挙：解保存法
・頻出集合列挙を列挙し、解集合を保持する
ただし、頻出度が同じスーパーセットが存在したら、消去する
⇒ アルゴリズム終了後、解集合は飽和集合の集合になる
・さらに枝狩りを加える
－例えば、バックトラック法で、
124 の閉包が1234 であり、飽和集合でないなら
任意のアイテム集合 124*** は飽和集合にならない
メリット：枝狩りが比較的良く効く
デメリット：メモリを大量に使用、包含関係の検索が重い
飽和集合列挙：飽和拡張
・飽和集合 P に対して、
P の飽和拡張＝（P + アイテム）の閉包
閉包
飽和集合
+
アイテム
－任意の飽和集合は、他の飽和集合の飽和拡張になる
－（ P の頻出度）＞（ P の飽和拡張の頻出度）
⇒ 飽和拡張が導出する関係は、閉路を含まず、全ての飽
和集合を張る
飽和拡張の関係図
・飽和拡張は非閉路的な関係を導出する
・出次数は高々 |E|
frequent
・グラフ探索で（頻出飽和集合数の）線形時間で列挙できる
メリット：線形時間列挙
デメリット：閉包の計算が重い、メモリを大量に使用
Prefix保存飽和拡張
・ prefix保存飽和拡張は、飽和拡張のバリエーション
定義：飽和集合P の閉包末尾
⇔ P ＝閉包（P ∩{1,…,j}）が成り立つ最小の j
定義：飽和拡張 H ＝閉包（P ∪{i}）が P のprefix保存飽和拡張
⇔ i > j かつ H ∩{1,…,i-1} ＝ P ∩{1,…,i-1} が成立
・ prefix保存飽和拡張には閉包の操作のみ必要（既発見解は不
要）
・任意の飽和集合は、他の唯一の飽和集合のPrefix保存飽和拡張
⇒ メモリを使うことなく、飽和集合を重複なく探索できる
飽和拡張・prefix保存飽和拡張の例
φ
・飽和拡張 ⇒ 非閉路グラフ
・ prefix保存飽和拡張 ⇒ 木
2
7,9
1,2,5,6,7,9
2,3,4,5
T ＝ 1,2,7,8,9
1,7,9
2,7,9
2
飽和拡張
prefix保存飽和拡張
1,7,9
2,5
1,2,7,9
1,2,7,8,9
2,3,4,5
1,2,5,6,7,9
2,7,9
頻出飽和集合列挙：まとめ
・解保存＋枝狩り（既存手法）
－計算効率はまあまあ
－解保存のためにメモリを使用する
頻出集合列挙ほどではないが、極大よりは多い
・バックトラック型枝狩り＋データベース縮約
－計算効率が良い
－解保存用のメモリが不要
（LCM）
計算機実験：FIMI04
・ FIMI: Frequent Itemset Mining Implementations
ICDM (International Conference on Data Mining) サテライト
ワークショップで、頻出／頻出飽和／極大頻出集合列挙のプ
ログラムコンテストを行った。去年・今年で2回目。
・去年は15、今年は8個の投稿があった
・ルール：ファイルを読み、列挙してファイルに書くこと
Time コマンドで時間を計測（メモリも他のコマンドで計測）
CPUを制御する命令（パイプラインなど）は使用禁止
計算機実験：FIMI04
・計算機環境：CPU、メモリ: Pentium4 3.2GHz、1GB RAM
OS、言語、コンパイラ: Linux 、C言語、gcc
・データセット：
－実データ：疎、アイテム数大
－機械学習用データ：密、アイテム数小、規則的
－人工データ：疎、アイテム数大、ランダム
－密な実データ：超蜜、アイテム数小
賞状と賞品
賞品は {ビール, 紙おむつ}
“Most Frequent Itemset” だそうです
実データ（超疎)
BMS-WebView2
飽和：LCM
頻出：LCM
極大：afopt
実データ（疎）
kosarak
飽和：LCM
頻出：nonodrfp＆LCM
極大： LCM
機械学習データ
pumsb
頻出：いろいろ
飽和：LCM＆DCI-closed
極大： LCM＆
FP-growth
密な実データ
acidents
飽和：LCM＆FP-growth
頻出：nonodrfp
＆FP-growth
極大： LCM
＆FP-growth
メモリ使用量
pumsb
頻出
飽和
極大
観察と考察
・頻出集合列挙には、apriori はそれほど効果がないようだ
・ FP-tree、データベースの縮小はαが大きいとき効く
・出現配布は、αが小さいとき効く
・極大性の判定は、他のアルゴリズムも優秀
・ prefix保存飽和拡張・同値類が大きいと効果的
・飽和性判定用データベース縮小は効果的
LCMは実データのような疎で構造があり解が多い場合に強い
今後の課題
・密なデータベースを効率良く扱う
・ radix sort の高速化
・極大列挙での効率の良い枝狩り
・ IOの改良
周りの評価はというと．．．
・頻出集合列挙をしている人々からの反応は今ひとつ
← 今までの流れにぜんぜん乗っていない
「君のはわけがわからないけど速いね」
・ LCMは本質でないところで速くしている、という感触
・データマイニングの人からは、
－仕事としては良い
－ FIMIは重箱の隅をつついている
（現実問題への取り組みを前進させていない）
・ εペーパーの集まり？？？（どこの分野もそうだけど）
今後の目標は
・列挙問題は、一般化された問題がない
☆ 数理計画 ⇒ LP、IP ☆データベース検索 ⇒ 2分木、SQL
☆ 全張木の列挙は、木の列挙では時間がかかりすぎ
・新しい問題に対して、列挙アルゴリズムを＊簡単に＊作れる
ような知見が必要
☆ 簡単・シンプル・速いアルゴリズム
☆ 問題構造の直感的解析
☆ 実際の計算でのアルゴリズム技術やデータ構造
・ FIMIも、こういう知見を得たいからやっているのだと思う
最後に
・今後、CPUの速度は以前のように劇的には向上しないようだ
今後はアルゴリズムの時代
（並列計算？？？）
頻出集合の列挙
・頻出集合列挙のボトルネックは、頻出度計算
・同値類内は、オカレンス集合が等しい
⇒ 頻出度計算が省略できる
・閉包を取らない解と閉包を取った解を保持
⇒ 両者は、同値類中の超立方体を導出
⇒ 超立方体内の解を列挙
同値類が大きければ効率が良い

Download Report