結(jié)合漢明距離及語義的文本相似度量方法研究

胡維華，鮑　乾，李　柯

(杭州電子科技大學計算機學院，浙江 杭州 310018)

?

結(jié)合漢明距離及語義的文本相似度量方法研究

胡維華，鮑乾，李柯

(杭州電子科技大學計算機學院，浙江 杭州 310018)

摘要：利用VSM模型的TF-IDF算法對文本進行相似度量是文本信息處理領域的常用做法，但是該方法涉及到高維稀疏矩陣的處理，計算效率不高，不利于處理大規(guī)模文本，同時該方法忽略詞項語義信息對文本的影響.另有一種基于語義的相似度算法可克服前一種方法的語義缺點，但需要知識庫的支持，其建立過程的繁雜使此類算法理論多過實踐.為此提出一種新的文本相似度計算方法，方法綜合TF-IDF算法以及HOWNET的語義信息，并利用漢明距離計算文本相似度，避開對高維稀疏矩陣的直接處理.實驗結(jié)果表明，與常用方法相比較，處理速度更快、性能更好，適用于大規(guī)模文本處理.

關鍵詞：文本相似度；向量空間模型；詞頻—逆文本頻率；語義；漢明距離

0引言

文本相似度計算作為文本信息處理的關鍵性技術(shù)，其準確率直接影響文本信息處理的結(jié)果.文本相似度表征文本間的匹配程度，相似度大小與文本相似程度成正比.目前，文本的相似度量方法主要分為基于統(tǒng)計學和基于語義分析兩類[1].基于統(tǒng)計學的方法，典型的是向量空間模型(Vector Space Model, VSM)，其優(yōu)點是：以向量表示文本，簡化文本中關鍵詞之間的復雜關系，使模型具備可計算性[2].其缺點是：文本表示模型維度高而稀疏以至于難以直接處理，同時忽略了詞與詞之間的語義關系，并需要大規(guī)模語料庫支持.基于語義分析的方法，一定程度上與VSM互補，準確率較高，但建立知識庫的過程太過繁雜，因此現(xiàn)有的相關研究一般采用收錄詞比較完備的詞典代替知識庫.中文文本相似性研究一般利用HOWNET[3]，如文獻[4]的詞匯語義相似性研究，文獻[5]的語句相關度研究，文獻[6]的文本語義相似性研究等；英文文本相似性研究最常用的是WORDNET[7]，如文獻[8]的詞語消歧研究.本文根據(jù)基于統(tǒng)計學和基于語義分析兩類方法的優(yōu)缺點，提出一種新的改進算法(HSim)，實驗結(jié)果表明，與傳統(tǒng)空間向量模型方法如TF-IDF相比，新方法得到的結(jié)果更符合語義判斷，運算速度有大幅度的提高.

1VSM模型與語義相似度

1.1VSM模型

VSM是統(tǒng)計學方法中最為經(jīng)典的一種文本相似度量方法，其向量特性簡化了文本中關鍵詞之間的復雜關系，可計算性高，因此是目前信息檢索領域中廣泛采用的模型之一.其核心思想是用向量來表示文本，一般用TF-IDF(Term Frequency-Inverse Document Frequency)來進行文本—向量之間的轉(zhuǎn)換.在VSM中，將文本看成是相互獨立的詞條組(T1,T2,T3,…,Tn)，也即向量構(gòu)成，于是文本間的相似度可以看成是向量之間的相互關系.文本相似度計算的核心是比較兩個給定的文本之間的差異，通常用[0,1]之間的1個數(shù)值來度量.在該模型中可用余弦距離計算方法來計算兩個向量之間的相互關系.即：

(1)

式中，Dx=(Tx,1,Tx,2,…,Tx,n)，Dy=(Ty,1,Ty,2,…,Ty,n).VSim(Dx,Dy)越接近數(shù)值1，說明兩個給定的文本相似度越高.

在用TF-IDF計算時會涉及到兩個概念：TF(詞頻)和IDF(逆文本頻率).

根據(jù)這兩個概念形成TF-IDF算法思想：fi,j表示詞Ti在文檔Dj中出現(xiàn)的頻率，lg(N/ni)表示文本中所有文檔數(shù)N與含有詞Ti的文檔數(shù)ni的比值.根據(jù)這兩個參數(shù)得到詞Ti的權(quán)重信息，稱之為Ti的TF-IDF權(quán)重，表示為：

(2)

TF-IDF是根據(jù)向量空間模型設計的，因此可以有效區(qū)分高頻詞和低區(qū)分力詞.將TF-IDF權(quán)重值代入D(T1,T2,T3,…,Tn),根據(jù)式(1)可得出VSim(Dx,Dy)值從而判斷Dx與Dy相似度.

1.2語義相似度

VSM計算模型是基于統(tǒng)計的，其文檔間的不相關性造成了文檔的語義語境脫離，特別是中文文檔，單純考慮詞頻等統(tǒng)計信息，給中文文檔的相似度計算帶來了極大偏差.

語義相似度計算的基本思想是在單純的代數(shù)統(tǒng)計基礎上，結(jié)合上下文語義語境，發(fā)掘文本中蘊含的語義信息，使文本相似度計算更加準確[9].

對于中文語義相似度的研究，知網(wǎng)HOWNET是國內(nèi)比較權(quán)威的代表之一.本文選擇知網(wǎng)作為算法一部分的原因在于知網(wǎng)系統(tǒng)有獨特的哲學思想.其特點反映在義項和義原上.義項是對詞匯語義的描述，一個詞分解為多個義項.義項又可以用更低層次的語言來描述，這種語言就是義原.義原是描述義項的最小單位.義原作為描述義項的基本單位的同時，相互之間又存在復雜的關系，如上下位關系、同義關系、反義關系、對義關系等.根據(jù)最重要的上下位關系，所有義原組成一個義原層次體系.該層次體系可稱之為義原樹，文獻[6]、文獻[10]就是圍繞義原樹設計相似度算法的.

2基于漢明距離和語義的文本相似度計算

2.1漢明距離

在信息論中，漢明距離是描述兩個n長碼字a=(a1a2…an)，b=(b1b2…bn)之間的距離.

(3)

其中，⊕表示模2加法，ai∈{0,1}，bi∈{0,1}.

L(a,b)表示兩碼字在相同位置上不同碼的數(shù)目總和，因此它可以反映兩碼字的差異程度，進而為兩碼字的相似程度提供依據(jù)[11].L(a,b)是介于0和n之間的數(shù)，為使相似度表征更為明顯，將式(3)變形為：

(4)

Lsim(a,b)介于0和1之間，Lsim(a,b)越接近1說明碼字a和b越相似.

在上文提到VSM模型中，式(1)文本相似度可用向量余弦值VSim(Dx,Dy)來表征，同樣的VSim(Dx,Dy)越接近1，說明文本Dx和Dy越相似.但是VSim(Dx,Dy)的計算涉及到高維稀疏矩陣，計算效率低.對文本來說，經(jīng)過文本預處理以及分詞，原文本轉(zhuǎn)化為關鍵字集合，與碼字的01串相似.將關鍵字集合繼續(xù)經(jīng)過某種規(guī)則轉(zhuǎn)化為碼字，使文本與碼字建立1-1關系，這樣文本集合中的文本相似關系就可利用式(4)計算得到.由于機器指令是01串，在計算速度上更具有優(yōu)越性.

2.2算法思想

前文提到，義原是知網(wǎng)體系的特點之一，是描述概念的最基本單位，將每個詞最終分解為多個義原.本算法所涉及的義原參照知網(wǎng)附帶的語義相似度計算版本，其總數(shù)為1 617個.

本文借鑒VSM模型，結(jié)合TF-IDF，HOWNET語義義原以及漢明距離，提出一種新算法，簡稱HSim.其基本思想是：利用知網(wǎng)義原作為紐帶，將TF-IDF算法得到詞項集分解歸入到義原集中，這一步驟稱之為義原化.此時義原集中單項內(nèi)容為其統(tǒng)計值，為建立詞項集與碼字集的1-1關系，首先，需要為之前的詞項集設置詞項閾值，以隔離低頻度詞項對其后建立的碼字集的影響，這里將處理后的詞項集稱為關鍵字集；其次，將關鍵字集義原化，得到的集合稱之為義原集.因義原集中的義原頻度有高有低，需要將義原集按頻度分割處理為n個義原子集，該義原子集稱之為漢明集.若義原集為U，兩個任意漢明集為Ai，Aj，則有Ai?U，Aj?U且Ai≠Aj，其中i,j∈(1,n)，i≠j.若有2個文本Dx，Dy，則每個漢明集根據(jù)式(4)計算得到相似度Asimi.每個漢明集根據(jù)分割原理賦予不同權(quán)重值Wi.則文本相似度計算公式可表示為：

(5)

2.3HSim算法步驟

根據(jù)上述基本算法思想，給出基于漢明距離和語義的文本相似度計算算法的具體步驟.描述中涉及的“=”運算符為賦值運算符；“==”為等值運算符.

輸入：詞項集Dx,Dy

輸出：詞項集Dx,Dy的相似度HSim(Dx,Dy).

1)判斷詞項集Dx,Dy的碼字集是否都已創(chuàng)建，若是，跳到步驟5；否則，根據(jù)式(2)分別處理Dx和Dy，得到文檔中各詞項的頻度權(quán)重值Dx(Tx1,Tx2,…,Txm)，Dy(Ty1,Ty2,…,Tyn)；

2)設置詞項閾值u，過濾文檔詞項，得到關鍵字集Dkx(kx1,kx2,…,kxp)，Dky(ky1,ky2,…,kyq)；

3)根據(jù)知網(wǎng)提供的詞匯語義相似度算法，得到關鍵字義原.對應Dkx,Dky分別創(chuàng)建義原集Domx(omx1,omx2,…,omxs)，Domy(omy1,omy2,…,omys)，初始值歸0.分別根據(jù)Dkx,Dky的關鍵字義原遍歷Domx,Domy，并在對應義原上執(zhí)行累加操作.累加數(shù)c按關鍵字頻度權(quán)重值T遞增，增量為1，初始值為1.權(quán)重值越高，累加數(shù)越大；

4)根據(jù)Domx,Domy分別建立碼字集BDomx,BDomy，非零置1.設置義原閾值v；

5)遍歷初始令i=1，j=1，h=1.從Domx,Domy的i位置同時開始遍歷，若omxj或omyj大于閾值v代表的權(quán)重值，則將BDomx,BDomy中的對應omxj和omyj的項從i到j劃分為漢明集h，記錄此時omxj和omyj中較大者值為OMh.然后令h=h+1，i=j+1.每遍歷1項令j=j+1；

6)根據(jù)式(4)計算漢明集h的相似度Asimh.重復步驟5，當j==s時，遍歷結(jié)束；

7)根據(jù)OMh值從小到大整數(shù)遞增設置漢明集權(quán)重Wh，增量為1；

8)根據(jù)式(5)計算詞項集Dx,Dy的相似度HSim(Dx,Dy).

下面給出關于閾值參數(shù)的定義.

定義1詞項閾值u，將文檔詞項集中詞項按數(shù)值從大到小排成數(shù)列，則u為某詞項值的數(shù)列位置與數(shù)列長度的比值.值域為(0,1).

定義2義原閾值v，將義原集中義原項按數(shù)值從小到大排成數(shù)列，則v為某義原項值的數(shù)列位置與數(shù)列長度的比值.值域為(0,1).

3實驗及結(jié)果分析

3.1數(shù)據(jù)及預處理

本文實現(xiàn)了基于漢明距離及語義的文本相似度計算模塊.實驗數(shù)據(jù)來源于復旦大學中文語料庫，從20個類別中，選取6個子集，共1 000篇文章作為數(shù)據(jù)集，如表1所示.本實驗從中選取一部分作為實驗數(shù)據(jù)進行算法驗證.

表1　實驗數(shù)據(jù)分布

算法輸入的是詞項集，因此需要對文本文檔先進行詞項化處理.本實驗采用的詞項化處理工具是ICTCLAS2013系統(tǒng)(http://ictclas.nlpir.org/)，其創(chuàng)始人是錢偉長中文信息處理科學技術(shù)獎一等獎、中科院院長獎獲得者張華平博士.該系統(tǒng)除了可以進行中文分詞，還可以有效地識別命名實體，避免命名實體對文檔內(nèi)容造成干擾.詞項化處理后，利用TF-IDF算法得到文檔詞項集中各詞項的頻度權(quán)重值.

3.2參數(shù)選擇及實驗

算法中需要設定的參數(shù)有詞項閾值u以及義原閾值v.

為證實HSim方法的有效性，實驗選擇VSM模型的TF-IDF算法(以TF-IDF代稱)進行比較.雖然TF-IDF存在一些問題，但它在搜索引擎、文本檢測等文本處理領域中有廣泛的應用.首先利用文本聚類確定詞項閾值u以及義原閾值v，從0開始取值；再以TF-IDF算法的相似度結(jié)果作為參照，并從耗時方面進行比較；最后從文本聚類的效果上進行度量.在文本聚類上，采用K-MEANS算法[12]，并用F度量值來衡量文本相似度算法.F度量值涉及到兩個概念：查準率P和召回率R.查準率是指得到的結(jié)果中正確結(jié)果的百分比，反映的是精確度.召回率是得到的正確結(jié)果與全部測試數(shù)據(jù)總的正確結(jié)果的比率，反映的是查全度.F值由查準率和召回率綜合而成，為查準率和召回率的調(diào)和平均值，是信息檢索中重要的衡量手段.公式如下：

(6)

實驗1為確定詞項閾值u，將義原閾值v設為0，即每個義原項相互獨立.圖1為文本聚類中不同詞項閾值對算法效率影響的實驗結(jié)果.當詞項閾值u為0.6時，F(xiàn)度量值最佳，聚類效果最好.閾值越低，說明得到的關鍵字集越小，越容易丟失一些逆文本詞項；反之，關鍵字集越大，混在其中的噪音詞項越多，對相似度的計算造成困擾.

實驗2確定義原閾值v.根據(jù)確定的詞項閾值u后，同樣利用K-MEANS文本聚類以及F度量，可以確定最佳義原閾值v.圖2為文本聚類中詞項閾值u為0.6時，義原閾值v不同取值對算法效率影響的實驗結(jié)果.義原閾值v為0時，義原項相互獨立，此時，一些高價值義原項容易被忽略.隨著v值越來越大，義原之間相關性也越強.當義原閾值v取0.3時，文本聚類效果達到最佳.義原閾值v大于0.30的趨勢表明，隨著義原項間相關性加強導致獨立性下降，一些義原項的高價值被稀釋，降低了算法效率.

圖1　詞項閾值對算法的影響

圖2義原閾值對算法的影響

實驗3選定詞項閾值u=0.6，義原閾值v=0.3后，與VSM模型的TF-IDF算法進行比較.在計算相似度方面的耗時上，結(jié)果如圖3所示.TF-IDF算法的余弦度量在計算時涉及矩陣運算，耗時較長，而HSim算法在相似度計算上進行類似于漢明距離的運算，耗時較短.

實驗4同樣在選定詞項閾值u=0.6，義原閾值v=0.3的情況下，采用K-MEANS聚類算法與VSM模型的TF-IDF算法進行聚類效果比較，結(jié)果如圖4所示.在聚類效果上HSim優(yōu)于TF-IDF，其原因在于它在根植于語義的基礎上，吸收了TF-IDF精髓，有效結(jié)合了漢明距離運算與TF-IDF權(quán)重運算，并在相似度計算上規(guī)避了TF-IDF所需的大量運算.

圖3　兩種算法耗時比較

圖4　兩種算法實現(xiàn)聚類算法的比較

4結(jié)束語

在分析基于統(tǒng)計以及基于語義兩類文本相似度量方法優(yōu)缺點的基礎上，本文提出了一種結(jié)合漢明距離及語義的文本相似度量新方法HSim.方法綜合了VSM模型、知網(wǎng)義原、漢明距離這3個基本概念，通過理論分析和實驗驗證，本文提出的HSim算法與目前文本處理領域中應用較廣泛的類似方法相比，復雜度低、精度高、耗時少.

參考文獻

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

[2]GOBLC,NA.Theroleofvoicequalityincommunicatingemotion,moodandattitude[J].SpeechCommunication, 2003, 40(1):189-212.

[3]董振東.知網(wǎng)[EB/OL].(2003-09-10)[2015-05-10].http://www.keenage.com.

[4]劉群,李素建.基于《知網(wǎng)》的詞匯語義相似度計算[J].中文計算語言學,2002,7(2):59-76.

[5]李素建.基于語義計算的語句相關度研究[J].計算機工程與應用,2002,38(7):75-76.

[6]金博,史彥軍,滕弘飛.基于語義理解的文本相似度算法[J].大連理工大學學報,2005,45(2):291-297.

[7]MILLERGA.WordNet:alexicaldatabaseforEnglish[J].CommunicationsoftheACM, 1995, 38(11): 39-41.

[8]PATWARDHANS,BANERJEES,PEDERSENT.Usingmeasuresofsemanticrelatednessforwordsensedisambiguation[M]. 2003: 241-257.

[9]夏志明，劉新.一種基于語義的中文文本相似度算法[J].計算機與現(xiàn)代化,2015(4):6-9.

[10]彭京,楊冬青,唐世渭,等.基于概念相似度的文本相似計算[J].中國科學(F輯:信息科學),2009,39(5):534-544.

[11]張煥炯,王國勝,鐘義信.基于漢明距離的文本相似度計算[J].計算機工程與應用,2001,37(19):21-22.

[12]李春青.文本聚類算法研究[J].軟件導刊,2015,14(1):74-76.

DOI：10.13954/j.cnki.hdu.2016.03.008

收稿日期：2015-10-16

作者簡介：胡維華(1949- )，男，浙江富陽人，教授，網(wǎng)絡協(xié)議、圖像處理、數(shù)據(jù)挖掘研究.

中圖分類號：TP391.1

文獻標識碼：A

文章編號：1001-9146(2016)03-0036-06

The Research about Text Similarity Measuring through Hamming-distance and Semantics

HU Weihua, BAO Qian, LI Ke

(SchoolofComputer,HangzhouDianziUniversity,HangzhouZhejiang310018,China)

Abstract：To measure the text-similarity, the term frequency-inverse document frequency(TF-IDF) algorithm combined with vector space model(VSM) is a common practice in the field of text information processing. However, this method involves the processing of high-dimensional sparse matrix with a low computational efficiency. In addition, it ignores the impact of semantic information on the text. Another kind of similarity algorithm based on semanteme can overcome this shortcoming. But it needs support of knowledgebase in specific fields, and the complexity of its establishment results in more theory than practice of such algorithm. For these concerns a new method is advanced, which integrates the advantages of TF-IDF and semantic information from HOWNET. This method works out the value of text-similarity by Hamming-distance, avoiding direct processing of high dimensional sparse matrix. The results show that new method is higher than the current method in the efficiency of processing, and is more suitable for processing a large amount of text.

Key words：text-similarity; vector space model; term frequency-inverse document frequency; semantic information; Hamming-distance