Document

発見問題に対する
列挙手法を用いた探索
宇野毅明（国立情報学研究所
＆総合研究大学院大学）
2007年9月27日産業総合研究所
計算からのアプローチ
・発見的な目的を持つアルゴリズムは、多くの研究がある
－画像・音声などの認識
－遺伝子予測など
－クラスタリング
－類似構造の検出
・モデリング、計算の難しさから、ヒューリスティックに基づく探索を
行うものが多い
利点：よいと思われるものが見つかっている、かな？
課題：何を見つけているのかわかりにくい
条件をいろいろ入ると、計算的にコストが増える
・ここでは、「アルゴリズム理論」から課題を見つめたい
アルゴリズム理論からの観察
・データマイニング的な問題では、モデリングの目的は多くの場合
「面白いもの」「役に立つもの」
 そもそも数理化・定式化困難
 基本的な条件だけを搾り出し、アルゴリズム設計の観点から有
利なモデル化をしてみよう
 そのさい、入力と出力をしっかり決めて、問題をしっかりと定式
化する（使いやすく？なる？）
・実際には、基本的な問題を解いて得られる解に、オーダーメード
的な処理をして質を高めるという使い方が一般的
 候補を見つけ、必要なものを絞り込む "列挙的なアプローチ"
列挙問題
列挙問題：与えられた問題の解を全て重複なく見つけ出す問題
・グラフの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 を結ぶパスを列挙せよ
解）
…
近年、広く使われ始めている
列挙モデルの難しさ
・組合せ的に選択可能な箇所があると、解数が爆発
例） 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
いかに効率よい探索ルートを作り、短時間で移動するかが課題
列挙事例：頻出パターンの列挙
頻出パターンの列挙
データベースの中に多く現れるパターンを頻出パターンという
データベース：トランザクション、ツリー、グラフ、多次元ベクトル
パターン：部分集合、木、パス・サイクル、グラフ、図形
 データの解析、特徴分析、知識・ルール発見
データベース
実験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 の部分集合
になっているようなデータベース
つまり、 D , ∀T ∈ D , T ⊆ E
1,2,5,6,7
2,3,4,5
D ＝ 1,2,7,8,9
1,7,9
・ POSデータ（各項目が、客1人の購入品目）
2,7,9
・アンケートのデータ（1人がチェックした項目）
2
・ web log （1人が1回のwebサーフィンで見たページ）
・オプション装備（車購入時に1人が選んだオプション）
実際のデータは、大きくて疎なものが多い
パワー則、スモールワールドが成り立つ
集合の出現と頻出度
集合 K に対して：
K の出現： K を含む D のトランザクション
K の出現集合 Occ(K)： K を含む D のトランザクション全ての集合
K の頻出度 frq(K)： K の出現集合の大きさ
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}の出現集合
＝ { {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つ以上のトランザクションに含まれる集合
D＝
1,2,5,6,7,9
2,3,4,5
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}
頻出集合列挙問題：与えられたデータベース D 、閾値θに対し、
D の頻出集合を全て出力する問題
２部グラフによる表現
・アイテム、トランザクションを頂点とし、包含関係を枝とする
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が入っている部分行列
バスケット分析
・スーパーなどの小売店舗で、同時に購入される事の多い品物
の組を知りたい
・客が購入した品目  トランザクション
・品目の組で、多くの客が購入したもの
 多くのトランザクションに含まれるアイテム集合
 （あるθに対する）頻出集合
● 牛乳、弁当
「おむつとビールの組合せが良く売れる」
という発見が有名
● お茶、弁当
● おにぎり、雑誌
● はさみ、のり
● ラーメン、はし
● こっぷ、皿
● 弁当、おにぎり
．．．
応用：クラスタリング
対象：データの関連を現すグラフ
（データの項目が頂点、関係のある、類似する項目間に枝）
類似する、あるいは互いに
関連するグループ
互いに背反だが、
立場が同じ項目のグループ
・データの種類・規模で大きさが変わる
・通常、それほど密ではない（次数高々100）
・局所的に密な部分が存在
・パワー則、スモールワールドが成り立つことが多
応用：ウェブコミュニティーの発見
対象：ウェブネットワーク
（ウェブページが頂点、リンクが枝）
グループになっている
リンク先
（同種のテーマ）
リンク元
（似た興味）
・グラフの大きさは世界全体で100億ページ
・ある種のドメインに区切ったり、意味のないページを除くと
1/10 から 1/1000 に小さくなる
・平均次数は10程度だが、局所的に密な部分が存在
・パワー則、スモールワールドが成り立つ
類義語群の発見
対象：単語ネットワーク
（単語が頂点、単語AとB を組合せて
複合語ができるとき、枝を張る）
関東
地方
関西
地区
中国
電力
北陸
2部クリークの片側が、
似た意味を持つ単語の集合
・大きなものでも、15万語程度
・通常、それほど密ではない（次数高々200）
・局所的に密な部分が存在
・パワー則、スモールワールドが成り立つ
類似論文のグループ化
対象：論文・アブストラクトグラフ
（論文が片側の頂点、単語がもう
片側の頂点で、論文のアブストラクト
が単語を含むときに枝を張る）
論文A
論文
論文C
語1
語2
語3
論文D
語：研究分野を表す単語群
論文：その分野の論文のグループ
・大きなものでも、10万語程度
・通常、それほど密ではない（平均次数高々200）
・局所的に密な部分が存在
・パワー則、スモールワールドが成り立つ
データベースの比較
・２つのデータベースが、意味的にどの程度似ているか知りたい
 大きさの違い、ノイズは無視したい
・各アイテム、属性などの総数だけでは、組合せがわからない
・組合せを細かく見ると、ノイズに振り回される
頻出集合を列挙することで、
組合せ的な特徴を比較できる
データ
ベース
データ
ベース
・いろいろな言語の辞書データ
・異なる種のゲノムデータ
・文書集合の単語データ（新聞のデータ、雑誌のデータなど）
・顧客のデータ
分類ルール、特性の発見
・データの特徴を現す規則、あるいは正例・負例を分類するような
規則が知りたい（A,B,C が含まれている、A,B が含まれれば、C
が含まれる、など）
・多く現れる組合せを用いないと、仮定部分を満たすものが少なく、
ルールとして意味がない
・組合せを細かく見ると、ノイズに振り回される
頻出集合を仮定に用いることで、
信頼度の高いルールを
効率良く見つけられる
データ
ベース
正例
・実験データ
・利用者履歴データ、マーケッティング
データ
ベース
負例
計算時間は、どうなるべきだろう？
・頻出集合の数は最高で 2n個になるから、計算時間 O(2n|D|) は、
|D| の部分を除けばある意味で仕方ない？
 そんなことはない。そんなにたくさん答えが出てくるような計算
は、そもそもしたくない
 つまり、解（頻出集合）の数はそんなに多くない、と思ってよい
 逆に考えると、解を出力する部分の計算は避けられない
つまり、「これだけは最低かかる」
・そこで、「解１つあたりの計算時間がどうなるか」に注目しよう
頻出集合の単調性
・工夫をするためには、何か問題の特徴を
つかまなくてはいけない
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
φ
重複に気をつける
・また、よくよく見ると、「どの頻出集合も、空集合（アイテムが
何も入っていない集合）にアイテムを１つずつ追加して作れる
・また、頻出集合にアイテムを追加して、頻出でなくなったら、そ
の後いくら追加しても2度と頻出にはならない
全ての追加の仕方を尽くせば、
全ての頻出集合が見つかる
・しかし、単純に全てを
尽くすと、大量に重複が出る
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
解1つ当たり、を速くする
・解１つあたりの計算時間はそれなりに（多項式時間で）抑えら
れたが、まだまだ大きい
・各 K＋e について、その頻出度を計算
－単純にするなら、全ての項目（トランザクション）について、
K＋e を含むかどうか調べる
 最悪、データベースの大きさに比例、
平均ではだいたい、項目数、
1,2,5,6,7,9
頻出度×Kの大きさ、の大きいほう
－ 2分木のようなデータ構造を作って、含むものだけ 2,3,4,5
1,2,7,8,9
抜き出す、あるいは勘定する、というのは、難しい
1,7,9
2,7,9
ここにもアルゴリズムが必要
2
含むものしか含まない
・アイテム集合 X の出現集合を T とする
・ X＋e の出現は X を含む（＝ X の出現）
 X＋e を含むトランザクションを見つけるとき
には、 T のトランザクションしか見なくてよい
・ T のトランザクションで e を含むものを集めると
X＋e の出現集合が得られる
・出現集合を更新すれば、
データ全体を見なくて良い
 計算時間はだいぶ短くなる
含むものしか含まない
・アイテム集合 X の出現集合を T とする
・ X＋e の出現は X を含む（＝ X の出現）
 X＋e を含むトランザクションを見つけるとき
には、 T のトランザクションしか見なくてよい
・ T のトランザクションで e を含むものを集めると
X＋e の出現集合が得られる
・出現集合を更新すれば、
データ全体を見なくて良い
 計算時間はだいぶ短くなる
共通部分をとる
・ T のトランザクションで e を含むものを集めると X＋e の出現
集合が得られる
 X＋e の出現集合は、 Xの出現集合と e の出現集合の共
通部分（両方に含まれるものを集めたもの）
・共通部分をとるには、両者をソートしておき、同時に先頭から
スキャンする
{1,3,7,8,9}
{1,2,4,7,9}
＝ {1,7,9}
計算時間は、スキャンしたアイテムの数  両者の大きさの和
振り分けによる高速化
・各アイテムに空のバケツを用意する
・ X の各出現 T に対して、以下を行う
－ T に含まれるアイテム e に対して、 e のバケツにT を入れる
 この操作が終わった後は、各アイテムe
のバケツの中身は X＋e の出現集合になる
A: 1,2,5,6,7,9
for each X の各出現 T
B: 2,3,4,5
for each T に含まれる e, e>Xの末尾
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 X の各出現 T
for each T に含まれる e, e>Xの末尾
eのバケツに T を挿入
・計算時間は,
X の各出現の (Xの末尾) より大きなアイテムの数の総和
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再帰呼び出しの計算時間のイメージ
・普通に頻出度の計算をすると
各 X＋e に対してデータを
一回スキャンする
(n-t)個
・共通部分による計算は
効果はこれだけではない
D(X) と D(e) のをスキャンする
 D(X) を n-t 回スキャンし、
＋
データベースの t より大きな
t
アイテムをスキャンする
・振り分けは D(X) に含まれるトランザ
クションの t のをスキャンする t より
大きなアイテムをスキャンする
t
(n-t)個
末広がり性
・再帰呼び出しを繰り返すと、 Xの頻出度は小さくなる
 振り分けの計算時間も短くなる
・バックトラックは、各反復で複数の再帰呼び出しをする
 計算木は、下に行くほど大きくなる
 計算時間を支配するのは一番下の数レベル
計算時間長
・・・
計算時間短
ほぼ全ての反復が短時間で終了  全体も速くなる
最小サポートが大きい場合も
・ θが大きいと、下のレベルでも多くの出現を見ることになる
 末広がり性による高速化はいまひとつ
・データベースの縮約により、下のレベルの高速化をはかる
（１）前回追加したアイテムより小さいアイテムは消す
（２）現在の出現集合からできるデータベースの中で、頻出になって
いないアイテムは消去する
（再帰呼び出しの中で加えられることが無いから）
（３）まったく同一のトランザクションは、１つにまとめる
１
・実データだと、下のほうのレベルでは
だいたい大きさが定数になる
θが小さいときと速度の大きな差はない
１
３
２
２
６
４
７
４
３
２
５
４
３
１
４
４
４
５
６
７
６
７
６
７
キャッシュとの相性
・速いプログラムを作るとき、キャッシュのヒット率が良く問題になる
－ループを開く
－メモリの配置を変える
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; }
●
●
●
●
●
●
▲
▲
▲
●●●
●▲
●
▲
●
▲
再帰的に問題が小さくなり、ある反復より先ではキャッシュに入る
 末広がり性より、ほぼ全ての部分でキャッシュに入っている
末広がり性の利用
・パターン 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}
２部グラフによる飽和集合の表現
・アイテム、トランザクションを頂点とし、包含関係を枝とする
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
極大頻出集合と飽和集合
極大頻出集合
・多項式時間で列挙できるかどうか、未解決
・クリークと同じように枝刈りをすると、高速に列挙できる
・数が少ないがθによる解のぶれが大きい
飽和集合
・逆探索という探索手法で多項式時間列挙可能
・離散アルゴリズムと末広がり性を用いて、高速列挙可能
・出現の意味で情報の損失がない
・ノイズが多いと出現集合が等しいものが少なくなり、
解の減少効率が悪くなる
両者とも、１つあたりほぼ定数時間、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
子どもを求める
・子どもから親を作る際に抜いた、最後のアイテムを親に追加
すると、出現集合は子どもと等しくなる
 子どもは、アイテムを１つ追加して、出現集合の共通部分
をとると得られる
 とはいえ、そのようにして作ったもの全てが子どもになると
は限らない
 子どもである条件は、抜いたアイテムより前の部分に、新
しくアイテムが追加されないこと
比較の手間
・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
参考文献など
・頻出集合およびその応用 (’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～）順序木・無順序木の多項式時間頻出列挙
逆探索の例：根付き木
親の定義：
左が重くなるように子供をソートし、
一番右の葉を除去する
逆探索の例：フロアプラン
親の定義：
左上の部屋の
右か下の壁をスライドして
左上の部屋をつぶす
（長方形による部屋分け）
実験結果
・実データからとった、著名なベンチマーク問題でテスト
・項目数は 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パターン程度
列挙事例：コードレスサイクルの列挙
化合物の立体構造の推定
・新たな化合物が得られたときに、その組成は比較的容易
に得られるが、結合の構造は容易に計測できず、さらに立
体的な構造の計測はもっと難しい
NO2
NO2
C6H5NO4
O
化合物
組成
OH
平面構造
すでに構造がわかっている化合物の
データを検索して、構造を推定する
OH
O
立体構造
化合物の立体構造の推定
・推定する化合物と部分的な平面構造が一致する化合物を
データベースから探し出す
 大域的な構造が拾えない
・検索結果を、環構造の複雑さ
で絞り込む
 立体構造の要因が入り、精度が増す
遺伝ネットワークの依存関係の解析
・遺伝子を頂点とし、遺伝子Aが発現すると、遺伝子Bに影響を
与え、発現するときに枝を引いたグラフを遺伝ネットワークという
・循環している系を見ようとすると、
サイクルの構造が必要
 サイクルを列挙することで、
どのような構造があるかを解析する
A
B
F
C
E
D
問題の定式化と狙い
・実用を考えればいろいろな条件が考えられるが、ここでの問題
のモデル化（定式化）では、基礎的な部分、つまりサイクルの列
挙のみを考える
サイクル列挙問題：
与えられたグラフ G のサイクルを全て出力する問題
・解の数に依存した計算時間
・簡単な構造の解法
A
B
F
C
E
D
分割法による列挙
・サイクルの集合は、単調性を満たさない
 バックトラックは適用できない
111…1
・分割法というアルゴリズムを使う
000…0
・最初の枝を選ぶ
・片方の端点に接続する枝それぞれについて、
「その枝を使うサイクル」を再帰的に列挙する
・ただし、サイクルができない枝は行わない
・最初の枝の、もう片方の端点に帰って
きたところでサイクルがひとつ見つかる
分割法の図解
・分割法（分枝限定法）の再帰構造を図示してみる
・各反復で、ある頂点を含むものと
含まないものに解集合を分割し、
できた集合が空でなければ、
再帰的に列挙を行う
v1
各反復で、解が
あるか判定し、
なければ中止
v1, v2
v1, v2
反復数が
解の個数×n
で抑えられる
v1
v1, v2
v1, v2
サイクルの存在のチェック
・効率良く列挙するためには、選択した枝を含むサイクルが存
在するかどうかを短時間でチェックする必要がある
・今まで選択した枝でできるパスの内点を全ての抜いたグラフ
で、端点から端点へ行ければサイクルが存在
グラフ探索1回でできる
探索1回で、加える枝
全てをチェックできる
１つあたりグラフの大き
さの時間で列挙できる
末広がり性の利用
・再帰構造の下の部分では、選択したパスの両端点が近い
 幅優先探索でチェックを行えば、
グラフ
小さい範囲しか探索しない
・再帰が深くなるほど、
反復が短時間で終了する
実用的には、１つあたり定数時間で列挙できる（1秒10万個）
・しかし、通常サイクルの数は多い
コードレスサイクルの利用
・ショートカットを持たないサイクルをコードレスサイクルという
・冗長なサイクルはコードレスにならない
（ある意味で極小）
・サイクルの本質部分が見える
応用上もありがたい
・少々の変更で、同様に列挙できる
（すでに通った頂点の隣を通ると、
コードができてしまうので、それを避ける）
化合物データのコードレスサイクル数は小さい
400原子程度の化合物でも高々10万程度  1-2秒
サイクルの存在のチェック
・このグラフを例にして動きを見る
s
s
a
a
c
c
b
d
e
d
b
f
e
g
j
t
g
f
i
t
t
h
i
e
g
f
h
f
t
h
h
i
j
i
j
j
t
t
t
t
t
j
擬似クリークの列挙
クリーク
クリーク：完全グラフになっている部分グラフ
（完全2部グラフになっている部分グラフ  2部クリーク）
類似する、あるいは互いに
関連するグループ
互いに背反だが、
立場が同じ項目のグループ
・クラスタリング発見などに使われる
・現実問題は、通常それほど密ではない（次数高々100）が、
局所的に密な部分が存在、パワー則、スモールワールド性
・単調性が成り立つので、列挙しやすい
・クリーク・極大クリークの列挙は効率良くできる(1秒10万、100万)
あいまいなクリーク
・クリークっぽいもの  完全グラフに近い部分グラフ
（完全2部グラフになっている部分グラフ  2部クリーク）
 クリークから少しだけ枝を取り除いたものとすればいいだろう
・抜く本数に制限をつけて、あいまいなクリークとそうでないものを
分ける  見つけるものが数理的にはっきりする
・全て見つける列挙問題として定式化する
あいまいの境界
・境界を固定して k 本とする
 単調性が保持されるのがうれしい、
が、小さい部分グラフはOK、大きな部分グラフはだめ、になる
・境界をクリーク枝数のθ ％とする
 部分グラフの大きさに密度が依存しないのがうれしい
 単調性がなくなる
今回はこれを解く
擬似クリーク（密部分グラフ）の定義
・頂点部分集合 S に対して、S の枝密度を
(S の頂点誘導グラフの枝数)
(|S|-1)|S| /2
クリークの
枝数
- S がクリーク  枝密度は 1
- S が独立集合  枝密度は 0
頂点の組のうち
結ばれているも
 S の枝密度が高ければ、クリークに近くなる
のの割合
閾値 θに対して S が擬似クリーク  (Sの枝密度) ≧ θ
擬似クリーク列挙問題：
与えられたグラフ G、密度閾値θ
に対し、G の擬似クリークを全て出力する問題
隣接行列で見ると
・アイテム、トランザクションを頂点とし、包含関係を枝とする
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が入っている部分行列
擬似クリークに関わる既存の結果
・１つ見つけるのは簡単
 空集合、１頂点の集合、枝の両端点が必ず擬似クリークになる
・大きさ k の擬似クリークを見つける問題はNP完全
 θ= 1 とすると、大きさ k のクリークを見つける問題になる
・最も枝密度の高い頂点数 k の部分グラフを見つける問題はNP完全
－ O(|V|1/3-ε) の近似率のアルゴリズムがある
－最適解がある程度濃い、とい条件では O((n/k)ε) 近似 [鈴木徳山]
－枝数が Ω(n2) ならPTASがある[Aroraら]
・データマイニングなどの分野で、擬似クリークを発見するアルゴリズムはいく
つか提案されているが、いずれも完全性がなく、列挙問題として捉えている研
究はない
分割法によるアプローチは困難
・列挙アルゴリズムの基本的な構築の仕方として、分割法
（分枝限定法）がある
・各反復で、ある頂点を含むものと
含まないものに解集合を分割し、
できた集合が空でなければ、
再帰的に列挙を行う
v
v1
1
v1, v2
解があるか判定
する問題がNP完全
v1, v2
v1, v2
v1, v2
困難性の証明
Theorem 1 与えられたグラフ G と閾値 θ、頂点部分集合 U
に対して、U を含む擬似クリークが存在するかどうかを判定
する問題はNP完全である
証明: 大きさkのクリークの存在判定を帰着
入力グラフ
G=(V,E)
|V|2 -1
枝密度 =
|V|2
2|V|2 個の
頂点を追加
し、Uとする
θ=
|V|2 -1
|V|2 +ε
・ (U + クリーク) のみが擬似クリーク
・大きくなると枝密度が真に増加）
・ εを適当に設定すると、大きさが
k 以上のクリークのみが擬似
クリークになる
果たして本当に困難か？
・この証明は「とても濃い」グラフの判定問題が難しいことを
証明しただけ
 密度が中くらいのところについては、良くわからない
 出力多項式時間アルゴリズムはできるかもしれない
θ= 1
出力多項式時間 計算時
間が入力の大きさと出力の
大きさに対して多項式
簡単
簡単
θ= 0
困難
?????
擬似クリークの
多項式遅延列挙アルゴリズム
逆探索法によるアプローチ
・列挙する対象の間に、非巡回的な親子関係を定義
objects
親子関係が導く根付き木を深さ優先探索することで列挙
探索は、再帰的に子どもを見つけることで行えるので、
子どもを見つけるアルゴリズムがあれば十分
擬似クリークの親
・ v*(K) ： G[K] の最小次数頂点の中で最小添え字のもの
・擬似クリーク K の親を K＼v*(K) で定義
K
K の親
・ K の枝密度＝ G[K] の平均次数 ÷(|K|-1)
・親は、K から最も枝密度の薄い部分を取り除いたものなので、
やはり擬似クリークになる
・親は大きさがちょうど１小さい  親子関係は非巡回的
子ども列挙による深さ優先探索
・列挙木を探索すれば、全てのあいまい頻出集合が見つけられる
・深さ優先で探索すれば、解をメモリに保持する必要もない（木の
深さは高々アイテム数）
・このような、陽に与えられていない木を深さ優先探索するにはど
うすればいいか？
 与えられた頂点の、子どもが順に見つけられれば十分
 見つけた子どもに対して、再帰的に子どもを見つければよい
objects
擬似クリーク列挙木の例
・閾値を70%に設定
3
6
1
2
4
5
7
子どもの発見
・擬似クリークの親は、頂点を１つ取り去って得られる
 擬似クリークの子どもは頂点を１つつけることで得られる
（子どもの候補 |V| 個しかない）
・ K∪v が K の子どもである 
① 擬似クリークであり
② K∪v の親が K （つまりはv*(K∪v) = v ）
・この条件を各頂点について素朴に評価するとO(|V|+|E|) 時間
・もう少し速くしましょう
子どもである条件
・ degK(v): v に隣接する K の頂点の数
 degK(v) がある一定値以上であるときのみ、 K∪v は擬似ク
リークになる（① の条件）
・各反復でdegK(v)を更新し（O(deg(v)) 時間）、その値ごとに分類
しておくことで、 ① の条件を満たすものを１つあたり定数時間で
見つけられる
・②の条件 v*(K∪v) = v も、degK(v)の値で場合分けするとクリア
－ degK(v) < K の最小次数  K∪v は必ず Kの子ども
－ degK(v) > K の最小次数＋１  K∪v は Kの子どもでない
子どもである条件 (2)
・ S(K): K の最小次数の頂点を、添え字順に並べた列
・ degK(v) ＝ K の最小次数 or ＋１  v が、
－ v より degK、添え字ともに小さい頂点はない
－ degK(u) ＝ degK(v) かつ添え字が v より小さい u 、および
degK(u) ＝ degK(v)-1 かつ添え字が v より大きい u
は必ず v と隣接
・ K の頂点を次数順・添え字順に見て、隣接リストをスキャンし、
K に含まれない各頂点に対して「隣接しない初めての頂点」を
見つける  それと、自分の添え字を比べればよい
１反復のチェック・データ更新時間は O(Δ(Δ+log |V|)) となる
擬似クリーク計算機実験
末広がり性
・バックトラックは、各反復で複数の再帰呼び出しをする
 計算木は、下に行くほど大きくなる
 計算時間を支配するのは一番下の数レベル
計算時間長
・・・
計算時間短
擬似クリークが少々大きく（4以上くらい？に）なると、
最小次数は平均的に小さいだろう
 平均的に計算時間は短いだろう
実装
実験環境： Pentium M 1.1GHz、256MBメモリ＋ cywin ＆ C
・実装は、単純なものを用いた
－ degK(v) の更新とグループ分けはするが、並び替えはしない
－ degK(v)＝ Kの最小添え字 or ＋１となる頂点に対して、素
朴にチェックをする
 この条件を満たす頂点はそれほど多くないだろう
 隣接しない頂点がすぐ見つかって、頂点１つに対する
チェックも結局は短時間でできるだろう
実験に用いたグラフ
- 通常のランダムグラフ
（確率 p で枝をはる）
- 局所的に密なランダムなグラフ
（自分と添え字が近い頂点のみに
確率1/2で枝を張る）
- ランダムに作成したスケールフリーグラフ
（頂点を順に追加し、次数に比例する確率で
他の頂点を定数本選び、枝を張る）
- 現実のデータ
（ソーシャルネットワークデータ）
ランダムグラフ
・枝の確率が 0.1 で、頂点数が 200-2000。閾値は90%。時間は
百万個あたり。クリーク列挙と比べると10倍程度遅い
r a ndom gr a ph p=0.1
#clique
time per 1M clique
time clique
#p-clique 0.9
time per 1M 0.9
time 0.9
#p-clique 0.8
time per 1M 0.8
time 0.8
1000000000
100000000
10000000
1000000
100000
1000
100
10
1
0.1
6400
4524
3200
2262
1600
1131
800
565
400
282
0.01
200
time (sec) & #cliques
10000
#vertices
次数が大きくなるにつれて、ほぼ線形に時間が伸びる
局所的に密なランダムグラフ
・自分の回り±30頂点に確率が 0.5で枝を張る
・ 100～25600 頂点、閾値は90%。同じくクリークより10倍遅い
locally dense random graph
#clique
1000000000
time per 1M clique
100000000
10000000
time clique
1000000
#p-clique 0.9
time per 1M 0.9
10000
1000
time 0.9
100
#p-clique 0.8
10
time per 1M 0.8
1
0.1
time 0.8
3E+05
64000
16000
4000
0.01
1000
time (sec) & #cliques
100000
#vertices
次数が変化しないので、時間は伸びない
ランダムに作成したスケールフリーグラフ
・大きさ10のクリークに１つずつ頂点を加える
・次数に比例する確率で他の頂点を10個選び、枝をはる
10000000
1000000
100000
#clique
time per 1M clique
time clique
#p-clique 0.9
time per 1M 0.9
time 0.9
#p-clique 0.8
time per 1M 0.8
time 0.8
10000
1000
100
1
0.1
16
00
0
32
00
0
64
00
12 0
80
0
25 0
60
00
80
00
40
00
20
00
0.01
10
00
time & #cliques
10
時間は非常にゆっくりと増加
#vertices
現実問題
・論文の共著関係を表すグラフ
・頂点数は3万、枝数は12万5千、スケールフリー
1000000000
real-world data
100000
#p-clique
time
time per 1M
1000
10
0.83
0.85
0.88
0.9
0.93
0.95
0.98
1
0.1
1
time & #p-cliques
10000000
threshold
1個あたりの計算時間は閾値によらないようだ
考察＋α
・実際の列挙の時間は、ひとつあたりほぼ定数時間
・理論的なバウンド、最大次数の２乗よりはるかに小さい
・なぜ現実的には速いのか？
－データの更新の時間は、追加された頂点の次数に線形
 degK を小さくする頂点の次数が大きいとは思えない
－子どもかどうかチェックしなければならない頂点は少ない
 子どもの数の定数倍
類似する部分文字列の発見
データベースから類似する項目を見つける
・データベースの項目の中で、似た項目のペアを全て見つけたい
（項目のペア全てについて、
2項関係が成り立つかを調べる）
・類似している項目の検出は、
データベース解析の基礎的な手法
 基礎的なツールがあれば、使い方しだいで
いろいろなことができる
（大域的な類似性、データの局所的な関連の構造・・・）
・ここでは、文字列について考えてみる
類似部分文字列
・文字列データ（文書）はいたるところに存在
・単なるキーワード検索でなく、文書間の類似構造が知りたい
－ web文書間の似た部分（引用？）
－多数のプログラムの解析
－ゲノム、たんぱく質の類似構造
・類似検索は非常に時間がかかる
－文書数の2乗のオーダーはかけられない
－編集距離を求めるのに、文書の大きさの2乗かかる
web、ゲノムで大きな問題
類似文字列に関する研究
・全対比較して編集距離を計算
 編集距離（挿入／削除／変化の最小数）は最短路で２乗時間
 A*などの改良も有効だが、文字列が似ているという仮定が必要
・ BLASTを始めとする相同発見アルゴリズム
（例えば11文字の）短い完全一致領域を見つけ、そこを種として検索
 文字列が長いと、大量の完全一致がある
 11文字を長くすると精度が落ちる
 良く現れる単語は候補から除外、遺伝子部分だけ注目
といった処理をしているようだ
・その他ヒューリスティックサーチ
－フーリエ変換を使った判定、指紋法による分類など
・類似検索
 大量の、コストの高いクエリを実行
アルゴリズム的に簡単な問題設定を
・類似殿尺度には、編集距離でなくハミング距離を
 線形時間でOK
・長さが可変だと大変なので、固定
・長い文書は大変なので、短いものを
 ハミング距離の計算がますます容易
こういう条件で定式化してみる：
問題：各項目が同じ長さ l の短い文字列（50文字程度）である
データベースを入力したときに、文字列のペアで異なり数（ハミ
ング距離）が d 文字以下である組を全て見つけよ
長い文字列の、ハミング距離でない比較
・長くて、ある程度（ハミング距離の意味で）似ている配列は、短
く似ている部分列を必ずある一定数以上含む
・長くて、編集距離の意味で似ている配列も、短く似ている部分
列を必ずある一定数以上含むだろう
 長い文字列は、オーバーラップするようにスライスして短い文
字列に分解すればよい
分解して比較
・長い文字列を、オーバーラップさせてスライスし、全対比較
・縦横に比較するゲノムをおき
マトリクスを作って類似するペアが
あるセルの色を白くする（各ピクセル内の
個数によって色の強弱をつける）
・長さα、幅βの領域にいくつかのペアが
あるときのみ、色を白くする
 長さαの部分配列が、誤差 k %弱で
似ているなら、必ず誤差 k %で似て
いる短い部分列がいくつかある
例：長さ3000で10%弱(間違い290)なら、
長さ30で間違い2の部分列を、少なくとも3つは含む
問題の難しさ
・全ての項目が同じだと、O(項目数2) 個の出力がある
 l を定数だと思えば、単純な全対比較のアルゴリズムが
計算量の意味では最適になる
 計算量理論的には面白くない問題
・現実には、やたらと似ているものがあるものを比較しても意味
が無い
 出力は少ないと仮定する
ATGCCGCG
GCGTGTAC
GCCTCTAT
TGCGTTTC
TGTAATGA
．．．
・ ATGCCGCG と AAGCCGCC
・ GCCTCTAT と GCTTCTAA
・ TGTAATGA と GGTAATGG
．．．
基本のアイディア：文字列の分割
・各文字列を、k（>d）個のブロックに分割する
・ k-d 個のブロックの場所を指定したときに、そこがまったく等しく
て、かつハミング距離がd 以下となるようなペアを全て見つけよ、
という部分問題を考える
 各文字列の k-d 個のブロックをつなげてキーにし、ソートをす
る。同じものはグループになる。それを総当りで比較すればよい
・ k-d 個のグループ数が大きければ、平均的にグループのメン
バー数は小さくなるので、総当りで比較してもたいしたことない
全ての場合を尽くす
・先の部分問題を、全ての場所の組合せについて解く
 ２つの文字列が似てれば、必ずどこか k-d 個のブロックが同じ
 必ずどれかの組合せで見つかる
・部分問題は、バケツソートやRadixソートで速く解ける
・組合せの数は kCd 。のk=5 で d=2 なら10通り
 ソート10回＋α で解ける。全対比較よりもかなり高速
・各文字の数から、１文字比較した場合に等しくなる確率を求め、
適切な分割数 k を使用する
例題
・ 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
重複の回避
・まったく同じ文字列があると、全てのブロックの組合せで見
つかるので、 kCd 。回出力される
 重複を回避する必要がある
・各見つかったペアについて、選択されていないブロックが選
択したブロックの間にあったら出力しないようにする
 等しいブロックが一番左端によっている場合にのみ出力
メモリに解を保持せずとも、重複が回避できる
イメージ的には
・似ているもののペアを探す問題は、マトリクスのセルの中で必
要なものを全て見つける問題
・全対比較は、マトリクスのセルをすべて見ていることに対応
・分類によるアルゴリズムは、
分類を順々にしていると思えば、
木構造の探索を行っていることに対応
計算実験
実験：長さ20文字で異なり数 d を変化
人のY染色体から部分配列をとって実験。PenMのノートPC
10000
1000
d=0
d=1
d=2
d=3
10
20
00
70
00
22
95
3
0.1
70
0
1
20
0
計算時間(秒)
100
長さ(1000文字)
ゲノムの比較 (1)
ヒト21番染色体とチンパンジー22番染色体の比較
・長さ3000万の配列×2 から、30文字の切片を3000万個取る
・似ている部分配列のペアの数に応じて、各ドットの明るさを変える
ヒト 21番染色体
・白い部分が
「似ている可能性のある部分」チ
ン
・黒い部分が
パ
「(絶対に)似ていない部分」ン
ジ
・格子模様は、繰り返し
配列を拾っている
PCで 1時間で可能
ー
22
番
染
色
体
ゲノムの比較 (2)
X
ヒトX染色体とマウスX染色体の比較
・ 30文字で間違い2文
字以下のペアを列挙
・長さ3000、幅300
の領域に3つペア
があれば点を打つ
マ
（誤差10%弱で似てウ
ス
いるものは、必ず３つ
染
のペアを含む）
色
体
・ノイズをかなり
除去できている
PCで 2時間で可能
ヒトX番染色体
ゲノムの比較 (3)
バクテリアを30種
ABC順の取得し
つなげて比較
・一度に複数の
ゲノムを比較できる
PCで 1時間で可能
（マイクロアレイ用の）固有な配列のデザイン
・マイクロアレイの設計には、ゲノム配列中でなるべく他の部分と
似ていない配列が使えるとありがたい
・配列の長さは２０文字、のように決まっているので、
対象となるゲノムの全て２０文字の部分配列を比較し、
似ているものがないもの、を見つければよい
・似ている文字列の数、はある種の統計量として利用できるかも
しれない
100Mベース、25文字、間違い2文字まで、くらいなら
PCで 1時間で可能
（生物学的な）課題点
・マウス13番染色体の未解読領域に適用を行っている
 既にいくつかの空白部分が埋まった
・比較は高速にできるようになった。だが、比較結果をどう使うか、何に
留意する必要があるか、といった点は、まだまだ明らかでない
－実験の指針を出すためには、
何を出力する必要があるか
－どの程度の精度が必要か
－どこまで処理を自動化すべきか
－エラーをどのように扱うべきか
 既存のアセンブリングソフト
(phred/phrap/consed)では見つからない、
特殊な重なり方をしている相同領域が
見つかる。どう解釈すべきか？
（情報学的・システム的な）課題点
・相同検索としての能力は高い
・しかし、細かい部分で既存のソフトに劣る
－アラインメントが取れない
－ゲノム固有の制限を入れていない
－データベースと連携していない
－インストーラ、GUIがない
－実験誤差データを考慮していない
－オンラインサービスをするべき
・既存のソフトウェアとの連携を
進めていくべきだろう
まとめ
・列挙手法を用いたデータマイニングへのアプローチ
・頻出集合・飽和集合の列挙アルゴリズム
・コードレスパス・サイクルの列挙アルゴリズム
・計算実験で、現実的な疎データに対する有効性を実証
将来の課題：
・計算量と現実的な計算時間のギャップを、より良く説明できるか
・あいまいな尺度によるモデル化と高速解法
・極大元・代表元の効率的な列挙手法
・ツールとしての利便性の向上

Download Report