全文总字数：2783字

1. 研究目的与意义及国内外研究现状

数据挖掘指的是从大型数据库或数据仓库中提取人们感兴趣的知识，这些知识是隐含的、事先未知的、潜在的有用信息。数据挖掘的任务是从数据中发现模式，模式有很多种，在实际应用中细分为6种:分类模式、回归模式、时间序列模式、聚类模式、关联模式和序列模式，其中关联模式的挖掘是目前数据挖掘领域中最为广泛的研究课题之一。 数据项之间的关联规则称为关联模式。我们所讨论的问题集中在数据挖掘中的关联规则上。关联规则用于从大量数据中发现项集之间的有趣关联或相关联系。关联规则挖掘的一个典型例子是购物篮分析。关联规则研究有助于发现交易数据库中不同商品(项)之间的联系，找出顾客购买行为模式，如购买了某一商品对购买其它商品的影响。分析结果可以应用于商品货架布局、货存安排以及根据购买模式对用户进行分类。关联规则有着广泛的应用:在商业领域，关联规则能够协助企业决策者完成市场分析和进行客户关系管理;在基因生物学中，关联规则可用来分析基因表达谱数据，揭示不同基因间或环境与基因表达之间的相关联系;在网络安全领域，关联规则能够揭示不同攻击行为之间的关系。此外，关联规则还能应用于分类、相关分析等数据挖掘领域。因此本文的研究具有较高的实用价值和理论意义。

国内外研究现状

数据挖掘的发展经历了一个逐步演变的过程。在上世纪60年代以前，计算机处于初始阶段，面对的常常是简单的电子数据处理，一般通过机器学习的方法处理这些电子数据，来为决策行为提供数理依据或通过某些策略来进行自动决策。所谓机器学习，就是将一些人们已经成功解决的问题范例输入计算机，计算机通过对这些范例进行总结和学习来产生一些规则，这些规则应该具有一定的通用性和稳健性，使计算机可以利用这些规则来处理某一类的问题。随后，随着神经网络技术的出现和发展，人们的注意力转向知识工程，知识工程不同于机器学习那样给计算机输入范例，让它生成出规则，而是直接给计算机输入己被代码化的规则，而计算机是通过使用这些规则来解决某些问题。专家系统就是这种方法所得到的成果，但它投资大、效果不甚理想。80年代人们又在新的神经网络理论的指导下，重新回到机器学习的方法上，并将其成果应用于处理大型商业数据库。知识发现(knowledge discovery in databases kdd)的概念首次出现在1989年8月举行的第11届国际联合人工智能学术会议中。随着kdd的影响越来越大，国际kdd组委会在1995年把专题讨论会替换为为国际会议，并在加拿大蒙特利尔市召开了第一届kdd国际学术会议，其后每年召开一次。到目前为止，由美国人工智能协会主办的kdd国际研讨会已经召开了多次，规模由原来的专题讨论会发展到国际学术大会，研究重点也逐渐从发现方法转向系统应用，并且开始注重多种发现策略和技术的集成和多种学科之间的相互渗透。其他内容的专题会议也把数据挖掘和知识发现列为议题之一，使kdd成为当前计算机科学界的一大热点，ieee(instituteof electricalandelectronicsengineers)，acm(associationfor computing machinery)等学会、期刊纷纷推出数据挖掘与知识发现(data ming and knowledge discovery)的会议议题与学术专刊。到目前为止，基于关系数据库与事务数据库的数据挖掘和知识发现的研究己经取得一定的进展和成果。目前影响较大的算法有:加拿大simon fraser大学jiawei.han教授提出的概念树提升算法、ibm的agrawal.r的关联算法、澳大利亚的j.r. quinlan教授的分类算法、密西根州立大学eric goodman教授的遗传算法等。数据挖掘未来的应用领域将会越来也广泛，热点包括web的数据挖掘、基因的数据挖掘以及文本的数据挖掘，数据量越来越大，复杂度越来越高，因此高效率的数据挖掘算法尤其是关联规则的挖掘算法将越来越重要，也越来越受到人的重视。

2. 研究的基本内容

关联规则挖掘是数据挖掘的基本问题之一。经典的关联规则挖掘算法主要是基于频繁集的方法，相关的算法主要有Apriori算法和FP-growth算法。FP-growth算法采用不同于以前Apriori系列算法的候选产生测试方法，采取模式增长的方法挖掘关联规则，它克服了Apriori系列算法的缺陷，取得了很好的效果。但是，FP-growth算法仍然存在着一些不足，如算法的性能严重依赖于数据库的大小，挖掘关联规则时需要递归地生成和释放成千上万的条件模式树等等。本文拟针对FP-growth算法进行较为深入的研究，探讨其中存在的问题，开展相关研究与改进，进行相关实验验证。最后，整理实验结果，按照学校要求形成毕业论文。

3. 实施方案、进度安排及预期效果

实施方案如下：(1) 全面了解挖掘关联规则相关算法，了解关联规则挖掘算法的应用。 (2) 重点研究基于fp-tree的关联规则挖掘算法一fp-growth算法，掌握该算法的基本原理，并分析该算法存在的相关问题。 (3)拟针对传统的fp-tree算法进行改进，使之占用更小的存储空间。 (4)对相关算法进行实现，并在数据集上进行相关实验，验证算法及改进方法的有效性。

进度安排： 2015年12月20日前，查阅相关文献；了解数据挖掘、关联规则挖掘等相关概念和内容。2016年1月16日前收集论文资料，提交开题报告；完成关联规则挖掘相关基本概念和算法的理解。2016年3月31日前掌握关联规则挖掘相关典型算法，如fp-tree，并实现该算法，并在相关文档数据集上进行实验。2016年4月15日前收集并分析实验结果，对算法进行相关改进，完成对算法实验的总结。2016年5月10日前撰写，完成毕业论文。2016年5月16日至5月29日进行毕业论文答辩。预期效果：针对fp-tree算法的某个方面进行改进，并进行相关实验验证与分析。形成毕业论文。

4. 参考文献

[1].《数据挖掘概念与技术》Jiawei Han著，范明等译，机械工业出版社.[2].陈凯，冯全源.《最大频繁项目集的高效挖掘》.微电子学与计算机. [3].丛丹，王俊普，杨文等.《基于FP-Tree的模式分解算法》.计算机工程. [4].谈克林，孙志辉.《一种FP树的并行挖掘算法》.计算机工程与应用. [5].(英)David Hand, Heikki Mannila, Padhraic Smyth著，张银奎，廖丽，宋俊等译. 《数据挖掘原理》.北京:机械工业出版社，2003.4.