（管理科学与工程专业论文）文本挖掘预处理相关基础技术分析与应用研究.pdf

绪论 文本挖掘预处理相关基础技术分析与应用研究 摘要 本论文将在对比分析并发现现有文本挖掘技术存在不足的基础上，提出改 进文本预处理精度的算法。文中涉及的主要技术包括文本收集、文本预处理、 处理后的文本的中文分词、预抽取训练样本及使用k n n 方法进行文本训练和 文本分类等。通过对系统功能的分析，本研究把系统分成了文本预处理、中文 分词、文本特征向量的提取、文本特征向量的训练和分类等四部分。 在文本特征向量的提取、文本特征向量的训练和分类部分中，作者研究了 一种基于词的文档频率( d f ) 和信息增益相融合的的方法，这种方法不仅相 对简单，有层次感，而且在保证分类器性能的基础上，可以允许我们适当地选 择训练样本，减少支持向量，从而提高k n n 的训练和分类速度。接着介绍了 k n n 的基本理论以及目前k n n 方法在文本分类中的应用情况，以及如何使 用k n n ，利用获得的文本特征向量及其权重来生成输入文档，进行文本训练 和分类的过程。 本课题实现了文本收集、文本预处理和中文分词等文本挖掘的关键技术， 并在研究的基础上提出了一套特征抽取及文本挖掘的方案，为后续的研究奠定 了基础。 关键词：中文分词向量空间模型k 最近邻方法文本挖掘 绪论 t h ea n a l y s i so nt h eb a s i ct e c h n i q u e sf o r p r e p r o c e s so ft e x tm i n i n ga n dt h es t u d y o nt h ea p p l i c a t i o no ft e x tm i n i n g a b s t r a c t t h eg e n e r a lw o r k f l o wo ft e x tm i n i n gh a sb e e ns y s t e m a t i c a l l ye x p l a i n e da n d i m p l e m e n t e di nt h i st h e s i s t h ek e yt e c h n i q u e su s e di nt e x tm i n i n gi n c l u d i n g c o l l e c t i n gt e x t ，p r e p r o c e s so ft e x t , a u t o m a t i cc h i n e s ew o r ds e g m e n t a t i o nf o rt h e p r o c e s s e dd o c u m e n t s ，s e l e c t i n gt r a i n i n gp a t t e r na n dr e d u c i n gs u p p o r tv e c t o r s ，t e x t t r a i n i n ga n d t e x tm i n i n g w ed i v i d et h es y s t e mi n t of o u rp a r t sb a s e do na n a l y s i so f t h es y s t e m sr e q u i r e m e n t ：t e x t c o l l e c t i n ga n dp r e p r o c e s s ，c h i n e s ew o r d s e g m e n t a t i o n ，s e l e c t i n gt r a i n i n gp a t t e r nv e c t o ra n dt h et r a i n i n ga n dc l a s s i f i c a t i o no f t h et e x tp a t t e r n sv e c t o r u n l i k et h eg e n e r a lt e x tm i n i n g ，w en e e dt oc o l l e c tt e s t ，p r e p r o c e s st h e s et e x t a n ds a v et h ew e i g h to ft h et e x t w ei m p l e m e n tap r e e m p t i v em u l t i t h r e a dw e bt e x t c o l l e c t o r i tc o l l e c t st h et e x to fs p e c i a lc a t a l o gu s i n g d e p t hf i r s ta l g o r i t h m a n dw e i m p l e m e n tat e x tp r e p r o c e s s o rt oe r 蹴t h et a ga n ds e tt h ew e i g h tf o rt h ew e bt e x t b yu s i n gr e , c u r s i v em a t c hm e t h o d i i 绪论 o nt h eo t h e rp a r t s ，w ef i r s ti n t r o d u c eac l a s s i f i e ru s i n gt h en e x u sb e t w e e n w o r d sa n dt y p et op r o p e r l ys e l e c tt r a i n i n gp a t t e r na n dt or e d u c es u p p o r tv e c t o r s a n dt h e nw ei n t r o d u c et h eb a s i ct h e o r ya b o u tkn e a r e s tn e i g h b o r ( k n n ) ，t h e a p p l i c a t i o no fk n n i nt e x tc l a s s i f i c a t i o na n dt h es o f t w a r ek n n t h ee x t r a c t e d p a t t e r n sa n dt h e i rw e i g h ta r eu s e dt of o r mt h ei n p u tf i l e ，t h r o u g hw h i c hw e c a n i m p l e m e n t t e x tt r a i n i n ga n dt e x tc l a s s i f i c a t i o n t h ea u t h o ri m p l e m e n tt h et e x tc o l l e c t o ra n dp r e p r o c e s s o ra n dt h ec h i n e s ew o r d s e g m e n t a t i o nm a c h i n ef o rt e x tm i n i n g ，p r o p o s ean e ws o l u t i o nf o rs e l e c t i n gt h et e x t p a t t e r n sa n dt e x tm i n i n gb a s e do no u rs t u d y k e yw o r d s ： c h i n e s ew o r ds e g m e n t a t i o nv e c t o rs p a c e m a c h i n e ( v s m ) kn e a r e s tn e i g h b o r ( k n n ) t e x t m i n i n g i i i 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： 日期： 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 本学位论文属于保密在旦年解密后适用本授权书。 本人签名： 导师签名： 1 1本论文的研究背景 1 1 1 社会所拥有的信息急增 第一章绪论 信息化社会，社会的运转就是智能化r r 系统的运转；社会的历史就是数据的历史。近 年来随着数据仓库和计算机网络的广泛应用，加上使用先进的信息自动生成、采集和存储 工具，社会所拥有的信息量大增： 1 ) 首先是九十年代以来，i n t e r n e t 以惊人的速度发展起来，它容纳了海量的各种类型 的一手和二手信息，包括文本信息、图片信息、声音信息、视频信息等； 2 ) 条形码技术和射频技术在商业上的普遍使用使得物与物、机器与机器之间的通信信 息成为数据管理的一个重要方向，如超级市场上的p o s 系统每天都要存储上万笔 的顾客购买商品信息，物流系统大量的物品流动和位置数据等； 3 ) 先进的现代科学观测仪器的使用每天也在生产巨量的数据，如各种同步卫星每小时 传回地球的遥感图像数据就达5 0 # g a ( 千兆) 字节； 4 ) 近几年来，基于文本内容的移动通信增值业务的发展，数据量更是成倍增长，如中 国移动运营商的彩铃业务、定制短信业务、博客业务、手机报业务等等，每天都记 录数十万乃至上百万用户咨询、订购、消费和支付的数据。 1 1 2 信息化社会以信息流为核心来带动 1 ) 工业文明突出的特点是以大规模的工业基地和商业基地为二元中心来带动物流、资 金流和人流的，这个时代，连接工业基地和商业基地之间的交通运输网络成为社会 北京邮电人学博f ：论文 发展的一个重要标志，信息的流动也主要是随着交通网络运行的。当社会从工业文 明向信息文明演进的时候，信息网络的地位逐步提升，并成为带动工业化实现跨越 式发展的核心力量。可以说，在信息社会信息流发达才会带来物流、资金流和人流。 网络信息化使社会的核心资源打破时空得以广泛共享，从而使市场全球化，经济一 体化，利益共同化。未来世界的商业中心、金融中心同时也必须是信息网最发达的 地方。任何传统网络( 即物流、资金流和人流) 如果不能运用信息智能化技术进行 升级，就会被淘汰。以中国邮政为例，它所拥有的人员和网点可以说都是中国最多 的机构之一，但经营物流配送业务，搞了很多年，也搞不过中外运、大通等，一个 重要原因是缺乏智能化的的信息支撑系统，管理手段过于陈旧，结果是物流配送准 确率和效率低下，客户流失严重。 2 ) 随着信息化进程加快，信息在社会各行业各领域的地位将日益重要并逐步成为最主 要的管理对象。这个时代是按人们占有信息、处理信息、利用信息的能力来衡量你 的综合竞争能力。你所拥有的信息越多，你的吸引力就越大。但仅拥有信息是不够 的，还必须有对应的处理能力和应用能力。当信息量大到一定程度后，如果没有科 学有效的方法进行处理和搜索，信息反而会成为社会的一种负担。这就是为什么基 于数据仓库的b i 系统日益受到重视的一个重要原因。 3 ) 信息将成为一种产品，以信息为核心的价值设计和价值传递将成为一种产业。当前 我国传统通信运营商正向信息服务商转型，如中国电信重新定位为综合信息服务 商，而中国移动则由移动通信专家变为移动信息专家，如何将强大计费系统所记录 的用户信息、业务信息、位置信息、市场反馈信息等生产成市场所需要的信息产品， 将成为这一转型成败的关键。未来，除了传统对信息的传输业务之外，各类市场信 息的分检和分发将成为电信运营商越来越重要的服务。另外，由于电信市场竞争的 加剧，传统语音业务资费水平的持续下降，如何利用强大数据库支撑下的经营分析 来实现精细化管理，提高效率，降低成本，也是各大运营商在转型过程中需要构建 的核心竞争能力。 北京邮电大学博七论文 1 2本论文选题的意义 作者在阅读可接触文献的基础上，深刻认识到文本挖掘是信息社会代表先进生产力 的重要技术和应用，尤其在我国推行。以信息化带动工业化，以工业化推动信息化战略 背景下，更具有十分重要的现实意义： 1 ) 文本数据挖掘已经被认识到是推进信息化发展的重要组成部分。人类社会的每一次 进步都是从劳动工具的改善开始，然后以生产效率提高、劳动者的解放为成功标志 的。我们目前正在经历的信息化文明就是要通过以计算机为代表的l t 技术将劳动 者从庞大的数据采集、记录、计算和指令分发中解放出来，实现生产和服务运营的 智能化，是继工业文明解放劳动者体力后，对劳动者智力的一次解放。信息化简单 来讲就是生产和服务运营流程的n 自动化与运营指令发布的智能化。而实现指令 智能化的主要途径就是通过对数据库的深入分析和挖掘，从中发现知识和规则，并 对一种现象一个事件运行状态和变化形成准确的判断和结论。 2 ) 文本数据挖掘被证明是提高信息利用效率和精度的有力手段。由于文本数据信息的 表达、存写和输出方式多种多样，如果不能对这种多样性进行有效的转换、分类和 排序，可以肯定互联网作为一种现代信息提供手段将不会象今天这样受欢迎，并成 为越来越多的人搜寻信息和学习的主要手段。试想，当你所关心的某一方面信息达 到上万条甚至数十万条时，而且这些信息以一种没有规则的顺序输出时，识别出真 正对你有用的信息可能是一项成本巨大几乎不现实的难题，因为这些信息存在严重 的重复现象、无关联现象、无序现象，但你却不知道哪一条是你所关心的而不得不 一条条去阅读。最近几年以来，互联网文本搜索引擎技术发展的经验表明，文本挖 掘不仅可以成功提升互联网向用户( 包括机器设备) 输出信息的准确性和效率，还 可以大大增强用户对互联信息的依赖程度。互联网界已经普遍认识到文本挖掘是一 项具有较大实用价值的技术，是组织和管理文本数据和知识的有力手段。概括来讲， 文本挖掘的核心就是通过搜索数据库，寻找隐含的模式，发现专家( 在这项技术之 前，我们更多依赖专家) 可能忽略的预测信息，因为这些信息常常是他们未能预测 到的。而对决策机构如企业来讲，文本挖掘就是一种决策支持过程，它主要基于 3 北京邮电大学博。 ：论文 朋、机器学习、统计学等技术，高度自动的分析原有的数据，做出归纳性的推理， 从中挖掘出潜在的模式，预测用户行为，帮助决策者调整策略，减少风险，做出正 确的决策，这就是文本挖掘的主要任务。 3 ) 文本数据挖掘是提高人工智能水平的关键技术。衡量人工智能水平高低的主要指标 就是机器的判断理解能力、决策思维能力和实施指挥能力，其中最为关键的就是判 断理解能力。但是信息，而且大部分信息都是以文本形式存在的。文本是由自然语 言表示的，如果机器能很好地理解自然语言，那么所有的问题将迎刃而解，但是目 前机器的还远远不具备对自然语言的判断理解能力。所以，将文本翻译成机器( 当 然包括普通消费者) 可以读取和理解的形式是利用文本信息所必须做到的。互联网 领域、图书信息管理领域、新闻档案管理领域的经验表明，结构化的搜索、浏览及 提供个性化的服务等方面，均在一定程度上依赖于准确的文本分类技术，这就是文 本数据挖掘的现实意义及应用价值。经过多年的研究与实践，文本挖掘已经逐渐与 搜索引擎、信息推送、信息过滤等信息处理技术相结合，对于电子图书馆、联机出 版、情报收集、信息服务、大规模文本信息的通信和寻径、以及大规模数据库特别 是文本数据库的知识挖掘和企业的精细化营销等领域均呈现出广阔的应用前景和 十分重要的现实意义。 4 ) 文本数据挖掘是推动粗放式管理向精细化管理变革的活化剂。在传统的决策支持系 统中，知识库中的知识和规则是由专家或程序员建立的，是由外部输入的，其有效 性的高低取于专家个人的经验和智汇。当描述现象的数据达到一定规模后，处理和 判断这些现象的工作量就会超过任何专家个人的能力，而文本数据挖掘的任务就是 通过计算机1 1 技术发现大量数据中依靠人力难以发现的知识，是从系统内部自动 获取知识的过程，对于那些决策者明确了解的信息，可以用查询、联机分析处理或 其他工具直接获取，比如“列出各个子公司在上个月的销售情况 ，而另外一些隐 藏在大量数据中的关系、规则和趋势，也可以由系统发现并提供给管理这些数据的 专家学习。中国移动通信公司的成功经验表明，通过对通信业务咨询、订购、消费 信息，尤其是增值业务( 如梦网业务、定制短信、彩铃、彩信、移动互联网业务、 4 北京邮电犬学博上论文 飞信等) 消费信息的深入挖掘，可以更加准确地把握用户的特征和需求偏好，跟踪 市场营销活动的市场反馈，并利用这些知识实现流程的 化，逐步向精细化营销 和营销管理的智能化方向发展，大大提高营销决策的准确性和效率，将企业从传统 的要素竞争力( 如产品、资金、人才等) 上升到组织竞争力( o r g a n i z a t i o nc o m p e t i t i v e c a p a c i t y ) 。 总之，社会发展将面临越来越多的文本数据，利用文本数据挖掘技术处理这些数据，不 仅可以带来巨大的商业价值和社会价值，而且是社会向信息化文明演化进程中确保自身“与 时俱进一所必须掌握的劳动工具。 1 3本论文选题的研究基础 1 3 1研究现状 1 ) 自动文本分类的研究已经进入到实用化阶段。作为文本挖掘核心部分的自动文本分类 研究始于上个世纪5 0 年代，i b m 公司以h p l u h n 为代表的一批研究人员在这一领域 进行了开创性的研究。为了改善计算机的存储和检索效率，他们提出来了以散列技术 为基础的自动分类思想并进行了有效的尝试，随后一些研究人员开始将这一方法应用 到包括图书情报和新闻档案管理的领域。1 9 6 0 年，m a r o n 在j o u r n a lo fa s m 上发表 了有关自动文本分类的第一篇论文o nt e l e v a n c e , p r o b a b i l i s t l ci n d e x i n ga n d i n f o r a a t i o nr e t r i e v a l ，文章对这种分类方法进行了系统的总结和论证，随后许多 著名的情报学家如l ( s p a r c h 、g s a lt o n 及r m n e e d h a m 等都在这一领域进行了卓有 成效的研究，将这一方法推进到了实用化的程度。概括起来，自动分类的研究大概已 经历了三个阶段：第一阶段( 1 9 5 8 1 9 6 4 ) 主要进行自动分类的可行性的概念研究，第 二阶段( 1 9 6 5 1 9 7 4 ) 进行自动分类的实验研究，第三阶段( 1 9 7 5 至今) 进入实用化阶 北京邮电大学博i ：论文 段。今天，自动文本分类和基础性的散列技术已经被广泛认可，而被更多关注的重点 则是如何将这些已经建立起来的方法论实用到社会的各个领域中去。 2 ) 文本提炼被普遍认为是文本挖掘的前提性工作。文本通常是以多种形式存储的，如 w o r d 、p p t 、t x t 、p d f 、e x c e l 等，如果不对不同形式存在的文本进行提炼，可以想 象文本挖掘是无法实现的。因此，文本挖掘首先要做的就是把任意格式的文本转换为 机器可以学习的媒介格式。这种媒介格式可以是半结构化的类似于概念图的表示，也 可以是结构化的类似于关系数据的表示。目前，媒介格式有基于文本的，每个实体代 表一个文本；或者是基于概念的，每个实体代表在某领域内会引起人们兴趣的概念或 对象。挖掘基于文本的媒介格式可以导出文本之间的模式和关系。文本聚类和文本分 类都是从基于文本的媒介格式中挖掘知识的例子。挖掘基于概念的媒介格式将导出对 象或概念间的模式和关系，预知建模和相关发现都属于这一类。基于文本的媒介形式 可以被置换为基于概念的媒介形式，比如通过对特定领域的相关信息的提取和重排技 术。 3 ) 预处理成为提高文本挖掘应用效率最关键的要求。早先的信息抽取技术便是文本挖掘 的雏形，一个著名的信息抽取的例子是f r u m p 项目，由g e r a l dd e j o n g 于1 9 8 2 年设 计，这个系统包含了一系列程序，这些程序能够扫描新闻数据库，并对其进行归档， 这一技术对提升文本信息搜索和查询效率是一个较大的贡献。后来，赫尔辛基大学的 数据挖掘科研小组在进行研究和试验时，发现处理非结构化文本资源显得越来越重要 ( 因为非结构化文本资源越来越多) ，并提出将数据挖掘技术直接应用于经过预处理 的文本信息的设想。他们将预处理过程看作是一个至关重要的环节，即预先对所有文 本进行格式转换和统一，然后用一种方法对所有文本进行一致的挖掘，大大提高文本 挖掘的效率，从而有效地改变了数据挖掘依赖于文本最初是如何被处理( 存储) 的这 一法则。构成文本的词汇数量是相当大的，相应地表示文本的向量空间的维数也相当 大，可以达到几万维。如果按照文本存在的原始维度进行搜索和查询，效率会低到对 决策支撑毫无意义的程度。因此需要进行维数压缩的工作，他们实验的结果表明，经 过维数压缩预处理后大大提高了程序的运行效率。 6 北京邮电大学博上论文 1 3 2 面临的问题 如上所述，由于文本挖掘存在着巨大的商业价值和社会价值，近半个世纪以来，国际上 已经在这一领域进行了一些有益的探索，但总体来看这一领域的研究只是刚刚开始，还有诸 多问题等待研究和解决。本文作者在阅读可以接触到的相关文献资料后，发现至少存在以下 三个方面的问题值得进一步研究： 1 ) 如何提高文本预处理的精度? 目前国际上文本预处理的研究成果对提高挖掘处理速 度做出了明显的贡献，但对精度却带来了负面的影响。因为目前提高速度是以降低文 本撮向量维度。损失文本的信息为代价的，结果是在文本挖掘过程中，信息极易发生 遗漏或污染现象( 即一些对挖掘对象或目标有紧密关联的一些信息被压缩掉了，而一 些没有关联的信息确被提取出来作为分类的因素或标准) ，导致精度下降。因此，如 何在提高处理速度和效率的同时，保持和提高机器学习的精度是我们需要不断研究解 决的课题。 2 ) 怎样进行领域适应( d o m a i na d a p t a t i o n ) ? 目前文本数据挖掘在图书情报、新闻、 互联网等行业已经进行了相当有效的应用，但进一步的实践发现这些行业已经取得的 经验并不容易运用到其它行业，原因是文本数据通常都带明显的行业特性，尤其在中 文环境中，同一文本在不同行业可能有非常不同的含义，每一个模型的建立就表现出 很大的行业局限，对文本挖掘的广泛推广带来了很大挑战。 3 ) 如何将国际上已经取得的成果应用于中文环境? 在国内，文本挖掘研究和实践起步较 晚，借鉴国际上已经取得的研究和应用成果无疑是非常必要的，但由于中文语句的特 殊性，如不以空格作为词的分隔标志，汉语没有时态概念等等，照搬国外的经验并不 能完全满足中文自动分类技术开发的要求，需要独辟蹊径，寻找的新思路。 7 北京邮电火学博上论文 1 4本论文选题的研究方向 根据以上的背景和现状分析表明，文本数据挖掘作为一项具有较大商业价值和社会价值 的技术已经受到了广泛的关注，目前的文本挖掘研究成果对效率和速度有了喜人的贡献，但 我们同时发现应用已有研究成果的精度表现却不尽人意。如果只有速度没有精度，文本挖掘 的效率再高，其价值也将大打折扣。为此，本文作者将试图在吸取前人研究成果的基础上， 重点针对这一问题进行研究和改进。 同时，作者在阅读现有国内的研究文献时，也发现已有的研究大多集中在文本数据挖掘 算法的讨论上，虽然提出了不少针对中文环境的模型和方法论，但主要集中在吸收国外研究 成果有效降低文本特征向量维度、提高挖掘预处理速度和效率，至于如何保持和提高挖掘的 精度方面研究讨论却较少。而我们所面临的环境却是，一方面中文文本数据库的建设和管理 起步较晚，中文文本质量总体较差，另一方面中文文本数据规模却在急剧增长，如果不能在 文本挖掘精度方面有所突破，必将影响文本挖掘在我国的应用推广和信息化的进程。 鉴于此，本文把研究的重点放在“如何在提高预处理效率的同时，保持挖掘的准确率 。 整个研究从文本挖掘的定义和相关概念介绍开始，通过对比分析信息增益( i n f o r m a t i o n g a i n ) ，x 2 统计法( c h i ) ，互信息( m u t u a li n f o r m a t i o n ) 等文本预处理要件的方法论，发现 现有文本预处理技术存在的不足，以及对互信息的算法提出基础性改进。 另外，针对中文文本挖掘的重要组成部分中文文词也进行了研究和改进。最后通过文本 挖掘的具体应用实践说明了本研究成果的价值。 8 第二章文本挖掘的定义和相关概念介绍 从上个世纪5 0 年代文本挖掘概念被提出以来，国际学术界一直没有停止对其进一步的 研究和实践，以下作者将先对文本挖掘的概念和相关的基础技术做一个综述。 2 1文本挖掘 什么是文本挖掘? 文本挖掘( t e x tm i n i n g ) 是指从文本库中抽取对抽取人有价值的信息 和知识的计算机处理技术，这种信息和知识不仅包括已经被认知的，而且包括大量还没有 被认知的。顾名思义，文本挖掘是在文本数据库中进行数据挖掘( d a t am i n i n g ) ，简单讲文 本挖掘就是数据挖掘的一个分支。文本数据挖掘是一个边缘学科，由机器学习、数理统计、 自然语言处理等多种学科交叉形成文本数据挖掘的出现是由应用需求来驱动的，是因为 文本信息量在很多领域的快速增长，超过了以往人工所能处理的范围。这些需求包括了目， 前比较前沿的智能商务( b u s i n e s si n t e l l i g e n c e ) 、信息检索( i n f o r m a t i o nr e t r i e v a l ) 、 生物信息处理( b i o i n f o r m a t i c s ) 等领域，例如，图书情报管理、新闻档案管理、互联网搜 索( w e bs e a r c h ) 、客户需求分析( c u s t o m e rd e m a n da n a l y s i s ) 等等。 文本挖掘的过程。如图2 一l 所示，由三部分组成：底层是文本数据挖掘的基础领域， 包括机器学习、数理统计、自然语言处理：在此基础上是文本数据挖掘的基本技术，有五 大类，包括文本信息抽取、文本分类、文本聚类、文本数据压缩、文本数据处理；在基础 技术之上是两个主要应用领域，包括信息访问和知识发现，信息访问包括信息检索、信息 浏览、信息过滤、信息报告，知识发现包括数据分析和数据预测。 9 北京邮电人学博i ：论文 ii 圈圈 i 文本信息抽取l i文本分类l ij1 _ j fi 囡囡圜 图2 - 1 文拳数据挖掘概现 通常情况下，我们可以把文本数据的分类、融合、压缩、摘要、以及从文本中发现知 识与提取信息都看作是文本数据挖掘的具体任务。以下我们先对文本数据挖掘的五大基本 技术做一个综述。在这五项基本技术中，文本信息抽取和文本数据压缩是文本数据挖掘特 有的技术，其它三项技术在其它数据挖掘领域中也会用到。 2 2 文本信息抽取( t e x ti n f o r m a t i o ne x t r a c t i o n ) 文本信息抽取是从文本数据中抽取人们关注的特定的信息，既可以作为这个文本数据 自身的特征对这个文本进行标注，以方便以后快速准确地找到这个文本，也可用于其它数 据挖掘处理，比如去掉重复性的文本、或对文本进行多因素混合排序。文本数据可以以旬、 段落、篇章为单位；抽取信息既可以以字、词、词组、旬、或段落为单位，也可以是这些 基本单位的组合。抽取信息可以是关于个体的( 比如，人、组织、时间、地点) ，也可以是 关于事实、事件、或个体间关系的。 文本信息抽取所抽取的信息可能是各种类型的，比如，文本中的名词短语、人名、地 名、机构名、产品名等实体名称，或者是电子文件的题目、作者、作者所属单位等元数据， 或者是专业术语的定义、网上购物信息、新闻报道中的事件等。文本信息抽取的目的决定 了人们对抽取取信息类型的定义。 1 0 北京邮电人学博士论文 通常把文本信息抽取看作是一个标注( t a g g i n g ) ，是指导机器学习的一个应用。t a g 在 中文里，可以叫做标签。在文本挖掘里，t a g g i n g 帮助你把你的文本分类，而t a g 就是标签 名，就是从文本中抽取的能够识别这个文本的关键词。通常情况下，一个文本可以有多个 标签，多少取决于这个文本所涉及的领域或服务的对象，领域和对象越多，标签就越多。 下面，我们通过机器学习的框架来说明这个问题。如图2 - 2 所示，文本信息抽取分为学习和 抽取两个过程。首先，一些有标注的数据样本，每一个样本由文字单元序列及相应的标注 序列组成，我们用毛或，2 毛一来表示第f 个样本的文字单元序列，y j , 2 y o , 来表示相应 的标注序列，其中f - 1 一。每一个毛，( | _ l - - , n ) 是一段文字，是我们进行处理的最 基本单元，每一个咒，( ，- , - - - , n ) 是一个标注。机器学习系统基于已有的标注数据构建 一个模型，它可以由一个条件概率分布来表示，即在给定随机变量置邑五的条件下随 机变量k k k 的条件概率分布这里每一个五( i - l 2 , k ) 取值为所有可能的处理文 字单元，每一个x ( 1 - 1 , 2 , 七) 取值为所有可能的标注。一般有七墨万。信息抽取系统参 照学习得到的条件概率分布模型，对一些新的文字单元序列进行标注。找到相应的标注序 列。具体来说。对一个文字单元序列+ 以+ i 2 + l ，_ 找到使 p 帆+ 幽m 虼山i + 成+ t , 2 山) 最大的标注序列儿椰+ 1 2 y 一山。 五舯1 ，1 而+ 1 刀 以) m gm 缓爿k u h x 。t ao - oh 山) 图2 - 2 文本信息抽取过程 捌型 州w 肌 钿 北京邮电大学博 ：论文 文字单元在具体实现中可以是一个文本、一个句子、一个词、甚至可以是中文的一个 字。标注可能是表示信息抽取对象的开始、结束、及其它。在信息抽取时我们将从标注为 开始到标注为结束的文字单元作为信息抽取。例如，在从英文文章中抽取基本名词短语的 信息抽取中，样本是英文句子，文字单元是词，抽取信息是基本名词短语，标注是名词短 语的开始、结束、或其它( 以b 、e 、0 表示) 。输入以下的英文句子，抽取系统输出相应 的标注序列，即输出相应的抽取信息。 输入：a tm i c r o s o f tr e s e a r c h ，w eh a v ea l li n s a t i a b l ec u r i o s i t ya n dt h ed e s i r et oc r e a t en e w t e c h n o l o g yt h a tw i l lh e l pd e f i n et h ec o m p u t i n ge x p e r i e n c e 输出：a t om i c r o s o f l br e s e a r c h e ，w e oh a v e oa n oi n s a t i a b l e bc u r i o s i t y ea n d ot h e o d e s i r e b et o oc r c a t e on e w bt e c h n o l o g y et h a t ow i l i oh e l p od e f i n e ot h e oc o m p u t i n g f b e x p e r i e n c e e 文本信息抽取就是通过一定规模的样本文本，通过文本挖掘的过程构建一个信息抽取 模型来对没有标注的文本加以标注，提高以后使用本文本的效率。文本信息抽取常用的模 型有：隐马尔可夫模型( h i d d e nm a r k o vm o d e l ) 、最大熵马尔可夫模型( m a x i m u me n t r o p y m a r k o vm o d e l ) 、条件随机场( c o n d i t i o n a lr a n d o mf i e l d ) 、表决感知机( v o t e dp e r c e p t r o n ) 。 2 3文本分类 简单地说，文本分类系统的任务是：在给定的分类体系下( 比如文本所涉及的领域、行 业、时间范围、地理范围等等) ，根据文本的内容自动地确定文本关联的类别。从数学理论 和应用角度来看，文本分类是一个映射的过程，它将未标明类别的文本映射到已有标注的 类别中( 不进行类别标注的文本是很难被使用的) ，该映射可以是一一映射，也可以是一对 多的映射，因为通常一篇文本可以同多个类别相关联。用数学公表示如下： f ：彳- - * b 式( 2 一1 ) 其中，a 为待分类的文本集合，b 为分类体系中的类别集合 北京邮电人学博t 论文 下面，我们通过机器学习的框架来描述这个问题。它分为学习和分类两个过程。如图 2 3 所示，首先有一些文本f l f i 及其所属类的标注c i c l ，学习系统从标注的数据中学到 一个函数厂仃) 或条件概率分布尸够ir ) ，我们称其为分类器。c 和t 取所有可能的类和文本 ( 通常是文本的特征) 。对新给出的文本“，分类系统利用学到的分类器对其进行分类。 类别可以只有两类，通常用0 和l ，或+ 1 和一1 表示，称为两类问题。当类别超过两类时， 可以采用“一类对所有其它类 的方法，把问题分解为两类问题处理。也可以用其它技术， 比如( e c 0 c ) 这里，我们只考虑两类问题。 g c 。le 2 c 2 卜e 。，c 一) 1 0 l 图2 - 3 文本分类 文本分类有非常广泛的应用。按照文本的来源可以包括新闻报道、网页、电子邮件、 学术论文、n c w s g r o u p 文章等类型，按照文本所涉及的领域可以包括搿政治一、“经济一、 搿体育竹、“教育一等等。也有根据其它特点的，比如，一正面意见一、一反面意见一。 也可以是根据应用要求的，比如，“垃圾邮件一和。非垃圾邮件一，。垃圾短信一和“非垃圾 短信一文本分类时，我们从文本中取出特征，将每个文本特征变成一个属性向量。通常， 我们把文本中的词抽取出来，将它们作为特征，特别是进行根据内容的分类的时候；这等 于是把文本当作一个。词包( b a go f w o r d s ) 一分类是机器学习的核心问题，即从文本中抽 取一些关键信息来对一个文本的内容进行准确描述并用这些信息对文本的类别进行标注。 国际上一些研究人员已经提出很多分类器模型来对文本进行分类，事实上这些模型今天被 北京邮电人学博f ：论文 广泛地应用到文本分类的工作。其中常用的模型或算法有：支持向量机或s v m ( s u p p o r t v e c t o rm a c h i n e ) 、边缘感知机( p e r c e p t r o nw i t hm a r g i n ) 、最近邻法( n e a r e s tn e i g h b o r ) ，决 策树( d e c i s i o nt r e e ) 、决策表( d e c i s i o nl i s t ) 、中心法( c e n t r o i d ) 、朴素贝叶斯( n a i v eb a y e s ) 、 a d ab o o s t 算法、l o g i s t i c 回归( l o g i s t i cr e g r e s s i o n ) 、w i n n o w 算法、神经网络( n e u r a l n e t w o r k ) 、贝叶斯网络( b a y e s i a nn e t w o r k ) 。 图2 4 和图2 5 介绍几种常用的模型与方法的基本概念。支持向量机s v m ( 或边缘感 知机) 用向量空间的点表示样本，在向量空间中寻找将正负例分开的边缘最大的超平面： 这里最大边缘( m a r g i n ) 是这个方法的重要概念。最近邻法同样用向量空间的点表示样本， 分类时将样本点分到离其最近邻的样本点的类中去；最近邻是重要概念。决策树或决策表 是定义在特征空间的，他们是基于规则的方法，学习时找到将正负例分的最开的分割 ( p a r t i t i o n ) 。中心法又叫作r o c 4 ；h i o ，取自其发明者；它先在向量空间中找到正负例的中心 点，分类时按离中心点的距离分类。 向量空间 支持向量机 图2 - 4 文本分类方法1 最近邻法 北京邮电人学博二 = 论文 特征空问 决策树，决策列表 图2 - 5 文本分类方法2 中心点法 已标注好的训练样本中的正负例特征往往会各自聚集在一起( 不排除有一些例外) 。在 s v m 学习过程中我们试图找到最佳的超平面，它可以最大程度上分离正负例( 注意我们这 里只关心分离训练样本数据) 。更精确地说，这个超平面拥有最大的正负例特征问的边缘。 边缘概念有精确定义，直观上它是正负例区域边界至超平面的距离。正负例中有例外时， 也可以用扩展的这个框架处理我们称以上的超平面为线性s v m 。这样，s v m 的学习就转 化为给定条件下的二次优化问题。理论上可以证明寻找最大边缘的超平面会促使泛化误差 最小，即对未知数据的期待分类误差最小( 这是机器学习的目标) ，这也就说明了为什么 s v m 会有效。此外，利用核函数技术可以将线性s v m 进一步扩展为非线性s v m 。 2 4文本自动聚类 文本聚类是根据文本表现出来的特征及分布进行归类。也就是说，以给定的文本在所 抽取的信息为中心周围集中的程度为依据将文本集分为若干子集，每个子集就称之为类， 这个类的名称是由所抽取的信息为特征定义的。可以说，聚类是对未知类别集合进行分类的 一种方法当通过聚类定义的类别表现稳定后，我们就可以用这个类别对示知的个体进行如 类，这个过程就是分类。 1 5 北京邮电犬学博七论文 聚类的基本要求是使得各个类别内部的文本尽可能相似，而类与类之间的文本尽可能 有明显的差异，这个差异就是文本特征。比如，同样都是包含核心分词企鹅的文本，一类 是关于企鹅这种动物的，而另一类则是关于用企鹅这个名称命名的商品的，因此这里的动 物和商品分别成为关键特征。这个特征既可以代表一个类内部的相似性，又能代表一个类 与另一个类之间的差异性。文本这种特征的选取往往根据应用目的或对象之不同而各异。 文本聚类可以用到各种场合。文本的类型可以是新闻报道、网页、电子邮件、论文、 n e w s g r o u p 文章。聚类时，如果一个样本只能属于一个类，我们称这样的聚类为硬聚类， 如果一个样本可以属于多个不同的类，我们称这样的聚类为软聚类。聚类还有分层聚类和 非分层聚类之分，其类分别是树状的或平坦的。 各种聚类方法原则上都可以用在文本聚类上。常用于文本聚类的方法有k 一均值法( k m e a n s ) 、模型估计法( m o d e le s t i m a t i o n ) ( 特别是混合模型估计法( m i x t u r em o d e l e s t i m a t i o n ) ) 、分层聚类法( h i e r a r c h a lc l u s t e r i n g ) ( 分层聚类法中又有自上而下法( d i v i s i v e ) 和自下而上法( a g g l o m e r a t i v e ) ) 。最近还有一些新方法被提出来。 2 4 1 层次凝聚聚类： 最常用的距离有： 1 ) 最小距离：用两类中样品之间的距离最短者作为两类的距离。 2 ) 最大距离：用两类中样品之间的距离最长者作为两类的距离。 3 ) 重心距离：用两类的重心之间的距离作为两类的距离。 4 ) 类平均距离：用两类中所有两两样品之间的平均距离作为两类的距离。 如果给定的文档集合是d = d 1 d j d n ，层次凝聚法的具体步骤如下： 1 ) 将d 中的每个文档看作是一个具有单个成员的类c i = d i ，这些类构成了d 的一个聚 类c = ( c 。，c ：c 。) ： 2 ) 计算c 中每对类( c 。，c j ) 之间的相似度s i m ( c 。，c j ) ： 3 ) 选取具有最大相似度的类对a r gn l a xs i m ( c 。，c j ) ，并将c t 和c j ，合并为一个新的 1 6 北京邮电人学博士论文 类c 一；uc j ，从而构成了d 的一个新的聚类c i = ( c ”g - c 。) ： 4 ) 重复以上步骤，直至c 中剩下一个类为止。 图2 - 6 层次凝聚法的聚类过程 层次凝聚法的聚类过程，形成一个层次的树状结构( 如图2 - 6 ) 所示。该树状结构中包含 了所有的层次信息以及所有的类内和类问的相似度。层次凝聚法是最为常用的聚类方法， 它可以生成层次化的的嵌套类，且准确度较高。但是这种方法运行速度较慢，不适合与大 量文档的集合。因为，在每次合并时需要全局地比较所有类之间的相似度，来选择出最 佳的两个类。因此，在本文随后两部分提出的聚类方法大大提高了文档的聚类速度。 2 4 2 k 均值聚类法 这里介绍k 一均值法，它属于非分层的硬聚类方法。k 一均值法利用向量空间模型，即将 每一样本看作为向量空间中的一个点( 向量) ，向量空间的维数是文本特征的数目。相似度 度量是平方欧几里得距离。具体算法是一个迭代算法它的结果依赖于初始值，不能保证 找到整体最优。我们先对样本进行归类，求出各个类的均值向量(