正负关联规则数据挖掘算法研究

杨井荣，侯向宁

(成都理工大学 工程技术学院，四川 乐山 614007)

0 引 言

在线事务处理(OLTP)[1]是传统的数据库应用程序。进行在线交易是它的主要任务，对数据进行查询处理是它的另一个主要任务。在ONLINE交易中，商业数据库需要极速增长的数据，以提供决策信息的支持。采矿技术(即在线分析处理(OLAP)的快速发展是从数据库中获取信息并使用信息。

目前，国内对数据挖掘的研究主要集中在算法的优化和改进上。该文在总结以往数据的基础上，从另一个角度研究了关联规则——负关联规则，使它们与传统规则有所差别。正相关的关联规则加上负相关的关联规则一起形成正负相关的关联规则，以达到提高关联规则数据挖掘效率的目的，也使数据挖掘理论中的关联规则得以完善。

1 关联规则的核心技术

关联规则的核心技术就是通过数据挖掘技术，寻找关联度、兴趣度非常高的一个重要的规则模型，以达到在大量数据中发现项目集之间的有效关联[2]的目的。在以往的研究中，关联规则使用频率最高的数据挖掘经常用于发现在交易数据库中不同种类、不同项目之间的联系。

设T={t1,t2,…,tm}是项(term)的m元集合。在这个等式里，设置事务有相关性的数据Data是DataBase事务集的集合元素，在此集合中的每个交易T是一个项的集合，用集合表示为Ti⊆T。公式里为每一个事务选择一个候选码，即一个关键字，称作T_KEY。若X是集合T中项的集合，被命名为项集(termset)，即项集X包含于事务T的充要条件是X⊆T。

据此，关联规则的形式可以用离散数学中的蕴涵式表示，P决定Q，其中P⊆T，Q⊆T，这里P与Q的交集为空集。

若规则P⟹Q在事务D中成立，并且存在支持度s(supportort)，充分且必要条件是D中事务包含P∪Q的百分比是s，即:

s=support(P⟹Q)=P(X∪Y)=|{T|P∪Q⊆∧T∈D}|/|D|

规则P⟹Q在事务D中成立，并且具有置信度c(confidence)，则充分且必要条件是D中包含P的事务同时也包含Q的百分比是c，即:

C=confidence(P⟹Q)=p(P/Q)={T|P∪Q⊆T∧T∈D}|/|{T|X⊆T∧T∈D}|

项的集合称为项集。包含K个项目的项目集称为K个项目集。例如，{printer，computer}是两项。物料集的发生频率是指包括该物料集在内的事务个数，被称为该物料集的发生频率，称为支持计数或计数。当且仅当sup乘以D中的事务总数，项目集的频率不小于最小支持时，就称项目集满足最小支持度。在文献[3]中，将达到或超过最小支持的项目集，简称为频繁项目集。集合的基数为K的频繁项目集全称为K-频繁项目集，简记为LK。在文献[4]中，将同时达到或超过最小支持度(min_SUP)、最小置信度(min_CONF)的关联规则称为强规则。

2 关联规则研究现状及分类

二十世纪末的关联规则挖掘形式主要是购物篮分析。二十一世纪扩展了关联规则研究类型。在文献[5]中，按照不同的标准，不同的维度，可以把关联规则分为不同的研究模型。

2.1 按值的类型分类

在文献[6]中，根据所处理值的数据类型进行分类，把关联规则分成布尔(Boolean)关联规则、数量化关联规则。

2.1.1 布尔关联规则

布尔关联规则(Boolean关联规则)处理的是连续的分类数据，该分类数据关注的是相关项目之间存在的关系。例如:SEX(M，“男性”)->professional(M，“快递员”)，其中M是代表某人员的变量。

2.1.2 数量化关联规则

数量化关联规则处理的是数字类型的数据。在处理之前，首先将数字类型的数据划分为不同的区间。另外，数量化关联规则也可以包含类别型变量。例如:SEX(M，“男性”)->Profession(M，“快递员”)->Age(M，“18～45”),其中M是代表某人员的变量，则数量化的属性Age是不连续的，即离散数据。

2.2 按照抽象层分类

在文献[7]中，按照能把数据抽象成的层数分类，把关联规则分成单层关联规则、多层关联规则。

2.2.1 单层关联规则

单层关联规则(single-level association rules)，只关心现实生活中数据的一个层次，不关心数据实际上有多个不同的层次，也不讨论不同抽象层的元组或字段。例如：购买(M，“毛笔”)决定也采购(A，“墨汁”)，其中M是表示购买者的变量，而毛笔和墨汁在数据中属于同一概念层。

2.2.2 多层关联规则

多层关联规则全面讨论了现实生活中数据的多样性、多层性。这个规则涉及不同抽象数据层的元组或字段。例如：

购买(A，“计算机”)->购买(A，“打印机”)

(1)

购买(A，“联想计算机”)->购买(A，“Sony打

印机”)

(2)

购买(A，“IBM计算机”)->购买(A，“打印机”)

(3)

其中，计算机和打印机属于同一抽象层，联想计算机、Sony打印机同属于同一抽象层，计算机与联想计算机相比，处于更高的抽象层，Printer与Sony Printer相比，也处于更高的抽象层。规则(3)展现了一个细节，联想计算机和较高层次打印机之间的多层关联规则。在文献[8]中，重命名这种关联规则称为交叉层关联规则(cross-level association rule)。

2.3 按照所涉及的数据维分类

在文献[9]中，按照所涉及的数据维度分类，把关联规则分成关联规则一维关联规则、多维关联规则。

2.3.1 一维关联规则

一维关联规则常常称为维度内关联规则。关联规则内的元组或字段仅仅涉及数据的一个维度。此类关联规则通常都可以通过事务数据库挖掘出来。例如：

购买(M，“毛笔”)->购买(M，“墨汁”)

(4)

2.3.2 多维关联规则

在文献[10]中，多维关联规则是指元组或字段涉及两个或多个数据维度的关联规则。这种关联规则常常通过关系型数据库或数据仓库进行挖掘。多维关联规则是按照数据维度重复与否进行区分的，按照这个标准，把关联规则分为维度间关联规则、混合维度间关联规则。维度间关联规则是指在相异数据维度重复出现的关联规则，参照规则(5)；混合维度关联规则是指在相同数据维度重复出现的关联规则，参照规则(6)。

sex(M，“男”)∧profession(M，“互联网”)⟹

buys(M，“品牌计算机” )

(5)

sex(M，“男”)∧buys(M，“品牌计算机”)⟹

buys(M，“品牌打印机”)

(6)

数据库字段或列可以是分类的或量化的。分类字段(categorical field)也称标称字段(nominal field)，是指具有可数并有限的不同的、无序的值的字段。分类字段多维关联规则挖掘利用先前的算法即可进行相应的处理。数量化字段(quantitative field)是指具有有序的数值类型值的字段。

关系型数据库可以分类或量化。category字段也称为nominal字段，是指具有有限数量的不同无序值的关系字段。前一种算法可以用来挖掘分类字段的多维关联规则。数量字段是指具有有序数值的字段。

3 正负关联规则数据挖掘算法

二十世纪末的关联规则数据挖掘(association rule，AR)是P⟹Q的模式，主要用来挖掘消费者事务数据库中元组集之间的关联关系。关联规则最初是以R.Agrawal为首提出的。二十世纪九十年代提出了一种快速算法，成为P⟹Q类关联规则的一个重要补充规则。该文研究了三种形式的关联规则：P⟹┑Q,┑P⟹Q,┑P⟹┑Q，这三种形式的关联规则被称为负AR，即NAR。该文提出了一种简单有效的利用正关联规则的相关信息计算负关联规则支持度和置信度的方法，并给出了能够同时挖掘正关联规则、负关联规则的算法。与现有算法相比，其不同之处在于，该算法不但可以挖掘频繁项目集中的正、负关联规则，同时还可以检测并且删除冲突规则。有一个非常有效，快速进行挖掘的算法。

(1)负关联规则的支持度和置信度计算方法[11]。

事务数据库D中规则P⟹Q的置信度[12](confidence，C)是指同时包含P和Q的事务数与包含P的事务数之比[13]，记录为C(P⟹Q)。负关联规则[14]包含不存在的项(non-existing-items，如┑P，┑Q)，很难直接计算它们的支持度和置信度[15]。因此，该文给出了以下定理和计算方法。

定理1：设P,Q⊂T，P∩Q=∅，则有：

①S(P)=1-s(┑P);

②S(P∪┑Q)=S(P)-S(P∪Q);

③S(┑P∪Q)=S(Q)-S(P∪Q);

④(┑P∪┑Q)=1-S(P)-S(Q)+S(P∪Q)。

根据定理1，为了能够用数学理论证明定理，该文利用离散数学的集合论的理论重新表示支持度和置信度，即将项目集的集合运算利用事务集的集合运算进行计算，这样，定理的证明就可以通过数学理论得以支撑，利用集合论中某些定理和性质，有利于理解定理1。

设Ps表示包含于项集P的事务集[16]，其集合基数|Ps|表示Ps中的事务数；类似地，设Qs表示包含于项集Q的事务集，其集合基数|Qs|表示Qs中的事务数。对于关系型数据库E，代表数据库中全体事务的集合，即全集，它的基数|E|是事务的总个数。相应的转换如下：

①s.count(P∪Q)=|Ps∩Qs|;

②s(P)=s.count(P)/|D|=|Ps|/|D|;

③s(P∪Q)=s.count(P∪Q)/|D|=|Ps∩Qs|/|D|;

④c(P⟹Q)=s(P∪Q)/s(P)=|Ps∩Qs|/

|Ps|。

推论1：设P,Q,T,P∩Q=∅，则有：

①c(P⟹┑Q)=(s(P)s(P∪Q))/s(P)=

1-c(P⟹Q);

②c(┑P⟹Q)=(s(Q)-s(P∪Q))/

(1-s(P));

③c(┑P⟹┑Q)=(1-s(P)-s(Q)+s(P∪Q))/(1-s(P))=1-c(┑P⟹Q)。

按照定理1和置信度的定义，很容易证明推论1，这里省略了推论1。推理1用于计算负关联规则的置信度[17]。

(2)正负关联规则数据挖掘的算法。

算法中，假设频繁项集已经求出并且已经保存在集合Collection中。

算法1：挖掘正关联规则和负关联规则。

Input:

Collection:频繁项集;

min_conf:最小支持度;

Output:

正关联规则和负关联规则集合AR;

①AR=∅;

②∥产生Collection中的正负关联规则

For any itemsetTin Collection do{

For any itemsetP∪Q=TandP∩Q=∅ do

{

correlation=s(P∪Q)/(s(P)s(Q))

if correlation>1 then{

∥产生P⟹Q和┑P⟹┑Q型的规则

ifc(P⟹Q)≥min_conf then

AR=AR∪{P⟹Q};

ifc(┑P⟹┑Q)≥min_conf then

AR=AR∪{┑P⟹┑Q};

}

if correlation<1 then{

∥产生P⟹┑Q和┑P⟹Q型的规则

ifc(P⟹┑Q)≥min_conf then

AR=AR∪{P⟹┑Q};

ifc(┑P⟹Q)≥min_conf then

AR=AR∪{┑P⟹Q};

}

}

}

③ returnAR;

据此，为了验证算法1的有效性，对合成数据进行了实验。实验在inteli7、4gram、win10、VS 2010集成开发环境下进行。有400个事务实验数据，最大项集数为6。设置min_support为0.15，min_conf为0.45，表1列出了两种算法的实验结果。

表1 两种算法关联规则数对照

从表1可以看出，算法1得到的正相关的关联规则数明显少于经典的Apriori算法。这就说明算法1删除了一些互相矛盾的关联规则，挖掘出许多负相关的关联规则，证明算法1是有效的。

4 P-S兴趣度在正负关联规则中的研究

文献[4]提到的一条规则P⟹Q只有在符合条件support(P∪Q)-support(P)support(Q)≥mininterest>0下才是有兴趣的。那么，对于负关联规则，support(P∪Q)-support(P)support(Q)可能小于0，因此可以使用它的绝对值作为条件，即规则P⟹Q仅在满足条件support(P∪Q)-support(P)support(Q)≥mininterest<0时才感兴趣。那么，这四种关联规则的最低利益之间的关系是什么？

定理2：如果|support(P∪Q)-support(P)support(Q)|≥mininterest,那么:

(1)|support(P∪┑Q)-support(P)support(┑Q)|≥mininterest;

(2)|support(┑P∪Q)-support(┑P)support(Q)|≥mininterest;

(3)|support(┑P∪┑Q)-support(┑P)support(┑Q)|≥mininterest。

从定理2可以看出，只要合理有效地进行最小兴趣度的选取，就能够有效地避免大部分不感兴趣的规则。与此同时，也证明了四种关联规则可以被同一个最小兴趣P所约束。

当同时研究正负关联规则[18-19]后有可能会出现conf(┑A⟹B)>conf(A⟹B)>min_conf的矛盾问题，而相关性的应用是解决这一矛盾问题的有效方法。该文对关联规则的相关性进行了定义，提出两个集合，集合A和集合B的相关性可以由support(A∪B)/support(A)support(B)表示，要求其中的s(A)≠Q,s(B)≠0。其实只要将P-S兴趣度稍加改进就可用于关联规则的相关性判断，即当同时研究正、负关联规则时，可能会出现conf(┑P⟹Q)>conf(P⟹Q)>min_conf的情况，应用关联是解决conf问题的一种有效方法，定义了关联规则的相关性。该文提出项集P和项集Q的相关性可以用P∪Q/support(P)support(Q)来计算，其中s(P)≠0,s(Q)≠0。实际应用中，可以通过提高P-S兴趣度来判断关联规则的相关性，即通过correlation(P,Q)=support(P∪Q)-support(P)support(Q)来度量。

correlation(P,Q)可能出现三种情况:

(1)若correlation(P,Q)>0，则P和Q是正相关的，即事件P出现的次数越多，事件B出现的次数也越多;

(2)若correlation(P,Q)=0，则P和Q是相互独立的，事件Q出现的次数与事件P出现的次数无关;

(3)若correlation(P,Q)<0，则P和Q负相关，事件P出现的次数越多，事件Q出现的次数越少。

定理3：如果correlation(P,Q)>0，那么:

(1)correlation(┑P,Q)<0;

(2)correlation(P, ┑Q)<0;

(3)correlation(┑P，┑Q)>0。

反之亦反之。

定理3说明规则P⟹Q(或┑P⟹┑Q)和P⟹┑Q(或┑P⟹Q)不会同时作为有效规则，从而有效防止自相矛盾的规则产生。

5 结束语

该文主要研究了负关联规则理论，并与传统的正关联规则(positive association rules)相结合，形成了较为完整的关联规则理论。对于负关联规则，它比传统的关联规则更有意义。目前，涉及负关联规则的领域很多，特别是在证券市场分析方面[20-25]。

在正、负关联规则的应用中，由于条件的限制，该文没有进行深入实践，只做了少量的原型研究，而负关联规则还需要进一步的研究和完善。目前，对关联规则的研究主要是从算法的角度出发。如何提高算法的时空有效性，使得算法经过处理后可以应用到负关联规则中，而关联规则挖掘正是将研究与应用相结合，因此该应用系统的设计非常重要。