基于数据挖掘Apriori算法实现与应用

山东科技大学数学与系统科学学院 李 潇

基于数据挖掘Apriori算法实现与应用

山东科技大学数学与系统科学学院 李 潇

本文主要对数据挖掘的有关算法进行学习与应用。首先介绍了这些算法的基本思想和算法步骤，然后运用这些算法进行实际问题的求解。本文着重介绍的是关联规则的Apriori算法。对Apriori算法，用其对当下高等学校排课的问题进行求解。

数据挖掘；Apriori算法

1.关联规则

给定一个事物集D，挖掘关联规则问题就是寻找支持度和置信度分别大于用户给定的最小阀值的关联规则。

我们在用关联规则解决某一问题时一般遵循一下步骤：

（1）任务：描述变量之间的关联关系；

（2）结构：用概率表示的“关联规则”；

（3）评分函数：支持度和置信度的阀值；

（4）搜索方法：系统搜素方法（通常使用的是带有修剪的广度优先）；

（5）数据管理技术：多重线性扫描。

2.Apriori算法及改进

Apriori算法是挖掘关联规则的最典型算法，该算法将挖掘关联规则的过程分为两个步骤：第一步利用迭代，找出所有的频繁项集；第二步利用频繁项集构造出强关联规则。算法的核心是利用剪枝步和连接步找出所有的频繁项集。

最后可能会产生大量的候选集和迭代过程中需要大量的扫描数据库，是Apriori算法运行效率不高的重要原因。为了提高算法的运算效率，Mannila曾经提出过一个Apriori算法的改进，即修剪算法。因为一个项集是频繁项集当且仅当它的所有子集都是频集。那么，如果Ck中某个候选项集中有一个（k-1）子集不是频集，那么即可以通过修剪算法剪掉Ck。正因为有了修剪算法可以显著降低计算所有的候选项集支持度。可以减少产生大量的候选项集。

另一种解决方法是，可以利用哈希表存储数据信息，包含该记录的编号和它的字段长度。在每次的扫描时，只扫描表中存在的记录，不需要每条记录都扫描。通过辅助表F，减少数据库的访问次数，提高运算速度。

3.Apriori算法在学生成绩中的应用

3.1 问题引入

成绩是国内各高校评价学生的重要指标，合理开发利用这些资源，利用数据挖掘分析这些学生成绩，找到课程之间的相关关系，必将对课程的开设安排具有重要的指导作用。

以国内某大学01届计算机专业学生在校四年的学习成绩为数据源，选取成绩数据库中计算机网络，C语言，计算机基础，外语，高等数学，数据库原理等8门课程作为研究对象，找出某门课程对其他课程的开设是否有影响，为学校教科老师以后排课提供参考，为以后学生选课提供依据。

3.2 建模过程

（1）数据清洗：原始数据库中包含全校各个专业、各个年级、各个学科的所有成绩，某些记录难免会有一些差错或者从经验上看没有关联的数据，为了便于进行数据挖掘，只选择某班部分学生的8门课程成绩作为挖掘对象，去掉其他所有不需要的字段，删除完全空白记录，如果某条记录中的某一两门课程成绩缺少，则该条记录缺少的成绩补为该科成绩的平均分，对于某条记录中的某门课程成绩有多于一个成绩的情况，则该门成绩按第一次成绩计算。则清洗后的数据表部分数据如表2.1所示。

表2.1

（2）数据转换：由于编写的Aprior算法程序是是处理离散数值的，因此，需要将数据进行转化，将大于等于90分，大于等于80且小于90，大于等于70且小于80，大于等于60且小于70，小于60的成绩分别用12345表示。将8门课程依次用ABCDEFGH表示。

（3）数据挖掘：数据挖掘过程主要是利用Apriori算法，采用广度优先的迭代搜素，设最小支持度为30%，产生频繁子集50个，从产生的频繁项目集中产生子集，根据关联规则挖掘算法原理，设置最小置信度60%，得到的关联规则15个，部分规则如表2-2所示。

表2.2

3.3 结果分析

第五条规则说明数据库原理成绩在80-90，计算机网络也在80-90的支持度为58.4%，置信度为76.5%，第六条规则说明C++程序设计在80-90分，计算机网络也在80-90的支持度为56.9%，置信度为83.4%这两个规则可信度和置信度都较高，但实际有没有关联还需要做深入的讨论。

上面第二条规则说明《计算机基础》成绩在70-80分之间，《高等数学》在80-90分之间的支持度为55.8%，置信度为87.2，虽然支持度和置信度都达到了要求，但是根据老师多年的教学经验，这两者之间并没有很强的关系，因此在实际排课中我们要实际经验联系数据做出安排。

3.4 模型改进

在上面建模过程中，在数据转换时，将成绩离散化为1-5的值，这样每一门课都会有5个不同的表示，例如A1、A2、A3、A4、A5，10门课就会有50个不同的符号来表示每一个项目。虽然之中划分对于分析没门课程之间的联系会给出更加有利和详细的证据。实际情况中，每一个专业大学四年所学课程通常都是在三四十门以上。如果仍谈按照以上的方式进行数据处理,扫描数据库中上百条记录，程序的运行效率会很低。

综上所述，为了兼顾程序的运行效率和得到确实可信的结果，当需要扫描大数据的数据库时，在数据转换时，不再将成绩划分成五个等级，而是将成绩划分为2个等级，如果成绩大于该科的平均分，则该成绩记为1，否则记为0

然后再利用matlab程序，导入内存中：Data=xlsread(‘E:ookl’)；

这样就将excel中的数据读入data中。

将数据存储到计算机内存中，当运行Apriori算法程序时，不需要每次都扫描数据库，只需扫描一次数据库文件，以后每次迭代中都只是扫描存储到计算机内存中的矩阵。加快了数据访问速度。模型改进之后，需要访问的数据量减少了一半以上，数据的访问次数也减少了很多，因此程序的运行效率会有显著的提高。这是今后在做大数据挖掘时，加快程序运行速度的一个解决办法。

4.结语

对于某些事情，凭借经验完全可以做出决策，如学校课程的安排，但是这些决策没有坚强的理论基础做支撑，有时候是很难站住脚的。但是如果我们能运用数据挖掘的有关知识，为这些经验提供理论科学依据，就会让这些经验显得更加可信。需要我们运用正确的方法，分析数据，做出决策，而数据挖掘技术就是最正确的方法。

[1]Xian jun Ni.Research of Data Mining Based on Neural Networks.北京:水利水电出版社,2003.

[2]史忠植.知识发现[M].北京:清华大学出版社,2002.

[3]张志霞,许童羽等.高等学校成绩分析方法的研究[J].沈阳农业大学学报,2008-06,10(3):322-324.

[4]杨洪伟,许童羽.Apriori算法在学生成绩分析中的应用研究[J].现代计算机(专业版),2010.

[5]李金忠.关联规则Apriori算法[J].电脑编程技巧与维护,2008(6):35-37.

[6]常朝德,代永卫等.关联规则在公安情报信息系统中的应用[J].计算机工程与应用,2008,44(5):75-78.

[7]赵辉.数据挖掘技术在学生成绩分析中的研究及应用[D].大连:大连海事大学,2007.

[8]陆楠.关联规则的挖掘及其算法的研究[D].长春:吉林大学,2007.

[9]周根贵.数据仓库与数据挖掘[M].浙江:浙江大学出版社,2004.