数据挖掘关联规则FP-growth算法..doc

目 录 摘要： ０ 1．介绍 １ 2.数据挖掘 １ 3.关联规则 ２ 4．数据采掘工具的研制及其应用 ３ 5.程序实现 ５ 算法描述 ６ 数据结构 ９ 算法实现细节 １３ 6.总结 ２０ 7.致谢 ２０ 摘要： 关联规则在数据挖掘是一个重要的研究内容。而产生频繁集则是产生关联规则的第一步。在大多数以前的实现中，人们普遍采用了类似于Apriori[2]的算法。这种算法有一个很大的缺点，就是使用了不断产生候选集并加以测试的方式来得到频繁集。但是，产生候选集的代价是很大的。 本文分析并且实现了在论文[1]中提出的FP-growth算法。FP-growth算法的优点是节省时间和空间，对大规模数据采用分治的办法以避免规模巨大难以接受。FP-growth算法主要通过FP-tree来构造频繁集。 FP-tree是一个数据库里跟产生频繁集有关的信息的压缩表示。在具体的实现中，我通过了一系列的从低到高的数据结构来实现它，并进而实现整个算法。该实现基于Windows平台，编程工具是Visual C++ 6.0，许多地方还用到了C++的标准模板库。 1．介绍 数据挖掘技术的出现是伴随着当今时代信息的爆炸性增长和人们面对纷繁的数据得到决策支持而出现的.数据挖掘工具中要实现的一个很重要的功能就是关联规则的找寻，而关联规则找寻的第一步就是要找到相应的频繁集. 本文就是建立在对一个频繁集产生算法的分析和实现的基础上的.通过一个程序具体实现了FP-growth算法,并将它作为一个使用数据挖掘工具,ARMiner的一部分. 本文的第2部分将介绍一些数据挖掘的基本知识. 第3部分讨论关联规则的一些问题. 第4部分是本文所实现的程序所属的数据挖掘工具ARMiner的一些介绍. 第5部分结合程序设计着重讨论一下本文是怎样实现FP-growth算法的。 2.数据挖掘 数据挖掘（Data Mining）就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。 何为知识?从广义上理解，数据、信息也是知识的表现形式，但是人们更把概念、规则、模式、规律和约束等看作知识。人们把数据看作是形成知识的源泉，好像从矿石中采矿或淘金一样。原始数据可以是结构化的，如关系数据库中的数据；也可以是半结构化的，如文本、图形和图像数据；甚至是分布在网络上的异构型数据。发现知识的方法可以是数学的，也可以是非数学的；可以是演绎的，也可以是归纳的。发现的知识可以被用于信息管理，查询优化，决策支持和过程控制等，还可以用于数据自身的维护。因此，数据挖掘是一门交叉学科，它把人们对数据的应用从低层次的简单查询，提升到从数据中挖掘知识，提供决策支持。在这种需求牵引下，汇聚了不同领域的研究者，尤其是数据库技术、人工智能技术、数理统计、可视化技术、并行计算等方面的学者和工程技术人员，投身到数据挖掘这一新兴的研究领域，形成新的技术热点。 这里所说的知识发现，不是要求发现放之四海而皆准的真理，也不是要去发现崭新的自然科学定理和纯数学公式，更不是什么机器定理证明。实际上，所有发现的知识都是相对的，是有特定前提和约束条件，面向特定领域的，同时还要能够易于被用户理解。最好能用自然语言表达所发现的结果。 数据挖掘的主要过程如下: 1. 确定业务对象 清晰地定义出业务问题,认清数据挖掘的目的是数据挖掘的重要一步.挖掘的最后结构是不可预测的,但要探索的问题应是有预见的,为了数据挖掘而数据挖掘则带有盲目性,是不会成功的. 2. 数据准备 1) 数据的选择 有哪些信誉好的足球投注网站所有与业务对象有关的内部和外部数据信息,并从中选择出适用于数据挖掘应用的数据. 2) 数据的预处理 研究数据的质量,为进一步的分析作准备.并确定将要进行的挖掘操作的类型. 3) 数据的转换 将数据转换成一个分析模型.这个分析模型是针对挖掘算法建立的.建立一个真正适合挖掘算法的分析模型是数据挖掘成功的关键. 3. 数据挖掘 对所得到的经过转换的数据进行挖掘.除了完善从选择合适的挖掘算法外,其余一切工作都能自动地完成. 4. 结果分析 解释并评估结果.其使用的分析方法一般应作数据挖掘操作而定,通常会用到可视化技术. 5. 知识的同化 将分析所得到的知识集成到业务信息系统的组织结构中去. 数据挖掘技术目前已经有不少成功的范例.其实在日常生活中我们也可以看到许多数据挖掘的应用.例如,如果你在沪上一家比较著名的电子商务网站购买了一张周星驰的经典搞笑片”大话西游”,该网站会提醒你, 【购买该商品的用户还买了这些商品】 行运一条龙 97家有喜事 武状元苏乞儿 月光宝盒 秀兰邓波儿（12套装） 这些就是用数据挖掘技术从购买这部片子的人群