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

摘要

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

目录

声明

摘要

1绪论

1．1引言

1．2研究背景及意义

1．3国内外研究现状

1．3．1 ANN查询量化编码方法的研究现状

1．3．2 ANN查询距离度量方式的研究现状

1．4本文研究内容及篇章结构

1．4．1研究内容

1．4．2篇章结构

1．5本章小结

2相关理论与技术

2．1最近邻查询介绍

2．2精确查询与近似查询

2．2．1精确查询

2．2．2近似查询

2．3流数据处理技术

2．3．1相关概念及特性

2．3．2批量计算和流式计算

2．4本章小结

3面向流数据的滑动窗口分层抽样算法

3．1滑动窗口数据流概要生成技术

3．1．1指数直方图技术

3．1．2基本窗口技术

3．1．3 CS技术

3．2衰减滑动窗口及衰减函数

3．3高维流数据的低阶表示

3．4 TWD-SWSS算法

3．4．1算法背景

3．4．2算法原理

3．4．3算法特性分析

3．4．4算法实验

3．5本章小结

4基于离散系数的动态自适应量化算法

4．1基于hash的ANN相关概念

4．1．1随机hash与hash学习

4．1．2信息熵

4．2基于hash学习的动态自适应量化编码方法框架

4．2．1相关定义

4．2．2动态自适应编码量化方法的比特位分配方式

4．3动态自适应编码量化算法实现

4．4本章小结

5基于动态自适应量化方法的动态自适应距离度量算法

5．1相似性度量方式

5．2动态自适应距离度量算法相关定义

5．3动态自适应距离度量算法实现

5．4本章小结

6流数据实时分析的近似最近邻查询模型

6．1模型设计

6．1．1数据来源

6．1．2架构设计

6．2实验环境

6．2．1实验配置

6．2．2评价指标

6．2．3实验方法

6．3实验结果

6．4本章小结

7总结和展望

7．1研究总结

7．2研究展望

致谢

参考文献

附录