文字列データの高速類似性解析と
可視化技術
宇野 毅明
国立情報学研究所
2009 年 10 月 24 日 SCOPE
モチベーションとバックグラウンド
大量の文字列データ
• 近年、大量の文字列データが簡単に蓄積されるようになりました。
－ 電子化された書籍、新聞、雑誌
－ Webなどの多数の人間が書いたテキストデータ
－ 特許文書や論文の文書
－ OCRなどで読み取った過去の社内文書
－ ヒトゲノムを始めとするゲノム情報
• データが大きすぎて、線形時間程度の処理しかできない
＋ 索引付けと（キーワード）検索
＋ 圧縮・展開
＋ 文字数・文字種・n-gram のカウント、分布
＋ 文単位の、単語切り出し、構文理解・・・
• 複雑な、組合せ的な処理はほとんど出来ていない
IT系のアプローチ
• それでも、情報学の研究者やIT企業は、大規模テキストデータを使っ
ていろいろなことをしている
＋ Web検索、データベースの構築
＋ 自動文書分類、文書ランキング、評判分析、話題抽出、
＋ 類似文書の検出、おすすめの表示 （リコメンデーション）
• どれも、小さいデータにある種の処理を行ない、それをデータベース
に登録するタイプ （グーグルランクを除く）
• 逆に、全体を眺めるような処理は行なわれていない
－ 話題の伝搬、引用関係
－ （部分的に）似た文書の検出、固有な文書の検出
－ 頻出するフレーズの発見
部分的な類似構造を検出できたら、一気にできることが増えそう
文書以外のデータでも
• ゲノム情報学の分野では、ゲノム情報（実際は文字列データ）を
を解析している
• やはりできていることは単純なことで、複雑な解析は難しい
＋ 完全一致をベースとした検索・比較
＋ 遺伝子の推定・・・
• 類似性の解析ができることで、効率化が進むものは多い
－ 機能が未知の遺伝子と類似する遺伝子を探す
－ 異なる種のゲノムの比較 （類似部分には意味がある）
－ ゲノム読み取り時に、断片配列をつなげる
－ 固有な部分配列の同定をして、マーカーとして使う
－ 同じく、プライマーとしてPCR増幅に使う
ゲノムの読み取り
ゲノムを読み取る方法
１． DNAを薬で溶かして、ひも状にする
２．放射線などを当てて、短い切片にぶつぶつ切る
３．機械で読む。1回で500文字程度読める
ただし、精度は99.9%程度。1000文字に1文字くらいミスる
４．読んだ結果をつなぎ合わせて、もとのゲノムを構築する
類似性のモデル
• ゲノムの変化（変異、あるいは実験での読み取りエラー）は、
局所的には、1文字単位で起きる
• 既存研究では、文字列の尺度で類似度を判定している
（コスト付き）編集距離
（ときどき）ハミング距離
• 両者ともに、数理的に美しい尺度であり、計算も容易
－ 長さ n の文字列の比較
ハミング距離： O(n) 時間、 編集距離 O(n2) 時間
• 実際には、大域的な入れ替わり構造がある
相同検索（類似文字列検索）の困難さ
• 相同検索は、ゲノム解析における中心的な道具
計算のうち半分以上は相同検索とも…
• しかし、類似検索なので計算資源が必要
現在は並列計算にたよっている
• 類似検索なので、基本的に２分探索のような手法は使えない
ソフトにより性能は異なるが、100万文字の配列（文字列）２つ
を比較するのにもかなり（数分から数時間）かかる
染色体のような、数億文字ある配列の比較には多大な計算
資源が必要 （あるいはヒューリスティックでやる）
もし、相同領域を短時間で行えるようになるなら、
それがゲノム研究に与える影響は大きい
類似構造発見の研究（アルゴリズム的）
• フィンガープリントを使った類似検索 （特徴量が一致するものを検索）
（ざっくり言って）文章単位しか狙っていない
類似するからと言ってフィンガープリントが一致するとは限らない
• BLASTを始めとする相同発見アルゴリズム
（例えば11文字の）短い完全一致領域を見つけ、そこを種として検索
文字列が長いと、大量の完全一致がある
11文字を長くすると精度が落ちる
良く現れる単語は候補から除外、遺伝子部分だけ注目
といった処理をしているようだ
• 類似検索
大量のクエリを実行しなければならない
類似検索は通常、完全一致検索より大幅に時間がかかる
アルゴリズム理論からのアプローチ
• 計算の高速化において、並列計算は強力であるが、コストが
かかるのが欠点 （プログラミングの複雑さも含め）
• アルゴリズム理論による高速化は、問題の大きさに対する計
算時間の増加を、計算手法の設計変更により、抑える
（もとから線形時間のタスクは取り組む意味がない）
100項目
100万項目
2-3倍
10000倍
アルゴリズム理論から、類似構造発見に取り組んでみる
問題のモデル化とアルゴリズム
何がほんとに似ているか
• 生物系の研究者に聞くと、編集距離は（距離が大きいと）研究者の直
感に対応していないようだ （テキストでもそのようだ）
同じ編集距離（ハミング距離）でも、似てる感が大きく違う
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 個のブロックが同じ
必ずどれかの組合せで見つかる
• 部分問題は、バケツソートや基数ソートで速く解ける
• 組合せの数は 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
計算量について
• ソートの部分は基数ソートで O(l |S|) 時間
• 基数ソートの1文字分ソートする部分を、複数のソートで共有する
ようにすると、ソート一回当たりの時間は O((l/k) |S|) に減少する
• 分類にかかる時間は、トータルで O((l/k) |S| kCd) 時間
• 全対比較の部分は、できたグループの大きさによるので、平均
的なことしか言えない、が、
• もし k=l ならば、グループ内の全てのペアは似ている、となる
１つのペアが kCd 回見つかるので、計算時間は O((|S| + dN)
kCd) となる （N は見つかるペアの数）
重複の回避
• まったく同じ文字列があると、全てのブロックの組合せで見
つかるので、 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にす
ればいい
ただし、(短い配列の）検索は苦手
（全部の比較と一部の比較の速度があまり変わらない）
なぜ高速化できるのか？
• チェックするマスを図示してみる
• アクセスするマス目の面積が大きく違う
• グループの数が増えると、より速くなる
実験：長さ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文字)
実験： 長さ30で、異なり数 d を変化させる
日本語webテキストデータ, 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)
キャッシュとの相性
• 近年のコンピュータアーキテクチャでは、キャッシュメモリとアル
ゴリズムの相性が良いと計算が速くなる
＋ メモリアクセスが乱雑でなく、ブロック化 or スキャン型
＋ ある期間に、少しのメモリアクセスをして、多数の計算を
する、というタイプの計算が全体を占める
• 複数分類法では、基数ソートがこれらの条件に当てはまらない
• しかし、全対比較を行なう部分は、この条件に当てはまる
• 問題を再帰的に分割するので、ある一定レベルより先の子問題
は、上記の条件を満たす
結果、全体としてみると、それなりに当てはまりが良い
コア並列化
• 最近のCPUは複数のコアを内蔵するものが多い
• 通常の並列化と異なる点は
＋ メモリを共有しているので、通信コストはさほどかからず、
共有メモリを使う並列化が有効
＋ メモリバスを共有しているので、メモリに頻繁にアクセス
する設計だと、メモリバスがボトルネックになる
• 複数分類法では、
－ 基問題を分割した子問題を（メモリコピーをせず）それぞれの
コアが処理できるので、効果的
＋ 基数ソートはメモリに頻繁にアクセスするため、良くない
＋ 全対比較はブロック化でメモリアクセス効率が良くなる
並列化の結果
• 大型の問題を解く場合の加速度は、この程度。
２コア 1.7 倍
４コア 3 倍
（AMD opetron）
• 全対比較のところは並列化の効果が高そうなので、
そこだけ GPU コンピューティングさせてみると、
＋ 128GPUコア で 30倍速程度
• うまく組合せてアレンジすれば、かなりの高速化が期待できそう。
長さ l が大きい場合
• l および k が大きくなると、ソートの回数が増えるため、計算は遅
くなる （1000文字中異なりが100、とか）
複数分類法と同じアイディアで高速化できる
• 長さ l の文字列を h 個に分割する
２つの文字列の距離がk 以下なら、必ず距離がk/h 以下のブ
ロックが存在
• k の選択と同じように、計算コストを算定して最適な h を選ぶ
分割の効能
• 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 文字なので、グループ数は同じ
比較する部分文字列の省略
• 少し長めの類似構造を調べたいときには、比較する部分文
字列を省略しても効果がある
－ 比較する文字列AとB （両者が同じこともあり得る）から長
さ l の文字列を取るときに、適当な k を定めて、A の部分文
字列のうち k/l 、B の 1/k を選び出して比較
－ どのような（少し長い）部分列の組に対しても、1/l 程度の
比較される部分列を含む
任意の部分列の組に対して
A
B
このように部分列が比較される
文字列の比較だけでなく
• 今まで、文字列の問題だけを考えてきたが、別に文字列にこだ
わる必要はない
－ 行列の部分行列
－ 離散ベクトル（行列）データの比較
• ベクトルデータを離散化して比較、01ベクトルの比較、画像の部
分比較などに使える
大規模データに対して近傍グラフが短時間で作れる！
０１０１００００１１
１１０１００００１１
１１００１０１０１０
００００１１００００
・・・・
10, 143, 29, 13
33, 29, 143, 35
1, 76, 33, 24
132, 7, 24, 24
・・・
類似構造の可視化
ドットプロットによる可視化
• 大域的な類似構造を捕らえるためには可視化が良い
• ドットプロットという可視化手法がある； 画像の横軸と縦軸を比較
したい文字列に対応させ、類似する部分に対応するピクセルに点を
打つ
• もし長い類似構造があると、
それは部分的な対角線として
可視化される
string A
String B
• 点の色の濃さを、対応する
部分列の組の中に含まれる
類似部分列の組にする
比較する部分列は、全ての
ポジションから取る
ゲノムの比較 (1)
ヒト21番染色体とチンパンジー22番染色体の比較
• 長さ3000万の配列×2 から、30文字の切片を3000万個取る
• 似ている部分配列のペアの数に応じて、各ドットの明るさを変える
ヒト 21番染色体
• 白い部分が
「似ている可能性のある部分」 チ
ン
• 黒い部分が
パ
「(絶対に)似ていない部分」 ン
ジ
• 格子模様は、繰り返し
配列を拾っている
PCで 1時間で可能
ー
22
番
染
色
体
ゲノムの比較 (2)
• ちょっと違いが大きなゲノムを比較してみる； マウスの11番染色
体とヒトの17番染色体の比較を、少し誤差の許容を大きくしてみる
と…
PCで2分
残念ながら何も見えない
• 各文字列について「10個
の相手としかペアを作ら
ない」とすると、少し見える
まだまだノイジーだし、
正確性を失っている
Human 17th chr
• 短いノイズのような多量の類似
部分列が全てを隠している
Mouse 11th chr.
同じくらいの明るさの点
• 同じ程度の明るさのピクセルでも、中の類似文字列のペアがど
のように分布しているかはわからない
• ペアが対角線に並んでいるところに興味がある
分散しているやつらはいらない
一部分に集中してしまっている物も興味がない
• 対角線的なペアのみを取り出すために、凝った方法を考えるとき
りがないので、簡単な方法でやってみる
長方形フィルター
• 対角線方向に傾けた、長方形の箱を考える (長さが α で幅が β)
もし、その箱の中にある程度のペアが入るなら、対角線上に並
んでいると考えていいだろう
• しかし、ペアがある一点に集中していたら、それは良くない
• ある箱の置き方に対して、ペアが閾値以上、集中せずに含まれ
るようなとき、それらのペアを残し、任意の箱の置き方に対してそ
のようにならないペアを消す
新しいモデル
• ２つの文字列の類似を「似ている短い区間がいくつかある」で定義
（距離ではなく、似ているかいないかの２値になる）
• この条件は、ある意味で、
既存の類似性の条件を弱めている
• 既存の意味での類似性の下界にもなる
例：長さ3000でハミング距離が10%弱
(間違い290)なら、長さ30で間違い2の部分列を、少なくとも3つは含む
• 離れた位置にある部分が似ていても全体が似ていることにはならない
ので、ずれの最大をβで制限する
• ２つの文字列が似ている部分文字列を持つ
「長さα、幅βの領域に閾値以上の類似部分文字列のペアがある」
ということになる
効率良く計算できるか
• 類似部分文字列を持つ長さα幅βの領域をどう見つけるか
ペア長さαの部分文字列を全対比較 ２乗の時間かかる
別の方法を考えないと、とても解けない
• 最初に、短くて似ている部分
文字列のペアを全部見つけておく
• 幅２βの斜めの線に沿って、長さαの領域に
閾値以上のペアがあるところを探す
• 斜め線をβずつずらして、全ての部分について似ている部分を探す
• 長さα幅βの似ている部分列は必ず見つかる(そうでないものも発見)
• 短くて似ている部分列を効率良く見つければよい
箱フィルタを使ってもう一度
• もう一度、マウスの11番染色体とヒトの17番染色体の比較をして
みる
• 箱の長さ、幅、閾値を 3000, 300, 3 にしてみる
• ノイズがほぼ取れている
PC で3分
Human 17th chr
• 画像の画素数を大きく
すれば、さらにノイズを
取り除ける
Mouse 11th chr.
さらに大きな比較
Mouse X chr.
マウスXとヒトX
染色体の比較
(両者1.5億文字)
Note:
BLASTZ で2週間
MURASAKI
だと 2-3 時間
ただし誤差が1%
だそうです。
Human X chr
PCで15分
ゲノムの比較 (3)
バクテリアを30種
ABC順の取得し
つなげて比較
• 一度に複数の
ゲノムを比較できる
PCで 1時間で可能
多数の比較結果を、色を変えて合成
• ある文字列を固定し、それと、他の文字列を比較して、結果
を（色を変えて）重ね合わせると、固定した文字列が他のどこ
と対応するかがわかる
ヒト22番染色体
マウスの全ての染色体
（全て左端から開始、右端は長さに応じて変化）
PCで6時間程度（3GB）
まとめ１
• 部短時間で類似する部分列を全て見つけ出す高速なアルゴリズ
ムを提案
• 類似する部分列をいくつ含むかに着目した新しい類似の尺度を
提案した
• 実際にゲノムで比較を行い、既存の方法よりはるかに短時間で
ある程度の保証をもつ解を得た
－ ヒト、チンパンジー、マウスの染色体の比較
バクテリアゲノムの多対多比較
•ツールとしての完成度を高める（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 という小さい画像のデータベースから取ってきたデー
タ（無圧縮グレイスケール画像データをバイナリファイルとして比
較、およそ1000次元）
• 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 で….
精度保証が上がると、指数的に時間がかかる
実は
• 精度を上げるには、精度保証を上げて時間を掛けて解くしかない
• わけではない。例えば精度保証 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分。
ただ、出力のチェックは、きっと同じものに対するチェックを何回
もするはず。ここのところが将来的な改良ポイント
実験結果１
• 問題サイズの増加に対する計算時間の増加。他の手法と比較
threshold
= 0.1 pi
10000
1000
100
MSM 0.1
CT 0.1
Computation time (sec)
LSH 0.1
10
1
1250
2500
5000
10000
20000
40000
80000
160000
320000
#vectors
実験結果２
• 解の数（似ているペアの数）はどのように増えるか
• 解１つあたりの計算時間はどうなるか
1E+09
100
100000000
MSM 0.1
threshold
= 0.1 pi
10000000
1000000
10
100000
MSM
0.1
0.05
0.1
0.15
1000
100
10
Computation time (sec)
#number of neighbor pairs (m)
10000
1
0.1
1
#vectors
#vectors
実験結果３
• 見つけそこないはどのように減っていくか (精度=0.9）
1
1
2
3
4
5
6
7
#replicates
#type II errors (ratio)
0.1
0.01
0.001
MSM 0.05
0.0001
MSM 0.1
MSM 0.15
0.00001
0.000001
0.0000001
1E-08
9.75
9.5
9.25
9
8.75
8.5
8.25
8
7.75
7.5
7.25
7
6.75
6.5
6.25
6
5.75
5.5
5.25
5
4.75
4.5
4.25
4
3.75
3.5
3.25
3
2.75
2.5
2.25
2
1.75
1.5
1.25
1
0.75
0.5
0.25
0
cosine distance (times threshold)
#pairs
実験結果４
• 本当は近くない奴をどの程度見つけたか
1400000
1200000
1000000
800000
600000
400000
200000
0
まとめ
• min-wise independence やベクトルとの内積の符号など、「類似す
ると一致する可能性が高い指標」をランダムに複数用いて文字列
を作り、文字列のハミング距離が短いものを見つけることで、短時
間で高い精度で類似するものを見つける方法の提案
• ベクトルデータと集合データ
• sachica を利用して高速計算
• 繰り返し計算による精度向上
どなたかいいデータ （多量の項目からなるベクトルデータ） 持って
ないでしょうか？
© Copyright 2024 ExpyDoc
