FPGrowth关联算法
前言：本站为你精心整理了FPGrowth关联算法范文，希望能为你的创作提供参考价值，我们的客服老师可以帮助你提供个性化的参考范文，欢迎咨询。
摘要关联规则挖掘用于从大量数据中揭示项集之间的有趣关联或相关联系，是数据挖掘的一项重要研究内容。本文首先对FP-Growth算法进行分析，然后运用该算法分析聚类结果中的学生簇与该簇学生所具有因素的关联关系，实践证明了该算法具有较强的实用性。
关键词数据挖掘；关联分析；频繁模式；FP-Tree
1引言
关联规则(AssociationRules)挖掘是数据挖掘研究领域的一个重要研究方向，它由美国IBMAlmadenResearchCenter的RakeshA-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=。
规则XY在交易数据库中的支持度(support)就是交易集中包含X和Y的交易数与所有交易数之比，记为support(XY)，即support(XY)=┃{T：X∪YT，TD}┃/┃D┃。
规则X=Y在交易数据库中的置信度(confidence)是指包含X和Y的交易数与包含X的交易数之比，记为confidence(X=Y)，即confidence(X=Y)=┃{T：X∪YT，T∈D}┃/┃{T：XT，T∈D}┃。
支持度和置信度是描述关联规则的两个重要概念，前者用于衡量关联规则在整个数据集中的统计重要性，后者用于衡量关联规则的可信程度。一般来说，只有支持率和置信度均较高的关联规则才可能是用户感兴趣、有用的关联规则。
关联规则的挖掘是一个两步的过程：
(1)找出所有的频繁项集：根据定义，这些项集出现的频繁性至少等于预定义的最小支持度计数。
(2)由频繁项集产生强关联规则：根据定义，这些规则必须满足最小支持度和最小置信度。
在以上两个步骤中，第二步较容易，挖掘关联规则的总体性能由第一步决定。
3FP-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的挖掘。该过程实现如下：
ProcedureFP-Growth(Tree，α)
①ifTree含单个路径Pthen
②for路径P中节点的每个组合(记作β)
③产生模式β∪α，其支持度support=β中节点的最小支持度；
④elseforeachαi在Tree的头部{
⑤产生一个模式β=αi∪α，其支持度support=αi.support；
⑥构造β的条件模式基，然后构造β的条件FP-Treeβ；
⑦ifTreeβ≠then
⑧调用FP-Growth(Treeβ，β)；}
对FP-Tree方法的性能研究表明：对于挖掘长和短的频繁模式，它都是有效和可伸缩的，并且比Apriori方法快了1个数量级。
4应用实现
本文主要是将FP-Growth算法应用到我校学生成绩数据库中，在学生成绩聚类的基础上对学生成绩的聚类簇与学生的内外部因素进行关联分析。
4.1关联分析目标
目前我校面对的教务处学生成绩数据库是一个多维的关系数据库，我们急切需要从这些海量数据中发现潜在的有用信息来帮助教学部门掌握更多的学生信息。基于此，根据学生的成绩信息对学生聚类，这些聚类信息反映了学生学习成绩的升降起伏等学习情况，结合学生的聚类信息与学生因素调查表信息，采用关联挖掘技术分析每一类学生的学生成绩与其内外部因素间的关联信息，进而分析得到影响学生学习的因素。4.2算法实现
定义频繁节点结构，用以构造频繁一次项的降序排列
typedefstructItemCode//SortItem
{
intCount；//频繁度
intPosition；//排序位置
ItemCode*Next；//下一个节点的地址
CStringData；//节点值
}ItemCode；
ItemCode*GetItem(CStringTableName，intSupport，intNumber，intCluNum)；//由数据库得到未排序频繁一项集节点链，并返回首节点；
voidGetSortItem(ItemCode*pHeadItem)；//对频繁一项集排序；
voidCreateFPTree(CStringTableName，CTreeCtrl&TempTree，CTreeCtrl&TreeCopy，boolSort，intNumber，intCluNum)；//按照频繁项排序建立FP-Tree；
voidGetFPItem(CTreeCtrl&TempTree，CListBox&LBox，intSupport，intNumber，intCluNum)；//按Support的支持度对TempTree的FP-Tree进行关联分析，得到频繁项显示在LBox；
voidSaveResultToDB()；//保存频繁项集结果到数据库；
voidComputeAssociate(intNumber，intCluNum)；//计算关联结果的相关分析值；
voidShowInChart(CActiveFrmChart&Chart，intNumber，intCluNum，intIndex)；//将挖掘结果显示在Chart中；
4.3挖掘结果
为了深入了解学生所处的内外部因素对学生成绩的影响，将分别对每个簇的学生所处的内外部因素进行关联挖掘，以获取每个簇学生所处内外部因素间的关联关系，分别对每个簇学生的内外部因素采用FP-Growth改进算法进行关联挖掘，因为支持度计数是与问题域相关的，用户可选择不同的支持度计数实验，我们在这里支持度计数选取为5。
部分簇构造FP-Tree如图1所示，因篇幅有限，只列举有代表意义的关联项。
图1生成的FP-Tree(灰色是频繁项)
5结束语
对该算法的研究和应用可以看出算法具有很强的实用性。本文对关联挖掘中支持度、置信度的选择没有进行深入的研究，因为对于一组给定的样本，由于缺乏经验或具体的问题域不同等其它原因导致事先不能合理地对聚类数目K、支持度、置信度的取值，这是一个比较棘手的问题，目前关于这方面研究的资料文献较少，因此将此问题作为下一步研究的方向具有重要的现实意义。
参考文献
[1][加]JiaweiHanMichelineKamber，范明，孟小峰等译.数据挖掘概念与技术[M].北京：机械工业出版社，2001.
[2]颜跃进，李舟军，陈火旺.基于FP-Tree有效挖掘最大频繁项集[J].软件学报，2005，16(2)：215-222.
[3]易彤，徐宝文，吴方君.一种基于FP树的挖掘关联规则的增量更新算法[J]计算机学报2004.5
[4]胡向前，基于FP-Tree的多层关联规则挖掘算法研究[D]重庆大学硕士学位论文2005.5
