基于约简频繁模式树的频繁模式挖掘及查询算法研究

摘要

频繁模式挖掘是数据挖掘中的一项重要工作，也是关联规则挖掘的一个关键步骤，可以应用于诸如分类、聚类、预测等数据挖掘任务中。目前，关联规则挖掘结果多以在线交互方式导出，如何从大量的频繁模式中查询指定频繁模式进而产生关联规则成为影响在线查询系统整体性能的重要因素。因此，本文研究频繁模式的高效挖掘算法及频繁模式的查询算法。完全频繁模式挖掘产生较大规模的结果集，而且目前大多数频繁模式挖掘算法都是以项集的形式输出挖掘结果，使得由多个频繁项集共享的前缀项集重复存储，不但占用存储空间，而且基于项集形式的模式匹配(项集查询)较为耗时。本文在对数据挖掘和关联规则的基本概念以及相关知识进行研究的基础上，提出一种完全频繁模式的约简表达形式--约简频繁模式树(SFP-tree)。无论在所包含的频繁模式还是存储规模上，SFP-tree的比相应的完全频繁模式小得多，而且易于逻辑的还原成完全频繁模式，基于SFP-tree能高效的实现模式匹配。本文给出了产生SFP-tree的挖掘算法，利用树形控件实现SFP-tree的可视化，并提出基于该SFP-tree的频繁模式查询算法。
　　 本研究主要内容包括：⑴提出以约简频繁模式树(Simplified Frequent Patterns Tree)为挖掘结果表达形式的频繁模式挖掘算法----MSFT算法(Mining based on Simplified Frequent PatternTree)。MSFT算法采用改进的深度优先搜索策略产生频繁项集，并采用位向量的方式来计算和存储频繁项集支持集，具有较小的内存开销。本文还给出了SFP-tree的树节点的组织方式和逻辑结构，对比实验证明MSFT算法的优越性。⑵提出基于SFP-tree的频繁模式查询算法。首先提出将SFP-tree逻辑的还原成完全频繁模式的方法，重点对其中的一类被称为单子女路径结点进行处理，即将其子女结点同时当成它的兄弟结点使用。然后提出基于SFP-tree的频繁模式查询算法，该算法由SFP-tree的根结点开始以宽度优先顺序扫描其子结点，发现包含给定频繁项集中的某个项的结点后，沿着以该项为根结点的子树深度优先向下查找，查找过程中利用单子女路径结点实现了约简频繁模式树到完全频繁模式树的部分逻辑还原。实验证明基于SFP-tree的频繁模式查询算法比基于完全频繁模式的模式匹配算法效率更高。

目录

文摘

英文文摘

第一章 绪论

1.1 研究背景及意义

1.2 国内外研究现状

1.3 本文研究内容及创新之处

1.4 本文的组织结构

第二章 关联挖掘中基本概念和经典算法

2.1 数据挖掘概述

2.2 关联规则挖掘的基本概念

2.3 经典算法

2.3.1 Apriori算法

2.3.2 FP-growth算法

2.4 本章小结

第三章 基于SFP-tree的频繁模式挖掘算法

3.1 问题的提出

3.2 频繁模式挖掘结果的不同形式

3.3 MSFT算法的相关概念

3.3.1 数据的垂直格式及位向量表示

3.3.2 改进的深度优先搜索策略

3.3.3 挖掘结果的树形输出格式

3.4 算法描述

3.4.1 算法描述部分

3.4.2 步骤说明

3.4.3 算法示例

3.5 算法实验结果

3.5.1 运行时间

3.5.2 内存消耗

3.5.3 挖掘结果大小

3.6 本章小结

第四章 基于约简频繁模式树的频繁模式查询算法

4.1 基于SFP-tree的频繁模式查询算法

4.1.1 SFP-tree逻辑还原为完全频繁模式树

4.1.2 基于SFP-tree的频繁模式查询算法

4.1.3 关联规则的生成

4.2 实验结果

4.3 本章小结

第五章 总结与展望

5.1 工作总结

5.2 展望

参考文献

发表论文和科研情况说明

致谢