序列概念格模型及其序列模式挖掘

论文摘要

信息技术的日新月异使得各个领域的数据量激增,在此背景下诞生的知识发现和数据挖掘给人们提供了一种新的认识数据、理解数据的智能手段。序列模式发现是其中的一个重要研究课题,概念格是一种擅长描述层次关系的有效工具,因此,研究概念格的基本理论以及将其应用于知识发现有着非常重要的意义。以概念格为工具来实现序列模式发现是当前数据挖掘领域的一个新的研究热点。本文对基于概念格的序列模式发现的方法展开研究。本文主要就此领域的相关问题展开系列研究,主要工作和创新点如下:详细讨论了序列模式的基本模型以及经典的发现方法,展现了序列模式发现研究领域的应用前景及所面临的挑战。综述了概念格的基本理论以及经典建格算法,并讨论了以概念格模型为核心来组织数据结构和算法以实现序列模式挖掘的基本方法和策略。提出了两种新的概念格的扩展模型,一种是以序列数据库中频繁项集为节点的基于兴趣度的序列概念格模型,并引入了序列的兴趣度,以方便在此基础上挖掘出用户感兴趣的序列模式。另一种是序列模糊概念格模型,它是把精确的序列数据库背景转化为模糊的序列形式背景,并定义了模糊序列概念的Galois闭包连接、序列模糊概念及序列模糊格结构,最后给出了序列模糊概念格的渐进式构造算法。由于传统的序列模式发现算法需要多次扫描数据库,因而时间开销较大,并且所挖掘出的所有的频繁序列整个过程缺乏针对性,时间代价高,结果数量巨大且难以理解。为解决此类问题我们提出两种基于概念格的序列模式发现算法,一种是基于兴趣度的序列概念格的最大序列模式挖掘,一种是基于序列模糊概念格的序列模式挖掘。通过实验表明,在序列概念格模型上可以方便有效地挖掘重要的序列模式,算法在时间与空间上都具有良好的性能。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 论文研究背景及现状
• 1.1.1 概念格模型
• 1.1.2 序列模式挖掘
• 1.2 论文创新点
• 1.3 论文的内容组织
• 1.4 本章小结
• 2 概念格模型与序列模式发现
• 2.1 概念格模型及其概念
• 2.1.1 形式背景和概念
• 2.1.2 概念格及其表示
• 2.2 概念格的生成算法概述
• 2.2.1 批生成算法（Batch Algorithm）
• 2.2.2 渐进式生成算法（Incremental Algorithm）
• 2.3 序列模式相关的概念及定义
• 2.3.1 数据源格式
• 2.3.2 序列模式基本概念及问题描述
• 2.4 序列模式发现的经典算法
• 2.4.1 基于Apriori 的候选码生成-测试的方法
• 2.4.1.1 频繁序列的Apriori 性质
• 2.4.1.2 候选序列集生成一测试迭代算法
• 2.4.2 基于垂直格式的候选码生成-测试的方法
• 2.4.2.1 数据分布技术
• 2.4.2.2 SPADE 主要思想
• 2.4.3 基于模式增长策略的算法
• 2.4.3.1 FreeSpan 算法
• 2.4.3.2 Prefixspan 算法
• 2.5 本章小结
• 3 序列概念格及其生成算法
• 3.1 引言
• 3.2 基于兴趣度的序列概念格模型及其构建
• 3.2.1 序列兴趣度
• 3.2.2 序列概念格模型
• 3.2.3 基于兴趣的序列概念格模型构造算法
• 3.3 实验与分析
• 3.3.1 实验结果
• 3.3.2 实验分析
• 3.4 本章小结
• 4 模糊概念格及其序列模糊概念格
• 4.1 引言
• 4.2 模糊概念格概述
• 4.2.1 模糊概念格的基本概念
• 4.2.2 模糊概念格的生成算法概述
• 4.3 序列模糊概念格模型
• 4.3.1 序列模糊形式背景
• 4.3.2 序列模糊概念格
• 4.3.3 序列模糊概念格构造算法
• 4.4 实验与分析
• 4.4.1 实验结果
• 4.4.2 实验分析
• 4.5 本章小结
• 5 基于概念格模型的序列模式发现
• 5.1 引言
• 5.2 基于兴趣度的序列概念格的最大模式挖掘
• 5.3 基于序列模糊概念格的序列模式挖掘
• 5.4 实验与分析
• 5.4.1 实验结果
• 5.4.2 实验分析
• 5.5 本章小结
• 6 结束语
• 6.1 本文工作总结
• 6.2 进一步的研究工作
• 参考文献
• 致谢
• 作者攻读硕士学位期间所发表的文章
• 作者攻读硕士学位期间参加的科研项目