第39卷 第2期 计算机工程 2013年2月 V01.39 No.2 Computer Engineering February 2013 ・人工智能及识别技术- 文章编号t 1o00—3428(2ol3)02—_017 4 文献标识码:A 中圈分类号l TP18 基于小波密度估计的数据流离群点检测 刘耀宗L ,张宏 ,盂锦 ,韩法旺 (1.南京理工大学计算机学院,南京210094;2.南京森林学院信息系,南京210046) 摘要:为能及时发现数据流上的局部离群点,分析数据流已有的离群点挖掘算法,提出基于小波密度估计的离群点检测 算法。利用小波密度估计多尺度和多粒度的特点,通过小波概率阈值判断数据流中当前滑动窗I=1内的数据点是否为离群点, 并对数据流中离群点检测过程进行讨论。仿真结果表明,与核密度估计算法相比,该算法的检测效率与精度较高。 关健词:数据流;局部离群点;离群点检测;核密度估计;小波密度估计 outliers Detection in Data Stream Based on 厂velet Density Estimation LIU Yao.zong ,一,ZHANG Hong ,MENG Jin ,HAN Fa-wang (1.School of Computer,Nanjing University of Science and Technology,Nanjing 2 1 0094,China; 2.Department ofInformation,Nanjing Forest Police College,Nanjing 210046,China) [AbstractI In order to ifnd local outliers in data stream,this paper anal ̄ zes traditional outliers detection algorithms,and intro— duces an outlier detection algorithm based Oil Wavelet Densiyt Estimation(WDE).It uses a multi—scale and multi-granularity characteristics of WDE using the wavelet probability threshold to judge the data stream within the current sliding window data points as outliers,and discusses outlier detection in data stream proceSs.Simulation results show that this algorithm has higher detection efifciency and accuracy in the data stream than Kenrel Densiyt Estimation(KDE)algorithm. [Key wordsl data stream;local outlier;outlier detection;Kenrel Densiyt Estimation(KDE);Wavelet Densiyt Esifmation(WDE) DOI:10.3969/j.issn.1000.3428.2013.02.036 l概述 数据与频繁模式的相异程度来度量数据的离群程度,从 数据流是近年来数据挖掘的研究热点之一,而数据 而动态地更新数据流中候选离群点的离群信息。然而, 流上离群点的检测是数据流挖掘重要的研究方向 J。 基于核函数的密度估计方法需要事先定义相应的核函 目前,针对数据流上的离群点检测研究己经取得了 数,无法对时变数据流进行灵活丰富的多尺度估计,不 不少成果,其中一些检测算法已得到应用。文献[3】研究 利于即时发现离群点,一般称之为局部离群点。文献[7] 数据流的离群点检测问题,并提出的异常的概念,主要 提出基于小波的数据流密度估计方法,克服了核密度估 介绍时间序列数据流的离群点检测问题。文献[4】针对分 计方法的不足,理论上优于传统密度估计技术。 布式数据流环境,提出基于核密度估计(Kernel Density 文献【3.6]的离群点检测方法比较偏重于数据流上全 Estimation,KDE) ̄分布式数据流的离群点检测算法。该 局离群点的发现,而不太重视局部离群点的检测。但在 算法的工作原理是将分布式数据流中各节点上的流数据 实际应用中,如对于正在生产的设备,若不能及时发现 作为全体数据流的一部分,计算各个节点的核密度估计 异常,所引起的损失和灾难是极其严重的。其次这些算 值,再得到全体数据流的离群点集合。文献[5]针对海量 法对数据流上离群点的定义也各不相同。如基于统计学 数据流的特点,提出一种基于网格和密度的增量式离群 和基于距离的离群点检测都依赖于给定数据集的“全局” 点挖掘算法,比较适合海量数据流的环境。文献[6]利用 分布,然后对于时变的流数据,数据通常并非均匀分布 作者倚介:刘耀宗(1974一),男,博士研究生,主研方向:数据流挖掘;张宏,教授、博士生导师;孟锦,博士研究生; 韩法旺,讲师、硕士 收稿日期:2012-03-16 修回日期:2012—05—31 E—mail:new025@126.corn 第39卷第2期 刘耀宗,张宏,孟锦,等:基于小波密度估计的数据流离群点检测 179 的,当各流数据块的分布密度相差很大时,局部离群点 测量值,从而使人们对它产生怀疑 J。可以设给定数据 将更加有意义。一个好的数据流离群点检测方法应该是 集 、数据点O∈ 、参数g和r,如果至多存在q个样 可以及时发现局部异常的 J。为此,本文提出一种基于 本点与O的距离在,.之内,则称O为离群点。 小波密度估计(Wavelet Density Estimation,WDE)的离群 2.2局部离群点 点检测算法。 数据流由于是动态变化的,及时发现局部离群点的 2基于WDE的数据流离群点检测 意义要大干全局离群点的检测。而局部离群点是指在数 据集中与其邻域表现不一致或大大地偏离其邻域的观 密度估计方法适合对流数据进行离群点检测,文献[4] 测点[引。 即采用核密度估计方法对分布式数据流进行全局离群点 对于某个数据对象O及其局部邻域观测分布情况, 的检测,但核密度估计的缺陷就是无法对时态数据流进 如果O的局部密度与邻域内的局部密度具有明显的差 行多尺度多粒度的分析,小波方法具有局部细节的表现 别,那么O可能为局部离群点 J。由于它的局部程度取 能力,同时小波密度估计也具有信号局部特征分析能力, 决于该数据对象相对于其邻域的孤立情况,可以视为局 适合于变化的数据流离群点上检测,从理论上看,小波 部的。通过这种方法可以判断出是否为局部离群点。 密度估计优于传统的核密度估计方法【7J。 基于距离的离群点定义没有考虑局部离群点的问 本文利用小波密度估计的多尺度和多粒度的特点, 题,比较适合全局离群点的检测 J。若使用数据密度估 采用概率阈值和密度估计判断数据流中当前滑动窗口内 计算法可以找出那些局部密度很小的数据点,即局部离 的数据点是否为离群点,并对离群点检测过程的细节进 群点,密度估计方法能有效检测出符合数据密度假设的 行讨论。 离群点 。 2.1基本定义 文献【5]把聚类簇视为密度估计值大的区域,而离群 定义1数据流(data stream) 点则视为密度估计值小的区域,采用数据密度值即可较 数据流是连续产生的按时间顺序生成的序列数据, 好地区分聚类簇与离群点,只要事先采用密度估计的方 为了研究方便,按数据块流入,也就是X={(Xl,t1), 法计算每个数据点附近的密度估计值。可得结论:有着 ( 2, ),…,( ,tf),…,( , )),其中,xi为 时刻到达的 相似密度估计值的数据可能是同一个范围的聚类簇,而 数据块,设 =(xi, ),每个数据块 由v个d维空间 密度估计值极低且与附近其他数据距离较远的数据点极 上的数据点组成。 有可能是离群点。 在实际对数据流进行离群点检测时通常是采用滑动 数据流局部离群点通常是检测可变长度的滑动窗口 窗口机制,窗口内的数据流是无限时态数据流的子集。 中数据块的信息而不是在固定窗口内检测 J。实际上, 定义2滑动窗13(sliding window) 异常的长度并不固定,在高速时变的数据流中的历史数 滑动窗13是用来观察最近一个时间段的数据流序 据可能会很快过时,基于可变长度的滑动窗口机制的数 列,该方法是对数据流取一长度为l 的滑动窗口,窗口 据流离群点检测方法可以检测数据流中持续时间长短不 大小受内存,并将该窗13等划分成大小1,的m个块, 同的离群点。 ,B2,…, ,其中,l = v。每有v个新数据到来, 定义4局部离群点(1ocal outlier) 记为 +l块,旧数据流窗口中的马移出窗口,am+1块 在数据流的离群点发现中,若仅需要关注数据点p 移入。 在一定区间内出现的概率,如果一个点出现的概率趋势 滑动窗口方法采用基于估计点的变化窗口大小的思 于0,则该点就有可能是离群点。 想,可以适应动态数据流变化中样本的分布,对提高估 用密度估计可以度量数据流中点的异常程度。为更 计的效果(精度和平滑度)具有比固定窗口大小更好的 好地区分离群点和正常点的数据密度,本文采用基于样 效果。 本点的数据密度估计方法的思想,即数据密度远小于附 定义3离群点(outlier) 近数据点密度的点可定义为离群点。 一个离群点是这样一个测量值,它过分地偏离其他 设r为异常检测半径,任意数据点 在距离r内概 180 计算机工程 2013年2月15日 率为: pf+r 可以计算出整个滑动窗口的全局小波密度估计,如 (p ,r)=Pr[pf— ,P +r]=』f(x)dx p 一 (1) 式(3)所示: 其中,f(x)为密度估计函数,本文采用小波密度估计 函数。 童 ):JI (川 1一 )季j一1(x)+ ) i≥2 f31 数据流到达后,如果数据点P 在距离r范围内的邻 居数为4 ,, - ,若数据点P 在范围r内的邻居数 l‘2.4小波概率阈值的计算 小波密度估计值的精确性取决于保留的系数,有 2种策略:(1)线性小波密度估计,适用于数据流去噪; , l ≤g,则数据点p 为离群点,g为设定的最少邻 居数。 为了能检测到滑动窗口内的离群点,对于任意数据 点p,,采用多粒度偏差因子MDEF(p , )衡量离群度,6c 为离群点抽样系数。设 , r)= ,at)・ I,标准差为 6MDEFo 标准差计算过程见文献[4],如果MDEF(pi, , )> g 踟F,则P 为局部离群点,其中,小波密度估计值是 整个滑动窗口的。 2.3小波密度估计 设数据流 , ,…, ≥1)为无限的数据流元素 序列的样本,数据流中元组 的特征由概率密度函数, 决定,而数据流的f是未知的,其小波密度估计函数计 算式为: ^ ,1 /( )= C jo, , ( )+ dj, ,Ax) (2) J=JO 其中,c A, 表示基本系统; ,代表阈值;尺度函数OJo, 描述了函数 的总体趋势;而小波函数 . ( )表现厂的 局部信息。系统的个数可能是无限的,由于系统受限, 必须对_厂的小波级数进行截取,估计值精度取决于保留 多少个系数。 将流入的数据等划分成块,采用基窗口对数据流块 进行小波密度估计,单独计算每个基窗口Bi的密度估计 ,前m个数据块的线性组合密度估计为季 ,采用一个 具有指数衰减的密度估计策略,该策略的基本思想是滑 动窗口中数据的权重随时间依次减少,超出滑动窗口之 外的历史数据其权重为0。衰减因子五决定了新接收的 流数据的重要程度,通过丑来调节新数据相对历史数据 的影响程度。 还可以表示窗口内流 的权值,满足0≤ ≤l,且∑ =l,定义为丑=(1- )/(1一 ),则 i=l g(x):∑4f ̄(x),营 (x):(1一五)季H(x)+ ( )。 (2)阈值小波密度估计,适用于离群点检测 J。而阈值小 波密度估计分为硬阈值和概率阈值,本文采用概率阈值 小波密度估计策略。 概率阈值小波密度估计本质上是一种非线性密度估 计方法,具有非常良好的局部适应特征,在收敛性和逼 近效果上均优于传统的线性小波密度估计 。 小波概率阈值设定的具体过程是Lfj:对于小波变换 中的每个非零的小波系数 ,采用随机变量Df以某一概 率取 ,并保留在小波系数序列中;而随机变量Df以某 一概率取0,即从小波系数序列中移除 ,条件是 E[Di]=di(数学期望)。 2.5基于WDE的数据流局部离群点检测算法 数据流的离群点检测算法需要增量地即时反馈出结 果,本文通过滑动窗口机制实时检测出局部离群点。基 于小波密度估计的数据流离群点算法描述如下: 算法WDE.Outlier 输入最新流入的数据元素 输出数据流 的离群点集合O Stepl数据流预处理,生成d维空间的时序点集 ; Step2滑动窗口内按序取m个数据点形成块x/; Step3根据式(2)计算基窗口的 ; Step4计算数据点p 在距离 范围内的邻居数; Step5根据式(3)计算整个滑动窗口的喜 ; Step6如果窗口满,则重新计算数据流的小波概率 阈值; Step7计算P 的多粒度偏差因子MDEF(pi,r,。【); Step8若MDEF(p ,r, )>g・ ̄MDEF,则输出Pf到集合0; Step9流入新的数据流块,继续Step2。 3实验结果与分析 为验证本文算法的有效性,用Matlab进行仿真实验, 采用2种数据集:(1)网络入侵检测数据集KDD-CUP一99, 该数据集由494 020个训练实例构成。由于原始数据集 第39卷第2期 刘耀宗,张宏,孟锦,等:基于小波密度估计的数据流离群点检测 181 过于庞大,而且分布不均匀,因此为方便实验,本文对 KDD.CUP.99原始数据作适当的修改,使得攻击(离群 点)只占数据集的2%,并对连续属性维进行归一离散 化。(2)仿真数据流(Synthetic Data S ̄eams),通过输入参 消耗时间较长。 4结束语 本文提出基于小波密度估计的数据流离群点检测算 法,对数据流按块用滑动窗口进行采样,并采用小波密 数来控制产生数据流维数、大小和离群点个数等,参数 为10维、1 000 KB,并均匀加入5%类具有一定偏差的 离群点。实验参数取lWI=100 KB,k=3,r=3,a=l/8。 本文算法将离群点检测的准确率以及运行的速度作 度估计方法进行离群点检测。理论分析和实验均表明, 该算法对于数据流上离群点的检测是可行和有效的。下 一步考虑将本文和研究成果应用于RFID数据流的清 为评测指标。并在同等实验条件用核密度估计 的检测 方法进行了性能对比。 滑动窗口内准确率的定义如式(4)所示: 检测准确率= 蔫 熹篙 (4 为实验方便起见,不失一般性,将测试数据集均分 为1 0组,一次性提交一组数据集至滑动窗口进行离群点 检测,最后取10组数据集的离群点检测结果的平均值。 2种算法在2种数据集下的平均检测准确率比较如 图1所示,平均检测时间比较如图2所示。 】。。 匠 KDE算法 — 一95 7777,, [皿本文算法 羹90 蚕 80 m KDDCUP99 Synthetic Data Streams ————数据集 图1平均检测准确率比较 KDDCUP99 Synthetic Data Streams 数据集 图2平均检测时间比较 基于实验可得出,本文算法适合低维数据流的离群 点检测,且结果较为准确,高维数据流检测延时也不明 显,KDE算法因为有窗口的延迟,因此,对高维数据流 洗【Ⅲ 中。 参考文献 [1] 周晓云,孙志挥,张柏礼,等.高维类别属性数据流离 群点快速检测算[J].软件学报,2007,1 8(4):933-942. [2]单世民,邓贵仕,何英吴.数据流中孤立点识别方法[J]. 计算机工程,2007,33(15):172—174. [3]Muthukrishnan S,Shah R,Vitter J.Mining Deviants in Time Series Data Streams[C]//Proceedings of the 1 6th International Conference on Scientific and Statistical Database Management.Santorini Island,Greece:[S.n.], 2O04:41.50. [4]杨宜东,孙志挥,张 净.基于核密度估计的分布数 据流离群点检测[J].计算机研究与发展,2005,42(9): 1498.15o4. [5] 张净,孙志挥,杨宜东.基于网格和密度的海量数据 增量式离群点挖掘算法[J].计算机研究与发展,2011, 48(5):823—830. [6]唐向红,李国徽,杨观赐.快速挖掘数据流中离群点[J]. 小型微型计算机系统,201 1,32(10):9-16. [7]Alberta B.Adaptive Wavelet Density Estimators over Data Streams[C]//Proceedings of the 1 9th International Conference on Scientiifc and Statistical Database Management.Banf,Canada:[S.n.],2007:9-1 1. [8] 薛安荣,鞠时光,何伟华,等.局部离群点挖掘算法研 究[J].计算机学报,2007,3O(8):1455.1463. [9 胡彩平,秦小麟.一种基于密度的局部离群点检测算法 9]DLOF[J].计算机研究与发展,2010,47(12):2110-2116. 【10】廖国琼,李晶,万常选.基于核密度估计的RFID数 据流清洗方法[J].计算机研究与发展,2010,47(z1): 337.341. 编辑金胡考