Storm平臺下基于稀疏ADtree的貝葉斯網絡分布式學習算法

丁 飛，莊 毅

(南京航空航天大學 計算機科學與技術學院， 南京 211106)

1 引 言

從給定的數據集中發現模型是數據挖掘與機器學習領域中的一個重要課題.很多算法的高復雜度使得高效地訓練模型極具挑戰.貝葉斯網絡是不確定知識推理中的常用模型之一.貝葉斯網絡的結構學習算法被證明是NP難問題[1].

由于貝葉斯網絡學習算法的復雜度很高，已有很多研究致力于加速算法，例如使用并行學習方法來學習貝葉斯網絡的結構.Sahin和Devasia利用了粒子群優化算法固有的并行行為，并將其應用到了并行化貝葉斯網絡學習算法中[2].Yu等人提出了PL-SEM(Parameter leaning structural expectation maximization)算法[3]，通過并行化結構期望最大化(structural expectation maximization，SEM)算法的期望最大化部分，充分利用了并行計算的資源.Madsen等人提出了一種并行化的方法[4]，同時考慮了縱向和橫向并行化來加速貝葉斯網絡學習過程中的條件獨立性測試.

但是，大規模的數據量仍可能會導致性能瓶頸.近年來，云計算的計算能力快速增長，為使用高級分布式編程范式加速貝葉斯網絡學習提供了新的途徑[5].Yue等人使用了Apache Hadoop的MapReduce范式擴展了經典的搜索與評分算法，動態地從大規模數據集中學習貝葉斯網絡[6].Basak等人將MapReduce框架應用到了貝葉斯網絡參數學習算法中，特別是EM算法[7,8].Arias等人使用Apache Spark框架提出了若干個基于MapReduce的貝葉斯網絡分類器[9]，減少了集群中的數據傳輸時間.

大部分現有的研究工作，通過反復執行MapReduce過程來執行分布式計算，操作的結果存儲在分布式文件系統(如Hadoop distributed file system, HDFS)中.很多學習算法以較粗的粒度進行分布化，并行度會受限于一些特定的參數，如貝葉斯網絡中的特征數量.重新設計適合并行計算的貝葉斯網絡學習算法，可以進一步充分利用計算資源，提高分布計算的并行度.另外，在迭代式的學習算法的時間消耗中，評分過程占到了最大的比重.由于在計算評分函數(如minimum description length, MDL)時，對于一個給定的概率圖，必須要對全體數據集的某些特征進行統計.學習算法頻繁而大量地訪問存儲在分布式文件系統上的數據，給計算性能帶來了很大的負擔.解決在分布式網絡中對全局數據頻繁進行隨機訪問的性能問題對于集群計算和機器學習領域是非常有價值的.

Apache Storm 的 Topology 框架為細粒度地分布化迭代式機器學習算法提供了新的技術途徑.Topology 框架是用于實時計算的分布式計算框架[10，11].不同于Hadoop和Spark使用"Map"和"Reduce"來批量地分布式處理數據，Storm使用"spout"和"bolt"流式地分布式處理數據.運行"spout"的計算節點將數據流發送到下游的"bolt"節點."bolt"計算節點執行自定義的操作，并且可以將數據再次發送到其他"bolt"計算節點[12].由"spout"和"bolt"組成的有向圖稱為一個Topology，類似于MapReduce框架，它定義了一個分布式任務的邏輯結構.另外Storm Topology框架還支持全分組策略，可以在計算節點內廣播數據元組.另外它也支持在計算任務的邏輯結構內存在閉環.因此，與Hadoop和Spark的MapReduce范式相比，Topology框架更適合進行迭代式的機器學習算法，如使用評分和搜索機制的貝葉斯網絡學習算法.

另外，稀疏ADtree為貝葉斯網絡分布式學習過程中頻繁隨機訪問數據集的性能問題提供了新的解決方法.稀疏ADtree(all-dimensions tree)[13，14]是kd-tree(k-dimensions tree)的一種泛化形式，用來存儲符號數據.稀疏ADtree常被用來加速特征選擇、關聯規則發現等需要計算統計信息的機器學習算法[15，16].稀疏ADtree的空間占用只與數據集的特征數量及其元數相關，與數據量無關.這使得它非常適合用于為大規模數據簡歷緩沖結構.由于它包含了所有可能的查詢的結果，在分布式環境下可以大幅地減少帶寬占用，從而加速算法的執行.

2 Storm平臺下基于稀疏ADTree的的貝葉斯網絡分布式學習算法

Storm平臺下基于稀疏ADTree的的貝葉斯網絡分布式學習算法通過使用Topology框架細粒度地分布化了貝葉斯網絡的學習過程，并使用稀疏ADtree緩解了計算評分函數的性能瓶頸.

2.1 基于Topology框架的貝葉斯網絡分布式學習機制

基于Topology框架的貝葉斯網絡分布式學習機制包含三種可以并行執行的任務：統計信息提取任務、狀態空間搜索任務和終止控制任務，以及三種數據流：輸入輸出數據流、候選貝葉斯網絡數據流和已評分貝葉斯網絡數據流.如圖1所示，三種任務分別記作task0、task1和task2.統計信息提取任務需要輸入初始貝葉斯網絡結構ε0和包含了終止條件的狀態εt兩個信息.統計信息提取任務的作用是從原始數據集提取計算貝葉斯網絡評分需要的統計信息，并存儲在稀疏ADtree中.狀態空間搜索任務從統計信息提取任務接收一個包含了稀疏ADtree的初始貝葉斯網絡狀態，并開始計算搜索空間內相鄰貝葉斯網絡狀態的評分.終止控制任務從狀態空間搜索任務接收每個已經被評分的貝葉斯網絡，并根據從統計信息提取任務所得到的終止條件來判定所得貝葉斯網絡的評分值是否滿足要求.當終止條件達到時，終止控制任務會向狀態空間搜索任務發送一對空元組，以指示所有狀態空間搜索節點停止計算.最后，終止控制任務將訓練完成的貝葉斯網絡εT輸出，算法結束.

圖1 基于Topology框架的貝葉斯網絡分布式學習機制Fig.1 Distributed Bayesian network learning mechanism based on Topology framework

使用基于Topology框架的貝葉斯網絡分布式學習機制搜索貝葉斯網絡的狀態空間時，統計信息提取任務和終止控制任務分別各由一個計算節點執行，狀態空間搜索由若干個計算節點并行執行.為了保證在分布式計算過程中，系統能夠應對貝葉斯網絡結構處理失敗或元組發送失敗等故障，本文利用了Apache Storm的acker組件的“錨定”(anchor)機制.在狀態空間搜索任務創建了新的候選貝葉斯網絡并向其他bolt計算節點發送的同時，該貝葉斯網絡被錨定至其前驅貝葉斯網絡.每個貝葉斯網絡被正確地評分和擴展后，Storm都會收到其對應的應答(ack).一旦元組的處理時間超時，acker組件會判定該元組的前驅元組處理失敗.Spout或bolt計算節點的fail函數會被回調來重新發送待評分的貝葉斯網絡.采用這樣的方式，基于Topology框架的貝葉斯網絡分布式學習機制可以保證由spout和bolt發出的每個貝葉斯網絡元組都能夠被完整地處理.

2.2 基于稀疏ADtree的統計信息提取算法

在學習貝葉斯網絡的結構時，需要使用完整的數據集才能計算得到一個貝葉斯網絡的評分值.數據集是分布式存儲在HDFS上的.雖然使用Storm Topology框架可以將搜索與評分任務細粒度地分布化，但是根據數據集的全局信息計算評分所需要的列聯表成為了新的性能瓶頸.當數據量巨大時，貝葉斯網絡的評分過程會嚴重延長學習貝葉斯網絡結構的整體時間.為了緩解這一性能瓶頸，本文提出基于稀疏ADtree的統計信息提取算法，計算貝葉斯網絡評分值所需要的統計信息存儲在占用空間極小的稀疏ADtree中，并將其分發給各個狀態空間搜索節點.避免了各狀態空間搜索節點從HDFS上訪問數據集來獲取全局的統計信息.

如圖2所示，稀疏ADtree由兩種節點組成：AD(All-dimensions)節點和Vary節點.AD節點的所有子節點都是Vary節點，Vary節點的所有子節點都是AD節點.AD節點用于存儲計數.一個AD節點存儲了數據集中符合查詢count(aj=vj,…,am=vm)的數據的數量，有M-j個Vary子節點.Vary節點用于區分不同的特征.每一個Vary節點對應于數據集中的一個特征aj，該節點有nj個AD子節點.此Vary節點的第k個AD子節點代表了查詢aj=k.ADtree中的所有AD節點就可以包含任何一個可能的查詢的統計結果.但其中仍然包含冗余的信息，可以通過省略MCV(most common value)節點及其子樹來減少空間占用.MCV被定義為一個Vary節點的子節點中計數最大的AD節點.被省略的子樹最有可能包含更多的節點，因此可以最大程度地縮小ADtree的空間.被省略子樹所包含的統計信息可以通過其兄弟子樹的信息及其相鄰Vary節點子樹下的信息恢復.另外，所有計數為0的AD節點及其子樹也被省略.

圖2 一個包含了2個特征、7條數據的稀疏ADtreeFig.2 A sparse ADtree with 2 features and 7 data samples

如算法1所示，基于稀疏ADtree的統計信息提取算法在Storm Topology框架的spout階段提取數據集的全局統計信息，并存儲致一個稀疏ADtree中，然后將其分發給各個狀態空間搜索任務.

算法1.基于稀疏ADtree的統計信息提取算法

常量It:用于識別終止狀態的常量

1.procedureExtractStatistics(ε0,εt)

2. 創建AD節點棧ADstack

3. 創建稀疏ADtree的根節點ADnode0

5.whileADstack不為空do

8.form:=i+1,…,Mdo

9. 創建Vary節點Vnodem作為ADnodei的子節點

10. 創建nm個空集childnums1,…,childnumsnm

12.vim:=第j條數據中特征ai的值

13. 將編號j加入到集合childnumsvm中

14.endfor

15.Vnodem.MCV:=arg maxk|childnumsk|

16.fork:=1,…,n,do

17.ifchildnumsk=φork=MCVthen

18. 將Vnodem的子樹設置為null

19.else

20. 將〈am+1,childnumsk〉壓入AD節點棧ADstack

21.endif

22.endfor

23.endfor

24.endwhile

25. 向各狀態空間搜索節點發送稀疏ADtree

27.ε0.parent:=null

28.ε0.score:=-∞

30.endprocedure

表1 一個具有7個樣本和2個特征的數據集Table 1 A dataset with 7 records and 2 attributes

2.3 基于稀疏ADtree的狀態空間搜索算法

用搜索和評分機制的貝葉斯網絡學習算法的性能瓶頸是將一個貝葉斯網絡擴展為若干貝葉斯網絡并對其評分的過程.由于此過程被大量地反復計算，因此將其并行化執行可以大幅度地加快計算速度.另外，由于采用了稀疏ADtree作為計算評分函數值的數據源，在計算評分函數值時，需要先從稀疏ADtree中構造列聯表，然后從中查詢得到需要的計數.列聯表的反復創建會延緩計算速度，因此本文提出了基于稀疏ADtree的貝葉斯網絡狀態空間搜索算法，使用本地列聯表集合來存儲已經創建過的列聯表，減少重復創建造成的時間開銷.

(1)

算法2.基于稀疏ADtree的狀態空間搜索算法

變量LocalConTab:存儲在計算節點的本地列聯表集合

2.ifεi=nullthen

3. 終止當前的狀態空間搜索任務

4.endif

5.ifct(ai(1),…,ai(m))?LocalConTabthen

6. 從稀疏ADtree遞歸構造列聯表ct(ai(1),…,ai(m))

7.endif

8.εi.score:=MDL(εn(i,j)|ct(ai(1),…,ai(m)))

10.for每一個εi相鄰的候選貝葉斯網絡結構do

12.endfor

13.endprocedure

為了計算MDL評分值，需要根據稀疏ADtree來構建查詢條件中的特征所對應的列聯表.列聯表ct(ai(1),…,ai(m))包含了所有特征ai(1),…,ai(m)的統計信息.由于不同的查詢條件包含的特征不同，所以所需要的列聯表也不同.因此，基于稀疏ADtree的貝葉斯網絡狀態空間搜索算法在每個狀態空間搜索節點中存儲了一個本地列聯表集合.每次構造的列聯表將本存儲在計算節點本地.在某個列聯表第二次需要被構造時，則無須再次創建，而是從本地列聯表集合中直接搜索到并查詢.在迭代計算的初期可能會由于大部分列聯表初次被創建，而使得計算過程較慢.但隨著迭代的進行，需要創建新列聯表的情況逐漸減少，計算過程會大幅加速.

在貝葉斯網絡εi的評分值計算完畢后，它將會被發送給終止控制節點，以判斷是否滿足收斂條件.最后，算法隨機增加、刪除或反轉一條貝葉斯網絡εi中的有向邊，形成若干個候選貝葉斯網絡.由貝葉斯網絡εi生成的第j個候選貝葉斯網絡記作εn(i,j).這些候選貝葉斯網絡將被發送給其他狀態空間搜索節點，并由其他節點進行評分和擴展.

表2 從圖2所示的稀疏ADtree構造的列聯表ct(a1,a2)Table 2 Contingency table ct(a1,a2) built from the sparse ADtree shown in Fig.2

例如，以圖2所示的稀疏ADtree為輸入進行查詢count(a1=3,a2=2).當算法判定接收到的貝葉斯網絡不為空后，首先在狀態空間搜索節點存儲的本地列聯表集合中查看是否已創建的列聯表ct(a1,a2).如果不存在，則開始創建列聯表的過程.從稀疏ADtree創建列聯表的算法使用Moore和Lee提出的MakeContab算法[14].所構造的列聯表如表2所示.每一行表示特征a1和a2的一種可能的取值組合.每行數據的最后一列是在整個數據集中符合該條件的數據的數量.此數量是在統計信息提取節點中使用基于稀疏ADtree的統計信息提取算法獲得的，并存儲在了稀疏ADtree中傳遞給了當前的狀態空間搜索節點.據此可以直接得到count(a1=3,a2=2)的值為2.類似地，可以根據稀疏ADtree計算得到所有MDL評分中mijk和mij*的值.最后，當前的貝葉斯網絡評分被存入εi.score，并被發送給了終止控制節點.最后，該貝葉斯網絡被擴展為若干個候選貝葉斯網絡，并被發送給其他狀態空間搜索節點進行下一步計算.

1http://storm.apache.org/.

在基于Topology架構的貝葉斯網絡分布式學習過程中，狀態搜索空間中不同的搜索分支并行地進行評分和搜索，候選貝葉斯網絡元組可以不按照特定的先后順序進行評分和擴展.這是由于，貝葉斯網絡結構學習的本質是從狀態空間中搜索得到一個最能表達數據集特征關聯的網絡結構.貝葉斯網絡的結構刻畫數據集的質量是由評分函數來評估的(如最小描述長度和赤池信息量準則).不同于最優化等需要迭代式算法解決的問題，貝葉斯網絡所有可能的結構所組成的狀態空間的搜索路徑并非必須按照一條路徑來搜索，而是可以由多個計算節點并行搜索和評分.在分布式環境下，不需要保證各個候選貝葉斯網絡被評分的先后順序.要分布式地學習貝葉斯網絡結構，只需要在執行過程中找到第一個具有足夠高評分值的網絡結構.另外，結構更為復雜的貝葉斯網絡會消耗更長的評分時間.如果限定更為簡單的貝葉斯網絡結構必須按照某個先后順序依次進行評分，會使得狀態空間中擁有復雜貝葉斯網絡結構的搜索分支成為瓶頸.允許狀態空間搜索節點在接收到一個元組后立刻根據稀疏ADtree進行評分、擴展和發送，可以充分利用分布式環境下的計算資源.

3 實驗與結果分析

本文使用了Apache Storm1(版本0.9.5)[10]實現了基于 Topology 框架的貝葉斯網絡分布式學習機制.使用Java(版本1.7.0)實現了貝葉斯網絡、基于稀疏ADtree的統計信息提取算法和基于稀疏ADtree貝葉斯網絡狀態空間搜索算法.使用Python(版本2.7.10)實現了稀疏ADtree和列聯表，并使用了Jython(版本2.5.3)將稀疏ADtree和列聯表嵌入到了Java實現的貝葉斯網絡分布式學習機制中.

本文在實驗中使用了費雪鳶尾花卉數據集(Iris dataset)和知識發現與數據挖掘杯99'競賽數據集(KDD1999 dataset)來訓練貝葉斯網絡.鳶尾花數據集由包含了150個鳶尾屬花卉的樣本組成.每條花卉數據包含四個特征，即花萼和花瓣的長度和寬度，以及該花卉的亞屬，即山鳶尾、變色鳶尾或維吉尼亞鳶尾.該數據集被廣泛應用于判別分析等統計學研究中.KDD1999數據集被用于第五屆國際知識發現與數據挖掘競賽，競賽的目的是構建一個網絡入侵檢測器來區分網絡攻擊數據與正常網絡數據.KDD1999數據集包含了500萬條網絡連接數據，每條數據包含TCP連接基本特征、內容特征和網絡流量統計特征等共42個特征.為了對比在具有不同特征維度和元數的數據集下的算法性能，我們將鳶尾花數據集擴展至10萬條數據，并取KDD1999的前10萬條數據進行實驗.

本文搭建了具有8個計算節點的Apache Storm云計算平臺，并使用基于 Topology 框架的貝葉斯網絡分布式學習機制訓練貝葉斯網絡.使用了1個計算節點來運行統計信息提取任務，使用了8個計算節點來運行狀態空間搜索任務，使用了1個計算節點來運行終止控制任務.為了驗證使用稀疏ADtree對貝葉斯網絡分布式學習的性能提升，記錄了每個計算節點上每次狀態空間搜索任務的開始時間和結束時間.另外，我們也分別獲取了統計信息提取任務、終止控制任務和整個分布式學習過程的總時間.使用兩個數據集對無稀疏ADtree優化和有稀疏ADtree優化的兩種情況分別進行了實驗以進行對比.使用鳶尾花數據集分布式訓練貝葉斯網絡的最大迭代次數設定為2000.使用KDD1999數據集分布式訓練貝葉斯網絡的最大迭代次數設定為3000.

首先，我們獲得按照開始時間排序的每次狀態空間搜索任務的執行時間(如圖3所示).圖表的縱軸表示某次狀態空間搜索任務的執行時間.圖表的橫軸表示此次狀態空間搜索任務是第幾次迭代.單機環境下訓練貝葉斯網絡的一次迭代，對應與分布式環境中某個計算節點執行一次狀態空間搜索任務.圖表中橫軸所示的"迭代次數"并不意味著在邏輯上右側的計算任務依賴于左側的計算，而是指的在時間上右側的計算任務發生在左側計算任務之后.圖3(a)和(b)為使用了鳶尾花數據集的測試結果，圖3(c)和(d)為使用了KDD1999數據集的測試結果.圖3(a)和(c)為未使用稀疏ADtree優化的貝葉斯網絡分布式學習的測試結果，圖3(b)和(d)為使用稀疏ADtree優化后的貝葉斯網絡分布式學習的測試結果.

圖3 稀疏ADtree優化前后狀態空間搜索任務的執行時間對比Fig.3 Comparison between the execution time of the state space searching task before and after the sparse ADtree optimization

使用鳶尾花數據集的實驗結果中，未使用稀疏ADtree優化的狀態空間搜索任務單次執行時間隨著迭代次數并沒有明顯變化(如圖3(a)所示).單次執行時間基本維持在0.1×104ms以內，最高不超過0.8×104ms.使用了稀疏ADtree優化后，狀態空間搜索任務的單次執行時間明顯地呈現出隨迭代次數減少的趨勢(如圖3(b)所示).在貝葉斯網絡訓練過程初期，單次執行時間最高不超過200ms.隨著執行速度不斷加快，單次執行時間最終基本穩定在50ms以內.使用KDD1999數據集的實驗結果中，也呈現出類似的規律.未使用稀疏ADtree優化的狀態空間搜索任務單次執行時間基本維持在0.2×104ms以內.使用了稀疏ADtree優化后，單次執行時間也明顯地呈現出隨著迭代次數逐漸減少、并最終維持在50ms以內的規律.

實驗結果表明了在使用了稀疏ADtree優化后，計算一個貝葉斯網絡的評分并生成其候選貝葉斯網絡的速度可以明顯加快.另外，由于基于稀疏ADtree的貝葉斯網絡狀態空間搜索算法在訓練過程初期需要頻繁創建新的列聯表，所以計算速度相對較慢.但隨著迭代逐漸進行，需要生成新的列聯表的可能性越來越小.大部分所需列聯表都已經根據稀疏ADtree恢復，并存儲在了狀態空間搜索節點.因此執行時間會不斷減少，并最終穩定在較低水平.

圖4 稀疏ADtree優化后的執行時間與未優化的時間加速比率Fig.4 Acceleration ratio of the execution time after sparse ADtree optimization to the time before optimization

另外，本文計算了使用稀疏ADtree優化和未優化的每次迭代執行時間的比值.如圖4所示，圖表的縱軸表示使用了稀疏ADtree優化后的單次執行時間除以未使用稀疏ADtree優化的單次執行時間.圖4(a)為使用鳶尾花數據集的實驗結果，圖4(b)為使用KDD1999數據集的實驗結果.圖表中的橫線表示優化前和優化后的執行時間相等，即比率為100%.低于此基準線的數據表示稀疏ADtree優化后執行速度更快，高于此基準線表示優化后速度更慢.

圖5 貝葉斯網絡分布式學習機制中各任務執行時間(鳶尾花數據集)Fig.5 Execution time of each task in the distributed Bayesian network learning machenics (Iris dataset)

實驗結果表明使用稀疏ADtree優化后，狀態空間搜索任務的執行速度在訓練初期是更慢的.這是由于不使用稀疏ADtree的方法不需要從稀疏ADtree中恢復統計信息(如MCV子樹所包含的統計信息).但在列聯表逐漸創建后，對一個貝葉斯網絡進行評分和擴展的時間大幅縮短.并且，算法的加速效果對于數據維度更少的鳶尾花數據集更加明顯.

最后，圖5和圖6分別給出了使用鳶尾花數據集和 KDD1999 數據集時，優化前后貝葉斯網絡分布式學習機制中各任務的執行時間.即：統計信息提取任務、狀態空間搜索任務和終止控制任務的執行時間，以及整個貝葉斯網絡分布式學習過程的總時間.圖表中給出的狀態空間搜索任務執行時間是所有計算節點在所有迭代中所消耗的時間總和.由于狀態空間搜索任務是在8個計算節點上分布式執行的，并且Storm集群在啟動后的初始化過程需要時間，因此三種任務的執行時間之和并不等于第四列的總時間.總時間是向Storm集群提交了計算任務到計算任務結束所測量到的時間差. 由圖5和圖6所示的實驗結果可以看出，在使用了稀疏ADtree優化后，因為統計信息提取任務需要根據數據集創建稀疏ADtree，其執行時間明顯增長.但狀態空間搜索任務的執行總執行時間大幅縮短.

圖6 貝葉斯網絡分布式學習機制中各任務執行時間(KDD1999數據集)Fig.6 Execution time of each task in the distributed Bayesian network learning machenics (KDD1999 dataset)

其分布式執行的方式可以使得該優勢進一步增強.終止控制任務的執行時間基本維持在很低的水平.由于狀態空間搜索任務的縮短的時間遠遠超過了統計信息提取任務所耽誤的時間，貝葉斯網絡分布式學習過程的總時間明顯縮短.

4 結 論

本文使用Apache Storm平臺提出了基于Topology框架的貝葉斯網絡分布式學習機制，細粒度地分布化了搜索與評分算法.并且，提出了基于稀疏ADtree的統計信息提取算法，在分布式學習貝葉斯網絡的初始階段將數據集的全局統計信息存儲在稀疏ADtree中，并分發給集群中各計算節點.另外，提出了基于稀疏ADtree的狀態空間搜索算法，使各計算節點從稀疏ADtree中恢復出列聯表來計算貝葉斯網絡的評分，從而避免了對分布式文件系統上數據集的頻繁訪問.本文使用了鳶尾花數據集和KDD1999數據集對算法的改進程度進行了測試.實驗結果表明，雖然構造稀疏ADtree會有一定的時間消耗，但各個計算節點上評分函數的執行時間可以大幅縮短.總體上，貝葉斯網絡結構分布式學習的過程得到了明顯加速.