局部相似度范文

局部相似度范文（精选7篇）

局部相似度 第1篇

纹理分析在图像处理、模式识别和计算机视觉等研究领域中都有着广泛的应用。纹理分析的方法很多, 大致可以分为三大类[1]:统计的方法、信号处理的方法以及基于结构的方法。在统计方法中, 局部二元模式方法LBP[2]以其简单有效的特性在这个领域中得到了研究者的重视。

LBP方法首先将中心像素与其周围邻域进行比较, 然后对结果二值化, 最后将二值化序列转换为十进制并赋予中心点。LBP可以极大地保留图像中的纹理信息并减少特征冗余, 在实践中有着广泛的应用, 比如人脸识别[3]、医学图像处理[4]等。

对LBP提出改进的方法很多。Tan提出了一种局部三元模式LTP (Local Ternary Pattern) [5]方法。LTP引入了一个阈值将LBP中的二元模式细分为三元。这种细分能够提高纹理分类的效果, 也使得LTP具有较高的鲁棒性。

Liao等提出了一种Dominant LBP (DLBP) [6]方法。在DLBP中首先统计测试图像中占主导的LBP模式, 然后用这些模式对纹理图像进行描述, 最后用Gabor特征对这些主导LBP特征进行补充。实验表明这种方法具有很高的纹理区分能力。

Guo等人提出了一种Completed LBP (CLBP) [7]方法。原始LBP中只是利用了图像邻域中的符号信息, 但是幅度与中心值也是很重要的纹理特征。CLBP有效地将上述三者结合在一起, 极大地提高了纹理分类的效率。

在纹理分析中对LBP方法的研究非常活跃[8,9]。本文提出了一种利用邻域相似信息实现纹理分类的二元模式方法。该方法首先计算邻域内像素点之间的相似性, 在此基础上结合现有LBP方法来表示纹理。实验表明本文提出的方法可以有效表征纹理并具有较高的鲁棒性。

1 LBP方法简介

LBP将邻域中心点与邻域中其它点进行比较并将结果二值化, 然后再将所得二进制序列转换为十进制并赋予中心点。LBP定义如下所示:

其中:

式中, pc是邻域中心点像素值, pi是邻域中其它点的像素值, N是邻域点的总个数, R是该圆形邻域的半径。

Zhao等人随后提出了一种Completed Local Binary Count (LBC) 模型[10]。该方法定义如下:

本文算法中所用到的LBP方法都采用LBC模型。

2 基于局部相似信息的LBP方法

LBP方法表征的是中心点与其邻域点的关系。为了充分利用邻域内的其它信息, 我们对原有LBP方法进行了改进, 即分别计算在半径辐射方向和旋转方向邻域点之间的相似特征, 如图1所示。

在半径辐射方向, 计算如下特征:

令T在整幅图像中的均值为Tmean, 则:

同理, 在旋转方向计算如下特征:

则有:

其中Amean是A在整幅图像中的均值。上述公式中s (x) 计算与式 (2) 相同。

LBP仅仅利用符号信息来表述纹理, CLBP则将符号信息与幅度信息以及中心点值结合在一起来表征纹理, 实践表明这种策略可以极大提高纹理分类能力。因此本文中将提出的特征与CLBP方法进行结合:首先将符号信息与提出的两种特征相融合, 然而将融合后的特征分别与邻域均值相结合。邻域均值信息计算如下:

与CLBP中的中心值相比, 以邻域的平均值为阈值具有较高的鲁棒性。

纹理分类时, 采用Chi-square distance[10]定义纹理间的距离。Chi-square距离定义如下所示:

其中mi和si分别时是两幅图像的第i个特征的统计值。B是特征模式的总个数。

3 实验结果

本文提出的方法与LBP、LTP以及CLBP在Outex[11]纹理数据库上进行了比较。下列网址分别提供了LBP和CLBP的源代码:http://www.cse.oulu.fi/CMV/Downloads/LBPMatlab, http://www4.comp.polyu.edu.hk/~cslzhang/code/CLBP.rar。

为了测试算法的鲁棒性, 将不同信噪比 (Signal Noise Rate, SNR) 的高斯噪声加入到纹理数据库中 (噪声均由MATLAB函数imnoise产生, 参数为measured’, linear’) 。

Outex是一个常用的纹理测试库。Outex中包含了大量的自然物体的表面纹理。Outex库中图像都是在不同条件下采集所得, 比如光照变化、旋转变化、分辨率变化等。这个纹理库包含很多测试序列, 在本次实验中我们采用了TC00010 (TC10) 和TC00012 (TC12) 序列。其中TC10采集条件为Inca’, TC12序列又包含了两个不同的采集条件T184’和horizon’。实验中部分测试图如图2所示。

实验中参数设置如下:半径R和邻域点的个数N分别为 (1, 8) 、 (2, 16) 、 (3, 24) 。所有测试方法均采用LBC模式。LTP中阈值为5。SRM和SAM表示本文提出的方法。其中SRM表示符号信息、半径方向邻域信息以及邻域均值相结合的特征;SAM表示符号信息、旋转方向邻域信息以及邻域均值相结合的特征。

从表1中看出, LTP的性能高于LBP, 而且当N与R增加时, 他们之间的差异越明显。从表中还可以看出CLBP的性能明显高于LTP。原因是无论LBP还是LTP这两种方法都只是利用了符号信息来描述纹理, 而CLBP在符号信息的基础上又结合了其它信息, 这样纹理分类性能提升比较明显。本文方法无论在TC10测试序列还是在TC12测试序列中纹理分类性能都高于LBP和LTP。总体来讲CLBP在Outex数据库上取得了较高的分类结果, 本文提出的方法与CLBP相比性能差别并不明显:在TC10测试数据上差别最大为1.01%;在TC12测试数据上, 本文提出的方法与CLBP的差别最大不超过4%, 在部分测试中性能甚至高于CLBP (horizon’R=1, N=8) 。

表2与表3显示, 加入噪声以后经典的LBP方法性能并不理想。作为LBP的一种改进, LTP鲁棒性能总体优于LBP, 但提升空间不明显。CLBP的抗噪性能高于LBP和LTP, 原因是CLBP中的幅度信息和中心值信息具有一定的抗噪性能。将三者结合在一起后, CLBP具有较好的鲁棒性。本文提出的方法由于考虑了邻域内像素点的相似性, 并且这种相似性在邻域内受噪声的影响较小, 所以总体来讲其抗噪性能高于CLBP。尤其是在噪声比较大的时候, 本文的方法抗噪性能表现更加突出, 如表3所示:CLBP与本文方法最大差距甚至超过了7% (T184’R=3, N=24) 。

4 结语

纹理分析是图像处理、模式识别和计算机视觉领域中的一个热点问题。目前提出的纹理分析算法还不能完全达到实际的要求, 不同的方法都有其优越性和局限性。本文在现有方法的基础上提出了一种利用邻域相似性实现纹理分析的LBP方法。实验表明与经典的LBP及其改进方法相比, 本文提出的方法在有效实现纹理分类的同时具有较高的抗噪性能。

参考文献

[1]Zhang Jiangguo, Tan Tieniu.Brief review of invariant texture analysis methods[J].Pattern Recognition, 2002, 35 (3) :735-747.

[2]Ojala T, Pietikainen M, David H.A comparative study of texture measures with classification based on feature distributions[J].Pattern Recognition, 1996, 19 (3) :51-59.

[3]Francisco A Pujol, Juan Carcia.Computing the principal local binary pattern for face recognition using data mining tools[J].Expert Systems with Applications, 2012, 39 (8) :7165-7172.

[4]Loris Nanni, Alessandra Lumini, Sheryl Brahnan.Local binary patterns variants as texture descriptors for medical image analysis[J].Artificial Intelligence in Medicine, 2010, 49 (2) :117-125.

[5]Tan Xiaoyang, Triggs B.Enhanced Local Texture Feature Sets for Face Recognition under Difficult Lighting Conditions[J].IEEE Transactions on Image Processing, 2010, 19 (6) :1635-1650.

[6]Liao S, Law M, Chung C S.Dominant local binary patterns for texture classification[J].IEEE Transactions on Image Processing, 2009, 18:1107-1118.

[7]Guo Z, Zhang L, Zhang D.A completed modelLing of local binary pattern operator for texture classification[J].IEEE Transactions on Image Processing, 2010, 19:1657-1663.

[8]Loris Nanni, Sheryl Brahnam, Alessandra lumini.A simple method for improving local binary patterns by considering non-uniform patterns[J].Pattern Recognition, 2012, 45 (10) :3844-3852.

[9]Liu Li, Zhao Lingjun, Long Yunli, et al.Extended local binary patterns for texture classification[J].Image and Vision Computing, 2012, 30 (2) :86-99.

[10]Yang Zhao, De Shuang Huang, Wei Jia.Completed Local Binary Count for Rotation Invariant Texture Classification[J].IEEE Transactions on Image Processing, 2012, 21 (10) :4492-4497.

局部相似度 第2篇

随着科学技术的发展和电力市场改革的深入,用户对电能的需求量日益增加,同时对电能质量的要求也越来越高[1]。为了提高电能质量,必须对电能质量问题进行诊断、定位和分类[2],而对短时电能质量扰动(SDPQDshort duration power quality disturbance)进行分类是对其进行治理的前提。

基于小波变换的SDPQD分类方法[2,3,4,5,6,7,8,9]能有效提取扰动特征但易受噪声影响,且分类过程不够简单[10]。作为连续小波变换和短时傅里叶变换的发展,S变换[11]具有良好的时频特性,有利于提取SDPQD特征[12]。文献[13,14,15,16]利用S变换良好的时频分析和特征提取特性,分别结合人工神经网络[13]、模糊系统[14]、支持向量机[15]、制定各种规则树[16]等方法实现了SDPQD分类,取得了较好的效果。上述方法的共同特点是:首先由S变换提取各类SDPQD特征,然后结合不同的分类器完成扰动分类,分类过程及算法复杂,难以直观理解和定量分析;而分类器只考虑模时频矩阵中特定行或列的信息,未能充分挖掘矩阵元素之间的关联信息,且各分类器自身存在一些缺点,如神经网络收敛性差、训练时间长、容易陷入局部最优[15],模糊系统很难建立“IF-THEN”这样的明显知识规则[15],支持向量机的识别能力易受自身参数的影响[17],规则树的制定过程复杂等;导致在噪声情况下,分类准确率均不高,且只考虑了特定时间范围内信号的扰动分类情况,均不能用于不同时间长度信号的扰动分类。

文献[18]提出一种基于S变换模时频矩阵相似度的分类方法,通过直接计算扰动信号S变换模时频矩阵与各种扰动标准模时频矩阵之间的相似度,量化其特征差异实现扰动分类,以模板匹配的方法代替传统分类器,简化了分类算法。但该方法未考虑扰动为任意时间长度的情况,即持续时间不同的扰动需要建立一系列不同的模板,且并未针对各种扰动模时频矩阵的特征选取模板,各扰动之间差异不明显,导致在20 dB的噪声水平下,电压凹陷、电压缺口和尖峰彼此之间容易误判。

本文提出基于S变换下模时频矩阵局部相似度的SDPQD分类方法。通过时频尺度缩放,实现各类扰动特征标准化,并按各扰动特征取其模时频矩阵特定部分,以此持续时间不同的同类扰动可建立唯一的标准化模板,作为该类扰动的标准判据。引入数字图像处理中相似度指标量化未知扰动各局部模时频矩阵与各类扰动标准化模板之间的接近程度,以模板匹配的方法,按照相似度最大原则对任意持续时间的扰动进行分类。局部化的扰动特征更能突出同类扰动彼此相似、不同类扰动彼此差异的性质,充分利用各扰动模时频矩阵中元素之间的关联信息,在20 dB噪声水平下每种测试样本与该类扰动标准化模板平均相似度皆达到了0.96以上,且与其他扰动标准化模板差别明显;特别是在强噪声环境下,有利于削弱噪声对分类准确率的影响。仿真结果表明,本文方法在40 dB,30 dB,20 dB噪声水平下分类准确率均为100%,是一种有效的SDPQD分类方法。

1 S变换基本原理及数字图像缩放原理

1.1 S变换基本原理

S变换由Stockwell于1996年提出,是一种可逆的局部时频分析方法,其思想是对连续小波变换和短时傅里叶变换的发展。信号x(t)的S变换S(τ,f)定义如下:

$S(\tau ,f)={\displaystyle {\int }_{-\infty }^{\infty }x}(t)w(\tau -t,f)\exp (-2\text{π}ft\text{i})\text{d}t(1)$

式中:τ为控制高斯窗口在t轴位置的参数;w(τ-t,f)为高斯窗口,

$w(\tau -t,f)=\frac{|f|}{\sqrt{2\text{π}}}\exp \left(\frac{-f{}^2(\tau -t){}^2}{2}\right)(2)$

由式(2)可以看出,S变换不同于短时傅里叶变换之处在于高斯窗口高度和宽度随频率而变化,克服了短时傅里叶变换窗口高度和宽度固定的缺陷。

S变换的离散表示形式(n≠0)为:

$S[m,n]={\displaystyle \sum _{k=0}^{{\rm N}-1}{\rm H}}[n+k]\exp \left(-\frac{2\pi {}^{2}k{}^2}{n{}^2}\right)\exp \left(\frac{2\text{π}km\text{i}}{{\rm N}}\right)(3)$

式中:

${\rm H}[n]=\frac{1}{{\rm N}}{\displaystyle \sum h}[k]\exp \left(-\frac{2\text{π}kn\text{i}}{{\rm N}}\right)(4)$

n=0时的离散S变换定义为:

$S[m,n]=\frac{1}{{\rm N}}{\displaystyle \sum _{k=0}^{{\rm N}-1}h}[k]n=0(5)$

式中:h[k]是对连续时间信号h(t)进行采样得到的离散时间序列。

S变换可由快速傅里叶变换实现快速计算。h[k]经S变换后得到一个复时频矩阵,对矩阵中的各个元素求模可得与之对应的模时频矩阵。

1.2 数字图像缩放原理

设原始图像中的点A0(x0,y0)缩放后,在新图像中的对应点为A1(x1,y1),则A0(x0,y0)与A1(x1,y1)之间的坐标关系可表示如下:

$\left[\begin{array}{c}x{}_1\\ y{}_1\\ 1\end{array}\right]=\left[\begin{array}{ccc}a& 0& 0\\ 0& b& 0\\ 0& 0& 1\end{array}\right]\left[\begin{array}{c}x{}_0\\ y{}_0\\ 1\end{array}\right](6)$

即

$\{\begin{array}{c}x{}_1=ax{}_0\\ y{}_1=by{}_0\end{array}(7)$

式中:a和b为缩放因子。

在数字图像中,规定所有的像素值都位于采样栅格的整数坐标处,而通过缩放后的灰度值往往会出现在原始图像中相邻像素值的点之间。为此,需要通过插值运算来获得缩放后不在采样点的像素的灰度值。双线性插值法原理[19]如图1所示。

双线性插值法通过线性插值方式来得到目的图像的像素值。对于一个点的像素,其坐标通过反向变换可得到一个浮点坐标(x1,y1),可令其为(i+u, j+v),其中 i 和j 均为整数, u 和v 为[0,1]区间的浮点数,则这个目的像素的值f(i+u,j+v)可由原图像中坐标为(i, j), (i+1,j), (i,j+1), (i+1,j+1)所对应的值的线性插值来决定,即

f(i+u,j+v)=(1-u)(1-v)f(i,j)+(1-u)vf(i,j+1)+u(1-v)f(i+1,j)+uvf(i+1,j+1) (8)

2 基于S变换下模时频矩阵局部相似度的SDPQD分类方法

本文考虑的单一SDPQD信号有:电压凹陷、电压凸起、电压缺口、电压尖峰、振荡暂态和短时谐波;复合型扰动有:电压凹陷加谐波和电压凸起加谐波。各信号采样频率为12.8 kHz(即每周期采样256个点),电压频率为50 Hz。

2.1 扰动标准化模板建立

首先生成不含噪声的8类SDPQD信号,其扰动时刻、持续时间、扰动幅值、谐波含量及振荡衰减率在其定义范围内随机变化。对每类任意持续时间长度的SDPQD信号30个波形进行S变换,采用S模矩阵幅值平方和均值定位扰动发生时间和持续时间[20],并提取S模矩阵中扰动发生前一周期至扰动结束后一周期各行、列元素,行对应频率值,列对应采样时间点。对其时频尺度进行缩放,首先统一时间尺度:将扰动发生前一周期和扰动结束后一周期各列尺度压缩为半个周期时间长度;将扰动持续期尺度缩放为一周期时间长度。然后对各行尺度缩放统一频宽分辨率,即可形成标准化的扰动特征矩阵,并将时频尺度缩放后30个相同大小的扰动特征矩阵相加后求平均,形成该类SDPQD全局模板,再根据各种扰动的特征从全局模板中选出最能表示该扰动特征的一部分作为标准化模板。因此,某类扰动标准化模板可以事先考虑不同条件情况下的同类扰动,且最能体现其扰动特征。

2.2 扰动信号等值线图像尺度缩放和局部化分析

2.2.1 尺度缩放分析

为更细致地观察出时频尺度压缩前后电压凹陷等值线图像发生的变化,将该类型扰动尺度变换前后的等值线图像在1 Hz～150 Hz区域进行放大。持续时间为4个周期的电压凹陷等值线图;持续时间不同,图像中等值线稀疏部分长短各异。将4个周期的电压凹陷持续期特征压缩为1个周期长度,如附录A图A1所示。建立电压凹陷的全局模板等值线图像如附录A图A2所示。由相似度计算可知:样本尺度压缩前与模板相似度为0.771 7,样本尺度压缩后与模板的相似度为0.958 9。

2.2.2 局部化分析

电压缺口和尖峰的扰动特征在高频段会产生暂态分量,但易受噪声影响且电压缺口与尖峰高频部分极其相似。由附录A图A3、图A4可知:在20 dB噪声水平下的电压缺口和电压尖峰测试样本非常相似,即图A3和图A4彼此容易误判。电压缺口和尖峰除了会产生暂态分量外,其主要扰动特征为在低频部分等值曲线的变化,上述2种扰动类型对应于不同的低频等值曲线变化,这种变化在时间极短的情况下不明显,可通过尺度缩放以后突出该变化,因而取全局模板中25 Hz～100 Hz作为其标准化模板,对其进行拉伸如附录A图A5和图A6所示;将测试样本取与标准化模板相同部分如附录A图A7和图A8所示,可以由图A5～图A8直观进行判断。由相似度计算可知:缺口和尖峰样本与全局模板相似度分别为0.957 1和0.957 3,缺口和尖峰样本与标准化模板的相似度分别为0.998 9和0.999 2。

同理,按各扰动特征取其模时频矩阵的一部分作为其标准化模板更能突出差异性,其余各扰动标准化模板的选取为:电压凹陷和电压凸起的扰动特征主要集中在基频附近,但为了加大与振荡暂态和短时谐波图像的差异,因而取全局模板中1 Hz～800 Hz作为其标准化模板;振荡暂态的主要扰动特征集中在扰动周期内的高频部分,因而取全局模板中频率600 Hz～800 Hz、采样点80～380作为其标准化模板;短时谐波的主要扰动特征集中在扰动周期内的中频部分,且为了能与电压凹陷加谐波等复合扰动显著区分,因而取全局模板中频率25 Hz～450 Hz、采样点80～380作为其标准化模板;电压凸起加谐波、电压凹陷加谐波与短时谐波标准化模板的选取情况相同。

由上述比较得出:时频尺度缩放起到统一扰动持续时间尺度和频宽分辨率的作用;同类持续时间不同的扰动,时频尺度缩放后扰动特征趋于一致,且在全局模板的基础上按各种扰动特征部分作为其标准化模板;各扰动标准化模板彼此间差别极大,说明通过时频尺度缩放和局部化模板,更加突出了各类扰动特征之间的差异性。

2.3 扰动分类原理

基于数字图像处理中相似度思想[19],设MA为某SDPQD测试样本信号经S变换和时频尺度缩放后按各扰动特征局部化后所得的扰动特征局部矩阵,MB为已建立的某类SDPQD信号的扰动标准化模板,两者之间的相似程度由下式描述。

$S{}_{\text{A}\text{B}}=\frac{{\displaystyle \sum _{i=1}^L{\displaystyle \sum _{j=1}^W{\rm M}}}{}_{\text{A}}(i,j){\rm M}{}_{\text{B}}(i,j)}{\sqrt{{\displaystyle \sum _{i=1}^L{\displaystyle \sum _{j=1}^W{\rm M}}}{}_{\text{A}}^2(i,j){\displaystyle \sum _{i=1}^L{\displaystyle \sum _{j=1}^W{\rm M}}}{}_{\text{B}}^2(i,j)}}(9)$

式中:L和W分别为矩阵的行数和列数;MA(i,j)和MB(i,j)分别为标准化后的扰动特征局部矩阵和扰动标准化模板中第i列和第j列元素幅值。

综上可知,扰动分类步骤为:首先对未知类型的SDPQD进行S变换分析,对S变换结果进行时频尺度缩放,生成全局模矩阵,然后分别计算该矩阵中与各扰动标准化模板相同大小的局部矩阵与各类扰动标准化模板的相似度,比较所得相似度的大小,如果与某一类扰动标准化模板相似度最大,则表明该扰动与这一类标准化模板内容最相近,故将未知类型扰动归为该扰动标准化模板对应的那一类SDPQD,即按相似度最大原理进行分类。

3 仿真分析

本文采用MATLAB 7.0生成8类SDPQD信号,其数学表达式及主要特征参数如表1所示。

3.1 仿真算例1

每类SDPQD信号随机生成100个测试样本,总计800个测试样本,在测试样本上叠加20 dB的高斯白噪声,计算测试样本经S变换和时频尺度缩放后的各扰动特征局部矩阵与8类扰动标准化模板的相似度。每类SDPQD的100个测试样本与该类扰动标准化模板的相似度范围分别如下:电压凹陷0.958 4～0.997 1,电压凸起0.970 6～0.995 4,电压缺口0.998 1～0.999 9,电压尖峰0.998 5～0.999 9,振荡暂态0.959 8～0.994 5,短时谐波0.973 1～0.993 3,电压凹陷+谐波0.952 3～0.982 5,电压凸起+谐波0.960 9～0.979 7。表2列出了各类扰动标准化模板之间的相似度,表3列出了每类SDPQD的100个测试样本与8类扰动标准化模板的平均相似度。从表2可以看出,各类标准化模板之间差别明显,虽然某些模板之间相似度很高(如缺口与尖峰),在其他样本与自身扰动标准化模板的相似度范围以内,但是在该类测试样本与此类模板的相似度并不高。由表3易看出,每类测试样本特征局部矩阵都与同类的标准化模板平均相似度最大,与其他扰动标准化模板差别明显,而且同一类标准化模板也只与其同类测试样本特征局部矩阵平均相似度最大且都达到了0.96以上,比文献[18]中的平均相似度更高。算例证明了利用标准化模板局部相似度分类的可行性。

注:A为扰动的幅值;t1为扰动发生时刻;t2为扰动结束时刻;c为衰减系数;α为波动频率相对系数;ω0为基波角频率;u(t)为单位阶跃函数;T为周期。

3.2 仿真算例2

在测试样本上分别叠加40 dB,30 dB,20 dB的高斯白噪声,每一类信号分别在3种噪声环境下随机各取1 000个样本,总计24 000个测试样本进行测试,这些SDPQD信号扰动时间变化较大,如电压凹陷、凸起的持续时间从1个周期至30个周期,数据本身不规则性较大。采用本文的方法,在40 dB,30 dB,20 dB噪声水平下分类准确率皆为100%,可见,该分类方法对噪声不敏感,分类结果理想。

4 结语

本文通过时频尺度缩放,并按各扰动特征取其模时频矩阵特定部分,以此持续时间不同的同类扰动可建立唯一的标准化模板作为该类扰动的标准判据,由此建立的标准化模板更能体现各类扰动的特征,每种测试样本与该类扰动标准化模板平均相似度皆达到了0.96以上,实现了对6种单一型和2种复合型SDPQD的分类。

以模板匹配的方法,按局部矩阵相似度最大原则进行分类;仿真结果表明,该方法对噪声不敏感,分类准确率高,过程简单明确,是一种有效的短时电能质量扰动分类方法。

下一步工作将考虑如何提高用该方法进行SDPQD分类的实时性。

附录见本刊网络版(http://www.aeps-info.com/aeps/ch/index.aspx)。

摘要：采用基于S变换下的模时频矩阵局部相似度对短时电能质量扰动进行分类。首先,由时频尺度缩放将各类持续时间不同的扰动特征标准化,按照各扰动特征选取其模时频矩阵特定部分,以此建立矩阵大小不一且特征明显的各类扰动标准化模板;然后计算未知扰动各局部模时频矩阵与各类扰动标准化模板之间的相似度,按照相似度最大原则将扰动进行分类。由于各类扰动在不同的时频区域高度聚合了自身特征,采用局部时频区域相似度原理大大提高了同类扰动的相似度,建立的各类扰动标准化模板之间差异明显,不使用辅助性分类器而直接实现扰动分类,且分类过程简单明确,可用于不同时间长度的扰动分类。该方法有效利用局部区域明确的时频相关性,抗干扰能力比采用全局相似度强。仿真结果表明了很好的短时电能质量扰动分类效果。

局部相似度 第3篇

Zadeh提出的模糊集成为处理不完全信息和不精确数据的智能推理的重要工具,在自动控制,模式识别、目标决策和智能系统等多个实际领域取得了成功应用。但随着应用的深入,人们发现它存在表现力不足的缺陷。例如,模糊集的隶属函数值是一个单一的值,对多维数据不能同时表示。

Gau等在分析Fuzzy集的局限性后,于1993年提出了Vague集。Vague集的tv(u)、fv(u)、1-tv(u)-fv(u)所对应的支持度、反对度、未知度被称Vague集的三要素,其隶属度不是单值,而是一个区间[tv(u),1-fv(u)],它们解决了Fuzzy集单值隶属度表现力不足的缺陷。目前,Vague集已在模糊分类、目标决策、模式识别、医疗诊断等领域取得了许多应用研究成果。在这些应用中相似度量是关键核心技术。但是现有的Vague集相似度量公式都是基于距离测度的,因此只要Vague集间的距离测度一样,它们就无法分辨,因此非常有必要寻找其它相似度量计算方法。文献[16]、[17]分别从模糊集贴近度理论导出了Vague集的相似度公式,为我们构造Vague集相似度量提出了一种新的思路。笔者将文献[16]的包含度概念和算术平均法相结合,推导出一种改进的基于包含度概念的Vague集相似度量,并通过实例验证,对基于包含度的Vague集相似度量理论进行了完善。

1 Vague集定义

定义1:令U是一个论域,对U的任一元素x,U中的一个Vague集V用一个真隶属函数tv(x)和一个假隶属函数fv(x)表示。tv(x)是从支持x的证据所导出的x的真隶属度下界,fv(x)则是从反对x的证据所导出的x的否定隶属度下界,tv(x)和fv(x)将区间[0,1]中的实数与其中每一元素联系起来,即:

undefined

其中,tv(x)+fv(x)1。

由对于任意Vague集V,tv(x)是Vague集V的真隶属函数,它表示支持x∈U证据的必要程度;fv(x)是Vague集的假隶属函数,它表示反对x∈U证据的必要程度;1-fv(x)则表示支持x∈U证据的可能程度;πv(x)=1-tv(x)-fv(x)表示x∈U的不确定程度。

当x是连续时,一个Vague集V可用以下表达式表示:

undefined

当X是离散时,一个Vague集V可用以下表达式表示:

undefined

定义2:Vague集A和B,A⊆B当且仅当对论域X上的任意一个元素x都有:tA(x)tB(x),fB(x)fA(x)。

定义3:Vague集A和B的并集是C,即C=AUB,其真假隶属度函数分别为:tC(x)=max(tA(x),tB(x)),1-fC(x)=max(1-fA(x),l-fB(x))

定义4:Vague集A和B的交集是C,即C=A∩B,其真假隶属度函数分别为:tC(x)=min(tA(x),tB(x)),1-fC(x)=min(1-fA(x),l-fB(x))。

定义5:Vague集A和B的和集是C,即C=A B,其真假隶属度函数分别为:tC(x)= tA(x)+tB(x),1-fC(x)=(1-fA(x))+(l-fB(x))。

2 Vague集上的包含度

定义6:称函数M:VSs(X)VSs(X)[0,1]为VSs(X)上的一个包含度,如果S满足如下性质:

(CP1)S(A,B)=1当且仅当A⊆B ;(CP2)如果tA(x)>0,x∈X,那么S(A,A-)=0当且仅当A=X-);(CP3)若A⊆B⊆C,则S(C,A)min(S(B,A),S(C,B))。

3 Vague集的相似度量准则

定义7:称函数S:VS(X)VS(X)[0,1]为Vague集A和B之间的相似度量,如果它满足如下准则:

准则1 (有界性)S(A,B)∈[0,1];准则2 (对称性)S(A,B)=S(B,A);准则3 (归一性)S(A,B)=1⇔A=B;准则4 (单调性)若A⊆B⊆C,则S(A,C)S(A,B)并且S(A,C)S(B,C)。

4 Vague集上的相似度量

文献[16]基于包含度的相似度量其实质上和文献[17]一样,都是基于最大最小值的相似度量,所以具有共同的缺陷,为了更好地度量Vague值之间的相似程度,利用文献[16]Vague包含度和文献[19]相似度的一般定义,给出了一种新的相似度量。

首先考虑Vague值的相似度量新方法,再计算Vague集之间的相似度量。

设x=[tx,1-fx],y=[ty,1-fy]是论域U上的两个Vague值,则

undefined

定理1:式(1)中的MJ(X,Y)是满足准则1-6的Vague值相似度量。

证明:

准则1:有界性。

由于tx∈[0,1],fx∈[0,1],ty∈[0,1]fy∈[0,1],有:

当tx≥ty时,因undefined,所以undefined。同理,当ty≥tx时,有undefined。

同样可证,undefined

准则2:对称性。

由公式(1)可以得知,结论成立。

准则3:归一性。

由MJ(X,Y)=1⇔(tx+ty+1-fx+1-fx)=2(tx∧ty+(1-fx)∧(1-fy)) (2)

下面分4种情况讨论:①tx≥ty,1-fx≥1-fy;式(5.2)可得:2ty+2-2fy=tx+ty+2-fx-fy⇒ty-tx=fy-fx,又ty-tx0,fy-fx≥0,所以有:t-tx=0,fy-fx=0⇒ty=tx,fy=fx;②ty≥tx,1-fy≥1-fx;由式(5.2)的对称性,可知其结论同①;③tx≥ty,1-fy≥1-fx;式(5.2)可得: 2ty+2-2fx=tx+ty+2-fx-fy⇒ty-tx=fx-fy,又ty-tx0,fx-fy≥0,所以有:ty-tx=0,fx-fy=0⇒ty=tx,fy=fx;④ty≥tx,1-fx ≥1-fy;由式(5.2)的对称性,可知其结论同③。

准则4:单调性。

由X⊆Y⊆Z可知,txtytz,1-fx1-fy1-fz;

undefined

由txtyt,1-fx1-fy1-fz可知:

(tx+ty+1-fx+1-fy)/2(tx+tz+1-fx+1-fz)/2,所以有:MJ(X,Z)MJ(X,Y)。同理,有MJ(X,Z)MJ(Y,Z) 。

5 应用实例

学科建设评比实例。利用该实例的数据验证本文给出的Vague相似度量。

例1:设A1、A2、A3是3个学科建设成果的专家分别从支持、反对、弃权进行投票的Vague值,C1,C2和C3是目标集中的3个目标条件,候选方案的特征由以下Vague集表示:

A1={(C1,[1]),(C2,[0.6,0.8]),(C3,[0.3,0.4])}

A2={(C1,[0.6,0.8]),(C2,[0.5,0.7]),(C3,[0.4,0.9])}

A3={(C1,[0.6,0.7]),(C2,[0.5,0.6]),(C3,[0.4,0.8])}

这里C1,C2和C3分别是从学科建设的学术队伍、科学研究、人才培养等方面来进行评估的Vague数据。理想方案A0{[1],[0.6,0.8],[0.4,0.9]}。利用公式(1)分别计算SJW(A0,A1),SJW(A0,A2),SJW(A0,A3)。

SJW(A0,A1)=0.9,SJW(A0,A2)=0.92,SJW(A0,A3)=0.88。

因此,相应的方案的优劣排序结果为:A2,A1,A3,学科建设评估结果:学科A2为优。

6 结束语

句子相似度计算模型的改进 第4篇

句子语句相似度由词形相似度、语句长度相似度、词序相似度决定的，并在此基础上提出基于此三个特征的新的句子相似度计算模型。其中词形相似度起主要作用，语句长度相似度起次要作用, 词序相似度的作用最小。下面分别加以说明与分析。

1.1 词形相似度

语言(文中以汉字为例)中的一个语句S (Sentence) 是L中的单字和特殊符号(以下简称单字)的一个有序集合。S的长度即是S中单字的个数，此处用Length (S) 表示。SameWC (S1, S2) 表示语句S1, S2Y中相同单字的个数，当一个单字在S1, S2中出现的次数不同时，以出现次数少的计数。语句S1, S2的词形相似度WordSimilar (X, Y) 由下面公式决定：

WordSimilar (X, Y) =SameWC (X, Y) Max (Length (X) , Length (Y) )

容易得出WordSimilar (X, Y) ∈[0, 1]，其意义是两个语句相同的字数越多, 两个语句越相似。

例如：S1=正态分布的含义是什么?S2=什么是正态分布?

则WordSimilar (S1, S2) =8/11≈0.73。

1.2 语句长度相似度

Length (S1) ，Length (S2) 分别表示语句S1和语句S2的长度, 即两个语句中的单字的个数。语句长度相似度LenghtSimilar (S1, S2) 由以下公式决定，

容易得出LenghtSimilar (S1, S2) ∈[0, 1]，其意义是两个语句的长度越接近, 两个语句越相似。

如上例中Length (S1) =11, Length (S2) =8则LenghtSimilar (S1, S2) ≈0.84。

1.3 词序相似度

OrderOccur (S1, S2) 表示在S1, S2中都出现且都只出现一次的单字的集合。PFirst (S1, S2) 表示OrderOccur (S1, S2) 中的单字在S1中的位置序号构成的向量, PSecond (S1, S2) 表示PFirst (S1, S2) 中的分量按对应单词在S2中的次序排列生成的向量。

例如S1=正态分布的含义是什么?S2=什么是正态分布?

则OrderOccur (S1, S2) ={“正”，“态”，“分”，“布”，“的”，“含”，“义”，“是”“什”，“么”，“?”}，S1中单字与序号的对应关系为：

则PFirst (S1, S2) = (0, 2, 3, 7, 8, 9, 10) ，由各分量对应的单词在S2中的顺序为：

PSecond (S1, S2) = (8, 9, 7, 0, 1, 2, 3, 10) ，ReWord (S1, S2) 表示PSecond (S1, S2) 各相邻分量的逆序数。上例中：8<9, 9<7, 7<0, 0<1, 1<2, 2<3, 3<10, 得ReWord (S1, S2) =2。语句S1, S2的词序相似度由公式以下公式决定，

容易得出：OrderSimilar (S1, S2) ∈[0, 1]。

从而可以得到OrderSimilar (S1, S2) =1-2/ (8-1) ≈0.71

这样定义词序相似度的优点是：当一个分句或短语整体发生长距离移动后, 仍与原来的语句很相似。实现快捷, 算法复杂度为O (m) ，其中m=|OrderOccur (S1, S2) |。

由以上三部分可以得到语句相似度公式如下：

Similar (S1, S2) =α*WordSimilar (S1, S2) +β*LenghtSimilar (S1, S2) +γ*OrderSimilar (S1, S2)

其中α, β, γ是常数，且满足α+β+γ=1，显然Similar (S1, S2) ∈[0, 1]。

在语句相似度中我们应该能够理解词形相似度起着主要作用, 语句长度相似度和词序相似度起着次要的作用, 因此α, β, γ取值时应该有α>>β, γ。若取α=0.8, β=0.15, γ=0.05，则上例中的Similar (S1, S2) 为：0.80.73+0.150.84+0.050.71=0.75。由此在检索应用中可设置一个阀值作为相似的一个条件, 当两个语句的相似度高于这个阀值时, 就可以认为这两个语句相似。利用语句相似度可以提高检索的效率和准确性。

2 不同特征加不同权值优化模型

上一小节我们提出基于词型、词序、词长等角度的句子相似度计算改进算法。在本节中我们通过对句子的深入分析，在分别对基于词特征，词义特征的句子相似度计算的基础上，提出一种基于句子相似度平面计算模型。该方法通过对不同的特征加不同的权值来调节各个特征对相似度计算的贡献, 从而使计算结果达到优化。该方法与其他方法相比，描述句子的信息更加全面, 从而使句子相似度计算更加准确。完整的表达一个句子的信息，不但依赖于组成句子的词汇的信息, 而且还包含词汇之间的关系。本节将从句子结构信息和组成句子的词汇信息进行研究, 力求将句子的内部信息尽可能准确的刻画出来，以便更精确的进行句子相似度计算。

2.1 基于关键词特征的句子相似度计算

基于关键词特征的句子相似度计算[1]，就是通过利用两个句子中所有有效词 (去掉停用词) 来构成向量空间，然后计算两个句子的向量，利用这两个向量夹角的余弦值作为句子相似度。任给两个句子S1和S2，它们的所有有效词构成的向量空间为V= (X1, X2, Xn) ，其中Xn为有效词。句子S1的向量V1={ω1, ω2, , ωn}，其中ωn为有效词Xn在句子S1中出现的次数。句子S2的向量V2={ψ1, ψ2, ψn}，其中ψn为有效词Xi在句子S2中出现的次数。则两个句子的相似度为：

这种方法只是简单的利用了词表面信息，对于一些内容相关性较小的语料效果较好。但是这种方法没有考虑词本身的词义信息以及句子的句法信息，因此具有一定的局限性。

2.2 基于词义距离的句子相似度计算

基于词义距离的句子相似度计算[2]，需要一定的词义知识资源作为基础。计算句子之间的词义相似度，要确定句子中的词在这个句子中所表达的词义。具体方法如下：

设2个句子M和N, M包含的词为M1、M2、Mm, N包含的词为N1、N2、Nn，则词Mi (1im) 和Ni (1jn) 之间的相似度可用Similar (Mi, Nj) 表示。这样就得到两个句子中任意2个词的相似度，M和N句子之间的语义相似度Similar (M, N) 为

式中：

ai=max (Similar (Mi, N1) , Similar (Mi, N2) , , Similar (Mi, Nn) )

bi=max (Similar (Ni, M1) , Similar (Ni, M2) , , Similar (Ni, Mn) )

在相似度计算时，该种方法充分考虑了句子中每个词的深层信息，使表面不同，深层意义相同的词被挖掘出来，而基于关键词特征的相似度计算就不可识别。但由于词典的不全面和一些未登录词的词义代码的缺失，也给计算带来了误差。

2.3 改进的句子相似度平面计算模型

一个对象可以从线性，平面等角度来描述，对应于空间描述即为一维，二维等。当然维数越高，对象的描述信息越全面准确。如果按照词序列表示句子，是一维线性空间;如果句子中的每个向量按照义元来表达，相当于二维空间。两种形式相比较，从二维的角度描述句子类似于全息照片，可以使句子包含的信息更准确，更全面的表示出来。

由2.1与2.2两部分的分析可知：基于关键词特征的方法体现了句子表面的信息;基于词义距离的相似度方法体现了组成句子的每个词深层的语义信息。我们的目标是，将句子的关键词特征、词义特征，扬长避短，互为补充，共同描述一个句子，从而根据这些特征计算句子和句子之间的相似度，获得较高的准确率。这里就涉及到如何确定这些特征的权重问题，在自然语言处理中，许多问题根据经验值来确定，但我们这里将根据问题建立数学模型，引入线性回归算法进行简单的求解，从而使目标函数在一定范围内达到最优。对于线性回归算法如下：

通过以上论述，我们从两个个侧面对句子所包含的信息进行刻画，即：词特征(KW)，词义特征(SE)，并将这些特征融合起来进行句子相似度的计算，从而得到一个较准确的相似度计算方法。

由此我们可以得到平面计算模型的句子相似度计算公式如下：

1) 公式一是两个相似度相乘后开平方，

2) 公式二是将两个相似度分别乘系数后相加(其中α+β=1), Similar (S1, S2) =αSimilar1*βSimilar2

其中Similar表示S1和S2两个基于词特征的相似度值，Similar2表示S1和S2两个基于词义特征的相似度值，在此我们的目标函数是寻找一组可能的参数组合{α, β}，使得相似度的计算更加准确，其中α+β=1。为了计算α和β，我们首先限定α和β参数取值范围为 (0, 1) ，那么我们怎么样去求α和β的值呢?我们主要通过回归分析(其主要用途是预测，即给出自变量的某些取值，求出相应的点估计和区间估计)来求α和β的值，具体计算过程如下：

假定自变量Similar1和Similar2是普通变量，因变量Similar是随机变量, 并设X=Similar1、Y=Similar2、Z=Similar，对于X, Y的一组值 (X1, Y1) , (X2, Y2) , , (Xn, Yn) ，做独立实验，得到随机变量相应的观测值Z1, Z2, , , Zn，这样就得到n对数据, (X1, Y1, Z1) , (X2, Y2, Z2) , (Xn Yn, Zn) , 称为一组容量为n的样本，将n对数据描在xoyz空间上，称为散点图。散点图直观地给出了n个点所呈现的趋势。对于自动评分和人工评分间的关系, 我们将利用二元线性回归，假定对X的每个值，有Z=αX+βY。

其中，α和β是与X, Y无关的常数，称为Z=αX+βY回归方程;α和β为回归系数。我们的目的是用样本来估计α和β的值，得估计值α'和β'。称Z'=α'X+β’Y为经验回归方程。利用该回归方程就可以进行预测。我们用最小二乘法求此回归方程。根据一组样本值 (X1, Y1) ， (X2, Y2) , , (Xn, Yn) ，然后利用最小二乘法[2]α和β的值。

第一个公式适合综合两个“与”关系的因素。而第二个公式更适合于综合两个“或”关系的因素。这里选择后者。因为两个相似度是互补的关系，相对比较独立。即只要其中一个相似度较高我们就认为两个句子相似度很高。而不是一定要两者都很高才认为两个句子的相似度很高。而且选择后者可以通过改变α和β动态调节两个相似度的比重。当然每个相似度都有自己的优点和缺点。只有适当地组合才能充分发挥它们各自优势，从而获得最佳的系统性能。

参考文献

[1]赵妍妍, 秦兵, 刘挺, 等.基于多特征融合的句子相似度计算[D].哈尔滨工业大学计算机学院, 2005.

中文短语文本相似度计算新方法 第5篇

为了给两个短语文本的相似度建立统一的衡量标准, 任意两个短语文本间的相似度计算公式的构造考虑了下列因素, 做了如下设计:①相似度依赖于两个短语文本中相同文字的位置;②两个完全相同的短语文本, 其相似度应为一常数, 如常数1;当一个短语文本某个位置的文字在另一个短语文本中有多个位置上的文字相同时, 其相似度仍然为该常数;③若两个短语文本相互不包含对方元素, 则其相似度为0。

2 相关定义

为了便于算法实现, 用A=“A0A1, , Am-1”和B=“B0, B1, , Bn-1”分别表示长度为m和n的短语文本。

基于相似度依赖于两个短语文本中相同文字的位置, 定义

undefined

为A中第i个文字与B中相匹配文字的位置集合。当A的第i个文字在B中无相匹配文字时, C (A, i, B) 为空集合Ø。同时, 定义

为文字Ai的最小匹配偏移值, 定义

为文字Ai的匹配贡献值。定义

undefined

为短语文本A相对于短语文本B的相似度。

式 (4) 符合相似度公式的要求, 下面给出其证明。

证明: (1) 当C (A, i, T) ≠∅时,

undefined

所以, 当两匹配文字偏移值|k-i|越大时, 短语文本A对于短语文本B的相似度SC (A, B) 越小, 当|k-i|越小时, SC (A, B) 越大, 即相似度依赖于两个短语文本中相同文字的位置。

(2) 当C (A, i, B) =Ø时,

即当两短语文本相互不包含对方元素时, 相似度为0。

(3) 当C (A, i, B) ≠∅且两短语文本完全相等时, 有

undefined

即两短语文本完全相等时相似度为常数1。

(4) 在两短语文本完全相等的情况下, 由于undefined, 那么短语文本A中的某一文字不管与短语文本B中多少个位置上的文字相同, 与i不同位置的k不会对相似度有影响, 即此种情况下d (A, i, B) 始终为0。例如:短语文本A=B=“1中3中中6”, A的第2个位置上的“中”字, 与短语文本B的第2、4、5个位置上的文字都相同, 根据公式 (2.1) 有C (A, 2, B) ={2, 4, 5}, 再根据公式 (2) 有undefinedd(A, 2, B) =min{|k-2||k=2, 4, 5}=min{|2-2|，|4-2|，|5-2|}=min{0, 2, 3, }=0, 所以不管B中有几个文字与“中”字相同, d (A, 2, B) 始终为0。

由 (4) 式得到的SC (A, B) 是一个相对值, 它表征B相似于A的程度, 而用同样的方法计算所得的SC (B, A) 也是一个相对值, 表征A相似于B的程度, 一般情况下, SC (A, B) ≠SC (B, A) , 所以不能由 (4) 式得到的值作为最终的短语文本A与B之间的相似程度。然而聚类时对象之间的相似度不存在参照与被参照的关系, 所以针对文本聚类的需要, 我们另外定义

undefined

作为短语文本A与短语文本B的相似度。

3 代码描述

根据上述短语文本相似度的定义, 用C#语言实现相似度计算中的主要函数, 包括计算文字匹配最小位置偏移值PosOffset函数、文字匹配贡献值CC函数、相对相似度SC函数和短语文本相似度S函数。

设m、n分别为短语文本A和短语文本B的长度, 那么当A与B相等时算法的时间复杂度为O (m+n) , 当A与B不等时算法时间复杂度为O (mn) 。由于算法只使用一维数组作为存储变量, 所以算法的空间复杂度较小。

4 算法的合理性检验

为了验证该算法的合理性, 设计了一套方案进行测试, 为了更好地反映各种因素对相似度值的影响, 实验中测试数据多处用数字代替不同的汉字, 具体内容如下:

(1) 验证短语文本完全相同时相似度是否为1, 完全不同时相似度是否为0。用“大学物理实验”分别与“马克思主义哲学”、“大学物理实验”比较, 用“中华人民共和国”分别与“湖南省长沙市”、“中华人民共和国”比较, 该算法计算的结果依次为“1”、“0”、“1”和“0”, 与期望值是相同的。

(2) 对于给定的两个短语文本A和B, 验证算法结果是否与两文本的调用顺序有关。我们取三组文本进行验证, 结果如表1所示。

由表1可以看出, 计算结果与两文本的调用顺序无关, 符合要求。

(3) 验证文字匹配偏移值对算法结果的影响, 即是否是偏移值越大, 两文本相似度越小, 反之越大。分别取1个、2个、3个文字匹配时的3组情形进行试验。

对于固定短语文本“语”, 分别取“语”、“英语”、“1英语”、“12英语”、“123英语”、“1234英语”与之比较, 得到的文字匹配偏移值文本相似度, 如图1所示。

对于固定短语文本“英语”, 分别取“英语123”、“英1语23”、“语英123”、“1英2语3”、“31英语2”、“31英2语”与之比较, 得到的文字匹配偏移值累加和文本相似度如图2所示。

对于固定短语文本“信息所”, 分别取“信息所12”、“信息1所2”、“息信所12”、“1信息所2”、“息所信12”、“息所1信2”、“息所12信”与之比较, 得到的文字匹配偏移值累加和文本相似度如图3所示。

(4) 验证对于一个固定的短语文本, 与另一短语文本的匹配文字位置相同情况下, 另一短语文本的长度对于相似度值的影响。我们分别取第1个位置和第2、4个位置相同的情况进行实验。

对于固定短语文本“语用知识库”, 分别取“语”、“语言”、“语议论”、“语法规则”、“语法 (上) ”、“语言学 (二) ”与之比较, 得到的短语文本长度文本相似度如图4所示。

对于固定短语文本“原理与构成”, 我们分别取短语文本“物理结构”、“1理2构3”、“1理2构34”、“1理2构345”、“1理2构3456”与之比较, 得到的短语文本长度文本相似度如图5所示。

(5) 验证对于一个固定长度的短语文本, 两文本匹配文字个数相同情况下, 另一短语文本长度对于相似度值的影响。取有2个匹配文字、3个匹配文字和5个匹配文字的情况分别进行试验。实验结果如表2所示。

从以上各项实验内容可以看出, 随着文本间相匹配情况的变化, 用此方法计算出的两文本的相似度值受很多因素的影响出现相应的变化, 且变化趋势与人们的主观判断相符合, 所以说综合考虑以上各种因素而设计的相似度计算公式是合理的, 可以将该公式用于短语文本的相似度计算。

5 结束语

文章针对中文短语信息的处理问题, 提出了一种新的中文短语文本相似度计算方法, 并对其进行了详细的描述。该算法首先定义了文字匹配位置集合, 然后定义了文字匹配最小位置偏移值, 在此基础上提出了文字匹配贡献值的概念, 又进一步定义了文本相对相似度, 最后提出了两短语文本之间的相似度计算公式。算法合理性检验结果表明, 用该方法计算出的不同短语文本之间相似度值的变化趋势是合理的, 可以满足短语文本分类、聚类、信息检索等的基本需要。

摘要：针对短语文本的分类、聚类、信息查询问题, 提出了一种新的中文短语文本相似度计算方法。用该方法计算出的文本相似度及一个比较文本与多个被比较文本所得相似度变化趋势是合理的, 因此可以满足短语文本分类/聚类和信息查询的需要。

关键词：相似度,文字匹配位置集合,文字匹配最小位置偏移值,文字匹配贡献值,短语文本相对相似度

参考文献

[1]李星毅, 增路平, 施化吉.基于单词相似度的文本聚类[J].计算机工程与设计, 2009 (8) .

[2]何海江.一种适应短语文本的相关测度及其应用[J].计算机工程, 2009 (6) .

[3]周法国, 杨炳儒.句子相似度计算新方法及在问答系统中的应用[J].计算机工程与应用, 2008 (1) .

试卷相似度自动评估技术的研究 第6篇

考试是反馈教学信息、评价教学质量、调控教学过程的重要手段,是学校教学质量监控与保障体系中不可缺少的重要环节。在试卷的命题管理工作中,一项重要的内容是控制试卷的相似度。例如,规定每门课程连续三年试卷内容相似度不得超过30%,A、B卷内容相似度不能超过30%等。通过人工方式对试卷进行相似度评估的工作量非常大。因此,研究试卷相似度自动评估技术,对于大规模考试管理具有非常重要的现实意义。

由于试卷相似度自动评估需要从语义上对试题进行理解,所以试卷相似度自动评估在很大程度上依赖于自然语言理解领域的理论和技术。例如试题“将数组中的数据按逆序排列”和试题“从大到小排列数组中的数据”虽然表述不同,但却属于相似试题。本文借鉴自然语言处理领域文本相似度计算方法[1,2,3,4,5,6],改进基于知网的词汇语义相似度计算方法,提出试题相似度和试卷相似度计算方法,解决了大规模考试管理中相似试卷的识别困难。文中开发了试卷相似度自动评估系统,其测试结果初步达到预期目标。

1 试卷相似度自动评估系统简介

1.1 试卷相似度自动评估系统的功能模块

试卷相似度自动评估系统包括试卷录入子系统、试卷管理子系统、试卷印刷子系统和系统管理子系统4个子系统(见图1)。

(1)试卷录入子系统为出卷教师提供了录入/修改试卷和试卷相似度自动评估功能。

(2)试卷管理子系统供各系部教务员使用,功能包括:

(1)查询本系各学期、各科目教师试卷的录入情况,以方便督促教师及时录入试卷;

(2)导出试卷进行审核,由于试卷中可能包含图片等非文本信息,自动导出的试卷可能存在格式等一些小问题,所以教务员需导出试卷进行审核;

(3)审核无误后,将试卷以WORD文件格式上传,为试卷印刷做准备;

(4)查询试卷的印刷情况。

(3)试卷印刷子系统供试卷印刷部门的工作人员使用,功能包括:

(1)查询待印刷的试卷(按考试时间先后或专业等进行排序),工作人员将试卷下载打印后进行印刷,非常方便;

(2)印刷完成后可将该试卷标识为已经印刷,各系部教务员可通过系统进行查询。

(4)系统管理子系统供系统管理员使用,完成试卷库的管理和用户信息管理。

1.2 试卷相似度自动评估的工作流程

试卷相似度自动评估系统的工作流程如图2所示。其中,试卷库存储往年各专业、各科目的试卷。命题教师将试卷录入到试卷评估系统,试卷评估系统将试卷与试卷库中往年同专业、同科目试卷进行相似度计算,若相似度均没有超过设定的阈值,则将试卷加入试卷库,返回“通过”的提示信息;若与某份试卷的相似度超过设定的阈值,则将待评估试卷中相似试题的题号和往年试卷中的相似试题返回给命题教师,供其修改试卷之用,命题教师修改之后可重新录入,并再次进行评估。

2 试卷相似度计算

2.1 相关概念的定义

(1)试题相似度:两道试题的相似程度。

假设用SimST(A,B)表示两道试题A和B的相似度,则SimST(A,B)∈[0,1],0表示两道试题完全不相关,1表示两道试题完全相同。

(2)相似试题:两道试题之间的相似度值如果超过一个设定的阈值(如70%),则认为是相似试题。

(3)试卷相似度:两份试卷的相似程度。

假设用SimSJ(A,B)表示两份试卷A和B的相似度,则SimSJ(A,B)∈[0,1],0表示两份试卷完全不相关,1表示两份试卷完全相同。

2.2 试卷相似度计算的流程

试卷相似度计算的流程主要包括:试卷预处理、试题分析、词汇相似度计算、试题相似度计算和试卷相似度计算5个步骤,如图3所示。

2.2.1 试卷预处理

试卷预处理是对原始试卷文本进行初步加工,主要包括:特殊元素抽取和客观题信息填充两部分。特殊元素抽取是指将试题文本中的特殊元素抽取出来。如果试题文本中包括了诸如数学公式、表格或图片等非常规文本时,需先将这些特殊元素抽取出来。客观题信息填充是指将客观题的信息补充完整。选择题和填空题等客观题信息不完整,且答案在表达试题语义方面往往起重要作用。为提高试题相似度计算的精度,需将试题答案添加到试题中,删除选择题各选项文本,以使试题变成一个完整的信息。预处理后的试卷由多个字符串组成,每个字符串即是一道试题。

2.2.2 试题分析

试题分析包括词法分析和关键词提取。词法分析主要包括汉语分词、词性标注、切分排歧和未登录词识别。目前词法分析研究已经比较成熟,有很多现成的程序可以使用。本研究采用了中国科学院计算技术研究所研制的汉语词法分析系统ICTCLAS2009。该系统对大部分词汇切分效果较好,但在不添加用户词典的情况下,专业词汇的切分效果不理想。如:

原始试题(判断题):认知学徒制是一种典型的认知主义教学模式。

分析结果:认知/v学徒/n制/k是/v一/m种/q典型/a的/u认知/v主义/n教学/v模式/n。/w

从上面例子可以看出,试题中的“认知学徒制”、“认知主义”、“教学模式”等专业词汇切分过细。ICTCLAS2009允许用户添加用户词典,可以将课程中涉及的专业词汇添加到系统中,提高词法分析的精度。通过将“认知学徒制”、“认知主义”、“教学模式”三个专业词汇添加到用户词典之后,该试题的分析结果为:

认知学徒制/n是/v一/m种/q典型/a的/u认知主义/n教学模式/n。/w

该试题已经被正确切分,并进行了词性标注,但其中的部分词汇,如“一”,“种”,“的”及标点符号等,对表达试题的意思没有意义,而且影响相似度计算的效率和精度,所以在进行试题相似度计算之前,须将这些词汇去除。ICT-CLAS2009提供了关键词提取功能,能将试题中表达主要意思的词汇提取出来,以减少相似度计算的噪音,提高相似度计算的效率和精度。利用ICTCLAS2009将以上试题进行关键词提取,结果为:

认知学徒制 教学模式 认知主义 典型

2.2.3 词汇相似度计算

试题分析之后的试题是由一系列词汇组成的词汇向量。试题词汇相似度计算采用基于知网的词汇相似度计算方法。知网(英文名称为HowNet)是一个以汉语和英语的词语所代表的概念为描述对象,以揭示概念与概念之间以及概念所具有的属性之间的关系为基本内容的常识知识库。一个词汇在知网中用一个或多个概念进行描述,每一个概念用一系列的义原进行描述。义原是最基本的、不易于再分割的意义的最小单位[5]。刘群和李素建提出的基于知网的词汇语义相似度模型[6]通过计算义原相似度,来计算概念相似度,最后计算两个词汇的语义相似度。该模型能够反映两个词汇语义上的相似程度。但由于试题中包含较多专业词汇,且专业词汇不包含于知网中,无法直接使用该模型进行词汇相似度计算。另由于试题相似度计算的计算量较大,为提高效率,对词汇相似度计算方法进行改进。改进的词汇语义相似度计算方法描述如下:

该方法主要从四方面进行改进:

(1)专业词汇和其它词汇的相似度设置为一个很小的常数(δ),专业词汇与专业词汇如果相同,则相似度设置为1,否则为一个很小的常数(δ),提高效率。

(2)如果词汇W1,W2相同,且词性标注也相同,则不进行义原相似度、概念相似度和词汇相似度计算,直接将两个词汇的相似度设置为1,以提高系统性能。

(3)若两个词汇词性不同,则两个词汇相似的可能性较小,直接将其相似度设置为一个很小的常数δ,减少计算量。

(4)当两个词汇不同,但词性标注相同时,在刘群、李素建的方法[6]基础上进行改进(即New_HowNet方法):在计算两个词汇的相似度时,只选择与标注词性相同的概念进行计算。例如词汇A在知网中用3个概念进行描述,其中一个概念的词性为名词,其它两个概念的词性为动词,试题中词汇A被标注为名词,则在相似度计算时,只选择其中名词词性的一个概念进行计算,其余两个概念不参与计算。

2.2.4 试题相似度计算

在词汇相似度计算的基础上,计算两道试题的相似度。假设试题T有n个词汇T1,T2Tn,试题T’有m个词汇T’1,T’2T’m,分别计算T中每个词汇与T’中各个词汇的相似度,得到矩阵如式(1)所示:

其中s(Ti,T’j)表示试题T中的词汇Ti,和试题T’中的词汇T’j的词汇相似度。分别取矩阵中各行的最大值,再对提取的最大值加权求和,即得到试题T和试题T’的相似度[7],如式(2)所示。

其中,ωi为各行最大值的权重,SimST(T,T’)为试题T和试题T’的相似度,SimST(T,T’)∈[0,1],1表示两道试题完全相同,0表示两道试题完全不相关。

各词汇权重根据其词性和是否是专业词汇确定。如果两道试题出现相同的专业词汇,则两道试题为相似试题的可能性较大,所以对于专业词汇在计算相似度时应设置为最高的权重(如可取2),名词、动词和形容词等关键词汇反映了试题主要语义信息,这些词的权重也较高,其它词汇权重较低。

经过大量试题相似度计算实验,实验结果表明,δ取0001,专业词汇权重取2,关键词汇(名词、动词和形容词)权重取1.5,其它词汇权重取1,并将相似试题的相似度阈值设置为0.7比较合适。

2.2.5 试卷相似度计算

试卷相似度在试题相似度计算的基础上进行。假设试卷A有m道试题A1,A2,,Am,试卷B有n道试题B1,B2,,Bn。分别计算试卷A中每道试题与试卷B中各道试题的相似度,若相似度最大值超过设定的阈值,则将该题标记为相似试题,最后求相似试题的分数之和,与试卷总分的比值,得试卷A与试卷B的相似度。试卷A,B相似度计算方法具体描述如下:

3 实验结果

为检验该系统的性能,选择不同专业10门课程进行试卷相似度评估测试。先将各课程去年试卷加入试卷库,各课程分别设计10份试卷(其中一份试卷与去年试卷完全相同,一份为其它课程完全不同的试卷,其余8份试卷含有部分相似试题),共100套试卷与试卷库中相同课程的试卷进行相似度计算测试,测试结果与人工检测的结果基本相同,证明本文所研究的试卷相似度计算方法是有效的。测试结果数据见表1。

4 结束语

文中阐述了试卷相似度计算的相关算法,首先对试卷进行预处理,将试卷分割成一道道独立的试题字符串;其次利用中国科学院计算技术研究所研制的汉语词法分析系统ICTCLAS2009对各道试题进行词法分析和关键词提取;再在刘群、李素建的基础上,结合试题相似度计算特点,设计词汇相似度计算方法,通过词汇相似度设计试题相似度计算方法,最后根据试题相似度计算试卷的相似度,从而实现了对试卷相似度自动评估,解决大规模试卷管理中试卷相似度评估的困难。实验测试结果基本达到预期目标。随着计算机技术和网络技术的发展,基于大规模电子题库随机抽题自动组卷的无纸化考试方式日益普及。文中所述的试题相似度计算方法在电子题库相似试题自动检测方面也适用。

摘要：针对大规模考试管理中存在相似试卷识别的困难,提出一种试卷相似度自动评估算法。参考现有知网词汇语义相似度计算方法,结合试卷相似度计算领域特点,改进词汇语义相似度计算方法,提出试题相似度和试卷相似度计算模型,实现对试卷相似度的自动评估,提高了大规模考试管理的工作效率。通过抽取各专业部分试卷进行相似度自动评估测试,测试结果与人工评估结果基本一致,达到预期目标。

关键词：试卷相似度,自动评估,语义相似度,知网

参考文献

[1]李玉红,柴林燕,张琪.结合分词技术与语句相似度的主观题自动判分算法[J].计算机工程与设计,2010,31(11):2663-2666.

[2]高思丹,袁春风.语句相似度计算在主观题自动批改技术中的初步应用[J].计算机工程与应用,2004,14:132-135.

[3]张亮,冯冲,陈肇雄,等.基于语句相似度计算的FAQ自动回复系统设计与实现[J].小型微型计算机系统,2006,27(4):720-723.

[4]王金铨,梁茂成,俞洪亮.基于N-gram和向量空间模型的语句相似度研究[J].现代外语,2007,30(4):405-413.

[5]董振东,董强.知网[EB/OL].http://www.keenage.com/html/e_index.html.2010-8-1.

[6]刘群,李素建.基于《知网》的词汇语义相似度计算[EB/OL].http://www.keenage.com/html/e_index.html.2010-8-1.

基于特征提取的图像相似度研究 第7篇

实验所选的算法简介如下。

1. 读入图片。2. 建立模型 (以颜色直方图为例) 。R、G、B各分量中每个分量有256 级灰度。总共有768 级灰度, 建立一个768 维的向量, 每一位代表所含像素占整个图像的比例。HSI空间模型先把RGB转换为HSI空间模型, 同样建立768 级分量。对查询图片与图片库图片进行前两步骤。3. 利用四种距离计算图像库中各图像和查询图像的距离。4. 根据距离大小进行排序, 输出排在前面的图像。

二、实验结果分析

实验素材含有1035 幅图片, 其中1000 幅是不同的, 35幅是根据实验选取的几个图片进行不同变换产生的。实验平台是windows XP, matlab7.0, AMD 5200+。本人选取了六幅典型图片进行试验。实验结果所用时间平均值如下表所示:

对于图片搜索效果统计如下:

2.1 运算时间比较。由上表可知运算由快到慢依次为:

颜色直方图RGB> 灰度直方图> 灰度矩> 形状无关矩>颜色直方图HSI> 颜色矩RGB> 颜色矩HSI。

2.2 四种距离的比较。如下表所示, 经过多次实验可得计算所需时间排序为:

2.3 矩与直方图。根据以上实验颜色矩、灰度矩一般与颜色直方图、灰度直方图效果差不多, 直方图只考虑了像素值的一阶特征, 但是维数却很高, 多达几百维。而颜色矩、灰度矩考虑了一阶矩、二阶矩、三阶矩三个特征, 特征向量维数较低, 只有不到十维。两者效果十分接近。

2.4 RGB和HSI颜色空间的比较。RGB是最常用的表示彩色图像的方法, HSI比较接近于人眼的感觉。以它们为颜色空间各自进行特征向量提取所得的检索结果有所不同。

2.5 颜色与灰度。灰度计算相比于颜色在很多情况下计算量较少, 在很多时候检索时也能得到不错的结果, 并且也可以吧许多颜色有差异但形状类似的实物检索出来。

2.6 形状不变矩。经过实验可以看出, 形状不变矩对翻转、尺寸变换、小规模旋转不敏感。颜色虽然具有旋转90 度等不敏感, 但是某些颜色方法对于大角度如接近45 度时, 由于有了黑色填充画布, 颜色的比例发生了变化, 对此颜色也变敏感了。

三、小结

实验表明, 颜色作为图像的最重要特征, 可以很容易把图像分类。直方图与矩来描述图像虽然处理过程不同, 但是结果相差不大。形状无关矩很适宜描述一幅特定图像, 但不适宜进行相似度比较。综合多种特征进行图像检索效果往往比使用单一特征效果要好。