面向不确定数据流的近似ER-Topk查询处理

随着移动互联网的快速发展以及信息技术的普遍应用,在许多应用中都产生了海量、不确定性数据,包括金融、军事、位置服务、医疗以及气象等。然而,传统的确定性数据管理方法很难管理不确定数据,亟需开发新型数据管理方法。可能世界模型被广泛用于为不确定数据建模,通过该模型可以衍生出诸多确定性的可能世界实例。不确定性数据流是指高速到达的海量不确定元组序列,因而不确定数据流管理比不确定性静态数据管理更具挑战性。面向于不确定数据流的ER-Topk查询是一个典型问题,但是处理复杂度高。提出一种近似算法来处理该查询,具有较小的空间复杂度;同时,还通过搜索策略优化来进一步提升查询处理效率。实验结果验证了所提方法的有效性和高效性。     

一种不确定数据流聚类算法

提出了EMicro算法,以解决不确定数据流上的聚类问题.与现有技术大多仅考虑元组间的距离不同,EMicro算法综合考虑了元组之间的距离与元组自身不确定性这两个因素,同时定义新标准来描述聚类结果质量.还提出了离群点处理机制,系统同时维护两个缓冲区,分别存放正常的微簇与潜在的离群点微簇,以期得到理想的性能.实验结果表明,与现有工作相比,EMicro的效率更高,且效果良好.     

基于GPU的不确定数据流窗口连接运算

在很多新兴应用领域、如传感器网络,实时监控系统等,产生的数据流是不断变化的、连续到达的、数据值可能不确定、且必须被快速处理。其中有些操作,如数据流的实时窗口连接运算,非常消耗时间,这对数据流处理系统的性能提出了严峻的挑战。目前,大多数算法采用软件优化来提高处理速度,但其性能提高有限。利用GPU（图形处理器）的高并行度、多线程、高带宽的并行处理能力,设计了一种软硬件结合的方法来加速处理数据流的窗口连接操作。在CUDA（统一计算架构）下,由CPU控制将内存中的数据传输至GPU存储器中,然后利用多线程进行并行处理。实验验证了提出的方法可以大幅度提高多数据流窗口连接的处理速度,可达到纯软件处理的50倍左右。     

不确定时间序列的规约方法

为提高不确定时间序列的查询效率,在对不确定时间序列数据集进行建模的基础上,提出由不确定时间序列向确定时间序列的 3种规约方法,分别为概率最大法、混合规约法和均值法,并给出具体的规约过程。实验结果表明,上述3种规约方法能减少时间序列的不确定性,为其相似性匹配、搜索和查询操作提供依据。     

基于粗糙模糊集的不确定数据流聚类算法??

为解决高维和高不确定级别的数据流聚类问题,提出了一种针对不确定数据流的聚类算法HFMicro。引入粗糙模糊集理论,定义了一种新的不确定数据流模型,并利用隶属程度的上、下近似来描述微簇。根据粗糙模糊集间的相似程度来选择最合适的微簇。使用动态衰减窗口模型提高算法的效率和聚类效果。由于采用了离线聚类模式,使得算法具有较好的实时性。实验结果表明,该算法能够很好地处理高维和高不确定级别的数据流,同时兼容存在级不确定性和属性级不确定性,与现有算法相比效果更好。     

基于免疫原理的不确定数据流聚类算法

提出一种基于免疫原理、对不确定数据流进行聚类的算法——IUMicro。IUMicro针对不确定数据流上元组级不确定性问题,引入动态更新以适应数据变化的免疫模型,其中包括一种有效的在线收集数据流统计信息的B细胞特征结构及其更新策略。为兼顾元组存在概率与元组间的距离两方面因素,定义概率识别半径,为每个不断到达的数据元组找到合理的候选簇。离线聚类根据免疫细胞识别区域的空间关系,进行任意形状的无监督聚类。实验结果表明,IUMicro能有效抑制噪声,具有良好的聚类质量和较快的处理速度。     

隐含概念漂移的不确定数据流集成分类算法

近年来,数据流分类问题已经逐渐成为数据挖掘领域的一个研究热点,然而传统的数据流分类算法大多只能处理数据项已知并且为精确值的数据流,无法有效地应用于现实应用中普遍存在的不确定数据流。为建立适应数据不确定性的分类模型,提高不确定数据流分类准确率,提出一种针对不确定数据流的集成分类算法,该算法将不确定数据用区间及其概率分布函数表示,用C4.5决策树分类方法和朴素贝叶斯分类方法训练基分类器,在合理处理数据流中不确定性的同时,还能有效解决数据流中隐含的概念漂移问题。实验结果表明,所提算法在处理不确定数据流的分类时具有较好的鲁棒性,并且具有较高的分类准确率。     

不确定数据流上的并行反Skyline查询

作为Skyline查询的一种重要变体,不确定数据流上的反Skyline查询已经成为研究的热点。已有的单机算法无法应对诸如高速数据流、高数据维度、大滑动窗口等情况,相应提出并行查询处理算法PRSUDS。算法采用基于角度划分的分发策略将处理任务分发至各并行节点,给出该分发策略的正确性证明,进而设计、实现算法的并行处理框架。实验结果表明PRSUDS算法较单机算法具有更好的综合性能,更能满足数据流查询的实时性要求。     

有色冶金过程不确定优化方法探讨

有色冶金过程受原料来源多样、工况条件波动、生产成分变化等因素的影响,存在大量的不确定性,严重影响了冶炼生产的稳定性与可靠性.鉴于此,综述不同类型不确定性优化问题的描述方法,具体包括概率不确定优化问题、模糊不确定优化问题和区间不确定优化问题.通过分析有色冶金生产过程的特点与需求,以3种典型的有色冶金过程不确定优化问题为例,探讨不同类型的有色冶金过程不确定优化方法.针对氧化铝生料浆配料过程的概率不确定优化问题,采用基于Hammersley sequence sampling(HSS)的方法实现不确定模型的确定性转换;针对湿法炼锌除铜过程的模糊不确定优化问题,采用基于模糊规则的方法进行确定性评估;针对锌电解分时供电过程的区间不确定优化问题,采用基于min-max的方法求解鲁棒解.工业运行数据均验证了上述方法的有效性.     

基于概率衰减窗口模型的不确定数据流频繁模式挖掘

考虑到不确定数据流的不确定性,设计了一种新的概率频繁模式树PFP-tree和基于该树的概率频繁模式挖掘方法PFP-growth.PFP-growth使用事务性不确定数据流及概率衰减窗口模型,通过计算各概率数据项的期望支持度以发现概率频繁模式,其主要特点有：考虑到窗口内不同时间到达数据项的贡献度不同,采用概率衰减窗口模型计算期望支持度,以提高模式挖掘准确度;设置数据项索引表和事务索引表,以加快频繁模式树检索速度;通过剪枝删除不可能成为频繁模式的结点,以降低模式树的存储及检索开销;对每个结点都设立一个事务概率信息链表,以支持数据项在不同事务中具有不同概率的情形.实验结果表明,PFP-growth在保证挖掘模式准确度的前提下,在处理时间和内存空间等方面都具有较好的性能.     

基于序列聚类的事件流数据特征分析

事件流是近年来兴起的一种对实时进入系统的海量数据进行分析查询的应用,而数据特征是评价系统所需要的负载模型的重要部分。以网络安全监控为背景,提出一种将事件流聚集成时间序列并进行相似性聚类来分析数据特征的方法。通过适当的粒度聚合,将事件流转化成时间序列,选取周期性的时间序列作为代表消除随机干扰,给出基于序列线性相似性的聚类算法。聚类试验表明,具有相似时间特征的事件流可以被有效地聚集到同一类中。     

基于最近邻过滤的数据流Skyline算法

在Skyline查询算法中,Lazy算法的数据处理能力较弱。针对该问题,利用最近邻过滤的思想,提出改进的NNSC算法。在预处理阶段,利用欧氏距离定义一个阈值,如果新插入数据对象的欧氏距离大于阈值,提前处理该对象,以提高算法利用率,减少资源的消耗。实验结果证明,NNSC可降低时空复杂度,对于正相关数据,性能提升效果明显。     

不确定数据流上Top-k异常点查询算法

近几年,随着数据流和不确定数据的产生,不确定数据流上的异常点检测成为新的研究热点。然而,现有的不确定数据的异常点定义中涉及3个参数,这对于用户是非常难设定的,以致不能查询到适合的异常点。在大多时候,用户更想知道最可能是异常点的对象,因此提出了不确定数据流上的top-k异常点查询算法。该算法通过估计数据对象异常点的概率范围而进行剪枝,从而减少了一些不必要的计算,同时增量地计算数据对象异常点的概率范围。在真实数据集和合成数据集上进行了一系列的模拟实验,证明了算法的性能。     

基于滑动窗口的Top-K概率频繁项查询算法研究

频繁项查询在网络监控、网络入侵检测、关联规则挖掘等方面是一项非常重要的技术.该技术在静态的不确定数据中已经得到了深入的研究.但随着数据流特征和不确定性表现的日益明显,在不确定数据流环境下的查询已经成为一项新的研究课题.因此基于数据流普遍采用的滑动窗口模型,提出了一种高效的概率Top-K频繁项查询算法sTopK-UFI.该算法避免了每次窗口更新都重新计算查询答案,而是利用现有的计算结果进行增量更新,从而减少查询代价.另外,该算法基于窗口中的现有数据对未来可能成为频繁项的元素进行预测,并利用泊松分布计算元素成为频繁项的概率上下界,提出相应的过滤策略,可以显著减少检测数据的数量,提高查询效率.实验结果表明,所提出算法可以有效地减少候选集、降低搜索空间、改善在不确定数据流上的查询性能.     

一种基于不确定规则的数据时效性判定方法

数据过时是影响数据质量的重要因素,因此判定数据时效性对于提高数据质量至关重要.当前判定数据时效性的方法可分为两类:基于时间戳的方法和基于规则的方法.基于时间戳的方法要求精确完整的时间戳,但这样的时间戳在很多应用中不存在.基于规则的方法不要求时间戳,但现有方法均依赖于冗余元组,且不能对数据时效性做出定量判定.同时,这些方法均基于确定规则,无法表达不确定的领域知识.针对上述问题,提出不确定时效规则及相应的数据时效性模型.基于该模型,进一步给出了两个可定量地判定数据时效性的算法.同时,还给出了时效规则的学习算法.真实数据上的实验结果验证了算法的有效性.     

不确定性数据管理技术研究综述

随着数据采集和处理技术的进步,人们对数据的不确定性的认识也逐步深入,在诸如经济、军事、物流、金融、电信等领域的具体应用中,数据的不确定性普遍存在,不确定性数据的表现形式多种多样,它们可以以关系型数据、半结构化数据、流数据或移动对象数据等形式出现,目前,根据应用特点与数据形式差异,研究者已经提出了多种针对不确定数据的数据模型,这些不确定性数据模型的核心思想都源自于可能世界模型,可能世界模型从一个或多个不确定的数据源演化出诸多确定的数据库实例,称为可能世界实例,而且所有实例的概率之和等于1.尽管可以首先分别为各个实例计算查询结果,然后合并中间结果以生成最终查询结果,但由于可能世界实例的数量远大于不确定性数据库的规模,这种方法并不可行,因此,必须运用排序、剪枝等肩发式技术设计新型算法,以提高效率.文中介绍了不确定性数据管理技术的概念、特点与挑战,综述了数据模型、数据预处理与集成、存储与索引、查询处理等方面的工作.     

基于流式计算的遥感卫星数据快视处理方法

随着高分辨率遥感卫星数据获取能力和地面数传接收能力的提高，现有遥感卫星快视处理系统的处理负载增大，实时性要求越来越难以满足。针对这些问题，采用流式计算思想提出了一种新的遥感卫星数据快视处理系统设计方法。在分析遥感卫星数据快视处理数据流特点的基础上，应用Storm框架对现有系统进行并行优化，设计遥感数据流处理任务拓扑结构，同时利用消息队列中间件Kafka改进处理单元间数据交换和数据缓存方式。实验表明，该系统在数据吞吐率和可靠性方面测试效果良好。     

不确定离散系统的最优鲁棒滤波

本文对一类含有范数有界参数不确定的离散线性系统的滤波问题进行了研究,了有限时域时变以及无限时域时不变两种情形,给出了一个对所有可容许参数不确定都能满足的估计误差方差上界,得到了使得该上界达到最小的最优鲁棒滤波器形式及其存在的充要条件,数值结果表明：当系统存在参数不确定时,本文所得到的滤波器优于标准的Ｋａｌｍａｎ滤波器以及文（４）中的鲁棒滤波器。     

Continuous Outlier Monitoring on Uncertain Data Streams

Outlier detection on data streams is an important task in data mining. The challenges become even larger when considering uncertain data. This paper studies the problem of outlier detection on uncertain data streams. We propose Continuous Uncertain Outlier Detection （CUOD）, which can quickly determine the nature of the uncertain elements by pruning to improve the efficiency. Furthermore, we propose a pruning approach -- Probability Pruning for Continuous Uncertain Outlier Detection （PCUOD） to reduce the detection cost. It is an estimated outlier probability method which can effectively reduce the amount of calculations. The cost of PCUOD incremental algorithm can satisfy the demand of uncertain data streams. Finally, a new method for parameter variable queries to CUOD is proposed, enabling the concurrent execution of different queries. To the best of our knowledge, this paper is the first work to perform outlier detection on uncertain data streams which can handle parameter variable queries simultaneously. Our methods are verified using both real data and synthetic data. The results show that they are able to reduce the required storage and running time.     

一种联系数表达的位置不确定数据流聚类算法

在不确定数据流聚类算法的研究中,位置不确定性是一种新的不确定数据类型.已有的不确定数据模型不能很好地描述和处理位置不确定数据.鉴于此,在提出基于联系数的位置不确定数据模型、联系距离函数、微簇密度可达性等主要概念的基础上,提出了一种联系数表达的位置不确定数据流聚类算法--UCNStream.数据流聚类算法采用在线/离线两级处理框架,使用基于密度峰值思想的初始化策略,定义了新的可动态维护的微簇聚类特征向量.利用衰减函数和微簇删除机制对微簇进行在线维护,准确地反映了数据流的演化过程.最后,分析了算法的计算复杂性,并通过对实际数据集上的实验与几种优秀的聚类算法进行了比较,实验结果表明,UCNStream算法具有较高的聚类精度和处理效率.