孫晶 化越 趙會(huì)群

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

1 引言

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

2 K2改進(jìn)算法

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

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

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

在開(kāi)始融合之前需要為貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)中的結(jié)點(diǎn)和邊進(jìn)行打標(biāo)簽。為了保證融合網(wǎng)絡(luò)結(jié)構(gòu)過(guò)程中結(jié)點(diǎn)的有序性，需要根據(jù)每個(gè)結(jié)點(diǎn)所代表的實(shí)際意義為每個(gè)結(jié)點(diǎn)和每一條邊打上標(biāo)簽。接著，將所有局部貝葉斯網(wǎng)絡(luò)的結(jié)點(diǎn)和網(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 的時(shí)，文本基于原貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)評(píng)分值對(duì)加入的邊進(jìn)行篩選，具體步驟為在改進(jìn)K2 算法學(xué)習(xí)局部貝葉斯網(wǎng)絡(luò)的過(guò)程中，分別得到局部貝葉斯網(wǎng)絡(luò)中每條邊評(píng)分值進(jìn)行存儲(chǔ).分別給予局部網(wǎng)絡(luò)結(jié)構(gòu)的評(píng)分最小值不同的權(quán)重，計(jì)算出來(lái)加權(quán)平均評(píng)分值作為融合網(wǎng)絡(luò)的邊的閾值。若加入初始網(wǎng)絡(luò)的邊的評(píng)分大于等于閾值，則加入其中。在得到融合貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)后，基于最大似然估計(jì)法求出條件概率表。對(duì)于根結(jié)點(diǎn)概率，可以根據(jù)結(jié)點(diǎn)不同取值的出現(xiàn)頻率，作為根節(jié)點(diǎn)的概率參數(shù)。對(duì)于節(jié)點(diǎn)的條件概率，可由給定父結(jié)點(diǎn)集的值時(shí)，結(jié)點(diǎn)不同取值的出現(xiàn)頻率求得。

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

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

4 實(shí)驗(yàn)分析

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

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

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

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

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

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

下面進(jìn)行閾值選取的實(shí)驗(yàn)，在閾值分別取所有評(píng)分的平均值，中位數(shù)以及隨機(jī)產(chǎn)生評(píng)分的均值的情況下，比較改進(jìn)算法和K2 算法生成的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)的邊的數(shù)量以及兩個(gè)網(wǎng)絡(luò)結(jié)構(gòu)的相似度。通過(guò)實(shí)驗(yàn)發(fā)現(xiàn)閾值選取的效果并不好，和K2 算法所得貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)的相似度最高只有89.58%。在下面實(shí)驗(yàn)當(dāng)中，閾值的選取不再只有一個(gè)，計(jì)算出每個(gè)結(jié)點(diǎn)的評(píng)分，在每個(gè)結(jié)點(diǎn)評(píng)分值區(qū)間內(nèi)隨機(jī)生成一個(gè)值作為閾值。利用3 組數(shù)據(jù)集，每個(gè)數(shù)據(jù)集進(jìn)行了100次實(shí)驗(yàn)，統(tǒng)計(jì)了100 次實(shí)驗(yàn)中網(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%。由以上實(shí)驗(yàn)可以知道，當(dāng)選擇一個(gè)合適閾值時(shí)，改進(jìn)算法準(zhǔn)確率可在90%以上。利用融合算法把股票貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)和房地產(chǎn)貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行融合，并且在不同數(shù)據(jù)量的情況下比較融合算法與K2 算法的運(yùn)行時(shí)間，如圖3所示。

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

5 結(jié)束語(yǔ)

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

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

圖2：相似度分析

圖3：運(yùn)行時(shí)間比較