海明距离

—184—

模糊匹配中的匹配度计算方法

李红明，秦贵和，郝勃，冀进朝

(吉林大学计算机科学与技术学院，长春130012)

摘要：介绍模糊推理机制中用于解决普通模糊匹配冲突问题的常用方法，包括海明距离和指数法。基于指数法提出类指数法和绝对值差

积法，根据相似度的定义证明其正确性。算例比较结果表明，绝对值差积法的性能优于其他3种方法。

关键词：模糊匹配；冲突消解；匹配度；指数法；海明距离

CalculationMethodofMatchingDegreeinFuzzyMatching

LIHong-ming,QINGui-he,HAOBo,JIJin-chao

(CollegeofComputerScienceandTechnology,JilinUniversity,Changchun130012)

【Abstract】Thispaperintroducesthecommonmethodsforsolvingthecollisionproblemofgeneralfuzzymatchinginfuzzyreasoningmechanism,

entstheexponent-likemethodandtheabsolutevaluedifferenceandproduct

mecalexample

comparisonresultsshowthattheabsolutevaluedifferenceandproductmethodhashigherperformancethanthethreeothermethods.

【Keywords】fuzzymatching;collisionresolution;matchingdegree;exponentmethod;Hamingdistance

计算机工程

ComputerEngineering

第36卷第6期

Vol.36No.6

2010年3月

March2010

·人工智能及识别技术·文章编号：1000—3428(2010)06—0184—02

文献标识码：A

中图分类号：TP391

1概述

在专家系统中，数值式的不确定推理包括基于概率的不

确定性推理和基于模糊逻辑的模糊推理。模糊性是事物不确

定性的重要方面，在由模糊性引起的不确定性知识解释中，

基于概率论的推理不够合理。文献[1]提出的模糊集理论以及

在此基础上发展起来的模糊逻辑弥补了上述不足。随着模糊

理论的成熟，模糊推理已成为专家系统的研究热点并得到广

泛应用。文献[2]提出直觉模糊逻辑，近年来，直觉模糊逻辑

中的相似度、相异度等被众多学者研究，直觉模糊逻辑是对

普通模糊逻辑的有效扩展[3]，但普通逻辑推理在工程上有一

定实用性，仍然具有研究价值。

在基于规则的推理中，规则的前提条件通常和用户给定

证据不完全一致，因此，在决定选择哪条规则进行推理时，

要将证据与规则的前提进行匹配。采用阈值法进行筛选时，

通常会有多条规则满足条件，即出现冲突。冲突消解策略一

般包括按匹配度排序、平均加权值排序、广义语序排序等。

匹配度常用的表示方法有贴近度、语义距离、相似度等[4]。

随着模糊理论的广泛应用，人们相继提出很多新方法，如接

近匹配排序[5]、差额降序法[6]等。本文在指数法和海明距离的

启发下，提出了2种新的匹配度计算方法。

2常用匹配度计算方法

常用的匹配度计算方法有贴近度、语义距离、相似度。

语义距离分为海明距离、欧几里德距离、柴可夫斯基距离和

切比雪夫距离。相似度包括最大最小法、算术平均法、几何

平均法、相关系数法、指数法。贴近度和相似度越大，匹配

度就越大，语义距离越小，则匹配度越大。下文主要介绍海

明距离和指数法。

设U={µ1

,µ

2

,µ

3

,µ

4

}为论域，A,B,C,D为U上表示一定

模糊概念的模糊子集。模糊知识包括：R1:ifxisAthenyisH1;

R2:ifxisBthenyisH2;R3:ifxisCthenyisH3。初始证据

为：xisD。

2.1海明距离

A,B的海明距离可以表示为

()

1

1

,()()

n

AiBi

i

dAB

n

µµµµ

=

=×−

∑

上式适用于有限集的情形，如

A=0.3/µ

1

+0.5/µ

2

+0.4/µ

3

+0.3/µ

4

B=0.5/µ

1

+0.5/µ

2

+0.6/µ

3

+0.4/µ

4

此时海明距离为

1

(,)(0.5-0.30.5-0.50.6-0.40.4-0.3)0.25

4

dAB=+++=

2.2指数法

A,B的相似性可表示为

1

()()

(,)e

n

AiBi

irAB

µµµµ

=

−−∑

=

以1.1节数据为例，得

(0.200.20.1)(,)e0.61rAB−+++==

32种新的匹配度计算方法

从指数法公式可以看出，对任意的2个模糊子集A,B，

使用海明距离和指数法得到的结果完全一致，即d(A,B)越大，

则r(A,B)越小，匹配度越小。本文在指数法的基础上提出

2

种新方法。

贴近度的定义如下：设()FU为论域

12

{,,,}

n

Uµµµ="，

基金项目：吉林省科技发展计划基金资助项目(20071423)；吉林大学

“985工程”研究生创新基金资助项目(20080233)

作者简介：李红明(1986－)，女，硕士研究生，主研方向：智能控制

与嵌入式系统；秦贵和，博士生导师；郝勃，本科生；冀进朝，

硕士研究生

收稿日期：2009-11-01E-mail：abillity.2003@