（计算机科学与技术专业论文）基于rbf神经网络的网页分类技术研究.pdf

卢乒j 附r at h e s i ss u b m i t t e df o r t h ed e g r e eo fm a s t e r c a n d i d a t e ：s h ig u o q i a n g s u p e r v i s o r ：p r o f l ic u n h e c o l l e g eo fc o m p u t e r & c o m m u n i c a t i o ne n g i n e e r i n g c h i n au n i v e r s i t yo fp e t r o l e u m ( e a s tc h i n a ) 一 。 _ 关于学位论文的独创性声明 本人郑重声明：所呈交的论文是本人在指导教师指导下独立进行研究工作所取得的 成果，论文中有关资料和数据是实事求是的。尽我所知，除文中已经加以标注和致谢外， 本论文不包含其他人已经发表或撰写的研究成果，也不包含本人或他人为获得中国石油 大学( 华东) 或其它教育机构的学位或学历证书而使用过的材料。与我同工作的同志 对研究所做的任何贡献均已在论文中作出了明确的说明。 若有不实之处，本人愿意承担相关法律责任。 学位论文作者签名：建! 坌狐日期：。7 o i l 年5 月2 9 日 学位论文使用授权书 本人完全同意中国石油大学( 华东) 有权使用本学位论文( 包括但不限于其印刷版 和电子版) ，使用方式包括但不限于：保留学位论文，按规定向国家有关部门( 机构) 送交学位论文，以学术交流为目的赠送和交换学位论文，允许学位论文被查阅、借阅和 复印，将学位论文的全部或部分内容编入有关数据库进行检索，采用影印、缩印或其他 复制手段保存学位论文。 保密学位论文在解密后的使用授权同上。 学位论文作者签名：塞亟鍪 指导教师签名：兰壅三丝公 同期：多d 年5 月x 日 日期：尹f 年5 月刀日 摘要 随着i n t e m e t 的普及，网络已经成为人们获取信息的主要途径，为了帮助人们从海 量网页中获取有用的信息，网页自动分类技术应运而生，其可以快速有效地分析和组织 海量网页信息，它是利用机器学习的方法对网页实现自动类别标注。在众多网页分类算 法中，r b f 神经网络因其出色的分类能力，成为机器学习的研究热点。 介绍了网页分类的流程，分析了r b f 神经网络技术发展、原理和相关技术，讨论 了r b f 神经网络在网页分类中的重要作用。阐述了目前r b f 神经网络常用训练算法， 研究了在多实例多标签框架下发展而来的m i m l r b f 神经网络模型。针对m i m l r b f 在不平衡样本下分类效果差的问题，提出了改进的训练算法，考虑了样本的整体分行情 况，使各类上产生的隐含层神经元趋于平衡，减少了不平衡样本对网络模型的影响。 针对s v d 方法在含有噪声数据的样本集上会导致网络整体误差变大的问题，提出 了基于最速下降法优化的权重训练算法，使用s v d 方法初始化权值矩阵，采用最速下 降法优化权值矩阵，并利用新权值矩阵的误差平方和函数计算学习率矩阵，提高了 m i m l r b f 神经网络在含有噪声数据的样本集上的分类精度。 最后，将改进后的训练算法应用到网页分类系统中，并对改进算法进行了实验对比 和性能分析。实验数据表明，本文算法具有更高的分类效率和准确率。 法 关键词：m i m l r b f 神经网络，网页分类，不平衡样本集，奇异值分解，最速下降 t h er e s e a r c ho fw e bp a g e sc l a s s i f i c a t i o n b a s e do nr b fn e u r a in e t w o r k s h ig u o q i a n g ( c o m p u t e rs i c e n c ea n dt e c h n o l o g y ) d i r e c t e db yp r o f l ic u n h e a b s t r a c t w i t ht h ep o p u l a r i t yo ft h ei n t e r a c t ，t h ei n t e r n e th a sb e c o m et h em a i nw a yp e o p l eg e t i n f o r m a t i o n w e bp a g e sc l a s s i f i c a t i o nc a l la n a l y z ea n do r g a n i z em a s s i v ew e bp a g e sq u i c k l y a n de f f i c i e n t l y ，i ti sak i n do fm a c h i n el e a r n i n gm e t h o d st h a ta s s i g nl a b e l st ow e bp a g e s a u t o m a t i c a l l y a m o n gt h em a n yw e bp a g e sc l a s s i f i c a t i o na l g o r i t h m s ，r b fn e u r a ln e t w o r k b e c o m ear e s e a r c hf o c u si nm a c h i n el e a r n i n gb e c a u s eo fi t se x c e l l e n tc l a s s i f i c a t i o na b i l i t y t h i st h e s i sd e s c r i b e st h ep r o c e s so fw e bp a g e sc l a s s i f i c a t i o n ，t h ed e v e l o p m e n to fr b f n e u r a ln e t w o r k ，r e l a t e dt e c h n o l o g i e s ，s u m m a r i z e st h ei m p o r t a n tr o l eo fr b f n e u r a ln e t w o r ki n w e bp a g e sc l a s s i f i c a t i o n t h ec o m m o nt r a i n i n gm e t h o d so fr b fa r ea l s os t u d i e d ，i n c l u d i n g t h ed e r i v e dm u l t i i n s t a n c em u l t i 1 a b e lr b fn e u r a ln e t w o r k w ep r o p o s e da l li m p r o v e d m e t h o df o rt h ep o o rp e r f o r m a n c eo fm i m l r b fo nu n b a l a n c e dd a t a s e t t h i sm e t h o dt a k e s i n t oa c c o u n tt h eo v e r a l ld i s t r i b u t i o no ft h es a m p l e s ，s ot h a tt h eh i d d e nn e u r o n sg e n e r a t e do n a l lc l a s s e st e n d st ob a l a n c e ，r e d u c i n gt h eu n b a l a n c ep r o b l e mo nt h en e t w o r k w h e nt h et r a i n i n gd a t aa r en o i s yo rn o te a s i l yd i s c e m i b l e ，t h es v dm e t h o dw i l lc a u s e a u g m e n t e do v e r a l l e r r o ri nn e t w o r kp e r f o r m a n c e i nt h i st h e s i s ，t h ew e i g h t so p t i m i z a t i o n m e t h o db a s e do nt h es t e e p e s td e s c e n tm e t h o di sp r o p o s e df o rr e l i e v et h i sp r o b l e m f i r s t l y ，t h e w e i g h tm a t r i xi si n i t i a l i z e db ys v dm e t h o d ，a n dt h e no p t i m i z e db ys t e e p e s td e s c e n tm e t h o d t h el e a r n i n gr a t em a t r i xi sc o m p u t e db ym i n i m i z i n gt h es u m s q u a r e de r r o rf u n c t i o no ft h e n e ww e i g h tm a t r i x t h ep e r f o r m a n c eo fn e t w o r ki si m p r o v e do nn o i s yt r a i n i n gd a t a f i n a l l y ，t h ei m p r o v e dt r a i n i n ga l g o r i t h m sa r ea p p l i e dt o t h ew e bp a g e sc l a s s i f i c a t i o n s y s t e m t h ep e r f o r m a n c eo fi m p r o v e da l g o r i t h m sa r ea n a l y z e da n dc o m p a r e d e x p e r i m e n t a l d a t as h o wt h a tt h ea l g o r i t h m sh a v eh i g h e re f f i c i e n c ya n da c c u r a c y k e y w o r d s ：m i m l r b fn e u r a ln e t w o r k s ，w e bp a g e sc l a s s i f i c a t i o n ，i m b a l a n c e ds a m p l e s ， s i n g u l a rv a l u ed e c o m p o s i t i o n ，s t e e p e s td e s c e n tm e t h o d 目录 第一章前言1 1 1 课题背景与意义1 1 2 国内外研究现状1 1 3 论文研究内容5 1 4 论文组织结构5 第二章网页分类技术综述7 2 1 网页分类简介7 2 1 1 网页信息抽取8 2 1 2 分词技术简介9 2 1 3 特征选取技术1 0 2 1 4 网页向量表示1 1 2 1 5 常用网页分类算法1 2 2 2r b f 神经网络1 4 2 3m i m l r b f 神经网络1 5 2 4 本章小结1 7 第三章不平衡样本下m im l r b f 神经网络改进算法18 3 1k - m e d o i d s 算法1 8 3 2h a u s d o r f f 距离1 8 3 3m i m l r b f 训练算法1 9 3 4 改进的m i m l r b f 训练算法2 1 3 5 实验与讨论2 2 3 5 1 实验设计2 2 3 5 2 实验结果。2 3 3 6 本章小结2 5 第四章基于最速下降法的权重优化算法2 6 4 1s v d 方法2 6 4 2 最速下降法2 7 2 9 3 0 5 3 2 运行结果分析4 4 5 4 本章小结4 5 总结4 6 主要工作4 6 主要创新点4 6 存在的问题及未来的方向：4 7 参考文献4 8 在学期间的研究成果5 2 致谢5 3 1 1 2 3 5 5 5 6 9 d l n n 引 驼 弘 2 5 ； 弘 ：； 甜 们 到互联网上，同 时各种新信息也通过互联网进行发布，互联网逐渐成为了人们获取信息的主要途径。据 统计，著名搜索引擎g o o g l e 收录的网页数已经超过1 0 0 亿。为了帮助人们从如此海量的 网页中获取有用的信息，网页自动分类技术应运而生。网页自动分类技术是利用机器学 习的技术对网页进行类别自动标注【1 1 。目前，网页分类已经在分类信息搜索、个性化搜 索、搜索结果自动分类等领域得到了实际应用【2 j 。 在众多的机器学习算法中，神经网络因其出色的学习能力、较强的鲁棒性和容错性、 良好的适应性等优点成为机器学习界的研究热点。r b f ( r a d i a lb a s i sf u n c t i o n ) 神经网 络【3 1 作为神经网络的一种，除具有一般神经网络的优点外，还具有非线性逼近能力强、 网络结构简单、网络权值与输出呈线性等优点。其已被广泛应用于模式识别、信号处理、 语音识别等领域。r b f 神经网络训练过程中，网络结构和参数选择，尤其是网络中心的 选择对神经网络的性能都有较大的影响，另外径向基函数也是影响网络性能的一个重要 因素。 本课题旨在对基于r b f 神经网络的网页分类技术进行研究，针对目前算法中存在的 不平衡样本下分类准确度低、噪声数据下分类误差大等缺点提出改进策略，并将改进后 的r b f 神经劂络应用到网页分类系统中，从而提高网页分类的效率和准确度。 1 2 国内外研究现状 1 9 4 3 年m c c u l l o c h 和p i t t s t 4 1 提出神经元的数学模型后，人工神经网络取得了巨大的发 展，成为一门具有独特风格的信息处理学科。神经网络按照其基本模式分类，有前馈型、 反馈型、自组织型、随机型网络等。在神经网络的应用中，应用较多的是前馈型网络， 但前馈型网络存在局部最优问题，并且训练速度慢，效率低。 1 9 7 1 年，h a r d y l 5 】首次提出利用径向基函数的思想对多维离散数据插值。1 9 8 5 年， p o w e l l 6 1 提出了多变量插值的径向基函数方法，并且对径向基函数的应用做了概括和回 顾。1 9 8 8 年，b r o o m h e a d 幂i l l o w e i7 】根据生物神经元具有局部响应的特点，将径向基函数 第一章前寄 引入神经网络设计，产生了r b f 神经网络。 r b f 神经网络由于其网络结构简单，收敛速度快，可以以任意精度逼近任何函数等 优点受到人们的关注。根据不同的应用，人们提出了一系列的学习策略用来改进r b f 神 经网络的性能。这些方法主要分为两类： ( 1 ) 网络中心和宽度的训练 网络中心和宽度的训练是r b f 神经网络训练过程的第一阶段。对于r b f 神经网络来 说中心点的确定是个关键问题，其很大程度上决定了r b f 神经网络性能的好坏。目前， 比较常用的中心点选择算法有：随机选取中心，基于监督学习的方法，基于聚类的选择 法。 随机选取中心是随机在输入样本数据中选取网络的中心，且中心固定。这种方法只 有在训练集样本分布均匀的时候才有效，当训练集样本分布不均匀时，采用这种方法选 取的中心通常不能反映训练集样本的分布情况，导致网络性能较差。基于监督学习的方 法是先按经验选定隐单元数，其余参数全由监督学习方法来确定。这种算法本质上与误 差反传算法相同，与初值有关，且难以找到全局最优。这也限制了监督学习方法的应用。 基于聚类的选择法对自变量空间的训练样本点进行聚类，以划分的类别数作为隐单元 数，以各类的中心为径向基函数的中心，各类的方差变换为宽度参数。常用的聚类方法 是k 均值法【8 】和k 中心点法【9 1 。 2 0 0 6 年，苏小红博士等提出一种基于最近邻聚类中心选取和梯度下降训练的混合 学习算法，利用最近邻聚类对学习样本进行自动聚类，在线确定r b f 神经网络的隐层结 构，然后再用梯度下降算法对在线确定的网络进行训练，调整网络参数。这种方法训练 速度快、学习精度高，但是其中一些参数需要人工指定。2 0 0 7 年，赵志刚博士等【1 1 】则利 用遗传算法对网络的中心进行了优化，该算法中的每代群体是一个完整的r b f 网络的编 码，而每个个体的编码对应的仅仅是l f 神经网络的隐层单元中的一个。最后优化的结 果足一个相互协作的多个径向基函数的组合，而不是单个的径向基函数，它们一起组成 一个有效的r b f 神经网络。这种方法所需关于系统的数据信息较少，对初始参数不敏感， 不易陷入局部极小点，但另一方面也增加了训练的时间。 径向基函数的宽度可以控制径向基函数衰减的快慢，也就是控制隐层神经元对输入 响应的范围，它应该反映输入空间的数据分布情况。比较有代表性的宽度确定算法有两 2 中国石油入学( 华东) 硕l - 学位论文 种。第一种是为所有径向基函数选择相同且固定的值，这种方法在数据分布均匀时比较 有效，但在数据分布不均匀时，这种方法确定的网络的性能往往较差，因为宽度应该根 据中心点的不同而不同。第二种方法为每个隐神经元独立的估计宽度，一种简单的方法 是计算数据点和它所对应的中心点的距离的标准差作为该隐神经元的宽度。如：m o o d y 署h d a r k e n t l 2 】提出通过有指导的k 最近邻来计算宽度。第二种方法与第一种方法相比，能 利用数据的分布情况来优化宽度参数，因此网络的性能得到很大提高。但n a b i l 1 3 1 等提 出用这种方法确定的宽度仍然是次优的。n a b i l 等人提出一种新的算法，首先计算每一个 聚类的标准差，然后为所有的径向基函数的宽度引入一个因子。宽度因子可以使整个网 络的逼近性能更趋于平滑，也使得网络的泛化能力更强。 ( 2 ) 网络权重的训练 整个r b f 网络的输出是所有隐含层神经元输出的线性组合，每个神经元到输出的权 重是该神经元的系数。因此在训练过程中，当每个神经元的径向基函数选定后，可以通 过解线性方程组来确定网络的权重。常用的算法有：伪逆法【1 4 】，最小均方( l m s ) 法【15 1 ， 最速下降( s d ) 法【1 6 】，快速繁殖法( q p ) 1 7 1 等。 伪逆法是网络学 - j 算法中最直接的学 - j 算法，p o g g i o 矛n g i r o s i t l s j 提出了这种方法的 一种变形，也就是正则化方法。这种方法需要求一个n n 矩阵的逆矩阵，n 是隐含层节 点的个数。因此，当隐含层节点个数很大时，这种方法的计算复杂度以及内存的占用都 比较高。l m s 方法不需要大量的内存，但使用该方法缺点是在学习过程中网络不能保证 收敛，且收敛过程缓慢。s d 方法在学习过程的每一阶段使用梯度误差函数计算下一阶段 的权重，这种方法的缺点也是收敛速度慢。q p 方法是s d 方法的优化，它在学习过程中 使用当前梯度和上一阶段的梯度。虽然q p 方法比s d 方法要精确，但它收敛速度仍然很 慢。2 0 0 7 年，m o n t a z e r 【1 9 】在s d 和q p 算法中引入最优学习率( o l r ) ，用来提高网络学习 的速度。并提出了通用最优快速下降算法进一步提高学习速度。 另外，r b f 网络结构的设计也是一个有待解决的问题。对于一个给定的待解决问题， 我们并不知道最佳的网络大小，如果网络太小，它就没有能力去很好地处理待解决的问 题，另一方面，如果网络太大，训练时间成指数增长，且当网络增大到一定程度网络的 性能将不再随网络的增大而提高。目前，在设计网络规模的研究中，涉及的算法有增减 法、正则化法、进化算法等。但这些算法都不能很好地解决网络规模设计的问题。此外， 3 第一章前言 h a r h p a m 币h d a w s o n t 2 0 1 提出隐含层径向基函数的选择是问题相关的，即不同的应用选择合 适的径向基函数能提高网络的性能。 多实例多标签学习算法是一种新型的学习框架，即每个样本用多个实例表示，并属 于多个类别【2 l 】。网页分类既是一种典型的多实例多标签分类问题。一个网页的正文通常 由多个段落组成，每个段落对应一个实例；一个网页也可以属于多个类别，如体育、奥 运会等。但是传统的网页分类算法，通常是单实例单标签的分类算法，即每个样本用一 个实例向量表示，并只被分到一个类别当中。这种单实例单标签分类算法可以看成是多 实例多标签分类算法的一种简化。因此，有三种方法来解决多实例多标签分类问题： ( 1 ) 通过多实例单标签，把多实例多标签问题转化成单实例单标签问题解决。如 m i m l b o o s t 算法【2 l j 。 ( 2 ) 通过单实例多标签，把多实例多标签问题转化成单实例单标签问题解决。如 m i m l s v m 算法【2 l 】。 ( 3 ) 设计多实例多标签算法直接解决多实例多标签问题。如z h z h o u 等设计的 d m i m l s v m 算法【2 2 】，m i n l i n gz h a n g 和z h i j i a nw 撕g 设计的m i m l r b f 算法【2 3 】。 前两种解决方法都是通过最终把多实例多标签算法最终转换成单实例单标签问题， 再用传统分类算法解决问题。虽然这种方法是可行的，但是m i n - l i n gz h a n g 和z h i - j i a n w a n g t 2 3 】指出在问题转换过程中可能会丢失部分有用信息，从而降低分类的准确度。第 三种方法在分类过程中则可以利用这些信息。 ” m i m l r b f ( m u l t i i n s t a n c em u l t i l a b e lr a d i a lb a s i sf u n c t i o n ) 派生自传统的i 也f 神 经网络，它同样由三层神经元组成。第二层神经元通过在各个训练样本上运行 k - m e d o i d s 聚类算法得到，其中实例间距离采用平均h a u s d o r f f 足e 副2 4 1 。第三层的权重 通过最小化平方和误差函数，使用奇异值分解计算得出。但当训练样本不均衡时，第一 阶段的k m e d o i d s 聚类算法在每一个类上产生的神经元的数量就会失衡，从而降低整 个网络的分类准确度。另外，g h a m o n t a z e r 等【2 5 1 指出如果第二层神经元的输出矩阵不 是满秩的，使用奇异值分解求出的权重矩阵会导致网络误差变大。 综上所述，在基于r b f 神经网络的分类技术理论和实际应用中，已经有了大量的工 作。但还存在着以下问题：( 1 ) 在不平衡样本集上分类效果差；( 2 ) 含有噪声的样本集 容易导致总体误差变大。本课题旨在对这些问题提出改进方法，在不平衡样本集上考虑 4 中国石油人学( 华东) 硕t 学位论文 总体的样本分布情况，使各类上产生的隐含层神经元趋于平衡，减少不平衡样本对神经 网络模型的影响。另外，利用最速下降法优化权值矩阵，提高神经网络在含有噪声的样 本集上的分类精度。 1 3 论文研究内容 论文的主要工作内容如下： ( 1 ) r b f 神经网络中心和宽度的确定 r b f 神经网络训练首先要解决的关键问题就是确定隐含层神经元的数量，以及每个 神经元的中心和宽度。这三个参数应该反映给定训练样本集中数据的整体分布情况。 m i m l r b f 神经网络在解决多实例多标签分类问题时，虽然其分类效果优于其他几种多 实例多标签分类算法，但是当训练集里各类别中的样本数目不均衡时，会导致网络分类 准确度明显下降。因为在确定每一类别上的神经元数目时，m i m l r b f 采用的是固定比 例法，即将每一类别上的神经元数设置为该类别中样本数的某一固定比例，此比例为人 工指定的经验值。另外，m i m l r b f 对于每一神经元的宽度采用的是各神经元中心间距 离的平均值。因此，根据训练集样本的分布优化各类别上神经元的数量，以及其中心和 宽度是本文的研究方向。 ( 2 ) 网络权值矩阵的优化 计算隐含层和输出层之间的权值矩阵是训练i m f 神经网络的第二阶段，此权值矩阵 的准确与否直接影响到网络的输出结果。m i m l r b f 神经网络在最小化误差函数时，首 先对误差函数关于权值变量求微分，然后使用奇异值分解来求解权值矩阵。然而在将奇 异值分解应用于l 也f 神经网络求权值时，g h a m o n t a z e r 等证明当训练集有噪声数据或 类别不容易区分时，此方法易导致整个网络的误差变大。因此，改进权值矩阵求解算法， 减少噪声数据对网络的影响，也是本文的研究方向。 1 4 论文组织结构 论文共分六章，具体结构如下： 第一章“前言，阐述了论文的研究背景和意义以及国内外研究现状，介绍了论文 的主要研究内容，最后给出论文的组织结构。 第一章前高 第二章“网页分类技术综述”，介绍了网页分类技术的概念、工作原理、常用的网 页分类算法以及评价指标。重点介绍了基于r b f 神经网络的网页分类技术。然后介绍 目i ； f 主流的r b f 神经网络的相关训练算法。 第三章“不平衡样本下m i m l r b f 神经网络改进算法，对m i m l r b f 神经网络第 一阶段的训练算法进行了分析，指出该训练算法在不平衡样本下训练得出的神经元数目 失衡，从而导致网络分类效果差的问题。针对此问题，提出改进算法。 第四章“基于最速下降法的权重优化算法，由于使用奇异值分解求解m i m l r b f 神经网络的权值，容易受训练样本中噪声数据的影响，从而降低网络的分类效果。本文 采用最速下降法对求出的权值进行优化，降低噪声数据对网络分类效果的影响。 第五章“网页分类实验系统设计”，为了验证第三章，第四章所提到的改进的训练 算法的效果，设计了网页分类实验系统。通过实验证明了改进的训练算法使得网页分类 的准确率有明显提高。 “总结 ，对全文进行了总结，说明了论文的主要工作、主要创新点、存在的不足 以及未来发展的方向。 6 中国石油大学( 华东) 硕j ：学位论文 2 1 网页分类简介 第二章网页分类技术综述 网页自动分类技术是利用机器学习的技术对网页进行类别的自动标注，即为一个已 知网页附上一个或多个类别标签，如：新闻、体育、经济等。它可以帮助人们有效的组 织和利用海量的网页信息。在网页出现以前，人们已经通过机器学习研究过文本自动分 类的方法，即文本自动分类( a u t o m a t i ct e x tc a t e g o r i z a t i o n ，a t c ) 技术【2 6 】。伴随着互联 网的迅速发展，大量的网页出现在互联网上，为了方便人们获取信息，人们在文本自动 分类技术的基础上发展了网页自动分类技术。网页与普通文本相比，它本身包含的信息 更为丰富，不仅包括人们感兴趣的正文信息，还包括许多控制格式的代码、链接、广告 信息等。因此，网页分类比普通文本分类更为复杂和困难。从数学的角度上来讲，分类 的本质就是能准确的反映出文本与其属性之间的关系2 7 1 。 ，、 ，、， 、 厂、 信息 特征特征分类器 i 训练集卜 分词 _ 抽取选取向餐 训练 厂 ， 、 ， ( | 球分类器 回 f 勰f 丫 皇 信息特征 特征分类器 l 测试集卜 分词 一 选取 _ 抽取 向量运算 、 图2 - 1 网页分类器系统结构图 f i 9 2 1w e bp a g ec l a s s i f i e rs y s t e ms t r u c t u r ed i a g r a m 如图2 1 所示，一般的网页分类器系统应该主要包括五大部分，前四个部分属于网 页预处理技术： ( 1 ) 信息抽取部分，此部分也称作网页净化。它去除网页中对分类无用的信息，如 代码，广告，链接等，保留对网页分类有用的信息。 ( 2 ) 分词部分，将连续的大段正文切分成一个一个单独的词。它是将连续的字序列 按照一定的规范重新组合成词序列的过程。在英文的行文中，单词之间是以空格作为自 然分界符的，而中文的行文词与词之间没有明显的分界符划分，因此中文分词要比英文 分词要复杂和困难。 7 第二章网页分类技术综述 ( 3 ) 特征选取，它把从网页中分词得出的特征词进行量化来表示网页信息。通常分 词得出的关键词是大量的，导致用来表示网页的向量维数很高，给网页分类造成困难。 需要对特征词进一步处理，选取那些最能表示原文含义的特征词。 ( 4 ) 向量表示，计算机并不能理解从网页中抽取的关键字，从本质上计算机只能识 别0 、1 代码，因此我们必须将特征词转换成计算机可以识别的代码。 ( 5 ) 分类器，通过学习训练集中的网页，自动对给定的网页进行分类。这部分是网 页分类的关键，可以选用不同的分类器，不同的分类器得出的分类结果可能会有差异。 2 1 1 网页信息抽取 互联网上的信息主要是以h t m l ( h y p e r t e x tm a r k u pl a n g u a g e ) 页面的形式出现的， h t m l 语言具有自身的结构特点。用h t m l 语言写成的源文件由不同含义的标记( 例如 、 等) ，各种超链接、导航等非主题信息，和文章的正文文本组成。网页信 息抽取就是从网页所包含的无结构或半结构的代码中识别并抽取对用户有用的数据，并 将这些数据转存为有结构和语义的清晰格式2 8 1 。它是网页分类系统中的第一步。虽然网 页数据属于一种半结构化的数据，但从本质上来看，它们依然是文本文件。通过对h t m l 不同含义标记的分析，可以得到网页中一些对页面分类有用的信息，但由于不同的人有 不同的网页编写风格，导致了网页格式的千差万别，所以要找出一种处理所有网页结构 的算法几乎是不可能的。比较常用的网页信息抽取方法有： ( 1 ) 基于自然语言处理的网页信息抽取 基于自然语言处理的网页信息抽取方法是发展比较早的信息抽取方法，它利用自然 语占处理技术实现网页信息的抽取，首先把网页的正文内容解析成多个句子，然后分析 句子的组成成分，再利用句子结构、短语及其之间的关系抽取信息。如w h i s k 信息抽取 系统【2 9 j ，此系统不仅能提取自由文本信息，还能提取结构化和半结构化的网页信息。对 于那些不符合标准文法的网页，能根据其上下文语义信息实现定位和提取。这种方法也 有它本身的不足： 由于h t m l 网页同时包含正文和代码，导致基于自然语言处理的网页信息抽取 适用范围较窄。 网页的结构较为复杂，不能充分发挥自然语言处理的优势，且此种方法需要大 量的样本进行训练才能学习到有效的抽取规则，处理速度有待提高。 ( 2 ) 基于w r a p p e r 的网页信息抽取 中国油人学( 4 芦东) 硕i ：学位论文 w r a f p e r 即包装器，是指专门从网页中抽取信息并转化成特定结构数据的应用程序。 它可以手动创建，也可以使用工具自动生成。手动建立包装器需要根据特定领域知识分 析网页信息，定义抽取规则。优点是准确率高，但建立复杂，维护代价大。使用工具生 成包装器需使用训练集，利用机器学习算法学习抽取规则。优点是速度快、易维护，但 受限于机器学习算法的有限性，准确率较低。已有系统如s t a l k e r t 3 0 l ，它是基于监督 学习的包装器信息抽取系统。 ( 3 ) 基于页面结构分析的网页信息抽取 该方法是利用网页的结构特征来抽取信息，它一般是先把网页解析成d o m ( d o c u m e n to b j e c tm o d e l ) 树，然后利用多种方式产生抽取规则，查找主题信息，典型 的系统有w 4 f 3 1 1 、l i x t o 3 2 1 l 和r o a d r u n n e r 3 3 1 等。其中比较有名是r o a d r u n n e r 系统，它 首先比较样本页面，得到此类页面的一个通用正则表达式，再利用该表达式实现网页信 息抽取。它不需要用户标注样本，能自动根据模型网页抽取网页信息，但是抽取的准确 率不高。 其它的网页信息抽取方法还有基于o n t o l o g y 的网页信g 抽取【3 4 j 、基于w r e b 查询的网 页信息抽取阅等。 2 1 2 分词技术简介 由于英文是以词为单位的，词与词之间是靠空格隔开，而中文是以字为单位，句子 中所有字连起来才能描述一个意思。因此中文分词要比英文分词困难的多，人们也提出 了许多中文分词的算法。目前分词算法主要分为三大类：基于字符串匹配的分词方法【3 6 1 、 基于理解的分词方法【3 7 】和基于统计的分词方法【3 8 】。 ( 1 ) 基于字符串匹配的分词方法 这种方法也称作机械分词方法，它按照一定的策略将待分析的汉字串与一个机器词 典中的词条进行匹配，若在词典中找到某个词，则匹配成功，即识别出一个词。按照扫 描方向的不同，字符串匹配方法可分为正向匹配和逆向匹配；按照不同优先长度匹配， 可以分为最长匹配和最短匹配；按照是否与词性标注过程相结合，又可以分为单纯分词 方法和分词与标注相结合的一体化方法。常用的机械分词方法有：正向最大匹配法、逆 向最大匹配法、最少切分( 使每句中切出的词数最少) 。实际使用的分词系统，都是 把机械分词作为一种初分手段，然后通过利用各种其它的语言信息迸一步提高切分的准 确率。 9 第二章网页分类技术综述 ( 2 ) 基于理解的分词方法 这种分词方法是通过让计算机模拟人对句子的理解，达到识别词的效果。其基本思 想就是在分词的同时进行句法、语义分析，利用句法信息和语义信息来处理歧义现象。 它通常包括三个部分：分词子系统、句法语义子系统、总控部分。在总控部分的协调下， 分词子系统可以获得有关词、句子等的句法和语义信息来对分词歧义进行判断，即它模 拟了人对句子的理解过程。这种分词方法需要使用大量的语言知识和信息。由于汉语语 言知识的笼统、复杂性，难以将各种语言信息组织成机器可直接读取的形式，因此目前 基于理解的分词系统还处在试验阶段。 ( 3 ) 基于统计的分词方法 从形式上看，词是稳定的字的组合，因此在上下文中，相邻的字同时出现的次数越 多，就越有可能构成一个词。因此字与字相邻共现的频率或概率能够较好的反映成词的 可信度。可以对语料中相邻共现的各个字的组合的频度进行统计，计算它们的互现信息。 互现信息体现了汉字之间结合关系的紧密程度。当紧密程度高于某一个阈值时，便可认 为此字组可能构成了一个词。这种方法只需对语料中的字组频度进行统计，不需要切分 词典，因而又叫做无词典分词法或统计取词方法。但这种方法也有一定的局限性，会经 常抽出一些共现频度高、但并不是词的常用字组，例如“这一”、“之一”、“有的”、“我 的、“许多的等，并且对常用词的识别精度差，时空开销大。 目前，哪种分词算法的准确度最高尚无定论。对以任何一个成熟的分词系统来说， 不可能单独依靠某一种算法来实现，都需要综合不同的算法。 2 1 3 特征选取技术 由于分词得出的特征词往往很多，一方面包含了很多冗余特征词，一方面给分类造 成困难。特征提取的主要功能是在不损伤文本核心信息的情况下尽量减少特征词的数 目，以此来降低向量空间维数，从而简化计算，提高分类的速度和效率。通常根据某个 特征评价函数计算每个特征的权重，然后根据权重对特征词排序，选取若干权重最高的 作为最终特征词。常用的特征词评估算法有词频法、t f i d f ( t e r mf r e q u e n c y - i n v e r s e d o c u m e n tf r e q u e n c y ) 、互信息、期望交叉熵、信息增益方法、z 2 统计法等【3 9 1 。 ( 1 ) 词频法 词频是一个特征词在某一文档中出现的次数。词频法就是将词频小于某一阈值的特 征词删除，从而降低特征空问的维数。这个方法假设出现频率小的词对分类的影响也较 1 0 中闺t j 油人学( 华东) 硕卜学位论文 小。但是在信息检索的研究中认为，有时频率小的词含有更多的信息。 t f i d f 是由s a l t o n 在1 9 8 8 年提出的，它是特征词权重最为有效的实现方法。t f 称为 词频，用于计算某个特征词描述文档内容的能力；i d f 称为反文档频率，用于计算该特 征词区分文档的能力。t f i d f 建立的基本假设是：在一个文档中出现多次的单词，在另 一个同类文档中同样会出现多次，反之亦然。t f i d f 公式如下： 一万tf,(丽d)x l o g ( n n , ) ( 2 - 1 ) 其中，彬( d ) 为特征词t 在文档d 中的权重，矿( d ) 为特征词，在文档d 中出现的次数， 为文档的总数，胛为训练集中出现，的文档数。 ( 3 ) 互信息 互信息计算的是某个特征词与类别之间的统计独立关系。它基于如下假设：某一特 征词在某个类别中出现频率高，而在其他类别中出现频率低，则说明该特征词与该类的 互信息大。特征词t 与类别c ，的互信息计算公式如下： m i ( t , c , ) - l 。g 而p ( t 而, c i ) - l o g 等 ( 2 - 2 ) 其中，p ( t ，c ，) 表示训练集中包含特征词r 又属于类c ，的文档出现的概率，p ( t ) 表示 包含f 的文档在训练集中出现的概率，p ( c ，) 表示训练集中属于类q 的文档出现的概率。 2 1 4 网页向量表示 计算机并不能理解从网页中抽取的关键字，从本质上计算机只能识别0 、l 代码，因 此我们必须将特征词转换成计算机可以识别的代码。根据贝叶斯理论，假设文档中的字 或词在对文档分类时贡献相互独立。就可以用文档中的字或词代替文档，虽然会丢失部 分文档信息，但也使得文档的表示和处理更加形式化，在实际分类中取得了不错的效果。 6 0 年代s a l t o n 等人提出的向量空间模型( v e c t o rs p a c em o d e ，v s m ) ，把文档内容的处理 简化为向量空间中的向量运算，并且它以空间上的相似度表达语义的相似度，直观易懂。 文档向量表示：( 彬，岷，呒) ，彬为第f 个特征项的权重。 第二章网页分类技术综述 2 1 5 常用网页分类算法 ( 1 ) k n n 分类算法 k n n 分类算法【4 0 1 的基本思想是：给定一个新文档后，计算训练集中与该文档距离最 近( 最相似) 的k 篇文档，根据这k 篇文档所属的类别判定此新文档的类别。k n n 算法 中，所选择的邻居文档都假设是已经正确分类的文档。k n n 算法步骤如下： 选用一个适当的距离度量，如欧式距离、余弦距离。使用该距离计算待分类文 档d 与训练集s 中所有文档的距离，选择与d 距离最近的七个文档作为d 的最近邻。 按照这k 个文档，计算d 属于每个类的权重形，形的计算公式为： k w ( d ，c j ) = s i m ( d , ，d ) 万( z ，q ) ( 2 3 ) i = i c j 代表训练集中的一个类；s i m ( d ，d ) 是d 与其第f 个最近邻的相似度；万( z ，q ) 的 定义如下： 万c d ，x ，= 三暑 c 2 - 4 ， 将文档d 分类到权重最大的类别。 k n n 算法不需要训练，它直接计算待分类文档与训练集中文档的相似