頻出集合発見問題に対する アルゴリズム技術

Presentation on theme: "頻出集合発見問題に対する アルゴリズム技術"— Presentation transcript:

1 頻出集合発見問題に対する アルゴリズム技術
宇野 毅明 （情報学研究所） 有村 博紀 （北海道大学） 中野 眞一 （群馬大学） 佐藤 寛子 （情報学研究所） 佐藤 健 （情報学研究所） 清見 礼 （JAIST） 2007年2月28日 コンピューテーション研究会

2 列挙とその応用の基本

3 列挙問題： 与えられた問題の解を全て重複なく見つけ出す問題 ・ グラフの2点間を結ぶパス ・ 数の合計の可能性 ．．．
列挙問題とは何でしょう 列挙問題： 与えられた問題の解を全て重複なく見つけ出す問題 ・ グラフの2点間を結ぶパス ・ 数の合計の可能性 ．．． A B ・ 1,3,5,8,14 の中から数字を 選んでできる合計を列挙せよ ・頂点 A と B を結ぶパスを列挙せよ 解） … 解） 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 情報科学の基礎的な問題 近年、広く使われ始めている

4 ・ 最適化は問題の一部分を見つける  列挙は問題の全ての部分を見つける
列挙は多面的 ・ 最適化は問題の一部分を見つける 　列挙は問題の全ての部分を見つける 列挙では解の全てを見つけるため、 問題の構造を全体的に把握することができる 「最適ではないが、役に立つ解」を、見つけ損なわない 問題の構造を調べたいとき、数理的にクリアでない 目的関数で解を得たいときに、列挙が有効

5 あいまいな目的 web ページの検索 （見つけたいページを見つける） ① キーワードを指定 ② キーワードを含むページを列挙
　① キーワードを指定 　② キーワードを含むページを列挙 　③ 見つかったページを実際に検証 Enumerations from databases solve many problems and give new knowledge キーワード検索 候補 Enumerations from databases solve many problems and give new knowledge 実際にページ を見て検証 Web ページ データベース ・ 数理的な部分をコンピュータで解く　（候補の列挙） ・ 残りはユーザに任せる　（候補の絞込み）

6 列挙 モデルから見ると 列挙は中間に位置する ・ シンプルかつ小規模なら、最適化が有効 （きれいな問題の良質な解を１つ求める）
　　　（きれいな問題の良質な解を１つ求める） ・ 複雑あるいは大規模ならばシミュレーションが有効 　　　（複雑・大規模な問題の多数の解を見つける） モデルが 列挙 列挙は中間に位置する 良質な解を多数見つける 最適化 シミュレ ーション シンプルなモデル をじっくり解く 複雑なモデル を粗く解く 線形計画 局所探索 組合せ最適化 アドホック ネットワーク 物理現象の計算

7 列挙研究の歴史 計算機パワーの増大 応用の発達 1960 1990 2000 実用の可能性が発現 黎明期： 基礎問題と計算量
応用で使われ始める （データマイニングなど） 1960 1990 2000 黎明期： 基礎問題と計算量 解が多さで、実用の観点はなし 逆探索 の出現 実用的なアルゴ リズムの発達 （疎な構造の利用、 巨大データ処理等） 極大元列挙法の出現 複雑な構造に対する列挙法の発達

8 典型的なOR的なアプローチは、データ収集でつまづくことが多い
問題発見 定式化 解法（最適化） 典型的な OR（＋数理計画） 的アプローチ データ収集 （システム構築） 求解 運用 できたモデルを実際に使う ここがボトルネック であることが多い その一方で、データが あふれている場所もある

9 ・ 近年、IT技術の発達で、大規模なデータが半自動的に収集できるようになった （POS、web、文書、顧客データ、財務、利用者、人事…）
データ中心の科学 ・ 近年、IT技術の発達で、大規模なデータが半自動的に収集できるようになった 　　（POS、web、文書、顧客データ、財務、利用者、人事…） ならば、データがそろっているところでモデルを作ればいい データの選別 モデル化 データ処理 いわば、データを出発点とした問題解決の科学 （人工知能、データマイニング、自然言語処理、セマンティックweb…）

10 データ中心科学の特徴 つまり、列挙 組合せの検索
・ データが整形されていない 　目的がはっきりしない、あるいは異なる目的のために集められたデータを用いるため、必要なものがすぐ取り出せるとは限らない。また、ノイズや不正確な情報も含まれうる。 ・ 目的関数があいまい 　データが情報の塊のようなものなので、そこから得られるものはやはり情報であることが多い（知識、特徴分析といったもの）。それら情報の価値は数理的な尺度では計りにくい。また、従来の最適化とは異なる尺度を用いることが多い。（グラフクラス、シークエンス、情報量、隣接性、類似度、頻出度・・・） ・ データが巨大で、構造を持つ 半自動で集められたデータであるので、データは通常、巨大である。しかし各項目が持つ属性は少なく、疎である。 ・ データ処理は比較的簡単なものが多い データ処理の計算は、最適化のような複雑ではなく、 組合せの検索や整形などいくつかの簡単な処理の組合せ つまり、列挙 組合せの検索

11 応用事例で実際に使える技術が出てきている
近年の列挙研究の方針 ・ 解が少ないようなモデルの構築 　短時間で求解が終わる上に、解の解析にかかる時間も短くなる 　　 － パスの代わりに最短パス 　　 － クリークの代わりに極大クリーク ・ 入力データは巨大だが、解は多くない問題を短時間で解く 　　 － パワー則や疎性の利用 　　 － 計算オーダーの減少と再帰構造の良質化 アルゴリズムの性能の向上： 標準的な PC で ・ 素朴なアルゴリズムでクリークを列挙　 100年以上 ・ 洗練されたアルゴリズムで極大クリーク  2時間程度 　　　(スループット：　秒速10万 個） 応用事例で実際に使える技術が出てきている

12 極大・極小なもの、代表者をいかに選ぶかが重要
列挙モデルの難しさ ・ 組合せ的に選択可能な箇所があると、解数が爆発 例）　2点を結ぶパス  最短路のみを列挙すれば、回避できうる 例）　グラフのクリーク  極大クリークのみを列挙すれば、回避できうる 大きなクリーク 極大・極小なもの、代表者をいかに選ぶかが重要

13 指数個解のある問題は、現実的には解く意味がない
列挙アルゴリズムの難しさ ・ 解は多いが、総当りは非効率 　列挙は解が指数個存在するので、ほぼ全ての組合せが解になりうる  総当り的な検索が計算量の意味で最適 　例）　2点間を結ぶパスは指数個ありうる 　　　2点間を結ぶパスは、枝の組合せ全てより指数分の１である 指数個解のある問題は、現実的には解く意味がない ボトルネック ＝ 解の個数 ＝ 出力の時間  解が少なければ速く、解が多ければ遅いアルゴリズムが望ましい － 解１つあたりの計算時間が短い（定数） － 1秒あたりの出力数が大きい（スループット）

14 いかに効率よい探索ルートを作り、短時間で移動するかが課題
効率的な探索が重要 例題） (3,2) から１つ、(9,3,5) から1つ、(4,1,3) から１つ、 (0,7,1) から１つ、合計4つの数字を選んでできる組合せの 中で、合計が10以下のものを求める　（予算10以下の組合せ） 4 1 3 7 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,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 2 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,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 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 全ての組合せより はるかに少ない いかに効率よい探索ルートを作り、短時間で移動するかが課題

15 頻出パターンの定義と応用

16 データベースを分析したい ・ データベース構築と検索は、もうできるようになった （絞込みや、あいまい検索はまだ改良の余地があるけど）
　（絞込みや、あいまい検索はまだ改良の余地があるけど） ・ より詳しくデータを解析するために、データの特徴を捉えたい 各種統計量（データベースの大きさ、密度、項目に現れる属性値の総計、分布）よりも、深い解析がしたい  組合せ（パターン）的な構造に注目 （どういう組合せ（パターン）が どれくらい入っているか） ・ 組合せ・パターンの個数は指数なの で、全てを尽くすのは効率的でない  多く現れるものだけに注目 データベース 実験1 実験2 実験3 実験4 　● 　▲ ATGCGCCGTA TAGCGGGTGG TTCGCGTTAG GGATATAAAT GCGCCAAATA ATAATGTATTA TTGAAGGGCG ACAGTCTCTCA ATAAGCGGCT 実験結果 ゲノム情報

17 頻出パターンの列挙 ・ データベースの中に多く現れるパターンを全て見つける問題を 頻出パターン列挙（あるいは発見、マイニング）問題という
　データベース： トランザクション、ツリー、グラフ、多次元ベクトル 　パターン： 部分集合、木、パス・サイクル、グラフ、図形 データベース 頻出する パターンを抽出 ・ 実験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 　　　　． 実験結果 ゲノム情報

18 研究の歴史 ・ 頻出パターン発見問題はデータマイニングの基礎的な問題
 星の数ほどの論文がある （Google Scholarで5000件） ・ 1990年代から、「大きなデータから知識を得たい」という 　　スローガンの元、研究されている  「巨大データを扱うこと」を前提としている ・ 1990年ごろ集合をパターンとしたものから始まり、 極大なもの、飽和集合、誤差つき．．．とバリエーションができ、 パターンの種類も、集合から文字列、文字シークエンス、集合シークエンス、パス、ツリー、グラフ．．． と増えてきている

19 アルゴリズム研究の歴史 ・ アルゴリズム的には － 1994年 Agrawal らの apriori （解の大きさごとに解候補を
生成してからデータベースをスキャンして頻出度を計算） － 1998年 Bayardo のバックトラック － 1998年 Pasquir らによる飽和パターンの提唱 － 2001年 Burdick らによる MAFIA （データをビット列で格納して、 　　　演算を高速化） － 2002年 Zakiによる CHARM （枝刈りを利用した飽和集合列挙） － 2002年 牧野らによる、極大パターンの列挙の困難性の証明 － 2003年 有村宇野による LCM 　　　　（初の多項式時間飽和集合列挙アルゴリズム）

20 応用：バスケット分析 ・ スーパーなどの小売店舗で、同時に購入される事の多い品物の組を知りたい ・ 客が購入した品目  トランザクション
・ 客が購入した品目  トランザクション ・ 品目の組で、多くの客が購入したもの  多くのトランザクションに含まれるアイテム集合  （あるθに対する）頻出集合 ● 牛乳、弁当 ● お茶、弁当 ● おにぎり、雑誌 ● はさみ、のり ● ラーメン、はし ● こっぷ、皿 ● 弁当、おにぎり 　　　．．． 「おむつとビールの組合せが良く売れる」 という発見が有名

21 応用：データベースの比較 ・ ２つのデータベースが、意味的にどの程度似ているか知りたい  大きさの違い、ノイズは無視したい
・ 各アイテム、属性などの総数だけでは、組合せがわからない ・ 組合せを細かく見ると、ノイズに振り回される データ ベース 頻出集合を列挙することで、 組合せ的な特徴を比較できる ・ いろいろな言語の辞書データ ・ 異なる種のゲノムデータ ・ 文書集合の単語データ（新聞のデータ、雑誌のデータなど） ・ 顧客のデータ

22 応用：分類ルール、特性の発見 ・ データの特徴を現す規則、あるいは正例・負例を分類するような規則が知りたい （A,B,C が含まれている、A,B が含まれれば、C が含まれる、など） ・ 多く現れる組合せを用いないと、仮定部分を満たすものが少なく、ルールとして意味がない ・ 組合せを細かく見ると、ノイズに振り回される 頻出集合を仮定に用いることで、 信頼度の高いルールを 効率良く見つけられる データ ベース データ ベース 正例 ・ 実験データ ・ 利用者履歴データ、マーケッティング 負例

23 多く現れる  頻出する 多く現れるものを見つけるために、多く現れるとは何か、を決める ・ データベースが項目の集まりだとする
多く現れる  頻出する 多く現れるものを見つけるために、多く現れるとは何か、を決める ・ データベースが項目の集まりだとする ・ パターンに対して、そのパターンを含む項目を出現という ・ 出現の数（頻出度）が閾値より大きければ、良く現れるとする （含む、の定義は、集合で行ったり、文字列の 包含、グラフの埋め込みなどで定義する） パターン XYZ {A,C,D} 項目 AXccYddZf {A,B,C,D,E}

24 トランザクションデータベース パターンとして、集合を考える トランザクションデータベース：
各トランザクション 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 ＝ 実際のデータは、大きくて疎なものが多い パワー則、スモールワールドが成り立つ

25 集合の出現と頻出度 集合K に対して： K の出現： K を含むT のトランザクション
K の出現集合 I(K)：　 K を含むT のトランザクション全ての集合 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 T ＝ 　{2,7,9}の出現集合 ＝　{ {1,2,5,6,7,9}, 　　　　{1,2,7,8,9}, {2,7,9} }

26 与えられたトランザクションデータベースと最小サポートθに対して、頻出集合を全て見つける問題を考える
・ 頻出集合：T の定数θ個以上のトランザクションに含まれる集合 　（頻出度がθ以上の集合）（ θを最小サポートとよぶ） 例） データベースT の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 T ＝ 与えられたトランザクションデータベースと最小サポートθに対して、頻出集合を全て見つける問題を考える

27 頻出集合の列挙

28 頻出パターンの単調性 ・ 頻出パターンの部分パターンは頻出 111…1  単調性が成り立つ  バックトラック法を適用できる
頻出集合であるかどうかのチェック はO(||T ||) 時間、最高 n 方向に登る  １つあたり O(||T ||n) 時間 頻出 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 多項式時間ではあるが、 ||T || も n も大きすぎる

29 末広がり性の利用 ・ パターン X の出現集合を T とする ・ X＋e の出現は X を含む（＝ X の出現）
T の中で e を含むもの  X＋e の出現集合 ・ 出現集合を更新すれば、 　　　データ全体を見なくて良い ・ 反復が深くなると、見るべき出現集合は小さくなる  反復が深くなるにつれ、計算時間は短くなる

30 ・ バックトラックは、各反復で複数の再帰呼び出しをする  計算木は、下に行くほど大きくなる  計算時間を支配するのは一番下の数レベル
末広がり性 ・ バックトラックは、各反復で複数の再帰呼び出しをする 　 計算木は、下に行くほど大きくなる  計算時間を支配するのは一番下の数レベル ・・・ 計算時間長 計算時間短 ほぼ全ての反復が短時間で終了 （1秒間におよそ100万個） 多くの列挙アルゴリズムが似たような再帰構造を持つので、 下のレベルの仕事を上のレベルがやれば、同様の改良ができる

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

32 頻出集合の問題点 ・ 面白い頻出集合を見つけようとすると、θを小さくする必要がある  大量の頻出集合が出てくる
 大量の頻出集合が出てくる ・ 情報を失わずに、頻出集合的な、数の少ないものを 　　　見つけるようにモデルを変えたい １． 極大頻出集合： 他の頻出集合に含まれない頻出集合 ２． 飽和集合： 出現集合が等しいものの中で極大なもの 111…1 000…0

33 極大頻出集合と飽和集合の例 ・ 頻出集合を出現集合で分類 ３つ以上に含まれるもの {1} {2} {7} {9} {1,7} {1,9}
{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 T ＝ 頻出飽和集合 極大頻出集合

34 両者とも、１つあたりほぼ定数時間、1秒間に1～10万個
極大頻出集合と飽和集合 極大頻出集合 ・ 多項式時間で列挙できるかどうか、未解決 ・ クリークと同じように枝刈りをすると、高速に列挙できる ・ 数が少ないがθによる解のぶれが大きい 飽和集合 ・ 逆探索という探索手法で多項式時間列挙可能 ・ 離散アルゴリズムと末広がり性を用いて、高速列挙可能 ・ 出現の意味で情報の損失がない ・ ノイズが多いと出現集合が等しいものが少なくなり、 　　　解の減少効率が悪くなる 両者とも、１つあたりほぼ定数時間、1秒間に1～10万個

35 飽和集合の列挙手法 ・ 頻出集合列挙ベース － 頻出集合列挙アルゴリズムをベースに、多少無駄な計算を省く
　－ 頻出集合列挙アルゴリズムをベースに、多少無駄な計算を省く 　－ 飽和集合のよさが出ない。計算時間の改善も少ない ・ 保存 ＋ 枝狩り　　 　－ 見つけた解を保存し、それを用いて無駄な分枝を刈る 　－ 計算速度はまあまあ 　－ 解保存のためにメモリを使用し、それがひとつのネック ・ 逆探索　＋　データベース縮約　　（LCM） 　　 － 計算効率が良い 　　 － 解保存用のメモリが不要

36 飽和集合の隣接関係 ・ 飽和集合から、添え字の大きい順に要素を抜いていく ・ どこかで出現集合が大きくなる
・ その出現集合の飽和集合を求める ・ こうして求めた飽和集合を、親とする　（一意的に定まる） ・ 親の頻出度は必ず真に大きいので、親子関係は非巡回的 　 親子関係は有向根付き木を導出する

37 逆探索 親子関係は有向根付き木を導出する この木を深さ優先探索すれば全ての解を見つけられる
・ 探索には、子供を見つけるアルゴリズムがあれば十分 ・ 子供が１つあたり多項式時間で見つかれば、全体も多項式時間 （親に要素を１つ加えて極大をとった飽和集合が子供になる） 非巡回的な親子関係と、子供を見つける多項式時間アルゴリズムがあれば、なんでも多項式時間列挙ができる

38 ・ データベースの全ての 飽和集合とその親子関係
親子関係の例 ・ データベースの全ての 飽和集合とその親子関係 φ 1,7,9 2,7,9 1,2,7,9 7,9 2,5 2 2,3,4,5 1,2,7,8,9 1,2,5,6,7,9 1,2,5,6,7,9 2,3,4,5 1,2,7,8,9 1,7,9 2,7,9 2 T ＝ 出現集合が隣接 親子関係

39 ・ 実データからとった、著名なベンチマーク問題でテスト ・ 項目数は 1万 ～ 100万 ・ 属性数は 1000 ～ 1万
実験結果 ・ 実データからとった、著名なベンチマーク問題でテスト ・ 項目数は 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 秒 6 秒 単純なスキャンは1秒で100パターン程度

40 計算機実験： FIMI04 ・ FIMI: Frequent Itemset Mining Implementations
－ ICDM (International Conference on Data Mining) サテライトワークショップで、頻出／頻出飽和／極大頻出集合列挙のプログラムコンテストを行った。2回目。3回目はなし ・去年は15、今年は8個の投稿があった ルール： － ファイルを読み、列挙してファイルに書くこと － time コマンドで時間を計測（メモリも他のコマンドで計測） － CPUを制御する命令（パイプラインなど）は使用禁止

41 計算機実験： FIMI04 ・計算機環境：CPU、メモリ: Pentium4 3.2GHz、1GB RAM
OS、言語、コンパイラ: Linux 、C言語、gcc ・ データセット： 　－ 実データ： 疎、アイテム数大 　－ 機械学習用データ： 密、アイテム数小、規則的 　－ 人工データ： 疎、アイテム数大、ランダム 　－ 密な実データ： 超密、アイテム数小 LCM（宇野有村清見）、見事優勝

42 “Most Frequent Itemset” だそうです
賞状と賞品 賞品は {ビール, 紙おむつ} “Most Frequent Itemset” だそうです

43 実データ（超疎） BMS-WebView2 頻出：LCM 飽和：LCM 極大：afopt

44 実データ（疎） kosarak 頻出：nonodrfp＆LCM 飽和：LCM 極大： LCM

45 機械学習データpumsb 頻出：いろいろ 飽和：LCM＆DCI-closed 極大： LCM＆ FP-growth

46 密な実データ accidents 頻出：nonodrfp ＆FP-growth 飽和：LCM＆FP-growth 極大： LCM

47 メモリ使用量 pumsb 頻出 飽和 極大

48 より複雑な構造を持つ頻出パターン

49 時系列データ ・ 時系列データを解析するには、項目の出現する順番が重要
　－ 「始まり ⇒ 終り」 と 「終り⇒始まり」 では意味がまったく違う ・ 文字列も同様 ゲノムデータ： ATGCGGCTGAGGCTGTTTT… 文書データ： 今日午前5時新宿区西新宿の交差点でトラックが… 購買履歴データ： {ビデオ}、{テープ,CD-R}、{デジカメ,電池,ケーブル}、{インク}… ・ 「部分文字列」では、パターンが少なすぎる 　（見えているもの、しか見つからない） 　　シークエンスを見つける

50 頻出（アイテム集合）シークエンス列挙問題が研究されている （大体同じテクニックで、同じような計算時間で列挙できる）
・ シークエンス：　データ列に順番を変更せずに現れる要素列 例） ABCDEAB に対して、 ACEA は部分シークエンスだが、 BBA は部分シークエンスでない ・ アイテム集合シークエンス： アイテム集合の列の中に、順番を変更せず現れるアイテムセットの列 例） {ビデオ}、{テープ,CD-R}、{デジカメ,電池,ケーブル}、{インク} {ビデオ}、{デジカメ,ケーブル} は部分アイテム集合シークエンス {インク}、{ケーブル} は部分アイテム集合シークエンスではない 頻出（アイテム集合）シークエンス列挙問題が研究されている （大体同じテクニックで、同じような計算時間で列挙できる）

51 文字列データ ・ 時系列データ、文字列データは、ときに、全体が１つの項目になっているような場合がある
例） 実験データ、パケットログなどのストリームデータ、染色体、など ・ この場合、１つのデータの中にシークエンスが何回現れるか、を評価する必要がある  現れる回数、の定義が重要 ABCDEFGHABCDEABC に ABC はどのように現れるか ・ 左端がどの位置に現れるかで評価

52 頻出シークエンスマイニング ・ トランザクションデータの各項目をソートすると、頻出集合問題は頻出シークエンス問題に帰着される
　 シークエンスのほうが難しい 　 極大シークエンスの列挙は 　　　　計算量の意味では難しい ・ 文字列データ２つの包含関係は線形時間でチェック できるので、頻出シークエンスの列挙は、バックトラックで １つあたり多項式時間で可能 ・ 出現が同じシークエンスの集合に、極大が 一意に存在しないので、飽和集合の導入は難しい ABCD ABD ACE BDE ABCD ACBD

53 実用上の工夫 ・ 項目が複数あり、パターンの頻出度を現れる項目数とする場合、データベース縮約が可能なので、末広がり性から高速なアルゴリズムが構築できる 　 項目が１つのデータの場合は、サポートが大きいと データの縮約ができないため、高速化できない ・ データの項目がとても長い場合、あまりにも間隔のあきすぎたデータは意味が無い 　 ギャップの長さの上限、ギャップの回数などに制約を与える ABCD EF GHI

54 頻出グラフマイニング ・グラフの頂点、あるいは枝にラベルがついたグラフをラベル付きグラフと呼ぶ －化合物 －地図 －組織図 －XML
頻出グラフマイニング： ラベルつきグラフのデータベースから、頻出するラベル付きグラフを見つける問題 ・ グラフ埋め込み問題（グラフA が グラフBを部分グラフとして含むか）がNP完全なので、計算量の意味では難しい さて、どうしましょうか

55 アプローチ１：そのままがんばる ・ 埋め込み判定に時間がかかるのは、埋め込むグラフが大きい場合  小さければ、なんてことはない
・ 埋め込み判定に時間がかかるのは、埋め込むグラフが大きい場合  小さければ、なんてことはない ・ 実際、大きなパターンがたくさん出てこられても、困る ・ 埋め込み判定は力技でやり、多少時間がかかっても気にしないことにする  次の問題は、候補となるパターンを如何に列挙するか ・ 幅優先的に、頂点数が小さいグラフから順に列挙する （過去に作ったグラフに頂点＆枝を加え、１つ大きいグラフを作る） ・過去に作ったグラフを全て記憶し、重複を避ける

56 アプローチ１：そのままがんばる (2) ・ 重複の判定は、実は面倒  グラフ同型性判定を解かなければいけない
 しかも、過去に生成した全てのグラフと同型性判定をすると、 　　大変な時間がかかる ・ 各グラフを、「標準型」の文字列に変換して、保存する  過去に生成したかどうかを、文字列検索でできる ・ 「標準型」は、そのグラフを表す、辞書順 　最小の隣接行列をベクトル化したもの １ 多少遅いが、列挙できる

57 列挙の困難さ ・ 重複の判定が効率よくなると、次のボトルネックは候補の生成部分  ひとつの候補が複数のルートで生成されると、計算の無駄がある ・ 深さ優先木を生成し、それに肉付けする形でのみ、生成を行う ・ ２つの頻出グラフを重なりがあるようにマージして、 　より大きな候補を作る 　 頻出グラフの部分グラフは頻出、という性質を使う だいぶ速くなるが、メモリの問題は残る

58 アプローチ２：クラスを限定する ・ グラフマイニングは、埋め込み＆重複検査が難しい  これらが簡単にできるクラスに限定する ・ たとえば、
　 これらが簡単にできるクラスに限定する ・ たとえば、 　－ パターンがパス・サイクル 　－ データベースの各項目が木 ・ 頻出パターンの生成が、深さ優先的にできるようになる ・ 埋め込みに関しては、生成する元となったパターンの埋め込みの位置を覚えておけば、楽にできる（位置が指数になる可能性はあるが）

59 ・ 各項目が順序木になっているデータベースから、 頻出する順序木を見つける 順序木： 子どもの順番が陽に指定された根付き木
頻出順序木列挙 ・ 各項目が順序木になっているデータベースから、 　　　　頻出する順序木を見つける 順序木： 子どもの順番が陽に指定された根付き木 ≠ 同型だが、子どもの順序が異なる

60 親の定義： 一番右の葉を除去する  子どもは一番右に 葉をつけたもの
順序木の列挙 親の定義： 一番右の葉を除去する  子どもは一番右に 　　葉をつけたもの

61 順序木  無順序木 ・ 子どもの順序が異なることに意味があまり無い場合、無順序木（普通の意味での根付き木）を列挙したい
・ 子根付き木は、単に右端に葉を追加するだけだと、 重複ができてしまう。 重複を回避するため、標準形を用いる

62 順序木  無順序木 (2) （順序木の）深さ列： 左を優先して深さ優先探索し、訪れた頂点の深さ＆ラベルをpre-orderで並べたもの
・２つの順序木が順番も含めて同型　⇔ 深さ列が等しい ・子供の順序を入れ替えていろいろな木が作れる。その中で最大の深さ列を持つものを left heavy embedding と呼ぶ （これが代表） 　　（各頂点の子供を子孫の深さ列の大きさでソート） ・２つの無順序木が同型　⇔ left heavy embedding が等しい 0,1,2,3,3,2,2,1,2, ,1,2,2,3,3,2,1,2, ,1,2,3,1,2,3,3,2,2

63 ・ left-heavy embedding T の親 ： T の最も右の葉を取った木  親も left-heavy embedding
標準形の親子関係 ・ left-heavy embedding T の親 ： T の最も右の葉を取った木 　　 親も left-heavy embedding 0,1,2,3,3,2,1,2,3,2, ,1,2,3,3,2,1,2,3, ,1,2,3,3,2,1,2,3 T 親 親の親 ・Left heavy embedding の子は、最右パスの右に、コピー深さ以浅に葉を付けたものになる 　 各頂点の子の深さ列の重みが逆転しない 　 コピー深さは O(1) で更新できる

64 ・ 順序木の列挙木の 枝刈りをしたものに対応
無順序木の列挙 ・ 順序木の列挙木の 枝刈りをしたものに対応

65 無順序木の列挙：その他 ・データが木である場合、順序木・無順序木の埋め込み判定は、親が埋め込み可能だった場所の、右端の葉の位置のみを覚えておけば十分  高速にチェックできる上、メモリが必要ない ・ 順序木・無順序木は、同一の出現を持つパターン達の極大が唯一とならない  飽和パターンを導入しても、ぱっとしない

66 逆探索の例： フロアプラン （長方形による部屋分け）
逆探索の例：　フロアプラン （長方形による部屋分け） 親の定義： 左上の部屋の 右か下の壁をスライドして 左上の部屋をつぶす

67 参考文献など ・ 頻出集合およびその応用 (’90～) 星の数ほど
・ 頻出集合およびその応用 (’90～)　　星の数ほど 　　 “frequent pattern”、”frequent itemset” で検索すると出てくる ・ 極大頻出集合およびその応用 (’90～)　　やはり多い 　　 “maximal frequent itemset” などで検索すると出てくる ・ pasquerらのアルゴリズム (‘99) 飽和集合の導入 ・ 宇野らのアルゴリズムLCM (‘04) 現在最速のアルゴリズム ・ 実装 LCM: (Linear time Closed itemset Miner) 宇野のHP ・ レポジトリ　（実装、論文、比較実験の数々）

68 参考文献など (2) ・ 鷲尾らのアルゴリズム （’01 ） グラフマイニングの先駆け ・ 中野先生（群馬大）の列挙アルゴリズム
・ 鷲尾らのアルゴリズム （’01 ） グラフマイニングの先駆け ・ 中野先生（群馬大）の列挙アルゴリズム 　　順序木・極大三角形分割・フロアプランなど ・ 中野・宇野・有村 （’03～ ） 順序木・無順序木の多項式時間頻出列挙

69 まとめ ・ データ中心の科学： あいまいな目的に対する列挙的なアプローチ ・ 頻出パターンは、データの組合せ的な特徴を捉えることができる
・ データ中心の科学：　あいまいな目的に対する列挙的なアプローチ　 ・ 頻出パターンは、データの組合せ的な特徴を捉えることができる ・ 出力数依存アルゴリズム、解数の小さいモデルの重要性 ・ 逆探索による効率な探索 ・ 末広がり性の利用が大規模データに対する高速処理の鍵 今後の課題 ・ 幾何学的なデータ＆パターン ・ エラーをゆるした包含関係の導入 ・ 飽和集合の他のパターンへの拡張 ・ 多項式時間列挙の難しいパターンの、実用的解決