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