列挙学校：第４コマ「複雑な構造の簡潔な列挙法と実装法」宇野毅明（国立情報学研究所＆総合研究大学院大学） 2008年2月28・29日列挙学校簡単に自己紹介名前：宇野毅明年齢・職種：３７歳、准教授研究分野：アルゴリズム理論－コンピュータプログラムの設計手法の理論－速いコンピュータを作ったり、プログラミングの腕を競うのではなく、「設計方法の違いによる性能の向上」を目指す最近の研究：ゲノム情報学やデータマイニングで出てくる巨大なデータベースの基礎的（とはいっても非常に時間のかかる）な解析を超高速で行うアルゴリズムの開発趣味（日課？）：子供と遊ぶこと１．列挙のつかみどころ１．１列挙の難しさ列挙の難しさ・列挙アルゴリズムを設計するときには、いくつかの難しさがある－重複を回避する難しさ（逆探索  岡本さん）－全てを見つける難しさ（探索経路構築）－同型なものを同一視する難しさ（標準形  中野さん）－計算を速くする難しさ（計算アルゴリズム） … どう難しいのか、少しおさらいしてみましょう重複を回避する難しさ・探索はできるので、全て見つけることはできるとする・しかし、どうやって同じものを２度出さないようにするか、あるいは同じ探索を繰り返さないようにするかは、それほど自明でない・簡単に回避するなら、解を全部メモリに保存すればよい  解が多くなるとメモリ効率が悪い  動的にメモリを確保して解を保存するルーチンと、解を効率よく検索するルーチンが必要（ハッシュがあればいい）・今の解を出力するか、あるいは探索を続けるか、過去の履歴を見ずに、解自体から計算でわかればよいこれを一般化すると、逆探索的なアイディアになる回避する必要がないと・解が多くなるとメモリ効率が悪い・動的にメモリを確保して解を保存するルーチンと、解を効率よく検索するルーチンが必要・これらが気にならないときは？  解はそんなに多くない。あるいは、メモリがたくさんある  ハッシュ or ２分木がある・力ずくで組んだほうがすっきり簡単  工学的に有利・時間計算量の意味でも問題はない  理論的にもOK これを一般化すると、逆探索的なアイディアになる同型なものの取り扱い・グラフなどの直線的でない構造を持つ構造は、２つのものが同じかどうかを判定することからして難しい・解決策は、比較しやすい構造（標準型）に変換すること  同じものは同じものに変換されること  サイズが巨大にならないこと・順序木のビット列化  無順序木の順序木化  直並列グラフやコグラフの無順序木化・標準型を列挙するアルゴリズムを作る＝もとの構造の列挙アルゴリズムを作る同型判定が難しいと・同型判定が難しかったらどうしましょうか？  グラフ、系列データ、行列・・・・それでも、だいたいは指数時間かければ同型性の判定はできる・グラフマイニングのように、列挙するものがごく小さい（せいぜい 30枝）くらいであれば、根性入れて計算すればいい  指数時間かからないことも多い  そもそも、列挙部分でなく、埋込み判定がボトルネック・計算量的には、数反復で指数時間、残りは多項式時間、というアルゴリズムが設計できれば、全体としては多項式時間  まだ、こういうタイプのアルゴリズムは存在しない探索自体が難しい・クリークやパスは、列挙が簡単－クリークは１つずつ付け足すと簡単に全てが得られる－パスは再帰的な場合分けができ、空の問題のチェックが簡単・しかし、こううまくいくものばかりではない。－極大な××、極小な○○ －あの条件とこの条件とこの条件と．．．  互いに隣接していない、場合分けも難しい・探索が難しい問題は、大きく２つに分けられる－１つ見つけるのは簡単。しかし列挙は… （極大クリークなど）－１つ見つけるのすら難しい（SATの充足可能解など）１つ見つけるのも難しい・難しい問題（NP完全）の解は、１つは見つけることすら難しい（最大クリーク、充足可能解、ハミルトンサイクル・・・）・その上、全部見つけるとなると、これはもう絶望的  各反復がNP完全になるので  理論的な結果はあきらめたほうが賢明・しかし、同型性と同じように、－「多くの場合易しい」充足可能解など－「解はそんなに多くない」極大、極小性がある－「解の範囲が限られている」大きさがある程度限られてるのであれば、力ずくでも何とかなる１つは見つけられる・１つは見つけられる場合：１つの解から他の解を作る方法を考える－うまく作れれば、解から解へと探索できる－全体がつながれば、列挙可能・しかし、「作る作業」が指数時間かかる、指数個の解が見つかる、という状況だと、時間効率は悪い・・・他の解への移動方法・極大解だったら－いくつか取り除いて小さくし、違うものを加えて大きくする  任意の解から任意の解へ移動できる－しかし、隣り合う解の数が指数個あるので、全て見に行くには、指数時間必要・隣が少なくなるように、移動を制限する－キーとなる要素を加えて、不要なものを除く  除き方が指数通りあると、うまくいかない・極大の場合、場合分け＋枝刈りが比較的うまく動く  極大解の上には何もない＆解の存在確認が簡単計算の高速化・高速化は、通常のアルゴリズムに対するテクニックが有効・各反復の計算の高速化－２分木、ハッシュなどのデータ構造、－隣接行列  接続行列による疎性の利用－よけいな処理を省いて、高速化  計算オーダー減少－キャッシュ、コードの最適化・列挙の場合、解を少しずつ変更する操作が多いので、データを動的に管理する方法が有効  各頂点の次数、重み和、頻出度など・指数的に広がる再帰構造を使った高速化が特に有効１．２これからの列挙アルゴリズム列挙アルゴリズムの設計・列挙アルゴリズムの設計の場面は、主に３つ－新しいアルゴリズムの設計、計算量の改善（理論）－実データに対する効率的な計算方法（工学）－実用ツールの作成、特定データの解析（実用）・互いに、互いの価値観はいまひとつ意味がない－実データ一個解けても、計算量の改善にはならない－複雑な問題のアルゴリズムは、実用では使えない－特定問題のツールは、モデルの意味でつまらない・しかし、互いの要素がないと、面白くないことも事実－実用のない理論  おもちゃの研究－理論のない応用  単なるプログラミング設計のセンス・いい研究・活動には、互いの分野を理解することが重要・しかし、知識の収集では分野のだけでは理解にならない－価値観、問題意識、目的、流儀、センス… ・以後の話では、価値観、センスのところに目を凝らして、話を聞いてください。実用面：データ中心の科学・近年、IT技術の発達で、大規模なデータが半自動的に収集できるようになった（POS、web、文書、顧客データ、財務、利用者、人事…）既存のデータを使って何かを得たいデータの選別モデル化データ処理いわば、データを出発点とした問題解決の科学（人工知能、データマイニング、自然言語処理、セマンティックweb… 近年の情報学でもメジャーな研究スタイル）データ中心科学の特徴・データが整形されていない目的がはっきりしない、あるいは異なる目的のために集められたデータを用いるため、必要なものがすぐ取り出せるとは限らない。また、ノイズや不正確な情報も含まれうる。・目的関数があいまいデータが情報の塊のようなものなので、そこから得られるものはやはり情報であることが多い（知識、特徴分析といったもの）。それら情報の価値は数理的な尺度では計りにくい。また、従来の最適化とは異なる尺度を用いることが多い。（グラフクラス、シークエンス、情報量、隣接性、類似度、頻出度・・・）・データが巨大で、構造を持つ半自動で集められたデータであるので、データは通常、巨大である。しかし各項目が持つ属性は少なく、疎である。・データ処理は列挙的な要因を持つものが多い複雑な目的関数を評価するため解候補を列挙する、列挙で得た解を分析して全体像を得る、ランキングして、相対評価を行う、などデータ処理の変化 ▪ 不ぞろいなデータから有用な情報を得るには複雑で豊かなモデルを解く必要がある ▪ そのためには、解く問題を複雑にする必要がある ▪ 比較・統計量  全対比較・組合せ的な統計量 ▪ キーワード検索  パターンマイニング ▪ 完全一致  類似検索データベース ▪ 最適化  列挙・このように処理が変化すると、既存のアルゴリズムを用いて行った場合に、非常に時間がかかることがある例）全対比較を通常の検索を用いて行うと、レコード数だけのクエリを必要とする複雑かつ大量の計算を効率良く行う手法の開発が重要データ処理に求められるもの［多様性］個別の案件に対してモデルが変化  問題設定の変化に対して柔軟であること－［基礎問題］解く問題が基礎的であること－［単純な構造］アルゴリズムのアイディアが単純であり、汎用性の高いレベルで構築されていること［速度］大規模データに対しても高速に動作すること  コードの改良より、良いアルゴリズムの開発－［疎成］データの疎性、スケールフリー性を利用して－［計算構造］計算構造の改良により、無駄な探索を省く－［スケールメリット］多数の操作を一度に行うことで高速化［正確性］なんらかの意味で正確な計算を行うこと－［列挙］全ての解をもらさず重複無く発見－［精度保障］誤差の範囲を保障するアルゴリズム理論の利点・大規模な計算には、アルゴリズム理論に基づいた技術が有効  アルゴリズム理論による高速化は、問題の大きさに対する計算時間の増加を抑える  計算の結果は変化しない 100項目 100万項目 2-3倍 10000倍データが巨大になるほど、アルゴリズム改良の加速率は上がる列挙アルゴリズムの理論面・基礎的な構造に関しては、ほぼ解かれていると考えてよい  パス、木、部分グラフ、連結成分、クリーク、系列・・・・同型性判定が容易なクラスも、けっこう解けている  シークエンス、ネックレス、木、極大平面グラフ・・・・しかし、応用的な要素がちょっとでも入ると、とたんに解かれているものが少なくなる－正例に含まれ、負例に含まれないパターンの列挙－計算量の削減、実用上の計算時間削減法・少々複雑な構造を持つものも同様－コーダルやインターバルなどのグラフクラス－あいまい性を許容した列挙－複数の条件を扱う列挙（クラス＋重み＋制約）これからの理論・基本アルゴリズムの完成度は高い・まったく新しいアルゴリズムの出現は、考えづらい  ある意味で、アプローチが固定的（探索しなければならないのは共通）・探索路決定、重複回避、標準型の設定など、次のレベルは大きな未解決分野  極大解列挙、幾何学パターンマイニング、仮説列挙・・・・厳密解法、ランダムサンプリング、数え上げなどへの応用も、重要な研究分野  列挙技術が、研究の芯になる可能性が高い  通常のアルゴリズムへの、列挙アルゴリズム技術の応用これからの実用・解列挙は、解の完全性という新しい状況を生む・ランキングや比較を行うことで、それぞれの解の質を厳密に評価できる  小さい問題で完全な評価を行えば、手法の質が測れる・解候補の列挙＋候補の絞込み、という方法は、モデルの変化や制約の変化に対して頑強  いいツールを作っておけば、いろいろな場面で使いまわしできる  お試し解析が簡単にできる・高速解法を使うと、今まで手に負えなかった巨大データ解析できる２．高速化の技術２．１頻出集合の列挙（LCM）頻出集合発見用のプログラム・頻出集合発見は、データマイニングと呼ばれる最近興ったデータ解析の中でも基礎的な問題なので、プログラムが多く作られている・入力データ、出力する解、どちらも大きいことが多いので、計算速度は非常に重要・しかも、アルゴリズムの設計しだいで、パフォーマンスが大きく変わる・国際プログラミングコンテストでも、こんな感じ。ばらつき大きい（時間軸は対数）どういう高速化技法あるのか、見てみようトランザクションデータベーストランザクションデータベース：各トランザクション T がアイテム集合 E の部分集合になっているようなデータベース、つまり、∀T ∈D, T ⊆ E 1,2,5,6,7,9 集合 P に対して： 2,3,4,5 P の出現： P を含むD のトランザクション D ＝ 1,2,7,8,9 P の出現集合 Occ(K)： P の出現の集合 1,7,9 P の頻出度 frq( P)： P の出現集合の大きさ 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} } 頻出集合・頻出集合： D の定数σ個以上のトランザクションに含まれる集合（頻出度がσ以上の集合）（ σを最小サポートとよぶ）例）データベース D の3つ以上のトランザクションに含まれる集合 1,2,5,6,7,9 2,3,4,5 D ＝ 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} 頻出集合列挙は、与えられたトランザクションデータベースと最小サポートσに対して、頻出集合を全て見つける問題バックトラック法・頻出集合は単調性を満たす（部分集合は必ず頻出）  バックトラック法が有効 Backtrack (P) 1 Output P 2 For each e > P の末尾（ P の最大のアイテム） If P ＋e が頻出集合 call Backtrack (P＋e) －再帰呼び出し回数は頻出集合数 O(|D|) －１呼び出し（反復と言う）の時間は（n-P の末尾）×（頻出度計算時間） 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 解１つあたり O(n|D|)、とても長い 3 2 φ 4 解1つ当たり、を速くする・解１つあたりの計算時間はそれなりに（多項式時間で）抑えられたが、まだまだ大きい・各 P＋e について、その頻出度を計算－単純にするなら、全ての項目（トランザクション）について、 P＋e を含むかどうか調べる  最悪、データベースの大きさに比例、平均ではだいたい、項目数、 1,2,5,6,7,9 頻出度×Pの大きさ、の大きいほう－ 2分木のようなデータ構造を作って、含むものだけ 2,3,4,5 1,2,7,8,9 抜き出す、あるいは勘定する、というのは、難しい 1,7,9 2,7,9 ここにアルゴリズムが必要 2 幅優先探索の利用 D0={φ}, k := 1 while Dk-1 が空でない for each Dk-1 のメンバー P for each e if P+e が頻出集合 then Dk に P+e を挿入・ P+e の頻出度を計算する前に P+e に含まれる部分集合が全てDkにあるか調べる 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 ・ないものがあるなら、頻出でない 1 φ メモリを使う点、検索に時間がかかる点がネック含むものしか含まない・アイテム集合 P の出現集合を T とする・ P＋e の出現は P を含む（＝ P の出現）  P＋e を含むトランザクションを見つけるときには、 T のトランザクションしか見なくてよい・ T のトランザクションで e を含むものを集めると P＋e の出現集合が得られる・出現集合を更新すれば、データ全体を見なくて良い  計算時間はだいぶ短くなる共通部分をとる・ T のトランザクションで e を含むものを集めると P＋e の出現集合が得られる  P＋e の出現集合は、 Pの出現集合と e の出現集合の共通部分（両方に含まれるものを集めたもの）・共通部分をとるには、両者をソートしておき、同時に先頭からスキャンする {1,3,7,8,9} {1,2,4,7,9} ＝ {1,7,9} 計算時間は、スキャンしたアイテムの数  両者の大きさの和ビット演算を使った共通部分の高速計算・各アイテムの出現をビットの形で保持する（現在の部分集合も同じように） {1,3,7,8,9} {1,2,4,7,9}   [101000111] [110100101] [100000101]  共通部分の計算が、AND 演算でできる（いっぺんに32個(最近は64個) 計算できる）メモリの節約にもなるしかし、後述するデータベース縮約と相性が悪い振り分けによる高速化・各アイテムに空のバケツを用意する・ P の各出現 T に対して、以下を行う－ T に含まれるアイテム e に対して、 e のバケツにT を入れる  この操作が終わった後は、各アイテムe のバケツの中身は P＋e の出現集合になる A: 1,2,5,6,7,9 for each P の各出現 T B: 2,3,4,5 for each T に含まれる e, e > Pの末尾 C: 1,2,7,8,9 eのバケツに T を挿入 D: 1,7,9 E: 2,7,9 F: 2 1: A,C,D 2: A,B,C,E,F 3: B 4: B 5: A,B 6: A 7: A,C,D,E 8: C 9: A,C,D,E 振り分けの計算時間 for each P の各出現 T for each T に含まれる e, e > Pの末尾 eのバケツに T を挿入・計算時間は, P の各出現の (Pの末尾) より大きなアイテムの数の総和・各アイテムに対する再帰呼び出しの準備をいっぺんにすることで、効率化している 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 Occurrence Deliver ・ Compute the denotations of P ∪{i} for all i’s at once, A 1 A2 1,2,5,6,7,9 2,3,4,5 D＝ 1,2,7,8,9 1,7,9 2,7,9 P = {1,7} 2 Check the frequency for all items to be added in linear time of the database size A5 A6 7 A9 B 2 3 4 5 C 1 C2 7 C8 C9 D 1 7 D9 7 9 E 2 F 2 Generating the recursive calls in reverse direction, we can re-use the memory 1再帰呼び出しの計算時間のイメージ・普通に頻出度の計算をすると各 P＋e に対してデータを一回スキャンする (n-t)個・共通部分による計算は効果はこれだけではない Occ(P) と Occ({e}) のをスキャンする  Occ(P) を n-t 回スキャンし、＋データベースの t より大きな t アイテムをスキャンする・振り分けは Occ(P) に含まれるトランザクションの t のをスキャンする t より大きなアイテムをスキャンする t (n-t)個末広がり性・再帰呼び出しを繰り返すと、 Pの頻出度は小さくなる  振り分けの計算時間も短くなる・バックトラックは、各反復で複数の再帰呼び出しをする  計算木は、下に行くほど大きくなる  計算時間を支配するのは一番下の数レベル計算時間長・・・計算時間短ほぼ全ての反復が短時間で終了  全体も速くなる最小サポートが大きい場合も・ σが大きいと、下のレベルでも多くの出現を見ることになる  末広がり性による高速化はいまひとつ・データベースの縮約により、下のレベルの高速化をはかる（１）前回追加したアイテムより小さいアイテムは消す（２）現在の出現集合からできるデータベースの中で、頻出になっていないアイテムは消去する（再帰呼び出しの中で加えられることが無いから）（３）まったく同一のトランザクションは、１つにまとめる１・実データだと、下のほうのレベルではだいたい大きさが定数になる σが小さいときと速度の大きな差はない１３２２６４７４３２５４３１４４４５６７６７６７キャッシュとの相性・速いプログラムを作るとき、キャッシュのヒット率が良く問題になる－ループを開く－メモリの配置を変える for i=1 to n { x[i]=0; }  for i=1 to n step 3 { x[i]=0; x[i+1]=0; x[i+2]=0; } ● ● ● ● ● ● ▲ ▲ ▲ ●●● ●▲ ● ▲ ● ▲ 再帰的に問題が小さくなり、ある反復より先ではキャッシュに入る  末広がり性より、ほぼ全ての部分でキャッシュに入っている木構造を用いた圧縮（trie, prefix tree）・各トランザクションを文字列とみなすと、2分木の形で格納でき、メモリを節約できる  振り分けと併用できる。スキャンの時間も、それだけ短くなる * A: 1,2,5,6,7,9 B: 2,3,4,5 C: 1,2,7,8,9 D: 1,7,9 E: 2,3,7,9 F: 2,7,9 1 2 1 2 5 6 7 7 8 9 7 9 3 4 5 7 9 7 9 D F B E 9 C A 参考文献など・頻出集合およびその応用 (’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/ ・中野・宇野・有村（’03～）順序木・無順序木の多項式時間頻出列挙２．２コンテストの結果計算機実験： FIMI04 ・ FIMI: Frequent Itemset Mining Implementations － ICDM (International Conference on Data Mining) サテライトワークショップで、頻出／頻出飽和／極大頻出集合列挙のプログラムコンテストを行った。2回目。3回目はなし・第1回は15、第2回は8個の投稿があったルール：－ファイルを読み、列挙してファイルに書くこと－ time コマンドで時間を計測（メモリも他のコマンドで計測）－ CPUを制御する命令（パイプラインなど）は使用禁止計算機実験： FIMI04 ・計算機環境：CPU、メモリ: Pentium4 3.2GHz、1GB RAM OS、言語、コンパイラ: Linux 、C言語、gcc ・データセット：－実データ：疎、アイテム数大－機械学習用データ：密、アイテム数小、規則的－人工データ：疎、アイテム数大、ランダム－密な実データ：超密、アイテム数小 LCM（宇野有村清見）、見事優勝賞状と賞品賞品は {ビール, 紙おむつ} “Most Frequent Itemset” だそうです実データ（すかすか）平均の大きさ5-10 BMS-POS BMSWebView2 retail 実データ（すかすか）メモリ使用量 BMS-POS BMSWebView2 retail 密（50%程度）で構造があるデータ pumsb connect chess 密で構造があるデータ、メモリ量 connect pumsb chess 密な実データ＆巨大データ accidents accidents メモリ web-doc 他の頻出パターン・末広がり性、含まれる項目の絞込み、データベースの縮約は他の頻出パターン発見でも使える技術－文字列、シークエンス、系列データ－行列－幾何データ、図形、ベクトル－グラフ、ツリー、パス、サイクルパターン {A,C,D} XYZ 項目 {A,B,C,D,E} AXccYddZf ２．３全張木列挙の高速化連結成分の列挙・与えられたグラフの、頂点 r を含む頂点部分集合で、連結になっているものを列挙する問題・現在の解に隣接する頂点を選び、その頂点を含むものの列挙と、含まないものの列挙に分割  再帰的に列挙効率的な計算・現在解に隣接する頂点を動的に管理すれば、高速計算可能・現在の解に隣接する頂点の集合と、追加頂点に隣接する頂点の集合の和集合を取ればいい  各反復に O(候補数) 時間効率的な計算・各反復で2つ再帰呼び出しする  反復数＜２×解数 v を使わない O(1) v を使う O(d(r)+d(v)) 使わない使わない・・・使わない使わない・各反復が自分の右の子から始まる左下パスの反復にO(1) ずつ計算時間を配る  各反復に O(1) 時間  各解に O(1) 時間全張木の列挙・全張木とは、グラフの全ての頂点を含む木のこと・ある枝を選び、その枝を含むものの列挙と、含まないものの列挙に分割  再帰的に列挙再帰が深くなると・再帰が深くなると、枝数・頂点数が減る・セルフループ、ブリッジも増える・セルフループは必ず使わない枝、ブリッジは必ず使う枝なので、グラフから消せる  グラフが小さくなる  計算木の末端での計算時間が短くなる再帰呼び出しのコピー・ k 本の多重枝に関する分割  どれか一本を使う問題がk 個・ k 本のサイクルもどき多重枝に関する分割  どれか一本を使わない問題がk 個  k 個の問題が短い時間で作れる・グラフが小さくなるときは、ブリッジ・セルフループがたくさんでき、たくさんの子問題を作るように変更できる。後は演習３．探索の難しさ３．１場合分け的なアプローチ充足可能解の列挙・充足可能解とは、与えられた論理式を満たす真偽値の割当て（x1∨x2∨￢x3） ∧ （￢x1∨x2∨x4）∧・・・∧（￢x5∨x4）・充足可能解を見つける問題はNP完全  列挙するのも、当然難しい・それでも列挙しようとしたら、どうするか？  場合分けと枝刈り（分枝限定法）が一般的分枝限定法・１つ１つ、場合分けをするように変数の値を決めていく・それぞれの値について、再帰呼び出しを行う・値を決めて行き、最後まで決めたら解がひとつ見つかる・途中で、分枝の先に解がないことが確認できたら、探索を打ち切る v1, v2  この精度・速さが鍵正確∩多項式なら、多項式遅延￢v1 v1 v1, ￢v2 ￢v1, v2 ￢v1, ￢v2 限定操作・現在の分枝の先に解がない  この先、どのように変数の値を決めても、充足できない（x1∨x2∨￢x3） ∧ （￢x1∨x2∨x4）∧・・・∧（￢x5∨x4）（x1∨x2∨￢x3） ∧ （￢x1∨x2∨偽）∧・・・∧（￢真∨偽）・途中で解が見つかる  途中で充足してしまった・充足可能性の判定は通常たやすいので、速く動きそう単調性を満たす族・集合族は、集合の集合・集合族 F の任意のメンバーの部分集合が F に含まれる  F は（逆）単調性を満たす、という－頻出パターン、クリーク、森、非連結なグラフ・・・・単調な集合族のメンバーの列挙は簡単だが、極大なメンバーの列挙は難しい  他のメンバーに真に含まれなければ極大単調性を満たす族・極大な要素の列挙は、比較的枝刈がしやすい ① いったんメンバーでなくなったら、枝刈できる ② 残り全部を追加してもメンバーなら、分枝の必要がない・ ①を完璧にやっても、メンバーを全部探索してしまうと非効率・１つ極大を見つけ、その要素を再帰の最後のレベルに寄せると、「寄せた部分までを全て使わない」という再帰が不要になる  ②にうまくはまる！再帰の方向解の大きさが30までなら、実用上はほぼ十分単調性を満たす族・バックトラック的な書き方で、アルゴリズムを記述（○○を使わない、を再帰でなくループで処理）極大列挙（P：現在の解, I：決定していない要素） P∪I に含まれる解の中で極大なもの S を見つける if S が極大解 output S for each e∈I＼S call 極大列挙（P∪e, I）; I := I＼{e} 再帰の方向 P I ３．２飽和集合の列挙頻出集合の問題点・面白い頻出集合を見つけようとすると、σを小さくする必要がある  大量の頻出集合が出てくる・情報を失わずに、頻出集合的な、数の少ないものを見つけるようにモデルを変えたい 111…1 １．極大頻出集合：他の頻出集合に含まれない頻出集合２．飽和集合：出現集合が等しいものの中で極大なもの 000…0 極大頻出集合と飽和集合の例・頻出集合を出現集合で分類 1,2,5,6,7,9 2,3,4,5 D＝ 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万個２部グラフによる表現・アイテム、トランザクションを頂点とし、包含関係を枝とする 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 隣接行列で見ると・アイテム、トランザクションを頂点とし、包含関係を枝とする 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 1 1 B 1 1 1 1 1 1 1 1 C 1 1 1 1 1 D 1 1 1 1 1 E 1 F 1 ・アイテム集合と、それらを含むトランザクションの集合  全てのセルに1が入っている部分行列飽和集合の列挙手法・頻出集合列挙ベース－頻出集合列挙アルゴリズムをベースに、多少無駄な計算を省く－飽和集合のよさが出ない。計算時間の改善も少ない・保存＋枝狩り－見つけた解を保存し、それを用いて無駄な分枝を刈る－計算速度はまあまあ－解保存のためにメモリを使用し、それがひとつのネック・逆探索＋データベース縮約－計算効率が良い－解保存用のメモリが不要（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 2,3,4,5 出現集合が隣接親子関係（ppc拡張） 1,2,7,8,9 1,2,5,6,7,9 2,7,9 子どもを求める・子どもから親を作る際に抜いた、最後のアイテムを親に追加すると、出現集合は子どもと等しくなる  子どもは、アイテムを１つ追加して、出現集合の共通部分をとると得られる  とはいえ、そのようにして作ったもの全てが子どもになるとは限らない  子どもである条件は、抜いたアイテムより前の部分に、新しくアイテムが追加されないこと（prefix preserving closure extension, prefix保存飽和拡張）データベースの縮小・頻出集合と同じように、データベースの縮小をしたい・追加したアイテムの前半部分を捨てられない  ppc 拡張の際に参照されるので・しかし、－後半が同一なら、必ず同時に Occ に入る－必要なのは前半（prefix）の共通部分だけなので、前半の共通部分をとり、保存すればよい・多くのトランザクションが1つになれば、自然に共通部分も小さくなる１１２２５６４７４３２４４３１ θが小さいときと速度の大きな差はない３４４５６７６７６７比較の手間・K+e の出現の共通部分、素直に計算してもよいが、「共通部分がKと等しいか」を調べるだけなので、必ずしも全て計算する必要はない  異なることがわかった時点で、計算をやめてよい・ K+e の出現それぞれを小さい順にたどり、 K 全てに共通するものがあるか調べる 3 4 6 9 11 ・全てに共通するものがあったら K に入っているか調べる・前回たどったところで止まっておき、次回はそこからたどる 4 11 1 3 4 5 9 11 K+e の出現集合 23 4 5 9 11 1 2 4 6 9 11 1 4 9 11 ビットマトリクス・スウィープポインタは、行列の形でデータを持ってないがゆえの工夫。隣接行列を持って入れば、もっと単純に速くできる・が、隣接行列は、大きすぎて構築することすら不可能・出現集合がある程度以下に小さくなったところで、行列を構築しよう  ビットで持てば、各列が1つの変数に入る！ビットマトリクスの定数時間計算・各アイテムに対応する列を１変数で持っていると、K+e の出現全てにそのアイテムが含まれるかどうか、1ステップでチェックできる・ K+e の出現のビットパターンと、アイテム i の列のビットパターンの AND をとる・アイテム i が K+e の出現全てに含まれるなら、共通部分はK+e の出現ビットパターンと等しくなる K の頂点・・・ K<i ∩N(vi) 実データ（すかすか）平均の大きさ5-10 BMS-POS BMSWebView2 retail 実データ（すかすか）メモリ使用量 BMS-POS BMSWebView2 retail 密（50%程度）で構造があるデータ connect pumsb chess 密で構造があるデータ、メモリ量 connect pumsb chess 密な実データ＆巨大データ accidents accidents メモリ web-doc 探索の難しさ：極大クリークの列挙クリーク列挙問題グラフのクリーク：部分グラフで、全ての頂点間に枝があるもの・ 2部クリークの列挙は、グラフの変換でクリーク列挙に帰着可能・最大クリークを求める問題はNP完全・極大クリークは簡単に求められる・最適化を中心に非常に多くの研究がある・大規模かつ疎なグラフでの、クラスタリングなどの応用が多いクリークの単調性・クリークの部分集合はクリーク  単調性が成り立つ  原点を出発して山を登り、クリークでなくなったら、戻って、他の方向に登る、というバックトラック式の列挙ができる・クリークであるかどうかのチェックはO(n2) 時間、最高 n 方向に登る  １つあたり O(n3) 時間・巨大データでは長時間 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秒間におよそ100万個）次数小さい頂点クリークの個数・実データには、比較的大きなクリークがよくある・大きなクリークの任意の部分集合はやはりクリークなので、個数は大きくなる・極大クリークのみを列挙しようクリーク－数が1/10～1/1000 に減る－任意のクリークは極大クリークに含まれるので、情報の損失がない－極大なほうが、中途半端なグループを含みにくく、モデルとして的確極大なクリークだけを上手に列挙できるか探索の難しさと枝刈り・極大クリークは山の頂上に対応  単純な操作では行きあえない・そもそも、原点のそばに極大クリークがない 111…1 ・バックトラックが通じないが、枝刈りをすると実に効率が良い（上に登っても、以前見つけた極大クリークに含まれるクリークしかみつからないとき、枝刈りをする）クリーク 000…0 ここでは、逆探索による多項式時間列挙を紹介極大クリークの隣接関係・極大クリーク K から、添え字の大きい順に頂点を抜いていく・どこかで「現在のクリークを含む辞書順最小の極大クリークK’」が K でなくなる（辞書順最小極大クリーク＝添え字の小さい順に頂点を加えてできる極大クリーク）・その K’を K の親とする（一意的に定まる）（prefix 保存飽和拡張とほとんど同じ。保存されないけど）・親は子どもより必ず辞書順で小さいので、親子関係は非巡回的  親子関係は有向根付き木を導出する逆探索親子関係は有向根付き木を導出するこの木を深さ優先探索すれば全ての解を見つけられる・探索には、子供を見つけるアルゴリズムがあれば十分・子供が１つあたり多項式時間で見つかれば、全体も多項式時間非巡回的な親子関係と、子供を見つける多項式時間アルゴリズムがあれば、なんでも多項式時間列挙ができる子どもの特徴づけ・ K[i]： K に頂点 i を加え、i に隣接する頂点を取り除きできたクリークを、含む辞書順最小のクリーク・ K' が K の子供  K[i] = K' がいずれかの i について成り立つ i K[i] だけ調べればよい（高々|V|個）・ i が K のどの頂点とも隣接しないなら、 K[i] の親は i を含む辞書順最小のクリークここが多項式性のポイント！通常は、消すものが一通りでない通常は K に隣接する i のみ調べればよい（高々（Δ+1）2個）例題・このグラフで実際の親子関係を見てみる１, ２３１３７５４１, ３, ５６２, ４, ６, ８７ 10 ８９ 12 ２４ 11 10 ３, ５, ７, ９, 12 11 ９, 11 11 ６, ８, 10 11 ８, 10, 11 ４, ８, 11 12 10, 12 例題・このグラフで実際の親子関係を見てみる１, ２３１３７５４１, ３, ５６２, ４, ６, ８７ 10 ８９ 12 ２４ 11 10 ３, ５, ７, ９, 12 11 ９, 11 11 ６, ８, 10 11 ８, 10, 11 ４, ８, 11 12 10, 12 辞書順最小の極大クリークを求める・ CAND(K)：頂点集合 K の全ての頂点に隣接する頂点の集合・ CAND(K) の中で最小添え字の頂点を K に加える、という作業を、 CAND(K) が空になるまで続ける・ CAND(K∪i) ＝ CAND(K) ∩ （iに隣接する頂点）なので、 i の次数の時間で更新可能・クリークの大きさは、最大次数 Δよりも高々1大きいだけなので、繰り返し解数は、高々 Δ＋１ O(Δ2) 時間で、「K を含む辞書順最小のクリーク」が求められる親を計算する・ K のいずれかの頂点に隣接する頂点全てについて、「 K のいくつの頂点と隣接するか」を記録（r(v)とする)  r(v) = |K| ⇒ K に追加可能・ K の最大添え字の頂点から順に消していき r(v) を更新する（ O(Δ2) 時間）  r(v) = |K| となるものができたら K に追加可能な頂点が現れたということ・その時点で、 K を含む極大クリークを見つければよい O(Δ2) 時間で、K の親が計算できる子どもを見つける通常は K に隣接する i のみ調べればよい（高々（Δ+1）2個） O(Δ2) 時間で、K[i] の親が計算できる・以上から、子どもを全て見つけるのにかかる時間はO(Δ4) であることがわかる・アルゴリズムは、各反復で極大クリークを１つ見つける極大クリークは１つあたり O(Δ4) 時間で列挙できる子どもの特徴づけ・ K<i： K に含まれる、添え字が i 未満の頂点の集合・ C(K）： K を含む辞書順最小のクリーク・ N(v）： v に隣接する頂点の集合（近傍）・ K[i] が K の子ども  ① K<i ∩N(vi) ＝ K[i]<i ② C(K<i ∩N(vi) ) ＝ K 特に ② は、が Kの親 L に対して、K ＝ L[j]、j<i となることと、 ② C(K<i ∩N(vi) )>i ＝ K>i が成り立つことが必要十分頂点 vi より前のみを見ればよい高速計算の技法・全ての集合は、配列で保持する（メモリもまとめて確保）・アクセスを良くするため、頂点の添え字順に並べておく ① K<i ∩N(vi)：普通に計算すれば、 O（|K<i|＋| N(vi)<i| )  振り分けを使って改良・ K の各頂点 vj に対し、 N(vj)>j の各頂点のバケツにvjを挿入・終了後、vi のバケツの中身は K<i ∩N(vi)  計算時間は O（|K<i∩N(vi)<i| ) ・再帰呼び出しを添え字の大きい順にすることで、バケツは再帰呼び出し内で繰り返し使える  初期設定でvi に大きさ N(vi) のバケツを確保すれば、２度と確保しないでよい計算時間・疎なグラフであれば、極大クリークの数は通常非常に小さい（頂点数の 10から100倍くらい）ソーシャルネットワークデータ： 4万頂点 6万枝  3秒辞書データ： 4万頂点 10万枝  50秒 webデータ： 500万頂点 5000万枝  1時間くらい？ … 現実的な疎データでは、だいたい全列挙可能と考えてよい参考文献など・築山らのアルゴリズム (‘78) 初の多項式時間アルゴリズム・宇野らのアルゴリズム (‘03) 改良版。大きく疎なデータでも速い・富田らのアルゴリズム (‘04) 枝刈りを用いた列挙。密でも速い・クリークの応用の文献は星の数ほど(Nature などにもある) “クラスタリング” + “クリーク” などで検索・実装 MACE: (MAximal Clique Enumerator) http:research.nii.ac.jp/~uno/ 宇野のHP ４．出力が多くない列挙問題解の数が少なくても・通常、列挙問題として考えられる問題は、解が組合せ的で、最悪で指数個存在する・そのような列挙問題で重要だったのは、解の数に対する計算時間。１つ見つけるのに、平均どれくらいの時間がかかるか・この概念は、解の数がそれほど多くない問題でも重要・出力が組合せ的でない例をいくつか見てみよう４．１．計算幾何学の列挙問題計算幾何学・ computational geometry のこと。（計算機科学ではない）・幾何学的なデータをどのように扱い、問題をどのように解くかを探求する分野・幾何学的な構造を出力するときは、単なる数値を出すだけではないことが多く、そうなると出力の大きさは O(1) ではない・凸包構成問題と線分交差判定問題を紹介する凸包・平面上（一般には d 次元空間上）にある点集合を含む最小の凸多角形（多面体）を見つける問題・計算幾何学の３大基礎問題のような位置づけ・出力の大きさは多角形の辺の数なので、最大 n ・ O(n log n) 時間で解ける。ソートが帰着できるので、これは最適余談：一般次元だと・３次元以上だと、面を出力する問題。面の数は O(nd/2) だそうです。・幾何変換をすると、面で与えられた多面体の端点を出力する問題になる (a1,…,ad) => a1x1,…,adxd = c 行進法・ y軸方向に一番下にある点を見つける。タイがあるときは、一番右のものを選ぶ・そこからラップを包むように凸包の辺を見つける・計算時間は、辺を見つける時間 × 辺の数・出力の大きさに線形のアルゴリズム次の辺を見つけるには・現在の頂点から、各頂点へのベクトルを求める・時計回り順で一番最後になるベクトルが、次の辺・計算時間は O(n)。最適ではないが、出力数依存・実際、ランダムな点配置では、辺の数は O(log n) 程度だそうだ辺を１つずつ見つけるところが、出力数依存にきいている線分交差判定問題・平面上（一般には d 次元空間上）にある線分の集合に対して、どの線分の組が交差するか調べる問題・出力は辺の組なので、最大 n2。最悪、全部が交差する。・２つの線分の交差判定は O(1) 時間でできる・単純に全ての組を比較するアルゴリズムは、入力の大きさの意味では最適なアルゴリズム・出力数依存のアルゴリズムが作れるか？スイープ法・垂直な走査線を一番左から一番右へと移動し、途中にある交点を１つずつ見つける・ ① 線分の始まり ② 線分の終わり ③ 交点をイベント点として、イベント点をたどってスキャンする・次に来そうなイベント点を、x 座標をキーにしてヒープに突っ込み、小さいものから順に取り出すスイープ法・走査線上で隣り合う線分のみ、交点があるかどうか調べる  交わる２つの線分は、交点直前のイベント点で必ず隣接するので、これだけで全部見つけられる・時間は（イベント点数）×（ヒープ操作時間）＝ O((n+K)log n)  交点の数 K に対して線形時間隣り合うものだけを見ることで、全部見ないですむ他にも－文字列マッチング（部分文字列としてマッチするところを見つける）－時系列データの中から、要素の平均が大きな区間を見つける問題－平面上に与えられた頂点集合を含む、何らかの条件を満たす極小な四角を見つける問題４．２類似項目の列挙類似項目の発見・工学的な基礎的な問題でも、解の少ない列挙問題はある・データベースの項目の中で、似た項目のペアを全て見つける（項目のペア全てについて、 2項関係が成り立つかを調べる）・類似している項目の検出は、データベース解析の基礎的な手法  基礎的なツールがあれば、使い方しだいでいろいろなことができる（大域的な類似性、データの局所的な関連の構造・・・）類似項目発見の計算時間・似たもののペアを全て見つけるさい、項目のペア全てについて、単純に全対比較を行うと項目数の２乗の時間がかかる  項目数が100万を越えるころか現実的には解けなくなる 100万×100万 ÷100万（演算per秒） = 100万秒・類似検索を使う手もあるが、100万回のクエリを実行しなければならない。類似検索は完全一致より大幅に時間がかかる  1秒間にクエリが1000回できるとして、1000秒問題が大きいので、平均的な意味でよいので、計算オーダーの小さいアルゴリズムがほしい応用１：リンクが似ているwebページ・リンク先、あるいはリンク元が、集合として似ているページは、よく似ていると考えられる  サッカーのページ、料理のページ、地域のページ・グループ化すれば、コミュニティー発見、著名なトピック、web の構造の解析など、いろいろなことがやりやすくなる・さらに、例えば、「スパムサイト」の検出にも使えるかも（レポート課題のコピーの検出、とか）応用３：長い文章の比較・（文庫本のような）長い文章がいくつかあるときに、類似する部分がどことどこにあるかを検出したい  長い文章の比較はそれ自体が大変（時間がかかる）ので、複数あると手が出ない・長い文章を、短い文字列にスライスし、全体を比較する  大域的に似た部分は、局所的に似ているところを多く含むと思われるつまり、似ている短い文字列のペアを多く含む・短い文字列の全対比較からアプローチできる応用５：特異的な部分を見つける・似ているものがない項目は、データの中で特異的な部分と考えられる－携帯電話・クレジットカードの不正使用－制御システムの故障・異常の発見－実験データから新しいものを発見－マーカーの設計（「宇野毅明のホームページは、”助教授，宇野毅明の研究”で検索するとユニークに定まる）・比較的大きなデータが複数あるような場合でも、特異な項目を多く含むもの、他のどのデータとも、似ている部分が少ないものは、特異なデータだと考えられる・「似ている項目の数」は、データがエラーを含む際の統計量として使えるかも知れない問題設定：短い文字列の比較・具体的に見るため、扱うデータベースと問題を具体化する問題：各項目が同じ長さ l の短い文字列（50文字程度）であるデータベースを入力したときに、文字列のペアで異なり数が d 文字以下である組を全て見つけよ（ハミング距離がd 以下）・全ての項目が同じだと、およそ（項目数）2 個の出力がある・現実には、やたらと似てるものがあるものを比較しても意味が無い  出力は少ないと仮定する例題・ ABC、ABD、ACC、EFG、FFG、AFG、GAB のペアでハミング距離が1以下のものを求めよ A A A E F A G B B C F F F A C D C G G G B G A A A E F A A B B C F F F B C D C G G G A A A A E F G B C B F F F A C C D G G G B A A A A E F G B B C F F F A C D C G G G B イメージ的には・似ているもののペアを探す問題は、マトリクスのセルの中で必要なものを全て見つける問題・全対比較は、マトリクスのセルをすべて見ていることに対応・分類によるアルゴリズムは、分類を順々にしていると思えば、木構造の探索を行っていることに対応ゲノムの比較 (2) ヒトX染色体とマウスX染色体の比較・ 30文字で間違い2文字以下のペアを列挙・長さ3000、幅300 の領域に3つペアがあれば点を打つ PCで 1時間で可能 X ・ノイズをかなり除去できているマウス染色体ヒトX番染色体４．３包含関係の列挙問題の定義入力：部分集合族（トランザクションデータベース） D = {T1,…,Tn} （ただし、各 Ti はアイテム集合 E = {1,…,n} の部分集合）＋閾値 θ 出力： |Ti∩Tj| がθより大きいような、全てのTi 、Tjのペア例：閾値 θ=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 D が巨大かつ疎で（各Ti が平均的に小さい）、出力の数がそれほど多くない（ ||D|| の数倍）状況での高速化を考える単純に全対比較すると・単純に全対比較するアルゴリズムを考える D ＝ for i=1 to |D|-1 for j=i to |D| if |Ti∩Tj|≧ θ then output (Ti, Tj ) 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 ・共通部分の計算は、各 Ti をアイテム順でソートしておき、Ti 、Tj をマージソートのように並行してスキャンすればよい。時間はO(|Ti |＋| Tj|) ・全体の計算時間は ∑i,j(|Ti |＋| Tj|) = 2n ||D|| かなり時間がかかると見てよい振り分けによる高速化・各Ti に対し、|Ti∩Tj|がθ以上になるものを見つける問題を考える・各アイテム e に対して、e を含む部分集合の集合を D(e) とする・ Ti が含む各 e に対して、D(e) の各 T に対して、カウントを１つ増やす、という作業をする  全ての e∈Ti についてこの作業をすると、各 Tj のカウントは |Ti∩Tj| になる for each e∈Ti for each Tj∈ D(e), j>i, do c(T)++ ・ D(e) を添え字順にソートしておくと、j>i である Tj∈ 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 振り分けの計算時間 for each e∈Ti for each Tj∈ D(e), j>i, do c(T)++ ・計算時間は ∑j ∑e∈Ti |{ Tj∈D(e), i<j}| ＝ ∑e |D(e)|2  |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 1再帰呼び出しの計算時間のイメージ・普通に頻出度の計算をすると各 X＋e に対してデータを一回スキャンする・共通部分による計算は D(e) と D(e) のをスキャンする  D(X) を n-t 回スキャンし、データベースの t より大きなアイテムをスキャンする・振り分けは D(X) に含まれるトランザクションの t のをスキャンする t より大きなアイテムをスキャンする (n-t)個＋ t t (n-t)個計算実験・ 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分簡単に追加できる条件・ |A∩B| が、|A| のα倍以上、(and/or) |B| のα倍以上・ |A∩B| / |A∪B| ≧ α ・ |A∪B| －|A∩B| ≦ θ など。この手の、共通部分や和集合の大きさから計算できる評価値であれば、簡単に評価できる・計算時間は、ほぼ線形で増えていくと思われるので、多少大きなデータでも大丈夫まとめ・列挙アルゴリズムの展望：不整データと解候補列挙・列挙アルゴリズムの難しさ：解きたい問題に合わせた努力・高速化の方法：末広がり的な構造を使い、末端を高速化－頻出集合：データベース縮約－頻出集合：頂点次数の管理・難しい問題に対する手法：－分枝限定法：探索順の変更による、枝刈りの効率化－極大クリーク：探索順の変更による、枝刈りの効率化面白い研究・ビジネスを目指してがんばってください５．演習問題演習：初級１ ① 数 a1,...,an を入力し、合計が b 以下となる組合せの中で極大なものを全て列挙する（多項式時間）アルゴリズムを設計せよ。（ヒント：数をソートしておくといいことがある） ② 無向グラフとその頂点 s と t を入力し、s と t を結ぶパスを列挙するアルゴリズムは、分割法で簡単に設計できる。 (sに接続する枝の、どれを選ぶか、で分枝する) この問題を大規模なネットワークで解くときには、モデルとしてどのような点を気をつけるべきか。また、高速化を行うには、どのような点を注意すればよいか。 ③ グラフを入力し、その枝2連結である部分グラフで極小なものを列挙するアルゴリズムを、講義の設計法に沿って設計せよ。多項式性は問わない演習：初級２ ④ 2次元平面上に定義された各辺が軸に平行な長方形の集合が与えられたとする。このとき、これら長方形の共通部分によって作られる長方形を列挙したい。このような列挙問題に対して、解の数、列挙法について論ぜよ。 ⑤ 数列 a1,...,an に対して、その部分列 b1,...,bm で、bi＞bi+1が任意のiについて成り立つものを降順列とよぶ。（部分列は、列から一部の数を順番を変えずに取り出したものである。）与えられた数列 a1,...,an の極大な降順列を列挙するアルゴリズムを設計せよ（ただし、数列内の任意の2つの数は異なるとする） ⑥ 状態の集合 V の上で定義されたマルコフ過程があるとする。このとき、ある状態 S∈V から出発し、10回の遷移を行って得られる状態の列を全て列挙するアルゴリズムを設計せよ。また、その高速化手法について論ぜよ。演習：初級３ ⑦ グラフとその頂点s を入力し、sから始まるハミルトンパスを全て列挙するアルゴリズムを設計せよ。多項式性は問わない演習：中級１ ① 頂点が平面上の点の集合であり、各枝が点対を結ぶ線分であり、かつどの２つの線分も内点を共有しない（真に交わらない）ようなグラフを平面埋め込みグラフという。極大な平面埋め込みグラフは、外面を除くすべての面が3角形になることが知られている。与えられた2次元上の点集合に対し、それを頂点集合とする極大な平面埋め込みグラフの列挙問題を、部分グラフの列挙問題に帰着して解く方法を論ぜよ。 ② 無向グラフの s-t パス、サイクル、全張木の間に、列挙の帰着関係を示せ。（どれを使うとどれが解ける、これよりこれが解が多い等） ③ 木 T が与えられたとき、T の葉を逐次的に取って T が空となるまで取って、得られる頂点の列を T の葉除去列とよぶ。全ての葉除去列を列挙するアルゴリズムを構築し、高速化の可能性を議論せよ。また、計算量を算定せよ。演習：上級１ ① グラフ G=(V,E) と整数 k を入力し、G[U] の最大次数が k 以下となるような U を列挙する問題を解くアルゴリズムを構築し、高速化を行うにはどのようなことを行えばよいか、論ぜよ。また、そのようなものの中で極大なものだけを列挙する多項式性アルゴリズムは存在するか、論ぜよ。 ② 全張木の列挙問題に対する講義中のアルゴリズムの計算時間を算定せよ ③ 各項目が同一の頂点集合を持つグラフであるようなデータベースがあるとする。このとき、枝の差分が k 本以内であるような項目の組を列挙するアルゴリズムを設計せよ