文档介绍：分布式环境基于相似度的关联规则挖掘模型的研究
摘要：介绍了关联规则挖掘的基本原理和方法，详细分析了分布式关联规则挖掘算法并给出其模型；提出一种充分考虑数据源异构性、基于相似度的的分布式数据挖掘方法。实验证明该模型提高了挖掘的准确率。
关键词：数据挖掘；关联规则；相似度；分布式系统
中图分类号：TP301．6文献标志码：A
文章编号：1001－3695(2008)03－0695－03
在分布式技术处理日益成熟的今天，网络数据的处理量也在不断增长。由于这些数据很多时候都是分散在不同的地方，挖掘大量分布式数据就需要研究出一种有效的分布式算法。分布式数据库系统关联规则的挖掘有其自身的特点，对其进行关联规则的挖掘需要专门的挖掘算法来实现。国际上的数据挖掘研究者已经对此作了一些研究。目前已有的数据挖掘算法包括Kargupta等人[1]提出的集体数据挖掘、Yamanishi[2]提出的分布式协作贝叶斯学****策略、Cheung等人[3]提出的分布式数据库中的有效挖掘关联规则。这些已有的DDM技术还有许多局限性：虽然目前的很多DDM(distributed data mining)技术使用各种标准和方法，将来自分布式数据源的原模型尽量优化，而且在同构数据挖掘方面已经相当成熟，但对于分布式数据源的异构性仍然不够成熟。本文提出一种基于相似度的分布式关联规则挖掘模型作为新的数据挖掘模型。其基本思想是：充分考虑到分布式数据的异构性，首先通过计算相似度将得到的数据集按照相似度进行分组；然后在分布式环境下使用已有的关联规则挖掘方法得到更加有效准确的关联规则。
1关联规则挖掘的基本概念及改进的apriori算法
1．1关联规则挖掘
关联规则挖掘就是从大量的数据中挖掘出有价值的描述数据项之间相互联系的有关知识。它是数据挖掘中最基础也是最流行的一种数据挖掘方法。假设I={I1,I2,…，Im}是一组数据集，对于给定的事务数据库D，其中的每个事务对应一个惟一的事务标志和一组项目集itemsets（I??itemsets）。关联规则是如下形式的一种蕴涵：X??Y。其中itemsets??X，itemsets??Y，且X∩Y=?痢?
在这种表示规则下，其支持度、可信度、期望可信度、作用度可定义如下：
a)支持度。规则X??Y的支持度定义为事务数据库中同时包含项目集X和Y的事务百分数。即若事务数据库D中有s%
的事务同时支持项目集X和Y，则s%就称为规则X??Y的支持度。支持度描述的是项目集X和Y的并集在事务数据库中出现的概率。
b）可信度。规则X??Y的可信度定义为在包含项目集X的事务中，同时也包含项目集Y的事务的百分数。即若在包含项目集X的事务中有c%的事务也同时包含了项目集Y，则c%就称为规则X??Y的可信度。可信度指出了在出现项目集X的事务中，项目集Y同时出现的概率有多大。
c）期望可信度。规则X??Y的期望可信度定义为事务数据库中包含项目集Y的事务的百分数。即若在事务数据库D中，如果有e%的事务支持项目集Y，则e%就称为规则X??Y的期望可信度。期望可信度描述的是在没有任何条件影响时，项目集Y在所有事务中出现的概率有多大。
d）作用度。规则的作用度定义为可信度和期望可信度的比值。它描述的是项目集X的出现对Y的出现有多大的影响。作用度越大，说明项目集Y受X的影响越大。
1．2Apriori算法
关联规则的挖掘问题就是在事务数据库D中找出具有用户给定的最小支持度和最小可信度的关联规则。Apriori算法主要任务是找出存在于事务数据库中的所有频繁项目集。
1．3改进的AprTidRec算法
针对apriori算法中一些不足之处，目前提出了许多优化方法来改进算法，包括
AprioriTid和AprioriHybrid等。这些优化算法主要从三个方面来提高算法的执行效率：减少扫描数据库的次数；减少生成候选项目集个数或不生成候选项目；采用新的存储结构。
在本文中主要采用第三种方法，即通过采用一个记录的存储结构来减少需要扫描数据库的次数，从而达到优化算法的目的。它的基本思想与apriori算法相似，不同之处在于后者在生成频繁集时包括连接步和剪枝步，而前者只需连接步即可。先对每个候选项集定义一个tidRec的记录结构，项集I的tidRec由数据库中包含I的交易的TID组成，。1项集的tidRec可通过搜索事务数据库得到。算法中记录的结构为〈I,tidRec,count〉。；count的值等于tidRec的