博文
基于多层特征的字符串相似度计算模型
|
章成志
摘 要： 针对计算字符串相似度传统方法的不足之处，提出以相似元作为字符串的基本处理单元，综合考虑相似元的字面、语义及统计关联等多层特征的字符串相似度计算方法；对常规计算方法中存在的，由相似元排序引起的相似元位置信息丢失问题进行了修正。实验结果表明该算法的有效性，并且对句子间、段落间的相似度计算有启发意义。
关键词： 字符串相似度；相似元；字面相似度；语义相似度；多特征度量
A Model for Chinese String Similarity Based on Multi-Level Features
Zhang Chengzhi
Abstract: String similarity computation has been used widely in the field of Chinese information processing. In this paper, a unifying model for string similarity computation is presented based on multi-level features. The novel approach of similarity computation uses the literal, semantic and statistical relative features of strings. The method can take advantage of the normal approaches to improve the computation accuracy. Experiments show that the proposed method is an effective solution to the Chinese string similarity computation problem, and it can be generalized to measure the similarity of other components of Chinese text, such as sentence, paragraph etc.
Key words: Chinese string similarity, similarity unit, multiple-features measuring, literal similarity, semantic similarity.
1 引 言
在中文信息处理领域中，计算中文字符串，如词语、词组等的相似度计算对词典编纂、基于实例的机器翻译、信息检索、自动问答、信息过滤等都具有重要的作用。此外，字符串序列相似度计算在异构数据库操作[1]、音乐乐谱分析、基因序列分析等方面中也有较好应用。
现有的计算字符串相似度的方法按照计算所依据的特征的不同，可以划分为三种方法，分别为：基于字面相似方法、基于统计关联方法、基于语义相似方法。其中，基于字面相似的计算方法主要有基于编辑距离的计算方法[2]和基于相同字或词的方法[3]。基于统计关联的方法主要有基于词汇共现[4]、向量空间模型[5]、基于部分语法分析[6]等。针对语料库存在的数据稀疏问题，改进的基于大规模语料库的方法主要有PMI-IR[7]和各种平滑算法[8]。基于语义的方法主要是利用释义词典[9]或者一些大规模的本体[10][11]对词汇进行语义上相似度计算。
基于字面的方法简单，易于实现，但使用时不够灵活并且没有考虑词语的同义替换；基于统计的方法可以得到许多仅靠人无法观测到的字符串间的有效关联，但该方法依赖于训练所用的语料库，受数据稀疏和数据噪声的干扰较大；基于语义的方法有时可以直观地计算出字面上不相似，并且统计关联较小获得的词汇间的相似度，但本体资源通常是由手工构建的，需耗费大量时间和人力。
本文综合利用这三种方法的优点，克服各自的缺点，提出计算字符串相似度的统一模型，即：以相似元作为中文字符串的基本处理单元，综合考虑相似元的字面、语义及统计关联等多层特征信息，建立基于相似学[12]、多层特征度量的字符串相似度计算统一模型，并对常规计算方法中存在的，由相似元排序引起的位置信息丢失问题进行了修正。
2 相似度计算的统一建模
2.1 相似度计算数学描述
传统的方法大都是从字符串的某一个特性上去计算相似度的，而结合字符串的字面特征、统计关联特征、语义特征等多层特征信息来计算字符串的相似度的还未见诸于报道。在对中文字符串相似度计算建立统一模型之前，先给出几个相关的说明。
Ω：中文字符串集合；
S：Ω的子集，即S
Ψ：语义词典或称义类词典，字符串切分用词条集合，每个词条有相应的义类编码，Ψ
S1、S2：给定的两个字符串，其中：
S1＝｛a1，a2，…，ai，…，aM｝，
i∈[1，M]，S1所含元素数量为M；
S2＝｛b1，b2，…，bj，…，bN｝，
j∈[1，N]，S2所含元素数量为N；
S1、S2中的元素可为单字或经语义词典（或本体）切分的义类词或其对应的义类编码[11]。例如：字符串“计算机控制”，元素完全为单字时，字符串可表示为：{计，算，机，控，制}，若经过语义词典（含无义类编码的词条）切分（本文以《同义词词林》[13]为语义体系），则字符串可表示为｛Bo010127，Je090101｝。
si: 相似元；在S1、S2中识别相似特征，具有相似特征的元素被称为相似元素，相似元素在S1、S2间形成的相似单元，简称相似元，记为s(ai，bj)，简记为sij。字符串S1中的元素ai相似于字符串S2中元素bj，元素ai与bj为相似元素，构成相似元s(ai，bj)，对字符串S1，S2按照相似优先排序，得：
S1’＝｛a1，a2，…，ai，…，aM｝，
S2’＝｛b1，b2，…，bj，…，bN｝，
此时，字符串间的相似元素为ai，bi，得相似元 s(ai，bi)，简记为si。
定义1：相似元数值为S1中元素ai与S2中对应相似元素bi的相似程度，记为q(si)。
定义2：字符串相似度为字符串S1、S2的相似程度，记为Sim(S1，S2)。
字符串相似度Sim(S1，S2)的一般数学描述如下：
Sim(S1，S2) = f (M，N，K，q(si)) ，(i∈[1，K]) (1)
即：相似度Sim(S1，S2)是S1中的元素
数量M、字符串S2中的元素数量N、字符串S1，S2间相似元数量K、反映每一相似元素相似程度的大小的相似元数值q(si)的多元函数。
根据相似学中测度相似性系统的相似度基本方法[12]，计算字符串的相似度，一般考虑两个方面的影响，即：相似字符的数量和相似字符的相似元数值大小，给出其计算公式如下：
(2)
其中，λi为反映相似元si对字符串相似度的影响程度的权值，λi∈[0，1]，且
。
若考虑相似特征数目相似程度Qn和特征相似程度Qs对相似元素的整体相似度有互补性时，可对Qn与Qs赋不同的权值，分别为α，β，且有：α，β∈[0，1]，α+β=1，则有：
(3)
2.2 字面相似度算法的改进
若只考虑字符串的字面特征，即字符串S1，S2中当其中的两个元素ai，bi在字面上完全匹配时，就认为ai，bi为相似元素，且相似元对字符串相似度的影响程度均等，即q(si)＝1，且λi＝1/K，根据公式（2）有：
（4）
公式（4）为常见的，最简单的基于字面的字符串相似度计算方法。例如，通过公式(4) 计算“计算机”与“微机”的相似度为Sim(“计算机”，“微机”)＝0.25。由于公式(4)没有考虑到字符串中相似元素的位置信息，使得计算的结果不可靠，例如：Sim(“计算机”，“机计算”)＝1。
根据公式（3），设置α，β的经验值为：α=0.6，β＝0.4，考虑到中文字符串“语义重心后移”的特点，则定义λi如公式（5）所示。
（5）
其中i，j分别表示相似元sij为字符串S1的第i个相似元，S2中的第j个相似元。则公式(3)转换为：
（6）
可以看出，公式（6）以及其他变种形式[14]在计算字符串相似度时，依旧没有完全考虑字符串中相似元的位置信息，例如：通过公式（6）及其他变种形式[14]，计算字符串“机微”，“微机”的相似度时，有：Sim(“机微”，“微机”)= 1。造成公式(4)、(6）计算结果与事实不符的根本原因在于：假设相似元字面相似数值q(si)等于“1”是不合理的。由于相似元数值的计算，除了与相似元素字面完全匹配有关，还应考虑相似元素在字符串间位置的差异性。
本文通过引入字符串相似元素的平移距离Distance(sij)=| i-j |对q(si)进行修正，| i-j |表示字符串S1，S2左对齐或右对齐后，相似元素sij在字串S1的位置i与在字串S2的位置j的差的绝对值。考虑平移代价因素，q(si)可通过公式（7）计算得到：
（7）
公式（3）则转化为：
(8)
根据公式(8)计算字符串“机微”，“微机”的相似度为：Sim(“机微”，“微机”)= 0.8。
另外，值得注意的是，字面相似度和词面相似度只是相似元素的颗粒度不同，它们在计算相似度的方法上，都是依据字面特征的，因此从本质上说，它们是一致的。
2.3 多层特征的相似元数值计算
求字符串相似度中关键的一个步骤为相似元数值q(si)的计算。相似元的获取是计算相似元的必要条件，但实际上，由于所考察对象相似性的复杂性，相似元很难获取。本文采用一种简化的策略，将字符串间元素的某一特征，作为判断其是否为相似元的根据，即：给定一阈值δ，以元素某一特征为考察对象，在不考虑字符串间元素位置差异的情况下，元素ai，bi在该特征上的相似度有：q(si)≥δ，则ai，bi为相似元素。本文在判断两元素是否为相似元素时，所依据的特征为字面特征、语义特征及统计关联特征。
对于语义特征，设置δ1＝0.25，即对于字符串中经义类词典Ψ切分后得到的义类编码Code[i]、Code[j]，若不考虑字符串间元素位置差异的情况下，Code[i]、Code[j]间的相似度大于1/4，则认为这两个元素是相似的。q(si)1计算如下：
(9)
其中n为两语义编码从根结点出发，开始不同的层数，n∈[1，5]。
对于字面特征，不考虑字符串间元素位置差异的情况下，设置δ2＝1，即针对字面特征有，q(si)2通过公式(7)求得。若仅仅考虑字面特征，则字符串的相似度计算就退化到字面相似度计算，即公式（6）的情形。
对于统计关联特征，在不考虑字符串间元素位置差异的情况下，设置δ3＝0.5。统计关联程度是从统计分布角度来度量元素之间的相似程度，预先通过训练语料，对目前暂时无法归类的词条，计算它们与语义词典中义类词语之间的互信息，即：对于无法归类的词条ai与义类词典Ψ中的词条bj，它们之间的互信息通过公式(10)得到：
(10)
对于ai，bj，若它们的互信息MI(ai，bj)大于给定的阈值δ3，则认为它们是相似的，将计算结果保存在统计关联表，记为：Tab_Relation。在计算字符串中两元素ai，bj的统计关联相似度时，直接从Tab_Relation中查找，若元素ai，bj∈Tab_Relation，则表明两元素相似，q(si)3计算如下：
（11）
其中：Max(MI)为Tab_Relation中词语互信息最大值。
对于每一相似元si对字符串相似度的影响程度的权值λi，在考虑了多层特征后，很难估计具体的权值。本文作平均权重处理，即：λi＝1/K，K为相似元的数量。
2.4 字符串相似度计算算法描述
对于给定的中文字符串S1，S2，利用公式（3）计算它们之间的相似度。对于字符串S1＝{a1，a2，…，ai，…，am｝，S2＝｛b1，b2，…，bj，…，bn｝若不完全相同，则利用义类词典Ψ对S1，S2进行最大匹配法切分后，得到，S
3 实验及结果
本文进行两组实验，每组实验分别进行基于字面、语义及多层特征方法的字符串相似度计算。第一组测试为封闭测试，以中文词语作为测试对象，
进行中文词语对应的同义词搜索测试实验。测试步骤为：事先从领域知识库中抽取人工认定的具有较高相似度的经济、军事类词对各100对。理后，然后将这些词打乱，用机器自动生成同义词对近40000对，然后分别用基于字面、基于语义、基于多层特征的相似度算法，将相似度大于0.66的词对与原来的词对相比较。测试结果如表1所示。
第二组测试为开放测试，即：以排列无序的关键词集合作为开放测试集，在开放测试集上进行同义词对的搜索测试实验。测试步骤为：从政治、经济两类别的各取关键词389，1200个，将每一类的词对打乱，然后进行相似度的计算，取出阈值大于0.66的词对，并对这些词对进行人工识别。根据相似度大小区分出同义词、准同义词、过于专指下位类词、相关词、不相关词。前三类词视为同义词，后两类次为非同义词，测试结果如表2所示。
从表1的各项统计数据可以看出，通过中文复合词对应的同义复合词搜索实验，使用基于多层特征的相似度计算方法，同义词对的召回率达到92.5%，而基于语义的方法，为87%，基于字面的方法，召回率仅为44.5%，这表明了在进行同义词对搜索的召回率上，基于多层特征的相似度计算优于单纯基于字面的和基于语义的计算方法。
从表2的各项数据也可以看出，依据基于多层特征的相似度计算方法进行同义词识别，识别率为29.23％，而基于语义的方法为25.52%，基于字面的方法，正确率仅为10.40%，表明基于多层特征的相似度计算方法，在识别同义词上正确率高于基于字面和基于语义的计算方法。这说明基于多层特征的计算方法确定词汇同义关系效率优于基于字面的和基于语义的相似度计算方法。此外，基于多层特征方法搜索出相似度高于阈值的相关词词对的比率为80.08，也高于其它两种方法的搜索结果，比率分别为72.15%、60.78%，这表明：该方法用于词语的聚类上，优势比较明显。
4 结束语
本文以相似元作为字符串的基本处理单元，综合考虑相似元的字面、语义及统计关联等多层特征，建立字符串相似度计算的统一模型，提出基于多层特征的字符串相似度计算方法；并对常规计算方法中存在的，由相似元排序引起的字符串结构信息丢失问题进行了修正。实验结果表明基于多层特征计算字符串相似度方法的有效性，并且对对句子间、段落间的相似度计算有启发意义。对字符串相似度的研究涉及到语义学相似学、系统论等许多相关知识，本文依据现有的语义体系还存在一些问题，相似元权值设置等需要进行进一步的深入研究。
参 考 文 献
[1] Santini S, Jain R. Similarity measures. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1999, 21(9):871~883.
[2] Monge AE, Elkan CP. The field-matching problem: algorithm and applications. Proceeding of the Second Internet Conference on Knowledge Discovery and Data Mining, Oregon, Portland, 1996, 8:267-270.
[3] Nirenburg S, Domashnev C, Grannes DJ. Two approaches to matching in example-based machine translation. Proceeding of TMI-93, Kyoto, Japan, 1993, 7:47-57.
[4] http://metadata.sims.berkeley.edu/index.html, 2003.
[5] Crouch CJ. An approach to the automatic construction of global thesauri. Information Processing and Management, 1990, 26(5):629~640.
[6] Lin DK. Automatic retrieval and clustering of similar words. Proceedings of the 17th International Conference on Computational Linguistics and 36th Annual Meeting of the Association for Computational Linguistics, Montreal, 1998, 6:768~774.
[7] Peter D. Turney. Mining the web for synonyms: PMI-IR versus LSA on TOEFL. Proceedings of the 12th European Conference on Machine Learning, Freiburg, 2001, 6:491~502.
[8] Weeds J. The Reliability of a similarity measure. Proceedings of the Fifth UK Special Interest Group for Computational Linguistics, Leeds. 2002,1,33-42.
[9] Pierre P. Senellart. Extraction of information in large graphs; Automaitc search for synonyms. Masters Intership Reports. University catholique de Louvam, Louvain-la-Neuve, Belgium, 2001, 1~17.
[10] Resnik P. Semantic similarity in a taxonomy: an information-based measure and its application to problems of ambiguity in natural language, journal of artificial intelligence research.1999, 11: 95~130.
[11] Li SJ, Zhang J, Huang X, Bai S. Semantic computation in Chinese question-answering system, Journal of Computer Science and Technology, 2002, 17(6):933~939.
[12] Zhou ML. Some concepts and mathematical consideration of similarity system theory. Journal of System Science and System Engineering, 1992, 1(1):84~92.
[13] 梅家驹. 同义词词林. 上海: 上海辞书出版社, 1983.
[14] 吴志强. 经济信息检索后控制词表的研制:[学位论文], 南京: 南京农业大学信息管理系, 1999.
注：本文发表于《情报学报》2005年第6期。
https://blog.sciencenet.cn/blog-36782-16192.html
上一篇：基于样本加权的文本聚类算法研究
下一篇：基于知识空间的智能信息检索模型研究
