中文字符串的相似度.doc

中文字符串的相似度如何确定中文字符串的相似度(ZT)(2008-06-14 09:19:27) 转载标签:中文字符串相似度分量权重 it 摘要在数据挖掘的研究中,我们往往需要判断文章是否雷同, 对类似文章或短句进行归类处理等, 这其中就会遇到这样的问题: 如何确定两个字符串之间的相似程度。本文综合作者的实际工作经验和数据挖掘理论, 结合中文字符串特性介绍一套相对完整的方法,以解决上述问题.。分析最简单的问题求解字符串由一组不同含义的单词组成, 它不同于数值型变量, 可以用一个特定的数值来确定它的大小或位置, 所以用何种方式来描述两个字符串之间的距离,成为了一个值得探讨的问题。通常情况下,用于分析的数据类型有如下几种:区间标度遍历、二元变量、标称型变量、序数型变量、比例标度型变量、混合类型变量等。综合这些变量类型, 本文认为字符串变量更适合于归类于二元变量, 我们可以利用分词技术将字符串分成若干个单词, 每个独立的单词作为二元变量的一个属性。我们把所有单词设定为一个二元变量属性集合 R ,字符串 1 和字符串 2 的单词包含于这个集合 R 。设 q 是字符串 1 和字符串 2 中都存在的单词的总数, s 是字符串 1 中存在,字符串 2 中不存在的单词总数,r 是字符串 2 中存在, 字符串 1 中不存在的单词总数, t 是字符串 1 和字符串 2 中都不存在的单词总数。我们称 q,r,s,t 为字符串比较中的 4 个状态分量。如图 1 所示: 由于两个字符串都不存在的单词对两个字符串的比较没有任何作用, 所以忽略 t ,于是我们采用非恒定的相似度评价系数(ard 系数) 来描述两个字符串见的相异度表示公式为相异度= r+s / (q+r+s) ,不难推断,他们的形似度公式为相似度=q/(q+r+s) 公式 1 图1 字符串关系描述例如如下两个字符串串: 字符串 1 :非对称变量字符串 2 :非对称空间他们的二元属性关系表为: 字符串/ 属性非对称变量空间非对称变量 YYYN 非对称空间 YYNYY 表示存在该单词属性, 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 前进前进 YY 前进 YN 相应的 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) = % 来源: (http://blog./s/) - 如何确定中文字符串的相似度(ZT)_ 土豆爸爸_ 新浪博客同义词问题在语言中, 同义词是经常遇到的问题, 如果两个字符串中存在同义词, 其相似度又如何计算呢。对于同义词问题, 我们要从分词过程中来解决。首先我们需要构建一个同义词对照表, 将同义词对应到一个等价单词, 在对字符串分词后对字符串中的所有单词到同义词表中查找, 如果存在, 则替换为对应的等价单词, 这样分词后, 两个字符串中的同义词就指向了相同的单词。比如存在同义词表如下: 单词等价词也许也许或许也许可能也许字符串 1 :他也许不来了字符串 2 :他可能不来了分词后二元属性关系表如下: 字符串/ 属性他也许不来了他也许不来了 YYYY 他可能不来了 YYYY 不难看出,两个字符串的相似度为 100% 同音不同义在中文网络环境中, 由于大多数网络文章的作者都是采用拼音输入法输入汉字, 经常会出现输入同音不同义的文字错