ノート/マイニング
訪問者数 4583 最終更新 2008-05-12 (月) 16:35:41
バスケット解析をＲで
図書データをＲで
バスケット解析 †
見た本 †
- 「データマイニング」 福田剛志、森本康彦、徳山豪著、共立出版
問題 †
みんながスーパーマーケットで１週間分の買物をするとする（米国での習慣）。
レジでの支払い時に、レジスター（ＰＯＳ端末）に買い物のリストが蓄積される。
この、＜１回の買物で買う品物のリスト＞のデータの蓄積を分析することによって、
どの品物を買った人がどの品物を同時に買うか、という情報を得ることが出来る。これを
参考にして商品配列を工夫する（近くに置く）などの売り上げ向上策が考えられる。
よく引用されるのが「紙おむつを買った人の多くがビールを買う」という例である。
これを完全なブラックボックス（理屈はわからないがとにかく結果として
紙おむつ→ビール）と考えるのではなく、
データマイニングでは「なぜその法則が成り立つのか」が人間にとってわかる必要が
あると考える。完全に自動化しないということであり、法則性の解釈に人間の介在が
必須と考えているようである。この辺が機械学習（ニューラルネットなど）とは異なる。
理論 †
定義：
- item: 例えば商品、手元の例では本
すべてのアイテムの集合 Ｉ。
- transaction: １回の買物籠の中身、手元の例では�。渦鵑梁濬弌↓△燭箸┐丕吋�月の貸出。
トランザクションＴはアイテムの集合。 Ｔ⊆Ｉ。
- association rule（相関ルール）「⇒」: Ｘ，Ｙ⊆ＩかつＸ∩Ｙ＝ΦであるＸ，Ｙの組に関する関係。例で言えば、Ｘが｛紙おむつ｝でＹが｛ビール｝。
「⇒」の前を前提部、後を結論部と呼ぶことにする。
- confidence 確信度: データベースＤ中のＸを含むトランザクションのうち、Ｙを含むものの割合がc(%)であるとき、「相関ルールＸ⇒ＹはＤにおいてｃ％の確信度confidenceで成立している」と言う。conf(Ｘ⇒Ｙ) = c% と書く。
- support 支持度: データベースＤ中のＸ∪Ｙを含むトランザクションの、全トランザクションに対する割合がs(%)であるとき、「相関ルールＸ⇒ＹはＤにおいてｓ％のサポート（支持度）supportをもつ」と言う。support(Ｘ⇒Ｙ） = s% と書く。
- 例
次のような４つのトランザクションがあるとする。
1: 含まれるアイテムはA,C,D
2: 含まれるアイテムはB,C,E
3: 含まれるアイテムはA,B,C,E
4: 含まれるアイテムはB,E
このとき、
conf({A}⇒{C})=(Aを含むトのうちCを含むト数)/(Aを含むト数）= 2/2 = 100%
support({A}⇒{C})=({A}∪{C}つまりAとCとを含むト数)/(全ト数) = 2/4 = 50%
conf({A}⇒{D})=(Aを含むトのうちDを含むト数)/(Aを含むト数）= 1/2 = 50%
support({A}⇒{D})=(AとDとを含むト数)/(全ト数) = 1/4 = 25%
conf({A,C}⇒{D})=(AとCを含むトのうちDを含むト数)/(AとCを含むト数）= 1/2 = 50%
support({A,C}⇒{D})=((AとC)とDを含むト数)/(全ト数) = 1/4 = 25%
- 計算の膨大さ
ＸとＹの選択のしかたで、非常に多くの「相関ルール」の可能性が出てくる。すべての組合せについて確信度や支持度を計算するのは大変になる。
アイテムがm個あるとき、相関ルールを作るためのk個を選ぶ方法はC(m,k)通りがあり、それぞれのk個を前提部と結論部に分ける方法は(2のk乗)-2通りあるので、両者の積になる。たとえばm=10でも57,000通り、m=100だと5.15×(10の47乗)となるので、すべての組合せについて計算することは困難である。一般に確信度と支持度がある程度高い情報が有用である。
価値の高い（確信度・支持度が高い）相関ルールを作るために、どのアイテム集合を選べばよいかは予めわかっていない。価値のあるルールを効率的に発見する方法が必要になる。
アプリオリアルゴリズム †
- Agrawal (SIGMOD 1993)
- 最小確信度 (minimum confidence) と最小支持度 (minimum support) を与えて、それ以上を持つ相関ルールを全て発見するという考え方。
- データベースＤ中の全てのトランザクションのうち、アイテム集合Ｘを含むトランザクションの割合を、support'(X)と書くことにする。
これを使うと、定義から
support(X⇒Y) = support'(X∪Y)
conf(X⇒Y) = support'(X∪Y)/support'(X)
と書ける。従って
support(X⇒Y) = support'(X∪Y) ≧ 最小支持度
conf(X⇒Y) = support'(X∪Y)/support'(X) ≧ 最小確信度
であるようなアイテム集合X∪Y、Xを生成しその確信度・支持度を求めればよい
- アイテム集合の支持度は逆単調である。つまりアイテム集合I, Jに対する
支持度support'(I), support'(J)について、
「もしI⊂Jならばsupport'(I)≧support'(J)」が成立つ。
これは自明だろう。I⊂Jとすると、Ｄ内にあるJを含むトランザクション集合Tr(J)は、必ずIを含むトランザクション集合Tr(I)に含まれる。つまりTr(J)⊆Tr(I)。だから全てのトランザクションに対する割合は、support'(J)≦ support'(I)。
- 最小支持度（minimum support）以上の支持度（support(X⇒Y)）を持つルールX⇒Yの確信度conf(X⇒Y)を求めるには、最小支持度以上の支持度support'(F)を持つアイテム集合 F（これを「頻出アイテム集合」と呼ぶ）のすべてについてその支持度を求めておけばよい。
（証明）
もし、アイテム集合Xが頻出でない（support'(X)＜最小支持度）なら、それより大きい（Xを包含する）アイテム集合Yの支持度は必ずXより小さく、頻出でない（逆単調性のため）。逆に、もしXが頻出であると、その部分集合Yの支持度はXより大きく、必ず頻出になる。
このことから、ルールX⇒Yが最小以上の支持度をもつなら、つまり support(X⇒Y) = support'(X∪Y) ≧ 最小支持度 なら、X∪Y⊇X であるから、Xの支持度 support'(X) ≧ 最小支持度 である。従って、X∪YもXも頻出であるので、すべての頻出アイテム集合の支持度を求めておけば、conf(X⇒Y) = support'(X∪Y)/support'(X) を求めることが出来る。
- これによって、条件を満たす相関ルールを全て求めるためには、
- 頻出アイテム集合（アイテム集合のうちsupport'が設定最小値より大きいもの）を全て見出し、それぞれのsupport'を求めておく
- これを使って、conf(X⇒Y) = support'(X∪Y)/support'(X)を計算し、それが設定した最小信頼度より大きいものを選ぶ
という手順を使えばよい。
- 一般に、前半のステップの方が処理が大変になる（データベースをスキャンしなければならない）ので、それを工夫することになる。データベースのスキャンはディスクアクセスを伴うので時間がかかる。
具体的には、
- １回のスキャンでいくつかのアイテム集合の支持度を計算する
- 要素数の少ないアイテム集合から始めてアイテム数を増やすが、ある集合で設定最小支持度を下回った場合は、それ以上アイテム数を増やしても支持度が増えないので（前出）そこで打ち切る
などの原理を使う。アプリオリアルゴリズムではk回目のデータベースのスキャンで要素数kのアイテム集合の支持度を求める方法を取っている。
ここからあと（3.1残り-3.2）は省略
分類階層つき相関ルール †
![[Toho University]](image/CLogo_Kihon_process.jpg "[Toho University]")
![[YYLAB]](image/yamanouc2.png "[YYLAB]")
