论文部分内容阅读
随着信息技术的发展,数据信息呈现爆炸式的增长。为了从海量数据中获取有用的信息,数据挖掘成为当今数据库研究方面最具活力的领域。关联规则挖掘是数据挖掘领域一个重要的研究方向,这项技术广泛应用于各大领域,有着极其重要的应用价值。随着数据集的大小和复杂性的增长,如何提高关联规则挖掘算法对大规模数据集的挖掘效率成为关联规则挖掘研究的核心问题。经典的关联规则挖掘算法Apriori算法是当前关联规则挖掘算法研究的热点。基于矩阵的Apriori算法相比Apriori算法减少了扫描数据库的次数,提高了计算支持度计数的效率,但仍然存在候选集过多,矩阵占用内存空间过大等问题。本文针对已有的基于矩阵的Apriori算法的不足,提出了一种改进的基于压缩矩阵的Apriori算法——NCMA。主要工作内容包括以下几个方面:(1)首先了解关联规则挖掘算法的背景和发展现状,重点探讨了Apriori算法及其改进算法的优缺点,分析了现有基于Apriori的改进算法存在的问题。(2)详细分析了基于矩阵的Apriori算法及其改进算法,发现改进的基于矩阵的Apriori算法仍然存在多次扫描矩阵、为减少候选集数量增加过多额外计算时间、矩阵压缩得不够彻底、挖掘结果的精确度不高、算法设计过于复杂等问题。(3)针对不足之处,提出一种改进的基于压缩矩阵的Apriori算法——NCMA。算法从矩阵存储、项集排序、矩阵压缩、支持度计数的计算、算法结束条件五个方面进行改进,并通过实例分析证明算法的正确性。(4)将NCMA算法和Apriori算法、CMApriori1算法从理论上和实验上进行分析比较,理论和实验结果都证明了NCMA算法能有效地减少扫描矩阵的次数,大大压缩了矩阵规模,减少了候选项集的数目,提高了挖掘频繁项集的效率。该算法在挖掘密集型数据库时比现有的基于矩阵的Apriori算法具有更高的运行效率和可伸缩性。