局部敏感哈希(LSH)之simhash和minhash

局部敏感哈希(LSH)之simhash和minhash

minhash

1. 把文档A分词形成分词向量L
2. 使用K个hash函数,然后每个hash将L里面的分词分别进行hash,然后得到K个被hash过的集合
3. 分别得到K个集合中的最小hash,然后组成一个长度为K的hash集合
4. 最后用Jaccard index求出两篇文档的相似度

simhash

1. 把文档A分词形成分词向量L,L中的每一个元素都包涵一个分词C以及一个分词的权重W
2. 对L中的每一个元素的分词C进行hash,得到C1,然后组成一个新的向量L1
3. 初始化一个长度大于C1长度的向量V,所有元素初始化为0
4. 分别判断L1中的每一个元素C1的第i位,如果C1i是1,那么Vi加上w,否则Vi减去w
5. 最后判断V中的每一项,如果第i项大于0,那么第i项变成1,否则变成0
6. 两篇文档a,b分别得到aV,bV
6. 最后求出aV和bV的海明距离,一般距离不大于3的情况下说明两篇文档是相似的

SimHash的工作原理

SimHash算法工作流程图:
<span>局部敏感哈希(LSH)之simhash和minhash</span>
<span>局部敏感哈希(LSH)之simhash和minhash</span>
 
  • 1、分词,把需要判断文本分词形成这个文章的特征单词。最后形成去掉噪音词的单词序列并为每个词加上权重,我们假设权重分为5个级别(1~5)。比如:“ 美国“51区”雇员称内部有9架飞碟,曾看见灰色外星人 ” ==> 分词后为 “ 美国(4) 51区(5) 雇员(3) 称(1) 内部(2) 有(1) 9架(3) 飞碟(5) 曾(1) 看见(3) 灰色(4) 外星人(5)”,括号里是代表单词在整个句子里重要程度,数字越大越重要。

  • 2、hash,通过hash算法把每个词变成hash值,比如“美国”通过hash算法计算为 100101,“51区”通过hash算法计算为 101011。这样我们的字符串就变成了一串串数字,还记得文章开头说过的吗,要把文章变为数字计算才能提高相似度计算性能,现在是降维过程进行时。

  • 3、加权,通过 2步骤的hash生成结果,需要按照单词的权重形成加权数字串,比如“美国”的hash值为“100101”,通过加权计算为“4 -4 -4 4 -4 4”;“51区”的hash值为“101011”,通过加权计算为 “ 5 -5 5 -5 5 5”。

  • 4、合并,把上面各个单词算出来的序列值累加,变成只有一个序列串。比如 “美国”的 “4 -4 -4 4 -4 4”,“51区”的 “ 5 -5 5 -5 5 5”, 把每一位进行累加, “4+5 -4+-5 -4+5 4+-5 -4+5 4+5” ==》 “9 -9 1 -1 1 9”。这里作为示例只算了两个单词的,真实计算需要把所有单词的序列串累加。

  • 5、降维,把4步算出来的 “9 -9 1 -1 1 9” 变成 0 1 串,形成我们最终的simhash签名。 如果每一位大于0 记为 1,小于0 记为 0。最后算出结果为:“1 0 1 0 1 1”。

 

整个过程图为:

<span>局部敏感哈希(LSH)之simhash和minhash</span>

 

一个例子如下:
<span>局部敏感哈希(LSH)之simhash和minhash</span>
 
<span>局部敏感哈希(LSH)之simhash和minhash</span>
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

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

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

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

(0)


相关推荐

  • JVM性能调优

    JVM性能调优1、JVM调优目标:使用较小的内存占用来获得较高的吞吐量或者较低的延迟。程序在上线前的测试或运行中有时会出现一些大大小小的JVM问题,比如cpuload过高、请求延迟、tps降低等,甚至出现内存泄漏(每次垃圾收集使用的时间越来越长,垃圾收集频率越来越高,每次垃圾收集清理掉的垃圾数据越来越少)、内存溢出导致系统崩溃,因此需要对JVM进行调优,使得程序在正常运行的前提下,获得更高的用户体验和运行…

  • Java输出结果保留两位小数

    Java输出结果保留两位小数Java输出结果保留两位小数

  • 计算机445 135 139端口,Win7如何关闭445 135 138 139端口[通俗易懂]

    计算机445 135 139端口,Win7如何关闭445 135 138 139端口[通俗易懂]5月12日全球爆发勒索病毒,国内外很多行业已遭受勒索病毒的侵害,勒索病毒迅速传播,目前已知传播途径基本都是通过445135137138139端口进行传播,那么只要关闭这些端口即可起到很好的预防作用,本文将介绍Win7怎么关闭445135137138139端口的方法。关闭445135137138139端口方法教程:1、打开Windows徽标(开始菜单),点击“控制面板”;2、…

    2022年10月10日
  • vuex的五大核心_vue的核心是什么

    vuex的五大核心_vue的核心是什么Vuex的核心概念Vuex有5个核心概念,分别是State,Getters,mutations,Actions,Modules。StateVuex使用单一状态树,也就是说,用一个对象包含了所有应

  • 常见分布式id生成方案_分布式id生成方案

    常见分布式id生成方案_分布式id生成方案文章目录一、为什么要用分布式ID1、什么是分布式ID2、那么分布式ID需要满足哪些条件二、分布式ID有哪些生成方式1、基于UUID2、基于数据库自增ID3、基于数据库集群模式4、基于数据库的号段模式5、基于Redis模式6、基于雪花算法(Snowflake)模式7、百度(uid-generator)8、美团(Leaf)号段模式snowflake模式9、滴滴(Tinyid)Http方式接入Java客户端方式接入三、总结一、为什么要用分布式ID在说分布式ID的具体实现之前,我们来简单分析一下为什么用分布式

    2022年10月25日
  • E-commerce 中促销系统的设计

    E-commerce 中促销系统的设计

发表回复

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

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