1、第5章 查询语言与查询处理第5章 查询语言与查询处理5.1 Web查询语言5.2 查询方式5.3 相关反馈5.4 查询扩展5.5 小结思考题第5章 查询语言与查询处理5.1 Web查询语言查询语言根据信息是否可以采用某种结构表示，可以把它分为两类：一类信息能够用数据或统一的结构加以表示，称之为结构化数据；另一类信息无法用数字或统一的结构来表示，如图像、声音、视频、文档等多媒体信息，称之为非结构化数据。要检索结构化信息，最常用的就是结构化查询语言SQL(Structure Query Language)，数据库管理系统如Oracle1，DB22和MySQL3等采用的就是SQL查询语言，但这不是本
2、书讨论的重点。与传统数据相比，Web上的信息是非结构化或半结构化的和动态的，具有如下的特点：第5章 查询语言与查询处理(1)隐含的模式信息。虽然具有一定的结构，但结构和数据混合在一起，没有显式的模式定义，HTML文件是一个典型的例子。(2)不规则的结构。一个数据集合可能由异构的元素组成，或用不同类型的数据表示相同的信息。(3)没有严格的类型约束。由于没有一个预先定义的模式，以及数据在结构上的不规则性，导致缺乏对数据的严格约束。半结构化数据的模式与传统的关系数据模式或面向对象数据模式的区别在于：(1)先有数据，后有模式；第5章 查询语言与查询处理(2)不对数据结构进行强制约束，只描述数据的结构信
3、息；(3)只描述数据部分结构的非精确模式；(4)随着被描述对象数据的不断更新而动态变化。因此半结构化数据的查询语言也具有明显的特点：(1)单值和集合值属性兼容。即同一查询对应不同的半结构化数据，结果可能是单值，也可能是集合值。(2)不同的查询对象数据类型。如HMTL 文件中同一项目可以是描述信息，也可以是一个链接，即网址。(3)未知结构的查询对象。有时查询对象往往只有部分结构已知，需要通过一些机制了解数据源中的对象结构及关联的内容。第5章 查询语言与查询处理第3章已经阐述过Web上最常见的HTML文件的特点，HTML 文件语义结构松散，数据种类多，变化频繁，难以描述查询对象。但Web数据也存在
4、一定的结构化特性，如HTML文件存在标题、超链接、图像等标记，标记间还存在嵌套关系。根据Web的某种数据模式，出现了一些Web查询语言，如Squeal4、WebSQL5、W3QL6和WebOQL7等，它们都针对不同的Web 数据模型，具有各自的查询特点8。第5章 查询语言与查询处理5.1.1 WebSQL查询语言查询语言WebSQL5将Web看做关系数据库模型，并将其映射成两张关系型数据表：Document表和Anchor表。Document表包含了URL、Title、Text、Length、Type和Modify等几个属性字段，分别表示页面地址、标题、正文内容，文档长度、类型、最近修改日期等
5、属性。每个Web页对应于Document表中的一条记录。Anchor表包含了Base、Label和Href等属性，每条记录对应于页面中的一个链接，其中Base是基地址URL，Label是链接的描述文字(锚文本)，Href是指向Web文档的URL。第5章 查询语言与查询处理WebSQL的语法类似于SQL语句，采用SELECT-FROM-WHERE形式。但是，由于WebSQL是Web查询语言，因此它不但要处理基于Web文档内容的文本查询，还要处理基于Web链接的体系结构查询。为此，WebSQL在SQL语句的基础上扩充了路径正则表达式功能。例如，表达式ab表示页面a含有指向页面b的链接，且a，b位于
6、同一站点；a=b表示页面a含有指向页面b的链接，但a，b位于不同站点；a*=b表示页面a经过0个或者任意多个相同站点的链接，到达位于其他站点的页面b；a|=b表示页面a可以通过一个站点内或站点间的链接到达页面b。第5章 查询语言与查询处理WebSQL所定义的Document表和Anchor表，只是概念上的虚拟表，并没有真实的数据存在。因此在实际的查询过程中，必须先实例化这两个表，再进行真正的查询。【例例5-1】试解释下列WebSQL语句的作用：SELECT d.url FROM Document d SUCH THAT d MENSIONS WebSQL Language解：解：FROM子句中
7、的SUCH THAT.MENSIONS.把Document表实例化为d表。d表的获取可以通过向搜索引擎发送查询关键字“WebSQL Language”得到，搜索引擎返回相关页面，这些页面的各个属性数据被填入d表，达到实例化d表的目的。此时d表中各条记录对应的页面的内容均包含有“WebSQL Language”这个字符串。第5章 查询语言与查询处理【例例5-2】试解释下列WebSQL语句的作用：SELECT e.label，e.href FROM Document d SUCH THAT http:/-d，Anchor e SUCH THAT base=d WHERE e.label CONTA
8、INS Home解：解：通过FROM子句的SUCH THAT语句，达到实例化Document表和Anchor表的目的。其中，Document表被实例化成d表，Anchor表被实例化为e表。d表中各条记录对应的页面都可以通过“http:/”的站内链接到达。e表则由d表中各条记录对应页面中的所有链接组成。上述查询语句返回e表中label和href，其中label必须包含“Home”。第5章 查询语言与查询处理WebSQL(http:/www.cs.toronto.edu/websql/)提供了交互式的应用程序，用户可以直接输入WebSQL查询语句进行Web查询，如图5-1(a)所示。输入查询语句后
9、，点击按钮“Exec”即可执行查询语句，其结果如图5-1(b)所示。有一个链接满足条件，其label和href分别为Home和http:/ 查询语言与查询处理图5-1 WebSQL查询第5章 查询语言与查询处理5.1.2 W3QL查询语言查询语言与WebSQL不同，W3QL6把Web当做图模式来看待。图由节点和有向边构成，每个URL构成图的一个节点。如果URL地址a所指向的是一个HTML格式的文档，且该文档中包含至少一个指向节点b的链接，则存在一条从节点a指向节点b的边。图中的节点有URL、Format、Name、Author等属性，边有Name、Href、REL等属性。第5章 查询语言与查询
10、处理【例例5-3】试解释下列W3QL语句的作用：SELECT cp n2/*result；FROM(n1，l1)，l2，n2；WHERE SQLCOND(n1.url=http:/ BFS上述查询语句的意思是：从节点http:/ 查询语言与查询处理图5-2 FROM(n1，l1)，l2，n2子句内涵示意图第5章 查询语言与查询处理W3QL最大的特点是它提供了一个可以使用已有UNIX工具(如cp等命令)的框架。这些UNIX工具可以用于对网页文档进行处理。因此，W3QL实际上可以看成一种用于Web查询的脚本语言。DKonopnicki等还设计了基于W3QL查询语言的W3QS系统，提供对WWW的查询
11、服务(http:/www.cs.technion.ac.il/konop/w3qs.html)。第5章 查询语言与查询处理5.1.3 WebOQL查询语言查询语言WebOQL7把Web映射为超树(Hypertree)数据模型。所谓的超树可以理解为一种带有超链接(Hyperlink)的结构化文档，它由标有记录(record)的有向弧组成。超树的有向弧分为内弧和外弧，其中内弧用来描述网页的内部结构，而外弧则用来表示网页间的超链接。每个网页都可以映射为一棵超树，如图5-3所示，相互联系的超树集合便构成了整个Web。图5-3(b)中，虚线是内弧，表示页面内部的定位；实线是外弧，表示指向页面外的超链接。
12、第5章 查询语言与查询处理图5-3 HTML文档和对应的超树第5章 查询语言与查询处理由于超树的内弧能够描述网页的内部结构，因此在使用WebOQL进行查询时，查询的粒度就可以细化到网页的文件结构。相比于WebSQL查询语言，后者只是把Web文件映射为包含标题、内容和格式等属性的节点，因此不能深入地对Web文件的内部结构进行查询。下面仍然以一个实例来简要说明WebOQL的语法和应用。【例例5-4】假设有一包含若干论文的超树csPapers，如图5-4所示，试查询作者是Smith的文章的标题和Url。第5章 查询语言与查询处理图5-4 csPapers的超树示意7第5章 查询语言与查询处理解：解：
13、为了查询作者是Smith的文章的标题和Url，使用如下的查询语句：select y.Title，y.Urlfrom x in csPapers，y in xwhere y.Authors“Smith”其中，“x in csPapers”递归地把csPapers的每一棵子树分别赋值给x，x表示x的第一棵子树的根弧。如果y的Author属性包含Smith，则返回y的Title与y的第一棵子树根弧的Url共同形成的弧，方括号表示在结果中构造新弧。上述语句查询的结果是如图5-5的一棵树。第5章 查询语言与查询处理图5-5 查询结果树第5章 查询语言与查询处理WebOQL不但可以用于Web查询，还能用于
14、Web站点重构、结构化文档查询等领域。WebOQL主要克服了以往Web查询语言的一些局限，比如，缺乏对文档内部结构的利用，同时，WebOQL还融合了半结构数据查询语言和站点重构的一些思想。除了上面介绍的三种Web查询语言外，还出现了其他的一些Web查询语言，如WEBL9、WebSSQL10和Squeal11等。但是，Web查询语言的影响和作用并不如设计者期待的那样广泛，大多数Web查询语言都处于研究阶段，目前还没有可以实用的基于Web查询语言的系统。第5章 查询语言与查询处理 5.2 查询方式查询方式对于使用搜索引擎的用户来说，查询通常意味着关键词。本节介绍单个关键词和多个关键词组合查询及其他
15、查询方式。5.2.1 基于关键词的查询基于关键词的查询查询是用户信息需求的概要表示，最容易最简便的表达就是关键词。主流搜索引擎一般都是基于用户提交的关键词，检索出包含有这些关键词的文档。查询可以简单地用一个关键词来表示，很多时候，一个关键词不足以表达用户的查询意愿，这时可以提交多个关键词。多关键词的查询就涉及到关键词的组合,不同的组合方式,可能产生不同的查询结果。第5章 查询语言与查询处理1 基于单个关键词的查询基于单个关键词的查询任何有意义的文本，都是由包含特定含义的单词序列构成的，能够代表某个文本主要表达意思的单词也称为关键词。可以说，单词是语言中独立运用的基本信息单位。在英文中，词是由分
16、隔符分隔开的字母序列，而在中文中，单词之间没有自然分隔符，需要采用特殊的中文分词技术，才可以将字分组成单词。基于单个关键词的查询，就是将用户输入的单个关键词于文本索引中查找，看是否有这个关键词的出现，如果有，再按照某种检索模型或计算方法，计算出现这个关键词的文本与用户的查询之间的相似度，然后，按照相似度大小顺序，把所有满足用户需求的文本作为输出结果呈现给用户。第5章 查询语言与查询处理所以，按照单个关键词查询的关键是把文本表示成单词序列，这也是索引的主要内容。把文本分成单词不是任意的，因为单词往往存在多义性，在不同的文本中含义不同，也就是说，在不同的文本中，单词的分割至关重要，它直接影响着查询
17、的准确度和用户的满意度。比如：“学生会听老师的”这个简单文本，可以这样分隔“学生/会/听/老师/的”，也可以分隔成“学生会/听/老师/的”。例如，用户输入“学生会”关键词，如果该信息检索系统使用第一种分隔法建立索引，可能无法检索到这个文本。很多搜索引擎，为了不发生上述漏检的问题，往往进行全文索引，即把文本中除了停用词的所有可能的单词都进行索引，或者以单字为索引单位。第5章 查询语言与查询处理2 基于多关键词的查询基于多关键词的查询单个关键词往往无法完全地表达用户的查询需求，很多信息检索系统允许用户输入多个关键词，以便较完全地表达用户的查询需求。那么，信息检索系统如何处理多个关键词呢？这里介绍两
18、种方法：布尔查询(Boolean Query)和上下文查询(Context Query)。布尔查询是利用布尔运算符，来组合关键词，形成组合查询的一种方式。最常用的运算符包括“OR”(逻辑或)、“AND”(逻辑与)、“NOT”或“BUT”(逻辑非)等，假设e1和e2是两个基本查询，下面举例来说明这些常用运算符的含义。第5章 查询语言与查询处理(1)OR运算符：例如查询(e1 OR e2)表示选择所有满足e1或e2的文档，重复的部分去掉；(2)AND运算符：例如查询(e1 AND e2)表示选择所有同时满足e1和e2的文档；(3)NOT运算符：例如查询(e1 BUT e2)表示选择所有满足e1但不
19、满足e2的文档。巧妙地使用逻辑非操作，可以缩小检索的范围，提高检索效率，检索出更准确的结果。比如：“计算机 BUT 网络”，表示检索出包含计算机但不包含网络的文档。如果没有“BUT 网络”，那么可能会检索出大量用户不需要的文档。第5章 查询语言与查询处理利用上述这些布尔运算符，可以将关键词组合起来，形成复杂的组合查询，可以使用查询语法树来示意这种组合。例如：计算机AND(通信OR网络)这个组合布尔查询，涉及到三个关键词，两个运算符(如果把括号也看成运算符，就有三个运算符)，其对应的查询语法树如图5-6所示。图5-6 布尔查询结构树第5章 查询语言与查询处理图5-6表示的是检索出包含“计算机”以
20、及“通信”或“网络”等词的所有文档。但是，对于普通用户来讲，要利用布尔运算符来表达自己的查询需求，却并不是一件容易的事，因为普通用户一般并不熟悉布尔运算符的含义。例如，一般人理解查询“小汽车和卡车”的意义是表示查找包含小汽车的文档或包含卡车的文档，而用逻辑的AND表示“小汽车AND卡车”其意思就是查找同时包含小汽车和卡车的文档。所以布尔查询可能给用户带来困惑，这就要求信息检索系统设计者要做充分的考虑，例如，Google搜索引擎在界面上给用户必要的说明，引导用户充分正确地表达查询需求，如图5-7所示。第5章 查询语言与查询处理图5-7 Google中文高级检索的界面第5章 查询语言与查询处理上下
21、文查询是进行多关键词组合查询的另外一种方法。上下文查询的一种实现方式是短语查询。短语查询由一系列单词查询组成，多个词形成一组词，由此来匹配文本中与其相近的词。在匹配的时候，可把文本中的停用词去掉，查询的要求是找到包含这些词的文档子集。上下文查询的另一种实现是近似查询，用户可以提供多个查询词，并给出单词之间允许的最大距离。距离可以用字符、字或词来衡量，可以要求查询结果中的词与查询中的词出现的顺序一致，也可以要求不一致。例如，用户提交的词组查询词可能是“红色”和“汽车”，目的是查询包含“红色汽车”的文档。但是，可能文档中包含“红色奔驰汽车”，也是用户感兴趣的文档。也就是说，虽然有些词夹在关键词中间
22、，或者说用户给出的词并不是紧挨着出现在文档中，这些文档也有可能与查询的要求相关。也可以给出词之间的距离限制，例如，“白色W/3 房子”表示词“白色”和“房子”出现在3个词(字)以内的文本，即满足查询要求。第5章 查询语言与查询处理搜索引擎比较流行的方法是用空格或逗号把词分开，用引号把词组合起来。最好的方案是只要用户说明准确的词组，并不要用户给出距离，系统隐含地考虑词之间的距离，按照词之间的距离加权，随着距离的增加，相关度呈指数下降。第5章 查询语言与查询处理3 自然语言查询自然语言查询把布尔查询模糊化，查询就变成了枚举多词查询和上下文查询，这样，所有能匹配部分用户查询的文档都被检索出来。匹配的
23、越多，排序的等级就越高。用户还可以表达哪些词是不想要的，将它们作为反例来处理，于是包含反例词的文档在排序计算结果中往往靠后。选择一个阈值，可以将相关度较低的文档排除在检索结果之外。在这种方案中，已经完全不用布尔操作，而是采取自然语言查询的思想。事实上，可以把布尔查询看做自然语言查询的简化和抽象。第5章 查询语言与查询处理自然语言查询是信息检索系统的一种非常自然的查询说明方式，用户提出的信息要求以自然语言的形式输入给系统，系统的处理过程一般是这样的：把句子中的停用词去掉，留下主干词，然后利用这些词进行查询，接下来具体的查询实施可以利用短语查询或近似查询处理方法。有些信息检索系统还可以对自然语言进
24、一步处理和分析，从中抽取一些概念，并用于匹配文档中的概念，这种概念查询方法可以用在特殊的提问式自然语言查询中。从自然语言中可以抽取提问关键词，例如“谁”、“什么时候”、“什么地方”等，系统就可以结合提取出的其他词，一并检索出与这些词相关的人物、时间、地点等。第5章 查询语言与查询处理5.2.2 模式匹配模式匹配模式匹配是人工智能领域中经常使用到的一个术语。所谓模式可以理解为某种特征，模式匹配就是看某个东西是否具有这种特征。在本节中，模式就是出现在文本中的某种或某几种语法特征，满足这些语法特征的文本就可以说是与此模式相匹配(match)。每个信息检索系统都允许处理多种模式，从简单的单词到很复杂的
25、常规表达式。一般来说，模式集越有效，用户构建的查询就越复杂，查询的实现也就越繁琐。常用的模式类型有以下几种5：(1)单词：最基本的模式，如“computer”或“计算机”。(2)前缀：构成单词开头部分的字符串。例如有一个前缀“re”，那么所有具有该前缀的单词(如reable、rebark、recall等)都匹配该前缀模式。第5章 查询语言与查询处理(3)后缀：构成单词结尾部分的字符串。例如，有一个后缀“less”后，那么，所有具有该后缀的单词(如careless、bless等)都匹配该后缀模式。(4)子字符串：在文本单词中出现的字符串，它作为一个整体，可以出现在单词或文本中的任何位置。例如，给
26、定子字符串“bea”，那么，所有包含该子字符串的单词或文本(如beauty、bear、abear等)都匹配该模式。查询的时候，这种模式可以出现在文本的任何地方，有时候可能产生意想不到的检索结果，例如：“any flow”也会与短语“many flowers”相匹配。第5章 查询语言与查询处理(5)范围：用一对字符串表示，可以用于匹配在词典顺序上位于这对字符串之间的任何单词。例如：有一对字符串表示的模式“tin”to“tix”，这些词如“tip”、“tire”、“title”正好在“tin”和“tix”之间，所以，它们匹配该模式。这种模式可用来限定范围，或组合某些特殊的查询。(6)许可误差：一个
27、带有误差阈值的单词。这种模式匹配的检索，是在基本模式基础上增加了误差阈值，允许检索出与基本单词相似的单词，只要在许可的误差范围之内即可。打字、拼写、视觉特征识别软件或者其他因素，都可能造成文本或单词出错，这种模式匹配刚好可以弥补这些差错，避免了因为差错可能产生的漏检。那么误差如何来量度呢？通常使用的量度是莱文斯汀距离(Levenshtein Distance)和最长共同子序列(Longest Common Subsequence)。第5章 查询语言与查询处理莱文斯汀距离也叫编辑距离(edit distance)。两个字符串之间的编辑距离是使字符串相等时所需要的字符插入、删除和代替的最小值，比如
28、“school”和“sc hool”两个字符串，它们的编辑距离为1，因为删除一个空格字符就可让两者相同。又比如，“misspell”和“mistell”的编辑距离为2，“misspell”和“misspelling”的编辑距离为3。两个字符串的距离(或误差)除了上面介绍的编辑距离方法之外，还有最长共同子序列方法。最长共同子序列是指两个字符串共有的最长子串的长度，它可以通过删除所有的非公共字符得到(不可以改变原字符的顺序)。例如：“misspell”和“mispell”之间的最长子序列是“mispell”；“misspelled”和“misinterpretted”的最长子序列是“mispeed
29、”。第5章 查询语言与查询处理(7)正则表达式：是一个由字符串和一些运算符所构成的通用模式。从简单的模式出发，可以构造复杂的模式。一个单独的字符是一个正则表达式。如果现在有正则表达式e1、e2和e，用如下常用的运算符功能可以构造新的正则表达式。并(|)：(e1|e2)也构成了一个正则表达式，它表示可匹配e1，或者也可匹配e2。(8)串(Concatenation)：正则表达式(e1e2)表示事件e2紧跟事件e1的出现而出现，即一个匹配e1的字符串和紧跟着的匹配e2的字符串。(9)重复：(e*)表示e连续出现，匹配的是零或多个e连续出现的字符串。下面举例来加深对正则表达式的理解：第5章 查询语言
30、与查询处理【例例5-5】有一个正则表达式“(u|e)nabl(e|ing)”，试写出三个满足该正则表达式含义的字符串。解：解：这个正则表达式表明，“nabl”一定要出现在字符串中，“u”或“e”任意出现一个即可，但必须紧挨在“nabl”之前，“e”和“ing”任意出现一个即可，但必须紧挨在“nabl”之后。所以，“unable”，“unabling”，“enable”等都可以满足这个正则表达式，即这三个字符串(或单词)都可作为匹配该正则表达式的结果输出。第5章 查询语言与查询处理(10)扩展模式：由用户来构建正则表达式往往很困难，也是不现实的事情。扩展模式提供了一种友好的查询构造方法，用户很容
31、易掌握和表达自己的查询意愿，由系统将用户提交的查询构造转换成正则表达式。可以把扩展模式理解为正则表达式的一个子集，检索系统可以在内部把扩展模式转化为正则表达式，或者用特定的算法去检索。不同的系统一般只支持各自的一组扩展模式，所以没有统一的定义。比如通配符模式“reh*e”，它表示以“reh”开头和以“e”结尾，之间可以是任何字符的字符串，所以“rehire”、“rehouse”、“rehmanniae”都匹配该模式。又比如，范围操作模式“c(1，5)”，它表示“c”出现15次的字符串，所以，“cat”、“access”等匹配该模式。第5章 查询语言与查询处理5.3 相关反馈相关反馈对于用户来说
32、，使用信息检索系统的最主要目的就是查找到自己需要的信息。至于系统输出给用户的信息是否是用户所需，就要采用相关度(或相似性、相关性)来量度了。但是尽管很多学者进行了大量的相关性研究，却没有形成统一的量化的相关性的定义。这是由于，一方面用户的需求本身就难于表达完全或表达清楚，另一方面系统对文本的表达也很困难，比如采用词频来表达文本本身就有很大的局限。所以，信息检索系统输出的按照相关度排序的检索结果往往不是太多就是太少。第5章 查询语言与查询处理在第1章介绍过一般的信息系统可以用“两个表示，一个比较”来概括，为了追求满意的检索效果，直观的想法就是让“表示”更加准确和完整。相关反馈主要着眼于通过人机交
33、互过程尽量准确地表示用户的需求。Rochhio等人给出了相关反馈的数学模型12：(5-1)nr110NRjjirinRQQ式中：Qn和Q0分别表示修正后的查询向量和初始的查询向量；Ri和NRi分别表示相关文档向量和不相关文档向量；r和nr分别是相关文档数和不相关文档数；，是常量，和可以控制反馈的程度。这个公式的含义很明显，就是在重构新的查询变量时，把用户指定为相关的文档进行正反馈，把用户指定为不相关的文档进行负反馈。相关反馈的过程可以用图5-8表示。第5章 查询语言与查询处理图5-8 相关反馈过程示意图第5章 查询语言与查询处理对任意一个查询，总存在一个理想的查询结果集，这个理想结果包含跟查询
34、完全相关的文档，不包含不相关的文档。相关反馈就是力图通过用户的参与，不断将用户的查询意愿反馈给系统，让查询结果逐步逼近理想结果集。根据图5-8，相关反馈的过程可以概括为：(1)用户输入初始查询；(2)信息检索系统向用户输出初始查询结果；(3)用户从结果中选择中意的文档，反馈给系统；(4)系统根据反馈信息重构查询，并重新输出结果给用户；(5)第(3)和第(4)可以一直进行下去，直到用户满意为止。第5章 查询语言与查询处理可见，在相关反馈过程中，查询重构是非常关键的一步，目前采用的方法主要有两种：一种是检索词加权，提高在相关文档中出现的检索词的权值，降低在非相关文档中出现的检索词的权值；另外一种是
35、查询扩展，将相关文档中新的有用的检索词用于扩展查询。很多时候，这两种方法一起使用。第5章 查询语言与查询处理5.3.1 向量空间模型中的相关反馈向量空间模型中的相关反馈向量空间模型是把查询和文档分别表示为向量，再通过计算向量的距离，来表征查询和文档之间的相似程度，并按照相似程度输出排序检索结果。向量空间模型中的相关反馈，主要利用用户对查询结果的相关或不相关的反馈，重新构造查询向量，利用新的查询向量，重新输出排序结果。设文档集大小为N，其中的相关文档数量为|Cr|；检出的文档中相关文档的数量为|Dr|，不相关文档的数量为|Dn|。这些变量之间的关系如图5-9所示。第5章 查询语言与查询处理图5-
36、9 VSM相关反馈涉及的变量定义第5章 查询语言与查询处理在理想的情况下，查询应该可以把相关文档和不相关文档完全区分开，这个查询就是理想查询，可用如下的公式表示5：(5-2)jCdrjCdrdCNdCqnjrj|1|1opt但比较难办的是，事先几乎不可能得到相关文档数目Cr，所以，这个理想查询是无法得到的。1971年，Rocchio提出了一种反馈方法12，通过用户的反馈，让重构的查询逐渐地靠近这个理想查询。标准的Rocchio公式如下：(5-3)jDdnjDdrmdDdDqqnjrj|第5章 查询语言与查询处理一般地，Rocchio公式中的=1。可见，Rocchio公式在理想查询公式的基础上增
37、加了q项，即增加了对用户初始查询意愿的考虑，这是很自然也很合理的。同时以用户指定的检出相关文档作为正反馈，很多系统为了加强正反馈，往往取r。同年，Ide在分析验证Rocchio公式的基础上，提出了另外两种查询重构方法13：Ide-regular：(5-4)jDdjDdmddqqnjrjIde-Dec-Hi：(5-5)jjDdmddqqrj不相关max第5章 查询语言与查询处理Ide-regular公式只在Rocchio公式的基础上作了细微的调整。Ide-Dec-Hi公式则对不相关文档部分作了大胆的处理，把用户认为最不相关的那篇文档或不相关文档中与查询q最相似的文档向量作为负反馈，其他的不相关文
38、档则不予考虑。以上3种反馈方法都是结合文档向量和初始查询向量以重构新的查询向量。但在向量权重的调整策略方面，三者是有差异的。Rocchio采用标准化因子方法；Ide-Dec-Hi采用的是向查询向量增加所有相关文档向量以及减去一篇最不相关文档向量的方法；Ide-Regular采用的则是向查询向量增加所有相关文档向量以及减去所有不相关文档向量的方法。1990年Salton等人对这3种反馈方法在6种不同的测试集上作了比较研究14，结果表明Ide-Dec-Hi方法最优。该研究还发现初始检索表达式含有重要的信息，且相关文档中含有的信息量要比不相关文档中的信息量大，这解释了为什么。Salton等还发现=0
39、.75，=0.25时，Rocchio方法可以获得较好的检索效果。第5章 查询语言与查询处理【例例5-6】设有一个初始查询向量：(5，0，3，0，1)，假设这个初始查询向量输出的初始结果集有两个文档D1和D2，用户反馈认定文档D1相关，文档D2不相关，其中文档D1向量为：(2，1，2，0，0)，文档D2向量为：(1，0，0，0，2)。假设=1，=0.75，=0.25，试采用标准Rocchio公式重构查询，采用内积计算并比较反馈前后的文档与查询的相似度。解：解：反馈前，利用初始查询向量进行检索，文档和查询的相似度分别如下：160100231025)(),sim(1,1tkqkdkwwqD72100
40、030015)(),sim(1,2tkqkdkwwqD第5章 查询语言与查询处理用户反馈认定D1是相关文档，D2是不相关文档，根据标准Rocchio公式，构造新的查询为：jDdnjDdrdDdDqqnjrj|Rocchio=1(5,0,3,0,1)+0.75(2,1,2,0,0)0.25(1,0,0,0,2)=(6.25,0.75,4.5,0.5)计算新查询和文档的相似度：25.22)(),sim(,1Rocchio1qkdktkwwqD25.7)(),sim(,12qkdktkwwqD第5章 查询语言与查询处理反馈前，D1与查询的相似度是D2与查询的相似度的2.29倍，用户反馈D1相关而D2
41、不相关，在重新构造的查询向量基础上进行相似度计算，D1与新查询的相似度是D2与新查询的相似度的3.07倍。可见，用户反馈加大了相关文档与不相关文档的分界，拉大了它们之间的差别，有利于更准确的结果输出。第5章 查询语言与查询处理5.3.2 概率模型中的相关反馈概率模型中的相关反馈经典的概率模型本身就是一个相关反馈的模型。事实上，在第2章的概率模型一节，就已经用实例解释了概率模型中相关反馈的工作过程，为了内容的完整性，这里再将概率模型相关反馈过程归纳如下：(1)用户输入初始查询，假设概率初始分布P(ki|R)=0.5和P(ki|)=ni/N，进行检索，用户从系统输出的初始结果集中判断出相关文档和不
42、相关文档。(2)利用公式(2-18)、(2-19)或任意一种变形，根据用户的反馈，重新估计计算P(ki|R)和P(ki|)。RR第5章 查询语言与查询处理(3)利用公式(2-13)，计算相似度，重新排序输出。(4)第(2)、(3)步可以不断反复进行，直到输出的结果用户满意为止。概率模型中相关反馈的优势体现在与检索词在相关文档、不相关文档中出现的概率直接联系，但是它忽略了每篇文档的检索词权重和上一次的概率调整；另外，与向量模型不同，概率模型中，相关文档没有直接用于查询修正，相反地，它只是利用相关文档中检索词的分布情况来决定检索词概率和权重，这是概率模型相关反馈方法不能像向量模型相关反馈方法一样有
43、效运作的一个原因。第5章 查询语言与查询处理向量空间模型相关反馈和概率模型相关反馈是最常用的相关反馈方法。其他的相关反馈方法可能是某方面的改进或针对特定系统的特别要求，并没有形成大的影响，例如布尔模型的相关反馈技术Dillon方法15、DNF方法16等。Crestani F17提出了一种神经网络的检索模型，将所有的文档和查询进行处理后生成一个知识表示矩阵，然后利用这个知识表示矩阵，生成相关文档列表，并进一步提出了基于神经网络模型的反馈方法，这个反馈方法分两步进行：对查询和相关文档采用BP(Back Propagation)学习算法进行训练，调整神经网络的参数；用训练出的神经网络，生成新的查询。
44、Crestani认为，无论是向量空间模型，还是概率模型，对相关文档和不相关文档的划分都是线性的，即只能用平面划分。因此准确率有一个上限，而神经网络模型可以进行曲面划分，故可以达到更高的准确率。第5章 查询语言与查询处理相关反馈需要用户的参与，由于各种原因，用户可能并不能很好地配合系统提供有效的反馈信息，因此出现了伪相关反馈(Pseudo Relevance Feedback)方法。所谓伪相关反馈就是不需要用户的参与，系统假定检索结果中排在前面(比如前10个)的文档是相关文档，然后利用这个信息来重构查询。第5章 查询语言与查询处理5.4 查询扩展查询扩展不管中文还是英文，都存在大量的同义词，或者
45、用不同的词来描述同一个概念，或者词语之间存在复杂的关系。对于大多数信息检索系统来讲，无法识别这些情况，往往导致检索效果的下降或检索失败。比如用户查询“土豆”，一般来说系统输出给用户的结果集是一些包含“土豆”的文档，而出现了“马铃薯”、“山药蛋”的文档一般不会被检出，尽管这几个词，指的是一个事物，但系统还没有“聪明”到可以认识到这点。又比如用户想找一些吃的东西，输入查询“food”，一般地，用户只能得到一些包含有“food”的文档，而包含“rice”、“grilled-fish”和“apple”等的文档很可能被忽略。第5章 查询语言与查询处理为了避免上述这些情况的发生，可以采用查询扩展的方法。比
46、如，用户输入查询“土豆”，系统自动把“马铃薯”、“山药蛋”增加为查询词后再进行查询，检索的结果不仅包含用户的输入查询词，还包含系统扩展的查询词，这直接提高了查全率。查询扩展的方法很多，可以把它分为三类：基于字典的简单查询扩展、自动局部分析(Automatic Local Analysis)方法和自动全局分析(Automatic Global Analysis)方法。第5章 查询语言与查询处理5.4.1 基于字典的简单查询扩展最简单的查询扩展是在用户的初始查询词的基础上，找到它的同义词，直接加入到查询词中；或者根据上下文关系，挑选一些词加入到查询词中。如何找到相同含义的词或相近含义的词呢？可以采
47、用电子词典来完成这个工作。目前，有很多电子词典可以选择，如普林斯顿大学的英语WordNet18、微软的MindNet19、欧洲的基于WordNet的EurowordNet20、日本电子辞书研究所(Japan Electronic Dictionary Research Institute，EDR)的日语和英语的概念词典21以及美国HPKB(High Performance KB)22等等。在中国，有HowNet23、CCD(Chinese Concept Dictionary)24等。本节将介绍两种电子词典：WordNet和HowNet。第5章 查询语言与查询处理1 WordNet1985年，
48、美国普林斯顿(Princeton)大学认知科学实验室(Cognitive Science Laboratory)开始启动WordNet项目的研究。WordNet是一个在线词典数据库系统，采用了与传统词典不同的方式，即按照词义而不是词形来组织词汇信息。目前已形成了WordNet的在线电子词典，并受到各国研究人员的广泛关注，很多国家也在进行WordNet的本土化工作。在WordNet的网站(网站首页：wordnet.princeton.edu)，WordNet定义为受人类词汇记忆的语言心理学理论启发而设计的一个在线词汇参考系统。英语名词、动词、形容词和副词被组织成同义词集合(Synset)，每个同
49、义词集表征一个词汇概念，同义词集间通过各种关系联系起来，如图5-10所示。第5章 查询语言与查询处理图5-10 WordNet词语关系图例第5章 查询语言与查询处理WordNet 3.0收录了超过15万个的独立词条，其中名词11万多个，动词1万多个，形容词2万多个，副词4000多个，分属于11万个不同的同义词集(Synset)。每个同义词集表示一个基本词汇概念，并在这些概念之间建立了各种关系，包括同义关系(synonymy)、反义关系(antonymy)、上下位关系(hypernymy&hyponymy)、部分关系(meronymy)、近义关系(similar)，因果关系(cause)、蕴涵关
50、系(entailment)、整体关系(holonym)等多种语义关系。图5-11列出了几种与查询扩展密切相关的WordNet关系的例子。第5章 查询语言与查询处理图5-11 WordNet关系举例第5章 查询语言与查询处理除了可登录WordNet网站进行在线查询，也可以下载安装程序，安装在本机上进行体验。在图5-12中，输入一个单词“food”，系统返回结果表明，“food”有三种含义，分别出现在三个同义词集中。图5-12 WordNet浏览器 第5章 查询语言与查询处理查询扩展正是利用这些关系进行的。比如，用户向信息检索系统输入“dog”查询词，通过WordNet发现“dog”有“domes
