近似最近邻大数据检索哈希散列方法综述

近似最近邻检索已成为人工智能时代海量数据快速检索主要技术之一。作为高效的近似最近邻检索方法,哈希散列方法受到广泛关注并且层出不穷。到目前为止还没有文献对主流哈希散列方法进行全面地分析和总结。鉴于此,本文首先系统地介绍哈希散列的基本知识,包括距离计算、损失函数、离散约束和外样本计算等。然后,深入对比分析主流哈希散列算法优缺点,并在主流数据库上进行性能评估。最后,总结哈希散列技术目前存在的问题,并提出若干潜在的哈希散列研究方向。本文对设计高效的哈希散列方法具有重要借鉴意义。     

近似最小树的哈希Dijkstra算法

为了解决Dijkstra(DK)算法对大规模数据构造最小树时效率不高的问题,结合局部敏感哈希映射(LSH),针对欧氏空间中的样本,提出了一种近似最小树的快速生成算法,即LSHDK算法.该算法通过减少查找近邻点的计算量提高运行速度.计算实验结果表明,当数据规模大于50 000个点时,LSHDK算法比DK算法速度更快且所计算的近似最小树在维数较低时误差非常小(0.00~0.05%),在维数较高时误差通常为0.1%~3.0%.     

基于最近邻优先的高效聚类算法

针对高维空间中任意形状的多层次聚类问题，基于“同类相近”的思想，提出并实现了最近邻优先吸收聚类算法NNAF算法。证明了最近邻点搜索定理，基于这一定理又提出了SNN(Searching Nearest Neighbors)算法和GSNN(Grid-based Searching Nearest Neighbors)算法，其时间复杂度为O(n*log(n))，当用扫描图像所得数据时，时间复杂度会降为O(n)；而使用传统的搜索算法，时间复杂度为O(n^2)；提出了实现任意形状高维空间聚类的NNAF算法，时间复杂度为O(n)；提出了MLCA(Multi-layer Cluster Algorithm)算法并证明了两个相关的定理，在改变阈值后重新聚类时，使用MLCA算法可以节省90％以上的时间。实验结果显示，以上算法适应于任意形状的高维空间数据的聚类，可以有效过滤噪声数据，且用户需要的先验知识少、可快速获得各种层次的聚类结果。     

位置隐私保护下的连续最近邻查询

已有的位置隐私保护下的连续最近邻查询往往采用snapshot方式进行,导致较高的中央处理器开销.为此,研究了基于位置隐私的连续最近邻查询,提出了基于重用技术的位置隐私保护的连续最近邻查询算法.该算法利用相邻时刻查询结果集的相似性来减少计算成本,从而实现答案集的快速更新,可大大加快系统响应时间.实验结果表明了该算法的有效性.     

一种基于最近邻优先的知识聚类算法

基于“同类相近”的思想,构建了一种改进的最短距离聚类算法——最近邻优先聚类算法NNPC．该算法可以快速获得不同层次的高质量聚类,进而找到满足要求的闽值参数和聚类,并能够高效处理以任意形状分布的具有噪声数据的大数据量高维数据,且用户需要的先验知识少．通过3个定理的提出和证明,体现算法的先进性．     

基于Fuzzy ART的K-最近邻分类改进算法

提出了一种K-最近邻改进算法,该算法用模糊自适应共振理论(Fuzzy ART)对K-最近邻的训练样本集进行浓缩,以改善K一最近邻的计算速度．该算法首先用Fuzzy ART将训练样本集中的每一类样本进行聚类,减小了训练样本集的数据量,提高了算法的计算速度,保持了预测精度,从而使该算法适用于海量数据集的情况．实验表明,该算法适用于对复杂而数据量较大的数据库进行分类．     

RPA：一种内存高效的度量空间recall@R近似最近邻搜索索引（英文）

现有的度量空间的近似最近邻搜索（approximate nearest neighbor search, ANNS）方法通常依赖于预选择的支撑点构成的序列,序列中的支撑点按照到数据元素的距离升序排列．然而,大多数现有的度量空间ANNS方法由于索引结构复杂、支撑点过多或者未能充分利用距离信息导致搜索时内存开销巨大．为此,提出精简排列阵（reduced permutation array, RPA）的度量空间recall@R近似最近邻搜索方法．对于全体数据元素,RPA预先选择k个支撑点,对每个数据元素仅存储离该数据元素最近的l个（l?k）,并将所有元素的支撑点序列构建为一个数组结构．在搜索过程中,利用一种得分函数,该函数基于查询对象到各个支撑点的距离来近似计算数据元素到查询对象的距离．同时,维护一个有界最小堆,以保存R个候选结果数据元素．RPA具有结构简单、内存效率高和可扩展性强等特点．实验结果表明,在相同召回率的情况下,与排列索引（permutation-based index, P-index）相比,RPA平均具有高达3倍的内存压缩比．研究结果可在内存资源有限的单机环境下提供一种有效的...     

基于改进最近邻聚类的机械手神经网络逆控制

机械手具有非线性时变、多变量、强耦合的特性,在机械手系统可逆的基础上,设计一种机械手的神经网络逆控制方案。通过神经网络逆辨识建立机械手的神经网络逆模型,把神经网络逆模型作为控制器模型与原机械手串联,构成一个伪线性动态模型,把非线性问题转化为线性问题。其中,辨识器和控制器均采用RBF神经网络结构,网络学习采用具有在线学习功能的最近邻聚类学习算法。仿真结果验证了本方案的有效性和可行性。     

一种用于图像匹配的快速有效的二分哈希搜索算法

文章针对高维图像特征的匹配问题,提出一种新的二分哈希搜索算法(Dichotomy BasedHash,DBH)。对具有大尺度旋转、缩放、视点和噪声变化的图像进行匹配,结果表明DBH可以较大提高最近邻搜索精度和查全率-查错率性能,从而获得较好的图像粗匹配结果。该算法搜索性能优于BBF(Best Bin First)算法,同时也比高维Hash搜索算法LSH(Local Sensitive Hash)更快更精确。     

障碍空间中不确定对象的组k最近邻查询方法

针对障碍空间中不确定对象的组k最近邻查询问题,提出了Pk OGNN(probabilistic k obstructed group nearest neighbor query)查询方法。Pk OGNN查询方法主要包括4个子算法:Compadist_o(),SpatialPru(),PruInterEnt()和PkOGNN(),这些子算法分别是集总障碍距离的计算方法、空间修剪方法、根据空间修剪方法进行R树中间结点修剪、最终精炼查询方法。所提Pk OGNN查询方法通过集成有效的修剪策略以便减少Pk OGNN的搜索空间,得到正确的k GNNs。理论研究和实验结果表明,所提方法具有较好的性能。