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

1、挖掘大型數(shù)據(jù)庫中的關(guān)聯(lián)規(guī)則關(guān)聯(lián)規(guī)則挖掘發(fā)現(xiàn)大量數(shù)據(jù)中項集之間有趣的關(guān)聯(lián)或相關(guān)聯(lián)系。隨著大量數(shù)據(jù)不停地收集和存儲，許多業(yè)界人士對于從他們的數(shù)據(jù)庫中挖掘關(guān)聯(lián)規(guī)則越來越感興趣。從大量商務(wù)事務(wù)記錄中發(fā)現(xiàn)有趣的關(guān)聯(lián)關(guān)系，可以幫助許多商務(wù)決策的制定，如分類設(shè)計、交叉購物和賤賣分析。關(guān)聯(lián)規(guī)則挖掘的一個典型例子是購物籃分析。該過程通過發(fā)現(xiàn)顧客放入其購物籃中不同商品（圖6.1）之間聯(lián)系，分析顧客的購買習(xí)慣。通過了解哪些商品頻繁地被顧客同時購買，這種關(guān)聯(lián)的發(fā)現(xiàn)可以幫助零售商制定營銷策略。例如，在同一次去超級市場，如果顧客購買牛奶，他也購買面包（和什么類型的面包）的可能性有多大？通過幫助零售商有選擇地經(jīng)銷和安排貨架

2、，這種信息可以引導(dǎo)銷售。例如，將牛奶和面包盡可能放近一些，可以進(jìn)一步刺激一次去商店同時購買這些商品。圖6.1 購物籃分析數(shù)據(jù)是事務(wù)的或關(guān)系的，如何由大量的數(shù)據(jù)中發(fā)現(xiàn)關(guān)聯(lián)規(guī)則？什么樣的關(guān)聯(lián)規(guī)則最有趣？我們?nèi)绾螏椭蛑笇?dǎo)挖掘過程發(fā)現(xiàn)有趣的關(guān)聯(lián)規(guī)則？對于關(guān)聯(lián)規(guī)則挖掘，什么樣的語言結(jié)構(gòu)對于定義關(guān)聯(lián)挖掘查詢是有用的？本章我們將深入研究這些問題。6.1 關(guān)聯(lián)規(guī)則挖掘關(guān)聯(lián)規(guī)則挖掘?qū)ふ医o定數(shù)據(jù)集中項之間的有趣聯(lián)系。本節(jié)簡要介紹關(guān)聯(lián)規(guī)則挖掘。6.1.1小節(jié)給出一個購物籃分析的例子，這是關(guān)聯(lián)規(guī)則挖掘的最初形式。挖掘關(guān)聯(lián)規(guī)則的基本概念在6.1.2小節(jié)給出。6.1.3小節(jié)給出一個路線圖，指向可挖掘的各種不同類型關(guān)聯(lián)規(guī)

3、則。6.1.1 購物籃分析：一個引發(fā)關(guān)聯(lián)規(guī)則挖掘的例子假定作為AllElectronics的分店經(jīng)理，你想更加了解你的顧客的購物習(xí)慣。例如，你想知道“什么商品組或集合顧客多半會在一次購物時同時購買？”為回答你的問題，你可以在你的商店顧客事務(wù)零售數(shù)據(jù)上運行購物籃分析。分析結(jié)果可以用于市場規(guī)劃、廣告策劃、分類設(shè)計。例如，購物籃分析可以幫助經(jīng)理設(shè)計不同的商店布局。一種策略是：經(jīng)常一塊購買的商品可以放近一些，以便進(jìn)一步刺激這些商品一起銷售。例如，如果顧客購買計算機(jī)也傾向于同時購買財務(wù)軟件，將硬件擺放離軟件陳列近一點，可能有助于增加二者的銷售。另一種策略是：將硬件和軟件放在商店的兩端，可能誘發(fā)買這些商品

4、的顧客一路挑選其它商品。例如，在決定購買一臺很貴的計算機(jī)之后，去看軟件陳列，購買財務(wù)軟件，路上可能看到安全系統(tǒng)，可能會決定也買家庭安全系統(tǒng)。購物籃分析也可以幫助零售商規(guī)劃什么商品降價出售。如果顧客趨向于同時購買計算機(jī)和打印機(jī)，打印機(jī)降價出售可能既促使購買打印機(jī)，又促使購買計算機(jī)。如果我們想象全域是商店中可利用的商品的集合，則每種商品有一個布爾變量，表示該商品的有無。每個籃子則可用一個布爾向量表示?？梢苑治霾紶栂蛄?，得到反映商品頻繁關(guān)聯(lián)或同時購買的購買模式。這些模式可以用關(guān)聯(lián)規(guī)則的形式表示。例如，購買計算機(jī)也趨向于同時購買財務(wù)管理軟件可以用以下關(guān)聯(lián)規(guī)則表示：support=2%,confiden

5、ce=60% (6.1)規(guī)則的支持度和置信度是兩個規(guī)則興趣度度量，已在前面4.1.4小節(jié)介紹。它們分別反映發(fā)現(xiàn)規(guī)則的有用性和確定性。關(guān)聯(lián)規(guī)則(6.1)的支持度2%意味分析事務(wù)的2%同時購買計算機(jī)和財務(wù)管理軟件。置信度60%意味購買計算機(jī)的顧客60%也購買財務(wù)管理軟件。關(guān)聯(lián)規(guī)則是有趣的，如果它滿足最小支持度閾值和最小置信度閾值。這些閾值可以由用戶或領(lǐng)域?qū)＜以O(shè)定。6.1.2 基本概念設(shè)I = i1 , i2 ,., im 是項的集合。設(shè)任務(wù)相關(guān)的數(shù)據(jù)D是數(shù)據(jù)庫事務(wù)的集合，其中每個事務(wù)T是項的集合，使得T I。每一個事務(wù)有一個標(biāo)識符，稱作TID。設(shè)A是一個項集，事務(wù)T包含A當(dāng)且僅當(dāng)A T。關(guān)聯(lián)規(guī)則是

6、形如A B的蘊涵式，其中A I，B I，并且A B = 。規(guī)則A B在事務(wù)集D中成立，具有支持度s，其中s是D中事務(wù)包含A B（即，A和B二者）的百分比。它是概率P(A B)。規(guī)則A B在事務(wù)集D中具有置信度c，如果D中包含A的事務(wù)同時也包含B的百分比是c。這是條件概率P(B|A)。即support (A B ) = P(A B) (6.2)confidence (A B ) = P(B|A) (6.3)同時滿足最小支持度閾值(min_sup)和最小置信度閾值(min_conf)的規(guī)則稱作強(qiáng)規(guī)則。為方便計，我們用0%和100%之間的值，而不是用0到1之間的值表示支持度和置信度。項的集合稱為項集

7、 在數(shù)據(jù)挖掘研究界，“itemset”比“item set”更常用。包含k個項的項集稱為k-項集。集合computer, financial_management_ software是一個2-項集。項集的出現(xiàn)頻率是包含項集的事務(wù)數(shù)，簡稱為項集的頻率、支持計數(shù)或計數(shù)。項集滿足最小支持度min_sup，如果項集的出現(xiàn)頻率大于或等于min_sup與D中事務(wù)總數(shù)的乘積。如果項集滿足最小支持度，則稱它為頻繁項集 在早期的工作中，滿足最小支持度的項集稱為大的。然而，該術(shù)語有時易混淆，因為它具有項集中項的個數(shù)的內(nèi)涵，而不是集合出現(xiàn)的頻率。因此，我們使用當(dāng)前術(shù)語頻繁。頻繁k -項集的集合通常記作Lk。 盡管頻

8、繁已取代大的，由于歷史的原因，頻繁k-項集仍記作Lk?！叭绾斡纱笮蛿?shù)據(jù)庫挖掘關(guān)聯(lián)規(guī)則？”關(guān)聯(lián)規(guī)則的挖掘是一個兩步的過程：找出所有頻繁項集：根據(jù)定義，這些項集出現(xiàn)的頻繁性至少和預(yù)定義的最小支持計數(shù)一樣。由頻繁項集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則：根據(jù)定義，這些規(guī)則必須滿足最小支持度和最小置信度。如果愿意，也可以使用附加的興趣度度量。這兩步中，第二步最容易。挖掘關(guān)聯(lián)規(guī)則的總體性能由第一步?jīng)Q定。6.1.3 關(guān)聯(lián)規(guī)則挖掘：一個路線圖購物籃分析只是關(guān)聯(lián)規(guī)則挖掘的一種形式。事實上，有許多種關(guān)聯(lián)規(guī)則。根據(jù)下面的標(biāo)準(zhǔn)，關(guān)聯(lián)規(guī)則有多種分類方法：根據(jù)規(guī)則中所處理的值類型：如果規(guī)則考慮的關(guān)聯(lián)是項的在與不在，則它是布爾關(guān)聯(lián)規(guī)則。例如，

9、上面的規(guī)則(6.1)是由購物籃分析得到的布爾關(guān)聯(lián)規(guī)則。如果規(guī)則描述的是量化的項或?qū)傩灾g的關(guān)聯(lián)，則它是量化關(guān)聯(lián)規(guī)則。在這種規(guī)則中，項或?qū)傩缘牧炕祫澐譃閰^(qū)間。下面的規(guī)則(6.4)是量化關(guān)聯(lián)規(guī)則的一個例子，其中，X是代表顧客的變量。 (6.4)注意，量化屬性age 和income已離散化。根據(jù)規(guī)則中涉及的數(shù)據(jù)維：如果關(guān)聯(lián)規(guī)則中的項或?qū)傩悦總€只涉及一個維，則它是單維關(guān)聯(lián)規(guī)則。注意，(6.1)式可以寫作 (6.5)規(guī)則(6.1)是單維關(guān)聯(lián)規(guī)則，因為它只涉及一個維buys 按照多維數(shù)據(jù)庫使用的術(shù)語，我們把規(guī)則中的每個不同謂詞稱作維。如果規(guī)則涉及兩個或多個維，如維buys, time_of_transa

10、ction和customer_category，則它是多維關(guān)聯(lián)規(guī)則。上面的規(guī)則(6.4)是一個多維關(guān)聯(lián)規(guī)則，因為它涉及三個維age, income和buys。根據(jù)規(guī)則集所涉及的抽象層：有些挖掘關(guān)聯(lián)規(guī)則的方法可以在不同的抽象層發(fā)現(xiàn)規(guī)則。例如，假定挖掘的關(guān)聯(lián)規(guī)則集包含下面規(guī)則：age(X,”30.39”) buys(X,”laptop computer”) (6.6)age(X,”30.39”) buys(X,” computer”) (6.7)在規(guī)則(6.6)和(6.7)中，購買的商品涉及不同的抽象層（即，”computer”在比”laptop computer”高的抽象層）。我們稱所挖掘的規(guī)則

11、集由多層關(guān)聯(lián)規(guī)則組成。反之，如果在給定的規(guī)則集中，規(guī)則不涉及不同抽象層的項或?qū)傩?，則該集合包含單層關(guān)聯(lián)規(guī)則。根據(jù)關(guān)聯(lián)挖掘的各種擴(kuò)充：關(guān)聯(lián)挖掘可以擴(kuò)充到相關(guān)分析，那里，可以識別項是否相關(guān)。還可以擴(kuò)充到挖掘最大模式（即，最大的頻繁模式）和頻繁閉項集。最大模式是頻繁模式p，使得p的任何真超模式 q是p的超模式，如果p是q的子模式；即，如果q包含p。都不是頻繁的。頻繁閉項集是一個頻繁的、閉的項集；其中，項集c是閉的，如果不存在c的真超集c，使得每個包含c的事務(wù)也包含c。使用最大模式和頻繁閉項集可以顯著地壓縮挖掘所產(chǎn)生的頻繁項集數(shù)。本章的其余部分，你將學(xué)習(xí)上述每種關(guān)聯(lián)規(guī)則的挖掘方法。由事務(wù)數(shù)據(jù)庫挖掘單維

12、布爾關(guān)聯(lián)規(guī)則本節(jié)，你將學(xué)習(xí)挖掘最簡單形式的關(guān)聯(lián)規(guī)則的方法。這種關(guān)聯(lián)規(guī)則是單維、單層、布爾關(guān)聯(lián)規(guī)則，如6.1.1小節(jié)所討論的購物籃分析中的那些。我們以提供Apriori算法開始（6.2.1小節(jié)）。AprioriApriori算法的一些變形，用于提高效率和可規(guī)模性。6.2.4小節(jié)提出一些挖掘關(guān)聯(lián)規(guī)則方法，不象Apriori，它們不涉及“候選”Apriori的原則用于提高冰山查詢的效率。冰山查詢在購物籃分析中是常見的。6.2.1 Apriori算法：使用候選項集找頻繁項集Apriori算法是一種最有影響的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項集的算法。算法的名字基于這樣的事實：算法使用頻繁項集性質(zhì)的先驗知識，正如我

13、們將看到的。Apriori使用一種稱作逐層搜索的迭代方法，k-項集用于探索(k+1)-項集。首先，找出頻繁1-項集的集合。該集合記作L1。L1用于找頻繁2-項集的集合L2，而L2用于找L3，如此下去，直到不能找到頻繁k-項集。找每個Lk需要一次數(shù)據(jù)庫掃描。為提高頻繁項集逐層產(chǎn)生的效率，一種稱作Apriori性質(zhì)的重要性質(zhì)用于壓縮搜索空間。我們先介紹該性質(zhì)，然后用一個例子解釋它的使用。Apriori性質(zhì)：頻繁項集的所有非空子集都必須也是頻繁的。Apriori性質(zhì)基于如下觀察：根據(jù)定義，如果項集I不滿足最小支持度閾值s，則I不是頻繁的，即P(I) s。如果項A添加到I，則結(jié)果項集（即，I A）不可

14、能比I更頻繁出現(xiàn)。因此，I A也不是頻繁的，即P(I A) s。該性質(zhì)屬于一種特殊的分類，稱作反單調(diào)，意指如果一個集合不能通過測試，則它的所有超集也都不能通過相同的測試。稱它為反單調(diào)的，因為在通不過測試的意義下，該性質(zhì)是單調(diào)的?！叭绾螌priori性質(zhì)用于算法？”為理解這一點，我們必須看看如何用Lk - 1找Lk。下面的兩步過程由連接和剪枝組成。連接步：為找Lk，通過Lk - 1與自己連接產(chǎn)生候選k-項集的集合。該候選項集的集合記作Ck。設(shè)l1和l2是Lk - 1中的項集。記號lij表示li的第j項（例如，l1k-2表示l1的倒數(shù)第3項）。為方便計，假定事務(wù)或項集中的項按字典次序排序。執(zhí)行連

15、接Lk - 1Lk - 1；其中，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)是簡單地保證不產(chǎn)生重復(fù)。連接l1和l2產(chǎn)生的結(jié)果項集是l1 1 l1 2. l1 k-1 l2 k-1。剪枝步：Ck是Lk的超集；即，它的成員可以是，也可以不是頻繁的，但所有的頻繁k-項集都包含在Ck中。掃描數(shù)據(jù)庫，確定Ck中每個候選的計數(shù)，從而確定Lk（即，根據(jù)定義，計數(shù)值不小于最小支持度計數(shù)

16、的所有候選是頻繁的，從而屬于Lk）。然而，Ck可能很大，這樣所涉及的計算量就很大。為壓縮Ck，可以用以下辦法使用Apriori性質(zhì)：任何非頻繁的(k-1)-項集都不是可能是頻繁k-項集的子集。因此，如果一個候選k-項集的(k-1)-子集不在Lk - 1中，則該候選也不可能是頻繁的，從而可以由Ck中刪除。這種子集測試可以使用所有頻繁項集的散列樹快速完成。例 讓我們看一個Apriori的具體例子。該例基于圖6.2的AllElectronics的事務(wù)數(shù)據(jù)庫。數(shù)據(jù)庫中有9個事務(wù)，即|D| = 9。Apriori假定事務(wù)中的項按字典次序存放。我們使用圖6.3解釋Apriori算法發(fā)現(xiàn)D中的頻繁項集。Al

17、lElectronics數(shù)據(jù)庫TIDList of item_IDsT100T200T300T400T500T600T700T800T900I1,I2,I5I2,I4I2,I3I1,I2,I4I1,I3I2,I3I1,I3I1,I2,I3,I5I1,I2,I3圖 AllElectronics某分店的事務(wù)數(shù)據(jù)在算法的第一次迭代，每個項都是候選1-項集的集合C1的成員。算法簡單地掃描所有的事務(wù)，對每個項的出現(xiàn)次數(shù)計數(shù)。假定最小事務(wù)支持計數(shù)為2（即，min_sup = 2/9 = 22%）。可以確定頻繁1-項集的集合L1。它由具有最小支持度的候選1-項集組成。為發(fā)現(xiàn)頻繁2-項集的集合L2，算法使用L

18、1L1產(chǎn)生候選2-項集的集合C2 L1L1等價于L1 L1，因為LkLk的定義要求兩個連接的項集共享k-1=0個項。C2由個2-項集組成。下一步，掃描D中事務(wù)，計算C2中每個候選項集的支持計數(shù)，如圖6.3的第二行的中間表所示。確定頻繁2-項集的集合L2，它由具有最小支持度的C2中的候選2-項集組成。圖6.3 候選項集和頻繁項集的產(chǎn)生，最小支持計數(shù)為2連接：C3= L2L2=I1,I2,I1,I3,I1,I5,I2,I3,I2,I4,I2,I5I1,I2,I1,I3,I1,I5,I2,I3,I2,I4,I2,I5 = I1,I2,I3,I1,I2,I5,I1,I3,I5,I2,I3,I4,I2,

19、I3,I5,I2,I4,I5使用Apriori性質(zhì)剪枝：頻繁項集的所有子集必須是頻繁的。存在候選項集，其子集不是頻繁的嗎？I1,I2,I3的2-項子集是I1,I2，I1,I3和I2,I3。I1,I2,I3的所有2-項子集都是L2的元素。因此，保留I1,I2,I3在C3中。I1,I2,I5的2-項子集是I1,I2，I1,I5和I2,I5。I1,I2,I5的所有2-項子集都是L2的元素。因此，保留I1,I2,I5在C3中。I1,I3,I5的2-項子集是I1,I3，I1,I5和I3,I5。I3,I5不是L2的元素，因而不是頻繁的。這樣，由C3中刪除I1,I3,I5。I2,I3,I4的2-項子集是I2

20、,I3，I2,I4和I3,I4。I3,I4不是L2的元素，因而不是頻繁的。這樣，由C3中刪除I2,I3,I4。I2,I3,I5的2-項子集是I2,I3，I2,I5和I3,I5。I3,I5不是L2的元素，因而不是頻繁的。這樣，由C3中刪除I2,I3,I5。I2,I4,I5的2-項子集是I2,I4，I2,I5和I4,I5。I4,I5不是L2的元素，因而不是頻繁的。這樣，由C3中刪除I2,I3,I5。3這樣，剪枝后C3 = I1,I2,I3,I1,I2,I5。圖6.4 使用Apriori性質(zhì)，由L2產(chǎn)生候選3-項集C3候選3-項集的集合C3的產(chǎn)生詳細(xì)地列在圖6.4中。首先，令C3 = L2L2 =

21、I1,I2,I3, I1,I2,I5, I1,I3,I5, I2,I3,I4, I2,I3,I5, I2,I4,I5。根據(jù)Apriori性質(zhì)，頻繁項集的所有子集必須是頻繁的，我們可以確定后4個候選不可能是頻繁的。因此，我們把它們由C3刪除，這樣，在此后掃描D確定L3時就不必再求它們的計數(shù)值。注意，Apriori算法使用逐層搜索技術(shù)，給定k-項集，我們只需要檢查它們的(k-1)-子集是否頻繁。掃描D中事務(wù)，以確定L3，它由具有最小支持度的C3中的候選3-項集組成（圖6.3）。算法使用L3L3產(chǎn)生候選4-項集的集合C4。盡管連接產(chǎn)生結(jié)果I1,I2,I3,I5，這個項集被剪去，因為它的子集I1,I3

22、,I5不是頻繁的。這樣，C4 = ，因此算法終止，找出了所有的頻繁項集。Apriori算法和它的相關(guān)過程的偽代碼。Apriori的第1步找出頻繁1-項集的集合L1。在2-10步，Lk - 1用于產(chǎn)生候選C k，以找出L k。Apriori_gen過程產(chǎn)生候選，然后使用Apriori性質(zhì)刪除那些具有非頻繁子集的候選（步驟3）。該過程在下面描述。一旦產(chǎn)生了所有的候選，就掃描數(shù)據(jù)庫（步驟4）。對于每個事務(wù)，使用subset函數(shù)找出事務(wù)中是候選的所有子集（步驟5），并對每個這樣的候選累加計數(shù)（步驟6和7）。最后，所有滿足最小支持度的候選形成頻繁項集L。然后，調(diào)用一個過程，由頻繁項集產(chǎn)生關(guān)聯(lián)規(guī)則。該過程

23、在6.2.2小節(jié)介紹。算法 (Apriori) 使用逐層迭代找出頻繁項集輸入：事務(wù)數(shù)據(jù)庫D；最小支持度閾值。輸出：D中的頻繁項集L。方法：L1 = find_frequent_1_itemsets(D);for (k = 2; Lk-1 ; k+) Ck = aproiri_gen(Lk-1,min_sup);for each transaction tD /scan D for countCt = subset(Ck,t); /get subsets of t that are candidatesfor each candidate cCt c.count+;Lk=cCk | c.coun

24、t min_supreturn L = kLk；procedure apriori_gen(Lk-1: frequent (k-1)-itemset; min_sup: support)for each itemset l1Lk-1for each itemset l2Lk-1if (l11=l21).(l1k-2=l2k-2)(l1k-11)。例如，當(dāng)掃描數(shù)據(jù)庫中每個事務(wù)，由C1中的候選1-項集產(chǎn)生頻繁1-項集L1時，我們可以對每個事務(wù)產(chǎn)生所有的2-項集，將它們散列（即，映射）到散列表結(jié)構(gòu)的不同桶中，并增加對應(yīng)的桶計數(shù)（圖6.6）。在散列表中對應(yīng)的桶計數(shù)低于支持度閾值的2-項集不可能是頻繁2

25、-項集，因而應(yīng)當(dāng)由候選項集中刪除。這種基于散列的技術(shù)可以大大壓縮要考察的k-項集（特別是當(dāng)k = 2時）。事務(wù)壓縮（壓縮進(jìn)一步迭代掃描的事務(wù)數(shù)）：不包含任何k-項集的事務(wù)不可能包含任何(k+1)-項集。這樣，這種事務(wù)在其后的考慮時，可以加上標(biāo)記或刪除，因為為產(chǎn)生j-項集(j k)，掃描數(shù)據(jù)庫時不再需要它們。劃分（為找候選項集劃分?jǐn)?shù)據(jù)）：可以使用劃分技術(shù)，它只需要兩次數(shù)據(jù)庫掃描，以挖掘頻繁項集（圖6.7）。它包含兩遍。在第I遍，算法將D中的事務(wù)劃分成n個非重疊的部分。如果D中事務(wù)的最小支持度閾值為min_sup，則每個部分的最小支持度計數(shù)為min_sup該部分中事務(wù)數(shù)。對每一部分，找出該部分內(nèi)的

26、頻繁項集。這些稱作局部頻繁項集。該過程使用一種特殊的數(shù)據(jù)結(jié)構(gòu)，對于每個項集，記錄包含項集中項的事務(wù)的TID。這使得對于k = 1,2,.，找出所有的局部頻繁k-項集只需要掃描一次數(shù)據(jù)庫。局部頻繁項集可能不是整個數(shù)據(jù)庫D的頻繁項集。D的任何頻繁項集必須作為局部頻繁項集至少出現(xiàn)在一個部分中。這樣，所有的局部頻繁項集作為D的候選項集。所有部分的頻繁項集的集合形成D的全局候選項集。在第II遍，第二次掃描D，評估每個候選的實際支持度，以確定全局頻繁項集。每一部分的大小和劃分的數(shù)目這樣確定，使得每一部分能夠放入內(nèi)存，這樣每遍只需要讀一次。圖 通過劃分挖掘選樣（在給定數(shù)據(jù)的一個子集挖掘）：選樣方法的基本思想

27、是：選取給定數(shù)據(jù)庫D的隨機(jī)樣本S，然后，在S而不是在D中搜索頻繁項集。用這種方法，我們犧牲了一些精度換取了有效性。樣本S的大小這樣選取，使得可以在內(nèi)存搜索S中頻繁項集；這樣，總共只需要掃描一次S中的事務(wù)。由于我們搜索S 中而不是D中的頻繁項集，我們可能丟失一些全局頻繁項集。為減少這種可能性，我們使用比最小支持度低的支持度閾值來找出局部于S的頻繁項集（記作LS）。然后，數(shù)據(jù)庫的其余部分用于計算LS中每個項集的實際頻繁度。有一種機(jī)制可以用來確定是否所有的頻繁項集都包含在LS中。如果LS實際包含了D中的所有頻繁項集，只需要掃描一次D。否則，可以做第二次掃描，以找出在第一次掃描時遺漏的頻繁項集。當(dāng)效率

28、最為重要時，如計算密集的應(yīng)用必須在不同的數(shù)據(jù)上運行時，選樣方法特別合適。動態(tài)項集計數(shù)（在掃描的不同點添加候選項集）：動態(tài)項集計數(shù)技術(shù)將數(shù)據(jù)庫劃分為標(biāo)記開始點的塊。不象Apriori僅在每次完整的數(shù)據(jù)庫掃描之前確定新的候選，在這種變形中，可以在任何開始點添加新的候選項集。該技術(shù)動態(tài)地評估已被計數(shù)的所有項集的支持度，如果一個項集的所有子集已被確定為頻繁的，則添加它作為新的候選。結(jié)果算法需要的數(shù)據(jù)庫掃描比Apriori少。其它變形涉及多層和多維關(guān)聯(lián)規(guī)則挖掘，在本章的其余部分討論。涉及空間數(shù)據(jù)、時間序列數(shù)據(jù)和多媒體數(shù)據(jù)的關(guān)聯(lián)挖掘在第9章討論。6.2.4 不產(chǎn)生候選挖掘頻繁項集正如我們已經(jīng)看到的，在許多

29、情況下，Apriori的候選產(chǎn)生-檢查方法大幅度壓縮了候選項集的大小，并導(dǎo)致很好的性能。然而，它有兩種開銷可能并非微不足道的。它可能需要產(chǎn)生大量候選項集。例如，如果有104個頻繁1-項集，則Apriori算法需要產(chǎn)生多達(dá)107個候選2-項集，累計并檢查它們的頻繁性。此外，為發(fā)現(xiàn)長度為100的頻繁模式，如a1 ,., a100，它必須產(chǎn)生多達(dá)2100 1030個候選。它可能需要重復(fù)地掃描數(shù)據(jù)庫，通過模式匹配檢查一個很大的候選集合。對于挖掘長模式尤其如此?！翱梢栽O(shè)計一種方法，挖掘全部頻繁項集，而不產(chǎn)生候選嗎？”一種有趣的方法稱作頻繁模式增長，或簡單地，F(xiàn)P-增長，它采取如下分治策略：將提供頻繁項集

30、的數(shù)據(jù)庫壓縮到一棵頻繁模式樹（或FP-樹），但仍保留項集關(guān)聯(lián)信息；然后，將這種壓縮后的數(shù)據(jù)庫分成一組條件數(shù)據(jù)庫（一種特殊類型的投影數(shù)據(jù)庫），每個關(guān)聯(lián)一個頻繁項，并分別挖掘每個數(shù)據(jù)庫。讓我們看一個例子。例 使用頻繁模式增長方法，我們重新考察例中圖事務(wù)數(shù)據(jù)庫D的挖掘。數(shù)據(jù)庫的第一次掃描與Apriori相同，它導(dǎo)出頻繁項（1-項集）的集合，并得到它們的支持度計數(shù)（頻繁性）。設(shè)最小支持度計數(shù)為2。頻繁項的集合按支持度計數(shù)的遞減序排序。結(jié)果集或表記作L。這樣，我們有L = I2:7, I1:6, I3:6, I4:2, I5:2。然后，F(xiàn)P-樹構(gòu)造如下：首先，創(chuàng)建樹的根結(jié)點，用“null”標(biāo)記。二次掃描

31、數(shù)據(jù)庫D。每個事務(wù)中的項按L中的次序處理（即，根據(jù)遞減支持度計數(shù)排序）并對每個事務(wù)創(chuàng)建一個分枝。例如，第一個事務(wù)“T100: I1, I2, I5”按L的次序包含三個項 I2, I1, I5，導(dǎo)致構(gòu)造樹的第一個分枝。該分枝具有三個結(jié)點，其中，I2作為根的子女鏈接，I1鏈接到I2，I5鏈接到I1。第二個事務(wù)T200按L的次序包含項I2和I4，它導(dǎo)致一個分枝，其中，I2鏈接到根，I4鏈接到I2。然而，該分枝應(yīng)當(dāng)與T100已存在的路徑共享前綴。這樣，我們將結(jié)點I2的計數(shù)增加1，并創(chuàng)建一個新結(jié)點(I4:1)，它作為(I2:2)的子女鏈接。一般地，當(dāng)為一個事務(wù)考慮增加分枝時，沿共同前綴上的每個結(jié)點的計數(shù)

32、增加1，為隨在前綴之后的項創(chuàng)建結(jié)點并鏈接。為方便樹遍歷，創(chuàng)建一個項頭表，使得每個項通過一個結(jié)點鏈指向它在樹中的出現(xiàn)。掃描所有的事務(wù)之后得到的樹展示在圖6.8中，附上相關(guān)的結(jié)點鏈。這樣，數(shù)據(jù)庫頻繁模式的挖掘問題就轉(zhuǎn)換成挖掘FP-樹問題。圖6.8 存放壓縮的頻繁模式信息的FP-樹FP-樹挖掘處理如下。由長度為1的頻繁模式（初始后綴模式）開始，構(gòu)造它的條件模式基（一個“子數(shù)據(jù)庫”， 由FP-樹中與后綴模式一起出現(xiàn)的前綴路徑集組成）。然后，構(gòu)造它的（條件）FP-樹，并遞歸地在該樹上進(jìn)行挖掘。模式增長通過后綴模式與由條件FP-樹產(chǎn)生的頻繁模式連接實現(xiàn)。FP-樹的挖掘總結(jié)在表6.1中，細(xì)節(jié)如下。讓我們首先

33、考慮I5，它是L中的最后一個項，而不是第一個。其原因隨著我們解釋FP-樹挖掘過程就會清楚。I5出現(xiàn)在圖6.8 的FP-樹的兩個分枝。（I5的出現(xiàn)容易通過沿它的結(jié)點鏈找到。）這些路徑由分枝和形成。這樣，考慮I5為后綴，它的兩個對應(yīng)前綴路徑是和，它們形成I5的條件模式基。它的條件FP-樹只包含單個路徑；不包含I3，因為它的支持度計數(shù)為1，小于最小支持度計數(shù)。該單個路徑產(chǎn)生頻繁模式的所有組合：I2 I5:2, I1 I5:2, I2 I1 I5:2。表6.1 通過創(chuàng)建條件（子）模式基挖掘FP-樹item條件模式基條件FP-樹產(chǎn)生的頻繁模式I5I4I3I1(I2 I1:1), (I2 I1 I3:1)

34、(I2 I1:1), (I2:1)(I2 I1:2), (I2:2), (I1:2)(I2:4), I2 I5:2, I1 I5:2, I2 I1 I5:2I2 I4:2I2 I3:4, I1 I3:4, I2 I1 I3:2I2 I1:4對于I4，它的兩個前綴形成條件模式基(I2 I1:1), (I2:1)，產(chǎn)生一個單結(jié)點的條件FP-樹，并導(dǎo)出一個頻繁模式I2 I4:2。注意，盡管I5跟在第一個分枝中的I4之后，也沒有必要在此分析中包含I5，因為涉及I5的頻繁模式在I5的考察時已經(jīng)分析過。這就是我們?yōu)槭裁从珊竺?，而不是由前面開始處理的原因。與以上分析類似，I3的條件模式基是(I2 I1:2)

35、, (I2:2), (I1:2)。它的條件FP-樹有兩個分枝和，如圖6.9所示，它產(chǎn)生模式集：I2 I3:4, I1 I3:2, I2 I1 I3:2。最后，I1的條件模式基是(I2,4)，它的FP-樹只包含一個結(jié)點，產(chǎn)生一個頻繁模式I2 I1:4。挖掘過程總結(jié)在圖6.10。圖6.9 具有條件結(jié)點I3的條件FP-樹算法：FP-增長。使用FP-樹，通過模式段增長，挖掘頻繁模式。輸入：事務(wù)數(shù)據(jù)庫D；最小支持度閾值min_sup。輸出：頻繁模式的完全集。方法：按以下步驟構(gòu)造FP-樹：掃描事務(wù)數(shù)據(jù)庫D一次。收集頻繁項的集合F和它們的支持度。對F按支持度降序排序，結(jié)果為頻繁項表L。創(chuàng)建FP-樹的根結(jié)點，

36、以“null”標(biāo)記它。對于D中每個事務(wù)Trans，執(zhí)行：選擇Trans中的頻繁項，并按L中的次序排序。設(shè)排序后的頻繁項表為p | P，其中，p是第一個元素，而P是剩余元素的表。調(diào)用insert_tree(p | P, T)。該過程執(zhí)行情況如下。如果T有子女N使得 = ，則N的計數(shù)增加1；否則創(chuàng)建一個新結(jié)點N，將其計數(shù)設(shè)置為1，鏈接到它的父結(jié)點T，并且通過結(jié)點鏈結(jié)構(gòu)將其鏈接到具有相同item-name的結(jié)點。如果P非空，遞歸地調(diào)用insert_tree(P, N)。FP-樹的挖掘通過調(diào)用FP_growth(FP_tree, null)實現(xiàn)。該過程實現(xiàn)如下：procedure FP_growth(

37、Tree, )if Tree 含單個路徑P then for 路徑P中結(jié)點的每個組合（記作）產(chǎn)生模式 ，其支持度support = 中結(jié)點的最小支持度；else for each a i 在Tree的頭部 產(chǎn)生一個模式 = a i ，其支持度support = a i .support；構(gòu)造的條件模式基，然后構(gòu)造的條件FP-樹Tree；if Tree then調(diào)用 FP_growth (Tree, )；圖 不產(chǎn)生候選，發(fā)現(xiàn)頻繁項集的FP-增長算法FP-增長方法將發(fā)現(xiàn)長頻繁模式的問題轉(zhuǎn)換成遞歸地發(fā)現(xiàn)一些短模式，然后與后綴連接。它使用最不頻繁的項作后綴，提供了好的選擇性。該方法大大降低了搜索開銷。

38、當(dāng)數(shù)據(jù)庫很大時，構(gòu)造基于內(nèi)存的FP-樹是不現(xiàn)實的。一種有趣的替換是首先將數(shù)據(jù)庫劃分成投影數(shù)據(jù)庫的集合，然后在每個投影數(shù)據(jù)庫上構(gòu)造FP-樹并挖掘它。該過程可以遞歸地用于投影數(shù)據(jù)庫，如果它的FP-樹還不能放進(jìn)內(nèi)存。對FP-樹方法的性能研究表明：對于挖掘長的和短的頻繁模式，它都是有效的和可規(guī)?；?，并且大約比Apriori算法快一個數(shù)量級。它也比樹-投影算法快。樹-投影算法遞歸地將數(shù)據(jù)庫投影為投影數(shù)據(jù)庫樹。6.2.5 冰山查詢Apriori算法可以用來提高回答冰山查詢的效率。冰山查詢在數(shù)據(jù)挖掘中經(jīng)常用，特別是對購物籃分析。冰山查詢在一個屬性或?qū)傩约嫌嬎阋粋€聚集函數(shù)，以找出大于某個指定閾值的聚集值。

39、給定關(guān)系R，它具有屬性a_1, a_2, . , a_n和b，一個聚集函數(shù)agg_f，冰山查詢形如select from group byhaving R.a_1, R.a_2, . ,R.a_n, agg_f(R.b)relation Ragg_f(R.b) = threshold給定大量輸入數(shù)據(jù)元組，滿足having子句中的閾值的輸出元組數(shù)量相對很少。輸出結(jié)果看作“冰山頂”，而“冰山”是輸入數(shù)據(jù)集。 一個冰山查詢：假定給定銷售數(shù)據(jù)，你想產(chǎn)生這樣的一個顧客-商品對的列表，這些顧客購買商品的數(shù)量達(dá)到3件或更多。這可以用下面的冰山查詢表示selectfromgroup byhavingP.cus

40、t_ID, P.Item_ID,SUM(P.qty)Purchases PP.cust_ID, Pitem_IDSUM(P.qty) =3 “如何回答例6.4的查詢？”你可能會問。一個常用的策略是使用散列或排序，對所有顧客-商品分組，計算聚集函數(shù)SUM的值，然后刪除被給定的顧客購買的商品數(shù)量少于3的那些。相對于處理的元組總數(shù)，滿足該條件的元組多半很少，為改進(jìn)性能留下了空間。我們可以使用Apriori性質(zhì)的變形，裁減需要考慮的顧客-商品對。即，不是考查每個顧客購買的每種商品的數(shù)量，我們可以產(chǎn)生cust_list，一個總共購買3件或更多商品的顧客表。例如selectfromgroup byhavi

41、ngPurchases PSUM(P.qty) = 3產(chǎn)生item_list，被顧客購買的、數(shù)量為3或更多的商品表。例如selectfromgroup byhavingP. item_IDPurchases PSUM(P.qty) = 3由先驗知識，我們可以刪除許多被散列/排序方法產(chǎn)生的顧客-商品對：僅對cust_list中的顧客和在item_list中的商品產(chǎn)生候選顧客-商品對。對每個這樣的對，維持一個計數(shù)。盡管該方法通過預(yù)先裁減許多對或分組提高了性能，所產(chǎn)生的顧客-商品對數(shù)量可能依然很大，不能放進(jìn)內(nèi)存。可以將散列和選樣策略集成到該過程，幫助提高該查詢回答技術(shù)的總體性能。6.3 由事務(wù)數(shù)據(jù)庫

42、挖掘多層關(guān)聯(lián)規(guī)則本節(jié)，你將學(xué)習(xí)挖掘多層關(guān)聯(lián)規(guī)則的方法。多層關(guān)聯(lián)規(guī)則是這樣一些規(guī)則，它們涉及多個抽象層中的項。本節(jié)還討論檢查冗余多層規(guī)則的方法。6.3.1 多層關(guān)聯(lián)規(guī)則對于許多應(yīng)用，由于多維數(shù)據(jù)空間數(shù)據(jù)的稀疏性，在低層或原始層的數(shù)據(jù)項之間很難找出強(qiáng)關(guān)聯(lián)規(guī)則。在較高的概念層發(fā)現(xiàn)的強(qiáng)關(guān)聯(lián)規(guī)則可能提供普遍意義的知識。然而，對一個用戶代表普遍意義的知識，對另一個用戶可能是新穎的。這樣，數(shù)據(jù)挖掘系統(tǒng)應(yīng)當(dāng)提供一種能力，在多個抽象層挖掘關(guān)聯(lián)規(guī)則，并容易在不同的抽象空間轉(zhuǎn)換。讓我們考察下面的例子。 假定給定表6.2事務(wù)數(shù)據(jù)的任務(wù)相關(guān)數(shù)據(jù)集，它是AllElectronics分店的計算機(jī)部的銷售數(shù)據(jù)，對每個事務(wù)TI

43、D給出了購買的商品。商品的概念分層在圖6.11給出。概念分層定義了由低層概念到高層更一般的概念的映射序列?？梢酝ㄟ^將數(shù)據(jù)內(nèi)的低層概念用概念分層中的其高層概念（祖先）替換，對數(shù)據(jù)進(jìn)行泛化 概念分層已在第2、4章詳細(xì)介紹。為了使得本書的沒章盡可能自包含，我們在此再次給出它的定義。泛化在第5章已介紹。圖6.11的概念分層有4層，記作0, 1, 2和3層。為方便計，概念分層中的層自頂向下編號，根結(jié)點all（最一般的抽象概念）為第0層。因此，第1層包括computer, software, printer和computer accessory，第2層包括desktop computer, laptop

44、computer, education software, financial management software, .，而第3層包括IBM desktop computer,., Microsoft education software，等等。第3層是該分層結(jié)構(gòu)的最特定的抽象層。概念分層可以由熟悉數(shù)據(jù)的用戶指定，也可以在數(shù)據(jù)中蘊涵存在。表 任務(wù)相關(guān)數(shù)據(jù)DTID購買的商品T1T2T3T4T5.IBM desktop computer, Sony b/w printerMicrosoft educationsoftware, Microsoft finacial management sof

45、twareLogitech mouse computer accessory, Ergo-way wrist pad computer accessoryIBM desktop computer, Microsoft finacial management software IBM desktop computer.圖 AllElectronics計算機(jī)商品的概念分層表中的項在圖概念分層的最低層。在這種原始層很難找出有趣的購買模式。例如，如果“IBM desktop computer”和“Sony b/w (黑白) printer”每個都在很少一部分事務(wù)中出現(xiàn)，則可能很難找到涉及它們的強(qiáng)關(guān)聯(lián)規(guī)

46、則。很少人同時購買它們，使得“ IBM desktop computer, Sony b/w printer ”不太可能滿足最小支持度。然而，考慮將“Sony b/w printer”泛化到“b/w printer”。在“IBM desktop computer”和“b/w printer”之間比在“IBM desktop computer”和“Sony b/w printer” 可望更容易發(fā)現(xiàn)強(qiáng)關(guān)聯(lián)。類似地，許多人同時購買“computer”和“printer”，而不是同時購買特定的“IBM desktop computer”和“Sony b/w printer”。換句話說，包含更一般項的項

47、集，如“ IBM desktop computer, b/w printer ”和“ computer, printer ”，比僅包含原始層數(shù)據(jù)的項集，如“ IBM desktop computer, Sony b/w printer ”，更可能滿足最小支持度。因此，在多個概念層的項之間找有趣的關(guān)聯(lián)比僅在原始層數(shù)據(jù)之間更容易找。由具有概念分層的關(guān)聯(lián)規(guī)則挖掘產(chǎn)生的規(guī)則稱為多層關(guān)聯(lián)規(guī)則，因為它們考慮多個概念層。6.3.2 挖掘多層關(guān)聯(lián)規(guī)則的方法“我們?nèi)绾问褂酶拍罘謱佑行У赝诰蚨鄬雨P(guān)聯(lián)規(guī)則？”讓我們看一些基于支持度-置信度框架的方法。一般地，可以采用自頂向下策略，由概念層1開始向下，到較低的更特定的

48、概念層，在每個概念層累加計數(shù)計算頻繁項集，直到不能再找到頻繁項集。即，一旦找出概念層1的所有頻繁項集，就開始在第2層找頻繁項集，如此下去。對于每一層，可以使用發(fā)現(xiàn)頻繁項集的任何算法，如Apriori或它的變形。這種方法有許多變形，介紹如下，并用圖6.12到圖6.16解釋。圖中矩形指出項或項集已被考察，而粗邊框的矩形指出已考察的項或項集是頻繁的。對于所有層使用一致的支持度（稱作一致支持度）：在每一層挖掘時，使用相同的最小支持度閾值。例如，在圖6.12中，整個使用最小支持度閾值5%（例如，對于由“computer”到“l(fā)aptop computer”）?！?computer”和“l(fā)aptop co

49、mputer”都是頻繁的，但“desktop computer”不是。圖6.12 具有一致支持度的多層挖掘使用一致的最小支持度閾值時，搜索過程是簡單的，并且用戶也只需要指定一個最小支持度閾值。根據(jù)祖先是其后代的超集的知識，可以采用優(yōu)化策略：搜索時避免考察這樣的項集，它包含其祖先不具有最小支持度的項。然而，一致支持度方法有一些困難。較低層次抽象的項不大可能象較高層次抽象的項出現(xiàn)得那么頻繁。如果最小支持度閾值設(shè)置太高，可能丟掉出現(xiàn)在較低抽象層中有意義的關(guān)聯(lián)規(guī)則。如果閾值設(shè)置太低，可能會產(chǎn)生出現(xiàn)在較高抽象層的無興趣的關(guān)聯(lián)規(guī)則。這導(dǎo)致了下面的方法。在較低層使用遞減的支持度（稱作遞減支持度）：每個抽象層

50、有它自己的最小支持度閾值。抽象層越低，對應(yīng)的閾值越小。例如，在圖6.13，層1和層2的最小支持度閾值分別為5%和3%。用這種方法，“computer”、“l(fā)aptop computer”和“desktop computer”都是頻繁的。圖6.13 具有遞減支持度的多層挖掘?qū)τ诰哂羞f減支持度的多層關(guān)聯(lián)規(guī)則挖掘，有許多可用的搜索策略，包括：逐層獨立：這是完全的寬度搜索，沒有頻繁項集的背景知識用于剪枝?？疾烀恳粋€結(jié)點，不管它的父結(jié)點是否是頻繁的。層交叉用單項過濾：一個第i層的項被考察，當(dāng)且僅當(dāng)它在第(i-1)層的父結(jié)點是頻繁的。換一句話說，我們由較一般的關(guān)聯(lián)考察更特定的關(guān)聯(lián)。如果一個結(jié)點是頻繁的，它

51、的子女將被考察；否則，它的子孫將由搜索中剪枝。例如，在圖中，“computer”的后代結(jié)點（即，“l(fā)aptop computer”和“desktop computer”）將不被考察，因為“computer”不是頻繁的。圖6.14 具有遞減支持度的多層挖掘，使用層交叉用單項過濾層交叉用k-項集過濾：一個第i層的k-項集被考察，當(dāng)且僅當(dāng)它在第(i-1)層的對應(yīng)父結(jié)點k-項集是頻繁的。例如，在圖6.15中，2-項集“computer, printer”是頻繁的，因而結(jié)點“l(fā)aptop computer, b/w printer”、“ laptop computer, color printer”、“

52、 desktop computer, b/w printer”和“desktop computer, color printer”被考察。圖6.15 具有遞減支持度的多層挖掘，使用層交叉用k-項集過濾，其中k=2“如何比較這些方法？”逐層獨立策略的條件很松，可能導(dǎo)致在低層考察大量非頻繁的項，找出一些不太重要的關(guān)聯(lián)。例如，如果“computer furniture”很少購買，考察特定的“computer chair”是否與“l(fā)aptop computer”關(guān)聯(lián)沒什么意思。然而，如果“computer accessories”經(jīng)常出售，考察“l(fā)aptop”與“mouse”之間是否存在關(guān)聯(lián)購買模式可

53、能是有意義的。層交叉用k-項集過濾策略允許系統(tǒng)僅考察頻繁k-項集的子女。這一限制可能太強(qiáng)，通常沒有多少k-項集組合后仍是頻繁的（特別是當(dāng)k 2時）。因此，有些有價值的模式可能被該方法過濾掉。層交叉用單項過濾策略是上兩個極端的折衷。然而，這種方法也可能丟失低層項之間的關(guān)聯(lián)；根據(jù)遞減的最小支持度，這些項是頻繁的，但它們的祖先不滿足最小支持度（由于每層的支持度閾值可能不同）。例如，如果根據(jù)第i層的最小支持度閾值，“color monitor”在第i層是頻繁的，但是它在(i-1)層的父結(jié)點“monitor”，根據(jù)第(i-1)層的最小支持度閾值，不是頻繁的，則頻繁的關(guān)聯(lián)“desktop computer

54、 color monitor”將丟失。層交叉單項過濾策略有一個修改版本，稱作受控的層交叉單項過濾策略?？梢栽O(shè)置一個稱作層傳遞閾值的閾值，用于向較低層“傳遞”相對頻繁的項（稱作子頻繁項）。換句話說，如果滿足層傳遞閾值，則該方法允許考查不滿足最小支持度閾值項的子女。每個概念層可以有它自己的層傳遞閾值。通常，對于一個給定層，層傳遞閾值設(shè)置為下一層的最小支持度閾值和給定層的最小支持度閾值之間的一個值。用戶可以在較高層選擇“下滑”或降低層傳遞閾值，使得子頻繁項的后代在較低層被考察。降低層傳遞閾值到最低層的最小支持度閾值將使得項的所有后代被考察。例如，在圖6.16中，設(shè)置層1的層傳遞閾值(level_pa

55、ssage_sup)為8%，使得第2層的“l(fā)aptop computer”和“desktop computer”被考察，并發(fā)現(xiàn)是頻繁的，盡管它們的父結(jié)點“computer”不是頻繁的。通過增加這種機(jī)制，用戶對進(jìn)一步控制多概念層上的挖掘過程有了更多的靈活性，同時減少無意義關(guān)聯(lián)的考察和產(chǎn)生。圖6.16 多層挖掘，受控的層交叉單項過濾迄今為止，我們的討論集中在發(fā)現(xiàn)這樣的頻繁項集，它的所有項都屬于同一概念層。這可能導(dǎo)致形如“computer printer”（其中，”computer”和”printer”都在概念層1）和“desktop computer b/w printer”（其中，”deskto

56、p computer”和”b/w printer”都在給定概念層的第2層）的規(guī)則。假定我們想要發(fā)現(xiàn)跨越概念層邊界的規(guī)則，如“computer b/w printer”，規(guī)則中的項不要求屬于同一概念層。這些規(guī)則稱作交叉層關(guān)聯(lián)規(guī)則?！叭绾瓮诰蚪徊鎸雨P(guān)聯(lián)規(guī)則？”如果挖掘由層i到層j的關(guān)聯(lián)，其中層j比層i更特定（即，在較低的抽象層），則應(yīng)當(dāng)使用層j的最小支持度閾值，使得層j的項可以包含在分析中。6.3.3 檢查冗余的多層關(guān)聯(lián)規(guī)則概念分層在數(shù)據(jù)挖掘中是有用的，因為它們允許不同的抽象層的知識發(fā)現(xiàn)，如多層關(guān)聯(lián)規(guī)則。然而，當(dāng)挖掘多層關(guān)聯(lián)規(guī)則時，由于項之間的“祖先”關(guān)系，有些發(fā)現(xiàn)的規(guī)則將是冗余的。例如，考慮下面

57、的規(guī)則，其中，根據(jù)圖的概念分層，”desktop computer”是”IBM desktop computer”的祖先。desktop computer b/w printer, support=8%, confidence=70% (6.9)IBM desktop computer b/w printer, support=2%, confidence=72% (6.10)“如果挖掘出規(guī)則和，那么后一個規(guī)則是有用的嗎？”你可能懷疑“它真的提供新穎的信息嗎？”如果后一個具有較小一般性的規(guī)則不提供新的信息，應(yīng)當(dāng)刪除它。讓我們看看如何來確定。規(guī)則R1是規(guī)則R2的祖先，如果將R2中的項用它在概念分

58、層中的祖先替換，能夠得到R1。例如，規(guī)則(6.9)是規(guī)則(6.10)的祖先，因為” desktop computer”是”IBM desktop computer”的祖先。根據(jù)這個定義，一個規(guī)則被認(rèn)為是冗余的，如果根據(jù)規(guī)則的祖先，它的支持度和置信度都接近于“期望”值。作為解釋，假定規(guī)則(6.9)具有70%置信度，8%支持度，并且大約四分之一的”desktop computer”銷售是”IBM desktop computer”。可以期望規(guī)則(6.10)具有大約70%的置信度（由于所有的”IBM desktop computer”樣本也是” desktop computer”樣本）和2%（即，8

59、%1/4）的支持度。如果確實是這種情況，規(guī)則(6.10)不是有趣的，因為它不提供附加的信息，并且它的一般性不如規(guī)則(6.9)。6.4 由數(shù)據(jù)庫和數(shù)據(jù)倉庫挖掘多維關(guān)聯(lián)規(guī)則本節(jié)，你將學(xué)習(xí)挖掘多維關(guān)聯(lián)規(guī)則的方法。多維關(guān)聯(lián)規(guī)則是涉及多個屬性或謂詞的規(guī)則（例如，關(guān)于顧客的buys和顧客的age的規(guī)則）。這些方法可以根據(jù)他們對量化屬性的處理組織。6.4.1 多維關(guān)聯(lián)規(guī)則到本章這里，我們研究了蘊涵單個謂詞，即謂詞buys的關(guān)聯(lián)規(guī)則。例如，在挖掘AllElectronics數(shù)據(jù)庫時，我們可能發(fā)現(xiàn)布爾關(guān)聯(lián)規(guī)則“IBM desktop computer Sony b/w printer”，它也可以寫成buys(X

60、,”IBM desktop computer”) buys(X,”Sony b/w printer”) (6.11)其中，X是變量，代表在AllElectronics購物的顧客。沿用多維數(shù)據(jù)庫使用的術(shù)語，我們把每個不同的謂詞稱作維。這樣，我們稱規(guī)則(6.11)為單維或維內(nèi)關(guān)聯(lián)規(guī)則，因為它們包含單個不同謂詞（即，buys）的多次出現(xiàn)（即，謂詞在規(guī)則中出現(xiàn)多次）。正如我們在本章的前幾節(jié)看到的，這種規(guī)則通常由事務(wù)數(shù)據(jù)挖掘。然而，假定不是使用事務(wù)數(shù)據(jù)庫，銷售和相關(guān)數(shù)據(jù)存放在關(guān)系數(shù)據(jù)庫或數(shù)據(jù)倉庫中。根據(jù)定義，這種存儲是多維的。例如，除記錄購買的商品之外，關(guān)系數(shù)據(jù)庫可能記錄與商品有關(guān)的其它屬性，如購買數(shù)量