冗長性が低く重要度の高いパターンの抽出(1)

　パターンマイニングはデータマイニングを代表する手法の一つで，特にアソシエーションルールを適用した「ビールとおむつ」などの例が有名です．
　最近は，Rなどのデータ分析ツールでもAprioriやEclat(頻出パターンマイニング), CSPADE(系列パターンマイニング)等のアルゴリズムを実行するライブラリが提供されており，パターンマイニングを実行することの障壁は比較的低くなっています．

　パターンマイニングでは，一般的に膨大な数のパターンが抽出されます．この事象はアイテムの組み合わせや順列の数が膨大になることに起因しており，少量のトランザクションから大量のパターンが抽出されることも決して珍しくありません*1．このような背景の下，パターンマイニングで抽出されたパターンから重要なパターンを抽出することは，大きな技術的課題の一つだと言えるでしょう．

抽出したパターンは膨大な数に

　以上で説明したことを実感するために，パターンマイニングを実行してみましょう．

　FIMIレポジトリで公開されているretailデータセットに対して適用します．まず，データセットを取得します．

$ wget http://fimi.ua.ac.be/data/retail.dat  # データの取得
$ wc -l retail.dat  # データは88,162レコード
88162 retail.dat
$ head retail.dat  # データの先頭
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 
30 31 32 
33 34 35 
36 37 38 39 40 41 42 43 44 45 46 
38 39 47 48 
38 39 48 49 50 51 52 53 54 55 56 57 58 
32 41 59 60 61 62 
3 39 48 
63 64 65 66 67 68 
32 69

　FP-growth アルゴリズムにより頻出パターンを抽出します．ここでは，Christian Borgelt先生が公開されているパターンマイニングのアルゴリズムの実行ファイルの中からFP-Growthを選んで使用します．サポートを0.1%(89レコード以上)と設定して実行しましょう．

$ # 最小アイテム数2, サポート0.001(0.1%), アイテム間のセパレータ","(-k,), アイテムセットの出現指標はサポート
$ ./fpgrowth -m2 -s0.1 -k, -v" %s" retail.dat fpgrowth_retail.dat
$ wc -l fpgrowth_retail.dat  # サポート0.1%以上のアイテムセットは5,472個 
5472 fpgrowth_retail.dat
$ head fpgrowth_retail.dat  # FP-growthを用いているためアイテムセットはサポート順に並ぶとは限らない
48,39 0.330551
38,39 0.117341
38,48,39 0.0692135
38,48 0.0901068
32,39 0.095903
32,48,39 0.0612736
32,48 0.0911277
32,38,39 0.0208707
32,38,48,39 0.0140196
32,38,48 0.0186702
$ sort -k2 -r fpgrowth_retail.dat | head  # サポートの降順にアイテムセットをソート
48,39 0.330551
41,39 0.129466
38,39 0.117341
41,48 0.102289
32,39 0.095903
32,48 0.0911277
38,48 0.0901068
41,48,39 0.0835507
38,48,39 0.0692135
32,48,39 0.0612736

大量のパターンが抽出されてしまいました・・・

冗長性が低く重要度が高いパターンを抽出する

　さて，このように膨大な数のパターンが抽出されるパターンマイニングの結果から，なるべく少なく情報量が多いパターンを列挙するためにはどうすれば良いでしょうか．このような問題意識から，いくつかの研究が行われています．この中から，今回は，冗長性が低く重要度が高いパターンを抽出することを目指して，以下のKDD'06の論文を取り上げます．

D.Xin, H.Cheng, X.Yan, J.Han, Extracting redundancy-aware top-k patterns, KDD'06.

　この論文で紹介されている手法は，最初から一般論だと少し分かりづらい面もあるかもしれないので，次の小さなデータセットを例にとって説明しましょう．

test.dat

a b c
a d e
b c d
a b c d
b c
a b d
d e
a b c d
c d e
a b c

　このデータセットに対して，上記と同様の手続きによってパターンマイニングを実行すると，以下の結果を得ます．行頭の連番は以後の説明のために付与したものです．

1. c,b 0.6
2. d,c 0.4
3. d,b,c 0.3
4. d,b 0.4
5. a,b 0.5
6. a,d,b 0.3
7. a,d 0.4
8. a,c,b 0.4
9. a,c 0.4
10. e,d 0.3

この中から，5個だけパターンを選びましょう．単純にサポートが大きいパターンの順に選ぶと，以下の7つが候補となるでしょう．

1. c,b 0.6
5. a,b 0.5
2. d,c 0.4
4. d,b 0.4
7. a,d 0.4
8. a,c,b 0.4
9. a,c 0.4

末尾にサポート0.4のパターンが5つ並んでおり，この方法では選び出す5個のパターンを決定できません．

少し見方を変えて，各パターンが元々のトランザクションデータのどのレコードに出現していたかについて調べてみましょう．

1. c,b 0.6  1, 3, 4, 5, 8, 10
2. d,c 0.4  3, 4, 8, 9
3. d,b,c 0.3  3, 4, 8
4. d,b 0.4  3, 4, 6, 8
5. a,b 0.5  1, 4, 6, 8, 10
6. a,d,b 0.3  4, 6, 8
7. a,d 0.4  2, 4, 6, 8
8. a,c,b 0.4  1, 4, 8, 10
9. a,c 0.4  1, 4, 8, 10
10. e,d 0.3  2, 7, 9

3フィールド目が出現したレコード番号のリストです．これを見ると，例えば

「8. a,c,b」と「9. a,c」はどちらも番号1, 4, 8, 10のレコードに出現している．
サポートが最も高い「1. c,b」と2番目の「5. a,b」は，番号1, 4, 8, 10のレコードで共通に出現している．

といったことが分かります．

　1番目の考察から，「9. a,c」が出現するときは，さらにbも追加された「8. a,c,b」が必ず出現していることが分かります．また，2番目の考察から，サポートがトップ2のパターンも，異なるトランザクションで独立に現れるのではなく，トランザクションの共通部分があることが分かります．

　このように，2つのパターンの間でのトランザクションの重なりがあることが，パターンが独立ではなく，お互いに何かしらの関係を持つことになります．この関係は，今回取り上げた論文では「冗長性」(redundancy)という概念により定量化されます．
　冗長性はどのように測れば良いでしょうか．論文では，

冗長性 = (2つのパターン間の距離) × (2つのパターンの重要性の最小値)

として冗長性を定義しています．ここで，2つのパターン間の距離の取り方はいろいろとありますが，代表的なものとして，Jaccard係数

$J=J(p, q)= 1 - \frac{||T(p) \cap T(q)||}{||T(p) \cup T(q)||},$

が挙げられます．この冗長性の定義に従うと，例えば，

「1. c.b」と「5. a,b」は，レコード1, 3, 4, 5, 6, 8, 10でどちらか一方が現れ，レコード1, 4, 8, 10で共通に現れている．⇒ 冗長性は，距離 $\frac{4}{7} \times$ 最小サポート $\min(0.6, 0.5) = \frac{2}{7}$ .
「8. a,c,b」と「9. a,c」は，レコード1, 4, 8, 10で共通に現れている．⇒ 冗長性は，距離 $\frac{4}{4} \times$ 最小サポート $\min(0.4, 0.4) = 0.4$ .

となります．

　さて，サポート等のパターン間の重要性が与えられ，冗長性が定義できたので，選び出したパターンの集合に対して次のように評価指標を定義できるでしょう．

パターンの集合の評価指標 = 各パターンの重要性の和 - パターン間の冗長性の和

10個のパターンから5個のパターンを選ぶ $_{10}\mathrm{C}_{5}$ 通りの集合から，重要度が高く，冗長性の低い集合を選択できそうです．しかし，このように全ての集合を列挙して，重要度と冗長性を考慮して集合を評価することはNP-hardな問題です．そこで，論文では貪欲的にパターンを選択していく方法が提案されています．

Redundancy-aware Top-k Patternの定式化

以上で説明した方法を定式化すると，次のようになります．

パターンの集合の評価
$k$ 個のパターンの集合 ${\cal P}^{k} = \{p_{1}, \, \dots, \, p_{k}\}$ の有益さを評価してみましょう．前提として，各パターンの重要度 $S(p)$ が求められているとします．重要度の指標として，サポート，コンフィデンス，リフトなどが用いられます．
各パターンが独立の場合は，評価関数 $G$ は各パターンの重要度の和，すなわち，

$G_{ind}({\cal P}^{k}) \, := \sum_{i=1}^{k} \, S(p_{i}).$

で定義できるでしょう．
しかし，一般的にはパターン間には冗長性があるため，評価関数は

$G_{ind}({\cal P}^{k}) \, := \sum_{i=1}^{k} \, S(p_{i}) - L({\cal P}^{k}),$

となります．ここで， $L$ はパターンの集合 ${\cal P}^{k}$ に対して定まる冗長性です．

MASとMMS
上記のパターン集合に対する評価の定式化においては，冗長性 $L$ をどのように定義するかがポイントになるます．本論文では，MAS(Maximal Average Significance, 極大平均重要度)とMMS(Maximal Marginal Significance)の2つが提案されています．以下ではパターンの個数 $k$ は外から指定するものとします．

MAS(Maximal Average Significance)
以下で定義する指標 $G_{as}$ が最大となる $k$ 個のパターンの集合 ${\cal P}^{k}$ を抽出する．
$G_{as}({\cal P}^{k}) = \sum_{i=1}^{k} \, S(p_{i}) - \frac{1}{k-1}\sum_{i=1}^{k} \sum_{j=1}^{i-1} \, R(p_{i}, \, p_{j}).$
ここで， $R(p_{i}, p_{j})$ はパターン $p_{i}$ と $p_{j}$ の間の冗長性であり，パターン間の距離 $D(p_{i}, \, p_{j})$ を用いて次式で定義される．
$R(p_{i}, p_{j}) := \left(1 - D(p_{i}, \, p_{j})\right) \times \min\left(S(p_{i}), \, S(p_{j})\right).$
MMS(Maximal Marginal Significance)
以下で定義する指標 $G_{ms}$ が最大となる $k$ 個のパターンの集合 ${\cal P}^{k}$ を抽出する．
$G_{ms}({\cal P}^{k}) = \sum_{i=1}^{k} \, S(p_{i}) - w(MST_{{\cal P}}).$

MASもMMSも最適解を求めることはNP-hardであるため，逐次的に近似解を求めていきます． $i$ 個目までのパターンが抽出されたとき，パターン $p \in {\cal P}/{\cal P}^{i}$ に対して，それまでに抽出されたパターンとの冗長性を求めることにより $p$ を採用することによるゲイン $g(p)$ を評価します．すなわち，ゲイン $g(p)$ を次式

$g(p) = \left\{\begin{array} {ll} S(p) - \frac{1}{|{\cal P}^{i}|} \sum_{q \in {\cal P}^{i}} \, R(p, \, q), & (MAS) \\ S(p) - \max_{q \in {\cal P}^{i}} R(p, \, q), & (MMS) \end{array} \right.$

で定義します．

上式を用いて $k$ 個のパターンを抽出すると計算量は $O(k^{2}n)$ となります．しかし， $i$ 回目までに抽出されなかったパターンに対しては， $i$ 回目に算出したゲインを用いてインクリメンタルに $i+1$ 回目のゲインを計算することにより，計算量を $O(kn)$ に削減できます．すなわち，パターン $p$ に対して以下のように $i$ 回目のゲインの結果 $g^{i}(p)$ を用いて $i+1$ 回目のゲイン $g^{i+1}(p)$ を算出します．

$g^{(i+1)}(p) = \left\{\begin{array} {ll} S(p) - \frac{1}{i} \left\{(i-1)\left(S(p) - g^{i}(p)\right) + R(p, \, p_{i}) \right\}, & (MAS) \\ S(p) - \max\left{S(p) - g^{i}(p), \, R(p, \, p_{i}) \right}, & (MMS) \end{array} \right.$

実装

C++を用いて実装しました．ソースコードはGithubに上げました．

適用例

上記のretailデータセットの頻出パターンに対して，Top-Kのパターンを抽出してみましょう．

入力ファイル: fpgrowth_retail.dat
トランザクションデータファイル: retail.dat
抽出するパターン数: 10
出力ファイル: redtopk_retail.dat

$ ./redtopk -i fpgrowth_retail.dat -t retail.dat -k 10 -o redtopk_retail.dat

以下の結果が得られます．

$ sort -k2 -r redtopk_retail.dat
{39,48} 0.330551
{39,41} 0.129466
{38,39} 0.117341
{41,48} 0.102289
{32,39} 0.095903
{32,48} 0.0911277
{38,48} 0.0901068
{39,41,48} 0.0835507
{38,39,48} 0.0692135
{32,39,48} 0.0612736