基于兴趣度的正负关联规则挖掘算法研究

基于兴趣度的正负关联规则挖掘算法研究

刘正红

关键词：兴趣度；正负关联规则；挖掘算法；数据挖掘

中图分类号：G423.04文献标识码：A文章编号：1004-633X（2011）10-0000-00

作者简介：刘正红（1979-），女，吉林长春人，博士，吉林工商学院信息工程分院讲师，研究方向：数据挖掘。

作者单位：吉林工商学院计算机系，吉林长春邮编130062

一、引言

数据挖掘是在海量数据中获得事先未知，潜在的知识。关联规则挖掘是数据挖掘中很重要的一部分，在事务数据库中寻求相关变化的项目之间彼此的积极和消极的影响，这种影响首先在商业中发现这种影响并且有效的指导营销决策，目前银行业也依据大量用户的数据所得的关联规则来推广新业务，在网络安全中，也使用关联规则检测部分非法入侵。随着Apriori算法[1]的广泛应用，用户对挖掘质量有更高的要求，经过研究发现，Apriori算法本身仅用支持度和置信度作为衡量指标，存在以下几个方面的突出问题：

1、具体问题中很难确定合适的支持度阈值；

2、置信度存在假象，表现为规则的置信度很高，但却与实际情况不相符[2][3]；

3、挖掘结果中不包含关联方向，得到大量没有意义的正关联，同时忽略了有意义的负关联；

针对支持度-置信度框架的不足，研究人员给出了很多改进方法，但都是将支持度和置信度作为基本评价指标，关联的本质没有得到有效度量。为了解决Apriori算法在设计上的不足，本文提出了基于兴趣度正负关联规则挖掘算法，采用相关系数作为兴趣度，并且作为第一阈值，好处有以下几个方面：

1、兴趣度的采用可以明确参与挖掘的项目之间的关联方向，从方向上来解决置信度存在的假象；

2、不会出现支持度设置过低，产生大量冗余规则，相反就漏掉大量有效规则的问题；

3、根据相关系数的符号来调整置信度的计算方法，可以将正负关联规则的置信度区别对待，分别得到正、负关联规则，在实际挖掘中大大的削减了参与挖掘数据的规模，有效的提高算法的性能。

二、基本概念

为了描述方便，我们给定参与挖掘的项目集合I，I={I1,I2…In}；每一个实际的事务Ti和有所有的事务构成的事务数据库D，其中Ti={Ii1,Ii2,…Iin}，D={T1,T2…Tn}且Iij∈I。

1、关联规则：X→Y的蕴含式，其中X,Y是I的两个不相交的项目集合，称为项目集。

2、支持度：在事务数据库中，同时包含X和Y的事务数与总事务数的比值，它用来描述在事务数据库中X和Y同时出现的频率，在海量数据中，具有统计意义，通常被理解为规则能够适用的广泛程度。

3、置信度：在事务数据库中X出现，Y也同时出现的概率，它是一个条件概率，被用来度量规则的强度。

4、相关系数：

（1-1）

度量两个随机变量间关联程度的量，其中COV(X,Y)是X,Y协方差，D(X),D(Y)为方差。

三、基于兴趣度的关联规则挖掘算法

1、兴趣度的引入

在关联规则挖掘中，置信度高低并不能完全反映出该规则真实的可信程度，实际上，置信度存在假象，如表Table1：

c和┐c分别表示买coffee和没买coffee的记录数，列m和┐m分别表示买milk和没买milk的记录数。

Table1:Statisticstableofmilkandcoffee

支持度-置信度框架下Coffee和milk之间的关联规则：

支持度：S(coffee?milk)=20/100=0.2

置信度：C(coffee?milk)=|c∪m|/|c|=20/25=0.8

我们可以得到规则：coffee?milk，即coffee的销售对milk的销售产生积极影响；而我们再看看不够买coffee和购买milk的关联规则：

支持度：S(┐coffee?milk)=70/100=0.7

置信度：C(┐coffee?milk)=|┐c∪m|/|┐c|=70/75=0.9

我们同样可以得到规则┐coffee?milk，即coffee的销售对milk的销售产生消极影响，以上这两条规则是相互矛盾的，表明置信度高的规则未必可信，而且仅仅使用支持度和置信度两个评价指标也不能判别关联的方向，既然条件概率存在偏颇，本文使用统计中测量关联程度的相关系数ρ作为新阈值----兴趣度进行挖掘。

从式（1-1）中我们得知：如果两个变量的变化趋势一致（X-E(X),Y-E(Y)符号相同），则COV(X,Y)>0;如果两个变量的变化趋势相反（X-E(X),Y-E(Y)符号相异），则COV(X,Y)<0;若X与Y独立，那么COV(X,Y)=0。ρ为正数表明X与Y正相关，且数值越大，正关联程度越强；相反，则X与Y负相关，数值越小，负关联程度越明显；如果ρ=0，则视为X与Y不相关[5]。

相关系数能反映随机变量的相关程度，通过实践，它也能准确的反映出事务数据库中项目之间关联的本质，相关系数是随机数据内在特征的一种体现，在事务数据库中使用置信度前提是大样本，而实际挖掘中确会因为样本空间的规模使得条件概率会有较大的波动，另外将相关系数作为兴趣度，并且作为挖掘的第一阈值，在关联规则的挖掘中可以同时完成正负关联的挖掘，这样既避免了由置信度造成的假象而产生的误导，也有效的缩小了参与数据的规模。

2、改进后的算法

兴趣度作为关联规则挖掘的第一阈值，会定性的将生成规则分成正关联规则项目集合PS（PositiveSet）、负关联规则项目集合NS(NegativeSet)、不关联项目集合NR(NotRelevant)，对事务数据库中的数据进行适当采样，得到一个能反映项目特征的相关系数矩阵，结合实际挖掘任务，集合相关系数的显著性水平合理给出兴趣度阈值，根据矩阵中（i,j）位置上的ρ值确定Ii,Ij的关联方向和关联强度。针对正负规则区别对待,分别进入其候选项目集的挖掘，负关联规则中的挖掘还需要对出现次数低的项目各项做取补变换（比如项目总数为100，该项目出现5次，计算负关联时需变为95次），才会得到正确的挖掘结果,具体算法流程和核心算法描述如下：

改进后的算法描述：BIRA（basedoninterestassociationrulesalgorithm）

（1）InitialPS,NS,NR;

（2）Constructthetwo-dimensionaltableaboutitemandtransaction;

（3）Calculatetheitemcorrelationmatrix;

（4）minRI,minsup,minconf(其中minRI有统计意义,minsup,minconf由用户指定)

For(i=1,j=1,i<=mj<=n;i++,j++)

If(ρij=0)

NR=NR∪{IiIj}

Elseif(ρij>0)

PS=PS∪{IiIj}

Else

NS=NS∪{IiIj}

（5）对NR,PS,NS产生项目集合算法

Procedurepositive_rules()

{

for(i=1,j=n;i<n;i++)

if(ρij>minRi)

Ip→InIq→In

then求Ip∧Iq与In相关系数ρpqn//其中p,q<n

if(ρpqn>0)

thenIp∧Iq→In

else┐(Ip∧Iq)→In

}

Procedurenegative_rules()

{

for(i=1,j=n;i<n;i++)

if(ρij<0)

Ip→InIq→In

then求┐Ip∧┐Iq与In相关系数ρpqn//其中p,q<n

if(ρpqn>0)

thenIp∧Iq→In

else┐(Ip∧Iq)→In

}

四、实验

为了说明算法的有效性，选用FrequentItemsetMiningDataset（http://fimi.ua.ac.be/data）数据进行实验，分别采用两种算法进行挖掘，得到的二项、三项关联结果如表Table2,Table3所示：

Table2部分二项关联规则

实验结果分析：两种算法得到的规则不完全相同，在二项关联结果中BIRA算法得到的规则基本上可以完全覆盖Apriori算法的结果，除此以外，①BIRA算法还把规则的特性进行了更详尽的描述，比如(I3,I11)是一个彼此消极影响的弱关联规则，如果我们详细的审视Aprior算法得到的（I3,I11），它的支持度很接近阈值0.05的，也就是说他在Apriori中也是一个边缘规则，从（I2,I11）这一点表现的更为明显，经过计算，I2与I11的关联强度更弱，在统计的显著性水平下，几乎可以忽略。②（I2,I12）这条规则因为支持度太低，被忽略，而实际上他们之间的影响是消极的，在很多应用中，负相关的规则用处更大。③Aprior算法在候选集的连接中会构造更多的数据，而BIRA确在挖掘的过程中将参与的项目分组，对后续挖掘的效率的提升有大帮助。

Table3部分三项关联规则

两种算法得到的三项关联结果的片段中，有很大差异，这种明显差异很大程度是由二项关联挖掘延续下来的，在Apriori算法中大项目集已经在挖掘过程中迅速减少，符合要求的关联规则也随之迅速降低，而在BIRA算法中，确生成了较多的规则，经过分析，多数都是有意义的，随着挖掘的深入，我们需要考虑阈值的设定问题，如果一直都是相同的阈值，会导致挖掘迅速收敛，可能很少会得到多项目的关联规则，这也是我们后续需要解决的问题。

五、结束语

本文根据实际研究了Apriori算法的弱点，引入相关系数作为产生关联规则的新的评价指标，并且改进了挖掘算法，在生成候选集时将兴趣度作为第一阈值，有效的解决了置信度造成的假象和更详尽的描述挖掘结果，同时削减了挖掘参与项目的规模，有效的提高了挖掘效率，降低了挖掘成本。经过实验，该算法是有价值的。

参考文献：

[1]李致勋,公慧玲.关联规则在网络异常检测中的作用[J].南昌大学学报(理工版)2010,(8).

[2]宋旭东.关联规则评价指标的研究[J].微计算机信息,2007,(23):174-176.

[3]马占欣.对最小置信度门限的置疑[J].计算机学报,2007,(6).

[4]HastieT,TibshiraniR,FriedmanJ著.范明,蔡玉梅,昝红英译.统计学基础-数据挖掘、推理与预测[M].电子工业出版社,2004.