劉牛
安徽工業(yè)大學(xué)計算機(jī)學(xué)院 安徽 243032
分類是數(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)值,實驗證明,這種方法能有效提高分類效果。
每個元組用一個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),然后選擇其中概率最大的類別作為其類別。即樸素貝葉斯分類模型為:
在現(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)行補(bǔ)齊和離散化;
步驟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)完成,并且算法可行。
為了驗證算法的可行性和有效性,用數(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)重,可以獲得更好的分類效果。
本文基于研究條件屬性與決策屬性之間的關(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.