基于位图的快速负序列模式挖掘算法研究

发布时间：2021-04-25 02:31

　　作为行为科学的重要组成部分,未发生行为的研究越来越受到学者们的关注。负序列模式挖掘作为一种同时发现发生和未发生行为的有效方法,在医疗行为分析、异常行为检测、推荐系统、教育等领域均有广泛的应用。但目前负序列模式挖掘算法的时间和空间效率依旧不高,即使作为最先进的算法f-NSP,仍存在着许多缺陷。此外,现有的负序列模式挖掘算法都是采用分段挖掘方法,即先利用正序列模式挖掘算法获得正序列模式,进而得到负序列模式,不能在挖掘正序列模式的同时获得负序列模式,这也使得算法效率不高。本文重点研究负序列模式挖掘效率问题,探索正负序列模式同时挖掘方法,并针对其中的关键问题进行了深入探讨。具体如下:本文针对f-NSP算法中的不足,提出了一种改进的负序列模式挖掘算法sc-NSP来挖掘更多有用的负序列模式。首先,通过一种改进的Prefix Span算法来挖掘正序列模式,相比于原算法使用的数组结构,改进的Prefix Span算法使用了位图结构,节省了空间消耗。其次,为了增加负候选的数量,发现更多有趣的负序列模式,我们放宽了频繁约束,并更换了负候选序列生成方法。此外,还设计了一种新的剪枝策略,来减少sc-NSP的计... 

【文章来源】：齐鲁工业大学山东省

【文章页数】：81 页

【学位级别】：硕士

【文章目录】：
摘要
ABSTRACT
第1章 绪论
    1.1 研究背景与意义
    1.2 国内外研究现状
    1.3 存在问题及研究内容
    1.4 创新点及组织架构
第2章 正负序列模式挖掘
    2.1 正序列模式挖掘
        2.1.1 基本概念
        2.1.2 正序列模式典型算法
    2.2 负序列模式挖掘
        2.2.1 负约束条件
        2.2.2 负包含定义
        2.2.3 负序列模式典型算法
    2.3 本章小结
第3章 改进的负序列模式挖掘算法
    3.1 负序列模式相关定义
    3.2 sc-NSP算法
        3.2.1 改进后的Prefix Span正序列模式生成算法
        3.2.2 负候选序列生成方法
        3.2.3 负候选序列的支持度计算方法
        3.2.4 sc-NSP算法伪代码及挖掘示例
    3.3 理论分析
        3.3.1 NSC数量的分析
        3.3.2 算法运行时间分析
    3.4 实验分析
        3.4.1 性能分析
        3.4.2 数据特征对运行时间的影响
        3.4.3 可扩展性分析
    3.5 案例研究
    3.6 本章小结
第4章 基于位操作的正负序列模式同时挖掘算法
    4.1 存在问题
    4.2 负包含定义和负约束条件
    4.3 B-NSP算法
        4.3.1 B-NSP的序列字典树及剪枝策略
        4.3.2 B-NSP的存储结构
        4.3.3 正负候选序列生成和支持度计算方法
        4.3.4 B-NSP算法伪代码
    4.4 实验分析
        4.4.1 性能分析
        4.4.2 数据特征对运行时间的影响
        4.4.3 可扩展性分析
    4.5 本章总结
第5章 总结及下一步工作
    5.1 研究总结
    5.2 下一步研究工作
参考文献
致谢
在学期间主要科研成果
    一、发表学术论文
    二、获奖情况
    三、参与科研项目
    四、申请专利


【参考文献】：
期刊论文
[1]Multilevel Pattern Mining Architecture for Automatic Network Monitoring in Heterogeneous Wireless Communication Networks[J]. Zhiguo Qu,John Keeney,Sebastian Robitzsch,Faisal Zaman,Xiaojun Wang.  中国通信. 2016(07)
[2]数据挖掘综述[J]. 钟晓,马少平,张钹,俞瑞钊.  模式识别与人工智能. 2001(01)

硕士论文
[1]基于项缺失的负序列模式挖掘关键技术研究[D]. 邱萍.齐鲁工业大学 2018
[2]重复正负序列模式挖掘关键技术的研究[D]. 宫永顺.齐鲁工业大学 2016
[3]大数据集序列模式挖掘算法研究[D]. 梁栋.山东师范大学 2015



本文编号：3158529