《布尔检索模型》PPT课件.ppt

布尔检索模型,XXXX,布尔检索模型,概述 布尔检索法是指利用布尔运算符连接各个检索词，然后由计算机进行逻辑运算，找出所需信息的一种检索方法。 设文本集D中某一文本i, 则该文本可表示为: 其中 为标引词用来反映文本i的内容 设另一用户检索表达式为 对于该检索式，系统响应并输出的一组文本应为:它们都含 有标引词 和 或者含有标引词 和 。,布尔运算符,AND（或*）：逻辑与 表示所连接两个检索词的交集部分。例如检索同时含有关键词A和B的集合C：A AND B OR（或+）: 逻辑或 表示查找含有检索词A和B之一，或同时包含检索词A和B的信息 : A OR B NOT（或-）: 逻辑非 表示含有检索词A并且不含有检索词B的信息： A NOT B,布尔运算符,运算符之间的优先级： NOT AND OR，如检索表达式：雪花 NOT 啤酒 AND 歌曲 OR 小说，搜索结果为：名字叫雪花的歌曲或者小说。 利用小括号（）可以设置出个性化的检索方程。例如检索出不包含日本在内的有关教育或法律方面的信息： （university OR college） AND （ education OR Law ）NOT Japan,布尔模型在网页查重中的应用,网页中的重复现象 微软曾作过一个试验，从网络中下载了150 000 000个网页，发现这些网页中有292是相似网页，而且这些相似网页中还有222是完全重复的(一字不差)；另外相似网页十分稳定地存在，一对相似的网页在1O个星期以后极有可能还是相似的网页。 网页重复的弊端 重复的网页降低了网页采集器的工作效率，浪费了数据挖掘工具的资源，使用户的工作效率下降，如何能够尽可能准确地去除这些重复的网页就是我们所面临的问题。,布尔模型在网页查重中的应用,关于重复的定义 一直以来，对于重复的定义都非常模糊，没有一个清晰的定义。一字不差可以理解为重复，字面上意义相近也可以理解为重复。对于重复各人都有自己的定义。, Conrad对于重复的定义是：如果两篇文章之间有超过 80 的用词相同，而且长度相差不超过正负20 ，则这两 篇文章就是重复的。 Pugh(work for Google)对于重复的定义就要简单得多：如果两篇文章之间有超过r个特征相同，则它们就是相似的。,布尔模型在网页查重中的应用,在利用布尔模型的查重算法中，对于重复的定义就是使用Pugh对重复的定义。 该算法是利用布尔模型进行查重，将每篇文章表示为一个二进制数，若是符合比较条件的两篇文章，则将两个二进制数异或，结果中为1的特征则是两篇文章不同的特征，计算出两篇文章中的不同特征个数后，再判断是否需要它们比较。,当语料集合较大时，文档之间两两比较的次数就相当巨大，这是所有网页查重算法的瓶颈。在使用布尔模型的网页查重算法中，两篇文档之间是否需要比较取决于它们的相同特征个数而不是文档长度，当特征的总个数差别在阈值d之内的时候，就异或其二进制码；否则不需要比较，直接判定它们不同。 在得到二进制码异或的结果（0或1）之后，在读取文档的过程中建立一个索引。(表1),网页重复的判定过程:,布尔模型在网页查重中的应用,其中id代表特征的唯一表示，Doic表示出现了该特征的文档的唯一标识符。当两篇文档相互比较而相异结果为1时，就将它们分别插入它们之间不同的特征链表中；否则，插入相同特征链表中。 当再有新的文档需要比较时，根据该文档中出现的特征，选择应该与它相同的集合，以减少比较次数。,布尔模型在网页查重中的应用,表一 索引数据结构,使用这种算法的优点： 由于一些词在所有文档中都大量出现，这些词将不会作为文档的特征值，可以忽略大量常用停用词的影响，如in，and，the等，这样读取文档时就不需要特别过滤常用词，节约了处理文档和提取特征的时间。 特征值的比较结果只有1和0两种状态，节约资源，易于实现。,布尔模型在网页查重中的应用,当两篇文档需要比较时，最好的情况就是所有的特征均不同，结果为0，此时的相异度就为1。当有 k（比如设k为0.2）以上特征不同时，则判定两篇文档为非相似文档；如有0.2 以下的特征不同，则需要计算这些不同特征总的频度(Tf)。表2为文档D1和D2相异度的计算实例。,相异度的计算:,布尔模型在网页查重中的应用, T表示文档中出现的特征，D表示特征t是否在文档Doic中出现过( 0表示没有出现，1表示出现了，这就是布尔模型)，Tf表示特征 t 在文档中的出现频率，Result表示两篇文档之间D的异或结果：Result=D1 D2。,表二 D1和D2相异度的计算,对于两篇文档i和 j，假设它们符合比较的条件，则它们的相异度计算公式为: 上式中 表示特征w在文档i中的频率，在计算分子时，要去掉在两篇文档中频率均较高的T4。在表2中，计算出 ，文档1和文档2的相似度为 。结果是文档1和文档2不同。,第一，与人们的思维习惯一致:用户可以通过布尔逻 辑运算符“AND”、“OR”、“NOT”将用户的提问“翻译”成系统可接受的形式。 第二，表达直观清晰:布尔逻辑式表达直观清晰。 第三，方便用户进行扩检和缩捡:用户可通过增加逻辑与进行缩小检索，增加逻辑或进行扩展检索。 第四，易于计算机实现:由于布尔检索是以比较方式在集合中进行检索的，返回结果只有1和0，易于实现，这也是现在的各种检索系统中都提供布尔检索的重要原因。,布尔检索模式的优点,第一，它的检索策略只基于0和1二元判定标准。例如，一篇文档只有相关和不相关两中状态，缺乏文档分级（rank）的概念，不能进行关键词重要性排序，限制了检索功能。 第二，没有反映概念之间内在的语义联系。所有的语义关系被简单的匹配代替，常常很难将用户的信息需求转换为准确的布尔表达式，一些与用户信息需求确实相关但又不是用检索式中。 第三，完全匹配会导致太少的结果文档被返回。没有加权的概念，容易出