《关联规则挖掘算法aprioritid算法的改善与研究》由会员分享，可在线阅读，更多相关《关联规则挖掘算法aprioritid算法的改善与研究（54页珍藏版）》请在金锄头文库上搜索。
1、河北工业大学 硕士学位论文 关联规则挖掘算法AprioriTid算法的改善与研究 姓名：安娜 申请学位级别：硕士 专业：管理科学与工程 指导教师：吴晓丹 2010-12 河北工业大学硕士论文 i 关联规则挖掘算法 AprioriTid 算法的改善与研究 关联规则挖掘算法 AprioriTid 算法的改善与研究 摘摘 要要 关联规则挖掘技术是数据挖掘领域应用最为广泛的技术之一， 本文对关联规则挖掘算 法AprioriTid算法进行分析， 总结出了目前关联规则AprioriTid算法存在的候选Tid 表庞大和存储大量无意义频繁项目集两个主要瓶颈问题。 本文针对上面的两个瓶颈问题提出了一种基于事务压
2、缩、 项目压缩， 同时可有效修剪 中间产生的频繁项目集的改进方法。通过使用 UCI 标准测试集Mushroom 测试集对其 进行了多方面的性能测试和比较， 由固定置信度下的不同支持度进行测试可知改进后的算 法较原算法在时间效率上提升了 20%-40%，极大的改善了算法的性能。最后，文章将改进 后的算法用在了高校成绩数据库中， 通过对高校成绩数据的分析与异常规则的提取， 为高 校课程制定提出了一些合理化建议。 关键词：关键词：数据挖掘，关联规则，AprioriTid 改进算法，数据预处理 关联规则挖掘算法 AprioriTid 算法的改善与研究 ii RESEARCH AND IMPROVEME
3、NT ON APRIORITID ALGORITHM OF ASSOCIATION RULES ABSTRACT Association rules mining technology is one of the most widely used techniques in data mining areas, it aims to extract inner and uneasily found links. The paper first introduces the related theory of association rules mining technology, analys
4、es the exist association rule algorithm-AprioriTid algorithm, and summarizes the exist two major bottleneck problems of current association rules mining: (1) For large database, the early formation of candidate Tid table may be larger than the original transaction database. (2) Every generating Tid
5、table records many meaningless item sets that cause heavy computer storage burden. This paper aims at above two bottleneck problems and presents an improvement algorithm that based on transaction compression and item sets compression, meanwhile, it presents a method that can simply and efficiently c
6、lip middle produced frequent item sets. Then it uses simple examples to analysis the theory examine. Secondly, the paper uses UCI standard test dataset to test and compare the improved algorithm performance, the improved algorithm saves 20%-40% time than the original algorithm, it can greatly improv
7、e the algorithm performance. Finally, the improved algorithm is used in the college scores database, through the analysis and extracting of the college grades data, it concludes some valuable advices. KEY WORDS: Data Mining, Association Rules, AprioriTid Improvement Algorithm, Data Preprocessing 河北工
8、业大学硕士论文 1 第一章第一章 绪论绪论 数据挖掘技术是一个融合了数据库技术、人工智能、神经网络、统计学、信息系统、数据可视化 等最新技术的科技研究成果。 经过若干年的发展， 数据挖掘技术已经具备了一套较为完整的理论体系， 并正朝着更深入的方向前进。在数据挖掘技术中，关联规则挖掘是数据挖掘的一个重要组成部分，它 主要是基于统计学的概率论知识，从而使得挖掘出来的规则更简单、易理解。本章主要介绍了关联规 则的研究背景和意义、 关联规则挖掘 AprioriTid 算法的国内外研究状况， 同时给出了本篇论文的主要 研究思路及论文框架。 1-1 研究背景及意义 1-1 研究背景及意义 （一）研究背景
9、（一）研究背景 近年来随着信息技术和互联网技术的广泛发展，数据挖掘技术已经引起了信息产业和计算机技术 领域的广泛重视。与传统的依靠收集、存储和简单数据处理方式不同，数据挖掘技术是一种面向数据 分析的技术， 重在寻求一种能够高效的对有用知识进行处理并最终提供给用户合理的决策支持。 目前， 数据挖掘研究主要集中在分类、聚类、关联模式挖掘和序列模式挖掘等，其中被称为“购物篮分析” 的关联规则挖掘技术是数据挖掘中最成熟和最关键的数据挖掘技术，它为海量信息转化为有用信息提 供了重要的技术手段。 自 1993 年关联规则问世以来， 关联规则技术得到了飞速发展， 现在它已经成为了一个具有实际应 用意义的数据
10、挖掘技术。关联规则挖掘捕捉的是项目间的内在联系，发现的是隐藏在表象背后的不易 被人们发现的信息， 且规则的表示形式简单易于理解， 它不需要用户有很多专业知识就可以进行预测。 同时，利用发现的规则可以帮助用户更好的进行市场管理、投资分析、决策支持和流程控制等，减少 用户不必要的消耗和浪费。随着关联规则技术的日益成熟，关联规则的应用领域也越来越多，它主要 应用在金融业、客户关系管理和零售业等盈利部门，关联规则在这些领域的成功应用为关联规则在其 它领域的发展提供了良好的借鉴，然而在教育行业这种非赢利机构的应用还比较少。 目前，关联规则的研究大都是以 Apriori 算法为基础进行的改进或扩展。使用
11、Apriori 算法提取 规则所产生的大量的候选项目集和频繁扫描数据库等缺点都有待于进一步去解决。而关联规则 AprioriTid 算法在一定程度上改善了 Apriori 算法的性能，本研究针对 Apriori 算法存在的缺点，希 望能够提出一种更好的、更有效率的关联规则挖掘算法，并将改进后的算法用到教育教学领域，以期 得到令人满意的规则解释。 （二）研究目标及意义 （二）研究目标及意义 通过对关联规则经典的 AprioriTid 算法的优缺点进行分析，提出了一种基于 AprioriTid 算法的改 进方法，提高规则的挖掘效率。并使用 UCI 标准数据集mushroom 数据集对算法进行性能测
12、试， 在分析了算法性能后，将改进后的 AprioriTid 算法用到高校成数据中，从而提取出课程属性之间存在 的关联性，并针对挖掘出来的结果对课程制定部门提出一些合理化的建议。 关联规则挖掘算法 AprioriTid 算法的改善与研究 2 1-2 关联规则国内外研究现状 1-2 关联规则国内外研究现状 1-2-1 国外研究现状 1-2-1 国外研究现状 关联规则挖掘技术是数据挖掘技术中最为流行的技术之一，在数据挖掘的发展中起着至关重要的 作用。自 Agrawal 等人在 1993 年首次提出关联规则挖掘问题并给出解决此问题最原始的算法 AIS1之 后，该问题得到了众多方面学者的密切关注，国际上
13、很多知名的研究机构都对数据挖掘技术投入了巨 大的精力，并已经取得了很大成效。目前，关联规则领域研究的内容在国外非常广泛，研究的重点也 已经由对方法的研究逐渐转向了对应用系统的开发。 关联规则算法方面的研究贡献主要有：1993 年由 Agrawal 等人首次提出的事务数据库中项集间的 关联规则挖掘问题，并于 1994 年正式提出关联规则挖掘领域的经典算法 Apriori 算法1。此后，许多 研究人员都对关联规则问题进行了大量的研究，包括对 Apriori 算法进行的改进以提高挖掘规则的效 率，如基于散列技术、事务压缩技术、划分技术和抽样技术的改进方法等2。基于散列技术的算法是 通过哈希技术来削减
14、数据集和候选项集，特别是对低阶的候选项集具有比较好的性能。基于数据集划 分的方法主要包括 Partition 算法、DIC 算法等，它主要通过数据集划分以节省访问外存的 I/O 开销。 抽样算法是通过对数据集进行随机抽样来产生频繁项目集的方法，如何找回边界的遗漏的频繁项目集 是抽样算法的关键。 这些方法在一定程度上改进了算法的性能， 但是都不能避免 Apriori 算法固有的多 次重复扫描数据库造成大量候选项集产生的问题。为了避免产生大量的候选项集，一些学者提出了不 产生候选项目集的 FP-growth 算法，但是当数据量很大时，如何将 FP-tree 完全放入内存中，如何构建 并分割树也是一
15、个难度很大的问题。 关联规则频繁项目集方面的研究工作主要包括：Gunopoulos 等人提出了最大频繁项目集问题3， 并对关联规则产生的上界复杂性给予了界定。 Zaki 等人在文献4-5中将一般的关联规则概念用于去挖掘 频繁项目集，又在文献6中引入了封闭频繁项目集的概念。Friedman 等人针对在多维空间内的点的撞 击问题进行了关联规则频繁项目集的挖掘与研究7。由于频繁项目集的挖掘是关联规则中最耗时的工 作，因此大多数算法都是围绕着这点所进行的改进或扩展8-9。 随后，又产生了许多扩展的关联规则，如基于约束的关联规则挖掘，多层次的关联规则挖掘以及 并行算法挖掘等都是目前比较热点的研究方向10
16、。并行算法的主要优点是可以充分运用并行系统增强 运算能力，通过有效分割挖掘任务进而提高挖掘算法的效率。另外，将一些评测参数（如作用度、兴 趣度等）引入到关联规则中，以及融合了 OLAP 技术的关联规则挖掘算法11-12等近年来也成为了主要 的研究方向。 融合关联规则技术的应用系统的开发一直是国外数据挖掘领域专家们研究的热点。例如，美国斯 坦福大学实验室开发出了大量商用数据挖掘系统，著名的基于数据立方体的联机分析挖掘 DBMiner 系统13，它嵌入了很多挖掘算法，此系统还可以和目前许多主流技术（如 SQL Sever、Oracle 等）紧 密结合，充分发挥数据挖掘技术的先进性。还有 IMB 公司的 Almaden 实验室所进行的 Quest 项目也包 含了对关联规则、分类和序列模式的研究14，典型产品有：在 IBM DB2 平台下的系统 DB2Intelligent Miner for Data 系统及 Windows NT 下的类似数据挖掘系统等。此外，美国宾西法尼亚大学的研究组通 河北工业大学硕士论文 3 过使用
