基于最小描述長度和K2的貝葉斯網絡結構學習算法

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

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

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

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

本文提出了一種新穎的基于KMBN算法.該算法在利用logistic回歸和互信息對數據集進行降維的基礎上，將MDL評分與K2算法結合，以構建出一種較優的網絡結構.實驗結果證實了該方法在效率和可靠性方面都明顯優于傳統的網絡結構學習算法.

1 貝葉斯網絡簡述

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

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

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

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

因此，貝葉斯網絡結構的MDL評分為

2 基于KMBN算法

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

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

2.1 屬性降維

利用logistic多變量回歸分析從結點變量X＝｛X1，X2，…，XM｝中找出用來構建貝葉斯網絡結構所需的變量.記rij＝p，對于屬性變量Xi和決策變量XM（i＜M），用riM來表示它們之間的關系.如果riM≤0.05，則表示Xi和XM間為顯著關系，即該屬性變量對決策變量的影響顯著；如果riM＞0.05，則表示Xi和XM間為非顯著關系，或者說與它們無關.這樣就得出了構建貝葉斯網絡結構的變量，記為｛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 構建無向圖

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

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

將I按大小進行排序，可得到初始結構結點的先驗順序，記為ρ.

2.3 構建有向圖

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

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

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

2.4 算法的偽代碼

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

輸出：一個貝葉斯網絡結構.

3 實驗結果分析

3.1 可靠性分析

為了驗證本文提出的基于KMBN算法的有效性，采用廣東省某醫院MICU病房提供的數據集對KMBN算法、基于K2的貝葉斯結構學習算法和基于K2與模擬退火的貝葉斯結構學習算法進行仿真實驗.該數據集包括209個病歷，每個病歷有44個屬性，其中6個屬性是系統疾病，可將它們合并成一個屬性.則屬性有Balance，Speak和Platelet等38屬性變量和1個決策變量Event.該決策變量記錄了病人出MICU后是否存活了300d以上.38個屬性中，21個為連續型，17個為離散型的.為了簡化，僅選擇了其中一部分數據進行說明，相關信息見表1.對于連續型屬性，主要是根據專家經驗知識設置斷點進行離散化，例如：對于屬性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 部分數據信息

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

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

圖1 KMBN算法的貝葉斯網絡結構學習結果

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

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

圖2 基于K2算法的貝葉斯網絡結構學習結果

圖3 基于K2與模擬退火的貝葉斯網絡結構學習結果

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

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

表2 幾種算法學習結果的對比

3.2 計算復雜度分析

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

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

4 結論

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

［1］王雙成，冷翠平，李小琳.小數據集的貝葉斯網絡結構學習［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］王楊，王睿，陳濤，等.貝葉斯分層模型在醫療器械臨床試驗中的應用［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］孫巖，呂世聘，王秀坤，等.貝葉斯網絡結構模型的構建［J］.小型微型計算機系統，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］朱明敏，劉三陽，汪春鋒.基于先驗結點序學習貝葉斯網絡結優化方法［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與模擬退火相結合的貝葉斯網絡結構學習［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.