數(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)典的頻繁項(xiàng)目集生成算法分析 nApriori算法的性能瓶頸問(wèn)題nApriori的改進(jìn)算法2022-2-22啤酒與尿布的故事說(shuō)起 n按常規(guī)思維，尿布與啤酒風(fēng)馬牛不相及，若不是借助數(shù)據(jù)挖掘技術(shù)對(duì)海量交易數(shù)據(jù)進(jìn)行挖掘和分析，沃爾瑪是不可能發(fā)現(xiàn)數(shù)據(jù)內(nèi)在這一有價(jià)值的規(guī)律的。 2022-2-23n在一家超市里，有一個(gè)有趣的現(xiàn)象：尿布和啤酒赫然擺在一起出售。但是這個(gè)奇怪的舉措?yún)s使尿布和啤酒的銷(xiāo)量雙雙增加了。這不是一個(gè)笑話，而是發(fā)生在美國(guó)沃爾瑪連鎖店超市的真實(shí)案例，并一直為商家所津津

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

3、尿布后又隨手帶回了他們喜歡的啤酒。2022-2-2數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘43.1 概述n關(guān)聯(lián)規(guī)則(Association Rule Mining)挖掘是數(shù)據(jù)挖掘中最活躍的研究方法之一n最早是由R.Agrawal等人提出的n其目的是為了發(fā)現(xiàn)超市交易數(shù)據(jù)庫(kù)中不同商品之間的關(guān)聯(lián)關(guān)系。n一個(gè)典型的關(guān)聯(lián)規(guī)則的例子是：70%購(gòu)買(mǎi)了牛奶的顧客將傾向于同時(shí)購(gòu)買(mǎi)面包。n經(jīng)典的關(guān)聯(lián)規(guī)則挖掘算法：Apriori算法和FP-growth算法 2022-2-253.2 引例n假定某超市銷(xiāo)售的商品包括：bread、bear、cake、cream、milk和tea 交易號(hào)交易號(hào)TID顧顧 客客 購(gòu)購(gòu) 買(mǎi)買(mǎi) 商商 品品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ù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘63.2 引例n定義3.1 項(xiàng)目與項(xiàng)集n設(shè)I=i1,i2,im是m個(gè)不同項(xiàng)目的集合，每個(gè)ik(k=1，2，m)稱(chēng)為一個(gè)項(xiàng)目(Item)。n項(xiàng)目的集合I稱(chēng)為項(xiàng)目集合(Itemset)，簡(jiǎn)稱(chēng)為項(xiàng)集。其元素個(gè)數(shù)稱(chēng)為項(xiàng)集的長(zhǎng)度，長(zhǎng)度為k的項(xiàng)集稱(chēng)為k-項(xiàng)集(k-Ite

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

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

7、對(duì)于關(guān)聯(lián)規(guī)則R：XY，其中XI,YI，并且XY=，規(guī)則R的的支持度(Support)是交易集中同時(shí)包含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ī)則需要滿(mǎn)足的最低重要性。規(guī)則的最小可信度(Minimum Confidence)記為confmin，它表示關(guān)聯(lián)規(guī)則需要滿(mǎn)足的最低可靠性。2022-2-2133.2 引例n定義3.7 關(guān)聯(lián)規(guī)則的可信度n對(duì)于關(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ī)則的簡(jiǎn)單例子 2022-2-215n顧客購(gòu)買(mǎi)記錄的數(shù)據(jù)庫(kù)D，包含6個(gè)事務(wù)。項(xiàng)集I=網(wǎng)球拍,網(wǎng)球,運(yùn)動(dòng)鞋,羽毛球?？紤]關(guān)聯(lián)規(guī)則（頻繁二項(xiàng)集）：網(wǎng)球拍與網(wǎng)球，事務(wù)1,2,3,4,6包含網(wǎng)球拍，事務(wù)1,2,6同時(shí)包含網(wǎng)球拍和網(wǎng)球，支持度(XY)/D=0.5，置信度(XY)/X=0.6。若給定最小支持度 = 0.5，最小置信度 = 0.6，認(rèn)為購(gòu)買(mǎi)網(wǎng)球拍和購(gòu)買(mǎi)網(wǎng)球之間存在關(guān)聯(lián)。 2022-2-216

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

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

11、 中支持X 的元組數(shù)為s。對(duì)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)目集。n定理定理3-23-2（ Appriori 屬性2）. .如果項(xiàng)目集X 是非頻繁項(xiàng)目集，那么它的所有超集都是非頻繁項(xiàng)目集。證明 （略）2022年2月2日星期三203.2.2 3.2.2 經(jīng)典的發(fā)現(xiàn)頻繁項(xiàng)目集算法經(jīng)典的發(fā)現(xiàn)頻繁項(xiàng)目集算法

12、n1994年，Agrawal 等人提出了著名的Apriori 算法。n算法算法3-13-1 Apriori（發(fā)現(xiàn)頻繁項(xiàng)目集）（1） L1 = large 1-itemsets; /所有1-項(xiàng)目頻集（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過(guò)程n算法apriori中調(diào)用了apriori-gen（Lk-1），是為了通過(guò)（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%序號(hào)lkxm-1confidencesupport規(guī)則（是否是強(qiáng)規(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、性能瓶頸問(wèn)題nApriori作為經(jīng)典的頻繁項(xiàng)目集生成算法，在數(shù)據(jù)挖掘中具有里程碑的作用。nApriori算法有兩個(gè)致命的性能瓶頸:n1 1多次掃描事務(wù)數(shù)據(jù)庫(kù)，需要很大的多次掃描事務(wù)數(shù)據(jù)庫(kù)，需要很大的I/OI/O負(fù)載負(fù)載n對(duì)每次對(duì)每次k k循環(huán)，侯選集循環(huán)，侯選集C Ck k中的每個(gè)元素都必須通過(guò)掃描中的每個(gè)元素都必須通過(guò)掃描數(shù)據(jù)庫(kù)一次來(lái)驗(yàn)證其是否加入數(shù)據(jù)庫(kù)一次來(lái)驗(yàn)證其是否加入L Lk k。假如有一個(gè)頻繁大。假如有一個(gè)頻繁大項(xiàng)目集包含項(xiàng)目集包含1010個(gè)項(xiàng)的話，那么就至少需要掃描事務(wù)數(shù)個(gè)項(xiàng)的話，那么就至少需要掃描事務(wù)數(shù)據(jù)庫(kù)據(jù)庫(kù)1010遍。遍。n2 2可能產(chǎn)生龐大的侯選集可能產(chǎn)生龐大的侯選集n由由

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

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

18、被分割成分塊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)目集。n作用：作用：n1 1合理利用主存空間：合理利用主存空間：數(shù)據(jù)分割將大數(shù)據(jù)集分成小的塊，為塊內(nèi)數(shù)據(jù)一次性導(dǎo)入主存提供機(jī)會(huì)。n2 2支持并行挖掘算法：支持并行挖掘算法：每個(gè)分塊的局部頻繁項(xiàng)目集是獨(dú)立生成的，因此提供了開(kāi)發(fā)并行數(shù)據(jù)挖掘算法的良好機(jī)制。2022年2月2日星期三33基于散列的方法基于散列

19、的方法n1995，Park等發(fā)現(xiàn)尋找頻繁項(xiàng)目集的主要計(jì)算是在生成2-頻繁項(xiàng)目集上。因此，Park等利用了這個(gè)性質(zhì)引入雜湊技術(shù)來(lái)改進(jìn)產(chǎn)生2-頻繁項(xiàng)目集的方法。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桶計(jì)數(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 對(duì)項(xiàng)目集格空間理論的發(fā)展nCloseClose算法算法nFP-treeFP-tree算法算法2022年2月2日星期三35探索新的理論n隨著數(shù)據(jù)庫(kù)容量的增大，重復(fù)訪問(wèn)數(shù)據(jù)庫(kù)（外存）將導(dǎo)致性能低下。因此，探索新的理論和算法來(lái)減少數(shù)據(jù)庫(kù)的掃描次數(shù)和侯選集

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

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

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