论文部分内容阅读
数据挖掘是从海量的数据中挖掘有潜在价值的信息的技术。分类是数据挖掘中一项非常重要的任务,在政府组织、科学研究、商业等诸多领域具有广泛的应用。统计学、机器学习、神经网络等领域的研究者提出了很多分类算法,这些算法大都适用于小型数据集,基于显露模式(Emerging Patterns,EPs)的分类方法是针对大型数据集的分类提出的。 显露模式是那些从一个数据集到另一个数据集支持度发生显著变化的项集,它对分类是有用的,这是因为它能捕获数据集中不同类之间的差异。第一个基于EPs的分类算法是G.Dong等提出的CAEP算法,此后相继提出了JEP-Classifier、DeEPs等一系列基于EPs的分类算法。在分类时我们发现用于分类的EPs的数量通常很大,不能选用所有的EPs用于分类。Fan和Ramamohanarao提议使用一种特殊的EPs,称作基本显露模式(essential Emerging Pattems,简称eEPs),进行分类,并建立了基于eEP的Bayes分类法,取得了很好的分类效果。 因此,如何高效地挖掘出eEPs是一个很重要的问题。eEPs是那些“最短的”EPs,使用EPs的边界表示,eEPs恰是EPs边界表示的一组下界,因此可以使用G.Dong和Li提出的边界算法来挖掘所有的eEPs。然而,这种方法的效率极低。为挖掘C类上的eEPs,必须首先挖掘C类和非C类上的长模式,然后使用边界算法得到C类上的eEPs。挖掘长模式是一项很耗时的工作,并且采用边界算法产生的eEPs并不包含支持度和增长率信息。为了得到eEPs的支持度和增长率,还需要再次扫描数据集,统计每个eEP的出现频率并计算增长率。 本文的主要工作是提出了一种基于模式树(P-树)的eEPs挖掘新算法eEPMiner。eEPMiner采用模式增长的策略,只需两次扫描事务数据库,就能挖掘出C类上所有的eEPs,并同时得到它们的增长率和支持度。并且在挖掘过程中,模式树不仅存储数据集中所有项的信息,而且支持类的信息。我们不需要附加的空间就可以直接在模式树上挖掘出所有的eEPs。在UCI机器学习数据库的多个数据集上的实验表明,eEPMiner具有很好的性能,其速度比基于边界的算法快得多。