Apriori算法在教育领域的应用

1、成 绩评卷人姓 名学 号 华 中 师 范 大 学研 究 生 课 程 论 文完成时间 2014.7.15 课程名称 数据挖掘 专 业 通信与信息系统 年 级 Aprior-TIDS算法在教育领域的应用摘 要：数据挖掘技术是应用一系列技术从大型数据库中提取出出隐含的、以前未知的、具有潜在应用价值的信息,它是知识发现（KDD）过程中最核心的部分。而关联规则的挖掘是数据挖掘的一项重要的任务,用以发现大量数据项集之间的相关联系。Apriori 算法在关联规则挖掘中最具代表与影响的一种算法。针对它需要重复的扫描数据库以确定各个候选项集的支持度计数和产生大量候选项集的缺陷，设计出了新的算法Aprior-TI

2、D（Sransaction Identifier)算法。本文还将探讨这个算法落实到教育相关领域上的两个具体应用-教育管理决策系统和招生管理系统。关键字：Aprior-TIDS；数据挖掘；教育决策；招生管理；关联规则；1.知识发现与数据挖掘1.1知识发现相关概念自从 1989 年 8 月在第 11 届国际联合人工会议上首次提出知识发现这一概念以来，研究者们给 KDD 下了很多定义。随着 KDD 研究的不断深入，对 KDD 的定义也在不断地改进，以下是目前对 KDD 比较公认定义： KDD 是从大量繁多的数据中提取出可信的、新颖的、有效的并能被人理解的模式的处理过程，这种处理过程是非平凡的过程1。

3、KDD 是一个多步骤的过程，并且根据实际需要这些步骤可能要多次反复，其主要步骤如图 1-1 所示： 1.准备：了解 KDD 相关领域的有关情况，熟悉有关的背景知识并了解用户需求。 2.筛选：从用户需求出发由数据库中提取出于本次 KDD 过程相关的数据，此过程主要是对数据库中的原始资源进行提取。 3.预处理：初步处理上一步所选择出的数据，包括对数据的完整性与一致性进行检查，对数据中出现的噪声进行判断并加以去除，对错误和丢失的数据进行修补。 4.缩减：对经过预处理数据的数据项，主要通过投影的方式或一些相关的数据库操作减少数据量。 5.任务定性：根据用户需求确定 KDD 的结果属于哪类知识，这是作为

4、选择知识发现算法的依据。 6.确定算法：根据上一步所得结果选择适合的算法、模型和参数。 7.数据挖掘：利用所选算法，从经过初步处理的数据中提取出用户所需的知识。要求其结果要简单易懂，一般都是一些常用的表达式或产生式。 8.模式解释：对发现的模式进行解释。 9.评价：将发现的数据以用户易于理解的方式呈现，也包含对知识一致性的检查。图1-1KDD过程从上述对 KDD 过程的描述可以得出结论：数据挖掘只是知识发现过程中的一个步骤，但它是知识发现过程中最重要的一个步骤。它主要是利用知识发现算法，从数据中发现出有关的知识或模式。1.2数据挖掘的相关概念。数据挖掘(Data mining,简称 DM)，就

5、是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。数据挖掘过程一般由确定挖掘对象、数据准备、模型建立、数据挖掘、结果分析表述和挖掘应用这几个主要阶段组成。数据挖掘可以描述为这几个阶段的反复过程2。首先确定目标、明确数据挖掘任务。（1）数据准备数据准备阶段又可进一步分成四个子步骤数据集成、数据选择、数据预处理和数据转换。A、数据集成。数据集成是将多文件或多数据库运行环境中的数据进行合并处理,解决语义模糊性,处理数据中的遗漏和清洗数据等。B、数据选择。数据选择指为数据挖掘目标搜集和选择有关的数据,这包括不同格式数据的

6、转换以及不同部门数据的统一和汇总。数据选择的目的是辨别出需要分析的数据集和,缩小处理范围,提高数据挖掘的质量。C、数据预处理。数据预处理是对数据进行清理和充实等工作。数据库中重要的数据是准确的,不重要的数据可能存在污染。预处理就是为了克服目前数据挖掘工具的局限性。D、数据转换。数据转换的一个重要工作就是对数据进行编码。数据库中字段属性的不同取值转换成数码形式经有利于搜索。（2）数据挖掘这个阶段将进行实际的挖掘操作,即利用机器学习、统计分析等方法,从数据库中发现有用的模式或知识这里模式是浓缩数据的信息形式,如精炼数据库、表格、产生式规则、决策树、神经网络的权值等。A、选择数据挖掘方法。如统计分析

7、、机器学习、模式识别方法和人工神经元方法等。B、选择数据挖掘算法。选择用来查找模式或符合数据的模型的算法,确定合适的模型和参数。另外,数据挖掘方法必须和目标相匹配。C、数据挖掘。查找感兴趣的模式。模式一般表示为一种特殊的形式或一套表达方式,如关联规则,分类规则或分类树,回归结构和聚类集等。除了选择合适的挖掘算法外,其余的一切工作都可自动完成。（3）数据挖掘结果分析表述和挖掘应用A、结果表达。尽量直观的表示挖掘结果,便于用户理解和使用,可利用可视化方法表示为图表等形式。B、结果评价。筛选和评价挖掘结果中的有用部分,查找可接受的结果。可定义兴趣指标,考虑结果的正确度、新颖度、有用性和简单性。把信息

8、从输出中过滤出来。利用可视化方法帮助用户决定所提取知识的有效性或对基本的数据或现象做出结论。C、知识巩固。把挖掘出的信息结合到执行系统中,了解这些信息的作用或证明这些信息。用预先知道且可信的信息来检查和验证所挖掘的信息,解决可能存在的矛盾。2.关联规则挖掘算法Apriori-TIDS2.1关联规则挖掘2.1.1定义关联规则挖掘是数据挖掘中一个最重要的过程，用以发现大量数据的项集间的一些内在的关联或相关联系。盎格鲁等人于 1993 年首先提出关联规则的概念，随后大量的研究人员对关联规则的的挖掘问题进行了详细的研究。现在关于关联挖掘定义的版本比较多，由 Jiawei Han、Micheline k

9、amber3等人给出的定义形式如下： 设 I=i1, i2, im是项集，D 是事务的集合，其中每个事务 T 是项的集合，T I。设 X 为一个项集， X I，而事务 T 包含 X 当且仅当 X T。则关联规则是一个形如X=>Y 的蕴含式，其中 X I，Y I，且 X Y =。那么关联规则的兴趣度可用支持度和置信度来衡量。支持度：P( )，即 X 项集和 Y 项集在事务集 D 中同时出现的概率。置信度：P(Y|X)，即在出现项集 X 的事务集合 D 中，项集 Y 也同时出现的概率。2.1.2分类管理规则根据涉及内容不同可有不同分类： 1.数值型与布尔型关联规则： 以关联规则中处理变化量的

10、类别不同进行分类。数值型的关联规则可以直接对原始的数据进行处理，或者和多维的关联规则或多层的关联规则相结合起来，对数值型的数据字段进行处理，将其进行动态的分割。布尔型关联规则处理的数据都是离散型的种类化的，方便显示变量间的关系。例如：电阻=(200250)=>额定工作电流=(15A25A)是一个量化的关联规则；而年级=“2005 届”=>专业=“软件工程”即为布尔型。 2.单维和多维关联规则： 以关联规则中数据涉及的维数不同进行分类。单维关联规则只涉及到数据的单维度。例如顾客购买的商品，牛奶=>纸巾，只涉及到用户购买的商品；而多维关联规则涉及到两个或两个以上的谓词，如：电阻(

11、200250)工作电流(<=25A)=>完全等级(A)中，包含了三个不同的谓词(“电阻”、“电流”和“安全等级”)，这种规则即称之为维间关联规则。在某一规则中包含的某些谓词重复出现，我们称其为混合维间关联规则。如：灯泡=>电阻(200250)工作电流(<=25A)=>完全等级(A) 3.单层和多层关联规则： 以关联规则中数据抽象的层次不同进行分类。单层关联规则中所有的变量都不考虑它在现实生活中数据的不同层次，而多层关联规则要对数据的变量多层次充分考虑。对于许多应用，在较低的数据层次很难找到强相关规则，而在较高的层次所发现的强相关规则可能具有比较普遍的意义。2.2

12、Apriori算法Apriori 算法作为在关联规则挖掘中最具代表与影响的一种算法。Apriori 算法核心思想是基于数据概率的挖掘数据布尔型关联规则项集，对据库中项目或事物之间的关系通过循序渐进的方式挖掘数据，对用户提出有价值的规则或指导意见。该算法的过程主要由两步构成，连接(类矩阵运算)和剪枝(去掉无意义或没有必要的中间结果)。在此算法中频繁的应用到项集这个概念。4 其具体的执行步骤如下： 1.根据用户的要求制定出最小支持度和最小置信度。 2.找出所有的频繁项集。首先由原始的数据库资料产生出物象集合，该集合称为候选集。如果某一个候选集的支持度大于最小支持度，则认为它属于频繁项集合中的项，从

13、而通过多次扫描产生出频繁项集。3.在该算法的执行的过程中，先由数据库读入所有的数据项，得出一个候选 1-项集合 C1(Candidate 1-itemset)的支持度，然后找出频繁项集 1-项的集合 L1(Large 1-itemset),并利用这些频繁 1-项集的结合与 2-项集合。 4.继续对数据库扫描，得出候选 2-项集 C2的支持度，找出 2-项集合 L2，利用这些频繁 2-项集合 L2的结合，产生候选 3-项集合 C3。 5.继续执行上述的步骤，重复对数据库的扫描、并和最小支持度进行比较，产生更高层次的频繁项集合，进行数据的优化。重复进行此操作步骤，直到不再结合产生新的候选频繁项集为

14、止。连接：为了找到频繁项集合 Lk，需要连接 Lk-1与自己产生连接候选项集 k-项集的集合。该候选频繁项项集合记做 Ck。设 l1和 l2是 Lk-1中的项集。记 lij表示 li的第 j 项。执行连接过程 Lk-1Lk-1,其中要求 Lk-1的元素 l1和 l2可以连接的，如果：(111= 121)(112= 122) (11k-2= 12k-2) (11k-1< 12k-1)，连接 11和12产生的结果项集是 111 12211k-1 12k-1。记号 lij表示 1i的第 j项。剪枝:扫描数据库，确定 Ck中每个候选项集的支持度计数。但是，候选集 Ck可能很大，为压缩 Ck，可以

15、利用以上法性质:任何非频繁项集合的(k-1)项集都不可能是频繁项集合 k项集的子集。所以，如果一个候选 k项集的(k-1) 项子集不在 Lk-1中，则该候选也不可能是频繁的，因此，从 Ck中删去。Apriori 算法为了生成所有的频繁集必须重复的扫描数据库并不断地进行连接和剪枝操作，为此在实现时主要是利用了递推的结构实现该算法：(1) L1= lareg 1-itemsets; (2) for (k=2; Lk-1&sut1; k+) do begin (3) Ck=apriori-gen(Lk-1); /新的候选集 (4) for all tranfsactions t&Ic

16、irc;D do begin (5) Ct=subset(Ck,t); /事务 t 中包含的候选集 (6) for all candidates c&Icirc; Ct=do (7) c.count+; (8) end (9) Lk=c&Icirc; Ck |c.count&sup;minsup (10) end (11) Answer=kLk; 第一步先产生频繁 1-项集 L1，然后是频繁 2-项集 L2，直到有某个 i 值使得 Li为空，这时算法停止。这里在第 k 次循环中，过程先产生候选 k-项集的集合 Ck，Ck中的每一个项集是对两个只有一个项不同的属于 Lk-

17、1的频集做一个(k-2)-连接来产生的。Ck中的项集是用来产生频集的候选集，最后的频集 Lk必须是 Ck的一个子集。Ck中的每个元素需在交易数据库中进行验证来决定其是否加入 Lk，这里的验证过程是算法性能的一个瓶颈。这个方法要求多次扫描可能很大的数据库，即如果频集最多包含 100 个项，那么就需要扫描交易数据库 100 遍，这需要很大的 I/O 负载。通过上述的描述可以看出，Apriori 算法存在着两个主要的缺陷： 1需要重复的扫描数据库以确定各个候选项集的支持度计数。 2需要产生大量候选项集。 这两个主要的缺陷(特别是第一个)成为了该算法的瓶颈，目前大多数对于该算法的改进基本都是针对于改进

18、这两个缺陷来进行的。2.3 Apriori算法的改进Apriori-TIDS算法随着待处理数据量的日益增多，Apriori 算法的缺陷渐渐突出，越来越难以适应用户的需求，为此许多研究学者以该算法为原型，就如何能减少扫描的次数和在系统内存一定的条件下减少读取原始数据库的次数上进行了大量的研究和实践。通过对 Apriori 算法及其改进算法的分析比较，针对原始算法需要多次重复扫描数据库以确定各个候选项集的支持度计数的缺陷进行改进，提出了一种新的算法Apriori-TID(Transaction Identifier)算法。5该算法的执行步骤如下： 1.扫描数据库，对包含每一个项集的事务进行支持度计

19、数，从而产生 l-项候选集C1。其中 C1的结构为：项集的名称 Item_set,事务标识符列表 Tid_list，支持度计数Support。从项集 C1中删除支持度计数小于最小支持度阈值的项，从而得到频繁 1-项集 L1。2.Lk-1自身进行连接操作，生成 k-项集 Ck。Ck的事务标识符列表为两个生成它的 Lk-1的事务标识符的交集。计算 Ck中项集的标识符列表中 TID 的数量，得到 Ck中每一个项集的计数。下面我们通过一个定理来证明该算法的正确性。定 理：对于一个 K-项集 L,设包含有 L1，L2，Lk-2，Lk-1的事务集合为 A，包含 L1L2Lk-1Lk的事务集合为 B，则有包

20、含 L 的事务集合是集合 A 和 B 的交集，即 AB。下面通过该定理证明 Apriori_TID 算法。 证明： (1)设 t 是 AB 中的任意一个事务。ABA tAA是包含有 L1L2Lk-2Lk-1的事务集 t 包含有 L1L2Lk-2Lk-1 AB B tBB 是包含有 L1L2Lk-1Lk的事务集 t 包含有 L1L2Lk-1Lk综上可得： t 包含了项集 L。 由此得证，AB 中的任意事务均包含项集 L。 (2)假设事务 t！AB，但 t 包含项集 L L1L2Lk-2Lk-1是项集 L 的子集 t 包含项集 L1L2Lk-2Lk-1而由题设可知，包含 L1L2Lk-2Lk-1的

21、事务都包含在集合 T1中 tT1同理 tT2由此可得 tAB 与假设矛盾 综上题设得证。 若 l1,l2是 Lk-1中两个可连接的项集。L1= L1L2Lk-2Lk-1,l2= L1L2Lk-1Lk,l=l1l2= L1L2Lk-1LkLk。 综上可知，包含 l 的事务集必然包含事务集 l1与 l2的交集。由此可得l.Tid_list=l1.Tid_lil2.Tid_list。由该式我们可以知道若要求的某一个事务集 l的 TID 列表，只需要求生成它的两个事务集 l1和 l2的 TID 属性列进行求交集的运算即可。 (3)此时，剩余的 Lk 中的项集均是满足最小支持度阈值的项集，所以Lk=Lk

22、.ItemSet。改进算法可描述如下：输入项：待挖掘的事务数据库 D；根据用户需求所订立的最小支持度阈值 min_sup 结果：D 中满足最小支持度阈值的所有频繁项集合 L。3.Apriori-TIDS算法在教育领域的应用3.1教育管理决策系统随着高校招生规模的不断扩大和信息技术的不断发展，各个高校都建立了自己的教务管理信息系统，这些系统大大提高了教学和管理的水平，同时也积累了大量的教学和管理数据。与其他资源相比，教育信息资源是无形的潜在的，但它对教育发展具有直接的、其他资源难以替代的作用。6教育信息挖掘对教育管理决策的辅助作用主要体现在以下几个方面： 合理设置课程 高校的好多课程之间都具有一

23、定的衔接性，先行课程学的好坏会直接影响后续课程的学习。利用数据挖掘技术，对学生的以往成绩进行挖掘，就能发现课程之间的关联，并以此为依据，对课程设置做出合理的调整。 改善教学模式 由于授课教师的授课方式和教学水平的差异，学生的成绩也会有所差别。通过数据挖掘，可以发现教师学历、职称、授课方式等同教学效果之间的联系，从而有针对性的改善教学模式，提高教学质量。 此外，数据挖掘技术在高校教学管理决策中的应用还有毕业生就业分析、课程成绩预测、试卷分析以及高校教学评估等，这些应用都会对高校的教学管理发挥积极地作用。3.1.1 系统总体构架ARMEMD 系统即教育管理决策中的关联规则挖掘系统：图3.1系统架构

24、1 将原始的数据经过初步的处理后，将其加载至基本数据库中。一般原始的数据文件都以多种形式存在于多种媒体介质中，为了能够统一的处理这些数据，我们就需要将这些数据进行集成，并用统一的格式进行数据的格式化，然后在加载至 ORACLE 数据库中。并对原始数据进行初步的清理，把数据库中一些错误或无用的噪声去掉。 2转换原始的数据库资料成为适应关联规则挖掘。 在进行基本数据库设计时，要考虑如下问题：（1）数据的原始形式（2）本数据挖掘系统的挖掘过程是否在该数据库中的结构适用（3）本系统以及其他系统的接口问题。因此，原始数据在初步加载完以后，需要对其进行结构上的转换，以便于利用挖掘系统对其进行数据的处理。

25、3利用改进的关联规则挖掘算法进行挖掘，得出用户感兴趣的规则信息。 将新的改进算法用 ORACLE 语言编写成数据库挖掘过程，对数据库中的信息进行关联规则的挖掘，并将其结果存放于一个规则库中的各个属性表中用以查询。制作一个可视化的人机交互界面来对挖掘参数来进行设定和调节(主要包括最小支持度阈值和最小置信度值)。 4最后为了能让用户获得跟直观的结果信息，将产生的关联规则通过一种可视化界面显示出来。3.1.2挖掘主题设计在教育决策系统设计中主要设计了五个主题：（1）课程关联（2）课程类别关联（3）学生基本信息关联（4）课程（5）基本信息关联和教学模式关联。3.1.3挖掘效果将新算法应用于教学管理系统

26、中，开发出具有专家功能的教育管理决策的关联规则挖掘系统。通过几个相关主题的设定，对现行的大学管理提出许多有价值的决策信息。该规则结果的展示方面，采用了一种文本和图形相结合的可视化方式，从而可以让用户更直观的看到挖掘的结果，同时通过该界面让用户对自己所感兴趣的规则进行筛选，提高了系统的智能性，使得挖掘结果更加符合用户的感兴趣程度。3.2招生管理系统近几年在参加高考生源人数急剧下降和本科院校的扩招双重影响下，高职院校招生工作日益艰难。传统的招生方式很多凭着优先的经验进行，没有针对性，不能有效节约招生宣传成本。因此，摆在高职院校面前的重要课题是如何利用本学校已有的招生资源信息来促使高职院校在每年的招

27、生宣传、提高考生报到率等方面做出正确的决策本文采用改进的关联规则算法Apriori算法对某高职院校招生系统的历史数据进行了挖掘，找出影响高职院校招生的潜在因素和规则，用来指导高职院校招生工作。73.2.1招生管理模型通过对数据挖掘的过程分析建立了招生管理模型。招生管理模型首先对往届录取新生信息和新生录取信息提取相关数据进行预处理，然后经过关联规则挖掘找出影响往届学生报到和新生报到的影响因素，最后为招生录取提供录取管理方案和辅助决策。招生管理模型的输入数据是考生的录取信息表和考生的报到信息表，输出数据是影响新生报到的关联因素，核心的功能是对招生数据关联规则的挖掘。招生管理模型如图3-2所示。图3

28、-2招生管理模型3.2.2招生管理模型实现高职院校新生录取信息数据挖掘模块采用delphi6为开发工具，后台数据库采用SQL Server2005，设计功能界面如图 5-2 所示。该模块可以从 SQL Server2005 数据库中按年份提取新生报到的信息，经过属性选择和概化出来，然后设置支持度和置信度相关参数，通过系统内部实现改进的 Apriori算法，分析出影响新生报到的主要因素和一般规律。该模块选择从招生的信息中选择影响入学的考生类别、性别等属性，并对所选属性进行概化处理，作为关联规则挖掘的数据源。同时，设置设置支持度和置信度有关参数挖掘出影响考生入学的关联规则。3.2.3关联规则挖掘过

29、程1数据来源 本系统采集数据来源于 JD 学院 2013 年考生信息。JD 学院的考生数据库采用 SQL Server 2005，招生管理系数据库中设计考生信息的有以下几张表： (1)考生基本信息表 ksinfo，该表保存考生的考号、姓名、性别等基本信息。 (2)考生成绩表 kscj，该表存储考生高考的各科成绩。 (3)考生生源表 kssy，存储考生生源地，包括考生的户籍信息。 (4)考生报到表 ksbd，主要记录考生报到的信息。 (5)考生科类代码表 kskldm，主要记录学生文史类还是理工类。 (6)考生专业表 kszyb，说明考生录取专业类别。 各个表与考生基本信息表 ksinfo 主键

30、 ksbh进行连接，通过在 SQL Sever2005 中建立视图 v_ksxx 得到数据挖掘的原始表，作为数据挖掘的数据源，部分数据显示如图 5-3所示。2属性选择 由于该系统数据挖掘目标是为学校的招生策略提高依据，挖掘出学生报考本校的相关规则。因此在考生的数据中和学生紧密相关的一些属性比如姓名、学生考号、身份证号、联系电话中信息与数据挖掘的目的无关。本文选择“考生类别”、 “科类”、“报考专业”、“成绩”、“科类”、“报到”六个属性进行规则挖掘。 3数据转换 如果关联规则算法处理的项目值太多，甚至某些数据是连续数据的话，关联规则算法将挖掘出大量的规则，如此多的规则显然对用户来说是没有实际价

31、值的。因此在数据挖掘之前，需要对值过多的项目进行泛化，对连续数据进行离散化处理。 由于报考职业院校的成绩普遍较低，根据学院教务处的成绩约定，将考生高考总成绩考试的总成绩划分成三段：大于 350 分的定为优秀；小于 250 的为差，250 到 350 之间的为一般。由于 JD 学院针对河北地区招生，省外的报考学生人数较少，所占比例小于 0.5%，因此删除这些省外学生的记录。根据以往的生源的情况、地理位置、地区人数、经济水平、招生宣传地区划分，将河北省的 11 个地区划分成 3 个区域：A、冀南地区，B、冀北地区，C、省会地区。JD学院目前共有 17 个专业，根据各专业所属领域，将这些专业划分成 4 类：人文类、机械类、电气信息类。通过上述数据转换处理后，分析的数据变成了事务数据。4.关联规则挖掘结果 系统提供属性选择和属性概化处理，在经过数据的预处理后，需要设置 Apriori算法的支持度和置信度两个参数支持度和置信度的设置需要一个比较科学合理