增强LSH

简介:   通过LSH hash functions我们能够得到一个或多个hash table,每个桶内的数据之间是近邻的可能性很大。我们希望原本相邻的数据经过LSH hash后,都能够落入到相同的桶内,而不相邻的数据经过LSH hash后,都能够落入到不同的桶中。

  通过LSH hash functions我们能够得到一个或多个hash table,每个桶内的数据之间是近邻的可能性很大。我们希望原本相邻的数据经过LSH hash后,都能够落入到相同的桶内,而不相邻的数据经过LSH hash后,都能够落入到不同的桶中。如果相邻的数据被投影到了不同的桶内,我们称为false negtive;如果不相邻的数据被投影到了相同的桶内,我们称为false positive。因此,我们在使用LSH中,我们希望能够尽量降低false negtive rate和false positive rate。

   通常,为了能够增强LSH,即使得false negtive rate和/或false positive rate降低,我们有两个途径来实现:1)在一个hash table内使用更多的LSH hash function;2)建立多个hash table。
  下面介绍一些常用的增强LSH的方法:
  1. 使用多个独立的hash table

  每个hash table由k个LSH hash function创建,每次选用k个LSH hash function(同属于一个LSH function family)就得到了一个hash table,重复多次,即可创建多个hash table。多个hash table的好处在于能够降低false positive rate。
  2. AND 与操作

  从同一个LSH function family中挑选出k个LSH function,H(X) = H(Y)有且仅当这k个Hi(X) = Hi(Y)都满足。也就是说只有当两个数据的这k个hash值都对应相同时,才会被投影到相同的桶内,只要有一个不满足就不会被投影到同一个桶内。
  AND与操作能够使得找到近邻数据的p1概率保持高概率的同时降低p2概率,即降低了falsenegtiverate。

  3. OR 或操作
  从同一个LSH function family中挑选出k个LSH function,H(X) = H(Y)有且仅当存在一个以上的Hi(X) = Hi(Y)。也就是说只要两个数据的这k个hash值中有一对以上相同时,就会被投影到相同的桶内,只有当这k个hash值都不相同时才不被投影到同一个桶内。

  OR或操作能够使得找到近邻数据的p1概率变的更大(越接近1)的同时保持p2概率较小,即降低了false positive rate。
  4. AND和OR的级联

  将与操作和或操作级联在一起,产生更多的hahs table,这样的好处在于能够使得p1更接近1,而p2更接近0。
  除了上面介绍的增强LSH的方法外,有时候我们希望将多个LSH hash function得到的hash值组合起来,在此基础上得到新的hash值,这样做的好处在于减少了存储hash table的空间。下面介绍一些常用方法:

  1. 求模运算

  new hash value = old hash value % N
  2. 随机投影

  假设通过k个LSH hash function得到了k个hash值:h1, h2..., hk。那么新的hash值采用如下公式求得:

new hash value = h1*r1 + h2*r2 + ... + hk*rk,其中r1, r2, ..., rk是一些随机数。
  3. XOR异或

  假设通过k个LSH hash function得到了k个hash值:h1, h2..., hk。那么新的hash值采用如下公式求得:new hash value = h1 XOR h2 XOR h3 ... XOR hk

目录
相关文章
|
3月前
|
机器学习/深度学习 存储 Python
数据增强
【7月更文挑战第29天】
51 15
|
3月前
|
存储 自然语言处理 开发者
通用性与灵活性对大模型的影响
通用性与灵活性对大模型的影响
|
4月前
|
jenkins 测试技术 持续交付
利用C++增强框架的可测试性(Testability)
**C++框架可测试性提升策略**:通过模块化设计、依赖注入、使用Mock对象和Stub、编写清晰接口及文档、断言与异常处理、分离测试代码与生产代码、自动化测试,可以有效增强C++框架的可测试性。这些方法有助于确保代码正确性、健壮性,提高可维护性和可扩展性。示例包括使用类和接口实现模块化,通过构造函数进行依赖注入,以及利用Google Test和Google Mock进行断言和模拟测试。
72 1
|
4月前
|
编解码 算法 计算机视觉
YOLOv8数据增强预处理方式详解:包括数据增强的作用,数据增强方式与方法
YOLOv8数据增强预处理方式详解:包括数据增强的作用,数据增强方式与方法
|
5月前
|
机器学习/深度学习 算法 定位技术
医学图像增强系统的设计_kaic
医学图像增强系统的设计_kaic
|
11月前
|
机器学习/深度学习 算法框架/工具 Python
pyton数据增强
pyton数据增强
75 0
|
人工智能 程序员 C#
通过简单原理增强软件可靠性
通过简单原理增强软件可靠性
|
机器学习/深度学习 人工智能 算法
数据增强方法汇总
数据增强方法汇总
245 0
|
机器学习/深度学习 存储 计算机视觉
【目标检测】常用数据增强从原理到实现
【目标检测】常用数据增强从原理到实现
283 0
|
机器学习/深度学习 算法 测试技术
使用用测试时数据增强(TTA)提高预测结果(上)
使用用测试时数据增强(TTA)提高预测结果
509 0