（计算机应用技术专业论文）概率流上复杂事件处理的研究.pdf

q 1 i r 、 。警l d p 二l 啦 1 愀y 18 4 1 4 0 6 at h e s i sf o rt h ed e g r e eo fm a s t e ri nc o m p u t e r a p p l i c a t i o n1 e c h n o i o g y r e s e a r c ho nc o m p l e xe v e n t p r o c e s s i n g i n p r o b a b i l i s t i cs t r e a m b yx uc h u a n f e i s u p e r v i s o r ：a s s o c i a t ep r o f e s s o rl ms h u l ( u a n n o r t h e a s t e r nu n i v e r s i 够 j u n e2 0 0 9 i 独创性l 声明 本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得 的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过 的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工 作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示 谢意。 学位论文作者签名： 彳他妙 日 期：加9 ；汐 l y 7l 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 作者和导师同意网上交流的时间为作者获得学位后： 半年口 一年 一年半口两年口 学位论文作者签名：稳侄伊 导师签名： 评纠耋 签字日期：厶嗍f 罗p 签字日期： 2 。7 奇多j ；| 。 j i 一 一i i 一 ， 了 - 一 ，i - 一 东北大学硕士学位论文摘要 概率流上复杂事件处理的研究 摘要 随着无线射频识别( r a d i of r e q u e n ti d e m i f i c a t i o n ，r f i d ) 和传感器等电子数据采集 设备( e l e c t r o l l i cd a t ag a t h e 血ge q u i p m e n t ，e d g e ) 的广泛应用，产生了空前海量的事 件类型数据，对这些事件数据进行复杂事件处理成为了非常重要的研究方向。复杂事件 处理广泛地应用于商业检测与预测、供应链管理、气候环境监测与预报和医疗监护等很 多领域。然而，当前的复杂事件处理方法大都是面向确定事件数据的，对于不确定事件 数据形成的概率流却无能为力，并且这些方法都缺乏对复杂事件发生前的预知能力。 针对这些问题，本文提出了一套概率流上复杂事件处理方案，它包括通过启发式搜 索和过滤实现的概率流上复杂事件检测算法h s f c e d ( h e 嘶s t i cs e a r c ha 1 1 df i l t e r c o m p l e xe v e n td e t e c t i o n ) 以及基于语义向量聚类和s v r 建模的概率流上的事件预测算 法s v c s v r e p( s e m 剐1 t i cv e c t o rc l u s t e r i n g -s u p p o r t 、厂e c t o rr e g r e s s i o nf o re v e n t p r e d i c t i o n ) 。本文的贡献点主要体现在： 首先，针对不确定事件数据形成的概率流，建立一种概率流模型，该模型不仅能表 达e d g e 设备检测出的不确定事件，而且可以通过贝叶斯网络表达和推理出不确定事件 的概率分布。在此过程中，提出了c p t r e e ( c o n d i t i o n a lp r o b a b i l i s t i ct r e e ) 结构来存储 贝叶斯网络中的条件概率，c p t r e e 相比于传统的条件概率表不但节省了存储的空间， 而且减少了查询的时间。 其次，提出了一种新的概率流上复杂事件检测算法h s f c e d ，该算法基于一种链 式队列结构启发式地搜索出满足查询请求的复杂事件，为了提高检测效率，放大概率阈 值对复杂事件进行无损过滤，并通过适当地设定允许偏差实现复杂事件的有损过滤，在 提高效率眇同时，保证查询结果的查全率。 t ， 再次，设计了一种语义向量结构，它表示大小为一个基本窗口的概率流片段的语义， 通过语义向量不但可以表达流片段的语义，而且把结构不同的流片段转化为相同结构的 语义向量，有利于建立预测模型。 最后，提出了一种全新的概率流上基于语义向量聚类的事件预测算法s v c s v r e p ， 该算法通过对语义向量的聚类和s v r 建模，可以预测出目标复杂事件在未来的一段时 间之内发生的概率。 一i i i 东北大学硕士学位论文摘要 此外，本文的复杂事件处理方案可以根据不同的需求设置不同的参数，从而返回不 同的结果。通过实验表明，此套复杂事件处理方案在概率流上能高效地检测出复杂事件， 并且能在保证较高的准确性的前提下，预测出目标复杂事件发生的概率。 关键词：概率流；复杂事件处理；启发式搜索；过滤；语义向量；s v r 建模 东北大学硕士学位论文a b s t r a c t r e s e a r c ho nc o m p l e xe v e n t p r o c e s s i n gi n p r o ba b i l i s t i cs t r e am a b s t r a c t w i t t lw i d ea p p l i c a t i o no fe d g e ( e l e c t r o i l i cd a t ag a t h e r i n ge q u i p m e n t ) s u c ha sr f i d ( r a d i of r e q u e n ti d e m i f i c a t i o n ) a n ds e n s o r ，m a s s i v ee v e n t - t y p ec i a t aa r eg e n e r a t e di 1 1o u r w o r l d t h e r e f o r e ，c o m p l e xe v e n tp r o c e s s i n gb e c o m e sa ne x t r e m e l yi m p o i r t a n tr e s e a r c hf i e l d f o rm e s ee v e n t t y p ei i a t a n o 、a d a y sc o m p l e xe v e m p r o c e s s i n gi sw i d e l ya p p l i c a b l et om a n y f i e l d s ，s u c ha sb u s i n e s sa c t i v i t ) rd e t e c t i n ga n dp r e d i c t i n g ，s u p p l yc h a i nm a n a g e m e m ，c l i m a t i c e n v i r o m n e mm o n i t o r i n g ，m e d i c a lc a r e ，a 1 1 ds oo n h o 、e v e r ，m o s to fc u r r e mc o m p l e xe v e m p r o c e s s i n ga l g o r i t h m sa r eo r i e n t e dc e r r t a i nd a t ai n s t e a do fu n c e r t a i ni i a t a 龇l dl a c k 也ea b i l i t yo f p r e d i c t i o nb e f o r ee v e n t so c c u l a i m e da tt 1 1 ea b o v ep r o b l e m s ，t 1 1 i s p a p e rp r o p o s e s as c h e m eo fc o m p l e xe v e n t p r o c e s s i n gi np r o b l b i l i s t i cs t r e 锄，w m c hi n c l u d e sc o m p l e xe v e n td e t e c t i o na l g o r i t h m h s f c e d ( h e u r i s t i cs e a r c ha n df i l t e r c o m p l e xe v e n td e t e c t i o n ) a c h i e v e db yh e u d s t i c s e a r c ha n df i l t e r ，a n de v e n tp r e d i c t i o na l g o r i s v c s v r 正p ( s e m a n t i cv 色c t o rc l u s t e r i n g s u p p o r tv e c t o rr e g r e s s i o nf o re v e n tp r e d i c t i o n ) a c l l i e v e db ys e m a n t i cv e c t o rc l u s t e r i n ga 1 1 d s v r m o d e l i n g c o n t r i b u t i o n so ft b j sp a p e rm a i l l l yr e s i d ei n ： f i r s t ，f o rp r o b a b i l i s t i cs t r e 锄g e n e r a t e db yu n c e n a i l le v e n t s ，a 玉【i n do fp r o b a b i l i s t i c s 订e 锄m o d e li s c o n s t r u c t e d ， i 1 1 c l u d i n ge v e n tm o d e l a n db a y e s i a i ln e 觚o r kt oe x p r e s s u n c e n a i ne v e m sd e t e c t e db ye d g ea n di n f e rt h ep r o b a b i l i 够d i s t r i b u t i o no ft 1 1 e m i nt l l i s p r o c e s s ，c o n d i t i o n a lp r o b a b i l i t ) ，t r e e ( c p t r e e ) s t m c n 】r ew m c hi su s e dt os t o r ec o n d i t i o n a l p r o b a b i l i t i e so fb a y e s i a nn e t 、o r ki sp r o p o s e d ，s a v i n gs t o r a g es p a c ea n dq u e r ) rt i m ec o m p a r e d 晰mt r a d i t i o n a lc o n d i t i o n a lp r o b a b i l i t ) rt a b l e s e c o n d ，an e wc o m p l e xe v e n td e t e c t i o na l g o r i t h mh s f c e di np r o b a b i l i s t i cs t r e 锄i s p r o p o s e d i 1 1t h i s p 印e r t 1 1 i sa l g o r i t l u l l c a l ld e t e c t c o n l p l e xe v e n t ss a t i s 匆i n gq u e 巧 r e q u i r e m e n t s 丘o mp r o b a b i l i s t i cs t r e a m 、v i t hah e 嘶s t i cm e t l l o d ，b a s e do nak i n do fs t r u c t u r e c a l l e dc h a i n1 1 1 s t a n c eq u e u e s t bi m p r o v et h ee 衔c i e n c y ，i ta c l l i e v e sl o s s l e s sf i l t e rf o rt 1 1 e c o m p o s i t ee v e n t sb ym a g l l i 母i n gp r o b a b i l i s t i ct h e s h o l d a n di tm n h e rf i l t e r sc o m p o s i t e v 一 东北大学硕士学位论文 a b s 仃a c t e v e n t sb y s e t t i l l gp r o p e r d e v i a t i o np e m i t ，i 1 1 s u r i n g h i 曲r e c a l l m e 锄w m l ei m p r o v i n g e 伍c i e n c y t h i r d ，s e m a n t i cv e c t o ri sd e s i g n e dt oi m p r o v ep r a c t i c a lv a l u eo fp r e d i c t i o n ，、v h i c h e x p r e s s e sp r o b a b i l i s t i cs t r e 锄s e g m e n ts e m a n t i ci nab a s i cw i n d o w t h es t r u c t l l r ec a i lc o n v e r t d i 髓r e n tp r o b a b i l i s t i cs 仃e 锄s e g i l l e n t si n t o 恤s 锄ev e c t o ri nf a v o ro f b u i l d i n gp r e d i c t i n g j m o d e l l a s t ，an e ws e m a n t i cv e c t o rc l u s t e r i n gb a s e de v e n tp r e d i c t i n ga l g o r i t h ms v c - s v r e pi n p r o b a b i l i s t i cs t r e 锄i sp r e s e n t e d i ti s a c h j e v e db ys e m a n t i cv e c t o rc l u s t e r i n ga n ds v r m o d e l i n g s v c - s v r e pc a np r e d i c tt 1 1 ep r o b a b i l i 够o ft h et a r g e tc o m p l e xe v e n tb e f o r et 1 1 i s e v e n to c c u r s 1 1 1a d d i t i o n ，吐l es c h e m eo fc o m p l e xe v e n tp r o c e s s i n gi sa b l et os e tp a r a m e t e ra c c o r d i n g r e q u i r e m e m s e x p e r i m e n tr e s u l t ss h o w sm em e t l l o d si 1 1t l l i sp a p e rc a ne m c i e n t l yd e t e c ta n d 东北大学硕士学位论文 目 录 目录 独创性声明i 摘要i i i a b s t r a c t v 第1 章绪论1 1 1 复杂事件处理的研究背景1 1 2 复杂事件处理的研究现状3 1 2 1 面向确定数据的复杂事件处理3 1 2 2 面向不确定数据的复杂事件处理5 1 3 本文的研究内容。6 1 4 本文结构8 第2 章相关知识介绍9 2 1 贝叶斯网络9 2 1 1 贝叶斯网络的组成和特点9 2 1 2 贝叶斯网络的应用：。1 0 2 2 支持向量机1 0 2 2 1 支持向量机算法的特点1 1 2 2 2 支持向量机的原理1 1 2 2 3 支持向量机回归1 4 2 3 复杂事件检测技术l5 2 3 1 复杂事件的检测方法1 5 2 3 2 复杂事件检测的基本模型1 6 2 4 事件预测1 7 2 5 本章小结l9 第3 章概率流上复杂事件检测算法研究2 1 3 1 概率流模型21 3 1 1 事件模型2 1 一v i t 东北大学硕士学位论文 目 录 3 1 2c p t r e e 结构。2 3 3 1 3 形成概率流2 5 3 2 查询接口2 5 3 3 启发式搜索的复杂事件检测算法2 6 3 3 1 有序匹配模式的检测2 7 3 3 2 含有无序匹配模式的检测2 9 3 3 3 概要模式的检测31 3 4 放大阈值过滤算法3 3 3 5h s f c e d 复杂事件检测算法的流程3 4 3 6 本章小结3 4 第4 章概率流上事件预测算法研究3 7 4 1 基于语义向量的预测3 7 4 1 1 概率流上的语义向量3 7 4 1 2 语义向量的构造3 8 4 2s v c s v r e p 的训练集4 0 4 2 1 语义向量生成训练样本4 0 4 2 2 通过聚类生成新的训练样本4 1 4 3 基于语义向量的预测和更新算法4 3 东北大学硕士学位论文目录 致谢6 1 攻读硕士期间参加的项目和发表的论文6 3 东北大学硕士学位论文 目录 东北大学硕士学位论文第1 章绪论 第1 章绪论 复杂事件处理( c o m p l e xe v e mp r o c e s s i n g ，c e p ) 在很多应用中发挥了重要的作用， 但是作为一种新兴的技术领域复杂事件处理仍面临许多挑战。本章首先简要介绍复杂事 件处理技术的研究背景，并对复杂事件处理的研究现状进行概述，然后给出了本文要研 究的内容，最后给出文章的组织结构。 1 1 复杂事件处理的研究背景 爱因斯坦在他的相对论中使用了“事件一词表示时空统一体中被观测到的物理 实体，字典中将事件定义为一件发生的事情或是对观测者有意义的状态更改。在我们 生活的世界里，事件无所不在。正像事件可用于物理实体建模一样，事件处理也可用 于软件建模：在面向对象系统中，由用户点击鼠标、按下按钮或选择菜单而产生的事 件对象，在g u i 组件和事务对象间传递，从而使系统对用户的操作做出响应；不仅如 此，事件处理在商务活动检测、工业生产中的调度和控制过程、网络监控和入侵检测 等很多方面都有应用。很多过程都是事件驱动的，它们接收事件、检测事件并对其做 出响应，从而使管理者理解系统内发生了什么，进而识别和解决问题，提高系统的操 作性能和安全性。由此可见，事件处理已经应用到各种各样的领域中。 在r f i d 、传感器等e d g e 设备使能的系统中，产生大量的数据，这些数据通常 是包含时间属性的元组类型的数据，它们被称为事件。然而，系统的管理者并不是对 所有的事件数据都感兴趣，数据在发挥作用前要使其有效化，使其变成具有丰富语意 并对管理者有价值的数据。如在风监控系统中，应用程序对每个传感器读出的风速数 据不感兴趣，而只对2 秒钟之内风速增加了5 英里的信息感兴趣，可以由此推断飓风 或龙卷风的到来。现代业务流程随时都在产生海量的、不同种类的事件，要想从中发 现有价值的事件无疑是大海捞针。帮助企业发现感兴趣或有意义的事件，需要一种新 的软件模式来处理数量众多的不同事件。由e d g e 设备直接读取或检测到的事件被称 为原子事件或简单事件，而由原子事件组成或生成的事件被称为复杂事件。风监控系 统中的风速数据是原子事件，表示风速的改变事件是复杂事件。以上情形需要有一种 独立的机制用于处理大量的具有时态约束的原子事件，并从其中整理和推断出有价值 的复杂事件，这种机制便是复杂事件处理( c o m p l e xe v e mp r o c e s s i n g ，c e p ) 。复杂事 件处理是一个新兴的技术领域，它的基本思想是：通过定义事件操作代数对底层的原 东北大学硕士学位论文第1 章绪论 子事件进行聚合，并通过在规则或查询语言中引用事件代数操作不断过滤连续到达的 事件，从而由原子事件查询、检测出符合应用需求的复杂事件。如在医疗监控中，来 自病人的传感器的监控数据经过复杂事件处理，可以适时地检测出病人病情的恶化， 进而向医护人员发出警报；在i u i d 使能的商品零售超市管理中，通过r f i d 读取商 品被取下货架、被带出出口、没有付款等原始事件信息，经过复杂事件处理，可以及 时检测、发现商品被偷盗的事件发生。 近年来，e d g e 设备的应用得到了迅猛发展，以r f i d 为例，所有的商品，在出 厂时，都将自动加上r f i d 标签。我们身上携带的身份证、工作证等证件也可以装上 r f i d 。另外，在纸币上也可印刷可读写的r f i d ，以监控现金的流向【l j 。今后，在一 些地区的所有关闸处，如库房出口、高速路口、超市出口、海关通道、安检通道，都 将装有r f i d 阅读器，自动识别所有的物流、人流和现金流，并对复杂事件或异常事 件进行检测。我国对i u i d 技术的开发也非常重视，在科技部2 0 0 6 年发布的国家“十 一五”科学技术发展规划中明确指出要组织实施射频标签( r f i d ) 技术与应用重大 项目。铁道部将所管辖的5 5 万多车辆加装了r f i d ，实现了车辆的实时管理。湖南省 公安厅交管局计划总投资3 5 亿元，采用i 强i d 技术对省内车辆实施监管。这些应用 也形成了空前的实时事件数据，这就需要设计复杂事件处理系统，以更高效更灵活的 方式来处理这些数据，使得系统能检测出对管理者有价值的复杂事件。 在实际应用中，由于e d g e 设备的阅读器( r e a d e r ) 自身的限制，它读出的数据很 可能不是精确数据，而是带有不确定性数据的元组【2 】，我们称这些不确定的元组类型数 据为不确定事件。事件的不确定性的级别有两个1 3 j ，一个是属性级别的不确定性，如某 人在某一时刻被检测到，这个事件中这个人的位置属性可能是不确定的( 用概率分布表 示位置) ；另一个是元组级别的不确定性，如表示人位置的事件是否存在是不确定的。 事件按发生的先后顺序排列就形成了事件流，如果组成事件流的事件是不确定事件，那 么称该事件流为概率事件流或概率流。在很多情况下，e d g e 设备直接检测出的原子事 件是不确定事件，概率事件流在现实生活中是广泛存在的，因此研究在概率事件流上的 复杂事件处理是具有重要意义的。 复杂事件处理可以发现和检测出人们感兴趣的模式或趋势，使用户能发现可能的机 遇或危险( 复杂事件) 。在很多情况下，用户还要求预知可能将要到来的机遇或危险， 即要求复杂事件处理有预测能力。例如，在气候监测管理中，预测出某一地区可能要发 生自然灾害比检测已经发生的灾害更有价值；在供应链管理中，经常需要预知一些地区 对某种物品的需求量。因此，在复杂事件处理中加入预测功能是十分有必要的。 东北大学硕士学位论文第1 章绪论 概率事件流上的复杂事件处理系统与传统的数据库管理系统相比，需要面临以下的 一些问题： ( 1 ) 由于不可能存储整个概率事件流，在处理过程中，复杂事件处理算法要随着 新不确定事件的到来而进行更新，因此需要设计某种数据结构来存储数据，等到数据处 理完毕后及时把数据从结构中删除。 ( 2 ) 由于概率事件流上的事件有不确定性，因此需要表示不同类型的不确定事件， 同时需要推理这些不确定事件的概率分布。 ( 3 ) 在概率流上事件处理的效率问题是必须考虑的问题。因为我们需要在数据更 新之前完成对它们的处理，而且还需要尽量保证结果的准确性。 ( 4 ) 当前的复杂事件处理系统几乎没有预测的能力，而我们需要使复杂事件处理 系统能预测目标事件发生的概率。 作为新兴技术领域，复杂事件处理技术还存在许多缺陷和空白，通过对复杂事件处 理技术进行研究，发现并解决现有技术存在的问题，具有非常重要的现实意义和学术价 值。 1 2 复杂事件处理的研究现状 目前由于应用需求的推动，复杂事件处理越来越受到关注和重视，逐渐成为继数 据流之后新的研究热点，许多专家和学者对复杂事件处理进行了深入研究，取得了许 多研究成果，其中包括面向确定数据的复杂事件处理技术和面向不确定数据的复杂事 件处理技术。 1 2 1 面向确定数据的复杂事件处理 面向确定数据的复杂事件处理技术的处理对象是确定的事件数据，当前有很多这 种类型的复杂事件处理系统，其中具有代表性的有：美国加州大学伯克利分校开发的 s a s e 【4 ，5 1 系统，c o m e u 大学开发的c a y u g a 系统【6 7 1 ，1 e x a s 大学a r l i n 舒o n 分校开发的 e s 骶锄系统【8 1 ，以及d a u l m o u t h 学院开发的p q s 系统【9 】。 s a s e 系统是最早提出的直接针对r f i d 事件数据进行查询处理的系统，该系统将 时序关系，数值限制，时序限制，n e g a t i o n 等操作分别作为操作符进行处理，实现了 数据采集和清洗，原子事件读取，复杂事件处理，事件存档，以及对事件的查询。查 询处理是由6 种算符的子集组成：序列扫描，序列构造，选择，窗口，非操作和转换， 如图1 1 所示，这些运算符由下至上构成了一个查询计划。同时s a s e 系统也设计了 属性分组等相关的查询优化策略。 东北大学硕士学位论文第1 章绪论 c a y u g a 系统是对传感数据中的事件实现高效在线的处理，它通过自定义的c a y u g a 自动机来进行复杂事件检测【6 j 。在c a y u g a 自动机中，将跃迁分为自循环的跃迁和向前 的跃迁。并且将自循环的跃迁分为用于过滤的跃迁和用于重绑定的跃迁，在自动机图 示中，通过自循环跃迁标在某个状态的上方或者下方来区分表示过滤和重绑定。不同 的操作有不同的跃迁类型，c a y u g a 自动机定义了一套规则来维护各个跃迁，它还定义 了多种内部命名规则，使得不同状态之间的映射和转换能够顺利地完成。c a y u g a 自动 机的示意图如图1 2 所示。 复合事件合成和转换t f 彳f 非操作n g ：! c ( b d m p d m c d 血c d ba n r = c 衄) 彳f 窗口w d ：d 血a 血e t 岔 选择：a a 船l = b 船l 皿da t 毗= l 皿da 捕】 一嚣7 彳。 砰。， 、 o ，- 。 口 图2 5e g h s 模型示意图 f i g 2 5i l l l 】s t r a t i o no fe g h sm o d e l 本章详细的介绍了与本文工作相关的知识。这些相关知识是本文研究内容的基础， 贝叶斯网络模型和对于当前复杂事件检测技术的分析与下一章的研究内容密切相关，而 支持向量机和事件预测算法又是第四章的基础。 东北大学硕士学位论文 第2 章相关知识介绍 一2 0 一 东北大学硕士学位论文 第3 章概率流上复杂事件检测算法研究 第3 章概率流上复杂事件检测算法研究 针对本文1 2 节论述的当