论文部分内容阅读
序列模式挖掘是数据挖掘一个重要的研究领域。随着WEB访问日志数据、交易数据库数据、DNA数据、气象数据等序列类型数据的急剧增加,序列模式挖掘被广泛地应用于网络通信、生产过程、生物医学、气象预测等领域,已成为数据挖掘中最活跃、最有影响的研究领域之一。
本文以序列模式挖掘为核心,对传统序列模式挖掘和闭合序列模式挖掘进行了广泛和深入的研究,主要内容包括:
(1)序列模式挖掘典型算法研究
对传统序列模式挖掘与闭合序列模式挖掘算法进行了广泛研究。关注了近年来出现的扩展模型序列模式挖掘算法、新数据形式序列模式挖掘算法以及基于新数据结构的序列模式挖掘算法。特别针对候选项生成—测试框架、模式增长框架两种策略的典型算法进行了深入剖析,在此基础上比较了各算法的优劣。
(2)基于2-序列连接增长的序列模式挖掘研究
针对传统序列模式挖掘算法中存在的多次扫描投影数据库的不足,本文结合数据垂直表示方法,在形式化定义序列末项位置信息表(LIPT)以及相同末项序列首位置信息表(SLIFPT)的基础上,提出基于2-序列连接增长的挖掘算法SPM-LIPT。该算法在挖掘过程中,通过与2-序列LIPT的比对、连接,实现序列增长,并通过检测 SLIFPT,避免了典型算法PrefixSpan多次扫描投影数据库寻找局部频繁项的不足。实验结果表明,SPM-LIPT算法在挖掘长序列时,比算法PrefixSpan有更好的时间性能。
(3)基于二级索引结构无候选项的闭合序列模式挖掘研究
针对闭合序列模式挖掘算法中存在的需要维护候选序列和重复扫描数据库的不足,本文结合H-struct结构思想,在形式化定义二级索引结构、子序列索引表、超序列索引表,并且扩展子模式回溯、超模式回溯等剪枝技术的基础上,提出无候选项的闭合序列模式挖掘算法posCloSpan。该算法在挖掘过程中,通过对子序列索引表、超序列索引表的检索,对非闭合序列进行修剪,无需保存闭合序列候选项。并通过对二级索引结构的检测,提前终止序列模式的增长,从而避免了重复扫描数据库。实验结果表明,算法posCloSpan比典型算法CloSpan有更好的时间性能。
本文以序列模式挖掘为核心,对传统序列模式挖掘和闭合序列模式挖掘进行了广泛和深入的研究,主要内容包括:
(1)序列模式挖掘典型算法研究
对传统序列模式挖掘与闭合序列模式挖掘算法进行了广泛研究。关注了近年来出现的扩展模型序列模式挖掘算法、新数据形式序列模式挖掘算法以及基于新数据结构的序列模式挖掘算法。特别针对候选项生成—测试框架、模式增长框架两种策略的典型算法进行了深入剖析,在此基础上比较了各算法的优劣。
(2)基于2-序列连接增长的序列模式挖掘研究
针对传统序列模式挖掘算法中存在的多次扫描投影数据库的不足,本文结合数据垂直表示方法,在形式化定义序列末项位置信息表(LIPT)以及相同末项序列首位置信息表(SLIFPT)的基础上,提出基于2-序列连接增长的挖掘算法SPM-LIPT。该算法在挖掘过程中,通过与2-序列LIPT的比对、连接,实现序列增长,并通过检测 SLIFPT,避免了典型算法PrefixSpan多次扫描投影数据库寻找局部频繁项的不足。实验结果表明,SPM-LIPT算法在挖掘长序列时,比算法PrefixSpan有更好的时间性能。
(3)基于二级索引结构无候选项的闭合序列模式挖掘研究
针对闭合序列模式挖掘算法中存在的需要维护候选序列和重复扫描数据库的不足,本文结合H-struct结构思想,在形式化定义二级索引结构、子序列索引表、超序列索引表,并且扩展子模式回溯、超模式回溯等剪枝技术的基础上,提出无候选项的闭合序列模式挖掘算法posCloSpan。该算法在挖掘过程中,通过对子序列索引表、超序列索引表的检索,对非闭合序列进行修剪,无需保存闭合序列候选项。并通过对二级索引结构的检测,提前终止序列模式的增长,从而避免了重复扫描数据库。实验结果表明,算法posCloSpan比典型算法CloSpan有更好的时间性能。