第8章 頻繁模式挖掘

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

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

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

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

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

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

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

8.1

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

8.1

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

問題：“什么商品組或集合顧客多半會在一次購物中同時購買？”購物籃分析：設全域為商店出售的商品的集合（即項目全集），一次購物購買（即事務）的商品為項目全集的子集，若每種商品用一個布爾變量表示該商品的有無，則每個購物籃可用一個布爾向量表示。通過對布爾向量的分析，得到反映商品頻繁關聯(lián)或同時購買的購買模式。這些模式可用關聯(lián)規(guī)則描述。

8.1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

support(XY)>＝min_sup

confidence(XY)>＝min_conf

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

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

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

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

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

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

關聯(lián)規(guī)則分類購物籃分析只是關聯(lián)規(guī)則挖掘的一種形式。根據(jù)不同的分類標準，關聯(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ù)類型，可以分為：布爾關聯(lián)規(guī)則，也稱為二值關聯(lián)規(guī)則，處理的數(shù)據(jù)都是離散的。如：尿布啤酒。量化關聯(lián)規(guī)則：在關聯(lián)規(guī)則中加入數(shù)量信息得到的規(guī)則。如：職業(yè)=“學生”收入=“0...1000”。數(shù)值類型2/5/2023292.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

尋找頻繁項集（續(xù)）Apriori算法中的關鍵步驟是由Lk-1找Lk，該步驟可分為兩步：第1步（連接）：為找Lk，通過Lk-1與自己連接產(chǎn)生候選K-項集的集合。將該候選項集的集合記作Ck。設l1和l2是Lk-1中的項集，記號li[j]表示li的第j項。執(zhí)行連接Lk-1和Lk-1，其中Lk-1的元素是可連接，如果它們前（k-2）個項相同而且第（k-2）項不同（為簡單計，設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)生的結果的項集是l1[1]l1[2]……l1[k-1]l2[k-1]。2/5/202347（1）

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

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

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

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

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

由頻繁項集產(chǎn)生關聯(lián)規(guī)則（續(xù)）產(chǎ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.

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

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

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

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

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

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

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

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

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

挖掘FP-Tree（續(xù)）針對圖8.6構造的FP-Tree樹進行挖掘過程：先從L中的最后一個數(shù)據(jù)項c（按頻度的升序）開始，沿著c的節(jié)點鏈表，首先發(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>}，構造出的FP-Tree有兩個節(jié)點<b:2e:2>，b和e的頻度均不小于2，是頻繁的。2/5/2023712.

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

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

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

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

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

關聯(lián)規(guī)則的興趣度（續(xù)）這條規(guī)則相應的置信度為2000/3000=0.66，是錯誤的關聯(lián)規(guī)則，因為吃早餐的學生的比例是75%，大于66%。打籃球和吃早餐實際上是負關聯(lián)的。只憑支持度和置信度閾值未必總能找出符合實際的規(guī)則。2/5/2023778.1.6

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

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

關聯(lián)