文档介绍：挖掘关联规则的快速算法(英) Rakesh Agrawal Ramakrishnan Srikant ? I BM 阿尔马丁研究中心圣塔克莱拉市 6 5 0 亨利道 9 5 1 2 0 证???针对找出销售交易中大量数据库里项目之间的关联规则问题,我们提出两种与已知算法完全不同的新的算法来解决此问题. 观察数据表明:这两种算法在从小问题的三个到大问题的多个度量的因子上都优于先前的算法. 根据这两种算法的特点,我们还指出如何将它们合并才是一个最佳的混合算法,称为 AprioriHybrid 算法. 按比例增大实验证明 AprioriHybri d 算法是随着交易数量按线性比例递增的, ??条形码技术的广泛应用使得零售商在收集和存储大量商品的价格数据时十分方便,简称为货篮数据. 一条这样的数据记录通常都包括某个顾客的交易日期, 交易中所购的物品项目. 成功的组织者视这种数据库为贸易市场基础结构的重要组成部分. 他们专注于研究用数据库技术来推动市场信息化过程,这样市场经营者就可以有能力发展及实施为顾客制定购买产品的方案和策略[6] . 有关在货篮数据上挖掘关联规则的问题在[4] 中已作介绍. 举个例子:可能有 98% 的顾客在购买轮胎和汽车配件的同时接受了有关汽车的服务. 找出所有这样的规则对于促进市场营销和提高顾客购买力是非常有价值的. 另外还有价目表设计,商品上架设计,进货安排,根据购买行为模式对顾客进行分类. 但这些应用中的数据库都是极其庞大的,因此,寻找一种快速的算法来完成此项任务是我们的当务之急. 以下是关于这个问题[4] 的一个表述:令I ={ 1 2 , , , m i i i ?}是m 个不同项目的集合, 给定一个事务数据库 D , 其中每一个事务 T 是I 中一些项目的集合, 且都与一个唯一的标识符 TID 相联. 如果对于 I 中的一个子集 X ,有X?T , 我们就说事务 T 包含 X . 关联规则是形如???????????????全部或部分材料允许被免费拷贝, 这些拷贝不是为直接的商业优势而制作的, VLDB 的拷贝权是由 VLDBE 授予的. 另外,拷贝或重新出版还需要金额和 VLDBE 的允许. 第 20 届极大数据库程序会议智利圣地亚哥? 1994 1 YX?的蕴含式, 其中IYX?, ,且YX?=?. 如果事务数据库 D 中有 c % 的事务包含 X 的同时也包含 Y ,则称关联规则 YX?的置信度为 c %. 如果事务数据库 D 中,有 s % 的事务包含了 YX?, 则称关联规则 YX?具有支持度 s %. 这个规则在我们讨论多项集的问题时比[4] 中的阐述要简单很多. 给定一个事务集 D ,挖掘关联规则的问题就是产生支持度和置信度分别大于用户给定的最小支持度和最小置信度的关联规则. 我们对事务集 D 的内容属性方面不加以讨论, 比如说, D 可以是一份数据文件,也可以是一张关系表,或者是一个关联表达式的结果. 找出所有关联规则中的算法, 我们称文章[4] 提出的为 AIS 算法, 文章[13] 提出的为 SET M 算法. 在本文中, 我们介绍两种新的算法: Apriori 和 AprioriTid 算法, 基本上与先前的算法不同. 我们将用实验结果证明这两种算法优于先前算法. 它们之间的差距主要体现在问题大小的增大及问题范围从小问题的三个到大问题的多个度量的因子上变化. 接着我们讨论由 Apriori 和 AprioriTid 算法合并而成的混合算法( AprioriHybrid 算法)是如何的优异. 实验证明 AprioriHybrid 算法具有良好的递推性能,开启了挖掘关联规则在数据库中应用的可行性. 找出关联规则属于数据库挖掘范畴[3,12] ,也称为数据库中的知识发现[21] . 类似地,但不直接可应用的工作还包括分类规则的介绍[8,11,22] ,因果关联规则的发现[19] ,学习逻辑定义[18] ,函数的数据拟合[15] 以及簇[9,10] . 非公开性的有关机器学习文献的作品是在[20] 中的 KID3 算法. 如果应用在查找所有关联规则问题上, 这个算法在与假定关联项的数目一样多的数据上进行运算时,运算量非常大. 最近在数据库上的研究工作是由数据出发来定义关联函数[16] . 函数关联规则需要十分严格的条件. 因此,定义一种函数规则为 AX?后,在[ 16] 中描述的算法若从规则 AYX??来考虑, 就无法推出. 我们考虑的这些关联规则要符合实际性质. 规则AX?的存在并不意味着 AYX??也成立,因为后者可能不具备最小支持度. 同样的,规则 YX?和ZY?的存在也不意味着 ZX?成立,因为后者可能也不具备最小