含正负项目的FP-Growth算法及其在日志分析中的应用研究

摘要

关联规则挖掘是数据挖掘中重要研究的方法之一，其目的是从大型数据库中发现有用的信息。人们利用数据挖掘技术从数据中获得了很多有用的信息，这些信息推动着人类科技的发展。但是，海量的数据是人们进行数据挖掘所面临的一大难题，如果没有高效率的挖掘算法，人们在进行数据挖掘时所耗费的时间将是巨大的。而且目前所研究的大多数数据挖掘都只是挖掘事务之间的正向关系，而往往忽略了事务间负关联关系的存在。但是在现实生活中的很多领域，单单对正关联规则进行挖掘是远远不够的，还需要考虑到所挖掘数据之间的负关联关系，从而提高关联规则的描述力。 本文针对以上问题，对以下三点展开了研究： (1)研究了包含事务数据库中正项目和负项目的FP-Growth算法 考虑到在引入负项目之后，就会使原有的数据量倍增，从而导致项集的数目过大，所构造的FP-tree的分支的长度也就会过长，FP-tree的空间占有率也会过大，挖掘效率也会随之降低。为解决这一问题，本文对FP-tree的构造方法进行了改进，即利用动态插入节点的方法构造FP-tree，而且将所有的指针倒转，从而生成一个新型的FP-tree，从而减低FP-tree的生成成本。本文还提出了一种最大频繁模式的挖掘算法—Max-IFPA算法，利用构造的新型FP-tree挖掘出所有的最大频繁项集。通过和其他算法的对比实验证明，本文所提出的挖掘算法在挖据频繁项集时比其他算法具有更高的效率。 (2)研究了基于多重最小支持度的FP-Growth算法改进 过高的设置单一支持度的值，可能会使对有用的信息因出现的频率低而被遗弃，也违背了引入负项目的初衷；而过低的设置单一支持度的值，则可能会使产生大量的无用的规则。所以为解决此问题，本文在新型FP-tree的基础上，引入了最小项目支持度的概念，提出了基于多重最小支持度的最大频繁模式挖掘算法MS_IFPA，通过对不同数据项提供不同的最小支持度数值的方法，可以使在有效避免生成大量无用规则的同时，成功挖掘出对有用的规则。 (3)将改进的算法应用于取证系统的日志分析中 首先在系统的客户端采集日志文件数据并提交到系统的服务器端，系统在服务器端首先用本文的算法对所提交的数据进行预处理，然后对预处理之后的数据进行证据分析、融合，最终生成取证报告以便用户查看。

目录

声明

摘要

第一章绪论

1.2国内外的研究现状

1.2.2关联规则挖掘方法的相关研究

1.4本文的组织结构

第二章关联规则的相关理论

2.1.2关联规则度量

2.1.3关联规则的挖掘步骤

2.2关联规则的挖掘算法

2.3本章小结

第三章包含正负项目的FP-Growth算法

3.2含正负项目关联规则的描述

3.3.3算法的描述

3.3.4举例说明

3.4实验及结果分析

3.5本章小结

第四章基于多重最小支持度的FP-Growth算法改进

4.2多重最小支持度的引入

4.4算法实验与比较

4.5本章小结

第五章改进的FP-Growth算法在日志分析中的应用

5.2系统实现

5.2.2服务器端

5.3本章小结

第六章总结与展望

参考文献

攻读硕士学位期间的主要成果

致谢