劉軒 安喜彬 王忠

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

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

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

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

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

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

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

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

1 基礎(chǔ)知識(shí)及問(wèn)題描述

1.1 Hoeffding 樹(shù)

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

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

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

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

1.2 問(wèn)題描述

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

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

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

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

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

2 分布式Hoeffding樹(shù)算法

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

圖1：分布式Hoeffding樹(shù)算法框圖

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

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

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

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

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

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

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

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

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

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

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

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

3 算法性能分析

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

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

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

3.2 仿真結(jié)果分析

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

圖2：合成數(shù)據(jù)集性能測(cè)試曲線(xiàn)

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

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

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

4 結(jié)論

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