基于约束的序列模式挖掘算法的研究

摘要

现有的序列模式挖掘算法能有效地在大型数据库中挖掘出完整的序列模式集。然而，随着应用领域越来越细化，用户对挖掘出来的序列模式提出了更高的要求。因此，将用户的要求或兴趣转化成一种或多种约束，来限定挖掘的序列模式是序列模式挖掘领域内的一个研究重点。本文针对这些问题，将研究重点放在基于约束的序列模式挖掘算法的研究上，这些研究问题在超市中顾客购买模式、网站访问页面的序列模式、电信告警序列模式和DNA模式等中有重要的意义。 本文首先提出了一种基于规则表达式约束的增量式序列模式挖掘算法。此算法用规则表达式来表示用户的要求，然后把规则表示式约束有机融合到增量挖掘过程中，采用三种优化策略优化挖掘过程，以减少所消耗的时间。在动态数据库中挖掘约束序列模式时，此算法的性能明显优于FASTUP算法。 其次，提出了当算法参数发生变化时序列模式的增量式更新算法。该算法基于格频繁模式树的结构，将前次挖掘得到的候选序列模式及其支持度的信息和索引集映射表都保存在格频繁模式树中，以便下次挖掘时使用，缩小了模式搜索空间，降低了模式挖掘的时间。在最小支持度阈值逐渐变小时，该算法的性能明显优于MEMISP算法。 最后，提出了一种基于时间粒度的周期约束序列模式挖掘算法。该算法采用日历中的时间概念作为周期约束中时间戳的表示方法，描述现实世界中的时间概念，通过构建HP-CSB，采用两种候选序列生成方式，提高了挖掘效率，其算法的性能优于PrefixSpan算法。 实验结果表明，本文提出的三种算法的挖掘性能明显优于现有的同类算法，实现了预期的研究目标。

目录

文摘

英文文摘

声明

第1章绪论

1.1序列模式挖掘技术

1.1.1序列模式的产生

1.1.2序列模式挖掘的国内外研究现状

1.1.3序列模式和关联规则的异同点

1.2基于约束的序列模式挖掘技术

1.2.1基于约束的序列模式挖掘的产生

1.2.2常见约束及分类

1.2.3基于约束的序列模式挖掘算法

1.3课题的主要研究内容及本文的结构

第2章基于约束的增量式序列模式挖掘算法

2.1引言

2.2规则表达式概念

2.3一般序列模式挖掘算法分析

2.4 RE_ IncUp算法的设计

2.4.1问题分析

2.4.2优化策略

2.4.3 RE_ IncUp算法

2.5应用实例与性能分析

2.5.1应用实例

2.5.2性能分析

2.6本章小结

第3章交互式序列模式挖掘算法

3.1引言

3.2 KISP算法分析

3.3 MEMISP算法的改进

3.3.1递归发现-索引的策略

3.3.2 MEMISP算法分析

3.4 MIFSPM算法的设计

3.4.1 MEMISP算法的改进

3.4.2格频繁模式树

3.4.3新频繁序列模式挖掘算法

3.4.4 MIFSPM算法

3.5应用实例与性能分析

3.5.1应用实例

3.5.2性能分析

3.6本章小结

第4章基于周期约束的序列模式挖掘算法

4.1引言

4.2传统序列模式挖掘算法分析

4.2.1传统序列模式挖掘算法

4.2.2性能分析与不足

4.3问题定义

4.4 PCS_ mine算法的设计

4.4.1预处理周期约束

4.4.2构造HP-CSB结构

4.4.3生成候选集

4.4.4 PCS_mine算法

4.5应用实例与性能分析

4.5.1应用实例

4.5.2性能分析

4.6本章小结

第5章算法实现与实验结果

5.1数据集的来源

5.2 RE_IncUp算法的实现与实验结果分析

5.2.1环境及数据集的设置

5.2.2实验结果分析

5.3 MIFSPM算法的实现与实验结果分析

5.3.1环境及数据集的设置

5.3.2实验结果分析

5.4 PCS_mine算法的实现与实验结果分析

5.4.1环境及数据集的设置

5.4.2实验结果分析

5.5本章小结

结论

参考文献

攻读硕士学位期间承担的科研任务与主要成果

致谢

作者简介