数据挖掘中的负关联规则算法

《数据挖掘中的负关联规则算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、万方数据第24卷总第50期西北民族大学学报(自然科学版)vol·“，No32oo；年9月Jo哪aIofNormwestuniv蜘，ityforNationalities(NaturalScience)Sept，2003数据挖掘中的负关联规则算法袁玉波，程君华(西安交通大学理学院，陕西西安710049)_m．声√咿√^，hpq廊。牺_4．4_自—h，～，-m-“√“√^．自_“√“，‘_6一_6√h—、卢一_目一_‘—h，、，-6—“-6—、，～，h“∥‘_“_“—“[摘要]关联规则是数据挖掘的主要研究方面．已拄对关联规则的研览主要集中在挖掘征关联规则上．事实上，负关联规则在应用中

2、的地位也是非常重要的．[关键词]数据挖掘；负关联规则；算法【中田分类号]029[文献标识码】A[文章编号]1009—210212003}03—0007—05在做决策时，我们常常会面对大量的因素．这些因素对决策目标而言，可能是有利因素，也可能是不利因素．为了达到低风险高收益的目的，我们必须详细地考察这些因素的行为．当期望的有利因素出现时，而那些不利因素是否出现，要通过利用先前的数据掌握．因此，关联规则算法具有重要的应用价值．同时，我们也将考虑到挖掘正的和负的关联规则之间是有基本的区别．我们可以利用剪枝算法来减小搜索空间时，一些被剪掉的项集在提取负关联规则时有可能是有用的．所以我们在

3、本文中将介绍一种比较有效的算法来挖掘负关联规则．1负关联规则定义2．1J=Iil，i2，⋯，i。l表示项集、表示数据库中不同的特性．一个记录￡包含项集A当且仅当Vi∈A，都有i∈￡．一个集合的所有子集构成的集合成为这个集合的超集，记作21．数据库D中的任一项集A都具有一个支撑度。记做supp(A)，定义为supp(A)=lA(t)l／lDI．这里A(t)=I￡∈Dt3A1．ID1表示D中包含的元素的个数．当一个项集的支撑度大于或等于给定的最小支撑度时，这个项集被称为频繁项集．A、B之间的负关联规则由A一一B产生，一个有效的负关联规则必须满足以下三个条件：1)AnB=日；2)sup

4、p(A)≥minsupp和supp(B)≥minsupp；3)supp(AU—B)≥mimupp(或supp(一AUB)≥minsupp，或supp(一AU—B)≥minsupp)．这里条件2)可以保证负关联规则在概率上的有意义性，其他的条件保证规则是有效的．通常，一个非频繁项集i被称为一个负项集，如果至少存在一个表达式i=AUB，使得A和B满足以上的三个条件．引理2．1(Piatetsky—Shapiro论断)令f是数据库TD中的一个项集，x，y∈j是项集，xny=口，supp(X)≠0，supp(Y)≠0，minsupp，minconf和mininterest>0由用户或专家

5、给出．那么x—y可以被提取为一个有意义的规则，如果1)supp(xUY)≥minsupp，2)supp(Yx)≥minconf，和[收稿日期】2003一惦一12[作者简介]袁玉渡(1976一)，男，云南昆明人，在读博士生，主要从事数据挖掘方面的研究万方数据3)IsuPP(xUB)一supp(x)supp(Y)l≥mininterest．由Piatetsky—Shapiro论断，如果supp(AU—B)一supp(A)supp(一B)≥mininterest，则称规则A一一B是有意义的．因此如果1)An马=目；2)supp(A)≥minsupp和supp(B)≥minsupp，和s

6、upp(AU—B)≥minsupp，3)supp(AU—B)一supp(A)supp(一B)≥mininterest，4)supp(AU—B)／supp(A)≥minconf．那么A一一B是一个有效的有意义的负关联规则，这里mininterest是由用户指定的一个最小的有意义值．AUB是一个有意义的负项集，否则A一一B是没有意义的，AUB是一个无意义的项集．这样，无意义的项集是数据库中任何除正的和负的有意义项集外的项集．当我们挖掘时，这样的项集必须被剪枝以缩小搜索空间．在另一方面，如果i是一个有意义的负项集，则至少有一个表达式i=AUB，使得规则之一：A一一B，一A一一B，一A—

7、B是一个有意义的负关联规则．然而，有很多关系到关联规则的频繁项集是无意义的．如果提取出来的项集仅仅处理正的和负的有意义的项集，搜索空间将被大大地减小，因此，下一部分的算法将仅集中在搜索给定数据库中有意义的频繁项集上．2算法经典的Apriori算法仅仅识别频繁项集，不包括任何非频繁项集．另一方面，它仅仅用一点探索性的信息来搜索一个给定的数据库中包含的项和项集这样一个成指数的空间．然而，当频繁项集的数目很大的时候，这个算法将耗费大量的计算工作量．由于这个原因，本文将介绍一个有效的算法