Python數(shù)據(jù)挖掘算法與應(yīng)用 課件 第8章 關(guān)聯(lián)規(guī)則分析

Association-rulesAnalysis第8章

關(guān)聯(lián)規(guī)則分析關(guān)聯(lián)規(guī)則相關(guān)概念8.2Apriori算法8.3FP-Growth算法8.4Eclat算法8.5概述8.1關(guān)聯(lián)規(guī)則典型應(yīng)用場景8.6學(xué)習(xí)目標(biāo)1關(guān)聯(lián)規(guī)則分析概述OverviewofAssociationRuleAnalysis8.1什么是關(guān)聯(lián)規(guī)則分析？關(guān)聯(lián)規(guī)則分析關(guān)聯(lián)規(guī)則分析（Association-rulesAnalysis）是數(shù)據(jù)挖掘領(lǐng)域的重要挖掘任務(wù)之一，它是以某種方式分析數(shù)據(jù)源，從數(shù)據(jù)樣本集中發(fā)現(xiàn)一些潛在有用的信息和不同數(shù)據(jù)樣本之間關(guān)系的過程。關(guān)聯(lián)規(guī)則分析于1993年由美國IBMAlmadenResearchCenter的RakeshAgrawal等人在進行市場購物籃分析時首先提出的，用以發(fā)現(xiàn)超市銷售數(shù)據(jù)庫中的顧客購買模式，現(xiàn)在已經(jīng)廣泛應(yīng)用于許多領(lǐng)域。關(guān)聯(lián)規(guī)則分類布爾型布爾型關(guān)聯(lián)規(guī)則處理的值都是離散的、種類化的，它顯示了這些變量之間的關(guān)系。數(shù)值型1、基于關(guān)聯(lián)規(guī)則處理的變量2、基于規(guī)則中數(shù)據(jù)的抽象層次3、基于規(guī)則中涉及到的數(shù)據(jù)的維數(shù)單層多層單維多維數(shù)值型關(guān)聯(lián)規(guī)則可以和多維關(guān)聯(lián)或多層關(guān)聯(lián)規(guī)則結(jié)合起來，對數(shù)值型字段進行處理，將其進行動態(tài)的分割，或者直接對原始的數(shù)據(jù)進行處理，當(dāng)然數(shù)值型關(guān)聯(lián)規(guī)則中也可以包含種類變量。在單層的關(guān)聯(lián)規(guī)則中，所有變量都沒有考慮到現(xiàn)實數(shù)據(jù)是具有多個不同層次的。在多層的關(guān)聯(lián)規(guī)則中，對數(shù)據(jù)的多層性已經(jīng)進行了充分的考慮。在單維的關(guān)聯(lián)規(guī)則中，只涉及到數(shù)據(jù)的一個維。換言之，單維關(guān)聯(lián)規(guī)則是處理單個屬性中的一些關(guān)系。多維的關(guān)聯(lián)規(guī)則中，要處理的數(shù)據(jù)將會涉及多個維。換言之，多維關(guān)聯(lián)規(guī)則是處理多個屬性之間的某些關(guān)系。關(guān)聯(lián)規(guī)則相關(guān)概念8.2Apriori算法8.3FP-Growth算法8.4Eclat算法8.5概述8.1關(guān)聯(lián)規(guī)則典型應(yīng)用場景8.6學(xué)習(xí)目標(biāo)2關(guān)聯(lián)規(guī)則相關(guān)概念RelatedConceptsofAssociationRules8.2基本概念事務(wù)集每一個事務(wù)（Transaction）T

對應(yīng)數(shù)據(jù)庫的一條記錄，因此事務(wù)集合對應(yīng)于數(shù)據(jù)集D={T1,T2,…,Tm}。事務(wù)事務(wù)是項的集合，其中一個事務(wù)對應(yīng)于一條記錄Ti，項對應(yīng)于屬性，即Ti={Ai1，Ai2,…,Aip}，Ti

D。對應(yīng)每一個事務(wù)有唯一的標(biāo)識，如事務(wù)號，記為TID。?項項是事務(wù)中的元素，對應(yīng)于記錄中的字段。項集項集是指若干項的集合。假設(shè)

I={A1,A2,…,An}是數(shù)據(jù)集D中所有項的集合，I

中任何子集X都稱為項集（itemset），若|X|=k，則稱X為k-項集。設(shè)Ti是一個事務(wù)，X是k-項集，如果X

Ti，則稱事務(wù)Ti包含項集X。?基本概念有了以上這些概念的定義，則可將關(guān)聯(lián)規(guī)則的定義表述如下：關(guān)聯(lián)規(guī)則一個關(guān)聯(lián)規(guī)則是形如X=>Y的蘊涵式，X

I，Y

I，并且X∩Y=?，X、Y分別稱為關(guān)聯(lián)規(guī)則X=>Y的前提和結(jié)論。關(guān)聯(lián)規(guī)則X=>Y表示這樣一種關(guān)聯(lián)，如果一個事務(wù)Ti包含項集X中的所有項，那么該事務(wù)Ti與項集Y的所有項有著關(guān)聯(lián)關(guān)系。??支持度、置信度和提升度一般使用支持度（support）和置信度（confidence）兩個參數(shù)來描述關(guān)聯(lián)規(guī)則的項。1、支持度項集支持?jǐn)?shù)：數(shù)據(jù)集D中包含項集X的事務(wù)數(shù)稱為項集X的支持?jǐn)?shù)，記為：項集支持度：項集X的支持度是指X在數(shù)據(jù)集D中出現(xiàn)的概率。規(guī)則支持度：關(guān)聯(lián)規(guī)則X=>Y在數(shù)據(jù)集D中的支持度是D中同時包含X、Y的事務(wù)數(shù)與所有事務(wù)數(shù)之比，記為S_port(X=>Y)。支持度描述了X、Y這兩個事務(wù)在事務(wù)集D中同時出現(xiàn)（記為X∪Y）的概率。支持度、置信度和提升度2、置信度規(guī)則置信度：關(guān)聯(lián)規(guī)則X=>Y的置信度是指同時包含X、Y的事務(wù)數(shù)與包含X的事務(wù)數(shù)之比，它用來衡量關(guān)聯(lián)規(guī)則的可信程度。記為：一般情況下，只有關(guān)聯(lián)規(guī)則的置信度大于或等于預(yù)設(shè)的閾值，就說明了它們之間具有某種程度的相關(guān)性，這才是一條有價值的規(guī)則。如果關(guān)聯(lián)規(guī)則置信度大于或等于用戶給定的最小置信度閾值，則稱關(guān)聯(lián)規(guī)則是可信的。支持度、置信度和提升度3、提升度提升度（Lift）是指當(dāng)銷售一個商品A時，另一個商品B銷售率會增加多少。計算公式為：假設(shè)關(guān)聯(lián)規(guī)則’牛奶’=>’雞蛋’的置信度為C_dence(’牛奶’=>’雞蛋’)=2/4，牛奶的支持度S_port(’牛奶’)=3/5，則’牛奶’和’雞蛋’的支持度Lift(’牛奶’=>’雞蛋’)=0.83。當(dāng)關(guān)聯(lián)規(guī)則A=>B的提升度值大于1的時候，說明商品A賣得越多，B也會賣得越多；當(dāng)提升度等于1則意味著商品A和B之間沒有關(guān)聯(lián)；當(dāng)提升度小于1則意味著購買商品A反而會減少B的銷量。頻繁項集關(guān)聯(lián)規(guī)則分析就是在數(shù)據(jù)集中找出所有頻繁和可信的關(guān)聯(lián)規(guī)則，即強關(guān)聯(lián)規(guī)則，通常所說的關(guān)聯(lián)規(guī)則指的就是強關(guān)聯(lián)規(guī)則。設(shè)k項集X的支持度為S_port(X)，若S_port(X)不小于用戶指定的最小支持度，則稱X為k項頻繁項集（frequentk-itemset）或頻繁k項集，否則稱X為k項非頻繁項集或非頻繁k項集。頻繁項集頻繁項集分析就是找出數(shù)據(jù)集中所有支持度大于或等于最小支持度閾值的項集。頻繁項集分析如果X是一個頻繁項集，并且X的任意一個超集都是非頻繁的，則稱X是最大頻繁項集。最大頻繁項集給定某數(shù)據(jù)集和最小支持度閾值，如果挖掘算法需要判斷k項集是頻繁項集還是非頻繁項集，那么k項集稱為候選項集。候選項集頻繁項集(1)頻繁項集的所有非空子集也是頻繁的。(2)非頻繁項集的所有超集是非頻繁的。頻繁項集具有兩個非常重要的性質(zhì)：設(shè)X、Y是D中的項集，由頻繁項集的性質(zhì)，若X

Y，如果X是非頻繁項集，則Y也是非頻繁項集；若X

Y，如果Y是頻繁項集，則X也是頻繁項集。給定一個數(shù)據(jù)集D，關(guān)聯(lián)規(guī)則分析的問題就是產(chǎn)生支持度和置信度分別大于用戶事先給定的最小支持度和最小置信度的關(guān)聯(lián)規(guī)則。關(guān)聯(lián)規(guī)則分析的任務(wù)就是要挖掘出D中所有的強關(guān)聯(lián)規(guī)則X=>Y。強關(guān)聯(lián)規(guī)則X=>Y對應(yīng)的項集X∪Y必定是頻繁項集，頻繁項集X∪Y導(dǎo)出的關(guān)聯(lián)規(guī)則X=>Y的置信度可由頻繁項集X和X∪Y的支持度計算。因此，可以把關(guān)聯(lián)規(guī)則分析劃分為兩個子問題：一個是找出所有的頻繁項集，即所有支持度不低于給定的最小支持度的項集；另一個是由頻繁項集產(chǎn)生強關(guān)聯(lián)規(guī)則，即從第一個子問題得到的頻繁項集中找出置信度不小于用戶給定的最小置信度的規(guī)則。其中，第一個子問題是關(guān)聯(lián)規(guī)則分析算法的核心問題，是衡量關(guān)聯(lián)規(guī)則分析算法的標(biāo)準(zhǔn)。??關(guān)聯(lián)規(guī)則相關(guān)概念8.2Apriori算法8.3FP-Growth算法8.4Eclat算法8.5概述8.1關(guān)聯(lián)規(guī)則典型應(yīng)用場景8.6學(xué)習(xí)目標(biāo)3Apriori算法AprioriAlgorithm8.3Apriori算法思想第二階段利用頻繁項集產(chǎn)生所需的規(guī)則。對給定的L，如果L包含其非空子集A，假設(shè)用戶給定的最小支持度和最小置信度閾值分別為minS_port和minC_dence，并滿足minS_port(L)/minS_port(A)≥minC_dence，則產(chǎn)生形式為A=>L-A的規(guī)則。找出所有超出最小支持度的項集，形成頻繁項集。首先通過掃描數(shù)據(jù)集，產(chǎn)生一個大的候選項集，并計算每個候選項集發(fā)生的次數(shù)，然后基于預(yù)先給定的最小支持度生成一維項集L1。再基于L1和數(shù)據(jù)集中的事務(wù)，產(chǎn)生二維項集L2；依此類推，直到生成N維項集LN，并且已經(jīng)不可能再生成滿足最小支持度的N+1維項集。這樣就依此產(chǎn)生項集{L1,L2,…,LN}。第一階段Agrawal等人于1993年首先提出了挖掘顧客交易數(shù)據(jù)庫中項集間的關(guān)聯(lián)規(guī)則問題，其核心方法是基于頻繁項集理論的遞推方法。在這兩個階段中，第一階段是算法的關(guān)鍵。一旦找到了項集，關(guān)聯(lián)規(guī)則的導(dǎo)出是自然的。事實上，我們一般只對滿足一定的支持度和可信度的關(guān)聯(lián)規(guī)則感興趣。挖掘關(guān)聯(lián)規(guī)則的問題就是產(chǎn)生支持度和置信度分別大于用戶給定的最小支持度和最小置信度的關(guān)聯(lián)規(guī)則。例8.1包含5個事務(wù)的商品銷售數(shù)據(jù)集合D如表8.1所示。表8.1銷售數(shù)據(jù)集D的商品項假設(shè)用戶的最小支持度minS_port=0.4，最小置信度minC_dence=0.6，用Apriori算法產(chǎn)生關(guān)聯(lián)規(guī)則。第一階段，找出存在于D中所有的頻繁特征項集，即那些支持度大于minS_port的項集。(1)利用minS_port=0.4，創(chuàng)建頻繁1-項集，如表8.2所示。表8.2產(chǎn)生頻繁1-項集根據(jù)minS_port=0.4，在1-項候選集C1中，項“蔥”、“蒜”、和“芹菜”不滿足用戶最小支持度要求，所以將這些項刪除，得到頻繁1-項集L1。(2)利用minS_port=0.4，創(chuàng)建頻繁2-項集，如表8.3所示。表8.3產(chǎn)生頻繁2-項集TID商品項

TID商品項T1雞蛋、面包、西紅柿、蔥、蒜、牛奶T4雞蛋、芹菜、牛奶T2面包、牛奶T5雞蛋、西紅柿、豆角T3雞蛋、豆角、牛奶

候選1-項集C1

頻繁1-項集L1雞蛋4

雞蛋4面包2

面包2西紅柿2

西紅柿2蔥1

牛奶4蒜1

豆角2牛奶4

豆角2

芹菜1

(3)通過表8.3形成候選3-項集C3。仍然利用minS_port=0.4，可以看出C3集合中的每個項集都有非頻繁子集，所以創(chuàng)建頻繁3-項集L3為空集，項集生成過程結(jié)束。如表8.4所示。表8.4產(chǎn)生3-項頻繁集由此可知，最大頻繁項集為L2。第二階段，在找出的頻繁項集的基礎(chǔ)上產(chǎn)生強關(guān)聯(lián)規(guī)則。即產(chǎn)生那些支持度和置信度分別大于或等于用戶給定的閾值的關(guān)聯(lián)規(guī)則。以生成的L2為基礎(chǔ)，生成可能的關(guān)聯(lián)規(guī)則如下：(1)C_dence(雞蛋=>牛奶)=3/4=0.75(2)C_dence(牛奶=>雞蛋)=3/4=0.75(3)C_dence(雞蛋=>西紅柿)=2/4=0.5(4)C_dence(西紅柿=>雞蛋)=2/2=1.0(5)C_dence(雞蛋=>豆角)=2/4=0.5(6)C_dence(豆角=>雞蛋)=2/2=1.0(7)C_dence(牛奶=>面包)=2/4=0.5(8)C_dence(面包=>牛奶)=2/2=1.0根據(jù)用戶最小置信度minC_dence=0.6，關(guān)聯(lián)規(guī)則為(1)、(2)、(4)、(6)、(8)。候選3-項集C3

頻繁3-項集L3雞蛋、牛奶、西紅柿1

空集

雞蛋、牛奶、豆角1

雞蛋、西紅柿、豆角1

雞蛋、牛奶、面包1

候選2-項集C2

頻繁2-項集L2雞蛋、面包1

雞蛋、牛奶3雞蛋、西紅柿2

雞蛋、西紅柿2雞蛋、牛奶3

雞蛋、豆角2雞蛋、豆角2

面包、牛奶2面包、西紅柿1

面包、牛奶2

面包、豆角0

西紅柿、牛奶1

西紅柿、豆角1

牛奶、豆角1

Apriori算法Apriori算法是一種深度優(yōu)先算法，它使用頻繁項集性質(zhì)的先驗知識，利用逐層搜索的迭代方法完成頻繁項集的挖掘工作：即k-項集用于搜索產(chǎn)生(k+1)-項集。其具體做法是首先產(chǎn)生候選1-項集C1，再根據(jù)C1產(chǎn)生頻繁1-項集L1，然后利用L1產(chǎn)生候選2-項集C2，再從C2中找出頻繁2-項集L2，而L2可以進一步找出L3，這樣如此不斷地循環(huán)繼續(xù)下去，直到不能找到頻繁k-項集為止。由于從候選項集中產(chǎn)生頻繁項集的過程需要遍歷數(shù)據(jù)集，因此如何正確地產(chǎn)生數(shù)目最少的候選項集十分關(guān)鍵。候選項集產(chǎn)生的過程被分為兩個部分：聯(lián)合與剪枝。采用這兩種方式，使得所有的頻繁項集既不會遺漏又不會重復(fù)。剪枝的目的是減少掃描數(shù)據(jù)集時需要比較的候選項集數(shù)量。剪枝的原則是：候選項集c的k個長度為k-1的子集都在Lk-1中，則保留c；否則c被剪枝。Apriori算法用apriori_gen函數(shù)來生成候選項集，該函數(shù)從頻繁項集Lk-1中派生出候選項集Ck。apriori_gen函數(shù)分為兩步，第一步用Lk-1自連接生成Ck；第二步剪掉無效的項集。生成候選k-項集函數(shù)apriori_gen()算法描述如下：(1)生成候選k-項集CkinsertintoCkselectp.Item1,p.Item2,…,p.Itemk-1,q.Itemk-1fromLk-1p,Lk-1qWherep.Item1=q.Item1,p.Item2=q.Item2,…,p.Itemk-2=q.Itemk-2,p.Itemk-1<q.Itemk-1//這里是對兩個具有k-1個共同項的頻繁集Lk-1進行鏈接(2)剪枝對于項集c∈Ck，如果存在c的子集s，|s|=k-1，且s?Lk-1，則剪掉c。

forall項集集c∈Ckdoforall(k-1)-項集c的子集sdoifs?Lk-1thenCk=Ck-{c}Apriori算法描述輸出產(chǎn)生關(guān)聯(lián)規(guī)則處理流程：step1：L1={1-項集}

//掃描所有項，計算每個項出現(xiàn)的次數(shù)，產(chǎn)生頻繁1-項集step2：for(k=2;Lk-1≠Φ;k++)dobegin

//進行迭代循環(huán)，根據(jù)前一次的Lk-1得到頻繁k-項集Lkstep3：Ck=apriori_gen(Lk-1)

//產(chǎn)生k項候選集step4：forallDi∈Ddo

//掃描一遍數(shù)據(jù)集Dstep5：beginstep6：Ci=subset(Ck,Di)

//確定每個Di所含候選k-項集的subset(Ck,Di)輸入數(shù)據(jù)集D，最小支持度閾值minS_port，最小置信度minC_dencestep7：forallc∈Cidoc.count++

//對候選集的計數(shù)step8：Lk={c∈Ci|c.count≥minS_port}

//刪除候選項集中小于最小支持度的，得到頻繁k-項集step9：endstep10：endstep11：forallsubsets?Lk

//對每個頻繁項集Lk，產(chǎn)生Lk的所有非空子集sstep12：ifC_dence(s=>Lk-s)≥minC_dence

//可信度大于等于最小可信度step13：則輸出s=>Lk-s

//由頻繁集產(chǎn)生關(guān)聯(lián)規(guī)則

Apriori算法的python實現(xiàn)L,suppData=apriori(df,min_support=0.5,use_colnames=False,max_len=None)Apriori()函數(shù)常用形式為：參數(shù)說明：(1)df：表示給定的數(shù)據(jù)集。(2)min_support：表示給定的最小支持度。(3)use_colnames：默認(rèn)False，表示返回的項集，用編號顯示。如果值為True則直接顯示項名稱。(4)max_len：默認(rèn)是None，表示最大項組合數(shù)，不做限制。如果只需要計算兩個項集，可將這個值設(shè)置為2。返回值：(1)L：返回頻繁項集。(2)suppData：返回頻繁項集的相應(yīng)支持度。Sklearn庫中沒有Apriori算法。但是可以采用Python的第三方庫實現(xiàn)Aprior算法發(fā)掘關(guān)聯(lián)規(guī)則。相關(guān)的庫有mlxtend機器學(xué)習(xí)包等，首先需要導(dǎo)入包含Apriori算法的mlxtend包：pipinstallmlxtend。例8.2用Python實現(xiàn)Apriori算法示例。importnumpyasnpdata_set=np.array([['雞蛋','面包','西紅柿','蔥','蒜','牛奶'],['面包','牛奶'],['雞蛋','牛奶','豆角'],['雞蛋','牛奶','芹菜'],['雞蛋','西紅柿','豆角']])defget_C1(data_set):C1=set()foritemindata_set:forlinitem:C1.add(frozenset([l]))returnC1#data_set--數(shù)據(jù)集；C--候選集；min_support--最小支持度defgetLByC(data_set,C,min_support):L={}#頻繁項集和支持?jǐn)?shù)forcinC:fordataindata_set:ifc.issubset(data):ifcnotinL:L[c]=1else:L[c]+=1errorKeys=[]forkeyinL:support=L[key]/float(len(data_set))ifsupport<min_support:#未達到最小支持?jǐn)?shù)errorKeys.append(key)else:L[key]=supportforkeyinerrorKeys:L.pop(key)returnL'''根據(jù)頻繁(k-1)項集自身連接產(chǎn)生候選K項集Ck并剪去不符合條件的候選L—頻繁K-1項集'''defgetCByL(L,k):len_L=len(L)#獲取L的頻繁項集數(shù)量L_keys=list(L.keys())#獲取L的鍵值C=set()foriinrange(len_L):forjinrange(1,len_L):l1=list(L_keys[i])l1.sort()l2=list(L_keys[j])l2.sort()if(l1[0:k-2]==l2[0:k-2]):

#取并集C_item=frozenset(l1).union(frozenset(l2))flag=True#判斷C_item的子集是否在L_keys中foriteminC_item:

#獲取C_item的子集subC=C_item-frozenset([item])ifsubCnotinL_keys:#不在flag=Falseifflag==True:C.add(C_item)returnCdefget_L(data_set,k,min_support):#C1較為特殊，先求C1=get_C1(data_set)L1=getLByC(data_set,C1,min_support)support_data={}L=[]L.append(L1)tempL=L1foriinrange(2,k+1):Ci=getCByL(tempL,i)tempL=getLByC(data_set,Ci,min_support)L.append(tempL)forlinL:forkeyinl:support_data[key]=l[key]returnL,support_data#獲取關(guān)聯(lián)規(guī)則defget_rule(L,support_data,min_support,min_conf):big_rules=[]sub_sets=[]foriinrange(0,len(L)):forfsetinL[i]:forsub_setinsub_sets:ifsub_set.issubset(fset):conf=support_data[fset]/support_data[fset-sub_set]big_rule=(fset-sub_set,sub_set,conf)ifconf>=min_confandbig_rulenotinbig_rules:big_rules.append(big_rule)sub_sets.append(fset)returnbig_rulesif__name__=="__main__":min_support=0.4#最小支持度min_conf=0.6#最小置信度

#獲取所有的頻繁項集L,support_data=get_L(data_set,3,min_support)

#獲取強關(guān)聯(lián)規(guī)則big_rule=get_rule(L,support_data,min_support,min_conf)獲取強關(guān)聯(lián)規(guī)則print('==========所有的頻繁項集如下===========')forlinL:forl_iteminl:print(l_item,end='')print('支持度為：%f'%l[l_item])print('===========================================')forruleinbig_rule:print(rule[0],'==>',rule[1],'\t\tconf=',rule[2])程序運行結(jié)果如圖8.1所示。圖8.1例8.2程序運行結(jié)果例8.3Apriori算法的Python實現(xiàn)示例。frommlxtend.preprocessingimportTransactionEncoderfrommlxtend.frequent_patternsimportapriorifrommlxtend.frequent_patternsimportassociation_rulesimportpandasaspddf_arr=[['雞蛋','面包','西紅柿','蔥','蒜','牛奶'],['面包','牛奶'],['雞蛋','牛奶','豆角'],['雞蛋','牛奶','芹菜'],['雞蛋','西紅柿','豆角']]#轉(zhuǎn)換為算法可接受模型(布爾值)te=TransactionEncoder()df_tf=te.fit_transform(df_arr)df=pd.DataFrame(df_tf,columns=te.columns_)#設(shè)置支持度求頻繁項集frequent_itemsets=apriori(df,min_support=0.4,use_colnames=True)#求關(guān)聯(lián)規(guī)則,設(shè)置最小置信度為0.15rules=association_rules(frequent_itemsets,metric='confidence',min_threshold=0.6)#設(shè)置最小提升度rules=rules.drop(rules[rules.lift<0.6].index)#設(shè)置標(biāo)題索引并打印結(jié)果rules.rename(columns={'antecedents':'from','consequents':'to','support':'sup','confidence':'conf'},inplace=True)rules=rules[['from','to','sup','conf','lift']]print(rules)關(guān)聯(lián)規(guī)則相關(guān)概念8.2Apriori算法8.3FP-Growth算法8.4Eclat算法8.5概述8.1關(guān)聯(lián)規(guī)則典型應(yīng)用場景8.6學(xué)習(xí)目標(biāo)4FP-Growth算法FP-GrowthAlgorithm8.4FP-Growth算法Apriori算法在產(chǎn)生頻繁項集前需要對事務(wù)集進行多次掃描，同時產(chǎn)生大量的候選頻繁集，這就使Apriori算法時間和空間復(fù)雜度較大。但是Apriori算法中有一個很重要的性質(zhì)：頻繁項集的所有非空子集都必須也是頻繁的。但是Apriori算法在挖掘長頻繁模式的時候性能往往低下，韓嘉煒等人在2000年提出了一種稱為頻繁模式增長（Frequent-PatternGrowth，F(xiàn)P-Growth）方法，將數(shù)據(jù)集存儲在一個特定的稱作FP-Tree的結(jié)構(gòu)之后發(fā)現(xiàn)頻繁項集或頻繁項對，即常在一塊出現(xiàn)的項的集合FP-Tree。FP-Growth算法比Apriori算法效率更高，在整個算法執(zhí)行過程中，只需遍歷事務(wù)集2次，就能夠完成頻繁模式發(fā)現(xiàn)。其發(fā)現(xiàn)頻繁項集的基本過程如下：(1)構(gòu)建FP樹；(2)從FP樹中挖掘頻繁項集。FP-Growth算法采用的策略FP-Growth算法采取如下分治策略：將提供頻繁項集的事務(wù)集壓縮到一棵頻繁模式樹，但仍保留項集關(guān)聯(lián)信息；然后，將這種壓縮后的事務(wù)集分成一組條件事務(wù)集，每個關(guān)聯(lián)一個頻繁項，并分別挖掘每個事務(wù)集。在算法中使用了一種稱為頻繁模式樹（FrequentPatternTree，F(xiàn)P-Tree）的數(shù)據(jù)結(jié)構(gòu)。FP-Tree是一種特殊的前綴樹，由頻繁項頭表和項前綴樹構(gòu)成。FP-Growth算法基于以上的結(jié)構(gòu)加快了整個挖掘過程。FP-Tree是將事務(wù)集中的各個項按照支持度排序后，把每個事務(wù)中的項按降序依次插入到一棵以null為根結(jié)點的樹中，同時在每個結(jié)點處記錄該結(jié)點出現(xiàn)的支持度。構(gòu)建FP-TreeFP-growth算法通過構(gòu)建FP-Tree來壓縮事務(wù)集中的信息，從而更加有效地產(chǎn)生頻繁項集。FP-Tree其實是一棵前綴樹，按支持度降序排列，支持度越高的頻繁項離根節(jié)點越近，從而使得更多的頻繁項可以共享前綴。表8.5事務(wù)集表8.5表示用于購物籃分析的事務(wù)集。其中，a，b，...，p分別表示事務(wù)集的項。首先，對該事務(wù)集進行一次掃描，計算每一行記錄中各個項的支持度，然后按照支持度降序排列，僅保留頻繁項集，剔除那些低于支持度閾值的項，這里支持度閾值取3，從而得到<(f:4)，(c:4)，(a:3)，(b:3)，(m:3)，(p:3)>（由于支持度計算公式中的分母|D|是不變的，所以僅需要比較公式中的分子）。表8.5中的第3列展示了排序后的結(jié)果。通過下面例子說明FP-Tree的構(gòu)建過程。事務(wù)集如表8.5所示。編號項頻繁項集100f,a,c,d,g,i,m,pf,c,a,m,p200a,b,c,f,l,m,of,c,a,b,m300b,f,h,j,of,b400b,c,k,s,pc,b,p500a,f,c,e,l,p,m,nf,c,a,m,p構(gòu)建FP-Tree第一條記錄<f，c，a，m，p>對應(yīng)于FP-Tree中的第一條分支<(f:1)，(c:1)，(a:1)，(m:1)，(p:1)>，如圖8.2所示。由于第二條記錄<f，c，a，b，m>與第一條記錄有相同的前綴<f，c，a>，因此<f，c，a>的支持度分別加1，同時在(a:2)節(jié)點下添加節(jié)點(b:1)，(m:1)。所以，F(xiàn)P-Tree中的第二條分支是<(f:2)，(c:2)，(a:2)，(h:1)，(m:1)>，如圖8.3所示。第三條記錄<f，b>與前兩條記錄相比，只有一個共同前綴<f>，因此，只需要在(f:3)下添加節(jié)點<b:1>，如圖8.4所示。

圖8.2

第一條記錄

圖8.3

第二條記錄

圖8.4

第三條記錄FP-Tree的根節(jié)點為null，不表示任何項。接下來，對事務(wù)集進行第二次掃描，從而開始構(gòu)建FP-Tree：nullf:1c:1a:1m:1p:1f:2a:2m:1p:1c:2b:1m:1nullf:3a:2m:1p:1c:2b:1m:1b:1null構(gòu)建FP-Tree第四條記錄<c，b，p>與之前所有記錄都沒有共同前綴，因此在根節(jié)點下添加節(jié)點(c:1)，(b:1)，(p:1)，如圖8.5所示。類似地，將第五條記錄<f，c，a，m，p>作為FP-Tree的一個分支，更新相關(guān)節(jié)點的支持度，如圖8.6所示。為了便于對整棵樹進行遍歷，建立一張項的頭表（AnItemHeaderTable）。這張表的第一列是按照降序排列的頻繁項。第二列是指向該頻繁項在FP-Tree中節(jié)點位置的指針。FP-Tree中每一個節(jié)點還有一個指針，用于指向相同名稱的節(jié)點，如圖8.7所示。

圖8.5

第四條記錄

圖8.6

第五條記錄圖8.7FP-Tree構(gòu)建FP-Tree過程：f:3a:2m:1p:1c:2b:1m:1b:1nullc:1p:1b:1f:4a:3m:2p:2c:3b:1m:1b:1nullc:1p:1b:1項頭表項結(jié)點鏈f

c

a

b

m

p構(gòu)建FP-Tree第一遍掃描數(shù)據(jù)，統(tǒng)計事務(wù)集中各項的出現(xiàn)次數(shù)，剔除不滿足要求的項，剩下的項加入頻繁1-項集L，并建立項頭表，按出現(xiàn)次數(shù)由高到低的順序排列元素。第二遍掃描數(shù)據(jù)，對事務(wù)集的每個事務(wù)，從中選出包含在項頭表中的項，將這些項按L的順序排序。將事務(wù)集中每個事務(wù)的頻繁-1項集插入到FP-Tree中。在插入節(jié)點的同時，將各節(jié)點索引到項頭表，把FP-Tree中相同的節(jié)點通過索引鏈接起來。綜上，F(xiàn)P-Tree建立的流程如下：FP-Tree算法描述處理流程：step1：遍歷D，得到頻繁項候選集L和L中每個項的支持度并刪除小于最小支持度的項。對L中的所有頻繁項依照支持度的高低降序排列，得到最終的頻繁-1項集L；step2：創(chuàng)建一個FP-Tree的根節(jié)點Tree，標(biāo)記為“null”；step3：foreach事務(wù)inDdostep4：sortbyorderofL；step5：for頻繁項Astep6：調(diào)用函數(shù)insert_tree(A,Tree)；step7：Endfor輸入事務(wù)集D，最小支持度SUPmin函數(shù)insert_tree()定義如下：insert_tree(A,root)ifroot有孩子節(jié)點N且屬性與A相等thenN.count++；else創(chuàng)建新節(jié)點N；設(shè)置各屬性；N.node-link索引項頭表中對應(yīng)節(jié)點；endif

輸出FP-Tree從FP-Tree中挖掘頻繁模式在FP-Tree中以

p

結(jié)尾的節(jié)點鏈共有兩條，分別是<(f:4)，(c:3)，(a:3)，(m:2)，(p:2)>和<(c:1)，(b:1)，(p:1)>。其中，第一條節(jié)點鏈表表示項清單<f，c，a，m，p>在事務(wù)集中共出現(xiàn)了兩次。需要注意到是，盡管<f，c，a>在第一條節(jié)點鏈中出現(xiàn)了3次，單個項<f>出現(xiàn)了4次，但是它們與p一起出現(xiàn)只有2次，所以在條件FP-Tree中將<(f:4)，(c:3)，(a:3)，(m:2)，(p:2)>記為<(f:2)，(c:2)，(a:2)，(m:2)，(p:2)>。同理，第二條節(jié)點鏈表示項清單<c，b，p>在事務(wù)集中只出現(xiàn)了一次。將p的前綴節(jié)點鏈<(f:2)，(c:2)，(a:2)，(m:2)>和<(c:1)，(b:1)>稱為p的條件模式基（conditionalpatternbase）。將p的條件模式基作為新的事務(wù)集，每一行存儲p的一個前綴節(jié)點鏈，根據(jù)前面構(gòu)建FP-Tree的過程，計算每一行記錄中各種項的支持度，然后按照支持度降序排列，僅保留頻繁項集，剔除那些低于支持度閾值的項，建立一棵新的FP-Tree，這棵樹被稱之為p的條件FP-Tree。如圖8.8所示。圖8.8

p的條件FP-Tree從圖8.8可以看到p的條件FP-Tree中滿足支持度閾值的只剩下一個節(jié)點(c:3)，所以以p結(jié)尾的頻繁項集有(p:3)，(c:3)。由于c的條件模式基為空，所以不需要構(gòu)建c的條件FP-Tree。從頭表的底部開始挖掘FP-Tree中的頻繁模式。nullc:3從FP-Tree中挖掘頻繁模式在FP-Tree中以

m

結(jié)尾的節(jié)點鏈共有兩條，分別是<(f:4)，(c:3)，(a:3)，(m:2)>和<(f:4)，(c:3)，(a:3)，(b:1)，(m:1)>。所以m的條件模式基是<(f:2)，(c:2)，(a:2)>和<(f:1)，(c:1)，(a:1)，(b:1)>。我們將m的條件模式基作為新的事務(wù)集，每一行存儲m的一個前綴節(jié)點鏈，計算每一行記錄中各種項的支持度，然后按照支持度降序排列，僅保留頻繁項集，剔除那些低于支持度閾值的項，建立m的條件FP-Tree，如圖8.9所示。圖8.9

m的條件FP-Tree與p不同，m的條件FP-Tree中有3個節(jié)點，所以需要多次遞歸地挖掘頻繁項集mine(<(f:3),(c:3),(a:3)|(m:3)>)。按照<(a:3),(c:3),(f:3)>的順序遞歸調(diào)用mine(<(f:3),(c:3)|a，m>)，mine(<(f:3)|c,m>)，mine(null|f,m)。由于(m:3)滿足支持度閾值要求，所以以m結(jié)尾的頻繁項集有{(m:3)}。從頭表的底部開始挖掘FP-Tree中的頻繁模式。項頭表項結(jié)點鏈f

c

af:4a:3c:3root從FP-Tree中挖掘頻繁模式基于(a,m)的條件模式如圖8.10所示。圖8.10

節(jié)點(a,m)的條件FP-Tree從圖8.10可以看出，節(jié)點(a,m)的條件FP-Tree有2個節(jié)點，需要進一步遞歸調(diào)用mine(<(f:3)|c,a,m>)和mine(<null|f,a,m>)。進一步遞歸mine(<(f:3)|c,a,m>)生成mine(<null|f,c,a,m>)。因此，以(a,m)結(jié)尾的頻繁項集有{(am:3)，(fam:3)，(cam:3)，(fcam:3)}。從頭表的底部開始挖掘FP-Tree中的頻繁模式。c:3f:3root基于(c,m)條件模式如圖8.11所示。圖8.11節(jié)點(c,m)的條件FP-Tree從圖8.11可以看出，節(jié)點(c,m)的條件FP-Tree只有1個節(jié)點，所以只需要遞歸調(diào)用mine(<null|f,c,m>)。因此，以(c,m)結(jié)尾的頻繁項集有{(cm:3),(fcm:3)}。同理，以(f,m)結(jié)尾的頻繁項集有{(fm:3)}。f:3root從FP-Tree中挖掘頻繁模式在FP-Tree中以

b

結(jié)尾的節(jié)點鏈共有三條，分別是<(f:4),(c:3),(a:3),(b:1)>，<(f:4),(b:1)>和<(c:1),(b:1)>。由于節(jié)點b的條件模式基<(f:1),(c:1),(a:1)>，<(f:1)>和<(c:1)>都不滿足支持度閾值，所以不需要再遞歸。因此，以b結(jié)尾的頻繁項集只有(b:3)。同理可得，以a結(jié)尾的頻繁項集{(fa:3),(ca:3)，(fca:3)，(a:3)}，以c結(jié)尾的頻繁項集{(fc:3)，(c:4)}，以f結(jié)尾的頻繁項集{(f:4)}。頻繁項的挖掘采用自底向上的順序，先由項頭表的最后的一個節(jié)點開始，尋找每一項的條件模式基。根據(jù)項頭表中各項索引，找出全部含有這個項的前綴路徑，對應(yīng)前綴路徑即為這個項的條件模式基。然后依照找出的條件模式基建立條件FP-Tree，對于每一個新建立的條件FP-Tree樹，重復(fù)上述步驟，直到建立的條件FP-Tree為空，或者只存在唯一路徑。若新建立的條件FP-Tree是一個空樹，它的前綴就是頻繁項；若新建立的條件FP-Tree只存在唯一路徑，通過例舉全部有可能的組合，然后將這些組合和該樹的前綴連接就得到了我們需要的頻繁項。從頭表的底部開始挖掘FP-Tree中的頻繁模式。FP-Tree算法描述處理流程：step1：L=null；step2：if(FP-Tree只包含單個路徑P)thenstep3：

foreachX∈Pdostep4：

ComputeX∪L，support(X∪L)=support(X)；step5：

returnL=L∪support>SUPmin的項目集X∪Lstep6：else//包含多個路徑step7：

foreach頻繁項Yin項頭表dostep8：

ComputeX=Y∪L，support(Y∪L)=support(X)；輸入FP-Tree，項集L（初值為空），最小支持度SUPminstep9：

ResearPCBofXandcreateFP-Treestep10：

ifTreeX≠Φthenstep11：

遞歸調(diào)用FP-Growth(TreeX,X)step12：

endifstep13：

endforstep14：endif輸出LFP-Growth算法的Python實現(xiàn)Sklearn庫中沒有FP-Growth算法。例8.4FP-Growth算法的Python實現(xiàn)。importreimportcollectionsimportitertoolsdata=[]data=[['a','b','c','d','e','f','g','h'],['a','f','g'],['b','d','e','f','j'],['a','b','d','i','k'],['a','b','e','g'],['g','b']]data=datasupport=3CountItem=collections.defaultdict(int)forlineindata:#統(tǒng)計item的頻率foriteminline:CountItem[item]+=1#將dict按照頻率從大到小排序,并且刪除掉頻率過小的項a=sorted(CountItem.items(),key=lambdax:x[1],reverse=True)foriinrange(len(a)):ifa[i][1]<support:a=a[:i]breakforiinrange(len(data)):#更新data中每一筆交易的商品順序data[i]=[charforcharindata[i]ifCountItem[char]>=support]data[i]=sorted(data[i],key=lambdax:CountItem[x],reverse=True)classnode:#定義節(jié)點def__init__(self,val,char):#定義當(dāng)前的計數(shù)self.val=val#定義當(dāng)前的字符是多少self.char=char#存儲孩子self.children={}#鏈表，鏈接到另一個孩子處self.next=None#構(gòu)建條件樹時向上搜索

self.father=None#用于鏈表的時候觀察是否已經(jīng)被訪問過了self.visit=0self.nodelink=collections.defaultdict()self.nodelink1=collections.defaultdict()classFPTree():def__init__(self):self.root=node(-1,'root')self.FrequentItem=collections.defaultdict(int)#用來存儲頻繁項集self.res=[]defBuildTree(self,data):#建立FP樹的函數(shù),data以list[list[]]的形式，其中內(nèi)部的list包含了商品的名稱，以字符串表示forlineindata:#取出第一個list，用line來表示root=self.rootforiteminline:#對于列表中的每一項ifitemnotinroot.children.keys():#如果item不在dict中root.children[item]=node(1,item)#創(chuàng)建一個新的節(jié)點root.children[item].father=root#用于從下往上尋找else:root.children[item].val+=1#否則，計數(shù)加1root=root.children[item]#往下走一步#根據(jù)這個root創(chuàng)建鏈表ifiteminself.root.nodelink.keys():#如果這個item在nodelink中已經(jīng)存在了ifroot.visit==0:#如果這個點沒有被訪問過self.root.nodelink1[item].next=rootself.root.nodelink1[item]=self.root.nodelink1[item].nextroot.visit=1#被訪問了else:#如果這個item在nodelink中不存在self.root.nodelink[item]=rootself.root.nodelink1[item]=rootroot.visit=1print('樹建立完成')returnself.rootdefIsSinglePath(self,root):ifnotroot:returnTrueifnotroot.children:returnTruea=list(root.children.values())iflen(a)>1:returnFalseelse:forvalueinroot.children.values():ifself.IsSinglePath(value)==False:returnFalsereturnTrueFP-Growth算法的Python實現(xiàn)defFP_growth(self,Tree,a,HeadTable):#Tree表示樹的根節(jié)點，a用列表表示的頻繁項集,HeadTable用來表示頭表#首先需要判斷這個樹是不是單路徑的，創(chuàng)建一個單路徑函數(shù)IsSinglePath(root)ifself.IsSinglePath(Tree):#如果是單路徑的#對于路徑中的每個組合，記作b，產(chǎn)生模式，b并a，support=b中節(jié)點的最小支持度root,temp=Tree,[]#創(chuàng)建一個空列表來存儲whileroot.children:forchildinroot.children.values():temp.append((child.char,child.val))root=childans=[]#產(chǎn)生每個組合foriinrange(1,len(temp)+1):ans+=list(binations(temp,i))foriteminans:mychar=[char[0]forcharinitem]+amycount=min([count[1]forcountinitem])ifmycount>=support:self.res.append([mychar,mycount])else:#不是單路徑，存在多個路徑root=Tree#對于root頭表中的每一項進行操作HeadTable.reverse()#首先將頭表逆序for(child,count)inHeadTable:#child表示字符，count表示支持度b=[child]+a#新的頻繁模式#構(gòu)造b的條件模式基self.res.append([b,count])tmp=Tree.nodelink[child]#此時為第一個節(jié)點從這個節(jié)點開始找,tmp一直保持在鏈表當(dāng)中data=[]#用來保存條件模式基whiletmp:#當(dāng)tmp一直存在的時候tmpup=tmp#準(zhǔn)備向上走res=[[],tmpup.val]#用來保存條件模式whiletmpup.father:res[0].append(tmpup.char)tmpup=tmpup.fatherres[0]=res[0][::-1]#逆序data.append(res)#條件模式基保存完畢tmp=tmp.nextFP-Growth算法的Python實現(xiàn)#條件模式基構(gòu)造完畢，儲存在data中，下一步是建立b的fp-TreeCountItem=collections.defaultdict(int)#統(tǒng)計詞頻for[tmp,count]indata:foriintmp[:-1]:CountItem[i]+=countforiinrange(len(data)):data[i][0]=[charforcharindata[i][0]ifCountItem[char]>=support]#刪除掉不符合的項data[i][0]=sorted(data[i][0],key=lambdax:CountItem[x],reverse=True)#排序#此時數(shù)據(jù)已經(jīng)準(zhǔn)備好了，我們需要做的就是構(gòu)造條件樹root=node(-1,'root')#創(chuàng)建根節(jié)點，值為-1，字符為rootfor[tmp,count]indata:#item是[list[],count]的形式tmproot=root#定位到根節(jié)點foritemintmp:#對于tmp中的每一個商品ifitemintmproot.children.keys():#如果這個商品已經(jīng)在tmproot的孩子中了tmproot.children[item].val+=count#更新值else:#如果這個商品沒有在tmproot的孩子中tmproot.children[item]=node(count,item)#創(chuàng)建一個新的節(jié)點tmproot.children[item].father=tmproot#方便從下往上找tmproot=tmproot.children[item]#往下走一步#根據(jù)這個root創(chuàng)建鏈表ifiteminroot.nodelink.keys():#這個item在nodelink中存在iftmproot.visit==0:root.nodelink1[item].next=tmprootroot.nodelink1[item]=root.nodelink1[item].nexttmproot.visit=1else:#這個item在nodelink中不存在root.nodelink[item]=tmprootroot.nodelink1[item]=tmproottmproot.visit=1ifroot:#如果新的條件樹不為空NewHeadTable=sorted(CountItem.items(),key=lambdax:x[1],reverse=True)foriinrange(len(NewHeadTable)):ifNewHeadTable[i][1]<support:NewHeadTable=NewHeadTable[:i]breakself.FP_growth(root,b,NewHeadTable)#我們需要創(chuàng)建新的headtable#成功返回條件樹FP-Growth算法的Python實現(xiàn)defPrintTree(self,root):#層次遍歷打印樹ifnotroot:returnres=[]ifroot.children:for(name,child)inroot.children.items():res+=[name+''+str(child.val),self.PrintTree(child)]returnreselse:returnobj=FPTree()root=obj.BuildTree(data)obj.FP_growth(root,[],a)print(obj.res)程序運行結(jié)果如圖8.12所示。圖8.12

例8.4程序運行結(jié)果

FP-Growth算法的Python實現(xiàn)關(guān)聯(lián)規(guī)則相關(guān)概念8.2Apriori算法8.3FP-Growth算法8.4Eclat算法8.5概述8.1關(guān)聯(lián)規(guī)則典型應(yīng)用場景8.6學(xué)習(xí)目標(biāo)5Eclat算法EclatAlgorithm8.5Eclat

算法概述Eclat算法是由Zaki博士2000年提出的，它利用數(shù)據(jù)庫和垂直數(shù)據(jù)格式，采用前綴等價關(guān)系劃分搜索空間，該算法只需要1次掃描數(shù)據(jù)庫，利用數(shù)據(jù)垂直表示形式的優(yōu)勢通過交叉計數(shù)來計算支持度，能夠高效地挖掘出頻繁集。Apriori算法和FP-Growth算法都是從項集格式{TID:itemset}的事務(wù)集中挖掘頻繁模式，其中TID是事務(wù)標(biāo)識符，而itemset是事務(wù)TID中購買的商品。這種數(shù)據(jù)格式稱為水平數(shù)據(jù)格式。數(shù)據(jù)也可以用項-TID集格式{item:TID_set}表示，其中item是項的名稱，而TID_set是包含item的事務(wù)標(biāo)識符的集合，這種數(shù)據(jù)格式稱為垂直數(shù)據(jù)格式。Eclat算法是一種深度優(yōu)先算法,采用垂直數(shù)據(jù)表示形式。例8.5假設(shè)事務(wù)集合D如表8.6所示。假設(shè)用戶的最小支持?jǐn)?shù)為2。表8.6事務(wù)集合DEclat算法生成頻繁項集。(1)水平格式轉(zhuǎn)換成垂直格式，并通過轉(zhuǎn)換后的倒排表可以加快頻繁集生成速度。如表8.7所示。表8.7D垂直格式倒排表(2)候選1-項集如表8.8所示。表8.8候選-1項集由于最小支持?jǐn)?shù)為2，則候選-1項集中都是頻繁-1項集。(3)由頻繁-1項集生成的候選-2項集。通過取每對頻繁項的TID集的交，可以在該數(shù)據(jù)集上進行挖掘。設(shè)最小支持度計數(shù)為2。由于表8.8中的每個項都是頻繁的，因此總共進行10次交運算，導(dǎo)致8個非空2項集，如表8.9所示。表8.9候選-2項集注意，項集｛A,D｝和{C,E}都只包含一個事務(wù)，因此它們都不屬于頻繁2項集的集合。(4)由頻繁-2項集生成的候選3-項集。根據(jù)先驗性質(zhì)，一個給定的3項集是候選3項集，僅當(dāng)它的每一個2項集子集都是頻繁的。這里候選產(chǎn)生過程將產(chǎn)生3個候選3-項集：｛A，B,C｝，｛A,B,D｝和{A,B,E}。通過取這些候選3項集任意對應(yīng)2項集的TID集的交，得到表8.10，其中只有兩個頻繁3項集：｛A,B,C:2｝和｛A,B,E:2｝。表8.10候選3-項集TIDItem

TIDItemT1A,E,BT6C,BT2D,BT7A,CT3C,BT8A,E,C,BT4A,D,B

T9A,C,BT5A,C

ItemTID

ItemTIDAT1,T4,T5,T7,T8,T9DT2,T4BT1,T2,T3,T4,T6,T8,T9ET1,T8CT3,T5,T6,T7,T8,T9

ItemFreq

ItemFreqA6D2B7E2C6

Item子事務(wù)集Freq

Item子事務(wù)集FreqAB{T1,T4,T8,T9}4BD{T2,T4}2AC{T5,T7,T8,T9}4BE{T1,T8}2AD{T4}1CD{}0AE{T1,T8}2CE{T8}1BC{T3,T6,T8,T9}4DE{}0Item子事務(wù)集Freq

Item子事務(wù)集FreqABC{T8,T9}2ABE{T1,T8}2ABD{T4}1

Eclat

算法描述處理流程：step1：通過掃描一次數(shù)據(jù)集D，把水平格式的數(shù)據(jù)轉(zhuǎn)換成垂直格式的TID集；step2：項集的支持度計數(shù)簡單地等于項集的TID集長度；step3：從k=1開始，可以根據(jù)先驗性質(zhì)，使用頻繁k-項集來構(gòu)造候選(k+1)-項集；step4：通過取頻繁k項集的TID集的交，計算對應(yīng)的(k+1)-項集的TID集；step5：重復(fù)該過程，每次k增加1，直到不能再找到頻繁項集或候選項集。輸入數(shù)據(jù)集D，最小支持度閾值minS_port輸出頻繁項集Eclat算法除了在產(chǎn)生候選(k+1)-項集時利用先驗性質(zhì)外，另一個優(yōu)點是不需要掃描數(shù)據(jù)庫來確定(k+1)-項集的支持度（k≥1），這是因為每個k項集的TID集攜帶了計算支持度的完整信息。然而，TID集可能很長，需要大量的內(nèi)存空間，長集合的交運算還需要大量的計算時間。例8.6Eclat算法的Python實現(xiàn)。importnumpyasnpfromitertoolsimportcombinationsdefread_data():dataset=[['牛奶','蔥','豆角','土豆','雞蛋','芹菜'],['蘋果','蔥','豆角','土豆','雞蛋','芹菜'],['牛奶','蘋果','土豆','雞蛋'],['牛奶','芒果','白菜','土豆','芹菜'],['白菜','蔥','芹菜','土豆','芒果','雞蛋']]returndatasetEclat

算法的Python實現(xiàn)#eclat算法defeclat(transactions,min_support=0.35):combos_to_counts={}fortransactionintransactions:#變量交易記錄goods=list(np.unique(transaction))#獲取商品列表length=len(goods)forkinrange(2,length+1):k_combos=list(combinations(goods,k))