首页 > SEO > 布尔模型 – 百科
2013六月13

布尔模型 – 百科

 

 

  布尔(Boolean)模型是基于集合论和布尔代数的一种简单检索模型。它的特点是查找那些于某个查询词返回为“真”的文档。在该模型中,一个查询词就是一个布尔表达式,包括关键词以及逻辑运算符。通过布尔表达式,可以表达用户希望文档所具有的特征。[1]由于集合的定义是非常直观的,Boolean模型提供了一个信息检索系统用户容易掌握的框架。查询串通常以语义精确的布尔表达式的方式输入 。

 

固定一个完全布尔代数 B 和一阶语言 L,后者由一组常量符号函数符号关系符号构成。L 的布尔值模型因此就由全集 M,它是元素(或名字)的集合,和对这些符号的释义组成。特别是,这个模型必须为 L 的每个常量符号指派一个 M 的元素,并为 L 的每个 n-元函数符号 f 和 n-元组 <a0,…,an-1> 中的每一个指派 M 的元素,这个模型必须为项 f(a0,…,an-1) 指派 M 的元素。

关系符号和等式的释义是更加复杂的: 对 M 每对元素 ab,模型必须为表达式 a=b 指派一个真值 ||a=b|| ;这个真值取自 B。类似的,对于 L 的每个n-元关系符号 R 和 n-元组 <a0,…,an-1> 中的每一个指派 M 的元素,这个模型必须指派 B 的一个元素为 ||R(a0,…,an-1)|| 的真值。

需要写些文字来解释在释义等式上的额外限制,保证它是等价关系并且这个关系顾及了等价事物的代换。

其他公式可以使用布尔代数来释义;对于命题连结词这是很容易的;你可以简单的在子公式的真值上应用对应的布尔运算符。例如,如果 φ(x) 和 ψ(y,z) 分别是带有一个和两个自由变量的公式,并且是要代换 xy 和 z 为模型的全集的元素 ab 和 c,则

\phi(a)\land\psi(b,c)

的真值简单的是

||\phi(a)\land\psi(b,c)||=||\phi(a)||\ \land\ ||\psi(b,c)||

对于量化的公式,我们需要利用布尔代数 B 的完全性。如果 φ(x) 是带有自由变量 x(可能还有其他我们忽略的自由变量),则

||\exists x\phi(x)||=\bigvee_{a\in M}||\phi(a)||

这里右手端要被理解为在 B 中所有真值 ||φ(a)|| 的上确界,这里 a 的范围在 M 之上。

一个公式的真值有时被称为它的可能性。它不能理解为一般意义上概率,它们不是实数而是完全布尔代数的 B 的元素。

 

给定一个完全布尔代数 B,有一个指示为 VB 的布尔值模型,它是冯·诺伊曼全集 V 的布尔取值的类似者。(严格的说,VB 是真类,所以我们需要适当的重新解释对于模型意味着什么)。非形式的说,我们认为 VB 是像“布尔值集合”的某种东西;换句话说,布尔值集合,不再有定义分明的元素和非元素,而有带有是这个集合的元素的特定“可能性”的对象。这个“可能性”是 B 的一个元素,不是实数。这不同于模糊集合的概念。

布尔值集合的(“可能的”)元素,依次也是布尔值集合,它的元素也是布尔值集合,以此类推。要得到布尔值集合的非循环定义,我们需要有层次的建造它们。所以对于 V 的每个序数 α 我们定义集合 VαB 为:

VαB 是 β<α 的 VβB 的并集,如果 α 是极限序数(包括 0)。
Vα+1B 是从 VαB 到 B 的所有函数的集合。(这种函数表示 VαB 的“可能的”子集;如果 f 是这种函数,则对于任何 xVαBf(x) 是 x 在这个集合中的可能性)。

我们定义类 VB 是所有集合 VαB 的并集。

有可能相对化这个完整构造于 ZF (或者有时它的片段)的某个传递模型 M。在这种情况下我们通过应用上述构造于 M 内部而构造布尔值模型 MB。对传递模型的限制是不严重的,因为Mostowski塌陷引理蕴涵了所有合理的(良基的外延)模型同构于传递模型。(如果模型 M 不是传递事物而使其变得更加杂乱,因为M 对什么意味着是“函数”或“集合”的释义可能不同于“外延”释义)。

接着我们需要在集合 VB 上定义两个 B-值的等于关系和成员关系。(在 VB 上的 B-值关系是从 VB×VB 到 B 的函数)。为了避免混淆于通常的等式和成员关系,对于在 VB 中的 x 和 y,它们指示为 ||x=y|| 和 ||xy||。它们定义如下:

||xy|| 被定义为 ∑t∈Dom(y) ||x=t|| ∧ y(t)   ("x 在 y 中如果它等于在 y 中的某个东西")
||x=y|| 被定义为 ||xy||∧||y⊆x||   ("x 等于 y 如果 x 和 y 相互都是对方的子集"),这里的
||xy|| 被定义为 ∏t∈Dom(x) x(t)⇒||ty||   ("x 是 y 的子集如果所有 x 的元素都在 y 中")

符号 ∑ 和 ∏ 意味着我们在完全布尔代数 B 中采用最小上界和最大下界。第一眼看来上述定义好像是循环的: ||  ∈ || 倚赖于 || = ||,它依赖于 || ⊆ ||,它依赖于 || ∈ ||。但是闭合检查证实了 || ∈ || 的定义只对于更小阶的元素依赖于 || ∈ ||,所以 || ∈ || 和 ||  = || 是从 VB×VB到 B 的良好定义的函数。

最后我们需要检查在 VB 上的这两个 B-值的关系 || ∈ || 和 || = || 使 VB 成为集合论的布尔值模型。没有自由变量的每个一阶集合论的句子都在 B中有一个值,我们需要检查等式的所有公理和 ZF 集合论的所有公理(没有自由变量的)有 B 的元素“真”的值。这是直接了当的,但是要花很长时间因为有很多不同的公理需要检查。

 

  缺陷

 

  第一,它的检索策略是基于二元判定标准(binary decision criterion)(例如,对于检索来说一篇文档只有相关和不相关两中状态),缺乏文档分级(rank)的概念,限制了检索功能。

 

  第二,虽然布尔表达式具有精确的语义,但常常很难将用

 

  户的信息需求转换为布尔表达式,实际上大多数检索用户发现在把他们所需的查询信息转换为布尔时并不是那么容易。

 

  除掉上述缺陷,Boolean模型仍然是文档数据库系统中的主要模型。

 

  Boolean模型定义索引术语只有两种状态,出现或者不出现在某一篇文档中,这样就导致了索引术语的权重都表现为二元性(例如, )。查询串q是一个传统的布尔表达式,假设 是q的分离形式,假设 是 的任何一种分离形式,文档与查询串的相关都定义为:

 

  如果 ,Boolean模型表示文档 与查询串相关(但可能不属于查询结果集),否则就表示与文档 不相关。

 

  Boolean模型的主要优点在于具有清楚和简单的形式,而主要缺陷在于完全匹配会导致太多或者太少的结果文档被返回。众所周知,索引术语的权重从根本上提高了检索系统的功能,从而导致了向量(Vector)模型的产生。

文章作者:houzhi
本文地址:http://www.hozseo.com/232.html
版权所有 © 转载时必须以链接形式注明作者和原始出处!

本文目前尚无任何评论.

发表评论

使用新浪微博登陆