相似性匹配（精选6篇）
相似性匹配 篇1
0 引言
电力系统故障诊断是指利用电力系统故障过程中产生的遥测、遥信和事件顺序(sequence of event, SOE)信息等,判断故障元件及故障类型,识别不正确动作的保护和断路器,辅助调度或运行人员处理故障,以缩短事故处理时间,防止事故扩大,加速系统恢复。经过30多年的努力,国内外在电力系统故障诊断领域提出了多种方法,主要有专家系统、解析模型、人工神经元网络、Petri网、粗糙集理论等。
基于专家系统的电力系统故障诊断方法利用保护设备动作规则建立知识库,用警报信号激活相应规则,通过推理识别故障元件,适用范围比较广,并在一些电力系统中得到了应用[1,2,3];不过,专家系统要求知识库完备,而知识库的维护比较困难,这样就很难保证有很好的容错能力,此外诊断速度也不够快。基于解析模型的方法[4,5,6]考虑故障元件与保护、 断路器动作的逻辑关系,将电力系统故障诊断问题描述为0-1整数规划问题,并采用优化算法求解;这种方法在一些实际电力系统中已经得到了应用,但对警报信号时序特征的利用不够系统和充分。基于人工神经元网络的电力系统故障诊断方法[7]的性能取决于训练样本是否完备,这一般无法保证;此外, 电力系统运行状态变化很快,这样就需要经常更新神经元网络,而训练过程很耗时;到目前为止,这种方法尚没有 在实际电 力系统中 得到应用 的报道。 Petri网理论[8,9,10]通过构造有向图的组合模型,采用矩阵运算求解,速度较快;但这种方法尚未能系统地计及警报的时序特征。粗糙集理论[11]的基本思路和专家系统类 似,但描述启 发式专家 知识的能 力更强。
如何充分利用系统发生故障后的各种警报信息,尤其是其时序特性,以提高故障诊断的准确性和容错性,已经成为电力系统故障诊断领域有待解决的重要问题。文献[6]通过引入时序约束网络,构建了利用时序信息的警报处理解析模型。文献[8]利用警报事件发生次 序,提出了基于时序模糊Petri网的电力系统故障诊断模型。文献[9-10]则进一步利用时序约束网络发展了基于电气量判据、保护判据和断路器 判据的多 源信息延 时约束加 权模糊Petri网故障诊断模型,但对时序信息的利用局限于数据筛选方面,未能充分利用时标偏差与信息准确程度的关联性。
时间序列在科学、工程、经济、社会等各个领域中广泛存在,每时每刻 都会有大 量的时间 序列产生[12,13]。数据挖掘技术是20世纪90年代中后期兴起的一门跨学科的综合研究领域,旨在从海量数据中提取出潜在的、有价值的知识甚至规律;而作为一种常见而重要的数据类型,时间序列的数据挖掘和分析是目前数据挖掘中最具有研究意义的问题之一[14]。
随着以现代信息技术为基础的电力系统调度自动化系统的发展,调度中心采集到的故障警报信息越来越多。基于全球定位系统(GPS)的全网对时的SOE信息包含了统一时标基准的警报时序信息,形成了较为准确的时间序列。如果能有效利用其蕴涵的信息,将能提高故障诊断的准确性和效率。
在时间序列挖掘的诸多任务和问题中,时间序列的相似性是最基础的问题,包括如何判别时间序列是否相似、如何衡量相似程度等[15]。
针对输电系统的实际情况,本文引入时间序列的数据挖掘概念,利用相似性的相关理论和方法为输电系统故障诊断提供决策支持。首先描述时间序列、关联时间序列组、时间序列相似性匹配等概念及其数学意义,之后分析了电力系统中警报信息的时间序列特性,建立了相关的时间序列模型。在此基础上,对电力系统时间序列距离概念进行了改进,以更好地衡量警报假说时间序列与实际警报信息时间序列间的相似程度。之后,将警报假说时间序列与实际警报信息时间序列之间的距离转换成元件故障的置信度,从而识别故障元件和故障类型。最后,对文献[10]中的多个故障场景及两个实际电力系统中的案例进行了测试,并与近年来提出的两种输电系统故障诊断方法[6,10]进行了比较分析。
与现有应用时序信息的故障诊断方法相比,本文所提出的故障诊断方法对时序信息的利用不仅局限于数据筛选,而且充分利用警报信息的时序与关联特性。通过利用时间序列的距离衡量时间不同步对警报信息准确性的干扰及警报信息漏报误报的严重程度,提高了故障诊断的准确度和容错性,在复杂故障、并发故障情况下能够正确识别警报漏报/误报等情况,同时运算速度快,满足在线运行要求。
1 时间序列相似性匹配
1.1 时间序列的数学描述
时间序列是某个物理量的记录值和时间节点组成的元素的有序集合[12],可记为:
式中:xi=(vi,ti)表示时间序列在ti时刻所记录的信息为vi;n为时间序列X的势,记作|X|=n;时间序列中时 间节点严 格递增,即i≤jti≤tj, i,j=1,2,…,n。
在狭义时间序列中,vi一般指某一实数值。在广义时间序列中,vi不仅局限于数值,也可以是多媒体数据、离散符号、自定义模型数据等多种信息。
1.2 关联时间序列组
对于时间 序列X1= {x1′,x2′,…,xk′, xk+1′,…,xm1′},X2={x1″,x2″,…,xk″,xk+1″,…, xm2″},…,Xn={x1(n),x2(n),…,xk(n),xk(n+)1,…,xm(nn)} (m1,m2,…,mn>k)的前k项元素相同(即x1′= x1″= … =x1(n),x2′=x2″= … =x2(n),…,xk′= xk″=…=xk(n)),可定义关联时间序列组:
式中:;f为标识位,f=1表示时间序列集合{Xi,i=1,2,…,n}的元素为并发时间序列,即时间序列Xs发生后Gx中的时间序列会同时发生,f=0则表示互斥时间序列,即Gx中的时间序列有且仅有一个会发生。关联时间序列组即一系列时间序列的集合。
1.3 时间序列的距离
时间序列的相似性常用距离来衡量[15],距离越小,两个时间序列的相似度就越高。时间序列的建模在不同应用领域有所不同,而时间序列距离的定义也随着时间序列建模方法不同而有所差异。
常见的时间序列距离包括欧式距离[16]、动态时间弯曲距离[17]、最长公共子串[18]、概率距离[19]、编辑距离[20,21]等。其中,编辑距离是计算两字符串序列间距离的一种量度;其需要将时间序列进行量化处理和编码后形成字符串,然后计算一个字符串转换为另一字符串所需的最小编辑操作步数。编辑操作包括插入、删除和替 换三种。对于字符 串序列X={x1,x2,…,xm}和Y={y1,y2,…,yn},序列X和序列Y之间的编辑距离Dm,n可用式(3)从D0,0递归计算得到。
式中:当xi= yi时,L (xi,yj)= 0,否则, L(xi,yj)=1。
编辑距离的计算方法成熟,可用于衡量电力系统中警报信息漏报/误报的严重程度。然而,编辑距离对于不同步的时间序列效果较差,警报信息时标信息不准确时就可能导致较大偏差。
动态时间弯曲距离在语音数字处理领域有诸多成功的应用,其允许不同步的点对应计算,也允许两时间序列长度不同,对同步问题不敏感。其本质是通过寻找两时间序列间的最小路径来计算它们间的距离,可以递归定义为:
式中:d (x1,y1)= ‖x1-y1‖;R (X )= {x2, x3,…,xm};R(Y)={y2,y3,…,yn}。
电力系统故障诊断既需要考虑警报信息漏报/ 误报情况,也需要适当计及时间不同步对警报信息准确性的干扰。本文结合编辑距离和动态时间弯曲距离的优点,在2.4节将提出一种适于衡量警报信息相似度的距离概念。
时间序列的相似性匹配分为全序列匹配查询和子序列匹配查询。全序列匹配查询是从预设的查询序列集合中,找出与被查询序列在整体上满足相似性的时间序列,所获得的匹配序列应与被查询序列的势大致相同。子序列匹配查询则是从势远大于查询序列的被查询序列中找出所有与查询序列距离小于给定距离的子序列的位置偏移和长度。电力系统发生故障后警报被集中送到调度中心形成警报序列,而可疑元件的故障假说则一般形成一个势小于警报序列的警报假说序列,这样若能在警报序列中找到与假说序列小于给定距离的子时间序列,则可视该故障假 说为真。因此,本文采用 子序列匹 配查询。
2 电力系统中的时间序列
当电力设备遥信动作时,保护设备或智能电力仪表会自动记录下动作时间、动作原因,形成基于统一时标基准的SOE信息。这些信息构成了较为准确的时间序列。
2.1 电力系统中的时间序列模型
设x=(v,t)为时间序列中的元素,定义警报信息v为一个3元组:
式中:A为警报事件,其既可表示在调度中心收到的设备动作或警报信息,也可表示系统中发生的某一事件(如输电线路发生单相接地故障);Δt为时间误差长度,用于描述事件发生时间不确定的情况, t和 Δt共同组成了一个时间约束,即事件A发生时间为[t-Δt/2,t+Δt/2];S为模糊项标识位,S=1和0分别表示元素x=(v,t)为必需项和模糊项。
若元素为模糊项,则时间序列X1={x1,x2,…,xn}虽然比X2={x1, x2,…,xi-1,xi+1,…,xn}多了元素xi,但X2与X1之间的编辑距离仍为0,称编辑距离为0的两个时间序列为等价时间序列。若元素xi=(vi,ti)(i= 1,2,…,n)为必需项,则X2与X1之间的编辑距离为1。
电力系统中发生的部分事件由于不具备信息上传能力,调度中心获取的时间序列并不包含这些事件,这部分警报信息与漏报/误报信息应该在诊断过程中加以区分。如发生故障的电气设备的保护装置动作发出跳闸指令后,断路器拒动,或断路器动作后绝缘被击穿,均有可能触发断路器失灵保护;然而, 断路器拒动事件无法直接从警报信息中获得,调度中心既有可能收到了断路器的动作信息(断路器动作后被击穿),也有可能未收到(断路器拒动),因此对该断路器上传的信息应有所警惕,不应简单视为漏报或误报。引入模糊项概念有利于区分 这些信息,提高故障诊断准确度。
在时间序列模型中,当Ai为以下事件时,元素xi=(vi,ti)应为模糊项:1Ai为电气设备故障,如输电线路、母线、变压器等发生故障;2Ai为断路器动作且Ai+1为该断路器的失灵保护动作。
2.2 电力系统中的保护配置通用模型
电力系统发生故障后,保护和断路器的警报信息就构成了警报时间序列。根据保护装置整定规范,可以构造一系列警报假说时间序列,如图1所示 (用$表示时间序列结束点)。
由图1可以看出,保护设备配置所生成的每一个时间序列都会以“$”或另一套保护装置动作结束。对于触发另一套保护装置的情形,由于保护装置动作是另一个系列的时间序列的起始元素,从而就形成一系列更长的时间序列。如此获得的所有时间序列就构成被查询时间序列集。
对于关联时间序列组G1的任一元素,事件发生时间ti按保护装置整定值设定,时间长度 Δti则根据允许的事件时间误差设定。当保护装置动作时,关联时间序列组中的时间序列相继发生,信息汇集后进入调度中心,形成准确的时间序列。
以图2为例,设输电线L1在t=0时刻发生瞬时单相接地故障并重合闸成功。
用时间序列描述为:
式中:x1=(v1,t1)=((L1线发生单相接地故障,0, 0),0);x2=(v2,t2)=((A站L1主保护动作,0,1), 49);x3=(v3,t3)=((B站L1主保护动作,0,1), 50);x4= (v4,t4)= ((C1分闸,0,1),100);x5= (v5,t5)= ((C2分闸,0,1),100);x6= (v6,t6)= ((C1重合闸,0,1),1 100);x7=(v7,t7)=((C2重合闸,0,1),1 105)。
根据SOE信息,调度中心 获取到时 间序列X2={x2,x3,x4,x5,x6,x7}。X1与X2等价。事件vi(i=1,2,…,7)在一个确定的时间点发生,该时间点记为ti,时间长度 Δti=0。
输电线L1两端的线路主保护的动作逻辑可用关联时间序列组G2描述。以断路器C2一侧为例:
式中:Xs= {((C2侧L1线路主保 护动作,10,1), 0)};Gx= {{((C2分闸,10,1),50),((C2重和闸, 50,1),1 050)},{((C2分闸,10,0),50),((C2失灵保护,10,1),250)}}。
元素Xs中的事件“C2侧L1线路主保护动作” 会触发C2断路器分闸。若C2断路器分闸成功,则1 000ms后C2将发生重合闸操作。若C2断路器拒动,或C2动作后由于绝缘被击穿等原因断路器两端仍连通,C2失灵保护都会动作,但调度中心不一定会收到C2分闸警报信息,因此((C2分闸,10,0), 50)为模糊项。C2分闸成功与否,会形成两个互斥的时间序列,这两个时间序列在一次故障过程中有且仅有一个会发生。
2.3 警报假说时间序列集
把并未真实发生的时间序列称为警报假说时间序列。从保护配置模型得到的时间序列集合称为警报假说时间序列集。在从调度中心得到的警报信息时间序列中,挖掘和分析与警报假说时间序列集相似的时间序列,则被称为时间序列匹配。
在图2中,假设在t=0时刻L1线路发生瞬时性单相接地故障,线路两侧主保护被触发。继电保护装置的动作逻辑可用关联时间序列组表示为:
式中:x1′= ((L1线发生瞬 时性单相 接地故障,0, 0),0);x2′= ((A站L1主保护动 作,10,1),50); x3′=((B站L1主保护动作,10,1),50);x4′=((C1分闸,10,1),100);x5′= ((C2分闸,10,1),100); x6′=((C1重合闸,10,1),1 100);x7′=((C2分闸, 10,1),1 100)。
关联时间序列组G1包括时间序列假说X3= {x1′,x2′,x4′,x6′}和X4={x1′,x3′,x5′,x7′}。线路L1发生单相接地故障会同时触发X3和X4,因此相关的标识位f=1。
对于关联时间序 列组G1中的时间 序列假说X3和X4,如果在实际警报序列X2={x2,x3,x4, x5,x6,x7}中能够找到匹配的时间子序列,则可以认为X3和X4已真实发生,进而判定t=0时刻线路L1发生了瞬时性单相接地故障。
2.4 改进的时间序列距离
在衡量电力系统中两个时间序列的相似性时, 既需要计及警报信息不同所造成的差异,也需要考虑时间偏差所带来的影响。基于编辑距离和动态时间弯曲距离的概念,这里提出一种适于衡量电力系统警报信息相似度的距离概念。下面所定义的距离概念既考虑了由于警报信息漏报/误报所造成的距离,也考虑了实际警报动作存在的时间误差。
为了后面描述方便,先定义以下几个符号。
运算符:表示时间序列元素x=(vx=(Ax, Δtx,Sx),tx)和y=(vy=(Ay,Δty,Sy),ty)之间的关系;若警报事件Ax=Ay,则x|=y。
运算符|∈和:表示时间序列元素x=(vx= (Ax,Δtx,Sx),tx)与时间序列X={x1,x2,…,xn} 之间的关系;若存在xi(i=1,2,…,n),使得x|= xi,则x|∈X,否则x|
这样,电力系统 中两时间 序列的距 离可定义 如下。
对于时间序列X={x1=(vx1,tx1),x2=(vx2, tx2),…,xn= (vxn,txn)}与时间序 列Y = {y1= (vy1,ty1),y2=(vy2,ty2),…,ym=(vym,tym)}(n≤ m),如果X与Y都没有模糊项,则它们之间的距离可定义为:
式中:β=|txi-tyj′|;γ=|(Δtxi+Δtyj′)/2|;i=1, 2,…,n;j=1,2,…,p;Ys为X在Y中利用元素匹配得到的子时间序列,即Ys={y1′,y2′,…,yp′},对于任意的yi′|∈Ys,有yi′|∈X且yi′是时间序列Y的元素(i=1,2,…,p);Dedit(X,Ys)为时间序列X与Ys的编辑距离,用于识别漏报/误报的警报信息, 考虑到Ys是Y的子时间序列,式(10)是一般情况下的简化计算公式;Dtime(X,Ys)为时间序列X与Ys之间的时间距离,用于衡量时间序列在时标信息方面的差异;a为编辑距离的权重系数,可根据电力系统中警报信息上传的可靠程度给定,漏报/误报信息越少,a可给定的 越大;b为时间距 离的权重 系数,可根据警报信息的时间信息的精确程度给定,时标越准确,b可给定的越大。
编辑距离衡量了电力系统中警报信息漏报/误报的严重程度,其值越大,则警报假说时间序列的置信度就越低;如果电力系统中获取的警报信息中漏报/误报比例较大,a可取较小的值,以降低编辑距离的权重,提高模型对漏报/误报信息的容错性。如果警报信息比较完备,a可取较大的值来排除干扰项,进而避免误判。同理,在系统时序信息不精确时b可取较小的值,以降低时标不准对诊断结果准确性的影响,反之则可取较大的值。
误报和时标不准均会导致两个时间序列之间存在差异。距离函数D (X,Y)通过权重系数a和b把相关差异进行了量化,其值越小,两个时间序列之间的差异越小,二者就越相似。
2.5 时间序列元素的置信度
警报假说时间序列X与警报信息时间序列Y之间的距离越小,则该假说的置信度越高。定义警报假说时间序列X的置信度CX为:
在式(12)中,把警报假说时间序列X与警报信息时间序列Y之间的距离通过反比例函数映射至 [0,1]区间,作为假说的置信度。当该距离足够小时,警报假说的置信度为1。
电力系统发生故障时,相关保护装置将动作跳开一些断路器;在多重故障、保护和/或断路器有误动或拒动的复杂情况下,有可能存在两个甚至两个以上警报假说时间序列都有较高的置信度。例如, 对于图2所示的例子,若线路L1发生单相接地故障,X3和X4可能同时有较高的置信度。
在警报假说时间序列集中,同一个时间序列元素xi=(vi=(Ai,Δti,Si),ti)可能会在多个警报假说时间序列X1,X2,…,Xn中存在。若时间序列X1,X2,…,Xn为并发时间序列,则元素xi的置信度应为时间序列X1,X2,…,Xn的置信度 的平均值;若时间序列X1,X2,…,Xn为互斥时间序列,则元素xi的置信度应取时间序列X1,X2,…,Xn的置信度中的最大值。即
式(12)和式(13)把时间序列的相似性转换成元件动作的置信度,这样就可以识别出故障元件。
3 故障诊断过程
3.1 基于时间序列匹配的故障诊断方法
电力系统发生故障后,继电保护装置将动作跳开相应的断路器,将故障元件隔离。可以利用断路器的实时信息,识别出故障区域,故障元件的识别则可局限于故障区域所包含的元件[22],这样故障诊断的速度可以大大提高。
故障区域识别一般在事故平息后进行,此时调度中心已经接收了相关的完整警报信息,其可以形成一个警报信息时间序列,即警报信息已按时间先后顺序到达,不再发生变化。基于时间序列的故障诊断方法运算过程简单,速度快,可满足在线故障诊断要求,其诊断过程如图3所示。
具体步骤如下。
步骤1:通过搜索系统中的无源区域,得到可疑故障元件集。
步骤2:根据保护设备整定规范,对涉及可疑故障元件的保护设备生成保护配置通用模型。在该模型中保护设备配置所生成的每个时间序列都会以 “$”或第2套保护设备动作结束;对于以第2套保护设备动作结束的时间序列,可通过展开第2套保护设备的保护配置通用模型,以获得完整的警报假说时间序列,从而构成警报假说时间序列集。
步骤3:对于警报假说时间序列集中的每一个警报假说时间序列,通过子时间序列匹配方式计算与调度中心收到的警报信息时间序列之间的距离。
步骤4:把时间序列距离转换成元件动作置信度,得到可疑故障元件的故障置信度,从而得到故障元件。
步骤5:故障过程分析。对故障发展过程进行解释,并对继电保护和断路器的动作状况、警报信息的准确性进行评估。
3.2 计及警报漏报的故障诊断修正策略
考虑到在实际电力系统中因为通信通道和设备本身的原因无法完全避免干扰而产生错误信息,故障诊断算法必须对收到的警报信息进行预处理,以改善容错性。对于存在警报漏报的情形,这里给出一种修正策略,以改善故障诊断的准确性。
若警报假说时间序列X的势为n(n≥3),且其与警报信息时间序列Y的编辑距离为d(0<d≤n/ 3),则警报假说 时间序列 中必有元 素xi= (vi= (Axi,Δtxi,Sxi),txi)在警报信息时间序列Y中未有对应警报信息,即xi|Y。此时,可假设由于某种原因发生了元素yi=(vyi=(Axi,Δtxi,Sxi),txi)的漏报,并在警报信息时间序列Y中插入虚拟事件构造新的警报信息时间序列Y′,之后对包含事件Axi的警报假说时间序列利用式(9)至式(13)重新计算元件动作的置信度。在计算过程中,虚拟事件yi的置信度利用式(14)修正:
式(14)中,n越大,漏报的警报数目越小即d越小,则虚拟事件yi=(vyi=(Axi,Δtxi,Sxi),txi)的置信度就越高。
4 算例分析
采用广州电力系统和浙江电力系统发生过的实际案例来说明所提出的方法的可行性与有效性。
4.1 广州电力系统故障案例
附录A中给出了广州电力系统的局部接线图、 案例的故障过程、故障后所收到的警报信息,以及针对该实际电力系统利用时间序列相似性匹配进行故障诊断的步骤和运算过程。
故障诊断结果与实际发生的故障情况相符。时间序列的匹配结果表明,所配置的警报假说时间序列与实际警报信息时间序列之间的编辑距离和时间距离均为0,这说明故障元件为线路L2943且断路器C12拒动,继电保护均正确动作,警报时标信息准确,警报信息完整。
4.2 浙江电力系统故障案例
附录B中给出了浙江电力系统的局部接线图、 案例的故障过程、故障后所收到的警报信息,以及针对该实际电力系统利用时间序列相似性匹配进行故障诊断的步骤和运算过程。该故障案例为多重并发故障,且存在故障后保护加速三相跳闸(加速三跳) 等复杂情况。
故障诊断结果与实际发生的故障情况相符,并准确给出了4335线、4336线、塘岭变C6断路器、塘岭变副母线等多个故障元件的故障时刻。从这个故障案例的诊断结果可以看出,所提出的故障诊断方法能够处理并发故障、加速三跳等复杂故障情况,对时标不准确、漏报/误报等信息具有良好的识别和容错能力。
4.3 与 近 年 来 提 出 的 两 种 故 障 诊 断 方 法 的 比 较分析
本文对文献[10]中的多个故障场景进行了测试,均能准确诊断故障。与近年提出的两种利用时序信息的电力系统故障诊断方法的对比分析如表1所示。表中:o(·)表示时间复杂度(计算量);k为矩阵阶数,即库所数;l为警报信 息时间序 列的长度;N为可疑故障元件数。
从表1可以看出,本文所提出的方法通过引入时间序列的数据挖掘概念与相关方法,充分利用了警报信息的时序与关联特性,提高了故障诊断的准确度和容错性,在复杂故障、并发故障情况下仍能迅速识别警报漏报/误报等情况。与国内外近阶段的相关研究成果比较,本文所提出的方法充分利用了时标偏差与信息准确程度的关联性,时间复杂度低, 运算速度快,满足在线诊断要求。
5 结语
为充分利用电力系统发生故障后的警报信号的时序特性,以提高故障诊断的效率和准确性,本文将时间序列的数据挖掘概念及相关技术引入电力系统故障诊断之中,提出了基于时间序列相似性匹配的故障诊断方法。与近年来提出的两种输电系统故障诊断方法相比,这种方法充分利用了警报信息时标偏差与信息准确程度的关联性,在复杂故障、并发故障情况下仍能识别警报漏报/误报等情况,准确诊断故障元件和故障类型,并对保护装置的动作行为进行评价,时间复杂度低,运算速度快,满足在线诊断要求。最后,采用两个实际电力系统中发生过的故障案例说明了所提出的故障诊断方法的可行性与有效性。
附录见本 刊网络版 (http://www.aeps-info. com/aeps/ch/index.aspx)。
摘要：输电系统发生故障后的警报信号具有丰富的时序信息,若能充分利用则会有助于快速和准确地诊断故障。调度中心采集到的故障警报包含了统一时标基准的时序信息,从而构成了时间序列。在此背景下,将时间序列的数据挖掘概念与相关方法引入输电系统故障诊断之中,提出了基于相似性匹配的故障诊断方法。首先,介绍了时间序列的概念及其相似性匹配方法。随后,将这种方法进行了改进并应用于输电系统故障诊断,构造了相应的时间序列模型,定义了时间序列距离,采用子序列匹配查询方法求解,并与近年来提出的两种输电系统故障诊断方法进行了比较分析。所提出的方法利用警报信息序列的时序特征,对于复杂故障、相继故障等情形仍能迅速识别警报漏报/误报等情况,正确诊断出故障元件与故障类型,并对继电保护装置进行评价。最后,用两个实际案例说明了所提出的故障诊断方法的可行性与有效性。
关键词：电力系统,故障诊断,时间序列,数据挖掘,相似性匹配
相似性匹配 篇2
本文通过GNP类关联规则挖掘方法构建外汇交易模型,通过外汇价格上升下降序列,提取显著的交易规则,并提出全新的GNP-SMT交易策略,基于GNP算法做序列的相似度匹配交易,进行外汇交易。
一、GNP-SMT方法
设Y(t)为在时间t的价格状态,它的值用1或0来表示向上或向下,其计算如下:
属性及其值对应于GNP方法中的判断节点功能。节点的连接被表示为关联规则。 图1显示了GNP类关联规则挖掘节点连接的示例。 其中,P1为一个处理节点,是关联规则的出发点。“Y(t)=1”,“Y(t-1)= 0”和“Y(t-2)=1”表示判断节点的功能。
GNP通过使用的判断节点检查数据库元组的属性值,并通过处理节点计算关联规则的测量。 判断节点通过判断的结果Yes或者No来决定下一个节点,对应着Yes边和No边。 此外,每个判断节点同时也检查t+1步中“Y(t+1)=C,C=1或者2”是否满足。
每个处理节点具有固有数字顺序(P1, P2...Pn),并且都连接到一个判断节点。 开始节点连接到P1。 属性值的检查从每个处理节点开始。 No-侧的判断节点连接到下一个编号的处理节点。 如果Y值从起点Ps检查结束,那么GNP也同样检查数据的下一个步。因此,数据库中的所有数据都进行检查。
CNP-based类关联规则挖掘的过程与一般的类关联规则挖掘方法的不同点在于:每个处理节点的N在每次访问都有更新(初始值N=0);它使用向后传输方法, 其中处理节点每次访问时步骤t更新到当前步骤n(最初n=n0);使用a, b, c, a(U), b(D)和c(D)计算规则的support, confidence和χ2值与以往的方法不同;这个方法会一直持续到得到足够大的n为止。 其中,在n步时刻,GNP向回追溯5步来发现规则,同时移动到下一步n+1,在向回追溯3步,如此一直持续下去……。每一步中向前追溯多长步骤是根据GNP节点的实际判断结果给出的。
当检测结束时,得到规则度量值。 在每个处理节点处,GNP都计算从所有Yes边到处理节点的样例个数,通过其作为测量关联规则的起始点。 N1表示从P1出发的总的记录数, 同时a, b, c分别表示每个判断节点通过Yes-边的记录数,并且a(U), a(D), b(U),b (D), c (U), c (D) 代表a, b, c中下一步为Up和Down的记录数。
利用这些得到的值, 就可以计算重要规则的度量,如使用b(U)/N1计算规则的支撑(support),使用b(D)/N1 计算规则的支撑(support), 使用b (U)/b计算规则的置信度(confidence),使用b(D)/b计算规则的置信度(confidence)。 同时,相应地χ2值也可以通过公式计算得出。
本文定义重要的关联规则满足如下条件:
其中,χ2min和min sup分别表示本文定义的最小χ2值和支撑(support)的阈值。 同时当规则序列为(Y=C),C=0,1时, 使用第三个表达式判断置信度(confidence)值。
所有满足重要性条件的关联规则都存贮在UP池和DOWN池中。 当GNP产生一个重要规则时,其总是要检查该规则是否是新的。GNP个体中的判断节点和处理节点的数目都为初始设定值, 并且每一代中所有的个体都有相同的节点数目, 节点之间的连接也是在初始化GNP个体的时候随机产生的。 GNP的个体并不需要包括所有的判断节点函数, 同时每个函数的数目也是不确定的,GNP个体中可以包含几个相同函数。
关于适应度和遗传算子, 本文使用Shimada等［4］所提出的判断GNP个体适应度的公式,即:
χ2(i),n(i)和αnew(i)分别相应地代表规则i的重要性水平(importance),复杂程度(complexity)和新颖性(novelty)。 考虑该适应度值来提取新的规则的潜在性。本文使用三种不同类型的进化算子:交叉、变异-I(改变节点的连接)、变异-II(改变判断节点的函数)。 每一代中,根据个体适应度值的大小对个体进行排序,将其中前1/3的个体选择出来。 然后,在下一代通过三种类型的进化算子产生3倍的个体组成新的一代。 如果交叉或变异的概率取很小的值, 那池中就会重复产生很多同样的规则,GNP就会过早收敛而达不到效果。所以参数值的设定通过实验决定。
GNP个体进化以提取新的满足条件的规则到池中,而不是像一般GNP算法中得到最高适应度值的个体。 因此,该方法在其进化方式上是与其他进化算法有本质上的区别。
二、投资模型
基于GNP的类别关联规则的数据挖掘与传统的方法有一点不同, 规则的获取是通过价格序列上升和下降得到的。 而投资量的大小则是通过预测以向上和向下的价格确定的概率来决定的。 如表1所示,在第0步设置投资X(0)的初始确认金额。 当它移动到下一个步1,价格下跌,失去了投资X(0),并返回步骤1时的收益R(1)=-X(0)。 然后决定在步骤1投资多少是根据GMP-SMT预测的概率来决定。 这个过程一直持续,在步骤9返回积累的收益R(9)=-X(0)+ X(1)+X(7)+…-X(8)。 而目标是最大化的回报R(N),同时,以降低投资风险。
表1中,U(t) :表示在t步价格上升;D(t) :表示在t步价格下降;x(t) :表示在t步的投资额;R(t) :表示在t步的收益额。
本模型主要解决在给定U (t) 或者D (t),t=0,1,2,3, …,s的条件下, 如何决定在s+1步投资额x(s+1),从而使得最后的收益额R最大化。
(一)价格上升下降概率计算
1.通过GNP-based类关联规则挖掘方法,计算在第s+1步价格上升或下降的概率。
2.依据历史价格上升下降数据, 通过与Up规则和Down规则的匹配来计算数据s的平均匹配度。
3.计算在s+1步价格上升或下降的概率:。
(二)策略计算
根据上式计算的s+1步价格上升的概率Pr(Up, s+1),本节采用两种方法来计算s+1步的策略x(s+1)值。
第一种方法(见图2情形1),其中x(s+1)为Pr(Up,s+1)的单调递增函数;另一种方法(见图2情形2),是通过决定一个正的α值,得到在s+1步平均收益R(s+1),从而来使用Pr(Up, s+1)计算x(s+1)。
三、实证分析
对全样本数据按2500手截取,数据呈现中间大,两端小的正态分布特征。 使用GNP-SMT方法的预测成功率在51.66%±0.32%左右, 其中51.66%为预测的均值,0.32%为预测的标准差。
从训练样本抽取2000个样本数据,GNP-SMT使用策略1累积收益达到70%左右。同时,从测试样本抽取550个样本数据,GNP-SMT使用策略1累积收益虽然在中间有所下降,但最后也达到60%左右。
考虑策略2, 从训练样本抽取2000个样本数据,GNP-SMT使用策略2累积收益表现不够平稳,其中在某个阶段收益率都为负值, 但最后累积的收益率也逐步上升,达到15%左右。从测试样本抽取550个样本数据,GNP-SMT使用策略2累积收益率的表现相当不错,最后可以达到90%左右的累积收益率。
整体最优策略的实证结果如下,全样本来看,年化收益率可以达到116%。 实证表明了GNP-SMT方法的有效性以及获利能力。 但需要注意的是,现实的金融环境错综复杂, 这种历史与现在关系的反映并不是时时刻刻都有效的,只有通过不断的创新发现,才能获取新的收益。
四、结语
GNP-SMT方法利用了技术分析中,“历史是会重复发生”这一假设条件,通过使用GNP得到历史数据里的规则,然后使用SMT技术匹配交易数据和历史数据。 实证也表明了这一方法的有效性以及获利能力。这在一定程度上也说明了市场不是完全有效的,历史的信息对现在的交易存在影响, 通过技术分析手段能够获得超额收益,这也验证了AMH的相关理论。
GNP-SMT为外汇交易提供了新的思路, 它通过预测汇率上升下降的概率进行投资决策, 通过本文的实证表明,GNP的相关算法在外汇市场上可以获得显著的收益率水平, 并且在不同的市场环境下都能够表现出很好的性质。
摘要：提出了一种基于外汇市场的价格上升下降序列的新的GNP-SMT方法 。基于遗传网络编程(GNP)与类关联规则,通过算法迭代,抽取大量的类关联规则,并存储在规则库中(上升池和下降池)。然后,将产生的规则进入池中来计算价格向上和向下价的概率。在训练期间,提取大量的向上和向下的规则后,使用相似度的匹配计算,以处理各个步骤的执行情况。在测试期间,连续交易的投资金额由GNP的SMT的预测概率计算确定。使用两种不同的情况下呈现的结果,模型都显示很好的盈利。
相似性匹配 篇3
关键词：模糊匹配,重复记录,数据分组,数据集
0引言
多数据源集成中, 集成数据的质量越来越引起重视, 多源数据集成所造成的信息重复是影响数据质量的关键因素之一。这些重复数据包括那些客观上表示现实世界同一实体, 但由于某些记录在格式拼写或人为组织上的差异而导致DBMS不能正确识别。例如把记录属性值“computer”误写成“compute” (漏写) 或“computeration” (插入) 、“湖南工业大学”写成“湖南工大” (缩写) ;把出生日期“1986-10-21”拼写成“10/21/1986”或“1986/10/21” (格式差异) 等, 以致计算机误认为是不同的记录。因此, 如何高效准确识别这些重复记录已成为数据集成和数据挖掘领域中的一个研究热点[1,2,3,4,5], 目前国内外文献资料中提出了很多有效的解决方案, 如文献[1]采用距离函数模型进行重复记录的检测;文献[2]提出了一种高效精确匹配识别记录的排序&合并算法;文献[3]设计了一种基于等级分组的重复记录检测方法;文献[4]探讨了一种基于聚类汇总的记录匹配算法;而文献[5]则研究了一种高效的基于N-Gram检测相似重复记录的方法。总的说来, 这些方法在重复记录的识别和检测中都取得了一定的成绩, 且各具特色, 如有的查全率和查准率高、有的时间空间复杂度小, 实现起来简单等, 但综合以上多个技术指标, 这些方法还有待改进。
本文提出了一种基于用户兴趣度分组的模糊匹配方法, 用来精确快速识别集成数据中相似重复记录, 其主要特征为: (1) 根据各操作用户对记录属性的评分计算各属性的兴趣度, 并根据兴趣度对记录分组, 目的是减少记录匹配比较次数, 提高识别的时间效率; (2) 组内记录采用一种布尔模型的算法进行匹配, 该算法实现简单, 有较高的查准率, 从而提高记录的识别精度。
1数据分组
1.1分组的基本思想
记录属性描述了实体的特征, 但各属性在描述实体特征时其重要性是不同的, 如关键属性能惟一确定一实体, 而非关键属性只能在某方面对实体进行描述。同样, 在比较两实体相似性时, 也总是优先考虑其关键属性的值, 然后再比较非关键属性值。数据分组的基本思想为[6]:首先各操作用户按其兴趣度对各实体属性进行评分, 该兴趣度反映了用户对该属性在实体中重要性的认同;然后计算所有用户对各属性的相对兴趣度, 并取最大相对兴趣度的属性对记录进行分组, 分组后的记录数如果太多, 可以再在组内选择第二个较大相对兴趣度的属性进一步分组, 如此循环, 直到组内的记录数达到一定的值为止。另外, 在分组过程中, 为避免在记录匹配比较时因分组原因出现遗漏, 如将“湖南工业大学”和“湖南工大”两记录不能分在同一组中, 可另选一兴趣度较大的属性重复以上分组过程, 如此循环直到分组合理或主要属性都“用完”为止。
采用以上分组方法, 可以达到两个目的: (1) 由于记录匹配计算只在组内进行, 可以有效地减少记录匹配比较的次数, 提高重复记录识别的时间、空间效率; (2) 采用多属性分组方法, 避免漏查, 提高了查全率。
1.2分组实现过程
1.2.1 相关定义
设操作数据的用户集合U={u1, u2, ..., um}, 数据记录集合R={r1, r2, ..., rn}, 属性集合F={F1, F2, ..., Fk}, 属性的兴趣度集合W={w1, w2, ..., wk}, 其中wj为属性Fj的相对兴趣度。用户ui (0<i≤m) 对属性Fj的兴趣度评分记为:Tij, 则m个用户对属性Fj的总评分为:
由式 (1) 可得属性Fj的相对兴趣度为:
上述计算结果如表1所示。
考虑到wj的值应在一个适度的百分比范围内, 故用户对每个属性的评分值规定为0≤Ti j≤k, 另外, 如果Tj=0, 则说明与之对应的属性Fj在记录中没有多大意义, 其存在与否对记录的重复识别不产生影响, 这也是符合情理的。
1.2.2 实现算法描述
(1) 根据公式 (1) 、 (2) 计算各属性兴趣度wj的值, 实现如下:
(2) 取wj值最大的属性, 根据记录中该属性值将数据集R划分成t个子集合R1, R2, …, Rt, 且R1∩R2∩…∩Rt=Ø。
(3) 设定一判定记录集合大小的临界值α, 如果|Ri|>α (|Ri|表示Ri子集中记录数目, i<t) , 则取余下属性中w值最大的属性, 在Ri中重复步骤 (2) , 以分解Ri为更小的数据子集, 如此循环, 直到上述条件不满足为止。
(4) 为避免由于记录中某个属性值的漏写、缩写、错写、插入、交换等造成相似重复记录不能分在同一组的问题, 引入多次分组技术, 即在上次分组完成后, 选择余下的w值最大的属性, 重复步骤 (2) 和 (3) , 重新把数据集R划分成相应的子集, 当然是否重新划分需根据实际情况确定。
2组内相似重复记录的识别
记录分组后, 接下来就要对组内重复记录进行识别, 本文提出了一种基于布尔模型的模糊匹配识别方法来解决该问题[7,8]。
2.1布尔模型识别方法定义
用ki表示xik (xi记录中第k个属性值) 中第i个关键词, K={K1, K2, …, Kt}表示xik中关键词的集合, t表示系统中关键词的数量, Sij (ki, xjk) 表示xik中第i个关键词ki与xjk的模糊匹配度, 用q表示查询, 其由关键词及其组合构成。若sij>0, 则ki与xjk匹配;若sij=0, 则ki与xjk不匹配。设某属性中所有关键词集合组成的向量为
上述是一般的匹配定义, 在布尔模型中, 关键词模糊匹配度变量sij∈{0, 1}, 由于只取2个值, 因此sij=0表示关键词ki与xjk不匹配, sij=1表示关键词ki与xjk匹配;另外, 模糊匹配中, 查询是常规的布尔表达式, 即用NOT、AND、OR将关键词连接起来, 令
查询q与属性值xjk精确匹配度定义为:
查询q与属性值xjk模糊匹配度定义为:
公式 (3) 、 (4) 中, q为记录xi中属性值xik中关键词所组成连接表达式, sij (q, xjk) 表示记录xi和xj的第k个属性的匹配度, 记录的匹配度定义为该记录中所有属性值的相似匹配度加权和, 即:
式 (5) 中wt为前面所定义的属性兴趣度, 考虑到多数据源集成中数据的组成特点, 本文采用公式 (4) 所示的模糊匹配方法, 以期识别范围更大, 查全率更高。
2.2布尔方法识别记录的过程及特点
用布尔方法来识别相似重复记录时, 第一步, 首先取组内一条记录, 并将该记录的有关属性值分割成多个关键词, 将这些关键词连接成表达式q;第二步, 在组内取其它某记录的相应属性值, 用公式 (4) 计算该属性的相似匹配度;第三步, 取以上两记录的其它属性, 重复第一步, 直到属性的相对兴趣度为0止;第四步, 利用公式 (5) 计算以上两记录的相似度匹配;第五步, 设定一记录相似判断因子τ, 其值可根据情况设定, 如取τ值为80%, 如果两记录匹配度大于或等于τ, 则为重复记录, 可删除, 否则, 非重复记录;第六步, 重复第二到第五步, 直到组内所有记录比较完为止。
布尔模型的优点主要有理论简单、容易实现、速度较快和使用方便等。正是由于它这些优点, 使得它在早期的以关键词匹配为主的字符串搜索引擎中广泛使用, 现在仍然广泛应用在数字图书馆等目录式匹配检索系统中。在本文的记录模糊匹配过程中, 用布尔方法实现属性值中关键词的匹配过程简单, 且存在较高的匹配精度和效率, 具体表现将在下面的实验中进行说明。
当然, 布尔模型的缺点也是显而易见的:第一, 同一查询中各个关键词的同等重要性, 不能反映不同关键词对同一个属性值的不同重要性;第二, 属性值与查询匹配度只有匹配 (值为1) 与不匹配 (值为0) 两种, 结果单一化, 因此如果属性值中关键词提取不全, 将会影响记录的相似匹配度。
3实验验证
文献[4]中提出了一种基于聚类汇总的记录匹配算法, 该算法是近几年来研究相似重复记录识别的典型算法之一, 其在记录匹配过程中认为各属性同等重要, 没有考虑属性的加权, 但考虑了新记录加入到类的时候, 聚类汇总会动态增量更新, 因而此算法是合理的。本文以该算法为参照物, 通过实验来比较两种方法在识别重复记录时, 其查准率和查询时间上的差别。
实验数据来源于某大型人才招聘网站上所采集的人才信息数据, 共有40.1万条记录, 每条记录包含16个字段属性, 其样本数据如表2所示。
为了研究方便, 分别从中随机抽取5.1万、11.3万、28.6万、37万条记录进行相似识别比较实验, 并且通过其它方法已检测出其中分别有0.1万、0.26万、0.45万、0.61万条客观重复记录;同时, 实验中记录属性的选择和处理是关键, 它是后续数据分组识别的基础。为此, 首先对样本记录16个字段属性, 根据115位网上用户的评分以及1.2.2节提供的算法得到各属性的兴趣度, 然后按兴趣度的大小对所有属性进行排序, 在实验中只选择了兴趣度较大的前10个属性, 而将后6个属性抛弃, 因这些属性的存在与否对记录的相似识别影响不大, 如“电话号码”属性, 其值的不同不能说明是两个不同的记录。下面将通过实验来验证本文方法的有效性。实验环境为CPU P4 3.1Ghz、内存1G、硬盘160GB、操作系统Windows XP、数据库DBMS为SQL Server 2000、程序用VC++编写。另外, 实验中的查准率用正确识别出来的重复记录占以上客观重复记录的百分比表示, 由于查全率是由机器和人工因素共同决定的 (分组次数的多少由人工根据需要确定) , 因此, 不作为实验验证考虑因素。
根据以上方案, 其实验结果如下图1、图2所示, 其中聚类汇总的记录匹配算法简称聚类汇总, 本文的模糊匹配方法简称模糊匹配。
从图1中可以看出, 模糊匹配方法的查准率会随着记录数的增加而下降, 而聚类汇总方法的查准率几乎没有改变。另外, 在记录总数量少的情况下, 模糊匹配的查准率更高些, 这是因为模糊匹配在记录匹配中要更多地考虑人的因素 (用户评分) , 数据量越大, 参与评分的人数越多, 其主观因素就越大, 而聚类汇总方法则在新加记录上总是动态更新聚类, 因而查准率稳定。
从图2可以看出两种方法在4个不同记录数下的运行时间, 随着数据量的增加, 聚类汇总方法需要的时间更多, 这是因为在聚类汇总过程中, 每次动态增量更新聚类后, 聚类中的所有记录都要进行匹配运算, 因而随着记录的增加, 其运行的时间更长些。
4结论
本文提出了一种按用户兴趣度分组的模糊匹配方法来识别多数据源集成中的重复记录, 该方法有可靠的理论依据, 算法实现简单、可操作性好。在实践中证明, 该方法在检测的时空效率和精度上有其优点, 尤其是在超大型数据集 (记录数量在100万条以上) 中重复记录识别上有很高的时间效率, 因此, 方法的提出有一定的实际应用价值。
参考文献
[1]Bilenko M, Mooney R.Adaptive name matching in information integra-tion[J].IEEE Intelligent System, 2003, 18 (5) :16-23.
[2]Monge A.An adaptive and efficient algorithm for detecting approxi-mately duplicate database records[EB/OL].2007-09-02.http://citeseer.ist.psu.edu/mongeov adaptive.html.
[3]李星毅, 包从剑, 施化吉.数据仓库中的相似重复记录检测方法[J].电子科技大学学报, 2007, 36 (6) :1273-1277
[4]王天江, 刘芳, 卢正鼎.基于聚类汇总的记录匹配算法[J].计算机工程与科学, 2004, 26 (9) :62-63, 101.
[5]邱越峰, 田增平, 季文, 等.一种高效的检测相似重复记录的方法[J].计算机学报, 2001, 24 (1) :69-77.
[6]张永, 迟忠先.位置编码在数据仓库ETL中的应用[J].计算机工程, 2007, 33 (1) :50-52.
[7]王亮.搜索引擎及其相关性排序研究[D].武汉:武汉大学, 2004.
相似性匹配 篇4
XML作为一种网络中常用的数据表示和交换标准,蕴含了丰富的信息。不同信息源的XML数据虽然可能表示相似或者相同的信息。然而,却可能具有不同的数据结构和内容。同时,即使两个XML文档有着相同的信息,一个XML文档也可能包含另一个XML文档所不包含的信息。集成这样相似或者相同的数据是有意义的,因为用户能够从集成的数据中获得更为完整和有用的信息。
图1为两棵基于不同DTD(Document Type Descriptor)的文档树。图中的两个XML文档树虽然在结构上不一样,但是却表示了相同的信息。同时,这两棵树还互相包含了另外一棵树所没有的信息,如图1(a)中的volumn和number与图1(b)中的initpage和endpage。
LAX[1]是一种有效的XML连接算法。其中XML文档树被分成多个能表示独立信息的子树,该算法通过计算子树叶、子节点的相似性来计算整个XML文档树的相似度。然而,LAX算法是通过计算子树的叶子节点的PCDATA值的相似性来计算整个XML文档树的相似性,这就使得算法计算过程中没有考虑语义信息。同时,在LAX算法执行过程中较为容易出现一个子树和多个子树匹配的现象,故匹配结果不是很精确。
本文基于子树匹配并根据路径信息的匹配提出了一个算法。其基本原理是在计算子树相似性的过程中,不仅考虑子树叶、子节点的PCDATA的值,还考虑了所匹配的叶子节点所在路径的相似性。该路径是从子树的根节点到叶子节点的完全路径。因为算法有效地考虑了叶子节点的语义信息并减少了一个子树和多个子树匹配的现象,故增加了计算的精确性和有效性。
1 相关工作与预备知识
1.1 相关工作
目前,树编辑距离是一种比较常见的,有效的度量XML文档结构相似性的计算方法[2]。首先将一个XML文档看作有序标记树,定义了一种对树进行操作的编辑距离[3,4,5],然后利用该编辑距离来计算两棵树之间的相似度。其基本思想是把两棵树之间的距离定义为利用编辑操作将一棵树转变到另一棵树所需的最小代价,这些编辑操作包括节点的更新、插入和删除。操作越少,树之间的距离越小,则文档之间的相似度越大。然而,树编辑距离的计算复杂度是很高的,在最坏情况下,计算复杂度为O(n4)。
为了尽最大可能地避免树编辑距离操作的高复杂度,文献[2]中提出了一种利用上下边界值来过滤或减少不必要的树编辑操作的方法。然而,该方法也有其缺陷。当上边界值大于阈值г或者下边界值小于阈值г时,树的编辑操作依然不可避免。
文献[1]中提出了一种基于子树匹配的XML的合并方法LAX。在最坏情况下,LAX的计算复杂度为O(n2)。LAX算法能够高效地计算XML文档的相似性并有效地合并来自于不同信息源的相似的XML文档。
本文在子树匹配的过程中考虑了路径的相似性[6,7],提出了一个算法。该算法在一定程度上考虑了语义的信息并有效减少了一个子树和多个子树匹配的情况,故其计算结果更为有效和正确。
1.2 预备知识
在LAX算法中,XML文档树被分成多个能够代表独立信息的子树。XML文档树的相似性是所有匹配的子树的相似性的平均值。LAX算法的核心思想是:通过计算关键路径的节点权重值找到簇点,从而将两棵XML文档树各自分成若干个子树。以一棵XML文档树为基树,另一棵文档树为目标树,匹配两棵文档树的所有子树。每一轮匹配中找到具有最大相似性的两棵子树,最后通过计算所有匹配子树的相似性的平均值得到XML文档的相似性值。
LAX算法中子树相似性的描述如下。令T1和T2为两棵XML文档树,其中T1为基树,T2为目标树。假设T1和T2被各自分成k1个子树t1i(1≤i≤k1)和k2个子树t2j(1≤j≤k2),子树t1i和t2j的相似性Ssub(t1i,t2j)由两棵子树匹配的叶子节点数占基数的叶子节点数的百分比决定,计算方法如下:
式(1)中,n表示两棵子树的匹配的叶子节点数,n1i表示基树的叶子节点数。
TM[i]表示一轮匹配中具有最大相似性的匹配子树,SM[i]表示这轮匹配中子树的相似性,计算方法如下:
在第i轮匹配中,给定阈值г,如果匹配子树TM[i]的相似性值SM[i]≥г,则称匹配子树为关键匹配子树。LAX算法通过关键匹配子树来合并XML文档。
XML文档树T1和T2的相似性ST(T1,T2)是所有匹配的子树的相似性的平均值,计算方法如下:
LAX算法能够有效地计算XML文档的相似性,但是LAX算法仅仅通过计算子树的叶子节点的PCDATA值的相似性,使得算法计算过程中没有考虑语义信息并在LAX算法执行过程中会较为容易出现一个子树和多个子树匹配的现象,故造成匹配结果不精确。
2 算法实现
匹配子树的示例如图2所示。在图2中,t11是图1中DBLP的子树,t21和t22是SIGMOD的子树。可以看出,子树t11和t21有两个相同的叶子节点值XML和John,而子树t11和t22也有两个相同的叶子节点值John和1。在LAX算法中,t11对t21和t22有相同的相似性。然而,可以进一步地观察到,在相同的叶子节点值中,(article,title,XML),(article,author,John)与(article,title,XML),(article,author,John)的匹配比(article,author,John),(article,volumn,1)与(article,author,John),(article,initpage,1)的匹配更有说服力,因为volumn与initpage的相似程度并不高。
本文将路径看成标签的集合,路径的相似性由集合相同元素的个数占集合元素个数的百分比决定。然而,路径上的各个节点对于路径的相似性的贡献是不一样的。在XML文档中,越是靠近顶层的节点信息对文档的作用越大,因而本文赋予这些节点更大的权值。
定义1:路径。设p=(n0,…,nn)为具有n个节点的路径,其中,节点ni的层次为i。路径p的每个节点被附加一个权重值,于是附加权重值的路径可表示为pw=(n0,w0;…;nn,wn),其中wi=eβi,β≤0。
定义2:路径相似性。设pw1和pw2为两条带有权重的路径,pw1与pw2的相似性Sp(pw1,pw2)定义为:
其中,wn(pw)=∑t∈pwwpw(t),wpw(t)为pw路径中节点t的权重值,
例1在图1中,考虑路径p1=(DBLP,article,volumn)与p2=(SIGMOD,article,initpage)。假设β=-0.1,这样,可以得到附加权值的路径pw1=(DBLP,1;article,0.904;volumn,0.818)和pw2=(SIGMOD,1;article,0.904;initpage,0.818)。pw1和pw2有相同的元素article,则Sp(pw1,pw2)=0.904/(2.723+2.723-0.904)=0.199。
定义3:XML子树相似性。给定一对匹配的子树t1,t2,设匹配子树的叶子节点个数为N,第i个匹配的叶子节点对应的子树t1和t2的路径为pw1i,pw2i,则子树t1,t2的相似性S(t1,t2)为:
例2在图2中,子树t11和子树t21有两个相同的叶子节点值XML和John,故Ssub(t11,t21)=2/4=50%。匹配的叶子节点XML对应着子树t11中的路径(article,1;title,0.904;XML,0.818)和子树t21的路径(article,1;title,0.904;XML,0.818),John对应着子树t11中的路径(article,1;title,0.904;John,0.818)和子树t21的路径(article,1;title,0.904;John,0.818)。由公式(5)可以得到S(t11,t21)=((1+1)/2)觹50%=0.5。同理,Ssub(t11,t22)=2/4=50%。匹配的叶子节点John对应着子树t11中的路径(article,1;title,0.904;John,0.818)和子树t22的路径(article,1;title,0.904;John,0.818),1对应着子树t11的路径(article,1;volumn,0.904;1,0.818)和子树t22的路径(article,1;initpage,0.904;1,0.818),由公式(5)可以得到S(t11,t22)=((1+0.5)/2)觹50%=0.325。
在例2中,S(t11,t21)>S(t11,t22)。然而,LAX算法得到t11和t21与t11和t22的相似性是相同的,故在加入了路径的相似性之后,可得到t11对t21比t22的相似性要高,于是有效地减少了一个子树与多个子树匹配的现象。具体计算XML文档相似的算法PLAX如下:
算法1 PLAX
输入:XML文档
输出:XML相似性
第一步:XML文档处理。将XML文档解析成XML文档树。
第二步:指定一棵XML文档树为基树,一棵XML文档树为目标树,通过计算XML各个节点的权重值,将XML文档树分成若干个子树。
第三步:遍历基树的所有子树t1 i和目标树的所有子树t2 j,计算子树t1 i和t2 j的相似性S(t1 i,t2 j)。
记录当前t1 i与子树t2 j的最大值和子树序号,更新最大值。
第四步:求取所有匹配子树的相似值的平均值,即为XML文档的相似值。
3 实验分析
3.1 实验配置
实验环境:CPU主频是2.10GHz;主存容量是2.00GB;操作系统是Microsoft Windows XP Professional;编程语言采用java;开发环境为eclipse。
数据集:实验采用来自于http://www.cs.washington.edu/research/xmldatasets的XML数据。
在实验中,本文引入一个参数,称之为匹配精确度,可用来度量PLAX算法和LAX算法正确选择匹配子树的百分比,计算方法如下:
其中,ncs表示正确选择匹配子树的个数,n表示XML文档树全部子树的个数。
3.2 实验结果分析
3.2.1 叶子节点数和子树个数对算法效率的影响
由图3和图4可以看出,随着叶子节点数和子树个数的增多,算法的运行时间在变长,但时间变化的幅度并不是很大。本文的实验数据大小都在400KB左右,故算法的运行时间都不超过2秒。
3.2.2 PLAX与LAX算法的对比实验
由于PLAX加入了路径信息的比较,故其有效地减少了一个子树与多个子树比较的现象。文中采用6对XML文档进行对比实验,其中,实验数据大小在400KB左右。在图5的6对XML文档的比较中,可以发现,PLAX都比较明显地减少了一个子树与多个子树比较的现象。
由于PLAX有效减少了一个子树与多个子树比较的现象,在图6中可以看出,PLAX正确选择匹配子树的数目明显增加,即匹配精确度增加。
4 结束语
在XML相似度计算中,现有方法在子树匹配过程中只考虑了叶子节点的信息却未考虑更多的语义信息,故出现了一个子树与多个子树匹配的现象。此外,在上述多个匹配的子树中,并不是所有的子树都是真正地匹配。因此,本文在子树匹配过程中考虑加入路径信息并给路径的每个标签赋予一定的权值,提出了一个算法。实验结果也表明该算法有效地增加了XML文档的匹配精确度。
参考文献
[1]APOSTOLICO A,GALIL Z.Pattern matching algorithms[M].O-xford University Press,1992.
[2]GUHA S,JAGADISH H V,KOUDAS N,et al.Approximate X-ML joins[C]//Proc.of ACM SIGMOD,2002:287-298.
[3]NIERMAN A,JAGADISH H V.Evaluating structural similarityin XML documents[C]//Proc.of WebDB,2002:61-66.
[4]ZHANG K,SHASHA D.Simple fast algorithm for the editingdistance between trees and related problems[J].SIAM Journal ofComputing,1989,18(6):1245-1262.
[5]LIANG W,YOKOTA H.LAX:an efficient approximate XML j-oin based on clustered leaf nodes for XML[C]//Proc.of BN-COD 2005,LNCS 3567,Springer,2005:82-97.
[6]刘晨,王秀坤,邹莎莎.一种基于频率及路径的XML聚类算法.中国科技论文在线.
相似性匹配 篇5
语义Web服务是近年来Web服务领域热门的研究方向之一。通过向Web服务中添加语义信息,来实现分布服务组件的自动发现和组合,以满足动态的、可扩充的、经济的企业应用集成(EAI)和电子商务的需要,是语义Web服务的目标。在语义Web服务发现方面,本体概念的引入提升了服务的语义表达能力和发现能力,改变了传统Web服务发现基于关键字查询的语义描述不清,查全、查准率低等缺陷。
目前比较公认的本体定义是Rudi Stuger于1998年提出的:“本体是共享概念模型的明确的、形式化的规范描述[1]”。通俗地讲,本体是为了让计算机对现实世界某一领域中的概念及概念之间的关系有明确、一致的理解而进行的形式化、规范化的描述。本体的优点在于它能指导人们对某一领域的知识达到一致的认识和理解,并使用计算机进行描述和逻辑推理,从而达到语义Web的目标。
本文首先介绍了目前语义Web服务匹配的两种主要方法(基于推理和基于相似度计算),分析了各自的优势和不足。并在这两种方法的基础上提出了一种改进的服务匹配策略,即在推理过程中的某些情况下使用相似度计算。该策略在一定程度上综合了两种方法的优点,具有精确的匹配能力和在最坏情况下仍有较好的运行效率。
1 目前的两种语义Web服务匹配方法
1.1 基于推理的服务匹配
基于推理的服务匹配是建立在领域本体概念间的层次关系之上的,使用描述逻辑进行推理匹配的方法。Massimo Paolucci等于2002年首先提出了一种基于DAML-S的服务匹配方法[2],利用DAML-S的Service Profile对服务的输入、输出、前提、效果(IOPE)进行匹配。该方法定义了四种匹配程度(以输出匹配为例,设outR为请求者的一个输出,outA为服务提供者的一个输出):
(1) Exact:当outR与outA相同或outR是outA的直接子类(subClassOf)时,结果为Exact。
(2) Plug-In:如果outA包含outR,也就是说outA可能完全满足outR。
(3) Subsumes:如果outR包含outA,即outA能部分满足outR但不是完全满足。
(4) Fail:在outR和outA间没有任何包含关系,匹配失败。
随后,Lei Li等人对上述四种匹配类型进行了补充,在Subsumes和Fail之间添加了Intersection,即outR与outA的交集是可满足的(outR∩outA≠ ∅,但outR不包含outA),说明outA有可能满足outR的部分功能。从上述介绍我们可以看到,基于推理的服务匹配方法将服务间的匹配程度分为几个等级:ExactPlug-InSubsumesIntersectionFail,但在同一等级内部无法进一步区分结果的匹配度。
1.2 基于相似度计算的服务匹配
基于相似度计算的服务匹配通过计算两个本体概念之间的相似度(一个介于0和1之间的数值)来得到更精确的匹配结果。目前计算概念间相似度的方法主要有基于几何距离、基于属性和基于信息容量等几种。
基于几何距离的相似度算法的基本思想就是用两个概念在本体有向图中的几何距离来衡量语义相关度,距离越短则相关度越高;基于属性的相似度算法[3]是根据比较个概念间相同的和不同的属性的多少来确定二者的相似度的。两个概念间相同的属性越多,不同的属性越少,则他们越相似;基于信息容量的相似度算法[4]的基本思想是两个概念的相似度由他们共同拥有的那部分概念所决定。由于每个概念都是由其祖先概念结点继承而来,继承了祖先结点的信息,因此两概念间的相似度可由他们最近的共同祖先结点所包含的信息容量来确定,共享的信息越多,则相似度越大。
1.3 两种匹配方式的比较
从精度方面:基于推理的匹配方法将服务间的匹配程度分为五个等级,但某些情况下(Plug-In、Subsumes和Intersection)同一级别内部不能进一步区分结果的匹配程度。而基于相似度计算的匹配方法可以清楚地区分这种差别。
从运行效率方面:基于推理的服务匹配的一个好处是可以在匹配之前对本体库进行预处理,为每个概念建立匹配等级列表 (具体方法在第三部分中详细介绍),从而将计算的复杂性转移到预处理阶段。匹配时只需在列表中查找对应的概念,可获得线性的时间复杂度;而基于相似度计算的服务匹配算法本身就比较复杂,加之不能进行类似的预处理,算法的复杂性全部集中在匹配阶段,如基于几何距离的最短路径算法,在最坏情况下(本体规模很大,概念间相似度却很小或根本不匹配)会有糟糕的响应时间。
2 基于推理和相似度计算的服务匹配策略
从上面分析可以看出,两种服务匹配策略各有优势和不足。因此我们考虑将两种发现策略相结合,提出一种基于推理和相似度计算的服务匹配策略,该策略的基本思想是:在大多数服务匹配情况下(精确匹配或不匹配),不需要计算服务的相似度,因此可先采用简单的基于推理的匹配方法得出服务的匹配等级,对于不是Exact和Fail的情况,再采用相似度算法计算服务的相似度。通过对本体库进行预处理,为每个概念维护Exact列表、Subsumes列表和Intersection列表,从而将基于推理方法的计算复杂性转移到预处理阶段,提高匹配阶段的运行效率。下面是算法的具体步骤(步骤中相似度计算的算法采用了文献[4]中提出的一种基于信息容量的相似度算法)。
2.1 预处理阶段――构建匹配等级列表
对于每个新加入领域本体的概念n:
for 每个领域本体中的概念m:
其中ExactList为精确匹配关系列表,SubsumesList为包含关系列表,IntersectionList为交集关系列表。exact(n,m)、subsumes(n,m)、intersection(n,m)分别为判定相应关系的方法。
2.2 概念语义相似度计算semMatch
其中,findInExactList(),findInSubsumesList(),findInInterse-ctionList()为在相应的匹配等级列表中查找相应概念的方法。
2.3 整体匹配算法
整体匹配对两服务中的每对输入、输出进行相似度匹配,返回结果中包含输入的语义相似度(simIn)和输出的语义相似度(simOut),分别为所有输入和输出概念对相似度的平均值。
3 一个服务匹配实例
我们采用“书籍”领域本体作为服务匹配的一个实例。由图1和2.1可知Literature Books的ExactList为(Literature Books,Essay,Novel,Poetry Anthology,Biography),SubsumesList为(River Novel,Nouvelle,Short Story),IntersectionList为NULL。当一个请求查询要求输出为Literature Books,而服务提供者提供的输出为Education Books时,采用上述算法将首先在本体库中Literature Books的匹配等级列表里查找Education Books项,在搜索ExactList、SubsumesList、IntersectionList都没有找到结果之后,匹配程序将返回两服务的输出匹配度为0,即输出匹配失败。而当请求查询要求的输入为Nouvelle而服务提供者提供的输入为Book时,匹配程序首先在Nouvelle的匹配等级列表里查找Book项,Nouvelle的SubsumesList为(Literature Books,Book),在SubsumesList中找到了Book项之后匹配程序进入相似度计算环节,并返回两服务的输入语义相似度。
4 算法性能分析
为了检验算法的改进效果,我们从互联网上选择了一个较大规模的领域本体pizza.owl (http://www.co-ode.org/ontologies/pizza/2006/07/18/pizza.owl)来进行匹配的测试。该本体由Manchester大学开发,包含了pizza领域的166个相关概念,比较适合进行算法的性能测试。
首先介绍一下测试方案:
方案一:单纯计算输入/输出相似度,不结合包含关系推理。
方案二:结合推理机制计算服务的输入/输出相似度,但不进行预处理(建立概念间的包含关系列表)。
方案三:结合推理机制计算输入/输出相似度,并在预处理阶段建立概念间的包含关系列表和匹配度列表。
从试验的结果可以看出,在不使用推理机制时,方案一的时间开销随着待匹配概念间语义距离的增大而急剧上升,在最坏情况下(两概念语义距离很大且相似度为0)的匹配效率很低;而结合推理机制后,由于排除了相似度为0的最坏情况,所以最坏情况下的时间开销有所降低。然而推理机制本身有一定的开销(判断是否插入、包含、交集关系),因此当本体规模很大时,反而可能出现速度变慢的情况;而第三种方案,无论在正常或最坏情况下,时间开销总是最小的,这是因为建立了概念间包含关系和匹配度的预处理列表,匹配时只需在列表中进行查找即可,从而把开销控制在线性时间以内。
5 结束语
在本文中我们提出了一个基于推理和相似度计算的语义Web服务匹配策略,该策略在一定程度上综合了现有两种服务匹配策略的优点,具有精确的匹配能力和在最坏情况下仍有较好的运行效率。该策略作为我们设计的语义Web服务匹配模型SWSMatchmaker的一部分,负责对服务的I.O.进行匹配;同时我们还在该模型中加入了对服务的P.E.(前提和效果)的匹配策略,进行全面的语义匹配。该模型目前正在开发和实现中。
参考文献
[1] Rudi Stuger,Richard Benjamins V.Knowledge Engineering: Principles and Methods[J].Data and Knowledge Engineering.1998,25(2):161.
[2]Massimo Paolucci,Takahiro Kawamura,Terry R Payne.Semantic matc-hing of Web services capabilities[C].In Proceedings of the First Inter-national Semantic Web Conference(ISWC),volume2342of Lecture Notes in Computer Science,2002:333347.
[3] Tversky A.Features of similarity [J].Psychological Review,1977,84(4):327.
相似性匹配 篇6
在相关的研究中,人们发现SIFT描述子在各种图像转换条件下,鲁棒性非常好。但SIFT描述子所占用的空间非常大,运行速度也慢,这是非常大的缺点。
1 学习图像特征描述子
在灰度图像补丁x当中,采用D维的向量来对其进行描述。也就是说,图像补丁特征数据映射到D维的向量空间Y。
在上面这个式子中,X指的是图像补丁的集合,也就是测试补丁以及训练补丁。向量C(x)=[c1(x),……,CD(x)]也属于补丁x的描述子。需要用一部分相应函数[hm(x)Mm=1,在这个式子里,hm必须是属于0 和1 之间的自然数,可以被当成补丁来获得描述子。
补丁x的描述子是这样的:C(x)=ATHT(x)。在这个式子当中, AT属于D×M的矩阵,可以被记作:A等于。其中,是描述子第d维对应的弱分类器系数向量。H(x)=[h1(x),……hM(x)]是由响应函数所组成的向量。因此描述子第d维的值应该是:。描述子的每一个维数都能够使其发生变化。笔者采用Ada Boost的办法,分析出了描述子每一维数的图像特征分类器的选择以及权重系数。
采用上面所说的Ada Boost方法来进行计算,先要开始确定训练样本。所谓的训练样本指的是有标记符号的补丁,[(x1,y1)],lj]Nj=1,在这个式子里,lj∈[- 11,] 。lj等于-1,这个代表的是两个不一样的补丁,同时这两个补丁也是相似的。有研究者采用Ada Boost来进行计算,发现Ada Boost方法实际上是对指数型损失函数优化的一种办法。学习目标函数应该是这样的:。
在上面这个式子当中,f(xi,yi)是补丁对相似性函数。笔者使用了描述子表示图像补丁特点,因此两个图像补丁互相的相似性度量就是两个相对的描述子之间的相似性度量,其流程图如图1所示。
在分析几个图像补丁的相似点的时候,必须要有两个流程,第一个是由图像补丁到描述子。第二个是将两个描述子的相似性进行对比,其需要建立在相似性度量函数上面。因此这样的描述可以被看成是一个二层神经网络。
1.1 特征响应函数
在这个过程中,可以将基于梯度的响应函数用来当作弱学习器。整个弱学习期是由三个参数组成,也就是说,在补丁x上,可以确定一个方向e,一个阀值T,以及矩形区域R。最后,响应函数可以这样被定义:
在这个式子当中,。另外,εe(x,m)=max(0,cos(e-0(x,m))。在这个式子当中,o(x,m)指的是补丁x在m处的像素梯度方向。方向,在这里面,q指的是梯度方向Bin的个数。采用积分图像来进行计算,效率会非常高。
1.2 学习特征的浮点描述子
采用以上方法,分析响应函数的在图像里的局部特征上作用结果乘积的权重和,运用另外的函数。。
在上面这个式子当中,∂d代表的是描述子的权重,从而得到浮点型描述子。此外,描述子的每一维对应一个响应函数。
把上面这个式子代入进去,可以得到目标函数:
响应函数空间也许属于无限的,因此如果要对OBssc进行优化,就存在一定的难度。但是可以采取Boosting来进行解决。这种算法具备贪婪的特性,可以构建弱学习器,但是效率却不高。需要对Boosted SSC的相似性函数进行修改。使用Ada Boost算法来修改相似性函数,从而算出低维数的图像特征浮点描述子,这个浮点描述子的构建方式可以被看成Ada Boost -Float - Point 。
笔者也是采用的这样的方式来对描述子进行计算,由于系数矩阵A一般都是浮点数。最后所得出的描述子也是浮点描述子。对图像补丁的相似性进行描述,需要计算出补丁对应的描述子的关联度。可以将相似性函数这样进行定义:
在上面这个式子里,C(x)以及σx都属于补丁x的描述子维数上的均值以及方差,也就是说:
在上述式子里,补丁y的表达式和x的表达是一样的,因为不是直接的对描述子的维度进行操作,所以其相似性的度量比维数值度量的鲁棒性更高。
将上面的式子代入进去,可以得到这样的目标函数:
这个目标函数属于凸函数,因此在进行优化的时候,可以找到最优解。在进行优化的时候,采用两步学习方式。第一步是在训练样本的基础上,利用Ada Boost将其最小化,从而得到M个弱学习器的权重。采取合理的方式对目标函数进一步的优化,最后再利用梯度下降法最小化OF,从而得到每一个弱学习器的权重。采取第一个算法对目标函数进行优化,从而得出配置优化的特征弱学习期非线性组合。在这个算法里,使用Ada Boost方法获得响应函数和相应的权重系数,从而构建补丁的特征描述子。这个算法对Boosted SSC进行了拓展。而且还要按照补丁的像素水平来分析相似性,使其被补丁描述子用来估算相似性。
2 怎样对描述子进行评估
在不同的数据集当中,对特征描述子的性能实施评估。第一种则是采用了Brown数据集进行评估。其包含了三组不同目标的图像补丁集,每一组有四十万个64 乘以64 补丁。这部分补丁是以Do G检测子检测出的兴趣点来作为中心。每一个数据集里的补丁有不同视角和灯光变化,其补丁数是十万、二十万以及五十万。一般采用32 乘以32 的降采样补丁,其中二十万补丁用作获取描述子,剩下的十万补丁用作测试集。
经过评估后,得出的结果是采用ROC曲线以及95%差错率来描述。
3 描述子性能对比实验
采用上面所说的描述子评估方式,在Brown中,利用3 个数据集对笔者提出的描述子进行性能评估。为了能够更好的了解实验结果,可以把结果分为两种,一种是进制描述子、浮点描述子。在本文中,将Yosemite看成训练集,将Liberty作为测试集。从而对描述子进行评估。
从图中可以看出,二值描述子是最快的,是浮点描述子中的几个数量级。这是因为弱分类器选择的响应函数组合形式不一样。这是由参数的选择所决定的。
5 总结与体会
本文提出了基于Ada Boost算法的一种框架。通过实验后发现,这样的学习架构所获得的特征描述子,在全部的描述子里面的图像局部匹配查准率最高。因此,这种方式也是合理的。
参考文献
[1]惠国保,童一飞,李东波.基于改进的图像局部区域相似度学习架构的图像特征匹配技术研究[J].计算机学报,2015.
[2]张芬.肇事车辆刹车痕迹图像特征匹配技术仿真[J].计算机仿真,2015.
[3]刘丽晖.基于不变量理论的遥感图像特征匹配技术[J].知识经济,2010.
[4]云延进,郭永彩,高潮.基于图像局部区域梯度特征描述的红外人体识别算法[J].光学技术,2008.
[5]罗楠,孙权森,耿蕾蕾等.一种扩展SURF描述符及其在遥感图像配准中的应用[J].测绘学报,2013.