收 稿日期 : 2008-05-04; 修 回日期 : 2008-07-24 基 金项 目: 国 家自 然 科学 基 金资 助 项目 ( 60673131, 60873019) ; 黑龙 江 省自 然 科 学基 金
资助项 目( F200608) ; 黑 龙江省 教育厅 海外 学人重 点科 研基金 资助 项目( 1152hq08)
作 者简介 : 谢志强 ( 1962-) , 男, 湖南新 邵人 , 教授 , 博士, 主要 研究 方向为 CIMS、数据 挖掘 ( xzq0111@ tom. com) ; 朱孟 杰( 1981- ) , 男 , 硕 士研 究
生, 主 要研 究方向 为数据 挖掘 ; 杨 静( 1962- ) , 女 , 教 授, 博导 , 博 士, 主要研 究方 向为数 据库 、数 据挖掘 .
基 于 改 进 FP-树 的 最 大 项 目 集 挖 掘 算 法
*
谢志强
1
, 朱孟杰
1
, 杨 静
2
( 1. 哈尔 滨理 工大 学 计 算 机 科 学 与 技术 学 院 , 哈 尔 滨 150080; 2. 哈 尔 滨 工 程 大 学 计 算 机 科 学 与 技 术 学 院 ,
哈尔 滨 150001)
摘 要: 挖掘 最 大频 繁项 目 集是 多种 数 据挖 掘 应用 中的 关 键问 题。 FP-growth 算 法是 目前 最 有效 的频 繁 模式 挖
掘算 法之 一, 其在 挖掘 最大 项目 集时要 递归 生成 大量 的条 件 FP-树, 存在 时空 效率 不高 的问 题。于 是结 合改 进的
FP-树, 提出 了一 种快 速挖 掘最 大项 目集的 算法 。该 算法 利用 改进 的 FP-树是单 向的 且每 个节 点只 保留 指向 父 节
点的 指针 , 可以节 约大 量的 存储 空间; 同 时引 入项目 序列 集和 它的 基本 操作 , 使挖掘 最大 频繁 项目 集 时 不生 成 含
大量 候选 项目 的集合 或条 件 FP-树, 可以 快速 地挖 掘出 所 有的 最 大 频繁 项 目 集。实 例 分 析证 明 所 提出 的 算 法 是
可行 的。
关键 词: 数 据挖 掘; 关联 规则 ; 最大 频繁 项目 集; 频繁模 式树
中图 分类 号: TP311 文 献标 志码: A 文 章编 号: 1001-3695( 2009) 02-0502-04
Maximumfrequent itemsets mining algorithm based on improved FP-tree
XIE Zhi-qiang
1
, ZHU Meng-jie
1
, YANG Jing
2
( 1. School of Computer Science & Technology, Harbin University of Science & Technology, Harbin 150080, China; 2. School of Computer
Science & Technology, Harbin Engineering University, Harbin 150001, China)
Abstract: Miningmaximumfrequentitemsetsis a keyproblemin manydata mining application. FP-growth algorithm is one of
the most efficientfrequentpattern mining methods. However, FP-growth algorithmmust generate ahuge number of conditional
FP-trees recursively in processes of miningmaximumfrequent, so the efficiency of it unsatisfactory. This paper proposed an ef-
ficient mining maximum frequent algorithm, itunified the improvement FP-tree. The FP-tree was a one-waytree and there is no
pointers to pointits children in each node, so it saved the massive memories space. Byintroducing set of itemsequences and its
operators, the algorithm didn’t generate conditional FP-tree or a large number of candidate sets in mining process, which
could conveniently get all maximum frequent itemsets. The example analysis shows the algorithm is feasibility and effective-
ness.
Key words: data mining; association rule; maximum frequent itemsets; FP-tree
0 引言
关联规则挖掘是数据挖掘中最活跃的研究方法之一, 最早
是由 Agrawal 等人
[ 1]
提出的, 它用于描述 事务数据库 中各交 易
项目之间的关系, 即频繁关系。关联规则挖掘问题可以划分成
两个子问题, 即发现频繁项目集和生成关联规则。发现频繁项
目集是关联规则挖掘和数列模 式等数 据挖掘 应用中 的关键 技
术和步骤, 因此许多研究都集中在频繁模式挖掘上。Apriori 算
法
[ 2]
是关联规则挖 掘的 一个 经典 算 法, 在数 据 挖掘 中具 有 里
程碑 的作用, 许 多早期 的研究 大多采 用类似 于 Apriori 的先 产
生候选集后进行测试的方法。但是随着研究的深入, 它的缺点
也暴露 出来, 即 需要多次扫 描数据库, 并且需 要很大的 I/O 负
载, 可能产生庞大的候选集。
Han 等人
[ 3]
提出了 一种利用频 繁模式树 ( FP-tree) 进 行频
繁模式挖掘的 FP-growth 算法。该算法 采用 FP-树存 放数据 库
的主要信息, 算法只 需要扫 描数 据库 两次, 使 关 键信 息以 FP-
树的形式存放在内存中, 避免了因多次扫描数据库而带来的大
量的 I/O 负载; 它不需要产 生候选集, 从而减少 了产生和测 试
候选集需要耗费的大量时间, 并且 采用分 而治之 的思想, 在 挖
掘过程中大大缩小了搜索空间。实验表明 FP-growth 算法的 性
能比 Apriori 算法快了一个数量级。虽然频繁模式算法 对于一
些非稠密数据库能够取得很好的性能, 但对于稠密数据库或者
支持度较小时, 频繁模式的 数量会 以指数 形式增 长, 使得找 出
所有的频繁模式成为不可 能的任 务。为了减 少频繁 模式中 的
冗余, 人们采用了各种方法, 其 中最主 要的有 挖掘频 繁闭项 目
集
[ 4]
( frequent closed itemset, FCI) 和 最 大 频繁 项 目 集 ( MFI) 。
其中 MFI 的规模最小, 而 且通 过最 大频 繁项 目 集可 以导 出 频
繁闭项目集和频繁项目集, 所以可以把发现频繁项目集的问题
转换为发现最大频繁项目 集的问 题。另外某 些数据 挖掘的 应
用中仅需发现最大频繁项目 集, 而 不必发 现频繁 项目集, 因 而
发现最大频繁项目集对数据挖掘具有重大的意义。
目前可用的 最大 频繁 项 目挖 掘算 法 有 Max-Miner
[ 5]
、Pin-
cer-Search
[ 6]
、DMFI
[ 7]
、DMFIA
[ 8]
及 IDMFIA
[ 9]
等 算 法。Max-
Miner采用了广度优先的搜 索方法, 另 外还采 用了超 集剪枝 策
第 26 卷第 2 期
2009 年 2 月
计 算 机 应 用 研 究
Application Research of Computers
Vol. 26 No. 2
Feb. 2009