Clementine關(guān)聯(lián)分析曹慧榮20110426

第9章探索內(nèi)部結(jié)構(gòu)：Clementine的關(guān)聯(lián)分析信息與計算科學專業(yè)2010本科

曹慧榮第9章探索內(nèi)部結(jié)構(gòu)：Clementine的關(guān)聯(lián)分析Apriori算法GRI算法序列關(guān)聯(lián)算法

主要方法有：9.1Apriori算法引例Apriori算法Apriori算法的典型應用

內(nèi)容安排：Step1:尋找頻繁項集;Step2:給出強關(guān)聯(lián)規(guī)則。9.1Apriori算法ID牛奶雞蛋面包110121013111401150001：尋找頻繁項集——受歡迎的商品或商品組合。

2：尋找頻繁（強）關(guān)聯(lián)規(guī)則——高頻的購物模式如買牛奶的必然買面包。

項集支持度{牛奶}0.6{雞蛋}0.4{面包}0.8{牛奶，雞蛋}0.2{牛奶，面包}0.6{雞蛋，面包}0.4{牛奶，雞蛋，面包}0.2引例：某超市銷售數(shù)據(jù)項：商品；項集：商品的集合。9.1Apriori算法ID牛奶雞蛋面包11012101311140115000例：某超市銷售數(shù)據(jù)Apriori算法完成：1.尋找頻繁項集；受歡迎的商品。2.尋找頻繁（強）的關(guān)聯(lián)規(guī)則。高頻的購物模式。當數(shù)據(jù)量大時，必須引入有效算法9.1Apriori算法K-項集：包含K個項的集合。頻繁項集：所有支持度大于等于最小支持度的項集。頻繁項集的尋找：如果有m種商品，則只要計算所有非空項集的支持度，大于等于最小支持度的即為頻繁項集。

一、尋找頻繁項集9.1Apriori算法

如前所述，m種商品的非空項集有2m-1個，計算量爆炸性增長。頻繁項集的性質(zhì)：

性質(zhì)1：頻繁項集的子集必為頻繁項集；性質(zhì)2：非頻繁項集的超集必為非頻繁項集。先找頻繁項集；然后再找頻繁規(guī)則例題1：設(shè)有項集T={a,b,c,d,e}所示的簡單交易數(shù)據(jù)庫，設(shè)minS=50%，求所有的頻繁項集。解：

step1:潛在的頻繁1-項集C1為

{a}，，{c}，uo0y0cy，{e}由最小支持度可以得到頻繁1-項集L1{a}，，{c}，{e}

交易號商品1a,c,d2b,c,e3a,b,c,e4b,e9.1Apriori算法一、尋找頻繁項集step2:在頻繁L1基礎(chǔ)上求L2

L1支持度{a}0.50.75{c}0.75{e}0.75連接L1*L1得到潛在C2C2支持度{a,b}0.25{a,c}0.5{a,e}0.25{b,c}0.5{b,e}0.75{c,e}0.5交易號商品1a,c,d2b,c,e3a,b,c,e4b,estep3:在頻繁L2基礎(chǔ)上求L3

交易號商品1a,c,d2b,c,e3a,b,c,e4b,eL2支持度{a,c}0.5{b,c}0.5{b,e}0.75{c,e}0.5連接L2*L2得到{a,b,c},{a,c,e},{b,c,e}剪枝，從而得到潛在的C3{b,c,e}因此所有的頻繁項集為：{a},,{c},{e},{a,c},{b,c},{b,e},{c,e},{b,c,e}潛在1-項集C1頻繁1-項集L1連接潛在2-項集C1頻繁2-項集L2連接剪枝潛在3-項集C3頻繁3-項集L3.。。。Apriori算法尋找頻繁項集的步驟——受歡迎的商品或商品組合。二、尋找強關(guān)聯(lián)規(guī)則關(guān)聯(lián)規(guī)則：形式上為

(規(guī)則支持度，規(guī)則置信度)支持度(Support)：同時購買A和B的客戶人數(shù)占總客戶數(shù)的百分比稱為規(guī)則的支持度。

置信度(Confidence)：同時購買A和B的客戶人數(shù)占購買A的客戶人數(shù)的百分比稱為規(guī)則的置信度。

由于在實際應用中，概率P一般是無法事先給出的，所以常以頻率代替。前項后項二、尋找強關(guān)聯(lián)規(guī)則例題2：計算下面規(guī)則的支持度與置信度。ID牛奶奶酪雞蛋面包1100121101311114000150100（1）{面包}{牛奶}（2）{牛奶}{面包}（3）{雞蛋}{奶酪}二、尋找強關(guān)聯(lián)規(guī)則ID牛奶奶酪雞蛋面包1100121101311114000150100{面包}{牛奶}(60%,75%){牛奶}{面包}(60%,100%){雞蛋}{奶酪}(20%,100%)(規(guī)則支持度，規(guī)則置信度)思考：（1）規(guī)則支持度小，規(guī)則置信度大，說明什么現(xiàn)象？

如1000個人中只有一個人購買了烤爐，又購買了碳，所以

{烤爐}{碳}(0.1%,100%)

（應用機會少）（2）規(guī)則支持度大，規(guī)則置信度小，說明什么現(xiàn)象？二、尋找強關(guān)聯(lián)規(guī)則

AB(規(guī)則支持度，規(guī)則置信度)一個好的規(guī)則應該有比較高的支持度和置信度．如果滿足最小支持度閾值和最小置信度閾值，則稱這個規(guī)則為強規(guī)則。我們的目的就是找出強關(guān)聯(lián)規(guī)則。由頻繁項集可以產(chǎn)生潛在的強關(guān)聯(lián)規(guī)則

二、尋找強關(guān)聯(lián)規(guī)則交易號商品1a,c,d2b,c,e3a,b,c,e4b,estep2.

由頻繁項集產(chǎn)生關(guān)聯(lián)規(guī)則如表：潛在強關(guān)聯(lián)規(guī)則置信度是否為強關(guān)聯(lián)規(guī)則{a}{c}1Yes{c}{a}0.67No{c}0.67No{c}0.67No{e}1Yes{e}1Yes例題3：同例題1的數(shù)據(jù)。設(shè)minS=50%，minC=80%，利用Apriori算法求所有的強關(guān)聯(lián)規(guī)則。解：step1.所有的頻繁項集為：{a},,{c},{e},{a,c},{b,c},{b,e},{c,e},{b,c,e}三、Apriori算法的步驟Apriori算法是一種尋找強關(guān)聯(lián)規(guī)則的算法

Apriori算法具體步驟:

第一步：產(chǎn)生頻繁項集第二步：構(gòu)造關(guān)聯(lián)規(guī)則。

給該超市的建議:

請將商品b和e的捆綁銷售或就近安排貨架!

四、Apriori算法的典型應用潛在強關(guān)聯(lián)規(guī)則置信度是否為強關(guān)聯(lián)規(guī)則{a}{c}1Yes{c}{a}0.67No{c}0.67No{c}0.67No{e}1Yes{e}1Yes成功案例：神奇的購物籃分析《啤酒與尿布:神奇的購物籃分析》的故事是營銷屆的神話，“啤酒”和“尿布”兩個看上去沒有關(guān)系的商品擺放在一起進行銷售、并獲得了很好的銷售收益，這種現(xiàn)象就是賣場中商品之間的關(guān)聯(lián)性，研究“啤酒與尿布”關(guān)聯(lián)的方法就是購物籃分析，購物籃分析是沃爾瑪秘而不宣的獨門武器，購物籃分析可以幫助我們在門店的銷售過程中找到具有關(guān)聯(lián)關(guān)系的商品，并以此獲得銷售收益的增長！Apriori算法是一種尋找強關(guān)聯(lián)規(guī)則的算法

Apriori算法具體步驟:

第一步：產(chǎn)生頻繁項集第二步：構(gòu)造關(guān)聯(lián)規(guī)則。附：關(guān)聯(lián)規(guī)則的相關(guān)分析強關(guān)聯(lián)規(guī)則不一定有正確的指導意義！例：在10000個交易中，6000個顧客交易包含計算機游戲，7500個顧客交易包含影碟機，4000個交易包含計算機游戲和影碟機。規(guī)則其實是誤導，因為購買影碟機的可能性是75%，比66%還大。事實是：計算機游戲和影碟機是負相關(guān)的。

關(guān)聯(lián)規(guī)則實用性的測度指標

規(guī)則AB提升度L=

L:<1，負相關(guān)

=1，A和B是獨立的

>1，正相關(guān)，每一個出現(xiàn)蘊涵另一個出現(xiàn)p({游戲})=0.6，p({影碟機})=0.75，p({游戲,影碟機})=0.4L=0.4/0.6*0.75=0.89<1負相關(guān)，規(guī)則無意義！附：關(guān)聯(lián)規(guī)則的相關(guān)分析小結(jié)：基本概念：