数决定。通过k次的迭代,可以获得匹配错误最小的两图之间的节点匹配,并计算出其匹配错误。
首先必须定义几个矩阵分别用来表示节点的错误差,可能的节点匹配对等。接着还要定义节点匹配错误的计算公式和边匹配错误计算公式,最后依据匹配错误的大小来确定两个图的相似度。将这种图匹配算法应用于图像检索,取得了很好的实验效果如图1-7所示的是两个图像的属性图结构。
通过计算可以得到图1-7示例中两幅图像的匹配错误,并依此进行图像的搜索或匹配。但同时可以发现该算法存在不足之处,它无法给出两幅图像的确切的相似度,仅能给出其匹配错误,无法定量的描述其相似程度,这也是该算法应要进一步改善的地方
1.8 基于本体的语义相似度测度算法
基于本体的语义相似度算法主要包括概念信息量法，语义距离法、基于属性的语义相似度、混合式语义相似度等方法。
1.8.1 概念信息量法：
概念信息量法以信息论和概率统计为基础，需要进行大量的文集统计工作。
1.8.2 基于概念属性的相似度计算
在本体结构中，概念的属性是决定语义相似度的重要因素［１４］。当两个概念拥有的相同属性越多，表明这两个概念间的语义相似度越大。概念属性的相似度计算公式为：
SimAtt(S,F)?Count(att(S)?att(F))（1）
Count(att(S)?att(F))其中，att(S)表示实体S属性的集合；att(F)表示实体F属性的集合；Count()表示统计
出的属性个数。若实体的某种相应的性质不存在时，则不用表示S、F在该性质上的相似度。
1.8.3 语义距离
语义距离是指本体结构中任意两个概念节点之间的最短路径长度。
基本假设如下：两概念的语义距离越大，其相似度越低，反之相似度越高。
设实体a、b分别对应语义知识库中的概念con1、con2，记sim_sem(con1,con2)为二者的语义相似度，因此sim_sem(a,b)=sim_sem(con1,con2)。
设Dist(con1,con2)为本体中两概念的最短语义距离，则语义相似度与语义距离之间存在如下关系：
（1） 当Dist(con1,con2)=0时，sim_sem(con1,con2)=1，表示完全相同。
（2） 当Dist(con1,con2)等于无穷大时，sim_sem(con1,con2)=0，表示完全不相似或不
相关。
用公式表示如下：
sim_sem(a,b)=sim_sem(con1,con2)=d（4）
Dist2(con1,con2)+d基于语义距离的语义相似度算法中,影响语义的主要因子有:概念深度,概念密度,关系类型,关联强度和概念属性等。本文主要对前三者进行介绍。
概念深度：
概念深度指概念节点与根节点的最短路径中包括的边数.概念深度对语义相似度的影响基于以下思想:以“IS-A”关系建立的本体概念树中,每一概念是其上位概念的细化,越到下层,概念所指的对象越具体,内涵越丰富.同等语义距离下,两个概念节点的深度越大,相似度越高,反之相似度越低;相反,同等语义距离下二者的概念层次差越小,则二者的语义相似度越高,反之相似度越低.
定义Dep(con)为概念con的深度;设root为根节点,令其深度为１,即Dep(root)＝１. 任意非根节点概念con的深度Dep(con)＝Dep(Parent(con))＋１,其中Parent(con)为con的直接上位概念节点。
Dep(tree)为本体树的深度，Deep(tree)?max(Dep(coni)),(i?1,2,...n),其中n 为概念的总数,coni为本体中的任意概念.
因此,概念深度对语义相似度影响因子Ps的计算如式(５),且满足Ps∈(０,１]
Ps?Dep(con1)?Dep(con2) (5)
Dep(con1)?Dep(con2)?2Dep(tree)概念密度:
本体层次中,局部区域概念密度越大,说明该区域概念细化程度越大,该处概念分类越具体,在其他因素相同的条件下,直接概念子节点间的语义相似度就越高.
定义Child(con)为概念con所包含的直接子节点的个数;Child(tree)为本体树中各概念节点中子节点数的最大值.设两个概念con１和con２最近共同祖先为
cona,其直接子节点的个数
为Child(cona);则概念密度对语义相似度影响因子Pm计算如式(６),且满足Pm ∈(０,１]
Pm?Child(cona)（6）
Child(tree)
关系类型：
本体中概念通过各种关系联系在一起,不同关系类型对概念语义相似度的影响也有所不同.如上下位的“同义关系”所表征的语义相似度应大于“整体--部分”关系所表征的语义相似度.在关系类型不多的情况下,可采用专家打分的方法来确定关系类型的语义强度.设Pr 为关系强度,则Pr∈(０,１]
1.8.4 改进的语义相似度算法
改善算法1：sim_sem(a,b)?(d)??Ps??Pm??Pr? (7) 2Dist(con1,con2)+d式中，?,?,?,?为调节因子，且满足????????1。由于语义距离在相似度计算中占主导地位,其他因子起辅助作用,所以?的权重相对较大,而?、?、?的权重相对较小.该语义相似度模型中权重大小的设置,除遵循上述原则外,可采用与用户交互或大样本数据进行训练的方法对初始权重进行修正,以满足不同上下文应用环境的要求.
改善算法2：
Weight(S,F)???WeightType(S,F)???WeightDepth(S,F)???WeightDensity(S,F)
()
其中，Weight(S,F)为有向边权重；WeightType(S,F)是概念的不同的（关系类型）对应的语义距离的权重；WeightDepth(S,F)是概念结点S、F之间的（概念深度）语义距离权重；
WeightDensity(S,F)表示概念节点S、F之间有向边（概念密度）的权重关系；α、β、γ
是可调节因子，且α＋β＋γ＝１。
由于有向边权重的大小与概念节点间的距离成反比，因此权重大小与有向边语义距离的关系如下：
Dist(S,F)=
1 (3)
Weight(S,F)其中，Dist(S,F)为概念节点间的距离。
综上所述，可得到的改进的语义距离相似度计算方法如下：
sim_sem(a,b)=sim_sem(con1,con2)=?Dist(con1,con2)+?2（4）
其中，SimDist(S,F)为语义距离相似度；?为可调节因子，且为大于0的实数。
1.8.5 语义相似度计算
将基于语义距离的方法与基于属性的方法相结合，可以得到实体语义相似度计算公式:
Sim(S,F)=?1?SimAtt(S,F)+?2?SimDist(S,F)（5）
其中，Sim(S,F)为实体语义相似度，?1+?2?1，且?1、?2大于0。
1.9 文本语义相似度模型
1.9.1 基于V SM的相似度模型
1.9.2 基于WordNet的相似度模型
1.9.3 基于FrameNet的相似度模型