从0到1,了解NLP中的文本相似度 (4)

我们看到,对于上述两句话,在经过余弦计算后,得到的相似度为0.766(其夹角大概是40度),还是比较接近于1,所以,上面的句子S1和句子S2是基本相似的。由此,我们就得到了文本相似度计算的处理流程是:

找出两篇文章的关键词;

每篇文章各取出若干个关键词,合并成一个集合,计算每篇文章对于这个集合中的词的词频;

生成两篇文章各自的词频向量;

计算两个向量的余弦相似度,值越接近于1就表示越相似;

simhash

基于余弦复杂度,通过两两比较文本向量来得到两个文本的相似程度是一个非常简单的算法。然而两两比较也就说明了时间复杂度是O(n2),那么在面对互联网海量信息时,考虑到一个文章的特征向量词可能特别多导致整个向量维度很高,使得计算的代价太大,就有些力不从心了。因此,为了在爬取网页时用于快速去重,Google发明了一种快速衡量两个文本集相似度的算法:simhash。

简单来说,simhash中使用了一种局部敏感型的hash算法。所谓局部敏感性hash,与传统hash算法不同的是(如MD5,当原始文本越是相似,其hash数值差异越大),simhash中的hash对于越是相似的内容产生的签名越相近。

原理

simhash的主要思想是降维,将文本分词结果从一个高维向量映射成一个0和1组成的bit指纹(fingerprint),然后通过比较这个二进制数字串的差异进而来表示原始文本内容的差异。下面我们通过图文方式来解释下这个降维和差异计算的过程。

img

simhash算法流程实例

在simhash中处理一个文本的步骤如下:

第一步,分词:

对文本进行分词操作,同时需要我们同时返回当前词组在文本内容中的权重(这基本上是目前所有分词工具都支持的功能)。

第二步,计算hash:

对于每一个得到的词组做hash,将词语表示为到01表示的bit位,需要保证每个hash结果的位数相同,如图中所示,使用的是8bit。

第三步,加权

根据每个词组对应的权重,对hash值做加权计算(bit为1则取为1做乘积,bit为0则取为-1做乘积),如上图中,

10011111与权重2加权得到[2 -2 -2 2 2 2 2 2];

01001011与权重1加权得到[-1 1 -1 -1 1 -1 1 1];

01001011与权重4加权后得到[-4 4 -4 -4 4 -4 4 4];

第三步,纵向相加:

将上述得到的加权向量结果,进行纵向相加实现降维,如上述所示,得到[-3 3 -7 -3 7 -3 7 7]。

第四步,归一化:

将最终降维向量,对于每一位大于0则取为1,否则取为0,这样就能得到最终的simhash的指纹签名[0 1 0 0 1 0 1 1]

第五步,相似度比较:

通过上面的步骤,我们可以利用SimHash算法为每一个网页生成一个向量指纹,在simhash中,判断2篇文本的相似性使用的是海明距离。什么是汉明距离?前文已经介绍过了。在在经验数据上,我们多认为两个文本的汉明距离<=3的话则认定是相似的。

实现

完整代码见Github

func SimHashSimilar(srcWordWeighs, dstWordWeights []WordWeight) (distance int, err error) { srcFingerPrint, err := simhashFingerPrint(srcWordWeighs) if err != nil { return } fmt.Println("srcFingerPrint: ", srcFingerPrint) dstFingerPrint, err := simhashFingerPrint(dstWordWeights) if err != nil { return } fmt.Println("dstFingerPrint: ", dstFingerPrint) distance = hammingDistance(srcFingerPrint, dstFingerPrint) return } func simhashFingerPrint(wordWeights []WordWeight) (fingerPrint []string, err error) { binaryWeights := make([]float64, 32) for _, ww := range wordWeights { bitHash := strHashBitCode(ww.Word) weights := calcWithWeight(bitHash, ww.Weight) //binary每个元素与weight的乘积结果数组 binaryWeights, err = sliceInnerPlus(binaryWeights, weights) //fmt.Printf("ww.Word:%v, bitHash:%v, ww.Weight:%v, binaryWeights: %v\n", ww.Word,bitHash, ww.Weight, binaryWeights) if err != nil { return } } fingerPrint = make([]string, 0) for _, b := range binaryWeights { if b > 0 { // bit 1 fingerPrint = append(fingerPrint, "1") } else { // bit 0 fingerPrint = append(fingerPrint, "0") } } return } func calcWithWeight(bitHash string, weight float64) []float64 { bitHashs := strings.Split(bitHash, "") binarys := make([]float64, 0) for _, bit := range bitHashs { if bit == "0" { binarys = append(binarys, float64(-1)*weight) } else { binarys = append(binarys, float64(weight)) } } return binarys } 结果

我们使用了调换一段长本文的语序来测试simhash的效果:

文本1: "沉默螺旋模式中呈现出民意动力的来源在于人类有害怕孤立的弱点,但光害怕孤立不至于影响民意的形成," + "主要是当个人觉察到自己对某论题的意见与环境中的强势意见一致(或不一致时),害怕孤立这个变项才会产生作用。 " + "从心理学的范畴来看,社会中的强势意见越来越强,甚至比实际情形还强,弱势意见越来越弱,甚至比实际情形还弱,这种动力运作的过程成–螺旋状" 文本2: "从心理学的范畴来看,害怕孤立这个变项才会产生作用。社会中的强势意见越来越强,甚至比实际情形还强,弱势意见越来越弱," + "主要是当个人觉察到自己对某论题的意见与环境中的强势意见一致(或不一致时),甚至比实际情形还弱,这种动力运作的过程成–螺旋状 " + "但光害怕孤立不至于影响民意的形成,沉默螺旋模式中呈现出民意动力的来源在于人类有害怕孤立的弱点"

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zyxygj.html