基于屬性加權(quán)的樸素貝葉斯分類算法改進(jìn)

劉牛

安徽工業(yè)大學(xué)計算機(jī)學(xué)院 安徽 243032

0 前言

分類是數(shù)據(jù)挖掘中一項重要的核心技術(shù)，其目的就是通過學(xué)習(xí)得到一個目標(biāo)函數(shù)f，把每個屬性集映射到一個預(yù)先定義的類標(biāo)號y，因此可以將分類看作是從數(shù)據(jù)庫到一組類別的映射。這些類別是被預(yù)先定義的，沒有重合的。數(shù)據(jù)庫里的每一個元組都可以準(zhǔn)確地分配到某個類中。樸素貝葉斯分類器是一種最簡單、有效、具有堅實的理論基礎(chǔ)并在實際應(yīng)用中得到廣泛使用的分類器。樸素貝葉斯分類方法基于條件獨立性假設(shè)，即假設(shè)一個屬性對給定類的影響?yīng)毩⒂谄渌麑傩?，而這在現(xiàn)實問題中往往并不成立，為此，許多學(xué)者做了大量的工作來放松獨立性假設(shè)。Harry Zhang等根據(jù)條件屬性對決策所起的作用給予它們不同的權(quán)值，提出了加權(quán)樸素貝葉斯分類模型。Zhou Jiyi等根據(jù)粗糙集權(quán)重確定方法提出了一種基于區(qū)分矩陣的屬性權(quán)重確定法。程克非、張聰提出了一種基于特征加權(quán)的樸素貝葉斯分類器。秦鋒、任詩流提出一種通過用加權(quán)調(diào)整的先驗概念來代替原樸素貝葉斯的先驗概率。白似雪，梅君提出一種計算每個屬性對每個類的相關(guān)概率和不相關(guān)概率，并以此進(jìn)行加權(quán)。本文提出另一種加權(quán)方法，將信息論里互信息知識與屬性之間的相關(guān)性相結(jié)合，給予不同的條件屬性賦予不同的權(quán)值，實驗證明，這種方法能有效提高分類效果。

1 樸素貝葉斯分類器

每個元組用一個n維屬性向量X= {x1,x2,…xn}表示，描述由n個屬性A1, A2，…，An對元組的n個測量。假定有m個類C1,C2.. .,Cm。這樣，給定一個未知的元組X，其P(Ci|X)最大的類Ci稱為最大后驗假定。根據(jù)貝葉斯定理：

由于P(X)對于所有類為常數(shù)，只需要P(X|Ci)P(Ci) 最大即可。如果類的先驗概率未知，則通常假定這些類是等概率的，即P(C1) =P(C2) = . . .P(Cm)。并據(jù)此對P(Ci|X)最大化。否則，最大化P(X|Ci)P(Ci) 。注意，類的先驗概率可以用P(Ci) =si/s計算其中si是類Ci中的訓(xùn)練樣本數(shù)，而 s 是訓(xùn)練樣本總數(shù)。

給定具有許多屬性的數(shù)據(jù)集，計算P(X|Ci) 的開銷可能非常大。為降低計算P(X|Ci) 的開銷，可以做類條件獨立的樸素假定。給定元組的類標(biāo)號，假定屬性值有條件地相互獨立，即在屬性間不存在依賴關(guān)系。這樣，

先驗概率 p(x1|Ci)，p(x2| Ci)，……，p(xn|Ci)可以從訓(xùn)練數(shù)據(jù)集求得。

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

2 屬性加權(quán)樸素貝葉斯分類算法

在現(xiàn)實實際應(yīng)用中不同的條件屬性與決策屬性之間的相關(guān)程度是不同的，當(dāng)條件屬性與決策屬性的相關(guān)程度高，它對分類的影響就要更大些，反之，如果條件屬性與決策屬性的相關(guān)程度較小，那么它對分類的影響就會很小。條件屬性與決策屬性的相關(guān)關(guān)系可以用相關(guān)系數(shù)的求解公式求得。設(shè)條件屬性為 Xi，決策屬性為 Y，其相關(guān)系數(shù)可以通過 Xi與Y的協(xié)方差與Xi與Y的方差的幾何平均數(shù)求商得到，它反映了Xi與Y屬性的線性相關(guān)緊密的程度，值越大表明屬性之間的聯(lián)系越緊密，反之則聯(lián)系較差。

屬性間的相關(guān)系數(shù)為：

由于權(quán)值的范圍介于0和1之間，則設(shè)定權(quán)值為：

信息論里的互信息概念是描述某個隨機(jī)變量關(guān)于其他隨機(jī)變量變化時的信息量的大小，它可以用來反映條件屬性提供的關(guān)于決策屬性的信息量的大小。而相關(guān)系數(shù)是通過代數(shù)方法里的協(xié)方差與方差來求得的，它側(cè)重與屬性間的偏離程度，能夠有效的改進(jìn)分類能力，但是它對屬性間的變化不敏感。因此希望通過結(jié)合相關(guān)系數(shù)與互信息的知識，從而使屬性獲得更好的權(quán)重，提高分類效果。

設(shè)條件屬性C和決策屬性D的互信息，記為：因此可以得出條件屬性i C的權(quán)值為：

綜合相關(guān)系數(shù)與互信息的權(quán)值公式，定義兩者的平均值作為新的權(quán)值公式：

基于屬性加權(quán)的AWI-AUC算法的實現(xiàn)關(guān)鍵在于求出各條件屬性與決策屬性之間的相關(guān)系數(shù)和他們的互信息。具體算法步驟如下：

步驟1 數(shù)據(jù)預(yù)處理：將訓(xùn)練樣本和待分類樣本進(jìn)行補齊和離散化；

步驟2 分類器的建構(gòu)。

步驟2.1 讀入并攪亂數(shù)據(jù)集，對數(shù)據(jù)集里的條件屬性，決策屬性，以及訓(xùn)練樣例進(jìn)行統(tǒng)計，生成統(tǒng)計表。再將數(shù)據(jù)集劃分為新的訓(xùn)練集和測試集。

步驟2.2 生成分類器網(wǎng)絡(luò)結(jié)構(gòu)，并對其進(jìn)行參數(shù)學(xué)習(xí)。

步驟2.3 計算所有的先驗概率值，即在決策屬性Dj下各個條件屬性Ci取值的概率p(Ci|D)。

步驟3 計算權(quán)值。

步驟 3 .1 權(quán)值 Wc的計算。掃描所有的訓(xùn)練集，求出各條件屬性與決策屬性的協(xié)方差 Cov(Ci，D)和方差 D(Ci)和D(D)，通過公式計算得到相關(guān)系數(shù)ρCiD，則權(quán)重Wc= |ρCiD|。

步驟 3 .2 權(quán)值 Wi的計算。先求出條件屬性和決策屬性的互信息I(Ci,D)，再計算權(quán)重Wi。

步驟3.3 綜合權(quán)值Wc和Wi，求得所需的權(quán)值Wci，并生成屬性權(quán)值列表。

步驟4 分類評估。通過對屬性給予不同的權(quán)值，得出分類結(jié)果。

該算法的性能在各多項式時間內(nèi)完成，并且算法可行。

3 實驗結(jié)果及分析

為了驗證算法的可行性和有效性，用數(shù)據(jù)集對算法進(jìn)行了測試。實驗數(shù)據(jù)集選自UCI(University of California in Irvine)數(shù)據(jù)庫，下載網(wǎng)址是 http：//www.ics.uci.edu/～mlearn/ MLRepository.html。所有數(shù)據(jù)集中數(shù)據(jù)的連續(xù)屬性值均進(jìn)行離散化處理。實驗在MBNC(Bayesian Networks Classifier using Matlab)平臺下完成。首先對數(shù)據(jù)集進(jìn)行隨機(jī)攪亂，打亂數(shù)據(jù)之間原先的排列順序，并對數(shù)據(jù)集采取5疊交叉驗證。每個數(shù)據(jù)集輪流實驗5次，取5次實驗的平均值作為實驗的測試結(jié)果。表1為經(jīng)過預(yù)處理后的數(shù)據(jù)集情況。

表1 預(yù)處理后的數(shù)據(jù)集

實驗結(jié)果如表2所示。O-AUC表示的是沒有使用加權(quán)方法時得出的AUC值，CC-AUC表示的是使用相關(guān)系數(shù)作為加權(quán)方法得到的AUC值，I-AUC表示的是使用信息論中的互信息知識作為權(quán)重后得到的AUC值，AWI-AUC表示的是本文提出的AWI-AUC算法得到的AUC值。

表2 實驗數(shù)據(jù)結(jié)果

由表2可知：

(1) 當(dāng) O-AUC與 CC-AUC，I-AUC比較時，可以看出CC-AUC，I-AUC在各個數(shù)據(jù)集下得到的 AUC值均大于O-AUC，可見通過把條件屬性與決策屬性的相關(guān)系數(shù)和互信息作為條件屬性的權(quán)重，可以提高分類器的分類性能，使得分類更加準(zhǔn)確。

(2) 當(dāng) CC-AUC與 I-AUC比較時，CC-AUC的值比I-AUC的值大的有6個數(shù)據(jù)集，比I-AUC值小的有4個數(shù)據(jù)集，并且這4個數(shù)據(jù)集中的訓(xùn)練集個數(shù)均偏大，可見I-AUC更適合對數(shù)據(jù)集大的進(jìn)行分類，會獲得更好的分類效果，只是原樣本集里填充和離散的數(shù)據(jù)會對原樣本產(chǎn)生影響。CC-AUC在這種情況下可以有效地提高貝葉斯分類能力。但CC-AUC采用的權(quán)重是通過相關(guān)系數(shù)得到，相關(guān)系數(shù)由代數(shù)的計算方法求得，結(jié)合實驗對數(shù)據(jù)規(guī)模偏小的數(shù)據(jù)集更加適合，因此將上述兩種方法綜合求均值，得到新的 AWI-AUC方法，通過實驗證明AWI-AUC在總體上要好于其他方法，并證明了通過挖掘?qū)傩灾g的潛在關(guān)系，對屬性賦予不同程度的權(quán)重，可以獲得更好的分類效果。

4 結(jié)束語

本文基于研究條件屬性與決策屬性之間的關(guān)系，并結(jié)合信息論中互信息的相關(guān)知識，提出一種加權(quán)的AWI-AUC方法，根據(jù)條件屬性對決策分類的重要性不同給予其不同的權(quán)重系數(shù)來對AUC方法進(jìn)行優(yōu)化評估。在MBNC實驗平臺上實現(xiàn)該方法，并在數(shù)據(jù)集上通過實驗比較，表明該方法的有效性和可行性。今后，將進(jìn)一步研究改進(jìn)條件屬性與決策屬性相關(guān)性的方法，以及分析條件屬性與條件屬性之間的關(guān)系，是否能夠更好地提高分類器的分類能力。

[1]秦鋒,楊波,程澤凱.分類器性能評價標(biāo)準(zhǔn)研究[J].計算機(jī)技術(shù)與發(fā)展.2006.

[2]Harry Zhang, Shengli Sheng. Learning Weighted Na?ve Bayes with Accurate Ranking. [C] // The 4th IEEE International Conference on Data Mining.Chicago: IEEE Computer Society,2004.

[3]ZHOU Jiyi, LV Yuejin. A New Method of Ascertaining Attribute Weight Based on Discernibility Matrix.CSIST.2010.

[4]程克非,張聰.基于特征加權(quán)的樸素貝葉斯分類器[J].計算機(jī)仿真.2006.

[5]秦鋒,任詩流等.基于屬性加權(quán)的樸素貝葉斯分類算法[J].計算機(jī)工程與應(yīng)用.2008.

[6]白似雪,梅君,吳穹.一種基于概率加權(quán)的樸素貝葉斯分類.2009.

[7]林士敏,王雙成,陸玉昌.Bayesian 方法的計算學(xué)習(xí)機(jī)制和問題求解[J].清華大學(xué)學(xué)報.2000.

[8]張明衛(wèi),王波,張斌.基于相關(guān)系數(shù)的加權(quán)樸素貝葉斯分類算法[J].東北大學(xué)學(xué)報(自然科學(xué)版).2008.

[9]C.Blake and C.Merz, UCI Repository of Machine Learning Databases. http:// www.ics.uci.edu/～mlearn/ MLRepository.html.1998.

[10]程澤凱,林士敏,陸玉昌.基于 Matlab的貝葉斯分類器平臺MBNC[J].復(fù)旦學(xué)報.2004.