Twitter中近似重复消息的判定方法研究((

曹鹏1,2,李静远1,满彤1,2,刘悦1,程学旗11中国科学院计算技术研究所网络重点实验室,北京,1001902中国科学院研究生院,北京,100190E-mail:caopeng@software.
ict.
ac.
cn摘要:微博客是Web2.
0出现以来的一个新生概念.
著名的Twitter系统是微博客中具有代表性的一个,其全球用户已经超过一亿,在世界范围内具有重要影响力:目前知名政治家、社会名流和大企业几乎都是Twitter的用户.
Twitter系统中的消息通常比较短小,而且语法不规范.
同时,由于Twitter中允许用户以多种格式自由转发消息,系统中存在大量内容重复或近似重复的消息.
重复消息的存在加重了系统存储的负担,对用户阅读、理解以及分析消息的内容也造成了不利影响.
本文分析了Twitter系统中转发消息的语法特点,并利用这些语法特点提取规则,把转发的消息变成普通的消息.
本文还提出统计字符种类和最短编辑距离两种字符串距离计算的方法以判定Twitter中近似重复的消息.
实验结果表明,两种方法具有扩展性强、实现简单、效率高等优点,能够有效地解决Twitter上的信息重复现象.

关键词:微博客;Twitter;重复信息DetectingNearDuplicateMessagesinTwitterPengCao1,2,JingyuanLi1,TongMan1,2,YueLiu1,XueqiCheng11KeyLabofNetworkScienceandTechnology,InstituteofComputingTechnology,CAS,Beijing1001902GraduateUniversityofChineseAcademyofSciences,Beijing,100190E-mail:caopeng@software.
ict.
ac.
cnAbstract:Microblogisaverynewconceptofweb2.
0.
ThemostimportantmicroblogsysteminuseisTwitter,withmorethanonehundredmillionusersallovertheworld.
Fornow,Twitterisoneofthemostinfluentialvoicesoftheglobe,itsusersincludingcelebrities,well-knownpoliticiansandfirst-ordercompanies.
ThelengthofthemessagesinTwitterisshort,andthecontentsofthemessagesareverylikelytobeinformalinsyntaxorgrammar.
Moreover,Twitterdoesnotstrictlydefinethesyntaxofretweet,whichcausestheexistenceofagreatnumberofnearduplicatemessages.
Thesenearduplicatemessagescanbeawasteofstorageresources,andcangreatlyreducetheuserexperienceofTwitter.
Inthispaper,thesyntaxofretweetmessagesisanalyzed,andamethodispresentedtoremovetheretweetsymbolsofmessagesusingtheanalyzedresults.
Inaddition,twotextdistancecalculatingmethods–characterstatisticsandshortesteditingdistance–areproposedtoclustertheTwittermessagesintogroupsofnearduplicatemessages.
Throughaseriesofexperiments,weprovedthatourmethodsareefficient,extensibleandeasytoimplement,andcanbeusedtodiscoverandfilterthenearduplicatemessagesinmicroblogs.
Keywords:Microblog,Twitter,NearDuplicateMessage概述随着Web2.
0的出现以及迅猛发展,社交类网站的概念渐渐深入人心.
随之而产生了"微博客(Microblog)"的概念.
微博客是一种非正式的迷你型博客,是最近新兴起的一个Web2.
0表现形式,是一种可以即时发布消息的系统.
微博客的最大的特点是消息的集成化和API的开放化.
用户可以通过移动设备、IM软件(Gtalk、MSN、QQ、Skype等)和外部API接口等途径发布消息.
例如,自2006年以来利用无线通信技术,Twitter用户无需输入手机号码,就可以通过客户端在微博客上发布信息.
微博客的另一个特点是其消息相对比较短小,每次最多能够发送140个字符的短文本,因此一般发布的消息只能是只言片语.

Twitter[1]是国外的一个社交网站,也是微博客中比较有代表性的实例之一.
目前,Twitter的使用非常火爆,用户数量高居国内外各种微博客系统之首.
根据2010年4月份在美国洛杉矶召开的Twitter开发者大会给出的权威资料,当前Twitter用户超过1.
05亿,且仍然以每天30万新用户的数量增长;同时,Twitter服务器的月访问请求超过190亿次[2].

在Twitter中,用户之间可能建立的好友关系称为"追随关系",即一个用户可以根据兴趣选择自己愿意关注的人而"追随"他,当然,同时他自己也可能被其他一些用户追随.
用户可以随时以消息形式发送一些内容,就像发送手机短信一样,所以类似Twitter这样的微博服务又被称为互联网上的短信平台.
一个用户发出的信息对他的所有"追随者(follower)"都是公开的.
因此,如果一个用户写了一条消息(称为tweet),他的所有追随者都可以看到,并且他们可以回复这个人的消息,而被回复的人同样可以看到别人回复他的消息.
于是,用户之间可能针对一个话题展开激烈的讨论,正如我们日常生活的对话一样,消息会越积累越多.
一个用户在Twitter中所写的消息,系统会自动地让他的追随者知道,这属于一种"推送"的方式.
另外,作为一个Twitter用户,他一般会经常关注自己所追随的人,回复他们所发的消息.
因此Twitter为用户之间信息交流提供了一个基础的平台.

Twitter中除了好友关系和消息回复关系以外,还有消息的转发关系.
也就是说,同一个内容的消息,可以在好友之间进行转发(retweet).
正是通过这种方便且简单的转发方式,Twitter可以令一条消息在数分钟内在数百万用户间大范围传播.

然而,在对Twitter的调研过程中我们发现,用户在发送消息的时候,往往会完全复制别人的消息,或者经过少量的修改后(添加、修改、删除部分字符),作为自己的消息而再次发送出去.
于是在Twitter中往往存在大量内容相同或者相似的消息,本文中称其为近似重复信息(nearduplicatemessage).
在单纯考虑消息种类的时候,经过转发的和少量修改的消息会有很大的重复,而内容重复的消息往往是没有意义的.
例如,Twitter的用户往往会发现,因为存在大量的重复消息,自己阅读到的消息数量很多,但真正得到的信息量却很有限.
比如自2010年5月份以来,Twitter中关于"世博会(WorldExpo)"的消息相对较多,而真正的原创的消息数量却有限,大部分都是用户之间来回转发的消息.
大量重复消息的存在对用户的影响往往是灾难性的:它们白白浪费了用户的时间和精力,降低了用户的使用热情.
去掉这种大量重复的消息,不但可以减轻系统存储的负担,而且可以提高用户阅读、理解和分析消息内容的效率,从而提高用户的使用热情.
因此,提出一种微博客系统上近似重复信息的高效判定方法是十分重要而有意义的.

本文详细地分析了Twitter系统中消息转发现象.
从大量存在的转发消息中提取出一些固定的程式化的词法结构特征,并据此归纳出一些规则.
然后,按照这些规则预处理Twitter中的消息,得到和系统无关的"原始消息"文本(真正被转发的消息内容).
在此基础上,提出针对Twitter消息的字符串近似匹配算法,以计算两条消息的距离,从而决定它们是否近似重复.

接下来的章节安排如下:本文第二部分介绍消息去重的相关工作和基本方法,第三部分阐述Twitter上消息去重的特殊性以及本文所采用的方法.
第四部分给出实验结果,第五部分是结论.

基本概念和相关工作消息的本质就是字符串.
因此最简单直接的消息重复判定规则是对两条消息进行全文匹配,即如果两条消息完全相同,则认为是重复的.
这种方法的特点是实现简单,只需要对字符串排序;但是其缺点也相当明显的:两条消息内容绝对相同,对文本要求太敏感、鲁棒性差.
因为完全相同的两条消息在twitter系统中几乎是不存在的.
一般地,Twitter用户总会在原始消息上添加、删除、修改部分内容,这种简单的方法并不能鉴别出这样的重复消息.
所以本文更关心近似重复消息,而不仅仅是完全重复消息.

判定近似重复消息的一般方法是给对每个消息进行压缩,压缩的信息称为指纹(fingerprint),然后利用指纹比较消息是否相同.
指纹方法是一种普遍的方法,它的本质是利用哈希(hash)进行文本压缩,判断重复性.
文献[3]对网络文档(网页)进行查重.
作者采取了多指纹的方法,即每个文档有若干个指纹,如果两个文档相同的指纹数达到一个预先给定的阈值,则认为它们是相同的.
如果允许误判,还有经典的Bloom-filter[4]方法可以用来进行查重,但它不仅限于消息查重领域.

文献[5]中提出的Simhash给出了在规模上百万的网页中查找重复的一个有效方法.
Simhash是一种文档指纹算法,它有如下性质:两个近似文档的指纹(两个整数)只差几个数据位(bit)[6].
这样,相当于把文档映射为整数,文档的相似度对应为整数的接近.
这种方法对哈希函数的选择要求比较高.

另外一种消息去重的直接想法是在消息中提取关键词,如果关键词的集合基本相同则认为它们重复.
更为深入的方法是提取出文档的摘要,根据语义的信息判断文档的相似度.
这种方法在消息聚类领域使用得比较广泛.
但是,它的缺点是涉及到的技术比较复杂,例如,自然语言理解、关键词提取、摘要抽取等等,因此实现难度大、复杂度比较高,效率也相对较低.
而且这种方法比较适合分析较长的文本,例如普通的文章,因为它们往往具有比较完备的结构、语法和语义信息.
但是,Twitter中的消息都是140个字符以内的短文本,文本内容和语法结构通常并不很规范,甚至还可能包括众多用户自定义的符号和标记,因此很难提取适当的关键词,抽取摘要就更加困难.
因此,Twitter中的近似重复消息判定也不能采取这种方法.

Twitter上近似重复消息的判定方法Twitter中转发消息的特点登录Twitter,用户会发现,有很多消息是非常相似的.
这些消息通常可以看作同一内容在好友之间的转发.
系统本身在用户转发消息时会给消息加上一些特殊的字符(如@、RT等),另外,用户回复某条消息时,系统同样会加上固定模式的字符,这些都对转发消息的识别提供了便利条件,为顺利找到"原创消息"提供了帮助.
但对于"原创消息",Twitter系统并不会在消息中加入特殊字符,因此,必须利用字符串本身的特性进行近似重复消息的判定.

Twitter对于用户消息的转发,在消息的语法结构本身并没有十分明确和严格的定义.
但是,根据文献[7],以及对实际采集到的消息的观察,我们发现,Twitter系统中转发的消息通常包含如下特征(一般"@"符号的后面是用户名):表1Twitter转发消息的特征Table1CharacteristicsofTwitterretweetmessage转发消息特征举例RT:@RT:@Aretweeting@retweeting@Aretweet@retweet@A(via@)(via@A)RT(via@)RT(via@A)hellothx@hellothx@Ar@r@Ahello这些转发消息特征的位置以及具体样式并不是一成不变的.
例如,假设用户名为A的用户发了一条消息,内容为hello,而用户名为B的用户转发了A的消息,按照上述的符号说明,转发的消息可能具有如下的格式:B:RT:@A:helloB:retweeting@A:helloB:retweet@A:helloB:hello(via@A)B:RT(via@A):helloB:hellothx@AB:r@A:hello事实上,Twitter系统本身并不强制约定用户转发消息的格式,以上格式只是比较常见的.
实际的情况千变万化.
例如,转发消息可能在"@用户名"后面缺少冒号,消息中可能有大量空白字符,此外,有些用户在转发消息时,甚至会修改消息的内容.
这些都给对消息的预处理带来了困难.

Twitter中消息预处理对于一个转发消息,我们考虑的对象是被转发的"原始消息",所以按照3.
1节所述规则,需要对消息进行一些预处理,把消息中的转发特征字符串过滤掉.

算法的描述如下:根据规则,查找@符号的位置,然后提取前后若干个位置的字符,如果可以匹配3.
1节中的特征,则删除这些内容.
如果有多个@符号,要依次分别处理.
但是我们要处理的不仅仅是转发关系,有些消息中包含单独的一个@符号后跟用户名,它并不是转发消息,而是代表针对这个用户发的消息,单独考虑消息内容的时候,这些字符也应删除掉.
另外,有的消息中会出现"#"符号,该井号后面紧接的是消息的关键词(或称为话题),我们认为保留这些内容对消息去重没有影响.
总之,经过基于规则的字符串匹配算法,把消息处理成最普通的字符串,这些字符串包含着消息的原始内容.

算法流程:步骤1查找第一个没探测到的@符号,如果没有则结束,否则转步骤2.
步骤2模糊匹配上述的规则,看看@符号前后的部分是否能和规则匹配,这里的匹配允许单词与符号之间出现任意多空白,冒号可有可无.
若能匹配规则,转步骤3,否则转步骤1.

步骤3删除掉匹配规则的部分,消息内容缩短.
转步骤1.
这样,我们就获得了"原始消息".
接下来,可以采取一些字符串处理中的经典算法,比较两条消息的相似度.

Twitter中消息距离的计算在预处理之后,我们获得的是字符串,计算字符串之间距离,可以用任意经典的方法.
本文使用统计字符种类和最短编辑距离两种方法.

3.
3.
1统计字符种类一种常用的给字符串做指纹的方法是统计字符串中每个字符的种类.
假设消息的编码方式是Unicode.
每个消息的字符对应的是一个16bit的二进制数.
由于一般的文本编辑器最小的编辑单位是4个bit.
我们把一个16bit的数拆成4组,每组4个bit,则每个组有24=16种;如果再考虑组别的话,每4个bit的可能性有16*4=64种情况.
这样我们可以统计每条消息中这64种情况的出现次数,为每个消息做一个指纹.
即使消息不是Unicode编码,我们也可以强行的把消息按Unicode理解,这相当于每64位分为一组.
于是,我们可以把所有的消息都按照这种方法解析.

这样对于一个消息M,可以得到向量V=(V1,V2……V64),其中Vi(1≤i≤64)代表这条消息的二进制表示中第i种情况出现的次数.
于是,两个消息的相似度,可以完全转化为两个向量之间的相似度.
而向量的相似度通常可以用曼哈顿距离或者余弦距离来计算.

事实上,这种表示方法压缩了字符串,用每个字符出现的次数代替了字符串本身,损失了字符出现的位置信息.
因此,对于同一个消息,如果只调换了字符顺序的话,通过这种方式计算出的消息指纹不变.
但实际情况中,这种情况往往出现较少.
(一个极端的例子是"喜欢"和"欢喜".
)3.
3.
2最短编辑距离最短编辑距离是一个经典的概念.
对一个字符串进行添加一个字符、删除一个字符或修改一个字符定义为进行一次操作.
两个字符串的最短编辑距离是指把一个字符串变为另外一个字符串需要的最少操作次数.

求解最小编辑距离是一个可以用动态规划方法解决的经典问题.
如果两条消息字符串长度分别为len1,len2,则计算它们的最短编辑距离的算法复杂度是O(len1*len2).
通常,这样的算法时间复杂度在长文本中是很慢的.
但是,针对Twitter系统中消息的长度都小于140个字符这一特性,我们可以使用它来计算消息的距离.

最短编辑距离对字符串的字符顺序比较敏感.
因此如果调换了消息中的字符顺序,它们的最短编辑距离差异会比较大.

Twitter中去除重复消息的方法由于上节中提到的两种距离计算方法各有利弊,本文采用两种方法叠加来计算消息的距离.
假设两个消息字符串之间的曼哈顿距离和最小编辑距离分别为d1和d2.
则定义两个消息的距离为D=d1+d2.
如果两条消息的距离小于一定的阈值(例如阈值选择5),则认为消息是近似相同的.

实验数据采集我们通过约20个TwipAPI代理,采集了Twitter系统中的将近70,000个用户的约854,629条消息.
数据采集的方式是通过浏览twitter得到一些用户的用户名,利用系统本身提供的api对这些用户、这些用户的好友、以及好友的好友的消息进行周期性采集.
采集时间为2010年4月16日至6月12日.
由于上海世界博览会恰好在此期间开幕,我们重点采集了Twitter上与世博会相关的消息,采集时使用的关键词包括"世博"、"exposhanghai"等.
消息长度分布在预处理消息之前,得到的消息字符串长度分布如图:图1消息长度分布图Fig1Thedistributionofthelengthofmessages可见,由Twitter本身的特征决定了所有的消息都比较短.
在120个字符以上的消息数量最多.
消息的平均长度只有66.
3.
对如此短的消息计算最短编辑距离的时间复杂度是可以接受的.

预处理后的结果按照3.
4节中介绍的方法,对所有消息都进行了预处理.
重点看了含有特殊字符(@rt等)的消息,以下是部分结果:图2预处理前的部分消息Fig2Messagesbeforepre-processing图3预处理后的消息Fig3Messagesafterpre-processing`由图2、图3可见,消息1是对bestguy说的话,因此需要去掉头部的部分内容;而消息2中的"retweet"一词是消息本身的文本的内容,所以应该保留,不能删掉;消息3结尾的"via"符合预先给出的模式,需要删掉.
消息4是既有"RT@"又有"thx@"的情况,同时与两个模式匹配,所以都需要去掉;消息5是"RT"在尾部,而且有两个"@"符号,需要同时处理,另外,消息头部的"thx"属于消息本身的文本内容,不应该删掉;消息6是头部不止有一个"RT@"的情况.
可见,我们设计的基于模式规则的消息预处理算法可以正确处理twitter中消息的绝大多数情况.

消息去重显示我们选取了与"世博"相关的消息一共.
找到了一些重复的消息,下图是我们的算法找到的一些近似重复的消息:图4近似重复的消息-1Fig4nearduplicatemessages-1从图4可以看出,显然是由于用户的转发行为,造成了重复的消息.
又如:图5近似重复的消息-2Fig5nearduplicate-2图5显示了系统中非用户转发行为产生的另外一类重复消息.
显然,这是一个稍微有一些字符不同的广告.

实验表明,对随机抽取的1000条相关的消息进行去重后,剩余894条,重复消息的比例高达10.
6%.
对与"世博"相关的全部27,559条相关的消息进行去重后,剩余16778条,近似重复消息达到10781条,占总数的39.
1%.
可见,如果不保存这些近似重复的信息将会节约很大存储空间.

结论本文提出了一套针对Twitter的近似重复消息判定方法.
由于Twitter消息的特殊性,分析其中短小的、结构随意的消息时并不适合采取通用的自然语言处理方法.
本文提出了基于字符串的方法,该方法包括两部分:预处理部分:根据统计规律产生的规则把消息处理成普通的字符串;计算距离部分:采用曼哈顿距离和最短编辑距离的叠加计算两个字符间的距离.

本方法不用进行自然语言理解的复杂计算,具有效率高、效果好、可扩展性强的特点.

在未来的工作中,可以考虑在预处理部分的规则库中添加新规则.
另外,计算距离的方法可以尝试采取其他的距离定义(例如cosine距离等),计算距离的加权方法也可以进行其他尝试.
本文提到的计算消息距离的方法对消息聚类也有一定的帮助.
今后,在大规模消息聚类中,还可以考虑采取分布式的方法(例如,分布式K-means聚类),提高聚类的效率.