[發明專利]一種基于并行演化搜索的貝葉斯網絡結構學習方法

在審

• 申請號: 201810085728.7
• 申請日: 2018-01-29
• 公開（公告）號: CN108197665A
• 公開（公告）日: 2018-06-22
• 發明（設計）人: 林小光;鐘坤華;孫啟龍;張矩
• 申請（專利權）人: 中國科學院重慶綠色智能技術研究院
• 主分類號: G06K9/62
• 分類號: G06K9/62;G06N3/12
• 代理公司: 北京同恒源知識產權代理有限公司 11275
• 代理人: 趙榮之

本發明涉及一種基于并行演化搜索的貝葉斯網絡結構學習方法，屬于人工智能領域。該方法基于演化計算的思想，對評分搜索過程并行化處理，以實現高效貝葉斯網絡結構學習。本發明通過采用Map Reduce技術將遺傳演化算法與結構尋優過程相結合，以充分利用多臺服務器并行計算的能力實現高效快速學習。本發明將傳統的遺傳算法應用到云計算，利用分布式計算方法處理海量數據的能力和遺傳算法并行性和全局搜索能力，快速高效地進行海量數據中貝葉斯網絡結構學習，是目前技術沒有的，具有實質性的突破。

技術領域

本發明屬于人工智能領域，涉及一種基于并行演化搜索的貝葉斯網絡結構學習方法

背景技術

貝葉斯網絡是基于概率推理的數學模型，是貝葉斯方法的擴展，是目前不確定知識表達和推理領域最有效的理論模型之一。貝葉斯網絡的信息表達由兩部分組成，一是采用有向無環圖表示條件獨立性信息的貝葉斯網絡結構，網絡中的每個節點表示特定域中的一個變量，節點間的連接表示相互間因果關系；一是條件概率分布函數(或條件概率表)。

貝葉斯網絡結構學習是在給定一個數據樣本集合的前提下，尋找一個與訓練樣本集匹配最好的網絡結構。貝葉斯網絡結構學習的目的是獲得特定域中每一變量間的邏輯關系，可以通過評分搜索算法獲得貝葉斯網絡結構，其結構尋優過程是一個NP hard問題。現有解決方案包括K2學習算法、Tan學習算法、貝葉斯度量機制、條件似然評分方法等。

基于評分搜索的貝葉斯網絡結構學習算法的基本思想是從一個基本網絡結構出發，使用一定的搜索算法對結構進行改變，如加邊、減邊、改變邊的方向等，使用一定的評分函數對網絡結構進行評分，評分的結果決定了該網絡的保留與否。主要涉及到兩個問題，一是評分函數的選取；二是搜索算法的選擇。

在大數據環境下，數據維度高，樣本空間大，采用通常的學習算法進行貝葉斯網絡結構學習，過程處理繁瑣，耗時長。而單機處理能力有限，往往不能在合理的時間內迅速得到貝葉斯網絡結構，極大地限制了下一步分析和決策。

現行國內外主流貝葉斯網絡結構學習方法基本上都是采用串行處理，同時貝葉斯網絡結構學習是NP hard問題，因此，在大數據環境下傳統貝葉斯網絡結構學習過程的性能和效率都會比較低，很難在合理的時間內得到所需要的貝葉斯網絡結構。

發明內容

有鑒于此，本發明的目的在于提供一種基于并行演化搜索的貝葉斯網絡結構學習方法，基于演化計算的思想，對評分搜索過程并行化處理，以實現高效貝葉斯網絡結構學習。本發明通過采用Map Reduce技術將遺傳演化算法與結構尋優過程相結合，以充分利用多臺服務器并行計算的能力實現高效快速學習。

為達到上述目的，本發明提供如下技術方案：

一種基于并行演化搜索的貝葉斯網絡結構學習方法，包括以下步驟：

S1：使用馬爾可夫鏈蒙特卡羅方法(Markov Chain Monte Carlo,MCMC)對原始樣本數據進行隨機采樣；采用吉布斯方法對隨機采樣過程進行優化處理，在高維情況下使得抽樣效率更高；考慮轉移概率的存在，抽樣數據由若干相對獨立具有初步條件概率的數據子集構成；

S2：將S1產生的數據子集分別進行基因編碼，得到初始種群X_j，即若干個無邊圖；

S3：采用貝葉斯評分方法定義評價函數，即采用后驗概率最大的原則G*＝arg maxP(G|D)，其中，D表示數據集，G表示一個在貝葉斯網絡N上的網絡結構；對于任意的結點x_i，如果其父節點集為π_i，則這個貝葉斯網絡結構的評價函數定義為：