关联规则相关性的度量

摘要：用Apriori算法生成的关联规则包含有无用规则，甚至误导规则。为了使生成的规则更有效，引入了统计学中的卡方检验从统计意义上检验规则是否关联，并找到卡方检验值与相关系数的数量关系，实现了两种方法的统一，并用基于相关系数的算法去生成关联规则。

关键词：关联规则;相关度;卡方检验;相关系数

中图分类号：TP311.13;TP301.6文献标识码：

文章编号：1001-9081(2007)04-0892-03

0引言

在支持度―置信度框架下，关联规则是数据项同时满足最小支持度阈值（minsup）和最小置信度阈值（minconf）的规则。但用此框架产生的规则有些是多余的，有些甚至具有很强的误导性。

某超市一段时间内形成1000条交易记录，同时购买牛奶、可乐，只买牛奶，只买可乐，两者都不买的数据记入表

1。此表在统计学中称为列联表。

考察买牛奶与买可乐的关系：设minsup=0.3,minconf=0.6。

根据支持度―置信度框架得出是强关联规则，即买牛奶的人有66%的可能性会买可乐，增加牛奶的销量就会刺激可乐的销量。但事实果真如此吗？

再看不买牛奶与买可乐的关系：

产生上述现象是因为规则的置信度有一定的欺骗性，conf(AB)只是在给定A的情况下B出现的条件概率，并没有考虑B在整个数据集中出现的随机概率sup(B)。如果B的随机概率本身就很大，那么置信度大的规则就不一定是强蕴涵关系。所以单凭置信度不能将强蕴涵的关联关系从随机关系中分离出来。上例可乐的随机概率sup(可乐)=0.75>conf(牛奶菘衫)≈0.66,这意味着在买牛奶的前提下买可乐的概率比随机情况还少9%，显然是错误的。而conf(牛奶可乐)=0.875>sup(可乐)=0.75是正确的强蕴涵规则，因为不买牛奶会买可乐的概率从随机情况下提高12.5%。这时可以说牛奶和可乐是负关联的，一个出现会减少另一个出现的概率。另一种情况sup(A)=1,sup(B)=0.7,conf(AB)=0.7,conf(BA)=1,但显然A与B没有关系是独立的，也即置信度为1的规则并不一定是强关联规则。因此需要引入其他方法去度量两项间是否有关联及关联程度以减少弱关联规则,负关联规则。严格说关联与不独立的概念是一致的，不同于相关。关联包括各种关系而相关只指线性关系。本文介绍了卡方检验(独立性检验)，发现了对于二态变量关联性与相关性的关系，得出可通过度量相关性去获得关联规则。

1卡方检验

针对项集间的关联关系许多学者、专家进行了研究。Piatetsky―Shapiro提出了P―S兴趣度，interest=sup(AB)-sup(A)sup(B)。在文献[5]中作者对其进行了改进，综合考虑了用户主观偏好、规则准确度、规则相关度及兴趣度。文献[7]中作者提出用有效度代替置信度，validity=p(AB)-p(AB)。文献[4]中作者提出匹配度，match=conf(AB)-conf(AB)。以上方法均能在一定程度上减少无用规则产生，但不能准确度量关联程度，因而产生的规则仍有一定误导性。

2算法思想

3算法实验验证

为验证算法有效性，用Java语言编程对某超市事务数据库1000条数据进行了测试。结果发现算法能有效去除负关联和和弱关联规则。且在给定显著水平α时，置信度越小，两个算法生成的规则数量差别越大，随着置信度的提高差别缩小。最小置信度给定时，显著水平越小生成规则数量差别也小，随着α增大，差别变大。

以下给出试验中的60个事务，每个事务有五项，每一项已经进行了0-1标准化。并对比给出两个算法生成的规则。

4结语

本文通过实例分析了支持度―置信度框架的不足，主要在于置信度并不能很好地反应项集间的关系，从而产生冗余，甚至是错误的规则。为了准确清晰地度量关联程度，引入了统计学中的卡方检验，并找到了它和相关系数的关系。经证明Q2=n(ρAB)2，这样可通过计算相关系数去排除弱关联及负关联规则，同时本文也给出了可实现的算法。

本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。