《數(shù)據挖掘基礎及其應用》課件第7章

第7章關聯(lián)規(guī)則Ⅰ:頻繁模式挖掘7.1引言7.2基本概念7.3頻繁項集挖掘7.4頻繁模式樹算法本章小結

7.1引言

關聯(lián)規(guī)則最初是針對購物籃分析(MarketBasketAnalysis)問題提出的。在店鋪中,分店經理想更多地了解顧客的購物習慣,特別是哪些商品容易被顧客同時購買。為回答該問題,需要對商店的事物零售數(shù)量進行購物籃分析。該過程通過挖掘顧客放入“購物籃”中的不同商品之間的關聯(lián),分析顧客的購物習慣,幫助零售商了解哪些商品頻繁地被顧客同時購買,從而輔助他們開發(fā)更好的營銷策略,如圖7-1所示。圖7-1購物籃行為分析

在描述有關關聯(lián)規(guī)則的一些細節(jié)之前,先來看一個有趣的“尿布與啤酒”的故事。在一家超市里,有一個有趣的現(xiàn)象:尿布和啤酒赫然擺在一起出售,但是這個奇怪的舉措卻使

尿布和啤酒的銷量雙雙增加了。這個故事一直為商家所津津樂道。實際上這不是一個單純的故事,而是一個真實發(fā)生的事件,主角是大名鼎鼎的沃爾瑪。沃爾瑪擁有世界上最大的

數(shù)據倉庫系統(tǒng),為了能夠準確了解顧客在其門店的購買習慣,沃爾瑪對其顧客的購物行為進行了購物籃分析,想知道顧客經常一起購買的商品有哪些。

沃爾瑪數(shù)據倉庫里集中了其各門店的詳細原始交易數(shù)據。在這些原始交易數(shù)據的基礎上,沃爾瑪利用數(shù)據挖掘技術對數(shù)據進行分析和挖掘。一個意外的發(fā)現(xiàn)是:跟尿布一起購買最多的商品竟是啤酒!經過大量的調查和分析,科學家們揭示了一個隱藏在“尿布與啤酒”背后的美國人的一種行為模式:在美國,一些年輕的父親下班后經常要到超市去買嬰兒尿布,而他們中有30%~40%的人同時也為自己買一些啤酒,如圖7-2所示。圖7-2交易數(shù)據與關聯(lián)規(guī)則

同時,一些知名的電子商務站點也從強關聯(lián)規(guī)則的挖掘中受益。這些電子購物網站對關聯(lián)規(guī)則進行挖掘,然后設置用戶有意要一起購買的捆綁包。也有一些購物網站使用它們

設置相應的交叉銷售,即購買某種商品的顧客會看到相關的另一種商品的廣告。

在我國,“數(shù)據海量,信息缺乏”是商業(yè)銀行在數(shù)據大集中之后普遍所面臨的尷尬狀況。金融業(yè)實施的大多數(shù)數(shù)據庫只能實現(xiàn)數(shù)據的錄入、查詢、統(tǒng)計等較低層次的功能,卻無法發(fā)現(xiàn)數(shù)據中存在的各種有用信息。關聯(lián)規(guī)則挖掘技術在我國的研究與應用并不是很深入。

7.2基本概念

關聯(lián)(Associations)分析的目的是挖掘隱藏在數(shù)據間的相互關系,即對于給定的一組項目和一個記錄集,通過對記錄集的分析,得出項目集中項目之間的相關性。項目之間的相關性用關聯(lián)規(guī)則來描述,關聯(lián)規(guī)則反映了一組數(shù)據項之間的密切程度或關系。相關定義如下:

定義7.9(強關聯(lián)規(guī)則)給定項集I={I1,I2,…,In},D={T1,T2,…,Td}是全體事務數(shù)據集,規(guī)則X→Y是關聯(lián)規(guī)則,當且僅當如下兩個條件得到滿足時X→Y是強關聯(lián)規(guī)則:

(1)規(guī)則支持度大于事先設定的閾值,即s(X→Y)≥minsup;

(2)規(guī)則置信度大于事先設定的閾值,即c(X→Y)≥minsup。

根據關聯(lián)規(guī)則的定義,關聯(lián)規(guī)則與頻繁項集的關系是:頻繁項集是關聯(lián)規(guī)則的前提。因此,關聯(lián)規(guī)則的挖掘主要被分解為下面兩步:

第一步,頻繁項集提取。找出所有的頻繁項集,即找出支持度大于或等于給定的最小支持度閾值的所有項集?？梢詮?~k遞歸查找k-頻繁項集。

第二步,關聯(lián)規(guī)則提取,即找出滿足最小支持度和最小置信度的關聯(lián)規(guī)則。對給定的L,如果其非空子集A?L,sup(L)為L的支持度,sup(A)為A的支持度,則產生形式為A→L-A的規(guī)則。

7.3頻繁項集挖掘

給定總項集I={I1,I2,…,In},要挖掘出所有的頻繁模式涉及兩大關鍵步驟:(1)創(chuàng)建所有的候選項集。(2)判斷一個候選項集是否是頻繁項集。最常用的方法有枚舉法(暴力破解)、剪枝算法(Apriori算法)、Apriori加速算法、FP算法等。

7.3.1暴力破解方法

暴力破解是最常用的方法,可以利用樹狀結構枚舉所有的候選項集,創(chuàng)建完候選項集樹之后,依次判斷每個候選項集是否滿足頻繁項集的要求。給定交易數(shù)據項集I={a,b,c,d,e},暴力破解算法枚舉所有子集合,如圖7-3所示。圖7-3暴力破解示例

其特點是:

①共k+1層;

②第一層是空集;

③第k層都是(k-1)-項集;

④每層只與上一層和下一層有關系。

暴力破解算法的優(yōu)點是:簡單、易懂;

暴力破解算法的缺點是:時間復雜度極高,為指數(shù)級(M=2d),其結構如圖7-3所示。基于暴力破解算法的頻繁模式挖掘如圖7-4所示。圖7-4基于暴力破解算法的頻繁模式挖掘

7.3.2Apriori算法

Apriori算法是一種挖掘關聯(lián)規(guī)則的頻繁項集算法,它開創(chuàng)性地使用基于支持度的剪枝技術,系統(tǒng)地控制候選項集指數(shù)增長。Apriori利用如下兩個基本性質:①頻繁項集的所

有非空子集都是頻繁的。如果項集I不滿足最小支持度閾值minsup,則I不是頻繁的,即sup(I)<minsup。②如果將項集A添加到I,則結果項集(I∪A)不可能比I更頻繁出現(xiàn)。因此,I∪A也不是頻繁的,sup(I∪A)<minsup,即存在反單調模式:

基于頻繁項集的反單調性,Apriori算法的核心思想總結如下:

頻繁項集的Apriori性質用于壓縮搜索空間(剪枝),以提高逐層產生頻繁項集的效率,如圖7-5所示。其中2-項集{AB}是非頻繁的,則以{AB}為子集的所有超集都是非頻繁的,包括{ABC}、{ABD}、{ABE}、{ABCD}、{ABCE}、{ABDE}、{ABCDE}。為了避免無效計算,可以對以{AB}為根節(jié)點的子樹進行剪枝操作,如圖7-5所示虛線所包圍的項集集合(子樹)圖7-5Apriori算法剪枝示意圖(虛線所包圍部分為剪枝部分)

以圖7-4中的數(shù)據為例,Apriori算法的計算過程如圖7-6所示。圖7-6Apriori算法的計算過程

具體描述如下

(1)初始通過單邊掃描數(shù)據集,確定每個項集的支持度,并得到所有頻繁1-項集的集合F1(步驟1和2)。

(2)之后使用上一次迭代產生的頻繁(k-1)-項集,產生新的候選k-項集(步驟5),其中apriori-gen函數(shù)將在下節(jié)進行細節(jié)介紹。

(3)再次掃描數(shù)據集獲得候選項集的支持度計數(shù)(步驟6~10),使用subset函數(shù)確定包含在每一個事物t中的Ck中的所有候選k-項集。subset函數(shù)的實現(xiàn)在后文中會介紹。

(4)刪去支持度計數(shù)小于minsup的所有候選項集(步驟12)。

(5)當沒有新的頻繁項集產生,即Fk=?時,算法結束(步驟13)。

Apriori算法是在早期成功處理頻繁項集產生的組合爆炸問題的算法之一,它通過使用先驗原理對指數(shù)搜索空間進行剪枝,成功地處理了組合爆炸問題。盡管顯著地提高了挖掘關聯(lián)關系的性能,但是該算法還是會導致不可低估的I/O開銷,因為它需要多次掃描事務數(shù)據集。此外,對于稠密數(shù)據集,由于事務數(shù)據寬度的增加,Apriori算法的性能會顯著降低。為了克服這些局限性和提高Apriori算法的效率,人們開發(fā)了一些替代方法。下面是這些方法的簡略描述。

1)項集格遍歷

概念上,可以把頻繁項集的搜索看作遍歷圖7-5中的項集格。算法使用的搜索策略指明了頻繁項集產生過程中是如何遍歷格結構的。根據頻繁項集在格中的布局,某些搜索策略優(yōu)于其他策略。這些策略包括:

(1)一般到特殊與特殊到一般。Apriori算法使用了“一般到特殊”的搜索策略,合并兩個頻繁(k-1)-項集得到候選k-項集。只要頻繁項集的最大長度不是太長,這種“一般到特

殊”的搜索策略是有效的。

圖7-7(a)中顯示使用這種策略效果最好的頻繁項集的分布,其中黑色的節(jié)點代表非頻繁項集。相反,“特殊到一般”的搜索策略在發(fā)現(xiàn)更一般的頻繁項集之前,先尋找更特殊的頻繁項集。這種策略對于發(fā)現(xiàn)稠密事務中的極大頻繁項集是有用的。稠密事務中頻繁項集的邊界靠近格的底部,如圖7-7(b)所示。可以使用先驗原理剪掉極大頻繁項集的所有子集。具體來說,如果候選k-項集是極大頻繁項集,則不必考察它的

任意k-1項子集。然而,如果候選k-項集是非頻繁的,則必須在下一迭代考察它所有的k-1項子集。另外一種策略是結合“一般到特殊”和“特殊到一般”的搜索策略,盡管這種雙

向搜索方法需要更多的空間存儲候選項集,但是對于圖7-7(c)所示的布局,該方法有助于加快確定頻繁項集邊界。圖7-7-一般到特殊、特殊到一般和雙向搜索

(2)等價類。另外一種遍歷的方法是先將格劃分為兩個不相交的節(jié)點組(或等價類),頻繁項集產生算法依次在每個等價類內搜索頻繁項集。例如,Apriori算法采用的逐層策略可以看作根據項集的大小劃分格,即在處理較大項集之前,首先找出所有的頻繁1-項集。等價類也可以根據項集的前綴或后綴來定義。在這種情況下,如果它們共享長度為K的相同前綴或后綴,則兩個項集屬于同一個等價類。在基于前綴的方法中,算法首先搜索以前綴a開始的頻繁項集,然后是以前綴b開始的頻繁項集,然后是c,如此下去?；谇熬Y和基于后綴的等價類都可以使用圖7-8所示的類似于樹的結構來演示。圖7-8基于項集前綴和后綴的等價類

(3)寬度優(yōu)先與深度優(yōu)先。Apriori算法采用寬度優(yōu)先的方法遍歷格,如圖7-9(a)所示。它首先發(fā)現(xiàn)所有的頻繁1-項集,接下來是頻繁2-項集,如此下去直到沒有新的頻繁項集產生為止。也可以以深度優(yōu)先的方式遍歷項集格,如圖7-9(b)和圖7-10所示。例如,算法可以從圖中的節(jié)點a開始,計算其支持度計數(shù)并判斷它是否頻繁。如果是,則算法漸增地擴展下層節(jié)點,即ab、abc等,直到到達一個非頻繁節(jié)點,如abcd。然后回溯到下一個分支,如abce,并且繼續(xù)搜索。圖7-9寬度優(yōu)先和深度優(yōu)先遍歷

通常,深度優(yōu)先搜索方法用于發(fā)現(xiàn)極大頻繁項集的算法。與寬度優(yōu)先方法相比,這種方法可以更快地檢測到頻繁項集邊界。一旦發(fā)現(xiàn)一個極大頻繁項集,就可以在它的子集上進行剪枝。例如,如果圖7-10中的節(jié)點bcde是極大頻繁項集,則算法就不必訪問以bd、be、c、d和e為根的子樹,因為它們不可能包含任何極大頻繁項集。然而,如果abc是極大頻繁項集,則只有ae和be這樣的節(jié)點不是極大頻繁項集,但以它們?yōu)楦淖訕溥€可能包含極大頻繁項集。深度優(yōu)先方法還允許使用不同的基于項集支持度的剪枝方法。例如,假定項集{a,b,c}和{a,b}具有相同的支持度,則可以跳過以abd和abe為根的子樹,因為可以確保它們不包含任何極大頻繁項集。圖7-10使用深度優(yōu)先的方法產生的候選項集

2)事務數(shù)據集的表示

事務數(shù)據集的表示方法有多種。表示方法的選擇可能影響計算候選項集支持度的I/O開銷。圖7-11顯示了兩種表示購物籃事務的不同方法。圖7-11(a)的表示法稱作水平數(shù)據布局,許多關聯(lián)規(guī)則挖掘算法(包括Apriori)都采用這種表示法;另一種可能的方法是存儲與每一個項集相關聯(lián)的事務標識符(TransactionIdentifer,TID),這種表示法稱作垂直(Vertical)數(shù)據布局。圖7-11水平與垂直數(shù)據形式

假設有15個3-項集:{145},{124},{457},{125},{458},{159},{136},{234},

{567},{345},{356},{357},{689},{367},{368},那么如何構建Hash函數(shù),可以有效地存儲15個3-項集?如圖7-12所示,可以構建Hash函數(shù)取模3操作(具體過程參看數(shù)據結構部分,Hash函數(shù)與Hash樹),構建Hash樹的基本思想是:將事務中每個項前綴的項集構建出來,采用遞歸的方式創(chuàng)建所有的項集。圖7-12Hash樹的構建

7.3.3加速技術

1.二次加速技術

Apriori算法通過反單調性質對候選項集進行剪枝操作,這在很大程度上降低了時間復雜性,在挖掘頻繁項集時每個候選項集都需要對數(shù)據庫進行掃描操作,能否通過其他方式加速這一過程?人們發(fā)現(xiàn)可采用哈希樹(Hash樹)的方式來降低時間復雜性。

構建Hash樹的前提是需要知道所有的k-項集,給定一個事務,通過枚舉的方式構建所有的k-項集,如圖7-13所示。圖7-13Hash樹構建

2.其他加速技術

Apriori算法需要重復地掃描數(shù)據庫,通過模式匹配方法對一個大的候選集合進行篩。為了提高Apriori算法的效率,目前已產生了許多Apriori算法的變形:

(1)散列技術:用于壓縮候選k-項集Ck。

(2)基于事務壓縮方法:目標是減少用于未來掃描的事務集的大小。

(3)基于劃分方法:Savasere設計了一個基于劃分(Partition)的算法,這個算法先把數(shù)據庫從邏輯上分成幾個互不相交的塊,每次單獨考慮一個分塊并對它生成所有的頻繁項集;然后把產生的頻繁項集合并,用來生成所有可能的頻繁項集;最后計算這些頻繁項集的支持度。

(4)基于采樣方法:采樣是發(fā)現(xiàn)規(guī)則的一個有效途徑。

(5)動態(tài)項集計數(shù):將給定事務集D劃分為標記開始點的塊,可以在任何開始點添加新的候選項集。

Apriori算法的缺點:

(1)在每一步產生候選項集時,循環(huán)產生的組合過多,沒有排除不應該參與組合的元素;

(2)每次計算項集的支持度時,對數(shù)據庫中的全部記錄進行了一次掃描比較,因此需要很大的I/O負載;

(3)當數(shù)據量過大時,需要采取頁面調入與調出算法,極其費時。

7.4頻繁模式樹算法

7.4.1FP樹表示法FP(FrequentPattern)樹是一種輸入數(shù)據的壓縮表示,它通過逐個讀入事務,并把每個事務映射到FP樹中的一條路徑來構造。由于不同的事務可能會有若干個相同的項,因此它們的路徑可能部分重疊。路徑相互重疊得越多,使用FP樹結構獲得的壓縮效果越好。如果FP樹足夠小,能夠存放在內存中,則可以直接從這個內存的結構中提取頻繁項集,而不必重復地掃描存放在硬盤上的數(shù)據。

圖7-14顯示了一個數(shù)據集,它包含10個事務和5個項。

隨后,用如下方法擴充FP樹:

(1)掃描一次數(shù)據集,確定每個項的支持度計數(shù)。

(2)第二次掃描數(shù)據集,構建FP樹。

(3)讀入第二個事務{b,c,d}后,為項b、c和d創(chuàng)建新的節(jié)點集,然后連接節(jié)點null→a→b,形成一條代表該事務的路徑。

(4)第三個事務{a,c,d,e}與第一個事務共享一個共同前綴項a,所以第三個事務的路徑null→a→c→d→e與第一個事務的路徑null→a→b部分重疊。

5)繼續(xù)該過程,直到每個事務都映射到FP樹的一條路徑。圖7-14構建FP樹

FP樹的大小也取決于項的排序方式。如果顛倒前面例子中的序,即項按照支持度由小到大排列,則FP樹表示如圖7-15所示。圖7-15支持度遞增順序方案的FP樹表示

7.4.2FP算法的頻繁項集的產生

FP增長是一種以自底向上方式探索樹,由FP樹產生頻繁項集的算法。給定圖7-14所示的樹,FP算法首先查找以e結尾的頻繁項集,接下來依次是d、c、b,最后是a。這種用于發(fā)現(xiàn)以某一個特定項結尾的頻繁項集的自底向上的策略等價于基于后綴的方法。由于每一個事務都映射到FP樹中的一條路徑,因而通過僅考察包含特定節(jié)點(如e)的路徑,就可以發(fā)現(xiàn)以e結尾的頻繁項集。使用與節(jié)點e相關聯(lián)的指針,可以快速訪問這些路徑,圖7-16(a)顯示了所提取的路徑。稍后詳細解釋如何處理這些路徑,以得到頻繁項集。圖7-16將項集分解為子問題

發(fā)現(xiàn)以e結尾的頻繁項集之后,FP算法通過處理與節(jié)點d相關聯(lián)的路徑,進一步尋找以d結尾的頻繁項集。圖7-16(b)顯示了對應的路徑。繼續(xù)該過程,直到處理了所有與節(jié)點c、b和a相關聯(lián)的路徑為止。圖7-16(c)、圖7-16(d)、圖7-16(e)分別顯示了這些項的路徑,而它們對應的頻繁項集匯總在表7-1中。

為了更具體地說明如何解決這些子問題,考慮發(fā)現(xiàn)所有以e結尾的頻繁項集的任務。

具體如下:

(1)收集包含e節(jié)點的所有路徑,這些初始的路徑稱為前綴路徑,如圖7-17(a)所示。

(2)由圖7-17(a)中所顯示的前綴路徑,通過把與節(jié)點e相關聯(lián)的支持度計數(shù)相加得到e的支持度計數(shù)。假定最小支持度為2,因為{e}的支持度是3,所以它是頻繁項集。１圖7-17-使用FP增長算法發(fā)現(xiàn)以e為結尾的頻繁項集的例子

(3)由于{e}是頻繁的,因此算法必須解決發(fā)現(xiàn)以de、ce、be和ae結尾的頻繁項集的子