基于頻繁項挖掘的貝葉斯網絡結構學習算法BNSL-FIM

李昡熠，周 鋆*

（1.國防科技大學系統工程學院，長沙 410073；2.國防科技大學信息系統工程重點實驗室，長沙 410073）

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

0 引言

貝葉斯網絡是一種通用的概率圖模型，它可以表示隨機變量之間的相關性，是隨機變量聯合概率分布的一種圖形化表示，具有很強的可解釋性，在機器學習領域有著廣泛的應用，是領域研究的熱點之一。

然而在真實機器學習問題中，由于實際樣本數據存在噪聲和大小限制以及網絡空間搜索的復雜性，學習貝葉斯網絡的結構是一個NP 難（Non-deterministic Polynomial hard，NPhard）問題［1］。因此，如何減小貝葉斯網絡結構學習的誤差成為了貝葉斯網絡學習的研究難點之一。近年來，人們發現合理的利用先驗知識，可以提高貝葉斯結構學習的準確度［2］，成為當前貝葉斯網絡研究領域關注的重點。

本文提出一種基于頻繁項挖掘及關聯規則校正的結構學習算法BNSL-FIM（Bayesian Network Structure Learning based on Frequent Item Mining），通過確定頻繁項之間的結構關系，從中提取先驗信息，并設計算法輔助提升最終結構學習的準確度。

如圖1 所示，本文提出的BNSL-FIM 算法首先對樣本數據進行二分類處理以及頻繁項挖掘，通過關聯規則分析初步提取變量間的因果關系；然后使用PC 算法（PC-Algorithm）［3］對頻繁項進行結構學習，并利用關聯規則分析結果對頻繁項的結構學習進行校正，從而形成最后的先驗知識；最后以BDeu（Bayesian Dirichlet equivalent uniform）評分函數為基礎提出融合先驗知識的評分方法，并使用該評分方法對樣本數據進行貝葉斯網絡結構學習以得到最終的網絡結構。

圖1 BNSL-FIM算法流程Fig.1 Flowchart of BNSL-FIM

1 相關工作

經典的貝葉斯網絡學習研究側重于評分函數的設計和搜索方法的優化［4］，通過對可能的網絡結構和節點參數形式進行描述，提高學習算法的智能水平和問題求解能力，在單一的問題領域已經達到了一定的學習極限。這些研究偏重模型對訓練數據的可解釋性，學習準確度主要由訓練數據的質量決定，在數據有限或問題復雜的情況下，往往會出現過擬合的情況［5］，難以在實際中應用。

近年來，人們發現結合先驗知識可以改進貝葉斯網絡學習的準確度，如引入結構先驗［6］，或引入一定的約束條件［7］等，都可以大大減少結構學習的搜索空間，從而便于算法在有限的時間內找到可行解，因此設計先驗知識的引入方法，是改進現有貝葉斯網絡結構學習算法的一種思路。

關聯分析是數據挖掘中重要的研究內容，其核心思想是通過對數據的共現關系進行計算分析［8］，從而發現數據之間隱含的關系與規律。肖海慧等［9］提出了一種融合關聯規則與知識的貝葉斯網絡結構學習算法；Kharya 等［10］提出通過計算關聯規則置信度和提升度并結合貝葉斯網絡進行預測的方法。這些方法均嘗試通過挖掘節點間的關聯規則來提升貝葉斯網絡的準確度，但由于關聯規則并不顯式地表示變量的因果關系，上述方法均沒有實現通過挖掘關聯規則自動化地進行貝葉斯網絡結構學習。為了解決該問題，本文設計了一種新的基于頻繁項挖掘的貝葉斯網絡結構學習算法。

2 基于頻繁項挖掘的先驗知識獲取方法

本章主要介紹如何基于頻繁項挖掘貝葉斯網絡結構學習所使用的先驗知識，包括：1）基于貝葉斯結構學習樣本數據的頻繁項集挖掘及其關聯規則分析方法；2）基于關聯規則的頻繁項集貝葉斯網絡結構校正。

2.1 頻繁項挖掘及其關聯規則分析

關聯規則分析主要包括兩個階段：第一階段是從樣本數據中找到頻繁項集，第二階段是從這些頻繁項集中挖掘出關聯規則。本文中的最大頻繁項集挖掘和關聯規則分析的形式化描述如下：

1）由于關聯規則分析要求給定的數據是布爾型變量，故對給定的數據集D={V，Dv}（其中V表示隨機變量，Dv表示隨機變量V的樣本數據）進行二分類，使得分類后數據集可用于頻繁項挖掘。

2）使用Apriori算法［4］挖掘支持度Support=P(Vi1∪Vi2∪…∪Vin)≥θ的頻繁項Freq_itemi={Vi1，Vi2，…，Vin}，其中θ為根據數據集分布規律所定義的最小支持度；并通過頻繁項集F=∪Freq_itemi得出最大頻繁項集Max_F={item|item∈F∩?(item∪(Vi?item)) ?F}。

3）對頻繁項集進行關聯規則分析，由于變量的關聯規則并不顯式地表示變量間的因果關系，故本文中并不使用關聯規則分析結果作為貝葉斯網絡結構學習的先驗知識，而是將關聯規則分析作為最大頻繁項集結構學習的校正。關聯規則分析的具體表示如下：對于任意兩個隨機變量Vi，Vj∈V，計算其支持度和置信度，公式如下所示：

其中：Sup(Vi→Vj)表示關聯規則(Vi→Vj)的支持度，即Vi、Vj同時發生的概率P(Vi∪Vj)，用來表示數據集中Vi、Vj同時發生的比例，反映了該關聯規則在數據庫中的重要性；Con(Vi→Vj)表示關聯規則(Vi→Vj)的置信度，即在變量Vi發生的情況下，Vj發生的條件概率，反映了該關聯規則的可信程度。本文通過篩選同時滿足最小支持度θ和最小置信度c的關聯規則{(Vi→Vj)|Sup(Vi→Vj)≥θ∩Con(Vi→Vj)≥c}確定最終的強關聯規則集Ass=∪(Vi→Vj)。

2.2 基于最大頻繁項集的結構學習與校正

關聯規則分析可得出具有強相關性的節點對，因果關系也是一種關聯關系，故可用關聯規則分析結果Ass對最大頻繁項集Max_F的貝葉斯網絡結構進行校正，提高最大頻繁項集貝葉斯網絡結構的準確度，并以此作為總體樣本數據貝葉斯網絡結構學習的先驗知識。

首先描述最大頻繁項集Max_F的貝葉斯網絡結構學習過程。由于最大頻繁項集的節點數通常較少，故使用基于約束的結構學習方法學習最大頻繁項集的貝葉斯網絡結構，本文使用PC 算法［3］對其進行結構學習。PC 算法通過條件獨立性測試來學習數據的依賴結構，嘗試通過分析數據中的條件依賴的獨立關系給出最好解釋的某個網絡。具體過程如下：依次提取頻繁項Freq_itemi，從給定的樣本數據集D={V，Dv}中提取頻繁項數據集，對Dfreq_i分別進行貝葉斯網絡結構學習得出貝葉斯結構BNfreq_i，最終求得頻繁項集的貝葉斯網絡結構集BNmax_f=∪BNfreq_i。

但由于PC算法對個體獨立性檢測的失敗比較敏感，某次檢測的錯誤結果將誤導整個網絡的構建過程，故使用上節中求得的關聯規則分析集Ass對頻繁項集的貝葉斯網絡結構集BNmax_f進行校正，以增加先驗知識的魯棒性。具體過程如下：對于任意節點對(Vi→Vj)∈BNmax_f，若(Vi→Vj)∈Ass，則將該節點對加入先驗知識白名單，即

同時，若頻繁項集間的節點不存在關聯規則也無法得出貝葉斯網絡結構，則認為其是不可能存在的變量依賴關系，并將其加入先驗知識黑名單，即

下文中將利用本節求得的Priwhite_list和Priblack_list作為先驗知識來進行貝葉斯網絡結構學習。

3 融合先驗知識的評分方法與結構學習

本文基于BDeu［11］評分函數融合先驗知識提出新的評分方法，并使用爬山搜索算法尋找評分最優的貝葉斯網絡結構。下面將詳細介紹融合先驗知識的貝葉斯網絡結構學習算法。

3.1 基本定義

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

定義1BDeu評分函數。該評分函數基于貝葉斯定理提出：對于給定的樣本數據D和模型結構G，根據貝葉斯公式

將后驗概率作為評分。由于P（D）不會影響不同的模型結構G，故評分公式等價為：

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

其中：θg表示給定模型結構G時的參數。當參數θg的先驗分布滿足乘積狄利克雷分布時，可以得到：

其中：Г（）表示gamma 函數；n表示隨機變量的個數；rПi表示第i個隨機變量Xi的父節點集可能的取值數；ri表示隨機變量Vi可能的取值數；nijk表示隨機變量Vi取k，隨機變量Vi的父節點集取j時的樣本個數；αijk為狄利克雷參數，當時，該評分函數為BDeu 評分函數，α*為等效樣本量（Equivalent Sample Size）。

算法1 爬山搜索算法。該搜索算法是一種局部擇優的搜索算法，算法思路是從當前結構的相鄰結構里，選取評分最高的結構作為下一個當前結構，重復操作直至所有相鄰結構的評分都比當前結構低。

輸入 數據集D，評分函數SD（G）；

輸出 使得分函數SD（G）最大的網絡結構Gmax。

3.2 融合先驗知識的結構學習

為了融合上文中得出的先驗知識Priwhite_list和Priblack_list，本節提出一種新的評分模型，在評分函數中增加罰項：

其中：rw表示滿足(Vi→Vj)∈Priwhite_list∩(Vi→Vj)∈G的元素個數，nk表示第k個滿足(Vi→Vj)∈Priwhite_list∩(Vi→Vj)∈G的樣本個數；rb表示滿足(Vi→Vj)∈Priblack_list∩(Vi→Vj)∈G的 元 素 個 數，nt表 示 第t個 滿 足(Vi→Vj)∈Priblack_list∩(Vi→Vj)∈G的樣本個數。定義本文中融合先驗的評分函數如下：

算法2 融合先驗知識的結構學習算法。該算法分為評分函數和搜索算法兩個階段，與未融合先驗知識的結構學習算法相比，該算法增加了基于頻繁項挖掘的先驗知識獲取過程。具體算法描述如下：首先基于頻繁項挖掘獲取先驗知識；再結合樣本數據特點確定評分函數的罰項權重γ的取值，并得出最終的評分函數；最后使用爬山搜索算法尋找最優的貝葉斯網絡結構。

輸入 數據集D，評分函數SPrior(G)，評分函數參數γ；

輸出 使得評分函數SPrior(G)最大的網絡結構Gmax。

4 實驗與結果分析

本章使用經典數據集對BNSL-FIM 算法進行有效性仿真驗證，并通過對比融合先驗知識所學習的網絡結構和未融合先驗知識所學習的網絡結構與原始結構的漢明距離來評判網絡結構的優劣性。

4.1 實驗配置

實驗基于linux-4.19.128-microsoft-standard 平臺，使用python集成環境anaconda3，python版本為3.7.9。實驗使用的6 個數據集均來源于公開在線平臺Bayesian Network Repository［17］，并使用開源python 軟件包pyAgrum 對貝葉斯網絡進行采樣，mlxtend 對采樣后數據進行頻繁項集挖掘和關聯規則分析，pgmpy 對數據進行貝葉斯網絡結構學習，最后通過比較學習到的網絡結構與原始網絡結構的漢明距離來評判該算法的有效性。

4.2 實驗過程

為了多維度驗證BNSL-FIM 算法的有效性，實驗過程中分別使用表1所示的6個標準數據集進行分析，其中包括小型貝葉斯網絡Asia、Sachs；中型貝葉斯網絡Alarm、Insurance 和大型貝葉斯網絡Hailfinder、Hepar2；并且在仿真過程中對不同數據量的樣本數據進行了測試，通過驗證不同類型的網絡結構和不同大小的樣本數據更真實地判斷本文提出算法的優劣性。

表1 實驗使用的6個標準數據集Tab.1 Six standard datasets used in experiments

實驗首先通過采樣數據集挖掘出頻繁項集和關聯規則，并確定最終的先驗知識；再使用本文中提出的融合先驗知識的評分函數對數據集進行貝葉斯網絡結構學習；最后計算學習所得網絡結構與原始網絡結構的漢明距離。所以在實驗開始之前要根據樣本數據的分布特點對最小支持度θ、最小置信度c以及評分函數的罰項權重γ這些實驗參數進行設置。本文中最小支持度與最小置信度的取值是通過分析樣本數據特點選取的經驗值，具體參數值見本文源代碼［18］。下面以采樣大小為5 000的Asia網絡為例詳細闡述實驗過程，其原始網絡結構如圖2所示。

圖2 Asia數據集的原始網絡結構Fig.2 Original network structure of Asia dataset

實驗過程主要分為三個階段：第一階段對數據集進行關聯規則分析，首先將數據集變量轉換為布爾值變量，設置最小支持度θ為0.75，最小置信度c為0.95，對數據集進行頻繁項集挖掘和關聯規則分析，表2 是一次實驗中對Aisa 采樣所得數據集進行關聯規則分析的數據，挖掘到的最大頻繁項集為：｛（Either，XraY，Tub，Asia，Lung）｝；接著對最大頻繁項集進行貝葉斯網絡結構學習，結合關聯規則分析結果確定最終的先驗知識。

表2 Asia數據集的關聯規則分析Tab.2 Association rule analysis of Asia dataset

實驗最終得到的先驗知識如圖3 所示，分析先驗知識的準確率可以得出，實驗中白名單先驗知識的準確率為100%，黑名單先驗知識的準確率為85.7%（虛線為錯誤邊）。雖然先驗知識的準確率未達到100%，但由于本文中提出的評分函數是基于權重和節點對同時出現的概率來設定懲罰項，故對于先驗知識有一定的容錯率。

圖3 Asia數據集中提取的先驗知識Fig.3 Prior knowledge extracted from Asia dataset

第二階段使用未融合先驗知識的算法和融合先驗知識的算法分別對Asia 數據集進行貝葉斯網絡結構學習，求得貝葉斯網絡結構如圖4 所示，可以看出，融合先驗知識的結構學習結果正確邊數（實線所示）多于未融合先驗知識的結構學習結果。

圖4 添加/不添加先驗下Asia數據集的結構學習結果Fig.4 Structure learning results on Asia dataset with/without prior knowledge

第三階段計算學習所得的網絡結構與原始結構的漢明距離，由于采樣數據的不確定性以及搜索過程中起始變量的不確定性，每次結果學習所得到的網絡結構存在差異，故為提高實驗結果的可靠性，每組數據進行多次采樣與結構學習，最后計算所得結構與原始結構漢明距離的平均值，以樣本數量為5 000的Asia網絡為例，重復10次的實驗結果如表3所示。

表3 Asia數據集的結構學習結果（漢明距離）對比Tab.3 Structure learning results（Hamming distance）on Asia dataset

4.3 實驗結果與分析

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

表4 兩個算法在6個標準數據集上的不同樣本大小條件下的結構學習結果（漢明距離）對比Tab.4 Structure learning results（Hamming distance）of two algorithms on 6 standard datasets under different sample sizes

5 結語

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