基于数据分割的几种关联规则采掘算法的探讨

《基于数据分割的几种关联规则采掘算法的探讨》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、山东大学硕士学位论文基于数据分割的几种关联规则采掘算法的探讨姓名：闫中敏申请学位级别：硕士专业：计算机软件与理论指导教师：李庆忠2001.4.28基于数据分割的几种关联规则采掘算法的探讨基于数据分割的几种关联规则采掘算法的探讨研究生闰中敏指导教师李庆忠教授摘要～，』I随着计算机应用的不断发展，海量的数据资料积累下＼来，以往的数据分析方法不能有效的从中发现有价值的信息，为了解决这一问题，数据采掘发展了起来。通过数据采掘，我们可以从十分繁杂的资料中发现有价值的信息或知识，达到为决策服务的目的，因此数据采掘成为目前国际上数据库和信息决策领

2、域的最前沿研究方向之一，它同数据仓库和数据存储被认为是当今三大数据库新技术。数据采掘所获得的知识其表达形式是多种多样的，通常可以是概念、规则、规律、模式、约束或可视化信息等，这些知识可以直接辅助决策过程：或修正已有的知识体系：也可以作为新的知识转存到知识存储机构中。基于数据分割的几种关联规则采掘算法的探讨关联规则采掘是数据采掘中的一个重要课题。关联规则是表示数据库中对象之间某种关联关系的规则，它提供的信息可用作商品销售目录设计，商场布置，针对性市场营销等。有关关联规则采掘的算法中但较为权威的算法则是R．Agraval等提出的Apri

3、ori算法，其基本思路是重复扫描数据库，每次生成一定长度(k)的大项目集L，再根据得到的h产生长度为k+l的项目集备选集C。下次对数据库进行扫描时仅对C。中的项目集计数，以得到k，，在所有的大项目集求出后，再根据公式计算得出符合条件的关联规则。可以看出，关联规则采掘的过程是一个对数据库中数据的统计过程，其挑战性在于数据量巨大，算法的效率是关键。围绕着怎样精减各选集的大小和减少对数据库的扫描遍数，有许多新技术应用到关联规则采、7掘中，如哈希技术、数据分割、抽样等等。1}本文提出了三种基于数据分割的关联规则采掘算法：算法PA、算法RP和

4、算法IMA，这三种算法的思想不同，解决问题的方式方法不同，它们分别适用于不同的采掘任务。由于引入了数据分割的技术，使得算法可以在分割后得到的块上并行执行，虽然在这种思路下的采掘算法需要协调不同的分割所得出的中间结果，但由于并行的计算可以分别在不同的计算机上进行，·这就使得每一分割的规模缩小，相对的可使用内存扩大，对提高算法效率是有很大帮助的。基于数据分割的几种关联规则采掘算法的探讨{算法PA是在Apriori算法基础上改进的一种算法。它虽然采纳了循环扫描数据库k次的思想，但由于引入了分割，可以通过用每一分割上所有k～重项目集(既是某

5、一分割上的大项目集，并且也是全局大项目集，其长度为k)的集合来生成此分割上的备选集，将每个分割上得到的备选集求并集，可以证明所有的全局大项目集都包含在这个并集中。这样就使得PA中得出的备选集既小于hpriori算法中的备选集，也小于分割算法中的备选集，从而减少了扫描数据库过程中的计数基数，即减少了计算过程中的内存占用；根据“如果x是某一分割的重项目集，则x是这一分割上的局部大项目集”，就可以对备选集中的项目集进行消减，去除那些在备选集中，但并不是本分割的局部大项目集的项目集，这样做可以有效的缩减备选集数目：算法的不足之处在于此算法对

6、数据库的循环次数与项目集长度有关，在算法执行前无法确定。因此算法PA适用于项目集长度固定的采掘任务。RP算法则采用了DIC算法的基本思想，对于不同长度的项目集并行计数，即每次读取数据库的一部分(一个分割)，读第一部分时只对卜项目集计数，读第二部分对1、2一项目集计数，顺次增多，这种思想缩减了对数据库的扫描遍数(可以证明整个算法需要对数据库扫描(k+2m一2)／m遍，其中m为数据库的分割数目)，大大降低了数据I／0操作次数：由于2一备选集的大小会大大影响采掘的性能，扫描过程中对各选集中的每一个局部卜大项目集，利用交易号序列集合记录包含

7、该基于数据分割的几种关联规则采掘算法的探讨项目集的交易标号，这样就可以直接得到局部2一大项目集，这样，就减小了所有的2一备选集，虽然此处采用了分割算法中交易号序列的思想，但只是在第一遍扫描过程中，并未造成过重的内存负担；算法中也根据消减项目集的原则对得到的备选集作了处理，但备选集中的项目集数目依然相对较大，这也正是这个算法的不足之处。算法RP适用于数据库中的项目基数相对较少，但数据库规模较大的采掘任务。IIVL^_算法引入项目集集合正界的概念，将每一个分割上局部大项目集的正界作为分割中所有项目集的浓缩，它包含了所有可能是大项目集的项

8、目集，将所有局部大项目集的正界合为整个数据库的正界，作为整个数据库的备选集，可以证明所有可能是大项目集的项目集都包含在整个数据库的正界中，可以将整个数据库的正界作为一种中间结果保存在数据库中，数据库修改时自动修改：并且算法借用了以往关