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

不确定数据流中频繁数据挖掘研究

作　者: 汤克明
导　师: 陈崚
学　校: 南京航空航天大学
专　业: 计算机应用技术
关键词: 不确定数据流频繁项查询 Top-k查询频繁闭项集挖掘频繁数量区间模式挖掘滑动窗口模型采样挖掘模型
分类号: TP311.13
类　型: 博士论文
年　份: 2012年
下　载: 75次
引　用: 0次
阅　读: 论文下载

内容摘要

随着计算机技术与通信技术的快速发展，传感器网络、Web服务和RFID技术得到了广泛应用，从而使得不确定性数据管理得到广泛的重视．在许多现实的应用中，例如经济形势预测、金融信息分析、生态环境监测、网络安全监控、物流管理等等，不确定数据流扮演着关键角色．在这些应用中，传统的数据管理技术却无法有效地管理新型的不确定数据流，这就引发了学术界和工业界对研发新型的不确定数据流管理技术的兴趣．因此，不确定数据流上的数据挖掘已经成为当前数据挖掘领域的研究热点．当前对于不确定数据流上的挖掘主要集中在不确定数据流上的聚类、不确定数据流上的频繁模式挖掘、Skyline查询、数据世系分析、异常分析等．本文在深入研究国内外的各种不确定数据流挖掘技术的基础上，讨论了目前国内外有关不确定数据流频繁数据挖掘的研究现状．由于不确定数据流上的频繁数据挖掘是不确定数据流上的关联规则、分类、聚类等挖掘的基础，在不确定数据流挖掘中具有重要的地位．因此，本文在不确定数据流上频繁数据挖掘方面进行了深入的研究，提出了有效的频繁数据挖掘算法．本文的主要工作有：（1）提出了一种基于滑动窗口的不确定数据流中频繁项查询算法SWBUFIM．本文根据频繁项的本质特性以及马尔科夫不等式，给出了两个裁剪规则，用于对不确定数据流进行预处理，裁剪掉不可能成为频繁项的元组．在此基础上我们：一方面利用动态规划方法计算期望概率，保证在时间内完成期望概率的计算；另一方面，根据不同数据项相互独立性原理，针对不同数据项开辟子滑动窗口，并且根据数据项的组合数目进行行列划分来处理频繁项挖掘问题，并在动态规划方法的基础上，进一步改进期望概率计算方法，只需要动态规划滑动窗口中前k-1项即可保证在时间内有效地完成期望概率的计算．实验结果表明，所提出的查询算法SWBUFIM具有较快的处理速度，其空间复杂度随着处理数据规模的增加成线性增长．（2）提出了一种基于滑动窗口的不确定数据流中top-k查询算法MPTopKTS．本文针对top-k查询的定义，根据不确定数据流及其滑动窗口的特性，研究基于滑动窗口top-k查询问题，提出了所有可能世界中元组集成员相对得分值高并且具有最大出现概率的top-k元组集(MPTopKTS)的查询算法．该算法基于滑动窗口建立概要表，然后在每一时刻对概要表进行修改，有效地减少了top-k查询问题的复杂性；能够在查询准确性与查询开销之间取得平衡，较小的计算开销获得高质量的近似结果．实验结果表明，所提出的查询算法在时间与空间复杂性方面优于其他类似的算法．（3）提出一种基于滑动窗口的不确定数据流中频繁闭项集的采样挖掘算法MFCIFUDS．本文针对不确定数据流频繁闭项集的挖掘问题，首先使用采样的方法，基于随机采样概率，把由不确定数据组成的事务转换成由确定性数据组成的事务，再利用基于确定性数据模型的频繁闭项集挖掘技术完成不确定数据流中频繁闭项集的挖掘任务．本文不但从理论上证明了基于采样技术利用确定性数据挖掘算法解决不确定数据挖掘问题的可行性，而且提出了一种改进频繁模式树生成与修改技术，有效地提高了基于FP-tree频繁模式树的频繁闭项集挖掘速度．实验结果表明，所提出的查询算法MFCIFUDS有较高的挖掘精度和处理速度．（4）提出了一种基于滑动窗口的不确定数据流中频繁数量区间模式的挖掘算法MFIPatFUS．不同于处理常规二进制项集事务不确定数据流，数量区间事务不确定数据流使用数量区间来表示事务属性，其不确定性在于属性数量区间范围的波动性，数量区间分布体现某种分布概率．本文借鉴常规的基于频繁模式树的不确定数据流频繁模式挖掘算法，设计一种频繁数量区间模式生成树FIPatTree，用于捕获不确定数据流中所有事务的数量区间信息．我们把原始数量区间边界值作为基元素，根据基元素的分布情况建立基数量区间，从而一方面基于基数量区间对原始数量区间进行重新划分；另一方面根据基数量区间数值范围在原始数量区间中所占比例决定其基数量区间概率．算法MFIPatFUS采用滑动窗口模型，使用FIPatTree树作为概要数据结构，事务属性以基数量区间结点保存在FIPatTree树中．建立树的过程类似常规频繁模式生成树的建立过程，不同点在于当属性基数量区间与出现概率均相同时，结点方可共享．对于共享结点设立频次与局部概率统计数值，为了方便遍历与修改，增设了与FIPatTree树相关联的属性索引与基数量区间索引．基于频繁数量区间模式生成树FIPatTree的频繁数量区间模式挖掘过程采用基于投影基与条件树的递归挖掘方法．实验结果表明，所提出滑动窗口模型的挖掘算法MFIPatFUS对处理数量区间事务组成的不确定数据流频繁数量区间模式挖掘是有效的．

全文目录

摘要  4-6
ABSTRACT  6-14
第一章绪论  14-20
  1.1 研究背景和意义  14-15
  1.2 不确定数据流挖掘  15-18
    1.2.1 不确定数据流特点  15
    1.2.2 不确定数据表示与建模  15-16
    1.2.3 不确定数据流挖掘的挑战  16-18
  1.3 研究内容及研究成果  18-19
  1.4 论文的组织结构  19-20
第二章不确定数据流频繁数据挖掘研究现状  20-38
  2.1 数据挖掘范畴  20-21
    2.1.1 数据挖掘的定义  20
    2.1.2 数据挖掘的过程  20
    2.1.3 数据挖掘的任务  20
    2.1.4 数据挖掘的类型  20
    2.1.5 数据挖掘的问题  20-21
  2.2 从不确定数据中挖掘频繁模式  21-31
    2.2.1 基于 Apriori 的不确定数据中频繁模式挖掘  23
    2.2.2 基于树的不确定数据中频繁模式挖掘  23-24
    2.2.3 基于树的不确定数据中频繁模式的约束挖掘  24-26
    2.2.4 基于树的不确定数据流中频繁模式挖掘  26
    2.2.5 基于超链接结构的不确定数据中频繁模式挖掘  26-28
    2.2.6 不确定数据的垂直挖掘  28
    2.2.7 不确定数据中频繁模式挖掘算法比较  28-31
  2.3 从不确定数据中挖掘概率频繁模式  31-34
    2.3.1 从不确定数据中挖掘概率有影响对象  32-33
    2.3.2 从不确定数据中挖掘概率频繁模式  33
    2.3.3 从不确定数据中挖掘概率关联规则  33-34
  2.4 不确定数据流中 Top-K 查询  34-36
  2.5 本章小结  36-38
第三章基于滑动窗口的不确定数据流中频繁项查询  38-56
  3.1 背景介绍  38-39
  3.2 静态不确定数据库的频繁项查询  39-43
    3.2.1 问题的描述  39
    3.2.2 剪枝策略  39-40
    3.2.3 静态不确定数据库中频繁项查询算法  40-43
      3.2.3.1 基于动态规划的概率计算方法  40
      3.2.3.2 概率计算方法的进一步改进  40-42
      3.2.3.3 基于动态规划方法的频繁项查询算法  42-43
  3.3 不确定数据流中频繁项查询算法  43-51
    3.3.1 问题的描述  43-44
    3.3.2 第一个滑动窗口上的频繁项挖掘  44-48
    3.3.3 删除滑动窗口中最旧的一个元组  48-49
    3.3.4 增加一个新元组到滑动窗口后的频繁项挖掘  49-51
  3.4 实验与结果分析  51-55
  3.5 本章小结  55-56
第四章基于滑动窗口的不确定数据流中 Top-k 查询  56-70
  4.1 背景介绍  56-57
  4.2 问题的描述  57-58
  4.3 基于滑动窗口的 MPTopKTS 查询算法  58-62
    4.3.1 算法的基本思想和框架  58-59
    4.3.2 算法 4.1 的正确性证明  59-62
  4.4 对后继窗口的处理  62-66
    4.4.1 数据结构  62-63
    4.4.2 删除一个旧元组  63-64
    4.4.3 插入一个新元组  64-66
  4.5 实验与结果分析  66-69
  4.6 本章小结  69-70
第五章基于滑动窗口的不确定数据流中频繁闭项集的采样挖掘  70-86
  5.1 背景介绍  70-71
  5.2 问题的描述  71-73
  5.3 基于滑动窗口的 MFCIFUDS 挖掘算法  73-83
    5.3.1 算法的基本思想  73-75
    5.3.2 算法的精确度分析  75-76
    5.3.3 基于模式增长树的频繁闭项集挖掘算法的改进处理  76-83
      5.3.3.1 改进 FP-tree 树和频繁闭项集表  77-78
      5.3.3.2 插入新事务时 FP-tree 树和频繁闭项集表 FCIT 的变化  78-81
      5.3.3.3 删除旧事务时 FP-tree 树和频繁闭项集表的变化  81-83
  5.4 实验与结果分析  83-85
  5.5 本章小结  85-86
第六章基于滑动窗口的不确定数据流中频繁数量区间模式挖掘  86-108
  6.1 背景介绍  86-87
  6.2 问题的描述  87-90
  6.3 算法的基本思路与示例  90-98
    6.3.1 构建频繁数量区间模式生成树  90-93
      6.3.1.1 从项集事务不确定数据集到 UF-tree  90-91
      6.3.1.2 从数量区间事务不确定数据集到 FIPatTree  91-93
    6.3.2 相关数据结构  93-95
    6.3.3 从 FIPatTree 中挖掘频繁数量区间模式  95-98
  6.4 基于滑动窗口的 MFIPatFUS 挖掘算法  98-105
    6.4.1 频繁数量区间模式挖掘框架算法  98-99
    6.4.2 创建频繁数量区间模式生成树  99-100
    6.4.3 频繁数量区间模式挖掘 MFIPatFUS 算法  100-102
    6.4.4 删除当前滑动窗口中最旧事务  102-103
    6.4.5 在当前滑动窗口中插入最新流入的事务  103-105
  6.5 实验与结果分析  105-106
  6.6 本章小结  106-108
第七章总结与展望  108-111
  7.1 研究工作总结  108-109
  7.2 未来工作展望  109-111
参考文献  111-120
致谢  120-121
在学期间的研究成果及发表的学术论文  121

不确定数据流中频繁数据挖掘研究

内容摘要

全文目录

相似论文