网络信息获取与情报分析技术(七)课件.ppt

1、网络情报获取分析技术提纲2 信息检索概述信息检索概述 倒排索引倒排索引 布尔查询的处理布尔查询的处理提纲3 信息检索概述信息检索概述 倒排索引倒排索引 布尔查询的处理布尔查询的处理信息检索Information Retrieval Information Retrieval (IR) is finding material (usually documents) of an unstructured nature (usually text) that satisfies an information need from within large collections (usually st

2、ored on computers). 信息检索是从大规模非结构化数据（通常是文本）的集合（通常保存在计算机上）中找出满足用户信息需求的资料（通常是文档）的过程。 Document 文档 Unstructured 非结构化 Information need 信息需求 Collection文档集、语料库4IR vs数据库: 结构化 vs 非结构化数据 结构化数据即指“表”中的数据5EmployeeManagerSalarySmithJones50000ChangSmith6000050000IvySmith数据库常常支持范围或者精确匹配查询 。e.g.,Salary 60000 AND Mana

3、ger = Smith.非结构化数据 通常指自由文本 允许 关键词加上操作符号的查询 更复杂的 概念性查询, 找出所有的有关西藏的网页 经典的检索模型一般都针对自由文本进行处理6半结构化数据 没有数据是完全无结构的 李甲主页 半结构化查询 Title contains data AND Bullets contain search 这里还没有提文本的语言结构7非结构化 vs. 结构化 vs. 半结构化 半结构化(Semi-structured)： 李甲主页 8传统信息检索 vs. 现代信息检索 传统信息检索主要关注非结构化、半结构化数据 现代信息检索中也处理结构化数据9非结构化数据(文本) v

4、s. 结构化数据(数据库) 1996年10数据量市场规模非结构化数据(文本) vs. 结构化数据(数据库) 2013年020406080100120140160180200Data volumeMarket CapUnstructuredStructured11数据量市场规模布尔检索 针对布尔查询的检索，布尔查询是指利用 AND, OR 或者 NOT操作符将词项 连接起来的查询 信息 AND 检索 信息 OR 检索 信息 AND 检索 AND NOT 教材 Google的高级搜索？12提纲13 信息检索概述信息检索概述 倒排索引倒排索引 布尔查询的处理布尔查询的处理一个简单的例子(莎士比亚全集

5、) 莎士比亚的哪部剧本包含Brutus及Caesar但是不包含Calpurnia？ 布尔表达式为 Brutus AND Caesar AND NOT Calpurnia。 笨方法： 从头到尾扫描所有剧本，对每部剧本判断它是否包含Brutus AND Caesar ，同时又不包含Calpurnia 笨方法为什么不好? 速度超慢 (特别是大型文档集) 处理NOT Calpurnia 并不容易（一旦包含即可停止判断） 不太容易支持其他操作 (e.g., find the word Romans near countrymen) 不支持检索结果的排序 (即只返回较好的结果)14词项-文档(term-d

6、oc)的关联矩阵Antony and CleopatraJulius CaesarThe TempestHamletOthelloMacbethAntony110001Brutus110100Caesar110111Calpurnia010000Cleopatra100000mercy101111worser101110若某剧本包含某单词，则该位置上为1，否则为0BrutusBrutus AND CaesarCaesar BUT NOT CalpurniaCalpurnia 关联向量(incidence vectors) 关联矩阵的每一列都是 0/1向量，每个0/1都对应一个词项 给定查询Br

7、utus AND Caesar AND NOT Calpurnia 取出三个列向量 ，并对Calpurnia 的列向量求补，最后按位进行与操作 110100 AND 110111 AND 101111 = 100100. 16上述查询的结果文档 Antony and Cleopatra, Act III, Scene ii Agrippa Aside to DOMITIUS ENOBARBUS: Why, Enobarbus, When Antony found Julius Caesar dead, He cried almost to roaring; and he wept When a

8、t Philippi he found Brutus slain. Hamlet, Act III, Scene ii Lord Polonius: I did enact Julius Caesar I was killed i the Capitol; Brutus killed me.17IR中的基本假设 文档集Collection: 由固定数目的文档组成 目标: 返回与用户需求相关的文档并辅助用户来完成某项任务 相关性Relevance 主观的概念 反映对象的匹配程度 不同应用相关性不同18典型的搜索过程文档集文档集任务任务信息需求信息需求查询查询 自然语言描自然语言描述述结果结果搜索

9、搜索引擎引擎查询查询重构重构Get rid of mice in a politically correct wayInfo about removing micewithout killing them How do I trap mice alive?mouse trap是否转义?是否转义?是否转义?检索效果的评价 正确率(Precision) : 返回结果文档中正确的比例。如返回80篇文档，其中20篇相关，正确率1/4 召回率(Recall) : 全部相关文档中被返回的比例，如返回80篇文档，其中20篇相关，但是总的应该相关的文档是100篇，召回率1/5 正确率和召回率反映检索效果的两个

10、方面，缺一不可。 全部返回，正确率低，召回率100% 只返回一个非常可靠的结果，正确率100%，召回率低 将在后面介绍(有兴趣的可以先看)20大文档集 假定N = 1 百万篇文档(1M), 每篇有1000个词(1K) 假定每个词平均有6个字节(包括空格和标点符号) 那么所有文档将约占6GB 空间. 假定 词汇表的大小(即词项个数) M = 500K21词项-文档矩阵将非常大 矩阵大小为 500K x 1M=500G 但是该矩阵中最多有10亿(1G)个1 词项-文档矩阵高度稀疏(sparse). 稀疏矩阵 应该有更好的表示方式 比如我们仅仅记录所有1的位置22Why?倒排索引(Inverted

11、index) 对每个词项t, 记录所有包含t的文档列表. 每篇文档用一个唯一的 docID来表示，通常是正整数，如1,2,3 能否采用定长数组的方式来存储docID列表23BrutusBrutusCalpurniaCalpurniaCaesarCaesar1245616 57 1321241131 45173231文档14中加入单词CaesarCaesar时该如何处理时该如何处理? 17454101倒排索引(续) 通常采用变长表方式 磁盘上，顺序存储方式比较好，便于快速读取 内存中，采用链表或者可变长数组方式 存储空间/易插入之间需要平衡24DictionaryPostings按docID排序

12、 (原因后面再讲)PostingBrutusCalpurniaCaesar1245616 57 1321241131 4517323117454101词典倒排(记录)表倒排记录Tokenizer词条流FriendsRomansCountrymen倒排索引构建Linguistic modules修改后的词条friendromancountrymanIndexer倒排索引friendromancountryman24213161待索引文档Friends, Romans, countrymen.词条化工具语言分析工具索引构建过程: 词条序列 二元组I did enact JuliusCaesar I

13、 was killed i the Capitol; Brutus killed me.Doc 1So let it be withCaesar. The nobleBrutus hath told youCaesar was ambitiousDoc 2索引构建过程: 排序 按词项排序 然后每个词项按docID排序 索引构建的核心步骤索引构建的核心步骤索引构建过程: 词典 & 倒排记录表 某个词项在单篇文档中的多次出现会被合并 拆分成词典和倒排记录表两部分 每个词项出现的文档数目(doc. frequency, DF)会被加入为什么加入？后面会讲存储开销计算29指针词项及文档频率后续章节:如

14、何快速构建索引?如何减少存储开销?倒排索引docID表第一讲：布尔检索提纲30 信息检索概述信息检索概述 倒排索引倒排索引 布尔查询的处理布尔查询的处理第一讲：布尔检索假定索引已经构建好 如何利用该索引来处理查询? 后面会讲 如何处理不同类型的查询? 比如带通配符的查询 “信息*检索”31今天主要内容第一讲：布尔检索AND查询的处理 考虑如下查询（从简单的布尔表达式入手）: Brutus AND Caesar 在词典中定位 Brutus 返回对应倒排记录表(对应的docID) 在词典中定位Caesar 再返回对应倒排记录表 合并(Merge)两个倒排记录表，即求交集32128342481632

15、64123581321BrutusBrutusCaesarCaesar合并过程 每个倒排记录表都有一个定位指针，两个指针同时从前往后扫描, 每次比较当前指针对应倒排记录，然后移动某个或两个指针。合并时间为两个表长之和的线性时间333412824816326412358132112834248163264123581321BrutusBrutusCaesarCaesar28假定表长分别为x 和y, 那么上述合并算法的复杂度为 O(x+y)关键原因: 倒排记录表按照docID排序上述合并算法的伪代码描述34其它布尔查询的处理 OR表达式：Brutus OR Caesar 两个倒排记录表的并集 NO

16、T表达式： Brutus AND NOT Caesar 两个倒排记录表的减 一般的布尔表达式 (Brutus OR Caesar) AND NOT(Antony OR Cleopatra) 查询处理的效率问题！35查询优化 查询处理中是否存在处理的顺序问题？ 考虑n 个词项的 AND 对每个词项，取出其倒排记录表，然后两两合并BrutusCaesarCalpurnia123581621 342481632 6412813 16查询: Brutus AND Calpurnia AND Caesar36查询优化 按照表从小到大(即df从小到大)的顺序进行处理: 每次从最小的开始合并37这是为什么保

17、存df的原因之一相当于处理查询 (Calpurnia AND Brutus) AND Caesar.BrutusCaesarCalpurnia123581621 342481632 6412813 16更通用的优化策略 e.g., (madding OR crowd) AND (ignoble OR strife) 每个布尔表达式都能转换成上述形式(合取范式) 获得每个词项的df (保守)通过将词项的df相加，估计每个OR表达式对应的倒排记录表的大小 按照上述估计从小到大依次处理每个OR表达式.38布尔检索的优点 构建简单，或许是构建IR系统的一种最简单方式 在30多年中是最主要的检索工具 当

18、前许多搜索系统仍然使用布尔检索模型: 电子邮件、文献编目、Mac OS X Spotlight工具39布尔检索例子: WestLaw (付费用户数目)最大的商业化法律搜索服务引擎 (1975年开始提供服务; 1992年加入排序功能) 几十T数据，700,000用户 大部分用户仍然使用布尔查询 查询的例子: 有关对政府侵权行为进行索赔的诉讼时效(What is the statute of limitations in cases involving the federal tort claims act?） LIMIT! /3 STATUTE ACTION /S FEDERAL /2 TORT

19、 /3 CLAIM /3 = within 3 words, /S = in same sentence40布尔检索例子: WestLaw 另一个例子: 残疾人士能够进入工作场所的要求（Requirements for disabled people to be able to access a workplace） disabl! /p access! /s work-site work-place (employment /3 place 扩展的布尔操作符 很多专业人士喜欢使用布尔搜索 非常清楚想要查什么、能得到什么 但是这并不意味着布尔搜索其实际效果就很好.Google支持布尔查询 想查

20、关于2011年快女 6进5 比赛的新闻，用布尔表达式怎么构造查询？ (2011 OR 今年) AND (快乐女声 OR 快女 OR 快乐女生) AND (6进5 OR 六进五 OR 六 AND 进 AND 五) 表达式相当复杂，构造困难！ 不严格的话结果过多，而且很多不相关；非常严格的话结果会很少，漏掉很多结果。42第一讲：布尔检索布尔检索的缺点 布尔查询构建复杂，不适合普通用户。构建不当，检索结果过多或者过少 没有充分利用词项的频率信息 1 vs. 0 次出现 2 vs. 1次出现 3 vs. 2次出现, 通常出现的越多越好，需要利用词项在文档中的词项频率(term frequency, tf)信息 不能对检索结果进行排序43论文要求 内容 所讲原理的公安应用分析或研究 结构数据收集 web数据收集 连接分析 倒排索引 布尔检索 向量空间模型 业务流程与工作方法的改进分析与研究 案件分析业务流程 主要分析模式 舆情分析的业务流程44论文结构 标题 姓名 班级 学号