论文部分内容阅读
“大数据”时代给数据检索带来了新的挑战，相似性检索显得尤为重要。局部敏感哈希算法是相似性检索中最流行的一种，该算法是建立在哈希的基础上的一种近似最近邻算法，它能将检索时间复杂度缩减到线性。与其它基于Tree的数据结构相比，局部敏感哈希算法能较好的处理数据在高维空间中的检索问题。注意到高维数据利用该算法检索得到候选集后需要进行相似度计算，而这一部分所耗费时间的占整个数据检索时间的比重非常大，所以该算法在处理大规模数据时的性能仍然需要提高。 针对局部敏感哈希算法，考虑到数据维数和数据量的急剧增加而检索时间还不能满足需求情况下，提出了在不同场合下两种改进的局部敏感哈希算法并应用于图像，本文在局部敏感哈希算法的基础上做了以下工作: 1.对利用局部敏感哈希算法查找前k个最相似(Top-k)的问题，提出了一种基于次数排序的局部敏感哈希算法(ST-LSH)。该算法将唯一化前的索引号按出现次数进行排序来输出，避免了相似度计算花费大量时间的问题。实验结果显示，与改进前的算法相比，在保证识别率基本不变的情况下，改进后的算法大大减少了数据检索时间。 2.在利用局部敏感哈希算法进行数据类别的查找过程中，为了弥补容易受噪声点的影响，提出了一种基于k近邻分类(k-nearest neighbor)局部敏感哈希算法（KNN-LSH）。KNN-LSH充分利用了唯一化后的候选集的信息，利用候选集唯一化后的索引号所属的类别进行k近邻分类。即统计当前候选集所属类别的信息，将查询对象归为所属类别最多的那一类，从而避免了大量的相似度计算。实验结果证明，与改进前的算法相比，KNN-LSH对分类问题的识别率要好于传统方法，具有稳定性，同时也缩短了数据检索时间。