首页> 正文

基于遗忘特性的数据流概要结构及其应用研究

2020-11-28阅读(354)

基于遗忘特性的数据流概要结构及其应用研究

论文摘要

随着计算机网络和各类电子设备应用的越来越广泛,越来越多的数据以连续的流的形式出现,如网络路由信息,传感器网络采集的实时信号,证券交易、信用卡交易、商场购物交易等的实时记录,因特网网站点击流,电信网络的电话呼叫业务记录,聊天室、短信等的实时文本流等,均产生连续不断的各类数据。这些数据被称为流数据或数据流。因为数据流和传统数据库等系统中处理的数据的巨大差别,迫使研究人员对数据流模型和处理方法进行深入研究。数据流处理的关键是应用单趟数据扫描算法,建立流数据的概要结构,以便随时能根据该结构提供数据流的近似处理结果。数据遗忘是数据流的一种重要特性,在数据流概要结构构造中应充分考虑这种遗忘特性。本文工作利用这种遗忘特性,提出了一种基于数据流遗忘特性的概要结构的框架,称为分层遗忘概要（Hierarchical AmnesicSynopses,简称HAS）。应用HAS结构,可将原来不考虑遗忘特性的概要结构构造方法改造为结合了数据流遗忘特性的方法。本文工作将HAS结构应用于直方图、抽样、小波、sketch、随机投影等主要的数据流概要结构中,并给出了几个典型应用。本文主要贡献包括:（1）提出了一种数据流概要结构的通用框架,HAS结构。该框架嵌入了数据流的遗忘特性,并且具有遗忘速度和重构误差控制的能力。利用该框架,可将现有的多种典型数据流概要结构改造成具有数据流遗忘特性处理能力。（2）实现了基于小波数据压缩的HAS结构（W-HAS）,提出了小波概要的归并方法,并讨论了在基于误差平方和（sse）和基于最大绝对误差（maxabs）两种误差度量标准下的W-HAS,以及如何进行W-HAS中的重构误差控制的方法。（3）讨论了基于加权随机抽样的HAS结构（WS-HAS）,分别对有放回和无放回加权随机抽样设计了WS-HAS概要结构的维护算法。（4）提出了结合HAS结构和直方图数据压缩方法的H-HAS结构,讨论了等宽直方图下的H-HAS结构的实现,用动态规划方法实现了最优直方图下的H-HAS结构。（5）基于数据流的W-HAS结构,讨论了数据流之间的近似距离和聚类中心的计算,并进而提出了适合并行多数据流的K-means聚类方法:W-HAS-clustering。同时,利用数据流的遗忘特性,应用随机投影,构造了基于随机投影的数据流分层概要结构RP-HAS,并设计了规范化后数据流的RP-HAS结构维护的方法。提出了基于RP-HAS结构的适合并行多数据流的聚类方法RP-HAS-clustering。（6）讨论了高维数据流中HAS结构的实现,并将其应用到数据流的分类和聚类中。（7）提出了一种基于sketch的数据流概要结构EFM sketch,并用EFM sketch来估算集合的相似度。在HAS结构的基础上,应用EFM sketch分析数据流上数据的相似度和演化。

论文目录

  • 摘要
  • Abstract
  • 第1章 绪论
  • 1.1 引言
  • 1.2 数据流研究进展
  • 1.2.1 数据流模型和数据流管理系统
  • 1.2.2 典型的数据流概要结构
  • 1.2.3 数据流上数据挖掘
  • 1.3 数据流特性的进一步分析及对概要结构构造的作用
  • 1.4 主要研究内容和本文结构
  • 1.4.1 本文主要研究内容
  • 1.4.2 本文主要贡献
  • 1.4.3 本文组织
  • 第2章 分层遗忘概要结构HAS
  • 2.1 引言
  • 2.2 数据流的HAS结构
  • 2.2.1 基本思想与记号
  • 2.2.2 从m个原始数据中提取k个数据节点
  • 2.2.3 数据流上HAS结构的动态维护
  • 2.3 滑动窗口中的HAS结构
  • 2.3.1 窗口长度为数据个数N
  • 2.3.2 窗口长度为时间T
  • 2.4 具有误差控制的HAS结构
  • 2.5 相关工作
  • 2.6 本章小结
  • 第3章 基于小波的HAS结构
  • 3.1 引言
  • 3.2 背景知识和相关工作
  • 3.2.1 基于Haar小波的数据压缩
  • 3.2.2 其它相关工作
  • 3.3 W-HAS基本思想
  • 3.4 Haar小波分解的归并
  • 3.5 基于sse误差度量的数据节点
  • 3.5.1 数据节点的表示
  • 3.5.2 数据节点的加法
  • abs误差度量的数据节点'>3.6 基于maxabs误差度量的数据节点
  • 3.6.1 数据节点的表示
  • 3.6.2 数据节点的加法
  • 3.7 W-HAS结构中的误差控制
  • 3.7.1 基于sse误差度量的误差控制
  • abs误差度量的误差控制'>3.7.2 基于maxabs误差度量的误差控制
  • 3.8 实验
  • 3.9 本章小结和进一步工作
  • 第4章 基于加权随机抽样的HAS结构
  • 4.1 引言
  • 4.2 数据流上的随机抽样及其相关工作
  • 4.2.1 均匀随机抽样
  • 4.2.2 加权随机抽样
  • 4.2.3 其它相关工作
  • 4.3 WS-HAS的基本思想
  • 4.4 无放回加权随机抽样下的数据节点
  • 4.4.1 数据节点的表示
  • 4.4.2 数据节点的加法
  • 4.5 有放回加权随机抽样下的数据节点
  • 4.5.1 数据节点的表示
  • 4.5.2 数据节点的加法
  • 4.6 WS-HAS中的误差控制
  • 4.7 实验
  • 4.8 本章小结及进一步工作
  • 第5章 基于直方图的HAS结构
  • 5.1 引言
  • 5.2 H-HAS结构的基本思想
  • 5.3 等宽直方图下的H-HAS结构的实现
  • 5.4 最优直方图下的H-HAS结构
  • 5.5 实验
  • 5.6 本章小结和进一步工作
  • 第6章 基于HAS结构的并行数据流聚类
  • 6.1 引言
  • 6.2 W-HAS-clustering方法
  • 6.2.1 相关工作
  • 6.2.2 W-HAS-clustering的聚类距离计算
  • 6.2.3 数据流的规范化
  • 6.2.4 W-HAS结构中数据节点的加法
  • 6.2.5 规范化后数据流的W-HAS结构
  • 6.2.6 W-HAS-clustering聚类方法
  • 6.2.7 实验
  • 6.3 RP-HAS-clustering方法
  • 6.3.1 背景知识和相关工作
  • 6.3.2 RP-HAS-clustering总体思想
  • 6.3.3 RP-HAS结构中数据节点的加法
  • 6.3.4 规范化后数据流的RP-HAS结构
  • 6.3.5 RP-HAS-clustering聚类方法
  • 6.3.6 实验
  • 6.4 本章小结和进一步工作
  • 第7章 高维数据流中的HAS结构
  • 7.1 引言
  • 7.2 HD-HAS结构的动态维护
  • 7.2.1 概念与定义
  • 7.2.2 从数据集中提取数据节点
  • 7.2.3 数据节点的聚类
  • 7.2.4 HD-HAS的动态维护
  • 7.3 基于HD-HAS结构的数据流聚类
  • 7.4 基于HD-HAS结构的数据流分类
  • 7.4.1 基于HD-HAS结构的最近邻分类
  • 7.4.2 基于HD-HAS结构的SVM分类
  • 7.5 HD-HAS结构的实现
  • 7.5.1 Γ分量为空
  • 7.5.2 Γ分量用数据平方的均值表示
  • i∈DxixiT'>7.5.3 Γ=1/nsumfromxi∈DxixiT
  • 7.6 实验
  • 7.6.1 MNIST数据集上的测试
  • 7.6.2 KDD-CUP'99数据集上的测试
  • 7.7 本章小结和进一步工作
  • 第8章 数据流上的相似度分析
  • 8.1 引言
  • 8.2 Flajolet-Martin方法及其它相关工作
  • 8.3 集合相似度估算的EFM sketch方法
  • 8.4 EFM sketch方法的进一步讨论
  • 8.4.1 散列函数个数r的分析
  • 8.4.2 加快每个数据的处理速度
  • 8.5 HAS结构下数据流相似度分析
  • 8.6 实验
  • 8.7 本章小结和进一步工作
  • 第9章 结束语
  • 参考文献
  • 攻读博士期间发表论文情况
  • 致谢

    • 相关论文文献

    • [1].基于差分隐私的非等距直方图发布方法[J]. 网络与信息安全学报 2020(03)
    • [2].基于抽样排序和层次划分的直方图发布算法[J]. 计算机应用研究 2020(07)
    • [3].基于直方图的热红外图像增强方法[J]. 红外技术 2020(09)
    • [4].差分隐私下一种精确直方图发布方法[J]. 计算机研究与发展 2016(05)
    • [5].基于几何直方图的特征描述[J]. 华中科技大学学报(自然科学版) 2015(02)
    • [6].“直方图”检测题[J]. 中学生数理化(七年级数学)(配合人教社教材) 2020(Z2)
    • [7].“直方图”检测题[J]. 中学生数理化(七年级数学)(配合人教社教材) 2019(Z2)
    • [8].根据直方图解题[J]. 中学生数理化(七年级数学)(配合人教社教材) 2018(Z2)
    • [9].数码摄影常识8 了解摄影信息直方图的用途[J]. 旅游纵览 2009(11)
    • [10].曝光准不准参看直方图[J]. 影像视觉 2009(08)
    • [11].直方图读、补、算[J]. 中学生数理化(七年级数学)(配合人教社教材) 2010(06)
    • [12].深度了解直方图[J]. 影像视觉 2010(10)
    • [13].读懂直方图[J]. 影像视觉 2010(S1)
    • [14].基于直方图移位的信息隐藏方法[J]. 计算机产品与流通 2019(07)
    • [15].基于直方图条件熵的水声数据分类算法[J]. 计算机工程 2016(11)
    • [16].浅谈气候直方图的绘制方法和判读技巧[J]. 中学政史地(初中适用) 2014(10)
    • [17].基于直方图平移的低失真可逆数据隐藏[J]. 信息与控制 2013(05)
    • [18].深入了解直方图[J]. 影像视觉 2012(06)
    • [19].直方图问题易错点分析[J]. 语数外学习(初中版七年级) 2011(06)
    • [20].基于改进的空间直方图变换的图像编辑技术研究[J]. 微电子学与计算机 2014(07)
    • [21].血细胞直方图对成人缺铁性贫血诊断的意义[J]. 微量元素与健康研究 2012(01)
    • [22].基于压缩直方图的劣质数据库上相似连接结果大小估计[J]. 小型微型计算机系统 2012(10)
    • [23].用一个时钟在FPGA中计算直方图[J]. 电子设计技术 2011(05)
    • [24].基于直方图交核的人脸识别[J]. 北京工业大学学报 2011(08)
    • [25].白细胞直方图在白血病诊断中的临床应用[J]. 国际检验医学杂志 2008(02)
    • [26].基于非均匀有序直方图和锐化的红外图像增强[J]. 半导体光电 2020(01)
    • [27].血小板直方图在血小板计数中的应用[J]. 临床医药文献电子杂志 2017(83)
    • [28].R语言直方图绘制[J]. 数字技术与应用 2018(09)
    • [29].基于局部敏感直方图的时空上下文跟踪[J]. 传感器与微系统 2017(01)
    • [30].基于稀疏特征直方图约束的鲁棒目标跟踪[J]. 计算机工程与设计 2017(08)

    标签：;  ;  ;  ;  ;  

    基于遗忘特性的数据流概要结构及其应用研究
    下载Doc文档

    猜你喜欢

    © 2024 毕速过 版权所有 鄂ICP备12018319号-5