增量数据挖掘初探.doc

《增量数据挖掘初探.doc》由会员分享，可在线阅读，更多相关《增量数据挖掘初探.doc（18页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、【精品文档】如有侵权，请联系网站删除，仅供学习与交流增量数据挖掘初探.精品文档.增量数据挖掘初探赵浩磊 (陕西理工学院数学系信息与计算科学专业2003级3班，陕西汉中723001)指导教师 周涛摘 要本文介绍了数据挖掘领域中的增量频繁模式挖掘，在介绍了频繁项集挖掘与增量频繁模式挖掘的一搬概念后，文章又相继介绍了了三种由相关研究人员提出的增量频繁模式挖掘算法，并分析了这些算法的优点与不足，并且在分析的同时发现了IUAMAR算法的严重缺陷，指出它是不可靠的算法最后，文章根据火锅销售数据挖掘的现实情况，结合其中的两种算法的优点，介绍了销售数据挖掘的实现。关键词 数据挖掘；关联规则；频繁项集；增量挖掘

2、算法 引言1.1 问题的提出近年来，信息技术的广泛应用提出了对信息处理能力的更高要求，老式的数据统计方法面对海量的数据以及全新的数据处理概念显得力不从心，在这种背景下,数据挖掘技术应运而生，并成为研究的热点数据挖掘就是从大量的、不完全的、有噪声的、模糊的、原始的数据中提取隐含在其中人们事先不知道也不可能直接获取的，但却非常有潜在价值的信息，它们包括关联规则挖掘、特征规则、分类规则等其中关联规则挖掘是发现大量数据中项与项之间有趣的关联或联系，它是数据挖掘领域中的一个热闹课题，得到了业界广泛的研究其中:Apriori算法是最早提出的也是最经典的算法，后来又出现了另一个高效的算法FP-Growth,

3、它解决了Apriori算法中的一个最大缺陷但它本身的实现却比较困难之后，广大学者就以上述算法为蓝本进行改进，使之更加有效，更加容易实现，并将其融入到各种数据处理系统中，使之发挥出自己巨大的作用但是以上的研究都是以假设数据库为静态的前提的事实上，在很多领域数据库都处在不断地更新（增加、删除、修改）中，所用的支持度阈值也会不断改变，并且动态数据库往往要求对用户的查寻指令做出快速地反应因此，提高动态数据库中关联规则发现的效率便成了一个重要的问题进行增量数据挖掘最直接的方法就是对更新后的数据库进行一次关联规则挖掘，但这样显然有很大的开销，而且随着时间的增长、数据库规模的不断增长，这样的方法也显得不现实

4、如何利用原始数据库的挖掘结果来更新频繁项集便成了增量频繁模式挖掘研究的起点虽然目前频繁模式的增量挖掘领域研究地还不很充分，但是广大研究人员对它们所做出的改进还是值得肯定的，针对阈值不变的增量频繁模式挖掘研究总体分为两大类：第一种的分别挖掘出原始数据库和更新数据库中的频繁项集，然后使用某种规则对其进行更新，这种算法的特点是可以最大利用现有的关联规则挖掘算法，但是频繁项集的更新规则很重要，规则制定或实现的时候一但发生问题，将对结果的分析产生致命影响第二种的基于散列的方法，这种方法不需要添加复杂的更新规则，实现起来也非常容易，结果可靠性高，但是它将占用较高的系统资源 本文将带介绍、分析几种不同类型的

5、算法 ，然后以一销售数据库为例介绍算法的实际应用 1.2 数据挖掘的基本概念与定义项（item）是一个文字，在交易数据库中，它可以代表商品；分类时，它可以代表属性的值设为项的全集，为事务数据库，其中每个事务包含中的一个子集支持度计数：项集的支持度是指，事务数据库中，包含的事务的个数支持度：项集的支持度计数等于的支持度计数除以事务数据库中事务的总条数给定一个支持度阈值minsup，若的支持度minsup，则是频繁的，若包含有k个项，则称X为频繁k-项集1Apriori性质1：若一个项集是频繁的，则它的所有子集也是频繁的；同样，如果一个项集有不频繁的子集，则这个项集就不可能是频繁的 融合原始、增量

6、数据库频繁模式的算法前面已经介绍过，基于融合思想的算法需要用基本的数据挖掘算法分别挖掘出原始、增量数据库中的频繁项集，然后对它们进行融合融合的时候需要以下三大结论的支持：设K是项集，DB为原始数据库，db为增量数据库，NDB为更新后的数据库1 K在DB中是频繁的，在db中也是频繁的，则K在NDB中是频繁的2 K在DB中是不频繁的，在db中也是不频繁的，则K在NDB中是不频繁的3 K只在DB或db其中之一中频繁，则K在NDB中是否频繁是不确定的2其中DB是原始数据库，db是增量数据库，K是频繁项集，NDB是更新后的数据库以上结论很容易根据频繁项集的定义得到证明有了上面的理论，很多学者对此思想产生

7、的算法进行了一些研究、改进，比如：只需要挖掘出原始数据库中的频繁项集，而用其它方法处理增量数据库如：何宏，肖建华，肖伟平提出了IUAMAR算法3，该算法可以处理对挖掘数据库进行追加的情况，利用挖掘知识库信息即原数据库挖掘出来的高频项目集和最小非高频繁项目集来产生新候选项目集，避免了类似Apriori的算法中候选项目集的数量庞大的问题下面文章将介绍这个算法，并对它的优缺点进行分析2.1 算法的相关概念与定义DB :原始数据库;db:增量数据库;UD：更新后的数据库:原始数据库中挖掘出来的高频项目集;MNL：最小非高频繁项目集；|DB| :原始数据库的长度（事务数）;|db| :增量数据库的长度（

8、事务数）;|UD| :更新后的数据库的长度（事务数）;Dx :X 项目集出现在DB库的次数;dx :X 项目集出现在db库的次数;CUD:新产生的候选项目集.Cx：候选项集在UD中出现的次数minsup：用户定义的支持度阈值定义数据结构：struct knowledge int field ;/ 挖 掘 数 据 库的字段代码struct knowledge*next其中field为项目集的出现次数用此结构建立三张链表：LDB,LMNI,LUD定义 1 这里所谓的最小非高频繁项目集，为没有子集或是其子集皆为高频项目集的非高频项目集定理 1 设，则时，项目集在更新后的数据库中仍为高频项目集.证明：

9、因为Dx,dx分别为X在D和d中的支持度计数，则为X在UD中的支持度，若它minsup则满足一个项集在数据库中频繁的定义，定理1证毕定理设，则时，X项目集在更后的新数据库中变为高中频繁项目集证明同上2.2 IUAMAR算法的流程步骤 1用Apriori算法挖掘原始数据库DB，产生高频项目集合及最小非高频项目集MNL，将结果分别保存到LDB,LMNI两个链表中，LUB暂时为空步骤 2 遍历db，更新各链表中与MNL元素的出现次数步骤 3 使用定理和定理检查各链表中的元素，如果不满足定理，则删除该项目集 ，并 且 更 新 三张 链 表 ,将不满足的清除出LB和LMNI，并将所有满足项集的并入LUB

10、步骤 4使用LMNI和LUB产生新的候选项集 步 骤 5 利用上述产生的候选项目集扫描更新后的UD一次，找出所有候选项目集在UD中出现的次数 ， 如果候选项目集X出现的次数，则这些项目集和更新后的LB、LMNI中的项目集合并一起成为更新数据库中的高频项目集算法的伪代码描述:BEGAINApriori(DB,LDB,LMNI,LUB)/算法的第一步IUAMAR(DB,db，minsup)For each Transaction T in db/扫描db中的每项Updating(db,LDB,UMll);/用db中的记录更新两链表各项目集出现的次数For eachitem set X in LDB

11、if(Dx+dx)/不满足定理LDB=LDB-XLUB=For eachitem set Y in LMNIif(Dx+dx)/不满足定理LMNI=LMNI-XLUB=CUD=gen(LUD,LMNI)/LUD和LMNI通过gen()产生候选项目集CUDFor each itemset X in CUDif(Cx)/不满足条件CUD=CUD-XLUB=LUBCUDEND2.3 实例说明表2.3.1 事务数据库编号事务编号事务11,2,361,3,4,521,4,573,4,531,3,582,344,5,691,3,4,552,3,6102,6表格 2.3.1设DB为表2.3.1中第条事务，d

12、b为表2.3.1中第条事务，minsup=0.4现利用上述算法对其进行增量挖掘首先用Apriori算法挖掘DB得：DB=1(4),3(4),4(3),5(4),13(3),15(3),45(3),LMNI =2(2),6(2),14(2),34(1),35(2)其中小括号中的数字是该集合在相应数据库中出现的总次数用db更新链表后变为:LDB=1(6),3(7),4(5),5(5),13(4),15(4),45(4)，LMNI=2(4),6(3),14(3),34(3),35(4)经过第三步的处理，各链表变为:LDB=1,3,4,5,13,15,45;LMNI=2,35;LUB=1,2,3,4,

13、5,13,15,35,45调用gen()函数产生候选项集:CUD=1,2,3,4,5,13,15,45,12,23,24,25,123,125,245,35,135,345，检查其在UB中的支持度计数：CUD=1(6),2(4),3(7),4(5),5(5),13(4),15(4),45(5),12(1),23(3),24(0),25(0),123(1),125(0),245(0),35(4),135(3),345(3)最后得到LUB=1,2,3,4,5,13,15,45,35,算法结束2.4 算法分析优点：显然，该算法通过引入“最小非高频繁项集”的概念巧妙得处理了经典Apriori算法产生候

14、选项集过多的问题，再加上链表的应用速度明显提高，内存占用也不大，用代码实现起来也很容易缺点：首先先考虑算法的可靠性问题，这是人们对一个算法所最关心的文中所述的算法可以说是以原始数据库中的频繁项集和最小非高频繁项集为基础的但是算法对三大定义中的最后一条考虑不周试想，若增量数据库比原始数据库还大，并且在增量数据库中出现了新的，在原始数据库中不曾出现过的新项集，上述算法如何处理？不论是LDB还是LMNI都没有该项集的出现，显然根据上述算法新的频繁项集丢失了，同样的问题也出现在对“非最小非高频繁项集的处理上”下来我们来做个实验：设原始数据库仍为表2.3.1中的前条，新的增量数据库ndb如下：表2.3.

15、2 增量数据库ndb编号事务72,5,6,785,6,795,6,7,8106,7,8115,6,7,9125,6,9首先用Apriori算法挖掘DB得：LDB=1(4),3(4),4(3),5(3),13(3),15(3),45(3),LMNI =2(2),6(2),14(2),34(1),35(2)用db更新链表后变为:LDB=1(4),3(4),4(3),5(8),13(3),15(3),45(3)，LMNI=2(3),6(8),14(2),34(1),35(2)经过第三步的处理，各链表变为:LDB=5;LMNI=6;LUB=5,6调用gen()函数产生候选项集并检查其在UB中的支持度计

16、数:CUD=5(8),6(8),56(6)，：最后得到LUB=5,6,56,算法结束根据频繁项集的定义，更新后的数据库中的频率项集应该是5,6,7,56,67，显然频繁项集7,67被丢失了虽然udb数据库很特殊，但由此可证明IUAMAR算法失去了一搬性，是不可靠的而如果把minsup设成0.3或者用个一般的增量数据库，UAMAR算法的缺点就被掩盖了综上所述，IUAMAR算法失去了最重要的可靠性，因而是失败的 基于事务树的增量挖掘算法基于树的频繁项集挖掘算法一直就是另一个研究热点，基于树的挖掘算法最大的优点就是不用产生候选项集，并且对事务数据库的扫描次数很少下面，文章将介绍由业宁，逸生，厚立提出

17、的基于事务线索树的算法5，并分析它的优缺点3.1 算法所使用的定义与概念定 义 1 设I=是一组项目集，D是一组事务集(也称之为事务数据库).D中的每个事务即是一组项目定 义 2 设序列S=， 将序列分成任意的两段S1=,S2=，其中,S1,S2非空，则称SI为S2的前缀,S2为S1的后缀.定义 3 事务线索树(transactiont hread tree,简称TT-tree)有且具有一个根结点，当结点数量n1时，其余结点可以分为m(m0)个互不相交的有限集,其中每个集合本身又是一棵树.设根结点为第0层，根结点的全部子结点组成第1层，子结点的全部子结点组成第2层， ，依次类推，直到叶子结点.

18、当层数大于1时，每个子结点都有一个唯一的指针指向其父结点，称该指针为线索.定 义 4 叶子结点所处的层数称为路径长度L定 义 5 结点索引表是由项目集I中的每一个项目I及支持度计数以及指向事务线索树中I，的结点链指针组成定义TT-tree中的结点由两个域构成，Item域保存项目集的名称，suport域保存该项目集当前的支持度计数3.2 TT -t re e构 造 算 法输入事务数据库D输出TT-tree算法步骤:stepl 打开事务数据库;创建一个root结点.step2 while(事务数据库结束?)step3 读一条事务T=step4 将事务中的项目I排序.step5 for each I

19、 in Tstep6 if(Match(TT-tree,I)为真)step7 Update ( TT-tree,Node)step8 elsestep9 Insert( TT-tree,I)stepl0 endifstepll endforstepl2 wend算法 中 的 3个子函数Match,Updat和Insert,分别定义如下:Match (TT-tree,I)函数从根结点开始匹配事务项目集序列和TT-tree上的一条路径，如果匹配则返回true，否则返回false.Update(TT-tree,Node)函数将链表中Node的计数加1，再将结点索引表的计数加1.Insert (fat

20、herNode,I)函数，形参为父结点fatherNode和项目I它的过程如下：step1创建一个新结点step2将结的点的项目集域设为Istep3将结点的suport域设为1step4将结点的首指针指向fatherNodestep5判断索引表中是否存在该结点的记录，若存在，相当支持度计数加1,若不存在，则创建它，最后把索引表中的结点和树中的相应结点相连接下面举个例子说明TT-Tree的构造算法设事务数据库如表3.2.1所示：表3.2.1 事务数据库TID项集1I1,I2,I52I2,I43I2,I34I1,I2,I45I1,I36I2,I37I1,I38I1,I2,I3,I59I1,I2,I

21、3按照上述算法可以得到如图3.2.1的TT-tree：I1I2I3I4I567622 RootI1:6I2:3I2:4I3:2I3:2I4:1I3:2I4:1I5:1I5:1图3.2.1：TT-Tree同结点的线索指针指向父结点的指针结点索引表由上图可知：如果从叶子结点逆向拆解TT-Tree，可以把图还原为原来的事务数据库，由此得到以下性质： 性质压缩的TT-tree和事务数据库是互逆的3.3 由TT-tree到关联规则的产生定 理 1 最大频繁集的长度小于等于线索树中最长路径的长度L.证 明 ：因为：最大频繁集事务集所以：|最 大 频 繁集的长度|事务集的长度|而 最长路径的长度=max|事

22、务集的长度|证 毕 .引理 1 频繁集的全部非空子集都是频繁的.定理 2 设 路径为，则一定有，该路径的支持度计数为min(m,n,o,.,x)=x证明： 由于构造TT-tree时，事务中的项目I中是按照序号排序的，且从root结点开始向下构造.因此同一条路径中的上层结点的数目一定大于等于下层结点的数目.因而 min(m,n,o,.,x)=x成立，证毕定理 3 从叶子结点开始，具有相同后缀全部路径的交集A的支持度计数，等于各个路径的子集A支持度计数之和.证明：根据TT-tree的构造算法，若两条路径完全相同，在树中的体现便是被压缩到同一分枝中如果两条路径有不同的前缀，则相同的后缀被压缩在同一分

23、枝中，而不同的前缀在不同的分枝中因此要求两条路径相同后缀部分的支持度计数，则将两条路径的支持度计数相加证毕定 理 4 通过逆向搜索TT-tree寻找各路径及其路径交集的支持度计数，如果其支持度计数大于等于频繁集支持度，则路径和路径交集的集合以及所包含的子集皆为频繁集.证 明 由性质1可知，TT-tree是事务数据库的压缩存储，其路径的支持度计数反映了相同事务的个数，大于等于频繁集支持度的路径，其集合即为频繁集.同理，由定理3可知，路径交集的支持度计数大于等于频繁集支持度，则路径交集亦为频繁集.易知频繁集的子集一定是频繁集.证毕挖 掘 算 法描述输入 T T-tree输 出 一个频繁集表算 法

24、步 骤:step1 forEach Node in Index_table_for_Node/从结点索引表中的最后一个结点开始step2 if Node.spportminsuport/不满足条件continue ;step3 elsestep4 将该结点插入FS1（频繁1-项集）中根据结点索引表指针，寻找TT-Tree中的相同结点，再根据线索指针逆向搜索到根结点.产生以该结点为后缀的一条或多条路径.step5 利用定理2计算各条路径的支持度计数，利用定理3计算路径交集的支持度计数.step6 产 生频繁集step7 end for下面以图3.2.1为例说明该算法是如何工作的(设最小支持度计数

25、为)首先查找结点索引表中的最后一个元素：I5,满足条件，将其插入FS1,FS1=I5:2搜索从I5到root的各条路径：I1,I2,I5,I1,I2,I3,I5路径长度：L(I1,I2,I5)=3，L(I1,I2,I3,I5)=4，路径支持度计数S(I1,I2,I5)=min(I1,I2,I5)=min(6,4,1)=1，S(I1,I2,I3,I5)=min(I1,I2,I3,I5)=min(6,4,2,1)=1，为方便起见，把S(I1,I2,I5)=1简记为I1,I2,I5:1最大长度为的频繁项集（简记为FS4）FS4=再计算路径的交集I1,I2,I3,I5:1I1,I2,I5:1=I1,I

26、2,I5:2得到FS3=I1,I2,I5:2根据引理可得FS2=I1,I2:2,I1,I5:2,I2,I5:2再从结点索引表中的I4开始，FS1=I5:2,I4,2，搜索到root的各路径：I1,I2,I4:1,I2,I4:1这两条路径本身不产生频繁项集，考虑它们的交集I1,I2,I4:1I2,I4:1=I2,I4:2，更新FS2得FS2=I1,I2:2,I1,I5:2,I2,I4:2,I2,I5:2注意：此处所说的更新是指用最新的支持度计数代替原来的支持度计数而并非叠加因为交运算本身就处理了需要叠加的情况然后，从结点I3开始，FS1=I5:2,I4:2,I3:6，搜索I3到root的各路径I

27、1,I2,I3:2,I1,I3:2,I2,I3:2三条路径本身便是频繁项集，更新相应的FS得：FS3=I1,I2,I3:2,I1,I2,I5:2，FS2=I1,I2:2,I1,I3:2,I1,I5:2,I2,I3:2,I2,I5:2计算路径交集I1,I2,I3:2I1,I3:2I2,I3:2=I3:6，暂不考虑FS1，I1,I2,I3:2I1,I3:2=I1,I3:4，I1,I2,I3:2I2,I3:2=I2,I3:4，I1,I3:2I2,I3:2=I3:4，更新相应FS得：FS2=I1,I2:2,I1,I3:4,I1,I5:2,I2,I3:4,I2,I5:2从I2开始, FS1=I5:2,I

28、4:2,I3:6,I2:7,搜索I2到root的路径I1,I2:4,I2:3 更新相应的频繁项集:FS2=I1,I2:4,I1,I3:4,I1,I5:2,I2,I3:4,I2,I5:2从I1开始, FS1=I5:2,I4:2,I3:6,I2:7,I1:6,搜索I1到root的路径：I1:6算法结束最后得到如表3.3.1所示的频繁项集：表格3.3.1 最终的频繁项集FS4FS3FS2FS1I1,I2,I3:2I1,I2,I5:2I1,I2:4I1,I3:4I1,I5:2I2,I3:4I2,I5:2I2,I4:2I5:2I4:2I3:6I2:7I1:63.4 算法分析算法优点：(1) 该算法支持增

29、量频繁模式挖掘，算法结束后，将TT-tree保存，若有新的增量数据库需要添加，可将增量数据库在原TT-tree的基础上压缩成树，即从数据库的更新变成树的更新，树更新完毕后重新由树生成关联规则(2) 该算法只需要扫描一便原始数据库，相比Apriori算法大大减少了IO开销(3) 该算法利用树（链表）来压缩数据库，并产生频繁项集，不但节省了存贮空间，而且由于链表在内存操作中的高速性，节省了算法实现后程序运行的时间开销(4) 算法从整个数据库着眼，从最大项集入手，对索引树中的元素逐个处理，保证了产生频繁项集的完整性，而支持度的合理更新，也保证了不会出现错误的冗余项集算法的缺点：(1) 若有增量数据库

30、加入，需要重新由TT-tree产生频繁项集，上次挖掘产生的结果没有得到充分利用，而且增量数据库越大，增量数据库加入的次数越多，需要的重复的交运算越多，这个缺点越明显(2) 若产生的TT-tree比较复杂，如各层（尤其是层）结点的数目过多，算法就面临着大量的交运算但要保证算法的可靠性，这个缺点是不可避免的综上所述，虽然“基于事务线索树的一次扫描关联规则增 量 挖 掘 算 法”具有它的弱点，但相对来说，它还是是一个成功的，高效的改进型算法4 基于散列思想的增量频繁模式挖掘算法宋中山，成林辉，吴立峰，提出的LIUA算法便是基于散列的，非常简单，容易实现，下面文章就介绍这个算法4.1LIUA算法简介L

31、IUA(ListIn crementalU pdatingA lgorithm，链表增量数据挖掘算法)利用链表插入、删除效率高的特性，在数据挖掘的过程中充分保存以前已经挖掘出来的信息，来提高随后的增量挖掘的效率.算法主要分为扫描DB和扫描db两部分.这里DB为更新前的目标数据库，db为数据库中新增加的记录集.(1) 扫 描 DB.首先根据用户输人的物品的种类n建立n个链表Listn,Listi(i=1,2,.,n) 的每个节点存在两个域:item域用来存放物品组合的名称;count域用来存放对应物品的支持度.Listi用来存放i-itemset(i-项集)的所有情况.例如:List1 存 放1

32、-项集的所有情况，并根据count值按降序排列.然后 扫 描 DB中的第一条事务，得出这条事务的所有非空子集(非空子集代表这条事务中所有物品的组合情况)，根据非空子集物品的个数(项集的个数)放人到对应的链表中，例如:11,13是第一条事务的其中一个子集，由于它包含两个物品:11,13，所以应放入List2 中.如果此链表已经包含该子集，则将对应的count+1，并重新将链表按照降序有序化;如果此链表不包含该子集，则在链表尾加人该子集，同时将对应的count置1.依次类推，对每条事务都进行类似的处理.(2) 扫 描 增加数据库db.扫描db实现增量数据挖掘.在时间比较充裕，即用户不是急需计算结果

33、的情况下，我们可以采用扫描DB的办法处理db，再把处理的结果链表和已保存的DB的结果链表进行迭加，以便今后的增量数据挖掘.在时 间 比 较紧迫，即用户需要在短时间内得到关联规则的情况下，用户急需知道的并不是所有的关联规则，可能只是需要符合某种条件的关联规则来进行决策.此时可以要求用户按照他的需求先设置参数，这样可以提高查找效率，节省查找时间.相关参数有:num : 用户 想知道的最大的关联物品数量;minsup :用户设立的门槛值(即关联物品在事务数据库中出现的最小次数).根据 num 值选择以前保留的List1 ,List2,.,Listnum链表;然后扫描库里的每一条事务，得出小于等于nu

34、m的非空子集(用户想知道的关联规则的相关物品的个数)，根据非空子集中项集的个数放人到对应的链表中，处理方法类似扫描DB的处理方法.4.2算法描述(1) 扫 描 DBfor( i= 0; in ;i+)/n代表所有物品的种类creat Listi=NULL;/建立链表，并初始化for all TDB doproduce all_subset;/代表非空子集for all_subset docount subset.i; /计 算 当前非空子集的项集个数if(listi.find(subset)=TRUE)listi.subset.count+listi.sort/排序elseinsert end

35、 of listilisti.subset.count+由于 D B 存储的是海量数据，在本次扫描中将会花费很长的时间.为了提高效率，可以考虑并行运算，将DB分成几个部分，各部分分别用多台机器进行扫描运算，最后将各链表进行迭加，这样做将大大提高运算速度.在CPU的计算及硬件v0的发展情况来看，多维阵列的存储方式，可以有效提供较佳的搜寻速度;而以目前硬件配置的价格日趋下降的趋势来看，资料的存放空间已经不是一个严重的问题了(2) 扫 描 增量数据库dbfor all Tdb doproduce all_subsetnum;/产生小于等于num的子集for all subset docount su

36、bset.i;/计 算 当前非空子集的项集个数if(listi.find(subset)=TRUE )Listi.subset.count+ ;Listil.sort; /排 序elselinsert end of Listilisti.subset.count+这个算法的思想很简单，文章就不再举例说明了4.3算法分析算法优点：(1) 由于处理每一条事务的时候都考虑的它的所有子集，该算法显然具有可靠性(2) 该算法只要扫描一边事务数据库(3) 该算法利用链表实现，减少了程序运行的时间开销，同时由于链表保存了散列结果，有利于对增量数据库的处理算法缺点：该算法最大的缺点是面对同一事务中项比较多的时

37、候处理得非常缓慢，而通常原始数据库比较大，包含“长事务”的可能性也较大，因此该算法处理原始数据库的时候要花不少时间，虽然文章也提出了用并行算法来解决这个问题，但这却增量了处理器开销5增量挖掘算法在火锅销售数据库中的应用5.1算法的选择通过对上述三个增量频繁模式挖掘算法的介绍，我们对增量频繁模式的挖掘有了一定的认识，基于融合思想的算法，由于规则制定的复杂性，可靠程度不高，而且对原始、增量数据库的挖掘也是基于原始的Apriori算法或其改进型，效率不是很理想基于散列思想的算法，对于增量数据库的处理比较合适，因为增量数据库通常情况下都比较小，但它对原始数据库的处理不太理想，开销很大幸好前面介绍的基于

38、事务线索树的算法，对于原始数据库的处理非常合适因此文章决定将“事务线索树”和“散列”两种算法结合起来以实现对火锅销售数据库的增量挖掘由于增量数据挖掘采用散列的算法，所以要求在“基于事务线索树的一次扫描关联规则增 量 挖 掘 算 法”中，不但要挖掘出频繁项集，而且也要保存非频繁的项集，这可以通过项集链表来现实算法的描述数据结构struct listitemsupportnext其中item为项集名称，support为项集的支持度计数,next指向下一个结点，以构成链表(1) BEGAIN(2) 输入DB,minsup(3) 使用3.2节的算法构造事务树(4) creat listn/创建一个数据

39、，每个元素为一个链表，且listn存放所有的n-项集如list存放所有的项集n为索引表的结点的个数，也代表一条事务中最大可能出现的项集数(5) forEach Node in Index_table_for_Node/从结点索引表中的最后一个结点开始(6) list1.insert(node) 将该结点插入list1（1-项集）中(7) 根据结点索引表指针，寻找TT-Tree中的相同结点，再根据线索指针逆向搜索到根结点.产生以该结点为后缀的一条或多条路径.(8) 利用3.3节定理2，计算各条路径的支持度计数，利用定理3计算路径交集的支持度计数.(9) 将所有路径及其支持度计数插入到相应的lis

40、t链表中(10) end for(11) get db/输入增量数据库(12) for each item in db/对增量数据库中的每一项进行处理(13) creat subset/产生这条事务的所有非空子集(14) for each subset/处理每一个非空子集(15) subset.count/计算子集包含的项的个数(16) if(listsubset.count.find(subset)=TRUE)(17) listsubset.count.subset.support+(18) else(19) listsubset.count.add(subset)(20) listsubs

41、et.count.subset.support=1(21) end for(22) end for(23) for i=1,i=minsup)(25) output listi.item(26) item+(27) end for(28) END5.2 实现过程5.2.1 用户界面用户界面基于一个对话框，其中包含两大部分如图5.1：图5.1 用户界面图5.1中左边的文本框用来输出关联规则的挖掘结果，右边的设置框用来指导用户输入原始增量数据库，以及支持度计数的值，当用户按下“确定”按键，程序首先判断应该进行原始还是增量数据库的挖掘，并调用相应过程挖掘原始或增量数据库中的频繁项集，并将结果输出在左

42、边的文本框中5.2.2文件的组织为了增量挖掘的需要，程序需要将5.1节算法中，由事务线索树挖掘而出的项集列表（本例命名为itemsetlist）保存在一个外部文件（本例为itemlist.dat）详细说明请参考文献9，后面使用散列算法挖掘增量数据库挖掘时，先将这个文件读入到内存中，再将散列得到的结果直接添加到列表中，最后保存，以便于下次的增量关联规则挖掘由于项集列表中保存了所有的项集，因此向用户输出结果的时候需要对照用户指定的支持度阈值，并将满足条件的结果输出项集在内存中以动态创建的树的方式保存，树中的结点采用CStringArray10与CUIntArray12对像相结合的方法来保存数据，C

43、StringArray可以方便地对字符串进行操作，CUIntArray对数组的操作十分便利基于增量挖掘的需要，程序要用到不至一个数据库，因此程序所用数据源需要动态注册，这个可以使用SQLConfigDataSource()11函数实现，整个程序结束后再将数据源注销整个程序的流程如图5.2：输入参数程序开始参数有效?Itemlist.dat存在？挖掘原始数据库挖掘增量数据库从itemsetlist中读出项集项集频繁？输出项集结束表尾？YNNYYNYN图5.2增量频繁模式挖掘流程图图5.3(a)为挖掘原始数据库的流程，图增量数据库5.3(b)为挖掘增量数据库的流程，由于基于事务线索树的算法，和基于

44、散列思想的算法已经在前面详细介绍过了，这是不再叙述输入原始数据库图5.3(a):原始数据库挖掘流程图5.3(b):增量数据库挖掘流程开始挖掘原始数据库读取数据库中的一条记录最后一条记录?构建事务树头构建itemsetlist表头更新事务树头使用索引树算法挖掘事务树更新itemsetlist表结束NY将itemsetlist表存入Itemlist.dat注册数据源注销数据源开始挖掘增量数据库输入增量数据库从Itemsettab.bat中读取iitemsetlist读取数据库中的一条记录使用列散算法处理更新itemsetlist表最后一条记录?将itemsetlist表存入Itemlist.dat结束YN注册数据源注销数据源5.2.3程序示例:设有如表5.2.3.1的原始数据库和如表5.2.3.2的增量数据库:表5.3.2.1 原始数据库DB事务编号I1I2I3I4I511100120101030110041101051010060110071100811101911100表5