智能推薦2---關(guān)聯(lián)分析

1、主講 張榮梅2014.10數(shù)據(jù)挖掘?qū)д撽P(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘算法功能根據(jù)所挖掘知識(shí)的類(lèi)型不同：為了反映事物之間依賴(lài)或關(guān)聯(lián)的為了反映事物之間依賴(lài)或關(guān)聯(lián)的為了反映同類(lèi)事物共同性質(zhì)的為了反映事物各方面特征的為了反映不同事物之間屬性差別的根據(jù)歷史的和當(dāng)前的數(shù)據(jù)推測(cè)未來(lái)數(shù)據(jù)揭示事物偏離常規(guī)的異?，F(xiàn)象數(shù)據(jù)挖掘技術(shù)數(shù)據(jù)挖掘技術(shù)關(guān)聯(lián)（關(guān)聯(lián)（AssociationAssociation）分類(lèi)（分類(lèi)（ClassificationClassification）預(yù)測(cè)（預(yù)測(cè)（PredictionPrediction）聚類(lèi)（聚類(lèi)（ClusteringClustering）WebWeb挖掘技術(shù)挖掘技術(shù) 3 3 挖掘頻繁模式和關(guān)聯(lián)

2、規(guī)則挖掘頻繁模式和關(guān)聯(lián)規(guī)則3.1 基本概念3.2 Apriori算法3.3 其他算法概述 3.1 3.1 關(guān)聯(lián)的基本概念關(guān)聯(lián)的基本概念若兩個(gè)或多個(gè)變量的取值之間存在某種規(guī)律性，就稱(chēng)為關(guān)聯(lián)。關(guān)聯(lián)規(guī)則是尋找同一事件中出現(xiàn)的不同項(xiàng)的相關(guān)性，比如在一次購(gòu)買(mǎi)活動(dòng)中所購(gòu)買(mǎi)不同商品的相關(guān)性。關(guān)聯(lián)分析即利用關(guān)聯(lián)規(guī)則進(jìn)行數(shù)據(jù)挖掘。購(gòu)物籃模型 典型案例-啤酒與尿布啤酒與尿布在商業(yè)應(yīng)用中常用關(guān)聯(lián)分析最典型的例子就是一家連鎖店(沃爾瑪)通過(guò)數(shù)據(jù)挖掘發(fā)現(xiàn)了小孩尿布與啤酒之間有著內(nèi)在的聯(lián)系，即“啤酒與尿布啤酒與尿布”的故事。在美國(guó)，一些年輕(2535歲）的父親下班后經(jīng)常要到超市去買(mǎi)嬰兒尿布，超市也因此發(fā)現(xiàn)了一個(gè)規(guī)律，在購(gòu)

3、買(mǎi)嬰兒尿布的年輕父親們中，有3040%的人同時(shí)要買(mǎi)一些啤酒。超市隨后調(diào)整了貨架的擺放，把尿布與啤酒放在一起，明顯增加了銷(xiāo)售額。Customerbuys diaperCustomerbuys bothCustomerbuys beer“啤酒與尿布”的關(guān)聯(lián)規(guī)則更多舉例e.g： 在購(gòu)買(mǎi)鐵錘的顧客當(dāng)中，有70的人同時(shí)購(gòu)買(mǎi)了鐵釘。關(guān)聯(lián)的基本概念關(guān)聯(lián)的基本概念關(guān)聯(lián)關(guān)聯(lián) 自然界中某種事物發(fā)生時(shí)其他事物也會(huì)發(fā)生，則這種聯(lián)系稱(chēng)之為關(guān)聯(lián)。反映事件之間依賴(lài)或關(guān)聯(lián)的知識(shí)稱(chēng)為關(guān)聯(lián)型知識(shí)（又稱(chēng)依賴(lài)關(guān)系）。關(guān)聯(lián)的類(lèi)型關(guān)聯(lián)的類(lèi)型 分為簡(jiǎn)單關(guān)聯(lián)、時(shí)序關(guān)聯(lián)、因果關(guān)聯(lián)。關(guān)聯(lián)規(guī)則關(guān)聯(lián)規(guī)則 關(guān)聯(lián)是兩個(gè)或多個(gè)變量取值之間存在的一類(lèi)重要的

4、可被發(fā)現(xiàn)的某種規(guī)律性。關(guān)聯(lián)的基本概念關(guān)聯(lián)的基本概念關(guān)聯(lián)規(guī)則的數(shù)學(xué)定義關(guān)聯(lián)規(guī)則的數(shù)學(xué)定義 設(shè)I=i1, i2, .,im 是一個(gè)以m個(gè)不同項(xiàng)的集合，任務(wù)相關(guān)的數(shù)據(jù)D是數(shù)據(jù)庫(kù)事務(wù)（交易）的集合，其中每個(gè)事務(wù)T是針對(duì)I的項(xiàng)的集合，即每一筆交易包含若干個(gè)屬于I的項(xiàng)。關(guān)聯(lián)規(guī)則可表示為：X=YX=Y，其中，其中X,Y X,Y I I 且且 X X Y= Y= X稱(chēng)為規(guī)則的前提或前項(xiàng)，Y稱(chēng)為結(jié)果或后項(xiàng)。規(guī)則X=YX=Y在事務(wù)集D D中成立，具有支持度支持度s s，具有置信度置信度c.c. 有兩個(gè)度量標(biāo)準(zhǔn)：支持度(Support)和可信度(Confidence)。 規(guī)則的支持度s定義為D中事務(wù)包含X U Y

5、X U Y 的百分比，即概率百分比，即概率P(XP(X UY) Y) : support (X=Y) =support (X U Y)=P(Xsupport (X=Y) =support (X U Y)=P(X UY)Y) 規(guī)則的可信度c定義為D中包含X的事務(wù)同時(shí)也包含Y的百分比，即條件概率P(Y|X)。 confidence(X= Y)=support(X U Y)/support(X)=P(Y|X)關(guān)聯(lián)規(guī)則的形式關(guān)聯(lián)規(guī)則的形式 R: X= Y 其中，X及Y是兩個(gè)不相交的集合，即X,YI且X Y= 關(guān)聯(lián)規(guī)則可以理解為一個(gè)命題，即如果一個(gè)交易支持項(xiàng)集X，則它也以一定的可能性支持項(xiàng)集Y，這一可能

6、性稱(chēng)之為規(guī)則的可信度，記為conf(R)或C (R)規(guī)則形式舉例舉例Body Head support, confidencebuys(x, “diapers”) buys(x, “beers”) 2%, 60%major(x, “CS”) takes(x, “DB”) grade(x , “A”) 5%, 75%關(guān)聯(lián)規(guī)則挖掘應(yīng)用實(shí)例關(guān)聯(lián)規(guī)則挖掘應(yīng)用實(shí)例 通過(guò)發(fā)現(xiàn)顧客放入其購(gòu)物籃中不同商品之間的聯(lián)系，分析顧客的購(gòu)買(mǎi)習(xí)慣。 通過(guò)了解哪些商品頻繁頻繁地被顧客同時(shí)同時(shí)購(gòu)買(mǎi)，這種關(guān)聯(lián)的發(fā)現(xiàn)可以幫助零售商制定營(yíng)銷(xiāo)策略。 例如，在同一次購(gòu)物中，如果顧客購(gòu)買(mǎi)牛奶的同時(shí)，也購(gòu)買(mǎi)面包（和什么類(lèi)型的面包）的可能性

7、有多大？ 這種信息可以引導(dǎo)銷(xiāo)售，可以幫助零售商有選擇地經(jīng)銷(xiāo)和安排貨架。例如，將牛奶和面包盡可能放近一些，可以進(jìn)一步刺激一次去商店同時(shí)購(gòu)買(mǎi)這些商品。關(guān)聯(lián)規(guī)則挖掘?qū)嵗P(guān)聯(lián)規(guī)則挖掘?qū)嵗?gòu)物籃分析購(gòu)物籃分析哪些商品頻繁地被顧客同時(shí)購(gòu)買(mǎi)？3.2 Apriori關(guān)聯(lián)規(guī)則挖掘算法關(guān)聯(lián)規(guī)則挖掘是從事務(wù)數(shù)據(jù)庫(kù)、關(guān)系數(shù)據(jù)庫(kù)和其它信息存儲(chǔ)中的大量數(shù)據(jù)項(xiàng)集之間發(fā)現(xiàn)有趣的、頻繁出現(xiàn)的模式、關(guān)聯(lián)和相關(guān)性。關(guān)聯(lián)規(guī)則挖掘步驟一般分為2個(gè)步驟：依據(jù)支持度找出所有的頻繁項(xiàng)集。 （頻度）依據(jù)置信度產(chǎn)生關(guān)聯(lián)規(guī)則。 （強(qiáng)度）可以根據(jù)興趣度，找出有興趣的關(guān)聯(lián)規(guī)則。先驗(yàn)算法購(gòu)物籃模型中的有關(guān)概念項(xiàng)商品事務(wù)-交易，購(gòu)物籃項(xiàng)集項(xiàng)集-每個(gè)購(gòu)物籃

8、由多個(gè)項(xiàng)組成的集合。包含k個(gè)項(xiàng)的項(xiàng)集稱(chēng)為k項(xiàng)集。milk，bread是一個(gè)2項(xiàng)集。支持度支持度-項(xiàng)集的頻率，是指包含項(xiàng)集的事務(wù)數(shù)。如果A是一個(gè)項(xiàng)集，A的支持度是指包含A的購(gòu)物籃的數(shù)目。頻繁項(xiàng)集頻繁項(xiàng)集-一個(gè)在多個(gè)購(gòu)物籃中出現(xiàn)的項(xiàng)集。假定最小支持度閾值為s。如果A的支持度不小于s，則稱(chēng)A是頻繁項(xiàng)集。置信度置信度-可信度。規(guī)則AB的可信度等于集合AB的支持度與A的支持度的比值興趣度-關(guān)聯(lián)規(guī)則AB的興趣度定義為其可信度與包含B的購(gòu)物籃的比率之差。如果為負(fù)值或接近于0，則表示關(guān)聯(lián)規(guī)則不十分有趣。關(guān)聯(lián)挖掘?qū)嵗?最簡(jiǎn)單的關(guān)聯(lián)規(guī)則挖掘Transaction ID Items Bought2000A,B,C1

9、000A,C4000A,D5000B,E,FFrequent Itemset SupportA75%B50%C50%A,C50%單維、單層、布爾關(guān)聯(lián)規(guī)則挖掘Minsupport =50%Minconfidence =50% For rule A Csupport = support(A C) = 50%confidence = support(A C)/support(A) = 66.7%For C A (50%, 100%)這就是 Apriori 算法算法Apriori 性質(zhì)：性質(zhì)：Any subset of a frequent itemset must be frequent Aprio

10、ri算法 Apriori算法是一種最有影響的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項(xiàng)集的算法。Apriori Apriori 算法的步驟算法的步驟-使用候選產(chǎn)生發(fā)現(xiàn)頻繁項(xiàng)集。（1）由候選項(xiàng)集(candidate itemset)產(chǎn)生頻繁項(xiàng)集(frequent itemset)； （2）由頻繁項(xiàng)集(frequent itemset)產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則(strong association rule)。vApriori 使用一種稱(chēng)作的迭代方法，v首先，通過(guò)掃描數(shù)據(jù)庫(kù)，累積每個(gè)項(xiàng)的計(jì)數(shù)，并收集滿(mǎn)足最小支持度的項(xiàng)，找出頻繁“1項(xiàng)集”的集合。該集合記作L1。然后，L1用于找頻繁“2項(xiàng)集”的集合L2，而L2用于找L3，如此下去

11、，直到不能再找到頻繁“K項(xiàng)集”。找每個(gè)LK需要一次數(shù)據(jù)庫(kù)全掃描。v為了提高頻繁項(xiàng)集逐層產(chǎn)生的效率，一種稱(chēng)作的重要性質(zhì)用于壓縮搜索空間。任一頻繁項(xiàng)集的所有非空子集也必須是頻繁的。反之，如果某個(gè)候選的非空子集不是頻繁的，那么該候選肯定不是頻繁的。v目的：過(guò)濾候選項(xiàng)集，減少工作量。v用頻繁項(xiàng)集Lk-1找頻繁項(xiàng)集Lk（k=2),由兩步組成：連接步和剪枝步。v（1）連接步連接步：為找Lk ，通過(guò)將Lk-1與自身連接產(chǎn)生候選k項(xiàng)集的集合Ck。然后掃描數(shù)據(jù)庫(kù)，確定Ck中每個(gè)候選項(xiàng)的計(jì)數(shù)，從而確定Lk。 Ck= Lk-1Lk-1自連接：按字典順序連接 (2)剪枝步剪枝步: :根據(jù)如果k項(xiàng)集的（k-1)項(xiàng)子集不

12、在Lk-1 中，則該候選也不可能是頻繁的，從而可以從Ck中刪除。 v頻繁項(xiàng)集發(fā)現(xiàn)過(guò)程：v（1）掃描v（2）計(jì)數(shù)v（3）比較v（4）產(chǎn)生頻繁項(xiàng)集v（5）連接、剪枝，產(chǎn)生候選項(xiàng)集v重復(fù)步驟（1）（5）直到不能發(fā)現(xiàn)更大頻集步驟2：產(chǎn)生關(guān)聯(lián)規(guī)則根據(jù)前面提到的置信度的定義，關(guān)聯(lián)規(guī)則的產(chǎn)生如下：（1）對(duì)于每個(gè)頻繁項(xiàng)集L，產(chǎn)生L的所有非空子集；（2）對(duì)于L的每個(gè)非空子集S，如果則輸出規(guī)則“S LS”。注：LS表示在項(xiàng)集L中除去S子集的項(xiàng)集。 舉 例由頻繁項(xiàng)集產(chǎn)生關(guān)聯(lián)規(guī)則頻繁項(xiàng)集l=B,C,EL的非空子集有：B,CB,EC.EBCE,得出關(guān)聯(lián)規(guī)則如下：BC=E BC=E ,confidence=2/2=100

13、%B E=C ,confidence=2/3=66.7%C E=B C E=B ,confidence=2/2=100%B=C E ,confidence=2/3=66.7%C=B E ,confidence=2/3=66.7%E=B C ,confidence=2/3=66.7%如果最小置信度閾值為70%，則只有上面的1,3規(guī)則可以輸出。Apriori算法偽代碼算法： Apriori，使用逐層迭代方法基于候選產(chǎn)生找出頻繁項(xiàng)集輸入：D：事務(wù)數(shù)據(jù)庫(kù) min_sup:最小支持度閾值輸出：L：D中的頻繁項(xiàng)集方法： （1） L 1 = find_frequent_1_itemsets(D); （2）

14、for (k=2;L k-1 ;k+) （3） C k = apriori_gen(L= apriori_gen(L k-1 );（4） for each transaction t D /scan D for counts（5） C t = subset(C k,t);/get the subsets of t that are candidates（6） for each candidate c C t（7） c.count+;（8） （9） L k =c Ck|c.countmin_sup（10） （11） return L= k L k;連接步和剪枝步第1 步：連接(join) Pro

15、cedure apriori_gen(L k -1:frequent(k- 1) itemset) 1) for each itemset l 1L k-1 2) for each itemset l 2L k-1 3) if (l 11=l 21)(l 1k-2=l 2k-2)(l1k-1 l 2k-1)then 4) c=l1 l2；/連接， 產(chǎn)生候選集 5) if has_infrequent_subsethas_infrequent_subset(c，L k-1 ) then 6) delete c;/修剪， 去掉無(wú)用的候選項(xiàng) 7) else add c to C k; 8) 9) r

16、eturn C k; 連接步和剪枝步第2 步: 剪枝(prune) procedure has_infrequent_subset(c: candidate k itemset;L k-1 : frequent(k- 1)itemset);/使用先驗(yàn)知識(shí) 1) for each (k- 1)subset s of c2) if s L k-1 then 3) return true; 4) return false; AprioriApriori算法的基本流程算法的基本流程使用逐層搜索的迭代方法，通過(guò)對(duì)數(shù)據(jù)庫(kù)的多次掃描發(fā)現(xiàn)所有的頻繁項(xiàng)集。在每一趟掃描中只考慮具有同一長(zhǎng)度k(即為項(xiàng)集中所含項(xiàng)目的

17、個(gè)數(shù))的所有項(xiàng)集。算法的第一次掃描僅僅計(jì)算每個(gè)項(xiàng)目的具體支持度，以確定長(zhǎng)度為1的頻繁項(xiàng)集。在后繼的每一次掃描中，首先使用在前一次獲得的頻繁項(xiàng)集Lk-1和Apriori-gen函數(shù)產(chǎn)生的候選項(xiàng)集q，接著掃描數(shù)據(jù)庫(kù)，計(jì)算Ck中候選項(xiàng)的支持度，最后確定候選項(xiàng)集中哪些真正成為頻繁項(xiàng)集。重復(fù)上述過(guò)程直到再也發(fā)現(xiàn)不了新的頻繁項(xiàng)集為止。TID Items100 1 3 4200 2 3 5300 1 2 3 5400 2 5Database Ditemset sup.1223334153itemset sup.12233353Scan DC1L1itemset1 21 31 52 32 53 5itemse

18、t sup1 211 321 512 322 533 52itemset sup1 322 322 533 52L2C2C2Scan DC3L3itemset2 3 5Scan Ditemset sup2 3 52Apriori算法實(shí)例設(shè)定最小支持度閾值為2 練習(xí)題練習(xí)題下表是某商店的事務(wù)數(shù)據(jù)庫(kù)D，數(shù)據(jù)庫(kù)中有9個(gè)事務(wù)。試用Apriori算法找出其關(guān)聯(lián)規(guī)則。TIDTID商品商品IDID列表列表T100I1，I2，I5T200I2.I4T300I2，I3T400I1，I2，I4T500I1，I3T600I2，I3T700I1，I3T800I1，I2，I3，I5T900I1，I2，I3設(shè)定最小支持度

19、閾值為2 掃描D，對(duì)每個(gè)候選項(xiàng)計(jì)數(shù)，生成C1：項(xiàng)集支持度計(jì)數(shù)I16I27I36I42I52比較候選項(xiàng)支持度計(jì)數(shù)與最小支持度計(jì)數(shù)，生成L1： 項(xiàng)集支持度計(jì)數(shù)I16I27I36I42I52由L1產(chǎn)生候選集C2： 項(xiàng)集I1，I2I1，I3I1，I4I1，I5I2，I3I2，I4I2，I5I3，I4I3，I5I4，I5再次掃描D，對(duì)每個(gè)候選項(xiàng)計(jì)數(shù)，產(chǎn)生L2： 項(xiàng)集支持度計(jì)數(shù)I1，I24I1，I34I1，I52I2，I34I2，I42I2，I52對(duì)L2進(jìn)行連接&剪枝，產(chǎn)生C3，即最終結(jié)果。 由頻繁項(xiàng)集產(chǎn)生關(guān)聯(lián)規(guī)則:L1=I1,I2,I5的非空子集有：I1,I2I1,I5I2,I5I1I2I5,結(jié)

20、果關(guān)聯(lián)規(guī)則如下：I1 I2=I5 confidence=2/4=50% 如果最小置信度閾值為70%，則2I1I1 I5=I2 I5=I2 confidence=2/2=100% 3,6條規(guī)則可以輸出。I2I2 I5=I1 I5=I1 confidence=2/2=100% 請(qǐng)寫(xiě)出第請(qǐng)寫(xiě)出第2 2個(gè)頻繁項(xiàng)集的關(guān)聯(lián)規(guī)則個(gè)頻繁項(xiàng)集的關(guān)聯(lián)規(guī)則I1= I2 I5 confidence=2/6=33%I2=I1 I5 confidence=2/7=29%I5=I1I5=I1 I2 I2 confidence=2/2=100%項(xiàng)集I1，I2，I3I1，I2，I5支持度計(jì)數(shù)22Apriori Apriori

21、算法的局限性算法的局限性可能需要產(chǎn)生大量候選項(xiàng)集。例如，如果有104個(gè)頻繁1項(xiàng)集，可能產(chǎn)生107個(gè)候選2項(xiàng)集?？赡苄枰貜?fù)掃描數(shù)據(jù)庫(kù)，通過(guò)模式匹配檢查一個(gè)很大的候選集合。由于依賴(lài)于候選項(xiàng)集產(chǎn)生頻繁項(xiàng)集的理論（Apriori類(lèi)算法）所開(kāi)發(fā)的算法具有先天的弱點(diǎn)，使得在基于Apriori算法開(kāi)發(fā)的應(yīng)用沒(méi)有實(shí)質(zhì)性突破。 FP-growthFP-growth算法算法- -頻繁模式增長(zhǎng)頻繁模式增長(zhǎng)Han等提出的一種新的算法理論，用一種壓縮的數(shù)據(jù)結(jié)構(gòu)(FP-tree)存儲(chǔ)關(guān)聯(lián)規(guī)則挖掘所需的全部數(shù)據(jù)信息，通過(guò)對(duì)源數(shù)據(jù)的兩次掃描，將數(shù)據(jù)信息存到這種結(jié)構(gòu)里，避開(kāi)了產(chǎn)生候選項(xiàng)集的步驟，極大地減少了數(shù)據(jù)交換和頻繁匹配

22、的開(kāi)銷(xiāo)。這就是所謂不候選產(chǎn)生挖掘頻繁項(xiàng)不候選產(chǎn)生挖掘頻繁項(xiàng)集的算法集的算法(Frequent Patterns Growth, FP-growth)。采用分治策略，首先，將提供頻繁項(xiàng)集的數(shù)據(jù)庫(kù)壓縮到一棵頻繁模式樹(shù)。然后，將壓縮后的數(shù)據(jù)庫(kù)劃分成一組條件數(shù)據(jù)庫(kù)，每個(gè)關(guān)聯(lián)一個(gè)頻繁項(xiàng)或“模式段”，并分別挖掘每個(gè)條件數(shù)據(jù)庫(kù)。FP-growthFP-growth算法算法- -頻繁模式增長(zhǎng)頻繁模式增長(zhǎng)(1)它構(gòu)造了一種新穎的、緊湊的數(shù)據(jù)結(jié)構(gòu)FP-tree。它是一種擴(kuò)展的前綴樹(shù)結(jié)構(gòu)，存儲(chǔ)了關(guān)于頻繁模式數(shù)量的重要信息。 (2)開(kāi)發(fā)了基于FP-tree的模式片斷成長(zhǎng)算法，它從長(zhǎng)度為1的頻繁模式開(kāi)始，只檢查它的條件

23、模式構(gòu)建它的條件模式樹(shù)，并且在這個(gè)樹(shù)上遞歸地進(jìn)行挖掘。模式的成長(zhǎng)通過(guò)聯(lián)合條件模式樹(shù)新產(chǎn)生的后綴模式實(shí)現(xiàn)。 (3)挖掘過(guò)程中采用的搜索技術(shù)是基于分區(qū)的，通過(guò)分割再解決的方法，而不是Apriori類(lèi)算法的自下向上產(chǎn)生頻繁模式的集合。2021-11-1145示例FP Growth算法找頻繁項(xiàng)集TidItems1I1,I2,I52I2,I43I2,I34I1,I2,I45I1,I36I2,I37I1,I38I1,I2,I3,I59I1,I2,I3事務(wù)數(shù)據(jù)庫(kù)如下，最小支持度閾值為2第第1 1步：步：構(gòu)造構(gòu)造FP-tree掃描事務(wù)數(shù)據(jù)庫(kù)得到頻繁1-項(xiàng)目集F定義min_sup=2，即最小支持度為2重新排列F

24、I1I2I3I4I567622I2I1I3I4I5766222021-11-1146重新調(diào)整事務(wù)數(shù)據(jù)庫(kù)TidItems1I2, I1,I52I2,I43I2,I34I2, I1,I45I1,I36I2,I37I1,I38I2, I1,I3,I59I2, I1,I3I27I16I36I42I522021-11-1147創(chuàng)建根結(jié)點(diǎn)和頻繁項(xiàng)目表Item-nameSupport CountNode-headI27NullI16NullI36NullI42NullI52NullNull2021-11-1148加入第一個(gè)事務(wù)(I2,I1,I5)Item-nameSupport CountNode-head

25、I27I16I36NullI42NullI52NullI2:1I1:1I5:12021-11-1149加入第二個(gè)事務(wù)(I2,I4)Item-nameSupport CountNode-headI27I16I36NullI42I52NullI2:2I1:1I5:1I4:12021-11-1150加入第三個(gè)事務(wù)(I2,I3)Item-nameSupport CountNode-headI27I16I36I42I52NullI2:3I1:1I5:1I4:1I3:12021-11-1151加入第四個(gè)事務(wù)(I2,I1,I4)Item-nameSupport CountNode-headI27I16I36

26、I42I52NullI2:4I1:2I5:1I4:1I3:1I4:12021-11-1152加入第五個(gè)事務(wù)(I1,I3)Item-nameSupport CountNode-headI27I16I36I42I52NullI2:4I1:2I5:1I4:1I3:1I4:1I1:1I3:12021-11-1153加入第六個(gè)事務(wù)(I2,I3)Item-nameSupport CountNode-headI27I16I36I42I52NullI2:5I1:2I5:1I4:1I3:2I4:1I1:1I3:12021-11-1154加入第七個(gè)事務(wù)(I1,I3)Item-nameSupport CountNo

27、de-headI27I16I36I42I52NullI2:5I1:2I5:1I4:1I3:2I4:1I1:2I3:22021-11-1155加入第八個(gè)事務(wù)(I2,I1,I3,I5)Item-nameSupport CountNode-headI27I16I36I42I52NullI2:6I1:3I5:1I4:1I3:2I4:1I1:2I3:2I5:1I3:12021-11-1156加入第九個(gè)事務(wù)(I2,I1,I3)Item-nameSupport CountNode-headI27I16I36I42I52NullI2:7I1:4I5:1I4:1I3:2I4:1I1:2I3:2I5:1I3:22

28、021-11-1157第二步、FP-growth首先考慮I5，得到條件模式基： 、構(gòu)造條件FP-tree得到I5頻繁項(xiàng)集：I2,I5:2,I1,I5:2,I2,I1,I5:2Item-nameNode-headI2I1NullI2:2I1:2I3:12021-11-1158第二步、FP-growth接著考慮I4，得到條件模式基： 、構(gòu)造條件FP-tree得到I4頻繁項(xiàng)集：I2,I4:2Item-nameNode-headI2NullI2:2I1:12021-11-1159第二步、FP-growth然后考慮I3，得到條件模式基： 、 構(gòu)造條件FP-tree由于此樹(shù)不是單分支路徑，因此需要遞歸挖掘

29、I3Item-nameNode-headI2I1NullI2:4I1:2I1:22021-11-1160第二步、FP-growth遞歸考慮I3，此時(shí)得到I1條件模式基,即I1, I3的條件模式基為構(gòu)造條件FP-tree得到I3的頻繁項(xiàng)目集I2,I3:4,I1,I3:4,I2,I1,I3:2Item-nameNode-headI2NullI2:22021-11-1161第二步、FP-growth最后考慮I1，得到條件模式基： 構(gòu)造條件FP-tree得到I1的頻繁項(xiàng)目集：I2,I1:4Item-nameNode-headI2NullI2:4產(chǎn)生的頻繁模式項(xiàng)項(xiàng)條件模式基條件模式基條件條件FPFP樹(shù)樹(shù)

30、產(chǎn)生的頻繁模式產(chǎn)生的頻繁模式I5I2 I1:1,I2 I1 I3:1I2 I5:2,I1 I5:2I2 I1 I5:2I4I2 I1:1,I2:1I2 I4:2I3I2 I1:2,I2:2,I1:2I2 I3:4,I1 I3:4I2 I1 I3:2I1I2:4I2 I1:4頻繁項(xiàng)目集及支持度為:L2=I1 I3:4, I2 I1:4 , I1 I5:2 , I2 I3:4, I2 I4:2, I2 I5:2L3=I2 I1 I5:2, I2 I1 I3:2與Apriori算法的結(jié)果是相同的。 FP-growthFP-growth算法算法FP-growthFP-growth算法的主要思想算法的主

31、要思想 該算法主要是為了克服類(lèi)Apriori算法的產(chǎn)生候選項(xiàng)集的缺點(diǎn)，通過(guò)采用一種新的數(shù)據(jù)結(jié)構(gòu)FP-tree來(lái)達(dá)到目的。 優(yōu)點(diǎn)：只掃描數(shù)據(jù)庫(kù)二次，并且不用產(chǎn)生候選項(xiàng)集，提高了效率。 FP-growthFP-growth算法算法（1 1）數(shù)據(jù)庫(kù)的第）數(shù)據(jù)庫(kù)的第1 1次掃描與次掃描與AprioriApriori相同，導(dǎo)出頻相同，導(dǎo)出頻繁項(xiàng)（繁項(xiàng)（1 1項(xiàng)集）的集合和支持度計(jì)數(shù)。頻繁項(xiàng)集項(xiàng)集）的集合和支持度計(jì)數(shù)。頻繁項(xiàng)集L L按按支持度計(jì)數(shù)的遞減排序。支持度計(jì)數(shù)的遞減排序。（2 2）構(gòu)造）構(gòu)造FPFP樹(shù)。首先創(chuàng)建樹(shù)根，用樹(shù)。首先創(chuàng)建樹(shù)根，用NULLNULL標(biāo)記。第標(biāo)記。第二次掃描數(shù)據(jù)庫(kù)二次掃描數(shù)據(jù)庫(kù)

32、D D。每個(gè)事務(wù)中的項(xiàng)按照。每個(gè)事務(wù)中的項(xiàng)按照L L中的次序中的次序處理。并對(duì)每個(gè)事務(wù)創(chuàng)建一個(gè)分枝。處理。并對(duì)每個(gè)事務(wù)創(chuàng)建一個(gè)分枝。一般地，當(dāng)為一個(gè)事務(wù)考慮增加分枝時(shí)，沿共同前一般地，當(dāng)為一個(gè)事務(wù)考慮增加分枝時(shí)，沿共同前綴上的每個(gè)節(jié)點(diǎn)的計(jì)數(shù)加綴上的每個(gè)節(jié)點(diǎn)的計(jì)數(shù)加1.1.（3 3）創(chuàng)建一個(gè)項(xiàng)頭表，使每項(xiàng)通過(guò)一個(gè)節(jié)點(diǎn)鏈指）創(chuàng)建一個(gè)項(xiàng)頭表，使每項(xiàng)通過(guò)一個(gè)節(jié)點(diǎn)鏈指向它在樹(shù)中的位置。向它在樹(shù)中的位置。FP樹(shù)的挖掘過(guò)程由每個(gè)長(zhǎng)度為1的頻繁模式（初試后綴模式）開(kāi)始，構(gòu)造它的條件模式基（由FP樹(shù)中與后綴模式一起出現(xiàn)的前綴路徑集組成），然后，構(gòu)造它的（條件）FP樹(shù)，并遞歸地對(duì)該樹(shù)進(jìn)行挖掘。模式增長(zhǎng)通過(guò)后綴模式

33、與條件FP樹(shù)產(chǎn)生的頻繁模式連接實(shí)現(xiàn)。FP-FP-增長(zhǎng)算法偽代碼算法偽代碼算法：FP-FP-增長(zhǎng)。使用FP-樹(shù)，通過(guò)模式段增長(zhǎng)，挖掘頻繁模式。輸入輸入：事務(wù)數(shù)據(jù)庫(kù)D；最小支持度閾值min_sup。輸出輸出：頻繁模式的完全集。1 按以下步驟構(gòu)造FP-樹(shù)：(a) 掃描事務(wù)數(shù)據(jù)庫(kù)D 一次。收集頻繁項(xiàng)的集合F 和它們的支持度。對(duì)F 按支持度降序排序，結(jié)果為頻繁項(xiàng)表L。(b) 創(chuàng)建FP樹(shù)的根結(jié)點(diǎn)，以“null”標(biāo)記它。對(duì)于D中每個(gè)事務(wù)Trans，執(zhí)行：選擇 Trans 中的頻繁項(xiàng)，并按L中的次序排序。設(shè)排序后的頻繁項(xiàng)表為p | P，其中，p 是第一個(gè)元素，而P 是剩余元素的表。調(diào)用insert_tree(

34、p | P, T)。該過(guò)程執(zhí)行情況如下:如果T有子女N 使得N.item-name = p.item-name，則N 的計(jì)數(shù)增加1；否則創(chuàng)建一個(gè)新結(jié)點(diǎn)N，將其計(jì)數(shù)設(shè)置為1，鏈接到它的父結(jié)點(diǎn)T，并且通過(guò)結(jié)點(diǎn)鏈結(jié)構(gòu)將其鏈接到具有相同item-name 的結(jié)點(diǎn)。如果P 非空，遞歸地調(diào)用insert_tree(P, N)。2 FP-樹(shù)的挖掘通過(guò)調(diào)用FP_growthFP_growth(FP_tree, null)實(shí)現(xiàn)。該過(guò)程實(shí)現(xiàn)如下：procedure FP_growth(Tree, ) (1) if Tree 含單個(gè)路徑P then (2) for each 路徑 P 中結(jié)點(diǎn)的每個(gè)組合（記作）(3)

35、 產(chǎn)生模式 ，其支持度support 等于中結(jié)點(diǎn)的最小支持度；(4) else for Tree 的頭表中的每個(gè)ai (5) 產(chǎn)生一個(gè)模式 = ai ，其支持度support = ai .support；(6) 構(gòu)造的條件模式基，然后構(gòu)造的條件FP樹(shù)Tree；(7) if Tree then(8) 調(diào)用 FP_growth (Tree, )；練習(xí)：構(gòu)建練習(xí)：構(gòu)建FPFP樹(shù)樹(shù)交易編號(hào)所有購(gòu)物項(xiàng)（排序后的）頻繁項(xiàng)100f,a,c,d,g,i,m,pF：4,c:4,a:3,m:3,p:3200a,b,c,f,l,m,oF:4,c:4,a:3,b:3,m:3300b,f,h,j,oF:4,b:3400

36、b,c,k,s,pC:4,b:3,p:3500a,f,c,e,l,p,m,nF:4,c:4,a:3,m:3,p:3其中，最小支持度閾值為3FP-growth 算法實(shí)現(xiàn)nullb:1f:3c:1b:1p:1a:2b:1m:1f:2c:2a:3f:4c:3m:2p:23.f,b4.c,b,pf:1c:1m:1p:1a:11.f,c,a,m,p2.f,c,a,b,m5.f,c,a,m,pFP-growth算法樹(shù)的構(gòu)造 FP-growth 算法實(shí)例頭 表項(xiàng)節(jié) 點(diǎn) 鏈 的 頭fcabmprootf:4c:1p:2m :2a:3b:1b:1p:1b:1c:3m :1生成的FP樹(shù) 節(jié)點(diǎn)鏈性質(zhì)對(duì)任意頻繁項(xiàng)ai

37、，順著ai的節(jié)點(diǎn)鏈，從ai的頭開(kāi)始，可以找到包含ai的所有頻繁模式。3.3 3.3 關(guān)聯(lián)規(guī)則挖掘的其他算法關(guān)聯(lián)規(guī)則挖掘的其他算法典型算法典型算法 AprioriApriori算法算法（及變種AprioriTid和AprioriHybrid)） AIS 算法（R. Agrawal等提出） SETM 算法（M. Houtsma等提出） DHP 算法（J. Park等提出） PARTITION 算法（A.Savasere等提出） Sampling 算法（H.Toivonen提出） FP-growth 算法（Jiawei Han提出）AISAIS算法的主要思想算法的主要思想其主要思想是一邊掃描數(shù)據(jù)庫(kù)，

38、一邊產(chǎn)生候選項(xiàng)集并累計(jì)支持度。具體地說(shuō)，在對(duì)數(shù)據(jù)庫(kù)進(jìn)行第k次掃描時(shí)，候選項(xiàng)集是由第k-1次掃描所產(chǎn)生的邊界集(frontier set)通過(guò)增加當(dāng)前事務(wù)中的項(xiàng)得到，同時(shí)計(jì)算候選項(xiàng)集中元素的支持?jǐn)?shù)，直到某次掃描所產(chǎn)生的邊界集為空。 缺點(diǎn)：生成的候選項(xiàng)集太大。AprioriApriori算法的主要思想算法的主要思想該算法利用了頻繁項(xiàng)集所具有的任意頻繁項(xiàng)集的子集都是頻繁項(xiàng)集的這一性質(zhì)對(duì)數(shù)據(jù)庫(kù)進(jìn)行多次掃描:第一次掃描得到頻繁項(xiàng)集的集合L1 ，第k趟掃描前先利用上次掃描的結(jié)果項(xiàng)目集Lk-1,產(chǎn)生候選k項(xiàng)集的集合Ck ，然后再通過(guò)掃描數(shù)據(jù)庫(kù)確定C中每一候選k項(xiàng)集的支持?jǐn)?shù)，最后在該次掃描結(jié)束時(shí)求出頻繁k項(xiàng)集

39、的集合Lk ，算法的終止條件是Ck或Lk為空。 優(yōu)點(diǎn)：所產(chǎn)生的候選項(xiàng)集比AIS算法少得多，效率較高。事實(shí)上，它被視為關(guān)聯(lián)規(guī)則挖掘最經(jīng)典的算法，其他很多算法都是其變種或改進(jìn)。 SETMSETM算法的主要思想算法的主要思想該算法實(shí)際也是AIS算法的變形。SETM把候選集的產(chǎn)生和累計(jì)分開(kāi)，在一個(gè)線性存儲(chǔ)結(jié)構(gòu)里存儲(chǔ)了所有候選集和相應(yīng)的交易的標(biāo)識(shí)符（TID）。每次掃描結(jié)束后，不再讀取數(shù)據(jù)庫(kù)，而是對(duì)TID進(jìn)行排序并累計(jì)各個(gè)候選集的支持度。其思想是掃描候選集的編碼（TID）來(lái)代替掃描數(shù)據(jù)庫(kù)，實(shí)質(zhì)上是把數(shù)據(jù)庫(kù)中與支持有關(guān)的信息單獨(dú)提取出來(lái)，構(gòu)成一個(gè)較小但充分的TID庫(kù)。這種做法大大減少了數(shù)據(jù)庫(kù)訪問(wèn)的時(shí)間。 缺點(diǎn)：候選項(xiàng)集過(guò)大。 DHPDHP算法的主要思想算法的主要思想該算法利用散列表(hash table)產(chǎn)生候選集，是對(duì)Apriori算法的直接改進(jìn)。在遍歷一次數(shù)據(jù)庫(kù)得到候選k-項(xiàng)集的支持度，得到頻繁k一項(xiàng)集后，DHP算法將每一個(gè)事務(wù)的可能的(k+1)-項(xiàng)集通過(guò)哈希規(guī)則形成散列表。