張慶梅

（中國科學技術(shù)大學 軟件學院，江蘇 蘇州215123）

輿情去重算法的研究與比較

張慶梅

（中國科學技術(shù)大學 軟件學院，江蘇 蘇州215123）

近年來，輿情信息在大數(shù)據(jù)服務(wù)中廣泛被加工使用，但轉(zhuǎn)載、復(fù)制等操作使得采集的輿情信息重復(fù)量龐大，給后期的加工帶來困難。在這種情況下，針對輿情數(shù)據(jù)開展去重研究的卻相對較少。文中針對輿情去重不可避免但缺乏理論指導(dǎo)的問題，通過研究SimHash、MinHash、Jaccard等經(jīng)典去重算法，結(jié)合TF、TF-IDF、特征碼等不同特征選擇和3 000輿情樣本進行實驗，最終發(fā)現(xiàn)MinHash+特征碼運行時間最短；Jaccard的漏判數(shù)最少，召回率可達90%以上；MinHash算法的誤判數(shù)最少，去重精度可達100%，并且MinHash通過閾值的調(diào)整能夠獲得Jaccard同樣的召回率。

輿情數(shù)據(jù)；去重算法；特征選擇；相似度計算；大數(shù)據(jù)服務(wù)

截至2015年12月，我國社交網(wǎng)站、微博等社交應(yīng)用的網(wǎng)民使用率達77.0%[1]，新媒體的迅捷性、開放性和方便性使得越來越多的網(wǎng)民使用其表達自己的意見和看法[2]。各種新媒體的出現(xiàn)，使得輿論信息傳播范圍更廣、速度更快、數(shù)量更大，輿情對社會經(jīng)濟影響也越來越大。西蒙曾指出：在信息時代，最稀缺的資源不再是信息本身，而是對信息的處理能力。目前大數(shù)據(jù)服務(wù)公司利用互聯(lián)網(wǎng)技術(shù)，收集有關(guān)輿情信息，再加工分析，為銀行、信托等金融機構(gòu)提供企業(yè)、個人的輿情數(shù)據(jù)，為其評估客戶信用、預(yù)估客戶風險、預(yù)測金融發(fā)展趨勢提供參考。此外對金融輿情信息進行分析，能夠?qū)鹑谶\行的形式和趨勢做出預(yù)測和判斷，方便引導(dǎo)輿情基于真實信息向有利于金融穩(wěn)定運行的方向發(fā)展[3]。但內(nèi)容復(fù)制、轉(zhuǎn)載等原因，互聯(lián)網(wǎng)上存在大量的相似重復(fù)網(wǎng)頁信息[4]，致使數(shù)據(jù)收集階段獲得的數(shù)據(jù)往往重復(fù)嚴重。這些重復(fù)的輿情數(shù)據(jù)一方面加大了后期人工運營的強度。另一方面影響數(shù)據(jù)服務(wù)質(zhì)量，增大數(shù)據(jù)存儲難度，降低索引效率，嚴重影響輿情價值的發(fā)揮。

文中針對輿情去重進行研究，分析SimHash、MinHash、Cosine Similarity、Jaccard 基于相似性度量的去重原理，對輿情數(shù)據(jù)文本的 TF、TF-IDF、TextRank和特征碼進行提取，使用不同方式將特征選擇與相似性計算方式進行結(jié)合，編程實現(xiàn)各個去重算法。確定合理高效的測試方案，利用3 000輿情數(shù)據(jù)樣本進行測試，獲取各個算法在輿情去重方面的測試結(jié)果，比較分析。實驗成果將在輿情數(shù)據(jù)去重方面為人們在進行算法選擇時提供決策參考。

1 相關(guān)工作

就輿情研究而言，國外起步較早，從19世紀中期開始發(fā)展，到20世紀中期已逐漸走向成熟。我國對網(wǎng)絡(luò)輿情的研究，直到20世紀末才剛剛開始[5]。整體上對輿情的研究主要集中于這兩個方面，一是收集和分析輿情信息進行輿情對策，來幫助政府或企業(yè)有效地應(yīng)對輿情節(jié)拍緩慢和極端化等問題[6]。二是基于信息技術(shù)的輿情監(jiān)測和輿情挖掘研究，依托計算機和網(wǎng)絡(luò)技術(shù)建構(gòu)監(jiān)測、分析和預(yù)警系統(tǒng)[7]。大數(shù)據(jù)時代的來臨，越來越依賴輿情大數(shù)據(jù)分析技術(shù)，而面對如此龐大的數(shù)據(jù)，大數(shù)據(jù)在進行分析之前必須對數(shù)據(jù)進行清洗工作，其中清洗環(huán)節(jié)的一個重要工作就是去除重復(fù)數(shù)據(jù)。

就去重算法而言，其主要應(yīng)用于搜索引擎。據(jù)統(tǒng)計，用戶在回答“檢索信息時遇到的最大問題”這一提問時，選擇“重復(fù)信息太多”選項的占44.6%，排名第1位[8]。因此在搜索引擎方面，解決網(wǎng)頁重復(fù)的問題是必不可少的步驟，網(wǎng)頁去重技術(shù)蘊含于信息搜索技術(shù)，是后者發(fā)展的有力支撐[9]。此外去重的開展是基于相似度的計算，因此去重技術(shù)的基本算法也被應(yīng)用于解決高維數(shù)據(jù)的聚類問題。例如利用基于LSH算法協(xié)同過濾處理高維數(shù)據(jù)的良好特性來解決圖書館用戶的聚類問題[10]。近年來，隨著存儲容量快速增長，去重技術(shù)也被應(yīng)用于數(shù)據(jù)備份系統(tǒng)來消除冗余數(shù)據(jù)，降低數(shù)據(jù)存儲成本[11]。

國外在去重方面的研究開始于19世紀，去重算法的應(yīng)用也比國內(nèi)成熟。目前許多去重算法都是在最初提出的算法的基礎(chǔ)上進行改進。1997年，Andrei Broder首次提出MinHash算法[12]，該算法可以用來快速估算兩個集合的相似度，查找網(wǎng)絡(luò)上的重復(fù)網(wǎng)頁或者相似新聞網(wǎng)頁[13]。在2000年，Peter.D.Turney首次提出關(guān)鍵字提取算法，將文章中出現(xiàn)的詞語劃分為關(guān)鍵和非關(guān)鍵兩部分，從關(guān)鍵類中選擇若干個作為關(guān)鍵詞。這個方法的提出為基于文章內(nèi)容的特征去重奠定了基礎(chǔ)[14]。2002年，ChariKar提出Simhash算法[15]，Simhash這個算法能將一篇文章最后轉(zhuǎn)換一個n位的指紋碼，所有相似度比較都基于這n位指紋碼進行，大大降低了計算維度。

綜上所述，對于去重技術(shù)，傳統(tǒng)的處理對象主要是網(wǎng)頁，目前也被擴展到其他領(lǐng)域解決去重和聚類問題，將去重算法應(yīng)用到輿情服務(wù)領(lǐng)域的卻很少。但是大數(shù)據(jù)時代的到來，在輿情數(shù)據(jù)分析方面去重已不可忽略。本課題針對輿情數(shù)據(jù)進行去重研究，通過實現(xiàn)幾種經(jīng)典的去重算法，使用輿情樣本進行測試，來觀察這些算法在輿情數(shù)據(jù)方面的去重表現(xiàn)，最終為輿情去重在算法方面的選擇提供參考資料。

2 相關(guān)理論及實現(xiàn)方法

2.1 特征選擇

文中特征選擇的范圍主要是這4種：TF、特征碼、TF-IDF和TextRank。這4種特征分別從不同方面反映了一個輿情文章的屬性。在去重技術(shù)中，不同的特征選擇將直接影響去重效果以及去重效率。

1）詞頻（TF）

常用的詞頻是指某個詞在文章中出現(xiàn)的次數(shù)，但這種計算方式忽略了文章有長短之分，當文章篇幅差距很大，這種表示文章的屬性將不能準確體現(xiàn)文章內(nèi)容之間的差異性，因此這種詞頻計算方式適用于文章長短相似的文章去重，具有一定的局限性。在本文采用的是相對詞頻（TF），其計算公式如式（1）所示。

2）特征碼

特征碼一般由主碼和輔碼構(gòu)成，主碼一般是一個自然段前幾個字符的組合，輔碼一般是各自然段中標點符號前后幾個字符的組合。文中采用的特征碼僅由輔碼組成。

3）TF-IDF

TF-IDF在詞頻的基礎(chǔ)上，能夠反映詞在文章中的“重要程度”，文中利用此特征值來獲取每個單詞的“重要程度”。了解TF-IDF首先了解逆文檔頻率，這個特征的取值大小與這個詞的常見程度成反比，比如最常見的詞，如“的”，“在”，“這”等，這個特征值會最小。而對于不常見的詞這個特征值會比較大。逆文檔頻率（IDF）的計算公式如式（2）所示。

詞頻和逆文檔頻率的乘積就是TF-IDF，某個詞在文章中的重要程度越大，TF-IDF的值就越大。TFIDF的計算公式如式（3）所示。

4）TextRank

文中TextRank的計算對象是文本里的詞語，每個詞語根據(jù)此算法會得到相應(yīng)的權(quán)重。計算公式如式（4）所示。

TextRank把每個詞語看成一個節(jié)點（Vi），文中認為文章中全部詞語都是相鄰的。S（Vi）表示文本中詞語的重要性，d是阻尼系數(shù)，通常設(shè)為0.85。ln（Vi）是文章中指向詞語的詞語集合，out（Vi）表示文章中詞語指向的詞語集合。

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

文中選用目前去重領(lǐng)域中經(jīng)典的去重算法進行研究，其中包括傳統(tǒng)的去重算法Jaccard、Cosine Similarity，這兩種是文本相似度比較中經(jīng)典的計算方式。同時也涉及針對海量數(shù)據(jù)去重的算法Simhash、Minhash，這兩種算法能夠很好地降維。近年來，數(shù)據(jù)量不斷增長，數(shù)據(jù)維度日漸增加，Simhash、Minhash以及其他位置敏感哈希 （LSH）的經(jīng)典算法都成為研究和改進的重點算法。

1）Jaccard

Jaccard用于計算兩個集合的相似程度，對于兩個集合A和B，利用Jaccard計算相似度的公式如式（5）所示。計算結(jié)果越大，文章的相似度越大。

2）Cosine Similarity

Cosine用于計算樣本向量之間的相似度，當把一篇文章的特征抽象成一個向量時，可以使用這種方式計算文章之間的相似度，類似幾何中夾角余弦的計算方式。對于兩個向量A和B，利用Cosine計算相似度的公式如（6）所示。

對于傳統(tǒng)的Cosine Similarity的主要思想是根據(jù)一篇文章中各個詞的詞頻來組成一個向量，通過計算兩篇文章的向量夾角來判定相似度[16]。在文中將向量的構(gòu)造不再局限于詞頻，而是采用其他更多的特征選擇。計算結(jié)果越靠近1，文章的相似度越大。

3）MinHash

MinHash通過hash函數(shù)，將文章中的每個詞語、關(guān)鍵句等映射成一個整數(shù)，從整數(shù)集合中篩選出最小的n個hash值。這樣每篇文章都能抽象成一個由n個hash整數(shù)組成的集合，然后使用Jaccard計算文章間的相似度。MinHash有兩種實現(xiàn)方法，一種是使用單個hash函數(shù)，另一種是使用多個hash函數(shù)，經(jīng)實驗前者特征比較時間太大，本文使用后者來與其他相似度算法進行比較。hash的對象是每個詞語。

4）SimHash

文中利用SimHash將一篇文章最后轉(zhuǎn)換一個32位的指紋碼，然后使用海明距離來計算文章間的相似度。海明距離是指兩個碼字對應(yīng)比特位取值不同的比特數(shù)目，例如：11001和01100從第一位開始依次有第一位、第三位、第五位不同，則海明距離為3。海明距離越大則相似度越小。本文實現(xiàn)SimHash的過程具體如下：

①首先將文章轉(zhuǎn)換為一組加權(quán)的字符串構(gòu)成的向量，這個字符串可以是詞或者句。

②初始化一個32維的向量V，每個元素值都為0。

③對于文章的字符串集合中的每一個字符串進行如下運算：

將字符串利用hash函數(shù)計算后得到一個32-bit的簽名。對于一個32-bit的簽名，如果第k位上為1，則對向量V中第i維加上這個字符串的權(quán)值，否則減去該字符串的權(quán)值。

④完成以上全部字符串的計算后，一篇文章將被映射成一個32維向量V，然后根據(jù)每一維的符號來確定生成一個32-bit的指紋碼，如果V的第i維為正數(shù)，則32-bit指紋的第i位（從左數(shù)）為1，否則為0。最終一篇文章被映射成一個32-bit指紋碼。

3 實驗測試及分析

整個實驗的研究內(nèi)容細分為兩大塊：特征選擇方法的研究和相似度算法的研究。每個模塊研究的具體內(nèi)容見表1。

比較方案就是針對上表所列內(nèi)容，利用3000輿情文章組合的數(shù)據(jù)集，采用先縱向比較，再交叉實驗的策略。首先，每一步驟內(nèi)的內(nèi)容進行縱向比較，在每個步驟中，選出效果最好的1-2個算法。然后，再橫向交叉組合實驗，整體上選出表現(xiàn)突出的組合方案?？紤]輿情數(shù)據(jù)服務(wù)準確度的需求，我們會優(yōu)先選擇誤判率較低的算法。

表1 去重算法的研究內(nèi)容

3.1 縱向比較特征選擇算法

在縱向比較特征選擇算法時，我們保持相似度算法相同，來對不同的特征選擇進行測試?？紤]算法實現(xiàn)原理，SimHash的實現(xiàn)過程與權(quán)值密切相關(guān)，因此相似度算法我們選擇SimHash，閾值都設(shè)為2。特征選擇的我們分別選用未加權(quán)、詞頻TF、TF-IDF、TextRank。對于特征碼，其不適用此比較方法，在此保留，留在后面進行比較。

不同特征選擇算法的比較結(jié)果見表2。

表2 特征選擇的算法比較結(jié)果

結(jié)果分析：TextRank雖然時間復(fù)雜度太高，但其對減少誤判率上有明顯優(yōu)勢。TF-IDF在減少誤判率有一定效果，在減少漏判率上也具有明顯優(yōu)勢。詞頻TF雖然在減少漏判率上有較好的效果，但誤判率大。

綜合考慮：特征選擇保留TextRank，TF-IDF。

3.2 縱向比較相似度算法

在縱向比較相似度算法時，我們只對文章進行分詞操作，不對詞語進行任何特征加權(quán)，并統(tǒng)一使用HanLP標準分詞。相似度算法中參與比較的有SimHash、MinHash和Cosine。其中SimHash的閾值為2；MinHash的hash函數(shù)個數(shù)選擇20，閾值為3；Cosine閾值設(shè)為0.95。對于Jaccard，其不適用此比較方法，在此保留，留在后面進行比較。

不同特征提取算法的比較結(jié)果見表3。

表3 特征提取的算法比較結(jié)果

結(jié)果分析：MinHash的誤判數(shù)最小，Cosine的漏判數(shù)雖然較小，但特征比較時間相對太大，而SimHash誤判數(shù)和漏判數(shù)都較多，效果太差。

綜合考慮：MinHash ＞ Cosine＞SimHash，保留MinHash（誤判數(shù)少）、Cosine（漏判數(shù)少）。

3.3 交叉組合比較

以上完成算法的縱向比較之后，使用縱向比較的結(jié)果再橫向交叉組合實驗。在交叉組合中各個算法的參數(shù)設(shè)置如下：MinHash的hash函數(shù)個數(shù)選擇20，閾值為5，使用CRF分詞；特征碼+MinHash中特征碼的長度設(shè)為5，其MinHash同樣使用20個hash函數(shù)，閾值同樣設(shè)為5；Jaccard的閾值設(shè)為0.2，分詞使用HanLP標準分詞；TextRank+Cosine閾值設(shè)為0.95，分詞使用HanLP標準分詞。交叉組合比較結(jié)果見表4。

表4 交叉組合比較結(jié)果

結(jié)果分析：MinHash算法誤判數(shù)最少，精度最高；Jaccard算法漏判數(shù)最少，召回率最高；特征碼+MinHash算法計算時間非常短。

4 結(jié) 論

優(yōu)先考慮算法精度（誤判數(shù)少）的情況下，推薦MinHash；優(yōu)先考慮算法召回率（漏判數(shù)少）的情況下，Jaccard算法最好，但誤判數(shù)較多；對運行時間有非常高要求時，推薦特征碼+MinHash。

總體來說MinHash在輿情去重效果上具有一定的優(yōu)勢。經(jīng)實驗，相似度判別的閾值設(shè)置對實驗結(jié)果有很大影響，在放寬MinHash閾值的情況下，MinHash能達到Jaccard同樣的漏判效果。結(jié)合Hadoop優(yōu)化算法特征計算和比較的時間復(fù)雜度，可以進一步提高去重效率。因此，實際應(yīng)用可以結(jié)合具體業(yè)務(wù)場景，針對MinHash進行優(yōu)化，使其在計算時間和漏判率上有一定的改善。

[1]中國互聯(lián)網(wǎng)信息中心.2016年第37次中國互聯(lián)網(wǎng)絡(luò)發(fā)展狀況統(tǒng)計報告[EB/OL].[2016].http://www.cnnic.net.cn/gywm/xwzx/rdxw/2016/201601/t20160122_53293.htm.

[2]魏超.新媒體技術(shù)發(fā)展對網(wǎng)絡(luò)輿情信息工作的影響研究[J].圖書情報工作，2014，58（1）：30-34.

[3]夏火松，甄化春.大數(shù)據(jù)環(huán)境下輿情分析與決策支持研究文獻綜述[J].情報雜志，2015，34（2）：1-6.

[4]賀知義.基于關(guān)鍵詞的搜索引擎網(wǎng)頁去重算法研究[D].湖北：華中師范大學，2015.

[5]張俊勇.基于本體的網(wǎng)絡(luò)輿情挖掘研究[D].重慶：重慶大學，2014.

[6]陳冬.公共部門應(yīng)對網(wǎng)絡(luò)輿情對策研究 [D].上海：華東理工大學，2013.

[7]曹樹金，周小又，陳桂鴻.網(wǎng)絡(luò)輿情監(jiān)控系統(tǒng)中的主題帖自動標引及情感傾向分析研究[J].圖書情報知識，2012，32（1）：66-73.

[8]中國互聯(lián)網(wǎng)絡(luò)信息中心.第十六次中國互聯(lián)網(wǎng)絡(luò)發(fā)展狀況統(tǒng)計報告 [EB/OL].[2016].http://www.cnnic.cn/gywm/xwzx/rdxw/2005nrd/201207/t20120710_31438.htm.

[9]李志義，梁士金.國內(nèi)網(wǎng)頁去重技術(shù)研究現(xiàn)狀與總結(jié)[J].信息技術(shù)，2011，55（7）：118-121.

[10]卞藝杰，陳超，馬玲玲，等.一種改進的LSH/MinHash協(xié)同過濾算法 [J].計算機與現(xiàn)代化，2013，12（12）：19-22.

[11]譚玉娟.數(shù)據(jù)備份系統(tǒng)中數(shù)據(jù)去重技術(shù)研究[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算法研究與實現(xiàn) [J].智能計算機與應(yīng)用，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—），女，安徽阜陽人，碩士研究生。研究方向：軟件系統(tǒng)設(shè)計。