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 | s]，[| d | s]和[|D + d | s].
定理1 设LD为D 中所有频繁项目集集合，Ld为d 中所有频繁项目集集合，LD + d为D + d
的所有频繁项目集集合，则LD + dLDLd，LDLdLD + d .
定理1 表明，若项目集X 在D 和d 中都为非频繁项目集，则其在D + d 中也必定为非频繁项目集，若X 在Dd 中为频繁项目集，则X 必包含在LD或Ld中.
性质1 在给定的事务数据库D 中，若一个长度为k 的项目集不是频繁的，则其长度为( k+ 1) 的超项目集不可能是频繁的.
性质2 设 = { I1，I2，，Ip} 为频繁项构成的项目集，且I12，，Ip按照频繁项逆序排
列，则其支持数可以通过遍历EFP - tree 中项目内容为Ip的链表，累加包含 中所有项目路径的支持数获得.
根据性质2，设计通过扫描EFP - tree，统计 对应支持数的modifyFPCountByTree 算法.输入: 事务数据库D 对应的EFP - treeD和按照频繁项逆序排列的项目集.
输出: 项目集 在事务数据库中的支持数.
int modifyFPCountByTree( EFP_treeD，)
{
iCount = 0;
搜索项目列表ItemList 获得项目内容为Ip的第一个树结点指针，保存到pCurrNode;
while ( pCurrNode)
{
逆序遍历该节点路径，若路径包含 中的所有项目，则iCount + = pCurrNode -
pCurrNode = pCurrNode - node_link;
}
return iCount
}
根据定理1，在数据集增加情形下，已知D中所有频繁项目集，我们只要再挖掘出d 中包含的所有频繁项目集，就可以得到D + d 中所有频繁项目集LD + d的超集，我们称其为D + d 中的候选频繁项目集，记为CD + d .设LD1为D 中所有频繁项，Ld1为d 中所有频繁项，L1 为D + d 中所有频繁项. 通过统计D 和d 对应EFP - tree 中的项目列表，可以确定L1 ，记L -D1 = LD1 - L1 ，L -d1 = Ld1 - L1，L +D1 = Ld1 - LD1，L +d1 = LD1 - Ld1 .
可以将CD + d划分为以下五部分:
( 1) LDd = { c | cLDLd} .
( 2) CD0 = { c | cLD - LDd且cL +D1 = } .
( 3) CD1 = { c | cLD - LDd且cL +D1} .
( 4) Cd0 = { c | cLd - LDd且cL +d1 = } .50 ( 5) Cd1 = { c | cLd - LDd
且cL +d1} .
显然CD0CD1 = ，Cd0Cd1 = .
根据定理1，LDd部分必定为Dd 中频繁项目集，只需要累加其支持数; 根据性质7，可以直接删除CD0和CD1中包含L -D1中项目的所有候选项目集，及Cd0和Cd1中包含L -d1的所有候选项目集; 对于CD0和Cd0，根据性质8，分别通过统计d 和D 对应EFP - tree中路径数可以确定项目集支持数; 对于CD1和Cd1，则需要扫描新增事务数据集d 和原数据集D 确定项目集支持数.
由此，可以得到最小支持度不变数据集连续增加情形下增量更新改进算法FPIUA2.
2. 2 增量更新改进算法FPIUA2
算法2: 最小支持度不变数据集连续增加情形下增量更新改进算法FPIUA2.
输入: 事务数据库D 及其对应EFP - treeD、所有频繁项目集LD; 新增事务数据库d; 最小支持度s.输出: 事务数据库D + d 中所有频繁项目集LD + d及更新后的EFP - tree
FPIUA2 ( )
{
通过FP - growth 算法获得新增事务数据库d 中的所有频繁项目集Ld及其对应的EFP -treed;
统计EFP - treeD和EFP - treed中的Item-List，获得新频繁项L1 ，并求得
L -D1 = LD1 - L1 ，L -d1 = Ld1 - L1 ，L +D1 = L1 - LD1
，L +d1 = L1 求LDd = LDLd，其中各频繁项的支持数为两者支持数之和，并更新LD = LD - LDd和Ld = Ld- LD
删除LD中包含有L -D1中项目的频繁项目集，删除Ld包含有L -d1中项目的频繁项目集;
对于项目集cCD0，记 为c 按照EFP -treed中频繁项目逆序排列后项目集，
c. count = c. cout + modifyFPCountByTree( EFP - treed，) ，
若c. count / | D + d |s 则将该项目集保存到LDd，
更新LD = LD - CD0;对于项目集cCd0，记 为c 按照EFP -treed中频繁项目逆序排列后项目集，c. count = c. cout + modifyFPCountByTree( EFP - treeD，) ，
若c. count / |D + d |s 则将该项目集保存到LDd，更新Ld = Ld - Cd0;扫描原事务数据库D，统计Ld中各项目集支持数; 扫描原事务数据库d，统计LD中各项目集支持数; / / 统计CD1和Cd1中候选频繁项目集支持数
删除LD和Ld中所有支持数少于指定| d + D| s 的所有项目集; LD + d = LDLD/ /更新EFP - tree
for each cLD1 - dele
teItemTreeNode ( c) ;L +D1按照新频繁次序排序;
AddNewItems ( LD1 + ) ;
按照L1次序调整EFP - tree 中频繁项在ItemList 和对应树节点位置;
for each transactions_t d { / /插入新数据集中事务
t = L transactions _ t ; insert _ tree
( [p | t]，EFP - tree) ; }
}
2. 3 算法分析
采用以下方法，FPIUA2 算法效率远远高于FP - growth 和已有增量更新算法:
( 1) FPIUA2 算法仅在新增数据集d 上通过FP - growth 算法获得频繁项目集，通常情况下| d || D | + | d | ，因此，其时间也远远小于直接在D + d 执行FP - growth 算法.
( 2) 若事务数据集中各事务都为随机事务，则D 和d 中得到的频繁项目集绝大部分相同，且频繁项LD1和Ld1也基本相同，几乎对所有新产生或失效频繁项目集，FPIUA2 算法只需统计内存中EFP - treeD或EFP - treed中相应路径支持数，即可获得支持度，不需要再次扫描数据集.
( 3) 通过以上处理，并删除CD + d中包含失效频繁项的候选频繁项目集，需要通过扫描数据集统计支持数的候选频繁项目集一般情况下小于2%.
( 4) 最坏情况下，FPIUA2 算法只需要扫描D 一次，扫描d 四次( 包括建立EFP - treed和更新EFP - treeD + d) .
对于稠密型数据集，在很高的支持度下，也会产生数量远远大于事务数的频繁项目集. 如在文献[2]中采用的connect - 4 数据集，在80% 的支持度下，在67557 个事务上，也会产生50 多万个频繁项目集，在这种情形下，由于FPIUA2 算法要进行大量的支持数统计运算，其效率远远低于直接执行FP - growth 算法. 我们的实验表明，对于稠密型数据集，FP - growth 算法的绝大部分执行时间耗费在构造EFP - tree 过程中，因此，在稠密型数据集下，应该采用先增量更新EFP -tree，然后在更新后的EFP - tree 中直接执行FP - growth算法的方式获得新频繁项目集，提高挖掘关联规的效率. 我们通过监控频繁项支持度及频繁项目集数量来确认是否为稠密型数据集( 目前暂定频繁项支持度大于等于30%，且频繁项目集数量大于事务数2 倍) .
3 结束语
在综合分析关联规则算法研究现状基础上，设计了EFP - tree 的高效更新算法，支持度连续变化情形下数据集连续增加情形下的增量更新改进算法FPIUA2，适用于稀疏型数据集和稠密型数据集，支持连续执行，且效率远高于FP -growth 和已有的增量更新算法.
