打开文本图片集
【摘 要】现行高校教务管理信息系统中存放了大量的历史数据，这些数据所隐藏的价值并没有被充分挖掘和利用，主要原因是目前的教务管理系统几乎没有数据挖掘功能。本文分析了关联规则的经典Apriori算法的优缺点，使用数据库SQL及VB编程语言对其优化，开发了一个教学决策支持平台原型，并以学生成绩与课程设置的潜在联系为例进行了分析。
【关键词】数据挖掘；关联规则；Apriori算法；决策支持平台
0 引言
数据挖掘是从大量或海量的数据中提取或“挖掘”知识[1]，找到或发现隐含在其中的预先并不知道的有潜在价值的知识的过程，有时也称之为知识发现。网络时代的高校购买或自行开发了各种信息化管理系统，例如教务管理信息系统、招生就业管理系统以及人事管理等系统等。这些系统中含有大量的数据，但是国内的教务管理信息系统几乎没有提供类似的决策支持功能。因此，有必要对这些大量的历史数据进行数据挖掘分析，提取隐含在其中的有价值的信息，以便于管理和决策活动的开展和进行。
1 关联规则研究进展
Agrawal等人于1993年首先提出挖掘顾客交易事物集中项集之间的关联规则，并于1994年设计了基于频集理论的Apriori算法[2-3]，以后很多的研究人员对此展开了研究，完善了其算法，并陆续提出了新的算法。例如，Hash算法、分块算法、串联关联规则算法、并行算法、分布式关联规则、增量挖掘算法等，上述算法都会产生所有频繁项，为了提高效率，有学者提出了直接挖掘极大频繁项集[4]或闭集频繁项[5]，二者的数量都远小于所有频繁项。韩家炜等人于2000年左右提出的FP-Growth关联规则挖掘算法，其挖掘效率较之Apriori有了数量级的提高。
2 相关定义
Apriori算法是一种经典的挖掘布尔型关联规则的频繁项集算法。下面给出一些常用的定义。
定义1 k-项集：包含k 个项目的项集称为k-项集。满足最小支持度的项集（见定义3）称为频繁项集，简称频繁集。
定义2 关联规则：A、B为两个项集，关联规则是诸如A→B的蕴涵式，此处A？奂I，B？奂I，且A∩B=？覫，A被称为规则前件，B被称为规则后件。
定义3 支持度：亦称为覆盖度，是事物库D中包含某项集的元组数目占所有元组的百分比。规则A→B表示同时包含项集A和B所占的百分比，见公式1，D表示事物库中元组总数。
定义4 置信度：或称可为信度、概率（Probability），规则A→B表示条件概率PA│B，见公式2。
定义5 强关联规则：对于不小于最小支持度阈值min_sup，并且不小于最小置信度阈值min_conf的规则称作强规则。反之，则称为弱关联规则。
定义6 期望置信度：期望置信度（Expected Confidence）是指在没有任何条件影响时，某项集在所有事务中出现的概率有多大。规则A→B的期望可信度是P（B）。
定义7 最大频繁项集： 若频繁项集L的所有超集都是非频繁项集， 则称L为最大频繁项集， 记做 MFI （Maximal Frequent Itemset）。
定义8 作用度：或称为提升度（Lift）、兴趣度分数（Interesting Score）或重要性（Importance）等，它描述了项集A出现对项集B的出现的影响程度。一般来说，作用度定义为可信度和期望可信度的比值（见表1），在某些文献里其计算方法不同。
定义3至定义7可以归纳为表1，这里用P（A）表示事务中出现项集A的概率，PB/A表示在出现项集A的事务中出现B的概率。
表1 各定义含义及计算公式
支持度S说明了本条规则在全部事务中所占的比例，该值越大，说明其关联的程度越大，可见它是对关联规则重要性的衡量，而置信度是对关联规则准确度的度量。如果某条关联规则的置信度很高而其支持度却很低，那么这条关联规则的实用性很小，因而也不是很重要。
作用度（提升度）说明了A与B的之间某种程度的相关性 [6]。一般来说，好的关联规则的提升度应该大于1，如果作用度等于1，说明A、B是两个互相独立的事件（其关联规则无意义）；若小于1，则说明二者之间为负相关，本文不讨论负相关，感兴趣的读者可以参阅相关文献。
3 经典关联挖掘算法Apriori
关联规则挖掘基本过程：选择事物表，统计各个项目的数目及总事务数；根据用户给定的最小支持度计算其最小支持计数，找出所有频繁项目集或者最大频繁项目集；根据用户给定的最小可信度，在频繁项目集中，找出强关联规则。
下面看一个实例来了解其基本算法。现有某零售商保存的客户交易记录如表2所示，其中包括交易ID、顾客ID及和商品ID等。
表2 客戶交易表
设定最小支持度MinSupport=0.3，最小置信度为MinConfidence=0.6，用Apriori算法找出全部的频繁项目集以及强关联规则。根据交易事物表，采用Apriori算法，支持数MinSup_count= MinSupport * 3=0.9。
3.1 生成频繁集
（1）扫描数据库，生成候选集C1={（A，1），（B，3），（C，1），（D，2）}；根据MinSup_count0.9可得到频繁项目集L1={A，B，C，D}。
（2）由L1生成候选集C2={（AB，1），（AC，0），（AD，0），（BC，1），（BD，2），（CD，1）}；根据MinSup_count0.9可得到频繁项目集L2={AB，BC，BD，CD}。
（3）由L2生成候选集C3={（BCD，1）}；根据MinSup_count0.9可得到频繁项目集L3={BCD}。
（4）由L3生成候选集C4=？，L4=？，因为为空故算法停止，所有的频繁项目集为{A，B，C，D，AB，BC，BD，CD，BCD}，可以生成关联规则的频繁项目集为{AB，BC，BD，CD，BCD}，其最大频繁项目集为{AB，BCD}。（通俗来说，在频繁项目集中，那些没有被其他元素所包含的频繁项目集称之为最大频繁项目集）。
3.2 生成关联规则
关联规则的置信度使用如下方法计算
（1）对每一个频繁项目集f，生成全部的非空并且非全集的子集。
（2）对f的每一个非空子集x，计算规则x（f-x）的置信度：Confidence（x（f-x））= （f的支持数/x的支持数）
① 频繁项目集{AB}的非空子集为{A}，{B}
Confidence（AB）=1/1=1
Confidence（BA）=1/3=0.33
② 频繁项目集{B，C}的非空子集为{B}，{C}
Confidence（BC）=1/3=0.33
Confidence（CB）=1/1=1
③ 频繁项目集{B，D}的非空子集为{B}，{D}
Confidence（BD）=2/3=0.67
Confidence（DB）=2/2=1
④ 频繁项目集{C，D}的非空子集为{C}，{D}
Confidence（CD）=1/1=1
Confidence（DC）=1/2=0.50
⑤ 频繁项目集{B，C，D}的非空子集为{B}，{C}，{D}，{B，C}，{B，D}， {C，D}。
Confidence（BCD）=1/3=0.33
Confidence（CBD）=1/1=1
Confidence（DCB）=1/2=0.50
Confidence（BCD）=1/1=1
Confidence（BDC）=1/2=0.50
Confidence（CDB）=1/1=1
根据计算可得所有强关联规则如下表3。
通过上述演算可以看出，Apriori算法的优点是原理简单易懂，缺点是需要多次扫描数据库，效率较低，并且在挖掘出的强关联规则中可能存在欺骗性，即一些强关联规则带来的知识并不符合日常认知。因此，为了挖掘有价值的关联规则，可以考虑将作用度作为第三个度量参数。
4 教务管理系统关联挖掘算法应用实例
4.1 数据获取
本平台数据来自正方教务管理系统，该系统有数据导出功能，可以选择导出为EXCEL文件或是DBF数据库文件。一般建议导出为DBF文件， 因为EXCEL2003及以下版本最大容量为65536行。考虑到多年累积下来的数据量很大，本实验平台将导出的数据汇集到SQL SERVER数据库中。导出的表结构如表4所示。
表4 教务管理系统成绩导出表
4.2 数据转换
（1）数据清洗
数据清理在整个数据挖掘的过程中占有极其重要的位置，好的数据是知识挖掘成功的关键，它可能占到建模的70%左右的工作量。
首先删除与数据挖掘无关的一些的字段，减少存储空间的占用。另外，由于系统操作人员的一些小的误操作，会导致数据呈现一系列的问题，像课程名称不统一，例如《高等数学A》及《高等数学1》是同一门课程，在使用时必须统一，对于大量数据可以考虑编写程序进行排查。删除由于学籍异动等原因造成的成绩空值记录。对于成绩重复的，根据标志字段，免修的则直接按照规定给予成绩；对于补考成绩一律以不及格处理。由于该系统已经直接把考察课程的“优秀、良好、中等、及格、不及格”转换为相应的分数成绩，所以不需要在程序里另行处理。
（2）数据离散化
由于经典Apriori算法是针对布尔型二值数据的，因此需要对其离散化，将连续型的成绩数据转换为0、1（考虑到出题的难易程度不同，以各科的平均分数作为界限，平均分及以上的为1，否则为0，也可以设置一个阀值供用户设置），同时编程实现数据的行列转换，即将表4所示的数据转化为表5所示的形式。另外，对于不同的数据挖掘对象及需求，对于原始数据的离散化，还可以考虑使用等分区间法、固定区间法、排序量化等方法。对于成绩的转换方法，还可以考虑将原始分数转换为标准分后再进行离散化处理。
4.3 数据挖掘工具
目前可以选择的数据挖掘工具有很多，国外的主要有IBM Miner、SAS Miner、SPSS Clementine等，这些数据挖掘工具包都提供了常用的挖掘算法，但由于是商业化的软件，价格昂贵。开源的则主推新加波怀卡托大学的Weka软件。国内的主要有基于B/S架构的数据挖掘软件工具主要有太普数据挖掘套件，英文名TIP DM Suite，简称TipDM，是广州太普软件花费数年时间自主研發的一个数据挖掘套件，使用JAVA语言开发，能从各种数据源获取数据，建立各种不同的数据挖掘模型。另外还有天津天才博通科技有限公司开发的GDM数据挖掘分析软件。BI产品内置的数据挖掘软件主要有SAP NetWear 7.0 Data Mining Workbench、Oracle 11g Data Mining、Microsoft SQL Server 2005 Analysis Services等。
本实验平台采用SQL SERVER 2005数据库，利用VB编程[7]，采用经典的Apriori算法，增加作用度对关联规则做进一步约束。
4.4 实验平台简介
该平台是“基于数据挖掘的教学决策支持平台”的子系统，系统采用灵活的插件结构，便于算法的扩展。从图1中可以看出，该系统非常灵活，能够从现有的数据库中任意选择感兴趣的课程以及不同的课程性质进行挖掘。图2展示的是利用Apriori经典算法结合作用度进行数据挖掘，生成强关联规则，并且可以将结果以表格的形式导入到WORD文件里，方便查看及打印。
图1 选择课程及课程性质
图2 课程关联规则挖掘
4.5 挖掘结果分析
使用Apriori算法，设置最小支持度S=0.2，最小置信度为C=0.5，作用度Lift=1.5，用Apriori算法挖掘某计算机班级的必修课成绩，记录数为1718条，人数30人，表中的Y/N代表是否为强关联规则。
表4 课程关联规则表
通过分析上述结果，我们可以了解到C语言》作为先开课有利于《数据结构》等其它课程的学习；分析中还发现，离散数学->数据结构，数据库原理，这条关联规则如果仅仅使用最小支持度及最小置信度来考量，它就不是强关联规则，但是考察作用度Lift得知《离散数学》的学习效果将对《数据结构》及《数据库原理》有着非常大的提升作用，因此我们认为它是一条好的规则。
5 结束语
我们在研究了Apriori算法的基础上初步实现了一个数据挖掘实验平台，可以针对正方教务管理系统的学生成绩进行挖掘，结合成绩预警系统，能够给教务管理者的教学决策提供一定的帮助。
【参考文献】
[1]Jiawei Han Micheline Kamber.数据挖掘概念与技术[M].范明，孟小峰，译.2版.北京：机械工业出版社.2007：10-11.
[2]Agrawal R，Imielinski T，Swami A.Mining Association Rules between sets of Items in Large Databases[C]//：Proc ACM SIGMOD Int Conf Management of Date.Washington D C，1993：207-216.
[3]R.Agrawal R.Srikant Fast Algorithms for Mining Association Rules in Large Databases[C]// Proc. 1994 Intl. Conf. On Very Large Databases（VLDB’1994）. Santiago Chile，1994：487-499.
[4]Bayardo R.Efficiently mining long patterns from databases[C]//Pro-ceedings of the ACM SIGMOD International Conference on Man-agement of Data.New York： ACM Press， 1998.
[5]Pasquier N， Bastide Y， Taouil R， et al.Discovering frequent closed itemsets for association rules[C]//Proc of the 7th Int Conf Database Theory （ ICDT" 99） ， Jerusalem， Israel， Jan 1999：398- 416.
[6]陳文伟，黄金才.数据仓库与数据挖掘[M].北京：人民邮电出版社，2004.
[7]于卫红.用VB对基于Apriori算法的数据挖掘的实现[J].计算机工程，2004，30（2）：196-196.
[责任编辑：薛俊歌]