去伪存真去粗取精页面质量评估及其在网络信息检索中的.ppt
去伪存真 去粗取精页面质量评估及其在网络信息检索中的应用,马少平 刘奕群清华大学计算机科学与技术系智能技术与系统国家重点实验室2006年7月，山东，济南,去伪存真 去粗取精,问题背景页面质量评估的相关工作概述高质量页面的查询无关特征分析基于学习的页面质量评估算法应用展望,去伪存真 去粗取精,问题背景页面质量评估的相关工作概述高质量页面的查询无关特征分析基于学习的页面质量评估算法应用展望,问题背景,World Wide Web的出现与发展,38年,13年,4年,1994年个人浏览器诞生，到1998年用户超过5000万人,问题背景,Web蕴含着多少信息？How Much Info 工程由Intel,Microsoft,HP,EMC等公司赞助，UC Berkeley大学完成2002年世界上共产生了5Exabyte的数据，其中92%的信息存储于电子介质相当于人类历史上所有说过的话语所包含的信息量的总和大部分存储于Web中，构成了Web中超过150Billion的网络页面,问题背景,Web的发展带来了什么？信息数量的急剧膨胀知识的获取空前简单与繁荣Information is no longer a scarce resource-attention is.(注意力，而不是信息，才是这个时代所稀缺的资源)(纽约时报，2005年10月16日)在信息化时代，知识实际上已经不是资源，智慧才是资源。（清华大学经管学院魏杰教授）从Web中有效的获取知识正在成为人们生活与工作的必须技能高科技企业员工1/3的时间用于查找资料由于无法找到有效信息而浪费的产值占企业收入1/5,问题背景,2005年搜索引擎市场的激烈竞争Google市值的变化举世关注Baidu上市造就数以百计的百万富翁MSN推出新版搜索，MSRA建立搜索研究中心Yahoo中国重组主要门户网站Sohu,Sina,Netease,腾讯纷纷推出搜索引擎产品,最早的网络搜索引擎索引系统诞生：Stanford大学,1995,pictures by Admit Singhal,Google Inc.SIGIR05 keynote speech,google.stanford.edu：google前身,Google服务器机群：1999,Google数据中心：2005,问题背景,问题背景：搜索引擎用户的需求,当前面临的存储与运算需求 每天处理超过2亿用户查询近80亿页面索引,Data by Admit Singhal,Google Inc.SIGIR05 keynote speech,问题背景：搜索引擎的索引能力,搜索引擎索引规模的竞争,2002.12,19.2 bilion(Aug.2005),From Danny Sullivan,SearchEngineWatch web site,问题背景：搜索引擎的索引能力,搜索引擎索引规模竞争的终结？没有任何一个搜索引擎可以覆盖互联网上的所有资源2005年9月,Google从首页去除了页面索引数量的信息，并解释说：“绝对的数量已经不再重要”,问题背景：搜索引擎的索引能力,对中文搜索引擎而言搜索引擎里每天有400多万被检索的关键词一般而言不重复的关键词会占总数的30%以内（根据李彦宏报告的百度状况）对于每个关键词，用户平均点击的页面数在2页以内 则可以估算如下:用户每天使用到的被索引的页面数为2400万个左右在百度的平均更新周期（1个月）内，用户共可能访问到的页面总数为7.2亿个，少于百度声称的索引量（8亿）更少于中文网页总数（20亿）,搜索引擎应当处理(存储、评价、预处理与后处理)所有的Web页面么?数据数量已然非常庞大网络环境数据质量堪忧：不可靠、Spam、过时，重复 不需要，也不可能!利用页面质量评估定位高质量页面在用户查询之前进行 数据预处理阶段使用查询无关特征进行,问题背景,问题背景,去伪存真 去粗取精,问题背景页面质量评估的相关工作概述高质量页面的查询无关特征分析基于学习的页面质量评估算法应用展望,页面质量评估相关工作概述,按照粒度不同宏观粒度的质量评估去除无用页面/定位有用页面清理“全局垃圾”微观粒度的质量评估去除页面中的无用部分/找出页面中最有用的部分清理“局部垃圾”,页面质量评估相关工作概述,宏观粒度的页面质量评估目的：找出对用户检索信息有用的页面当前的研究重点：Web链接结构分析如果存在超链接L从页面P(source)指向页面P(destiny)，则P(source)与P(destiny)之间满足：假设1：（内容推荐假设）页面P(source)的作者推荐页面P(destiny)的内容，且利用L的链接文本内容对P(destiny)进行描述。假设2：（主题相关假设）被超链接连接的两个页面P(source)与P(destiny)比随机抽取的两个页面有更大的概率有内容相关性。PageRank（Google）,HITS（Kleinberg.）及众多的改进算法,页面质量评估相关工作概述,微观粒度的页面质量评估目的：找出对用户检索信息有用的页面的某个部分去除特定垃圾信息（利用机器学习方法和一定量的训练）去除广告条（Davison et.al.）去除页面中的无关链接与垃圾链接（Kushmerick et.al.）页面分块模型依据语料统计信息计算页面块的信息量（Lin et.al.）基于模板频度检测构建站点模板（Yossef et.al.Yi et.al.）基于页面块的绝对位置和机器学习方法计算块的重要性（VIsion Based Page Segmentation,VIPS,MSRA）,页面质量评估相关工作概述,微观粒度的质量评估示例（页面分块）,页面质量评估相关工作概述,页面质量评估的研究现状微观粒度具有数据挖掘方面研究的积累（数据预处理、数据清理等）相对比较成熟完善宏观粒度搜索引擎竞价排名机制的引入，带来了大量的链接垃圾内容推荐和主题相关假设受到挑战过多关注页面自身的特性，忽略用户的实际需求只重视链接结构特征，忽略页面其他类型的查询无关特征,是我们研究的重点,页面质量评估的研究现状,页面质量评估应当涉及到链接关系之外的特征信息PageRank only uses the link structure of the web to estimate page quality.It seems to us that a better estimate of the quality of a page requires additional sources of information.Monika R.Henzinger,Research Director of Google 我们的理解：对于检索系统而言，页面质量的最根本评价不是由诸如页面在链接结构图中的重要程度这样的特征来决定的。能否满足用户获取信息的需要是页面质量评价的根本出发点。研究用户需要什么，而非假设用户需要什么,页面质量评估：我们的做法,有可能成为用户检索目标的页面才是高质量的用户需要什么？反映在用户查询的目标页面中高质量页面：可能成为用户检索目标的Web页面矛盾：查询目标页面是与查询相关的页面质量评估是查询无关的过程必须使用查询无关特征宏观上来讲，与查询相关的查询目标页面是否存在与查询无关的特征呢？,去伪存真 去粗取精,问题背景页面质量评估的相关工作概述高质量页面的查询无关特征分析基于学习的页面质量评估算法应用展望,高质量页面的查询无关特征分析,基于真实网络语料库进行查询目标页面的查询无关特征分析语料库2005.11月采集的超过3700万中文网页占用空间超过0.5 Terabyte.自S获得高质量页面采样训练集:1600页面测试集:17000页面由Sogou工程师手工标注,高质量页面的查询无关特征分析,基于超链接结构分析的特征PageRank入链接个数入链接文本长度其他特征文档长度/大小完全镜像个数URL长度与类型页面编码,高质量页面的查询无关特征分析,PageRank,高质量页面的查询无关特征分析,入链接个数,高质量页面的查询无关特征分析,入链接文本长度,高质量页面的查询无关特征分析,文档长度,高质量页面的查询无关特征分析,页面镜像个数,高质量页面的查询无关特征分析,URL 长度/类型,高质量页面的查询无关特征分析,其他部分特征查询无关特征能够有效地区分目标页面与普通页面，亦即查询目标页面具有查询无关特征,去伪存真 去粗取精,问题背景页面质量评估的相关工作概述高质量页面的查询无关特征分析基于学习的页面质量评估算法应用展望,基于学习的页面质量评估算法,根据查询无关特征计算页面成为查询目标页面的可能性，用这种可能性表示页面质量的高低形式化的表述为：具有查询无关特征A1,A2,A3,An的页面P成为查询目标页面的可能性,基于学习的页面质量评估算法,算法描述1 单特征分析,（贝叶斯公式）,（先验概率定义）,基于学习的页面质量评估算法,算法描述2 多特征分析在合理选取的基础上，可以发现特征之间的近似独立性关系,基于学习的页面质量评估算法,算法描述2 多特征分析（续）,（朴素贝叶斯假设）,（特征近似独立）,基于学习的页面质量评估算法,比较 的相对大小,基于学习的页面质量评估算法,高质量页面的概率分布情况,基于学习的页面质量评估算法,测试效果测试集合：17000多个查询目标页面（训练集的10倍）算法判定出的高质量页面仅占数据总量的5%，但能够满足超过92%以上的用户查询需求,基于学习的页面质量评估算法,质量评估算法效果的评价指标高质量页面平均召回率（High Quality Page Average Recall,AR）,High Quality Recall,基于学习的页面质量评估算法,与直接应用PageRank作为页面质量评估指标的比较,比仅使用PageRank特征取得更好的效果,并不单独依靠某个特征实现评估任务,基于学习的页面质量评估算法,算法分辨垃圾/低质量页面的能力同时具有较好的筛选作弊页面和低质量页面的作用,去伪存真 去粗取精,问题背景页面质量评估的相关工作概述高质量页面的查询无关特征分析基于学习的页面质量评估算法应用展望,应用展望,利用页面质量评估算法作为搜索引擎层次索引机制的基础,普通页面,高质量索引,质量评价算法,搜索引擎系统,结果,查询,反馈,应用展望,同PageRank一样作为Ranking算法的依据PageRank：用户随机访问到某个页面的可能性页面质量：某个页面成为用户查询目标的普适可能性具有明确的物理含义利用类似方法进行垃圾页面清理工作统计垃圾页面的查询无关特征比较查询目标页面而言，这种特征应当更加明显利用机器学习方法构建分类器计算某个页面成为垃圾页面的概率,应用展望,其它的可能应用方向用于提高搜索引擎Spider的页面抓取效率提高个人化搜索（personalized search）质量更好的理解用户使用搜索引擎的行为特点,摘自http:/连续几天，定时被百度的抓取机器人抓到系统停止响应。拜托百度，不要这样抓内容了。就算抓，也应该用1个线程来抓，只抓更新的内容，何必每天抓一次，而且用无数个线程，而且 每次都要抓全部内容，还不放过任何wiki的历史页面，甚至连错误信息都要原样搬走。这种抓取方法，谁受得了？,Thank you!Questions or comments?,
