楊立洪 葉成達(dá)

摘 要：為了彌補(bǔ)傳統(tǒng)樸素貝葉斯分類器在實(shí)際應(yīng)用中代價(jià)不敏感的缺點(diǎn)，基于最小風(fēng)險(xiǎn)準(zhǔn)則構(gòu)建樸素貝葉斯模型和樹(shù)增強(qiáng)樸素貝葉斯網(wǎng)模型，通過(guò)預(yù)先設(shè)置損失矩陣，分類器可以區(qū)分各種誤判情形產(chǎn)生的代價(jià)，利用1 000條德國(guó)信用卡樣本數(shù)據(jù)進(jìn)行實(shí)驗(yàn)。研究發(fā)現(xiàn)，在以損失最小為導(dǎo)向的用戶信用評(píng)估方面，基于最小風(fēng)險(xiǎn)準(zhǔn)則構(gòu)建分類器產(chǎn)生的總損失更小，綜合性能更好；在分類性能上，簡(jiǎn)單的樸素貝葉斯模型可與復(fù)雜的基于爬山算法建立的貝葉斯網(wǎng)絡(luò)模型相媲美；從整體經(jīng)濟(jì)效益看，樸素貝葉斯模型更勝一籌。

關(guān)鍵詞：樸素貝葉斯；樹(shù)增強(qiáng)樸素貝葉斯網(wǎng)；代價(jià)敏感；最小風(fēng)險(xiǎn)準(zhǔn)則；爬山算法

DOI：10.11907/rjdk.171519

中圖分類號(hào)：TP319

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-7800（2018）006-0146-04

Abstract：In order to make up for the shortcoming that the traditional Naive Bayes is not sensitive in the practical application， Naive Bayes and Tree augmented naive Bayesian network are established based on the minimum risk criterion. By pre-setting the loss matrix， the classifier can distinguish the costs of various miscarriages.1 000 German credit card samples were used for experiments. Experiment results have shown that the classifier based on the minimum risk criterion produces less total loss and better overall performance in the least-cost-oriented user credit evaluation. In terms of classification performance， the simple Naive Bayesian model can be compared with the complex Bayesian network model based on the hill-climbing algorithm. The Naive Bayes model is superior in the overall economic efficiency.

Key Words：Naive Bayes； tree augmented naive bayesian network； cost sensitive； minimum risk criterion； hill climbing algorithm

0 引言

貝葉斯網(wǎng)絡(luò)是貝葉斯方法與圖形理論的有機(jī)結(jié)合[1]。1986年P(guān)earl首次在專家系統(tǒng)中引進(jìn)了貝葉斯網(wǎng)絡(luò)[2]。貝葉斯網(wǎng)由于在理論上具有嚴(yán)格性和一致性，能直觀表達(dá)圖形化知識(shí)等特點(diǎn)，已經(jīng)成為人工智能領(lǐng)域的研究熱點(diǎn)。貝葉斯網(wǎng)的學(xué)習(xí)包括構(gòu)建有向無(wú)環(huán)圖的學(xué)習(xí)、結(jié)構(gòu)學(xué)習(xí)及每個(gè)變量局部條件概率分布的學(xué)習(xí)即參數(shù)學(xué)習(xí)。貝葉斯網(wǎng)本身是一種不定性因果關(guān)聯(lián)模型，具有強(qiáng)大的不確定性推理能力，利用條件概率表示各變量間的相關(guān)性。樸素貝葉斯分類器基于一個(gè)簡(jiǎn)單的假設(shè)：在給定分類特征條件下屬性值之間條件是相互獨(dú)立的。在現(xiàn)實(shí)世界中，它的屬性獨(dú)立性假設(shè)使其無(wú)法表示實(shí)際應(yīng)用中各屬性之間的依賴關(guān)系，影響了分類性能。因此，針對(duì)實(shí)際應(yīng)用對(duì)樸素貝葉斯分類模型進(jìn)行改進(jìn)，使之在屬性獨(dú)立性假設(shè)不滿足的條件下依然具有較高分類精度。由于“樸素貝葉斯假設(shè)”在實(shí)際中往往不成立，因此對(duì)樸素貝葉斯分類器的改進(jìn)，一般從放松樸素貝葉斯假設(shè)入手，當(dāng)屬性間存在依賴時(shí)，采用合適的方法對(duì)分類器結(jié)構(gòu)進(jìn)行修正。隱藏樸素貝葉斯[3]考慮屬性間的依賴關(guān)系，并采用條件互信息進(jìn)行計(jì)算。樹(shù)增強(qiáng)樸素貝葉斯（Tree Augmented Naive Bayesian Classifier， TAN分類器）假設(shè)在貝葉斯網(wǎng)中，每個(gè)屬性除了有類別屬性作為父節(jié)點(diǎn)外，還可以有至多一個(gè)其它屬性作為父節(jié)點(diǎn)，所有屬性節(jié)點(diǎn)可以構(gòu)成一個(gè)最大支撐樹(shù)。TAN模型通過(guò)發(fā)現(xiàn)屬性對(duì)之間的依賴關(guān)系放松樸素貝葉斯中任意屬性之間獨(dú)立的假設(shè)[4]。貝葉斯網(wǎng)的結(jié)構(gòu)學(xué)習(xí)一般需要考慮模型選擇和模型優(yōu)化兩個(gè)方面[5]。模型選擇決定了評(píng)判不同模型優(yōu)劣的準(zhǔn)則，而模型優(yōu)化則是把最優(yōu)模型結(jié)構(gòu)找出來(lái)。1992年Cooper等[6]發(fā)現(xiàn)基于爬山搜索算法和貝葉斯評(píng)分準(zhǔn)則的經(jīng)典K2算法效果良好；1994年Remeo[7]提出K3算法，使用MDL評(píng)分函數(shù)進(jìn)行貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)；1995年Chickering等[8]將模擬退火算法應(yīng)用于貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)中；Gamez等[9]應(yīng)用爬山算法進(jìn)行貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)。本文根據(jù)實(shí)際應(yīng)用中的具體情況，通過(guò)建立貝葉斯網(wǎng)模型解決信用系統(tǒng)中常見(jiàn)的用戶信用評(píng)估問(wèn)題。傳統(tǒng)的樸素貝葉斯模型不具有代價(jià)敏感特性，這一缺點(diǎn)使得模型輸出產(chǎn)生較高的經(jīng)濟(jì)損失?？紤]代價(jià)的分類學(xué)習(xí)稱為代價(jià)敏感學(xué)習(xí)[10]。Maloof[11]提出了處理不平衡數(shù)據(jù)集中類別誤判代價(jià)不相等且不確定的解決方案。Elkan[12]詳細(xì)介紹了代價(jià)敏感分類決策的基本概念，并通過(guò)實(shí)驗(yàn)證實(shí)了改變訓(xùn)練正負(fù)樣本的比例對(duì)最終分類效果影響不大。在實(shí)際數(shù)據(jù)挖掘應(yīng)用中，存在許多在線分類問(wèn)題，Wang等[13]利用在線梯度下降算法的思想，提出了代價(jià)敏感學(xué)習(xí)在線分類算法。在信用評(píng)估中，如果把信用良好的客戶誤判為信用差的客戶固然會(huì)使銀行損失一筆收益，但如果將原本信用差的客戶錯(cuò)判為信用良好，就會(huì)造成更大損失。 顯然這兩種不同的錯(cuò)誤判斷所造成損失的嚴(yán)重程度是有顯著差別的，后者的損失比前者更嚴(yán)重。本文在傳統(tǒng)的貝葉斯網(wǎng)模型中加入代價(jià)敏感學(xué)習(xí)，使得最終模型輸出產(chǎn)生的總損失有所減小，以提高分類器的綜合性能。

1 數(shù)據(jù)集

本文以德國(guó)信用卡數(shù)據(jù)為例，在R數(shù)據(jù)分析軟件工作環(huán)境下進(jìn)行實(shí)證分析。原始數(shù)據(jù)集中共有1 000個(gè)樣本、21個(gè)變量指標(biāo)。數(shù)據(jù)中混有連續(xù)數(shù)據(jù)和離散數(shù)據(jù)，為了滿足軟件的輸入，對(duì)21個(gè)變量指標(biāo)進(jìn)行處理，包括離散化處理和變量分解處理（性別與婚姻狀況變量marital分解為性別sex和婚姻狀況marriage兩個(gè)變量），最后得到22個(gè)變量指標(biāo)。部分變量說(shuō)明如表1所示。

2 樸素貝葉斯與樹(shù)增強(qiáng)樸素貝葉斯網(wǎng)算法理論

2.1 基于最大后驗(yàn)概率準(zhǔn)則的樸素貝葉斯模型算法

3 算法實(shí)驗(yàn)與結(jié)果

3.1 基于最大后驗(yàn)概率準(zhǔn)則的信用評(píng)估模型實(shí)驗(yàn)

該處類別變量為信用級(jí)別變量指標(biāo)good_bad，可取值為good和bad，分別有700和300個(gè)。根據(jù)1 000個(gè)樣本，采用10折交叉檢驗(yàn)方法進(jìn)行計(jì)算，最后通過(guò)計(jì)算10次平均誤分率和總損失評(píng)價(jià)模型性能，其中模型總損失是根據(jù)損失矩陣計(jì)算出來(lái)的?；谧畲蠛篁?yàn)概率準(zhǔn)則的損失矩陣：

其中：c-12=1表示把原本信用好的客戶判為信用不好的客戶，損失1個(gè)單位；c-21=1表示把原本為信用不好的客戶判為信用好的客戶（造成更大損失），損失1個(gè)單位。采用10折交叉檢驗(yàn)方法，會(huì)得到10個(gè)混淆矩陣，混淆矩陣的形式為：

其中，a表示類別變量good_bad取值為bad（共有a+c個(gè)）時(shí)，有a個(gè)模型輸出為bad，c則表示有c個(gè)模型輸出為good；b表示類別變量good_bad取值為good（共有b+d個(gè)）時(shí)，有b個(gè)模型輸出為good，d則表示有d個(gè)模型輸出為bad。

最大后驗(yàn)概率準(zhǔn)則樸素貝葉斯模型信用評(píng)估的效果見(jiàn)表2。

最大后驗(yàn)概率準(zhǔn)則TAN模型信用評(píng)估效果見(jiàn)表3。

3.2 基于最小風(fēng)險(xiǎn)準(zhǔn)則的信用評(píng)估模型實(shí)驗(yàn)

針對(duì)德國(guó)信用卡數(shù)據(jù)，對(duì)客戶進(jìn)行分類，由于把原來(lái)為“bad”的客戶判為“good”，會(huì)造成更大損失，于是提出分類風(fēng)險(xiǎn)概念。通過(guò)將基于最大后驗(yàn)概率進(jìn)行分類換為基于最小風(fēng)險(xiǎn)進(jìn)行分類的方法，使得將原來(lái)為“bad”的客戶判為“good”的情況減少。此時(shí)，損失矩陣：

其中：c-12=1表示把原本為信用好的客戶判為信用不好的客戶，損失1個(gè)單位；c-21=5表示把原本為信用不好的客戶判為信用好的客戶（造成更大的損失），損失5個(gè)單位。不同準(zhǔn)則下的樸素貝葉斯與TAN模型的綜合信用評(píng)估效果對(duì)比如表4所示。

加入最小風(fēng)險(xiǎn)準(zhǔn)則的概念后，“bad”誤分率和總損失明顯下降，達(dá)到預(yù)期效果。根據(jù)表格數(shù)據(jù)可知，樸素貝葉斯模型“bad”誤分率從0.480 2降至0.165 9，下降了65.45%，TAN模型“bad”誤分率從0.516 2降至0.261 1，下降了49.42%，但代價(jià)是增加了“good”誤分率與總體誤分率。

4 利用爬山算法構(gòu)建貝葉斯網(wǎng)絡(luò)模型進(jìn)行信用評(píng)估

基于爬山算法建立的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)相比樸素貝葉斯和TAN網(wǎng)絡(luò)結(jié)構(gòu)更加復(fù)雜。有向邊連接父節(jié)點(diǎn)和子節(jié)點(diǎn)，并由父節(jié)點(diǎn)指向子節(jié)點(diǎn)，表示給定父節(jié)點(diǎn)變量取值，子節(jié)點(diǎn)變量與網(wǎng)絡(luò)其它節(jié)點(diǎn)變量條件獨(dú)立。模型選擇階段的評(píng)分函數(shù)選為AIC[15]，并對(duì)建立的貝葉斯網(wǎng)絡(luò)模型進(jìn)行條件獨(dú)立性檢驗(yàn)，即給定某變量父節(jié)點(diǎn)變量，該變量與其它變量獨(dú)立，確保網(wǎng)絡(luò)結(jié)構(gòu)的合理性。10組測(cè)試部分結(jié)果見(jiàn)表5（假設(shè)α=0.05）。

根據(jù)表5可以發(fā)現(xiàn)，變量“property”與“duration”相關(guān)性很強(qiáng)，所以需要添加有向邊；給定“amount”，“duration”、“property”和“job”具有很強(qiáng)的不獨(dú)立性，將“amount”指向“duration”的有向邊刪除。“property”（財(cái)產(chǎn)狀況）與“duration”（貸款時(shí)間）之間的有向邊方向，指定由“property”指向“duration”。

基于爬山算法構(gòu)建的貝葉斯網(wǎng)絡(luò)模型使用最大似然估計(jì)和貝葉斯估計(jì)兩種參數(shù)學(xué)習(xí)方法，信用評(píng)估效果如表6所示。

由表6可知，基于爬山算法、評(píng)分函數(shù)為AIC建立的貝葉斯模型分類預(yù)測(cè)結(jié)果，與樸素貝葉斯、TAN模型的信用評(píng)分效果很接近，同時(shí)使用最大似然估計(jì)和貝葉斯估計(jì)的參數(shù)學(xué)習(xí)方法，其模型評(píng)估效果接近一致。

5 結(jié)語(yǔ)

通過(guò)實(shí)際數(shù)據(jù)，分析了貝葉斯網(wǎng)絡(luò)中的樸素貝葉斯網(wǎng)和樹(shù)增強(qiáng)樸素貝葉斯網(wǎng)（TAN）對(duì)德國(guó)信用卡數(shù)據(jù)的評(píng)估效果，結(jié)果顯示兩種分類器的性能差異不大，分類精度較高，但損失代價(jià)較大。在最小風(fēng)險(xiǎn)準(zhǔn)則下，評(píng)估效果相比最大后驗(yàn)概率準(zhǔn)則沒(méi)有發(fā)生明顯變化，總損失有所下降，綜合性能相對(duì)提高?；谂郎剿惴ń⒌呢惾~斯網(wǎng)絡(luò)模型評(píng)估效果與前兩種模型接近，說(shuō)明簡(jiǎn)單的樸素貝葉斯模型可以產(chǎn)生更高的經(jīng)濟(jì)效益。在此基礎(chǔ)上分析了最大似然估計(jì)和貝葉斯估計(jì)方法的模型評(píng)估效果。結(jié)果顯示，兩種參數(shù)學(xué)習(xí)方法的模型評(píng)估效果很接近，這是因?yàn)閿?shù)據(jù)量足夠大，使得貝葉斯估計(jì)趨近于最大似然估計(jì)。

參考文獻(xiàn)：

[1] PAN H P， LIU L. Fuzzy Bayesian networks[J]. International Journal of Pattern Recognition and Artificial Intelligence， 2000，14（7）：941-962.

[2] JUDEA P. Probabilistic reasoning in intelligent systems： networks of plausible inference[D]. CA ：San Mateo， 1988.

[3] ZHANG H， JIANG L， SU J. Hidden Naive Bayes [C]. National Conference on Artificial Intelligence， 2005：919-924.

[4] FRIED N， GEIGER D， GOLDSZMIDT M. Bayesian network classifiers[J]. Machine Learning， 1997，29（2-3）：131-163.

[5] ZHANG L W， GUO H P. Introduction to Bayesian networks[M]. Perking： Science Press， 2006.

[6] COOPER G F， HERSKOVITS E. A Bayesian method for the induction of probabilistic networks from data[J]. Machine Learning， 1992，9（4）：309-347.

[7] BOUCKAERT R R. A stratified simulation scheme for inference in Bayesian Belief[C].Proceedings of the Tenth Conference on Uncertainty in Artificial Intelligence， 1994：110-117.

[8] CHICKERING D， GEIGER D， HECKERMAN D. Learning Bayesian networks： search methods and experimental results[C]. Proceedings of the 5th Conference on Artificial Intelligence and Statistics， 1995：112-128.

[9] GAMEZ J A， MATEO J L， PUERTA J M. Learning Bayesian networks by hill climbing： efficient methods based on progressive restriction of the neighborhood[J]. Data Mining and Knowledge Discovery， 2011，22：106-148.

[10] TURNEY P D. Types of cost in inductive concept learning[J]. In Proceedings of Workshop on Cost-Sensitive Learning at the 17th International Conference on Machine Learning， 2002：15-21.

[11] MALOOF M A. Learning when data sets are imbalanced and when costs are unequal and unknown[C]. Washington， DC： In Proceedings of the ICML′03 Workshop on Learning from Imbalanced Data Sets， 2003.

[12] ELKAN C. The foundations of cost-sensitive learning[C]. Seventeenth International Joint Conference on Artificial Intelligence，2001：973-978.

[13] WANG J， ZHAO P， HOI S C H. Cost-sensitive online classification[J]. IEEE Transactions on Knowledge and Data Engineering， 2014，26（10）：2425-2438.

[14] 茆詩(shī)松.貝葉斯統(tǒng)計(jì)[M].北京：中國(guó)統(tǒng)計(jì)出版社，1999.

[15] 何德琳.貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法改進(jìn)研究[D].北京：北京化工大學(xué)，2008.

（責(zé)任編輯：何 麗）