（信号与信息处理专业论文）文本分类和聚类中若干问题的研究.pdf

文本分类和聚类中若干问题的研究 摘要 文本分类和聚类是文本信息处理领域的一个重要分支，其目标就 是研究如何更有效地组织和管理文本信息，并快速、准确、全面地从 中找到、分流、定位和形成用户所需要的信息。文本分类和聚类作为 获取和组织大量文本数据的关键技术，可以在很大程度上解决信息杂 乱和信息爆炸的问题。而且作为信息过滤、信息检索、搜索引擎、文 本数据库、数字化图书馆等领域的技术基础，文本分类和聚类有着广 阔的应用前景。随着信息化时代的到来，文本分类和聚类的重要性日 趋显著，其研究工作已经不仅仅是科学家的兴趣所在，世界上许多国 家和地区的政府及工业界都十分关注并积极投身于文本分类和聚类 领域的研究。 本文针对文本分类和聚类中亟需解决的海量应用、分类精度以及 理解深度等问题，开展了以下创新性研究： 第一，探讨了基于统计模型的文本分类。主要研究了传统的统计 模型方法在文本分类领域中的应用。首先，研究了基于贝叶斯方法的 文本分类技术。在此基础上，利用加权的方法提出了一种改进的贝叶 斯算法。其次，研究了如何利用无标签样本进行学习的问题。通过采 用转导推理，整合了无标签样本和有标签样本的学习。最后，探讨了 字符级统计方法在文本分类中的应用。此外，通过把垃圾邮件过滤和 短信分类任务的解决贯穿始终，将这一部分的研究内容在其上逐一实 现。实验结果表明，本文的方法不仅易于工程实现，能够联合无标签 样本学习，而且可以较好地在分类速度和精度之间进行折衷，以达到 快速准确处理海量文本信息的能力。 第二，探讨了基于分类器集成的文本分类。主要研究了基于简单 多数投票策略的分类器集成问题。首先，给出了一个分类器错误的分 解式( e + v 分解) ，在理论证明的基础上，提出了一个能够指示分类 器集成性能的指标i v i o 借由线性规划方法，分析了基于简单多数投票 策略的分类器集成性能的理论上下界。最后，探讨了可能达到集成性 能理论上界的两种途径：1 ) 选择性分类器集成；2 ) 基于i v i 指标优化 的分类器集成。此外，我们将这部分所研究的方法应用于垃圾邮件过 滤任务。实验结果表明，本文的方法能够很好地提高集成后文本分类 器的精度，具有良好的应用前景。 第三，探讨了基于非线性方法的文本聚类。我们期望能够将传统 的文本聚类处理提升到“理解”的层次。将文本聚类处理领域的研究， 从长期专注于“语法”层次的研究，演进到“语义”的层次。首先，通过 使用流形学习工具，研究了中文词汇在语义空间( 分类空间) 的分布 情况，这部分研究将为迸一步基于语义的特征选择工作打下良好的基 础。在此基础上，利用w b r d n e t 词典进行了短信聚类的研究。实验结 果表明，本文的方法能够更好地反映文本之间的内在联系。 关键词：文本分类和聚类统计模型分类器集成流形学习垃 圾邮件过滤短信处理 r e s e a r c ho nk e yp r o b l e m si nt e x t c l a s s i f i c a t i o na n dc l u s t e r i n g a b s t r a c t t b x tc l a s s i f i c a t i o na n dc l u s t e r i n gi so n eo ft h em o s tv a l u a b l e t e c h n o l o 百e si n “t b x ti n f o n l l a t i o np r o c e s s i n g a r e at h a ta r o u s e se x t e n s i v e s t u d yo ft h eo r g a n i z a t i o n ，m a n a g e m e n ta n dp r o c e s s i n go fl a r g ea m o u n to f t e x td a t a w h j c hl o c a t e sr e q u j r e di n f i o r n l a l i o ns w i r j y a c c u r a l e l ya n d c o m p r e h e r i s i v e l y t e 赳c l a s s i f i c a t i o na n dc l u s t e r i n g ，t h ek e yt e c h n o l o g yi n o 唱a r i i z i n ga i l dp r o c e s s i n gl a r g em o u n t o f t e x td a c 锄s o l v et h ep r o b l e m o fi n f o m l a t i o nd i s o r d e r 艄de x p l o s i o nt oag r e a te x t e m m o r e o v e r t c x t c l 嬲s i 6 c a t i o n 锄dc l u s t e r i n gw i l lb ew i d e l y 印p l i e d 勰m et c c l l l l i c a lb a s i s o f m f o r m a t i o nf i l t e r i n g ， i n f o n n a t i o nr e t r i e v a l ，s e a r c h e n g i n e ， t e x t d a t a b a s e 。锄dd i g i 协l i i b 姗r ya n ds oo n 厅t ht h ea d v e n to f t h ei n f o 姗a t i o n e r a ，t e x tc l a s s i f i c a t i o na n dc l u s t e r i n ga r cb e c o m i n gh i g h l i g h t i n g t h e y h a v eb e c o m en o to n l yt h et a s t e so fs c i e m i s t sb u ta l s ot l l ei n t e r e s t so f g o v e m m e m sa i l df o r c e s t h eg o v e m m e n 协a n di n d u s t r i a lc o m m u n i t i e so f m 锄yc o u n t r i e s r e 西o n sa ms ok e e no nt c x tc l a s s i f i c a t i o n 锄dc l u s t 耐n g t e c l l i l i q u e st h a tt h e yh a v ei i e s t e dag r e a td e a lo fm o n e yo nr e l e v a n t r e s e a r c h i nt h i sd i s s e r t a t i o i l t t l r e ep r o b l e m st ob ed e a l tw i ma f et h o r o u g h l y i n v e s t i g a t e d ，w h i c hi n c l u d e st h ed e v e i o p m e n to fp r o c e s s i n ga l g o r i t l l r n s f o rh u g e 锄o u n to ft e 斌d a t a ；i m p r o v i n gt h ep e r f b r n l a n c eo ft e x t c l 鹳s i f i c a t i o nt e c h n i q u e s ；p r o m o t i n gt h et r a d i t i 伽皿lt e x ti l l f 0 n a t i o n c j l l s t 甜n gt e c l 】l l i q u 豁t o i l d 蹦岫1 d i n g ”l e v e l n em a i nc o n t r i b u t i o n so f m i sm s s e r t a t i o na r es u m m a r i z e da sf 0 l l o w s ： f i r s n y w ed i s c u s s e dt h e 印p l i c a t i o n so fs t a t i s t i c a l 埘i o d e ii nt e x t c l a s s i 氏a t i o nf i e l d a tt l l eb e g i i l i l i n g ，w es t u d i e dt i l e a p p l i c a t i o n o f c o n v e m i o n a lb a y e s i 锄m e t h o di i lt c ) ( tc l a s s i f i c a t i o nf i e l d t h e n 觚 珊 i i l l p r o v e d 、v e i g h t e db a y e s i a nm e t h o dw 船p r o p o s e d a sf o l l o w i n g ，t l l e m e t l l o dt h a tc o m b i n e sl a b e l e d 锄du n l a b e l e dd a t au s i i l g 咖s c i u c t i v e i n f e 旧n c ei sd i s c 璐s e d a tl 勰t w ep m b e di l l t o t l l e 印p l i c a t i o no f c h l r a c t e r 1 e v e ls t a t i s t i c a lm e t t l o di i lh u 留et e x tc l a s s i f i c a t i o nf i e l d m o r e o v e r s o l u t i o n st o 砌o l l l i 舱s p 锄f i l t e r i n g 锄ds h o nm e s s a g e s c l 私s i f i c a t i o nt a s k sh a v eb e e ne x p l o r e dt h r o u 曲m i ss e c t i o n e x p e r i m e n t a l r e hp r o v e s 虹l a tm e s ee a s y 吨o u m e t h o d sc a nn o to n i yl e a m 丘o m l a b e l e d 锄du n l a b e l e dd a t a ，b u ta l s oa c h i e v et m d e - o f rb e “张e np r o c e s s i n g c u m c ya i l ds p d s e c o n d l y ，w ed i s c u s sm ea p p l i c a t i o n so fc l a s s i f i e 捧e n s e m b l ei nt e x t c l a s s i f i c a t i o nf i e l d i nt h ef i r s t p l a c e ， t h ee + v( e r r o r _ t r i a n c e ) d e c o n l p o s i t i o ni so u t i i n e d o nt h eb a s i so fr i g o r o u sp r o o fa b o u tt h i s m e o r y ai v li n d e xi sp r o p o s e dt l l a tc a nr e n e c tt i l ee i l s e m b l ep e r f o r m a n c e i na d d i t i o i l ，w ef o m l u l a t e dt h e m a j o r i 够v o t i n gp r o b l e m a sa i l o p t i m 妇i o np r o b l e mw “hi i n e a rc o n s t r a i n t s ，a n dt h e nt h et h e o r e t i c a l u p p e r a n dl o w e rb o u n d sf 0 r p e r f o 瑚a n c e o b t a i n e db yc o m b i n i n g c l a s s i f i e r st h r o u 曲m a j o r i t ) rv o t i n ga r ei l l u s n a t e d a tl a s t ，w ed i s c u s st w o p o s s i b l e 印p r o a c h e st or e a c ht i i et h e o r e t i c a lu p p e rb o u n db yc o m b i n i n g c l a s s i f i e 髂m r o u g hm a j o r i t yv o t i n g ：1 ) s e l e c t i v ee n s e m b l e ；2 ) e n s e m b l e b 髂e do nt i l eo p t i m i z a t i o no fi v i b e s i d 鹤，t h er e s u l t i n gt e c l l f l o l o g yh a s b e e ns u c c e s s m l l yi m p i e m e n t e di i lo u rs p 锄f i l t e r i n gs ys t i ：m a tl a s t ，w ei n v e s t i g a t e d l ea p p l i c a t i o 船o ft l l en l i n e a rm e n l o d si n t e ) ( ti l l f 0 肌a t i o nc l u s t a 曲gf i e l d w bd i s c u s s e dh o wt op r o m o t et h e 仃a d i t i o n a lt e 斌i i l f o n i l a t i o nc l u s 劬g t e c l l i l i q u e st 0 u 1 1 d e r s t a n d i n g l e v e l b y 懈啦m a i l i f o l d 锄i y s i s ，w e 研m 撕l ys t u d i e dm ed i s 胁u t i o no f c l l i n e s ew o r d si l lac o n t i n u o l l ss e m 锄t i cs p a c e ，砌c hi s 懈e 向lf o r 细岫e r s 岫o ff c a n l l es e l e c t i o nb 船e do ns e ma 1 1 _ t i cd i s 协c e t h e nw e i n v e s t i g 纳e ds h o r tm e s s a | g e sc l u s t i 。r i n gb a 靶do nw r o r d n 眈e x p e r i m e n t a l 鲫hp r o v e st t l a tm e s em e t l l o d sc a l ir e f l e c tt h ei l i c a l l a lm l a t i o no f t e x t s k e yw o i s ：t e x tc l 雒s i f i c a t i o n 弛dc l u s t e 由gs t a t i s t i c a lm o d e l c l 私s 湎e r 伽e m b l em a | l i f o l dl e 锄j n g s p 锄丘l t e 血g s h o r t m e s s a g e s 创新性声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： 盘弱蠢 口期： 盘2 ：4 ：边 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。 本学位论文不属于保密范围。适用本授权书。 本人签名： 导师签名： 缅盔日期：选2 ：乙q 日期：孕且l 北京邮电大学博士学位论文第一章绪论 1 1 引言 第一章绪论 国人一向激赏“以文载道，以文立人”的处世哲学。曹丕典论论文 ：“盖文 章，经国之大业，不朽之盛事。”孔子；“言之无文，行之不远”，“不知诗，无 以言”，诗可以兴，可以观，非唯心群，可以怨，迩之事父，远之事君，多识鸟 兽草木之名。”刘勰文心雕龙：“文之为德也大矣，与天地并生”。“心生而言 立，言立而文明”。左传襄公二十四年：“大上有立德，其次有立功，其次有 立言。”林林总总，都说明将信息以文本的形式流传下来，从古至今都是一件非 常重要的事情。世界上下五千年的丰富文化遗产，大部分都随着文字得以流传。 如今，随着i n t e “w t 的迅猛发展和日益普及，一方面使得人们可以更加方便快捷 地获取各种电子化的文本信息，但是另一方面，随之而来的纷繁复杂的文本信息 处理问题也就成为了大家重要的研究对象尤其是在当代，信息是极其重要的资 源，不能充分掌握它、利用它，无论是对个人还是对整个社会，都会造成巨大的 损失。因此，获取、处理和运用信息的手段至关重要可以这样说，文本信息自 动化处理能力的每一步提高，给我国的科学技术( 包括国家的信息化) 、文化教 育、经济建设、国家安全所带来的效益，将是无法用金钱的数额来衡量的。反之， 如果我们落后了，不管是落后于国际水平还是落后于现实需要，后果都是严重的。 随着信息时代的到来，电子化文本信息迅速膨胀，如何有效地组织和管理这 些信息，并快速、准确、全面地从中找到用户所需要的信息是当前文本信息处理 领域所面临的一大挑战。文本分类和聚类作为文本信息处理领域的一个重要分 支，其目标就是研究如何更有效地组织和管理文本信息，并快速、准确、全面地 从中找到、分流、定位和形成用户所需要的信息。文本分类和聚类作为处理和组 织大量文本数据的关键技术，可以在很大程度上解决信息杂乱和信息爆炸所带来 的问题，而且作为信息过滤、信息检索、搜索引擎、文本数据库、数字化图书馆 等领域的技术基础，文本分类和聚类有着广阔的应用前景。虽然文本分类和聚类 问题只是文本信息处理领域研究的一个方面，但也同时是至关重要的一个方面。 它的解决关系到电子化信息的普及和使用效率，当然也就关系到全国各行各业信 北京邮电大学博士学位论文 第一章绪论 息化的程度，各行各业现代化的水平。时至今日，文本分类和聚类技术的重要性 日趋显著，其研究工作已经不仅仅是科学家的兴趣所在，还受到了各国政府和军 队等权力部门的密切关注，世界上许多国家和地区的政府及工业界都十分关注并 积极投身于文本分类和聚类领域的研究，其进展不仅将促进科学和技术的进步， 还会对各国的国力产生一定的影响。 但是，文本分类和聚类所涉及理论和应用问题范围十分广泛，处理起来非常 复杂。而且随着信息时代日新月异的发展，研究中遇到的一些老问题还没有得到 解决时，新的问题又不断涌现，层出不穷。其真正解决可能需要更多的人，费很 长时间( 也许需要几代人) ，刻苦地研究，经过反复失败、反复探索，逐渐接近 完善。正如许嘉璐先生在中文信息处理若干重要问题一书的序一中文信息 处理的研究应该走向高潮中所展望的那样：“未来的路有多长，没有人能 说得出来，我们只知道科学技术是没有止境的，那么，中文信息处理技术的发展 也将是没有止境的祝中文信息处理早口出现突破性的进展”。 1 2 课题研究背景 现代文本信息处理领域的研究发轫于上世纪六十年代。上世纪六十年代，国 际文本信息处理领域的大师s a l 自呱q 【2 魄出向量空间模型( v s m ：v e c 衙s p e m o d e l ) 并成功应用于s m a r t 文本分类系统，成为现代意义上的文本信息处理 研究开始的重要标志。1 9 8 9 年，腮e 会刊砒姆册dd 眦，西曙船e 胁谚问 世，其目的是为研究者，开发者，管理者，策略制定者以及其他感兴趣的用户提 供知识和数据工程领域的最新的理论和实践进展其创刊号的第一篇文章中，在 国际上享有崇高声望的专家r 矗m 锄l r n l yc v 【3 l 就提出关注更有效地组织和管 理文本信息，并快速、准确、全面地从中找到、分流、定位和形成用户所需要的 信息的内容。模式识别领域的国际知名刊物“腰e e 开硼阳c 砌h f 删凡恤聊彳撇咖妇 绷d 脑a 曲办圮肺2 啦铲聊”自1 9 8 8 问世起，就不断关注文本信息处理领域的各种 问题，特别是文本分类和聚类的研究。一些著名的国际期刊包括c 吖 开册舅耐如圪，鲫蜘聊捌胁 缸棚”、饧删矿奶轫撕耐铆如删叠m ，、“m 可 谚l 豫a m e n c d ns o c i e 哆对i 咖m 删 0 ns c i e m 矿、“i e e e 裔傩s n o 凇伽印s t e 黼 朋a 珥册d o 忱朋p 咖矿等等，都非常关注文本信息处理领域的进展。 2 北京邮电大学博士学位论文第一章绪论 文本分类和聚类技术的深刻变革来自于自上个世纪八十年代以来席卷全球 的信息化浪潮。特别是近十年来，文本分类和聚类处理领域的研究取得了长足的 进步，其相关研究成果已经渗透到各个学科，在智能控 b i 、机器视觉、知识处理、 信息检索、信息过滤等领域取得了令人鼓舞的进展。有鉴于此，近年来。文本分 类与聚类技术领域相关研究不仅受到了科研工作者的高度重视，也得到了各类国 家计划、研究基金和企业项目的大力支持国家自然科学基金委员会、国防基金 委员会、国家8 6 3 计划、国家9 7 3 计划、攀登计划以及各省市的科研基金部门等都 对文本信息处理领域的研究给予了必要的资助1 4 】o 国际上，t r e c ( t e 峨i 逻t r i e v a l c o n f e r e n c e ，m s t 和美国国防部联合举办的年会和测试) 嘲、s l g 瓜( s p e c i a ji n t e r e s t g r o u po ni n f o 咖a t i o n 融r i “a i ，a c m 的年会) 1 6 j 、n t c i r ( n i i n a c s i st e x t c o l l e c t i o nf o ri rs y s t e 脚，n i i 主办的针对亚洲语种的测试) 【刀、t d t ( t o p i c d e t e c t i o na n dt r a c k i n g ，n i s t 主办的测试) 嘲、m u c ( m e s s a g eu n d e r s 切n d i n g c o n 岛r e i l c c ，d j 龇主办的测试) 唧、a c e ( a u t 0 瑚t i cc o n t e n te x 纰i c t i o n ，n i s t 主办的测试) 【1 0 1 等国际会议和评测活动十分活跃，吸引了全世界的注意，强有力 地推动了研究进展。 总结已有的研究成果，文本分类和聚类处理中的一些技术已经进入了实用阶 段。在文本表达方面，基于m 盯k o v 过程的n g 姗m 模型和s a i t o n 的向量空间模型提 供了对文本进行描述的有效数学模型。在文本特征选择方面，提出了词频倒文 档频度法( t f - i d f ：t e 珊f r e q u e n c y i i n r e r d o c 啪e n tf 陀q u e n c y ) 、信息增益 法( i g ：i 嘶) n n a l j o ng a i n ) 、c h i 统计量法、互信息法( m i ： m u t 憾li n f o 加a t i ) 等【i i i 专门的方法，同时，还将主成分分析、线性鉴别分析和奇异值分解的 方法应用于文本特征选择，衍生出了潜在语义索引旧( l s i ：l 栅ts e m a r n i ci n d e x ) 的重要概念。 在此基础上，在文本分类方面，贝叶斯分类器、支撑向量机( s v m ) 【1 4 】、自 组织映射( s o m ) 【1 5 j 、粗糙剿1 们、逝邻( k n n ) 【1 7 】【1 、决策树【1 叭、关联规则唧1 、 分类器集成伫1 1 以及向量相似度等模型得到了广泛应用。 在文本聚类方面，平面划分方法阱l 、层次凝聚方法【2 3 1 、基于s o m 的方法【堋、 基于密度的方法洲嘲、基于网格的方法脚1 1 2 刀、模糊聚类方法口。】1 2 9 1 也已经得到了 广泛的应用。 同时，以垃圾邮件过滤为代表的文本分类和聚类在特定领域的应用研究越来 北京邮电大学博士学位论文第一章绪论 越受到重视，2 0 0 5 年，t r e c 开始将垃圾邮件过滤系统作为技术评测对象【3 0 】，标 志着这项技术的代表性和重要性。目前。一些商用的垃圾邮件过滤器已经进入市 场，如d ea _ d 1 2 s p 锄，s p 吼b a y e s d 2 j s p 卸1 p b c p 3 1 等一些面向新型文本媒质 的文本分类和聚类技术，如短信分析【3 4 1 ，b l o g s ( 具有观点倾向性判断的) 检索 【3 5 】等也受到人们广泛的关注。 文本分类和聚类领域的研究风生水起，造就了许多互联网英雄，如y a h 0 0 的 杨致远，g 0 0 9 l e 的l 锄可p a g e 和s e r g e yb m ，b a i d u 的李彦宏等。 鉴于以上认识，在国家自然科学基金项目n o 6 0 4 7 5 0 0 7 、n o 6 0 6 7 5 0 0 l 、教育 部重点项目n o 0 2 0 ”、教育部跨世纪人才基金和国家信息安全2 4 2 项目资助下， 本文对文本分类和聚类中的若干问题进行了研究，提出了一些见解和方法，希望 对解决文本分类和聚类中的相关问题有所帮助。 1 3 文本分类和聚类技术概述 我们首先厘清几个概念： 文本：首先区分文本( t e x t ) 和文档( d o c u m e n t ) 的概念，我们认为文档是 一个较为广义的概念，其内涵涵盖各种文本组织形式，其外延包括文本文档、图 像文档、视频文档及其混合组织形式。而本文所研究的对象“文本”所指的 是文本文档( 自e x td o c u m e n t ) ，其内涵涵盖纯文本对象，其外延包括各种以纯文 本内容为主的文本组织形式，包括w | c b 网页、邮件讨论组、短信、b l o g 等。 文本分类：按照事先定义的类别来决定一篇文本的归属的过程被称为文本分 类。其类别可以通过概念进行定义，也可以通过标注的实例学习得到。 文本聚类：将文本对象的集合分组成为由类似的对象组成的多个类的过程被 称为文本聚类。这些对象与同一个簇中的对象彼此相似，与其它簇中的对象相异。 聚类一般是无监督学习过程 这样一来，文本分类和聚类技术就可以表述为针对文本文档研究根据给定类 别进行分类处理和根据文档内在联系进行聚类处理的技术 在文本分类方面，最初人们希望通过经验和专业知识对事物进行定性分析， 即由专业人员手工编写和维护分类规则来进行分类。这类系统的典型例子是 c o n s l l r i e 系统【3 6 1 。手工方法的缺点是构建自动分类器时必须要为领域专家获 4 北京邮电大学博士学位论文 第一章绪论 取的知识和知识工程师的知识表示之问架起桥梁。如果这种分类器被应用到完全 不同的领域，工作必须推倒重来 二十世纪九十年代以来，随着信息存储技术和通信技术的迅猛发展，大量的 文字信息开始以计算机可读的形式存在，而且其数量每天仍在急剧增加。在这种 情况下，基于机器学习的文本分类逐渐取代了基于知识工程的方法，成为文本分 类的主流技术。贝叶斯分类器、支撑向量机( s 田，自组织映射( s o m ) 、粗糙集、 k 近邻( 帅、决策树、关联规则、分类器集成以及向量相似度等模型得到了广 泛应用。这些方法大致可以分为三大类：基于统计模型的方法( 如贝叶斯分类器、 k n n 、向量相似度等) 、基于连接的方法( 如s o m ) 和基于规则的方法( 如决策 树、关联规则等) 。它们之间的主要区别在于规则获取方法。 典型的文本分类模型如图1 1 所示。文本分类模型由训练模块和分类模块构 成。在训练模块中，首先对训练文本进行预处理得到文本表示，然后利用文本表 示训练分类器，最后根据测试结果进行性能评测。在分类模块中，首先将测试文 本进行预处理得到文本表示，再经分类器分类，最后得到测试文本所属的类别。 即分类决策。 上司一一点 聋 嚣辇旷t ，n 一：澜 图卜l 典型的文本分类模型 文本分类己经被广泛地应用在很多地方，比如不同类型的文本分类任务( 诸 如专利、新闻、w e b 网页及讨论组f 3 7 1 的分类等) 、信息过滤( 诸如敏感信息过 滤、垃圾邮件，短信过滤【3 0 肄) 。 北京邮电大学博士学位论文 第- 章绪论 综合比较这些算法性能的差异是一件很不容易的事情，但是通过对相关文献 所得到的分类结果进行统计和比较，对于文本分类技术可以得到以下几点结论： 1 )基于传统的贝叶斯方法的文本分类算法，因其简单易行在文本分类 中得到了广泛的应用。但是贝叶斯方法相较其它算法，性能较差： 2 ) s v m 算法在现有的方法中表现出最好的性能，但是其算法复杂度限 制了其在大规模语料库中的应用； 3 ) k n n 、s 0 m 、粗糙集分类的性能比s v m 略差，但是k n n 的优点是其 分类模型相对简单； 4 )决策树、关联规则分类的性能相对较差，但是它们能够提供用户可 理解的、有用的分类知识，这也是其它算法的不足之处； 5 ) 分类器集成方法能够极大的提高文本分类算法的精度。 在文本聚类方面，最初，作为统计学的一个分支，基于距离的聚类分析己经 被广泛地研究了许多年。许多成功的方法，如k m e a i l s 【3 。j 、k m e d o i d s 【3 9 1 等，已经 被加入到许多统计分析软件包或系统中，例如s p l u s 、s p s s 、s a s 以及m a t l a b 。 随着信息化时代的到来，基于机器学习的文本聚类方法大行其道，包括平面划分 方法、层次凝聚方法、基于s o m 的方法、基于密度的方法、基于网格的方法、 模糊聚类方法也已经得到了广泛的应用。 图1 - 2 典型的文本聚类模型 6 北京邮电大学博士学位论文第一章绪论 典型的文本聚类模型如图1 2 所示。文本聚类中，首先对文本库中的文本进 行预处理得到文本表示，然后对文本表示利用各种聚类算法将其聚集成簇聚类 的指导原则是追求较高类内相似度和较低类间相似度 文本聚类己经被广泛地应用在在很多地方，如在信息检索系统中以提高信息 检索的效率、组织搜索引擎返回的结果、帮助用户测览超大规模的文本数据、生 成w e b 文本的分类层次树、帮助用户管理和组织个人e m a i l 、电子文档删h 1 4 2 l 等。 文本聚类同时又是一个非常难的问题，一方面是因为它没有任何预知信息， 对所要划分的类别信息也是未知的，因而难于处理。另一方面，聚类算法和所要 解决的问题密切相关。可以这么说，有多少种具体问题，相应地便会有多少种因 此而开发的聚类算法1 4 3 1 。因此很难对不同的聚类算法进行客观、公正、科学的评 价。但是在最近的文本聚类研究中，一个比较重要的趋势是。人们希望脱离原先 基于语法层次的相似性聚类，得到能够理解文本内容的聚类方法。基于概念的文 本聚类，以及最近基于语义、语用层次所做的研究l “】1 4 5 脚l m 都是这思想的体 现。 1 4 文本分类和聚类领域面对的挑战 现在既是文本分类和聚类技术最为蓬勃发展的时代，又是其面临巨大挑战的 时代： 1 ) 文本分类和聚类技术处理内容日趋复杂化和多元化。随着时代的发展， 文本分类和聚类技术发生了天翻地覆的变化。其“内涵”仍然涵盖有效地组织和管 理文本信息，并快速、准确、全面地从中找到、分流、定位和形成用户所需要的 信息等核心内容。但是其“外延”却极大的丰富，处理对象已经由简单的纯文本对 象，发展到包括w e b 网页、邮件讨论组、短信、即时通信、b b s 论坛等等，不 一而足。这使得从各式各样文本形式中抽取处理内容本身也成为了一门学问，即 信息抽取【4 ”( i e ：i n ：f o i 删n i 蚰咖6 ) ，受到人们的广泛关注。而且文本分 类和聚类处理的对象也不再局限于文本领域。还逐渐和语音分类及检索h 埘，图像 分类及检索【5 0 】【5 ”，机器视射视频分类及检索p 2 5 3 增技术结合在一起，如通过语 一文转换以及建立图像，视频的描述( p r o f i l e ) 将语音、图像，视频分类及检索问题 7 北京邮电大学博士学位论文第一+ 章绪论 转换为文本分类及检索问题。种种发展，均使得文本分类和聚类技术发生了质的 变化，提升到前所未有的水平。同时也使得研究中遇到的一些老问题还没有得到 解决时，新的问题又不断涌现，层出不穷。 2 ) 海量信息处理。信息大爆炸，一方面使得人们很容易获取巨量的信息， 使文本信息以前所未有的速度传播，发展。然而，事物总是有两面性的，另外一 方面，这也使得如何处理这些海量数据成为了摆在人们面前的难题。这里的处理 包含两个方面的含义： 第一，如何进行海量数据实时处理的问题。一般来说，现有的算法只是在中 小数据集上显示出优势，大都是因为速度瓶颈无法成功应用于海量数据挖掘。而 处理海量数据挖掘的算法一般来说精度都不高。如何达到速度和精度的折衷，需 要进行深入的研究。 第二，如何进行无标签样本学习的问题。信息化使得我们能够轻松获得大量 的信息( 无标注背景信息) ，但是这些信息只是原始语料，一般来说，只有经过 整理标注才能投入实际应用。而手工标注大量高质量的训练样本的工作是极端枯 燥和代价巨大的。因此如何整合有标签数据和无标签数据的学习，成为了一个现 实的问题。 3 ) 人性化，个性化处理。我们无论是对文本进行分类和聚类，还是进行其它 深层次的处理，其最终目的始终都要面对人的需求，因此人性化个性化处理是 大势所趋，不可避免侈4 】【5 5 1 。这里的人性化，个性化处理也包含两个方面的含义： 第一，如何开发增量式自适应更新的算法，跟踪捕获用户的需求。因为算法 的开发一般面对的是通用的情况，即针对最一般的情况进行处理。而实际中碰到 的总是具体的问题，如何使通用框架适合每个用户的需求，我们必须开发增量式 自适应更新的算法，通过不断学习，跟踪捕获用户的需求 第二，如何从更高的层次，即从“理解”的层次处理用户需求。具有理解并自 动处理文本信息能力的机器，才算是智能文本信息处理机器，也才可以替代人类 劳动者工作。这样，传统上人类劳动者依靠简单的“控制指令”来同机器合作的局 面就可以大为改观，从而可以做到人和机器之间的合理分工和默契合作。这对于 整个社会生产力和促进人类劳动者从自然力的束缚下获得越来越多的解放具有 伟大的意义。 4 ) 对更高处理精度的追求。对信息处理更高、更快、更强的追逐是人类永 l 北京邮电大学博士学位论文第一章绪论 恒的追求如何开发分类精度更高，更鲁棒，速度更快的文本和聚类技术，也是 我们作为文本信息处理领域研究者的永恒追求。 。 。 1 5 文本分类和聚类领域亟需解决的问题 现代文本分类和聚类领域面临巨大的挑战，而且随着研究的深入，其中的一 些深层次问题也逐渐暴露出来，其中的一些已成为本学科进一步发展的阻碍。但 是，从另一个方面来看，它们也揭示了文本分类和聚类领域下一步应该着重研究 的内容。 本文认为，目前亟需解决以下几个问题： 1 ) 设计出易于使用的工程化文本分类方法。文本分类工作缺少统一的理论 框架，经验性成分相当高。虽然针对具体问题，可以迅速给出一般处理方法，但 是如果要使得系统获得良好的性能，只能具体问题具体分析，通过大量费力耗时 的实验摸索，确定出适合的处理模型、算法以及参数设置，其应用效果极大依赖 于使用者的经验。即使采用同样的方法解决同样的问题，由于操作者不同，其结 果很可能大相径庭。在实际应用中，操作者往往是缺乏文本处理经验的普通工程 技术人员，如果没有易于使用的工程化文本分类处理方法，文本分类技术的应用 效果将很难得到保证 2 ) 开发适用于海量信息处理的文本分类算法。这包含两个方面的问题： 第一，设计性能和效率兼备的海量数据的实时处理算法； 第二，充分利用无标签样本进行学习。通过整合有标签数据和无标签数据的 学习，提升文本分类技术的应用性能 3 ) 提高文本分类技术的处理精度。一般来说，精度问题往往是文本分类处 理技术从理论走向实际的最大障碍。因此开发分类精度更高，更鲁棒，速度更快 的文本分类技术成为文本信息处理领域重要的研究目标。 4 ) 将传统的文本聚类提升到理解的层次。文本聚类是“文本信息处理”领域 的一个重要分支。文本信息处理的根本强标是使机器能够“一定程度上理解并自 动处理”文本信息。而文本聚类的目的也不外乎是使机器能够在“一定程度上理解 并自动组织”文本信息。换言之，处理只是手段，理解并自动组织才是目的。具 有理解并自动处理文本信息能力的机器，才算是智能文本信息处理机器，也才可 9 北京邮电大学博上学位论文第- 章绪论 以替代人类劳动者工作。但是，如何使得使机器能够在“一定程度上理解并自动 组织”文本信息。国内外关于这方面的研究，长期专注于“语法”层次的研究。如 何从“语法”上升至“语义”乃至“语用”的层次，最终达到对内容的理解，这仍然是 研究者努力工作的方向。 1 6 本文的工作 我们针对上一节所提出的4 个问题，主要做了以下几个方面的工作，如图1 3 所示，它们分别对应于本文的第2 至4 章。 文本分类和聚类中遇到的问题 设计出易于使用的工程化 文本分类处理方法 开发适用于海最信息的文本 分类处理算法 提高文本分类 处理技术的精度 将传统的文本聚类提升至 理解的层次 本文的工作 统计模型的研究 文奉颅处理技术的研究 n a i v eb a y e s 分类器的研究及改进 分类器集成 分炎器错误e + v 分解 指示分类器斗。成r 能的指标i v i 分类器集成性能的理论界限 达到理论上界的町能途径 统计模型的研究 字符级统计方法 基于转等推理的无标签样本学习 分类器集成 分类器错误e + v 分解 指示分类器集成性能的指标m 分类器集成性能的理论界限 达到理论上界的可能途径 非线性方法在文本聚类中应用 中文词i 在语义空间的分布情况 基于、o r d n 眦的短信聚类研究 图l 一3 本文的主要工作 上面从逻辑上阐述了本文的主要内容，如果从章节上来划分，本文的内容可 以分为： 第2 章，基于统计模型的文本分类。本章主要研究了传统的统计模型方法在 文本分类领域中的应用。首先，研究了贝叶斯方法在文本分类中的应用。在此基 础上，利用加权的方法给出了一种改进的贝叶斯算法。接下来，研究了如何利用 日 日 日 北京邮电大学博士学位论文第- 。章绪论 无标签样本进行学习的问题。通过科用转导推理，整合了无标签样本和有标签样 本的学习。最后，探讨了字符级统计方法在文本分类中的应用。此外，本章通过 一个在线自适应更新的垃圾邮件过滤任务和短信分类任务的解决贯穿始末，将本 章研究的内容逐一实现。实验结果表明。本章的方法不仅易于工程实现，能够联 合无标签样本学习，而且可以较好地在分类速度和精度之问达成折衷，以达到快 速准确处理海量文本信息的能力 第3 章，基于分类器集成的文本分类。本章主要研究了基于简单多数投票策 略的分类器集成问题。首先，给出了个分类器错误的分解式( 卧_ v 分解) ，在 理论证明的基础上，得到了一个能够指示分类器集成性能的指标i v l 。借由线性规 划方法，分析了基于简单多数投票策略的分类器集成性能的理论上下界。最后， 探讨了可能达到集成性能理论上界的两种途径：1 ) 选择性分类器集成：2 ) 基于 l v l 指标优化的分类器集成。此外，我们将这部分研究的方法应用于垃圾邮件过滤 任务。实验结果表明。本章的方法能够很好地提高集成后文本分类器的精度，具 有良好的应用前景。 第4 章，基于非线性方法的文本聚类。我们期望能够将传统的文本聚类处理 提升到理解的层次。将文本聚类领域的研究，从长期专注于“语法”层次的研究， 演进到“语义”的层次。首先，通过使用流形学习工具，研究了中文词汇在语义空 间( 分类空间) 的分布情况，这部分工作将为进一步的基于语义的特征选择工作 打下良好的基础。在此基础上，利用w b r d n e t 词典进行了短信聚类的研究。实