（计算机应用技术专业论文）基于rough集的web文本分类及其信息抽取研究.pdf

abs tr act 丁 七 e w e b is a huger e pos i t o ryofi n fo n u a t i o n and th e r e is a need for ca t e g oriz in g web pages tofacil l tate the in d e x i n g ， se ar chand r e 幼 e v a l ofpag es. rou g h 喊 小 印叮加 t r odu c edine ar l yl9 80.s isa fo n 力 alm a th e m at i c ait o o l to 切 ， t vag u e and unce 到 刀 i n kno wledge. inr o u ghsetthe0 ryb a se d p r a c t i cal app 1 i c at i o ns， 曲yprel l m 如 印 李of add l t l o 钊 all 创 沁 rmat l on a bout d a laisneeded， 即d代 a dab le deci si on ru le sare e as ily i n d u c t ed 嫩thl com p u tatl o nal c o m p l e x i ty . ithas 扛 肠 e ady beenapp l i edtoa v e ry嫩dev 州e 钾ofdo幻 。 a u o 5 . ihthis p al 姆 r，we di s cus s s e v e ra 1 1 s s u e s re 1 at edtoa u t o m atedt e x t cl assi fi c a t i on o f w e b p 昭e s . w 七 di s cus s th e p 找 沁 e s s o f t e xtc l as s i fi c ationo f w e b p age s and a n a 1 y 邓 企 滋 世 e sse 1 ecti on andc ategori zat 1 on al gor i th m sof w e bpagesandgive， o r n e 即g g e st i o nsfor w e bp age s c ateg o ri zat 1 o n . w七 i nve st i g ate the e 月 七 c t l v e n e s s o f the r o u g h set se l ectio n o n web te xtcl as si fi c a t 1 o n an d p r o posea new fe a n 双 e re d uctio n m e t h o d b ased o n the rou gh set th e o ry wi t h the ncwfe a to r e re d u c t l o n m etho d ， we c a n al s o get the key w o r d s o f sor n e o nec 咖9 o ryand t h e l r si gni fi c anc e. k e yw七 rd鱿 叭 触 bt e x tcl ass伍c a t i o n ; rou gh se t ; 介 a 奴 甘 e 访化r n l a ti o n 学位论文独创性声明 学位论文独创性声明 本人声明所呈交的学位论文是本人在导 师指导 下进行的研究工作及取得的 研究成果。 据我所知，除了 文中特别加以标注和致谢的地方外，论文中不包含 其他人已 经发 表或撰写 过的 研究成果， 也不包 含为 获得南昌大李 或其他教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的 任何 贡献均已在论文中作了明确的说明并表示谢意。 学 位 论 文 作 者 签 “ 手 “ 叫伽 签 字 日 期 : ， 。口 年 ” 7 日 学位论文版权使用授权书 本学 位论文作者 完 全了 解 南昌大李 有关保留 、 使用学位论文的 规定， 有权保留 并向国家有关部门 或机构送交论文的复印件和磁盘，允许论文被查阅 和借阅. 本人授权南昌大学可以 将学位论文的 全部或部 分内 容编入有关数 据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学 位 论 文 作 者 签 “ 手 “ : 可 你 导师签名 ( 手写):柳达 签 字 日 期 : 、 矜 乙 月 / 宁 日 签字日期: 渐 一产 月 / 分 日 学位论文作者毕业后去向: 工 作 单 位 : 沁 叫砖 大 等 通 讯 地 址 : 1 叫衫 心体 瓦 协 ， 尽 凡 电 话 : ， 了 名 7 知 势 邮 编 :3 3 0 0 侈 第1 章引言 第1 章 引言 l l问题的描述 当 前网 络正在深度和 广度方 面飞 速发展， 加 t 。 刀 e t 也正 在前所未 有地改 变着 我们的生活。 虽然加吻 m 以上包含了 大量的信息资源， 但其所具有的开放性、 动 态性和异构性使得网 络上的资 源分布较分散，且无统一的管理和结构， 这就大 大降 低了 人们对信息资源的 利用效率，导致了 信息获取的困 难。 如何在这些大 量、异构的 海量信息资源中，快速有效的发掘蕴含具有巨 大潜在价值的知识和 信息， 合理分类及准确地定位所需信息， 同时过滤大量无用的或不相关的内 容， 是当今信息发展和信息处理领域的主流技术。 数据挖掘可以 帮助我们从大量原始数据中 挖掘出隐含的、有用的尚 未发现 的 信息和知识，有效解决信息丰富而知识贫乏的问 题。数据挖掘的绝大部分工 作涉及的是结构化数据库， 而节 几 b 文本信息大部分是非结构化或半结构化的 文 本信息. 因此，基于m 触 b 文本信息的挖掘作为数据挖掘的一个新主题， 引起了 人们的极大兴趣。 分类是我们认识自 然的一种重要手段，在计算机出现之后，我们就开始借 助这一利器研究数据的自 动分类问 题。 从计算的观点看， 如果分类原则是事先 通过示例告诉计算机的， 那么计算机在示例基础上形成分类机制的过程就称为 有监督的 分类， 称为自 动分类问 题;如果事先没有任何示例， 全凭数据自 身在 某种角度上的相似性来分类，这时自 然就谈不上遵守既定分类体系的问 题，那 么这种分类过程就称为无监督的分类，也称为自 动聚类问 题。 聚类和分类都是 机器学习、 统计等领域关注的课题，随着相关研究的开展， 它们又被纳入所谓 “ 数据挖掘”的框架之下. 分类和聚类有着不同的实现过程.自 动分类先抽取 待分类文本的特征， 将之与各类别中 文本所具有的 共同 特征或一定的 分类标准、 分类参数进行比较，然后将待分类文本归为特征相近的类，并赋予相应的分类 号。 它一般分为训练和分类两个阶段. 训练阶段所用到的文本集合由 属于预先 定义好的 类别体系的 文本组成。 分类系统先通过训练文本集学习分类知识，然 后在测试阶段根据所学的知识为待分类文本确定一个或多个合适的类别， 例如 第 1 章引言 文本分流和信息过滤。 而自 动聚类首先从文本中 抽取有关特征，再根据一定的 法则或需要利用聚类算法将具有相同或相近特征的文本定义为一类，划分出的 类别是不确定的，要求同一类内文本的内容相似度尽可能大，而不同类别之间 的相似度尽可能小。 对于文本而言，其类别体系相对较明 确，并且一旦确定就 荃本不会再变化，主要依据应用领域或公众认可的 分类标准，因而很适于在给 定的 类别体系下确定其类别的分类方法。 本文所研究的节 陌 b 文本自 动分类就是 指在给定的类别体系下进行的分类。 web 文本分类是指在给定分类体系下， 根据v 触 b 文本内 容自 动确定文本类 别的过程。 2 0 世纪9 。 年代以 前，占主导地位的 文本分类方法一直是基于知识 工程的分类方法， 即由 专业人员手工进行分类。 人工分类非常费时， 效率过低。 90年代以 来，众多的统计方法和机器学习方法应用于自 动文本分类。 大多数w七 b 分类方法共同的特点是首先定义一些互斥的类别， 然后通过训 练样本对类别进行训练， 最后计算新v 几 b 文档与类别样本相似度把它归为与它 最相似的类。 1 .2研究背景和意义 随着计算机技术及其应用的迅速发展，网络上的文本资源在几年间呈现爆 炸式的 增长，网上庞大的数字化信息和人们获取所需信息能力间的矛盾日 益突 出。 一方面网络信息的激增增加了 对于快速、自 动文本分类的迫切需求，另一 方面又为基于数据挖掘技术的文本分类方法准备了充分的资源。 但现在的很多 系统，由 于对样本文档的数量要求较大，从而造成系统效率的下降，或是由 于 不能满足样本文档的数量，造成分类不全、 含义不清、 缺乏学习能力等问题。 研究有效的晒 几 b 文本分类就显得十分必要， 并且它在文本检索、 信息获取、 信 息过滤、数据组织和信息管理，以 及互联网上的搜索都有十分广泛的应用。文 本自 动分类是组织和管理文本信息的有力手段，可以在较大程度上解决信息杂 乱无章的问 题， 使用户更容易更准确地定位所需的信息，有效地提高 信息服务 的 质量tll . 所以 本课题具有重大的实际意义， 主要表现在以 下几个方面: ( 1) 文本分类为信息检索提供了良 好的文本集的组织与结构， 极大简化了 在文本信息库中存取文本的操作， 也为信息检索提供了更高效的 搜索 策略和更准确的查询结果。 (2) 互联网上的在线文本信息急剧增加， 手工分类和处理这些信息不但耗 第 1 章 引言 费大量的人力和物力，在速度和精度方面也远远不能满足用户的要 求。 文本自 动分类及相关技术的应用可以帮助用户有效收集和选择其 所感兴趣的文本信息， 尤其是帮助用户在日 益增多的 海量信息中发现 新的概念并自 动分析它们之间的关系，真正做到信息处理的自 动化。 ( 3 ) 将快速精细的 分类技术与包过滤技术有机地结合， 能有效地防止不健 康信息的侵入， 如文本分类在防火墙技术中的 应用。 同时， 也可减少 互联网上有害信息的流动。 (4) 文本分类是几乎是所有基于内容的文件管理的学科的基石， 是处理和 组织大规模文本信息的关键技术， 可以说研究文本分类有广泛的商业 前景和应用价值。 (5)分类技术可以 把用户分为对不同信息感兴趣的群体从而实现个性化 的信息服。 1 .3 国内外的现状及发展趋势 l 3. 1国外文本分类研究 到目 前，自 动分类在国外经历了三个发展阶段: 第一阶段( 1 9 58一 1 9 64)主要进行自 动分 类的 可行性 研究: 第二 阶段(1 9 6 5 一 19 74)进行自 动分 类的实 验研究: 第三阶段( 19 75一至今 ) 进入实 用化阶 段。 国 外的 文 本自 动分 类研究始于20世纪50年代末， h.p. l l ll l l l 首先将词频统 计思想用于自 动分类， 在该领域进行了开创性的 研究。 1 9 60年， m ar on在j o 切 m al 。 fa s m 上发表了有关自 动分类的第一篇论文( on rele v a n c e ， p r o b a b il i s t i c 加 d e x in g in fo n 力 a t l o . al r e tri e v a l ) ， 其后许多学者在这一领 域进行了 卓有成效的 研 究工作。 从20世纪60年代 直到20世纪50年代末， 这期间 最有效的 文 本分 类系 统 一直是由 专家人工构建的 基于知识工程技术的分类系统。 其典型应用就是卡内 基集团为路透社开发的co n s tl u e 系统， 它主要是由 专业人员编写了 一些分类规 则来指导分类， 在r e u t e r s 的部分语料库上它的效果非常好， 平均准确率和召回 率都可达到如%， 但是 在其它的 应用领域采用c 。 拙 仃 刀 e 系统将会耗费大量的人 力和物力。 第 1 章 引言 90年代初期， 基于机器学习 洲朗 h 匕 e learni n g ) 的 分类技术开始取 代基于知 识工程的方法成为文本分类的主流技术。这种算法通过归纳文本集的 特征自 动 创建一个分类器，这些文档集合事先由各领域专家人工地分类到类集 c 二 c l ， c z ， ” .， ck)的 各 个 类c 中 分 类 器 可 以 作 为 一 个 规 则 决 定 文 档妈 是 否 属 于 类q， 如果 类 集c 被 更 新， 或者 系统要应 用 于 其 它 不同的 领域， 只 需要 重新构 造一个人工分类文档集合， 通过机器学习，自 动地构造一个分类器， 显然，由 于这种分类方法不再需要知识工程师和领域专家的介入，节约了大量专家人力 资源，同时加快了分类系统的建立速度。 近年来， 研究者们结合机器学习方法和人工智能的技术进行了大胆的探索， 提出了多种分类模型和分类算法。如基于向 量空间模型的r occ hi 。分类器及其 一系列的改 进算法. 如支持向 量机方法(s u p po rtvector m ac hi n e ) ， k近 邻方 法 ( k n n ) 、 朴素贝叶 斯方法 困 v e b ay es ) 、 决策树 方 法( deci si ontr e e) 、 神经网 络 困e ur a l n et)等等。 这些方法在英文及欧洲 语种文 本自 动分 类上有广泛的 研究， 均取得了不错的效果.国外很多研究人员对英文文本分类领域的各个问题都有 相当深入的研究，对几种流行的方法进行了大量的对比研究。很多研究表明， k n n和s v m是英文文本分类中的最好方法， 还有一些研究人员研究表明结合 不同的 分类器能够提高分类的精度。 目 前，国外的自 动分类系统己经从最初的 可行性研究经历了实验研究进入 了实用化阶段，并在邮 件分类、电 子会议、信息过滤等方面得到了 较为广泛的 应用。 1994年， a t t 七 。 招 t e njo ac h l m s 等研究了基于支持向量机 的文本分类方法。 第 1 章 引言 1 3 .2国内文本分类研究 相对于国 外文本分类的发展水平，国内文本分类技术的 研究起步较晚， 研 究工作始于80年代初期。 1 981 年， 侯汉清先生首先对自 动分类进行探讨， 从计算机管理分类表、 计 算机分类检索、计算机自 动分类、机编分类表等四 个方面介绍了国外的发展概 况。 到目 前， 我国已 研制出一批辅助归类系统及自 动归 类系统， 例如: 1 9 84年， 莫少强研发了以 人工主题分析、 系统完成查表的辅助分类系统;1 9 86年， 上海 交通大学的 朱兰娟等开 发了 计算类归属度、 据b 叼 爬 5 最小损失原则确定 分类的 自 动分类系统:1 9 92年，同济大学计算机系的陈大访、陆皓等研制了以 产生式 系统、 人工定类为主要技术特点的自 动分类系统:1 994 年， 东北大学图书馆的 李欣、陈星研发了 基于联想抽词、 禁用词表、关系知识库、同义词典库的 专家 系统; 1 995 年， 清华大学电子工程系的吴军开发了以 语料相关系数作为分类依 据，字频、 词频及其常用搭配为补充、人工指导的自 动分类系统;1 997 年， 长 春地质学院图 书馆的 邓要武、王连俊等开发了以 分级知识库、产生式系统为技 术核心的正向 推理系统。同年，上海交通大学的王永成等研发了基于部件词典 技术、自 动分类用关键词分类归属表的自 动分类系统;1999年，中国 农业大学 的陶兰等人研制了 基于b p网 络的 文本分类系统:随后，中国 科学院 计算技术 研究所的 李晓黎等提出了 一种新的分类模型， 该模型在己有的英语语义词典及 大量训练集的基础上， 应用机器学习、数据挖掘等技术进行知识获取并最终形 成若干个概念推理网: 2 0 01年， 大连理工大学计算机科学系的林鸿飞给出了基 于示例的 文本标题分类机制。 加02年， 北京大学计算机系的王爱华等利用基于 信任函数的 信息综合方法对多个文本分类器进行组合使用。 2 0 03年，山 西大学 计算机科学系的 李钝在空间向 量模型的 基础上将文本聚类和r o u gh集理论的 属 性约简相结合，提出了一种新的文本分类方法。 虽然中英文之间存在着较大差异而无法直接照搬国外的研究成果，但是， 随着中文信息处理技术， 特别是中 文自 动分词技术的日 渐成熟，以 此为基础的 中文文本分类技术的研究得到了快速发展。 中文和英文文本的分类虽然有技术上的相似点， 但是由 于中文的博大精深， 因此国内 对中文文本的分类仍然有很多不足的地方，主要有以下五个方面: ( 1) 无标准的 分类测试文档集。 国内 还没有标准、 开放的分类测试文档集 可供使用， 而训练文档集应该能够广泛地代表分类系统所要处理的客 第 1 章引言 观存在的各个文档类中的文档。 一般地， 训练文档集应该是公认的经 人工分类的语料库。 国外文档研究都使用共同的测试文档库， 这样就 可以比较不同分类方法和系统的性能， 而就中文文档分类而言， 各研 究者使用自己 建立的训练文档库进行测试， 测试结果没有可比 性。 ( 2 ) 分类间无层次性. 现有文档分类系统基本上都是平面分类， 现有文档 分类系统基本上把文档类看成是互不相交的， 它们处在一个平面层次 上， 而实际上文档概念类别之间 存在层次关系， 即一 个大类往往包含 许多小类， 因此， 按照层次结构对文档库进行分类更能体现文档之间 的语义关系， 这就是层次化文档分类成为当前文档自 动分类研究的一 个热点问题的原因。 (3) 分类模型不完备。 文档预处理后生成的文本向量基本局限 在二维。目 前 ( 词或词组， 权值f) 这样一个二维元组是常用的文档模型，同时 为了减少计算量， 特征提取又删去了 一些信息( 其中有可能是非常重 要的) 。如何增加元组的表示维数， 例如词或词组、 权值f 位置信息， 建立一个更加完备的文档模型，是一个值得探讨的问题。 (4) 无通用的分词技术。现有文档分类技术基本上是基于词或词串信息， 在中文处理中称作分词。 就中文文档分类而言， 分词是一项非常复杂 的工作， 分类系统一般都比较复杂和庞大， 分词速度慢， 且准确度不 高， 因此， 研究无须词典支持、 领域独立的文本分类系统无疑具有重 要价值，这使得文档分类系统成为真正意义上的通用系统。 ( 5) 随着互联网和多媒体技术的进一步发展，文本分类技术将与图 像识 别、 语音识别技术相互融合， 比 如图 像文本的分类、 语音文本的 分类、 多媒体数据库索引等， 这也进一步要求文本分类技术在文本的处理方 法、克服噪音干扰、分类精度等方面有进一步的提高。 l 4 研究内容 r o u g h 集 理 论 件3 】是 八 十 年 代 初z. p awlak针 对q f ire ge的 边 界 域 思 想 提出 的， 用来研究不完整数据、不精确知识的 表达、学习和归纳等方法。把那些无 法确认的 个体都归于边界线区域， 这个区域被定义为上近似集和下近似集之差 集，由于上近似集和下近似集都可以 通过等价关系给出确定的数学描述， 所以 含糊元素数目 可以 被计算出 来， 从而真假二值之间的含糊程度可以 计算。 这套 方法与统计方法处理不确定问题时不同，它不是采用概率方法描述数据的不确 第 1 章 引言 定性;与这一领域传统的模糊集合论处理不精确数据的方法也不相同。用于分 类， 可以 发现不准确数据或噪声数据内 在的 结构联系:用于特征归约， 可以 识 别和删除 无助于给定训练数据分类的属性; 用于相关分析，可以 根据分类任务 评估每个属性的贡献或意义。 其主要思想是在保持分类能力不变的前提下， 通 过知识约简，导出问 题的 决策或分类规则。 文本分类目 标是在分析文本内 容的基础上， 给文本分配一个或多个比 较合 适的 类别， 从而提高文本检索、 文本存储等应用的处理效率。 节 触 b 分类， 尤其 是w e b 文本的 分类是v 触 b 挖掘的一个重要研究课题。 叭 触 b 分类是指按照一定的 类别体系对网页进行自 动标记， 对一个待识别网页予以 一个或多 个类别标识。 m 触 b 文本的分类，是文本分类的一种具体应用. 本文主要研究内容包括以下部分: ( 1) 研究机器学习在节 触 b 文本分类中的应用。 文本自 动分类研究已 有近五十年的历史，在不同的历史阶段产生了 不同的 研究方法。 本文主要研究基于机器学习的m 触 b 文本自 动分类技术，比较全面地 分析与之相关的各个问 题， 特别是v 触 b 文本表达方法、 常用机器学习方法的实 现原理及其优缺点。 (2)研究认 触 b 文本分具体过程和分类性能评价标准， 分析常用的分类方 法特点及性能。 文本分类自 动分类还离不开文档向量的构造，向量的分量与文档中的特征 项相对应。 这种向量通常高 达几千维甚至数万维， 计算量相当大，因此需要对 文档向量进行约简， 而传统的基于频率的阐值过滤法往往会导致有效信息的 丢 失，也影响了分类的准确度。 常见的文本分类方法有支持向 量机方法、 k近邻 方法、 朴素贝叶斯方法、 决策树方法等等。 朴素贝叶斯方法和k近邻方法无法 得到显式规则;决策树方法得到的规则 含有大量的冗余条件。 (3)基于r o u gh集理论的， 触 b 文本分类的研究。 r o u gh集理论用于分类有以 下 优点: 能 够获得分类所需的 最小 特征属性 集， 可以 在不影响分类精度的 条件下降 低特征向 量的维数，并可以得到最简洁的 显 式 表达的 分 类规则。以 往的r o u gh方法直 接将所有的向 量组成一个决策表， 造 成维数过大，运算起来非常困 难. 本文提出 一种新的属性约简方法 一- 同 类属 性约简，先将一些无关的属性约简掉， 然后再组成决策表，使得大量与分类无 关的 属性不参与分类学习， 极大减少了 运算量，加快分类训练的速度，同时也 不影响分类的效果。 (4)研究v 几 b 文本分类信息面临的问题。 第1 章引言 目 前认 范 b 文本分类技术得到了 快速发展， 但还面临很多问 题， 如标准数据 集，m 怂 b 文本的表达模型，分类体系中类别间的语意关系， 合理的性能评价标 准等。 1 .5本文的组织和结构 本文的内容安排如下:第一章简述本文选题的背景和意义，研究现状以及 本文研究的内 容;第二章综述研 怂 b 文本分类的定义、过程、特点和评价标准， 研究分析常 用的节 触 b 分类算法的 特点; 第三章概 述r o u gh集理论， 并 将其应用 到研 触 b 文本分类中; 第四 章研究rou g h 集理论在， 触 b 文本 分类中的 应用问 题， 重点讨论属性约简， 决策规则和规则匹配问题。 第五章总结分析全文研究成果， 并提出要进一步研究的问题。 1 .6本章小结 随着网络的不断发展，v 触 b 文本分类技术成为文本分类新的研究方向，也 是数据挖掘的重要研究问 题。 本章首先阐述了w 七 b 文本分类的必要性， 其次简 述了本文主要的研究内容，最后介绍了本文的内容结构。 第2 章 web 文本分类 第2 章 、 v 七 b 文本分类 2. i we b 文本分类的定义 简单地 讲， v 触 b 文 本分类就是运用 机器学习 伽咏划 山 . 助明 ” n g ， m l ) 、 知识 工程口 功 洲同g e e n g 口 e e n 必 9 ， 灯) 或其它方法来建 立 一个分类模型， 然 后利用这 个模型将未知类别的节 几 b 文本文档分类到一个或多个预定义的 类别中。 web 文 本 分 类 就 是 将 一 个 二 元 组 。 d ， c 映 射 到 一 个 布 尔 值 的 任 务. 其中d 是 所 讨 论 的 文 档的 集 合， c = c : ， 几 ，二 ， c ， 是 预 先 定 义 的 类 别的 集 合。 如 果 将 二 元 组 映 射 为 值t ( 加 . ) ， 则 认 为 文 档 灼属 于 类 别 乌 ， 否 则 认 为 文 档妈不 属 于 类 别 ， 更形式 化地说， 假设有个未知的目 标函 数沪 : d x c 峥 t ， f ) ， 这个函 数能 够 将任意一个 v 傀 b文本准确地分类，节 儿 b文本分类就是要找到一个函数 护 : d x c ，代月使 得 它的 结果 能 够 尽 可能 地 与护 接 近， 根据应用的需要可以给m 几 七 文本分类加以不同的约束。例如可能需要这样 一 个 分 类 器 ， 对 给 定 的 整 数k，每 个 文 档 妈。 d 需 要 分 类 到c 中 的k 个 不 同 的 类别中. 卜1 时，即一个文档只能分给一个类别， 这样的分类称为单类别分类， 而 如果一 个文档可以 分给c中的任意 个类 别， 这样的 分类称为多 类别分 类， 单 类 别 分 类 的 一 个 特 例 就 是 二 值 分 类 ， 即 对 任 意 一 个 文 档 呜。 d 要 么 属 于 类 别 c， ， 要 么 不 属 于 类 别 ， 雌时 属 于 类 别 c 的 补 集 可 ). 理论 上， 只需二值分 类( 同 时也是 单类别 分类) 就 可解决 所有分类的问 题。 这 是因为一个二值分类的算法也，可以用于多类别分类，只需将类别集合 c = 和 ， ， c z ， ，c 。 上 的 多 文 档 分 类 问 题 转 变 为 回 个 独 立 的 在 类 别 集 伪 ， 币上 的 二值分类问 题。 但是 这 样做的 前提条 件是c中的 各个 类别必须是随 机独立的， 第2 章 职 触 b 文本分类 即 对c 中 的 任 意 两 个 类 别 己 和 砂 ， 侧 妈 ， c)的 值 不 依 赖 于 似 妈 ， 砂 ) 的 值 ， 反 之 亦然。 然而反过来一个多类别分类的 算法不能够用于二值分类和单类别分类。 这 是 因 为 ， 给 定 一 个 待 分 类 文 档妈， 多 类 别 分 类 算 法 ， 可 能 将 其 分 类 到妙1 个 类别中，很难从这 k个类别中选择一个最合适的 类别来用于单类别分类。另外 多 类 别 分 类 可 能 根 本 就 没 有 将 呜 分 类 到 任 何 类 别 中 ， 这 时 也 很 难 从 类 别 集 合c 中 选 择 一 个 类 别 分 给呜 使 其 适 用 于 单 类 别 分 类 因 此 ， 可 以 将 类 别 集 合 c = c 1 ， c z ，: ， clc l 上 的 分 类 问 题 看 作 是 icl 个 独 立 的 二 值分类问题，为 c中的每一个类别c (i = 1 ，2，. . ， ic 卜 构造二值分类器 巾 ， : d斗 t ， f 。 2. 2 we b 分类的特点 在m 触 b 分类之前出现的是文本分类，文本分类是在预先给定分类体系下， 根据文本内容自 动确定文本类别的过程。从 触 b分类是在文本分类技术上发展起 来的， 但 w 七 b分类问题相对文本分类更加难处理，要考虑更多因素，这一特点 主要是由网页特征决定的。网页与文本文档不同，具有以 下特点: 网页的格式灵活多样。与文本文档的纯文本格式不同，网页是多种格式并存， 而且同一格式的网页也存在多个标准。我们可以把自己 制作的网页自由 地发布 到互联网上，因此网页的风格、格式变化很大。 ( 1)网页的数据内容多样。文本文档中都是文本数据， 而网页中除了有文 本数据还有图形图像数据，音频数据以 及视频数据等。不同是数据处 理方法各不相同，从而增加了网页处理的难度。目 前，大多数网页中 主要包含的是文本信息。 (2) 网页中 有大量的结构信息，能否合理的利用这些信息，必然影响分类 器的性能。网页中除纯文本以外，还有其它一些内 容对分类有贡献， 如网页的u r l ， h t m l 结构标记和超链接。 其中n几e 和hn 标注网 页的标题和段落子标题，b 、1 、u标记起强调文本作用， me t a标记 中的 k e y wo r d字段是对网页主题的描述，超链接周围的文本通常 第2 章 v 触 b 文本分类 是对链接指向网页的描述，网页之间存在链接也说明网页主题具有一 定的联系，网页的 1 r l中通常也会出 现跟网页类别相关的关键字。 在文献3l 1 中 作者对网页中不同 位置的 信息 对表现文本内 容的能力进 行了测试， 结果表明网页不同标记符中的信息对于文本信息的检索有 不同的影响. 其中 m e ta标记中的信息最具有代表力， 如果使用 m eta 和下 t l e 标 记符中的 信息来表示文档， 其文 本分类结果要好于 仅用b 。 勿 标记符中的信息来表示联 阳 b 文本。由 此可以看出在节 儿 b文本中不同 位置上的信息在表达文档信息方面的贡献是不同的。 (3) 访问网页会产生页面访问日 志，对日 志进行适当的分析有助于网页的 关联分析和分类。 网页中 包含大量信息， 这些信息可能对v 触 b 分类有贡献， 也可能存在噪声， 综合利用上述特征设计分类算法是研 触 b 分类的关键，也是难点所在。 2. 3 w七 b 文本分类的 过程 m 触 b文本分类过程包括:节 触 b文本表达， 分类器训练过程和新文档分类过 程 ( 如2 . 1 图所示) 。 图2. i v 几 b 文本分类过程示意图 v 触 b 文本是h tl n l 文件，大都包含很多无用信息即噪声，如与内 容无关的导 航条、广告信息、版权信息等等。在分类过程中，属性取值中只有名词与动词 第2 章 m 阳 b 文本分类 等有实际意义的词才对分类有作用，其它一些词性的词对网页的分类没有实际 的意义，比如 “ 好” 、 “ 是” 、 “ 啊” 等。因此在选取特征项之前，先要净化 w e b 文本。 研 触 b文本表达是从文档中 抽取能够表达主题的词汇， 也就是标引词，通常 是关键字。这一步主要是收集文本，并进行预处理，包括处理乱码、非文本内 容等; 机器内 码转换; 处理词 千( s te lnm i ng) 及停用词(s top w o r d s) : 删除 无效文本; 按类型集进行人工分类;按一定比例随机划分训练集和测试集。 确定特征项， 并按一定的描述模型对文本进行标引。它的作用是将文本的内 容按照一种计算 机能 够理 解的 格式 用 特征 任 。 咖r e ， 及 前) 描 述出 来， 使机 器能 够对文 本 进行 处理 和运算。由于在认 触 b 文本中不同位置上的信息在表达文档信息方面的贡献是不 同的，因此我们在词的权值中 应该体现出该词的位置信息， 这样才能够体现出 节 触 b文档的结构特征。通过文本表达方法得到的标引词 ( 特征项)的维数普遍 较大，这会影响分类的效率，甚至超出机器或算法的处理能力。因此要进行维 度约简，生成一个更紧凑的 特征空间。维度约简就是减少特征项，包括特征选 择 和 特 征 抽 取 两 个 过 程ll.词 . 训练集应该是公认的经人工分类的语料库，在训练集上进行机器学习，确 定分类器的各个参数，抽取分类规则，建立分类器。 最后利用分类器对新的文档进行分类。 2. l l w七 b 文本表达 web文本内 容变成机器内 部表示结构的方法多种多样， 可以 用词、字、短 语、 n- gram、显著性短语等形成向量、树等结构。在经典的研究中通常利用特 征( 介巾， 包括字、 词、 词组 等 ) 的 词频信息建 立文本向 量. 文本表示包括两个问题:表示与计算。表示特指特征的提取，计算指权重 的定义和语义相似度的定义。 特征提取包括特征的定义和筛选，特征定义和筛 选考虑以 什么作为文本的 特征， 并不是所有的词和字都要求或者可以 成为特征。 特征的权重定义及特征结构上的相似度度量可以 选取不同的 模型，如向量空间 模型、概率模型、语言模型等。文本表示是文本分类的第一步，该步骤的变化 很多，对最终聚类效果的影响也不尽相同。文本表示本质上是对原始文本进行 转换， 使之在机器上可形式化描述、可计算。 特征定义与筛选可以 采用不同的 特征选择方法， 可利用n-g r 即 . ， r a i ， 树提 取特征、可利用 l sl 降维转化特征、也可利用语义词典 w b r d n et或者 h o w n et 第2 章 节 几 b 文本分类 定义更复杂的特征结构。关于特征定义与筛选可以 参考自 然语言处理领域中的 相关研究，这里不详细介绍。 本节接下来主要介绍信息检索和文本分析处理中 经常用到的几个检索模型， 这几个检索模型根据不同的理论假设推导、定义了 不同的特征权重计算方法与语义相似度计算方法，是文本表示模型的重要组成 部分。 2. 3. l i 布尔模型 布尔模型是基于集合论与布尔代数之上的一种简单模型， 主要应用于信息 检 索 中 。 在 布 尔 模 型 中 ， 文 档 妈中 索 引 特 征 tl 的 权 重 哟 .， 是 二 值 的 ， 即 琳 ， “ 0， 1 一个文档表示成文档中出现的特征的集合，也可以表示成为特征空间上的一个 向量， 向 量中每个分量权重为0 或者1 ， 这种布尔模型称为经典布尔模型。 经典 布尔 模型中 查询与文 档的 相关性只能是。 或者1 ， 满足查询q ， e ry中的 所有逻辑 表达式的文档被判定相关，不满足的被判定为不相关. 经典布尔模型只能 用于信息检索中计算用户查询与文档的相关性， 而无法 利用该模型计算两个文档更深层面的相似度，无法在更多的文本处理应用中使 用。 在经典布尔模型基础上， 研究人员又提出了扩展布尔模型( e x te n d edb oole an a p p r o a c b ) ， 重新定义了户 刀 d 与or操作符成为多元操作符， 使相关性可以 成为0 ， 11 之间 的 数。 】 治 e 在si g i r 9 4 上的 论 文中 分 析了 几种 扩展 布尔 模 型，比 如五 】及 y 喊， 节 白 三 ie r- k ra 丘 ， p . n o rm与1 吐 加 i tc g 匕 e ， 认为s al to n 等 提出 的卜 的 n ” 模 型 相 对更优， 在卜 n o n n 中 ， 多 元六 刀 d 查询的 相似 度定 义为:d= (t ， ， 、) 1 1 二 1 . ， ， 伽 理 = 刁 刃 d (t ， ， 鞠)，i= l. n)， 共 有n 个 特 征 ， 为 特 征 ， %为 查 询 中 的 权 重 艺(l一 、)p ， 畔) : 敌 材 刀 ( d， (t : ， wq : )a nd (tz ， 礼 2 ).a nd (t 。 ， 踢d = 卜( 丝 一 下尸 一 一一广 ， (l p ao) 畔 艺i-l 对卜 n o rm扩展布尔模型稍做改 动就，可以 用于两个文本之间的 相似度计算。 将 要计算相似度的两个文本进行转化，一个用d的定义表示出 来， 另一个用and 伽e 尽的定义表示出 来， 那么就可以 利用卜 加n 力 扩展布尔 模型 进行更深层面的 相似度计算。 第2 章 节 触 b 文本分类 参 数p 趋近于 无穷时卜 的n n 模型相当于 经典 布尔模型， 空间模型。 布尔模型是基于集合论与布尔代数之上的一种表示模型 以转化为向量来等价实现，是一种类向量的模型。 p=1 时相当于向 量 ，其表示与计算可 1 1 l 2 向t空间模型 s al ton 教授提出 的向 量空间 模型 简称v s m模型0 儿 c t o r spac e m odel)， 是信 息检索领域中 经典的检索 模型11 01 ，目 前应用最多 且效果较好， 本文也主要采用 该模型。 ( l) v s m模型表示过程 向量空间模型将文档表示成一个向量，向量的每一维表示一个特征，这个 特征可以 是一 个字、 一个词、 一个n- gr am 或某 个复杂的 结 构。 通过对文档的 解 析处理可以得到这些特征. 通常情况下 用向 量空间模型中的向 量表示文 档时， 需 要对文档进行切分 ( 中 文分词、 英文 通过词的 分界符识别单词) 、 停用词处理、 英文词的 词形 还原或者 提取词干(s t e n ll u in g ) ，经过若 几个处理步骤后， 基本上就可以 得到一系列词， 将这些词作为文档的特征。所有的这些词构成一个 “ 空间” ，每个词对应着空间 中的一维。每个文档可以用文档中的词来表示，这些词及其对应的权重构成一 个向 量。 文档对应特征空间中的一个向量， 对应特征空间中的一个点。 表2 . 1 说 明v s m模型中文档与向量空间之间的映射关系。 表2. i v s m模型中文本与空间的映射表 文档视角向量空间模型视角 文档向量或者空间中的点 词l 空间中的一个维度 文档集合 分布在空间中的一组点 集 整个词典构成空间的 各个维度 词 的 权 重!空 间 中 点 的 坐 标 值 ( 2 )权重定义 在向 量空间模型中， 每个文档山 其组成特征t 来表示， 不同的t 在文档中作 用不同，根据特征对文档内 容表达的重要性每个特征可以 获得一个权重， 权重 的经典 定义是tf* idf 公式. 其中仆 指介 n nf r e q u e nc y ， 表示t 在文档d 中出 第2 章 节 阳 b 文本分类 现的次 数， 称为 词频; mf 指加 v 已 n 屹 d oc 切 叮 即 t f r 闪 u e n c y ， s al ton 将i d f 定义为: idk= le 岭， ” 表 示 ” 文 档 集 “ 中 所 “ 的 文 档 数 “ 拼 表 示 整 个 文 档 集 合 中 出 现过t 的 文档的总数， 称为特征的文档频率. i d f 反映特征在整个文档集合中的 分布情况，在一定程度上体现了该特征的区分能力， 吓 反映特征在文档内部的 分 布 情 况， 两 者 相 结 合的tf* idf可以 看 成 该 特 征 在 文 档中 的 重 要 程 度wl 厂 w， 声 ” 职声 * 扣月。 文档最后被表示成为一个带权重的向量，权重是该文档在向量空间中相应 维 度的 坐 标， 公 式wt 讨 是向 量 空 间 模 型 中 经 典 的 权 重 度 量 方 法 2. 3. l 3概率检索模型 概率检索模型是信息检索领域另一系列比较成熟的模型，经过多年的发展 已 在很多系统中应用并取得不错的效果， 尤其o k 户 田 1 模型在多届的t r e c评测 中取得过很好的成绩. 概率模型是一系列模型的简称，这类模型有自己的假设 前提， 有比 较完整的推理过程，将相似度看成一个概率。在信息检索中，主要 计算p ( r e l v 曲 ce l d oc 切 叮 ent q 明 斗 ) 并利用概率排序原则p rp口 ro b a b i l i s t i c r 肛 正 in g p ri nc i p l e ) 来判断不同 文 档与同 一个查询 相关的 程度。 p ( r e l v ad c e idoc 切 m e n t q 此 叮 ) 表示给出 一 个查询q u 恻， 文档d oc 班 n e nt与该 查询相关的 概率. 根据不同 的 假设进行 推理求p ( r e l v an c e doc u 比 哈 n t q u 恻) 的 计 算公式， 可以衍生出不同的概率检索模型.概率检索模型包括 bir ( b l l l aj 了 玩 d e pe n d e n cer e tri e v al ) ， b u 田川 田 了 i n d e 声 nce l n d e x mode l) ， inq u e r y 等. 实际 上应用最广泛的是o k a p i 模型， 该模型的权重定义公式通过一系列假设和推理 得到， 表现不俗，其权重定义公式称为b m 2 5 公式。 w， ， = 1。或 ( n一 n ) + 0 .5 n+0 . 5 、 . ( 工 丛 二 里 竺 、 )协 k十 犷 少 k= 气. (l一 b)+ b * dl/ 酬成 】 琳刀=( 棍+ 1 ) * 叼 了 ( 2 1 ) 棍十 q 了 第 2 章 m 触 b 文本分类 b m25 公 式 中 ， 特 征 权 重 计 算 公 式 wl 尹 的 计 算 需 三 个 全 局 的 变 量n 、 a v d l 、 n 以 及两 个人上确定的 参量kl 与b . n表示整个 语料的 文档总 数， 创d l 表示语料中 所 有文 档的 平均 文档 长度， n 表示 特征t 的 文 档 频率. 气 和b 的 经 验 值 可以 取 气 习.2 ， b = 0 . 7 ， 对于摘要之类的 短文本b 经验 取0. 25。 w，. ， 是 查 询 中 特 征 权 重 的 计 算 方 法 ， 在 信 息 检 索 系 统 的 查 询 处 理 中 需 要 计 算 这 个 权 重 不 需 要 该 公 式 。 在wt 二 中 只 有 参 数气 ， 气 经 验 上 可 取7 或 者10 00， 利 用棍 来 调整 查 询中tf 对于 权重的 影响 。 向 量空间模型与概率模型都是对原始文本的表示模型， 在实践中这两者的 应用最为广泛。其主要的不同点在于对语义相似度度量的定义上，向 量空间模 型在欧拉几何空间通过向量的夹角余弦来定义的，概率模型在概率测度空间上 通过概率来衡量两个文本的语义相似度，概率模型基于概率值而不是几何测度 值来衡量语义相似度.这两个模型存在许多相同点，两者的特征权重定义都基 于词频并且都假设了特征间的相互独立性。 1 3. l 4语言模型 语言模型是自1 9 98年以 来逐步发展起来的检索模型， 本质上也是一种基于 概率和统计的模型。语言模型中认为每个文档都是一个语言模型，整个语料集 也是一个语言模型，查询也看成一个语言模型。通过计算语言模型与语言模型 之间的距离计算查询与文档的相关性、计算文档与文档之间的相关性。 统计语言模型认为语言就是字母表上的一种概率分布， 通过概率分布计算 任何一个字母序列成为该语言一个句子或者其他语言