Python數(shù)據(jù)挖掘算法與應(yīng)用 課件 第8-10章 關(guān)聯(lián)規(guī)則分析、預(yù)測(cè)模型、深度學(xué)習(xí)簡(jiǎn)介

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)用場(chǎ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ò)程。關(guān)聯(lián)規(guī)則分析于1993年由美國(guó)IBMAlmadenResearchCenter的RakeshAgrawal等人在進(jìn)行市場(chǎng)購(gòu)物籃分析時(shí)首先提出的，用以發(fā)現(xiàn)超市銷售數(shù)據(jù)庫(kù)中的顧客購(gòu)買模式，現(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é)合起來(lái)，對(duì)數(shù)值型字段進(jìn)行處理，將其進(jìn)行動(dòng)態(tài)的分割，或者直接對(duì)原始的數(shù)據(jù)進(jìn)行處理，當(dāng)然數(shù)值型關(guān)聯(lián)規(guī)則中也可以包含種類變量。在單層的關(guān)聯(lián)規(guī)則中，所有變量都沒(méi)有考慮到現(xiàn)實(shí)數(shù)據(jù)是具有多個(gè)不同層次的。在多層的關(guān)聯(lián)規(guī)則中，對(duì)數(shù)據(jù)的多層性已經(jīng)進(jìn)行了充分的考慮。在單維的關(guān)聯(lián)規(guī)則中，只涉及到數(shù)據(jù)的一個(gè)維。換言之，單維關(guān)聯(lián)規(guī)則是處理單個(gè)屬性中的一些關(guān)系。多維的關(guān)聯(lián)規(guī)則中，要處理的數(shù)據(jù)將會(huì)涉及多個(gè)維。換言之，多維關(guān)聯(lián)規(guī)則是處理多個(gè)屬性之間的某些關(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)用場(chǎng)景8.6學(xué)習(xí)目標(biāo)2關(guān)聯(lián)規(guī)則相關(guān)概念RelatedConceptsofAssociationRules8.2基本概念事務(wù)集每一個(gè)事務(wù)（Transaction）T

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

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

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

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

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

Y，如果X是非頻繁項(xiàng)集，則Y也是非頻繁項(xiàng)集；若X

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

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

候選1-項(xiàng)集C1

頻繁1-項(xiàng)集L1雞蛋4

雞蛋4面包2

面包2西紅柿2

西紅柿2蔥1

牛奶4蒜1

豆角2牛奶4

豆角2

芹菜1

(3)通過(guò)表8.3形成候選3-項(xiàng)集C3。仍然利用minS_port=0.4，可以看出C3集合中的每個(gè)項(xiàng)集都有非頻繁子集，所以創(chuàng)建頻繁3-項(xiàng)集L3為空集，項(xiàng)集生成過(guò)程結(jié)束。如表8.4所示。表8.4產(chǎn)生3-項(xiàng)頻繁集由此可知，最大頻繁項(xiàng)集為L(zhǎng)2。第二階段，在找出的頻繁項(xiàng)集的基礎(chǔ)上產(chǎn)生強(qiáng)關(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-項(xiàng)集C3

頻繁3-項(xiàng)集L3雞蛋、牛奶、西紅柿1

空集

雞蛋、牛奶、豆角1

雞蛋、西紅柿、豆角1

雞蛋、牛奶、面包1

候選2-項(xiàng)集C2

頻繁2-項(xiàng)集L2雞蛋、面包1

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

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

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

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

面包、牛奶2

面包、豆角0

西紅柿、牛奶1

西紅柿、豆角1

牛奶、豆角1

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

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

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

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

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

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

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

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

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

//對(duì)每個(gè)頻繁項(xiàng)集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實(shí)現(xiàn)L,suppData=apriori(df,min_support=0.5,use_colnames=False,max_len=None)Apriori()函數(shù)常用形式為：參數(shù)說(shuō)明：(1)df：表示給定的數(shù)據(jù)集。(2)min_support：表示給定的最小支持度。(3)use_colnames：默認(rèn)False，表示返回的項(xiàng)集，用編號(hào)顯示。如果值為True則直接顯示項(xiàng)名稱。(4)max_len：默認(rèn)是None，表示最大項(xiàng)組合數(shù)，不做限制。如果只需要計(jì)算兩個(gè)項(xiàng)集，可將這個(gè)值設(shè)置為2。返回值：(1)L：返回頻繁項(xiàng)集。(2)suppData：返回頻繁項(xiàng)集的相應(yīng)支持度。Sklearn庫(kù)中沒(méi)有Apriori算法。但是可以采用Python的第三方庫(kù)實(shí)現(xiàn)Aprior算法發(fā)掘關(guān)聯(lián)規(guī)則。相關(guān)的庫(kù)有mlxtend機(jī)器學(xué)習(xí)包等，首先需要導(dǎo)入包含Apriori算法的mlxtend包：pipinstallmlxtend。例8.2用Python實(shí)現(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={}#頻繁項(xiàng)集和支持?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:#未達(dá)到最小支持?jǐn)?shù)errorKeys.append(key)else:L[key]=supportforkeyinerrorKeys:L.pop(key)returnL'''根據(jù)頻繁(k-1)項(xiàng)集自身連接產(chǎn)生候選K項(xiàng)集Ck并剪去不符合條件的候選L—頻繁K-1項(xiàng)集'''defgetCByL(L,k):len_L=len(L)#獲取L的頻繁項(xiàng)集數(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#最小置信度

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

#獲取強(qiáng)關(guān)聯(lián)規(guī)則big_rule=get_rule(L,support_data,min_support,min_conf)獲取強(qiáng)關(guān)聯(lián)規(guī)則print('==========所有的頻繁項(xiàng)集如下===========')forlinL:forl_iteminl:print(l_item,end='')print('支持度為：%f'%l[l_item])print('===========================================')forruleinbig_rule:print(rule[0],'==>',rule[1],'\t\tconf=',rule[2])程序運(yùn)行結(jié)果如圖8.1所示。圖8.1例8.2程序運(yùn)行結(jié)果例8.3Apriori算法的Python實(shí)現(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è)置支持度求頻繁項(xiàng)集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)用場(chǎng)景8.6學(xué)習(xí)目標(biāo)4FP-Growth算法FP-GrowthAlgorithm8.4FP-Growth算法Apriori算法在產(chǎn)生頻繁項(xiàng)集前需要對(duì)事務(wù)集進(jìn)行多次掃描，同時(shí)產(chǎn)生大量的候選頻繁集，這就使Apriori算法時(shí)間和空間復(fù)雜度較大。但是Apriori算法中有一個(gè)很重要的性質(zhì)：頻繁項(xiàng)集的所有非空子集都必須也是頻繁的。但是Apriori算法在挖掘長(zhǎng)頻繁模式的時(shí)候性能往往低下，韓嘉煒等人在2000年提出了一種稱為頻繁模式增長(zhǎng)（Frequent-PatternGrowth，F(xiàn)P-Growth）方法，將數(shù)據(jù)集存儲(chǔ)在一個(gè)特定的稱作FP-Tree的結(jié)構(gòu)之后發(fā)現(xiàn)頻繁項(xiàng)集或頻繁項(xiàng)對(duì)，即常在一塊出現(xiàn)的項(xiàng)的集合FP-Tree。FP-Growth算法比Apriori算法效率更高，在整個(gè)算法執(zhí)行過(guò)程中，只需遍歷事務(wù)集2次，就能夠完成頻繁模式發(fā)現(xiàn)。其發(fā)現(xiàn)頻繁項(xiàng)集的基本過(guò)程如下：(1)構(gòu)建FP樹(shù)；(2)從FP樹(shù)中挖掘頻繁項(xiàng)集。FP-Growth算法采用的策略FP-Growth算法采取如下分治策略：將提供頻繁項(xiàng)集的事務(wù)集壓縮到一棵頻繁模式樹(shù)，但仍保留項(xiàng)集關(guān)聯(lián)信息；然后，將這種壓縮后的事務(wù)集分成一組條件事務(wù)集，每個(gè)關(guān)聯(lián)一個(gè)頻繁項(xiàng)，并分別挖掘每個(gè)事務(wù)集。在算法中使用了一種稱為頻繁模式樹(shù)（FrequentPatternTree，F(xiàn)P-Tree）的數(shù)據(jù)結(jié)構(gòu)。FP-Tree是一種特殊的前綴樹(shù)，由頻繁項(xiàng)頭表和項(xiàng)前綴樹(shù)構(gòu)成。FP-Growth算法基于以上的結(jié)構(gòu)加快了整個(gè)挖掘過(guò)程。FP-Tree是將事務(wù)集中的各個(gè)項(xiàng)按照支持度排序后，把每個(gè)事務(wù)中的項(xiàng)按降序依次插入到一棵以null為根結(jié)點(diǎn)的樹(shù)中，同時(shí)在每個(gè)結(jié)點(diǎn)處記錄該結(jié)點(diǎn)出現(xiàn)的支持度。構(gòu)建FP-TreeFP-growth算法通過(guò)構(gòu)建FP-Tree來(lái)壓縮事務(wù)集中的信息，從而更加有效地產(chǎn)生頻繁項(xiàng)集。FP-Tree其實(shí)是一棵前綴樹(shù)，按支持度降序排列，支持度越高的頻繁項(xiàng)離根節(jié)點(diǎn)越近，從而使得更多的頻繁項(xiàng)可以共享前綴。表8.5事務(wù)集表8.5表示用于購(gòu)物籃分析的事務(wù)集。其中，a，b，...，p分別表示事務(wù)集的項(xiàng)。首先，對(duì)該事務(wù)集進(jìn)行一次掃描，計(jì)算每一行記錄中各個(gè)項(xiàng)的支持度，然后按照支持度降序排列，僅保留頻繁項(xiàng)集，剔除那些低于支持度閾值的項(xiàng)，這里支持度閾值取3，從而得到<(f:4)，(c:4)，(a:3)，(b:3)，(m:3)，(p:3)>（由于支持度計(jì)算公式中的分母|D|是不變的，所以僅需要比較公式中的分子）。表8.5中的第3列展示了排序后的結(jié)果。通過(guò)下面例子說(shuō)明FP-Tree的構(gòu)建過(guò)程。事務(wù)集如表8.5所示。編號(hào)項(xiàng)頻繁項(xiàng)集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>對(duì)應(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，同時(shí)在(a:2)節(jié)點(diǎn)下添加節(jié)點(diǎn)(b:1)，(m:1)。所以，F(xiàn)P-Tree中的第二條分支是<(f:2)，(c:2)，(a:2)，(h:1)，(m:1)>，如圖8.3所示。第三條記錄<f，b>與前兩條記錄相比，只有一個(gè)共同前綴<f>，因此，只需要在(f:3)下添加節(jié)點(diǎn)<b:1>，如圖8.4所示。

圖8.2

第一條記錄

圖8.3

第二條記錄

圖8.4

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

圖8.5

第四條記錄

圖8.6

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

c

a

b

m

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

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

p

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

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

m

結(jié)尾的節(jié)點(diǎn)鏈共有兩條，分別是<(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ù)集，每一行存儲(chǔ)m的一個(gè)前綴節(jié)點(diǎn)鏈，計(jì)算每一行記錄中各種項(xiàng)的支持度，然后按照支持度降序排列，僅保留頻繁項(xiàng)集，剔除那些低于支持度閾值的項(xiàng)，建立m的條件FP-Tree，如圖8.9所示。圖8.9

m的條件FP-Tree與p不同，m的條件FP-Tree中有3個(gè)節(jié)點(diǎn)，所以需要多次遞歸地挖掘頻繁項(xiàng)集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é)尾的頻繁項(xiàng)集有{(m:3)}。從頭表的底部開(kāi)始挖掘FP-Tree中的頻繁模式。項(xiàng)頭表項(xiàng)結(jié)點(diǎn)鏈f

c

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

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

b

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

foreachX∈Pdostep4：

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

returnL=L∪support>SUPmin的項(xiàng)目集X∪Lstep6：else//包含多個(gè)路徑step7：

foreach頻繁項(xiàng)Yin項(xiàng)頭表dostep8：

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

ResearPCBofXandcreateFP-Treestep10：

ifTreeX≠Φthenstep11：

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

endifstep13：

endforstep14：endif輸出LFP-Growth算法的Python實(shí)現(xiàn)Sklearn庫(kù)中沒(méi)有FP-Growth算法。例8.4FP-Growth算法的Python實(shí)現(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)計(jì)item的頻率foriteminline:CountItem[item]+=1#將dict按照頻率從大到小排序,并且刪除掉頻率過(guò)小的項(xiàng)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é)點(diǎn)def__init__(self,val,char):#定義當(dāng)前的計(jì)數(shù)self.val=val#定義當(dāng)前的字符是多少self.char=char#存儲(chǔ)孩子self.children={}#鏈表，鏈接到另一個(gè)孩子處self.next=None#構(gòu)建條件樹(shù)時(shí)向上搜索

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

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

FP-Growth算法的Python實(shí)現(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)用場(chǎng)景8.6學(xué)習(xí)目標(biāo)5Eclat算法EclatAlgorithm8.5Eclat

算法概述Eclat算法是由Zaki博士2000年提出的，它利用數(shù)據(jù)庫(kù)和垂直數(shù)據(jù)格式，采用前綴等價(jià)關(guān)系劃分搜索空間，該算法只需要1次掃描數(shù)據(jù)庫(kù)，利用數(shù)據(jù)垂直表示形式的優(yōu)勢(shì)通過(guò)交叉計(jì)數(shù)來(lái)計(jì)算支持度，能夠高效地挖掘出頻繁集。Apriori算法和FP-Growth算法都是從項(xiàng)集格式{TID:itemset}的事務(wù)集中挖掘頻繁模式，其中TID是事務(wù)標(biāo)識(shí)符，而itemset是事務(wù)TID中購(gòu)買的商品。這種數(shù)據(jù)格式稱為水平數(shù)據(jù)格式。數(shù)據(jù)也可以用項(xiàng)-TID集格式{item:TID_set}表示，其中item是項(xiàng)的名稱，而TID_set是包含item的事務(wù)標(biāo)識(shí)符的集合，這種數(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算法生成頻繁項(xiàng)集。(1)水平格式轉(zhuǎn)換成垂直格式，并通過(guò)轉(zhuǎn)換后的倒排表可以加快頻繁集生成速度。如表8.7所示。表8.7D垂直格式倒排表(2)候選1-項(xiàng)集如表8.8所示。表8.8候選-1項(xiàng)集由于最小支持?jǐn)?shù)為2，則候選-1項(xiàng)集中都是頻繁-1項(xiàng)集。(3)由頻繁-1項(xiàng)集生成的候選-2項(xiàng)集。通過(guò)取每對(duì)頻繁項(xiàng)的TID集的交，可以在該數(shù)據(jù)集上進(jìn)行挖掘。設(shè)最小支持度計(jì)數(shù)為2。由于表8.8中的每個(gè)項(xiàng)都是頻繁的，因此總共進(jìn)行10次交運(yùn)算，導(dǎo)致8個(gè)非空2項(xiàng)集，如表8.9所示。表8.9候選-2項(xiàng)集注意，項(xiàng)集｛A,D｝和{C,E}都只包含一個(gè)事務(wù)，因此它們都不屬于頻繁2項(xiàng)集的集合。(4)由頻繁-2項(xiàng)集生成的候選3-項(xiàng)集。根據(jù)先驗(yàn)性質(zhì)，一個(gè)給定的3項(xiàng)集是候選3項(xiàng)集，僅當(dāng)它的每一個(gè)2項(xiàng)集子集都是頻繁的。這里候選產(chǎn)生過(guò)程將產(chǎn)生3個(gè)候選3-項(xiàng)集：｛A，B,C｝，｛A,B,D｝和{A,B,E}。通過(guò)取這些候選3項(xiàng)集任意對(duì)應(yīng)2項(xiàng)集的TID集的交，得到表8.10，其中只有兩個(gè)頻繁3項(xiàng)集：｛A,B,C:2｝和｛A,B,E:2｝。表8.10候選3-項(xiàng)集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：通過(guò)掃描一次數(shù)據(jù)集D，把水平格式的數(shù)據(jù)轉(zhuǎn)換成垂直格式的TID集；step2：項(xiàng)集的支持度計(jì)數(shù)簡(jiǎn)單地等于項(xiàng)集的TID集長(zhǎng)度；step3：從k=1開(kāi)始，可以根據(jù)先驗(yàn)性質(zhì)，使用頻繁k-項(xiàng)集來(lái)構(gòu)造候選(k+1)-項(xiàng)集；step4：通過(guò)取頻繁k項(xiàng)集的TID集的交，計(jì)算對(duì)應(yīng)的(k+1)-項(xiàng)集的TID集；step5：重復(fù)該過(guò)程，每次k增加1，直到不能再找到頻繁項(xiàng)集或候選項(xiàng)集。輸入數(shù)據(jù)集D，最小支持度閾值minS_port輸出頻繁項(xiàng)集Eclat算法除了在產(chǎn)生候選(k+1)-項(xiàng)集時(shí)利用先驗(yàn)性質(zhì)外，另一個(gè)優(yōu)點(diǎn)是不需要掃描數(shù)據(jù)庫(kù)來(lái)確定(k+1)-項(xiàng)集的支持度（k≥1），這是因?yàn)槊總€(gè)k項(xiàng)集的TID集攜帶了計(jì)算支持度的完整信息。然而，TID集可能很長(zhǎng)，需要大量的內(nèi)存空間，長(zhǎng)集合的交運(yùn)算還需要大量的計(jì)算時(shí)間。例8.6Eclat算法的Python實(shí)現(xiàn)。importnumpyasnpfromitertoolsimportcombinationsdefread_data():dataset=[['牛奶','蔥','豆角','土豆','雞蛋','芹菜'],['蘋果','蔥','豆角','土豆','雞蛋','芹菜'],['牛奶','蘋果','土豆','雞蛋'],['牛奶','芒果','白菜','土豆','芹菜'],['白菜','蔥','芹菜','土豆','芒果','雞蛋']]returndatasetEclat

算法的Python實(shí)現(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))