（模式识别与智能系统专业论文）文本分类中的特征选择方法研究.pdf

ab s tr a c t ab s t r a c t i n r e c e n t y e a r s , t h e r e h a v e b e e n e x t e n s i v e s t u d i e s a n d s i g n i f i c a n t p r o g r e s s e s i n a u t o m a t i c t e x t c a t e g o r i z a t i o n , w h i c h i s o n e o f t h e h o t s p o t s a s w e ll a s k e y t e c h n i q u e s 恤t h e i n f o r m a t i o n r e tr i e v a l a n d d a t a mi n in g fi e l d s . t e x t c a t e g o r i z a t i o n i s a n i m p o r ta n t r e s e a r c h a r e a a p p l y i n g t h e t e c h n o l o g y o f n a t u r a l l a n g u a g e p r o c e s s i n g , a n d w o r k a s a n e ff e c t i v e a p p r o a c h t o i n f o r m a t io n r e t ri e v a l a n d t e x t m in i n g . s p e c i fi c a l l y , w i t h t h e d e v e l o p m e n t o f i n t e r n e t a n d t h e h i g h - s p e e d i n c re a s e o f d i g i t a l i n f o r m a t i o n , t h e n e t w o r k h a s b e c o m e a w o r l d w i d e p l a t f o r m f o r i n f o r m a t i o n t r a n s f e r r i n g a n d i n t e ll ig e n c e p r o c e s s 吨.g i v e n s u c h .r a p i d i n f o r m a t i o n e x p l o s i o n , m a n u a l c a t e g o r i z a t i o n o f i n f o r m a t i o n b e c o m e s f a r fr o m e ff i c i e n t , t h e r e f o re t e n d s t o b e s u b s t it u t e d b y t e x t a u t o m a t ic c a t e g o ri z a t i o n s . i n t h e r e s e a r c h c o m m u n i t y , m o s t o f t h e s t u d i e s in a u t o m a t i c t e x t c a t e g o r i z a t i o n r e c e n t l y f o c u s o n t h e e x p l o r a t i o n o f c a t e g o r i z a t i o n a lg o ri t h m s a n d t h e i m p r o v e m e n t o f c l a s s i fi c a t i o n p e r f o r m a n c e . h o w e v e r , f e a t u r e s e l e c t i o n , w h i c h h a s a l w a y s b e e n a b o t t l e n ec k i n t e x t c a t e g o r i z a t i o n , i s s t i ll a p r o b l e m w h i c h c a l l s f o r m o re e ff e c t i v e a n d n o v e l s o l u t i o n s t o r e v o l v e . t h u s , 山 e re i s a n u r g e n t d e m a n d o f t h e s t u d y o n f e a t u r e s e l e c t i o n a l g o ri t h m s . t h i s d i s s e r ta t i o n i n v e s t i g a t e s s e v e r a l t e c h n o l o g i e s i n v o l v e d i n t e x t c a t e g o ri z a t i o n i n a l a r g e d e t a i l , a n d s p e c ia l l y a n a l y z e s t h e p e r f o r ma n c e , t h e m e r i t a n d t h e d e f e c t o f v a r i o u s f e a t u r e s e l e c ti o n a l g o ri t h m s w i d e l y u s e d i n t e x t c a t e g o r i z a t i o n . b a s e d o n t h i s in v e s ti g a t i o n , w e a d d r e s s a s e t o f e x i s t i n g p r o b l e m s in f e a t u r e s e l e c t i o n w i t h e ff e c t iv e 即p r o a c h e s w e p r o p o s e 氏w h i c h a r e b ri e fl y d e s c r ib e d a s f o ll o w s . ( 1 ) b e c a u s e t h e f e a t u r e s e l e c t i o n a p p r o a c h b a s e d o n d o c u m e n t f re q u e n c y , mu t u a l i n f o r m a t i o n m a y s e l e c t f e a t u r e s t h a t a r e r e l e v a n t t o b o t h c l a s s e s w h i l e e v e n ly d i s t ri b u t e d b e t w e e n 山 e t w o c l a s s e s , w e p r o p o s e d t h e c o n t ri b u t i o n d i ff e r e n c e i d e a , s tr e s s i n g t h a t t h e f e a t u r e s w h i c h c o n t ri b u t e e q u a l l y m u c h t o b o t h c l a s s e s d o n o t n e c e s s a r i l y h a v e s tr o n g c l a s s i fi c a t i o n a b i l i ty , b u t t h o s e v a ry g r e a t l y i n c o n t ri b u t i o n t o e a c h c l a s s d e fi n i t e l y h a v e s tr o n g c l a s s i f i c a t i o n a b i l i ty . d r i v e n b y t h i s m o t i v a t i o n , ab s tr a c t i m p r o v e m e n t s h a v e b e e n m a d e t o b o t h t r a d i t i o n a l d o c u m e n t f r e q u e n c y a n d m u t u a l i n f o r m a t i o n f e a t u r e s e l e c t i o n a p p r o a c h e s . ( 2 ) t o a d d r e s s t h e p ro b l e m o f d i ff i c u l t i e s i n e v a lu a t i n g t h e g e n u i n e v a lu e o f t h e f e a t u r e s in c u r r e n t f e a t u r e s e l e c t i o n a p p ro a c h e s , b y ta k i n g w o r d - fr e q u e n c y f a c t o r i n t o c o n s i d e r a t i o n , t h e d i s s e r ta t i o n p r o p o s e d a w o r d - fr e q u e n c y b a s e d a p p r o a c h t o f e a t u r e s e l e c t i o n a p p r o a c h b a s e d o n t h e i d e a o f c o n t r i b u t i o n d i ff e r e n c e . ( 3 ) t o a d d r e s s t h e p r o b l e m o f f e a t u r e r e d u n d a n c y i n c u r r e n t f e a t u r e s e l e c t i o n a p p r o a c h e s w h i c h f a i l t o c o n s i d e r t h e a s s o c ia t i o n a m o n g f e a t u r e s , t h e d i s s e r t a ti o n p r o p o s e d a c l u s t e r - b a s e d a p p ro a c h t o f e a t u r e s e l e c t i o n , w h i c h c l u s t e r s t h e f e a t u r e s b a s e d o n t h e s i m i l a r i t y b e t w e e n f e a t u r e s . wit h i n e a c h c l u s t e r , w e s e l e c t t h e c e n t e r o f t h e c l u s t e r a n d fi l t e r a ll 山 e o t h e r f e a t u r e s , in w h i c h w a y t h e r e d u n d a n c y o f t h e f e a t u re s e t i s s i g n i fi c a n t l y r e d u c e d t h e e x p e r im e n t a l r e s u l t s s h o w t h a t t h e p ro p o s e d a p p ro a c h e s s i g n i fi c a n t l y i m p ro v e t h e p e r f o r m a n c e o f t e x t c la s s i fi c a t io n . 盆 即 w o r d s . t e x t c a t e g o r i z a t i o n, f e a tu r e s e l e c t i o n , c l u s t e r , d o c u m e n t f r e q u e n c y , m u t u a l i n f o r m a t i o n , i n f o r m a t i o n g a i n . 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定 同意如下各项内容:按照学校要求提交学位论文的印刷本和电 子版 本;学校有权保存学位论文的印 刷本和电 子版，并采用影印、缩印、 扫描、 数字化或其它手段保存论文; 学校有权提供目 录检索以 及提供 本学位论文全文或者部分的阅览服务; 学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版; 在不以赢利为目的的前 提下，学校可以 适当复制论文的部分或全部内容用于学术活动。 学 位 论 文 作 者 签 名 : 弘豆 衰 :z 0 0 7 年， 月 ， 日 经指导教师同意， 本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名:学位论文作者签名: i 立 及 解密时间:年月日 各密级的最长保密年限及书写格式规定如下: 内部 5 年 ( 最长5 年， 可少于5 年) 秘密1 0 年 ( 最长1 0 年，可少于1 0 年) 机密2 0 年 ( 最长20年，可少于2 0 年) 南开大学学位论文原创性声明 本人郑重声明: 所呈交的学位论文， 是本人在导师指导下， 进行 研究工作所取得的成果。 除文中已经注明引用的内容外， 本学位论文 的研究成果不包含任何他人创作的、 己 公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体， 均已 在文中以明 确方式标明。 本学位论文原创性声明的法律责任 由本人承担。 学 位 论 文 作 者 签 名 :4之 瓦 2 im 7年 .4 - 月 / 8日 第一章 引言 第一章 引言 1 . 1文本分类中特征选择问题的背景与意义 随着信息时代的到来和科学技术的迅猛发展，互联网为人们提供了极其丰 富的 信息资源， 其飞速发展也导致其信息量呈几何级数增长。为了 有效地管理 和利用这些信息， 基于内 容的 信息 检索和数据挖掘逐渐成为备受关 注的 领域。 其中， 文 本分 类( t e x t c a t e g o r i z a t i o n ， 简称 t c ) 技术 是信息 检索 和文 本 挖掘的 重要 基础， 其主要任务是在预先给定的 类别标记( l a b e l ) 集合下， 根据文本的内 容判定 它的类别。文本分类在自 然语言处理与理解、 信息组织与管理、内容信息过游 等领域都有着广泛的应用。2 0 世纪9 0 年代逐渐成熟的汲取机器学习的文本分类 方法，更注重分类模型的自 动挖掘和生成及动态优化能力，在分类效果和灵活 性上都比 之前基于知识工程和专家系统的文本分类系统有所突破，成为相关领 研究和应用的经典范例。 文本自 动分类技术是替代传统的繁杂人工分类方法的有效手段和必然趋 势， 特别是随着互联网技术的发展，网络成为人们进行信息交互和处理的最有 效平台， 各种数字化信息每天以 极高的 速度增长， 面对如此巨 大的信息， 人工 分类己 经无能为力，计算机自 动分类已 成为网 络时代的必然选择。通过利用先 进的计算机技术、人工智能技术，不仅可以实验方便快捷的分类效果，节省大 里的 人力物力，并且可以 进一步进行更深层次的 信息挖掘处理， 提高信息的利 用效率. 目 前对于文本分类技术的 研究， 大多数研究者的 精力主要放在各种不同 分 类方法的探索与改进上。 然而，文本分类中的 特征选择一直是文本分类的关键 技术和瓶颈技术，因此， 对于特征选择算法的 研究是十分必要的。 随着网 络的发展， 在线文档爆炸式增加， 对文本分类提出了 更高的要求。 目 前， 在自 动文本分 类中 主要采 用向 量空间 模型 ( v s l1 o 表 示文本， 一般 选 择文本 信息的基本单位，即文本中的词作为 特征项。 构成文本的词 汇的 数量是相当 大 的，从而得到的文本向量和词频矩阵为数都会相当大，可以 达到几万维。在理 第 1 页 第一章 引言 论上， 较多的特征应该能提供比 较强的识别能力， 但是当 面对实际的 机器学习 过程时，对于有限的训练数据，过多的特征不仅大大减慢学习程序的速度，同 时也会导致分类器对训练数据的过度拟合， 特别是那些与类别不相关的 特征和 冗余特征，更会误导学习算法。在众多的原始特征中，存在不少特征是不相关 的 和冗余的 . 我 们可以 将特征 按照其对最终 分 类的 作用分为三 类 1 z 1 ， 相关 特征 ( r e l e v a n t f e a t u r e ) 、 不相关 特征 ( i r r e l e v a n t f e a t u r e ) 和冗 余 特征 ( r e d u n d a n t f e a t u r e ) . 其中 相 关 特征就 是那 些包含明 显分 类 信息， 去除 之后 将导 致错 误率明 显上升的那些特征，即相关特征能够非常高效的将各个类别互相区分开:与之 相反，不相关特征不含任何的分类信息;冗余特征中虽然含有一定的分类信息， 但是 这些分类信息己 经被其 他的 相关 特征所提供 3 1 . 也就 是说， 不相关 关 特征和 冗余特作对最终的 分类没有作用或作用不大。为了 准确的 估计参数或者对未知 样本进行分类， 训练样本的 个数是随着特作数目 呈指数增长的， 这就是所谓的 维数灾难问 题 ( c u r s e o f d im e n s i o n a li ty ) 。 许多分类算法的 性能受到无关特征和 冗余特征的影响，如朴素贝叶斯、最近邻、决策树和神经网络等。 综上所述，特征选择问 题是一个相当难的问题，历来深受人们的关注。由 于该问题的复杂性，对于特征有效选择的研究曾经进入过相对低潮，也相对制 约了 模式识别和人工智能的发展。随着计算机硬件性能的不断提升，过去由于 计算上过于复杂难以 求解的问 题现在可以使用计算机进行求解， 从而对于特征 选择的 研究又渐渐进入高潮。目 前，特征选择方面的研究还存在不少的缺陷， 在不少方面需要不断进行改进、弥补、发现和革新，以 达到最终提高分类器性 能的目 的。总而言之， 特征选择是模式识别中最为困难的任务之一，也是模式 识别系统中最为重要的一个环节。因此，对特征有效选择的深入研究，是十分 具有理论和实际价值的，特征选择理论和方法的进步，必将推动模式识别和人 工智能科学的发展。 第 2 页 第一章 引言 1 . 2研究现状 1 .2 . 1文本分类技术 文本分类是文本挖掘中一项非常重要的任务，也是国内外研究较多的一种 挖掘技术。在机器学习中分类称作有监督学习或有教师归纳，其目的是提出一 个分类函数或分类模型 ( 也称作分类器)，该模型能把数据库中的数据项映射 到给定类别中的一个。 一般来讲，文本分类需要四个步骤: ( 1 ) 获取训 练 文本集: 训练文 本集由 一组 经过预处理的 文本特征向 量组 成， 每个训练文本 ( 或称训练样本) 有一个类别 标签; ( 2 ) 选择分 类 方法并训练分 类模型: 文 本分 类方 法有统计方法、 机器学习 方 法、神经网络方法等等。 在对待分类样本进行分类前， 要根据所选择的 分类方 法，利用训练集进行训练并得出分类模型; ( 3 ) 用训 练 得到的 分类模型 对其它待 分类 文 本进行 分类; ( 4 ) 根据分类结果评估分类模型。 另外需要注意的是， 文本分类的效果一般和数据集本身的 特点有关。 有的 数据集包含噪声，有的 存在缺失值，有的分布稀疏，有的字段或属性间相关性 强。目 前，普遍认为不存在某种方法能适合于各种特点的数据4 . 气 随着i n t e rn e t 技术的发展和普及，在线文本信息迅速增加，文本分类成为处 理和组织大量文本数据的关键技术。而近二十多年来计算机软、硬件技术的发 展和自 然语言处理、 人工智能等领域的研究进展为文本自 动分类提供了 技术条 件和理论基础。 迄今为止， 文本分类研究己 经取得了 很大的进展， 提出了 一系 列 有 效 的 方 法 ， 其 中 分 类 质 量 较 好 的 有 k 最 近 邻 ( k -n e a r e s t n e i g h b o r , k n n ) 14 - 6 . 7 1 支 持向 量 机 ( s u p p o r t v e c t o r m a c h in e , s v m ) 、 朴 素 贝 叶 斯 ( n a iv e b a y e s , nb). 1 9 9 8 年文 献 1 2 1 提出了 基于关 联规则的 分类方 法 c b a ， 此后陆 续有 人进行 这 方面 的研究。 国内 对中 文文本自 动 分类的 研究 起步 较晚， 尽管己 有一些研究成果 1 3 - 1 6 1 第 3 页 第一章 引言 但由于尚没有通用的标准语料和评价方法，很难对这些成果进行比 较。 1 . 2 .2特征选择技术 国 外对特征选择的 研究较多， 特别是己 有专门 针对文本分类特征选择方法 的 比 较 研究 门 . 国内 对 这一问 题的 研究以 跟 踪 研究 为 主， 集中 在 将国 外 现 有的 特 征评估函数用于中文文本特征选择及对其进行改进。 关于特征选择的算法，很多研究仍然按照传统的思路: ( 1 ) 用概率统 计方法度量并比 较 特征 项关 于类别分布的 显著性， 如b n s ( b i- n o r m a l s e p a r a t io n ) 11 71 等 ; ( 2 ) 从 信 息 嫡 角 度 研 究 特 征 项 分 布 相 似 性 的 方 法， 如 基 于 全 局 信 息 ( g i ) 1 1 8 1 等; ( 3 ) 隐 含语义 分析 途径， 即 通过 矩阵的 不同 分解 和化简 来获取 将向 量语 义或 统 计 信 息向 低 维 空 间 压 缩 的 线 性 映 射， 如 差 量 ( d iff e r e n t ia l) l s i 1 等 . 一些新颖的研究思路包括: ( 1 ) 多步骤或组合的 选择方法， 即首先用基本的 特征选择方法确定初始的特 征 集 ， 然 后以 某 种 标 准 ( 如 考 虑 其 他 项 与 初 始 集 特 征 的 同 现 ( c o - o c c u r r e n c e ) 等 2 1b 进 行 特 征 的 补 充， 或 者 综 合 其 他 因 素 ( 如 依 第 2 种 显 著 性 选 择 标 准 2 1 , 2 2 1或 考 虑 线 性 分 类 器 系 数 值 大小 23 等 ) 进行 冗 余 特 征的 删 减; ( 2 ) 尝试借鉴语言学技术进行的 研究有从手工输入的 特征中 学习 特征信息 2 4 1 及基于 wo r d n e t 2 5 1 的 特征提取等方法， 但方法所产生的 效果都不理想. 特征选择必须考对分类的影响，即关注分类器效果指标随特征数目 增加的 变 化 趋 势 . 很 多 文 献 中 7 . 17 - 2 2 , 2 6 1 比 较 一 致 的 现 象 是 : 合 理 的 降 维 方 法 会 使 多 数 分 类器都呈现出随特征数量增加， 效果快速提高并能迅速接近平稳; 但若特征数 目 过大， 性能反而可能出 现缓慢降 低。这表明:降维不仅能大量降 低处理开销， 而 且 在 很多 情 况下 可以 改 善 分 类 器的 效 果. f o r m a n 及y a n g 等 人 分 别 从 有 效 性、 区分能力及获得最好效果的 机会等方面对不同的 特征选择方法进行了 广泛比 较 7. 171。 从 结 果 来 看 : b n s , 扩 ， ig 等 统 计 it 及 组 合 方 法 具 有 一 定 的 优 势 : 另 外 ， 不 同 分 类 器 倾 向 于 接 受 不 同 的 特 定 降 维 方 法 7 , 17 ,2 1 ,2 6 1 . 常 用 的 特 征 提 取 与 特 征 选 第 4 页 第一章 引言 择 算 法 的 效 果 在 不 同 情 况 下 互 有 高 低 或 相 当 27 , 18, 2 81 1 3本文主要研究内容 本文首先对文本分类中的所涉及各项技术进行了 较全面的阐述， 并指出 特 征选择是文本分类过程中的一项关键任务。 对当 前文本分类中 各种常用的 特征 选择算法的性能及优缺点进行了分析，指出了现有特征选择方法存在的三个问 题: ( 1 ) 评估函 数不合理 文档频数和互信息等方法，均通过某种的评估函数计算特征与各个类别之 间的相关性，再将这些相关度简单求和、求均值得到最终的 特征平均。这类方 法有可能选择与各个类别相关度都较大、但在类间分布比较均匀的特征，而这 类特征包含的分类信息是相当少的，应该从特征集中剔除。 可见， 这两种特征 选择方法的评估函数存在不合理之处。 ( 2 ) 未考虑词频因素 现有的文本特征选择方法均未考虑词频因素，即认为特征在文档中出现一 次 与 多 次 的 效 果 是 一 样的 : 文 档 频 数、 犷 统 计 方 法 的 计 算 仅 需 统 计 包 含 特 征 项 的 文档数;而信息增益、互信息、期望交叉嫡、文本证据权和几率比方法都是基 于概率的评估方法， 仅需要特征的0 / 1 表示，也忽略了 特征的词频因素。 但是直 观上看， 一个文档包含某个特征一次与多次的意义应该是不同的， 现有的方法 忽视了这种差异， 必然导致特征的价值无法被正确地评估。 ( 3 ) 特征冗余问 题 现有的 文本特征选择的 基本思想通常是构造一个评价函 数， 对特征集的每 个特征进行评估. 这样每个特征都获得一个评估分， 然后对所有的 特征按照其 评估分的 大小进行排序， 选取预定数目 的 最佳特征作为结果的 特征子集。由 于 这类方法只考虑了 特征与类别之间的相关性， 而忽略了 特征之间的 关联， 所以 无法处理特征冗余问题。 针对上述的三个问 题，本文提出了 三种改进的特征选择方法: 第5 页 第一章 引言 ( 1 ) 基于差分贡献的特征选择方法 在特征评估中， 对两个类别“ 贡献” 都大的 特征并不意味着对这两个类别 的分类能力也强， 而贡献差大的 特征却往往具有强类别区分能力。 基于“ 差分 贡献”的方法能够过滤掉在两类间 概率分布比 较均匀，分布差异不大的特征， 保留了 大量出 现在某一类中， 而在另一 类中出 现次数比 较少的 特征。 ( 2 ) 基于差分词频的特征选择方法 将词频统计和 “ 差分贡献”的思想结合起来， 如果一个特征在两 类之间的 词频差较大，则认为它具有较强的类别区分能力。这类特征选择方法适用于两 类问题。 ( 3 ) 基于聚类的 特征选择方法 现有的特征评估方法均根据各个特征在不同类别的不同实例的重要性来筛 选特征，由于这类方法只考虑了 特征与类别之间的相关性，而忽略了特征之间 的关联，所以无法处理特征冗余问题。通过将特征聚类，簇内特征间都非常相 似， 这些 特征在类别区分能力上往往也是类似的。因 此， 我们取每个簇的中 心 代表整个簇， 将簇中的其他特征过滤掉， 这样特征集的冗余性就大大降 低。 最后通过实验验证三种改进的方法的有效性。 1 a本文内容结构 本文一共六章，内容安排如下: 第一章为引言，首先简单介绍文本分类、 特征选择的研究意义与研究动态， 指出 特征选择是文本分类问 题中的瓶颈技术和关键技术，界定本文的 主要研究 内容. 第二 章介绍文本分类和特征选择的知识和背景， 首先介绍文本分类的 概念， 及文本分类中的各项关键技术， 然后介绍特征选择的 概念及相关技术， 最后介 绍常用的文本特征选择方法。 第三章提出现有的文本特征选择方法中 存在的三个问 题:评估函数不合理、 未考虑词频因素和特征冗余性问 题，并介绍相关改进工作。 第 6 页 第一章 引言 第四章提出 “ 差分贡献”的思想，并基于这个思想对传统的文档频数和互 信息方法进行改进。 接着又将 “ 差分贡献” 和词频统计相结合， 提出基于差分 词频的特征选择方法，将词频作为评估特征价值的一个关键因素。 第五章提出 基于聚类的 特征选择方法， 该方法通过聚类的手段解决特征集 的冗余性问题。 第六章介绍实验设置和实验结果分析。 其中 第三章对现有特征 选择方法存在问 题的 分析，与第四、 五章提出的对 这些问题的解决方法，是本文的研究重点。 第七章是对全文工作的总结，并提出 进一步的研究方向。 第7 页 第二章 文本分类中的特征选择方法概述 第二章 文本分类中的特征选择方法概述 2 . 1文本分类技术综述 2 . 1 . 1问题描述 i n t e r n e t以 惊人的速度发展起来，随之而来的是互联网上容纳的海量的各种 类型的原始信息，包括文本信息、声音信息、图像信息等等。如何在浩若烟海 而又纷繁芜杂的文本中掌握最有效的信息始终是信息处理的一大目 标.基于人 工智能技术的文本分类系统能依据文本的语义将大量的文本自 动分门别类，从 而更好地帮助人们把握文本信息。近年来，文本分类技术已 经逐渐与搜索引擎、 信息推送、信息过滤等信息处理技术相结合，有效地提高了信息服务的质量。 典型的文本分类应用包括:垃圾邮件的判定、新闻出版按照栏目 分类、网页分 类 ( 类似与y a h o o 的分类) 、 个性化新闻等。 概括地说， 文本分类的任务就是要在给定的分类体系下， 根据文本的内容由 系统自 动地确定文本所属的 类别。从数学角度来看，文本分类是一个映射的过 程，它将未标明类别的文本映射到己知的类别中。因为一篇文本有可能只属于 某一个类别，也有可能同多个类别相关联，因此这个映射可以是一一映射，也 可以是一对多映射。用数学公式表示如下: f : a - b f : a - + b其中， a为 未知类 别的 文本集 合， b 为 分类体系中的 类 别集合。 文本分类的映射规则是系统通过学习已 有类别标记的训练数据， 总结出分类 的规律性而建立的 判别公式和判别规则。 然后在遇到新的文本适时，根据总结 出的判别规则，确定文本所属的类别。 2 . 1 .2文本表示与向量空间模型 目 前自 然语言理解领域的多项实践标明， 在以自 然语言为 研究对象的知识处 第 8 页 第二章 文本分类中的特征选择方法概述 理和知识获取问题中，知识表示始终是其主要的瓶颈。要将文档相互比较，首 先就 要 描 述 文 档. 在 文 献 2 9 1 第 一 次 提出自 动 文 本 检 索 ( a u t o m a t i c t e x t r e tr ie v a l) 和信息检索( i n f o r m a t i o n r e t r i e v a l ) 概念后， 出 现了 许多基于文档( d o c u m e n t ) 和 ( q u e ry ) 之间相关词语比较的计算模型，具有代表性的有布尔模型( b o o l e a n m o d e l) 3 0 l ，向 量空间 模型( v e c t o r s p a c e m o d e l, v s m ) p l , 聚类模型 ( c lu s te r m o d e l) j1 2 1 , 荃 于 知 识 模型 ( k n o w le d g e - b a s e d m o d e l ) 3 3 和 概率 模型 ( p r o b a b i li s tic m o d e l) 3 z 3 4 1 等。 上述几 种模型中，向 量空间 模型( v s m ) 由 于具有较强的 可计算性和可操作 性，得到了广泛的应用。特别是随着网上信息的迅速膨胀，它的应用已经不仅 仅局限于文本检索、自 动文摘、关键词自 动提取等传统问题，还被广泛地应用 到搜索引擎、个人信息代理、网上新闻发布等信息检索领域新的应用中，并取 得了较好的效果。 向a空间模型的最大优点在于它在知识表示方法上的巨大优势。在该模型 中， 文档的内 容 被形式 化为多 维空间 中 的 一 个点 ， 通过向 量( v e c t o r ) 的形 式给出. 文本分类则可方便地转化成对向量的处理、计算。也正是因为把文档以向量的 形式定义到实数域中，才使得模式识别和其他领域中的各种成熟技术得以采用， 极大地提高了自 然语言文档的可计算性和可操作性。 向量空间模型的缺点在于关键词之间线性无关的假说前提。在自 然语言中， 词或短语之间存在着十分密切地联系，即存在 “ 斜交”现象，很难满足假定条 件，因此对计算结果地可靠性造成一定的影响。此外，将复杂地语义关系归结 为简单的向量结构，丢失了许多有价值地线索。 2 . 1 .2 . 1向且空间模型的基本概念 项( t e r m ) : 文本的内 容 特征常常 用它 所含有的 基本 语言单 位( 字， 词， 词组， 或短语等) 来表示， 这些基本的语言单位被统称为文本的 项，即文本可以 用项 集 ( t e r m l i s t ) 表 示为d ( t t 2 , ., t ) ， 其中 t k 是 项，1 5 k 5 n e 项的 权 重 ( t e r m w e ig h t ) : 对于 含 有n 个 项的 文 本d ( t t . . , 0， 项tk 被 赋 予 一定的权 重 w k，表示它们在文本 d 中的重要程度 ，即 第 ， 页 第二章 文本分类中的特征选择方法概述 d = d ( t w , ; t 2 , w , ; . .; t , 嗽) ， 简 记 为d = d ( w , ; w 2 ; . .; 嗽) . 这 时 我 们 说 项t k 的 权 重为巩，1 5 k 5 n . 向 量 空间 模 型 ( v s m ) : 给 定 文 本d = d ( t 不 ; t 2 , w , ; .; t , w . ) ， 由 于t k 在 文 本 中既可以重复出现又有先后次序的关系，分析起来仍有一定的困难。为了简化 分析， 可以 暂时不 考虑tk 在文档中的 先后 顺序并要求tk 互异. 这时 可以 把 tl ， t:， “ ， 气 看成一个， 维的坐标系，而不 ， 巩， ” .， 嗽为相应的坐标值，因而 d ( w . ; w 2 ; . ; w . ) 被 看 成n 维 空 间 中 的 一 个向 量 . 我 们 称d ( w , ; w 2 ; . ; w) 为 文 本d 的向量表示。 相 似 度 ( s i m i l a r i t y ) : 两 个 文 本d , 和d 2 之间 的内 容相 关 程 度常 常 用 它 们 之间 的 相 似 度 s im ( d d 2 ) 3 5 1来 度 量 。 当 文 本 被 表 示 为 向 量 时 ， 我 们 可 以 借 助 于 向 里 之间的某种距离来表示文本之间的相似度，常用向量之间的内 积进行度量: l)2) (2-(2- s im ( d d 2 ) = 艺w ,k x w 2 k 或者用夹角余弦值表示， 如公式( 2 - 2 ) 和图2 . 1 所示。 s i m ( d几) = c o s o k _ i k _ 1 d1 d2 图2 . 1 文 本间 的 相 似 度s im ( 几， 几) 2 . 1 .2 .2项的选择 如前所述，项可以 是文本中的 各种语言单位， 对中 文来说 有字、词、 短语， 第 1 0页 第二章 文本分类中的 特征 选择方法概述 甚至是句子或句群等更高单位。项也可以是相应词语或者短语的语义概念类。 因此，项的选择只能由处理速度、精度、存储空间等方面的具体要求来决定。 选出的项越具有代表性，语言层次越高，所包含的信息就越丰富，但是分析的 代价就越大，而且受分析精度 ( 如句法分析的正确率)的影响 就越大。 由 于词汇是文本最基本的表示项， 在文本中出 现的 频度越高， 就越能呈现一 定的统计规律，再考虑到处理大规模真实文本所面临的困难，选择词作为特征 项是比较合理的， 常常被应用于文本检索与分类邻域。但是直接选用文本中的 词作为文本特征项也会存在以下问题: ( 1 ) 文 本中 存 在一些没 有实际意义但是 使用 频率 很高的 虚词 和功能词， 入中 文 中的“ 的气“ 把” ， “ 了” 等，英语中的“ t h e . a , o f 等， 常常把一些真正 有分类作用的实词淹没掉。 解决这个问题的方法是把这些词组织成一个禁用词 表 ( s to p l i s t) 3 6 1 ， 把 禁 用 词 表 中 的 词 从 特征 集 中 过 滤 掉 。 此外， 还可以 在文本预处理时进行词性标注， 从词汇特征集中滤去那些对区 分类别贡献极小的大部分虚词和功能词。 ( 2 ) 一词多义 或词 汇 变形问 题. 事实 上，自 然 语言 有着极 其 丰富的语言 现象. 例如词汇之间的关系，就有同义、近义、从属、 关联等关系。 在使用短语等复合词时， 关系就更复杂了。 另外， 词汇的歧义和多义也很普 遍， 例如“ 他高兴地走了” ( 副词“ 地” 应该是禁用词) ， “ 地很不平” ( 名词“ 地” 不应作为禁用词) ，因此，不同的词义当作不同的项来看会更合理。 词汇的变形问 题主要是指西文单词有复杂的词尾变化和派生现象。 解决这些 问题常有两种方法: 第一种是进行概念语义标注，以 便把同义的或相似的特征 项 合 并 为 相 应的 概 念 类. 第 二 种， 对 于 西 文， 可以 通 过 抽 取 词 干 ( s t e m m in g ) 3 , 处理，把同 源的词用同一个词来标记。显然， 通过概念标注并利用概念信息作 为文本的 特征项比 单纯的 词汇信息更能反映文本的内容.因此， 词汇相同 或相 近的词汇往往被映射为一个概念，而同一词汇所表示的词义也是和上下文相关 的， 把词汇在具体的 上下文所对应的概念作为文本的描述项，则内 容相似但用 词上有较大差异的 文章，彼此之间的相似度就会大大增加。所以 采用概念作为 特征项是比较合理的， 但这样做的同时也势必加大了文本处理的复杂程度. 第 1 1 页 第二章 文本分类中的特征选择方法概述 2 . 1 .2 .3关于向量空间模型的讨论 向 量空间 模型虽然具有许多 优点， 但同 时也存在许多不足之处: 首 先，向 量空间 模型是一 种不考虑 特征 项出 现顺序的 词 袋 田 a g o f w o r d s ) 文 本表示模型，这种模型虽然带来了 计算和操作上的方便， 但却损失了 大量的文 本结构信息。 而这些信息在自 然语言中 是至关重要的 ( 如句子中 词序信息等) 。 其次， 在权重计算和相似度的 计算中 也做了很多简化工作: 一是对不同的语 言单位构成的 特征项大都只考虑其统计信息并采用统一的权重计算方法， 而这 种计算只是经验公式， 并没有很好的理论基础， 所以 计算出的权重未必能真实 反映各项的重要性。二是向 量空间模型是建立在所有项两两正交这一假设基础 之上的， 没有考虑特征项间的相关性。 对于自 然语言这种有着非常丰富语言现 象的研究对象来说，这种假设显然是过于严格的，不能很好地反映自 然语言的 特征。目 前己 经有许多改进项权重计算的方法，但是效果并不明显，原因在于 语义关系实际 上是一个很复杂的 运算， 采用简单的初等运算代替它，误差势必 存在。 因此，如何确定和弥补现有文本内容映射到特征项时大量有效信息的损失， 是自 然语言处理领域今后需要关注和解决的问题之一。 2 . 1 . 3文本分类方法概述 分类算法是分类系统的核心部分，在分类器构造上早期多使用基于知识工 程的 规 则 方 法 ， 现 在 主 要 使 用 基 于 统 计 的 方 法 ， 如 朴 素 贝 叶 斯 ( n a iv e b a y e s ) 13 , k - 近 邻 ( k - n e a r e s t n e i g h b o u r s , k - n n ) 1-9 、 回 归 模 型 ( r e g r e s s io n m o d e l ) 15 1 、 神 经 网 络 ( n e u r a l n e tw o r k , n m 13 1 1 、 支 持 向 量 机 ( s u p p o r t v e c t o r m a c h in e ) 3 1 4 2 1等 . 其 中 ， 经过大t实验证明， s v m, k n n是性能比 较优秀的分类器。 下面简要介绍一下 这几种分类方法。 1 . 朴素贝叶斯算法 在 文 本自 动 分 类中 ， 贝 叶 斯 ( b a y e s ) 分 类 方 法 3 a 1 是 一 种 最 常 用 的 、 有 指 导 性 的方法， 它以贝叶斯定理为理论基础，是一种在己知先验概率与条件概率的情 第 1 2 页 第二章 文本分类中的特征选择方法概述 况下的模式识别方法。 贝叶斯分类器分两种: 一种是朴素贝叶斯分类器， 它假设一个属性对给定 类的影响独立于其他属性，即 特征独立性假设。当假设成立， 与其他分类算法 相比， 朴素贝叶 斯分类器是最 精确的. 有很多经 验证明 u 】 这种分 类方法比 较简 单，能正确地对文本进行分类，且不需要花太多时间去训练分类模型，运行速 度较快，因此