elsur.jpn.org >

« 読了: 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アルゴリズムでは、

  1. まず閾値以上のsupport(同時出現割合) を持つアイテムセットを抽出し、
  2. そのアイテムセットを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)のものも交じっている。

まず、よく使うやつ:

以下、confidenceを変換した指標。

その他の指標:

で、これらの指標を以下の基準で採点する。

以上の基準で各指標を採点する。たとえば、ベイズファクターはasym, dec, cst, cst, convex, desc, easy, a. だそうだ。liftは、sym, dex, cst, var, linear, desc, easy, a。

 この論文の本題は実はここからで、この採点表を主成分分析かなにかにかけて、指標を空間にマッピングし、データマイニング・ユーザの好みを聴取して選好ベクトルを描きいれ、あなたはこの指標をお使いなさいとレコメンドする... という、いささか斜め上の方向に突っ走っていくのである。それはそれで面白いんだけど、いま関心ないのでパス。

 アソシエーション分析で使う指標が気持ち悪くて、もやもやしていたんだけど、その理由が自分なりに整理できたので、得るところ大きかった。

論文:データ解析(-2014) - 読了:Lenca, et al.(2008) アソシエーション・ルールの興味深さの指標