Apriori算法在教育领域的应用

《Apriori算法在教育领域的应用》由会员分享，可在线阅读，更多相关《Apriori算法在教育领域的应用（11页珍藏版）》请在金锄头文库上搜索。

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

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

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

4、据。6. 确定算法：根据上一步所得结果选择适合的算法、模型和参数。7. 数据挖掘：利用所选算法，从经过初步处理的数据中提取出用户所需的知识。要求其 结果要简单易懂，一般都是一些常用的表达式或产生式。8. 模式解释：对发现的模式进行解释。9. 评价：将发现的数据以用户易于理解的方式呈现，也包含对知识一致性的检查。YS?二图 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.11定义关联规则挖掘是数据挖掘中一个最重要的过程，用以发现大量数据的项集间的一些内在 的关联或相关联系。盎格鲁等人于 1993 年首先提出关联规则的概念，随后大量的研究人员 对关联规则的的挖掘问题进行了详细的研究。现在关于关联挖掘定义的版本比较多，由 Jiawei H

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

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

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

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

13、过程中，先由数据库读入所有的数据项，得出一个候选 1-项集合 q(Candidate 1-itemset)的支持度，然后找出频繁项集1-项的集合L/Large 1-itemset)，并利用 这些频繁 1-项集的结合与 2-项集合。4继续对数据库扫描，得出候选2-项集C2的支持度，找出2-项集合L2，利用这些频 繁2-项集合L2的结合，产生候选3-项集合C3o5继续执行上述的步骤，重复对数据库的扫描、并和最小支持度进行比较，产生更高层 次的频繁项集合，进行数据的优化。重复进行此操作步骤，直到不再结合产生新的候选频繁 项集为止。连接:为了找到频繁项集合Lk，需要连接Lk-1与自己产生连接候选项集k

14、-项集的集合。 该候选频繁项项集合记做Ck。设1,和12是Lk1中的项集。记1.门表示1.的第j项。执行k12k-1iji连接过程Lk-1-Lk-1，其中要求Lk-1的元素11和12可以连接的，如果：(111= 121)A(112= 122) AA(11k-2= 12k-2) A(11k-1 12k-1)，连接 11 和 12 产生的结果项集是 11 1221k-1 12k-1。记号1询表示h的第j项。剪枝:扫描数据库，确定Ck中每个候选项集的支持度计数。但是，候选集Ck可能很大， 为压缩Ck，可以利用以上法性质:任何非频繁项集合的(k-1)项集都不可能是频繁项集合k 项集的子集。所以，如果一

15、个候选k项集的(k-1)项子集不在Lk1中，则该候选也不可 能是频繁的，因此，从ck中删去。k(1)(2)(3)(4)(5)(6)(7)(8)L1= 1areg 1-itemsets; for (k=2; Lk-1&sut1; k+) do begink-1Apriori 算法为了生成所有的频繁集必须重复的扫描数据库并不断地进行连接和剪枝操 作，为此在实现时主要是利用了递推的结构实现该算法:Ck=apriori-gen(Lk-1);/新的候选集 for a11 tranfsactions tÎD do beginCt=subset(Ck，t);/事务 t 中包含的候选集for a11 candidates cÎ C=dotc. count+;end(9) Lk=cÎ Ck |c.count⊃minsupkk(10) end(11) Answer= U kLj第一步先产生频繁1-项集Lr然后是频繁2-项集L2,直到有某个i值使得L.为空，12i这时算法停止。这里在第k次循环中，过程先产生候选k-项集的集合Ck，C