Document

近年の列挙技術の進展
ー計画立案と解法ー
宇野毅明（情報学研究所）
有村博紀（北海道大学）
中野眞一（群馬大学）
佐藤寛子（情報学研究所）
佐藤健（情報学研究所）
清見礼（情報学研究所）
2006年 9月11日 OR学会第56回シンポジウム
列挙問題とは何でしょう
列挙問題：与えられた問題の解を全て重複なく見つけ出す問題
・グラフの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
いかに効率よい探索ルートを作り、短時間で移動するかが課題
事例研究の評価
モデル
入力の大きさ、事後処理のコストに対して、解数が十分小さいか
データの性質などから解数を見積もり、求解時間を算定
－極大性、代表解の選出などがうまく使えているか
アルゴリズム
解１つあたりの計算時間が十分短いか
計算量と理論的根拠に基づく計算時間の算定
－出力数依存の計算手法になっているか
－余計な組合せを見ない、効率よい探索
－疎性、パワー則などの上手な利用
－末広がり性を利用した反復的な問題縮小
列挙事例：クリークの列挙
クリーク列挙問題
グラフのクリーク：部分グラフで、全ての頂点間に枝があるもの
・ 2部クリークの列挙問題は、グラフの変換でクリーク列挙に
帰着できる
・最大クリークを求める問題はNP完全
・極大クリークは簡単に求められる
・最適化を中心に非常に多くの研究がある
応用：クラスタリング
対象：データの関連を現すグラフ
（データの項目が頂点、関係のある、類似する項目間に枝）
類似する、あるいは互いに
関連するグループ
互いに背反だが、
立場が同じ項目のグループ
・データの種類・規模で大きさが変わる
・通常、それほど密ではない（次数高々100）
・局所的に密な部分が存在
・パワー則、スモールワールドが成り立つことが多
応用：ウェブコミュニティーの発見
対象：ウェブネットワーク
（ウェブページが頂点、リンクが枝）
グループになっている
リンク先
（同種のテーマ）
リンク元
（似た興味）
・グラフの大きさは世界全体で100億ページ
・ある種のドメインに区切ったり、意味のないページを除くと
1/10 から 1/1000 に小さくなる
・平均次数は10程度だが、局所的に密な部分が存在
・パワー則、スモールワールドが成り立つ
類義語群の発見
対象：単語ネットワーク
（単語が頂点、単語AとB を組合せて
複合語ができるとき、枝を張る）
関東
地方
関西
地区
中国
電力
北陸
2部クリークの片側が、
似た意味を持つ単語の集合
・大きなものでも、15万語程度
・通常、それほど密ではない（次数高々200）
・局所的に密な部分が存在
・パワー則、スモールワールドが成り立つ
類似論文のグループ化
対象：論文・アブストラクトグラフ
（論文が片側の頂点、単語がもう
片側の頂点で、論文のアブストラクト
が単語を含むときに枝を張る）
論文A
論文
論文C
語1
語2
語3
論文D
語：研究分野を表す単語群
論文：その分野の論文のグループ
・大きなものでも、10万語程度
・通常、それほど密ではない（平均次数高々200）
・局所的に密な部分が存在
・パワー則、スモールワールドが成り立つ
クリークの単調性
・クリークの部分集合はクリーク
 単調性が成り立つ
 原点を出発して山を登り、
クリークでなくなったら、
戻って、他の方向に登る、
というバックトラック式の
列挙ができる
クリークであるかどうかのチェック
はO(n2) 時間、最高 n 方向に登る
 １つあたり O(n3) 時間
111…1
クリーク
000…0
1,2,3,4
1,2,3 1,2,4
1,2
SQL でもかけるが、巨大データでは長時間
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
現実的には１つあたり定数時間で列挙できる
（1秒間におよそ10万個）
計算時間
・疎なグラフであれば、極大クリークの数は通常非常に小さい
（頂点数の 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
列挙事例：頻出パターンの列挙
頻出パターンの列挙
データベースの中に多く現れるパターンを頻出パターンという
データベース：トランザクション、ツリー、グラフ、多次元ベクトル
パターン：部分集合、木、パス・サイクル、グラフ、図形
 データの解析、特徴分析、知識・ルール発見
データベース
実験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
．
．
．
多く現れる  頻出する
多く現れるものを見つけるために、多く現れるとは何か、を決める
・データベースが項目の集まりだとする
・パターンに対して、そのパターンを含む項目を出現という
・出現の数（頻出度）が閾値より大きければ、良く現れるとする
（含む、の定義は、集合で行ったり、文字列の
包含、グラフの埋め込みなどで定義する）
パターン
{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}
バスケット分析
・スーパーなどの小売店舗で、同時に購入される事の多い品物
の組を知りたい
・客が購入した品目  トランザクション
・品目の組で、多くの客が購入したもの
 多くのトランザクションに含まれるアイテム集合
 （あるθに対する）頻出集合
● 牛乳、弁当
「おむつとビールの組合せが良く売れる」
という発見が有名
● お茶、弁当
● おにぎり、雑誌
● はさみ、のり
● ラーメン、はし
● こっぷ、皿
● 弁当、おにぎり
．．．
データベースの比較
・２つのデータベースが、意味的にどの程度似ているか知りたい
 大きさの違い、ノイズは無視したい
・各アイテム、属性などの総数だけでは、組合せがわからない
・組合せを細かく見ると、ノイズに振り回される
頻出集合を列挙することで、
組合せ的な特徴を比較できる
データ
ベース
データ
ベース
・いろいろな言語の辞書データ
・異なる種のゲノムデータ
・文書集合の単語データ（新聞のデータ、雑誌のデータなど）
・顧客のデータ
分類ルール、特性の発見
・データの特徴を現す規則、あるいは正例・負例を分類するような
規則が知りたい（A,B,C が含まれている、A,B が含まれれば、C
が含まれる、など）
・多く現れる組合せを用いないと、仮定部分を満たすものが少なく、
ルールとして意味がない
・組合せを細かく見ると、ノイズに振り回される
頻出集合を仮定に用いることで、
信頼度の高いルールを
効率良く見つけられる
データ
ベース
正例
・実験データ
・利用者履歴データ、マーケッティング
データ
ベース
負例
頻出パターンの単調性
・頻出パターンの部分パターンは頻出
 単調性が成り立つ
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万個
飽和集合の隣接関係
・飽和集合から、添え字の大きい順に要素を抜いていく
・どこかで出現集合が大きくなる
・その出現集合の飽和集合を求める
・こうして求めた飽和集合を、親とする（一意的に定まる）
・親の頻出度は必ず真に大きいので、親子関係は非巡回的
 親子関係は有向根付き木を導出する
逆探索
親子関係は有向根付き木を導出する
この木を深さ優先探索すれば全ての解を見つけられる
・探索には、子供を見つけるアルゴリズムがあれば十分
・子供が１つあたり多項式時間で見つかれば、全体も多項式時間
（親に要素を１つ加えて極大をとった飽和集合が子供になる）
非巡回的な親子関係と、子供を見つける多項式時間アル
ゴリズムがあれば、なんでも多項式時間列挙ができる
親子関係の例
・データベースの全ての
飽和集合とその親子関係
φ
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パターン程度
参考文献など
・頻出集合およびその応用 (’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
列挙事例：コードレスサイクルの列挙
化合物の立体構造の推定
・新たな化合物が得られたときに、その組成は比較的容易
に得られるが、結合の構造は容易に計測できず、さらに立
体的な構造の計測はもっと難しい
NO2
NO2
C6H5NO4
O
化合物
組成
OH
平面構造
すでに構造がわかっている化合物の
データを検索して、構造を推定する
OH
O
立体構造
化合物の立体構造の推定
・推定する化合物と部分的な平面構造が一致する化合物を
データベースから探し出す
 大域的な構造が拾えない
・検索結果を、環構造の複雑さ
で絞り込む
 立体構造の要因が入り、精度が増す
遺伝ネットワークの依存関係の解析
・遺伝子を頂点とし、遺伝子Aが発現すると、遺伝子Bに影響を
与え、発現するときに枝を引いたグラフを遺伝ネットワークという
・循環している系を見ようとすると、
サイクルの構造が必要
 サイクルを列挙することで、
どのような構造があるかを解析する
A
B
F
C
E
D
分割法による列挙
・サイクルの集合は、単調性を満たさない
 バックトラックは適用できない
111…1
・分割法というアルゴリズムを使う
000…0
・最初の枝を選ぶ
・片方の端点に接続する枝それぞれについて、
「その枝を使うサイクル」を再帰的に列挙する
・ただし、サイクルができない枝は行わない
・最初の枝の、もう片方の端点に帰って
きたところでサイクルがひとつ見つかる
サイクルの存在のチェック
・効率良く列挙するためには、選択した枝を含むサイクルが存
在するかどうかを短時間でチェックする必要がある
・今まで選択した枝でできるパスの内点を全ての抜いたグラフ
で、端点から端点へ行ければサイクルが存在
グラフ探索1回でできる
探索1回で、加える枝
全てをチェックできる
１つあたりグラフの大き
さの時間で列挙できる
末広がり性の利用
・再帰構造の下の部分では、選択したパスの両端点が近い
 幅優先探索でチェックを行えば、
グラフ
小さい範囲しか探索しない
・再帰が深くなるほど、
反復が短時間で終了する
実用的には、１つあたり定数時間で列挙できる（1秒10万個）
・しかし、通常サイクルの数は多い
コードレスサイクルの利用
・ショートカットを持たないサイクルをコードレスサイクルという
・冗長なサイクルはコードレスにならない
（ある意味で極小）
・サイクルの本質部分が見える
応用上もありがたい
・少々の変更で、同様に列挙できる
（すでに通った頂点の隣を通ると、
コードができてしまうので、それを避ける）
化合物データのコードレスサイクル数は小さい
400原子程度の化合物でも高々10万程度  1-2秒
列挙事例：類似項目ペアの列挙
データベースから類似する項目を見つける
・データベースの、何と何が似ているか、構造が知りたい
（近接グラフを作る、クラスタリング、アラインメント、部分比較）
ATGCCGCG
GCGTGTAC
GCCTCTAT
TGCGTTTC
TGTAATGA
．．．
・ ATGCCGCG と AAGCCGCC
・ GCCTCTAT と GCTTCTAA
・ TGTAATGA と GGTAATGG
．．．
・全部のペアが似ていると、２乗の時間がかかる
 単純な全対比較が（計算量の意味で）最適
項目数が 1000万個程度でも、素直に全対比較は1年以上かかる
・類似の他の尺度、ベクトルデータ、包含関係などでも同様の問題
応用：類似する文字列のペア
・多数の短い文字列の中で，類似する（異なりがd文字以下）ペアを全
て見つける
 長い文字列データ（ゲノム情報）の，類似部分の候補を絞り込む
 多数の長い文字列データの，類似するペアの候補を絞り込む
ATGCCGCG
GCGTGTAC
GCCTCTAT
TGCGTTTC
TGTAATGA
．．．
・ ATGCCGCG と AAGCCGCC
・ GCCTCTAT と GCTTCTAA
・ TGTAATGA と GGTAATGG
．．．
・長い文字列を比較するとき、どこが似ているか検出できる
（似ている部分は、多量の似ているペアを含む）
・大量の文書データのどの項目のどの部分とどこが似ている、
という情報が得られる
基本のアイデア：多方向からの分類
・２つの文字列の異なりが、どこにあるか、に注目する
・逆に、「異なりの場所がこことこことここ」と指定したときに、
類似するペアを見つける問題を考える
文字列ソートで線形時間
AC T CG T
AC G CG A
・「異なりの場所」の組合せ全てを尽くすと
GA G TG A
全ての似ているペアが見つかる
GA C TG C
TG G TG A
・さらに、再帰的な分類、末広がり性、
枝刈りを用いると、相当に高速化される
ゲノムの比較
ヒト21番染色体とチンパンジー22番染色体の比較
・ 3000万文字の文字列×2 から、30文字の切片を3000万個取る
・類似するペアを見つける
・横方向がヒト、縦方向がチンパンジー、というマトリクスを作って、
類似するペアがたくさん
ヒト 21番染色体
あるセルの色を白くする
・白い部分が
「似ている可能性のある部分」
・黒い部分が
「(絶対に)似ていない部分」
PCで 3-4時間で可能
チ
ン
パ
ン
ジ
ー
22
番
染
色
体
最後に：難しい問題
・組合せ的でないもの（解がベクトルなど、連続値を取るもの）
（施設配置問題の局所最適解、など）
・そもそも解を１つ見つけるのすら困難なもの
（最短順回路の列挙、最大安定集合の列挙、など）
・同型なものが多数あり、判定が難しいもの
（グラフの列挙、2部グラフの列挙）
・データが大きな上、求解に疎性が使えない場合
まとめ
・列挙は多面的で、データの全体を解析できる
・出力数依存アルゴリズム、解数の小さいモデルの重要性
・データ中心の科学：あいまいな目的に対する解候補の列挙
・極大、代表の利用で解数が小さく意味的に良いモデルの構築
・分割法・逆探索により効率な探索
・分類、末広がり性の利用が大規模データに対する高速処理の鍵
・列挙は、手法の中でまだまだ発展途上
・これから利用価値が高まり、モデル・アルゴリズムともに、
面白いものが出てくるだろう

Download Report