一种双向关联规则提取算法.doc

文档介绍：一种双向关联规则提取算法摘要:针对互为“前件”和“后件”的单向关联规则中发现的有趣现象,提出双向关联规则的概念,对“置信度”进行了重新的定义和分类,并在分析的基础上,提出一种双向关联规则的挖掘算法。关键词:双向关联规则;左置信度;右置信度;强双向关联规则;强弱双向关联规则;频繁项集中图分类号:TP311文献标识码:A文章编号:1009-3044(2009)05-1204-03 AExtractionAlgorithmofTwo-wayAssociationRules YUANCai-hong,ZHANGLian-tang (ComputerandInformationEngineeringCollegeofHenanUniversity,Kaifeng475004,China) Abstract:Againsttheinterestingphenomenonfoundintheone-wayassociationrulesinwhichone's‘beforetherule'isother's'aftertherule',itputforwardtheconceptoftwo-wayassociationrulesand"confidence"tobecarriedoutare-,atwo-wayalgorithmforminingassociationrulesisputforword. Keywords:two-wayassociationrules;leftconfidence;rightconfidence;strongtwo-wayassociationrules;strong-weaktwo-wayassociationrules;frequentitemsets 1引言关联规则最早是由Agrawal等人提出的[1],最初提出的动机是针对购物篮分析问题提出的,其目的是为了发现交易数据库中不同商品之间的联系规则,这些规则可以用来指导商家科学地安排进货、库存及货架设计等。关联规则是形如X→Y的蕴含表达式,其中X和Y是不相交的项集[2]。传统关联规则挖掘是单向的[3],在这些单向规则中我们发现一些有趣的规则,比如:“牛奶→面包(sup=75%,conf=91%)”和“面包→牛奶(sup=75%,conf=95%)”,两个规则都具有较高的支持度和置信度,说明两者总同时出现;现有的关联规则提取算法会把低置信度的规则滤掉,原因是认为它对决策者提取的信息意义不大,但是,如在电脑器材销售数据库上的两条规则:“个人电脑→U盘(sup=67%,conf=95%)”和“U盘→个人电脑(sup=67%,conf=10%)”,其中第一个规则具有较高置信度,而后面的规则支持度较低,说明个人电脑的销售,对于U盘具有促销作用,而大多购买U盘的人不会购买个人电脑,这样一对关联规则对商家来说,也是非常有意义的。本文提出一种双向关联规则提取算法,以挖掘那些在某些领域会更有意义的规则。 2基本定义和定理在后面介绍过程中,会用到的定义和定理如下: :设D为事务数据库,I是D上的项目集,称“U?圮V”为双向关联规则,其中,U?奂I,V?奂I,并且U∩V=∮。其中,U、V