關聯(lián)規(guī)則挖掘以改進樸素貝葉斯*

俞　杰　丁曉劍　崔　鵬

(信息系統(tǒng)工程重點實驗室　南京　210007)

?

關聯(lián)規(guī)則挖掘以改進樸素貝葉斯*

俞杰丁曉劍崔鵬

(信息系統(tǒng)工程重點實驗室南京210007)

摘要樸素貝葉斯算法是建立在條件獨立性假設上的，但是在實際應用中，類屬性條件獨立假設并不成立。針對這個問題，結合關聯(lián)規(guī)則方法構造一個改進的樸素貝葉斯分類器。通過挖掘感興趣的和頻繁的項目集，深入研究樣本算法中的屬性聯(lián)系。使隨后運用樸素貝葉斯方法的各個屬性盡量屬性獨立,達到樸素貝葉斯分類器的要求。實例標簽方法改善了樸素貝葉斯的分類性能。

關鍵詞樸素貝葉斯; 條件獨立性假設; 項目集

Class NumberTP311

1引言

數(shù)據(jù)挖掘是從大量數(shù)據(jù)中提取出可信、新穎、有效并能被人理解的模式的高級處理過程。它與數(shù)據(jù)庫中的知識發(fā)現(xiàn)(Knowledge Discover Database,KDD)有著緊密的關系,而KDD 是一個多步驟的處理過程,一般分為問題定義、數(shù)據(jù)提取、數(shù)據(jù)預處理、數(shù)據(jù)挖掘、知識評估。

數(shù)據(jù)挖掘技術是人們長期對數(shù)據(jù)庫技術進行研究和開發(fā)的結果。起初各種商業(yè)數(shù)據(jù)是存儲在計算機的數(shù)據(jù)庫中的,然后發(fā)展到可對數(shù)據(jù)庫進行查詢和訪問,進而發(fā)展到對數(shù)據(jù)庫的即時遍歷。數(shù)據(jù)挖掘使數(shù)據(jù)庫技術進入了一個更高級的階段,它不僅能對過去的數(shù)據(jù)進行查詢和遍歷,并且能夠找出過去數(shù)據(jù)之間的潛在聯(lián)系,從而促進信息的傳遞。從商業(yè)數(shù)據(jù)到商業(yè)信息的進化過程中,每一步前進都是建立在上一步的基礎上的。數(shù)據(jù)管理的進化可以分為四個階段: 1) 數(shù)據(jù)搜集。這主要集中在20世紀60年代,其特點為可提供靜態(tài)歷史數(shù)據(jù)。 2) 數(shù)據(jù)訪問。這在80年代發(fā)展起來,我們所熟知的關系數(shù)據(jù)庫、結構化查詢語言等都可對此提供技術支持,其特點為動態(tài)修改數(shù)據(jù)信息。 3) 數(shù)據(jù)倉庫。90年代數(shù)據(jù)倉庫浮出水面,有關技術主要是聯(lián)機分析處理、多維數(shù)據(jù)庫等,其特點為在各層次提供回溯的動態(tài)的歷史數(shù)據(jù)。 4) 數(shù)據(jù)挖掘。這也是當前正在流行的,有關技術內容包括高級算法、多處理系統(tǒng)、海量算法,其最顯著之處在于可以提供預測性信息。

目前,國外數(shù)據(jù)挖掘的發(fā)展趨勢研究方面主要有:對知識發(fā)現(xiàn)方法的研究進一步發(fā)展,如近年來注重對Bayes(貝葉斯)方法以及Boosting 方法的研究和提高;傳統(tǒng)的統(tǒng)計學回歸法在KDD 中的應用; KDD 與數(shù)據(jù)庫的緊密結合。

2數(shù)據(jù)挖掘功能

數(shù)據(jù)挖掘功能用于指定數(shù)據(jù)挖掘任務要找的模式類型。一般而言，數(shù)據(jù)挖掘任務可以分為兩類:描述和預測。描述性挖掘任務描述數(shù)據(jù)庫中數(shù)據(jù)的一般性質。預測性挖掘任務對當前數(shù)據(jù)進行推斷，以做出預測。也是說模式是數(shù)據(jù)挖掘的一個目標，模式經(jīng)過評估和表示后就是知識，數(shù)據(jù)挖掘這個知識發(fā)現(xiàn)過程(KDD)也就結束了。

在某些情況下，用戶不知道他們的數(shù)據(jù)中什么類型的模式是有趣的，因此可能想并行地搜索多種不同的模式。這樣，重要的是數(shù)據(jù)挖掘系統(tǒng)要能夠挖掘多種類型的模式，以滿足不同的用戶需求或不同的應用。此外，數(shù)據(jù)挖掘系統(tǒng)應當能夠在各種粒度(即不同的抽象層)發(fā)現(xiàn)模式。數(shù)據(jù)挖掘系統(tǒng)還應當允許用戶給出提示，指導或聚焦有趣模式的搜索。由于有些模式并非對數(shù)據(jù)庫中的所有數(shù)據(jù)都成立，通常每個被發(fā)現(xiàn)的模式都附上一個確定性或“可信性”度量。

當前描述(關聯(lián))和預測(分類)挖掘認為是不相交的研究和應用領域，關于它們相結合的研究較少。對于關聯(lián)挖掘很具代表性的算法就是Apriori。而分類挖掘則有決策樹方法、基于規(guī)則的方法、基于記憶推理、神經(jīng)網(wǎng)絡、樸素貝葉斯和貝葉斯信念網(wǎng)絡、支持向量機等多種方法。下面將對兩方面的技術發(fā)展作一下探討。

2.1關聯(lián)規(guī)則挖掘技術

關聯(lián)規(guī)則挖掘問題就是在事務數(shù)據(jù)庫D中找出具有用戶給定的最小支持度minsup和最小置信度minconf的關聯(lián)規(guī)則。關聯(lián)規(guī)則挖掘問題可以分解為以下兩個子問題。

1) 找出存在與事務數(shù)據(jù)庫中的所有強項集X的支持度support(X)不小于用戶給定的最小支持度minsup,則稱X為強項集(large itemset) 。

2) 利用強項集生成關聯(lián)規(guī)則。對于每個強項集A，若B

事實上,挖掘關聯(lián)規(guī)則的整個執(zhí)行過程中第一個子問題是核心問題。當找到所有的最大項目集后,相應的關聯(lián)規(guī)則將很容易生成。

R.Agrawal等提出了關聯(lián)規(guī)則挖掘問題以后,一批有效的挖掘關聯(lián)規(guī)則的算法在過去幾年中得到了長足的發(fā)展。到目前為止,其主要研究方向有:基于規(guī)則中涉及到的數(shù)據(jù)維數(shù)的挖掘算法，基于規(guī)則中數(shù)據(jù)的抽象層次的挖掘算法, 基于規(guī)則中處理變量類別的挖掘算法, 其他關聯(lián)規(guī)則算法等。

在此，本文只分析經(jīng)典的Apriori算法。算法Apriori 利用“在給定的事務數(shù)據(jù)庫D中，任意強項集的子集都是強項集；任意弱項集的超集都是弱項集”這一原理對事務數(shù)據(jù)庫進行多次掃描,第一次掃描得出大1-項集L1，第k(k>1)次掃描前先利用第k-1次掃描的結果(即大k-1項集Lk-1) 和函數(shù)Apriori-gen產(chǎn)生候選大k-項集Ck,然后在掃描過程中確定Ck中每個元素的支持數(shù),最后在每次掃描結束時計算出大k-項集Lk,算法在當候選大k-項集Ck為空時結束。

2.2樸素貝葉斯分類方法

貝葉斯分類算法是一類利用概率統(tǒng)計知識進行分類的算法，它可以預測類成員關系的可能性。由于貝葉斯方法具有堅實的數(shù)學理論基礎以及綜合先驗信息和數(shù)據(jù)樣本信息的能力，該方法成為研究分類問題的重要方法之一。

設每個數(shù)據(jù)樣本用一個n維特征向量來描述n個屬性的值，即:X={x1，x2，…，xn}，假定有m個類，分別用C1,C2,…，Cm表示。給定一個未知的數(shù)據(jù)樣本X(即沒有類標號)，若樸素貝葉斯分類法將未知的樣本X分配給類Ci，則一定是P(Ci|X)>P(Cj|X) 1≤j≤m，j≠i。

根據(jù)貝葉斯定理，由于P(X)對于所有類為常數(shù)，最大化后驗概率P(Ci|X)可轉化為最大化先驗概率P(X|Ci)P(Ci)。如果訓練數(shù)據(jù)集有許多屬性和元組，計算P(X|Ci)的開銷可能非常大，為此，通常假設各屬性的取值互相獨立，這樣先驗概率P(x1|Ci)，P(x2|Ci)，…，P(xn|Ci)可以從訓練數(shù)據(jù)集求得。

根據(jù)此方法，對一個未知類別的樣本X，可以先分別計算出X屬于每一個類別Ci的概率P(X|Ci)P(Ci)，然后選擇其中概率最大的類別作為其類別。

樸素貝葉斯算法成立的前提是各屬性之間互相獨立。當數(shù)據(jù)集滿足這種獨立性假設時,分類的準確度較高，否則可能較低。另外，該算法沒有分類規(guī)則輸出。

3相關研究工作

NB由于它的高效率以及準確性越來越受到重視。許多關于分類算法的比較研究表明，NB在許多領域甚至可以與一些構造復雜的分類算法相媲美，如C4.5、神經(jīng)網(wǎng)絡。

然后，在許多現(xiàn)實領域，類屬性條件獨立假設并不成立。因此，各種研究就主要集中在怎樣使用某種技術來減弱這個獨立假定限制來改進NB。最初的Bayesian Network完全去掉了這種假定，從而導致了NP問題的出現(xiàn)。然而，實踐證明:沒有獨立假定限制的Bayesian Network，其分類精度并不總比NB高，而且在某些領域甚至顯得明顯不足。Friedman和Goldzmidt提出了一種優(yōu)化的基于BN的拓撲結構TAN(Tree-Augmented Naive Bayesian Network)。TAN簡化網(wǎng)絡結構為樹結構，且只考慮屬性對之間最重要的關聯(lián)。

上面的兩種方法皆在減弱這個獨立假定限制。對于變量x,y,z,稱x和y關于給定的變量z條件依賴，如果公式P(x|y,z)=P(x|z)成立，其中P(y,z)>0。假設一個極端情況，就是公式P(x|y,z)=P(x|z)對幾乎所有的關于x,y,z的實例成立，很顯然，x和y條件依賴于c。像如上情況算法將存儲聯(lián)合概率分布P(x,y,z)的所有元素，用它在分類時可以取得很好的精度。這種不但冗余而且易錯，因為沒有足夠的數(shù)據(jù)對所有可能的變量分配提高可靠概率估計。C.Boutilier提出了指定上下文依賴的概念，只考慮在指定上下文中變量的依賴關系。相似地，貝葉斯多重網(wǎng)絡(Bayesian Multinets)模型分別對每個類中變量的關系。在此，如果更進一步，只考慮實例中的變量的關系的話更完美了。

4對樸素貝葉斯方法的改進

本文試著從實例中變量關系的角度來估計元素的概率分布，這些關系將用項目集來表示。

發(fā)現(xiàn)關聯(lián)模式的算法要求數(shù)據(jù)是二元屬性形式。這樣，常常需要將連續(xù)屬性變換成分類屬性(離散化，discretization)，并且連續(xù)和離散屬性可能都需要變換成一個或多個二元屬性(二元化，binarization)。此外，如果一個分類屬性具有大量不同值(類別)，或者某些值出現(xiàn)不頻繁，則對于特定的數(shù)據(jù)挖掘任務，通過合并某些值減少類別的數(shù)目可能是有益的。結果的間隔考慮為明顯的屬性值，每個可能的屬性值對都稱為一個項目。對于給定的有n個屬性的訓練樣本通常用項目集{a1,…an}表示，并用類ci標記。其中標記的項目集大小為n(每個n屬性都有一個值，但是不包括類的值)。每個訓練樣本看成是一組事務集合。

4.1挖掘感興趣的和頻繁的項目集

令D為訓練樣本集。如果項目集l在D中關于類ci的支持度為s(D中有s%的樣本同時包含l和ci)，有公式l.supi=s。同樣，D中l(wèi)的支持度表示為l.sup，注意l.supi就是觀察到的概率P(l,ci),同樣的l.sup就是觀測到的概率P(l)。如果它的支持度高于給定的最小支持度minsup，稱它為頻繁的。

對于樣本實例A={a1,…,an},如果結合A的子集的先驗知識，分類精度應該能得到提升。長的項目集明顯有利于分類，因為它含有更多關于屬性聯(lián)系的信息。

假定將對實例A={a1,…,an}進行分類。在學習階段要挖掘出所有感興趣的和頻繁的項目集F。圖1顯示了A的所有子集，其中不頻繁的和不感興趣的子集用斜體表示。在此選擇F的邊界項目集，所謂邊界項目集就是含有A子集的可能的最長的項目集，在圖中我們用黑體表示。經(jīng)典的樸素貝葉斯算法因為假定所有屬性之間獨立，所有只考慮了圖1的第一層的情況。對于TAN則用到了第二層的某些項目集。

在此采用類似于Apriori的算法挖掘其中感興趣的和頻繁的項目集，具體算法將在后面提到。算法尋找在F中的最長的子集增量構造P(A,ci)的近似估計。

a1a2a3a4a5

a1a2a1a3a1a4a1a5a2a3a2a4a2a5a3a4a3a5a4a5

a1a2a3a1a2a4a1a2a5a1a3a4a1a3a5a1a4a5a2a3a4a2a3a5a2a4a5a3a4a5

a1a2a3a4a1a2a3a5a1a2a4a5a1a3a4a5a2a3a4a5

a1a2a3a4a5

現(xiàn)在考慮下面的幾個公式，為圖1中用邊界項目集關于{a1,…an}的乘積逼近估計：

1) {a1a2a3},{a1a4a5}?P(a1a2a3ci)P(a4a5|a1ci);

2) {a1a2a3},{a2a5},{a1a4a5}?P(a1a2a3ci)P(a5|a2ci)P(a4|a1a5ci);

3) {a1a2a3},{a2a5},{a3a4}?P(a1a2a3ci)P(a5|a2ci)P(a4|a3ci);

4) {a2a5},{a3a5},{a1a2a3},{a1a4a5}?P(a2a5ci)P(a3|a5ci)P(a1|a2a3ci)P(a4|a1a5ci)。

注意{a1a2a3},{a1a4a5},{a2a5}同2)有相同的項目集(順序不一樣)不是乘積逼近估計，因為{a2a5}中的元素已經(jīng)在前兩個項目集中包含了。對于一個給定的項目集明顯的有不止一個的乘積逼近估計，并一定包括所有的邊界項目集。為此需要制定一個策略增量對A估計，每次增加一個項目集，直到遍歷完所有的項目集。本文采取了四個條件保證估計工作得到順利進行:

1) |l-已選元素|≤1

2) |lk-已選元素|≥|lj-已選元素|

3) |lk|≥|lj|

4)lk比lj更感興趣

條件1)保證了該方法為乘積逼近，如果滿足后面三個條件，就用lk代替lj；條件2)保證序列中的每個項目集含有未覆蓋項目的最少元素，等同于使用項目集數(shù)目最大化。該條件有效考慮到高次序的項目集(減弱條件依賴假設)；如果條件2)兩項目集有項目的最小數(shù)目，條件3)優(yōu)先考慮長項目集，同樣是為了減弱條件依賴性；條件4)則優(yōu)先考慮感興趣度高的項目集。

表1給出了P(a1,…a5ci) 乘積逼近的增量估計過程，開始已選元素集設為空集，所有的項目集滿足條件Ⅰ，滿足條件Ⅱ的有{a2a5},{a3a4},{a3a5}，但是三個集合都有相同的大小。為此需要選擇最感興趣的，假定選擇{a2a5}。然后將它放入已選項目中，元素a2和a5放入已選項目中。再看剩余的項目集，{a3a5}包含最少的未覆蓋集，僅有a3。將它放入已選項目中并標記為已選。接著{a3a4}和{a1a2a3}都含有一個未覆蓋集，由條件3)選擇{a1a2a3}。最后{a3a4}未選擇，因為它所有的元素在已選項目都有了。從以上選擇可以得到P(a1,…a5ci) 乘積逼近的結果P(a2a5ci)P(a3|a5ci)P(a1|a2a3ci)P(a4|a1a5ci)。

表1　P(a1,…a5ci) 乘積逼近的增量估計過程

算法genItemsets用基于Apriori算法的自低向上的方法產(chǎn)生感興趣集和頻繁集。為了有利于類計算，每個項目集對每個類ci都關聯(lián)計數(shù)器counti。

首先，所有的1-項目集l=(ai)都包括在F1中。然后對數(shù)據(jù)庫D遍歷對每個類ci得到類計數(shù)l.counti。這樣保證該分類算法最少和樸素貝葉斯含有一樣的信息。同樣，集Fk包括長度為k的項目集的所有感興趣集和頻繁集。

genItemsets(D)

輸入:數(shù)據(jù)庫D中的樣本

輸出:項目集l的集F和它們的類計數(shù)l.counti。

1.F1={{aj}aj是非類屬性}

2. 對所有的l∈F1和所有的類i計算l.counti。

3. for(k=2,Fk-1≠∮;k++) {

4.Ck=genCandidates(Fk-1)

5. for all tuplest∈D{

6.Ct=subsets(Ck,t);

7.i=class oft;

8.for all candidate l∈Ct{

9.l.counti++;

10. }

11. }

12.Fk=selectF(Ck)

13.}

14. returnF=∪kFkand l.countifor all l∈Fand all I

genItemsets算法產(chǎn)生候選集Ck，即Fk-1的超集。第5～9行搜索數(shù)據(jù)庫計算所有項目集關于的Ck類支持度。對于D中的每個元組t，選擇屬于Ck的所有子集，相應類的計數(shù)加一。這樣算出候選項目集l的類支持度l.counti。等待計數(shù)完成，項目集增加，接著selectF選出頻繁集。

(1)

興趣度I(l|lj,lk)是衡量這個估計的方法:

(2)

當P(l,ci)=Pj,k(l,ci)時，I(l|lj,lk)就會等于零；

在項目集l中，有|l|(|l|-1)/2對不同的lj，lk，l的興趣度定義為這些的平均值，有:

(3)

I(l)的值高表示l是感興趣的，因為P(l,ci)不能用小項目集估計。如果I(l)值低于一閾值α，可以忽略它，因為它不能提供更多的信息。

4.2分類算法

classify(F,A)

輸入:樣本A的集F

輸出:A的所屬分類ci

1.cov=∮//A中已選項目集

2.nom=∮//

3.den=∮//

4.B={l∈Aand?l′∈F:l′?Aandl?l′}.

5.for (k=1,cov?A,k++) {

6.lk=pickNext(cov,B)

7.nom=nom∪{lk}

8.den=den∪{lk∩cov}

9.cov=cov∪lk

10.}

(4)

pickNext(cov,B)

T={l∈B: |l-covered|≥1};

返回一項目集lk∈T，并其它的項目集lj∈T；

a)|lk-covered|<|lj-covered|，或者

b)|lk-covered|=|lj-covered|有|lk|>|lj|，或者

c)|lk-covered|=|lj-covered|，|lk|>|lj|，有I(lk)>I(lj)

前面已經(jīng)提到，分類就是每次加入一個項目集增量對A乘積逼近，直到?jīng)]有可加的項目集為止。第4行選擇A的頻繁集F的邊界B；函數(shù)pickNext就是用我們定義的四個條件選取合適的子集加入已選項目集中。第6行每個選擇的項目集lk都對乘積逼近有影響，已知覆蓋元素，lk的未覆蓋元素的條件概率可以表示為

(5)

第7行和第8行分別是式(5)的分子和分母估計的項目集，lk和lk∩cov分別存儲在集nom和den中，并用式(4)計算出每個類ci的乘積逼近的值，并返回最有可能的類。對于P(l,ci)可以用公式P(l,ci)=l.counti/|D|計算。

5結語

當需要對一個新的樣本分類時，根據(jù)前面的分類算法充分考慮樣本間各屬性的內在聯(lián)系，在最差情況下，即找出的項目集F的大小都為1時，該分類器等同于經(jīng)典樸素貝葉斯算法。

參 考 文 獻

[1] 談恒貴,王文杰,李游華.數(shù)據(jù)挖掘分類算法綜述[J].微型機與應用, 2005(2):4-9.

[2] 羅海蛟.數(shù)據(jù)挖掘中分類算法的研究及其應用[J].微機發(fā)展,2003,13(2):48-250.

[3] 王峻.一種基于屬性相關性度量的樸素貝葉斯分類模型[J].安慶師范學院學報,2007,13(2):14-16.

[4] Zhang H, Sheng S. Learning weighted Naive Bayes with accurate ranking[C]//Proceedings of the 4th IEEE International Conference on Data Mining,2004:567-570.

[5] 吳寧,柏春霞,祝毅博.一種應用關聯(lián)規(guī)則森林的改進貝葉斯分類算法[J].西安交通大學學報,2009,43(2):48-52.

[6] 張明衛(wèi),王波,張斌,等.基于相關系數(shù)的加權樸素貝葉斯分類算法[J].東北大學學報,2008,29(7):953-955.

[7] 李方,劉瓊蓀.基于改進屬性的加權樸素貝葉斯分類模型[J].計算機工程與應用，2010，46(4):132-133.

Improvement of Naive Bayes By Association Rule Excavation

YU JieDING XiaojianCUI Peng

(Science and Technology on Information Systems Engineering Laboratory, Nanjing210007)

AbstractNaive Bayes algorithm is based on condition independence assumption. However, in the real world application, attribute condition independence assumption is not exist. To solve this problem, association rule method is combined to construct an improved naive Bayes classifier. By mining interesting and frequent item sets, Class supports of frequent item sets are computed in the training phase. Upon arrival of a new case to be classified, some of the generated item sets are selected and their class supports are used to compute the probability that the case belongs to tihs class. The results is the class with highest such probability.

Key Wordsnaive Bayes, condition independence assumption, item sets

* 收稿日期：2015年11月9日,修回日期：2015年12月28日

作者簡介：俞杰,男,高級工程師,研究方向:系統(tǒng)建模與仿真。丁曉劍,男,高級工程師,研究方向:數(shù)據(jù)挖掘。崔鵬,男,工程師,研究方向:系統(tǒng)仿真研究。

中圖分類號TP311

DOI：10.3969/j.issn.1672-9730.2016.05.029