張慶梅

(中國科學(xué)技術(shù)大學(xué) 軟件學(xué)院,蘇州 215123)

針對(duì)輿情數(shù)據(jù)的去重算法①

張慶梅

(中國科學(xué)技術(shù)大學(xué) 軟件學(xué)院,蘇州 215123)

針對(duì)在數(shù)據(jù)服務(wù)中輿情去重不可避免且缺乏理論指導(dǎo)的問題,通過研究SimHash、MinHash、Jaccard、Cosine Similarty經(jīng)典去重算法,以及常見的分詞和特征選擇算法,以尋求表現(xiàn)優(yōu)異的算法搭配,并對(duì)傳統(tǒng)Jaccard和SimHash進(jìn)行了改進(jìn)分別產(chǎn)生新算法:基于短文章的Jaccard和基于Cosine Distance的SimHash.針對(duì)比較對(duì)象眾多實(shí)驗(yàn)效率低下的問題,提出了先縱向比較篩選出優(yōu)勢算法,然后橫向比較獲得最佳搭配,最后綜合比較的策略,并結(jié)合3000輿情樣本實(shí)驗(yàn)證明:改進(jìn)的SimHash比傳統(tǒng)的SimHash具有更高的精度和召回率;改進(jìn)的Jaccard較傳統(tǒng)Jaccard,召回率提高了17%,效率提高了50%;MinHash+結(jié)巴全模式分詞和Jaccard+IKAnalyzer智能分詞在保持精度高于96%的條件下,都具有75%以上的高召回率,且穩(wěn)定性很好.其中MinHash去重效果略低于Jaccard,但特征比較時(shí)間較短,綜合表現(xiàn)最好.

輿情數(shù)據(jù);去重算法;相似度計(jì)算;大數(shù)據(jù)服務(wù)

據(jù)中國互聯(lián)網(wǎng)絡(luò)信息中心統(tǒng)計(jì),截止到2015年12月,我國社交網(wǎng)站、微博等社交應(yīng)用的網(wǎng)民使用率達(dá)77.0%[1],新媒體逐漸成為網(wǎng)民表達(dá)意見和看法、行使公民權(quán)利的重要渠道和方式[2],是用戶獲取和分享“新聞熱點(diǎn)”、“興趣內(nèi)容”、“專業(yè)知識(shí)”、“輿論導(dǎo)向”的重要平臺(tái)[3].從社會(huì)學(xué)角度來看,這些輿情信息反映了民眾的社會(huì)政治態(tài)度,有著強(qiáng)大的監(jiān)督力度[4].而輿情信息的價(jià)值遠(yuǎn)遠(yuǎn)不止其傳播性所帶來的社會(huì)監(jiān)督力度,在金融領(lǐng)域也廣泛被使用.由于輿情信息可以準(zhǔn)確反映個(gè)人和企業(yè)的信用狀況,目前已有大數(shù)據(jù)服務(wù)公司采集輿情數(shù)據(jù),然后加工分析為金融機(jī)構(gòu)在信用評(píng)定、風(fēng)險(xiǎn)評(píng)估方面提高參考.然而隨著大數(shù)據(jù)時(shí)代的到來,抓取的輿情數(shù)據(jù)重復(fù)性冗余急劇增大[5],這些重復(fù)的數(shù)據(jù)嚴(yán)重影響后期的加工處理和客戶體驗(yàn).據(jù)調(diào)研,目前的去重技術(shù)大多針對(duì)網(wǎng)頁,專門針對(duì)輿情數(shù)據(jù)的卻很少.因此對(duì)于輿情數(shù)據(jù)服務(wù),迫切需要針對(duì)輿情開展去重研究來解決數(shù)據(jù)重復(fù)帶來的一系列問題.本文通過對(duì)幾種經(jīng)典去重算法在輿情數(shù)據(jù)方面的表現(xiàn)進(jìn)行研究,并分析不同實(shí)現(xiàn)方式的去重算法之間的精度、召回率和效率的差異,尋求在輿情去重上表現(xiàn)優(yōu)異的算法,為輿情數(shù)據(jù)服務(wù)在機(jī)器去重方面提供參考.

1 相關(guān)技術(shù)和實(shí)現(xiàn)方法

本文將整個(gè)去重分為三個(gè)步驟:首先是分詞,將一篇文章轉(zhuǎn)化為詞語列表;然后是對(duì)文章進(jìn)行特征選擇,實(shí)現(xiàn)文章特征屬性的提取;最后是基于相似度計(jì)算的去重算法進(jìn)行去重.因此關(guān)鍵技術(shù)包括分詞、特征選擇、相似度計(jì)算.每種技術(shù)中本文都有多種候選算法,相關(guān)技術(shù)的研究對(duì)象如表1所示.

表1 相關(guān)技術(shù)的研究對(duì)象

1.1 分詞

本文的分詞具體指中文分詞,目的是將漢字序列切分成由詞語組成的序列[6].分詞算法的不同將直接影響去重效果.本文嘗試通過比較不同分詞算法對(duì)輿情去重效果的影響,來獲得最適合輿情去重的分詞方法.本文選用中文分詞中比較常用的3種分詞方法:結(jié)巴分詞、IKAnalyzer分詞和HanLP分詞,其中結(jié)巴分詞包含3種模式:精確模式、全模式和搜索引擎模式.IKAnalyzer包含2種分詞模式:細(xì)粒度模式和智能模式.HanLP包含8個(gè)分詞器:標(biāo)準(zhǔn)分詞、NLP分詞、索引分詞、N最短路徑分詞、最短路徑分詞、CRF分詞、極速詞典分詞和繁體分詞.由于本文的輿情樣本全部是簡體中文,因此本文只將前7種分詞納入此后的研究中去.

1.2 特征選擇

選用較小維度的特征代表整個(gè)文本正文的過程就是特征選擇.在本文中將幾種常見的特征選擇納入研究范圍,分別是:詞頻、TF-IDF和TextRank.這三種特征選擇都是權(quán)重特征,適合與Cosine Similarity和SimHash算法結(jié)合使用.

1.2.1 詞頻

詞頻是指詞語出現(xiàn)的次數(shù),詞頻統(tǒng)計(jì)通常不單獨(dú)被使用,一般是結(jié)合其他算法一起使用,應(yīng)用范圍涉及中文分詞、研究熱點(diǎn)分析、文本分析等諸多方面[7-9].常用詞頻的計(jì)算方式是獲取某個(gè)詞在文章中出現(xiàn)的次數(shù),但這種計(jì)算方式忽略了文章有長短之分.當(dāng)文章篇幅差距很大,將不能準(zhǔn)確體現(xiàn)文章內(nèi)容之間的差異性.因此在本文采用的是相對(duì)詞頻,它對(duì)的計(jì)算公式如式(1)所示.

1.2.2 TF-IDF

TF-IDF和詞頻同樣都是常用的加權(quán)技術(shù),但相比于詞頻,TF-IDF能夠反映整個(gè)詞在一個(gè)文本集合或者語料庫中的“重要程度”,詞頻僅僅在一定程度上反映一個(gè)詞在一篇文章的重要程度,沒有將整個(gè)文本庫的大小考慮進(jìn)去.TF-IDF廣泛應(yīng)用于自動(dòng)關(guān)鍵詞提取、文本摘要提取等[10,11].TF-IDF的主要思想是詞語的重要性隨著這個(gè)詞在文本出現(xiàn)的次數(shù)成正比,同時(shí)隨著它在整個(gè)文本集合中出現(xiàn)的頻率成反比,某個(gè)詞在文章中的重要程度越大,TF-IDF的值就越大.了解TF-IDF首先了解逆文檔頻率,詞頻和逆文檔頻率的乘積就是TF-IDF,逆文檔頻率(IDF)的計(jì)算公式如式(2)所示.

1.2.3 TextRank

TextRank是受啟發(fā)于PageRank,PageRank最開始是用于網(wǎng)頁相關(guān)性和重要性的評(píng)估,獲取網(wǎng)頁排序,提高用戶對(duì)搜索引擎檢索結(jié)果的滿意度,此算法由Google的創(chuàng)始人謝爾蓋?布林和拉里?佩奇在1998年提出[12].PageRank的計(jì)算公式如式(3)所示.

S(Vi)表示網(wǎng)頁i的重要性,d是阻尼系數(shù),通常設(shè)為0.85.In(Vi)是指向網(wǎng)頁i的鏈接集合,Out(Vi)表示網(wǎng)頁i指向的網(wǎng)頁集合,|Out(Vi)|表示網(wǎng)頁i指向的網(wǎng)頁集合的元素個(gè)數(shù).整個(gè)計(jì)算需要經(jīng)過多次迭代,初始設(shè)置網(wǎng)頁重要性為1.

TextRank計(jì)算對(duì)象從網(wǎng)頁轉(zhuǎn)化為文本中的詞語或者句子,每個(gè)詞語或句子根據(jù)此算法會(huì)得到相應(yīng)的權(quán)重.具體計(jì)算公式如式(4)所示.

本文利用此特征選擇主要是獲取不同詞語的權(quán)重值,即把每個(gè)詞語看成一個(gè)節(jié)點(diǎn)(Vi).當(dāng)計(jì)算對(duì)象是詞語時(shí),因?yàn)?wjk取值都為 1,TextRank就蛻變成PageRank.不過式4中的變量含義有所變化,S(Vi)表示文本中詞語i的重要性,In(Vi)是文章中指向詞語i的詞語集合,|Out(Vi)|表示文章中詞語i指向的詞語集合的元素個(gè)數(shù).詞語之間的相鄰關(guān)系,依賴于窗口大小的設(shè)置,一個(gè)窗口中的任意兩個(gè)詞語之間都是相鄰的,并且邊都是無向無權(quán)的.由于TextRank需要經(jīng)過多次迭代,因此特征獲取的時(shí)間復(fù)雜度很高.

1.3 相似度計(jì)算

相似度計(jì)算是指是在特征選擇的基礎(chǔ)上通過去重算法來求取文章之間相似度的過程,是自然語言處理和數(shù)據(jù)挖掘中常用的操作.本文參考網(wǎng)頁去重的經(jīng)典算法,將 Jaccard、Cosine Similarity、SimHash和MinHash納入研究范圍,對(duì)于傳統(tǒng)實(shí)現(xiàn)方式, MinHash有兩種:基于單Hash函數(shù)的MinHash算法和基于多Hash函數(shù)的MinHash算法,其余的各有一種.本文除了實(shí)現(xiàn)傳統(tǒng)的算法之外,還對(duì)傳統(tǒng)Jaccard和SimHash進(jìn)行改進(jìn)分別產(chǎn)生新的算法:基于短文章的Jaccard和基于Cosine Distance的SimHash.

2 基于相似度計(jì)算的去重算法

對(duì)于不同的應(yīng)用場景,考慮到數(shù)據(jù)規(guī)模、時(shí)間開銷,去重算法的選擇會(huì)有所不同.本文在此分析不同算法的去重原理以及時(shí)間開銷,從理論上分析不同算法的優(yōu)缺點(diǎn),并給出具體的實(shí)現(xiàn)步驟.為不同需求的應(yīng)用場景在去重算法的選擇上提供參考.

2.1 Jaccard算法

Jaccard系數(shù),又稱Jaccard相似度系數(shù),用來評(píng)估兩個(gè)集合之間的相似度和分散度[13],Jaccard系數(shù)越大表明兩篇文章的相似度越大.利用Jaccard去重,首先將文章通過分詞轉(zhuǎn)化為由詞語構(gòu)成的特征集合,通過檢查兩個(gè)集合的Jaccard系數(shù)是否超過指定的閾值來判斷文章是否重復(fù).

1)傳統(tǒng)的Jaccard

傳統(tǒng)的Jaccard,基于Merge算法,通過求取兩個(gè)文章的特征集合交集和并集的長度比例來衡量文章之間的距離.計(jì)算公式如式(5)所示.

從實(shí)現(xiàn)的原理上看,傳統(tǒng)的Jaccard算法,并沒有將兩篇文章的長度差異考慮進(jìn)去,假設(shè)兩篇文章重復(fù)的文章長度差異很大,例如一個(gè)包含1500個(gè)單詞,一個(gè)包含500個(gè)單詞,兩篇文章的單詞交集長度是500,利用傳統(tǒng)的Jaccard計(jì)算兩篇文章距離,結(jié)果是:0.25,傳統(tǒng) Jaccard的閾值一般在0.5以上,在這種情況下,就很容易漏判長度差異大的重復(fù)文章.此外Merge算法的時(shí)間復(fù)雜度是O(m+n)(m和n是兩個(gè)集合的長度),不是很高,但當(dāng)文章篇幅很長,數(shù)據(jù)規(guī)模很大時(shí),這個(gè)時(shí)間開銷將會(huì)非常龐大.因此Jaccard算法不適應(yīng)文章篇幅普遍較長、數(shù)據(jù)規(guī)模較大的業(yè)務(wù)場景.

2)基于短文章的Jaccard

針對(duì)傳統(tǒng)Jaccard對(duì)屬于包含關(guān)系重復(fù)的文章識(shí)別能力低的問題,本文提出一種基于短文章的Jaccard,通過求取兩個(gè)特征集合交集占短文章集合長度的比例來衡量兩文章的距離.以下簡稱改進(jìn)的Jaccard,計(jì)算公式如式(6)所示.

在這種改進(jìn)下,屬于包含關(guān)系的重復(fù)文章,即使文章長度差異很大,求取的文章Jaccard系數(shù)也會(huì)隨文章相似程度的增大而增大.對(duì)于傳統(tǒng)Jaccard中的例子,使用改進(jìn)的Jaccard計(jì)算,兩篇文章的距離就是1,即完全重復(fù),符合實(shí)際情況.改進(jìn)的Jaccard的時(shí)間復(fù)雜度和傳統(tǒng)Jaccard相同,但是相比傳統(tǒng)的Jaccard少了求并集的過程,因此時(shí)間消耗要少.

2.2 Cosine Similarity算法

Cosine Similarity又稱Cosine Distance,與幾何中的向量余弦夾角很相似.當(dāng)把一篇文章的特征抽象成一個(gè)向量時(shí),可以使用這種方式計(jì)算文章之間的相似度,計(jì)算公式如式(7)所示.

具體實(shí)現(xiàn)步驟如下:

對(duì)于Step 3向量坐標(biāo)的轉(zhuǎn)化,需要遍歷集合unionS中的元素,并依次判斷每個(gè)元素在待轉(zhuǎn)化向量中的存在情況,因此整個(gè)相似度計(jì)算的時(shí)間復(fù)雜度平均為O(n*m)(n為并集的長度,m為待轉(zhuǎn)化向量的長度),相比于Jaccard,時(shí)間開銷更大.

2.3 SimHash算法

SimHash是由Charikar在2002年提出的去重算法,主要用于海量文本的去重工作[14].SimHash對(duì)文章進(jìn)行相似度計(jì)算,需要兩步,首先特征提取形成指紋,然后根據(jù)指紋進(jìn)行特征比較,計(jì)算相似度.

1)傳統(tǒng)的SimHash

傳統(tǒng)的SimHash首先將一篇文章轉(zhuǎn)化為由k位0/1構(gòu)成的指紋(k通常取32或64),然后利用Hamming Distance(海明距離)來對(duì)兩篇文章的指紋進(jìn)行相似計(jì)算.海明距離是指兩串二進(jìn)制編碼對(duì)應(yīng)比特位取值不同的比特?cái)?shù)目,海明距離越大則相似度越小.由于SimHash能將一篇文章轉(zhuǎn)化為k位的字符,相比于Jaccard和Cosine Similarity,能大大降低特征比較的維度.雖然多了特征提取的步驟,但對(duì)于大數(shù)據(jù)服務(wù),一篇文章只需在入庫時(shí)進(jìn)行一次特征提取,然后將形成的指紋保存下來,而特征比較會(huì)在每次去重時(shí)都要基于指紋進(jìn)行多次.因此對(duì)于大規(guī)模的數(shù)據(jù)去重, SimHash具有絕對(duì)優(yōu)勢的去重效率.傳統(tǒng)的SimHash的具體實(shí)現(xiàn)步驟如下:

(2)基于Cosine Distance的SimHash

在對(duì)Cosine Distance和傳統(tǒng)SimHash研究的基礎(chǔ)上,本文提出基于Cosine Distance的SimHash,以下簡稱SimHashCosine.該SimHash特征提取只保留傳統(tǒng)SimHash實(shí)現(xiàn)步驟的Step1.1-1.4,然后利用Cosine Distance來計(jì)算指紋之間的相似度,最后通過判斷是否超過給定的閾值來判定是否重復(fù).兩種SimHash的時(shí)間開銷差異主要體現(xiàn)在是特征比較上,若n為指紋碼的長度,m為閾值(n>m),傳統(tǒng)的SimHash相似度計(jì)算利用Hamming Distance,時(shí)間復(fù)雜度最壞情況是O(n),最小只有O(m),而SimHashCosine,相似度計(jì)算利用Cosine Distance,時(shí)間復(fù)雜度至少O(n),且時(shí)間頻度至少是傳統(tǒng)SimHash的3倍,因此在特征比較效率上傳統(tǒng)的SimHash更高一點(diǎn).

2.4 MinHash算法

MinHash和SimHash一樣,能對(duì)文章進(jìn)行很好的降維,適用于大規(guī)模的網(wǎng)頁去重工作[15].MinHash經(jīng)過特征提取,將一篇文章最終轉(zhuǎn)化為n個(gè)最小Hash函數(shù)值構(gòu)成的特征集合,然后基于Hash函數(shù)值集合獲取Jaccard距離來衡量相似度.

1)基于單Hash函數(shù)的MinHash

基于單 Hash函數(shù)的 MinHash,以下簡稱MinOneHash,在進(jìn)行特征提取僅使用了一個(gè)Hash函數(shù),然后使用傳統(tǒng)的基于Merge算法的Jaccard計(jì)算相似度,具體的實(shí)現(xiàn)步驟如下:

2)基于多Hash函數(shù)的MinHash

基于多 Hash函數(shù)的 MinHash,以下簡稱MinMutilHash,使用n個(gè)Hash函數(shù)進(jìn)行特征提取(n>1),特征提取的步驟:對(duì)于事先確定的n個(gè)Hash函數(shù),對(duì)于每個(gè)Hash函數(shù),按照約定的順序都對(duì)文章的詞語集合s中的所有詞語進(jìn)行Hash操作,形成各自的Hash函數(shù)值集合,然后各自從各自的Hash函數(shù)值集合中篩選出最小Hash值,n個(gè)Hash函數(shù)最終獲得n個(gè)最小值.由于特征提取計(jì)算維度的擴(kuò)大,相對(duì)于MinOneHash,時(shí)間復(fù)雜度較高.但MinMutilHash相似度計(jì)算法是根據(jù)Broder提出的最小獨(dú)立置換概念,通過求得兩個(gè)Hash函數(shù)值集合中對(duì)應(yīng)位置Hash值相同的元素?cái)?shù)目來評(píng)估相似度,特征比較的時(shí)間復(fù)雜度是 O(n),相比于MinMutilHash的O(m+n),特征比較效率要高.

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

3.1 測試方案設(shè)計(jì)

由于涉及算法眾多,以排列組合的形式進(jìn)行組合測試需要耗費(fèi)大量時(shí)間.因此本文針對(duì)表1所列算法,先縱向比較剔除明顯劣勢的算法,然后橫向比較獲得各個(gè)去重算法最適宜的分詞算法和特征選擇,最后對(duì)去重表現(xiàn)良好的候選算法,進(jìn)行進(jìn)一步優(yōu)化后再綜合測試比較的策略.

本文以精度、召回率、計(jì)算時(shí)間來衡量算法的去重效果.精度是衡量算法準(zhǔn)確性的指標(biāo),公式如式(8)所示.召回率是衡量算法查全程度的指標(biāo).公式如式(9)所示

考慮到大數(shù)據(jù)服務(wù)對(duì)數(shù)據(jù)準(zhǔn)確性的要求,去重效果的衡量標(biāo)準(zhǔn)以精度優(yōu)先,精度越高表示去重效果越好;其次是召回率,召回率越高去重效果越好;在精度相差不大時(shí),優(yōu)先選擇召回率高的算法,相差不大的標(biāo)準(zhǔn)是正負(fù)差值不超過1%;計(jì)算時(shí)間最后考慮.計(jì)算時(shí)間中包括兩部分:特征提取時(shí)間,特征比較時(shí)間.在大數(shù)據(jù)服務(wù)的輿情去重中,對(duì)一篇文章特征提取只需要進(jìn)行一次,特征比較則會(huì)進(jìn)行很多次,因此對(duì)于不同的去重算法,算法特征比較時(shí)間要優(yōu)于特征提取時(shí)間考慮.測試樣本統(tǒng)一使用包含3000真實(shí)輿情文章的數(shù)據(jù)集.

3.2 縱向比較

3.2.1 分詞算法的比較

為了保證實(shí)驗(yàn)結(jié)果不受特征選擇的影響,在本實(shí)驗(yàn)中對(duì)詞語都不進(jìn)行特征選擇,為了保證實(shí)驗(yàn)結(jié)果不受去重算法的影響,在本實(shí)驗(yàn)中去重算法統(tǒng)一使用傳統(tǒng)的SimHash.測試結(jié)果如表2所示.

表2 基于結(jié)巴分詞不同模式的去重測試結(jié)果

由表2可得,精度:IKAnalyzer智能>HanLP CRF>結(jié)巴全模式分詞>90.5%,召回率:IKAnalyzer智能>HanLP CRF>結(jié)巴全模式分詞>55.5%,因此保留IKAnalyzer智能、HanLP CRF和結(jié)巴全模式.

3.2.2 特征選擇算法的比較

本文繼續(xù)使用SimHash算法,分詞算法選用IKAnalyzer智能分詞,以無加權(quán)為參照,觀察不同特征選擇下去重效果的差.實(shí)驗(yàn)結(jié)果如表3所示.

表3 基于不同特征選擇的去重測試結(jié)果

由表3可得,無加權(quán)和TextRank去重表現(xiàn)最好,但是根據(jù)實(shí)驗(yàn)發(fā)現(xiàn)TextRank特征提取時(shí)間很長導(dǎo)致總計(jì)算時(shí)間太長,且更換其他分詞算法時(shí),結(jié)合TextRank的去重效果都有所降低,因此輿情去重在此只保留無加權(quán).

3.2.3 去重算法比較

去重算法的比較研究部分主要任務(wù)是從Jaccard、SimHash、MinHash中各篩選出一種,然后和Cosine Similarity進(jìn)行比較.測試結(jié)果如表4所示.

表4 不同去重算法的測試結(jié)果

由表4可知:

① 在精度和召回率上,SimHashCosine同時(shí)高于SimHashHamming,保留SimHashCosine.

②MinMultiHash精度略低于MinOneHash,但兩者相差不大,且在召回率和特征比較時(shí)間上, MinMultiHash相比于MinOneHash具有絕對(duì)優(yōu)勢,因此保留MinMultiHash.

③Cosine Similarity時(shí)間花費(fèi)太大,確定舍去.

④ 傳統(tǒng)的Jaccard精度明顯高于改進(jìn)的Jaccard,但改進(jìn)的Jaccard召回率和特征效率明顯高于傳統(tǒng)的Jaccard,各具明顯優(yōu)勢,實(shí)際使用時(shí)可以根據(jù)場景需求進(jìn)行選擇,在面向金融行業(yè)的大數(shù)據(jù)服務(wù)中,以精度優(yōu)先保留傳統(tǒng)的Jaccard.

3.3 橫向比較

在算法橫向比較部分,分詞算法保留IKAnalyzer智能、HanLP CRF和結(jié)巴全模式,排除使用特征選擇,因此在橫向比較部分主要研究保留的分詞算法對(duì)去重算法的影響.便于表示在此將IKAnalyzer智能、HanLP CRF、結(jié)巴全模式分詞分別簡稱為智能、CRF、全模式.橫向比較結(jié)果如表5所示.

表5 橫向比較結(jié)果

由表5可知:

① 精度優(yōu)先原則,SimHashCosine與IKAnalyzer智能結(jié)合效果最高.

②MinMultiHash與三種分詞方法結(jié)合時(shí),全模式和CRF精度最高且相差很小,考慮全模式的召回率明顯高于CRF,確定MinMultiHash和全模式結(jié)合.

③Jaccard與三種分詞方法結(jié)合時(shí),召回率和精度都相差不大,但特征比較時(shí)間,全模式:1018.42s,智能:638.54s,CRF:861.57s,其中IKAnalyzer智能模式最短,因此選擇智能模式和Jaccard結(jié)合.

3.3 綜合比較

算法橫向比較后篩選出這3種算法: MinMultiHash+結(jié)巴全模式、Jaccard+IKAnalyzer智能、SimHashCosine+IKAnalyzer智能.閾值的不同,會(huì)導(dǎo)致去重結(jié)果有很大差異,此處研究這3種算法去重效果隨著閾值的變化情況.此外本文認(rèn)為一個(gè)好的去重算法,應(yīng)當(dāng)在保持較高精度時(shí)召回率也很高,算法的特征比較時(shí)間短,算法的穩(wěn)定性較好.這個(gè)穩(wěn)定性主要體現(xiàn)在在整個(gè)閾值取值范圍內(nèi),精度和召回率隨閾值的整體變化是否比較平穩(wěn).本文以折線圖的形式展示每種算法隨著閾值的改變,精度和召回率的變化趨勢.精度隨閾值的變化折線圖如圖1所示,召回率隨閾值變化折線圖如圖2所示.如果一個(gè)算法的某個(gè)閾值精度少于80%或召回率低于40%,相應(yīng)閾值下的精度和召回率都不再被顯示.

圖1 精度隨閾值的變化折線圖

圖2 召回率隨閾值的變化折線圖

由圖1和2很明顯可以看出:

①Jaccard和MinMultiHash在很大的閾值變化范圍內(nèi),都能同時(shí)保證較高的精度和較高的召回率.

②Jaccard始終以微弱的優(yōu)勢,在精度和召回率上高于MinMultiHash.

③ 算法的穩(wěn)定性排序:Jaccard>MinMultiHash> SimHashCosine.

④ 結(jié)合表4觀察,MinMultiHash特征比較時(shí)間遠(yuǎn)小于Jaccard.

因此在輿情去重場景中,對(duì)算法精度和召回率非常高,推薦Jaccard;追求較高的精度和召回率,同時(shí)對(duì)時(shí)間的要求也很高的情況,推薦MinMultiHash.

4 結(jié)語

輿情是大數(shù)據(jù)服務(wù)中一種重要的數(shù)據(jù)產(chǎn)品,但隨著大數(shù)據(jù)時(shí)代的來臨,輿情服務(wù)必須解決重復(fù)嚴(yán)重的問題才能提供更高質(zhì)量的數(shù)據(jù).本文通過對(duì)分詞算法、特征選擇和去重算法進(jìn)行實(shí)驗(yàn)研究,并對(duì)傳統(tǒng)的Jaccard和SimHash進(jìn)行了改進(jìn).提出了先縱向比較,后橫向比較,最后綜合比較的實(shí)驗(yàn)策略,通過此實(shí)驗(yàn)策略篩選出了輿情去重表現(xiàn)突出的算法搭配.隨著輿情研究的深入,在今后可將Hadoop算法納入研究范圍,以提高算法的去重效率.

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

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

3胡洋,劉秀榮,魏娜,張么九,劉婉行,鈕文異.北京健康教育微博體系初建參與者網(wǎng)絡(luò)及微博使用習(xí)慣的現(xiàn)狀分析.中國健康教育,2014,30(8):706–708.

4吳紹忠,李淑華.互聯(lián)網(wǎng)絡(luò)輿情預(yù)警機(jī)制研究.中國人民公安大學(xué)學(xué)報(bào),2008,14(3):38–42.

5賀知義.基于關(guān)鍵詞的搜索引擎網(wǎng)頁去重算法研究[碩士學(xué)位論文].武漢:華中師范大學(xué),2015.

6龍樹全,趙正文,唐華.中文分詞算法概述.電腦知識(shí)與技術(shù), 2009,5(10):2605–2607.

7劉洪波.詞頻統(tǒng)計(jì)的發(fā)展.情報(bào)科學(xué),1991,12(6):69–73.

8朱小娟,陳特放.基于SVM的詞頻統(tǒng)計(jì)中文分詞研究.微計(jì)算機(jī)信息,2007,23(30):205–207.

9華秀麗,朱巧明,李培峰.語義分析與詞頻統(tǒng)計(jì)相結(jié)合的中文文本相似度量方法研究.計(jì)算機(jī)應(yīng)用研究,2012,29(3):833–836.

10王景中,邱銅相.改進(jìn)的TF-IDF關(guān)鍵詞提取方法.計(jì)算機(jī)科學(xué)與應(yīng)用,2013,35(10):2901–2904.

11 Cho J,Shivakumar N,Garcia-Molina H.Finding Replicated WebCollections.AcmSigmodRecord,2000,29(2):355–366.

12黃德才,戚華春.PageRank算法研究.計(jì)算工程,2003,32(4): 145–146.

13 Real R,Vargas JM.The Probabilistic Basis of Jaccard's Index of Similarity.Systematic Biology,1996,45(3):380–385.

14 Sood S,Loguinov D.Probabilistic Near-Duplicate Detection Using SimHash.Acm Conference on Information,New York,2011:1117–1126.

15 Rao BC,Zhu E.Searching Web Data using MinHash LSH. International Conference on Management of Data,New York,2016:2257–2258.

Duplicate RemovalAlgorithm for Public Opinion

ZHANG Qing-Mei

(School of Software Engineering,University of Science and Technology of China,Suzhou 215123,China)

In big data services,duplicate removal of public opinion information is inevitable,and it lacks theoretical guidance.There is a research on the classical duplicate removal algorithm such as SimHash,MinHash,Jaccard,Cosine Similarty,as well as common segmentation algorithm and feature selection algorithm in order to seek excellent performance of the algorithm.The Jaccard based on short article and the SimHash algorithm based on Cosine Distance are proposed to improve the traditional algorithms.Aiming at the problem of the low efficiency of experiment on many research subjects,the strategy is adopted that filters out algorithm of obvious advantages by vertical comparison firstly, and gets the most appropriate algorithm collocation by horizontal comparison secondly,at last,makes a comprehensive comparison.The experiment of 3000 public opinion samples shows that improved SimHash has better effect than traditional SimHash;improved Jaccard increases the recall rate by 17%and improves the efficiency by 50%compared with traditional Jaccard.Under the condition that the accuracy is higher than 96%,MinHash+Jieba full pattern word segmentation and Jaccard+IKAnalyzer intelligent word segmentation has more than 75%recall rate and good stability. MinHash is a bit weak than Jaccard in the aspect of removal effect,yet has the best comprehensive performance and shorter feature comparison time.

public opinion data;duplicate removal algorithm;similarity computation;big data service

2016-08-28;收到修改稿時(shí)間:2016-09-27

10.15888/j.cnki.csa.005745