Download presentation
Presentation is loading. Please wait.
1
检索 林琛 博士、副教授
2
本讲要点 从实用角度看搜索引擎架构 检索排序模型 数据获取：爬虫 查询处理：布尔检索与查询扩展 数据索引：倒排表 排序模型 检索评价
向量空间模型与Rocchio查询扩展 语言模型与查询扩展（简略）
3
检索与查询 查询 检索 结构化数据（数据库） 查询语言 返回对象是记录 结果集是确定的 排序由用户指定 注重效率
自然语言/html等无结构或半结构化数据 自然语言 返回对象可以是文档/人/产品…… 结果集是不确定的 一般根据相关度排序 更注重效果 现在数据库查询也发展fuzzy search等，和信息检索交叉
4
构建一个Web检索系统 构建一个手机智能导购系统 得到电商的产品信息库及在线用户评论数据 用户输入对手机的消费需求
在数据中找到符合需求的对象 返回并排序
5
数据采集：爬虫 起始页面：种子 爬虫基本流程 京东，新蛋，亚马逊，苏宁…… 初始化采集URL种子队列； 重复如下过程：
京东入口，链往 HTC New One ， Nokia Lumia等 HTC New One链往更多网页 HTC New One包含了该手机的评论（需要保存该页面） 爬虫基本流程 初始化采集URL种子队列； 重复如下过程： 从队列中取出URL 下载并分析网页 从网页中抽取更多的URL 将这些URL放到队列中
6
爬虫的实际问题 规模问题 礼貌性问题 鲁棒性问题 新鲜性问题 如果要在一个月内采集20,000,000,000个页面
那么必须要在一秒内大概采集 8000个网页! 由于我们采集的网页可能重复、不可下载或者是作弊网页，实际上可能需要更快的采集速度才能达到上述指标 必须采取分布式设计 礼貌性问题 不要高频率采集某个网站 仅仅采集robots.txt所规定的可以采集的网页 鲁棒性问题 能够处理采集器陷阱、检测重复页面、超大页面、超大网站、动态页面等问题 新鲜性问题 必须要定期更新或者重采 优先处理高质量网页 返回
7
查询处理 词包模型 布尔检索 时尚轻薄的手机 时尚>轻薄 时尚 OR 轻薄 AND 手机 AND NOT 电脑
用户是否正确的表达了信息需求？ 用户是否完整的表达了信息需求？
8
查询扩展 某篇文档 d 包含“时髦”，但是不包含 “时尚” 某篇文档d’包含“超级本”，但是不包含“轻薄笔记本” 查询扩展
基于全局建立同义词词典扩展查询（“时髦”“时尚”同义） 基于局部的相关反馈（在该查询下“超级”与“轻薄”相关） 用户提交一个(简短的)查询 搜索引擎返回一系列文档 （用户）将部分返回文档标记为相关的，将部分文档标记为不相关的 搜索引擎根据标记结果计算得到信息需求的一个新查询表示，希望该表示好于初始的查询表示 搜索引擎对新查询进行处理，返回新结果 无相关反馈的叫做ad hoc检索 循环 返回
9
索引 笨方法：从头到尾扫描所有评论，对每个评论判断它是否包含时尚 AND 轻薄，同时又不包含笔记本电脑 倒排索引
对每个词项t, 记录所有包含t的对象列表. 一个对象通常是一个文档，每篇文档用一个唯一的 docID来表示，通常是正整数，如1,2,3…
10
倒排索引进行布尔查询 在词典中定位“时尚”（B树） 在词典中定位“轻薄” 合并(Merge)两个倒排记录表 倒排记录 按docID排序
再返回对应倒排记录表 合并(Merge)两个倒排记录表 每个倒排记录表都有一个定位指针，两个指针同时从前往后扫描, 每次比较当前指针对应倒排记录，然后移动某个或两个指针。合并时间为两个表长之和的线性时间 OR：两个倒排记录的并集；AND：交集；NOT：剪 1 3 4 6 31 67 91 100 123 1：时尚 8 词典 2：轻薄 6 3：手机 5 2 4 6 16 31 倒排记录 按docID排序
11
查询优化 每个查询都写成如下形式的合取范式 对每个子句 按照上述估计从小到大依次处理每个子句
(a OR b) AND (c NOT d) AND (e OR f) 对每个子句 获得每个词项的df (保守)通过将词项的df相加，估计每个子句对应的倒排记录表的大小 按照上述估计从小到大依次处理每个子句
12
索引的预处理 努比亚手机 问题1：web检索的源数据是html格式，需要哪些部分的内容？是否有偏重？
<html xmlns=“ <head> <title>【努比亚Z5 mini】努比亚（nubia）小牛 Z5 mini 3G手机（黑色）WCDMA/TD-SCDMA/CDMA2000【行情 报价 价格 评测】-京东商城</title> <script>var jdpts = new Object(); jdpts._st = new Date().getTime();</script> <meta http-equiv=“Content-Type” content=“text/html; charset=gb2312” /> <meta name=“keywords” content=“nubiaZ5 mini,努比亚Z5 mini,努比亚Z5 mini手机报价,nubiaZ5 mini报价”/> <meta name=“description” content=“【努比亚Z5 mini】京东JD.COM提供努比亚Z5 mini正品行货，全国的价格最低，并包括nubiaZ5 mini手机网购指南，以及努比亚Z5 mini图片、Z5 mini参数、Z5 mini评论、Z5 mini心得、Z5 mini技巧等信息，网购努比亚Z5 mini手机上京东,放心又轻松" /> Mobile phone (also known as a cellular phone, cell phone, and a hand phone) are devices that can make and receivetelephone calls over a radio link while moving around a wide geographic area. It does so by connecting to a cellular networkprovided by a mobile phone operator, allowing access to the public telephone network. By contrast, a cordless telephone is used only within the short range of a single, private base station. 问题2：词项的边界在哪里？以字为单元还是词语？英语和中文相同吗？ Devices=device?
13
索引 文档分析 确定索引单位 文档格式识别 文档语言识别 文档编码识别 词条化(Tokenization) 分词 （去除停用词） 归一化
建立词典 倒排记录表 记录位置和词组
14
处理短语查询 输入查询作为一个短语整体，比如 中国科学院” 解决方案 “我去了中国 农业 科学院”（不是答案）
有证据表明，用户很容易理解短语查询的概念，这也是很多搜索引擎”高级搜索”中比较成功的一个功能。 但是很多查询是隐式短语查询information retrieval textbook [information retrieval] textbook 解决方案 双词索引(n-gram)：每两个连续的词组成词对(作为短语)来索引 倒排索引
15
带位置信息的索引 短语查询 <term, 出现term的文档篇数； doc1: 位置1, 位置2 … ;
等等> 短语查询 对每个词项，抽出其对应的倒排记录表 合并<docID:位置 >表 考虑前后位置之间的距离不大于某个值
16
排序 布尔检索没有排序 信息过载 用户只希望看到一些而不是成千上万的结果 信息检索中，排序非常重要
17
向量空间模型 查询看作一个向量 每篇文档为一个向量 向量夹角 每篇文档为一个向量 Term1:weight1 权重 t 在 d 中的词频
反映t的信息量：t在语料C中的文档频率倒数 词项的tf-idf权重是tf权重和idf权重的乘积
18
向量空间模型中的查询扩展：Rocchio
向量空间模型中将文档表示成高维空间中的点 一系列点的中心：质心
19
Rocchio算法原理 （伪）相关反馈 最优查询是将相关文档和不相关文档分得最开 相关文档集Dr，不相关文档集Dnr
不能分开相关和不相关文档 Ur-Unr 区分效果很好
20
实际使用的Rocchio算法 实际使用中由于无法知道所有的相关和不相关文档 SMART系统1971年使用
一旦出现负权重即设为0.因为在向量空间模型中，权重为负是没有意义的。 正反馈价值往往大于负反馈如β = 0.75, γ = 0.25.甚至只允许正反馈，即γ=0 qm: 修改后的查询; q0: 原始查询; Dr 、Dnr : 已知的相关和不相关文档集合；α, β, γ: 权重
21
语言模型 文档模型：词项的分布 文档：样本 查询：样本 查询似然概率 证监会 微博
中国证券监督管理委员会（简称证监会）官方微博10月15日在腾讯微博开通，是证监会信息公开的又一重要平台。证监会将第一时间通过微博这一新媒体渠道，向社会公众公开关于全国证券期货市场的重要信息，维护市场公开、公平、公正，维护投资者特别是中小投资者合法权益，促进资本市场健康发展。 证监会开微博
22
估计MD 多项式模型：D是抛1个L面的骰子抛|D|次生成的，将每次朝上的那面对应的词项集合起来便生成文本D。 最大似然估计：
出现次数为0的词语 Jelinek-Mercer(JM)，0≤λ≤1 Dirichlet Priors(Dir) Absolute Discounting(Abs)
23
语言模型中的查询扩展 相关模型 查询：语言模型->样本 相关文档的集合：语言模型->样本集
24
信息检索的评价（1） 不考虑结果中的序 准确率 召回率 P = TP / ( TP + FP ) R = TP / ( TP + FN )
召回率 P = TP / ( TP + FP ) R = TP / ( TP + FN )
25
信息检索评价（2） 准确率和召回率的trade-off 允许准确率和召回率的折中（通常取调和平均数）
26
信息检索的评价（3） 考虑结果中的序 平均正确率(Average Precision, AP)：对不同召回率点上的正确率进行平均
结果1 结果2 结果3 结果k 结果N 信息检索的评价（3） 考虑结果中的序 平均正确率(Average Precision, AP)：对不同召回率点上的正确率进行平均 未插值的AP: 某个查询Q共有6个相关结果，某系统排序返回了5篇相关文档，其位置分别是第1，第2，第5，第10，第20位，则AP=(1/1+2/2+3/5+4/10+5/20+0)/6 多个查询的AP的平均值称为系统的MAP(Mean AP) MAP是IR领域使用最广泛的指标之一 MRR(Mean Reciprocal Rank)：（第一个）答案在结果中的排序的倒数作为它的准确度 对所有的查询取平均。
27
信息检索评价（4） 考虑结果和答案中的序 假设答案中被划分为若干个等级 最好情况下结果的排序 计算（NDCG@真实结果的位置rank）
每个等级有分值（线性/指数） 最好情况下结果的排序 假定2个3等，1个2等，4个1等 则结果[ ] 增益(gain)：赢得等级的分值 折算增益（discounted gain）一般情况下用户会优先点选排在前面的搜索结果，结果分值x折算因子= log2/log(1+rank) 折算累积增益（discounted cumulative gain）加上真实结果中排在前面的累计增益 归一化（normalized discounted cumulative gain）：除以最好情况该位置的累计增益 Pooling法产生的答案 非常相关：5/25-1 相关：4/24-1 中立： 不太相关： 不相关：
28
信息检索的评价：例子 结果 评价 分值 文档 Highly relevant 10 1,6 Relevant 1 2,5,7
Not relevant 3,4,8,9,10 排序 文档 1 2 3 4 5 6 8 7 9 10 DCG NDCG 1 1/10=0.1 1+10x0.63 7.3/16.3 7.3 7.3/16.8 7.73/17.23 Relevance judgement 相关度评价 指标 Highly relevant Relevant 2/5=0.4 4/5=0.8 F-score P:0.4,R:1 = 0.286 P:0.8,R:0.8 = 0.4 MAP (1+1/5)/2=0.6 (1+1/2+1/4+1/5)/5=0.39 MRR ½=0.5 1/1=1 NDCG （3）MAP （4）MRR （5）NDCG
Similar presentations
