（应用数学专业论文）中文网页分类特征提取算法探讨.pdf

中山大学硕士学位论文 中文网页分类特征提取算法探讨 专业： 硕士生： 指导老师： 应用数学 梁永江 张磊 摘要 i n t e r a c t 的迅猛发展使得网页分类技术的应用越来越广。这种技术通过将w e b 网页进行分类、组织和检索，达到有效组织处理海量网页的目的，它是主题搜索、 个性化信息检索、搜索引擎的目录导航以及信息过滤等领域的核心技术。 网页提供的特征通常多达数万个，直接基于这数万个变量的建模难度相当 大，这就使得特征提取成为网页分类的一个关键步骤。但是，传统特征提取方法 存在两个明显的不足：其一，传统的m i 度量方法过分倾向于低频词和小样本类 别，降低了抽取出的特征的代表性。其二，传统的特征选择方法只是简单地按特 征度量的分值依次选取具有最大分值的特征，忽略了特征的组合对类别的偏向程 度，导致单个特征较优，但组合起来却未必最优，从而降低了分类器的性能。 本文的主要创新之处在于，在m i ( - f f 信息) 度量的基础上提出一种新的度量 一m i d n 特征度量( 定义见4 2 2 节) ，并提出两种新的特征选择方法：b b ss ( b i a s b a l a n c e ds e l e c t i o nb ys c o r e ) 和b b s 算法( 见n ( b i a s b a l a n c e ds e l e c t i o nb yn u m b e r ) 4 3 2 节) 。这两种方法分别以每个类别获得的类偏向度、特征个数的方差最小为 目标，修正了传统方法造成的特征对类别的偏向程度不一致的问题。在搜狐门户 网站的新闻库数据上的实验证明，本文提出的两种新算法，比传统算法的分类性 能要更好。 关键词：网页分类，特征提取，互信息，m i d n ，b b sn ，b b s s 中山大学硕士学位论文 d i s c u s s i o no ff e a t u r ee x t r a c t i o nf o rc h i n e s e 、b p a g ec a t e g o r i z a t i o n m a j o r ：a p p l i e dm a t h e m a t i c s n a m e ：l i a n gy o n gj i a n g s u p e r v i s o r ：z h a n gl e i a bs t r a c t w i t ht h er a p i dd e v e l o p m e n to fi n t e m e t ，w e bp a g ec l a s s i f i c a t i o nt e c h n o l o g y b e c o m e sm o r ea n dm o r ei m p o r t a n t ，w h i c ho r g a n i z i e sw e bp a g e se f f i c i e n t l ya n d e f f e c t i v e l yb yc l a s s i f i n gw e bp a g e sa u t o m a t i c a l l y i tp h y sa ni m p o r t a n tr o l ei nm a n y f i e l d ss u c ha ss e a r c h i n ge n g i n e ，i n f o r m a t i o nf i l t e r i n g ，e t c t h e r ea r ea l w a y st e n so ft h o u s a n d so ff e a t u r e si nw e bp a g e w h i c hm a k e s c l a s s i f i c a t i o nad i f f i c u l tj o b t h e r e f o r e ，f e a t u r es e l e c t i o nb e c o m e sak e ys t e pb e f o r e c l a s s i f i c a t i o n t h et r a d i t i o n a lf e a t u r es e l e c t i o na l g o r i t h mh a st w od i s a d v a n t a g e s ：1 ) t e n dt ol o wf r e q u e n c yw o r d sa n ds m a l l s a m p l ec a t e g o r y ，2 ) j u s ts e l e c t i n gf e a t u r e s w i t ht h em a x i m u ms c o r eo n eb yo n e ，w h i l ei g n o r i n gt h ei n f l u e n c et ot h e c a t e g o r i z a t i o no ft h eg r o u po ff e a t u r e s ，a n da sr e s u l to ft h a t ，e a c hf e a t u r ei so p t i m a l , w h i l et h ef e a t u r es u b s e tn o t t h em a i nc o n t r i b u t i o n so ft h i sp a p e ri n c l u d e ：1 ) p r o p o s i n gan e wm e a s u r e ，m i d n m e a s u r e ( i ns e c t i o n4 2 2 ) ，o nt h eb a s i so fm u t u a li n f o r m a t i o n ( m i ) m e a s u r e ，2 ) p r o p o s i n gt w on e wf e a t u r es e l e c t i o na l g o r i t h m s ：b b s sa n db b s na l g o r i t h m ( i n s e c t i o n4 3 2 ) t h eo b j e c t i v eo ft h ef o r m e ri st om i n i m i z et h ev a r i a n c eo fb i a sd e g r e e o fc a t e g o r i e s ，a n dt h eo b j e c t w eo ft h el a t t e ri st om i n i m i z et h ev a r i a n c eo ft h en u m b e r o ff e a t u r e s e x p e r i m e n t so nw e bd a t a s e t ss h o wt h a tt h et w on e wa l g o r i t h m sh a v e b e t t e rp e r f o r m a n c ei l lc l a s s i f i c a t i o nt h a nt h eo r i g i n a lo n e k e yw o r d s ：w e bp a g ec a t e g o r i z a t i o n ，f e a t u r ee x t r a c t i o n ，m u t u a li n f o r m a t i o n , m i d n ，b b s _ s ，b b s _ n m 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的作品成果。对本文的研究作出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：刃黎永江 日期：z 彳矿年 月2 矿日 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保留 学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权将学 位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查 阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩印或其 他方法保存学位论文。 学位论文作者签名：黎永汇 日期：叫口年j 月工矿日 日 中山大学硕士学位论文 1 1 研究背景 第一章绪论 1 1 1 网页分类技术的应用 i n t e r n e t 的出现，使得数据资源以前所未有的方式和速度在全球内传播共享， w e b 上的网页数据量呈几何指数倍增长。文献【1 】指出，截止2 0 0 8 年，o o o g l e 索 引的网页数量已经达到一万亿，而c n n i c ( 中国互联网络信息中心y 2 】第2 3 次报 告称，国内的网页总数超过1 6 0 亿个，较2 0 0 7 年增长9 0 。 面对如此丰富的w e b 数据，我们面临一个新的挑战：那就是如何准确、快速 地找到我们想要的信息? 目前处理w e b 数据的最广泛的手段是i n t e m e t 的搜索引 擎( “g o o g l e ”、“b a i d u ”、“y a h o o 等) 。但是，目前基于关键字的搜索方式存在一 些问题，例如，对任一关键字的搜索，都可能导致返回成百上千的文档，但是其 中很多文档与主题的相关性不大，或者所包含的内容质量不高，不是我们想要获 取的东西。因此，现在的i n t e r n e t 搜索引擎的查全率、查准率都不尽如人意，并 且不能发现w e b 数据背后蕴藏的知识。 分类作为数据管理的一种有效手段，在组织和处理海量的w e b 数据方面上扮 演了关键的角色。网页分类技术是传统文本分类技术的延伸，能够根据需求自动 将网页数据归类，从而帮助人们更好地组织数据、挖掘决策数据、提高使用数据 的质量。具体来说，网页分类技术可以应用于： ( 1 ) 构建、扩展网页目录的结构( w e b 网页目录层次) 现有的w e b 目录，例如y a h o o ! 和d m o z 的o d p 3 l ( o p e nd i r e c t o r yp r o j e c t ，开 放式目录) 项目，为信息检索提供了一种方便的途径，人们可以在预先设定的目 录中找到需要的信息，避免了盲目性。到目前为止，这些目录主要是由人工进行 中山大学硕士学位论文 维护的。截止2 0 0 8 年2 月，有7 8 ，9 4 0 个编辑者在维护o d p 项目。而随着w e b 信息的变动和增长，单靠人工进行维护这些w e b 目录显得越来越低效。为此， 学者们开始研究如何利用分类技术自动更新和扩展w e b 目录。h u a n g 等人【4 】提出 了一种基于用户定义的目录自动建立分类器的方法，然后将分类器应用于更新扩 展w e b 目录。随着对分类技术的深入研究，分类器将能够自动产生自定义甚至 动态的w e b 目录层次。 ( 2 ) 提高信息搜索的质量 模糊查询的一个问题是降低了查询结果的质量。例如，在中文检索中，提交 一个“人大”词项的查询，返回的结果可能既有关于“全国人民代表大会 ，也 有关于“中国人民大学 之类的，这是因为词项“人大 既可以指示为“人民代 表大会 ，也可以指示为“中国人民大学 。为此，可以利用网页自动分类技术， 由已知类别的网页训练一个分类器，将新的网页进行归类。当用户进行检索时， 在预定义的类别目录中进行检索，搜索引擎会将类别下的网页返回给用户，由此 降低检索的模糊性，提高搜索结果的准确率。 ( 3 ) 辅助问题解答系统 一个问题解答系统可以通过分类技术提高答案的质量。例如，给出一系列问 题，形成一个个查询，交由搜索引擎进行回答。然后搜索引擎搜索出大量网页， 并且将网页分到3 个类别：主题网页( 解答方案) 、相关网页( 与解答方案相关) 、 不相关网页。为了搜索到更多的主题网页，可以从相关网页的“出链接”中找到 更多的主题的网页，然后从主题网页的聚类结果中提取出答案。 ( 4 ) 建立一个高效的主题爬虫或者垂直搜索引擎 为了获取某些特定领域的信息而进行全网抓取是低效的，而采用主题爬虫进 行局部抓取将更有效率。为此，训练一个分类器对网页进行按主题分类，为抓取 的范围提供依据，这样就只会抓取那些我们想要的网页。 1 1 2 网页分类建模的难点是特征提取 当对网页使用分类技术时，为了便于对不同网页进行相似性比较，网页必须 有一种数据化的表示，即特征向量。特征向量中应该体现网页的各种信息，包括： 2 中山大学硕士学位论文 网页正文；超链接信息；网页元标签；网页的目录结构信息。其中，与 网页主题相关的超链接信息、网页标题、元标签含有重要的分类信息。 实现网页分类的一个难点是维数灾难问题，即特征向量的维数通常多达数 万，这使得计算复杂度增加，同时冗余特征的存在又使得分类准确率降低。 特征提取就是为了解决这类问题而产生的一门技术。特征提取就是从所有特 征中挑选出对分类最有效的特征，从而实现降低特征空间维数的目的。 1 1 3 本文选择特征提取为研究主题 如何从高维特征空间中选择最有价值的特征是一个重要的研究课题。互信息 ( m u t u a li n f o r m a t i o n ，m i ) 5 1 是文本分类中常用的特征度量方法，但传统的互信息 方法过分倾向于低频词和小样本类别，降低了抽取出的特征的质量。为此，本文 以词项的类文本次数对m i 特征度量加以修正，提出m i d n 特征度量，并通过实 验比较m i d n 度量和z 2 统乇t l t 6 1 ( c h i ) 的分类效果，实验表明：m i d n 和c h i 的 分类效果相当；它们与传统的m i 度量相比，都有较大的提高。 传统的特征选择方法只是简单按特征度量的分值进行选取具有最大分值的 特征，忽略了特征的组合对类别的偏向程度，导致单个特征较优，但组合起来却 未必是最优模型，降低了分类模型的准确率。为此，本文提出b b ss ( b i a s b a l a n c e ds e l e c t i o nb ys c o r e ) 和b b sn ( b i a sb a l a n c e ds e l e c t i o nb yn u m b e r ) 算法， 统称为b b s 特征选择算法。这两种算法分别以类别的度量分值和类别的特征个 数作为选择方向，使得每个类别获得的度量分值或者特征个数的方差最小，达到 偏向修正的目的。 1 2国内外研究状况 1 2 1 文本分类研究状况 网页分类是组织和利用海量w e b 数据的重要手段，它的基础是文本分类技 3 中山大学硕士学位论文 术。文本分类的研究开始于上世纪5 0 年代末，1 9 6 0 年，m a r o n 在j a c m 7 1 上发 表了有关文本分类的第一篇论文。随后，很多学者在这一领域进行了扩展研究。 在2 0 世纪9 0 年代前，主流的文本分类方法一直是基于知识工程( k b e ，k n o w l e d g e b a s e de n g i n e e r i n g ) 的，是由专业人士进行人工分类，导致成本高而且效率低下。 后来，随着统计方法和机器学习知识的引入，使得自动智能分类成为文本分类的 主要发展方向。 目前常用的文本分类模型包括：朴素贝叶斯分类模型1 8 l ( n a i v eb a y e s ，n b ) ； 神经网络模型9 ，1 0 ，1 1 ，1 2 ( n n e 0 ；支持向量机模型【1 3 1 4 ，1 5 ，1 6 1 ( s v m ) ：k 最近邻 模型【1 7 ，1 8 】；决策树模型【1 9 , 2 0 l ；基于规则的分类模型 2 1 , 2 2 j ；l l s 一2 3 】模型等。 y a n g 和l i u 【2 4 】对n b 、n n e t 、s v m 、心、s v m 、l l s f 模型进行实验，实 验结果表明：s v m 的分类精度较高，n b 的运算时间最少，而k n n 模型实现简 单且分类准确率较高。 1 2 2 网页分类研究状况 网页分类的研究始于上世纪9 0 年代，它的兴起是由于互联网的飞速发展。 由于文本自动分类的研究相对较早，而且已经研究出比较成熟的技术，因此有不 少的研究工作是将文本分类的技术应用到网页分类上。f u m k r a n z 2 6 】用“指向该 网页所有链接周围的文本 、“链接所在段落的标题 、“上级标题文本 三种特征 表示网页，并用r i p p e r 算法对文本进行分类，准确率比仅使用网页局部文本的 方法提高了2 0 ；o h 等人【2 6 】结合文本相似性选择了部分跟原网页较接近的网页 文本，试验结果e 值比使用所有链接网页提高了7 。 k a n 和t h i 2 7 】利用文本和u r l ( 统一资源定位符) 作为特征，用于对学校的站 点网页进行分类。由于分类对象是学校站点，所以他们只需分类很少类别，如院 系、课程、学生以及科研网页等。然后采用最大熵方法过滤特征，采用s v m ( 支 持向量机) 作为分类模型进行分类网页。 些研究工作集中在分类网页的层次结构。y a n g 和l e e 冽利用文本挖掘工具， 用于识别网页集合的一些重要话题，目标是要自动产生网页的目录以及它们的结 构。他们利用s o m ( 自组织映射) 神经网络模型聚类网页，然后利用一个递归过程， 4 中山大学硕士学位论文 产生出特定话题的层次结构。 一些学者应用r e l i e f f 2 9 , 3 0 】算法到自动分类技术中。等人利用r e l i e f f 算 法和隐贝叶斯模型分类网页。他们基于r e l i e f f 决策树找出相关的特征词以提高 网页分类的性能。找出相关特征后，在隐贝叶斯结构中为每个特征创建一个隐父 节点，其中隐父节点受所有特征影响。 x u 等人1 3 2 1 提出一个融合多数据源的网页分类框架。通过一个核函数，每个 数据源表示成一个核矩阵，这个矩阵可以看成是所有网页之间的泛化相似性矩 阵。然后数据的融合就转成了核矩阵的组合。最后，将融合后的核矩阵用到基于 核的分类算法上。 1 2 3 特征提取研究状况 特征提取是网页分类的一个关键步骤。在网页自动分类中，通常要处理数百 万的网页，数万的特征以及成百上千的类别。特征个数太多对网页分类的训练时 间、分类准确性都有不好的影响，分类器算法的时间复杂度、空间复杂度会随着 特征空间维数的增加而呈指数增加。 目前，在文本分类领域中，有几种常用的特征度量方法，包括：文档频率 ( d o c u m e n tf r e q u e n c y ，d f ) 3 3 】；信息增益( i n f o r m a t i o ng a i n ，i f ) 1 3 4 1 ；互信 息( m u t u a l i n f o r m a t i o n ，m i ) 【5 1 ；z 2 统计量( c h i ) 1 6 ；期望交叉熵( e x p e c t e d c r o s se n t r o p y ) 3 5 1 ；术语强度( t e r ms t r e n g t h ， is ) 1 3 6 】；优势比( o d d sr a t i o ) 3 3 l 等等。 y a n g l 3 7 】等人对多种特征度量方法进行测试，实验表明，c h i 和i g 的效果最 好，m i 的效果最差。y a n g 等人的实验结论是基于英文文本，用于中文文本时结 论是否同样成立，目前还没有明确的定论。为此，不少学者对上述特征度量方法 进行研究、比较，并取得一定的成果。包括：n g 【3 8 1 等人认为仅用本类别文本中 的高频词作为特征，能取得很好的分类效果，于是他们对c h i 方法进行了改进， 得到“c o r r e l a t i o nc o e f f i c i e n t 方法。g a l a v o t f i 等人1 3 9 1 在此基础上，提出了一种更 为简化的z 2 统计量度量。另外，针对互信息度量过分倾向于“低频词”、忽略了 5 中山大学硕士学位论文 有用的“高频词 缺点，谭金波【删等在互信息度量上加入词项出现的概率，增 加“高频词 的权重，得到改进的互信息度量( m i p w ) 。王秀娟【4 1 】等采用了如下 方法：求特征对各类贡献的信息量的最大值和次大值之比，用以计算特征对各类 贡献的信息量，比值越大，说明特征的分类能力越强。 综上所述，网页分类技术已经得到越来越广泛的研究，针对网页本身半结构 化数据和高维特征空间等特点，选取具有最大相关性的网页内容作为特征，以及 选出对分类有贡献的特征，可以明显提高网页分类的“准确率 和“召回率， 改善用户的检索质量。为此，本文对特征度量和特征选择算法进行研究，提出 m i d n 特征度量以及b b ss 、b b sn 特征选择算法，提高网页分类的性能。 1 3 本文的主要工作及创新之处 本文首先介绍网页分类的一般过程，常用的文本特征选择算法以及k n n 分 类模型等。然后，针对网页半结构化的特性，提出以“网页标题”、“m e t a 中的 关键字和描述字段 、“正文 以及“相关链接信息”作为依据来设计网页特征向 量，并给出相应网页特征的提取算法。 传统特征提取方法存在两个明显的不足：其一，传统的m i 度量方法过分倾 向于低频词和小样本类别，降低了抽取出的特征的代表性。其二，传统的特征选 择方法只是简单按特征度量的分值依次选取具有最大分值的单个特征，忽略了特 征的组合对类别的偏向程度，导致单个特征较优，但组合起来却未必是最优模型， 减低了分类器的性能。 本文的主要创新之处在于，在m i ( f f 信息) 度量的基础上提出一种新的度量 m i d n 特征度量( 定义见4 2 2 节) ，并提出两种新的特征选择算法：b b ss ( a i a s b a l a n c e ds e l e c t i o nb ys c o r e ) 和b b s _ n ( b i a sb a l a n c e ds e l e c t i o nb yn u m b e r ) 算法。 这两种算法分别以每个类别获得的类偏向度、特征个数的方差最小为目标，修正 了传统算法造成的特征对类别的偏向程度不一致的问题。在搜狐门户网站的新闻 库数据上的实验证明，本文提出的两种新算法，比传统算法的分类性能要更好。 6 中山大学硕士学位论文 1 4 本文的组织结构 第一章绪论，简要介绍网页分类的背景及应用、国内外研究现状，本文的 主要工作和组织结构。 第二章中文网页自动分类技术，介绍网页分类的定义、处理步骤、网页表 示模型、特征提取方法、k n n 分类模型以及文本分类模型评价指标。 第三章本文实现的网页特征提取算法，介绍本文提出的中文网页正文特征、 标题特征、元标签特征、相关链接信息特征的提取方法。 第四章m i d n 特征度量和b b s 特征选择算法的提出，分析m i 度量过分倾 向于低频词和小样本类别等缺点，提出m i d n 特征度量。针对传统特征选择算 法造成各类获得的类偏向度和类特征个数不均衡的缺陷，提出b b ss 算法和 b b s n 算法。 第五章实证分析，以搜狐新闻库作为实验数据，对本文提出的m i d n 度量 的效果和b b s 特征选择算法的有效性进行实证分析。实验证明，本文提出的两 种新算法，比传统算法的分类性能要更好。 第六章总结，对全文进行总结，说明论文的主要工作、创新点以及存在的 不足，并提出未来的研究方向。 7 中山大学硕士学位论文 第二章中文网页自动分类技术 2 1 网页分类定义 网页分类，顾名思义，就是将网页分到一个或多个已知的类别的过程。它是 将分类技术应用于网页而产生的- - f 技术。分类是一种有监督学习的方法【3 4 1 ， 它利用已分类的样本对分类器进行训练，然后利用分类器分类未知类别数据的一 种技术。 网页分类的目的，是寻找函数西：d x c 一 t r u e ，f a l s e ，希望通过这个函数， 能将任意一个网页尽可能准确地分类。这里，d p 。，d ：，d i d l 卜一文档集合； c - 忙。，c ：，c l c l 卜类标集合。函数也称为分类器，它是根据已掌握f 拘i j i l 练 集的信息，总结出分类的规律而建立的判别公式和判别准则。 网页分类问题可以划分为几个子问题：主题分类；功能分类；情感分 类；其它类型的分类( 见图2 1 ) 。主题分类是一般意义上的分类，它关心的是 网页所属的主题。例如，判断一个网页是关于“艺术 、“商业 、“体育 、“健康” 等是属于主题分类。而功能分类关心的是网页扮演的角色。例如，描述一个网页 时它是一个“个人网页 、“课程网页”还是“商业网页 是属于功能分类。而情 感分类关注的是一个网页表达的观点，即作者对某个特别话题的态度、观点。其 它分类类型包括体裁分类【4 2 j 等。 根据类别的个数来分，分类问题可以分为：两类分类问题；多类分类问 题。其中两类分类问题就是将网页分到两个类上( 见图2 - 2 ( a ) 所举的实例) ，往往 将两类分别称为正例和负例；而多类分类问题即是类别个数大于2 的情形( 见图 2 - 2 ( b ) 的实例) 。 根据一个网页可以隶属的类别个数来分，网页分类可以分为：单类标分类； 多类标分类。在单类标分类问题中，每个网页仅可以赋予一个类别；然而在多 8 中山大学硕士学位论文 类标分类问题中，每个网页可以赋予一个以上的类别。例如，在多类标分类问题 中，假设有4 个类别：艺术、财经、i t 、体育，这时，每个网页可以是单类标的， 4 个类别中选其中个( 见图2 - 3 ( a ) f l 勺实例) ，也可以多类标，网页可同时属于两 个以上类别( 见图2 - 3 ( b ) 的实例) 。 根据类别指派的模糊性来分，网页分类可以分为：硬分类；软分类。在 硬分类中，每个网页属于某个类别没有模糊性，只有属于和不属于两种可能，没 有其它的中间状态。而在软分类中，每个网页属于某个类别有一个隶属度值，表 明这个网页属于这个类别的可能性( 见图2 - 3 ( c ) 的实例) 。 从类别的组织来分，网页分类也可以分为：平等分类；等级分类。在平 等分类中，类别之间是平等的，没有父类别或者子类别。而在等级分类中，类别 组织成一棵树状结构，每个类别可以有数个子类别( 见图2 4 的实例) 。 图2 1 网页分类子问题类型 ( a ) 两类分类 甲 网页分类器 3 图2 - 2 两类和多类分类 9 ( b ) 多类分类 中山大学硕士学位论文 i i i网页集l | il l l 广 l 网页分类器 i li i网页集i i l阻 l 上 i 网页分类器 回圈圈慝习 i 一 ( a ) 单类标的多类分类( b ) 多类标的多类分类 i 。ll i 网页集l i l阻 l i + l 网页分类器 ( c ) 多类，软分类 图2 3 单类标和多类标分类 1 0 中山大学硕士学位论文 ( a ) 平等分类 ( b ) 等级分类 图2 4 平等和等级分类 2 2 中文网页自动分类的一般步骤 网页自动分类的核心是训练一个分类器，从数学上说就是根据样本信息，得 到一个或多个决策函数，或者得到一个决策规则的集合。训练分类器的主要过程 是：训练和分类。所谓“训练 ，就是以已标有类标的网页特征向量作为训练集， 建立网页和预先定义的类信息的映射关系。然后用已训练好的分类模型对未知类 标的网页进行分类。概括起来，网页分类主要包括如下步骤：预处理；特征 提取；分类器训练；分类；性能评估。这个过程见图2 5 所示。 中山大学硕士学位论文 训练集 1 1 r 终止 图2 - 5 网页分类一般步骤 1 2 中山大学硕士学位论文 2 3 文本表示模型 网页采用超文本编写，是一个由各种各样的字符组成的字符串集，无法 直接为学习算法所学习、训练。因此，为了能将机器学习方法用于网页分 类问题中，首先需要将网页转为学习算法易于处理的形式。现在常用的网 页表示方法有：布尔模型【4 3 l ( b o o l e a nm o d e l ) 、概率模型【4 4 l ( p r o b a b i l i s t i c m o d e l ) 、向量空间模型【4 5 j ( v e c t o rs p a c em o d e l ) 等。 2 3 1 布尔模型 布尔模型【4 3 】是基于布尔代数和集合论的一种简单检索模型，它的特征向 量是以关键词出现与否来表示文本内容。布尔模型定义了一个以二值变量 为元素的向量来表示文本，这些变量对应于文本中的特征项( 文本集中词项 和词组) 。若某特征项在文本中出现，则该特征项所对应的变量的值为1 ， 否则为o 。定义式如下所示： d fi ( m 1 ，心2 ，w a ，m r ) ，k 一1 ，2 ，t ( 2 - 1 ) 其中t 是特征个数，为0 或者1 ，表示第k 个特征在文本i 中是否出现。 布尔模型的主要优点是形式简单，而缺陷是文本表示能力有限，无法区分特征项 对文本内容的重要程度，因匹配过于严格而导致过多或者过少的文本匹配，用于 分类时准确率和召回率较差。 2 3 2 概率模型 信息检索中往往不能确切地了解到与文本相关的属性，而且检索信息表示往 往具有模糊性，为此，人们尝试运用概率方法解决这方面的问题。概率模型【4 4 1 度量词与词间的相关性，识别出文本集中的与文本分类相关的文本和不相关的文 本。它以概率论为理论依据，通过赋予词项某种概率值表示这些词在“相关文本 中山大学硕七学位论文 和“不相关文本”中出现的概率，然后计算文本间相关性概率，根据这个概率值 做出决策。 设文本d 和用户查询q 用二值词项 f i - j 量( a ，a ：，口r ) 表示，当词项d 时，口，= 1 ，否则a ，；0 。文本d 和查询q 的关联公式为： 跏( d ，q ) 一渊 ( 2 2 ) 其中，p ，。兰，q ；。盟。n 是训练集中文本总数，r 是与用户查询相关 的文本数，仇是训练集中包含词项t 的文本数，r a 是r 个相关文本中包含词项的 文本数。 概率模型1 4 4 】的优点在于，文本可以按照它们的相似度大小进行排序。缺点在 于，没有考虑词项在文本中的频率，而且没有考虑词项间的相关关系。 2 3 3 向量空间模型 向量空间模型【4 5 】是由s a l t o n 等人在2 0 世纪6 0 年代提出，并应用到了 s m a r t 系统中。该模型的相关技术，包括“词项选择”、“特征加权策略 ， 以及用于优化查询的“相关反馈”等。这些技术在文本分类、信息检索、 数据库索引等许多领域得到了广泛应用。随着万维网上数据的迅速膨胀， 它被广泛应用到搜索引擎设计、网页自动分类等新的领域，并且取得了很 好的效果。 向量空间模型1 4 5 l 的基本思想是利用相似度表示文本内容间的相关程度。 在向量空间模型中，每个文本可以表示为如下向量： y ( d ) 一 o ，暇( d ”；o 。，睨( d ) ) 】-( 2 - 3 ) 其中t ；是特征项，形 ) 是t i 对应权重，反映特征t ，对识别文本d 的重要程度。 向量空问模型【4 5 】把文本简化为以“项的权重 为分量的向量表示，把分 类建模表示为向量空间的运算，大大减少了问题求解的复杂性。此外，向 1 4 中山大学硕士学位论文 量空间模型对词项权重的评分以及相似度估算没有做统一的规定，只是提 出一个一般的理论框架，使得对不同的数据可以采用的相应的权重评价方 法和相似度计算方法，使得这个模型有广泛的适应性。不过，向量空间忽 略了词项出现的顺序，尽管带来了计算上的简便，却损失了有用的文本结 构信息，缺乏对文本语义上的理解。 2 4 特征提取的常用方法 网页分类建模中特征个数通常多达数万。特征提取不但能避免维数灾难 问题的出现，降低分类算法的计算复杂度，也能提高分类的准确率。为此， 本节重点介绍网页分类中的特征提取方法。 2 4 1 特征提取定义 特征提取可以看作是一个最优化搜索问题，目标是选择最优的特征子集。 可以形式化表示为： ) ，：x ”- x 4 ，d 预测类标 类c非类g 实际类标 类c i z p v 豫职f n 一 刚； 非类c f 即。善鹧 掰- 善巩 贸 中山大学硕士学位论文 表2 - 4 微平均和宏平均下的准确率、召回率、墨指标 微平均宏平均 准确率n t p 。善喝 n 翌 t p + f p 羹+ 冠) 召回率堡。善职 _ e r r e 一! = ! t p + f n 薹( 职+ 吼) f l 指标 2 善r e t e 。翌局一。p r i ( p + r e ；) 中山大学硕七学位论文 第三章本文实现的网页特征提取算法 网页内容包含的信息很丰富，包括网页标题、网页主题内容、大量的图 片和视频信息、广告信息、导航链接等等。合理利用这些信息可以提高网 页分类的性能。本章主要介绍这些网页特征的提取方法，为分类作好准备。 3 1 正文之外的网页特征 网页以h t m l 的格式编写，使得除了在浏览器上可见的文本内容，它 还包含h t m l 标签、超链接以及锚文本( 在标签 和 之间的文本) 。网 页上可作为分类特征的对象包括： ( 1 ) 网页文本以及标签 在浏览器上可见的网页主题内容是最直接的网页特征，除此之外，网页 的h t m l 标签也可以作为网页特征，如网页标题、元数据中的描述文件( m e t a n a m e = d e s c r i p t i o n ) 、元数据中的关键词( m e t an a m e = k e y w o r d s ) 等。 ( 2 ) 视觉分析 由浏览器显示出来的视觉表示也可作为网页的特征。文献【4 9 】中将网页 表示为一个“视觉关联多重图 。在图里面，每个节点代表一个h t m l 对象， 每条边表示视觉表示中的空间关系。基于视觉上的分析，可应用一些启发 性规则来识别网页中的不同的区域。 ( 3 ) 网页u r l u r l 是w w w 上网页的一个标识，拥有相同u r l 前缀的网页属于同一 个网站，如果相同的前缀越长，它们属于同一个类别的可能性越大。 ( 4 ) 网页链接信息 网页链接信息是网页区别于纯文本的重要特征。在提取链接信息前，首 先检测被链接网页和链接网页是否具有相关性，与网页标题相关的链接被 中m 大学硕学位论文 提取出来作为网页特征，不相关链接则被过滤。 ( 5 ) 邻近网页的信息 由超链接关联的两个网页具有链接关系。因此，可以提取邻近网页的特 征作为本网页的特征。网页可以组织成一颗树状结构，邻近的网页的关系 包括：父节点、子节点、兄弟节点、祖父节点和子孙节点。 本文以网页中包含的标题、元数据中的描述和关键字、正文以及链接信 息作为特征进行分类。下面几节中，我们将依次介绍上述这几种特征分别 对应的提取方法。 3 2 网页标题和元数据特征提取 下面以一个新浪体育的网页源代码作为示例，介绍网页标题和元数据特 征提取的算法思想。源代码如圈3 1 所示 f _ - l l t j 一町n 。哗商罔华商晨报“一 f - 一l l t jz t ：u r l “h t t p ：s p d r t s s l n a o mc n g a i f b e l j i n g a r t i s t g n z f i n d e xs ；一。 泌t i t li鎏瓣g!黧漾鬻黧豁婕黼黼|9赫辫瓣拶tdescr。ptlonc o n t e 。 呐- t 一巫启贤辱黄晓明政外生括投资高乖夫与红酒嫦”) 。( 1 1 。n 。k ：嚣篇嚣。t ，y p e - 。a p p 。l i 。c a t 。t 。o 。n r ，s s * 。x 。l n t i 。t l e - , 粼喜盔；娣矿。e f - ，h t 。t p 。：l i ( s c r i p tt 9 p e t e x t l j - u a s c r i p t “5 c h t t p ：i a s i n a l m 9 c n h o _ l s i n a f l a s h j s ” s c r 2 p tt ，p p “t e x t ，扣u a s c r i p t ”5 r c “h t t p ：，s i n a c o c n ，i f ，8 7 ，2 口 h c o n t e n t 】! ，处理页面广告内容s t a r t - t p i a g f o e 印p u “：1 即1 8 l ：”2 ”州一1 1 ；7 7 碲8 髑，需要检测的日期差单位，无 。 图3 - 1 网页源代码文本显示 中山大学硕十学位论文 网页标题总是放在标签h e a d 里面的 和 之间，因此可以编 写正则表达式 ( 幸? ) 提取出标题内容c o n t e n t ，然后在c o n t e n t 中 找到最后一个“一”或者“ 字符，去掉其后的字符，这是因为末尾字符通 常是标识网站，如“新浪网 等，对分类并无意义。 算法流程图如下： 匹配 ( 宰? ) 占 以字符“_ ”分裂得到匹配字 符串，得到k 个字串 上 将前k - 1 个字串合并得到标题内容 i r 终止 图3 - 2 标题特征提取流程图 类似标题特征的提取方法，元数据的d e s c r i p t i o n 和k e y w o r d s 也可以通 过编写正则表达式抽取得到。算法流程图如下： 匹配 上 在得到的匹配结果c o n t e n t 上 继续匹配c o n t e n t - “( + ? ) 上 将得到的最终匹配项保存 上 r 终止 、 i 兀f f d 上 在得到的匹配结果c o n t e n t 上 继续匹配c o n t e n t f f i “( ? ) 上 将得到的最终匹配项保存 i 厂、 ( 终止 ) 图3 - 3m e t ak e y w o r d s 和d e s c r i p t i o n 特征提取流程图 中m 大顽学位论女 对图3 - 1 所示的嘲页源代码，进行网页标题和m c t a 数据特征提取，得 到的结果见图3 - 4 。 ( a ) 网页标题提取结果 f b ) m e t a 数据提取结果 图3 4 网页标题和m e t a 数据特征提取结果 3 3 网页正文特征提取 目前应用最为广泛的w e b 数据库抽取技术是网页包装( w r 8 p p e r ) 方法 构造一个稳定的w r a p p e r 技术难度大而且需要很长时间。故本节介绍另一种 简单快捷而且准确度较高的方法，用于提取网页正文特征。 通常情况下，网页的正文的长度总是会超过其他特征( 如标韪) 的长度。 也有例外的情况，如视频、图片网页，它的正文往往只有一句话。在这种 情况下以标题作为正文内容。 在介绍正文特征提取方法前，先介绍h t m l p a r s e r 如】这个纯i a v a 写的h t m l 解析库。h t m l p a r s e r 的基本功能包括：信息提取；信息转换。它可以对 h t m l 进行有效的信息检索，提取出我们想要的文本信息、链接信息等。 h t m l p a r s e r 主要有三种节点：r e m a r k n o d e ，表示h t m l 的注释； t a g n o d e ， 标签节点； t e x t n o d e 文本节点。h t m l p a r s e r 的节点类继承关系见图3 - 5 。 中山大学硕士学位论文 图3 - 5h t m l p a r s e r 的节点类继承关系图 其中，本文用到的几个t a g 节点的意义见表3 - 1 。 表3 1 几个t a g 节点意义 t a g 节点 意义 t a b l c ：t a b h t m l 中以 标签标识的表格块 d i vh t m l 中以 标签标识的d i v 块 p a r a g r a p h t a gh t m l 中以 标签标识的段落块 l i n k t a gh t m l 中以 标签标识的超链接块 s c r i p t t a gh t m l 中 标签标识的脚本块 利用h t m l p a r s e r 解析网页内容时，最长的正文一般放在t a b l c t a g 、d i v 或者p a r a g r a p h t a g 里面。为此可以找出d i v 、t a b l e t a g 、p a r a g r a p h t a g 块中 最长文本作为正文。这样处理会有一个问题，即经常会有一些h t m l 元素 的长度超过正文的长度，如“ s c r i p t ( * ? ) 之间的脚本内容。为此， 在解析一个网页前，首先要把这些脚本代码去掉。总的来说，本文的正文 特征提取算法的基本步骤是： 步骤一：去掉网页中“ s c r i p t ( ? ) 之间的脚本文本； 中山大学硕士学位论文 步骤二：遍历由h t r n l p a r s e r 解析后的节点树，找出长度最大的t a b l e t a g 、 d i v 或者p a r a g r a p h t a g 块。 正文特征提取算法是一个递归的过程，算法流程图见图3 - 6 。 图3 6 正文特征提取流程