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

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

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

主要方法有：9.1Apriori算法引例Apriori算法Apriori算法的典型應(yīng)用

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

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

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

一、尋找頻繁項(xiàng)集9.1Apriori算法

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

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

step1:潛在的頻繁1-項(xiàng)集C1為

{a}，，{c}，guwuaqo，{e}由最小支持度可以得到頻繁1-項(xiàng)集L1{a}，，{c}，{e}

交易號(hào)商品1a,c,d2b,c,e3a,b,c,e4b,e9.1Apriori算法一、尋找頻繁項(xiàng)集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交易號(hào)商品1a,c,d2b,c,e3a,b,c,e4b,estep3:在頻繁L2基礎(chǔ)上求L3

交易號(hào)商品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}因此所有的頻繁項(xiàng)集為：{a},,{c},{e},{a,c},{b,c},{b,e},{c,e},{b,c,e}潛在1-項(xiàng)集C1頻繁1-項(xiàng)集L1連接潛在2-項(xiàng)集C1頻繁2-項(xiàng)集L2連接剪枝潛在3-項(xiàng)集C3頻繁3-項(xiàng)集L3.。。。Apriori算法尋找頻繁項(xiàng)集的步驟——受歡迎的商品或商品組合。二、尋找強(qiáng)關(guān)聯(lián)規(guī)則關(guān)聯(lián)規(guī)則：形式上為

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

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

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

如1000個(gè)人中只有一個(gè)人購(gòu)買了烤爐，又購(gòu)買了碳，所以

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

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

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

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

由頻繁項(xiàng)集產(chǎn)生關(guān)聯(lián)規(guī)則如表：潛在強(qiáng)關(guān)聯(lián)規(guī)則置信度是否為強(qiáng)關(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算法求所有的強(qiáng)關(guān)聯(lián)規(guī)則。解：step1.所有的頻繁項(xiàng)集為：{a},,{c},{e},{a,c},{b,c},{b,e},{c,e},{b,c,e}三、Apriori算法的步驟Apriori算法是一種尋找強(qiáng)關(guān)聯(lián)規(guī)則的算法

Apriori算法具體步驟:

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

給該超市的建議:

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

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

Apriori算法具體步驟:

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

關(guān)聯(lián)規(guī)則實(shí)用性的測(cè)度指標(biāo)

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

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

=1，A和B是獨(dú)立的

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