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

时间序列流的层次聚类和频繁模式的挖掘算法研究

作　者: 周兴华
导　师: 陆建峰
学　校: 南京理工大学
专　业: 模式识别与智能系统
关键词: 时间序列流 层次聚类 增量系统 频繁模式 多线程
分类号: TP311.13
类　型: 硕士论文
年　份: 2013年
下　载: 13次
引　用: 0次
阅　读: 论文下载
 

内容摘要


时间序列挖掘是数据挖掘领域中最具挑战性的十大研究方向之一。时间序列流是一种连续、高速、无限、时变的按照时间排列的有序序列。连续性要求挖掘算法扫描次数少；高速性要求挖掘算法的实时性高；数据量的无限性要求挖掘算法能够缓存数据,并分批装载进主存中：数据内容的时变性要求挖掘算法具有处理概念漂移的能力,能够反映出数据的演化性质。由于时间序列流的复杂特性,时间序列流的挖掘研究仍处于探索阶段,本文将从层次聚类系统和序列频繁模式挖掘两个方面开展研究。由于层次聚类算法具有自适应确定聚类数目、适合多种类型的簇结构和效率高等多种优点,使得它在数据流聚类研究中应用广泛。本文重点研究了数据流层次聚类中的ODAC(the Online Divisive Agglomerative Clustering)算法。ODAC算法是一个时间序列流增量式聚类算法,采用自顶向下策略构建簇的一个层次树状结构。但它存在两种问题：噪音数据影响聚类结果和处理概念漂移时重构簇结构代价过大。本文提出了一种基于粗糙集理论的改进算法ODRC(the Online Divisive Rough Clustering)。 ODRC算法分为两个阶段：第一阶段根据时间序列流样本生成子簇的层次结构,第二阶段利用限制容差关系模型扩展子簇的粗糙集定义,从而获得子簇结构基于粗糙集的等价划分。该算法能够获得比原算法更加合理的簇结构,增强了对时间序列流中概念漂移现象的处理能力。实验结果表明了该方法的可行性和有效性。序列模式挖掘作为数据挖掘领域的研究热点之一,其任务是从序列数据库中挖掘出频繁序列供决策者做出决策。本文引入了一种基于滑动窗口技术的序列模式挖掘算法MFI-TransSW,该算法采用比特序列实现滑动窗口操作,较好解决了在数据一遍扫描和有限内存空间的限制下实现快速处理的难题。针对MFI-TransSW算法在频繁模式生成阶段计算效率不高的情况,本文提出了一种基于窗口划分成固定数目段的多线程算法MFI-MultiSW. MFI-MultiSW算法采用线性链表结构存储当前候选项集和窗口内事务的信息,并在线性链表的基础上采用多线程方法生成频繁模式。实验结果表明,改进算法相比原算法具有较高的执行效率,尤其在多核环境中,性能提升更为显著。

全文目录


摘要  3-4
Abstract  4-6
目录  6-8
1 绪论  8-14
  1.1 研究背景与意义  8-9
  1.2 国内外研究现状  9-11
  1.3 主要工作与创新之处  11-12
  1.4 论文组织结构  12-14
2 时间序列流层次聚类算法的分析  14-27
  2.1 传统层次流聚类算法  14-16
    2.1.1 分解型层次聚类法-BIRCH算法  14-16
    2.1.2 凝聚型层次聚类法-CURE算法  16
  2.2 时间序列相似性度量的主要方法  16-19
    2.2.1 基于形状的相似度  16-17
    2.2.2 基于特征的相似度  17-18
    2.2.3 基于模型的相似度  18
    2.2.4 符号时序数据的相似度  18-19
  2.3 时间序列流聚类  19-20
  2.4 在线分裂合并聚类算法ODAC  20-24
    2.4.1 ODAC的算法框架  20-22
    2.4.2 增量式相似性度量  22
    2.4.3 算法步骤  22-24
  2.5 ODAC算法的评估  24-26
    2.5.1 控制层次结构增长的标准  24-25
    2.5.2 概念漂移的处理  25-26
    2.5.3 算法复杂度分析  26
  2.6 本章小结  26-27
3 基于粗糙集理论的ODAC改进算法  27-38
  3.1 ODAC算法的缺陷  27
  3.2 基于粗糙集理论的聚类研究  27-29
    3.2.1 粗糙集理论  28
    3.2.2 利用粗糙集的概念进行聚类  28-29
  3.3 在线分裂粗糙聚类算法ODRC  29-36
    3.3.1 限制容差关系模型  29-30
    3.3.2 一个实例  30-32
    3.3.3 ODRC的算法框架  32-34
    3.3.4 算法步骤  34-36
  3.4 ODRC算法的评估  36
    3.4.1 概念漂移的处理  36
    3.4.2 算法复杂度分析  36
  3.5 本章小结  36-38
4 时间序列流聚类实验  38-45
  4.1 实验数据介绍  38-39
  4.2 聚类质量分析  39-40
  4.3 时间效率分析  40-42
  4.4 算法参数评估  42-44
  4.5 本章小结  44-45
5 时间序列流频繁模式挖掘算法的研究  45-60
  5.1 频繁模式挖掘算法的数据流处理模型  45-46
  5.2 滑动窗口模型的频繁模式挖掘算法  46-47
  5.3 MFI-TransSW算法  47-49
    5.3.1 算法主体思想  47-48
    5.3.2 MFI-TransSW算法缺陷  48-49
  5.4 改进算法MFI-MultiSW  49-55
    5.4.1 算法改进技术  49-53
    5.4.2 频繁模式挖掘过程  53-55
    5.4.3 频繁模式中的时序限制  55
  5.5 实验结果  55-59
  5.6 本章小结  59-60
6 总结和展望  60-61
  6.1 研究工作总结  60
  6.2 工作展望  60-61
致谢  61-62
参考文献  62-67
附录  67

相似论文

  1. AVS视频解码器在PC平台上的优化及场解码的改善,TN919.81
  2. 基于智能学习的多传感器目标识别与跟踪系统研究,TP391.41
  3. 基于比对技术的非法网站探测系统的实现与研究,TP393.08
  4. 一种基于i.MX51的嵌入式VoIP终端的设计与实现,TN916.2
  5. 对于系统发育谱法聚类算法的改进,TP311.13
  6. 中文人名跨文档指代消解研究,TP391.1
  7. 一种基于ARM-LINUX和SQLITE的组件化嵌入式软件系统设计,TP311.52
  8. 基于C/S模式的使用权限管理系统的设计与实现,TP311.52
  9. 基于DEA模型的我国R&D投入产出效率评估研究,G322
  10. 运载火箭数字化智能数据评估系统,TP311.52
  11. 基于并行计算的立体影像密集匹配算法研究,TP391.41
  12. 面向消费者感性需求的手持GPS设计探讨,TN967.1
  13. 基于IP协议的网络轮询实现,TP311.52
  14. 一种基于全局频繁模式的数据挖掘算法及系统实现,TP311.13
  15. 基于C/S架构的车辆远程监控系统的设计与实现,TP277
  16. 分布式交互仿真模拟技术的研究及其在深水海洋平台锚泊操作模拟中的应用,U674.381
  17. 基于多线程求解一维下料问题的递归算法,TP301.6
  18. 在线非接触开放式数控测量系统的研究,TG80
  19. 基于多核的动态剖析加速方法研究,TP332
  20. 基于多线程图像处理机测试系统的研究,TP391.41
  21. 云备份中的双指纹校验与多线程传输技术研究,TP309.3

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