描述性规则挖掘若干关键技术研究

论文摘要

描述性规则挖掘是数据挖掘研究领域的重要课题之一。数据挖掘的任务是从大量的数据中发现模式,按照其功能作用可分为预测性和描述性挖掘,描述性规则挖掘对数据中存在的规律、规则做出一种描述,它涵盖了数据挖掘中关联分析、序列模式发现等重要研究领域。论文研究工作结合省知识产权平台建设工作,针对专利文献的挖掘和利用,在现有的描述性规则挖掘研究的基础上,针对描述性规则挖掘的实际需求和若干需要解决的关键技术,以关联规则分析为基础,对描述性规则挖掘中的序列模式挖掘技术、分布环境下关联规则快速挖掘技术以及基于关联分析的离群知识发现方法等进行研究。针对序列模式挖掘过程本身是一个反复的交互式过程,提出了一种基于PrefixSpan的快速交互式序列模式挖掘算法,当最小支持度发生变化时,算法能够充分利用前次或中间结果,快速生成新的模式;结合序列模式的增量式更新问题,提出了基于投影数据库的序列模式增量式更新算法ISPMP,算法采用间接拼接的方法更新已经得到的序列,用增量数据库来减小投影数据库,从而有效提高算法效率;在此基础上,为了进一步提高序列模式挖掘的效率,提出了一种基于二进制形式的候选频繁序列模式生成和相应的计算支持数方法,该方法只需对挖掘对象进行一些“或”、“与”、“异或”、等逻辑运算操作,显著降低了候选频繁序列模式生成和相应的支持数计算的实现难度,将该方法与序列模式挖掘及更新算法相结合,可以有效提高序列模式挖掘及更新算法的效率;针对大数据集关联规则发现问题,提出了一种快速挖掘全局最大频繁项目集算法FMGMFI,该算法采用FP-tree存储结构,由于FP-tree结构是一种压缩的存储结构,数据库中的记录可被压缩存储在建立的局部FP-tree的各路经中,使得FMGMFI可方便地从各局部FP-tree的相关路径中得到项目集的支持度,同时采用自顶向下和自底向上的双向搜索策略,可有效地降低网络通讯代价,高效地生成关联规则;最后,针对现有离群点检测算法多数面向低维空间数据,并且缺少语义解释的问题,结合关联分析及粗糙集知识提出了一种基于关联分析的离群点检测算法,算法可以有效发现存在于大量数据集中有别于正常关联模式的那些异常数据点。在论文的研究过程中,针对所提出各种算法进行了大量的实验验证,实验结果表明了算法的合理性和有效性。

论文目录

• 摘要
• Abstract
• 第一章 概述
• 1.1 选题依据及意义
• 1.1.1 描述性规则挖掘
• 1.1.2 选题的依据
• 1.1.3 课题研究的意义
• 1.2 描述性规则挖掘研究概况
• 1.2.1 数据挖掘的模型分类与任务分类
• 1.2.2 关联规则挖掘
• 1.2.3 序列模式挖掘
• 1.2.4 聚类及离群知识发现
• 1.3 数据挖掘研究的理论基础
• 1.4 本文的组织
• 第二章 基于 PrefixSpan的快速交互序列模式挖掘算法
• 2.1 序列模式挖掘概述
• 2.2 相关定义
• 2.3 基于PrefixSpan的序列模式挖掘算法
• 2.4 基于PrefixSpan的快速交互序列模式挖掘算法FISPM
• 2.4.1 FISPM算法描述
• 2.4.2 局部完全挖掘候选序列
• 2.4.3 FISPM算法的优化
• 2.5 算法性能分析及试验结果
• 2.6 本章小结
• 第三章 基于投影数据库的增量式序列模式更新算法
• 3.1 序列模式的增量更新问题
• 3.2 基于投影数据库的增量式序列模式更新算法ISPMP
• 3.2.1 ISPMP算法描述
• 3.2.2 间接拼接（Implicit Merging）数据序列
• 3.2.3 删除或更改交易时的序列模式维护
• 3.3 实验结果与分析
• 3.4 本章小结
• 第四章 基于二进制编码的序列模式挖掘及其更新算法
• 4.1 相关定义与性质
• 4.2 算法描述
• 4.2.1 候选频繁序列模式的生成算法
• 4.2.2 频繁序列模式支持数的计算
• 4.2.3 序列模式挖掘算法B-GSP
• 4.2.4 序列模式更新挖掘算法FUFSPA
• 4.2.5 算法比较与实现
• 4.3 本章小结
• 第五章 分布式全局最大频繁项目集发现算法
• 5.1 问题描述
• 5.1.1 频繁模式树FP-tree
• 5.1.2 全局最大频繁项目集
• 5.2 基于FP-Tree的全局最大频繁项目集挖掘算法FAMGMFI
• 5.2.1 局部最大频繁项目集挖掘算法AMLMFI
• 5.2.2 全局最大频繁项目集挖掘算法模型
• 5.2.3 全局最大频繁项目集挖掘算法
• 5.2.4 示例说明和实验结果
• 5.3 全局最大频繁项目集的快速更新算法FAUGMFI
• 5.3.1 FAUGMFI算法原理
• 5.3.2 全局最大频繁项目集的快速更新算法FAUGMFI
• 5.3.3 性能测试
• 5.4 本章小结
• 第六章 基于关联分析的高维空间离群知识发现算法
• 6.1 离群知识发现问题
• 6.2 基于关联分析的离群点发现算法
• 6.2.1 相关定义及性质
• 6.2.2 离群点描述
• 6.2.3 算法分析及试验情况
• 6.2.4 实验结果
• 6.3 本章小结
• 第七章 结束语
• 7.1 本文工作总结
• 7.2 进一步的研究工作
• 致谢
• 参考文献
• 附录I 读博期间发表、录用及修改的论文目录
• 附录II 读博期间科研工作情况