孫晶 化越 趙會群

（北方工業大學信息學院 北京市 100144）

1 引言

貝葉斯網絡以概率論和圖論作為基礎，通過有向無環圖和條件概率表來表示隨機變量之間的依賴關系。由于貝葉斯網絡具有結合先驗經驗對不確定性知識進行有效推理和決策等特性，它已被應用在交通，故障檢查和醫學等領域當中[1，2，3]。貝葉斯網絡結構學習算法一直以來都是貝葉斯網絡研究的熱點，其目的就是尋找到能夠較好擬合數據集的網絡結構[4]。由于傳統的貝葉斯網絡構造算法中，為了求得節點之間的依賴關系的評分函數，依賴對節點的指數級別的遍歷過程，造成了時間復雜度過高，限制了大數據集的訓練和學習，尤其是在數據源復雜和不同領域數據組合構建貝葉斯網絡的情況更是如此。本文提出了組合數據下貝葉斯網絡構建算法。首先訓練不同領域數據的貝葉斯網絡結構，再通過融合算法進行融合，解決因結點過多帶來算法效率較低的問題。此外，本文利用K2 算法學習局部貝葉斯網絡，但是K2 算法對于每一種結構，都要使用評分函數進行評分，這使K2 算法的計算強度大。針對此問題，本文提出K2 改進算法，新算法在評分的過程中通過減少評分函數的調用次數，減少算法的計算量，提高算法效率。

2 K2改進算法

K2 改進算法是在評分過程中加入了閾值ρ。對每個結點和可能成為其父親結點進行評分，之后將評分值與閾值進行比較，如果評分值大于閾值且沒有達到父親結點個數上限，便將評分值所對應的父親結點加入到最優父親集合。K2 改進算法步驟為假設每個結點沒有父親結點，根據輸入結點次序，排在當前結點前的結點皆有可能成為其父親結點，假設Pre(Xi)為當前結點可能父親結點集合，πi為最優父親結點集合。利用K2 評分公式，如式（1）所示，計算將當前節點Xi和Pre(Xi)中每個節z1,l=1,2,…m,的評分Score，并計算閾值ρ。比較z1的評分Score 和閾值ρ 的大小，若Score＞ρ，則將z1加入πi中。當結點的父親個數達到父親結點上限個數，結點所有可能的父親結點集合已經搜索完，這兩個條件滿足其中一個條件時，終止再為當前結點X_i 尋找最優父親結點。

與K2 算法相比，改進算法不再對所有可能的結構進行評分，而是只對當前結點和每一個父親結點分別進行評分，減少了K2 評分函數的使用，從而提高學習網絡的質量并減少所需的計算量。本文對閾值取值有四種選擇：（1）所有評分的均值。（2）所有評分的中位數。（3）所有評分之間產生隨機數。（4）對于每個結點都設定一個閾值ρ。這時閾值ρ 的取值為每個結點的評分的隨機數。

3 貝葉斯網絡融合算法

在開始融合之前需要為貝葉斯網絡結構中的結點和邊進行打標簽。為了保證融合網絡結構過程中結點的有序性，需要根據每個結點所代表的實際意義為每個結點和每一條邊打上標簽。接著，將所有局部貝葉斯網絡的結點和網絡結構中重復的邊作為初始網絡G=(V,E)。為了融合后保留最多邊和信息，將Ew加入到網絡結構G中，其中Ew是在局部貝葉斯網絡中出現的邊但卻不存在于G。為了保留最多的信息，將Ew中的邊全部加入G 是最理想的情況，但這不適于所有情況，且易造成融合網絡結構復雜或存在冗余邊。因此在加入G 的時，文本基于原貝葉斯網絡結構評分值對加入的邊進行篩選，具體步驟為在改進K2 算法學習局部貝葉斯網絡的過程中，分別得到局部貝葉斯網絡中每條邊評分值進行存儲.分別給予局部網絡結構的評分最小值不同的權重，計算出來加權平均評分值作為融合網絡的邊的閾值。若加入初始網絡的邊的評分大于等于閾值，則加入其中。在得到融合貝葉斯網絡結構后，基于最大似然估計法求出條件概率表。對于根結點概率，可以根據結點不同取值的出現頻率，作為根節點的概率參數。對于節點的條件概率，可由給定父結點集的值時，結點不同取值的出現頻率求得。

表1：數據來源

表2：數據集展示

4 實驗分析

本文選取2009 至2019年十年間宏觀因素、股票以及房地產三方面，一共27 個數據來構建貝葉斯網絡結構。14 個宏觀因素分別從4 個途徑獲取，其中從開源數據集蘿卜投研中獲得居民消費水平、供應貨幣量、商品消費品總額、工業增加值、消費者信心指數和證券投資者信心指數、匯率；從中國人民銀行官網獲得存款利率、準備金利率，貸款利率、個人商業住房貸款利率和個人公積金貸款利率；從新浪財經爬取股票新聞數據；從國務院辦公室爬取股票政策和新聞政策。11 個股票數據主要利用Tushare 數據庫開源接口調用，獲取滬深300、中國石油、寶鋼股份、中國建筑、中國聯通、中國中車、長江電力、格力電器、恒瑞醫藥、貴州茅臺和中國平安；2個房地產數據分別從Tushare 數據庫中獲取地產指數以及從安居客網頁上爬取房價數據。具體數據獲取的內容如表1所示。

構建貝葉斯網絡結構所需要的數據為離散變量，進行實驗前需要對數據進行清洗和離散化，離散化后變量取值如下：

經過離散化后對于新聞類數據，得到了每個月利好股票新聞個數和每個月利空股票新聞個數。離散化處理后，股票新聞有三種取值[0，1，2，3]。0 表示小于100 個，1 表示大于100 并且小于300個，2 表示大于300 并且小于500 個，3 表示大于500 個。對于政策類數據，得到了每個月利好股票政策個數、每個月利空股票政策個數、每個月利好房地產政策個數和每個月利空房地產政策個數。股票和房地產政策有三種取值[0，1，2，3]，0 表示小于5 個，1表示大于5 并且小于10 個，2 表示大于10 并且小于20 個，3 表示大于20。其余數據均為每月漲幅度，有三種取值[0,1,2]，當月漲跌幅為(0,+∞)，即比上月上漲，變量取值為1；當月漲跌幅為(-∞,0)，即比上月下降，變量取值為0；當月漲跌幅等于0，即與上月持平，變量取值為2。

為進行實驗，本文將數據整理為三個數據集，分別為股票數據集、房地產數據集和股票房地產組合數據集。其中股票數據集有24個特征，房地產數據集有15 個特征，股票房地產組合數據集有31個特征，具體特征如表2所示，具體特征描述如離散處理后部分所示。

將K2 算法和K2 改進算法分別在3 個集中選擇不同結點個數進行運行，統計K2 評分函數的使用次數，如圖1所示。

從圖1 可以看出，與傳統的K2 算法相比，改進算法減少了評分函數的使用次數，降低了計算量。隨著結點個數增長，兩種算法在計算量上的差距越來越明顯。

下面進行閾值選取的實驗，在閾值分別取所有評分的平均值，中位數以及隨機產生評分的均值的情況下，比較改進算法和K2 算法生成的貝葉斯網絡結構的邊的數量以及兩個網絡結構的相似度。通過實驗發現閾值選取的效果并不好，和K2 算法所得貝葉斯網絡結構的相似度最高只有89.58%。在下面實驗當中，閾值的選取不再只有一個，計算出每個結點的評分，在每個結點評分值區間內隨機生成一個值作為閾值。利用3 組數據集，每個數據集進行了100次實驗，統計了100 次實驗中網絡結構與K2 算法所得網絡結構得相似度，如圖2所示。

由圖2 可以看出，在房地產數據集中相似度最高為91.56%。在股票數據集中相似度最高為91.84%。在股票和房地產數據集中相似度最高為91.36%。由以上實驗可以知道，當選擇一個合適閾值時，改進算法準確率可在90%以上。利用融合算法把股票貝葉斯網絡結構和房地產貝葉斯網絡結構進行融合，并且在不同數據量的情況下比較融合算法與K2 算法的運行時間，如圖3所示。

從圖3 可以看出K2 算法消耗大量的運行時間，而融合算法的運行時間明顯減少，并且融合算法對樣本容量的大小不敏感，具有處理大數據集的能力。

5 結束語

本文提出的組合數據下貝葉斯網絡構建算法，首先對K2 算法進行修改，將閾值加入到K2 評分過程中，得到結點依賴關系，來減少評分函數計算量大的問題，并通過貝葉斯網絡結構融合的方法，解決結點增加帶來的運行時間過長的問題。算法能夠隨著樣本數量的增加保持其穩定性，并通過實驗結果證明了K2 改進算法和貝葉斯網絡結構融合算法的可行性。

圖1：評分函數調用次數比較

圖2：相似度分析

圖3：運行時間比較