频繁模式集挖掘算法TFPDM的研究

频繁模式集挖掘算法ＴＦＰＤＭ的研究　

林红飞。庄卫华　

（河海大学计算机及信息工程学院，南京２１００９８）　

Ｅ—ｍａｉｌ：ｃｏｓｍｏｓ＠ｈｈｕ．ｅｄｕ．ｃｎ　

摘　要：受经典的Ａｐｒｉｏｒｉ算法思想和ＦＰ—Ｇｒｏｗｔｈ算法思想的启发．在结合两者优点的基础上提出了一种新的算法思想，　

它是对传统的ＦＰ～Ｇｒｏｗｔｈ算法的变形。该算法只需对数据库扫描一次，可以同时对全局和局部频繁模式集进行挖掘，减　

少了对发生增益数据库挖掘的费用。理论分析表明算法是有效的、可行的。　

关键词：全局和局部频繁模式集：变形的频繁集挖掘算法；ＦＰ－Ｇｒｏｗｔｈ算法；Ａｐｒｉｏｒｉ算法　

文章编号：１００２—８３３１（２００６）３２—０１６０—０４　文献标识码：Ａ　中图分类号：ＴＰ３１１　

ＴＦＰＤＭ　ｆｏｒ　Ｍｉｎｉｎｇ　Ｆｒｅｑｕｅｎｔ　Ｐａｔｔｅｒｎｓ　

ＬＩＮ　Ｈｏｎｇ—ｆｅｉ，ＺＨＵＡＮＧ　Ｗｅｉ－ｈｕａ　

（Ｃｏｌｌｅｇｅ　ｏｆ　Ｃｏｍｐｕｔｅｒ　ａｎｄ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ．Ｈｏｈａｉ　Ｕｎｉｖｅｒｓｉｔｙ，Ｎａｎｊｉｎｇ　２１００９８，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ：Ｔｈｉｓ　ｐａｐｅｒ　ｐｒｏｖｉｄｓ　ａ　ｎｅｗ　ａｎｄ　ｅｆｆｅｃｔｉｖｅ　ａｌｇｏｒｉｔｈｍ　ｂａｓｅｄ　ｏｎ　Ａｐｒｉｏｒｉ　ａｎｄ　ＦＰ＿Ｇｒｏｗｔｈ．Ｉｔ　ｉｓ　ａ　ｔｒａｎｓｆｏｒｍａｔｉｏｎ　ｏｆ　ＦＰ－Ｇｒｏｗｔｈ．Ｉｔ　ｎｏｔ　ｏｎｌｙ　ｍｉｎｅｓ　ｔｈｅ　ｇｌｏｂａｌ　ａｎｄ　ｌｏｃａｌ￣ｅｑｕｅｎｔ　ｐａｔｔｅｒｎｓ，ｂｕｔ　ａｌｓｏ　ｒｅｄｕｃｅｓ　ｔｈｅ　ｅｘｐｅｎｄｉｔｕｒｅ　ｏｆ　ｕｐｄａｔｅｄ　

ｄａｔａｂａｓｅ＇ｓ　ｍｉｎｉｎｇ．Ｗｈａｔ＇ｓ　ｍｏｒｅ，ｉｔ　ｏｎｌｙ　ｎｅｅｄｓ　ｏｎｅ　ｄａｔａｂａｓｅ’Ｓ　ｓｃａｎｎｉｎｇ．Ｔｈｒｏｕｇｈ　ａｎａｌｙｚｉｎｇ，ｗｅ　ｃａｎ　ｓｅｅ　ｉｔ　ｉｓ　ｅｆｆｅｃｔｉｖｅ　ａｎｄ　

ｆｅａｓｉｂｌｅ，　

Ｋｅｙ　ｗｏｒｄｓ：ｇｌｏｂａｌ　ａｎｄ　ｌｏｃａｌ　ｆｒｅｑｕｅｎｔ　ｐａｔｔｅｒｎｓ；ＴＦＰＤＭ；ＦＰ—Ｇｒｏｗｔｈ；Ａｐｒｉｏｒｉ　

１　前言　

频繁模式是产生关联规则的基础．是数据挖掘的重要内容　

之－－［“。Ａｇｒａｗａｌ于１９９３年首次提出布尔型关联规则问题及相　

应的Ａｐｒｉｏｒｉ算法【２ｌ　ｌ后，数据挖掘领域的研究者在关联规则挖　

掘与更新上做了大量的工作【４＿５１。其中，韩家炜等人提出的频繁　

模式集（或称频繁集、频繁项目集）挖掘算法（ＦＰ—Ｇｒｏｗｔｈ）…采用　

压缩ＦＰ—ｔｒｅｅ存储结构。打破了Ａｐｒｉｏｒｉ—ｌｉｋｅ框架．可以有效地　

提高频繁模式集的挖掘效率。　

但Ａｐｒｉｏｒｉ算法每生成一个Ｋ项频繁集都会产生大量的候　

选集和对数据库扫描一次．这成为Ａｐｒｉｏｒｉ算法严重的瓶颈…；　

ＦＰ—Ｇｒｏｗｔｈ算法对数据库至少要进行２次扫描．同时如何提高　

经常发生增益的数据库的挖掘效率也是一个值得关注的问题，　

致使这些算法在大型数据库中的应用效率不容乐观。　

本文提出了一种变形的频繁集挖掘算法（Ｔｒａｎｓｆｏｒｍａｔｉｖｅ　

Ｆｒｅｑｕｅｎｔ　Ｐａｔｔｅｒｎｓ　Ｍｉｎｉｎｇ　Ａｌｇｏｒｉｔｈｍ．ＴＦＰＤＭ）．它有别于现有的　

基于ＦＰ—ｔｒｅｅ思想的挖掘算法，它的主要的特点是：只要对数据　

库扫描一次。现实生活中数据库中的信息随着时间的推移一直　

在增益．当要对整个数据库重新挖掘频繁集时．采用本算法的　

数据结构只要扫描一次数据库中信息发生增益的那部分，而不　

必对数据库中以前的信息重新扫描，同时利用本算法的数据结　

构可以挖掘目前一段时间内的局部频繁集：与ＦＰ—Ｇｒｏｗｔｈ算法　

相比，除了在数据结构方面采用ＦＰ—ｔｒｅｅ思想外，算法的各步骤　

都有别于ＦＰ—Ｇｒｏｗｔｈ算法：通过实验可以发现Ａｐｒｉｏｒｉ算法寻　

找频繁集主要的计算是在生成频繁２一项集Ｌｋ上　。ＴＦＰＤＭ算　

法采用的Ａｐｒｉｏｒｉ思想只要生成少于ｍ个２一项候选集（ｍ是项　

目的总数），并只要对有限个数的事务集进行扫描。　２相关知识　

２．１　支持度和频繁集　

设，＝　，ｉ　，…，ｉ　ｌ是ｍ个不同项目（或称事务元素）的集　

合，给定事务数据库ＤＢ．ＤＢ．ｃｏｕｎｔ表示数据库中的事务数。　、　ｙ　，，ＤＢ的关联规则的形式形如：　—ｙ，此关联规则的支持度　

（ｓｕｐｐｏｒｔ）：ｃｏｎｔａｉｎ（Ｘ，Ｙ）／ＤＢ、ｃｏｕｎｔ，ｃｏｎｔａｉｎ（Ｘ，Ｙ）表示ＤＢ中同　

时包含　和ｙ的事务数：此关联规则的置信度（ｃｏｎｆｉｄｅｎｃｅ）是　

个条件概率：ｃｏｎｔａｉｎ（Ｘ）／ｃｏｎｔａｉｎ（Ｙ）。ｃｏｎｔａｉｎ（Ｘ）和ｃｏｎｔａｉｎ（ｙ）　

分别表示ＤＢ中包含　的事务数和包含ｙ的事务数。　在ＤＢ　

中的支持度是指ＤＢ中包含　事务的百分比，记为Ｘ．ｓｕｐ。　频繁模式：如果　的支持度不小于用户给定的最小支持　

度阈值Ｓ，则称　为ＤＢ中的频繁模式，模式的项目个数Ｋ称　

为项目集的维数或长度．此频繁模式也称为频繁Ｋ一项目集。　

全局频繁模式集：集合中每个元素　相对于整个数据库　

来说都是频繁模式。　

局部频繁模式集：集合中每个元素　相对于某局部数据　

库来说都是频繁模式。　最大频繁模式：频繁模式，Ｙ的所有超集都是非频繁模式，　

则称　为最大频繁模式。　

性质１若　为频繁模型．则　的所有非空子集为频繁模　

型。　显然，任何频繁模型都是某最大频繁模型的子集，所以可　

以把发现所有频繁模型的问题转化为发现所有最大频繁模型　

的问题。　

２．２频繁模式树ＦＰｊｒｅｅ　

Ａｐｒｉｏｒｉ算法具体内容请读者查阅参考文献【２】。韩家炜等人　

提出的频繁模式集挖掘算法（ＦＰ—Ｇｒｏｗｔｈ）中，ＦＰ＿ｔｒｅｅ每个节点　

作者简介：林红飞，硕士研究生，主要研究方向数据挖掘、机器学习；庄卫华，副教授，主要研究领域为数据库应用。　

１６０　２Ｏ０６．

３２计算机工程与应用　维普资讯 http://www.cqvip.com 南４个域组成：节点名称ｎａｍｅ、节点计数ｃｏｕｎｔ、节点链ｎｅｘｔ、　

指向该节点的同名链ｌｉｎｋ及父节点指针ｐａｒｅｎｔ。另外，为方便　树的遍历，创建了一个频繁项目头表Ｈｔａｂｌｅ，它南两个域组成：　

项目名称ｎａｍｅ和项目链头ｈｅａｄ，其中项目链头指向ＦＰ＿ｔｒｅｅ　中与之名称相同的第ｌ节点。频繁模式树ＦＰ—ｔｒｅｅ的构造算法　

如下：　

（１）扫捕数据库ＤＢ一遍。得到频繁项目的集合Ｆ和每个　

频繁项目的支持度。把，按支持度递降排序，结果记为　。　

（２）创建ＦＰ—ｔｒｅｅ的根节点，记为丁，并且标记为’ｎｕｌｌ’，然　

后对ＤＢ中的每个交易Ｔｒａｎｓ做如下的步骤　

根据　中的顺序．选出并排序每个交易Ｔｒａｎｓ中的频繁项　

目。把Ｔｒａｎｓ中排好序的频繁项列表记为　｛　１　∈，ｌ，其中　

是Ｔｒａｎｓ的第　个元素，Ｐ是Ｔｒａｎｓ的元素有序列表。调用ｉｎ—　

ｓｅｒｔ—ｔｒｅｅ（Ｐ，Ｔ）。　函数ｉｎｓｅｒｔ＿ｔｒｅｅ（Ｐ，Ｔ）的运行如下：　

根据Ｐ沿着　的节点ｎｅｘｔ顺序地遍历　，在　元素时，如　

果　有一个子结点Ⅳ．其中Ｎ．ｎａｍｅ＝Ｐ￣．ｎａｍｅ．则将Ⅳ的ｃｏｕｎｔ　域值增加ｌ；否则，创建一个新节点Ⅳ，使它的ｃｏｕｎｔ为１．使它　

的父节点为７’，并且使它的ｌｉｎｋ和那些具有相同ｎａｍｅ域串起　

来。如果Ｐ余下的集合非空．记为ＮＰ．则递归调用ｉｎｅｓｒｔ＿ｔｒｅｅ　

（ＮＰ，Ｎ）。　性质２　ＣｈｉｌＮｏｄｅ为ＦＰ＿ｔｒｅｅ中的一节点．ＰａｒＮｏｄｅ为　

ＣｈｉｌＮｏｄｅ的祖先节点．则ＣｈｉｌＮｏｄｅ．ｃｏｕｎｔ＜￣ＰａｒＮｏｄｅ．ｃｏｕｎｔ　

３　ＴＦＰＤＭ算法　

３．１　ＴＦＰＤＭ算法设计　

３．１．１数据结构设计　

沿用ＦＰ—Ｇｒｏｗｔｈ数据结构的思想，ＴＦＰＳＭ算法采用的数据　结构南两部分组成：记录项目元素头表Ｈｔａｌｅ（图１）和ＮｅＷ　

ＦＰ＿ｔｒｅｅ树中节点ｎｏｄｅ的数据结构（图２），可以看出新的数据　

结构在原来ＦＰ—Ｇｒｏｗｔｈ的数据结构基础　增加了一些功能成　

员。需要说明的是之所以采用这样的数据结构　目的是全局和　

局部频繁模式集的挖掘在同一颗树七进行．只需要构造Ｎｅｗ　

ＦＰ＿ｔｒｅｅ树一次，不必分别构造两棵树，同时强调信息的复用　

性，有利于今后的再挖掘，提高挖掘的速度。　

下面对罔种参数的做一些说明：　

！ｍｅ【　＝：０ｕｎｌ＿　！！　

图ｌ　Ｈｔａｂｌｅ　

Ｎａｍｅ　Ｇｐａｓｓ—ｃｏｕｎｔ　Ｌｐａｓｓ—ｃｏｕｎｔ　Ｐａｒｅｎｔ　Ｎｅｘｔ　ｉ　Ｎｅｉｇｈｂｏｒ　Ｎａｍｅ：事务元素的名称，它是事务的基本组成单位．在　Ｈｔａｂｌｅ表中它以一定的顺序上下排列并且为关键字段　

Ｇ—ｃｏｕｎｔ：用于记录该事务元素在数据库中出现的总次数，　

在挖掘全局频繁模式集时，用它来判断该元素是否为全局频繁　

模式，如是该元素则参加求全局频繁集的运算。　

Ｌ　ｃｏｕｎｔ：用于记录该事务元素最近一段时间比如说最近　

一个月，在数据库中出现的总次数，在挖掘最近局部频繁模式　

集时，用它来判断该元素是否为局部频繁模式，如是则该元素　参加求最近一段时间的频繁模式集的运算。　

ＩｓＦｒｅｑｕｅｎｔ：是个布尔值，南阀值ｍｉｎ．ｓｕｐ、Ｇ—ｃｏｕｎｔ或　

Ｌ＿ｃｏｕｎｔ决定其值．ｙｅｓ表示该元素参加求数据库全局或局部　

频繁集的运算．反之．则不参加。　

Ｎｅｉｇｈｂｏｒ：一个指针．连接在树中与Ｎａｍｅ同名的领域元　素，最末端的Ｎｅｉｇｈｂｏｒ值为Ｎｕｌｌ。　

ＧＰａｓｓ＿ｃｏｕｎｔ：在构造Ｎｅｗ　ＦＰ＿ｔｒｅｅ时，用于记录该元素在　

某分枝上经过的总次数，挖掘全局频繁模式集用。　

ＬＰａｓｓ＿ｃｏｕｎｔ：用数据库中最近一段时间里的事务更新Ｎｅｗ　

ＦＰ—ｔｒｅｅ时，记录该事务元素在某分枝　经过的总次数。注意：　

在构造或更改Ｎｅｗ　ＦＰ＿ｔｒｅｅ时．ＧＰａｓｓ＿ｃｏｕｎｔ＋＋和ＬＰａｓｓ＿ｃｏｕｎｔ＋＋　是同时进行的。　

Ｐａｒｅｎｔ：用于该元素指向其在Ｎｅｗ　ＦＰ＿ｔｒｅｅ中的父节点。　

Ｎｅｘｔ：用于该元素指向其在Ｎｅｗ　ＦＰ－ｔｒｅｅ中的子节点　

３．１．２如何构造Ｎｅｗ　ＦＰ＿ｔｒｅｅ　

在ＴＦＰＤＭ算法中，事务元素的排序方法与ＦＰ—Ｇｒｏｗｔｈ采　

用的方法不同，它是预先对所有的事务元素按某一同定的次序　进行排序，而不必通过扫描数据库求出每个元素的支持度后，　

按照它们的支持数的大小进行排序　

给定事务数据库ＤＢ，，＝ｆ　．，　：，…，　｝是ＤＢ的ｍ个不同项　目元素有序的集合。Ｔ／ＥＤＢ．但遍历到　时。先对ｎ中的项目　

元素进行排序，然后调用Ｎｌｎｓｅｒｔ—Ｔｒｅｅ（　，　），这里的构造函数　

与第一部分介绍的Ｉｎｓｅｒｔ＿Ｔｒｅｅ（）运算过程大体相同，只不过多　

了对新添加的字段的赋值，　是树的根节点，开始为ＮＵＬＬ一　

算法的输入：事务集；有ｍ个排列表项的Ｈｔａｂｌｅ，Ｎａｍｅ字　

段不为空和Ｔ－－ＮＵＬＬ。算法的输出：Ｎｅｗ　ＦＰ＿ｔｒｅｅ　罔３是对具体　

的小型数据库用Ｎｌｎｓｅｒｔ—ｔｒｅｅ（）函数构造生成的ＦＰ　ｔｒｅｅ树，为　

简单起见．将Ｈｔａｂｌｅ表中的每个基本元素的Ｇ　ＣＯＵｎｔ和　

Ｌ　ｃｏｕｎｔ相等，将　中每个节点的ＧＰａｓｓ＿ｃｏｕｎｔ和ＬＰａｓｓ＿ｃｏｕｎｔ　相等，还有就是组成每个事务的基本元素已好序。　

３．１．３利用构造生成的Ｎｅｗ　ＦＰ＿ｔｒｅｅ树产生频繁项目集