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

作者：肖波

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

Email：blog.eaglet@gmail.com

2007/4 南京

摘要

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

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

分析

     最簡單的問題求解

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

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

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

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

相異度 = 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%

單詞重復問題求解

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

字符串1：前進前進

字符串2：前進

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

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

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

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

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

狀態分量權重 

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

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

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

回到上面問題，對于上一節的兩個字符串，如果我們設置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%

同音不同義

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

小節

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

參考文獻

《數據挖掘概念與技術》 機械工業出版社 Jiawei Han, Micheline Kamber