《数据库应用与设计-非结构化数据处理》由会员分享，可在线阅读，更多相关《数据库应用与设计-非结构化数据处理（173页珍藏版）》请在金锄头文库上搜索。
1、第5章 非结构化数据处理 IR 布尔检索 倒排表 模糊检索 相似性 TFIDF 提纲 信息检索概述信息检索概述 倒排索引倒排索引 布尔查询的处理布尔查询的处理 信息检索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 stored on computers
2、 信息检索是从大规模非结构化数据 通常是文本 的集合 通常保信息检索是从大规模非结构化数据 通常是文本 的集合 通常保 存在计算机上 中找出满足用户信息需求的资料 通常是文档 的存在计算机上 中找出满足用户信息需求的资料 通常是文档 的 过程 过程 Document 文档文档 Unstructured 非结构化非结构化 Information need 信息需求信息需求 Collection 文档集 语料库文档集 语料库 3 IR VS数据库 结构化 VS 非结构化 数据 结构化数据即指 表 中的数据结构化数据即指 表 中的数据 Employee Manager Salary Smith Jo
3、nes 50000 Chang Smith 60000 50000 Ivy Smith 数据库常常支持范围或者精确匹配查询 e g Salary 60000 AND Manager Smith 非结构化数据 通常指自由文本通常指自由文本 允许允许 关键词加上操作符号的查询 更复杂的 概念性查询 找出所有的有关药物滥用 drug abuse 的网页 经典的检索模型一般都针对自由文本进行处理经典的检索模型一般都针对自由文本进行处理 半结构化数据 没有数据是完全无结构的没有数据是完全无结构的 李甲主页李甲主页 半结构化查询半结构化查询 Title contains data AND Bullets
4、contain search 这里还没有提文本的语言结构 非结构化数据 文本 VS 结构化数据 数据库 1996年 0 20 40 60 80 100 120 140 160 180 200 Data volumeMarket Cap Unstructured Structured 数据量 市场规模 非结构化数据 文本 VS 结构化数据 数据库 2009年 数据量 市场规模 布尔检索 针对布尔查询的检索 布尔查询是指利用 AND OR 或者 NOT 操作符将词项 连接起来的查询 信息 AND 检索 信息 OR 检索 信息 AND 检索 AND NOT 教材 提纲 信息检索概述信息检索概述 倒排
5、索引倒排索引 布尔查询的处理布尔查询的处理 一个简单的例子 莎士比亚全集 莎士比亚的哪部剧本包含莎士比亚的哪部剧本包含Brutus及及Caesar但是不包含但是不包含Calpurnia 布尔表达式为布尔表达式为 Brutus AND Caesar AND NOT Calpurnia 笨方法 笨方法 从头到尾扫描所有剧本 对每部剧本判断它是否包含从头到尾扫描所有剧本 对每部剧本判断它是否包含 Brutus AND Caesar 同时又不包含 同时又不包含Calpurnia 笨方法为什么不好笨方法为什么不好 速度超慢 特别是大型文档集 处理NOT Calpurnia 并不容易 一旦包含即可停止判断
6、 不太容易支持其他操作 e g find the word Romans near countrymen 不支持检索结果的排序 即只返回较好的结果 词项 文档 TERM DOC 的关联矩阵 Antony and CleopatraJulius CaesarThe TempestHamletOthelloMacbeth Antony110001 Brutus110100 Caesar110111 Calpurnia010000 Cleopatra100000 mercy101111 worser101110 若某剧本包含某单 词 则该位置上为1 否则为0 BrutusBrutus AND Cae
7、sarCaesar BUT NOT CalpurniaCalpurnia 关联向量 INCIDENCE VECTORS 关联矩阵的每一列都是关联矩阵的每一列都是 0 1向量 每个向量 每个0 1都对应一个词项都对应一个词项 给定查询给定查询Brutus AND Caesar AND NOT Calpurnia 取出三个列向量取出三个列向量 并对 并对Calpurnia 的列向量求补 最后按位进行的列向量求补 最后按位进行 与操作与操作 110100 AND 110111 AND 101111 100100 上述查询的结果文档 Antony and Cleopatra Act III Scene
8、 ii Agrippa Aside to DOMITIUS ENOBARBUS Why Enobarbus When Antony found Julius Caesar dead He cried almost to roaring and he wept When at 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 IR中的基本假设 文档集文档集Collecti
9、on 由固定数目的文档组成由固定数目的文档组成 目标目标 返回与用户需求相关的文档并辅助用户来完成某项任务返回与用户需求相关的文档并辅助用户来完成某项任务 相关性相关性Relevance 主观的概念 反映对象的匹配程度 不同应用相关性不同 典型的搜索过程 文档集文档集 任务任务 信息需求信息需求 查询查询 自然语言描自然语言描 述述 结果结果 搜索搜索 引擎引擎 查询查询 重构重构 Get rid of mice in a politically correct way Info about removing mice without killing them How do I trap mi
10、ce alive mouse trap 是否转义 是否转义 是否转义 检索效果的评价 正确率正确率 Precision 返回结果文档中正确的比例 如返回返回结果文档中正确的比例 如返回80篇文篇文 档 其中档 其中20篇相关 正确率篇相关 正确率1 4 召回率召回率 Recall 全部相关文档中被返回的比例 如返回全部相关文档中被返回的比例 如返回80篇文档 篇文档 其中其中20篇相关 但是总的应该相关的文档是篇相关 但是总的应该相关的文档是100篇 召回率篇 召回率1 5 正确率和召回率反映检索效果的两个方面 缺一不可 正确率和召回率反映检索效果的两个方面 缺一不可 全部返回 正确率低 召回
11、率100 只返回一个非常可靠的结果 正确率100 召回率低 大文档集 假定假定N 1 百万篇文档百万篇文档 1M 每篇有每篇有1000个词个词 1K 假定每个词平均有假定每个词平均有6个字节个字节 包括空格和标点符号包括空格和标点符号 那么所有文档将约占6GB 空间 假定假定 词汇表的大小词汇表的大小 即词项个数即词项个数 M 500K 词项 文档矩阵将非常大 矩阵大小为矩阵大小为 500K x 1M 500G 但是该矩阵中最多有但是该矩阵中最多有10亿亿 1G 个个1 词项 文档矩阵高度稀疏 sparse 稀疏矩阵 应该有更好的表示方式应该有更好的表示方式 比如我们仅仅记录所有1的位置 Wh
12、y 倒排索引 INVERTED INDEX 对每个词项对每个词项t 记录所有包含记录所有包含t的文档列表的文档列表 每篇文档用一个唯一的 docID来表示 通常是正整数 如 1 2 3 能否采用定长数组的方式来存储能否采用定长数组的方式来存储docID列表列表 BrutusBrutus CalpurniaCalpurnia CaesarCaesar 1 2 4 5 6 16 57 132 1 2 4 11 31 45 173 2 31 文档14中加入单词CaesarCaesar时该如何处理时该如何处理 174 54 101 倒排索引 续 通常采用变长表方式通常采用变长表方式 磁盘上 顺序存储方
13、式比较好 便于快速读取 内存中 采用链表或者可变长数组方式 存储空间 易插入之间需要平衡 Dictionary Postings 按docID排序 原因后面再讲 Posting Brutus Calpurnia Caesar 1 2 4 5 6 16 57 132 1 2 4 11 31 45 173 2 31 174 54 101 词典 倒排 记录 表 倒排记录 Tokenizer 词条流 Friends Romans Countrymen 倒排索引构建 Linguistic modules 修改后的词条 friend roman countryman Indexer 倒排索引 friend
14、 roman countryman 2 4 2 13 16 1 More on these later 待索引文档 Friends Romans countrymen 词条化工具 语言分析工具 索引构建过程 词条序列 二元组二元组 I did enact Julius Caesar I was killed i the Capitol Brutus killed me Doc 1 So let it be with Caesar The noble Brutus hath told you Caesar was ambitious Doc 2 索引构建过程 排序 按词项排序按词项排序 然后每个
15、词项按docID排序 索引构建的核心步骤索引构建的核心步骤 索引构建过程 词典 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 3 CLAIM 3 within 3 words S in same sent
16、ence 布尔检索例子 WESTLAW HTTP WWW WESTLAW COM 另一个例子另一个例子 残疾人士能够进入工作场所的要求 Requirements for disabled people to be able to access a workplace disabl p access s work site work place employment 3 place 扩展的布尔操作符扩展的布尔操作符 很多专业人士喜欢使用布尔搜索很多专业人士喜欢使用布尔搜索 非常清楚想要查什么 能得到什么 但是这并不意味着布尔搜索其实际效果就很好但是这并不意味着布尔搜索其实际效果就很好 GOOGLE支持布尔查询 想查关于想查关于2011年快女年快女 6进进5 比赛的新闻 用布尔表达式怎么构造查比赛的新闻 用布尔表达式怎么构造查 询 询 2011 OR 今年今年 AND 快乐女声快乐女声 OR 快女快女 OR 快乐女生快乐女生 AND 6进进 5 OR 六进五六进五 OR 六六 AND 进进 AND 五五 表达式相当复杂 构造困难 表达式相当复杂 构造困难 不严格的话结果过多 而且很多不相关
