LSH 局部敏感哈希( 三 ) _局部敏感哈希

P1：如果存在一个点至少存在一个满足
P2： q通过哈希到的块中仅包含以外的点的块数小于cl 。
定理则P1,P2可以保证至少的概率。其中
总结:
以上便是LSH的基本理论, 我总结一下。对于LSH算的主要流程分为两个部分，一个是建立哈希结构，另一个便是检索。在知道具体度量方式的情况下，利用该度量下的LSH哈希函数，建立哈希结构。首先选取合适的k ， l参数，然后建立 l张哈希表，每张哈希表用k个独立抽取的基本哈希函数联合判断，建立哈希表的内部结构。哈希值相同的点放在一起，哈希值不同的放在不同的地方。至于查询，当q成为我们的查询点, 首先计算q在每张哈希表的哈希值，取出对应哈希值的哈希桶内所有点，与q做距离计算。找到满足我们条件的点作为查询结果。
六、局部敏感哈希规整说到Hash ，大家都很熟悉，是一种典型的Key-Value结构，最常见的算法莫过于MD5 。其设计思想是使Key集合中的任意关键字能够尽可能均匀的变换到Value空间中，不同的Key对应不同的Value ，即使Key值只有轻微变化， Value值也会发生很大地变化。这样特性可以作为文件的唯一标识，在做下载校验时我们就使用了这个特性。但是有没有这样一种Hash呢？他能够使相似Key值计算出的Value值相同或在某种度量下相近呢？甚至得到的Value值能够保留原始文件的信息，这样相同或相近的文件能够以Hash的方式被快速检索出来，或用作快速的相似性比对。位置敏感哈希（Local Sensitive Hashing, LSH）正好满足了这种需求，在大规模数据处理中应用非常广泛，例如已下场景：

近似检测（Near-duplicate detection）：通常运用在网页去重方面。在搜索中往往会遇到内容相似的重复页面，它们中大多是由于网站之间转载造成的。可以对页面计算LSH ，通过查找相等或相近的LSH值找到Near-duplicate 。
图像、音频检索：通常图像、音频文件都比较大，并且比较起来相对麻烦，我们可以事先对其计算LSH ，用作信息指纹，这样可以给定一个文件的LSH值，快速找到与其相等或相近的图像和文件。
聚类：将LSH值作为样本特征，将相同或相近的LSH值的样本合并在一起作为一个类别。

LSH(Location Sensitive Hash),即位置敏感哈希函数。与一般哈希函数不同的是位置敏感性，也就是散列前的相似点经过哈希之后，也能够在一定程度上相似，并且具有一定的概率保证。LSH的形式化定义可参见前面部分。
如下图，空间上的点经位置敏感哈希函数散列之后，对于q ，其rNN有可能散列到同一个桶（如第一个桶）,即散列到第一个桶的概率较大，会大于某一个概率阈值p1;而其(1+emxilong)rNN之外的对象则不太可能散列到第一个桶，即散列到第一个桶的概率很小，会小于某个阈值p2.

文章插图

LSH的作用:
◆高维下近似查询相似性检索在各种领域特别是在视频、音频、图像、文本等含有丰富特征信息领域中的应用变得越来越重要。丰富的特征信息一般用高维向量表示，由此相似性检索一般通过K近邻或近似近邻查询来实现。一个理想的相似性检索一般需要满足以下四个条件[4]：

高准确性。即返回的结果和线性查找的结果接近。
空间复杂度低。即占用内存空间少。理想状态下，空间复杂度随数据集呈线性增长，但不会远大于数据集的大小。
时间复杂度低。检索的时间复杂度最好为O（1）或O（logN) 。
支持高维度。能够较灵活地支持高维数据的检索。

此外, 检索模式应能快速地构造索引数据结构, 并且可以完成插入、删除等操作。
传统主要方法是基于空间划分的算法——tree类似算法，如R-tree ， Kd-tree ， SR-tree 。这种算法返回的结果是精确的，但是这种算法在高维数据集上的时间效率并不高。实验[5]指出维度高于10之后，基于空间划分的算法时间复杂度反而不如线性查找。LSH方法能够在保证一定程度上的准确性的前提下，时间和空间复杂度得到降低，并且能够很好地支持高维数据的检索。