基于頻繁項(xiàng)挖掘的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法BNSL-FIM

李昡熠，周 鋆*

（1.國(guó)防科技大學(xué)系統(tǒng)工程學(xué)院，長(zhǎng)沙 410073；2.國(guó)防科技大學(xué)信息系統(tǒng)工程重點(diǎn)實(shí)驗(yàn)室，長(zhǎng)沙 410073）

（?通信作者電子郵箱zhouyun@nudt.edu.cn）

0 引言

貝葉斯網(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í)問(wèn)題中，由于實(shí)際樣本數(shù)據(jù)存在噪聲和大小限制以及網(wǎng)絡(luò)空間搜索的復(fù)雜性，學(xué)習(xí)貝葉斯網(wǎng)絡(luò)的結(jié)構(gòu)是一個(gè)NP 難（Non-deterministic Polynomial hard，NPhard）問(wèn)題［1］。因此，如何減小貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)的誤差成為了貝葉斯網(wǎng)絡(luò)學(xué)習(xí)的研究難點(diǎn)之一。近年來(lái)，人們發(fā)現(xiàn)合理的利用先驗(yàn)知識(shí)，可以提高貝葉斯結(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），通過(guò)確定頻繁項(xiàng)之間的結(jié)構(gòu)關(guān)系，從中提取先驗(yàn)信息，并設(shè)計(jì)算法輔助提升最終結(jié)構(gòu)學(xué)習(xí)的準(zhǔn)確度。

如圖1 所示，本文提出的BNSL-FIM 算法首先對(duì)樣本數(shù)據(jù)進(jìn)行二分類處理以及頻繁項(xiàng)挖掘，通過(guò)關(guān)聯(lián)規(guī)則分析初步提取變量間的因果關(guān)系；然后使用PC 算法（PC-Algorithm）［3］對(duì)頻繁項(xiàng)進(jìn)行結(jié)構(gòu)學(xué)習(xí)，并利用關(guān)聯(lián)規(guī)則分析結(jié)果對(duì)頻繁項(xiàng)的結(jié)構(gòu)學(xué)習(xí)進(jìn)行校正，從而形成最后的先驗(yàn)知識(shí)；最后以BDeu（Bayesian Dirichlet equivalent uniform）評(píng)分函數(shù)為基礎(chǔ)提出融合先驗(yàn)知識(shí)的評(píng)分方法，并使用該評(píng)分方法對(duì)樣本數(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

1 相關(guān)工作

經(jīng)典的貝葉斯網(wǎng)絡(luò)學(xué)習(xí)研究側(cè)重于評(píng)分函數(shù)的設(shè)計(jì)和搜索方法的優(yōu)化［4］，通過(guò)對(duì)可能的網(wǎng)絡(luò)結(jié)構(gòu)和節(jié)點(diǎn)參數(shù)形式進(jìn)行描述，提高學(xué)習(xí)算法的智能水平和問(wèn)題求解能力，在單一的問(wèn)題領(lǐng)域已經(jīng)達(dá)到了一定的學(xué)習(xí)極限。這些研究偏重模型對(duì)訓(xùn)練數(shù)據(jù)的可解釋性，學(xué)習(xí)準(zhǔn)確度主要由訓(xùn)練數(shù)據(jù)的質(zhì)量決定，在數(shù)據(jù)有限或問(wèn)題復(fù)雜的情況下，往往會(huì)出現(xiàn)過(guò)擬合的情況［5］，難以在實(shí)際中應(yīng)用。

近年來(lái)，人們發(fā)現(xiàn)結(jié)合先驗(yàn)知識(shí)可以改進(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)知識(shí)的引入方法，是改進(jìn)現(xiàn)有貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法的一種思路。

關(guān)聯(lián)分析是數(shù)據(jù)挖掘中重要的研究?jī)?nèi)容，其核心思想是通過(guò)對(duì)數(shù)據(jù)的共現(xiàn)關(guān)系進(jìn)行計(jì)算分析［8］，從而發(fā)現(xiàn)數(shù)據(jù)之間隱含的關(guān)系與規(guī)律。肖?；鄣龋?］提出了一種融合關(guān)聯(lián)規(guī)則與知識(shí)的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法；Kharya 等［10］提出通過(guò)計(jì)算關(guān)聯(lián)規(guī)則置信度和提升度并結(jié)合貝葉斯網(wǎng)絡(luò)進(jìn)行預(yù)測(cè)的方法。這些方法均嘗試通過(guò)挖掘節(jié)點(diǎn)間的關(guān)聯(lián)規(guī)則來(lái)提升貝葉斯網(wǎng)絡(luò)的準(zhǔn)確度，但由于關(guān)聯(lián)規(guī)則并不顯式地表示變量的因果關(guān)系，上述方法均沒(méi)有實(shí)現(xiàn)通過(guò)挖掘關(guān)聯(lián)規(guī)則自動(dòng)化地進(jìn)行貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)。為了解決該問(wèn)題，本文設(shè)計(jì)了一種新的基于頻繁項(xiàng)挖掘的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法。

2 基于頻繁項(xiàng)挖掘的先驗(yàn)知識(shí)獲取方法

本章主要介紹如何基于頻繁項(xiàng)挖掘貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)所使用的先驗(yàn)知識(shí)，包括：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)校正。

2.1 頻繁項(xiàng)挖掘及其關(guān)聯(lián)規(guī)則分析

關(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ù)是布爾型變量，故對(duì)給定的數(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ī)律所定義的最小支持度；并通過(guò)頻繁項(xiàng)集F=∪Freq_itemi得出最大頻繁項(xiàng)集Max_F={item|item∈F∩?(item∪(Vi?item)) ?F}。

3）對(duì)頻繁項(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)知識(shí)，而是將關(guān)聯(lián)規(guī)則分析作為最大頻繁項(xiàng)集結(jié)構(gòu)學(xué)習(xí)的校正。關(guān)聯(lián)規(guī)則分析的具體表示如下：對(duì)于任意兩個(gè)隨機(jī)變量Vi，Vj∈V，計(jì)算其支持度和置信度，公式如下所示：

其中：Sup(Vi→Vj)表示關(guān)聯(lián)規(guī)則(Vi→Vj)的支持度，即Vi、Vj同時(shí)發(fā)生的概率P(Vi∪Vj)，用來(lái)表示數(shù)據(jù)集中Vi、Vj同時(shí)發(fā)生的比例，反映了該關(guān)聯(lián)規(guī)則在數(shù)據(jù)庫(kù)中的重要性；Con(Vi→Vj)表示關(guān)聯(lián)規(guī)則(Vi→Vj)的置信度，即在變量Vi發(fā)生的情況下，Vj發(fā)生的條件概率，反映了該關(guān)聯(lián)規(guī)則的可信程度。本文通過(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)。

2.2 基于最大頻繁項(xiàng)集的結(jié)構(gòu)學(xué)習(xí)與校正

關(guān)聯(lián)規(guī)則分析可得出具有強(qiáng)相關(guān)性的節(jié)點(diǎn)對(duì)，因果關(guān)系也是一種關(guān)聯(lián)關(guān)系，故可用關(guān)聯(lián)規(guī)則分析結(jié)果Ass對(duì)最大頻繁項(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)知識(shí)。

首先描述最大頻繁項(xiàng)集Max_F的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)過(guò)程。由于最大頻繁項(xiàng)集的節(jié)點(diǎn)數(shù)通常較少，故使用基于約束的結(jié)構(gòu)學(xué)習(xí)方法學(xué)習(xí)最大頻繁項(xiàng)集的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)，本文使用PC 算法［3］對(duì)其進(jìn)行結(jié)構(gòu)學(xué)習(xí)。PC 算法通過(guò)條件獨(dú)立性測(cè)試來(lái)學(xué)習(xí)數(shù)據(jù)的依賴結(jié)構(gòu)，嘗試通過(guò)分析數(shù)據(jù)中的條件依賴的獨(dú)立關(guān)系給出最好解釋的某個(gè)網(wǎng)絡(luò)。具體過(guò)程如下：依次提取頻繁項(xiàng)Freq_itemi，從給定的樣本數(shù)據(jù)集D={V，Dv}中提取頻繁項(xiàng)數(shù)據(jù)集，對(duì)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算法對(duì)個(gè)體獨(dú)立性檢測(cè)的失敗比較敏感，某次檢測(cè)的錯(cuò)誤結(jié)果將誤導(dǎo)整個(gè)網(wǎng)絡(luò)的構(gòu)建過(guò)程，故使用上節(jié)中求得的關(guān)聯(lián)規(guī)則分析集Ass對(duì)頻繁項(xiàng)集的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)集BNmax_f進(jìn)行校正，以增加先驗(yàn)知識(shí)的魯棒性。具體過(guò)程如下：對(duì)于任意節(jié)點(diǎn)對(duì)(Vi→Vj)∈BNmax_f，若(Vi→Vj)∈Ass，則將該節(jié)點(diǎn)對(duì)加入先驗(yàn)知識(shí)白名單，即

同時(shí)，若頻繁項(xiàng)集間的節(jié)點(diǎn)不存在關(guān)聯(lián)規(guī)則也無(wú)法得出貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)，則認(rèn)為其是不可能存在的變量依賴關(guān)系，并將其加入先驗(yàn)知識(shí)黑名單，即

下文中將利用本節(jié)求得的Priwhite_list和Priblack_list作為先驗(yàn)知識(shí)來(lái)進(jìn)行貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)。

3 融合先驗(yàn)知識(shí)的評(píng)分方法與結(jié)構(gòu)學(xué)習(xí)

本文基于BDeu［11］評(píng)分函數(shù)融合先驗(yàn)知識(shí)提出新的評(píng)分方法，并使用爬山搜索算法尋找評(píng)分最優(yōu)的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)。下面將詳細(xì)介紹融合先驗(yàn)知識(shí)的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法。

3.1 基本定義

基于評(píng)分的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法利用評(píng)分函數(shù)對(duì)貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)的好壞進(jìn)行評(píng)判，并通過(guò)搜索算法尋找評(píng)分最優(yōu)的網(wǎng)絡(luò)結(jié)構(gòu)。因此，該算法主要包括兩個(gè)方面：評(píng)分函數(shù)的選取和搜索算法的選取。評(píng)分函數(shù)包括評(píng)價(jià)后驗(yàn)概率P(G|D)的評(píng)分函數(shù)以及同時(shí)考慮結(jié)構(gòu)擬合度和復(fù)雜度的評(píng)分函數(shù)。常用的評(píng)分函數(shù)有經(jīng)典評(píng)分函數(shù)BDeu［11］、K2［12］、最短信息準(zhǔn)則（Minimum Description Length，MDL）［13］、貝葉斯信息準(zhǔn)則（Bayesian Information Criterion，BIC）［14］和近幾年新提出的評(píng)分函數(shù)Min-BDeu&Max-BDeu［15］、NO TEARS［16］等。對(duì)于搜索算法，由于網(wǎng)絡(luò)空間的復(fù)雜度隨節(jié)點(diǎn)數(shù)增加呈指數(shù)增長(zhǎng)，搜索出最優(yōu)的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)是個(gè)NP難問(wèn)題，通常使用近似算法來(lái)求取次優(yōu)網(wǎng)絡(luò)結(jié)構(gòu)。本節(jié)將詳細(xì)介紹本文中使用的BDeu評(píng)分函數(shù)和爬山搜索算法。

定義1BDeu評(píng)分函數(shù)。該評(píng)分函數(shù)基于貝葉斯定理提出：對(duì)于給定的樣本數(shù)據(jù)D和模型結(jié)構(gòu)G，根據(jù)貝葉斯公式

將后驗(yàn)概率作為評(píng)分。由于P（D）不會(huì)影響不同的模型結(jié)構(gòu)G，故評(píng)分公式等價(jià)為：

將P(D|G)展開(kāi)可得：

其中：θ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í)，該評(píng)分函數(shù)為BDeu 評(píng)分函數(shù)，α*為等效樣本量（Equivalent Sample Size）。

算法1 爬山搜索算法。該搜索算法是一種局部擇優(yōu)的搜索算法，算法思路是從當(dāng)前結(jié)構(gòu)的相鄰結(jié)構(gòu)里，選取評(píng)分最高的結(jié)構(gòu)作為下一個(gè)當(dāng)前結(jié)構(gòu)，重復(fù)操作直至所有相鄰結(jié)構(gòu)的評(píng)分都比當(dāng)前結(jié)構(gòu)低。

輸入 數(shù)據(jù)集D，評(píng)分函數(shù)SD（G）；

輸出 使得分函數(shù)SD（G）最大的網(wǎng)絡(luò)結(jié)構(gòu)Gmax。

3.2 融合先驗(yàn)知識(shí)的結(jié)構(gòu)學(xué)習(xí)

為了融合上文中得出的先驗(yàn)知識(shí)Priwhite_list和Priblack_list，本節(jié)提出一種新的評(píng)分模型，在評(píng)分函數(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)的評(píng)分函數(shù)如下：

算法2 融合先驗(yàn)知識(shí)的結(jié)構(gòu)學(xué)習(xí)算法。該算法分為評(píng)分函數(shù)和搜索算法兩個(gè)階段，與未融合先驗(yàn)知識(shí)的結(jié)構(gòu)學(xué)習(xí)算法相比，該算法增加了基于頻繁項(xiàng)挖掘的先驗(yàn)知識(shí)獲取過(guò)程。具體算法描述如下：首先基于頻繁項(xiàng)挖掘獲取先驗(yàn)知識(shí)；再結(jié)合樣本數(shù)據(jù)特點(diǎn)確定評(píng)分函數(shù)的罰項(xiàng)權(quán)重γ的取值，并得出最終的評(píng)分函數(shù)；最后使用爬山搜索算法尋找最優(yōu)的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)。

輸入 數(shù)據(jù)集D，評(píng)分函數(shù)SPrior(G)，評(píng)分函數(shù)參數(shù)γ；

輸出 使得評(píng)分函數(shù)SPrior(G)最大的網(wǎng)絡(luò)結(jié)構(gòu)Gmax。

4 實(shí)驗(yàn)與結(jié)果分析

本章使用經(jīng)典數(shù)據(jù)集對(duì)BNSL-FIM 算法進(jìn)行有效性仿真驗(yàn)證，并通過(guò)對(duì)比融合先驗(yàn)知識(shí)所學(xué)習(xí)的網(wǎng)絡(luò)結(jié)構(gòu)和未融合先驗(yàn)知識(shí)所學(xué)習(xí)的網(wǎng)絡(luò)結(jié)構(gòu)與原始結(jié)構(gòu)的漢明距離來(lái)評(píng)判網(wǎng)絡(luò)結(jié)構(gòu)的優(yōu)劣性。

4.1 實(shí)驗(yàn)配置

實(shí)驗(yàn)基于linux-4.19.128-microsoft-standard 平臺(tái)，使用python集成環(huán)境anaconda3，python版本為3.7.9。實(shí)驗(yàn)使用的6 個(gè)數(shù)據(jù)集均來(lái)源于公開(kāi)在線平臺(tái)Bayesian Network Repository［17］，并使用開(kāi)源python 軟件包pyAgrum 對(duì)貝葉斯網(wǎng)絡(luò)進(jìn)行采樣，mlxtend 對(duì)采樣后數(shù)據(jù)進(jìn)行頻繁項(xiàng)集挖掘和關(guān)聯(lián)規(guī)則分析，pgmpy 對(duì)數(shù)據(jù)進(jìn)行貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)，最后通過(guò)比較學(xué)習(xí)到的網(wǎng)絡(luò)結(jié)構(gòu)與原始網(wǎng)絡(luò)結(jié)構(gòu)的漢明距離來(lái)評(píng)判該算法的有效性。

4.2 實(shí)驗(yàn)過(guò)程

為了多維度驗(yàn)證BNSL-FIM 算法的有效性，實(shí)驗(yàn)過(guò)程中分別使用表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；并且在仿真過(guò)程中對(duì)不同數(shù)據(jù)量的樣本數(shù)據(jù)進(jìn)行了測(cè)試，通過(guò)驗(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)首先通過(guò)采樣數(shù)據(jù)集挖掘出頻繁項(xiàng)集和關(guān)聯(lián)規(guī)則，并確定最終的先驗(yàn)知識(shí)；再使用本文中提出的融合先驗(yàn)知識(shí)的評(píng)分函數(shù)對(duì)數(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)開(kāi)始之前要根據(jù)樣本數(shù)據(jù)的分布特點(diǎn)對(duì)最小支持度θ、最小置信度c以及評(píng)分函數(shù)的罰項(xiàng)權(quán)重γ這些實(shí)驗(yàn)參數(shù)進(jìn)行設(shè)置。本文中最小支持度與最小置信度的取值是通過(guò)分析樣本數(shù)據(jù)特點(diǎn)選取的經(jīng)驗(yàn)值，具體參數(shù)值見(jiàn)本文源代碼［18］。下面以采樣大小為5 000的Asia網(wǎng)絡(luò)為例詳細(xì)闡述實(shí)驗(yàn)過(guò)程，其原始網(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)過(guò)程主要分為三個(gè)階段：第一階段對(duì)數(shù)據(jù)集進(jìn)行關(guān)聯(lián)規(guī)則分析，首先將數(shù)據(jù)集變量轉(zhuǎn)換為布爾值變量，設(shè)置最小支持度θ為0.75，最小置信度c為0.95，對(duì)數(shù)據(jù)集進(jìn)行頻繁項(xiàng)集挖掘和關(guān)聯(lián)規(guī)則分析，表2 是一次實(shí)驗(yàn)中對(duì)Aisa 采樣所得數(shù)據(jù)集進(jìn)行關(guān)聯(lián)規(guī)則分析的數(shù)據(jù)，挖掘到的最大頻繁項(xiàng)集為：｛（Either，XraY，Tub，Asia，Lung）｝；接著對(duì)最大頻繁項(xiàng)集進(jìn)行貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)，結(jié)合關(guān)聯(lián)規(guī)則分析結(jié)果確定最終的先驗(yàn)知識(shí)。

表2 Asia數(shù)據(jù)集的關(guān)聯(lián)規(guī)則分析Tab.2 Association rule analysis of Asia dataset

實(shí)驗(yàn)最終得到的先驗(yàn)知識(shí)如圖3 所示，分析先驗(yàn)知識(shí)的準(zhǔn)確率可以得出，實(shí)驗(yàn)中白名單先驗(yàn)知識(shí)的準(zhǔn)確率為100%，黑名單先驗(yàn)知識(shí)的準(zhǔn)確率為85.7%（虛線為錯(cuò)誤邊）。雖然先驗(yàn)知識(shí)的準(zhǔn)確率未達(dá)到100%，但由于本文中提出的評(píng)分函數(shù)是基于權(quán)重和節(jié)點(diǎn)對(duì)同時(shí)出現(xiàn)的概率來(lái)設(shè)定懲罰項(xiàng)，故對(duì)于先驗(yàn)知識(shí)有一定的容錯(cuò)率。

圖3 Asia數(shù)據(jù)集中提取的先驗(yàn)知識(shí)Fig.3 Prior knowledge extracted from Asia dataset

第二階段使用未融合先驗(yàn)知識(shí)的算法和融合先驗(yàn)知識(shí)的算法分別對(duì)Asia 數(shù)據(jù)集進(jìn)行貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)，求得貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)如圖4 所示，可以看出，融合先驗(yàn)知識(shí)的結(jié)構(gòu)學(xué)習(xí)結(jié)果正確邊數(shù)（實(shí)線所示）多于未融合先驗(yàn)知識(shí)的結(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ù)的不確定性以及搜索過(guò)程中起始變量的不確定性，每次結(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é)果（漢明距離）對(duì)比Tab.3 Structure learning results（Hamming distance）on Asia dataset

4.3 實(shí)驗(yàn)結(jié)果與分析

通過(guò)4.2 節(jié)所述的實(shí)驗(yàn)配置和實(shí)驗(yàn)方法，分別對(duì)不同樣本大小的6 個(gè)經(jīng)典網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行實(shí)驗(yàn)分析，結(jié)果如表4 所示。由表4可以看出，BNSL-FIM算法對(duì)Asia和Hailfinder網(wǎng)絡(luò)有較為顯著的提升效果，但對(duì)Alarm 和Hepar2 網(wǎng)絡(luò)的結(jié)構(gòu)學(xué)習(xí)幾乎沒(méi)有提升效果。一方面，這取決于數(shù)據(jù)集中的頻繁項(xiàng)集的特點(diǎn)，比如頻繁項(xiàng)集中能否挖掘出有效的因果關(guān)系信息或先驗(yàn)信息是否可靠；另一方面，由于pgmpy軟件包提供的爬山搜索算法是基于可分解的評(píng)分函數(shù)［19］搜索網(wǎng)絡(luò)，當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)較多時(shí)，融合先驗(yàn)知識(shí)的評(píng)分函數(shù)的罰項(xiàng)會(huì)導(dǎo)致ΔS＞epsilon的情況增多，搜索空間成倍增大，影響搜索效率，為平衡搜索時(shí)間和內(nèi)存使用情況，實(shí)驗(yàn)中調(diào)低了大型網(wǎng)絡(luò)中先驗(yàn)知識(shí)的權(quán)重取值，也影響了實(shí)驗(yàn)結(jié)果；同時(shí)，BNSL-FIM 算法在小樣本數(shù)據(jù)下的效果沒(méi)有大樣本數(shù)據(jù)下效果明顯，這是由于小樣本數(shù)據(jù)信息量不足，更難挖掘出正確的關(guān)聯(lián)信息，這導(dǎo)致了小樣本情況下所獲取的先驗(yàn)知識(shí)準(zhǔn)確性較低，從而影響實(shí)驗(yàn)結(jié)果。

表4 兩個(gè)算法在6個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集上的不同樣本大小條件下的結(jié)構(gòu)學(xué)習(xí)結(jié)果（漢明距離）對(duì)比Tab.4 Structure learning results（Hamming distance）of two algorithms on 6 standard datasets under different sample sizes

5 結(jié)語(yǔ)

本文針對(duì)如何提高貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)提出了一種以挖掘頻繁項(xiàng)集生成先驗(yàn)知識(shí)的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法，實(shí)驗(yàn)結(jié)果表明該算法對(duì)具有某些特點(diǎn)（比如網(wǎng)絡(luò)節(jié)點(diǎn)較少/頻繁項(xiàng)集中隨機(jī)變量存在因果關(guān)系）的網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)有較明顯的提升效果。但該算法仍然存在一些不足，比如降低了基于可分解評(píng)分函數(shù)的爬山搜索的算法性能，使得對(duì)于大型網(wǎng)絡(luò)的適應(yīng)性較差；對(duì)于小樣本數(shù)據(jù)和錯(cuò)誤先驗(yàn)信息的適應(yīng)能力仍需要提高。針對(duì)如何提升該算法的魯棒性和搜索算法的性能是下一步需要繼續(xù)研究的問(wèn)題。