[發明專利]基于Storm的馬爾可夫等價類模型分布式學習方法

有效

• 申請號: 201611122068.2
• 申請日: 2016-12-08
• 公開（公告）號: CN106650800B
• 公開（公告）日: 2020-06-30
• 發明（設計）人: 丁飛;莊毅;顧晶晶;鐘偉
• 申請（專利權）人: 南京航空航天大學
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 南京理工大學專利中心 32203
• 代理人: 馬魯晉

1.一種基于Storm的馬爾可夫等價類模型分布式學習方法，其特征在于，包括以下步驟：

步驟1、將馬爾可夫等價類模型的訓練數據集上傳至分布式文件系統HDFS中，通過Storm平臺的Topology框架對訓練數據集進行學習，創建四種云計算節點，分別是初始化節點node⁰、搜索節點node¹、評分節點node²和輸出節點node³；

步驟2、初始化節點node⁰創建初始馬爾可夫等價類狀態ε_i，使用初始馬爾可夫等價類狀態生成發送給node^k的狀態圖元組其中k為云計算節點編號，且0≤k≤3，并發送至任一搜索節點node¹以啟動搜索過程，向集群中唯一的輸出節點發送狀態圖元組是包含了搜索空間內第i個馬爾可夫等價類的狀態圖元組，是在搜索空間內的第j個相鄰狀態圖元組；

步驟3、搜索節點node¹根據從初始化節點node⁰和評分節點node²收到的當前狀態圖元組和前驅狀態圖元組為當前狀態圖元組生成標識符，將當前狀態圖元組發送給輸出節點node³，確定當前狀態圖元組的所有可能的合法修改操作符，并將應用操作符之后產生的狀態圖元組發送給任一評分節點node²，其中是在搜索空間內的唯一的直接前驅狀態圖元組；

步驟4、評分節點node²將從搜索節點node¹收到的當前狀態圖元組分布式地存儲在各評分節點中，并計算運行實例未存儲過的當前狀態圖元組的評分，將帶有評分值的狀態圖元組發送至搜索節點；

步驟5、輸出節點node³根據從初始化節點node⁰收到的終止條件來判斷帶有評分值的狀態圖元組是否達到了局部最優，如果達到了局部最優，則輸出該狀態圖元組中對應的馬爾可夫等價類模型，否則不做任何操作。

2.根據權利要求1所述的基于Storm的馬爾可夫等價類模型分布式學習方法，其特征在于：步驟2中馬爾可夫等價類狀態ε_i為一個三元組：

其中為表示一個馬爾可夫等價類模型的完全部分有向無環圖CPDAG,I_p(i)是ε_i前驅狀態的標識符，s_i是已求得的ε_i對數據集的擬合度評分；

所述狀態圖元組的公式為：

式中，K_i為根據馬爾可夫等價類狀態ε_i計算得到的散列值，I_n(i,j)為狀態圖元組的標識符，由搜索節點的運行實例的標識符和運行實例已搜索過的狀態數量組成。

3.根據權利要求1所述的基于Storm的馬爾可夫等價類模型分布式學習方法，其特征在于：步驟3中確定當前狀態圖元組的所有可能的合法修改操作符，具體是去除會導致其轉移至前驅狀態圖元組的操作符。

4.根據權利要求1所述的基于Storm的馬爾可夫等價類模型分布式學習方法，其特征在于：步驟4中評分節點node²使用分布式散列表DHT存儲馬爾可夫等價類搜索空間，N個評分節點僅存儲其接收到的狀態圖元組，第i個評分節點所存儲的狀態圖元組組成集合χ_i，各狀態圖元組集合滿足如下約束：

其中Ε為搜索空間中所有已搜索過的馬爾可夫等價類狀態所組成的集合，Ε是馬爾可夫等價類狀態全集的一個真子集，每個評分節點中的狀態圖元組集合是Ε的一個劃分。

5.根據權利要求1所述的基于Storm的馬爾可夫等價類模型分布式學習方法，其特征在于：步驟4中計算運行實例未存儲過的當前狀態圖元組的評分，具體采用MDL最小描述長度準則來計算馬爾可夫等價類狀態對數據集的擬合度評分，獲得擬合度評分最大的完全部分有向無環圖，具體按照如下公式求解：

其中為使得擬合度評分最大的完全部分有向無環圖，M為表示馬爾可夫等價類模型的CPDAG中的節點數量，q_i表示中第i個節點的父節點所有可能的組合，n_i為第i個節點可能的取值范圍，m_ijk為數據集中符合上面所說的三個條件的條目數量，M_f是馬爾可夫等價類模型中自由節點的數量，為代表數據集中第i個屬性的節點的父節點集合。