第7章 關(guān)聯(lián)規(guī)則挖掘

第七章關(guān)聯(lián)規(guī)則的挖掘一、關(guān)聯(lián)規(guī)則挖掘的含義關(guān)聯(lián)規(guī)則用于表示OLTP數(shù)據(jù)庫中諸多屬性（項(xiàng)集）之間的關(guān)聯(lián)程度。而關(guān)聯(lián)規(guī)則挖掘（AssociationRulesMining）則是利用數(shù)據(jù)庫中的大量數(shù)據(jù)通過關(guān)聯(lián)算法尋找屬性間的相關(guān)性。例：(超級市場)在購買商品A的客戶中有90%的人會同時購買商品B，則可用關(guān)聯(lián)規(guī)則表示為：支持度(Support)

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

同時購買A和B的客戶人數(shù)占購買A的客戶人數(shù)的百分比稱為規(guī)則的置信度。由于在實(shí)際應(yīng)用中，概率P一般是無法事先給出的，所以常以頻度代替購買A的顧客購買B的顧客同時購買A和B的顧客（AB）如果不考慮關(guān)聯(lián)規(guī)則的支持度和置信度，那么在事務(wù)數(shù)據(jù)庫中存在無窮多的關(guān)聯(lián)規(guī)則。事實(shí)上，人們一般只對滿足一定的支持度和可信度的關(guān)聯(lián)規(guī)則感興趣。為了發(fā)現(xiàn)出有意義的關(guān)聯(lián)規(guī)則，需要給定兩個閾值：最小支持度和最小置信度。關(guān)聯(lián)規(guī)則挖掘的實(shí)質(zhì)是在數(shù)據(jù)集合中尋找滿足用戶給定的最小支持度和最小置信度的規(guī)則。

例：交易情況如下表，要求最小支持度為50%,最小可信度為50%,則可得到：AC(50%,66.6%)CA(50%,100%)ID號購買的商品001A，B，C002A，C003A，D004B，E，F(xiàn)二、關(guān)聯(lián)規(guī)則挖掘算法：TheAprioriAlgorithm

Agrawal等人提出1、術(shù)語項(xiàng)集：在數(shù)據(jù)庫中出現(xiàn)的屬性值的集合。頻繁項(xiàng)集：滿足最小支持度要求的項(xiàng)集。關(guān)聯(lián)規(guī)則一定是在滿足用戶的最小支持度要求的頻繁項(xiàng)集中產(chǎn)生的，因此，關(guān)聯(lián)規(guī)則挖掘也就是在數(shù)據(jù)庫中尋找頻繁項(xiàng)集的過程。K_項(xiàng)集：包含K個項(xiàng)的項(xiàng)集。交易號購買的商品001A，B，C002A，C003A，D004B，E，F(xiàn)例：項(xiàng)集：{A，B，C，D，E，F(xiàn)，..}1_項(xiàng)集：{A}，{B}，{C}，..，{F}2_項(xiàng)集：{A，B}，{A，C}….如要求最小支持度為50%，則：頻繁項(xiàng)集：{A}，{B}，{C}，{A，C}頻繁項(xiàng)集的任何子集也一定是頻繁的??！2、關(guān)聯(lián)規(guī)則分類1）根據(jù)規(guī)則中所處理的值類型布爾關(guān)聯(lián)規(guī)則：規(guī)則考慮的關(guān)聯(lián)項(xiàng)是否存在量化關(guān)聯(lián)規(guī)則：規(guī)則描述的是量化的項(xiàng)或?qū)傩蚤g的規(guī)則2）根據(jù)規(guī)則中所涉及的數(shù)據(jù)維(1)是單維的，涉及buys;(2)多維，涉及年齡、收入和buys3）根據(jù)規(guī)則中所涉及的抽象層商品位于不同層，計(jì)算機(jī)的抽象層高，稱為多層關(guān)聯(lián)規(guī)則3、Apriori算法符號定義：Lk:k項(xiàng)頻繁集的集合；Ck：k項(xiàng)集的候補(bǔ)集合步驟：連接:

用Lk-1自連接得到Ck，（k>2)[注]

設(shè)l1,l2是有兩個有k-1個有序項(xiàng)的項(xiàng)集，lj[i]代表k-1個項(xiàng)的第i項(xiàng)(j=1,2;i=1,2,k-1)。l1和l2是可連接的l1Xl2，需滿足：

l1[1]=l2[1],l1[2]=l2[2]，….，l1[k-2]=l2[k-2]，

l1[k-1]≠l2[k-1]，產(chǎn)生的項(xiàng)是：

l1[1]l1[2]….l1[k-2]l1[k-1]l2[k-1](lj[i]是有序的）*注：C2=由1_項(xiàng)集兩兩組合生成，共C2m(m為1_項(xiàng)集合的項(xiàng)數(shù)）修剪:

一個k-項(xiàng)集，如果它的一個k-1項(xiàng)子集不是頻繁的，那它本身也不可能是頻繁的。例：l1={A,B,C}，l2={A,B,D}，l3={A,C,F}則：l1Xl2={A,B,C,D}l1X

l3，l2X

l3均為空為什么l1

X

l3不生成{A,B,C,F}?{A，B，C}，{A，B，F(xiàn)}4、偽代碼:min_support為最小支持度

L1=找頻繁1_項(xiàng)集；for(k=2;Lk!=;k++){

Ck=由Lk-1生成候補(bǔ)集合；

foreach

t

∈

Ck

{

計(jì)算t在數(shù)據(jù)集合中出現(xiàn)的次數(shù)；

if(出現(xiàn)計(jì)數(shù)小于min_support)

從Ck中剔除；

}

Lk=Ck；

}return

k

Lk;5、關(guān)聯(lián)規(guī)則挖掘例，（要求最小支持?jǐn)?shù)為2）數(shù)據(jù)庫D掃描DC1itemsetsup{12}1{13}2{15}1{23}2{25}3C2{35}2C2掃描DC3掃描DL3L1L26、可以產(chǎn)生哪些規(guī)則前面的例子中，得到一個頻繁集{2，3，5}，非空真子集有{2}，{3}，{5}，{2，3}，{2，5}，{3，5}L1L3L2規(guī)則：2353

255

2323

525

335

2置信度：2/3=66%（{2，3，5}頻度/{2}頻度）2/3=66%（{2，3，5}頻度/{3}頻度）2/3=66%（{2，3，5}頻度/{5}頻度）2/2=100%（{2，3，5}頻度/{2，3}頻度）2/3=66%（{2，3，5}頻度/{2，5}頻度）2/2=100%（{2，3，5}頻度/{3，5}頻度）支持度：2/4=50%7、Apriori

夠快了嗎?—性能瓶頸Apriori算法的核心:用頻繁的(k-1)_項(xiàng)集生成候選的頻繁k_項(xiàng)集用數(shù)據(jù)庫掃描和模式匹配計(jì)算候選集的支持度Apriori

的瓶頸:候選集生成巨大的候選集:104

個頻繁1_項(xiàng)集要生成107

個候選2_項(xiàng)集要找尺寸為100的頻繁模式，如{a1,a2,…,a100},你必須先產(chǎn)生21001030

個候選集（1_項(xiàng)集）多次掃描數(shù)據(jù)庫：如果最長的模式是n的話，則需要n次數(shù)據(jù)庫掃描為提高Apriori算法的性能，有許多改進(jìn)的算法。8、如何在概念分層有效地挖掘多層關(guān)聯(lián)規(guī)則

一般采用自頂向下策略，由概念層1開始向下，到較低的更特定的概念層，對每個概念層的頻繁集累加計(jì)數(shù)，直到不能再找到頻繁項(xiàng)集。計(jì)算機(jī)[支持度=10%]臺式機(jī)[支持度=6%]筆記本[支持度=4%]層1:minsup=5%層2:minsup=5%非頻繁

問題：因?yàn)檩^低層次抽象的項(xiàng)不大可能像較高層次抽象的項(xiàng)出現(xiàn)得那么頻繁。如果最小支持度閥值設(shè)置的太高，可能丟掉出現(xiàn)在較低抽象層次中有意義的關(guān)聯(lián)規(guī)則。如果閥值設(shè)置太底，可能會出現(xiàn)在較高抽象層的無興趣的關(guān)聯(lián)規(guī)則。對于所有層使用一致的最小支持度8、如何在概念分層有效地挖掘多層關(guān)聯(lián)規(guī)則

一般采用自頂向下策略，由概念層1開始向下，到較低的更特定的概念層，對每個概念層的頻繁集累加計(jì)數(shù)，直到不能再找到頻繁項(xiàng)集。對于所有層使用一致的最小支持度在較低層使用遞減的最小支持度計(jì)算機(jī)[支持度=10%]臺式機(jī)[支持度=6%]筆記本[支持度=4%]層1:minsup=5%層2:minsup=3%9、冗余的多層關(guān)聯(lián)規(guī)則處理買筆記本買打印機(jī)[支持度=8%,置信度=70%](1)

買IBM筆記本買打印機(jī)[支持度=2%,置信度=72%](2)規(guī)則2有用嗎？它提供了新穎的信息嗎？

如果后一個具有較小一般性的規(guī)則，它不提供新的信息，應(yīng)當(dāng)刪除它！如果一個規(guī)則的祖先，它的支持度和置信度都接近于該規(guī)則的“期望”值，這個規(guī)則是冗余的。

從（1）的置信度=70%推斷：

買筆記本同時買打印機(jī)的交易數(shù)/買筆記本交易數(shù)=70%IBM筆記本屬于筆記本，因此置信度也應(yīng)該在70%左右。由（2)實(shí)際為72%，基本無差異。9、冗余的多層關(guān)聯(lián)規(guī)則處理買筆記本買打印機(jī)[支持度=8%,置信度=70%](1)

買IBM筆記本買打印機(jī)[支持度=2%,置信度=72%](2)規(guī)則2有用嗎？它提供了新穎的信息嗎？

如果后一個具有較小一般性的規(guī)則，它不提供新的信息，應(yīng)當(dāng)刪除它！如果一個規(guī)則的祖先，它的支持度和置信度都接近于該規(guī)則的“期望”值，這個規(guī)則是冗余的。

從（1）的支持度=8%推斷：

買筆記本同時買打印機(jī)的交易數(shù)/總交易數(shù)=8%，假定從數(shù)據(jù)集中還發(fā)現(xiàn)，IBM筆記本在占整個筆記本銷量的25%。

則：買IBM筆記本的支持度應(yīng)該為8%*25%=2%，由（2)實(shí)際為2%，兩者相同。結(jié)論：規(guī)則（2）不是有趣的，因?yàn)樗惶峁┯腥さ男畔ⅰ?0、關(guān)聯(lián)規(guī)則的相關(guān)分析

強(qiáng)關(guān)聯(lián)規(guī)則不一定有趣其實(shí)，規(guī)則是誤導(dǎo)，因?yàn)橘徺I影碟機(jī)的可能性是75%，比66%還大。事實(shí)是：計(jì)算機(jī)游戲和影碟機(jī)是負(fù)相關(guān)的。

A和B的相關(guān)性：corrAB:<1，負(fù)相關(guān)

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

>1，正相關(guān)，每一個出現(xiàn)蘊(yùn)涵另一個出現(xiàn)例：在10000個交易中，6000個顧客交易包含計(jì)算機(jī)游戲，7500個顧客交易包含影碟機(jī)，4000個交易包含計(jì)算機(jī)游戲和影碟機(jī)。10、關(guān)聯(lián)規(guī)則的相關(guān)分析

強(qiáng)關(guān)聯(lián)規(guī)則不一定有趣其實(shí)，規(guī)則是誤導(dǎo)，因?yàn)橘徺I影碟機(jī)的可能性是75%，比66%還大。事實(shí)是：計(jì)算機(jī)游戲和影碟機(jī)是負(fù)相關(guān)的。例：在10000個交易中，6000個顧客交易包含計(jì)算機(jī)游戲，7500個顧客交易包含影碟機(jī)，40