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

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

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

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

C，其支持度=50%置信度Apriori算法(1)Apriori算法是挖掘布爾關聯規則頻繁項集的算法Apriori算法利用的是Apriori性質：頻繁項集的所有非空子集也必須是頻繁的。模式不可能比A更頻繁的出現Apriori算法是反單調的，即一個集合如果不能通過測試，則該集合的所有超集也不能通過相同的測試。Apriori性質通過減少搜索空間，來提高頻繁項集逐層產生的效率Apriori算法(2)Apriori算法利用頻繁項集性質的先驗知識（priorknowledge），通過逐層搜索的迭代方法，即將k-項集用于探察(k+1)-項集，來窮盡數據集中的所有頻繁項集。先找到頻繁1-項集集合L1,然后用L1找到頻繁2-項集集合L2，接著用L2找L3，直到找不到頻繁k-項集，找每個Lk需要一次數據庫掃描。Apriori算法步驟Apriori算法由連接和剪枝兩個步驟組成。連接步：為找Lk，通過Lk-1

與自己連接產生候選k-項集的集合。該候選項集的集合記作Ck。設l1

和l2

是Lk-1

中的項集。記號li[j]表示li

的第j項（例如，l1[k-2]表示l1

的倒數第3項）。為方便計，假定事務或項集中的項按字典次序排序。執行連接；其中，Lk-1

的元素是可連接的，如果它們前(k-2)個項相同；即，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])是簡單地保證不產生重復。連接l1

和l2

產生的結果項集是l1[1]l1

[2]...l1

[k-1]l2

[k-1]。剪枝步：Ck

是Lk

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

中。掃描數據庫，確定Ck

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

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

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

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

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

的事務數據庫。數據庫中有9個事務，即|D|=9。Apriori

假定事務中的項按字典次序存放。我們使用圖6.3解釋Apriori算法發現D中的頻繁項集。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最小支持計數：2使用Apiori性質由L2產生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性質剪枝：頻繁項集的所有子集必須是頻繁的，對候選項C3，我們可以刪除其子集為非頻繁的選項：{A,B,C}的2項子集是{A,B},{A,C},{B,C}，其中{A,B}不是L2的元素，所以刪除這個選項；{A,C,E}的2項子集是{A,C},{A,E},{C,E}，其中{A,E}

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

僅在每次完整的數據庫掃描之前確定新的候選，在這種變形中，可以在任何開始點添加新的候選項集。該技術動態地評估已被計數的所有項集的支持度，如果一個項集的所有子集已被確定為頻繁的，則添加它作為新的候選。結果算法需要的數據庫掃描比Apriori

少。其它變形涉及多層和多維關聯規則挖掘，在本章的其余部分討論。涉及空間數據、時間序列數據和多媒體數據的關聯挖掘在第9章討論。6.2.4不產生候選挖掘頻繁項集正如我們已經看到的，在許多情況下，Apriori

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

算法需要產生多達107個候選2-項集，累計并檢查它們的頻繁性。此外，為發現長度為100的頻繁模式，如{a1,...,a100}，它必須產生多達2100≈1030

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

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

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

算法快一個數量級。它也比樹-投影算法快。樹-投影算法遞歸地將數據庫投影為投影數據庫樹。6.2.5冰山查詢Apriori

算法可以用來提高回答冰山查詢的效率。冰山查詢在數據挖掘中經常用，特別是對購物籃分析。冰山查詢在一個屬性或屬性集上計算一個聚集函數，以找出大于某個指定閾值的聚集值。給定關系R，它具有屬性a_1,a_2,...,a_n

和b，一個聚集函數agg_f，冰山查詢形如：6.2.5冰山查詢給定大量輸入數據元組，滿足having子句中的閾值的輸出元組數量相對很少。輸出結果看作“冰山頂”，而“冰山”是輸入數據集。例6.4一個冰山查詢：假定給定銷售數據，你想產生這樣的一個顧客-商品對的列表，這些顧客購買商品的數量達到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的查詢？”一個常用的策略是使用散列或排序，對所有顧客-商品分組，計算聚集函數SUM的值，然后刪除被給定的顧客購買的商品數量少于3的那些。相對于處理的元組總數，滿足該條件的元組多半很少，為改進性能留下了空間。我們可以使用Apriori

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

中的顧客和在item_list

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

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