改进的关联规则挖掘算法及其在课程设置中的应用

杨强

长江大学计算机科学学院 湖北荆州 434023

作者：杨强，长江大学计算机科学学院讲师。

随着基于校园网络教学管理系统中学生成绩信息的急剧增长，直接根据学生的成绩数据分布找出前期课程与后继课程的关系、课程教授效果等，并据此进行教学进程的决策是十分困难的。因此必须借助于相应的数据挖掘工具，发现数据中隐藏的课程相关规律或模式，为决策提供支持。

1 关联规则挖掘算法

1.1 算法描述

关联规则的概念首先由R.Agrowal等人提出，是描述数据库中数据项（属性、变量）之间所存在的（潜在）关系的规则，目前已成为数据挖掘中非常重要的一个研究方向。

发现关联规则要经过4个步骤：1）预处理与挖掘任务有关的数据。根据具体问题的要求对数据库进行相应的操作，从而构成规格化的数据库D；2）针对D，求出所有满足最小支持度的项集，即大项集，由于一般情况下所面临的数据库都比较大，所以此步是算法的核心；3）生成满足最小置信度的规则，形成规则集R；4）解释并输出R。

经典关联规则挖掘算法Apriori，它是一种找频繁项集的基本算法。算法的核心主要在寻找频繁项目集上，主要是基于Apriori性质：频繁项集的所有非空子集都必须也是频繁的。利用这个性质可以有效地压缩搜索空间。算法主要思路：为找Lk，通过Lk-1与自己连接产生候选k项集的集合，该候选项的集合记作Ck；依次下去直到Ck+1为空。在产生Ck（k＝1,2,…,k）时，利用剪枝策略压缩Ck。利用任何非频繁的(k-1)项集都不可能是频繁k项集这一Apriori性质，删去那些(k-1)子集不在Lk-1中的k候选项目集。

Apriori过多次扫描数据库D来发现所有频繁项集。存在2个问题：1）算法必须多次扫描事务数据库，对候选项目集进行模式匹配；2）算法必须花大量的时间进行连接操作及处理候选项目集。这2个问题是当前关联规则挖掘的热点和难点。也是约束系统性能的瓶颈。

1.2 算法改进

针对以上2个问题，可以对Apriori算法做下面的改进。

1）首先，扫描事务数据库，同时记录包含该项的事务标识符TID，产生1（项候选集C1）。C1的结构为：项集Item—set，支持计数Support，事务标识符列表Tid—list。然后从C1中删除不满足最小支持度阈值的项集，则C1中的项集集合即是频繁1（项集L1）。

2）Lk-1与Lk-1连接，生成Ck。其中Ck事务

标识符列表等于生成它的2个Lk-1的事务标识符列表的交集。对Ck的计数不需扫描事务数据库，只需计算Ck中事务标识符列表中的TID个数即可。

1.3 算法描述

输入：事务数据库D；最小支持度阀值min_sup。输出：D中的频繁项集L。见框1。

2 算法在课程相关性分析中的应用

2.1 算法应用

设I是由m门课程组成的集合，给定一个数据库D为学生成绩库记录的集合，其中的每一个记录T是I中一组属性的集合，即Tgl，T有一个唯一的标识符TID。

根据上述对算法改进的思想，候选集的结构中包含一个事物标识符列表，该列的长度是不确定的，因此在关系数据库中不容易实现。为此，在算法的实现做了如下调整：在候选集表中，每一个＜项集，事务标识符＞作为一个记录，这样候选集中的一个项集对应多条记录。学生课程成绩表的部分数据字段如表1所列，该表中的部分数据如表2所列。

表1 学生课程成绩表部分字段

表2 学生课程成绩部分数据表

表3 候选项集

2.2 挖掘结果

本实例是对某校计算机学院的学生成绩进行分析，首先是对各不同专业的学生成绩进行分析，得到专业内各课程之间的相关信息。由于各专业各学科存在交叉性，可以利用改进后的关联规则进行综合分析，得到学院内课程之间的相关性分析。通过对学生成绩数据库挖掘后，得出课程关联规则（如表4所示）：规则1表明，离散数学作为石油地质基础的先行课程的支持度是3.97%，信任度是72.84%。因此加强离散数学的学习有助于数据结构的学习。其他规则同样可按这种方式分析。

对表2中的数据进行处理，得到的候选项集如表3所列。然后从候选集表中统计每个项集的计数，插入频繁项集表中。同时，将候选集中的非频繁项集删除，以便于生成下一级候选集。

表4 挖掘结果部分实例

3 结论

通过改进后的Apriori算法对教育信息数据库进行数据挖掘，产生的规则对学校的课程安排、学生的素质教育以及教学模式等方面提供了有价值的参考。所以决策者可以通过合理安排相关课程的开课顺序、加强前期课程的教学时间和师资配备来改善后续课程的教学效果，从而为制定合理、最优的教学计划和人才培养方案提供帮助。

[1]Agrawal R, Imielinski T, Swami A. Mining Association Rules between Sets of Items in Large Databases[A].ACM SIGMOD Conference,1993

[2]Agrawal R, Srikant R. Fast Algorithms for Mining Association Rules in Large Database[A].VLDB:1994

[3]安颖.一种改进的Apriori挖掘关联规则算法[J].软件导刊,2008(10)

[4]曲春锦.改进的关联规则挖掘算法及其在教育信息挖掘中的应用[J].交通与计算机,2005(4)