内容消重算法总结

背景

在内容推荐业务中,因为用户发布的内容经常有重复,而重复消费相同/相似内容,对用户的价值不大。

所以一般在推荐的物料池中,我们会对内容进行相似消重。本文重点总结一下常见的消重算法,以及在消重算法中会遇到的一些问题。

一般来说,消重算法,主要包括:指纹生成,相似度计算,group生成三个阶段。

 

具体说明

1、simhash

从谷歌中来,到谷歌中去,又是一篇谷歌07年论文里来的《Detecting Near-Duplicates for Web Crawling》,Google用的网页去重算法。步骤很简单:

——>分词,计算词权重

——>对词hash

——>把所有的0变成-1,乘以词的权重

——>hash值求和,累加

——>降维,生成指纹

——>计算海明距离

放一张图

 

使用simhash需要注意的几个问题:

1、假设有abc三个文本,D(ab)=D(bc)=1,D(ac)=2。那么消重的时候,假设我们认为距离<=1为相似。一个group的keyitem节点是谁非常关键。如果以b为keyitem,ac会被消重在一起,如果以a为keyitem,c就不会消重在一起。

2、simhash适合于长文本的消重,在短文本里,simhash表现很差,不太典型的例子:比如:”爸爸打我” 跟”我打爸爸” 会被消重, 有人把词权重 用位置代替词频的思路不错。还有比如同义词问题,”我爱土豆””我爱马铃薯”不会被消重,但是实际上是一样的。

3、海明距离取多少合适,我个人感觉,针对不同的分类,可能需要不同的距离,一般来说,长文本距离小于3的基本都相似。

4、随着要比较的内容越来越多,比较的效率也是很重要的问题,比较偏向技术,此处不讲。

 

2、感知hash算法

感知哈希算法是一类算法的总称,主要用来做相似图片的搜索工作。包括aHash(平均值哈希)、pHash(感知哈希)、dHash(差异值哈希)。

这块涉及到图像的东西,简单说一下,准确率比较高的dHash。

核心还是生成dHash的指纹,步骤:

——>压缩图片:将图片压缩到非常小的像素点,方便计算,隐藏细节,保留核心特征。

——>灰度化:三维的RGB色值压缩到一维(彩色变黑白)

——>差异计算:每一行单独比较,如果前一个像素的颜色强度大于第二个像素,那么差异值就设置为True(也就是1),如果不大于第二个像素,就设置为False(也就是0)。

——>转化为hash值:我们将差异值数组中每一个值看做一个bit,每8个bit组成为一个16进制值,将16进制值连接起来转换为字符串,就得出了最后的dHash值。

——>计算海明距离

放图:

原图

 

 

压缩

 

 

灰度化

 

最后

在实际应用中,我们会发现,一个doc经常会由文本+图片共同组成,人去判断相似,也是综合信息去考量的。

实际的消重工作会基于这两类算法上做很多的优化跟补充。从产品上讲,消重的价值,是把那些”重复阅读起来”没有价值的信息,合并到一个信息里进去。而我们往往知道,某一个同质化的内容”刷屏”了。”重复内容”很多这个事情,又有新的阅读价值。而合并到一个信息里进去,合并后的聚类簇选择谁作为keyitem,也是产品工作的核心,一般来说,保护原创,保护优质是非常关键的。

业内也有人使用word2vector/doc2vector 用作消重的,工具各有利弊,能处理好业务的需求,就是好工具。  消重算法的核心,还是对高维的原始内容抽取核心特征降维抽象,然后比较抽象出的距离。

 

参考文章

https://www.jianshu.com/p/193f0089b7a2

海量数据相似度计算之simhash和海明距离

机器学习 2018-08-05
上一篇: 下一篇:

评论已关闭。