第9章探索內部結構：Clementine的關聯分析信息與計算科學專業2010本科

曹慧榮第9章探索內部結構：Clementine的關聯分析Apriori算法GRI算法序列關聯算法

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

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

2：尋找頻繁（強）關聯規則——高頻的購物模式如買牛奶的必然買面包。

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

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

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

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

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

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

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

L1支持度{a}0.5{b}0.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基礎上求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},{b},{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算法尋找頻繁項集的步驟——受歡迎的商品或商品組合。二、尋找強關聯規則關聯規則：形式上為

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

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

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

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

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

（應用機會少）（2）規則支持度大，規則置信度小，說明什么現象？二、尋找強關聯規則

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

二、尋找強關聯規則交易號商品1a,c,d2b,c,e3a,b,c,e4b,estep2.

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

Apriori算法具體步驟:

第一步：產生頻繁項集第二步：構造關聯規則。

給該超市的建議:

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

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

Apriori算法具體步驟:

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

關聯規則實用性的測度指標

規則AB提升度L=

L:<1，負相關

=1，A和B是獨立的

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