【作者】 王振；

【导师】 赵宏伟；

【作者基本信息】 吉林大学 ， 计算机应用技术， 2017， 博士

【摘要】 近邻检索技术旨在返回与查询样本较相似的数据点,其在机器学习和计算机视觉领域中有着广泛的应用。近年来,随着网络技术的快速发展和多媒体设备的迅速普及,我们已经步入了多媒体大数据时代,并且多媒体特征一般为高维浮点型向量。因此,实时响应海量高维浮点向量的近邻检索请求,已经成为当前学术界和商业界的热点问题。哈希算法可将高维浮点型向量表示成紧凑二进制编码,并根据汉明距离关系查询近邻点。二进制编码所占用的存储空间较少,并且汉明距离的计算复杂度较低。因此,在海量数据库中,可采用基于二值编码的近邻检索算法快速得到近邻样本。然而,有限长度的二进制编码的区分性较弱,并且一些哈希算法自身也存在一些问题,使得在汉明空间内得到的近邻检索结果与原空间内的近邻检索结果之间存在偏差,而且这些问题还没有得到很好的解决。本论文从基于二值编码的近邻检索的不同阶段,探索提升近邻检索性能的方案,并力求两个空间内的检索结果之间具有较高的一致性。近邻检索一般包含初始检索阶段和后验证两个过程。在初始检索阶段中,决定近邻检索结果的主要因素是数据集的二进制编码,其与相似性保持目标函数以及算法的收敛情况相关。在后验证阶段中,近邻检索性能的提升幅度取决于距离表的区分性。本文以上述研究方向为切入点,探索如何快速获取具有较优近邻检索性能的二进制编码,以及如何在后验证阶段中进一步提升近邻检索性能。本文中的主要研究内容和创新成果如下:1.提出了归一化距离相似性保持哈希算法,通过最小化数据点对在两种不同空间内的归一化距离差别来保证数据点对在不同空间内拥有相近的相似度。为了能够通过比较数据点对在不同空间内的距离值来判断它们是否具有相同的相似度,本文采用了归一化处理,使得数据点对在不同空间内拥有相同的距离取值范围,而且这一做法能够避免距离比例参数的引入。当训练数据集或目标编码长度发生变化时,无需人为交叉验证使得算法性能最优的距离比例参数,有效降低了算法的训练复杂度,算法性能相对稳定。算法的原目标函数中包含数据点的二值编码过程,其为离散型函数,直接优化该目标函数较困难。为此,本文采用S型符号函数松弛处理二值编码过程,使得目标函数连续化。当训练数据集为海量数据库时,本文采用随机批量梯度下降算法优化目标函数,使得算法能够快速收敛。2.提出了排序一致性哈希算法,在欧式空间和汉明空间内,分别根据数据点对的不同种类的距离值对其排序,并要求两种不同排序之间的区别最小,符合近邻检索的本质要求,属于相对相似性保持哈希算法。同时,还引入了量化误差,要求被映射为相同编码的数据点在原空间内互为近邻关系,从而保证所生成的二进制编码符合空间分布特性。在训练阶段中,学习同时满足上述两种约束条件的编码中心点时,本文分别探索利用分层编码机制和子空间划分方法降低训练时间复杂度。根据所生成的编码中心点,可采用基于查找的方式编码新数据点,但其编码时间复杂度较高,不适应于海量数据库。为此,本文构建了类似于两步机制的算法框架,监督学习线性哈希映射函数,使得编码时间复杂度从指数级降为线性级。本文中的强哈希映射函数是由自适应提升算法组合多个弱哈希函数形成的,能够最大程度地保留数据点之间的原始局部敏感信息。3.提出了适应空间分布的多重编码算法和距离表。哈希算法学习数据集的二进制编码时,常采用梯度下降算法优化目标函数。但梯度下降算法具有局部最优性,若目标编码长度有限,数据点在汉明空间内的区分性较弱。为了解决上述问题,本文提出自适应多重编码算法,根据数据集的空间分布和目标编码长度,采用经验学习算法,自适应生成一组或多组数据点作为初始输入,从而保证算法能够快速得到完备解。多重编码算法将数据点映射成多重二进制编码,并根据平均汉明距离返回初始近邻检索结果。在汉明空间内的近邻查询结果中存在许多与查询数据点共享相同汉明距离的数据点,但它们与查询数据点在原空间内的相似度是不同的。为了进一步区分拥有相同汉明距离的数据点对之间的相似度,本文建立了适应空间分布特性的距离表。一般距离表将拥有相同编码的数据点的坐标均值作为中心点,若编码长度有限,多个聚类数据集可能共享相同的中心点,使得中心点之间的距离值不能精确表达数据点之间的相似关系。本文根据数据集的空间密度分布,自适应学习符合聚类分布特性的中心点,并且中心点的数量与编码长度无关,也不同于K均值聚类算法,不需要人为确定聚类数量。本文将不同中心点之间的距离值,按照中心点的二值索引存入到不同的位置中,从而得到区分性较强的距离表。若编码长度较短,编码种类数将少于中心点数,将有多个中心点对共享相同的二值索引,它们之间的距离值会被存储在距离表中的相同位置。但是,多个中心点对拥有相同的多重索引的概率较小。在后验证阶段中,可根据数据点对的多重索引从距离表中得到多个距离集合,并通过计算它们之间的交集来确定最终距离值。在本文中,根据数据点之间的汉明距离得到初始检索结果之后,将根据适应空间分布特性的距离表,重新判断拥有相同汉明距离的数据点对之间的相对相似性,并对它们重新排序,从而进一步提升近邻检索性能。更多还原

【Abstract】 Approximate nearest neighbors(ANN)search,which aims at returning the data points with smaller distance values to the query samples,has been widely applied in the area of machine learning and computer vision.Due to the rapid development of the Internet technology and the widespread use of the multimedia equipment,the era of massive multimedia data has reached.Different from the text information,the features of the multimedia data are represented as high dimensional floating-point vectors.As a result,how to fast respond the ANN search of the massive high dimensional vectors has become a hot issue in the academia and business area.Hashing algorithms map the high dimensional floating-point vectors into the Hamming space,and represent them as compact binary codes.Thus,the approximate nearest neighbors are returned according to the similarity among their binary representations.As the memory occupancy rate and the Hamming distance computation complexity are relative lower,the ANN search of the massive high dimensional vectors can be fast done in the Hamming space.However,the binary codes’ weak discrimination and some hashing algorithms’ limitation would lead to worse ANN search performance,and these problems have not been well solved.In this paper,all stages of the ANN search framework have been studied,and the innovation measures are proposed to minimize the differences between the retrieval results in the Hamming space and those in the original space.The ANN search procedure often includes the initial retrieval stage and the post-verification step.The initial ANN search results are mainly determined by the quality of the binary codes which relate to the objective function and the convergence results.During the post-verification stage,whether the ANN search performance can be further improved lies on the distance table.The research points mentioned above are studied in this paper,and we mainly explore how to quickly obtain the excellent binary codes and the optimal distance table.The research contents and innovation points are shown as below:1.The normalized distance similarity preserving hashing is proposed.The bias between the data pairs’ different kinds of normalized distance values is tried to be minimized,which guarantees the data pairs’ similarity in the Hamming space is close to that in the Euclidean space.According to the definition of the objective function,the value range of the Hamming distance should be identical to that of the original distance.To fulfill the above goal,the normalization procedure is employed in this paper.As a result,no parameter is involved in the objective function.When the training database and the binary codes’ length changing,there is no need comparing and selecting the parameter which makes the ANN search performance best.Thus,the algorithm’s training complexity become relative lower,and the ANN search performances are more stable.The objective function is defined based on the discrete function of the binary encoding procedure,and it is diffcult to directly optimize such an objective function.In order to avoid the above situation,the Sigmoid function is adopted to relax the binary encoding procedure.For the massive database,the batch stochastic gradient descent algorithm,which can reduce the training time complexity,is employed to learn the hashing function.2.The ranking consistence hashing is proposed in this paper.Firstly,the data pairs are separately sorted according to their Hamming and Euclidean distance values.Then,the differences between the data pairs’ ranking orders in the two spaces are required to be minimized.Based on the above definition,the relative similarity among the data pairs which satisfies the requirements of the ANN search is preserved.Meanwhile,the quantization error,which demands the data points with the same binary code should be near neighbors,is employed to make the obtained binary codes distribution adaptive.During the training stage,the hierarchical mechanism and the sub-space method are separately utilized to reduce the training time complexity.On the basis of the learnt encoding centers,the out-of-samples can be encoded through lookup-based mechanism.However,the encoding time complexity is higher,and it is not capable for the massive database.To solve this problem,the framework similar to the two-step mechanism is constructed to supervise learning linear hashing functions.The final hashing functions are formed through combining many weak ones assisted by the adaboost mechanism,which can largely preserve the locality sensitive information.3.The gradient descent algorithm is employed to optimize the objective function in many hashing algorithms.However,it usually converges when the local optimum values are found.In order to solve the above problem,many groups of encoding centers are initialized according to the data distribution and the length of the binary bits.As a result,the algorithm converges in reason time and all minimial vaules are found.The data points are encoded as multiple binary codes and the initial retrieval results are returned according to the average Hamming distance.In the Hamming space,many data points share the same distance value with the query sample,but their similarity degrees are not identical in the original space.To avoid the situation mentioned above,the distribution adaptive distance table is established in this paper.Different from the commonly used distance table which considers the mean value of the data with the same binary code as centers,the values in our distance table represents the distances among different cluster centers.As a result,the discrimination ability is enhanced.Due to the finite length of the binary codes,many pairs of the cluster centers share the same binary index,and their distance values are stored in the same position of the distance table.During the post-verification stage,the data pair’s distance can be obtained through computing the intersection of the distance sets corresponding to the data pair’s multiple binary indexes.According to the obtained distance values,the ANN search performances can be further improved through re-sorting the initial retrieval results.更多还原