面向流式数据近似最近邻查询的降维与量化方法研究

【作者】 赵亮；

【导师】 王永利；

【作者基本信息】 南京理工大学 ， 智能计算与系统， 2018， 硕士

【摘要】 最近邻查询是各种大数据实时分析的基础问题,其目标是衡量不同对象间的差异性或相似性,在数据中寻找内容相似或者语义相关的对象。这里的对象可以是文本、网页、图像,在数学上都可以表示为向量或者向量的集合。理想的大数据相似性查询应该支持低延迟、高吞吐、持续稳定运行等特性,流数据场景下实时最近邻查询相关问题极具研究价值,在智能电网、智慧城市和公共服务等诸多实时分析领域具有广泛的应用前景。本文通过研究流式数据的抽样算法,使用滑动窗口分层抽样算法对海量流式数据进行数据浓缩,并通过对浓缩后的数据进行维度上的采样进行维度约简实现降维,同时研究一种有效的近似最近邻查询的量化与距离度量方式,最大限度地保持原始数据的近邻结构,实现流式数据的近似最近邻查询,提高查询准确率。本文的主要研究工作如下所述:1、提出一种在滑动窗口模型下,基于时间权重的滑动窗口分层抽样算法,通过将滑动窗口划分成多个基本窗口,然后根据预设的衰减函数为每个基本窗口设定相应的权重,再根据此权重值和基本窗口中数据元素的个数设定其抽样比,根据此抽样比对流数据进行抽样实现数据浓缩,同时通过计算不同数据维度的重要程度对数据维度进行抽样实现降维。2、针对目前基于hash学习的近似最近邻查询方法通常学习一组用于数据投影的超平面,并且简单地对来自每个超平面划分的结果进行二值化编码,而忽视了信息可能不均匀地分布在整个投影中,每一维投影中数据取值范围可能不一样的事实,本文提出一种动态自适应编码量化方法,根据投影维度的信息量动态地为该维度分配相应的二进制编码位数,并通过动态规划使得所有投影的总信息量最大,以尽可能地保持原始数据的近邻结构。3、在前述动态自适应编码量化算法的基础上,提出一种动态自适应距离度量算法,根据每一投影维度的编码位数计算其二进制编码间的距离,以解决现有距离度量方法将整个二进制串看作一个整体计算距离,仅仅只适用于单位量化的弊端。针对上述提出的相关算法,本文在最后进行了实验验证,实验结果表明,经过滑动窗口分层抽样算法对流式数据进行抽样,有效地保持了流式数据的概要信息,并证明了动态自适应编码量化方法较传统的hash量化方法有显著的改进,动态自适应编码方法和距离度量方式对原始数据的近邻结构保持优于传统固定位数量化编码以及海明距离度量方式。更多还原

【Abstract】 Nearest Neighbor Search is the basic problem of real-time analysis of all kinds of big data,which is to measure the difference or similarity between different objects,and to find the similar or semantic related objects in the data set.Mathematically,Objects,including text,web pages and images,can be represented as a collection of vectors or vectors.The ideal large data similarity query should have low latency,high throughput and stable operation.Real-time nearest neighbor search in streaming data scenarios is of great research value,which has a wide range of applications in real-time analysis such as smart grid,smart city and public service.In this paper,by researching the sampling algorithm of streaming data,using the sliding window hierarchical sampling algorithm to concentrate the massive data,and sampling the concentrated data implement dimensions reduction.Simultaneously studying the quantization and distance measurement of an effective approximate nearest-neighbor search,and maximizing the original data neighbor structure achieve the nearest neighbor search of streaming data,and improve the query accuracy.The main research work in this paper are as follows:Firstly,proposing a sliding window hierarchical sampling method based on time-weighted sliding window model.By dividing the sliding window into several basic windows and using the preset attenuation function to set the corresponding weight of each basic window,and then according to the weight value and the number of data elements in the basic window to set the sampling ratio,according to the sampling ratio sampling the stream data to concentrate the data.At the same time,the data dimension is sampled to reduce dimensions by calculating the importance of different data dimensions.Secondly,because of the current hash-based approximate nearest-neighbor search methods usually learn a set of hyperplanes for data projection,and simply binarize the results from each hyperplane division,while ignoring the fact that the information may be unevenly distributed throughout the projection dimension,and the values of the data in each dimension projection may not be the same.In this paper,we proposed a dynamic adaptive coding quantization method,which dynamically allocates the corresponding binary coded bits to the dimension according to the information amount of the projection dimension.By using the dynamic programming,the total information of all the projections is maximized so as to keep the neighborhood structure of the original data as much as possible.Thirdly,based on the dynamic adaptive coding quantization algorithm,we proposed a dynamic adaptive distance measurement algorithm,which calculates the distance between binary codes according to the number of bits coded for each projection dimension.So as to solve the problem that the existing distance measurement method reduces the entire binary string as a entirety to calculate distance,which only applies to the unit quantification.Aiming at the above algorithms proposed in this paper,the experiments are carried out in the end.The experimental results show that sampling the streaming data through the sliding window hierarchical sampling algorithm effectively preserves the summary information of the streaming data,and prove that the dynamic adaptive coding quantization method has a significant improvement over the traditional hash quantization method.The theory proves that the dynamic adaptive coding method and the distance measurement method is superior to the traditional fixed-digit quantization coding and the Hamming distance measurement method on maintaining the neighborhood structure of original data.更多还原