关联规则的相关算法研究基于Apriori和FPgrowth算法

《关联规则的相关算法研究基于Apriori和FPgrowth算法》由会员分享，可在线阅读，更多相关《关联规则的相关算法研究基于Apriori和FPgrowth算法（56页珍藏版）》请在装配图网上搜索。

1、学校代码：10491 研究生学号：120080940 中国地质大学硕士学位论文关联规则的相关算法研究-基于Apriori和FP-growth算法硕 士 生：学科专业：计算机软件与理论指导教师：二一年五月A Dissertation Submitted to China Universityof Geosciences for the Master Degree of Computer Software and TheoryResearch on Association Rules Mining Algorithm-base on Apriori and FP-growthMaster Cand

2、idate：LIANG WeiMajor：Computer Software and TheorySupervisor：SUN BinChina University of GeosciencesWuhan 430074 P. R. China中国地质大学（武汉）研究生学位论文原创性声明本人郑重声明：本人所呈交的硕士学位论文关联规则的相关算法研究-基于Apriori和FP-growth算法，是本人在导师的指导下，在中国地质大学（武汉）攻读硕士学位期间独立进行研究工作所取得的成果。论文中除已注明部分外不包含他人已发表或撰写过的研究成果，对论文的完成提供过帮助的有关人员已在文中说明并致以谢意。本人

3、所呈交的硕士学位论文没有违反学术道德和学术规范，没有侵权行为，并愿意承担由此而产生的法律责任和法律后果。学位论文作者（签字）： 日期：年月日作者简介梁伟，男，壮族，1976年1月出生于广西壮族自治区崇左市。2008年9月进入中国地质大学（武汉）信息工程学院攻读硕士学位，专业为计算机软件与理论，研究方向为数据库技术和数据挖掘。至今已经修完全部课程，共计15门课程，其中学位课程10门，选修课程5门，各门课程成绩合格，总学分为28分，各科平均成绩为72分。在硕士研究生学习阶段，认真学习专业知识，阅读大量专业文献，以第一作者在公开刊物发表论文两篇：关联规则算法探讨-企业技术开发（CN 43-1172/

4、TB ，2009.10）基于MYSQL的SQL注入问题研究-科教导刊（CN 42-1795/N，2009.12）关联规则的相关算法研究-基于Apriori和FP-growth算法硕士生：梁 伟 导师：孙 斌摘 要数据挖掘是当今人工智能和数据库研究方面最富活力的领域。数据挖掘是指从大量的数据中发现潜在的、有用的知识的过程。关联规则数据挖掘是数据挖掘的一个主要研究内容，而如何快速发现频繁项集是关联规则数据挖掘算法的核心问题。本文讨论了数据挖掘和关联规则的一般理论，包括数据挖掘的概念、任务、模式以及数据挖掘的应用和发展趋势。深入研究了关联规则挖掘算法，分析了关联规则挖掘中经典的Apriori和FP-

5、growth算法，并总结了Apriori和FP-growth算法中存在的问题。针对Apriori算法的效率问题，从两个角度进行改进：(1)降低候选项目集中候选项产生的数量；(2)减少扫描数据库的次数。给出了一种较为高效的关联规则挖掘算法。算法的主要思想是在扫描数据库的同时把支持每个项目的事务都标记出来，采用一种新的方法生成所有的频繁集。该算法只需对源数据库进行一次扫描就可以找出所有的频繁集，并通过裁剪候选集的方法达到减少候选项数目集的目的。这样做不但降低了算法的I/O负荷，而且减少了时间开销，具有很高的效率。最后，将基于关联规则的数据挖掘改进算法方法应用到学生考试成绩管理中，对挖掘结果进行了分

6、析，并提出了指导意见。本文的工作虽然取得了一定的成果，但尚有大量问题有待于进一步研究，比如，关联规则挖掘应用系统的设计；关联规则有趣度的研究以及如何将挖掘结果友好地呈现给用户。关键词：数据挖掘 关联规则 频繁集 支持度 可信度Research on Association Rules Mining Algorithm-base on Apriori and FP-growthMaster Candidate：LIANG Wei Supervisor：SUN BinABSTRACTData Mining is one of the most active research fields,espe

7、cially in the fields of artificial intelligence and Database.Data Mining is a kind of process that reveals potential useful knowledge from massive data.The association rules mining is a main research aspect of data mining.And the discovery of the frequent item sets is a key problem of the associatio

8、n rule mining algorithm.The Data Mining is discussed generally in this paper，including its concepts, patterns,applications and development trend.Apriori algorithm and FP-growth algorithm are researched and analysed deeply,which are classic of the association rule mining algorithms.And then summarize

9、s the problems existing in there two algorithms.For improving the existing poor efficiency of Apriori algorithm,this paper expounds some schemes in two aspects. One sheme is reducing the candidate item sets,and the other is decreasing the times spending in scanning Database.Then,a more efficient alg

10、orithm for association rule mining is presented.The main idea of the algoritnm is to mark all the transactions supporting each item in scanning Databese.The new algorithm adopts a unique way to generate the frequent item sets.It can mine all the frequent item sets by scanning the source Database onl

11、y once and reducing the candidate item sets depending on the pruning.It not only decreases the bear of I/O,but also reduces the execution time,and then got high efficiency.Finally,the new method based on association rules is applied into the Management of student test scores ,the mining result is an

12、alyzed,and instructive opinion is proposed. Although the certain results has been obtained in this paper,there are still many questions to be studied hardly,such as,designing the association rule mining application system,studying the interesting association rules and presenting the mining results m

13、ore friendly to the user. Keywords：Data Mining Association Rules Frequent Item Set Support Confidence目 录第一章 绪论11.1课题的研究背景11.2数据挖掘中的关联规则21.3关联规则数据挖掘的研究现状21.3.1国外研究现状21.3.2国内研究状况31.3.3关联规则新进展41.4本文主要内容41.5本文的组织结构5第二章 数据挖掘及关联规则概述62.1数据挖掘62.1.1数据挖掘的产生和发展62.1.3数据挖掘的过程72.1.4数据挖掘的主要方法82.1.5数据挖掘的发展趋势82.2关联规

14、则92.2.1啤酒和尿布问题92.2.2基本概念92.2.3基本模型102.2.4关联规则的主要应用102.2.5关联规则的分类112.2.6关联规则的挖掘过程122.3关联规则挖掘算法分类122.3.1关联规则算法原理122.3.2经典关联规则算法122.3.3改进的关联规则算法132.4本章小结13第三章 关联规则的经典算法143.1 Apriori算法143.1.2 Apriori性质143.1.3算法描述153.1.4算法分析153.1.5算法步骤163.1.6示例说明163.2 FP-tree频集算法183.2.1算法的基本思想183.2.2算法的主要步骤193.2.3算法描述193

15、.2.4算法示例说明203.2.5算法分析223.3本章小结22第四章 改进的关联规则挖掘算法234.1算法改进思想234.2算法的主要基本步骤244.3算法描述254.4算法实例254.5算法评价284.5本章小结29第五章 改进算法在学生成绩教学指导的应用305.1学生成绩教学指导现状305.2改进算法在成绩管理中的应用315.3本章小结37第六章 结束语38致 谢40参考文献412010.5中国地质大学硕士学位论文41第一章 绪论数据挖掘技术是上个世纪90年代初开始，在国内外迅速发展起来的一门交叉学科，该新兴学科涉及到计算机、数据库、统计学、人工智能与机器学习等多个领域。数据挖掘领域融合

16、了各个学科领域的技术和成果，它的表现方法多种多样。信息技术的快速发展及计算机的应用普及和数据存储技术的迅猛发展，大大提高了人们获取数据的能力，由此使得各个行业积累了大量的专业数据，数据挖掘就是利用各个学科的综合技术对海量数据进行分析处理。1.1课题的研究背景在过去的三十多年里，随着计算机硬件技术、数据收集技术和数据存储技术的飞速发展，各个学科及各行各业都逐步建立起了各自的数据库体系。在这些专业的大型数据库中，存放了海量的数据，如何才能有效利用这些数据，使其能为我们的生产实践所利用，成为人们所关注的问题。但是，面对堆积成山的丰富的数据资源来说，人们缺乏高效有力的分析手段和分析工具，于是就必然出现

17、“数据丰富而信息贫乏”的尴尬状况。很明显，数据库操作系统的查询和检索虽十分方便，但对于应付这些海量数据而言也显得无能为力，虽然之后伴随着数据仓库出现的在线分析OLAP技术具有总结、概化及聚集等强大功能，且可从不同角度来观察、分析数据，并能进行多维分析和决策支持，但OLAP技术始终不能对数据进行更深层次的分析，发现和挖掘大量数据背后所隐藏的规律和知识。俗话说，需要是发明之母，在这种形势下，数据挖掘的产生就成为了必然。数据挖掘是指从大量的数据中提取人们感兴趣的知识，这些知识是隐含的、事先未知的、并且是潜在有用的信息。数据挖掘是计算机技术研究中的一个很有应用价值的新领域，目前已经成为国际上数据库和信

18、息决策领域中最前沿的研究方向之一，引起了学术界和工业界的广泛关注。数据挖掘也叫数据挖掘中发现知识（KDD）。KDD一词首次出现在1989年8月举行的第11届国际联合人工智能学术会上。随着KDD在学术界和工业界的影响越来越大，国际KDD组委会于1995年把专题讨论会更名为国际会议，每年召开一次，其规模也由原来的KDD专题讨论会发展发展成为现在的国际性学术大会。此外，国际上还有许多数据挖掘年会，例如PAKDD、PKDD、SIAM-Data Mining等重要国际会议。另外，数据库、人工智能、信息处理、知识工程等领域的国际学术刊物也纷纷开辟了KDD专题和专刊。KDD作为在对大规模数据库进行分析的重要

19、工具，对它的研究已经成为数据库及人工智能领域研究的一个热点1。按照挖掘结果模式、数据挖掘任务可以分为两大类：描述性数据挖掘和预测性数据挖掘。描述性数据是对数据的一般特性进行描述。预测性数据挖掘是通过对现有数据进行分析推理，对未来的行为进行预测。具体可分为概念描述、关联规则分析、分类分析、聚类分析、异常分析及演化分析等。 1.2数据挖掘中的关联规则 1993年，Agrawal等人首次提出了关联规则问题，关联规则所反映的是某事物与他事物之间的相互依存性和关联性。假如有两个或多个事物之间有某种关联性，那么一个事物的发生状况可以通过其他事物的属性预测出来。最为简单和经典的关联规则发现问题就是对超级市场

20、里的顾客的购物记录，即购物篮数据进行分析，通过分析顾客所购买的货物的相关性来发现顾客的购买习惯，由此来制定有针对性的营销策略，提高超市商品销量。关联规则最经典的应用案例就是美国沃尔玛超市的“尿布与啤酒的故事”。关联规则数据挖掘的目的是发现数据中的规律性，比如在超级市场中顾客买某物品的同时还会同时购买哪些物品，买一台电脑后会否紧跟着购买电脑软件等。从专业的角度上来说，关联规则数据挖掘就是要从事务数据库中的项集和对象中挖掘出频繁模式、关联性、因果关系及关联规则。关联规则挖掘在数据挖掘领域是一个研究热点，从二十世纪九十年代初至今的二十多年时间里一直被广大专家、学者广泛研究。他们的研究工作主要是对原有

21、的算法进行改进和优化，通过算法优化来提高算法的挖掘效率。随着关联规则挖掘技术的不断发展和成熟，关联规则也得到了很好的应用，其应用的范围也由最初的购物篮扩展到网站路径优化、网络行为挖掘、网络人侵检测等领域。关联规则的理论研究的内容也从最初的频繁模式挖掘扩展到最大模式挖掘、增量挖掘等等。1.3关联规则数据挖掘的研究现状1.3.1国外研究现状R.Agrawal等人提出的关联规则数据挖掘问题因其可发现统计学和人工智能无法发现的数据项之间或者属性之间隐藏的属性，这说明它很有研究价值，因此国外众多学者和专家针对关联规则挖掘问题作了大量的研究和探索工作。Apriori是关联规则算法中最具代表性的算法，对Ap

22、riori算法的运行效率改进是一个很重要的问题，此后，为了提高Apriori算法的效率，很多研究者提出了关联规则相关的改进算法：Savasere等人提出了分割的关联规则挖掘算法，分区算法扫描数据库一次生成所有潜在的大项目集，然后在对数据库的第二次扫描中，所有的项目集的支持度被确定。Park等人于1995年提出DHP的算法，DHP算法利用一个额外的哈希表，旨在限制产生尽可能多的候选项集。Toivonen于1996年提出了抽样算法，该算法通常只需要扫描遍数据库，在最坏的情况下也只是需要扫描2次数据库。Brin等人于1997年提出动态项集计数（DIC）的算法，通过对被划分成若干带有起始点标志的模块的

23、数据库进行反复扫描。相较于Apriori算法，DIC算法可以在任何起点标志处添加新的候选项目集，无需重新扫描整个数据库。1998年Lin等人提出了钳形搜索（Pincer-Search）算法，该算法能有效发现最大频繁集。2001年，Yang等人提出了一个高效的基于散列的方法发现的最大频繁集（HMFS）算法，该算法融合了DHP算法和钳形搜索（Pincer-Search）算法的优点。此外遗传算法也适用于关联规则挖掘，算法可以生成对关联规则挖掘合适的阈值。 改进的关联规则算法提高了Apriori算法的效率，大部分改进算法的研究一般都集中在设置最小支持度和最小置信度以实现挖掘出更客观和更有效的关联规则问

24、题。越来越多的关联规则研究采用多元化的算法研究，如将遗传元启发式方法，蚁群算法和系统，与Apriori算法结合起来研究。1.3.2国内研究状况目前，国内对关联规则的研究大多是围绕最大频繁项目集生成问题来展开的，对原有算法加以改进，主要目的是为了实现空间、时间的有效充分利用。具体方法一般是减少数据库扫描次数，以及对候选项集进行压缩处理。国内还有学者引入其他相关理论对关联规则进行研究，通过引入先进的理论，丰富和深化了关联规则研究内容，算法的有效性得到了提高。比如引入粗糙集概念后，可以使关联规则发现的模式的解释能力和精确度得到提高。引入聚类方法解决了提取数量关联规则过程中出现的连续属性离散化的问题。

25、引入神经网络概念并提出在数据库中通过相互激活和竞争机制来发现关联规则。从研究形式上看，由购物篮模式开始，国内对关联规则的研究不断深入，出现了多种不同形式的关联规则研究，从单维、单层、布尔关联规向多维、多层及加权等复杂形式扩展。关联规则挖掘指导思想也有了新的变化，提出了概念指导的关联规则的挖掘算法和基于概念格的关联规则的提取算法。国内比较有影响力的算法是冯玉才等人提出的 UA算法和朱玉全等人提出的FIUA算法等关联规则的增量式更新算法。在国内，大多数数据挖掘方面的研究项目主要是由政府资助，关联规则的具体研究和应用主要在各大研究所和高校中进行。主要研究成果有：（1）多策略数据挖掘平台MSMiner

26、系统，它是由中科院计算机研究所的智能信息处理重点试验室研制开发的，该系统集成了关联规则挖掘算法；（2）ARMiner数据挖掘系统，由复旦大学研制开发，该系统集成了基于Apriori的改进的关联规则算法。随着数据挖掘技术的迅速和电子商务迅速发展，目前国内对关联规则的个性化研究，基于关联规则的个性化推荐问题已成为研究热点，关联规则的个性化推荐技术已经应用到各大B2C商务网站中。1.3.3关联规则新进展时间序列数据存在于社会的各个领域，比如自然科学研究数据：天文观测、气象图像等方面的数据；患者病例数据:患者每次去医院看病的病情记录，心电图、B超等扫描仪器的数据记录等2；金融业和商业方面的交易数据：股

27、市每天的交易价格及交易量、超市每种商品的销售情况等等。可以说时间序列无处不在。随着信息技术的迅猛发展，计算机技术及存储设备的存储量日益增大，数据收集能力不断得到提高，因此时间序列数据库也会变得越发膨胀，因此，数据挖掘领域中对时间序列的关联规则挖掘的研究显得越发重要。相对于关系数据库中关联规则挖掘和分类规则挖掘等相对比较成熟的部分而言，时间序列关联规则挖掘的研究是数据挖掘研究领域中的较为新的一个分支，目前，国际上对于时间序列的关联规则挖掘的研究逐步成为一个新的热点，但国内在这方面的研究文献尚不多见，只有某些学者从理论框架的角度对事态关联规则挖掘做过简单介绍和分析。时间序列的关联规则数据挖掘技术自

28、上个世纪90年代中期以来有了快速的发展。它由最初的相似性分析到目前的人工智能的多学科交叉研究，至今已出现多个研究方向。时间序列的一个最基本的且相对比较困难的问题是对其相似性的研究。时间序列的相似性，是指测定两个已知的时间序列的行为曲线的相似性。由于时间序列往往来自于实际，时间序列数据库来自于各行各业，所以相似性的测量标准和要求并非完全一致，因此使得相似性问题的研究比较困难。关联规则挖掘技术不断得到发展，产生了各种挖掘技术，这些技术在相似性的基础上也不断地被应用于时间序列数据库，如对时间序列进行聚类、分类，产生关联规则等等。时间序列研究的另一个基础问题就是时间序列的索引问题，即给定了一个时间序列

29、集Q，索引技术是指能够在序列集中尽快地找到与给定的时间序列q最为相似的序列子集q1, 索引技术也进行相似性计算。无论是对时间序列进行相似性研究还是索引技术研究，对时间序列进行有效描述，仍是提高计算效率的一个的关键途径。关于时间序列的关联规则挖掘技术研究领域，除了对相似性的研究以外，主要还有对时间序列模式挖掘的研究，这方面研究包括时态模式挖掘和趋势预测。时态模式挖掘的一个关键技术是关联规则的挖掘技术，而趋势预测采用的主要技术是分类规则的挖掘技术。主要技术流程是：首先对时间序列数据进行预处理，然后从数据库中抽取出关键的、对时间序列的发展趋势影响较大的预测属性，将抽取出的属性组成属性集，抽取的预测属

30、性可以表征时间序列的某种特性，但是这种特性又与时间没有任何关系，故对时间序列进行行为趋势的分类预测可采用普通的静态规则挖掘工具。1.4本文主要内容本文的重点研究内容是数据挖掘技术中的关联规则挖掘算法。研究分析国内外在关联规则算法领域所取得的一些成果，重点深入研究和分析了Apriori算法和FP-growth算法，概括和总结这两个经典算法的优点和存在问题。在已有基于这两种算法的改进算法基础上，针对Apriori算法的自身难以克服的瓶颈问题提出了一种改进的算法。在后面的章节中将结合当地某学校学生的考试成绩情况，应用本文提出的改进关联规则算法，对学生的考试成绩进行挖掘，通过改进的关联规则算法分析挖掘

31、出学生考试成绩为优秀的各门课程间可能隐藏的各种关联关系，为教师以后的教学工作中指定相应的教学计划或方案提供帮助和参考。1.5本文的组织结构本文共分为六章，组织结构如下：第一章为绪论，介绍数据挖掘和关联规则研究背景，概括了关联规则挖掘的发展历程和关键技术，总结分析关联规则数据挖掘的国内外研究现状及发展趋势。第二章 对数据挖掘和关联规则作了详细的概述。详细介绍了数据挖掘的相关概念和基本理论及发展趋势，重点介绍了关联规则的基本概念、基本性质、基本模型及关联规则算法的分类，并通过简单例子来描述关联规则。为后面的关联规则算法研究提供理论支持。第三章 介绍关联规则数据挖掘的两个经典算法Apriori和FP

32、-growth算法。分别介绍两个算法的基本概念，简述了算法的基本思想，给出了算法的基本步骤，分析和概括了算法的特点。并通过示例对算法加以描述。第四章 给出本文一种改进了的关联规则算法。分析改进算法的理论依据和理论基础，并作了算法原理分析，对比分析了改进算法和经典算法的执行效率，最后通过实验验证算法的效率问题。第五章 结合某学校学生的考试成绩，应用本文改进的算法对考生成绩进行关联分析。第六章为结束语，对本文作了综述和总结。第二章 数据挖掘及关联规则概述本文着重阐述的是关联规则挖掘算法问题，在深入讨论和分析关联算法之前，本章首先介绍数据挖掘和关联规则的基础理论知识。2.1数据挖掘数据挖掘，就是从大

33、量的、不完全的、有噪声的、模糊的、随机的实际应用数据中发现隐含的、规律性的、人们事先未知的，但又是潜在有用的且最终可以被理解的信息和知识的意义重大的过程。数据挖掘作为一门新兴的、多学科交叉的学科正在被应用到各个工作和生产领域，正在各行各业的以信息分析为基础的决策支持系统活动中扮演着越来越重要的角色。2.1.1数据挖掘的产生和发展1989年8月，在第十一届人工智能联合会议专题研讨会上首次提出了基于数据库的知识发现技术，即Knowledge Discovery in Database（KDD）,KDD技术涉及多个学科领域：包括机器学习、统计学、模式识别、人工智能、数据库、专家系统、知识获取、可视化

34、技术及高性能计算等。1995年，数据挖掘(Data Mining)的概念在美国计算机年会（ACM）上首次被提出，数据挖掘被定义为从数据库中发现那些具有隐含性、未知性、但是具有潜在使用性的信息的过程。由于数据挖掘是数据库中知识发现KDD过程中最为关键的步骤，所以在实际工作、生产应用当中，人们往往认为数据挖掘和KDD这两个术语是同一概念。促进数据挖掘的诞生、发展及应用的原因是很多的，但最主要的是四个因素：超大规模数据库的出现、先进计算机技术、经营管理的需要和对这些数据的精深计算能力。（1）超大规模数据库的出现大规模数据库，尤其是数据仓库的出现，促进了数据挖掘的迅速发展应用。依靠计算机自动收集的各种

35、业务处理数据，使数据挖掘技术有了生存的基础。若没有大规模数据库，数据挖掘技术就没有挖掘对象。（2）先进计算机技术在短短几十年，计算机技术发展日新月异，特别是网络技术并行处理体系的发展，计算机体系结构的计算能力更强了、速度更快了。先进的计算机技术水平成为促进数据挖掘技术发展的第二个重要因素。（3）经营管理的需要进入21世纪，全球经济一体化进程加快，企业竞争越来越大，管理者希望能从企业积累的大量历史数据中找到应付激烈竞争的方法，希望能从这些数据中找到解决经营管理中遇到的各种棘手问题的良方。对于决策者，希望能用工具从历史数据中找到原因，快速挖掘出对经营管理有用的各种信息，解决市场压力。（4）对数据挖

36、掘的精深计算能力大规模数据的挖掘需要复杂的、精深的计算能力，主要基于统计学、信息论、认识论、集合论和人工智能等各个学科理论。随着这些数据挖掘方法和技术不断发展和成熟，产生了许多具有学科特点的数据挖掘应用领域。正是这些精深的计算能力，成为了促进数据挖掘诞生和发展的重要因素。数据挖掘是计算机科学技术和信息科学技术发展到一定阶段的必然产物，也是拥有大规模数据库、高效计算能力、经营管理的压力和有效的计算方法后的产物，数据挖掘就是从存放在大型数据库、数据仓库或其他信息库中的海量数据中发现、挖掘出有用知识的一个过程。2.1.2数据挖掘系统分类由于应用领域不同，数据挖掘系统挖掘的数据的类型不同，按照不同的分

37、类标准，可以对数据挖掘系统进行不同的分类。（1）按应用面分类可分为：通用的数据挖掘系统和特定领域的数据挖掘系统两种。（2）按所处理的数据类型分类可分为：结构化数据挖掘系统、半结构化数据挖掘系统及非结构化数据挖掘系统三种。（3）按所挖掘的规则类型分类可分为：关联规则则挖掘系统、判别规则挖掘系统、特征规则挖掘系统、分类规则挖掘系统、进化规则挖掘系统、聚合规则挖掘系统及误差分析规则挖掘系统七种。（4）按所发现的知识的抽象层次分类可分为：一般性知识挖掘系统、原始层知识挖掘系统及多层知识挖掘系统三种。（5）按所利用的数据挖掘技术分类可分为：自制的知识挖掘系统、验证驱动挖掘系统、发现驱动挖掘系统、交互式数

38、据挖掘系统四种。（6）按所处理的数据类型分类可分为：关系数据挖掘系统、空间数据挖掘系统、面向对象数据挖掘系统、多媒体数据挖掘系统、时域数据挖掘系统、文本数据挖掘系统、Web数据挖掘系统七种。2.1.3数据挖掘的过程（1）问题定义进行数据挖掘，首先必须分析应用领域，包括两方面：应用中涉及的各种知识和应用的目标。（2）建立主题目标数据挖掘要有一个明确的主题目标，该主题目标决定此后数据挖掘要进行的各种操作。（3）准备数据包括两方面：一是从多个数据源去整合数据挖掘所需要的数据；二是如何从现有数据中衍生出所需的指标。具体包括数据抽取、数据清洗、数据变换、数据规约及数据质量分析等步骤（5）建立模型在问题进

39、一步明确，数据结构和内容进一步调整的基础上，就可以形成知识的模型。对历史数据建立一个预测模型，然后再用另外一些数据对这个模型进行测试。建立模型是一个反复的过程。（6）模式评价和验证数据挖掘结果所得到的模式对我们来说可能并没有实际意义，也可能没有什么实用价值，还有可能错误地反映数据的真实意义，更严重的是可能在某些情况下会与事实相悖，因此对数据挖掘的结果进行评估是非常有必要的，通过评估来确定数据挖掘是否存在偏差，偏差是否在允许的范围内，并判断挖掘结果正确性。2.1.4数据挖掘的主要方法（1）概念/类描述:特性化和区分，归纳，总结和对比数据的特性。（2）关联分析发现数据之间的关联规则，规则展示属性值

40、频繁的在给定的数据中所一起出现的条件。（3）分类和预测通过构造模型或函数来描述和区别类或概念，预测类型、标志未知的对象类。（4）聚类分析将类似的数据归类到一起，形成一个新的类别进行分析。2.1.5数据挖掘的发展趋势数据挖掘技术相对于数据库技术来说还是比较新，一直被认为是很有前途的学科，随着统计学、计算机科学、人工智能等相关学科的发展，同时受到用户不断提出的新问题和需求的刺激，数据挖掘技术必然得到不断发展。数据挖掘技术在未来的主要发展方向为：（1）嵌入式数据挖掘（2）用于垂直应用的数据挖掘包（3）产品合并（4）预言模型标记语言PMML（Predictive Model Markup Langua

41、ge）（5）对异构数据的挖掘（6）算法的效率及可扩展性（7）可视化数据挖掘技术（8）多抽象层交互挖掘知识（9）隐私保护及数据安全（10）Web数据挖掘2.2关联规则若两个或多个变量的取值之间存在某种规律性，就称为关联。关联规则就是寻找同一个事件中出现的不同项的相关性，比如某商场中顾客购买不同商品的相关性。所谓的关联分析，就是利用关联规则进行数据挖掘。2.2.1啤酒和尿布问题关联规则分析可以反映一个事件和其他事件之间存在的问题和知识。如果两项或者多项属性之间存在关联，那其中一项的属性值就可以依据其他属性值进行预测。关联规则分析在商业中应用的最典型的实例就是一家大型连锁店通过对购物篮数据进行关联分

42、析后发现小孩所使用的尿布和啤酒之间的关联联系，这就是数据挖掘领域中著名的“啤酒与尿布”的故事。故事主要内容的是：在美国，有不少刚当上父亲的年轻人，经常在下班后去超级市场购物，购买婴儿使用的尿布，超市管理者发现了这么一条有趣的规律：购买了婴儿尿布的年轻父亲当中，同时有30%40%的人还购买了一些啤酒。于是超市随后调整了货架，对货物进行了重新摆放，将尿布和啤酒放在一起，这样就方便了这些年轻父亲购买，这么做使得销售额明显增加。这种关联分析在零售业中得到了广泛应用，企业可以获得注入产品间的关联，或者产品类别和购买这些类别产品的顾客的统计信息之间的关联规则，故关联分析又被称为购物篮分析，在销售配货、商店

43、商品陈列设计、超市购物路线设计、产品定价和促销等方面都得到广泛应用。2.2.2基本概念（1）项集项集（Itemset）是一组项。每个项都是一个属性值。比如在商场购物数据中，有项集包含了一组产品，如蛋糕，可乐及牛奶。在研究客户的统计信息中，项集包含一些信息，如性别=男，教育程度=大学本科，居住地=南宁。每个项集都有大小，大小用来表示项集中所包含的项的数目。比如项集性别=男，教育程度=大学本科，居住地=南宁有3个项，所以该项集大小就是3。（2）支持度支持度用于度量一个项集出现的频率。项集1，2，3的支持度就是同时包含1，2，3的事务总个数所组成的。可表示如下：Support(1,2,3)=Numb

44、er of Transactions(1,2,3)最小支持度Minimum-Support(minsupp)是一个参数，必须在处理关联模型前制定该参数，它用来表示用户只对满足最小支持度的项集和规则感兴趣，这些规则表示数据集的最低支持度。该参数用于对项集进行了限制，不是对规则进行限制。（3）置信度置信度（Confidence）是关联规则的属性。关联规则1，2=3的概率是使用1，2的支持度除1，2，3的支持度来计算得出。该概率在数据挖掘研究中被称为置信度（Confidence）。可以按以下方式来定义：Confidence(1,2=3)= Confidence(3/1,2)=Support(1,2,

45、3)/Support(1,2)最小置信度Minimum-Confidence是一个阀值参数，必须在运行算法前制定此参数，该参数表示用户只对某些规则感兴趣，这些规则出现的频率较高。Minimum-Confidence对项集没有任何影响，但会影响规则。2.2.3基本模型设I=i1, i2, im为所有项目的集合，D为事务数据库，事务T是一个项目子集（TI）。每一个事务具有区别于其它事务的唯一事务标识TID。设A是一个由项目构成的集合，称为项集。事务T包含项集A，当且仅当AT。如果项集A中包含k个项目，则称其为k项集。项集A在事务数据库D中出现的次数占D中总事务的百分比就是该项集的支持度。如果项集的

46、支持度不小于用户预先设置的最小支持度，就称该项集是频繁项集或大项集。关联规则是形如XY的逻辑蕴含式，其中XI，YI，且XY=。如果事务数据库D中有s%的事务包含XY，则称关联规则XY的支持度为s%，实际上，支持度也就是一个概率值。若项集X的支持度记为support (X)，规则XY的置信度support (XY)support (X)。这是一个条件概率P (Y | X)。也就是： support (XY)=P (X Y) confidence (XY)= support (X Y)/ support (X)=P (Y | X) 2.2.4关联规则的简单例子用一个简单的例子说明关联规则（如下表1

47、）。表1是顾客购买记录的数据库D，包含6个事务。项集I=网球拍,网球,运动鞋,羽毛球。考虑关联规则：网球拍网球，事务1,2,3,4,6包含网球拍，事务1,2,6同时包含网球拍和网球，支持度=3/6=1/2=50%，置信度=3/5=60%。若给定最小支持度 = 0.5，最小支持度 = 0.6，关联规则网球拍网球是有趣的，我们可以认为购买网球拍和购买网球之间存在关联。表1：交易数据TID网球拍网 球运动鞋羽毛球1111021100310004101050111611002.2.4关联规则的主要应用（1）零售业零售业就是关联规则最初的，也是重要的应用领域之一，目的是发现商品的购买模式，把经常一起购买

48、的商品摆放在一起，从而促进这些商品的销售。其中，“啤酒与尿布”的例子就是关联规则在零售业的一个成功应用。关联规则还可以发现客户对特定商品的偏好，有助于确定客户的主要来源，在不减少收入的前提下节约不必要的开支。（2）市场营销电话卡是电信公司的主要业务之一，面对激烈的市场竞争，电信公司需要不断地推出新的电话卡和制定各种不同的优惠措施。由于不同的电话卡的功能和优惠方式不同，将不同卡捆绑起来销售是一种常用的促销手段。如果电话卡的销售数据进行关联股则的挖掘，利用它们之间的关联关系，就可以制定更加有效的捆绑促销策略。在银行业中，关联规则被用来分析各项服务之间的关系，主动为用户提供所需要的服务。在保险业中，

49、关联规则可以发现投保人和索赔的关系。例如把一份人寿保险的保单作为一个交易，记录投保人的年龄、性别、健康状况、工作单位、工作地址和工资等信息。通过分析这些数据，可以得到类似这样一些关联规则：年龄在40岁以上，工作在某工业区的投保人当中，有将近一半的人向保险公司索赔过。通过分析原因，发现该地区的污染比较严重，导致工作在该地区的人健康状况不好，因此，在所赔率业相对比较高。了解这样的事实后，保险公司可以相应地提高这个地区的保险金额。（3）识别欺诈关联规则不仅可以发现出现频率高的规律，也可以反映异常情况。在有些领域中，发现异常情况比发现普遍规律更有价值。例如，保险公司分析客户的保险申请，发现不寻常的多项

50、保险申请，这些申请可能是欺诈行为。另外，通信业、信用卡公司、股票交易所、银行业也有这方面的需要。（4）因特网随着因特网的迅速发展，网络信息量越来越大，网页的内容也越来越丰富。当网络拥挤或用户要访问的网页数据量较大的时候，就可能需要较长的等待时间。缓存是提高响应速度的常用方法，将用户可能要访问的网页提前存储在缓存中，待需要时直接从缓存读出，由此带来的一个问题是选择哪些网页放入缓存，才能有效利用有限的缓存空间8。关联规则提供了一种有效的方法来解决这个问题，根据用户前一段时间访问网络的记录，利用关联规则数据挖掘算法发现用户的访问模式，也就是经常被一起访问的网页。当用户在上网的过程中，利用关联规则动态

51、地更新缓存，提前传输将来可能被访问的网页。考虑到用户的访问模式可能有所变化，还可以对已经生成的关联规则做定期的更新，使得这些规则更符合用户当前的访问习惯。2.2.5关联规则的分类由于关联分析的对象和目标有所不同，根据不同的分类标准，可对关联规则进行分类如下：（1）按照基于规则中处理的变量的类别分类。可分为：布尔型关联规则和数值型关联规则两种。（2）按照基于规则中数据的抽象层次分类。可分为：单层关联规则和多层关联规则两种。（3）按照基于规则中涉及到的数据的维数分类。可分为：单维关联规则的和多维关联规则两种。2.2.6关联规则的挖掘过程关联规则挖掘主要分为以下两个过程：（1）找出所有的频繁项集(F

52、requent Itemsets)。这一步，挖掘出所有大于预设支持度阀值的频繁模式，也是关联规则数据挖掘中最重要和关键的步骤。（2）由挖掘出来的频繁项集产生强关联规则。要产生的强规则就是那些满足最小支持度阀值和最小置信度阀值的关联规则。2.3关联规则挖掘算法分类2.3.1关联规则算法原理关联规则挖掘目的是挖掘出数据库或者数据仓库中各个数据项集间隐藏的关联关系。关联规则算法实际上是关联相关性的计数引擎。关联规则算法一般有以下两个步骤：1、找出所有支持度大于最小支持度阀值的事务组合，既是频繁项集。对于静态数据相应的算法主要有Apriori和AprioriTid，而动态数据，主要有FP-Growth

53、、FP-Stream、FP-DS算法等。2、基于频繁模式产生的强关联规则。这个步骤所需要的时间比第一步少得多，所以算法主要是以研究第一步，即对频繁项集的挖掘为主。2.3.2经典关联规则算法(1)产生候选项集的算法IBM公司Almaden研究中心的R.Agrawal首先提出关联规则模型，并给出求解算法AIS。随后又出现了SETM和Apriori等算法。其中，Apriori是关联规则模型中的经典算法之一。Apriori算法利用频繁项集的先验知识（prior knowledge）的性质，通过逐层搜索的迭代方法，即将频繁（k-1）-项集用于连接生成频繁k-项集，挖掘出数据集中的全部频繁项集。(2)不用

54、生成候选集的算法针对Apriori算法的固有缺陷，J. Han等人提出了不产生候选频繁项集的方法：FP-树频集算法。算法采用分而治之的思想，在对数据库第一遍扫描之后，把数据库中的所有的频集都压缩到一棵频繁模式树（FP-tree），但仍保留所有频集中的关联信息，随后再将FP-tree分化成一些条件库，每个库和一个长度为1的频集相关，然后再对这些条件库分别进行挖掘。当原始数据量很大的时候，也可以结合划分的方法,使得一个FP-tree可以放入计算机主内存中。实验表明，FP-growth算法对不同长度的关联规则都有很好的适应性，同时在执行效率方面较之Apriori算法有较大的提高。2.3.3改进的关联

55、规则算法Apriori算法主要的瓶颈问题是：(1)要对数据进行多次扫描。(2)会产生大量的候选项集。(3)对候选项集的支持度计算非常繁琐； 因此对该算法的解决思路主要是依据如下原则来展开的： (1)减少对数据库的扫描次数。(2)缩减产生的候选项集；(3)改进对候选项集的支持度计算方法目前改进的算法主要有：(1)基于hash表的项集计数。将每个项集通过相应的hash函数映射到hash表中的不同的桶中，这样可以通过将桶中的项集技术跟最小支持计数相比较先淘汰一部分项集。(2)事务压缩（压缩进一步迭代的事务数）。不包含任何k-项集的事务不可能包含任何(k+1)-项集，这种事务在下一步的计算中可以加上标

56、记或删除。(3)划分。挖掘频繁项集只需要两次数据扫描,D中的任何频繁项集必须作为局部频繁项集至少出现在一个部分中。第一次扫描：将数据划分为多个部分并找到局部频繁项集。第二次扫描：评估每个候选项集的实际支持度，以确定全局频繁项集。(4)选样（在给定数据的一个子集挖掘）。算法基本思想是选择原始数据的一个样本，在这个样本上用Apriori算法挖掘频繁模式，通过牺牲精确度来减少算法开销，为了提高效率，样本大小应该以可以放在内存中为宜，可以适当降低最小支持度来减少遗漏的频繁模式。(5)动态项集计数。在扫描的不同点添加候选项集，这样，如果一个候选项集已经满足最少支持度，则在可以直接将它添加到频繁项集，而不

57、必在这次扫描的以后对比中继续计算。2.4本章小结关联规则数据挖掘是数据挖掘的研究热点，本章主要描述了关联规则算法的相关概念和基本算法的性质，给出了关联规则的分类、算法的基本步骤并讨论了关联规则算法的分类。第三章 关联规则的经典算法在发现关联规则的领域中，Apriori算法的影响力非常之大，算法命名源于算法使用了频繁项集性质的先验（prior）知识。在对深度优先数据挖掘算法的研究工作中，韩家炜教授（J. han）等人没有沿用传统的潜在频繁项集的方法求解频繁项目集，创造性地提出了称为频率模式增长（FP_growth）的算法,它采用分而治之的思想。现在分别介绍这两个经典算法。3.1 Apriori算

58、法Apriori算法是关联规则挖掘中最重要的算法，它是一种用于挖掘布尔关联规则中的频繁项集的算法，其核心是基于两阶段频集思想的递推算法。所有支持度大于或等于最小支持度的项集称为频繁项集，简称频集。Apriori算法最显著的特征是应用先验知识即prior knowledge（频繁项集性质），通过迭代的方法逐层搜索数据库，即将（k-1）-项集用于连接生成候选k-项集，以此来发现数据集中的所有频繁项集。3.1.1算法基本思想该算法的基本思想是：首先找出所有的频繁项集，这些项集出现的频率（次数）要求不小于预先设定的最小支持事务数（通过最小支持度得出）。然后通过得到频集来产生关联规则，这些规则同样必须满

59、足不小于最小支持度和最小可信度的条件，满足该条件的关联规则就是强关联规则。然后利用所有频集来产生我们所感兴趣的关联规则，即产生只包含该集合的所有非空子集的关联规则，且每一条规则的右边只出现一项，这里采用的是中规则的定义。一旦符合条件的规则被生成，那么只有那些不小于用户预设的最小置信度的规则才能最终被留下来。为了生成所有频繁项集，使用了递推的方法。先找到频繁1-项集集合L1,然后用L1找到频繁2-项集集合L2，接着用L2找L3，直到找不到频繁k-项集为止，找每个Lk都需要对数据库扫描一次。3.1.2 Apriori性质性质(一)：频繁项集的所有非空子集也必须是频繁的。即AB模式不可能比A更频繁的

60、出现。性质(二)：非频繁项集的超集一定不是频繁项集。即Apriori算法是反单调的，一个集合如果不能通过测试，则该集合的所有超集也不能通过相同的测试。Apriori算法运用第一个性质，利用已得到的或者已知的频繁项集来构造长度更大的项集，这些更长的项集成为潜在频繁项集（候选项集）。潜在频繁K-项集的集合Ck指的是那些有可能成为频繁k项集的项集所组成的集合。以后只需计算潜在频繁项集的支持度，而不必计算所有不同项集的支持度，因此在一定程度上减少了计算量。3.1.3算法描述(1) L1=频繁1项集; (2) for(k=2;L（k-1）;k+) do begin (3) Ck=Apriori_gen(

61、L(k-1); /新的潜在频繁项集 (4) for all transactions tD do begin /数据库扫描(5) Ct=subset(Ck,t); /t中包含的潜在频繁项集 (6) for all candidates cCt do (7) c.count+; (8) end; (9) Lk=cCk|c.countminsup /产生频繁K-项集(10) end; (11) Answer=kLk103.1.4算法分析算法分为第一次遍历和第k次遍历：第一次遍历计算每个项目的具体值，确定大项目集1项目集L1。 第k次遍历利用前一次找到的大项集L(k-1) 和Apriori-gen函

62、数产生候选集Ck ，然后扫描数据库，得到Ck 中候选的支持度，剔除了不合格的候选项集后Ck作为Lk。 Apriori_gen函数：本质是合并项目集成为候选项目集（Apriori_gen），算法法如下：Insert into Ck Select p1, p2,，pk-1，qk-1From L(k-1) p， L(k-1) qWhere p1 = q1，pk-2 = qk-2 pk-1 qk-1然后，对于Ck 中某集合c的任意子集，如果不存在于L(k-1) ，则删除c；比如下面例子：L3 为 1 ,2, 3 ,1, 2, 4, 1 ,3, 5, 2, 3, 4在合并后为C4: 1, 2 ,3, 4 1 ,3 ,4 ,5；因为1, 3 ,4 ,5 中的1, 4 ,5不存在于L3，所以C4 中1, 3, 4 ,5应该删除，故L4 : 1, 2 ,3 ,4。Subset函数：候选项目集Ck 是存储在一个哈希（Hash）树中的，哈希（Hash）树中的一个树节点包含项集的一个链表即叶节点或包含一个哈希表（Hash）即一个内节点。在内节点中，哈希表（Hash）的每一个Bucker都指向到另一