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)


相关推荐

  • springmvc源码下载_idea jar包导入

    springmvc源码下载_idea jar包导入1.首先需要下载源码码云地址:https://gitee.com/mirrors/Spring-Framework.git很快推荐GitHub地址:https://github.com/spring-projects/spring-framework.git不推荐然后打开idea,下载源码2.下载并配置gradle环境下载地址:https://services…

  • vs2005注册_vs注册界面设计

    vs2005注册_vs注册界面设计注册码:KYTYH-TQKW6-VWPBQ-DKC8F-HWC4J找到SETUP文件夹下的setup.sdb,用记事本打开它,找到[ProductKey],将下面的一行序列号删除,改为正式Key,保存后再安装就是正式版了,记住,中间没有横线!!如果先前已经安装好180天的版本,请在添加删除VisualStudio2005时,可以输入序列号,进行升级。找到SETUP文件夹下的setup.

  • Hadoop基础-Map端链式编程之MapReduce统计TopN示例

    Hadoop基础-Map端链式编程之MapReduce统计TopN示例

  • 常用坐标系简介(正在完善~)

    常用坐标系简介(正在完善~)

  • vue3 axios跨域_vueaxios跨域请求

    vue3 axios跨域_vueaxios跨域请求//vue.config.jsconstpath=require(“path”);constwebpack=require(“webpack”);module.exports={//项目部署的基本路径//默认假设你的应用将会部署在域名的根部//比如,https://www.vue-cli.com///如果你的应用是部署在一个子路径下,那么你需要在这里指定子路径,比如,如果你部署在https://www.my-vue.com/my-ap.

  • roc曲线的意义_【科研助手】ROC曲线在医学诊断类稿件中的应用「建议收藏」

    roc曲线的意义_【科研助手】ROC曲线在医学诊断类稿件中的应用「建议收藏」ROC曲线,即受试者工作特征曲线(receiveroperatingcharacteristiccurve),是以灵敏度为纵坐标,1-特异度为横坐标绘制而成的曲线,其在临床医学诊断类稿件中受到人们的广泛关注且应用逐渐深入。而稿件中的ROC曲线应用是否合理及数据逻辑能否行得通,还需认真分析。今天,小编就跟大家聊一聊ROC曲线在医学诊断类稿件中的应用。传统的诊断试验评价方法要求将试验结…

发表回复

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

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