曾 安，李曉兵，楊海東，潘 丹

（1.廣東工業(yè)大學計算機學院，廣東 廣州 510006；2.中油管道物資裝備總公司，河北 廊坊 065000；3.美國Batteries Plus公司，哈特蘭市 威斯康辛州 53029）

貝葉斯網(wǎng)絡是以概率論和圖論為理論基礎(chǔ)，用一個帶有條件概率的有向無環(huán)圖來表示隨機變量間依賴和獨立關(guān)系的網(wǎng)絡模型［1］.由于貝葉斯網(wǎng)絡具有獨特的不確定性表達形式、易于綜合先驗知識以及直觀的推理結(jié)果等特性，貝葉斯網(wǎng)絡已逐漸成為在不確定情況下進行推理和決策的一種很受歡迎的網(wǎng)絡結(jié)構(gòu)，并已在故障檢測、交通管理和金融投資與市場分析等領(lǐng)域取得了應用［2－4］.實際上，貝葉斯網(wǎng)絡也常用在醫(yī)療領(lǐng)域之中.例如：CPCSBN遠程醫(yī)療系統(tǒng)［5］，它是一個多層貝葉斯網(wǎng)絡，有448個結(jié)點和908條邊，是優(yōu)于世界上主要的遠程醫(yī)療診斷分析方法；Alarm網(wǎng)［6］具有37個結(jié)點和46條邊，描述了在醫(yī)院手術(shù)室中所存在的潛在細菌問題；Take HeartⅡ系統(tǒng)［7］是基于貝葉斯網(wǎng)的用于心血管并診斷的臨床支持決策系統(tǒng)（Clinical Decision Support System，CDSS）等.國內(nèi)使用貝葉斯網(wǎng)絡在冠脈支架臨床進行試驗［8］，使用貝葉斯決策分類提高了藥物分類的準確性［9］.通過貝葉斯網(wǎng)絡圖形化的特點，建立起疾病診斷、終點與癥狀、臨床檢驗的因果關(guān)系的模型，使醫(yī)療的診斷、處理更加科學和客觀.

貝葉斯網(wǎng)絡結(jié)構(gòu)學習是目前研究的熱點，其目的是獲取能較好吻合數(shù)據(jù)集并且盡可能簡單的網(wǎng)絡結(jié)構(gòu).同時，貝葉斯網(wǎng)絡結(jié)構(gòu)學習也是一個NP難題.在實際中，人們主要是通過啟發(fā)式方法來獲取最優(yōu)的網(wǎng)絡結(jié)構(gòu)［10－11］.它主要分為兩類：一類是基于條件獨立性測試的學習方法，這類方法過程比較復雜，學習效率比較低，需要假設(shè)一些限制條件來提高算法的學習效率［12］；另一類是基于評分搜索的學習方法，該類方法對個體測試的錯誤并不敏感，可以在數(shù)據(jù)變量的依賴程度與添加邊的復雜度之間選擇一個折中的方法，如G.Cooper和E.Herskovits提出的K2算法［13］.如今，已經(jīng)提出了很多貝葉斯結(jié)構(gòu)學習的算法［14－15］，并且大多研究是基于評分搜索的學習方法.

本文提出了一種新穎的基于KMBN算法.該算法在利用logistic回歸和互信息對數(shù)據(jù)集進行降維的基礎(chǔ)上，將MDL評分與K2算法結(jié)合，以構(gòu)建出一種較優(yōu)的網(wǎng)絡結(jié)構(gòu).實驗結(jié)果證實了該方法在效率和可靠性方面都明顯優(yōu)于傳統(tǒng)的網(wǎng)絡結(jié)構(gòu)學習算法.

1 貝葉斯網(wǎng)絡簡述

貝葉斯網(wǎng)絡又稱為信念網(wǎng)絡、因果概率網(wǎng)絡等.它可以將具體問題中復雜的變量關(guān)系體現(xiàn)在一個網(wǎng)絡結(jié)構(gòu)中，并通過局部條件概率緊湊地表達出來.它描述了變量之間的依賴和因果關(guān)系，并使變量間的關(guān)系形成相對穩(wěn)定的狀態(tài).貝葉斯網(wǎng)絡分為有向無環(huán)圖（directed acyclic graph，DAG）和條件概率表（conditional probability table，CPT）兩部分.其中，有向無環(huán)圖包括結(jié)點集合與結(jié)點之間的有向邊，有向邊代表結(jié)點之間的依賴關(guān)系；條件概率表表示結(jié)點之間的關(guān)聯(lián)強度或置信度.學習貝葉斯網(wǎng)絡結(jié)構(gòu)來解決問題，不僅需要考慮先驗知識的融合、評估函數(shù)的選擇，而且也要考慮不完備數(shù)據(jù)等因素的影響.

眾所周知，K2算法是貝葉斯網(wǎng)絡結(jié)構(gòu)學習領(lǐng)域的經(jīng)典算法［16］，具有非常優(yōu)異的學習性能.K2算法有2個前提條件，就是要先給出結(jié)點的順序和每個結(jié)點的父結(jié)點個數(shù)的上限.它的目的是尋找結(jié)構(gòu)G的Cooper－Herskovis（CH）評分較高的模型，通過對數(shù)據(jù)集D的分析，找到與D吻合最好的貝葉斯網(wǎng)絡結(jié)構(gòu)G，即CH（G｜D）最大的網(wǎng)絡結(jié)構(gòu).其中

式中CH（〈Xi，πi〉｜D）為Xi的家族CH評分.依據(jù)這一思想，在給出結(jié)點序ρ以及每個結(jié)點的父結(jié)點個數(shù)的上限u的情況下，K2利用貪婪搜索一次為每個結(jié)點找到其父結(jié)點集，從而最終構(gòu)建出完整的貝葉斯網(wǎng)絡.但在使用CH評分之前，首先需要選定先驗分布中的超參數(shù).通常這并非易事，因為理論上我們需要對每一個可能的結(jié)構(gòu)都提供參數(shù)先驗分布，而結(jié)構(gòu)數(shù)目眾多，無法一一羅列.MDL準則不需要計算其參數(shù)的先驗分布，計算較簡單，且由于明確地將結(jié)構(gòu)復雜性作為一個指標而傾向于選擇較簡單的網(wǎng)絡結(jié)構(gòu)，計算結(jié)果更容易被接受.因此，基于MDL準則的算法可較好地實現(xiàn)目標網(wǎng)絡結(jié)構(gòu)的拓撲簡單性與對實例數(shù)據(jù)集擬合度之間的權(quán)衡.

MDL是Rissanen在研究通用編碼時提出的［17－18］.它綜合考慮了似然函數(shù)和計算復雜度兩方面的因素.這個準則的基本原理是對于給定的實例數(shù)據(jù)進行壓縮，從而降低數(shù)據(jù)的編碼（描述）長度.一個MDL評分由以下2部分構(gòu)成：

因此，貝葉斯網(wǎng)絡結(jié)構(gòu)的MDL評分為

2 基于KMBN算法

基于KMBN算法主要包含3個步驟：（1）屬性（變量）降維，在對連續(xù)性變量進行離散化的基礎(chǔ)上，利用logistic多變量回歸分析找出相關(guān)性較為顯著的變量；（2）構(gòu)建無向圖，然后計算每一個屬性變量和決策變量間的互信息熵，互信息熵較小的變量之間連接邊；（3）構(gòu)建有向圖，運用MDL局部打分原理和K2算法來確定邊的方向.

設(shè)一個數(shù)據(jù)集D 有M 個變量，記為X＝｛X1，X2，…，XM｝，假設(shè)｛X1，X2，…，XM－1｝是屬性變量，XM是決策變量.

2.1 屬性降維

利用logistic多變量回歸分析從結(jié)點變量X＝｛X1，X2，…，XM｝中找出用來構(gòu)建貝葉斯網(wǎng)絡結(jié)構(gòu)所需的變量.記rij＝p，對于屬性變量Xi和決策變量XM（i＜M），用riM來表示它們之間的關(guān)系.如果riM≤0.05，則表示Xi和XM間為顯著關(guān)系，即該屬性變量對決策變量的影響顯著；如果riM＞0.05，則表示Xi和XM間為非顯著關(guān)系，或者說與它們無關(guān).這樣就得出了構(gòu)建貝葉斯網(wǎng)絡結(jié)構(gòu)的變量，記為｛X1，X2，…，XN，其中XN＝XM為決策變量.

本研究對象選擇2016年12月~2017年12月在我院接受治療的120例初診2型糖尿病患者。將其按照就診時間先后分為觀察組與對照組,每組各60例患者。其中對照組男性32例,女性28例;年齡為37~70歲,平均年齡為(48.5±3.5)歲;病程1~7年,平均病程為(3.5±1.5)年;觀察組男性31例,女性29例;年齡為38~70歲,平均年齡為(49.0±3.2)歲;病程1~6年,平均病程為(3.2±1.0)年。兩組患者一般資料相比,無顯著差異(P>0.05),具有可比性。

2.2 構(gòu)建無向圖

依次對每一個屬性變量和決策變量〈Xi，XN〉，i＝1，2，…，N－1計算，其互信息熵為

其中xi為Xi的值，xN為XN的值.給定一個閾值e（e通常是一個很小的正數(shù)）.當I＜e時，連接邊Xi～XN.

將I按大小進行排序，可得到初始結(jié)構(gòu)結(jié)點的先驗順序，記為ρ.

2.3 構(gòu)建有向圖

對于上述已經(jīng)存在的無向圖，運用MDL局部打分原理來確定邊的方向.MDL局部打分原理如下：

設(shè)2個貝葉斯網(wǎng)絡結(jié)構(gòu)分別為G1，G2，其中變量Xi的父結(jié)點集分別為Π1和Π2，如果Π1和Π2中只有π1和π2不同，那么ScoreMDL（G1｜D）－ScoreMDL（G2｜D）＝ScoreMDL（X1∪π1｜D）－ScoreMDL（X2∪π2｜D），π1和π2分別為Π1和Π2中的父結(jié)點，ScoreMDL（Gi｜D）表示結(jié)構(gòu)Gi在數(shù)據(jù)集D 上的最小描述長度，i＝1，2.

對變量Xj，假設(shè)它已經(jīng)有了一些父結(jié)點為πj.若｜πj｜＜u，即變量Xj的父結(jié)點個數(shù)還沒達到u，則就要繼續(xù)找尋它的父結(jié)點.首先考慮那些在ρ中排在Xj之前、但卻還不是Xj的父結(jié)點的變量，從這些變量中選出Xi，計算新測度值MDL評分（記為ScoreNew）.然后將其與舊測度（記為ScoreOld）做比較，如果ScoreNew＜ScoreOld，則記Xi為Xj的父結(jié)點，否則停止尋找Xj的父結(jié)點.

2.4 算法的偽代碼

輸入：n個變量的集合X＝｛X1，X2，…，Xn｝；變量父結(jié)點的上限個數(shù)為u；變量的順序ρ；一個包含N個樣本的完整數(shù)據(jù)集D.

輸出：一個貝葉斯網(wǎng)絡結(jié)構(gòu).

3 實驗結(jié)果分析

3.1 可靠性分析

為了驗證本文提出的基于KMBN算法的有效性，采用廣東省某醫(yī)院MICU病房提供的數(shù)據(jù)集對KMBN算法、基于K2的貝葉斯結(jié)構(gòu)學習算法和基于K2與模擬退火的貝葉斯結(jié)構(gòu)學習算法進行仿真實驗.該數(shù)據(jù)集包括209個病歷，每個病歷有44個屬性，其中6個屬性是系統(tǒng)疾病，可將它們合并成一個屬性.則屬性有Balance，Speak和Platelet等38屬性變量和1個決策變量Event.該決策變量記錄了病人出MICU后是否存活了300d以上.38個屬性中，21個為連續(xù)型，17個為離散型的.為了簡化，僅選擇了其中一部分數(shù)據(jù)進行說明，相關(guān)信息見表1.對于連續(xù)型屬性，主要是根據(jù)專家經(jīng)驗知識設(shè)置斷點進行離散化，例如：對于屬性Platelet（100～300）×109個／L的為正常，低于100×109個／L或高于300×109個／L的為異常；屬性Procalcitonin小于0.5μg／L的為正常，大于或等于0.5μg／L的為異常；屬性Lactic Acid在0.5～2mmol／L之間為正常，小于0.5mmol／L或者大于2mmol／L的為異常.

表1 部分數(shù)據(jù)信息

對上述39個屬性采用回歸分析方法降維后，其中的12個屬性被保留了下來，它們包括11個屬性變量和1個決策變量（為了作圖方便，將它們用字母代替）：

我們對余下的12個屬性采用本文中提出的KMBN算法來構(gòu)建貝葉斯網(wǎng)絡結(jié)構(gòu).取結(jié)點變量的父結(jié)點的最大個數(shù)u＝4，結(jié)果如圖1所示.

圖1 KMBN算法的貝葉斯網(wǎng)絡結(jié)構(gòu)學習結(jié)果

為了驗證提出算法的性能，將結(jié)果分別與文獻［13］中的基于K2的貝葉斯結(jié)構(gòu)學習算法，文獻［19］中的K2與模擬退火相結(jié)合的貝葉斯結(jié)構(gòu)學習算法進行了比較.依然取結(jié)點變量的父結(jié)點的最大個數(shù)u＝4，基于K2算法的貝葉斯網(wǎng)絡結(jié)構(gòu)學習結(jié)果如圖2所示.

文獻［19］中的K2與模擬退火相結(jié)合的貝葉斯結(jié)構(gòu)學習算法的結(jié)果如圖3所示.

圖2 基于K2算法的貝葉斯網(wǎng)絡結(jié)構(gòu)學習結(jié)果

圖3 基于K2與模擬退火的貝葉斯網(wǎng)絡結(jié)構(gòu)學習結(jié)果

醫(yī)學診斷，特別是在臨床，需要簡潔、快速的診斷模型，冗長而耗費時間的診斷模型難以在臨床中推廣.ApacheⅡ評分模型［20］、GCS評分模型［21］就是臨床中快速的診斷模型.本文通過回歸分析方法來降維，在原本39個屬性中保留12個屬性，結(jié)點的減少簡化了決策變量的分析.通過KMBN算法得出的貝葉斯網(wǎng)絡結(jié)構(gòu)提示結(jié)果受Survival Desire和FAST評分［22］的直接影響，兩屬性使診斷快速而有效，文獻［13］方法顯示結(jié)果受到多個因素（H，K，G和A）影響，本文方法明顯提高了效率.而圖3方法顯示，結(jié)果受屬性（Eyesight，Temperature）影響，對照醫(yī)學領(lǐng)域，不符合實際.圖2中，顯示B，C，D，E，F(xiàn)，I，J之間沒有依賴關(guān)系.實際上，隨著疾病的進展和臟器功能衰竭，這些屬性是相互影響的，因此使用圖1解釋疾病發(fā)展更加合理.

本文算法、文獻［13］和文獻［19］的學習結(jié)果數(shù)據(jù)如表2所示.從表2中可以看出，KMBN算法、基于K2的貝葉斯結(jié)構(gòu)學習算法和基于K2與模擬退火的貝葉斯結(jié)構(gòu)學習算法得出的邊數(shù)分別為19條，37條，20條.明顯基于K2的貝葉斯結(jié)構(gòu)學習方法得出的關(guān)系更為復雜，而KMBN方法和基于K2與模擬退火的貝葉斯結(jié)構(gòu)學習方法的關(guān)系復雜度相似.它們精確度的檢驗有待驗證.但由模型中邊的情況觀察，通過醫(yī)學理解可知，圖1中FAST功能評級的下降提示患者存在老年癡呆，因此影響患者語言能力，語言能力的下降直接導致社交功能受損，然后將伴隨生存欲望的下降，最終導致結(jié)果的發(fā)生.而氧合指數(shù)的下降往往伴隨著呼吸機輔助呼吸，因此其語言及生存欲望下降，同時，乳酸的上升導致臟器灌注的下降，將影響視覺和腎臟血流（尿素氮上升），其他的結(jié)果也有類似的聯(lián)系.總體來說，圖1對于結(jié)果的解釋較為合理，反觀圖3中生存欲望對于體溫、膽紅素的影響在醫(yī)學中難以解釋.同時，體溫和視覺對于結(jié)果的直接影響也無法通過醫(yī)學理論解釋.實際上，在該方法中多個邊所確定的關(guān)系均無法在醫(yī)學領(lǐng)域中解釋，因此極大影響結(jié)果的可信度判斷.

表2 幾種算法學習結(jié)果的對比

3.2 計算復雜度分析

K2算法的時間復雜度為O（mk2n2r），其中：m表示實例樣本個數(shù)，k表示父結(jié)點個數(shù)，r表示每一個結(jié)點的取值個數(shù).在基于K2與模擬退火算法中，計算的復雜度與K2算法不同的就是多了等溫搜索次數(shù)t和最大迭代次數(shù)s，所以基于K2與模擬退火算法的時間復雜度是O（mk2n2rts）.對于文中改進的KMBN算法，在得出先驗結(jié)點順序后不再依賴實例樣本個數(shù)，因此其時間復雜度為O（k2n2r）.

由此可看出，基于K2與模擬退火的貝葉斯結(jié)構(gòu)學習算法的計算時間比較復雜，基于K2的貝葉斯結(jié)構(gòu)學習算法和本文算法接近，但基于K2的貝葉斯結(jié)構(gòu)學習算法得出的結(jié)果受到多個因素影響，效率明顯較低.再者，基于K2的貝葉斯結(jié)構(gòu)學習算法得出的結(jié)構(gòu)圖中的邊數(shù)比其他2個多很多，這在搜索診斷治療結(jié)果時需要花費更多的時間.雖然基于K2與模擬退火的貝葉斯結(jié)構(gòu)學習算法得出的結(jié)構(gòu)圖邊數(shù)與本文算法很接近，但前者確定的很多關(guān)系無法在醫(yī)學領(lǐng)域中證實，缺乏準確性.

4 結(jié)論

貝葉斯網(wǎng)絡結(jié)構(gòu)學習是數(shù)據(jù)挖掘的重要研究方向，它提供了不確定性環(huán)境下的知識表示、推理、學習手段，可以解決診斷、預測、分類等問題.本文充分考慮了條件變量與決策變量的數(shù)據(jù)分布關(guān)系，通過logistic回歸分析和條件互信息熵對案例數(shù)據(jù)進行了預處理，接著用提出的打分——搜索算法即KMBN算法對數(shù)據(jù)集進行了貝葉斯網(wǎng)絡結(jié)構(gòu)學習.實驗結(jié)果表明，本文算法與傳統(tǒng)的基于K2算法的貝葉斯結(jié)構(gòu)學習比較，前者明顯簡化了網(wǎng)絡結(jié)構(gòu).本文算法與基于K2與模擬退火的貝葉斯結(jié)構(gòu)學習算法比較，可以看出，本文算法具有較好的可靠性.同時，本文算法在時間復雜度上面也有改善，為貝葉斯網(wǎng)絡廣泛應用于解決實際問題又提供了一種新的有效方法.

［1］王雙成，冷翠平，李小琳.小數(shù)據(jù)集的貝葉斯網(wǎng)絡結(jié)構(gòu)學習［J］.自動化學報，2009，35（8）：1063－1069.

［2］HUANG YINGPING，MCMURRAN R，DHADYALLA G.Probability based vehicle fault diagnosis：Bayesian network method［J］.Journal of Intelligent Manufacturing，2008，19（3）：301－311.

［3］JULIO C R，GUILLERMINA M，LUDIVINA G.Fault diagnosis in an industrial process using Bayesian networks：application of the junction tree algorithm［C］／／Proceedings of Electronics，Robotics and Automotive Mechanics Conference，Cerma：Mexico，2009：301－306.

［4］JUAN M F，JUAN F H，BENJAMIN P.Introduction to the special issue on graphical models and information retrieval［J］.Journal of Approximate Reasoning，2009，50（7）：929－931.

［5］OLIéSKO A，LUCAS P，DRUZDZEL MJ.Comparison of rule－based and Bayesian network approaches in medical diagnostic systems［J］.Artificial Intelligence in Medicine，Lecture Notes in Computer Science，2001（8）：283－292.

［6］BEINLICH IA，SUERMONDT HJ，CHAVEZ RM，et al.The alarm monitoring system：a case study with two probabilistic inference techniques for belief networks［C］／／Artificial Intelligence in Medicine，Lecture Notes in Medical Informatics，London：AMAZON，1989：247－256.

［7］HOPE LR，NICHOLSON AE，KORB KB，et al.Take heartⅡ：a tool to support clinical cardiovascular risk assessment［J］.Tech Rep，2007：209.

［8］王楊，王睿，陳濤，等.貝葉斯分層模型在醫(yī)療器械臨床試驗中的應用［J］.中華疾病控制雜志，2012，3（16）：254－256.

［9］周揚，呂進，戴曙光，等.基于貝葉斯決策的近紅外光譜藥片分類方法［J］.分析化學，2013，2（41）：293－296.

［10］TAE YOUNG YANG，JAE CHANG LEE.Bayesian nearest－neighbor analysis via record value statistics and nonhomogeneous spatial Poisson processes［J］.Computational Statistics ＆ Data Analysis，2007，51：4438－4449.

［11］FEELDERS AD，LINDA C VAN DER GAAG.Learning Bayesian network parameters under order constraints［J］.International Journal of Approximate Reasoning，2006，33：37－53.

［12］孫巖，呂世聘，王秀坤，等.貝葉斯網(wǎng)絡結(jié)構(gòu)模型的構(gòu)建［J］.小型微型計算機系統(tǒng)，2008，29（5）：859－862.

［13］COOPER G，HERSOVITS E.A Bayesian method for the induction of probabilistic networks from data［J］.Machine Learning，1992，9（4）：309－347.

［14］BRENDAN J FREY，NEBOJSA JOJIC.A comparison of algorithms for inference and learning in probabilistic graphical models［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27（9）：1392－1416.

［15］ZGUROVSKII M Z，BIDYUK P I，TERENT'EV A N.Methods of constructing Bayesian networks based on scoring functions［J］.Cybernetics and Systems Analysis，2008，44（2）：219－224.

［16］朱明敏，劉三陽，汪春鋒.基于先驗結(jié)點序?qū)W習貝葉斯網(wǎng)絡結(jié)優(yōu)化方法［J］.自動化學報，2011，12：1514－1519.

［17］HUANLLU H，MOTODA H，SETIONO R，et al.An ever evolving frontier in data mining［J］.Workshop and Conference Proceedings，2010，10：4－13.

［18］MARKOV Z.MDL－based unsupervised attribute ranking［C］／／Proceedings of the twenty－sixth international florida artificial intelligence research society conference.California：The AAAI Press，2013：444－449.

［19］金焱，胡云安，張瑾，等.K2與模擬退火相結(jié)合的貝葉斯網(wǎng)絡結(jié)構(gòu)學習［J］.東南大學學報，2012，42（1）：82－86.

［20］KNAUS WA，DRAPER EA，WAGNER DP，et al.ApacheⅡ：a severity of disease classification system［J］.Crit Care Med，1985，13（10）：818－829.

［21］TEASDALE G，JENNETT B.Assessment of coma and impaired consciousness［J］.A practical Scale Lancet，1974（2）：81－84.

［22］HEISBERG B.Functional assessment staging（Fast）［J］.Psychopharmacol Bull，1988，24（4）：653－659.