龙源期刊网 http://www.qikan.com.cn
数据库中关联规则挖掘研究与应用
作者：刘晓娜
来源：《电脑知识与技术·学术交流》2008年第09期
摘要：简要地介绍了关联规则，通过对关联分析的经典算法-Apriori算法的分析，发现了经典算法Apriori算法的缺陷，给出了改进的关联规则算法FARM_New算法和基于筛选压缩的Apriori挖掘算。并将其应用到教学质量评估系统中进行对比分析。 关键词：数据挖掘；关联规则；教学质量评估系统
中图分类号：TP311文献标识码：A 文章编号：1009-3044(2008)09-11580-03
Study and Application of Association Rule Mining in Database LIU Xiao-na
(Shenyang Normal University , Institute for Scientific Information Software,Shenyang 110034,China)
Abstract: This text briefly introduce association rule.By analyzing the application of classic Apriori algorithm, Apriori algorithm is found that it has some disadvantages. And then FARM_NEW algorithm and the Apriori algorithm of riddling compression those improving the association rule algorithm are proposed. They are applied to teaching quality assessment system system, and are contrast and analysis.
Key words: date mining; association rule; teaching quality assessment system 1 引言
随着数字化校园的建设，高校教学评估已经越来越受到重视，教学质量评估系统也应运而生。目前全国高校都在面临着学校招生人数不断扩大的局面，高校的管理工作、特别是教学管理工作将会变得非常繁重的复杂。因此随着教学规模的扩大，教学质量的评估得作用越来越明显，但其信息量变得十分庞大，这时利用数据挖掘技术，将针对已有海量教学信息进行有效的知识发现，为管理者提供有益的帮助。教学评估系统包括基本信息管理、学生系统、课程系统、教师管理、教学计划、成绩管理、课程评分等系统，涉及教学管理的各个环节。由于教学质量评估系统自己的特殊性，其数据挖掘采用关联规则挖掘。
龙源期刊网 http://www.qikan.com.cn
2 数据挖掘及模糊关联规则
2.1 数据挖掘
数据挖掘是20世纪80年代后期兴起的学科，指从数据中获取正确、新颖、有潜在应用价值和最终可理解模式的非平凡的过程。简单地说，数据挖掘就是从大型数据库或数据仓库中储存的大量的、不完整的、有噪声的数据中发现潜在的、有价值的、有趣知识的过程。提取的知识一般可以表示为概念、规则、规律、模式等形式。 2.2 模糊关联规则
定义1：设I={i1，i2，…，in}是由n个不同的项目组成的项目集。给定一个数据库D，其中的每一个记录T是I中一组项目集合(T是I的数据项子集)，即T?I，T有一个唯一的标识符TID。若集合X?I且X?T，则称记录T包含集合X。
定义2：设R={rl，r2，…，rk}是由k个不同的模糊区间组成的集合。若A={al，a2，…，ap}?R，则称A为R中一组模糊区间。
定义3：uA(X)=Λuaj(xi)表示集合X对区间A的隶属程度，其中每一个xj在A中都有唯一的aj与之相对应，uaj(xi)表示属性值xi对区间aj的隶属程度。
定义4：一条模糊关联规则就是形如X_A?Y_B的蕴涵式，其中X?I，Y?I，X∩Y=Φ，A?R，B?R，ai、bj分别是xi、yj对应的模糊区间。
3 经典模糊关联规则算法及改进算法
3.1 经典算法——Apriori算法
Apriori算法的基本思想是首先找出所有的频繁项集，这些项集出现的频繁性至少和预定义的最小支持度一样。然后由频繁项集产生强关联规则，这些规则必须满足最小支持度和最小可信度。
Apriori算法的性质是频繁项集的所有非空子集必定是频繁的，或者说非频繁项集的所有超集必定是非频繁的。即若存在项集I不是频繁的，满足P(I)
龙源期刊网 http://www.qikan.com.cn
产生频繁项集的过程主要分为连接和剪枝两步：
连接步骤：为了发现Lk，可以将Lk-1中两个项集相连接以获得一个Lk的候选集合Ck。设l1和l2为Lk-1中的两个项集（元素），记号li[j]表示li中的第j个项。为方便起见，假设交易数据库中各交易记录中各项均已按字典排序。若Lk-1的连接操作记为Lk-1Lk-1，它表示若l1和l2中的前(k－2)项是相同的，则Lk-1中l1和l2的内容就可以连接到一起。 剪枝步骤：Ck是Lk的一个超集，其中的各元素（项集）不一定都是频繁项集，但所有的频繁k_项集一定都在Ck中，即有Lk?Ck。扫描一遍数据库就可以决定Ck中每个候选项集（元素）的支持频度，并由此获得Lk中各个元素（频繁k_项集）。所有频度不小于最小支持度的候选项集就是属于Lk的频繁项集。然而由于Ck中的候选项集很多，如此操作所涉及的计算量（运算时间）是非常大的，为了减少Ck的大小，就需要利用Apriori性质，因而也就可以将其从中删去。Apriori算法有些缺陷，如它需要对事物数据库进行多次扫描，这就对I/O的负载能力提出了一定的要求；并且这种算法可能产上庞大的候选集，这就对时间和内存存储空间是一种挑战。
3.2 Apriori算法的改进算法——FARM_New算法
此改进算法是由Srikant、Hong、程继华等提出的，FARM_New算法主要步骤如下： (1)按照预定义的分类方法，将祖先加到相应的事务结点之上。
(2)扫描数据库D，产生候选项集，如果项的出现次数≥min_sup，该项集成为频繁项集。首先产生频繁1-项集，然后产生候选2-项集，这个过程直至产生所有的频繁项集时结束。 (3)引入在第2阶段产生的所有可能的关联规则。计算这些规则的置信度，如果满足置信度阈值，则将其保留，否则予以删除。
(4)通过以下3个阈值条件筛选，将不符合兴趣度条件的关联规则移去，将符合条件的兴趣规则输出：这条规则的父规则没有满足条件（在预定义的分类规则中用该项的父结点替换该项得到）；必须满足最小支持度阈值；必须满足最小置信度阈值。
FARM_New算法相对于Apriori算法的一些缺陷有所改进。采用模式的支持事务集合的比较方法代替了Apriori算法的模式匹配，节约了存储模糊项集和模糊频繁项集的内存占用，从而提高了挖掘算法的性能；对非终点项进行处理，从而提高了挖掘规则的精确性；算法所构造的频繁模糊模式，是由预定义在属性上的模糊概念组成，使得交叉层的关联规则挖掘可以很容易地从上述范围内找到。
3.3 Apriori算法的改进算法——基于筛选压缩的Apriori算法