一種基於MapReduce的大規模貝葉斯網並行推理方法
2023-10-09 07:36:09 2
一種基於MapReduce的大規模貝葉斯網並行推理方法
【專利摘要】本發明涉及一種基於MapReduce的大規模貝葉斯網並行推理方法。針對大規模貝葉斯網中節點數量多或各節點條件概率參數多而帶來的推理效率低、計算量大等缺點，以克服效率瓶頸為主要目標，利用分布式資料庫HBase來存儲大規模貝葉斯網，建立HBase查詢處理與貝葉斯網推理任務之間的關係，並基於MapReduce實現貝葉斯網的並行推理。給出的方法更符合數據分析、醫療診斷、工業控制、經濟預測等領域中實際問題的特點，具有更好的吻合度，可消除貝葉斯網節點數量的限制，對其中不確定性知識的表示、推理及應用等提供支撐技術。
【專利說明】—種基於MapReduce的大規模貝葉斯網並行推理方法
【技術領域】
[0001]本發明公開了一種基於MapReduce的大規模貝葉斯網並行推理方法，涉及基於MapReduce將大規模貝葉斯網存儲到分布式資料庫HBase、將貝葉斯網的概率推理轉換為HBase上的數據查詢處理、以及基於MapReduce實現貝葉斯網概率推理的方法。屬於人工智慧及信息處理領域。
【背景技術】
[0002]隨著數據採集手段和數據格式的日益多樣、數據規模的急劇增長，對數據中所蘊含知識的表達、理解和應用，越來越受到人們的關注。貝葉斯網(Bayesian Network)以圖模型來表達同時包含了概率分布和因果聯繫的不確定性知識，以定性和定量的方式表示隨機變量之間的相互依賴關係，成為當前不確定性知識表示和推理的基本框架。貝葉斯網被廣泛用於數據分析、醫療診斷、工業控制、經濟預測等領域，例如，基於貝葉斯網描述社交網中用戶之間的相互影響，描述基因片段之間的相互作用，等等。
[0003]由於貝葉斯網的構建和推理具有指數時間複雜度，傳統的貝葉斯網中節點上限一般為幾十個。但是，隨著各類數據的增長和新型應用的出現，用來反映其中所蘊含不確定性知識的貝葉斯網的規模也日益增大，這些大規模貝葉斯網的特點是節點數量多、各節點條件概率參數多。近年來，大規模貝葉斯網的構建及其在實際中的應用越來越受到關注，例如，陸洋(〈上海交通大學碩士論文〉，2013)針對基因數據分析提出了分塊學習與合併的大規模貝葉斯網構建方法。針對大規模貝葉斯網的概率推理問題，為了儘可能提高推理效率，公知的方法將貝葉斯網中的特定結構用於加速概率推理、提出了並行的精確推理或近似推理等技術。胡春玲等(〈模式識別與人工智慧〉，2011，24 (6):846-855)改進了基於鄰接樹的精確推理算法，向光軍等(〈雲南大學學報〉，2010，32 (4):392-395)對變量消元的精確推理算法進行並行化，楊峰(〈合肥工業大學碩士論文>，2008)基於抽樣技術進行近似推理，孫詠梅等(〈專利2011110319410〉，2012)引入本體和用戶反饋來提高推理速度。這些方法從一定程度上提高了貝葉斯網推理的效率，但是對於持續增長的貝葉斯網規模和複雜的實際應用，仍然無法提供一種具有可擴展性、對貝葉斯網規模不敏感的普適性推理方法。
[0004]描述不確定性知識的大規模貝葉斯網，本身就是一個規模較大的數據源，而MapReduce是有效處理海量、分布式數據的編程模型。針對海量數據及相關的知識發現問題，公知的方法以MapReduce作為並行算法設計與實現的基礎，克服了傳統集中式算法無法並行處理海量數據的不足，使許多計算複雜度極高的算法仍能較好地適應許多海量數據挖掘與分析的需求。周家帥等(〈專利201210157463.X〉，2012)提出了基於MapReduce的大圖上距離連接查詢方法，李莉仙等(〈計算機系統應用>，2013，22 (2):108-111)提出了MapReduce框架下的樸素貝葉斯算法並行化方法，王源(〈雲南大學碩士論文>，2013)提出了基於MapReduce的貝葉斯網學習方法。但是,這些基於MapReduce的方法並未涉及大規模貝葉斯網的推理。
[0005]本發明針對大規模貝葉斯網的高效推理問題，利用運行在Hadoop分布式文件系統HDFS之上的分布式資料庫HBase，將大規模貝葉斯網視為大規模數據，提出了將大規模貝葉斯網存儲到HBase的方法，建立了貝葉斯網推理任務與分布式資料庫查詢處理之間的關係，基於MapReduce給出了通過分布式資料庫的查詢處理來實現貝葉斯網並行推理的方法。為大規模貝葉斯網的高效推理提供了一種伸縮性好、使用開源工具的新方法，為不確定性知識表示及相關分析、預測和決策等應用提供了一種新的技術基礎。
【發明內容】
[0006]、本發明的目的在於
提供一種基於MapReduce的大規模貝葉斯網並行推理方法。針對大規模貝葉斯網中節點數量多或各節點條件概率參數多而帶來的推理效率低、計算量大等缺點，以克服效率瓶頸為主要目標，利用分布式資料庫HBase來存儲大規模貝葉斯網，建立HBase查詢處理與貝葉斯網推理任務之間的關係，並基於MapReduce實現貝葉斯網的並行推理。給出的方法更符合數據分析、醫療診斷、工業控制、經濟預測等領域中實際問題的特點，具有更好的吻合度，可消除貝葉斯網節點數量的限制，對其中不確定性知識的表示、推理及應用等提供支撐技術。
[0007]、本發明按以下步驟完成
本發明工藝流程為:首先，建立HBase資料庫中用來存儲大規模貝葉斯網的表，並基於MapReduce、以〈key, value〉方式並行地將貝葉斯網的有向無環圖結構和各節點的條件概率參數表存儲到HBase表中；然後，對貝葉斯網上的推理任務進行分解，基於MapReduce以並行的方式查詢HBase中相應的概率參數，並通過這些概率參數的乘法和加法運算得到推理任務所涉及的邊 緣概率分布，進而得到概率推理結果。
[0008]大規模貝葉斯網的分布式存儲
一個貝葉斯網是一個有向無環圖，表示為G=(K，幻，其中:K={^，…，兒}為節點的集合，η為G中節點的個數χΕ為有向邊的集合；每個節點為(I^i </?)有一張條件概率參數表，簡記為CPT，描述了為的父親節點集/?^.)對為的影響，包含為不同取值的條件概率/IZMai)) ,/Mai)為/?的值。為了能高效地進行大規模貝葉斯網的概率推理，首先將貝葉斯網存儲到磁碟上，即保存以下兩類信息:貝葉斯網中節點間的父子關係，以及各節點的條件概率參數表。
[0009]對於運行在Hadoop分布式文件系統HDFS之上的分布式資料庫HBase，可通過Hadoop主節點(NameNode)來操作HBase。貝葉斯網的存儲，就是將上述兩類信息按照HBase的格式分布式地存儲到Hadoop平臺中的各數據節點(DataNode)上。
[0010]分別針對G中的每個節點為.,將尤、/? Gi)及為.的條件概率參數表以〈key, value〉形式、作為一行存儲到HBase的表Tw中，其中為為行標識；key表示為「列族名=列族成員」形式，尤為列族名，(a》為列族成員;value為/7Cai !/? (a》)。對於每個節點尤，基於MapReduce,使用Map函數並行地讀取為.的條件概率參數表中的每一個/7Cai \Pa (a,.))值，並存儲為 Tw 中邏輯形式為(Aj I I Aj Pa (A1) =a1Pa (?) | | Piaj \Pa (.a,)))的一行，「 | | 」為行標識、key和value的邏輯分隔符。從而,可通過Hadoop主節點來訪問HBase,進而支持貝葉斯網的推理。
[0011]貝葉斯網的並行推理以後驗概率計算為典型代表的概率計算，是貝葉斯網推理的幾類任務，其本質是查找各節點的條件概率參數表、並利用貝葉斯網中的條件獨立性來簡化聯合概率分布的計算。貝葉斯網G之上的後驗概率計算，就是計算給定證據節點值情形下查詢節點值的概率，表示為產(^7|萬=e)，其中必和0分別為證據節點和查詢節點，萬E V, Q E V,E n Φ於和7分別為萬和0的值。
[0012]首先，分解概率推理任務。
[0013]根據
【權利要求】
1.一種基於MapReduce的大規模貝葉斯網並行推理方法，其特徵在於:按以下步驟完成: (1)大規模貝葉斯網的分布式存儲 一個貝葉斯網是一個有向無環圖，表示為G=(K，幻，其中:K={^，…，兒}為節點的集合，η為G中節點的個數χΕ為有向邊的集合；每個節點為(I^i </?)有一張條件概率參數表，簡記為CPT，描述了為的父親節點集/?^.)對為的影響，包含為不同取值的條件概^Pia1IPaia1)),Paia1)為/?^.)的值，為了能高效地進行大規模貝葉斯網的概率推理，首先將貝葉斯網存儲到磁碟上，即保存以下兩類信息:貝葉斯網中節點間的父子關係，以及各節點的條件概率參數表； 對於運行在Hadoop分布式文件系統HDFS之上的分布式資料庫HBase,可通過Hadoop主節點(NameNode)來操作HBase，貝葉斯網的存儲，就是將上述兩類信息按照HBase的格式分布式地存儲到Hadoop平臺中的各數據節點(DataNode)上； 分別針對G中的每個節點尤,將尤)/? (Aj)及Ai的條件概率參數表以〈key, value)形式、作為一行存儲到HBase的表Tw中，其中-Jj為行標識；key表示為「列族名=列族成員」形式，為.作⑷)為列族名，(a》為列族成員；value為/7Cai l/Ma》)，對於每個節點尤，基於MapReduce,使用Map函數並行地讀取為.的條件概率參數表中的每一個/7Cai \Pa (a,.))值，並存儲為 Tw 中邏輯形式為(Aj I I Aj Pa (A1) =a1Pa (?) | | Piaj \Pa (.a,)))的一行，「 | | 」為行標識、key和value的邏輯分隔符,從而,可通過Hadoop主節點來訪問HBase,進而支持貝葉斯網的推理； (2)貝葉斯網的並行推理 以後驗概率計算為典型代表的概率計算，是貝葉斯網推理的幾類任務，其本質是查找各節點的條件概率參數表、並利用貝葉斯網中的條件獨立性來簡化聯合概率分布的計算，貝葉斯網^之上的後驗概率計算，就`是計算給定證據節點值情形下查詢節點值的概率，表示為產(^7|萬=e)，其中必和0分別為證據節點和查詢節點，萬E V, Q E V,E Π Φ於和g分別為萬和0的值， 首先，分解概率推理任務，
根據
2.根據權利要求1所述的一種基於MapReduce的大規模貝葉斯網並行推理方法，其特徵在於:所述方法是指「信用卡欺詐檢測」的貝葉斯網推理方法，按以下步驟完成: (1)貝葉斯網的分布式存儲 針對存儲「信用卡欺詐檢測」貝葉斯網的Tbn中的節點F、G、J、A、S,使用Map函數並行地讀取節點的條件概率參數表中的每一個值，並將其以〈key, value)形式存儲到中，對於F,若有八片/；) =0.1和=0.9，則存儲到HBase資料庫。表中的行以F作為行標識，列族為{F=i\ I I 0.1)和I I 0.9)， (2)分解概率推理任務 若已知證據節點值C^=a4, /=J1),查詢節點值Z7=Z11,推理任務為:計算|J=a4,/=J1)，由於
【文檔編號】G06F17/30GK103744878SQ201310709499
【公開日】2014年4月23日 申請日期:2013年12月21日 優先權日:2013年12月21日
【發明者】嶽昆, 徐娟, 方啟宇, 張驥先, 田凱琳, 劉惟一 申請人:雲南大學