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

曹路舟

(池州职业技术学院信息技术系，安徽池州247000)

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

曹路舟

(池州职业技术学院信息技术系，安徽池州247000)

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

数据挖掘;关联规则;FP－growth算法

1 数据挖掘及其过程

数据挖掘［1］就是指从海量的、不完整的、具有噪声的、模糊的和随机的数据中，提取隐藏在其中的、人们事先并不知道的、但又是值得可信的、潜在的和有价值的信息和知识的过程.数据挖掘一般要经过:数据的准备阶段、选择需要的数据阶段、对选取的数据进行预处理阶段、对预处理后数据进行挖掘阶段、最后进行模型的转换及模式的评价阶段.数据挖掘过程的多个步骤是相互关联的，并不是相互独立的.数据挖掘的过程如图1所示.

图1 数据挖掘过程

2 关联规则挖掘算法

关联规则挖掘方法是一种最重要的也是最普遍的数据挖掘方法.

2.1 关联规则含义［2］

I={I1，I2，…，In}是一个项目的集合.DB是一个由任务之间有关联的数据构成的事务数据库集，而其中的每一个事务T是一个项目集，且有T⊆I.各个事务T都与标识符TID有关联.令P为一个项目的集合，同时T也包含P，即P⊆T.关联规则可以表示为M⇒N，其中M⊆I，N⊆I，且有M∩N=Ø.关联规则M⇒N是以支持度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－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 学生基本信息表

3.2 数据预处理

上面信息表中的数据都是连续型数值数据，而关联规则算法是无法直接处理这些数据的，所以我们必须先要把这些连续数据进行离散化［8－10］，离散后的形式如表2所示:

表2 离散化后的学生基本信息表

接着把表2的值域部分设定成如下项目代码形式如表3所示:

表3 项目代码形式的学生基本信息表

最后对事务数据集进行形式上的转换，如表4所示:

表4 形式上转换后的事务数据集

3.3 数据挖掘结果及成因分析

3.3.1 挖掘结果

本次挖掘根据当前的实际情况预设Smin=4%，Cmin=45%.使用FP－growth算法对上述经过一系列处理的数据进行充分挖掘后，去掉小于最小置信度C的记录，部分关联规则结果如表5所示(补考的同学不予考虑):

表5 部分关联规则结果

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元以下，同时申请的助学贷款超过3 000元的农村同学，申请一般困难时的置信度为98.26%，非常可信.

除了这几条关联规则外，还有许多其他的关联规则，不再一一列举.

(2)成因分析

对学校实际贫困生资助系统资源库中的贫困生信息进行统计，共有贫困生2 217人，而使用FP－growth算法挖掘后产生的贫困生人数为1 925人，两者之间存在一定的差距，这说明使用FP－growth算法的数据挖掘效率并不是100%.这是由于:①关联规则并不是直接的因果关系，数据之间并不本质必然的联系，只是反映了一个客观现象而已;②收集到数据比较有限，并不全面和可靠;③数据收集过程中学生的实际情况比较复杂，如有些同学家庭状况确实不好但平时生活仍然很奢侈而未能成为贫困生;④挖掘工具的使用也会对数据挖掘结果造成一定的影响等等.

4 结语

通过以上分析，得知使用FP－growth算法进行数据挖掘，找出了数据间的关联规则，能够在某种程度上反映了贫困生的认定与学生学习成绩、贷款、消费水平以及家庭情况等之间存在的关系规律，对贫困生的认定有很大的参考价值和指导意义.其实除了关联规则这种常用的挖掘技术以外，还有许多其他的先进的挖掘技术和方法.针对具体的问题，怎样选择一个更高效率的数据挖掘技术和方法是将来需要研究解决的问题.

［1］ 纪希禹.数据挖掘技术应用实例［M］.北京:机械工业出版社，2009.

［2］ 曹路舟.关联规则算法在高职院校贫困生认定工作中的应用［D］.合肥:安徽大学，2011.

［3］ JIAWEIHAN，MICHELINE KAMBER.范明，孟小峰等译.数据挖掘概念与技术［M］.北京:机械工业出版社，2001.

［4］ 李雄飞，董元方，李军.数据挖掘与知识发现［M］.2版.北京:高等教育出版社，2010.

［5］ JIAWei－Han，KAMBER M.Datamining concepts and techniques［M］.北京:高等教育出版社，2001.

［6］ 李金娟，王卫锋.基于FP－growth算法在学生成绩中的关联规则分析［J］.巢湖学院学报，2007，16:30－33.

［7］ 石云平.FP－growth关联算法研究［J］.计算机与信息技术，2008，26:11－12.

［8］ 王新宇，杜孝平.FP－growth算法的实现方法研究［J］.计算机工程与应用，2004，29:174－176.

［9］ 王远敏.图象数据库关联规则的挖掘方法研究［J］.数字技术与应用，2012(6):81－82.

［10］周琪锋，张立臣.数据挖掘在实验系统的应用［J］.科技资讯，2007(8):101－102.

［责任编辑 王新奇］

On the Application of FP－Grow th Algorithm in Determ ining the Needy Students in Higher Vocational Colleges

CAO Lu－zhou

(Department of Information Technology，Chizhou Vocational Technology College，Chizhou 247000，China)

With the increasing student population in higher vocational colleges，students in needy condition have been on the increase.The subsidizing is becomingmore complicated.The previous identification approach can notmeet the currentneeds.To better tackle the issue，FP－growth algorithm is applied in the datamining of the needy students.The potential value latent in the data and the internal relationships of the data can be identified.The approach is of referential value for the identification of the needy students，hence，higher efficiency.

datamining;association rule;FP－growth algorithm

1008－5564(2015)01－0068－05

TP301

A

本文通过以数据表的形式建立贫困生认定的数据平台，采用量化的方法发掘出贫困生认定和学生日常生活中的哪些因素有关，让学校在以后贫困生认定过程中对这些因素加以重视，对理性的去认定贫困生，并做出相应的、合理的资助策略很有帮助.

2014－09－20

2012年池州职业技术学院教学研究项目“关联规则在高职院校贫困生认定工作中的应用研究”(池职院［2012］146号);2010年池州职业技术学院院级教学团队“计算机应用技术教学团队”(池职院［2010］39号);2013年安徽省优秀人才基金重点项目“基于路径约束的消除XML冗余算法研究”(2013SQRL131ZD)

曹路舟(1979—)，男，安徽枞阳人，池州职业技术学院信息技术系副教授，硕士，主要从事数据挖掘和XML数据库研究.