面向多维教务管理数据的关联规则算法研究.doc

自然科学基础研究类所属学科计算机项目编号佳木斯大学科学技术研究项目申 请 书(重点项目 面上项目 指导项目)项目名称 面向多维教务管理数据的关联规则算法研究项目负责人 张磊联系电话在学院 教务处项目起止日期 2011.8.1-2013.7.31填报日期 2011年6月佳木斯大学科技处2011年5月填表说明一、申请书各项内容，要实事求是，认真填写。除签名栏外必须打字，字号小四（简表不小于五号），宋体。外来语要同时用原文和中文表达，第一次出现的缩写词，必须注出全称。二、所在单位要写清楚所在学院（系、部、处）。三、项目组成员要在申请书上亲自签名，不得代签。四、申请书内容要逐项填写，可顺延加页。五、申请书用A4纸双面输出，于左侧装订成册，申请书与附表各一份。六、“预期成果”栏要认真填写，未完成“预期成果”者将不予结题。七、项目发表论文需注明佳木斯大学科技项目资助并写明项目编号，否则不予认定为结题成果。结题论文第一署名单位必须是佳木斯大学，项目负责人至少发表一篇为第一作者或通讯作者的论文，且该论文应在“预期成果”中为最高水平。一、基本信息表 研究项目项 目 名 称面向多维教务管理数据的关联规则算法研究关键词（最多四个）教务管理数据、关联规则类 型基础研究 应用基础研究所属学科计算机申请经费3000元起止时间2011.8.1-2013.7.31申请者姓名性别年龄学历学位技术职称所学专业从事专业张磊男29研究生硕士助理研究员计算机科学与技术教育学身份证院（系、部、处）教务处所在学科或实验室重点学科（省 校） 重点实验室（厅 校） 其他学科带头人学科带头人 后备带头人研究生导师是 否手机人数专业技术职称参加课题的在读学生参加学院数高级中级初级博士生硕士生本科生615项目组主要成员不含申请者姓 名性别年龄技术职称学历学位学院（系、部、处）签 字崔虹云女34讲师研究生硕士理学院李晶女44教授研究生硕士信息电子技术学院陈育德男31助理研究员研究生硕士教务处陈新男32助理研究员本科双学位教务处尚东昌男33讲师研究生硕士教务处陈凌凌女34实验师研究生硕士教务处二、立题依据1研究目的与意义随着高等教育的飞速发展以及教务管理软件的广泛应用，传统的以纸质数据为中心、统计学方法为手段的高校分析决策逐渐被以电子数据为中心、数据挖掘技术为手段的全新分析决策方法所取代。教务管理服务也转变为以教务管理数据为中心，通过教务管理各部门之间的关系，深入了解教务数据在部门间传递及在院系间产生的诸多问题，提高教务管理质量，保持和提高教务教学水平的一种新型教务管理机制。然而，随着数据量以及数据类型的不断变化，现有的管理软件处理能力以及数据挖掘算法的分析解决能力都面临着各种各样的挑战。以教学设施数据为例，由于办学规模的不断扩大，学校教学校区不断增长，因此势必造成多个校区中存在不同教学设施的情况。如何合理利用不同校区之间的不同教学设施，减少学生或教师在教学过程中出现的问题，成为了教务管理服务中急需解决的问题。因此，以教务管理服务数据为中心的数据挖掘技术，能够处理教务管理数据中存在的多维、复杂等各种情况数据的数据挖掘方法，成为了当前关于教务管理数据挖掘技术中的全新课题。而在这种数据挖掘技术中，面向多维教务数据的关联规则算法具有着很强的理论意义和应用价值。因此本项目将着重研究多维教务数据中的关联规则的获取和关联规则算法的实现。2国内外研究现状在1993年Rakesh Agrawal等首次提出了关联规则挖掘的概念并给出了基于数据库多趟扫描的Als算法1，此后关联规则由于其可用性和易于理解的优点获得了广泛的关注和深入的研究，提高获取的关联规则的精确度和执行效率成为研究的中心议题。Agrawal其后提出了改进的AIS算法Apriori，AprioriTID及AprioriHybrid，成为众多关联规则算法的基础。随着多种关联规则算法的提出以及算法不断显现出的优点及高效的处理能力，越来越多的人投入到对关联规则算法的研究中去，并且取得了很好的研究成果，产生了很多提高关联规则算法处理能力的改进算法，如FDBM_Apriori算法2，该算法采用基于划分的方式，将数据库使用分区和二进制处理，分成若干子集，然后对子集使用Apriori算法进行计算，可以看作为Apriori算法和基于划分的算法的一个很好的实践。同样DDApriori算法3、MDMITB 算法4、基于文献5的ME-Apriori算法等也都是在Apriori算法的基础上整合其他方式针对Apriori算法进行改进。在针对Apriori算法进行改进的同时，将已有的Apriori算法的改进算法再次进行改进也成为了流行，并出现了大量的改进算法，例如：针对FP-Tree算法提出的FPWAL算法6，以及基于矩阵的关联规则挖掘算法APM算法7，该算法的基本思想就是首先将数据库转化为布尔矩阵，然后针对转化后的布尔矩阵进行数据预处理，最后将经过预处理的数据进行计算求出频繁k-项集。另外NFWARM算法8也是基于矩阵的关联规则算法中比较具有代表性的算法。这些算法的提出在很大程度上解决了经典算法中存在的不足之处，适应了数据发展的需要。但是数据技术的不断发展所带来的影响使得已有的算法在不断改进的同时面临了更多的数据处理难题，多维数据的处理就是其中最为典型的一个。由于Apriori在处理多维数据能力上的不足上，人们又将研究的方向投入到多维关联规则算法的研究中去，针对实际问题中出现多维数据的情况很多人又提出了与之对应的多维关联规则算法，如基于数据立方体的Apriori_Cube算法及其改进算法9-11,所谓数据立方体挖掘算法，就是根据用户给定的挖掘任务将待挖掘的数据仓库按照一定的数据相关行整理成立方体的形式，简单的说就是对数据进行分层、分块的处理，然后在整理好的小数据块上进行频繁谓词集计算，最后在所得到频繁谓词集中得出有用的关联，这种算法在一定程度上解决了多维Apriori算法在多维问题上的不足。还有一些其它相关的获取多维关联规则的算法如：MB算法12、MPIT算法13、LDPIS算法14等。其中LDPIS算法主要思想就是将多维事物数据库中每个事物中的项集被事务中的维值约束，在LDPI树中只有那些被改进的LD树中的频繁维谓词集约束的频繁k-项集才能与频繁维谓词集一起形成多维频繁项集，因此只需要考虑LD中频繁维谓词集代表的维值约束。由于LDPI树中的桶与LD中的频繁维谓词集是一一对应的，因此可以用桶存放对应的频繁维谓词集约束下的候选项集和频繁项集，而用LDPI树结构由给定的事物去应对哪些桶中的候选项集计数。桶里存放的是一组事物序号，可以通过这些序号到全局事物数组里查到具体的事物，采用LexiItemsTreeBuild算法进行处理。另外还有UML 2.0 profile算法15、GARC 算法16、CBAR算法17、BSC-tree和FIS-tree算法18、CFP-growth算法19、TBAR 算法20等等。参考文献1Jiawei Han，Micheline Kamber. 数据挖掘概念与技术. 机械工业出版社,2005，3、149-167、223-234.2徐增辉.数据挖掘在现代远程教育中的应用.电脑知识与技术，2007，（5）：1179-1180.3杨金凤，刘锋.一种新的改进Apriori算法.信息化纵横，2010，（1）：55-56+60.4郑全朝，武建华. 基于二分搜索的最大频繁项目集求解算法改.计算机应用与软件，2010，（5）：269-271.5 余波，朱东华，刘卓君.加权关联规则挖掘算法在电子商务中的应用.计算机工程与应用，2008，44(17):128-13.6彭珍,裴丽丽,杨炳儒.一种新的关联规则挖掘方法.计算机工程与应用，2009，（45）：127-129. 7吴仁堂，周根宝. 基于模式矩阵匹配的关联规则挖掘算法.内蒙古农业大学学报，2009.（3）：190-193.8刘闻超,施化吉,马素琴.一种加权模糊关联挖掘算法.计算机工程与设计，2010，31（16）：3654-3657. 9高学东.王文贤.武森.基于数据立方体的多维关联规则的挖掘方法.计算机工程，2003，29（14）：74-76.10贺琼,刘谭仁,郭平.数据立方体上多维多层关联规则挖掘算法.计算机应用，2004，24（3）：85-87.11吴少莹,乔梅,楼佳.一种新的多维关联规则挖掘算法.天津理工大学学报，2008.24（4）：78-81.12范明,牛常勇,朱琰.一种多维关联挖掘的有效算法.计算机科学，2001，28（11）：44-47.13方旺盛,郑到,邵利平.基于多维关联规则的算法研究及系统实现.计算机与数字工程，2004，32（4）：25-28.14 黄德才，张良燕，龚卫华，刘端阳. 一种改进的关联规则增量式更新算法.计算机工程，2008，34（10）：38-39+42.15Jose Zubcoff and Juan Trujillo. A UML 2.0 profile to design Association Rule mining models in the multidimensional conceptual modeling of data warehouses. Data & Knowledge Engineering Volume 63, Issue 1, October 2007, Pages 44-62.16Guoqing Chen, Hongyan Liu, Lan Yu, Qiang Wei, Xing Zhang. A new approach to classification based on association rule mining.Decision Support Systems, Volume 42, Issue 2, November 2006, Pages 674-689.17Yuh-Jiuan Tsay, Jiunn-Yann Chiang. CBAR: an efficient method for mining association rules Knowledge-Based Systems, Volume 18, Issues 2-3, April 2005, Pages 99-105. 18Xiang-Rong Jiang, Le Gruenwald . Microarray gene expression data association rules mining based on BSC-tree and FIS-treeData & Knowledge Engineering, Volume 53, Issue 1, April 2005, Pages 3-29.19Ya-Han Hu, Yen-Liang Chen .Mining association rules with multiple minimum supports: a new mining algorithm and a support tuning mechanism Decision Support Systems, Volume 42, Issue 1, October 2006, Pages 1-24.20Fernando Berzal, Juan-Carlos Cubero, Nicols Marn, Jos-Mara Serrano .TBAR: An efficient method for association rule mining in relational databases Data & Knowledge Engineering, Volume 37, Issue 1, April 2001, Pages 47-64.3. 研究工作基础、现有条件和手段1.积累了大量的教务管理数据，包括教室管理、调串课管理、课程管理、考试管理、成绩管理等多种数据，为研究奠定了数据基础；2.项目组成员有着多年数据挖掘研究的经验，在数据挖掘技术上做了大量的工作，取得了一定的研究成果。在该项目上也作出了大量的基础性工作，积累了相关研究理论和技术基础；3.项目组成员一直处在教务管理第一线，具有较高的教务管理水平，积累了大量的实际工作经验，不仅能够针对研究提供大量的实验数据，而且能够在项目的研究过程中提出更多实际可行的建议。三、研究方案1. 主要研究内容、创新点及特色（1）研究内容关联规则算法针对已有建立的数据仓库，通过研究一种高效的关联规则算法，对数据仓库中的数据进行数据挖掘，最终得出对决策具有一定指导意义的规则。拟采用聚类的方法进行频繁项集的获取；聚类算法针对传统聚类算法中存在的不足以及其它可以转换为聚类算法的相关算法的研究，研究一种能够适合在计算关联规则时使用的新型聚类算法，该算法不仅能够快速高效的完成聚类任务，还应具有一定的多维数据处理能力。拟针对粒子群聚类算法（PSO）进行变形优化，通过不同算法结合获取适合研究内容的聚类方法；多维约束机制针对关联规则获取的两个基本步骤中的第二步进行约束，通过关联规则算法的计算得出的规则数据中存在着一定的冗余数据，同时在去除不满足最小支持度阈值的数据集时，存在丢失规则的可能，通过制定一种相应的多维约束机制，最小的减少算法本身对获取规则的影响。（2）创新点及特色1、PSO和K-means相结合：粒子群优化算法（PSO）自问世以来以其收敛速度快被广泛的应用于各个方面，若简单的将该算法应用于聚类显然是不现实的，而单纯的将PSO和K-means算法结合使用也将会影响聚类效果。因此，在不影响算法本身优点的情况下最大限度的提升聚类能力，为关联规则的获取奠定基础。2、对于关联规则获取的研究：作为数据挖掘的两种不同算法，聚类算法和关联规则算法在数据挖掘技术中都具有很强的影响力，在关联规则算法中传统的Apriori算法由于在计算时产生大量的频繁项集空集，这给算法执行的时间和空间造成了很大的影响，而聚类算法则可以通过聚类的方式获取频繁项集并且不产生空集降低了时间和空间的影响。2. 拟解决关键问题通过以上分析我们很容易发现，教务管理服务数据中需解决多维数据问题主要在聚类算法的研究和关联规则算法的研究两个方面：1、聚类算法传统的聚类算法k-means算法在执行的过程中存在一定的局限，也就是对孤立点的处理存在严重的不足，而在教务管理数据中极有可能会存在大量的孤立点。而粒子群优化的聚类算法虽然对多维数据具有很好的处理能力，但是当涉及到大量数据时又会由于处理方式和处理步骤的复杂造成大量的空间消耗。当前已经有部分学者提出将两种算法结合到一起进行使用，然而其方法在教务管理数据的挖掘中存在一定的局限，因此本课题在聚类算法中拟研究一种将k-means算法和PSO算法有机结合的一种新型算法，其中可能会涉及到对两种算法的适应性修改，通过最终研究后的算法，解决在关联规则获取过程中通过聚类算法处理部分多维教务管理数据的问题。2、关联规则算法对于多维甚至高维关联规则算法的研究是目前比较热门的研究方向，并且产生了很多具有很好处理能力的算法，然而现存的算法一般具有数据局限性，针对教务管理数据直接使用这样的方法显然是不现实的，而且目前现有的多维关联规则算法在时间和空间的消耗上也存在着严重的不足。因此本课题在关联规则获取的算法上拟采用一种基于聚类算法的新型关联规则获取方法，采用聚类的方式减少频繁项集中空集的数量，通过多次聚类产生一种树形结构的数据集，每一个数据集作为一个频繁节点，通过多个频繁节点获取频繁项目集，最终获取备选关联规则。在获取备选关联规则之后增加一种约束机制降低在规则获取过程中因消去低于最小支持度阈值项集而造成的规则缺失。基本数据模型结构如图1所示：AA1A2A11A12A21A22BB1B2DC图1 本课题拟采用的算法数据模型3. 主要研究方法和技术路线本课题将按照系统工程的方法开展研究工作，首先基于所要解决的关键问题进行相应的理论研究以及相关参考文献的查阅，然后在总结理论研究获得的结果的基础上进行数据代入实验，通过实验对比改进算法在理论研究中存在的不足，最后结合已有的实验比对结果得出最终的关联规则算法。本课题采取的技术路线是：系统应用调研多维关联规则理论探讨多维关联规则理论方法研究多维关联规则算法研究算法与软件原型实现算法数据验证算法总结。整体研究思路如图2所示：多维关联规则技术多维关联规则理论对于教务管理多维数据的算法求解模型聚类分析关联规则基于教务管理多维数据的软件验证算法应用图2 本课题的研究方案整体思路4. 项目的进度安排1、2011年8月10月，资料调研，阅读与课题相关的文献，了解相应发展过程及国内外的研究现状，提出项目研究的初步方案。2、2011年10月12月，进行理论上的研究，在初步处理数据并研究聚类算法