無線傳感器網絡數據的個性化加權在線集成學習算法

劉 偉,王 琦,于化龍

(江蘇科技大學 計算機學院,江蘇 鎮江 212003)

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

1 相關工作

近年來,無線傳感器網絡已廣泛應用于生產生活的各個領域,在環境監測[1]、現代農業[2]、自然災害預警[3]等領域發揮著重要的作用.為了獲取全面、準確的信息,通常在監控區域內部署大量傳感器節點.為了完成數據采集任務,通常采用基于分簇的無線傳感器網絡路由協議[4-7],即把網絡在邏輯上劃分為若干簇,每個簇由一個簇首和若干個簇內成員節點構成.簇內成員節點負責采集感知數據并發送給簇首,簇首負責簇內通信調度、數據融合以及發送數據至基站,基站以互聯網的方式最終將數據發送給用戶.

無線傳感器網絡作為一種數據采集型網絡,其數據是以數據流的形式傳遞給用戶[8,9],該數據流具有時間順序性、分布變化快速、潛在無限、數據間關聯性強等特點[10].針對無線傳感器網絡的數據特點,如何準確地對傳感器數據進行精確的在線預測,便成為一個急需解決的問題.

傳統的基于機器學習方法的預測模型歸根結底是對某一靜態數據分布的學習,即通過先驗數據訓練出一個誤差最小的預測模型,無需考慮因為數據的變化而更新模型的問題.但是,在無線傳感器數據流環境中,一些數據分布是隨著環境變化和時間推移而發生改變,且這種改變是不可預測的,即產生概念漂移現象[11],如在一個測量溫度的傳感器網絡中,某年可能出現極寒或極熱情況,則該年的數據分布將不同于歷史數據.如果還是依靠舊數據訓練的模型用于對新數據進行預測,則表現出較差的泛化性能.因此,在設計無線傳感器網絡數據的預測模型時,需要考慮因數據變化而帶來的概念漂移問題.

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

在本文,我們提出并分析了一種新穎的個性化加權在線集成算法.使用先驗數據對模型進行訓練學習,采用加權投票的組合策略,將多個弱預測模型組合成一個強預測模型.為了適應概念漂移現象,按照順序一批接一批地處理實例,每次處理一批實例后更新集成學習預測模型.我們的貢獻如下:

1)基于無線傳感器網絡數據流的時間順序性,將先驗數據劃分為若干數據塊,訓練出若干弱預測模型.

2)考慮前后數據塊概率分布的差異性,通過計算各數據塊之間的K-L散度值,確定各弱預測模型的權重,進行動態加權集成.

2 所提方法

為了對無線傳感器網絡的數據流進行預測,本文提出了個性化的加權在線集成學習模型.如圖1所示,對于無線傳感數據流,該方法首先按照時間順序將先驗數據劃分為若干數據塊,對于最新接收到的數據塊Bm,保留距離新數據塊最近的n個數據塊Bm-n,…,Bm-1,并通過這n個數據塊,分別訓練出n個預測模型,同時假設每個數據塊均符合多維高斯分布,并分別計算及記錄每數據塊的均值和方差.通過分別計算新數據塊到最近的n個數據塊之間的K-L散度值,確定其相似度,進而據此計算每個模型對應的投票權重,最終生成一個加權集成預測模型.每次處理一批實例后,采用新模型替換集成學習預測模型集中距離新數據塊最遠的一個預測模型.

圖1 個性化集成在線學習預測模型示意圖

2.1 K-L散度計算

高斯分布是自然科學和行為科學中最常見的一種概率分布形式.因此,可以近似地認為無線傳感器網絡中各數據塊在每一特征維度上均服從高斯分布[16,17].

對于單變量高斯分布,其概率密度函數可表示如下:

(1)

其中,μ為數學期望值,σ為方差.

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

(2)

其中,μ為期望值,Σ為協方差矩陣.

K-L散度,是一種度量兩種概率分布P1和P2之間差異的度量測度.假設概率分布P1表示真實分布,概率分布P2表示擬合的真實分布,那么則可以通過計算它們之間的K-L散度值來度量使用概率分布P2擬合真實分布P1所產生的信息損耗[18].多變量高斯分布的K-L散度值可以按照公式(3)來進行計算得到:

DKL(P1‖P2)

=EP1(logP1-logP2)

(3)

其中,Σ1和Σ2分別代表兩個數據集的協方差矩陣,而μ1和μ2則表示它們的期望值.顯然,當兩個分布完全相同時,則它們的K-L散度值為零.當兩個分布的差別較大時,則它們的K-L散度值也會較大,且會隨著分布差異的增大,K-L散度值越變越大.

2.2 基于K-L散度的權重分配策略

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

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

w=e-kx

(4)

其中,k為一個常數,用于調控權重的衰減速度,x表示對應的K-L散度值,w則為計算得到的權重值.顯然,利用該式,可以建立K-L散度值與權重之間的負相關關系,即K-L散度值越大,二者差異也越大,對應的投票權重也越小.

計算Bm被n個預測模型預測的結果Rn,Rn-1,…,R1,將具有相同結果的預測模型聚類,假設有s類,并對每類的w進行求和得{W1,W2,…,Ws},取其中最大值所對應的類別作為最終的預測結果.

2.3 在線加權集成預測模型

本文所提出的個性化加權在線集成算法,其詳細的算法流程如表1所示.

表1 算法流程

Table 1 Flowchart of the proposed algorithm

3 實驗與結果

3.1 度量標準

本文主要采用預測精度作為衡量算法性能優劣的度量指標[19],對于精度,其計算公式如下:

(5)

其中,total_num為新數據塊中的樣本總數,correct_num為預測正確的樣本數,Accuracy值越大,則表明預測精度越高.

3.2 數據集描述

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

Sensor Stream數據集來源于英特爾-伯克利實驗室.無線傳感器網絡由54個傳感器節點組成,每隔1～3分鐘采集網絡內各個傳感器節點的溫度值、濕度值、光線亮度值和自身電壓值等,共計執行2個月的數據采集任務.該數據集使用傳感器節點ID作為類標,令溫度值、濕度值、光線亮度值和自身電壓值作為特征值.因此,對于該數據集,學習任務就是要完全根據傳感器數據和相應的記錄時間來正確預測傳感器的ID(54個傳感器中的1個).

由于該數據集中的樣本數量過多且相互獨立,為了簡化實驗的過程,本文截取了原始數據集中傳感器節點ID為1,2,3,4的所有樣本,并通過異常值處理、冗余數據處理后得到簡化后數據集.繼而,按照時間順序將簡化后的數據集劃分為若干數據塊B1,B2,…,Bn,平均每個數據塊中包含3500個樣本,本文選擇前50個數據塊來運行實驗并驗證所提算法的性能.

3.3 實驗設置

為了表明本文算法與具體采用何種分類器是無關的,本文分別采用了決策樹、K近鄰和支持向量機等三種不同的分類算法對其進行驗證.

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

3.4 實驗和結果

本文共設計了兩組實驗,第一組用來確定本文算法的最佳參數設置,第二組實驗則用來驗證本文算法的優越性.為了證明本文算法的優越性,也將其與基線的算法進行了對比,即不考慮分布差異的無加權集成預測模型.

3.4.1 網格搜索方法確定最優參數

如圖2所示,當將衰減常數k固定為5時,通過調控集成規模n的值可以觀察到這一參數對算法總體性能的影響規律.從該圖中可以看出,若集成規模n=5,無論決策樹、K近鄰,還是支持向量機分類器均可以得到最高的分類精度.

圖2 n值變化對算法性能的影響

如圖3所示,當將集成規模n固定為5時,我們也可以通過調控公式(4)中的衰減常數k的值來觀察其影響規律.從該圖中可以觀察到:若k=10時,基于決策樹、K近鄰、支持向量機算法的分類器分別對49個數據塊進行預測,且平均預測準確率最高.

圖3 k值變化對算法性能的影響

3.4.2 算法比較與結果分析

當n=5,k=10,即保留距離本次數據塊最近的5個數據塊和其所對應的分類器,并分別計算本次數據塊與前5個數據塊之間的K-L散度值,并根據衰減常數k值,確定投票權重值.根據投票機制,確定投票值最大的類別,作為該數據塊中某個樣本的分類值.

如圖4所示,以決策樹為集成中的個體分類模型,本文所提出的基于K-L散度加權的集成預測模型在49個數據塊上的平均預測精度為78.9%,相比于無加權集成預測模型提高了近5.7%.其中,在31個數據塊上的預測精度均優于無加權集成預測模型,在10個數據塊上的預測精度達到了100%.

如圖5所示,以K近鄰為集成中的個體分類模型,本文所提出的基于K-L散度加權的集成預測模型在49個數據塊上的平均預測精度達到了78.3%,相比于無加權的集成學習預測模型提高了近5.6%.其中,在30個數據塊上的預測精度均優于無加權集成預測模型,在10個數據塊上的預測精度達到了100%.

如圖6所示,以支持向量機為集成中的個體分類模型,本文所提出的基于K-L散度加權的集成預測模型在49個數據塊上的平均預測精度達到了71.3%,相比于無加權的集成學習預測模型提高了近4.3%.其中,在32個數據塊上的預測精度均優于無加權集成預測模型,但僅在1個數據塊上的預測精度達到了100%.

圖4 基于決策樹的集成學習預測模型的預測準確度

圖5 基于K-近鄰的集成學習預測模型的預測準確度

圖6 基于支持向量機的集成學習預測模型的預測準確度

通過上述的實驗結果可以看出:本文算法無論采用何種基分類器,其性能均要優于無加權的集成預測模型.一方面證明了本文算法并不依賴于某種具體的基分類算法,另一方面也證明了考慮分布差異,進而進行個性化加權的必要性.至于在三種不同分類器上,最終的分類精度有很大不同,則完全是由基分類器自身特性及參數設置而導致的,并不影響驗證本文算法的優越性.

4 結 語

針對無線傳感器網絡數據流易于產生分布漂移這一特點,本文設計了一種個性化的加權在線集成分類算法.該算法充分考慮了分布間的差異性,并通過K-L散度對其進行量化,可以有效評估已建立的各個分類器對新數據塊準確預測的貢獻程度,并將其轉化為集成投票權重,有效地提升了對傳感器數據流的預測精度.特別地,在集成預測模型中,本文采用了動態的基分類器更新策略,可以有效地降低決策的時間復雜度,能夠滿足無線傳感數據實時性的需求.通過大量實驗驗證了本文算法的有效性、可行性及優越性.