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

作者：肖波

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

Email：blog.eaglet@gmail.com

2007/4 南京

摘要

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

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

分析

     最簡單的問題求解

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

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

       綜合這些變量類型，本文認(rèn)為字符串變量更適合于歸類于二元變量，我們可以利用分詞技術(shù)將字符串分成若干個單詞，每個獨(dú)立的單詞作為二元變量的一個屬性。我們把所有單詞設(shè)定為一個二元變量屬性集合R，字符串1和字符串2的單詞包含于這個集合R。設(shè)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 字符串關(guān)系描述

例如如下兩個字符串串：

字符串1：非對稱變量

字符串2：非對稱空間

他們的二元屬性關(guān)系表為：

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

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

那么對應(yīng)的

s = 1; q = 2; r = 1

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

單詞重復(fù)問題求解

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

字符串1：前進(jìn)前進(jìn)

字符串2：前進(jìn)

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

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

字符串/屬性	前進(jìn)1	前進(jìn)2
前進(jìn)前進(jìn)	Y	Y
前進(jìn)	Y	N

相應(yīng)的 q = 1, s=1, r= 0

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

狀態(tài)分量權(quán)重 

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

我們設(shè)對應(yīng)q,r,s三個變量的權(quán)重分別是Kq, Kr, Ks ，則公式1 演進(jìn)為

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

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

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

同義詞問題

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

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

比如存在同義詞表如下：

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

字符串1：他也許不來了

字符串2：他可能不來了

分詞后二元屬性關(guān)系表如下：

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

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

同音不同義

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

小節(jié)

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

參考文獻(xiàn)

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