入侵检测中常用数据挖掘算法的分析与研究

杨铭

摘 要：数据挖掘算法是一个定义完备的过程，它以数据作为输入并产生模型或模式形式的输出。本文介绍了2种入侵检测中常用的数据挖掘算法，并说明了在入侵检测中应用数据挖掘技术的优点。

关键词：数据挖掘；关联分析；序列分析；算法

1 引言

数据挖掘（Data Mining，DM），又称为数据捕捞、知识挖掘、知识发现、模式分析等，是从大量的、不完全、包含噪声数据的、模糊的、随机的数据中发现知识（模式）的非平凡过程。该定义包含以下几层含义：数据是指一个有关事实的集合，记录了事务有关方面的原始信息，数据源必须是真实的、大量的、包含噪声的；模式给出了数据的特性或数据之间的关系，是对数据包含的信息的更抽象描述，发现的知识是可理解的、新颖的、潜在有用的、可解释的：不是要发现所有的知识，通常是针对特定的需求来发现满足需要的知识。数据挖掘系统具有以下主要成分：数据库、数据仓库或其它信息库、数据库或数据仓库服务器、知识库、数据挖掘引擎、模式评估模块和图形用户界面。

2 关联分析算法

关联规则挖掘技术用于发现数据库中属性之间的有趣关联，和传统的产生式规则不同，关联规则可以有一个或者多个关联属性。同时一个规则的输出属性可以是另外一个的输入属性。

定义1：关联规则挖掘的数据集记为D（一般为事务数据库），D={t1，t2，…tk…，tm，}，tk={i1，i2，…im，…iP}，tk（k=1，2，…n）称为事务。im={1，2，…p}，称为项目。

定义2：设I={il，i2，…im}是D中全体项目的集合，I中的任何子集X称为D中的项目集，x=k称为集合X为K项目集。设tk和X分别为D中的事务和项目集，如果x tk，称事务tk包含项目集X。每一个事务都由一个唯一的标识符，称为TID。

定义3：数据集D中包含项目集X的事务数称为项目集X的支持数，记为σx。项目集X的支持度记为support（x）：

其中|D|是数据集D的事务数，若support（x）不小于用户支持的最小度（minspport），则称X为频繁项目集，简称频集，否则称X为非频繁项目集，简称非频集。

定义4：若X、Y为项目集，且X∩Y≠Φ，蕴涵式X Y称为关联规则，X、Y分别称为关联规则X Y的前提和结论。项目集X∪Y的支持度称为关联规则X Y的支持度，记作：support（X Y），support（X Y）=support（X∪Y），关联规则X Y的置信度，记作：confidence（X Y）：

3 序列分析算法

序列模式与关联模式相仿，不同的是它处理不同记录之间属性集的关联关系，把数据之间的关联性与时间联系起来。为了发现序列模式，不仅需要知道事件是否发生，而且需要确定事件发生的时间。序列模式分析的侧重点在于分析数据间的前后序列关系。序列分析描述的问题是：在给定交易序列数据库中，每个序列按照交易时间排列成一组交易集，挖掘序列函数作用在这个交易序列数据库上，返回出现的高频序列。将序列模式发现的问题分解成以下几个阶段：

⑴排序阶段。利用客户标识字作为主关键字及事务发生的时间做为次关键字将数据库进行排序，该步骤也将原始的事务数据库转换成客户序列的数据库。

⑵大项目集阶段。在该阶段发现所有的大项目集L，同时发现了所有的大1序列的集合，并把大数据项集映射为一组相邻的整数，每个大数据项对应一个整数。

⑶转换阶段。需要重复确定哪一个给定的大序列集被包含于顾客序列中，要快速完成这种测试，需要将每一个顾客序列转换成一个替换的代表。在一个已转换的客户序列中，每一个事务被包含于该事务中的所有大项目集来替换。如果一个事务不包含任何大项目集，在已转换的序列中就不应保留该事务。如果一个客户序列不包含任何大项目集，则从已转换的数据库中去掉该序列，但是，总客户数的计数仍要对它计数。这个已转换的数据库称为Dt，根据磁盘空间的大小，可以生成这个己转换的数据库，或者当在一个遍历期间读每一个客户序列时通过快速查找完成这个转换。

⑷序列阶段。利用大项目集，发现所期望的序列。

⑸最大阶段。在大序列中发现最大的序列。

4 在入侵检测中应用数据挖掘技术的优点

数据挖掘技术能够从大量的审计数据和网络数据中抽取出能充分描述网络连接和主机会话特征的属性，利用数据挖掘技术产生能够精确描述入侵行为和系统正常行为模式的规则，并自动产生精确适用的检测模型。同时应用数据挖掘方法的检测系统不是基于预定义的检测模型，自适应能力强，可以有效地检测新型攻击以及己知攻击的变种，也可以有效地剔除重复的攻击数据，因而具有较低的虚警率，减少漏报的发生。

[参考文献]

[1]李志云，周国祥，张丽萍.一种挖掘大型数据库的关联规则新算法[J]. 合肥工业大学学报（自然科学版）.2010（02）.

[2]Armananzas R，IInza，R.Santana，et al.A review of estimation of distribution algorithms in bioinformatics.BioData Min. 2008.

[3]李学明.计算机数据的关联规则挖掘理论和算法研究[D].重庆大学.