第8章 頻繁模式挖掘

五邑大學(xué)計(jì)算機(jī)學(xué)院何國輝數(shù)據(jù)倉庫與數(shù)據(jù)挖掘

DataWarehouseandDataMining2/5/20231數(shù)據(jù)倉庫與數(shù)據(jù)挖掘

DataWarehouseandDataMining第八章頻繁模式挖掘2/5/20232頻繁模式(frequentpattern)是指在數(shù)據(jù)集中頻繁出現(xiàn)的模式?，F(xiàn)實(shí)生活中存在多種類型的頻繁模式，包括頻繁項(xiàng)集、頻繁子序列（又稱序列模式）和頻繁子結(jié)構(gòu)。8.0

基本概念2/5/20233幾個(gè)概念。頻繁項(xiàng)集一般是指頻繁地在事務(wù)數(shù)據(jù)集中一起出現(xiàn)的商品的集合，如小賣部中被許多顧客頻繁地一起購買的牛奶和面包。頻繁子序列，如顧客傾向于先購買便攜機(jī)，再購買數(shù)碼相機(jī)，然后再購買內(nèi)存卡這樣的模式就是一個(gè)（頻繁）序列模式。8.0

基本概念（續(xù)）2/5/20234頻繁子結(jié)構(gòu)是指從圖集合中挖掘頻繁子圖模式。子結(jié)構(gòu)可能涉及不同的結(jié)構(gòu)形式（例如，圖、樹或格），可以與項(xiàng)集或子序列結(jié)合在一起。如果一個(gè)子結(jié)構(gòu)頻繁地出現(xiàn)，則稱它為（頻繁）子結(jié)構(gòu)模式。8.0

基本概念（續(xù)）2/5/202358.0

基本概念（續(xù)）頻繁項(xiàng)集挖掘是頻繁模式挖掘的基礎(chǔ)。2/5/20236關(guān)聯(lián)規(guī)則(AssociationRuleMining)挖掘是數(shù)據(jù)挖掘中最活躍的研究方法之一。關(guān)聯(lián)規(guī)則挖掘的目的：找出數(shù)據(jù)庫中不同數(shù)據(jù)項(xiàng)集之間隱藏的關(guān)聯(lián)關(guān)系。

8.1

頻繁項(xiàng)集和關(guān)聯(lián)規(guī)則2/5/20237最早是由R.Agrawal等人在1993年提出的。其目的是為了發(fā)現(xiàn)超市交易數(shù)據(jù)庫中不同商品之間的關(guān)聯(lián)關(guān)系。一個(gè)典型的關(guān)聯(lián)規(guī)則的例子是：70%購買了牛奶的顧客將傾向于同時(shí)購買面包。經(jīng)典的關(guān)聯(lián)規(guī)則挖掘算法：Apriori算法和FP-growth算法。

8.1

頻繁項(xiàng)集和關(guān)聯(lián)規(guī)則（續(xù)）2/5/202381.購物籃分析－引發(fā)關(guān)聯(lián)規(guī)則挖掘的例子

問題：“什么商品組或集合顧客多半會(huì)在一次購物中同時(shí)購買？”購物籃分析：設(shè)全域?yàn)樯痰瓿鍪鄣纳唐返募希错?xiàng)目全集），一次購物購買（即事務(wù)）的商品為項(xiàng)目全集的子集，若每種商品用一個(gè)布爾變量表示該商品的有無，則每個(gè)購物籃可用一個(gè)布爾向量表示。通過對(duì)布爾向量的分析，得到反映商品頻繁關(guān)聯(lián)或同時(shí)購買的購買模式。這些模式可用關(guān)聯(lián)規(guī)則描述。

8.1

頻繁項(xiàng)集合關(guān)聯(lián)規(guī)則（續(xù)）2/5/202398.1.1

問題描述現(xiàn)實(shí)：商店有很多商品，例如“面包”、“牛奶”、“啤酒”等。顧客將把他們需要的商品放入購物籃中。研究的目的：發(fā)現(xiàn)顧客通常會(huì)同時(shí)購買哪些商品。通過上述研究可以幫助零售商合理地?cái)[放商品，引導(dǎo)銷售。2/5/2023108.1.1

問題描述（續(xù)）舉例：某一個(gè)時(shí)間段內(nèi)顧客購物的記錄形成一個(gè)交易數(shù)據(jù)庫，每一條記錄代表一次交易，包含一個(gè)交易標(biāo)識(shí)符（TID）和本次交易所購買的商品。一個(gè)簡(jiǎn)單交易數(shù)據(jù)庫實(shí)例數(shù)據(jù)庫D：TID項(xiàng)001A、C、D002B、C、E003A、B、C、E004B、E2/5/2023118.1.1

問題描述（續(xù)）幾個(gè)基本概念：數(shù)據(jù)項(xiàng)：設(shè)I={i1，i2，…,im}是常數(shù)的集合，其中m是任意有限的正整數(shù)常量，每個(gè)常數(shù)ik（k=1,2，...，m）稱為一個(gè)數(shù)據(jù)項(xiàng)。項(xiàng)集：由I中的數(shù)據(jù)項(xiàng)組成的集合，即XI。K-項(xiàng)集：一個(gè)大小為K的項(xiàng)集（包含有K項(xiàng)，如{A、B}為2-項(xiàng)集，{A、C、D}為3-項(xiàng)集）。一個(gè)交易T：是由在I中的數(shù)據(jù)項(xiàng)所構(gòu)成的集合，即TI。2/5/2023128.1.1

問題描述（續(xù)）【定義1】以商場(chǎng)交易數(shù)據(jù)庫為例，形式化地描述關(guān)聯(lián)規(guī)則：設(shè)I={i1，i2，…,im}是項(xiàng)的集合，表示各種商品的集合；D={t1，t2，…,tn}為交易集，表示每筆交易的集合（是全體事務(wù)的集合）。其中每一個(gè)事務(wù)T都是項(xiàng)的集合，且有TI。每個(gè)事務(wù)都有一個(gè)相關(guān)的唯一標(biāo)識(shí)符和它對(duì)應(yīng)，也就是事務(wù)標(biāo)識(shí)符或TID。2/5/2023138.1.1

問題描述（續(xù)）設(shè)X為一個(gè)由多個(gè)項(xiàng)目構(gòu)成的集合，稱為項(xiàng)集，如001中的{A、C、D}，當(dāng)且僅當(dāng)XT時(shí)我們說事務(wù)T包含X。2/5/2023148.1.1

問題描述（續(xù)）項(xiàng)集X在在事務(wù)數(shù)據(jù)庫DB中出現(xiàn)的次數(shù)占總事務(wù)的百分比叫做項(xiàng)集的支持度。如果項(xiàng)集的支持度超過用戶給定的最小支持度閾值，就稱該項(xiàng)集是頻繁項(xiàng)集（或大項(xiàng)集）。2/5/2023158.1.1

問題描述（續(xù)）關(guān)聯(lián)規(guī)則關(guān)聯(lián)規(guī)則是形如XY的蘊(yùn)含式，其中XI，YI且XY=，則X稱為規(guī)則的條件，Y稱為規(guī)則的結(jié)果。如果事務(wù)數(shù)據(jù)庫D中有s%的事務(wù)包含XY，則稱關(guān)聯(lián)規(guī)則XY的支持度為s%。支持度是指項(xiàng)集X和Y在數(shù)據(jù)庫D中同時(shí)出現(xiàn)的概率。2/5/2023168.1.1

問題描述（續(xù)）【定義2】關(guān)聯(lián)規(guī)則XY對(duì)事務(wù)集D的支持度（support）定義為D中包含有事務(wù)X和Y的百分比。關(guān)聯(lián)規(guī)則XY對(duì)事務(wù)集合D的置信度（confidence）定義為D中包含有X的事務(wù)數(shù)與同時(shí)包含Y的百分比。即：

support(XY)＝(包含X和Y的事務(wù)數(shù)/事務(wù)總數(shù))×100％

confidence(XY)＝(包含X和Y的事務(wù)數(shù)/包含X的事務(wù)數(shù))×100％2/5/2023178.1.1

問題描述（續(xù)）【例8.1】某顧客購物的交易數(shù)據(jù)庫總交易數(shù)為5。2/5/2023188.1.1

問題描述（續(xù)）【例8.1】相關(guān)的支持度和置信度。

support(XY)＝(包含X和Y的事務(wù)數(shù)/事務(wù)總數(shù))×100％

confidence(XY)＝(包含X和Y的事務(wù)數(shù)/包含X的事務(wù)數(shù))×100％2/5/2023198.1.1

問題描述（續(xù)）頻度：由于分母相同，有時(shí)僅用分子表示，即項(xiàng)集在數(shù)據(jù)庫中出現(xiàn)的次數(shù)來代表支持度。通過支持度和置信度作為評(píng)分函數(shù)，給出了對(duì)模式進(jìn)行評(píng)價(jià)的一個(gè)量化標(biāo)準(zhǔn)。2/5/2023208.1.1

問題描述（續(xù)）進(jìn)行關(guān)聯(lián)規(guī)則挖掘時(shí)，要求用戶給出兩個(gè)閾值：最小支持度（頻度）s；最小置信度c。表示：

support(XY)>＝min_sup

confidence(XY)>＝min_conf

的關(guān)聯(lián)規(guī)則稱為強(qiáng)規(guī)則；否則稱為弱規(guī)則。數(shù)據(jù)挖掘主要就是對(duì)強(qiáng)規(guī)則的挖掘。通過設(shè)置最小支持度和最小置信度可以了解某些數(shù)據(jù)之間的關(guān)聯(lián)程度。2/5/2023218.1.1

問題描述（續(xù)）關(guān)聯(lián)規(guī)則挖掘就是要從大量的潛在的規(guī)則庫中尋找出滿足支持度（頻度）和置信度閾值的所有規(guī)則。2/5/2023228.1.1

問題描述（續(xù)）舉例：一個(gè)食品連鎖店保留著每周的事務(wù)記錄，其中每一條事務(wù)表示在一項(xiàng)收款機(jī)業(yè)務(wù)中賣出的項(xiàng)目。連鎖店的管理會(huì)收到一個(gè)事務(wù)匯總報(bào)告，報(bào)告表明了每種項(xiàng)目的銷售量是多少。此外，他們要定期了解哪些項(xiàng)目經(jīng)常被顧客一起購買。他們發(fā)現(xiàn)顧客購買了花生醬后，100%地會(huì)購買面包。而且，顧客購買了花生醬后，有33%也購買果凍。不過，所有事務(wù)中大約只有50%包含花生醬。2/5/2023238.1.1

問題描述（續(xù)）被用于在其中尋找關(guān)聯(lián)規(guī)則的數(shù)據(jù)庫可以看作為一個(gè)元組集合，每個(gè)元組包含一組項(xiàng)目。一個(gè)元組可能是： {花生醬、面包、果凍}包含三個(gè)項(xiàng)目：花生醬、面包、果凍每個(gè)項(xiàng)目表示購買的一種產(chǎn)品一個(gè)元組是一次購買的產(chǎn)品列表2/5/2023248.1.1

問題描述（續(xù)）樣本數(shù)據(jù)庫演示關(guān)聯(lián)規(guī)則的樣本數(shù)據(jù)事務(wù)項(xiàng)目t1面包、果凍、花生醬t2面包、花生醬t3面包、牛奶、花生醬t4啤酒、面包t5啤酒、牛奶2/5/2023258.1.1

問題描述（續(xù)）找出的所有項(xiàng)目集合的支持度集合支持度集合支持度啤酒40啤酒、面包、牛奶0面包80啤酒、面包、花生醬0果凍20啤酒、果凍、牛奶0牛奶40啤酒、果凍、花生醬0花生醬60啤酒、牛奶、花生醬0啤酒、面包20面包、果凍、牛奶0啤酒、果凍0面包、果凍、花生醬20啤酒、牛奶20面包、牛奶、花生醬20啤酒、花生醬0果凍、牛奶、花生醬0面包、果凍、20啤酒、面包、果凍、牛奶0面包、果凍20啤酒、面包、果凍、花生醬0面包、花生醬60啤酒、面包、牛奶、花生醬0果凍、牛奶0啤酒、果凍、牛奶、花生醬0果凍、花生醬20面包、果凍、牛奶、花生醬0牛奶、花生醬20啤酒、面包、果凍、牛奶、花生醬0啤酒、面包、果凍02/5/2023268.1.1

問題描述（續(xù)）問題發(fā)現(xiàn)：項(xiàng)目的個(gè)數(shù)成指數(shù)增長(zhǎng)：從5個(gè)項(xiàng)目的集合得到31個(gè)項(xiàng)目集合（忽略空集）關(guān)聯(lián)規(guī)則挖掘過程：第一步：尋找頻繁項(xiàng)集。根據(jù)定義，這些項(xiàng)集出現(xiàn)的頻度不小于預(yù)先定義的最小額度。---較難第二步：由頻繁項(xiàng)集產(chǎn)生關(guān)聯(lián)規(guī)則。根據(jù)定義，這些規(guī)則必須滿足最小支持度和最小置信度。--較易2/5/2023278.1.2

關(guān)聯(lián)規(guī)則分類購物籃分析只是關(guān)聯(lián)規(guī)則挖掘的一種形式。根據(jù)不同的分類標(biāo)準(zhǔn)，關(guān)聯(lián)規(guī)則有多種分類方法：根據(jù)規(guī)則中所處理的數(shù)據(jù)類型分類根據(jù)規(guī)則中涉及的數(shù)據(jù)維數(shù)分類根據(jù)規(guī)則中數(shù)據(jù)的抽象層次分類其它2/5/2023281.

根據(jù)規(guī)則中所處理的數(shù)據(jù)類型分類根據(jù)規(guī)則中所處理的數(shù)據(jù)類型，可以分為：布爾關(guān)聯(lián)規(guī)則，也稱為二值關(guān)聯(lián)規(guī)則，處理的數(shù)據(jù)都是離散的。如：尿布啤酒。量化關(guān)聯(lián)規(guī)則：在關(guān)聯(lián)規(guī)則中加入數(shù)量信息得到的規(guī)則。如：職業(yè)=“學(xué)生”收入=“0...1000”。數(shù)值類型2/5/2023292.

根據(jù)規(guī)則中涉及的數(shù)據(jù)維數(shù)分類根據(jù)規(guī)則中涉及的數(shù)據(jù)維數(shù)，可以分為：?jiǎn)尉S關(guān)聯(lián)規(guī)則，只涉及數(shù)據(jù)表的一個(gè)字段。如：尿布啤酒。多維關(guān)聯(lián)規(guī)則：涉及數(shù)據(jù)表的多個(gè)字段。如：性別=“女”職業(yè)=“護(hù)士”，是二維關(guān)聯(lián)規(guī)則；又如：年齡=“20...30”∧職業(yè)=“學(xué)生”購買=“電腦”，是三維關(guān)聯(lián)規(guī)則。2/5/2023303.

根據(jù)規(guī)則中數(shù)據(jù)的抽象層次分類根據(jù)規(guī)則中數(shù)據(jù)的抽象層次，可以分為：?jiǎn)螌雨P(guān)聯(lián)規(guī)則，所有的變量都是細(xì)節(jié)數(shù)據(jù)，沒有層次之分，如：IBM臺(tái)式機(jī)HP打印機(jī)。多層關(guān)聯(lián)規(guī)則：發(fā)生關(guān)聯(lián)的數(shù)據(jù)可能位于同一層次，也可能位于不同的層次。如：臺(tái)式機(jī)HP打印機(jī)。2/5/2023314.

其它可以對(duì)關(guān)聯(lián)規(guī)則施加語義約束，以便限制規(guī)則左部或者右部必須包含某些字段。后續(xù)章節(jié)將著重介紹布爾關(guān)聯(lián)規(guī)則挖掘的兩類具有代表性的算法。2/5/2023328.1.3

關(guān)聯(lián)規(guī)則挖掘的經(jīng)典算法AprioriR.Agrawal等人于1993年首先提出了挖掘顧客交易數(shù)據(jù)庫中項(xiàng)集間的關(guān)聯(lián)規(guī)則問題，給出了形式化定義和算法AIS，但該算法影響不大。R.Agrawal等人又于1994年提出了著名的Apriori算法。2/5/2023338.1.3

關(guān)聯(lián)規(guī)則挖掘的經(jīng)典算法Apriori（續(xù)）Apriori算法是一種最有影響的挖掘布爾關(guān)聯(lián)規(guī)則大（頻繁）項(xiàng)目集的算法。它使用一種稱作逐層搜索的迭代算法，通過k-項(xiàng)集用于探索（k+1）-項(xiàng)集。已經(jīng)為大部分商業(yè)產(chǎn)品所使用。2/5/2023341.

Apriori算法描述關(guān)聯(lián)規(guī)則挖掘過程：第一步：尋找頻繁項(xiàng)集。根據(jù)定義，這些項(xiàng)集出現(xiàn)的頻度不小于預(yù)先定義的最小額度。---較難第二步：由頻繁項(xiàng)集產(chǎn)生關(guān)聯(lián)規(guī)則。根據(jù)定義，這些規(guī)則必須滿足最小支持度和最小置信度。--較易找出滿足定義的大項(xiàng)目集從大項(xiàng)目集（頻繁項(xiàng)目集）生成關(guān)聯(lián)規(guī)則2/5/2023351.

Apriori算法描述（續(xù)）上述兩步工作中第二步比較容易。目前主要研究重點(diǎn)：如何快速地找出所有頻繁項(xiàng)集。--核心2/5/202336（1）

尋找頻繁項(xiàng)集找出大項(xiàng)目集的算法可以很簡(jiǎn)單，但代價(jià)很高。簡(jiǎn)單的方法是：對(duì)出現(xiàn)在事務(wù)中的所有項(xiàng)目集進(jìn)行計(jì)數(shù)。給定一個(gè)大小為m的項(xiàng)目集合，共有2m個(gè)子集，去掉空集，則潛在的大項(xiàng)目集數(shù)為2m-1。隨著項(xiàng)目數(shù)的增多，潛在的大項(xiàng)目集數(shù)成爆炸性增長(zhǎng)。（當(dāng)m=5，為31個(gè)；當(dāng)m=30，變成1073741823個(gè)）解決問題的難點(diǎn)：如何高效確定所有大項(xiàng)目集。大部分關(guān)聯(lián)規(guī)則算法都利用巧妙的方法來減少要計(jì)數(shù)的項(xiàng)目集。2/5/202337（1）

尋找頻繁項(xiàng)集（續(xù)）【公理1】：如果一個(gè)項(xiàng)集S是頻繁的（項(xiàng)集S的出現(xiàn)頻度大于最小頻度），那么S的任意非空子集也是頻繁的。反之，如果一個(gè)項(xiàng)集S的某個(gè)非空子集不是頻繁的，則這個(gè)項(xiàng)集也不可能是頻繁的。舉例：如果一個(gè)交易包含{A、B}，則它必然也包含{A、B}的所有子集；反過來，如果{A}或{B}不是頻繁項(xiàng)集，即{A}或{B}的出現(xiàn)頻度小于最小頻度，則{A、B}的出現(xiàn)頻度也一定小于最小頻度，因此{(lán)A、B}也不可能是頻繁項(xiàng)集。2/5/202338（1）

尋找頻繁項(xiàng)集（續(xù)）【結(jié)論一】：假設(shè)項(xiàng)集{A、B}具有一個(gè)非頻繁子集{A}，則根據(jù)【公理1】可知，{A、B}不可能是頻繁項(xiàng)集?！绢l繁項(xiàng)集（大項(xiàng)目集）的性質(zhì)】：大項(xiàng)目集的任一子集也一定是大的。大項(xiàng)目集也稱作是向下封閉的，如果一個(gè)項(xiàng)目集滿足最小支持度的要求，其所有的子集也滿足這一要求。2/5/202339（1）

尋找頻繁項(xiàng)集（續(xù)）其逆命題：如果知道一個(gè)項(xiàng)目集是小的，就不需要生成它的任何超集來作為它的候選集，因?yàn)樗鼈円惨欢ㄊ切〉?。Apriori性質(zhì)基于如下事實(shí)：根據(jù)定義，如果項(xiàng)集I不滿足最小支持度閾值min_sup，則I不是頻繁的，即sup（I）<min_sup。如果將項(xiàng)A添加到I，則結(jié)果項(xiàng)集（即I∪A）不可能比I更頻繁出現(xiàn)。因此，I∪A也不是頻繁的，即sup（I∪A）<min_sup。頻繁項(xiàng)集的Apriori性質(zhì)用于壓縮搜索空間（剪枝），以提高逐層產(chǎn)生頻繁項(xiàng)集的效率。2/5/202340（1）

尋找頻繁項(xiàng)集（續(xù)）用圖表示上述性質(zhì)，例子中有四個(gè)項(xiàng)目{A，B，C，D}，格中的線表示子集關(guān)系，大項(xiàng)目集的性質(zhì)表明：如果原來的項(xiàng)目集是大的，則在路徑中位于其上的任何集合也一定是大的。ABDCABACADBCBDCD?ABCABDBCDACDABCD項(xiàng)目{ACD}的非空子集是：{AC，AD，CD，A，C，D}{A，B，C，D}項(xiàng)目集的格結(jié)構(gòu)2/5/202341（1）

尋找頻繁項(xiàng)集（續(xù)）如果{A，C，D}是大（頻繁）的，則其每一個(gè)子集也是大的，如果其任何一個(gè)子集是小的，則{A，C，D}也是小的。?ABDCABACADBCBDCDABCABDBCDACDABCD項(xiàng)目{ACD}的非空子集是：{AC，AD，CD，A，C，D}{A，C，D}的子集2/5/202342（1）

尋找頻繁項(xiàng)集（續(xù)）【思路】：先找出所有的頻繁1-項(xiàng)集，以此為基礎(chǔ)，由它們來產(chǎn)生候選的2-項(xiàng)集，通過觀察數(shù)據(jù)（掃描數(shù)據(jù)庫）來計(jì)算它們的頻度，從而找出真正的頻繁2-項(xiàng)集。以此類推，得到其它K-項(xiàng)集。2/5/202343（1）

尋找頻繁項(xiàng)集（續(xù)）【Apriori算法的基本思想】：它使用一種稱作逐層搜索的迭代算法，通過k-項(xiàng)集用于探索（k+1）-項(xiàng)集。2/5/202344（1）

尋找頻繁項(xiàng)集（續(xù)）【Apriori算法描述】：首先，通過掃描數(shù)據(jù)集，產(chǎn)生一個(gè)大的候選數(shù)據(jù)項(xiàng)集,并計(jì)算每個(gè)候選數(shù)據(jù)項(xiàng)C發(fā)生的次數(shù)，然后基于預(yù)先給定的最小支持度生成頻繁1-項(xiàng)集的集合，該集合記作；然后基于和數(shù)據(jù)集中的數(shù)據(jù)，產(chǎn)生頻繁2-項(xiàng)集

；用同樣的方法，直到生成頻繁n-項(xiàng)集，其中已不再可能生成滿足最小支持度的（N+1）－項(xiàng)集。最后，從大數(shù)據(jù)項(xiàng)集中導(dǎo)出規(guī)則。在第一次迭代的第一步中，產(chǎn)生的候選集包含所有1-項(xiàng)集，實(shí)為數(shù)據(jù)庫中所有的項(xiàng)，再計(jì)算各自的支持度。2/5/202345（1）

尋找頻繁項(xiàng)集（續(xù)）【Apriori算法】：在第i趟掃描的過程中，對(duì)Ci進(jìn)行計(jì)數(shù)，通過對(duì)數(shù)據(jù)庫的一次掃描得到每個(gè)候選項(xiàng)集的頻度，只有那些大的候選集被用于生成下一趟掃描的候選集，即用Li生成Ci+1。為了生成大小為i+1的候選，要對(duì)前一趟掃描發(fā)現(xiàn)的大項(xiàng)目集進(jìn)行連接運(yùn)算。表示：Lk*Lk={XY其中X，YLk，|XY|=k–1}2/5/202346（1）

尋找頻繁項(xiàng)集（續(xù)）Apriori算法中的關(guān)鍵步驟是由Lk-1找Lk，該步驟可分為兩步：第1步（連接）：為找Lk，通過Lk-1與自己連接產(chǎn)生候選K-項(xiàng)集的集合。將該候選項(xiàng)集的集合記作Ck。設(shè)l1和l2是Lk-1中的項(xiàng)集，記號(hào)li[j]表示li的第j項(xiàng)。執(zhí)行連接Lk-1和Lk-1，其中Lk-1的元素是可連接，如果它們前（k-2）個(gè)項(xiàng)相同而且第（k-2）項(xiàng)不同（為簡(jiǎn)單計(jì)，設(shè)l1[k-1]<l2[k-1]），即：

l1[1]=l2[1]∧l1[2]=l2[2]∧……∧l1[k-2]=l2[k-2]∧l1[k-1]<l2[k-1]

則Lk-1的元素l1和l2是可連接的。連接l1和l2產(chǎn)生的結(jié)果的項(xiàng)集是l1[1]l1[2]……l1[k-1]l2[k-1]。2/5/202347（1）

尋找頻繁項(xiàng)集（續(xù)）第2步（剪枝）：Ck是Lk的超集，即它的成員可以是也可以不是頻繁的，但所有的頻繁k-項(xiàng)集都包含在Ck中。掃描數(shù)據(jù)庫，確定Ck中每個(gè)候選的計(jì)數(shù)，從而確定Lk。然而，Ck可能很大，這樣所涉及的計(jì)算量就很大。為壓縮Ck，可以用以下辦法使用Apriori性質(zhì)：任何非頻繁的（k-1）-項(xiàng)集都不可能是頻繁k-項(xiàng)集的子集。因此，如果一個(gè)候選k-項(xiàng)集的（k-1）-子集不在Lk-1中，則該候選也不可能是頻繁的，從而可以由Ck中刪除。2/5/202348（1）

尋找頻繁項(xiàng)集（續(xù)）【Apriori算法舉例】：假設(shè)事務(wù)數(shù)據(jù)庫D中有4個(gè)事務(wù)，最小頻度是2，則算法的主要步驟如圖所示。2/5/202349（1）

尋找頻繁項(xiàng)集（續(xù)）Apriori算法是一種自底向上寬度優(yōu)先搜素過程。2/5/202350（2）

由頻繁項(xiàng)集產(chǎn)生關(guān)聯(lián)規(guī)則一旦找出所有的頻繁項(xiàng)集，就可以由它們來產(chǎn)生關(guān)聯(lián)規(guī)則。關(guān)聯(lián)規(guī)則產(chǎn)生的步驟：對(duì)于每個(gè)頻繁項(xiàng)集r，產(chǎn)生r的所有非空子集。對(duì)于r的每個(gè)非空子集s，如果support_count(r)/support_count(s)≧min_conf，則輸出規(guī)則s（r-s）。其中，support_count為支持度，min_conf為置信度。2/5/202351（2）

由頻繁項(xiàng)集產(chǎn)生關(guān)聯(lián)規(guī)則（續(xù)）結(jié)合下圖數(shù)據(jù)庫舉例，產(chǎn)生關(guān)聯(lián)規(guī)則方法。根據(jù)前述計(jì)算得到的頻繁項(xiàng)集為{b、c、e}。獲得所有非空子集{b、c}、{b、e}、{c、e}、、{c}、{e}。演示關(guān)聯(lián)規(guī)則的樣本數(shù)據(jù)TID項(xiàng)目01a、b、d02b、c、e03a、b、c、e04b、e2/5/202352（2）

由頻繁項(xiàng)集產(chǎn)生關(guān)聯(lián)規(guī)則（續(xù)）產(chǎn)生的關(guān)聯(lián)規(guī)則：規(guī)則置信度b∧ce2/2=100%b∧ec2/3=66%c∧eb2/2=100%bc∧e2/4=50%cb∧e2/2=100%eb∧c2/3=66%2/5/2023532.

對(duì)Apriori算法的改進(jìn)Apriori算法的主要缺點(diǎn)：每處理一層就要讀一次數(shù)據(jù)庫。對(duì)于一個(gè)有n個(gè)項(xiàng)目的數(shù)據(jù)集，最壞的情況需要讀n次數(shù)據(jù)庫。為了提高算法效率，需要對(duì)Apriori算法改進(jìn)。人們相繼提出了一些方法，從不同角度對(duì)Apriori算法進(jìn)行改進(jìn)。2/5/202354（1）減少必須分析的候選項(xiàng)集數(shù)量Apriori算法通過在內(nèi)存中為每一個(gè)候選項(xiàng)集設(shè)置一個(gè)計(jì)數(shù)器來計(jì)算頻度。當(dāng)候選項(xiàng)集很多時(shí)將占據(jù)大量?jī)?nèi)存，導(dǎo)致內(nèi)存不夠用，需要盡量減少候選項(xiàng)集數(shù)量。Apriori算法在構(gòu)造Ck+1時(shí)利用Lk進(jìn)行消減，一定程度降低了候選項(xiàng)集數(shù)量，但是對(duì)C2作用不大。2/5/202355（1）減少必須分析的候選項(xiàng)集數(shù)量（續(xù)）PCY算法：通過一種基于哈希的技術(shù)來減少候選集（尤其是C2）的大小。PCY算法思路：整體流程和Apriori算法一樣，但是在計(jì)算每個(gè)1-項(xiàng)集頻度生成L1時(shí)，PCY算法順便生成一個(gè)哈希表。哈希表由若干桶組成，每個(gè)桶存放一組項(xiàng)集和一個(gè)計(jì)數(shù)器，用來記錄通過哈希函數(shù)映射到該桶的項(xiàng)集及其頻度，函數(shù)值相同的項(xiàng)集存放在同一個(gè)桶中。在計(jì)算C2時(shí)，PCY算法利用該哈希表的信息對(duì)C2做進(jìn)一步消減。2/5/202356（1）減少必須分析的候選項(xiàng)集數(shù)量（續(xù)）PCY算法步驟實(shí)現(xiàn)過程：第一趟掃描數(shù)據(jù)庫時(shí)計(jì)算所有1-項(xiàng)集的頻度。對(duì)每個(gè)交易，將其中的數(shù)據(jù)項(xiàng)進(jìn)行兩兩組合，然后哈希到一個(gè)桶中，桶計(jì)數(shù)加1.掃描結(jié)束時(shí)，將頻度大于最小頻度的1-項(xiàng)集放入L1中。進(jìn)行第二趟掃描數(shù)據(jù)庫，完成由L1生成C2。每一個(gè)候選2-項(xiàng)集（i，j）必須滿足兩個(gè)條件：第一，i在L1中，j在L1中；第二，2-項(xiàng)集（i，j）必須哈希到一個(gè)計(jì)數(shù)值大于最小頻度的桶中。2/5/202357（1）減少必須分析的候選項(xiàng)集數(shù)量（續(xù)）PCY算法舉例：假設(shè)哈希是h(i，j)=((orderofi）*10+（orderofj））mod7,。數(shù)據(jù)項(xiàng)a、b、c、d、e的次序（order）分別設(shè)為1、2、3、4、5。2/5/202358（1）減少必須分析的候選項(xiàng)集數(shù)量（續(xù)）PCY算法優(yōu)點(diǎn)：減少了候選集C2的大小。2/5/202359（2）減少數(shù)據(jù)庫掃描的次數(shù)Apriori算法要求多次掃描數(shù)據(jù)庫。如果大項(xiàng)集的最大長(zhǎng)度是k，則需要最多掃描k+1遍數(shù)據(jù)庫。人們提出了多種方法，通過兩次或一次掃描數(shù)據(jù)庫來獲得所有的頻繁項(xiàng)目集。有關(guān)方法：基于采樣的方法基于劃分的方法2/5/202360（2）減少數(shù)據(jù)庫掃描的次數(shù)（續(xù)）基于采樣的方法取主存大小的一個(gè)數(shù)據(jù)庫樣本，運(yùn)用Apriori算法，并且按比例伸縮最小支持度（頻度）s。再對(duì)數(shù)據(jù)庫進(jìn)行一次完整掃描，對(duì)由樣本數(shù)據(jù)庫求得的頻繁項(xiàng)集進(jìn)行驗(yàn)證。2/5/202361（2）減少數(shù)據(jù)庫掃描的次數(shù)（續(xù)）基于劃分的方法將交易數(shù)據(jù)庫D劃分為n塊不想交的部分D1，D2，...Dn（要求每一塊都能夠放在內(nèi)存中），用Apriori算法求出每一塊Di中的所有頻繁項(xiàng)集Li；然后合并所有的Li。再次完整掃描一遍數(shù)據(jù)庫，對(duì)L中的每一項(xiàng)集進(jìn)行驗(yàn)證。2/5/2023628.1.4

關(guān)聯(lián)規(guī)則挖掘的重要算法FP-GrowthApriori算法的特點(diǎn)是要產(chǎn)生候選項(xiàng)集。然后對(duì)候選項(xiàng)集進(jìn)行計(jì)數(shù)，以判斷它們是不是頻繁項(xiàng)集。在某些情況下，這類算法可能會(huì)產(chǎn)生大量候選項(xiàng)集，代價(jià)非常大。Apriori算法的變形雖然使其得到一定程度的改善，但并未根本改觀。迫切需要尋找新的算法。2/5/2023638.1.4

關(guān)聯(lián)規(guī)則挖掘的重要算法FP-Growth（續(xù)）Han等人引入“頻繁模式增長(zhǎng)”（簡(jiǎn)稱FP-增長(zhǎng)）的概念，可以不產(chǎn)生候選就能夠找出所有的頻繁項(xiàng)集。韓家煒現(xiàn)為美國伊利諾伊大學(xué)計(jì)算機(jī)系正教授。韓教授于2003年獲選美國計(jì)算機(jī)協(xié)會(huì)院士（ACMFellow）（Citation:“Forcontributionsinknowledgediscoveryanddatamining”，漢譯：“對(duì)知識(shí)發(fā)現(xiàn)和數(shù)據(jù)挖掘做出貢獻(xiàn)”）。韓教授1978畢業(yè)于鄭州大學(xué)計(jì)算機(jī)科學(xué)系，同年考入中科院研究生，1985年美國威斯康辛大學(xué)計(jì)算機(jī)系博士畢業(yè)。2/5/2023648.1.4

關(guān)聯(lián)規(guī)則挖掘的重要算法FP-Growth（續(xù)）FP-Growth算法的特點(diǎn)把數(shù)據(jù)D壓縮映射到一個(gè)小而緊湊的數(shù)據(jù)結(jié)構(gòu)FP-Tree，即頻繁模式樹中，避免了多次掃描數(shù)據(jù)庫D。利用“模式分段增長(zhǎng)”法避免產(chǎn)生大量的候選集。采用分而治之的方法將數(shù)據(jù)挖掘任務(wù)分解成許多小任務(wù)，從而極大地縮小了搜素空間。2/5/2023658.1.4

關(guān)聯(lián)規(guī)則挖掘的重要算法FP-Growth（續(xù)）【舉例】使用FP-Growth算法重新對(duì)例8.4中圖8.3所示的事務(wù)數(shù)據(jù)庫進(jìn)行關(guān)聯(lián)規(guī)則挖掘，具體步驟分為：構(gòu)造FP-Tree挖掘FP-Tree2/5/2023661.

構(gòu)造FP-Tree對(duì)數(shù)據(jù)庫的第一次掃描與Apriori算法相同，掃描結(jié)束后得到一個(gè)頻繁項(xiàng)（1-項(xiàng)集）集合，以及頻度。設(shè)最小頻度為2（與例8.4相同）。將所有的頻繁1-項(xiàng)集按頻度降序排序，結(jié)果集記作L。則L={b:4，e:3，a:2，c:2}。構(gòu)造FP-Tree：首先創(chuàng)建樹的根節(jié)點(diǎn)，用“null”標(biāo)記。對(duì)數(shù)據(jù)庫做第二次掃描。數(shù)據(jù)庫中每條交易中的數(shù)據(jù)項(xiàng)按L中的次序依次處理（即根據(jù)遞減頻度排序），并對(duì)每個(gè)交易創(chuàng)建一個(gè)分枝。2/5/2023671.

構(gòu)造FP-Tree（續(xù)）所生成的FP-Tree為：2/5/2023681.

構(gòu)造FP-Tree（續(xù)）所生成的FP-Tree為：將對(duì)交易數(shù)據(jù)庫的而頻繁模式挖掘問題轉(zhuǎn)換成針對(duì)該FP-Tree進(jìn)行挖掘的問題。nullc:1b:4a:1e:3c:1a:12/5/2023692.

挖掘FP-Tree構(gòu)造FP-Tree時(shí)是按照1-項(xiàng)集頻度的降序進(jìn)行的，對(duì)構(gòu)造后的FP-Ｔree進(jìn)行挖掘時(shí)，需要按照1-項(xiàng)集頻度的升序進(jìn)行。對(duì)于每一個(gè)1-項(xiàng)集，首先構(gòu)造它的條件數(shù)據(jù)庫。所謂條件數(shù)據(jù)庫，是一個(gè)“子數(shù)據(jù)庫”，由FP-Tree中與該1-項(xiàng)集一起出現(xiàn)的前綴路徑組成。具體實(shí)現(xiàn)：從數(shù)據(jù)項(xiàng)頭表中首先找到該1-項(xiàng)集，然后順著鏈表找到它在樹中出現(xiàn)的位置，每找到一個(gè)位置，則得到從樹根到該位置的一條路徑，該路徑就構(gòu)成了條件數(shù)據(jù)庫中的一部分。2/5/2023702.

挖掘FP-Tree（續(xù)）針對(duì)圖8.6構(gòu)造的FP-Tree樹進(jìn)行挖掘過程：先從L中的最后一個(gè)數(shù)據(jù)項(xiàng)c（按頻度的升序）開始，沿著c的節(jié)點(diǎn)鏈表，首先發(fā)現(xiàn)C出現(xiàn)在FP-Tree的一條分枝<b:1e:1c:1>上，則將該路徑的前綴<b:1e:1>放到c的條件數(shù)據(jù)庫中；再順著c的鏈表走下去，發(fā)現(xiàn)c出現(xiàn)在FP-Tree的另一條分枝<b:1e:1a:1c:1>上，則將該路徑前綴<b:1e:1a:1>放到c的條件數(shù)據(jù)庫中；得到c的條件數(shù)據(jù)庫為{<b:1e:1>，<b:1e:1a:1>}，構(gòu)造出的FP-Tree有兩個(gè)節(jié)點(diǎn)<b:2e:2>，b和e的頻度均不小于2，是頻繁的。2/5/2023712.

挖掘FP-Tree（續(xù)）得到該子數(shù)據(jù)庫生成的頻繁模式{b，e，be}。將其與生成該子數(shù)據(jù)庫的項(xiàng)目c連接后（稱為增長(zhǎng)模式），生成所有包含c的頻繁模式，即{bc：2}，{ec：2}，{bec：2}。依次類推...2/5/2023728.1.5

其它關(guān)聯(lián)規(guī)則挖掘方法前面介紹的關(guān)聯(lián)規(guī)則沒有考慮數(shù)據(jù)對(duì)象的概念層次和蘊(yùn)含多個(gè)謂詞，實(shí)際生活中往往并非如此。如：惠普牌打印機(jī)->打印機(jī)->電子產(chǎn)品；或者數(shù)據(jù)庫中不但記錄了顧客購買商品的名稱，而且還記錄了數(shù)量、單價(jià)等，需要體現(xiàn)多種維度的關(guān)聯(lián)關(guān)系。多層關(guān)聯(lián)規(guī)則多維關(guān)聯(lián)規(guī)則2/5/2023731.

多層關(guān)聯(lián)規(guī)則挖掘方法：一般采用自頂向下的策略，從最一般的概念層（第0層）開始，到較具體的某特定概念層，在每個(gè)概念層上尋找頻繁項(xiàng)集，直到不能找到頻繁項(xiàng)集為止。最小支持度的設(shè)置：采用逐層遞減的支持度設(shè)置策略。2/5/2023742.

多維關(guān)聯(lián)規(guī)則涉及數(shù)據(jù)表的多個(gè)字段。二維關(guān)聯(lián)規(guī)則：如：性別=“女”職業(yè)=“護(hù)士”。三維關(guān)聯(lián)規(guī)則：如：年齡=“20...30”∧職業(yè)=“學(xué)生”購買=“電腦”。2/5/2023758.1.6

關(guān)聯(lián)規(guī)則的興趣度按照前述方法產(chǎn)生的關(guān)聯(lián)規(guī)則并非都有用。舉例：如下是從一個(gè)有5000名學(xué)生的學(xué)校的調(diào)查結(jié)果中進(jìn)行挖掘的實(shí)例。提供早餐的零售商對(duì)這些學(xué)生每天早上所從事的活動(dòng)進(jìn)行了一次調(diào)查。數(shù)據(jù)表明：60%的學(xué)生（3000名學(xué)生）打籃球，75%的學(xué)生（3750名學(xué)生）吃這種早餐，40%的學(xué)生（2000名學(xué)生）既打籃球，也吃這種早餐。那么如果設(shè)minsup為40%，minconf為60%挖掘關(guān)聯(lián)規(guī)則，我們可以得到如下的關(guān)聯(lián)規(guī)則：打籃球吃早餐 （1）2/5/2023768.1.6

關(guān)聯(lián)規(guī)則的興趣度（續(xù)）這條規(guī)則相應(yīng)的置信度為2000/3000=0.66，是錯(cuò)誤的關(guān)聯(lián)規(guī)則，因?yàn)槌栽绮偷膶W(xué)生的比例是75%，大于66%。打籃球和吃早餐實(shí)際上是負(fù)關(guān)聯(lián)的。只憑支持度和置信度閾值未必總能找出符合實(shí)際的規(guī)則。2/5/2023778.1.6

關(guān)聯(lián)規(guī)則的興趣度（續(xù)）為了消除這種誤導(dǎo)的規(guī)則，應(yīng)該在關(guān)聯(lián)規(guī)則AB的置信度超過某個(gè)特定的度量標(biāo)準(zhǔn)時(shí)，定義它為有意義的。因此有如下關(guān)聯(lián)規(guī)則S（A，B）/S（A）-S（B）>d或者：S（A，B）-S（A）*S（B）>k式中d和k是適當(dāng)?shù)牧?。從而提出了興趣度的概念2/5/2023788.1.6

關(guān)聯(lián)規(guī)則的興趣度（續(xù)）興趣度為了刪掉一些無趣的規(guī)則，即避免生成“錯(cuò)覺”的關(guān)聯(lián)規(guī)則，人們定義了興趣度的度量值，通過興趣度來修剪無趣的規(guī)則。今后確定關(guān)聯(lián)規(guī)則可以采用三個(gè)度量值：支持度、置信度、興趣度。2/5/2023798.1.6

關(guān)聯(lián)