基于可视布局信息的网页噪音去除算法

基于可视布局信息的网页噪音去除算法http://bigpc.net.pku.edu.cn/~yhf/check/zzg/2004083005%BB%F9%D3%DA%BF%C9%CA%D3%BC%B0%B2%BC%BE%D6%D0%C5%CF%A2%B5%C4%CD%F8%D2%B3%D4%EB%D2%F4%C8%A5%B3%FD%CB%E3%B7%A8%20.doc
荆  涛    左万利
(吉林大学计算机科学与技术学院 长春 130012)
摘要：本文探讨了网页预处理中的噪音去除．由于单一页面中包含丰富的可视信息，提出了一个更加精确的噪音去除算法．与现有采用“可视布局信息”的算法相比，新方法利用一个更加精确的页面显示算法去获得布局信息，并进行页面划分．实验结果表明本文算法优于现有同类算法．
关键词：网页；噪音；页面布局
中图法分类号: TP18  文献标识码: A
随着互联网的迅猛发展，Web上的网页数目呈现出指数级的爆炸性增长趋势．面对如此巨大的资源，在WEB上检索及发现有价值的信息已成为了一项重要的任务．基于WEB的研究涉及信息检索，信息抽取，搜索引擎，网页自动分类及摘要，主题爬行等方面．研究处理的主要对象——网页，在页面中除了表达主题的内容外，还有为了维持页面的链接关系而进行的导航设计或出于商业目的等进行的广告及修饰等内容，这些对于以网页为数据进行处理的算法而言就是噪音．而当前研究对如何去除噪音却未能进行深入的探讨．例如，在做网页分类时，通常是去掉网页中的标记，将页面转化成“BAG OF WORDS”，然后用文本向量空间模型表示，应用分类算法来进行分类．而在做网页的爬行时，也是在对网页进行解析的基础上，对页面内的各个链接同等看待，放入待爬行队列中，由爬行器进行下载．实际上，这样的处理将把许多与主题无关的词，链接带入数据集中，这对于分类算法精度及爬行器性能的影响是巨大的．同时，这样的做法都忽视了网页中应用HTML所产生的可视化信息，及页面在布局上所体现出的设计者的意图．而这些网页在显示时所表现出来的信息，恰恰是人在浏览页面时，对页面内容做出判断的主要依据．本文从人浏览网页的经验出发，利用网页在显示时所表现出的可视化信息及布局特征，对网页进行分块处理．在块的基础上有效地去除了页面内噪音．本文组织[1]如下：1.相关工作 2.算法描述 3.实现及实验 4.结论及未来工作．
1.         相关工作
在与网页噪音去除相近的工作中，可以看到两类情形：A：基于一个或多个网站中的页面集进行页面的模板检测，把为了生成页面而在网站中使用的模板作为噪音由页面中去除．B：基于单一页面的处理，根据所处理页面的DOM结构，可视信息等应用一些启发性规则对页面内的噪音去除．在A类情形中：文[1]中提出信息块（CONTENT BLOCK）概念，对新闻网站中的页面进行处理．以页面中TABLE标记作为处理元素，将页面分割成块，然后由页面集计算出各块的信息熵值，当熵值小于阈值时，认为此块为信息块．此种方法将页面看作可由TABLE分割的集合，并假设已知块在页面集中分布的先验知识，这种假设对于其它类型页面很难成立．而Liu等[2]文中，根据页面的DOM结构，构造STYLE TREE，进行同一网站内页面模板的检测，以排除各页面内的噪音，提高了WEB挖掘的结果，但对从任意网站下载的页面集或B类情形无效．B类情形中：文[3]提出了根据布局信息对页面分块的算法，以消除噪音对分类的影响，但其在分块过程中采用的页面布局算法对于HTML规范中的框架，图层及CSS不支持，因此页面布局算法并不总能反映实际的页面布局．同时分块中主要依赖TABLE标记作为分块的主要参考标记，因此对于没有用TABLE做布局的页面不适应．此外，文[4]利用页面的DOM结构，依据一些规则，对页面内一些元素进行了裁减，但对于链接丰富的HUB页面，如MSN，造成页面中HUB链接被删除．文[5]提出了VIPS算法，将页面转化成内容结构．VIPS基于页面的可视化信息来进行页面划分，并定义其内聚度．算法通过可视块抽取，分隔条检测及构造内容结构三步迭代进行，以各块的内聚度值与预定义的终止条件比较作为迭代的终止条件．此算法对页面进行细致地划分，但并未对噪音数据进行进一步的处理．本文算法属于B类情形，对单一页面进行页面内的噪音去除，应用于主题爬行课题之中．
2.         算法描述
2.1.        网页噪音
虽然XML发展很快，但目前WEB上大量存在的页面仍由HTML写成．由于HTML本身不具备自描述的特性，因此页面在书写时负责显示和承担主题描述的信息混在一起，并且设计者可随意把各类内容加入到页面中．因此网页中充满与主题无关的噪音是个常见的现象．网页噪音根据其划分粒度的不同，可从整个WEB和单一页面本身来加以定义．此处借用[2]中所述定义名称．
定义1：全局噪音
在对WEB上得到的一组页面集进行挖掘或聚类时，若一个网页所存留的副本，如镜像网站，复制的页面，及旧版本的页面也在此页面集中，则这些副本成为噪音数据．
定义2：局部噪音
在一个页面内与页面主题无关的区域及项．这些噪音包括广告栏，导航条，修饰作用的图片等．
本文中由于是对单一页面进行处理，因此今后文中所指噪音将为局部噪音．
在一个页面中常见噪音信息包括这样几类：
a．  导航类：为了维持网页间的链接关系，方便浏览者对网站进行浏览而设置的链接．
b．  修饰类：为了美化页面而采用的背景，修饰图片，动画等．如站点标志图片，广告条．
c．  交互类：为了收集用户提交信息或提供站内搜索服务的表单等．如在线的问卷调查表．
d．  其它类：网页中声明的版权信息，创建时间，作者等描述性信息．
虽然网页中的噪音很多，且网页设计没有统一规范，但设计者大部分都将噪音信息放在页面中的次要位置，以突出主题．如版权信息一般在页面底部，广告栏一般在顶部等．这种设计习惯也为我们利用布局信息去除噪音带来了便利．
2.2.        DOM（文档对象模型）
在对网页的编程实现中会用到文档对象模型（DOM）．DOM提供了访问页面中各个元素属性与方法的接口．每一个网页都会对应一个DOM树．通过对DOM树的遍历，可以对页面中每一个元素进行处理．如可访问元素所对应的位置的坐标，元素所占空间的宽度和高度等．以下是一个DOM树及HTML源码的对照图．
图1 HTML源码与DOM对照图
Fig.1 HTML & DOM
2.3.        噪音去除算法
本文利用页面内可视布局信息来进行噪音去除，是基于如下常识：
a．  页面设计布局上的常规做法
通常设计者在设计页面时会先进行布局的设计，即先用表格或图层等标记在页面显示区域中勾画出页面内容分布的区域．然后再在特定区域内进行细化的页面设计，把所需元素标记放入进去．这种设计上的方法，会用一些区域来存放导航条，版权，广告栏等信息，即这些区域为噪音区域．
b．  用户在浏览页面时识别页面主题的常识
用户在浏览网页时，可以很容易的找到页面中表达主题的区域而不会被导航条，广告栏等信息所迷惑．这是因为用户会将自己的注意力集中于页面中部大块的区域，即设计者通常用来存放页面主题内容的区域．用户浏览时会下意识地将页面进行划分，而将一些噪音区域略掉．这正是机器去除噪音难于做到的事情．
在以上常识基础上，可将页面布局粗分成如下五个区域：HEADER，FOOTER，LM，RM，CENTER，分别代表页面的上，下，左，右及中部区域．通过阈值可调整各区域大小．五个区域划分图如下：其中H代表HEADER，F代表FOOTER，LM和RM分别代表左右两边区域，C代表中部区域．H1，H2，W1，W2分别代表区域划分时所用的阈值．
图2页面布局图
Fig.2 Page Layout
上述划分与[3]中划分相似，但本文算法与之相比有如下不同：
a．  采用精确的页面显示算法，将[3]中显示算法未能处理的包含框架，图层及CSS的页面进行了显示．使得页面划分时所用的布局与用户浏览时所见的一致．
b．  以实际的页面大小，来决定各区域阈值的选取，而非[3]中采用固定大小页面及固定阈值的方法，使页面划分与实际一致．
c．  划分过程中可根据页面中任一标记元素的布局信息来决定此元素属于哪一块中，而非[3]中强依赖于TABLE标记作为分块的依据．
d．  在划分结束后，将CENTER区域中的页面内容作为主题返回，而处于其余四个区域中的内容视为噪音．虽然此仅为一启发式规则，但在实验中发现此规则对大多数页面是合理的．
算法：VL_PS 网页噪音去除
输入：任一网页
输出：去除噪音后的网页
a．  将输入网页转化为DOM结构，并显示，由DOM得到页面实际大小．
b．  根据页面实际大小决定各区域的阈值H1（上边界），H2（下边界），W1（左边界），W2（右边界）．
c．  对页面内所有元素（BODY标记除外）取得其绝对坐标及实际大小（宽度和高度）和由阈值所划分出的区域进行比较．
若任一元素E，其布局信息记为（LEFT，TOP）为其所占区域左上角原点绝对坐标．（WIDTH，HEIGHT）记为此元素所占区域大小．则：
IF E.TOP+E.HEIGHT<=H1，则E属于HEADER；
IF E.TOP>=H2，则E属于FOOTER；
IF E.LEFT+E.WIDTH<=W1，则E属于LM；
IF E.LEFT>=W2，则E属于RM；
d．  所有未被划分出去的元素属于CENTER，将处于CENTER中页面内容作为结果返回．
上述算法中通过一次对DOM树的遍历即可实现页面区域的划分，并去除噪音．算法中各元素布局信息的计算，均采用了元素在页面中所处的绝对坐标．由于在DOM树中各元素存在层次关系，因此由DOM直接得到的坐标信息是相对于其父元素的，为得到元素的绝对坐标，可通过回溯由元素到BODY标记这样一条元素到根的DOM树的路径，叠加各坐标值获得．
3.         实现及实验
本算法在WINDOWS XP系统，512M内存，以DELPHI语言编程实现．为了使页面显示效果与浏览器显示方式一致，算法实现采用了IE浏览器所提供的COM接口来获得页面的DOM结构，并使页面得以显示．IE对CSS等HTML元素显示的良好支持，使页面显示及实际一致．
由于目前对于网页噪音去除仍未有标准数据集，故本实验采用与[3]中类似的方法实现．首先在已由爬行器下载的页面集中选取5000页面集，然后手工对这些页面进行区域的标记，记录结果．然后应用算法对这些页面进行自动处理，并记录下结果．二结果进行比较对照以验证页面划分的正确性．实验结果表明本算法正确地取得了页面的布局信息，尤其是一些采用CSS作为定位方式的页面也得到了很好的处理．这些页面是[3]中算法无法正确处理的．在实验中设定上边界H1为200，下边界H2为160，W1和W2为页面实际宽度的30%．实验中将分块及去除噪音结果分为好，较好，较差，差四个等级，在每级中包含的页面数占比如下表所示：
表1 页面集噪音去除结果表
Table1 page sets eliminating noise result
好
较好
较差
差
24%
52%
22%
2%
以YAHOO网站内一个网页为例显示页面在去噪音前后所表现出的形式（URL见下）：
http://list.auctions.shopping.yahoo.com/21600-category.html?alocale=0us
图3 页面处理前
Fig.3 Page Before processing
图4 页面处理后
Fig.4 Page After processing
本算法采用了与[3]类似的思想，但所用的页面显示算法更加精确，使得算法中获得的布局信息与用户浏览时一致，并且阈值也根据页面布局的实际情况而计算获得，因而取得了更好地效果．
4.         结论与未来工作
WEB的蓬勃发展，使得许多研究如信
息检索、文本分类，数据挖掘等由传统领域转到了WEB上，面对的数据形式是网页．而网页是充满噪音的，因此去除网页上噪音对于获得算法所需的数据表示尤其重要．本文利用依据网页特有的可视布局信息，提出了基于可视布局信息去除页面噪音的方法．通过精确地页面显示算法，获得页面中元素的布局信息，更好的理解了网页设计者布局的意图及表达主题的内容．实验结果验证了其有效性．但本文算法中阈值选取算法仍属于经验化的取值，目前正在进行利用布局信息自动提取阈值的研究．此外，网页除了有噪音外，很多页面本身也是多主题的，这在主题爬行研究中，这些与所需主题内容无关的其它主题内容也应属于噪音范围，这将是今后的一个研究工作．
参考文献：
[1]      Shian-Hua Lin, Jan-Ming Ho: Discovering informative content blocks from Web documents，KDD 2002: 588-593.
[2]      Lan Yi, Bing Liu, Xiaoli Li: Eliminating noisy information in Web pages for data mining. KDD 2003: 296-305.
[3]      Milos Kovacevic, Michelangelo Dilligenti, Marco Gori, Veljko M. Milutinovic: Recognition of Common Areas in a Web Page Using a Visualization Approach. AIMSA 2002: 203-212.
[4]      Suhit Gupta, Gail E. Kaiser, David Neistadt, Peter Grimm: DOM-based content extraction of HTML documents. WWW 2003: 207-214.
[5]      Deng Cai, Shipeng Yu, Ji-Rong Wen, Wei-Ying Ma: Extracting Content Structure for Web Pages Based on Visual Representation. APWeb 2003: 406-417.
Eliminating Noisy Information in Web Pages Through Visual Layout Information
Jing Tao  Zuo Wan-Li
(College of Computer Science and Technology, Jilin University, Changchun 130012)
Abstract: This paper investigates noise elimination problem for web page preprocessing. Targeted at standalone web page with richer visual information, a more precise noise elimination algorithm is put forward. Compared with existing approaches based on “visual layout information”, the newly proposed method adopts a more precise web page rendering algorithm in extracting layout information and partitioning page segments. Experimental results show that the proposed algorithm outperforms existing algorithms of the same category.
Key words: web page; noise; page layout
[1]基金项目：国家自然科学基金（编号：60373099）作者简介：荆涛（1974-），男，硕士研究生，主要研究方向为搜索引擎，主题爬行，WEB挖掘等．Email: jingtaocst@163.com Tel:0431-5166492