论文部分内容阅读
数据挖掘技术是解决数据丰富而知识贫乏的有效途径,当属信息科学领域的前沿研究课题之一,有关的研究和应用极大提高了决策支持的能力,它已被公认为是数据库研究中一个极富应用前景的领域。本文描述了数据挖掘的概念、功能以及发现模式的分类。在众多的数据挖掘算法中,挖掘关联规则是数据挖掘领域中的重要研究内容,其中挖掘频繁项目集是挖掘关联规则中的关键问题之一。又因为最大频繁项目集已经隐含了所有的频繁项目集,所以可以将发现频繁项目集的问题转化为发现最大频繁项目集的问题。本文主要对挖掘频繁项目集与挖掘最大频繁项目集的问题进行了研究 先前的挖掘频繁项目集算法分为基于Apriori算法和FP_growth算法两类。基于Apriori算法都需要先生成候选频繁项目集,再对其进行检验以判断其是否为频繁的;基于FP_growth算法则至少都需要扫描两遍数据库以建立FP-tree。然而扫描数据库和检验候选项目集是否为频繁项目集这些过程所需代价都是很高的。本文首先提出了一种改进的挖掘频繁项目集的算法IODLG,主要从以下几个方面改进了算法挖掘效率。第一采用位阵存储技术即为每个项目赋一个比特值,此技术使得算法只需扫描一遍数据库,就可得到挖掘频繁项目集所需的全部信息,并可以加快检测候选项目集的速度;第二定义项目值以取代项目名,项目值可以更好的与项目的比特向量建立关联;第三为关联图中的每个节点定义出度与入度值,可以有效减少候选项目集的个数。经试验证明,通过以上三个方面的改进,IODLG算法可以大大提高算法挖掘频繁项目集的效率并减少系统的存储空间。 对于最大频繁项目集挖掘方面,本文在充分研究已有算法的基础之上,提出了一种新的基于FP-tree的挖掘最大频繁项目集算法MFI-FP。算法主要包括一下三个部分:首先定义新FP-tree结构,说明其构造过程并分析其性质。采用新FP-tree可以使算法只需扫描一遍FP—tree即可得到挖掘最大频繁项目集所需的信息,同时扫描过FP-tree后,可以立即释放FP-tree中大量的无用节点以节省空间;其次,提出了一种新的存储最大频繁项目集的数据结构,这种结构可以减少存储最大频繁项目集所需的空间,提高挖掘的效率,尤其适用于长模式的频繁项