Apriori算法在教育领域的应用Word文档下载推荐.docx
- 文档编号:7381449
- 上传时间:2023-05-08
- 格式:DOCX
- 页数:16
- 大小:129.25KB
Apriori算法在教育领域的应用Word文档下载推荐.docx
《Apriori算法在教育领域的应用Word文档下载推荐.docx》由会员分享,可在线阅读,更多相关《Apriori算法在教育领域的应用Word文档下载推荐.docx(16页珍藏版)》请在冰点文库上搜索。
了解KDD相关领域的有关情况,熟悉有关的背景知识并了解用户需求。
2.筛选:
从用户需求出发由数据库中提取出于本次KDD过程相关的数据,此过程主要是对数据库中的原始资源进行提取。
3.预处理:
初步处理上一步所选择出的数据,包括对数据的完整性与一致性进行检查,对数据中出现的噪声进行判断并加以去除,对错误和丢失的数据进行修补。
4.缩减:
对经过预处理数据的数据项,主要通过投影的方式或一些相关的数据库操作减少数据量。
5.任务定性:
根据用户需求确定KDD的结果属于哪类知识,这是作为选择知识发现算法的依据。
6.确定算法:
根据上一步所得结果选择适合的算法、模型和参数。
7.数据挖掘:
利用所选算法,从经过初步处理的数据中提取出用户所需的知识。
要求其结果要简单易懂,一般都是一些常用的表达式或产生式。
8.模式解释:
对发现的模式进行解释。
9.评价:
将发现的数据以用户易于理解的方式呈现,也包含对知识一致性的检查。
图1-1KDD过程
从上述对KDD过程的描述可以得出结论:
数据挖掘只是知识发现过程中的一个步骤,但它是知识发现过程中最重要的一个步骤。
它主要是利用知识发现算法,从数据中发现出有关的知识或模式。
1.2数据挖掘的相关概念。
数据挖掘(Datamining,简称DM),就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中,提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。
数据挖掘过程一般由确定挖掘对象、数据准备、模型建立、数据挖掘、结果分析表述和挖掘应用这几个主要阶段组成。
数据挖掘可以描述为这几个阶段的反复过程[2]。
首先确定目标、明确数据挖掘任务。
(1)数据准备
数据准备阶段又可进一步分成四个子步骤数据集成、数据选择、数据预处理和数据转换。
A、数据集成。
数据集成是将多文件或多数据库运行环境中的数据进行合并处理,解决语义模糊性,处理数据中的遗漏和清洗数据等。
B、数据选择。
数据选择指为数据挖掘目标搜集和选择有关的数据,这包括不同格式数据的转换以及不同部门数据的统一和汇总。
数据选择的目的是辨别出需要分析的数据集和,缩小处理范围,提高数据挖掘的质量。
C、数据预处理。
数据预处理是对数据进行清理和充实等工作。
数据库中重要的数据是准确的,不重要的数据可能存在污染。
预处理就是为了克服目前数据挖掘工具的局限性。
D、数据转换。
数据转换的一个重要工作就是对数据进行编码。
数据库中字段属性的不同取值转换成数码形式经有利于搜索。
(2)数据挖掘
这个阶段将进行实际的挖掘操作,即利用机器学习、统计分析等方法,从数据库中发现有用的模式或知识这里模式是浓缩数据的信息形式,如精炼数据库、表格、产生式规则、决策树、神经网络的权值等。
A、选择数据挖掘方法。
如统计分析、机器学习、模式识别方法和人工神经元方法等。
B、选择数据挖掘算法。
选择用来查找模式或符合数据的模型的算法,确定合适的模型和参数。
另外,数据挖掘方法必须和目标相匹配。
C、数据挖掘。
查找感兴趣的模式。
模式一般表示为一种特殊的形式或一套表达方式,如关联规则,分类规则或分类树,回归结构和聚类集等。
除了选择合适的挖掘算法外,其余的一切工作都可自动完成。
(3)数据挖掘结果分析表述和挖掘应用
A、结果表达。
尽量直观的表示挖掘结果,便于用户理解和使用,可利用可视化方法表示为图表等形式。
B、结果评价。
筛选和评价挖掘结果中的有用部分,查找可接受的结果。
可定义兴趣指标,考虑结果的正确度、新颖度、有用性和简单性。
把信息从输出中过滤出来。
利用可视化方法帮助用户决定所提取知识的有效性或对基本的数据或现象做出结论。
C、知识巩固。
把挖掘出的信息结合到执行系统中,了解这些信息的作用或证明这些信息。
用预先知道且可信的信息来检查和验证所挖掘的信息,解决可能存在的矛盾。
2.关联规则挖掘算法—Apriori-TIDS
2.1关联规则挖掘
2.1.1定义
关联规则挖掘是数据挖掘中一个最重要的过程,用以发现大量数据的项集间的一些内在的关联或相关联系。
盎格鲁等人于1993年首先提出关联规则的概念,随后大量的研究人员对关联规则的的挖掘问题进行了详细的研究。
现在关于关联挖掘定义的版本比较多,由JiaweiHan、Michelinekamber[3]等人给出的定义形式如下:
设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.数值型与布尔型关联规则:
以关联规则中处理变化量的类别不同进行分类。
数值型的关联规则可以直接对原始的数据进行处理,或者和多维的关联规则或多层的关联规则相结合起来,对数值型的数据字段进行处理,将其进行动态的分割。
布尔型关联规则处理的数据都是离散型的种类化的,方便显示变量间的关系。
例如:
电阻=(200Ω~250Ω)=>
额定工作电流=(15A~25A)是一个量化的关联规则;
而年级=“2005届”=>
专业=“软件工程”即为布尔型。
2.单维和多维关联规则:
以关联规则中数据涉及的维数不同进行分类。
单维关联规则只涉及到数据的单维度。
例如顾客购买的商品,牛奶=>
纸巾,只涉及到用户购买的商品;
而多维关联规则涉及到两个或两个以上的谓词,如:
电阻(200Ω~250Ω)^工作电流(<
=25A)=>
完全等级(‘A’)中,包含了三个不同的谓词(“电阻”、“电流”和“安全等级”),这种规则即称之为维间关联规则。
在某一规则中包含的某些谓词重复出现,我们称其为混合维间关联规则。
如:
灯泡=>
完全等级(‘A’)
3.单层和多层关联规则:
以关联规则中数据抽象的层次不同进行分类。
单层关联规则中所有的变量都不考虑它在现实生活中数据的不同层次,而多层关联规则要对数据的变量多层次充分考虑。
对于许多应用,在较低的数据层次很难找到强相关规则,而在较高的层次所发现的强相关规则可能具有比较普遍的意义。
2.2Apriori算法
Apriori算法作为在关联规则挖掘中最具代表与影响的一种算法。
Apriori算法核心思想是基于数据概率的挖掘数据布尔型关联规则项集,对据库中项目或事物之间的关系通过循序渐进的方式挖掘数据,对用户提出有价值的规则或指导意见。
该算法的过程主要由两步构成,连接(类矩阵运算)和剪枝(去掉无意义或没有必要的中间结果)。
在此算法中频繁的应用到项集这个概念。
[4]
其具体的执行步骤如下:
1.根据用户的要求制定出最小支持度和最小置信度。
2.找出所有的频繁项集。
首先由原始的数据库资料产生出物象集合,该集合称为候选集。
如果某一个候选集的支持度大于最小支持度,则认为它属于频繁项集合中的项,从而通过多次扫描产生出频繁项集。
3.在该算法的执行的过程中,先由数据库读入所有的数据项,得出一个候选1-项集合C1(Candidate1-itemset)的支持度,然后找出频繁项集1-项的集合L1(Large1-itemset),并利用这些频繁1-项集的结合与2-项集合。
4.继续对数据库扫描,得出候选2-项集C2的支持度,找出2-项集合L2,利用这些频繁2-项集合L2的结合,产生候选3-项集合C3。
5.继续执行上述的步骤,重复对数据库的扫描、并和最小支持度进行比较,产生更高层次的频繁项集合,进行数据的优化。
重复进行此操作步骤,直到不再结合产生新的候选频繁项集为止。
连接:
为了找到频繁项集合Lk,需要连接Lk-1与自己产生连接候选项集k-项集的集合。
该候选频繁项项集合记做Ck。
设l1和l2是Lk-1中的项集。
记li[j]表示li的第j项。
执行连接过程Lk-1∞Lk-1,其中要求Lk-1的元素l1和l2可以连接的,如果:
(11[1]=12[1])∧(11[2]=12[2])∧…∧(11[k-2]=12[k-2])∧(11[k-1]<
12[k-1]),连接11和12产生的结果项集是11[1]12[2]……11[k-1]12[k-1]。
记号li[j]表示1i的第j项。
剪枝:
扫描数据库,确定Ck中每个候选项集的支持度计数。
但是,候选集Ck可能很大,为压缩Ck,可以利用以上法性质:
任何非频繁项集合的(k-1)—项集都不可能是频繁项集合k—项集的子集。
所以,如果一个候选k—项集的(k-1)项子集不在Lk-1中,则该候选也不可能是频繁的,因此,从Ck中删去。
Apriori算法为了生成所有的频繁集必须重复的扫描数据库并不断地进行连接和剪枝操作,为此在实现时主要是利用了递推的结构实现该算法:
(1)L1={lareg1-itemsets};
(2)for(k=2;
Lk-1&
sut1;
k++)dobegin
(3)Ck=apriori-gen(Lk-1);
//新的候选集
(4)foralltranfsactionst&
Icirc;
Ddobegin
(5)Ct=subset(Ck,t);
//事务t中包含的候选集
(6)forallcandidatesc&
Ct=do
(7)c.count++;
(8)end
(9)Lk={c&
Ck|c.count&
sup;
minsup}
(10)end
(11)Answer=∪kLk;
第一步先产生频繁1-项集L1,然后是频繁2-项集L2,直到有某个i值使得Li为空,这时算法停止。
这里在第k次循环中,过程先产生候选k-项集的集合Ck,Ck中的每一个项集是对两个只有一个项不同的属于Lk-1的频集做一个(k-2)-连接来产生的。
Ck中的项集是用来产生频集的候选集,最后的频集Lk必须是Ck的一个子集。
Ck中的每个元素需在交易数据库中进行验证来决定其是否加入Lk,这里的验证过程是算法性能的一个瓶颈。
这个方法要求多次扫描可能很大的数据库,即如果频集最多包含100个项,那么就需要扫描交易数据库100遍,这需要很大的I/O负载。
通过上述的描述可以看出,Apriori算法存在着两个主要的缺陷:
1.需要重复的扫描数据库以确定各个候选项集的支持度计数。
2.需要产生大量候选项集。
这两个主要的缺陷(特别是第一个)成为了该算法的瓶颈,目前大多数对于该算法的改进基本都是针对于改进这两个缺陷来进行的。
2.3Apriori算法的改进Apriori-TIDS算法
随着待处理数据量的日益增多,Apriori算法的缺陷渐渐突出,越来越难以适应用户的需求,为此许多研究学者以该算法为原型,就如何能减少扫描的次数和在系统内存一定的条件下减少读取原始数据库的次数上进行了大量的研究和实践。
通过对Apriori算法及其改进算法的分析比较,针对原始算法需要多次重复扫描数据库以确定各个候选项集的支持度计数的缺陷进行改进,提出了一种新的算法Apriori-TID(TransactionIdentifier)算法。
[5]
该算法的执行步骤如下:
1.扫描数据库,对包含每一个项集的事务进行支持度计数,从而产生l-项候选集C1。
其中C1的结构为:
项集的名称Item_set,事务标识符列表Tid_list,支持度计数Support。
从项集C1中删除支持度计数小于最小支持度阈值的项,从而得到频繁1-项集L1。
2.Lk-1自身进行连接操作,生成k-项集Ck。
Ck的事务标识符列表为两个生成它的Lk-1的事务标识符的交集。
计算Ck中项集的标识符列表中TID的数量,得到Ck中每一个项集的计数。
下面我们通过一个定理来证明该算法的正确性。
定理:
对于一个K-项集L,设包含有L[1],L[2],……,L[k-2],L[k-1]的事务集合为A,包含L[1]L[2]……L[k-1]L[k]的事务集合为B,则有包含L的事务集合是集合A和B的交集,即A∩B。
下面通过该定理证明Apriori_TID算法。
证明:
(1)设t是A∩B中的任意一个事务。
A∩B⊆A⇒t∈A
A是包含有L[1]L[2]……L[k-2]L[k-1]的事务集⇒t包含有L[1]L[2]……L[k-2]L[k-1]
A∩B⊆B⇒t∈B
B是包含有L[1]L[2]……L[k-1]L[k]的事务集⇒t包含有L[1]L[2]……L[k-1]L[k]
综上可得:
t包含了项集L。
由此得证,A∩B中的任意事务均包含项集L。
(2)假设事务t!
∈A∩B,但t包含项集L
L[1]L[2]……L[k-2]L[k-1]是项集L的子集⇒t包含项集L[1]L[2]……L[k-2]L[k-1]而由题设可知,包含L[1]L[2]……L[k-2]L[k-1]的事务都包含在集合T1中⇒t∈T1
同理t∈T2由此可得t∈A∩B
与假设矛盾
综上题设得证。
若l1,l2是Lk-1中两个可连接的项集。
L1=L[1]L[2]……L[k-2]L[k-1],l2=L[1]L[2]……L[k-1]
L[k],l=l1∞l2=L[1]L[2]……L[k-1]L[k]∈Lk。
综上可知,包含l的事务集必然包含事务集l1与l2的交集。
由此可得l.Tid_list=l1.Tid_li∩l2.Tid_list。
由该式我们可以知道若要求的某一个事务集l的TID列表,只需要求生成它的两个事务集l1和l2的TID属性列进行求交集的运算即可。
(3)此时,剩余的Lk中的项集均是满足最小支持度阈值的项集,所以Lk=Lk.ItemSet。
改进算法可描述如下:
输入项:
待挖掘的事务数据库D;
根据用户需求所订立的最小支持度阈值min_sup
结果:
D中满足最小支持度阈值的所有频繁项集合L。
3.Apriori-TIDS算法在教育领域的应用
3.1教育管理决策系统
随着高校招生规模的不断扩大和信息技术的不断发展,各个高校都建立了自己的教务管理信息系统,这些系统大大提高了教学和管理的水平,同时也积累了大量的教学和管理数据。
与其他资源相比,教育信息资源是无形的潜在的,但它对教育发展具有直接的、其他资源难以替代的作用。
[6]教育信息挖掘对教育管理决策的辅助作用主要体现在以下几个方面:
合理设置课程
高校的好多课程之间都具有一定的衔接性,先行课程学的好坏会直接影响后续课程的学习。
利用数据挖掘技术,对学生的以往成绩进行挖掘,就能发现课程之间的关联,并以此为依据,对课程设置做出合理的调整。
改善教学模式
由于授课教师的授课方式和教学水平的差异,学生的成绩也会有所差别。
通过数据挖掘,可以发现教师学历、职称、授课方式等同教学效果之间的联系,从而有针对性的改善教学模式,提高教学质量。
此外,数据挖掘技术在高校教学管理决策中的应用还有毕业生就业分析、课程成绩预测、试卷分析以及高校教学评估等,这些应用都会对高校的教学管理发挥积极地作用。
3.1.1系统总体构架
ARMEMD系统即教育管理决策中的关联规则挖掘系统:
图3.1系统架构
1.将原始的数据经过初步的处理后,将其加载至基本数据库中。
一般原始的数据文件都以多种形式存在于多种媒体介质中,为了能够统一的处理这些数据,我们就需要将这些数据进行集成,并用统一的格式进行数据的格式化,然后在加载至ORACLE数据库中。
并对原始数据进行初步的清理,把数据库中一些错误或无用的噪声去掉。
2.转换原始的数据库资料成为适应关联规则挖掘。
在进行基本数据库设计时,要考虑如下问题:
(1)数据的原始形式
(2)本数据挖掘系统的挖掘过程是否在该数据库中的结构适用(3)本系统以及其他系统的接口问题。
因此,原始数据在初步加载完以后,需要对其进行结构上的转换,以便于利用挖掘系统对其进行数据的处理。
3.利用改进的关联规则挖掘算法进行挖掘,得出用户感兴趣的规则信息。
将新的改进算法用ORACLE语言编写成数据库挖掘过程,对数据库中的信息进行关联规则的挖掘,并将其结果存放于一个规则库中的各个属性表中用以查询。
制作一个可视化的人机交互界面来对挖掘参数来进行设定和调节(主要包括最小支持度阈值和最小置信度值)。
4.最后为了能让用户获得跟直观的结果信息,将产生的关联规则通过一种可视化界面显示出来。
3.1.2挖掘主题设计
在教育决策系统设计中主要设计了五个主题:
(1)课程关联
(2)课程类别关联(3)学生基本信息关联(4)课程(5)基本信息关联和教学模式关联。
3.1.3挖掘效果
将新算法应用于教学管理系统中,开发出具有专家功能的教育管理决策的关联规则挖掘系统。
通过几个相关主题的设定,对现行的大学管理提出许多有价值的决策信息。
该规则结果的展示方面,采用了一种文本和图形相结合的可视化方式,从而可以让用户更直观的看到挖掘的结果,同时通过该界面让用户对自己所感兴趣的规则进行筛选,提高了系统的智能性,使得挖掘结果更加符合用户的感兴趣程度。
3.2招生管理系统
近几年在参加高考生源人数急剧下降和本科院校的扩招双重影响下,高职院校招生工作日益艰难。
传统的招生方式很多凭着优先的经验进行,没有针对性,不能有效节约招生宣传成本。
因此,摆在高职院校面前的重要课题是如何利用本学校已有的招生资源信息来促使高职院校在每年的招生宣传、提高考生报到率等方面做出正确的决策本文采用改进的关联规则算法Apriori算法对某高职院校招生系统的历史数据进行了挖掘,找出影响高职院校招生的潜在因素和规则,用来指导高职院校招生工作。
[7]
3.2.1招生管理模型
通过对数据挖掘的过程分析建立了招生管理模型。
招生管理模型首先对往届录取新生信息和新生录取信息提取相关数据进行预处理,然后经过关联规则挖掘找出影响往届学生报到和新生报到的影响因素,最后为招生录取提供录取管理方案和辅助决策。
招生管理模型的输入数据是考生的录取信息表和考生的报到信息表,输出数据是影响新生报到的关联因素,核心的功能是对招生数据关联规则的挖掘。
招生管理模型如图3-2所示。
图3-2招生管理模型
3.2.2招生管理模型实现
高职院校新生录取信息数据挖掘模块采用delphi6为开发工具,后台数据库采用SQL
Server2005,设计功能界面如图5-2所示。
该模块可以从SQLServer2005数据库中按年份提取新生报到的信息,经过属性选择和概化出来,然后设置支持度和置信度相关参数,通过系统内部实现改进的Apriori算法,分析出影响新生报到的主要因素和一般规律。
该模块选择从招生的信息中选择影响入学的考生类别、性别等属性,并对所选属性进行概化处理,作为关联规则挖掘的数据源。
同时,设置设置支持度和置信度有关参数挖掘出影响考生入学的关联规则。
3.2.3关联规则挖掘过程
1.数据来源
本系统采集数据来源于JD学院2013年考生信息。
JD学院的考生数据库采用SQL
Server2005,招生管理系数据库中设计考生信息的有以下几张表:
(1)考生基本信息表ksinfo,该表保存考生的考号、姓名、性别等基本信息。
(2)考生成绩表kscj,该表存储考生高考的各科成绩。
(3)考生生源表kssy,存储考生生源地,包括考生的户籍信息。
(4)考生报到表ksbd,主要记录考生报到的信息。
(5)考生科类代码表kskldm,主要记录学生文史类还是理工类。
(6)考生专业表kszyb,说明考生录取专业类别。
各个表与考生基本信息表ksinfo主键ksbh进行连接,通过在SQLSever2005中建立视图v_ksxx得到数据挖掘的原始表,作为数据挖掘的数据源,部分数据显示如图5-3所示。
2.属性选择
由于该系统数据挖掘目标是为学校的招生策略提高依据,挖掘出学生报考本校的相
关规则。
因此在考生的数据中和学生紧密相关的一些属性比如姓名、学生考号、身份证
号、联系电话中信息与数据挖掘的目的无关。
本文选择“考生类别”、“科类”、“报考
专业”、“成绩”、“科类”、“报到””六个属性进行规则挖掘。
3.数据转换
如果关联规则算法处理的项目值太多,甚至某些数据是连续数据的话,关联规则算法将挖掘出大量的规则,如此多的规则显然对用户来说是没有实际价值的。
因此在数据挖掘之前,需要对值过多的项目进行泛化,对连续数据进行离散化处理。
由于报考职业院校的成绩普遍较低,根据学院教务处的成绩约定,将考生高考总成绩考试的总成绩划分成三段:
大于350分的定为优秀;
小于250的为差,250到350之间的为一般。
由于JD学院针对河北地区招生,省外的报考学生人数较少,所占比例小于0.5%,因此删除这些省外学生的记录。
根据以往的生源的情况、地理位置、地区人数、经济水平、招生宣传地区划分,将河北省的11个地区划分成3个区域:
A、冀南地区,B、冀北地区,C、省会地区。
JD学院目前共有17个专业,根据各专业所属领域,将这些专业划分成4类:
人文类、机械类、电气信息类。
通过上述数据转换处理后,分析的数据变成了事务数据。
4.关联规则挖掘结果
系统提供属性选择和属性概化处理,在经过数据的预处理后,需要设置Apriori算法的支持度和置信度两个参数支持度和置信度的设置需要一个比较科学合理的值,过大或过小都会都挖掘结果产生很大的影响。
本系统会根据用户挖掘的数据量、过去挖掘经验等因素推荐一个值,但这个值是用户调整这两个
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- Apriori 算法 教育 领域 应用