基于参考度的有效关联规则挖掘*

柳景超,宋胜锋

(海军工程大学电子工程学院,武汉 430033)

基于参考度的有效关联规则挖掘*

柳景超,宋胜锋

(海军工程大学电子工程学院,武汉 430033)

针对当前关联规则挖掘采用的支持度-置信度框架在具体应用中存在的问题,引入新的指标——参考度对模型中关联规则挖掘算法评价体系进行改进。实验表明,通过引入参考度,能够提高挖掘有效规则的效率。

数据挖掘,关联规则,入侵检测,参考度

引 言

入侵检测系统作为一种积极主动的安全防护措施,能够检测出各种形式的入侵行为,是安全防护体系的重要组成部分。以数据为中心的入侵检测实际上是一个数据分析的过程。随着网络信息的不断丰富和带宽的提高,收集的审计数据和网络数据包的数量将是非常巨大,要想从海量的审计数据和网络数据包中发现有意义的信息将变得非常困难。

数据挖掘是从大量数据中抽取出潜在的、有价值的知识的过程。因此,将数据挖掘应用于入侵检测成为一个很有前途的研究方向[1]。关联规则挖掘是数据挖掘中一个重要手段,在入侵检测中发挥了重要作用。本文针对当前关联规则挖掘采用的支持度-置信度框架在具体应用中存在的问题,引入新的评价指标——参考度对模型中关联规则挖掘算法评价体系进行改进。实验表明,通过引入参考度,能够提高挖掘有效规则的效率。

1 关联规则

关联规则挖掘是数据挖掘研究的一个重要分支,其目的就是从海量数据中挖掘出有价值的描述数据项之间相互联系的有关知识[2]。关联规则挖掘问题可以分解为以下两个子问题:

(1)找出所有频繁项集,即找出的所有项集的支持度满足用户所规定的最小支持度;

(2)由频繁项集构造置信度不低于用户规定的最小置信度阈值的强关联规则。

目前通常采用的挖掘算法为 Apriori算法[3]。Ap riori算法对关联规则的评价指标为支持度和置信度,基于支持度-置信度框架的挖掘算法能够挖掘出一些有效关联规则,但在实际应用中可能会产生大量冗余的、起误导作用的规则。例如:通过对某服务器系统安全日志数据库D随机抽取2 000条事务,并对以下 4个数据项集:

I1= {连接服务器 21端口}、I2={拒绝服务攻击}、I3={提供 www服务}和 I4={开放 80端口 }进行统计、分析:结果如表 1所示。

表1 项目支持数列表

如果假定min sup=20%,min cof=30%,可以挖掘出如下两个关联规则:

规则(1)I1⇒I2(support=40%,con f=80%);

规则 (2)I3⇒ I4(support=60%,con f=100%)。

通过对产生的规则进行分析,可知规则(1)的含义为凡是连接服务器 21端口的行为都是拒绝服务攻击;规则(2)的含义是提供 www服务的服务器会开放80端口。对于规则(1)来说,显然是一个错误的规则,如果规则库加入这一规则将会增大系统的误报率影响整个入侵检测系统的准确性;而规则(2)尽管是一个正确的规则,但这是一个众所周知的事实,对于检测入侵行为而言没有实际意义,这样的规则加入到规则库,将会增加入侵检测系统搜索规则库的时间,降低检测效率。

2 引入新的指标改进关联规则评价体系

为了避免生成大量冗余甚至是具有误导作用的关联规则,一些文章曾引入诸多阈值以加强对关联规则的评判[4-6]。在对该问题进行深入研究的基础上,引入参考度来提高关联规则的有效性。

定义1:参考度。对于关联规则X⇒Y,其参考度为:

其中,P(X)表示X出现的概率,P(Y)表示Y出现的概率,P(XY)表示X、Y同时出现的概率,P()表示X不出现的概率,PY)表示、Y同时出现的概率。

当某一项集支持度为 1时,通常认为它与其他任何项集之间不具有相关性,则不需要考虑该项集与其它项集之间的参考度。任何一个项集X出现的概率为 0＜P(X)＜1。 由于 0＜P(Y/X),P(Y/)≤1,所以参考度的取值范围 [-1,1]。

为了进一步说明参考度的有效性,有必要给出相关度[7]的概念。从概率的角度定义相关度:

则由式(1)～式(3)可以得到:

分析式(4)可知,参考度的定义不仅包含了相关度的因素,而且还考虑了P(Y)的因素。因此,引入参考度可以充分体现规则X⇒Y的有效性。

当 corr=corr1时,corr=corr1=1,即如果 X、Y不相关 ,则也不相关;当 corr＞ 1时,corr1＜ 1,即如果X、Y具有正相关性,Y具有负相关性;当corr＜1时,corr1＞ 1,也即是如果X、Y是负相关,说明X的发生对Y的发生起抑制作用。此时,X⇒Y为无意义的规则应丢弃;同时考虑其反面规则。

与支持度、置信度类似,参考度也有阈值,称之为最小参考度,记为m in consult。可以通过确定最小参考度来重新定义强关联规则。

定义 2:强关联规则。事务库D上的关联规则X⇒Y,如果满足最小支持度、最小置信度和最小参考度的阈值,则认为是用户感兴趣的规则,即强关联规则。

引入参考度之后,可以将关联规则分为以下几种情况:

(1)有效的关联规则,即用户感兴趣的规则,此时该规则满足最小支持度、最小置信度,且 consult＞0;

(2)冗余规则,即满足最小支持度、最小置信度,且consult=0的规则;

(3)负关联规则,即满足最小支持度、最小置信度,且 consult＜0的规则,此时其反面规则可能为感兴趣规则,应加以考虑。

在新的评价体系支持度-置信度-参考度框架下,关联规则的挖掘工作分为以下 4个步骤:

(1)利用 Ap riori算法,找出事务数据库D中所有频繁项集L;

(2)对步骤(1)产生的所有频繁项集 l∈ L,产生所有满足置信度、参考度的关联规则,并加入到关联规则集合R中;

(3)对于步骤(2)中参考度小于0的所有频繁项集 l∈ L,考虑其反面规则,产生所有满足支持度、置信度、参考度的反面规则(⇒Y),并加入到关联规则集合R中;

(4)输出关联规则集合 R。

对于第(3)步,要计算其反面规则的相关阈值,即对于反面规则⇒Y需要作以下运算:

通过上述的推导过程可以得出,反面规则的相关阈值均可以利用步骤(2)中求出的结果计算得到,无需再对事务库进行扫描。

下面仍以表 1为例,在引入参考度的情况下重新挖掘这两条规则,设min consult=0.6。对于规则(1),计算其参考度为:

同样舍弃。

通过分析,可以得到以下结果:规则(1)及反面规则均不是强关联规则,即是否连接服务器 21端口不是判断拒绝服务攻击的一个主要标志;而对于规则(2),尽管不会对检测效果产生误导,但由于这条规则实际意义不大,增加该规则会降低系统工作效率,因此引入新的评价指标后同样将其舍弃。

3 实验分析

为了验证引进的第三个指标——参考度对结果产生的影响,以 KDD Cup 1999 Data[8]为数据集,进行实验分析。KDD Cup 1999 Data是在军事网络环境中运用非常广泛的模拟入侵攻击所得到的网络数据集,是为第三届国际知识发现和数据挖掘竞赛提供的。在实验过程中选取2 000条记录作为测试数据集。实验所使用的硬件平台是 Pentium4 3.00 GHz处理器,512 M内存和 80 G硬盘的 PC机,操作系统为Window s XP。

设定最小支持度为15%,最小置信度为80%,在不同的参考度下,统计产生的规则数目。结果如图1所示。

图 1表明,算法产生的规则数随着参考度阈值的增加而递减,因为随着参考度的增大,越来越多的规则被淘汰。由此可以看出,加入新的评价指标——参考度来控制产生关联规则的质量是可行的,而且给系统带来极大好处。

图 1 参考度阈值-规则数关系图

4 结束语

关联规则挖掘作为数据挖掘中的一个重要手段在入侵检测中发挥了重要作用。本文针对当前关联规则挖掘采用的支持度-置信度框架在具体应用中存在的问题,引入新的评价指标——参考度对模型中关联规则挖掘算法评价体系进行改进。实验表明,通过引入参考度,能够提高挖掘有效规则的效率。

[1] Lee W.A Data M ining Framew ork for Construc ting Features and M odels for Intrusion Detec tion Systems[D].New York Co lumbia University,1999.

[2] Agrawal R,Im ielinske T, Swam i A. M ining Association Rules Betw een Sets o f Items in Large Databases[C]//Proc. o f the ACM SIGMOD International Con ference on the M anagement of Data.W ashington D.C,1993,5:207-216.

[3] Agrawal R,Srikant R.Fast Algorithms for M ining Association Rules[R].Reaearch Re-port RJ9893,IBM Almaden Research Center,San Jose,California,1994.

[4] 伊卫国,卫金茂,王名扬.挖掘有效的关联规则[J].计算机工程与科学,2005,32(27):91-94.

[5] 吴良杰,刘红祥.基于确信因子的有效关联规则挖掘[J].计算机工程与应用,2004,40(32):187-189.

[6] 罗 可,郗东妹.采掘有效的关联规则 [J].小型微型计算机系统,2005,25(26):1374-1379.

[7] 李 鹏.数据挖掘在入侵检测中的应用研究[D].郑州:解放军信息工程大学,2004.

[8] KDD Cup 1999 Data[EB/OL].h ttp://kdd.ics.uci.edu/databases/kddcup99/kddcup99.htm l.

M ining Efficient Association Ru les Based on Consult

LIU Jing-chao,SONG Sheng-feng
(College of Electronic Engineering,N ava l University o f Engineering,Wuhan 430033,China)

Peop le find that generated association rules may be false or redundant when using the traditional evaluating indicator. The article introduces the new measure-consu lt to imp rove measure system ofmining algorithm.The experiments show that the efficiency of valid rules can be enhanced by adding the new measure.

datam ining,association rules,intrusion detection,measure-consult

TP393.08,TP311.13

A

1002-0640(2011)05-0079-03

2010-01-08

2010-04-05

湖北省自然科学基金资助项目(2006ABA 009)

柳景超(1979- ),女 ,河南周口人,硕士,讲师,研究方向:数据挖掘,入侵检测。