面向無線傳感網絡的分布式Hoeffding樹算法研究

劉軒 安喜彬 王忠

（火箭軍工程大學研究生院 陜西省西安市 710025）

隨著傳感器硬件、網絡技術的不斷發展，產生了大量的實時觀測數據，并且數據流傳輸的速度和體積都不斷增加[1-3]。數據流相比于傳統的數據模型，具有觀測速度快、數據量大、難以存儲的特點。數據流數據挖掘技術通常采用增量處理的方式完成數據分析，數據模型通過數據流不斷的完成更新，并可用于實時預測新數據[4-6]。因此，數據流挖掘技術正逐漸成為研究熱點[7,8]。

數據分類是數據流挖掘中一個重要的應用方向，目的在于從數據流中利用增量學習的方法訓練完成一個從觀測量到類標的映射關系，以便于對新數據進行分類預測，如垃圾郵件分類、銀行個人信用等級評估等。針對數據流分類問題，Domings[9]等人提出了一種建立決策樹的增量式Hoeffding樹算法（Hoeffding Tree, HT），算法僅需要對數據流內的數據訪問一次，就可以建立決策樹。該算法基于Hoeffding不等式僅依靠部分少量樣本就能找到概率意義上近似最優的分裂點。Hoeffding樹訓練過程中需要訪問完整的數據流信息，故無法直接應用于網絡中的分布式實時數據流，急需發展一種能處理分布式數據流的決策樹算法。

本文針對基于無線傳感網絡的實時數據流分類問題，提出了一種分布式自適應Hoeffding樹算法。本文主要貢獻點如下：

（1）提出了一種基于實時數據流的分布式Hoeffding樹算法(DHT)。網絡節點通過交流一些統計信息，使得單個節點生成的Hoeffding樹能有效逼近于集中式的Hoeffding樹模型。相比于HT算法，DHT算法能有效解決網絡中分布式實時數據流無法被單個節點訪問的問題，如傳遞原始數據通信代價高和保密數據無法傳輸的問題。

（2）假設數據之間是相互獨立的。在分布式一致性算法的幫助下，節點間通過通信一些統計信息，使得每個節點均能獲得該時間周期內整個網絡所觀測所有數據的數據特征。進而，網絡中每個節點根據該信息獨立完成模型更新，使得單個節點獲得模型為全局模型而非基于單個節點數據流的局部模型。

論文框架如下：第2節對分布式數據流的分類問題進行了描述，第3節提出了分布式Hoeffding樹。第4節對所提算法進行了算法復雜度分析及仿真驗證。第5節進行了總結。

符號定義：定義X為數據x的特征空間，D為數據特征X的維度，xpq代表第p個特征的第q個取值，y為數據的類別，K為類別的總個數。Xa和Xb分別代表葉子節點最優和第二優分裂特征。l代表Hoeffding樹的葉子節點，lm代表第m個葉子。Si為第i個節點的數據流，完整數據流為S={S1,…,SN}，N為網絡中節點個數。

1 基礎知識及問題描述

1.1 Hoeffding 樹

Domingos和Hulten[9]首次提出了一種針對數據流的增量式Hoeffding樹，只需對數據完成一次掃描，新數據根據每個分支的分裂點特征，分配至對應的葉子節點，而后進行一些相關統計量的更新，無需存儲原始數據，也不會多次調用原始數據。當葉子節點的樣本數達到一定值時，計算葉子節點的所有屬性的信息增益，如果最大和次大的信息增益之差滿足Hoeffding不等式時，葉子節點就在當前的最優分裂點處分裂，變成分支節點。

假定Xa和Xb為信息增益最大的兩個屬性，如果兩個的信息增益之差，大于Hoeffding界，則可以證明Xa為信息增益最大的屬性的置信度為1-δ[10-11]。Hoeffding界的計算方法為：

從概率角度來講，可以選擇為Xa分裂點，將該葉子節點變成分支節點。信息增益可以采用經典決策樹中的計算方法，如Gini增益，信息增益等。HT算法的具體流程見文獻[9]。

HT算法的一個關鍵特性是，在概率意義下，可以保證它生成的樹與批學習器生成的決策樹具有任意漸近性。也就是說，增量學習的方法并不顯著影響生成樹的性能。從算法流程和算法原理中可以看出，整個增量式算法能夠成功的核心在于當前葉子節點的最優分裂特征是否滿足Hoeffding界，這也將是分布式數據流構建Hoeffding樹的核心所在。

1.2 問題描述

假定一個由N個節點組成的傳感器網絡，通信拓撲可用圖模型描述，即其中N={1,2,…,N}代表了節點的集合，E描述了節點間的通信連接關系。若則代表了節點i與節點j是連通的，定義節點 的所有鄰居集合為且如果圖G內任何兩個節點之間均存在至少一條有向路，那么定義圖G是強連通[12]。定義圖G的加權鄰接矩陣當時，否則且一般來講，鄰接權重矩陣A是對稱雙隨機矩陣，即滿足，

網絡實時數據流具有快速到達、數據規模大和到達速率難以控制的特點，前一刻和后一刻到達的數據量可能相差很大。假設每個節點均獨立觀測數據流Si，每個觀測周期t內，各個節點所觀測到的數據個數不一。記為其中，代表時間t第i個節點收到的第1個觀測數據，為相應的類標，nt代表節點i在t時間周期內觀測數據的總個數，nt是動態變化的。

基于網絡的實時數據流，每個節點均有自身的數據流，若采用傳統的數據流處理方法，需將所有節點的每一時刻的數據傳輸到同一節點進行處理。這將消耗大量的通信資源，難以滿足實時性要求，且對中心節點的穩定性、可靠性要求較高，一旦中心節點損毀，該數據處理模型將終止。此外，在實際應用中，網絡中的節點往往屬于不同的部門和組織，直接交流原始的觀測數據可能會觸及到一些保密信息，因此，部門之間的數據交流被大大限制。構建分布式Hoeffding樹模型，將會有效解決上述問題。旨在網絡中各節點在不交換原始數據的情況下，均可得到與集中訓練效果一致的Hoeffding樹模型。整個算法設計過程中主要面臨兩方面的挑戰：

（1）在線挑戰：如何實時動態的處理數據流信息，無需重復的訪問歷史數據，就可動態構建性能優良的決策樹。

（2）分布式挑戰：如何在不交流原始數據流的前提下，使得各個節點都能得到適用于全局數據特征的Hoeffding樹。

2 分布式Hoeffding樹算法

本節基于分布式一致性策略，節點間通過交互部分統計量信息，單個節點近似得到全局的統計量信息，進而完成Gini值和Hoeffding界的計算，實現分布式Hoeffding樹的構建。算法流程如圖1所示。

圖1：分布式Hoeffding樹算法框圖

本文選取基尼指數的為分裂評估函數，具體的計算方法如下：假設分類問題中有K個類，對于給定的樣本集D，基尼指數為：

其中，Ck為樣本集D中第k類樣本的子集，K為類別個數。若樣本集合D以特征A下的某一個取值分裂，數據被分為D1和D2兩部分，即D2=D-D1。則在特征的條件下，集合D的基尼指數為：

網絡中每個節點均有自身的數據流，可獨自完成自身統計量的計算。記節點 的相關統計信息為若節點i根據自身的統計信息量，采用Hoeffding樹算法完成模型訓練，將得到適應于本地數據流的模型，但該模型并不適用全局數據流。如何讓單個節點得到全局的數據統計信息量，成為單個節點在不交換原始數據情況下，構建適用于全局數據流分類模型的關鍵。

近些年，隨著分布式算法的逐漸發展，節點間通過交互一些信息，就可以使每個節點趨于一致，常見的有共同尋找最大值、最小值、平均值等。由HT算法可知，統計量npqk(l)內涵蓋了決策樹第l個葉子完成生成過程中所需要的相關信息，通過npqk(l)可完成Ck(l)、D(l)、D1(l)及D2(l)等量的計算。單個節點i期望得到每個葉子相關的全局統計信息，主要包括以下內容：

經過充分迭代后，可得：

經過一致性算法后，單個節點可近似得到全局信息npqk(l)[16-17]。式（4）基尼指數計算中，均為相關統計量的比值量，可有效消除公式中網絡總節點數N帶來的影響，整個分裂特征選取的相關計算不再包含全局量，單個節點可獨立完成分裂特征的選取和Hoeffding界ε的計算，見式（1），進而獨自構造Hoeffding樹模型。分布式Hoeffding樹算法概括見算法1。

算法1 分布式Hoeffding樹(DHT)輸入：樣本數據流Si，屬性集合X，信息增益函數G(·)，預定的置信度δ；輸出：實時決策樹HTi；1. 用單個節點（根節點）初始化HTi，屬性集為；2. For 每一類yk；3. For 每個屬性的每個取值xpq設定統計量；4. 設定初始值為0，npqk(l1)=0；5. For 樣本流Si中每一個樣本(x,yk)；6. 將新樣本數據(x,y)按照樹結構劃分到實時決策樹HT對應的葉子節點l；7. 樣本(x,y)過樹節點的統計量npqk(l)加1；8. 一致性網絡中葉子節點l的統計信息量，ConsensusTheStatistics(l)；9. 試圖分裂葉子節點l，AttempToSplit (l)；10. 返回：實時決策樹HTi。函數1 ConsensusTheStatistics(l)1. 網絡節點i獨自更新統計量ni pqk；2. 與鄰居節點交互統計量信息ni pqk；3. 使用一致性策略更新；4. 返回：。函數2 AttempToSplit (l)

1. 記葉子節點樣本數最多的類為葉子l的類別；

2. If 葉子節點l中的樣本不屬于同一類；

3. 基于一致性的統計信息結果nipqk，計算各個屬性的基尼指數；

5. 基于nipqk，采用式(1)計算Hoeffding界ε；

相比于傳統的集中式HT算法，DHT算法引入了分布式一致性策略，主要用于獲得全局的統計信息，為單個節點獲得全數據流的最優分裂點、次優分裂點以及Hoeffding界的計算奠定基礎。DHT算法，不需要將網絡中所有數據流收集到一起集中處理，只需要鄰居節點之間傳輸一些關于數據的統計量信息，單個節點即可獲得全局數據流的數據特征，而后獨自完成Hoeffding樹的更新。由于單個節點的模型是基于全局數據流特征訓練而成，故該算法生成的Hoeffding樹能有效逼近于將網絡節點中所有節點的數據收集于同一節點后訓練的Hoeffding樹模型。

3 算法性能分析

本節采用合成數據集對提出的算法進行了驗證。介紹了合成數據生成方法和實際數據來源，并仿真對比分析了DHT與VFDT算法中集中式Hoeffding樹（HT）的分類結果。

3.1 合成數據生成方法

合成數據有較大的優勢，可以很簡單的生成符合多種概念漂移方式的數據，如突變型、漸變型和混合型，以檢驗算法適應概念漂移數據的能力。常見的MOA數據流生成器包含超平面數據集生成器[18]，、SEA數據集生成器[19]和LED生成器[20]，本文利用skmultiflow包內集成的上述數據流生成器，完成數據集的生成。采用上述三個數據生成器各自生成1個含有50000個樣本的概念漂移數據集。

3.2 仿真結果分析

采用合成數據集進對比提出的DHT標準的集中式的HT（VFDT）算法，仿真結果見圖2。

圖2：合成數據集性能測試曲線

從上述結果可知：

（1）基于一致性統計信息的分布式Hoeffding樹能有效應對分布式數據流帶來的單個無線傳感網絡節點無法訪問全局數據的困難，且單個無線傳感網絡節點的本地模型均能有效逼近與集中式Hoeffding樹的模型。

（2）從仿真圖中，可以看出在模型預測結果中仍然存在一定的震蕩，其原因可能為數據生成過程中含有一定的噪聲率，以及數據量過小導致模型泛化能力較差。

4 結論

針對無線傳感網絡的實時數據流分類問題，提出了一種分布式自適應Hoeffding樹算法。在模型生成過程中，不需要存儲和反復調用歷史數據集，僅需要訪問一次數據樣本。每個節點獨自完成自身數據流數據統計量的計算，而后在分布式一致性算法的幫助下，鄰居節點間通過交互一些統計信息，單個節點即可獲得該時間段內整個網絡內所有節點所觀測數據的數據特征。單個節點依據一致性的統計信息獨自完成分裂特征的選擇及實時決策樹的生成。由于Hoeffding樹的更新是基于該時間段內的全局數據特征的估計值完成的，故單個節點獲得的本地模型為全局模型而非基于單個節點數據流的局部模型。最后，仿真驗證了算法的有效性和可行性。