劉牛

安徽工業(yè)大學計算機學院 安徽 243032

0 前言

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

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中的訓練樣本數(shù)，而 s 是訓練樣本總數(shù)。

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

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

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

2 屬性加權樸素貝葉斯分類算法

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

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

由于權值的范圍介于0和1之間，則設定權值為：

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

設條件屬性C和決策屬性D的互信息，記為：因此可以得出條件屬性i C的權值為：

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

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

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

步驟2 分類器的建構。

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

步驟2.2 生成分類器網(wǎng)絡結構，并對其進行參數(shù)學習。

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

步驟3 計算權值。

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

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

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

步驟4 分類評估。通過對屬性給予不同的權值，得出分類結果。

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

3 實驗結果及分析

為了驗證算法的可行性和有效性，用數(shù)據(jù)集對算法進行了測試。實驗數(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ù)屬性值均進行離散化處理。實驗在MBNC(Bayesian Networks Classifier using Matlab)平臺下完成。首先對數(shù)據(jù)集進行隨機攪亂，打亂數(shù)據(jù)之間原先的排列順序，并對數(shù)據(jù)集采取5疊交叉驗證。每個數(shù)據(jù)集輪流實驗5次，取5次實驗的平均值作為實驗的測試結果。表1為經過預處理后的數(shù)據(jù)集情況。

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

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

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

由表2可知：

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

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

4 結束語

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

[1]秦鋒,楊波,程澤凱.分類器性能評價標準研究[J].計算機技術與發(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]程克非,張聰.基于特征加權的樸素貝葉斯分類器[J].計算機仿真.2006.

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

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

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

[8]張明衛(wèi),王波,張斌.基于相關系數(shù)的加權樸素貝葉斯分類算法[J].東北大學學報(自然科學版).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].復旦學報.2004.