（计算机应用技术专业论文）基于支持向量机的网页自动分类方法研究与实现.pdf

摘要 摘要 随着互联网的发展，w e b 已经成为人们获取信息的重要渠道和手段，但同时 呈指数增长的w e b 信息，又对人们如何从中获取有效的信息带来了巨大挑战。探 索自动、高效的网页信息检索方法，以提高人们定位、查找相关信息的能力，已 经成为人们普遍关注的热门研究课题。网页自动分类技术作为w e b 挖掘的基础， 正在受到越来越多研究者的关注。与普通文本分类不同，网页含有大量与主题不 相关的干扰，这严重影响了网页分类的质量。事实上，目前网页自动分类的效果 普遍不佳。本文的目的是，在传统文本分类的基础上，针对网页数据的特性，研 究利用支持向量机进行网页自动分类的相关技术和方法，以提高网页分类的效 果，促进w e b 分类技术的发展。本文主要研究内容如下： ( 1 ) 直接采用传统向量空间模型，在网页分类中不能充分利用网页特征信 息。本文结合网页数据的特点，采用基于分块重要度的特征项权重系数，改进了 传统向量空间模型，得到了更合理的网页特征向量。 ( 2 ) 联合特征选取。文档频率特征选取( d f ) 和卡方检验特征选取方法( c h t ) 是两种常用的特征选取方法。但是，单纯使用d f 不能有效选取较强类别信息的 词项，单纯使用c h i 统计方法则不能很好地过滤低频词中的噪声词。因此，本 文提出了一种d f 和c h i 联合特征选取方法。该方法综合利用了d f 和c h i 方法的 优点，能够选取较好的特征词，以改善分类器的效果。在2 0 0 7 年全国搜索引擎 与w e b 挖掘中文网页分类评测中，使特征空间的维数降为8 1 7 7 ，远低于其它院 校的数万维。 ( 3 ) 变步长的支持向量机核函数参数优选。目前，支持向量机的参数选择 没有统一的理论原则，大都依靠实验逐步寻优得到。本文采用变步长的参数优选 方法进行参数选择，首先用大步长的参数选择方式，快速确定一个较优参数的可 能范围；然后在该范围内再用小步长方法逐步找到更好的参数。虽然该方法不能 保证获得全局最优参数，但是能够在较短的时间内获得令人满意的参数。 本文所提出的特征向量提取方法和所实现的网页分类模型，在数字图书馆、 主题搜索、个性化信息检索、搜索引擎目录导航、信息过滤、主动信息推送服务 等领域具有广泛的应用前景。 关键词信息检索：网页分类；特征选取；支持向量机 a b s t r a c t 曼i一一m m ) m l l ! 曼! 曼! 曼皇皇曼苎曼皇! ! 曼皇曼曼! 曼曼皇曼曼! 曼曼皇皇曼兰蔓曼曼曼曼皇 a b s t r a c t w i 廿it h er a p i dd e v e l o p m e n to fi n t e r a c ta n dw e bs i t e sa sa ni m p o r t a n tc h a n n e lt o a c c e s sp u b l i ci n f o r m a t i o n ，t h e r ec o m ee n o r m o u sc h a l l e n g e st oc a p t u r ev a l u a b l e i n f o r m a t i o ne f f i c i e n t l y i th a sb e c o m eah o tr e s e a r c ht o p i ct oe x p l o r ea na u t o m a t i ca n d e f f i c i e n tw e bp a g ei n f o r m a t i o nr e t r i e v i n gm e t h o dw i t hab e t t e rp e r f o r m a n c et ol o c a t e a n df i n do u tp e r t i n e n ti n f o r m a t i o n a sab a s i so fw e bm i n i n g ，a u t o m a t i cw e bp a g e c a t e g o r i z a t i o ni sa t t r a c t i n gm o r ea n dm o r ec o n c e r n sf r o mr e s e a r c h e r s c o m p a r e dw i t h p l a i nt e x t s ，w e bp a g e sc o n t a i np l e n t yo fn o i s e ，w h i c hi sn o tr e l a t e dt ot h em a i nt h e m e o ft h ew e bp a g ea n da f f e c t st h eq u a l i t yo fw e bp a g ec a t e g o r i z a t i o n i nf a c t ，t h er e s u l t o fw e bp a g ec a t e g o r i z a t i o ni su s u a l l yp o o ra tp r e s e n t b a s e do nt r a d i t i o n a lt e x t c a t e g o r i z a t i o n ，t h ep u r p o s eo ft h i sp a p e ri st ou s et h ep r o p e r t i e so fw e bd a t aa n d s u p p o r tv e c t o r m a c h i n em o d e lt o s t u d y m e t h o d sf o ra u t o m a t i cw e b p a g e c a t e g o r i z a t i o na n dt oi m p r o v et h e i rp e r f o r m a n c ei nt h ea p p l i c a t i o no fr e l e v a n t t e c h n o l o g i e s t h em a i nc o n t r i b u t i o n so ft h i st h e s i sa r ea sf o l l o w s ： ( 1 ) c h a r a c t e r i s t i c so fw e bp a g e sc a r ln o tb es u f f i c i e n t l yd e s c r i b e db yt r a d i t i o n a l v e c t o rs p a c em o d e l ( v s m ) d i r e c t l y c o m b i n i n g 谢t ht h ep r o p e r t i e so fw e bp a g e s ，t h i s t h e s i si m p r o v e st r a n d i t i o n a lv s mt oo b t a i nb e t t e rf e a t u r ev e c t o r sf o rw e b p a g e sb a s e d o nf e a t u r ew e i g h t sr e l a t e dt ob l o c ki m p o r t a n c e ( 2 ) j o i n tf e a t u r es e l e c t i o n d o c u m e n tf r e q u e n c y ( d f ) a n dc h i s q u a r et e s t ( c h i ) ， a r et w oc o m m o n l yu s e df e a t u r es e l e c t i o nm e t h o d s h o w e v e li ti sn o tv e r ye f f e c t i v e l y f o rd fa l o n et os e l e c tw o r d sw i t hs t r o n gc a t e g o r yi n f o r m a t i o na n df o rc h ia l o n et o f i l t e r l o w - f r e q u e n c yn o i s ew o r d s t h e r e f o r e ，t h i st h e s i sp r o p o s e s an e wf e a t u r e e x t r a c t i o nm e t h o d ，n a m e dj o i n tf e a t u r es e l e c t i o n ，w h i c hc a l le x t r a c tb e n e rf e a t u r e w o r d st oi m p r o v ew e bp a g ec l a s s i f i e r sb yt a k i n gt h ea d v a n t a g e so f b o t hd fa n dc h i i nt h es y m p o s i mo fs e a r c he n g i n ea n dw e bm i n i n g ( s e w m ) i n2 0 0 7 ，i te f f e c t i v e l y r e d u c et h ed i m e n s i o no ff e a t u r ev e c t o r st o817 7w h i c hi sf a rb e l o wt h ed i m e n s i o n ( t e n so ft h o u s a n d ) o fo t h e rt e a m s ( 3 ) av a r i a b l es t e p s i z em e t h o dt oo p t i m i z et h es v mp a r a m e t e r s a tp r e s e n t ，t h e r e i sn o tag e n e r a lt h e o r yt os e l e c to p t i m a ls v m p a r a m e t e r s ，w h i c ha r eu s u a l l yo b t a i n e d g r a d u a l l yb yp l e n t yo fe x p e r i m e n t s t h i st h e s i sa d o p t sav a r i a b l es t e p s i z em e t h o dt o s e l e c ts v mp a r a m e t e r s ，w h i c hf i r s tf i n dap o s s i b l ed o m a i nf o rr e l a t i v e l yg o o d p a r a m t e r sw i t hab i gs t e p s i z e ，t h e ns e a r c hb e t t e ra n db e t t e rp a r a m e t e r sw i t hd i f f e r e n t s m a l ls t e p s i z e si nt h ed o m a i n a l t h o u g ht h i sm e t h o dm a yn o tf i n dt h eg l o b a l l y i i l 。p t l m l a lp a r a m e t e r ，i c a no b t a i ns a t i s f a c t o r yp a r 锄e t e r si n r e l a t i v e l yl e s sc 。m p u t i n g r e s o u r c ea n dt i m e k e y w o r d si n f o r m a t i o nr e t r i e v a l ；w e bp a g ec a t e g o r i z a t i o n ；f e a 她es e l e c t i o n ：s v m i v 罢峨 b 1砭 础谢薹 甜啦町 嗽 o 姗谊 瞅 = 一 龇训毗盹 d e 瓢 a 叶 i砌掣= ： m ? 噼 a u n n k p o r r = 罨 姒雠弧 一 e m d 】r 啪龇 眦砥 n t i 触 一础 沮捌 垮 m m 沌疵 自 r 呛 一一一 幻汹她讲凡 一一一 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 关于论文使用授权的说明 如舌j - 沙 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：目烨 导师签名查至握日期：逊兰印 第1 章绪论 1 1 研究背景 第1 章绪论 随着信息存储技术和通信技术的飞速发展，尤其是近年来随着国际互联网的 发展，网络上的信息资源呈指数增长，w e b 已经成为拥有几十亿个页面的分布 式信息空间，如何在这些大量、异质的海量信息资源中，快速有效的发掘蕴含具 有巨大潜在价值的有用知识和信息，合理分类及准确地定位所需信息，同时过滤 大量无用的或不相关的内容，已成为知识获取和信息过滤的瓶颈，也是当今信息 发展和信息处理领域的主流技术。如何利用计算机高效率的信息处理能力，获取 有用的信息，成为人类面临的共同问题。网页自动分类便是解决这个问题的有力 有段之一。 网页分类是处理海量网页信息的常用方法，也是文本挖掘和网络挖掘的一项 重要研究内容。由于广告栏、导航条和版权信息等噪声的存在，网页分类比文本 分类难度更大口1 。如果直接将纯文本分类方法应用于网页分类，则很可能受到网 页噪声信息的误导和干扰，而无法将分类的重点集中在网页主题和重要内容上， 影响分类的效果。因此，设计智能的处理方法，以便从网页中抽取主题内容，成 为当前网页数据挖掘的重要方向之一。 同时，网页自动分类在数字图书馆、主题搜索口1 、个性化信息检索h 1 、搜索 引擎的目录导航服务呻1 、信息过滤口3 、主动信息推送服务哺1 等领域有着广泛地应 用。 近年来研究者们从各自不同的角度把越来越多的知识引入网页分类领域，虽 然在研究过程中不断有新的理论和方法产生，取得了令人鼓舞的成绩，但还是有 许多方法有待进一步研究和改进的，比如网页的特征表示、特征选取、网页摘要、 分类算法等，中文网页分类中还有分词的问题。本文重点从网页信息提取、支持 向量机参数优选等方面研究基于支持向量机的网页文类方法。 1 2 网页分类概述 在w e b 出现之前，人们已研究过许多普通文档分类的方法，形成了各种文 档自动分类技术( a u t o m a t i ct e x tc 1 a s s i f i c a t i o n ，即a t c ) 。随着海量网页 信息的大规模增长，文档自动分类技术的处理对象从普通文档扩展到网页信息， 自然地，a t c 技术成了实现网页自动分类的基础。所谓文档自动分类就是用计算 机程序来确定目标文档和预先定义类别之间的隶属关系。用以完成网页自动分类 北京 _ 业大学t 学硕士学位论文 的软件，称为网页自动分类系统。 1 2 1 文本分类的历史及研究现状 国外对文本自动分类的研究开展较早，文本分类在国外大致经历了三个发展 阶段： 第一阶段( 1 9 5 8 - 1 9 6 4 ) 主要进行自动分类的可行性研究。5 0 年代末，h pl u h n 提出的词频统计思想用于自动分类，是这一领域的开创性研究。1 9 6 0 年，m a r o n 在j o u r n a lo fa s m 上发表了关于自动分类的第一篇论文“o nr e l e v a n c e ， p r o b a b i l i t i ci n d e x i n ga n di n f o r m a t i o nr e t r i e v a l ”。 第二阶段( 1 9 6 5 - 1 9 7 4 ) 进行自动分类的试验研究。众多学者在这一领域进 行了卓有成效的研究工作，如k s p a r k 、g s a l t o n 以及r m n e e d h a m 、m e l e s k 、 k s j o n e s 等。 第三阶段( 1 9 7 5 - 至今) 进入实用化阶段，邮件分类、电子会议、信息过滤 等方面取得了较为广泛的应用，其中较为成功的系统有麻省理工学院( m i t ) 为白 宫开发的邮件分类系统、卡内基集团为路透社开发的c o n s t r u e 系统等。 我国的文本分类的研究工作始于2 0 世纪8 0 年代，大致经历了可行性探讨一 一自动分类系统阶段。1 9 8 1 年，候汉清教授对于计算机在文本分类工作中的应 用做了探讨，并介绍了国外计算机管理分类表、计算机分类检索、计算机自动分 类、计算机编制分类表等方面的概况。此后，我国陆续研制出一批计算机辅助分 类系统和自动分类系统。例如，广东省中山图书馆的莫少强开发的计算机辅助图 书分类系统( c - a b c ) 、清华大学吴军研制的自动分类系统、山西大学刘开瑛等人 开发的金融自动分类系统、东北大学图书馆的图书馆分类专家系统、上海交通大 学王永成等研制的基于神经网络优化算法的中文自动分类系统、广州西风公司研 制开发的西风文本自动分类系统、北大天网搜索引擎的基于k n n 的网页自动分 类系统等等。 1 2 2 网页分类研究现状 网页分类是在文本分类技术上发展起来的，其研究对象是大规模w e b 文本数 据。由于网页数据的特点：1 ) 网页的格式灵活，多种格式并存，而且统一格式 的网页存在不同标准；2 ) 网页的写作风格和内容变化大：3 ) 与纯文本数据相比， 网页数据含有丰富的结构信息，较少的内容信息；4 ) 随着网络营销的发展，网 络广告或垃圾网页也成为了互联网上不可忽视的数据。由于网页数据具有除了包 含一定的文本信息，还具有上述特点，因此，一方面网页分类是建立在文本分类 的基础上，另一方面它又有别于传统的文本分类。 2 第1 章绪论 f u r n k r a n z 用指向该网页所有链接周围的文本、链接所在段落的标题以及上 级标题文本表示网页，用r i p p e r 对基于这种表示的文本进行分类，正确率比使 用网页局部文本提高了2 0 吲；c h a k r a b a r t i 和g h a n i 等人尝试用网页的局部文 本和跟它链接网页的文本表示网页，分类结果还没有只使用网页局部文本好n 0 n 】；o h 等人也结合网页局部文本和链接网页的文本表示网页，但没有引入所有链 接网页的文本，而是基于文本相似性选择了部分跟原网页较接近的网页文本，试 验结果f l 指标比使用所有链接网页提高了7 n 。这些工作没有得到一致的结 论，y a n g 等人在h o o v e r s 和w e b k b 数据集上的研究给出了比较客观的解释：网 页集中是否存在某种规律以及能否利用这些规律对网页分类算法的性能起关键 的影响作用，因此应该根据这些规律设计网页的表示方式和网页分类算法n 羽。 文献n 3 1 用组合网页分类器的方法进行分类。文献n 们提出了一种用朴素贝叶斯协调 分类器综合网页纯文本和其它结构信息的分类方法。 综合前人的研究工作，网页分类的研究工作主要分两种思路，一是用表示 纯文本的方式表示网页，二是组合文本分类器的方法。用纯文本方式表示网页 是困难的，也是不合理的。用组合分类器的方法能够综合利用网页的特征，选择 合适的组合策略可以提高网页分类器的效果。 1 2 2 文本分类的主要方法 根据文本特征的表示方式和利用的文本信息不同，文本分类算法大致分为以 下三类： 1 ) 词匹配法。词匹配法就是根据文档包含的词与描述类别的词之间的匹配 程度，来确定文档所属类别的一种方法。词匹配法又分为简单匹配法和基于同义 词的词匹配法。简单词根据文档和类别中共同出现的词决定文档所属类别。显然， 这种分类方法过于简单，分类效果不理想。基于同义词的词匹配法是对简单词匹 配方法的改进，定义一个同义词表，根据文档和类别共同包含的词或同义词决定 其所属类别。简单词匹配是简单字符串的匹配，改进后的方法是基于语义的匹配。 2 ) 基于知识工程的方法。基于知识工程的文档分类方法，需要编制大量面 向具体领域的推理规则。不同领域的分类问题，需要不同领域的专家定义不同的 推理规则，并且分类效果过分依赖于推理规则。因此，基于规则的方法在实际分 类系统中较少使用。 3 ) 统计学习方法。统计学习法的基本思想是先收集一些与待分类文档属于 相同领域的文档作为训练集，并有专家人工分类，然后分析这些已标示类别的文 档，用统计方法从中挖掘关键词和类别之间的联系，从而形成分类的知识，再利 用这些学到的知识对待分类文档进行分类。显然，这种方法忽略文档的语言学结 北京丁业火学t 学硕 ：学位论文 构，用关键词来表示文档，通过有指导的机器学习训练分类器，再用该分类器对 待分类文档进行分类。这种统计学习分类法，由于有较好的理论基础，简单的实 现机制以及较好的分类效果等特点，被广泛采用。 随着分类方法研究的发展，越来越多的统计方法被应用到文档分类领域。向 量空间模型引表示和s o w 表示分类方法得到快速发展。 1 ) 向量空间模型( v s m ) 表示法。文档表示为特征词向量，向量中元素对应词 频，丢弃了特征词在文档中的顺序信息，也称为b o w 表示n 引。使用v s m 的算法 大多属于基于词频统计的学习方法，如朴素b a y e s ( n b ) 、支持向量机方法( s v m ) 、 k n n 、神经元网络( n n ) 和r o c c h i o 等。特征词通常要进行选择实现降维， 文档 向量根据特征词权重对词频权值进行调整。 2 ) s o w 表示。跟v s m 相比忽略词频信息，只关心特征词是否出现。使用s o w 的算法有c 4 5 、r i p p e r 、f o i l 等符号规则归纳算法n 射。 v s m 和s o w 表示方式没有考虑特征词的语义信息，基于文档语义进行分类也 是一个研究方向。w o r d n e t 和知网( h o w - n e t ) 分别是描述英、中文概念的语义知 识库。研究表明，基于词频统计的学习方法取得不错的分类性能，基于语义的分 类结果没有显著提高，如果数据集很大分类性能反而降低，这也许跟目前自然语 言理解水平还比较低有关。如何将这两个方向的研究相结合值得关注。 其中，支持向量机( s u p p o r tv e c t o rm a c h i n e ，s w ) ，是v a p n i k 对统计学 习理论深入分析，提出结构风险最小化准则，在此理论基础上的支持向量机方法 ( s v m ) ，能够有效解决小样本集的机器学习问题n 。j o a c h i m s 将s v m 方法应用到 文本分类，并取得好的分类性能n 8 j 9 1 。由于s v m 方法解决分类问题的关键是选择 合适的核函数，因此随着s v m 方法在文本分类领域研究的不断深入，出现了许多 新的核函数。j o a c h i m s 使用多项式核函数、r b f 核函数和s i g m o i d 核函数进行文 本分类。h u m a l o d h i 和j o h ns h a w e - t a y l o r 等人将字符串核函数引入文本分类啪1 ， 这种核函数可以有效利用特征词的顺序信息而且通过近似方法降低算法的计算 复杂性；n e l l oc r i s t i a n i n i 等人则使用语义核函数设计文本分类器口。 1 3 网页分类模型 网页分类是按照预先定义的分类体系，根据网页文档的内容属性自动确定其 所属的关联类别，又称为网页文档分类或网页文本分类。下面对网页分类模型进 行简要介绍，其中包括网页分类的定义、体系框架、两阶段过程和评价指标等。 1 3 1 网页分类的定义 网页分类的形式化描述如下：网页文档分类就是将一个二元组 4 第1 章绪论 曼i 一曼 一。一一i 曼i 曼曼曼曼蔓曼曼 d xc 映射到一个布尔值的任务。该映射用数学公式表示为 。 ， ：d x cj 仃，f ) ，其中，d = d l ，d 2 ，蠢，d 。 为待分类文档集合， c = c l ，c 2 ，c ，c 册 为分类体系的类别集合。如果将二元组 映射为值 t ( t r u e ) ，则认为文档d 。属于类别c ，否则认为文档d ，不属于类别c ，。文档分类 的核心问题就是如何构造一个分类函数：d xc - - - t ，f ) ，并利用该函数将未知 的文本映射到给定的类别空间。在文档自动分类领域，主要采用机器学习的技术 和方法，即将文档的自动分类过程归结为一个机器学习任务。 1 3 2 网页分类的体系框架 1 ) 网页文档表示，根据分类算法的要求，把网页文档表示的内容转换成计 算机能够表示，分类算法能够识别的数值向量或符号向量。其中主要用到的关键 技术包括：中文分词、特征抽取和向量化等。研究证明，“文档表示”的质量， 将影响分类器的训练与构造，并最终影响分类的效果。 2 ) 分类器设计，指的是分类器的构造及其阚值选择等。分类器的选择和设 计是文档分类的核心内容。包括常用的机器学习分类方法有基于相似度计算方 法、贝叶斯方法、k 近邻方法、支持向量机和决策树方法。阈值选择，文档分类 需要输出的结果是确切类别，因此需要确定一个闽值，将置信度大于此阈值的文 档归入一类，而小于该阈值的文档归为另外一类。 3 ) 分类器的应用实践，主要研究分类器如何走出实验室，投入实际应用。 这个过程包括评测集的构建、性能评价指标的确定等。根据应用的领域不同，不 断改进、优化分类模型及其参数。使分类器在相应的领域得到较好地利用，帮助 人们在信息处理和使用中减少信息查询时间、组织和过滤时间、阅读时间等。网 页分类的体系结构见图1 - 1 。 北京t 业大学工学硕士学位论文 图1 - 1 网页分类的体系结构 f i g u r el 一1a r c h i t e c t u r eo fw e bp a g ec a t e g o r i z a t i o n 1 3 3 文档分类的两阶段过程和两个数据集 基于统计的有指导的机器学习方法包括两个阶段的处理过程：训练过程和分 类过程实现。在这两阶段过程中使用的数据集或语料集分别称为训练数据集( 训 练集) 和测试数据集( 测试集) 。其中训练集是由专业人员进行标示了类别的文 档数据集合，测试集是未标示类别的待分类文档数据集。中文网页自动分类的过 程中有一个基本的假设：文档的内容与其中所包含的词有着必然的联系，同一类 的文档之间总存在多个共同的词，而不同类的文档所包含的词之间差异很大。 因此，分类器的训练过程可以看作是在已知文档类别的情况下，统计不同类 别内的词的分布，即在预先定义的类别集合c ( c - c ，c l ，c ) ) 与词项 集合t ( t = t ，t ，t ) ) 的幂集之间建立一种加权的映射关系，形成一 种向量表示；相应的，分类器的分类过程，可以看作在已知一篇文档内所包含词 项分布( 用一个向量表示) 的情况下，和在训练中形成的每个类别的向量表示进 行对比，来确定该文档与类别的隶属关系。网页分类的两阶段过程见图卜2 。 6 第1 章绪论 图1 2 网页分类两阶段处理过程 f i g u r e1 - 2t w o s t a g ep r o c e s so fw e bp a g ec a t e g o d z a t i o n 1 3 4 文档分类的评价指标 在文本分类领域，一般不使用定性指标而使用定量指标评价分类系统的优 劣，通常借鉴信息检索领域的评价标准来评价分类系统。主要的指标有：查准率、 查全率、和宏f ，值。 查准率( p r e c i s i o n ，简记为p ) ：是分类系统正确分类的文档数与实际分类 ， 的文档数的比率，它体现分类系统分类结果的准确程度。即：p = 二，其中，是 ，以 在分类正确的文档数，朋是实际分类的文档数。 查全率( r e c a l l ，简记为r ) ：是分类系统正确分类的文档数与应有的文档 ， 数的比率，它体现了分类系统分类结果的完备性。即：，= 二，其中，是分类正确 刀 的文档数，以为所有测试文档，应该有的文档数。 查准率和查全率这两个标准是互补的，单纯提高查准率就会导致查全率的降 低，反之亦然。尽管一个好的分类系统应该同时具有较高的查准率和较高的查全 率，但是实际的分类系统往往在二者之间作出一些折中，从而避免一个指标过低。 因此，人们还定义了另外一个评价指标： f 。值：反映查准率和查全率的综合效果。根据计算方式不同，分为微观f 。值 ( m i c r o - f 1 ) 和宏观f ，值( m a c r o f 。) 。其定义如下： 7 北京i t 业大学丁学硕士学位论文 _ i m i c r 。一e ：2 p r p + ， 胁册一曩= 昙喜互， ( 1 - 2 ) 2 x p ， m a c r o e = _ _ 。l _ 奠一 ( 卜3 ) ( p ，+ ) c i - i ，4 i 其中c 为训练集中文档的类别数，p ，是第i x 文档的查准率，是第i x 文档 的查全率。 1 4 文本分类算法 文本分类研究的是为一个文档分配一个或多个与定义类别的问题。分类方法 大多来自模式分类，基本可以分为三大类。一种是基于统计的方法，如 n a i v e b a y e s ，k n n ，支持向量机等方法：另一种是基于连接的方法，即人工神经 网络；还有一种是基于规则的方法，如决策树、关联规则等。下面介绍几种典型 的方法。 1 4 1r o c c h i o 方法相似度计算法 该分类方法思想比较简单，根据算术平均为每类文档集生成一个代表该类的 中心向量，然后在新的被分类文档到来时，确定新文档向量，计算该向量与每类 中心向量的距离( 相似度) ，则判定文档属于与文档距离最近的类，具体步骤如 下： ， 1 ) 通过对所有训练文档向量简单的算术平均计算每类文档集的中心向量； 2 ) 对新文档分词处理并将其表示为特征向量； 3 ) 计算新文档特征向量和每类中心向量间的相似度，公式： 材 w 雎w 业 j 砌( 盔，q ) = 了笋f ( 1 4 ) 1 f ( 以) ( w ) lk - i 扣l 其中，z 为新文档的特征向量，0 为第j 类文档的中心向量，m 为特征向量 8 第1 章绪论 的维数，为新文档向量第k 维权重，业为第j 类文档向量的第k 维权重。 4 ) 比较每类中心向量与新文档向量的相似度，将文档分类到相似度最大的 那个类别中。 1 4 2n a i v eb a y e r 贝叶斯方法 该文档分类的基本思想是计算文档属于类别的概率。文档属于类别的概率等 于文档中的每个词属于类别的概率的综合表达式，具体步骤如下： 1 ) 计算特征词属于第个类别的概率向量( ，w 2 ，w k i ，) ； d l 、 1 + n ( w k ，z ) 其中，= 尸( lc j ) = i l d i y l + n ( e ，z ) k = li - i ，尸( ic i ) 为词睨在类别c 中出现的权重，ld l 为该类别的训练文档数，( ，d ，) 为词在d ，中的词频， i 叫id i v t 为总词条数，( 既，d ，) 为类别q 所有词的词频之和。 k = li = 1 2 ) 在新文档到达时，根据特征词分词，然后按下面的公式计算该文本z 属 于类巳的概率： p ( c ，id ，；目) = p ( c 歹l 爹) np ( w 七ic _ ，；万) m “ 七毒l f c f 尸( c ，l r = l c ；万) 嘶 ( 1 - 5 ) 其中，p 10 ) = 毫嘉，p ( c ，i 爹) 为相似含义，l c i 为类别的总数， ( ，z ) 为词在z 中的词频； 3 ) 比较新文档属于所有类别的概率，将文档分到概率最大的那个类别中。 该算法的基本思想是：在给定新文档后，考虑在训练文档集中与新文档距离 最近( 最相似) 的k 篇文档，根据这k 篇文档所属的类别判定文档所属的类别， 9 w ，_ ， p 斤兀纠 秒 北京t 业大学工学坝土学位论文 具体算法步骤如下： 1 ) 根据特征项集合重新描述训练文档向量； 2 ) 在新文档到来时，根据特征词，确定新文档的向量表示； 3 ) 在训练文档集中选出与新文档最相似的k 个文档，计算公式为： m w t k 肛 s i m ( d 一，p ) 2 了笋f ( 1 6 ) 、( w 左) ( w 盖) i k = l k = l 其中，k 值得确定目前没有很好的方法，一般先定一个初始值，然后根据试 验测试的结果调整k 值，一般初始值定在几百到几千之间。d ，为第f 训练文档的 特征向量，p ，为第j 个新文档地特征向量，m 为特征向量的维数，为训练文 档向量第k 维权重，w 庸为第j 个新文档向量的第k 维权重； 4 ) 在新文档的k 个邻居中，依次计算每类的权重，计算公式如下： p ( i ，c j ) = 一_ s i m ( 2 ，孑。) y ( 孑。，c ) ( 1 7 ) 4 e k n n 其中，i 为新文档的特征向量，s i m ( i ，d r ) 为相似度计算公式，与上一步骤的 计算公式相同，而y ( z ，q ) y 蝴w j n 性函数，即，如果孑属于类勺，那么函数值 为1 ，否则为0 ； 5 ) 比较每类的权重，将文档分到权重最大的那个类别中。 1 4 4s v m 一支持向量机 支持向量机是v a p n i k 等人根据统计学习理论提出的一种新的学习方法，受 到了国际学术界的重视，近年来在很多领域得到了应用。统计学理论认为，学习 机器的期望风险r ( 国) 是由经验风险r e i n p ( c o ) 和置信范围g ( h n ) 组成，h 是学习机 器的v c 维，n 是训练样本数，缈为权值向量。由统计学理论发展而来的支持向 量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 算法能够有效地解决高维、非线性及有限 样本下的模式识别问题。它的主要思想是针对两类分类问题，在高维空间中寻找 一个超平面作为两类的分割，以保证最小的分类错误率。它通过非线性变换，将 输入向量映射到一个高维空间h ，在h 中构造最优分类超平面，从而达到最好的 泛化能力。支持向量机算法相当于求解一个凸集优化问题，因此局部最优解一定 是全局最优解。将支持向量机应用于网页文档自动分类，不仅有效地避免了维数 1 0 第l 章绪论 曼曼皇- - - - ,- - 一i i i _ m 曼曼曼曼鼍鼍 灾难，而且很多研究表明支持向量机分类器是优越的分类器之一。本文第2 章将 作详细介绍。 1 5 本课题的提出 互联网的信息呈指数级增长，网页分类技术已成为人们从海量的w e b 信息中 获取有效信息有效手段。经过多年的研究，网页分类研究有了一定的应用，但是 分类的正确率远没有普通文本分类高。在仅几年全国搜索引擎和w e b 挖掘大会的 中文网页自动分类评测中，经过人工挑选的相对规范的网页分类正确率也仅为达 到6 0 9 6 _ 7 0 。对随机网页的分类正确率就更低了。因此，提出本文研究课题， 旨在通过对w e b 数据的分析处理，探索一种表达网页信息的方法，研究影响分类 的因素，构造基于支持向量的模型，提高网页分类的质量和效果。从而为网页分 类技术在数字图书馆、主题搜索、个性化信息检索、搜索引擎目录导航、信息过 滤、主动信息推送服务等领域的广泛应用提供技术支持。 1 6 本文的组织结构 本文共分4 章，第1 章是绪论，介绍了本课题提出的背景，并对文本分类和 网页分类进行了回顾和展望，概述了网页分类模型及分类算法，并列出了本文的 研究内容；第2 章支持向量机理论，概述了统计学习理论、机器学习模型和标准 支持向量机分类方法，并总结了支持量机方法的特点；第3 章是网页信息预处理， 从网页结构入手，设计了一种网页预处理的流程并提出了一种联合特征选取方 法，改进了网页文档向量化模型；第4 章基于l i b s v m 的中文网页分类系统设计 及应用，简要介绍了l i b s v m 软件包，设计和实现了一个网页自动分类模型，采 用变步长的支持向量机参数优选方法，训练出了一个性能良好的分类器。基于此 分类器，参加了2 0 0 7 年全国搜索引擎与w e b 挖掘( s e l j | m 2 0 0 7 ) 中文网页自动分 类评测，最后论文给出了相关实验结果和s e w m 2 0 0 7 中文网页自动分类评测中的 和评测效果。 北京t 业大学t 学硕_ 上学位论文 第2 章支持向量机理论 传统的机器学习算法都是以经典统计学中的渐进理论为依据的，其理论基础 为统计学中的大数定理，即统计规律只有在已知样本数无限多的情况下才表现出 来。b a y e s 、k n n 等传统类型的分类器，都是以无限多的假设为前提，许多算法 的结论都是在训练样本趋于无穷的假设下得到的。但是，这一前提条件在实际中 是很难成立的。实际中的训练样本总是有限的，以样本数量趋于无穷所得到的经 验风险最小化原则为基础的算法，往往会出现过拟合、模型过于复杂等问题。国 内外很多学者对中英文的研究表明，在文本分类实践中建立一个标准的、足够大 的、在统计理论上有保证的训练样本库是极其困难的。我们也可以想象，即使是 人工建立起的样本库也不能保证完全准确，人工领域专家对于文档类别的判断也 是不尽相同的，更何况样本数目尽可能大所要耗费的人工劳动也是无法估计的。 所以符合要求的样本库的建立是很难的。各种研究都只能是在有限样本下得出的 结论，很难有理想的效果。而统计学习理论( s t a t i s t i c a ll e a r n i n gt h e o r y ，s l t ) 在这方面取得了实质性的突破【2 6 1 2 7 】，研究有限样本下机器学习的特征，正是统 计学习理论所要解决的问题。 2 1 统计学习理论 统计学习理论( s t a t i s t i c a ll e a r n i n gt h e o r y ，s l t ) 是v a p n i k 2 7 , 2 8 】等人在2 0 世纪7 0 年代末提出，并在9 0 年代逐渐完善的一种针对小样本的机器学习理论。 统计学习理论研究了有限样本条件下有关经验风险与期望风险之间关系等问题， 并据此提出了结构风险最小归纳原理，克服了以往经验风险最小化原则的缺点。 9 0 年代中期，基于统计学习理论的支持向量机方法( s u p p o r tv e c t o rm a c h i n e ， s v m ) ，在解决一系列实际问题中获碍成功，表现出优良的学习能力尤其是泛化 能力，能够有效地解决小样本学习问题。 2 1 1 机器学习的基本问题 机器学习的目的是根据给定的训练样本求得对某系统输入输出之间依赖关 系的估计，使它能够对未知输出做出尽可能准确的预测。我们希望构造具有学习 和推广能力的机器，它能模拟人的学习过程，通过对己知数据的学习，找出数据 间相互依赖的关系，从而对未知的数据做出判断。机器学习的模型见图2 1 。 1 2 第2 章支持向量机理论 输入x 输出y 预测输出y 图2 一l 机器学习模型 f i g u r e2 - 1m o d e lo fm a c h i n el e a r n i n g s 是研究的系统，l m 是学习器。给定x ，s 输出y ，l m 输出歹。可以表示 为：变量y 与x 存在一定的未知依赖关系，即遵循某一未知的联合概率f ( x ，y ) ( x 和y 之间的确定关系可以看作是其特例) ，机器学习问题就是根据n 个独立分 布观测样本： ( x 1y 1 ) ，( x 2 ，y 2 ) ，( 矗，y 。) ( 2 1 ) 在一组函数 厂( x ，w ) ) 中求一个最优的函数f ( x ，w o ) 对依赖关系进行估计，使 期望风险( 2 2 ) 最小。 尺( w ) = i 上( 弘f ( x ，w ) ) d f ( x ，y ) ( 2 2 ) 其中， f ( x ，叻) 称作预测函数集，w 为函数的广义参数， f ( x ，们) 可以表示 任何函数集；l ( y ，f ( x ，w ) ) 为由于用f ( x ，w ) 对y 进行预测而造成的损失，不同类 型的学习问题有不同形式的损失函数。预测函数也称作学习函数、学习模型或学 习机器。 有三类基本的学习问题，即模式识别、函数逼近和概率密度估计。 对模式识别问题，输出y 是类别标号，两类情况下y = 0 ，1 ) 或 一1 ，1 ) ，预测函 数称作指示函数，损失函数可以定义为： 三绯例= 侄矿i fy y = 舷f ( x , 比w ) , ( 2 - 3 ) 使风险最小就是b a y e s 决策中使错误率最小。在函数逼近问题中，y 是连续 变量( 这里假设为单值函数) ，损失函数可定义为 l ( y ，f ( x ，w ) ) = ( y - f ( x ，w ) ) 2( 2 - 4 ) 即采用最小平方误差准