FP—Growth关联规则挖掘的改进算法.pdfVIP

第l7卷第1期 平顶山工 学院学报 V01．17 No．1 2008年1月 Journal of PiIl8diIl{ 8Il~ tute 0fTeetmology Jan． 文章编号：1671—9662(2008)01—0021—04 FP—Growth关联规则挖掘的改进算法 张 星，李 蓓 (平顶山工学院计算机科学与工程系，河南平顶山467044) 摘 要： 文章通过对FP—Growth算法分析，提出的改进算法能有效地减少需遍历的树的节点数，从而 降低了时问开销。实验表明：改进算法能明显地提高挖掘效率。 关键词： 关联规则；FP—Growth算法；FP—Tree；数据挖掘 中图分类号：TP301 文献标识码：A 1 关联规则概述 关联规则 (Association Rules)挖掘是数据挖掘研究领域的一个重要研究方向，它由美国IBM灿叮出 I Reseaw．h Center 的Rakesh A—grawal等人于1993年首先提出，是描述数据库中数据项之间存在的一些潜在关系的规则。 设，={I1，，2…．，，m}是项的集合，D={ ， …．， }是一个事务数据库，其中每个事务 是项的结合，使得 c，。每个事务有一个标识符，称为T／D。如果，fI勺一个子集 满足 c T，则称事务 包含项目集 。一个关联规则就是 形如精 Y的蕴涵式， c，、y c，、 n Y= 。 规则 Y在交易数据库中的支持度(Support)就是交易集中包含 和y的交易数与所有交易数之比，记为support ( y)，即support( y)=I{ ： U Y c T，T∈D}I／I D I。 规则精 Y在交易数据库中的置信度(Confidence)是指包含 和 y的交易数与包含 的交易数之比，记为 confidence(Xjy)，即confidence( jy)=I{ ：X U y c T，T∈D}I／I{T：X c T，T∈D}I。 支持度和置信度是描述关联规则的两个重要概念，前者用于衡量关联规则在整个数据集中的统计重要性，后者用 于衡量关联规则的可信程度。一般来说，只有支持率和置信度均较高的关联规则才可能是用户感兴趣、有用的关联规则。 同时满足最小支持度阈值(min sup)和最小置信度阈值(win—conf)的规则称为强规则。关联规则挖掘的任务就是要挖 掘出事务数据库D中所有的强规则。 关联规则的挖掘是一个两步的过程： (1)找出所有的频繁项集：根据定义，这些项集出现的频繁性至少等于预定义的最小支持度计数。 (2)由频繁项集产生强关联规则：根据定义，这些规则必须满足最小支持度和最小置信度。 在以上两个步骤中，第二步较容易。挖掘关联规则的总体性能由第一步决定。项 表1 事务数据集 的集合称为项集，包含 个项的项集称为J}一项集。 ⅡD Items 2 FP—Growth算法 001 A，C，D，F，G，L，M，P FP—Growth(Frequent—Pattern Growth)算法是由Jianwei Han等人提出的，是一种不 002 A，B，C，F，L，M，0，P 产生候选项集而采用模式增长的方式挖掘频繁模式的算法。它采用如下分治策略： 003 B，F，L，H，0 将提供频繁项集的数据库压缩到一颗频繁模式树，但仍保留项集关联信息，然后将这 004 B，C，K，S，N 种压缩后的数据库分成一组条件数据库，每个关联一个频繁项，并分别挖掘每个数据 005 A，F，C，E，L，P，M，N 库。对表1事务数据集： 006 A，B，C，F，M，P 采用FP—Growth算法挖掘如下：