余良俊,甘勝豐,范正薇

(1.湖北第二師范學院 計算機學院,武漢 430205; 2.湖北廣播電視大學 繼續(xù)教育學院,武漢 430074)

0 概述

分類是機器學習中一項非常重要的任務,是當前人工智能領域的熱點研究課題[1]。常見的分類器構造方法有貝葉斯網(wǎng)絡、決策樹、演化算法、人工神經(jīng)網(wǎng)絡、粗糙集與模糊集等[2]。其中,貝葉斯網(wǎng)絡結合統(tǒng)計學、圖論的相關知識,成為機器學習領域研究中最為流行的方法之一[3-4],并廣泛應用于文本分類[5]、風險預警[6]、核密度估計[7]與情感分析[8]等諸多領域。

為了提升分類性能,研究人員提出了很多貝葉斯網(wǎng)絡分類算法,然而學習最優(yōu)的貝葉斯網(wǎng)絡是一個NP-hard問題[9]。樸素貝葉斯網(wǎng)絡模型作為貝葉斯網(wǎng)絡模型中經(jīng)典、簡單且高效的模型,得到了廣泛的研究應用。樸素貝葉斯網(wǎng)絡假設屬性之間是相互獨立的,該假設稱為屬性條件獨立假設。但由于該假設與現(xiàn)實分類問題并不相符,因此影響了樸素貝葉斯網(wǎng)絡的分類性能。目前,對樸素貝葉斯網(wǎng)絡分類算法的改進研究主要圍繞結構擴展[10-11]、屬性加權[12-13]、屬性選擇[14-15]、實例加權[16]以及實例選擇[17]等5個方面進行展開,結構擴展方法通過增加有限的有向邊來擴展樸素貝葉斯網(wǎng)絡的拓撲結構,表達屬性變量之間的依賴關系,削弱樸素貝葉斯網(wǎng)絡的屬性條件獨立假設,提升分類性能[18]。

一依賴估測器(One-Dependence Estimator,ODE)是樸素貝葉斯網(wǎng)絡結構擴展方法中的經(jīng)典模型。文獻[18]提出平均一依賴估測器(Average One-Dependence Estimator,AODE)算法。在該算法中,類變量作為每個屬性節(jié)點的父親節(jié)點,同時把一個屬性變量作為其余所有屬性的父親節(jié)點。TANB(Tree Augmented Naive Bayes)算法[19]以ODE模型為基礎,在屬性變量之間增加了樹結構模型,通過計算屬性之間的條件相互信息來確定樹結構模型。HNB算法[20]可以避免學習貝葉斯網(wǎng)絡拓撲結構,為每個屬性節(jié)點建模,產(chǎn)生隱性的父親節(jié)點,其是一種特殊的ODE模型結構。

以上算法均可提升ODE模型的分類性能,但查閱最新資料發(fā)現(xiàn),現(xiàn)有的ODE模型分類算法在進行分類判別時,認為不同的屬性作為根節(jié)點對應的分類器在分類過程中起到的貢獻是相同的,然而并未考慮不同的屬性作為根節(jié)點時對分類過程的貢獻不同。因此,本文以ODE模型為基礎,采用屬性值加權的方法對ODE模型進行改進,利用相互信息(Mutual Information,MI)計算屬性值對應的權值,并在標準數(shù)據(jù)集上對本文提出的MI-ODE算法的分類性能進行評估。

1 算法的建模與設計

樸素貝葉斯網(wǎng)絡分類算法作為機器學習領域的經(jīng)典算法之一,雖然網(wǎng)絡拓撲結構簡單,但分類效果與其他經(jīng)典的機器學習分類器模型相當,而且分類性能更穩(wěn)定、高效,因此得到了研究人員的廣泛關注。本文用A1,A2,…,Am表示m個屬性變量,待測實例x表示為x=，其中，ai為第i個屬性Ai對應的取值。假設屬性變量個數(shù)為4,樸素貝葉斯網(wǎng)絡的模型結構如圖1所示。從圖1可以看出,樸素貝葉斯網(wǎng)絡中屬性之間是相互獨立的,沒有依賴關系。

圖1 樸素貝葉斯網(wǎng)絡模型結構

利用ODE模型對樸素貝葉斯網(wǎng)絡的結構模型進行擴展,并對所有的屬性都確定一個非類屬性的父親節(jié)點,以此來表達屬性變量間的依賴關系,提升算法的分類精度?，F(xiàn)有的ODE模型分類算法在進行分類判別時,僅對每個ODE模型進行算術平均,并未考慮不同的屬性作為根節(jié)點時，不同的ODE模型對分類過程的貢獻不同。本文將ODE模型與屬性值加權方法相結合,以ODE模型為研究基礎,開展屬性值加權方法研究。在對模型計算權值的過程中,采用MI的度量方式計算屬性值父親節(jié)點與類變量節(jié)點之間的依賴關系,并作為ODE模型的權值。同時,對ODE分類器模型進行屬性值加權平均,并提出MI-ODE算法。本文算法的研究設計分為2個部分:ODE建模和屬性值加權方法研究。

1.1 一依賴估測器模型建模

ODE模型在建模過程中,對每一個屬性節(jié)點構建了一個特殊的樹擴展貝葉斯網(wǎng)絡拓撲結構,每個拓撲結構就是一個ODE分類器，ODE分類器的個數(shù)取決于屬性變量的個數(shù)。在每個ODE模型中,類變量是所有屬性變量的父親節(jié)點。同時，遍歷每個屬性節(jié)點作為父親節(jié)點構建多個樹拓撲結構,在每個樹結構中每個屬性有且僅有一個屬性父親節(jié)點。假設屬性變量個數(shù)為4,AODE模型結構如圖2所示。其中,A1、A2、A3、A4表示4個屬性變量,C表示類變量,其是每個屬性節(jié)點的父親節(jié)點。

圖2 AODE模型結構

在每個ODE模型中,均有一個屬性變量是其余所有屬性的父親節(jié)點。當屬性Ai作為屬性父親節(jié)點時,對應的ODE模型分類器用式(1)進行分類:

(1)

其中,ai為第i個屬性Ai對應的取值,ak表示父親節(jié)點取值為ai時對應的屬性子節(jié)點的取值。類標記c對應類變量取值集合C中的某一個取值。概率P(ai,c)和P(ak|ai,c)的計算方法分別如式(2)、式(3)所示:

(2)

(3)

其中,n為訓練實例的個數(shù),ai為第i個屬性Ai對應的取值,ak表示父親屬性節(jié)點取值為ai時對應的屬性子節(jié)點的取值,ni為第i個屬性的取值個數(shù)。F(ai,c)表示屬性值ai和類標記c同時出現(xiàn)的頻率次數(shù),F(ak,ai,c)表示屬性值ai、屬性值ak和類標記c同時出現(xiàn)的頻率次數(shù)。當有m個屬性變量時,按照圖2的建模方式建立m個ODE模型分類器,即對樸素貝葉斯模型進行m種不同的拓撲結構擴展,并根據(jù)每個ODE模型分類器計算出待測實例的類標記。

1.2 屬性值加權方法研究

MI-ODE算法對ODE模型采取屬性值加權方法進行研究,改變了現(xiàn)有算法對每個ODE模型進行算術平均的現(xiàn)狀。綜合考慮不同屬性作為根節(jié)點時不同ODE模型對分類過程的不同貢獻。本文算法利用相互信息作為信息度量方式,計算屬性值父親節(jié)點和類變量之間的依賴關系,對ODE進行屬性值加權。對依賴關系大的ODE模型分配大權值,同時給依賴關系小的ODE模型分配小權值。屬性值加權的ODE模型結構如圖3所示。其中,A1、A2、A3、A4表示4個屬性變量,類變量C為每個屬性節(jié)點的父親節(jié)點，Wi,ai表示第i個屬性作為父親節(jié)點,且屬性變量的取值為ai時對應ODE模型的權值。

圖3 屬性值加權的ODE模型結構

MI-ODE算法根據(jù)屬性變量對ODE模型進行建模,當有m個屬性變量時,建立m個不同的ODE模型拓撲結構。但與傳統(tǒng)研究方法不同的是,本文MI-ODE算法對每個ODE模型計算了根節(jié)點屬性值的權值,通過計算屬性父親節(jié)點的屬性值與類變量之間的關聯(lián)性來獲取ODE模型權重,再對m個不同的ODE模型進行屬性值加權平均。

在計算分類精度時,對每個ODE模型引入屬性值加權平均,待測實例用式(4)進行分類:

(4)

合理計算ODE模型權重Wi,ai以及合理度量屬性父親節(jié)點的屬性值與類變量之間的關聯(lián)性是本文算法的難點問題。MI-ODE算法在計算權重的過程中,采用相互信息作為度量方式來計算某一屬性值作為根節(jié)點時對應的ODE模型權重。相互信息在信息論中常用來度量2個變量之間的依賴程度,表示2個變量之間的共同信息量[21-22]。屬性變量Ai和類變量C之間的相互信息則定義為:

(5)

其中,相互信息MI(Ai;C)度量了屬性變量Ai對類變量C的依賴程度,可以反映屬性變量Ai在分類過程中的重要性,且其值越大,在分類過程中對應的作用越大。

在本文算法中,需要計算當屬性父親節(jié)點Ai取值為ai時,與其對應的ODE模型的權值Wi,ai。Wi,ai表示屬性值ai和類變量C之間的依賴關系。根據(jù)相互信息度量可得:

(6)

當有m個屬性變量時,即可根據(jù)式(6)計算出m個不同的ODE模型對應的權值,再根據(jù)式(4)對每個ODE模型進行屬性值加權平均來求取待測實例的類標記。

本文提出的MI-ODE算法具體步驟為:

輸入訓練數(shù)據(jù)集D,測試實例x

輸出測試實例x的類標記

步驟1當有m個屬性變量時,建立m個不同的ODE模型拓撲結構。

1)對每個屬性父親節(jié)點的屬性值ai和每個類標記c,根據(jù)式(2)計算P(ai,c)。

2)對每個屬性父親節(jié)點Ai對應的屬性子節(jié)點對應的每個屬性值ak(k≠i),根據(jù)式(3)計算P(ak|ai,c)。

3)對m個不同的ODE模型拓撲結構,根據(jù)屬性父親節(jié)點的屬性值ai,根據(jù)式(6)計算對應的ODE模型的權值。

步驟2根據(jù)式(4)計算測試實例x的類標記。

步驟3返回測試實例x對應的類標記。

2 實驗設計與分析

2.1 實驗數(shù)據(jù)與實驗平臺

本文研究將借助國際數(shù)據(jù)挖掘WEKA實驗平臺以及Eclipse軟件進行。實驗數(shù)據(jù)集來源于由加州大學歐文分校經(jīng)過精心挑選用于現(xiàn)實分類問題的36個UCI標準數(shù)據(jù)集。數(shù)據(jù)集來源于現(xiàn)實生活中的分類問題,且包含的實例數(shù)眾多。不同的數(shù)據(jù)集包含的實例數(shù)和類標記的數(shù)量各不相同,因此該數(shù)據(jù)集在國際數(shù)據(jù)挖掘領域具有較強的代表性。

由于相關數(shù)據(jù)挖掘算法只能對名詞性屬性進行處理,因此首先需要對36個UCI標準數(shù)據(jù)集進行預處理。本文對數(shù)據(jù)集的預處理包括采用WEKA實驗平臺的無導師過濾器Replace Missing Values替換缺失值,有導師過濾器Discretize對數(shù)值型數(shù)據(jù)進行離散,以及無監(jiān)督過濾器Remove對無用屬性進行刪除等操作。

2.2 實驗設計與結果分析

以預處理后的36個UCI標準數(shù)據(jù)集為研究對象,借助WEKA實驗平臺以及Eclipse軟件完成實驗。實驗比較了MI-ODE算法、NB算法、AODE算法以及TAN算法的分類性能。為了更準確地評估本文提出的MI-ODE算法的分類性能,對所有算法均設置了相同的數(shù)據(jù)集、相同的實驗平臺以及相同的評估方法,且實驗均采用10次十折交叉驗證法,并采用置信度為95%的t-test統(tǒng)計測試方法[23]對算法的分類精度以及AUC[24]指標進行分析比較。4種算法的分類精度結果如表1所示,AUC指標結果如表2所示。其中,表1和表2中的w/t/l值是指MI-ODE算法相對于其他算法,在置信度為95%的t-test統(tǒng)計測試方法下得到的比較結果。w表示MI-ODE算法的分類精度高于其他算法的實例集總數(shù)量,t表示MI-ODE算法的分類精度與其他算法相等的實例集總數(shù)量,l表示MI-ODE算法的分類精度低于其他算法的實例集總數(shù)量。

表1 4種算法的分類精度對比

表2 4種算法的AUC對比

從表1可以看出,MI-ODE算法的平均分類精度最高,為86.49%。相較于NB算法,MI-ODE算法在15個數(shù)據(jù)集上的分類精度有明顯提升;相較于AODE算法、TAN算法,MI-ODE算法均在9個數(shù)據(jù)集上的分類精度有明顯提升;相較于NB算法,MI-ODE算法在數(shù)據(jù)集letter上的分類精度提升了17.63%,提升效果非常顯著,這說明相較于其他算法,本文提出的MI-ODE算法的分類精度性能最優(yōu)。

從表2可以看出,MI-ODE算法的平均AUC指標最高,為93.88%。相較于NB算法,MI-ODE算法在16個數(shù)據(jù)集上的AUC指標有明顯提升;相較于AODE算法,MI-ODE算法在9個數(shù)據(jù)集上的AUC指標有明顯提升;相較于TAN算法,MI-ODE算法在11個數(shù)據(jù)集上的AUC指標有明顯提升;相較于NB算法,MI-ODE算法在數(shù)據(jù)集vehicle上的AUC指標提升了6.11%,提升效果非常顯著,這說明相較于其他算法,本文提出的MI-ODE算法的AUC指標性能最優(yōu)。

綜上所述,相比于NB算法、AODE算法以及TAN算法,本文提出的MI-ODE算法的分類精度和AUC均有所改進,且分類性能最優(yōu)。

3 結束語

為解決現(xiàn)有ODE模型未考慮到不同屬性作為根節(jié)點時對分類過程貢獻不同的問題,本文提出基于相互信息的屬性值加權MI-ODE算法。實驗結果表明,MI-ODE算法提升了樸素貝葉斯網(wǎng)絡分類算法以及ODE模型經(jīng)典算法的分類性能。后續(xù)將繼續(xù)以樹擴展的樸素貝葉斯模型為基礎,對貝葉斯網(wǎng)絡分類算法進行改進。