（计算机应用技术专业论文）时间序列异常检测的研究与应用.pdf

河海大学硕士研究生论文时间序列异常检测的研究与应用 摘要 在数据挖掘过程中，常常存在与数据模型或数据一般规律不符合的数据对 象，这类与其它数据不一致的数据对象就称为异常数据，它们往往容易被人们所 忽略。然而，这些数据对象可能是具有特殊意义的，而且相对于那些普通的数据 而言，这类异常的数据往往包含着更多重要的信息和知识。因此，如何检测出这 些异常是很有意义的一项研究工作，具有一定的研究价值。 时间序列是一种常见的数据类型，由于时间序列数据有序性的特点，使得其 异常检测比普通数据集合更为复杂。本文主要研究时间序列中异常检测的方法， 并结合水文领域的知识和实验数据的特点，将方法应用到水位时间序列的异常检 测中。 本文的主要工作有以下几点： ( 1 ) 对数据集合中的异常检测方法进行研究，分析并总结了各类检测方法的 优缺点，并比较了各自适用的范围。 ( 2 ) 阐述了时间序列异常检测的相关概念，研究了时间序列中异常点的检测 方法。结合水位数据的特点，引入了平均变化量、平均变化率这两个统计量，并 在其基础上给出了水位时间序列中异常点的定义，提出了基于累积变化量检测水 位时间序列中异常点的方法。使用太湖流域五个测站的水位数据进行实验，并对 检测出的异常点进行了归类、分析和修正。 ( 3 ) 本文讨论了时间序列模式和异常模式的相关概念，研究了时间序列中异 常模式的检测方法，分类总结了目前已有方法的特点。给出了水位时间序列异常 子序列和异常模式的定义，提出了基于距离度量检测水位时间序列中异常模式的 方法。通过实验证明了方法的有效性，并对结果进行了详细分析。 关键词：数据挖掘，异常检测，时间序列，异常点，异常模式 河海大学硕士研究生论文时间序列异常检测的研究与应用 a b s t r a c t i nt h ep r o c e s so fd a t a m i n i n g ，t h e r ea l w a y se x i s td a t at h a td on o tc o n f o 咖t ot h e d a t am o d e la n dg e n e r a l1 1 l l e s n i sk j n do fd a t ai n c o n s i s t e n t sw i t h0 t h e r si sc a l l e d a b n o 珊a ld a t aw h i c hi sp m n et ob ei g n o r e db yp e o p l e h o w e v e r ，t h e s ea b n o 姗a ld a t a m a yh a v e s o m es p e c i a l m e a n i n g s t h e y s o m e t i m e sc o n t a i nm o r e i m p o n a j l t i n f o 册a t i o na n dk n o w l e d g ec o m p a r e dw i t h0 t h e fn o r i n a ld a t a s o ，t h e ya l w a y sh a v e m o r er e s e a r c hs i g n i f ! i c a n c e h o wt od e t e c tt h e mi sam e a n i n g f u lr e s e a r c hw o r k t i m e s e r i e si s ac o m m o nk i n d o fd a t a b e c a u s eo fi t sc h a f a c t e r i s t i c so f o r d e r l i n e s s ，t h ea n o m a l yd e t e c t i o ni sm o r ec o m p l e xt on o n l l a ld a t a s e t s i nt h i sp a p e r ， o u rr e s e a r c hm a i n l yf o c u s e so nm e t h o d so ft i m es e r i e sa b n o 珊a ld e t e c t i o n w ea p p l y t h e s em e t h o d st od e t e c ta b n o 瑚a ld a t ai nw a t e rl e v e lt i m es e r i e sc o m b i n e dw i t h h y d r o l o g i c a lk n o w l e d g ea n dc h a r a c t e r i s t i c so fo u re x p e r i m e n t e dd a t a t h ew o r ko ft h i sp a p e rm a i n l yi n c l u d e sf o u o w i n gp o i n t s ： ( 1 ) r e s e a r c hm e t h o d so fa n o m a l yd e t e c t i o ni nd a t a s e t s a n a l y s ea n ds u m m a r i z e t h ea ( 1 v a n t a g e sa n dd i s a d v a n t a g e so fv a “o u sm e t h o d s w ea l s oc o m p a r et h e i rs c o p e 硝 a p p l i c a t i o nr e s p e c t i v e l y ( 2 ) w 色e x p l a i nr e l a t e dc o n c e p t sa b o u tt i m e s e r i e s a n o m a l yd e t e c t i o na n d r e s e a r c hm e t h o d so fo u t l i e r sd e t e c t i o ni nt i m es e r i e s c o m b i n e dw i t hc h a r a c t e r i s t i c so f e x p e r i m e n t e dd a t aw ei n t r o d u c em e a nc h a n g ea n dm e a nr a t eo fc h a n g e ，a n d 百v e t h ed e f i n i t i o no fo u t l i e r si nw a t e rl e v e l t i m es e r i e sb a s e d0 nt h e s et w 0s t a t i s t i c s t h e n w ep u tf o r w a r dam e t h o db a s e do na c c u m u l a t i v ec h a n g et od e t e c to u t l i e r si nw a t e r l e v e l t i m es e r i e s w ee x p e r i m e n tw i t hf i v eh y d r o 伊a p h i cs t a t i o n so ft a i h u w ec l a s s i f y a i l da n a l y s ed e t e c t e do u t l i e r s ，t h e nc o r r e c tt h e m ( 3 ) t h i sp a p e r d i s c u s s e sr e l a t e dc o n c e p t sa b o u tt i m es e r i e sa b n o 姗a l s u b s e q u e n c ea n da b n o 瑚a lp a t t e m ，r e s e a r c h e se x i s t i n gm e t h o d so fa b n o 珊a lp a t t e m d e t e c t i o ni nt i m es e r i e s c l a s s i f i e sa n ds u m m a r i z e st h ef e a t u r co ft h e s em e t h o d s t h i s p a p e r 西v e st h ed e f i n i t i o no fw a t e rl e v e lt i m e s e r i e sa b n o 姗a ls u b s e q u e n c ea n d a b n o r m a lp a t t e m ，t h e np u t sf o r w a r dam e t h o db a s e do nd i s t a n c em e a s u r et od e t e c t a b n o 肌a lp a t t e m si nw a t e rl e v e lt i m es e r i e s w ep r o v et h ev a l i d i t yo ft h em e t h o db y e x p e r i m e n ta n da n a l y s et h er e s u l ti nd e t a i l k e y w o r d s ：d a t am i n i n g ，a n o m a l yd e t e c t i o n ，t i m es e r i e s ，o u t l i e r s ，a b n o 皿a lp a t t e m l i 学位论文独创性声明： 本人所呈交的学位论文是我个人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果。与我一 同工作的同事对本研究所做的任何贡献均已在论文中作了明确的说 明并表示了谢意。如不实，本人负全部责任。 论文作者( 签名) ：歪k 是w 。g 年6 月，阳 学位论文使用授权说明 河海大学、中国科学技术信息研究所、国家图书馆、中国学术期 刊( 光盘版) 电子杂志社有权保留本人所送交学位论文的复印件或电 子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文 档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允 许论文被查阅和借阅。论文全部或部分内容的公布( 包括刊登) 授权河 海大学研究生院办理。 论文作者( 签名) ：坠采9 年6 月r 影日 河海人学坝i 研究生论立时问序列异常榆测的研究j 府用 1 1研究背景 1 1 1 数据挖掘 第一章绪论 随着数据库技术的迅速发展以及数据库管理系统的广泛应用，人们积累的 数据越来越多。激增的数据背后隐藏着许多重要的信息，人们希望能够对其进 行更高层次的分析，以便更好地利用这些数据。目前的数据库系统可以高效地 实现数据的录入、查询、统计等助能，但无法发现数据中存在的关系和规则， 无法根据现有的数据预测未来的发展趋势。用数据库来存储数据，用机器学习 的方法来分析数据，挖掘大量数据背后的知识，这两哲的结合促成了数据挖掘 ( d a t am i n i n g ) 的产生。 定义1 1 ：数据挖掘 数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用 数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知 识的过程。 原始数据可以是结构化的，如关系型数据库中的数据；也可以是半结构化 的，如文本、图形、图像数据；甚至是分布在网络上的异构型数据。数据挖掘 的方法可以是数学的，也可以是非数学的：可以是演绎的，也可以是归纳的。 挖掘出来的信息可以被用于信息管理、决策支持、过程控制等，还可用于数据 自身的维护。 因此，数据挖掘汇聚了不同领域的研究者，是个多学科交叉研究领域， 它融合了数据库( d a t a b a s e ) 技术、人工智能( a r t m c i a li n t e l l i 黜c e ) 、机器学 习( m a c h i n el e a m i n g ) 、统计学( s t a t i s t i c s ) 、知识工稗( k n o w l e d g ee n 百n e 甜n g ) 、 面向对象方法( o b j e c t o d e n t e dm e t h o d ) 、信息检索( 1 n f o n n “i o nr e t r i e v a l ) 、高 性能计算( h i 曲p e 墒m a n c e c o m p u t i n g ) 以及数据i 叮视化( d a t a s u a l i z a t i o n ) 等最新技术的研究成果。经过十几年的研究，产生了许多新概念和方法。 数据挖掘的仟务是从数据中发现模式。数据挖掘任务一般可以分两类，描 述和预测。描述性挖掘任务刻画数据库中数据的般特性；预测性挖掘任务在 当前数据卜进行推断，以进行预测【2 1 。具体可以可分为：分类或预测模型发现、 数据总结、聚类、关联规则发现、序列模式发现、依赖关系或依赖模型发现、 异常和趋势发现等等。 河海大学硕士研究生论文时间序列异常检测的研究与应用 1 1 2 时间序列数据挖掘 时间序列是按照时间顺序取得的一系列观测值。对于时间序列的定义，有 很多种不同的表述形式，常见的有以下几种： 定义1 2 ：时间序列( 形式1 ) 时间序列( t i m es 嘶e s ) 是指一些在相同的时间间隔下获得的，并且和时 间变化顺序相关的序列值( 整数或实数) 的集合【卸。 定义1 3 ：时问序列( 形式2 ) 时间序列是按照时间顺序取得的一系列观测值口引。 定义1 4 ：时间序列( 形式3 ) 时间序列是由记录值和记录时间组成的元素的有序集合，记为 x = “= ( v l ， ) ，而= ( v 2 ，f 2 ) ，= ( l ，。) ) 。元素五= ( v j ，) 表示时间序列在f 。时 刻的记观测值为v ，记录时间f i 是严格增加的 2 9 1 。 从以这些上定义可以看出，时间序列数据作为一类特殊的数据类型，与其 它数据类型相比，时间序列数据有着自身的特点 3 0 ： ( 1 ) 有明显的时间先后。每个记录都必须有时间维，可以按时间进行排列。 如果按关联规则的表示方法，所得的规则应体现出时间要素，一般应是先发生 的推出后发生的，体现出时间延迟的概念。 ( 2 ) 多是数值型。属性记录的属性类型可以分为三种：一是布尔型：二是类 别型；三是数值型，如降雨量、气温值等。 ( 3 ) 反映出序列特征。不论哪种类型，应该是在某一时间段内连续的记录集， 有一定的连贯性，有规律性可寻。 很多数据是以时间序列的形式出现的，如股票市场的每日波动，科学实验， 一个工厂装船货物数量的月度序列，公路事故数量的周度序列，某化工生产过 程按小时观测的产量，某水文测站测量得出的逐日水位数据等等。 时间序列数据可分为： ( 1 ) 科学数据。例如，水文数据，气象数据，地质数据，环境数据、天体物 理学数据，医学数据及网络流量数据等。 ( 2 ) 经济、市场及生产数据。例如，股票数据，销售数据，用电负荷数据等。 ( 3 ) 语音数据，包括声音、录音等数据。 可以看出，时问序列是一类重要的复杂数据对象，社会、科学、经济、技 术等领域中广泛存在着大量的时间序列数据有待进一步的分析和处理。在计算 ? r i 海人学硕1 1 研究生论文时问序列异常榆测的研究与应用 机技术快速发展和应用普及的今天，这样_ 人量的时间序列数据被存储在计算机 上，使得我们捕j 有海量的时问序列数据。 时问序列数据在数据库中占相当大的比重。它广泛存在于各种大型的商业、 医学、工程和社会科学等数据库中，形成规模庞大的时问序列数据库。这些海 量的时间序列数据库真实地记录了应用系统在各个时刻的所有重要信息，如能 找到某种高效率的数据处理方法，从时序数据中抽取时序内部的规律用于时序 的数值、周期、趋势分析和预测等，必将大大提高这些时问序列数据库的实用 价值。 另一方面，由于自然界里的事物之间是相互联系和相互影响的，事物的变 化和发展有其内在的必然性，因而己经发生的历史时问序列与将来发生的时间 序列之间必然有其内在的联系。因此，我们通过分析和研究反映事物过去的运 动、变化和发展的历史时间序列数据，在很大程度上是可以发现事物变化发展 的内在规律的。这就能为决策者制定决策提供重要的参考信息或知识。 时间序列数据挖掘( t i m es 耐e sd a t am i n i 雌) 就是基于这一需求所提出来 的。 定义1 5 ：时间序列数据挖掘 时间序列数据挖掘是对一个或多个时问序列的数据挖掘，是从大量的时问 序列数据中提取人们事先不知道的、与时间属性相关的有用信息和知识并用于 指导人们的社会、经济、军事和生活等活动【2 1 。 人们不断地研究和探索新技术、新方法，寻求有效的技术和方法来揭示这 些时间序列数据集中所隐藏的知识或信息，把历史时序数据转化为对人类有用 的知识和信息，这就使得时问序列数据挖掘的研究得剑了空前的发展，并己发 展成为数据挖掘的一个重要的研究方向。时问序列数据挖掘对人类社会、科技 和经济的发展具有重大意义，并正逐渐成为数据挖掘的研究热点之一。 1 1 - 3 时间序列异常检测 在数据挖掘过程中，常常存在与数据模型或数据一般规律不符合的数据对 象，这类与其它数据不一致的数据对象就称为异常数据，它们往往容易被人们 所忽略。然而，这些数据对象可能是具有特殊意义的，而且相对于那些普通的 数据而言，这类异常的数据往往提供了更多的有用信息，它们往往更具有研究 价值。 异常数据产生的原因很多，主要的原因有： ( 1 ) 在数据的阅读、记录、计算、误操作时产生的错误，例如：一个站点测 量出的水位数据为负值，就可能是由于输入错误，或者由于程序在处理遗漏数 河海犬学硕士研究生论文时间序列异常检测的研究与应用 据所设置的缺省值所造成的。 ( 2 1 异常数据也可能是从不同的数据源合并数据时由于各自的量度单位、时 间不一致而引起的错误。 ( 3 ) 另外，异常数据还可能是由于数据内在特性而造成的，如：一个公司的 首席执行官工资在与其他公司雇员工资相比时，就可能构成一个异常数据；又 如，在河流汛期测得的流量数据和该条河流其他时段测得数据相比，就可以看 作是异常数据。 因此，可以看到，不能简单的把异常数据看作是“错误的数据”，并进行简 单的处理。对于数据中存在的错误数据，需要开发有效的检测算法，为数据分 析提供清洁可靠的数据；但也可以看到，某些异常数据可能包含着某种重要的 知识，分析它们能获得到有实际应用意义的知识。 任何一个数据挖掘任务都不会是一个简单的工作，而是有着复杂的理论基 础和应用背景。异常检测( a 1 1 0 m a l v d e t e c t i o n ) 也是数据挖掘的一个重要分支， 它被广泛的应用在很多领域。比如：检测信用卡欺诈行为、监控电子商务中的 犯罪行为、检测网络入侵等等。在某些情况下，异常数据比其它数据甚至更为 有用：在网络入侵检测领域，网络攻击的数量在整个网络数据流中只占很小的 一部分；在医疗数据库中，对胸部的x 光摄影片图像进行是否有乳癌的分类 时，异常的象素( 有癌) 往往仅是整个图像的一小部分。尽管小事件很少出现 ( 不频繁) ，但在上面的例子中，他们的重要性与其它事件相比更大，从而使他 们的检测显得异常重要。 从上面的分析中可以看出，异常检测与其它许多数据挖掘研究的对象不同， 它不是研究数据集中的绝大多数对象，而是关注那些数据集合中小部分的对象。 这些小部分的异常数据( 对象) 可能包含着某种重要的信息和知识。因此，异 常数据检测和分析是一个较为特殊却很有意义的数据挖掘任务。 时间序列是一种常见而又重要的数据类型，在海量的时间序列中发现其背 后隐藏的知识对于我们分析时间序列变化规律，科学地做出决策具有重要的意 义。在数据挖掘概念提出不久，就有不少研究者把数据挖掘的思想运用到时间 序列分析中来。随着异常检测相关技术的研究与发展，其应用领域也不仅仅局 限于普通的无序数据集合，很多研究者( 尤其是国外) 的目光更多关注到时间 序列中的异常检测方法。 1 2研究现状 早在上世纪8 0 年代初，国外就出现了专门针对异常检测的研究。随着异常 检测受到越来越多的关注，使用的检测方法也越来越多： 4 河海大学硕士研究生论文时间序列异常检测的研究与应用 ( 1 1 统计学方法【3 l 基于统计学的方法是最早被提出来的。统计中常用的方法是先对给定的数 据集合假设一个分布或概率模型( 例如一个正态分布) ，然后根据该模型，采用 不一致检测确定异常。 该方法存在问题：一是绝大多数一致性检验是针对单个属性的，而许多数 据挖掘问题要求在多维空间中发现异常点；二是统计学方法要求知道关于数据 集合参数的知识，例如数据分布，但许多情况下，数据分布是未知的。 ( 2 1 基于距离的方法【4 ，2 2 j 随后提出了基于距离的方法来检测异常点。如果数据集合中至少有p 部分 对象与对象。的距离大于d 则对象。是一个带参数口、d 的基于距离的异常点， 记为d b ( p ，d ) 。这个定义统一了异常点的概念，所以被称作一致异常点。 直观而言，如果不依赖于统计检验，可将基于距离的异常点看作是那些没 有足够多邻居的对象，此处邻居是基于距给定对象之间的距离定义的。目前， 该领域研究人员提供了若干高效的基于距离的异常点挖掘算法，比较有代表性 的是：基于索引的算法、嵌套循环算法和基于单元的算法，这些算法的主要特 点是以对象间的距离作为相似性度量。 该方法的优点是：概括了基于统计模型的异常点的含义，并且对相对高维 数据集有较好的挖掘效果；存在问题：一是距离函数和参数的选择问题；二是 仅能发现全局异常点，而丢失了局部异常点。 ( 3 ) 基于密度的方法【5 ，2 6 】 基于密度的异常点检测方法可以发现局部的异常点基本思想来自于密度聚 类方法，该方法在判断一个对象。是否为异常点时，首先计算其k 距离，从而 可以检测出哪些对象是。的邻居，然后查找对象。的k 距离领域，计算出。相 对于其领域内所有对象的可达距离，以得出对象。的局部可达密度u ( l 0 c a l r e a c h a b i l i t vd e l l s i t v ) 。最后，该方法计算出的一个重要的变量：局部异常点因 子l o f ( l o c a lo u n i c rf a c t o r ) 。可以证明，在同一个聚类中的任何对象o ，其 l o f 近似等于1 ，只要一个对象的l o f 远大于1 ，它可能就是一个异常点。 基于密度的方法即仅能发现全局异常点( g l o b a lo 眦1 i e r s ) ，也能发现局部 异常点( l o c a lo u t l i e r s ) 【5 】，解决了上述基于距离的方法中存在的第二点问题。 但是该方法的计算步骤比较繁琐，复杂度较高，不适台直接用于数据较多的情 况。 ( 4 ) 基于偏离的方法 6 l 基于偏离模型的异常点检测不采用统计检验或对象问的距离度量值来确定 异常对象，而是通过检查一组对象的主要特征来确定异常点，如果一个对象的 特征与给定的描述过分“偏离”，则该对象被认为是异常点。基于偏离模型的异 河海大学硕士研究生论文 时问序列异常检测的研究与应用 常点挖掘方法主要有序列异常技术和o l a p 数据立方体技术两种。 然而，上述这些异常检测方法主要研究的对象并不是时间序列。对于时间 序列，它的一个重要特点是具有时间属性，序列值之间存在严格的顺序，是一 种有序的数据。上述的异常检测算法都是针对无序数据集的，并不适用于时间 序列数据。 如1 1 2 小节所述，时间序列是种常见而又重要的数据类型，在海量的时 间序列中发现其背后隐藏的知识对于我们分析时间序列变化规律，科学地做出 决策具有重要的意义。在数据挖掘概念提出不久，就有不少研究者把数据挖掘 的思想运用到时间序列分析中来。随着异常检测相关技术的研究与发展，其应 用领域也不仅仅局限于普通的无序数据集合，很多研究者( 尤其是国外) 的目 光更多关注到时间序列中的异常检测方法。 按照异常的表现形式不同，时间序列的异常可以分为以下三种【7 】： ( 1 ) 序列异常：序列异常是指在时间序列数据集中与其它时间序列显著不同 的、来源于不同产生机制的时间序列。 ( 2 1 点异常：点异常是指在一条时间序列上与其它序列点存在显著差异的、 具有异常特征的序列点。 ( 3 1 模式异常：模式异常是在一条时间序列上与其它模式存在显著差异的、 具有异常行为的模式。 其中，时间序列的异常主要研究的是点异常和模式异常。 时间序列由于其动态数据类型的性质且数据量大决定了针对时间序列的异 常检测比较复杂。目前国内外在这方面的研究还处于刚刚起步阶段，研究工作 显得不成熟。到目前为止，时间序列的异常还没有个公认的定义，许多研究 者都提出了不同的时间序列异常定义，而且，研究者往往使用不同的术语来表 述“异常”这一概念，其中与异常点( o u t l i e r s ) 相关的术语包括：偏离点( d e v i a n t ) 、 变化点( c h a 醒ep o i n t ) 等；与异常模式( a b n o 珊a lp a 仕咖) 相关的术语包括： 新颖模式( n o v e l t yp a t t 锄) 、奇异模式( s u r p r i s ep a t t e r n ) 、不一致事件( d i s c r o d ) 、 新颖事件( n o v de v e i l t ) 、异常的行为( a b e h tb c h a v i o r ) 等【8 1 。 这些术语的侧重点略有不同，但是都是在表达“异常的，与众不同”的意 思，为了保持一致性，本文在后续描述中在不影响语义的前提下，一般统一使 用“异常点”和“异常模式”这两词来描述。 以下对现有的研究成果进行简要的叙述，本文4 3 小节将进行详细的阐述。 目前针对时间序列中异常检测的方法主要有以下几大类： ( 1 ) 生物学方法【9 】 该方法是从生物的免疫系统的机制中获得灵感的，用免疫系统中自我( s d f ) 6 徊j 海大学硕士研究生论文时间序列异常检测的研究与应用 和异己( o t l l c r ) 的概念来分别代表正常的数据模式和异常模式，并借鉴负选择 机制来检测时间序列中的异常模式。方法的主要缺陷是，当j 下常的数据变得多 种多样，那么可能产生的正常模式的数目也同样增加，这会导致产生不出任何 用于负选择过程的异己，最终会使得选择过程失败，检测不出任何异常模式。 ( 2 ) 基于频率的方法【8 】 基于频率的方法使用马尔可夫模型( m a r k o v m o d e l ) 和后缀树检测新颖( 异 常) 模式。该方法的主要思想是：采用后缀树来编码时间序列中所有出现的模 式，用马尔科夫模型来预测没有被观测到的模式期望发生的概率，然后根据用 户给定的阈值来判断模式的奇异性，即检测出异常的模式。方法优点是特别高 效，可以在线性的时间和空间内检测新颖模式，存在的问题是，由于采用了时 间序列离散化技术，有意义的数据可能在转换的过程中丢失。 ( 3 ) 机器学习的方法【1 0 _ 1 3 】 目前相关研究方法主要包括两大类：人工神经网纠1 0 1 和支持向量机 1 l - 1 2 1 。 对于异常检测，人工神经网络它能够很好的处理小规模的问题，但是不能 很好的扩展到处理大规模的问题。 支持向量机s v m ( s u p p o r tv e 吐0 rm a c h i n e ) 于神经网络，计算上效率高很 多，并且有同样的处理能力。但是s v m 理论上较为复杂，且作为一种机器学 习方法中，建立模型的过程也比较复杂，实现上有一定难度。 另外，还有一种基于规则的机器学习方、法【1 3 l ，该方法是首先将原始的数据 聚类或者分段，然后用规则来描述产生的分段。根据规则，构造一个仅接受正 常模式的状态机，任何不被接受的序列，即任何偏离规则的序列被认为是一个 新颖模式，也就是异常模式。该方法产生的规则是人类可读的，这有助于清晰 的解释规则和对模型进行调整。 ( 4 ) 基于特征空间的方法【1 4 】 首先对时间序列进行分段，从分段中抽取特征，然后在特征空间中应用无 序数据集合中的异常点检测方法来发现异常。该方法将时问序列中的异常检测 归结为对异常点的检测，这样就可以利用现有的无序数据集合中那些较为成熟 的异常点检测方法来间接的检测出时间序列中的异常。 然而，分段结果的好坏直接影响到检测结果的优劣，如何选择合适的分段 方法是较为困难的；并且，对每个分段抽取出的一组特征值是否能够代表这一 段时间序列也是需要探讨的问题。 f 5 1 基于s a x 的方法 基于s a x ( s y m b o la g 掣e g a t ea p p r o x i m a t i o n ) 的方法【1 5 】。该方法最早由 e a m o n n k e 0 曲等人提出。他们引入了一个新的问题：查找时削序列中的不一致 事件( d i s c r o d ) 。不致事件是一个时间序列中那些和其它子序列差别最大的 7 河海大学硕士研究生论文时间序列异常检测的研究与应用 子序列，即时间序列中最不寻常( m o s tu n u s u a l ) 的子序列，这和相似性查找 要解决的问题正好相反。 ( 6 ) 其它一些方法 1 5 - 1 7 l 其它检测时间序列异常的方法还有：基于小波的方法【1 6 1 ，能够改进模式的 查询性能，缺点是不能够检测出正常模式之间的短期的新颖( 异常) 模式；基 于a r ( 自回归) 模型f 1 7 的方法，以及其改进的a r m a ( 自回归滑动平均) 模 型，这种模型表示法的一个缺点是事先要假定某个模型，而实际上，用户很难 确定所要分析的时间序列服从什么模型，即使能够确定，模型参数的值也难选 择。 根据上述分析可见，时问序列的异常检测虽然方法很多，但是大多数方法 仍然处于探索阶段，还有很多不成熟的地方，很多方法适应性不强，且普遍存 在明显的缺陷，如错误检测率较高，即将非异常情况检测成为异常情况 i 引。因 此，对时间序列异常检测的方法不够成熟，还有很多的可研究的空间，并且在 研究上存在一定的难度。 1 3研究工作 本文的主要研究工作有： ( 1 ) 相关研究工作包括：对无序数据集合中的异常检测方法进行了研究，分 析并总结了各类检测方法的优缺点，比较了方法各自适用的范围，该工作为后 续研究奠定了理论基础：对时间序列中异常检测方法进行研究，对现有的方法 进行分类和总结，并分析其各自存在的问题。 ( 2 ) 理论基础部分的研究包括：总结了目前现有研究工作中对异常点的定义 和相关概念：研究了时间序列、水文时间序列以及时间序列模式和异常模式的 定义和相关概念。 ( 3 ) 在应用和实验部分，本文根据水文数据的特点，引入了平均变化量、平 均变化率这两个统计量，在此基础上给出了水位时间序列中异常点的定义；提 出了基于累积变化量检测水位时问序列中异常点的方法，对主要的算法部分进 行分析，并结合水文领域知识，对检测出的异常点的可能成因进行归类、分析 和修正；结合水文数据的特点，给出了水位时问序列异常子序列和异常模式的 定义，提出了基于距离度量检测水位时间序列中异常模式的方法，对方法的主 要步骤进行了描述，分析了主要部分的算法，详细比较了各种距离度量方法， 最后对实验结果进行了解释和分析。 河海人学硕士研究生论立 时问序列异常检测的研究与应用 1 4论文安排 第1 章 第2 章 第3 章 第4 章 第5 章 介绍本论文的研究背景、研究现状及本文研究的工作和意义。 本章主要研究无序数据集合中异常点的检测方法。首先给出目前较为 权威的几个异常点的定义，从本质上和直观上理解并分析异常点的诸 多特点，然后重点对这些普通无序数据集合中异常点的检测方法进行 研究和总结，主要分成统计学方法、基于距离的方法、基于密度的方 法等几个大类进行研究。 本章主要工作是时间序列中异常点的检测方法的研究及其应用。首先 介绍相关概念和研究工作，然后结合水位数据的特点给出了水位时间 序列中异常点的定义，并提出基于累积变化量检测水位时间序列中异 常点的方法，重点介绍核心算法的主要步骤，并对算法进行分析。通 过实验对该方法的有效性进行验证，对检测出的异常点的可能成因进 行归类和分析，并对异常点进行修正。 本章主要工作是时间序列中异常模式检测方法的研究及其应用。首先 介绍与时嵋j 序列模式和异常模式相关的概念，分类总结了目前已有的 各种时间序列异常模式的检测方法。然后给出水位时间序列中异常子 序列和异常模式的定义，在此基础上提出基于距离度量的方法检测水 位时间序列中的异常模式。分析该方法的主要步骤、算法部分的复杂 度，重点比较了各种距离度量方法，最后，对实验结果进行分析。 论文的总结和对未来进一步工作的展望。 9 河海大学硕士研究生论文时间序列异常检测的研究与应用 2 1 引言 第二章异常点检测 普通数据集合的数据表现形式是一个有限的点集，这种数据的特性是：集 合中的对象之间不存在任何顺序关系。相对于时间序列在中的数据对象而言， 这类数据集合中的数据对象之间不存在时间上的先后顺序关系。这类数据集合 是现实中最为常见的一种数据类型，如：一个公司中所有员工的工资数额所组 成的数据集合，又如：一个班级中所有学生信息( 年龄、身高等) 组成的数据 集合。前者只有一个属性，称为一维数据集合；后者含有多个属性，称为多维 数据集合。 可以看出，这类数据集合中的一个对象就是一个一维的数据点或者一个多 维的数据点，因此，普通数据集合中异常检测研究的问题就是指针对异常点的 检测，包括一维和多维的异常点检测问题。 在过去的一个多世纪中，异常点问题的研究经历了几次盛衰交替。在9 0 年 代的数据挖掘研究中，异常点通常被作为聚类挖掘的副产品，并且，许多聚类 挖掘算法把异常点作为干扰数据剔除1 9 。o 】。因此，在数据挖掘研究领域，异常 点挖掘当初并不是研究主流，但随着人们对其重要性认识的加深，异常点挖掘 日益受到重视。目前，它再次成为信息科学中一个活跃的分支，在数据库和数 据挖掘研究领域受到广泛关注。 与此同时，异常点的研究领域和应用范围也逐渐扩大。从最初研究针对普 通的数据集合中低维数据集合中异常点检测，到后来针对高维数据集合中异常 点的检测，一直应用到各种数据集合类型，如面向时间序列中的异常( 异常点、 异常模式) 检测。 本章主要研究并总结了普通数据集合中的异常检测的方法，这些方法为本 文后续章节中关注的时间序列异常检测方法奠定了理论基础。 2 。2 异常点的定义和概念 异常点有多种别名，如噪声、偏离点、例外点等，除上述外，国内译名还 有孤立点、离群点等。对于数据集合中的异常点( 对象) ，直观上，它们一般孤 立于其它对象存在，因此研究者常使用“孤立点”一词来形象的描述异常点。 但本文为了保持描述的一致性，一般都使用异常点来统一进行说明。 如前所述，异常检测是数据挖掘的一个重要分支。异常点挖掘可以被形式 化的描斟2 】：给定一个含有n 个数据点或对象的集合，预期的异常点数目k ， 发现集合中与其余数据相比显著相异的、异常的或不一致的前k 个对象。所以， 1 0 河海大学硕士研究生论文 时间序列异常检测的研究与应用 异常点挖掘问题可被看作两个子问题： ( 1 ) 在给定的数据集合中定义什么样的数据被认为是不一致的； ( 2 ) 找到一个有效的方法来挖掘这样的异常点。 异常点挖掘的第一个子问题，即是要解决异常点的定义问题。目前，异常 点定义有多种，最具代表性和被广泛接受的是h 抓憾n s 早在1 9 8 0 年给出的异常 点( o u n i c r ) 的本质性定义【4 】： 定义2 1 ：异常点本质上的定义 异常是在数据集中与众不同的数据，使人怀疑这些数据并非随机偏差，而 是产生于完全不同的机制。 另外具有代表性的还有vb 锄c t 等人在1 9 9 4 年在统计学领域给出的异常 点直观上的定义 2 1 】： 定义2 2 ：异常点直观上的定义 一个异常点( o u t l i e r ) 是这样的数据点，基于某种度量而言，该数据点与 数据集中的其他数据有着显著的不同。 除定义2 1 和2 2 以外，许多研究者根据特定的研究背景，给出了不同的异 常点的定义、聚类算法对异常的定义：异常是聚类嵌于其中的背景噪声；异常 探测算法对异常的定义：异常是既不属于聚类也不属于背景噪声的点，它们的 行为与正常的行为有很大的不同。尽管它们不尽相同，但都反映了异常点的特 点： ( 1 ) 首先，异常点看起来是令人惊讶的，它是异常点的关键特征之一； ( 2 ) 其次，异常点是一个相对的定义，如果初始分布模型的假设不同，会产 生不同的结论； ( 3 ) 最后，异常点有较强主观性，几乎所有研究者进行异常点挖掘研究时都 定义特有的挖掘背景。 目前，研究者们根据对异常存在的不同假设，开发了很多异常检测算法， 以解决异常点挖掘的第二个子问题：如何找到一个有效的方法来挖掘这样的异 常点。在近十几年的研究发展中，各种新颖的异常点检测方法可谓层出不穷， 但大体上都是基于传统经典的几种检测方法，主要有：基于统计的算法、基于 偏离的算法、基于距离的算法、基于密度的算法，以及面向高维数据的算法等。 本章以下几节将对这几类经典的异常点检测方法做详细的介绍和总结。 河海大学硬士研究生论文时间序列异常检测的研究与应用 2 3 异常检测方法研究 2 3 1 统计学的检测方法 基于统计学的方法是最早被提出用来检测数据集合中异常点的方法。基于 统计的异常检测方法假设所给定的数据集存在一个分布或概率模型( 如一个正 态分布) ；然后根据相应模型并通过不一致性测试来发现异常数据。应用这种测 试需要了解数据集参数的有关知识( 如数据分布情况) 、分布参数知识( 如均值 和方差) ，以及所预期的异常数据个数川。 假设给定的数据集服从一个随机分布( 如正态分布) ，用不一致性检验识别 孤立点。在大多数情况下，不能知道数据的具体分布，而且现实数据也往往不 符合任何一种理想状态的数学分布。另外即使在低维( 一维或二维) 时的数据 分布已知，在高维情况下，估计数据点的分布也是极其困难的。 最简单的一维样本孤立点检测方法是应用统计学。假定值的分布已知，必 须找出基本的统计参数，如均值和方差。在这些值和孤立点期望( 预测) 数目 的基础上，建立方差函数阈值是可行的。所有阈值之外的样本都是可能的孤立 点。这种简单方法的主要问题在于对数据分布的预先假设。 例如，所给的数据集是某个水文测站在同一时段内，通过多次测量，得到 的一组水位数据： 3 1 ，3 1 ，3 o ，3 1 ，2 9 ，2 5 ，3 o ，3 o ，3 1 。 那么，相应的统计参数是：均值= 2 9 8 ；标准差= o 1 9 。如果选择数据分 布的阈值为：阈值= 均值2 标准差。故在 2 6 0 ，3 3 6 】区间以外的数据 都是潜在的孤立点，所以值为2 5 的数据就是一个例外，这可能是由于测量误 差或者数据录入错误导致。 基于统计的孤立点发现方法是当已知数据集的概率分布及参数( 如正态分 布，均值、标准差) ，用不一致性检验确定孤立点及其个数。该方法存在两个关 键问题： n 1 绝大多数一致性检验是针对单个属性的，而许多数据挖掘问题要求在多 维空间中发现异常点。对于大多数的应用来泌，例如图像和地理数据，其数据 集的维数一般都是高维的。 ( 2 ) 统计学方法要求知道关于数据集合参数的知识，例如数据分布，但许多 情况下，数据分布是未知的，尤其当没有特定检验时，统计学方法不能保证所 有的异常点都被发现，或者观察到的分布不能恰当地被标准分布来建模描述。 即使存在一个标准分布，分布拟合的过程耗时太长 2 2 】。 1 2 河海大学硕上研究生论文时问序列异常检测的研究与应用 因此，基于统计的孤立点检测这种方法适用于低维数值型数据，不适用于 高维数据、周期数据和分类数据的挖掘。因为必须事先知道数据的分布特征， 这就限制了它的应用范围。实际生活中，以上缺陷都大大限制了基于统计的方 法的应用，使得它主要局限于科研计算，而且算法的可移植性较差。 另外，在工业生产中经常需要检测并剔除测量数据中异常数据，常用到的 标准是3 盯。准则，即认为偏差超过3 盯。( 3 倍标准差) 的测量值为异常数据， 应当剔除。其它标准还有肖维准则、格拉布斯准则等，这些标准都是基于统计 学的。 2 3 2 基于距离的检测方法 基于距离的异常点的概念最早由e m k n o r r 和r 1n g 提出【4 ，2 2 1 ，s r a i i l a s w a m y 等人对该方法进行了改进【2 3 】。在这些方法里，一般根据数据对象的 最近邻居来判断其是否为异常点。 基于距离的异常点检测方法适合于观测值的分布不符合任何标准分布的情 况，并且适合于多维的数据集，因此，其克服了基于统计学的异常点检测方法 的两大缺点。以下是e m k n o r r 和r t n 2 针对基于距离的异常点提出的定义 捌： 定义2 3 ：基于距离的异常点定义 如果数据集合s 中，对象。是一个异常点，仅当s 中至少有p 部分对象与 。的距离大于d ，换句话晚，如果。在d 范围内有不多于m 个邻居，则对象。 是一个带参数p 、d 的基于距离的异常点，记为d b ( p ，d ) 。 在定义2 3 中，m = n 4 ( 1 一p ) ，n 为数据集中对象的个数。距离度量函数一 般使用欧氏距离曼哈顿距离。 基于距离的异常点定义d b ( p ，d ) 可以概括基于统计学中的异常点定义。如， 统计学中的异常点常常这样定义：设存在一个正态分布数据集，如果数据集中 存在与均值之间的距离大于或等于3 倍偏差的数据对象，则该对象被认为是异 常点。可以证明【2 2 】，以上定义的异常点可以由以下这个基于距离的异常点定义 所概括：d b ( 0 9 9 8 8 ，o 1 3 盯) 。 其它一些基于距离的异常点定义还有： ( 1 )