区域相似度

区域相似度（精选八篇）

区域相似度 篇1

随着计算机与网络的发展以及相机等数码产品的普及, 图像的种类和数量也在飞速的增加[1]。如何能够有效地组织和处理大量的图片信息并从其中检索出用户需要的图片成为一个重要的问题。多媒体信息检索技术[2]是解决此类问题的核心技术。在多媒体信息检索技术当中, 图像检索技术根据检索方法的不同可以分为两种:一种是基于文本的图像检索技术[3], 另外一种是基于内容的图像检索技术[4]。基于文本的图像检索技术通过利用人工标注的关键词表示图像, 把图像检索转化为相关关键词的查询与匹配。基于文本的图像检索技术的优点是方便、检索速度快, 用户只需要输入相关的关键词就可以查询并得到相关的结果。但是基于文本的图像检索技术需要人工对图像标注关键词, 工作量大。基于内容的图像检索技术依赖于图像的视觉内容, 譬如图像的颜色、纹理和形状等。通过测量图像视觉内容的相似度检索图像。由于图像视觉内容特征的提取与匹配可以由计算机自动完成, 因此基于内容的图像检索技术得到了广泛的研究与应用。

虽然基于内容的图像检索技术取得了很多的研究成果, 但是由于基于内容的图像检索技术存在语义鸿沟[9], 即低层视觉特征, 这些特征有形状、颜色、纹理, 而其对用户的查询做不到完全的反映和匹配, 如何完美地实现基于语义的图像检索仍是一个问题。由于用户更习惯于用文字来表达查询需求, 并且现有的互联网搜索引擎提供基于文本的图像检索, 但是人工标注又是一项相当费时费力的工作, 由此催生了自动图像标注技术的发展[10]。

基于区域的图像检索技术 (Region-based image retrieval technology) [5,6,7,8]通过图像分割技术将一幅图像分割为若干个同质区域 (Homogenous Region) , 由于每个同质区域的语义相对比较单一, 因此能够准确地描述图像的语义内容。其次在每一个区域使用局部的特征来描述, 综合每个区域的特征对图像自动标注。然后基于固定的相似性度量标准, 完成图像的检索。

在这篇论文中, 提出了一种基于区域匹配的图像标注方法。首先, 通过N-Cut方法把图像分割成若干个同质区域, 然后用k-means方法对分割后的区域进行聚类。在每一类中, 选择具有代表性的若干区域, 对其进行人工标注关键词。最后用所选择区域的颜色特征和纹理特征的平均值数值化关键词。对于测试图片, 计算分割后区域的颜色特征和纹理特征的值。如果区域的特征值与关键词的距离小于一定的阈值, 就用这个关键词标注图像。

1 图像特征提取与表达

早期的基于内容的图像检索技术, 通常用全局特征表示图像。由于全局特征表示图像存在不足, 一些研究提出了区域特征、局部特征等。图像区域的选择可以分为三种:固定划分法、分割法以及显著点法。固定划分法使用统一的方法分割图像, 不考虑图像的视觉内容差异。Monay和GaticaPerez提出一种方法, 这种方法把每幅图像分割成三个固定的区域, 即图像的上半部分、中心以及下半部分[11]。文献[12-13]提出了一种更简单的方法, 每一幅图像被平均分为相同大的矩形区域, 即图像栅格化划分。

分割方法的目的是把图像分割成若干个同质区域, 每一个区域对应于一个对象。研究人员已经提出了很多知名的分割算法, 其中, N-Cut算法[14]和JSEG算法[15]是具有代表性的分割算法。

特征提取的主要任务是提取能够表示图像可视内容的特征信息。在本论文中, 主要提取了图像的颜色特征和纹理特征, 并通过一定的算法得到图像的颜色特征值和纹理特征值。

1.1 颜色特征

由于图像中包含大量的颜色信息, 颜色特征的提取方法简单, 因此, 在图像检索和标注中通常使用颜色特征作为可视内容特征[16]。颜色信息可以在不同的空间中表示, 其中最常见的空间为RGB颜色空间。RGB颜色空间是由红色、绿色以及蓝色三种基色组成, 其他颜色都可以由这三种基色线性表示。在三维空间中, 三个坐标轴分别表示红色、绿色以及蓝色, 如图1所示。

在图1中, 坐标原点表示黑色, 与原点距离最远的定点表示白色。图1中三个坐标轴分别表示三种基本颜色:红色、绿色以及蓝色。剩余的三个顶点对应于三个互补色:品红色, 蓝绿色和黄色.其余各点对应的颜色可以用该点到原点的向量来表示。

除了RGB之外, HSV[17]也是常见的描述颜色特征的颜色空间。由于HSV颜色空间为视觉感知的颜色空间, 所以本文中使用HSV颜色空间。HSV颜色空间由色调、饱和度和亮度组成。由RGB颜色空间转换成HSV颜色空间的方法如下:

其中, R, G, B∈[0, 255], H∈[0, 360], S, V∈[0, 1]。

由于转换后的HSV颜色值维度过高, 因此需要对转换后的HSV颜色值实施量化。本论文中, 将色调分为八份, 饱和度以及亮度分为三份, 量化过程如下:

通过量化, 可以得到图像的颜色特征值。

1.2 纹理特征

纹理是由物理性质, 如物体的表面的粗糙度决定。人们可以很容易地看出不同的纹理, 因此可以通过纹理得到视觉信息[18,19]。并且纹理也是一种非常重要的可视内容特征。灰度共生矩阵通过提供图像的变化幅度、间隔、灰度方向等, 能够用于计算图像对应的特征值, 图像的纹理特征可以通过这些特征值来表达, 所以该文采用灰度共生矩阵方法来完成纹理特征的提取[11]。在文献[11]里面, 总共涉及到十四种纹理特征的参数, 在这些参数里面, 选取局部平稳参数、惯性矩参数、角二阶矩参数和熵参数等四种表达能力比较强的参数。

2 关键词的数值化

在第1节中, 提到了两种代表性的图像分割算法N-Cut和JSEG, 本文中将使用N-Cut算法分割图像, 每个图像被划分成多个互不重叠的区域。分割过程如下:

在基于图论的图像分割方法中, 一幅图像被看成无向加权图, G={V, E, W}, 其中V表示节点集, 在图像中像素表示节点。E表示两两节点之间的连线。Wij表示节点之间的权重。权重可以通过计算像素、亮度或者其他信息之间的距离得到。例如, 一幅图像分割成两部分A和B:A∪B=V, A∩B=, 两个子集之间的相似度由以下公式计算:

Shi和Malikt提出了Normalized Cut描述两类间的分离度, 并且可以得到一个N-cut值作为测量标准:

其中, assoc (A, V) 表示节点A与其他所有节点权重的和。最佳分割方法是最小化以下目标函数:

通过k-means方法对分割后的区域进行聚类, 在每一类中, 选择具有代表性的若干区域, 对其进行人工标注关键词。标注后用所选择区域的颜色特征和纹理特征的平均值数值化关键词。把所标注的关键词作为种子集。对于测试图片, 则需计算分割后区域的颜色特征和纹理特征的值。如果测试图像分割后的区域特征值与关键词的距离小于一定的阈值, 就用这个关键词标注测试图像。

3 实验结果与分析

在本节中将介绍数据集以及在数据集上所做的实验, 通过分析实验结果说明本论文的方法的有效性。

3.1 数据集

本节中实验以及得到的结果所使用的数据集为Corel图像库。该图像库中包含10类图像集, 分别为建筑、花、人、马、大象、海洋、恐龙、车、食物以及山。每类图像集中有100幅图像, 选取每个类中的70幅图像作为训练集。每一幅图像通过图像分割算法被分为三部分, 然后利用k-means算法对分割后的区域聚类。选择每一类中具有代表性的区域进行人工标注。剩下的300幅图像作为测试集。

3.2 测量标准

用查全率、查准率和F1值来度量实验结果的性能。在测试集中, 包含关键词k的图像数目用Kt表示。通过标注模型的应用, 标注结果里面含有关键词k的图像有Ks个, 其中Kr表示其中正确的数目。

查全率Recall表示被正确提取的信息的比例, 计算公式为:

查准率Precision表示查询的精确度, 计算公式为:

F1是查全率和查准率的调和平均, 表示整体的性能, 其计算公式为:

3.3 实验结果分析

当用特征值数值化关键词时, 使用了三种方法:第一种方法是只使用颜色特征数值化关键词;第二种方法是只使用纹理特征数值化关键词;第三种方法是使用颜色特征值和纹理特征值数值化关键词。实验结果如表1所示。

由表1可知, 当只使用颜色特征数值化关键词时, 查全率为0.379, 查准率为0.339, F1值为0.358;当只使用纹理特征数值化关键词时, 查全率为0.356, 查准率为0.317, F1值为0.336;当同时使用颜色特征值和纹理特征值数值化关键词时, 查全率为0.494, 查准率为0.467, F1值为0.479。实验结果显示, 结合颜色特征值和纹理特征值更能够有效地自动标注图像。

当计算区域的特征值与关键词的距离时, 如果区域的特征值与关键词的距离小于一定的阈值, 就用这个关键词标注图像。实验结果与阈值的选择的关系如图2所示。

在图2中, 可以看出, 选择的阈值越小, 查准率的值越大, 查全率的值越小。当阈值选择为0.4时, 图像自动标注的实验效果最好, 查全率为0.468, 查准率为0.556, F1值为0.507。

图3为本文所提出方法的部分实验结果。

在图3中, 设置一个阈值完成标注任务, 图3 (a) 、即第一幅图像只有两个关键词海洋、沙滩符合条件, 所以只有两个标注词;图3 (b) 和图3 (c) 都有三个标注词符合条件;而图3 (d) 图中, 由于道路的特征值跟沙滩相近, 所以错误地将图中的道路标注为沙滩。

4 结束语

中文短文本语法语义相似度算法 篇2

摘要：通过分析中文短文本的特征，提出了一种基于语法语义的短文本相似度算法.该算法结合中文语句语义的相似性以及语句语法的相似性，即计算具有相同句法结构的短文本的相似度以及考虑语句词组顺序对相似度的贡献，对中文短文本相似度进行计算.实验表明，本文提出的算法在中文短文本相似度计算结果上更加接近人们的主观判断并且拥有比较好的精确率与召回率.

关键词：语法语义相似度；语句相似性计算；HowNet；语料库；语法分析；语义分析；相似度计算

中图分类号：TP391.1 文献标识码：A

文章编号：1674-2974（2016）02-0135-06

短文本相似度计算在文章查重、信息检索、图像检索、智能机器问答、词义消歧和搜索引擎等多个领域有着非常广泛的应用[1]，并在英文处理方面取得了许多实质性的成果，如机器人语音对话系统等.但是在中文信息处理中存在一些困难，例如未登录词识别问题、语法结构复杂和一词多义等[2].为此本文主要研究中文短文本（语句）相似度计算方法，并提高计算结果的精确度.

短文本相似度表示的是多个短文本（语句）之间的相似程度，属于一种度量参数，相似度值越高，则表明文本间越相似，反之越不相似[3].文本相似度包括语义和语法等方面，但是在实际中主要考虑语义层次的相似性，往往忽略了文本的语法结构对文本相似度的重要影响.

大量的研究证明短文本的语法结构对相似性的影响是非常重要的[4]，但是当前基于HowNet[5]的中文短文本相似度计算大都是分析文本的语义层次的相似性，这样就会导致计算结果的精确度和召回率都不高，为了提高相似度计算的精确度和召回率，本文以HowNet为语料库和Stanford[6]为语法解析工具，在中文短文本的语义信息基础上加入了文本的语法结构信息来研究短文本相似度计算.

1语句相似度计算

HowNet主要揭示了概念间关系及概念的属性间的关系，有关HowNet详细介绍可见参考文献[2]，在此不赘述.

义原距离定义为两个义原间最短路径上边的数目[7].义原距离反映的是两个义原的相对关系，距离越大，则表明两者相似性越低，反之则越高.义原深度定义为两个义原的最近公共父节点到根节点的层次数.义原深度反映的是两个义原在义原层次结构中的绝对关系，深度越小，表明两者越不相似，反之则越相似.

2基于语法语义的相似度计算

目前基于中文短文本的相似度算法中，大多数研究者着眼于语句的语义层次，然而组成一个语句的不单单是词语本身的语义含义，还包括语法结构，例如一个句子包含不同的句法和词语顺序[8]等.

最近大量实验证明语句的语法结构对相似度有着重要的影响，不能忽视[4].例如，“今天我追赶了一只狗.”和“一只狗今天追赶了我.”这两个语句根据人的主观判断，是两种相反的意思，可是目前绝大多数相似度算法中这两个语句的相似度值是极其高的，甚至是1，即完全一样，这显然不合适.忽视了语句的语法信息，其计算结果往往缺乏合理性.

本文对中文语句的相似度算法进行改进，在计算相似度的时候，不但考虑语义信息，还将语句的语法结构加进来.本文涉及的语法结构主要从3方面来进行考虑：

1）具有相同语法结构的词语集合间的相似度；

2）两个语句中所包含的语法结构的相似性；

3）经过分词后的词组在语句中出现的位置的相似性.

为了解决目前中文领域大多数短文本相似度计算仅仅涉及语句语义特性的缺陷，本文结合语句的语义特性和语法特性，进行短文本的相似度计算.

2.1语法结构的提取

要对语句的语法结构进行提取与分析，首先需要对语句进行分词.本文使用Ictclas4j分词工具，该工具是Sinboy在中科院张华平和刘群研制的FreeICTCLAS的基础上完成的一个开源中文分词项目.同时使用Stanford[6]工具进行语法解析，该工具是由Stanford NLP Group开发的开源工具.

对于某一中文语句，经过语法工具分析后，能够得到某个词语的具体词性，斜杠后面表示的就是该词语的具体词性，如图1所示.

但是，仅仅知道词语的具体词性是不够的，具体的词性代表的是词语的特性，并不表示一个语句的结构组成，我们需要从中提取出语句的语法结构，例如简单从句、名词性从句和动词短语等，然后把相应的词语或短语归类到语法结构集合中.

本文通过分析汉语语法结构的多样性及词语的具体词性，提出一种新的语句语法结构的提取方法，提取过程如下：

1）使用Ictclas4j与Stanford对语句进行分词处理以及语法解析，得到最基本的词语或短语的词性标注.

2）进一步分析以上获得的结果，通过逐层解析以及句法树分析的方式把已经标注好语法词性的词语或短语进行抽取与归纳，抽取出语句的组成结构类型，例如简单从句类型和动词短语类型等.

3）最后把具有相同语法结构类型的词语或短句存放在相应结构类型的集合中，形成不同的语法结构集合，例如简单从句类型集合、名词性从句类型集合和动词短语类型集合等，实现对语句的语法组成结构的分析.

通过使用上述语句语法结构提取方法进行语句语法处理，提取出语句的语法结构以及相应所包含的词组，如图2所示.

与图1相比较，我们发现一个中文语句经过语法结构提取后，可以得到该语句的结构组成，例如动词性短语和介词性短语等，相比于图1中单个词语的词性标注，能够得到语句的语法结构组成，更加有利于对中文语句语法语义相似度的研究.因为研究语句的语法结构时，我们更加倾向于研究其整体的结构类型组成，而不是单单某个词语.

中文语句句法结构类型部分见表1.

2.2语句句法结构类型相似度计算

经过语句语法结构提取方法分析后，每个语句都被切分成若干个结构类型，例如有的包含名词性短语和动词性短语等，有的却包括简单从句、名词性短语和副词短语等.

语句语法结构类型相似度计算思想就是计算两个语句中含有相同结构类型的个数与所有结构类型的个数的比值.该比值反映了两个语句在句法结构上的相似性.

定义1假设语句Sen1包含m个不同的句法结构类型，分别为ST11，ST12，…，ST1m，Sen2包含n个不同的句法结构类型，分别为ST21，ST22，…，ST2n，则句法结构上的相似度sst计算公式如下：

2.3语句词组位置相似度计算

中文语句中词组的位置对短文本间的相似性有着重要影响，所以需要计算词组位置的相似度[8].

本文中采用的方法不是以单个汉字为基本单位，而是以经过分词后的词组为单位，因为单个汉字包含的信息太少，词组能够反映更多的信息，所以以词组为单位计算词组位置的相似度更加合理.

本文计算语句词组位置相似度的方法如下：

2.4基于语法结构的语句语义相似度计算

目前绝大多数的中文语句相似度计算方法都是根据第一个语句中的每个词语分别和第二个语句中的每对词语计算相似度，取最大值作为第一个语句中的那个词语对第二个语句的相似度，然后第一个语句中每个词语都这样计算，最后取所有相似度值的均值作为第一个语句对第二个语句的相似度.

上述的方法完全依靠语义信息，而忽视了语法结构信息，计算结果都不太理想，因此本文把语法结构信息加入计算中，即计算具有相同语法结构类型的词组间的相似度，综合了语法和语义两大方面.

2.5基于语法语义的语句相似度计算

基于语法语义的语句相似度计算方法综合考虑了语法和语义两方面特性，主要包括基于语法结构的语句语义相似度计算、语句语法结构类型相似度计算和语句词组位置相似度计算.

通过公式（5），（6）和（7）可以得到语句间的最终计算公式，见式（8）.

公式（8）表示，中文语句间的相似度最终由语句的语法和语义的相似性共同构成.在计算短文本（语句）间的相似度时，改变了以往仅仅考虑语句语义相似性的思路，本文不但考虑语义相似性，还考虑了语句语法结构对相似性的影响.

本文在计算语义相似度时，加入语法结构信息，即计算具有相同语法结构的词组集合间的相似度，另外充分考虑了句法结构类型和词组位置相似性对整体语句相似度的贡献与影响.最终短文本（语句）间相似度计算更加符合中文语句的特点，计算结果更加合理，与人们的主观判断更为接近.

3实验及分析

当前基于语法的相似度计算方法多用于英文短文本处理，为进行中文短文本相似度计算，本文采用了以下3种方法来对相似度算法进行分析.

方法一：刘群、李素建等[9]提出的一种相似度方法，在计算时仅仅考虑义原距离，未考虑深度.

方法二：一种既考虑义原距离和深度，又在计算过程中加入词语词频作为权重的方法[2]，具体参数设置详见参考文献[2].

方法三：本文中介绍的基于语法语义的短文本相似度计算方法.

利用上述3种方法分别测试50对中文语句，计算语句（短文本）间的相似度值，部分计算结果见表2.

3.1权重因子实验与分析

利用上述实验数据，对方法三的短文本相似度计算公式中的权重因子a和b进行实验分析，获得能够使得计算公式的效果最佳的权重因子组合.

采用控制变量法对 a=0.35，0.45，0.55，0.65，0.75，0.85，0.90，0.95和b=0.3，0.4，0.5，0.6，0.7，0.8进行实验分析，且设置相似度阈值为0.6，根据获得的结果进而计算得到不同的精确度和召回率.不管权重因子a和b取上述的哪个值，本文提出的相似度计算方法的召回率基本上都是差不多的，稳定在0.882上下，这说明了本文方法的稳定性. 根据实验结果绘制本文方法在权重因子a和b不同取值时的精确度的折线图，如图3所示，其中横坐标表示a的取值，纵坐标表示精确度，b的不同取值采用不同的线条表示.

根据图3分析可知，当权重因子a的值大于0.6，b的取值在[0.4，0.6]时，本文方法的精确度基本上都在0.75以上，尤其当a值在（0.85，0.95]区间时，本方法的精确度可达到最大值0.833，且比较稳定.

综上所述，可以得到本文最终计算公式中的权重因子a和b的取值范围.当a值在（0.85，0.95]区间，且b的取值在[0.4，0.6]时，本文方法的召回率以及精确度能够同时达到比较高的水平，分别为0.882和0.833.

3.2短文本相似度实验与分析

方法三中的权重因子a和b分别取为0.88和0.5，然后对实验数据进行统计分析，计算3种不同计算方法的计算结果的精确率和召回率，且设置相似度阈值为0.6，结果如图4所示.

根据图4可知，在召回率基本上比较高的情况下，本文提出的方法的精确率为0.833，比方法一的0.577和方法二的0.619都要高，这说明本文方法非常明显地提高了查准率，有效地减少了噪音数据，计算结果更加能够被人们接受.

把实验数据分为近义的语句对集合和反义的语句对集合，分别进一步分析.

对于近义的语句对集合，将相似度区间分为3个，图5描述了不同方法在每个区间内近义语句对占所有近义语句对的比例.方法一中接近一半的语句对的相似度值在（0.8，1]间，其在（0.5，8]间的语句对还不到一半，因为语句对没有完全一样的，所以计算结果偏高，且还有一些语句对的相似度低于0.5，显然其计算结果不合理.方法二中大概82.00%的语句对的相似度值都在（0.5，8]之间，比较符合实际，但是其计算结果中仍然有低于0.5的，结果也不太理想.而方法三中在（0.8，1]之间的不到25.00%，绝大部分都是在（0.5，8]之间，没有低于0.5的，这样的计算结果显然更加合理，更接近人们的主观判断.

对于反义语句对集合，把相似度区间分为4个，图6描述了不同方法分别在每个区间中的测试语句对所占的比例.由图可知，方法一和方法二在相似度大于0.5时大概都有75.00%的反义语句对，而低于0.5的却只有25.00%，显然它们的计算结果都非常不理想，计算粗糙.而方法三在（0.5，1]区间中只有29.00%左右的反义语句对，且约71.00%的语句相似度都是低于0.5.显然方法三计算结果更加合理和精确.另外由表2可知，有些语句意思明明是完全相反的，可方法一和方法二计算结果都非常高，甚至是1，而方法三却能够得到非常合理的结果.

由上述实验结果可知，本文提出的方法相比于方法一和方法二，具有比较好的查全率，并且其精确率更高，能够非常有效地减少噪音数据的产生，更加接近人们的主观判断.

4结论

本文以HowNet为词典库，以Stanford为语法解析工具，并在此基础上研究了本文提出的基于语法语义的中文短文本的相似度计算.

在本文描述的方法中，我们结合语句的语法结构和语义信息计算整个语句的相似度，即计算具有相同语法结构的词组间的语义相似度以及考虑语法结构类型间相似性和词组位置相似性对整个语句相似度的影响.即使两个语句完全一样，但是语句结构不同或词组位置不同，也会导致意思完全不一样，这样的计算方式与人们的主观判断更加接近，也符合中文语句（短文本）的复杂性特点.

本文研究的方法在一定程度上解决了目前中文领域基于HowNet进行短文本相似度计算的方法中存在的结果不合理现象.通过实验对3种方法进行对比分析，证明了本文描述的中文短文本相似度方法更合理，具有比较好的召回率和精确率.

参考文献

[1]蒋溢，丁优，熊安萍，等.一种基于知网的词汇语义相似度改进计算方法[J].重庆邮电大学学报：自然科学版， 2009，21（4）： 533-537.

JIANG Yi， DING You， XIONG An-ping， et al. An improved computation method of words semantic similarity based on HowNet[J]. Journal of Chongqing University of Posts and Telecommunications： Natural Science， 2009，21（4）： 533-537.（In Chinese）

[2]廖志芳，邱丽霞，谢岳山， 等.一种频率增强的语句语义相似度计算[J]. 湖南大学学报：自然科学版，2013，40（2）：82-88.

LIAO Zhi-fang， QIU Li-xia， XIE Yue-shan， et al. A frequency enhanced algorithm of sentence semantic similarity[J]. Journal of Hunan University： Natural Sciences， 2013，40（2）： 82-88.（In Chinese）

[3]李连，朱爱红，苏涛.一种改进的基于向量空间文本相似度算法的研究与实现[J].计算机应用与软件，2012，29（2）：282-284.

LI Lian， ZHU Ai-hong， SU Tao. Research and implementation of an improved VSM-based text similarity algorithm[J]. Computer Applications and Software， 2012，29（2）：282-284.（In Chinese）

[4]OLIVA J， SERRANO J I， CASTILLO M D， et al. SyMSS： a syntax-based measure for short-text semantic similarity[J]. Data & Knowledge Engineering， 2011，70（4）：390-405.

[5]董振东，董强.关于知网—中文信息结构库[EB/OL]//http：//www.keenage.com/html/c_index.html.

DONG Zhen-dong， DONG Qiang.Chinese information database based on CNKI[EB/OL]//www.heenage， com/html/C.cndex.html.（In Chinese）

[6]The Stanford Natural Language Processing Group. The Stanford NLP[EB/OL]//http：//nlp.stanford.edu/software/lex-parser.shtml.

[7]ISLAM A， INKPEN D. Semantic text similarity using corpus-based word similarity and string similarity[R]. Ottawa：University of Ottawa，2008.

[8]LI Y H， MCLEAN D， BANDAR Z A， et al. Sentence similarity based on semantic nets and corpus statistics[J]. IEEE Transactions on Knowledge and Data Engineering，2006，18（8）：1138-1150.

[9]刘群，李素建. 基于《知网》的词汇语义相似度计算[C]//第三届语义学研讨会论文集. 台北：台北中央研究院，2002： 149-163.

文本相似度的计算 篇3

1 特征向量的选取

由于中文和英文的差别,在进行中文信息处理时,为了提供效率和精度,都引入了中文分词机制,即先把文本切分为关键词序列,再进行信息处理。计算文本的相似度也需要引入中文分词,这里采用的中国科学院计算技术研究所汉语词法分析系统ICTCLAS的开源代码。为了更好地进行相似度的计算,把经过处理之后得到的关键词进行停用词的处理。即把各种标点符号、汉语中最常用的虚词(介词、连词、助词和叹词等)、英语中最常用的虚词和感叹词作为停用词。在最终得到的关键词列表里面不包括停用词,这些处理后的关键词构成了文本的特征向量。

2 余弦系数

假设Di、Dj是两个不同的文本,经过特征向量选取后得到的向量为Di=(d1i,d2i,…,dmi)T与Dj=(d1j,d2j,…,dmj)T,其中dkj(dki)表示关键词k发生在文本j(i)中的频率权重。则文本Di、Dj的余弦系数为:

在余弦系数方法中dkj(dki)表示频率权重,即关键词在特征向量中出现的概率,其计算公式为:C/SUM,其中C为关键词出现的次数,SUM为特征向量中关键词出现的次数的总和。

我们利用余弦系数是求文本的相似度,而且参与运算的特征向量的维数是相等的,因此对于获取的特征向量还要做一些处理,即参与运算的特征向量的关键词要同时出现在两个文本中,也就是对两个特征向量集合求交集,这样得到最终的向量Di与Dj,利用余弦系数进行相似度的计算。

要判断两个文本是否相似是需要一个标准的,即设定一个阈值检验计算之后的结果。若计算结构大于等于阈值,判定其相似,反之则判定不相似。对于阈值的选择是比较灵活的,可以根据需要的精度进行设置,精度要求越高,阈值越大,一般的取值范围是[0.5,1)。

3 小结

我们用Java编程实现了文本相似度的计算,并应用到我们的数字图书馆系统中。在本系统中,对于特征向量中关键词的选择时没有考虑词语的相似性,比如“电脑”和“计算机”应该作为一个关键词。因此下一步的研究工作是增加词语相似性的判断来提高判断的精度,同时要考虑在网络环境下如何高效的进行文本相似度的计算,以进一步的提高数字图书馆系统的效率。

参考文献

[1]陶跃华.基于向量的相似度计算方案[J].云南师范大学学报,2001,21(5):17-19.

[2]张启宇,朱玲.中文垃圾邮件过滤系统的实现[C].2007年网络与信息系统学术会议论文集.

[3]文本相似度计算——余弦定理和广义Jaccard系数[EB/OL].(2007-08-04).http://blog.csdn.net/tttick/archive/2007/08/04/1726022.aspx.

词汇语义相似度算法研究及应用 篇4

词汇的语义相似度在自然语言处理领域有着不可替代的意义和作用。然而词汇之间的语义关系是非常复杂的, 使用一个简单的数值很难来度量词汇之间含义的相似程度。同样的一对词语, 在一方面看可能非常相似, 但是换个角度就可能相差甚远。所以, 研究词语语义相似度离不开具体的应用背景, 例如, 在机器翻译应用中, 词汇语义相似度用来衡量中文和英文文本中, 中文单词与中文词语之间是否可替换;而在信息检索中, 词汇语义相似度要体现用户查询所使用的关键词与用户实际查询目的在语义上是否一致。

1词语相似度研究现状

词语相似度主要分为基于语义本体资源、基于统计算法和将前两者融合的混合技术3种方法:利用语义资源计算词语相似度也可称为基于本体 (或知识库) 的词语相似度算法, 主要根据专家人工建立的语义网络计算相似度。利用统计技术计算词语间语义相似度采用的是无监督的机器学习算法, 分为基于大规模语料库和基于普通词典等方法。混合技术则结合统计技术和语义资源, 取长补短, 提高相似度计算的正确率。

1.1基于语义资源的词语相似度算法

近年来, 一些诸如同义词词林、WordNet、知网这种大规模可量化的语言本体的诞生与发展, 为进行真实文本的语义分析和理解提供了强有力的资源支持。特别是最近几年“知网”等语义资源不断丰富发展, 中文语义研究方向逐渐增多。知网作为一个知识系统, 是一个网而不是树, 它主要反映概念的共性和个性, 同时知网还着力反映概念之间和概念属性之间的各种关系。而词语DEF之间的路径距离则代表了词汇语义的聚合程度。

1.2基于统计的语义相似度算法

基于统计的语义相似度方法建立在如果两个词语的含义相同或相近, 则伴随它们同时出现的上下文也相同或相近。该方法主要以词语的上下文信息的概率分布作为相似度参考, 计算的方法主要包含有向量空间模型 (VSM) 、词语共现信息、基于部分语法分析和改进的基于大规模语料库的方法。

1.3基于混合技术的语义相似度算法

基于大规模语料统计的算法相对专家手工建立的语义资源更加客观, 但每种统计模型的创建都受语料库中数据质量的极大干扰, 如不可避免的数据稀疏和数据噪声都直接影响最终的相似度计算结果。基于语义资源的算法执行起来简单有效, 但语义资源建设需要专业人士耗费人力物力, 同时严重受建设者的主观意识影响。所以, 一种语义与统计相融合的词语相似度算法应运而生, 通过发挥两种算法各自的优势进行词汇间的语义相似度的计算。混合算法能够利用本体知识对稀疏数据进行扩充, 从而在一定程度上解决数据稀疏的问题。

2词语相似度应用实验

FAQ即常见问题库, 它一般作为自动问答系统的子部分存在。比如“百度知道”, 每当用户输入一个问题时, 首先可以查找与之相似的问题及其对应的答案。所以FAQ主要用来搜集用户提问频率较高的问题, 并将它对应的答案一起进行存储。当用户需要输入一个新的查询问题时, FAQ首先可以在搜集存储的常见问题库中查找与其相似的问题, 如果找到了相同的问句, 就将该问句的相关答案抽取出来, 并作为最终答案返回给用户。但是由于汉语表现形式的多样性, 同样一个问题往往有多种表现形式, 因此在FAQ中很难查找到一模一样的问句。在FAQ中进行问答行为的过程, 实际是计算用户提交问句与常见问题库中问句间句子语义相似程度的过程。

本文为实现FAQ查询功能, 采用向量空间模型 (VSM) 计算用户提交问句与常见问题库中问题例句间的相似程度, 而句子相似度的计算依赖于词汇语义之间的相似度, 本文使用基于语义 (知网) 、基于统计 (上下文点互信息) 和语义统计相融合的相似度算法作为词汇语义的权值, 通过VSM算法计算句子间相似程度, 并对其进行对比实验, 最终根据FAQ中检索的相似问句效果来比较上述算法间的优劣。

2.1基于向量空间模型的句子相似度算法

向量空间模型 (Vector Space Model, 简称VSM) 最初用在信息检索 (IR) 中用来对用户查询和语料库文档建模, 如今已经得到了广泛的应用, 如在句子或文档的表示中, 就是通过句子中去掉停用词后剩下的有效词来构成向量空间, 然后在该向量空间中将待计算的句子进行向量化, 以两个向量夹角的余弦值作为句子之间的相似度度量。

2.2实验方法

本文选择从百度知道“生活类别”下数据内容较广的美容塑身类别中采集10个常见问题, 组成领域问答库。

本文对相似度计算的结果评测方法选择Pooling方法评测, P@N代表参与评测的算法都要返回前N个答案。分别采用准确率 (Precision) 、召回率 (Recall) 、F值以及MRR (Mean Reciprocal Rank) 、MAP (Mean Average Precision) 5个指标进行评价。其中, MRR、MAP的公式如下:

undefined

其中, RQ为算法返回的正确答案总数, rQ为算法返回的排名最靠后的正确答案, #DocQ (i) 为算法返回第i个正确答案时共返回答案的总数。

2.3实验结果

本文选择的测试问句如表1, 并分别返回前5、10、20个答案作为该算法返回的结果。

从图1可知, 语义与统计相融合的词语相似度算法 (M-3) 在不考虑检索到结果的相关度排序问题下, 效果最好, 其次为基于语义的词语相似度算法 (M-2) , 最后是基于统计的词语相似度算法 (M-1) 。如果考虑返回结果的相关度的排序, 效果最好的为语义与统计相融合的词语相似度算法, 其次为基于统计的词语相似度算法, 最后是基于语义的词语相似度算法。并且语义与统计融合的算法的优势更加明显。

3结语

从第6个问题 (S-6) “嘉和的智能止鼾器效果怎么样?”可以看出, 基于统计的词语相似度受制于训练语料的规模, 由于数据稀疏 (止鼾器出现次数很少) , 由统计方法计算“止鼾器”的结果不理想, 而基于语义的词语相似度算法可以得到较好的效果;从第三个问题 (S-3) “直肠癌化疗后掉头发怎么办?”可以看出, 单纯的基于语义计算词语相似度则完全依赖语义资源, 语义词典中“直肠癌”与“头发”的相似度较低, 而基于统计的词语相似度算法则能给出较高的相似度值。可见, 将两者融合能有效地克服各自算法的缺点, 给出更加合理的词语相似度数值。

参考文献

[1]董振东, 董强.知网[EB/OL].http://www.keenage.com, 2002.

[2]刘群, 李素建.基于知网的词汇相似度计算[EB/OL].http://www.keenage.com, 2002.

[3]PETER D TURNEY.Similarity of semantic relations[J].Computa-tional Linguistics Journal, 2006 (3) .

[4]PETER D TUNREY.Mining the web for synonyms:pmi-ir versuslsa on toefl[C]//Proceedings of The 12th European Conference onMachine Learning.Freiburg, 2001.

基于纹理特征相似度伪装评估模型 篇5

灰度共生矩阵通过灰度值不同的像素的分布反映了灰度的分布特性, 也反映了这些像素对之间的位置关系和分布特性。基本步骤是先利用像素对之间的方向和距离参数构造共生矩阵, 然后从矩阵中提取能量、对比度等有意义的统计量来表示纹理特征。这样做能够在保证检索准确度比较高的条件下, 明显的降低计算量, 即提高检索速度和效率。

灰度共生矩阵表示图像中相距d= (∆x, ∆y) 的两个灰度像素同时出现的联合概率分布。若图像的灰度级为L, 则共生矩阵为L×L矩阵。设一个像素的灰度值为i, 另一个的灰度值为j, 联合概率密度P (i, j) 可以定义为:

其中, 是第一个像素的坐标;像素灰度级;S是具有特定空间关系的像素对的集合;#S表示集合中的元素个数。

2 基于2D-Gabor小波变换的纹理分析模型

采用直接Gabor变换计算复杂度较高, 会产生维数较高的问题, 仍需要改进。特征向量维数过高将会对这个分类系统产生许多负面影响, 对Gabor特征向量进行降维是必要的。本文将尺度和方向的显著性作为权重引入相似度量。在进行相似性度量是不采用概率论框架, 而是将可信度引入相似性度量, 可信度是可通过标准化能量值得到。

用表示尺度集合, 用表示方向集合, 则共有P×Q种尺度和方向组合。用CI表示该组合的集合, 可表示为:

对集合CI中的每个元素, 采用式 (5.19) 计算能量信息。则能量信息集合表示为:

并对EI中的每个元素进行归一化处理使其不受图像是实际尺寸影响, 归一化之后的能量信息集合:

从EI'的元素中选取前N个具有最大能量值的元素并提取对应尺度和方向上的特征, 根据这些特征构造图像标识, 则提取的图像特征可能是局部的。

为了使表述简化, 用x表示 (p, q) 。设表示在[X1, X2]上连续的3个点, 且E' (xx-1) 、E' (xx) 、E' (xx+1) 分别表示处的能量值, 则采用下式进行峰的判定。

若∆<0且和, 则xi对应的为峰。

根据上式判定在区间[X1, X2]内可以确定峰集合:

在确定峰集合的过程中还应去除虚假峰的影响。虚假峰是指符合峰判定条件, 但不具备显著标识尺度和方向。其约束条件为∆<0且, 虚假峰不加入峰集合。针对显著峰集合中的每个元素, 计算能量信息, 分别计算均值µmn和标准方差σmn。采用计算得到的所有均值和标准差确定特征向量。

3 基于灰度共生矩阵和Gabor小波变换联合进行纹理特征相似度判别

灰度共生矩阵法和小波变换方法联合进行纹理特征相似度的度量采用以下步骤:

(1) 获取一定照明条件下相同观察距离、相同分辨率的伪装图像和背景图像;

(2) 将原始彩色图像转换为灰度图像;

(3) 对伪装和背景图像分别进行三层小波分解;

(4) 对各层的低频分量计算特征矢量。计算其灰度共生矩阵, 以能量 (E) 、对比度 (I) 、熵 (H) 、均匀性 (L) 和相关 (C) 等五个特征值组成纹理特征矢量。。

(5) 特征归一化。图像特征矢量的各特征值有时相差很大, 需要将特征分量归一化到相同的区间。采用高斯归一化, 即分别计算特征分量值的均值m和标准差s, 然后利用变换, 将各特征值归一化到[0, 1]区间。

(6) 判别模型。利用马氏 (P.C.Mahalanobis) 距离计算背景和伪装之间的纹理相似度, 即以各特征差值的均方根作为相似度判断准则, 且当纹理完全相同时, 相似度为1。

其中, TM, TN是背景和目标的纹理特征矢量, 为[TM, TN]的协方差矩阵

4 实验结果及分析

图1给出的是林地型伪装场景的局部背景和迷彩图案, 用上述方法计算比较背景与不同迷彩纹理的相似度。

表1是仿豹纹迷彩、仿枫叶迷彩和仿杨叶迷彩图案与背景的相似度系数。根据前面的论述运用灰度共生矩阵方法计算伪装方案与背景相似度可以看做是对较近距离光学侦测的仿真, 而利用小波变换方法计算相似度可看作是在不同距离对目标光学侦察仿真, 如果灰度共生矩阵法的侦测距离为S则一次小波分解、二次小波分解、三次小波分解的计算结果可以分别看作是侦测距离分别为2S、4S、8S上的相似度比较。

由表1, 可以看出, 当伪装目标分别运用A、B和C方案处于背景中在较近观察距离时, 迷彩伪装C和迷彩伪装A与背景纹理相似度较好;当侦察距离变大, 背景有较好的纹理相似度是迷彩伪装B和迷彩伪装C, 所以仿真训练过程中可以根据不同的的战术应用条件和需求, 决定采用哪种迷彩伪装纹理方案, 评估训练效果。

不同距离上的观察效果除了上述因素外还受迷彩斑块的大小影响。图2为背景及五种迷彩方案, 它们的纹理模式相同的, 只是斑块大小不同, 表2为这五种迷彩方案的三层小波变换相似系数。

通过图2和表2的对比分析, 不难发现迷彩斑块大小并非越小越好, 虽然纹理布局相同, 不同斑块大小的方案在不同分辨率上与背景的相似程度是不同的。从表2数据对比可知迷彩图案G在不同观察距离上都具有较好的伪装效果, 而它的斑点并不是最小的。

摘要：本文提出一种基于灰度共生矩阵和小波变换的方法相结合进行纹理相似度判别的评估模型。图像的纹理特性综合反映了斑点构成的分布和特征, 因此伪装与背景的纹理特性差异, 可以反映出他们之间的综合特性差异。灰度共生矩阵可定量描述纹理特征, 而小波变换将图像分解为不同层次, 可以模拟在不同观察距离上伪装效果的评估。本文在进行模型分析将伪装图像进行多层小波分解, 只在变换后的低频部分, 对不同层次上伪装和背景图像的低频图像纹理特征进行比较, 能够较好的反映伪装和背景在不同观察距离上的综合纹理相似度。

区域相似度 篇6

关键词：增强现实,ARToolKit,图像匹配,相关系数,相对误差

1 概述

增强现实技术(Augmented Reality，简称AR)是在用户所处的现实环境的基础上加载虚拟场景，在现实场景的基础上扩展用户视觉，实现用户与虚拟以及现实之间的交互。因此增强现实技术的研究有着广阔的应用前景和商业价值。

ARToolKit是一套基于C语言及OpenGL的增强现实系统开发包，该工具包是最初由日本大阪大学的Hirokazo Kato博士于1999年在华盛顿大学人机接口实验室(HITLab)设计开发的[1,2,3]。

ARToolKit利用计算机视觉技术来计算观察者视点相对于所检测到的矩形标记的位置和姿态，从而实现对矩形标记的实时跟踪与定位，加载虚拟物体进行增强，并实时显示增强后的视频。

ARToolKit首先初始化摄像机内置参数，导入矩形标记模式文件作为匹配模板，启动摄像头捕获视频，然后根据用户设定的阀值将采集到的一帧彩色图像进行二值化处理，转化为黑白二值图像[7]。对该二值图像进行连通域分析，找出其中所有的矩形区域，对这些矩形区域进行初步处理，如清除过小的矩形区域，将筛选过后的矩形区域在该帧彩色图像中找出相对应的矩形区域作为候选区域，将每一候选区域与模板库中的匹配模板进行图像匹配值的计算，即相似度计算，并记录该候选区域的相关状态信息，对于模板库中的每一个匹配模板而言，候选区域中与之匹配所得到的匹配值最高者并且大于给定相似度参考值，则认为匹配成功，AR-ToolKit找到了一个标记，利用该标记区域的变形来计算摄像机变换矩阵，从而计算出摄像机相对于标记的位置和姿态，这样就可以进行跟踪与定位，叠加虚拟物体。

ARToolKit的矩形标记一般采用封闭的黑色正方形外框、内部为任意图形或图像但非空的矩形标记为标识物，矩形边长一般为80mm，黑色矩形框内标记图像边长一般为40mm[4]。

ARToolKit在进行标记检测时，图像匹配值计算是一个重要的环节，计算的精度直接影响着标记检测的效率与正确性。本文分析了ARToolKit图像匹配值计算的精度与不足，针对这些不足进行了改进，并通过实验进行验证。

2 ARToolKit图像匹配值计算分析

ARToolKit在导入矩形标记模式文件后，将标记模式文件的4个48*16大小的RGB矩阵阵列变换成4个256*3的BGR矩阵阵列，分别代表着矩形标记的4个方向，在提取出矩形候选区域后，ARToolKit提取出候选区域的像素点的RGB值，并最终转换成256*3的BGR矩阵阵列，然后分别与标记模式文件中的4个256*3矩阵阵列进行图像匹配值计算，确定相似度与方向。

假定标记模式文件中的一个256*3矩阵阵列为P(i,j)，假定矩形候选区域的矩阵阵列为Q(i,j)，ARToolKit通过计算图像匹配值CF来确定所提取的矩形区域与标识物模式文件的相似度，见公式(1)：

由公式(1)可知，ARToolKit采用矩阵的相关系数关来计算图像匹配相似度，CF的取值范围为CF≤1,CF值越大，表示该矩形候选区域与匹配模板的某一方向相似度越大。

以图1所示的两张矩形标记为例进行实验，实验环境为：X86 PC兼容系统，NVIDIA Quadro NVS 140M显卡，14.1英寸屏幕，分辨率1400*1050,为采用USB 2.0接口、最大分辨率为1280*960和最大输出速率为30帧/秒的CMOS摄像头，打印机;Windows XP OS,Matalab 7.0,ARToolKit 2.7.1;白纸若干，光照为室内日光灯照射。分别打印80mm,70mm,90mm规格的标记，将80mm的标记通过ARToolKit提供的mk_pattd.exe制作成标记模式文件后，通过Matalab 7.0用相关系数进行匹配值计算，其结果如表1所示。

从表1可以看出利用矩阵相关系数计算图像匹配值，其结果较高，对于多个标记，完全不同的两幅图像其计算出的匹配值CF偏大，容易产生错误判断，这对于实际应用中多标记检测是极其不利的。另外，由公式(1)可知CF=1的充要条件是当Q(i,j)=kP(i,j)，k为常数。当CF=1时，ARToolKit认为此时提取的矩形区域与匹配模板完全匹配，但事实上只有当k=1时，提取的矩形区域与匹配模板才完全匹配，而且当│k-1│越大，提取的矩形区域与匹配差异越大，这样就会产生两个完全不相同的矩阵被认为是完全相同的错误。

3 ARToolKit图像匹配值计算的改进

针对相关系数计算图像匹配值的不足，本文引入相对误差法，并加以改进以提高识别精度。相对误差法多用于直方图相似度计算[5,6]，计算见公式(2)：

将该计算公式用于ARToolKit中图像匹配值计算中，矩阵P和Q为256*3的BGR阵列矩阵，以像素点为横坐标，以每个像素点分别对应的R、G、B值为纵坐标，矩阵P和矩阵Q的相似度计算公式可定义为：

考虑分母为0的情况，可作如下规定:当出现Max(|P(i,j)|,|Q(i,j)|)=0时Max(|P(i,j)|,|Q(i,j)|)=0.1。

由公式(3)可知，由于|P(i,j)-Q(i,j)|≥0,因此Sim(P,Q)=1成立的充要条件是P(i,j)=Q(i,j)，显然，ARToolKit用此公式计算图像匹配值CF=1时，不存在两个并不完全相同的矩阵被认为是完全相同，ARToolKit此时认为提取的矩形区域与标记模式文件匹配成功。

以图1所示标记为例，采用相对误差法，标记模式文件匹配值如表2所示。

从表2可以看出,采用相对误差法计算出的匹配值整体偏低,对于多标记,采用相对误差发计算完全不同的两幅图像其计算出的匹配值则要低得多,但对同一标记识别率较低,为此本文对相对误差法提出改进,以提高对同一标记的识别率。

由公式(3)可知，相对误差求矩阵相似度的基本思想是算出两个矩阵每对对应点的相似度，然后计算相似度的总和，最后取该和的平均值，每一对对应点的相似度各自独立，不受其他点的相似度影响，反过来说，每一对对应点的相似度都会直接影响整个矩阵的相似度，因此相对误差法计算出的相似度受矩阵单个点的相似度影响较大，在考虑矩阵整体相似度方面不如相关系数方法，正是由于这点，导致相对误差法计算出的相似度值较低，因此需要对相对误差法进行改进，改进的一个重要原则是每一对对应点的相似度不再是各自独立，不能直接影响整个矩阵的相似度，改进后的公式见公式(4)。

考虑分母为0的情况，规定当分母为0时，分母值取0.1，显然，改进后的公式Sim(P,Q)取1的充要条件是P(i,j)=Q(i,j)，并且考虑了矩阵的整体性，每对对应点的相似度不再是各自独立，也不能直接影响整个矩阵的相似度。

以图1所示标记为例，采用改进后的公式(4),匹配值计算如表3所示。

从表3可以知道，改进后的算法计算出的匹配值就同一标记而言，比相对误差法明显提高，并且保持了对其它标记的低匹配值，另外相对于相关系数方法计算而言，改进后的公式虽然对同一标记计算出的匹配值要低，但是对其它标记计算出的匹配值却要低得多，并且中间差值总体上要大，这便于开发人员设定相似度参考值，在识别误判的几率上要比相关系数法小得多。

4结论

本文分析了ARToolKit图像匹配值计算的精度，对ARToolKit计算图像匹配值公式提出了改进，提高了ARToolKit识别标记时的精度，今后的主要工作集中在ARToolKit矩形区域提取与应用方面。

参考文献

[1]朱淼良,姚远,蒋云良.增强现实综述[J].中国图像图形学报,2004,9(7):767-774.

[2]沈克.基于ARToolKit平台的增强现实人机交互系统的若干问题研究[D].合肥工业大学硕士论文,2007.

[3]黄有群,姬永成,李丹.基于ARToolKit工具的增强现实交互操作研究[J].计算机与现代化,2008,157(9):97-100.

[4]ARToolKit.http://www.hitl.washington.edu/artoolkit/documentation/tutorialmulti.htm.

[5]薛向阳,罗航哉,朱兴全,吴立德.一种新的颜色相似度定义及其计算方法[J].计算机学报,1999,22(9):918-922.

[6]高美真,申艳梅.基于颜色直方图的图像检索技术[J].微电子学与计算机,2008,25(4):25-27.

基于领域本体的概念相似度算法研究 篇7

近年来,本体已经成为语义Web、人工智能、数据集成、信息检索等研究领域的热门课题。领域本体可以有效地组织领域中的知识,使知识更好地共享、重用。但是在利用本体的同时,如何提高概念相似度计算精度却成了本体应用的一个难题。例如,目前大多数的信息检索方法都是基于关键字进行检索,查准率不高。既然本体描述了数据的语义,则基于本体进行信息检索的检索效率显然要高,本体在信息检索中的应用能够显著地提高检索的精确率和返回率[1]。在信息检索领域中,概念的语义相似度计算起着重要的作用。因此需研究基于领域本体的计算概念语义相似度的计算方法。

1 相关背景及研究工作

1.1 概念语义相似度

同样的词语在不同的上下文中可能会有不同的语义,即语义多元化。在已经对词语排除歧义的基础上,对概念的语义进行比较。语义相似度在不同的应用领域中可能会有不同的含义。例如,在信息整合领域中,相似度一般指的是文本与文本能够匹配的程度;而在信息检索领域中,相似度则反映与用户查询在语义上的匹配程度,相似度越高,表明该文本与用户的请求越接近[2]。

工作背景是信息检索领域。现约定,相似度的取值范围在0～1 之间。当比较的2个概念完全相同的时候,其相似度为1;反之,当比较的2个概念没有任何关联的时候,其相似度为0;在其他情况下,即比较的两个概念之间有一定的关联的情况下,其相似度在0 到1 之间。

1.2 相关研究

对于概念的语义相似度计算,国外许多研究者利用了语义词典Wordnet中的同义词集组成的树状层次体系结构[3],一种方法是考虑两个概念共享信息的程度,基于信息理论定义相似度计算方法;另一种采用了先计算两概念在树中的信息熵或语义距离,然后转化为语义相似度的办法。在国内,相关研究起步相对较晚。具体而言,文献[4,5]中,首先计算两个概念在树中的语义距离,然后转换为2个概念间语义相似度;文献[6]对概念实例采用联合分布概率统计的方法,确定概念间语义相似度;文献[2]运用基于概念实例的相似算法,再结合概念层次树中影响相似度的两个因素,最后得到不同本体间两个概念的相似度;文献[7]提出了概念结构相似度的基本思想和相应公式。

上述实验结果都与人的主观判断的结果相符。但是文献[4,5]是基于一个本体中,内部概念的相似度计算,并没有涉及到多个不同本体间的概念相似度计算;文献[7]对概念实例的范畴划分过于绝对,对于不属于该概念范畴的部分实例,与该概念可能存在一定的相似,这些相似度被忽略了;文献[2]通过计算概念子概念间的相似度而得出概念的总相似度,并未考虑概念之间的父概念及兄弟概念之间的相似性;文献[8]提出了概念结构相似度的基本思想,但给出的公式还不够精细。

针对上述情况,现对文献[2,7]中的公式进行改进,并结合一种新的基于距离的概念相似度算法从而得到计算概念相似度的新算法。

2 基本概念

根据studder的定义,本体是共享概念模型的明确形式化规范说明,它提供了一种明确的形式化的领域知识描述手段,同时支持对隐含知识进行推理,在信息集成和知识管理等领域发挥着重要的作用。本体的形式化的定义为O={C,R,HC,HR,A,I},其中C是领域概念的集合;R为概念间的层次关系;HC为概念间的其它关系,如Same As关系,Part Of关系,Contains关系等,它们是概念集笛卡尔积的子集;HR定义了关系之间的层次结构;A是公理的集合,代表永真断言,I是本体实例的集合。概念是客观世界任何事物的抽象描述。如事物、功能、行为、过程、策略等,语义上它表示对象的集合[8]。现定义概念为一个四元组:C={i,L,P,Ic},其中i为概念的唯一标识符,用URI表示,L为概念的语言词汇,P为概念所拥有的属性的集合,Ic为属于该概念的实例的集合。当两个本体元素具有某些共同特征时,则定义它们是相似的。相似的程度用相似度来表示。

(1) sim(x,y)∈[0,1]。

相似度的计算值为[0,1]区间中的一个实数。

(2) sim(x,y)=1当且仅当x=y。

如果两个对象是完全相似的,则相似度为1。

(3) sim(x,y)=0。

如果两个对象没有任何共同特征,那么其相似度为0。

(4) sim(x,y)=sim(y,x)。

相似关系是对称的。

在有的研究中如自然语言处理,常采用距离的概念。一般说来,两个词汇的距离越大,其相似性越小。

3 相似度计算

3.1 基于距离的概念相似度算法

比较同一个本体中两个概念C1,C2的相似度。定义Cf为C1和C2的最近公共父结点。定义dc1,dc2分别为从C1,C2到Cf的结点数。w1,w2分别为C1,C2的权值。D为树的最大深度。dep(C1)表示节点C1在树中的深度即层次。计算概念C1,C2的相似度:

$w{}_1=\frac{Dep(C{}_1)}{Dep(C{}_1)+Dep(C{}_2)}$ (1)

w2=1-w1 (w1,w2>0)

sim$(C{}_1,C{}_2)=1-\frac{w{}_1\text{d}c{}_1+w{}_2\text{d}c{}_2}{2Dw{}_{1}w{}_2}$ (2)

sim(C1,C2)∈[0,1]。

以上是比较同一个本体中两个不同概念的相似度,现在再对不同本体间的两个概念进行相似度的比较。

(1) 定义概念C1,C2分别来自两个本体O1,O2。定义R为C2的所有父节点,子节点,兄弟节点的集合。条件如下:

(ⅰ) 若a是b的父结点。如果存在结点集合n1,n2,n3,…,nk|ni是ni+1的直接父结点,即

a=n1,b=nk。

(ⅱ) 若a是b的子结点,如果存在结点集合n1,n2,n3,…,nk|ni是ni+1的直接子结点,即

a=n1,b=nk。

(ⅲ) 如果a,b共有直接父结点,则a,b互为直接兄弟结点。

(2) 计算C2到x的距离d:

(ⅰ) 定义S为x的集合;x为概念|x∈R并且x∈O1。

(ⅱ) d为从C2到x所经历的结点数。

(3) 重复步骤(2)得到最小距离d。

(4) 通过式(2)计算C1与S中每个x的相似度(C1与x同属O1)。

(5) 通过步骤(3)中的最小距离d来定义一个误差值g。

(6) 用simM(C1,x)来表示在步骤(4)中得到的C1与x的最大相似度值。

(7) 最终得到C1,C2的相似度。

sim(C1,C2)=simM(C1,x)-g (3)

3.2 概念结构相似度算法

定义结构相似度 SCH(Sci,Scj)[8]

式(4)中SCHf(Sci,Tcj)表示概念Sci,Tcj的父概念之间的相似度;SCHb(Sci,Tcj)表示概念Sci,Tcj的兄弟概念集之间的相似度; SCHs(Sci,Tcj)表示概念Sci,Tcj的子概念集之间的相似度。α,β,λ表示权重因子,因考虑到层次结构中父子、兄弟概念对其相似度的影响是不同的,故在此赋值的权值大小为 α≥β≥λ≥0。

具体如下:

SCHf(Sci,Tcj)=sim(Scif,Tcjf) (5)

式(5)中,Scif,Tcjf分别表示概念Sci,Tcj的父概念。

$\begin{array}{l}\text{S}{}_{\text{C}\text{Η}\text{b}}(S{}_{ci},{\rm T}{}_{cj})=\\ {\displaystyle \sum _{S{}_{ci\text{b}n}\in S{}_{ci\text{b}}}\underset{{\rm T}{}_{cj\text{b}n}\in {\rm T}{}_{cj\text{b}}}{{\displaystyle \max }}}(\text{s}\text{i}\text{m}(S{}_{ci\text{b}m},{\rm T}{}_{cj\text{b}n}))/2\text{W}\text{i}\text{d}(S{}_{ci\text{b}})+\\ {\displaystyle \sum _{{\rm T}{}_{cj\text{b}n}\in {\rm T}{}_{cj\text{b}}}\underset{S{}_{ci\text{b}m}\in S{}_{ci\text{b}}}{{\displaystyle \max }}}(\text{s}\text{i}\text{m}({\rm T}{}_{cj\text{b}n},S{}_{ci\text{b}m}))/2\text{W}\text{i}\text{d}({\rm T}{}_{cj\text{b}})(6)\end{array}$

式(6)中,m∈(0,Wid(Scib)),n∈(0,Wid(Tcjb));Scib,Tcjb分别表示概念Sci,Tcj的兄弟概念集;Scibm,Tcjbn表示Scib,Tcjb中的概念;Wid(Scib),Wid(Tcjb)分别为Sci,Tcj所拥有的兄弟概念的个数。

$\begin{array}{l}\text{S}{}_{\text{C}\text{Η}\text{s}}(\text{S}{}_{\text{c}\text{i}},\text{Τ}{}_{\text{c}\text{j}})=\\ {\displaystyle \sum _{\text{S}{}_{\text{c}\text{i}s\text{g}}\in \text{S}{}_{\text{c}\text{i}s}}\underset{{\rm T}{}_{cj\text{s}h}\in {\rm T}{}_{dj\text{s}}}{{\displaystyle \max }}}(\text{s}\text{i}\text{m}(S{}_{ci\text{s}g},{\rm T}{}_{cj\text{s}h}))/2\text{W}\text{i}\text{d}(S{}_{ci\text{s}})+\\ {\displaystyle \sum _{{\rm T}{}_{cj\text{s}h}\in {\rm T}{}_{ccj\text{s}}}\underset{S{}_{ci\text{s}g}\in S{}_{ci\text{s}}}{{\displaystyle \max }}}(\text{s}\text{i}\text{m}({\rm T}{}_{cj\text{s}h},S{}_{ci\text{s}g}))/2\text{W}\text{i}\text{d}({\rm T}{}_{cj\text{s}})(7)\end{array}$

其中,g∈(0,Wid(Scis)),h∈(0,Wid(Tcjs));Scis,Tcjs分别表示概念Sci,Tcj的子概念集;Scisg,Tcjsh表示Scis,Tcjs中的概念;Wid(Scis),Wid(Tcjs)分别为Sci,Tcj所拥有的子概念的个数。

3.3 相似度影响因子

本体中概念的层次结构越接近,其相似度越大,因而2 个概念在其相应概念树中所处的层次差越小,其相似度越高,针对概念在概念树中所处的层次深度差对概念间语义相似度的影响,本文引入系数x 如下:

$x=t\sqrt{1-\frac{\left|Dep(S{}_{ci})-Dep({\rm T}{}_{cj})\right|}{Dep(S{}_{ci})+Dep({\rm T}{}_{cj})}}(8)$

式(8)中t为可调节参数, Dep(Sci) 表示Sci在S 概念树中的层次(考虑到多重继承的问题,这里选用从该结点到根结点的最长路径来计算),Dep(Tcj) 表示Tcj 在T 概念树中的层次,概念树的根结点层次为0。

同样,两个概念的兄弟节点个数相对较大,也即,它们的父节点分类细致程度较高,则这对概念的语义会较为接近,所以一个概念的分类细致程度也应该是计算语义距离时应考虑的一个因素。引入系数y 如下。

$y=k\sqrt{1-\frac{\left|\text{W}\text{i}\text{d}(S{}_{ci})-\text{W}\text{i}\text{d}({\rm T}{}_{cj})\right|}{\text{W}\text{i}\text{d}(S{}_{ci})+\text{W}\text{i}\text{d}({\rm T}{}_{cj})}}$ (9)

式(9)中k为可调节参数。

3.4 总相似度

将式(5)、式(6)和式(1)结合得到式(7)如下

Sim(Sci,Tcj)即为最终的概念间语义相似度。

4 实验结果

4.1 实验评价准则

本文采用信息检索领域查全率和查准率作为评价映射算法的主要准则,并定义如下:

(1) 概念查全率(Recall)

$r=\frac{\text{正}\text{确}\text{发}\text{现}\text{的}\text{概}\text{念}\text{对}}{\text{可}\text{能}\text{存}\text{在}\text{的}\text{概}\text{念}\text{对}}$。

(2) 概念召回率(Precision)

$p=\frac{\text{发}\text{现}\text{的}\text{正}\text{确}\text{概}\text{念}\text{对}}{\text{所}\text{有}\text{发}\text{现}\text{的}\text{概}\text{念}\text{对}}$。

4.2 实验结果

实验利用本体建模工具Protégé3.1 创建了油田地质领域的两个不同的本体,分别包括300多个概念和关系,对照专家经验,按照本文的算法,取不同的加权系数,相似度计算结果比使用单一的算法计算的结果更接近实际情况。实验结果表明改进后的算法提高了计算精度。

5 结束语

领域本体在知识的共享和重用中起到关键的作用。然而由于各自建立适合自身的本体,使不同本体之间存在个体差异性,本体间也就不可避免地存在着语义冲突,研究者使用本体概念的相似度值判断两个概念间的语义关系。本文针对目前概念相似度计算所存在的问题,提出了一种新的综合的相似度计算方法。从概念的结构不同层次分别计算概念的相似度,然后加权平均求出综合的概念相似度,提高了概念映射的查全率。但是,计算过程中各个权值的设定还只是根据经验来给定,有一定的误差,对权值的设定也可以使用sigmoid函数自动选择。另外,在计算概念的相似度时,没有考虑概念名称、属性、实例等的相似度,而属性对概念的影响因素是很重要的的,还需做深入的研究。

摘要：随着本体技术的逐渐成熟,如何为本体搭建语义桥梁以实现知识的重用与共享成为新的研究热点。在分析现有相关技术的基础上,提出一种计算不同本体中概念间语义相似度的方法,该方法以基于距离的概念相似度算法为基础,同时对概念结构进行分析将两者结合,从而计算出最终的概念间语义相似度。实验证明该方法有效。该研究工作可以应用于面向Web的知识检索领域。

关键词：领域本体,概念相似度,算法

参考文献

[1]Uarino N,Masolo C,Gverter.Onto Seek:Content-based Access to the Web IEEE Intelligent Systems,1999;14(3):70—80

[2]王家琴,李仁发,李仲生,等.一种基于本体的概念语义相似度方法的研究.计算机工程,2007;33(11):201—203

[3]Evaluating Word Net2based measures of lexical semantic related-ness.Computational Linguistics,2004;1(1):1—49

[4]徐德智,郑春卉,Passi K.基于SUMO的概念语义相似度研究.计算机应用,2006;26(1):180—183

[5]吴健,吴朝晖,李莹.基于本体论和词汇语义相似度的Web服务发现.计算机学报,2005;28(4):595—602

[6]Doan A H,Madhavan J,Domingos P.Learning to map betweenOntolo-gies on the semantic Web.//Proceedings of the11thInternational Conference on World Wide Web,New York,USA:ACM Press,2002:662—673

[7]徐德智,肖文芳,王怀民.本体映射过程中的概念相似度计算.计算机工程与应用,2007;43(9):167—169

区域相似度 篇8

当今互联网信息量不断扩大, 网络经济发展迅猛, 信息过载成为社会性问题。个性化推荐系统是解决这一问题的一种有效工具。协同过滤技术在推荐系统, 尤其是在电子商务中得到了广泛的应用[1、6], 几乎所有大型电子商务平台都使用了各种推荐系统, 对用户的特征和喜好进行分析, 并提供更具个性化的推荐。协同过滤利用具有相似经验的用户群体的偏好信息为特定用户进行商品或信息的推荐。根据模型的不同, 协同过滤可分为基于用户的协同过滤[2]和基于项目的协同过滤[3]。

Slope One算法[4]是一种基于项目的协同过滤算法, 它使用一个线性回归模型进行预测, 在与其他复杂的协同过滤推荐具有同等推荐精度的前提下, 花销更少, 更加易于实现。它的简洁高效使得采用Slope One算法的推荐系统更加易于实现和维护。然而, Slope One算法在进行推荐时, 没有考虑到用户的作用, 用户间的内在关联对预测结果起着重要影响。Slope One算法不加区分地采用所有用户评分数据来计算项目之间的偏差, 这就导致一些与当前活跃用户偏好不同甚至相反的用户数据同等参与了预测, 这会削弱拥有高相似度的用户的作用效果, 使得预测精度降低。采用聚类[8]或动态k近邻[5]可以去除部分噪声数据, 但却造成了数据丢失。数据稀疏性问题是当前推荐系统所面临的主要问题之一[7]。在数据极端稀疏的情况下, 数据的缺失将使得推荐效果很不理想。

因此本文提出了一种改进的Slope One算法 (US-Slope One) , 利用用户相似度对用户评分差值进行加权, 使得拥有不同相似度的用户数据以不同权重参与预测, 实现在尽可能保证不丢失评分信息的前提下, 在非稠密数据集中的推荐精度得到提升。

1 Slope One算法理论

1.1 Slope One算法

假设推荐系统中有m个用户和n个项目, 分别建立两个集合U={u1, u2, …, um}和I={i1, i2, …, in}, U代表用户集合, I代表项目集合。推荐算法常用矩阵Rm×n来表示不同用户对每个项目的评分。行向量Rm表示每个用户的评分, 列向量Rn表示每个项目的得分。为了使计算更加明确, 采用ri, j (1≤i≤m, 1≤j≤n) 表示用户i对项目j的评分。

Slope One算法采用fxxb进行预测, 其中参数b是用户对两项目的平均评分偏差。Slope One算法先计算项目ij与其他项目ik之间的平均评分偏差devjk, 再预测当前活跃用户u对目标项目j的可能评分Predictionu, j。定义Sjk为给项目ij和项目ik都评过分的用户集合, Rj为与项目ij同时被评分的项目集合, countX为集合X中的元素个数。Slope One算法如下:

1.2 加权Slope One算法

为平衡每个项目对目标项目的影响, 同时对项目ij和ik评过分的用户数目sjk将作为权重加入两项目评分偏差的计算, 其中sjkcountSjk。

1.3 双极Slope One算法

双极Slope One算法考虑到用户对物品的喜好, 将项目集合Ijk划分为两部分, 一个是用户评分高于其评分均值的项目集合Ijklike, 剩下的构成Ijkdislike。从而分别计算出喜欢偏差devjklike和不喜欢偏差devjkdislike。

同样的方法, 我们可以计算不喜欢偏差devjkdislike。最后得出评分预测如下:

2 US-Slope One算法设计

如前一章所述, Slope One算法采用所有用户评分数据而不考虑相似度问题, 当存在大量噪声数据时, 预测准确度会大大降低, 导致最终的推荐结果不理想。然而在数据极度稀疏的情况下, 往往又希望保留尽可能多的数据, US-Slope One算法针对这一问题, 采用用户相似度进行加权, 使得相似度不同的用户数据以不同权重加入预测。常用的用户相似性度量方法有余弦相似性, 修正余弦相似性, 皮尔逊相关系数以及斯皮尔曼相似性等。考虑到不同用户的评分尺度问题, 本文采用修正余弦相似性计算用户间相似度。若用户ua和ub的共同评分的项目集合为Iab, 用户ua和ub对项目ic的评分分别为rac和rbc, ra和rb分别表示用户ua和ub的评分均值, 则用户ua和ub之间的相似度simua, ub为:

将用户相似度作为评分偏差计算的权值, US-Slope One算法如下:

3 实验结果及分析

3.1 实验所用数据集

本实验所用的数据集是由Group Lens研究产品组提供的电影评分数据集Movielens (http://moviel ens.umn.edu) , 该数据包括943个用户对1682部电影的共计100000条评分记录, 其中每位用户至少对20部电影进行了评分。评分值范围是1到5分, 分值越高代表用户对电影的评价越好。该数据稀疏度为6.30%。实验时从该数据集中按一定规则随机抽取80%的数据作为训练集, 其余20%作为测试集。

3.2 度量标准

用于推荐系统的推荐质量评价的度量标准主要包括统计精度度量方法和决策支持精度度量方法两种。其中统计精度度量方法的平均绝对误差MAE (Means Absolute Error) 和均方根误差RMSE (Root Mean Square Error) 由于更易于理解并且能够更直观地对推荐质量进行度量, 因此成为推荐质量评价最常用的方法。MAE和RMSE的值越小, 代表推荐质量越高。本文实验采用MAE和RMSE作为推荐质量的度量标准。

假设两个分组P和Q分别代表预测评分集合和实际评分集合, P={p1, p2, …, pN}, Q={q1, q2, …, qN}。MAE和RMSE的定义如下:

3.3 实验结果

本实验将US-Slope One算法与基本Slope One算法和加权Slope One算法以及双极Slope One算法进行比较, 得到的MAE值和RMSE值分别如图1和图2所示。经统计学分析, 实验结果具有代表性。

实验结果表明, 在稀疏数据集上, US-Slope One算法的MAE值和RMSE值均明显低于Slope One算法、加权Slope One算法和双极Slope One算法, 其推荐精度更高。US-Slope One算法总体推荐性能更好, 使用用户相似度进行加权能够在保证数据量尽可能完整的基础上显著提高了预测精度。

4 结论

本文分析了Slope One推荐算法及其改进算法, 针对其在数据稀疏情况下利用有限用户评分数据做出更合理的推荐问题, 提出了将用户相似度作为权重融入预测的US-Slope One算法, 在尽可能保证不丢失原始数据的基础上, 更加合理地运用数据。最后, 对本算法以及已有算法在稀疏数据集上进行试验, 比较结果表明本算法提升了现有算法对于稀疏数据集的适应性, 提高了预测精度和推荐性能。

参考文献

[1]林德军, 孟祥武.基于奇异值分解的Slope One算法[J].新型工业化, 2012.

[2]陶俊, 张宁.基于用户兴趣分类的协同过滤推荐算法[J].计算机系统应用, 2011, 20 (5) :55-59.

[3]邓爱林, 朱扬勇, 施伯乐.基于项目评分预测的协同过滤推荐算法[J].软件学报, 2003, 14 (9) .

[4]Lemire D, Maclachlan A.Slope One Predictors for Online Rating-Based Collaborative Filtering[C], in proceedings of the SIAM Data Mining Conference, Newport Beach, California, 2005.

[5]孙丽梅, 李晶皎, 孙焕良.基于动态k近邻的Slope One协同过滤推荐算法[J].计算机科学与探索, 2011, 5 (9) :857-864.

[6]张华.基于数据挖掘技术的电子商务旅游线路推荐系统[J].软件, 2013, 34 (3) :57-58.

[7]李善涛, 肖波.基于社交网络的信息推荐系统[J].软件, 2013, 34 (12) :41-45.