开题报告基于关联规则的成绩分析系统设计与实现

山山 东东 科科 技技 大大 学学 本科毕业设计（论文）开题报告本科毕业设计（论文）开题报告 题 目基于关联规则的成绩分析系统设计与实现 学 院 名称信息科学与工程学院 专 业 班 级软件工程 2011 级 2 班 学 生 姓 名柳汝滕 学号201101051718 指 导 教 师倪维健 填表时间：二一五年四月六日 设计（论文） 题目 基于关联规则的成绩分析系统设计与实现 设计（论文） 类型（划“”） 工程设计应用研究开发研究基础研究其它 一、本课题的研究目的和意义 数据挖掘是指以某种方式分析数据源，从中发现一些潜在的有用的信息，所 以数据挖掘又称作知识发现， 而关联规则挖掘则是数据挖掘中的一个很重要的课 题，顾名思义，它是从数据背后发现事物之间可能存在的关联或者联系。 本课题主要目的是通过研究 Apriori 算法和信息熵理论， 研究关联规则在学 生成绩分析方面的应用。 传统的 Apriori 算法在生成频繁项集和关联规则方面存 在着诸多缺陷。本课题针对 Apriori 算法进行一定程度的改进，使得更加有利于 应用于成绩分析。将该算法集成到学生管理平台下，通过对不同课程的成绩数据 进行挖掘， 比找出不同课程之间可能存在的关联， 了解学生课程成绩之间的关系， 比如：A 同学的 a 课程得分属于优秀，同时该学生的 b 课程得分也属于优秀，是 否可以推断 a 课程优秀的同学 b 课程相应的也多数为优秀。 通过类似的分析利于 院系调节相关课程的设置，使得课程的安排更加合理，通过分析课程的关联，安 排课程学习的先后顺序，辅助教学管理。同时该算法可以对课程成绩的评比是否 合理提供一定的参考意见。 数据挖掘中关联规则的分析并不局限于成绩分析， 在很多领域有着广泛的应 用于发展潜力，是一门具有广阔前景的数据处理与分析技术,它将在有大量信息 的教育领域中发挥不可估量的作用。 二、本课题的主要研究内容（提纲） 本课题主要目的是通过研究 Apriori 算法和信息熵理论， 研究关联规则在学 生成绩分析方面的应用。 1、关联规则分析： 关联规则分析的步骤： （1）从事务集合中找出频繁项目集； （2）从频繁项目集合中生成满足最低置信度的关联规则。 2、Apriori 算法： （1）传统的 Apriori 算法： 传统的 Apriori 算法在生成关联规则方面利用了向下封闭属性： 如果一个项 集是频繁项目集， 那么它的非空子集必定是频繁项目集。 它先生成 1-频繁项目集， 再利用 1-频繁项目集生成 2-频繁项目集， 然后根据 2-频繁项目集生成 3-频繁项 目集，依次类推，直至生成所有的频繁项目集，然后从频繁项目集中找出符合条 件的关联规则。 （2）改进的 Apriori 算法： 由于传统的 Apriori 算法的某些特性，使得算法存在着一定程度的改进，使 得关联规则的生成速度更加迅速。 3、信息熵： Apriori 算法在生成频繁项集方面具有一定的优势， 是一个比较优秀的算法。 但是在关联规则的生成方面存在一定的偶然性， 很容易受到部分偶然数据的影响 造成分析的结果与实际情况无法很好的吻合， 所以对 Apriori 在生成关联规则方 面不再使用简单的 p(B|A)=P(AB)/P(A)来作为置信度来判断。 不妨把信息熵理解成某种特定信息的出现概率， 某一信息出现与否是不确定 的，衡量它的标准是根据其出现的概率来度量。概率大，出现机会多，不确定性 小；反之就大。不确定性函数 f 是概率 P 的单调递降函数；两个独立符号所产生 的不确定性应等于各自不确定性之和，即 f（P1，P2）=f（P1）+f（P2），这称 为可加性。同时满足这两个条件的函数 f 是对数函数，即 f(P) = log(1/p)。 三、文献综述（国内外研究情况及其发展） 关联规则挖掘是数据挖掘研究领域中的一个重要分支， 最近几年已成为数据 挖掘领域一个重要的研究方向，而 Apriori 算法是关联规则挖掘中的经典算法， Apriori 算法的改进也是一个热门研究点，并取得了一定的成果。 1948 年，香农提出了“信息熵”的概念，解决了对信息的量化度量问题。从 那之后信息熵就广泛的应用于电子信息、决策分析、图像处理、农业科技研究等 广泛的领域，并获得很好的实际应用效果。 1、国外研究现状 1993 年， 美国著名学者 R.Agrawal 等人首次提出了关联规则挖掘问题， 之后 提出了基于频繁项集的著名 Apriori 算法。Apriori 算法是数据挖掘中关联规则 的最典型最核心最基本的算法。目前，国外对此算法的改进有：Pard 基于散列技 术的改进， Savasere 基于划分的改进， Toivonen 基于采样的改进， J.Han 和 Y.Fu 基于事务压缩的改进，等等，有效的改善了 Apriori 算法的效率低下问题。 2、国内研究现状 目前，国内在 Apriori 算法应用方面比较成熟，针对 Apriori 算法本身存在 的缺陷，也出现了改进和优化方法。但与国外的关联规则挖掘方法研究相比较， 我国在数据挖掘研究方面起步较晚。 国内针对关联规则挖掘涉及的领域进行了广 泛的研究，主要包括：对求频繁项集算法的研究、关联规则挖掘理论研究以及其 应用研究。也对经典的 Apriori 算法进行了改进：基于十字链表的改进，基于数 组向量的改进，基于逆编码性质的改进，基于压缩矩阵和聚类的 Apriori 算法的 改进等等，使得算法效率得到了大大的提高。 3、Apriori 算法研究方向 现今，伴随着数据爆炸时代的到来，数据信息量日益更新变化，也越来越庞 大。信息量的潜在规则也在不断发生着变化，涉及到数据挖掘算法的研究，相关 的算法也非常复杂。关于 Apriori 算法的未来研究方向，根据前人的改进方向以 及总结，可以发现今后一段时间可能在如下几个方向进行更加深入的研究：（1） 如何降低算法的时间复杂度和空间复杂度，提高算法的效率。（2）如何对算法 进行更加进一步的优化，包括数据结构等。（3）在关联规则挖掘的过程中，如 何与用户进行交互，使得用户更加直观而简单的读懂关联规则，发现潜在信息。 在挖掘的过程中，根据用户的领域知识，产生可视化的应用平台，使得用户获取 信息更加直观。 4、Apriori 算法应用发展趋势 对于 Apriori 算法的未来应用趋势，预测可能在如下领域有所涉及：（1） 人的血型与其成功的可能性之间的关系挖掘。（2）工作效率与其学历的高低之 间的关系挖掘，从而为工资分配，人才招聘提供决策支持。（3）父母学历的高 低与子女的个数之间的关系的挖掘，为计划生育政策提供良好的决策支持，从而 促进社会更好发展。（4）像智能化设备的研究，比如依靠语音识别的自动门。 5、信息熵理论的研究与发展 信息熵的大小用于表示概率系统的不确定程度,信息熵理论的研究通常都是 结合具体的情况，信息熵公式是确定的，但是信息熵的理论需要结合实际情况进 行一定程度的修改，来匹配特定课题的研究。 信息熵是一个非常有用的信息分析工具， 在很多领域有着广泛的因公， 比如： 广告、语音识别、图像分割等，都需要使用信息熵作为部分信息过滤的工具，在 未来的信息科技发展中，会有更加宽广的应用。 四、拟解决的关键问题 1、算法的研究与改进： （1）使用 java 语言实现经典 Apriori 算法，基于经典 Apriori 算法本身的 特征，通过优化频繁项集的生成过程，减少数据事务的访问次数。 （2）优化生成关联规则中的子集的产生过程，修改传统 Apriori 算法中关 联规则生成的方式，使用信息熵理论计算 A-B 的置信度问题。 2、数据过滤： （1）输入数据的过滤：输入数据是由学生成绩的原始数据组成的，需要对 学生的成绩进行过滤使得成绩可以作为事务的基本项可以输入算法； （2）关联规则的过滤：算法产生的关联规则是有一些与实际情况并不会相 符合，需要对明显不符合实际情况的关联规则进行一定程度的过滤。 五、研究思路和方法 1、前期准备 中国知网下载大量关于关联规则中 Apriori 算法以及信息熵相关论文， 理解 传统的 Apriori 核心思想：连接和剪枝；理解信息熵理论的产生原因以及与本课 题的适用程度。 2、中期工作 使用 java 编程实现传统 Apriori 算法，写工具类，对输入数据处理，使得 可以符合 Apriori 算法的输入。 根据信息熵理论， 制定一个适合 Apriori 算法生成关联规则中最小置信度的 生成公式。对 Apriori 算法改进，将普通的数据项的输入在内部处理为对数字的 操作，提高算法效率，将信息熵生成的公式替换传统的 Apriori 算法。分析改进 算法与传统算法的优化结果。 设计一个在线的成绩分析系统，前端页面使用 html5、bootstrap、jquery 等 技术或框架，使得用户可以通过自主设置支持度与置信度以及可以选择需要分析 的课程，并将生成的关联规则有效的展示给用户。对关联规则进行分析，生成更 加具有说服力的数据挖掘结果，为院系管理者提供教学决策支持。 六、本课题的进度安排 第 5、6 周：根据课题，规划自己的毕设整体的设计思路。熟悉传统 Apriori 算法思想，以及信息熵理论，对理论知识做到熟悉、熟练应用。 第 7、8 周：从网络或图书馆等资源库中查阅大量论文，总结传统 Apriori 算法存在的缺陷，并提出相关的 Apriori 算法的改进思路。在此期间，使用 Java 语言实现传统的 Apriori 算法，并使用部分数据做测试。 第 9、10 周：实现改进的 Apriori 算法，并对数据进行预处理，使用 Java 编写工具类，实现自动的对相应 Excel 成绩数据分析处理。并生成预处理结果， 代入算法中，分析算法与数据的匹配关系。 第 11、12 周：学习 Html5、bootstrap 的使用，整理出一个比较友好的程序 交互界面，方便系统的数据的输入以及结果的展示。并有针对性的对算法和输入 输出数据做一定的修改，使得信息处理更加符合要求。 第 13 周：撰写毕业设计论文初稿。并对系统的 bug 等进行修缮等工作。 第 14 周：修改毕业设计论文。 第 15 周： 修改完善毕业设计论文以及对其他有关毕业设计的一系列资料进行 整理。 七、参考文献 1 R.Agrawal,T.Imielinsla and A.Swami. Mining association rules between sets of items in large databaseC. In Proc. of theACM SIGMOD, 1993:207-216. 2 R. R.Agrawal. Fast algorithms for mining association ruleC. In Proc. of International Conference on Very Large Databases, 1994: 478-499. 3 M. J.S.Park. An effective hash-based algorithm for mining association rulesC. In Proc.ACM SIGMOD, 1995:175-186. 4 E.A.Savasers, Navathe. An efficient algorithm for mining association rules in large databasesC. In Proc. of International Conference on Very Large Databases, 1995: 432-443. 5 H.Toivonen. Sampling large databases of association rulesC. In Proc. of International Conference on Very Large Databases, 1996:134-145. 6 Y. J.Han. Discovery of multiple-level association rules from large data- basesC. In Proc. of International Conference on Very Large Databases, 1995: 420-431. 7 J. J.Han. Mining Frequent Patterns without Candidate GenerationC. In Proc. of the 2000ACM-SIGMOD, 2001:1-12. 8 杨旭,汤海京数据科学导论M