不确定频繁闭项集挖掘算法研究

摘要

随着互联网的发展和科学技术的不断进步，各行各业都出现了海量的数据，这些数据是传统的技术所无法处理的。例如在经济、金融、电信等行业都出现了海量的数据。在这样的大数据背景下如何挖掘出有用的知识变得越来越有意义。它可以有效的解决当前数据丰富而知识匮乏的问题。挖掘频繁项集一直以来都是数据挖掘技术中的重点问题。挖掘得出的频繁项集可以更好的指导更有效的方案的制定。例如经典的啤酒和尿布的案例。
　　然而数据挖掘的结果往往不尽如人意，由于海量的数据以及支持度较低的时候挖掘出的频繁项集的数量和关联规则的数量往往也是巨大的，显然这不是我们想要的结果，一般的解决思路就是让结果只产生更具有代表性的子集，例如挖掘最大频繁项集或者挖掘频繁闭项集，但是最大频繁项集将会丢失重要的信息，所以我们选择使用频繁闭项集来代替海量的频繁项集。
　　近些年来，数据在传感器网络、卫星图像信息、Web应用领域、无限射频技术以及经济、物流、电信等应用中都表现出了一种不确定性。因此在不确定性数据集中如何运用数据挖掘技术变得十分迫切。然而目前经典的挖掘算法都是针对确定的数据集进行数据挖掘的。针对目前不确定性的数据集我们需要提出新的数据模型来应对数据的复杂性。
　　本文深入学习研究频繁闭项集的挖掘算法之后提出改进策略，并且对当前广泛出现的不确定性数据模型深入学习，阅读大量文献之后提出了一种不确定频繁闭项集挖掘算法。主要研究成果如下：
　　1、频繁项集挖掘的两种策略。深入研究学习了大量的频繁项集挖掘算法之后，频繁项集挖掘领域的经典算法主要有两类，一是Apriori算法以及以Apriori算法为基础的以层次迭代为策略来求取频繁项集的挖掘算法。该算法的主要的不足之处就是必须多次访问事务数据库和产生大量的候选项集，这无疑增加了大量的时空开销。二是FP-Growth算法以及基于FP-Tree结构的算法。该类算法采用深度优先遍历FP-Tree的策略，只需要访问一次事务数据库并且完全避免了利用候选项集的策略，时空效率得到了大大的提高。
　　2、频繁闭项集挖掘的两种策略。用来代替频繁项集而出现的频繁闭项集的挖掘算法主要分为两类，一是类Apriori算法，二是类FP-Growth算法，在第二类算法中挖掘频繁闭项集效率最高的算法就是DCI_Closed算法，该算法提出这样的概念：生成子是保序的，并且证明得出每个闭项集都有唯一保序的生成子序列。利用这一性质来达到剪枝的目的，提高了的算法运行的时间效率。
　　3、提出了一种改进的 DCI_Closed算法，针对当前频繁闭项集高效挖掘算法DCI_Closed在挖掘过程中存在一定的不足之处，本文在DCI_Closed算法的基础之上提出了一种改进的 DCI_Closed算法，在算法中引入共生项集和双生项集的概念，在构造FP-Tree结构的时候对候选的1-项集进行有效的剪枝操作，以此来提高算法的时空效率。
　　4、提出了一种新算法 U_DCI_Closed算法，不确定性数据集下挖掘频繁项集已经成为数据挖掘领域中热点问题，然而在不确定性数据集下挖掘最大频繁项集和频繁闭项集的算法并不多见。在深入了解不确定性数据领域中的数学模型以及认真研究频繁闭项集挖掘的经典算法之后，发现利用可能世界模型理论将不确定性事务数据转换为确定的事务数据，可以保留原先数据的不确定性，结合经典的闭项集挖掘算法DCI_Closed提出了一种新算法U_DCI_Closed算法，实验表明新算法能够在不确定数据集下高效的挖掘频繁闭项集。

目录

封面

声明

目录

中文摘要

英文摘要

第一章 绪论

1.1研究背景及意义

1.2国内外研究现状

1.3主要创新点

1.4主要内容和组织结构

第二章 频繁项集挖掘相关技术

2.1频繁项集挖掘基本知识

2.2频繁闭项集挖掘算法分析

2.3不确定数据频繁项集挖掘算法

2.4本章小结

第三章 DCI_Closed算法的一种改进

3.1 DCI_Closed算法分析

3.2 DCI_Closed算法改进

3.3 实验结果及分析

3.5 本章小结

第四章 一种不确定频繁闭项集挖掘算法

4.1 不确定频繁项集挖掘相关概念

4.2 不确定频繁闭项集挖掘算法U_DCI_Closed

4.3实验结果及分析

4.4 本章小结

第五章 总结与展望

5.1总结

5.2展望

参考文献

攻读硕士学位期间取得的科研成果

致谢