劉軒 安喜彬 王忠

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

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

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

本文針對基于無線傳感網(wǎng)絡(luò)的實時數(shù)據(jù)流分類問題，提出了一種分布式自適應(yīng)Hoeffding樹算法。本文主要貢獻點如下：

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

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

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

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

1 基礎(chǔ)知識及問題描述

1.1 Hoeffding 樹

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

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

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

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

1.2 問題描述

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

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

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

（1）在線挑戰(zhàn)：如何實時動態(tài)的處理數(shù)據(jù)流信息，無需重復的訪問歷史數(shù)據(jù)，就可動態(tài)構(gòu)建性能優(yōu)良的決策樹。

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

2 分布式Hoeffding樹算法

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

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

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

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

網(wǎng)絡(luò)中每個節(jié)點均有自身的數(shù)據(jù)流，可獨自完成自身統(tǒng)計量的計算。記節(jié)點 的相關(guān)統(tǒng)計信息為若節(jié)點i根據(jù)自身的統(tǒng)計信息量，采用Hoeffding樹算法完成模型訓練，將得到適應(yīng)于本地數(shù)據(jù)流的模型，但該模型并不適用全局數(shù)據(jù)流。如何讓單個節(jié)點得到全局的數(shù)據(jù)統(tǒng)計信息量，成為單個節(jié)點在不交換原始數(shù)據(jù)情況下，構(gòu)建適用于全局數(shù)據(jù)流分類模型的關(guān)鍵。

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

經(jīng)過充分迭代后，可得：

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

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

1. 記葉子節(jié)點樣本數(shù)最多的類為葉子l的類別；

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

3. 基于一致性的統(tǒng)計信息結(jié)果nipqk，計算各個屬性的基尼指數(shù)；

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

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

3 算法性能分析

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

3.1 合成數(shù)據(jù)生成方法

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

3.2 仿真結(jié)果分析

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

圖2：合成數(shù)據(jù)集性能測試曲線

從上述結(jié)果可知：

（1）基于一致性統(tǒng)計信息的分布式Hoeffding樹能有效應(yīng)對分布式數(shù)據(jù)流帶來的單個無線傳感網(wǎng)絡(luò)節(jié)點無法訪問全局數(shù)據(jù)的困難，且單個無線傳感網(wǎng)絡(luò)節(jié)點的本地模型均能有效逼近與集中式Hoeffding樹的模型。

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

4 結(jié)論

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