论文部分内容阅读
频繁项集的挖掘技术在如今的数据“爆炸”时代,有着越来越重要的地位,它是解决实际问题的一种非常重要的手段。很多学者在最近20年中提出了许多有关挖掘频繁项集的相关算法以用来解决生产中的实际问题。但随着我们的数据量级呈几何倍增增长,我们对频繁项集挖掘算法的执行效率越来越重视。本文首先把有关频繁项集的国内外的研究成果进行了汇总,并对这些研究成果进行了深入的分析。并且着重分析了基于水平数据格式的Apriori算法和FP-growth算法,以及基于垂直数据格式的Eclat算法相关理论、实现流程以及在时间性能和空间性能的具体情况。之后比较了每一个算法的优、缺点,这么做的目的是为了提出性能更高效的算法做好充分的理论储备。本文是在结合这些研究成果的一些优点的基础上,提出了一种基于垂直格式的数据存储形式基础上全新的频繁挖掘算法——FDSL算法(Frequent Deep Search List)。该算法通过把水平数据结构变成一种有序的垂直数据存储结构,并根据这个结构构建了相应地搜索bitmap,通过扫描这个bitmap,构造出一个有序搜索列表,然后利用深度优先查找策略,对这个有序的搜索列表进行深度搜索,这样就可以同时生成候选集以及候选集的支持度。这样在O(n)时间复杂度下利用上述搜索策略就可以生成相应的频繁项集。为了证明本文提出的FDSL算法的性能,本文使用C++编程语言分别实现了Apriori算法、Ecalt算法以及FDSL算法,并选用等长和不等长两种不同的数据格式的数据集对上述三种频繁项集挖掘算法进行了充分的比较并获得了大量实验数据。实验结果表明,本文提出的算法在与传统的基于水平格式的Apriori算法以及垂直格式的Eclat算法在不同的支持度阈值上进行了充分的比较后发现,本文提出的算法(FDSL)在时间性能上相对于其他算法优势还是比较明显。