關(guān)聯(lián)規(guī)則的樸素貝葉斯分類結(jié)構(gòu)優(yōu)化仿真

王正杰+姚道洪

摘要：樸素貝葉斯分類器要求屬性變量間相互獨立，此時的分類準(zhǔn)確率和效率是很高的，但是不滿足該條件時分類性能就會受很大影響。針對屬性變量間不相互獨立造成分類性能低這一問題，借助于關(guān)聯(lián)規(guī)則挖掘，提出一種優(yōu)化樸素貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)的方法。首先，預(yù)置合適的支持度和置信度挖掘強(qiáng)關(guān)聯(lián)規(guī)則，找到屬性變量、分類變量間的共現(xiàn)關(guān)系；然后，根據(jù)關(guān)聯(lián)規(guī)則對屬性變量進(jìn)行約減，在樸素貝葉斯分類結(jié)構(gòu)基礎(chǔ)上做節(jié)點和邊的增減；最后，分別通過增邊、約簡和混合優(yōu)化得到三種結(jié)構(gòu)模型。對比仿真實驗表明，增邊可以有效提高分類準(zhǔn)確率，節(jié)點和邊的約減可以有效提高分類效率。

關(guān)鍵詞： 關(guān)聯(lián)規(guī)則；樸素貝葉斯分類器；貝葉斯網(wǎng)絡(luò)；網(wǎng)絡(luò)結(jié)構(gòu)；數(shù)據(jù)挖掘

中圖分類號：TP391.9 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2017）27-0241-05

Abstract：The naive bayes classifier requires that the attributes are independent of each other， the classification accuracy and efficiency is high at this time， but when the condition is not satisfied， the classification performance will be greatly affected. Aiming at the problem that the attribute variables are not independent of each other， the classification performance is low， this paper puts forward a method of optimizing the network structure Based on association rule mining. First of all， set the appropriate support and confidence， mining association rules， find the attribute variables， classification of co-occurrence between relations；Then， according to the association rules to subtract attribute variables do increase or decrease of nodes and edges Based on naive bayesian classifier network structure；Finally， by adding edges， reduce the nodes and edges， hybrid optimization， this paper get the structure model of three kinds of optimization.The simulation experiments show that the increase side can effectively improve the classification accuracy of nodes and edges of subtract， can effectively improve the efficiency of classification.

Key words：association rule mining； naive bayes classifier； bayesian networks； network structure； data mining

1 概述

在眾多分類技術(shù)中，樸素貝葉斯分類器在很多領(lǐng)域中因有很好的分類能力而受青睞，它的結(jié)構(gòu)模型簡單而有代表性，基本數(shù)學(xué)理論源出貝葉斯公式，分類預(yù)測模型泛化能力強(qiáng)，準(zhǔn)確率和效率高。可是，屬性變量間獨立假設(shè)的條件決定了該分類器并不能放之四海皆準(zhǔn)，勉強(qiáng)應(yīng)用，其分類結(jié)果可能會違背數(shù)據(jù)反映的內(nèi)在固有信息，當(dāng)然也影響到分類準(zhǔn)確率。因此，在樸素貝葉斯分類結(jié)構(gòu)的基礎(chǔ)上進(jìn)行結(jié)構(gòu)的優(yōu)化對有效提高準(zhǔn)確率或效率是一個突破。

為獲得具有更高分類準(zhǔn)確率和效率的網(wǎng)絡(luò)結(jié)構(gòu)，很多專家學(xué)者在樸素貝葉斯分類結(jié)構(gòu)的基礎(chǔ)上做了很多改進(jìn)工作。文獻(xiàn)[1]在樸素貝葉斯分類結(jié)構(gòu)的屬性節(jié)點間加入能夠減緩樸素貝葉斯的強(qiáng)獨立性假設(shè)的增強(qiáng)弧，建立了雙層貝葉斯模型（DLBAN），大大提高了查全率和查準(zhǔn)率；文獻(xiàn)[2]提出一種特征加權(quán)樸素貝葉斯分類器（FWNB），分類的正確率與樹擴(kuò)展樸素貝葉斯（TAN）和樸素貝葉斯樹（NBTree）的相當(dāng)，但分類的效率有所提高；文獻(xiàn)[3]提出了一種基于先驗節(jié)點序?qū)W習(xí)網(wǎng)絡(luò)結(jié)構(gòu)的優(yōu)化方法，定義優(yōu)化目標(biāo)函數(shù)和可行域空間，將網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)的問題轉(zhuǎn)化成解目標(biāo)函數(shù)極值的數(shù)學(xué)規(guī)劃問題，令人耳目一新；文獻(xiàn)[4]在訓(xùn)練集上選取若干屬性子集，以這些子集來構(gòu)建貝葉斯分類器，利用遺傳算法進(jìn)行優(yōu)選，比樸素貝葉斯方法有更高的分類精度。也有學(xué)者利用關(guān)聯(lián)規(guī)則優(yōu)化網(wǎng)絡(luò)結(jié)構(gòu)：文獻(xiàn)[5]提出一種基于關(guān)聯(lián)規(guī)則屬性約減的貝葉斯方法AD-TAN，在逐層刪除冗余節(jié)點時，計算較為繁瑣；文獻(xiàn)[6]提出一種基于關(guān)聯(lián)規(guī)則的貝葉斯網(wǎng)絡(luò)分類算法，先利用關(guān)聯(lián)規(guī)則挖掘候選網(wǎng)絡(luò)邊集，再通過貪心算法學(xué)習(xí)網(wǎng)絡(luò)結(jié)構(gòu)，算法復(fù)雜不易操作。

關(guān)聯(lián)規(guī)則挖掘可以把看似互不相關(guān)的項歸在不同的項集里，挖掘出項間潛在的共現(xiàn)關(guān)系。比如在很多資料中都提到沃爾瑪超市利用關(guān)聯(lián)規(guī)則挖掘找到了“啤酒”和“尿布”的關(guān)聯(lián)關(guān)系，這也是關(guān)聯(lián)規(guī)則應(yīng)用當(dāng)中最神奇和最成功的案例之一。

本文將挖掘的關(guān)聯(lián)規(guī)則作為優(yōu)化分類結(jié)構(gòu)的依據(jù)，通過增邊提高分類準(zhǔn)確率，通過節(jié)點和邊的約減提高分類效率，通過設(shè)置不同的關(guān)聯(lián)規(guī)則支持度和置信度閾值控制結(jié)構(gòu)優(yōu)化的程度。下面先介紹樸素貝葉斯分類器和關(guān)聯(lián)規(guī)則挖掘技術(shù)，再闡述結(jié)構(gòu)優(yōu)化的三種模型，最后做仿真實驗與其他分類算法做效果對比，以此說明優(yōu)化算法的優(yōu)越性。endprint

2 樸素貝葉斯分類原理

2.1 貝葉斯網(wǎng)絡(luò)

貝葉斯網(wǎng)絡(luò)（Bayesian Networks， BN）是一種推理工具，基本理論基于概率論和圖論。對于變量集[V={X1，X2，...，Xn}]對應(yīng)了一個二元組[（G，P）]，[G]表示一個有向無環(huán)圖，也稱為貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)，[P]表示一個條件概率表（CPT），也稱為貝葉斯網(wǎng)絡(luò)參數(shù)。在圖[G]中，一個節(jié)點[A]的所有前驅(qū)節(jié)點稱為[A]的父節(jié)點集，用[Pa（A）]表示。

3.1.2 Apriori 算法

在挖掘頻繁項集的關(guān)聯(lián)規(guī)則算法當(dāng)中，Apriori 算法是最早和最經(jīng)典的算法之一。Apriori 算法通過反復(fù)迭代來計算數(shù)據(jù)庫中的頻繁項集，第i次迭代計算出的項集[Li]稱為頻繁i-項集，每一次迭代過程中都要經(jīng)歷確定候選集[Ci]和根據(jù)最小支持度minsup選擇候選集[Li]兩個步驟，分別稱為連接（join）和剪枝（prune）。算法的輸入是數(shù)據(jù)事務(wù)集，預(yù)設(shè)支持度和置信度閾值，最終輸出頻繁項目集。

另外，由于Apriori算法頻繁地掃描數(shù)據(jù)集，所以算法效率并不高，為此很多專家學(xué)者提出了一些改進(jìn)算法，如AprioriTid算法、DHP算法、Partition算法、FP-growth算法、DLG算法等[5]。

3.2 結(jié)構(gòu)優(yōu)化算法

3.2.1 屬性變量間結(jié)構(gòu)擴(kuò)展算法ESBA

所謂樸素貝葉斯分類器屬性變量間結(jié)構(gòu)擴(kuò)展（Extended structure between attributes， ESBA），是指在樸素貝葉斯網(wǎng)絡(luò)的基礎(chǔ)上添加屬性變量節(jié)點間的邊，使得新結(jié)構(gòu)更能適應(yīng)樣本數(shù)據(jù)，目的是使網(wǎng)絡(luò)分類能力更強(qiáng)，能彌補(bǔ)NBC的網(wǎng)絡(luò)結(jié)構(gòu)適應(yīng)性差的缺點。利用關(guān)聯(lián)規(guī)則對NBC結(jié)構(gòu)擴(kuò)展的流程如圖2。

具體步驟是：

（1） 確定最小支持度，先對關(guān)聯(lián)規(guī)則進(jìn)行試挖掘。如果最小支持度比較小，挖掘出的關(guān)聯(lián)規(guī)則數(shù)量會很大，結(jié)構(gòu)擴(kuò)展時加邊數(shù)量會增多，不利于簡化結(jié)構(gòu)；如果最小支持度比較大，挖掘出的關(guān)聯(lián)規(guī)則數(shù)量較少，需擴(kuò)展的邊數(shù)量也會較少甚至沒有，達(dá)不到結(jié)構(gòu)擴(kuò)展的目的。所以，最小支持度的確定要考慮以上兩因素，有必要多次嘗試后確定最終的最小支持度。

（2） 從關(guān)聯(lián)規(guī)則中選出前項和后項都是屬性變量節(jié)點的高置信度和高提升度的規(guī)則，在已有NBC結(jié)構(gòu)上按照從先決條件節(jié)點到結(jié)果節(jié)點指向添加有向邊，完成一次結(jié)構(gòu)擴(kuò)展。

（3） 依照擴(kuò)展后的結(jié)構(gòu)計算分類準(zhǔn)確率，把握網(wǎng)絡(luò)分類能力。如果分類性能沒有得到明顯改善，則終止結(jié)構(gòu)擴(kuò)展，結(jié)束。如果分類性能好，說明上一次加邊擴(kuò)展的新結(jié)構(gòu)更優(yōu)，有必要繼續(xù)加邊，轉(zhuǎn)到第4步。

（4） 找到次高置信度的規(guī)則，重復(fù)第2、3步，直至不能再添加有效的有向邊。

在NBC結(jié)構(gòu)的基礎(chǔ)上增加屬性變量節(jié)點間的邊，結(jié)構(gòu)要比NBC的復(fù)雜，這在分類的準(zhǔn)確率上可能有所提高，但結(jié)構(gòu)的復(fù)雜化使屬性變量節(jié)點較多時分類效率降低。

3.2.2 屬性變量間結(jié)構(gòu)約簡算法RS

在有的大型事務(wù)中，項目集[I]=[i1，][i2，][...] [，in]的項目數(shù)比較多，利用NBC進(jìn)行結(jié)構(gòu)建模時冗余的屬性變量節(jié)點也會很多，這時可以考慮利用關(guān)聯(lián)規(guī)則挖掘出對分類起關(guān)鍵作用的屬性，利用這些關(guān)鍵屬性做NBC結(jié)構(gòu)建模，這樣能大大提高運(yùn)算效率，在分類準(zhǔn)確率上還不會有太大影響。這一做法可稱為結(jié)構(gòu)約簡（Reduction structure，RS），具體做法是：

（1） 挖掘那些屬性變量節(jié)點為前項，分類屬性節(jié)點為后項的關(guān)聯(lián)規(guī)則，規(guī)則[R]要滿足基本條件，見（4）式。

（2） 關(guān)聯(lián)規(guī)則中沒有出現(xiàn)的屬性變量為冗余變量，在NBC的結(jié)構(gòu)中將相應(yīng)的節(jié)點刪除。

需要注意的是，如此構(gòu)造的NBC擴(kuò)展結(jié)構(gòu)可能會在分類準(zhǔn)確率上有損失，但以準(zhǔn)確率的略微損失換取結(jié)構(gòu)精減帶來的高效分類，這對高維實例集分類是值得的。

3.2.3 混合結(jié)構(gòu)優(yōu)化算法EHS

NBC的混合結(jié)構(gòu)擴(kuò)展（ Expansion of the hybrid structure，EHS）是指將前述ESBA和RS技術(shù)相結(jié)合，根據(jù)挖掘的關(guān)聯(lián)規(guī)則，在屬性變量節(jié)點間即考慮增加邊，又考慮對屬性變量節(jié)點進(jìn)行約簡，混合結(jié)構(gòu)擴(kuò)展EHS力求在NBC結(jié)構(gòu)基礎(chǔ)上進(jìn)一步優(yōu)化，目的是調(diào)整分類準(zhǔn)確率和效率，使優(yōu)化后的分類器有更好的分類能力。另外，在混合結(jié)構(gòu)擴(kuò)展過程中可能會遇到的情況和處理辦法如下：

（1） 關(guān)聯(lián)規(guī)則后項結(jié)果全是屬性變量而沒有分類變量，此時不再做屬性約簡，只考慮在屬性變量節(jié)點間加邊，此時的網(wǎng)絡(luò)結(jié)構(gòu)應(yīng)該比NBC結(jié)構(gòu)復(fù)雜，此種網(wǎng)絡(luò)分類能力較強(qiáng)，但效率比NBC應(yīng)該差。

（2） 關(guān)聯(lián)規(guī)則后項結(jié)果全是分類變量而沒有屬性變量，此時只做屬性約簡，不在屬性變量節(jié)點間增加邊，此時的網(wǎng)絡(luò)結(jié)構(gòu)屬性變量節(jié)點數(shù)量減少，是一個規(guī)模較小的NBC結(jié)構(gòu)。此種網(wǎng)絡(luò)分類能力比NBC稍差，但分類效率大大提升。

（3） 關(guān)聯(lián)規(guī)則中前項和后項即有屬性變量也有分類變量，是兩類變量間的混雜規(guī)則，這時即考慮對屬性變量節(jié)點進(jìn)行約簡，又考慮在屬性變量節(jié)點間增加邊。另外，關(guān)于關(guān)聯(lián)規(guī)則還要注意：如果規(guī)則[R：A，B?C]滿足基本條件（4）式，那么[R1：A?C]，[R2：B?C]也都滿足基本條件，在擴(kuò)展的結(jié)構(gòu)中要做相應(yīng)的結(jié)構(gòu)優(yōu)化。

（4） 如果[A，B]是兩個屬性變量，規(guī)則[R1：A?B]與[R2：B?A]同時出現(xiàn)時，取兩者的置信度[conf]較高者，如果置信度都一樣兩規(guī)則中任選其一。

3.2.4 舉例

為進(jìn)一步說明結(jié)構(gòu)模型擴(kuò)展過程，下面以Weka 3.9 自帶文件weather.nominal.arff的數(shù)據(jù)來源進(jìn)行仿真。數(shù)據(jù)中有14個實例，五個變量，其中有四個屬性變量（outlook， temperature， humidity， windy），一個分類變量（play），均為離散型變量，取值情況見表1。endprint

本例來看，ESBA模型和EHS模型與NBC的分類能力相當(dāng)，可替代NBC進(jìn)行分類。RS模型因刪除了一個屬性節(jié)點，分類正確率降低。weather數(shù)據(jù)集實例數(shù)量少，屬性變量個數(shù)少，較難發(fā)現(xiàn)分類效率的差異，后文大型數(shù)據(jù)集的仿真結(jié)果就可反映這一點。

4 仿真及分析

下面將上述樸素貝葉斯分類器的幾種結(jié)構(gòu)優(yōu)化技術(shù)應(yīng)用到其他數(shù)據(jù)集，并做分類正確率的對比。另外，再將EHS與其他分類技術(shù)做分類性能對比，其他技術(shù)包括決策樹、支持向量機(jī)、BP神經(jīng)網(wǎng)絡(luò)。如果數(shù)據(jù)集中屬性變量為連續(xù)型，則用Weka.unsuperised.attribute.discretize過濾器進(jìn)行等頻離散化處理。首先對UCI數(shù)據(jù)集iris進(jìn)行仿真。NBC、ESBA、RS、EHS分類正確率對比情況見表3，四個模型的結(jié)構(gòu)見圖4。

對比中可見，在大型數(shù)據(jù)集中，利用關(guān)聯(lián)規(guī)則對屬性變量進(jìn)行約減可以很大程度提升分類效率，縮短建模時間，在正確率上可能會略有損失；利用關(guān)聯(lián)規(guī)則增加共現(xiàn)屬性變量間的邊，有利于提高分類的正確率，但在分類效率上略有損失，建模時間通常會多一些；混合結(jié)構(gòu)優(yōu)化EHS模型在各數(shù)據(jù)集中正確率和效率有波動，是因為屬性約減和增減邊的規(guī)模各有不同。在后續(xù)研究中可以嘗試通過控制關(guān)聯(lián)規(guī)則挖掘的最小支持度和最小置信度有效改變強(qiáng)關(guān)聯(lián)規(guī)則數(shù)量，以達(dá)到控制分類正確率和分類效率的目的。

5 結(jié)束語

樸素貝葉斯分類器因獨立假設(shè)的條件在應(yīng)用上受局限，分類準(zhǔn)確率也受影響。為此，通過關(guān)聯(lián)規(guī)則挖掘找到分類屬性、類別間的共現(xiàn)關(guān)系，對樸素貝葉斯分類器的結(jié)構(gòu)模型進(jìn)行修繕優(yōu)化。通過仿真實驗，證實了新結(jié)構(gòu)的分類器在分類準(zhǔn)確率或效率上各有所長，將其應(yīng)用到大型數(shù)據(jù)集中定能發(fā)揮優(yōu)勢，對于以后做進(jìn)一步屬性降維、提高準(zhǔn)確率和效率的研究有一定作用。

參考文獻(xiàn)：

[1] 郗海龍，張玉環(huán). 惡意網(wǎng)絡(luò)軟件行為評估中的分類優(yōu)化模型仿真[J]. 計算機(jī)仿真，2015，（10）：467-470.

[2] 程克非，張聰. 基于特征加權(quán)的樸素貝葉斯分類器[J]. 計算機(jī)仿真，2006，（10）：92-94+150.

[3] 朱明敏，劉三陽，汪春峰. 基于先驗節(jié)點序?qū)W習(xí)貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)的優(yōu)化方法[J]. 自動化學(xué)報，2011，（12）：1514-1519.

[4] 胡為成，胡學(xué)鋼. 基于遺傳算法的樸素貝葉斯分類[J]. 計算機(jī)技術(shù)與發(fā)展，2007，（01）：30-32.

[5] 王曉龍. 基于關(guān)聯(lián)規(guī)則屬性約簡的樹增廣樸素貝葉斯分類器及應(yīng)用[D].吉林大學(xué)，2014.

[6] 張子義，王德亮. 基于關(guān)聯(lián)規(guī)則的貝葉斯網(wǎng)絡(luò)分類器[J]. 計算機(jī)應(yīng)用，2009，（S1）：134-136.

[7] Agrawal R， Mannila H， Srikant R， et al. Fast Discovery of Association Rules[J]. Advances in knowledge discovery and data mining，1996，12（1）：307-328.

[8] 王曉海，吳志剛. 數(shù)據(jù)挖掘：概念、模型、方法和算法[M].北京：清華大學(xué)出版社，2013.

[9] 袁梅宇. 數(shù)據(jù)挖掘與機(jī)器學(xué)習(xí)WEKA應(yīng)用技術(shù)與實踐[M].北京：清華大學(xué)出版，2014.endprint