關聯規則挖掘以改進樸素貝葉斯*

俞　杰　丁曉劍　崔　鵬

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

?

關聯規則挖掘以改進樸素貝葉斯*

俞杰丁曉劍崔鵬

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

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

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

Class NumberTP311

1引言

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

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

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

2數據挖掘功能

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

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

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

2.1關聯規則挖掘技術

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

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

2) 利用強項集生成關聯規則。對于每個強項集A，若B

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

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

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

2.2樸素貝葉斯分類方法

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

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

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

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

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

3相關研究工作

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

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

上面的兩種方法皆在減弱這個獨立假定限制。對于變量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。像如上情況算法將存儲聯合概率分布P(x,y,z)的所有元素，用它在分類時可以取得很好的精度。這種不但冗余而且易錯，因為沒有足夠的數據對所有可能的變量分配提高可靠概率估計。C.Boutilier提出了指定上下文依賴的概念，只考慮在指定上下文中變量的依賴關系。相似地，貝葉斯多重網絡(Bayesian Multinets)模型分別對每個類中變量的關系。在此，如果更進一步，只考慮實例中的變量的關系的話更完美了。

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

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

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

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

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

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

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

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

a1a2a3a4a5

a1a2a1a3a1a4a1a5a2a3a2a4a2a5a3a4a3a5a4a5

a1a2a3a1a2a4a1a2a5a1a3a4a1a3a5a1a4a5a2a3a4a2a3a5a2a4a5a3a4a5

a1a2a3a4a1a2a3a5a1a2a4a5a1a3a4a5a2a3a4a5

a1a2a3a4a5

現在考慮下面的幾個公式，為圖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}中的元素已經在前兩個項目集中包含了。對于一個給定的項目集明顯的有不止一個的乘積逼近估計，并一定包括所有的邊界項目集。為此需要制定一個策略增量對A估計，每次增加一個項目集，直到遍歷完所有的項目集。本文采取了四個條件保證估計工作得到順利進行:

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

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

3) |lk|≥|lj|

4)lk比lj更感興趣

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

表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算法的自低向上的方法產生感興趣集和頻繁集。為了有利于類計算，每個項目集對每個類ci都關聯計數器counti。

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

genItemsets(D)

輸入:數據庫D中的樣本

輸出:項目集l的集F和它們的類計數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算法產生候選集Ck，即Fk-1的超集。第5～9行搜索數據庫計算所有項目集關于的Ck類支持度。對于D中的每個元組t，選擇屬于Ck的所有子集，相應類的計數加一。這樣算出候選項目集l的類支持度l.counti。等待計數完成，項目集增加，接著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)

前面已經提到，分類就是每次加入一個項目集增量對A乘積逼近，直到沒有可加的項目集為止。第4行選擇A的頻繁集F的邊界B；函數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結語

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

參 考 文 獻

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

[2] 羅海蛟.數據挖掘中分類算法的研究及其應用[J].微機發展,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] 吳寧,柏春霞,祝毅博.一種應用關聯規則森林的改進貝葉斯分類算法[J].西安交通大學學報,2009,43(2):48-52.

[6] 張明衛,王波,張斌,等.基于相關系數的加權樸素貝葉斯分類算法[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日

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

中圖分類號TP311

DOI：10.3969/j.issn.1672-9730.2016.05.029