第３１卷第２期２０１０年３月
吉首大学学报（自然科学版）
ＪｏｕｒｎａｌｏｆＪｉｓｈｏｕＵｎｉｖｅｒｓｉｔｙ（ＮａｔｕｒａｌＳｃｉｅｎｃｅＥｄｉｔｉｏｎ）
Ｖ０１．３１Ｎｏ．２
Ｍａｒ．２０１０
文章编号：１００７—２９８５（２０１０）０２—００３８—０５
数据挖掘中关联规则集的优化
高永惠
（怀化学院计算机系，湖南怀化４１８００８）
摘要：尝试重新定义了正关联规则和负关联规则，并给出它们的兴趣度，从而统一了正、负关联规则的评价标准．在此基础上，采用逻辑的方法查找极小矛盾集以判定关联规则集的一致性，通过修改极小矛盾集中的规则消除关联规则集的不一致，从而优化原有的关联规则集．
关键词：数据挖掘；关联规则；评价中图分类号－ＴＰ３１１。ｌ
文献标识码：Ａ
通常数据挖掘所得到的关联规则都是肯定的规则，否定的关联规则的加入扩充了规则集的表达能力，然而，它可能导致规则集的不一致．类似地，文献［１—２］提到的否定的关联规则ｂｕｙＲｕｆｆｌｅｓ－－－ｂｕｙＰｅｐｓｉ和ｂｕｙ
ｔｅａ－－－ｂｕｙ
ｃｏｆｆｅｅ也可能导致规
则集的不一致．文献Ｅ２］已经提到规则的不一致问题，认为也许是“支持度一置信度”框架的缺陷造成的，但他们并没有进一步研究．实际上，即使所有规则都符合正性相关，负规则的引入仍然可能导致规则集的不一致，使得人们无从使用所挖掘出的关联规则．文献［３１提出对正关联规则和各种形式的负关联规则分别设置不同的最小置信度；文献［４］提出使用两级支持度来约束正负关联规则的挖掘．更多的是采用对满足最小支持度和最小置信度的规则再进行相关度度量，这些做法不仅繁琐，还容易遗漏一些有价值的关联规则．
笔者对初始关联规则集∑进行尽量少的修改得到一致的规则集合∑Ｍ，并进一步扩充关联规则的表达能力．从目前的关联规则价值衡量方法可以看出，客观层面考虑的是单条规则的前件和后件之间的关系，主观层面考虑的是用户的兴趣取向，而整个规则集各规则之间的关系并没有被考虑，所以不可能发现和处理规则之间存在的矛盾．笔者尝试考虑规则之间的相互关系，以解决关联规则集的不一致问题，并且认为这对数据挖掘方法本身以及用户有效地利用关联规则是有积极意义的．
１基本概念
设ｆ＝｛ｉ，，ｉ：，…，厶）是项集，记Ｄ为事务Ｔ的集合，事务Ｔ是项的集合，并且Ｔ篁Ｉ．对应每一个事务有唯一的标识，如事务号记作订Ｄ．设Ｘ是ｆ中项的集合，如果Ｘ∈Ｔ，那么称事务Ｔ包含Ｘ．
定义ｌ
正关联规则是形如Ｘ—ｙ的蕴涵式，其中Ｘｃｊ，ｙｃ，，并且ＸｎＹ＝现负关联规则是形如Ｘ一］ｙ的蕴涵式，其中ＸｃＪ，ｙｃＪ，并且ＸｎＹ＝统
正、负关联规则的兴趣度（ｉｎｔｅｒｅｓｔ）是规则前件成立时后件发生的概率与规则前件不成立时后件发生的概率
Ｘ）一Ｐ（Ｙ
定义２
定义３
的差值，即Ｉｎｔ（Ｘ—ｙ）＝Ｐ（Ｙ
Ｘ）．
Ｉ］Ｘ），Ｉｎｔ（Ｘ一］聊＝Ｐ（７
Ｙ
Ｘ）一Ｐ（７Ｙ
１
Ｘ）＝Ｐ（ＹＩ］Ｘ）一Ｐ（Ｙ
可以采用下述方法计算正、负关联规则的兴趣度．其中Ｃｏｕｎｔ（ＹＵＸ）表示数据集中同时包含ｘ和ｙ的事务数，Ｃｏｕｎｔ（Ｘ）表示数据集中包含ｘ的事务数，Ｃｏｕｎｔ（Ｙ）表示数据集中包含ｙ的事务数，Ｃｏｕｎｔ（Ｄ）表示数据集中的事务总数．只要计算出Ｐ（Ｙ
Ｐ（Ｙ
Ｘ）和Ｐ（ＹＩ］ｘ），就可以计算出正、负关联规则的兴趣度：
１
ｆ的＝Ｃｏｕｎｔ（ＹＵＸ）／ＣＯｕｎｔ（Ｘ）；Ｐ（ＹＸ）＝（Ｃｏｕｎｔ（ｙ）一Ｃｏｕｎｔ（ＹＵＸ））／（Ｃｏｕｎｔ（Ｄ）一Ｃｏｕｎｔ（Ｘ））．
文中定义的兴趣度具有以下性质：
＊收稿日期：２０１０—０２—１２
作者简介：高永惠（１９６２一），女，湖南常德人，怀化学院计算机系讲师，主要从事计算机应用及教学研究．
第２期
性质１性质２性质３性质４性质５
性质６
高水惠：数据挖掘中关联规则集的优化
兴趣度（ｉｎｔｅｒｅｓｔ）的取值范围是［～１，１］．ｉｎｔｅｒｅｓｔ—ｏ，规则前件和后件无关．ｉｎｔｅｒｅｓｔ＞ｏ，规则前件和后件正相关．ｉｎｔｅｒｅｓｔ＜Ｏ，规则前件和后件负相关．
ｉｎｔｅｒｅｓｔ＝１，规则前件是后件的充分必要条件．ｉｎｔｅｒｅｓｔ＝一１，规则前件是后件的非的充分必要条件．
３９
文中重新定义了肯定、否定的关联规则，并且定义了它们的兴趣度．包含正、负关联规则的规则集是关于兴趣度的全序集，所以可以将兴趣度作为正、负关联规则统一的价值衡量标准．
为了便于考虑规则间的关系。选用命题逻辑［钼语言来描述正、负关联规则．正关联规则ｘ—ｙ可以写为形如ｉ１Ａ
∈Ｙ，ｉｓ
ｉ２
Ａ
ｉ３…一“１＾妇＾“３…的蕴涵式，其中ｉｌ，ｉｚ，ｉ３．． ∈Ｘ，“１，谝，ｉ一…
Ａ
Ａｉ２Ａｉ３…为规则的前件，ｉＨｌ＾ｉ啪＾瓴３．． 为规则的后件．
ｉ２
负关联规则ｘ一１ｙ可以写为形如ｉ１Ａｏｚ，ｉＭ…∈Ｙ，ｉ１Ａ
定义４
ｉ２
ｉ３…一］“１＾］“＾］０３．． 的蕴涵式，其中ｉ１，ｉ２，ｉ。…∈Ｘ，“１，
Ａｉ３．． 为规则的前件，］讧１＾１如＋２＾］缸＋３…为规则的后件．
规则集∑是矛盾的，当且仅当存在前提ｘ能在∑中推出结论Ｙ和］弘卜６｜，即∑ｕ｛ｘ｝一且∑ｕ
称规则集ｆ是极小矛盾集，当且仅当Ｊ’是矛盾的且ｒ的任意真子集都是一致的［７］．
｛ｘ｝ｈｙ．如果规则集＞：不是矛盾的，那么是一致的．
定义５
定理１
关联规则集≥：是一致的，当且仅当不存在极小矛盾集ｒ互≥：．
２
优化的解决方法
文中主要解决的问题是找出关联规则集≥：中的每个极小矛盾集．首先是采用纯文字删除法压缩子句集，通过使用支
２．１方法概述
持集策略对压缩后子句集进行归结得到备选矛盾集，进而从备选矛盾集中找出极小矛盾集．为得到一致的关联规则集合，最简单的方法就是在每个极小矛盾集中删除１条规则．因为产生极小矛盾集时删除了一些规则，所以通过扩充修改关联规则集来增强表达能力．