基于网页结构与链接关系的中文文本分类方法

摘 要:提出一种通过综合考虑网页的HTML结构信息以及网页间的链接关系,修改网页文本在向量空间模型表示中的权值,对网页进行分类的方法。考虑到页面里处在不同HTML标记下的内容具有不同的语义含义,某些特殊标记下的内容具有较重要的意义,对网页的分类起较大的作用,因此对不同标记下的内容赋以不同的权值,可以提高分类效果。考虑到页面正文中链接指向的页面内容与原网页相关度较高,通过综合考虑这些页面的内容,可以有效加强类别关键词的权值,减少噪声,提高分类效果。经过实验证明这一方法提高了分类结果的F1值。关键词:中文文本分类;HTML结构; 链接关系; 向量空间模型

中图分类号:TN911-34; TP391 文献标识码:A

文章编号:1004-373X(2010)22-0054-03

A Novel Chinese Text Calssification Method Using Webpage Tags and Hyperlinks

GUO Xiao, JIANG Zong-li

(College of Computer Science, Beijing University of Technology, Beijing 100124, China)

Abstract: A webpage classification method using the HTML tags and hyperlinks to improve the vector space model representation is introduced. Because the content in different HTML tags has different semantic meaning and plays different role in webpage classification, assigning weights to the content by the importance can improve the classification accuracy. In addition, to better model the webpage for classification, combining the information provided by the webpage that are referred in the body of the original webpage, considering they are relevant and can enhance the weights of relevant words and reduce the weighs of irrelevant words. The experimental results demonstrate that the proposed method effectively improves F1 measure.

Keywords: Chinese text calssification; HTML tags; hyperlinks; vector space model

收稿日期:2010-06-19

随着计算机技术、通信技术等信息技术的高速发展,以及互联网基础设施建设与网络信息工具的大量推广应用,网络上的信息正在以几何级数进行着增长。如何使用户能够方便地从网络上海量的信息资源中获得其期望的部分,成为了当前信息领域重要的研究课题。

网络搜索引擎,是用来进行网络文本索引的一种重要手段,是针对网络中大量网页文本信息进行信息挖掘的有效手段。在网络搜索引擎的构建中,网页文本分类问题是一个关键性的核心问题。高质量高效率的网页文本自动分类,对构建高效、实用的搜索引擎起着重要的作用。同时在解决主题搜索、个性化信息检索、搜索引擎的目录导航等相关问题时,网页文本分类技术也是十分重要的。因此研究如何提升网页文本分类性能,对研究新一代搜索引擎有着重要意义。

1 网页文本分类技术简析

网页文本分类是指按照预先定义的主题类别,根据海量网页文档的内容,确定相应网页的类别。

目前,网页文本分类采用的技术基础是基于内容的纯文本分类。基本方法是,在抓取到的网页集合中,对每篇网页文本进行纯文本的内容抽取,得到相应的纯文本文档。再将抽取出的纯文本组成新的文档集合,在新的文档集合上应用纯文本分类算法,进行分类。再根据纯文本和网页文本的对应关系,对网页文本进行分类。即应用网页的纯文本内容信息,对网页进行分类。

上述方法的本质,是将网页文本的分类问题映射成为纯文本分类的问题。但是,由于网页文本是超文本标记语言(HTML),并非纯文本的自然语言。因此,这样的映射,不能很好地反映网页分类问题的本质。所以仅应用基于网页内容的纯文本分类方法,会对网页文本分类的准确率造成一定的不良影响[1]。

针对这个问题,目前已经有一些改进的技术。一类改进方法,是在对网页进行文本内容提取时,基于网页HTML结构信息,对提取出的纯文本的向量表示进行某些修改[2-4]。还有一类改进,是针对网页文本中的超级链接,利用不同页面间的链接关系进行分类。

2 HTML结构与超级链接综合的网页分类

本文提出以基于网页内容的文本分类为基础,综合考虑网页页面的HTML结构信息以及网页间的链接关系,对网页进行分类。考虑到纯文本分类技术的成熟性,仍然采取基于内容的纯文本分类方法作为网页分类的基础,再从网页文本向纯文本的转换过程中增加一个中间的步骤,即首先对网页文档进行页面结构和链接关系分析,生成待处理的中间文档集,再通过一定的算法将中间文档转化为纯文本,从而应用纯文本的分类算法进行分类。其核心思想是,将网页文档转化为纯文本,进而应用向量空间模型对纯文本进行表示并分类,在这个过程中,增加一个修改向量权值的中间过程。通过这一步处理,使得向量空间模型对网页语义的表达更加准确,进而提升分类算法的综合性能。

整个过程包括网页预处理、中文分词、文档的向量化表示、特征提取和分类5大步骤[5]。HTML结构与超链接综合利用出现在网页预处理和文档的向量化表示中。下面分别讨论。

2.1 网页预处理

对网页集进行预处理,主要是针对网页HTML标签进行分析。应用传统的标记窗算法对网页内容进行分析,抽取出网页正文部分(包括正文中的超级链接)。根据HTML标签对Web页面物理显示所产生的影响,将HTML标签进行分类。典型标签如下[6]:

(1) 标签及本身所修饰的内容不在浏览器中显示,如。

(2) 标签修饰的内容在浏览器上显示,对其进一步划分:

① 改变文本的物理显示,如 ;

② 改变文本的内容样式,通过改变文本的物理显示来实现,如 ;

③ 物理显示无变化,但标签反映修饰内容属性,如 ;

④ 当鼠标悬停时显示内容,如。

(3) 标签本身在浏览器中显示,包括,这些标签用于定义列表项。

(4) 根据浏览器不同设置,标签所修饰的内容可能显示,也可能不显示。

对页面内各类HTML标签做进一步的分析可以发现这些标记在页面信息表达上的一些特点。第(1)类标签对于页面显示无任何影响,可以认为其对网页内容表达没有贡献,此类信息对于分类没有帮助,故后续的处理中将其舍弃。在第(2)类标签中,①和②两类标签是最常用的HTML结构标记,是网页文本在内容表达上与无格式纯文本有较大不同的地方。段落层次、加粗等结构标识突出了处于不同位置的文字信息的不同重要程度。因此将这类标记所表达的不同语义赋与对应文字以不同权值,可以提升文本语义表示的精确性。┑(3)类标签虽要在页面中进行显示,但是标签本身表达的语义信息有限,多为列表格式信息,故后续的分析中对其舍弃。第(4)类标签多为HTML标记中针对多媒体的应用,而这正是网页页面有别于纯文本的地方。这些标签所修饰的多媒体信息对于整个网页内容的表达起了相当巨大的作用。但是,传统的文本提取与向量化表示对多媒体信息无法有效的表达。例如网页中的图片信息对于整个网页的内容表达有非常重要直观突出作用。但是,图片信息无法直接转化为文本表示并对其内容进行表达。一个重要应用是对于标签的“ALT”属性,用户可以通过浏览器设置来决定是否下载图像。“ALT”属性表示图像不能显示时的替换文本,通常能够反映图片的内容。对这类标签的处理可以很好地利用网页中的多媒体信息。

除了HTML标签表达了重要的语义信息之外,页面上超级链接也表达了一定的语义信息。传统的处理方式多是单独利用网页间的拓扑链接关系进行分析,较少的考虑链接的语义关系。本文提出的改进方案,考虑了网页上的到其他页面的链出链接的语义内涵。

2.2 文档的向量化表示

(1) 应用向量空间模型,对文档本身进行向量化[7]。将分词处理后的文档按照改进权值分配的TF-IDF公式进行向量化表示,计算各词的权值。将┟扛霆页面P转化为向量V。

TF*IDF:W(ti,d)=tf(ti,d)*log(N/ nt+L)

其中:W(ti,d)为词ti在文本d中的权重;tf(ti,d)为词ti在文档d中的加权词频,具体计算公式见后面;N为训练集文本的总数;nt为训练文本集中出现词ti的文本数;L为平衡因子,为了防止对数内出现1使得对数为零,故选择较小的正实数施加影响,本实验中选择L=1.0E-4。

tf(ti,d) =∑(w(ek)•tf(ti,ek,d))

其中:ek表示的是上文分析的HTML文本的组成部分。tf(ti,ek,d)表示在网页文档d中,ek部分特征项ti 的出现频率;w(ek)为预先定义的HTML位置权重参数。根据前文所述的分类,对HTML标签分配权重。

标签 (ek) 权重

… 10

… 8

… 7

… 6

…5

… 5

…5

… 4

4

… 3

(2) 利用页面的链接关系,修改文档的向量表示。

网页制作者在进行信息的时候,不仅是将自己需要表达的内容制作成页面放在网上供人们浏览,通常还会利用到一些网络上已经存在的页面或资源,对其自身内容进行解释与补充。或者提供一些经过搜集整理的网络上的相关内容,进行对照说明。并且在通常情况下,网站的制作者不会在自己的页面主体部分中加入主题无关的垃圾链接。充分考虑这些相关链接所提供的信息,对网页分类的准确性会有一定的影响,现在已经提出的基于网页链接关系的技术有PageRank算法和HITS算法[8-9]。

可以假设网页正文中链接的语义含义是:链接指向的页面内容是对原网页内容的补充与强调,是主题相关的。因此,充分利用这些页面的内容信息有利于对原网页的内容进行表达。本文采用的方法是通过将这些被链接的页面的内容以一定的比例附加在原网页上,来达到附加信息量以提高区分度的目的。

对每个页面中正文部分的链出链接进行分析。设页面P0的正文部分具有n个分别指向P1,P2,…,Pn页面的链接。采用向量空间模型对页面进行表示,设向量Vi代表Pi页面。基于前面的假设,对P0页面的向量表示V0进行修改。用V表示V1,V2,…,Vn的重心:V=(V1+V2+,…,+Vn)/n,取V0=V0 +ΔV。其中,ΔV= |V|*V/|V0+V|,即用|V|*V/|V0+V|修改原向量。

假设极限条件下,页面P0自身的内容为空,仅有指向外部的链接。这个页面可以看作一个Hub页面,它所表达的内容信息,就是它所指向的页面的内容信息的总和。根据上面公式可得:ΔV=V,即V0=0+V=V,符合语义含义。在另一种极限情况下,页面P0不具有指向其他页面的链接。则V=0,ΔV=0,V0=V0,即页面的权值具有不变性,符合语义含义。在中间情况下,ΔV采用带模的调和平均作为改变量,对原向量进行修改。充分考虑了原网页和链接指向网页内容的信息量的大小分布,符合语义含义。

3 实 验

3.1 实验数据集

实验语料选用北大天网提供的大规模中文Web测试集CWT200g(Chinese Web Test collection with 200 GB web pages)。其中包括37 482 913个网页。采用20%~80%切分,选取其中的80%作为训练集,其余作为测试集。

3.2 评估方法

分类效果评估是指一些用来评价分类器分类准确度的量化标准[10]。通常采用以下5种标准从不同的方面评价一个分类器:查准率(precision)、查全率(recall)、F1标准、宏观平均值(macro-averaged score)、微观平均值(micro-averaged score)。其中:

查全率=分类正确文本数/总文本数×100%

查准率=分类正确的文本数/实际分类的文本数×100%

F1为查全率与查准率的调和平均,综合的反映了分类的效果。

3.3 实验结果

实验中,在所选用的训练集上,分别应用传统方法和本文提出的改进方法对网页进行预处理并进行向量化表示,然后对分类器进行训练。分类器采用支持向量机方法(SVM)[10-11]。然后在测试集上分别应用分类器进行分类,并按照类别计算F1值。实验结果对比了传统方法和本文提出的改进方法的分类结果。如图1所示,列出了9个主要类别的分类情况,其中柱状图数值分别代表对该类别分类的F1值。

图1 各类别F1值

3.4 实验结果分析

从实验结果可以看出,本文提出的改进方法在各个类别上都比传统的分类方法获得更高的F1值。说明在各个类别分类的综合性能上具有一定的改进。其别是对那些在传统方法分类中结果较差,类主题自身较不明确的教育、旅游、经济等类的分类上有很大的提升。但是在如军事、计算机等主题相对明确的类别上改进算法提升不是很显著。

例如,旅游类别的网页内容较杂,类别本身区分度较低,传统的方法仅通过网页正文内容信息进行分类,在内容上会和社会、经济等类别的网页发生严重的交叉。所以传统方法对于这样类别的网页分类性能相对较差。在改进的方法中,由于网页内链接所指向网页的内容被引入,使得原文档相对增长,信息量增加,文档所表达信息的类别重叠程度下降,所以分类性能有了较大提升。

军事类别的网页内容较集中,该类别中的网页内容具有较强的独特性,类自身聚集程度较高。通过对原文档增长的方法不能较显著的改变分类性能。在某些情况下,还可能由于主题漂移而起到相反的作用。在测试集上的综合分类效果来看,F1值由传统算法的87.1%提升到了93.4%,具有显著的改进。

4 结 语

通过实验证明,综合考虑网页HTML结构标识以及网页链接关系所表达的语义信息,在应用向量空间模型对网页进行表示的时候,修改权值以达到更好的表达效果。应用本文提出的改进方法,在测试集上进行分类,F1值由传统算法的87.1%提升到93.4%,具有显著改进。

另外,由于链接较多的页面会导致原页面主题发生漂移,针对这一现象还有待进一步研究。

参考文献

[1]施聪莺,徐朝军,杨晓江.TFIDF算法研究综述[J].计算机应用,2009(Z1):167-170,180.

[2]赵小华,马建芬.文本分类算法中词语权重计算方法的改进[J].电脑知识与技术,2009(36):209-213.

[3]陈素萍,谢丽聪.一种文本特征选择方法的研究[J].计算机技术与发展,2009(2):112-115.

[4]陈笑筑,王东,陈笑蓉.基于页面标签的网页分类研究[J].商场现代化,2009(19):100-101.

[5]台德艺,谢飞,胡学钢.基于位置权重的文本分类[J].安徽水利水电职业技术学院学报,2008(1):64-66.

[6] 刘海峰,王倩,王元元.基于Web的文本检索位置加权模型研究[J].情报科学,2007(3):451-455.

[7]刘艳民.中文网页分类方法的研究[J].微电子学与计算机,2009(9):48-51.

[8]范聪贤,刘秋菊,徐汀荣.应用Web结构挖掘的PageRank算法的改进研究[J].计算机工程与应用,2010(9):127-129.

[9]常庆,周明全,耿国华.基于PageRank和HITS的Web搜索[J].计算机技术与发展,2008(7):77-79.

[10]杨创新.基于机器学习的高性能中文文本分类研究[D].广州:华南理工大学,2009.

[11]姜鹤,陈丽亚.SVM文本分类中一种新的特征提取方法[J].计算机技术与发展,2010(3):17-19,23.