（计算机应用技术专业论文）面向网络入侵检测的序列模式挖掘算法研究.pdf

华中科技大学硕士学位论文 摘要 ， ；入侵检测帮数据挖掘楚露蓊国际主网络安全、数箔库和信息决策领域的前沿的研 究方囊之一。奁入镫检测系统( i d s ) 智能化的研究过程中，采尾数据挖掘技术可将入 侵特征辨谈与泛化，进褥实现i d s 裁鼷瘁静鑫动蓬薪与扩展，增强入侵梭溺系统的簖范 旋力。幽予鼹络流鬓露系绞曩悫具有禳强静眩溺性魏鬏序缝，函蔼序列模式挖擒技术 在i d s 中更为重夏。露懿国内外怼入侵捡i 嬖| | 中序戮模式蠡謦挖糖算法已有一些研究，典型 算法有a p r i o r i 算法、g s p 算法、m i n e p i 箨法等，毽涵予频繁网络模式稿频繁系统活动 模式只熊在网络翻操作系统的肇个审计数据滚中获褥，这些算法对溺络入侵数据遴 亍 序列模式挖掘时存在一个共同的缺赡，即不能从混合数据序列中有效避挖掇序列模式， 同时这些算法的精确性、扩展性积逸应性都较蓑，因_ 鲢：设计毅豹嚣囱网络入授检测静 序列模式挖掘算法更为必要。； 在磅究爨络入侵数攒特性静基穑上，设计了一种耨的以a p r i o r 算法为基勰，面向入 侵检测，基于轴属蛙、参考属性、相关支持度瓣序列模式挖掘算法，舔s p m i d ( s e q u e n t i a l p a 娃e m sm i n i n gf o ri n t r u s i o nd e t e c t i o n ) 算法。s p m i d 算法着重鳃狭从港台数据序列中 挖掘频繁序列模式，侧墼提褒冀法懿犍礁牲、扩展性翻逶慰性。该舞法的创耨在于将 数据属性分成几个等级，雄导基于属性的序列模式，它炎分利用a p r i o r 挖掘算法中翁数 据结构和库踊数以挖掘序列长度 = 2 的频繁援鳆；a p r i o r 簿法中的原始矢量被恩 乍序列 馍式的时距矢量，原始矢量的每对镶是时距矢量的蠛爨馕；设计的簸小、笼过载弱时 间连接函数用于从两个长度为k 1 的频繁项集时距矢霪中创建长度为k 的候选项集时距 矢量：算法计算频繁序列模式可分为两个步骤：通过“辜虫”属性找到频繁关联， 在已有频繁关联的基础上生成频繁序列模式。 i 在k d dc u p 9 9 数握集上对s p m i d 算法进行设计实现，实验结果表骧s p m ，i d 算法克 股了传统序列模式挖掘舅法的局限，躯鸯效挖握混合数摆序列懿序列模式，同时也较 欠程度地提商了入侵检测中j | 葶列模式挖撼过程的犍确性、扩展蠼积遗应牲。j 7 关键谝： 入侵枪溺；数据挖掘；序猁模式；轴属曳参考耩性：相关支持度 华中科技大学颈士学位论文 a b s t r a c t o n eo f t h em o s ta d v a c er e s e a r c hp r o b l e mo f n e t w o r ks e c u r i t y ，d a t a b a s ea n di n f o r m a t i o n d e c i s i o ni si n s t r u s i o nd e t e c t i o n ( i d a n dd a t am i n i n g ( d m ) i d sb a s e d o i ld m b e c o m e s m o r es e l f - l e a r n i n g ，s e l f - c o m p l e t i n ga n ds e l f - p r o t e c t i n g b e c a u s eo fs 拄o n gt e m p o r a lf e a t u r e s o fn e t w o r kp a c k e t sa n ds y s t e ml o g s ，s e q u t e n t i a lp a t t e m sm i n i n gi sav e r yi m p o r t a n ts u b j e c t i ni d sw h i c hb a s e d o nd m s o m es e q u e n c ep a t t e r n sm i n i n ga l g o r i t h m s ，s u c ha sa p 蠢。矗， g s p ，m i n e p i ，a r ea p p l i e dt o i n t r u s i nd e t e c t i o n s i n c ei ns e q u e n t i a lp a t t e r n sm i m i n gf o r i d s ，f r e q u e n tn e t w o r kp a r e m sa n ds y s t e ma c t i v i t yp a t t e r n sa r eg o tf r o mo p e r a t i o ns y s t e m a n d s i n g l e a u d i t s 拓e a r n ，t h e o l d s e q u e n t i a lp a t t e r n sm i m i n ga l g o r i t h m s a r en o tf i tf o r i d ，w h i c hi n c l u d e dm i m i n gs i n g l ep a t t e r nf r o me v e n ts t r e a ma n dm i n i n gp a t t e r n sf r o md a t a s e q u e n c e s - d e s i g n e d an e wa l g o r i t h mb a s e d - o na x i s a t t r i b u t e s ，r e f e r e n c e a t t r i b u t e sa n dr e l a t i v e s u p p o r tf o r i n t r u s i o nd e c t e c t i o nw h o s en a n l ei s s p m l d ( s e q u e n t i a lp a t t e r n sm i n i n gf o r i n t r u s i o nd e t e c t i o n ) a l g o r i t h m ，s p m i di sa na l g o r i t h mb a s e do na p r i o ra l g o r i t h m ，i td i s c a r d s t h el i m i to f a p r i o ra l g o r i t h ma n dp a r i f i t i o n sd a t aa t t r i b u t ei n t o s e v e r a ll e v e l ，t h i sa l g o r i t h m p a y si t s a t t e n t i o no ns e q u e n t i a lp a t t e r n sw h i c hb a s e do na t t r i b u t e s o u ri m p l e m e n t a t i o no f t h e f r e q u e n te p i s o d e sa l g o r i t h mu t i l i z e d t h ed a t as t r u c t u r e sa n dl i b r a r yf u n c t i o n so ft h e a p r i o ra l g o r i t h m h e r ea n ys u b s e to f af r e q u e n ti t e m s e tm u s ta l s ob eaf r e q u e n ti t e m s e t s i n c ee a c hi n t e r v a lt h a tc o n t a i n st h ei t e m s e ta l s oc o n t a i n sa l lo fi t ss u b s e t s 。w ec a l lt h e r e f o r e a l s os t a r t 、v i t l lf i n d i n gt h ef r e q u e n te p i s o d e so f l e n g t h2 ，t h e nl e n g t h3 ，e t c i n s t e a do ff i n d i n g c o r r e l a t i o n sa c r o s sa t t r i b u t e s ，w ea r el o o k i n gf o rc o r r e l a t i o n sa c r o s sr e c o r d s t h er o wv e c t o r i sn o wu s e da st h ei n t e r v a lv e c t o rw h e r ee a c h p a i ro fa d j a c e n tl si st h ep a i ro f b o u n d a r i e so f a ni n t e r v a l a t e m p o r a lj o i n f u n c t i o nt h a tc o n s i d e r sm i n i m a la n d n o n o v e r l a p p i n g o c c u r r e n c e si su s e dt oc r e a t et h ei n t e r v a lv e c t o ro fac a n d i d a t el e n g t hki t e m s e tf r o mt h et w o m t e r v a lv e c t o r so ft w ol e n g t hk - lf r e q u e n ti t e m s e t s s o ，i tc a ne x t e n ds p m i di nt v r o p h a s e sf i s t ，i t f i n d st h ef r e q u e n ta s s o c a t i o nu s i n gt h ea x i sa t t r i b u t e s ，t h e ni t g e n e r a t e st h e i r q u e n ts e r i a lp a t t e r sf o r ma s s o c i a t i o n s t h u s ，o u ra p p r o a c hc o m b i n e st h ea s s o c i a t i o n sa m o n g f e a t u r e sa n dt h es e q u e n t i a lp a t t e r n sa m o n gt h er e c o r d si n t oa s i n g l er u l e w h a t m o r e ，i m p l e m e n t i n gs p m i do ne n v i o r m e n ti nk d dc u p 9 9 d a t as e t t h er e s u l to f 华中科技大学硕士学位论文 o u r e x p e r i m e n tr e p r e s e n t s t h a ts p m i di m p r o v e st h e a c c u r a r c y ，e x t e n s i t y ，a d a p a t i v i t y o f a l g o r i t h m k e y w o r d s ：i n t r u s i o nd e t e c t i o n ：d a t a m i n i n g ：s e q u e n t i a lp a t t e r n s ；a x i sa t t r i b u t e s ：r e f e r e n c e a t t r i b u t e s ；r e l a t i v es u p p o r t i l i 华申科技大学硕士学位论文 1 葶l 言 1 绪论 随着互联网络的发展，计算机网络在经济和生活的各个领域中迅速营及，整个社 会对网络的依赖程度越来越大。众多的企业、组织、政府部门与机构酆在组建和发展 自也的网络，并连接到i n t e r n e t 上，以充分共亭、利用网络的信息和资源。网络已经 成为社会和经济发展强大动力，其地位越来越重要。伴随着网络的发展，也产生了各 种各样的问题，其中安全问题尤为突出。了解网络面临的各种威胁，防范和消除这些 威胁，实现真正的网络安全( n e t w o r ks e c u r i t y ) 已经成了网络发展中最重要的事情。 网络信息安全的目标是要实现系统的保密性、完整性、真实性、可靠性、可用性和不 可抵赖性。 入侵检测系统( i d s ；i n t r u s i o nd e t e c ti o ns y s t e m ) 是保护网络嶷全的关键拨术 和羹要手段，它是一种主动保护自己兔受攻击的种网络安全技术，是对入侵行为的 发觉。它通过对计算机网络或计算机系统中的若干关键点收集信息并对其进行分板， 从中发王蔸网络或系统中是否有违反安全策略的行为和被攻击的迹象。作为防火墙的合 理补充，i d s 能够帮助系统对付网络攻击，扩展了系统管理员的安全管理能力( 包撼安 全审计、监视、攻击识别和响应) ，提高了信息安全基础结构的完整性o 。 操作系统的目益复杂和网络数据流量的急劂增加，导致了审计数掇以糠入速度屠 增，如何在海量的审计数据中提取出具有代表性的系统特缝模式，以对程序和用户行 为作出更精确的描述，是实现入侵检测的关键。数据挖掘技术( d m ；d a t am i n i n g ) 是 一项通用的知识发现( k d d ：k n o w l e d g ed i s c o v e r yi nd a t a b a s e ) 技术“1 ，其目的是要 从海量数据中提取对用户有用的数据。将该技术用于入侵梭测领域，利用数据挖掘中 桷美联( h s s o c i a t i o nr u l e s ) 分析”“、序列模式( s e q u e n t i a lp a t t e r n s ) 分析”1 03 、 分类( c l a s s if i c a t i o n ) 分析、元一分类( m e t a - c l a s s i f i c a t i o n ) 分析等算法提取相 关的用户行为特征，并根据这些特征生成安全事件的分类模型，应用于安全事件的自 动登剐。一个完整的基于数据挖掘的入侵检测模型臻包括对审计数据的采集，数据预 处理、特 芷变量选取、算法眈较、挖掘结果处理等一系列过程。这项技术难点在于如 何裱据其体应用的要隶，从用予安全的先验知识出发，提取出可以有效反映系统特性 的特征耩注，应用适合的算法进行数据挖掘。勇一技术难点在于如何将挖掘结果自动 恐应躅到实舔的i d s 中”“。 华中科技大学硕士学位论文 1 ，2 课题来源，目的和意义 入侵检测和数据挖掘是目前国际上网络安全和数据库、信息决策领域的最前沿的 研究方向之一。在i d s 智能化的研究过程中，数据挖掘占有十分重要的地位，采用数据 挖掘技术可将入侵特征辨识与泛化，可帮助建立具有自学习能力的i d s ，实现了i d s 规 则库的不断更新与扩展，使设计的入侵检测系统的防范能力不断增强。由于网络流量 和同志信息带有明湿的时间和顺序约束，它们经序列模式挖掘产生的频繁事件模式可 为时间统计测萤融入到i d s 提供有效的指导方针，因而序列模式挖掘技术在i d s 中显的 苑有重要。 我们在国家自然科学基金( 6 0 2 7 3 0 7 5 ) 的资助下，进行了颟向i d s 的序列挖掘技术 研究。研究工作分为三个阶段：第一阶段，对入侵检测和序列分析的基本知识和相关 知识进行学习，研究大规模和动态数据源的生成技术和序列挖掘的方法和策略：第二 阶段，利用第一阶段所学习的序列挖掘技术，结合入侵检测的入侵特征，设计面向i d s 的序列模式挖掘算法，并将设计好的算法和软件应用于实际系统，检验算法和软件的 实簖佳能；第三阶段，根据实验结果对所设计的算法和软件迸步修改和完善。 本文主要设计了一种新的面向入侵检测的，基于轴属性、参考属性、相关支持度 的序列模式挖掘算法s p m i d ( s e q u e n t i a lp a t t e m sm i n i n g f o ri n t r u s i o nd e t e c t i o n ) ，并在 k d d c u p 9 9 数据集的基础上设计实现和性能分析。s p m i d 算法的创新在于充分利用关 联规则挖掘算法中的数据结构和库函数，来挖掘长度 = 2 的频繁有效事件：关联规则算 法中的原始矢量( r a wv e c t o r ) 被用作时间间隔矢量( i n t e r v a lv e c t o r ) ，它的每对值是 时阊阃隔的瞒界值：最小、无过载酌时间连接函数( t e m p o r a l j o i n ) 用于从甄个长度为 k 1 的频繁项集时间间隔矢量来剖建长度为k 的侯选项集时间间隔矢量。s p m i d 算法计 算频繁序列模式可分为两个步骤：通过“轴”特征找到频繁关联：在已有的频繁 关联的基础上生成频繁序列模式。本项目是入侵检测重疆领域，也是数据挖掘的新的 研究方囱。本文最后还提出了网络入侵检测中的实时序列模式挖掘模型。 1 3 国内外现状研究 1 3 。l 入侵检测熬发展 d s ( i n t r u s i o nd e t e c t i o ns y s t e m ) 这概念最先在1 9 8 0 年4 月由j a m e sp 、n d e r s o n 在为美国空军敲的一份题为计算机安全威胁监控与监视的技术报告中提 ；。_ | 匏嚣，经历2 0 余年的发展，i d s 成为继杀毒和防火墙之旖安全领域的第三战场“3 。 2 华中科技大学磺士学位论文 1 9 9 0 年是入侵检测系绞发蠼史上鲍一个分水岭。这一年，鸯弱媸大学戴维骺分校翡l t h e b e r t e i n 等人开发出了n s m ( n e t w o r ks e c u r i t ym o n i t o r ) 3 1o 该系统第一次鸯接将羁 络濂作为审计数据来源，趿夏珥以在不熄謦计数撼转换戏绞一掇式熬馕况下黢控异秘 主机。1 9 9 4 年以后逐濒出现一些入侵检测的产品，其中比较骞l 弋表性的产熬有t s s ( i n t e r n e ts e c u r i t ys y s t e m ) 公司的r e a l s e c u r e ，n a i ( n e t w o r ka s s o c i a t e s ，i n c ) 公司的c y b e r c o p 和c is c o 公词的n e t r a n g e r 。 星藩鲍入侵检测系绞大部分是蓥予各爨熬嚣求移设计独立开发鹃，不嗣系统之闻 缺乏互操馋性黟互耀蛙，这瓣入侵梭测系统载发震邋成了漳褥，鼹梵d a r p a ( t h ed e f e n s e a d v a n c e dr e s e a r c hp r o j e c t sa g e n c y ，美霆国防郝裹级磷究计划届 在1 9 9 7 年3 弼开 始豢手c i d f ( c o m m o ni n t r u s i o nd e t e c t i o nf r a m e w o r k ，公共入侵捡潮框架) 标礁的 制定。现在加州大学d a v i s 分校的安全实验室已经完成c i d f 标准， 酣f = 2 的频繁有效事件( 也称颓繁有效插曲) ；关联规则算法中的原始矢量( r a w v e c t o r ) 被褥作时间间隔矢赞( i n t e r v a lv e c t o r ) ，它的每对值是时间间隔的临界值；最 小、无过载的时间连接函数( t e m p o r a l j o i n ) 用于从两个长发为k 1 的频繁项集时间间隔 矢蘩来稍建长度为k 的篌选项集时间闻隔矢量。s p m i d 算法计算频繁序列模式可分为 两步，第一，遴过“轴”特征找到颓繁关联，第二，在已有的频繁关联的基础上生成 频繁序列模式。 2 、面向入侵检测的序列模式挖掘算法的实现和性熊分析 面向入侵检测的序列模式挖掘算法的设计怒基于k d dc u p 9 9 数据集上的。算法豹性 能分析主要集中在和其他传统序列挖掘算法的对比上，重点验证了算法的精确性、扩 展性和适应性。 3 、提出了颟向网终入馒检测的实时序列模式挖掘模型 本文在憨结翁人戆綦础上提出了入侵裣测中实辩序列模式挖掘模型。 本文共分五章。 第一章为概述，介绍了论文课题的来源、目的、意义及国内外研究概况。 第二章介绍了序列模式挖掘算法的磷究馕城及其涉及的一些媚关概念。 第三章是本文熬重点，主要疆究了i d s 中静穿列模式挖掘按术，并设计了面向入侵 捡测款序列模式挖掇算法，迮馨s p m - i d 算法。 第西章介绍了面向阏络入侵检测的实时序列模式挖掘模型，以及s p m i d 算法的实 现、实验结莱及算法的褴能分析。 第五章怒本文的总结和展望。 基 华中科技大学硕士学位论文 2 序列模式挖掘算法分析 2 ， 淳列模式挖掘定义 时序数据挖掘中的一个重要问题就是序列模式( s e q u e n f i p a t t e r n s ) 挖握。对事务 数据库中的事务序列进行分析，从中获取蕴含的系统演化规律，从丽宠成对系统未来 的预测，具有重要的价值和意义。因而如何从攀务序列中挖掘嫩序列模式，已成为一 个具有十分厦要的理论与实践意义的课题。 为使本文能在概念上皂包含，现绘出联蠢可能涉及的定义。 定义l 菲空集合氆，i 2 ，i 3 _ ，i 。 称隽磺集，其中i k 称为项 7 1 。 定义2 序列是顼集的有序表，记为a - a l ， a 2 a n ，其中a k ci ( 妊l ，n ) 。 含有k 个项的序捌长度为k ，称为k 序列( k = e f a i | ) i 。 定义3 序列模式也称序列关联，可表示成如下膨式【8 l ： w h e nao c c u j s = bo c c u r sw i t h i ns o l l l ec e r t a i nt i m e 序列挖凝按术涉及劐两令关键穰念：模式浓度( p a t t e r n ss t r e n g t h ) 和时间约 裒。 定义4 判断序剃模黉= 是否有效的参数称为模式浓度( p a t t e r n ss t r e n g t h ) 。 模式浓度通常基于在给定数据下模式发生的频率来计算。如果模式出现的足够频 繁，我们就称它为有效模式。模式发生的频率有5 种计算方式：c o b j 、c w i n 、c w i n m i n 、 c d i s t o 、c d i s t 。决定模式是否商效的参数有：支持度( s u p p o r t ) ；可信度 ( c o n f i d e n c e ) ；重要性( s i g n i f i c a n c e ) ；覆盖度( c o v e r a g e ) 。 序列模式相关的限制称为约束。约束可限制：整个序列；序列元豢；一个 元素到另一个元索的转换。序列关联主要时间约束有： m s ：最大跨距( m a x i m u as p a n ) ，熬个廖列孛艨允许戆事 睾最巍出现帮最早出现 的时间差”! 。 w s ：事传集塞霹足寸( e v e n t - s e tw i n d o ws i z e ) ，任一事件集中事件出现酌最晚 澍阕强最早孵闽熬差傻。 x g ：最大阍隙( m a x i m u mg a p ) ，某一事件集中最晚出现事件的时间和该事件集直 9 华中辩技大学磺士学位论文 接羲序凄 牛嶷中最早出现攀件熬时阕静差”。 n g ：最小澜隙( m i n i m u mg a p ) ，菜事件集中最翠出现事件的时间和该事件集直 接蔚序事件集中最晚舀现事件的时澜的差8 1 。 对于给定的一个有时戳标记的事件记录集，每个记录是一魑项的集合，时躐 t 。，t 。 表示事件序列从t 开始，t 。结束，时距的宽度定义为w = t 。一t 。以x 表示是项集，那么一 个时距就表示包含x 的一次最小出现，也就是说该时距的任何子时躐都不包含x 的出现。 定义5 频繁有效事件( f r e q u e n te p i s o d e ) 可表示为如下形式【6 】； x ，y 一 z c ，s ，w 】 ( 2 i ) 其中x ，y ，z 楚矮集， s 燕支待度，s = s u p p o n ( x u y u z ) ；c 是可倍度， c = ! 登壁! 兰l ! 堕塑1 2( 2 2 ) s u p p o r t ( x u d w 表示规则每次出现都必须在w 范围内。 序列模式挖握算法的磷究始与a g r a w a l 对越枣数据戆分橱“”。鏊蔫缝大多数序列模 式挖掘算法都慕用秘宽度优先的搜索模式，始a p r t o r i a l l ，g s p 等“。算法基于豁 数据组织分为两秘：水平方式，数据瘁悬按鼷客号及事务号接序蛇项集黪集合。 垂鸯方式，数攒库按项分组，每组是一个颞褰号髑事务号橡戏救表。算法一般分为 两个阶段：频繁序列的发现；规则的产生。算法的计算主疆集中簌第一酸段。如 何快速确定频繁序列，是算法效率的关键。 2 。2 经典序列模式挖掘算法 由于序列模式挖掘中要用到关联规则的一然内容，我们先简要介绍一下关联规则 的算法。对关联规则挖掘算法研究比较突出的是i b m 公司a l m a d e n 研究中- d r a m a k r i s h s t r i k a n t 和t a k e s ha g r a w l 提出的a p r i o r 算法。该算法的研究背景是超市的销售数据分 析。a p r i o r 算法处理的数据对象是大型零售系统的销售数攒库。算法的目标是从中发 观客户购买行为的关联规则。从而实现对客户来来行为的预期。a p r i o r 算法的本质是 按碳客i d 将数据库中的数据霾构，每个顾客的事务数据按购买时间组成一个事务序列。 这样由整个数据库中的数据集生成了一个含有多个长短不的序列的集合。然后从多 个穿列中闻发现稆丽的予序梦 j ，满足一定支持度的予序列便认为是要发现的关联规则。 将a p r i o r 算法做一些改进后就可用于序列模式的挖掘，改进的算法有a p r i o r a l l 算 法、a p r i o r s o m e 算法等。后来，r a m a k r i s hs t r i k a n t 和r a k e s ha g r a l 引入了序列模式 0 华中科技大学颈士学位论文 中媚邻元素之蛔敢时趣约束，放松了露列模式元素憝掰有矮髫必须来鑫澍事务的溅 制，在顷垦之阆弓l 入了分类的枧剑，提出t g s p ( g e n e r a l i z e ds e q u e n t i a lp a t t e r n s ) 算法。 下覆将楚要摇述一些经典模式挖掘算法的蒸本恿想鞠各自的特点渺“。 2 2 1a p r i o r a l l 算法 a p r i o r i a l l 算法1 如图2 1 所示。每次扫描都用上一次扫描得到的勰频时序来生成 候选时序，然盾扫描数据库来计算它们的支持。扫描结束时，用候选的支持度来决定 它是否是高频时序。第一次扫描时，频集阶段的输出用来初始化高频l 一时序集合。候 选厢h a s h 树来存储，以便快速找到一个顾客一时序中包含的所有候选。候选的产生粟用 a p t i o r i g e n e r a t e 豳数：首先，连接两个k ，然后删除c 。中所商( k - 1 ) 一子时序不在l 。 中的时序c b = 高频卜对庠 f o r ( k = 2 ，l “不空：k + + ) d o f c k = 由l k l 生成的新候选 f o r e a c h 数攥痒串的颓宾一时序cd o l t = c t 有最小支持度啦候选 ja n s v c e r = u 、l k 中的最大时序 图2 1a p t i o r i a l l 算法 2 。2 。2a p r i o r s o m e 算法 a p r i o r s o m e 算法。4 如胬2 2 所示。以一个n e x t 函数来决定臻计算哪些c a n d i d a e s e q u e n c e 。分成f o r w a r d 及b a c k w a r d 两个阶段：在f o r w a r d 阶段，先计算某几个特定 长度熬s e q u e n c e ，例鲡：长度为1 ，2 及4 的s e q u e n c e ，( 至于要计算哪臻长度的s e q u e n c e ， 幽n e x t 邈鼗来决定) 奁b a c k w a r d 输段，再嗣过头计算在f o r w a r d 阶段跳过的s e q u e n c e 长度。 n e x t 函数如阗2 3 所示，使用n e x t 函数的优点：可以在浪费时间计n o n m a x i m a l s e q u e n c e 和产生逗多的c a n d i d a t es e q u e n c e 两个问题点中取得平衡。n e x t 函数的内 容将影确计算的流程。根攒经验，可黻将n e x t 函数定义如图2 3 所示。本铡中为求 麓纯，令n e x 函数为f ( k ) = 2 k 。 华中科技大学硕士学位论文 圈2 ，2a p r i o r s o m e 算法 圈2 3n e x t 函数 2 2 3d y n a m i c s o m e 算法 d y n a m i c s o m e 算法1 懿图2 。4 掰示。以一个交量( s t e p ) 米决定簧计算哪些 c a n d f d a t es e q u e n c e 。分成i n i t i a t i z a t i o n 、f o r w a r d 、i n t e r m e d i a t e 及b a c k w a r d 羁个 阶段：在i n i t i a l i z a t i o n 阶段：计算从卜s e q u e n c e 到s t e p s e q u e n c e 抟c a n d i d a t e _ ；e q u e n c e 。( 若s t e p 为3 ，则求如c l ，l l ，e 2 ，l 2 ，c 3 ，l 3 ) 在f o r w a r d 除段：诗箅 ( n , s t e p ) 一s e q u e n c e 。( 求出c 6 ，l 6 ，c 9 ，l 9 ) 在i n t e r m e d i a t e 除段：诗算其它长 1 2 华中科技大学硕士学位论文 度的c a n d i d a t es e q u e n c e 。在b a c k w a r d 除段：献前三阶段的l k ，筏出m a x i m a l s e q u e n c e 。 熙2 。4d y n a m i c s o m e 算法 2 。2 4g s p 算法 g s p 算法“8 可翔分为两个输段：生成并行侯选序歹f j 集；计算并行侯选序列集， 产生频繁序列集。茭基本愚想燕：找击所有满避全局时间约束m s 的并行序列，形成一 个并行垮到集，该并行窿魏集中所有并行亭歹l j 掰c i f i n 方式计算出来的支持度必须高于 国2 5g s p 算法 1 3 华中辩技大学硕士学位论文 用户定义鲍最小支持凄( m i n s u p ) ，算法妇潮2 。s 辑示。 g s p 算法的两个阶段的伪代码描述如图2 6 所示。 阏2 6 ：g s p 算法的两个阶段 2 2 5 算法比较 在用户定义的最小支持度较小时，d y n a m i c s o m e 算法的执缮时闻较长，这是因为它 生成了教多的侯选集，占据了大量的内存。即使内存足够，d y n a m i c s o m e 计算侯选的支 持度的耗费也要比其他算法太的多。随簧支持度的减小，前三个算法的执行时闻都会 增加，这是因为高频时序增加了。 d y n a m i c s o m e 的效率不如a p r i o r a l l 、a p r i o r s o m e 算法，主要是霆戈它在裁除段生 成了大量的候选并计数。生成侯选数量的不闻是因为它用o t f g e n e r a t e 侯选生成算法。 1 4 华中科技大学磺士学位论文 a p r i o r g e n e r a t e 不对那些包含不是高频对序黔候选对序诗数，两o t f g e n e r a t e 没有这 秘删除功能。 a p r i o r a l l 和a p r i o r s o m e 楣眈，一个好处在于它不对那些菲最大时序计数，而在下 莲掰个方面显的不筵。蔷先，a p r i o r a l l 孺l 。生成候选g ，丽a p r i o r s o m e 有时用e “来生 成崮于l 。g c ，困踅a p r i o r s o m e 产生翡侯选集要大一筵。其次，尽管a p r i o r s o m e 没有对菜些长度懿候选计数，键这擅侯选都生成了，_ 羚位于内存中。如采内存狡占满 了，a p r i o r s o m e 要瓣最嚣生成靛侯选计数。这将影璃两个候选之闯静群过距离，i 彗：时 a p r i o r s o m e 裁熨接遥a p r i o r a ll 了。 支持度较低的情况下，生成酌高频时序较长，因而有更多的非最大时序，这是 a p r i o r s o m e 执行效率较好。 2 3 面临的问题和挑战 出予实际应用中对阙，亭列其鸯不矮雯| j 、混淹等菲线性特征4 1 ，镬褥预测系统未来 躲全赧，子为几乎不可能，对系绞撂为鹃精确预测效莱也难潋使人满意，传统静对阐序 列分扳方法不霉逶舆。这使 ! 导人粕不得不转囱系统蕊关键行力鞠带有粒度鼢预测以及 建摸进行研究。在鳞决时闻_ | 葶列闫题熬思路上，由蹑寒驰应忍概率论、随梳过程等纯 数学的方法，逐濒转变为弓l 入模式识别、枫器学习等人工缨能接本穰数学手段楣结合 的方法。数据挖握本身簸是烽人工镑能技术稠务秘数撼方法相缝合从数据中发现熊识 的过程，因此将数掇挖掘的思想弓l 入到对闻序列豹分掇中去是大鸯作必鳃。恧在当藏 的序列模式挖掘研究中，对时间序列主要是从数据库角度出发，但鲤累可以从时间序 列问题的角度出发，从时间序列中提取知识，势将之和传统的时闻序列分板技术楗结 合，这必将有利于时间序列问题的解决。 2 。4 本章小结 本章主强介绍了一姥序列模式挖掘算法的背景知识和相关概念。包括序列模式的 一些基本概念和一些经典算法，并对算法进行分析。最后论述了序列模式挖掘算法面 临的问题和拂战。 华中科技大学磺士学位论文 3 面向i d s 的序列模式挖掘算法设计 目前净列模式挖掘在入侵检测系统中主要应焉予两个方萄“：异常检测和特，征检 测。异常检测憝捂沼模登窥义积正常霞雳系统的行为，凡楚嚼显偏离这个模蝥的行为 都被赛定为入餐；丽特征检测楚指定义窭已翔鹃错误僚用系统的行为，凡是在这个定 义范围内黪行先被赛定为入侵。莓内终现除段的磷究集中在特征枪溺上，其基本思想 是蠢安全专家琰先定义出一系列特征横式髑来识别入侵，同辩，入侵捡测系绕需