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

俞　杰　丁曉劍　崔　鵬

(信息系統(tǒng)工程重點(diǎn)實(shí)驗(yàn)室　南京　210007)

?

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

俞杰丁曉劍崔鵬

(信息系統(tǒng)工程重點(diǎn)實(shí)驗(yàn)室南京210007)

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

關(guān)鍵詞樸素貝葉斯; 條件獨(dú)立性假設(shè); 項(xiàng)目集

Class NumberTP311

1引言

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

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

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

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

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

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

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

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

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

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

2) 利用強(qiáng)項(xiàng)集生成關(guān)聯(lián)規(guī)則。對(duì)于每個(gè)強(qiáng)項(xiàng)集A，若B

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

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

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

2.2樸素貝葉斯分類方法

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

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

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

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

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

3相關(guān)研究工作

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

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

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

4對(duì)樸素貝葉斯方法的改進(jìn)

本文試著從實(shí)例中變量關(guān)系的角度來(lái)估計(jì)元素的概率分布，這些關(guān)系將用項(xiàng)目集來(lái)表示。

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

4.1挖掘感興趣的和頻繁的項(xiàng)目集

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

對(duì)于樣本實(shí)例A={a1,…,an},如果結(jié)合A的子集的先驗(yàn)知識(shí)，分類精度應(yīng)該能得到提升。長(zhǎng)的項(xiàng)目集明顯有利于分類，因?yàn)樗懈嚓P(guān)于屬性聯(lián)系的信息。

假定將對(duì)實(shí)例A={a1,…,an}進(jìn)行分類。在學(xué)習(xí)階段要挖掘出所有感興趣的和頻繁的項(xiàng)目集F。圖1顯示了A的所有子集，其中不頻繁的和不感興趣的子集用斜體表示。在此選擇F的邊界項(xiàng)目集，所謂邊界項(xiàng)目集就是含有A子集的可能的最長(zhǎng)的項(xiàng)目集，在圖中我們用黑體表示。經(jīng)典的樸素貝葉斯算法因?yàn)榧俣ㄋ袑傩灾g獨(dú)立，所有只考慮了圖1的第一層的情況。對(duì)于TAN則用到了第二層的某些項(xiàng)目集。

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

a1a2a3a4a5

a1a2a1a3a1a4a1a5a2a3a2a4a2a5a3a4a3a5a4a5

a1a2a3a1a2a4a1a2a5a1a3a4a1a3a5a1a4a5a2a3a4a2a3a5a2a4a5a3a4a5

a1a2a3a4a1a2a3a5a1a2a4a5a1a3a4a5a2a3a4a5

a1a2a3a4a5

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

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)有相同的項(xiàng)目集(順序不一樣)不是乘積逼近估計(jì)，因?yàn)閧a2a5}中的元素已經(jīng)在前兩個(gè)項(xiàng)目集中包含了。對(duì)于一個(gè)給定的項(xiàng)目集明顯的有不止一個(gè)的乘積逼近估計(jì)，并一定包括所有的邊界項(xiàng)目集。為此需要制定一個(gè)策略增量對(duì)A估計(jì)，每次增加一個(gè)項(xiàng)目集，直到遍歷完所有的項(xiàng)目集。本文采取了四個(gè)條件保證估計(jì)工作得到順利進(jìn)行:

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

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

3) |lk|≥|lj|

4)lk比lj更感興趣

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

表1給出了P(a1,…a5ci) 乘積逼近的增量估計(jì)過(guò)程，開(kāi)始已選元素集設(shè)為空集，所有的項(xiàng)目集滿足條件Ⅰ，滿足條件Ⅱ的有{a2a5},{a3a4},{a3a5}，但是三個(gè)集合都有相同的大小。為此需要選擇最感興趣的，假定選擇{a2a5}。然后將它放入已選項(xiàng)目中，元素a2和a5放入已選項(xiàng)目中。再看剩余的項(xiàng)目集，{a3a5}包含最少的未覆蓋集，僅有a3。將它放入已選項(xiàng)目中并標(biāo)記為已選。接著{a3a4}和{a1a2a3}都含有一個(gè)未覆蓋集，由條件3)選擇{a1a2a3}。最后{a3a4}未選擇，因?yàn)樗械脑卦谝堰x項(xiàng)目都有了。從以上選擇可以得到P(a1,…a5ci) 乘積逼近的結(jié)果P(a2a5ci)P(a3|a5ci)P(a1|a2a3ci)P(a4|a1a5ci)。

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

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

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

genItemsets(D)

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

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

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

2. 對(duì)所有的l∈F1和所有的類i計(jì)算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ù)庫(kù)計(jì)算所有項(xiàng)目集關(guān)于的Ck類支持度。對(duì)于D中的每個(gè)元組t，選擇屬于Ck的所有子集，相應(yīng)類的計(jì)數(shù)加一。這樣算出候選項(xiàng)目集l的類支持度l.counti。等待計(jì)數(shù)完成，項(xiàng)目集增加，接著selectF選出頻繁集。

(1)

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

(2)

當(dāng)P(l,ci)=Pj,k(l,ci)時(shí)，I(l|lj,lk)就會(huì)等于零；

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

(3)

I(l)的值高表示l是感興趣的，因?yàn)镻(l,ci)不能用小項(xiàng)目集估計(jì)。如果I(l)值低于一閾值α，可以忽略它，因?yàn)樗荒芴峁└嗟男畔ⅰ?/p>

4.2分類算法

classify(F,A)

輸入:樣本A的集F

輸出:A的所屬分類ci

1.cov=∮//A中已選項(xiàng)目集

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};

返回一項(xiàng)目集lk∈T，并其它的項(xiàng)目集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)提到，分類就是每次加入一個(gè)項(xiàng)目集增量對(duì)A乘積逼近，直到?jīng)]有可加的項(xiàng)目集為止。第4行選擇A的頻繁集F的邊界B；函數(shù)pickNext就是用我們定義的四個(gè)條件選取合適的子集加入已選項(xiàng)目集中。第6行每個(gè)選擇的項(xiàng)目集lk都對(duì)乘積逼近有影響，已知覆蓋元素，lk的未覆蓋元素的條件概率可以表示為

(5)

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

5結(jié)語(yǔ)

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

參 考 文 獻(xiàn)

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

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

[3] 王峻.一種基于屬性相關(guān)性度量的樸素貝葉斯分類模型[J].安慶師范學(xué)院學(xué)報(bào),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] 吳寧,柏春霞,祝毅博.一種應(yīng)用關(guān)聯(lián)規(guī)則森林的改進(jìn)貝葉斯分類算法[J].西安交通大學(xué)學(xué)報(bào),2009,43(2):48-52.

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

[7] 李方,劉瓊蓀.基于改進(jìn)屬性的加權(quán)樸素貝葉斯分類模型[J].計(jì)算機(jī)工程與應(yīng)用，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日

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

中圖分類號(hào)TP311

DOI：10.3969/j.issn.1672-9730.2016.05.029