关于一种高效的关联规则连续增量更新改进算法.docVIP

关于一种高效的关联规则连续增量更新改进算法 　　0 引言 　　关联规则算法发展过程中，最经典、最通用的方法是由Agrawal 等人于1993 年提出的Apriori算法和1994 年提出的改进算法AprioriTid.Apriori 算法利用“在给定的事务数据库D 中，一个长度为k 的项目集不是频繁的，则其长度为( k+ 1) 的超项目集不可能是频繁的”这一性质，通过在每次迭代产生候选项目集过程中，即时裁减存在子集未包含在上次扫描过程中生成的频繁项目集中的候选项目集，以尽可能减少每次生成的候选项目集. 为了突破类Apriori 算法的两个瓶颈问题，Han J 等于2000 年提出了关联规则算法研究历程中的另一个里程碑式频繁项目集增长算法FP - growth. 在FP - tree 思想基础上，许多学者对数据结构进行了一系列的研究，以更进一步提高算法效率. 比较有效的有GostaGrahne 等提出的通过创建附加数组以去掉创建条件子树时第一次扫描操作的FP - growth* 算法，Tseng 等提出的基于位操作事务频繁项数组以减少存储容量和挖掘效率的FPL 算法，及国内陈安龙等提出的融合FP - Tree 和图论的极大团理论优势的MAXCFPTree 算法. 　　该文针对FP - growth 算法存在的不能进行增量更新，以及已有基于FP - growth[4]的增量更新算法效率不高、不支持连续更新等问题，该文在FP - tree 基础上，设计了新的可以进行增量更新的EFP - tree 数据结构及其高效增量更新算法及增量更新改进算法FPIUA2 数据集连续增加，该算法适用于稀疏型数据集和稠密型数据集、支持连续执行、效率远高于FP - growth 和已有的增量更新算法并且具有很好的可扩展性. 　　1 预备知识 　　1. 1 FP - growth 算法原理 　　按照频繁项列表ItemList，整个频繁项目集的集合被划分为几个没有重叠的子集: ( 1) 含有项p( 列表ItemList 的尾部) 的频繁项目集; ( 2)包含m，但不包含p 的频繁项目集; 3. 包含b，但不包含m 和p 的频繁项目集; ……6. 只包含f 的频繁项目集. 　　在节点链的帮助下，从频繁项列表ItemList的末尾开始，采用递归方法来挖掘所有频繁项目 　　集的算法分为如下三个步骤: 　　( 1) 生成条件模式基( conditional patternbase) : 结点p 产生了频繁模式{ p: 3 } 和两条FP - tree路径{ f: 4，c : 3: a: 3，m: 2，p: 2} 和{ c: 1，b:1，p: 1} ，其前缀路径为{ f: 2，c: 2: a: 2，m: 2} 和{ c:1，b: 1} ，称为条件模式基. 　　( 2) 基于条件模式基构建FP - tree，称为条件FP 子树. 　　( 3) 通过递归调用FP - growth 算法挖掘FP子树，得到该条件子树包含的所有频繁项目集( 初始调用FP - growth( FP_tree，null) ) . 　　1. 2 FIUA1 算法思想 　　由于在数据集保持不变的情形下，对于最小支持度s 增加的情形，直接通过比较原频繁项目集中记录的支持度即可获得新频繁项目集，FIUA1算法主要研究了最小支持度s 减少后，基于FP - tree 的频繁项目集更新问题. 　　2 关联规则连续增量更新改进算法FPIUA2 　　首先在FP - tree 基础上，设计了最小支持度不变数据集连续增加下的更新改进算法增量更新改进算法FPIUA2 适用于数据集连续增加的情形，理论分析和实验都表明该算法同时适用于稀疏型数据集和稠密型数据集，支持连续执行，效率远高于FP - growth 和已有的增量更新算法，其效率较FP - Growth、FPUA 和FIUA2 算法提高了将近1 个数量级. 　　2. 1 算法思想 　　设D 为原有事务数据库，d 为添加到事务数据库D 中的新事务数据库，分别用X. CountD、X.Countd和X. CountD + d表示X 在D、d 和D + d中的支持数，S( XD) 、S( Xd) 和S( XD + d) 表示X 在D、d和D + d 中的支持度. 则有S( XD) = X. CountD / |D| ，S ( Xd) = X. Countd / | d | ，S ( XD + d) = X.CountD + d / |D + d | . 最小支持度s 在D、d 和D + d 　　中对应的最小支持数为[| D | ti