パターンマイニングの新しい落としどころ
－クラスタリングを用いたパターンマイニング－
宇野 毅明 （国立情報学研究所
＆総合研究大学院大学）
2010年9月5日 IBISML,PRMU,CVIM
パターンマイニング
• 大規模データを入力し、そのデータに良く現れるパターンを全て見
つける問題
• データから、特徴的な部分を「発見」したいときに、その「候補」を見
つける手法として有益
• データマイニング分野の中心的な問題。たくさんの研究あり
• しかし、最近は閉塞感も漂う
本発表
パターンマイニングに新しいパラダイムを導入 （したいですね）
パターン
マイニング
データベース
実験1
●
●
●
▲
●
実験2
▲
●
●
●
●
●
▲
▲
実験3
▲
実験4
▲
▲
▲
▲
▲
実験結果
▲
●
●
●
●
ATGCGCCGTA
TAGCGGGTGG
TTCGCGTTAG
GGATATAAAT
GCGCCAAATA
ATAATGTATTA
TTGAAGGGCG
ACAGTCTCTCA
ATAAGCGGCT
ゲノム情報
パターン
• 実験1● ,実験3 ▲
• 実験2● ,実験4●
• ATGCAT
• 実験2●, 実験3 ▲, 実験4●
• 実験2▲ ,実験3 ▲
• CCCGGGTAA
．
• GGCGTTA
．
• ATAAGGG
．
．
．
．
パターンマイニングを総括
（私見です。ご了承下さい）
原始的なモチベーション
• もともとのモチベーションは、たぶん、
（大きな）データの局所的な特徴を捉えたい
• 全体的に均質ではなく、多種の要素が混在する巨大なデータの解
析が必要になってきたから
単に全体的な分布を捕らえてしまうと、
局所に際だつ特徴は全て埋もれてしまう
• 局所的な特徴が得られれば、マイノリティーに対応できる
嗜好的な商品の販売戦略
異常事例の特徴解析
顧客分類、データ分類
．．．．
問題の定式化
• 次にモデル作り。局所的な特徴とは何か
共通の要因が知りたいから、共通する構造にしましょう
顕著なものが知りたいので、多くの項目に含まれる構造を
という流れだと思います。
パターンマイニング
（巨大な）データの、閾値以上の項目に含まれる（現れる）、
ある決められたクラスの構造を全て見つける問題
• 以後、apriori、深さ優先など多くの探索手法
ビットマップやFP-tree などデータ構造とアルゴリズム
飽和集合と極大頻出集合など、発展させたモデル が出ます。
問題設定：意外とイケてます
• 元のモチベーションが「発見」。なので最適化型の問題設定は有用
性が低く、列挙型が適当
○
• 大規模データを対象とするので、単純なデータから単純な評価値
で解を見つけるようにしている
○
• 最小サポートというパラメータが存在し、それで見つける解をコント
ロールできる
○
• 便利にできている
アルゴリズムから見ると
• パターンマイニングは、データの巨大さと解の多さから、重たい計
算を要求するため、高速アルゴリズムは必須要因
• アルゴリズムから見ると、パターンマイニングは「列挙問題」
• 列挙の中でも簡単な問題になっているため、楽に設計ができる
単調性、閾値（最小サポート）による制約、単純なアイテム集合
• もし「情報量最大のものk個」なら、これほど流行らなかっただろう
（アルゴリズムとモデルの間の、いい落としどころを見つけている）
特徴の定義
が複雑
解析モデル
パターン
マイニング
指数的に時
間がかかる
列挙
アルゴリズム
既存研究の歴史
• いい落としどころ（新しい研究分野）ができたので、研究は発展
多種の構造データへの対応、頻度の定義、パターンの定義（極大）
探索アルゴリズム、データ構造．．．など
• が、今日はアルゴリズムの話はしません
• 最近目につく問題点を、深く議論したいと思います。
最近目につく問題点
• 最近、パターンマイニングの研究は、たこつぼにはまっている気が
します。やり尽くされているので、新規の研究は難しいと言うことです
いいモデルがなかなか出てこない。いい技術も
出てこない。既存のものを大きく超えることは難しい
モデルの単純さゆえに直接的に利用ができない。
副次的に利用するには、道具が複雑すぎる
有益なものを見つけようとすると、解が沢山出てくる。
大量の似た解を処理できない
• 昔はきっと、「これができれば」という希望があったと思います
また距離が開いてしまった
• パターンマイニングは、いい落としどころだったはずだが、いつの
まにかアルゴリズムのほうに入ってしまっている
（最近の研究はモデルでなく「アルゴリズムの拡張」になっている）
• いつの間にか、また「モデルとアルゴリズムの距離」が開いた！
• ということは、また新しい「落としどころ」が必要
新たな落としどころを、計算とモデルの両面から考える
特徴の定義
が複雑
解析モデル
パターン
マイニング
指数的に時
間がかかる
パターン
マイニング 列挙アル
列挙
ゴリズム
アルゴリズム
新しい問題設定とその解法
もう一度モチベーションから
• 立ち戻ってみると、もともと「局所的な」「特徴」が見つけたかったの
だが、「大量の局所」と「大量の特徴」が見つかってしまっている。
• 少しの（代表的な）局所の、代表的な特徴がわかれば十分だろう
• しかし、代表のみを残すために、パターンに制約を付ける、というア
プローチは今ひとつうまくいっていない。
多くの面白い局所のパターンを切ってしまう可能性があるため
• 飽和集合のように、完全性
を保証しようとすると、少し
しか減らせない
（臆病すぎ）
データ
パターンへの制約は妥当か？
• 「局所」とは、パターンマイニングの言葉で言えば、
「パターンが出現する項目の集合」
• 「出現集合が他と違うもの」を残したくて、「出現集合が似ているも
の」はまとめたい
パターンに対する制約ではない!!!
パターンに対する制約でうまくゆく訳がない
• もっと「出現集合」に
注目して計算すべき
代表は、出現集合に制約
を与えて定義すべき
データ
複雑なモデル・手法は、、、
• こういう方向性で問題を考えると、ついつい複雑なモデルを複雑
な手法を使って解く、というパターンになる。
あるいは、ある程度強い仮定を置いて問題を解くことになる
（アルゴリズム的な意味です）
• 数理的にはいい結果が出せるかもしれないが、利用者にとって
は親切でない
• だんだん、何をしているのか分からなくなってくる、、、
（最適化の分野、アルゴリズムの分野などで、こういうトピックをいく
つか見てきました。）
格言をマネました
• 「簡単な問題を解く途中で、難しい問題を解いてはならない。なぜな
ら、そこでノイズが発生し精度が減少するからである」 by Vapnik
という格言があるそうです。そこで、
• 「単純で頑強な解を求める途中で、複雑で不定な計算を用いては
ならない。なぜなら、そこで単純性と頑強性が失われるからである」
by うの
• この方針にしたがって、添え字順や計算の順序に振り回されない
手法を考えよう
単純な
構造
難しい
不安定
単純•安定
な解
「見つけ方」の逆転
・ 頻出パターンは、「局所的」な「特徴」であるが、その見つけ方は、
まず特徴候補を列挙して、どの局所に現れるかを計算している。
定義の流れと逆なので、よく考えると気持ち悪い
• まず、「共通な要因を持つ項目の集合」を見つけてから、
「それらに共通する特徴」を見つけるようにできるといい。
定義の流れに合っているので、自然な感じ
「無駄なパターンを見つけなく」なってくれるとうれしい
データ
データ
もう、あるんじゃないですか？
• この方法、とどのつまりは類似性に基づいてクラスタリングして、
共通するパターンを見つけよう、ということ。
Q: すでにあるんじゃないですか？
• A: あります。データをクラスタリングして、その中心を取って代
表とするような、パターン学習は多くあります。
• が、心意気が違います。
「クラスタリング」が「分類」なの
が問題です
思考実験
• Webページ（サイト）を、リンク先の類似性でクラスタリングする
＋ g○ogle, Yah○o, amaz○n にリンクしているページ、という巨
大クラスタができそう。で、これら3サイトが特徴
これら3サイトにリンクしていると、このクラスタに吸収されて
しまい、マイナーなトピックで類似している人々が全滅してしまう
• 宇野のページは、どのページも、トップページ、英語版、NII、にリ
ンクしているので、強力に全部似ているわけですが、「アルゴリズ
ム関係にリンクを張っているサイト」でくくって欲しいのです
• マイニングの基本「自明でない、深いパターンを見つけたい」とい
う心意気が否定されるモデリングになっているので、流行らない (?)
なんとかしようとすると
• 例えば、クラスタ数を変えれば、隠れたクラスタも見つけられるかも
しかし、クラスタ数をあらかじめ決めるのが難しい
• 雰囲気的には、頻度を決めうちしてパターンマイニングをしている
ようなもの。全てのクラスタ数でのクラスタを列挙すればいいか。
• この問題、たぶんマルチラベルクラスタリングだが、ちょっと雰囲気
が違う感じがする （ラベルではなく、グループ分けが知りたい）
（マルチラベル自体、研究が少なく、
単純でぱっとした手法は難しそう）
クリークによる局所構造発見
• 共通した構造を持つ項目の集合
どの２つの項目も共通する構造を持つ （類似性、と呼んでおく）
どの２つの項目も類似性を持つ項目集合を見つけよう
• 「類似する項目」の間に枝が張ってあると思うと、
局所的な項目集合 （極大）クリーク
• 極大クリークを列挙することで、
「類似する項目集合」を見つけてしまおう
（クリークは高速列挙できる）
クリークマイニングの弱点
• クリークは基本的に局所構造を表すが、歓迎されないものもある
★ とてもよく似たクリークは不要
▲ クリークとクリークを橋渡しする構造も（小さければ）不要
• それぞれ、★ クリークに枝欠損があるとき、▲ クリーク同士が近
いとき、に多発する
クリーク
クリーク
クリーク
クリ
ーク
クリ
ーク
クリ
ーク
クリ
ーク
類似構造を考えると
• ★ クリークの枝欠損、▲ 近いクリーク、は多発しないだろう
★ A と B は多くのC に対して共に共通の構造を持つ
A と B も共通の構造を持つ可能性が高いだろう
▲局所構造の多くが互いに共通の構造を持つ
全体が共通の構造を持ちそうだ
• つまり、共通の構造を持つもの（似ている
もの）が結ばれたグラフには、それほど多く
の極大クリークはないだろう、と推測される
クリーク
クリ
ーク
クリ
ーク
データクリーニング
• 逆に、積極的に不利な構造をグラフから取り除くと、より局所をはっ
きりさせられる （小さなクリークにしか含まれない枝は消していい）
－A と B 両方に隣接する頂点が多数あるなら、AB 間に枝をはる
★ クリークの枝欠損がなくなる
－A と B 両方に隣接する頂点が少しなら、AB 間の枝を切る
▲ 近いクリークを結ぶ枝が無くなる
クリーク
• 極大クリークの数が非常に小さい
グラフができるものと期待される
クリ
ーク
クリ
ーク
共通部分を取ってパターンを作る
• 局所的な項目グループが得られたら、それら項目の共通部分を
取ればパターンが得られる、 だろう。
• 共通部分が素直に取れないと、共通部分取得自体が一つの選
択問題になるが、ここは自然に行うことを目指す
（例えば頻度チャートとか、多数決による決定がある）
1, 2, 3, 4, 5, 6
1, 2, 3, 5
1, 2, 3, 4
------------1,2,3,(4),(5)
1, 2, 3, 4
1, 2,
5, 6
3, 4, 5, 6
-------------------------(1),(2),(3),(4),(5),(6)
計算的な課題
• 類似する項目の組を全て見つけ、近接グラフを作る
アイテムセットマイニングの場合、大きさ２のアイテム集合
を見つける問題になる
A: 1, 2, 3, 4, 5, 6
B: 1, 2, 3, 5
C: 1, 2, 3, 4
• 極大クリーク列挙は、いろいろな方法で高速に列挙できる
• 共通部分を取るところは、多数決を取っているだけなので、たいし
た時間はかからない
というわけで、高速計算が可能なモデル
アルゴリズム的な特性
• アルゴリズムから見た解法の特性は、と言うと、
① 仕組みがシンプル
類似性の列挙・クリーク列挙・多数決、どれも比較的単純
なので、
② 変化への対応が簡単
類似項目の列挙と多数決を組み込めばすぐに改良できる
① 結果がロバスト
変数の添え字順などによる変化がない
パラメータの変化による解の変化も、ある程度少ないだろう。
（クリークが大きくなったり小さくなったりするだけなので）
ねらっているところに、うまく着陸できている、か？
計算実験１：Webリンクデータ
•日本のWebリンクデータ (from 東大喜連川研究室)
－ ノード数 550万、枝数1300万 （サイト単位に加工済み）
• Web はデータが大きいために、手法にある程度流れがある
+ データ全体を簡単な手法で解析
（(k)連結成分、強連結成分、ページランク、最大流、、）
+ データをしぼって深い解析
（評判分析、リンク予測、、、）
（Webテキストマイニングは、リンク解析ではない）
• クリークを列挙して、コミュニティーを見つける研究もある
（が、解の多さが問題）
計算実験１：Webリンクデータ
• クラスタリングしようと思って極大クリークを列挙すると、
数が大きすぎて列挙できない
リンク先の類似性でデータを作り直してみる
• 20個以上のリンク先を共有するものを「似ている」とし、大きさ
20以上の極大クリークを列挙
極大クリーク数が約 8000個に減少！
ほとんどがスパムのグループ、、、
• 計算時間はおよそ10分（大きさ２の頻出集合を見つけているの
と等価）。実用に十分耐えうる
解の分布
• 通常のパターンマイニング（極大クリーク列挙）では、解が大
きくなるにつれ指数的にその数が増える
• 本手法の場合、非常に緩やかに解数が増加し、さらに非常に
大きな解がぽつぽつと見つかる
大きな解を見つけるために要する時間は格段に短い
非自明な解を見つけやすい？？？
極大クリーク数
• ある程度、情報をアブストラクト
することに成功しているのだろう
解の大きさ
実験２：BMS-WebView2 (クリック)
• KDDで使われたクリックストリームのベンチマークデータ
－ アイテム数3300，トランザクション数 7.7万 平均サイズ 5
• 頻出度100で、頻出集合が1万個ほど、50で7万個ほど
• まずは、アイテムの類似性によるクラスタを見てみる
• 100(50)以上のトランザクションに共通して含まれていたら「似て
いる」として本手法を適用
極大クリークが1個だけ！ （全部が含まれる）
ある程度頻出するアイテム全てが似てしまっている
• 計算時間も意外と長い（10分。頻出集合は10秒）
原因の推測
• クリックストリームデータには、ある種の特徴があるだろう
－ トップページから順にリンクをつついてページをたどる
－ だいたいのサイトはツリー構造をしている
ほとんどの項目に共通して含まれるページが自然と多くなる
（ツリーの根に近いページは、多くの項目に含まれる）
必然的に、多くのページが、多くの項目に共通して含まれてし
まう
対策
• たくさんの項目に含まれるページがあって、それが良くない
頻出度がある程度以上高いアイテムは無視しよう
• でもやっぱりだめ。極大クリークは一個だけ
（主要なページは、行き来する人がたくさんいて、自然と
同一クラスタに入ってしまうのであろう。）
• こちらではうまくいかない。やはり「特徴のある局所を見つける」
ほうがいいのだろう。
トランザクションをクラスタリングして、その共通部分を取る
トランザクション クラスタリング
• 10個のアイテムを共有するトランザクションが似てるとして実行
• でもやっぱりだめ。極大クリークは一個だけ
（主要なページは、行き来する人がたくさんいて、自然と
同一クラスタに入ってしまうのであろう。）
• また、頻出度が高いアイテムを無視してみる （頻出度100以上）
大きさ10以上のクリークは1900個ほど
• データクリーニングをすると、余計に個数が増えてしまう。。。
54000個ほど。中途半端に頂点をつなぐことで、かえって似
たクリークが増えてしまっているようだ
共通部分を取る
• 各クラスタの共通部分を取って、頻度チャートを作る
(1916:0.91) (1180:0.91) (1898:0.73)
(1916:1.00) (1180:0.82) (847:0.73) (1898:0.64)
(2272:1.00) (2382:0.91) (2258:0.91)
(2628:1.00) (2247:1.00) (2789:1.00) (1551:1.00) (2342:0.90)
(2775:0.80) (2469:0.70) (2797:0.60) (3047:0.60) (2704:0.50)
(2841:0.50)
(2247:1.00) (2342:0.90) (2789:0.90) (2628:0.80) (2775:0.80)
(1551:0.80) (2469:0.70) (2214:0.50) (3047:0.50) (2797:0.50)
• 共通性が高いものが多い、パターンも大きめ
• 100% 近いものが多いので、比較的安定しているだろう
• 同一なパターンで頻度チャートがビミョーに違うものが沢山出る
（同一なものを除くと個数が半分ぐらいになる）
まとめ
• 既存のパターンマイニングの定式化に問題定義
• クラスタリングを用いて共通部分を取るという、新しいパラダイム
の提案
• アイテムセットマイニングでの実証
単純な手法の連結＋α （マジョリティ計算）で実現可能
• 計算実験 （テールの長い解分布、頻出アイテムの無視）
今後の課題
• 哲学の浸透
• 他のパターンマイニング問題での応用
• （マルチラベル）クラスタリングへの展開
頻出文字列の発見
頻出文字列
• （巨大な）文字列データから、頻出する文字列を見つけたい
（頻出する＝あちこちに現れる）
• suffix array やradix sort などで、ほぼ線形時間で、多数現れる
部分文字列は見つけられる （閾値以上の回数現れる者の中で
極大なもの、といった設定もOK）
• しかし、アイテムセットのように、「現れる」ことが包含関係で表
されているものに比べると、自由度が低い
（ ＝ きっちりと全体が現れるものしか見つけられない）
• ゲノムなどエラーのあるデータ、ひな形や定型文書のような一
部変化するデータでは、今ひとつ
あいまい性の導入
• エラーや、部分的な変化に対応するには、厳密に一致する文
字列だけでなく、曖昧マッチングの意味であちこちに現れる文字
列を見つける必要がある
• 曖昧性の尺度は、ハミング距離、編集距離、固定回数のギャ
ップ、マルチプルアラインメントのスコアが小さい、など
• しかし、こうすると、短い頻出文字列がたくさん存在してしまう
• いくら高速なアルゴリズムを作っても、これらを全部列挙する
のは無理だし、そもそも見つけてもうれしくない
• 困った困った、ので、違うアプローチを考える
不都合をたっぷり享受
• あいまい頻出文字列問題は、パターンマイニングの負の側面
をたっぷりと享受している
解数の爆発、 解の類似・冗長性、 無意味な解の氾濫
長さ固定 ＆ 多数決
• 長さを固定すれば、今回の枠組みには収まる
文字列の各所から、固定長の文字列を取得
類似する文字列の組を列挙してクラスタリング
全部に共通する構造（マジョリティ）を見つ
ABCDHFG
けて、それをパターンとみなす。
AABDEFH
ABCDEFH
• パターンは多数決で決めれば良い
BBHDEGH
ABHDHFG
• 長さはある程度短くないと、挿入削除が面倒
AAHDEFG
短い類似部分列の発見には sachica を利用 ------AB*DEF[GH]
類似する部分列の発見 (sachica)
問題： 各項目が同じ長さ l の短い文字列（50文字程度）であるデ
ータベースを入力したときに、文字列のペアで異なり数（ハミング
距離）が d 文字以下である組を全て見つけよ
• 長い文字列の比較には、各ポジションを先頭とする長さ l の部
分文字列を全てに対してこの問題を解く。
（似ている部分列はペアを沢山含むところとして見つかる）
ATGCCGCG
GCGTGTAC
GCCTCTAT
TGCGTTTC
TGTAATGA
．．．
• ATGCCGCG と AAGCCGCC
• GCCTCTAT と GCTTCTAA
• TGTAATGA と GGTAATGG
．．．
実験してみると
• クリーク数は意外と小さく、大きさ／個数のヒストグラムも特殊
（ロングテールよりテールが立っている）
• 同じもの、続いているものが沢山ある
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個
ところが
• データが大きくなると、うまく動きません。
ずれたクリークが沢山あるので、列挙が大変。
ネットワークも必然的に密
• クリーク発見が大変 クラスタリングが大変
• もう少し楽なクラスタリング手法を用いよう
☆ 連結成分？ すごく大きなクラスタが見つかってしまう
☆ ニューマンクラスタリング等？
密な部分を固まりと見なすため、すごく大きな
クラスタが出てきそう
簡単に解決
• 安定的ではないが、もっと単純に行ってみよう
次数最大の 部分文字列（似たものが最も沢山ある）
を芯に据えて、そこから左右に伸ばしてみよう
分布の山の真ん中にある頂上をとらえているイメージ
• まず芯と似ている部分列を全て並べ、似ているものが多い間
左右に伸ばす。似ているものが少なくなったら、その時点でやめ
る。
• 伸ばしきったところで、一つパターンが得られる。その部分列と
なってしまったものは除去し、同じように繰り返す。
頻出文字列を核にする
① 最も似ている物が多いもの S を見つける
② S と似ている物を全て集める ( S1,…,Sm)
③ それらをそろえて並べ、文字が共通している部分を抜き出す
次に進む
• 一番良く現れる物について頻出文字列を見つけたら、次に「2番
目に良く現れる文字列」について同じことをする
• ただし、頻出文字列を見つけるときに使った文字列の部分列で、
「見つけた頻出文字列」の一部になっているものは「もう使ったよ
う」という意味を込めて消去
• どんどん候補が消されるので、それほど多くの解は見つからない
• 仕組みが単純で、計算も速い
• それなりに似通っていない解が見つかる
計算結果
• マウス13番染色体 Genic1 での実験結果(150万文字)。長さ30異
なり数2、多数決の閾値は 70%。10回以上現れるもののみ注目
#T#GCAAAGGCTTT#CCACATTGATTACATTCATAAGGTTTCTCTCCAGTATGGGTTCTTTTATGATATCTGA
#TTGCAAAGGCTTTACCACATTGATTACATTCATAAGGTTT#TCTCCAGTATGG#TTCTTTTATGATATCTGA
GAC#A#TGTGACAGGAAAAGGCTTTACCACATTGATTACATTCATAAGGTTTCTCTCCAGTATGGGTTCTTTT
GATTACTGTGA#AGGAAAAGGCTTTACCACATTGATTACATTCATAAGGTTTCTCTCCAGTATGGGTTCTTTT
#TGATATCTGAGACTA#TGTGACAGGAAAAGGCTTT#CCACATTGATTACATTCATAAGGTTTCTCTCCAGTA
ATGA#ATTGGAGAT#A
TGGGTTCTTTTATGATAT#TGAGAC#A
#TCTCTGAA#AAAGAAAT#AAAGAAGATCTCAGAAGATGGAAAGATCTCCCATGCTCAT#GATTGGCAGGATC
AATATAGTAAAAATGGCTATCTTGCCAAAAGCAATCTACAGATTCAATGCAATCCCCATCAAAAT#CCAACT#
AATTCTTCA
• # は多数決が決まらない場所、計算時間は10秒ほど
計算結果 日本語テキスト
• さきほどと同じ日本語テキスト、100万文字、20文字異なり2、次
数（頻出度）20以上
##，０００円までの商品#，０００円までの商品#，０００円までの商品
#，０００円までの商品#，０００円までの商品#
###月日月火水木金土１２３４５６７８９１０１１１２１３１４１５１６１７１
８１９２０２１２２２３２４２５２６２７２８２９３０３１##
###月日月火水木金土１２３４５６７８９１０１１１２１３１４１５１６１７１
８１９２０２１２２２３２４２５２６２７２８２９３０３１##
###Ｃａｔｅｇｏｒｙ：激安ポールスミス腕時計激安通販｜格安最安値
通販へ【ポールスミス 腕時計 ＰＳ#０#
• 解は17個。だいぶ様相が変わりました。よりざっくり取っているの
で、解が減っているのでしょう
計算結果 日本語テキスト
• 異なりを4に、次数（頻出度）を10に変更したら、出てきました。
#組の成立となりました。## #月１#日（土）男性１２名：女性１#名のご参
加で、５組の成立となりました。## ４月７日（土）男性#０名：女性#
##，###円（税別、送料別）Ｐａｕｌ Ｓｍｉｔｈ Ｍｅｎ’ｓ／ポールスミス メンズ
サイズフェイス：Ｈ約４．５ｃｍ×Ｗ約３．#ｃｍ、厚み約#．#ｃｍ（リューズ除
く）ベルト：幅約２．#ｃｍ腕まわり：最大約###
#年０#月２００#年０#月２００６年０#月２００６年０#月２００６年０#月２００６
年０#月２００６年０#月２００#年０#月２００#年１２月２００５年…
• 解は29個。感度が落ちるので、少し低い頻出度、大きな異なり数
で行う必要があるようです。
調子に乗って
• 調子に乗って、さらに大きな問題を解いてみました。
－ 日本語Webテキスト 500MB（2.5億文字程度）
－ 頻出度10 長さ20、異なり2
• 計算時間30分ほどで、頻出文字列が6000個ほど。使用メモリは
600MBほど （入力データの1.3倍ほど）
• ほとんどはなんらかのテンプレートで、完全に一致しているようだ
• ときどき、日付などのゆらぎを吸収したパターンが見つかる
• 異なり数を4にすると2時間。ちょっと大きな異なりも見つける
#####［アウトレットセール］メーカー販売価格#，##０円（税込）ａｃｃ
ａｐｌｕｓ特価#，##０円（税込）#
まとめ
• 類似部分列の組を使って、頻出文字列発見問題を、クラスタリン
グを用いて解く方法を明確化
• 極大クリーク列挙を用いた解法と、次数最大部分列を芯にしたよ
り単純かつ高速な解法の提案
• 計算実験での良好な結果
今後の課題
• 「安定的な、重なりを許すクラスタリング」をベースにした頻出パ
ターン発見の拡大 （系列、グラフ、幾何データ、、、）
• 他のアプローチ（落としどころ）はないですか？
• 数理や応用では、どう解釈するのだろう？？？
© Copyright 2024 ExpyDoc
