LSH-局部敏感哈希
2024-09-30 04:17:45
LSH的基本思想是：
将原始数据空间中的两个邻近数据点通过某种映射或变换，使得这两个数据点在变换后的数据空间中仍然相邻的概率很大，而不相邻的数据点被映射到同一个桶的概率很小。
因此，最最重要的就变成了就是找到一个这样的映射或变换，也就是所谓的hash function。有没有觉得如果找到一簇这样的函数，一下子天空都变蓝了。
那么hash function应该怎样用数学语言来描述呢？
对于任意q,p属于S，若从集合S到U的函数族H={h1,h2…hn}对距离函数D(q,p)，如欧式距离、曼哈顿距离等等，满足条件
$D(p,q){\leq}r$且$Pro[h(p)=h(q)]{\geq}p_{1}$
$D(p,q)>r(1+{\varepsilon})$且$Pro[h(p)=h(q)]{\leq}p_{2}$
则称为D(p,q)是位置敏感的。
这两个公式就是开头的一句话的数学模型而已。
这里说明一下，LSH不是确定性的，而是概率性的，也就是说有一定的概率可能将两个距离很远的映射到一个捅中，将距离很近的映射到不同的捅中。这是在进行降维的时候带来的不可避免的缺陷。
不同的距离函数需要使用不同的LSH算法，目前不存在一种统一的LSH算法。
最新文章
- Java进击C#——语法之多线程
- iOS事件传递->处理->响应
- ibatis 轻松入门
- python gevent 协程
- SPFA+寻路（行路难，洛谷2832）
- response.setContentType设置
- server.transfer 用法
- jenkins2 pipeline高级
- hihoCoder#1015 : KMP算法 （KMP模板）
- jQuery - 实时统计输入框输入个数（中文输入法适用）
- 汇编debug 截图
- AndroidStudio KeyMap
- DataSet数据导出为Excel文档（每个DataTable为一个Sheet）
- Qt读写二进制文件
- IGT一道笔试题
- Power Strings
- 201521123001《Java程序设计》第8周学习总结
- Holer实现外网访问ARM嵌入式Linux系统
- day 06云计算的三种服务模式：IaaS，PaaS和SaaS
- c/c++ 中的重要函数