去伪存真去粗取精页面质量评估及其在网络信息检索中的.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前身,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）质量 更好的理解用户使