Apriori算法优化及其在挖掘学生成绩中的应用汇编Word格式.docx
《Apriori算法优化及其在挖掘学生成绩中的应用汇编Word格式.docx》由会员分享，可在线阅读，更多相关《Apriori算法优化及其在挖掘学生成绩中的应用汇编Word格式.docx（17页珍藏版）》请在冰点文库上搜索。
1.2研究内容
本文的研究工作主要源于以上内容，主要目的是对数据挖掘中的关联规则进行深入研究，针对数据挖掘中关联规则经典挖掘算法Apriori算法的缺陷，探讨数据挖掘中关联规则的优化问题，给出一种优化算法，并简单分析地对两种算法的挖掘效率进行比较分析，最后又利用数据挖掘工具SPSSClementine针对具体的数据（即07级信管专业主要课程成绩）进行关联分析。
论文的主要工作及结构如下：
1.课题简介。
简单介绍了研究课题的背景和研究内容。
2.关联规则分析。
简单介绍了关联规则基本概念的基础上，引出经典算法Apriori算法，在介绍算法思想的基础上，通过一个具体实例来演示算法的挖掘过程，然后分析算法的优缺点，提出其性能瓶颈。
3.Apriori算法改进。
主要针对事务压缩，即及时删除事务数组中的无效事务，减少扫描的事务数，而且将所需要的数据库表事先映射到内存中，那么在以后的扫描中就不用再都设计部数据库，从而提高效率。
4.数据挖掘工具的应用。
使用数据挖掘工具SPSSClementine结合实际教学数据，进行数据挖掘，得出挖掘结果，并针对挖掘结果进行分析，得到对教学有帮助的信息，并对挖掘过程中存在的问题进行分析。
第2章关联规则
2.1基本概念
2.1.1定义
设I={i1，i2，……，im}是项的集合。
记D为交易T的集合，这里交易T是项的集合，并且T
I。
对应每一个交易有唯一的标识，如交易号，记作TID。
设X是一个I中项的集合，如果X
T，那么称交易T包X。
项的集合称为项集。
包含k个项的项集称为k-项集。
项集的出现频率是指包含该项集的事务数，简称为项集的频率或支持度计数。
一个关联规则是形如X
Y的蕴涵式，这里X
I，Y
I，并且X∩Y=
。
规则X
Y在交易数据D中的支持度（support）是交易集中同时包含X和Y的交易数与所有交易数之比，记为support（X
Y），即：
规则X
Y在交易集D中的置信度（confidence）是指包含X和Y的交易数与包含X的交易数之比，记为confidence（X
如果不考虑关联规则的支持度和置信度，那么在事务数据库中存在无穷多的关联规则。
事实上，人们一般只对满足一定的支持度和置信度的关联规则感兴趣，同时满足最小支持度（min_sup）和最小置信度（min_conf）的规则称为强关联规则。
因此，为了挖掘出有意义的关联规则，需要给定两个阈值：
最小支持度和最小置信度。
前者即用户规定的关联规则必须满足的最小支持度，它表示了一组物品集在统计意义上的需满足的最低程度：
后者即用户规定的关联规则必须满足的最小置信度，它反应了关联规则的最低可靠度。
2.1.2分类
根据不同的标准，关联规则可以有以下几种分类方法：
1根据规则所处理的类型值，可以分为布尔类型和量化类型。
2.根据规则中涉及的数据维数，可以分为单维和多维的关联规则。
3.根据规则集所涉及的抽象层，可以分为单层或多层关联规则。
2.1.3过程
关联规则挖掘的任务就是在事务数据库D中找出具有用户给定的最小支持度min_sup和最小置信度min_conf的强关联规则。
步骤如下：
1.根据最小支持度阈值找出数据集D所有频繁项目集；
2.根据频繁项所有频繁项目集和最小置信度阈值产生所有关联规则。
理论依据如下：
因为
所以如果频繁项集l的第一个非空子集s满足：
那么产生强关联规则：
2.2Apriori算法
2.2.1算法思想
该算法是一种挖掘布尔关联规则频繁项集的算法。
它利用频繁项集性质，用逐层搜索的迭代方法来找出所有的频繁项集。
首先，找出频繁1-项集的集合，该集合记作L1。
L1用于找频繁2-项集的集合L2，而L2用于找L3，如此下去，直到不能找到频繁k-项集为止。
在第k次循环中，先产生候选k项集的集合Ck，Ck的项集是用来产生频繁项集的候选集。
Ck中的每个元素在数据库中根据支持度计数进行验证，决定是否加入Lk。
2.2.2实例分析
下面给出一个具体的实例来说明Apriori算法的挖掘过程，事务数据库如表2-1所示：
表2-1事务数据库
TID
I1
I2
I3
I4
I5
T1
89
96
91
94
T2
81
80
T3
82
67
86
92
93
T4
78
69
88
T5
70
66
63
72
T6
71
64
77
73
85
T7
95
65
75
T8
61
55
T9
其中I1：
C语言I2：
C++I3：
离散数学I4：
操作系统I5：
计算机组成原理
首先按照一定的标准将原始成绩进行转换，即将每个成绩转化布尔类型（0，1数据），原则为高于该科成绩平均分的为1，低于的为0，从而得到一个新的数据库D，转换后的数据如表2-2所示：
表2-2事务数据库
1
在上数据库D中利用Apriori算法进行关联规则的挖掘，事务数据库的事务数为9，min_sup=4。
利用min_sup对数据库D进行挖掘，最大频繁项集的产生过程如下：
1.扫描数据库D，得到候选1-项集C1并计算各个项集的支持度（表2-3）
表2-3候选1-项集C1
项集
支持度计数
{I1}
5
{I2}
4
{I3}
{I4}
3
{I5}
6
2.剪枝，将C1中支持度小于给定值4的项剪去，得到1-频繁项集L1（表2-4）
表2-41-频繁项集L1
3.利用Apriori算法进行自连接操作，得到C2，,扫描数据库D得到各个候选2-项集的支持度（表2-5）
表2-5候选2-项集C2
{I1,I2}
{I1,I3}
{I1,I5}
{I2,I3}
{I2,I5}
{I3,I5}
4.剪枝，将C2中支持度小于给定值4的项剪去，得到2-频繁项集L2（表2-6）
表2-62-频繁项集L2
5.利用Apriori算法进行自连接操作，得到C3，扫描数据库D得到各个候选3-项集的支持度（表2-7）
表2-7候选3-项集C3
{I1,I2,I3}
{I1,I2,I5}
{I1,I3,I5}
{I1,I2,I3,I5}
6.剪枝，将C3中支持度小于给定值4的项剪去，得到3-频繁项集L3（表2-8）
表2-83-频繁项集L3
7.结束，频繁项集L3{I1,I3,I5}即为{C语言，离散数学，计算机组成原理}
2.3Apriori算法改进
2.3.1改进思想
由于当一个事务中不包含长度为k的频繁项集时，则必然不包含长度为k+1-频繁项集；
而任意一个k-项集的支持度与规模小于它的事务无关。
所以，在生成k-候选频繁项集时，就不用再扫描字段长度小于k的记录，以便减少扫描的数据量。
那么，我们可以另建一张辅助表F（以矩阵形式存储），用于存储这些信息，包含该记录的编号和它的字段长度。
在随后的过程中，及时删除其中不可能出现在候选项集中的记录，即字段长度不大于将要生成的k-频繁项集k值，而且也不被包含在频繁项集中的记录。
在每次的扫描时，只扫描辅助表中存在的记录，不需要每条记录都扫描。
改进算法从两个方面提高了运行效率：
1.将要查询的数据表取出放入内存中，存储为矩阵E，从而使以后每次扫描时不需要再访问数据库，而是直接访问内存，从而使速度增快；
2.通过辅助表F，减少访问表E中记录的无效记录，从而使访问次数减少。
2.3.2实例分析
根据上一节的数据库，改进算法执行过程如下：
1.扫描数据库D，生成数据表E（表2-2），将其放入内存中，同时计算每条记录的规模，生成初始辅助表F1
表2-9辅助表F1
字段长度
2
2.根据给定值min_sup得到1-频繁项集L1（表2-4）
3.修改，将F1中字段长度不大于1的记录删除（删除T5,T8,T9）。
如果该记录包含在频繁项集中，则不从表F1中删除，得表2-10
表2-10辅助表F2
4.L1通过连接产生候选频繁2-项集C2（表2-5），通过扫描辅助表F2和E得到C2中各个项集的支持度，获得2-频繁项集L2（表2-6）。
5.修改，将F2中字段长度不大于2的记录删除（删除T6,T7），得表2-11
表2-11辅助表F3
6.L2通过连接产生候选频繁3-项集C2（表2-7），通过扫描辅助表F3和E得到C3中各个项集的支持度，获得3-频繁项集L3（表2-8）。
7.结束，得到的所有频繁项集，得表2-12
表2-12频繁项集
第3章数据挖掘在学生成绩中的应用
3.1数据挖掘工具简介-SPSSClementine
Clementine翻译成中文是克莱门氏小柑橘，它是ISL（IntegralSolutionsLimited）公司开发的数据挖掘工具平台。
1999年SPSS公司收购了ISL公司，对Clementine产品进行重新整合和开发，现在Clementine已经成为SPSS公司的又一亮点。
Clementine功能特别强大，它可以进行分类和预测、聚类、关联分析、时序分析等功能，提供神经网络、决策树与回归树、线性回归、自组织网络、快速聚类、二次聚类、主成分分析和因子分析等多种方法。
它具有交互式可视化的用户界面，几乎所有的操作都可以在窗口下发现，而不需要编程来完成。
具备开发的数据库接口，支持定界或等宽格式文本文件、SPSS文件、SAS文件和多种类型的关系数据库。
它提供两种建立模型的方式，在简单模式下，用户无需做任何设定，系统会按照默认的设置；
在专家模式下，用户则可以根据自己的需要对模型中的各个参数进行适当的调节，从而使模型达到最佳的效果。
而且它还具有很好的发布功能。
3.2建模过程
目前，大多数高校的教学计划均是由教学院长编写，他们凭借多年的教学经验，再经合有关规定，来决定给学生开哪些，以及课程顺序。
但是这不免会有一定的主观性，忽略了多年来积累下来的学生成绩这一宝贵资源的重要性。
我们可以对学生各科成绩进行数据挖掘，找到这些学科之间的关联规则，客观地了解它们之间的关系，以有助于今后教学计划的编写。
以下就对于我们信管专业前五个学期的成绩建模进行数据挖掘。
3.2.1数据清洗与集成
1.数据清洗：
消除噪声和不一致的数据。
对于成绩缺少的记录按该科成绩的平均分记，对于成绩多的记录按第一次成绩记。
2.数据集成：
多种数据源组合在一起。
本次试验采用单一数据源，只需要将各个学期的成绩集合在一个文件（*.xls）里即可。
结果如下图所示：
图3-1原始数据
3.2.2数据选择与转换
3.数据选择：
从数据库中提取与分析任务相关的数据。
对于这次试验，学科的学分、学生的学号、姓名对于数据分析并没有什么作用，而我们信管专业是综合性专业，我们所学的课程大致可以分为基础课程、管理课程和计算机课程，本次试验主要针对计算机方面的课程进行分析，所以，在数据源中只保留这方面的课程成绩。
4.数据转换：
数据变换成适合挖掘的形式。
Apriori算法是布尔类型的关联规则算法，所以要将连续的学生成绩变为离散的布尔类型数据（0，1）。
由于各个科目的之间评分标准不一致，所以本次试验的转换方式为如果成绩大于该科的平均分，则为1；
小于该科的平均分，则为0。
图3-2数据源
3.2.3数据挖掘
5.数据挖掘：
使用智能方法提取数据模式。
步骤：
Ø
将数据源（信管成绩.xls）导入到流中；
对数据源建立类型：
将类型设置为离散型，将方向设置为两者；
导入Apriori模型，将前项、后项设置为全部项，最低支持度设为35%，最低置信度设为85%，最大前项数设为3；
模型图：
图3-2模型图
执行结果：
图3-4数据挖掘结果1
3.3模式评估与表示
6.模式评估：
根据某种兴趣度度量，识别表示的真正有趣的模式。
根据图3-4的挖掘结果分析可得，有些课程之间虽然有很大的关联，如电子商务概论和计算机组成原理，但是它们之间实际上并没有很密切的关系，一个偏于网络应用，一个偏于硬件组成，类似的还有IT项目管理与VB.NET之间。
7.知识表示：
图3-5数据挖掘结果2
（操作系统、VB.NET）
计算机组成原理置信度为90.0%
（VB.NET、JAVA）
（电子商务概论、VB.NET）
计算机组成原理置信度为94.444%
（JAVA、VB.NET）
操作系统置信度为85.5%
8.分析：
由图3-5分析得，C语言程序设计、离散数学、、数据结构和其它很多学科都有关系，所以，它们应该做为基础学科，较早开设。
而JAVA、电子商务概论、C++和其它学科的联系较少，JAVA和C++是比较深层次的学科，而电子商务概论是应用型的，所以应该较晚开设。
而计算机实用基础和其它学科的关联很小，说明它的学习不太会影响其它学科的学习，可能是由于随着计算机的普及，大家在学习该课之前已基本掌握了它的内容，所以，以后或许可以考虑不再开设此科目，以节约资源。
由图3-4分析可得，编程语言的学习促进同学对操作系统的学习，而操作系统的学习促进对计算机组成原理的学习，这是因为随着大家知识的积累，越发想从根本上了解计算机的运作。
而计算机组成原理、JAVA、VB.NET是规则中后项主要的科目（14/15），可知它们受其它学科的影响较大，应较晚开设，而它们本身也正是较为深入的学科，正适合较晚开设。
而规则中并没有挖掘出C语言程序设计
C++这一规则，可见，这两个学科的学习并可能并没有名称上的那么密切。
当然，虽然得到了那么多规则，但是这可能并不能说明绝对的问题，因为原始数据只是我们专业50名学生的成绩，规模不是很大，而且这个成绩也不完全是考试成绩，一般包括30%的平时成绩和70%的考试成绩，有些学科是直接交的论文，这对挖掘结果都有一定的影响。
还有就是在对原始数据进行离散化处理时，同样也产生了误差。
附
参考文献：
《数据挖掘技术的研究和应用》
《Apriori算法及其改进算法》
《数据挖掘原理及SPSSClementine应用宝典》
论文感想：
写到这里，论文也接近了尾声，不禁有点不舍。
因为觉得在把课程中学习的知识真正在实际中运用太有趣了，虽然本文针对学生成绩挖掘出来的知识并不一定是有趣的，但是让我从一开始对关联规则仅仅停留在定义上，对SPSSClementine毫不了解，到现在用SPSSClementine实施了整个关联规则的挖掘过程，感觉有了收获，当然这仅仅是一点点，以后还对它进行探索。
这次试验这我知道，我们不光要学习课本上知识，更要在课外，针对课本上知识进行延伸，运用。
谁会把上面的引号改成不是这样的对称形式的呀？
为了不影响您真情的挥洒，这里我就不给出模板了。
J
写不写都行。
不写的话就删除这章好了。
仅“同等学历”的同学需要写这个。
什么是“同等学历”？
我也不懂。
L
千万不要删除行尾的分节符，此行不会被打印。
不要在此行和下页的注释之间填写任何内容
下面的内容是参考文献，通过“插入”“引用”“脚注和尾注”，插入尾注到“文档结尾”后，word会自动生成序号。
双击序号能自动定位。
移动引用位置会自动重新编号。
还可以插入“交叉引用”，实现对一篇文献的多次引用。
因为本人能力所限，不能将其自动放入前面的“参考文献”章节内，也不能去掉接下来的这半条直线，所以就只能麻烦您这么做了：
打印前，备份文档，然后将下面的内容copy&
paste到“参考文献”内，并要手工修改序号。
注意！
copy前一定要备份！
以后再做修改时，要修改备份文档。
升级会员 