五邑大學計算機學院何國輝數據倉庫與數據挖掘

DataWarehouseandDataMining2/5/20231數據倉庫與數據挖掘

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

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

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

基本概念（續）2/5/202358.0

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

8.1

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

8.1

頻繁項集和關聯規則（續）2/5/202381.購物籃分析－引發關聯規則挖掘的例子

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

8.1

頻繁項集合關聯規則（續）2/5/202398.1.1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

support(XY)>＝min_sup

confidence(XY)>＝min_conf

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

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

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

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

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

問題描述（續）找出的所有項目集合的支持度集合支持度集合支持度啤酒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

問題描述（續）問題發現：項目的個數成指數增長：從5個項目的集合得到31個項目集合（忽略空集）關聯規則挖掘過程：第一步：尋找頻繁項集。根據定義，這些項集出現的頻度不小于預先定義的最小額度。---較難第二步：由頻繁項集產生關聯規則。根據定義，這些規則必須滿足最小支持度和最小置信度。--較易2/5/2023278.1.2

關聯規則分類購物籃分析只是關聯規則挖掘的一種形式。根據不同的分類標準，關聯規則有多種分類方法：根據規則中所處理的數據類型分類根據規則中涉及的數據維數分類根據規則中數據的抽象層次分類其它2/5/2023281.

根據規則中所處理的數據類型分類根據規則中所處理的數據類型，可以分為：布爾關聯規則，也稱為二值關聯規則，處理的數據都是離散的。如：尿布啤酒。量化關聯規則：在關聯規則中加入數量信息得到的規則。如：職業=“學生”收入=“0...1000”。數值類型2/5/2023292.

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

根據規則中數據的抽象層次分類根據規則中數據的抽象層次，可以分為：單層關聯規則，所有的變量都是細節數據，沒有層次之分，如：IBM臺式機HP打印機。多層關聯規則：發生關聯的數據可能位于同一層次，也可能位于不同的層次。如：臺式機HP打印機。2/5/2023314.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

尋找頻繁項集（續）Apriori算法中的關鍵步驟是由Lk-1找Lk，該步驟可分為兩步：第1步（連接）：為找Lk，通過Lk-1與自己連接產生候選K-項集的集合。將該候選項集的集合記作Ck。設l1和l2是Lk-1中的項集，記號li[j]表示li的第j項。執行連接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產生的結果的項集是l1[1]l1[2]……l1[k-1]l2[k-1]。2/5/202347（1）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

多維關聯規則涉及數據表的多個字段。二維關聯規則：如：性別=“女”職業=“護士”。三維關聯規則：如：年齡=“20...30”∧職業=“學生”購買=“電腦”。2/5/2023758.1.6

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

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

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

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

關聯