サブグラフ列挙と頻出パターンマイニング－データサイエンスで活躍する列挙アルゴリズム宇野毅明（国立情報学研究所＆総合研究大学院大学） 2008年9月2日 FIT １．列挙の利用実用面：データ中心の科学・近年、IT技術の発達で、大規模なデータが半自動的に収集できるようになった（POS、web、文書、顧客データ、財務、利用者、人事…）既存のデータを多角的な視点から解析し、何かを得たい問題発見定式化求解データの選別モデル化データ処理いわば、データを出発点とした問題解決の科学（人工知能、データマイニング、自然言語処理、セマンティックweb… 近年の情報学でもメジャーな研究スタイル）データ全体を調べるために、常に高速なデータ処理が課題データ中心科学でのアプローチ・データが整形されていない：ノイズ、うそ、質・作成目的の違いがある－データ収集の目的が、解析の目的と異なる－半自動的に、多様な場面でデータを収集している  あいまいさを許容するモデルと計算が必須・評価値があいまい：数理的に表現しにくい評価値、目的自体が不明確－役に立つ、わかりやすい、面白いといった尺度  最適解がベストとは限らないため、良い解が多量に必要・巨大で構造を持つデータ： 100万項目、べき乗則、局所的な密構造  単純な問題を高速に解く必要がある  データの平均的な特徴を捉えた、平均的に高速な手法が重要・個々の場面で問題が変化：  共通する基礎的な問題を解くツールが、実用上・応用乗重要  個別の尺度を最適化するより、条件を満たす解の列挙アプローチの変化きれい非整形あいまい計算明確あいまい列挙モデル個別対応中規模大規模基礎的問題のツール現実的高速計算まとめると、「大規模で基礎的な問題に対する、あいまいさを考慮した、高速な列挙アルゴリズムの開発」が重要列挙の利点・最適解がどの程度「最適」なのか、最適化ではわからない  列挙なら、いい解の分布が分かる・確かでない目的関数を最適化しても、欲しいものは得られない  良い解の列挙なら、多くの候補の中から最も良いものが選べる・個別の問題の最適解は、他の問題でも良いとは限らない  基本的な制約を満たす解の列挙なら、汎用性が高い・最適化はシステムの極みを見せるのに対して、列挙は問題の構造すべてを知ることができ、解析や知らないものの発見に有利列挙の応用・最適化の別解：複数の目的を持つ最適化や、目的がはっきりしない、あるいはゆらぐような問題では、準最適解を候補として列挙して、次のプロセスで真の最適解を探す・データマイニング：役に立ちそうなもの、特徴などが満たすべき制約を考え、それを満たす解を列挙する。多数の解の生成により見つけ損ないをなくす・特徴量（カーネル）：機械学習で使われる、構造をベクトルデータとして表す方法の一つに全ての部分構造を列挙、数を勘定するものがある。・探索、特にゲーム：着手可能な手を、評価値が良さそうなものから順に列挙して手を読む・証明、不具合がないことの確認：列挙を完全に行うことで場合を尽くす。条件を設定することで、自明でない高速化を行う列挙の難しさ・列挙アルゴリズムを設計するときには、いくつかの難しさがある－全てを見つける難しさ（探索経路構築）－重複を回避する難しさ（逆探索）－同型なものを同一視する難しさ（標準形）－計算を速くする難しさ（計算アルゴリズム） … しかし、実際はうまく解ける物も多い探索の難しさ・列挙の対象はたいてい、１つ見つけるのは簡単な物・今まで見つけた物が全ての解であるか、どのように調べる？－経路列挙で、今まで見つけた経路が全てか調べる？・クリークやパス（経路）は、隣接性を持つ－クリークは１つずつ付け足すと全てが得られる－パスは再帰的な場合分けができ、空の問題のチェックが簡単・しかし、こううまくいくものばかりではない。－極大な××、極小な○○ －あの条件とこの条件とこの条件と．．．  互いに隣接していない、場合分けも難しい重複を回避する難しさ・探索はできるので、全て見つけることはできるとする・しかし、どうやって同じものを２度出さないようにするか、あるいは同じ探索を繰り返さないようにするかは、それほど自明でない・簡単に回避するなら、解を全部メモリに保存すればよい  解が多くなるとメモリ効率が悪い  動的にメモリを確保して解を保存するルーチンと、解を効率よく検索するルーチンが必要（ハッシュがあればいい）・今の解を出力するか、あるいは探索を続けるか、過去の履歴を見ずに、解自体から計算でわかればよい計算の高速化・高速化は、通常のアルゴリズムに対するテクニックが有効・各反復の計算の高速化－２分木、ハッシュなどのデータ構造、－隣接行列  接続行列による疎性の利用－よけいな処理を省いて、高速化  計算オーダー減少－キャッシュ、コードの最適化・列挙の場合、解を少しずつ変更する操作が多いので、データを動的に管理する方法が有効  各頂点の次数、重み和、頻出度など・指数的に広がる再帰構造を使った高速化が特に有効アルゴリズム理論の利点・大規模な計算には、アルゴリズム理論に基づいた技術が有効  アルゴリズム理論による高速化は、問題の大きさに対する計算時間の増加を抑える  計算の結果は変化しない 100項目 100万項目 2-3倍 10000倍データが巨大になるほど、アルゴリズム改良の加速率は上がる２．頻出集合の列挙（LCM）データベースを分析したい・データベース構築と検索は、もうできるようになった（絞込みや、あいまい検索はまだ改良の余地があるけど）・より詳しくデータを解析するために、データの特徴を捉えたい各種統計量（データベースの大きさ、密度、項目に現れる属性値の総計、分布）よりも、深い解析がしたい  組合せ（パターン）的な構造に注目（どういう組合せ（パターン）がどれくらい入っているか）・組合せ・パターンの個数は指数なので、全てを尽くすのは効率的でない  多く現れるものだけに注目データベース実験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 ．．．トランザクションデータベーストランザクションデータベース：各トランザクション T がアイテム集合 E の部分集合になっているようなデータベース、つまり、∀T ∈D, T ⊆ E ３つ以上に含まれるもの 1,2,5,6,7,9 {1} {2} {7} {9} 2,3,4,5 {1,7} {1,9} D ＝ 1,2,7,8,9 {2,7} {2,9} {7,9} 1,7,9 {1,7,9} {2,7,9} 2,7,9 2 {1,2}を含むトランザクション＝ { {1,2,5,6,7,9}, {1,2,7,8,9} } 頻出集合列挙は、与えられたトランザクションデータベースと最小サポートσに対して、頻出集合を全て見つける問題パターンマイニングの応用売上げデータの分析・雑誌とおにぎりが良く一緒に売れてます・夜訪れる男性は高めの弁当を買ってます・さんまと大根とすだちはセット販売したらどうですか？・・・画像認識項目の自動分類遺伝子Z： ●○★ 遺伝子A： ●△▲ 遺伝子Z： ●○★ 遺伝子B： ●△▲ ・・・遺伝子F1： ■□ 遺伝子D： ●△▲ 遺伝子F2： ■□ ・・・・・・ Webページのトピック分類・みかんとみかんでない画像を分ける特徴を見つける・ Webページを、リンクやキーワードの組合せで、トピック毎に分類全国ラーメンラーメン巡りの旅人カツカレーと私カレーの作り方基礎的な問題なので、応用に広がりがある頻出集合の単調性・工夫をするためには、何か問題の特徴をつかまなくてはいけない 111…1 ・使えそうなのが、「頻出集合の部分集合は必ず頻出」、というもの（単調性という）  つまり、ハッセ図（包含関係を図示したもの）の上で、頻出集合は連結なエリアに存在頻出 000…0 1,2,3,4 1,2,3 1,2,4 1,2 ・空集合から出発し、１つずつアイテムを加えることで、全ての頻出集合が作れるが、適当に作ると重複がでる 1,3 1 1,3,4 1,4 2,3,4 2,3 2,4 3,4 2 3 4 φ バックトラック法による探索・そもそも重複が起こるのは、各頻出集合がいくつもの部分集合から「アイテムを１つ追加」として得られるのが原因（{1,2,3} には、{2,3}+1, {1,3}+2, {1,2}+3 の3通りある）・そこで、各頻出集合に対して、「作られ方」と1通りに制限する・具体的には、「一番大きなアイテムを加えた場合のみ」とする（{1,2,3} は、{1,2}+3 という 1,2,3,4 作り方でしか作らない、ということ） 1,2,3 1,2,4 1,3,4 2,3,4 探索ルートが木構造になるので、重複がなくなる 1,2 1,3 1 こういう探索方法をバックトラック法という 1,4 2,3 2,4 3,4 2 3 4 φ バックトラック法の計算時間・計算時間を算定してみる。擬似コードは Backtrack (K) 1 Output K 2 For each e > K の末尾（ K の最大のアイテム） If K ＋e が頻出集合 call Backtrack (K＋e) －再帰呼び出しの回数は、頻出集合の数と同じ－1呼び出し（反復と言う）の O(|D|) 計算時間は（n-K の末尾）×（頻出度計算時間） 1,2,3,4 1,2,3 1,2,4 1,3,4 2,3,4 1,2 1,3 1,4 2,3 2,4 3,4 1 解の個数に線形の計算時間になった 3 2 φ 4 各反復の高速化・アイテム集合 X+e を含むトランザクションを見つけたい・ X＋e を含めば X を含むので、X を含むトランザクションだけを調べればよい（すでに計算済み）（検索で言うところの絞り込みと同じ）  データ全体を見る必要はない・さらに、追加するアイテム e を選ぶ際にも「X を含むトランザクションに含まれるもの」だけで十分・２つを合わせると、大幅な計算の省略ができる（一部だけの高速化に見えるが、全体を高速化できている末広がり性・再帰呼び出しを繰り返すと、 Pの頻出度は小さくなる  振り分けの計算時間も短くなる・バックトラックは、各反復で複数の再帰呼び出しをする  計算木は、下に行くほど大きくなる  計算時間を支配するのは一番下の数レベル計算時間長・・・計算時間短ほぼ全ての反復が短時間で終了  全体も速くなる最小サポートが大きい場合も・ σが大きいと、下のレベルでも多くの場所を見ることになる  末広がり性による高速化はいまひとつ・データベースの縮約により、下のレベルの高速化をはかる（１）前回追加したアイテムより小さいアイテムは消す（２）現在のデータベースの中で、頻出になっていないアイテムは消去する（再帰呼び出しの中で加えられることが無いから）（３）まったく同一のトランザクションは、１つにまとめる１・実データだと、下のほうのレベルでは大きさがだいたい定数になる頻出度が小さいときと同程度の速度１３２２６４７４３２５４３１４４４５６７６７６７実データ（すかすか）平均の大きさ5-10 BMS-POS BMSWebView2 retail 実データ（すかすか）メモリ使用量 BMS-POS BMSWebView2 retail ３．頻出集合の応用事例応用：他の頻出パターンマイニング・パターンマイニングは、基本的にパターン毎にプログラムを組み替える必要がある・もし、部分パターン列挙が可能であれば、各項目に含まれる部分パターンを列挙してしまうと、アイテム集合マイニングに帰着できる例）項目が高さ２以下の木であるデータから、高さ2以下の木のパターンを見つける 1 2 {1, 2, 3, 4} 3 4 5 ・・・グラフ、シークエンスの集合など各項目が×××の集合応用：他の頻出パターンマイニング・部分パターンがあまり多くない場合、例えばマルチセットのマイニングや各項目が複数のグラフや系列でできている場合など、パターンが構造の集合、という形をしているときに有効なテクニックである。・有向非閉路グラフから頻出有向グラフを見つけるアルゴリズム有向非閉路グラフ ⊇ Alexandre Termier, Yoshinori Tamada, Seiya Imoto, Takashi Washio, Tomoyuki Higuchi, From Closed Tree Mining to Closed DAG Mining 応用：遺伝子のクラスタリング・多くの遺伝子は他の遺伝子と共起して機能する・臓器などの部位、発達段階による時期などで、一緒に発現する・共起しやすい遺伝子をグループ化すると、関係の深い遺伝子が分かるだろう A: ● ● ● ● B: ● ● ● ● C: ● ● ● ● ・トランザクション 発現する場所（時）、アイテム 遺伝子とすると、頻出集合は、多くの場所で共通に発現する遺伝子のグループになる。（実際は飽和集合を見つけている）・似通った物を消すため、25%の領域が他に含まれるものは消去 Y. Okada, W. Fujibuchi, P. Horton, Module Discovery in Gene Expression Data Using Closed Itemset Mining Algorithm 応用：分類規則の発見・パターンが含まれる項目の重みの合計を考えると、重み付きの頻出パターン発見ができる正例（＋の重み）  含まれることが重要な項目を指定できる  頻出パターンの場合、項目の重みは全て１負例（－の重み）・さらに負の重みを許すと、「含まれたくない項目」が表現できる  自動分類を行いたいデータに対して、正例の項目には正の重み、負例のデータには負の重みを与えると、分類規則に相当するアイテム集合が見つかる・見つかるパターン数に対する計算時間は長くなるが、それでも実用の範囲内応用：画像分類・自動分類の手法の一つに、各項目の特徴ベクトルと基準ベクトルの内積を取って、その値によって正例と負例に分類する方法がある・基準ベクトルを最適化して、分類規則を学習する・特徴ベクトルに使う特徴には、属性値をそのまま使うことが多いが、そこにアイテム集合を使うと可能性が広がる・変数が多くなるので、列生成法を使って最適化する S. Nowozin, K. Tsuda, T. Uno, T. Kudo, G. Bakir Weighted Substructure Mining for Image Analysis ２部グラフによる表現・アイテム、トランザクションを頂点とし、包含関係を枝とする A: 1,2,5,6,7,9 B: 2,3,4,5 D＝ C: 1,2,7,8,9 D: 1,7,9 E: 2,7,9 F: 2 1 2 3 4 5 6 7 8 9 A B C D E ・アイテム集合と、それらを含むトランザクションの集合  ２部グラフの２部クリーク・アイテム集合とその出現集合  トランザクション側が極大な２部クリーク F 応用：複合語による単語の分類・単語を、複合語の作り方を使ってグループに分類・単語が頂点、単語を組合せて複合語ができるとき、枝を張るとして2部グラフを作る関東地方関西地区中国電力北陸・極大2部クリークを見つけると、それが類義語、あるいは反対語など、関連する意味を持つ単語群になるだろう中渡瀬秀一, 相澤彰子完全N部グラフ構造を用いた単語の多義性獲得応用： webコミュニティーの抽出・ web のリンク構造から、 2部クリークを見つけ出す－リンク元: 共通の趣味を持つページ－リンク先: 同じカテゴリのページ・グラフから2部クリークを見つけるには、グラフを2部グラフに変換グラフサイトサイト趣味バイクホンダバイク好きカワサキバイク万歳ヤマハバイク人生隣接している頂点間に枝を張る頂点集合頂点集合実装の参照先・宇野のHP （頻出集合の他の構造のマイニング、列挙や類似比較アルゴリズムの実装） http:research.nii.ac.jp/~uno/ ・実装、問題、論文のレポジトリ（比較実験の数々も） http://fimi.cs.helsinki.fi/ ・羽室・森田による GUI 応用：その他・ブログユーザ空間からの頻出なコミュニティ抽出法・ Extracting generic basis of association rules from SAGE data ・ローカルデータベースにおけるアイテム集合の相関の違いに基づく隠れた相関の発見・コンピュータゲームプレイヤの静的評価関数の自動生成に関する研究動向・駒位置と効き関係に注目した詰み評価関数の自動生成・Mining complex genotypic features for predicting HIV-1 drug resistance ・・・４．その他の実用的列挙部分グラフ列挙問題部分グラフ列挙：与えられたグラフの（頂点誘導）部分グラフで、定められたグラフクラスに属する物を全て見つける－パス、サイクル、木、スター、クリーク、コーダルグラフ、インターバルグラフ、密部分グラフ、... －ラベル付き、重み付き、同型性の扱い、... ・応用でのモデルがグラフクラスに対応・クラスによって、解の数、列挙の難しさが変わる・頻出集合は、2部グラフの2部クリークに対応グラフクリーク列挙問題グラフのクリーク：部分グラフで、全ての頂点間に枝があるもの・ 2部クリークの列挙は、グラフの変換でクリーク列挙に帰着可能・最大クリークを求める問題はNP完全・極大クリークは簡単に求められる・最適化を中心に非常に多くの研究がある・大規模かつ疎なグラフでの、クラスタリングなどの応用が多い単調性を利用して列挙・クリークの部分集合はクリーク  単調性が成り立つので、山登り法（バックトラックで列挙可能）・単純に作った手法では１つ O(n3) 時間 111…1 クリーク 000…0 ・クリークに追加できる  クリークの全ての頂点に隣接なので、これらの頂点を更新することで、１つ O(Δ) 時間・末広がり的な計算構造により、実際はほぼ定数時間新旧アルゴリズムの比較 30000 25000 20000 15000 10000 5000 0 10 00 30 00 50 00 70 00 90 00 16 00 64 0 00 25 0 60 00 1万個あたりの計算時間(秒) 既存と提案手法の比較既存 r=10 提案 r=10 既存 r=30 提案 r=30 次数巨大あり頂点数・次数の増加に対しては、ほぼ線形で伸びる・共著関係を表す実データに対しても、ほぼ１つあたり定数時間スパムサイト検出・スパムサイト：ある種のリンク構造を構築してページの重要性を上げ、（不正な）商業活動や、違法な行為を行うサイト  web検索では、スパムサイトを表示したくない  スパムサイトを機械的に判別したい・スパムサイトは、ランキングを上げるために密なリンク構造（完全に密ならばクリーク）を作っている  クリークを見つけることでスパムサイトを検出  実際には、スパムサイトは非常に大きな次数を持っており、巨大な、少しずつ違う極大クリークがあり見つけきれない小野拓史, 豊田正史, 喜連川優, リンク解析を用いたウェブ上のスパム発見手法に関する一考察その他の応用研究・ Core Stability of Minimum Coloring Games ・ Biclustering Protein Complex Interactions with a Biclique Finding Algorithm ・ Faster Algorithms for Constructing a Concept (Galois) Lattice ・ An Efficient Algorithm for the Extended (l, d)-Motif Problem With Unknown Number of Binding Sites ・ Rapid Detection of Botnets through Collaborative Networks of Peers サイクルの列挙・グラフの中から、わっかになっている経路を全て見つける問題がサイクル列挙問題・分割法（場合分けをしていき、解が無くなった場合を枝刈りする）で、１つあたり O（|E|）時間で解ける、という1972年の結果がある・実際は、中くらいのグラフでも大量のサイクルがあり、非実用的・ショートカットのないサイクルのみに限定すると、数が実用的な範囲に収まる。計算時間は１つあたり O（|E|）時間応用と性能・グサイクルの列挙も、分割していくに従い問題が小さくなるため、末広がり的な構造を持ち、高速な列挙が可能・化学化合物では、ショートカットのないサイクルは環構造と呼ばれ、特徴を知る上で大切な概念・化合物の性質を予測する際に、環構造列挙の結果を使って精度を上げている研究もある類似項目対の列挙・非常に多くの項目を持つデータベースの、どの項目とどの項目が似ているか、含むかを調べる  普通に全対比較したのでは、とても終わらない・テキストのような切れ目のないデータは、小さく切って似てるものを探すことで、中規模の類似構造を検出例：共通部分が2以上のペア (A,B), (A,C), (A,D), (A,E) (C,D), (C,E), (D,E) D ＝類似項目が同一グループに入るよう分類する、という手法で高速化 A: 1,2,5,6,7 B: 2,3,4,5 C: 1,2,7,8,9 D: 1,7,9 E: 2,7,9 F: 2 リンク先が似ているwebページ・ webリンクのデータの一部を使用－ノード数 550万、枝数1300万－ Pentium4 3.2GHz、メモリ2GB ・リンク先 20個以上 288684個、20個以上共有するペア数が143683844個、計算時間、約8分・リンク元 20個以上が 138914個、20個以上共有するペア数が18846527個、計算時間、約3分・方向を無視して、リンクが 100個以上あるものが 152131個、 100個以上共有するペア数が32451468個、計算時間、約7分・方向を無視して、リンクが20個以上あるものが370377 個、 20個以上共有するペア数が152919813個、計算時間、約14分ゲノムの比較 (2) X ヒトX染色体とマウスX染色体の比較・ 30文字で間違い2文字以下のペアを列挙・長さ3000、幅300 の領域に3つペアがあれば点を打つマ（誤差10%弱で似てウスいるものは、必ず３つ染のペアを含む）色体・ノイズをかなり除去できている PCで 1時間で可能ヒトX番染色体まとめ・データ中心化学に対する列挙からのアプローチ－あいまい性、ノイズ、個別対応．．．  列挙が効果的に使える・頻出集合の列挙－単調性を使った列挙法－データベース縮小を使い、計算構造の末広がりに合わせた高速化・クリーク、サイクルの列挙・類似項目・包含関係の列挙 ■ 厳密解法、ランダムサンプリング、数え上げなどへの応用 ■ データ解析分野での、列挙を用いたアプローチの確立 ■ 実践的な列挙アルゴリズムを説明する理論構築