两阶段的多元时间序列异常检测算法

两阶段的多元时间序列异常检测算法 两阶段的多元时间序列异常检测算法 第28卷第7期 2011年7月 计算机应用研究 ApplicationResearchofComputers V0l_28No.7 Ju1.20l1 两阶段的多元时间序列异常检测算法 王欣 (中国民航飞行学院计算机学院,四川广汉618307) 摘要:提出了一个两阶段的多元时间序列异常检测算法.该算法通过有界坐标系统(BCS)技术计算多元时 间序列样本之间的相似性,采用基于距离的方法实现异常检测.算法第一阶段采用K—means算法对数据进行聚 类,并按照一个启发式规则对其进行排序;第二阶段在聚类结果上采用循环嵌套算法进行异常检测,并通过两个 剪枝规则进行高效剪枝,提高了算法的效率.在两个实际数据集上进行实验,实验结果验证了算法的有效性. 关键词:多元时间序列;有界坐标系统;基于距离的异常检测 中图分类号:TP311;TP301.6文献标志码:A文章编号:1001—3695(2011)07—2466—04 doi:10.3969/j.issn.1001—3695.2011.07.017 Two—stageoutlierdetectioninmultivariatetimeseries WANGXi" (SchoolofComputerScience,CivilAviationFlightUniversityofChina,GuanghanSichuan 618307,China) Abstract:Thispaperproposedanefficienttwo— stagealgorithmfordetectingoutliersinmultivariatetimeseries(MTS)data- sets.Usedtheboundedcoordinatesystem(BCS)metrictomeasurethesimilaritybetweentwo MTSsamples,andmeasuredthe outliernessofasamplebyaveragedistancetoitsk-nearestneighbors.Itpartitionedthedataint oclusters,andusednestedloop algorithmtofindtop-noutliers.UtilizedaheuristicandtwopruningrulestoquicklyremoveM TSsamplesthatwerenotpossible outliercandidates,reducingsignificantlythedistancecomputationamongobjects.Experim entsonreal—worlddatasetsshowthe effectivenessoftheproposedalgorithm. Keywords:multivariatetimeseries:boundedcoordinatesystem;distance—basedOU山 erdetection 异常检测用来发现数据集中显着偏离于其他数据的数 据….基于距离的异常检测算法由于思想直观,易于实现而 得到了广泛的研究和应用.这一算法又大致分为循环嵌套的 算法,基于索引的算法和基于单元的算法.循环嵌套算法在大 数据集上效率低下,但维数可扩展性好;基于索引和基于单元 的算法则很难应用于高维数据集. 时间序列X={(t)l1?t?m}是一组变量在连续时间点t 七获得的一系列采样值,每个采样值是一个d维特征向量 X(t):((t),x(t),…,(t)).当d=1时,称为一元时间 序列;当d?2时则 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示多元时间序列(multivariatetimeseries, MTS),用m×d矩阵来表示,其中m是采样值个数,d是变量个 数J.多元时间序列广泛存在于各个领域,例如:在生产过程 监控领域,监控数据来源于多个传感器的连续记录;在飞行品 质监控领域,飞机上安装的大量传感器采集飞机从起飞到降落 过程中一系列与飞行性能和飞行状态相关的飞行数据.多 元时间序列同时具有数据量大,维度高,变量相关性高,大量噪 声干扰等特点,使异常检测更加困难. 本文在基于距离的异常检测算法基础上,针对循环嵌套算 法在大数据集上效率低下的问题,改进了传统的循环嵌套算 法,提出两阶段多元时间序列异常检测算法.算法首先对数据 集进行聚类,将得到的簇按照包含异常点可能性大小排序,然 后在数据上应用剪枝规则提高异常检测的效率.实验结果验 证了算法的可行性和有效性. 1问题描述及相关定义 本文要解决的问题是从一个MTS样本组成的数据集中, 挖掘出异常因子最高的前n个样本,研究工作集中于提高异常 检测算法的效率. 1.1多元时间序列的异常检测 定义1MTS样本的异常因子.对于MTS数据集D,给定 参数k和P?D,则样本P的异常因子定义为P与其个最近邻 的MTS样本的平均距离: 1 D(p)=?kNN(P)distBcs(p,g.)(1) kNN(p)表示P在集合D中的k个最近邻元素的集合, 其中, kNN查询时采用dist距离计算样本间的相似性,dist距离 的定义在后文中给出.(p)衡量了P的异常程度,D"(P)越 大,表示P越远离|j}一邻域内的近邻,处于分布的稀疏区域,成为 异常点的可能性越大. 定义2数据集|D中的第rt个异常点.给定MTS数据集 D,参数n,如果D中有n一1个样本g满足(q)?(P),则 P是D中的第n个异常点. 在上述定义的基础上,多元时间序列的异常检测描述为: 计算MTS数据集D中每个MTS样本的异常因子D0,将其按从 大到小降序排列,异常因子最高的前n个序列就是所求的异常 收稿日期:2010.12—22;修回日期:2011—02-17基金项目:国家自然科学基金资助 项目(60879022,60832012);中国民用航空局科技项 目(MHRD200801) 作者简介:王欣(1973一),男,四川绵阳人,副教授,博士,主要研究方向为数据挖掘 (cafucwx@163.~om). 第7期王欣:两阶段的多元时间序列异常检测算法?2467? 序列,即top—rt异常序列. 1.2多元时间序列的相似性度量 多元时间序列异常检测的基础是MTS样本之间的相似性 度量.一个MTS由于各变量之间的相关性,相似性度量不是 各变量所代表的一元序列的相似性的简单叠加.文献[6]将 多元时间序列组织成一个更长的一元时间序列再进行相似性 度量,这样会丢失变量之间的相关性信息.文献[7]提出一种 基于PCA的MTS相似性度量,其方法是计算两个MTS矩 阵的主成分之间夹角的余弦平方和.文献[2]在PCA和矩阵 范数的基础上,提出扩展的Frobenius范数(extendedFrobenius nornl,Eros)度量MTS之间的相似性,其方法是计算两个MTS 矩阵的主成分之间夹角余弦的加权和.但.s和Eros不满足 三角不等式. 本文采用Shen等人提出的有界坐标系统(boundedco— ordinatesystem,BCS)来度量MTS样本之间的相似性.BCS采 用PCA分析后得到的主成分参数(均值,方差,特征向量等)描 述高维数据集合,可以根据这些分布参数来计算MTS样本之 间的相似性.PCA计算样本协方差矩阵的一组 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 正交特征 向量{l1?i?d}(设数据集的维数为d),每个向量对应的特 征值A.表示将数据投影到该特征向量时数据的方差.用 表示PCA变换后的第i个主成分轴.数据点在上投影 的方差为or(A=or). 对于表示MTS样本的矩阵X,在PCA变换后的新坐标系 下的紧凑概要模式表示为BCS(=(O,一,).其中O 表示新坐标系的原点(X中多维向量的均值).=2o-e,表 示长度为2or的第i个主成分,特征向量e表示的方向,标 准差Or.表示上正负半轴的长度.可以看出是上以 长度为界的一个区段,称为有界主成分(boundedprincipal component).从几何的角度,MTS样本X的BCS表示可以看 做是以x中多维向量的均值为原点,以d个有界主成分为坐 标轴的d维坐标系统. 定义3MTS样本之间的相似性度量.考虑两个MTS样 本x和Y,其BCS表示分别为BCS(X)=O,,…,)和 BCS(:(O,,…,),则x和Y之间的相似性可以通 过以下的距离测度函数来度量: distBc5(BCS(X),BCS()=I1O一OIl2+ d..... ?Il一)ll(2)'I 其中,Il?lI表示向量的欧式范数.式(2)的前半部分是两个 坐标原点之间的平移距离,后半部分表示了X和Y的有界主 成分向量张成的坐标空间中每个坐标轴方向上相似性的累加, 其中综合了旋转和伸缩的因素. 使用dist吣度量MTS之间的相似性,具有以下优点:a) MTS的BCS表示是一个紧凑的模式表示,保留了时间序列的 主要特征,实现了数据压缩,减小了相似性匹配时的计算量; b)相似性度量dist的计算只与MTS的变量个数d有关,而 与序列的长度m无关,使得两个不等长序列之间的相似性度 量成为可能;e)BCS表示提取了主要特征,避免了原始时间序 列上点对点的比较,抑制了噪声的干扰;d)distBcs满足三角不 等式. 2TSOD-MTS算法 基于距离的异常检测中的循环嵌套算法通过循环扫描样 本集为各样本寻找近邻,复杂度为D(m)(m为数据集中样本 个数).从异常因子D.(P)的定义可以看出,要得到数据集中 异常因子最高的前n个对象,需要对每个对象进行kNN查询, 以获得每个对象的k个最近邻.循环嵌套算法采取的策略就 是使用两层循环,外循环遍历读取数据集中每个对象,内循环 对外循环读取的对象进行kNN查询,因此需要计算所有对象 两两之间的距离.提高基于距离的异常检测算法效率的关键 在于减少kNN查询时对象间距离计算的次数. 2.1TSOD?MTS算法的构造 针对循环嵌套算法存在的不足,本文提出两阶段的MTS 异常检测算法(two—stageoutlierdetectionforMTS,TSOD.MTS), 其中的关键是使用了一个启发式规则和两个剪枝规则. TSOD—MTS算法第一阶段对数据集进行大致聚类,然后采用启 发式规则估计每个簇包含异常点的可能性,按可能性从大到小 进行排序;第二阶段在聚类的结果上采用循环嵌套算法实现异 常检测,并通过两个剪枝规则进行高效剪枝,提高了算法的 效率. 在算法执行的过程中,保存已计算好的前n个异常点,记 minD.为这些异常点的值的最小值J,该值作为剪枝阈 值,随着已经检查数据集的增大而单调递增.当计算数据集中 的一个对象P的D.(P)值时,假设已从整个数据集的一个子集 中计算了P的D"(P),因为D.(P)随着已处理数据集的增大而 单调递减,当前的D.(P)值就是最终真正的D.(P)的上界.如 果当前的D(P)<minD.,就可以断定P不是异常点而将其进 行剪枝,转而处理数据集中下一个对象.根据上述分析,在循 环嵌套的执行过程中,如果剪枝阈值minD能够快速增大,则 对于大部分的正常数据计算其D(P)时就可以实现快速剪枝, 大大减少kNN查询时对象间距离计算的次数. 1)MTS的K—mealls聚类 用K.means算法对数据集进行大致聚类,得到包含k个簇 的集合LC={C.,C2,…,C},其中C为第i个簇,c为簇c的 中心.算法采用平方误差准则,使得每一个数据点到其最近的 簇中心的平方距离和被最小化. 算法1MTS的K—means聚类算法 输入:MTS序列数据集,聚类的数目k; 输出:k个簇. 随机选择k个点作为初始簇的中心(c,c,…,c); repeat 选择一个新序列样本,采用distBcs距离计算X与k个簇均值之 间的距离. ifdistBcs(X,cj):min{distBcs(X,c;)I1??},则将X指派到第J 个簇; 更新簇均值; until平方误差准则函数不再发生变化. 有两个指标可以大致估计一个簇中包含异常点的可能性 大小,一个是簇中元素的个数,用lCI表示;另一个是簇在特征 空间中的尺寸,用簇的半径rc大致表示.簇的半径是簇的中 心到该簇中最远点之间的距离,即rc=max{d(C,)?C, 1??JGli.基于聚类的离群挖掘算法通常将小簇(即IcI小 ? 2468?计算机应用研究第28卷 的簇)指定为异常簇,赢观的想法是异常点极可能包含在兀 素个数少的簇中.另一方面,尺寸大的簇有可能密度较低,导 致其中元素的D值较大,包含异常点的可能性较大.将这两 个因素综合起来,用一个指标来表示一个簇包含异常点的可能 性大小的估计(estimationofoutlyingdegreeofacluster),表示为 EODC=rc/ICl. 这一阶段的启发式规则可以描述为:聚类算法将数据集划 分为k个簇后,按EODC的值从大到小进行排序.假设排序后 的结果为EODC(C)?EODC(C)?…?EODC(C),排序后 的簇传递给第二阶段. 2)MTS的异常检测 这一阶段改进了传统的循环嵌套算法,在其基础上增加了 两个剪枝规则. 规则1如果D.(P)<minD",对象P被修剪而无须进行 kNN查询. 规则2对P进行kNN查询过程中,假设取q与P计算距 离以检查是否为近邻,又假设q已经计算过(q)值,则可以 利用D.(q)和三角不等式计算出D(P)的上界.如果该上界 值小于minD.,则对象P被修剪而无须进行kNN查询. 规则2推导如下:假设已经计算了对象q的异常因子 (q).对P进行kNN查询时,取q与P计算距离以检查是否 为近邻.对象g与q的个最近邻之间形成k个三角形,根 据三角不等式有: k ×distBcs(P,q)+ZlZEkNN(q) distscs(q,)> k ?distBcs(p,Zi)(3) 式(3)两边同除k,得到 1k distscs(P,g)+Da(g)>亡kq)distscs(p,)() q的k个最近邻不一定是P的个最近邻,因此有 1k EkN)distBcs(P)>D.(p)(5) 根据式(4)和式(5)得到 dist日cs(p,g)+D"(g)>D"(p)(6) 这样就得到(p)值的上界.如果该上界小于剪枝阈值 minD,即式(7)成立, 说明 关于失联党员情况说明岗位说明总经理岗位说明书会计岗位说明书行政主管岗位说明书 P不可能是异常点而无须再进行 kNN查询. distBcs(p,g)+D.(g)<minD.(7) 按照第一阶段的启发式规则排序后的簇集合传递给第二 阶段.循环嵌套算法依次从c到c检测异常点.因为首先 检测EODC值大的簇中的对象,导致剪枝阈值rainD.迅速增 大,因此对于占数据集绝大多数的正常数据,就会因为剪枝规 则1和2的作用,不必精确获得对象的k个最近邻,就可以确 定其为非异常点而中断kNN查询,减少了对象间距离计算的 次数.阈值minD增大越快,内循环kNN查询时的剪枝效率 越高. 算法2MTS的异常检测算法 输入:排序后的MTS序列的簇集合Lc,最近邻个数k,异常点个数 n; 输出:异常样本集合topO. 1:初始化剪枝阈值minD.+_JD,异常点集合t叩0+I 2:foreachCELC 3:foreachP?C 4:P的最近邻集合neighbours(p)一 5:foreach?LC 6:foreachq?C,q?p 7:ifdistBcs(p,q)<rainD"一D"(g) 8:goto3 9:endif 10:ifIneighbours(p)l<ordistBcs(P,q)<maxdist(P,neighbours (p)) 11:Neighbours(p)=proximity(p,neighbours(p)LIq,) 12:endif 13:iflneighbours(p)I=kandD.(P)<minD. 14:goto3 15:endif 16:endfor 17:endfor 18:topO=topOutliers(topOLip,n) 19:minD"=min(D(O)forallOintopO) 20:endfor 21:endfor 其中,maxdist(,S)返回与集合S中对象之间的最大距离;函 数proximity(,s,k)返回集合S中关于的k个最近邻;函数 topOutliers(S,n)返回集合S中D值最大的前n个对象. 2.2算法复杂度分析 TSOD—MTS算法的第一阶段采用K—means聚类算法,平均 时间复杂度为0(km×d),其中m表示MTS数据集中样本个 数,k表示聚类个数,d表示数据的维数.传统循环嵌套算法进 行异常检测时,为了精确获得每个对象的k个最近邻,需要计 算所有对象两两之间的距离,时间复杂度为O(m×d).本文 采用了一个启发式规则和两个剪枝规则对其进行改进.由于 异常数据的数目远远小于数据集中样本的总数,对于占数据集 绝大多数的正常数据对象,在搜索对象的个最近邻时,通过 高效的剪枝而尽可能早地中断kNN查询,大大减少了对象间 距离计算的次数,因此第二阶段具有近似线性的时间复杂度O (m×d).综合异常检测的两个阶段,TSOD.MTS算法的时间 复杂度与数据集大小成近似线性关系. 3实验与结果分析 本章对所提出的TSOD—MTS算法进行性能测试.算法代 码采用MATLAB8.0实现,实验平台配置为P41.8GHz,1GB 内存的PC,操作系统为WindowsXP.首先采用EEG数据进行 实验分析….EEG数据就是脑电图数据,是在测试者的64个 部位安装256Hz的电极同时测量得到的一组数据.数据收集 来源于两种人群:controlsubjects和alcoholicsubjects.一共有 122个测试者,每个测试者共进行120次测试;每个MTS样本 为256×64阶的矩阵.实验从原始EEG数据中选取了600个 MTS样本作为测试数据集,将标记有alcoholicsubjects的样本 作为异常样本.为了测试算法对数据集大小的伸缩性,取最近 邻个数k=10,异常点个数n=10,让数据集中MTS样本个数 从100增加到600,执行TSOD—MTS算法和循环嵌套算法所花 费的时间对比如图1所示.从图中可见,当样本的个数增加 时,循环嵌套算法所花费的时间与样本的个数呈近似二次方关 系,而TSOD.MTS算法与样本个数呈近似线性关系. 第二个实验是针对航空公司的QAR(quickaccessreco— rder)数据.QAR是飞机机载记录系统中的快速存储装置,可 第7期王欣:两阶段的多元时间序列异常检测算法?2469? 以同时记录几百到几千个传感器采集的飞行参数,大多数参数 的采样频率是1Hz.实验采用某航空公司的同一个航线上同 一 个机型的1200个航班的QAR数据,并从飞行参数中选择 了包含飞机性能和飞行状态的30个参数.为了使航班之间的 飞行数据具有可比性,将飞行过程划分为若干飞行阶段(滑 跑,起飞,爬升,巡航,下降,进近,着陆等),每个阶段的飞行数 据就构成一个MTS序列.由于各航班的同一个飞行阶段的时 间长短不一,数据集中的MTS是不等长序列.MTS序列中数 据趋势的突变或变量间相关关系的突变等都会使得序列呈现 出异常,其中可能蕴涵着飞机性能和飞行状态方面的重要信 息.取最近邻个数k=10,异常点个数n=5,在QAR数据集上 执行TSOD—MTS算法,得到五个偏离于大多数正常航班的包含 异常飞行阶段的航班.经航空公司的飞行品质监控的专家分 析,排除了其中的三个航班,剩下两个航班的异常分别是由于 飞行员的不规范操作和发动机性能衰退造成的.说明算法能 够有效地从大量的QAR数据中发现机组操作和飞行性能方面 存在的问题. 星 曹 4结束语 样本个数 图1对数据集大小的伸缩性对比 本文研究了多元时间序列上的异常检测问题,提出了 TSOD—MTS算法.算法采用BCS方法计算MTS样本之间的相 似性,采用基于距离的方法实现异常检测.为了提高异常挖掘 的效率,算法分为两个阶段.第一阶段采用K-means算法对数 据集进行大致聚类,并用一个启发式规则估计每个簇包含异常 点的可能性,按可能性从大到小进行排序;第二阶段在循环嵌 套算法的基础上增加了两个剪枝规则,可以有效地减少对象间 距离计算的次数,实现近似线性的时间复杂度.实验结果表 明,本文提出的算法是可行而有效的.进一步的研究内容主要 包括MTS相似性度量和异常程度度量的改进,以及算法效率 的优化等. 参考文献: [1]HODGEVJ,AUSTINJ.Asurveyofoutlierdetectionmethodologies [J].ArtificialIntelligenceReview,2004,22(2):85—126. [2]YANGK,SHAHABIC.APCA—basedsimilaritymeasureformuhivari. atetimeseries[C]//Procofthe2ndACMInternationalWorkshopon MultimediaDatabases.NewYork:ACMPress,2004:65-74. [3]孔成安,李文华,尹湛.利用QAR数据实施飞机性能监控[J].中 国民用航空,2008,94(1O):54—56. [4]ANGIULLIF,PIZZUTIC.Outliermininginlargehigh—dimensional datasets[J].IEEETransonKnowledgeandDataEngineering, 2005,17(2):203—215. [5]RAMASWAMYS,RASTOGIR,SHIMK.Efficientalgorithmsfor miningoutliersfromlargedatasets[C]//ProcofACMSIGMODIn— ternationalConferenceonManagementofData.NewYork:ACM Press,2000:427—438. [6]ZHANGXiao—lei,BEGLEITERH,PORJESZB,eta1.Eventrelated potentialsduringobjectrecognitiontasks[J].BrainResearchBulle- tin,1995,38(6):531—538. [7]SINGHALA,SEBORGDE.Patternmatchinginhistoricalbatchdata usingPCA[J].IEEEControlSystemsMagazine,2002,22(5): 53_63. [8]SHENHT,ZHOUX,HUANGZ,eta1.Statisticalsummarizationof contentfeaturesforfastnear—duplicatevideodetection[c]//Pmcof the15thACMInternationalConferenceonMultimedia.NewYork: ACMPress,2007:164—165. [9]JIANGMF,TSENGSS,SUCM.Two—phaseclusteringprocessfor outlierdetection[J].PatternRecognitionLetters,2001,22(6-7): 691—700. [1O]VuNH,GOPALKRISHNANV.Efficientpruningschemesfordis— tance—basedoutlierdetection[c]//ProcofEuropeanConferenceon MachineLearningandPrinciplesandPracticeofKnowledgeDiscovery inDatabases.London:Springer—Verlag,2009:160—175. [11]BAYSD,KIBLERD,PAZZANIMJ,eta1.TheUCIKDDarchiveof largedatasetsfordataminingresearchandexperimentation[J].ACM SIGKDDExplorationsNewsletter,2000,2(2):81—85. (上接第2465页) 参考文献: [1]CHIUCC,YEHYSH,CHOUJS.Afastalgorithmforreliability— orientedtaskassignmentinadistributedsystem[J].ComputerCom- munications,2002,25(17):1622—1630. [2]HSIEHCC.Optimaltaskallocationandhardwareredundancypolicies indistributedcomputingsystems[J].EuropeanJournalofOpera? tionalResearch,2003,147(2):430—447. [3]SHATZSM,WANGJP,GOTOM.Taskallocationformaximizingre— liabilityofdistributedcomputersystems[J].IEEETransonCom- puters,1992,41(9):1156—1168. [4]KARTIKS,MURTHYCSR.Taskallocationalgorithmsformaximi. zingreliabilityofdistributedcomputingsystems[J].IEEETranson Computers,1997,46(6):719-724. [5]VIDYARTHIDP,TRIPATHIAK.Maximizingreliabilityofdistribu- tedcomputingsystemswithtaskallocationusingsimplegeneticalgo— rithm[J].JournalofSystemsArchitecture,2001,47(6):549— 554. [6]A'ITIYAG,HAMAMY.Taskallocationformaximizingreliabilityof distributedsystems:asimulatedannealingapproach[J].Journalof ParallelandDistributedComputing,2006,66(10):1259-1266. [7]YINPY,YusS,WANGPei—pei,eta1.Taskallocationformaximi— zingreliabilityofadistributedsystemusinghybridparticleswarmop— timization[J].JournalofSystemsandSoftware,2007,80(5): 724-735. [8]TINDELLK,BURNSA,WELLINGSA.Allocationhardreal—time task:anNP-hardproblemmadeeasy[J].RealTimeSystemsRe? searchGroup,1992,4(2):145?165. [9]明平顺,李晓霞.汽车可靠性理论[M].北京:机械工业出版社, 2003. [10]KENNEDYJ,EBERHARTRC.Particleswarmoptimization[c]// ProcofIEEEInternationalConferenceonNeuralNetworks.Pisca— taway:IEEEServiceCenter,1995:1942-1948.