高性能数据挖掘 快速项集挖掘算法及性能研究PDF电子书下载

第1章 概述 1

1.1 项集：数据挖掘研究领域的焦点之一 3

1.2 频繁项集挖掘问题的研究历史 5

1.3 高可用项集挖掘问题的研究历史 7

1.4 本书的主要内容 9

第2章 频繁项集挖掘问题 11

2.1 概述 12

2.1.1 问题形式化定义 12

2.1.2 搜索空间与方法 13

2.2 基础频繁项集挖掘算法介绍 14

2.2.1 经典的候选生成Apriori算法 15

2.2.2 以垂直视角处理数据库的Eclat算法 16

2.2.3 基于前缀树结构的FP-growth算法 17

2.3 性能测试的软硬件环境 19

2.3.1 数据库描述 19

2.3.2 参照算法介绍 20

2.3.3 其他软硬件设施 22

2.4 实验一：三种基础算法的性能测试 23

2.4.1 实验结果 23

2.4.2 性能评价 24

第3章 BFP-growth：快速模式增长算法 27

3.1 经典模式增长算法的性能分析 28

3.1.1 影响 FP-growth性能的三个因素 28

3.1.2 ICDM最佳算法：FPgrowth 28

3.2 批量模式增长算法：BFP-growth 30

3.2.1 性能提升的途径 30

3.2.2 核心步骤：两次前缀树遍历 31

3.2.3 算法伪代码 34

3.3 BFP-growth算法的性能分析 35

3.3.1 更少的遍历花费 35

3.3.2 FP-array技术应该集成在BFP-growth中吗 36

3.3.3 无修饰的前缀树结构 37

3.4 实验二：BFP-growth的性能测试及讨论 38

3.4.1 BFP-growth 及FPgrowth*与基础算法的对比 38

3.4.2 实验结果讨论 38

3.5 小结 40

第4章 基于结点集合结构的NS算法 41

4.1 Eclat及FP-growth算法的优缺点 42

4.2 结点集合结构（Node-set） 43

4.2.1 条件结点 44

4.2.2 结点拓扑序号 45

4.2.3 使用结点集合结构表示前缀树 46

4.3 NS算法 47

4.3.1 映射前缀树到结点集合结构 47

4.3.2 从结点集合结构中挖掘频繁项集 48

4.3.3 一个例子 50

4.3.4 NS算法的原子操作 51

4.4 实验三：NS算法与其他快速挖掘算法的性能对比 51

4.4.1 实验结果 52

4.4.2 结果讨论：NS算法的性能优势 53

4.5 小结 54

第5章 用Patricia结构挖掘频繁项集 55

5.1 研究动机 56

5.2 Patricia*结构 57

5.2.1 单孩子结点 58

5.2.2 构造Patricia*结构 59

5.3 用Patricia*结构挖掘频繁项集 60

5.3.1 先前的挖掘流程 60

5.3.2 改进的挖掘流程 61

5.3.3 PatriciaMine*算法 62

5.4 实验结果 63

5.4.1 结点数量统计 64

5.4.2 性能对比 65

5.5 小结 66

第6章 频繁项集挖掘算法的内存耗费 68

6.1 BFP-growth算法内存使用情况分析 69

6.2 NS算法内存使用情况分析 69

6.3 实验四：快速挖掘算法的内存耗费 70

6.4 SP算法 71

6.4.1 研究动机 71

6.4.2 基础知识 72

6.4.3 挖掘频繁项集 76

6.4.4 实验结果与结论 79

第7章 高可用项集挖掘问题 80

7.1 从频繁项集到高可用项集 81

7.2 问题的形式化定义 82

7.3 已有挖掘算法概述 83

第8章 非候选生成高可用项集挖掘算法 87

8.1 项集有用性列表结构 88

8.1.1 初始有用性列表 88

8.1.2 2-项集的有用性列表 90

8.1.3 k-项集有用性列表（k≥3） 91

8.2 HUI-Miner算法 92

8.2.1 剪枝策略 93

8.2.2 算法伪代码 94

8.3 HUI-Miner算法的实现细节 95

8.3.1 有用性列表表头 95

8.3.2 重新标注tid 95

8.3.3 交易权重有用性增加的顺序 96

8.4 实验五：HUI-Miner性能测试 97

8.4.1 实验设置 97

8.4.2 HUI-Miner及对比算法的运行时间 98

8.4.3 HUI-Miner 及对比算法的内存耗费 99

8.4.4 项处理顺序对HUI-Miner性能的影响 100

8.4.5 可扩展性 101

8.4.6 实验结果讨论 102

8.5 小结 103

第9章 快速识别高可用项集 105

9.1 先前算法的性能瓶颈 106

9.2 基本识别算法（BIA） 107

9.3 基于候选树的快速识别算法（FIA） 110

9.3.1 候选树结构 110

9.3.2 快速识别算法 111

9.4 算法分析：BIA与FIA 114

9.5 实验六：BIA与FIA的性能对比 115

9.5.1 高可用项集识别时间 116

9.5.2 候选项集生成时间 117

9.5.3 内存耗费 117

9.5.4 实验结果分析 117

9.6 实验七：FIA-UP-Growth＋和 HUI-Miner的性能对比 118

9.6.1 运行时间＆内存耗费 118

9.6.2 实验结果分析 119

9.7 小结 120

第10章 最大频繁项集挖掘 122

10.1 介绍 122

10.2 基本概念 124

10.3 MAFIA算法 125

10.3.1 深度优先遍历 125

10.3.2 搜索空间剪枝 126

10.3.3 有效的MFI超集检查 130

10.4 挖掘非最大频繁项集 131

10.4.1 挖掘所有的频繁项集 132

10.4.2 挖掘所有的频繁闭项集 132

10.5 实施细节 133

10.6 结论 134

第11章 频繁闭项集挖掘 135

11.1 介绍 135

11.2 频繁项集挖掘 137

11.2.1 基本定义 137

11.2.2 先前的解决方案 138

11.3 项集—记录标识符集合搜索树与等价类 139

11.4 CHARM算法设计与实现 141

11.4.1 快速的闭项集子集合检查 144

11.4.2 使用差异集合快速进行频繁计数 145

11.4.3 其他优化及正确性 147

11.5 实验结果 148

11.6 结论 149

参考文献 150