基于矩阵的模糊关联规则挖掘算法及其应用研究

2010-05-13李林,易云飞,黄潜,覃俊

现代电子技术 2009年20期

李林,易云飞,黄潜,覃俊

摘要:针对布尔型关联规则不能表达挖掘对象中模糊信息的关联性,给出了一系列有关模糊关联规则的定义,并提出了一种基于矩阵结构的模糊关联规则数据挖掘算法(FARMBM)。该算法通过构造矩阵结构来压缩存储模糊模式候选集和频繁集,有效节约了存储模糊模式候选集和模糊模式频繁集内存花销,只需扫描数据库两遍,且可以有效减少系统的I/O开销。这里把FARMBM运用到入侵检测的仿真实验中,实验结果表明,该算法是有效的。

关键词:Apriori;矩阵;模糊关联规则;隶属函数;入侵检测

中图分类号:TP39308文献标识码:A

文章编号:1004-373X(2009)20-069-04

Study and Application of Fuzzy Association Rule Mining Based on Matrix

LI Lin1,YI Yunfei1,2,HUANG Qian1,QIN Jun1

(1.College of Computer Science,South-central University for Nationalities,Wuhan,430074,China;

2.Hechi University,Yizhou,546300,China)

Abstract:In allusion to the Boolean association rules can′t express the association of fuzzy data,a series of definitions of fuzzy association rules and mining algorithm based on matrix for fuzzy association rules are proposed.The algorithm can store fuzzy pattern candidate sets and frequent sets compressible by constructing matrix structure,which effectively saves the memory cost for storing fuzzy pattern candidate sets and frequent sets,it only scans database twice,besides it can effectively reduce the I/O spending.FARMBM is applied to the simulation results of intrusion detection,and efficiency of the algorithm is verified by the experiment.

Keywords:Apriori;matrix;fuzzy association rule;membership function;intrusion detection

0 引言

入侵检测技术[1-3]是网络安全的核心技术之一,是网络信息系统的一种重要的动态防护手段。入侵检测技术的研究是进一步研究网络安全问题的基础,是解决网络安全问题的前提和保证。当然,网络入侵技术也在不断的发展,随着网络数据的增大,入侵的行为表现为不确定性、复杂性等特点。那么入侵检测怎么样才能做到既减小数据量,又能有效地检测到入侵。在入侵检测技术中引入数据挖掘就能有效的解决这一问题。数据挖掘技术在从大量数据中提取特征和规则方面具有很大的优势,将数据挖掘技术应用于入侵检测中,能够克服目前入侵检测技术存在的缺陷,建立一个准确性高的、易于扩展的、适应性好、伸缩性好、智能的入侵检测系统。在对关联规则深入分析的基础上,把模糊集合理论与数据挖掘技术中关联规则挖掘结合起来,提出了一种基于矩阵结构的模糊关联规则数据挖掘算法(FARMBM),并把FARMBM运用到了入侵检测技术当中。

1 关联规则的概念与算法

1.1 关联规则的概念

关联规则是当前数据挖掘研究的主要模式之一,它用于确定数据集中不同领域或属性之间的联系,找出可信的、有价值的多个域之间的依赖关系。关联规则的挖掘目标是从数据库中找出形如“由于某些事件的发生而引起另外一些事件的发生”的规则[4-10]。

定义1 设I={i1,i2,…,im}是由m个不同的数据项目组成的集合,其中的元素称为项(item),项的集合成为项集,包含k个项的项集成为k项集,给定一个事务(交易)D,即交易数据库,其中的每一个事务(交易)T是数据项I的一个子集,即T罥,T有一个惟一的标识符TID;当且仅当X罷时,称交易T包含项集X;那么关联规则就形如X軾的蕴含式;其中,X罥,Y罥,X∩Y=h,即表示满足X中条件的记录也一定满足Y。关联规则X軾在数据库中成立,就有支持度s和具有置信度c。这也就是交易数据集D中具有支持度s,即D中至少有s%的事务包含X∪Y,描述为:support(X軾)=P(X∪Y)。

同时交易数据集D中具有置信度c,即D中包含X的事务至少有c%同时也包含Y,描述为:

confidence(X軾)=P(Y|X)

大多数关联规则挖掘算法通常采用的一种策略是:将关联规则挖掘任务分解为如下两个子任务:

(1) 频繁项集产生:其目标是发现满足最小支持度阈值的所有项集,这些项集称作频繁项集(Frequent Itemset)。

(2) 规则的产生:其目标是从上一步发现的频繁项集中提取所有高置信度的规则,这些规则称强规则(Strong Rule)。

Apriori算法是挖掘产生关联规则所需频繁项集的基本算法;它也是一个很有影响的关联规则挖掘算法。Apriori 算法就是根据有关频繁项集特性的先验知识(Prior Knowledge)而命名的。该算法利用了一个层次顺序搜索的循环方法来完成频繁项集的挖掘工作。

Apriori算法[2]的基本思想是先找出所有频繁1-项集,这些项集组成L1,然后由L1产生频繁2-项集,直到有某个r值使得Lr为空,此时算法结束。从Lk-1到Lk的实现,是把Lk-1与自身连接生成候选k-项集合,记为Ck,Ck中的每一个项集是对两个只有一个项不同属于Lk-1的频集做一个(k-2)连接来产生的。Ck中的项集是用来产生频集的候选集,最后的频集Lk必须是Ck的一个子集。

由于Ck中的每个元素需在交易数据库中进行验证来决定其是否加入Lk,那么这个方法就要求多次扫描可能很大的交易数据库,即如果频集最多包含10个项,那么就需要扫描交易数据库10遍,这需要很大的I/O负载。

1.2 基于矩阵结构的关联规则数据挖掘算法

从Apriori算法的步骤可以看出,该算法有三个缺点:

(1) 在每一步产生的候选项集过多,没有排除不应参与组合的元素;

(2) 每次计算子项集的支持度时,都要进行一遍数据库扫描比较,大大增加系统的I/O开销,并且数据库有些可以删除的项或事务被多次扫描;

(3) 连接程序中相同的项重复比较太多。

针对这些缺点,采用矩阵结构改进Apriori算法,算法思想如下:

(1) 首先把所要挖掘的数据转化为矩阵结构:事务集T作为行的标记,项I作为列的标记,矩阵中每个元素对应某一事务对应某个属性的支持计数,这样每一列的和除以事务的总和,就是所有事务对这一列所对应属性的支持度。

(2) 如果某一事务中只包含一个属性,那么它不可能再包含任一个链接后的2-项集或者k-项集(k≥2),这一事务在以后统计更高阶的频繁集时不再用到,为了提高扫描速度,可以把这一事务删除,对应矩阵就是把这一行给删除。

(3) 接下来把每一列所对应属性的支持度与最小支持度minsup进行比较,如果小于minsup则把这一列删除,保留下来的就是频繁1-项集。

(4) 然后矩阵与自身进行一次连接,这样就产生了2-项集。

(5)接着重复做步骤(2)~(4),直到矩阵为空或只剩一列,这时候已经找到所有支持度大于最小支持度的项集,即频集,算法结束。

可以看出,此算法可以有效地减小事务集以及属性集,这就避免了数据库有些可以删除的项或事务被多次扫描。同时解决了连接程序中相同的项重复比较太多的问题。

2 基于矩阵结构的模糊关联规则数据挖掘算法

2.1 模糊关联规则

用于入侵检测技术[2,3]的关联规则挖掘,需要考虑网络数据特有的特点,否则会产生很多无用的规则。由于关联规则数据挖掘通常只能对离散值进行处理,在数据预处理中要将连续属性域划分为若干离散区间,这就导致了所谓的“尖锐边界”(Sharp Boundary)问题。这就引出了关联规则数据挖掘存在两个缺陷:

(1) 关联规则直接依赖于审计记录,与审计记录具有一一对应的关系,缺少灵活性。

(2) 属性值的微小变化将会引起分类上的突变。比如:设定TCP包在区间[0.5,0.9]是挖掘出某一属性的正常模式,那么如果TCP包是0.900 001,就会判断为异常,也就是说某个行为如果与表示正常模式的区间稍有偏差,会被判为异常。那么,入侵行为如稍有一些变化而落入区间内,就不会被检测出来。

这里采用属性论域上的模糊集来软化边界。这是因为模糊集可以在集合元素和非集合元素之间提供平滑的过渡[4,5]。

定义2 数据集D={t1,t2,…,tk,…,tn},I={i1,i2,…,im}为m个不同的数据项目组成的集合,要发现的模糊关联规则是形如的蕴涵式。其中,X={x1,x2,…,xn},Y={y1,y2,…,yn}且X∩Y=h,A={fx1,fx2,…,fxp},B={fy1,fy2,…,fyq}分别是与X,Y中属性相应的模糊集集合。

则支持度描述为:

support()=∑∈D(∧xj∈

X{αaj(di[xj])}/|D|

其中,αaj(di[xj])为di的隶属度。

置信度[6]描述为:

confidence()=support

A∪B>/support

由关联规则挖掘所产生的规则集,其模式是准确的,而在入侵检测系统中,对于规则集的建立,往往更偏重于语义的,而不是非常准确的区间描述,比如采用数据包传输的大与小,由TCP协议传输的数据包所占比例的高与低来描述网络传输数据的性质,要比用精确的区间如用[100,110)来描述更符合实际处理的需要。因此,将模糊关联规则应用于入侵检测系统中,更符合入侵检测的数据处理模式,使得规则集的建立更趋于准确降低了规则集建立的疏漏和误判。为此,把模糊集合理论与关联规则挖掘结合起来,提出基于矩阵结构的模糊关联规则数据挖掘算法(Fuzzy Association Rule Mining Base on Matrix,FARMBM)。

2.2 算法的描述

FARMBM算法与基于矩阵结构的关联规则数据挖掘算法基本相似,只有一点不同就是首先需要将挖掘的数据通过隶属函数转化为模糊数据集后再进行挖掘。具体算法如下:

算法:FARMBM

输入:模糊数据集D、最小支持度minsup;

输出:模糊关联规则集。

方法:

初始化矩阵行和列数:countrow和countcol;

初始化矩阵:

double[,] arraya;//使用一个二维数组存放矩阵

double[] tempa;//使用一个一维数组存放每个属性的支持度

String[,]strArr;//使用一个字符串数组来存放各个属性

While(countcol>1);//矩阵至少大于一列