劉 偉,王 琦,于化龍

(江蘇科技大學(xué) 計(jì)算機(jī)學(xué)院,江蘇 鎮(zhèn)江 212003)

E-mail:weiliu@stu.just.edu.cn

1 相關(guān)工作

近年來(lái),無(wú)線(xiàn)傳感器網(wǎng)絡(luò)已廣泛應(yīng)用于生產(chǎn)生活的各個(gè)領(lǐng)域,在環(huán)境監(jiān)測(cè)[1]、現(xiàn)代農(nóng)業(yè)[2]、自然災(zāi)害預(yù)警[3]等領(lǐng)域發(fā)揮著重要的作用.為了獲取全面、準(zhǔn)確的信息,通常在監(jiān)控區(qū)域內(nèi)部署大量傳感器節(jié)點(diǎn).為了完成數(shù)據(jù)采集任務(wù),通常采用基于分簇的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)路由協(xié)議[4-7],即把網(wǎng)絡(luò)在邏輯上劃分為若干簇,每個(gè)簇由一個(gè)簇首和若干個(gè)簇內(nèi)成員節(jié)點(diǎn)構(gòu)成.簇內(nèi)成員節(jié)點(diǎn)負(fù)責(zé)采集感知數(shù)據(jù)并發(fā)送給簇首,簇首負(fù)責(zé)簇內(nèi)通信調(diào)度、數(shù)據(jù)融合以及發(fā)送數(shù)據(jù)至基站,基站以互聯(lián)網(wǎng)的方式最終將數(shù)據(jù)發(fā)送給用戶(hù).

無(wú)線(xiàn)傳感器網(wǎng)絡(luò)作為一種數(shù)據(jù)采集型網(wǎng)絡(luò),其數(shù)據(jù)是以數(shù)據(jù)流的形式傳遞給用戶(hù)[8,9],該數(shù)據(jù)流具有時(shí)間順序性、分布變化快速、潛在無(wú)限、數(shù)據(jù)間關(guān)聯(lián)性強(qiáng)等特點(diǎn)[10].針對(duì)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的數(shù)據(jù)特點(diǎn),如何準(zhǔn)確地對(duì)傳感器數(shù)據(jù)進(jìn)行精確的在線(xiàn)預(yù)測(cè),便成為一個(gè)急需解決的問(wèn)題.

傳統(tǒng)的基于機(jī)器學(xué)習(xí)方法的預(yù)測(cè)模型歸根結(jié)底是對(duì)某一靜態(tài)數(shù)據(jù)分布的學(xué)習(xí),即通過(guò)先驗(yàn)數(shù)據(jù)訓(xùn)練出一個(gè)誤差最小的預(yù)測(cè)模型,無(wú)需考慮因?yàn)閿?shù)據(jù)的變化而更新模型的問(wèn)題.但是,在無(wú)線(xiàn)傳感器數(shù)據(jù)流環(huán)境中,一些數(shù)據(jù)分布是隨著環(huán)境變化和時(shí)間推移而發(fā)生改變,且這種改變是不可預(yù)測(cè)的,即產(chǎn)生概念漂移現(xiàn)象[11],如在一個(gè)測(cè)量溫度的傳感器網(wǎng)絡(luò)中,某年可能出現(xiàn)極寒或極熱情況,則該年的數(shù)據(jù)分布將不同于歷史數(shù)據(jù).如果還是依靠舊數(shù)據(jù)訓(xùn)練的模型用于對(duì)新數(shù)據(jù)進(jìn)行預(yù)測(cè),則表現(xiàn)出較差的泛化性能.因此,在設(shè)計(jì)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)數(shù)據(jù)的預(yù)測(cè)模型時(shí),需要考慮因數(shù)據(jù)變化而帶來(lái)的概念漂移問(wèn)題.

針對(duì)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)數(shù)據(jù)流的特點(diǎn),文獻(xiàn)[10]介紹了包括決策樹(shù)、分類(lèi)關(guān)聯(lián)規(guī)則等集成分類(lèi)模型.文獻(xiàn)[12]提出了自適應(yīng)集成方法,對(duì)概念漂移的數(shù)據(jù)流進(jìn)行分類(lèi).文獻(xiàn)[13]給出了一種基于數(shù)據(jù)塊的在線(xiàn)處理概念漂移數(shù)據(jù)流的集成分類(lèi)方法.文獻(xiàn)[14]則采用了在線(xiàn)權(quán)重集成方法和在線(xiàn)隨機(jī)森林方法,來(lái)設(shè)計(jì)集成分類(lèi)方法.眾多學(xué)者已將集成學(xué)習(xí)應(yīng)用于處理概念漂移數(shù)據(jù)流,即把多個(gè)不同的弱預(yù)測(cè)模型組合成一個(gè)強(qiáng)預(yù)測(cè)模型[15],利用不同預(yù)測(cè)模型之間的差異,來(lái)提高模型的泛化性能.集成學(xué)習(xí)預(yù)測(cè)模型具有更高的預(yù)測(cè)準(zhǔn)確度,可以很好地適應(yīng)概念的變化,將概念漂移的影響削弱在共同決策中.集成學(xué)習(xí)預(yù)測(cè)模型有兩個(gè)主要的問(wèn)題需要解決,一是如何得到若干個(gè)弱預(yù)測(cè)模型,二是如何選擇一種組合策略,將這些弱預(yù)測(cè)模型組合成一個(gè)強(qiáng)預(yù)測(cè)模型.

在本文,我們提出并分析了一種新穎的個(gè)性化加權(quán)在線(xiàn)集成算法.使用先驗(yàn)數(shù)據(jù)對(duì)模型進(jìn)行訓(xùn)練學(xué)習(xí),采用加權(quán)投票的組合策略,將多個(gè)弱預(yù)測(cè)模型組合成一個(gè)強(qiáng)預(yù)測(cè)模型.為了適應(yīng)概念漂移現(xiàn)象,按照順序一批接一批地處理實(shí)例,每次處理一批實(shí)例后更新集成學(xué)習(xí)預(yù)測(cè)模型.我們的貢獻(xiàn)如下:

1)基于無(wú)線(xiàn)傳感器網(wǎng)絡(luò)數(shù)據(jù)流的時(shí)間順序性,將先驗(yàn)數(shù)據(jù)劃分為若干數(shù)據(jù)塊,訓(xùn)練出若干弱預(yù)測(cè)模型.

2)考慮前后數(shù)據(jù)塊概率分布的差異性,通過(guò)計(jì)算各數(shù)據(jù)塊之間的K-L散度值,確定各弱預(yù)測(cè)模型的權(quán)重,進(jìn)行動(dòng)態(tài)加權(quán)集成.

2 所提方法

為了對(duì)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的數(shù)據(jù)流進(jìn)行預(yù)測(cè),本文提出了個(gè)性化的加權(quán)在線(xiàn)集成學(xué)習(xí)模型.如圖1所示,對(duì)于無(wú)線(xiàn)傳感數(shù)據(jù)流,該方法首先按照時(shí)間順序?qū)⑾闰?yàn)數(shù)據(jù)劃分為若干數(shù)據(jù)塊,對(duì)于最新接收到的數(shù)據(jù)塊Bm,保留距離新數(shù)據(jù)塊最近的n個(gè)數(shù)據(jù)塊Bm-n,…,Bm-1,并通過(guò)這n個(gè)數(shù)據(jù)塊,分別訓(xùn)練出n個(gè)預(yù)測(cè)模型,同時(shí)假設(shè)每個(gè)數(shù)據(jù)塊均符合多維高斯分布,并分別計(jì)算及記錄每數(shù)據(jù)塊的均值和方差.通過(guò)分別計(jì)算新數(shù)據(jù)塊到最近的n個(gè)數(shù)據(jù)塊之間的K-L散度值,確定其相似度,進(jìn)而據(jù)此計(jì)算每個(gè)模型對(duì)應(yīng)的投票權(quán)重,最終生成一個(gè)加權(quán)集成預(yù)測(cè)模型.每次處理一批實(shí)例后,采用新模型替換集成學(xué)習(xí)預(yù)測(cè)模型集中距離新數(shù)據(jù)塊最遠(yuǎn)的一個(gè)預(yù)測(cè)模型.

圖1 個(gè)性化集成在線(xiàn)學(xué)習(xí)預(yù)測(cè)模型示意圖

2.1 K-L散度計(jì)算

高斯分布是自然科學(xué)和行為科學(xué)中最常見(jiàn)的一種概率分布形式.因此,可以近似地認(rèn)為無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中各數(shù)據(jù)塊在每一特征維度上均服從高斯分布[16,17].

對(duì)于單變量高斯分布,其概率密度函數(shù)可表示如下:

(1)

其中,μ為數(shù)學(xué)期望值,σ為方差.

對(duì)于多變量高斯分布,其概率密度函數(shù)則可表示如下:

(2)

其中,μ為期望值,Σ為協(xié)方差矩陣.

K-L散度,是一種度量?jī)煞N概率分布P1和P2之間差異的度量測(cè)度.假設(shè)概率分布P1表示真實(shí)分布,概率分布P2表示擬合的真實(shí)分布,那么則可以通過(guò)計(jì)算它們之間的K-L散度值來(lái)度量使用概率分布P2擬合真實(shí)分布P1所產(chǎn)生的信息損耗[18].多變量高斯分布的K-L散度值可以按照公式(3)來(lái)進(jìn)行計(jì)算得到:

DKL(P1‖P2)

=EP1(logP1-logP2)

(3)

其中,Σ1和Σ2分別代表兩個(gè)數(shù)據(jù)集的協(xié)方差矩陣,而μ1和μ2則表示它們的期望值.顯然,當(dāng)兩個(gè)分布完全相同時(shí),則它們的K-L散度值為零.當(dāng)兩個(gè)分布的差別較大時(shí),則它們的K-L散度值也會(huì)較大,且會(huì)隨著分布差異的增大,K-L散度值越變?cè)酱?

2.2 基于K-L散度的權(quán)重分配策略

由于無(wú)線(xiàn)數(shù)據(jù)傳感器網(wǎng)絡(luò)數(shù)據(jù)流具有時(shí)間順序性這一特點(diǎn),因此可以按照時(shí)間分布規(guī)律將數(shù)據(jù)劃分為若干個(gè)數(shù)據(jù)塊.如圖1所示,假設(shè)在集成預(yù)測(cè)模型中,我們只保留與最新接收的數(shù)據(jù)塊Bm最鄰近的n個(gè)數(shù)據(jù)塊Bm-n,…,Bm-1以及預(yù)測(cè)模型Cm-n,…,Cm-1,并計(jì)算各個(gè)數(shù)據(jù)塊的期望值μm-n,…,μm-1與協(xié)方差矩陣Σm-n,…,Σm-1,同時(shí)計(jì)算Bm的期望值μm和協(xié)方差矩陣Σm.

按照公式(3),分別計(jì)算Bm到Bm-n,…,Bm-1之間的K-L散度值Dm-nm,…,Dm-1m.假設(shè)Dim最小,則表明第i塊數(shù)據(jù)與第m塊數(shù)據(jù)的概率分布最為相似,則顯然采用對(duì)應(yīng)的預(yù)測(cè)模型Ci對(duì)新數(shù)據(jù)塊Bm進(jìn)行預(yù)測(cè)也要最為準(zhǔn)確,故理應(yīng)為其分配最大的權(quán)重.本文引入公式(4)所示的衰減函數(shù),來(lái)計(jì)算得到權(quán)重所有的wm-nm,…,wm-1m.

w=e-kx

(4)

其中,k為一個(gè)常數(shù),用于調(diào)控權(quán)重的衰減速度,x表示對(duì)應(yīng)的K-L散度值,w則為計(jì)算得到的權(quán)重值.顯然,利用該式,可以建立K-L散度值與權(quán)重之間的負(fù)相關(guān)關(guān)系,即K-L散度值越大,二者差異也越大,對(duì)應(yīng)的投票權(quán)重也越小.

計(jì)算Bm被n個(gè)預(yù)測(cè)模型預(yù)測(cè)的結(jié)果Rn,Rn-1,…,R1,將具有相同結(jié)果的預(yù)測(cè)模型聚類(lèi),假設(shè)有s類(lèi),并對(duì)每類(lèi)的w進(jìn)行求和得{W1,W2,…,Ws},取其中最大值所對(duì)應(yīng)的類(lèi)別作為最終的預(yù)測(cè)結(jié)果.

2.3 在線(xiàn)加權(quán)集成預(yù)測(cè)模型

本文所提出的個(gè)性化加權(quán)在線(xiàn)集成算法,其詳細(xì)的算法流程如表1所示.

表1 算法流程

Table 1 Flowchart of the proposed algorithm

3 實(shí)驗(yàn)與結(jié)果

3.1 度量標(biāo)準(zhǔn)

本文主要采用預(yù)測(cè)精度作為衡量算法性能優(yōu)劣的度量指標(biāo)[19],對(duì)于精度,其計(jì)算公式如下:

(5)

其中,total_num為新數(shù)據(jù)塊中的樣本總數(shù),correct_num為預(yù)測(cè)正確的樣本數(shù),Accuracy值越大,則表明預(yù)測(cè)精度越高.

3.2 數(shù)據(jù)集描述

本文采用Sensor Stream數(shù)據(jù)集(1)http://www.cse.fau.edu/～xqzhu/stream.html.對(duì)所提算法的性能進(jìn)行測(cè)試,下面將對(duì)該數(shù)據(jù)集進(jìn)行簡(jiǎn)單介紹.

Sensor Stream數(shù)據(jù)集來(lái)源于英特爾-伯克利實(shí)驗(yàn)室.無(wú)線(xiàn)傳感器網(wǎng)絡(luò)由54個(gè)傳感器節(jié)點(diǎn)組成,每隔1～3分鐘采集網(wǎng)絡(luò)內(nèi)各個(gè)傳感器節(jié)點(diǎn)的溫度值、濕度值、光線(xiàn)亮度值和自身電壓值等,共計(jì)執(zhí)行2個(gè)月的數(shù)據(jù)采集任務(wù).該數(shù)據(jù)集使用傳感器節(jié)點(diǎn)ID作為類(lèi)標(biāo),令溫度值、濕度值、光線(xiàn)亮度值和自身電壓值作為特征值.因此,對(duì)于該數(shù)據(jù)集,學(xué)習(xí)任務(wù)就是要完全根據(jù)傳感器數(shù)據(jù)和相應(yīng)的記錄時(shí)間來(lái)正確預(yù)測(cè)傳感器的ID(54個(gè)傳感器中的1個(gè)).

由于該數(shù)據(jù)集中的樣本數(shù)量過(guò)多且相互獨(dú)立,為了簡(jiǎn)化實(shí)驗(yàn)的過(guò)程,本文截取了原始數(shù)據(jù)集中傳感器節(jié)點(diǎn)ID為1,2,3,4的所有樣本,并通過(guò)異常值處理、冗余數(shù)據(jù)處理后得到簡(jiǎn)化后數(shù)據(jù)集.繼而,按照時(shí)間順序?qū)⒑?jiǎn)化后的數(shù)據(jù)集劃分為若干數(shù)據(jù)塊B1,B2,…,Bn,平均每個(gè)數(shù)據(jù)塊中包含3500個(gè)樣本,本文選擇前50個(gè)數(shù)據(jù)塊來(lái)運(yùn)行實(shí)驗(yàn)并驗(yàn)證所提算法的性能.

3.3 實(shí)驗(yàn)設(shè)置

為了表明本文算法與具體采用何種分類(lèi)器是無(wú)關(guān)的,本文分別采用了決策樹(shù)、K近鄰和支持向量機(jī)等三種不同的分類(lèi)算法對(duì)其進(jìn)行驗(yàn)證.

決策樹(shù)采用的是CART算法;K近鄰算法中的參數(shù)K預(yù)設(shè)為7;支持向量機(jī)選擇高斯核函數(shù),懲罰因子統(tǒng)一設(shè)置為1,核函數(shù)系數(shù)則設(shè)置為樣本特征數(shù)的倒數(shù).

3.4 實(shí)驗(yàn)和結(jié)果

本文共設(shè)計(jì)了兩組實(shí)驗(yàn),第一組用來(lái)確定本文算法的最佳參數(shù)設(shè)置,第二組實(shí)驗(yàn)則用來(lái)驗(yàn)證本文算法的優(yōu)越性.為了證明本文算法的優(yōu)越性,也將其與基線(xiàn)的算法進(jìn)行了對(duì)比,即不考慮分布差異的無(wú)加權(quán)集成預(yù)測(cè)模型.

3.4.1 網(wǎng)格搜索方法確定最優(yōu)參數(shù)

如圖2所示,當(dāng)將衰減常數(shù)k固定為5時(shí),通過(guò)調(diào)控集成規(guī)模n的值可以觀察到這一參數(shù)對(duì)算法總體性能的影響規(guī)律.從該圖中可以看出,若集成規(guī)模n=5,無(wú)論決策樹(shù)、K近鄰,還是支持向量機(jī)分類(lèi)器均可以得到最高的分類(lèi)精度.

圖2 n值變化對(duì)算法性能的影響

如圖3所示,當(dāng)將集成規(guī)模n固定為5時(shí),我們也可以通過(guò)調(diào)控公式(4)中的衰減常數(shù)k的值來(lái)觀察其影響規(guī)律.從該圖中可以觀察到:若k=10時(shí),基于決策樹(shù)、K近鄰、支持向量機(jī)算法的分類(lèi)器分別對(duì)49個(gè)數(shù)據(jù)塊進(jìn)行預(yù)測(cè),且平均預(yù)測(cè)準(zhǔn)確率最高.

圖3 k值變化對(duì)算法性能的影響

3.4.2 算法比較與結(jié)果分析

當(dāng)n=5,k=10,即保留距離本次數(shù)據(jù)塊最近的5個(gè)數(shù)據(jù)塊和其所對(duì)應(yīng)的分類(lèi)器,并分別計(jì)算本次數(shù)據(jù)塊與前5個(gè)數(shù)據(jù)塊之間的K-L散度值,并根據(jù)衰減常數(shù)k值,確定投票權(quán)重值.根據(jù)投票機(jī)制,確定投票值最大的類(lèi)別,作為該數(shù)據(jù)塊中某個(gè)樣本的分類(lèi)值.

如圖4所示,以決策樹(shù)為集成中的個(gè)體分類(lèi)模型,本文所提出的基于K-L散度加權(quán)的集成預(yù)測(cè)模型在49個(gè)數(shù)據(jù)塊上的平均預(yù)測(cè)精度為78.9%,相比于無(wú)加權(quán)集成預(yù)測(cè)模型提高了近5.7%.其中,在31個(gè)數(shù)據(jù)塊上的預(yù)測(cè)精度均優(yōu)于無(wú)加權(quán)集成預(yù)測(cè)模型,在10個(gè)數(shù)據(jù)塊上的預(yù)測(cè)精度達(dá)到了100%.

如圖5所示,以K近鄰為集成中的個(gè)體分類(lèi)模型,本文所提出的基于K-L散度加權(quán)的集成預(yù)測(cè)模型在49個(gè)數(shù)據(jù)塊上的平均預(yù)測(cè)精度達(dá)到了78.3%,相比于無(wú)加權(quán)的集成學(xué)習(xí)預(yù)測(cè)模型提高了近5.6%.其中,在30個(gè)數(shù)據(jù)塊上的預(yù)測(cè)精度均優(yōu)于無(wú)加權(quán)集成預(yù)測(cè)模型,在10個(gè)數(shù)據(jù)塊上的預(yù)測(cè)精度達(dá)到了100%.

如圖6所示,以支持向量機(jī)為集成中的個(gè)體分類(lèi)模型,本文所提出的基于K-L散度加權(quán)的集成預(yù)測(cè)模型在49個(gè)數(shù)據(jù)塊上的平均預(yù)測(cè)精度達(dá)到了71.3%,相比于無(wú)加權(quán)的集成學(xué)習(xí)預(yù)測(cè)模型提高了近4.3%.其中,在32個(gè)數(shù)據(jù)塊上的預(yù)測(cè)精度均優(yōu)于無(wú)加權(quán)集成預(yù)測(cè)模型,但僅在1個(gè)數(shù)據(jù)塊上的預(yù)測(cè)精度達(dá)到了100%.

圖4 基于決策樹(shù)的集成學(xué)習(xí)預(yù)測(cè)模型的預(yù)測(cè)準(zhǔn)確度

圖5 基于K-近鄰的集成學(xué)習(xí)預(yù)測(cè)模型的預(yù)測(cè)準(zhǔn)確度

圖6 基于支持向量機(jī)的集成學(xué)習(xí)預(yù)測(cè)模型的預(yù)測(cè)準(zhǔn)確度

通過(guò)上述的實(shí)驗(yàn)結(jié)果可以看出:本文算法無(wú)論采用何種基分類(lèi)器,其性能均要優(yōu)于無(wú)加權(quán)的集成預(yù)測(cè)模型.一方面證明了本文算法并不依賴(lài)于某種具體的基分類(lèi)算法,另一方面也證明了考慮分布差異,進(jìn)而進(jìn)行個(gè)性化加權(quán)的必要性.至于在三種不同分類(lèi)器上,最終的分類(lèi)精度有很大不同,則完全是由基分類(lèi)器自身特性及參數(shù)設(shè)置而導(dǎo)致的,并不影響驗(yàn)證本文算法的優(yōu)越性.

4 結(jié) 語(yǔ)

針對(duì)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)數(shù)據(jù)流易于產(chǎn)生分布漂移這一特點(diǎn),本文設(shè)計(jì)了一種個(gè)性化的加權(quán)在線(xiàn)集成分類(lèi)算法.該算法充分考慮了分布間的差異性,并通過(guò)K-L散度對(duì)其進(jìn)行量化,可以有效評(píng)估已建立的各個(gè)分類(lèi)器對(duì)新數(shù)據(jù)塊準(zhǔn)確預(yù)測(cè)的貢獻(xiàn)程度,并將其轉(zhuǎn)化為集成投票權(quán)重,有效地提升了對(duì)傳感器數(shù)據(jù)流的預(yù)測(cè)精度.特別地,在集成預(yù)測(cè)模型中,本文采用了動(dòng)態(tài)的基分類(lèi)器更新策略,可以有效地降低決策的時(shí)間復(fù)雜度,能夠滿(mǎn)足無(wú)線(xiàn)傳感數(shù)據(jù)實(shí)時(shí)性的需求.通過(guò)大量實(shí)驗(yàn)驗(yàn)證了本文算法的有效性、可行性及優(yōu)越性.