事务模式树分层挖掘算法及其应用

《事务模式树分层挖掘算法及其应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第39卷第5期兰州大学学报(自然科学版)Vo1．39No．52003年1O月JournalofLanzhouUniversity(NaturalSciences)oCt．2003文章编号：O455—2059(2003)05—0048—05事务模式树分层挖掘算法及其应用秦首科，徐学洲(西安电子科技大学软件工程研究所．陕西西安710071)摘要：从事务数据、时间序列数据等数据库中挖掘频繁模式已在数据挖掘领域中得到了广泛地研究．针对目前已有的Apriori算法和频繁模式增长算法在时间和空间等方面的复杂性和低效性，提出了一种新的数据结构——事务模式树，用来存放待挖掘的事务信

2、息，同时给出一种基于该数据结构的挖掘算法——事务模式树分层挖掘算法．最后，把该算法应用于保险业务．结果表明。该算法简单高效，值得推广．关键词：数据挖掘；频繁模式；事务模式树；分层中围分类号：TP311文献标识码：A该算法的许多改进使它比以前具有了更好的性能，0引言例如LPMiner：¨等．频繁模式挖掘在数据挖掘中占有重要的地位，但是随着所处理问题的规模不断变大，它仍然它已被广泛地用于挖掘关联规则、相关性、因暴露出了不足之处：首先，它和其他算法一样对于果关系、序列模式、事件、多维模式’、最大不断更新的数据库只能在每次更新后将整个数据模式、局部周期模式⋯]、新兴模式⋯等

3、数据挖掘库从头到尾挖掘一遍，而不能基于以前的挖掘结果对象．只对新加入的记录进行处理，因而在面对许多领域Apriori算法l1和频繁模式增长(frequent—的实际应用时其效率将直线下降，以至于对许多问patterngrowth)算法n是两种具有代表性的算法．题将会变得不可能处理；其次，该算法的时间复杂Apriori算法正如它的名字，该算法使用频繁项集度瓶颈在于它对FP一树的挖掘，在挖掘过程中它需性质的先验知识，它使用一种称作逐层搜索的迭代要不断地递归构造条件模式基和条件FP一树，然后方法，即志一项集用于探索(五+1)一项集．它有两种再对它们进行挖掘，最后再连接每次

4、递归所发现的开销非常巨大：(1)需要产生大量候选项集．例如，模式，基于该算法的改进都是通过尽量减少其递归如果有10个频繁1一项集，则需产生10个候选2一次数来提高性能，但递归对它们来说都是不可避免项集，并累计检查它们的频繁性．此外，为发现长度的；再次，该算法的空间复杂度瓶颈在于它需要将为1O0的频繁模式，如{a，n，⋯，a。。)，需产生多达巨大的结果集(所有频繁项集)另外保存而不能将2。≈10。。个候选；(2)需要重复地扫描数据库，通其保留在FP一树中，这样将会有数据库、FP一树、结过模式匹配检查一个很大的候选集合．对于挖掘长果集同时存在于挖掘过程中，因此既增大了存

5、储开模式尤其如此．销又加大了算法的复杂度．频繁模式增长算法自提出以来一直是挖掘频然而，我们能否通过对一棵树的挖掘把结果繁模式的最好算法，它采取如下分治策略：将提供(频繁项集)自然地剩余在该树中，待需要时可方频繁项集的数据库压缩到一棵频繁模式树(FP一便、高效地将结果取出，这样不但可以提高挖掘效树)，但仍保留项集关联信息；然后，将这种压缩后率、减少存储开销还可以在挖掘已被更新的数据库的数据库分成一组条件数据库(一种特殊类型的投时利用已有的结果，达到只处理新加入的数据就可影数据库)，每个关联一个频繁项，分别挖掘数据获得全部挖掘结果的目的．因此，我们设计了事务库．它大约比

6、Apriori算法快一个数量级．目前基于模式树分层挖掘算法．它的高效性来自于以下3项收稿日期：2002—10—08．基金项目：国家部委基金资助项目(51406050201DZ01)作者简介：秦首科(1978一)，男，硕士．IllⅢ霭I疆l第5期秦首科等：事务模式树分层挖掘算法及其应用49技术的支持：(1)将事务模式压缩到事务模式树中，这样可以高效地获取模式信息并且无须多次扫描数据库；(2)利用最小支持度是模式长度的函数这一性质，对模式进行分层挖掘，避免时间复杂度为O(2”)的操作．挖掘过程逐层进行，无须递归．频繁模式自然地剩余在树中，无须分段连接；(3)事务模式树具

7、有保存以前挖掘结果的特性，当有新的事务数据加入时，无须重新构造树，也无须重复以加入的数据进行篓处理即可需基于以前的结果对新图1事务模式树’Fig．1。：：：1事务模式树的构建1．3事务模式树构建算法构建一棵事务模式树的算法描述如下：1．1频繁模式挖掘的概念算法：构造事务模式树．设I={，，⋯，)是项的集合，即项集输入：事务数据库D。(itemset)．设任务相关的数据D是数据库事务的集输出：事务模式树．合，其中每个事务丁是一个项集，且丁包含于．包方法：创建事务模式树的根节点，以“null”标记它．对于含是个项的项集称为是一项集．集合{computer，D中的每个