有效解决数据缺失问题的聚集查询算法

近年来,工业界和学术界面临着非常严重的数据缺失问题,缺失值极大降低了数据可用性。现有的缺失值填充技术需要较大的时间开销,很难满足大数据查询实时性的需求,为此,研究在有缺失值的情况下高效处理聚集查询,将基于采样的近似聚集查询处理与缺失值填充技术有效的结合,快速返回满足用户需求的聚集结果。采用基于块（block-level）的采样策略,在采集到的样本上进行缺失值填充,并根据缺失值填充的结果重构得到聚集结果的无偏估计。真实数据集和合成数据集上的实验结果表明,该文的方法比当前最好的方法在保证相同精度的前提下,大大提升了查询效率。     

基于AP聚类的不完整大数据填充

不完整数据的分析与填充一直是大数据处理的热点研究课题,传统的分析方法无法对不完整数据直接聚类,大部分方法先填充缺失值,然后对数据聚类。这些方法一般利用整个数据集对缺失数据进行填充,使得填充值容易受到噪声的干扰,导致填充结果不精确,进而造成聚类精度很低。提出一种不完整数据聚类算法,对不完全信息系统的相似度公式进行重新定义,给出不完整数据对象间的相似度度量方式,进而直接对不完整数据聚类。根据聚类结果将同一类对象划分到相同的簇中,通过同一类对象的属性值对缺失值进行填充,避免噪声对填充值的干扰,提高填充结果的精确性。实验结果表明,提出的方法能够对不完整数据进行聚类,并有效提高缺失数据的填充精度。     

基于互信息属性排序的不完整数据聚类算法

数据缺失对聚类算法提出了挑战,传统方法往往采用均值或回归方法将不完整数据进行填充,再对填充后的数据进行聚类.为解决均值填充和回归填充等方法在数据缺失比率增大时填充精度以及聚类效果变差的问题,提出一种新的不完整数据相似度计算方法.以期望互信息为依据对数据集中的属性排序,充分考虑了数据集中与位置相关的属性值特征,以数据集本身元素作为缺失值填充的来源,对排序后的不完整数据集进行相似度填充计算,最后采用基于局部密度的聚类算法进行聚类.利用UCI机器学习库中的数据集验证本文填充聚类算法,实验结果表明,当数据集中缺失值增多时,算法对缺失值的容忍性较好,对缺失元素的恢复能力较强,填充精度以及最终聚类结果方面均表现良好.本文填充计算相似度的方法考虑数据集的每个属性值来对缺失值逐个填充,因而耗时较多.     

基于共享知识的不完整大数据填充方法

针对传统大数据填充方法相似度度量方法单一,且通常只考虑原数据集内部联系,使得填充数据容易被原数据集限制、失去自身原有特点、填充结果不客观等问题.提出一种新的概念——共享知识,该方法首先基于共享知识构建不完整数据集与异源相似完整数据集的共享关系,并建立共享信息系统;其次通过新的相似度度量方法建立它们对象间的相似关系,从而用异源相似完整数据集对象对不完整的数据集对象进行相似填充.实验结果表明,新的相似度度量方法比单一的数值型相似度度量方法填充精度更高.与其他填补算法相比,该方法对缺失值的填充精度值能够稳定地保持在0.85以上,均方根误差稳定在0.15之下,充分保留了填充值的客观性,填充效果更好.     

不完整大数据的分布式聚类填充算法

传统大数据填充算法是根据整个数据集对缺失数据进行填充,使得填充值容易受到不同类别数据的干扰,导致填充结果不精确。针对该问题,给出不完整数据的相似度度量方法,使用近邻传播( AP )算法对不完整数据进行聚类。采用云计算技术优化AP聚类算法,实现一种基于MapReduce的分布式聚类算法,根据算法聚类结果将同一类数据对象划分到相同簇中,并利用同一类对象的属性值对缺失值进行填充。实验结果表明,该算法能实现不完整大数据的聚类,同时加快聚类速度,提高缺失数据的填充精度。     

基于概率矩阵分解的不完整数据集特征选择方法

在机器学习理论与应用中,特征选择是降低高维数据特征维度的常用方法之一。传统的特征选择方法多数基于完整数据集,对实际应用中普遍存在缺失数据的情形研究较少。针对不完整数据中含有未被观察信息和存在异常值的特点,提出一种基于概率矩阵分解技术的鲁棒特征选择方法。使用基于分簇的概率矩阵分解模型对数据集中的缺失值进行近似估计,以有效测量相邻簇之间数据的相似性,缩小问题规模,同时降低填充误差。依据缺失数据值存在少量异常值的情形,利用基于l_2,1损失函数的方法进行特征选择,在此基础上给出不完整数据集的特征选择方法流程,并对其收敛性进行理论分析。该方法利用不完整数据集中的所有信息,有效应对不完整数据集中异常值带来的影响。实验结果表明,相比传统特征选择方法,该方法在合成数据集上选择更少的无关特征,可降低异常值带来的影响,在真实数据集上获得了较高的分类准确率,能够选择出更为准确的特征。     

一种基于数据综合的智能搜索模型SMBDI

本文以语义Web中基于数据综合的应用为背景，提出了一种由本体论提供语义支持的智能搜索模型SMBDI．给出了该模型在底层数据综合、用户界面及查询处理等方面的实施策略。模型分析表明，该模型可以解决目前搜索方式存在的结果不完整或冗余度过高、存在大量无用信息以及数据格式不统一等问题，为语义Web在搜索及查询方面的应用提供了一种新的实现方案。     

Spark环境下不完整数据集成填充方法

目前已有的不完整数据填充方法大多局限于单一类型的缺失变量,对大规模数据的填充效果相对弱势.为了解决真实大数据中混合类型变量的缺失问题,本文提出了一个新的模型——SXGBI(Spark-based eXtreme Gradient Boosting Imputation),其适应于连续型和分类型两种缺失变量并存的不完整数据填充,同时具备快速处理大数据的泛化能力.该方法通过对集成学习方法XGBoost的改进,将多种补全算法结合在一起,构建了一个集成学习器,并结合Spark分布式计算框架进行了并行化设计,能较好地运行于Spark分布式集群上.实验表明,随着缺失率的增长,SXGBI在RMSE、PFC和F1几项评价指标上都取得了比实验中其它填充方法更好的填充结果.此外,它还可以有效地运用在大规模的数据集上.     

构造性覆盖下不完整数据修正填充方法

不完整数据处理是数据挖掘、机器学习等领域中的重要问题,缺失值填充是处理不完整数据的主流方法。当前已有的缺失值填充方法大多运用统计学和机器学习领域的相关技术来分析原始数据中的剩余信息,从而得到较为合理的值来替代缺失部分。缺失值填充大致可以分为单一填充和多重填充,这些填充方法在不同的场景下有着各自的优势。但是,很少有方法能进一步考虑样本空间分布中的邻域信息,并以此对缺失值的填充结果进行修正。鉴于此,本文提出了一种可广泛应用于诸多现有填充方法的框架用以提升现有方法的填充效果,该框架由预填充、空间邻域信息挖掘和修正填充三部分构成。本文对7种填充方法在8个UCI数据集上进行了实验,实验结果验证了本文所提框架的有效性和鲁棒性。     

无线传感器网络中缺失数据估计算法

为了提高无线传感器网络(WSN)中缺失数据估计值的精度,提出了一种自决策插值算法。该算法能够根据数据集的空间相关性以及缺失数据的连续性选择不同的缺失数据估计策略,并将自回归滑动平均(ARMA)模型引入到对缺失数据插值的研究中。与传统缺失值估计算法相比,该算法不仅考虑到无线传感器网络的特性,而且考虑到数据集本身的特性。在真实数据集上测试结果表明,该算法提高了对缺失值估计的精度。     

Efficient k-dominant skyline query over incomplete data using MapReduce

Skyline queries are extensively incorporated in various real-life applications by filtering uninteresting data objects. Sometimes, a skyline query may return so many results because it cannot control the retrieval conditions especially for highdimensional datasets. As an extension of skyline query, the kdominant skyline query reduces the control of the dimension by controlling the value of the parameter kto achieve the purpose of reducing the retrieval objects. In addition, with the continuous promotion of Bigdata applications, the data we acquired may not have the entire content that people wanted for some practically reasons of delivery failure, no power of battery, accidental loss, so that the data might be incomplete with missing values in some attributes. Obviously, the k-dominant skyline query algorithms of incomplete data depend on the user definition in some degree and the results cannot be shared. Meanwhile, the existing algorithms are unsuitable for directly used to the incomplete big data. Based on the above situations, this paper mainly studies k-dominant skyline query problem over incomplete dataset and combines this problem with the distributed structure like MapReduce environment. First, we propose an index structure over incomplete data, named incomplete data index based on dominate hierarchical tree (ID-DHT). Applying the bucket strategy, the incomplete data is divided into different buckets according to the dimensions of missing attributes. Second, we also put forward query algorithm for incomplete data in MapReduce environment, named MapReduce incomplete data based on dominant hierarchical tree algorithm (MR-ID-DHTA). The data in the bucket is allocated to the subspace according to the dominant condition by Map function. Reduce function controls the data according to the key value and returns the k-dominant skyline query result. The effective experiments demonstrate the validity and usability of our index structure and the algorithm.     

Histogram-by: A grouping operator for continuous domains

In this paper, we propose a new operator, histogram-by, which provides a grouping for continuous domains, which partitions records into several groups by given ranges of the target attributes. The histogram-by operator can be represented as histogram-by clause in the SQL statement, and can be easily amenable to query optimization. As the application of the histogram-by operator, we introduce a multi-dimensional histogram query, which returns aggregate values of all ranges specified by the histogram-by clause. To process the query efficiently, we propose effective algorithms using aggregate R-trees. Our experimental results show that our algorithms are reliable in terms of performance over the synthetic and real-world datasets.     

语义缓存的聚集查询匹配研究

为提高海量数据库系统的查询效率，围绕海量数据库系统中的聚集查询技术，把通常应用于小型数据库查询的语义缓存技术拓展到海量数据库的聚集查询中．首先研究了面向聚集查询的语义缓存形式化描述，在此基础上讨论了利用缓存处理查询的条件并对查询匹配进行了分类，提出并实现了包含匹配判定算法和相交匹配判定算法，最后给出了相应的实验结果．在某大型实际工程中的应用表明上述判定算法是有效的．     

Querying and ranking incomplete twigs in probabilistic XML

As the next generation language of the Internet, XML has been the de-facto standard of information exchange over the web. A core operation for XML query processing is to find all the occurrences of a twig pattern in an XML database. In addition, the study of probabilistic data has become an emerging topic for various applications on the Web. Therefore, researching the combination of XML twig pattern and probabilistic data is quite significant. In prior work of probabilistic XML, the answers of a given twig query are always complete. However, complete answers with low probabilities may be deemed irrelevant while incomplete answers with high probabilities are of great significance because incomplete answers may be the potential answers that interest the users. Different from complete evaluation, evaluating incomplete twigs in probabilistic XML introduces some new challenges. On one hand, incomplete queries do not only obtain complete matches, but also return answers that contain considerable incomplete matches. On the other hand, the processing of incomplete evaluation is more complicated. It is obvious that a ranking approach should be adopted along with evaluating incomplete answers. In this paper, we propose an efficient algorithm to handle the problem of querying incomplete twigs over the probabilistic XML database. We also present a novel algorithm for ranking the incomplete answers. The experimental results show that our proposed algorithms can improve the performance of querying and ranking incomplete twigs significantly.     

一种面向不完整数据流上的k-支配skyline查询算法

skyline查询是数据挖掘一个重要的研究方向,在基于数据的决策支持等应用中有着重要的作用.由于现实应用中存在着大量的不完整数据流,但大多数现有的skyline查询算法都依赖于如下的假设:1)任意数据点的所有维度值都是已知的;2)数据集是稳定、有界的并且可以随意访问.此外,随着数据维度的增加,skyline数据点的个数会变得过多,因此引入了k-支配skyline的概念,但是不完整数据的k-支配关系并不具有传递性,现有的skyline查询算法都无法适用.基于这些问题,考虑到数据流高维、无界、顺序性的特点,并且在某些维度上可能具有缺失值的特性,提出了一种新的基于滑动窗口的不完整数据流的k-支配skyline查询算法,实验结果表明,算法不仅可以支持不完整数据流上的k-支配skyline计算,并能够保证效率和性能.     

异常信息的智能分类算法研究

信息处理过程中对异常信息的智能化处理是一个前沿的且富有挑战性的研究方向;针对所获取的信息由于噪声干扰等因素存在缺失这一异常现象,提出了一种不完整(缺失)数据的智能分类算法;对于某一个不完整样本,该方法首先根据找到的近邻类别信息得到单个或多个版本的估计样本,这样在保证插补的准确性的同时能够有效地表征由于缺失引起的不精确性,然后用分类器分类带有估计值的样本;最后,在证据推理框架下提出一种新的信任分类方法,将难以划分类别的样本分配到对应的复合类来描述由于缺失值引起的样本类别的不确定性,同时降低错误分类的风险;用UCI数据库的真实数据集来验证算法的有效性,实验结果表明该算法能够有效地处理不完整数据分类问题.     

数据流上的复合滑动窗口聚集算法

基于滑动窗口的聚集查询是数据流研究领域的一个热点问题。在已有的研究工作中,聚集算法都是针对立即执行的连续查询提出的,这些算法均是当数据流新到一个元组立即计算一次聚集结果。而在实际应用中,连续查询有时采取的是周期执行方式。论文针对周期执行的连续查询提出了复合滑动窗口聚集算法,即数据流新到一个元组,将它插入到基本窗口中,当基本窗口被插满时计算一次聚集结果。给出了非增量式和增量式两种算法。理论分析和实验结果表明增量式算法具有较好的性能。     

Aggregate Queries Over Conditional Tables

Conditional tables have been identified long ago as a way to capture unknown or incomplete information. However, queries over conditional tables have never been allowed to involve column functions such as aggregates. In this paper, the theory of conditional tables is extended in this direction, and it is shown that a strong representation system exists which has the closure property that the result of an aggregate query over a conditional table can be again represented by a conditional table. It turns out, however, that the number of tuples in a conditional table representing the result of an aggregate query may grow exponentially in the number of variables in the table. This phenomenon is analyzed in detail, and tight upper and lower bounds concerning the number of tuples contained in the result of an aggregate query are given. Finally, representation techniques are sketched that approximate aggregation results in tables of reasonable size.