博士论文-高性能文本分类算法研究.pdf

中国科学院计算技术研究所 博士学位论文 高性能文本分类算法研究 申请学位级别：博士 专业：计算机系统结构 摘要 因特网上的文本信息的爆炸式增长给文本分类的精度与速度提出了新的标准与挑 战。这就要求文本分类在提高精度的同时，还要进一步提升训练与分类速度。为了面对 时代的挑战，作者从特征选择与学习算法两个角度展开了深入的研究，取得了一系列突 破性进展。 作者从基于分辨矩阵的粗糙集属性约简中受到启发，提出了一系列基于粗集理论的 文本特征选择算法，即d b i 、d b 2 、l d b 。实验结果表明，d b 2 与l d b 极为稳定，达 到了与信息增益相当的精度；当特征数较少时，d b 2 与l d b 的精度要明显高于信息增 益。同时，在时间上也具有相当的优势，d b 2 与l d b 的时间代价与文档频次、互信息、 c h i 统计大体相当，但明显低于信息增益。 “没有免费的午餐定理”表明：任何一种模式分类算法都不存在“与生俱来”的优 越性。换句话说，所有分类器都存在一定程度上的“分类器偏差”。原因很简单，因为所 有分类器都建立在某种假设( 模型) 之上。通常，这个偏差会导致训练集与测试集错误率 增大。很自然地，作者就考虑采用训练集错分样本来在线修正分类器模型。这便是拉推 策略的基本思想。作者将拉推策略应用到三个基本的分类器，即中心法、贝叶斯、最近 邻，于是得到三个修正的分类器，即r c c 、r n b 、r k n n 。其中r c c 的性能最为卓越。 实验结果表明算法r c c 取得了逼近s v m 的分类精度，但运行时间需求却与问题规模成 线性关系，因此实际运行时间要远远低于s v m 。 但是，拉推策略只是降低了经验误差，还没有有效地降低推广误差。作者的一个非 常直接的想法就是，不但要求训练样本与正确类别的相似度大于所有与其它类别的相似 度，而且要至少存在一个间隔，即近似m a r g i n 。算法的具体做法就是，不但对误分样本 要修正相应类代表，而且对m a r g i n 较小的样本也要修正相应类代表。实验结果表明该算 法既能降低训练集误差，又能在一定程度上降低推广误差。并且，分类质量要比拉推策 略高出1 个百分点。 考虑到层次化分类的实用性与有效性。作者将拉推策略推广到层次化分类。作者给 出了两种将拉推策略推广到层次模型的方法。其一是选取整棵树进行拉推修正。其二是 选取每个非叶子节点进行拉推修正。实验结果表明，层次拉推策略的分类质量与非层次 拉推策略基本相当，但运行时间上具有明显的优越性。 概念索引采用类中心作为压缩空间的坐标。但是，简单地采用类中心来代表一个类 别，往往受到类中样本分布情况的影响。因此，为了提高类中心的表达能力，作者借助 于拉推策略来修正类中心。然后再把修正的类中心作为压缩空间的坐标。实验结果表明， 修正的概念索引在精度上要明显优于普通的概念索引。同时，修正的概念索引在与s v m 分类器的兼容性方面表现得更为出色。 高性能文本分类算法研究：摘要 概念索引使用中一t l , 法的类代表( 类中心) 来作为“概念”。于是，作者把“概念”进行 推广。也就是说，不仅仅可以使用类中心来作为“概念”，还可以使用其它类代表，如 w i n n o w 的权向量、贝叶斯的类概率与词概率、k n n 的类代表、s v m 的支持向量等等， 来作为“概念”。作者把采用推广的“概念”来进行压缩的方法统称为“分类器索引”。 实验结果表明分类器索引表现出了非常稳定的性能。 前面所提到的分类器修正都是采用在线方式，也可以认为这是一种局部修正算法。 为了克服这类算法的随机性，作者试图从全局的角度来考虑分类器修正。也就是说每次 不是考虑一个错分样本( 或m a r g i n 错分样本) ，而是同时考虑所有错分样本( 包括m a r g i n 错分样本) 。于是对所有错分样本建立一个全局的目标函数。然后采用经典的优化理论来 修正分类器。实验结果表明该算法取得了与s v m 相当的分类精度，但实际运行时间要 远远低于s v m 。 关键词：特征选择；特征提取；文本分类；文本挖掘；机器学习；信息检索 r e s e a r c ho nh i g h - p e r f o r m a n c et e x tc a t e g o r i z a t i o n s o n g b ot a n ( c o m p u t e r a r c h i t e c t u r e ) d i r e c t e db yj u ng ua n dx u e q ic b e n g 1 1 1 er a p i dg r o w t ho ft e x ti n f o r m a t i o no ft h ei n t e r n e tb r i n g sf o r w a r dn e ws t a n d a r d sa n d c h a l l e n g e sf o rt e x tc l a s s i f i c a t i o nw i t hr e s p e c tt oa c c u r a c ya n ds p e e d s ot h et r e n dr e q u e s t su s n o to n l yt ob o o s tt h ea c c u r a c yb u ta l s ot oa c c e l e r a t et h es p e e d i no r d e rt oc o n f r o n tt h e c h a l l e n g e ，t h ea u t h o rc o n d u c t sa l le x t e n s i v er e s e a r c ho nt h ep e r s p e c t i v e so ff e a t u r es e l e c t i o n a n dl e a r n i n ga l g o r i t h m s ，a n da c h i e v e ss i g n i f i c a n tp r o g r e s s t h ea u t h o rg a i n si n s i g h t sf r o ma t t r i b u t er e d u c t i o nb a s e do nd i s c e r n a b i l i t ym a t r i xa n d p r o p o s e sa f e w r o u g h - s e tb a s e dt e x tf e a t u r es e l e c t i o na l g o r i t h m s ，i e ，d b i ，d b 2a n dl d b n e e x p e r i m e n t a lr e s u l t si n d i c a t et h a td b 2a n dl d by i e l dh i g ha c c u r a c y , w h i c hi sn e a r l yt h es a m e a si n f o r m a t i o ng a i n ；w h e nt h ef e a t u r en u m b e ri ss m a l l ，d b 2a n dl d bc a nb e a ti n f o r m a t i o n g a i ni na c c u r a c y m e a n w h i l e ，t h et i m er e q u i r e m e n to f d b 2a n dl d bi sa b o u tt h es a m ea st h a t o f d o c u m e n tf r e q u e n c y , m u t u a li n f o r m a t i o no rc h is t a t i s t i c s ，b u to b v i o u s l ys m a l l e rt h a nt h a t o f i n f o r m a t i o ng a i n n of r e el u n c ht h e o r e m i n d i c a t e s ：a n yp a t t e r nc l a s s i f i c a t i o na l g o r i t h mc a n n o th o l dt h e s u p e r i o r i t yi n i t sb l o o d i no t h e rw o r d s ，a l lp a t t e r nc l a s s i f i c a t i o na l g o r i t h m ss u f f e rf r o m c l a s s i f i e rb i a s ”t os o m ee x t e n t t h er e a s o ni st h a ta l lc l a s s i f i e r sa l eb a s e do ns o m ek i n do f h y p o t h e s i s ( m o d e l ) g e n e r a l l ys p e a k i n g t h i ss o - c a l l e db i a sw i l lr e s u l ti ni n c r e a s eo f t r a i n i n g - s e t a n dt e s t - s e te l l o rr a t e v e r yn a t u r a l l y , t h ea u t h o ra d o p t sm i s e l a s s i f i e de x a m p l e st or e v i s et h e c l a s s i f i e rm o d e lo n l i n e 1 1 l i si st h eb a s i ci d e ao f d r a g p u s h i n gs t r a t e g y t 1 l ea u t h o ra p p l i e s t h i ss t r a t e g yt ot h r e eb a s ec l a s s i f i e r s ，i e ，c e n t r o i dc l a s s i f e r , n a i v eb a y e sc l a s s i f i e r , n e a r e s t n e i g h b o rc l a s s i f i e r , a n do b t a i n st h r e er e f i n e dc l a s s i f i e r , i e ，r c c ，r n b ，r k n n a m o n gt h e t h r e er e f i n e dc l a s s i f i e r sr c cp e r f o r m st h eb e s t e x p e r i m e n t a lr e s u l t si n d i c a t et h a tr c c d e l i v e r sh i 曲p r e c i s i o nt h a ta p p r o a c h e ss t a t e - o f - t h e - a r ts v m a n dt h er u n n i n gt i m eo fr c c s c a l e sl i n e a r l yw i t ht h es i z eo f t r a i n i n g s e t , a n ds oi sf a rl o w e rt h a nt h a to f s v m h o w e v e r , d r a g p u s h i n gs t r a t e g yh a s j u s tr e d u c e dt h ee m p i r i c a le r r o r , b u th a sn o tr e d u c e dt h e g e n e r a l i z e de r r o r v e r yd i r e c t l y , t h ea u t h o rn o to n l yd e m a n d st h a tt h es i m i l a r i t y ( s i m l ) o f e a c h t r a i n i n ge x a m p l et oi t si r u ec l a s si sb i g g e rt h a nt h es i m i l a r i t y ( s i m 2 ) t oa n yo t h e rc l a s s e s , b u t a l s or e q u i r e st h a tt h e r ee x i s t sa “m a r g i n a tl e a s tb e t w e e ns i m la n ds i m 2 t h ep r o p o s e d a l g o r i t h mt a k e sa d v a n t a g eo fn o to n l yt h em i s c l a s s i f i e de x a m p l e sb u ta l s ot h es m a l l - m a r g i n e x a m p l e s t or e f i n et h ec l a s s i f i e rm o d e l 1 1 1 ee x p e r i m e n t a lr e s u l t si n d i c a t et h i sa l g o r i t h mc a nn o t 1 1 1 商性能文本分类算法研究：a b s t r a c t o n l yr e d u c et h et r a i n i n g - s e te r r o rr a t eb u ta l s od e c r e a s et h eg e n e r a l i z e de r r o rr a t e t os o m e d e g r e e f u r t h e r m o r e ，t h ep r o p o s e da l g o r i t h m b e a t sd r a g p u s h i n gs t r a t e g y b y1 w i t h r e s p e c t i v et oa c c u r a c y i nv i e wo f t h ep r a c t i c a b i l i t ya n de f f i c i e n c yo f h i e r a r c h i c a lc a t e g o r i z a t i o n , t h ea u t h o ra p p l i e s d r a g p u s h i n gs t r a t e g y t oh i e r a r c h i c a l c a t e g o r i z a t i o n t w om e t h o d st oi m p l e m e n tt h e h i e r a r c h i c a ld r a g p u s h i n gs t r a t e g ya r ep r e s e n t e db yt h ea u t h o r t h ef i r s tm e t h o di st oa p p l yt h e d r a u s h i n gs t r a t e g yt o t h ew h o l et r e e ( t r a i n i n gs e t ) ；t h es e c o n dm e t h o di st o a p p l yt h e d r a g p u s h i n gs t r a t e g yt oe a c hn o d e ( ap a r to ft r a i n i n gs e t ) t h ee x p e r i m e n t a lr e s u l t si n d i c a t e t h a th i e r a r c h i c a ld r a g p u s h i n gs t r a t e g y y i e l d st h es a m ep e r f o 衄a n c ea sf l a t d r a g p u s h i n g s t r a t e g y , b u tg a i n so b v i o u ss u p e r i o r i t yo v e rf l a td r a g p u s h i n gs t r a t e g yi nr u n n i n gt i m e c o n c e p ti n d e xt a k e st h ec e n t r o i do f c l a s sa st h ec o o r d i n a t eo f r e d u c e ds p a c e h o w e v e r , t h e r e p r e s e n t a t i v ea b i l i t yo f c e n t r o i do f t e ns u f f e r sf r o mt h ed i s t r i b u t i o no f t r a i n i n ge x a m p l e s a sa r e s u l t , i no r d e rt oe n h a n c et h er e p r e s e n t a t i v ea b i l i t yo fc e n t r o i d s ，t h ea u t h o rr e s o r t st ot h e d r a g p u s h i n gs t r a t e g yt or e f i n ec e n t r o i d s , a n dt h e nt a k e st h er e f i n e dc e n t r o i d sa sc o o r d i n a t e so f r e d u c e ds p a c e t h ee x p e r i m e n t a lr e s u l ts h o w s ，r e f i n e dc o n c e p ti n d e xi so b v i o u s l ys u p e r i o rt o c o n c e p ti n d e xa st op r e c i s i o n m e a n w h i l e ，r e f i n e dc o n c e p ti n d e xb e h a v e sm o r ec o m p a t i b l y w i t hs v mt h a nc o n c e p ti n d e x c o n c e p ti n d e xt a k e sc l a s sr e p r e s e n t a t i v e s ( c e n t r o i d s ) o f c e n t r o i dc l a s s i f i e ra s “ c o n c e p t s ia s ar e s u l t , t h ea u t h o rg e n e r a l i z e st h es o - c a l l e d “c o n c e p t s t h a ti st os a y , t h ea u t h o rn o to n l y m a k e su s eo f c l a s sr e p r e s e n t a t i v e so fc e n t r o i dc l a s s i f i e r , b u ta l s oe m p l o y sc l a s sr e p r e s e n t a t i v e s o fo t h e rc l a s s i f i e r s ，s u c ha sw i n n o wc l a s s i f i e r , n a i v eb a y e s ，a n dn e a r e s tn e i g h b o r , a s c o n c e p t s ”t h ea u t h o rc a l l st h eg e n e r a l i z e dc o n c e p ti n d e xa sc l a s s i f i e ri n d e x t h e e x p e r i m e n t a lr e s u l t si n d i c a t et h a tc l a s s i f i e ri n d e xp e r f o r m sv e r yr o b u s t l ya n de f f i c i e n t l y a l la b o v ec l a s s i f i e rr e f i n e m e n ta p p r o a c h e sa d o p to n l i n em o d i f i c a t i o n a n dt h e yc a nb e t h o u g h ta sak i n do fl o c a lr e f i n e m e n ta l g o r i t h m i no r d e rt oo v e r c o m et h er a n d o m n e s so f t h i s k i n do f a l g o r i t h m , t h ea u t h o ra t t e m p t st or e f i n ec l a s s i f i e rf r o mt h ew h o l ep e r s p e c t i v e t h a ti st o s a y , h ed o e s n te m p l o yo n em i s c l a s s i f i e de x a m p l e ( o rs m a l l m a r 西ne x a m p l e ) t or e f i n e c l a s s i f i e r , b u tt a k e sa d v a n t a g eo fa l lm i s c l a s s i f i e de x a m p l e s ( o rs m a l l m a r g i ne x a m p l e s ) t o r e f i n ec l a s s i f i e r t h e nh eb u i l d sa g l o b a lo b j e c t i v ef u n c t i o na n da d o p t so p t i m i z a t i o nt h e o r e m t o r e f i n ec l a s s i f i e r t h ee x p e r i m e n t a lr e s u l t si n d i c a t e t h a tp r o p o s e da l g o r i t h md e l i v e r sh i g h p r e c i s i o nt h a ti sc o m p a r a b l et os t a t e - o f - t h e a r ts v ma n dr u n sm u c hf a s t e rt h a ns v m k e y w o r d s ：f e a t u r es e l e c t i o n ；f e a t u r ea b s t r a c t i o n ；t e x tc l a s s i f i c a t i o n ；t e x tm i n i n g ；m a c h i n e l e a r n i n g ；i n f o r m a t i o nr e t r i e v a l i v 图2 1 多层感知机示意图 图目录 图3 1 七种特征选择算法对中心法的m a e r o f l 影响3 9 图3 2 七种特征选择算法对最近邻的m a c r o f l 影响3 9 图3 3 七种特征选择算法对w m n o w 的m a c r o f l 影响4 0 图3 4 七种特征选择算法对贝叶斯的m a c r o f l 影响4 0 图3 5 七种特征选择算法对s v m r o r c h 的m a c r o f l 影响4 0 图4 1 圆形与椭圆形分布对中心法的影响4 2 图4 2 样本不均衡性对最近邻分类器的影响4 2 图4 3 类别( a 、b 、c ) 的二进制编码。 图4 4 分类树示意图 图4 5 ( a ) 拉推策略示意图 图4 5 ( b ) 修正后的中心示意图 图4 5 ( e ) 含三个类的数据分布示意图 图4 5 ( d ) 修正后的三个中心示意图 图4 6 八种分类算法的微平均f l 曲线。5 5 图4 7r k n n 与k n n 的微平均f l 随邻居k 的变化曲线5 5 图4 8r c c 、r n b 、r k n n 随m a x l t e r a t i o n 的变化曲线5 6 图4 9r c c 、r n b 、r k n n 随p u s h w e i g h t 的变化曲线。 图4 1 0r c c 、r n b 、r k n n 随d r a g w e i g h t 的变化曲线 图5 1 错误率与m a r g i n 错误率下降曲线 图5 2 层次结构示意图。 图7 1 有序风险最小化示意图 图7 2 线性可分情况下的最优分类面 5 7 i x 盯 钙 卯 钉 钉 铝 高性能文本分类算法研究：图目录 图7 3 支持向量机示意图 图7 4 四个语料集上的微平均f 1 曲线 图7 5 训练误差与m a r g i n 随迭代步数的变化曲线 图7 6 分类质量随迭代步数的变化曲线 图7 7 分类质量随w e i g h t 的变化曲线 8 5 9 0 图7 8 分类质量随l e a m r a t e 的变化曲线 图7 9 分类质量随m i n m a r g i n 的变化曲线 x 9 2 9 3 表2 1 邻接表 表3 1 决镱表示例 表目录 表3 2 决策表3 1 的分辨矩阵 表3 3 采用行格式的分辨矩阵 表3 4 采用连续值的决策表 表3 5 连续属性值的行格式分辨矩阵 表3 6 七种特征选择算法的运行时间比较 表4 1 八种分类算法的最好微平均f 1 比较 表4 2 八种分类算法的最好宏平均f l 比较 表4 3 八种分类算法的训练时间比较 表4 4 八种分类算法的分类时间比较5 4 表5 1 三个语料集上的最好宏平均f l 比较6 1 表5 2 三个语料集上的最好微平均f l 比较。6 l 表5 3 训练时间比较 表5 4 分类时间比较6 2 表5 5n e w s g r o u p h i e r 的层次结构 6 5 表5 6t a n c o r p h i e r 的层次结构6 5 表5 7r c v l - v 2 h i e r 的层次结构 表5 8 分类器代码表 表5 9 九种分类算法在三个语料集上的微平均f 1 比较 表5 1 0 九种分类算法在三个语料集上的宏平均f l 比较。 表5 1 1 九种分类算法的训练时间比较 表5 1 2 九种分类算法的分类时间比较 6 6 6 7 6 8 6 8 6 9 6 9 岛性能文本分类算法研究：表目录 表6 1 微平均f l 比较 表6 2 宏平均f l 比较 表6 3 特征选择时间比较 表6 4 训练时间比较 表6 5 分类时间比较 7 3 7 3 表6 6s v m 在w e b k b - 4 上的支持向量数量的比较7 4 表6 7 中心法在五个语料上的微平均f l 比较7 7 表6 8 中心法在五个语料上的宏平均f 1 比较7 7 表6 9s v m t o r c h 在五个语料上的微平均f l 比较7 7 表6 1 0s v m t o r c h 在五个语料上的宏平均f 1 比较。7 8 表7 1 四个语料集上的最好微平均f l 比较9 0 表7 2 四个语料集上的最好宏平均f l 比较。9 0 表7 - 3 训练时间比较 表7 4 分类时间比较。 声明 ? 我声明本论文是我本人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢的地方外，本论文中不包含 基他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究所做 的任何贡献均已在论文中作了明确的说明并表示了谢意。 。 作者签名：玛地吼砸y 论文版权使用授权书 本人授权中国科学院计算技术研究所可以保留并向国家有关部门或机 构送交本论文的复印件和电子文档，允许本论文被查阅和借阅，可以将本 ， 论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 _ 扫描等复制手段保存、汇编本论文。 ( 保密论文在解密后适用本授权书。) j - 一 。作薯签名鹚柏鹂师繇带凌日期：加山川。 ， 1 1 研究背景 第一章引言 二十一世纪是一个信息爆炸的时代 全世界每年出版图书8 0 万种，期刊4 0 万种，其他文献信息资料4 0 0 万种；发表科 学论文大约5 0 0 万篇，平均每天1 4 0 0 0 篇左右，每3 5 秒就有l 篇论文发表，不到1 分钟 就有1 本新书问世，每小时出现近2 0 项技术发明，每天约有4 0 亿个信息单位的信息量 向全世界发送。德国学者哈根曾说，一个科学家即使目前夜以继日地工作，也只能阅读 有关他自己专业世界上全部出版物的5 。 加利福尼亚大学伯克利分校的一项研究结果表明 l y m a n 0 3 ，仅过去3 年中，全球新 生产出的信息量就翻了一番。据这所大学发布的新闻公报介绍，该校信息管理及系统学 院莱曼教授领导的小组在研究中对多种信息源进行了采样分析，结果发现，2 0 0 2 年中， 全球由纸张、胶片以及磁，光存储介质所记录的信息生产总量达到5 万亿兆字节，约等 于1 9 9 9 年全球信息产量的两倍。换句话说，在1 9 9 9 年到2 0 0 2 年这3 年问，世界范围内 信息生产量以平均每年3 0 左右的速度递增。 因特网上的信息量也呈现出爆炸式的增长态势，1 9 9 8 年年初，因特网仅有3 2 亿个 w e b 页面，1 9 9 9 年2 月该数字上升为8 亿个。到2 0 0 0 年7 月已经发展为2 l 亿个，且仍 在以每天7 0 0 万个页面、每8 个月就翻一番的速度增长着。截止到2 0 0 4 年1 2 月，g o o g l e 宣称已经索引的网页数量已经超过8 0 亿。即使如此，仍有专家指出，因特网还尚未到达 它的快速增长期。 在信息数据保持高速增长的同时，我们的吸收能力却并没有随之增强。因而，我们 一方面感觉自己淹没在信息的海洋里，但另一方面又发现得不到最急需的信息。这就是 我们经常所说的“信息发达，知识贫乏”。这种局面促使我们迫切需要一种高效而快速的 工具来帮助组织与管理这些海量信息。其中一个直接而成功的范例就是根据信息的主题 对信息进行归门别类。 鉴于因特网上的大部分信息都以文本的形式存在。因此，文本信息的分类就显得更 加迫切、更加与人们的工作与生活密切相关。同时，爆炸式增长的文本信息给文本分类 的精度与速度提出了新的标准与挑战。这要求文本分类在提高精度的同时，还要进一步 提升训练与分类速度。这就是高性能文本分类算法的基本要求。 中国科学院博士学位论文高性能文本分类算法研究 1 2 研究意义 1 2 1 信息组织 对文本进行组织可以提高用户查找的效率。比如目前图书馆的归类体系，就能够避 免读者进行遍历式查找。再如当今的门户网站如新浪、搜狐、雅虎等都把网页按照内容 进行层次归类，这样就能让读者们很快浏览到所需要的信息。很显然，文档组织属于典 型的多类文本分类问题。 然而，目前大多数文档归类工作都由人工完成，甚至就连新浪、搜狐、雅虎等大部 分归类都由人工完成。这很显然必将耗费极大的人力物力。若能够采用计算机自动文本 分类技术来辅助文档归类，这必将大大地提高分类的效率。 1 2 2 信息过滤 随着信息获取方便性的提高，人们对获取网络上更为相关的信息的需求也在不断增 长。于是，人们迫切需要一种智能的信息过滤技术，该技术能够根据用户的需要，对源 源不断到来的文本进行动态的分类、筛选。从而保留有用信息，屏蔽无关信息。从文本 分类的角度来说，它属于两类文本分类问题，它将所有文本区分为“相关文本”与“无 关文本”。 信息过滤能够主动地获取用户特定的信息需求，进而使用这些信息需求组成过滤条 件，对信息资源进行过滤，就能把符合条件的信息抽取出来进行服务。因此，信息过滤 具有个性化与主动化这两个显著特点。个性化的实质是针对性，即对不同的用户采取不 同的服务策略，提供不同的服务内容；主动服务的实质是主动性，即不需用户做什么， 系统自动按照用户的需求来提供相应的服务个性化主动服务将使用户付出尽可能小的 努力，获得尽可能好的服务。 传统的获取信息的技术中用户是主动方，因此可以称之为“拉”( p u l l ) 与之相反的 另一种方式则称为“推”( p u s h ) ，由信息发布方主动地将信息推送给感兴趣的用户用 户的兴趣可以使用用户自己提交的p r o f i l e 。或者用户访问过的文本集合来描述。面对用 户形式各异的个性化信息需求，良好的信息过滤系统能够充分适应并及时捕捉到用户兴 趣的迁移，始终提供最能满足用户需求的信息。此外，通过适当的引导用户参与到过滤 过程中或者分析用户对待过滤结果的网络行为等技术实现动态反馈，根据这些反馈动态 调整用户兴趣的表示以及信息筛选的准则，从而实现更加高效的自适应式信息过滤。 1 2 。3 邮件分类 电子邮件作为最广泛和成功的i n t e r n e t 服务已经成为人们日常生活中不可缺少的组 成部分。但在给人们带来巨大方便的同时，也日益显示出其负面影响，那就是我们每天 收到的邮件中有很大一部分是那种“不请自来”的所谓“垃圾”邮件，它们或者是推销 第一章引言 广告，或者是一些有害的不良信息，甚至还有病毒。这些垃圾邮件不仅对网络安全形成 威胁，而且还造成了各方面资金上的巨大浪费。2 0 0 2 年由于垃圾邮件造成的损失大约在 9 0 亿至1 0 0 亿美金，2 0 0 3 年这个数据是成倍增加。 2 0 0 4 年7 月，中国互联网络信息中心( c m 仉c ) 发布的第十四次中国互联网发展 状况统计报告显示垃圾邮件在数量上是正常邮件的两倍。对垃圾邮件进行“围剿”已 经刻不容缓。 目前邮件分类可以看作通常的文本分类问题，它可以分为两种模式。其一是两类模 式，即按照垃圾与非垃圾来分类；另一种是多类模式，比如工作、会议、垃圾等。 1 2 4 话题跟踪 话题识别与跟踪的基本思想源于1 9 9 6 年，当时美国国防高级研究计划署( d a r p a ) 根据自己的需求，提出要开发一种新技术，能在没有人工干预的情况下自动判断新闻数 据流的主题。随后，来自d a r p a 、卡内基梅隆大学、d r a g o n 系统公司以及麻萨诸塞大 学的研究者开始定义话题识别与跟踪( t o p i cd e t e c t i o ra n dt r a c k i n g ，t d t ) 研究的内容， 并开发用于解决问题的初步技术。从文本挖掘的角度上来说，话题识别类似于文本聚类； 而话题跟踪类似于多类文本分类。 话题识别与跟踪，作为一项旨在帮助人们应对信息过载问题的研究，以新闻专线 ( n e w s w i r e ) 、广播、电视等媒体信息流为处理对象，将语言形式的信息流分割为不同的 新闻报道( n e w ss t o r y ) ，监控对新话题的报道，并将涉及某个话题的报道组织起来以某种 方式呈现给用户。它的研究目标是要实现按话题查找、组织和利用来自多种新闻媒体的 多语言信息。这类新技术是现实中急需的，比如：自动监控各种信息源( 如广播、电视等) ， 并从中识别出各种突发事件、新事件以及关于已知事件的新信息，这可广泛用于信息安 全、证券市场分析等领域。另外，还可以找出有关用户某一感兴趣话题的所有报道，研 究这一话题的发展历程等等。 1 2 5 新信息检测 文档信息检索技术能够在一定程度上满足文档的检索需求，但是往往会包含大量的 无关的、重复冗余的信息，同时信息粒度偏大。而且用户需要提炼自己的需求，以适当 的关键词表达出来 为了进一步提高检索的性能，我们希望研发出一种新的检索技术，该技术能够检索 出粒度比文档更小的相关信息，并进一步排除冗余、陈旧的信息。这里的粒度与文档相 对应，我们一般称之为片断( p a s s a g e ) ，其中包括：段落( p a r a g r a p h ) 、句子集( s e n t e n c ec l u s t e r ) 和句子为了评价与计算的便利，我们一般采用句子作为这种信息检索的粒度，我们称 之为句子级新信息检测州o v e n yd e t e c t i o na ts e n t e n c el e v e l ) 。 句子级新信息检测内在地包含着两个主要内容：相关句子检索与新信息内容的检测 新信息内容的检测可以分为监督与非监督检测。监督环境下的新信息内容的检测可以看 中国科学院博士学位论文高性能文本分类算法研究 作简单的两类文本分类问题，文本在这里指的是句子。类别对应为新信息与旧信息。 1 3 研究历史 1 9 5 8 年，l u l m 提出了采用词频统计来提取摘要的思想 l u h n 5 8 。他采用词语的频率 与分布信息来估计每个词语的相对重要度。然后再估计每个句子的相对重要度。于是得 分高的句子就被抽取为摘要 6 0 年代，m a r o n 的工作把文本分类向前推进了一大步 m a r o n 6 1 。他开创性地采用了 贝叶斯公式来进行文本分类。他用一组标引词来代表一篇文档，然后统计每个标引词在 每个类别下的概率然后计算该组标引词同每个类别的后验概率。挑选后验概率最大的 类别作为该篇文档的类别。为了简化后验概率的计算，m a r o n 率先作出了特征独立性假 设与类别排它性假设。特征独立性假设就是后来被广泛采用的“贝叶斯假设”更值得一 提的是他采用了s h a n n o n 熵束选择最有分类能力的特征( 标引词) 。 从6 0 年代到8 0 年代，采用知识工程的文本自动方法一直处于领导地位 s e b 9 9 。这 一阶段的主要特点是采用人工的方式来构建分类器。因此不可避免地需要大量领域专家 和知识工程师的参与。这样就会带来两个方面的困难，首先会耗费大量的研发经费；同 时难以保证知识与规则的正确性与一致性。但是这段时期内也涌现了一批性能不错的分 类系统，如路透社使用的c o n s t r u e 系统 f u h r 9 1 1 。它能够自动地对路透社每天的成千上 万篇稿件进行分类。 9 0 年代以后，基于机器学习的自动文本分类方法逐步占据统治地位。因为基于机器 学习的自动文本分类的正确性完全可与人工专家相当，但分类速度却要远远高于人工专 家。同时，基于机器学习的自动文本分类无需领域专家与知识工程师的参与，而通常的 机器学习算法都具有良好的领域移植性。因此，基于机器学习的自动文本分类具有更低 的开发费用、更快的开发速度、更好的推广性能。 几乎所有重要的机器学习算法都被引入到文本领域中来。比如最小二乘拟和回归模 型 y a n 9 9 4 】、最近邻 m a s a n d 9 2 】、贝叶斯 l a n g l e y 9 2 】、决策树 l e w i s 9 4 】、神经网络 w i e n e r 9 5 、线性分类器- d a v i d 9 6 等等。其中回归模型与最近邻分类器的分类质量表现 较为出色 9 0 年代中期v a p n i k v a p n i k 9 5 提出了著名的支持向量机。支持向量机利用了结构风 险最小化的原则，对有限样本情况下的分类器设计具有很好的效果。它从两类线性可分 问题发展而来，它的目