学位论文 > 优秀研究生学位论文题录展示

基于树结构的精简序列模式挖掘算法研究

作　者: 解玉洁
导　师: 任家东
学　校: 燕山大学
专　业: 计算机软件与理论
关键词: 位置信息表 序列扩展匹配 WAP-Tree 投影树 漏洞特征提取
分类号: TP311.13
类　型: 硕士论文
年　份: 2010年
下　载: 13次
引　用: 0次
阅　读: 论文下载
 

内容摘要


现有的序列模式挖掘算法能有效地在大型数据库中挖掘出完整的序列模式集,然而在很多实际应用中,用户更希望找出感兴趣的、更简洁的模式,而不是所有的模式。本文主要研究了如何挖掘精简序列模式,如何有效的增量挖掘精简序列模式,以及如何精确的挖掘重复间隔精简序列模式等问题,这些问题的研究在顾客购物分析,交易分析,Web页面的访问模式预测,DNA序列分析,软件行为模式分析中具有重要的意义。本文首先设计了一种基于改进前缀树的最大序列模式挖掘算法CSMS,算法利用纵向、横向结合搜索位置信息表的序列扩展匹配方法找到潜在最大序列模式,同时,把每个找到的潜在最大序列模式存储在改进的前缀树PStree中,最后通过对PStree进行剪枝,得到由最大序列模式组成的前缀树MPStree。该算法具有较好的时间效率和扩展性。其次,提出了一种基于重复链接WAP-Tree结构的闭合重复间隔序列模式挖掘算法MRCGP,算法首先为频繁1项集构建一个位置信息表,然后通过搜索位置信息表找到所有由不同项组成的2序列模式,最后构建一个重复链接WAP-Tree维护所有的频繁项集,通过逐步挖掘已存在模式的投影树,得到所有的闭合重复间隔序列模式集。该算法的性能优于CloGSgrow。最后,设计了一个面向软件漏洞特征提取的闭合序列模式挖掘算法MSPT和更新算法UMSPT。算法MSPT首先搜索半频繁和频繁2模式,然后为半频繁和频繁项构建一个漏洞序列树,利用投影技术,逐步找到半闭合和闭合序列模式。算法UMSPT插入新的序列到漏洞序列树,搜索树中新插入的分支找到新序列中的闭合和半闭合模式。最后通过检查已存在模式的包含关系以及支持度信息得到更新数据库中的所有半闭合和闭合序列模式集。本文使用现实数据集进行挖掘,通过实验对本文所提出的CSMS算法、MRCGP算法、MSPT算法以及UMSPT算法进行验证。

全文目录


摘要  5-7
Abstract  7-11
第1章 绪论  11-17
  1.1 序列模式挖掘技术  11-15
    1.1.1 序列模式挖掘研究背景及意义  11-12
    1.1.2 序列模式挖掘的任务  12-13
    1.1.3 国内外研究现状  13-15
    1.1.4 存在的问题  15
  1.2 课题主要研究内容  15-16
  1.3 本文的结构内容安排  16-17
第2章 基于改进前缀树PStree 的最大序列模式挖掘  17-29
  2.1 引言  17-18
  2.2 序列匹配扩展的思想  18-19
  2.3 问题定义与描述  19-20
  2.4 最大序列模式挖掘算法CSMS 的设计  20-27
    2.4.1 位置信息表的构建  20-21
    2.4.2 搜索SMS  21-23
    2.4.3 潜在最大序列模式树PStree 的设计  23-25
    2.4.4 PStree 剪枝  25-26
    2.4.5 算法CSMS 设计  26-27
  2.5 算法分析与应用实例  27-28
    2.5.1 算法分析  27-28
    2.5.2 应用实例  28
  2.6 本章小结  28-29
第3章 基于重复链接WAP-Tree 的闭合重复间隔序列模式挖掘  29-43
  3.1 引言  29-30
  3.2 问题定义与描述  30-31
  3.3 重复间隔序列模式挖掘算法设计原则  31-33
  3.4 MRCGP 算法设计  33-40
    3.4.1 RLWAP-Tree 设计过程  33-37
    3.4.2 搜索2-RPDI  37-38
    3.4.3 闭合重复间隔序列模式算法MRCGP 的设计  38-40
  3.5 算法分析  40-41
  3.6 实例  41-42
  3.7 本章小结  42-43
第4章 面向软件漏洞特征提取的闭合序列模式挖掘  43-55
  4.1 引言  43-44
  4.2 问题定义与描述  44-45
  4.3 面向软件漏洞特征提取的闭合序列模式挖掘  45-48
    4.3.1 搜索半频繁和频繁2 模式  45-47
    4.3.2 数据结构的设计  47-48
  4.4 算法MSPT 的设计  48-50
  4.5 增量闭合序列模式挖掘算法  50-52
  4.6 算法分析  52
  4.7 应用实例  52-53
  4.8 本章小结  53-55
第5章 算法实现及实验分析  55-65
  5.1 数据集的来源  55
  5.2 CSMS 算法实验  55-58
    5.2.1 环境及数据集的设置  55-56
    5.2.2 实验结果分析  56-58
  5.3 MRCGP 算法的实现  58-62
    5.3.1 环境及数据集的设置  58-59
    5.3.2 实验结果分析  59-62
  5.4 算法MSPT 和UMSPT 的性能测试  62-64
    5.4.1 环境及数据集的设置  62-63
    5.4.2 实验结果分析  63-64
  5.5 本章小结  64-65
结论  65-67
参考文献  67-73
攻读硕士学位期间承担的科研任务与主要成果  73-74
致谢  74-75
作者简介  75

相似论文

  1. 基于CPRIP-Tree的空间伴生模式挖掘算法研究与应用,TP311.13
  2. 基于Web挖掘的电子商务推荐技术的研究,TP311.13
  3. 支持XML数据查询的F&B索引结构的研究,TP311.13
  4. 海量多数据库集成系统的查询处理研究,TP311.13
  5. 海量数据压缩、操作和处理方法的研究,TP311.13
  6. 频繁图结构并行挖掘算法的研究与实现,TP311.13
  7. 海量多数据库集成系统的Mediator和Wrapper机制的设计与实现,TP311.13
  8. 隐式用户兴趣挖掘的研究与实现,TP311.13
  9. 基于BAP的数据压缩、操作与查询处理系统的实现,TP311.13
  10. 医疗信息集成平台中DICOM中间件及访问控制模型的设计与实现,TP311.13
  11. K-均值聚类算法的研究与改进,TP311.13
  12. 基于流形学习的数据降维技术研究,TP311.13
  13. K-means聚类优化算法的研究,TP311.13
  14. 公安110指挥决策业务系统,TP311.13
  15. 基于分治法的聚类方法研究,TP311.13
  16. 不完备信息系统的完备化及其上的知识获取,TP311.13
  17. 演化聚类算法及其应用研究,TP311.13
  18. 教学质量评估数据挖掘系统设计与开发,TP311.13
  19. 数据挖掘技术在电视用户满意度分析中的应用研究,TP311.13
  20. Web使用挖掘与网页个性化服务推荐研究,TP311.13
  21. 数据挖掘在学校管理和学生培养中的应用,TP311.13

中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 计算机软件 > 程序设计、软件工程 > 程序设计 > 数据库理论与系统
© 2012 www.xueweilunwen.com