屬性值加權的一依賴估測器模型分類算法研究

余良俊,甘勝豐,范正薇

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

0 概述

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

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

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

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

1 算法的建模與設計

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

圖1 樸素貝葉斯網絡模型結構

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

1.1 一依賴估測器模型建模

ODE模型在建模過程中,對每一個屬性節(jié)點構建了一個特殊的樹擴展貝葉斯網絡拓撲結構,每個拓撲結構就是一個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ù)集來源于由加州大學歐文分校經過精心挑選用于現(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算法提升了樸素貝葉斯網絡分類算法以及ODE模型經典算法的分類性能。后續(xù)將繼續(xù)以樹擴展的樸素貝葉斯模型為基礎,對貝葉斯網絡分類算法進行改進。