李昡熠,周 鋆*
(1.國防科技大學(xué)系統(tǒng)工程學(xué)院,長沙 410073;2.國防科技大學(xué)信息系統(tǒng)工程重點(diǎn)實(shí)驗(yàn)室,長沙 410073)
(?通信作者電子郵箱zhouyun@nudt.edu.cn)
貝葉斯網(wǎng)絡(luò)是一種通用的概率圖模型,它可以表示隨機(jī)變量之間的相關(guān)性,是隨機(jī)變量聯(lián)合概率分布的一種圖形化表示,具有很強(qiáng)的可解釋性,在機(jī)器學(xué)習(xí)領(lǐng)域有著廣泛的應(yīng)用,是領(lǐng)域研究的熱點(diǎn)之一。
然而在真實(shí)機(jī)器學(xué)習(xí)問題中,由于實(shí)際樣本數(shù)據(jù)存在噪聲和大小限制以及網(wǎng)絡(luò)空間搜索的復(fù)雜性,學(xué)習(xí)貝葉斯網(wǎng)絡(luò)的結(jié)構(gòu)是一個(gè)NP 難(Non-deterministic Polynomial hard,NPhard)問題[1]。因此,如何減小貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)的誤差成為了貝葉斯網(wǎng)絡(luò)學(xué)習(xí)的研究難點(diǎn)之一。近年來,人們發(fā)現(xiàn)合理的利用先驗(yàn)知識,可以提高貝葉斯結(jié)構(gòu)學(xué)習(xí)的準(zhǔn)確度[2],成為當(dāng)前貝葉斯網(wǎng)絡(luò)研究領(lǐng)域關(guān)注的重點(diǎn)。
本文提出一種基于頻繁項(xiàng)挖掘及關(guān)聯(lián)規(guī)則校正的結(jié)構(gòu)學(xué)習(xí)算法BNSL-FIM(Bayesian Network Structure Learning based on Frequent Item Mining),通過確定頻繁項(xiàng)之間的結(jié)構(gòu)關(guān)系,從中提取先驗(yàn)信息,并設(shè)計(jì)算法輔助提升最終結(jié)構(gòu)學(xué)習(xí)的準(zhǔn)確度。
如圖1 所示,本文提出的BNSL-FIM 算法首先對樣本數(shù)據(jù)進(jìn)行二分類處理以及頻繁項(xiàng)挖掘,通過關(guān)聯(lián)規(guī)則分析初步提取變量間的因果關(guān)系;然后使用PC 算法(PC-Algorithm)[3]對頻繁項(xiàng)進(jìn)行結(jié)構(gòu)學(xué)習(xí),并利用關(guān)聯(lián)規(guī)則分析結(jié)果對頻繁項(xiàng)的結(jié)構(gòu)學(xué)習(xí)進(jìn)行校正,從而形成最后的先驗(yàn)知識;最后以BDeu(Bayesian Dirichlet equivalent uniform)評分函數(shù)為基礎(chǔ)提出融合先驗(yàn)知識的評分方法,并使用該評分方法對樣本數(shù)據(jù)進(jìn)行貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)以得到最終的網(wǎng)絡(luò)結(jié)構(gòu)。
圖1 BNSL-FIM算法流程Fig.1 Flowchart of BNSL-FIM
經(jīng)典的貝葉斯網(wǎng)絡(luò)學(xué)習(xí)研究側(cè)重于評分函數(shù)的設(shè)計(jì)和搜索方法的優(yōu)化[4],通過對可能的網(wǎng)絡(luò)結(jié)構(gòu)和節(jié)點(diǎn)參數(shù)形式進(jìn)行描述,提高學(xué)習(xí)算法的智能水平和問題求解能力,在單一的問題領(lǐng)域已經(jīng)達(dá)到了一定的學(xué)習(xí)極限。這些研究偏重模型對訓(xùn)練數(shù)據(jù)的可解釋性,學(xué)習(xí)準(zhǔn)確度主要由訓(xùn)練數(shù)據(jù)的質(zhì)量決定,在數(shù)據(jù)有限或問題復(fù)雜的情況下,往往會出現(xiàn)過擬合的情況[5],難以在實(shí)際中應(yīng)用。
近年來,人們發(fā)現(xiàn)結(jié)合先驗(yàn)知識可以改進(jìn)貝葉斯網(wǎng)絡(luò)學(xué)習(xí)的準(zhǔn)確度,如引入結(jié)構(gòu)先驗(yàn)[6],或引入一定的約束條件[7]等,都可以大大減少結(jié)構(gòu)學(xué)習(xí)的搜索空間,從而便于算法在有限的時(shí)間內(nèi)找到可行解,因此設(shè)計(jì)先驗(yàn)知識的引入方法,是改進(jìn)現(xiàn)有貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法的一種思路。
關(guān)聯(lián)分析是數(shù)據(jù)挖掘中重要的研究內(nèi)容,其核心思想是通過對數(shù)據(jù)的共現(xiàn)關(guān)系進(jìn)行計(jì)算分析[8],從而發(fā)現(xiàn)數(shù)據(jù)之間隱含的關(guān)系與規(guī)律。肖?;鄣龋?]提出了一種融合關(guān)聯(lián)規(guī)則與知識的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法;Kharya 等[10]提出通過計(jì)算關(guān)聯(lián)規(guī)則置信度和提升度并結(jié)合貝葉斯網(wǎng)絡(luò)進(jìn)行預(yù)測的方法。這些方法均嘗試通過挖掘節(jié)點(diǎn)間的關(guān)聯(lián)規(guī)則來提升貝葉斯網(wǎng)絡(luò)的準(zhǔn)確度,但由于關(guān)聯(lián)規(guī)則并不顯式地表示變量的因果關(guān)系,上述方法均沒有實(shí)現(xiàn)通過挖掘關(guān)聯(lián)規(guī)則自動(dòng)化地進(jìn)行貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)。為了解決該問題,本文設(shè)計(jì)了一種新的基于頻繁項(xiàng)挖掘的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法。
本章主要介紹如何基于頻繁項(xiàng)挖掘貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)所使用的先驗(yàn)知識,包括:1)基于貝葉斯結(jié)構(gòu)學(xué)習(xí)樣本數(shù)據(jù)的頻繁項(xiàng)集挖掘及其關(guān)聯(lián)規(guī)則分析方法;2)基于關(guān)聯(lián)規(guī)則的頻繁項(xiàng)集貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)校正。
關(guān)聯(lián)規(guī)則分析主要包括兩個(gè)階段:第一階段是從樣本數(shù)據(jù)中找到頻繁項(xiàng)集,第二階段是從這些頻繁項(xiàng)集中挖掘出關(guān)聯(lián)規(guī)則。本文中的最大頻繁項(xiàng)集挖掘和關(guān)聯(lián)規(guī)則分析的形式化描述如下:
1)由于關(guān)聯(lián)規(guī)則分析要求給定的數(shù)據(jù)是布爾型變量,故對給定的數(shù)據(jù)集D={V,Dv}(其中V表示隨機(jī)變量,Dv表示隨機(jī)變量V的樣本數(shù)據(jù))進(jìn)行二分類,使得分類后數(shù)據(jù)集可用于頻繁項(xiàng)挖掘。
2)使用Apriori算法[4]挖掘支持度Support=P(Vi1∪Vi2∪…∪Vin)≥θ的頻繁項(xiàng)Freq_itemi={Vi1,Vi2,…,Vin},其中θ為根據(jù)數(shù)據(jù)集分布規(guī)律所定義的最小支持度;并通過頻繁項(xiàng)集F=∪Freq_itemi得出最大頻繁項(xiàng)集Max_F={item|item∈F∩?(item∪(Vi?item)) ?F}。
3)對頻繁項(xiàng)集進(jìn)行關(guān)聯(lián)規(guī)則分析,由于變量的關(guān)聯(lián)規(guī)則并不顯式地表示變量間的因果關(guān)系,故本文中并不使用關(guān)聯(lián)規(guī)則分析結(jié)果作為貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)的先驗(yàn)知識,而是將關(guān)聯(lián)規(guī)則分析作為最大頻繁項(xiàng)集結(jié)構(gòu)學(xué)習(xí)的校正。關(guān)聯(lián)規(guī)則分析的具體表示如下:對于任意兩個(gè)隨機(jī)變量Vi,Vj∈V,計(jì)算其支持度和置信度,公式如下所示:
其中:Sup(Vi→Vj)表示關(guān)聯(lián)規(guī)則(Vi→Vj)的支持度,即Vi、Vj同時(shí)發(fā)生的概率P(Vi∪Vj),用來表示數(shù)據(jù)集中Vi、Vj同時(shí)發(fā)生的比例,反映了該關(guān)聯(lián)規(guī)則在數(shù)據(jù)庫中的重要性;Con(Vi→Vj)表示關(guān)聯(lián)規(guī)則(Vi→Vj)的置信度,即在變量Vi發(fā)生的情況下,Vj發(fā)生的條件概率,反映了該關(guān)聯(lián)規(guī)則的可信程度。本文通過篩選同時(shí)滿足最小支持度θ和最小置信度c的關(guān)聯(lián)規(guī)則{(Vi→Vj)|Sup(Vi→Vj)≥θ∩Con(Vi→Vj)≥c}確定最終的強(qiáng)關(guān)聯(lián)規(guī)則集Ass=∪(Vi→Vj)。
關(guān)聯(lián)規(guī)則分析可得出具有強(qiáng)相關(guān)性的節(jié)點(diǎn)對,因果關(guān)系也是一種關(guān)聯(lián)關(guān)系,故可用關(guān)聯(lián)規(guī)則分析結(jié)果Ass對最大頻繁項(xiàng)集Max_F的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行校正,提高最大頻繁項(xiàng)集貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)的準(zhǔn)確度,并以此作為總體樣本數(shù)據(jù)貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)的先驗(yàn)知識。
首先描述最大頻繁項(xiàng)集Max_F的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)過程。由于最大頻繁項(xiàng)集的節(jié)點(diǎn)數(shù)通常較少,故使用基于約束的結(jié)構(gòu)學(xué)習(xí)方法學(xué)習(xí)最大頻繁項(xiàng)集的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu),本文使用PC 算法[3]對其進(jìn)行結(jié)構(gòu)學(xué)習(xí)。PC 算法通過條件獨(dú)立性測試來學(xué)習(xí)數(shù)據(jù)的依賴結(jié)構(gòu),嘗試通過分析數(shù)據(jù)中的條件依賴的獨(dú)立關(guān)系給出最好解釋的某個(gè)網(wǎng)絡(luò)。具體過程如下:依次提取頻繁項(xiàng)Freq_itemi,從給定的樣本數(shù)據(jù)集D={V,Dv}中提取頻繁項(xiàng)數(shù)據(jù)集,對Dfreq_i分別進(jìn)行貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)得出貝葉斯結(jié)構(gòu)BNfreq_i,最終求得頻繁項(xiàng)集的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)集BNmax_f=∪BNfreq_i。
但由于PC算法對個(gè)體獨(dú)立性檢測的失敗比較敏感,某次檢測的錯(cuò)誤結(jié)果將誤導(dǎo)整個(gè)網(wǎng)絡(luò)的構(gòu)建過程,故使用上節(jié)中求得的關(guān)聯(lián)規(guī)則分析集Ass對頻繁項(xiàng)集的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)集BNmax_f進(jìn)行校正,以增加先驗(yàn)知識的魯棒性。具體過程如下:對于任意節(jié)點(diǎn)對(Vi→Vj)∈BNmax_f,若(Vi→Vj)∈Ass,則將該節(jié)點(diǎn)對加入先驗(yàn)知識白名單,即
同時(shí),若頻繁項(xiàng)集間的節(jié)點(diǎn)不存在關(guān)聯(lián)規(guī)則也無法得出貝葉斯網(wǎng)絡(luò)結(jié)構(gòu),則認(rèn)為其是不可能存在的變量依賴關(guān)系,并將其加入先驗(yàn)知識黑名單,即
下文中將利用本節(jié)求得的Priwhite_list和Priblack_list作為先驗(yàn)知識來進(jìn)行貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)。
本文基于BDeu[11]評分函數(shù)融合先驗(yàn)知識提出新的評分方法,并使用爬山搜索算法尋找評分最優(yōu)的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)。下面將詳細(xì)介紹融合先驗(yàn)知識的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法。
基于評分的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法利用評分函數(shù)對貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)的好壞進(jìn)行評判,并通過搜索算法尋找評分最優(yōu)的網(wǎng)絡(luò)結(jié)構(gòu)。因此,該算法主要包括兩個(gè)方面:評分函數(shù)的選取和搜索算法的選取。評分函數(shù)包括評價(jià)后驗(yàn)概率P(G|D)的評分函數(shù)以及同時(shí)考慮結(jié)構(gòu)擬合度和復(fù)雜度的評分函數(shù)。常用的評分函數(shù)有經(jīng)典評分函數(shù)BDeu[11]、K2[12]、最短信息準(zhǔn)則(Minimum Description Length,MDL)[13]、貝葉斯信息準(zhǔn)則(Bayesian Information Criterion,BIC)[14]和近幾年新提出的評分函數(shù)Min-BDeu&Max-BDeu[15]、NO TEARS[16]等。對于搜索算法,由于網(wǎng)絡(luò)空間的復(fù)雜度隨節(jié)點(diǎn)數(shù)增加呈指數(shù)增長,搜索出最優(yōu)的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)是個(gè)NP難問題,通常使用近似算法來求取次優(yōu)網(wǎng)絡(luò)結(jié)構(gòu)。本節(jié)將詳細(xì)介紹本文中使用的BDeu評分函數(shù)和爬山搜索算法。
定義1BDeu評分函數(shù)。該評分函數(shù)基于貝葉斯定理提出:對于給定的樣本數(shù)據(jù)D和模型結(jié)構(gòu)G,根據(jù)貝葉斯公式
將后驗(yàn)概率作為評分。由于P(D)不會影響不同的模型結(jié)構(gòu)G,故評分公式等價(jià)為:
將P(D|G)展開可得:
其中:θg表示給定模型結(jié)構(gòu)G時(shí)的參數(shù)。當(dāng)參數(shù)θg的先驗(yàn)分布滿足乘積狄利克雷分布時(shí),可以得到:
其中:Г()表示gamma 函數(shù);n表示隨機(jī)變量的個(gè)數(shù);rПi表示第i個(gè)隨機(jī)變量Xi的父節(jié)點(diǎn)集可能的取值數(shù);ri表示隨機(jī)變量Vi可能的取值數(shù);nijk表示隨機(jī)變量Vi取k,隨機(jī)變量Vi的父節(jié)點(diǎn)集取j時(shí)的樣本個(gè)數(shù);αijk為狄利克雷參數(shù),當(dāng)時(shí),該評分函數(shù)為BDeu 評分函數(shù),α*為等效樣本量(Equivalent Sample Size)。
算法1 爬山搜索算法。該搜索算法是一種局部擇優(yōu)的搜索算法,算法思路是從當(dāng)前結(jié)構(gòu)的相鄰結(jié)構(gòu)里,選取評分最高的結(jié)構(gòu)作為下一個(gè)當(dāng)前結(jié)構(gòu),重復(fù)操作直至所有相鄰結(jié)構(gòu)的評分都比當(dāng)前結(jié)構(gòu)低。
輸入 數(shù)據(jù)集D,評分函數(shù)SD(G);
輸出 使得分函數(shù)SD(G)最大的網(wǎng)絡(luò)結(jié)構(gòu)Gmax。
為了融合上文中得出的先驗(yàn)知識Priwhite_list和Priblack_list,本節(jié)提出一種新的評分模型,在評分函數(shù)中增加罰項(xiàng):
其中:rw表示滿足(Vi→Vj)∈Priwhite_list∩(Vi→Vj)∈G的元素個(gè)數(shù),nk表示第k個(gè)滿足(Vi→Vj)∈Priwhite_list∩(Vi→Vj)∈G的樣本個(gè)數(shù);rb表示滿足(Vi→Vj)∈Priblack_list∩(Vi→Vj)∈G的 元 素 個(gè) 數(shù),nt表 示 第t個(gè) 滿 足(Vi→Vj)∈Priblack_list∩(Vi→Vj)∈G的樣本個(gè)數(shù)。定義本文中融合先驗(yàn)的評分函數(shù)如下:
算法2 融合先驗(yàn)知識的結(jié)構(gòu)學(xué)習(xí)算法。該算法分為評分函數(shù)和搜索算法兩個(gè)階段,與未融合先驗(yàn)知識的結(jié)構(gòu)學(xué)習(xí)算法相比,該算法增加了基于頻繁項(xiàng)挖掘的先驗(yàn)知識獲取過程。具體算法描述如下:首先基于頻繁項(xiàng)挖掘獲取先驗(yàn)知識;再結(jié)合樣本數(shù)據(jù)特點(diǎn)確定評分函數(shù)的罰項(xiàng)權(quán)重γ的取值,并得出最終的評分函數(shù);最后使用爬山搜索算法尋找最優(yōu)的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)。
輸入 數(shù)據(jù)集D,評分函數(shù)SPrior(G),評分函數(shù)參數(shù)γ;
輸出 使得評分函數(shù)SPrior(G)最大的網(wǎng)絡(luò)結(jié)構(gòu)Gmax。
本章使用經(jīng)典數(shù)據(jù)集對BNSL-FIM 算法進(jìn)行有效性仿真驗(yàn)證,并通過對比融合先驗(yàn)知識所學(xué)習(xí)的網(wǎng)絡(luò)結(jié)構(gòu)和未融合先驗(yàn)知識所學(xué)習(xí)的網(wǎng)絡(luò)結(jié)構(gòu)與原始結(jié)構(gòu)的漢明距離來評判網(wǎng)絡(luò)結(jié)構(gòu)的優(yōu)劣性。
實(shí)驗(yàn)基于linux-4.19.128-microsoft-standard 平臺,使用python集成環(huán)境anaconda3,python版本為3.7.9。實(shí)驗(yàn)使用的6 個(gè)數(shù)據(jù)集均來源于公開在線平臺Bayesian Network Repository[17],并使用開源python 軟件包pyAgrum 對貝葉斯網(wǎng)絡(luò)進(jìn)行采樣,mlxtend 對采樣后數(shù)據(jù)進(jìn)行頻繁項(xiàng)集挖掘和關(guān)聯(lián)規(guī)則分析,pgmpy 對數(shù)據(jù)進(jìn)行貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí),最后通過比較學(xué)習(xí)到的網(wǎng)絡(luò)結(jié)構(gòu)與原始網(wǎng)絡(luò)結(jié)構(gòu)的漢明距離來評判該算法的有效性。
為了多維度驗(yàn)證BNSL-FIM 算法的有效性,實(shí)驗(yàn)過程中分別使用表1所示的6個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集進(jìn)行分析,其中包括小型貝葉斯網(wǎng)絡(luò)Asia、Sachs;中型貝葉斯網(wǎng)絡(luò)Alarm、Insurance 和大型貝葉斯網(wǎng)絡(luò)Hailfinder、Hepar2;并且在仿真過程中對不同數(shù)據(jù)量的樣本數(shù)據(jù)進(jìn)行了測試,通過驗(yàn)證不同類型的網(wǎng)絡(luò)結(jié)構(gòu)和不同大小的樣本數(shù)據(jù)更真實(shí)地判斷本文提出算法的優(yōu)劣性。
表1 實(shí)驗(yàn)使用的6個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集Tab.1 Six standard datasets used in experiments
實(shí)驗(yàn)首先通過采樣數(shù)據(jù)集挖掘出頻繁項(xiàng)集和關(guān)聯(lián)規(guī)則,并確定最終的先驗(yàn)知識;再使用本文中提出的融合先驗(yàn)知識的評分函數(shù)對數(shù)據(jù)集進(jìn)行貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí);最后計(jì)算學(xué)習(xí)所得網(wǎng)絡(luò)結(jié)構(gòu)與原始網(wǎng)絡(luò)結(jié)構(gòu)的漢明距離。所以在實(shí)驗(yàn)開始之前要根據(jù)樣本數(shù)據(jù)的分布特點(diǎn)對最小支持度θ、最小置信度c以及評分函數(shù)的罰項(xiàng)權(quán)重γ這些實(shí)驗(yàn)參數(shù)進(jìn)行設(shè)置。本文中最小支持度與最小置信度的取值是通過分析樣本數(shù)據(jù)特點(diǎn)選取的經(jīng)驗(yàn)值,具體參數(shù)值見本文源代碼[18]。下面以采樣大小為5 000的Asia網(wǎng)絡(luò)為例詳細(xì)闡述實(shí)驗(yàn)過程,其原始網(wǎng)絡(luò)結(jié)構(gòu)如圖2所示。
圖2 Asia數(shù)據(jù)集的原始網(wǎng)絡(luò)結(jié)構(gòu)Fig.2 Original network structure of Asia dataset
實(shí)驗(yàn)過程主要分為三個(gè)階段:第一階段對數(shù)據(jù)集進(jìn)行關(guān)聯(lián)規(guī)則分析,首先將數(shù)據(jù)集變量轉(zhuǎn)換為布爾值變量,設(shè)置最小支持度θ為0.75,最小置信度c為0.95,對數(shù)據(jù)集進(jìn)行頻繁項(xiàng)集挖掘和關(guān)聯(lián)規(guī)則分析,表2 是一次實(shí)驗(yàn)中對Aisa 采樣所得數(shù)據(jù)集進(jìn)行關(guān)聯(lián)規(guī)則分析的數(shù)據(jù),挖掘到的最大頻繁項(xiàng)集為:{(Either,XraY,Tub,Asia,Lung)};接著對最大頻繁項(xiàng)集進(jìn)行貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí),結(jié)合關(guān)聯(lián)規(guī)則分析結(jié)果確定最終的先驗(yàn)知識。
表2 Asia數(shù)據(jù)集的關(guān)聯(lián)規(guī)則分析Tab.2 Association rule analysis of Asia dataset
實(shí)驗(yàn)最終得到的先驗(yàn)知識如圖3 所示,分析先驗(yàn)知識的準(zhǔn)確率可以得出,實(shí)驗(yàn)中白名單先驗(yàn)知識的準(zhǔn)確率為100%,黑名單先驗(yàn)知識的準(zhǔn)確率為85.7%(虛線為錯(cuò)誤邊)。雖然先驗(yàn)知識的準(zhǔn)確率未達(dá)到100%,但由于本文中提出的評分函數(shù)是基于權(quán)重和節(jié)點(diǎn)對同時(shí)出現(xiàn)的概率來設(shè)定懲罰項(xiàng),故對于先驗(yàn)知識有一定的容錯(cuò)率。
圖3 Asia數(shù)據(jù)集中提取的先驗(yàn)知識Fig.3 Prior knowledge extracted from Asia dataset
第二階段使用未融合先驗(yàn)知識的算法和融合先驗(yàn)知識的算法分別對Asia 數(shù)據(jù)集進(jìn)行貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí),求得貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)如圖4 所示,可以看出,融合先驗(yàn)知識的結(jié)構(gòu)學(xué)習(xí)結(jié)果正確邊數(shù)(實(shí)線所示)多于未融合先驗(yàn)知識的結(jié)構(gòu)學(xué)習(xí)結(jié)果。
圖4 添加/不添加先驗(yàn)下Asia數(shù)據(jù)集的結(jié)構(gòu)學(xué)習(xí)結(jié)果Fig.4 Structure learning results on Asia dataset with/without prior knowledge
第三階段計(jì)算學(xué)習(xí)所得的網(wǎng)絡(luò)結(jié)構(gòu)與原始結(jié)構(gòu)的漢明距離,由于采樣數(shù)據(jù)的不確定性以及搜索過程中起始變量的不確定性,每次結(jié)果學(xué)習(xí)所得到的網(wǎng)絡(luò)結(jié)構(gòu)存在差異,故為提高實(shí)驗(yàn)結(jié)果的可靠性,每組數(shù)據(jù)進(jìn)行多次采樣與結(jié)構(gòu)學(xué)習(xí),最后計(jì)算所得結(jié)構(gòu)與原始結(jié)構(gòu)漢明距離的平均值,以樣本數(shù)量為5 000的Asia網(wǎng)絡(luò)為例,重復(fù)10次的實(shí)驗(yàn)結(jié)果如表3所示。
表3 Asia數(shù)據(jù)集的結(jié)構(gòu)學(xué)習(xí)結(jié)果(漢明距離)對比Tab.3 Structure learning results(Hamming distance)on Asia dataset
通過4.2 節(jié)所述的實(shí)驗(yàn)配置和實(shí)驗(yàn)方法,分別對不同樣本大小的6 個(gè)經(jīng)典網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行實(shí)驗(yàn)分析,結(jié)果如表4 所示。由表4可以看出,BNSL-FIM算法對Asia和Hailfinder網(wǎng)絡(luò)有較為顯著的提升效果,但對Alarm 和Hepar2 網(wǎng)絡(luò)的結(jié)構(gòu)學(xué)習(xí)幾乎沒有提升效果。一方面,這取決于數(shù)據(jù)集中的頻繁項(xiàng)集的特點(diǎn),比如頻繁項(xiàng)集中能否挖掘出有效的因果關(guān)系信息或先驗(yàn)信息是否可靠;另一方面,由于pgmpy軟件包提供的爬山搜索算法是基于可分解的評分函數(shù)[19]搜索網(wǎng)絡(luò),當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)較多時(shí),融合先驗(yàn)知識的評分函數(shù)的罰項(xiàng)會導(dǎo)致ΔS>epsilon的情況增多,搜索空間成倍增大,影響搜索效率,為平衡搜索時(shí)間和內(nèi)存使用情況,實(shí)驗(yàn)中調(diào)低了大型網(wǎng)絡(luò)中先驗(yàn)知識的權(quán)重取值,也影響了實(shí)驗(yàn)結(jié)果;同時(shí),BNSL-FIM 算法在小樣本數(shù)據(jù)下的效果沒有大樣本數(shù)據(jù)下效果明顯,這是由于小樣本數(shù)據(jù)信息量不足,更難挖掘出正確的關(guān)聯(lián)信息,這導(dǎo)致了小樣本情況下所獲取的先驗(yàn)知識準(zhǔn)確性較低,從而影響實(shí)驗(yàn)結(jié)果。
表4 兩個(gè)算法在6個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集上的不同樣本大小條件下的結(jié)構(gòu)學(xué)習(xí)結(jié)果(漢明距離)對比Tab.4 Structure learning results(Hamming distance)of two algorithms on 6 standard datasets under different sample sizes
本文針對如何提高貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)提出了一種以挖掘頻繁項(xiàng)集生成先驗(yàn)知識的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法,實(shí)驗(yàn)結(jié)果表明該算法對具有某些特點(diǎn)(比如網(wǎng)絡(luò)節(jié)點(diǎn)較少/頻繁項(xiàng)集中隨機(jī)變量存在因果關(guān)系)的網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)有較明顯的提升效果。但該算法仍然存在一些不足,比如降低了基于可分解評分函數(shù)的爬山搜索的算法性能,使得對于大型網(wǎng)絡(luò)的適應(yīng)性較差;對于小樣本數(shù)據(jù)和錯(cuò)誤先驗(yàn)信息的適應(yīng)能力仍需要提高。針對如何提升該算法的魯棒性和搜索算法的性能是下一步需要繼續(xù)研究的問題。