CWYAlpha

Just another WordPress.com site

Thought this was cool: 短文本合并重复(去重)的简单有效做法

leave a comment »


短文本合并重复(去重)的简单有效做法

2012/6/12

不大合适的SimHash

前些日子看了Charikar SimHash的介绍《Simhash算法原理和网页查重应用》,核心思想是用一个f位的hash值来表示文件的特征值,然后使用hash值之间的Hamming距离来衡量相似性。输入的是一个文档的特征集合,输出的是f位的二进制数S。

于是用来测试短文本(长度在8个中文字符~45个中文字符之间)相似性,做法很简单:

1.将短文本做分词,得到分词数组,数组每一个元素都转为hash字符串。

2.利用simhash算法来计算分词数组的simhash值。

3.利用simhash的similarity算法计算simhash1和simhash2的相似度。

这种做法的缺点是:

1.误判率高。

如下图所示,

 http://s4.sinaimg.cn/middle/72995dcc4c0c38b09c313&690

SimHash可能不适合做这种短标题的重复度判断,虽然SimHash在空间消耗和计算复杂性方面相对Shingle和BloomFilter占优

 

介绍一下2009年2月份我们做Twitter锐推榜时是如何做的

Twitter中对于热门事件的中文表达多种多样,转发时又往往会追加很多格式的各种内容,造成了相似内容的短文本的信息指纹不同,在这种情况下,段国成认为需要先为短文本抽取标签,再通过标签来计算相似度进行锐推合并。

1.
短文本抽取标签的方法:

1.1. 剔除所有英文、数字、标点字符;

1.2. 剔除所有Twitter用户名;

1.3.分词,并标注词性,仅保留实体词性
,如名词、动词;(技巧一!)

1.4.过滤掉常用实体词
(常用实体词是通过对历史锐推训练而得,即建立自己的停止词表);(技巧二!)

1.5.计算保留实体词的词频,并以此为权重,选择权重大的词语作为标签;

1.6.标签数组长度大于一个阈值
(如3),才认为是有信息量的锐推,否则忽略。(技巧三!)

 

2.
合并相似短文本(即我们所说的Retweet
)方法:

2.1.以每个标签作为Shingle特征(即核心思想还是“一个数据段分成若干Shingle,每个Shingle计算出一个hash值,然后组成一个以hash值为元素的数组,以此作为特征值或叫信息指纹来表示这个数据段”);

2.2.以网页去重领域中改进的
Shingle
方法
来进行计算近期内(目的:缩小计算范围)
锐推的相似度(Shingle算法的核心思想是将文本相似性问题转换为集合的相似性问题,改进的Shingle方法的时间复杂度近似于线性);

2.3.对相似程度大于一定阈值的、不同信息指纹的热门锐推,再次扫描出来,将它们的热度进行合并。

 

以上结果就构成了@rtmeme的运算机制。它特别适合处理十几个、几十个汉字的短文本合并重复,适用于微博领域。

 

也看到有人这么做:先Shingle再SimHash,不知道是否适合海量短文本合并重复,回头试试看。

@郑昀于北京

 

 

推荐阅读:

1、

『我认为腾讯目前的O2O产品其实是没任何借鉴意义的,因为真的做得比较差。但我们也有一点做好的决心。……所以尽管我们在局部解决了闭环的问题,但实际上整个O2O的闭环仍然是遥遥无期的事情。』——《戴志康:让我焦躁并痛苦着的O2O》http://t.cn/zOFL5Cc

2、

#O2O是个伪概念#:知乎O2O系列问答:http://t.cn/SzuEjr;清科投资集团对O2O的解读:http://t.cn/zOgcikN;黄绍麟:O2O和无线电子商务是伪概念http://t.cn/zOfodfZ

3、

推荐阅读:『而Google的#simhash#算法产生的签名,可以用来比较原始内容的相似度时,便很想了解这种神奇的算法的原理。出人意料,这个算法并不深奥,其思想是非常清澈美妙的。』——《Simhash算法原理和网页查重应用》http://t.cn/zOrhqUb

4、

旧文推荐阅读:『我的团长我的团中,学生李梁对龙文章说,我相信你们能战胜日本人,但问题仍然存在。李鸿章们不遗余力地修铁路、办实业,但问题依然存在。 器物上的改变是不会解决问题的。』http://t.cn/zOlg0Kg

 

赠图一枚:

https://i0.wp.com/ww4.sinaimg.cn/large/70a90346gw1dtjk9sv096j.jpg

本文链接


0

   

0

IT 牛人博客聚合网站(udpwork.com) 聚合
|
评论: 0
|
10000+ 本编程/Linux PDF/CHM 电子书下载

from IT牛人博客聚合网站: http://www.udpwork.com/item/7476.html

Written by cwyalpha

六月 12, 2012 在 5:09 下午

发表在 Uncategorized

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s

%d 博主赞过: