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

列挙とその応用の基本

列挙問題： 与えられた問題の解を全て重複なく見つけ出す問題 ・ グラフの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 情報科学の基礎的な問題 近年、広く使われ始めている

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

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

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

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

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

・ 近年、IT技術の発達で、大規模なデータが半自動的に収集できるようになった （POS、web、文書、顧客データ、財務、利用者、人事…） データ中心の科学 ・ 近年、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 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 全ての組合せより はるかに少ない いかに効率よい探索ルートを作り、短時間で移動するかが課題

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

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

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

研究の歴史 ・ 頻出パターン発見問題はデータマイニングの基礎的な問題  星の数ほどの論文がある （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 が含まれる、など） ・ 多く現れる組合せを用いないと、仮定部分を満たすものが少なく、ルールとして意味がない ・ 組合せを細かく見ると、ノイズに振り回される 頻出集合を仮定に用いることで、 信頼度の高いルールを 効率良く見つけられる データ ベース データ ベース 正例 ・ 実験データ ・ 利用者履歴データ、マーケッティング 負例

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

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

集合の出現と頻出度 集合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} }

与えられたトランザクションデータベースと最小サポートθに対して、頻出集合を全て見つける問題を考える ・ 頻出集合：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 ＝ 与えられたトランザクションデータベースと最小サポートθに対して、頻出集合を全て見つける問題を考える

頻出集合の列挙

頻出パターンの単調性 ・ 頻出パターンの部分パターンは頻出 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 も大きすぎる

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

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

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

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

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

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

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

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

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

・ データベースの全ての 飽和集合とその親子関係 親子関係の例 ・ データベースの全ての 飽和集合とその親子関係 φ 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 ＝ 出現集合が隣接 親子関係

・ 実データからとった、著名なベンチマーク問題でテスト ・ 項目数は 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パターン程度

計算機実験： 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” だそうです 賞状と賞品 賞品は {ビール, 紙おむつ} “Most Frequent Itemset” だそうです

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

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

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

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

メモリ使用量 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 標準形の親子関係 ・ left-heavy embedding T の親 ： T の最も右の葉を取った木 　　 親も left-heavy embedding 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 T 親 親の親 ・Left heavy embedding の子は、最右パスの右に、コピー深さ以浅に葉を付けたものになる 　 各頂点の子の深さ列の重みが逆転しない 　 コピー深さは O(1) で更新できる

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

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

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

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

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

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