论文部分内容阅读
数据挖掘是研究从大量数据中发现有用知识的理论与方法,它是目前国际上数据库和信息决策领域的最前沿研究方向之一。关联规则是数据挖掘中一个较早的、有意义的研究课题之一。在关联规则的挖掘过程中,频繁项集挖掘是整个挖掘过程的基础,也是整个挖掘的核心,如何高效和有效的挖掘频繁项集一直以来就是研究人员关注的热点。但是,在实际应用中,由于大数据的存在和频繁项集数量巨大,从而阻碍了频繁项集的广泛应用。因此,如何对频繁项集算法进行优化和对频繁项集进行压缩成为了当前研究的一个重要方向。 本文首先介绍了数据挖掘的相关背景和当前国内外研究现状,随后简单的介绍了关联规则和频繁项集的基本挖掘技术,同时,简要分析了频繁项集的压缩技术和常用频繁项集压缩方法的比较。最后,本文提出了基于贪心策略的Top-K频繁项集挖掘算法NFIMG算法和由NFIMG算法衍生结合闭合节点性质剪枝的Top-K闭频繁项集挖掘算法NCFIMG。 (1)本文提出的NFIMG算法。该算法基于贪心策略生成的频繁链表,抛弃了人工对于最小支持度的干预,只需一次遍历数据库操作,使用生成即所得的挖掘方式进行Top-K频繁项集的挖掘。并且,文中通过理论证明了该算法的可行性和时间及空间的优越性。最后,通过采用UCI数据集对比实验证明了该算法性能的优越。 (2)本文提出的挖掘Top-K频繁闭项集的NCFIMG算法。该算法本质上基于本文提出的NFIMG算法,同时,结合闭项集的性质进行挖掘,过程中依据的“闭合节点”引理进行剪枝操作。之后,本文在理论证明了该算法的正确性,通过对比试验证明了该算法在时间和空间上优越性。同时,该算法思路清晰,易于实现,并且可以和NFIMG算法在挖掘过程中进行挖掘类型转换。 本文对所提出的算法进行了广泛的对比试验。分别在UCI机器学习库中的多个数据集以及IBM数据生成器上生成的数据集上进行了对比试验。实验结果表明,与Apriori,NApriori算法相比,本文所提出的NFIMG算法在空间复杂性和时间复杂性都要略逊一筹。同时,改进算法NCFIMG在与TFP算法等的比较中,在挖掘效率和存储空间上的优势也非常明显。实验结果表明本文所提出的NCFIMG算法在进行长项集的挖掘时更有效率。这些研究成果为频繁项集在实际问题中的应用提供了一种有效的解决问题的途径。