Document

オフライン類似項目発見問題と
複数分類アルゴリズム
宇野毅明
国立情報学研究所
津田宏治
杉山将
産業総合研究所
東京工業大学
2009 年 2 月 26 日
簡単に自己紹介
名前：宇野毅明
年齢・職種：国立情報学研究所・准教授・38歳
研究分野：アルゴリズム理論とその応用
－グラフアルゴリズムを中心とした離散アルゴリズム
－組合せ最適化とそれにまつわる数理
－列挙アルゴリズムと、頻出パターンマイニングへの応用
最近の研究：ゲノム情報学やデータマイングで出てくる巨大なデー
タベースの基礎的（とはいっても非常に時間のかかる）な解析を超
高速で行うアルゴリズムの開発
もっとー：速い安い（単純）うまい
趣味（日課？）：子供と遊ぶこと
ゲノム情報学の計算面での到達点
・ゲノム情報学の問題、解けるようになったでしょうか？
情報学的には：
「基礎的なものは解けてます」
「知識発見など、複雑な問題が解けないですね」
生物学的には：
「計算ができなくて困っています」
「難しいことより、まず簡単なことができないんです」
・非常に大きなギャップがある
・聞き込みをしてみると、「計算量がわかっても意味がない」「研究のフ
ォーカスがずれている」「実装がない」「基礎的な問題が解きたいが、（
モデル化、あるいはアルゴリズム的な意味で）筋が違う」などなど
（考慮する要因や、問題の定式化など）
ゲノム相同領域発見問題
（注）ゲノム情報学の分野では、文字列の類似する部分を相同領
域、類似する部分を見つける問題（類似検索）を相同領域検索、
あるいは相同検索といいます
 ゲノムは種の進化や個体差、実験のエラーなどにより、同じ
機能を持つものでも、異なる形でコードされていることが多い
 そもそも、似たものを見つけるのも重要
－機能が未知の遺伝子と類似する遺伝子を探す
－異なる種のゲノムの比較（類似部分には意味がある）
－ゲノム読み取り時に、断片配列をつなげる
－固有な部分配列の同定をして、マーカーとして使う
－同じく、プライマーとしてPCR増幅に使う
ゲノムの読み取り
ゲノムを読み取る方法
１． DNAを薬で溶かして、ひも状にする
２．放射線などを当てて、短い切片にぶつぶつ切る
３．機械で読む。1回で500文字程度読める
ただし、精度は99.9%程度。1000文字に1文字くらいミスる
４．読んだ結果をつなぎ合わせて、もとのゲノムを構築する
系統樹作り
・各生物種が、どれくらい前に分かれたものかという、進化の系
統樹を推測する
・ゲノムが似ているものは最近分かれた種である、という推測で
樹を作る
・いくつかのまったく違う生物から大まかな樹を作るものと、ター
ゲットとなる種を（例えばイネとか）決めて、その中でどのように
細かい種が分かれていったかを調べるものがあるようだ
類似性のモデル
・ゲノムの変化（変異、あるいは実験での読み取りエラー）は、
局所的には、1文字単位で起きる
・既存研究では、文字列の尺度で類似度を判定している
 （コスト付き）編集距離
 （ときどき）ハミング距離
・両者ともに、数理的に美しい尺度であり、計算も容易
－長さ n の文字列の比較
ハミング距離： O(n) 時間、編集距離 O(n2) 時間
・実際には、大域的な入れ替わり構造がある
最短路問題
・２つのゲノムに対して、グリッド型のネットワークを作る
ATGCA
AGCAT
ATGCA*
A*GCAT
横移動：左側に空白を挿入
縦移動：下側に空白を挿入
斜め移動：空白無し（同じ文字ならコスト０）
A
C
G
T
A
A G C A T
しかし、巨大な n の２乗は果てしなく大きい
相同検索の応用と困難さ
・相同検索は、ゲノム解析における中心的な道具
 計算のうち半分以上は相同検索とも…
・しかし、類似検索なので計算資源が必要
 現在は並列計算にたよっている
・類似検索なので、基本的に２分探索のような手法は使えない
 ソフトにより性能は異なるが、100万文字の配列（文字列）２つ
を比較するのにもかなり（数分から数時間）かかる
 染色体のような、数億文字ある配列の比較には多大な計算
資源が必要（あるいはヒューリスティックでやる）
もし、相同領域を短時間で行えるようになるなら、
それがゲノム研究に与える影響は大きい
相同領域発見の研究（アルゴリズム的）
・２つ文字列の編集距離（挿入／削除／変化の最小数）は最短路アル
ゴリズムを使って、ある程度高速に求められる
 ２つの文字列が似ていないと有効でない
 入れ替わり構造は発見できない
・ BLASTを始めとする相同発見アルゴリズム
（例えば11文字の）短い完全一致領域を見つけ、そこを種として検索
 文字列が長いと、大量の完全一致がある
 11文字を長くすると精度が落ちる
 良く現れる単語は候補から除外、遺伝子部分だけ注目
といった処理をしているようだ
・類似検索
 大量のクエリを実行しなければならない
類似検索は通常、完全一致検索より大幅に時間がかかる
アルゴリズム理論からのアプローチ
・計算の高速化において、並列計算は強力であるが、コストが
かかるのが欠点（プログラミングの複雑さも含め）
・アルゴリズム理論による高速化は、問題の大きさに対する計
算時間の増加を、計算手法の設計変更により、抑える
100項目
100万項目
2-3倍
10000倍
データが巨大になるほど、アルゴリズム改良の加速率は上がる
アルゴリズム理論から、相同領域発見のモデルに取り組んでみる
アルゴリズムからモデル・定式化へ
・通常、モデル化（定式化）とアルゴリズムは、解ける問題と解きたい問
題のすりあわせして、うまい落としどころを見つける
問題
アルゴリズム
・しかし、相同性検索では、状況が少し違うように見える
 「うまく解ける問題」の単純な拡張 or ヒューリスティック手法
・完全一致の検索がうまくできる、うまく評価できる類似性の尺度があ
る、という２つを単純に組み合わせただけ
・アルゴリズムの視点から問題の定式化を見直せば、よりうまく解ける
モデルが提唱できるかも
何がほんとに似ているか
・生物系の研究者に聞くと、編集距離は（距離が大きいと）研究者の直
感に対応していないようだ
 同じ編集距離（ハミング距離）でも、似てる感が大きく違う
ATGCATGCATATATATATGCATGC
ATGCATGCGCGCGCGCATGCATGC
ATGCATGCATATATATATGCATGC
AAGGAAGGAAAAAAAAAAGGAAGG
・どうも、部分的に集中して似てるところが効いているようだ
・あまり短い部分だけが似ていても、意味がないようだ
・さらに、実用上は「似ている部分が見つかればいい」ので、解の中に
「似ていない部分が混ざっていてもいい」
（見つけ損ないはダメだが、偽者を見つけても大きな被害はない）
短い文字列の比較
問題：各項目が同じ長さ l の短い文字列（50文字程度）であるデ
ータベースを入力したときに、文字列のペアで異なり数（ハミング
距離）が d 文字以下である組を全て見つけよ
・ゲノム全体から各ポジションを先頭とする長さ l の部分文字列
を全て集めてこの問題を解くと、似ている部分列が全て見つかる
（ハミング距離の意味で似ている部分文字列）
ATGCCGCG
GCGTGTAC
GCCTCTAT
TGCGTTTC
TGTAATGA
．．．
・ ATGCCGCG と AAGCCGCC
・ GCCTCTAT と GCTTCTAA
・ TGTAATGA と GGTAATGG
．．．
問題の難しさ
・全ての項目が同じだと、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以下のものを求めよ
ABCDE
ABDDE
ADCDE
CDEFG
CDEFF
CDEGG
AAGAB
A
A
A
C
C
C
A
BCDE
BDDE
DCDE
DEFG
DEFF
DEGG
AGAB
A
A
A
C
C
C
A
BC
BD
DC
DE
DE
DE
AG
DE
DE
DE
FG
FF
GG
AB
ABC
ABD
ADC
CDE
CDE
CDE
AAG
DE
DE
DE
FG
FF
GG
AB
Computation Time
・ The classification is done by a radix sort, or simply bucket sort,
in O(l |S|) time
・ By recursively classify the blocks one-by-one to sharing the
classification of the same position of blocks, reduces to O((l/k) |S|)
・ Time for classification is O((l/k) |S| kCd) in total
・ Time for pairwise comparison depends on the group size
 we choose a good k before execution of the algorithm
・ When k=l, any pair in a group is similar
 The time complexity is O((|S| + dN) kCd)
重複の回避
・まったく同じ文字列があると、全てのブロックの組合せで見
つかるので、 kCd 。回出力される
 重複を回避する必要がある
・各見つかったペアについて、選択されていないブロックが選
択したブロックの間にあったら出力しないようにする
 等しいブロックが一番左端によっている場合にのみ出力
メモリに解を保持せずとも、重複が回避できる
k の選択
・一番良い k をあらかじめ計算するのは不可能（と思われる）
・どの k が良いか推定する問題を解いて、選ぶ
・ 2つの文字をランダムに選んだときの一致する確率を元に、l/k 個
の文字を使ってグループ分けしたときの、各グループのメンバーの
平均値を計算
・それを元に、計算コストを算定する。これを全ての k について行っ
てベストなものを選ぶ
なぜBLASTより速くできるのか？
・オリジナルのBLASTは、連続して11文字同じところを見つける
 大雑把に言って、分類精度は、4の11乗 ≒ 400万
 100万塩基あたりから苦しそう
・今回の手法は、例えば 30文字中間違い3文字（連続して7文
字同じ、と同じ精度）で6個に分割するなら、
大雑把に、分類精度は、4の15乗 ≒ 10億を20回
 2億塩基あたりから苦しいが、そうなったら分割数を7にす
ればいい
ただし、(短い配列の）検索は苦手
（全部の比較と一部の比較の速度があまり変わらない）
なぜ高速化できるのか？
・チェックするマスを図示してみる
・アクセスするマス目の面積が大きく違う
・グループの数が増えると、より速くなる
イメージ的には
・似ているもののペアを探す問題は、マトリクスのセルの中で必
要なものを全て見つける問題
・全対比較は、マトリクスのセルをすべて見ていることに対応
・分類によるアルゴリズムは、
分類を順々にしていると思えば、
木構造の探索を行っていることに対応
Exp: fix length to 20, and change distance d
Prefixes of Y-chromosome of Human, on a note PC with Pentium M
1.1GHz, 256MB RAM
10000
d=0
d=1
d=2
d=3
100
10
20
00
70
00
22
95
3
0.1
70
0
1
20
0
CPU time(sec)
1000
length(1000lett.)
Exp.: fix length to 30, and change distance d
Web texts written in Japanese, Core2duo, E8400 3GHz, 4GB RAM
30,0text
Japanese
1000
30,1
30,2
100
time, time/#pairs (sec)
30,3
30,4
10
30,0 ave
30,1 ave
1
30,2 ave
30,3 ave
30,4 ave
0.1
1366
2556
5272
10637 21046 40915
letters (1000)
実験：長さ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文字)
長さ l が大きい場合
・ l および k が大きくなると、ソートの回数が増えるため、計算は遅
くなる
 複数分類法と同じアイディアで高速化できる
・長さ l の文字列を h 個に分割する
 ２つの文字列の距離がk 以下なら、必ず距離がk/h 以下のブ
ロックが存在
・ k の選択と同じように、計算コストを算定して最適な h を選ぶ
比較する部分文字列の省略
・少し長めの類似構造を調べたいときには、比較する部分文
字列を省略しても効果がある
－比較する文字列AとB （両者が同じこともあり得る）から長
さ l の文字列を取るときに、適当な k を定めて、A の部分文
字列のうち k/l 、B の 1/k を選び出して比較
－どのような（少し長い）部分列の組に対しても、1/l 程度の
比較される部分列を含む
任意の部分列の組に対して
A
B
このように部分列が比較される
分割の効能
・ 1000文字でハミング距離100以下の組を見つけるとする
・ k=103 ブロックに分割とすると、103個の中から3 個を選ぶ組合せ
はおよそ 100*100*100/6 で15万通りくらい
・ 3つのブロックの文字数はおよそ29 文字。(文字種^29) 程度のグ
ループに分類
・ h=10 とし、k=14 としてその中から 6 個を選ぶとすると、ソート回
数は 14*13*12*11/4*3*2*1 ＝およそ1000通り（コストが150 分の1
×10回）
・ブロック4つの文字数はおよそ29 文字なので、グループ数は同じ
文字列の比較だけでなく
・今まで、文字列の問題だけを考えてきたが、別に文字列にこだ
わる必要はない
－行列の部分行列
－離散ベクトル（行列）データの比較
・ベクトルデータを離散化して比較、01ベクトルの比較、画像の
部分比較などに使える
 大規模データに対して近傍グラフが短時間で作れる！
０１０１００００１１
１１０１００００１１
１１００１０１０１０
００００１１００００
・・・・
10, 143, 29, 13
33, 29, 143, 35
1, 76, 33, 24
132, 7, 24, 24
・・・
Visualization by Dot Plot
・ To capture the global similarity, visualize it by drawing a figure
・ Consider a matrix, whose cell corresponds to pair of (long)
substrings of two strings
・ Long similar substrings
will be seen as diagonal lines
string A
String B
・ Intensity of a cell is given by
the number of similar substrings
taken from the corresponding
(long) substrings
 Strings taken from all positions
ゲノムの比較 (1)
ヒト21番染色体とチンパンジー22番染色体の比較
・長さ3000万の配列×2 から、30文字の切片を3000万個取る
・似ている部分配列のペアの数に応じて、各ドットの明るさを変える
ヒト 21番染色体
・白い部分が
「似ている可能性のある部分」チ
ン
・黒い部分が
パ
「(絶対に)似ていない部分」ン
ジ
・格子模様は、繰り返し
配列を拾っている
PCで 1時間で可能
ー
22
番
染
色
体
Dot Plot for Long Genome Sequence
・ The comparison of mouse 11th chromosome and human 17th
chromosome is …
not visible
・ By restricting #output
pairs to 10, for each string,
we can see something
 Still noisy, and lose
completeness
2 min by PC
Human 17th chr
・ Huge amount of noisy
similar pairs hide everything
Mouse 11th chr.
Same Intensity
・ Even if a cell includes many pairs, it does not always represent the
similarity
・ Pairs composing diagonal a line are important
 Pairs distributed are not
 Pairs concentrated into a small area are also not
・There would be many models representing “pairs on a line”,
but we use a simple one
Box Filtering
・ One of simple models is to consider the number of pairs in a diagonal
long box, (of length α, and width β)
 If there are pairs of a certain number h in a box, we consider they
are a part of a line
・ On the other hand, if such pairs are in quite small area, we would say
they are not a line
・ By removing pairs not composing a line, and replace pairs in a box by a
point, we can simplify the figure
新しいモデル
・２つの文字列の類似を「似ている短い区間がいくつかある」で定義
（距離ではなく、似ているかいないかの２値になる）
・この条件は、ある意味で、
既存の類似性の条件を弱めている
・既存の意味での類似性の下界にもなる
例：長さ3000でハミング距離が10%弱
(間違い290)なら、長さ30で間違い2の部分列を、少なくとも3つは含む
・離れた位置にある部分が似ていても全体が似ていることにはならない
ので、ずれの最大をβで制限する
・２つの文字列が似ている部分文字列を持つ
 「長さα、幅βの領域に閾値以上の類似部分文字列のペアがある」
ということになる
効率良く計算できるか
・類似部分文字列を持つ長さα幅βの領域をどう見つけるか
ペア長さαの部分文字列を全対比較  ２乗の時間かかる
 別の方法を考えないと、とても解けない
・最初に、短くて似ている部分
文字列のペアを全部見つけておく
・幅２βの斜めの線に沿って、長さαの領域に
閾値以上のペアがあるところを探す
・斜め線をβずつずらして、全ての部分について似ている部分を探す
・長さα幅βの似ている部分列は必ず見つかる(そうでないものも発見)
・短くて似ている部分列を効率良く見つければよい
Dot Plot for Long Genome Sequence
・ Again, the comparison of mouse 11th chromosome and human 17th
chromosome
・ We set the width, length, #pairs of the box to 3000, 300, 3
similar pairs hide everything
Mouse 11th chr.
・ In high resolution, we
can remove the noise much
3 min by PC
Human 17th chr
・ We could erase almost
the noise pattern
Dot Plot for Long Genome Sequence
Mouse X chr.
15 min
by PC
Note:
BLASTZ: 7days
MURASAKI:
2-3 hours with
small error ratio
Human X chr
Comparison
mouse X chr.
and
human X chr.
ゲノムの比較 (3)
バクテリアを30種
ABC順の取得し
つなげて比較
・一度に複数の
ゲノムを比較できる
PCで 1時間で可能
Superimpose Many Images by Coloring
・ We can superimpose the comparisons between a fixed string
and the other strings, by using many colors
Human 22nd chr
all chr’s of mouse (all start form leftmost)
6 hours by a PC
まとめ
・類似する部分列をいくつ含むかに着目した新しい類似の尺度を
提案した
・部短時間で類似する部分列を全て見つけ出す高速なアルゴリズ
ムを提案
・実際にゲノムで比較を行い、既存の方法よりはるかに短時間で
ある程度の保証をもつ解を得た
－ヒト、チンパンジー、マウスの染色体の比較
バクテリアゲノムの多対多比較
・ツールとしての完成度を高める（UI、解の圧縮など）
・機能の追加（特にアセンブリ）
類似部分文字列による
ミスマッチ頻出文字列発見
宇野毅明（国立情報学研究所
＆総合研究大学院大学）
2008年 11月
頻出文字列
・（巨大な）文字列データから、頻出する文字列を見つけたい
（頻出する＝あちこちに現れる）
・ suffix array やradix sort などで、ほぼ線形時間で、多数現れる
部分文字列は見つけられる（閾値以上の回数現れる者の中で
極大なもの、といった設定もOK）
・しかし、アイテムセットのように、「現れる」ことが包含関係で表
されているものに比べると、自由度が低い
（＝きっちりと全体が現れるものしか見つけられない）
・ゲノムなどエラーのあるデータ、ひな形や定型文書のような
一部変化するデータでは、今ひとつ
あいまい性の導入
・エラーや、部分的な変化に対応するには、厳密に一致する文
字列だけでなく、曖昧マッチングの意味であちこちに現れる文字
列を見つける必要がある
・曖昧性の尺度は、ハミング距離、編集距離、固定回数の
ギャップ、マルチプルアラインメントのスコアが小さい、など
・しかし、こうすると、短い頻出文字列がたくさん存在してしまう
・いくら高速なアルゴリズムを作っても、これらを全部列挙する
のは無理だし、そもそも見つけてもうれしくない
・困った困った、ので、違うアプローチを考える
類似部分文字列を使う
・文字列パターンAが、データ文字列S のあちこちに現れるとする
 つまり、{x1,…,xn}番目から始まる部分文字列とA が似ている
・このとき、x1,…,xn 番目から始まる部分文字列は、互いに似てる
・文字列パターンを見つけるのは難しいので、似ている部分文字
列のグループを見つけよう
 文字列パターンの出現位置集合の候補になるだろう
・当然、似ている部分文字列の組を見つけても、それが文字列パ
ターンの出現集合になっているとは限らない
多数決による文字列パターン決め
・出現に対応する文字列パターンは、似ている文字列を重ね合わ
せて、多数決で勝つ者を選んで決めよう
ABCDHFG
AABDEFH
ABCDEFH
BBHDEGH
ABHDHFG
AAHDEFG
------AB*DEF[GH]
グループは極大クリークで
似ているもののグループ化は、「似ている者の間に枝がある」グ
ラフの中からクリーク、特に極大なクリークを見つければいいで
しょう。
・クリーク：全ての頂点間に枝がある部分グラフ
（全てのペアが似ている）
・指数的に沢山あるので、極大なものだけでいいでしょう
似てる文字列の発見
問題：各項目が同じ長さ l の短い文字列（50文字程度）である
データベースを入力したときに、文字列のペアで異なり数（ハミン
グ距離）が d 文字以下である組を全て見つけよ
・長い文字列の比較には、各ポジションを先頭とする長さ l の部
分文字列を全てに対してこの問題を解く。
（似ている部分列はペアを沢山含むところとして見つかる）
ATGCCGCG
GCGTGTAC
GCCTCTAT
TGCGTTTC
TGTAATGA
．．．
・ ATGCCGCG と AAGCCGCC
・ GCCTCTAT と GCTTCTAA
・ TGTAATGA と GGTAATGG
．．．
追加できる候補を絞り込む
・追加できる頂点を効率よく見つけたい
追加できる  クリークの全ての頂点に隣接
あらかじめ、追加できる候補を調べておくと楽
・さらに、新しい頂点を１つ追加したとき、
候補に残る頂点  新しい頂点に隣接
候補の集合の更新は、
追加する頂点に隣接する頂点と、
候補の共通部分をとればいい
クリーク一個あたり、頂点の次数の時間
例題
・このグラフで実際の親子関係を見てみる
１, ２
３
１
３
７
５
４
１, ３, ５
６
２, ４, ６, ８
７
10
８
９
12
２
４
11
10
３, ５, ７, ９, 12
11
９, 11
11
６, ８, 10
11
８, 10, 11
４, ８, 11
12
10, 12
末広がり性
・バックトラックは、各反復で複数の再帰呼び出しをする
 計算木は、下に行くほど大きくなる
 計算時間を支配するのは一番下の数レベル
次数大きい
頂点
・・・
次数小さい
頂点
ほぼ全ての反復が短時間で終了
（1秒間におよそ100万個）
多くの列挙アルゴリズムが似たような再帰構造を持つので、
下のレベルの仕事を上のレベルがやれば、同様の改良ができる
新旧アルゴリズムの比較
30000
25000
既存 r=10
提案 r=10
既存 r=30
提案 r=30
次数巨大あり
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万個あたりの計算時間(秒)
既存と提案手法の比較
頂点数
実験してみると
・クリーク数は意外と小さく、大きさ／個数のヒストグラムも特殊
（ロングテールよりテールが立っている）
・同じもの、続いているものが沢山ある
GAATAGAATCGAATGGAATGGCATCGAATGGAATGGAATG
AATAGAATCGAATGGAATGGCATCGAATGGAATGGAATGG
ATAGAATCGAATGGAATGGCATCGAATGGAATGGAATGGA
TAGAATCGAATGGAATGGCATCGAATGGAATGGAATGGAA
AGAATCGAATGGAATGGCATCGAATGGAATGGAATGGAAT
GAATCGAATGGAATGGCATCGAATGGAATGGAATGGAATG
GGAATAGAATGGAATGGAGTGTAATGGAAAGATATCGAAT
GAATAGAATGGAATGGAGTGTAATGGAAAGATATCGAATG
AATAGAATGGAATGGAGTGTAATGGAAAGATATCGAATGG
ATAGAATGGAATGGAGTGTAATGGAAAGATATCGAATGGA
TAGAATGGAATGGAGTGTAATGGAAAGATATCGAATGGAA
・・・・・
・同じものは１つに、続いているものはつなげてしまいたい
重なりをつなげる
・重なっているクリークとは
{ 1, 6, 30, 51, 85 }
 { 2, 31, 52, 74, 86 }
のように、中身を１つずらしたら多くの位置が同一になるもの
・クリークの集合と、クリークの中身を１増じたものを比較し、共
通部分が大きいものの組を見つけると、重なるものの検出がで
きる
・共通部分の大きいペアの発見  大きさ２の頻出集合発見
なので、簡単・短時間
ヒューリスティックによるつなげ方
・重なり方の関係は、有向グラフになる
・クリークに対して、そのクリークが出枝で隣接するクリークの集
合を、続きクリーク集合と呼ぶ
・つなげるときには
① 入り次数が０の頂点 v を見つけ、v と続きクリーク集合をある
程度（半分以上）共有するクリークの集合を見つける（S とする）
② S の続きクリーク集合の和集合を求める。S のクリークの続
きクリーク集合の最大値が、和集合の半分より小さければ、分
岐していると見なす。（そこまでの共通部分を出力）
③ 分岐していなければ、S を和集合として ② へ
つながった解
・ヒトY染色体頭から200万文字、50文字中違い2、頻出度10
GTGGCGGGCGCCTGTAGTCCCAGCTACT#GGGAGGCTGAGGCAGGAGAAT
GTGGTTTTGATTTGCATTTCTCTGATGGCCAGTGATGATGAGCATTTTTTCATGTGT
GTTTCTTTTGCTGTGCAGAAGCTCTTTAGTTTAATTAGATCCCATTTGTCAATTTTG
GTTTTTTTCTTGTAAATTTGTTTGAGTTCATTGTAGATTCTGGATATTAGCCCTTTGT
CAGATGAGTAGGTTGC
TAAAAAATGATAAAGGGGATATCACCACCGATCCCACAGAAATACAAACTACCA
TAAGTCTTTAATCCATCTTGAATT#ATTTTTGTATAAGGTGTAAGGAAGG
TACCATTCAGGACATAGGCATGGGCAAGGACTTCATGTCTAAAACACCAAAA
・全部で122個。この手の問題としては、解の数が非常に小さい
つながった解２
・日本語webテキスト、100万文字、20文字中違い2、頻出度20
#まじめに恋人#結婚相手を探している#のための出会い系サイトです。#
#・#１０５（フリーダイヤル）０５２・４８#・７５#７
##７００１，０００２，０００３，０００１０，０００円以##
###Ａｌｌ #ｉｇｈｔｓ #ｅｓｅｒｖｅｄ．##
・・・・・・・・・・・・・・・・・・・・
ス腕時計激安通販｜格安最安値通販へ【ポールスミス腕時計ＰＳ#０
金土１２３４５６７８９１０１１１２１３１４１５１６１７１８１９２
０２１２２２３２４２５２６２７２８２９３０３１
年１０月２００#年０９月２００#年０８月２００
名：女性１#名のご参加で、５組の成立となりました。お
・解は38個
まとめ
・類似する文字列を高速発見するアルゴリズムを使って、ミスマッ
チ頻出部分文字列を見つける問題を高速で解く方法を提案しまし
た
・面白いものそんなに多くなく出てくるので、実にいい感じです
・他のものでも（共通部分が取れるものなら、ある程度）使えると
思います
・さあ、がんばって実験と論文書きしましょう
大規模近傍グラフの高速近似作成
宇野毅明（国立情報学研究所
＆総合研究大学院大学）
津田宏治（産業総合研究所
＆マックスプランツ研究所）
杉山将
（東京工業大学）
2008年12月26日 T-primal
基本的な問題設定
項目
項目
・データがあり、その中から似ているもの
の組を見つける、という問題設定
・データの項目数の２乗の時間をかければ
解ける。つまり多項式性は明らか
 項目数が巨大で、２乗では動かない状況を考えよう
・最悪の場合、出力の大きさからして２乗
 出力は少ないと仮定しよう（項目数の××倍、という感じ）
・実問題ではけっこうよく見られるケース
実問題の特徴を生かした計算方法を考えよう
データの種類
・データ／尺度はいろいろ
－多次元ベクトル、集合、文字列、画像・・・
－ユークリッド距離、ハミング距離、編集距離、・・・
・応用もいろいろ
－類似グラフ上での× ×
＝クラスタリング、ブリーフプロパゲーション、などなど
・博物学にならぬよう、根底に流れる理論・知見を得たい
・応用で使いやすいよう、単純な作りで、いいインプリを用意したい
研究の始まり
・津田さんから電話がありまして。
「こんな論文あるんすけど、sachica と組合せて使えない
ですか」
「うまくいきそうですね。やってみましょう」
・プログラミングして実験して、けっこういい感じです
というのが現在の状況。その後、杉山さん、比戸さんに仲
間に入っていただきました。
・学習ではないので、KDDに出そうかと思ってます。
超平面で分類
・多次元ベクトルデータ（点データ） x1, ..., xn ∈ Rd が与えられる
・ここで、ランダムに作った（原点を通る）超平面で点を分類する
・似た方向のベクトルは、超平面の同じ側にいる確率が高い
・ h 個のランダム超平面を発生させると、
似た方向のベクトルは、多くの超平面に
対して同じ側にいる確率が高い
・ 2つのベクトルのなす角度がθ
であるとき、その確率は 1 – (θ/π)
・ 01ベクトル（集合）の場合、
θ=cos-1(|A∩B| / √|A|・|B|) です
複数のランダム超平面
・２つのベクトルのなす角度が θ 以内なら、h 個のランダム超平面
π1,..., πh のうち多くのもので符号（どちら側にいるか）が一致
 2項分布を使って計算すると、確率 XX以上で k 個以上が一
致する、という最大の k を見つけることができる
 少し大きめの h を選んでおくと、角度が θ以上のベクトル対が
上記の条件を満たすことが少なくなる
・多くのベクトルからなるデータベースの中から、この条件を使っ
て、なす角度が小さいものを近似的に見つけられる
・符号の一致数が多いもの＝ハミング距離の短いものなので、
先のアルゴリズム sachica が使える
ランダム超平面の使い方
① 多次元ベクトルデータベース（点データ） x1, ..., xn ∈ Rd 、角度
簡単
閾値θ、精度閾値σを入力
② n、θ、σから、ハミング距離を見つけやすいよう十分に大きい h
を選び、２項分布を使ってハミング距離の閾値 z を計算
簡単
③ ランダムな原点を通る超平面（法線ベクトル） π1・・・πh を生成
簡単
④ 各ベクトル xi について符号列 H(xi) = π1(xi)・・・π(xi) を計算
簡単
⑤ H(xi) と H(xj) のハミング距離が閾値 z より短いペアxi, xj を列
先日のアルゴリズム
挙
sachica を利用
⑥見つけたペアの中で実際になす角度が θ以下のものを出力
簡単
実験：ランダム超平面
・頻出集合発見のベンチマーク問題
・ tiny images という小さい画像のデータベースから取ってきたデー
タ（無圧縮画像データをバイナリファイルとして比較、およそ3000
次元）
・ t=0.1π,0.2π で実験
・ Core2Duo E8400、4GB RAM
・ tiny images 6万件、角度 0.1π で、
精度保証が 0.84だと秒、0.92 だと65秒、0.96 で165秒、0.98で96
秒、 0.99 で 260秒、0.995 で
実験結果：tiny images
・ tiny images 6万件、角度 0.1π で、
－精度保証が 0.84だと37 秒、0.92 だと65秒、0.96 で165秒、0.98
で96秒、 0.99 で 260秒、0.995 で
－見つけ損ない数は、(1-精度) にほぼ比例。が安定的でない
・ tiny images 6万件、角度 0.15π で、
－精度保証が 0.84だと 182秒、0.92 だと224秒、0.96 で291秒、
0.98で368秒、 0.99 で771 秒
－ハミング距離が長いので、計算がきつい（100中40文字とか）
・ tiny images 6万件、角度 0.05π で、
－精度保証が 0.84だと 15 秒、0.92 だと20秒、0.96 で25秒、0.98
で33秒、 0.99 で 45 秒。ほとんどが問題変換とチェック
実験結果：tiny images
・ tiny images 6万件、角度 0.1π で、
－精度保証が 0.84だと37 秒、0.92 だと65秒、0.96 で165秒、0.98
で96秒、 0.99 で 260秒、0.995 で
－見つけ損ない数は、(1-精度) にほぼ比例。が安定的でない
・ tiny images 6万件、角度 0.15π で、
－精度保証が 0.84だと 182秒、0.92 だと224秒、0.96 で291秒、
0.98で368秒、 0.99 で771 秒
－ハミング距離が長いので、計算がきつい（100中40文字とか）
・ cover tree というnearest neighbor 検索アルゴリズムを全部の点に
対して検索かけてみたが、6．7万件では 1時間たっても終わらず。3
．8万件は50分ほどで終了
実験結果：トランザクションデータ
・ 55万件のPOSデータでθ＝.1πのとき（3000次元）
－精度保証が 0.5-0.9 で 30-50秒程度
－データがスパースなので、各ベクトルの非ゼロ要素はせいぜい
5-6個。よってほとんどが「まったく同じもの」
・機械学習のベンチマーク connect 6.6万件、(100次元、密度50%く
らい)のときは、cover tree だと 1000秒くらい
・ sachica を使うと、θ=.1π、精度保証0.9 で500秒くらい、 0.5 だと20
秒くらい
・ kosarak というクリックストリームデータは、まったく同じもののペア
だけで1億以上のペアがあり、計算できず
実は
・精度を上げるには、精度保証を上げて時間を掛けて解くしかない
・わけではない。例えば精度保証 0.9 の計算を2回して和集合を求
めると、各枝の見つかる確率は0.99 になる。3回やれば0.999。回数
を増やすだけで（線形のコスト増加で）精度を指数的に上げられる
・確率0.5で見つけられれば、それを10回すると1023/1024 の確率（
0.999)で各枝が見つかる
・角度0.1π、保証0.5で実行すると、38万件でも2分程度
1000次元、保証0.5、角度0.05π、100万件でも4分程度
この時点で、入力ファイルの大きさが1GBを突破。メモリが限界
さらなる高速化
 そのうち前処理・後処理が8分以上・・・、
というわけで、内積の計算を改善したら2分になりました。ただ、
これでも、sachica の実行時間は20秒ほど
 少し文字列を長めにするようにして、間違いが起きにくくして
みたら、計算時間が1/3 程度に短くなりました
・この作業を10回ほどやるので、一回が4分でも全体は40分。
ただ、出力のチェックは、きっと同じものに対するチェックを何回
もするはず。ここのところが将来的な改良ポイント
まとめ
・ min-wise independence やベクトルとの内積の符号など、「類似
すると一致する可能性が高い指標」をランダムに複数用いて文字
列を作り、文字列のハミング距離が短いものを見つけることで、短
時間で高い精度で類似するものを見つける方法の提案
・ベクトルデータと集合データ
・ sachica を利用して高速計算
・繰り返し計算による精度向上
どなたかいいデータ（多量の項目からなるベクトルデータ）持って
ないでしょうか？

Download Report