Document

頻出集合発見問題に対する
アルゴリズム技術
宇野毅明（情報学研究所）
有村博紀（北海道大学）
中野眞一（群馬大学）
佐藤寛子（情報学研究所）
佐藤健（情報学研究所）
清見礼（JAIST）
2007年2月28日コンピューテーション研究会
列挙とその応用の基本
列挙問題とは何でしょう
列挙問題：与えられた問題の解を全て重複なく見つけ出す問題
・グラフの2点間を結ぶパス
・数の合計の可能性
B
A
．．．
・ 1,3,5,8,14 の中から数字を
選んでできる合計を列挙せよ
解）
0, 1, 3, 4, 5, 6, 8, 9, 11, 12, 13,
14, 15, 16, 17, 18, 19, 20, 22,
23, 25, 26, 27, 28, 30, 31
情報科学の基礎的な問題
・頂点 A と B を結ぶパスを列挙せよ
解）
…
近年、広く使われ始めている
列挙は多面的
・最適化は問題の一部分を見つける
 列挙は問題の全ての部分を見つける
列挙では解の全てを見つけるため、
問題の構造を全体的に把握することができる
「最適ではないが、役に立つ解」を、見つけ損なわない
問題の構造を調べたいとき、数理的にクリアでない
目的関数で解を得たいときに、列挙が有効
あいまいな目的
web ページの検索（見つけたいページを見つける）
① キーワードを指定
② キーワードを含むページを列挙
③ 見つかったページを実際に検証
候補
Web ページ
データベース
キーワード検索
Enumerations
from databases
solve many
problems and
Enumerations
give new
from databases
knowledge
Enumerations
solve many
Enumerations
from
databases
problems and
from
databases
solve
many
give new
solve
many
problems
and
knowledge
problems andgive new
give new knowledge
knowledge
Enumerations
from databases
solve many
problems and
give new
knowledge
実際にページ
を見て検証
・数理的な部分をコンピュータで解く（候補の列挙）
・残りはユーザに任せる（候補の絞込み）
モデルから見ると
モデルが
・シンプルかつ小規模なら、最適化が有効
（きれいな問題の良質な解を１つ求める）
・複雑あるいは大規模ならばシミュレーションが有効
（複雑・大規模な問題の多数の解を見つける）
列挙は中間に位置する
シンプルなモデル
をじっくり解く
線形計画
局所探索
組合せ最適化
最適
化
複雑なモデル
を粗く解く
列挙
良質な解を多数見つける
シミュレ
ーション
アドホック
ネットワーク
物理現象の計算
列挙研究の歴史
計算機パワーの増大
実用の可能性が発現
応用の発達
応用で使われ始める
（データマイニングなど）
1960
黎明期：
基礎問題と計算量
解が多さで、実用
の観点はなし
1990
2000
逆探索
の出現
極大元
列挙法
の出現
複雑な構造に対する
列挙法の発達
実用的なアルゴ
リズムの発達
（疎な構造の利用、
巨大データ処理等）
OR的アプローチのボトルネック
典型的なOR的なアプローチは、データ収集でつまづくことが多い
典型的な OR（＋数理計画）的アプローチ
問題発見
定式化
解法（最適化）
できたモデルを実際に使う
データ収集
（システム構築）
ここがボトルネック
であることが多い
求解
運用
その一方で、データが
あふれている場所もある
データ中心の科学
・近年、IT技術の発達で、大規模なデータが半自動的に収集で
きるようになった
（POS、web、文書、顧客データ、財務、利用者、人事…）
ならば、データがそろっているところでモデルを作ればいい
データの選別
モデル化
データ処理
いわば、データを出発点とした問題解決の科学
（人工知能、データマイニング、自然言語処理、セマンティックweb…）
データ中心科学の特徴
・データが整形されていない
目的がはっきりしない、あるいは異なる目的のために集められたデータを用いるため、
必要なものがすぐ取り出せるとは限らない。また、ノイズや不正確な情報も含まれうる。
・目的関数があいまい
データが情報の塊のようなものなので、そこから得られるものはやはり情報であること
が多い（知識、特徴分析といったもの）。それら情報の価値は数理的な尺度では計りにく
い。また、従来の最適化とは異なる尺度を用いることが多い。（グラフクラス、シークエ
ンス、情報量、隣接性、類似度、頻出度・・・）
・データが巨大で、構造を持つ
半自動で集められたデータであるので、データは通常、巨大である。しかし各
項目が持つ属性は少なく、疎である。
・データ処理は比較的簡単なものが多い
データ処理の計算は、最適化のような複雑ではなく、
組合せの検索や整形などいくつかの簡単な処理の組合せ
組合せの検索
つまり、列挙
近年の列挙研究の方針
・解が少ないようなモデルの構築
短時間で求解が終わる上に、解の解析にかかる時間も短くなる
－パスの代わりに最短パス
－クリークの代わりに極大クリーク
・入力データは巨大だが、解は多くない問題を短時間で解く
－パワー則や疎性の利用
－計算オーダーの減少と再帰構造の良質化
アルゴリズムの性能の向上：標準的な PC で
・素朴なアルゴリズムでクリークを列挙  100年以上
・洗練されたアルゴリズムで極大クリーク  2時間程度
(スループット：秒速10万個）
応用事例で実際に使える技術が出てきている
列挙モデルの難しさ
・組合せ的に選択可能な箇所があると、解数が爆発
例） 2点を結ぶパス
 最短路のみを列挙すれば、回避できうる
例）グラフのクリーク
大きなクリーク
 極大クリークのみを列挙すれば、回避できうる
極大・極小なもの、代表者をいかに選ぶかが重要
列挙アルゴリズムの難しさ
・解は多いが、総当りは非効率
列挙は解が指数個存在するので、ほぼ全ての組合せが解になりうる
 総当り的な検索が計算量の意味で最適
例） 2点間を結ぶパスは指数個ありうる
2点間を結ぶパスは、枝の組合せ全てより指数分の１である
指数個解のある問題は、現実的には解く意味がない
ボトルネック＝解の個数＝出力の時間
 解が少なければ速く、解が多ければ遅いアルゴリズムが望ましい
－解１つあたりの計算時間が短い（定数）
－ 1秒あたりの出力数が大きい（スループット）
効率的な探索が重要
例題） (3,2) から１つ、(9,3,5) から1つ、(4,1,3) から１つ、
(0,7,1) から１つ、合計4つの数字を選んでできる組合せの
中で、合計が10以下のものを求める（予算10以下の組合せ）
4
1
3
全ての組合せより
0
7
1
0
7
1
0
7
1
はるかに少ない
9 3,9,4,0 3,9,4,7 3,9,4,1 3,9,1,0 3,9,1,7 3,9,1,1 3,9,3,0 3,9,3,7 3,9,3,1
3 3 3,3,4,0 3,3,4,7 3,3,4,1 3,3,1,0 3,3,1,7 3,3,1,1 3,3,3,0 3,3,3,7 3,3,3,1
5 3,5,4,0 3,5,4,7 3,5,4,1 3,5,1,0 3,5,1,7 3,5,1,1 3,5,3,0 3,5,3,7 3,5,3,1
9 2,9,4,0 2,9,4,7 2,9,4,1 2,9,1,0 2,9,1,7 2,9,1,1 2,9,3,0 2,9,3,7 2,9,3,1
2 3 2,3,4,0 2,3,4,7 2,3,4,1 2,3,1,0 2,3,1,7 2,3,1,1 2,3,3,0 2,3,3,7 2,3,3,1
5 2,5,4,0 2,5,4,7 2,5,4,1 2,5,1,0 2,5,1,7 2,5,1,1 2,5,3,0 2,5,3,7 2,5,3,1
いかに効率よい探索ルートを作り、短時間で移動するかが課題
頻出パターンの定義と応用
データベースを分析したい
・データベース構築と検索は、もうできるようになった
（絞込みや、あいまい検索はまだ改良の余地があるけど）
・より詳しくデータを解析するために、データの特徴を捉えたい
各種統計量（データベースの大きさ、密度、項目に現れる属性値
の総計、分布）よりも、深い解析がしたい
 組合せ（パターン）的な構造に注目
（どういう組合せ（パターン）が
どれくらい入っているか）
・組合せ・パターンの個数は指数なの
で、全てを尽くすのは効率的でない
 多く現れるものだけに注目
データベース
実験1 実験2 実験3 実験4
●
▲
▲
●
▲
●
●
▲
●
●
●
▲
●
▲
●
●
●
▲
●
●
▲
▲
▲
▲
実験結果
ATGCGCCGTA
TAGCGGGTGG
TTCGCGTTAG
GGATATAAAT
GCGCCAAATA
ATAATGTATTA
TTGAAGGGCG
ACAGTCTCTCA
ATAAGCGGCT
ゲノム情報
頻出パターンの列挙
・データベースの中に多く現れるパターンを全て見つける問題を
頻出パターン列挙（あるいは発見、マイニング）問題という
データベース：トランザクション、ツリー、グラフ、多次元ベクトル
パターン：部分集合、木、パス・サイクル、グラフ、図形
データベース
実験1 実験2 実験3 実験4
●
▲
▲
●
▲
●
●
▲
●
●
●
▲
●
▲
●
●
●
▲
●
●
▲
▲
▲
▲
実験結果
頻出する
パターンを抽出
ATGCGCCGTA
TAGCGGGTGG
TTCGCGTTAG
GGATATAAAT
GCGCCAAATA
ATAATGTATTA
TTGAAGGGCG
ACAGTCTCTCA
ATAAGCGGCT
ゲノム情報
・実験1● ,実験3 ▲
・実験2● ,実験4●
・実験2●, 実験3 ▲, 実験4●
・実験2▲ ,実験3 ▲
．
．
．
・ ATGCAT
・ CCCGGGTAA
・ GGCGTTA
・ ATAAGGG
．
．
．
研究の歴史
・頻出パターン発見問題はデータマイニングの基礎的な問題
 星の数ほどの論文がある（Google Scholarで5000件）
・ 1990年代から、「大きなデータから知識を得たい」という
スローガンの元、研究されている
 「巨大データを扱うこと」を前提としている
・ 1990年ごろ集合をパターンとしたものから始まり、
極大なもの、飽和集合、誤差つき．．．とバリエーションができ、
パターンの種類も、集合から文字列、文字シークエンス、集合
シークエンス、パス、ツリー、グラフ．．．
と増えてきている
アルゴリズム研究の歴史
・アルゴリズム的には
－ 1994年 Agrawal らの apriori （解の大きさごとに解候補を
生成してからデータベースをスキャンして頻出度を計算）
－ 1998年 Bayardo のバックトラック
－ 1998年 Pasquir らによる飽和パターンの提唱
－ 2001年 Burdick らによる MAFIA （データをビット列で格納して、
演算を高速化）
－ 2002年 Zakiによる CHARM （枝刈りを利用した飽和集合列挙）
－ 2002年牧野らによる、極大パターンの列挙の困難性の証明
－ 2003年有村宇野による LCM
（初の多項式時間飽和集合列挙アルゴリズム）
応用：バスケット分析
・スーパーなどの小売店舗で、同時に購入される事の多い品物
の組を知りたい
・客が購入した品目  トランザクション
・品目の組で、多くの客が購入したもの
 多くのトランザクションに含まれるアイテム集合
 （あるθに対する）頻出集合
● 牛乳、弁当
「おむつとビールの組合せが良く売れる」
という発見が有名
● お茶、弁当
● おにぎり、雑誌
● はさみ、のり
● ラーメン、はし
● こっぷ、皿
● 弁当、おにぎり
．．．
応用：データベースの比較
・２つのデータベースが、意味的にどの程度似ているか知りたい
 大きさの違い、ノイズは無視したい
・各アイテム、属性などの総数だけでは、組合せがわからない
・組合せを細かく見ると、ノイズに振り回される
頻出集合を列挙することで、
組合せ的な特徴を比較できる
データ
ベース
データ
ベース
・いろいろな言語の辞書データ
・異なる種のゲノムデータ
・文書集合の単語データ（新聞のデータ、雑誌のデータなど）
・顧客のデータ
応用：分類ルール、特性の発見
・データの特徴を現す規則、あるいは正例・負例を分類するような
規則が知りたい（A,B,C が含まれている、A,B が含まれれば、C
が含まれる、など）
・多く現れる組合せを用いないと、仮定部分を満たすものが少なく、
ルールとして意味がない
・組合せを細かく見ると、ノイズに振り回される
頻出集合を仮定に用いることで、
信頼度の高いルールを
効率良く見つけられる
データ
ベース
正例
・実験データ
・利用者履歴データ、マーケッティング
データ
ベース
負例
多く現れる  頻出する
多く現れるものを見つけるために、多く現れるとは何か、を決める
・データベースが項目の集まりだとする
・パターンに対して、そのパターンを含む項目を出現という
・出現の数（頻出度）が閾値より大きければ、良く現れるとする
（含む、の定義は、集合で行ったり、文字列の
包含、グラフの埋め込みなどで定義する）
パターン
{A,C,D}
XYZ
項目
{A,B,C,D,E}
AXccYddZf
トランザクションデータベース
パターンとして、集合を考える
トランザクションデータベース：
各トランザクション T がアイテム集合 E の部分集合
1,2,5,6,7
になっているようなデータベース
2,3,4,5
つまり、 T , ∀T ∈T , T ⊆ E
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} }
{2,7,9}の出現集合
＝ { {1,2,5,6,7,9},
{1,2,7,8,9},
{2,7,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}
与えられたトランザクションデータベースと最小サポートθ
に対して、頻出集合を全て見つける問題を考える
頻出集合の列挙
頻出パターンの単調性
・頻出パターンの部分パターンは頻出
 単調性が成り立つ
111…1
 バックトラック法を適用できる
頻出
000…0
頻出集合であるかどうかのチェック
はO(||T ||) 時間、最高 n 方向に登る
 １つあたり O(||T ||n) 時間
1,2,3,4
1,2,3 1,2,4
1,2
1,3
1,3,4
1,4
2,3,4
2,3
2,4
3,4
2
3
4
多項式時間ではあるが、
||T || も n も大きすぎる
1
φ
末広がり性の利用
・パターン X の出現集合を T とする
・ X＋e の出現は X を含む（＝ X の出現）
T の中で e を含むもの  X＋e の出現集合
・出現集合を更新すれば、
データ全体を見なくて良い
・反復が深くなると、見るべき出現集合は小さくなる
 反復が深くなるにつれ、計算時間は短くなる
末広がり性
・バックトラックは、各反復で複数の再帰呼び出しをする
 計算木は、下に行くほど大きくなる
 計算時間を支配するのは一番下の数レベル
計算時間長
・・・
計算時間短
ほぼ全ての反復が短時間で終了
（1秒間におよそ100万個）
多くの列挙アルゴリズムが似たような再帰構造を持つので、
下のレベルの仕事を上のレベルがやれば、同様の改良ができる
最小サポートが大きい場合も
・ θが大きいと、下のレベルでも多くの出現を見ることになる
 末広がり性による高速化はいまひとつ
・データベースの縮約により、下のレベルの高速化をはかる
（１）前回追加したアイテムより小さいアイテムは消す
（２）現在の出現集合からできるデータベースの中で、頻出になって
いないアイテムは消去する
（再帰呼び出しの中で加えられることが無いから）
（３）まったく同一のトランザクションは、１つにまとめる
１
・実データだと、下のほうのレベルでは
だいたい大きさが定数になる
θが小さいときと速度の大きな差はない
１
３
２
２
６
４
７
４
３
２
５
４
３
１
４
４
４
５
６
７
６
７
６
７
頻出集合の問題点
・面白い頻出集合を見つけようとすると、θを小さくする必要がある
 大量の頻出集合が出てくる
・情報を失わずに、頻出集合的な、数の少ないものを
見つけるようにモデルを変えたい
111…1
１．極大頻出集合：
他の頻出集合に含まれない頻出集合
２．飽和集合：
出現集合が等しいものの中で極大なもの
000…0
極大頻出集合と飽和集合の例
・頻出集合を出現集合で分類
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}
{1,7}
{1,9}
{2,7}
{2,9}
{1,7,9}
{9}
{7,9}
{2,7,9}
極大頻出集合と飽和集合
極大頻出集合
・多項式時間で列挙できるかどうか、未解決
・クリークと同じように枝刈りをすると、高速に列挙できる
・数が少ないがθによる解のぶれが大きい
飽和集合
・逆探索という探索手法で多項式時間列挙可能
・離散アルゴリズムと末広がり性を用いて、高速列挙可能
・出現の意味で情報の損失がない
・ノイズが多いと出現集合が等しいものが少なくなり、
解の減少効率が悪くなる
両者とも、１つあたりほぼ定数時間、1秒間に1～10万個
飽和集合の列挙手法
・頻出集合列挙ベース
－頻出集合列挙アルゴリズムをベースに、多少無駄な計算を
省く
－飽和集合のよさが出ない。計算時間の改善も少ない
・保存＋枝狩り
－見つけた解を保存し、それを用いて無駄な分枝を刈る
－計算速度はまあまあ
－解保存のためにメモリを使用し、それがひとつのネック
・逆探索＋データベース縮約
－計算効率が良い
－解保存用のメモリが不要
（LCM）
飽和集合の隣接関係
・飽和集合から、添え字の大きい順に要素を抜いていく
・どこかで出現集合が大きくなる
・その出現集合の飽和集合を求める
・こうして求めた飽和集合を、親とする（一意的に定まる）
・親の頻出度は必ず真に大きいので、親子関係は非巡回的
 親子関係は有向根付き木を導出する
逆探索
親子関係は有向根付き木を導出する
この木を深さ優先探索すれば全ての解を見つけられる
・探索には、子供を見つけるアルゴリズムがあれば十分
・子供が１つあたり多項式時間で見つかれば、全体も多項式時間
（親に要素を１つ加えて極大をとった飽和集合が子供になる）
非巡回的な親子関係と、子供を見つける多項式時間アル
ゴリズムがあれば、なんでも多項式時間列挙ができる
親子関係の例
・データベースの全ての
飽和集合とその親子関係
φ
2
1,2,5,6,7,9
2,3,4,5
T ＝ 1,2,7,8,9
1,7,9
2,7,9
2
出現集合が隣接
親子関係
7,9
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
実験結果
・実データからとった、著名なベンチマーク問題でテスト
・項目数は 1万～ 100万
・属性数は 1000 ～ 1万
Pen. M 1GHz
256MB メモリ
データ種別
POS
クリック
Web閲覧
顧客
単語
項目数
51万
99万
7.7万
8.8万
6万
データサイズ
330万
800万
31万
90万
23万
出力数
460万
110万
53万
37万
100万
計算時間
80 秒
34 秒
3秒
3秒
6秒
単純なスキャンは1秒で100パターン程度
計算機実験： FIMI04
・ FIMI: Frequent Itemset Mining Implementations
－ ICDM (International Conference on Data Mining) サテライト
ワークショップで、頻出／頻出飽和／極大頻出集合列挙のプ
ログラムコンテストを行った。2回目。3回目はなし
・去年は15、今年は8個の投稿があった
ルール：
－ファイルを読み、列挙してファイルに書くこと
－ time コマンドで時間を計測（メモリも他のコマンドで計測）
－ CPUを制御する命令（パイプラインなど）は使用禁止
計算機実験： FIMI04
・計算機環境：CPU、メモリ: Pentium4 3.2GHz、1GB RAM
OS、言語、コンパイラ: Linux 、C言語、gcc
・データセット：
－実データ：疎、アイテム数大
－機械学習用データ：密、アイテム数小、規則的
－人工データ：疎、アイテム数大、ランダム
－密な実データ：超密、アイテム数小
LCM（宇野有村清見）、見事優勝
賞状と賞品
賞品は {ビール, 紙おむつ}
“Most Frequent Itemset” だそうです
実データ（超疎）
BMS-WebView2
飽和：LCM
頻出：LCM
極大：afopt
実データ（疎）
kosarak
飽和：LCM
頻出：nonodrfp＆LCM
極大： LCM
機械学習データ
pumsb
頻出：いろいろ
飽和：LCM＆DCI-closed
極大： LCM＆
FP-growth
密な実データ
accidents
飽和：LCM＆FP-growth
頻出：nonodrfp
＆FP-growth
極大： LCM
＆FP-growth
メモリ使用量
pumsb
頻出
飽和
極大
より複雑な構造を持つ頻出パターン
時系列データ
・時系列データを解析するには、項目の出現する順番が重要
－「始まり ⇒ 終り」と「終り⇒始まり」では意味がまったく違う
・文字列も同様
ゲノムデータ： ATGCGGCTGAGGCTGTTTT…
文書データ：今日午前5時新宿区西新宿の交差点でトラックが…
購買履歴データ： {ビデオ}、{テープ,CD-R}、{デジカメ,電池,ケーブ
ル}、{インク}…
・「部分文字列」では、パターンが少なすぎる
（見えているもの、しか見つからない）
 シークエンスを見つける
シークエンス
・シークエンス：データ列に順番を変更せずに現れる要素列
例） ABCDEAB に対して、 ACEA は部分シークエンスだが、
BBA は部分シークエンスでない
・アイテム集合シークエンス：アイテム集合の列の中に、順番を変
更せず現れるアイテムセットの列
例） {ビデオ}、{テープ,CD-R}、{デジカメ,電池,ケーブル}、{インク}
{ビデオ}、{デジカメ,ケーブル} は部分アイテム集合シークエンス
{インク}、{ケーブル} は部分アイテム集合シークエンスではない
頻出（アイテム集合）シークエンス列挙問題が研究されている
（大体同じテクニックで、同じような計算時間で列挙できる）
文字列データ
・時系列データ、文字列データは、ときに、全体が１つの項目になっ
ているような場合がある
例）実験データ、パケットログなどのストリームデータ、染色体、など
・この場合、１つのデータの中にシークエンスが何回現れるか、を評
価する必要がある
 現れる回数、の定義が重要
ABCDEFGHABCDEABC に ABC はどのように現れるか
・左端がどの位置に現れるかで評価
頻出シークエンスマイニング
・トランザクションデータの各項目をソートすると、頻出集合問
題は頻出シークエンス問題に帰着される
ABCD
 シークエンスのほうが難しい
ABD
 極大シークエンスの列挙は
ACE
計算量の意味では難しい
BDE
・文字列データ２つの包含関係は線形時間でチェック
できるので、頻出シークエンスの列挙は、バックトラックで
１つあたり多項式時間で可能
・出現が同じシークエンスの集合に、極大が
一意に存在しないので、飽和集合の導入は難しい
ABCD
ACBD
実用上の工夫
・項目が複数あり、パターンの頻出度を現れる項目数とする場合、
データベース縮約が可能なので、末広がり性から高速なアルゴリ
ズムが構築できる
 項目が１つのデータの場合は、サポートが大きいと
データの縮約ができないため、高速化できない
・データの項目がとても長い場合、あまりにも間隔のあきすぎた
データは意味が無い
 ギャップの長さの上限、ギャップの回数などに制約を与える
ABCD
EF GHI
頻出グラフマイニング
・グラフの頂点、あるいは枝にラベルがついたグラフをラベル
付きグラフと呼ぶ
－化合物
－地図
－組織図
－XML
頻出グラフマイニング：ラベルつきグラフのデータベースから、
頻出するラベル付きグラフを見つける問題
・グラフ埋め込み問題（グラフA がグラフBを部分グラフとして
含むか）がNP完全なので、計算量の意味では難しい
さて、どうしましょうか
アプローチ１：そのままがんばる
・埋め込み判定に時間がかかるのは、埋め込むグラフが大きい場
合  小さければ、なんてことはない
・実際、大きなパターンがたくさん出てこられても、困る
・埋め込み判定は力技でやり、多少時間がかかっても気にしない
ことにする
 次の問題は、候補となるパターンを如何に列挙するか
・幅優先的に、頂点数が小さいグラフから順に列挙する
（過去に作ったグラフに頂点＆枝を加え、１つ大きいグラフを作る）
・過去に作ったグラフを全て記憶し、重複を避ける
アプローチ１：そのままがんばる (2)
・重複の判定は、実は面倒
 グラフ同型性判定を解かなければいけない
 しかも、過去に生成した全てのグラフと同型性判定をすると、
大変な時間がかかる
・各グラフを、「標準型」の文字列に変換して、保存する
 過去に生成したかどうかを、文字列検索でできる
・「標準型」は、そのグラフを表す、辞書順
最小の隣接行列をベクトル化したもの
多少遅いが、列挙できる
１
１
１
１
１
１
１
１
１
１
１
１
列挙の困難さ
・重複の判定が効率よくなると、次のボトルネックは候補の生成
部分  ひとつの候補が複数のルートで生成されると、計算の
無駄がある
・深さ優先木を生成し、それに肉付けする形でのみ、生成を行う
・２つの頻出グラフを重なりがあるようにマージして、
より大きな候補を作る
 頻出グラフの部分グラフは頻出、という性質を使う
だいぶ速くなるが、メモリの問題は残る
アプローチ２：クラスを限定する
・グラフマイニングは、埋め込み＆重複検査が難しい
 これらが簡単にできるクラスに限定する
・たとえば、
－パターンがパス・サイクル
－データベースの各項目が木
・頻出パターンの生成が、深さ優先的にできるようになる
・埋め込みに関しては、生成する元となったパターンの埋め込み
の位置を覚えておけば、楽にできる（位置が指数になる可能性は
あるが）
頻出順序木列挙
・各項目が順序木になっているデータベースから、
頻出する順序木を見つける
順序木：子どもの順番が陽に指定された根付き木
≠
≠
同型だが、子どもの順序が異なる
順序木の列挙
親の定義：
一番右の葉を除去す
る
 子どもは一番右に
葉をつけたもの
順序木  無順序木
・子どもの順序が異なることに意味があまり無い場合、無順序木
（普通の意味での根付き木）を列挙したい
・子根付き木は、単に右端に葉を追加するだけだと、
重複ができてしまう。
重複を回避するた
め、標準形を用いる
順序木  無順序木 (2)
（順序木の）深さ列：左を優先して深さ優先探索し、訪れた頂点の
深さ＆ラベルをpre-orderで並べたもの
・２つの順序木が順番も含めて同型 ⇔ 深さ列が等しい
・子供の順序を入れ替えていろいろな木が作れる。その中で最大の
深さ列を持つものを left heavy embedding と呼ぶ（これが代表）
（各頂点の子供を子孫の深さ列の大きさでソート）
・２つの無順序木が同型 ⇔ left heavy embedding が等しい
0,1,2,3,3,2,2,1,2,3
0,1,2,2,3,3,2,1,2,3
0,1,2,3,1,2,3,3,2,2
標準形の親子関係
・ left-heavy embedding T の親： T の最も右の葉を取った木
 親も left-heavy embedding
T
0,1,2,3,3,2,1,2,3,2,1
親
0,1,2,3,3,2,1,2,3,2
親の親
0,1,2,3,3,2,1,2,3
・Left heavy embedding の子は、最右パスの右に、
コピー深さ以浅に葉を付けたものになる
 各頂点の子の深さ列の重みが逆転しない
 コピー深さは O(1) で更新できる
無順序木の列挙
・順序木の列挙木の
枝刈りをしたものに対応
無順序木の列挙：その他
・データが木である場合、順序木・無順序木の埋め込み判定は、
親が埋め込み可能だった場所の、右端の葉の位置のみを覚え
ておけば十分
 高速にチェックできる上、メモリが必要ない
・順序木・無順序木は、同一の出現を持つパターン達の極大が
唯一とならない
 飽和パターンを導入しても、ぱっとしない
逆探索の例：フロアプラン
親の定義：
左上の部屋の
右か下の壁をスライドして
左上の部屋をつぶす
（長方形による部屋分け）
参考文献など
・頻出集合およびその応用 (’90～) 星の数ほど
“frequent pattern”、”frequent itemset” で検索すると出てくる
・極大頻出集合およびその応用 (’90～) やはり多い
“maximal frequent itemset” などで検索すると出てくる
・ pasquerらのアルゴリズム (‘99) 飽和集合の導入
・宇野らのアルゴリズムLCM (‘04) 現在最速のアルゴリズム
・実装 LCM: (Linear time Closed itemset Miner)
http:research.nii.ac.jp/~uno/
・レポジトリ（実装、論文、比較実験の数々）
http://fimi.cs.helsinki.fi/
宇野のHP
参考文献など (2)
・鷲尾らのアルゴリズム（’01 ）グラフマイニングの先駆け
・中野先生（群馬大）の列挙アルゴリズム
順序木・極大三角形分割・フロアプランなど
・中野・宇野・有村（’03～）順序木・無順序木の多項式時間
頻出列挙
まとめ
・データ中心の科学：あいまいな目的に対する列挙的なアプローチ
・頻出パターンは、データの組合せ的な特徴を捉えることができる
・出力数依存アルゴリズム、解数の小さいモデルの重要性
・逆探索による効率な探索
・末広がり性の利用が大規模データに対する高速処理の鍵
今後の課題
・幾何学的なデータ＆パターン
・エラーをゆるした包含関係の導入
・飽和集合の他のパターンへの拡張
・多項式時間列挙の難しいパターンの、実用的解決

Download Report