多数据库中的间接关联规则挖掘算法

段巧灵++李芬++张莉

摘要：随着多数据库技术的快速发展，在多个数据库中获取有效信息显得尤为重要。现有技术都是在一个数据库中挖掘间接关联规则。采用投票率作为规则兴趣度量来提取全局间接关联规则，并在此基础上定义了相对支持度和方差来衡量间接规则的强度，以从多个数据库中挖掘有效的间接关联规则。最后通过实验验证了该方法的有效性。

关键词：间接关联规则；数据挖掘；多数据库；投票率

DOIDOI：10.11907/rjdk.161920

中图分类号：TP312

文献标识码：A文章编号文章编号：16727800（2016）009004902

作者简介作者简介：段巧灵（1986-），女，湖南衡阳人，硕士，武汉晴川学院计算机学院助教，研究方向为数据挖掘、机器学习。

0引言

关联规则作为数据挖掘的重要领域之一，由R Agrawal[1]在1993年首次提出。关联规则是通过频繁项集的挖掘来获取的，却忽略了其中的非频繁项集。例如，在超市的商品交易中，如果数据项对（A，B）频率非常低，但是（A，C）和（B，C）出现的频率却非常高，可称为间接关联规则[2]，即（A，B）通过中间集C间接关联。间接关联规则提供了非常有价值的信息，可以应用在很多方面，如对文本的查询进行分类、市场营销、Web日志挖掘和股票分析等。

目前，现有技术都是在单个数据库中挖掘间接关联规则。随着多数据库技术的快速发展，在多个数据库中挖掘间接关联规则显得尤为重要[3]。本文致力于挖掘多数据库中的间接关联规则，即挖掘全局的间接关联规则。使用投票率作为标准选取有效的全局间接关联规则，并通过计算各个有效的间接规则的支持度方差对其进行排序，以供决策者使用。最后设计了相关算法，实验结果证明了该算法的有效性。

1相关工作

1.1问题描述

间接关联规则是形如的一个表达式，其中A，B，MT，A∩B=Φ，项对（A，B）依赖中间项集M而存在，称项对（A，B）通过中间集M间接关联。挖掘间接关联规则即找出满足条件的中间项M：

（1） sup（A，B）≤ts

（2） sup（A，M）≥tf，sup（B，M）≥tf，dep（A，M）≥td，dep（B，M）≥td

其中，dep（A，B）=P（A∩B）[]P（A）*P（B）表示项集之间依赖关系的强度，ts、tf、td分别称为项对支持度阈值、中间集支持度阈值、依赖度阈值。通常设置tf≥ts。

1.2间接关联规则挖掘技术

现行的间接关联规则挖掘研究主要针对提高开发效率和扩展定义两方面[46]。间接关联规则是由P N Tan等在文献[2]中首次提出。通过频繁项集挖掘间接关联规则，主要分为以下两步：①用标准的频繁项集挖掘算法获取所有频繁项集，如Apriori算法；②通过检查由频繁项集产生的候选关联规则来发现有效的间接关联规则。

显然，通过挖掘所有频繁项集来获取间接关联规则非常费时。Wan在文献[4]中提出了一种基于HIstruct的数据模型，通过HI-mine算法来提高间接关联规则挖掘效率；Chen等在文献[5]中考虑到数据项的生命周期，探索出一种新模式并用MGGrowth算法来挖掘间接关联规则；Ouyang等在文献[6]中考虑到不同角色在现实世界中的应用，提出一个间接的加权关联规则模型来扩展间接关联规则挖掘模型。

2多数据库中的间接关联规则挖掘

在多数据库中挖掘有效的间接关联规则主要包括以下3个步骤：①对多个数据库使用聚类算法进行分类；②对每个数据库进行间接关联规则挖掘；③挖掘多个数据中的全局间接关联规则。

下文详细阐述了多数据库挖掘的第3个步骤。在科学研究及应用中，对于规则的选取可以采用投票来决定。一个规则投票数越多，则表示该规则可靠性越高。因此，多数据库中的全局间接关联规则是以投票率作为标准来挖掘的。