（计算机软件与理论专业论文）连续属性离散化方法的研究及其在入侵检测中的应用.pdf

摘要随着计算机及网络技术的高速发展和不断应用，数据挖掘和知识发现技术应运而生，并引起了信息产业界的极大关注。同时，入侵检测技术作为网络安全措施的一个环节也日趋重要，并成为动态网络安全技术中核心技术之一。关联规则作为一种活跃的重要知识发现技术，可以从入侵检测数据中发现正常和异常的行为模式，并且能有效地检测已知入侵。因此，研究关联规则的高效算法有利于提高入侵检测的准确性和时效性通常关联规则都是基于交易数据库的，然而，目前数学角度上的数据集合理论基础，它只能处理离散数据，现实中大量的实型数据亟待进行离散化，因而，关联挖掘的同时，研究数据表中连续属性的离散化具有重要的理论和现实意义。在关联算法应用上，由于存在有些数据呈连续的，不符合关联挖掘的条件，往往需要对这些数据进行离散化。对于传统的离散化，大多数的离散化方法没有考虑不同连续属性离散化结果间的互补性和相关性，每个属性的离散化过程都是独立进行的，往往会改变信息系统的不可分辨关系，容易产生不合理和冗余的断点。在入侵检测数据中，大量的网络数据中存在许多属性的连续，导致了单属性离散化效率低下，大量断点的产生使得离散效果不明显，往往趋于不合理和冗余。针对传统离散化问题，本文提出了基于频数监督断点的连续属性的离散化方法，实验结果表明该算法所产生的断点不仅符合实际数据分布，让断点更趋于合理、精练。在多属性的离散化方法中，提出了一种基于粗糙集的动态多属性离散方法。该方法不仅有效降低了断点的冗余性，与相关研究对比其合理性和离散精度也得到了提高，这对入侵检测数据进行关联挖掘的预处理具有一定意义。本文的研究成果，对于将离散化方法进行入侵检测准备数据的预处理及其辅助关联挖掘技术应用在入侵检测领域，具有一定的发展潜力和效益。关键词：离散化：关联规则；入侵检测r e s e a r c ho nd i s c r e t i z a t i o nt e c h n o l o g ya n di t sa p p l i c a t i o no ni n t r u s i o nd e t e c t i o na b s t r a c tw i t hq u i c kd e v e l o p m e n ta n da p p l i c a t i o no fc o m p u t e ra n dn e t w o r kt e c h n o l o g y , d a t am i n i n gt h a tc o m e si n t oe x i s t e n c ea st h es i t u a t i o nr e q u i r e si sg r e a t l yc o n c e m e d m e a n w h i l e ，i n t r u s i o nd e t e c t i o ns h o w si t sg r o n gv i t a l i t y a s s o c i a t i o nr u l ei ss u c ha ni m p o r t a n ta n da c t i v et e c h n i q u et h a ti tc a l ld i s c o v e rt h eb e h a v i o rp a r e mb e t w e e nn o r m a la n da b n o r m a ld a t a t h u s ，r e s e a r c ho fa s s o c i a t i o nr u l ei si nf a v o ro fi m p r o v i n gt h ea c c u r a c ya n dt i m e l i n e s s g e n e r a l l y , a c c o r d i n gt oc u r r e n ts e tt h e o r yi nm a t h ，t h el a r g er e a ln u m b e r sn e e dt ob ed i s c r e t i z e ds ot h a tt h i ss t u d yh a si m p o r t a n tt h e o r e t i ca n dp r a c t i c a ls i g n i f i c a n c e f o rt h ed i s e r e t i z a t i o n ，t h ec o m p l e m e n t a r i t i e sa n dr e l a t i v i t i e sb e t w e e nd i f f e r e n ta t t r i b u t e sa r en o tt a k e ni n t oa c c o u n ti nm o s td i s c r e t em e t h o d s e v e r yp r o c e s s i n gt e n d st op e r f o r mr e l a t i v e l ys ot h a ti ta l w a y sc h a n g e st h ee q u i v a l e n tr e l a t i o na n dg e n e r a t e su n r e a s o n a b l ea n dr e d u n d a n tb r e a k p o i n t s a m o n gi dd a t a , c o n t i n u o u sa t t r i b u t e sa 他s oa b u n d a n tt h a ts i n g l ea t t r i b u t ed i s e r e t i z e di n e f f i c i e n t l ya n dt h er e s u l t sw i t hm a n yb r e a kp o i n t so r e nl e a dt om a k ei r r a t i o n a la n dr e d u n d a n t t h i st h e s i sp r e s e n t sa na l g o r i t h mw i t ht h er e s u l tt h a tt h eb r e a k p o i n t sa r en o to n l yi nl i n ew i t ha c t u a ls t a t i s t i c a ld i s t r i b u t i o n ，b u ta l s ot h e y 棚m o r er e a s o n a b l ea n dr e f m e d t h em u l t - a t t r i b u t ea l g o r i t h ms h o w st h er e d u c e dr e d u n d a n c y , w h i c hc o m p a r e dw i t hr e l a t e ds t u d i e si t sr a t i o n a l i t ya n da c c u r a c yh a sb e e ni m p r o v e d r e f e r i n gt ot h ea s p e c t so fh o wt oa p p l yt h ed i s c r e t i z a t i o nm e t h o di n t oi n t r u s i o nd e t e c t i o nd a t aa n dh o wt od i s c r e t i z a t i o na s s i s t sa s s o c i a t i v et e c h n i q u et 0b ea d o p t e di n t oi n t r u s i o nd e t e c t i o n ，t h er e s u l t so f r e s e a r c hh a si t sd e v e l o p m e n tp o t e n t i a la n de f f e c t i v e n e s s k e y w o r d s ：d i s c r e t i z a t i o n ；a s s o c i a t i o nr u l e ；i n t r u s i o nd e t e c t i o n厦门大学学位论文原创性声明本人呈交的学位论文是本人在导师指导下，独立完成的研究成果。本人在论文写作中参考其他个人或集体已经发表的研究成果，均在文中以适当方式明确标明，并符合法律规范和厦门大学研究生学术活动规范( 试行) 。另外，该学位论文为() 课题( 组)的研究成果，获得() 课题( 组) 经费或实验室的资助，在() 实验室完成。( 请在以上括号内填写课题或课题组负责人或实验室名称，未有此项声明内容的，可以不作特别声明。)声明人( 签名) ：林盯鹳咿咱年泰月。1 日厦门大学学位论文著作权使用声明本人同意厦门大学根据中华人民共和国学位条例暂行实施办法等规定保留和使用此学位论文，并向主管部门或其指定机构送交学位论文( 包括纸质版和电子版) ，允许学位论文进入厦门大学图书馆及其数据库被查阅、借阅。本人同意厦门大学将学位论文加入全国博士、硕士学位论文共建单位数据库进行检索，将学位论文的标题和摘要汇编出版，采用影印、缩印或者其它方式合理复制学位论文。本学位论文属于：|( ) 1 经厦门大学保密委员会审查核定的保密学位论文，于1 朋年a 蜩式日解密，解密后适用上述授权。() 2 不保密，适用上述授权。( 请在以上相应括号内打搿 或填上相应内容。保密学位论文应是已经厦门大学保密委员会审定过的学位论文，未经厦门大学保密委员会审定的学位论文均为公开学位论文。此声明栏不填写的，默认为公开学位论文，均适用上述授权。)声明人( 签名) ：荆巳以辑1 尸1 钆b 月武日第一章绪论第一章绪论本章首先介绍课题的研究背景和意义，阐述了数据挖掘技术、入侵检测、离散化技术国内外研究现状和发展方向。介绍研究可能存在的问题，并概述了本文的主要研究内容和特色，包括本文组织结构。1 1 课题研究背景与意义纵观计算机与网络发展的过去几十年，在网络上所呈现的计算机安全事件层出不穷。网络自身的快速发展，加上各国计算机体系结构不断地相继受到不同程度的攻击，整个世界计算机安全已受到严峻的威胁和挑战。入侵检测i d( i n t r u s i o nd e t e c t i o n ) 成为了安全积极领域上一个值得发展的研究课题n 。在网络安全技术中，入侵检测是一项新的安全技术，它是继防火墙、信息加密等方法之后的新一代安全保障。入侵检测作为一种积极主动的信息安全技术，提供了对内部攻击、外部攻击和误操作的实时保护，在网络系统受到危害之前拦截和响应入侵。目前大多数网络入侵检测系统i d s ( i n t r u s i o nd e t e c t i o ns y s t e m ) 都是通过手工定制的方式建立起来的，尤其是用于识别判断入侵行为的检测知识，由于缺少有关入侵检测的最新知识，以致不能准确发现未知的入侵或攻击行为，且自身存在传统上的不足，如漏报，误报等，没有办法对原有存在的入侵原型在大量数据的监测中准确地做出判断。利用数据挖掘( d a t am i n i n g ) 技术对网络数据加以分析，总结出一些正常模式，用来进行异常检测，将有助于提高入侵检测系统的准确性和完备性目前，数据挖掘的主要技术有关联规则、聚类、粗糙集、神经网络等方面引。关联规则( a s s o c i a t i o nr u l e s ) 作为数据挖掘上一个重要技术，它表示数据库中一组对象之间的某种关联关系的规则。把关联规则应用于入侵检测，可以有效提高正常模式和入侵规则的科学性和可靠性。目前采用关联规则技术的方法建立入侵检测系统已经成为研究的一个热点关联规则通过它对数据集的分析处理，可以挖掘出数据集中项之间的有趣联系。挖掘的对象不仅是数据源、文件系统，也包括诸如w e b 资源等任何数据集连续属性离散化方法的研究及其在入侵检测中的应用合当前计算机中数据通常保存在许多数据库中，这数据库中数据属性不外乎两种类型喳1 ：一种是离散的属性，也称是符号的、或名称的，类别的属性这些属性是用少量的离散值表示的，例如颜色、形状等；另一种是连续属性，也称是实数的、或有序的、或数值的属性，这些属性表示了对象的一种可测量的属性，其值取自一段连续的区间。连续属性的离散化( d i s c r e t i z a t i o n ) 即实型空间向整型空间的映射，是数据挖掘过程中预处理阶段的步骤之一，由于它在减少后继算法的时空复杂度、提高系统的鲁棒性上的重要作用而被广泛研究嘲t n 】，其离散化结果直接关系到后续的诸如关联规则挖掘的效率和准确性。在数据挖掘、机器学习领域中，离散化处理通常被当作一种边缘性的辅助工作而没有受到应有的重视。然而，现实世界的许多应用中常常涉及连续的数值属性，目前许多的入侵检测技术却要求所处理的属性取离散值，比如基于关联分析的入侵规则挖掘。对待处理数据中的连续属性进行离散化，具有如下的意义：( 1 ) 各种常见机器学习方法，一般要求输入离散化的数据，才有较高的学习效率；( 2 ) 用数据库作为知识源，把逻辑学、统计学、机器学习、模糊数学等学科成果综合到一起，进行从数据库中发现知识的研究，使得数据库不仅仅能任意查询数据，而且上升到对数据库中数据的整体特征的认识；( 3 ) 有利于数据库自身的增长和管理，而且大大提高了数据库的利用率：( 4 ) 有可能成为决策支持系统的基础，特别是使用模糊学和自然语言值，通过隶属云和语言原子模型来沟通定性分析和定量分析。1 2 国内外研究状况及存在问题将数据挖掘技术应用到入侵检测系统中，是把入侵检测看作一种数据分析的过程，可以对大量的网络安全数据进行智能化处理，发现各种异常行为，从而使入侵检测系统具有更好的自学习、自适应和自我扩展的能力。w e n k el e e 首先将数据挖掘技术应用于入侵检测嘲，目前国际上在该领域的研究很活跃。国内已有少数大学和研究单位在做将这方面的研究。比如中国科学院高能物理研究所计算中心提出了一种基于数据挖掘技术建立入侵检测系统的方法n 副：北京邮电大学交换技术与通信网国家重点实验室提出一种自适应的入侵检测系统框架n 引；西安交第一章绪论通大学计算机科学与技术系提出了一种自学习自完善功能的入侵检测模型，在模型中采用了移动a g e n t ，注重于移动a g e n t 的研究n 劓；中国科学院研究生院信息安全国家重点实验室提出了基于模式挖掘的用户行为异常检测的方法利用数据挖掘中的关联分析和序列模式挖掘技术对用户行为进行模式挖掘的方法n 钉，这些研究主要仍基于哥伦比亚大学w e n k el e e 的思路。目前国内外关于数据库入侵检测方面的研究还处于起步阶段，还没有形成适应性强、准确度高的数据库入侵检测系统，还有很大的研究空间。目前应用于入侵检测的方法主要是基于聚类、分类、关联规则和序列模式分析其中，关联规则挖掘技术的应用较为广泛，该领域的研究主要集中在挖掘算法、特征提取和离散化算法的优化设计上关联规则挖掘问题最早是由a g r a w a l 等人提出的“1 。目前已提出许多有效的挖掘算法，如a g r a w a l 等人提出的a i s 、a p r i o r i 和a p r i o r i t i d 等算法n 削；p a r k 等人提出的d h p ( d i r e c th a s h i n ga n dp r u n n i n g ) 算法等等。而关联规则的挖掘问题由s r i k a n t 等人于1 9 9 6 在文献n 射中提出，现已引起许多研究学者的极大关注入侵检测问题本身的模糊性和连续属性的离散化问题，m i s s i s s i p p i 州立大学的j i a n x i o n gl u 和s u s a nm b r i d g e s 等人将模糊逻辑引入入侵检测。采用模糊关联规则和模糊频繁情节算法挖掘审计数据，以期使入侵检测系统具有某种程度的智能性，从而减少误报。国内学者在基于关联规则的入侵检测研究中有代表性的研究成果包括：国防科技大学计算机学院宋世杰等人将a p r i o r i 算法进行扩展并用于入侵检测；中国科学院研究生院信息安全国家重点实验室连一峰等人对t e l n e t 会话中用户执行的s h e l l 命令序列进行挖掘，建立用户异常行为模型：武汉大学电子信息学院凌军等人提出并实现了一个基于规则的、层次化的智能入侵检测原型系统( r i d e s ) 连续属性的离散化是数据挖掘和机器学习的重要预处理步骤，直接关系到挖掘或学习的效果瓣3 。随着数据挖掘研究和入侵检测的发展，已经发展了很多处理离散型数据的算法，如决策树、关联规则等。对于连续型数据，则需要进行离散化处理。目前，已经出现许多离散化算法，其中主要有n a i v es c a l e r 。等宽，等频，信息熵等n 钆剐。此外还有，有等频方法、等宽方法、s l o w i n s k i 方法( s 方法) 、h u 方法( h 方法) 瞰3 、l e n a r e i k ( l 方法) 嘲等。但是这些方法需要人为地规连续属性离散化方法的研究及其在入侵检测中的应用定划分维数，或者预先给定一个参数。连续属性的最优离散化是一个n p 完全问题矧，作为数据挖掘和机器学习的重要预处理步骤，离散化方法的性能将对后续的数据挖掘任务产生直接影响，不好的离散化会导致一些关键信息的丢失或造成沉重的挖掘负荷。将关联规则技术应用于入侵检测无论在理论上还是在技术都是可行的，其技术难点主要在于如何根据具体应用要求，从有关安全的先验知识出发，提取出有效地反映系统特性的特征属性，应用合适的算法进行挖掘。目前将关联规则方法运用于入侵检测的研究工作，从总体上说还处于理论研究阶段，待解决的问题主要有：( 1 ) 数据预处理在一个信息系统中，对于信息缺省的对象一般无法归类。在信息缺省的情况下，不经过信息的预处理，直接建立知识发现的方法一个值得探索的问题。数据格式的标准化或量化。许多数据集中包括着复杂的数据类型，如关系数据、半结构化数据、非结构化数据、超文本数据和多媒体数据等等。从不同的格式或非格式地具有不同数据语义的数据源而来的数据集，对数据挖掘提出了新的挑战。通过检查与正常行为相违背的行为，异常检测能够发现一些新的未知的入侵，但由于其正常行为模型的建立完全依赖于对训练数据集中正常数据样本的学习，所以保证训练数据集的洁净性，即不包含任何异常数据。而实际上，要为系统的学习而收集这样一个洁净数据集往往是十分困难的，一旦出现入侵数据被误为正常数据出现在训练数据集中，必然导致该类入侵行为以及其变种都将被系统视为正常数据。( 2 ) 连续属性的离散化在保持数据在离散过程中的不可分辨关系和在一定程度上保证决策表原有分类结果的不变性的基础上，尽可能降低断点数量，并使所得到的断点不仅符合数据分布，又体现属性的内在知识背景。类别信息的判断应用是将监督式方法从而把类别的信息带到离散化的过程，类别信息在决策表中的决策属性这一列体现，是整个决策表的关键属性一般来说，描述不同对象特征的属性集是较大的但是对于信息系统分类的知识发现来说有些属性并不总是必要的。不重要的属性离散程度太低会产生不必要的断点，会影响后面整个多属性动态地离散化，使断4第一章绪论点产生冗余，通过知识简约( 即就是在属性中寻找一个最小的属性集，它能完全确定知识发现，也即由这个最小属性集确定的分类知识与用全体属性集确定的分类知识是相同的) 最终去除噪音数据。解决多值属性关联规则的一般方法为将属性的取值数量按一定的标准分成若干个区间段，然后将属性值转换为一个序对 ，这样就将多值属性关联规则挖掘问题转化为布尔型关联规则。将知识库中多个连续的属性进行动态离散化，不仅能够得到更好的断点结果，还能够从这些含有连续属性的数据库中取得较好的数据集。所以，属性的离散是数据处理的一个重要前提。( 3 ) a p r i o r i 关联挖掘关联挖掘问题提供了一条有效途径，但存在着明显的不足：一是造成明显的边界问题，即在挖掘过程中，对靠近区间边界的值的作用，要么过分强调，要么被忽略：二是划分的区间可能不简明或无实际意义，不利于专家理解和信息抽取。产生以上问题的实质在于客观世界的复杂性和多样性，难以用精确的方式进行处理。事实上，关联规则的兴趣度最小支持度和最小置信度并不能确保所挖掘出的关联规则都是用户所感兴趣的，其中可能包含许多冗余、无意义的关联规则，对关联规则兴趣度进行研究就显得十分必要，目前文献嘲等有一些初步的结果。对于关联规则挖掘算法的交互性馐钉，目前一般过程是在用户规定最小支持度和最小置信度等参数之后，通过扫描数据集找出所有的频繁项目集，并根据频繁项目集生成关联规则，最后将挖掘出的关联规则提交给用户。如果用户不满意所得到的挖掘结果，则需要修改最小支持度、最小置信度等参数并再次运行关联规则挖掘算法。用户要得到满意的结果可能需要上述过程的多次反复。因此需要较长时间，关联规则挖掘算法与用户的交互性也是一个值得关注的问题。( 4 ) 性能与效率数据挖掘算法在大型数据库中的运行时必须是可预计和可接受的。许多现有的数据挖掘算法往往适合常驻内存的、小数据集的数据挖掘，而大型数据库中存放了t b 级的数据有数据无法同时导入内存。所以从数据库观点，有效性和可伸缩性是实现数据挖掘系统的关键问题。随着数据库的规模不断增大，不仅加大了挖掘算法的搜索空间，而且也增加了盲目挖掘的可能性。因此必须结合领域知识去提取与我们发现任务有关的数据，删除无用的数据，有效地降低问题的维数，连续属性离散化方法的研究及其在入侵检测中的应用提高挖掘算法的效率。( 5 ) 关联规则挖掘技术与入侵检测的融合关联规则挖掘技术的研究吸引了许多其它领域的研究者从事该问题的研究，使得关联规则挖掘可以吸收其它领域的研究成果。如关联规则挖掘技术与数据仓库等数据库技术的融合将推动关联规则挖掘技术进一步实用化，关联规则与模糊技术、云模型和概念格的进一步深入结合，将可以提高其应用能力和挖掘效率3 。入侵模式数据库被扩展到可检测出一些未知入侵的模式，虽然可以提高入侵检测系统的检测率，但这种方法同时也增加了系统的误报率。且实际情况并非如此，网络是动态的。入侵检测也一样，随着时间的推移，新的入侵就可能出现。此外，有效的检测和处理噪声和异常数据的方法；聚类结果的可视化；对数据输入顺序不敏感性等也是聚类分析所研究的方向1 3 主要研究内容本论文的研究工作框图如图1 1 所示，主要研究内容如下：( 1 ) 连续属性离散化技术的研究。认真分析当前离散化算法的研究现状，针对所存在的断点数量和质量上的问题，提出改进的单属性和多属性离散化算法，在保持数据在离散过程中的不可分辨关系和在一定程度上保证决策表原有分类结果的不变性的基础上，尽可能降低断点数量，并使所得到的断点不仅符合数据分布，又体现属性的内在知识背景；( 2 ) 将改进的离散化方法和关联规则算法应用于入侵检测的规则挖掘中特征属性、特征的选取对建立离散模型的准确性影响很大，因此单一使用分类思想进行入侵检测往往效果并不理想。为了提高检测准确率，需要将数据的标准化、离散化并引入启发信息使属性之间的关系更容易的接受分析以备进行入侵检测。第一章绪论研究结构框架模型建立与设计ll 算法与技术选择li 应用研究建立入侵检测模嚣! |设计关联规则挖掘模型构造离散化模型a p f i o f i 关联算法、离散化算法的实现与改进、结构化方法设计等数据选择与预处理关联技术的融a口一联系写分析一图1 1 研究方案框架图1 4 本文的组织结构算法改进与应用本文主要研究了数据挖掘技术及其在入侵检测领域的具体应用，深入探讨了离散化技术在数据预处理上的理论算法和过程应用以及改进的关联规则算法与入侵检测的融合。下面介绍一下论文的内容结构，本文共六章，各章的具体内容安排如下：第一章绪论，介绍课题的研究背景和意义，阐述了数据挖掘技术、入侵检测系统、离散化技术国内外研究现状和发展方向介绍研究可能处在的问题，并概况了本文的主要研究内容和特色，包括本文组织结构。第二章主要描述了数据挖掘和其一些应用，包括其数据挖掘的过程，主要技术和知识发现，重点阐述了关联规则挖掘的相关概念。在分析入侵检测要求和实现方法的基础上，探讨了数据挖掘与入侵检测的应用结合问题。第三章介绍了离散化的具体相关概念、过程与分类和常用的离散化方法，提出了一种频数监督断点算法第四章在介绍相对信息熵、属性重要度和关联度分析的基础上，提出连续属性离散化方法的研究及其在入侵检测中的应用一种多属性离散化算法r s r g c d m d ，并介绍了r s r g c d m d 的算法描述和过程及其算法的比较与分析第五章详细介绍了所设计的基于离散化技术的入侵规则挖掘系统，并利用z d i ) - 9 9 - c u p 数据，对系统进行验证。第六章总结和展望。对本文的研究成果进行概括和总结，并提出了未来的研究方向。- 8 第二章数据挖掘技术研究第二章数据挖掘技术研究本章首先系统地归纳了数据挖掘的过程及主要技术，详细阐述了关联规则挖掘技术的相关概念，并在分析入侵检测要求和实现方法的基础上，探讨了数据挖掘与入侵检测的应用结合问题。2 1数据挖掘与知识发现数据挖掘被认为是数据库研究中的一个新领域。该领域研究的目的是从大型数据库中发现一些有价值的规则。知识发现也有人称之为数据挖掘，在许多文献中，研究者们往往不加区别地使用这两个术语，可以认为数据挖掘、知识发现是同义词。早期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 s ) 是指知识发现，现在则统称知识发现和数据挖掘。数据挖掘是基于人工智能、机器学习、统计学等技术，采用有效的算法，从信息资源中和数据仓库中发现最初未知的、但最终可理解的有用知识和规则，这些规则蕴含了数据库中一组对象之间的特定关系，这些关系为决策提供依据。2 1 1 数据挖掘定义与过程( 1 ) 技术上的定义：数据挖掘( d a t am i n i n g ) 圈就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。数据挖掘是一门交叉技术，它把人们对数据的应用从低层次的简单查询，提升到从数据中挖掘知识，提供决策支持在这种需求牵引下，汇聚了不同领域的研究者，尤其是数据库技术、人工智能技术、数理统计、可视化技术、并行计算等方面的工程技术人员，投身到数据挖掘这一新兴的研究领域，形成新的技术热点。当然数据挖掘并没有一个完全统一的精确定义，在不同的文献或应用领域也有一些其他的定义。( 2 ) 商业角度上的定义：数据挖掘是一种新的商业信息处理技术，其主要特点是对商业数据库中大量业务数据进行抽取、转换、分析和其他模型连续属性离散化方法的研究及其在入侵检测中的应用化处理，从中提取辅助商业决策的关键性数据。现在，由于各行业业务自动化的实现，商业领域产生了大量的业务数据，这些数据不再是为了分析的目的而收集的，而是由于商业的运作而产生的。分析这些数据也不再是单纯为了研究的需要，更主要是为商业决策提供真正有价值的信息，进而获得利润。因此，从商业的角度数据挖掘可以描述为按企业既定业务目标，对大量的企业数据进行探索和分析，揭示隐藏的、未知的或验证已知的规律性，并进一步将其模型化的先进有效的方法。数据挖掘是从数据中提取模式并转化为人们可以理解的形式的过程汹3 ，主要由以下步骤组成：1 数据清理：消除噪声或不一致数据；2 数据集成：多种数据源可以集成在一起；3 数据选择：从数据库中检索与分析任务相关的数据；4 数据变换：统一成适合挖掘的形式；5 提取模式：使用算法提取数据模式；6 模式评估：根据某种兴趣度度量，识别表示知识的真正有趣的模式；7 知识表现：使用可视化和知识表示技术，向用户提供挖掘的知识。具体过程如图2 1 所示。图2 1 数据挖掘的一般过程资料来源：参考韩家炜等译，数据挖掘：概念与技术饽1 2 0 0 1- 1 0 -第二章数据挖掘技术研究2 1 2 知识发现发现知识的方法可以是数学的，也可以是非数学的，可以是演绎的，也可以是归纳的。发现的知识可以被用于信息管理，查询优化，决策支持和过程控制等，还可以用于数据自身的维护删知识发现是识别出存在于数据库中的有效的、新颖的、具有潜在价值的乃至最终可理解的模式的非平凡过程。知识发现主要有三个阶段：数据准备、数据挖掘和解释评价。数据挖掘是知识发现的一个特定的、关键阶段，知识发现是其中的一个或多个阶段的反复过程。数据挖掘是数据库中知识发现不可缺少的一部分，而l ( d d 知识发现是将未加工的数据转换成为有用信息的整个过程，如图2 2所示。输入信息图2 2 数据库中知识发现( 渤) 过程资料来源：( 参考) 史忠植知识发现嗍，2 0 0 2 2 1 3 数据挖掘主要技术信息数据挖掘技术来自应用的需要，要对这些数据进行微观、中观乃至宏观的统计、分析、综合和推理，以指导实际问题的求解，企图发现事件间的相互关联，甚至利用己有的数据对未来活动进行预测嘲1 其主要技术包括以下几个方面：( 1 ) 分类与回归( c l a s s i f i c a t i o na n dr e g r e s s i o n )分类是寻找描述数据类型或概念的模型或函数的过程，以便能够使用这些模型来预测类标号未知的对象所属的类。这些模型基于对训练数据集的分析而得到可以用多种形式表示，如分类规则、判定树、数学公式等。此外，分类包括其他技术，如基于规则的分类器、最近邻分类1 1 连续属性离散化方法的研究及其在入侵检测中的应用器、贝叶斯分类器、人工神经网络( a n n ) 、支持向量机( s v l t ) 、组合方法等不平衡类问题。回归则是通过具有初值的变量来预测其它变量的值。和分类方法不同的是，分类输出的是离散的类别值，而回归输出的则是连续数值。( 2 ) 关联分析( a s s o c i a t i o na n a l y s i s )关联分析用于发现大量数据集中记录之间有意义的关联或相互关系，寻找给定数据集中项之间的有趣联系。关联规则的支持度和置信度是两个规则兴趣度度量，它们分别反映发现规则的有用性和确定性。关联分析的目的就是挖掘出隐藏在数据间的相互关系。关联分析就是给定一组i t e m 和一个记录集合，通过分析记录集合，推导出i t e m 间的相关性。关联规则挖掘的经典算法有a p r i o r i 算法，a p r i o r i t i d 算法。( 3 ) 聚类分析( c l u s t e ra n a l y s i s )聚类分析将数据划分成有意义或有用的簇。如果目标是划分成有意义的组，则簇应当是捕获数据的自然结构。聚类在处理数据对象时不考虑类标号，而是根据“最大化类内的相似性、最小化类间的相似性”的原则对数据对象进行聚类或分组的。聚类分析可以建立宏观的概念，发现数据的分布模式，以及可能的数据属性之间的相互关系。聚类分析都在广泛的领域扮演着重要角色。这些领域包括：心理学和其他社会科学、生物学、统计学、模式识别、信息检索等。“) 孤立点分析( o u t l i e ra n a l y s i s )数据库中可能包含一些数据对象与大部分数据的一般行为或模型不一致，称为孤立点。大部分数据挖掘方法将孤立点视为噪声或例外而丢弃，然而在一些应用( 如欺骗检测) 中，罕见的事件可能比正常出现的那些更有趣。针对孤立点的资料分析称为孤立点挖掘。( 5 ) 序列分析( s e q u e n c ea n a l y s i s )序列分析和时间序列说明数据中的序列信息和时间相关的序列分析前面所提到的数据挖掘方法，事件产生的序列信息被忽略或简单的被作为一条记录对待。而这种方法可以很好的表示序列信息，这对于挖掘与时间关系比较密切的用户行为有很大的帮助。1 2 第二章数据挖掘技术研究2 1 4 关联规则挖掘技术2 1 4 1 关联规则性质定义关联规则是数据挖掘中一种简单但很实用的规则。关联规则模式属于描述型模式，发现关联规则的算法属于无监督学习的算法。关联规则本身是一种很重要的知识，它能表示数据之间的相互关系，对统计和决策工作有重大意义。关联规则的主要应用包括商场的顾客购物分析，网络故障分析等。规则的支持度和可信度是两个度量尺度，它们分别反映规则的有用性和确定性。( 1 ) 项集与支持度( i t e m )设i = “，i 2 ，f 尉) 是二进制文字的集合，其中的元素称为项( i t e m ) 。记d为交易( t r a n s a c t i o n ) t 的集合，这里交易t 是项的集合，并记为乃。对应每一个交易有唯一的标识，如交易号，记作t i d 。设x 是一个i 中项的集合，如果x 冬t 那么称，交易t 包含x 。( 2 ) 支持度与置信度( s u p p o r ta n do o n f id e n c e )规则x - y 在交易数据库d 中的支持度( s u p p o r t ) 是交易集中包含x 和y 的交易数与所有交易数之比，记为s u p p o r t ( x = y ) ，即s u p p o r t ( x ： y ) = l t ：x u y t ，t gd i i d i( 2 1 )设t 中有s 的事务同时支持物品集x 和y ，s 称为关联规则x _ y 的支持度。支持度描述了x 和y 这两个物品集的并集在所有的事务中出现的概率有多大。如果某天共有1 0 0 0 个顾客到商场购买物品，其中有1 0 0 个顾客同时购买了铁锤和铁钉，那么上述的关联规则的支持度就是1 0 。给定一个交易集d ，挖掘关联规则问题就是产生支持度和可信度分别大于用户给定的最小支持度( m i n s u p p ) 和最小可信度( m i n c o n f ) 的关联规则。项集的一个重要性质是它的支持度计数，即包含特定项集的事务个数。可以表示为：似x ) 爿辑i x t , ，驯( 2 2 )其中，符号1 1 表示集合中元素的个数。一个关联规则是形如x = y 的蕴涵式，这里xci ，yci ，并且x n y = o 规则x _ y 在交易集中的可信度( c o n f i d e n c e ) 是指包含x 和y 的交易数与包含x 的交易数之比，记为1 3 -连续属性离散化方法的研究及其在入侵检测中的应用c o n f i d e n c e ( x = y ) ，即c o n f i d e n c e ( x = y ) ：lf t ：x u y c _ t ，t d ) l i t ：x t ，t 妄d ) l ( 2 3 )可信度就是指在出现了物品集x 的事务t 中，物品集y 也同时出现的概率有多大。例如，在购买铁锤的顾客当中，有7 0 的人同时购买了铁钉。在这个例子中，该关联规则的可信度就回答了这样一个问题：如果一个顾客购买了铁锤，那么他也购买铁钉的可能性有多大呢? 答案显然为，购买铁锤的顾客中有7 0 的人购买了铁钉，所以可信度是7 0 。( 3 ) 关联规则( a s s o c i a t i 0 1 3r u l e )关联规则是形如x _ 】，的蕴涵表达式，其中x 和l ，是不相交的项集，即x n y = 妒。关联规则的强度可以用它的支持度( s u p p o r t ) 和置信度( c o n f i d e n c e ) 度量。支持度确定规则可以用于给定数据集的频繁程度，而置信度确定y 在包含】，在包含x 的事务中出现的频繁程度泓1 。支持度( s )和置信度( c ) 两种度量形式如下：艄_ n = 等产c ( x + l o = 等( 2 4 )( 2 5 )关联规则发现即为给定事务的集合r ，关联规则发现是指找出支持度大于等于m m s u p 并且置信度大于等于m i n c o n f 的所有规则，其中m m s u p 和m i n c o n f 是对应的支持度和置信度的阀值。性质l ：子集支持设a 和b 是两个不同的项目集，如果a c _ b ，则s u p p ( a ) = s u p p ( b ) 。因为数据库d 中所有支持b 的交易也一定支持a 。性质2 ：非频繁项目集的超集也一定是非频繁的如果a 在d 中不满足最小支持度条件，即s u p p ( a ) m i n s u p ，则a 的每个超集b 也不是频繁的。由性质l 可得s u p p ( b ) ps u p p ( a ) m i n s u p ，因此b 也不是频繁的。1 4 第二章数据挖掘技术研究性质3 ：频繁项目集的子集也是频繁的如果项目集b 是数据库d 中的频繁项集，即s u p p = s u p p ( b ) = m i n s u p ，因此a 也是频繁的。，2 1 4 2 关联规则挖掘过程与现有技术图2 3 关联规则挖掘的原型步骤资料来源：参考范明等译，数据挖掘导论，2 0 0 6挖掘关联规则的步骤大体可以分成以下两步3 ：( 1 )找出所有的频繁项集，即找出那些支持度不小于事先给定支持度的项集：( 2 )在找出频繁项集的基础上产生强关联规则，即产生那些支持度和置信度分别大于或等于事先给定的支持度和置信度的关联规则。在上述两个步骤中，第二个步骤相对要容易一些，因为它只需要在己经找出的频繁项集的基础上列出所有可能的关联规则，然后用支持度和置信度来衡量这些关联规则，同时满足支持度和置信度要求的关联规则就被认为是有趣的。事实上，由于所有的关联规则都是在频繁项集的基础上产生的，所以说它们已经满足了支持度的要求，从而只需考虑置信度的要求。第一个步骤是挖掘关联规则的关键步骤，挖掘关联规则的总体性能由第一个步骤决定，因此所有挖掘关联规则的算法都是着重于研究第一个步骤。关联规则挖掘的原型步骤如图2 3 所示目前许多专家学者通过大量的研究工作，提出了一些改进的算法以提高关联算法的效率，主要就是朝着降低所需的计算量与减少扫描数据库的次数来改善，下面介绍几个改良关联算法的相关研究：- 15 连续属性离散化方法的研究及其在入侵检测中的应用( 1 ) 划分算法( p a r t i t i o n ) ：为了减少对数据库的扫描次数，s a v a s e r ee ta 1 于1 9 9 5 年提出了p a r t i t i o n 算法m 1 要两遍扫描数据库来挖掘频繁项集。在第一遍中，算法将数据库中的事务集划分为几个非重叠的逻辑子集。如果最小支持度为m i n s u p ，则每个部分的最小支持事务数为m i n s u p该部分中事务数。对每一部分，找出该部分内的频繁项集，也就是局部频繁项集。所有局部频繁项集的集合形成了数据库的全局候选项集。在第二遍扫描中，评估每个候选项集的实际支持度，以确定全局频繁项集。通过适当地划分数据库，使得每一部分都能够放入内存，每个阶段只需要扫描一次即可。算法的正确性是基于局部频繁项集可能不是整个数据库的频繁项集，但是全局频繁项集必须作为局部频繁项集至少出现在一个部分中。( 2 ) f p - g r o w t h 算法：频繁模式增长( f r e q u e n tp a t t e r ng r o w t h ) ，简称f p _ 增长，它由h a n 。p e i 和y i n 于2 0 0 0 年提出不产生侯选项集的情况下产生所有的频繁项集。频繁模式增长算法采用了一个两步骤分而治之的策略：第一遍扫描首先将数据库压缩为一棵频繁模式树( f p - t r e e ) ，同时保留项集的相关信息：然后将压缩后的数据库分成一组条件数据库，每个条件数据库关联一个频繁项，再分别对它们进行挖掘。f p - g r o w t h 算法成功地使用了新的数据结构f p - t r e e ，避免了产生侯选频繁项集。它将所有的频繁项按支持度递减排序得到序f _ l i s t ，任意一个事务中的频繁项按此顺序进行排序后插入到f p - t r e e 中。而f p - g r o w t h 算法自下而上生成后缀项集，依据后缀项集构造条件f p - t r e e ，在其上递归挖掘。递归操作本身就是对条件模式基的进一步划分。( 3 ) 散列算法：c h e ne ta 1 提出的d h p 算法删减不必要侯选项目集的概念来改善挖掘关联规则时的效率。d h p 算法以a p r i o r i 算法为基础，但它引入了l l a s ht a b l e 的结构，并根据统计学上的定理，将其转换为非频繁项目集的删选机制，减少执行过程中不必要的项目集的数量，降低所需要的计算成本，从而有效提升挖掘关联规则的效率。d h p算法的具体步骤为：( 1 ) 利用频繁l 项目集将第二层的侯选项目集建立1 岳第二章数据挖掘技术研究h a s h 表：( 2 ) 根据h a s h 表所产生的侯选项目集，筛选出频繁项目集，再利用频繁项目集削减数据库的大小：( 3 ) 产生频繁2 项目集之后，以后的步骤就与a p r i o r i 算法相同，直到无法再产生更高层次的频繁项目集为止。( 4 ) 抽样算法( s 锄p l i n g ) l为了提高a p r i o r i 算法的效率，l l a n n i l a 等人提出了一种抽样挖掘方法，t o i v o n e n 等人进一步发展了这个思想。抽样方法的基本思想是：选取给定数据库d 的随机样本s ，然后在s 而不是d 中搜索频繁项集。使用这种方法，以牺牲一些精度为代价换取高效性。这样，总共只需要扫描一次s 中的事务，为了减小精度降低而带来的损失，可以使用比最小支持度低的支持度闭值来找出s 中的频繁项集。然后，数据库的其余部分用于计算其中每个项集的实际支持度，以便验证结果的正确性。当效率最为重要时，采用抽样方法来挖掘特别适合。2 143 关联规则经典算法与评估a p r i o r i 算法是第一个关联规则算法，它开创地使用基于支持度的剪枝技术，系统地控制候选项集指数增长。它在数据挖掘中是一个重要的算法，在一组给定的数据项以及交易集合中，分析出数据项集在交易集合中出现的频度关系。 p r i o r i 算法具体描述如下：首先扫描数据库，计算每个数据项的支持度，并根据支持度阀值产生频繁l 一项集厶之后在厶的范围内产生候选的2 一项集集合，算法扫描数据库考察每个候选项集，通过考察的所有项集组成频繁2 一项集的集合，再由厶生成厶，依此类推进行迭代，迭代过程直到不能找到频繁k 一项集终止其中，算法在州生成。时由连接和剪枝两步过程组成- 1 7 -连续属性离散化方法的研究及其在入侵检测中的应用算法l ：a p r i o r i ( 发现频繁