結(jié)合特征選擇和優(yōu)化隨機森林的無線網(wǎng)絡(luò)數(shù)據(jù)丟失重建

栗風永, 周 剛

(上海電力大學 計算機科學與技術(shù)學院, 上海 200090)

在實際數(shù)據(jù)的收集過程中,無線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks,WSNs)[1]數(shù)據(jù)丟失的情況十分普遍。大多數(shù)基礎(chǔ)學科的研究依賴于精確完整的數(shù)據(jù)集,而準確完整地傳輸數(shù)據(jù)集是保障基礎(chǔ)學科研究能否順利進行的重要前提,因此針對數(shù)據(jù)重建的研究十分必要。傳統(tǒng)的WSNs中,造成數(shù)據(jù)丟失的原因主要包括以下4個方面:一是無線信道傳輸?shù)牟环€(wěn)定性,傳輸過程有噪聲的干擾;二是樹形和分簇的拓撲結(jié)構(gòu)導(dǎo)致信道之間相互的干擾;三是突發(fā)事件形成數(shù)據(jù)爆發(fā)導(dǎo)致傳輸過程中的擁塞;四是節(jié)點被損壞或節(jié)點電池因續(xù)航問題導(dǎo)致的意外失效。

針對WSNs傳輸過程中數(shù)據(jù)丟失的現(xiàn)象,已有不少典型的解決方案被提出。例如,局部插值算法中的K鄰近(K-Nearest Neighbors,KNN)[2-3]算法是一種十分經(jīng)典的插值算法。KNN利用需要恢復(fù)數(shù)據(jù)的相鄰K個數(shù)據(jù)來重建丟失數(shù)據(jù)。這里的“相鄰”指的是在典型場景下數(shù)據(jù)采集節(jié)點之間物理上的位置關(guān)系。對于“相鄰數(shù)據(jù)”的不同使用方法,形成了KNN算法的不同變種,如直接平均、加權(quán)平均以及擬合后的估計等。在數(shù)據(jù)丟失率不是太高且相鄰關(guān)系容易獲得的應(yīng)用場景中,KNN算法簡單且有效,因此被廣泛應(yīng)用于低保真度要求的數(shù)據(jù)估計中。LI F Y等人[4]提出了基于數(shù)據(jù)分解的集成恢復(fù)算法,首先將原始數(shù)據(jù)進行冗余膨脹,再使用接受到的部分數(shù)據(jù)重建原始數(shù)據(jù),只要數(shù)據(jù)丟失不超過一定比例,則原始數(shù)據(jù)可以通過集成算法[5]被完美恢復(fù)。該算法在數(shù)據(jù)丟失率較低的情況下有很好的數(shù)據(jù)重建能力,但在數(shù)據(jù)丟失率較高時,由于原始數(shù)據(jù)的膨脹率太大,數(shù)據(jù)計算的時間復(fù)雜度和空間復(fù)雜度過高,會導(dǎo)致整體數(shù)據(jù)傳輸性能的下降。全局逐步細化插值算法中的三角剖分(Delaunay Triangulation,DT)[6]將每個有值的數(shù)據(jù)當作一個個頂點,根據(jù)全局誤差逐步減小的過程將頂點連成一個個三角形從而插入缺失值。DT進行數(shù)據(jù)重建時依賴傳感器在空間上的位置分布,被廣泛應(yīng)用于機器視覺中的三圍曲面渲染中。非參數(shù)數(shù)據(jù)自適應(yīng)插值算法中的多通道信號頻譜分析(Multi-channel Singular Spectrum Analysis,MSSA)[7]屬于主成分分析的一個分支,利用嵌入式自協(xié)方差矩陣關(guān)系進行插值,當數(shù)據(jù)丟失率較大時,其恢復(fù)精度并不高,因此通常被應(yīng)用于地理位置或氣象數(shù)據(jù)的重建中。

綜上所述,這些方案大多通過插值估計來進行數(shù)據(jù)的恢復(fù)和重建,在很多的應(yīng)用場景下無法有效解決WSNs中的數(shù)據(jù)重建精度問題,在一定程度上說,已有方法只能在丟失數(shù)據(jù)規(guī)模較小的情況下才能有效重建原始數(shù)據(jù),而針對較大丟失率的高精度重建方法還很少。

本文針對WSNs的高保真數(shù)據(jù)傳輸問題,提出了一種基于KNN和隨機森林相結(jié)合的數(shù)據(jù)丟失重建方法,簡稱KNN-Frost算法。首先利用KNN算法對數(shù)據(jù)樣本中的特征值進行篩選,建立完備的隨機森林分類模型,然后利用建立好的隨機森林模型對含有丟失特征的樣本進行準確分類,并利用已存在的完整樣本對缺失數(shù)據(jù)進行預(yù)測。最終完成針對丟失數(shù)據(jù)的準確重建。相比于現(xiàn)有的數(shù)據(jù)重建算法,本文所提方法在數(shù)據(jù)重建精度方面有了較好的改進,在數(shù)據(jù)丟失率達到80%的情況下,依然優(yōu)于現(xiàn)有方案。

1 相關(guān)工作

傳統(tǒng)的隨機森林算法是基于ID3 (Iterative Dichotomiser 3)[8]方法進行分類預(yù)測。該算法以信息熵[9-10]和信息增益[11]為衡量標準。

根據(jù)信息量的定義,若一個消息x出現(xiàn)的概率為p,則其所含的信息熵I為

I=-log2p

(1)

它是指每個屬性所含信息量的統(tǒng)計平均值。當一個信息包含多種屬性時,則屬性的平均信息熵H(x)為

(2)

式中:m——屬性的種類數(shù)。

由式(2)可知,當H(x)=0時,數(shù)據(jù)集可以被完美地分類,即所有元素都屬于同一類別。假設(shè)存在數(shù)據(jù)集X,在常規(guī)隨機森林模型中,ID3算法會計算每一個屬性的信息熵,具有最小信息熵的屬性在一次迭代中用來劃分數(shù)據(jù)集X。

信息增益表示在得知特征A的信息前提下,使得類B的信息不確定性減少的程度。假設(shè)在事件yi出現(xiàn)的條件下,隨機事件xi發(fā)生的條件概率為p(xi|yi),則其條件自信息量定義為

I(xi|yi)=-log2p(xi|yi)

I=1,2,3,…,n

(3)

當一個特征不能變化時,系統(tǒng)的信息量就叫做條件熵[12]。在給定yi條件下,xi的條件自信息量為I(xi|yi),X集合的條件熵H(X|yi)為

(4)

而當給定Y(即各個yi)條件時,X集合的條件熵H(X|Y)可計算為

(5)

H(X|Y)表示已知屬性Y后,X的不確定度。對應(yīng)地,計算集合X被屬性Y分類前后熵的差異即可表示相應(yīng)的信息增益。ID3會為每一個屬性計算信息熵,具有最大信息增益的屬性在本次迭代中用來劃分數(shù)據(jù)集X。

從上述核心思想看,隨機森林算法根據(jù)最大信息熵增益原則選擇劃分當前數(shù)據(jù)集的特征,再進行森林構(gòu)造[13]。在數(shù)據(jù)樣本特征較多的情況下,一些與目標特征相關(guān)性較差的特征會干擾算法分類的結(jié)果,從而導(dǎo)致算法性能的下降。因此,有必要在建立隨機森林模型前先對特征進行劃分篩選,將相關(guān)性較差的特征進行過濾,以提高隨機森林模型的分類性能。

2 提出的算法

2.1 算法框架

傳感器的數(shù)據(jù)發(fā)送端通過無線信道進行數(shù)據(jù)發(fā)送,但在傳輸?shù)倪^程中,由于無線傳輸信道的不穩(wěn)定性,使得傳感器數(shù)據(jù)接收端接收到的數(shù)據(jù)集會有部分數(shù)據(jù)樣本的特征值發(fā)生丟失。本文提出的方案主要由3部分組成:特征提取和目標特征值分類;特征選擇和隨機森林構(gòu)造;數(shù)據(jù)重建。首先,針對接受到的數(shù)據(jù)集進行特征提取,確定缺失特征,并將此特征作為目標特征進行分類;其次,使用接收到的完整數(shù)據(jù)集,運用KNN算法進行特征選擇,選擇出與目標特征相關(guān)性較高的特征;然后,從這些特征中隨機地無放回抽取特征構(gòu)造決策樹,進而建立隨機森林;最后,結(jié)合已建立的隨機森林,利用丟失目標特征的數(shù)據(jù)樣本的其他特征值對丟失目標特征值進行預(yù)測,從而完成數(shù)據(jù)重建。該算法的整體框架如圖1所示。

圖1 所提算法的整體框架

2.2 基于KNN特征選擇的數(shù)據(jù)丟失重建

將WSNs接收端接收到的數(shù)據(jù)集進行特征提取,然后利用KNN算法進行特征選擇,構(gòu)造隨機森林,再結(jié)合缺失數(shù)據(jù)集的其他特征值,通過隨機森林重建丟失數(shù)據(jù)。假設(shè)接收方接收到一批無線傳感器數(shù)據(jù),簡化該數(shù)據(jù)集的結(jié)構(gòu),記為

(6)

矩陣A中每個元素表示傳感器在某個時間節(jié)點的屬性測量值(屬性包括溫度、壓力值、濕度值等)。例如,第m行n列的數(shù)據(jù)表示在第m個時間節(jié)點的第n個屬性的傳感器測量值。A中每行元素表示相應(yīng)某個時間點所有傳感器屬性值的集合,即數(shù)據(jù)集的每個樣本。每列數(shù)據(jù)表示某個屬性值在所有時間節(jié)點上的數(shù)據(jù)集合,即數(shù)據(jù)集的每個特征。假設(shè)由于無線信道干擾,傳感器數(shù)據(jù)第i行第j列的某元素發(fā)生丟失,即表示在第i時間節(jié)點的第j個屬性元素發(fā)生了丟失,即對應(yīng)A中的aij發(fā)生丟失。本文所提算法可以按照以下步驟實現(xiàn)對丟失數(shù)據(jù)aij的重建。

步驟1 數(shù)據(jù)集特征提取和特征分類。將A中的n個屬性提取出來,提取出的特征種類可表示為As=[a1s,a2s,a3s,…,ams]T,s=1,2,3,…,n,即A矩陣的第s列所有元素構(gòu)成的向量,總共有n個特征,其中第j列特征向量Aj作為目標特征,剩下的n-1個特征作為訓(xùn)練特征。

將目標特征向量Aj=[a1j,a2j,a3j,…,amj]T進行特征值分類,即將Aj中的元素值分為T1,T2,T3,…,Tt總共t個分類,其中aij屬于t1,t2,t3,…,tn這T個分類中的某一個分類。

步驟2 特征選擇。首先將aij元素在矩陣A中所在行的樣本數(shù)據(jù)[ai1,ai2,ai3,…,ain]和所在目標特征向量Aj=[a1j,a2j,a3j,…,amj]T進行剔除,剩余的m-1個樣本和n-1個特征組成新的數(shù)據(jù)集記為B,即

(7)

矩陣B的每列分別表示KNN算法的特征樣本,用Bs表示,s=1,2,3,…,n。Bs=[a1s,a2s,…,a(j-1)s,a(j+1)s,…,ams]T。使用歐氏距離分別計算出n-1個特征樣本到目標特征樣本Aj的距離。已知Bs∈B,則Bs到Aj的距離為

(8)

選取其中距離目標樣本Aj最短的K個特征L1,L2,L3,…,Lk作為特征選擇的結(jié)果。由于K的大小決定了特征選擇的維數(shù),所以后續(xù)實驗將對其進行討論。

步驟3 特征抽取。從L1,L2,L3,…,Lk中隨機地無放回抽取出j個特征和目標樣本Aj,組成新的數(shù)據(jù)集A。

步驟4 計算特征信息增益。在新的A數(shù)據(jù)集中,目標特征As有T個分類,其所占的比例為PT(T=1,2,3,…,t),則A數(shù)據(jù)集的信息熵為

(9)

特征向量Ai的特征值共有M個分類,其所占的比例為PM(M=1,2,3,…,m)。在已知特征向量Ai的情況下,其分類條件熵為

H(D|Ai)=

(10)

計算出特征向量Ai的信息增益為

G(D|Ai)=H(D)-H(D|Ai)

(11)

選擇信息增益最大的屬性即找出特征最大的G(D|Ai),用Amax來表示,即

Amax=max(G(D|Ai))

(12)

步驟5 構(gòu)造決策樹。將選出的Amax特征作為決策樹的根節(jié)點。Amax的特征值又有多個分類,每個分類下又可以構(gòu)造出一個新的數(shù)據(jù)集。重復(fù)步驟(4)計算信息增益,遞歸生成決策樹,直至當前節(jié)點包含的數(shù)據(jù)集為空集,不能再繼續(xù)劃分為止,則基于新A的數(shù)據(jù)集的決策樹構(gòu)造完整。

步驟6 重復(fù)步驟3～步驟5,構(gòu)造多棵決策樹,構(gòu)造隨機森林模型。

步驟7 使用隨機森林對丟失數(shù)據(jù)進行重建。將矩陣A中丟失aij元素的行數(shù)據(jù)樣本取出,其值為[ai1,ai2,ai3,…,ai(j-1)ai(j+1),…,ain]。將該行數(shù)據(jù)代入隨機森林的每棵決策樹中,可得到單棵樹對aij的分類預(yù)測,得到分類結(jié)果Ti∈T1,T2,T3,…,Tt。再將多個決策樹的分類預(yù)測結(jié)果進行多數(shù)投票集成,確定aij的預(yù)測結(jié)果。

3 實驗結(jié)果與分析

以某城市為例,該城市位于北半球中緯度大陸東岸,屬于溫帶季風氣候。為了體現(xiàn)本文所提KNN-Frost算法的性能,使用分布在該城市不同位置的24個傳感器節(jié)點,選取傳感器測量值變化幅度較大的時間段進行數(shù)據(jù)測量。從4月1日到5月1日,每天每小時測量一次數(shù)據(jù)。氣溫取值范圍為-1～24 ℃。選取24個傳感器的溫度、壓力、濕度等共144個特征值,共720條數(shù)據(jù)作為樣本,將數(shù)據(jù)集經(jīng)過無線信道進行傳輸。假設(shè)某個傳感器的溫度值由于不良的傳輸信道而發(fā)生了丟失,則可將其作為目標值,剩余的143個特征作為特征值,然后利用本文所提算法對丟失的傳感器的溫度值進行數(shù)據(jù)重建。

3.1 數(shù)據(jù)預(yù)處理

為了展示本文所提算法的性能,對得到的720條數(shù)據(jù)樣本進行數(shù)據(jù)分割,隨機取出部分數(shù)據(jù)作為訓(xùn)練集,用來生成隨機森林,剩余部分的數(shù)據(jù)作為測試集,用來測試隨機森林分類預(yù)測的準確性。利用仿真實驗?zāi)M在固定數(shù)據(jù)集大小的情況下,對應(yīng)不同數(shù)據(jù)丟失率的重建情況。例如,模擬20%的數(shù)據(jù)丟失,則將數(shù)據(jù)集劃分為80%的訓(xùn)練集和20%的測試集;模擬30%的數(shù)據(jù)丟失,則將數(shù)據(jù)集劃分為70%的訓(xùn)練集和30%的測試集。

3.2 最優(yōu)K值確定

本文固定實驗數(shù)據(jù)集的大小,其他條件不變,數(shù)據(jù)丟失率固定在20%,40%,60%,80%,選擇K值為3,10,30,50,70,90,110,130等8個不同的值,使用KNN-Frost算法進行數(shù)據(jù)重建。當算法的性能達到最佳時,將對應(yīng)的K值確定為最佳值。表1給出了對應(yīng)的實驗結(jié)果。

從表1可以看出,隨著K值的增加,重建性能逐漸增加。當K=30時,重建的效率最高。之后,隨著K值的增大,數(shù)據(jù)的重建能力緩慢下降。這說明在原始特征集中存在一個最佳的特征子集可以使構(gòu)建的隨機森林模型具有最佳分類性能。

表1 不同K值下數(shù)據(jù)恢復(fù)率的大小對比 單位:%

3.3 與已有方法的對比

由于溫度會隨著季節(jié)的變化而變化,故仿真實驗分別模擬感知春季(10～15 ℃)、夏季(15～24 ℃)、秋季(10～22 ℃)、冬季(-1～10 ℃)4個季節(jié)的溫度變化情況,將30個傳感器節(jié)點設(shè)置為感知環(huán)境溫度,并使用WSNs進行數(shù)據(jù)傳輸。對丟失的數(shù)據(jù),采用本文所提算法進行數(shù)據(jù)的重建,并求出其數(shù)據(jù)重建率(Data Reconstruction,DR)。其計算公式為

(13)

數(shù)據(jù)的丟失率固定在5個級別,分別是10%,30%,50%,70%,80%。采用KNN算法中由距離度量的方式不同而衍生的變種算法——歐幾里德距離(Euclidean)、曼哈頓距離(Manhaltan)、切比雪夫距離(Chebyshev)、夾角余弦距離(Angle consine)和漢明距離(Hamming)進行數(shù)據(jù)的仿真重建。5種變種算法與KNN-Frost算法對比的結(jié)果如圖2所示。

圖2 5種變種算法與KNNFrost算法在數(shù)據(jù)重建率和數(shù)據(jù)丟失率之間的關(guān)系對比

實驗中使用最優(yōu)值的參數(shù)K=30來重建丟失的值。由于重建的數(shù)據(jù)與實際值之間存在微小的差距,故設(shè)置重建誤差α=0.5,即表示只要重建數(shù)值與實際值的誤差在0～0.5之間,都認為重建的數(shù)據(jù)是有效的。實驗結(jié)果以數(shù)據(jù)的重建率來表示算法數(shù)據(jù)重建能力的強弱。每次實驗重復(fù)100次,給出平均的DR值。由圖2可以看出,隨著數(shù)據(jù)丟失率的逐步增加,5種變種算法和KNN-Frost算法的DR值都趨于緩慢下降,但相比于KNN的任何變種算法,KNN-Frost算法都有著較好的數(shù)據(jù)重建率。

為了進一步展示KNN-Frost算法在分類預(yù)測方面的優(yōu)越性,在相同的數(shù)據(jù)集下,模擬數(shù)據(jù)丟失,采用兩種已有的數(shù)據(jù)恢復(fù)方法,即基于ID3特征選擇的隨機森林算法和基于Gini特征選擇的隨機森林算法,與KNN-Frost算法進行丟失數(shù)據(jù)重建對比。實驗分別對比3種不同情況:一是其他條件不變,隨機森林中樹的深度為2,4,6,8,10時的數(shù)據(jù)重建能力;二是集成樹的數(shù)量為5,10,15,20,25時的數(shù)據(jù)重建能力;三是數(shù)據(jù)丟失率為20%,40%,60%,80%時的數(shù)據(jù)重建能力。3種算法的對比結(jié)果如圖3,圖4,圖5所示。

由從圖3和圖4可以看出,隨著樹的數(shù)量和深度的增加,數(shù)據(jù)重建率逐漸升高,到達峰值后趨于平緩。對比3種隨機森林的方法可以看出,無論是哪種情況下,KNN-Frost算法的性能都要優(yōu)越于其他兩種算法,這是因為該算法在構(gòu)建隨機森林前先對特征進行了篩選,使得構(gòu)建的隨機森林模型的分類效果得到了提升。

此外,由圖5可以看出,隨著數(shù)據(jù)丟失率的提高,數(shù)據(jù)的重建率逐漸下降,但KNN-Frost算法仍好于其他兩種算法,并且當數(shù)據(jù)丟失率高達80%時,該算法依然可以達到恢復(fù)約70%的原始數(shù)據(jù)。這說明KNN-Frost算法仍然有著明顯的較高的數(shù)據(jù)重建能力。

圖3 樹的深度為5和10的時不同樹的深度與重建率的關(guān)系對比

圖4 樹的數(shù)量為10和15時集成樹的數(shù)量與數(shù)據(jù)重建率的關(guān)系對比

圖5 不同樹深度和樹數(shù)量下數(shù)據(jù)丟失率與數(shù)據(jù)重建率的關(guān)系對比

4 結(jié) 語

本文提出的KNN-Frost算法有效解決了無線網(wǎng)絡(luò)傳輸中數(shù)據(jù)丟失的問題,改進了現(xiàn)有算法在重建數(shù)據(jù)時精度不高的弊端;通過構(gòu)建基于KNN的特征選擇算法,使得隨機森林模型能夠以更高精度給出預(yù)測值,從而實現(xiàn)較好的數(shù)據(jù)重建效果;KNN-Frost算法可以應(yīng)對不同無線傳感器網(wǎng)絡(luò)結(jié)構(gòu)中的數(shù)據(jù)重建問題,具有較好的適配性。

此外,KNN-Frost算法在丟失數(shù)據(jù)的特征值分類較多且數(shù)據(jù)集特征較少的情況下,數(shù)據(jù)重建的效果可能會下降。但無線傳感器網(wǎng)絡(luò)收集的數(shù)據(jù)特點通常是數(shù)據(jù)變化幅度較小,并且數(shù)據(jù)集巨大,這些特點使得KNN-Frost算法較適用于無線網(wǎng)絡(luò)環(huán)境的數(shù)據(jù)重建。在未來的工作中,將針對特征值分類較多、數(shù)據(jù)特征較少的應(yīng)用場景,在原算法的基礎(chǔ)上嘗試其他的特征選擇方式,進一步改進算法,以期獲取更好的結(jié)果。