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

張慶梅

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

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

張慶梅

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

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

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

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

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

1 相關(guān)工作

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

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

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

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

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

2.1 特征選擇

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

1）詞頻（TF）

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

2）特征碼

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

3）TF-IDF

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

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

4）TextRank

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

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

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

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

1）Jaccard

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

2）Cosine Similarity

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

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

3）MinHash

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

4）SimHash

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

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

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

③對(duì)于文章的字符串集合中的每一個(gè)字符串進(jìn)行如下運(yùn)算：

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

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

3 實(shí)驗(yàn)測(cè)試及分析

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

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

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

3.1 縱向比較特征選擇算法

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

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

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

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

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

3.2 縱向比較相似度算法

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

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

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

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

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

3.3 交叉組合比較

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

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

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

4 結(jié) 論

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

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

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

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

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

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

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

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

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

[8]中國互聯(lián)網(wǎng)絡(luò)信息中心.第十六次中國互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計(jì)報(bào)告 [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]卞藝杰，陳超，馬玲玲，等.一種改進(jìn)的LSH/MinHash協(xié)同過濾算法 [J].計(jì)算機(jī)與現(xiàn)代化，2013，12（12）：19-22.

[11]譚玉娟.數(shù)據(jù)備份系統(tǒng)中數(shù)據(jù)去重技術(shù)研究[D].武漢：華中科技大學(xué)，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]王洪亞，吳西送，任建軍，等.分布式平臺(tái)下MinHash算法研究與實(shí)現(xiàn) [J].智能計(jì)算機(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].吉林：吉林大學(xué)，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稿件編號(hào)：201605015

張慶梅（1992—），女，安徽阜陽人，碩士研究生。研究方向：軟件系統(tǒng)設(shè)計(jì)。