搜索引擎中的信息检索和链接分析技术.ppt

1、搜索引擎中的信息检索和链接分析技术,3,Overview,简介 排序 网页作弊(Spamming) 信息检索(IR) 在 Google 的成功应用 远景展望,4,Introduction: History,WWW 出现 (1992) Mosaic/Netscape 出现 (1993-95) 网络爬虫(Crawler)出现 (1994): M. Mauldin (founded Lycos) Yahoo 成立: 1994, 网页目录 搜索引擎出现 1994-1996 (InfoSeek, Lycos, Altavista, Excite, Inktomi, ) Google 创立: 1996-9

2、8 试图把搜索技术卖出去。 没找到买主。都忙着办门户网站(portals),5,The Pipeline,Crawling: 循着链接下载网页 Indexing: 纪录哪个词在哪儿出现 Ranking: 从几十亿网页中找出跟用户查询最匹配的 Serving: 处理查询，生成结果网页,6,Ranking: History,早期搜索引擎都是基于信息检索技术 (IR) 领域出现于 1950 年代 主要着眼于文本检索 主要使用统计方法来分析文本 运用heuristics 基于词的位置分配权重(靠开始或者在题目里比较好) 多词查询时，这些词在文章中越近越好 普通词不重要 (e.g. the, 的),7,

3、Information Retrieval (IR),TF x IDF: TF (Term frequency): 一个词在一篇文章中出现的次数 IDF (Inverse document frequency): 总文章数/(含有这个词的文章数) 乘积越高，则相应的文章对该词匹配越精确：这个词在这篇文章中出现的次数多，而且包含这个字的文章少。 聚类(clustering): 把相关的信息合到一起 分类(classification): 根椐某个标准，把内容归类。 信息提取(extraction): 从文本中提取关键词,8,Ranking: Drawbacks of IR,对网页搜索：IR 必要

4、但不充分 不能表达内容权威性( authority) 在上的一片文章和在 某个blog 上重贴的版本得分一样 不能表示 web navigation 搜索 ibm 是在找 可能看起来没有一篇IBM季度报告重要,9,Ranking: Link Analysis,但是好在有链接 网上导航的工具 表示目标网页重要 对目标网页的推荐 还描述目标网页 (Anchor text),10,Ranking: Link Analysis,链接分析：利用链接信息来判断网页重要性 Hubs and Authorities (Jon Kleinberg) PageRank (Brin and Page),11,Hub

5、s and Authorities,权威(Authority)网页: 最经常被指向的网页: , 中心(Hub) 网页: 有很多外向链接的网页。链接多有相关主题: 只有指向最好的中心网页才是最好的权威网页。只有指向最好的权威网页才是最好的中心网页。 HITS (Hyperlink-Induced Topic Search):,Base Results,12,HITS: Pros and Cons,Pros: 自动主体分组: 如果一个检索词有多个意义，多组权威和中心网页自动识别：Apple 对立的观点自动分开: 房地产价格趋势. Cons: 在线计算:长处理时间, 只对小的索引有效. 对极其明确范

6、围的检索不太好: adobe reader 7.0.8,13,Pagerank,PageRank: 利用 Web 所拥有的庞大链接构造的特性来对网页重要性的排序。 网页A指向网页B的链接被看作是A对B的支持投票 投票数目影响页面的重要性。 Pagerank 不单单只看投票数(即链接数) “重要性”高的页面所投的票的评价会更高 Pagerank 基于整个链接图离线计算，跟搜索词无关。计算非常高效,14,Pagerank,B,A,C,Pr(B) = Pr(A)/4 + Pr(C)/3 M：链接矩阵: m(i, j) = 0 如果 i 不指向 j; = 1/i_out， i_out 是 节点 i 的

7、总链接数 P：pagerank向量, 我们有： MP=cP,15,Pagerank,假设一个网上冲浪者随机点击看到的网页链接，他到达某个网页的概率就是这个网页的 PageRank 值。 如果一个网页没有外向链接怎么办? - 依照小概率, 比如说， 15%, 一个用户会停止点击链接，而将URL敲进地址框 (或从个人爱好表里选取) 个性化 pageranks, 具有明确主题的 pageranks,16,Anchor Text,描述目标网页的短句: XXX 的个人主页, Google search engine 有些信息无用： Click here 有些是恶意中伤,17,Put Everything

8、 Together,信息检索 链接分析 Anchor Text 上下文相关摘要 秘密配料,18,Overview,简介 排序 网页作弊(Spamming) 信息检索(IR) 在 Google 的成功应用 远景展望,19,There is Value in Getting Ranked High,Spam(网页作弊): 通过欺诈搜索引擎使网页排序高于所应该得到的排序的行为。 用户跟着搜索结果走 钱跟着用户 spammers 跟着钱 网页排名高 更多的销售，更多的广告显示和点击 用户会那么容易上当受骗吗?,20,What do They Click On,大多数用户只会点击前几个搜索结果 很少用户

9、会往下拖动浏览器去看其他搜索结果 真正用户关心的只是在不需要往下拖动的可视区域 极少用户去翻看下一页搜索结果,21,The Real World: Search Engine Spam,搜索引擎作弊是怎么做的？,22,The Real World: Defeating IR,关键字堆砌 和 隐蔽技术 网页爬虫在抓取网页时会声明自己是搜索引擎的抓取机器人 作弊网站则给它一个使用了作弊技术优化过的页面 而当用户访问这个页面时，看到的则是正常的页面,很容易被检测的作弊方法: 我们只需要检测页面的关键字出现密度,23,The Real World: Search Engine Spam,这类网页作弊也

10、可检测 只需要使用自然语言处理(NLP)技术去检测网页内容与查询是否相关即可,24,The Real World: Defeating IR/NLP,25,The Real World: Search Engine Spam,这时链接分析的作用就体现出来了: 没有人愿意去链接到这些作弊的吧。,26,The Real World: Getting Links,过期域名 一个合法域名的拥有者不想再续租它了 网页作弊者买下这个域名，这时域名已经有了很多的链入的链接 例如, 链接描述的锚文字(anchor text): The War on Freedom The War on Freedom How

11、 and Why America was attacked The War on Freedom,27,交换链接,The Real World: Getting Links,28,The Real World: Getting Links,邮件列表,29,The Real World: Getting Links,访客留言簿,30,The Real World,如果说能找到可信第三方，只信任这些可信方的链接 只信任老师 只信任大学教授 只信任大学计算机系的教授 只信任拿到终身教职的计算机系教授,31,The Real World,P: 计算机系的教授 U: 某大学,某学生X的简历,嘿，我们可使

12、网页在Google上排名升高,32,The Real World,P: 计算机系的教授 U: 某大学,学生Y的页面,存放在学校的网站上 里面还有到卖地毯的网站的链接,33,The Real World,巨大的商业利益总是充满诱惑的,34,The Real World,Any algorithm can be and will be attacked by spammers thats what keeps this job interesting,任何算法都会而且一定会被网页作弊者所攻破 这使得反作弊的工作会一直很有趣，不是么？,35,The Real World,魔高一尺，道高一丈,36,T

13、he Real World,网页作弊是确实存在的问题 不过大多数的搜索引擎还是有效的 每天超过八亿次使用(所有的搜索引擎加在一起） 我们内部的指标显示 近年来我们反网页作弊的工作一直在大步向前 但我们仍然需要警惕,37,Research Question,能否设计一个对“网页作弊”具有先天免疫力的搜索引擎？,38,The Real World,够酷吧,39,Overview,简介 排序 网页作弊(Spamming) 信息检索(IR) 在 Google 的成功应用 远景展望,40,Related Search,相关性和 相似性分析,41,IRGoogle: Google News,聚类,42,IRGoogle: Image Search,图片的标注,43,IRGoogle: Google Scholar,论文引用情况的分析,44,IRGoogle: AdSense,Google AdSense 基于内容的广告,45,Overview,简介 排序 网页作弊(Spamming) 信息检索(IR) 在 Google 的成功应用 远景展望,46,The P