Microsoft PowerPoint - 13AssociationRules-01.ppt [互換モード]

Size: px

Start display at page:

Download "Microsoft PowerPoint - 13AssociationRules-01.ppt [互換モード]"

ゆきやたけ
5 years ago
Views:

1 本日の予定情報意味論 (3) 相関規則櫻井彰人慶應義塾大学理工学部相関規則相関規則発見のアルゴリズム large/frequent item set ( 頻出アイテム集合 ) support ( 支持度 ) confidence ( 信頼度 ) 相関規則 (association rule) R. Agrawal, T. Imielinsi, and A. Swami, Mining Association Rules between Sets of Items in Large Databases, SIGMOD Conference R. Agrawal and R. Sriant, Fast Algorithms for Mining Association Rules, VLDB バスケットデータ小売店 ( デパートスーパーコンビニ等 ) での売上データをこのように呼ぶ何故か? 一個のデータ ( レコード ) は日時顧客属性購入品の単価個数類似の構造をもったものをバスケットデータと呼ぶ一回ごとの取引 ( 売上購入預入れ引出し等 ) をトランザクションと呼ぶバスケット分析相関規則バスケット= 買い物かごバスケットの中 ( 購入した商品の組合せ ) を知ってどのような組合せで商品が購入されるかを知るレシート 03 牛乳パン果物トランザクション <03, { 牛乳, パン, 果物 }> 複数種の製品 ( サービスでもよい ) がどのような組合せで同時に購買されやすいかを表現する理解が容易 {a, b, c, d,,,} も {a, b,,,,} も非常に頻繁に現れれば {a, b} が購入されるときは {c, d} も購入されると言える行動に結び付けられる {a, b} の近くに {c, d} を置く

2 相関規則の例問合せ (query) の例パンとバターを含むトランザクションの 90% は牛乳を含む ( パンとバターを買うと 90% の確からしさでその客は牛乳を買う ) 前件 (antecedent) パンとバター後件 (consequent) 牛乳信頼度 (confidence factor) 90% 前件は前提後件は結論などと呼ぶ結論に即席麺を含む全ての規則を見つけよ前提に缶コーヒーを含む全ての規則を見出せ前提にパン結論にジュースを含む全ての規則をみつけよ店内の棚 Aと棚 Bにある品目に関係する全ての規則を見出せ結論に即席麺を含む規則のなかで最良の ( 信頼性が最も高い ) 個の規則を見出せ記法記法アイテム I = {i,i,,i m } トランザクションアイテムの集合通常アイテムは辞書式順序で整列 TID トランザクションの一意名 T I 相関規則 X Y X I, Y I かつ X Y 例 I アイテムの集合 { きゅうり, パセリ, 玉ねぎ, トマト, 塩, パン, ほうれん草, 卵, バター } D トランザクション集合 {{ きゅうり, パセリ, 玉ねぎ, トマト, 塩, パン }, { トマト, きゅうり, パセリ }, 3 { トマト, きゅうり, ほうれん草, 玉ねぎ, パセリ }, 4 { トマト, きゅうり, 玉ねぎ, パン }, 5 { トマト, 塩, 玉ねぎ }, 6 { パン, 卵 } 7 { トマト, 卵, きゅうり } 8 { パン, バター }} Confidence と Support 相関規則 X Y の信頼度 confidence が c であるとは, D 中のトランザクションで X を含むものの 00 c% はまた Y をも含む. 相関規則 X Y の支持度 support が s であるとは, D 中のトランザクションの 00 s% が X と Y とを含む. アイテムセット X の支持度 support も同様に定義するすなわち D 中のトランザクションの 00 s% が X を含む.

3 問題の定義トランザクション集合 D が与えられたとき, 支持度と信頼度がユーザが指定する最小支持度と最小信頼度より大きくなるような相関規則全部を求めよ. なお最小支持度より大きな支持度をもつアイテムセットを頻出アイテム集合と呼ぶ例 T ID アイテム乳製品, 果物乳製品, 果物, 野菜 3 乳製品 4 果物, シリアル support({ 乳製品 }) = 3/4 support({ 果物 }) = 3/4 support({ 乳製品, 果物 }) =/4 もし最小支持度 =3/4 ならば { 乳製品 } と { 果物 } は頻出アイテム集合, { 乳製品, 果物 } は違う. 注 X A は X Y A を意味しない (X も Y も買う, i.e., 論理的には and) 最小支持度に達しないかもしれない X A と A Z から X Z が得られるわけではない最小信頼度に達しないかもしれない全相関規則を見つけること頻出アイテム集合全てを見出せ最小支持度より大きな支持度をもつアイテムセット. 頻出アイテム集合を用いて規則を生成する. アイデアの基本仮に ABCD と AB が頻出アイテム集合とする次を計算する conf = support(abcd) / support(ab) もし conf >= minconf ならば AB CD が成立する. 頻出アイテム集合の発見データを複数回スキャンする最初のスキャン個々のアイテムの支持度を数える. 以降のスキャン以前のスキャンで得た頻出アイテム集合を用いて候補アイテム集合を生成する. データをスキャンして当該候補の本当の支持度を計算する. もし新しい頻出アイテム集合が得られなくなれば停止. 定義. - 個のアイテムをもつ頻出アイテム集合. 3

4 トリック Apriori property 頻出アイテム集合の枝狩り頻出アイテム集合のどんな部分集合も頻出. 従って頻出 - アイテム集合 - を見つけるには頻出 - アイテム集合を組み合わせて候補を作る. 頻出でない部分集合を含む候補を削除する. a, b a, b, c a, c a, b, d a, c, d b, c, d a, d a,b,c,d b, c b, d a b c d c, d {a,d} は頻出ではないとする. そうすると 3- アイテム集合 {a,b,d}, {a,c,d} および 4- アイテム集合 {a,b,c,d} は頻出でなく生成されない. Apriori Algorithm 候補の生成 L { 頻出 -アイテム集合 } for ( ; L Answer - C apriori- gen( L ); for 全トランザクション t D do begin C subset( C,t) ; ) do begin t L ; - for 全候補 c C do c.count ; L { c C c.count minsup} t アイテム生起回数の算出新しい - アイテム集合の候補の生成全候補の支持度の計算 minsup 以上の支持度をもつ候補のみ選び出す Join step insert into C select item, item,..., item, q. item from L as p, L as q where item q.item,..., item q.item Prune step for 全アイテム集合 c C do for cの全 ( -) -部分集合 s do if ( s L-) then C から c を削除 p と q はつとも - 頻出アイテム集合で先頭の - アイテムが同一のもの, item q.item q の最後のアイテムを p に付加することによる候補の (-)- 部分集合を全部調べ頻出でない部分集合をもつような候補を削除する先頭だけで十分何故か? 例正しさ L 3 = { { 3}, { 4}, { 3 4}, { 3 5}, { 3 4} } join のあと { { 3 4}, { 3 4 5} } prune のあと { 3 4} { 4 5} と {3 4 5} は L 3 に含まれていない C L であることを示せ頻出アイテム集合の部分集合は頻出でなければならないこの join は L - に任意のアイテムを付け加えて拡張し次にその (-) 部分集合が L - にないものを削除することと等価である insert into C select item, item,..., item, q. item from L as p,l as q where item q.item,..., item q.item for 全アイテム集合 c C do for cの全 ( -) -部分集合 s do if ( s L-) then C から c を削除, item 重複を防ぐ q.item 4

5 Subset 関数 C 中のでトランザクション t に含まれているものを抽出するハッシュ木を用いることにより O() の時間で調べることができる. 最大時間 O(max(,size(t)) L { 頻出 -アイテム集合 } for ( ; L- ; ) do begin C apriori- gen( L- ); for 全トランザクションt D do begin Ct subset( C,t) for 全候補 c Ct do c.count ; L { c C c.count minsup} Answer L; 簡単な例 Trans-ID Items A C D B C E 3 A B C E 4 B E 5 A B C E 簡単な例 TID アイテム集合 ACD BCE 3 ABCE 4 BE 5 ABCE 最小支持度 60% 最小信頼度 75% 頻出アイテム集合支持度 {BCE},{AC} 60% {BC},{CE},{A} 60% {BE},{B},{C},{E} 80% 相関規則 X => Y 信頼度 (X => Y) = support(x Y)/ support(x) 支持度 (X => Y) = support(x Y) 規則 {BC} => {E} に対し支持度 = support({bce}) = 60% 信頼度 = support({bce})/support({bc}) = 00% 簡単な例 TID アイテム ACD BCE 3 ABCE 4 BE 5 ABCE 相関規則信頼度 {BC} =>{E} 00% {BE} =>{C} 75% {CE} =>{B} 00% {B} =>{CE} 75% {C} =>{BE} 75% {E} =>{BC} 75% 最小支持度 60% 最小信頼度 75% 頻出アイテム集合支持度 {BCE},{AC} 60% {BC},{CE},{A} 60% {BE},{B},{C},{E} 80% 支持度 (X => Y) = support(x Y) 信頼度 (X => Y) = support(x Y)/ support(x) 簡単な例 minsup = 40% Database D. TID Items C {A} 3 L A C D {B} 4 B C E {C} 4 3 A B C E {D} 4 B E {E} 4 5 A B C E C C L {AB} {AC} 3 {AE} {BC} 3 {BE} 4 {CE} 3 {AB} {AC} 3 {AE} {BC} 3 {BE} 4 {CE} 3. {A} 3 {B} 4 {C} 4 {E} 4 {AB} {AC} {AE} {BC} {BE} {CE} Database D TID Items A C D B C E 3 A B C E 4 B E 5 A B C E 簡単な例 minsup = 40% {AB} {AC} 3 {AE} {BC} 3 {BE} 4 {CE} 3 {ABC} {ABE} {ACE} {BCE} L 4 {ABCE} C 4 {ABCE} C 3 L 3 {ABC} {ABE} {ACE} {BCE} 3 {ABC} {ABE} {ACE} {BCE} 3 C 4 {ABCE} 5

6 別の例 Database D TID items 00 A C D 00 B C E 300 A B C E 400 B E {A C} Remove {B C} {C E} 3 {B E} {B C E}. {A} {D} Itemset sup {A B} {A C} {A E} {B C} {B E} 3 {C E} {B C E}. Remove {A} Remove {A B] {A C} {A E} {B C} {B E} {C E} {B C E} Apriori アルゴリズム例 3 データベース D. L. TID Items C {A} 3 {A} 3 00 A C D 00 B C E 300 A B C E {D} 400 A B E C C C 3 {A B} {A B} {A C} {A C} {A B C} {A E} {A E} {A B E} {B C} {B C} {A C E} {B E} 3 L 3 {B E} {B C E} {C E} {C E} and Remove {A B E} {B C E} Apriori アルゴリズム例 4 データベース D. L. TID Items C {A} {A} 00 A C E 00 B C E 300 A B C {D} {E} 400 B E {E} L C C {A B} {A B} {A C} {A C} {A C} {B C} {A E} 0 {A E} {B E} {B C} {B C} {B E} {B E} {3 {C 5} E} {C E} 興味度の尺度客観的尺度には二つのよく知られた尺度支持度信頼度主観的尺度実際にルール ( パターン ) が興味深いのは例えば以下のような場合それが思いがけない時 ( ユーザにとって驚くべき事実であるとき ); and/or 行動可能なとき ( ユーザがそれによって何か意味のある行動がとれるとき ) 支持度と信頼度に対する批判例 (Agrawal & Yu, PODS98) 支持度人の学生の中で 3000 人がバスケットボールをする 3750 人がシリアルを食べる 000 人がバスケットをし, かつシリアルを食べるバスケットボールをするシリアルを食べる [40%, 66.7%] は誤解を招くなぜなら全学生の中でシリアルを食べる学生は75% でそれは 66.7% よりも大きいからバスケットボールをするシリアルを食べない [0%, 33.3%] の方がより正確だが, 支持度と信頼度はいずれもより低い basetball not basetball sum(row) 信頼度 000, cereal , not cereal sum(col.) 例支持度と信頼度に対する批判 X と Y 正の相関を持つ (8 ヶのペア中 6 ヶが一致 ) X と Z 負の相関を持つ (8 ヶのペア中 5 ヶが不一致 ) X Z の支持度と信頼度の方が大きくなる X0000 Y Z0 Rule Support Confidence X Y 5% 50% X Z 37.50% 75% 6

7 興味度の他の尺度 corr A B) corr A,B = A) B) A) と B) を考える (A, B を含まない場合を考えることに ) A と B とが独立のとき A^B)=B)*A) この値がより小さいとき,AとBは負の相関を持つ; そうでなければ AとBは正の相関を持つ X0000 Y Z0 Itemset Support corr X,Y 5% X,Z 37.50% 0.9 Y,Z.50% 0.57 例バスケットボールとシリアルの場合 basetball not basetball sum(row) cereal not cereal sum(col.) バスケットボールをする B シリアルを食べる C B)=0.6 C)=0.75 C)=0. 5 B C)= 0.4 B C)=0. B C) B C [40%, 66.7%] corr B,C = = = B) C) B C) B C [0%, 33.3%] corr B,C = = 0. = 0. B) C)

Microsoft PowerPoint - 13AssociationRules-01.ppt [互換モード]

Microsoft PowerPoint - 13AssociationRules-01.ppt [互換モード] 本日の予定情報意味論 (3) 相関規則櫻井彰人慶應義塾大学理工学部相関規則相関規則発見のアルゴリズム large/frequent item set ( 頻出アイテム集合 ) support ( 支持度 ) confidence ( 信頼度 ) 相関規則 (association rule) R. Agrawal, T. Imielinsi, and A. Swami, Mining Association