注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

创业....投资学习....

记录技术随想,结交志同道合朋友

 
 
 

日志

 
 
关于我

season,一直关注家乡的发展,关注个人的成长.工作后关注创业,关注投资.....可却忘记了一点,没有空中楼阁.于是我把视线投向了如何准备创业,创业需要什么?资源(PROFIT的六个方面?)?勇气?经验?教训?...所有的都对,但所有的都应该脚踏实地.所以,我能做的就是学习学习再学习......可应该在什么样的生存状态下学习?于是我还要解决生存的问题,再于是工作+学习便成了我日常生活的主题,而我却希望有一天事业+家庭变成我生活的主题

关联规则挖掘技术若干问题研究 第三章  

2007-03-23 09:54:01|  分类: BI讨论 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

 

第三章                基于支持度变化的FP-Growth算法

由于数据挖掘经常面对的是数据量非常巨大的数据库或数据仓库,因此就迫切需要高效的算法来挖掘关联规则。目前在关联规则算法中为了发现频繁项集,人们己经研究了各种各样有效的算法。一般说来,这些算法都是遵循两个原则:一,要建立频繁项集的一个候选集;二,在候选集中找出确实包含频繁项集的所有子集。然而在现实的应用领域中,由于使用数据挖掘软件的大多数用户缺乏实践经验,用户在开始时对挖掘所需要的最小支持度(min_sup)并没有一个明确的值,因此就会出现这样的情形:经过一次关联规则挖掘后用户对自己找出的关联规则并不满意,转而再去进行一遍又一遍的挖掘,直到获得满意的效果,显然对于大型的数据库及数据仓库来说这样的重复工作是非常浪费时间的。同时我们也注意到,重复的挖掘工作也存在着重复计算,因此我们就有必要寻找一种针对支持度变化的高效挖掘算法。本章在FP-Growth算法的基础上提出了针对这种情况的快速算法,利用前次的挖掘结果进行再挖掘,从而大大节省挖掘时间。

§3.1         相关概念与问题描述

基于支持度变化的关联规则更新算法属于增量更新研究范畴,下文是对关联规则更新问题的相关概念与问题进行的描述。

1 关联规则更新问题分类[4,25,34,35]

根据实际应用需求,关联规则的更新问题可以分为以下几种情况:

(1)事务数据库不变,最小支持度发生变化时,关联规则的高效更新问题;

(2)最小支持度不变,一个事务数据集添加到事务数据库D中去时,如何生成最新事务数据库D'中的关联规则

(3)最小支持度不变,从事务数据库中删除一个事务数据集后,如何高效地生成事务数据库中的关联规则。

至于其它情况,可由上述三种情况组合而成,因此,这三种情况是更新问题的基础和核心。

2 增量更新现状[13,14]

Cheung 等首先考虑了关联规则的高效更新问题,提出了FUP[13]算法,该算法能有效地利用已经获得的关于频繁项目集的结果,大大降低了关联规则的更新代价。 随后他们又在此基础上提出了FUP2算法,从而不仅可以处理交易增加的情况,还可以处理交易删除与修改的情况。Feldman提出了一种称为Border算法的关联规则的更新技术,在用户指定的最低支持度为绝对数且保持不变的条件下,该算法只需考察所有真子集均为频繁项目集而本身却不是项目集的情况。在上述这些算法的执行过程中都产生了大量的候选项目集,并占用大量的空间和时间开销。

FUP (Fast Update) 算法就是解决增量更新问题的一种经典算法。它的基本思想是:对任意一个k (k 1) 项集,若它在DB和db 中都是频繁项集,那么它在DB db中同样是频繁项集;若它在DB 和db 中都是非频繁项集,那么它在DB db 中同样是非频繁项集;若它仅在DB(db) 中是频繁项集,则其支持计数应该加上db (DB) 中的支持计数来决定它在DB db中是否为频繁项集。UWEP (Update With Early Pruning) 算法借鉴了FUP2 和Partition 算法。它的基本思想是对于候选k 项集不必等到第k 次遍历,就尽可能早地剪切掉非频繁k-项集,有效地减少了候选项集的数目。该算法的不足之处是对于预剪切的策略考虑得还不太完善。

以上算法都是针对Apriori算法,尽管FP-Growth 算法克服了先前关联规则挖掘算法的不足,节省了大量的空间和时间开销,但由于它没有考虑挖掘关联规则的高效增量更新问题,严重限制了该算法的实际应用。目前研究者已经提出了一些基于FP 树的增量更新关联规则的算法,例如文献[10]和[11]等分别提出的最小支持度发生变化后关联规则的更新和事务数据库发生变化后关联规则的更新;文献[12]则讨论了最小支持度不变,一个事务数据集添加到事务数据库中去时,如何生成事务数据库的频繁项目集的情形。

3 问题描述

目前,发现关联规则的问题受到许多学者的极大关注,并相继提出了多种快速发现关联规则的挖掘算法。这些算法能有效地挖掘出静态事务数据库中的关联规则,然而,在现实世界事务数据库中,数据是随时间的变化而变化的。商业机构中的交易是一个不断进行的过程,交易行为的模式很可能随时间呈现出某种发展趋势,使得当前已发现的关联规则可能不再生效,而可能存在新的有效关联规则有待于进一步去发现。因此,能否有效地挖掘出动态事务数据库中的频繁项目集或关联规则是衡量一个算法好坏的关键因素。在实际的挖掘过程中,一方面用户往往需要对最小支持度和最小置信度这两个阈值进行不断调整来寻找真正感兴趣的规则;另一方面数据库的数据是不断进行添加、修改和删除的,这是一个动态的交互过程。随着时间的改变,关联规则随之不断地进行更新。

解决关联规则更新问题最简单的方法就是运用挖掘算法对更新后的数据库重新进行挖掘运算。这种方法虽然实现简单,但是它没有充分利用以前的发现结果,效率较低。

鉴于这些情况,目前关联规则更新的研究重点在于如何使算法充分利用以往挖掘出来的结果来加速本次挖掘过程。因此,本文的重点落在了最小支持度变化后关联规则的更新问题。

§3.2         FIUA1算法

定义3.1:设旧的最小支持度为s L 1为D中1-项频繁项集,L为D中频繁项目集的集合。同样地,对于新的最小支持度s'L'1为D中1-项频繁项集,L'为D中频繁项目集的集合。

当最小支持度发生改变时,可分为两种情况: (1) s > s'; (2) s < s'

性质3.1:如果s > s', 那么L 1 L'1L L'。如果s < s',那么L 1 L'1L L'

对于任意项目集c L1 (c L),有c.supD  s 成立,如果s > s',那么c.supD> s', 即c L'1 (c L'),故有L 1 L'1L L'成立。同样可知如果s < s',那么L 1 L'1, L L'。由性质1可知,在第2种情况下,频繁项目集的更新是很简单的,只需在原来的频繁项目集L 中删除所有支持度小于s'的项目集即可;在第1种情况下,当前已发现的频繁项目集L 仍然生效,而原有的一些非频繁项目集可能成为新的频繁项目集,因此,如何发现D中所有新的频繁项目集(记为LN )将是第1种情况的关键问题,下面将集中讨论这一问题。

定义3.2:当s > s'(即支持度降低时),设LNL'-L={I L'| },表示当支持度下降后(s')比原支持度条件(s)下多产生的频繁项集。LN1L'1-L 1={I  L'1| },表示当支持度下降后(s')比原支持度条件(s)下多产生的1-项频繁集。

由定义3.2,我们可以方便的得出:L'LN +L,而对于L是已知的频繁项集集合,因此只需要求的LN,我们就可以求出支持度变化后的频繁项集集合L'。下面的主要问题就集中在了如何求解LN

性质3.2:1-项集LN1对应的频繁项集即为LN

证明:由2.2.3节有关FP-Growth算法的介绍中,条件模式基的生成是“对Tree头上的每个 i”进行循环操作,即FP-Growth的生成次序是根据1-项频繁项集中的排序,从最低的支持度计数的项开始逐项建立条件模式基并生成相应规则。而当支持度降低时,首先1-项频繁集中的项会增加,增加的量根据定义2可知为LN1,因此,1-项集LN1对应的频繁项集即为LN

性质3.2提供了求解LN的思路,即对1-项集LN1运用FP-Growth算法即可进行求解。然而,FP-Growth算法预求解关联规则,需要另外一个极其重要的变量:对应的FP-Tree。当支持度发生变化时,经典的FP-Growth算法中,FP-Tree也会随之变化,因此,求解的问题就将范围缩小至求解支持度变小后如何求解对应的FP-Tree的问题。

性质3.3:设Htable [1 : m ]Htable' [1 : m']分别表示支持度为s 、s'时的频繁项目头表,n =|L N1|,则L N ={ Htable' [ k ]. Item->name│m < k< m'} ,m'= m + n ,

证明:由于m = L 1, m'= L'1│,且L'1=L 1 L N1,L 1 L N1 = ,因此m'= │L 1│+ |L N1|= m + n 。另外, 由于L N1中各项目的支持度介于s′与s 之间,而L 1中各项目的支持度均不小于s ,因此L N1中各项目的支持度均小于L 1中任意项目的支持度。又因为频繁项目头表Htable′[1 : m′]是按其支持度降序排列的,故L N ={ Htable' [ k ]. Item->name│m < k< m'}。证毕。

性质3.4:设FP-Tree,FP-Tree′分别表示支持度为s 、s′时的频繁模式树,则L N1中的项目所对应的节点均为FP-Tree′的叶子节点或叶子节点的前缀节点,且无L 1中节点介于这些节点之间。

证明:由性质3.3 和频繁模式树的构造过程可知,该性质是显然成立的。证毕。

按照性质3.3 ,3.4 可以很方便地实现FP-Tree与FP-Tree′间的转换,只需增加或删除频繁模式树的叶子节点即可。据此可得由FP-Tree来构造FP-Tree′的方法:调用Adjust FP-Tree ( FP-Tree , L N1 ) 。

过程Adjust FP-Tree ( Tree , ) 描述如下:

算法3.1:Adjust FP-Tree ( Tree , )

输入:Tree ,

输出:FP-Tree′

过程:

Procedure Adjust FP-Tree ( Tree , )

/ / 在Tree 中添加对应于 中项目的节点

1)       if ( ) then {

2)       L′= L 1 ; / / 将L 1 中各项目按支持度降序排列存放在L′中

3)       for each transactions t D do {

4)          t′= L′  t;  / / 取出t 中属于L′的项目

5)          search Tree and insert t′ into Tree ;

}

}

  / / Tree 中已包含t′中非 中的项目

6)  else do nothing;  / / Tree 不变

由定义3.2 可知,为了求LN1,只需求得L′1和 L1即可。因此,调用FP-Growth 时应将 限定在LN1中,递归调用FP-Growth 时无需作限制。

算法3.2:增量式更新算法FIUA1 ( s′< s) . [14]

输入:支持度为s 时D 中的所有频繁项目集L和FP-Tree,新支持度s′。

输出:支持度为s′时D 中的所有频繁项目集L′

Do begin

1)  if ( ) then {

2)  调用Adjust FP-Tree (FP-Tree , LN1) 得到FP-Tree′;

3)  for each / / 求L′N

4)          { 调用L =FP-Growth(FP-Tree′, ) ;

5)                 L′= L ∪L  ;

             }

      }

6)   output (L′);

end

§1.3         基于最小支持度变化的FP-Growth算法

FIUA1算法解决了FP-Growth算法中增量更新的部分问题,但FIUA1算法本身也存在着不足,主要体现在FIUA1算法仍不可避免的对原有数据源进行2次遍历,虽然针对原有FP-Growth算法进行了效率提升,但效率的提升并不明显。

针对这种现象,提出了基于完全FP-Tree的IFIUA1算法,具体的思想如下。

定义3.3:极小值 ,设定趋近于0的一个确定的支持度阈值,该极小值小于等于任意给定的支持度阈值S,亦即: 。

定义3.4:完全1-项集,在极小值为最小支持度阈值时产生的1-项集。完全1-项集包含任意的以最小支持度阈值S生成的1-项集,完全1-项集记为 。

定义3.5:完全FP-Tree,运用FP-Tree生成算法并将其最小支持度阈值设定为极小值 时生成的FP-Tree。完全FP-Tree包含任意一棵以最小支持度S生成的FP-Tree,完全FP-Tree记为 。

这样,并根据3.2节,可得 , , ,且 , 。因此,只需求得LN1,并根据求得的LN1,在 进行挖掘即可求得新增的频繁项集LN,而求LN1可根据如下思路进行:将原有支持度下1-项集保存并记为L1,在 中求得新支持度下1-项集并记为 ,这样即可求得 。而且求L1与 均在 中进行,无需遍历原有数据源。

因此, IFIUA1可如下描述。

算法3.3:增量式更新算法IFIUA1

输入:支持度为s 时D 中的所有频繁项目集L,新支持度s′。

输出:支持度为s′时D 中的所有频繁项目集L′

Do begin

1)     根据 与最小支持度S求得 ;

2   ;Tree=

3)   if ( )

4)   { if ( Tree只包含单路径P)

5)             {   对路径P中节点的每个组合(记为 )

6)               生成模式 x,支持数=B中所有节点的最小支持度

                 }

7)     else       for each

8)          {   生成模式 = i x,支持度= i.support;

9)           构造 的条件模式库和 的条件FP树Tree ;

10)                 if Tree  != 空集

11)                调用L =FP-Growth(Tree , ,S) ;

12)                  L’= L ∪L  ;

                   }

          }

13)      output (L′);

end

由上,以下整理出基于最小支持度变化的FP-Growth算法的运算逻辑,并在此运算逻辑基础上给出具体的算法实现伪码。运算逻辑如下:1,首先生成一棵完全FP-Tree( ),同时生成完全1-项集 ,并将 、 存储保存;2:设定 , , ;3:根据设定的最小支持度阈值,在 中生成1-项频繁集 并存储保存;3:求得 ;4:根据LN1在 中进行挖掘运算产生频繁项集集合;5:设定 并存储。本节根据一般的FP-Growth算法运算阶段,将逻辑步骤1和2归为算法1(FP-Tree的生成)阶段,将逻辑步骤3-5归为算法2(频繁项集生成)阶段。每阶段具体过程如次:

算法3.4:构造完全FP-Tree:

输入:交易数据库DB,极小值 。

输出: ,

步骤:

1)扫描数据库DB一遍,得到频繁项的集合F和每个频繁项的支持度。把F按支持度递降排序,结果记为 。

2)创建FP-Tree的根节点,记为T,并且标记为’null’。然后对DB中的每个事务Trans做如下的步骤。根据L中的顺序,选出并排序Trans中的事务项。把Trans中排好序的事务项列表记为[p|P],其中p是第一个元素,P是列表的剩余部分。调用insert_tree([p|P],T)。

函数insert_tree([p|P],T)的运行如下:

如果T有一个子结点N,其中N.item-name=p.item-name,则将N的count域值增加1;否则,创建一个新节点N,使它的count为1,使它的父节点为T,并且使它的node_link和那些具有相同item_name域串起来。如果P非空,则递归调用insert_tree(P,N)。

3) , , ,S=1 ;

4)存储并输出 ,

算法3.5:基于最小支持度变化的FP-Growth算法:

输入: , ,S’

输出:L

procedure FP-Growth ( , ,S’)

 {

1)if( )//S为原支持度,初始值为1

2)      then{从规则库中直接筛选支持度为S’的关联规则;}

3)else

4){  根据 与最小支持度S求得 ;

5)    ;Tree=

6)   if ( )

7)   { if ( Tree只包含单路径P)

8)             {   对路径P中节点的每个组合(记为 )

9)               生成模式 x,支持数=B中所有节点的最小支持度

                 }

10)     else     for each

11)         {   生成模式 = i x,支持度= i.support;

12)           构造 的条件模式库和 的条件FP树Tree ;

13)                 if Tree  != 空集

14)               调用L =FP-Growth(Tree , ,S) ;

15)                  L= L ∪L  ;

                   }

               }

16)  , ;

17)  output (L);

}

}

§3.4         算法分析与试验

1 算法分析

    基于最小支持度变化的FP-Growth算法在第一次调用时生成完全1-项集和完全FP-Tree,克服了FIUA1算法在支持度变化时需要重新2次扫描事务数据库的缺点。但同时也带来了如第一次调用时间花销加大,占用了更多的空间等的缺点。

2 试验平台

本文在VS.Net平台下使用C#语言实现了基于最小支持度变化的FP-Growth算法,并把该算法与FIUA1算法进行了比较。使用的数据为根据学生成绩数据的特性结合课程信息库仿真生成的10K事务数据。仿真程序算法如下:

算法3.6:仿真数据生成

输入:欲生成事务数

输出:仿真数据集

Gen_Data(count)

1) {for each i=1;i<count;i++//count为预定义的事务数

//生成[40,60]区间那随机数,学生平均选课数为40~60门。

2)     course_count=Get_random(40,60);

3)     for each j=1;j<course_count;j++

4)            course= Get_Course();//获取课程相关信息

5)            grade= Get_random(0,100);//生成成绩

6)            insert(i,course,grade) into D;//存储}试验中所使用的计算机为Intel Celeron 1.7GHz, 768MB内存,操作系统为Windows server 2003,数据存储系统为SQL Server 2005。

  评论这张
 
阅读(143)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018