硕士学位论文-SVM在文本分类中的应用.pdf

哈尔滨工程大学硕士学位论文 摘要 随着 i n t e rn e t 的迅速发展，网络信息不断膨胀。为了提供高效、准确的 信息服务，作者需要对网络中纷繁芜杂的信息进行合理的组织与分类。本文 的目 标就是以文本信息处理为背景， 从理论及应用两个层次对文本信息的分 类方法进行了较为深入的研究。 首先，本文研究分析文本分类器的总体模型，包括:信息预处理、特征 表示、特征提取。重点研究分析了特征表示与特征提取技术，文本的分类算 法。 其次，认真研究了统计学习理论的主要内容和 s v m算法的基本原理。 并且就 s v m的训练算法、分类算法、多类分类算法、 核函数等热点问 题分 别加以讨论。阐述了s v m研究和应用现状，以及所面临的问题。 最后详细分析研究了一个基于 s v m 的文本分类器模型。该模型通过计 算训练集中的词条和类别的加权互信息，获得文本特征集， 然后通过智能分 词和统计方法获得测试文本在v s m空间中的t f - i d f函数表示， 通过计算语 义相似度获得文本的语义信息，对文本向量进行加权。训练文本集按照上面 方法进行向量表示后，作为支持向 量机的学习向量进行训练，从而获得文本 分类的支持向 量。 对于将要进行分类的文本， 也按照上面的方法进行向量化， 然后通过支持向量机判别该文本的类别。在该模型的基础上，并以系统中的 多类分类为例， 探讨了s v m的核函 数选择以 及惩罚参数c的确定，并结合 实验加以验证。 关键词:文本分类;统计学习理论:s v m;多类分类 哈尔滨工程大学硕士学位论文 a b s t r a c t n e t w ork i n f o r m a t i o n i n c r e ase s r a p i d 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 rne t . i n o r d e r t o m a k e t h e i n f o r m a t i o n s e r v i c e m o r e e f f i c i e n t a n d p r e c i s e , i t i s i m p o rt a n t t o m a k e t h e i n f o r ma t i o n i n i n t e rne t o r g a n i z e d a n d c a t e g o r i z e d r e a s o n a b l y . t h e t e x t f o c u s e s o n p r o c e s s i n g t e x t i n f o r m a t i o n i n t h e n e t w o r k a n d p r o c e e d e s t h e r e s e a r c h o n t e x t c a t e g o r iz a t i o n fr o m t w o l e v e l s : t h e o ry a n d a p p l i c a t i o n . f i r s t l y , t h e t e x t a n a l y z e s t h e t o t a l m o d e l o f t e x t c a t e g o r i z a t i o n , i n c l u d i n g t h e i n f o r m a t i o n p r e p r o c e s s i n g , f e a t u r e r e p r e s e n t a t i o n a n d f e a t u r e c a t c h i n g . t h e a u t h o r a n a l y z e s t e c h n o l o g i e s o f f e a t u r e r e p re s e n t a t i o n , f e a t u r e c a t c h i n g a n d t e x t c a t e g o r i z a t i o n a l g o r i t h m e s p e c i a l l y . s e c o n d l y , t h e t e x t s t u d i e s t h e s t a t i s t i c a l l e a rn i n g t h e o ry ( s l t ) a n d s u p p o rt v e c t o r ma c h i n e ( s v m) t h e o r y s e r i o u s l y , d i s c u s s e s t r a i n i n g , c a t e g o r i z i n g a n d m u l t i - c a t e g o r y c l a s s i f i c a t i o n a lg o r it h m a n d k e rn e l f u n c t i o n . t h e a u t h o r s h o w s t h e r e s e a r c h a n d a p p l i c a t i o n s t a t u s o f s u p p o r t v e c t o r m a c c h i n e , a n d p o i n t s o u t s o m e i m p o rt a n t i s s u e s . f i n a l l y , t h e t e x t a n a l y z e s a d o c u m e n t c a t e g o r i z a t i o n mo d e l b ase d o n s v m. t h i s m o d e l g e t s t h e t e x t f e a t u r e s m o d e l b y c a l c u l a t i n g t h e m u t u a l i n f o r m a t i o n o f w o r d s a n d t y p e s . t h e n i n t e l l i g e n t c h i n e s e w o r d s e g m e n t a t i o n s y s t e m b a s e d o n s y n t a x u n d e r s t a n d i n g h e l p s t h e a u t h o r g e t t h e t f - i d f d e s c r i p t i o n i n v s m o f t h e t e s t i n g d o c u m e n t . t h e w o r d s i m i l a r i t y i s t a k e n t o w e i g h t t h e d o c u m e n t v e c t o r f e a t u r e s . a ft e r b e i n g t r a n s l a t e d t o t h e v e c t o r s , t h e t r a i n i n g d o c u m e n t s a r e l e a rne d b y t h e s v m a n d t h e s u p p o rt v e c t o r i s g o t t o c a t e g o r i z e . t h e n t h e a u t h o r c a n c a t e g o r i z e t h e t e s t i n g d o c u m e n t s a ft e r t r a n s l a t i n g t h e d o c u m e n t s t o v e c t o r f e a t u r e s b a s e d o n t h e mo d e l , t h e a u t h o r d i s c u s s e s t h e k e rne l f u n c t i o n c h o i c e a n d t h e p e n a lt y p a r a m e t e r c d e t e r m i n a t i o n th r o u g h t h e e x a m p le s o f , m u lt i - c a t e g o r y c l ass i f i c a t i o n i n s v m, c o n f i r m s t h e c o n c l u s i o n s b y t h e e x p e r i m e n t s 哈尔滨工程大学硕士学位论文 k e y w o r d s : t e x t c a t e g o ri z a t i o n ; s l t ; s v m; m u l t i - c a t e g o ry c l a s s i f i c a t i o n 哈尔滨工程大学 学位论文原创性声明 本人郑重声明: 本论文的所有工作， 是在导师的指导 下，由作者本人独立完成的。有关观点、 方法、数据和文 献的引用已在文中指出， 并与参考文献相对应。 除文中己 注明引用的内容外， 本论文不包含任何其他个人或集体已 经公开发表的作品成果。 对本文的研究做出 重要贡献的个 人和集体， 均已在文中以明确方式标明。 本人完全意识到 本声明的法律结果由本人承担。 作 者 、签 字 ): 川 皿j 日 期 : i m d年2月劫 日 哈尔滨工程大学硕士学位论文 第 1 章绪论 1 . 1课题的来源、目的和意义 本课题来源于黑龙江省自 然科学基金项目 f 0 3 - 0 4 f 0 1 - 0 6 ) 。 文本分类 是一种确定文章所属类别的情报分析方法，是大型信息检索或文本挖掘系统 中的一个重要组成部分，也是文本挖掘的核心环节。由于文本分类可以应用 于信息检索、机器翻译、自 动文摘、信息过滤、邮 件过滤等诸多领域，因此 文本的自 动分类是自 然语言处理的一个十分重要的问题n .2 1 。在文本自 动分类 中，分类模型 ( 分类器)是决定分类效果好坏的一个关键部分，现有的文本 分 类模型 主要有 决策树( d e c i s i o n t re e ， 简 称d t ) 、 支持向 量机( s u p p o r t v e c t o r ma c h i n e ，简称s v m) 、贝叶斯网络、k - 最邻近法 ( k n n )等。 统计学习理论是一种专门研究有限样本条件下机器学习规律的理论。该 理论针对小样本统计问题建立了一套新的理论体系，在这种体系下的统计推 理规则不仅考虑了 渐近性能的要求，而且追求在现有有限 信息的条件下得到 最优结果。统计学习理论是建立在一套较坚实的理论基础之上的，为解决有 限样本学习问题提供了一个统一的框架。在这一理论基础上发展了一种新的 通用学习方法s v m，该方法已初步表现出很多优于己有方法的性能。 s v m方法是建立在统计学习理论的v c维理论和结构风险最小化原理基础上 的，根据有限的样本信息在模型的复杂性 ( 即对特定训练样本的学习精度， a c c u r a c y ) 和学习能力 ( 即无错误地识别任意样本的能力) 之间寻求最佳折 衷，以 期获得最好的 推广能力 ( g e n e r a l i z a t i o n a b i l i t y ) 。目 前， s v m算法在 模式识别、回归估计、概率密度函数估计等方面都有应用。例如，在模式识 别方面，对于手写数字识别、语音识别、人脸图像识别、文章分类等问题， s v m算法在精度上已经超过传统的学习算法或与之不相上下134 1 . 本文正是根据 s v m 的特点和己 有的研究经验及成果，设计了一个基于 s v m的文本分类器，对s v m在文本自 动分类中的 应用效果、 优缺点及其应 用潜力进行了初步的研究。 一裂垫塑垄璧理理婴二一一一一一一 1 . 2文本分类的研究现状 国 外 对于 文 本自 动 分 类的 研究 开 展 得较 早， 2 0 世纪5 0 年 代 末， h . p . l u h n 对 文 本自 动 分 类 进 行 了 开 创 性 的 研 究 ， 将 词 频 统 计 思 想 应 用 于自 动 分 类 cs i 目 前， 文 本自 动 分 类己 广 泛 地 应 用 于 电 子 邮 件 分 类、 电 子 会 议 、 数 字 图 书 馆 搜索引擎、信息检索等方面。 文本自 动分类主要经历了四个发展阶段: 第 一 阶 段( 1 9 5 8 - 1 9 6 4 ) : 研究 文 本自 动 分 类 的 可 能 性; 第 二 阶 段( 1 9 6 5 - 1 9 7 4 ) : 进 入 文 本自 动 分 类 的 实 验 性 阶 段 ; 第 三 阶 段( 1 9 7 5 - 1 9 9 8 ) : 文 本自 动 分 类的 实 用 性 阶 段 ; 第四 阶 段( 1 9 9 0 至 今) : 因 特网 文本自 动分 类 研究 阶 段。 国 外 较早的 文 本自 动 分 类 应用 系 统 有卡内 基 集团 为 路 透社 开 发的 c h r u c h 9 5 系 统 ， 它能 对 路 透 社 成 千 上 万的 稿 件 进 行自 动 分 类 ; 德 国o ld e n b u r g 大 学 一 个 研 究 项 目g e r h a r d 6; 欧 洲 资 助 的 项 目 研 究d e s i r e ; 搜 索 引 擎 c o r a ， 其目 标 是 获 取 计 算 机 科 学 方 面 的 研 究 论 文 ， 对 于 部 分 从 网 上 采 集 的 p s 格 式 的 论 文 ， 可 用 关 键 词 来 进 行 检 索 ， p s 格 式 的 论 文 通 过 概 率 统 计 技 术 被自 动 根 据 标 题 来 分 类 ， 论 文 的 题目 、 作 者 等 采 用 隐 马 尔 可 夫 模 型 来 抽 取 。 国 内 对 于 文 本自 动 分 类 的 研 究 起 步 较 晚 ， 1 9 8 1 年 ， 候 汉 清 教 授 对 于 计 算 机 在 文 本 分 类 工 作 中 的 应 用 做 了 探 讨 。 此 后 ， 我 国 陆 续 研 制 了 一 批 计 算 机 辅 助 分 类 系 统 和自 动 分 类 系 统 。 南 京 大 学 的 邹 涛 等 人 运 用 了 v s m ( v e c t o r s p a c e m o d e l ) 设 计 了 一 个 中 文 文 档自 动 分 类 系 统c t d c s ， 封 闭 性 测 试 最 好 ， 准 确 率 有1 0 0 % ， 查 全 率 有9 3 % ， 开 放 性 测 试 的 结 果 ， 查 全 率9 6 % ， 准 确 率9 9 % . 中 科 院 计 算 所 的 李 晓 黎 、 史 忠 植 等 人 应 用 概 念 推 理 网 进 行 文 本 分 类 81 e 中 科 大 的 范 众 等 人 在k n n , b a y e s 和 文 档 相 似 性 研 究 的 基 础 上 提 出 了 一 个 超 文 本 协 调 分 类 器 91， 主 要 特 色 是 适 当 考 虑 了 h t m l 文 本 中 的 结 构 化 信 息 ， 并 且 将 文 本 分 类 器 和 超 文 本 结 构 信 息 分 类 器 结 合 起 来 ， 从 而 达 到 更 好 的 效 果 。 复 旦 大 学 的 周 水 庚 等 人 用 了 。 - g r a m 方 法 对 中 文 文 本 进 行 分 类 尝 试 10， 从 文 档 中 提 取 n - g r a m 属 性 ， 然 后 用 o n 方 法 判 别 文 本 类 别 ， 摆 脱 了 对 词 典 和 切 词 处 理 的 依 赖 ， 实 现 文 本 分 类 的 领 域 无 关 性 和 时 间 无 关 性 。 新 加 坡 h w e e t o u n g 等 人 研 究 了 用p e r c e p tr o n le a rn in g 树 状 结 构 进 行 文 本 分 类 n n 中 国 农 业 大 学 的 陶 兰 一 一 一 一 兽a z 1y 些if t !* 4:ly ; 等 人 用k o h o n e n 网 络 设 计了 文 本自 动 分 类 系 统 工i t c 9 8 1“ 1 , 它 是 一 种自 适 应 的神经网络。 文 本自 动 分 类问 题 最 初 是 应 信 息 检 索的 需 求 而出 现的 ， 在 早 期 的 研 究中 ， 主 要 采 用 信 息 检 索 技 术中 经 典 的 布 尔 模 型 对 文 本 进 行 分 类， 随 着 计 算 机 运 算 速 度的 不 断 提高 和存 贮空 间 的 不 断 扩 大， 文 本 分 类 技 术 又引 起了 较多 的 重 视 并 有 了 新 的 发 展 ， 尤 其 在 最 近1 0 年 中 ， 随 着 对自 然 语 言 处 理 及 人 工 智 能 技 术 的 研 究日 渐 深 入， 曾 经 一 度 被 当 作 信 息 检 索问 题 进 行 研 究 的 文 本自 动 分 类问 题 正 越 来 越 被 视 为 模 式 识 别 的 一 个 特 例 进 行 研 究 。 在 近 期 的 研 究 中 ， 较 为 常 用 的 研 究 方 法 是 采 用 基 于 统 计 的 方 法 抽 取 关 键 词( 文 本 特 征 )， 运 用 信 息 检 索 中 的 计 算 模 型 进 行 特 征 加 权， 采 用 模 式 识 别 学 习 算 法 进 行 类 别 学 习 。 当 然 还 有其它技术方法，这里不一一叙述。 1 . 3支持向量机的研究现状 s v m是在统计学习理论基础上构造的一种通用学习机器。 作为s v m的 奠基者前苏联数学家v v a p n i k 早在上世纪6 0 年代就开始了 统计学习 理论的 研究。 事实上， 早在2 0 世纪7 0 年代初， v a p n i k 就己 经给出了 经验风险和期望 风险关系的定量刻画，奠定了小样本统计学的理论基础，但这时并没有引起 人们的注意。 统计学习 理论是一 种新理 论， 真正引 起人们的 注意是1 9 9 5 年， 文 献 1 3 的出现是统计学习理论走向成熟和得到正式承认的标记。目前，一般认为统 计学习理论是神经网络的最新进展。 由于 s v m 算法的潜在应用价值，吸引了国际上众多的知名学者，近几 年出现了 许多发展和改进的 s v m 算法。如文献 1 4 - 1 6 所述。另外，s m o l a 在他的博士论文中详细研究了s v m算法中各种核的机理和应用。 s v m方法在理论上具有突出的优势， 贝尔实验室率先在美国邮政手写数 字库识别研究方面应用s v m方法取得了较大的成功10 1 。 在随后的几年内， 有 关 s v m 的应用研究得到了 很多领域的学者的重视， 在人脸检测、 验证和识 别、说话人/ 语音识别、文字/ 手写体识别 3 、图像处理及其它应用研究等方 一二二 垫 垦 夔 叁 鲤 廷 掣 丝 二 一 一 一 一 面取得了大量的研究成果。 ( 1 )人脸检测、验证和识别 o s u n a l“ 嚷早 将s v m应 用 于 人 脸 检 测， 并 取 得了 较 好的 效 果。 其方 法是 直 接 训 练 非 线 性s v m分 类 器 完 成 人 脸 与 非 人 脸 的 分 类 。 由 于s v m的 训 练 需 要 大 量 的 存 储 空 间 ， 并 且 非 线 性s v m分 类 器 需 要 较 多 的 支 持 向 量 ， 速 度 很 慢。 为 此， 马 勇 等 【19i提出 了 一 种 层 次 型 结 构 的s v m分 类 器， 它由 一 个 线 性 s v m组 合 和 一 个 非 线 性s v m组 成 。 大 量 实 验 结 果 表 明 这 种 方 法 不 仅 具 有 较 高的 检 测 率和 较低的 误检 率， 而 且 具 有 较 快的 速 度。 ( 2 )说话人/ 语音识别 说 话 人 识 别 属 于 连 续 输 入 信 号 的 分 类 问 题 ， s v m是 一 个 很 好 的 分 类 器 ， 但 不 适 合 处 理 连 续 输 入 的 样 本 。 为 此 ， 忻 栋 等 20 引入 隐 式 马 尔 可 夫 模 型h m m , 建 立 了s v m和h m m的 混 合 模 型 。 为 了 方 便 与h a m 组 成 混 合 模 型 ， 首 先 将s v m的 输 出 形 式 改 为 概 率 输 出 。 实 验 中 使 用y o h o 数 据 库 ， 特 征 提 取 采 用1 2 阶 的 线 性 预 测 系 数 分 析 及 其 微 分 ， 组 成2 4 维 的 特 征 向 量 。 实 验 表 明 h m m和s v m的结合达到了 很好的效果。 ( 3 )文字/ 手写体识别 贝 尔 实 验 室 对 美 国 邮 政 手 写 数 字 库 进 行 的 实 验 ， 人 工 识 别 平 均 错 误 率 是 2 .5 % ， 专门 针 对 该 特 定问 题 设 计 的5 层 神 经网 络 错 误 率 为5 . 1 %( 其中 利 用 了 大 量 先 验 知 识 ) ， 而 用3 种s v m方 法( 采 用3 种 核 函 数 ) 得 到 的 错 误 率 分 别 为4 .0 % , 4 . 1 % 和4 .2 % ， 而 且 是 直 接 采 用1 6 x 1 6 的 字 符 点 阵 作 为 输 入 ， 表明了s v m的优越性能。 ( 4 )图像处理 图 像 过 滤 : 一 般 的 互 联 网 色 情 图 像 过 滤 软 件 主 要 采 用 网 址 库 的 形 式 来 封 锁 色 情 网 址 或 采 用 人 工 智 能 方 法 对 接 收 到 的 中 、 英 文 信 息 进 行 分 析 甄 别 段 立 娟 提 出 一 种 多 层 次 特 定 类 型 图 像 过 滤 法 ， 即 以 综 合 肤 色 模 型 检 验 ， s v m分 类 和 最 近 邻 方 法 校 验 的 多 层 次 图 像 处 理 框 架 ， 达 到8 5 % 以 上 的 准 确 率 图 像 分 类 和 检 索 : 由 于 计 算 机 自 动 抽 取 的 图 像 特 征 和 人 所 理 解 的 语 义 间 存 在 巨 大 的 差 距 ， 图 像 检 索 结 果 难 以 令 人 满 意 张 磊 等 以s v m为 分 类 器 ， 在 每 次 反 馈 中 对 用 户 标 记 的 正 例 和 反 例 样 本 进 行 学 习 ， 并 根 据 学 习 所 得 的 模 型 进 行 检 索 ， 实 验 表 明 : 在 有 限 训 练 样 本 情 况 下 具 有 良 好 的 泛 化 能 力 。 哈尔滨工程大学硕士学位论文 ( 5 ) 其它研究 由于 s v m 的优越性，其应用研究目前开展己经相当广泛。陈光英等(2 1 1 设计并实现了一种基于 s v m 分类器的网络入侵检测系统。它收集并计算除 服务器端口之外t c p / i p的流量特征，使用s v m算法进行分类，从而识别 出该连接的服务类型， 通过与该连接服务器端口 所表明服务类型的比较，检 测出异常的t c p 连接。 李晓黎等2 2 1提出了一种将s v m与无监督聚类相结合 的新分类算法，并应用于网页分类问题。该算法首先利用无监督聚类分别对 训练集中正例和反例聚类， 然后挑选一些例子训练s v m并获得基于s v m分 类器。 近年来， s v m在工程实践、 化学化工等方面也取得了很多有益的应用 研究成果，其应用领域日趋广泛。 1 . 4本文的组织结构 本文认真研究分析了 s v m 在文本分类中的基本原理和一般方法，对 s v m分类和文本分类的定义、 相关技术以 及国内外研究现状进行了认真地归 纳总结， 并在此基础上实现了一个基于s v m的文本分类器， 对s v m在文本 自 动分类中的应用效果、优缺点进行了 研究。本文的整体结构如下: 首先是绪论， 概括性的分析了文本分类的研究现状、 s v m的研究状况和 研究内容。 接着分析了文本分类的基本概念和方法;然后主要分析了文本分类的过 程，文本的表示，特征项的提取:重点分析研究了文本的特征表示与特征提 取技术和文本的分类算法。 其次是统计学习理论概述，主要分析研究统计学习理论研究内容:经验 风险最小化， v c维，结构风险最小化，学习过程的一致性。 然后是研究s v m的主要研究内容: s v m的主要理论基础， s v m的训练 算 法和分类算法。 并分析研究了 关于s v m理论的 研究与应用， s v m的 多类 分类问 题。同时指出对s v m进一步研究和应用需要解决的一些重要问 题。 最后分析研究了一个基于s v m 的文本分类器。分析了分类器的总体模 型、设计思想及实现。 并以系统中的多类分类为例，并结合实验加以 验证。 哈尔滨工程大学硕士学位论文 第2 章文本分类系统的研究 2 . 1文本分类概述 文本分类是指在给定分类体系下，根据文本内容自动确定文本类别的过 程。2 0 世纪9 0 年代以前，占主导地位的文本分类方法一直是基于知识工程的 分类方法，即由专业人员手工进行分类。人工分类非常费时，效率过低。9 0 年代以 来，众多的统计方法和机器学习方法应用于自 动文本分类。目 前英文 自 动分类己 经取得了丰硕的成果，提出了多种成熟的分类方法，如最近邻分 类、贝叶斯分类、d t 方法以及基于s v m. v s m、回归模型和神经网络等方 法。目 前国内中 文文本分类研究主要集中 在朴素贝叶斯2 3 1 ( n a i v e b a y e s , 简称n b )、 v s m + “ 和s v m i i等技术上。本章将讨论各种文本分类技术。 2 . 2文本分类的任务 简单地说文本分类系统的任务是: 在给定的分类体系下，根据文本的内 容自 动地确定文本关联的类别。从数学角度来看:文本分类是一个映射的过 程，它将未标明类别的文本映射到已有的类别中，用数学公式表示如下: f : a -) b 在上式中: a为待分类的文本集合， b为分类体系中的类别集合。 2 . 3文本分类的过程 2 . 3 . 1文本分类过程概述 文本的自 动分类是一种典型的有教师的机器学习问 题，一般分为训练和 分类两个阶段，系统流程如图2 . 1 和图2 .2 所示。 哈尔滨工程大学硕士学位论文 训练文本i 耸) i预处理特征提取 片之 ! 训绷 构造分类器 图2 . 1 文本分类的训练阶段 分类文本 阵军 洲预处理特征提取 r = : : i 分类运算/ 输出类别 图2 2文本分类的分类阶段 下面对每一个阶段进行详细的说明。 2 . 3 . 2文本的表示 文本特征指的是关于文本的元数据，分为描述性特征:如文本的名称、 日期、大小、类型等，以及语义性特征:如文本的作者、机构、标题、内容 等。描述性特征易于获得，而语义性特征较难得到。 对于内容这个难以表示的特征，作者首先要找到一种能被计算机所处理 的表示方法。 根据“ 贝叶斯假设” ， 假定组成文本的字或词在确定文本类别的 作用上相互独立， 这样， 就可以使用文本中出现的字或词的集合来代替文本， 不言而喻，这将丢失大量关于文章内容的信息，但是这种假设可以 使文本的 表示和处理形式化， 并且可以在文本分类中取得较好的效果。 v s m是近年来 应用较多且效果较好的方法之一z b , v s m采用简洁的特征矢量来表示文档， 在进行特征提取时， 不使用大量 的句法语法信息，也无需对文档进行复杂的自然语言处理和语义处理， 在 v s m中， 文档空间被看作是由一组正交特征矢量所形成的矢量空间， 每个文 档d 被看作是矢量空间中的一点，表示为矢量空间中的一个矢量: v ( d ) = ( ( t , , w , ) ,( t 2 ,w 2 ) , . , ( t ,w ) ) ( 2 - 1 ) 其中i = 1 , 2 , . . ., n , t ; 为特征项， w 、 为t ; 在d 中的权值。 可以 将d中的字或词作为t ; ，也可以 要求t . 是d中出现的短语，从而提高内 容表示的准确性。 w ; 一般定义为t ， 在d 中出现频率t f ; 的函数，即 w i = y , ( t f ) ( 2 - 2 ) 那么选取什么作为特征项呢，一 般可以 选择字、词或词组， 根据实验结 果，普遍认为选取词作为特征项要优于字和词组，因此，要将文本表示为向 哈尔滨工程大学硕士学位论文 量空间中的一个向量，就首先要将文本分词，由 这些词作为向 量的维数来表 示文本， 最初的向量表示完全是a l 形式，即，如果文本中出现了该词，那 么文本向量的该维为1 ， 否则为0 。 这种方法无法体现这个词在文本中的作用 程度，所以逐渐0 . 1 被更精确的词频代替，词频分为绝对词频和相对词频， 绝对词频，即使用词在文本中出现的频率表示文本，相对词频为归一化的词 频， 其计算方法主要运用t f - i d f 公式，目 前存在多种t f - i d f 公式， 本文采 用了一种比 较普遍的t f - i d f 公式 m l w( t , d ) = tf ( t , d ) x 1 0 9 2 ( n/ n , + 0 .0 1 ) ( 2 - 3 ) y-二 、 tf ( t , d ) x 10 9 2 (n / n , + 0 .0 1) 2 其 中 ， w ( t , 句为 词t 在 文 本d 中 的 权 重 ， 而 tf ( t , d ) 为 词t 在 文 本d 中 的 词 频 ， n为训练文本的总数， n t 为训练文本集中出 现t 的文本数，分母为归一化因 子。 另外还存在其它的t f - i d f公式，例如: w( t , d ) = ( i + l o g , tf ( t , d ) ) x 1 0 9 2 ( n / n , ) ( 2 - 4) 艺 e a ( 1 + 10 9 2 tf ( t , d ) ) x 10 9 2 ( n / n , ) z 该公式中参数的含义与上式相同。 文本经过分词程序分词后，首先去除停用词， 合并数字和人名等词汇， 然后统计词频，最终表示为上式描述的向 量。 2 . 3 . 3文本特征项的提取 根据 j o h n p i e r r e的理论g a l ，用来表示文本的特征理论上应具有如下特 点: ( 1 )数量上尽量少 ( 2 )出现频率适中 ( 3 ) 冗余少 ( 4 )噪音少 哈尔滨工程大学硕士学位论文 ( 5 )与其所属类别语义相关 ( 6 )含义尽量明确 就文本来说， 最方便采用的特征就是词或短语， 它们具有如下一些特点: 数量众多、出现频率不等、噪音多、与其所属类别不一定相关。 特征提取正是解决这个问题的方案，从文本中得到的初始特征集可以简 单的被分为有用特征集和无用特征集两部分，特征提取的目的就是尽量的保 留有用特征，剔除无用特征，它通常会采用某种标准对特征的重要性进行评 价，之后只要保留重要程度较高的特征即可，特征提取的好处有二: ( 1 )提高分类效率，因为无用特征被剔除使得特征集得到压缩; ( 2 )提高分类精度，因为减少了无用特征对于分类结果的干扰。 下面分析己有的常见特征提取算法，它们相互间的不同之处主要在于不 同的特征重要性评价方法。 ( l ) i g特征提取 i g + “ ( i n f o r m a t i o n g a i n )即 信息 赢 取， i g 值代表了 特征 在v il 练集上的 分 布情况，它通过统计特征在各个类别中的出现次数来计算，公式如下: g ( t ) 一艺 几 , p ( c ,) io g p ( c ,) + p ,( i ) 艺 “ p , ( c l t ) lo g p, ( c , it ) + ( 2 - 5) p , ( t ) 艺 几 , p ( c , t ) lo g p ,( c , it ) 其中 t 代表特征， c 代表第 i 个类别， m 为类别数， p : 代表概率。 i g值越 高表示该特征在训练集中的类别上分布越集中。 i g方法提取i g值较高的特 征，其基本思想为分布越集中的特征越重要。 ( 2 ) mi 特征提取 m1 11 1 ( mu t u a l i n f o r m a t i o n )互信息值，它通过计算特征和类别之间的相 关性来完成提取。计算公式为: p ( t a c ) 1 ( t , c ) = l o g丁万 片l t ) x 片气 c ) ( 2 - 6 ) 其中 t 代表特征， 。 代表类别，为方便计算，简化为: 哈尔滨工程大学硕士学位论文 axn i k r , c 1 =l o g-长丁 -丁 下，下二 t 左+t1 x又 a + i s ) ( 2 - 7 ) 其中 n 为训练集中包含的文本总数，a为 t 与 c同时出现的次数， b为 t 出现而c 不出现的次数， c为 c出现而 t 不出现的次数。 通过该公式就可 以取得特征与各类别间的互信息值。 为了能取得特征在数据集上的整体评价， 有以下两种计算方法: 1 _ r ( t ) 二 艺p ( j i ( t , , ) ( 2 - 9 ) i . - ( t ) = 艺 i ( t ) ( 2 - 9 ) 前者代表了特征和各类别的平均互信息值，后者则取特征与各类别互信息值 中的最大值。m i 方法提取互信息值较高的特征，其基本思想为与类别相关 性越高的特征越重要。 ( 3 ) c h i 特征提取 c h i “ 具有和 m i 方法基本相似的思想，同样通过计算特征 t 和类别 c 间的依赖程度来完成提取。 但二者的计算细节不同 ， c h i 作了更多地考虑。 有种看法认为 c h i是一种正规化 了的mi , c h i的计算公式如下: c h i ( t , c ) m x ( a d 一 c b ) z ( a + c ) x ( b + d ) x ( a + b ) x ( c+ d ) ( 2 - 1 0 ) 其中 n 出现而 为训练集中包含的文本总数， a为 t 与 c同时出现的次数， b为 t 现的次数 体评价: 未出现的次数， c为 c出现而 t未出现的次数， d为二者都未出 。 与mi 相同， c h i 也有平均值和最大值两种方法来取得特征的整 c h i , , ( t ) = 艺p , ( c ) c h i ( t , c ) ( 2 - 1 1 ) c h i . . ( t ) = 艺m a x c h i ( t , c ; ) ( 2 - 1 2) 方法的基本思想也是与类别关系越紧密的特征重要性越高。 d f 特征提取 ( d o c u m e n t f r e q u e n c y )即文档频率， 1 0 指训练集中包含该特征的文 哈尔滨工程大学硕士学位论文 本总数，所谓文本包含特征是指这个特征在该文本中出 现，忽略其在文本中 的出现次数。d f方法提取 d f值较高的特征，它的目的是去掉在训练集上 出 现次数过少的特征， 保留出现达到一定次数，具有一定影响力的特征。 2 . 4文本的分类算法 文本分类方法有很多，如图2 . 3 所示。 图2 .3自 动文档分类算法 大多数的文本分类研究都趋向于二分问 题，即一个文本与预先确定的主 题要么相关， 要么不相关。 然而现实中大量的文本都是由不同的主题组成的， 这样就提出了文本多类别分类问题。 定义2 . 1 : 设d、 ， d 2 .d n , d n 表示第 n 个文本训练集; d = d , . . . d , 表示 训练文本向 量;c , . . . c表示文本的类别; n:表示训练集中 类c , 的样本个数。 2 . 4 . 1 r o c c h i o 算法 r o c c h i o e“ 是情报检索领域最经典的算法。在算法中，首先为每一个类c 建立一个原型向量 ( 即训练集中c 类的所有样本的平均向量)，然后通过计 算文档向量d 与每一个原型向量的距离来给d 分类。 可以 通过点积或者j a c c a r d 近似来计算这个距离。这种方法学习速度非常快。 1 1 哈尔滨工程大学硕士学位论文 2 . 4 . 2朴素贝叶斯分类 n b 分类器四 利用下列贝叶斯公式通过类别的先验概率和词的分布来计 算未知文本属于某一类别的概率: p ( c , d ) = p ( c , ) p ( d i c ) ( 2 - 1 3 ) p ( d ) 其 中 ，p ( c , i d ) 为 样 本 d 属 于 类 c的 概 率， p ( d i c , ) 为 类 c中 含 有 样 本 d 的 概 率。 在 所 有p ( c , i d ) ( i 一 1 , 2 , . ., m ) 中 ， 若p ( c , i d ) 值 最 大 ， 则 文 本 d 归 为 c ti 类。 由 于 p ( d ) 是 常 数， 因 此 将 要 求 解p ( c , i d ) 的 问 题 转 换 为 只 要 求 解 p ( c g ) p ( d lc j ) e 假 设 文 本 中 词 的 分 布 是 条 件 独 立 的 ， 则 p ( c , i d ) = p ( c , ) p ( d i c ) = p ( c , ) rlp ( d , i c j ) ( 2 - 1 4) 其中， p ( c ; ) = c ,中 文 本 个 数 总文本个数 , p ( 风 c , ) = d ;在 类 c j 中 出 现 的 次 数 c 中 所 有 词 的 个 数 ( 2 - 1 5 ) 尽管词的分布是条件独立的，这个假设在实际文本中是不成立的，但在实际 应用中n b 分类器一般都能取得相对较好的结果。 2 . 4 . 3 k 一 近邻算法 k n n f3 z ?方法是一种基于实例的文本分类方法。首先，对于一个待分类文 本，计算它与训练样本集中每个文本的文本相似度，根据文本相似度找出k 个最相似的训练文本。这最相似的k 个文本按其和待分类文本的相似度高低 对类别予以加权平均，从而预测待分类文本的类别。文本向量d 属于类别c ; 的权值w mi d )由式 ( 2 - 1 6 ) 计算。 权值越高， 认为文本向 量d 属于类别c ; 的概率越高: w ( c , i d ) 二 艺s ( d , d j ) p ( c d ) ( 2 - 1 6 ) 其 中 ， s ( d , d , ) 是向 量 之间 的 余 弦 相 似 度; d d z , d ,是 训 练 集中 与 d 余 弦 哈尔滨工程大学硕士学位论文 相 似 度 最 大 的 k 个 文 本 向 量 : 而p ( c , i 几 ) ， 当 d ， 属 于 类 别 c ; 时 为 i ， 否 则 为 0 a 通过上面的分析可知， k n n的实质就是以特征属性权值作为特征空间的坐标 系测度，先计算测试集与训练集之间在该坐标系中的余弦距离，然后根据测 试集与训练集的距离远近来确定类别。 2 . 4 . 4决策树分类 d t 是一种常用数据分类技术，同样适用于文本分类。 d t 的建立算法有 多种， 包括: 基于信息增益的启发式算法i d 3 ; 基于信息增益率的解决连续属 j性分类的算法c 4 ;基于g i n i 系数的算法c a r t ;针对大样本集的可伸缩算法 s l i q ;可并行化算法s p r i n t : 将建树和剪枝集成到一 起的 算法p b u l i c o 2 . 4 . 5支持向量机方法 s v mi“ l方法适合大样本集的分类，特别是文本分类， 它将降维和分类结 合在一起。s v m算法基于结构风险最小化原理，将原始数据集合压缩到支持 向量集合，然后用子集学习得到新知识，同时也给出由这些支持向量决定的 规则。并且可得到学习错误的概率上界。假设线性分类面的形式为: g ( d ) = w. d+ b =o ( 2 - 1 7 ) 其中c o 为分类面的权系数向 量， b 为分 类阐值， 可用任一支持向量求得， 或者 通过两类中任一对支持向量取中值求得。将判别函数归一化，使得所有样本 都 满足 g ( d ) j= 1 ， 即y j ( co d ) + b - 1 z o , i = 1 , 2 , . ,n , y 是样 本的 类别 标记即当 样本属于类c 时y i一 l ，否则y i =-1 ; d ;是相应的 样本。 这样样本的分类间隔 就等于2 1 1 1 w 日 ， 设计的目 标就是要使 得这个间隔 值最小。 据此定 义 l a g r a n g e 函数: l (to ,b ,a ) = i (to .0.)，一 擎y ,co -d ;+ h一 ， ( 2 - 1 8 ) 其中为a ; 0 为l a g r a n g e 乘数， 对w 和 b 求 偏微分并令其为 。 ， 原问 题转换 成如 下 对 偶 问 题 : 在 约 束 条 件 艺y ,a ; = o , a ; 0 , i 一 1 , 2 , ., 。 下 对 a ; 求 解 下 列 函 数 的 哈尔滨工程大学硕士学位论文 最大值: q (a ) = i s ，一 告 名 a ;a iy ;y ,(d d ,) ( 2 - 1 9) 如果a , 为最优解，再由 公式 。 = 艺a .: x y d ( 2 - 2 0 ) 得出最优分类面的权系数向量。为了判断某个样本是否属于类c ，计算如下 最优分类函数: f ( d ) = s ig n ( o ) - d ) + b 卜s ig n 艺a ; * y ; ( d ; - d ) + b * ( 2 - 2 1 ) 若f ( d ) = 1 ， d 就属于该类; 否则就不属于该 类。 对于 线性不可分的 情况， 可 以引入松弛因子，在求最优解的限制条件中加入对松弛因子的惩罚函数。 2 . 4 . 6基干投票的方法 在研究多分类器组合时提出了 投票算法， 其核心思想是: k