《关联规则增量式更新算法研究》由会员分享，可在线阅读，更多相关《关联规则增量式更新算法研究（48页珍藏版）》请在金锄头文库上搜索。
1、合肥工业大学 硕士学位论文 关联理论视角下的隐喻理解与翻译以围城为例 姓名：涂明 申请学位级别：硕士 专业：材料学 指导教师：汪家权 20100301 关联规则增量式更新算法研究关联规则增量式更新算法研究 摘 要 摘 要 数据挖掘作为一种从海量数据背后获取知识的技术，如今已得到了广泛的 应用。关联规则挖掘是数据挖掘的一个重要分支，也是最先研究的问题之一。 Apriori 算法是关联规则中的经典算法，其他的很多算法都是以此为基础进行 改进的，且大多数算法都是针对静态数据库。 在实际应用中，数据库中的数据经常需要变动，如果用以前的算法来挖掘 规则，则是对更新后的数据库重新运行一次算法，这样效率将非
2、常低，因此关 联规则的增量式更新算法出现了。关联规则增量式更新算法有两个典型代表： FUP 算法和 IUA 算法,本文只对 FUP 算法进行讨论，在分析研究 FUP 算法的不足 之后，提出了一种新的增量式更新算法 TMFUP 算法，本算法采用的数据格式是 垂直型数据格式，和 FUP 算法相比，可以显著的减少扫描原数据库的次数，算 法的执行效率较高。 关键词关键词：数据挖掘；关联规则；增量式更新；垂直型数据格式 RESEARCH ON INCREMENTAL UPDATING ALGORITHM FOR MINING ASSOCIATION RULES ABSTRACT Data Mining
3、as a technology for getting valuable information and knowledge from mass of data , theses days has been widely used . Association Rules Mining is an important branch of Data Mining , also is the first one of the issues . Apriori algorithm is a classical one in Association Rules Mining , many other a
4、lgorithms are on the basis of it for improve- ment , and most algorithms are aimed at a static database . In practical applications , the data of the databases often needs to change , if use the previous algorithm to mine the rules , it will re-run the algorithm to the updated database, so the effic
5、iency will be very low . Consequently , the Incremental Updating Algorithm for mining Association Rules appeared . There are two typical examples : FUP algorithm and IUA algorithm in the Incremental Updating Algorithm for Minning Association Rules . In this paper , we just discuss FUP algorithm . Af
6、ter analyzing and studying the FUP algo- rithms defect , We proposed a new Incremental Update algorithm: TMFUP algorithm. The data format in the algorithm is vertical , compared with FUP algorithm , TMFUP algorithm can significantly decrease the number of scaning the original database , and the algo
7、rithms implementation is more efficient. Key words: Data Mining ; association rule ; incremental updating ; vertical data format 插图清单 插图清单 图 1.1 数据挖掘的过程 7 图 3.1 实例计算过程 . 15 图 4.1 TMFUP 简单的实例流程 . 26 图 4.2 实例分析 . 32 图 4.3 实验结果对比图 . 33 表格清单 表格清单 表 4.1 水平型数据格式 . 22 表 4.2 垂直型数据格式 . 23 独 创 性 声 明 独 创 性 声 明
8、 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所 知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得 合肥工业大学 或其他教育机构的学位或证书而使用过的材料。与我一同 工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名： 涂 明 签字日期： 2010 年 4 月 27 日 学位论文版权使用授权书 学位论文版权使用授权书 本学位论文作者完全了解 合肥工业大学 有关保留、使用学位论文的规定，有权保留并向国 家有关部门或机构送交论文的复印件和磁盘， 允许论文被查阅和借阅。 本人
9、授权 合肥工业大学 可 以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手 段保存、汇编学位论文。 (保密的学位论文在解密后适用本授权书) 学位论文作者签名：涂明 导师签名：张公让 签字日期： 2010 年 4 月 27 日 签字日期： 2010 年 4 月 27 日 学位论文作者毕业后去向： 工作单位： 电话： 通讯地址： 邮编： 40 特别声明特别声明 本学位论文是在我的导师指导下独立完成的。在研究生学习期间，我的导师要 求我坚决抵制学术不端行为。在此，我郑重声明，本论文无任何学术不端行为，如 果被发现有任何学术不端行为，一切责任完全由本人承担。 学位论文
10、签名：涂 明 签字日期：2010 年 4 月 27 日 1 第一章 绪 论 第一章 绪 论 数据库技术和计算机网络技术的迅速发展，使得人们积累的数据量急剧地 增长，人们已经被淹没在数据的海洋中，面对如此海量的数据，如何从中提取 出对我们有用的信息，这是一个人们迫切需要解决的一个问题。由于传统的数 据分析工具无法处理如此海量的数据，因此在巨大需求的推动下，数据挖掘 (Data Mining)技术应运而生。 本章在1.1节介绍课题的研究背景，1.2节介绍课题的研究现状，1.3节阐述 对本文的研究工作和全文的组织结构。 1.1 课题的研究背景 1.1 课题的研究背景 随着计算机技术、网络技术以及通讯
11、技术的迅速发展和普及，信息技术将 我们领进了全新的信息社会。数据库应用的范围、规模和深度不断扩大，产生 的数据规模越来越大，在社会的各个领域中都应用了大量的数据库，做出决策 所需要的数据量也变得越来越巨大。据不完全统计，2000年全球数据存储容量 约为300万TB，到2008年，这一数字已经飙升至上亿TB。在广义上看，数据有三 种不同的形式：数据(Data)、信息(Information)和知识(Knowledge)，计算机 存储技术和网络技术的发展加速了人们收集数据的范围和容量，导致了人们现 在面临的“数据爆炸而信息匮乏”现象。在这样的情形下，人们面临的主要问 题已经不再是没有充分的信息来供
12、我们选择，而是在面对如此庞大的信息，如 何更为有效地利用它们，并且找到蕴含于这些信息之中的有价值的知识宝藏。 数据量的急剧增长，使得现有的数据分析工具已无法适应新的需求。当前 的数据库系统技术无法发现隐藏在海量数据背后的知识和规则，而且无法根据 现有的数据去预测未来的发展趋势。因此，人们对联机决策和分析等高级信息 处理技术的要求越来越迫切。由于有了强大的需求，各企业开始认识到有效地 解决大容量数据的利用问题具有巨大的商机。学者们开始研究如何从大容量数 据集中获取有用信息和知识的方法，在这样的背景下数据挖掘(Data Mining) 技术应运而生，并得以在社会生活的各个领域蓬勃发展。一般地，在那
13、些存在 着海量数据的领域，数据挖掘技术都可以一显身手，除了在商业决策、企业管 理、金融分析和科学研究等领域可以见到数据挖掘技术的应用外，还可以在制 造业、司法、医学、交通、科教、国防、新闻媒体及互联网等行业或领域应用 这一项技术。数据挖掘将信息分析处理技术推到了一个更高的阶段。比尔-盖茨 曾预计，数据挖掘技术将是今后计算机技术发展的一个极其重要的方向 1。 由R.Agrawal等人首先提出来的关联规则挖掘是数据挖掘最先开始研究的 问题之一，随着数据库中数据的大量积累，人们对于从数据库中挖掘关联规则 越来越感兴趣。从商业事务记录中发现有趣的关联关系，可以帮助制定许多商 2 业决策。 在实际应用中
14、，数据库中的数据经常发生变动，常常需要对用于挖掘的数 据进行增加、删除等操作，或者，用户也常常需要通过调整最小支持度和最小 可信度这两个阈值来得到感兴趣的关联规则。这就是关联规则的增量式更新问 题，此时，如果按照传统的挖掘方法，是用新的数据集和阈值按原来的挖掘算 法重新再做一次挖掘运算，但如果这样的话，那么上一次挖掘得到的的计算结 果就浪费了。因此，如何充分利用前一次的挖掘结果，如何高效地解决关联规 则的更新，这样的一些问题成为了关联规则挖掘的一个重要研究方向。 1.2 课题的国内外研究现状 1.2 课题的国内外研究现状 数据挖掘起源于从数据库中“知识发现”(Knowledge Discove
15、ry in Da- tabase，简称KDD)，它的首次出现是在1989年美国底特律举办的第十一届国际 联合人工智能学术会议“数据库中的知识发现”专题讨论会上。自1989年的第 一届专题讨论会之后，在1991、1993、1994年又连续举办了KDD专题研讨会，从 1995在加拿大召开的第一届“知识发现与数据挖掘”国际会议开始，KDD研讨会 发展成为每年一次的国际性学术大会。会议较全面地探讨了数据挖掘与知识发 现(Data Mining and Knowledge Discovery，DMKD)的基础理论、新的发现算法 以及一些实践应用等。在1998年美国纽约举办的第四届“知识发现与数据挖掘”
16、国际学术会议上有30几家软件公司展示了他们开发的关于数据挖掘方面的软件 产品。IEEE、SIGMOD、ACM、IFIS、VLDB等学会、期刊都把DMKD列为会议议题或 出版专刊 2。 到目前为止，对关系数据库和事务数据库进行知识发现和数据挖掘的研究 与应用已取得了一些成果，其中最有影响的一些算法有：加拿大Simon Fraser 大学韩家炜教授的概念树提升算法 3、IBM公司R.Agrawal的关联规则算法4、 澳大利亚的J.R.Quinlan教授的分类算法 5、密西根州立大学Erick Goodman的 遗传算法等。此外在应用方面，IBM、SAS、SPSS、Oracle、SGI等著名的软件公 司都在数据挖掘领域投入了巨资进行研发，开发出了不少软件产品，如：IBM Intelligent Miner、 SAS Enterprise Miner、 SPSS PASW Modeler(以前叫Clemen- tine)
