如何確定中文字符串的相似度

作者：肖波

個人博客：http://blog.csdn.net/eaglet

Email：blog.eaglet@gmail.com

2007/4 南京

摘要

在數(shù)據(jù)挖掘的研究中，我們往往需要判斷文章是否雷同,對類似文章或短句進行歸類處理等，這其中就會遇到這樣的問題：如何確定兩個字符串之間的相似程度。

本文綜合作者的實際工作經驗和數(shù)據(jù)挖掘理論，結合中文字符串特性介紹一套相對完整的方法，以解決上述問題.。

分析

     最簡單的問題求解

       字符串由一組不同含義的單詞組成，它不同于數(shù)值型變量，可以用一個特定的數(shù)值來確定它的大小或位置，所以用何種方式來描述兩個字符串之間的距離，成為了一個值得探討的問題。

       通常情況下，用于分析的數(shù)據(jù)類型有如下幾種：區(qū)間標度遍歷、二元變量、標稱型變量、序數(shù)型變量、比例標度型變量、混合類型變量等。

       綜合這些變量類型，本文認為字符串變量更適合于歸類于二元變量，我們可以利用分詞技術將字符串分成若干個單詞，每個獨立的單詞作為二元變量的一個屬性。我們把所有單詞設定為一個二元變量屬性集合R，字符串1和字符串2的單詞包含于這個集合R。設q是字符串1和字符串2中都存在的單詞的總數(shù)，s是字符串1中存在，字符串2中不存在的單詞總數(shù)，r是字符串2中存在，字符串1中不存在的單詞總數(shù)，t是字符串1和字符串2中都不存在的單詞總數(shù)。我們稱 q,r,s,t為字符串比較中的4個狀態(tài)分量。 如圖1所示：

由于兩個字符串都不存在的單詞對兩個字符串的比較沒有任何作用，所以忽略t，于是我們采用非恒定的相似度評價系數(shù)(Jaccard系數(shù))來描述兩個字符串見的相異度表示公式為

相異度 = r+s / (q+r+s)，不難推斷，他們的形似度公式為

相似度=q/(q+r+s) 公式1

圖1 字符串關系描述

例如如下兩個字符串串：

字符串1：非對稱變量

字符串2：非對稱空間

他們的二元屬性關系表為：

字符串/屬性	非	對稱	變量	空間
非對稱變量	Y	Y	Y	N
非對稱空間	Y	Y	N	Y

Y 表示存在該單詞屬性，N表示不存在該單詞屬性

那么對應的

s = 1; q = 2; r = 1

兩個字符串的相似度為 2/(1+2+1) = 50%

單詞重復問題求解

前面討論的問題是最簡單的字符串比較問題，這個問題中單個字符串不存在重復的單詞，然而如果字符串中出現(xiàn)重復單詞，采用上一節(jié)的公式套用后得到的結果往往不夠理想，比如

字符串1：前進前進

字符串2：前進

公式1相似度=q/(q+r+s) 來計算，

q = 1 , r=s=0 ，得到的相似度為100%，而實際上這兩個字符串并不完全相同。為解決這個問題，我們必須將在不同位置出現(xiàn)的相同單詞假設為不同單詞，以其在字符串中出現(xiàn)的次序作為區(qū)分，這樣其二元屬性關系表如下：

字符串/屬性	前進1	前進2
前進前進	Y	Y
前進	Y	N

相應的 q = 1, s=1, r= 0

其相似度為 1/(1+1+0) = 50%

狀態(tài)分量權重 

在實際應用中，q,r,s三種狀態(tài)分量并不一定是同等價值的，它們往往根據(jù)實際應用的需要存在不同的權重，比如對于某些應用來說，兩個字符串中相同單詞數(shù)量比不同單詞數(shù)量更能說明字符串的相似程度，那么我們必須將q的權重提高，重新計算相似程度。

我們設對應q,r,s三個變量的權重分別是Kq, Kr, Ks ，則公式1 演進為

相似度=Kq*q/(Kq*q+Kr*r+Ks*s) (Kq > 0 , Kr>=0,Ka>=0) 公式2

回到上面問題，對于上一節(jié)的兩個字符串，如果我們設置Kq = 2 ,Kr=Ks=1，則更加公式2

它們的相似度為 2*1/ (2*1+1*1+1*0) = 66.7%

同義詞問題

在語言中，同義詞是經常遇到的問題，如果兩個字符串中存在同義詞，其相似度又如何計算呢。

對于同義詞問題，我們要從分詞過程中來解決。首先我們需要構建一個同義詞對照表，將同義詞對應到一個等價單詞，在對字符串分詞后對字符串中的所有單詞到同義詞表中查找，如果存在，則替換為對應的等價單詞，這樣分詞后，兩個字符串中的同義詞就指向了相同的單詞。

比如存在同義詞表如下：

單詞	等價詞
也許	也許
或許	也許
可能	也許

字符串1：他也許不來了

字符串2：他可能不來了

分詞后二元屬性關系表如下：

字符串/屬性	他	也許	不來	了
他也許不來了	Y	Y	Y	Y
他可能不來了	Y	Y	Y	Y

不難看出，兩個字符串的相似度為 100%

同音不同義

在中文網絡環(huán)境中，由于大多數(shù)網絡文章的作者都是采用拼音輸入法輸入漢字，經常會出現(xiàn)輸入同音不同義的文字錯誤，為了糾正這種錯誤，我們可以考慮采用漢語拼音的方式進行分詞，也可以綜合分詞，也就是先正常分詞，在拼音分詞，字符串的分詞結果去兩者的并集。

小節(jié)

確定字符串相似度的方法很多，本文根據(jù)作者多年從事數(shù)據(jù)挖掘工作的經驗結合數(shù)據(jù)挖掘理論提出的相關解決方案，可以較好的解決中文字符串分析中的相似度比較問題。但技術的發(fā)展是不斷前進的，相信未來還會有更好的方法來解決中文字符串相似度比較問題。讀者如果有更好的想法或者發(fā)現(xiàn)本文算法中的不足，非常歡迎和本文作者聯(lián)系。

參考文獻

《數(shù)據(jù)挖掘概念與技術》 機械工業(yè)出版社 Jiawei Han, Micheline Kamber