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

VIP免费

3.0 牛悦 2024-11-19 4 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]显得尤为重要，它正是发现数据间隐含的规律的有效方

法。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

15 积分 4人已下载

立即下载 VIP免费下载

摘要：

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

展开>> 收起<<

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

共72页,预览8页

还剩页未读，继续阅读

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

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

推荐作者

热门标签

举报选择: