`
longgangbai
  • 浏览: 7330955 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论
阅读更多

面向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在线生成系统

分享到:
评论

相关推荐

    计算几何的不规则三角网算法研究及在GIS中应用

    《计算几何的不规则三角网算法研究及在GIS中应用》这篇硕士论文深入探讨了不规则三角网(TIN:Triangulated Irregular Network)在地理信息系统(GIS)中的理论与实践,是学习和研究这一领域的宝贵参考资料。不规则...

    关联规则推荐的高效分布式计算框架.pdf

    对于候选规则挖掘,本文将其转化为森林上的路径搜索计算,提出了一种高效的单机路径搜索算法。这种算法能够在有序模式森林的基础上快速找到与用户浏览记录相匹配的关联规则,从而加快了推荐计算的速度。 负载均衡的...

    京东搜索排名规则深析干货PPT学习教案.pptx

    总结来说,京东搜索排名规则涉及到分词、召回、索引限制、商品质量分计算、相关度排序和搜索反馈等多个方面,商家需综合考虑这些因素来优化商品信息,提升搜索排名,从而提高商品的可见性和销售潜力。

    计算机毕业设计:游戏规则

    例如,使用链表或数组来存储游戏对象,用搜索算法(如A*寻路算法)来计算角色的最佳移动路径。同时,为了提高效率和可扩展性,游戏规则可能会设计成模块化,这样可以方便地添加、修改或删除某个规则。 最后,游戏...

    博弈树搜索的算法改进论文.pdf

    然而,随着游戏复杂度的增加,原始的搜索算法面临计算资源消耗巨大、搜索效率低下的问题。因此,针对博弈树搜索的算法改进成为研究热点,旨在提升搜索速度和决策质量。 #### 最小最大策略与负极大算法 博弈搜索的...

    android 搜索热点词 不规则显示

    总之,实现“android搜索页热点词标签的不规则显示”涉及到自定义View的绘制、字符大小和颜色的随机化、自动换行的计算以及布局的适配。通过巧妙地组合这些技术,我们可以创建一个动态且富有视觉吸引力的搜索热点...

    数据挖掘中关联规则经典算法Apriori

    算法的核心是利用“先验知识”(即Apriori性质)来减少搜索空间,避免无效的候选集生成。Apriori性质指出,如果一个项集是频繁的,那么它的所有子集也必须是频繁的。通过这个性质,算法可以提前排除不可能成为频繁项...

    基于关联规则的医疗大数据挖掘算法.pdf

    频繁项集的查找是关联规则挖掘的基础,它涉及搜索给定数据集中所有频繁项集的过程。通过频繁项集的查找,可以进一步确定强关联规则。而在医疗大数据的背景下,频繁项集的查找将对疾病模式、药物相互作用等医学领域的...

    基于ssm+mysql关联规则的计算机类考研院校推荐系统源码数据库论文.docx

    6. 关联规则:该规则用于推荐用户可能感兴趣的院校信息,提高搜索效率,解决信息过载的问题。 7. 考研院校推荐系统:该系统旨在解决用户在搜索院校信息时面临的困扰,帮助人们快速找到适合自己的考研院校信息。 8....

    gis地图距离计算

    这涉及到网络分析,包括Dijkstra算法或A*搜索算法,它们会考虑交通规则、路况等因素,找到最短或最快路线。 6. **精度与误差**:在实际应用中,GPS坐标可能存在定位误差,这可能影响到距离计算的精确性。为了提高...

    计算机专业英语论文翻译

    ARM 算法在方式上与他们搜索的通过子集关系项集格跨区不同,大多数方法使用水平精明的或自底向下的搜索的格,为了计算频繁项。如果长期频繁项目集都在预计中,那么纯自顶向下的方法是首选,一些提出的混合搜索,他们...

    alphabeta搜索五子棋

    五子棋是一种深受人们喜爱的智力游戏,其规则简单,但策略深奥。在计算机科学领域,如何让计算机在游戏中展现出高超的棋艺,一直是人工智能研究的重要课题。本文将深入探讨AlphaBeta搜索算法在五子棋中的应用及其...

    计算智能的发展历史

    在函数优化中,进化计算能有效地搜索多维函数的全局最小值。 总的来说,计算智能的发展历程是不断探索和融合的过程,从最初的理论构想到实际应用,它已经成为解决复杂问题的强大工具。未来,随着大数据、机器学习和...

    matlab 线搜索方法_matlab线搜索方法_线搜索_

    2. **Armijo回退规则**:它是一种背tracking线搜索策略,设定一个初始步长,如果函数值没有降低,则减小步长并重新计算,直到满足一定的下降条件。 3. **Wolfe条件**:除了 Armijo 条件外,还添加了一个强Wolfe条件...

    算法-数据结构和算法-2-最坏时间复杂度和计算规则.rar

    本资源"算法-数据结构和算法-2-最坏时间复杂度和计算规则"聚焦于理解和分析算法的时间复杂度,特别是最坏情况下的时间复杂度,以及如何计算这些复杂度。以下是关于这一主题的详尽解析。 首先,我们需要了解什么是...

    24点计算程序(产生式算法)

    此外,源代码可能会包含一些优化措施,如记忆化搜索,将已经计算过的状态存储起来,避免重复计算;或者采用迭代加深的深度优先搜索,每次增加一定的深度限制,直到找到解决方案。 总结来说,"24点计算程序(产生式...

    张军《计算智能 》教材 课件 ppt

    《计算智能》是计算机科学领域的一门重要课程,主要探讨如何通过模拟生物进化、神经网络、模糊逻辑等自然现象来解决复杂问题。本教材由张军教授编著,结合课件,为学习者提供了深入浅出的理解路径。下面将详细阐述...

    高性能计算实验_SAT问题.docx

    该算法的设计思想是利用深度优先的方法对解空间做深度优先搜索,在赋值的过程中利用一些规则找到一些唯一的赋值方式。DPLL 算法是由 M.Davis 和 H.Putnam 于 1960 年提出的,现在已经成为解决 SAT 问题的最著名的...

    易语言表达式计算公式解析

    通过理解和掌握这些知识点,开发者可以构建出自己的表达式计算引擎,实现自定义的计算规则,这对于开发计算器应用、数据分析工具或者其他需要进行动态计算的软件非常有用。在实际编程中,理解并运用这些原理能够提升...

Global site tag (gtag.js) - Google Analytics