基于top-k(σ)算法的异常数据检测方法
基于top-k(σ)算法的异常数据检测方法
【技术领域】
[0001] 本发明设及一种无线传感器网络异常数据检测方法，具体是设及一种基于 t〇p-k(〇 )算法的无线传感器网络异常数据检测方法。
【背景技术】
[0002] 在真实的生活环境中存在很多物理现象（比如温度、湿度、大气压力等）都需要持 续地被监测。无线传感器网络作为一种非常重要的数据来源，其采集的数据非常容易受到 各种噪声来源的影响，比如节点软硬件故障，节点通信时遇到的环境噪声。该些噪声会严重 影响传感器的读数，W及数据的分布情况，导致传感器产生不精确的或不正确的数据。因 此，设计一种有效的数据流分析处理方法是近年来无线传感器网络异常检测研究的重点。
[0003] 异常检测技术在各个领域中都是一个深入研究的问题，无线传感器网路独特的特 点W及严格的约束条件使得该问题的研究更具有挑战性。针对无线传感器网路中的异常数 据检测问题，目前已经提出过很多种方法，该些方法可W分为基于分布的、基于深度的、基 于聚类的、基于距离的W及基于密度的方法。此外，按照传感器网络体系机构异常检测技术 又可W集中分为集中式的和分布式的。
[0004] 化ai化SA等人提出的基于top-k算法在数据挖掘等领域中具有广泛的应用，该 算法主要是通过构造构造数据列表，将列表中的某列按数据特征进行升序排列，从而进行 异常数据的判断，该方法的优点是根据构造的数据列表可W直观地识别异常数据点分布的 区域及数目，且该方法在无线传感器网络异常数据检测应用中尚未见到。但是，由于目前大 规模无线传感器网络数据异常值的出现并无特定规律，如果传感器采集到的无线传感网络 数据的异常值持续、频繁出现，或者异常值在正常值周围分布比较均匀时，基于top-k算法 的无线传感器网络异常检测方法则不能有效地检测出异常值。
[0005] 因此，需要提出一种新型的无线传感器网络异常值检测方法。
【发明内容】
[0006] 发明目的；为了克服现有技术中存在的不足，本发明提供一种高检测率和低误报 率的基于top-k( 0 )算法的异常数据检测方法。
[0007] 技术方案：为实现上述目的，本发明的提供的一种基于top-k(o)算法的异常数 据检测方法，包括W下步骤：
[000引 S1 ;将传感器节点采集的数据进行数据标准化处理；
[0009] S2 ;根据处理后的数据的分布规律构造数据单元格，该数据单元格包括若干个小 数据单元格，小数据单元格表示为Cwj.，其中i表示小数据单元格的行号W及j表示小数据 单元格的列号；
[0010] S3 ;构造PC列表，所述PC列表包括四列数据，第一列数据表示小数据单元格Cw 的位置，第二列数据表示该小数据单元格Cwj.中数据点的个数，第二列数据用N(c)表示，第 S列数据Nd(C)表示该小数据单元格Cwj.的D领域内的数据点的个数，第S列数据用ND(C) 表示，第四列数据RD表示分布数据集到中屯、数据集的距离，第四列数据用RD表示；
[0011] S4 ;将小数据单元格Cw中数据点的个数填入所述PC列表中与该小数据单元格 Cw对应的第二列数据中，将小数据单元格CW的D领域内的数据点的个数填入所述PC列 表中与该小数据单元格Cwj对应的第=列数据中，将分布数据集到中屯、数据集的距离填入 所述PC列表中与该小数据单元格Cwj对应的第四列数据中。
[0012] S5 ;将所述PC列表中的第S列数据进行升序排列；
[001引 S6 ;将排列后的PC列表中位于上层位置的对应的小数据单元格Cw中的数据点 作为潜在异常数据点；
[0014] S7 ;将所述潜在异常数据点对应的小数据单元格Cw对应的第四列数据分别与阔 值0进行比较，如果第四列数据大于阔值0,则与该第四列数据对应的小数据单元格Cw 内的数据点为异常数据点，否则与该第四列数据对应的小数据单元格Cwj.内的数据点为正 常数据点。
[0015] 进一步地，步骤S3中所述小数据单元格Cwj的D领域表示^点〇为中屯、，D为半 径的领域，其中所述点0位于所述小数据单元格Cwj.的正中屯、，所述半径D为正数。
[0016] 进一步地，步骤S3中计算分布数据集到中屯、数据集的距离包括W下步骤：
[0017]S31;设传感器节点采集的所有数据点的集合为样本集r，所述中屯、数据集是指 所述样本集r中正常数据点的集合，所述分布数据集是指所述样本集r中任一子集；
[0018] S32;设数据点〇1是所述中屯、数据集的中屯、数据点，设数据点〇2是所述分布数据集 的中屯、数据点；
[0019]S33 ;计算所述数据点〇1和所述数据点02之间的欧式距离，则所述数据点0 1和所 述数据点〇2之间的欧式距离为所述分布数据集到所述中屯、数据集的距离。
[0020] 进一步地，步骤S7中所述阔值0的取值范围是2. 5~3。
[002U 有益效果；本发明提出的基于top-k(0 )算法主要是针对现有技术中基于top-k 算法的改进，具有的优点是：
[0022] 1、利用基于top-k算法对异常值进行检测时，当异常点在某个单元格内分布比较 密集时，根据Nd(C)所在的列按升序排列后，异常点所在的数据单元格就不会位于PC列表 的前几行，该样容易将异常值误判为正常值；或者当正常数据点分布疏散，根据Nd(C)所在 的列按升序排列后，正常数据点所在的数据单元格可能会出现在PC列表的前几行，该样容 易将正常值误判为异常值；而本发明通过增设距离阔值0和PC列表中数据列RD，利用位 于PC列表中前几行的RD的值与阔值0进行比较来判定无线传感器网络数据异常情况，有 效避免了把异常值误判为正常值或者有效避免了将正常值误判为异常值，大大降低了本发 明算法的误报率，通过具体仿真实验发现，本发明提出的算法的误报率比基于top-k算法 降低了 4.48% ;
[0023] 2、本发明通过调整阔值0的取值大大提高了本发明算法的检测率，通过具体仿 真实验发现，本发明提出的算法检测率达到了 93. 7%，本发明的算法与基于top-k算法比 较检测率提高了 4.94%。
【附图说明】
[0024] 图1是本发明提出的基于top-k(0)算法的异常数据检测方法的流程图；
[0025] 图2是单元格领域示意图；
[0026] 图3是分布数据集到中屯、数据集的距离示意图；
[0027] 图4是样本数据分布示意图；
[002引 图5是不同的阔值0所对应的top-k(0)算法的检测率；
[0029] 图6是不同的阔值0所对应的top-k(0)算法的误报率；
[0030] 图7是基于top-k算法和基于top-k(0)算法两种算法的检测率的对比图； [003U图8是基于top-k算法和基于top-k(0)算法两种算法的误报率的对比图。
【具体实施方式】
[0032] 下面结合实施例对本发明作更进一步的说明。
[003引本发明提出的一种基于top-k(o)算法的异常数据检测方法，参照图1，当无线传 感器网络应用于环境检测时，传感器节点采集的数据属性包括温度、湿度、大气压力等，该 些数据属性的度量单位不一致，所W在利用本发明的方法时首先需要对传感器节点采集的 数据进行数据标准化处理；
[0034] 然后根据处理后的数据的分布规律构造数据单元格，数据点分布在数据单元格 中，该数据单元格是由若干个小数据单元格组成，也可W说是由若干个矩形网格组成，其中 每一个小数据单元格可W表示为Cwj.，其中i表示小数据单元格在数据单元格中的行号W 及j表示小数据单元格在数据单元格中的列号，参照图4,数据单元格是一个7行7列的数 据单元格W第7行第5列的小数据单元格为例，该小数据单元格表示为
[0035] 接着构造PC列表，所述PC列表包括 四列数据，第一列数据表示小数据单元格在数 据单元格中的位置，用Cw表示，第二列数据表示该小数据单元格Cw中数据点的个数，用 N似表示，第S列数据表示该小数据单元格Cw的D领域内的数据点的个数，用Nd似表 示，第四列数据表示分布数据集到中屯、数据集的距离，用RD表示；其中小数据单元格Cwj 的D领域是指^点0为中屯、，D为半径的领域，参照图2,图2中每个矩形方格表示一个小 数据单元格，W正中间的小数据单元格为例，正中间的小数据单元格的D领域就是W点0为 中屯、，D为半径的圆形领域，其中点0位于所述正中间的小数据单元格的正中屯、位置，半径D 为正数，W图4为例，小数据单元格C,xe的D领域内的数据点的个数为2个，小数据单元格 C7xe中数据点的个数为1个；
[0036] 当实际进行检测时，传感器节点采集的数据样本非常大，需要通过计算得到小数 据单元格Cwj.中数据点的个数和D领域内的数据点的个数；
[0037] 设小数据单元格Cw的中屯、点为〇1，则为中心r为半径的领域即为小数据单 元格Cw的r领域内数据点的个数，假定0i的r邻域集和0i的r邻域内数据点个数分别表 示成DN(〇i)和#DN(〇i)。设Ai和AJ分别表示两个独立的d维正态随机向量，均值分别为Ui =[U。，. . .，ujT和U产[U"，. . .，Uw]T，协方差分别为 diag(0. ..，0"2)和Zj =diag( 0 "2,. . . ,0jd])，则Ai_Aj~N(U 2j)，设Pr(0。Oj,r)表示OjGDN(0i)的 概率，则
[003引Pr(0。Oj,r) = /rN(Ui-Uj,ZZj)dA(1)
[0039] 其中，R是W相-Uj)为圆心r为半径的圆；
[0040]设〇郝0典别表示两个二维数据样本，其属性满足A i~N(u。Zi)和 Aj~N(u非Zj)，而Ui= [u…ujT，Uj= [u "，Uj'2]t和Zi=diag( o "2, o。2)，zj二 diag(0/，。巧2)。则
[0041] Pr(〇i，Oj，r)可表示为：
[0042]
[0043] 其中，ai=u。-11"和a2=un-Uj'2;
[0044] 假走oii=oji=o。=oj2=o,并使a2=ai2+a22,因此，公式似可间化为；
[0045]
(3)
[0046] 由公式（3)可知，Pr(〇i，o^)的大小不受〇i，o巧?差的影响，其大小仅仅取决于a2 的大小，因此，Pr(0。Oj,r)可用Pr(a,r)表示，a表示为（〇iGr}和{〇jGr}的欧拉距 离的均值，则对于每个二维数据CVPr(0。Oj.，r)的累积值就是〇i的r邻域内数据点个数， 良P#DN(〇i) + =Pr(0。Oj,r);
[0047] 接着计算分布数据集到中屯、数据集的距离RD，首先介绍几个概念；假设传感器节 点采集的所有数据点的集合为样本集r，则中屯、数据集是指所述样本集r中正常数据点 的集合，分布数据集是指所述样本集r中任一子集，设数据点〇1是所述中屯、数据集的中屯、 数据点，设数据点〇2是所述分布数据集的中屯、数据点，则所述数据点01和所述数据点0 2之 间的欧式距离就是所述分布数据集到所述中屯、数据集的距离RD，参照图3,设A为中屯、数据 集，B为分布数据集，则中屯、数据集A到分布数据集B的距离RD就是计算中屯、数据集A的 中屯、数据点〇1到分布数据集B的中屯、数据点02之间的欧式距离；
[0048] 接着将小数据单元格Cw中数据点的个数填入所述PC列表中与该小数据单元格 Cw对应的第二列数据N似中，将小数据单元格CW的D领域内的数据点的个数填入所述 PC列表中与该小数据单元格Cw对应的第；列数据Nd似中，将分布数据集到中屯、数据集 的距离填入所述PC列表中与该小数据单元格Cwj对应的第四列数据RD中，W图4为例，小 数据单元格C,xe的D领域内的数据点的个数Nd(C)为2,小数据单元格C,xe中数据点的个 数N(C)为1，分布数据集到中屯、数据集的距离RD为3. 04。
[0049] 将若干个小数据单元格Cw的数据特性；包括N(C)、Nd似和畑分别填入所述PC 列表中，接着将所述PC列表中的第S列数据Nd(C)按照数值大小进行升序排列，该样Nd(C) 数据较小的对应的小数据单元格就位于PC列表的上层，也就是PC列表的最前面几行，将排 在PC列表中最前面几行且Nd(C)值明显低于其他Nd(C)值的对应的第四列数据RD与阔值 曰进行比较，如果第四列数据RD远远大于阔值0,则与该第四列数据RD对应的小数据单 元格Cwj.内的所有数据点判定为异常数据点，否则判定为正常数据点。
[0化日]作为优选，所述阔值0的取值范围是2. 5~3。
[0化1] 实施例；首先根据样本数据点的分布规律构造数据单元格，参照图4,是一个简单 的数据样本分布示意图，该数据单元格是一个7行7列的数据单元格，该数据单元格中包 括多个小矩形网格，该小矩形网格就是小数据单元格，小数据单元格表示为Cwj，其中i= 1，…，7;j= 1，…，7,可W看出在该数据单元格中大多数数据点集中在第3行第6列即数 据单元格Csxe中，则该数据点集合作为中屯、数据点集合；然后构造PC列表，分别将各个小 数据单元格中数据点的个数填入PC列表第二列中，将小数据单元格的D领域内数据点的个 数填入PC列表第S列中，将分布数据集到中屯、数据集的距离填入PC列表第四列中，本发明 实施例选取了图4数据单元格中的14个小数据单元格，分别将14个小数据单元格的各个 特征值（包括N(C)、Nd(C)和畑）填入PC列表中，PC列表如表1所示；
[00巧表1
[0053]
[0054] 接着将PC列表中的第S列数据即Nd(C)列进行升序排列，经排列后发现，数据单 元格的D领域内数据点个数较少的就自然出现再PC列表的最前面几行，则将排在PC列表 中前面几行的数据单元格中所有数据点作为潜在异常数据点，表1中，可W将PC列表中前 面5行对应的数据单元格（即C7X日、(：7><7^3乂2、〔4乂2、〔7乂日）中的所有数据点作为潜在异常点； 接着将5个数据单元格（即C7xg、C7x7、C3X2、C4X2、C7><e)分别对应的畑值与阔值。进行比 较，数据单元格Cyxe对应的RD值为3. 04,而本发明所述阔值0的取值范围是2. 5~3,则 数据单元格C,xe对应的RD值大于阔值0，所W数据单元格中的所有数据点即为异常数 据点；同理，数据单元格C7X7的畑值为3. 63,则数据单元格C7X7对应的畑值大于阔值0， 所W数据单元格C7X7中的所有数据点即为异常数据点，数据单元格C3X2的RD值为3.37，贝。 数据单元格C3X2对应的RD值大于阔值0，所W数据单元格C3X2中的所有数据点即为异常 数据点，数据单元格C4X2的畑值为3. 35,则数据单元格C4X2对应的畑值大于阔值0，所 W数据单元格C4X2中的所有数据点即为异常数据点，数据单元格C7xe的RD值为3. 36,则数 据单元格C,xe对应的RD值大于阔值0，所W数据单元格C 中的所有数据点即为异常数 据点。
[00巧]实验验证：
[0化6] 本文利用MTLAB巧2010b)软件平台，对所提出的无线传感器网络异常数据检测 方法进行仿真分析。实验数据来源于无线传感器网络野外实验系统，该系统采样频率为每 隔10分钟采样一次。选择编号为1391的节点在2013年4月份测得的温度、湿度作为实 验数据。共进行了五组不同样本大小的仿真实验，仿真实验选取的样本数据大小分别为50 组、100组、400组、800组和1000组。
[0化7]为了评价和比较两种无线传感器网络异常数据检测方法的性能，本文使用检测 率、误报率作为主要性能评价指标。检测率是指算法检测到的异常数据样本数与实际的异 常数据样本总数之比；误报率是指被算法误判为异常的正 常数据样本数与总的正常数据样 本数之比。
[005引验证参数0对算法top-k(0)性能的影响；
[0化9]为了比较参数0对top-k(〇 )算法性能的影响，本文针对50组数据、100组数据、 400组数据、800组数据W及1000组数据该五个不同规模的样本集进行实验。通过实验发 现，上述样本集随参数0取值的不同，其相应的检测率和误报率也随之发生变化，实验结 果如图6和图7所示，横坐标表示所选取的五个样本（分别用样本1、样本2、样本3、样本4 及样本5表示），纵坐标则表示算法所对应的检测率、误报率。
[0060] 本实验主要选取0 = 2, 0 = 2. 5, 0 = 3W及0 = 3. 5该四个参数值进行实 验，根据图5和图6不难发现，当0 =2时，其检测率维持在98%W上，但其所对应的误报 率也相对较高。该是因为0参数选取越小，top-k(o)算法进行异常情况判断的区域随之 变大（即，如果之前将0 >3区域判为异常值，现在需将0 >2区域判为异常值），该区域 内的异常数据通过算法可快速识别出来，但同时也容易将该区域内的部分正常数据误判为 异常值。此时，算法的检测率相对较高（维持在98%W上），但误报率也相对较高（平均达 到了 1.6% );
[0061] 当0 = 3. 5时，算法进行异常判断的区域缩小（即如果之前将0 > 3区域判为 异常值，现在需将0 >3.5区域判为异常值），故此区域内很多异常点难W通过该算法识别 出来，则其检测率就较低（维持在65%左右），但其误报率却很低，降到0. 5%W下。通过上 述分析可知，当0取在2. 5和3之间时，既能保证top-k(o)算法在维持较高检测率的同 时，也能最大程度地降低误报率；
[0062] 综上所述，所述阔值0的取值范围是2. 5~3。
[0063] 验证数据样本规模对算法性能的影响：
[0064] 根据上述实验中的参数0对top-k(0)算法性能的影响，该里取0= 3作为参 照，为了比较top-k与top-k(O)两种算法的检测效果，利用top-k算法与ttop-k(O)算 法分别对五组不同规模大小的实验样本进行多次实验。
[0065] 通过该实验发现，top-k算法与top-k(0)算法检测率的对比如图7所示，其误报 率对比如图8所示。横坐标表示所选取的五个样本（分别用样本1、样本2、样本3、样本4 及样本5表示），纵坐标则表示算法所对应的检测率、误报率，柱形图中空屯、柱形条表示的 是top-k算法，实屯、柱形条表示的是top-k(0)算法。
[0066] 当选用实验数据样本较少、数据分布较疏散（即样本1)时，top-k(0)算法的检 测率明显高于top-k算法，该是因为受样本数目及其数据分布的影响，top-k算法只能识 别某单元格邻域内的相应数据点，但不能判断各个单元格数据点间的相对距离是否在其异 常范围之外，而top-k(O)算法通过引进阔值0很好地弥补了该缺陷，故在该种情况下， top-k(0)算法的检测率高出top-k算法16. 66%，相应地误报率降低了 2. 08%。
[0067] 随着实验样本数目的不断变大，top-k算法的检测率逐步提高，误报率也相应降 低，该是因为样本数目的增多，正常数据点与异常数据点有了明显的区域差别（即两种数 据点的分布差异明显）。此时，异常区域范围内的数据点个数远少于正常数据点个数，故 top-k算法能容易识别大部分异常值。但top-k(O)算法的检测率始终高于top-k算法，W 及误报率低于top-k算法。其原因是top-k(0)算法是建立在top-k算法的基础上，通过 增设阔值0，使其算法的判断精度更精确，该样可W识别一些top-k算法无法识别的异常 值。
[0068] W上所述仅是本发明的优选实施方式，应当指出；对于本技术领域的技术人员来 说，在不脱离本发明原理的前提下，还可W做出若干改进和润饰，该些改进和润饰也应视为 本发明的保护范围。
【主权项】
1. 基于top-k(O)算法的异常数据检测方法，其特征在于：包括以下步骤： 51 :将传感器节点采集的数据进行数据标准化处理； 52 :根据处理后的数据的分布规律构造数据单元格，该数据单元格包括若干个小数据 单元格，小数据单元格表示为CiXj，其中i表示小数据单元格的行号以及j表示小数据单元 格的列号； 53 :构造PC列表，所述PC列表包括四列数据，第一列数据表示小数据单元格Cm的位 置，第二列数据表示该小数据单元格Ci>Q_中数据点的个数，第二列数据用N(C)表示，第三列 数据Nd (C)表示该小数据单元格Cixj的D领域内的数据点的个数，第三列数据用ND (C)表 示，第四列数据RD表示分布数据集到中心数据集的距离，第四列数据用RD表示； 54 :将小数据单元格Cm中数据点的个数填入所述PC列表中与该小数据单元格CiXj 对应的第二列数据中，将小数据单元格Ci&的D领域内的数据点的个数填入所述PC列表中 与该小数据单元格Cixj对应的第三列数据中，将分布数据集到中心数据集的距离填入所述 PC列表中与该小数据单元格Ci>Q_对应的第四列数据中。 55 :将所述PC列表中的第三列数据进行升序排列； 56 :将排列后的PC列表中位于上层位置的对应的小数据单元格Ci>Q_中的数据点作为 潜在异常数据点； 57 :将所述潜在异常数据点对应的小数据单元格Cm对应的第四列数据分别与阈值〇 进行比较，如果第四列数据大于阈值〇，则与该第四列数据对应的小数据单元格Ci>Q_内的 数据点为异常数据点，否则与该第四列数据对应的小数据单元格Ci>Q_内的数据点为正常数 据点。2. 根据权利要求1所述的基于top-k( 〇 )算法的异常数据检测方法，其特征在于：步 骤S3中所述小数据单元格Ci>Q_的D领域表示以点〇为中心，D为半径的领域，其中所述点 〇位于所述小数据单元格Cixj的正中心，所述半径D为正数。3. 根据权利要求1所述的基于top-k( 〇 )算法的异常数据检测方法，其特征在于：步 骤S3中计算分布数据集到中心数据集的距离包括以下步骤： 531 :设传感器节点采集的所有数据点的集合为样本集r，所述中心数据集是指所述 样本集r中正常数据点的集合，所述分布数据集是指所述样本集r中任一子集； 532 :设数据点〇1是所述中心数据集的中心数据点，设数据点〇2是所述分布数据集的中 心数据点； 533 :计算所述数据点〇1和所述数据点〇 2之间的欧式距离，则所述数据点〇 :和所述数 据点〇2之间的欧式距离为所述分布数据集到所述中心数据集的距离。4. 根据权利要求1所述的基于top-k( 〇 )算法的异常数据检测方法，其特征在于：步 骤S7中所述阈值〇的取值范围是2. 5~3。
【专利摘要】本发明公开了一种基于top-k(σ)算法的异常数据检测方法，通过构造PC列表，将潜在异常数据点对应的小数据单元格对应的第四列数据分别与阈值进行比较，如果大于阈值，则与该第四列数据对应的小数据单元格内的数据点为异常数据点，否则为正常数据点；有效避免了把异常值误判为正常值或者有效避免了将正常值误判为异常值，大大降低了本发明算法的误报率，通过具体仿真实验发现，本发明提出的算法的误报率比基于top-k算法降低了4.48％；本发明通过调整阈值的取值大大提高了本发明算法的检测率，通过具体仿真实验发现，本发明提出的算法检测率达到了93.7％，本发明的算法与基于top-k算法比较检测率提高了4.94％。
【IPC分类】H04W24/08, H04W84/18, G06F17/30
【公开号】CN104902509
【申请号】CN201510256798
【发明人】李光辉, 胡石, 冯海林
【申请人】浙江农林大学
【公开日】2015年9月9日
【申请日】2015年5月19日
【技术领域】
[0001] 本发明设及一种无线传感器网络异常数据检测方法，具体是设及一种基于 t〇p-k(〇 )算法的无线传感器网络异常数据检测方法。
【背景技术】
[0002] 在真实的生活环境中存在很多物理现象（比如温度、湿度、大气压力等）都需要持 续地被监测。无线传感器网络作为一种非常重要的数据来源，其采集的数据非常容易受到 各种噪声来源的影响，比如节点软硬件故障，节点通信时遇到的环境噪声。该些噪声会严重 影响传感器的读数，W及数据的分布情况，导致传感器产生不精确的或不正确的数据。因 此，设计一种有效的数据流分析处理方法是近年来无线传感器网络异常检测研究的重点。
[0003] 异常检测技术在各个领域中都是一个深入研究的问题，无线传感器网路独特的特 点W及严格的约束条件使得该问题的研究更具有挑战性。针对无线传感器网路中的异常数 据检测问题，目前已经提出过很多种方法，该些方法可W分为基于分布的、基于深度的、基 于聚类的、基于距离的W及基于密度的方法。此外，按照传感器网络体系机构异常检测技术 又可W集中分为集中式的和分布式的。
[0004] 化ai化SA等人提出的基于top-k算法在数据挖掘等领域中具有广泛的应用，该 算法主要是通过构造构造数据列表，将列表中的某列按数据特征进行升序排列，从而进行 异常数据的判断，该方法的优点是根据构造的数据列表可W直观地识别异常数据点分布的 区域及数目，且该方法在无线传感器网络异常数据检测应用中尚未见到。但是，由于目前大 规模无线传感器网络数据异常值的出现并无特定规律，如果传感器采集到的无线传感网络 数据的异常值持续、频繁出现，或者异常值在正常值周围分布比较均匀时，基于top-k算法 的无线传感器网络异常检测方法则不能有效地检测出异常值。
[0005] 因此，需要提出一种新型的无线传感器网络异常值检测方法。
【发明内容】
[0006] 发明目的；为了克服现有技术中存在的不足，本发明提供一种高检测率和低误报 率的基于top-k( 0 )算法的异常数据检测方法。
[0007] 技术方案：为实现上述目的，本发明的提供的一种基于top-k(o)算法的异常数 据检测方法，包括W下步骤：
[000引 S1 ;将传感器节点采集的数据进行数据标准化处理；
[0009] S2 ;根据处理后的数据的分布规律构造数据单元格，该数据单元格包括若干个小 数据单元格，小数据单元格表示为Cwj.，其中i表示小数据单元格的行号W及j表示小数据 单元格的列号；
[0010] S3 ;构造PC列表，所述PC列表包括四列数据，第一列数据表示小数据单元格Cw 的位置，第二列数据表示该小数据单元格Cwj.中数据点的个数，第二列数据用N(c)表示，第 S列数据Nd(C)表示该小数据单元格Cwj.的D领域内的数据点的个数，第S列数据用ND(C) 表示，第四列数据RD表示分布数据集到中屯、数据集的距离，第四列数据用RD表示；
[0011] S4 ;将小数据单元格Cw中数据点的个数填入所述PC列表中与该小数据单元格 Cw对应的第二列数据中，将小数据单元格CW的D领域内的数据点的个数填入所述PC列 表中与该小数据单元格Cwj对应的第=列数据中，将分布数据集到中屯、数据集的距离填入 所述PC列表中与该小数据单元格Cwj对应的第四列数据中。
[0012] S5 ;将所述PC列表中的第S列数据进行升序排列；
[001引 S6 ;将排列后的PC列表中位于上层位置的对应的小数据单元格Cw中的数据点 作为潜在异常数据点；
[0014] S7 ;将所述潜在异常数据点对应的小数据单元格Cw对应的第四列数据分别与阔 值0进行比较，如果第四列数据大于阔值0,则与该第四列数据对应的小数据单元格Cw 内的数据点为异常数据点，否则与该第四列数据对应的小数据单元格Cwj.内的数据点为正 常数据点。
[0015] 进一步地，步骤S3中所述小数据单元格Cwj的D领域表示^点〇为中屯、，D为半 径的领域，其中所述点0位于所述小数据单元格Cwj.的正中屯、，所述半径D为正数。
[0016] 进一步地，步骤S3中计算分布数据集到中屯、数据集的距离包括W下步骤：
[0017]S31;设传感器节点采集的所有数据点的集合为样本集r，所述中屯、数据集是指 所述样本集r中正常数据点的集合，所述分布数据集是指所述样本集r中任一子集；
[0018] S32;设数据点〇1是所述中屯、数据集的中屯、数据点，设数据点〇2是所述分布数据集 的中屯、数据点；
[0019]S33 ;计算所述数据点〇1和所述数据点02之间的欧式距离，则所述数据点0 1和所 述数据点〇2之间的欧式距离为所述分布数据集到所述中屯、数据集的距离。
[0020] 进一步地，步骤S7中所述阔值0的取值范围是2. 5~3。
[002U 有益效果；本发明提出的基于top-k(0 )算法主要是针对现有技术中基于top-k 算法的改进，具有的优点是：
[0022] 1、利用基于top-k算法对异常值进行检测时，当异常点在某个单元格内分布比较 密集时，根据Nd(C)所在的列按升序排列后，异常点所在的数据单元格就不会位于PC列表 的前几行，该样容易将异常值误判为正常值；或者当正常数据点分布疏散，根据Nd(C)所在 的列按升序排列后，正常数据点所在的数据单元格可能会出现在PC列表的前几行，该样容 易将正常值误判为异常值；而本发明通过增设距离阔值0和PC列表中数据列RD，利用位 于PC列表中前几行的RD的值与阔值0进行比较来判定无线传感器网络数据异常情况，有 效避免了把异常值误判为正常值或者有效避免了将正常值误判为异常值，大大降低了本发 明算法的误报率，通过具体仿真实验发现，本发明提出的算法的误报率比基于top-k算法 降低了 4.48% ;
[0023] 2、本发明通过调整阔值0的取值大大提高了本发明算法的检测率，通过具体仿 真实验发现，本发明提出的算法检测率达到了 93. 7%，本发明的算法与基于top-k算法比 较检测率提高了 4.94%。
【附图说明】
[0024] 图1是本发明提出的基于top-k(0)算法的异常数据检测方法的流程图；
[0025] 图2是单元格领域示意图；
[0026] 图3是分布数据集到中屯、数据集的距离示意图；
[0027] 图4是样本数据分布示意图；
[002引 图5是不同的阔值0所对应的top-k(0)算法的检测率；
[0029] 图6是不同的阔值0所对应的top-k(0)算法的误报率；
[0030] 图7是基于top-k算法和基于top-k(0)算法两种算法的检测率的对比图； [003U图8是基于top-k算法和基于top-k(0)算法两种算法的误报率的对比图。
【具体实施方式】
[0032] 下面结合实施例对本发明作更进一步的说明。
[003引本发明提出的一种基于top-k(o)算法的异常数据检测方法，参照图1，当无线传 感器网络应用于环境检测时，传感器节点采集的数据属性包括温度、湿度、大气压力等，该 些数据属性的度量单位不一致，所W在利用本发明的方法时首先需要对传感器节点采集的 数据进行数据标准化处理；
[0034] 然后根据处理后的数据的分布规律构造数据单元格，数据点分布在数据单元格 中，该数据单元格是由若干个小数据单元格组成，也可W说是由若干个矩形网格组成，其中 每一个小数据单元格可W表示为Cwj.，其中i表示小数据单元格在数据单元格中的行号W 及j表示小数据单元格在数据单元格中的列号，参照图4,数据单元格是一个7行7列的数 据单元格W第7行第5列的小数据单元格为例，该小数据单元格表示为
[0035] 接着构造PC列表，所述PC列表包括 四列数据，第一列数据表示小数据单元格在数 据单元格中的位置，用Cw表示，第二列数据表示该小数据单元格Cw中数据点的个数，用 N似表示，第S列数据表示该小数据单元格Cw的D领域内的数据点的个数，用Nd似表 示，第四列数据表示分布数据集到中屯、数据集的距离，用RD表示；其中小数据单元格Cwj 的D领域是指^点0为中屯、，D为半径的领域，参照图2,图2中每个矩形方格表示一个小 数据单元格，W正中间的小数据单元格为例，正中间的小数据单元格的D领域就是W点0为 中屯、，D为半径的圆形领域，其中点0位于所述正中间的小数据单元格的正中屯、位置，半径D 为正数，W图4为例，小数据单元格C,xe的D领域内的数据点的个数为2个，小数据单元格 C7xe中数据点的个数为1个；
[0036] 当实际进行检测时，传感器节点采集的数据样本非常大，需要通过计算得到小数 据单元格Cwj.中数据点的个数和D领域内的数据点的个数；
[0037] 设小数据单元格Cw的中屯、点为〇1，则为中心r为半径的领域即为小数据单 元格Cw的r领域内数据点的个数，假定0i的r邻域集和0i的r邻域内数据点个数分别表 示成DN(〇i)和#DN(〇i)。设Ai和AJ分别表示两个独立的d维正态随机向量，均值分别为Ui =[U。，. . .，ujT和U产[U"，. . .，Uw]T，协方差分别为 diag(0. ..，0"2)和Zj =diag( 0 "2,. . . ,0jd])，则Ai_Aj~N(U 2j)，设Pr(0。Oj,r)表示OjGDN(0i)的 概率，则
[003引Pr(0。Oj,r) = /rN(Ui-Uj,ZZj)dA(1)
[0039] 其中，R是W相-Uj)为圆心r为半径的圆；
[0040]设〇郝0典别表示两个二维数据样本，其属性满足A i~N(u。Zi)和 Aj~N(u非Zj)，而Ui= [u…ujT，Uj= [u "，Uj'2]t和Zi=diag( o "2, o。2)，zj二 diag(0/，。巧2)。则
[0041] Pr(〇i，Oj，r)可表示为：
[0042]
[0043] 其中，ai=u。-11"和a2=un-Uj'2;
[0044] 假走oii=oji=o。=oj2=o,并使a2=ai2+a22,因此，公式似可间化为；
[0045]
(3)
[0046] 由公式（3)可知，Pr(〇i，o^)的大小不受〇i，o巧?差的影响，其大小仅仅取决于a2 的大小，因此，Pr(0。Oj,r)可用Pr(a,r)表示，a表示为（〇iGr}和{〇jGr}的欧拉距 离的均值，则对于每个二维数据CVPr(0。Oj.，r)的累积值就是〇i的r邻域内数据点个数， 良P#DN(〇i) + =Pr(0。Oj,r);
[0047] 接着计算分布数据集到中屯、数据集的距离RD，首先介绍几个概念；假设传感器节 点采集的所有数据点的集合为样本集r，则中屯、数据集是指所述样本集r中正常数据点 的集合，分布数据集是指所述样本集r中任一子集，设数据点〇1是所述中屯、数据集的中屯、 数据点，设数据点〇2是所述分布数据集的中屯、数据点，则所述数据点01和所述数据点0 2之 间的欧式距离就是所述分布数据集到所述中屯、数据集的距离RD，参照图3,设A为中屯、数据 集，B为分布数据集，则中屯、数据集A到分布数据集B的距离RD就是计算中屯、数据集A的 中屯、数据点〇1到分布数据集B的中屯、数据点02之间的欧式距离；
[0048] 接着将小数据单元格Cw中数据点的个数填入所述PC列表中与该小数据单元格 Cw对应的第二列数据N似中，将小数据单元格CW的D领域内的数据点的个数填入所述 PC列表中与该小数据单元格Cw对应的第；列数据Nd似中，将分布数据集到中屯、数据集 的距离填入所述PC列表中与该小数据单元格Cwj对应的第四列数据RD中，W图4为例，小 数据单元格C,xe的D领域内的数据点的个数Nd(C)为2,小数据单元格C,xe中数据点的个 数N(C)为1，分布数据集到中屯、数据集的距离RD为3. 04。
[0049] 将若干个小数据单元格Cw的数据特性；包括N(C)、Nd似和畑分别填入所述PC 列表中，接着将所述PC列表中的第S列数据Nd(C)按照数值大小进行升序排列，该样Nd(C) 数据较小的对应的小数据单元格就位于PC列表的上层，也就是PC列表的最前面几行，将排 在PC列表中最前面几行且Nd(C)值明显低于其他Nd(C)值的对应的第四列数据RD与阔值 曰进行比较，如果第四列数据RD远远大于阔值0,则与该第四列数据RD对应的小数据单 元格Cwj.内的所有数据点判定为异常数据点，否则判定为正常数据点。
[0化日]作为优选，所述阔值0的取值范围是2. 5~3。
[0化1] 实施例；首先根据样本数据点的分布规律构造数据单元格，参照图4,是一个简单 的数据样本分布示意图，该数据单元格是一个7行7列的数据单元格，该数据单元格中包 括多个小矩形网格，该小矩形网格就是小数据单元格，小数据单元格表示为Cwj，其中i= 1，…，7;j= 1，…，7,可W看出在该数据单元格中大多数数据点集中在第3行第6列即数 据单元格Csxe中，则该数据点集合作为中屯、数据点集合；然后构造PC列表，分别将各个小 数据单元格中数据点的个数填入PC列表第二列中，将小数据单元格的D领域内数据点的个 数填入PC列表第S列中，将分布数据集到中屯、数据集的距离填入PC列表第四列中，本发明 实施例选取了图4数据单元格中的14个小数据单元格，分别将14个小数据单元格的各个 特征值（包括N(C)、Nd(C)和畑）填入PC列表中，PC列表如表1所示；
[00巧表1
[0053]
[0054] 接着将PC列表中的第S列数据即Nd(C)列进行升序排列，经排列后发现，数据单 元格的D领域内数据点个数较少的就自然出现再PC列表的最前面几行，则将排在PC列表 中前面几行的数据单元格中所有数据点作为潜在异常数据点，表1中，可W将PC列表中前 面5行对应的数据单元格（即C7X日、(：7><7^3乂2、〔4乂2、〔7乂日）中的所有数据点作为潜在异常点； 接着将5个数据单元格（即C7xg、C7x7、C3X2、C4X2、C7><e)分别对应的畑值与阔值。进行比 较，数据单元格Cyxe对应的RD值为3. 04,而本发明所述阔值0的取值范围是2. 5~3,则 数据单元格C,xe对应的RD值大于阔值0，所W数据单元格中的所有数据点即为异常数 据点；同理，数据单元格C7X7的畑值为3. 63,则数据单元格C7X7对应的畑值大于阔值0， 所W数据单元格C7X7中的所有数据点即为异常数据点，数据单元格C3X2的RD值为3.37，贝。 数据单元格C3X2对应的RD值大于阔值0，所W数据单元格C3X2中的所有数据点即为异常 数据点，数据单元格C4X2的畑值为3. 35,则数据单元格C4X2对应的畑值大于阔值0，所 W数据单元格C4X2中的所有数据点即为异常数据点，数据单元格C7xe的RD值为3. 36,则数 据单元格C,xe对应的RD值大于阔值0，所W数据单元格C 中的所有数据点即为异常数 据点。
[00巧]实验验证：
[0化6] 本文利用MTLAB巧2010b)软件平台，对所提出的无线传感器网络异常数据检测 方法进行仿真分析。实验数据来源于无线传感器网络野外实验系统，该系统采样频率为每 隔10分钟采样一次。选择编号为1391的节点在2013年4月份测得的温度、湿度作为实 验数据。共进行了五组不同样本大小的仿真实验，仿真实验选取的样本数据大小分别为50 组、100组、400组、800组和1000组。
[0化7]为了评价和比较两种无线传感器网络异常数据检测方法的性能，本文使用检测 率、误报率作为主要性能评价指标。检测率是指算法检测到的异常数据样本数与实际的异 常数据样本总数之比；误报率是指被算法误判为异常的正 常数据样本数与总的正常数据样 本数之比。
[005引验证参数0对算法top-k(0)性能的影响；
[0化9]为了比较参数0对top-k(〇 )算法性能的影响，本文针对50组数据、100组数据、 400组数据、800组数据W及1000组数据该五个不同规模的样本集进行实验。通过实验发 现，上述样本集随参数0取值的不同，其相应的检测率和误报率也随之发生变化，实验结 果如图6和图7所示，横坐标表示所选取的五个样本（分别用样本1、样本2、样本3、样本4 及样本5表示），纵坐标则表示算法所对应的检测率、误报率。
[0060] 本实验主要选取0 = 2, 0 = 2. 5, 0 = 3W及0 = 3. 5该四个参数值进行实 验，根据图5和图6不难发现，当0 =2时，其检测率维持在98%W上，但其所对应的误报 率也相对较高。该是因为0参数选取越小，top-k(o)算法进行异常情况判断的区域随之 变大（即，如果之前将0 >3区域判为异常值，现在需将0 >2区域判为异常值），该区域 内的异常数据通过算法可快速识别出来，但同时也容易将该区域内的部分正常数据误判为 异常值。此时，算法的检测率相对较高（维持在98%W上），但误报率也相对较高（平均达 到了 1.6% );
[0061] 当0 = 3. 5时，算法进行异常判断的区域缩小（即如果之前将0 > 3区域判为 异常值，现在需将0 >3.5区域判为异常值），故此区域内很多异常点难W通过该算法识别 出来，则其检测率就较低（维持在65%左右），但其误报率却很低，降到0. 5%W下。通过上 述分析可知，当0取在2. 5和3之间时，既能保证top-k(o)算法在维持较高检测率的同 时，也能最大程度地降低误报率；
[0062] 综上所述，所述阔值0的取值范围是2. 5~3。
[0063] 验证数据样本规模对算法性能的影响：
[0064] 根据上述实验中的参数0对top-k(0)算法性能的影响，该里取0= 3作为参 照，为了比较top-k与top-k(O)两种算法的检测效果，利用top-k算法与ttop-k(O)算 法分别对五组不同规模大小的实验样本进行多次实验。
[0065] 通过该实验发现，top-k算法与top-k(0)算法检测率的对比如图7所示，其误报 率对比如图8所示。横坐标表示所选取的五个样本（分别用样本1、样本2、样本3、样本4 及样本5表示），纵坐标则表示算法所对应的检测率、误报率，柱形图中空屯、柱形条表示的 是top-k算法，实屯、柱形条表示的是top-k(0)算法。
[0066] 当选用实验数据样本较少、数据分布较疏散（即样本1)时，top-k(0)算法的检 测率明显高于top-k算法，该是因为受样本数目及其数据分布的影响，top-k算法只能识 别某单元格邻域内的相应数据点，但不能判断各个单元格数据点间的相对距离是否在其异 常范围之外，而top-k(O)算法通过引进阔值0很好地弥补了该缺陷，故在该种情况下， top-k(0)算法的检测率高出top-k算法16. 66%，相应地误报率降低了 2. 08%。
[0067] 随着实验样本数目的不断变大，top-k算法的检测率逐步提高，误报率也相应降 低，该是因为样本数目的增多，正常数据点与异常数据点有了明显的区域差别（即两种数 据点的分布差异明显）。此时，异常区域范围内的数据点个数远少于正常数据点个数，故 top-k算法能容易识别大部分异常值。但top-k(O)算法的检测率始终高于top-k算法，W 及误报率低于top-k算法。其原因是top-k(0)算法是建立在top-k算法的基础上，通过 增设阔值0，使其算法的判断精度更精确，该样可W识别一些top-k算法无法识别的异常 值。
[0068] W上所述仅是本发明的优选实施方式，应当指出；对于本技术领域的技术人员来 说，在不脱离本发明原理的前提下，还可W做出若干改进和润饰，该些改进和润饰也应视为 本发明的保护范围。
【主权项】
1. 基于top-k(O)算法的异常数据检测方法，其特征在于：包括以下步骤： 51 :将传感器节点采集的数据进行数据标准化处理； 52 :根据处理后的数据的分布规律构造数据单元格，该数据单元格包括若干个小数据 单元格，小数据单元格表示为CiXj，其中i表示小数据单元格的行号以及j表示小数据单元 格的列号； 53 :构造PC列表，所述PC列表包括四列数据，第一列数据表示小数据单元格Cm的位 置，第二列数据表示该小数据单元格Ci>Q_中数据点的个数，第二列数据用N(C)表示，第三列 数据Nd (C)表示该小数据单元格Cixj的D领域内的数据点的个数，第三列数据用ND (C)表 示，第四列数据RD表示分布数据集到中心数据集的距离，第四列数据用RD表示； 54 :将小数据单元格Cm中数据点的个数填入所述PC列表中与该小数据单元格CiXj 对应的第二列数据中，将小数据单元格Ci&的D领域内的数据点的个数填入所述PC列表中 与该小数据单元格Cixj对应的第三列数据中，将分布数据集到中心数据集的距离填入所述 PC列表中与该小数据单元格Ci>Q_对应的第四列数据中。 55 :将所述PC列表中的第三列数据进行升序排列； 56 :将排列后的PC列表中位于上层位置的对应的小数据单元格Ci>Q_中的数据点作为 潜在异常数据点； 57 :将所述潜在异常数据点对应的小数据单元格Cm对应的第四列数据分别与阈值〇 进行比较，如果第四列数据大于阈值〇，则与该第四列数据对应的小数据单元格Ci>Q_内的 数据点为异常数据点，否则与该第四列数据对应的小数据单元格Ci>Q_内的数据点为正常数 据点。2. 根据权利要求1所述的基于top-k( 〇 )算法的异常数据检测方法，其特征在于：步 骤S3中所述小数据单元格Ci>Q_的D领域表示以点〇为中心，D为半径的领域，其中所述点 〇位于所述小数据单元格Cixj的正中心，所述半径D为正数。3. 根据权利要求1所述的基于top-k( 〇 )算法的异常数据检测方法，其特征在于：步 骤S3中计算分布数据集到中心数据集的距离包括以下步骤： 531 :设传感器节点采集的所有数据点的集合为样本集r，所述中心数据集是指所述 样本集r中正常数据点的集合，所述分布数据集是指所述样本集r中任一子集； 532 :设数据点〇1是所述中心数据集的中心数据点，设数据点〇2是所述分布数据集的中 心数据点； 533 :计算所述数据点〇1和所述数据点〇 2之间的欧式距离，则所述数据点〇 :和所述数 据点〇2之间的欧式距离为所述分布数据集到所述中心数据集的距离。4. 根据权利要求1所述的基于top-k( 〇 )算法的异常数据检测方法，其特征在于：步 骤S7中所述阈值〇的取值范围是2. 5~3。
【专利摘要】本发明公开了一种基于top-k(σ)算法的异常数据检测方法，通过构造PC列表，将潜在异常数据点对应的小数据单元格对应的第四列数据分别与阈值进行比较，如果大于阈值，则与该第四列数据对应的小数据单元格内的数据点为异常数据点，否则为正常数据点；有效避免了把异常值误判为正常值或者有效避免了将正常值误判为异常值，大大降低了本发明算法的误报率，通过具体仿真实验发现，本发明提出的算法的误报率比基于top-k算法降低了4.48％；本发明通过调整阈值的取值大大提高了本发明算法的检测率，通过具体仿真实验发现，本发明提出的算法检测率达到了93.7％，本发明的算法与基于top-k算法比较检测率提高了4.94％。
【IPC分类】H04W24/08, H04W84/18, G06F17/30
【公开号】CN104902509
【申请号】CN201510256798
【发明人】李光辉, 胡石, 冯海林
【申请人】浙江农林大学
【公开日】2015年9月9日
【申请日】2015年5月19日
最新回复(0)