數(shù)據(jù)挖掘原理與算法03改

1、2022年2月2日星期三1第三章第三章 關(guān)聯(lián)規(guī)則挖掘理論和算法關(guān)聯(lián)規(guī)則挖掘理論和算法 內(nèi)容提要內(nèi)容提要n基本概念與解決方法 n經(jīng)典的頻繁項目集生成算法分析 nApriori算法的性能瓶頸問題nApriori的改進算法2022-2-22啤酒與尿布的故事說起 n按常規(guī)思維，尿布與啤酒風馬牛不相及，若不是借助數(shù)據(jù)挖掘技術(shù)對海量交易數(shù)據(jù)進行挖掘和分析，沃爾瑪是不可能發(fā)現(xiàn)數(shù)據(jù)內(nèi)在這一有價值的規(guī)律的。 2022-2-23n在一家超市里，有一個有趣的現(xiàn)象：尿布和啤酒赫然擺在一起出售。但是這個奇怪的舉措?yún)s使尿布和啤酒的銷量雙雙增加了。這不是一個笑話，而是發(fā)生在美國沃爾瑪連鎖店超市的真實案例，并一直為商家所津津

2、樂道。沃爾瑪擁有世界上最大的數(shù)據(jù)倉庫系統(tǒng)，為了能夠準確了解顧客在其門店的購買習慣，沃爾瑪對其顧客的購物行為進行購物籃分析，想知道顧客經(jīng)常一起購買的商品有哪些。沃爾瑪數(shù)據(jù)倉庫里集中了其各門店的詳細原始交易數(shù)據(jù)。在這些原始交易數(shù)據(jù)的基礎(chǔ)上，沃爾瑪利用數(shù)據(jù)挖掘方法對這些數(shù)據(jù)進行分析和挖掘。一個意外的發(fā)現(xiàn)是：跟尿布一起購買最多的商品竟是啤酒！經(jīng)過大量實際調(diào)查和分析，揭示了一個隱藏在尿布與啤酒背后的美國人的一種行為模式：在美國，一些年輕的父親下班后經(jīng)常要到超市去買嬰兒尿布，而他們中有30%40%的人同時也為自己買一些啤酒。產(chǎn)生這一現(xiàn)象的原因是：美國的太太們常叮囑她們的丈夫下班后為小孩買尿布，而丈夫們在買

3、尿布后又隨手帶回了他們喜歡的啤酒。2022-2-2數(shù)據(jù)倉庫與數(shù)據(jù)挖掘43.1 概述n關(guān)聯(lián)規(guī)則(Association Rule Mining)挖掘是數(shù)據(jù)挖掘中最活躍的研究方法之一n最早是由R.Agrawal等人提出的n其目的是為了發(fā)現(xiàn)超市交易數(shù)據(jù)庫中不同商品之間的關(guān)聯(lián)關(guān)系。n一個典型的關(guān)聯(lián)規(guī)則的例子是：70%購買了牛奶的顧客將傾向于同時購買面包。n經(jīng)典的關(guān)聯(lián)規(guī)則挖掘算法：Apriori算法和FP-growth算法 2022-2-253.2 引例n假定某超市銷售的商品包括：bread、bear、cake、cream、milk和tea 交易號交易號TID顧顧 客客 購購 買買 商商 品品Items

4、T1bread cream milk teaT2bread cream milkT3cake milkT4milk teaT5bread cake milkT6bread teaT7beer milk teaT8bread teaT9bread cream milk teaT10bread milk tea2022-2-2數(shù)據(jù)倉庫與數(shù)據(jù)挖掘63.2 引例n定義3.1 項目與項集n設(shè)I=i1,i2,im是m個不同項目的集合，每個ik(k=1，2，m)稱為一個項目(Item)。n項目的集合I稱為項目集合(Itemset)，簡稱為項集。其元素個數(shù)稱為項集的長度，長度為k的項集稱為k-項集(k-Ite

5、mset)。2022-2-2數(shù)據(jù)倉庫與數(shù)據(jù)挖掘73.2 引例n定義3.2 交易n每筆交易T(Transaction)是項集I上的一個子集，即TI，但通常TI。n對應(yīng)每一個交易有一個唯一的標識交易號，記作TIDn交易的全體構(gòu)成了交易數(shù)據(jù)庫D，或稱交易記錄集D，簡稱交易集D。n交易集D中包含交易的個數(shù)記為|D|。 2022-2-283.2 引例n定義3.3 項集的支持度n對于項集X，XI，設(shè)定count(XT)為交易集D中包含X的交易的數(shù)量n項集X的支持度support(X)就是項集X出現(xiàn)的概率，從而描述了X的重要性。 |D|T)count(Xsupport(X)2022-2-293.2 引例n定

6、義3.4 項集的最小支持度與頻繁集n發(fā)現(xiàn)關(guān)聯(lián)規(guī)則要求項集必須滿足的最小支持閾值，稱為項集的最小支持度(Minimum Support)，記為supmin。從統(tǒng)計意義上講，它表示用戶關(guān)心的關(guān)聯(lián)規(guī)則必須滿足的最低重要性。只有滿足最小支持度的項集才能產(chǎn)生關(guān)聯(lián)規(guī)則。n支持度大于或等于supmin的項集稱為頻繁項集，簡稱頻繁集，反之則稱為非頻繁集。通常k-項集如果滿足supmin，稱為k-頻繁集，記作Lk。2022-2-2103.2 引例n定義3.5 關(guān)聯(lián)規(guī)則n關(guān)聯(lián)規(guī)則(Association Rule)可以表示為一個蘊含式：n R：XY 2022-2-2113.2 引例n定義3.6 關(guān)聯(lián)規(guī)則的支持度n

7、對于關(guān)聯(lián)規(guī)則R：XY，其中XI,YI，并且XY=，規(guī)則R的的支持度(Support)是交易集中同時包含X和Y的交易數(shù)與所有交易數(shù)之比。 |D|Y)count(XY)support(X2022-2-2123.2 引例n定義3.8 關(guān)聯(lián)規(guī)則的最小支持度和最小可信度n關(guān)聯(lián)規(guī)則的最小支持度也就是衡量頻繁集的最小支持度(Minimum Support)，記為supmin，它用于衡量規(guī)則需要滿足的最低重要性。規(guī)則的最小可信度(Minimum Confidence)記為confmin，它表示關(guān)聯(lián)規(guī)則需要滿足的最低可靠性。2022-2-2133.2 引例n定義3.7 關(guān)聯(lián)規(guī)則的可信度n對于關(guān)聯(lián)規(guī)則R：XY，其

8、中XI,YI，并且XY=，規(guī)則R的可信度(Confidence)是指包含X和Y的交易數(shù)與包含X的交易數(shù)之比 support(X)Y)support(XY)(X confidence2022-2-214關(guān)聯(lián)規(guī)則的簡單例子 2022-2-215n顧客購買記錄的數(shù)據(jù)庫D，包含6個事務(wù)。項集I=網(wǎng)球拍,網(wǎng)球,運動鞋,羽毛球?？紤]關(guān)聯(lián)規(guī)則（頻繁二項集）：網(wǎng)球拍與網(wǎng)球，事務(wù)1,2,3,4,6包含網(wǎng)球拍，事務(wù)1,2,6同時包含網(wǎng)球拍和網(wǎng)球，支持度(XY)/D=0.5，置信度(XY)/X=0.6。若給定最小支持度 = 0.5，最小置信度 = 0.6，認為購買網(wǎng)球拍和購買網(wǎng)球之間存在關(guān)聯(lián)。 2022-2-216

9、3.2 引例n定義3.9 強關(guān)聯(lián)規(guī)則n如果規(guī)則XY滿足：s u p p o r t ( X Y ) s u p m i n 且confidence(XY)confmin，稱關(guān)聯(lián)規(guī)則XY為強關(guān)聯(lián)規(guī)則，否則稱關(guān)聯(lián)規(guī)則XY為弱關(guān)聯(lián)規(guī)則。在挖掘關(guān)聯(lián)規(guī)則時，產(chǎn)生的關(guān)聯(lián)規(guī)則要經(jīng)過supmin和confmin的衡量，篩選出來的強關(guān)聯(lián)規(guī)則才能用于指導(dǎo)商家的決策。2022年2月2日星期三17關(guān)聯(lián)規(guī)則挖掘基本過程n關(guān)聯(lián)規(guī)則挖掘問題可以劃分成兩個子問題：n1. 1. 發(fā)現(xiàn)頻繁項目集發(fā)現(xiàn)頻繁項目集: :通過用戶給定Minsupport ，尋找所有頻繁項目集或者最大頻繁項目集。n2 2生成關(guān)聯(lián)規(guī)則生成關(guān)聯(lián)規(guī)則: :通過

10、用戶給定Minconfidence ，在頻繁項目集中，尋找關(guān)聯(lián)規(guī)則。n第1個子問題是近年來關(guān)聯(lián)規(guī)則挖掘算法研究的重點。2022年2月2日星期三183.2 經(jīng)典的頻繁項目集生成算法分析n項目集空間理論n經(jīng)典的發(fā)現(xiàn)頻繁項目集算法經(jīng)典的發(fā)現(xiàn)頻繁項目集算法n關(guān)聯(lián)規(guī)則生成算法關(guān)聯(lián)規(guī)則生成算法2022年2月2日星期三193.2.1 項目集空間理論 nAgrawal等人建立了用于事務(wù)數(shù)據(jù)庫挖掘的項目集格空間理論（1993, Appriori 屬性）。n定理定理3-13-1（ Appriori 屬性1）. . 如果項目集X 是頻繁項目集，那么它的所有非空子集都是頻繁項目集。證明 設(shè)X是一個項目集，事務(wù)數(shù)據(jù)庫T

11、 中支持X 的元組數(shù)為s。對X的任一非空子集為Y，設(shè)T中支持Y的元組數(shù)為s1。根據(jù)項目集支持數(shù)的定義，很容易知道支持X 的元組一定支持Y，所以s1 s，即support（Y） support（X）。按假設(shè)：項目集X 是頻繁項目集，即support(X) minsupport，所以support（Y） support（X） minsupport，因此Y是頻繁項目集。n定理定理3-23-2（ Appriori 屬性2）. .如果項目集X 是非頻繁項目集，那么它的所有超集都是非頻繁項目集。證明 （略）2022年2月2日星期三203.2.2 3.2.2 經(jīng)典的發(fā)現(xiàn)頻繁項目集算法經(jīng)典的發(fā)現(xiàn)頻繁項目集算法

12、n1994年，Agrawal 等人提出了著名的Apriori 算法。n算法算法3-13-1 Apriori（發(fā)現(xiàn)頻繁項目集）（1） L1 = large 1-itemsets; /所有1-項目頻集（2） FOR （k=2; Lk-1; k+） DO BEGIN（3） Ck=apriori-gen（Lk-1）; / Ck是k-候選集（4） FOR all transactions tD DO BEGIN（5） Ct=subset（Ck，t）; / Ct是所有t包含的候選集元素（6） FOR all candidates c Ct DO（7） c.count+;（8） END（9） Lk=cCk

13、|c.countminsup_count（10） END（11） L= Lk; 2022年2月2日星期三21apriori-gen過程n算法apriori中調(diào)用了apriori-gen（Lk-1），是為了通過（k-1）-頻集產(chǎn)生K-侯選集。nhas_infrequent_subset（c， Lk-1），判斷c是否加入到k-侯選集中。（1） FOR all itemset p Lk-1 DO （2） FOR all itemset qLk-1 DO （3） IF p.item1=q.item1， ， p.itemk-2=q.itemk-2， p.itemk-1 1） THEN /generate

14、 rules with subsets of xm-1 as antecedents（7） genrules（lk， xm-1）;（8） END（9）END； 2022年2月2日星期三28Rule-generate算法例子nMinconfidence=80%序號lkxm-1confidencesupport規(guī)則（是否是強規(guī)則）123523100%50%235（是）2235267%50%235（否）3235367%50%325（否）42352567%50%253（否）5235567%50%523（否） 623535100%50%352（是）2022年2月2日星期三293.3 Apriori算法的

15、性能瓶頸問題nApriori作為經(jīng)典的頻繁項目集生成算法，在數(shù)據(jù)挖掘中具有里程碑的作用。nApriori算法有兩個致命的性能瓶頸:n1 1多次掃描事務(wù)數(shù)據(jù)庫，需要很大的多次掃描事務(wù)數(shù)據(jù)庫，需要很大的I/OI/O負載負載n對每次對每次k k循環(huán)，侯選集循環(huán)，侯選集C Ck k中的每個元素都必須通過掃描中的每個元素都必須通過掃描數(shù)據(jù)庫一次來驗證其是否加入數(shù)據(jù)庫一次來驗證其是否加入L Lk k。假如有一個頻繁大。假如有一個頻繁大項目集包含項目集包含1010個項的話，那么就至少需要掃描事務(wù)數(shù)個項的話，那么就至少需要掃描事務(wù)數(shù)據(jù)庫據(jù)庫1010遍。遍。n2 2可能產(chǎn)生龐大的侯選集可能產(chǎn)生龐大的侯選集n由由

16、L Lk-1k-1產(chǎn)生產(chǎn)生k-k-侯選集侯選集C Ck k是指數(shù)增長的，例如是指數(shù)增長的，例如10104 4個個1-1-頻頻繁項目集就有可能產(chǎn)生接近繁項目集就有可能產(chǎn)生接近10107 7個元素的個元素的2-2-侯選集。如侯選集。如此大的侯選集對時間和主存空間都是一種挑戰(zhàn)。此大的侯選集對時間和主存空間都是一種挑戰(zhàn)。2022年2月2日星期三303.4 Apriori的改進算法n基于數(shù)據(jù)分割的方法基于數(shù)據(jù)分割的方法n基于散列的方法基于散列的方法2022年2月2日星期三313.4 提高Apriori算法效率的技術(shù)n一些算法雖然仍然遵循Apriori 屬性，但是由于引入了相關(guān)技術(shù)，在一定程度上改善了Ap

17、riori算法適應(yīng)性和效率。n主要的改進方法有：n基于數(shù)據(jù)分割（Partition）的方法：基本原理是“在一個劃分中的支持度小于最小支持度的k-項集不可能是全局頻繁的”。n基于散列（Hash）的方法：基本原理是“在一個hash桶內(nèi)支持度小于最小支持度的k-項集不可能是全局頻繁的”。n基于采樣（Sampling）的方法：基本原理是“通過采樣技術(shù)，評估被采樣的子集中，并依次來估計k-項集的全局頻度”。n其他：如，動態(tài)刪除沒有用的事務(wù)：“不包含任何Lk的事務(wù)對未來的掃描結(jié)果不會產(chǎn)生影響，因而可以刪除”。2022年2月2日星期三32基于數(shù)據(jù)分割的方法基于數(shù)據(jù)分割的方法n定理定理3-53-5 設(shè)數(shù)據(jù)集D

18、被分割成分塊D1， D2， ， Dn，全局最小支持數(shù)為minsup_count。如果一個數(shù)據(jù)分塊Di 的局部最小支持數(shù)minsup_counti （i=1，2，n），按著如下方法生成：minsup_counti= minsup_count *|Di| / |D|則所有的局部頻繁項目集涵蓋全局頻繁項目集。n作用：作用：n1 1合理利用主存空間：合理利用主存空間：數(shù)據(jù)分割將大數(shù)據(jù)集分成小的塊，為塊內(nèi)數(shù)據(jù)一次性導(dǎo)入主存提供機會。n2 2支持并行挖掘算法：支持并行挖掘算法：每個分塊的局部頻繁項目集是獨立生成的，因此提供了開發(fā)并行數(shù)據(jù)挖掘算法的良好機制。2022年2月2日星期三33基于散列的方法基于散列

19、的方法n1995，Park等發(fā)現(xiàn)尋找頻繁項目集的主要計算是在生成2-頻繁項目集上。因此，Park等利用了這個性質(zhì)引入雜湊技術(shù)來改進產(chǎn)生2-頻繁項目集的方法。n例子：桶地址桶地址 =（10 x+y10 x+y）mod 7mod 7；minsupport_count=3minsupport_count=3 TID Items1 I1，I2，I52 I2，I43 I2，I34 I1，I2，I45 I1，I36 I2，I37 I1，I38 I1，I2，I3，I59 I1，I2，I3桶地址 0 1 2 3 4 5 6桶計數(shù) 2 2 4 2 2 4 4桶內(nèi) I1，I4 I1，I5 I2，I3 I2，I4

20、I2，I5 I1，I2 I1，I3 I3，I5 I1，I5 I2，I3 I2，I4 I2，I5 I1，I2 I1，I3 I2，I3 I1，I2 I1，I3 I2，I3 I1，I2 I1，I3L2=I2，I3 ， I1，I2 ， I1，I3 2022年2月2日星期三34第三章第三章 關(guān)聯(lián)規(guī)則挖掘理論和算法關(guān)聯(lián)規(guī)則挖掘理論和算法 內(nèi)容提要內(nèi)容提要3.5 對項目集格空間理論的發(fā)展nCloseClose算法算法nFP-treeFP-tree算法算法2022年2月2日星期三35探索新的理論n隨著數(shù)據(jù)庫容量的增大，重復(fù)訪問數(shù)據(jù)庫（外存）將導(dǎo)致性能低下。因此，探索新的理論和算法來減少數(shù)據(jù)庫的掃描次數(shù)和侯選集

21、空間占用，已經(jīng)成為近年來關(guān)聯(lián)規(guī)則挖掘研究的熱點之一。n兩個典型的方法：nClose算法 nFP-tree算法 2022年2月2日星期三36CloseClose算法對應(yīng)的原理算法對應(yīng)的原理n一個頻繁閉合項目集的所有閉合子集一定是頻繁的；一個非頻繁閉合項目集的所有閉合超集一定是非頻繁的。n什么是一個閉合的項目集？n一個項目集C是閉合的，當且僅當對于在C中的任何元素，不可能在C中存在小于或等于它的支持度的子集。n例如，C1=AB3，ABC2是閉合的； C2=AB2，ABC2不是閉合的； 2022年2月2日星期三37CloseClose算法的例子算法的例子n下面是Close算法作用到表4-1數(shù)據(jù)集的執(zhí)

22、行過程（假如minsup_count=3）：n掃描數(shù)據(jù)庫得到L1=(A,3), (B,5), (C,4), (D,3), (E,3)；相應(yīng)關(guān)閉項目集為 Cl (A)=ABC,3，Cl (B)=B,5，Cl (C)=BC,4，Cl (D)=BD,3，Cl(E)=BE,3 ；nL2=(AB,3), (AC,3), (BC,4), (BD,3), (BE,3)；相應(yīng)關(guān)閉集為C2 (AB)=ABC,3； nL3，L4，L5不用測，于是頻繁大項集為ABC 。樣本數(shù)據(jù)庫TIDItemset1 A，B，C，D2B，C，E3A，B，C，E4B，D，E5A ， B ， C ， D2022年2月2日星期三38FP

23、-treeFP-tree算法的基本原理算法的基本原理n進行2次數(shù)據(jù)庫掃描：一次對所有1-項目的頻度排序；一次將數(shù)據(jù)庫信息轉(zhuǎn)變成緊縮內(nèi)存結(jié)構(gòu)。n不使用侯選集，直接壓縮數(shù)據(jù)庫成一個頻繁模式樹，通過頻繁模式樹可以直接得到頻集。n基本步驟是：n兩次掃描數(shù)據(jù)庫，生成頻繁模式樹FP-Tree：n掃描數(shù)據(jù)庫一次，得到所有掃描數(shù)據(jù)庫一次，得到所有1-1-項目的頻度排序表項目的頻度排序表T T；n依照依照T T，再掃描數(shù)據(jù)庫，得到，再掃描數(shù)據(jù)庫，得到FP-TreeFP-Tree。n使用FP-Tree，生成頻集：n為為FP-treeFP-tree中的每個節(jié)點生成條件模式庫；中的每個節(jié)點生成條件模式庫；n用條件模式庫構(gòu)造對應(yīng)的條件用條件模式庫構(gòu)造對應(yīng)的條件FP-treeFP-tree；n遞歸挖掘條件遞歸挖掘條件FP-treesFP-trees同時增長其包含的頻繁集：同時增長其包含的頻繁集：n如果條件FP-tree只包含一個路徑，則直接生成所包含的頻繁集。 2022年2月2日星期三39生成頻繁模式樹FP-Treef:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1TItem frequency head f4c4a3b3m3p3min_support = 0.5TID