大型數(shù)據(jù)庫中的關(guān)聯(lián)規(guī)則挖掘

大型數(shù)據(jù)庫中的關(guān)聯(lián)規(guī)則挖掘什么是關(guān)聯(lián)規(guī)則挖掘？關(guān)聯(lián)規(guī)則挖掘發(fā)現(xiàn)大量數(shù)據(jù)中項(xiàng)集之間有趣的關(guān)聯(lián)或相關(guān)聯(lián)系。隨著大量數(shù)據(jù)不停地收集和存儲(chǔ)，許多業(yè)界人士對(duì)于從他們的數(shù)據(jù)庫中挖掘關(guān)聯(lián)規(guī)則越來越感興趣。從大量商務(wù)事務(wù)記錄中發(fā)現(xiàn)有趣的關(guān)聯(lián)關(guān)系，可以幫助許多商務(wù)決策的制定，如分類設(shè)計(jì)、交叉購物和賤賣分析。關(guān)聯(lián)規(guī)則挖掘的一個(gè)典型例子是購物籃分析。該過程通過發(fā)現(xiàn)顧客放入其購物籃中不同商品（圖6.1）之間聯(lián)系，分析顧客的購買習(xí)慣。通過了解哪些商品頻繁地被顧客同時(shí)購買，這種關(guān)聯(lián)的發(fā)現(xiàn)可以幫助零售商制定營銷策略。例如，在同一次去超級(jí)市場(chǎng)，如果顧客購買牛奶，他也購買面包（和什么類型的面包）的可能性有多大？通過幫助零售商有選擇地經(jīng)銷和安排貨架，這種信息可以引導(dǎo)銷售。例如，將牛奶和面包盡可能放近一些，可以進(jìn)一步刺激一次去商店同時(shí)購買這些商品?！澳虿寂c啤酒”——典型關(guān)聯(lián)分析案例采用關(guān)聯(lián)模型比較典型的案例是“尿布與啤酒”的故事。在美國，一些年輕的父親下班后經(jīng)常要到超市去買嬰兒尿布，超市也因此發(fā)現(xiàn)了一個(gè)規(guī)律，在購買嬰兒尿布的年輕父親們中，有30%～40%的人同時(shí)要買一些啤酒。超市隨后調(diào)整了貨架的擺放，把尿布和啤酒放在一起，明顯增加了銷售額。同樣的，我們還可以根據(jù)關(guān)聯(lián)規(guī)則在商品銷售方面做各種促銷活動(dòng)。購物籃分析假定作為AllElectronics

的分店經(jīng)理，你想更加了解你的顧客的購物習(xí)慣。例如，你想知道“什么商品組或集合顧客多半會(huì)在一次購物時(shí)同時(shí)購買？”為回答你的問題，你可以在你的商店顧客事務(wù)零售數(shù)據(jù)上運(yùn)行購物籃分析。分析結(jié)果可以用于市場(chǎng)規(guī)劃、廣告策劃、分類設(shè)計(jì)。例如，購物籃分析可以幫助經(jīng)理設(shè)計(jì)不同的商店布局。一種策略是：經(jīng)常一塊購買的商品可以放近一些，以便進(jìn)一步刺激這些商品一起銷售。例如，如果顧客購買計(jì)算機(jī)也傾向于同時(shí)購買財(cái)務(wù)軟件，將硬件擺放離軟件陳列近一點(diǎn)，可能有助于增加二者的銷售。另一種策略是：將硬件和軟件放在商店的兩端，可能誘發(fā)買這些商品的顧客一路挑選其它商品。例如，在決定購買一臺(tái)很貴的計(jì)算機(jī)之后，去看軟件陳列，購買財(cái)務(wù)軟件，路上可能看到安全系統(tǒng)，可能會(huì)決定也買家庭安全系統(tǒng)。購物籃分析也可以幫助零售商規(guī)劃什么商品降價(jià)出售。如果顧客趨向于同時(shí)購買計(jì)算機(jī)和打印機(jī)，打印機(jī)降價(jià)出售可能既促使購買打印機(jī)，又促使購買計(jì)算機(jī)。購物籃分析如果問題的全域是商店中所有商品的集合，則對(duì)每種商品都可以用一個(gè)布爾量來表示該商品是否被顧客購買，則每個(gè)購物籃都可以用一個(gè)布爾向量表示；而通過分析布爾向量則可以得到商品被頻繁關(guān)聯(lián)或被同時(shí)購買的模式，這些模式就可以用關(guān)聯(lián)規(guī)則表示關(guān)聯(lián)規(guī)則的兩個(gè)興趣度度量支持度置信度6.1.2基本概念設(shè)I={i1,i2,...,im

}是項(xiàng)的集合。設(shè)任務(wù)相關(guān)的數(shù)據(jù)D是數(shù)據(jù)庫事務(wù)的集合，其中每個(gè)事務(wù)T是項(xiàng)的集合，使得T?I。每一個(gè)事務(wù)有一個(gè)標(biāo)識(shí)符，稱作TID。設(shè)A是一個(gè)項(xiàng)集，事務(wù)T包含A當(dāng)且僅當(dāng)A?T。關(guān)聯(lián)規(guī)則是形如A?B的蘊(yùn)涵式，其中A?I，B?I，并且A∩B=?。規(guī)則A?B在事務(wù)集D中成立，具有支持度s，其中s是D中事務(wù)包含A∪B（即，A和B二者）的百分比。6.1.2基本概念它是概率P(A∪B)。規(guī)則A?B在事務(wù)集D中具有置信度c，如果D中包含A的事務(wù)同時(shí)也包含B的百分比是c。這是條件概率P(B|A)。support(A?B)=P(A∪B)(6.2)confidence(A?B)=P(B|A)(6.3)6.1.2基本概念同時(shí)滿足最小支持度閾值(min_sup)和最小置信度閾值(min_conf)的規(guī)則稱作強(qiáng)規(guī)則。為方便計(jì)，我們用0%和100%之間的值，而不是用0到1之間的值表示支持度和置信度。項(xiàng)的集合稱為項(xiàng)集。包含k個(gè)項(xiàng)的項(xiàng)集稱為k-項(xiàng)集。集合{computer,financial_management_software}是一個(gè)2-項(xiàng)集。項(xiàng)集的出現(xiàn)頻率是包含項(xiàng)集的事務(wù)數(shù)，簡稱為項(xiàng)集的頻率、支持計(jì)數(shù)或計(jì)數(shù)。項(xiàng)集滿足最小支持度min_sup，如果項(xiàng)集的出現(xiàn)頻率大于或等于min_sup

與D中事務(wù)總數(shù)的乘積。如果項(xiàng)集滿足最小支持度，則稱它為頻繁項(xiàng)集。頻繁k-項(xiàng)集的集合通常記作Lk?；靖拍睢纠?xiàng)的集合I={A,B,C,D,E,F}每個(gè)事務(wù)T由事務(wù)標(biāo)識(shí)符TID標(biāo)識(shí)，它是項(xiàng)的集合比如：TID(2000)={A,B,C}任務(wù)相關(guān)數(shù)據(jù)D是數(shù)據(jù)庫事務(wù)的集合D規(guī)則度量：支持度和置信度CustomerbuysdiaperCustomerbuysbothCustomerbuysbeer對(duì)所有滿足最小支持度和置信度的關(guān)聯(lián)規(guī)則支持度s是指事務(wù)集D中包含的百分比置信度c是指D中包含A的事務(wù)同時(shí)也包含B的百分比假設(shè)最小支持度為50%，最小置信度為50%，則有如下關(guān)聯(lián)規(guī)則AC(50%,66.6%)CA(50%,100%)大型數(shù)據(jù)庫關(guān)聯(lián)規(guī)則挖掘(1)基本概念k－項(xiàng)集：包含k個(gè)項(xiàng)的集合{牛奶，面包，黃油}是個(gè)3－項(xiàng)集項(xiàng)集的頻率是指包含項(xiàng)集的事務(wù)數(shù)如果項(xiàng)集的頻率大于（最小支持度×D中的事務(wù)總數(shù)），則稱該項(xiàng)集為頻繁項(xiàng)集大型數(shù)據(jù)庫關(guān)聯(lián)規(guī)則挖掘(2)大型數(shù)據(jù)庫中的關(guān)聯(lián)規(guī)則挖掘包含兩個(gè)過程：找出所有頻繁項(xiàng)集大部分的計(jì)算都集中在這一步由頻繁項(xiàng)集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則即滿足最小支持度和最小置信度的規(guī)則關(guān)聯(lián)規(guī)則挖掘分類(1)關(guān)聯(lián)規(guī)則有多種分類：根據(jù)規(guī)則中所處理的值類型布爾關(guān)聯(lián)規(guī)則量化關(guān)聯(lián)規(guī)則（規(guī)則描述的是量化的項(xiàng)或?qū)傩蚤g的關(guān)聯(lián)性）根據(jù)規(guī)則中涉及的數(shù)據(jù)維單維關(guān)聯(lián)規(guī)則（僅涉及buys這個(gè)維）多維關(guān)聯(lián)規(guī)則關(guān)聯(lián)規(guī)則挖掘分類(2)根據(jù)規(guī)則集所涉及的抽象層單層關(guān)聯(lián)規(guī)則多層關(guān)聯(lián)規(guī)則（在不同的抽象層發(fā)現(xiàn)關(guān)聯(lián)規(guī)則）根據(jù)關(guān)聯(lián)挖掘的各種擴(kuò)充挖掘最大的頻繁模式（該模式的任何真超模式都是非頻繁的）挖掘頻繁閉項(xiàng)集（一個(gè)項(xiàng)集c是頻繁閉項(xiàng)集，如果不存在其真超集c’，使得每個(gè)包含c的事務(wù)也包含c’）（最大的頻繁模式和頻繁閉項(xiàng)集可以用來減少挖掘中產(chǎn)生的頻繁項(xiàng)集）由事務(wù)數(shù)據(jù)庫挖掘單維布爾關(guān)聯(lián)規(guī)則最簡單的關(guān)聯(lián)規(guī)則挖掘，即單維、單層、布爾關(guān)聯(lián)規(guī)則的挖掘。最小支持度50%最小置信度50%對(duì)規(guī)則A

C，其支持度=50%置信度Apriori算法(1)Apriori算法是挖掘布爾關(guān)聯(lián)規(guī)則頻繁項(xiàng)集的算法Apriori算法利用的是Apriori性質(zhì)：頻繁項(xiàng)集的所有非空子集也必須是頻繁的。模式不可能比A更頻繁的出現(xiàn)Apriori算法是反單調(diào)的，即一個(gè)集合如果不能通過測(cè)試，則該集合的所有超集也不能通過相同的測(cè)試。Apriori性質(zhì)通過減少搜索空間，來提高頻繁項(xiàng)集逐層產(chǎn)生的效率Apriori算法(2)Apriori算法利用頻繁項(xiàng)集性質(zhì)的先驗(yàn)知識(shí)（priorknowledge），通過逐層搜索的迭代方法，即將k-項(xiàng)集用于探察(k+1)-項(xiàng)集，來窮盡數(shù)據(jù)集中的所有頻繁項(xiàng)集。先找到頻繁1-項(xiàng)集集合L1,然后用L1找到頻繁2-項(xiàng)集集合L2，接著用L2找L3，直到找不到頻繁k-項(xiàng)集，找每個(gè)Lk需要一次數(shù)據(jù)庫掃描。Apriori算法步驟Apriori算法由連接和剪枝兩個(gè)步驟組成。連接步：為找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)（例如，l1[k-2]表示l1

的倒數(shù)第3項(xiàng)）。為方便計(jì)，假定事務(wù)或項(xiàng)集中的項(xiàng)按字典次序排序。執(zhí)行連接；其中，Lk-1

的元素是可連接的，如果它們前(k-2)個(gè)項(xiàng)相同；即，Lk-1

的元素l1

和l2

是可連接的，如果(l1

[1]=l2

[1])∧(l1[2]=l2

[2])∧...∧(l1[k-2]=l2

[k-2])∧(l1

[k-1]<l2

[k-1])。條件(l1[k-1]<l2

[k-1])是簡單地保證不產(chǎn)生重復(fù)。連接l1

和l2

產(chǎn)生的結(jié)果項(xiàng)集是l1[1]l1

[2]...l1

[k-1]l2

[k-1]。剪枝步：Ck

是Lk

的超集；即，它的成員可以是，也可以不是頻繁的，但所有的頻繁k-項(xiàng)集都包含在Ck

中。掃描數(shù)據(jù)庫，確定Ck

中每個(gè)候選的計(jì)數(shù)，從而確定Lk（即，根據(jù)定義，計(jì)數(shù)值不小于最小支持度計(jì)數(shù)的所有候選是頻繁的，從而屬于Lk）。然而，Ck

可能很大，這樣所涉及的計(jì)算量就很大。為壓縮Ck，可以用以下辦法使用Apriori

性質(zhì)：任何非頻繁的(k-1)-項(xiàng)集都不是可能是頻繁k-項(xiàng)集的子集。因此，如果一個(gè)候選k-項(xiàng)集的(k-1)-子集不在Lk-1中，則該候選也不可能是頻繁的，從而可以由Ck

中刪除。這種子集測(cè)試可以使用所有頻繁項(xiàng)集的散列樹快速完成。例6.1讓我們看一個(gè)Apriori

的具體例子。該例基于圖6.2的AllElectronics

的事務(wù)數(shù)據(jù)庫。數(shù)據(jù)庫中有9個(gè)事務(wù)，即|D|=9。Apriori

假定事務(wù)中的項(xiàng)按字典次序存放。我們使用圖6.3解釋Apriori算法發(fā)現(xiàn)D中的頻繁項(xiàng)集。Apriori算法——示例DatabaseTDB1stscanC1L1L2C2C22ndscanC3L33rdscanTidItems10A,C,D20B,C,E30A,B,C,E40B,EItemsetsup{A}2{B}3{C}3{D}1{E}3Itemsetsup{A}2{B}3{C}3{E}3Itemset{A,B}{A,C}{A,E}{B,C}{B,E}{C,E}Itemsetsup{A,B}1{A,C}2{A,E}1{B,C}2{B,E}3{C,E}2Itemsetsup{A,C}2{B,C}2{B,E}3{C,E}2Itemset{B,C,E}Itemsetsup{B,C,E}2最小支持計(jì)數(shù)：2使用Apiori性質(zhì)由L2產(chǎn)生C31．連接：C3=L2

L2={{A,C},{B,C},{B,E}{C,E}}{{A,C},{B,C},{B,E}{C,E}}={{A,B,C},{A,C,E},{B,C,E}}2．使用Apriori性質(zhì)剪枝：頻繁項(xiàng)集的所有子集必須是頻繁的，對(duì)候選項(xiàng)C3，我們可以刪除其子集為非頻繁的選項(xiàng)：{A,B,C}的2項(xiàng)子集是{A,B},{A,C},{B,C}，其中{A,B}不是L2的元素，所以刪除這個(gè)選項(xiàng)；{A,C,E}的2項(xiàng)子集是{A,C},{A,E},{C,E}，其中{A,E}

不是L2的元素，所以刪除這個(gè)選項(xiàng)；{B,C,E}的2項(xiàng)子集是{B,C},{B,E},{C,E}，它的所有2－項(xiàng)子集都是L2的元素，因此保留這個(gè)選項(xiàng)。3．這樣，剪枝后得到C3={{B,C,E}}由頻繁項(xiàng)集產(chǎn)生關(guān)聯(lián)規(guī)則同時(shí)滿足最小支持度和最小置信度的才是強(qiáng)關(guān)聯(lián)規(guī)則，從頻繁項(xiàng)集產(chǎn)生的規(guī)則都滿足支持度要求，而其置信度則可由一下公式計(jì)算：每個(gè)關(guān)聯(lián)規(guī)則可由如下過程產(chǎn)生：對(duì)于每個(gè)頻繁項(xiàng)集l，產(chǎn)生l的所有非空子集；對(duì)于每個(gè)非空子集s，如果 則輸出規(guī)則“ ”6.2.3提高Apriori的有效性（1）基于散列的技術(shù)（散列項(xiàng)集計(jì)數(shù)）：一種基于散列的技術(shù)可以用于壓縮候選k-項(xiàng)集Ck(k>1)。例如，當(dāng)掃描數(shù)據(jù)庫中每個(gè)事務(wù)，由C1中的候選1-項(xiàng)集產(chǎn)生頻繁1-項(xiàng)集L1時(shí)，我們可以對(duì)每個(gè)事務(wù)產(chǎn)生所有的2-項(xiàng)集，將它們散列（即，映射）到散列表結(jié)構(gòu)的不同桶中，并增加對(duì)應(yīng)的桶計(jì)數(shù)（圖6.6）。在散列表中對(duì)應(yīng)的桶計(jì)數(shù)低于支持度閾值的2-項(xiàng)集不可能是頻繁2-項(xiàng)集，因而應(yīng)當(dāng)由候選項(xiàng)集中刪除。這種基于散列的技術(shù)可以大大壓縮要考察的k-項(xiàng)集（特別是當(dāng)k=2時(shí)）。6.2.3提高Apriori的有效性6.2.3提高Apriori的有效性（2）事務(wù)壓縮（壓縮進(jìn)一步迭代掃描的事務(wù)數(shù)）：不包含任何k-項(xiàng)集的事務(wù)不可能包含任何(k+1)-項(xiàng)集。這樣，這種事務(wù)在其后的考慮時(shí)，可以加上標(biāo)記或刪除，因?yàn)闉楫a(chǎn)生j-項(xiàng)集(j>k)，掃描數(shù)據(jù)庫時(shí)不再需要它們。6.2.3提高Apriori的有效性劃分（為找候選項(xiàng)集劃分?jǐn)?shù)據(jù)）：可以使用劃分技術(shù)，它只需要兩次數(shù)據(jù)庫掃描，以挖掘頻繁項(xiàng)集（圖6.7）。它包含兩遍。在第I遍，算法將D中的事務(wù)劃分成n個(gè)非重疊的部分。如果D中事務(wù)的最小支持度閾值為min_sup，則每個(gè)部分的最小支持度計(jì)數(shù)為min_sup×該部分中事務(wù)數(shù)。對(duì)每一部分，找出該部分內(nèi)的頻繁項(xiàng)集。這些稱作局部頻繁項(xiàng)集。該過程使用一種特殊的數(shù)據(jù)結(jié)構(gòu)，對(duì)于每個(gè)項(xiàng)集，記錄包含項(xiàng)集中項(xiàng)的事務(wù)的TID。這使得對(duì)于k=1,2,..，找出所有的局部頻繁k-項(xiàng)集只需要掃描一次數(shù)據(jù)庫。6.2.3提高Apriori的有效性局部頻繁項(xiàng)集可能不是整個(gè)數(shù)據(jù)庫D的頻繁項(xiàng)集。D的任何頻繁項(xiàng)集必須作為局部頻繁項(xiàng)集至少出現(xiàn)在一個(gè)部分中。這樣，所有的局部頻繁項(xiàng)集作為D的候選項(xiàng)集。所有部分的頻繁項(xiàng)集的集合形成D的全局候選項(xiàng)集。在第II遍，第二次掃描D，評(píng)估每個(gè)候選的實(shí)際支持度，以確定全局頻繁項(xiàng)集。每一部分的大小和劃分的數(shù)目這樣確定，使得每一部分能夠放入內(nèi)存，這樣每遍只需要讀一次。6.2.3提高Apriori的有效性（4）選樣（在給定數(shù)據(jù)的一個(gè)子集挖掘）：選樣方法的基本思想是：選取給定數(shù)據(jù)庫D的隨機(jī)樣本S，然后，在S而不是在D中搜索頻繁項(xiàng)集。用這種方法，我們犧牲了一些精度換取了有效性。樣本S的大小這樣選取，使得可以在內(nèi)存搜索S中頻繁項(xiàng)集；這樣，總共只需要掃描一次S中的事務(wù)。由于我們搜索S中而不是D中的頻繁項(xiàng)集，我們可能丟失一些全局頻繁項(xiàng)集。為減少這種可能性，我們使用比最小支持度低的支持度閾值來找出局部于S的頻繁項(xiàng)集（記作LS）。6.2.3提高Apriori的有效性然后，數(shù)據(jù)庫的其余部分用于計(jì)算LS中每個(gè)項(xiàng)集的實(shí)際頻繁度。有一種機(jī)制可以用來確定是否所有的頻繁項(xiàng)集都包含在LS中。如果LS實(shí)際包含了D中的所有頻繁項(xiàng)集，只需要掃描一次D。否則，可以做第二次掃描，以找出在第一次掃描時(shí)遺漏的頻繁項(xiàng)集。當(dāng)效率最為重要時(shí)，如計(jì)算密集的應(yīng)用必須在不同的數(shù)據(jù)上運(yùn)行時(shí)，選樣方法特別合適。6.2.3提高Apriori的有效性（5）動(dòng)態(tài)項(xiàng)集計(jì)數(shù)（在掃描的不同點(diǎn)添加候選項(xiàng)集）：動(dòng)態(tài)項(xiàng)集計(jì)數(shù)技術(shù)將數(shù)據(jù)庫劃分為標(biāo)記開始點(diǎn)的塊。不象Apriori

僅在每次完整的數(shù)據(jù)庫掃描之前確定新的候選，在這種變形中，可以在任何開始點(diǎn)添加新的候選項(xiàng)集。該技術(shù)動(dòng)態(tài)地評(píng)估已被計(jì)數(shù)的所有項(xiàng)集的支持度，如果一個(gè)項(xiàng)集的所有子集已被確定為頻繁的，則添加它作為新的候選。結(jié)果算法需要的數(shù)據(jù)庫掃描比Apriori

少。其它變形涉及多層和多維關(guān)聯(lián)規(guī)則挖掘，在本章的其余部分討論。涉及空間數(shù)據(jù)、時(shí)間序列數(shù)據(jù)和多媒體數(shù)據(jù)的關(guān)聯(lián)挖掘在第9章討論。6.2.4不產(chǎn)生候選挖掘頻繁項(xiàng)集正如我們已經(jīng)看到的，在許多情況下，Apriori

的候選產(chǎn)生-檢查方法大幅度壓縮了候選項(xiàng)集的大小，并導(dǎo)致很好的性能。然而，它有兩種開銷可能并非微不足道的。6.2.4不產(chǎn)生候選挖掘頻繁項(xiàng)集它可能需要產(chǎn)生大量候選項(xiàng)集。例如，如果有104個(gè)頻繁1-項(xiàng)集，則Apriori

算法需要產(chǎn)生多達(dá)107個(gè)候選2-項(xiàng)集，累計(jì)并檢查它們的頻繁性。此外，為發(fā)現(xiàn)長度為100的頻繁模式，如{a1,...,a100}，它必須產(chǎn)生多達(dá)2100≈1030

個(gè)候選。它可能需要重復(fù)地掃描數(shù)據(jù)庫，通過模式匹配檢查一個(gè)很大的候選集合。對(duì)于挖掘長模式尤其如此。6.2.4不產(chǎn)生候選挖掘頻繁項(xiàng)集“可以設(shè)計(jì)一種方法，挖掘全部頻繁項(xiàng)集，而不產(chǎn)生候選嗎？”一種有趣的方法稱作頻繁模式增長，或簡單地，F(xiàn)P-增長，它采取如下分治策略：將提供頻繁項(xiàng)集的數(shù)據(jù)庫壓縮到一棵頻繁模式樹（或FP-樹），但仍保留項(xiàng)集關(guān)聯(lián)信息；然后，將這種壓縮后的數(shù)據(jù)庫分成一組條件數(shù)據(jù)庫（一種特殊類型的投影數(shù)據(jù)庫），每個(gè)關(guān)聯(lián)一個(gè)頻繁項(xiàng)，并分別挖掘每個(gè)數(shù)據(jù)庫。讓我們看一個(gè)例子。6.2.4不產(chǎn)生候選挖掘頻繁項(xiàng)集例6.3使用頻繁模式增長方法，我們重新考察例6.1中圖6.2事務(wù)數(shù)據(jù)庫D的挖掘。數(shù)據(jù)庫的第一次掃描與Apriori

相同，它導(dǎo)出頻繁項(xiàng)（1-項(xiàng)集）的集合，并得到它們的支持度計(jì)數(shù)（頻繁性）。設(shè)最小支持度計(jì)數(shù)為2。頻繁項(xiàng)的集合按支持度計(jì)數(shù)的遞減序排序。結(jié)果集或表記作L。這樣，我們有L=[I2:7,I1:6,I3:6,I4:2,I5:2]。6.2.4不產(chǎn)生候選挖掘頻繁項(xiàng)集然后，F(xiàn)P-樹構(gòu)造如下：首先，創(chuàng)建樹的根結(jié)點(diǎn)，用“null”標(biāo)記。二次掃描數(shù)據(jù)庫D。每個(gè)事務(wù)中的項(xiàng)按L中的次序處理（即，根據(jù)遞減支持度計(jì)數(shù)排序）并對(duì)每個(gè)事務(wù)創(chuàng)建一個(gè)分枝。例如，第一個(gè)事務(wù)“T100:I1,I2,I5”按L的次序包含三個(gè)項(xiàng){I2,I1,I5}，導(dǎo)致構(gòu)造樹的第一個(gè)分枝<(I2:1),(I1:1),(I5:1)>。該分枝具有三個(gè)結(jié)點(diǎn)，其中，I2作為根的子女鏈接，I1鏈接到I2，I5鏈接到I1。6.2.4不產(chǎn)生候選挖掘頻繁項(xiàng)集第二個(gè)事務(wù)T200按L的次序包含項(xiàng)I2和I4，它導(dǎo)致一個(gè)分枝，其中，I2鏈接到根，I4鏈接到I2。然而，該分枝應(yīng)當(dāng)與T100已存在的路徑共享前綴<I2>。這樣，我們將結(jié)點(diǎn)I2的計(jì)數(shù)增加1，并創(chuàng)建一個(gè)新結(jié)點(diǎn)(I4:1)，它作為(I2:2)的子女鏈接。一般地，當(dāng)為一個(gè)事務(wù)考慮增加分枝時(shí)，沿共同前綴上的每個(gè)結(jié)點(diǎn)的計(jì)數(shù)增加1，為隨在前綴之后的項(xiàng)創(chuàng)建結(jié)點(diǎn)并鏈接。6.2.4不產(chǎn)生候選挖掘頻繁項(xiàng)集為方便樹遍歷，創(chuàng)建一個(gè)項(xiàng)頭表，使得每個(gè)項(xiàng)通過一個(gè)結(jié)點(diǎn)鏈指向它在樹中的出現(xiàn)。掃描所有的事務(wù)之后得到的樹展示在圖6.8中，附上相關(guān)的結(jié)點(diǎn)鏈。這樣，數(shù)據(jù)庫頻繁模式的挖掘問題就轉(zhuǎn)換成挖掘FP-樹問題。6.2.4不產(chǎn)生候選挖掘頻繁項(xiàng)集6.2.4不產(chǎn)生候選挖掘頻繁項(xiàng)集FP-樹挖掘處理如下。由長度為1的頻繁模式（初始后綴模式）開始，構(gòu)造它的條件模式基（一個(gè)“子數(shù)據(jù)庫”，由FP-樹中與后綴模式一起出現(xiàn)的前綴路徑集組成）。然后，構(gòu)造它的（條件）FP-樹，并遞歸地在該樹上進(jìn)行挖掘。模式增長通過后綴模式與由條件FP-樹產(chǎn)生的頻繁模式連接實(shí)現(xiàn)。6.2.4不產(chǎn)生候選挖掘頻繁項(xiàng)集FP-樹的挖掘總結(jié)在表6.1中，讓我們首先考慮I5，它是L中的最后一個(gè)項(xiàng)，而不是第一個(gè)。其原因隨著我們解釋FP-樹挖掘過程就會(huì)清楚。I5出現(xiàn)在圖6.8的FP-樹的兩個(gè)分枝。（I5的出現(xiàn)容易通過沿它的結(jié)點(diǎn)鏈找到。）這些路徑由分枝<(I2I1I5:1)>和<(I2I1I3I5:1)>形成。這樣，考慮I5為后綴，它的兩個(gè)對(duì)應(yīng)前綴路徑是<(I2I1:1)>和<(I2I1I3:1)>，它們形成I5的條件模式基。它的條件FP-樹只包含單個(gè)路徑<(I2:2I1:2)>；不包含I3，因?yàn)樗闹С侄扔?jì)數(shù)為1，小于最小支持度計(jì)數(shù)。該單個(gè)路徑產(chǎn)生頻繁模式的所有組合：I2I5:2,I1I5:2,I2I1I5:2。6.2.4不產(chǎn)生候選挖掘頻繁項(xiàng)集6.2.4不產(chǎn)生候選挖掘頻繁項(xiàng)集對(duì)于I4，它的兩個(gè)前綴形成條件模式基{(I2I1:1),(I2:1)，產(chǎn)生一個(gè)單結(jié)點(diǎn)的條件FP-樹<I2:2>，并導(dǎo)出一個(gè)頻繁模式I2I4:2。注意，盡管I5跟在第一個(gè)分枝中的I4之后，也沒有必要在此分析中包含I5，因?yàn)樯婕癐5的頻繁模式在I5的考察時(shí)已經(jīng)分析過。這就是我們?yōu)槭裁从珊竺?，而不是由前面開始處理的原因。6.2.4不產(chǎn)生候選挖掘頻繁項(xiàng)集與以上分析類似，I3的條件模式基是{(I2I1:2),(I2:2),(I1:2)}。它的條件FP-樹有兩個(gè)分枝<I2:4,I1:2>和<I1:2>，如圖6.9所示，它產(chǎn)生模式集：{I2I3:4,I1I3:2,I2I1I3:2}。最后，I1的條件模式基是{(I2,4)}，它的FP-樹只包含一個(gè)結(jié)點(diǎn)<I2:4>，產(chǎn)生一個(gè)頻繁模式I2I1:4。挖掘過程總結(jié)在圖不產(chǎn)生候選挖掘頻繁項(xiàng)集算法：FP-增長。使用FP-樹，通過模式段增長，挖掘頻繁模式。輸入：事務(wù)數(shù)據(jù)庫D；最小支持度閾值min_sup。輸出：頻繁模式的完全集。方法：1．按以下步驟構(gòu)造FP-樹：(a)掃描事務(wù)數(shù)據(jù)庫D一次。收集頻繁項(xiàng)的集合F和它們的支持度。對(duì)F按支持度降序排序，結(jié)果為頻繁項(xiàng)表L。6.2.4不產(chǎn)生候選挖掘頻繁項(xiàng)集(b)創(chuàng)建FP-樹的根結(jié)點(diǎn)，以“null”標(biāo)記它。對(duì)于D中每個(gè)事務(wù)Trans，執(zhí)行：選擇Trans中的頻繁項(xiàng)，并按L中的次序排序。設(shè)排序后的頻繁項(xiàng)表為[p|P]，其中，p是第一個(gè)元素，而P是剩余元素的表。調(diào)用insert_tree([p

|P],T)。該過程執(zhí)行情況如下。如果T有子女N使得N.item-name=p.item-name，則N的計(jì)數(shù)增加1；否則創(chuàng)建一個(gè)新結(jié)點(diǎn)N，將其計(jì)數(shù)設(shè)置為1，鏈接到它的父結(jié)點(diǎn)T，并且通過結(jié)點(diǎn)鏈結(jié)構(gòu)將其鏈接到具有相同item-name的結(jié)點(diǎn)。如果P非空，遞歸地調(diào)用insert_tree(P,N)。6.2.4不產(chǎn)生候選挖掘頻繁項(xiàng)集6.2.4不產(chǎn)生候選挖掘頻繁項(xiàng)集FP-增長方法將發(fā)現(xiàn)長頻繁模式的問題轉(zhuǎn)換成遞歸地發(fā)現(xiàn)一些短模式，然后與后綴連接。它使用最不頻繁的項(xiàng)作后綴，提供了好的選擇性。該方法大大降低了搜索開銷。當(dāng)數(shù)據(jù)庫很大時(shí)，構(gòu)造基于內(nèi)存的FP-樹是不現(xiàn)實(shí)的。一種有趣的替換是首先將數(shù)據(jù)庫劃分成投影數(shù)據(jù)庫的集合，然后在每個(gè)投影數(shù)據(jù)庫上構(gòu)造FP-樹并挖掘它。該過程可以遞歸地用于投影數(shù)據(jù)庫，如果它的FP-樹還不能放進(jìn)內(nèi)存。對(duì)FP-樹方法的性能研究表明：對(duì)于挖掘長的和短的頻繁模式，它都是有效的和可規(guī)?；?，并且大約比Apriori

算法快一個(gè)數(shù)量級(jí)。它也比樹-投影算法快。樹-投影算法遞歸地將數(shù)據(jù)庫投影為投影數(shù)據(jù)庫樹。6.2.5冰山查詢Apriori

算法可以用來提高回答冰山查詢的效率。冰山查詢?cè)跀?shù)據(jù)挖掘中經(jīng)常用，特別是對(duì)購物籃分析。冰山查詢?cè)谝粋€(gè)屬性或?qū)傩约嫌?jì)算一個(gè)聚集函數(shù)，以找出大于某個(gè)指定閾值的聚集值。給定關(guān)系R，它具有屬性a_1,a_2,...,a_n

和b，一個(gè)聚集函數(shù)agg_f，冰山查詢形如：6.2.5冰山查詢給定大量輸入數(shù)據(jù)元組，滿足having子句中的閾值的輸出元組數(shù)量相對(duì)很少。輸出結(jié)果看作“冰山頂”，而“冰山”是輸入數(shù)據(jù)集。例6.4一個(gè)冰山查詢：假定給定銷售數(shù)據(jù)，你想產(chǎn)生這樣的一個(gè)顧客-商品對(duì)的列表，這些顧客購買商品的數(shù)量達(dá)到3件或更多。這可以用下面的冰山查詢表示：6.2.5冰山查詢SelectP.cust_ID,P.Item_ID,SUM(P.qty)FromPurchasesPgroupbyP.cust_ID,Pitem_IDHavingSUM(P.qty)>=36.2.5冰山查詢“如何回答例6.4的查詢？”一個(gè)常用的策略是使用散列或排序，對(duì)所有顧客-商品分組，計(jì)算聚集函數(shù)SUM的值，然后刪除被給定的顧客購買的商品數(shù)量少于3的那些。相對(duì)于處理的元組總數(shù)，滿足該條件的元組多半很少，為改進(jìn)性能留下了空間。我們可以使用Apriori

性質(zhì)的變形，裁減需要考慮的顧客-商品對(duì)。即，不是考查每個(gè)顧客購買的每種商品的數(shù)量，我們可以：6.2.5冰山查詢6.2.5冰山查詢由先驗(yàn)知識(shí)，我們可以刪除許多被散列/排序方法產(chǎn)生的顧客-商品對(duì)：僅對(duì)cust_list

中的顧客和在item_list

中的商品產(chǎn)生候選顧客-商品對(duì)。對(duì)每個(gè)這樣的對(duì)，維持一個(gè)計(jì)數(shù)。盡管該方法通過預(yù)先裁減許多對(duì)或分組提高了性能，所產(chǎn)生的顧客-商品對(duì)數(shù)量可能依然很大，不能放進(jìn)內(nèi)存?？梢詫⑸⒘泻瓦x樣策略集成到該過程，幫助提高該查詢回答技術(shù)的總體性能。6.2.5冰山查詢6.2.5冰山查詢6.2.5冰山查詢多層關(guān)聯(lián)規(guī)則(1)數(shù)據(jù)項(xiàng)中經(jīng)常會(huì)形成概念分層底層的數(shù)據(jù)項(xiàng)，其支持度往往也較低這意味著挖掘底層數(shù)據(jù)項(xiàng)之間的關(guān)聯(lián)規(guī)則必須定義不同的支持度AllComputeraccessorysoftwarelaptopfinancialmousecolorprintercomputerdesktopIBMedu.Microsoftb/wHPSonywristpadLogitechTIDItemsT1{IBMD/C,Sonyb/w}T2{M.Sw.,Ms.fin.Sw.}T3{Logi.mouse,Ergowaywristpad}T4{IBMD/C,Ms.Fin.Sw.}T5{IBMD/C}Ergoway多層關(guān)聯(lián)規(guī)則(2)在適當(dāng)?shù)牡燃?jí)挖掘出來的數(shù)據(jù)項(xiàng)間的關(guān)聯(lián)規(guī)則可能是非常有用的通常，事務(wù)數(shù)據(jù)庫中的數(shù)據(jù)也是根據(jù)維和概念分層來進(jìn)行儲(chǔ)存的這為從事務(wù)數(shù)據(jù)庫中挖掘不同層次的關(guān)聯(lián)規(guī)則提供了可能。在多個(gè)抽象層挖掘關(guān)聯(lián)規(guī)則，并在不同的抽象層進(jìn)行轉(zhuǎn)化，是數(shù)據(jù)挖掘系統(tǒng)應(yīng)該提供的能力挖掘多層關(guān)聯(lián)規(guī)則的方法通常，多層關(guān)聯(lián)規(guī)則的挖掘還是使用置信度－支持度框架，可以采用自頂向下策略請(qǐng)注意：概念分層中，一個(gè)節(jié)點(diǎn)的支持度肯定不小于該節(jié)點(diǎn)的任何子節(jié)點(diǎn)的支持度由概念層1開始向下，到較低的更特定的概念層，對(duì)每個(gè)概念層的頻繁項(xiàng)計(jì)算累加計(jì)數(shù)每一層的關(guān)聯(lián)規(guī)則挖掘可以使用Apriori等多種方法例如：先找高層的關(guān)聯(lián)規(guī)則：computer->printer[20%,60%]再找較低層的關(guān)聯(lián)規(guī)則：laptop->colorprinter[10%,50%]多層關(guān)聯(lián)——一致支持度一致支持度：對(duì)所有層都使用一致的最小支持度優(yōu)點(diǎn)：搜索時(shí)容易采用優(yōu)化策略，即一個(gè)項(xiàng)如果不滿足最小支持度，它的所有子項(xiàng)都可以不用搜索缺點(diǎn)：最小支持度值設(shè)置困難太高：將丟掉出現(xiàn)在較低抽象層中有意義的關(guān)聯(lián)規(guī)則太低：會(huì)在較高層產(chǎn)生太多的無興趣的規(guī)則多層關(guān)聯(lián)——遞減支持度使用遞減支持度，可以解決使用一致支持度時(shí)在最小支持度值上設(shè)定的困難遞減支持度：在較低層使用遞減的最小支持度每一層都有自己的一個(gè)獨(dú)立的最小支持度抽象層越低，對(duì)應(yīng)的最小支持度越小min_sup=5%min_sup=5%min_sup=3%多層關(guān)聯(lián)——搜索策略(1)具有遞減支持度的多層關(guān)聯(lián)規(guī)則的搜索策略逐層獨(dú)立：完全的寬度搜索，沒有頻繁項(xiàng)集的背景知識(shí)用于剪枝層交叉單項(xiàng)過濾：一個(gè)第i層的項(xiàng)被考察，當(dāng)且僅當(dāng)它在第（i-1）層的父節(jié)點(diǎn)是頻繁的（P165,圖6-14）(computer)(laptopcomputer,desktopcomputer)層交叉k項(xiàng)集過濾：一個(gè)第i層的k項(xiàng)集被考察，當(dāng)且僅當(dāng)它在第(i-1)層的對(duì)應(yīng)父節(jié)點(diǎn)k-項(xiàng)集是頻繁的（P165,圖6-15）(computer,printer)((laptopcomputer,colorprinter),(desktopcomputer,b/wprinter)…)多層關(guān)聯(lián)——搜索策略(2)搜索策略比較逐層獨(dú)立策略條件松，可能導(dǎo)致底層考察大量非頻繁項(xiàng)層交叉k項(xiàng)集過濾策略限制太強(qiáng)，僅允許考察頻繁k-項(xiàng)集的子女層交叉單項(xiàng)過濾策略是上述兩者的折中，但仍可能丟失低層頻繁項(xiàng)（圖6-14)受控的層交叉單項(xiàng)過濾策略層交叉單項(xiàng)過濾策略的改進(jìn)版本設(shè)置一個(gè)層傳遞臨界值，用于向較低層傳遞相對(duì)頻繁的項(xiàng)。即如果滿足層傳遞臨界值，則允許考察不滿足最小支持度臨界值的項(xiàng)的子女用戶對(duì)進(jìn)一步控制多概念層上的挖掘過程有了更多的靈活性，同時(shí)減少無意義關(guān)聯(lián)的考察和產(chǎn)生min_sup=12%level_passage_support=8%min_sup=3%檢查冗余的多層關(guān)聯(lián)規(guī)則挖掘多層關(guān)聯(lián)規(guī)則時(shí)，由于項(xiàng)間的“祖先”關(guān)系，有些發(fā)現(xiàn)的規(guī)則將是冗余的例如：desktopcomputer=>b/wprinter[sup=8%,con=70%] (1)IBMdesktopcomputer=>b/wprinter[sup=2%,con=72%](2)上例中，我們說第一個(gè)規(guī)則是第二個(gè)規(guī)則的“祖先”如果規(guī)則(2)中的項(xiàng)用它在概念分層中的“祖先”代替，能得到(1)，而且(1)的支持度和置信度都接近“期望”值，則(1)是冗余的。多維關(guān)聯(lián)規(guī)則——概念單維關(guān)聯(lián)規(guī)則：buys(X,“milk”)＝buys(X,“bread”)多維關(guān)聯(lián)規(guī)則：涉及兩個(gè)或多個(gè)維或謂詞的關(guān)聯(lián)規(guī)則維間關(guān)聯(lián)規(guī)則：不包含重復(fù)的謂詞age(X,”19-25”)∧occupation(X,“student”)=>buys(X,“coke”)混合維關(guān)聯(lián)規(guī)則：包含某些謂詞的多次出現(xiàn)age(X,”19-25”)∧buys(X,“popcorn”)=>buys(X,“coke”)在多維關(guān)聯(lián)規(guī)則挖掘中，我們搜索的不是頻繁項(xiàng)集，而是頻繁謂詞集。k-謂詞集是包含k個(gè)合取謂詞的集合。例如：{age,occupation,buys}是一個(gè)3-謂詞集挖掘多維關(guān)聯(lián)規(guī)則的技術(shù)數(shù)據(jù)屬性可以分為分類屬性和量化屬性分類屬性具有有限個(gè)不同值，值之間無序量化屬性數(shù)值類型的值，并且值之間有一個(gè)隱含的序挖掘多維關(guān)聯(lián)規(guī)則的技術(shù)可以根據(jù)量化屬性的處理分為三種基本方法：1.量化屬性的靜態(tài)離散化使用預(yù)定義的概念分層對(duì)量化屬性進(jìn)行靜態(tài)地離散化2.量化關(guān)聯(lián)規(guī)則根據(jù)數(shù)據(jù)的分布，將量化屬性離散化到“箱”3.基于距離的關(guān)聯(lián)規(guī)則考慮數(shù)據(jù)點(diǎn)之間的距離，動(dòng)態(tài)地離散化量化屬性多維關(guān)聯(lián)規(guī)則挖掘——使用量化屬性的靜態(tài)離散化量化屬性使用預(yù)定義的概念分層，在挖掘前進(jìn)行離散化數(shù)值屬性的值用區(qū)間代替如果任務(wù)相關(guān)數(shù)據(jù)存在關(guān)系數(shù)據(jù)庫中，則找出所有頻繁的k-謂詞集將需要k或k+1次表掃描數(shù)據(jù)立方體技術(shù)非常適合挖掘多維關(guān)聯(lián)規(guī)則n-維方體的單元用于存放對(duì)應(yīng)n-謂詞集的計(jì)數(shù)或支持度，0-D方體用于存放任務(wù)相關(guān)數(shù)據(jù)的事務(wù)總數(shù)如果包含感興趣的維的數(shù)據(jù)立方體已經(jīng)存在并物化，挖掘?qū)?huì)很快，同時(shí)可以利用Apriori性質(zhì)：頻繁謂詞集的每個(gè)子集也必須是頻繁的(income)(age)()(buys)(age,income)(age,buys)(income,buys)(age,income,buys)挖掘量化關(guān)聯(lián)規(guī)則(1)量化關(guān)聯(lián)規(guī)則中，數(shù)值屬性將根據(jù)某種挖掘標(biāo)準(zhǔn)，進(jìn)行動(dòng)態(tài)的離散化例如：最大化挖掘規(guī)則的置信度和緊湊性為了簡化量化關(guān)聯(lián)規(guī)則挖掘的討論，我們將聚焦于類似以下形式的2-維量化關(guān)聯(lián)規(guī)則：Aquan1

Aquan2Acat（兩個(gè)量化屬性和一個(gè)分類屬性間的關(guān)聯(lián)）例如：age(X,”30-39”)income(X,”42K-48K