中文文本相似度在商業(yè)網(wǎng)絡(luò)中的應(yīng)用

[摘要] 目前文本相似度在商業(yè)網(wǎng)絡(luò)中應(yīng)用廣泛，本文主要討論中文文本相似度研究的現(xiàn)狀，給出中文文本相似計(jì)算的定義和概念，提出基于PHP的中文文本相似度算法，針對(duì)某網(wǎng)站的在線系統(tǒng)，進(jìn)行對(duì)文檔之間的相似程度的數(shù)值分析，表明所提出的算法具有一定的有效性。

[關(guān)鍵詞] 文本相似度 分詞 PHP

一、引言

文本挖掘以數(shù)據(jù)挖掘?yàn)榛A(chǔ)，結(jié)合機(jī)器學(xué)習(xí)，自然語言處理，信息檢索和知識(shí)管理等領(lǐng)域的技術(shù)來處理文本數(shù)據(jù)，從中獲得有價(jià)值的信息或數(shù)據(jù)幫助人們更好的決策。人們也可以把文本挖掘技術(shù)應(yīng)用到各種相關(guān)的領(lǐng)域，帶來社會(huì)效益或經(jīng)濟(jì)效益。在中文信息處理中，文本相似度的計(jì)算廣泛應(yīng)用于信息檢索、機(jī)器翻譯、自動(dòng)問答系統(tǒng)、文本挖掘等領(lǐng)域，是一個(gè)非常基礎(chǔ)而關(guān)鍵的問題，長期以來一直是人們研究的熱點(diǎn)和難點(diǎn)。

文本相似度在商業(yè)網(wǎng)絡(luò)中應(yīng)用廣泛，比如人們要在網(wǎng)站中進(jìn)行信息搜索時(shí)，利用輸入的搜索信息找到與此信息相似度較高的信息，人們要利用網(wǎng)絡(luò)中一些舊的有用信息用來找出新的相似性信息，以供人們更好的做決策或者投資，人們可以通過比較相似性，將有用信息分為不同的類別，針對(duì)這些類別采取不同的解決方案或者用這些類別去解決某些問題。在某些網(wǎng)絡(luò)系統(tǒng)中，針對(duì)人們提出的問題，可以判斷問題的相似度，如果相似度很高，可以用相似性的答案去回答，這樣大大節(jié)省時(shí)間和效率。因此，文本相似度在商業(yè)或者網(wǎng)絡(luò)中的應(yīng)用是很有好處的，也可以幫助人們更好地做決策，或者解決一些問題。

很多文本相似度的算法是以向量空間模型(VSM)和隱性語義標(biāo)引(LSI)為基礎(chǔ)的。在VSM中，文本被表示成詞出現(xiàn)在這個(gè)文本中的頻率的向量。兩個(gè)文本之間的相似度用它們?cè)~頻向量之間的夾角余弦計(jì)算。LSI也是一種基于向量空間技術(shù)的方法。其工作原理是利用矩陣?yán)碚撝械摹捌娈愔捣纸?SVD)”技術(shù)，將詞頻矩陣轉(zhuǎn)化為奇異矩陣，可以通過標(biāo)準(zhǔn)化的內(nèi)積計(jì)算來計(jì)算向量之間的夾角余弦相似度，進(jìn)而根據(jù)計(jì)算結(jié)果比較文本間的相似度。另外國內(nèi)學(xué)者潘謙紅、王炬、史忠植提出利用屬性論計(jì)算文本相似度，張煥炯、王國勝、鐘義信提出基于漢明距離的文本相似度計(jì)算，金博、史彥軍等提出利用知網(wǎng)的知識(shí)結(jié)構(gòu)及其知識(shí)描述語言的語法進(jìn)行相似度計(jì)算的方法。

以上是目前中文文本相似與算法的主要幾種方法，本文在上述幾種方法基礎(chǔ)之上，提出了一個(gè)基于PHP的文本相似計(jì)算算法，來計(jì)算文本之間的相似程度，因?yàn)镻HP語言本身是一種網(wǎng)絡(luò)語言，因此算法要在網(wǎng)站中進(jìn)行應(yīng)用。

二、中文文本相似度定義及概念

1.基于PHP的漢語分詞系統(tǒng)SCWS簡介

中文分詞是對(duì)中文文本進(jìn)行自動(dòng)分析的第一個(gè)步驟，分詞是中文文本相似度計(jì)算的基礎(chǔ)和前提。目前分詞方法很多，常用的有正向、逆向最大匹配法、最佳匹配法、逐詞遍歷法、詞頻統(tǒng)計(jì)法、聯(lián)想、回溯法、鄰接約束法和最少分詞法等。我們采用了SCWS(Simple Chinese Words Segmentation)簡易中文分詞系統(tǒng)實(shí)現(xiàn)文本分詞，它是一套基于詞頻詞典的機(jī)械中文分詞引擎，它能將一整段的漢字基本正確的切分成詞。在后面的算法描述的第一步就是要用這個(gè)系統(tǒng)先對(duì)文本進(jìn)行分詞，然后在分詞后的文本中去掉一部分沒有實(shí)際意義的詞，就是下面要介紹的停用詞。

2.停用詞

在信息檢索中，集合文獻(xiàn)中出現(xiàn)頻率高于80%的單詞是沒有用的，這些詞常稱為“停用詞”，需要過濾掉。一般認(rèn)為停用詞包括冠詞、介詞、連詞和語氣詞，還可以包括這些詞之外的其他詞，例如一些動(dòng)詞、副詞和形容詞，可以將這類詞歸為停用詞。在排除停用詞后，可以降低序列的長度。我們所要做的就是建立一個(gè)停用詞庫，將分詞后的詞語與停用詞庫進(jìn)行匹配，如果文本中某詞屬于停用詞庫，將該詞從文本中剔除，反之，保留該詞。

3.中文文本相似度的定義

中文文本相似度關(guān)系包括以下幾種關(guān)系:詞與詞、詞與句、詞與段、句與句、句與段以及段與段等。上述的各種相似度關(guān)系可分別用于不同的研究領(lǐng)域，例如，在信息檢索中，相似度主要用于反映文本與用戶查詢?cè)谝饬x上的符合程度，在基于實(shí)例的機(jī)器翻譯中，相似度更多用于衡量文本中詞語的可替換程度，在自動(dòng)問答中，相似度反映的是句子間語義上的匹配程度，而在多文檔文摘系統(tǒng)中，相似度可以反映出局部主題信息的擬合程度。

相似度定義如下:對(duì)于兩個(gè)中文文本，相似度指的是這兩個(gè)文本之間基于字與詞語上的匹配程度。簡單來說，就是字符串與字符串之間或者句與句之間的匹配程度。如果相比較的字符串A完全包含字符串B活著字符串A和字符串B中的字或者詞語完全一樣，就認(rèn)為這兩個(gè)字符串完全相似，即相似度是100%，如果字符串A和字符串B中的字或者詞語完全不一樣，就認(rèn)為這兩個(gè)字符串不相似，如果字符串A和字符串B中的某些字或者詞語一樣或者意思相近，就認(rèn)為這兩個(gè)字符串存在相似性，相似度介于0%～100%之間。由字符串的比較可以擴(kuò)大到句與句之間的比較。

定義:如果對(duì)文本A和文本B進(jìn)行相似分析和比較，將文本A和文本B具有相同屬性或特性兩兩對(duì)應(yīng)組成相似元，相似元用ui=(ai，bi)表示，當(dāng)文本A和文本B間存在著n個(gè)相似元:u1，u2，…，un時(shí)，則將這n個(gè)相似元以集合U表示為:{u1，u2，…，un}。

其中，ui=(ai，bi)，0≤ui≤1。

當(dāng)ui=0，表示兩系統(tǒng)對(duì)應(yīng)元素既不相同也不相似;

當(dāng)O< ui<1，表示兩系統(tǒng)對(duì)應(yīng)元素處于其他情況;

當(dāng)ui=1，表示兩系統(tǒng)對(duì)應(yīng)元素完全相同。

三、基于PHP的中文文本相似度算法

1.最長公共子序列算法

這個(gè)算法的主要思想是，一個(gè)給定序列的子序列就是該給定序列中去掉零個(gè)或者多個(gè)元素，給定兩個(gè)序列X和Y，如果序列Z既是X的一個(gè)子序列，又是Y的一個(gè)子序列，那么Z是X和Y公共子序列。最長公共子序列:(Longest-Common-Subsequence)，這里定義相似度=最長公共子序列的長度×2/(字符串一的長度+字符串二的長度)。

2.算法實(shí)現(xiàn)流程

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

(1)對(duì)文本A和文本B分別用漢語分詞系統(tǒng)SCWS進(jìn)行分詞。

(2)去掉分詞后的文本A和文本B中的停用詞得序列A和序列B。

(3)對(duì)序列A和序列B用最長公共子序列算法計(jì)算最長公共子序列的長度。

(4)計(jì)算文本A和文本B之間的相似度。文本A和文本B之間的相似度 = 最長公共子序列的長度×2/(序列A的長度+序列B的長度)。

以下是本文用PHP實(shí)現(xiàn)的算法的主要步驟:

Step 1:讀入待比較的兩個(gè)序列A=(A1，A2，…，An)和B=(B1，B2，…，Bn)。

Step 2:分別計(jì)算兩個(gè)序列的長度L(A)和L(B)，分別將序列存入數(shù)組S(A)和S(B)，這里注意的是，因?yàn)槭羌冎形淖址虼擞?jì)算長度時(shí)，要計(jì)算中文字符長度，而不是單字符長度，存入數(shù)組中時(shí)，一個(gè)數(shù)組元素S(A)[n]存的是序列中的一個(gè)子序列An。

Step 3:構(gòu)建最長公共子序列矩陣C[L(A)][L(B)]，矩陣大小為L(A)×L(B)。

C[0][j]=0，j=0，1，…，L(B)-1，C[i][0]=0，i=0，1，…， L(A)-1

if S(A)[1]=S(B)[j]，j=1，2，…， L(B)-1，C[1][j]=C[0][j]+1，j=1，2，…， L(B)-1

else if C[0][j]>=C[1][j-1]，j=1，2，…，L(B)-1，C[1][j]=C[0][j]，j=1，2，…， L(B)-1

else C[1][j]==C[1][j-1]，j=1，2，…， L(B)-1

i=i+1(if i = L(A)-1，break)

Step 4:采用遞歸算法，讀入最長公共子序列矩陣C[L(A)][L(B)]、i、j，i=L(A)-1，j=L(B)-1，if(i=0||j=0)S(A)[i+1]=S(B)[j+1]，輸出S(B)[j+1]。if S(A)[i+1]=S(B)[j+1]，調(diào)用遞歸(參數(shù)為C，i-1，j-1)并輸出S(B)[j+1]，else if C[i][j+1]>=C[i+1][j]，調(diào)用遞歸(參數(shù)為C，i-1，j)，反之，調(diào)用遞歸(參數(shù)為C，i，j-1)。

Step 5:計(jì)算相似度，最長公共子序列的長度為上述遞歸算法得到的序列長度，去掉序列A和序列B中出現(xiàn)的重復(fù)子序列，用最長公共子序列計(jì)算公式計(jì)算出兩個(gè)文本之間的相似程度。

本算法可以用于多文本之間的兩兩比較。

四、實(shí)驗(yàn)結(jié)果

為了檢驗(yàn)算法分析文本的相似能力，我們使用算法分析了網(wǎng)站中文檔之間的相似性，選用的實(shí)驗(yàn)數(shù)據(jù)——文本庫是來源于某網(wǎng)站的數(shù)據(jù)庫，數(shù)據(jù)庫采用的是MySQL數(shù)據(jù)庫， 測試樣本是數(shù)據(jù)庫中的文檔。

我們對(duì)數(shù)據(jù)庫中的文本進(jìn)行分組得到11組文檔組，每組有2～6條文檔題目為偏向一個(gè)主題的相似性題目，接下來將每一組中的幾個(gè)題目對(duì)應(yīng)的文檔進(jìn)行分詞和停用詞處理，然后用算法進(jìn)行相似度的計(jì)算，計(jì)算包括段落間的計(jì)算和整篇文檔之間的計(jì)算，如表所示，計(jì)算結(jié)果出現(xiàn)相似度高的文檔數(shù)一共有49篇，通過人工檢查實(shí)際文檔內(nèi)容相似度高的文檔數(shù)為45篇，因此可以得出識(shí)別正確率為91.84%，查全率為100%。說明本文算法具有一定的有效性。

五、結(jié)論

本文所提出的算法可以計(jì)算文本之間的相似性，識(shí)別出相似性高的文本數(shù)正確率較高，對(duì)于發(fā)現(xiàn)文本的相似性具有一定的作用，通過將文本進(jìn)行相似性的分析，可以將有用信息進(jìn)行分類，某一個(gè)類別的信息可以用于解決某些商業(yè)問題或者可以進(jìn)行某種決策，那么在得到新的信息，可以通過相似性的分析，將這些新的信息歸到某一類別中，那么針對(duì)這些新的信息可以知道人們?nèi)绾螞Q策或者去解決相對(duì)應(yīng)的哪些問題，提高效率，這也是文本相似度作為一種商業(yè)技術(shù)的廣泛應(yīng)用。

參考文獻(xiàn):

[1]G. Salton， A. Wong and C. S. Yang.Vector Space Model for Automatic Indexing[J].Communications of the ACM， 1975， 18(11):613～620

[2]Deerwester S.， Dumais， Furnas， et al.Indexing by latent semantic analysis[J].Journal of the American Society for Information Science， 1990， 41(6):391～407

[3]潘謙紅王炬史忠植:基于屬性論的文本相似度計(jì)算[J].計(jì)算機(jī)學(xué)報(bào)，1999，22(6):651～655

[4]張煥炯王國勝鐘義信:基于漢明距離的文本相似度計(jì)算[J].計(jì)算機(jī)工程與應(yīng)用，2001，19:21～22

[5]金博史彥軍滕弘飛:基于語義理解的文本相似度算法[J].大連理工大學(xué)學(xué)報(bào)，2005，45(2):291～297

[6]劉小軍趙棟姚衛(wèi)東:一種用于中文文本查重的雙因子相似度算法[J].計(jì)算機(jī)仿真，2007，24(12):312～314

[7]黃姝怡:基于知網(wǎng)的中文文本相似度計(jì)算研究[D].廣州:中山大學(xué)，2008