《网络信息获取与情报分析技术(七)ppt课件》由会员分享，可在线阅读，更多相关《网络信息获取与情报分析技术(七)ppt课件（46页珍藏版）》请在金锄头文库上搜索。
1、网络情报获取分析技术 提纲 2 信息检索概述倒排索引布尔查询的处理 提纲 3 信息检索概述倒排索引布尔查询的处理 信息检索InformationRetrieval InformationRetrieval IR isfindingmaterial usuallydocuments ofanunstructurednature usuallytext thatsatisfiesaninformationneedfromwithinlargecollections usuallystoredoncomputers 信息检索是从大规模非结构化数据 通常是文本 的集合 通常保存在计算机上 中找出满足用
2、户信息需求的资料 通常是文档 的过程 Document 文档Unstructured 非结构化Informationneed 信息需求Collection 文档集 语料库 4 IRvs数据库 结构化vs非结构化数据 结构化数据即指 表 中的数据 5 Employee Manager Salary Smith Jones 50000 Chang Smith 60000 50000 Ivy Smith 数据库常常支持范围或者精确匹配查询 e g Salary 60000ANDManager Smith 非结构化数据 通常指自由文本允许关键词加上操作符号的查询更复杂的概念性查询 找出所有的有关西藏的
3、网页经典的检索模型一般都针对自由文本进行处理 6 半结构化数据 没有数据是完全无结构的李甲主页 半结构化查询TitlecontainsdataANDBulletscontainsearch 这里还没有提文本的语言结构 7 非结构化vs 结构化vs 半结构化 半结构化 Semi structured 李甲主页 8 传统信息检索vs 现代信息检索 传统信息检索主要关注非结构化 半结构化数据现代信息检索中也处理结构化数据 9 非结构化数据 文本 vs 结构化数据 数据库 1996年 10 数据量 市场规模 非结构化数据 文本 vs 结构化数据 数据库 2013年 11 数据量 市场规模 布尔检索 针
4、对布尔查询的检索 布尔查询是指利用AND OR或者NOT操作符将词项连接起来的查询信息AND检索信息OR检索信息AND检索ANDNOT教材Google的高级搜索 12 提纲 13 信息检索概述倒排索引布尔查询的处理 一个简单的例子 莎士比亚全集 莎士比亚的哪部剧本包含Brutus及Caesar但是不包含Calpurnia 布尔表达式为BrutusANDCaesarANDNOTCalpurnia 笨方法 从头到尾扫描所有剧本 对每部剧本判断它是否包含BrutusANDCaesar 同时又不包含Calpurnia笨方法为什么不好 速度超慢 特别是大型文档集 处理NOTCalpurnia并不容易 一
5、旦包含即可停止判断 不太容易支持其他操作 e g findthewordRomansnearcountrymen 不支持检索结果的排序 即只返回较好的结果 14 词项 文档 term doc 的关联矩阵 若某剧本包含某单词 则该位置上为1 否则为0 BrutusANDCaesarBUTNOTCalpurnia 关联向量 incidencevectors 关联矩阵的每一列都是0 1向量 每个0 1都对应一个词项给定查询BrutusANDCaesarANDNOTCalpurnia取出三个列向量 并对Calpurnia的列向量求补 最后按位进行与操作110100AND110111AND101111
6、100100 16 上述查询的结果文档 AntonyandCleopatra ActIII SceneiiAgrippa AsidetoDOMITIUSENOBARBUS Why Enobarbus WhenAntonyfoundJuliusCaesardead Hecriedalmosttoroaring andheweptWhenatPhilippihefoundBrutusslain Hamlet ActIII SceneiiLordPolonius IdidenactJuliusCaesarIwaskilledi theCapitol Brutuskilledme 17 IR中的基本假
7、设 文档集Collection 由固定数目的文档组成目标 返回与用户需求相关的文档并辅助用户来完成某项任务相关性Relevance主观的概念反映对象的匹配程度不同应用相关性不同 18 典型的搜索过程 文档集 任务 信息需求 查询 自然语言描述 结果 搜索引擎 查询重构 Getridofmiceinapoliticallycorrectway Infoaboutremovingmicewithoutkillingthem HowdoItrapmicealive mousetrap 检索效果的评价 正确率 Precision 返回结果文档中正确的比例 如返回80篇文档 其中20篇相关 正确率1 4
8、召回率 Recall 全部相关文档中被返回的比例 如返回80篇文档 其中20篇相关 但是总的应该相关的文档是100篇 召回率1 5正确率和召回率反映检索效果的两个方面 缺一不可 全部返回 正确率低 召回率100 只返回一个非常可靠的结果 正确率100 召回率低将在后面介绍 有兴趣的可以先看 20 大文档集 假定N 1百万篇文档 1M 每篇有1000个词 1K 假定每个词平均有6个字节 包括空格和标点符号 那么所有文档将约占6GB空间 假定词汇表的大小 即词项个数 M 500K 21 词项 文档矩阵将非常大 矩阵大小为500Kx1M 500G但是该矩阵中最多有10亿 1G 个1词项 文档矩阵高度
9、稀疏 sparse 稀疏矩阵应该有更好的表示方式比如我们仅仅记录所有1的位置 22 Why 倒排索引 Invertedindex 对每个词项t 记录所有包含t的文档列表 每篇文档用一个唯一的docID来表示 通常是正整数 如1 2 3 能否采用定长数组的方式来存储docID列表 23 Brutus Calpurnia Caesar 2 31 文档14中加入单词Caesar时该如何处理 174 54 101 倒排索引 续 通常采用变长表方式磁盘上 顺序存储方式比较好 便于快速读取内存中 采用链表或者可变长数组方式存储空间 易插入之间需要平衡 24 按docID排序 原因后面再讲 Posting
10、Brutus Calpurnia Caesar 2 31 174 54 101 词典 倒排 记录 表 倒排记录 倒排索引构建 待索引文档 Friends Romans countrymen 词条化工具 语言分析工具 索引构建过程 词条序列 二元组 IdidenactJuliusCaesarIwaskilledi theCapitol Brutuskilledme Doc1 SoletitbewithCaesar ThenobleBrutushathtoldyouCaesarwasambitious Doc2 索引构建过程 排序 按词项排序然后每个词项按docID排序 索引构建的核心步骤 索引构
11、建过程 词典 倒排记录表 某个词项在单篇文档中的多次出现会被合并拆分成词典和倒排记录表两部分每个词项出现的文档数目 doc frequency DF 会被加入 为什么加入 后面会讲 存储开销计算 29 指针 词项及文档频率 后续章节 如何快速构建索引 如何减少存储开销 倒排索引 docID表 第一讲 布尔检索 提纲 30 信息检索概述倒排索引布尔查询的处理 第一讲 布尔检索 假定索引已经构建好 如何利用该索引来处理查询 后面会讲 如何处理不同类型的查询 比如带通配符的查询 信息 检索 31 今天主要内容 第一讲 布尔检索 AND查询的处理 考虑如下查询 从简单的布尔表达式入手 BrutusAN
12、DCaesar在词典中定位Brutus返回对应倒排记录表 对应的docID 在词典中定位Caesar再返回对应倒排记录表合并 Merge 两个倒排记录表 即求交集 32 128 34 Brutus Caesar 合并过程 每个倒排记录表都有一个定位指针 两个指针同时从前往后扫描 每次比较当前指针对应倒排记录 然后移动某个或两个指针 合并时间为两个表长之和的线性时间 33 128 34 2 假定表长分别为x和y 那么上述合并算法的复杂度为O x y 关键原因 倒排记录表按照docID排序 上述合并算法的伪代码描述 34 其它布尔查询的处理 OR表达式 BrutusORCaesar两个倒排记录表的
13、并集NOT表达式 BrutusANDNOTCaesar两个倒排记录表的减一般的布尔表达式 BrutusORCaesar ANDNOT AntonyORCleopatra 查询处理的效率问题 35 查询优化 查询处理中是否存在处理的顺序问题 考虑n个词项的AND对每个词项 取出其倒排记录表 然后两两合并 Brutus Caesar Calpurnia 13 16 查询 BrutusANDCalpurniaANDCaesar 36 查询优化 按照表从小到大 即df从小到大 的顺序进行处理 每次从最小的开始合并 37 这是为什么保存df的原因之一 相当于处理查询 CalpurniaANDBrutus
14、 ANDCaesar Brutus Caesar Calpurnia 13 16 更通用的优化策略 e g maddingORcrowd AND ignobleORstrife 每个布尔表达式都能转换成上述形式 合取范式 获得每个词项的df 保守 通过将词项的df相加 估计每个OR表达式对应的倒排记录表的大小按照上述估计从小到大依次处理每个OR表达式 38 布尔检索的优点 构建简单 或许是构建IR系统的一种最简单方式在30多年中是最主要的检索工具当前许多搜索系统仍然使用布尔检索模型 电子邮件 文献编目 MacOSXSpotlight工具 39 布尔检索例子 WestLaw 付费用户数目 最大的
15、商业化法律搜索服务引擎 1975年开始提供服务 1992年加入排序功能 几十T数据 700 000用户大部分用户仍然使用布尔查询查询的例子 有关对政府侵权行为进行索赔的诉讼时效 Whatisthestatuteoflimitationsincasesinvolvingthefederaltortclaimsact LIMIT 3STATUTEACTION SFEDERAL 2TORT 3CLAIM 3 within3words S insamesentence 40 布尔检索例子 WestLaw 另一个例子 残疾人士能够进入工作场所的要求 Requirementsfordisabledpeop
16、letobeabletoaccessaworkplace disabl paccess swork sitework place employment 3place扩展的布尔操作符很多专业人士喜欢使用布尔搜索非常清楚想要查什么 能得到什么但是这并不意味着布尔搜索其实际效果就很好 Google支持布尔查询 想查关于2011年快女6进5比赛的新闻 用布尔表达式怎么构造查询 2011OR今年 AND 快乐女声OR快女OR快乐女生 AND 6进5OR六进五OR六AND进AND五 表达式相当复杂 构造困难 不严格的话结果过多 而且很多不相关 非常严格的话结果会很少 漏掉很多结果 42 第一讲 布尔检索 布尔检索的缺点 布尔查询构建复杂 不适合普通用户 构建不当 检索结果过多或者过少没有充分利用词项的频率信息1vs 0次出现2vs 1次出现3vs 2次出现 通常出现的越多越好 需要利用词项在文档中的词项频率 termfrequency tf 信息不能对检索结果进行排序 43 论文要求 内容所讲原理的公安应用分析或研究结构数据收集web数据收集连接分析倒排索引布尔检索向量空间模型业务流程与工作方法的
