论文部分内容阅读
数据挖掘技术是近年来数据库和人工智能等领域研究的热点课题,它引起了科学界和产业界的广泛关注。关联规则挖掘作为数据挖掘领域的一个重要研究分支,它的任务是发现所有满足支持度闭值和置信度阂值的强关联规则。目前,关联规则的挖掘技术也被成功的运用到分类中,其思想是把属性和类别联系在一起。本文主要针对如何更有效的挖掘类关联规则这一问题展开研究。
频繁模式和对应的关联或相关规则刻画了属性条件与类标号之间的有趣联系,因此,近来用于有效的分类。本文考察关联分类(associative classification),其中关联规则的产生和分析旨在于分类。其基本思想是,将搜索频繁模式(属性-值对的合取)与类标号之间的强关联。由于关联规则考察了多属性之间的高置信度关联,这种方法可能克服决策树归纳一次只考虑一个属性的局限性。许多研究发现,关联分类比诸如ID3等传统的分类方法更准确。关联分类方法的主要不同在于频繁项集挖掘所用的方法和导出的规则如何分析和用于分类。本文着重研究前两点,即频繁项集挖掘和规则的导出。
本文的主要工作如下:
对关联规则挖掘的基本理论进行了总体研究,并给出Aprior算法、FP-Growth算法和Eclat算法的介绍、算法示例以及效率分析。
尽管在关联规则的挖掘中,Apriori算法作为一种经典算法已经取得了不错的效果,但是它仍然在某些方面的表现不尽如人意。Apriori算法在进行操作时,必须对数据库进行反复的扫描,以得到的频繁项集的支持度。相比于已经存在的一些关联规则挖掘算法来说,FP-Growth有了长足的进步,但构造FP-树的过程仍然是复杂的。与Apriori算法和FP-growth算法相比,Eclat算法的优势也十分明显。Eclat算法仅需扫描一次数据库,并且在信息存储的过程中,它采用了垂直数据库,正因如此,计算支持度也相当简单。
对分类规则挖掘进行深入研究,针对决策树分类和关联分类算法,分别对ID3和CMAR算法进行介绍,并结合算法流程进行说明,对其性能进行分析。
ID3算法之所以称为一种经典的决策树分类算法,作为数据挖掘和机器学习领域中的一个范例,是因为其结构简单,便于读者理解,并且理论也是十分清晰明了的。但是它在分类过程中,只能考虑单一属性,无法取得很好的分类效果。
CMAR(Classification Based on Multiple Class-Association Rules,基于多关联规则的分类)在频繁项集挖掘和分类器构造方面都不同于CBA。CMAR采用FP增长算法的变形来发现满足最小支持度和最小置信度闽值规则的完全集。FP增长使用称作FP树的树结构记录包含在给定数据集D中所有频繁项集信息,仅需要扫描两次数据库。CMAR采用类FPgrowth算法来挖掘类关联规则,虽然只需要扫描两次数据集,但在挖掘过程中需递归地建立条件FP-tree,这使得算法在执行时内存,消耗太大。
目前对于关联分类方法的改进主要考虑这几方面问题:1)减少扫描数据库次数2)产生尽可能少的候选集3)减少构建FP一树的消耗以及尽可能地节省内存。
在已有的对关联规则以及分类规则研究的基础上,我们提出了一种新的挖掘类关联规则的算法--MCAR(Mining Class Association Rules),它主要有以下几个特征。
首先,MCAR算法紧需要扫描一次数据库,并在此过程中得到全部的规则,而不是像以往的算法那样需要对数据库进行多次扫描。第二,对于不能产生有效规则的无效项集,我们使用了类频繁项集修剪策略对其进行修剪,使无效的规则在产生之前就被删除。第三,为了改进某些复杂的结构如FP-树,我们使用了使用了垂直数据库的形式,并使用了交操作来计算支持度。
我们用一个算法示例来说明MCAR算法的有效性,并证明了该算法避免了大量冗余的计算,因此极大了提高了类关联规则挖掘的效率。试验结果证明,MCAR算法所产生的类关联规则集合和其他类关联规则算法所得到的集合相比数量明显减小,并且算法结构简单易于理解。