（计算机应用技术专业论文）支持向量机文本分类的关键问题研究.pdf

支持向量机文本分类的关键问题研究 摘要 随着计算机网络、数据库、多媒体等技术的飞速发展和日益普及，因特网上的可用 信息以惊人的速度增加，仅g o o g l e 搜索引擎能索引到的网页就高达8 0 亿张以上。因特 网信息表现为文本、声频j 。图象和视频等，其中文本类信息占绝大多数。为了更好地处 理这些数量庞大、结构不确定的文本类信息，人们迫切需要一些高效的文本检索、查询 和过滤系统，而文本分类正是实现这些系统所需的一项关键技术。 文本分类是指一个把自然语言的文本按其内容归入一个或多个预先定义好的类别 的过程。由于网上信息数量巨大而且存在形式多样，因此传统的由专家进行手工分类的 方法已无法满足现阶段应用的需要。自动文本分类是在给定的分类体系下，由特定的算 法根据文本的内容确定与之相关联的类别。自动文本分类是人工智能技术和信息获取技 术相结合的研究领域，是进行基于文本内容的自动信息处理的核心技术。 支持向量机是在上世纪末发展起来的一种基于结构风险最小化准则的分类学习机 模型。它通过构造并求解目标函数来获得两类样本数据之间的决策超平面，以保证最小 的分类错误率。从实际分类效果来看，支持向量机在解决小样本、非线性及高维的模式 识别问题时是目前己知的分类器中效果最好的，而这些问题恰是文本分类问题所面临的 困难。因此，支持向量机和文本分类问题有着良好的结合点。 虽然支持向量机的训练算法本身就可以克服特征词向量维数过高的问题，但针对文 本样本的特征提取步骤仍是不可或缺的，这是因为当大量特征词与分类无关时，只会使 支持向量机“过分适应于”训练样本而降低推广性能。此外，传统的基于词频统计的特 征提取方法也无法体现词与词之间的相互联系。针对这一问题，本文的第二章将潜在语 义索引和粗糙集特征提取结合起来，提出了一种在潜在语义空间利用粗糙集进行特征提 取的方法，试验结果表明采用新方法提取特征可以明显改善支持向量机的推广性能。 在分类问题广泛应用的允许训练误差的高斯核函数的支持向量机中，核参数孑和折 衷参数c 对于支持向量机的分类性能有着至关重要的影响。模型选择，即如何选择恰当 的训练参数，一直是支持向量机研究的一个重要课题。本文的第三章对这一问题进行了 分析，并提出了判断参数选择恰当与否的简化评价指标，并在此基础上提出了一种两步 骤的选择恰当参数的方法。第三章的试验表明，简化计算方法可以快速而准确地计算推 广误差评价指标，参数选择算法可以搜索到最佳的训练参数。 传统支持向量机最大的困难在于当训练样本数量较大时，支持向量机的训练时间较 长。这是因为采用分解法时，训练复杂度与样本数量的平方成正比。如何降低支持向量 机的训练复杂度直都是一个棘手的问题，本文的第四章根据预选取支持向量的思路对 摘要 上述问题进行了分析，将粗糙集的概念引入了支持向量的预选分析过程中。第四章提出 的新算法选取两类样本的上近似集的交集作为支持向量的候选集，并对两类样本上近似 集交集的一致性进行了证明。试验表明，训练样本的上近似集的交集可以代替全部训练 集进行训练，从而提高训练速度。 支持向量机的基本模型是针对两类样本集提出的，在处理多类样本集的分类问题 时，目前效果最好的方法是训练一系列针对两类样本的子分类器。尽管这种方法可以获 得令人满意的分类效果，但其训练时间比较长。我们认为，在多数情况下，并不是所有 的子分类器都值得训练，部分子分类器是冗余的。本文的第五章对训练子分类器的必要 性进行了分析，并提出一种采用主动学习策略的多类别支持向量机，新算法按子分类器 的重要程度逐渐训练子分类器。实验证明，这一算法可以在几乎不降低分类性能的基础 上，显著减少子分类器的个数。 直推式支持向量机是直推式学习理论和支持向量机的结合，它是目前分类效果最好 的支持向量机。但它的分类效果极其依赖于事先指定的正样本数量虬的选择。当与 实际情况相差较大时，直推式支持向量机的分类性能甚至还不如普通的支持向量机。本 文的第六章着重讨论了直推式支持向量机对d 的值过分敏感的问题，提出了逐个判定 准则来调整测试集松弛变量的类别标签，从而使的值在训练过程中可变。实验结果 表明，改进后的方法使直推式支持向量机不再对事先指定的他的选择敏感，能稳定地 获得较好的分类效果。 网页是带有特定结构信息并说明链接关系的文本，与纯文本相比，网页的信息量更 大、样本与样本之间的联系更紧密，但也比纯文本分类问题更加难以处理，要考虑更多 因素。本文的第七章在分析了模糊直推式支持向量机在网页处理方面不足的基础上，从 超链接分析的过程和利用网页重要性信息这两方面对其进行了改进。基于网页数据的试 验表明，新算法有更强的适应性和更高的准确性。 综上所述，本文的主要创新包括如下几方面的内容： 1 根据文本分类领域的特征，改进了留一错误的评价指标和模型选择算法，显著 提高了模型选择的效率； 2 提出了基于粗糙集的支持向量预选方法，缩短了训练的时间： 3 针对多类别分类问题，提出了采用主动学习策略的多类别支持向量机，可以在 几乎不降低分类性能的条件下，减少子分类器的个数； 4 提出了更恰当的直推式支持向量机松弛变量标签调整准则，从而能稳定地获得 较好的分类效果。 此外，本论文还在特征词的提取方法和网页分类等方面进行了研究和改进，使特征提取 和网页分类的性能都有所提高。 关键词：文本分类，网页分类，支持向量机，特征提取，模型选择，粗糙集，潜在语义 分析，主动学习，直推式学习 r e s e a r c h i n go nt h ek e y p r o b l e m so ft e x tc i a s s i f i c a t i o nw “ht h e s u p p o i tv b c t o rm a c h i n e s a b s t r a c t w i t ht h er a p i dd e v e l o p m e n ta 1 1 dm c r e a s m gp o p u l a r 泣a t i o no ft h et e c h n i q u e so fn e t w o r k ， d a t a b a s ea n dm u l t i m e d i a ，t h ea v a i l a b l ei n f o r m a t i o no nt h ei n t e m e tm c r e a s e sa te g r e g i o u s s p e e d j u s tu s 吨t h es e a r c he n g i l l eo fg o o g j e ，w ec a n 血dm o r et h a n8b i l l i o n so fw e b p a g e s t h ei i l f o r m a t i o no nt h ei m e h l e ti 1 1 c l u d e st h et e x c s ，a u d i o s ，p i c t u r e sa n dv i d e o s n gt h e s e ， t h et e i i l f o r m a t i o ni s i i lt h em a j o r i t y i no r d e rt op r o c e s st h el a r g e rn u m b e ro ft e x t i n f o r m a t i o nmd i 虢r e n ts t m c t u r e s ，h u m a nn e e d s o l ee 伍ci e n t i 1 1 d e x m g ，q u e r y m ga n d f d t e 血gs y s t e m s t e ) ( tc l a s s 伍c a t i o ni st h ek e yt e c h n o l o g yt oi i l l p l e m e n tt h e s es y s t e i l l s t e x tc l a s s i a t i o ni sap r o c e s s ，w h j c hg r o u p st h en a t l l r a ll a n g u a g et e 赋si m oo n eo rm o r e p r e d e 抽e dt h e m ec l a s s e sa c c o r d i l l gt ot h e i rc o n t e n t s t h et r a d i t i o n a lm e t h o d s ，w h i c hc l a s s i 匆 t h et e ) ( t sw i t ht h ee x p e r t sm a n u a l l y ，a r en o tc o m p e t e mn o w a d a y s ，d u et ot h eq u a n t n ya j l d d i v e r s i t vo fw e bi 1 1 f o m a t i o n a u t o m 砒i ct e ) ( tc l a s s i f i c a t i o nm e a i l sl a b e l i l l gt h ec l a s sl a b e lf o ra t e x tu s 协gs o m ea l g o r i t l u l l s i ti sac o m b 血a t i v er e s e a r c hf i e l do fa r t i f i c i a lm e l l i g e n c ea n d i n 南m 诅t i o nr e t r i e v a la n di ti st h ec o r et e c h n j q u eo ft h ec o n t e n t b a s e da u t o m a t i ci i l 内r m a t i o n p r o c e s s i n g d e v e l o d e d 丘o mt h e1 a s td e c a d eo ft h e2 0 “c e n t u r y ，t h es u p p o r tv e c t o rl m c h i l l e ( s v m ) i s ac l a s s i f i e r _ w h j c hi sb a s e do nt h es t m c t u r a l 融s km i l l i m 娩a t i o np r i l l c i p l e t h es v m c o n s t r u c t sa j l ds o l v e sa 1 1o b j e c t i v em n c t i o nt o 丘n da no p t 曲a lh y p e 印1 a n e ，w l i c hs e p a r a t e st h e p o s i t i v ea n dn e g a t i v es a m p l e sw i t ht h ek g e s tr n a r g m ，s ot h a tt h e 商h i i i l u mt r a 曲h ge 仃0 rc a n b eo b t a i 】1 e d a ss h o 、n b ym a n ye x p e r i m e n t s ，t h ep e r f o r m a l l c eo fs v m si sb e t t e rt h a na n y k n o w nl e a r 咖gm a c h j i l e s ，w h e nt h et e s ts a n 叩l e sa r en o l l l i l l e a ra 1 1 dh j g h - d i i l l e n s i o n s o ，t h e s v mi ss u i t a b l ef o rt e ) ( tc l a s s 蚯c a t i o n a l t h o u 幽t h et r a i 幽ga l g o r i t h mc a no v e r c o m et h ep r o b l e mo fk g hd h e n s i o n a l i t y of d a t a ，凫a t u r es e l e c t i o ni sa ne s s e m i a ls t e po f t e x tc i a s s i f i c a t i o n t 1 1 i si sb e c a u s et h es v m w i l l o v e r 6 tt h et r a 砬n gd a t aa n dt h eg e n e r a l 泣a t i o na b i l i t yw i l lb ed e c r e a s e ，w h e nt h e r ee x i t st o o m a n yf e a t u r e si r r e l a t i v et oc l a s s i f i c a t i o n f u n h e r m o r e ，t h et r a d i t i o n a l 仔e q u e n c y - b a s e df 宅a t u r e s e l e c t i o nm e t h o d si g n o r et h es e m a n t i cr e l a t i o l l s k po ft h ew o r d s t bc o p ew i t ht h e s ep r o b l e i l l s ， w ep r o p o s eah y b r i di n e t h o di ns e c t i o n2 ，w m c hi 1 1 t e g r a t e sl a t e n ts e m a n t i c1 1 1 d e x m ga n d a b s t r a c t r o u g hs e t st h e o r ) ，u s i l l gt h er e d u c tc o n c e p to ft h er o u 曲s e t s ，t h eh y b r i dm e t h o dc a ns e l e c t t h e a h l r e smt h es e m 枷i c c o n c e p ts p a c e t h ee x p e r i i l l e m a ir e s u l t s s h o wt h a tt h e p e r f 0 咖a n c eo ft h eh y b r i dm e t h o di sr e r n a r k a b l yh i 曲e rt h a l lt h et r a d i t i o n a lr n e t h o d sw h e n s v mi su s e da st h ec l a s s 洫r t h es o r m a r g i i ls v m sw i t hg a u s s i a nk e m e l sa r em o s tc o m m o nu s e di 1 1t e x t c l a s s m c a t i o n i nt 上l i st ) ，p eo fs v m s ，t h ep a r a m e t e r s a n dca 虢c tt h ep e r f o m a n c eo ft h e c l a s s i 丘c a t i o ns i g l l i f i c 枷l y t h em o d e ls e l e c t i o n ，w h i e l lm e a n ss e l e c t 血gt h ea p p r o 砸a t e p a u r a m e t e r sf o rt h es v m ，i sv e r yi m p o r t a j l ti s s u et i l l n ow i ns e c t i o n3 ，w ed i s c u s st m s p r o b l e ma n dp r o p o s es o 1 es i m p l i f i e de s t i i l l a t o r st oj u d g ew h e t h e rt h ep a r a n t e r sa r ep r o p e r b a s e do nt h es i i i l p l i f i e de s t i i l l a t o r s ，ap a r 锄e t e r - s e l e c t 血gm e t h o di sa l s o p r e s e n t e di i lt 场s s e c t i o n t h ee x p e r i m e n t a l r e s u l t ss h o wt h a tt h es i i n p l i f l e de s t i l l l a t o r sa r ee 伍c i e n ta 1 1 da c c u r a t e ； t h ep a r a n l e t e r - s e l e c t i l l gm e t h 6 dc a j l 曲dt h ep r o p e rp a r a h l e t e r s t h eb i g g e s td i 伍c u l t yo ft r a j i 血gt h es v mi st 1 1 a tt h et r a j i 血gt h ei 1 1 c r e a s e sr a p i d l yw i t h t h ei 工l c r e m e n to ft h es i z eo f 乜拙gd a t 如f o rt h et 抽1 ec o m p l e x “yi sp r o p o r t i o n a t et ot h e s q u a r eo ft h en 吼b e ro ft h e 仃a m 血gd a t a ，w h e nd e c o h l p o s em e t h o di su s e dt os o l v et h es v m p r o b l e m i ns e c t i o n4 ，w ep r o p o s ear - o u g hs e t s - b a s e ds u p p o r tv e c t o r sp r e s e l e c t m gm e t h o d f o rr e d u c i l l gt h es i z eo ft h et r a i l 血gd a t a t h en e wm e t h o du t i l i z e st h ec o n c e p to f b o u l l d a r y r e g i o no fr o u g hs e t st h e o 巧t oa m l y z et r 蛐gs a m p l e sa n ds e l e c t st h es a n 叩l e st h a ta r ei i lt h e b o u l l d a r yr e g i o na st h et r a i l l 试gs u b s e t e x p e r i r l l e n t a lr e s u l t ss h o wt h a tt h ed e wm e t h o dc a l l r e d u c et h es 讫eo ft r a i l l i n gd a t ar e n w k a b l y 埘t h o u td e c r e a s i l l gt h ea c c u r a c ys e r i o u s 工y t bd e a lw i t ht h em u l t i c a t e g o r yc l a s s i f i c a t i o np r o b l e m ，t h ec o 姗o nm e t h o di st o 仃a i na s e r i e so fb i l l a r ys u b - c l a s s i f i e r sa 1 1 dc o m b i l l et h e i ro p i l l i o no nc l a s s i n c a t i o n a l t h o u g ht m s m e t h o di sa v a i l a b l e ，i ts u 船r s 丘o mt h el o n gt r a i l l i n gt i i l l e w 爸c o n s i d e rn o ta j ls u b c l a s s i 丘e r s o f “1 一a - 1 ”a r ew o r t ht r a 证i i l g ；s o m eo ft h e ma r er e d u l l d a m i ns e c t i o n5 ，w ea n a l y z et h e e s s e m i a l i t yo ft h es u b - c l a s s i f i e r sa n dp r o p o s ea 1 1a c t i 记l e 踟血g b a s e dm u l t i s v mm e t h o d ， w m c ht r a i l lt h en e c e s s a r ) ，s u b c 1 2 l s s i f i e r s a c c o r d i l l gt ot h e i r 呻o n a n c e t h ee x p e r i m e n t a l r e s u l t sp r o v et h a tt h en e wm e t h o dc a nr e d u c et h en u m b e ro fs u b c l a s s i f i e r sw “h o u td e c r e a s i l l g t h ep e r f o m l a n c e t h et r a l l s d u c t i v es u p p o r tv e c t o rm a c 血e ( t s v m ) i st h et r a n s d u c t i v ei i 位r e n c eo ft h e s u p p o r tv e c t o rr 1 1 a c h i i l e ，w h o s ep e r f - o m m c ei sb e t t e rt h a l lt h er e g u l a rs v mg e n e r a l l y h o w e v e r ，t h ec l a s s i f i c a t i o np e r f o n m n c eo ft s v md e p e n d so nt h en u m b e ro fp o s i t i v e s a r n p l e s ，w 1 1 i c hi sa p p o 缸e d b e f o r et r a j i 血g w h e nt h ea p p o 谳e d 坼i s m c hd i 虢r e m 舶m t h er e a lv a l u e ，t h ep e r 南m 瑚1 c eo ft s v mi se v e nw o r s et h a l lt h a to ft h er e g u 协s v m i n s e c t i o n6 ，w ed i s c u s st 1 1 i sp r o b l e ma n dp r o p o s ea1 1 e wt r a n s d u c t i v et r a i l l 曲ga l g o r i t h mb y s u b s t i t u t m gt b ep a i r - w i s ee x c h a n g i l l gc r i t e r i o nw i t ht h ei 1 1 d i v i d u a l l yj u d g i l l ga i l dc h m g m g c r i t e r i o n e x d e r i m e n t a lr e s u h ss h o wt h a tt h en e wm e t h o dr e l e a s e st h er e s t r i c t i o no ft h e a p p o 缸i n e mo f a i l dt h e 血p r o v e dt s v m w i uo b t a i l lt h eb e s tp e r f o 删es t e a d 丑y t h ew e bp a g e sa r et e x t sw i t hs p e c i a ls t r u c t u r a li i l f o r r n a t i o l l ，w h i c hs p e c i f i e st h el i i 出血g r e l a t i o n s h i p c o m p a r e dw i t ht h e p u r e t e x t s ，t h ew e bp a g e sc a n 了m o r e 删b r l a t i o na n d t h e r e l a t i o n s h i pa m o n gt h e mi sm o r ee x p l i c i t h o w e v e r ，t h ec l a s s m c a t i o no fw e b p a g e si s r n o r e d 蠲c u i tt h a nm e “p l l r e t e 斌s i ns e c t i o n7 ，e 锄a l y z et h ed e 丘c i e n c i e so ft h ef t s v m ，a n d i m p r o v et h ef t s v mo nt 、oa s p e c t s t h ef i r s to n e i st h eh y p e r l i i 墩a 1 1 a l y z m ga n dt h es e c o n d o n ei st h ew e i g h tm f o r m a t i o nu t i l i z i l l g e x p e r 曲e n t a l r e s u l t so nw 曲k bs h o wt h a t t h e i m p r o v e df t s v mp e r f o r m s b e t t e rt h a nt h ef t s v m ，w h e na c c u r a c ya n da d a p t a b i l i t y i s c o m p a r e d 心h a sm e n t i o n e da b o v e ，t h em a i nc o t 啪u t j o n so f t h et h e s i sa r es 1 皿m a r i z e da sf o o w s 1 s h p l i 母t h ee s t 油a t o r so fg e n e r a l i z a t i o ne r r o ra c c o r d i l l gt ot h ec h a r a c t e r i s t i co f t e x t c l a s s i f i c a t i o n 甜l di 工1 1 d r o v et h em o d e ls e i e c t i o nm e t h o d ，w b j c hc a ni i n 耻o v e t h e e 伍c i e n c y ； 2 a r o u g hs e t s b a s e ds u p p o r tv e c t o rp r e s e k c t i o nm e t h o di sp r o p o s e dt or e c h l c et h e t r 蛐gt i n l e ； 3 am u l t i s v mr n e t h o dw i t ha c t i v el e a n 】m gs t r a t e g yi sp r o p o s e df o rm u h i c a t e g o r y c l a s s i f i c a t i o np r o b l e m ，c a nr e d u c et h en u m b e ro fs u b c l a s s i 氏r sw i t h o u td e c r e a s i l l g t h ep e d o r m a n c e ； 4 al a b e l e x c h a n g 协gc r i t e r i o nf o rt s v mi sp r o p o s e d ；w h i c hc a no b t a mt h eb e s t p e r f o m 觚c es t e a d i l y ； b e s i d e s ，w ea l s or e s e a r c hf e a t u r es e l e c t i o np r o b l e ma n dw e bp a g ec l a s s i f i c a t i o np r o b l e m a 1 1 di m p r o v et h er n e t h o d so ft h e mmt 1 1 i sp a p e r ，s ot h a t ，t h e i rp e r f o r m a n c ec a nb eb e t t e rt h a n t h e 亿t t n e r k e yw o r d s ：t e x cc l a s s m c a t i o n ，w e bp a g e s e l e c t i o 皿r n o d e ls e l e c t i o n ，r o u g hs e t s ， t r a l l s m l c t i v el e a i n m g c l a s s i f i c a t i o 玛s u p p o r tv e c t o rn l a c h i l l e ，f e a m r e l a t e n ts e m a m i c1 1 1 d e x 访g ， a c t i v e 1 e a r n i i l g ， v 上海交通大学 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 日期：洒年l ( 月c 8 日 上海交通大学 学位论文版权使用授权书 本学位沦文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权上海交通大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 保密口，在年解密后适用本授权书。 本学位论文属于 不保密口。 ( 请在以上方框内打“、，”) 学位硷文作者签名：函眸 指导教师签名：岳j r f i j | ：舾圭f 周 g 日l 三l 期：诃年f f 月囝日 上海交通大学博士学位论文 1 1 文本分类的意义 第一章绪论 本论文所讨论的“文本”，是指一般的电子化文本或其中的某个片段，它可能是媒 体新闻、科技报告、网页或电子邮件等。随着计算机网络、数据库、多媒体等技术的飞 速发展和日益普及，因特网上的可用信息以惊人的速度增加，截止到2 0 0 5 年6 月，仅 g o o g l e 搜索引擎能索引的网页就高达8 ，0 5 8 ，0 4 4 ，6 5 l 张。因特网信息的表现形式包括文 本、声频、图象和视频等等，据统计，在全部多媒体信息中，文本类信息占了8 0 以上 【2j 。为了更好地处理这些数量庞大、结构不确定的文本类信息，人们迫切需要一些高效 的文本检索、查询和过滤系统，而文本分类正是实现这些系统所需的一项关键技术。 文本分类( t e x tc l a s s i a t i o 皿t c ) 是指一种把自然语言的文本按其内容划分到一个 或多个预先定义好的类别中的过程。由于网上信息数量巨大而且存在形式多样，因此传 统的由专家进行手工分类( 如y a h o o ! 【3j ) 的方法已远远不能满足当今科技发展的实际需 要，研发快速而高效的自动文本分类系统已迫在眉睫。 自动文本分类是在给定的分类体系下，由计算机根据文本的内容来确定文本所属的 类别。它是以半结构化或非结构化的文本数据为研究对象，通过统计分析、机器学习、 模式识别等方法将文本归入最恰当类别的一个非平凡( 有一定程度的智能性、自动性) 的过程，它是基于文本内容的自动信息处理的核心技术。 国内外许多学者将自动文本分类应用在信息检索、信息抽取( i r ) 、信息过滤( i f ) 等 领域，并取得了较好的效果。但传统的自动文本分类方法面临着一些难以克服的技术困 难，主要表现在难以处理维数灾难、分类精度难以令人满意和推广性能不佳等方面。 支持向量机( s u p p o r tv e c t o rm a c h m ，s v m ) 【4 j 】是在二十世纪九十年代发展起来的 一种基于结构风险最小化准则的分类学习机模型。它通过构造并求解目标函数来获得两 类样本数据之间的决策超平面，以保证最小的分类错误率。这一新兴的学习机模型已经 在手写数字识别、三维目标识别、人脸识别、文本图像分类、时间序列预测、主成份分 析等实际问题的应用中，表现出了良好的分类或识别能力。从实际分类效果来看，支持 向量机在解决小样本、非线性及高维的模式识别问题中是目前己知的分类器中效果最好 的，而这些问题恰是文本分类问题所面临的困难。因此，支持向量机和文本分类问题有 着良好的结合点。如今，支持向量机的研究及其应用已引起越来越多人的兴趣和关注， 成为机器学习理论和技术领域中的一个新热点。 第一章绪论 本课题以非结构化和半结构化的英语文本作为研究对象，以支持向量机( s v m ) 为 基本学习机模型，结合主动学习、直推式学习、粗糙集和潜在语义索引等前沿技术对文 本分类的若干关键问题进行研究。我们研究的目标是希望通过改进算法，使支持向量机 的文本分类性能得到进一步的提高，包括使分类结果更准确、模型选择更便利以及训练 时间更短等。 1 2 文本的表示 根据不同的应用需要，文本的表示方法也有很多种：包括语义网表示、框架表示、 向量空间模型( v e c t o rs p a c em o d e l ，v s m ) 表示等。q u i l i a n 于1 9 6 9 年提出了用语义网表 示知识的方法【6 j 。它以概念和概念之间的关系表示自然语言的逻辑结构，目前已成为自 然语言理解，尤其是句法分析和语义分析的主要文本表示方法( 7 1 。框架方法用一组预定 义的“属性值”对来表示文本，其中属性可以是单独的，也可以是嵌套的。它特别适 合于表示一些格式或内容相对固定的文本，如g r i s h i l l a n 曾用时间，地点，爆炸装置，伤 亡人数等属性来描述南美恐怖事件的新闻 引。 向量空间模型最初由s a h o n 提出 9 1 ，它在文本分类和信息提取等领域有着广泛的应 用。根据“贝叶斯假设”，组成文本的字或词在确定文本类别归属的贡献上互相独立， 这样就可以使用文本中出现的字或词的集合来代替原文。虽然代替的代价是损失了部分 关于文本内容的信息，但它可使文本表示更简单化、处理更形式化。 向量空间模型的基本思想是以权向量( ，) 来表示文本d ，其中 暇为第i 个特征项的权重。矾，分别对应特征项，l ，垃，如，“。通 常，英文文本可选择单词的词干和n g r 锄作为特征项。n g r a m 是指在文本中连续的玎个字 母组合【i ，用n g r 锄技术可以实现语言无关的特征项选取。 无论采用单词还是n g r 锄作为文本的特征项，都必须先对文本进行预处理。预处理 过程首先剔除标点符号、数字、停用词和低频词。停用词是指文本中出现频率极高，但 包含信息却很少的词，这些词对分类几乎不起作用。如冠词t h e 、a ，连词a n d 、o r 等等 1 。低频词是指某些在整个文本集合中出现的次数都很少的词，显然，它们也不适合作 为文本的特征项。由于我们研究的对象是英文文本，而英语词汇在语句中有特殊的变形 形式，如名词的数、格和动词的时态等，若选择单词作为特征项，还必须将变形的单词 恢复其基本形式【1 ，因此预处理还必须包括对单词的取词干处理。 最初的研究将特征词向量完全以0 ，1 形式表示，如果文本中出现了特征词，则文本 向量中与该特征词对应的分量为l ，否则为0 。由于这种方法无法体现词在文本中的重要 程度，现已被更精确的词频代替，词频分为绝对词频和相对词频。绝对词频以词在文本 中出现的次数表示文本；它在一定程度上反映了单词的重要程度。但对于长度相差较大 的文本，两者的绝对词频缺乏可比性。相对词频是绝对词频归一化处理后的指标，通常 上海交通大学博士学位论文 用如式( 卜1 ) 所示的萨动r 公式 1 2 】来计算。 川) ：三丝丝些墅丝兰坚) 州妙( f ，d ) l o g ( 门，+ o 0 1 ) j 2 其中，( f ，为词庄文本d 中的权重，而矿( ，动为词疮文本d 中的词频：l o g ( m 门。+ o 0 1 ) 称作动项，根据s h 锄o n 信息论原理，如果个词在所有文本中出现的频率越高， 那么它所包含的信息熵就越小；因此，脚颂的作用是减少那些在很多篇文本中都出现的 词的权重【l3 l 。式( 1 1 ) 中的分母为归一化因子，归一化后的( f ，动介于0 和1 之间。为训 练文本的总数，2 。为训练文本集中出现f 的文本数。 经过上述步骤，文本转换为向量空间中的向量。向量之间的相似程度和差异程度是 判断两文本关系的重要依据。根据向量空间的定义，文本的相似程度可以由向量间的夹 角等指标度量，夹角越小，则文本之间的相似程度越大。文本的差异程度可以用向量之 间距离来表达，距离越大，则文本之间的差异程度越大。常用的相似程度度量有： 余弦夹角： c d s ( d i ，d j ) = d i c e 系数： d i c p ( d f ，d ，) = j a c c a r d 系数： 七= i 厮 七= l o 5 ( 孵+ 吆) 七= l七= i j a c c a r d u i ，dj 、) = x w k 瞬+ 七= l 其中，盔和尉旨两个文本特征向量， 长度。常用的差异程度度量有： 欧氏( e u c l i d ) 距离： 帜一d 川2 = ( ( 一) 2 ) 2 明氏( m 敞o v s l ( i ) 距离： 帜一d 川9 = ( ( 一) 9 ) 帅 ( 1 2 ) ( 1 3 ) ( 1 - 4 ) 一 七= l 彬和啄是凶和巧向量的各分量。胛是特征向量的 ( 1 5 ) ( 1 - 6 ) 第一章绪论 曼氏( m a n h a t t a n ) 距离： 帜一d 川：= ( 一) 么( 一) 7 ( 1 - 7 ) 其中，西和西指两个文本特征向量，孵女和是西和面向量的各分量。在明氏距离中， p 是大于0 的整数，当p = 1 时，为海明距离：p = 2 时，为欧氏距离。在曼氏距离中，4 是 正定阵，( ) 代表转置。 超文本在纯文本的基础上增加了一些结构化信息，如超链接结构、锚链文本( 超链 接上的词句) 等，因而它是种半结构化数据。在多数情况下，超链接结构表达了超文 本之间的某种联系，因此超链接信息对超文本分类有一定的帮助。在超文本分类中，超 链接信息应该与超文本中的纯文本信息结合起来加以利用，以便从数据集中获得更多的 分类信息。 1 3 文本分类的常用方法 从数学角度理解，文本分类可以看作是一个映射的过程，它将未标明类别的文本映 射到预先定义的类别中。用数学公式表示如下： 厂( 4 ) = b( 1 8 ) 式( 1 8 ) 中厂( ) 代表分类函数，其中4 为待分类的文本集合，b 为类别集合。支持向 量机是一种典型的监督学习过程。基于监督学习的分类系统通常分两步骤完成文本分类 过程。首先，分类系统通过学习不同类的若干样本的数据信息，发现类别规律并建立的 判别公式或规则，这一步称作“学习”或“训练”。当经过训练的分类系统遇到新文本 时，就可以根据先前总结的判别公式或规则来确定文本所属的类别，这一步称作“测试”。 基于无监督学习的分类系统，通过增大类别之间差异性，同时增大类别内部相似性 以实现对无训练样本的数据的分类。聚类是典型的无监督学习过程。由于没有已知类别 的训练集，所以它的训练时间和训练结果的不确定性都比监督的学习过程大得多。在本 论文中，我们不讨论这种方法。 基于半监督学习的分类系统是上述两种方法的折衷，它利用数量有限“训练”样本 总结出一定的规律，并根据数量众多的“测试”样本所携带的分类信息