基于分布式架構的海量文本快速相似度檢測研究

晉曉琳，張樹武，劉杰

(1.中國傳媒大學 信息工程學院，北京 100024；2. 中國科學院自動化研究所 數(shù)字內(nèi)容技術與研究中心，北京 100190；3.北京電影學院未來影像高精尖創(chuàng)新中心，北京 100088)

1 引言

在高速發(fā)展的21世紀，每時每刻都有大量的信息產(chǎn)生并在互聯(lián)網(wǎng)上快速傳播。數(shù)據(jù)集合規(guī)模已實現(xiàn)從GB到PB的飛躍，未來網(wǎng)絡大數(shù)據(jù)還將實現(xiàn)近50倍的增長。IDC《數(shù)字宇宙》的研究報告表明：2020 年全球新建和復制的信息量將超過40ZB，是2012年的12倍；而中國的數(shù)據(jù)量則會在2020年超過8ZB，比2012年增長22倍。雖然數(shù)據(jù)量的飛速增長帶來了大數(shù)據(jù)技術和服務市場的繁榮發(fā)展，但面對海量文本數(shù)據(jù)人們變得越來越手足無措，所以人們越來越希望能夠在海量文本環(huán)境下快速精確地提取出所需要的信息，從而對所選信息進行后續(xù)處理。為了解決這一問題，就需要一個文本相似性檢測技術，使人們能夠快速準確地從海量數(shù)據(jù)中找到最為相似的文本。

文本相似度算法一直是自然語言處理領域研究的重點之一，國內(nèi)外學者也提出了一些解決方案?；诰嚯x的計算相似度的方法主要有余弦距離[1]、編輯距離[2]、漢明距離、歐幾里得距離。如丁智斌等提出先用VSM向量空間模型進行文本向量化[3]，通過使用余弦相似度和 Jaccard 相似度這兩種基于向量內(nèi)積的方法進行相似度計算。胡維華等利用漢明距離計算文本相似度[4]，該方法首先采用TF-IDF算法以及《知網(wǎng)》的語義信息來加強語義信息，然后利用漢明距離計算文本相似度，避開對高維稀疏矩陣的直接處理并提高了文本計算的準確性?；诰嚯x的計算方法適用于文本數(shù)量較小的情況，在海量文本環(huán)境下，該計算方法的效率非常低。VSM 向量空間模型(Vector Space Model)是一種基于向量空間的方法，它是由Gerard Salton 等在1969年首先提出的[5] [6]。該模型需要逐個進行向量化，并進行余弦計算，比較消耗CPU處理時間，所以不適合于海量文本環(huán)境下。Simhash算法是2002年由Google 的Charikar提出的文本指紋算法[7]。該算法主要用來處理Google網(wǎng)頁去重問題，也是目前主流的海量相似度算法之一[8] [9] [10]。Simhash算法主要通過指紋間的漢明距離來比較文本的相似程度，而且其“降維”的思想使得檢測速度快，常常被用做處理海量文本查找。但該算法的實質(zhì)是基于哈希的算法，只能得到一個粗略的相似度篩選，高的相似度并不意味著文本一定相似。

現(xiàn)在使用最多的搜索引擎主要是Elasticsearch和Solr[11][12][13]。Elasticsearch是一個建立在全文搜索引擎 Apache LuceneTM基礎上的搜索引擎，可以說Lucene是當今最先進、最高效的全功能開源搜索引擎框架。它是一個實時分布式的搜索引擎和數(shù)據(jù)分析引擎，能夠進行全文檢索，結構化檢索，數(shù)據(jù)分析，可以幫助你用前所未有的速度去處理大規(guī)模數(shù)據(jù)。對于海量數(shù)據(jù)來說，ES可以自動將大規(guī)模數(shù)據(jù)分布到多臺服務器上進行存儲和檢索，而不需要額外建立數(shù)據(jù)庫。對于Solr來說，在建立索引時，它會產(chǎn)生io阻塞，查詢性能較差，實時索引搜索效率不高。所以海量數(shù)據(jù)進行搜索時，ES更具有優(yōu)勢。因為ES實時搜索的優(yōu)點，國內(nèi)外很多公司都使用該框架作為信息檢工具。例如，Github公司使用Elasticsearch搜索20TB的數(shù)據(jù)，包括13億的文件和 1300億行的代碼；維基百科作為多語言的網(wǎng)絡百科全書，整個網(wǎng)站的總編輯次數(shù)已超過10億次，它使用Elasticsearch來進行全文搜索并高亮顯示關鍵詞，以及給用戶進行搜索推薦等功能；The Guardian是英國三大綜合性內(nèi)容日報之一，Elasticsearch作為該新聞網(wǎng)站的搜索引擎去記錄用戶行為日志、發(fā)布用戶評論、進行數(shù)據(jù)分析。

在對海量文本進行搜索查詢時，Elasticsearch能夠分布式實時文件存儲，并將每一個字段都編入索引，使其可以被實時搜索。本文選用ES作為文本相似度檢測的第一步，通過多個關鍵詞的并行搜索來篩選出候選樣本。余弦相似度算法適合于小樣本集合，因此本文選用TF-IDF作為關鍵詞提取算法，通過關鍵詞作為ES查詢條件在海量文本環(huán)境下快速篩選出可疑候選集，進而再用余弦相似度來進一步找到最為相似的文本。

2 關鍵技術

2.1 Elasticsearch

Elasticsearch(簡稱ES)是一個基于Lucene構建的實時、分布式、RESTful的搜索引擎。它的高級之處在于，使用Lucene作為核心來實現(xiàn)所有索引和搜索的功能，使得每個文檔的內(nèi)容都可以被索引、搜索、排序、過濾。同時，它還提供了豐富的聚合功能，可以對數(shù)據(jù)進行多維度分析；對外統(tǒng)一使用REST API接口進行溝通，即Client與Server之間使用HTTP協(xié)議通信 ，Elasticsearch的架構圖如圖1所示。

圖1 Elasticsearch分布式搜索引擎架構圖

Elasticsearch進行全文檢索有以下流程：(1)建立索引：ES中的索引相當于SQL中的一個數(shù)據(jù)庫，通過建立索引名字來進行后續(xù)文檔的搜索、更新及刪除等操作。不同于傳統(tǒng)的關系型數(shù)據(jù)庫，ES能夠?qū)?shù)據(jù)存儲于一個或多個索引中進行分布式索引。分布式索引通過將一個索引進行分片，也就是說將一個索引通過分片又重新分成一個個獨立的索引。在海量數(shù)據(jù)下，ES正是因為對索引進行分片來分攤硬件壓力，從而達到能夠進行實時快速搜索。在創(chuàng)建索引時，用戶可指定其分片的數(shù)量，默認數(shù)量為5個。(2)建立映射：在存儲文本之前需要建立映射，ES中使用Mapping來對存儲文本進行分析。使用者可根據(jù)需要在Mapping中申明字段的數(shù)據(jù)類型、是否建立倒排索引、建立倒排索引時使用什么分詞器。默認情況下，ES會為所有的string類型數(shù)據(jù)使用standard分詞器來建立倒排索引。這個類似于MySQL在db schema。(3)文本存儲：ES是面向文檔型數(shù)據(jù)庫，一條數(shù)據(jù)在這里就是一個文檔，用JSON作為文檔序列化的格式。一個文檔中包含_index、_type、_id、_source等核心元數(shù)據(jù)，其中_index說明一個document屬于哪個index，這里的index為文本集合建立的索引，索引相當于一個數(shù)據(jù)庫；_type說明document屬于index中的哪個類別，也就是數(shù)據(jù)庫中的表；_id代表document的唯一標識，與index和type一起，可以唯一標識和定位一個document ；_source代表了document中具體包含的內(nèi)容，例如標題、關鍵詞、文本內(nèi)容等信息，也就是數(shù)據(jù)庫中的字段。一個 ES 集群可以包含多個索引，也就是說索引中包含了很多類型。這些類型中包含了很多的文檔，然后每個文檔中又包含了很多的字段。(4)文本查詢：ES的查詢語法(query DSL)分為兩部分：query和filter，區(qū)別在于查詢的結果是要完全匹配還是相關性匹配。filter查詢考慮的是“文檔中的字段值是否等于給定值”，答案在“是”與“否”中；而query查詢考慮的是“文檔中的字段值與給定值的匹配程度如何”，會計算出每份文檔與給定值的相關性分數(shù)，用這個分數(shù)對匹配了的文檔進行相關性排序。

2.2 余弦相似度

余弦相似度，也稱為余弦距離，是用向量空間中兩個向量夾角的余弦值作為衡量兩個個體間差異的大小的度量。它是文本相似度計算比較經(jīng)典和常用的算法之一。如果余弦值越接近1，就表明夾角越接近0度，也就是兩個向量越相似，這就叫“余弦相似性”。該算法的基本思路是：如果兩個文本的用詞越相似，它們的內(nèi)容就應該越相似。因此，一般通過詞頻來計算它們之間的相似程度。余弦距離計算相似度主要采用以下步驟：第一步，對文本進行分詞以及去停用詞。對于短文本，可以直接對文本進行分詞；而對長文本來說，則需要進行文本關鍵詞提??；第二步，計算詞頻。列出文本中所有詞語，如果文本中有該詞語就加1，沒有出現(xiàn)則為0；第三步，通過第二步計算出的詞頻可以生成文本的詞頻向量；第四步，計算向量之間的余弦距離，值越大就說明兩個文本越相似。文本的向量為多維向量，設向量A=(A1，A2，，An)，B=(B1，B2，，Bn)，則余弦距離公式如公式1所示：

(1)

2.3 TF-IDF

TF-IDF(term frequency-inverse document frequency)是一種用于資訊檢索與資訊探勘的常用加權技術[14]。TF-IDF是一種統(tǒng)計方法，用以評估一個詞在一個文檔集中的某一份文檔的重要程度。TF-IDF主要思想是：如果某個詞或短語在一篇文章中出現(xiàn)的頻率TF高，并且在其他文章中很少出現(xiàn)，則認為此詞或短語在該文章中占有重要位置，而且更能代表該文章的主題。TF-IDF實際上是：TF * IDF，其中，TF詞頻(Term Frequency)，IDF反文檔頻率(Inverse Document Frequency)。如果一個詞的TF-IDF的權重越大說明這個詞匯有很好的辨別能力。某一特定文件內(nèi)的高詞語頻率，以及該詞語在整個文件集合中的低詞語頻率，可以產(chǎn)生出高權重的TF-IDF。因此，通過TF-IDF來提取文本的關鍵詞。TF-IDF計算公式如公式2所示：

(2)

3 分布式海量文本快速相似度檢測技術研究改進

本文所研究的海量文本快速相似度檢測主要是使用分布式搜索引擎框架Elasticsearch來篩選出候選樣本集，然后使用余弦距離來進行最終的相似度比較，最后選出相似度最大的值為所需樣本。分布式搜索框架通過輸入關鍵詞來進行文本搜索，搜索出來的文本都是包含關鍵詞的文本，所以可以通過搜索引擎在海量文本下盡可能多的過濾到無關文檔，召回相關文檔，從而來加快比較速度。分布式搜索框架只能做到關鍵詞或者關鍵句的搜索，也就是說只能做到篩選出文本含有搜索關鍵詞或者句子的文本。如果句子有所改動就無法搜索出來，所以篩選之后的候選樣本集需要采用精確的相似度算法進行更加精確的比對，最后選出最為相似的文本。

分布式海量文本快速相似度檢測技術研究流程如圖2所示，具體步驟如下：

1.首先將海量文本集合存入ES分布式搜索引擎中，并設置中文分詞器。這樣做主要是可以進行詞語對的搜索，例如，搜索“科學”，如果設置分詞器就會查詢到包含“科學”的詞的文本，而不會搜到只包含“科”或“學”的文本，從而能夠找到更加相關的文本；

2.通過特征提取算法TF-IDF來進行文本關鍵詞的提取，提取的關鍵詞作為ES搜索引擎的查詢條件。每篇文本選取TF-IDF值高的前20個關鍵詞來表示文本主題意思；

3.將提取的文本關鍵詞作為ES的查詢條件來篩選出文本候選樣本。本文從每篇文本提取TF-IDF高的前20個關鍵詞中并選取前10個關鍵詞作為可以ES的查詢條件，并通過最少匹配來選取候選文本；

4.經(jīng)過召回一定數(shù)量的文本作為候選樣本進行余弦相似度計算。例如全文比對召回前150個文本，句子比對的話召回前200。那么，對候選文本集合進行余弦距離的比較，最后選取文本相似度最大作為相似文本輸出。

圖2 分布式海量文本快速相似度檢測技術研究流程框圖

4 實驗驗證

4.1 實驗數(shù)據(jù)及工具

本實驗選用了THUCNews作為實驗數(shù)據(jù)，總共有836075萬條新聞數(shù)據(jù)，數(shù)據(jù)主要分為財經(jīng)、科技、體育、社會、教育等十四類新聞。THUCNews是根據(jù)新浪新聞RSS訂閱頻道2005-2011年間的歷史數(shù)據(jù)篩選過濾生成，均為UTF-8純文本格式。在新聞中同一類型的新聞數(shù)據(jù)之間的特征詞很相似，這也為實驗增加難度。

文本預處理過程中，去停用詞表采用的是哈工大的停用詞表；使用jieba分詞來進行文本分詞處理。jieba分詞支持最大概率法(Maximum Probability)，隱式馬爾科夫模型(Hidden Markov Model)，索引模型(QuerySegment)，混合模型(MixSegment)，共四種分詞模式，同時有詞性標注，關鍵詞提取，支持自定義字典等功能。

實驗運行環(huán)境是在CPU為Intel(R)Core(TM)i7- 4790 @3.60GHz，內(nèi)存16GB，操作系統(tǒng)為windows7 64bit，采用Python語言實現(xiàn)算法，并在Anaconda3自帶的Spyder編譯器上運行，分布式搜索引擎選用Elasticsearch 2.3.4版本，IK為搜索引擎的分詞器。

4.2 實驗結果分析

實驗分為2個實驗，其中實驗1主要是通過文本之間的相似度比較；實驗2是句子與文本之間的相似度比較。為了更加符合實際環(huán)境，我們從80多萬篇文本中隨機選取500篇新聞文本，并對其進行25%左右的隨機修改。對文本的修改主要是對文本進行開頭、結尾、中間的不同程度的刪除、增加和修改，從而更加符合現(xiàn)實中大多數(shù)相似文本并不是完全相似，都有一下雜質(zhì)的干擾存在。這兩個實驗主要是通過修改后的文本和句子，能夠通過快速精確的找到未修改前的文本以及包含該句子的文本。

實驗1中，主要是修改后的500個文本在80多萬的文本集合中找到對應的文本，從而驗證該算法的性能。該實驗通過Simhash算法、Simhash算法結合余弦距離以及ES搜索引擎結合余弦距離的方法進行召回率、準確率以及時間復雜度的比較。在ES結合余弦距離的算法中，輸入10個關鍵詞，且最少匹配6個；然后通過ES召回前150個文本，最后用余弦距離與召回的文本進行相似度比較，選出最大相似度文本。實驗1結果如圖3所示：

圖3 修改文本相似度比較

實驗2中，從文本集合中通過句子符號進行文本分割，并且在眾多句子集合中隨機選取68個句子，并對句子進行一定程度的修改。在對文本按句子分割時，會為每個句子配上對應的id號，從而能更好的驗證。該實驗的目的主要是通過修改后的句子來找到句子所在的文本。該實驗通過Simhash算法、Simhash算法結合余弦距離、余弦距離、最長公共子序列以及ES結合余弦距離來進行準確率和時間復雜度的比較。在ES結合余弦距離的算法中，輸入10個關鍵詞，且最少匹配6個，且ES召回前200個文本。對召回文本進行分句，然后用余弦距離進行句子之間的比較，最后選出相似度最大的句子所在文本為最后結果。實驗2結果如圖4所示：

圖4 修改句子相似度比較

通過實驗可知：實驗1中該實驗將Simhash的漢明距離設為10、16、25，通過實驗比較發(fā)現(xiàn)閾值為16的準確率以及召回率最為合適。ES結合余弦距離方法的召回率和準確率為100%，運行時間為77.45s；而閾值為16的Simhash算法結合余弦距離的方法召回率為98.4%，準確率為96.7%，運行時間為574.38s。對于修改文本來說，本文方法在準確率和召回率有很大的提升，而且時間上也滿足海量文本快速檢測的要求。在實驗2中，該實驗通過比較發(fā)現(xiàn)，LCS和余弦距離的方法運行時間太長，不適合海量文本；只用Simhash算法進行相似度雖然比較，時間上縮短，但是準確率只有72.06%；Simhash結合余弦距離與ES結合余弦距離的方法比較適合海量文本環(huán)境下，其中，兩者在準確率上都為100%，但是，前者的運行時間是后者的7.4倍，所以分布式搜索引擎結合余弦距離的方法更加適合海量文本。

5 結束語

為了滿足海量文本環(huán)境下快速且準確的找到所需文本，本文提出了基于分布式架構的海量文本快速相似度檢測技術。本文主要是通過常用海量文本相似度算法Simhash與分布式搜索引擎ES進行比較發(fā)現(xiàn)，分布式搜索引擎在準確率、召回率以及時間復雜度上都更加適合作為海量文本初步篩選算法。該方法比simhash算法能夠更有效的縮小比較范圍來提高查找速率。對于分布式搜索引擎來說，準確率以及召回率的高低取決于查找的關鍵詞的精確性，所以為了完善本文提出的算法，接下來需要更加精確的關鍵詞提取算法來提取更能代表文本意思的詞語，從而縮小候選文本集來進一步加快比較速度。