（计算机应用技术专业论文）计算系统性能异常检测算法的研究与实现.pdf

南京理工大学硕士学位论文 计算系统性能异常检测算法的研究与实现 摘要 计算系统性能异常是指在软件运行期间，由于资源逐渐耗尽或运行错误逐渐累积 所导致的计算系统性能逐渐下降，最终下降到人们所不能容忍的程度的现象。性能异 常检测能根据系统资源的占用情况，对提取的系统性能属性进行定量分析，实时监测 系统的性能状况。 本文首先研究了性能异常检测的算法，主要有基于统计的异常检测算法、基于数 据挖掘的异常检测算法、基于机器学习的异常检测算法以及基于人工免疫系统的异常 检测算法，并分析了现有的异常检测算法的不足，它们不能完全满足性能异常检测的 需要。其次针对性能异常检测的具体问题，采用了一般的异常检测算法，将健康的系 统状态划分为一类，不健康的系统状态划分为另一类。从而提出了一种多阶段聚类算 法，该算法将层次聚类和其它的聚类技术进行集成，形成多阶段聚类，有效地提高了 聚类的准确度和速度；实验结果表明该算法具备较好的检测性能。荐次改进了贝叶斯 分类器，它不受类条件独立假设的限制，透过对属性集的筛选减少属性之间的依赖性， 从而增强了贝叶斯分类器的适用性以及加快了分类的速度；实验结果表明该算法能够 有效地提高分类精确度和异常检测的准确率。最后比较了两种方法各自的适用范围和 优缺点。 关键词计算系统性能异常性能异常检测多阶段聚类算法改进的贝叶斯分类器 兰坠! 氅一 堡圭兰苎 a b s t r a c t t h ec o m p u t i n gs y s t e mp e r f o r m a n c ee x c e p t i o ni st h ep h e n o m e n o no fp e r f o r m a n c e c h a r a c t e r i s t i c ss m o o t h l yd e g r a d i n gd u r i n gt h er u n n i n go fs o f t w a r e , b e c a u s eo fe x h a u s t i n g o fl e s o u l e so rc u m u l a t i n go fr u n t i m ee r r o r s ，u n t i la ni n t o l e r a b l er e d u c t i o no fc a p a c i t vi s e v e n t u a l l yr e a c h e d t h ep e r f o r m a n c ea n o m a l yd e t e c t i o nc a l lq u a n t i f i c a t i o n a l l ya n a l y z et h e p e r f o r m a n c ea t t r i b u t e sa c c o r d i n gt ot h ee n g r o s s i n go fs y s t e mr e s o u r c c sa n dr e a l - t i m e l y i n s p e c ts y s t e m ss t a t u s f i r s t l y , 、ei n v e s t i g a t et h ea l g o r i t h m so fp e r f o r m a n c ea n o m a l yd e t e c t i o nt h e ya l e a n o m a l yd e l e t i o na l g o r i t h mb a s e so ns t a t i s t i c ，a n o m a l yd e t e c t i o na l g o r i t h mb a s e so nd a t a m i n i n g ，a n o m a l yd e t e c t i o na l g o r i t h mb a s e so nm a c h i n el e a r n i n ga n da n o m a l yd e t e c t i o n a l g o r i t h mb a s e so nn a r l r a li m m u n i t ys y s t e m w ea l s oa n a l y z et h es h o r t a g eo fe x i s t i n g a l g o r i t h m s t h e yc a n n o tc o m p l e t e l ys a t i s f yt h en e e do fp e r f o r m a n c ee x c e p t i o nd e t e c t i o n s e c o n d l bw ea i ma tt h es p e c i a lp r o b l e mo fp e r f o r m a n c ee x c e p t i o nd e t e c t i o na n da d o p t g e n e r a la n o m a l yd e t e c t i o na l g o r i t h m , i nw h i c hh d a l t h ys y s t e ms t a t e sa r ed i v i d e di n t oo n e c l a s s ，u n h e a l t h ys t a t e sa l ed i v i d e di n t oa n o t h e rc l a s s t h e r e b yt h em u l t i p h a s e dc l u s t e r i n g a l g o r i t h mi sp r o p o s e d , i ti n t e g r a t e sl a y e r e dc l u s t e r i n ga n do t h e rc l u s t e r i n gt of o r m m u l t i - p h a s e dc l u s t e r i n g 。t h u st h ea l g o r i t h mc a ne f f e c t i v e l yi n c r e a s et h ea c c u r a c ya n dt h e r a t e t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h ep r o p o s e da l g o r i t h mh a sag o o dd e t e c t i o ne f f e c t t h i r d l y , t h ei m p r o v e db a y e s i a nc l a s s i f i e r si sp r o p o s e d n a h 咛b a y e s i a nc l a s s i f i e r sw h i c h m a k ei n d e p e n d e n c ea s s u m p t i o n sp e r f o r mr e m a r k a b l yw e l lo ns o m ed a t as e t sb u tp o o r l yo n o t h e r s w ee x p l o r ew a y st oi m p r o v et h eb a y e s i a nc l a s s i f i e rb ys e a r c h i n gf o rd e p e n d e n c i e s a m o n ga t t r i b u t e s t h ei m p r o v e dc l a s s i f i e r b o o s t si t s a p p l i c a b i l i t y a n di n c r e a s e st h e c l a s s i f i e dr a t e t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h ei m p r o v e dc l a s s i f i e rc a ne f f e c t i v e l y i m p r o v et h ec l a s s i f i e da c c u r a c ya n dt h ed e t e c t i o ne f f e c t f i n a l l y , w ec o m p a r et h et w o a l g o r i t h m s k e y w o r d s ：c o m p u t i n gs y s t e mp e r f o r m a n c ee x c e p t i o n ，p e r f o r m a n c ea n o m a l yd e t e c t i o n ， m u l t i - p h a s e dc l u s t e r i n ga l g o r i t h m ，i m p r o v e db a y e s i a nc l a s s i f i e r s l i 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在 本学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发 表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学 历而使用过的材料。与我一同工作的同事对本学位论文做m 的贡献均 已在论文巾作了明确的说明。 研究生签名：匦i 聱纽j 。石年凸月l 口 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅 或上网公布本学位论文的全部或部分内容，叫以向有关部门或机构送 交并授权其保存、借阅或上网公布本学位论文的全部或部分内容。对 于保密论文，按保密的有关规定和程序处理。 研究生签名：陋辽整1 土d 眄年莎月工日 南京理工大学硕士学位论文 计算系统性能异常检测算法的研究与实现 1 绪论 信息技术的飞速发展引起了计算领域的重大变更，但是随着应用的深入，不得不 正视如下事实：1 ) 计算系统的高可信赖、高速度和高可用性等特点，要求其管理与 维护从人的直接干预下解脱出来；2 ) 系统自身总体结构复杂化倾向已使人难以直接 对其进行系统性能衰退的检测和防护。 这种不应该也不可能完全由人直接干预，以维护计算系统性能的趋势引发出新的 研究方向，即所谓的“自主计算”( a u t o n o m i cc o m p m i n g ) 。自主计算主要包括自我 配置、自我修复、自我优化和自我保护。其原理是模仿人的植物神经系统，它们能够 自动地控制相关机体的运行，而不用经过大脑主观意识的干预。 自主计算的系统必须能够感知环境的变化和内部状态，提取系统状态并从中分析 出系统的性能状况，为自我管理提供充分的决策支持。为此本文采用系统性能异常检 测从提取的系统性能属性中分析系统的性能状况。 1 1 背景 传统的容错技术是将系统设计成即使局部发生故障，整体依然功能不变。然而再 坚固的系统依然会发生放障。其原因主要有三个方面：人的操作失误、外部攻击、硬 件故障和软件衰退而导致的系统性能异常。髓着软件不断地变大、变复杂，软件已经 成为系统性能下降的主要原因。即使所有由软件导致的系统性能下降的原因在于软件 本身的设计错误，但是现今软件如此复杂以及在软件测试过程中存在一定的限制使得 开发完全没有错误的软件是不现实的。因此在软件的运行过程中，要采用系统性能异 常检测来延缓软件的衰老，最终达到减慢系统性能下降速度的目的。 1 1 1 性能异常检测 异常检测被用来发现小的模式，即数据集中间显著不同于其它数据的对象。异常 检测可以应用在入侵检测、电信和信用卡欺骗、贷款审批、气象预报、金融领域和客 户分类等领域中。本文中所讨论的性能异常检测算法主要应用于系统性能保持和软件 抗衰方面，它的作用就在于建立一个模型或规则库来正确的分类系统性能异常状况。 性能异常检测是保证系统持续正常工作的前提。可以用于性能异常检测的算法主 要有：基于统计的异常检测算法；基于数据挖掘的异常检测算法；基于机器学习的异 常检测算法；基于人工免疫系统的异常检测算法。 硕士论文 性能异常检测就是用来识别计算系统运行的性能异常，将健康的系统状态划分成 一类，不健康的系统状态( 即异常) 划分成另外一类。首先提取系统的性能属性如： 内存使用率，c p u 的占用率，网络带宽、资源使用率、工作负荷、响应时间、服务 时间等；然后选用性能异常检测算法对所提取的性能属性建立一个模型或规则库来正 确的分类系统性能的异常状况，这样就可以及时地检测到系统的异常：对出现异常的 系统采取必要的措施。不然的话，一旦这类异常出现，将导致系统短暂的瘫痪，产生 难以预料的后果，给系统造成不必要的经济损失。 性能异常检测算法与一般的异常检测算法的不同之处在于必须应对高度变化的 系统内外部环境变化带来的概念迁移，也就是正常或异常定义的变化。一般来说性能 异常检测是一个二元分类问题，但是每一类都可以进一步划分成若干的层次( 与标准 的距离来衡量) 来表明不同的情况( 比如说性能异常有不同的等级，采用不同的恢复 操作) ，为自我管理提供不同的决策策略。 1 , 1 2 系统性能异常检涓的必要性 真正系统的性能会随着时间的推移而逐渐下降，最终系统的性能将会下降到人们 所不能容忍的程度。导致系统性能下降的两个最主要的因素是条件冲突和软件衰退， 前者指系统的性能从一个很好的状态突然下降到o ；而后者则意味着一个缓慢的降低 过程，出现降低过程的原因有：内存膨胀或泄漏、未释放的文件锁、数据污损、错误 累积等等。本文只针对软件衰退来分析采用性能异常检测的必要性。 i n t e m e t 技术的迅速发展给计算机系统提出了新的挑战，当今的计算机系统必须 具有可靠性，既能够2 4 小时为用户提供正确的服务，又必须具有可用性，还能够随时为 成千上万的用户提供服务。人们对计算机系统的依赖性越来越强，计算机系统故障所 造成的损失也越来越不容忽视。据报告，由于服务器的突然停机给企业造成的经济损 失甚至可以高达2 7 万美元分钟【4 ”。据g a r t n e r g r o u p 估算，4 0 的服务器故障是由软 件引起的( 2 。 目前，已经观察到软件随罄时间的推移出现了衰退的现象。h u a n ge t a 1 2 1 1 报导了 在无线电通讯帐单应用软件中，随着时间的推移，软件出现崩溃或挂起的错误。 a v r i t z e r w e y u k e r t 2 4 l 讨论了在无线电通讯转换软件中的衰退现象，表现为性能的逐 步下降。在广泛使用的软件诸如n e t s c a p e & x t t n 中也观察到了软件衰退的现象。在要 求高可靠性和高实用性的系统中，软件衰退可以导致储运损耗表现为很高的成本。 对出现性能下降的系统，通常采取的策略只是一些本能的反应，如：故障出现以 后才采取行动。最近提出了一种预防性的措施，即周期性地停止软件的运行，“清理” 其内部状态，然后重启，将系统以及它的操作环境恢复到一个干净的( c l e a n ) 状态。 堕塞墨三查堂塑圭茎堡堡苎生墨墨篓堡塑墨堂堡型苎鳖塑塑塑兰塑 “清理”软件的内部状态包括碎片收集、清空操作系统内核表，重新初始化内部数据 结构等。这些措施披称为软件抗衰，可以这样来定义软件抗衰：它是一种基于前摄 ( p r o a c f i v e ) 思想的故障处理技术，目的在于整理系统的内部状态以防止在将来出现 更多严重的紧急故障。它包括周期性地中止应用软件或程序的运行，清理其内部状态 以及重启。 虽然任何抗衰都会有一定的负荷，但是它能够预防更多严重故障的发生。因此， 在分析抗衰策略过程中的一个重要阀题是确定其在实用性和成本方面的有效性，以及 提出一个最佳的标准来决定何时以及多久将系统从异常的状态中恢复过来。本文使用 系统性能异常检测算法对提取的系统性能属性进行定量分析，检测系统何时出现了性 能异常的现象。至于多久以及如何将系统从异常的状态中恢复过来不属于本文研究 的范围，在此不做详细地讨论。 1 。1 3 研究现状 在系统运行期间，可能会出现由于资源逐渐耗尽或运行错误逐渐累积所导致的系 统性能下降的现象。由于软件错误导致的软件衰退从而引起的系统性能异常很难避 免，一般来说，软件错误可能存在于用户书写的程序、软件调用的构件、软件的开发 环境，甚至操作系统中。当今，在工业界广泛采用基于构件的软件复用技术，大多商 业构件提供黑箱复用的方式，其源码不鹾被修改；即使是白箱复用的构件，在复杂的软 件结构中确定错误的来源也非易事。因此，通常人们采用控制开发过程、调试和测试 软件来减少程序中错误的发生。针对软件衰退现状，1 9 9 5 年y h u a n g 首次提出了软 件抗襄技术1 2 q ，软件抗衰是指为预防系统突然发生故障而预先采取的措施。它是一种 前摄的容错技术，主要通过适时、透度地消除系统内部错误的运行状态柬完成。主要 措施有：周期性地暂停软件的运行，清除系统的内部状态，重新启动并恢复为干净的初 始，中间状态。常见的内部状念清理手段有清除缓冲序列、内存垃圾收集、重新初始 化内核表、清理文件系统等。最简单、常见的软件抗衰措施是计算机的重新引导。 1 9 9 3 年，y h u a n g 设计的可重用软件容错构件已经被用于a t & t 、操作系统m l ， 它处理策略从本质上来说是反应式，只有当发生故障后，才采取相应处理措施。y h u a n g 等人在首次提出的软件衰退概念f 2 1 j 中，采用了一个基于连续时间马尔可夫链的 简单模型。s g a r g 等人在yh u a n g 的研究基础上提出了更细致的模型d 1 他们采用马 尔可夫再生随机p e t r i 网模型来描述并进行定量研究。在文献f 5 】中，s g a r g 等人开创 性地提出非马尔可夫模型，对基于事务处理型应用软件系统进行研究并以数据说碣。 a b o b b i o 等人则提出了一种细粒度模型来平滑软件衰退过程【2 8 1 。软件抗衰也是i b m 公司的e l i z a 计划中的一个重要研究方面。目前，i b m 提出了两种实现软件抗衰的方 硕士论文 法咿1 ：t s r ( t i m e - b a s e ds o r w a r er e j u v e n a t i o n ) 和s s rf s y m p t o m - b a s e ds o f t w a r e r e j u v e n a t i o n ) 。前者主要参照以往系统发生故障的时间，设定近似的软件抗袁周期，由 系统根据周期自主地重启；后者则运用了智能化的方法，设计了一组s r a ，实时监测软 件系统资源的馒用情况，决定是否采取抗衰措施。 在国内，也有机构开始关注该方向的研究。其代表是南京大学刚刚启动的国家自 然科学基金项目“软件抗衰和自愈技术研究”。 本文针对软件衰退引起的系统性能下降，采用了系统性能的异常检测方法，根据 系统资源的占用情况，对提取的系统性能属性进行定量分析，实时监测系统的性能状 况。 1 2 课爱来漂 本课题属于计算系统性能保持关键技术研究的一个子课题，源于国家自然科学基 金( n o 6 0 2 7 3 0 3 5 ) 。 1 , 3 本文的主要工作 信息技术的飞速发展在维护计算系统性能方面引发了新的研究方向，即自主计 算。让计算系统在运行时刻能自主地维持其高性能，这种认识将彻底改变目前对系统 研制的做法，对计算系统需要的高可信赖、高性能提供有力的保证。实现系统的抗衰 退能力可以提高计算系统的自主性。本文提出的系统性能异常检测算法对提取的系统 性能属性进行定量分析，检测系统何时出现异常。 本文做了以下的工作： 1 在阅读了大量的中外文参考文献后，总结了系统性能异常检测的基本知识， 为想要了解该领域的人提供了资料。 2 将现有的可以用于性能异常检测的算法分成了四类( 基于统计的、基于数据 挖掘的、基于机器学习的、基于人工免疫系统的) ，分别对每一类中的某一个算法迸 行了分析。 3 针对性能异常检测的具体问题，采用了一般的异常检测算法，提出了一种多 阶段聚类算法，它将凝聚的层次聚类和其它的聚类技术进行集成。在第一阶段基于密 度进行初次聚类，通过距离矩阵计算每一个数据点的密度及其相应的密度集合，然后 将密度最大的数据点及其密度集合中的元素形成一个簇，重复此过程直到数据集为 空；在第二阶段基于相似度进行再次聚类，首先计算每一个簇之间的相似度，然后将 相似度最大的两个簇合并成一个新的簇，重复此过程直到满足终止条件为止。还给出 了系统性能异常检测的模型以及检测的算法。实验结果表明该算法具有较好的检测性 4 南京理工大学硕士学位论文 计算系统性能异常捡谢算法的研究与实现 能。 4 对存在类条件独立假设的朴素贝叶斯吩类器进行了改进，探讨了通过搜索属 性之间的依赖性来改进分类器的方法，从而提出了两种改进的方法，分别为前向选择 属性方法和后向消去属性方法。首先计算任意两个不同属性之间的依赖度，前向选择 属性方法用依赖度较小的属性对属性子集进行初始化，然后逐渐增加属性直到满足一 定的条件为止；而后向消去属性方法先将依赖度较大的属性从属性集中删除，用剩余 的属性对属性子集进行初始化，然后逐渐删除属性直到满足一定的条件为止。实验结 果表明这两种方法均能提高分类器的分类精确度，但是前向选择属性方法能更大程度 地改进朴素贝叶斯分类器的分类性能。 5 对多阶段聚类算法和改进的贝叶斯分类器进行了比较，得出了各自的优缺点 和适用范围。 1 4 本文的组织鳍柄 第一章：介绍了性能异常检测算法；分析了进行系统性能异常检测的必要性；同 时介绍了本课题的来源，本文的主要工作和组织结构。 第二章：对现有的可以用于性能异常检测的算法进行了分类，对每一类中的某一 个算法进行了分析。 接下来的两章是本文的重点。 第三章；简要介绍了聚类的概念和主要的聚类分析方法，针对性能异常检测的具 体问题，采用一般的异常检测算法，提出了一种新的聚类算法，即多阶段聚类算法， 该算法将基于密度的聚类方法和基于相似度的凝聚层次聚类方法进行集成，形成多阶 段聚类。最后进行实验，证明算法的有效性。 第四章：简要介绍了贝叶斯定理和朴素贝叶斯分类器，基于朴素贝叶斯分类器存 在类条件独立的假设，提出了两种改进朴素贝叶斯分类器的方法，给出了计算属性之 间依赖性的方法以及如何进行属性选择。最后进行实验，证明算法的有效性。 第五章：对本文所做的工作进行了总结，并展望了未来的研究方向。 1 5 本章小结 构。 本章以概要的方式介绍了论文背景，课题的来源，以及本文的主要工作和组织结 性能异常检测算法研究硕士论文 2 性能异常检潮算法研究 2 1 性能异常检潮概述 异常检测被用来发现小的模式，即数据集中间显著不同于其它数据的对象。下面 给出了异常的几种不同的定义，h a w k i n s t 3 0 给出了异常的本质住的定义：异常是在数 据集中与众不同的数据，使人怀疑这些数据并非随机偏差，而是产生于完全不同的机 制。聚类算法对异常的定义：异常是聚类嵌于其中的背景噪声。异常检测算法对异常 的定义：异常是既不属于聚类也不属于背景噪声的点，他们的行为与正常的行为有很 大不同。 在异常检测中常用的测量参数包括：窜计事件的数量、间隔时间、资源消耗情况 等。d e n n i n 9 1 6 提出了用于异常检测的5 种统计模型： ( 1 ) 操作模型，该模型假设异常可通过测量结果与一些固定指标相比较得到， 固定指标可以根据经验值或一段时间内的统计平均得到； ( 2 ) 方差，计算参数的方差，设定其簧信区间，当测量值超过簧信区间的范围 时表明可能存在异常； ( 3 ) 多元模型，操作模型的扩展，通过同时分析多个参数实现检测： ( 4 ) 马尔柯夫过程模型，将每种类型的事件定义为系统状态，用状态转移矩阵 来表示状态的变化，若对应于发生事件的状态转移矩阵概率较小，则该时间可 能是异常事件； ( 5 ) 时间序列模型，将事件计数与资源耗用根据时间排成序列，如果一个新事 件在该时间发生的概率较低，则该事件可能是异常事件。 异常检测可以应用在入侵检测、电信和信用卡欺骗、贷款审批、气象预报、金融 领域和客户分类等领域中。本文中所讨论的性能异常检测主要应用于系统性能保持和 软件抗衰方面，它的作用就在于建立一个模型或规则库来正确的分类系统性能异常状 况，性能异常检测算法与一般的异常检测算法的不同之处在于必须应对高度变化的系 统内外部环境变化带来的概念迁移，也就是正常或异常定义的变化。 一般来说性能异常检测是一个= 元分类问题，但是每一类都可以进一步划分成若 干的层次( 与标准的距离来衡量) 来表明不同的情况( 比如说系统性能异常有不同的 等级，采用不同的恢复操作) ，为自我管理提供不同的决策策略。 6 南京理工大学硕士学位论文 计算系统性能异常检测算法的研究与实现 2 2 现有性能异常检一算法分析 目前可以用于性能异常检测的算法有很多，比如：基于统计的异常检测算法、基 于数据挖掘的异常检测算法、基于机器学习的异常检测算法以及基于人工免疫系统的 异常检测算法。本文对这四类算法分别就其中一个具体的算法进行分析。 2 2 1 基于机器学习的异常检涓算法 决策树学习是一种基于机器学习的异常检测算法。它是种逼近离散值目标函数 的方法，在这种方法中学习到的函数被表示为一棵决策树。学习得到的决策树也能再 被表示为多个i f 也e n 的规则，以提高可读性。 决策树通过把实例从根结点排列到某个叶子结点来分类实例，叶子结点即为实例 所属的分类。树上的每一个结点说明了对实例的某个属性的测试，并且该结点的每一 个后继分支对应于该属性的一个可能值。分类实例的方法是从这颗树的根结点开始， 测试这个结点指定的属性，然后按照给定实例的该属性值对应的树枝向下移动。然后 这个过程在以新结点为根的子树上重复。 基本的决策树学习算法，大致相当于i d 3 算法。基本的i d 3 算法通过自顶向下构造 决策树来进行学习。构造过程是从“哪一个属性将在树的根结点被测试? ”这个问题 开始的。为了回答这个问题，使用统计测试来确定每一个实例属性单独分类训练样例 的能力。分类能力最好的属性被选做树的根结点的测试。然后为根结点属性的每个可 能值产生一个分支，并把训练样例排列到适当的分支( 也就是，样例的该属性值对应 的分支) 之下。然后重复整个过程，用每个分支结点关联的训练样例来选取在该点被 测试的最佳属性。这形成了对合格决策树的贪婪搜索，也就是算法从不回溯重新考虑 以前的选择弘j 。 i d 3 算法的核心问题是选取在树的每个结点要测试的属性。我们希望选择的是最 有助于分类实例的属性。i d 3 算法在增长树的每一步使用信息增益标准从候选属性中 选择属性。 通过观察i d 3 算法的搜索空间和搜索策略，可以看出这个算法的优势和不足。 i d 3 算法中的假设空间包含所有的决策树，它是关于现有属性的有限离散值函 数的一个完整空间。因为每个有限离教值函数可被表示为某个决策树，所以i d 3 算法 避免了搜索不完整假设空间( 例如那些仅考虑舍取假设的方法) 的个主要风险：假 设空间可能不包含目标函数。 d 3 算法在搜索的每一步都使用当前的所有训练样例，以统计为基础决定怎样 改进当前的假设。这与那些基于单独的训练样例递增做出决定的方法不同。使用所有 7 性舱异常检测算法研究 硕士论文 样例的统计属性( 如：信息增益) 的一个优点是大大降低了对个别训练样例错误的敏 感性。因此，通过修改i i ) 3 算法的终止准则以接受不完全拟合训练数据的假设，它可 以被很容易地扩展到处理含有噪声的训练数据。 当遍历决策树空间时，1 d 3 仅维护单一的当前假设。因为仅考虑单一的假设， i d 3 算法失去了所有一致假设所带来的优势。例如，它不能判断有多少个其它的决策 树也是与现有的训练数据一致的，或者使用新的实例查询来最优地区分这些竞争假 设。 基本的i d 3 算法在搜索中不进行回溯。每当在树的某一层次选择了一个属性进 行测试，它不会再回溯重新考虑这个选择。所以，它易受无回溯的爬山搜索中匏常见 风险影响：收敛到局部最优的答案，而不是全局最优的【2 l 。 决策树学习还存在一些实际的问题，包括： ( 1 ) 过度拟合数据。当决策树创建时，由于数据中的噪声和孤立点，许多分枝 反映的是训练数据中的异常。剪枝方法处理这种过分适应数据问题。通常，这种方法 使用统计度量，剪去最不可靠的分枝，这将导致较快的分类，提高树独立于测试数据 正确分类的能力。有两种常用的剪枝方法：在先剪枝方法中，通过提前停止树的构 造( 例如，通过决定在给定的节点上不再分裂或划分谢练样本的子集) 而对树“剪枝”。 一旦停止，节点成为树叶。该树叶可能持有子集样本中最频繁的类，或这些样本的概 率分布。如果在个节点划分样本将导致低于预定义阈值的分裂，则给定子集的进一 步划分将停止。然而，选取一个适当的阙值是困难的。较高的阈值可能导致过分简化 的树，而较低的闽值可能使得树的化筒太少。第二种方法是后剪枝方法，它由“完 全生长”的树剪去分枝。通过删除节点的分枝，剪去树节点。代价复杂性剪枝算法是 后剪枝方法的一个实例。最下面的未被剪枝的节点成为树叶，并用它先前分枝中最频 繁的类标记。对于树中每个菲树叶节点，算法计算该节点上的子树被剪枝可能出现的 期望错误率。然后，使用每个分枝的错误率，结合沿每个分枝观察的权重评估，计算 不对该节点剪枝的期望错误率。如果剪去该节点导致较高的期望错误率，则保留该子 树：否则剪去该子树。产生一组逐渐被剪枝的树之后，使用一个独立的测试集评估每 颗树的准确率，就能得到具有最小期望错误率的决策树。我们可以根据编码所需的二 进位位数，而不是根据期望错误率，对树进行剪技。“最佳剪技树”使得编码所需的 二进位最少。这种方法采用最小描述长度( m d l ) 原则。这一原则遵循的理念是最 简单的解是最期望的。不像代价复杂性剪枝，它不需要独立的样本集。也可以交叉使 用先剪枝和后剪枝，形成组合式方法。后剪枝所需的计算比先剪枝多，但通常产生更 可靠的树。 ( 2 ) 基本豹决策树算法要求所有的属性是分类的或离散的。可以修改该算法， 允许属性具有整个离散区间或连续值。在这种属性a 上的测试导致两个分枝，对应于 改进的贝叶斯分类器 硕士论文 条件a s v 和a v ，其中v 是a 的某个数值。给定a 的值v ，确定v 时考虑v 1 个可能 的分割e 通常，考虑每对相邻值的中闻值。如果这些值已预先排序，则只需要扫描一 次这些值。 ( 3 ) 信息增益度量有倾斜，它倾向于适合具有许多值的属性。已经提出了一些 替代的方法，如增益率，它考虑每个属性值的概率。还有一些其它选择度量，包括 g i n i 索引，z 2 相依表统计和g - 统计。 ( 4 ) 已经提出了许多方法来处理空缺的属性值。例如，属性a 的空缺值或未知 值可以用a 的最常见值替代。作为选择，属性a 的外观上的信息增益也可以按a 的值 为未知的样本比例减少。这样，具有缺少值的样本“片段”可以在溺试节点被划分到 多个分枝。其它方法可能寻找a 的最或然值，或使用a 和其它属性的已知联系f ”。 通过重复地将数据划分成越来越小的部分，决策树可能面临碎片问题。碎片是指 个给定分枝中的样本数太小，没有统计意义。解决该问题的一种方法是将分类属性 值分组，树节点可以测试个属性值是否属于给定的集合，如4 f q ，岛，口。 。另 种替代是创建二叉决繁树，其每个分技拥有一个属性上的布尔测试。二叉树导致较 少的数据碎片，些实验研究发现二叉决策树比传统的决策树更精确。 l o h & s h i h t 4 2 1 提出了一种快速的、无偏差韵、有效的、统计树q u e s t ( q u i c k ， u n b i a s e d ，e 臌c i e n t ，s t a t i s t i c a lt r e e ) 。它是一种可以生成类似于c & r t p l j 的二叉决 策树的树结构分类算法，生成二又树的原因是因为二叉树允许使用诸如剪枝、直接终 止舰则以及取代分枝这些技术。在每一次分裂过程中，使用a n o v af t e s t 或l e v e n e s t e s t ( 用于顺序的以及连续的预测值) 或p e a r s o n se h i - s q u a r e ( 用于离散预测值) 计算 预测变量和目标变量之间的相关性。如果目标变量是多项式，使用2 平均聚类产生2 个超类。与目标变量具有最大相关性的预测值被选择用于分裂，应用二次判别式分析 ( q d a ) 为预测变量寻找最佳的分裂点。递归地重复此过程直到引发一条终止规则。 c h a i d 4 2 】和c & r t 算法在树生成的过程中间时对变量选择和分裂选择进行处理。而 q u e s t 分别对它们进行处理。众所周知，彻底的搜索方法比如c & r t 倾向于选择具有较 多离散值的变量，在树的生成过程中能够提供更多的分裂，这会导致模型中存在偏差， 降低了结果的一般性；c & r t 的另一个局限是搜索分裂的计算开销。q u e s t 方法可以解 决这些问题，可以证 , q q a e s t 在变量选择的偏差和计算_ 歼销方面比彻底的搜索方法要 来得好。尽管如此，当使用一元分裂时，在分类精确度、分裂点的可变性以及树的大 小方面不存在明显的优势。 2 2 2 基于数据挖掘的异常检灏算法 遗传算法是种基于数据挖掘的异常检测算法。它是根据d a r w i n 进化论和m e n d e l 性能异常检测算法研究 硕士论文 的遗传学说生物进化思想而启发得出的一种全局优化算法。目前遗传算法已经得到广 泛的应用，如自动控制、数据挖掘、计算机科学、工程设计和神经网络等领域。 遗传算法的基本思想可归为两点；1 ) 将物种进化的理论用于求问题的解，物种 的进化又可分为遗传和变异两个方面 2 ) 只有最适合环境的物种才能保留下来，因 而经反复求解后可以得到最佳的解。 遗传算法按照一定的规则生成经过基因编码的初始群体，然后从这些代表问题的 可能潜在解的初始群体出发，挑选适应度强的个体进行交叉和变异，以期发现适应度 更佳的个体，如此一代代地演化，得到一个最优个体，将其经过解码，该最佳个体则 对应问题的最优解或近似最优解。 遗传算法的特点如下：与传统的确定性算法不同，遗传算法只对系统的输出进 行适应度评判，与系统的内部复杂性无关，是一种黑箱方法。并行性和对全局信息 的有效利用能力是遗传算法的显著特点。传统的优化方法采用的是确定性计算法 则，而遗传算法是一类基于概率的迭代优化算法，个体间的交叉及个体自身的复制和 变异等都存在着随机性，因此遗传算法可以克服使用确定性计算的传统优化方法对噪 声比较敏感的缺点，所以遗传算法具有更高的强壮性。遗传算法在解空间内进行充 分的搜索，但并不是盲目地瞎碰，而是一种启发式搜索，其搜索时耗和效率往往优于 其它优化方法l 。 遗传算法最初用于优化问题，在分类问题方面的应用还处于“原型”阶段。用遗 传算法进行分类时，一般地，遗传学习开始如下：创建一个出随机产生的规则组成的 初始群体。每个规则可以用一个二进位串表示。如果个属性具有k ( k 2 ) 个值，则 可以用k 个二进位对该属性的值编码。类可以用类似的形式编码。根据适者生存的原 则，形成由当前群体中最适合的规则组成新的群体，以及这些规则的后代。典型情况 下，规则的适合度用它对训练样本集的分类准确率评估。后代通过使用诸如交叉和变 异等遗传操作来创建。在交叉操作中，来自规则对的子串交换，形成新的规则对。在 变异操作中，规则串中随机选择的位被反转。由先前的规则群体产生新的规则群体的 过程继续，直到群体p “进化”，p 中的每个规则满足预先指定的适合度阈值。最后用 口中的规则对新的样本进行分类。 遗传算法的有效性主要来自于遗传操作，即选择、交叉和变异，尤其是交叉操作， 在遗传算法中起着核心作用。 传统的选择方法( 适应度比例法) 存在超强群体和封闭竞争的问题。超强个体问 题即在群体中可能存在一个或几个个体的适应度值远大于其它串的适应度值，在繁殖 中占据了完全的主导地位，因此可能经过几次迭代处理后，求解过程就收敛于局部最 优点。封闭竞争是指群体中个体的结构和适应度值都很接近，因此交叉后子代变化也 不大，这就使求解过程变得极为缓慢以致停顿，因此无法进行有效的搜索，难以发现 i o 旦室墨王r 犬堂堡生竺垡堡苎 塑苎墨竺丝塑墨堂垒型! 望堕堡垒兰壅墨 全局最优解，有时也将这种现象称作早熟收敛f 3 】。 因此，i n u ek o n y a f 3 2 1 对比例选择做了进一步的修改：个体的适应度只用来确定它 们之间的排列顺序，适应度值越大，个体在序列中的位置( 记作p o s ( i ) ) 越高，个体 成为父代的概率和其在序列中的位置成比例。 尸( f ) = p o s ( i ) ( ( n + 1 ) ( n 2 ) ) n ：群体中个体的数目 ( 2 2 1 ) 在应用这种方法时不需要准确的计算参数矢量的误差。如果满足它们比较的标 准，这种方法已经足够了，它意味着能够戏剧性地提高算法的速度，因为( 如果我们 可以找到一种快速比较矢量的方法) 它没有必要为进行比较的两个矢量计算训练集中 每一对输入组合的结果( 或误差) 。 上述讨论的选择方法不能百分之百地阻止群体中最好的个体意外地消失，这是因 为后代不是父代的一个拷贝；它是两个父代的组合。因此当最好的个体出现在下一代 中时，要将它保存起来，当然它也能被选作为父代。这是一种最优策略，即保证在每 一代中最好的个体的适应度增加或在最坏情况下保持不变。 一个好的选择策略一般应在迭代的初始阶段将一些明显不合理的个体淘汰掉，以 利于在其后进行的处理过程中能够得到更好的结果：而在迭代进行到一定的阶段后， 又要适当地保留差异不大的个体，以便在以后能够产生更多的寻优方向来更好地求 解，以免使过程落入局部最优而无法得到更好的结果。 遗传算法的搜索能力主要是由选择和交叉赋予的。交叉可以把两个个体中优良的 模式传递到子代中，使子代具有优于其父辈的性能，如果交叉后得到的子代的适应度 不佳，则可以在此后的选择过程中将其去除。因此，交叉算子是遗传算法中的最主要 的算子。寻优的搜索过程主要是通过交叉算子来实现的。因此，交叉算子在遗传算法 的迭代运算中发生的概率比较大。交叉并不是在每一对个体上都发生的，它的发生频 率由交叉概率决定。交叉操作在遗传算法中起至关重要的全局搜索作用，有效的交叉 策略可保证遗传搜索的速度和质量。 变异算子则保证了算法能搜索到问题解空间的每一点，从而使算法具有全局寻 优，它进一步增强了遗传算法的能力，变异本身是一种随机搜索，然而与复制，交叉 算子结合在一起，就能避免由于复制与交叉算子而引起的某些信息永久性丢失，保证 了遗传算法的有效性1 3 。 传统的单点交叉方法存在一个问题，它不满足一个重要的生物进化模型的标准： 后代和父代之间具有一定的相似性。通过对参数矢量组成部分的分离产生了上述的问 题。所以在许多遗传应用中，分离的位置被限制在一定的范围，这意味着，不仅是搜 索空间的间隔受限制，而且分离也要动态地受到限制。h l = l l ek o n y a 【3 2 】提出了一种消 改进的贝叶斯分类器 硕士论文 除这种限制的方法，其中后代矢量中第j 个组成部分来自于父代矢量中第j 个组成部分 的特殊线性组合( s p e c i a l l i n e a r c o m b i n a t i o n ，简称s l 。c ) ，据此c ( 歹) 可以由式( 2 2 2 ) 计算， c ( j ) = e l a ( j ) + c 2 b ( j ) ( 2 2 2 ) 其中，c ( j ) 式表示后代矢量中第j 个组成部分，a ，b 表示父代矢量，c 1 取0 5 至1 1 1 之间 的实数，c 2 = l c 1 。为每一组后代分别产生一个随机数k ( i ) ，当，k ( i 】时，c f ，) 由 式( 2 2 2 ) 可得：当j r ( i ) 时，式( 2 2 2 ) 中q 和c ，的角色互换一下。这样后代中 第1 个到第r ( 0 个组成部分将和父代中相应的部分比较相似，第k ( i 1 + 1 个部分到第 s 个部分将和父代中相应的部分比较相似。s l c 交叉方法可以更加灵活地扫描搜索空 间，它还具有更强地调整参数矢量的能力。尽管如此，它不能证明最优解位于由最初 的s 个参数矢量定义的s 维矩形的几何中心。而是在其附近。因此从实数区间 1 q ，l + q 】 中取c l 的值可能会有用，其q b o q u ) 进行评估。若有些卵( h ) 足够小，那q 就 是不一致的，从而拒绝正面假设。一个反面假设圩，它描述o ，来自另一个分布g ，这 个结果依赖如何选择f 模型，因为o i 在一个模型为异常数据而在另一个模型中可能就 是有效数据。 在决定( 不一致) 测试效能时，反面模型也是非常重要的。也就是当o i 的确为异 常数据时正面假设被拒绝的概率。有几种类型的反面分布： ( 1 ) 内在反面分布。这 种情况下，正面假设认为所有来自分布f 的对象均被拒绝；而反面假设则描述所有对 象来自分布g 却成立：h ：d ，g ，其中i = l 2 ，h 。f 和g 可能是不同的分布，或同 个分布而具有不同的参数。对g 的分布形式有所规定以使其有能力产生异常数据。如： 它可以有不同的均值或分布。 ( 2 ) 混合反面分布。混合反面假设认为不一致的值在 分布f 中不是异常数据，但被来自其它分布的数据所污染，这种情况下，反面假设就 是：一h ：o i f 1 一五1 f + 2 g ，其中f _ 1 ，2 ，n 。( 3 ) 滑动反面分布。这种反面假设认为 所有( 除了较少部分外) 对象独立来自初始分布f ( 具有参数，矿) ；剩余对象独 立来自修改后的分布f ( 其中的参数有所变化) 。 有两种检测异常数据的基本过程：( 1 ) 块过程，这种情况下，要么所有被怀疑的 改进的贝叶斯分类器 硕士论文 对象均作为异常数据；要么所