模糊匹配范文（精选5篇）
模糊匹配 第1篇
为了能更准确理解用户的搜索关键字目标,将基于语义的模糊匹配技术应用到中文模糊识别搜索引擎中,让用户能搜索到更多相关的信息。核心思想是根据用户输入的查询信息,将和输入信息关键字相似的信息都纳入搜索引擎范围内,帮助用户找到相关信息。
搜索引擎模糊匹配框架设计
基于搜索引擎自动建立相关网的过程,相对于手动建立更方便,词汇量更丰富,更偏重包括当前文化背景下使用的词汇。
在相关网建立后,需要讨论新的从相关网到相似网算法的分析和讨论。在粗略环境下,可以使用基于距离的相似度算法进行相似网建立。
利用爬虫技术获取Internet中大量网页信息,利用分词技术从这些网页中取出内容,并保持原有词语出现的先后顺序,当大量统计出现某些词和某些词离的很近,则认为这些词之间是有关联的,自动加入相关网中,每个词按照只加入离的最近的相关词为原则,递归扩散充实相关网。
在相关网的基础上,做一个相关网的拷贝Net1,从Net1取出一词W1,依次算出所有和这个词的相似度,并只取出相似度最高的一组词W2,W3,将这个词W1和相似词W2,W3一同填充近相关网,然后取出相似词中的第一个W2,在Net1中重复上述动作,加入除已加入的词以外所有的词,在取出剩下的词重复这个动作,这样就建立了相似网。
建立好相关网和相似网后,在有用户输入的情况下,就可以采用查询网状结构的算法,遍历已经建好的两个网,生成新的关键词用来在搜索引擎上进行精确匹配,以扩展用户的搜索结果,提供更智能的搜索选择。
应用实例
搜索引擎词语搜索主要是计算机处理,搜索网页、进行网页预处理、进行词语相关分析、进行词语相似分析,根据用户输入词语进行词语匹配,根据匹配结果进行对应网页搜索,对搜索出的网页进行关键字摘取,然后展示给用户。
搜索引擎句子搜索主要是计算机处理,搜索网页、进行网页预处理、进行句子相似分析,根据用户输入句子进行句子匹配,根据匹配结果进行对应网页搜索,对搜索出的网页进行关键字摘取,然后展示给用户。
本文使用爬虫技术建立和充实相关词语网(以下简称相关网)类似Word Net组织结构,相似词语网(以下简称相似网)类似Word Net组织结构,并在Word Net磨床程序思路上,充实在基于模糊识别的搜索引擎中,分为几个不同部分:
网页爬虫部分:搜索引擎和模糊模型的数据来源;
模糊模型部分:分析用户输入关键字并给出相似关键字集合和相关关键字集合;
相关模型网:相关模型网即仿照Word Net构建中文相关词语网;
相似模型网:根据相关模型利用前面所述计算相似度的算法构建的相似模型网;
数据库信息保存部分:保存爬虫信息结果;
用户界面部分:提供用户输入,反馈查询结果。
模糊匹配系统实现的功能包括:
(1)对于既定的语义树,通过模糊匹配算法,包括语义相似度算法以及语义相近度算法,计算出语义树及各个节点间相似距离和相关距离,构建出相似网和相近网,在后续的搜索中依靠相似网和相近网不同词的距离来匹配出相关的一些信息。
(2)根据系统所实现的功能,进行分析:
搜索到的内容是正确的:例如搜索A,需要搜索A相关的内容,而不是B。
搜索到的内容是准确的:例如搜索A距离为3内容,不能出现A距离为4的词。
搜索到的内容需要根据与被搜索内容的距离进行排列:例如B到A的距离为2,C到A的距离为3,那么搜索A后,反馈的是B,C。
小结
基于模糊集的Web服务匹配算法 第2篇
随着Internet技术的迅速发展,Web服务的数量和规模与日俱增,企业之间的动态联盟和服务组合也发生着日新月异的变化。这迫切需要将分布于Internet上的众多Web服务进行自动化、智能化的交互,即服务请求者能够快速、准确、全面地绑定请求服务。因此,服务匹配的需求和应用日益广泛。
当前的Web服务搜索中,服务请求者的输入往往是基于自然语言的描述,信息和知识存在不确定性。而计算机所能处理和“理解”的是机器语言,它通过一系列符号去代表计算机的动作和被处理单元的状态。自然语言与机器语言的区别在于,自然语言是基于人的认识理解而存在的,而每个人对客观世界的认识不同,对于同一概念的理解也会有所差异,具有模糊逻辑。
因此,本论文提出基于模糊集的Web服务匹配算法,将模糊概念和模糊关系等模糊集理论引入Web模型中,把Web服务潜在数据抽象化并分类作为模糊术语和规则,从而实现人与计算机的“对话”处理。
1 当前的模糊匹配
Web服务模糊匹配的研究源于Web服务发现,已成为Web技术领域内十分活跃的研究课题。传统的Web服务发现机制使用关键词匹配技术,往往由于要求太高而造成服务匹配失败过多。目前的Web服务匹配的研究主要有分层和量化两个方向:Xiang[9]和Keller[2]基于集合间的关系把匹配程度分成Exact、Plug-in、Subsumes和Fail等多个层次;而国内的张钋[4]和胡建强[5]提出了要量化两个Web服务描述间相似度。这说明匹配算法追求的目标不是精益求精的完全匹配,而且力求匹配的完整性,也就是模糊匹配。
目前,基于模糊集的匹配算法往往针对某一特定领域。英国Coventry大学的Kuo-Ming Chao[11]构建了一个由模糊识别器、模糊引擎、UDDIOWL-S以及模糊转换器组成的模糊匹配框架;印度的Muhammad Abulaish和Lipika Dey[12]对标准本体架构(O=
可见,国外的模糊匹配主要集中在理论框架和模糊本体方面,而国内的研究则是针对中文具有丰富的副词、形容词这一特点而集中实现语言算子这方面的问题,下面逐一展开介绍。
上海交通大学的任煜[6]针对目前工程材料数据库无法表达自然语言中模糊概念的现状,提出材料性能和模糊集合的匹配以及模糊语句向SQL语句转换的方法,开发了具有模糊查询功能的工程材料数据库;云南农业大学的何汉明,李永强[7]根据数值型语言变量的模糊算子和字符型语言变量的模糊字型、字音,构建了一个能够较准确表达模糊语言变量含义的数学模型,帮助用户在信息模糊的情况下检索出所需信息;北京航空航天大学的封春升、郝爱民[8]在模糊识别方法的基础上引入了模式匹配,在语法分析的基础上,结合工程应用来定义最适合自然语言识别的语言模式,然后把模式存入到知识库中。
因此,当前基于模糊信息或者模糊集的匹配算法,大多是在已有资料库的基础上针对自然语言的模糊信息进行处理、服务匹配。而我们所提出的基于模糊集的Web服务匹配算法亦是如此。
2 基于模糊集的Web服务匹配
本论文提出的基于模糊集的Web服务匹配主要包括:文本文档的处理、构建添加模糊度的词库、文本文档的处理之后关键词的匹配情况、关键词的概念匹配转换为文本文档的匹配,具体实施方案如图1所示。
2.1 文档分词
对于一段文档或者文字描述利用分词算法,去掉停用词,可以将其分割成多个关键词,这些关键词组成文档向量。现有的分词算法可分为3大类:基于字符串匹配的分词方法、基于理解的分词方法和基于统计的分词方法。这些分词算法都比较成熟,本文不做赘述。现简单介绍一下分词之后如何根据分词结果计算文本文档的相似度,其基本思想是向量空间模型。
假如,d为文档(被查询)分词后的向量,q为查询文档分词后的向量,如下
那么,以上2个文本向量之间的相似度为它们的内积:
其中,权值W指的是该关键词对于一个文本的重要程度,即该词在多大程度上可以将这个文档与其他文档区别开。计算公式如下(详见参考文献[3]):
2.2 添加模糊度的词库
基于模糊集的服务匹配目前主要集中于某一特定领域。之所以建立添加模糊度的词库模型,是为了量化相同领域内不同概念之间的不一致性。根据概念之间的相互关系,为其赋予一个0到1之间的权重值(见表1),以此来量化地表征两个节点词汇的关联程度,即模糊度。
词库中各个概念之间的关系没有主次关系,故采用的数据结构为“图”,即将每个概念关键词作为图中的每一个顶点,而词与词之间如果存在相互关系则用边(弧)来表示,对于不同的关系用不同的权重来表示,这样就构建了一个网状关系的词库。
2.3 概念之间的匹配
词库网络中,任意两个概念之间存在3种关系:直接联系、间接联系、无联系。如果概念之间存在直接联系,则二者之间存在通路;若存在间接联系则需要多个概念的连接建立通路;无联系则不存在通路。
对于存在联系的概念,概念之间的联系可能不仅是一条路径。如果存在多个路径可以相关联,那么如何找到一条路径使得概念之间的关联度最大,这就涉及到服务匹配的算法问题。
在上述词库网络之中,如果概念t和t'之间存在k条可达路径,t→imt'代表第i条路径,路径长度(即路径经过的节点数)为m(M∈(0,1)),σij为该路径上词汇ti和tj的关联权值,则第i条路径的关联强度为该路径上词汇之间的关联权值的乘积:
那么,词汇的相似度定义为它们之间存在的所有可达路径的最大关联强度:
其中的最大关联度的确定,即max{σ(t→imt')}的计算,借鉴了图论中最短路径的思想,由程序来实现。
3 铸造业的材料选择
本文以铸造业中常见的材料选择作为基于模糊集服务匹配的实施案例。
铸造业中,设计者根据工程的要求选定一种材料。而在机械行业中,一种材料往往有多重机械性能,而多种材料也有可能共有一种机械性能,可能存在如下问题:
1)设计者没有考虑到已有的材料库中是否存在该材料;
2)设计者指定的材料仅在机械性能方面有优势,而其经济效益存在劣势;
3)如果有其他的材料也能完成类似的功能,也可以作为替代性材料。
本文以此作为案例实施,使用的编程语言是java,开发工具是eclipse和mySql。
3.1 材料选择实施方案
系统得到请求者的需求后,经过处理返回与之匹配的服务。其结果可以完全匹配,也可以存在一定的差别。比如请求者输入需求材料A时,系统根据材料本体库中已有的材料,结合建立的材料词库,返回能满足需求的材料A以及替代品B、C等,然后再进行其他方面的匹配,诸如寻求材料的供应商等等,如图2所示。
3.2 构建工程材料词库
要实施该案例,首先需要构建工程材料词库。而鉴于项目的时间限制,本论文建立了一个小型的(约50个词)、关于机械材料方面的词库,如图3所示。
该词库是根据数据结构中“图”(添加权重的图称之为“网络”)的形式来完成的。词库中,每个概念相当于网络中的每一个节点。它们的地位是等同的,都是同一类型的概念,不具有从属的关系。概念之间根据它们的关系定义不同的相似度,即权值,详见表1所示。
3.3 算法实现
对于一个复杂的工程材料网络,要想确定其中任意两种材料之间的关联程度。本论文中借鉴图论中最短路径的思想,结合本案例中的具体情况来实现可替代材料的匹配。具体实现如下:系统得到接受请求者的材料,经过处理找到其在材料网中的位置,然后遍历与该位置相关联的所有材料。如果请求材料与遍历的材料直接存在直接的联系,就以二者之间的权重作为其相似度;如果存在间接的联系,则需要对多种间接联系进行对比来完成,具体的实现由程序来完成。
3.4 实验结果分析
限于篇幅,本文仅列出部分测试数据,如表2所示,其中0.8~1指的是系统返回的、与请求材料的相似度在0.8到1之间的可替代材料的个数,0.5~0.8也是如此。输入每个词作为请求,系统分别返回3.7个、9.3个可替代材料,并且系统返回的概念均能满足预期目标,可以替代请求的材料。
虽然这样的匹配算法没有达到完全的精确匹配,但是比较符合工程的实际情况,同时也丰富了匹配结果,为制造者提供了更大的选择余地。
4 结束语
Web服务匹配是服务发现的重要步骤,是Web技术的主要应用。本文提出的基于模糊集的Web服务匹配,经过理论论证与研究,结合铸造业实例,在提高Web服务发现效率的基础上允许在搜索查询中不精确、模糊的词汇,为请求者提供更加丰富、完整的匹配服务。同时,该算法也使得计算机在一定程度上具有判断和处理模糊信息的能力,提高了机器的“智能”特性,从而实现人与计算机的“对话”处理。
此外,就理论意义而言,传统的逻辑是二值逻辑,对于Web服务匹配来说,只有匹配成功和匹配失败。而引入模糊集之后,服务匹配中加入了模糊信息,匹配失败到成功有不同的数值来标识,这就是多值逻辑。因此,本文的匹配方法也实现了二值逻辑到多值逻辑的转换,具有较高的理论意义。
参考文献
[1]Mark Klein,Abraham Bernstein.Searching for Services on the Semantic Web using Process Ontologies.IOS Press,2001,1:59-172.
[2]Uwe Keller,Ruben Lara,Axel Polleres,Ioan Toma,Michael Kifer,and Dieter Fensel.WSMO Web Service Discovery.2004.
[3]王浩鸣.信息检索发展概述[D].西安:西安财经学院.
[4]张钋.基于语义的网络服务匹配机制的研究与实现[D].北京:清华大学.2005.
[5]胡建强,等.Web服务描述语言QWSDL和服务匹配模型研究[J].计算机学报,2005:505-513.
[6]任煜,褚学宁,蔡莉霞,王滨,邓建国,陈运远,陈俊伟.基于模糊查询的工程材料数据库[J].机械工程材料.2006(12):91-94.
[7]何汉明,李永强.构建模糊检索的数学模型[J].控制工程,2003(13):159-161.
[8]封春升,郝爱民.基于模式匹配的自然语言识别[J].计算机工程与应用,2006.19:144-147.
[9]Xiang G.,Jian Y.and Mike p.p.The Capability Matching ofWeb Services.in the proceeding of the Four IEEE Interna-tional Symposium on Multimedia Software Engineering.2002,IEEE Computer Society.
[10]唐九阳,张维明,肖卫东,宋峻峰,汤大权.面向虚拟组织资源发现的语义模糊匹配[J].计算机科学,2006:172-175.
[11]Kuo-Ming Chao,Muhammad Younas,Chi-Chun Lo,Tao-Hsin Tan.Fuzzy Matchmaking for Web Services.Proceed-ings of the 19th International Conference on Advanced Infor-mation Networking and Applications(AINA’05)2005.
模糊匹配 第3篇
图像匹配算法性能评估[1,2,3]是一个复杂的系统工程,为全面评估匹配算法性能的优劣,在评估中通常采用多种指标,如能反映匹配识别正确性方面的指标(匹配概率的均值),能反映识别效率方面的指标(单次匹配时间)等。对于建立的多指标评估体系,通过赋予各指标不同的权重,体现不同指标的不同重要性,使评估结论能够多侧面反映匹配算法的综合匹配识别效果。本文在引入模糊数学中的模糊综合评判方法建立图像匹配综合评估模型的基础上,纳入多种图像匹配算法性能评估指标,得出综合合理的评估结论。
1 模糊综合评判模型
1.1 模糊综合评判模型的建立
模糊综合评判[4]是以模糊数学为基础,应用模糊关系合成的原理,为了某种目的,将一些边界不清、不易定量的因素定量化,对在复杂环境中受各种因素影响的事物或对象进行综合评价的一种方法。它是通过构造不同等级的模糊子集把反映被评事物的模糊指标进行量化,然后利用模糊变换原理对指标进行综合。
模糊综合评判包括三个基本要素[5]:因素集、评语集和权重集。
因素集可以表示为U={u1,u2,…,ui,…,un},其中,ui为综合评判中需要考虑的各种单项评估指标,如U={匹配概率均值(u1),匹配速度(u2)}。
评语集可以表示为V={v1,v2,…,vj,…,vm},其中,vj为评价匹配算法性能优劣的一种评语,如V={优(v1),良(v2),中(v3),差(v4)}。
权重是以某种数量形式对比、衡量因素集各元素对综合评估贡献大小的量值。依据不同的背景,各种因素对系统的重要程度是不一致的,因此,采用权重集A={a1,a2,…,ai,…,an}为各因素分配权重,其中,ai为第i种单项评估指标的分配权重,一般地,它们满足归一化要求:。
M(∧,∨)算子为
建立模糊综合评判模型的一般步骤[6]为
1)确定因素集U
根据评估目的,从重点关心的问题出发,结合单项评估指标确定因素集。各因素集元素之间尽量相对独立,且容易比较出相互之间的权重。若必须同时考察具有相关性的因素,可以考虑使用多级模糊综合评判模型。
2)确定评语集V
根据评估内容,确定评语集中的元素,层次分明,意义清晰。一般情况下,评语集中的元素个数取[3,7]中的整数,这样便于给出被评事物的评语归属,如果评语集中的元素个数过大,那么语言难以描述且不易判断评语归属。
3)因素集元素权重分配
由于各评价因素对评估对象的重要程度不同,因此需要确定各因素的权重集A={a1,a2,…,ai,…,an},其中0≤ai≤1,且。权重集的选择与具体评估背景有关,一般不恒定。
4)为每个评语选择对应的因素变化区间
根据评估要求和实验数据为每个评语选择对应的因素变化区间,如表1所示(假定µ1>µ2>µ3,v1
5)得出单因素评判矩阵
逐个对每个因素集元素进行量化,确定单因素对各评语的隶属度。
假设使用一种匹配算法进行了k组目标匹配识别实验,每组获得因素集上所有单项评估指标的一个值。设匹配概率均值大于等于µ1的有k11组,落在[µ2,µ1)、[µ3,µ2)区间上的分别有k12、k13组,小于µ3的有k14组,则对该种匹配方法在匹配概率均值这一单项评估指标上的单因素评判结果为
类似地,对于多种单项评估指标可以得出单因素评判矩阵:
其中:rij=kij/k,i=1,…,n,j=1,…,m。n为因素集元素个数,m为评语集元素个数。
6)得出模糊综合评判结果
将表示各因素权重向量的A与各评价指标的隶属度矩阵R用合适的算子进行合成,得到各被评价事物的模糊综合结果向量。R中的不同值表示不同指标对各级模糊子集的隶属度,R与代表权向量的A进行合成,可得到该被评价对象从总体上看对各等级模糊子集的隶属度,即模糊综合评判的结果:
其中评判结果B为一个向量,向量中的元素表明对每一种评语的隶属程度。
7)多级模糊综合评判方法
当模糊综合评判的对象相当复杂时,需要考虑的因素往往很多,这样,在众多因素当中权重的分配比较难以确定。即使形成了一个权重分配方案,由于该方案要满足归一化要求,会使权重集中的元素变得较小,导致评语集中的元素也变得较小,很多信息都在变换中损失掉了,对哪一个评语都难以占据绝对优势,从而导致模糊综合评判难以达到较好的评估效果,失去了实际意义。因此,在进行综合评估时并不是考虑的因素集元素越多越好,关键是要考虑该因素所起作用的大小,如果选取的因素过多,就会分散对主要因素的评价。因素集元素的确定需要根据实际情况来分析,有些因素需要分解,有些因素需要综合或删减。另外,因素集元素还可能分属不同的层次。当模糊综合评判的因素集元素较多时,通常把各因素进行合理分类,先对每一类进行综合评判,再对评判结果进行各类之间的高层次的综合,这就是多级模糊综合评判[7],如图1所示。
8)评判结果向量的分析
通过模糊综合评判,得到的评判结果以向量的形式表达被评判对象对各评语的隶属度,相比一个点值,能够为综合评估匹配算法的性能提供更加丰富的信息。但有时为了使评判结果更加简化且便于比较,需要对评判结果向量做进一步处理。首先,可以通过对评判结果向量的归一化来进行分析,得到的等价结果表示各评语等级在综合评判结果中占的百分比。在此基础上,还可以将各评语等级数量化,采用加权平均法,得到一个评判值。
1.2 权重的确定
权重确定方法大致可分为两种[8]:主观判断法(如专家调查法、环比评分法等)和客观判断法(如熵值法、多元回归分析法等)。主观判断法一般受主观因素干扰较大,而客观判断法则是通过提取分析数据本身所包含的客观信息,从中找出规律以确定权重。但是客观判断法往往过分依赖客观数据,且只有得到全部数据后才能确定权重,忽视了人的主动作用。
权重应该根据评价目的确定为因素集元素在对某算法性能评估中的相对重要程度,在统一的规则下比较算法。如何客观、合理的分配权重,主要取决于两方面:
1)各评判因素对评判对象的影响程度;
2)专家对各评判因素的主观认识。
由于专家认识的着眼点不同,因而对某一评判因素考虑的重要程度,即权重的分配不同。这是个模糊性问题。为了确保评估结果的准确合理,一般可对统计实验或专家评分等方法进行综合,逐步调整完善,给每个评价因素相应的权重。
2 评估实验
2.1 权重的确定
选择灰度相关匹配算法和相位相关匹配算法两类算法进行性能评估实验(下文分别简称算法1和算法2)。选取信噪比(SNR)、旋转误差因子(θ)、尺度误差因子(σ)3个图像度量指标作为参照信息。在参考图集中随机选取41幅,从每幅参考图中再分别截取98幅子图,作为匹配参考图,并对其添加畸变获得参考实时图对。
将因素集分为三个层次:
第一级因素集:U={u1,u2,u3},其中u1:准确性,u2:适应性,u3:实时性。
第二级因素集:u1={u1(1),u1(2),u1(3)},u2={u2(1),u2(2),u2(3)},u3={u3(1),u3(2),u3(3)}。其中,u1(1),u2(1),u3(1)分别代表在信噪比SNR影响下的匹配概率均值、适应性指标、匹配速度;u1(1),u2(2),u3(2):分别代表在尺度误差因子(σ)影响下的匹配概率均值、适应性指标、匹配速度;u1(3),u2(3),u3(3):分别代表在旋转误差因子(θ)影响下的匹配概率均值、适应性指标、匹配速度。
第三级因素集:uj(i)={uj(i1),uj(i2),uj(i3)},i=1,2,3,j=1,2,3。第三级因素集分别将第二级因素集u1,u2,u3分为三个子集,即SNR分别在5、25、50三个水平下、σ分别在1、1.1、1.2三个水平下及θ分别在6°、8°、10°三个水平下的匹配概率均值、适应性指标、匹配速度。
对两种匹配算法设定相同的权重集。第一级因素集的权重集设为A={0.40,0.40,0.20},第二级因素集的权重集都设为A′={0.2,0.3,0.5},第三级因素集的权重集都设为A″={0.2,0.3,0.5}。
评语划分为四个等级,即评语集为V={v1,v2,v3,v4},其中,v1:优,v2:良,v3:中,v4:差。
分别将两种算法应用于待测数据,记录实验结果,采用多极模糊综合评判模型评估算法性能。
2.2 数据分析和评估结论
根据多次实验的情况,各因素在每个评语对应的因素变化区间赋值如表2。
1)求第一级模糊综合评判结果
对算法1的第一级模糊综合评判的结果为
对算法2的第一级模糊综合评判的结果为
2)第二级模糊综合评判
第一级模糊综合评判的结果即为第二级模糊综合评判的单因素评判矩阵,与权重集进行模糊合成,得到第二级模糊综合评判的结果。
算法1的第二级模糊综合评判的结果为
算法2的第二级模糊综合评判的结果为
3)第三级模糊综合评判
第二级模糊综合评判的结果即为第三级模糊综合评判的单因素评判矩阵,与权重集进行模糊合成,得到第三级模糊综合评判的结果。
算法1的第三级模糊综合评判的结果为:B1=(0.27 0.3 0.4 0.4),归一化之后近似等于B1′=(0.2 0.22 0.29 0.29)。最后的归一化模糊综合评判结果表明,算法1的性能综合表现为:20%为优,22%为良,29%为中,29%为差。
算法2的第三级模糊综合评判的结果为:B2=(0.4 0.4 0.4 0.3),归一化之后近似等于B2′=(0.27 0.27 0.27 0.19)。最后的归一化模糊综合评判结果表明,算法2的性能综合表现为:27%为优,27%为良,27%为中,19%为差。
从归一化评判结果看,算法1的性能有42%表现为优良,29%表现为差,而算法2的性能有54%表现为优良,19%表现为差。比较而言,算法2的性能优于算法1。
为了充分利用综合评判结果提供的信息,得到更加简化且便于比较的评判结果,对评判结果向量做进一步处理。将优、良、中、差四个评语等级分别量化为:1、0.85、0.75、0.6,采用加权平均法将归一化评判结果与评语等级量化值结合,得到两种算法的评判值分别为0.7985和0.8160。比较两个评判值,容易判断算法2的性能优于算法1。
为了说明多指标综合评估模型相对于单一指标评估的优势,下面考察在尺度误差因子(σ)影响下两种算法的匹配性能。此时,尺度误差因子(σ)权重变为1,信噪比(SNR)和旋转误差因子(θ)权重都变为0。此时两种算法的模糊综合评判结果分别为(0.27 0.3 0.3 0.4)及(0.3 0.3 0.4 0.35),归一化后为(0.21 0.24 0.24 0.31)及(0.22 0.22 0.3 0.26),评判值分别为0.780和0.785。从结果可以看出,算法2与算法1在尺度误差因子(σ)测试条件下匹配准确性差不多,难以度量两算法的差异,但是在综合考虑多个评估指标及权重后,可以看出算法2的性能优于算法1。
综合来说,根据评估目的建立评估指标体系后,模糊综合评判模型能够充分得出综合评估结论。尤其当两种算法的某些性能较为接近时,采用该模型的评估结论更利于区分出两种算法的性能差异,为使用者提供参考。
3 结论
本文综述了模糊综合评判的基本概念及数学模型,并建立了基于模糊综合评判的匹配性能评估方法,对模型进行了评估仿真实验,得出评估结论。依据评估目的及各种先验知识,基于模糊综合评判的评估方法通过划分因素集层次,合理选择因素集权重及评语集,得出能够反映多方面性能的综合评估结论,并且该结论用对评语集各元素的隶属度来描述,能够更为合理的评估匹配算法性能。
参考文献
[1]Sadjadi Firooz,Bazakos Mike.A Perspective On ATR Evaluation Technology[J].Proc.of SPIE(S0277-786X),1990,1310:2-15.
[2]Brain Bassham C.Automatic Target Recognition Classification System Evaluation Methodology[D].Wright-Patterson AFB,OH:School of Engineering and Management,Air Force Inst.of Tech,2002.
[3]Nasr Hatem,Bazakos Mike.Automated Evaluation and Adaptation of Automatic Target Recognition System[J].Proc.of SPIE(S0277-786X),1990,1310:108-119.
[4]杨伦标,高英仪.模糊数学原理及应用[M].广州:华南理工大学出版社,2001.YANG Lun-biao,GAO Ying-yi.The Principle and Application of Fuzzy Mathematics[M].Guangzhou:South China University of Technology Press,2001.
[5]谢季坚,刘承平.模糊数学方法及其应用[M].武汉:华中理工大学出版社,2000.XIE Ji-jian,LIU Cheng-ping.The Method and Application of Fuzzy Mathematics[M].Wuhan:Huazhong University of Technology Press,2000.
[6]韩晶.基于模糊综合评判的供应商智能化选择与评价体系研究[D].济南:山东大学,2006.HAN Jing.The Research of Intelligent Supplier and Evaluation System Based on Fuzzy Comprehensive Evaluation[D].Jinan:Shandong University,2006.
[7]史天录,阮铭业,杨树芳.项目投资决策中的多级模糊综合评判方法及其应用研究[J].装备制造技术,2006(1):30-32.SHI Tian-lu,RUAN Ming-ye,YANG Shu-fang.Multilevel Fuzzy Integrative Judgment in Project Investing Decision-making[J].Equipment Manufacturing Technology,2006(1):30-32.
模糊匹配 第4篇
关键词：正则表达式,编译原理,模糊查询,数据匹配验证
1 引言
随着因特网的普及,基于Web站点的模糊查询和输入数据的格式匹配验证在网络中的应用非常广泛。比如使用搜索引擎在整个Web站点中搜索包含输入关键字的信息;验证输入的值是否与某种可预知的字符序列相匹配,如身份证号码、电子邮件地址、电话号码、邮政编码等字符序列。这些包含输入关键字的信息和可预知的字符序列可以用正则表达式所定义的模式来描述。
本文简要介绍了正则表达式及其运算,并从程序设计的角度分析了正则表达式在设计模糊查询程序和数据匹配验证程序方面的应用。
2 正则表达式及其运算
正则表达式是编译原理中用来描述字符串格式的一种文本模式,这种文本模式完全由它所匹配的串集来定义;与程序设计语言中的表达式类似,正则表达式也是由运算对象和运算符组合而成,只不过其运算对象是基本正则表达式,运算符是一些具有运算含义的元字符而已。因此,充分理解正则表达式中具有运算含义的元字符,是我们正确使用正则表达式的首要条件。
不同的编程工具和软件环境所支持的正则表达式的扩展运算和元字符有所不同。所以我们在使用时,必须根据应用的软件环境注意区分。正则表达式有3种基本运算和若干个扩展运算。下面介绍3种基本运算,有关扩展运算的介绍参见文献[1]。
1)选择:从多个选择对象中选择其一,用元字符“|”(竖线)表示。例如:正则表达式a|b匹配了a或b中的任一字符。
2)连结:由并置表示(不用元字符)。例如:正则表达式ab只匹配ab。
3)重复:正则表达式的重复也称为“闭包”,由元字符“*”表示。例如:a*匹配串ε(空串)、a、aa、aaa...。
这3种基本运算的优先顺序是:重复运算*优先权最高,连结其次,选择运算|最低。另外,使用括号可以改变它们的优先顺序。
3 正则表达式用于模糊查询
SQL语言的查询语句通常使用LIKE关键字实现简单的模糊查询,其中用到的通配符就是正则表达式的元字符,由于SQL语言本身支持的通配符少、功能较弱,所以不同的数据库产品在标准SQL的基础上都有所扩展,在此以Oracle Database为例来介绍正则表达式在模糊查询方面的应用。
Oracle中用于正则表达式运算的有REGEXP_LIKE操作符和REGEXP_INSTR、REGEXP_SUBSTR以及REGEXP_REPLACE函数。被搜索的数据既可以是简单的字符串,也可以是存储在数据库字符列中的大量文本。Oracle的正则表达式支持POSIX字符类,POSIX字符类必须包含在一个由方括号([])指示的字符列表中,其中的元字符类似于命名的正则表达式,这样写出的正则表达式比较特别,可以包含控制字符一类的特殊字符。
Oracle支持的正则表达式元字符也有所变化,其中表达式首部的元字符“^”表示一行正则表达式的开始,元字符“$”表示正则表达式一行的结尾;还用“{m}”表示前面的符号重复m次,用“{m,n}”表示前面的符号有最少m次最多n次的重复,象a(b|c|d)e这样的正则表达式还可以表示为a[bcd]e,匹配abe,ace,ade。另外,元字符“^”和元字符“-”还具有二义性,表达式首部的元字符“^”表示一行正则表达式的开始,而一个字符列表首部的元字符“^”代表非。因此,^[[:digit:]]匹配以数字开始的模式,而[^[:digit:]]匹配包含了任意非数字字符的模式。连字符“-”指示一个范围,正则表达式[a-m]匹配字母a到字母m之间的任意字母。但如果它是一个字符行中的第一个字符(如在[-afg]中),则它就代表连字符。
使用REGEXP_LIKE操作符可以实现较为复杂的模糊查询,如例1。
例1:在户籍管理中,根据身份证号查找出生于1988年8月的兰州市居民。
REGEXP_SUBSTR函数可以提取一个字符串与正则表达式相匹配的部分,REGEXP_INSTR函数返回一个模式的起始位置,REGEXP_REPLACE函数用指定的字符串来替换匹配的模式。因篇幅所限,相关语法格式和功能描述请参阅文献[2]。
4 正则表达式用于匹配验证
Visual Studio.net通过System.Text.Regular Expressions命名空间包含的一些类提供对正则表达式的支持,并且支持的元字符更加丰富、功能更加强大,所构造的模式也比较复杂,表2列出了部分元字符和它们在正则表达式上下文中的功能描述。
在Web站点设计中,我们常常要设计用户注册程序。要求用户输入用户名、密码、身份证号码、电子邮件地址等信息,同时要验证输入的这些字符串是否符合相关的模式,比如密码是否在六位以上、电子邮件地址是否符合格式等等。ASP.net的Regular Expression Validator控件用于验证输入控件的值是否与某个正则表达式所定义的模式相匹配。该控件的Validation Expression属性指定用于验证的正则表达式,客户端的正则表达式验证语法和服务器端略有不同。在客户端,使用的是JScript正则表达式语法。而在服务器端使用的则是Regex语法。由于JScript正则表达式语法是Regex语法的子集,所以最好使用JScript正则表达式语法,以便在客户端和服务器端得到同样的结果。
例2:验证电子邮件地址格式的合法性。
在输入格式错误的电子邮件地址后,运行结果如图1所示。
5 结论
在事务处理程序与WEB程序的设计中,搜索替换以及文本的匹配验证是最常见的操作,传统的设计方法是由用户提供与预期的搜索结果匹配的精确文本。这对于静态文本的搜索替换与匹配验证已经足够了,但它缺乏灵活性,若采用这种方法搜索或验证动态文本,将会变得很困难。因此,引入正则表达式解决上述问题是较好的一种途径。
参考文献
[1]胡元义.编译原理教程[M].西安:西安电子科技大学出版社,2003.
[2]Rischert A.Writing Better SQL Using Regular Expressions[EB/OL].http://otn.oracle.com/oramag/webcolumns/2003/techarticles/rischert_reg-exp_pt1.html.
[3]MSDN for Visual Studio.NET[DB/CD].Microsoft Corporation,2002.
模糊匹配 第5篇
Web服务在电子商务和信息领域的作用日益显著,服务提供者和消费者不仅希望找到所需的功能,也期望得到良好的非功能属性,如服务质量(QoS)。QoS包括服务的可靠性、安全性、信任及执行成本[1]。
目前衡量QoS侧重于功能属性方面,如网络吞吐量、延时及响应时间,而忽略了服务的非功能属性。实际上,在衡量非功能属时,应该考虑消费者的QoS的偏好,因为非功能属性受消费者的偏好与经验的影响。因此,消费者偏好可以用模糊方式表达,这有利于找到合适的服务。
本文在描述模糊匹配模型的基础上,提出了一种基于一致性的QoS适度方法,增加一个调解机制,在服务分类过程中对消费者和请求者之间不同的评价标准进行模糊相似聚类[2],从而达到一致性。该方法使得返回的结果更客观,为消费者找到所需的高质量的服务。
2、Web服务的模糊匹配
Web服务技术包括一系列标准语言描述接口和通讯协议,以增加软件的互操作性。服务消费者或软件开发者可以通过组合已有的服务构造新的服务。匹配是半自动或自动组合的一个步骤,传统的信息系统(数据库)通过Web服务技术打包变成服务,这种情况下服务接口和能力的相关信息不能有效地为消费者定位所需服务,因为他们更专注于数据的内容。此外,用户或者系统将使用模糊请求,在查询中包括模糊术语,因此需要对数据进行进一步的描述,包括对数据和信息进行抽象。下面通过对模糊框架的描述,引入模糊逻辑和语义Web技术对底层数据进行抽象优化发现过程[3],进而导出相似聚类方法解决服务消费者之间的不同评价标准,提高服务质量。
服务模糊匹配框架[4]如下图1所示。主要由模糊转换器(Fuzzy Converter)、匹配引擎(Matching Engine)、OWL-S2UDDI转换器、OWL-S Files、UDDI Register等组成。
其中OWL-S Files是用来存储OWL-S的档。OWL-S是基于本体OWL的描述语言,采用明确的、计算机可以理解的语言标识来描述Web,试图利用语义描述和逻辑推理最终实现服务匹配的自动化和智能化,Service Profile是OWL-S重要组成部分,除基本描述之外,使用输入(Input)、输出(Output)、前提条件(Precondition)和结果(Result)等元素描述Web服务;OWL-S2UDDI转换器将包含语义信息的OWL-S Files映射到UDDI注册器中供用户查找;模糊转换器用于将服务请求的模糊条件进行转换;匹配引擎(Matching Engine)主要由OWL-S匹配、模糊匹配组成。
文章[4]的研究是假设服务消费者和提供者对服务属性值有一致的偏好以及相同的期望。为了解决该问题,通过引入模糊调解器调整服务消费者和提供者的期望达到统一[5]。
3、一致性的QoS适度方法
上节提出了在模糊匹配框架的基础上引入一个模糊调解器,来建立服务消费者和提供者之间不同的桥梁。模糊调解器将消费者使用模糊请求进行评估后的结果保存起来,然后进行聚类和计算。
模糊调解器的工作原理是用来修正模糊规则,将各个消费者的意见进行处理,达到普遍的一致性,因而消费者可以得到满意的服务结果。虽然开始时,由于模糊规则主观性太强,查询的结果不一定满足消费者的查询请求,因此也没有必要根据消费者的反馈结果来调整规则。然而,单个消费者的意见是非常主观的,但多个消费者的意见组合在一起就没那么主观了,就有必要进行一致性处理。
达到一致性可以看作是聚类问题,通过模糊数学中的方法可以解决该问题。
3.1 相似聚类方法
为了解决服务消费者之间的不同评价标准,引入了相似聚类方法(SAM)。SAM将消费者不同的意见进行聚类,使之达到统一的标准。该方法采用相似度测量计算一组里面单个个体和其他部分的不一致来获得索引的一致性。即将每个个体的值进行聚类,通过计算达到对某个QoS属性值的一致认识。
SAM方法包括如下几个步骤。
步骤1:每个消费者采用一个正的梯形模糊数作为标准,描述他(她)的主观模糊偏好。梯形模糊数可以记作Qi(ai,bi,ci,di),其中ai≤bi≤ci≤di。如果x的值落在[bi,ci],USERi可以主观认为标准为1,即。
步骤2:获得USERi与USERj的判断相似度的标准。也可以表示为Qi(ai,bi,ci,di)与可以通过相似度函数计算。记作。如下所示:
步骤3:公式(2)中的聚类矩阵用来计算组中的每一对值的相似度[6]。
其中,,如果Sij=1,i=j则。
步骤4:计算单一用户的平均一致性。
步骤5:计算每个用户的相对一致性。
步骤6:权重的分配。
步骤7:计算个体统一度系数(CDC),由以下公式计算
认为每个个体返回的结果是平等的,故β=0。这种情况可以减少CDC的相对统一度。
步骤8:根据以上步骤得到的结果,每个个体的判断标准组合在一起,形成统一的标准Q。
3.2 相似聚类方法实例
这里选取了一个订购飞机票的实例。假定有一个QoS属性值一“便宜”是原子模糊语句,记作。再取一个初始“便宜”值,记做Qinit=(0,0,14500,16500),其中:a≤b≤c≤d。
在假定的模糊条件的初始值情况下,可以得到以下结论。如果票的价格为NTD14500,根据模糊规则,。如果票的价格是NTD15500,则。
再假设有一个群体消费者,记作Useri(i=1,2,3,...,n),他们有不同的主观判断标准定义“便宜”。当他们使用模糊查询时,返回“便宜”的结果记为Qi (ai,bi,ci,di)。
由上节公式(1)以及,每组关于便宜标准的相似度可以计算出来,如下:
由以上计算得到的结果,再根据公式(2),得到AM(一致性矩阵)。表示如下:
由公式(3),平均统一度计算如下:
A(USER1)=0.906 A(USER2)=0.915
A(USER3)=0.881 A(USER4)=0.775
再根据公式(4),每个的结果如下:
由上节提到的,假设每个参与者的意见的权重是相同的,即β=0。则有CDCi=RADi。
最后由公式(6),将四个不同用户对QoS属性值一便宜,进行上述过程的聚类,得到一致认同的结果:
最初,采取了一个主观的值:=(0,0,14500,16500)在模糊引擎中进行推理。经过消费者的反馈意见及他们对“便宜”这一模糊语句的标准,经过上节模糊相似聚类的一系列过程,可以达到不同消费者对“便宜”的相对统一意见。修正后的QoS属性值=(0,0,13332.3,14939.9)将代替初始值。模糊引擎在匹配过程采用相对客观的QoS值,使得消费者可以更好的找到所需服务。
3.3 实验结果评估
采用4种不同的消费者以及10种不同的航线来评估三种匹配方法。
在第一个实验中,只使用了UDDI以及基于能力的匹配机制,不包括模糊匹配,基于能力的匹配假设对消费者而言,他们满足能力限制因此,每个服务消费者开始检查Web服务的内容是否满足它们的需求。表1显示了结果,接下来是服务消费者的模糊集。
对于以上实验,在第二种方法中,引入模糊匹配,在模糊匹配器部署之前,服务提供者对数据进行模糊分类。因此,初始化模糊集=(0,0,14500,16500)引入来评估OoS值,对每个服务提供者都很便宜。
第三种方案就是本文提出的方法,是针对4个服务消费者发出请求模糊匹配,根据它们各自给出了QoS值cheap采用SAM方法进行处理,聚类一个一致性的QoS值cheap,得到一个更主观的模糊值。且采用θ=0.5。
以上三种方法得到的结果,如表1所示
从表1可以看出,本文提出的方法在匹配过程中能提高查准率[7],即服务消费者可以得到高质量的Web服务。
4、结束语
匹配是服务发现和组合过程中一个重要的过程。本文提出了一种支持QoS约束的Web服务模糊发现方法。它的主要优势在于:引入模糊逻辑,能对底层的信息和数据抽象和分类,处理模糊请求条件。通过模糊聚类方法,使得不同请求者之间对QoS属性值达到一致性认识。模糊引擎在匹配过程采用相对客观的QoS值,使得服务消费者可以更好地找到所需服务。最后通过实验验证该方法提高了查准率。
由于条件的限制,本文只选取了一个QoS属性值,且Web服务的数量是有限的。在模糊聚类过程中,只考虑了不同消费者的权重是相同的。因此,下一步工作将弥补以上两大缺陷。
摘要：随着Web服务的迅速发展,QoS作为Web服务的一个衡量标准,重要性日益显著。然而,现在技术很少考虑到QoS非功能的重要性,故不能找到合适满意的服务。本文提出了新的方法,通过引入模糊逻辑,将消费者的意见进行模糊相似聚类计算,旨在计算功能和非功能的QoS权重,对QoS属性值达到一致性认可,从而使得消费者更好地发现所需服务。
关键词：模糊匹配,QoS,Web服务
参考文献
[1]郑晓霞,王建仁.基于QoS的Web服务发现模型研究[J].情报科学,2007,25(2):250-253
[2]Yu T,Lin K J.Service selection algorithms for Web services with end-to-end QoS contrains[C]// Hsu M C,Zhang LJ.The IEEE Int'l Conf on E-Commerce Technology(CEC 2004),New York:IEEE Press,2004:129-136
[3]C-L Huang,K-M Chao,C-C Lo:A Moderated Fuzzy Matchmaking for Web Services,Proceedings of The 5th International Conference on Computer and Information Technology,Shanghai,China,IEEE CS,2005
[4]阳辉,金可音,汤双权,徐利谋,基于语义Web Services的模糊匹配,计算机技术与发展2007第17卷第11期.