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

搜索引擎中的信息检索和链接分析技术 华中科技大学研究员朱会灿 2 Overview 简介排序网页作弊 Spamming 信息检索 IR 在Google的成功应用远景展望 3 Introduction History WWW出现 1992 Mosaic Netscape出现 1993 95 网络爬虫 Crawler 出现 1994 M Mauldin foundedLycos Yahoo成立 1994 网页目录搜索引擎出现1994 1996 InfoSeek Lycos Altavista Excite Inktomi Google创立 1996 98试图把搜索技术卖出去 没找到买主 都忙着办门户网站 portals 4 ThePipeline Crawling 循着链接下载网页Indexing 纪录哪个词在哪儿出现Ranking 从几十亿网页中找出跟用户查询最匹配的Serving 处理查询 生成结果网页 5 Ranking History 早期搜索引擎都是基于信息检索技术 IR 领域出现于1950年代主要着眼于文本检索主要使用统计方法来分析文本运用heuristics基于词的位置分配权重 靠开始或者在题目里比较好 多词查询时 这些词在文章中越近越好普通词不重要 e g the 的 6 InformationRetrieval IR TFxIDF TF Termfrequency 一个词在一篇文章中出现的次数IDF Inversedocumentfrequency 总文章数 含有这个词的文章数 乘积越高 则相应的文章对该词匹配越精确 这个词在这篇文章中出现的次数多 而且包含这个字的文章少 聚类 clustering 把相关的信息合到一起分类 classification 根椐某个标准 把内容归类 信息提取 extraction 从文本中提取关键词 7 Ranking DrawbacksofIR 对网页搜索 IR必要但不充分不能表达内容权威性 authority 在上的一片文章和在某个blog上重贴的版本得分一样不能表示webnavigation搜索ibm是在找可能看起来没有一篇IBM季度报告重要 8 Ranking LinkAnalysis 但是好在有链接 网上导航的工具表示目标网页重要对目标网页的推荐还描述目标网页 Anchortext 9 Ranking LinkAnalysis 链接分析 利用链接信息来判断网页重要性HubsandAuthorities JonKleinberg PageRank BrinandPage 10 HubsandAuthorities 权威 Authority 网页 最经常被指向的网页 中心 Hub 网页 有很多外向链接的网页 链接多有相关主题 只有指向最好的中心网页才是最好的权威网页 只有指向最好的权威网页才是最好的中心网页 HITS Hyperlink InducedTopicSearch BaseResults 11 HITS ProsandCons Pros 自动主体分组 如果一个检索词有多个意义 多组权威和中心网页自动识别 Apple对立的观点自动分开 房地产价格趋势 Cons 在线计算 长处理时间 只对小的索引有效 对极其明确范围的检索不太好 adobereader7 0 8 12 Pagerank PageRank 利用Web所拥有的庞大链接构造的特性来对网页重要性的排序 网页A指向网页B的链接被看作是A对B的支持投票投票数目影响页面的重要性 Pagerank不单单只看投票数 即链接数 重要性 高的页面所投的票的评价会更高Pagerank基于整个链接图离线计算 跟搜索词无关 计算非常高效 13 Pagerank B A C Pr B Pr A 4 Pr C 3M 链接矩阵 m i j 0如果i不指向j 1 i out i out是节点i的总链接数P pagerank向量 我们有 MP cP 14 Pagerank 假设一个网上冲浪者随机点击看到的网页链接 他到达某个网页的概率就是这个网页的PageRank值 如果一个网页没有外向链接怎么办 依照小概率 比如说 15 一个用户会停止点击链接 而将URL敲进地址框 或从个人爱好表里选取 个性化pageranks 具有明确主题的pageranks 15 AnchorText 描述目标网页的短句 XXX的个人主页 Googlesearchengine有些信息无用 Clickhere有些是恶意中伤 16 PutEverythingTogether 信息检索链接分析AnchorText上下文相关摘要秘密配料 17 Overview 简介排序网页作弊 Spamming 信息检索 IR 在Google的成功应用远景展望 18 ThereisValueinGettingRankedHigh Spam 网页作弊 通过欺诈搜索引擎使网页排序高于所应该得到的排序的行为 用户跟着搜索结果走钱跟着用户 spammers跟着钱 网页排名高 更多的销售 更多的广告显示和点击用户会那么容易上当受骗吗 19 WhatdoTheyClickOn 大多数用户只会点击前几个搜索结果很少用户会往下拖动浏览器去看其他搜索结果真正用户关心的只是在不需要往下拖动的可视区域极少用户去翻看下一页搜索结果 20 TheRealWorld SearchEngineSpam 搜索引擎作弊是怎么做的 21 TheRealWorld DefeatingIR 关键字堆砌和隐蔽技术网页爬虫在抓取网页时会声明自己是搜索引擎的抓取机器人作弊网站则给它一个使用了作弊技术优化过的页面而当用户访问这个页面时 看到的则是正常的页面 很容易被检测的作弊方法 我们只需要检测页面的关键字出现密度 22 TheRealWorld SearchEngineSpam 这类网页作弊也可检测 只需要使用自然语言处理 NLP 技术去检测网页内容与查询是否相关即可 23 TheRealWorld DefeatingIR NLP 24 TheRealWorld SearchEngineSpam 这时链接分析的作用就体现出来了 没有人愿意去链接到这些作弊的吧 25 TheRealWorld GettingLinks 过期域名一个合法域名的拥有者不想再续租它了网页作弊者买下这个域名 这时域名已经有了很多的链入的链接例如 链接描述的锚文字 anchortext TheWaronFreedomTheWaronFreedomHowandWhyAmericawasattackedTheWaronFreedom 26 交换链接 TheRealWorld GettingLinks 27 TheRealWorld GettingLinks 邮件列表 28 TheRealWorld GettingLinks 访客留言簿 29 TheRealWorld 如果说能找到可信第三方 只信任这些可信方的链接 只信任老师 只信任大学教授 只信任大学计算机系的教授 只信任拿到终身教职的计算机系教授 30 TheRealWorld P 计算机系的教授U 某大学 某学生X的简历 嘿 我们可使网页在Google上排名升高 31 TheRealWorld P 计算机系的教授U 某大学 学生Y的页面 存放在学校的网站上里面还有到卖地毯的网站的链接 32 TheRealWorld 巨大的商业利益总是充满诱惑的 33 TheRealWorld Anyalgorithmcanbeandwillbeattackedbyspammers that swhatkeepsthisjobinteresting 任何算法都会而且一定会被网页作弊者所攻破 这使得反作弊的工作会一直很有趣 不是么 34 TheRealWorld 魔高一尺 道高一丈 35 TheRealWorld 网页作弊是确实存在的问题不过大多数的搜索引擎还是有效的每天超过八亿次使用 所有的搜索引擎加在一起 我们内部的指标显示近年来我们反网页作弊的工作一直在大步向前但我们仍然需要警惕 36 ResearchQuestion 能否设计一个对 网页作弊 具有先天免疫力的搜索引擎 37 TheRealWorld 够酷吧 38 Overview 简介排序网页作弊 Spamming 信息检索 IR 在Google的成功应用远景展望 39 RelatedSearch 相关性和相似性分析 40 IR Google GoogleNews 聚类 41 IR Google ImageSearch 图片的标注 42 IR Google GoogleScholar 论文引用情况的分析 43 IR Google AdSense GoogleAdSense基于内容的广告 44 Overview 简介排序网页作弊 Spamming 信息检索 IR 在Google的成功应用远景展望 45 ThePer