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

摘要随着i n t e m e t 的发展，为了能够有效地组织和分析海量的w e b 信息，人们希望能够对网页实现自动分类。因此，网页分类技术便成了快速且有效地组织网络上海量信息的一项重要技术。它是使用机器学习的方法实现网页类别的自动标注。在众多的网页分类算法中，支持向量机因为其出色的学习能力，已成为机器学习界的研究热点。介绍了支持向量机技术发展，原理和相关技术，概括了支持向量机技术在网页分类中的重要作用。阐述了目前支持向量机常用的训练算法，针对目前训练算法在面对高维度超大数量集训练时存在的训练时间过长、迭代次数过多的问题，提出了基于三样本点迭代的支持向量机训练算法。在保证获得解析解的前提下，将每次迭代优化的样本点个数由原有算法的两个提升为三个，减少了迭代次数，缩短了训练算法的学习时间。针对经典支持向量机训练算法不支持增量学习的缺陷，分析并证明了现有增量学习算法中普遍存在的丢失样本有效信息的问题，提出了基于超平面距离的支持向量机增量学习算法。根据支持向量的几何分布特点，采用超平面距离预选取方法，从增量样本中选取最有可能成为支持向量的样本进行增量学习，在保证不丢失样本有效信息的前提下，减少了增量学习时的样本个数，提高增量学习的训练速度。最后，将改进后的支持向量机训练算法应用到网页分类系统中，对以上的改进策略进行实验比较和性能分析。实验数据表明，本文算法具有更高的分类的效率和准确度。关键词：支持向量机，网页分类，s m o 算法，增量学习，超平面距离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 nb a s e do ns u p p o r tv e c t o rm a c h i n et e c h n i q u el i uk a n g w e i ( c o m p u t e ra p p l i c a t i o nt 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 ea b s t r a c tw i t ht h ed e v e l o p m e n to fi n t e m e t , w eh o p et oc l a s s i f yt h ew e bp a g e sa u t o m a t i c a l l yi no r d e rt oo r g a n i z ea n da n a l y s et h el a r g en u m b e r so fi n f o r m a t i o ne f f i c i e n t l y a m o n gt h ev a r i o u sw e bp a g ec l a s s i f i c a t i o nm e t h o d s ，s u p p o r tv e c t o rm a c h i n e ( s v m ) b e c a m et h eh o ts p o tr e s e a r c ha r e ab e c a u s eo fi t se x c e l l e n tl e a r n i n gc a p a c i t y f i r s to fa l lw ei n t r o d u c et h ed e v e l o p m e n to fs u p p o r tv e c t o rm a c h i n e ，w o r k i n gt h e o r ya n dr e l a t e dt e c h n o l o g i e s t h e nw es u m m a r i z et h ei m p o r t a n tf u n c t i o no ft h es v mi nw e bp a g ec l a s s i f i c a t i o n w es t u d yo nt h es v mt e c h n o l o g y , a i mt ot h el o n gt i m eo ft r a i n i n ga n dl a r g en u m b e r so fi t e r a t i o nw h e nt r a i n i n gi nt h eh i g h d i m e n s i o nd a t a s e t ，w ep r o p o s ean e ws v mt r a i n i n ga l g o r i t h mb a s e do nt h r e ep o i n ti t e r a t i o n i ti n c r e a s et h en u m b e ro fo p t i m i z e ds a m p l ep o i n tf r o mt w ot ot h r e ei ne a c hi t e r a t e dt i m e ，r e d u c et h ei t e r a t i o nt i m ea n dt r a i n i n gc o s t t o w a r d st h es h o r t a g e so ft h ec l a s s i cs v mt r a i n i n ga l g o r i t h m ，w er e s e a r c ht h et h e o r yo fs v mi n c r e m e n t a ll e a r n i n ga l g o r i t h m ，a n a l y s ea n di m p r o v et h a ti tl o s tm e f u l li n f o r m a t i o no fs a m p l es e t s ，p r o p o s ean e wm e t h o db a s e do nt h eh y p e r p l a n ed i s t a n c e a c c o r i n gt ot h eg e o m e t r i cd i s t r i b u t i o nc h a r a c t e ro fs v m ，w eu s e 也ep r e - s e l e c t i o nh y p e r p l a n ed i s t a n c em e t h o dt oc h o o s et h em o s tp o s s i b l es u p p o r tv e c t o rs a m p l ei n t ot h ei n c r e m e n t a ll e a r np r o c e s s i n g o nt h eb a s i so fm a n t a i nt h eu s e f u l li n f o r m a t i o n ，t h i sm e t h o dc a nd e c r e a s et h en u m b e r so fi n c r e m e n t a ll e a r n i n gs a m p l ea n di m p r o v et h et r a i n i n gs p e e do fi n c r e m e n t a ll e a r n i n g a tl a s t ，w eu s et h ei m p r o v e ds v ml e a r n i n ga l g o r i t h mi n t ot h ew e bp a g ec l a s s i f i c a t i o ns y s t e m ，c o m p a r ea n da n a l y s et h ec a p a b i l i t yo fc l a s s i f i c a t i o n t h er e s u l ti n d i c a t e st h a tt h ep r o p o s e dm e t h o dh a sh 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 ：s u p p o r tv e c t o rm a c h i n e ，w e bp a g ec l a s s i f i c a t i o n ，s m oa l g o r i t h m ，i n c r e m e n t a ll e a r n i n g ，h y p e r p l a n ed i s t a n c e关于学位论文的独创性声明本人郑重声明：所呈交的论文是本人在指导教师指导下独立进行研究工作所取得的成果，论文中有关资料和数据是实事求是的。尽我所知，除文中已经加以标注和致谢外，本论文不包含其他人已经发表或撰写的研究成果，也不包含本人或他人为获得中国石油大学( 华东) 或其它教育机构的学位或学历证书而使用过的材料。与我一同工作的同志对研究所做的任何贡献均已在论文中作出了明确的说明。若有不实之处，本人愿意承担相关法律责任。学位论文作者签名：日期：沙7 年夕月2 乙e l学位论文使用授权书本人完全同意中国石油大学( 华东) 有权使用本学位论文( 包括但不限于其印刷版和电子版) ，使用方式包括但不限于：保留学位论文，按规定向国家有关部门( 机构)送交学位论文，以学术交流为目的赠送和交换学位论文，允许学位论文被查阅、借阅和复印，将学位论文的全部或部分内容编入有关数据库进行检索，采用影印、缩印或其他复制手段保存学位论文。保密学位论文在解密后的使用授权同上。学位论文作者指导教师签名日期：砷年，月1 日日期：7 年岁月2 日中国石油大学( 华东) 硕士学位论文1 1 课题背景与意义第一章前言随着i n t e m e t 的迅速发展，互联网上的信息量急剧增长，截止到目前g o o g l e 检索的页面数已经超过n 8 0 亿。为了能够有效地组织和分析这些海量的w e b 信息，人们希望能够按照其内容实现对网页的自动分类。因此，网页自动分类技术便成了快速且有效地组织网络上海量信息的一个重要技术【1 1 。它是使用机器学习的方法实现网页类别的自动标注。目前，网页自动分类技术在数字图书馆、主题搜索、个性化信息检索、搜索引擎的目录导航服务、信息过滤、主动信息推送服务等领域得到了广泛地应用【2 】。在已经出现的多种网页自动分类算法中，支持向量机( s u p p o r tv e c t o rm a c h i n e ，简称s v m ) 因为其出色的学习能力，已成为机器学习界的研究热点 3 1 。它以统计学习理论为基础，具有简洁的数学形式、直观的几何解释和良好的泛化能力，避免了局部最优解，有效地克服了“维数灾难 ，且人为设定的参数少，便于使用，已经在人脸检测，手写体数字识别，文本自动分类等许多领域获得了广泛的应用【4 】。但是，s v m 也存在一些缺陷，在很多方面，尤其是超高维、大样本集训练时仍然不能令人满意。本课题旨在对支持向量机技术进行研究，针对目前算法中普遍存在的训练时间过长，不支持增量学习等缺点提出改进策略，并将改进后的算法应用到网页分类系统中，从而提高分类的效率和准确度。1 2 国内外研究现状支持向量机理论是在上世纪9 0 年代由v a p n i k 等人提出的，它是一种建立在统计学习理论基础上的新型机器学习方法。在此之前2 0 世纪7 0 年代，统计学习理论己经建立起了基本的体系，而直n 9 0 年代这一理论框架下才产生了“支持向量机( s v m ) ”这通用的机器学习方法。或许是统计学习理论为人们系统研究有限样本情况下机器学习问题提供了有力的理论基础，或许更是因为在这一基础上的支持向量机方法表现出的令人向往的优良特性，人们开始迅速重视这一早在2 0 年前就该重视的学术方向 5 , 1 5 】。1 s v m 训练算法研究现状v a p n i k 提出的支持向量机的主要思想是针对二类分类问题，在高维空间中寻找一个第一章前言超平面作为二类的分割，以保证最小的分类错误率。最优超平面的维护是一个复杂的学习训练的过程。它可以最终归结为一个凸二次规划( q u a d r a t i cp r o g r a m m i n g ，简称q p ) 问题，对于小规模的q p 问题，经典最优化算法，如牛顿法、拟牛顿法等都可以较好地求解，但当训练集很大，特别是支撑向量数目也很大时，一般的训练算法将无法完成【2 5 】。研究人员提出了许多针对大规模训练集的s v m 训练算法。1 9 9 5 年，c 0 n e s 和岫提出c h u n k i 】略的算法【2 6 1 ，其出发点是：删除矩阵中对l a g r a n g e乘数为零的行和列将不会影响最终的结果，因此，可将一个大型q p i ；1 题分解为一系列较小规模的q p i ； 题，然后找到所有非零的l a g r a n g e 乘数并删除所有为零的l a g r a n g e 乘数。在算法的每步中c h u n k i n g 都解决一个q p 问题，其样本为上一步所剩的具有非零l a g r a n g e 乘数的样本以及m 个不满足k k t 条件的最差样本。如果在某一步中，不满足k k t条件的样本数不足m 个，则这些样本全部加入到新的q p i h - 题中。每个q p 子问题都采用上一个q p 子问题的结果作为初始值，在算法进行到最后一步时所有非零l a g - r a n g e 乘数都被找到，从而解决了初始的大型q p i h 7 题。c h u n k i n g 算法将矩阵规模从训练样本数的平方减少到具有非零l a g r a n g e 乘数的样本数的平方。然而，在训练集的支持向量数很大时，c h u n k i n g 算法仍然无法将矩阵放人内存中。1 9 9 7 年：q s t m a 等人证明f 2 7 1 ，如果存在不满足k k t 条件的样本，则在将其加入到前一子问题的集合中后，重新优化该子问题，可行点( f e a s i b l ep o i n t ) 将依然满足约束条件，且性能严格地得到了改进。因此，如果每步至少加入一个不满足k k t 条件的样本，则利用一系列的q p 子问题就可以保证实现收敛。值得注意的是，c h u n k i n g 算法满足该定理，因此可保证收敛。o s u n a 等在此基础上提出了一种s v m 训练算法。即首先建立一个工作集( w o r k i n gs e t ) ，保持其大小不变，在解决每个q p 子问题时，先从工作集中移走一个样本，并加入一个不满足k k t 条件的样本，再进行优化。但是该算法存在效率问题，因为在每一步中，进行一次q p i b - 题的最优化只能使一个样本符合k k t 条件。1 9 9 8 年，j o a c h i m s 提出一种解决大型s v m 学习的算法，称为s v m “g h t 2 8 1 。该算法实际上是o s u n a 方法的推广。其基本思想是，如果存在不满足k k t 条件的样本，则以某种方式选择q 个样本作为工作集，其它样本保持不变，在这个工作集上解决q p i h - 题。重复这一过程，直至所有样本都满足k k t 条件。该算法得到了很好的应用，台湾大学林智仁教授等在此基础上开发设计的一个简单、易于使用和快速有效的s v m 模式识别与回归2中国石油大学( 华东) 硕士学位论文的软件包“b s v m 。但是s v m u 班算法对于每个子q p 问题都是用数值算法进行求解，在计算时仍然要存储每次二次规划问题的核函数矩阵，当数据集足够大时，计算机的内存仍然不能满足需求。1 9 9 8 年，p l a t t 提出一种名为s m o ( s e q u e n t i a lm i n i m a lo p t i m i z a t i o n ) 的s v m 训练算法【2 9 1 。该算法基于o s u n a 的 i eb y l ，将一个大型q p i h 题分解为一系列最小规模的o p 子j h - j题，即仅具有两个l a g r a n g e 乘数的q p 问题，从而使得原问题可以通过分析的方法加以解决，避免了在内循环中使用数值算法进行q p 最优化。s m o 的一个显著优点是不需使用数值分析中的q p 软件包。值得注意的是，该算法在训练线性s v m 时，可以获得非常好的性能。在对s m o 作进一步的研究之后，1 9 9 9 年p l a t t 指出，通过核优化方法可大大提高s m o 的性能。s m o 算法的威力在于两个数据点的优化问题可以获得解析解，从而避免了多样本情况下的数值解不稳定及耗时问题，同时也不需要大的矩阵存储空间，特别适合稀疏样本。另外，其工作集的选择不是采用传统的最陡下降法，而是采用启发式策略。p l a t t 设计了两个嵌套的循环来寻找待优化的样本然后在内环中选择另外一个样本，完成一次优化，再循环，进行下一次优化，直至全部样本都满足最优条件【1 5 】。s m o 算法主要耗时在最优条件的判断和在非线性情况下误差的重置方面。所以近来对s m o 算法的改进集中在这两个方面。k e e r t h i 等人修正了优化条件 3 0 】，并针对经验方法提出了两个改进方法，以保证算法收敛，并减少迭代次数。无论是o s u n a 的分解算法还是p l a t t 的s m o 算法，都使用满足一定条件的k k t 作为选择自由变量集合和评价算法是否收敛的标准。但是以前的k k t 原则中参数选择具有一定的未确定性，显然用这个参数作为选择自由变量和评价算法是否收敛的标准是不够准确的，从而对某些特定的问题，可能会影响到算法的效率。k e e r t h i 改进后的算法采用了一种新型的k k t 条件，减少了计算机的消耗，提高了效率。2 s v m 增量学习算法研究现状经典s v m 训练算法是不支持增量学习的，如果有新的样本加入，则需要对所有训练样本重新进行训练，非常浪费时间。如果能将原有的知识保留起来与新加入的样本一起进行训练，则既能继承先前所学习的知识，又能减少由于新样本的加入而重新学习的时间，这正符合人类的学习习惯。实际中，样本的采集都是不断积累的，经常有新的样本第一章前言加入是很常见的，而且支持向量机的最优分类面只与支持向量有关。因此，对s v m 算法中增量学习的研究具有重要的理论意义和实用价值。萧嵘等人提出t s i s v m 方法口5 1 。该算法把历史样本训练得到的s v 集、新增样本中的错分样本一起训练得到新的分类器，把历史样本中的剩余样本和新样本的正确分类样本起作为增量，多次迭代，直到增量中的错分样本为空时，收敛于所得分类器。为了加快对s v 集搜索的收敛速度，萧嵘等人又提出了q i s v m 算法，有选择的淘汰一些对最终分类影响很小的样本，从而缩减历史样本集的规模。此方法计算复杂度为d ( n 。3 y + d n g 矿) ，远小于重新计算的复杂度，并且减少了对存储空间的占用，但缺点是需要人为的选择很多参数。s y e d 等提出的增量学习算法【3 6 1 2 p ，增量训练由s v 样本组成，再训练只需要进行一次即可完成，所有的非s v 样本点都抛弃。这样减少了计算复杂度，但是忽略了历史样本集的非s v 最终可能成为支持向量的问题。曾文华等人提出将违背k k t 条件的样本和s v 集一起训练的新算法，更能体现样本的分布状态对学习结果的影响【3 7 1 。该算法分别对样本和新增样本训练得到分类器f1 ，r2 ，和支持向量集s v l 、s v 2 ，在历史样本中找到违背r2 1 拘k k t 条件的样本，加入到s v l 、s v 2 一起训练得到最终分类器。该算法l ：l s y e d 的分类精度提高了2 个百分点左右，训练时间也减少了很多。为了进一步提高精度，唐小力等人考虑到两类样本中数目的样本被错分的机率较大的问题，对两类样本加权，减少样本类中由于样本数不平衡而对分类造成的影响【3 8 】。实验表明，算法和上述改进的算法相比，正确率要提高2 个百分点左右。采用多支持向量机对新增样本进行学习能够弥补由于单一分类器而造成的新增样本分布状况敏感度高的问题，采用多个分类器训练，可以降低新增样本对原分类器的敏感度。b a t c h s v m 增量学习算法【3 9 】将新增样本分成互不相交的多个子集，对新增样本分批训练，每次训练中把位于分类间隔以内的样本加入到历史样本中，重新训练，直到所有新增样本都训练完。该算法降低了空间复杂度，时间复杂度并没有提高。此外，该算法的应用还是在新增样本的子集具有相似分布前提下进行的。杨静等人提出了d m _ m i s v m 算法【4 0 1 ，改善了b a t c h s v m 增量学习算法中的不足。4中国石油大学( 华东) 硕士学位论文它将历史样本分解成互不相交的n 个子集，训练出n 个分类器ri ，依次对新增样本训练，保留训练精度p i ，以分类精度小于所给精度为循环条件，不断的改善分类精度小于所给分类精度的分类器提高了分类精度。对于增量问题，a h m e d s n 最早提出ts v m 增量训练算法 3 7 1 ，该算法每次只选一小批常规二次规划算法能处理的数据作为增量，保留原样本中的支持向量和新增样本混合训练。g a u w e n b e r g h sg 等人提出了增量训练的精确解【4 1 1 ，即增加一个训练样本或减少一个训练样本对l a g r a n g e 系数和支持向量的影响，该算法是有效的，缺点是当样本无限增多时，还必须放弃一些样本才能够实用。孔锐等人提出了一种快速增量学习算法【4 2 】，该算法依据边界向量不一定是支持向量，但支持向量一定是边界向量的原理，首先选择那些可能成为支持向量的边界向量，进行s v m 的增量学习，找出支持向量，最终求出最优分类面，提高了训练速度。此外，张波等人提出了基于中心距离比值的增量运动向量机( c d r i s v m ) 1 4 3 1 ，利用中心距离比值，在保证训练和测试准确率没有改变的情况下，大大提高了收敛速度。李东晖等人提出了基于壳向量的线性s v m 增量学习算法m ，通过初始样本集求得壳向量，进行s v m 训练，得到支持向量集，降低了二次规划过程的复杂度，提高了整个算法的训练速度和分类精度。1 3 论文研究内容论文的主要工作内容如下：( 1 ) s m o 算法的研究和改进p l a t t 提出的s m o 算法解决了大规模s v m 问题训练时计算量过大，存储量过多的问题，它是将分结算法思想推向极致得出的，每次迭代仅优化两个点的最小子集，而且这两个点的优化都可以获得解析解，两个点的选择也是启发式的。s m o 的主要问题表现在当面对大数据集训练时，训练时间过长，收敛速度过慢。这是因为每次优化的点过少，所以迭代的次数过多，造成最终迭代时间长。因此应该尽可能的增多s m o 每次迭代优化的点的个数，前提是要保证能够获得各优化点的解析解。另外，s m o 算法启发式选择点的方法，还存在着随机的成分，造成因为点的优化先后次序不一样，最终收敛5第一章前言的时间差别很大。因此，改进启发式选择优化点的策略也是研究的方向。( 2 ) s v m 增量学习算法的研究和改进经典的s m o 算法本身是不支持增量学习的，每次增加新样本点时需要重新训练。现在流行的增量算法大都把精力集中在如何筛选样本点，尽可能的选择可能成为边界点的样本点，而删除那些不可能成为支持向量的样本点。在这个过程中各个增量算法都考虑了原来训练集中那些非支持向量的点，而忽略了新增训练集中那些满足k k t 条件的点，一般认为他们不可能成为支持向量，因此统统删除，但是实际上他们的作用跟原来训练集中非支持向量样本点的作用是一致的。因此应该采取策略将这部分中可能成为支持向量的点也加到下一步训练的集合中，以提高增量学习的精度，这是另一个研究内容。1 4 论文组织结构论文共分六章，具体结构如下：第一章“前言 ，阐述了论文的研究背景和意义以及国内外研究现状，介绍了论文的主要研究内容，最后给出论文的组织结构。第二章“相关关键技术 ，首先介绍了网页分类技术的发展、工作原理和评价指标，重点介绍了基于支持向量机的网页分类技术。然后介绍目前主流的支持向量机训练算法s m o 算法和s v m 增量学习算法，最后总结指出了现有经典算法中存在的问题。第三章“基于三样本点迭代的支持向量机改进算法 ，对s m 0 算法的特点进行了分析，指出了该算法在面对高维大数量样本集是存在的迭代次数过多，训练时间过长的问题，针对其存在的问题，提出了基于三样本点迭代的s m o 改进算法。第四章“基于超平面距离的支持向量机增量学习算法”，在对现有支持向量机增量学习算法研究的基础上，分析并证明了现有s v m 增量学习算法普遍存在的丢失有效样本信息的问题。根据支持向量机的几何特性，提出了基于超平面距离的支持向量机增量学习算法。第五章“中文网页分类实验系统设计 ，为了验证第三章、第四章所提到的改进算法的效果，设计了中文网页分类实验系统。通过实验证明了改进的算法提高了网页分类的效率和准确率，最后对两种改进方法进行了比较。“总结”，对全文进行了总结，说明了论文的主要工作、主要创新点、存在的不足6中国石油大学( 华东) 硕士学位论文以及未来发展的方向。7第二章相关关键技术2 1 网页分类技术第二章相关关键技术在w e b 出现之前，人们已研究过许多普通文档分类的方法，形成了各种文档自动分类( 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 ) 技术 6 1 。随着海量网页信息的涌现，a t c技术的处理对象从普通文档扩展到网页信息，自然地，a t c 技术成了实现网页自动分类的基础。所谓文档自动分类就是用计算机程序来确定指定文档和预先定义类别之间的隶属关系【刀。2 1 1 分类预处理技术( 1 ) 文本分类所谓文本分类，实际上就是对收集的文献给出其标识导引，通过分类，文本被加工为特征明确，便于检索和利用的数据记录。基于这样的思想：已知一定范围内的类目的主题，如果知道欲分类的文献属于其中的某一个类目，那么就可以把该类的主题赋予该文献。对大量的训练文本进行人工分类，它们分别属于这已知类中的一类，然后对训练文本训练构成分类器，当对后来的文本进行分类时，利用分类器把它们分类到已知的类中。从数学角度讲，分类的实质就是要精确地反映文献与属性的关系【引。分类器系统结构如图所示：、厂、可训练厂圈咽、。l 律凿巽l集7 悟一l益圄圜信息 、j乡l 测试l引i 兰竺广 空兰l ，7 削i 集i。阿司i务l预处理特征提取训练、分类图2 - 1 分类器系统结构图f i 9 2 - 1c 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 m8中国石油大学( 华东) 硕士学位论文( 2 ) 文本的表示计算机并不具有人类的智能，人在阅读文章后，根据自身的理解能力可以产生对文章内容的模糊认识，而计算机并不能轻易地“读懂”文章，从根本上说，它只认识0 和1 ，所以必须将文本转换为计算机可以识别的格式。根据“贝叶斯假设 ，假定组成文本的字或词在确定文本类别的作用上相互独立。这样，就可以使用文本中出现的字或词的集合来代替文本，这将丢失大量关于文章内容的信息，但是这种假设可以使文本的表示和处理形式化，并可在文本分类中取得较好的效果【羽。目前，在信息处理方向上，文本的表示主要采用向量空间模型( v s m ) 。其基本思想是以向量来表示文本：眠，呒，呢，呒) ，其中形为第i 个特征项的权重，一般可以选择字、词或词组作为特征项，根据实验结果，普遍认为选取词作为特征项要优于字和词组【9 】。因此，要将文本表示为向量空间中的一个向量，就首先要将文本分词，由这些词作为向量的维数来表示文本，最初的向量表示完全是0 、1 形式，即如果文本中出现了该词，那么文本向量的该维为l ，否则为0 。( 3 ) 预处理网页分类所面对的对象是i n t e r n e t 上的网页，格式多种多样，为了确保网页分类的顺利进行，首先要对网页进行预处理。同普通英文文本相比，中文网页具有自身的特性：1 ) 中文网页使用中文编辑。不像英语单词之间存在自然的间隔，中文需要分词处理。而且分词的效果能够显著地影响分类效果；2 ) 网页使用超文本设计。它包含大量的h t m l 标签和超链接。可以利用这些信息来改进分类的质量；3 ) 网页通常包含大量的“噪音”。同普通文本相比，网页的设计比较随意，通常包含各类广告，设计人员的注释以及版权申明等无用信息。有时同一个网页甚至会包含多个不同的主题【l 们。因此，对于中文网页的分类，最重要的预处理任务是对网页进行分词，分词的效果好坏会直接影响到后面的其他处理过程【lo 】。中文文本的自然语言中词与词之间没有明显的切分标志，所以首先需对文本进行分词处理。中文文本分词有不少成熟的方法，例如基于字符串匹配的分词方法，基于理解的分词方法和基于统计的分词方法【1 1 1 ，因分词不是本课题的研究重点，在此不作赘述。( 4 ) 特征提取特征提取的目的在于减小文本的特征向量维数，去除冗余特征，保留有区分能力的特征。同时，具有区分能力的特征可以提高系统的效率和精度，所以文本分类系统中的特征选择部分是至关重要的。特征提取的基本思想通常是构造一个评价函数，对特征集9第二章相关关键技术的每个特征进行评估。这样每个特征都获得一个评估分，然后对所有的特征按照其评估分的大小进行排序，选取预定数目的最佳特征作为结果的特征子集。常用的特征选择方法有：文档频率、信息增益、互信息、z2 统计量、期望交叉熵、文本证据权和几率比等【1 2 1 。特征提取的过程可以分为以下三步：1 ) 文本粗降维：文本分词后可以通过计算每个词在语料库中的词频进行粗略的降维，方法是删除一些频率很高与很低的词，这些词对分类作用不大或是没有实际意义的功能词。2 ) 计算相对词频：相对词频为归一化的词频，其计算方法主要运用t f i d f 公式：州) 2 再丽( d ) x 丽l o g ( n i n e )( 2 - 1 )其中，形( d ) 为词t 在文本d 中的权重，而矿( d ) 为词形在文本d 中的词频，为训练文本的总数，栉，为训练文本集中出现形的文本数，分母为归一化因子。t f i d f 表示法中包含了文档词频，反映了词条区分文档内容属性的强弱：词频越高，则区分能力越强；同时 i t i d f 中也包含了词条在文档集中出现范围的量度：包含该词条的文档越多，则它区分文档内容属性的能力越弱【1 3 1 。3 ) 文本数字化。文本数字化即是把文本表示成一个稀疏向量，向量的分量是词的权重，词，在文本d 上的权重记为w ( t ，d ) 1 4 】。2 1 2 网页分类算法分类目前，主要的文档自动分类算法可以分为三类【1 5 】：1 ) 词匹配法。词匹配法又可以分为简单词匹配法和基于同义词的词匹配法两种。简单词匹配法是最简单、最直观的文档分类算法，它根据文档和类名中共同出现的词决定文档属于哪些类。很显然，这种算法的分类规则过于简单，分类效果也很差。基于同义词的词匹配法是对简单词匹配法的改进，它先定义一张同义词表，然后根据文档和类名以及类的描述中共同出现的词( 含同义词) 决定文档属于哪些类。这种分类算法扩大了词的匹配范围，在性能上要优于简单词匹配法。不过，这种算法的分类规则仍然很机械，而且同义词表的构成是静态的，对文档的上下文不敏感，无法正确处理文档中其具体含义依赖于上下文的词，分类的准确度也很低。l o中国石油大学( 华东) 硕士学位论文2 ) 基于知识工程的方法。基于知识工程的文档分类方法，需要知识工程师手工地编制大量的推理规则，这些规则通常面向具体的领域，当处理不同领域的分类问题时，需要不同领域的专家制定不同的推理规则，而分类质量严重依赖于推理规则的质量。因此，在实际的分类系统中较少使用基于知识工程的学习法。3 ) 统计学习法。统计学习法和词匹配法在分类机制上有着本质的不同。它的基本思路是先搜集一些与待分类文档同处一个领域的文档作为训练集，并由专家进行人工分类，保证分类的准确性，然后分析这些已经分好类的文档，从中挖掘关键词和类之间的联系，最后再利用这些学到的知识对文档分类，而不是机械地按词进行匹配。因此，这种方法通常忽略文档的语言学结构，而用关键词来表示文档，通过有指导的机器学习来训练分类器，最后利用训练过的分类器来对待分类的文档进行分类。这种基于统计的经验学习法由于具有较好的理论基础、简单的实现机制、以及较好的文档分类质量等优点，目前实用的分类系统基本上都是采用这种分类方法。根据分类结果的不同，基于统计学习法的分类系统在整体上可以被分为两类：独立二元( i n d e p e n d e n tb i n a r y ) 分类系统和m 元( m - a r y ) 分类系统【l 酊。所谓独立二元分类，就是给定一篇文档，分类系统对每一个类都独立地判断这篇文档是否属于该类：要么属于，要么不属于，而不存在其它的结果，并且在分类过程中，不同类别之间互不影响。所谓m 元分类就是给定一篇文档，系统计算这篇文档与所有预先定义的类的相似度，并按这篇文档和各个候选类的相似度排序，最后输出候选类列表。图2 - 2 网页分类算法分类f i 9 2 - 2w e bp a g ec l a s s i f i c a t i o na l g o r i t h m s第二章相关关键技术2 1 3 常用网页分类算法1 k n n 算法。k n n 分类算法是一种传统的基于统计的模式识别方法。算法思想很简单：对于一篇待分类文档) c ，系统在训练集中找到k 个最相近的邻居，使用这k 个邻居的类别为该文档的候选类别。该文档与k 个邻居之间的相似度为候选类别的权重，然后使用预先得到的最优截尾阈值，就可以得到该文档的最终分类列表。k n n 算法的定义如公式2 - 2 所示。y ( x ，c ) = s i m ( z ，d ，) y ( d ，c j ) 一6 jd t t 删( 2 - 2 )其中，x 为一篇待分类网页向量表示；d 为训练集中的一篇实例网页向量表示；c 为一类别；y ( 吐，c ) 0 ，1 ) ；b j 为预先计算得到的c ，的最优截尾阈值；s i m ( x ，d ) 为待分类网页与网页实例之间的相似度。k n n 算法本身简单有效，它是一种l a z y - - l e a r n i n g 算法，分类器不需要使用训练集进行训练，训练时间复杂度为0 。k n n 分类的计算复杂度和训练集中的文档数目成正比，也就是说，如果训练集中文档总数为n ，那么k n n 的分类时间复杂度为0 ( n ) 1 0 1 。2 n b 算法设彳是类标号未知的数据样本。设日为某种假定，如数据样本戈属于某特定的类c 。对于分类问题，我们希望能确定尸( 日ix ) ( 给定观测数据样本，假定日成立的概率) 。尸( 日lx ) 是后验概率，条件下日的后验概率。贝叶斯定理是：p ( hix ) ：p ( x 万ih - ) p ( h )( 2 3 )p ( x 、。其中，p ( x1 日) 是条件日下，的后验概率。p ( x ) 是样本具有某些属性值的概率，尸( 日)是样本属于某个类的概率 1 6 】。贝叶斯文本分类模型是一种典型的基于统计方法的分类模型。贝叶斯定理是贝叶斯理论中最重要的一个公式，是贝叶斯学习方法的理论基础【1 8 】，它将事件的先验概率与后验概率巧妙地联系起来，利用先验信息和样本数据信息确定事件的后验概率。该算法的主要思想是基于贝叶斯假设，即文档中的词汇在确定文本类别的作用上相互独立，也就是说，词汇之间相互独立并且同一词汇在文档中出现的概率与词汇在文档中的位置无关。它首先计算特征词属于每个类别的先验概率，在新文本到达时，根据特1 2中国石油大学( 华东) 硕士学位论文征词的先验概率计算该文本属于每一个类别的后验概率，最后取后验概率最大的类别作为分类结果【1 8 】。先验概率独立于训练样本数据，而后验概率反映了样本数据对类c ，的影响。根据贝叶斯定理有：p ( cid ) ：! ! 里! 1 2 1 1 1 2 ：墨生：竺：坠! 鱼! 墨! ! !( 2 - 4 )-7尸( d )尸( 形，呢)其中，形，d = ( ，形，呢) ，p ( d ) 对所有的类都是常数，可以忽略不考虑。贝叶斯分类方法有一个前提假设，即各个项之间相互独立，因此我们可得：p ( qf 功= 尸( 形，呢ic j ) p ( c , ) = 尸( q ) i - i 尸( 形lq )( 2 - 5 )；1从而基于b a y e s 定理的文本分类公式可表示如下：c = a r g m a x p ( c ji ，呢) = a r g m a x p ( c _ ，) 兀p ( 形ic )( 2 6 )t = l2 2 支持向量机基本原理2 2 1 支持向量机概述支持向量机( s v m ) 是由v a p n i k 提出的，它是统计学习理论的一种实现方式，它不仅追求训练样本上的准确性，而且在训练样本准确性的基础上考虑了学习空间的复杂性，即在样本学习精度和学习空间复杂性之间采取了一种折中，从而使得所得到的模型对于未知样本具有好的推广泛化能力。传统的学习理论基于经验风险最小化原则( e i 洲) ，以大量的样本进行训练，找到一个能够精确逼近这些样本的函数。该函数能够对未知样本做出好的预测。2 0 世纪6 0 年代，很多学者认为决定学习机推广能力的唯一因素就是它在训练集上的性能，认为e r m 原则是不言而喻的，但如果学习能力过强，就会产生所谓的过学习情况，此时学习到的函数复杂性太高，把训练数据中的噪声也全部当作实际数据的规律进行学习，因此泛化推广能力极差。v a p n i k 则提出了基于结构风险最小化s r m 原则的算法，在函数集复杂性和样本复杂性之间进行折中，并在理论上给出了推广误差的界，该推广误差的界分为两部分，经验风险和置信范围。经验风险即传统学习机在训练样本上的误差( 置信范围则以v a p n i k 等提出的v c 维理论的概念为参数进行度量，该参数衡量了函数集的复杂性。一个好的学习机需在二者之间做出权衡，第二章相关关键技术从而达到总的推广误差最小，此即结构风险最小化原则) 2 0 l 。2 2 2 支持向量机的几何意义s v m 具有直观的几何意义，对于线性可分情况：给定训练样本 l ，y 1 ) ，( 而，y f ) ，x e r 一，y + 1 ，一1 ) 寻找一个超平面 + b = 0 将其正确分开，这样的超平面往往不止一个，其中与两类样本点间隔m a r g i n 最大的分类超平面会获得最佳的推广能力：即最优分类超平面，如图2 - 3 。最优超平面仅由离它最近的样本点所决定，而与其它样本无关，这些样本点即所谓支持向量，这也正是支持向量机名称的由来【2 1 1 。而对于非线性问题，支持向量机采用特征映射方法，通过引入核函数k ，使得k ，x j ) = j 西( 动，实现非线性变化后的线性分类f 6 】，如图2 一：4 所示。图2 - 3 线性支持向量机f i 9 2 - 3l i n e a rs u p p o r tv e c t o rm a c h i n e2 2 3 支持向量机的一般原理图2 - 4 非线性支持向量机f i 9 2 - 4n o n l i n e a rs u p p o r tv e c t o rm a c h i n e假设存在二类训练样本集【2 3 】：d = 舡l ，y 1 ) ，( x l ，删，x 锹以，y p 1 ，叫( 2 - 7 )在线性可分得情况下存在一个超平面： + b = 0( 2 8 )将此样本集最优分类：如果训练样本可以无误差地被划分，每一类数据与超平面距离最近的向量与超平面之间的距离最大，此超平面称为最优超平面。其中，0 3 是超平面的法线方向。求解最优超平面 + b = 0 ，即对于给定的训练样本，找到权值c o 和偏移b 的最优值，使下式最小化：口( ) = 1 2l | i f -( 2 - 9 )同时满足约束条件：y f 【 + b 1 ，f = 1 ，z( 2 - 1 0 )可以看出这是一个二次规划问题，采用拉格朗日乘子法求解，引入拉格朗日乘子伍i1 4中国石油大学( 华东) 硕士学位论文o ，i = 1 ，求解下列函数：，三( 国，b ，口) = 圭i l 国1 1 2 一口， 少，【 + 6 】一1 i s l这里l 的极值点为鞍点，可取三对c o 和b 最小值6 0 - - - - 0 9 ，b = b ，a = 0 【，经过线性变换原问题转换为对偶形式，在约束条件：，y ，= 0 , 0 吼c 待1 ，( 2 - 1 1 )以及对a 的最大值( 2 1 2 )求解如下的极大化：liim a x w ( a ) = z t t , j 一号口f 口，y f y k = e r a - 号a7 q 口( 2 - 1 3 )f 毒1j 掌1暑1得到最优超平面：埘国。= 嘶乃i l l( 2 - 1 4 )b = 一号 x rx s为任意支持向量( 2 - 1 5 )从( 2 1 4 ) 式可以看出，0 【i = 0 的样本对于分类不起任何作用，只有0 【j 0 的样本对+ 起作用，从而决定分类结果，这样的样本即为支持向量。相应的分类器为：( z ) = s g n ( 舶+ ) = s g n ( a t y f k 柏+ ( 2 1 6 )，1 1根据删的符号来确定测试样本x 的归属，当刷= + 1 时，则样本x 属于当前判别的类别，当刷= 一1 时，则样本x 不属于当前判别的类别。在线性可分的情况下，支持向量机的内积核函数k = 铝，x 产。对非线性问题，不同的内积核函数将形成不同的算法，本文中使用的核函数是径向基核函数：k = e x p 一学2 3 支持向量机的训练算法( 2 1 7 )由上文可知，训练一个s v m $ 目当于求解一个凸二次规划( q u a d r a t i cp r o g r a m m i n g ，简称o p ) 问题 2 4 】：第二章相关关键技术，fm a xr v ( a ) = 口，一号a , q ( i ，j ) a ，i = 1i = l歹= l，旺y ，口，= 0 , 0 口，c ，i = 1 ，zi = 1( 2 - 1 8 )其中q ( f ，歹) = y i y k ，q 为z z 矩阵，k 是核函数。由于矩阵q 非负正，因此该问题是一个凸最优化问题，k k t 条件1 是其最优点应满足的充要条件，即所有的训练样本都应