基于粗糙集改进Apriori算法在高校贫困生认定中的应用

樊伟 刘红 匡亚茹

摘要：为增强困难学生认定的准确度，该文从粗糙集理论思想通过属性约简，得到关键属性集合，建立决策信息表，利用改进的Apriori算法对决策条件属性数据分析，给出频繁项集;通过对部分贫困生数据实验验证，得出该算法在一定程度上保证贫困生认定的准确度。

关键词：粗糙集;Apriori算法;属性约简;数据挖掘;贫困生认定

中图分类号：TP391.9      文献标识码：A

文章编号：1009-3044（2019）21-0003-04

开放科学（资源服务）标识码（OSID）：

Abstract： In order to enhance the accuracy of the identification of difficult students， this paper gets the key attribute set from the rough set theory thought through attribute reduction， establishes the decision information table， uses the improved Apriori algorithm to analyze the decision condition attribute data， gives the frequent item set， and through the experimental verification of some poor students ' data， It is concluded that the algorithm ensures the accuracy of the identification of poor students to a certain extent.

Key words： rough sets; Apriori algorithm; Apriori algorithm; teaching quality evaluation; Data mining; poor student identification

1 背景

贫困生的认定是高校学生工作的重要组成部分，国家和地方政府推出一系列举措帮扶每个贫困生，制定一系列的量化标准。如何认定贫困生，把助学金用到真正学校帮助的学生身上。认定工作完成学生资助工作首要任务，是学校实施各项资助措施的依据[1]。本文提出了基于粗糙集的属性依赖度对属性进行约简的算法，利用核心属性数据，再通过改进的Apriori算法对决策属性数据分析，总结出频繁项集;大大减少读取数据库的次数，防止候选项集大量产生，降低了关联规则挖掘的时间复杂度，提高对贫困生认定的效率。

2 设计思路

2.1 设计流程

该算法的设计思想分两步走：首先运用属性约简算法对全校Excel统计的贫困生数据进行约简，将约简后的决策信息表导入进Access数据库;再通过改进的Apriori算法对决策信息进行关联规则的数据分析，从而产生频繁项集。算法流程图1如下：

2.2 粗糙集基本理论

粗糙集理论是处理模糊和不确定信息的数学工具，在1982年由波兰科学家Z.Pawlak提出，其主要思想是在保留分類能力的前提下进行数据化简，识别并分析数据之间依赖关系。目前在机器学习、过程控制、决策分析等领域应用广泛。属性约简是粗糙集理论中研究重要课题，更多学者提出改进约简算法[3]。属性约简基于Rough集理论的知识获取，主要是通过对原始决策表的约简，在保持决策表决策属性和条件属性之间的依赖关系不发生变化的前提下对决策表删除不相关或不重要的属性。

定义1 形式上，四元组[S=（U，A，V，f）]是一个信息系统，其中[A=C?D]，[U={x1，x2，???，xn}]，[U]中的每个[xi（1≤i≤n）]称为一个对象，[A=C?D]是属性的非空有限集合，[C={c1，c2，???，cm}]是条件属性集合，[D={d1，d2，???，dk}]是决策属性集合，且[C?D=?]，[C≠?]，[D≠?];其中，[V=a∈AVa，Va]是属性a的值域;[f：?a∈A，x∈U，f（x，a）∈Va]，一般简记为[S=（U，A）]，则这样的知识表达系统为决策表。

定义2 令[R]为一族等价关系，[r∈R]，如果[ind（R）=ind（R-{r}）]，则称[r]为[R]中不必要的;否则称[r]为[R]中必要的。

设[Q?P]。如果[Q]是独立的，且[ind（Q）=ind（P）]，则称[Q]为[P]的一个约简。[P]中所有必要的原始关系构成集合称为[P]的核，记做[core（P）]。

核与约简有如下关系：[core（P）=?red（P）] ，其中[red（P）]表示[P]的所有约简[5]。

定义 3 假设[P]和[Q]是集合[U]上的等价关系，正域、负域、边界域定义如下：

正域：[posp（Q）=X∈U/QPX];

负域：[NEGp（Q）=X∈U/QPX];

边界域：[BNDp（Q）=X∈U/QPX-X∈U/QPX]。

定义4 令[K=（U，A）]为一知识库，且[P，Q∈R]当[k=rp（Q）=|posp（Q）|/|U|]称知识[Q]是[k]度依赖于知识[P]的，记作[p?kQ]。当[k=1]时，我们称[Q]完全依赖于[P];当[0

2.3 改进的Apriori算法

Apriori算法是经典的挖掘频繁项集和关联规则的数据挖掘算法，使用频繁项集性质的先验性质进行逐层搜索的迭代方法。在计算过程中多次读取数据库，需对项集剪枝。针对Apriori算法在计算中产生大量的候选项集和对数据库的读取时有较大的I/O开销等问题[6]，提出了利用链表建立数据模型，链表包括分项集头结点、项结点、事务结点三种结点。 如图2所示对数据库只需扫描一次，这样避免在Apriori 算法中多次扫描数据库，大大减少了对I/O开销。链表的兄弟结点从左到右依照子集支持度的递增顺序排列，由1-项集产生较少的候选2-项集，由2-项集再产生更少的候选3-项集，大大提升内核的汇聚能力。

3 算法在高校贫困生认定中验证

在网络信息化高度发展的当代，对贫困生的认定应从多方面入手来进行界定，定量和定性相结合的认定标准，对贫困生的基本信息进行汇总，相关信息表如下：

学生基本信息表（学号，姓名，性别，出生年月，民族，身份证号码，政治面貌，院系，专业，年级，个人爱好，孤残，单亲，烈士子女，健康状况，家庭人口数，家庭年收入，已参加勤工俭学，家庭地址）。

家庭成员登记表（姓名，年龄，与学生关系，职业，工作单位，健康状况，学号）。

贫困生认定申请表（学号，姓名，院系，专业，年级，班级，家庭人均年收入，申请理由）。

学生成绩表（学号，姓名，院系，班级，课程名，成绩）。

校园一卡通月消費明细表（卡号、学号，姓名，性别，月消费金额）。

助学贷款登记表（学号、姓名、院系、专业、年级、班、贷款金额（元） [7]。

对上述数据表等信息进行汇总分析，得到反映学生是否贫困的基本因素（a1：是否申请贫困;a2：是否补考;a3：户籍;a4：家庭人口;a5：月生活费用;a6：是否抽烟喝酒;a7：贷款金额; a8：兄弟姐妹上学人数;a9：烈士子女;a10：家庭人均月收入;a11：危重病人;a12：单亲或孤残，a13：父母职业;a14：是否贫困地区），构成原始信息决策表的条件属性[C]。现抽取某高校17级15名学生相关信息构成的论域[U={x1，x2，???，x15}]，认定学生是否为贫困结果：贫困和不贫困，即得决策属性集[D]。

为了方便运用粗糙集算法对上述数据进行数据约简，对连续型数值数据进行离散化，如贷款金额、月消费金额等属性，用数字编号各属性值：

调整最小支持度为25%，最小置信度为80%，利用改进的Apriori算法生成频繁项集，如表6所示：

对生成的10条规则加以分析得出：

规则1：月生活费用>500，说明该生月生活费在500元以上，虽是农村户口，家庭人口在6人以下，家中有2人上学，父母务农，贫困生认定的可信度在56.17%。

规则4：月生活费用<=500，说明该生月生活费在500元以下，虽是城镇户口，但父母失业，低保，贫困认定的可信度为87.23%。

规则7：月生活费用<350，说明该生单亲，农村户口，上学人数有2人，家庭负担较重，申请过助学贷款，贫困生认定的可信度为100%。

规则9：月生活费用<350，说明该生月生活费用在350元以下，虽城镇户口，单亲，但是烈士子女，符合重点优抚对象，贫困生认定的可信度为100%。

4 结束语

本文提出基于粗糙集理论的属性依赖度的属性约简方法引入到经典的Apriori算法的改进工作中减少对数据库的扫描次数及产生大量的候选项集的问题，对贫困生信息的认定实验中验证了该方法能有效地进行数据约简和关联规则挖掘，能提高高校贫困生认定的效率。

参考文献：

[1] 丁桂兰， 周艳华. 高校贫困生认定的现实困境与对策思考[J]. 教育与职业， 2010（9）： 33-35.

[2] 白华， 徐英. 高校贫困生资助绩效评价指标体系设计[J]. 黑龙江高教研究， 2016（6）： 116-120.

[3] 张文东， 李明壮， 等. 基于粗糙集理论的属性约简算法[J]. 计算机工程与设计， 2008（11）： 5795-5797.

[4] 杨沛， 袁莎， 等. 一种改进的基于依赖度的属性约简算法[J]. 云南民族大学学报， 2011（11）： 504-507.

[5] 陈鑫影. 粗糙集在企业信息系统中的应用[J]. 商场现代化， 2007（11）： 36.

[6] 周玲元， 段隆振. 改进的 Apriori 算法在高校图书推荐服务中的应用研究[J]. 图书馆学研究， 2013（2）： 89-91.

[7] 曹路舟. Apriori算法在高职院校贫困生认定工作中的应用[J]. 池州学院学报， 2012（12）： 9-11.

[8] 申静， 王华彪. 高校贫困生认定的困境与对策[J]. 学校党建与思想教育， 2012（3）： 50-51.

[9] 胡善忠， 徐怡. 多粒度粗糙集粒度约简的高效算法[J]. 计算机应用， 2017（37）： 3392-3398.

[10] 喻瑛， 杨峥， 王伟杰. 基于分布式计算模式的两种属性约简算法[J]. 计算机技术与发展， 2018（1）： 28-32.

【通联编辑：谢媛媛】