论文部分内容阅读
数据库的规模急剧膨胀，数据库应用的不断深化，但是数据库管理系统却没有提供有效的工具和方法来利用这些数据，出现了数据丰富而知识贫乏的状况，导致了数据挖掘的出现。作为数据挖掘中重要任务之一的频繁模式的挖掘，被应用在关联规则、相关分析、序列模式、显露模式、最长模式等许多重要数据挖掘任务中，得到了广泛研究。 长期以来，挖掘频繁模式主要采用Apriori算法及其改进形式，这类算法需要产生大量候选项集，并反复扫描数据库，降低了挖掘的效率。FP-Growth算法是一种基于模式增长的频繁模式挖掘算法，避免了大量候选项集的产生，只需要两次扫描数据库。效率比Apriori算法快一个数量级。然而，此算法及其改进形式在挖掘频繁模式时不可避免地需要递归地创建附加数据结构，并且每当模式增长时就要创建一次。动态地创建如此大量的附加数据结构，将耗费大量时间和空间。并且以上算法对于不同特点的数据库没有较好的适应性。 本文基于模式增长的思想，提出两种新的频繁模式挖掘算法：最小项优先的挖掘方法和最大项优先的挖掘方法。其通过采用一定的挖掘策略，使整个挖掘过程直接在初始生成的压缩的数据结构中进行，而不需要另外递归创建附加的数据结构。使频繁模式挖掘的效率得到了进一步的提高。使用相同的数据集，性能研究表明：算法速度大约是FP-Growth算法3～4倍，而所需要的存储空间不到FP-Growth算法的一半。对于稠密数据集，算法的优势更加显著。 利用深度优先的方法符合最长模式挖掘的性质，基于最小项优先的频繁模式挖掘算法，提出了新的挖掘长模式算法。采用挖掘尽可能长的频繁模式和忽略对与约束项集具有相同支持计数的项处理的策略，大大地减少了算法的搜索空间；具有分而治之性质的过滤策略较大地提高了算法的效率。在相同条件下使用相同的数据集，与最近出现的同类算法相比，效率提高几倍，特别是对于稠密数据集，效率更加明显。