FP-growth算法在高职院校贫困生认定工作中的应用研究

 [摘 要] 随着高职院校招生规模的不断扩大，经济困难的学生越来越多，贫困生的资助工作难度也不断加大，传统的贫困生认定工作方法越来越不能满足现实的需要，为了完善并做好目前的高职院校贫困生认定工作，我们运用FP-growth算法对所有收集到贫困生数据进行数据挖掘，发现隐藏在这些数据背后潜在的价值，找出一些数据之间内在的关联，给贫困生的认定工作提供一定的帮助，从而提高贫困生认定工作的效率。
关键词: 数据挖掘；关联规则；FP-growth算法
中图分类号: TP301 文献标识码:A

本文通过以数据表的形式建立贫困生认定的数据平台，采用量化的方法发掘出贫困生认定和学生日常生活中的哪些因素有关，让学校在以后贫困生认定过程中对这些因素加以重视，对理性的去认定贫困生，并做出相应的、合理的资助策略很有帮助。
1 数据挖掘及其过程
数据挖掘[1]就是指从海量的、不完整的、具有噪声的、模糊的和随机的数据中，提取隐藏在其中的、人们事先并不知道的、但又是值得可信的、潜在的和有价值的信息和知识的过程。数据挖掘一般要经过：数据的准备阶段、选择需要的数据阶段、对选取的数据进行预处理阶段、对预处理后数据进行挖掘阶段、最后进行模型的转换及模式的评价阶段。数据挖掘过程的多个步骤是相互关联的，并不是相互独立的。
2 关联规则挖掘算法
关联规则挖掘方法是一种最重要的也是最普遍的数据挖掘方法。
2.1 关联规则含义[2]
I={I1，I2，…，In}是一个项目的集合。DB是一个由任务之间有关联的数据构成的事务数据库集，而其中的每一个事务T是一个项目集，且有TI。各个事务T都与标识符TID有关联。令P为一个项目的集合，同时T也包含P，即PT。关联规则可以表示为MN，其中MI,NI,且有 M∩N=∅。关联规则MN是以支持度S、置信度C包含事务数据库DB。(S表示事务数据库DB中包含M或N的事务百分比；C表示事务数据库DB中包含M和N事务的百分比)。
2.2关联规则说明
1）关联规则的任务就是在给定的事物数据库中，发现数据与项目之间有价值、有用的联系，并产生的满足给定条件的关联规则。
2）为描述方便，关联规则中的最小支持度用Smin表示，最小置信度用Cmin表示。
3）关联规则的主要算法有Apriori算法以及改进型的Apriori算法，FP-growth算法等。
2.3 FP-growth算法
通过前期的研究分析得知[3,4,5]：Apriori算法数据挖掘时时间和空间效率都不是太高，而FP-growth算法只进行两次必要的数据库扫描，而且不使用候选项目集，直接压缩数据库成一个频繁模式树，最后通过这棵树生成相应的关联规则，搜索空间减少很多，而且还不产生大量候选集的问题。实验表明:FP-growth算法对不同长度的规则具有很好的适应性，效率上较高。
FP-growth算法是基于频繁模式树（FP-tree）这种数据结构的一种加快整个数据挖掘过程的关联规则挖掘算法。而FP-tree是将寻求全部的频繁项目集的过程分为两步[6]：
Step1： 如何构建一个FP-tree
1）首先整体扫描一次事务数据库DB。求出频繁项的集合以及相应的支持度，接着按照支持度的降序排列，形成一个最初的频繁项表L。
2）创建FP-tree的根结点，同时将其标记为null。接着对DB中的各个事务T，都进行如下处理：选取T中的频繁项集，并以L中的降序排列为依据,设经过降序排列处理后的频繁项表为[q|Q],其中q是首个项目表，Q是除了首个项目表以外的其他项目表；若[q|Q]不为空，就调用函数insert_tree([q|Q],T)。
insert_tree([q|Q],T)的执行如下[7]：
若T中有子女结点N可以使得N.item_name=q.item_name，则N计数并加1；否则创建一个新结点N，将从1开始计数，链接到N的父结点T上，同时通过结点链将其链接到具有相同item_name的结点。若Q非空，则递归调用insert_tree(Q,T)。
Step2： 利用FP-tree挖掘出全部的频繁项目集
FP-tree通过调用FP_growth(FP-tree,null)算法来挖掘频繁项目集。实现过程如下[4]：
3 FP-growth算法在贫困生认定中的应用研究
3.1数据准备
为了做好前期的准备工作，首先，我们对所有上交到学校贫困生认定部门的申请困难资助的学生的数据进行合理处理，获得与贫困生认定有关的数据表如下：
学生简明登记表（学号，姓名，性别，年龄，民族，所在系部，所学专业，所在班级，原籍，特长，单亲或孤残，家庭总人口，健康状况，家庭现住址）；
成绩总表（学号，姓名，所在系部，所在班级，课程名，成绩）
贫困生认定申请表（学号，姓名，所在系部，所学专业，所在班级，家庭年收入，申请理由）；
家庭成员登记表（姓名，性别，年龄，与学生关系，健康状况，职业，工作单位）；
食堂卡月消费表（卡号、学号，姓名，性别，年龄，月消费金额）；
助学贷款登记表（学号、姓名、年龄，所在系部、所学专业、所在班级、贷款金额(元)、贷款期限(月)、贷款利率)。
由于这些表由不同的部门提供，因此他们提供的这些表的在形式上就不统一，存在着差异，于是我们利用数据转换工具，把这些形式上不统一的表都转换成我们需要的形式上统一的数据表。
接着我们利用数据转换后的各表数据作为源数据，进行必要的格式化处理，再选取需要的字段后，去除不必要的字段，得到学生基本信息表如下表1所示：
表1 学生基本信息表
学号
是否申请贫困 是否补考 原户口 家庭总人口 食堂月消费金额 贷款总额 上学总人数 危重病人 单亲或孤残 父母职业
1131302 是 否 农村 5 260 3000 3 无 否 务农
1131313 是 否 农村 4 300 无 2 无 否 务农
1131327 是 否 城镇 3 250 0 1 无 是 失业
…… … … … … … …… …… … …… ……
3.2数据预处理
上面信息表中的数据都是连续型数值数据，而关联规则算法是无法直接处理这些数据的，所以我们必须先要把这些连续数据进行离散化[8,9,10]，离散后的形式如下表2所示：
表2
属性 值域
是否申请贫困 {是，否}
是否补考 {是，否}
原户口 {城镇，农村}
家庭总人口 {1-3，4-7，>7}
食堂月消费金额 {<250,250-350,>350}
贷款总额 {0,<4000,4000-6000，>6000}
上学总人数 {1,2，>2}
危重病人 {有，无}
单亲或孤残 {是，否}
父母职业 {稳定收入，务农或失业}
接着把表2的值域部分设定成如下项目代码形式如下表3所示：
表3
属性 项目代码
是否申请贫困 {1，2}
是否补考 {3，4}
原户口 {5，6}
家庭总人口 {7，8，9}
食堂月消费金额 {10,11,12}
贷款总额 {13，14，15，16}
上学总人数 {17,18，19}
危重病人 {20，21}
单亲或孤残 {22，23}
父母职业 {24，25}
最后对事务数据集进行形式上的转换，得到如下表4：
表4
TID ITEM
1131302 1，4，6，8，11，14，19，21，23，25
1131313 1，4，6，8，11，13，18，21，23，25
1131327 1，4，5，7，11，13，17，21，22，25
…… ……
3.3 数据挖掘结果及成因分析
3.3.1 挖掘结果
本次挖掘根据当前的实际情况预设Smin=4%, Cmin=45%。使用FP-growth算法对上述经过一系列处理的数据进行充分挖掘后,去掉小于最小置信度C的记录，部分关联规则结果如表5所示（补考的同学不予考虑）：
表5
规则号 关联规则 支持度 置信度
规则1 食堂月消费金额<=300,农村户口，父母务农，上学人数=2 =>一般困难 20.25% 75.75%
规则2 食堂月消费金额<=300,城镇户口，父母失业 =>一般困难 6.25% 75.45%
规则3 食堂月消费金额<=300,农村户口，父母务农，上学人数=2，申请助学贷款>3000 =>一般困难 4.75% 98.26%
…… …… …… ……
3.3.2 规则含义及成因分析
1．规则含义
规则1：食堂月消费金额<=300,农村户口，父母务农，上学人数=2 =>一般困难（置信度=75.75%），这条规则所表达的含义是一个来自农村学生在食堂的月消费金额不高于300元的、父母没有固定工作，同时还有兄弟姐妹上学的申请一般困难的置信度是75.75%，比较可信；
规则2：食堂月消费金额<=300,城镇户口，父母失业 =>一般困难（置信度=75.45%），这条规则所表达的含义是一个来自城镇的学生在父母双失业，即父母失去工作的情形下，在食堂的月消费金额不高于300元的同学申请一般困难的置信度为75.45%，也是比较可信的；
规则3：月消费金额<300,农村户口，上学人数=2，申请了助学贷款 =>一般困难（置信度=98.26%），这条规则所表达的含义是来自农村的学生有兄弟姐妹在上学、在食堂的月消费在300元以下，同时申请的助学贷款超过3000元的农村同学，申请一般困难时的置信度为98.26%，非常可信。
除了这几条关联规则外，还有许多其他的关联规则，不再一一列举。
2．成因分析
对学校实际贫困生资助系统资源库中的贫困生信息进行统计，共有贫困生2217 人，而使用FP-growth算法挖掘后产生的贫困生人数为1925人，两者之间存在一定的差距，这说明使用FP-growth算法的数据挖掘效率并不是100%。这是由于（1）关联规则并不是直接的因果关系，数据之间并不本质必然的联系，只是反映了一个客观现象而已；（2）收集到数据比较有限，并不全面和可靠；（3）数据收集过程中学生的实际情况比较复杂，如有些同学家庭状况确实不好但平时生活仍然很奢侈而未能成为贫困生；（4）挖掘工具的使用也会对数据挖掘结果造成一定的影响等等。
4 结束语
通过以上分析，得知使用FP-growth算法进行数据挖掘，找出了数据间的关联规则，能够在某种程度上反映了贫困生的认定与学生学习成绩、贷款、消费水平以及家庭情况等之间存在的关系规律，对贫困生的认定有很大的参考价值和指导意义，其实除了关联规则这种常用的挖掘技术以外，还有许多其他的先进的挖掘技术和方法，针对具体的问题，怎样选择一个更高效率的数据挖掘技术和方法是将来研究需要解决的问题。
参考文献：
[1]纪希禹.数据挖掘技术应用实例[M].北京:机械工业出版社,2009．
[2]曹路舟.关联规则算法在高职院校贫困生认定工作中的应用[D].合肥：安徽大学，2011
[3]Jiawei Han,Micheline Kamber著,范明，孟小峰等译.数据挖掘概念与技术[M].北京：机械工业出版社,2001.
[4]李雄飞，董元方，李军．数据挖掘与知识发现（第2版）[M]．北京：高等教育出版社，2010. [5]Jiawei Han,Micheline Kamber,Data Mining Concepts and Techniques[M].北京:高等教育出版社,2001.
[6]李金娟，王卫锋.基于FP-growth算法在学生成绩中的关联规则分析[J].巢湖：巢湖学院学报，2007:30-33.
[7]石云平.FP-growth关联算法研究[J].合肥：计算机与信息技术，2008: 11-12.
[8]王新宇，杜孝平等.FP-growth算法的实现方法研究[J].北京：计算机工程与应用，2004:174-176.
[9]王远敏.图象数据库关联规则的挖掘方法研究[J].天津：数字技术与应用，2012:81-82.
[10]周琪锋，张立臣.数据挖掘在实验系统的应用[J].北京：科技资讯，2007:101-102.