M2LSH:基于LSH的高维数据近似最近邻查找算法

在许多应用中,LSH(Locality Sensitive Hashing)以及各种变体,是解决近似最近邻问题的有效算法之一.虽然这些算法能够很好地处理分布比较均匀的高维数据,但从设计方案来看,都没有针对数据分布不均匀的情况做相应的优化.针对这一问题,本文提出了一种新的基于LSH的解决方案(M2LSH,2 Layers Merging LSH),对于数据分布不均匀的情况依然能得到一个比较好的查询效果.首先,将数据存放到具有计数功能的组合哈希向量表示的哈希桶中,然后通过二次哈希将这些桶号投影到一维空间,在此空间根据各个桶中存放的数据个数合并相邻哈希桶,使得新哈希桶中的数据量能够大致均衡.查询时仅访问有限个哈希桶,就能找到较优结果.本文给出了详细的理论分析,并通过实验验证了M2LSH的性能,不仅能减少访问时间,也可提高结果的正确率.     

基于深度学习的散列检索技术研究进展

大数据时代,数据呈现维度高、数据量大和增长快等特点。面对大量的复杂数据,如何高效地检索相似近邻数据是近似最近邻查询的研究热点。散列技术通过将数据映射为二进制码的方式,能够显著加快相似性计算,并在检索过程中节省存储和通信开销。近年来深度学习在提取数据特征方面表现出速度快、精度高等优异的性能,使得基于深度学习的散列检索技术得到越来越广泛的运用。总结了深度学习散列的主要方法和前沿进展,并对未来的研究方向展开简要探讨。     

时空道路网络连续最近邻查询的新方法

时空道路网络里连续最近邻查询在时空数据库查询的领域是一个新的重要课题，本文提出一个有效的方法（IE）以处理道路网络里的移动对象的k个最近邻居（k-NN）查询问题。     

SLSB-forest:高维数据的近似k近邻查询

近似k近邻查询的研究一直受到广泛关注,局部敏感散列(LSH)是解决此问题的主流方法之一.LSH及目前大部分改进版本都会面临以下问题:数据散列以后在桶里分布不均匀;无法准确计算对应参数k的查询范围建立索引.基于此,将支持动态数据索引的LSH和B-tree结合,构建新的SLSB-forest索引结构,使散列桶里的数据维持在一个合理的区间.针对SLSB-forest提出了两种查询算法:快速查找和准确率优先查找,并通过理论和实验证明查找过程中查询范围的动态变化.     

一种基于密度网格索引的k-最近邻查询算法

基于位置的服务的迅速发展对服务响应的效率提升和成本控制提出了更高的要求,本文提出了一种基于密度网格索引的k-最近邻查询算法,该算法首先利用矩形的几何特点获取一系列候选搜索半径,随后根据移动对象的密度分布情况选择适当的候选搜索半径进行距离过滤,尽量减少不必要的内存索引单元和磁盘索引单元的访问.实验表明,实现了本文算法的密度网格索引在k-最近邻查询的查询效率上与ST²B-tree不相上下,而查询的I/O代价与其他索引结构相比有明显的优势.     

基于改进最近邻算法的电力数据缺失处理方法

针对电力数据采集缺失算法存在的准确率低、计算开销大等缺陷,文中将最近邻算法与对抗神经网络结合,提出了一种电网用户信息缺失处理算法。对于最近邻算法存在的高维度数据处理能力差的问题,使用自编码器对高维数据进行降维,同时通过变分方法引入了隐变量学习数据中可连续、可解释的特征。利用最近邻算法生成数据样本标签,由对抗神经网络根据样本标签和自编码器输出特征最终生成缺失数据。在公开数据集进行的实验测试中,所提算法的准确率与迭代次数在所有应用场景及对比算法中均为最优,充分表明了算法的高效性和工程实用性。     

WQ:基于权重求解的哈希算法

由于最近邻查询算法一般需要较高时间和空间代价,往往不能满足大数据查询的需要.哈希技术可以大幅度减少查询时间和存储空间,其主要思想是将原始空间中的高维数据映射成为一组编码,且满足保相似性原则.现有的大部分哈希方法一般认为哈希编码的各维度权重相同.然而在实际情况中,不同的维度往往携带有不同的信息.为此,本文提出了新的算法,为编码的每个维度分配权重,并提出了对应的量化编码方式.理论证明了算法的可行性,在真实数据集下与其他哈希算法对比实验也验证了该算法的有效性.     

基于R-树的连续最近邻查询算法优化研究

连续最近邻查询是空间数据库中一类重要的查询,在解决这个问题的已有方法中,最有效的是基于R-树的一次遍历算法,但这个算法中没有对R树的遍历顺序进行优化,没能最大程度地删剪结点,就磁盘存取而言是低效率的.对这个算法进行了改进,通过优化遍历顺序减少了磁盘存取数量,提高了I/O效率.     

LBS中面向协同位置隐私保护的群组最近邻查询

在分析现有群组最近邻查询中位置隐私保护的基础上,提出LBS中一种面向位置隐私保护的群组最近邻查询方法。该方法采用分布式系统结构,克服了集中式匿名系统结构所存在通信瓶颈和攻击重点的缺陷。在此基础上根据用户群组的运动状态信息,提出使用位置随机扰动和门限秘密共享的Paillier密码系统来安全地计算用户群组的质心位置。于是将用户群组的最近邻查询转换为此质心的最近邻查询。与现有的相关工作相比,理论分析表明所提有关方案能够在有效抵御现有的距离交叉攻击和共谋攻击下,实现灵活的群组最近邻查询,同时耗费较低的网络资源。     

高维数据空间索引的研究

讨论了高维数据空间索引的基本结构,建树算法以及典型的查询方式,重点对几种有代表性的索引方法,如K－D－Tree,R-Tree,R-Tree,X-Tree,TV-Tree,Hillert R-Tree在节点形状,重叠,插入原则,分裂原则,再插入等方面进行了比较研究。     

基于动态路网的分布式邻近目标查询算法

提出了一种基于实时路况信息的分布式邻近目标查询算法,采用基于Voronoi图的划分将地理信息存储在离它最近路口的智能摄像头上,实时路况信息由智能摄像头采集,通过对路口的畅通程度进行建模,估算出路口间通行所需要的时间。当有车辆查询邻近目标时,网络中的智能摄像头根据所在路口的畅通程度和到邻近路口的距离,在分布式查询过程中加入延时转发机制,广播目标路径询问的数据分组,使数据分组的发送能模拟当前的路况进行传输,从而获得到达邻近目标的路径。基于真实数据的实验结果表明算法是有效的,处理大量并发查询时的性能优于现有方法。     

不确定数据查询处理

 数据的不确定性在现实世界中的经济、军事、物流、金融、电信等领域普遍存在.不确定数据广泛应用于环境维护、市场分析、基于位置的服务LBS以及数量经济研究等应用.由于这些应用的重要性以及收集和累积的不确定数据数量的快速增长,查询这些数据已经成为一个重要的任务,并日益受到广大数据库研究者的关注.本文介绍了不确定数据查询的基本原理,并对不确定数据的近邻查询、逆向近邻查询、排序查询、Top-k查询以及连接查询进行了详细的讨论.同时对这些技术的优缺点进行了分析、对比.最后给出了未来的研究方向.     

近邻法参考样本集的最优选择

为克服近邻分类法需要大量计算和存储的缺点,本文利用Tabu搜索来求解满足一定错误率条件的最小参考样本集.当错误率阈值设为0时,可以得到原训练集的一致子集.当错误率阈值设为适当的非零值时,可以较好地克服近邻估计的偏置.通过在Tabu搜索中引入适当的激活(aspiration)条件,避免了在可行和不可行解区间无意义的来回搜索,加快了收敛的速度.实验结果表明,本文算法在压缩比和分类性能上都优于经典的算法.本文还证明了Dasarathy的算法^[6]得到的最小一致子集(Minimal Consistent Set: MCS)不是最小的,其MCS也不一定是单调减的.     

基于监督的距离度量学习方法研究

很多机器学习算法（比如K近邻算法）,学习的效果非常依赖于输入数据的距离度量,距离度量学习的主要目标是通过训练样本学习出一个能够更有效反映样本空间的距离函数,在此距离函数下,同类样本具有较近的距离,异类样本具有较远的距离。对近年来基于监督的距离度量学习方法的基本思想和算法进行了研究,并对当前距离度量学习的热点进行了介绍。     

一种改进的双线性插值图像放大算法

针对传统的双线性插值图像放大算法存在的边缘模糊问题,提出一种改进算法：先计算插值点的双线性插值和最近邻点插值,然后以4个邻点的灰度方差构造权重,将二种插值进行加权融合获得最终插值结果。该算法既考虑到插值点与邻点之间距离关系,又考虑到邻点的灰度分布特性,有效地提高了放大图像的质量。实验结果验证了算法的有效性。     

高维空间下基于密度的离群点探测算法实现

离群点是数据仓库中表现行为异常的数据。对高维空间下离群点的性质进行了研究,采用高维空间数据在低维空间投影再进行探测的策略,解决了高维空间数据稀疏难以用数据点距离判断离群的问题。算法实现中选取彼此关联紧密的维,数据点之间的距离采用最近邻定义,用基于密度的离群点探测方法,能在局部空间内更有效地探测到离群点。     

基于网格搜索的改进SVM模拟电路故障诊断方法

针对模拟电路故障识别与诊断问题,提出了一种基于K最近邻的一对一SVM分类器(KNN-OSVM)的故障诊断方法。将K最近邻算法与用网格搜索法优化后的一对一SVM模型相结合,建立KNN-OSVM模型,有效解决了SVM因存在不可分域造成的误分问题,提高了故障诊断率。采用小波分析法提取输出端电压信号作为故障特征值,采用网格搜索对核函数、惩罚参数寻优。采用两个模拟电路进行仿真实验,并将改进的SVM与传统SVM进行对比。结果证明了该故障诊断方法的可行性。