黄毅杰，张艺雪

(1.漳州职业技术学院 计算机工程系，福建 漳州363000；2.漳州卫生职业学院 信息技术部，福建 漳州363000)

关联规则是数据挖掘技术的主要研究方向之一.1994年, Agrawal等人提出了关联规则挖掘的经典算法Apriori[1].Apriori算法利用层次循环顺序搜索的方法来挖掘频繁项集，但该算法需要多次扫描数据库并产生了大量的候选项集[2].

本文提出了一种基于矩阵的关联规则算法，通过向量矩阵来表示事务数据库，减少了扫描数据库的次数，通过矩阵的运算快速生成k-项集.

1 关联规则基本概念

假设项的集合为I={i1，i2，…，im}，在I中包含了m个不同的数据项.在给定的数据库D中，所有的事务都包含在D中，T表示D中的每条事务，T是I中项的集合，使得T⊆I.每条事务T有唯一的TID标识.关联规则如同A⟹B蕴涵式，其中，A⊂I,B⊂I，且A∩B=ø.设A是I的子集，A的支持度S(A)是指D中出现A的概率，如果S(A)≥最小支持度(min_sup)，则称A为频繁项集.蕴涵式A⟹B具有支持度S(A⟹B)，其支持度是指A和B在D中同时发生的概率，即S(A⟹B)=P(A∪B)[3].

关联规则的支持度和可信度分别体现出了规则发生的频度和强度.

在事务数据库D中找出同时满足最小可信度(min_sup)和最小可信度(min_conf)是关联分析的最终目的[4].

2 Apriori算法思想

Apriori算法的实现可分为两步：

第一步是发现事务数据库D中的所有支持度大于最小支持度的项集，这个工作是关联规则的关键所在，具有较大的计算量，也是衡量算法性能的关键.

第二步是根据第一步识别出的频繁项集提取出关联规则[5].

Apriori算法的流程图如图1所示：

图1 Apriori算法的流程图

从Apriori算法的流程图中可以看出，Apriori算法需要多次反复扫描数据库，产生较大的I/O消耗，在k=2的时候会产生大量的候选项集，特别是在挖掘较大型的数据库关联规则时，使得效率降低.

3 基于矩阵的关联规则算法

算法的改进思想是通过把事务数据库转换为向量矩阵减少扫描数据库次数，在K=2时，采用转化后的矩阵乘以其转置矩阵的方法得到较少的候选项集，提高效率.算法步骤如下：

(1)转换矩阵：扫描一遍数据库，把事务数据库D转换为向量矩阵Am×n，矩阵的行代表D中的每条事务，矩阵的列代表D中数据项，其中，

(2)生成频繁1-项目集：按顺序求各列向量的数量积，在结果中统计1的数量，这个数量值即项目I的支持度计数support_count(Ij)，如果support_count(Ij)/n>最小支持度(min_sup),则Ij项的组合为频繁1-项目集，否则Ij为非频繁1-项目集，删除该项所在的列，按照支持度计数由小到大排序，生成矩阵D1.

(3)生成频繁2-项目集：通过D1乘以D1的转置矩阵得到S，如果S矩阵右上角的数据Sij>min_sup，则Sij项的组合为频繁2-项目集[6]，对满足min_sup的Sij的数据修改为“1”，其余改为“0”，生成矩阵D2.

(4)裁剪矩阵，产生k-项集：实际上往往L中的有些频繁(k-1)-项目集已经对Lk-1的生成没有作用，计算Lk-1各个项目出现的频度，如果其中有项目的频度小于k-1，则删除该项目所在的项目集，以此减少产生不必要的候选项集.通过对Lk-1的连接和剪枝，产生频繁k-项集.

4 实验分析

事务数据库如表1所示，设定最小支持度计数2，

表1 事务数据库

表2 矩阵D1

对各个项集进行支持度计数，每个项集都满足最小支持度，生成矩阵D1，如表2所示.其中L1为{I1:2,I2:3,I3:4,I4:2,}

通过D1乘以D1的转置矩阵得到S，其中L2为{I2I3:3,I2I4:2,I3I4:2}

通过L2连接得到L3为{I2I3I4}，由L3可知不会产生频繁4-项集，算法停止.

5 算法性能分析

本文提出的算法把事务数据库转换为向量矩阵，不再扫描原始的事务数据库，向量矩阵只存储0和1数据，大大减少了占用的空间，特别是在大数据集上更能体现其运算效率.图2为本文算法与Apriori算法在测试事务数据库，在最小支持度设为2%，事务从500到8 500的增加过程中的算法的执行时间比较结果.从图中可以看出，随着事务的增加，本文提出的算法的运行时间优势更为明显.

图2 算法比较

6 在教学评价模块上的应用

学生对教师的教学评价可以体现出该教师在教学过程中给学生留下印象的好坏，体现出该教师的教学效果等，通过关联分析学生对教师的教学评价，挖掘出教学质量与教师的一些性质的关联规则对高校的师资引进、师资建设、师资配置的决策起到重要作用.

学生评价表主要包含了教学态度、教学水平、教学方法、教学效果等四个一级指标，总的包含16个二级指标.教师任课班级的学生对18个二级指标进行评分，取其平均分并用五级制来体现学生评价的最终结果.

本文的数据来源于某高职教学管理系统数据库，并通过一定方式去除了一些异常信息，如有些学生的评价分全为0，有些学生的评价时间只有几秒钟等.

本文的挖掘对象主要在教师的职称、学历、任职时间、性别和评价得分等级，其中职称包含助教、讲师、副教授、教授，项目用{I1，I2，I3，I4}表示；学历包含本科、硕士、博士，项目用{I5，I6，I7}表示；任教时间包含<5年、6～10年、11～15年、>16年，项目用{I8，I9，I10，I11}表示；性别包含男、女，项目用{I12，I13}表示；评价得分等级包含优、良、中、合格、不合格，项目用{I14，I15，I16，I17，I18}表示.通过项目表示教师信息如表3所示.

表3 项目信息表

根据本文提出的算法，将事务数据库转换为向量矩阵，如表4所示.

表4 转换后的矩阵

运用本文提出的算法对转换后的矩阵进行挖掘，设最小支持度为15%，最小可信度为50%，得到以下典型关联规则，如表5所示.

表5 典型关联规则

由上表可以看出，如第1条关联规则中表示，在数据库中，有26.8%的记录为讲师，硕士，任职时间11～15年的，在这26.8%的记录中，有53.3%的评价等级为优秀；在第二条关联规则中表示，在数据库中，有32.6%的记录为助教，硕士，任职时间<5年的，在这32.6%的记录中，有91.3%的评价等级为中.

通过这些关联规则可以看出学历、职称层次较高和任职时间较长的教师的评价等级都比较高，为了提高高校教师教学效果，应鼓励青年教师提高学历层次，通过“老带新”的方式，提高高校教师的教学水平.

7 结束语

本文介绍了数据挖掘中关联规则的概念和Apriori算法的基本思想，提出了一种基于矩阵的关联规则算法，并运用该算法于高校教学评价系统中，通过对学生评价结果进行关联规则的挖掘，可以对学校进一步提高教学效果起到客观的参考作用.

参考文献：

[1]Jaeger T,Sailer R,Shankar U.PRIMA:Policy-reduced Integrity Measurement Architecture[C]//Proc.of the 11th ACM Symposium on Access Control Models and Technologies.Lake Tahoe,USA:[s.n.],2006:19-28.

[2]刘星沙，谭利球，熊拥军.关联规则挖掘算法及其应用研究[J].计算机工程与科学，2007(10):13-16.

[3]廖琴，郝志峰，陈志宏.数据挖掘与数学建模[M].北京：国防工业出版社，2010:74-75.

[4]刘独玉,杨晋浩,钟守铭.关联规则挖掘研究综述[J].成都大学学报,2006,25(1):54-58.

[5]HAN Jia-wei，KAMBER M.数据挖掘概念与技术[M].范明，孟小峰，等译.北京:机械工业出版社,2001:149-179.

[6]黄龙军，段龙镇，章志明.一种基于上三角项集矩阵的频繁项集挖掘算法[J].计算机应用研究,2006(11):25-26,40.