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

基于统计密度的流数据频繁模式挖掘

作　者: 高强
导　师: 张春慨
学　校: 哈尔滨工业大学
专　业: 计算机科学与技术
关键词: 统计密度流数据挖掘频繁项集
分类号: TP311.13
类　型: 硕士论文
年　份: 2013年
下　载: 14次
引　用: 0次
阅　读: 论文下载

内容摘要

目前大部分流数据挖掘方法都是从基于静态数据集的数据挖掘方法改进而来的。并且秉承了基于静态数据集的数据挖掘的理念将数据存于可控制范围内，并在此范围内进行数据挖掘，因此这类流数据挖掘方法的思想是将一部分流数据存在本地，然后在基于这部分数据进行挖掘工作。但是这种思想并不完全适合用在流数据挖掘上面，也就是说现在的大多数基于滑动窗口，界标窗口的挖掘方法存在其固有的缺点，即只能以窗口内的数据为基础来进行挖掘。这样就不可避免的忽略了流数据的时间波动特性。还有一个缺点就是因为有存储设备的限制，窗口的大小受到限制，这样即便使用对流数据有一定兼顾的衰退窗口机制也同样不能彻底解决流数据的历史特性问题。针对这些缺点，本文基于统计数据密度分布特性提出了一种比较适合流数据的挖掘方法，称为PDB-FIM(Probability Density Based Frequent Item-set Mining)。算法PDB-FIM通过维持两棵流数据信息树的方式记录了当前感兴趣项集的频繁信息和密度分布信息，并且在查询到达时通过对记录信息的处理和挖掘输出维持数据中的频繁模式。这种方法有以下几个特点：占用内存少，兼顾历史数据性好，对数据的波动性敏感等。下面是本文涉及的主要内容：首先，本文提出了算法PDB-FIM维持主存平衡的方式通过密度信息和支持度信息剪枝的双重策略达到贮存使用的动态平衡，并且通过维持两棵信息树的方式将感兴趣项集的信息保存到查询到来以前。其次，本文还介绍了完全信息树和不完全信息树的概念，并且采用通过保持一棵不完全信息树和一棵完全信息树的方法节省内存加快算法的速度。同时还提出了其他可行的方案并分析了这些方法的优缺点。第三，本论文介绍了一种密度信息的提取、处理、计算和使用的方法，这也是本文的一个创新的地方。最后，本文还做了算法PDB-FIM和经典流数据挖掘算法CFI-Stream的比较实验，结果表明在查询频度合适的情况下不但单个项集处理时间被大大缩小，并且能够对过期频繁的数据进行剔除。

全文目录

摘要  4-5
Abstract  5-6
目录  6-8
第一章绪论  8-13
  1.1 课题背景  8
  1.2 国内外研究现状  8-11
    1.2.1 滑动窗口机制  9-10
    1.2.2 界标窗口机制  10-11
    1.2.3 衰退窗口机制  11
  1.3 主要研究内容  11-12
  1.4 本文组织  12-13
第二章算法 PDB-FIM 背景知识概述  13-22
  2.1 引言  13
  2.2 算法理论背景知识及正确性证明  13-22
    2.2.1 事件概率密度的定义  13-14
    2.2.2 流数据的近似正态分布属性证明  14-15
    2.2.3 算法原理说明与正确性证明  15
    2.2.4 正态分布中μ和的最大似然估计  15-16
    2.2.5 单个节点的数据更新方法正确性证明  16-19
    2.2.6 事件的定义  19
    2.2.7 数据项完全集和数据项子集  19
    2.2.8 信息完全树  19-22
第三章密度信息树 PDIT 概述  22-33
  3.1 密度信息树 PDIT(Probability Density Information Tree)的定义  22
  3.2 密度信息树 PDIT 的维持过程  22-33
    3.2.1 密度信息树 PDIT 的插入过程  23-25
    3.2.2 密度信息树 PDIT 产生信息完全树的过程  25-31
    3.2.3 密度信息树 PDIT 的剪枝  31-33
第四章算法 PDB-FIM 实现过程  33-51
  4.1 算法概述  33-35
  4.2 算法 PDB-FIM 的执行条件  35-37
    4.2.1 两棵树策略的优点  35-36
    4.2.2 查询频率的要求  36-37
  4.3 算法 PDB-FIM 的执行过程  37-39
  4.4 算法 PDB-FIM 中不可能概率的计算方法  39-41
  4.5 未解决问题及算法的缺陷  41-44
    4.5.1 查询频度对结果有影响  41-42
    4.5.2 偷渡效应  42-44
  4.6 实验  44-51
    4.6.1 数据集  44
    4.6.2 不同挖掘频度下算法 PDB-FIM 的效率对比实验  44-45
    4.6.3 不同项集长度下算法 PDB-FIM 的对比实验  45-47
    4.6.4 不同最小支持度大小的情况下算法的空间复杂度走势实验  47-48
    4.6.5 最小剪枝频率对剪枝比的影响实验  48-49
    4.6.6 算法运行过程中冗余节点对比  49-50
    4.6.7 算法正确率验证实验  50-51
结论  51-52
参考文献  52-57
致谢  57

基于统计密度的流数据频繁模式挖掘

内容摘要

全文目录

相似论文