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

1、第七章第七章 關聯(lián)規(guī)則的挖掘關聯(lián)規(guī)則的挖掘一、關聯(lián)規(guī)則挖掘的含義一、關聯(lián)規(guī)則挖掘的含義 關聯(lián)規(guī)則用于表示關聯(lián)規(guī)則用于表示OLTPOLTP數據庫中諸多屬性（項集）之間數據庫中諸多屬性（項集）之間的關聯(lián)程度。而關聯(lián)規(guī)則挖掘（的關聯(lián)程度。而關聯(lián)規(guī)則挖掘（ Association Rules MiningAssociation Rules Mining）則是利用數據庫中的大量數據通過關聯(lián)算法尋找屬性間的相關則是利用數據庫中的大量數據通過關聯(lián)算法尋找屬性間的相關性。性。 例：例：( (超級市場超級市場) )在購買商品在購買商品A A的客戶中有的客戶中有90%90%的人會同時購的人會同時購買商品買商品B

2、B，則可用關聯(lián)規(guī)則表示為：，則可用關聯(lián)規(guī)則表示為：BA支持度支持度(Support) 同時購買同時購買A A和和B B的客戶人數占總客戶數的百分比稱為規(guī)則的的客戶人數占總客戶數的百分比稱為規(guī)則的支持度。支持度。)()(supBAPBAport置信度置信度(Confidence) 同時購買同時購買A和和B的客戶人數占購買的客戶人數占購買A的客戶人數的百分比稱的客戶人數的百分比稱為規(guī)則的置信度。為規(guī)則的置信度。)()()|()(APBAPABPBAconfidence 由于在實際應用中，概率由于在實際應用中，概率P一般是無法事先給出的，一般是無法事先給出的，所以常以頻度代替所以常以頻度代替購買購買

3、A的顧客的顧客購買購買B的顧客的顧客同時購買同時購買A和和B的顧客（的顧客（A B） 如果不考慮關聯(lián)規(guī)則的支持度和如果不考慮關聯(lián)規(guī)則的支持度和置置信度信度，那么在事務數那么在事務數據庫中存在無窮多的關聯(lián)規(guī)則。事實上據庫中存在無窮多的關聯(lián)規(guī)則。事實上，人們一般只對滿足人們一般只對滿足一定的支持度和可信度的關聯(lián)規(guī)則感興趣。一定的支持度和可信度的關聯(lián)規(guī)則感興趣。 為了發(fā)現(xiàn)出有意義的關聯(lián)規(guī)則為了發(fā)現(xiàn)出有意義的關聯(lián)規(guī)則，需要給定兩個閾值需要給定兩個閾值：最最小支持度和最小小支持度和最小置置信度。信度。關聯(lián)規(guī)則挖掘的實質是在數據集合關聯(lián)規(guī)則挖掘的實質是在數據集合中尋找滿足用戶給定的最小支持度和最小置信度的

4、規(guī)則。中尋找滿足用戶給定的最小支持度和最小置信度的規(guī)則。 例：交易情況如下表，例：交易情況如下表，要求最小支持度為要求最小支持度為50%, 50%, 最小可信度為最小可信度為 50%, 50%, 則可得到：則可得到：A A C (50%, 66.6%) C (50%, 66.6%)C C A (50%, 100%) A (50%, 100%)ID號號購買的商品購買的商品001A，B，C002A，C003A，D004B，E，F(xiàn)二、關聯(lián)規(guī)則挖掘算法二、關聯(lián)規(guī)則挖掘算法： The Apriori Algorithm Agrawal等人提出等人提出1 1、術語、術語項集項集：在數據庫中出現(xiàn)的屬性值的集

5、合。在數據庫中出現(xiàn)的屬性值的集合。頻繁項集頻繁項集：滿足最小支持度要求的項集。滿足最小支持度要求的項集。 關聯(lián)規(guī)則一定是在滿足用戶的最小支持度要求的頻關聯(lián)規(guī)則一定是在滿足用戶的最小支持度要求的頻繁項集中產生的，因此，關聯(lián)規(guī)則挖掘也就是在數據庫中繁項集中產生的，因此，關聯(lián)規(guī)則挖掘也就是在數據庫中尋找頻繁項集的過程。尋找頻繁項集的過程。K_K_項集：項集：包含包含K K個項的項集。個項的項集。交易號交易號購買的商品購買的商品001A，B，C002A，C003A，D004B，E，F(xiàn)例：例：項集：項集：A，B，C，D，E，F(xiàn)，.1_項集：項集：A，B，C，.，F(xiàn)2_項集：項集：A，B，A，C.如要求最

6、小支持度為如要求最小支持度為50%，則：，則：頻繁項集：頻繁項集：A，B，C，A，C頻繁項集的任何子集也一定是頻繁的！頻繁項集的任何子集也一定是頻繁的！2、關聯(lián)規(guī)則分類、關聯(lián)規(guī)則分類1）根據規(guī)則中所處理的）根據規(guī)則中所處理的值類型值類型布爾關聯(lián)規(guī)則：規(guī)則考慮的關聯(lián)項是否存在布爾關聯(lián)規(guī)則：規(guī)則考慮的關聯(lián)項是否存在量化關聯(lián)規(guī)則：規(guī)則描述的是量化的項或屬性間的規(guī)則量化關聯(lián)規(guī)則：規(guī)則描述的是量化的項或屬性間的規(guī)則(2) )buys(x,)42K.50K(x,)30.39(x,背投高清晰電視收入年齡(1) )128Kbuys(x,)Sony(x,記憶棒的數碼相機Sonybuys2）根據規(guī)則中所涉及的）根

7、據規(guī)則中所涉及的數據維數據維(1)是單維的，涉及是單維的，涉及buys; (2)多維，涉及年齡、收入和多維，涉及年齡、收入和buys3）根據規(guī)則中所涉及的）根據規(guī)則中所涉及的抽象層抽象層)buys()30.39age(x,)buys()30.39age(x,計算機臺式機商品位于不同層，計算機的抽象層高，稱為商品位于不同層，計算機的抽象層高，稱為多層關聯(lián)規(guī)則多層關聯(lián)規(guī)則3 3、 AprioriApriori算法算法符號定義：符號定義： Lk:k項項頻繁頻繁集的集合；集的集合； Ck：k項集的候補集合項集的候補集合步驟：步驟：連接連接: 用用 Lk-1自連接得到自連接得到Ck，（，（k2) 注注

8、設設l1,l2是有是有兩個有兩個有k-1個有序項的項集，個有序項的項集，lji代表代表k-1個項的第個項的第i項項(j=1,2; i=1,2,k-1)。l1和和l2是可連接的是可連接的l1Xl2，需滿足：需滿足： l11=l21 ,l12=l22，.，l1k-2=l2k-2， l1k-1 l2k-1，產生的項是：產生的項是： l11l12.l1k-2l1k-1l2k-1(lji是有序的）是有序的）*注：注：C2= 由由1_項集兩兩組合生成項集兩兩組合生成 ，共，共C2m(m為為1_項集合的項數）項集合的項數）修剪修剪: 一個一個k-項集，如果它的一個項集，如果它的一個k-1項子集不是頻繁的，那

9、它本項子集不是頻繁的，那它本身也不可能是頻繁的。身也不可能是頻繁的。例：例：l1=A,B,C ， l2=A,B,D，l3=A,C,F則：則：l1 X l2=A,B,C,D l1 X l3，l2 X l3均為空均為空為什么為什么l1 X l3不生成不生成A,B,C,F?A，B，C ，A，B，F(xiàn)4、偽代碼、偽代碼:min_support為最小支持度為最小支持度L1= 找頻繁找頻繁1_項集；項集；for (k = 2; Lk !=; k+) Ck= 由由 Lk-1生成候補集合；生成候補集合； for each t Ck 計算計算t在數據集合中出現(xiàn)的次數；在數據集合中出現(xiàn)的次數； if (出現(xiàn)計數小于

10、出現(xiàn)計數小于min_support) 從從Ck中剔除；中剔除； Lk = Ck； return k Lk;5、關聯(lián)規(guī)則挖掘例，（要求最小支持數為、關聯(lián)規(guī)則挖掘例，（要求最小支持數為2）TID Items100 1 3 4200 2 3 5300 1 2 3 5400 2 5數據庫數據庫 D掃描掃描 Ditemset sup.1223334153C1itemsetsup1 211 321 512 322 53C23 52itemset1 21 31 52 32 53 5C2掃描掃描 DC3itemset2 3 5掃描掃描 DL3itemset sup2 3 52itemset sup.12233

11、353L1itemset sup1 322 322 533 52L26、可以產生哪些規(guī)則、可以產生哪些規(guī)則 前面的例子中，得到一個頻繁集前面的例子中，得到一個頻繁集 2，3，5，非空真子集有，非空真子集有2，3，5，2，3，2，5，3，5itemset sup.12233353L1itemset sup1 322 322 533 52L3itemset sup2 3 52L2規(guī)則：規(guī)則：2 3 3 5 53 3 2 2 5 55 5 2 2 3 32 2 3 3 5 52 2 5 5 3 33 3 5 5 2 2置信度：置信度：2/3=66%（2，3，5頻度頻度/2頻度）頻度）2/3=66%（

12、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 夠快了嗎夠快了嗎? 性能瓶頸性能瓶頸AprioriApriori算法的核心算法的核心: :用頻繁的用頻繁的( (k-k-1)_1)_項集生成項集生成候選候選的頻繁的頻繁 k k_ _項集項集用數據庫掃描和模式匹配計算候選集的支持度用數據庫掃描和模式匹配計算候選集的支持度AprioriApriori

13、 的瓶頸的瓶頸: : 候選集生成候選集生成巨大的候選集巨大的候選集: :10104 4 個頻繁個頻繁1 1_ _項集要生成項集要生成 10107 7 個候選個候選 2_2_項集項集要找尺寸為要找尺寸為100100的頻繁模式，如的頻繁模式，如 a a1 1, a, a2 2, , , a, a100100, , 你必須先產生你必須先產生2 2100 100 10 103030 個候選集（個候選集（1_1_項集）項集）多次掃描數據庫多次掃描數據庫： 如果最長的模式是如果最長的模式是n n的話，則需要的話，則需要n n次數據庫掃描次數據庫掃描為提高為提高AprioriApriori算法的性能，有許多

14、改進的算法。算法的性能，有許多改進的算法。8、如何在概念分層有效地挖掘多層關聯(lián)規(guī)則、如何在概念分層有效地挖掘多層關聯(lián)規(guī)則 一般采用自頂向下策略，由概念層一般采用自頂向下策略，由概念層1開始向下，到較低的開始向下，到較低的更特定的概念層，對每個概念層的頻繁集累加計數，直到不更特定的概念層，對每個概念層的頻繁集累加計數，直到不能再找到頻繁項集。能再找到頻繁項集。計算機計算機支持度支持度=10%臺式機臺式機支持度支持度=6%筆記本筆記本支持度支持度=4%層層1: minsup=5%層層2: minsup=5%非頻繁非頻繁 問題：問題：因為較低層次抽象的項不大可能像較高層次抽象的項因為較低層次抽象的項

15、不大可能像較高層次抽象的項出現(xiàn)得那么頻繁。如果最小支持度閥值設置的太高，可能丟出現(xiàn)得那么頻繁。如果最小支持度閥值設置的太高，可能丟掉出現(xiàn)在較低抽象層次中有意義的關聯(lián)規(guī)則。如果閥值設置掉出現(xiàn)在較低抽象層次中有意義的關聯(lián)規(guī)則。如果閥值設置太底，可能會出現(xiàn)在較高抽象層的無興趣的關聯(lián)規(guī)則。太底，可能會出現(xiàn)在較高抽象層的無興趣的關聯(lián)規(guī)則。對于所有層使用一致的最小支持度對于所有層使用一致的最小支持度8、如何在概念分層有效地挖掘多層關聯(lián)規(guī)則、如何在概念分層有效地挖掘多層關聯(lián)規(guī)則 一般采用自頂向下策略，由概念層一般采用自頂向下策略，由概念層1開始向下，到較低的開始向下，到較低的更特定的概念層，對每個概念層的頻

16、繁集累加計數，直到不更特定的概念層，對每個概念層的頻繁集累加計數，直到不能再找到頻繁項集。能再找到頻繁項集。對于所有層使用一致的最小支持度對于所有層使用一致的最小支持度在較低層使用遞減的最小支持度在較低層使用遞減的最小支持度計算機計算機支持度支持度=10%臺式機臺式機支持度支持度=6%筆記本筆記本支持度支持度=4%層層1: minsup=5%層層2: minsup=3%9、冗余的多層關聯(lián)規(guī)則處理、冗余的多層關聯(lián)規(guī)則處理 買筆記本買筆記本買打印機買打印機 支持度支持度=8%,=8%,置信度置信度=70% (1)=70% (1) 買買IBM筆記本筆記本買打印機買打印機 支持度支持度=2%,=2%,

17、置信度置信度=72% (2)=72% (2)規(guī)則規(guī)則2有用嗎？它提供了新穎的信息嗎？有用嗎？它提供了新穎的信息嗎？ 如果后一個具有較小一般性的規(guī)則，它不提供新的信息，應如果后一個具有較小一般性的規(guī)則，它不提供新的信息，應當刪除它！當刪除它！ 如果一個規(guī)則的祖先，它的支持度和置信度都接近于該規(guī)如果一個規(guī)則的祖先，它的支持度和置信度都接近于該規(guī)則的則的“期望期望”值，這個規(guī)則是冗余的。值，這個規(guī)則是冗余的。 從（從（1）的）的置信度置信度=70%=70%推斷：推斷： 買筆記本買筆記本同時買打印機的交易數同時買打印機的交易數/ /買筆記本交易數買筆記本交易數=70% IBM筆記本屬于筆記本，因此筆記

18、本屬于筆記本，因此置信度也應該在置信度也應該在70%70%左右。由左右。由（2)2)實際為實際為72%72%，基本無差異。，基本無差異。9、冗余的多層關聯(lián)規(guī)則處理、冗余的多層關聯(lián)規(guī)則處理 買筆記本買筆記本買打印機買打印機 支持度支持度=8%,=8%,置信度置信度=70% (1)=70% (1) 買買IBM筆記本筆記本買打印機買打印機 支持度支持度=2%,=2%,置信度置信度=72% (2)=72% (2)規(guī)則規(guī)則2有用嗎？它提供了新穎的信息嗎？有用嗎？它提供了新穎的信息嗎？ 如果后一個具有較小一般性的規(guī)則，它不提供新的信息，應如果后一個具有較小一般性的規(guī)則，它不提供新的信息，應當刪除它！當刪除

19、它！ 如果一個規(guī)則的祖先，它的支持度和置信度都接近于該規(guī)如果一個規(guī)則的祖先，它的支持度和置信度都接近于該規(guī)則的則的“期望期望”值，這個規(guī)則是冗余的。值，這個規(guī)則是冗余的。 從（從（1）的）的支持度支持度=8%=8%推斷：推斷： 買筆記本買筆記本同時買打印機的交易數同時買打印機的交易數/ /總交易數總交易數=8%，假定從，假定從數據集中還發(fā)現(xiàn)，數據集中還發(fā)現(xiàn)，IBM筆記本在占整個筆記本銷量的筆記本在占整個筆記本銷量的25%。 則：買則：買IBM筆記本的支持度應該為筆記本的支持度應該為8%*25%=2%， 由（由（2)2)實際為實際為2%2%，兩者相同。，兩者相同。結論：規(guī)則（結論：規(guī)則（2）不是

20、有趣的，因為它不提供有趣的信息。）不是有趣的，因為它不提供有趣的信息。10、關聯(lián)規(guī)則的相關分析、關聯(lián)規(guī)則的相關分析 強關聯(lián)規(guī)則不一定有趣強關聯(lián)規(guī)則不一定有趣%66%,40) ,() ,(置信度支持度影碟機計算機游戲xbuysxbuys 其實，規(guī)則是誤導，因為購買影碟機的可能性是其實，規(guī)則是誤導，因為購買影碟機的可能性是75%，比，比66%還大。事實是：計算機游戲和影碟機是負相關的。還大。事實是：計算機游戲和影碟機是負相關的。 A和和B的相關性：的相關性：)()()(BpApBApcorrABcorrAB: 1，正相關，每一個出現(xiàn)蘊涵另一個出現(xiàn)，正相關，每一個出現(xiàn)蘊涵另一個出現(xiàn) 例：在例：在10000個交易中，個交易中，6000個顧客交易包含計算機游戲，個顧客交易包含計算機游戲，7500個顧客交易包含影碟機，個顧客交易包含影碟機，4000個交易包