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

數(shù)據(jù)挖掘原理與算法03第一頁，共32頁。關(guān)聯(lián)規(guī)則挖掘（AssociationRuleMining）是數(shù)據(jù)挖掘中研究較早而且至今仍活躍的研究方法之一。最早是由Agrawal等人提出的（1993）。最初提出的動機(jī)是針對購物籃分析（BasketAnalysis）問題提出的，其目的是為了發(fā)現(xiàn)交易數(shù)據(jù)庫（TransactionDatabase）中不同商品之間的聯(lián)系規(guī)則。關(guān)聯(lián)規(guī)則的挖掘工作成果頗豐。例如，關(guān)聯(lián)規(guī)則的挖掘理論、算法設(shè)計(jì)、算法的性能以及應(yīng)用推廣、并行關(guān)聯(lián)規(guī)則挖掘（ParallelAssociationRuleMining）以及數(shù)量關(guān)聯(lián)規(guī)則挖掘（QuantitiveAssociationRuleMining）等。關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘的其他研究分支的基礎(chǔ)。3.1基本概念與解決方法2023/4/182第二頁，共32頁。3.1基本概念與解決方法事務(wù)數(shù)據(jù)庫設(shè)I={i1，i2，…，im}是一個(gè)項(xiàng)目集合，事務(wù)數(shù)據(jù)庫D={t1，t2，…，tn}是由一系列具有唯一標(biāo)識TID的事務(wù)組成，每個(gè)事務(wù)ti（i=1，2，…，n）都對應(yīng)I上的一個(gè)子集。一個(gè)事務(wù)數(shù)據(jù)庫可以用來刻畫：購物記錄：I是全部物品集合，D是購物清單，每個(gè)元組ti是一次購買物品的集合（它當(dāng)然是I的一個(gè)子集）。其它應(yīng)用問題2023/4/183第三頁，共32頁。支持度與頻繁項(xiàng)目集定義3-1（項(xiàng)目集的支持度）.給定一個(gè)全局項(xiàng)目集I和數(shù)據(jù)庫D，一個(gè)項(xiàng)目集I1I在D上的支持度（Support）是包含I1的事務(wù)在D中所占的百分比：support（I1

）=||{tD|I1

t}||/||D||。定義3-2（頻繁項(xiàng)目集）.給定全局項(xiàng)目集I和數(shù)據(jù)庫D，D中所有滿足用戶指定的最小支持度（Minsupport）的項(xiàng)目集，即大于或等于minsupport的I的非空子集，稱為頻繁項(xiàng)目集（頻集：FrequentItemsets）或者大項(xiàng)目集（LargeIitemsets）。在頻繁項(xiàng)目集中挑選出所有不被其他元素包含的頻繁項(xiàng)目集稱為最大頻繁項(xiàng)目集（最大頻集：MaximumFrequentItemsets）或最大大項(xiàng)目集（MaximumLargeIitemsets）。2023/4/184第四頁，共32頁?？尚哦扰c關(guān)聯(lián)規(guī)則定義3-3（關(guān)聯(lián)規(guī)則與可信度）.給定一個(gè)全局項(xiàng)目集I和數(shù)據(jù)庫D，一個(gè)定義在I和D上的關(guān)聯(lián)規(guī)則形如I1I2，并且它的可信度或信任度或置信度（Confidence）是指包含I1和I2的事務(wù)數(shù)與包含I1的事務(wù)數(shù)之比，即Confidence（I1I2）=support（I1∪I2）/support（I1），其中I1，I2I，I1∩I2=Ф。定義3-4（強(qiáng)關(guān)聯(lián)規(guī)則）.

D在I上滿足最小支持度和最小信任度（Minconfidence）的關(guān)聯(lián)規(guī)則稱為強(qiáng)關(guān)聯(lián)規(guī)則（StrongAssociationRule）。2023/4/185第五頁，共32頁。關(guān)聯(lián)規(guī)則挖掘基本過程關(guān)聯(lián)規(guī)則挖掘問題可以劃分成兩個(gè)子問題：1.發(fā)現(xiàn)頻繁項(xiàng)目集:通過用戶給定Minsupport，尋找所有頻繁項(xiàng)目集或者最大頻繁項(xiàng)目集。2．生成關(guān)聯(lián)規(guī)則:通過用戶給定Minconfidence，在頻繁項(xiàng)目集中，尋找關(guān)聯(lián)規(guī)則。第1個(gè)子問題是近年來關(guān)聯(lián)規(guī)則挖掘算法研究的重點(diǎn)。2023/4/186第六頁，共32頁。3.2經(jīng)典的頻繁項(xiàng)目集生成算法分析項(xiàng)目集空間理論經(jīng)典的發(fā)現(xiàn)頻繁項(xiàng)目集算法關(guān)聯(lián)規(guī)則生成算法2023/4/187第七頁，共32頁。3.2.1項(xiàng)目集空間理論Agrawal等人建立了用于事務(wù)數(shù)據(jù)庫挖掘的項(xiàng)目集格空間理論（1993,Appriori屬性）。定理3-1（Appriori屬性1）.

如果項(xiàng)目集X是頻繁項(xiàng)目集，那么它的所有非空子集都是頻繁項(xiàng)目集。證明設(shè)X是一個(gè)項(xiàng)目集，事務(wù)數(shù)據(jù)庫T中支持X的元組數(shù)為s。對X的任一非空子集為Y，設(shè)T中支持Y的元組數(shù)為s1。根據(jù)項(xiàng)目集支持?jǐn)?shù)的定義，很容易知道支持X的元組一定支持Y，所以s1≥s，即support（Y）≥support（X）。按假設(shè)：項(xiàng)目集X是頻繁項(xiàng)目集，即support(X)≥minsupport，所以support（Y）≥support（X）≥minsupport，因此Y是頻繁項(xiàng)目集。□定理3-2（Appriori屬性2）.如果項(xiàng)目集X是非頻繁項(xiàng)目集，那么它的所有超集都是非頻繁項(xiàng)目集。證明（略）2023/4/188第八頁，共32頁。3.2.2經(jīng)典的發(fā)現(xiàn)頻繁項(xiàng)目集算法1994年，Agrawal等人提出了著名的Apriori算法。算法3-1Apriori（發(fā)現(xiàn)頻繁項(xiàng)目集）（1）L1={large1-itemsets};//所有1-項(xiàng)目頻集（2）FOR（k=2;Lk-1;k++）DOBEGIN（3）Ck=apriori-gen（Lk-1）;//Ck是k-候選集（4）FORalltransactionstDDOBEGIN（5）Ct=subset（Ck，t）;//Ct是所有t包含的候選集元素（6）FORallcandidatescCtDO（7）c.count++;（8）END（9）Lk={cCk|c.countminsup_count}（10）END（11）L=Lk;

2023/4/189第九頁，共32頁。apriori-gen過程算法apriori中調(diào)用了apriori-gen（Lk-1），是為了通過（k-1）-頻集產(chǎn)生K-侯選集。has_infrequent_subset（c，Lk-1），判斷c是否加入到k-侯選集中。（1）FORallitemsetpLk-1DO（2）FORallitemsetqLk-1DO（3）IFp.item1=q.item1，…，p.itemk-2=q.itemk-2，p.itemk-1<q.itemk-1THENBEGIN（4）c=p∞q;//把q的第k-1個(gè)元素連到p后（5）IF

has_infrequent_subset（c，Lk-1）THEN（6）deletec;//刪除含有非頻繁項(xiàng)目子集的侯選元素（7）ELSEaddctoCk;（8）END（9）ReturnCk;2023/4/1810第十頁，共32頁。發(fā)現(xiàn)算法解決的是關(guān)聯(lián)規(guī)則挖掘的第一個(gè)問題關(guān)聯(lián)規(guī)則分為布爾關(guān)聯(lián)規(guī)則和多值規(guī)則多值關(guān)聯(lián)規(guī)則都轉(zhuǎn)化為布爾關(guān)聯(lián)規(guī)則來解決，因此先介紹布爾關(guān)聯(lián)規(guī)則算法Apriori，AprioriTid2023/4/1811第十一頁，共32頁。Apriori算法分析分為第一次遍歷和第k次遍歷第一次遍歷計(jì)算每個(gè)項(xiàng)目的具體值，確定大項(xiàng)目集1項(xiàng)目集L1

第k次遍歷利用前一次找到的大項(xiàng)集Lk-1

和Apriori-gen函數(shù)產(chǎn)生候選集Ck，然后掃描數(shù)據(jù)庫，得到Ck

中候選的支持度，剔除了不合格的候選后Ck作為Lk2023/4/1812第十二頁，共32頁。例3-1下表給出一個(gè)樣本事務(wù)數(shù)據(jù)庫，并對它實(shí)施Apriori算法。TIDItemsetTIDItemset123A,B,C,DB,C,EA,B,C,E45B,D,EA,B,C,D2023/4/1813第十三頁，共32頁。Apriori算法例子Minsupport=40%DatabaseDScanDC1L1L2C2C2ScanDC3L3ScanD2023/4/1814第十四頁，共32頁。3.2.3關(guān)聯(lián)規(guī)則生成算法根據(jù)上面介紹的關(guān)聯(lián)規(guī)則挖掘的兩個(gè)步驟，在得到了所有頻繁項(xiàng)目集后，可以按照下面的步驟生成關(guān)聯(lián)規(guī)則：對于每一個(gè)頻繁項(xiàng)目集l，生成其所有的非空子集；對于l

的每一個(gè)非空子集x，計(jì)算Conference（x），如果Confidence（x）≥minconfidence，那么“x（l-x）”成立。算法3-4

從給定的頻繁項(xiàng)目集中生成強(qiáng)關(guān)聯(lián)規(guī)則算法3-4的核心是genrules遞歸過程，它實(shí)現(xiàn)一個(gè)頻繁項(xiàng)目集中所有強(qiáng)關(guān)聯(lián)規(guī)則的生成。Rule-generate（L，minconf）（1）FOReachfrequentitemsetlkinL（2）genrules（lk

，lk）;2023/4/1815第十五頁，共32頁。算法-遞歸測試一個(gè)頻集中的關(guān)聯(lián)規(guī)則算法3-5遞歸測試一個(gè)頻集中的關(guān)聯(lián)規(guī)則genrules（lk:frequentk-itemset，xm:frequentm-itemset）（1）X={（m-1）-itemsetsxm-1|xm-1inxm}；（2）FOReachxm-1inXBEGIN（3）conf=support（lk）/support（xm-1）;（4）IF（conf≥minconf）THENBEGIN（5）printtherule“xm-1（

lk-xm-1），withsupport=support（lk），confidence=conf”;（6）IF（m-1>1）THEN//generateruleswithsubsetsofxm-1asantecedents（7）genrules（lk，

xm-1）;（8）END（9）END；2023/4/1816第十六頁，共32頁。Rule-generate算法例子Minconfidence=80%序號 lk xm-1 confidence support 規(guī)則（是否是強(qiáng)規(guī)則） 1 235 23 100% 50% 235（是） 2 235 2 67% 50% 235（否） 3 235 3 67% 50% 325（否） 4 235 25 67% 50% 253（否） 5 235 5 67% 50% 523（否）

6 235 35 100% 50% 352（是） 2023/4/1817第十七頁，共32頁。3.3Apriori算法的性能瓶頸問題Apriori作為經(jīng)典的頻繁項(xiàng)目集生成算法，在數(shù)據(jù)挖掘中具有里程碑的作用。Apriori算法有兩個(gè)致命的性能瓶頸:1．多次掃描事務(wù)數(shù)據(jù)庫，需要很大的I/O負(fù)載對每次k循環(huán)，侯選集Ck中的每個(gè)元素都必須通過掃描數(shù)據(jù)庫一次來驗(yàn)證其是否加入Lk。假如有一個(gè)頻繁大項(xiàng)目集包含10個(gè)項(xiàng)的話，那么就至少需要掃描事務(wù)數(shù)據(jù)庫10遍。2．可能產(chǎn)生龐大的侯選集由Lk-1產(chǎn)生k-侯選集Ck是指數(shù)增長的，例如104個(gè)1-頻繁項(xiàng)目集就有可能產(chǎn)生接近107個(gè)元素的2-侯選集。如此大的侯選集對時(shí)間和主存空間都是一種挑戰(zhàn)。2023/4/1818第十八頁，共32頁。3.4Apriori的改進(jìn)算法基于數(shù)據(jù)分割的方法基于散列的方法2023/4/1819第十九頁，共32頁。3.4提高Apriori算法效率的技術(shù)一些算法雖然仍然遵循Apriori屬性，但是由于引入了相關(guān)技術(shù)，在一定程度上改善了Apriori算法適應(yīng)性和效率。主要的改進(jìn)方法有：基于數(shù)據(jù)分割（Partition）的方法：基本原理是“在一個(gè)劃分中的支持度小于最小支持度的k-項(xiàng)集不可能是全局頻繁的”?；谏⒘校℉ash）的方法：基本原理是“在一個(gè)hash桶內(nèi)支持度小于最小支持度的k-項(xiàng)集不可能是全局頻繁的”?；诓蓸樱⊿ampling）的方法：基本原理是“通過采樣技術(shù)，評估被采樣的子集中，并依次來估計(jì)k-項(xiàng)集的全局頻度”。其他：如，動態(tài)刪除沒有用的事務(wù)：“不包含任何Lk的事務(wù)對未來的掃描結(jié)果不會產(chǎn)生影響，因而可以刪除”。2023/4/1820第二十頁，共32頁?；跀?shù)據(jù)分割的方法定理3-5

設(shè)數(shù)據(jù)集D被分割成分塊D1，D2，…，Dn，全局最小支持?jǐn)?shù)為minsup_count。如果一個(gè)數(shù)據(jù)分塊Di

的局部最小支持?jǐn)?shù)minsup_counti（i=1，2，…，n），按著如下方法生成：minsup_counti=minsup_count*||Di||/||D||則所有的局部頻繁項(xiàng)目集涵蓋全局頻繁項(xiàng)目集。作用：1．合理利用主存空間：數(shù)據(jù)分割將大數(shù)據(jù)集分成小的塊，為塊內(nèi)數(shù)據(jù)一次性導(dǎo)入主存提供機(jī)會。2．支持并行挖掘算法：每個(gè)分塊的局部頻繁項(xiàng)目集是獨(dú)立生成的，因此提供了開發(fā)并行數(shù)據(jù)挖掘算法的良好機(jī)制。2023/4/1821第二十一頁，共32頁。基于散列的方法1995，Park等發(fā)現(xiàn)尋找頻繁項(xiàng)目集的主要計(jì)算是在生成2-頻繁項(xiàng)目集上。因此，Park等利用了這個(gè)性質(zhì)引入雜湊技術(shù)來改進(jìn)產(chǎn)生2-頻繁項(xiàng)目集的方法。例子：桶地址

=（10x+y）mod7；minsupport_count=3

TIDItems 1I1，I2，I52I2，I4

3I2，I3

4I1，I2，I45I1，I3

6I2，I3

7I1，I3

8I1，I2，I3，I59I1，I2，I3 桶地址0 12 3456桶計(jì)數(shù)2 24 2244桶內(nèi){I1，I4}{I1，I5}{I2，I3}{I2，I4}{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，I3}L2={{I2，I3}，{I1，I2}，{I1，I3}}2023/4/1822第二十二頁，共32頁。第三章關(guān)聯(lián)規(guī)則挖掘理論和算法

內(nèi)容提要3.5對項(xiàng)目集格空間理論的發(fā)展Close算法FP-tree算法2023/4/1823第二十三頁，共32頁。探索新的理論隨著數(shù)據(jù)庫容量的增大，重復(fù)訪問數(shù)據(jù)庫（外存）將導(dǎo)致性能低下。因此，探索新的理論和算法來減少數(shù)據(jù)庫的掃描次數(shù)和侯選集空間占用，已經(jīng)成為近年來關(guān)聯(lián)規(guī)則挖掘研究的熱點(diǎn)之一。兩個(gè)典型的方法：Close算法FP-tree算法2023/4/1824第二十四頁，共32頁。Close算法對應(yīng)的原理一個(gè)頻繁閉合項(xiàng)目集的所有閉合子集一定是頻繁的；一個(gè)非頻繁閉合項(xiàng)目集的所有閉合超集一定是非頻繁的。什么是一個(gè)閉合的項(xiàng)目集？一個(gè)項(xiàng)目集C是閉合的，當(dāng)且僅當(dāng)對于在C中的任何元素，不可能在C中存在小于或等于它的支持度的子集。例如，C1={AB3，ABC2}是閉合的；C2={AB2，ABC2}不是閉合的；

2023/4/1825第二十五頁，共32頁。Close算法的例子下面是Close算法作用到表4-1數(shù)據(jù)集的執(zhí)行過程（假如minsup_count=3）：掃描數(shù)據(jù)庫得到L1={(A,3),(B,5),(C,4),(D,3),(E,3)}；相應(yīng)關(guān)閉項(xiàng)目集為Cl(A)={ABC,3}，Cl(B)={B,5}，Cl(C)={BC,4}，Cl(D)={BD,3}，Cl(E)={BE,3}；L2={(AB,3),(AC,3),(BC,4),(BD,3),(BE,3)}；相應(yīng)關(guān)閉集為C2(AB)={ABC,3}；L3，L4，L5不用測，于是頻繁大項(xiàng)集為{ABC}。樣本數(shù)據(jù)庫TID Itemset 1 A，B，C，D2 B，C，E3 A，B，C，E4 B，D，E5 A，B，C，D 2023/4/1826第二十六頁，共32頁。FP-tree算法的基本原理進(jìn)行2次數(shù)據(jù)庫掃描：一次對所有1-項(xiàng)目的頻度排序；一次將數(shù)據(jù)庫信息轉(zhuǎn)變成緊縮內(nèi)存結(jié)構(gòu)。不使用侯選集，直接壓縮數(shù)據(jù)庫成一個(gè)頻繁模式樹，通過頻繁模式樹可以直接得到頻集?；静襟E是：兩次掃描數(shù)據(jù)庫，生成頻繁模式樹FP-Tree：掃描數(shù)據(jù)庫一次，得到所有1-項(xiàng)目的頻度排序表T；依照T，再掃描數(shù)據(jù)庫，得到FP-Tree。使用FP-Tree，生成頻集：為FP-tree中的每個(gè)節(jié)點(diǎn)生成條件模式庫；用條件模式庫構(gòu)造對應(yīng)的條件FP-tree；遞歸挖掘條件FP-trees同時(shí)增長其包含的頻繁集：如果條件FP-tree只包含一個(gè)路徑，則直接生成所包含的頻繁集。2023/4/1827第二十七頁，共32頁。生成頻繁模式樹FP-Tree{}f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1TItemfrequencyheadf 4c 4a 3b 3m 3p 3min_support=0.5TID OriginalItems (ordered)frequentitems100 {f,a,c,d,g,i,m,p}

{f,c,a,m,p}2