基于FP-tree的关联规则挖掘算法研究与应用

VIP免费

3.0 牛悦 2024-11-19 5 4 4.22MB 72 页 15积分

侵权投诉

摘要

关联规则挖掘主要发现大量数据中数据集之间有趣的关联或相关联系，它是

数据挖掘领域内的一个重要课题。频繁项集挖掘是生成关联规则的关键步骤，其

效率问题是关联规则挖掘中的一大难点和热点。频繁项集可分为完全频繁项集、

频繁闭项集和最大频繁项集三类。完全频繁项集挖掘算法将产生大量的有可能是

无实际意义的频繁项集，由此产生了频繁闭项集挖掘算法，大大降低了频繁项集

的数量。但当数据集变得更加稠密或支持度阈值更小时，这类算法的性能下降较

快。与完全频繁项集和频繁闭项集相比，最大频繁项集的个数是最少的，所以挖

掘最大频繁项集可以有效缩小问题的求解规模，对用户迅速发现和理解稠密数据

集中的长频繁模式具有重要的意义。

论文在 FPMax 算法的基础上研究了最大频繁项集挖掘问题。通常在基于

FP-tree 的最大频繁项集挖掘算法中，影响其执行效率的主要是递归和超集检测。

因此本文提出了一种改进的基于排序的最大频繁项集挖掘算法 S-FP-MFI。在递归

之前，其根据条件模式基含有的项目数对条件模式基进行动态排序，以减少递归

次数；另外基于 MFI-tree 的投影策略减少了超集检测时间。实验与 FPMax，

DMFI

算法比较，表明 S-FP-MFI 算法在支持度较小时，相比同类算法，有较高的执行效

率。

串行挖掘算法，在时间和空间上都有一定局限性，影响了算法的有效性。本

文在 S-FP-MFI 基础上，提出了一种基于任务划分的，面向分布式计算的最大频繁

项集挖掘算法 DFPMax，建立 FP-tree 后对条件模式基的挖掘任务，应用到分布式

系统中所有的计算节点上，并且并行执行。实验表明，

DFPMax 算法不但能够提高

计算效率，而且当数据库规模不断增加时该算法具有良好的延展性。

关键词：最大频繁项集频繁模式树条件模式基超级检测动态排序

Web 服务递归

ABSTRACT

Association rules mining is mainly used to find interesting association or

connection of the data sets in a large quantity of data, it is a significant subject in the

field of data mining. Mining frequent item sets is the key step for generating association

rules, and efficiency problem of it is a major difficulty and hotspot in generating

association rules. Frequent item sets mining can be classified as complete, closed and

maximal frequent item sets. Complete frequent item sets mining algorithm will generate

a large number of frequent item sets without practical significance, so frequent closed

item sets mining algorithm generated, greatly reducing the number of frequent item sets.

But when the data sets were dense or support threshold was becoming less, this

algorithm's performance declined faster. Compared to the frequent closed item sets and

the complete frequent item sets, the number of MFIs is minimal. So mining maximum

frequent item sets can effectively reduce the problem size, and it is great significant for

users to quickly find and understand the long frequent patterns in dense data sets.

The paper based on the FPMax algorithm researched the maximal frequent item

sets mining algorithm. Generally, in frequent item sets mining algorithms Based on the

FP-tree , the main factors affecting its execution efficiency were recursion and superset

checking. Therefore this paper proposed a new maximum frequent item sets mining

algorithms S-FP-MFI(sorted frequent pattern tree for maximal frequent item set).

According to the number of the item of condition-pattern, it sorted condition-pattern in

order to reduce recursion number, and adopted MFI-tree storing maximum frequent

item sets to reduce superset checking time by the projection strategy. Experimental

results testify the effectiveness of the algorithm with a low support threshold, compared

to the FPMax and DMFI algorithm.

As result of limitation in space and time, the effectiveness of the serial algorithm

was affected. Based on task- division and oriented distributed computing, this paper

presented a maximal frequent item sets mining algorithms DFPMax, building FP-tree

and then mining the conditional pattern bases in parallel on all compute nodes in a

distributed system. The experiments showed that not only the algorithm could improve

computing efficiency, but also when the database size was increasing, the algorithm had

good scalability.

Key words: maximal frequent item sets, frequent pattern tree,

conditional pattern base, superset checking, dynamic sorting, web

service, recursive

摘要

ABSTRACT

第一章绪论 ................................................................................................................. 1

§1.1 研究背景及意义 ..............................................................................................1

§1.2 国内外研究现状 ...............................................................................................2

§1.2.1 国外研究现状 .......................................................................................2

§1.2.2 国内研究现状 .......................................................................................3

§1.3 本文主要工作 ...................................................................................................3

§1.4 论文结构 ...........................................................................................................4

第二章数据挖掘和关联规则概述 ............................................................................. 6

§2.1 数据挖掘概述 ..................................................................................................6

§2.1.1 数据挖掘的任务 ...................................................................................7

§2.1.2 数据挖掘过程和应用 ...........................................................................8

§2.1.3 数据挖掘面临的主要挑战 ...................................................................9

§2.2 关联规则挖掘概述 ........................................................................................10

§2.2.1 关联规则挖掘基本概念 .....................................................................10

§2.2.2 关联规则挖掘过程 .............................................................................12

§2.3 频繁项集挖掘相关工作 ................................................................................13

§2.3.1 完全频繁项集挖掘算法 .....................................................................13

§2.3.2 频繁闭项集挖掘算法 .........................................................................15

§2.3.3 最大频繁项集挖掘算法 .....................................................................15

§2.4 本章小结 ......................................................................................................17

第三章改进的最大频繁项集挖掘算法 .......................................................................18

§3.1 最大频繁项集挖掘算法 FPMax 算法介绍 ..................................................18

§3.1.1 FP-tree 数据结构 .................................................................................18

§3.1.2 FP-tree 数据结构建立 .........................................................................18

§3.1.3 FP-Growth 算法描述 ...........................................................................21

§3.1.4 FPMax 算法介绍 .................................................................................22

§3.2 改进的最大频繁项集挖掘算法 S-FP-MFI .................................................. 24

§3.2.1 S-FP-MFI 算法描述 ............................................................................ 24

§3.2.2 算法步骤 .............................................................................................25

§3.2.3 S-FP-MFI 实验分析 ............................................................................ 26

§3.3 基于分布式计算的最大频繁项集挖掘算法 ................................................29

§3.3.1 WebService 简介 ................................................................................. 29

§3.3.2 算法描述 .............................................................................................33

§3.3.3 算法步骤 .............................................................................................34

§3.3.4 DFPMax 算法实验分析 ......................................................................36

§3.4 关联规则产生算法 ........................................................................................37

§3.4.1 关联规则产生算法 .............................................................................38

§3.5 本章小结 ........................................................................................................40

第四章基于 S-FP-MFI 算法的关联规则挖掘在商品监测系统中的应用 ................ 41

§4.1 第三只眼商品监测系统简介 ........................................................................41

§4.2 系统实现 ........................................................................................................41

§4.2.1 基于 MVC 模式的系统架构 ............................................................. 42

§4.2.2 Web 表现层-Struts 架构 ......................................................................43

§4.2.3 业务逻辑层 ..........................................................................................43

§4.2.4 持久层-Hibernate ............................................................................... 43

§4.2.5 数据库表结构 .....................................................................................44

§4.2.6 系统用户功能框架图 .........................................................................46

§4.2.7 系统流程图 .........................................................................................48

§4.2.8 后台系统实现 .....................................................................................48

§4.2.9 手机客户端实现 ..................................................................................51

§4.3 数据预处理 ....................................................................................................55

§4.4 挖掘结果分析 ................................................................................................57

§4.5 本章小结 ........................................................................................................61

第五章总结和展望 .......................................................................................................62

§5.1 工作总结 .........................................................................................................62

§5.2 未来展望 .........................................................................................................62

参考文献 .........................................................................................................................64

在读期间公开发表的论文和承担科研项目及取得成果 .............................................68

致谢 .................................................................................................................................69

第一章绪论

§1.1 研究背景及意义

进入新世纪，数据挖掘技术引起了信息产业界的极大关注。其主要原因在

于计算机网络技术和数据库技术的高速发展，人们积累的数据量急剧地增长，

已经把人们淹没在数据的广阔海洋中，面对如此海量的数据,如何从中提取出

对我们有用的信息，已经成为巨大的挑战。人们如何才能不被大量的数据所淹

没，并从中发现隐藏的、能对决策提供支持的信息，提高数据的利用率，就成

了人们的所关心的焦点。数据库系统虽然可以对数据进行简单的查询、记录、

统计等，但是对于数据之间的关系和规律的发现，则显得束手无策。这种情况

下，数据挖掘技术[1,2]显得尤为重要，它正是发现数据间隐含的规律的有效方

法。

数据挖掘又被称为数据库中的“知识发现”，是近年来企业界相当热门的

一个话题。在广义和狭义上数据挖掘的定义是有区分的。从广义来看，数据挖

掘是从大量嘈杂的原始数据集中，挖掘隐藏的，难以预知的，用户可能感兴趣

的和对决策有潜在价值的规则和知识的过程。从狭义来看，可以定义其是从大

量复杂的数据集中提取隐含知识的过程。简单的来讲，就是通过数据库技术、

机器学习、人工智能、统计学等领域的技术，从数据仓库或数据库中寻找出潜

在的且有应用价值的知识，为科学研究提供有用的理论和技术支持，为人们的

生活工作学习提供有利信息的技术。目前，它已经成为计算机科学研究中一个

活跃的前沿领域，并在银行金融、医疗卫生、保险、政府、教育、公共设施、

远程通讯、软件开发、运输、市场分析、环境保护、科学研究和产品制造等许

多领域成功得到广泛的应用，其产生的社会效益和经济效益十分可观；同时数

据挖掘使各类机构和组织能更好地理解它们的内部组织结构、业务处理流程和

顾客的购买行为，从提高企业的投资收益。

随着信息科学的逐步发展和社会发展，数据挖掘技术是顺应社会发展需求

的直接结果。以数据采集技术以为主的文件系统率先产生。当人们解决了数据

的收集问题以后，系统性能的瓶颈就变成了对数据如何进行高效的的处理(包

括数据存储、快速检索等等)，于是数据库技术在此情况下产生了。当上述问

题成功解决后，人们就希望能够从历史数据中获取更多有用的信息，便于指导

基于 FP-tree 的关联规则挖掘算法研究与应用

生产、生活和学习，在此情况下，数据仓库和在线数据分析(OLAP)技术这样

就产生了。人们的大部分日常需求可以通过这些技术解决。例如 OLAP 支持多

维数据分析，针对特定问题的决策支持，并且查询结果直观而易懂。但人们更

加希望对数据做出深入的研究分析，获取更多更深刻的知识。这就要借助于数

据挖掘技术，对数据进行深入的分析，才能获取更多的隐含知识，为企业和个

人提供更多有用的信息。

从广义上讲，关联分析就是数据挖掘的本质。如何获取隐藏在数据背后的知

识是数据挖掘的目的，人们把两个或两个以上变量的取值之间存在某种联系和规

律，称为关联。数据关联可分为简单关联、时序关联、因果关联，其中因果关联

是数据库中存在的一类重要的、可被发现的知识。找出数据库中的数据间隐藏的

关联网就是关联分析的目。关联分析能为企业或个人提供重要信息，对人们的生

成、生活和学习都有重要指导意义。

§1.2 国内外研究现状

§1.2.1 国外研究现状

第11 届国际人工智能联合会议的专题讨论会于 1989 年8月在美国底特律举

行，会上 KDD 该术语[3,4]首次提出。之后 KDD 的专题性研讨会[3,6]在1991 年、1993

年和 1994 年再次举行，各行各业的理论研究员和实际应用开发者汇集在该会议上，

集中讨论了数据统计、海量数据如何高效存储和分析算法、知识发现和运用等问

题。迄今为止，美国人工智能协会共主办了 13 次的 KDD 国际研讨，随着研究人

员的大力支持，参加会议的人数已达到千余人次，论文的内容质量也逐步提升，

俨然该会议已经成为国际型的大会。

世界上很多组织、部门机构和大学[8]对数据挖掘技术都有浓厚的兴趣，例如有

卡内基梅隆大学(有机造 DM、多媒体数据库 DM、互连网 DM 三个研究中心）、斯

坦福大学、麻省理工学院。著名研究机构如：ACM、KDNet、NCDM 等。由美国

人工智能协会（AAAI）主办的国际 DMKD 学术会议，每年参与人数达六七百人，

收录的论文数量迅速增加。另外，诸如 Data Mining、Advanced Spatial Databases、

Very Large Databases 、International Symposium on Digital Earth 、ACM 、IFIS 和

SIGMOD 等国际学术会议如期举行。目前，“Data Ming and Knowledge Discovery”

学术杂志已经被 SCI(Science Citation Index)全部收录，难度指数跃居信息领域的前

列[9,10]。

第一章绪论

关联规则挖掘问题自 R.Agrawal 提出以后，其理论研究日趋成熟而且应用领域

更加广泛，关联可以分为简单关联、时序关联、因果关联。无论要挖掘哪一种类

型的关联规则，挖掘频繁项集既是最基本的步骤，同时也是最为关键的步骤。

R.Agrawal 等在 1993 年提出的 Apriori 算法是频繁项集挖掘算法的核心，它开

辟了频繁项集挖掘算法的先河；它是最具影响力的算法，是一种宽度优先搜索算

法。当给定的支持度阈值较低或者数据集比较稠密时，完全频繁项集挖掘算法将

产生大量的频繁项集，这将增加用户充分理解挖掘结果的难度。为了解决这一问

题，Pasquier 等最早提出了使用频繁闭项集挖掘关联规则的思想，并提出了挖掘频

繁闭项集的第一个算法 A-close；该算法借鉴了 Apriori 算法的思想，采用了宽度优

先的策略来搜索频繁闭项集。但对于像生物信息数据、通信数据等比较稠密的数

据，即使改变算法的搜索策略，也会影响算法的性能。目前对于稠密数据集挖掘

问题的另一个解决方案是挖掘数据集中潜在的最大频繁项集。文章正是对最大频

繁项集的挖掘问题进行了研究。

§1.2.2 国内研究现状

与国外相比，国内学者或机构对数据挖掘技术的认识和学习起步稍晚。随着

数据挖掘技术在金融市场等领域应用及其产生的效益，近年来，数据挖掘的基础

理论及其应用研究，在国内的许多科研单位和高等院校竞相开展，并取得了一定

的研究成果。例如，在基础理论研究方面，北京系统工程研究所注重于数据挖掘

的基础理论研究，例如模糊方法如何应用在知识发现过程中；北京大学对数据立

方体方面的进行了研究。复旦大学、浙江大学、中国科技大学等单位机构主要研

究了对关联规则挖掘算法如何进行优化。南京大学、四川大学和上海交通大学等

单位对数据挖掘的数据结构进行了研究[11]，例如非结构化数据和 Web 数据的挖掘。

当前我国对数据挖掘的研究发展还是很快的，不但专业的学术机构热衷于数据

挖掘的研究，而且许多企业也开始注重数据挖掘技术在企业自身经营和产品设计

中的应用，开发了一些智能产品。作为知识发现的重要方法，数据挖掘已经在各

行各业得到了广泛地应用，正在中国形成一个新的行业。

§1.3 本文主要工作

论文主要对关联规则挖掘进行了研究，尤其对最大频繁项集挖掘做了重要论

述，从关联规则涉及的基本概念出发，在不同角度讨论了最大频繁项集挖掘的有

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

15 积分 4人已下载

立即下载 VIP免费下载

摘要：

摘要关联规则挖掘主要发现大量数据中数据集之间有趣的关联或相关联系，它是数据挖掘领域内的一个重要课题。频繁项集挖掘是生成关联规则的关键步骤，其效率问题是关联规则挖掘中的一大难点和热点。频繁项集可分为完全频繁项集、频繁闭项集和最大频繁项集三类。完全频繁项集挖掘算法将产生大量的有可能是无实际意义的频繁项集，由此产生了频繁闭项集挖掘算法，大大降低了频繁项集的数量。但当数据集变得更加稠密或支持度阈值更小时，这类算法的性能下降较快。与完全频繁项集和频繁闭项集相比，最大频繁项集的个数是最少的，所以挖掘最大频繁项集可以有效缩小问题的求解规模，对用户迅速发现和理解稠密数据集中的长频繁模式具有重要的意义。论文在F...

展开>> 收起<<

基于FP-tree的关联规则挖掘算法研究与应用.pdf

共72页,预览8页

还剩页未读，继续阅读

基于FP-tree的关联规则挖掘算法研究与应用

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

推荐作者

热门标签

举报选择: