（计算机应用技术专业论文）基于文本聚类的新闻信息聚合的研究.pdf

摘要 摘要 i n t e r n e t 韵不断发展。网上新两信息的获取已成为入们鲡识来源的主要途 径。但是，随之而来的“信息爆炸”，使得人们通过搜索引擎或者浏览网页很难 从大量的地搜索结果中获取方便的、有效的信息，这也成为当今面临的挑战。 文本聚类可以对发现大量文本信息中的相互规律、潜在的联系。帮助用户从多 种视角更清晰、直观的获得信息； 本文在研究一般聚类算法的基础上，通过对互联网新闻文本信息的文本特 性的深入分析，通过对新闻文本的特征值抽取，实现了用k m e a n s 算法和后缀 树聚类算法( s t c ) 对新闻文本的处理，并通过实验验证了文本聚类算法的性能。 构造了基于文本聚类的新闻信息聚合的模型系统。该系统从大量主流新闻媒体 网站获取信息，实现了基于文本聚类对新闻信息聚合。 通过一系列实验，后缀树聚类算法由于在特征选择方面充分的考虑了文本 特性，通过引入短语特征产生了较好的聚类结果。 关键词：信息获取、文本聚类、信息聚合、后缀树算法； a b s t r a c t w i mt l l ed e v e l o p m 饥to ft h ei n t 唧e tt c c 王l r l o l o g y ，t og c ti n f o 肌a l i o nf 如mi n t 伽e t b e c o i i l et l l em o s ti i l l p o r t a i l t w a yt og e ti n f 0 咖a t i o n b u tw i mt l l e i i l f o 珊a t i c x p l o s i o n ，i ti sag r e a tc h a i l e i l g ct og c ti n f o r n l a t i 丘d ms 黜he n 舀n ea 1 1 dw 曲s i t c c o n v e l l i 锄ta n dg 腧c t i v c 。t e x tc 1 u s t 谢n gc a nf i n di n f o n n a t i o nl 删s 1 l l ep o t e l l t i a l l m l 【s 丘0 mm a s s i v ej l l f o m a t i 叩趴dh e l pu s e r st og e ii n f b n n a t i o nm o r cc l e a d y d i r 。c t l y 丘o mm u l t i p l ep e r s p e c d v 昭 b a s o d 伽m es t l l d yo ft l l eg 啪e r a ld u s t 酣n ga l g o r i t l l m 。t 1 1 r o u g ha n i n d e p t ha n a l y s i s o ft 1 1 ec h a m c t e d s t i c so fi f l t 哪e tn e w st e x ti n 如哪n a t i o f lam o d e lb a s e do nt l l e c h a m c t 甜s t i c so fn e w s 溆tw a sp r o p o s e d w i t l la l l a l y s i so ft l l ek - m e 挪d u s t 甜n g a i g 砸t h r n 龇d t h e 踟m x 仃e e ( s t c ) d u s t 砥n ga l 窖舳d e a l i n g w i m t h e n c w so f m e r e s u d e e p 坟w ed o1 0 t so fe x p 舐m 锄t c e 币矗c a t i o n 也et h ep 刮白锄a n c co f 矗e x t c l u s t e r i n ga l g o d t l l m s ，a l s oc o n s t n l c ta i n f o n n a t i o na g g r e g a t i o ns y s t e n lb a s o do nt e ) 【t d u s 涮n gt e c h n o l o 豺t h i ss y s t e mg c ti n f o f m a t i o nm a i n s 仃e a mn e w sm 耐i aw e b s i t 岱， r e a l i z ei n f o 】a t i o na g 笋e g a t i o nb a s e do i lt l l et e x tc l u s t 嘶n go f n e w s t h r o u g has e r i e so f t e s t sa n dc e 币f i c a t i o n ，t l l es u 仃i x 仃e ed u s t e r i n ga l g o r i t l l i i l ，d u et 0 t h e c h o i c e o f c o n s i d 甜n g o f t h e n e w s t e x t s c h a r a 曲嘶s t i c s ，p r o d u c e b e t t e r r e s u l t s k e yw o r d s ：i n f 嘶m a t i o na c c e s s ，1 e x tc l u s t 甜n g ，l n f 0 i m a t i o na g g r e g a t i o n ，t h e s u f f i xt r e ea l g o r i t h m ( s 代) 学位论文版权使用授权书 本人完全了解北京机械工业学院关于收集、保存、使用学位论文 的规定，同意如下各项内容：按照学校要求提交学位论文的印刷本和 电子版本；学校有权保存学位论文的印刷本和电子版，并采用影印、 缩印、扫描、数字化或其它手段保存论文；学校有权提供目录检索以 及提供本学位论文全文或者部分的阅览服务；学校有权按有关规定向 国家有关部门或者机构送交论文的复印件和电子版；在不以赢利为目 的的前提下，学校可以适当复制论文的部分或全部内容用于学术活 动。 学位论文作者签名： a 哪 劢睇 年弓月矽日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 年月日年月日 硕士学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、己公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 签名： 第l 章绪论 1 。1 选题背景 第1 章绪论 随着新闻行业竞争的日益激烈以及信息网络技术、特别是互联网技术的飞 速发展，新闻信息需求不断飞速地增长。当前，新闻用户的主体需求逐渐从阅 读新闻转向咨询服务、数据深入挖掘和多元化、全方位的综合服务。随着 i n t e r n e t 中有用信息与冗余信息的同步海量增长，用户要从中获取所需信息已 非易事。同时，互联网也已成为人们获取信息的一个重要途径，每天通过网络 区浏览新闻，进行网上冲浪已经是人们生活中必不可少的事情。然而，由于w e b 信息的日益增长，人们不得不花费大量的时间去搜索、浏览自己需要的信息。在 此情形下，采用聚类技术将用户所需要的w e b 页面聚合起来，使用户避免了网上 盲目点击和无目的阅读问题，更易于获得感兴趣的新闻信息。 文本聚类是文本挖掘的研究内容之一，涉及到许多研究领域，包括数据挖 掘、统计学、生物学以及机器学习等。聚类根据数据集中数据的不同特征，将 其划分为不同的数据类，使得属于同一类别的个体之间的距离尽可能的小，而 不同类别上的个体问的距离尽可能的大。用少数的几个类代表整个数据集会丢 失数据集的些细节信息，但这样简化了数据集的表示。通过聚类，人们能够 识别密集的和稀疏的区域，因而发现全局的分布模式，以及数据属性之间有趣 的相互关系。因此，文本聚类是一个将文本集分组的全自动处理过程。每个组 里的文本在定方面互相接近。如果把文本的内容作为聚类的基础，不同的组 则与文本集不同的主题相对应。文本聚类是一个发现文本集包含内容的方法。 近年来，可以很容易地从i n t e r n e t 、数字图书馆、新闻机构和公司内部网 上获得数目惊人的文本文档。于是，人们对发展能够帮助用户有效地导航、总 结和组织这些文本信息技术的兴趣越来越强。快速和高质量的文本聚类技术在 实现这个目标过程中扮演了重要的角色。通过将大量信息组织成少数有意义的 簇，这种技术能够提供导航浏览机制，或者，通过聚类驱动的降维或权值调整 来极大地改善检索性能。因此，文本聚类研究成为当前国际上数据挖掘的一个 重要课题。 第l 章绪论 1 2 研究背景 1 2 1 概述 在w e b 中存在大量网站，全世界有超过3 千万个网站。中文w e b 上网站的数 量有上6 6 万个，域名数量有1 8 0 多万个。网站包含有众多的文本、图片、多媒 体数据。下表描述了2 0 0 2 年全世界w e b 的数据量“1 ： 种类数据量 ( t e r a b y t e s ) 表面w e b1 6 7 深度w e b9 1 8 5 0 电子邮件信息4 4 0 6 0 6 即时消息信息2 7 4 总共5 3 2 8 9 7 表1 1 霄e b 数据量 同时我们也看到，由于数据量巨大，w e b 用户查找信息并不是很容易。2 0 0 2 年全世界有6 亿多w e b 用户，并且平均每人每月花费l l 小时2 4 分钟的时问用 来上网。w e b 用户般在网上发送和接收电子邮件，查看新闻，查找信息等活 动。w e b 用户的活动可以用下表进行初步的统计： w 曲用户行为统计 编号活动比例 1 发送和接收电子邮件5 2 2 查看新闻3 2 3使用搜索引擎查找信息2 9 4单纯的网上放松和休闲2 3 5在某一项爱好上查找信息2 1 6用i n t e r n e t 搜索来回答某一个目题1 9 7 由于工作的原因而上网研究某一项内容 1 9 8 研究某一个产品和服务1 9 9 查询天气1 7 第l 章绪论 i l o l 即时消息 l 1 4 l 表1 2 _ l r e b 用户行为统计 从上表可以看到，( 3 ) ，( 5 ) ，( 6 ) 基本上都是在做信息的查找，可以看出提高 信息聚合的效率对w e b 用户会有很大的帮助。 一方面w e b 中数据量巨大，类型丰富，含有丰富的信息，另一方面，正是由于 数量巨大，w e b 用户检索信息时需要花费很大的精力和时间。为了找到一个感兴 趣主题的相关内容，w e b 用户不可能通过人工浏览整个w e b 来查找信息，需要能够 帮助检索w e b 信息的工具。信息聚合技术为w e b 信息提供了一个单一的入口，是 为了解决w e b 数据太多，利用率低以及w e b 用户查找数据不方便的目的而设计 的。 信息聚合。1 是指从不同的数据源汇集并分析相关信息、解决这些信息在语义 方面的异构性，并提供基于数据源之间关系、业务过程的聚合等功能。 1 2 2 文本聚类及信息聚合的研究现状 当文本聚类的主要应用主要有以下几个方面： 文档聚类可以作为多文档自动文摘等自然语言处理应用的预处理步骤， 比较典型的例子是哥伦比亚大学开发的多文档文摘系统n e w s b l a s t e r 。 n e w s b l a s t e r 将每天发生的重要新闻文本进行聚类处理，并对同主题文档进行冗 余消除、信息融合、文本生成等处理，从而生成一篇简明扼要的摘要文档； 对搜索引擎返回的结果进行聚类，使用户迅速定位到所需要的信息。 h u a _ j u nz e n g 等人提出了对搜索引擎返回的结果进行聚类的学习算法。比较典 型的系统则有v i v i s i ( h t t p ：w w w v i v i s i m o c o m ) 和 i n f o n e t w a r e ( h t t p ：w 啊i n f o n e t w a r e c 伽) ，还有g o 0 9 1 e ( h t t p ：蚋哪9 0 0 9 1 e c o m ) 等。 系统允许用户输入检索关键词，而后对检索到的文档进行聚类处理，并输出各 个不同类别的简要描述，从而可以缩小检索的范围，用户只需关注比较有希望 的主题。另外这种方法也可以为用户二次检索提供线索； 对用户感兴趣的文档( 如用户浏览器c a c h e 中的网页) 聚类，从而发现 用户的兴趣模式并用于信息过滤和信息主动推荐等服务。目前，g o o g l e 已经在其 咨询频道开始应用。如下图： 第l 章绪论 图1 1 用户推荐 聚类技术还可以用来改善文本分类的结果，如俄亥俄州立大学的y c f a n g ，s p a r t h a s a r a t h y 和f s c h w a r t z 等人的工作。 数字图书馆服务。通过s o m 神经网络等方法，可以将高维空间的文档拓 扑保序地映射到二维空间，使得聚类结果可视化和便于理解，如s o m l i b 系统； 文档集合的自动整理。如s c a t t e r g a t h e r 是一个基于聚类的文档浏览 系统。而微软的j i r o n gw e n 等人则利用聚类技术对用户提出的查询记录进行 聚类，并利用结果更新搜索引擎网站的f a q 。 对新闻信息的进行聚合的研究和应用有：百度( h t t p ：n e w s b a i d u c o m ) ， y a h o o ( h t t p ：c n n e w s y a h o o c 0 硼) ，g o o g l e ( h t t p ：n e w s g o o g l e c o m ) ， 基本上都是聚合主流新闻媒体的新闻信息，采用自动分类排列显示，并提供新 闻检索服务。这其中，百度和y a h o o 的新闻频道主要采用文本自动分类的技术 对新闻进行分类，对新闻的检索也是普通的检索，对结果没有采取进一步的处 理。g 0 0 9 l e 应用了文本聚类技术对对用户感兴趣的文档( 如用户浏览器c a c h e 中的网页) 聚类，从而发现用户的兴趣模式并用于信息过滤和信息主动推荐等 第1 章绪论 服务。 目前，在聚类领域比较有影响力的应用a q u a b r o w s e r ，g r o k k e r ，a n d v i v i s i i l l 0 。a q u a b r o w s e r 定位为图书馆搜索，v i v i s i m o 和g r o k k e r 则定位为 i n t e r n e t a q u a b r o w s e r 的特点是发现( 可视化) 和结果限定( 分类) 。v i v i s i m o 的特点是自动聚类( 文本方式) 。g r o k k e r 是图形化。三者都是对结果引入智能 化。v i v i s i m o 利用聚类技术层次化地分类呈现搜索结果，在方便用户获取有用 信息上胜出一筹。以下是我在v i v i s i m o 上搜索n b a 的结果呈现。左边是根据内 容聚类的结果，右边是点击“s t a t i s t i c s ”后出现的细类条目。 如图所示，在左侧清晰直观显示了查询。n b a 后的聚类树。非常方便于阅读 相关新闻。不同的用户可以根据自己的兴趣去选择相应的目录。 1 2 3 发展趋势 图1 2 英文文本搜索结果聚类 第l 章绪论 文本聚类是一种有效的文本挖掘方法，能从大量文本数据中发现潜在的知 识和规律，它既是一个知识获取技术，也是一种文本处理过程。下面分几个方 面来探讨一下文本聚类研究的发展已应用的趋势。 许多搜索引擎专家表示，文本聚类技术较传统的网页级别系统更为方便好 用。据专门报导网路搜寻业的网站s e a r c h e n g i n e w a t c h 编辑，同时是图书馆员 的普莱斯指出，随著资料库日益变大，试图在如大海般广阔的资讯中找出想要 的资讯也变得愈来愈难，所以使用者需要额外的帮助。v i v i s i j 刀。的创办人之一 兼执行长瓦德斯一裴瑞兹指出，传统的搜索引擎擅长于尽可能地爬梳更多的网页 资料，但聚类的的重点则是要解决资讯爆炸的问题，他认为重点就是要“忽略 资讯”，也就是找出能排除不相干资讯的技术。 文本聚类技术是下一代搜索引擎等领域的关键技术有着非常广泛的应用前 景和市场前景。有代表性如b b m a 阳r e b 2 o 模式的聚合搜索正在不断兴起。 2 4 文本聚类的基本步骤 文本聚类的方法有很多，文本聚类一般分为5 个步骤： s t e p l ：模式表示，包括特征抽取与选择，把文本表示成可计算的形式 s t e p 2 ：根据领域知识定义模式之问的相似度计算公式 s t e p 3 ：聚类或者分组 s t e p 4 ：网页簇排序 s t e p 5 ：数据抽象表达 s t e p 6 ：评价输出结果 1 3 论文结构 本文共分七章： 第一章绪论，介绍文本聚类的基本概念、研究内容、发展现状以及相关技 术等，为我们下面的研究奠定理论基础。 第二章新闻文本于处理及相关的技术。 第三章几种典型的聚类的算法的分析与比较。 第四章改进的新闻信息文本聚类算法。 6 第l 章绪论 第五章多媒体新闻信息聚合系统，包括系统结构及工作流程、各模块的实 现。 第六章全文总结，概括本文的观点和结论，介绍了本文的研究背景、研究 内容、研究方法及本文特点。最后提出了今后工作的展望。 论文提出利用文本聚类技术对搜索结果进行自动分类，为搜索结果提供一 个大概视图以提高搜索结果的浏览效率，并且提供一个更加友好的用户界面。 本文在研究一般聚类算法的基础上，通过对互联网新闻文本信息的文本特 性的深入分析，提出了基于新闻文本的特征值模型。实现了用k - m e a n s 算法和 后缀树聚类算法( s t c ) 对新闻文本的处理，并通过实验验证了文本聚类算法的 性能。构造了基于文本聚类的新闻信息聚合的模型系统。该系统从大量主流新 闻媒体网站获取信息，实现了基于文本聚类对新闻信息聚合。 通过一系列测试和验证，后缀树聚类算法由于在特征选择方面充分的考虑 了文本特性，通过引入短语特征产生了较好的聚类结果。 第2 章向晕空间模型及相关技术 第2 章新闻文本预处理及采用的相关技术 2 。1 新闻文本的特性分析 本章将对新闻文本的特征进行深入分析，明确新闻文本的要素组成，针对 新闻的各项特征提出新闻文本聚类的技术框架，并探讨其中所涉及的关键技术。 新闻属于半结构化的数据，介于结构化与非结构化之问，同时具备结构化 数据与非结构化数据。例如：新闻文本包含记者名字、报道日期、报道地点等结 构化部分与事件描述的非结构化部分。综合分析新闻文本，其主要有以下几个 特性嘲： 1 文本结构：简单性 新闻文本结构的简单性主要表现在这样儿个方面： 新闻文木的结构形式相对单一，倒金字塔结构形式被比较一致地认为它是 新闻传播最有效的结构形式，是最为成熟的新闻文本结构形式。 鲁慝室奉 麓翔蠢童 曹基 夺耘蠢 量蔫 图2 】新闻文本拓扑结构图 2 首段摘要j 撰写特色 重要的概念( 关键词条) 大多出现在首段 3 文本语言：明确性 8 第2 章向量空闻模型及相关技术 新闻文本语言的明确性是以新闻接受主体的易受性为标准的，即文本的语 言叙述要让普通阶层的人感到鲜明清晰，传播者对新闻事实的叙述不能故弄玄 虚，而要自觉去掉那些容易引起多义、模糊特别是歧义的叙述符号和叙述方式。 新闻文本的本质在于为受众提供明白清晰的事实信息，因而会尽量避免因文本 语言不明确导致的主观解或曲解。 4 文木词汇：新词多 新闻文本主要报道每天发生的重要事件，涉及面广、题材多，其内容更新 很快。相对来说，如今的字典虽然规模在不停的扩大，但是仍然远远落后于社 会的发展，新人、新的概念和观点层出不穷，大量的新词也随之不断涌现，字 典面临逐渐老化的问题。因此，新闻文本中新词的出现非常频繁，尤其发生在 科技和财经领域。另外，新的人名、地名和机构名称等名词也频繁出现。 2 2 向量空间模型 向量空间模型( v s m ) 埘是s a l t o n 等人于6 0 年代末首先提出的，并在著名 的s 凇r t ( s y s t 鲫f o rt h em a n i p u l a t i o na n dr e t r i e v a lo ft e x t ) 系统得到成 功的应用。从此以后，该模型及其相关技术，包括项的选择、加权策略，以及 采用相关反馈进行优化查询等在文本分类、自动索引、信息检索等许多领域得 到广泛的应用。特别是随着网上信息的迅速膨胀，还被广泛地应用到搜索引擎、 个人信息代理、网上新闻发布等信息检索领域新的应用中，并且取得了较好的 效果。 l 文档( d o c u 砸e n t ) ：泛指一般的文本或者文本中的片段( 段落、句群或句子) 一般指篇文章。尽管文档可以是多媒体对象，但是以下讨论中本文只认为是 文本对象，文本与文档不加以区剐。 2 项( t e r m ) ：文本的内容特征常常用它所含有的基本语一言单位( 字、词、 词组或短语等) 来表示，这些基本的语言单位被统称为文本的项，即文本可以用 项集( t e n l ll i s t ) 表示为d ( t l ，t a t 3 ，t 。) 。 3 项的权重( t e 瑚i g h t ) 4 向量空间模型( v 铡) 5 相似度( s i m i l a r i t y ) ：两个文本d ，和d ：之问的( 内容) 相关程度( d e g r e e o fr e l e v a n c e ) 常常用它们之间的相似度s i m ( d ，d 。) 来度量。当文本被表示为向 9 第2 章向量空间模型及相关技术 量空间模型时。可以借助于向量之间的某种距离来表示文本间的相似度，常用 向量之间的内积进行计算： s i m p l d 2 ) 。k 岵 “ ( 2 1 ) 或者用夹角余弦值来表示 嵋。 s l m ( d l ，d 2 ) = 嘲疗一 如图( 2 2 ) 所示： ( 2 2 ) 啦。) ) 图( 2 2 ) 文本的向量空间模型( v s m ) 以及文本问的相似度s i m ( d l ，d 2 ) 2 3 新闻文本项的选择 如前所述，项可以是文本中的各种语言单位，特别是对中文来说有字，词， 短语，甚至是句子或句群等更高单位项也可以是相应词语或者短语的语义概念 类。因此，项的选择只能由处理速度，精度，存储空间等方面的具体要求来决 定。选出的项越具有代表性，语言层次越高，所包含的信息就越丰富，但是分 析的代价就越大，而且受分析精度( 如句法分析的正确率) 的影响就越大。由于 词汇是文本最基本的表示项，在文本中的出现频度较高，呈现一定的统计规律， 再考虑到处理大规模真实文本所面临的困难，选择词或者短语作为特征项是比 较合理的，常常被应用于文本检索与分类领域。但是直接选用文本中的词或者 l o 第2 章向量空闻模型及相关技术 词组作为文本特征项时也会出现以下问颓“埘： l 文本中存在一些没有实在意义但使用频率很高的虚词和功能词，如英语 中的“t h e ”，“a ”，“o f ”等，常常把一些真正由分类作用的实词淹没掉。 解决这个问题的方法是把这些词组织成一个禁用词表，去除停用词，合并数字 和人名等词汇，把禁用词表中的词从特征集中滤掉。去除停用词，合并数字和 人名等词汇。此外，还可以在文本预处理时进行词性标注，从词汇特征集中滤 去那些对特征区别贡献极小的大部分虚词和功能词。 2 一词多义或词汇变形问题。事实上，自然语言有着极为丰富的语言现象。 例如词汇之间的关系，就有同义关系、近义关系、从属关系、关联关系等等。 在使用短语等复合词时关系就更加复杂了。另外词汇的歧义和多义也很普遍， 例如”c o n s 0 1 eaf r i e n di ng r i e ，( c o n s 0 1 e 意义为安慰) ，。l o g i ni n t oo n e c o n s o l e ”( 这里的c o n s o l e 指的是计算机中的终端) ，因此，不同的词义当作不 同的项来看待会更合理。词汇变形问题主要是指西文单词有复杂地词尾变化和 派生现象。解决这些问题常有两种办法：第一种是进行概念语义标注，以便把同 义的或相似的特征项合并为相应的概念类。对于西文，可以通过特别的抽取词 干处理，把同源的词用同一个词干来标记。显然，通过概念标注并利用概念信 息作为文本的特征项比单纯的词汇信息更能反映文本的内容。因此，词义相同 或者详尽的词汇往往被映射为同一个概念，而同一词汇所表示的词义也是和上 下文相关的，把词汇在具体的上下文中所对应的概念作为文本的描述项，那么 内容相似而仅在用词上有较大差异的文章，彼此之间的相似度就会大大增加。 所以采用概念作为特征项是比较合理的。但是这样做的同时势必加大了文本处 理的复杂程度。 2 4 新闻文本项的权重计算 在确定了原始特征项，并通过某种特征提取方法得到了二次特征之后，另 一个很重要问题就是特征项的权重问题。目前最普遍的赋权重方法是运用统计 方法，即用文本的统计信息，主要是词频，来计算特征项权重。被广泛应用的 权重计算公式是t f i d f 御公式： 留) = 毵酗) 岫+ o 0 1 第2 章向量空间模型及相关技术 其中，t f 。( d ) 为词条t ，在文档d 中的出现频率，n 为所有文档的数目，n 为含有词条t 的文档数目。我们可以这样理解向量空间中的每一个分量：每个分 量刻画了项t 区分文本内容属性的能力，一个项在文本集中出现范围越广，说 明它区分文本内容属性的能力越低；在一个特定文本中出现频度越高，说明它 在区分该文本内容属性方面的能力越强。 考虑到文本长度对权重的影响，还应该对项权重公式做归一处理，将各项 权重规范到f o ，l j 之间。 另外，标题、副标题和关键字表中出现的词汇和短语，在设置权重时应单 独考虑，使其具有较高权重。多年实验表明，t f i d f 是文本处理的一个有效工 具。事实上，这一公式不仅在信息检索中得到了成功应用，它对其他文本处理 领域，如信息分发、信息过滤和文本分类也有很好的借鉴意义。 彬瞄) = ( 2 3 ) 经过以上步骤，得到一个列维数较少的文档特征矩阵，矩阵中行代表文档， 列代表特征。 2 5 新闻文本特征值抽取 首先，提取新闻文本中表达整个事件最核心的部分。主要包含三个部分： 1 文本的标题部分，摘要部分。绝大多数的新闻文本，都可以通过文本的 标题和摘要部分，就可以获取事件的基本的特征，从中可以提取描述事件的短 语和关键词。 2 提取特定文本的元数据。如图2 3 所示： 第2 章向鼍宅间模型及相关技术 2 6 分词和词频处理 图2 3 元数据提取 分词才用词库的最大匹配分词算法。其过程很简单，首先准备一个词 库，顺序扫描待分词的句子，将句中候选词按照从大到小的顺序依次跟词库中 的词进行匹配，匹配成功即作为一个词输出。最大匹配分词算法的流程图如图 2 。5 所示。 在得列了所用的己分词的语料后我们还需采用的预处理步骤为： ( 1 ) 统计语料中所有出现的词汇及其出现频率和出现次数 就是对所有语料进行一次扫描，扫描的程序并不复杂，只是汉字是两个字 节的机器内码表示的，并且每个字节的内码其值大于十六进制的a o ( o x a 0 ) 。注 意这一点就可以正确扫描到所有的词汇及其频率。 ( 2 ) 去除平凡词 高居统计频率榜首的是“在”、“了”、“和”、“的”等对文章意义贡献不大 的平凡词，在我们的实验中这些词也被过滤而不考虑。 在本文中，采用的分词方法是由中国科学院计算技术研究所的i c t c l a s 系 第2 章向量空间模型及相关技术 统，在这个系统中对于分好的词进行了词性的标注。 图2 5分词流程 ( 3 ) 去除出现频率较低的词 如大量的词其频率小于3 ，这些词一般对聚类的贡献也不大，因此也去除它们。 第3 章聚类算法 第3 章聚类算法 3 1 引言 a 问题背景 聚类是对数据对象进行划分的种过程，与分类不同的是，它所划分的 类是未知的，故此，这是一个“无指导的学习”( u n s u p e r v i s e dl e a r n i n g ) 过 程，即聚类算法不需要“教师”的指导，不需要提供训练数据，它倾向于数据 的自然划分。 文本聚类( t e x tc l u s t e r i n g ) ：将文本集合分组成多个类或簇，使得 在同一个簇中的文本内容具有较高的相似度，而不同簇中的文本内容差别较大。 它是聚类分析技术在文本处理领域的一种应用。 b 问题描述 1 划分聚类 给定： 个文档的集合d = ，d 。，d d 一个相似度的度量方法 一个划分的准则( c r e t i r i o n ) 个期望的聚类数量k 计算： 一个赋值函数j t ：dj 1 ，k ) 7 满足划分的准则，使用指定的相似度计算方法 2 聚类一般过程 幽3 1 聚类般过程 3 。2 聚类算法涉及的各类型数据 ，? 巨引 l “_ i l l 饩j 图3 1 数据矩阵 相异度矩阵存储n 个对象两两之间的近似性，表现形式为一个n 书n 的矩 囊 雄舯 口 d t ) d 取2 ) o ；! d ( 丑。nd ( n 2 ) b 固( 3 。2 ) 榴异度矩阵 矩阵中的d ( i ，j ) 表示对象i 和对象j 之间的相异性，通常它是一个非负的 数值，当对象i 和对象j 越相似或接近时其值越接近o ：两个对象越不同其值就 越大。因此有d ( i ，j ) = d ( j ，i ) ，d ( i ，i ) ：o 数据矩阵通常被称为二模矩阵，而相异度矩阵称为单模矩阵，这是因为前者 的行和列代表不同的实体而后者的行和列代表相同的实体。实际中很多聚类算 法是以相异度矩阵为基础的。 1 6 第3 章聚类算法 3 3 现阶段比较典型的集中聚类算法 目前，已经提出的聚类算法有很多，可以在此仔细分析研究它们的具体性 能、优势与缺点，明确它们所适合的具体情形，当然，这些算法一般都存在这 样或那样的不足，对于一些情况无能为力。因此，在使用这些聚类算法的时候， 必然要与具体情况相结合，做出一些相应的调整。一般来说这些算法可以分为 如下的几类： 3 3 1 划分方法( p a r t i 硼i n g _ e t h o d ) 给定一个n 个对象或元组的数据库，一个划分方法构建数据的k 个划分， 每个划分表示一个聚簇，并且k n 。也就是说它将数据划分为k 个组，同时满足 如下的要求：( i ) 每个组至少包含一个对象：( i i ) 每个对象必须属于且只属于一 个组。 给定要构建的划分的数目k ，划分方法首先创建一个初始划分。然后采用一 种迭代的重定位技术，尝试通过对象在划分问的不断移动来改进划分。一个好 的划分的一般准则是：在同一个类中的对象之间尽可能的接近或相关，而不同类 中的对象之问尽可能的远离或不同。 实际上绝大多数应用采用了以下比较流行的启发式算法：( i ) k 一平均算法， 在该算法中每个簇用该簇中对象的平均值来表示。( i i ) k - 中心点算法，在该算 法中，每个簇用接近聚类中心的一个对象来表示。这些启发式聚类方法对在中 小规模的数据库中发现球状簇很适用，而且其实现相对的简单。但是它不能发 现任意形状的簇，其参数k 对聚类结果有很大的影响，很影响聚类的质量而且 这类算法不具有很好的伸缩性。要对大规模的数据集进行聚类以及处理复杂形 状的聚类就要对基于划分的方法做进一步的扩展。 如下为当前最常用最流行的两个经典算法的详细阐述： 1 k 一平均算法( k m e a n s ) “”的具体步骤如下： 输入：簇的数目k 和包含n 个对象的数据库 输出：k 个簇并且使平方误差准则最小 1 假设要聚成k 个类。由人为决定k 个类中心五( 1 ) ，磊o ) z i ( 1 ) 2 在第k 次叠代中，样本集f zj 用如下方法分类： 对所有i = 1 ，2 ，k ，i 不等于j 若娶z 一互 ) | i i z 一五( 七竭，则z e 只( 七) 3 令由 2 ) 得到的q ( 詹) 的新的类的平准值为乙罅+ 1 ) ， 令小：到z 一乃 + 埔最，j 、小l ，2 ，k 乙o + 1 ) = 古z ，哆：薯( 幻 则 ”嘶哪 中的样本数。 对于所有的j ：1 ，2 ，k ，若乙 + 1 ) 。乙( 的，则终止。否则继续再从 + o 密3 3 ) l r 平均值法迭代图铡 这个算法尝试找出使平方误差函数值最小的k 个划分。当结果簇是密集的， 而簇与簇之问区别明显时它的效果很好。但是k 一平均方法只有在簇的平均值被 定义的情况下才能使用，这可能不适用于某些应用，例如涉及分类属性约数据。 要求用户必须事先给出k ( 要生成的簇的数目) 可以说是该方法最大的缺点，而且 k 一平均方法不适合于发现非凸面形状的簇，或者大小差别很大的簇，与此同时 它对于“噪声”和孤立点数据很敏感，少量的该类数据能够对平均值产生大的 影响。此算法不仅对参数k 的选择很敏感而且对最初始簇中心的选择也具有很 大的依赖性。不同的初始类中心选择可能会产生不同的聚类结果。它的流行主 要在于它的实现很简单。 针对卜平均算法对“噪声”和孤立点数据的敏感性，对其进行改迸出现k 一 中心点方法。 2 k 一中心点算法具体步骤如下： 输入：结果簇的数目k ，包含n 个对象的数据库 输出：k 个簇，使得所有对象与其最近中心点的相异度总和最小 1 假设要聚成k 个类。由人为决定k 个类中心z 。( 1 ) ，z ：( 1 ) ，z 。( 1 ) 1 8 第3 章聚类算法 2 若l z 一互l | | z 一乞2 ，则z e s ，焉为以z 。为中心点的簇，对所有的 i = 1 ，2 ，k ，i 不等于j 3 ) 在每次叠代中， 对所有i = l ，2 ，k ，随机从以z i 为中心点的簇中取z o 若荟i z z ，l 荟i z 一互8 ，其中z 为簇中的每一个对象，则用z r 代替z t 为中心点。 4 由( 3 得到的新的类的中心点 ，= 肛一z f i 令 mz 鹏 最小，i = 1 ，2 ，k z 为以z ，为中心点的簇中的对象 5 若j 已经达到最小或不再变化，则终止。 ：羔l 畸 一i 嘈 图( 3 4 ) k 一中心点过程图例 当存在“噪声”和孤立点时k 一中心点方法比k - 平均方法更健壮，这是因为 中心点不像平均值那样那么容易受极端数据的影响。但是由于k 一中心点方法试 图找出最好的中心点，它对所有的数据对象进行分析，对可能的各种组合估算 聚类结果的质量，因此它的执行代价比k 一平均值方法高，而且这种方法仍要求 指定结果簇的数目k 。 k 一中心点方法对于小的数据集非常的有效，但对于大的数据集没有良好的 可伸缩性，为了处理较大的数据集合，可以采用基于选择的方法c l a r a ( c l u s t e r i n gl a r g ea p p l i c a t i o n ) ，它的主要思想是不考虑整个数据集合，选 1 9 第3 苹聚类算法 择实际数据的小部分作为数据样本，然后对选出的样本使用k - 中心点方法。 如果样本是以非常随机的方式选取的它应当足以代表原来的数据集合。但是如 果样本发生偏斜，随机样本的一个好的聚类不一定代表了整个数据集合的一个 好的聚类。因此最好是把采样技术和k 一中心点方法相结合。但是不管如何这些 方法始终需要用户指定结果簇的数目k ，这是可能是他们共同的最大的不足之 处。 3 3 2 层次方法( h i e r a r c h i c a i _ e t h o d ) 层次方法对给定的数据对象集合进行层次的分解。根据层次的分解如何形 成，层次的方法可以分为凝聚的和分裂的两种凝聚的方法，也称自底向上的方 法，一开始将每个对象作为单独的一个组，然后相继的合并相近的对象或组， 直到所有的组合并为一个( 层次的最上层) ，或者达到某个要求的终止条件。分 裂的方法，也称为自顶向下的方法，一开始将所有的对象雹于一个簇中。在迭 代的每一步中，一个簇被分裂为更小的簇，直到最终每个对象在单独的一个簇 中，或者达到一个终止条件。具体过程如下( 图3 5 ) 所示： 坐：竺堂竺兰! ! ! ! ! 竺堕竖露麓麓澄鍪戮霜戮鍪豳鍪罂翟圉 s t 印os ：唧1 产2 ：婶3 ：却4a g g l o m e r a l i v e 上j l 上_ l 叫。丽磊 s 姊4s 饴p 3s 唧2s l e p ls t e p o d i 、，l s i v e ( d 乳蛾a ) 图( 3 5 ) 数据对象 a b ，c ，d ，e 的凝聚与分裂 现在算法研究主要集中在凝聚层次聚类方面，分裂方面的很少。其中凝聚 方面，可以按照的思路就是：寻找“距离”最近的两个样本结合。这个算法步骤 如下： 2 0 第3 章聚类算法 数。 有n 个样本的集合s 2l 乙，z 2 ，z 若想要聚成k 个类，其中k 要预先指定。 1 k = n ，c l ； 五) i = 1 2 ，n 【2 ) i fk =kt h e n 啪 【3 找到q 与c ，之弼的矩离d ( q 。q ) 最小的一对 f 4 c 与c ，台并成一个类qt 并计算新的c i 的中心 5 】去除c ，k = l 【一l 。然居转到第二步 类间距离d ( c i ，q ) 的度量可以有以下四种： 1 中心间距：d ；= 孵一够l ，其中m 2 专萎z ，n i 是属于c i 的样本 罂 。 2 距离最近的样本：盔互置g ，乙e q l 互一乙l 哭 。 3 距离最近的样本：赡= z f 毫c f ，乞萤q i 互一乙l 4 1 类间平均距离正。音丕聂l z _ z ，l _ c 4 类间平均距离： v jt ：，墨 c l饶岛c c l 图( 3 6 ) 层次方法图例 相似接尺度 6 9 7 0 8 0 9 0 1 0 0 层次聚类方法虽然很简单，但是它经常的遇到合并或分裂点选择的困难。 合并和分裂点的选择是非常关键的，因为一旦一组对象被合并或者分裂，下一 步的处理将在新生成的簇上进行，已做的处理不能被撤消，聚类之间也不能交 换对象，这样做不用担心组合数目的不同选择，相对来说计算代价会较小。但 另一方面造成的后果是如果在某一步没有很好的选择合并和分裂点，则可能会 导致低质量的聚类结果。而且由于合并和分裂的决定需要检查和估算大量的对 第3 章聚类算法 象或簇，这种聚类方法不具有很好的可伸缩性。 改进层次方法聚类质量的一个很有前途的方向是把层次聚类和其他聚类方 法相结合起来，形成多阶段的聚类。下面将讨论的b i r c h 算法就是其中有代表 性的一种，它首先用数结构对对象进行层次划分，然后采用其他的聚类算法对 聚类结果进行求精。它采用最多的聚类算法是划分方法方面的。 b i r c h 算法的核心是用一个聚类特征三元组c f 总结了一个簇个体的有关信 息，从而使一个簇内的点的表示可以用相对应的聚类特征而不必用具体的对象 点，通过构造满足分支因子和簇直径限制的聚类特征树来求聚类，具体如下： 对于一个具有n 个d 维数据点的类x ，( i = 1 ，2 ，n ) ，它的聚类特征向量 定义为： 汀* ( 板朋，鼢 ( 3 1 ) 一 y 置 其中n 为类中点的个数，工s 表示n 个点的线性和，冒反映了类的重心 s s 表示n 个点的平方和喜槲，反映了直径的大，j 、。 螭蹑 图( 3 7 ) c f 树结构 此外对于聚类特征有如下的定理： 。 假设易现+ 1 1 s ls 打和= ( 鸩，碣，蕊) 分别为两个类的聚类特征，两 个类合并后形成的新类的聚类特征为： 嬲+ 职e 弼+ 鹄，蠲+ 碣，磷+ 蹋 以们 该算法通过聚类特征可以方便的进行中心、半径、直径和类内、类间距离 的计算。 算法的聚类特征树是一个具有两个参数：分支因子b 和类直径t 的高度平衡 树，分支因子规定了树的每个节点子女的最多个数，而类直径体现了对一类中 点的直径大小的限制，即这些点在多大范围内可以聚为一类。非叶子节点为其 第3 章聚类算法 子女中的最大关键字，可以根据这些关键字进行插入索引，它总结了其子女的 信息。 聚类特征树可以动态的构造，因此不要求所有的数据读入内存而可以在外 存中逐个的读入数据项，新的数据项总是插入到树中与该数据距离最近的叶子 中，如果插入后使得该叶子的直径大于类直径t 那么则把该叶子节点分裂。其 他叶子节点也需要检查是否超过分支因子来判断其分裂与否，直至该数据插入 到叶子中，并且满足不超过类直径，丽每个非叶子节点的子女个数不大于分枝 因子。可以通过改变类直径大小，修改特征树大小来控制其占内存容量。 b i r c h 算法通过一次扫描就可以进行较好的聚类，而且其具有较好的伸缩 性，由此可见，该算法适合于大型数据库。但b i r c h 算法在聚类的过程中借助 了直径来作为进行聚类的一个要求因此它只适用于类的分布呈凸形及球形等情 况，并且由于b i r c h 算法需提供正确参数：聚类个数k 和簇直径t ，这两个参数 在聚类时很难确定而且对于不可视的高维数据是不行的。 3 3 3 基于密度的方法( d e n s i t y b a s e dm e t h o d ) 绝大多数划分方法基于对象之间的距离迸行聚类。这样的方法只能发现球 状的或凸形的簇，而在发现任意形状的簇上遇到了困难。在这种情况下提出了 基于密度的另一类聚类方法。其主要思想是：只要临近区域的密度( 对象或数据 点的数且) 超过某个