论文题目: 频繁模式挖掘相关技术研究
论文类型: 博士论文
论文专业: 计算机软件与理论
作者: 马海兵
导师: 胡运发
关键词: 数据挖掘,频繁模式,频繁闭合模式,频繁子树,互关联后继树模型
文献来源: 复旦大学
发表年度: 2005
论文摘要: 随着计算机与信息技术的普及及大容量存储技术的发展,人们在日常事务处理和科学研究中积累了大量宝贵的数据。如何从中提取或“挖掘”用户所需要的信息,是当前信息科学和技术领域面临的一大挑战。频繁模式挖掘是数据挖掘领域的一个基本问题,研究内容一般包括事务、序列、树和图。其方法被广泛应用于许多其它数据挖掘任务中,如相关性分析,周期分析,最大模式,闭合模式,查询,分类,索引等等。由于问题本身的基础性和内在复杂性,频繁模式挖掘方法成为许多研究者关注的课题。 本文对频繁模式挖掘相关技术进行了研究。重点研究了以下几个问题:将互关联后继树模型引入频繁模式挖掘方法;利用静态IS树高效挖掘频繁项集和频繁闭合项集;利用模式增长方法在有序树构成的森林中挖掘嵌入式频繁子树;在无序树构成的森林中挖掘直接频繁子树;及相关的实现技术等。本文研究内容和创新工作主要包括以下五个方面: 1)基于IS~+-树模型的频繁模式挖掘 互关联后继树模型是一种新型的全文存储索引模型。这种模型充分利用了字符序列的有序性和冗余性,适用于海量的全文存储和索引。互关联后继树模型是一种通用的模型。本文扩展了互关联后继树模型的应用领域,首次提出一种基于间接互关联后继树模型(IS~+-树)的频繁模式挖掘算法。算法特点是:挖掘任务只局部关联于一棵根树;动态更新性好,仅做增量变化:算法简单实用。与传统方法相比,该算法具有较好的挖掘效率。 2)基于静态IS-树的频繁模式挖掘 间接互关联后继树在强调了通用性的同时损失了效率。本文进一步提出一种基于静态IS-树专用模型的频繁项集挖掘算法IS-mine。IS—mine直接构造频繁项集,不进行候选集产生与测试操作;算法采用深度优先,模式增长的策略,挖掘任务只在一棵静态的IS-树上进行,避免代价较高的动态树的构建;针对不同特征的数据集,算法采用不同的过滤技术缩小搜索空间。实验与理论分析表明,对于稠密和稀疏数据两类数据集,算法都具有较好的时空效率。 3)高效频繁闭合模式 频繁闭合模式提供了完全频繁模式的所有信息,但数量却可以少几个数量级。本文提出一种基于静态IS-树的频繁闭合项集有效算法IS-Close。算法采用静态投影,模式增长的方法;用多种策略,尽量在算法运行的早期利用闭合项集的各种
论文目录:
目录
图表目录
摘要
ABSTRACT
第一章 绪论
1.1 研究背景
1.2 相关研究工作
1.2.1 频繁项集挖掘
1.2.2 序列模式挖掘
1.2.3 时间序列模式挖掘
1.2.4 最大项集和闭合项集模式挖掘
1.2.5 频繁子树
1.2.6 频繁子图
1.3 本文工作
1.3.1 研究目标
1.3.2 研究内容
1.3.3 本文结构
1.4 几个术语的说明
第二章 基于间接互关联后继树模型的频繁模式挖掘
2.1 引言
2.2 相关工作
2.3 FP-GROWTH算法挖掘频繁模式
2.3.1 基本思路
2.3.2 挖掘算法
2.3.3 算法讨论
2.4 互关联后继树模型的基本概念和相关定义
2.5 基于IS~+树的频繁模式挖掘
2.5.1 IS~+-树创建算法
2.5.2 IS~+-树频繁项集挖掘算法
2.5.3 IS~+-树挖掘算法与FP-growth算法的比较
2.6 实验和性能分析
2.6.1 实验环境和数据集特征
2.6.2 实验结果分析
2.7 结论
第三章 基于静态IS-树的频繁模式挖掘
3.1 引言
3.2 基本概念和相关定义
3.3 基于静态IS树的频繁模式挖掘
3.3.1 静态IS-树的创建
3.3.2 基于静态IS-树的频繁模式挖掘
3.4.实验和性能分析
3.4.1 实验环境和数据集特征
3.4.2 实验结果分析
3.5.结论
第四章 高效挖掘频繁闭合模式
4.1 引言
4.2 相关工作
4.3 问题描述和相关定义
4.4 闭含测试
4.5 挖掘频繁闭合项集算法IS-CLOSE
4.6 实验和性能分析
4.6.1 实验环境和数据集特征
4.6.2 实验结果分析
4.7 结论
第五章 基于拓扑投影的嵌入式频繁子树挖掘
5.1 介绍
5.2 相关工作
5.3 问题定义
5.4 用TREEMINER算法挖掘频繁子树
5.4.1 生成候选树
5.4.2 候选子树计数
5.4.3 scope-list求交运算
5.4.4 算法讨论
5.5 基于拓扑投影的频繁子树模式增长
5.5.1 树和森林的拓扑编码
5.5.2 用最右路径扩展方法构造模式增长空间
5.5.3 基于拓扑投影的频繁子树模式增长框架
5.6 用TG算法挖掘频繁子树
5.6.1 TG算法
5.6.2 空间性能分析
5.7 实验和性能分析
5.7.1 数据集特征
5.7.2 性能比较
5.7.3 结果分析
5.8 结论和展望
第六章 在无序树森林中高效挖掘直接频繁子树
6.1 介绍
6.2 问题定义
6.3 无序树的规范化
6.4 用HYBRIDTREEMINER算法挖掘直接频繁子树
6.4.1 相关定义
6.4.2 HybridTreeMiner挖掘算法
6.4.3 算法讨论
6.5 用模式增长方法挖掘直接频繁子树
6.5.1 树和森林的宽度优先编码
6.5.2 直接子树模式拓扑编码方法
6.5.3 模式增长空间
6.6 UT-GROWTH算法
6.7 实验和性能分析
6.7.1 数据集特征
6.7.2 性能比较
6.7.3 结果分析
6.8 结论和展望
第七章 应用
7.1 概述
7.2 关联规则挖掘
7.2.1 简介
7.2.2 基本概念
7.2.3 由频繁项集产生关联规则
7.3 基于关联规则挖掘的分类器
7.3.1 简介
7.3.2 ARCS方法
7.3.3 CBA方法
7.3.4 CAEP方法
7.4 针对XML数据的结构分类器
7.4.1 简介
7.4.2 结构规则的概念
7.4.3 基于结构规则的分类器
7.4.4 小论
7.5 基于频繁结构的图索引方法
7.5.1 简介
7.5.2 特征选择
7.5.3 索引创建和维护
7.5.4 小结
7.6 结论
第八章 总结与展望
8.1 总结
8.2 进一步的工作
参考文献
攻读博士学位期间参与的科研项目及主要成果
致谢
发布时间: 2005-09-19
参考文献
- [1].频繁模式挖掘算法研究[D]. 战立强.哈尔滨工程大学2007
- [2].XML数据频繁模式挖掘技术研究[D]. 贝毅君.浙江大学2008
- [3].频繁模式挖掘和动态维护的理论与方法研究[D]. 林晓勇.北京化工大学2008
- [4].频繁模式挖掘算法与剪枝策略研究[D]. 徐玉生.兰州大学2008
- [5].频繁模式挖掘相关技术研究[D]. 刘勇.复旦大学2007
- [6].基于位值压缩存储的频繁模式挖掘方法及应用研究[D]. 王倩.燕山大学2016
- [7].面向不确定数据的频繁模式挖掘方法研究[D]. 于晓梅.山东师范大学2016
- [8].半结构化数据频繁模式挖掘相关技术研究[D]. 杨厚群.重庆大学2010
- [9].加权频繁模式挖掘算法研究[D]. 耿汝年.江南大学2008
- [10].数据流频繁模式挖掘及数据预测算法研究[D]. 陈辉.华中科技大学2008
标签：数据挖掘论文; 频繁模式论文; 频繁闭合模式论文; 频繁子树论文; 互关联后继树模型论文;