FP-Growth关联算法应用研究+20137212913189.docVIP

FP-Growth关联算法应用研究 1 引言 关联规则(Association Rules)挖掘是数据挖掘研究领域的一个重要研究方向，它由美国IBM Almaden Research Center 的Rakesh A-Grawal等人于1993年首先提出，是描述数据库中数据项之间存在的一些潜在关系的规则。 2 关联分析概念 设I = {I1，I2，…，Im}是项的集合，D = {T1，T2，…，Tn}是一个事务数据库，其中每个事务T是项的集合，使得TI。每个事务有一个标识符，称为TID。如果I的一个子集X满足XT，则称事务T包含项目集X。一个关联规则就是形如X=Y的蕴涵式，XI、YI、X∩Y= 。 规则X Y在交易数据库中的支持度(support)就是交易集中包含X和Y的交易数与所有交易数之比，记为support (X Y)，即support(X Y)=┃{T：X∪Y T，T D}┃/┃D┃。 规则X=Y在交易数据库中的置信度(confidence)是指包含X和Y的交易数与包含X的交易数之比，记为confidence(X=Y)，即confidence(X=Y)= ┃{T：X∪Y T，T∈D}┃/┃{T：X T， T ∈D }┃。 支持度和置信度是描述关联规则的两个重要概念，前者用于衡量关联规则在整个数据集中的统计重要性，后者用于衡量关联规则的可信程度。一般来说，只有支持率和置信度均较高的关联规则才可能是用户感兴趣、有用的关联规则。 关联规则的挖掘是一个两步的过程： (1)找出所有的频繁项集：根据定义，这些项集出现的频繁性至少等于预定义的最小支持度计数。 (2)由频繁项集产生强关联规则：根据定义，这些规则必须满足最小支持度和最小置信度。 在以上两个步骤中，第二步较容易，挖掘关联规则的总体性能由第一步决定。 3 FP-Growth关联算法分析 针对经典关联Apriori算法的固有缺陷，产生了候选挖掘频繁项集的方法—FP-Growth算法。FP-Growth算法采用分而治之的策略，在经过第一遍扫描之后，把数据库中的频繁项集压缩到一棵频繁模式树(FP-Tree)，同时依然保留其中的关联信息，随后再将FP-Tree分化成一些条件数据库，每个条件数据关联一个频繁项，然后再分别对这些条件库进行挖掘。FP-Growth算法将发现长频繁模式的问题转换为递归地发现一些短模式，然后连接后缀。它使用最不频繁的项作为后缀，提供了好的选择性。FP-Growth算法核心思想如下所示： 输入：事务数据库D；最小支持度阈值min_sup。 输出：频繁模式的完全集。 方法： (1)构造FP-Tree。 ①扫描事务数据库D一次。收集频繁项的集合F和它们的支持度。对F按支持度降序排序，结果为频繁项表L。 ②创建FP-Tree的根节点，以“NULL”标记它。对于D中每个事务Trans，执行：选择Trans的频繁项，并按照L中的次序排序。设排序后的频繁项表为[p|P]，其中p是第一个元素，而P是剩余元素的表。调用insert_tree([p|P]，T)。该过程执行过程如下：如果T有子女N使得N.item-name= p.item-name，则N的计数增加1，否则创建一个新节点N，将其计数设置为1，链接到它的父节点T，并且通过节点链结构将其链接到具有相同item-name的节点。如果P非空，递归地调用insert_tree(P，N)。 (2)通过调用FP-Growth(FP-Tree，null)实现FP-Tree的挖掘。该过程实现如下： Procedure FP-Growth(Tree，α) ①if Tree 含单个路径P then ②for 路径P中节点的每个组合(记作β) ③产生模式β∪α，其支持度support = β中节点的最小支持度； ④else for each αi在Tree的头部{ ⑤产生一个模式β = αi∪α，其支持度support =αi.　support； ⑥构造β的条件模式基，然后构造β的条件FP-Treeβ； ⑦if Treeβ≠ then ⑧调用FP-Growth(Treeβ，β)；} 对FP-Tree方法的性能研究表明：对于挖掘长和短的频繁模式，它都是有效和可伸缩的，并且比Apriori方法快了1个数量级。 4 应用实现 本文主要是将FP-Growth算法应用到我校学生成绩数据库中，在学生成绩聚类的基础上对学生成绩的聚类簇与学生的内外部因素进行关联分析。 4.1 关联分析目标 目前我校面对的教务处学