データマイニングを味見する
～ 計算から見たデータマイニング ～
宇野 毅明 （国立情報学研究所
,総合研究大学院大学）
2011年6月 東北大学経済学部
簡単に自己紹介
名前： 宇野 毅明
年齢・職種：国立情報学研究所・准教授・41歳
研究分野： アルゴリズム理論とその応用
－ グラフアルゴリズムを中心とした離散アルゴリズム
－ 組合せ最適化とそれにまつわる数理
－ 列挙アルゴリズムと、頻出パターンマイニングへの応用
最近の研究： ゲノム情報学やデータマイングで出てくる巨大なデー
タベースの基礎的（とはいっても非常に時間のかかる）な解析を超
高速で行うアルゴリズムの開発
今日のトピック： パターンマイニング
• 大規模データを入力し、そのデータに良く現れるパターンを全て見
つける問題
• データから、特徴的な部分を「発見」したいときに、その「候補」を見
つける手法として有益
• データマイニング分野の中心的な問題。たくさんの研究あり
• しかし、最近は閉塞感も漂う
本発表
データマイニングの目標とパターンマイニングの最近の成果
パターン
マイニング
データベース
実験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
．
．
．
．
１． データマイニングの見方
（私見です。ご了承下さい）
データマイニングとは
• データマイニングは、データからなんらかの知識を発見する手法
• （目的無く）集められたデータを分析することで、新たな知見を見い
だそう、というのがそもそもの動機
嗜好的な商品の販売戦略
異常事例の特徴解析
顧客分類、データ分類
．．．．
• 分析では、例えば、以下のようなものを見つける
＋ グループ A とグループ B を分けるルール
＋ A ならば B であることが多い、という依存関係
＋ A と B と C は一緒に起ることが多い、という相関関係
「統計」と同じ？
＋ グループ A とグループ B を分けるルール
＋ A ならば B であることが多い、という依存関係
＋ A と B と C は一緒に起ることが多い、という相関関係
昔から統計の分野で盛んに行われてきたこと ？
• 実はそのとおりで、やっていること自体は依然と変わりがない
• しかし、アプローチの仕方、ものの見方の角度が大きく異なる
（分布、計算、発見、検証、…）
巨視的に見ると
① 統計は 検証 、データマイニングは 発見 、が目的
② 統計には モデル（分布） があるが、データマイニングは ない
③ マイニングの出発点は 計算 、統計は（たぶん） 数理モデル
④ マイニングの目標は 局所 、統計は（たぶん） 大域
⑤ データマイニングは 巨大なデータ が合い言葉
• おむつと缶ビールが一緒に売れている
- 統計は、これが「どれくらい普通でないことなのか」を調べる
- データマイニングは、これを「どのように発見するか」を問う
（つまりは、基本的に 計算手法 の学問）
発見と検証
① 統計は 検証 、データマイニングは 発見 が目的
• おむつと缶ビールが一緒に売れている
- 統計は、これが「どれくらい普通でないことなのか」を調べる
- データマイニングは、これを「どのように発見するか」を問う
• 統計では、分布を仮定して、おむつと缶ビールが一緒に売れること
がどれくらい珍しいことか、調べる。
モデルが必要。また、「おむつと缶ビール」という、候補が必要
• データマイニングでは、「よく売れる商品の組合せ」を網羅的に調べ
上げるので、モデルや候補は不要
どれくらい珍しいかわからない。候補は大量に出てくる
それぞれの難しさ
① 統計は 検証 、データマイニングは 発見 が目的
② 統計には モデル（分布） があるが、データマイニングは ない
③マイニングの目標は 局所 、統計は（たぶん） 大域
④ マイニングの出発点（困難性）は 計算 、統計は（たぶん） 数理モ
デル （工学と原理原則、帰納と演繹）
• おむつとビールの例（頻出集合）から、これらの違いはよく見える
• そうなると、統計では、モデルの構築と検証のための数理が技術
的な困難になる
• データマイニングでは、（巨大なデータから）「効率良く解を見つける
こと」が難しさになる
（効率良く見つけられるモデルは何か、という点も）
代表的な問題
• データマイニングの基礎的＆代表的な問題
＋ 決定木、分類（学習）
＋ クラスタリング
＋ 頻出パターン
• どれも、「局所的な特徴」を捕らえることを目標にしている
似たような嗜好を持つ人のグループ
AとBを分ける属性（の組合せ）
多く（それでも一部）の客に共通して購買される商品
．．．．
２． パターンマイニングの近況
（私見です。ご了承下さい）
頻出パターンの列挙
• データベースの中に多く現れるパターンを全て見つける問題を
頻出パターン列挙（あるいは発見、マイニング）問題という
データベース： トランザクション、ツリー、グラフ、多次元ベクトル
パターン： 部分集合、木、パス・サイクル、グラフ、図形
データベース
実験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
．
．
．
パターンマイニングの応用
売上げデータの分析
• 雑誌とおにぎりが良く一緒に売れてます
• 夜 訪れる男性は高めの弁当を買ってます
• さんま と 大根 と すだち は
セット販売したらどうですか？
・・・
画像認識
• みかんとみかんでない画像を分ける
特徴を見つける
項目の自動分類
遺伝子Z： ●○★
遺伝子A： ●△▲
遺伝子Z： ●○★
遺伝子B： ●△▲
・・・ 遺伝子F1： ■□
遺伝子D： ●△▲
遺伝子F2： ■□
・・・
・・・
Webページのトピック分類
• Webページを、リンクやキーワードの
組合せで、トピック毎に分類
全国
ラーメンラーメン
巡り の旅人
基礎的な問題なので、応用に広がりがある
カツカレー
と私 カレーの
作り方
原始的なモチベーション
• もともとのモチベーションは、たぶん、
（大きな）データの局所的な特徴を捉えたい
• 全体的に均質ではなく、多種の要素が混在する巨大なデータの解
析が必要になってきたから
単に全体的な分布を捕らえてしまうと、
局所に際だつ特徴は全て埋もれてしまう
• 局所的な特徴が得られれば、マイノリティーに対応できる
嗜好的な商品の販売戦略
異常事例の特徴解析
顧客分類、データ分類
．．．．
問題の定式化
• 次にモデル作り。局所的な特徴とは何か
共通の要因が知りたいから、共通する構造にしましょう
顕著なものが知りたいので、多くの項目に含まれる構造を
という流れだと思います。
パターンマイニング
（巨大な）データの、閾値以上の項目に含まれる（現れる）、
ある決められたクラスの構造を全て見つける問題
• 以後、apriori、深さ優先など多くの探索手法
ビットマップやFP-tree などデータ構造とアルゴリズム
飽和集合と極大頻出集合など、発展させたモデル が出ます。
問題設定：意外と良い感じです
• 元のモチベーションが「発見」。なので最適化型の問題設定は有用
性が低く、列挙型が適当
○
• 大規模データを対象とするので、単純なデータから単純な評価値
で解を見つけるようにしている
○
• 最小サポートというパラメータが存在し、それで見つける解をコント
ロールできる
○
• 便利にできている
アルゴリズムから見ると
• パターンマイニングは、データの巨大さと解の多さから、重たい計
算を要求するため、高速アルゴリズムは必須要因
• アルゴリズムから見ると、パターンマイニングは「列挙問題」
• 列挙の中でも簡単な問題になっているため、楽に設計ができる
単調性、閾値（最小サポート）による制約、単純なアイテム集合
• もし「情報量最大のものk個」なら、これほど流行らなかっただろう
（アルゴリズムとモデルの間の、いい落としどころを見つけている）
特徴の定義
が複雑
解析モデル
パターン
マイニング
指数的に時
間がかかる
列挙
アルゴリズム
既存研究の歴史
• いい落としどころ（新しい研究分野）ができたので、研究は発展
多種の構造データへの対応、頻度の定義、パターンの定義（極大）
探索アルゴリズム、データ構造．．．など
• が、今日はアルゴリズムの話を深くはしません （ちょっと紹介）
• 歴史的な話、最近の問題意識などを、紹介したいと思います。
（新しいモデルも少し）
３． マイニングアルゴリズム鳥瞰
頻出集合の単調性
• 工夫をするためには、何か問題の特徴をつ
かまなくてはいけない
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
φ
マイニングの技術の歴史
• いくつかのブレイクスルーがある
第１世代
apriori （幅優先）： ディスク上のデータ用
111…1
頻出
第２世代
深さ優先探索： データをメモリに保持
000…0
第３世代
データベースの圧縮： trie(FP-tree) などで再帰的に圧縮
第４世代？
基数ソート、振り分け、および ppc拡張による飽和集合列挙
第１世代： apriori
• 各レベルごとに頻出集合の候補（１つ下のレベルの頻出集合に１つアイ
テムを加えたもの）を生成し、その頻出度を計算
Comp_CK (K={v1,…,vk})
1. S0={φ}, k := 0
2. while Sk が空でない
3. for each トランザクション Ti
4. for each P∈Sk,P⊆Ti
P の頻出度＋１
5. 頻出でない P を Sk から除去
6. for each P∈Sk
7.
for each アイテム e
8.
P+e を Sk+1 に挿入
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
φ
• P+e の部分集合で、Skに入っていないものがあれば頻出でない
• １レベルにつき、ディスクのスキャンが一回ですむ
• メモリ使用量と検索の手間がボトルネック
第２世代： 深さ優先（バックトラック）
• 空集合から出発し、頻出集合である限り再帰的にアイテムを追加
Backtrack (P, Occ(P) )
1. output P
2. for each e > Pの末尾
（P の最大添え字のアイテム）
ダウンプロジェクト
3. Occ(P∪e) = Occ(P) ∩ Occ(e)
4. if |Occ(P∪e)| ≧ σ then （頻出なら再帰）
call Backtrack (P∪e, Occ(P∪e) )
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,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
φ
含むものしか含まない
• アイテム集合 X の出現集合を T とする
• X＋e の出現は X を含む（＝ X の出現）
X＋e を含むトランザクションを見つけるとき
には、 T のトランザクションしか見なくてよい
• T のトランザクションで e を含むものを集めると
X＋e の出現集合が得られる
Occ(X＋e) = Occ(X) ∩ Occ(e)
配列リストの形で持てば、Occ(X) と Occ(e) の両方をスキャンす
るだけ、つまり O( |Occ(X)| + |Occ(e)|) 時間
• 出現集合を更新すれば、データ全体を見なくて良い
計算時間はだいぶ短くなる
第３世代： 再帰的データ圧縮（FP-tree）
• データベースの縮約により、再帰の深いレベルでの高速化する
（１） 前回追加したアイテムより小さいアイテムは消す
（２） 現在の出現集合からできるデータベースの中で、頻出になって
いないアイテムは消去する
（再帰呼び出しの中で加えられることが無いから）
（３） まったく同一のトランザクションは、１つにまとめる
• 実データだと、下のほうのレベルではだいたい大きさが定数になる
• FP-tree（trie）を使うと、共有する prefix
も圧縮されるが、オーバーヘッドも大きい
１
１
２
２
５
６
４
７
４
３
２
４
４
３
１
σが小さいときと速度の大きな差はない
３
４
４
５
６
７
６
７
６
７
木構造を用いた圧縮 （trie, prefix tree）
• 各トランザクションを文字列とみなすと、2分木の形で格納でき、メ
モリを節約できる （共有する prefix の分だけ小さくなる）
振り分けと併用できる。スキャンの時間も、それだけ短くなる
• BDD（ZDD）も利用可能
A: 1,2,5,6,7,9
B: 2,3,4,5
C: 1,2,7,8,9
D: 1,7,9
E: 2,3,7,9
F: 2,7,9
*
1
2
1
2
5
6
7
7
8
9
7
9
3
4
5
7
9
7
9
D
F
B
E
9
C
A
末広がり性
• 再帰の末端以外はさほど高速化されていないのに、なぜ実際
には大幅に高速化されるのか？
• バックトラックは、各反復で複数の再帰呼び出しをする
計算木は、下に行くほど大きくなる
反復の平均計算時間を支配するのは一番下の数レベル
計算時間長
・・・
計算時間短
ダウンプロジェクトや圧縮による末端の高速化が
全体を高速化している
第４(?)世代： 振り分け・基数ソート・ppc拡張
• trie を使ったデータの圧縮には nlogn の時間がかかる
基数ソートで、（ハッシュでの）オーバーヘッドなしに線形時間
• 疎な行列の転置を使って、追加するアイテムの出現を、いっぺん
に線形時間で求める （振り分け）
• ppc 拡張を用いて飽和集合を無駄なく列挙
１
１
３
２
２
６
４
７
４
３
２
５
４
３
１
４
４
４
５
６
７
６
７
６
７
振り分けによる高速化
• 各アイテムに空のバケツを用意する
• X の各出現 T に対して、以下を行う
－ T に含まれるアイテム e に対して、 e のバケツにT を入れる
この操作が終わった後は、各アイテムe
のバケツの中身は X＋e の出現集合になる
振り分け (X)
1. for each X の各出現 T
2. for each e∈T, e > Xの末尾
eのバケツに T を挿入
A: 1,2,5,6,7,9
B: 2,3,4,5
C: 1,2,7,8,9
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
１反復の計算時間のイメージ
• 普通に頻出度の計算をすると
各 P＋e に対してデータを
一回スキャンする
• ダウンプロジェクトは
Occ(P) と Occ({e}) をスキャンする
Occ(P) を n-i 回スキャンし、
データベースの i より大きな
アイテムをスキャンする
n個
＋
(n-i)個
i
• 振り分けは出現Occ(P) 中のトランザ
クションの i より大きい部分をスキャンする
Occ(P)
i
技術のまとめ
第１世代 apriori （幅優先）
ディスク上のデータ用のスキャン回数を最小化
データがメモリに乗らないとき速い
第２世代 深さ優先（バックトラック）
出現の集合を保持するところがミソ
データをメモリに入ると速い
第３世代 再帰的データ圧縮(FP-tree)
末端の計算の高速化が全体を高速化
第４世代 基数ソート、振り分け、 ppc拡張
検索技術からアルゴリズム技術へ
111…1
頻出
000…0
実データ（超疎)
BMS-WebView2
飽和：LCM
頻出：LCM
極大：afopt
実データ（疎）
kosarak
飽和：LCM
頻出：nonodrfp＆LCM
極大： LCM
賞状と賞品
賞品は {ビール, 紙おむつ}
“Most Frequent Itemset” だそうです
４．新しい問題設定とその解法
最近目につく問題点
• 最近、パターンマイニングの研究は、たこつぼにはまっている気が
します。やり尽くされているので、新規の研究は難しいと言うことです
（計算が高速化できるようになってしまったので、大きな課題がな
い）
いいモデルがなかなか出てこない。いい技術も
出てこない。既存のものを大きく超えることは難しい
モデルの単純さゆえに直接的に利用ができない。
副次的に利用するには、道具が複雑すぎる
有益なものを見つけようとすると、解が沢山出てくる。
大量の似た解を処理できない
• 昔はきっと、「これができれば」という希望があったと思います
また距離が開いてしまった
• パターンマイニングは、いい落としどころだったはずだが、いつの
まにかアルゴリズムのほうに入ってしまっている
（最近の研究はモデルでなく「アルゴリズムの拡張」になっている）
• いつの間にか、また「モデルとアルゴリズムの距離」が開いた！
• ということは、また新しい「落としどころ」が必要
新たな落としどころを、計算とモデルの両面から考える
特徴の定義
が複雑
解析モデル
パターン
マイニング
指数的に時
間がかかる
パターン
マイニング 列挙アル
列挙
ゴリズム
アルゴリズム
もう一度モチベーションから
• 立ち戻ってみると、もともと「局所的な」「特徴」が見つけたかったの
だが、「大量の局所」と「大量の特徴」が見つかってしまっている。
• 少しの（代表的な）局所の、代表的な特徴がわかれば十分だろう
• しかし、代表のみを残すために、パターンに制約を付ける、というア
プローチは今ひとつうまくいっていない。
多くの面白い局所のパターンを切ってしまう可能性があるため
• 飽和集合のように、完全性
を保証しようとすると、少し
しか減らせない
（臆病すぎ）
データ
パターンへの制約は妥当か？
• 「局所」とは、パターンマイニングの言葉で言えば、
「パターンが出現する項目の集合」
• 「出現集合が他と違うもの」を残したくて、「出現集合が似ているも
の」はまとめたい
パターンに対する制約ではない!!!
パターンに対する制約でうまくゆく訳がない
• もっと「出現集合」に
注目して計算すべき
代表は、出現集合に制約
を与えて定義すべき
データ
複雑なモデル・手法は、、、
• こういう方向性で問題を考えると、ついつい複雑なモデルを複雑
な手法を使って解く、というパターンになる。
あるいは、ある程度強い仮定を置いて問題を解くことになる
（アルゴリズム的な意味です）
• 数理的にはいい結果が出せるかもしれないが、利用者にとって
は親切でない
• だんだん、何をしているのか分からなくなってくる、、、
（最適化の分野、アルゴリズムの分野などで、こういうトピックをいく
つか見てきました。）
「見つけ方」の逆転
• 頻出パターンは、「局所的」な「特徴」であるが、その見つけ方は、
まず特徴候補を列挙して、どの局所に現れるかを計算している。
定義の流れと逆なので、よく考えると気持ち悪い
• まず、「共通な要因を持つ項目の集合」を見つけてから、
「それらに共通する特徴」を見つけるようにできるといい。
定義の流れに合っているので、自然な感じ
「無駄なパターンを見つけなく」なってくれるとうれしい
データ
データ
もう、あるんじゃないですか？
• この方法、とどのつまりは類似性に基づいてクラスタリングして、共
通するパターンを見つけよう、ということ。
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
．．．
簡単に解決
• 安定的ではないが、単純に行ってみる
次数最大の 部分文字列（似たものが最も沢山ある）
を芯に据えて、そこから左右に伸ばしてみよう
分布の山の真ん中にある頂上をとらえているイメージ
• まず芯と似ている部分列を全て並べ、似ているものが多い間
左右に伸ばす。似ているものが少なくなったら、その時点でやめ
る。
• 伸ばしきったところで、一つパターンが得られる。その部分列と
なってしまったものは除去し、同じように繰り返す。
頻出文字列を核にする
① 最も似ている物が多いもの 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
