« 読了: Goethals & Zaki (2004) 頻出アイテムセット・マイニングの世界最強アルゴリズムを決める選手権2003 | メイン | 読了: Parkin (2004) セックスと食べ物とアーネスト・ディヒター »
2013年6月18日 (火)
Lenca, P., Myer, P., Vaillant, B., Lallich, S. (2008) On selecting interestingness measures for association rules: User oriented description and multiple criteria decision aid. European Journal of Operational Research, 184(2), 610–626.
アソシエーション分析で、発見したルールの興味深さを評価するための指標がいっぱい提案されているので、比較しましょう。という話が載っている論文。ほんとはLallich, Teytaud, Prudhomme(2007)の同趣旨の論文を読み始めたんだけど、前半で話についていけなくなってあきらめた(後半ではなんかFDRみたいな統計的手法を提案しているのに。残念)。なんだか腹が立つので、もうすこしユーザ向けに書かれたのを探して読んだ次第。よく見たら、著者名がだぶっている。
ええと、背景としては... アソシエーション分析では巨大な出現行列からルールを抽出するが、有名な Aprioriアルゴリズムでは、
- まず閾値以上のsupport(同時出現割合) を持つアイテムセットを抽出し、
- そのアイテムセットをAとBに分け、閾値以上のconfidence (Aの出現割合に対するA&Bの同時出現割合の比) を持つ規則 if A then B を生成する。
このやりかただと規則がたくさん生成されちゃうので、なんらかのかたちでのフィルタリングが必要になる。主観的にやる方法もあるが(Silberschantz & Tuzhilin, 1995, Chap.; Liu, Hsu, Chen, 1997, Conf.; Liu, Hsu, Chen, Ma, 2007, IEEE-IS を参照せよとのこと)、ここではデータに基づきルールの興味深さを評価する指標について考える。
検討する指標は以下の通り。以下、A=1 かつ B=1 の頻度をNab, 割合を Pabと書く。A=1 かつ B=0 の頻度と割合は Nab', Pab' と書く。A=1 の頻度と割合は単に Na, Pa と書く。Aの下でのBの割合 Pab/Pa を Pb/a と略記する。各指標についてのコメントにはLallich, Teytaud, Prudhomme(2007)のものも交じっている。
まず、よく使うやつ:
- support: Pab. 独立な時にPa Pb。
- confidence: Pb/a. 独立な時にPb。
以下、confidenceを変換した指標。
- Lift: (Pb/a) / Pb = Pab / (Pa Pb). confidenceのPbに対する比。A→Bの事例数(Pab)が、AとBが独立である場合に期待される事例数(Pa Pb)に比べて何倍あるか、とも解釈できる。独立な時に1。
- centered confidence: Pb/a - Pb. confidenceとPbとの差。独立な時に0。
- Piatetshky-Shapiro: n Pa (Pb/a - Pb) = n (Pab - Pa Pb). centered confidenceをさらに(n Pa)倍。対称的。独立な時に0。
- Zhang: (Pab - Pa Pb) / Max(Pab Pb', Pb Pab'). こうなると直感的にわかる意味はない。Piatetsky-Shapiroを、下限が-1, 上限が+1となるよう調整した指標。独立な時に0。
- Loevinger: (Pb/a - Pb) / Pb'. centered confidenceの、Pb'に対する比。独立なときに0。
- ピアソンの相関係数: (Pab - Pa Pb) / sqrt( Pa Pa' Pb Pb'). Piatetsky-Shapiroの変換だといえる。対称的。独立なときに0。
- カッパ係数: 2 (Pab - Pa Pb)/(Pa + Pb ^ 2 Pa Pb). よくみると、これもPiatetsky-Shapiroみたいなものだ。独立なときに0。
- implication index: sqrt(n) (Pab' - Pa Pb') / sqrt(Pa Pb'). これはA→Bの反事例に注目していて、AとB'についてのPiatetsky-Shapiroを変換した指標になっている。独立な時に0。A→Bの興味深さの指標 として使う際は-1を掛ける。
- least contradiction: (Pab - Pab') / Pb. これもconfidence系の指標である由。独立な時にはNa(Nb-Nb')/(N Nb)となる由。なんでこんなん提案したのかな...
- Sebag and Schoenauer: Pab / Pab'. AのもとでのBのオッズ。confidenceの単調増加変換になっている。独立な時は Nb/Nb' となる。
- examples and counter-examples rate: 1 - (Pab' / Pab). AのもとでのB'のオッズを1から引いた値。confidenceの単調増加変換になっている。独立な時は(Nb-Nb')/Nb となる。
- information gain: log (Pab / (Pa Pb)). Liftの対数。独立なときは0になる。
- Laplace: (Pb/a + (1/(n Pa)) / (1 + (2/(n Pa)). これもconfidenceの系列で、nを考慮にいれている由。独立な時は...ややこしいので省略。
その他の指標:
- ベイズ・ファクター: (Pab Pb')/(Pab' Pb) = {(Pb/a) / (Pb'/a)}/(Pb / Pb') = (Pa/b) / (Pa/b'). AのもとでのBのオッズの、全体におけるBのオッズに対する比。独立なときに1。
- conviction: (Pa Pb') / Pab'. A→Bの反事例数が、AとBが独立である場合に期待される事例数(Pa Pb')に比べて何分の一か。独立な時に1。
- intensity of implication: Prob[ N(0,1) >= (implication index) ]. 独立な時に0.5。
- Probabilistc discriminant index: Prob[ N(0,1) > (implication index)^{CR/\Beta} ]. ヤヤコシイので省略。
- truncated entropic intensity of implication: ものすごくヤヤコシイので省略。
で、これらの指標を以下の基準で採点する。
- 非対称性。A→Bの興味深さとB→Aの興味深さが同じ指標(sym)より、異なる指標(asym)がのぞましい。
- Nbとともに減少するか(dec), 減少しないか(no-dec)。(ここ、よくわからない。Nab, Nab', Na'b'が一定の時、Na'bが大きいほどA→Bの興味深さは下がるから、Nbが大きいときのほうが興味深さは下がってほしい、というようなことだろうか?)
- 独立性。AとBが独立な時に定数であってほしい(cst)。変化されると困る(var)。
- 反事例 Nab' がゼロのときにどうなるか。できれば最大値ないし無限大になってほしい(cst)。そうでないと困る(var)。
- Pab'がゼロに近いときにどうなるか。普通に考えれば、ゼロから離れるにつれて興味深さは下がりそうだが(linear)、ちょっとゼロから離れていても依然として興味深いからあんまり値が下がってくれては困る(concave)、という見方と、いやさっさと下がってほしい(convex)、という見方がある。
- Nに対する敏感性。Nが大きいときに指標も大きくなってほしいという見方(stat)と、変わらないでほしいという見方(desc)があるだろう。
- 閾値が決めやすいほうがいい。そこで、NaとNbを固定したときの、AとBが独立だという帰無仮説の棄却閾を求めることが簡単か(easy), 難しいか(hard)に注目する。
- 意味がわかりやすいかどうか。a,b,cの三段階。
以上の基準で各指標を採点する。たとえば、ベイズファクターはasym, dec, cst, cst, convex, desc, easy, a. だそうだ。liftは、sym, dex, cst, var, linear, desc, easy, a。
この論文の本題は実はここからで、この採点表を主成分分析かなにかにかけて、指標を空間にマッピングし、データマイニング・ユーザの好みを聴取して選好ベクトルを描きいれ、あなたはこの指標をお使いなさいとレコメンドする... という、いささか斜め上の方向に突っ走っていくのである。それはそれで面白いんだけど、いま関心ないのでパス。
アソシエーション分析で使う指標が気持ち悪くて、もやもやしていたんだけど、その理由が自分なりに整理できたので、得るところ大きかった。
論文：データ解析(-2014) - 読了：Lenca, et al.(2008) アソシエーション・ルールの興味深さの指標