关联规则挖掘算法FP-Growth在高职网络技术专业学生成绩分析中的应用

罗拥军， 罗云芳

(广西职业技术学院　计算机与电子信息工程系， 广西　南宁 　530226)



关联规则挖掘算法FP-Growth在高职网络技术专业学生成绩分析中的应用

罗拥军， 罗云芳

(广西职业技术学院计算机与电子信息工程系， 广西南宁 530226)

从大量的成绩数据中进行数据挖掘并从中获得有价值的信息，是一件非常有意义的研究。以计算机网络技术专业学生10年的成绩作为数据源，运用基于关联规则的FP-Growth算法，研究5门课程之间的关联，为制订该专业人才培养方案提供参考和借鉴。

关联规则；FP-Growth算法；成绩分析

0　引言

在学校，历年的教学实践产生了大量的成绩数据。如何更好地利用和分析这些数据，从而为教学管理服务，这是非常重要的科学研究。为了让海量规模的成绩数据能够真正发挥巨大的作用，需要将这些数据转换为有用的信息和知识，即从传统的数据统计向数据挖掘和分析进行转换。

关联规则挖掘是数据挖掘领域中活跃的一个分支。关联规则主要是描述数据库中数据项之间某种潜在关系的规则，目前它在教育方面的研究与应用主要体现在课堂教学评价、试题分析、学生管理等方面[1-3]。

本文基于FP-Growth算法[4]，对广西职业技术学院2003～2012级计算机网络技术专业学生的计算机应用基础等5门课程的成绩进行分析，主要研究各课程之间的内在联系，并给出详细的分析，为学校以及教师的教学决策提供帮助。

1　关联规则及其挖掘的过程

1993年，R. Agrawal等人在文献[5]中首先提出关联规则分析问题。关联规则的相关概念如下：设项集I={i1,i2,…,in}，其中in称为项；交易集D={T1,T2,…,Tp}，其中Tp称为交易，它是项的集合，并且T⊆I。

关联规则：设X、Y是某些项组成的非空集合，则形如X⟹Y(其中X⊆I,X≠φ,Y⊆I,Y≠φ，并且X∩Y≠φ)的逻辑蕴涵关系称为关联规则。X称为关联规则的前件或先决条件，Y称为关联规则的后件或结果。

关联规则的支持度：交易集D中包含项集X和Y交易数的与交易总数之比，称为规则X⟹Y在交易集D中的支持度，计算公式如下：

关联规则的置信度：交易集D中包含X和Y的交易数与包X的交易数之比，称为规则X⟹Y在交易集D的置信度，记作confidence(X⟹Y)，计算公式如下：

对关联规则X⟹Y，其置信度表示X和Y同时出现的概率有多大。

支持度是对关联规则重要性的衡量，用以说明该规则在所有事务中的代表性有多大，支持度越大，该关联规则越重要；置信度则是对关联规则可靠性的衡量，置信度越大，则说明该关联规则越可靠。

关联规则必须满足的支持度的最小值，称为最小支持度，用min_sup表示。关联规则必须满足的置信度的最小值，称为最小置信度，用min_conf表示。

对于交易集D和关联规则X⟹Y，若同时满足sup(X⟹Y)≥min_sup和confidence(X⟹Y)≥min_conf则关联规则X⟹Y称为强规则，否则关联规则X⟹Y称为弱规则。强关联规则表示该规则是既重要又可靠的关联规则。

项集支持度：设X是由某些项目组成的非空集合，即X⊆I且X≠φ，则X在交易集D中的支持度是交易集D中包含项集X的交易数与所有交易数之比，记为sup(X)，计算公式如下：

如果项集X的支持度sup(X)≥min_sup，则称X为频繁项集。

关联规则挖掘问题就是产生支持度和置信度分别大于用户给定的最小支持度和最小置信度的强关联规则[4]。

2　FP-Growth算法

2000年，J. Han 等人提出了频繁模式增长算法——FP-Growth算法。该算法是一种不产生候选项集的挖掘频繁项集的方法，采用的是分而治之的策略，它通过2次数据库扫描，把每个事务所包含的频繁项集压缩存储到频繁模式树FP-Tree中，然后利用这棵树生成关联规则。

算法的第一步，构造频繁模式树FP-Tree。参见图1，首先第一次扫描数据库D，得到频繁1-项集的集合F和每个频繁项的支持数(即项目在D中出现的次数)。按照支持数的大小降序排列，构建频繁项目表L。

图1　生成频繁模式树

之后创建频繁模式树FP-Tree的根结点，用null标记。再次扫描数据库D，从每个事务T中选取频繁项，而从事务T中把非频繁项删除，并按照L中的次序排列。并对每个事务T创建一个分支，构建频繁模式树时，每个节点用项目名和支持数来标识。事务T1中的第一个频繁项链接到根，第二个链接到第一个，依此类推。如果T2的分支与原来的路径共享前缀时，则沿共同前缀的每个节点数加1；并为跟随共享前缀之后的项创建结点并链接。同样插入其他分支，直至全部事务插入完毕，最终生成FP-Tree。

第二步，频繁模式树FP-Tree调用FP-Growth(Tree,null)来完成挖掘。其流程示意如图2。

图2　FP-Growth的调用

简而言之，FP-Growth算法的执行过程如下：

(1)在FP-Growth递归调用的第一层，模式前后a=null，得到的其实就是频繁1-项集。

(2)对每一个频繁1-项集，递归调用FP-Growth()，从而获得多元频繁项集。

3　FP-Growth算法在成绩分析中的应用

3.1数据预处理

我们收集了广西职业技术学院计算机网络技术专业计算机应用基础、计算机安装和维护技术、计算机网络技术、服务器配置与管理技术、网络设计与配置技术的2003～2012共10个年级的成绩，并对数据进行预处理。数据主要来源于学院教务科研处。

(1)对缺少成绩的处理。个别学生因为退学、没有参加考试等原因造成无成绩记录，为不影响数据挖掘，将此类记录逐一删除。

(2)对补考成绩的处理。在原始数据中，同时记录有不及格成绩和补考成绩的，我们只保留最初考试的成绩分数，而将补考成绩去掉。

经过数据清理后，共得到有效记录1 048条(见表1)。

表1　2003～2012年级部分学生成绩表

注： L1为计算机应用基础；L2为算机安装与维护技术；L3为计算机网络技术；L4为服务器配置与管理技术；L5为网络设计与配置技术。

(3)数据离散化

在对学生试卷成绩进行关联分析挖掘时，需进行离散化处理，为简单起见，将成绩划分成≥75分为学习良好，用“1”表示；以下则用“0”表示，如表2所示。

表2　学习成绩离散化(部分)

3.2数据挖掘及结果分析

我们设定最小支持度为30%，置信度为20%，挖掘得到项集支持度和置信度见表3～6。

表3　计算机应用基础与其他课程成绩项集的支持度和置信度

从表3可以看出计算机应用基础学习成绩良好者，计算机安装与维护技术、计算机网络技术、服务器安装与管理技术及网络设计与配置技术都有可能取得良好的成绩。

表4　专业基础课与其他课程成绩项集的支持度和置信度

从表4可以看出计算机安装与维护技术学习成绩良好者，网络设计与配置技术可能取得良好的成绩；计算机网络技术学习成绩良好者，服务器安装与管理技术也成绩良好。

表5　专业基础课与其他课程成绩项集的支持度和置信度

从表5可以看出计算机应用基础与计算机安装与维护技术学习成绩均良好者，网络设计与配置技术取得良好成绩的可能性达68.24%；计算机应用基础与计算机网络技术学习成绩均良好者，服务器安装与管理技术成绩也相当好，其可能性达87.69%。计算机网络学习成绩好，网络设计和配置技术也取得良好成绩还说得过去，但内容以偏硬件为主的计算机安装与维护技术成绩良好，在内容以理论为主的计算机网络技术和操作以软件为主的服务器配置和管理技术也取得好成绩，在关联上似乎显得牵强。

表6　先导课程与网络设计与配置技术成绩项集的支持度和置信度

表6说明，作为一门综合性的课程，网络设计与配置技术其先导课程学习成绩良好，那么本门课程也容易获得较好成绩，其可能性达78.57%。

4　结论

数据挖掘结果表明，这5门课程安排的顺序是合理的，即第1个学期安排计算机应用基础，第2学期安排计算机安装与维护技术，第3学期安排计算机网络技术，第4学期安排服务器与管理技术，第5学期安排网络设计与配置技术，这也说明了专业基础课的重要性。

[1]谭庆. 关联规则Apriori算法在试卷成绩分析中的应用研究[J]. 信阳师范学院学报(自然科学版),2009,22(2):300-303.

[2]崔学文. 关联规则挖掘算法Apriori在学生成绩分析中的应用[J]. 河北北方学院学报(自然科学版),2011,27(1):44-47.

[3]陈伟莲. 基于数据挖掘技术的某学院成绩分析应用[D]. 华南理工大学,2012.

[4] R Agrawal, R Srikant. Fast Algorithms for Mining Association Rules in Large Database[C]∥Proceedings of the 20th International Conference on Very Large Data bases.San Francisco, CA, USA：Santiago，1994:487-499.

[5] R Agrawal, T Imielinski, A Swami. Mining Association Rules Between Sets of Items in Large Databases[J].Acm Sigmod Record,1993,22(2):207-216.

[6]J Han , J Pei, Y Yin. Mining frequent patterns without candidate generation[J].Acm Sigmod Record, 2000, 29(2):1-12.

[Abstract]Data mining from a large number of performance data and getting valuable information is a very meaningful research.Taking the 10-year scores of students majoring in computer network technology as a source of data, using the FP-Growth algorithm based on association rules, the association between five courses was studied. It can provide reference for formulating the professional talent training scheme.

[Key words]association rules; FP-Growth algorithm; score analysis

[责任编辑刘景平]

Application of Association Rule Mining Algorithm FP-Growth in the Score Analysis of Students from Network Technology Specialty in Polytechnics

LUO Yong-jun, LUO Yun-fang

(Department of Computer and Electronic Information Engineering,Guangxi Polytechnic, Nanning, Guangxi 530226, China)

TP311；TP391

A

1672-9021(2016)02-0067-06

罗拥军(1964-)，男，广西全州人，广西职业技术学院计算机与电子信息工程系高级实验师，主要研究方向：计算机应用与教学。

2015-11-25