JSAI 2011 全国大会 in 盛岡
2G3 データマイニング「頻出パターン」
06月02日(Thu) 14:45～17:00 G会場

モジュラリティの差異に基づくコントラスト法（Patterns with Emerging Modularity
and their Detection）

北海道大学 大学院情報科学研究科
鶴田 哲章 (現在 ＮＴＴコムウエァ) 、 原口 誠

背景： マイニング分野における変化の抽出
2つ（以上）のDBを比較：
パターンの頻度（アイテムの共起）の違いを検出 Emerging Pattern(G.Dong
Pattern(G Dong et al ‘99)
99)
 Contrast Set(S.D.Bay et al ’01, P.K.Novak et al ‘09)
 lift (p(A|B)/p(A) ） の差異（比率） (Taniguchi et al ’06 ) 相関マイニング (Brin ‘98)： 独立な場合との差異 （統計量、情報量）
相関の差異を検出 （Li et al ‘11）
 今回： 必然性(in Newman clustering) の差異
単なる共起頻度・相関ではなく、稀なものの結合を重要視
抽出目標 base と target を比較し、必然性が増加するもの
抽出目標：を比較し 必然性が増加するもの
1

共起の必然性の差が大きくなる場合
必然性大 －必然性小低次数の項の共起

共起しにくい項の共起
比較的に小規模のクラスタ抽出
ボランティア代表者の被災者の生活の調査

高次数の項の低い共起共起しやすい項が共起していない
す 項
or 例え共起していても有り難がらない家,代表,生活,住宅

話題が特定化され、次数が低くなる?

様々な話題で使用され、次数が高いモデュラリティ行列
ｍ 回、「ランダムに」辺を生成。ｍ：辺の総数
ただし、ランダムグラフ s.t.
頂点周りの辺期待値の総和 ＝ 現実の次数（次数保存性＋独立性） k_i k_j /2m が導出

B = A − P = ( Aij − Pij ) ij
A = D t D, Pij = ki k j / 2m
Ｄ： 文書－項（ブール値）、Ａ：共起頻度
低次数の共起： ランダム性から遠くなり必然。regard
高次数の共起： 当たり前。予想できるから disregard2Newmanモジュラリティの利用に向けて
 Newman(クラスタリング)の場合
 目的は全ネットワークのグラフ分割
 分割を評価する関数Qを定め、モヂュラリティ行列分割を評価する関数Qを定め モヂュラリティ行列 Ｂ のスペクトル分解に基づく、近似的最適クラスタリングの計算
 本研究
 目的はクラスタリングではなく、モジュラリティが増加するパターンをマイニングする モジュラリティの差異を計算
ジ差異を計算 単一の準最適なパターンではなく、可能性のあるパターンを枚挙

Newmanによる分割の評価(‘06)
S = (s1 L s c )各グループの評価

sT Bss = ∑ Bij si s j = ∑ Bij
si = s j =1i, j

グラフ分割の評価(cQ = ∑ sTk Bss k = Tr S T BSSk =1x Bx = λ1 z1 + .. + λ p z p − β1 z p +1 − .. − β n − p z n2T)

222sT Bs = λ1 (u11 + u 21 ) 2 + .. − β1 (u13 + u 23 ) 2 − ...
λ1 λ2 − β1 − β 2⎛1⎞u14⎜ ⎟ v1 u11 u12 u13s = ⎜1⎟ v
u 21 u22 u23u242⎜0⎟⎝ ⎠ v
u31 u32 u33
u34
32X k − Yk2

固有値の平方根で補正したベクトルの２乗ノルムの和. 正と負のベクトル

3２つのDBにおける「モジュラリティの差異」
モジュラリティの差ki′k ′j ⎞ ⎛kk ⎞⎛⎟⎟ − ⎜⎜ Aij − i j ⎟⎟Bij = ⎜⎜ Aij′ −2 m′ ⎠ ⎝2m ⎠⎝⎛1⎞⎜ ⎟s = ⎜1⎟⎜0⎟⎝ ⎠v1v2v3ｓ に対し、

λ1
λ1 u11
λ1 u 21
λ1 u31

λ2
λ2 u12
λ2 u22
λ2 u32β1− β1 u13− β1 u23− β1 u33β2− β 2 u14
− β 2 u24
− β 2 u34++XY

パターン評価のためにグループ評価法を借用
2

グループの評価 = X k − Yk2

正の成分での大きさ

負の成分での大きさ

 直感的意味
正の成分による空間

負の成分による空間
このベクトルの大きさの総和

このベクトルの大きさの総和
正： 方向性が集中しているほどベター
負： 方向性が「ばらけている」ほどベター

余弦類似度. 球面
クラスタの分散4

予備実験用ストラテジーPattern 生成と評価：
縦型、set enumeration tree
|正のベクトル|^2 － |負のベクトル|^2
アイテムの追加に対し、非単調

制約： 負の成分に対し、中心ベクトルとの余弦類似度の総和が一定の値以下アイテムの追加に対し安全でない制約： 要改良
幅限定探索： 制約を満たす候補アイテムで、正の 成分評価がトップＮ個に絞り込む
制約を満たすものの中でトップＮ個を探索する、分枝限定トップＮ枚挙とは異なる。
本実験では 動的順序付けのもとで、最適トップＮ解のみを枚挙。

実験 用いたデータについて
 毎日新聞の「神戸」を含む1994年の文書集合(DB)と1995年の文書集合(DB’)を用いて実験
 DBの文書数：2337
 DB’の文書数：9324
 DB・DB’に共通して出現する名詞（アイテム）

5成分の選択について
0.016

固有値の絶対値

0.014

0.012

0.01

λ1 x12 + λ2 x2 2 + ... − β1 y12 − β 2 y2 2 − ...

0.008

0.006

殆どが殆どがゼロ近傍なので、それ以外近傍なので、それ以外の成分を現在は使用

0.004

0.002

1
10
1928
3746
55
64
73
82
91
100
109
118
127
136
145
154
163
172
181
190
199
208
217
226
235
244
253
262
271
280
289
298
307
316
325
334
343

0

計算時間
2500

2000

N = 10
実行時間(秒)

1500

1000

500

0
1683

2467

3715

5349

9549

アイテム数

6

品質
得られたパターン

モジュラリティの差

支持度の差

ＪＲ,次,地震0.0002465

0.0068673

伊丹,南,明石,西宮,須磨,中央0.0002072

0.0002178

伊丹,南,明石,宝塚,尼崎

0.0001887

0.001397556

決定,発生,被害0.0000590

0.0006479

地震による被害と、その地域の再開発計画の決定

家,代表,生活,住宅

0.0000535

0.0009686

ボランティア代表者の被災者の生
活の調査

滋賀,明石,宝塚

0.0000448

0.0037571

各種交通機関の復旧

反映していた(DB'での)文書の概要
地震による被害を受けた、各種交通機関の復旧システム,全国,被害0.0000439

0.0030063

地震による被害によって表面化した、行政システムの問題

南,明石,宝塚
南明石 宝塚
伊丹,南,明石

00.0000436
00004360.0000430

00.0022567
00225670.001507

各種交通機関の復旧
各種交通機関の復旧センター,会場,中央0.0000422

0.0037571

チャリティーコンサートの会場案内

必然性(modularity)の差が大きいもの

差は小さすぎて emerging
pattern としては実質的に抽出不能

今後の課題
 探索の完全性の観点から
 負の成分ベクトルに対する枝刈りの安全性は ＮＧ

アイテム追加により分散は単調に増加するとは限らない。
 他の安全性を保証する制約に替える as 分散が一定以内の部分を含まない、等 正の成分ベクトル： 論文では枝の本数を限定（高々Ｎ個）動的順序で、分枝限定枝刈りＯＫ （concept vector を基準にした、）
 成分選択指針:

ゼロ近傍が多数でないとき
 今回： １部グラフモデュラリティ。２部グラフ版がより正確.

7