基于貝葉斯方法的決策樹分類算法

1、收稿日期:2005-06-06;修訂日期:2005-08-14作者簡介:樊建聰(1977-,男,山東青島人,助教,碩士,主要研究方向:人工智能應(yīng)用、數(shù)據(jù)挖掘算法;張問銀(1972-,男,山東臨沂人,講師,博士,主要研究方向:圖像信息安全;梁永全(1967-,男,山東聊城人,教授,博士生導(dǎo)師,主要研究方向:人工智能理論及應(yīng)用、數(shù)據(jù)庫、多媒體.文章編號:1001-9081(200512-2882-03基于貝葉斯方法的決策樹分類算法樊建聰1,張問銀2,梁永全1(1.山東科技大學(xué)信息科學(xué)與工程學(xué)院,山東青島266510;2.臨沂師范學(xué)院計算機(jī)系,山東臨沂276005(howdoyoudo07yahoo

2、 摘要:針對數(shù)據(jù)挖掘的特點(diǎn)和本質(zhì),充分利用貝葉斯方法和決策樹分類的優(yōu)點(diǎn),將貝葉斯的先驗信息方法與決策樹分類的信息增益方法相結(jié)合,提出了一種新的數(shù)據(jù)挖掘分類算法(BD1.0算法,并對此算法進(jìn)行了設(shè)計和分析。實(shí)驗分析表明,該算法可以處理不一致或者不完整數(shù)據(jù)等“臟數(shù)據(jù)”,比單純使用貝葉斯方法或決策樹方法具有更高的準(zhǔn)確率,而且與C4.5算法具有近似的時間復(fù)雜度。關(guān)鍵詞:數(shù)據(jù)挖掘;分類;貝葉斯原理;決策樹中圖分類號:TP301.6文獻(xiàn)標(biāo)識碼:AD ec isi on tree cl a ssi f i ca ti on a lgor ith m ba sed on Bayesi a n m ethodF

3、 AN J ian 2cong 1,Z HANG W en 2yin 2,L I A NG Yong 2quan1(1.College of Infor m ation Science and Technology,Shandong U niversity of Science and Technology,Q ingdao Shandong 266510,China;2.D epart m ent of Co m puter ,L inyi N or m al U niversity,L inyi Shandong 276005,China Abstract:According t o th

4、e characteristic and essence of data m ining and taking advantage of Bayesian method,a ne w classificati on method na med BD1.0algorith m was p resented .This method combined the p ri or inf or mati on and infor mati on gain method of decisi on tree .The design and analysis of the algorith m was int

5、r oduced t oo .The experi m ent results show that the algorith m can deal with dirty data such as incomp lete data or inconsistent data,and it is more accurate than only useing Bayesian method or decisi on tree .It has app r oxi m ate ti m e comp lexity with C4.5algorith m.Key words:data m ining;cla

6、ssificati on;Bayesian p rinci p le;decisi on tree1分類方法及算法概述分類是數(shù)據(jù)挖掘的任務(wù)之一。分類就是找出一個類別的概念描述,它代表了這類數(shù)據(jù)的整體信息,即該類的內(nèi)涵描述,并用這種描述來構(gòu)造模型,一般用規(guī)則或決策樹模式表示。分類利用訓(xùn)練數(shù)據(jù)集通過一定的算法而求得分類規(guī)則,可被用于規(guī)則描述和預(yù)測。分類的目的是通過一定的學(xué)習(xí)獲取一個分類函數(shù)或分類模型(也常稱作分類器,該模型能把數(shù)據(jù)集中的數(shù)據(jù)項映射到給定類別中的某一個1。要構(gòu)造分類器,需要有一個訓(xùn)練樣本數(shù)據(jù)集作為輸入。訓(xùn)練集由一組數(shù)據(jù)庫記錄或元組構(gòu)成,每個元組是一個由有關(guān)字段(又稱屬性或特征值組成的

7、特征向量。此外,訓(xùn)練樣本還有一個類別標(biāo)記。一個具體樣本的形式可為(v 1,v 2,v n ;c ,其中v i 表示屬性值,c 表示類別。目前,分類器的構(gòu)造方法有多種,應(yīng)用比較廣泛的有決策樹方法、統(tǒng)計方法、機(jī)器學(xué)習(xí)方法、神經(jīng)網(wǎng)絡(luò)方法、遺傳算法、粗糙集以及模糊邏輯等2。不同的分類方法有不同的特點(diǎn)。通常,有三種對分類方法評價或比較的尺度:1分類結(jié)果的準(zhǔn)確度。它是用得最多的一種比較尺度,特別是對于預(yù)測型分類任務(wù);2分類計算的速度。計算速度依賴于具體的實(shí)現(xiàn)細(xì)節(jié)和硬件環(huán)境,在數(shù)據(jù)挖掘中,由于操作對象是海量數(shù)據(jù),因此空間和時間的復(fù)雜度問題將是非常重要的一個環(huán)節(jié);3分類器對各種類型數(shù)據(jù)集的適應(yīng)度。由于所分析的

8、數(shù)據(jù)對象中,可能會存在不完整數(shù)據(jù)、噪聲數(shù)據(jù)或不一致數(shù)據(jù),或者數(shù)據(jù)的分布是稀疏的,因此一個好的分類器能夠?qū)Ω鞣N類型的數(shù)據(jù)集有較強(qiáng)的適應(yīng)能力。統(tǒng)計方法主要有最近鄰歸類、基于事例的學(xué)習(xí)等,這些方法本質(zhì)上是基于某種距離進(jìn)行相應(yīng)變換,得到具有另外一些參數(shù)的分類公式。統(tǒng)計學(xué)上主要用的基本距離公式有絕對值距離、歐氏距離、明斯基距離等。無論哪種基于距離的分類器,都需要對數(shù)據(jù)集中的所有數(shù)據(jù)進(jìn)行兩兩檢測,以確定一條記錄是否與另一條記錄在同一類別中,如果數(shù)據(jù)量非常大,這種檢測將很耗時,因為每個數(shù)據(jù)都必須進(jìn)行兩次計算。神經(jīng)網(wǎng)絡(luò)方法對數(shù)據(jù)集中的噪聲數(shù)據(jù)有很好的處理性能,而且即使數(shù)據(jù)未經(jīng)訓(xùn)練,也能發(fā)現(xiàn)對數(shù)據(jù)的分類模式。但

9、是神經(jīng)網(wǎng)絡(luò)在運(yùn)行時需要大量參數(shù),這必然會增加人為地干預(yù),致使分類速度和分類器的適應(yīng)度差。遺傳算法、粗糙集等方法是基于規(guī)則的方法,這種方法都有一個共同的問題,就是對于連續(xù)數(shù)據(jù)會形成明顯的截斷面。這種截斷面可能會把一些屬于同一類別A 的數(shù)據(jù)分到兩個不同的類別A 和B 中,其中B 是與A 相鄰近的類別。決策樹3分類算法中應(yīng)用比較廣泛的是I D 算法和C4.5、C5.0算法4,5等,基于決策樹的分類算法的一個最大的優(yōu)點(diǎn),同時也是最大的缺點(diǎn)是它在學(xué)習(xí)過程中不需要使用第25卷第12期2005年12月計算機(jī)應(yīng)用Computer App licati onsVol .25No .12Dec .2005者了解很

10、多背景知識,只要訓(xùn)練樣本能夠用屬性結(jié)論式的方式表達(dá)出來即可。而在某些情況下,某些數(shù)據(jù)在分類時,需要考慮與它們相關(guān)的背景知識,尤其是一些類屬不是很明顯的數(shù)據(jù),這對于分類的精度和準(zhǔn)確度是很重要的。2貝葉斯方法與決策樹方法2.1貝葉斯方法貝葉斯方法的關(guān)鍵是使用概率表示各種形式的不確定性。在選擇某事件面臨不確定性時,在某一時刻假定此事件會發(fā)生的概率,然后根據(jù)不斷獲取的新的信息修正此概率。修正之前的概率稱為先驗概率,修正之后的概率稱為后驗概率。貝葉斯原理就是根據(jù)新的信息從先驗概率得到后驗概率的一種方法。通常用下面的式子表示貝葉斯原理5:P (k|a =P (a |k P (k nj =1P (a |j

11、P (j 其中,j 表示一個特定的事件;a 表示某一行動;P (k (k =1,2,n 是先驗概率;先驗概率通過對條件概率P (a|k加權(quán)平均的計算后,得到后驗概率P (k|a 。設(shè)某樣本數(shù)據(jù)集中每個變量的特征向量為X =(x 1,x 2,x n ,類別向量為C =(c 1,c 2,c l 。分類的目的6是把特征向量X 歸入到某個類別c i (i 1,2,l中。于是可以選擇后驗概率最大的類別,即P (c i |X >P (c j |X ,其中i,j 1,2,l。2.2決策樹決策樹分類是以實(shí)例為基礎(chǔ)的歸納分類算法,它主要從一組無次序、無規(guī)則的事例中推理出決策樹表示形式的分類規(guī)則,并采用自頂

12、向下的遞歸方式,在決策樹的內(nèi)部節(jié)點(diǎn)之間進(jìn)行屬性值的比較,在節(jié)點(diǎn)內(nèi)部進(jìn)行屬性的選擇,根據(jù)不同的屬性值判斷從節(jié)點(diǎn)向下的分支,在決策樹的葉節(jié)點(diǎn)得出結(jié)論。如圖1所示是一棵決策樹 。圖1決策樹圖1中,葉節(jié)點(diǎn)L i 表示類別,n i 表示對某個屬性值的測試,cond ij 表示測試條件。每一個類別可表示為節(jié)點(diǎn)的合取,所有類別可表示為葉節(jié)點(diǎn)的析取,即:L i =n i 1n i 2n ik ,i =1,2,C =L 1L 2L t ,t =1,2,2.3貝葉斯決策樹定義貝葉斯決策樹在原有決策樹T 的基礎(chǔ)上,在T 中加入新的節(jié)點(diǎn),此節(jié)點(diǎn)位于T 的兩個屬性測試節(jié)點(diǎn)之間,能夠根據(jù)貝葉斯原理進(jìn)行函數(shù)計算,稱之為貝葉

13、斯節(jié)點(diǎn),具有這樣節(jié)點(diǎn)的決策樹稱作貝葉斯決策樹 。圖2貝葉斯決策樹貝葉斯決策樹結(jié)構(gòu)如圖2所示。貝葉斯節(jié)點(diǎn)分為兩部分,分別是0值和f 值。0值表示此節(jié)點(diǎn)不進(jìn)行任何計算,直接根據(jù)條件轉(zhuǎn)向下一屬性測試節(jié)點(diǎn);f 值表示需要計算函數(shù)f 的值,這里的函數(shù)f 可以是樸素貝葉斯公式,也可以是其他貝葉斯公式,針對具體情況而定。也就是說,如果貝葉斯節(jié)點(diǎn)需要f 值,則下一個屬性節(jié)點(diǎn)的選擇依賴于兩點(diǎn):(1屬性測試條件;(2函數(shù)f 的值。這兩部分進(jìn)行下一屬性節(jié)點(diǎn)的選取時,都采用IF THEN 的形式,即:IF THEN IF f 取某個值THEN 3算法的設(shè)計及其分析3.1算法設(shè)計根據(jù)上面對分類問題的介紹與分析,可以設(shè)計

14、使用貝葉斯方法的一種分類算法BD1.0。此算法的基本思想是:(1對于能夠用信息增益方法確切選擇某個屬性的分支,選取貝葉斯節(jié)點(diǎn)的0或f 值。其中信息增益的計算方法2為:設(shè)集合S,要把S 中的數(shù)據(jù)樣本分到m 個不同類別C i(i =1,2,m 中,且s i 是類別C i 中的樣本個數(shù),則一個給定樣本集的期望值是:I (s 1,s 2,s m =-p ilog2(p i (1其中p i =s i/|S |。設(shè)屬性A 具有v 個不同的值a 1,a 2,a v ,用屬性A 將S 劃分為v 個子集S 1,S 2,S v ,其中S j 包含S 中的這樣一些樣本,它們在A 上具有值a j 。設(shè)s ij 是子集

15、S j 中類C i 的樣本數(shù),則由A 劃分成子集的期望信息值是:E (A =(s1j+s m j /|S |I (s 1j,sm j(2其中,I (s 1j ,s m j =-pijlog 2(p ij ,p ij =s ij/|S j|。由式(1和(2可得信息增益值Ga in (A 為:Ga in (A =I (s 1,s 2,s m -E (A (2對于無法確定其分類類別的數(shù)據(jù)對象,或者屬性值丟失的屬性,選取f 值。函數(shù)f 的選取主要依據(jù)經(jīng)驗知識或者以前的實(shí)驗結(jié)果確定其先驗概率,根據(jù)概率判斷先將其分到哪些類中,然后利用貝葉斯方法進(jìn)行處理,確定后驗概率,選取后驗概率最大的那一類,此類即為數(shù)據(jù)

16、對象所屬的類別。根據(jù)上述分析,BD1.0算法描述如下:算法:使用貝葉斯方法的BD1.0算法Input:給定一個數(shù)據(jù)集X 1,X 2,X n ,其中每個X i具有一個或多個屬性X ij (i,j =1,2,n,;Output:對輸入的數(shù)據(jù)集X 1,X 2,X n ,已劃分到各相關(guān)的類別L j 中。顯示或打印出各類數(shù)據(jù)。(1確定要生成的類的數(shù)目k 和各類別L j (j =1,2,k ,L j 的確定依據(jù)事先給定的類的特征或?qū)傩?(2使用信息增益方法首先確定要對哪個屬性先進(jìn)行判斷,確定要進(jìn)行分類的數(shù)據(jù)X i (i =1,2,的某個或某些屬性,屬性值與相應(yīng)的類相關(guān);(3IF 屬性選擇無二義性and 數(shù)

17、據(jù)分類無二義性THEN 貝葉斯節(jié)點(diǎn)選取0值ELSE 轉(zhuǎn)(4;3882第12期樊建聰?shù)?基于貝葉斯方法的決策樹分類算法(4按某種原則對Xi 進(jìn)行分類,若Xi確定對應(yīng)某一類別Lj,則將X i劃分到此類;否則,若X i不能確定分到某一類別,而是與某些類都相關(guān),則根據(jù)先驗信息P(Lj先把它置入某一類,然后根據(jù)計算出的P(Xi|L j和P(X i來計算后驗概率。若是根據(jù)Xi的m個屬性進(jìn)行分類,并且屬性之間是獨(dú)立的,則將Xi 劃分為Xi1,Xi2,X i m,于是P(X i|L j可表示為如下的乘積公式:P(Xi1|Lj×P(Xi2|Lj××P(Xi m|Lj從而可計算出后驗

18、概率:P(Lj|X i=P(LjP(Ximj=1P(Xij|L j其中P(Lj 表示Xi屬于Lj類的概率,表示先驗信息。選取根據(jù)此式計算出的后驗概率值最大的點(diǎn)劃分到類別L j中;(5選取貝葉斯節(jié)點(diǎn)的f值,且f=P(Lj|X i;(6轉(zhuǎn)到(3。3.2算法分析BD1.0算法具有與其他決策樹分類算法相似的優(yōu)點(diǎn):(1產(chǎn)生的分類規(guī)則易于理解。決策樹每個分支的節(jié)點(diǎn)的合取都對應(yīng)一個分類規(guī)則,決策樹分類算法最后可輸出一個類別規(guī)則集,即樹葉節(jié)點(diǎn)的析取式。(2分類速度相對較快,最壞時間復(fù)雜度為O(n3。BD1.0算法主要進(jìn)行兩項工作, 即判斷是否要計算f值和是否要計算屬性的后驗概率值,而在最壞情況下,根據(jù)算法第(

19、3步的判斷,需要計算所有數(shù)據(jù)的后驗概率值。設(shè)共有n個數(shù)據(jù),每個數(shù)據(jù)有m個屬性,需要把這些數(shù)據(jù)分配到k個類別中,并且假設(shè)計算一個數(shù)據(jù)的后驗概率值需要時間1,計算一次信息增益值需要時間2,則最壞情況下此算法的計算時間為:(1+m2nk=nk1+m n2當(dāng)m=n=k時,計算時間為n21+n32,即最壞時間復(fù)雜度為O(n3。BD1.0算法獨(dú)具的優(yōu)點(diǎn):(1分類的精度更高。對于用信息增益計算不能確定的屬性選取,可通過貝葉斯方法解決。分類一般按照數(shù)據(jù)的某個或某些屬性進(jìn)行,假設(shè)某數(shù)據(jù)有兩個需要計算信息增益值的屬性A1和A2,如果其增益值Ga in(A1和Ga in(A2,則屬性的選擇出現(xiàn)二義性,如果大量的數(shù)據(jù)

20、具有這種二義性,則必然會影響數(shù)據(jù)的分類精度和準(zhǔn)確率。BD1.0算法通過貝葉斯方法利用先驗信息,可以對這種情況作很好地處理。(2分類的魯棒性更強(qiáng)。BD1.0算法能夠更好地處理不一致、不完整和噪聲等干擾數(shù)據(jù)。數(shù)據(jù)挖掘處理的是海量數(shù)據(jù),由于主觀和客觀原因,在這些數(shù)據(jù)中不可避免的存在非正常數(shù)據(jù)。解決這類問題可以使用數(shù)據(jù)預(yù)處理方法2,但這種解決方法十分耗時;也可以使用貝葉斯方法,根據(jù)對數(shù)據(jù)歷史信息和專家的經(jīng)驗來消除不一致數(shù)據(jù),平滑不完整數(shù)據(jù),排除噪聲數(shù)據(jù)等。4算法的驗證取一組平面掃描數(shù)據(jù),利用BD1.0算法從這些數(shù)據(jù)中找出平面上的點(diǎn)和異常點(diǎn)。部分?jǐn)?shù)據(jù)列于表1中。表1中的數(shù)據(jù)有5列,其中I D是數(shù)據(jù)序號,

21、每一個數(shù)據(jù)有4個屬性,分別用A ttri1、A ttri2、A ttri3、A ttri4表示,其中A ttri2列中存在空值和缺失值。表1部分實(shí)驗數(shù)據(jù)表I D A ttri1A ttri2A ttri3A ttri41 1.3301810.117200882 1.7892210.517200933 2.3312810.917200984 3.4003011.3172011216023.504NULL119.3172129116123.456119.7172129516523.672126121.3172131016623.64082121.7172131417020.40033123.317

22、21329首先將所有數(shù)據(jù)分為兩大類,即平面數(shù)據(jù)集類和異常數(shù)據(jù)集類,然后計算屬性的信息增益值,得:Ga in(A ttri1=0.35,Ga in(A ttri2=0.5,Ga in(A ttri3 =0.72,Ga in(A ttri4=0.11由于A ttri3的信息增益值最大,先按A ttri3進(jìn)行分類。A ttri3中有不完全的屬性數(shù)據(jù)值,則按Bayes方法進(jìn)行計算,再進(jìn)行分類。這樣將這組數(shù)據(jù)分類后的結(jié)果如圖3所示。圖3對數(shù)據(jù)分類后的結(jié)果5結(jié)語使用貝葉斯方法最有爭議之處就是先驗信息的使用。先驗信息來源于經(jīng)驗或者以前的實(shí)驗結(jié)論,沒有確定的理論依據(jù)作支持,因此在很多方面頗有爭議。但是大量事實(shí)表明,對于大型數(shù)據(jù)集,貝葉斯分類表現(xiàn)出高準(zhǔn)確率和運(yùn)算的高速度。參考文獻(xiàn):1高洪深.決策支持系統(tǒng)理論方法案例M.第2版.北京:清華大學(xué)出版社,2000.56-89.2HAN