simhash算法_Mapreduce原理

simhash算法_Mapreduce原理一、LSH介绍    LSH(Localitysensitivehashing)是局部敏感性hashing,它与传统的hash是不同的。传统hash的目的是希望得到O(1)的查找性能,将原始数据映射到相应的桶内。    LSH的基本思想是将空间中原始数据相邻的2个数据点通过映射或者投影变换后,这两个数据点在新的空间中的相邻概率很大,不相邻的点映射到同一个桶的概率小。我们可以看到将一个在超大

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

一、LSH 介绍

    LSH(Locality sensitive hashing)是局部敏感性hashing,它与传统的hash是不同的。传统hash的目的是希望得到O(1)的查找性能,将原始数据映射到相应的桶内。
    LSH的基本思想是将空间中原始数据相邻的2个数据点通过映射或者投影变换后,这两个数据点在新的空间中的相邻概率很大,不相邻的点映射到同一个桶的概率小。我们可以看到将一个在超大集合内查找相邻元素的问题转化为了在一个很小的集合内查找相邻元素的问题,显然计算量下降了很多。下面借用一幅图来表示:

这里写图片描述

LSH满足如下条件:
ifd(x,y)d1,thenP(h(x)=h(y))P1
ifd(x,y)d2,thenP(h(x)=h(y))P2
•其中d(x,y)表示x和y之间的距离,d1 < d2,h(x)和h(y)分别表示对x和y进行hash变换。
•满足以上两个条件的hash functions称为(d1,d2,p1,p2)-sensitive。而通过一个或多个(d1,d2,p1,p2)-sensitive的hash function对原始数据集合进行hashing生成一个或多个hash table的过程称为Locality-sensitive Hashing.

二、Simhash 算法

    SimHash 算法的输入是一个向量,输出是一个 f 位的签名值。设输入的是一个文档的特征集合,每个特征有一定的权重。
Simhash 算法如下:

  1. 将一个

    f
    维向量 v⃗  初始化为 0⃗  , f 位的二进制数

    S
    初始化为0

    • 对每一个特征:
      用传统的hash算法对该特征产生一个 f 位的签名

      b
      .
      对于 i=1tof:
      如果 b 的第

      i
      位为1,则 v⃗  S 加上该特征的权重



      否则, v⃗  的第 i 个元素减去该特征的权重
    • 如果

      v⃗ 
      的第 i 个元素大于0,

      S
      的第 i 位为1,否则为0
    • 输出

      S
      作为签名
    • 如下图所示:
      这里写图片描述

      SimHash是由随机超平面hash算法演变而来的,对于一个 n 维向量

      v⃗ 
      , 要得到一个f位的签名( f<<n ),算法如下:

      1.随机产生 f

      n
      维的向量 r⃗ 1,r⃗ 2,,r⃗ f
      2.对每一个向量 r⃗ i ,如果 v⃗  r⃗ i 的点积大于 0 ,则最终签名的第

      i
      位为 1 ,否则为

      0

          上述算法相当于随机产生了f个n维超平面,每个超平面将v所在的空间一分为二。v在这个超平面上方则得到一个1,否则得到一个0,然后将得到的f个0或1组合起来成为一个f维的签名。

          如果两个向量 u⃗ ,v⃗  的夹角为 θ ,则一个随机超平面将它们分开的概率为 θπ ,因此 u⃗ ,v⃗  的签名的对应位不同的概率等于 θπ ,所以,我们可以用两个向量的签名的不同的对应位的数量,即汉明距离,来衡量这两个向量的差异程度。

          在simhash中并没有直接产生用于分割空间的随机向量,而是间接产生的:第k个特征的hash签名的第i位拿出来,如果为0,则改为-1,如果为1则不变,作为第i个随机向量的第k维。由于hash签名是f位的,因此这样能产生f个随机向量,对应f个随机超平面。

          simhash算法得到的两个签名的汉明距离可以用来衡量原始向量的夹角。这其实是一种降维技术,将高维的向量用较低维度的签名来表征。衡量两个内容相似度,需要计算汉明距离。汉明距离是两个字符串对应位置的不同字符的个数:
      1011101 与1001001 之间的汉明距离是2。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/187342.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • 说说 jBPM 工作流引擎的设计原理

    说说 jBPM 工作流引擎的设计原理1服务API设计jBPM4工作流引擎的核心PVM主要依靠4组服务API:流程定义服务-ProcessService。流程执行服务-ExecutionService。流程管理服务-ManagermentService。指令服务-CommandService。应用通过这些服务与PVM进行数据交互,这些都是在支持事务的持久化模式下运…

  • 使用CSS画一个三角形

    使用CSS画一个三角形使用CSS画一个三角形

  • PE盘装系统时无法找到ISO文件

    PE盘装系统时无法找到ISO文件用PE盘装系统时,在选择包含Windows安装文件的文件夹时,找不到ISO系统镜像映像,如图所示此时在‘选择包含Windows安装文件的文件夹’选项时,不能鼠标左击,需要右击。。。…

  • 手眼标定之基本原理

    手眼标定之基本原理文章目录一前言二Eye-in-Hand2.1基础知识准备2.2Eye-in-Hand基本原理三跋原文首发于微信公众号【视觉IMAX】。一前言机器人的视觉系统分为固定场景视觉系统和运动的「手-眼」视觉系统。摄像机与机器人的手部末端,构成手眼视觉系统。根据摄像机与机器人相互位置的不同,手眼视觉系统分为Eye-in-Hand系统和Eye-to-Hand系统。Eye-in-Hand…

  • 【Linux + Makefile】十分钟教你学会Makefile的FORCE「建议收藏」

    【Linux + Makefile】十分钟教你学会Makefile的FORCE「建议收藏」Makefile有种FORCE的写法,你了解过它的原理和用途吗?

  • 基于IP路由的GSLB《CDN技术详解》

    基于IP路由的GSLB《CDN技术详解》基于IP路由的GSLB是基于路由器原有的路由算法和数据包转发能力工作的。如图所示,有两个本地均衡器1和2,放在不同的POP点中,负责各自POP点内的服务器的负载均衡。先为这两个本地均衡器配置一个相同的VIP地址,对IP网上的路由器来说,这是到同一个IP地址的两条不同的路由。1)当终端a输入URL访问网站时,DNS系统会把VIP作为域名解析结果反馈给终端。2)终端向这个VIP发送请求时,请求数…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号