张庆梅

（中国科学技术大学 软件学院，江苏 苏州215123）

舆情去重算法的研究与比较

张庆梅

（中国科学技术大学 软件学院，江苏 苏州215123）

近年来，舆情信息在大数据服务中广泛被加工使用，但转载、复制等操作使得采集的舆情信息重复量庞大，给后期的加工带来困难。在这种情况下，针对舆情数据开展去重研究的却相对较少。文中针对舆情去重不可避免但缺乏理论指导的问题，通过研究SimHash、MinHash、Jaccard等经典去重算法，结合TF、TF-IDF、特征码等不同特征选择和3 000舆情样本进行实验，最终发现MinHash+特征码运行时间最短；Jaccard的漏判数最少，召回率可达90%以上；MinHash算法的误判数最少，去重精度可达100%，并且MinHash通过阈值的调整能够获得Jaccard同样的召回率。

舆情数据；去重算法；特征选择；相似度计算；大数据服务

截至2015年12月，我国社交网站、微博等社交应用的网民使用率达77.0%[1]，新媒体的迅捷性、开放性和方便性使得越来越多的网民使用其表达自己的意见和看法[2]。各种新媒体的出现，使得舆论信息传播范围更广、速度更快、数量更大，舆情对社会经济影响也越来越大。西蒙曾指出：在信息时代，最稀缺的资源不再是信息本身，而是对信息的处理能力。目前大数据服务公司利用互联网技术，收集有关舆情信息，再加工分析，为银行、信托等金融机构提供企业、个人的舆情数据，为其评估客户信用、预估客户风险、预测金融发展趋势提供参考。此外对金融舆情信息进行分析，能够对金融运行的形式和趋势做出预测和判断，方便引导舆情基于真实信息向有利于金融稳定运行的方向发展[3]。但内容复制、转载等原因，互联网上存在大量的相似重复网页信息[4]，致使数据收集阶段获得的数据往往重复严重。这些重复的舆情数据一方面加大了后期人工运营的强度。另一方面影响数据服务质量，增大数据存储难度，降低索引效率，严重影响舆情价值的发挥。

文中针对舆情去重进行研究，分析SimHash、MinHash、Cosine Similarity、Jaccard 基于相似性度量的去重原理，对舆情数据文本的 TF、TF-IDF、TextRank和特征码进行提取，使用不同方式将特征选择与相似性计算方式进行结合，编程实现各个去重算法。确定合理高效的测试方案，利用3 000舆情数据样本进行测试，获取各个算法在舆情去重方面的测试结果，比较分析。实验成果将在舆情数据去重方面为人们在进行算法选择时提供决策参考。

1 相关工作

就舆情研究而言，国外起步较早，从19世纪中期开始发展，到20世纪中期已逐渐走向成熟。我国对网络舆情的研究，直到20世纪末才刚刚开始[5]。整体上对舆情的研究主要集中于这两个方面，一是收集和分析舆情信息进行舆情对策，来帮助政府或企业有效地应对舆情节拍缓慢和极端化等问题[6]。二是基于信息技术的舆情监测和舆情挖掘研究，依托计算机和网络技术建构监测、分析和预警系统[7]。大数据时代的来临，越来越依赖舆情大数据分析技术，而面对如此庞大的数据，大数据在进行分析之前必须对数据进行清洗工作，其中清洗环节的一个重要工作就是去除重复数据。

就去重算法而言，其主要应用于搜索引擎。据统计，用户在回答“检索信息时遇到的最大问题”这一提问时，选择“重复信息太多”选项的占44.6%，排名第1位[8]。因此在搜索引擎方面，解决网页重复的问题是必不可少的步骤，网页去重技术蕴含于信息搜索技术，是后者发展的有力支撑[9]。此外去重的开展是基于相似度的计算，因此去重技术的基本算法也被应用于解决高维数据的聚类问题。例如利用基于LSH算法协同过滤处理高维数据的良好特性来解决图书馆用户的聚类问题[10]。近年来，随着存储容量快速增长，去重技术也被应用于数据备份系统来消除冗余数据，降低数据存储成本[11]。

国外在去重方面的研究开始于19世纪，去重算法的应用也比国内成熟。目前许多去重算法都是在最初提出的算法的基础上进行改进。1997年，Andrei Broder首次提出MinHash算法[12]，该算法可以用来快速估算两个集合的相似度，查找网络上的重复网页或者相似新闻网页[13]。在2000年，Peter.D.Turney首次提出关键字提取算法，将文章中出现的词语划分为关键和非关键两部分，从关键类中选择若干个作为关键词。这个方法的提出为基于文章内容的特征去重奠定了基础[14]。2002年，ChariKar提出Simhash算法[15]，Simhash这个算法能将一篇文章最后转换一个n位的指纹码，所有相似度比较都基于这n位指纹码进行，大大降低了计算维度。

综上所述，对于去重技术，传统的处理对象主要是网页，目前也被扩展到其他领域解决去重和聚类问题，将去重算法应用到舆情服务领域的却很少。但是大数据时代的到来，在舆情数据分析方面去重已不可忽略。本课题针对舆情数据进行去重研究，通过实现几种经典的去重算法，使用舆情样本进行测试，来观察这些算法在舆情数据方面的去重表现，最终为舆情去重在算法方面的选择提供参考资料。

2 相关理论及实现方法

2.1 特征选择

文中特征选择的范围主要是这4种：TF、特征码、TF-IDF和TextRank。这4种特征分别从不同方面反映了一个舆情文章的属性。在去重技术中，不同的特征选择将直接影响去重效果以及去重效率。

1）词频（TF）

常用的词频是指某个词在文章中出现的次数，但这种计算方式忽略了文章有长短之分，当文章篇幅差距很大，这种表示文章的属性将不能准确体现文章内容之间的差异性，因此这种词频计算方式适用于文章长短相似的文章去重，具有一定的局限性。在本文采用的是相对词频（TF），其计算公式如式（1）所示。

2）特征码

特征码一般由主码和辅码构成，主码一般是一个自然段前几个字符的组合，辅码一般是各自然段中标点符号前后几个字符的组合。文中采用的特征码仅由辅码组成。

3）TF-IDF

TF-IDF在词频的基础上，能够反映词在文章中的“重要程度”，文中利用此特征值来获取每个单词的“重要程度”。了解TF-IDF首先了解逆文档频率，这个特征的取值大小与这个词的常见程度成反比，比如最常见的词，如“的”，“在”，“这”等，这个特征值会最小。而对于不常见的词这个特征值会比较大。逆文档频率（IDF）的计算公式如式（2）所示。

词频和逆文档频率的乘积就是TF-IDF，某个词在文章中的重要程度越大，TF-IDF的值就越大。TFIDF的计算公式如式（3）所示。

4）TextRank

文中TextRank的计算对象是文本里的词语，每个词语根据此算法会得到相应的权重。计算公式如式（4）所示。

TextRank把每个词语看成一个节点（Vi），文中认为文章中全部词语都是相邻的。S（Vi）表示文本中词语的重要性，d是阻尼系数，通常设为0.85。ln（Vi）是文章中指向词语的词语集合，out（Vi）表示文章中词语指向的词语集合。

2.2 基于相似性度量的去重算法

文中选用目前去重领域中经典的去重算法进行研究，其中包括传统的去重算法Jaccard、Cosine Similarity，这两种是文本相似度比较中经典的计算方式。同时也涉及针对海量数据去重的算法Simhash、Minhash，这两种算法能够很好地降维。近年来，数据量不断增长，数据维度日渐增加，Simhash、Minhash以及其他位置敏感哈希 （LSH）的经典算法都成为研究和改进的重点算法。

1）Jaccard

Jaccard用于计算两个集合的相似程度，对于两个集合A和B，利用Jaccard计算相似度的公式如式（5）所示。计算结果越大，文章的相似度越大。

2）Cosine Similarity

Cosine用于计算样本向量之间的相似度，当把一篇文章的特征抽象成一个向量时，可以使用这种方式计算文章之间的相似度，类似几何中夹角余弦的计算方式。对于两个向量A和B，利用Cosine计算相似度的公式如（6）所示。

对于传统的Cosine Similarity的主要思想是根据一篇文章中各个词的词频来组成一个向量，通过计算两篇文章的向量夹角来判定相似度[16]。在文中将向量的构造不再局限于词频，而是采用其他更多的特征选择。计算结果越靠近1，文章的相似度越大。

3）MinHash

MinHash通过hash函数，将文章中的每个词语、关键句等映射成一个整数，从整数集合中筛选出最小的n个hash值。这样每篇文章都能抽象成一个由n个hash整数组成的集合，然后使用Jaccard计算文章间的相似度。MinHash有两种实现方法，一种是使用单个hash函数，另一种是使用多个hash函数，经实验前者特征比较时间太大，本文使用后者来与其他相似度算法进行比较。hash的对象是每个词语。

4）SimHash

文中利用SimHash将一篇文章最后转换一个32位的指纹码，然后使用海明距离来计算文章间的相似度。海明距离是指两个码字对应比特位取值不同的比特数目，例如：11001和01100从第一位开始依次有第一位、第三位、第五位不同，则海明距离为3。海明距离越大则相似度越小。本文实现SimHash的过程具体如下：

①首先将文章转换为一组加权的字符串构成的向量，这个字符串可以是词或者句。

②初始化一个32维的向量V，每个元素值都为0。

③对于文章的字符串集合中的每一个字符串进行如下运算：

将字符串利用hash函数计算后得到一个32-bit的签名。对于一个32-bit的签名，如果第k位上为1，则对向量V中第i维加上这个字符串的权值，否则减去该字符串的权值。

④完成以上全部字符串的计算后，一篇文章将被映射成一个32维向量V，然后根据每一维的符号来确定生成一个32-bit的指纹码，如果V的第i维为正数，则32-bit指纹的第i位（从左数）为1，否则为0。最终一篇文章被映射成一个32-bit指纹码。

3 实验测试及分析

整个实验的研究内容细分为两大块：特征选择方法的研究和相似度算法的研究。每个模块研究的具体内容见表1。

比较方案就是针对上表所列内容，利用3000舆情文章组合的数据集，采用先纵向比较，再交叉实验的策略。首先，每一步骤内的内容进行纵向比较，在每个步骤中，选出效果最好的1-2个算法。然后，再横向交叉组合实验，整体上选出表现突出的组合方案。考虑舆情数据服务准确度的需求，我们会优先选择误判率较低的算法。

表1 去重算法的研究内容

3.1 纵向比较特征选择算法

在纵向比较特征选择算法时，我们保持相似度算法相同，来对不同的特征选择进行测试。考虑算法实现原理，SimHash的实现过程与权值密切相关，因此相似度算法我们选择SimHash，阈值都设为2。特征选择的我们分别选用未加权、词频TF、TF-IDF、TextRank。对于特征码，其不适用此比较方法，在此保留，留在后面进行比较。

不同特征选择算法的比较结果见表2。

表2 特征选择的算法比较结果

结果分析：TextRank虽然时间复杂度太高，但其对减少误判率上有明显优势。TF-IDF在减少误判率有一定效果，在减少漏判率上也具有明显优势。词频TF虽然在减少漏判率上有较好的效果，但误判率大。

综合考虑：特征选择保留TextRank，TF-IDF。

3.2 纵向比较相似度算法

在纵向比较相似度算法时，我们只对文章进行分词操作，不对词语进行任何特征加权，并统一使用HanLP标准分词。相似度算法中参与比较的有SimHash、MinHash和Cosine。其中SimHash的阈值为2；MinHash的hash函数个数选择20，阈值为3；Cosine阈值设为0.95。对于Jaccard，其不适用此比较方法，在此保留，留在后面进行比较。

不同特征提取算法的比较结果见表3。

表3 特征提取的算法比较结果

结果分析：MinHash的误判数最小，Cosine的漏判数虽然较小，但特征比较时间相对太大，而SimHash误判数和漏判数都较多，效果太差。

综合考虑：MinHash ＞ Cosine＞SimHash，保留MinHash（误判数少）、Cosine（漏判数少）。

3.3 交叉组合比较

以上完成算法的纵向比较之后，使用纵向比较的结果再横向交叉组合实验。在交叉组合中各个算法的参数设置如下：MinHash的hash函数个数选择20，阈值为5，使用CRF分词；特征码+MinHash中特征码的长度设为5，其MinHash同样使用20个hash函数，阈值同样设为5；Jaccard的阈值设为0.2，分词使用HanLP标准分词；TextRank+Cosine阈值设为0.95，分词使用HanLP标准分词。交叉组合比较结果见表4。

表4 交叉组合比较结果

结果分析：MinHash算法误判数最少，精度最高；Jaccard算法漏判数最少，召回率最高；特征码+MinHash算法计算时间非常短。

4 结 论

优先考虑算法精度（误判数少）的情况下，推荐MinHash；优先考虑算法召回率（漏判数少）的情况下，Jaccard算法最好，但误判数较多；对运行时间有非常高要求时，推荐特征码+MinHash。

总体来说MinHash在舆情去重效果上具有一定的优势。经实验，相似度判别的阈值设置对实验结果有很大影响，在放宽MinHash阈值的情况下，MinHash能达到Jaccard同样的漏判效果。结合Hadoop优化算法特征计算和比较的时间复杂度，可以进一步提高去重效率。因此，实际应用可以结合具体业务场景，针对MinHash进行优化，使其在计算时间和漏判率上有一定的改善。

[1]中国互联网信息中心.2016年第37次中国互联网络发展状况统计报告[EB/OL].[2016].http://www.cnnic.net.cn/gywm/xwzx/rdxw/2016/201601/t20160122_53293.htm.

[2]魏超.新媒体技术发展对网络舆情信息工作的影响研究[J].图书情报工作，2014，58（1）：30-34.

[3]夏火松，甄化春.大数据环境下舆情分析与决策支持研究文献综述[J].情报杂志，2015，34（2）：1-6.

[4]贺知义.基于关键词的搜索引擎网页去重算法研究[D].湖北：华中师范大学，2015.

[5]张俊勇.基于本体的网络舆情挖掘研究[D].重庆：重庆大学，2014.

[6]陈冬.公共部门应对网络舆情对策研究 [D].上海：华东理工大学，2013.

[7]曹树金，周小又，陈桂鸿.网络舆情监控系统中的主题帖自动标引及情感倾向分析研究[J].图书情报知识，2012，32（1）：66-73.

[8]中国互联网络信息中心.第十六次中国互联网络发展状况统计报告 [EB/OL].[2016].http://www.cnnic.cn/gywm/xwzx/rdxw/2005nrd/201207/t20120710_31438.htm.

[9]李志义，梁士金.国内网页去重技术研究现状与总结[J].信息技术，2011，55（7）：118-121.

[10]卞艺杰，陈超，马玲玲，等.一种改进的LSH/MinHash协同过滤算法 [J].计算机与现代化，2013，12（12）：19-22.

[11]谭玉娟.数据备份系统中数据去重技术研究[D].武汉：华中科技大学，2012.

[12]Andrei Broder.On the resemblance and containment of documents[C]//Proceedings of the Compression and Complexity of Sequences.Washington:IEEE,1997:21-29.

[13]王洪亚，吴西送，任建军，等.分布式平台下MinHash算法研究与实现 [J].智能计算机与应用，2014，4（6）：44-46.

[14]D.Cohn,H.Chang.Learning to Probabilistically Identify Authoritative Documents[C]//Proceedings of the Seventeenth International Conference on Machine Learning.San Francisco:Morgan Kaufmann Publishers Inc，2000：167-174.

[15]Charikar M.S.Similarity Estimation Techniques from Algorithms[C]//Proceeding of the 34th annual ACM Symposium on theory of computing.NewYork.NY.USA:AACM,2002:380-388.

[16]王源.一种基于Simhash的文本快速去重算法[D].吉林：吉林大学，2014.

Research and comparison on duplication deletion algorithm of public opinion

ZHANG Qing-mei（School of Software Engineering of USTC，Suzhou 215123，China）

In recent years，public opinion information is processed and used in the big data serviceswidely，but those operation such as copying，reproducing make the repetitionof the collection of public opinion information hugeand make post-processingbecome very difficult.In this situation，there is relativelyless about study on the on duplication deletion of public opinion.Althoughit is inevitable for big data services to remove the duplication of public opinion，it lacks theoretical guidance.Therefore，in this paper，throughstudying onthe classical duplication deletion algorithmsuch asSimHash，MinHash，Jaccard，and combining the algorithmwithdifferent feature selection algorithm such as TF，TF-IDF，feature code and3000 public opinion sample to make a series of experiments.Finally resultsshow that MinHash combined with feature code have the shortest running time，Jaccard have the least number of missed article and the recall rate can reach more than 90%，MinHash have the least number of mistakes and accuracycan reach 100%，furthermore，MinHash can get the same recall rate by adjusting threshold.

public opinion data； duplication deletion algorithm； feature selection； similarity computing；big data service

TP391

：A

：1674－6236（2017）14-0023-05

2016-05-04稿件编号：201605015

张庆梅（1992—），女，安徽阜阳人，硕士研究生。研究方向：软件系统设计。