栗風(fēng)永, 周 剛

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

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

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

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

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

1 相關(guān)工作

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

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

I=-log2p

(1)

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

(2)

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

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

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

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

I=1,2,3,…,n

(3)

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

(4)

而當(dāng)給定Y(即各個(gè)yi)條件時(shí),X集合的條件熵H(X|Y)可計(jì)算為

(5)

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

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

2 提出的算法

2.1 算法框架

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

圖1 所提算法的整體框架

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

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

(6)

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

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

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

步驟2 特征選擇。首先將aij元素在矩陣A中所在行的樣本數(shù)據(jù)[ai1,ai2,ai3,…,ain]和所在目標(biāo)特征向量Aj=[a1j,a2j,a3j,…,amj]T進(jìn)行剔除,剩余的m-1個(gè)樣本和n-1個(gè)特征組成新的數(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。使用歐氏距離分別計(jì)算出n-1個(gè)特征樣本到目標(biāo)特征樣本Aj的距離。已知Bs∈B,則Bs到Aj的距離為

(8)

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

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

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

(9)

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

H(D|Ai)=

(10)

計(jì)算出特征向量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é)點(diǎn)。Amax的特征值又有多個(gè)分類,每個(gè)分類下又可以構(gòu)造出一個(gè)新的數(shù)據(jù)集。重復(fù)步驟(4)計(jì)算信息增益,遞歸生成決策樹,直至當(dāng)前節(jié)點(diǎn)包含的數(shù)據(jù)集為空集,不能再繼續(xù)劃分為止,則基于新A的數(shù)據(jù)集的決策樹構(gòu)造完整。

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

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

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

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

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

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

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

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

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

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

3.3 與已有方法的對(duì)比

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

(13)

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

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

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

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

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

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

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

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

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

4 結(jié) 語

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

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