挖掘大型數據庫中的關聯規則第一頁，共六十四頁，編輯于2023年，星期三引言—要挖掘知識的類型概念描述：特征化和比較；關聯規則；分類/預測；聚類分析；其他的數據挖掘任務。2第二頁，共六十四頁，編輯于2023年，星期三

第6章挖掘大型數據庫中的關聯規則第三頁，共六十四頁，編輯于2023年，星期三引言關聯規則挖掘發現大量數據中項集之間有趣的關聯或相關聯系。從大量商業事務記錄中發現有趣的關聯關系，可以幫助許多商務決策的制定，如分類設計、交叉購物和促銷分析等。2第四頁，共六十四頁，編輯于2023年，星期三引言如何從事務DB或關系DB的大量數據中挖掘出關聯規則知識？什么樣的關聯規則才是最有意義的？如何才能使挖掘過程盡快發現有價值的關聯規則知識？這是本章要討論的內容。2第五頁，共六十四頁，編輯于2023年，星期三

第6章6.1關聯規則挖掘6.2由事務數據庫挖掘單維布爾關聯規則6.3由事務數據庫挖掘多層關聯規則6.4由事務數據庫和數據倉庫挖掘多維關聯規則第六頁，共六十四頁，編輯于2023年，星期三學習目的掌握關聯規則挖掘算法--Apriori算法。

理解多層關聯規則挖掘及其方法；

理解多維關聯規則挖掘及其方法。7第七頁，共六十四頁，編輯于2023年，星期三6.1關聯規則挖掘關聯規則挖掘(Associationrulemining)：關聯規則挖掘的主要對象是交易型數據庫，一個交易一般由交易處理時間，一組顧客購買的物品，有時也有顧客標識號組成。關聯規則挖掘用以挖掘一次交易中，物品之間同時出現的規律的知識模式，以反映顧客的購買行為。更確切的說，關聯規則是通過量化的數字來描述物品X的出現對物品Y的出現有多大的影響。第八頁，共六十四頁，編輯于2023年，星期三以零售業為例，通過對銷售數據的關聯分析，體育用品商店可以發現隱含在數據中的規律：

“購買籃球的顧客中有70%的人同時購買籃球運動服，所有交易中有40%的人同時購買籃球和籃球運動服”

等等。

關聯規則挖掘第九頁，共六十四頁，編輯于2023年，星期三

購物籃分析購物籃分析是關聯規則挖掘的最初形式。如，某商店經理可能更想了解如下的購物習慣：

“顧客多半會在購物時同時購買什么商品組或集合？”

為解答這個問題，可以在商店顧客事務零售數據庫上進行購物籃分析。分析的結果可用于市場規劃、廣告策劃和分類設計。4第十頁，共六十四頁，編輯于2023年，星期三5

設商店中所有銷售商品為一個集合，每個商品均為一個布爾變量，布爾變量用來表示該商品是否被(一個)顧客購買。則，每個購物籃（事務數據庫）可以用一個布爾向量表示。分析該布爾向量，得到反映商品頻繁關聯或同時購買的購買模式。

購物籃分析第十一頁，共六十四頁，編輯于2023年，星期三computer=>financial_management_software[support=2%,confidence=60%]關聯規則的支持度(support)2%表示：全部事務中，有2%的交易同時購買計算機和財務管理軟件。關聯規則的置信度(confidence)60%表示：購買計算機的顧客中，有60%也同時購買了財務管理軟件。6

購物籃分析例如，在購買計算機的同時購買財務管理軟件，可用如下關聯規則表示：第十二頁，共六十四頁，編輯于2023年，星期三1.關聯規則的基本概念？第十三頁，共六十四頁，編輯于2023年，星期三關聯規則挖掘的基本概念1）事務數據庫：設I={i1，i2，…，im}是一個項目集合，事務數據庫D={t1，t2，…，tn}是由一系列具有唯一標識TID的事務組成，每個事務ti（i=1，2，…，n）都對應I上的一個子集。示例：購物記錄I是全部物品集合，如商場現有的所有商品；

D是購物清單，如顧客的購物清單；

D中的每個元組ti代表一次事務（商業行為），是一次購買物品的集合（I的一個子集）。第十四頁，共六十四頁，編輯于2023年，星期三基本概念2）支持度(support)：支持度是模式為真的任務相關的元組（或事務）所占的百分比。對于形如“”的關聯規則，支持度定義為：其中，A、B是項目的集合。示例：假定任務相關數據由AllElectronics的計算機部的事務數組成，一個支持度為30%的關聯規則：意味著在計算機部的所有顧客中，有30%同時購買了計算機（A）和軟件（B）。第十五頁，共六十四頁，編輯于2023年，星期三基本概念3）置信度(certainty)：每個發現的模式都有一個表示其有效性或值得信賴性的度量。對于形如“”的關聯規則，其有效性度量為置信度，定義為：其中，A、B是項目的集合。示例：假定任務相關數據由AllElectronics的計算機部購買物品的事務數組成，一個置信度為85%的關聯規則：意味著買計算機（A）的顧客中，有85%也同時購買了軟件（B）。第十六頁，共六十四頁，編輯于2023年，星期三

第十七頁，共六十四頁，編輯于2023年，星期三基本概念4）強關聯規則：

置信度表示規則的可信度；置信度小：規則無意義支持度表示模式在事務數據庫中的出現頻率；支持度小：規則使用面窄同時滿足用戶定義的最小置信度和最小支持度閾值的關聯規則，稱為強關聯規則（strongassociationrule），并被認為是有趣的。第十八頁，共六十四頁，編輯于2023年，星期三2.關聯規則的分類？第十九頁，共六十四頁，編輯于2023年，星期三（1）基于規則中處理的變量類別布爾型：離散的、可枚舉的、種類化的如：性別=“男”=>職業=“網絡工程師”數值型：含有定量的數據項如，性別=“男”=>收入=“3500”關聯規則的分類：第二十頁，共六十四頁，編輯于2023年，星期三（2）基于規則中數據的抽象層次單層關聯規則：所有的變量都不考慮層次如：性別=“男”=>職業=“網絡工程師”多層關聯規則：考慮變量的不同層次性如，數碼相機=>三星手機，（數碼相機是三星數碼相機的較高層抽象）再如，數碼相機=>手機（數碼相機、手機是三星數碼相機和三星手機的較高層抽象）。關聯規則的分類：第二十一頁，共六十四頁，編輯于2023年，星期三多層關聯規則又可以分為：同層關聯規則：如果一個關聯規則對應的項目是同一個粒度層次，那么它是同層關聯規則

如，數碼相機=>手機。層間關聯規則：如果在不同的粒度層次上考慮問題，那么得到的是層間關聯規則。如，數碼相機=>三星手機關聯規則的分類：第二十二頁，共六十四頁，編輯于2023年，星期三（3）基于規則中涉及的數據維數單維關聯規則：只涉及一個屬性（維），處理單個屬性（維）中的一些關系如：啤酒=>尿布，只涉及到用戶購買的物品一個維；多維關聯規則：處理多個屬性（維）上的關系如，性別“女”=>職業“秘書”，此規則涉及到兩個屬性（維）的關系。關聯規則的分類：第二十三頁，共六十四頁，編輯于2023年，星期三6.2由事務數據庫挖掘單維布爾關聯規則關聯規則挖掘的兩步過程：

1）找出所有的頻繁項集：這些項集出現的頻繁性要滿足最小支持度原則。2）由頻繁項集產生強關聯規則：滿足最小支持度和最小置信度。常用方法：

Apriori算法第二十四頁，共六十四頁，編輯于2023年，星期三頻繁項集

項的集合稱為項集（itemset），項的項集稱為k-項集，如集合{computer,software}是一個2-項集。

項集的頻率：即包含項集的事務數，也稱為項集的支持計數(support_count)。Min_sup:設定的支持率閾值如果項集的出現頻率大于或等于min_sup與D中事務總數的乘積，就稱該項集滿足最小支持度min_sup。頻繁項集：滿足最小支持度的項集，頻繁k-項集通常記做：Lk。第二十五頁，共六十四頁，編輯于2023年，星期三基本概念頻繁項集：頻繁項集是頻繁出現在數據集中的項集；有助于發現數據中蘊含的內在規律哪些產品經常被一起購買？---啤酒和尿布？買了PC之后接著都會買些什么？哪種DNA對這種新藥敏感？能揭示數據集內在的、重要的特性。第二十六頁，共六十四頁，編輯于2023年，星期三Apriori算法Apriori算法原理：任何一個頻繁項集的子集必定是頻繁項集；如，如果{A,B}是頻繁項集，則{A}、{B}都是頻繁項集。任何非頻繁項集的超集都為非頻繁項集如，如果{A}、{B}是非頻繁項集，則{A,B}是非頻繁項集第二十七頁，共六十四頁，編輯于2023年，星期三Apriori算法

算法的關鍵步驟：找出頻繁項集：滿足最小支持度的項目集；方法：使用從1到k的候選集逐層遞歸的產生頻繁項集。由頻繁項集產生關聯規則。第二十八頁，共六十四頁，編輯于2023年，星期三APRIORI算法過程Apriori算法利用逐層迭代來計算數據庫中的頻繁項集。第i次迭代計算出所有頻繁i項集(包含i個元素的項集)。每一次迭代有兩個步驟：產生候選集；計算和選擇候選集。原理是：如果一個項集是頻繁的，那么它的所有子集也是頻繁的。在第一次迭代中，產生的候選集包含所有1-項集，并計算其支持度s，s大于閾值的1-項集被選為頻繁1-項集。第二次迭代時，Apriori算法首先去除非頻繁1-項集，在頻繁1-項集的基礎上產生候選二項集，繼而結合設定的最小支持度閾值，產生頻繁2-項集。第二十九頁，共六十四頁，編輯于2023年，星期三如，以表6-1中的數據為例。假設smin=50%。APRIORI算法過程第三十頁，共六十四頁，編輯于2023年，星期三在第一次迭代中，所有單項集都作為候選集，產生一個候選集列表；圖5-1給出第一次迭代的結果在下一步中，計算每一項的支持度，然后在smin的基礎上選擇頻繁項集。APRIORI算法過程圖5-1Apriori算法第一次迭代的結果第三十一頁，共六十四頁，編輯于2023年，星期三在挖掘2-項集時，因為2-項集的任何子集都是頻繁項集，所以Apriori算法使用L1*L1來產生候選集。{*}運算通常定義為：

Lk*Lk={X∪Y其中X,Y∈Lk,|X∪Y|=k+1}

注:|X∪Y|=k+1，即X和Y合取容量為k+1因此，第二次迭代中的候選集C2由運算|L1|·|L1-1|/2所產生，其個數為：4·3/2=6。用該列表來掃描DB，計算每一個候選集的支持度，并與smin進行比較，產生2-項頻繁集L2。圖5-2給出了所有這些步驟和第二次迭代的結果。APRIORI算法過程第三十二頁，共六十四頁，編輯于2023年，星期三APRIORI算法過程第三十三頁，共六十四頁，編輯于2023年，星期三候選集C3

運用L2*L2來產生，運算結果得到{A,B,C},{A,C,E},{B,C,E}，但只有{B,C,E}的所有子集是頻繁項集，成為候選的3-項集。然后掃描DB，根據最小支持計數，挖掘出頻繁3-項集，見圖5-3所示:因為本例的L3無法產生候選的4-項集，所以算法停止迭代過程。圖5-3Apriori算法第三次迭代的結果APRIORI算法過程第三十四頁，共六十四頁，編輯于2023年，星期三該算法不僅計算所有頻繁集的支持度，也計算那些沒有被刪除的非頻繁候選集的支持度。所有非頻繁但被算法計算支持度的候選項集的集合被稱為負邊界。因此，如果項集是非頻繁的，但它的子集都是頻繁的，那么它就在負邊界之中。APRIORI算法過程第三十五頁，共六十四頁，編輯于2023年，星期三36Apriori算法源代碼算法：Apriori使用根據候選生成的逐層迭代找出頻繁項集輸入：事務數據庫D；最小支持度閾值min_sup輸出：D中的頻繁項集L（1）L1={large1-itemsets};//所有1-項目頻集（2）FOR（k=2;Lk-1;k++）DOBEGIN（3）Ck=apriori-gen（Lk-1）;//Ck是k-候選集（4）FORalltransactionstDDOBEGIN（5）Ct=subset（Ck，t）;//Ct是所有t包含的候選集元素（6）FORallcandidatescCtDO（7）c.count++;（8）END（9）Lk={cCk|c.countminsup_count}（10）END（11）L=Lk;

第三十六頁，共六十四頁，編輯于2023年，星期三第三十七頁，共六十四頁，編輯于2023年，星期三38第三十八頁，共六十四頁，編輯于2023年，星期三第三十九頁，共六十四頁，編輯于2023年，星期三示例：對于前面的例子，基于事務數據庫D，在假定最小支持度閾值為50%的前提下，我們得到了頻繁項集{2,3,5}。問，由該頻繁項集可以產生哪些關聯規則？分析：頻繁項集L={2,3,5}的非空子集有{2,3},{2,5},{3,5},{2},{3},{5}。則由這些子集可以產生如下關聯規則：由頻繁項集產生關聯規則如果限定最小置信度閾值為80%，則只有規則（1），（3）為強關聯規則。第四十頁，共六十四頁，編輯于2023年，星期三Apriori作為經典的頻繁項目集生成算法，在數據挖掘中具有里程碑的作用。Apriori算法有兩個致命的性能瓶頸:1．多次掃描事務數據庫，需要很大的I/O負載對每次k循環，侯選集Ck中的每個元素都必須通過掃描數據庫來驗證其是否加入Lk。假如有一個頻繁大項目集包含10個項的話，那么就至少需要掃描事務數據庫10遍。2．可能產生龐大的侯選集由Lk-1產生k-侯選集Ck是指數增長的。Apriori算法的性能瓶頸第四十一頁，共六十四頁，編輯于2023年，星期三如何提高Apriori算法的效率一些算法雖然仍然遵循Apriori屬性，但是由于引入了相關技術，在一定程度上改善了Apriori算法適應性和效率。主要的改進方法有：基于數據分割（Partition）的方法：基本原理是“在一個劃分中的支持度小于最小支持度的k-項集不可能是全局頻繁的”。基于散列（Hash）的方法：基本原理是“在一個hash桶內支持度小于最小支持度的k-項集不可能是全局頻繁的”。基于采樣的方法：基本原理是“通過采樣技術，評估被采樣的子集，并依次來估計k-項集的全局頻度”。其他：如，動態刪除沒有用的事務：“不包含任何Lk的事務對未來的掃描結果不會產生影響，因而可以刪除”。第四十二頁，共六十四頁，編輯于2023年，星期三6.3由事務數據庫挖掘多層關聯規則多層關聯規則：對許多應用，由于多維數據空間數據的稀疏性，在低層或原始層的數據項之間很難找到強關聯規則。如，IBM臺式機=>Sony打印機，在兩個數據項間可能很難找到強關聯規則在較高的概念層，則較容易得到強關聯規則。這種強關聯規則對某些用戶可能是普遍意義的，對其他用戶則可能是新穎的。

如，臺式機=>打印機，找到強關聯規則的可能性就大多了因此，數據挖掘系統應當能提供一種能力，在多個抽象層挖掘關聯規則，并容易在不同的抽象空間轉換。第四十三頁，共六十四頁，編輯于2023年，星期三示例示例：給定AllElectronics公司分店的計算機部的銷售數據，如表6-2所示，對每個事務TID給出了購買的商品。第四十四頁，共六十四頁，編輯于2023年，星期三示例圖5-4商品的概念分層第四十五頁，共六十四頁，編輯于2023年，星期三示例概念分層：定義了低層概念到更一般的高層概念的映射序列。可通過對數據內的低層概念用概念分層中其高層概念進行替換，以實現對數據的概化。圖5-4中的概念分層有4層，記做0,1,2,3：0層：根節點all（最一般的抽象概念）；1層：computer,software,printer,computeraccessory2層：desktopcomputer,laptopcomputer,educationalsoftware,financialmanagementsoftware…3層：IBMdesktopcomputer,Microsofteducationalsoftware,…第四十六頁，共六十四頁，編輯于2023年，星期三示例表5-2中的項對應圖5-4中概念分層的最低層，即第3層，在這種原始層很難找出有趣的購買模式。如，很難找到“IBMdesktopcomputer”和“Sonyb/wprinter”的強關聯規則，因為很少有人同時購買它們，是的{IBMdesktopcomputer,Sonyb/wprinter}不太可能滿足最小支持度。然而，考慮將“Sonyb/wprinter”概化到“b/wprinter”，在“IBMdesktopcomputer”和“b/wprinter”之間比在“IBMdesktopcomputer”和“Sonyb/wprinter”間，更可望發現強關聯規則。類似的，在“computer”和“printer”間，則更容易發現強關聯規則。第四十七頁，共六十四頁，編輯于2023年，星期三多層關聯規則多層關聯規則挖掘的度量方法仍可以沿用“支持度-置信度框架”；但是，有兩種設置支持度的策略：對于所有層使用一致的最小支持度（一致支持度）：在每一層挖掘時，使用相同的最小支持度閾值。在較低層使用遞減的最小支持度（遞減支持度）：每個抽象層有它自己的最小支持度閾值，抽象層越低，對應的閾值越小。第四十八頁，共六十四頁，編輯于2023年，星期三一致支持度如下圖，在挖掘過程中，設置一致的最小支持度閾值5%。發現，層1滿足此閾值，在層2中，“2%milk”滿足，而“skimmilk”則不滿足。說明，較低層次抽象的項不大可能像較高層次抽象的項出現得那么頻繁。第四十九頁，共六十四頁，編輯于2023年，星期三一致支持度優勢：使用一致的最小支持度閾值，搜索過程是簡單的，且用戶只需用指定一個最小支持度閾值。缺陷：如果最小支持度閾值設置太高，可能丟掉出現在較低抽象層中有意義的關聯規則；反之，設置太低，則可能會在較高抽象層產生無興趣的關聯規則解決方法：“遞減支持度”第五十頁，共六十四頁，編輯于2023年，星期三遞減支持度如下圖，在挖掘過程中，使用遞減支持度。層1和層2的閾值分別設定為5%和3%，用這種方法，“Milk”，“2%Milik”和“SkimMilk”都是頻繁的。第五十一頁，共六十四頁，編輯于2023年，星期三遞減支持度對于具有遞減支持度的多層關聯規則挖掘，有許多可用的搜索策略：“逐層獨立”“層交叉單項過濾”“層交叉k-項集過濾”第五十二頁，共六十四頁，編輯于2023年，星期三1）逐層獨立逐層獨立：這是完全的寬度搜索，沒有頻繁項集的背景知識用于剪枝；頻繁項集：如果一個項集是頻繁的，那么它的所有子集也是頻繁的；考慮每一個節點，不管它的父節點是否是頻繁的。第五十三頁，共六十四頁，編輯于2023年，星期三2）層交叉單項過濾層交叉單項過濾：一個第i層的項被考察，當且僅當它在第(i-1)層的父節點是頻繁的。即，由較一般的關聯考察更特定的關聯。如果一個節點是頻繁的，它的子女將被考察；否則，它的子孫將被剪枝。如下圖所示。第五十四頁，共六十四頁，編輯于2023年，星期三3）層交叉k-項集過濾層交叉k-項集過濾：一個第i層的k-項集被考察，當且僅當它在第(i-1)層的k-項集父節點是頻繁的。如，下圖中，2-項集{computer,printer}是頻繁的，因而節點{laptopcomputer,b/wprinter},{laptopcomputer,colorprinter},{desktopcomputer,b/wprinter},{desktopcomputer,colorprinter}被考察。第五十五頁，共六十四頁，編輯于2023年，星期三6.4由關系數據庫和數據倉庫挖掘多維關聯規則單維關聯規則：前面所介紹的關聯規則都只涉及一個謂詞，如buys謂詞。如在一個商場的數據庫挖掘中，可挖掘出如下關聯規則：其中X為代表顧客的一個變量。同樣，一個多層次關聯規則可為：在上述兩個關聯規則中僅包含一個特定的謂詞：buys，因此被稱為單維關聯規則，或維內關聯規則。第五十六頁，共六十四頁，編輯于2023年，星期三6.4由關系數據庫和數據倉庫挖掘多維關聯規則假定不是對事務數據庫進行分析，而是對關系數據庫或數據倉庫中的銷售和相關信息進行分析，此時的數據是以多維形式定義存儲的。如，除記錄在銷售事務中購買的商品外，關系數據庫可能還記錄著與商品有關的其他屬性，如購買數量、價格、銷售地址等；還可能有購物顧客的基本信息，如年齡、職業、信譽度、收入、地址等。若將數據庫的每個屬性或數據倉庫的每個維看作一個謂詞，可挖掘得到多維關聯規則。第五十七頁，共六十四頁，編輯于2023年，星期三6.4由關系數據庫和數據倉庫挖掘多維關聯規則多維關聯規則：包含兩個或多個維或謂詞的關聯規則稱為多維關聯規則。如上述規則中，包含三個不