組合數(shù)據(jù)下貝葉斯網(wǎng)絡(luò)構(gòu)建算法研究

孫晶 化越 趙會群

（北方工業(yè)大學(xué)信息學(xué)院 北京市 100144）

1 引言

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

2 K2改進(jìn)算法

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

與K2 算法相比，改進(jìn)算法不再對所有可能的結(jié)構(gòu)進(jìn)行評分，而是只對當(dāng)前結(jié)點和每一個父親結(jié)點分別進(jìn)行評分，減少了K2 評分函數(shù)的使用，從而提高學(xué)習(xí)網(wǎng)絡(luò)的質(zhì)量并減少所需的計算量。本文對閾值取值有四種選擇：（1）所有評分的均值。（2）所有評分的中位數(shù)。（3）所有評分之間產(chǎn)生隨機數(shù)。（4）對于每個結(jié)點都設(shè)定一個閾值ρ。這時閾值ρ 的取值為每個結(jié)點的評分的隨機數(shù)。

3 貝葉斯網(wǎng)絡(luò)融合算法

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

表1：數(shù)據(jù)來源

表2：數(shù)據(jù)集展示

4 實驗分析

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

構(gòu)建貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)所需要的數(shù)據(jù)為離散變量，進(jìn)行實驗前需要對數(shù)據(jù)進(jìn)行清洗和離散化，離散化后變量取值如下：

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

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

將K2 算法和K2 改進(jìn)算法分別在3 個集中選擇不同結(jié)點個數(shù)進(jìn)行運行，統(tǒng)計K2 評分函數(shù)的使用次數(shù)，如圖1所示。

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

下面進(jìn)行閾值選取的實驗，在閾值分別取所有評分的平均值，中位數(shù)以及隨機產(chǎn)生評分的均值的情況下，比較改進(jìn)算法和K2 算法生成的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)的邊的數(shù)量以及兩個網(wǎng)絡(luò)結(jié)構(gòu)的相似度。通過實驗發(fā)現(xiàn)閾值選取的效果并不好，和K2 算法所得貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)的相似度最高只有89.58%。在下面實驗當(dāng)中，閾值的選取不再只有一個，計算出每個結(jié)點的評分，在每個結(jié)點評分值區(qū)間內(nèi)隨機生成一個值作為閾值。利用3 組數(shù)據(jù)集，每個數(shù)據(jù)集進(jìn)行了100次實驗，統(tǒng)計了100 次實驗中網(wǎng)絡(luò)結(jié)構(gòu)與K2 算法所得網(wǎng)絡(luò)結(jié)構(gòu)得相似度，如圖2所示。

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

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

5 結(jié)束語

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

圖1：評分函數(shù)調(diào)用次數(shù)比較

圖2：相似度分析

圖3：運行時間比較