搜索计算的规则

面向Web应用的网页预处理
2003年12月3日
(讲稿由张志刚协助准备)
搜索引擎的三个组成部分
收集,得到"原始网页文件"
服务,需要的是"网页的表示"
整理,中间的转换及其相关任务
天网流程
"整理"阶段的目标
便于服务的实现:效果,效率
效果 – 服务对用户的效果
例如搜索引擎,就要追求"相关性"之类
效率 – 不仅是用户感到的服务的效率,还有生成服务系统的效率
"不太优化"的流水线
单服务目标还是多服务目标
收集的海量网页数据是可以为多个应用目标服务的(发挥想象力)
常规搜索引擎
分类目录搜索引擎
主题搜索引擎(例如教育主题)
个性化搜索引擎(例如"天网知名度")
"反馈迭代式"搜索引擎
文本挖掘(语言学,新词的产生)
电子商务…
共同的基本需求
去除"噪音"(净化,purification)
local noise,网页内和主题无关的内容,例如广告,版权信息,等等.
消除冗余
global noise,包括镜像站点,和转载复制(replica, near-replica),等等
不过,有的应用可能希望保持冗余, 例如Web InfoMall,以保持"历史的真实"
Local noise对应用的影响举例
网页分类
由于噪音内容的主题无关性,训练集中的噪音内容会导致各个类别的特征不够明显,而待分类网页中的噪音内容则会导致该网页类别不明确,因而影响了网页自动分类的效果.
因此,训练网页和测试网页都应该"去噪"
Local noise的影响
Web信息检索
如果不去掉噪音内容,建立索引时,一张网页会因为索引项在噪音内容中出现而被记录到倒排表中,因而在查询时,由于查询词在网页的噪音内容中出现而将该网页检索出来.
影响"查准率"
Local noise的影响
重复网页的识别(消重)
相同的主题内容,由于放在了不同的模板中(噪音内容不同)导致应该被消掉但实际上被消重程序判断为非镜像网页而保留.
不同的内容,由于放在了相同的模板中,如果噪音很重,则可能导致不应该被消掉但实际上被消重程序判断为镜像网页而消掉.
一句话,局部噪音影响对网页主体内容的判断
全局噪音对应用的影响
浪费资源
抓取时间,存储空间
索引负担
建立索引时,必须对大量的重复网页建立索引,使倒排文件变得庞大.
影响服务效果
庞大的倒排文件直接影响提供服务时的响应速度,并且,检索结果中会出现大量的重复结果,不仅无价值,而且annoying.
倒排文件的大小对性能的影响
(后面专门分析)
数字图书馆有类似需要
传统的文本检索预处理(净化)
对文本的词汇分析
数字,标点,大小写等等
取掉停用词(stopwords)
去掉语义区分能力很低的词(例如"大家","我们"等)
对保留下来的词作词缀(英文)处理
保证能够将包含与查询词同根的文档检索出来
索引项的选取(也算是某种前期"特征提取")
比如:通常名词比动词,形容词更具有语义信息
索引项的归类组织
便于用相关的词对查询词进行扩展(query expansion)
Web网页带来的新特点(有好有坏)
文档内容的半结构性
HTML规范中定义了一套标签来规划网页内容的布局(如:,)以及内容的显示方式(如:,,).
其中规划布局的标签的结构在一定程度上蕴含了文档内容的语义关系;而描述内容显示方式的标签则蕴含了内容的重要性信息.
文档之间的超链接
网页中通常会有超链指向内容相关的网页,相关的超链蕴含着网页间内容相关性.
某些网页本身不含有主题内容,而仅包含一组超链指向其他的网页,称之为HUB网页(集散网页),
某些网页被许多其他网页引用(指向),意味着某种重要性,称之为authority网页(权威网页).因此,通过链接情况可以在一定程度上判断一个网页在Web上的重要性.(在科技论文中,引用情况有同等效应)
文档内容的随意性
网页中的内容除了主题内容外,还通常包含广告,版权声明,导航条等噪音信息.
这些噪音内容会对基于网页内容的应用造成影响(如:网页分类,信息检索).而广告等噪音内容通常是作为超链的anchor text出现的,因此噪音内容也对基于超链指向的应用造成影响(如:主题搜索).
网页重复现象严重
Web上的网页存在大量重复的情况,一部分是对原始网页的完全考贝(称之为镜像网页),另一部分则是将原始网页中的主题内容放在不同的模板中转载(称之为转载网页).
天网搜的中国互联网上从2002年12月-2003年4月的1.18亿网页,去掉镜像网页后只剩3000万,而再去掉转载网页后只剩余1800万.
仔细想想
不同的应用除了消除上述"local noise"和"global noise"的共同需求外,还有
文档的某种内部表示
例如,a bag of words
不同的应用要求可能不同
因此我们想,如果在"整理"阶段能提供某种综合的文档表示("最大公因子"),能够适应不同应用,会有意义.
我们的目标
在原始网页内容的基础上,建立一种有效的表示模型,满足如下特点
"元数据"分离
噪音去除(提炼出比较干净的主题内容)
链接关系保持
实现这个模型
给定一篇网页,生成该模型包含的元素
基础性工作,希望能成为多种应用的底层服务,"一石多鸟".
元数据的参考规范
Dublin Core是描述网上资源的一个较为通用的Meta data 模型,其中包含了较为通用和常用Meta data.常用的Meta data包括:
Identifier:对一个网络上实体的唯一标识,如:URL
Title,标题
Keywords,关键词
Abstract:摘要(在数字图书馆,改进索引方面经常用到)
Classification Code:从语义角度的分类(对主题搜索,个性化服务有用)
EDA (Encoded Archival Description)
美国国会图书馆和档案馆制定的一套针对电子文档Meta data模型,其中包含了主题内容和引用文献两项,这对于Web Apps是非常实用的,其中引用文献与网页中相关超链有着相近的含义,而主题内容可以看作是净化后的网页内容.
将Meta data的提取放入预处理工作另外一个原因是出于效率的考虑.在噪音去除的过程中,Meta data已经生成或接近生成,因此在预处理过程中,将所需的信息一次性提取可以大大提高效率.
网页的DocView模型(8要素)
标识:URL
标题:不一定是之间的,要形成
摘要:要提炼
关键词:要提炼
主题内容:去掉噪音后的东西
内容类别:源于对主题内容的分析
主题相关引用:排除噪音链接
类型(有主题网页,集散网页,图片网页)
实现方面的考虑
目标:对每一篇网页,提取出上述8个元素
技术追求:不基于关于网页结构的先验知识(例如网站模版),从而可达最大的通用性
别人不一定这样做
文章[2] 假设:对于一个网站,内部的网页基本上是使用相同模板的.
于是,对每张网页构造标签树.认为标签树中,如果某个结点的内容在网页集内频繁出现,就会被认为是广告等噪音信息.
我们认为我们的目标更有用
"天网系统"的预处理
目标:在各种Web Apps前搭建一个精炼的,方便操作的信息平台
准备工作:得到网页的结构
构造网页的标签树(刻画网页内容的结构)
准备工作:确定判断与评价的依据和方法
网页类型:如何区分
对于主题网页
内容分类:如何确定
标题:
摘要:
关键词:
主题正文:
相关链接:
基本思路:用VSM,量化表示网页
实现VSM必须考虑的几个问题
特征词的选取
权值的确定(二元,TF,DF,TFIDF,…)
网页相似度的测度
特征选取
注意,现在的目标是一个综合的基础表示,不仅要支持检索,还有分类,以及其他应用.
停用词总是要去掉的,但传统的的停用词集和规模很小,起到的降维作用不大.
试想,在一个大的数据集上根据TFIDF公式计算每个词项的权值,然后把权值小于一定阈值的词项作为停用词去掉.这样做的问题是这个阈值如何确定 用DF也似乎不妥.
我们的策略:学习
随机选取一个有一定规模的网页集,考察其中的词的特性
认为:如果一个词在其中大量的网页中的词频都较高,我们认为这样的词对网页的区分能力较低,可以当作停用词对待.
"大量" >200;"较高" >= 2
这种定量的根据 统计考察高频词随文档频率的分布.
高频词的文档频率分布
"天网"预处理:网页内容净化
网页净化(主题内容的提取)是其他工作的基础
网页净化的过程,是对标签树的结点进行剪裁的过程.那么按照怎样的策略剪裁呢
两个启发式规则:
1,一篇网页中的正文通常是用成段的文字来描述,中间通常不会加入大量的超链.
2,而非正文信息通常是伴随着超链出现的.
这两个启发式规则并不是对所有的网页都适用,对于一个有主题内容的网页是适用的,但对于一个目录型网页显然是不适用的.因此必须对网页的形式进行分类:主题网页,目录型网页,图片网页.
两个层次的处理思想:"内容块"和"网页"
有主题网页
HUB网页:超链多并且文字数量与超链数量的比值偏小是该类网页的特征.门户网站的首页就是典型的HUB网页
图片网页:图片量大并且文字数量与图片数量的比值偏小是该类网页的特征.某个机构的人员介绍网页就是典型的图片网页
而网页的类型则可以通过网页内各个内容块的类型来综合获得.我们把网页内的内容块也分为上述三类,并按照如下规则进行分类:如果内容块中词项数与图片数的比值小于某个阈值,该内容块就是图片类型,如果内容块中作为anchor text出现的词项数与该块中总词项数的比值小于某个阈值,该内容块就是目录类型,否则为主题类型.
"天网"预处理:网页内容净化
给定一篇网页,我们统计网页中出现在每一类内容块中的词项数来决定网页的类型,即出现在哪一类内容块中的词项多,该网页就是哪一种类型的网页.
为了更准确起见,我们只统计网页中央区域内出现在每一类内容块中的词项数来决定网页的类型,因为网页周围通常都是超链,容易把主题内容简短的主题网页误导成目录型.
内容块的取舍(对应于标签树结点的剪裁)
对于主题网页,保留网页中的主题内容块并按照网页原有的布局重新组合起来就构成了一个只含有主题内容的网页.
对于目录型网页和图片型网页,重要的信息通常放在网页的中央位置,而网页边缘的超链通常重要性较低.因此我们可以通过网页布局的信息去掉网页周围内容块.
重复网页的识别与消除
"天网"目前采用的消重算法
对于每张网页,从净化后的网页中,选取最有代表性的一组关键词,并使用该关键词组生成一个指纹.通过比较两个网页的指纹是否相同来判断两个网页是否相似.
指纹生成算法如下:
Step1: 将每个网页表示成特征向量,使用每个特征项的的词频作为其权值.
Step2: 将特征项按照词频降序排列,词频相同的特征项按照字符排序
Step3: 选取前α 个特征项,然后重新按照字符排序(否则找不到对应关系了)
Step4: 调用系统的MD5算法,将每个特征项串转化为一个128比特的串,作为该网页的指纹
重复网页识别与消除
该方法的优缺点
效率高:基于单指纹的方法中,需要为每个网页生成一个指纹,时间复杂度为(O(N)),通过排序可以方便的把相同的MD5聚到一起,时间复杂度为 (O(N*logN)) ,但这个过程仅仅是对128 bit的串排序.而基于两两相似度比较的方法则需要(O(N*N)),而且进行的是文档比较操作.
对并行处理有很好的适应性:基于单指纹的方法中,网页相似的关系是一个等价关系(就看指纹的相等与否),因此对于分布在多台机器上的网页,可以各自先本地处理,然后对每台机器上消重结果进行合并,对合并结果再次排序即可.而基于两两相似度比较的方法中,网页的相似关系则不是一个等价关系,即:A与B相似,B 与C相似,不能保证A与C相似.因此,多机并行处理时问题很多.
过于敏感:单指纹的方法很敏感,只要提取的关键词不同,那么生成的指纹一定不同.而且,指纹的差别不能体现网页的差别.而基于两两相似度比较的方法则可以很好的量化网页间的差别.
"天网"预处理:Meta data提取
在得到网页的主题内容(正文)之后,我们采用下图中的流程提取DocView模型其它的要素.
元信息提取:关键词
以网页特征项的权值为依据,可以采用下述两种策略选取关键词
a,绝对数量策略 :严格选取权值最大的α个特征项作为该网页的关键词( α为事先定义的关键词个数)
b,相对数量策略 :首先计算所有特征项权值的算术平均值avg,然后定义一个调节阈值β(0<ββ then // β为相似度阈值
7: 保留CBi中的URL
8: else 不保留CBi中的URL
9: end if
10: end if
11:end for
原始网页与最终DocView的对应图
测试
DocView在线生成系统