使用fp树挖掘闭频繁项集方法探究

《使用fp树挖掘闭频繁项集方法探究》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、使用FP树挖掘闭频繁项集方法探究　　摘要：数据挖掘可以在现有的大量数据中提取有用的信息和知识。数据挖掘包括很多知识提取、模式分析的方法，其中挖掘频繁模式对于分析数据之间的关联和其他联系起着重要作用。本文研究讨论了在已有的FP增长策略的基础上增加剪枝的步骤，来挖掘存在的闭频繁模式，从而减少可能产生的大量频繁项集，使得挖掘出的闭频繁模式更加有针对性和有效性。关键词：频繁模式FP增长策略闭频繁项集剪枝中图分类号：TP31文献标识码：A文章编号：1007-9416（2013）10-0108-011引言4随着信息产业的发展，存在着可以

2、广泛使用的大量数据，将这些数据转换成有用的信息和知识成了迫切需要解决的关键问题。在数据挖掘中存在很多提取、模式分析的方法，包括概念/描述、挖掘频繁模式、关联和相关、分类和预测、聚类分析、离群点分析及演变分析等。其中频繁模式对于挖掘数据之间的关联、相关和许多其他有趣的联系起着至关重要的作用；此外，对数据分类、聚类和其他数据挖掘任务也有帮助。因此，频繁模式的挖掘就成了一项重要的研究课题之一。本文研究了使用FP树挖掘闭频繁项集的方法，使得挖掘的频繁模式更加有针对性。2FP增长策略基本原理FP增长策略即频繁模式增长，是一种可以挖掘出

3、全部频繁项集而不产生大量侯选的方法，它采取如下分治策略：首先将提供频繁项的数据库压缩到一棵频繁模式树，但仍保留项集关联信息；然后，将压缩后的数据库划分成一组条件数据库，每个关联一个频繁项或“模式段”，并分别挖掘每个条件数据库。当数据库很大时，可将数据库划分成投影数据库的集合，然后在每个投影数据库构造FP树并挖掘[1]。3挖掘闭频繁项集的意义设有数据集S，项集I，项集X，项集Y，则频繁项集指的是当项集I的相对支持度满足预定义的最小支持度阈值时，称I为频繁项集。如果不存在真超项集Y使得Y与X在S中有相同的支持度计数，则称项集X在

4、数据集S是闭的。如果项集X在数据集S中是闭的和频繁的，则称项集X是数据集S中的闭频繁项集[2]。频繁项集挖掘可能产生大量频繁项集，特别是当最小支持度阈值min_sup设置较低或数据集中存在长模式时尤其如此。而闭频繁项集可以显著减少频繁项集挖掘所产生的模式数量而保持关于频繁项集的集合。4挖掘闭频繁项集方法研究4在使用FP树挖掘频繁项集的过程中搜索闭频繁项集，一旦识别闭项集就尽快对探索空间进行剪枝，剪枝的策略是：如果包含频繁项集X的每个事务都包含项集Y，但不包含Y的任何真超集，则X∪Y形成一个闭频繁项集，并且不必再搜索包含X，但

5、不包含Y的任何项集[2]。本文以下面例子演示具体实现方法。设有事务数据如表1。首先对数据库进行第一次扫描，导出频繁1项集的集合和支持度计数。设最小支持度计数为2，结果集记作L，则有L={{I2：7}，{I1：6}，{I3：6}，{I4：2}，{I5：2}}。然后，构造FP树。创建树的根节点，第二次扫描数据库，每个事务中的项按L中的次序处理并对每个事务创建一个分支。当为一个事务考虑增加分枝时，沿共同前缀上的每个节点的计数增加1。得到FP树如图1：4第三，挖掘频繁模式，识别闭项集进行剪枝，从而得到闭频繁项集。由每个长度为1的频繁

6、模式开始，构造它的条件模式基，然后构造它的FP树，并递归地对该树进行挖掘。首先考虑I5，I5出现在图1FP树的两个分支，形成的路径是〈I2，I1，I5：1〉和〈I2，，I1，I3，I5：1〉。，因此，它的两个对应前缀路径是〈I2，I1：1〉和〈I2，，I1，I3：1〉形成I5的条件模式基。该单个路径产生的所有频繁模式有：{I2，I5：2}，{I1，I5：2}，{I2，I1，I5：2}。在此进行剪枝，前缀项集{I5：2}的投影条件数据库是{{I2，I1}，{I2，I1，I3}}，它的每个事务都包含项集{I2，I1}，但不包含{

7、I2，I1}的真超集。项集{I2，I1}可以与{I5}合并，形成闭项集{I5，I2，I1：2}；并且不必挖掘包含I5但不包含{I2，I1}的闭项集。整个过程得到如表2结果。5结语频繁模式的挖掘在数据库挖掘中应用非常广泛，但当最小支持度阈值设置较低或数据集中存在长模式时可能产生大量频繁项集，因此本文研究的有针对性地只挖掘闭频繁项集具有实用意义。参考文献[1]汉德，张银奎（译）.数据挖掘原理[M].北京：机械工业出版社，2003.[2]JiaweiHan，MichelineKamber，范明，孟小峰（译）.数据挖掘概念与技术[M

8、].北京：机械工业出版社，2007.4