基于素数编码的序列模式挖掘研究

论文摘要

序列模式挖掘是数据挖掘领域中一个活跃的研究分支,有着广泛的应用前景,如顾客购买行为分析、Web点击流分析以及生物序列分析等,目前已经得到了广泛地研究,提出了许多经典的算法,如GSP算法、SPADE算法以及PrefixSpan算法等等,这些算法仅仅是挖掘出满足用户指定的最小支持度minsup的序列模式,然而用户可能需要更加抽象的信息,即根据分类概念,将序列数据库中的项目分成不同的类,形成不同的层次进行多层序列模式挖掘,而且用户可能更关注比较重要的序列模式,即将序列的权重参与到挖掘过程中进行加权序列模式挖掘。由于素数论中的素数编码方案具有良好的数学性质、鲜明的层次性与简洁的更新操作等优点,为此本文利用素数编码对序列模式挖掘进行了系统的研究,主要研究工作包括：（1）在多层序列模式挖掘中,编码既要直观地表达层次关系,又要方便确定不同层次之间的关系,编码方式将直接影响着算法的效率。本文在多层序列模式挖掘中采用素数编码,并证明了通过素数编码的简单整除操作就可确定层与层之间的父—子关系,提出了基于素数编码的多层序列模式挖掘算法（PMSM）和交叉层序列模式挖掘算法（CROSS-PMSM）。实验证明,该算法能有效地从序列数据库中挖掘多层和交叉层序列模式。（2）在加权序列模式挖掘中,基于候选码生成-测试方法的MWSP是目前应用性最好的算法之一,然而在挖掘过程中容易出现候选组合爆炸的情况,为此本文提出了一种高效的加权序列模式挖掘算法（PWSM）。PWSM算法引入k-最小加权支持数概念并利用前缀投影数据库原理有效地避免了候选组合爆炸的发生,并且在挖掘的过程中充分利用最小加权支持数,再次对算法进行优化。实验表明,该算法较MWSP算法有较好的时间和空间性能。（3）在多层序列模式和加权序列模式的基础之上,本文定义了多层加权序列模式MWSP （Multi-level Weighted Sequential Pattern）,提出了多层加权序列模式挖掘框架,并且给出了基于素数编码的多层加权序列模式挖掘算法（PMWSM）。该算法即可以为用户提供更加抽象的信息又可以挖掘出满足用户需求的有价值的序列模式。通过实验证明,本文提出的基于素数编码的多层加权序列模式挖掘算法在时间与空间上都具有良好的性能。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 论文研究背景与选题依据
• 1.2 论文主要内容与创新
• 1.3 论文内容组织
• 第二章 素数编码理论与序列模式挖掘
• 2.1 素数编码理论
• 2.1.1 素数及其编码理论的基本概念
• 2.1.2 素数编码方案
• 2.1.3 素数编码理论的应用
• 2.2 序列模式挖掘
• 2.2.1 序列模式挖掘的基本概念
• 2.2.2 序列模式挖掘典型算法
• 2.2.3 序列模式挖掘的应用
• 2.3 小结
• 第三章 基于素数编码的多层序列模式挖掘
• 3.1 引言
• 3.2 相关知识
• 3.3 基于素数编码的多层序列模式挖掘算法
• 3.3.1 分类结构树中的素数编码
• 3.3.2 多层序列模式挖掘算法（PMSM）
• 3.3.3 交叉层序列模式挖掘算法（CROSS-PMSM）
• 3.4 实验结果与分析
• 3.5 小结
• 第四章 改进的加权序列模式挖掘算法
• 4.1 引言
• 4.2 相关知识
• 4.3 基于前缀投影数据库的加权序列模式挖掘算法
• 4.3.1 K-最小加权支持数
• 4.3.2 加权序列模式挖掘算法
• 4.3.3 实验结果与分析
• 4.4 小结
• 第五章 多层加权序列模式模型及挖掘算法
• 5.1 引言
• 5.2 多层加权序列模式模型
• 5.3 基于素数编码的多层加权序列模式挖掘算法（PMWSM）
• 5.3.1 PMWSM算法描述
• 5.3.2 PMWSM算法实例分析
• 5.4 实验结果与分析
• 5.5 小结
• 第六章 结束语
• 6.1 论文总结
• 6.2 进一步研究工作
• 致谢
• 参考文献
• 攻读硕士期间撰写的主要论文
• 攻读硕士期间参加的科研项目/学术会议/获奖