结合特征选择和优化随机森林的无线网络数据丢失重建

栗风永, 周 刚

(上海电力大学 计算机科学与技术学院, 上海 200090)

在实际数据的收集过程中,无线传感器网络(Wireless Sensor Networks,WSNs)[1]数据丢失的情况十分普遍。大多数基础学科的研究依赖于精确完整的数据集,而准确完整地传输数据集是保障基础学科研究能否顺利进行的重要前提,因此针对数据重建的研究十分必要。传统的WSNs中,造成数据丢失的原因主要包括以下4个方面:一是无线信道传输的不稳定性,传输过程有噪声的干扰;二是树形和分簇的拓扑结构导致信道之间相互的干扰;三是突发事件形成数据爆发导致传输过程中的拥塞;四是节点被损坏或节点电池因续航问题导致的意外失效。

针对WSNs传输过程中数据丢失的现象,已有不少典型的解决方案被提出。例如,局部插值算法中的K邻近(K-Nearest Neighbors,KNN)[2-3]算法是一种十分经典的插值算法。KNN利用需要恢复数据的相邻K个数据来重建丢失数据。这里的“相邻”指的是在典型场景下数据采集节点之间物理上的位置关系。对于“相邻数据”的不同使用方法,形成了KNN算法的不同变种,如直接平均、加权平均以及拟合后的估计等。在数据丢失率不是太高且相邻关系容易获得的应用场景中,KNN算法简单且有效,因此被广泛应用于低保真度要求的数据估计中。LI F Y等人[4]提出了基于数据分解的集成恢复算法,首先将原始数据进行冗余膨胀,再使用接受到的部分数据重建原始数据,只要数据丢失不超过一定比例,则原始数据可以通过集成算法[5]被完美恢复。该算法在数据丢失率较低的情况下有很好的数据重建能力,但在数据丢失率较高时,由于原始数据的膨胀率太大,数据计算的时间复杂度和空间复杂度过高,会导致整体数据传输性能的下降。全局逐步细化插值算法中的三角剖分(Delaunay Triangulation,DT)[6]将每个有值的数据当作一个个顶点,根据全局误差逐步减小的过程将顶点连成一个个三角形从而插入缺失值。DT进行数据重建时依赖传感器在空间上的位置分布,被广泛应用于机器视觉中的三围曲面渲染中。非参数数据自适应插值算法中的多通道信号频谱分析(Multi-channel Singular Spectrum Analysis,MSSA)[7]属于主成分分析的一个分支,利用嵌入式自协方差矩阵关系进行插值,当数据丢失率较大时,其恢复精度并不高,因此通常被应用于地理位置或气象数据的重建中。

综上所述,这些方案大多通过插值估计来进行数据的恢复和重建,在很多的应用场景下无法有效解决WSNs中的数据重建精度问题,在一定程度上说,已有方法只能在丢失数据规模较小的情况下才能有效重建原始数据,而针对较大丢失率的高精度重建方法还很少。

本文针对WSNs的高保真数据传输问题,提出了一种基于KNN和随机森林相结合的数据丢失重建方法,简称KNN-Frost算法。首先利用KNN算法对数据样本中的特征值进行筛选,建立完备的随机森林分类模型,然后利用建立好的随机森林模型对含有丢失特征的样本进行准确分类,并利用已存在的完整样本对缺失数据进行预测。最终完成针对丢失数据的准确重建。相比于现有的数据重建算法,本文所提方法在数据重建精度方面有了较好的改进,在数据丢失率达到80%的情况下,依然优于现有方案。

1 相关工作

传统的随机森林算法是基于ID3 (Iterative Dichotomiser 3)[8]方法进行分类预测。该算法以信息熵[9-10]和信息增益[11]为衡量标准。

根据信息量的定义,若一个消息x出现的概率为p,则其所含的信息熵I为

I=-log2p

(1)

它是指每个属性所含信息量的统计平均值。当一个信息包含多种属性时,则属性的平均信息熵H(x)为

(2)

式中:m——属性的种类数。

由式(2)可知,当H(x)=0时,数据集可以被完美地分类,即所有元素都属于同一类别。假设存在数据集X,在常规随机森林模型中,ID3算法会计算每一个属性的信息熵,具有最小信息熵的属性在一次迭代中用来划分数据集X。

信息增益表示在得知特征A的信息前提下,使得类B的信息不确定性减少的程度。假设在事件yi出现的条件下,随机事件xi发生的条件概率为p(xi|yi),则其条件自信息量定义为

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

I=1,2,3,…,n

(3)

当一个特征不能变化时,系统的信息量就叫做条件熵[12]。在给定yi条件下,xi的条件自信息量为I(xi|yi),X集合的条件熵H(X|yi)为

(4)

而当给定Y(即各个yi)条件时,X集合的条件熵H(X|Y)可计算为

(5)

H(X|Y)表示已知属性Y后,X的不确定度。对应地,计算集合X被属性Y分类前后熵的差异即可表示相应的信息增益。ID3会为每一个属性计算信息熵,具有最大信息增益的属性在本次迭代中用来划分数据集X。

从上述核心思想看,随机森林算法根据最大信息熵增益原则选择划分当前数据集的特征,再进行森林构造[13]。在数据样本特征较多的情况下,一些与目标特征相关性较差的特征会干扰算法分类的结果,从而导致算法性能的下降。因此,有必要在建立随机森林模型前先对特征进行划分筛选,将相关性较差的特征进行过滤,以提高随机森林模型的分类性能。

2 提出的算法

2.1 算法框架

传感器的数据发送端通过无线信道进行数据发送,但在传输的过程中,由于无线传输信道的不稳定性,使得传感器数据接收端接收到的数据集会有部分数据样本的特征值发生丢失。本文提出的方案主要由3部分组成:特征提取和目标特征值分类;特征选择和随机森林构造;数据重建。首先,针对接受到的数据集进行特征提取,确定缺失特征,并将此特征作为目标特征进行分类;其次,使用接收到的完整数据集,运用KNN算法进行特征选择,选择出与目标特征相关性较高的特征;然后,从这些特征中随机地无放回抽取特征构造决策树,进而建立随机森林;最后,结合已建立的随机森林,利用丢失目标特征的数据样本的其他特征值对丢失目标特征值进行预测,从而完成数据重建。该算法的整体框架如图1所示。

图1 所提算法的整体框架

2.2 基于KNN特征选择的数据丢失重建

将WSNs接收端接收到的数据集进行特征提取,然后利用KNN算法进行特征选择,构造随机森林,再结合缺失数据集的其他特征值,通过随机森林重建丢失数据。假设接收方接收到一批无线传感器数据,简化该数据集的结构,记为

(6)

矩阵A中每个元素表示传感器在某个时间节点的属性测量值(属性包括温度、压力值、湿度值等)。例如,第m行n列的数据表示在第m个时间节点的第n个属性的传感器测量值。A中每行元素表示相应某个时间点所有传感器属性值的集合,即数据集的每个样本。每列数据表示某个属性值在所有时间节点上的数据集合,即数据集的每个特征。假设由于无线信道干扰,传感器数据第i行第j列的某元素发生丢失,即表示在第i时间节点的第j个属性元素发生了丢失,即对应A中的aij发生丢失。本文所提算法可以按照以下步骤实现对丢失数据aij的重建。

步骤1 数据集特征提取和特征分类。将A中的n个属性提取出来,提取出的特征种类可表示为As=[a1s,a2s,a3s,…,ams]T,s=1,2,3,…,n,即A矩阵的第s列所有元素构成的向量,总共有n个特征,其中第j列特征向量Aj作为目标特征,剩下的n-1个特征作为训练特征。

将目标特征向量Aj=[a1j,a2j,a3j,…,amj]T进行特征值分类,即将Aj中的元素值分为T1,T2,T3,…,Tt总共t个分类,其中aij属于t1,t2,t3,…,tn这T个分类中的某一个分类。

步骤2 特征选择。首先将aij元素在矩阵A中所在行的样本数据[ai1,ai2,ai3,…,ain]和所在目标特征向量Aj=[a1j,a2j,a3j,…,amj]T进行剔除,剩余的m-1个样本和n-1个特征组成新的数据集记为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作为特征选择的结果。由于K的大小决定了特征选择的维数,所以后续实验将对其进行讨论。

步骤3 特征抽取。从L1,L2,L3,…,Lk中随机地无放回抽取出j个特征和目标样本Aj,组成新的数据集A。

步骤4 计算特征信息增益。在新的A数据集中,目标特征As有T个分类,其所占的比例为PT(T=1,2,3,…,t),则A数据集的信息熵为

(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 构造决策树。将选出的Amax特征作为决策树的根节点。Amax的特征值又有多个分类,每个分类下又可以构造出一个新的数据集。重复步骤(4)计算信息增益,递归生成决策树,直至当前节点包含的数据集为空集,不能再继续划分为止,则基于新A的数据集的决策树构造完整。

步骤6 重复步骤3～步骤5,构造多棵决策树,构造随机森林模型。

步骤7 使用随机森林对丢失数据进行重建。将矩阵A中丢失aij元素的行数据样本取出,其值为[ai1,ai2,ai3,…,ai(j-1)ai(j+1),…,ain]。将该行数据代入随机森林的每棵决策树中,可得到单棵树对aij的分类预测,得到分类结果Ti∈T1,T2,T3,…,Tt。再将多个决策树的分类预测结果进行多数投票集成,确定aij的预测结果。

3 实验结果与分析

以某城市为例,该城市位于北半球中纬度大陆东岸,属于温带季风气候。为了体现本文所提KNN-Frost算法的性能,使用分布在该城市不同位置的24个传感器节点,选取传感器测量值变化幅度较大的时间段进行数据测量。从4月1日到5月1日,每天每小时测量一次数据。气温取值范围为-1～24 ℃。选取24个传感器的温度、压力、湿度等共144个特征值,共720条数据作为样本,将数据集经过无线信道进行传输。假设某个传感器的温度值由于不良的传输信道而发生了丢失,则可将其作为目标值,剩余的143个特征作为特征值,然后利用本文所提算法对丢失的传感器的温度值进行数据重建。

3.1 数据预处理

为了展示本文所提算法的性能,对得到的720条数据样本进行数据分割,随机取出部分数据作为训练集,用来生成随机森林,剩余部分的数据作为测试集,用来测试随机森林分类预测的准确性。利用仿真实验模拟在固定数据集大小的情况下,对应不同数据丢失率的重建情况。例如,模拟20%的数据丢失,则将数据集划分为80%的训练集和20%的测试集;模拟30%的数据丢失,则将数据集划分为70%的训练集和30%的测试集。

3.2 最优K值确定

本文固定实验数据集的大小,其他条件不变,数据丢失率固定在20%,40%,60%,80%,选择K值为3,10,30,50,70,90,110,130等8个不同的值,使用KNN-Frost算法进行数据重建。当算法的性能达到最佳时,将对应的K值确定为最佳值。表1给出了对应的实验结果。

从表1可以看出,随着K值的增加,重建性能逐渐增加。当K=30时,重建的效率最高。之后,随着K值的增大,数据的重建能力缓慢下降。这说明在原始特征集中存在一个最佳的特征子集可以使构建的随机森林模型具有最佳分类性能。

表1 不同K值下数据恢复率的大小对比 单位:%

3.3 与已有方法的对比

由于温度会随着季节的变化而变化,故仿真实验分别模拟感知春季(10～15 ℃)、夏季(15～24 ℃)、秋季(10～22 ℃)、冬季(-1～10 ℃)4个季节的温度变化情况,将30个传感器节点设置为感知环境温度,并使用WSNs进行数据传输。对丢失的数据,采用本文所提算法进行数据的重建,并求出其数据重建率(Data Reconstruction,DR)。其计算公式为

(13)

数据的丢失率固定在5个级别,分别是10%,30%,50%,70%,80%。采用KNN算法中由距离度量的方式不同而衍生的变种算法——欧几里德距离(Euclidean)、曼哈顿距离(Manhaltan)、切比雪夫距离(Chebyshev)、夹角余弦距离(Angle consine)和汉明距离(Hamming)进行数据的仿真重建。5种变种算法与KNN-Frost算法对比的结果如图2所示。

图2 5种变种算法与KNNFrost算法在数据重建率和数据丢失率之间的关系对比

实验中使用最优值的参数K=30来重建丢失的值。由于重建的数据与实际值之间存在微小的差距,故设置重建误差α=0.5,即表示只要重建数值与实际值的误差在0～0.5之间,都认为重建的数据是有效的。实验结果以数据的重建率来表示算法数据重建能力的强弱。每次实验重复100次,给出平均的DR值。由图2可以看出,随着数据丢失率的逐步增加,5种变种算法和KNN-Frost算法的DR值都趋于缓慢下降,但相比于KNN的任何变种算法,KNN-Frost算法都有着较好的数据重建率。

为了进一步展示KNN-Frost算法在分类预测方面的优越性,在相同的数据集下,模拟数据丢失,采用两种已有的数据恢复方法,即基于ID3特征选择的随机森林算法和基于Gini特征选择的随机森林算法,与KNN-Frost算法进行丢失数据重建对比。实验分别对比3种不同情况:一是其他条件不变,随机森林中树的深度为2,4,6,8,10时的数据重建能力;二是集成树的数量为5,10,15,20,25时的数据重建能力;三是数据丢失率为20%,40%,60%,80%时的数据重建能力。3种算法的对比结果如图3,图4,图5所示。

由从图3和图4可以看出,随着树的数量和深度的增加,数据重建率逐渐升高,到达峰值后趋于平缓。对比3种随机森林的方法可以看出,无论是哪种情况下,KNN-Frost算法的性能都要优越于其他两种算法,这是因为该算法在构建随机森林前先对特征进行了筛选,使得构建的随机森林模型的分类效果得到了提升。

此外,由图5可以看出,随着数据丢失率的提高,数据的重建率逐渐下降,但KNN-Frost算法仍好于其他两种算法,并且当数据丢失率高达80%时,该算法依然可以达到恢复约70%的原始数据。这说明KNN-Frost算法仍然有着明显的较高的数据重建能力。

图3 树的深度为5和10的时不同树的深度与重建率的关系对比

图4 树的数量为10和15时集成树的数量与数据重建率的关系对比

图5 不同树深度和树数量下数据丢失率与数据重建率的关系对比

4 结 语

本文提出的KNN-Frost算法有效解决了无线网络传输中数据丢失的问题,改进了现有算法在重建数据时精度不高的弊端;通过构建基于KNN的特征选择算法,使得随机森林模型能够以更高精度给出预测值,从而实现较好的数据重建效果;KNN-Frost算法可以应对不同无线传感器网络结构中的数据重建问题,具有较好的适配性。

此外,KNN-Frost算法在丢失数据的特征值分类较多且数据集特征较少的情况下,数据重建的效果可能会下降。但无线传感器网络收集的数据特点通常是数据变化幅度较小,并且数据集巨大,这些特点使得KNN-Frost算法较适用于无线网络环境的数据重建。在未来的工作中,将针对特征值分类较多、数据特征较少的应用场景,在原算法的基础上尝试其他的特征选择方式,进一步改进算法,以期获取更好的结果。