一种挖掘负关联规则的有效方法

张雅芬，王 新

(云南民族大学数学与计算机科学学院，云南昆明650500)

1 问题概述

传统的关联规则挖掘算法是依赖于支持度和置信度来挖掘的，它最初是由Agrawal等于1993年提出来的［1-2］，经典的Apriori算法也被同时提出.关联规则的任务就是挖掘出同时满足支持度和置信度最小阈值的规则.

下面来看一个例子［3-4］，希望分析爱喝咖啡和爱喝茶的人之间的关系.收集一组人关于饮料偏爱的信息，并汇总在表1中.

表1 1 000个人的饮料偏爱

支持度s=喝茶同时喝咖啡的人数/总人数=150/1 000=15%，置信度c=喝茶同时喝咖啡的人数/喝茶的人数=150/200=75%.发现该条规则的支持度和置信度都很高，似乎喜欢喝茶的人也喜欢喝咖啡.但是再仔细观察表中的数据可以发现，不管他是否喝茶，喝咖啡的人的比例为800/1 000=80%，而喝咖啡的饮茶者却只占75%.这说明一个人如果喝茶，则他喝咖啡的可能性由80%下降到75%.从该实例中可以发现置信度的缺陷在于该度量忽略了规则后件中项集的支持度.更奇怪的是喝咖啡的饮茶者所占的比例75%实际少于所有喝咖啡的人所占的比例80%，这表明饮茶者和喝咖啡的人之间存在着一种逆关系，这也是种关联规则，只是它是一种负相关［4］，称之为负关联规则，与之相对的传统关联规则即为正关联规则.

在上述实例中发现基于这种框架的关联规则挖掘存在一定的缺陷和局限性，在挖掘过程中，将会丢失许多有价值的信息，从而给决策者带来一定的误导.因此在挖掘过程中，需要重视负关联规则的挖掘.例如在购物篮分析中，负关联规则表明顾客购买某些商品有可能就不购买某些商品，这对决策者设计商店布局有一定的导向性;在投资、营销或者广告策划等诸多领域的决策过程中，负关联规则同样有着不容忽视的作用.

对于负关联规则的研究，最初是由Brin等在文献［5］中提出2个频繁项集间的负相关;Savasere等在文献［6］中研究了强负关联规则问题;WU Xindong等［7］提出一种PR模型.之后许多学者研究关于负关联规则算法以及改进，如文献［8-9］.本文提出了一种结合相关系数和最小兴趣度2个度量的负关联规则算法，其中相关系数用以识别关联规则是正规则还是负规则，比较方便简单，避免了对决策者的误导;最小兴趣度保证了所挖掘产生的负关联规则的有效性，避免了大量冗余的规则产生，给决策者带来一定的导向性.并且通过实验证明该算法是有效的.

2 负关联规则的相关知识

负关联规则指的是在2个项集之间的互斥或否定关系，其形如A⇒¬B，¬A⇒B，¬A⇒¬B，其中¬A，¬B分别表示交易中不含有A，B．如在商场中A表示购买茶叶，B表示购买咖啡，则¬A表示不购买茶叶，¬B表示不购买咖啡，因此A⇒¬B表示顾客购买茶叶则不会购买咖啡的相关规则，此即为一条负关联规则.下面给出负关联规则的相关定义，其中min_sup为最小支持度阈值，min_conf为最小置信度阈值：

定义1 对于给定的项集A，B其中A∩B=Ø，A，B之间共有8种关联规则，如下所示：

其中⑤～⑧和①～④是对应的，其中①和⑤称为正关联规则，②～④称为负关联规则．因此在本文中主要讨论负关联规则②～④．

定义2 一个有意义的负关联规则必须满足以下3个条件：

① A∩B=Ø;

② sup(A)≥min_sup且sup(B)≥min_sup;

③ sup(A∪¬B)≥min_sup或者sup(¬A∪B)≥min_sup或者sup(¬A∪¬B)≥min_sup．

对于负关联规则支持度和置信度计算可以参考文献［10］．下面将根据负关联规则的支持度和置信度的计算方法求解上述例子的相关度量．为简单起见，茶事务用t表示，咖啡事务用c表示，则对于该实例中的负关联规则形式如下：t→¬ c，¬ t→c，¬ t→¬ c．则可以得出：

① sup(t→c)=0．15，conf(t→c)=0．75．

② sup(t→¬ c)=0．05，sup(¬ t→c)=0．65，sup(¬ t→¬ c)=0．15;

③ conf(t→¬ c)=0．25，conf(¬ t→c)=0．812 5，conf(¬ t→¬ c)=0．187 5．

可以假设最小支持度阈值min_sup=0.15，最小置信度阈值min_conf=0.55.很容易得到¬t→c是1条强负关联规则.这意味着不饮茶者会可能提高喝咖啡的可能性.此时出现的矛盾是：到 底是还是通过对本文中提到的例子进行分析可知它是一个负相关，并且是一个强负关联规则，与强正关联规则相对［10］.

3 负关联规则的识别和有效性

本文提出的算法基于相关系数和最小兴趣度，其中相关系数用以识别关联规则是正规则还是负规则，避免了对决策者的误导;最小兴趣度保证了所挖掘产生的负关联规则的有效性，避免了大量冗余的规则产生.

3.1 相关系数

设随机变量X，Y的相关系数［11］或者标准协方差为记为 ρXY．其中 D(X)，D(Y)为变量 X，Y的标准差．Cov(X，Y)为X，Y的协方差．一般地当ρXY=0时，称X与Y不相关;当0＜ρXY≤1，则变量X与Y正相关，表明随机变量Y随X的增大而增大;当-1≤ρXY＜0，则变量X与Y充分负相关，表明随机变量Y随X的增大而减少．

4 算法描述

在上述的例子中，不难发现并不是所有的频繁项集产生的规则都是有趣的.因此在挖掘规则的过程中加入了最小兴趣度，对规则的产生进行了剪枝，从而在一定程度上减少了搜索空间和存储空间.在此算法中假设频繁项集已经产生.算法如下：

输入：L：频繁项集;min_conf为最小置信度;min_interest为最小兴趣度;ρ是相关系数的值;

输出：INAR(有趣负关联规则的集合)。

1)初始化INAR=Ø;

2)计算相关系数

for each itemset I in L，I=A∪B⊆L and A∩B=Ø do{

① ρ=correlation(A，B)

② if-1≤ρ＜0 then

{

if conf(A→¬B)≥min_conf and(sup(A∪¬ B)-sup(A)sup(¬B))≥min_interest then

INAR=INAR∪{A→¬B};

if conf(¬ A→B)≥min_conf and(sup(¬ A∪B)-sup(¬ A)sup(B))≥min_interest then

INAR=INAR∪{¬ A→B};

}

if 0＜ρ≤1 then

{

if conf(¬ A→¬ B)≥min_conf and(sup(¬ A∪¬ B)-sup(¬ A)sup(¬ B))≥min_interest then;

INAR=INAR∪{¬ A→¬ B};

}

}

3)return INAR.

算法中步骤2)通过计算相关系数，并且如果满足最小兴趣度的值，此时才产生规则，并且产生的规则是用户感兴趣的.包括①计算相关系数;②满足相关系数条件和最小兴趣度的值，输出形如A→¬B，¬A→B，¬A→¬B的有趣的负关联规则;步骤3)返回结果INAR，结束整个算法.

表2 事务数据集

表3 关联规则数比较

5 实验

为了证明算法的有效性，考虑如表2所示的小型事务交易表［7］，其中包括10条交易数据和6个项.表中TID表示每条交易的标识符号，分别用 T1，T2，…，T10表示;表中的 A，B，…，F等分别表示每条交易所包含的对象．若以购物篮事务为例，如A，B，D表示的是顾客购买的商品的集合.具体的实验是基于Matlab的仿真效果.一般设min_sup=0.2，min_conf=0.40.表3中列出了本文算法与经典的Apriori算法的实验结果进行比较.

从表3中可以发现，经典Apriori算法得到正关联规则数是24，但无法发现负关联规则的存在;而通过本文的算法可以直接得到负关联规则数，正关联规则在运行中不出现，从而节省了一定的存储空间.同时根据表中所显示的当min_interest取0和0.05时，负关联规则数由39减少到12，被删除的负关联规则数明显增多，这说明提高最小兴趣度能够减少一些无意义的规则出现，删除了一些无意义的负关联规则数目，使得剩余的规则数目减少了，便于用户从中选择有意义的规则，从而保证了挖掘出来的负关联规则是用户感兴趣的，提高了负关联规则的挖掘的效率，因此此算法是有效的.

6 结语

本文通过实例引出传统的关联规则挖掘算法在挖掘过程中存在的问题，将兴趣度和相关系数两者进行结合，从一定程度上减少了大量无趣的负关联规则的产生.但是此种方法在一定程度上还存在一定的局限性，后将作进一步完善.

［1］ AGRAWAL R.Mining association rules between sets of items in large database［C］//Proceeding of the 1993 ACM SIGM OD International Conference on Management of Data.New York：ACM Press，1993：207-216.

［2］AGRAWAL R，SRIKANT R.Fast algorithms for mining association rules［C］//Proceeding of the 20th VLDB Conference.Santiago：Morgan Kaufmann，1994：487-499.

［3］ CORNELIS C，YAN Peng，ZHANG Xing，et al.Minning postive and negative association rules from large databases［C］//2006 IEEE Conference on CIS.Bangkol：IEEE，2006：613-618.

［4］TAN Pangning，STEINBACH M，KUMAR V.数据挖掘导论［M］.范明，范宏建，译.北京：人民邮电出版社，2006.

［5］ BRIN S，MOTWANI R，SILVERSTEIN C.Beyond market baskets：Generalizing association rules to correlations［C］//Processing of the ACM SIGMOD Conference.New York：ACM，1997：265-276.

［6］ SAVASERE A，OMIECINSKI E，NAVATHE S.Mining for strong negative association in a large database of customer transation［C］//In：Proceedings of the 1998 International Conference on Data Engineering.Orlando：IEEE，1998：494-502.

［7］ WU Xindong，ZHANG C，ZHANG S.Mining both positive and negative associations rules［C］//Proceedings of the 19th ICML.New York：Springer Verlag，2002：658-665.

［8］张倩，王治和，张国治.基于相关系数的正、负关联规则挖掘算法［J］.陕西理工学院学报，2005，21(4)：35-38.

［9］董祥军，宋瀚涛，姜合.基于最小兴趣度的正、负关联规则挖掘［J］.计算机工程与应用，2004，24(2)：24-27.

［10］汪际和，陈平，王新.一种基于信息表的关联规则挖掘方法［J］.云南民族大学学报：自然科学版，2010，19(6)：432-434.

［11］陈荣江.概率论与数理统计［M］.北京：北京大学出版社，2006.

［12］ SHAIRO P.Discovery，analysis，and presentation of strong rules［C］//G Piatetsky Shapiro，W Frawley eds.Knowledge discovery in Databases.AAAI Press/MIT Press，1991：229-248.