英语原文共 10 页，剩余内容已隐藏，支付完成后下载完整资料

重访局部敏感哈希算法：填补理论与算法分析的空白

王洪亚 东华大学计算机科学与技术学院，中国 上海

LihChyun Shu 台湾成功大学管理学院，中国 台湾

Davood Rafiei 艾伯塔大学计算机科学学院，加拿大 埃德蒙顿

摘要：高维空间中，局部敏感哈希算法（LSH）是公认的且最有前途的相似性搜索方法之一。以往提出的大量基于LSH的最近邻搜索算法已经被广泛用于现实生活的多种应用中。除了在实际应用中表现出的优异性能，LSH算法能够流行主要是由于它们可证明的性能优势：查询成本、空间消费和失效概率。在本文中，我们展示了LSH算法理论分析与实际应用技术分析之间存在的惊人的差距。尤其是，在经典的LSH算法分析中，我们发现了一个在实际生活中不能成立的关键假设，这表明利用现有的方法分析LSH算法的实际性能从概念上看就是不匹配的。为了解决这个问题，建立了一种新的分析模型，来弥补了LSH算法理论分析与实际应用之间的差距。在该模型的帮助下，我们识别出有关LSH算法的一些常用文献中的重要缺陷。并利用大量真实数据集的进行实验，实验结果证明了此模型的有效性。

引言

最近邻搜索在高维空间中的距离函数在某些领域中具有重要的意义，比如：数据库、信息检索、数据挖掘，模式识别与机器学习等。当数据的维度较低时，一些方法（如：R-tree[13]，kd-tree[6]）在实际应用中性能较好。然而，随着维度的增加（如：大于50），这些传统的基于树的索引方法在查询过程比线性扫描数据集中的每个点只有略微的优势[21]。这种现象通常被称为“维度灾难”。

为了克服搜索时间瓶颈，提出了许多提高速度精度的近似算法。在本文中，我们利用局部敏感哈希算法，该算法是最有前途的相似性搜索算法之一，已被广泛应用应用于各种领域，包括Web聚类，计算机视觉和计算生物学。

我们指出，LSH算法不能直接解决最近邻搜索，并提出了一个在高维空间中称为c-近似r-邻近搜索（详见2.2中定义1）的问题[16]。LSH算法的关键思想是，设计哈希函数尽可能使度量空间中临近的点发生碰撞的概率较大。如果哈希函数集H满足定义2中所列的条件，H就称为局部敏感。到目前为止，已发现好几种基于LSH的计算相似性的方法，比如海明距离[16]、LS距离[9]、Jaccard系数[7]、余弦距离[8]等。

当给定一个特定的度量和相应的LSH算法的哈希函数集时，就能很容易的设计出一个高效的最近邻搜索算法，稍后将详细讨论该点。简单地说，在预处理阶段，通过随机选择的独立的哈希函数H将数据集中所有的点映射到一系列哈希表或哈希桶中。当查询时，只需要哈希该查询点并检索哈希桶中是否已存在该点。

由于LSH算法的稳健性，那些基于LSH的算法才有能力提供一些常数失效概率，并在空间使用成本和查询成本方面拥有优越的渐进性能。Indyk and Motwani在他们经典的LSH算法中最早证明了上述理论结果。随后，在此基础上，后人进一步的研究了LSH算法，并提出了多种形式，比如：LSH-forest[5]、LSB-tree[20]、Multi-probe LSH[18]和C2LSH[11] ，以获得相应的理论保证。

出人意料的是，在实验过程中，我们观察到经典的LSH算法在实际效果与预期性能之间惊人的偏差。例如，一个典型的实验如图1所示，其中预期的成功率表示预期的性能，最高、最低及平均成功比率分别表示实际应用中最好的最坏的情况和平均性能。理论上，由于实际的成功比率包含最大成功率、最小成功率及平均成功率，应该能够符合预期的性能[3]，但是事实上，如图1 所示，最大值/最小值与预期的算法性能之间存在明显的差距，这些矛盾的结果将利用被广泛接受的分析方法做进一步的审查，详细介绍在2.3节中。

图1

显然，这样一个显着的差异不能简单地归结为实验中的“随机误差”。相反，因为这种性能差距揭示了一个多年来一直被忽略的微妙的问题，我们将在本文的其余部分严肃讨论。基于这样的观察，我们对LSH算法进行了系统而深入的研究，有以下几点发现：

• 我们观察到LSH算法分析中一个关键的假设，就是从实验角度看，不正确的分析方法可能会产生错误理论结果。
• 建立了一种新的模型，以弥补LSH算法预期的理论结果与实际应用结果之间的差距。基于此模型，我们在定理证明过程中发现了一个致命的缺陷，就是说，理论上，几乎所有的LSH算法实现性能的保障都是存疑的。特别是，部分有关LSH算法的文献中所证明的近似查询的常数概率。
• 我们还检查了经典LSH算法的参数选择，给出了由随机r-near邻近问题(文献[16]中的定义4)导致的失效概率，而由参数K和L影响的故障率却总是近乎相等。使用本文所提出的模型可以更精确的预测LSH算法的结果是最具有实际意义的发现。
• 为了验证我们的观点，利用了大量真实数据集的进行实验，而实验结果证明了此模型的有效性。同时，证明了当数据集的基数足够大时，现有的分析模型是准确且有效的。

本文的剩余部分组织结构如下所示。第2节简单概述LSH算法及其相关工作。第3节介绍了本文的主要理论成果。第4节为实验结果分析，以验证我们所提出的模型的有效性。第5节也就是最后一节，给出了研究结果的结论以及对未来的展望。

LSH算法简要概述及相关工作

最近邻搜索问题

根据一些距离度量，在高维空间中，局部敏感哈希算法与最近邻查找搜索密切相关。因此，在正式介绍LSH算法具体细节之前，我们首先根据最近邻搜索给出了一些必要的符号的定义。

我们使用O代表一组数据点，设数据集O内所有的点（ O ）都存在于d维空间R^d内。令表示数据集O中的第j类点，其中j = 1,2,hellip;,d。对于数据集O中任意两点o、q，它们之间的距离被定义为如下所示：

对于给定的数据集，它的邻近NN_q 中的查询点q在l_s规范下被定义为：

O （2）

为了简化符号，我们在下文中省略了下标s。

近邻搜索的目的是，当给定一个数据集和一个查询点时，能够找到一个有效的方法返回该查询点的邻近点。从本质上看，近邻搜索问题实际上是一个优化问题，因为它的目标是通过目标函数找到距离(上述情况中就是指与查询点之间的距离)最小的点。但是公认的是，当数据维度足够大（gt;d）时，近邻搜索的绝大多数解决方案几乎与线性扫描数据集中的每个点效率相当，无优势可言。这种现象通常被称为“维度灾难” [21]。

直接解决这个问题是非常困难的，Indyk等使用等球点位置[6]的方法解决了r邻近搜索问题。若点o和q之间的距离小于等于r，则称点o在查询点q的r邻近内。r邻近搜索 的目的就是展示查询点q r-邻近内的点。如图2所示，o1是q的邻近点，o1和o2都是q的r-邻近点。

r-邻近搜索算法仍然会出现“维度灾难”现象。幸运的是，在许多领域，最近邻搜索也是适用的。给定一个查询点q，若存在一个数据点满足，且c gt; 1，则称该点为查询点q在l_s规范下的最近邻搜索点，记为。我们以c-近似r-邻近命名以上的最近邻搜索方法，定义如下：

定义1：数据集O中的点都属于d-维空间中，c gt; 1，构造一个数据结构，对于给定的任意查询点q在数据集O都存在它的r-邻近点，而这样的范围称之为数据集O中的c-近似r-邻近域。

在图2中，由于点o1、o2与点q之间的距离小于r，很明显这两点均是点q的c-近似r-邻近点。相反，点o3落在c-近似r-邻近域外。

图2 第2节中所讨论概念和定义的实例

局部敏感哈希算法

局部敏感哈希是高维空间中最流行的最近邻查找算法之一。该算法的主要思想是：通过使用特定的哈希函数，使相邻近的点的发生碰撞的概率远大于不相邻的点。

在本文中，用H表示d-维空间内的哈希函数集。任意两点o和q ,随机从哈希函数集H中选择一个散列函数h，这两个点的碰撞概率都满足以下条件，那么就称H是局部敏感的。

定义2：（局部敏感哈希）如果哈希函数集H符合（r, cr, p₁, p₂）-sensitive，那么d-维空间的任意两点和函数集中的任意哈希函数h，都满足以下条件：

• 如果，则PrH
• 如果，则PrH

要是LSH族有效，则要保证。

给定一个LSH集H，LSH_C表示经典的LSH算法，工作流程如下：对于参数K和L，L作用是选择哈希桶 选择哈希桶，其中是从H随机选择的函数。数据集O中的每一个点o，通过（j = 1, hellip;, L）计算得到哈希桶号，然后将点o插入对应的哈希桶内。要处理查询点q，首先需要计算 （j = 1, hellip;, L），然后检索至少一个哈希桶内的所有点。对于所有待检索的点，筛选过程就是计算每个点与查询点之间的距离。基本上，有两种主要的过滤策略。

1. 在整数集中T找到第一个T时就停止搜索,返回离查询点距离最小的点。
2. 继续搜索直至所有的点都处理过，此时返回与查询点之间的距离小于r的点。

这两种策略，结合前面讨论的数据结构，就形成了不同的LSH_C。特别的是，第一种策略旨在解决随机的crNN搜索问题，定义如下：

定义3：数据集O中的点都属于d-维空间中，c gt; 1，，构造一个数据结构，对于任意查询点q，如果数据集O存在q的r-邻近点，那么返回数据集O中部分点q的c-近似r-邻近点的概率为。

不同于它确定性部分，crNN随机搜索的解决方案可能会出现假阳性。如图2所示，尽管点o4落在最外层的圆外，它仍有机会被识别点q的crNN点。

策略1在理论上是非常有意义的，若参数K和L选择正确，它本身的查询效果和空间性能 就非常好。但是，和策略2相比，策略1 的质量不可观，所以在实际应用中很少使用。

策略2能够解决r-邻近随机搜索问题，定义如下：

定义4：数据集O中的点都属于d-维空间中，c gt; 1，，构造一个数据结构，对于任意查询点q，如果数据集O存在q的r-邻近点，那么返回数据集O中所有点q的r-邻近点的概率为。

上述定义的问题能够返回查询点q的所有rNNs点，只是r-邻近搜索问题随机版的一个特殊例子。因为查询点的所有rNNS点都在结果集中，所有策略2拥有较好的结果质量且不会出现假阳性。然而，如果没有与查询点发生碰撞，仍可能出现伪阴性。如图2所示，尽管点o1和o2 都是q的r-邻近点，但是通过策略2计算，只会返回点o2。

相比于返回查询点的所有r-邻近点，策略2的实际执行过程会依照与查询点之间的距离将所有r-邻近点按照升序排列，并返回排序表中离查询点最近的点。和策略1相比，策略2以及它的排序过程能够提供更有质量的结果。但是，需要付出更多的查询时间以及缺乏足够的理论证明。

经典LSH算法的理论性能

基于LSH的算法最有吸引力的部分就是，无论从理论上还是实践上看，通过设置参数K和L的值，都能够使算法的查询时间远小于其他算法。接下来，在策略1和策略2的基础上，针对经典的LSH算法，我们提出了一些更重要的理论结果。

在策略1中，如果我们令，（），然后对于随机crNN搜索问题，主要又查询时间O（）和距离计算时间O（）决定，且常数失效率。

在策略2中,失效概率和查询时间很大程度取决于参数K和L。不同于策略1 ，它的查询时间不存在理论证明，最坏的情况下可能高达O（n）。但数据集很大而参数选择不正确时，就会发生这样的情况。幸运的是，对于绝大数的真实数据集，只要谨慎选择K和L的值，它的查询时间几乎是线性的。

策略2常用的参数选择方法如下所示。设点o是查询点q的r-邻近点，且参数K取任意值。对于函数g_j，g_j(o) = g_j (q)的概率至少为。因此，当j = 1, 2, hellip;, L,时，g_j(o) = g_j (q)的概率至少为。结果，通过策略2 返回q的任意r-邻近点的概率至少为。如何选择参数K不在本文的考虑范围中，有兴趣的读者可以自行阅读其他文献。

重访局部敏感哈希

准备工作

在本文的其余部分，我们使用了一个稍微不同的局部敏感哈希的描述来达到我们的目的，定义如下：

定义5：如果d维空间中的任意两点o,q满足式(3)，则哈希集H就称为敏感哈希。

PrH fH（r） （3）

式中r是q与o之间的距离，f_H(r)是一个关于r的单调递减函数。

请注意，虽然用一个不同的形式表示，定义5在本质上相当于[16]中给出的原始定义。事实上，我们的定义与[8]中用到的LSH定义非常相似，该定义重点研究了Jaccard和余弦相似性度量法。

用最近邻空间搜索在一些ls规范下的一个d维空间，f_H(r)解析表达式中的s已经被发现属于[0,2]。两个具体实例（s=1,2）将马上在3.2节与4.1节分别讨论。 剩余内容已隐藏，支付完成后下载完整资料

资料编号：[30398]，资料为PDF文档或Word文档，PDF文档可免费转换为Word