（计算机应用技术专业论文）基于文本聚类的网页消重算法研究.pdf

摘要 随着网络技术的迅速发展和互联网规模的不断扩大，互联网已经成为了全球 最大、最广泛使用的信息库，人们能够获得的信息资源也同益丰富。网络信息的 指数级膨胀给信息检索带来了巨大的困难，并且网络信息的易复制性使得网络中 存在大量的重复信息，因此，发现并消除重复信息的研究工作具有重要意义。 本文首先对传统的文本聚类方法和网页消重方法进行了研究，总结了它们各 自的优缺点。并结合两种聚类算法的优点，提出b i s e c t i n gk m e a n s - i - f 聚类算法，通 过u c i 数据集的测试评估，验证了它在聚类的最大凝聚度，正确率以及时间丌销 方面都比较理想。 然后，本文通过t i d y 将w e b 文档转换为格式良好的h t m l 文档，并利用d o m 解析成树状结构。由于网页数据存在噪音的特点，文中提出最大正文块算法用于 特定网页集合的噪声去除和正文块发现，并验证了它的可行性。并在经过最大正 文块去噪后的网页集合对b i s e c t i n gk m e a n s + + 算法和前n 项高频词m d 5 值算法进 行比对实验，发现它在查准率和查全率上有优势，但在时间开销上略逊一筹。 在b 2 b 门户网站信息抽取项目的公司信息整合模块中，以前的基于关键词和 向量空间模型的消重算法已经无法胜任。面对实际应用中遇到的问题，文中提出 了把实体识别方法应用到重复公司信息发现中，通过公司信息的整合，一方面消 除了重复数据，节省了存储空间，提高了搜索引擎的用户体验；另一方面挖掘出 了公司的详细信息，并为用于产品检索的质量排名算法提供了评分依据。 关键词：文本聚类；向量空间模型；网页消重；d o m 树；最大j 下文块；实体识别 分类号：t p 3 9 1 1 a bs t r a c t a st h ew o r l dw i d ew e b g r o w sr a p i d l yt ob e c o m et h el a r g e s ta n dt h em o s tp o p u l a r s o u r c eo fr e a d i l ya v a i l a b l ei n f o r m a t i o n ，i ti s i n c r e a s i n g l ya b u n d a n tt oa c c e s st o i n f o r m a t i o ns o u r c e s b u t ，b e c a u s eo f e x p a n s i o n so fn e t w o r ki n f o r m a t i o n a ta n e x p o n e n t i a lr a t e ，p e o p l ee n c o u n t e rn u m e r o u sd i f f i c u l t i e si ni r ( i n f o r m a t i o nr e t r i e v a l ) m e a n w h i l e ，w i t hw e bp a g e sb e i n ge a s yt oc o p y , n e t w o r ks e r v i c e sa b o u n dw i t hd u p l i c a t e i n f o r m a t i o n c o n s e q u e n t l y , t od e t e c ta n de l i m i n a t et h o s ep a g e si nf a c s i m i l ei so fg r e a t s i g n i f i c a n c e i nt h ef i r s tp l a c e ，t h i sp a p e ri n t r o d u c e st r a d i t i o n a ld o c u m e n t c l u s t e r i n ga l g o r i t h m s a n dt h ed u p l i c a t ep a g ed e t e c t i o nt e c h n o l o g y , a n a l y z i n ga n ds u m m a r i z i n ga d v a n t a g e s a n dd i s a d v a n t a g e so fb o t hm e t h o d sr e s p e c t i v e l y b ym a k i n gu s eo ft w oo r i g i n a l c l u s t e r i n ga l g o r i t h m s ，t h i sp a p e rp r o p o s e sb i s e c t i n gk l l l e a l l s - h - c l u s t e r i n ga l g o r i t h m t h ee x p e r i m e n t so nt h eu c id a t as e t ss u g g e s ti t ss s ev a l u e ，d e m o n s t r a t i n gt h e e f f e c t i v e n e s sa n de f f i c i e n c yo ft h ec o r r e c tr a t eo f c l u s t e r i n ga n dr u n t i m e f u r t h e r , i nt h i sp a p e r , w e bd o c u m e n t sa r ec o n v e r t e dt ob eh t m ld o c u m e n t sw i t h g o o df o r m a tb yt i d ya n dp a r s e dt od o mt r e es t r u c t u r e a c c o r d i n gt oc h a r a c t e r i s t i c so f t h ew e bp a g ew i t hn o i s e ，w ep r o p o s et h em a xt e x tb l o c ka l g o r i t h m t h i si n n o v a t i v e a p p r o a c hs h o u l db eu s e dt oe l i m i n a t en o i s e so fw e bp a g e sa n dd i s c o v e ri m p o r t a n tt e x t b l o c k sa n dc o m p r e h e n s i v ee v a l u a t i o nv e r i t i e si t sf e a s i b i l i t y t h ee x p e r i m e n t so nw e b p a g e sd e n o i s e db yt h em a xt e x tb l o c ka l g o r i t h ms u g g e s tt h eb i s e c t i n gi o n e a n s + + a l g o r i t h ms h o u l db ea v a il a b l ei nt h ep r e c i s i o na n dr e c a l l ，a n dt h em d 5v a l u eo ft o pn h i g h - f r e q u e n c yw o r d sa l g o r i t h mi nt i m ee x p e n d i t u r e l a s t l y , t h eo r i g i n a la l g o r i t h m sw i t hk e y w o r d sa n dv s m ( v e c t o rs p a c em o d e l ) h a v eb e e nu n a b l et oc o m p l e t et h et a s k ，w h i c hi n t e g r a t ec o m p a n yi n f o r m a t i o ni nt h e i n f o r m a t i o ne x t r a c t i o np r o j e c to fb 2 bw e b s i t e s w i t hp r a c t i c a lp r o b l e m s ，t h ee n t i t y i d e n t i f i c a t i o nt e c h n i q u es h o u l db e a p p l i e dt ot h ed e t e c t i o no fd u p l i c a t ec o m p a n y i n f o r m a t i o n t h ei n t e g r a t i o no fc o m p a n yi n f o r m a t i o n ，o nt h eo n eh a n d ，e l i m i n a t e st h e d u p l i c a t ed a t a ，s a v e ss t o r a g es p a c ea n di m p r o v e su s e l e x p e r i e n c ew i t hs e a r c he n g i n e , o n t h eo t h e rh a n d ，i tc o u l dm i n ed e t a i l e dc o m p a n yi n f o r m a t i o na n dp r o v i d e sas c o r eb a s e d o nf o rq u a l i t yr a n ka l g o r i t h m k e y w o r d s ：d o c u m e n tc l u s t e r i n g ；v e c t o rs p a c em o d e l ；d u p l i c a t ew e bp a g e d e t e c t i o n ；d o mt r e e ；m a xt e x tb l o c k ；e n t i t yi d e n t i f i c a t i o n c l a s s n o ：t p 3 9 1 1 v 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 签字同期：乙嘲年6 月3 日 导师签名： 签字日期：膨莎妙日 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位论文作者签名：幽嵌 签字r 期： 溯年月3 同 致谢 本论文的工作是在我的导师于剑教授的悉心指导下完成的，于剑教授渊博的 学术知识，严谨的治学态度和科学的工作方法使我受益匪浅，为我的工作和学习 树立了榜样。在此衷心感谢两年来于剑老师对我的关心和指导。 于老师悉心指导我完成了实验室的科研工作，在学习上和生活上都给予了我 很大的关心和帮助，在论文的撰写过程中给我提出了许多宝贵的修改意见。 感谢计算机所人工智能实验室各位老师的指导和帮助，他们给予了我许多启 发性的思想和有益的讨论，在此向他们表示深深的谢意。 感谢沱沱网搜索研发部的同事们，在与他们一起进行项目期间，给予了我指 导和帮助，帮助我解决了许多实际问题，使我学到了许多有用的知识。 在实验室工作及撰写论文期间，朱岩、肖宇等同学帮我搜集相关资料，共同 探讨相关领域的问题，对她们的无私帮助表示忠心的感谢。 特别感谢我的父母，他们的殷切期望和悉心嘱托时刻激励着我发奋学习，努 力上进，他们的理解和支持使我能够在学校专心完成我的学业。 1 1 选题意义 1 综述 随着i n t e r n e t 的迅猛发展和同益普及，网络上的信息量呈现爆炸式的增长，一 方面使得人们可以更加方便、快捷地获取各种电子化的文本信息；另一方面，随 之而来的纷繁复杂的文本信息处理问题也就成为了大家的研究重点，如何有效检 索这些海量信息成为当前重要的研究课题。在过去的几十年中，因为信息检索技 术越来越受到人们的重视，信息检索领域已经得到发展和壮大，并且超过了它最 初的文献检索、图书馆检索的目标。特别是上个世纪9 0 年代以来互联网的飞速发 展、搜索引擎g o o g l e 和百度的广泛应用，使人们对信息检索的重要性有了一个全 新的认识，对搜索引擎的依赖也同益加深。 根据中国互联网络信息中一t , ( c h i n ai n t e r n e tn e t w o r ki n f o r m a t i o nc e n t e r , c n n i c ) 最新的第2 1 次中国互联网络发展状况统计报告显示，截至2 0 0 7 年1 2 月，中 国网站数量已达1 5 0 万个，比去年同期增长了6 6 万个，增长率达到7 8 4 ，中国 网页总数已经有8 4 7 亿个，年增长率达到8 9 4 ，统计还显示，目前中国2 1 亿网 民中使用搜索引擎的比例是7 2 4 ，即已有1 5 2 亿人，半年净增3 0 8 6 万。随着人 们对搜索服务的同益依赖，搜索引擎市场的竞争也更加激烈。如何让人们能够快 速找到想要的信息成为各个搜索引擎公司面临的重要问题。研究表明大多数用户 看搜索结果通常只看前三页，因此全网搜索引擎如g o o g l e 、百度等都致力于提高 和改进自己的排名算法，使得用户需要的信息尽可能的排在最前面，方便用户的 使用，从而提高自己的知名度和流量。可是用户的需求越来越具体化，越来越多 元化，伴随着网络使用的普及，i n t e r n e t 为人们所作的事情也越来越多，因此一些 垂直搜索引擎如雨后春笋般，拔地而起。如酷讯火车票搜索，爱帮生活搜索，奇 虎论坛搜索，沱沱商务搜索。垂直搜索的意义就在于针对用户的特定需求，提供 与之相关的内容和服务。互联网上信息有无序性，重复性的特点，既然垂直搜索 引擎是为用户提供专业和个性化服务的，所以如何使它提供的信息具有针对性和 可读性，使信息呈现有序，重复率低是急需解决的问题。 目前，大部分搜索引擎公司都借助近似重复网页发现技术来快速全面的发现 重复信息。发现重复或者近似网页对于搜索引擎有诸多好处： 首先，如果能够找出这些重复网页并从数据库中去掉，就能够节省系统存储 空间，进而可以利用这部分空间来存放更多的有效内容，同时也提高了w e b 检索 的质量。 其次，如果能够在以往搜集信息时加以分析，发现一些镜像站点，并做标记， 那么在以后的网页搜集过程中就可以避丌这些镜像站点，从而提高有效网页的搜 集速度。 另外，如果某个网页的镜像度较高，也就预示着该网页相对重要，在搜集网 页时应赋予它较高的优先级，而当搜索引擎系统在计算页面排序得分的时候，应 该赋予它较高的权值。 而且，如果当用户点击了一个死链接，引擎可以将用户自动引导到该页面重 复页面，这样可以有效的增加用户的检索体验。因此，近似镜像网页的及时发现 有利于提高和改善搜索引擎系统的性能和服务质量。 聚类技术作为机器学习领域的一个前沿分支，在处理海量数据，处理无标定 数据时具有明显的优势，聚类技术不像分类那样需要大量的人工干预和人工标定 的训练样本。面对互联网上迅速增长的文本信息，再想通过人工干预来完成各种 文档的归类，重复文本的发现已经是不可能的事情。因此，如何有效地使用聚类 技术处理目前搜索引擎面临的信息检索，信息分类，用户定位，信息推送，信息 消重等问题成为了人们研究的重点。 1 2 文本聚类的发展与现状 聚类分析技术作为数据分析的工具和方法，已经被广泛地应用到许多领域中， 如模式识别、图像处理、数据挖掘、信息检索等。在金融领域，聚类能够帮助金 融行业人员分析金融数据，预测股市行情，帮助市场推广人员分析客户行为习惯， 定位客户群体；在医学领域技术，聚类能够进行基因序列分析，转录因子识别， 中药配伍发现等等。而且，在一些软件，如s p l u s ，s p s s ，s a s ，m i c r o s o f ts q l 2 0 0 5 中，也加入了聚类分析工具。 文本聚类是聚类方法在文本信息处理领域的一个重要应用分支，其目标就是 研究如何更有效地组织和管理文本信息，并快速、准确、全面地从中找到、分流、 定位和形成用户所需要的信息。 目前，人们已经从信息缺乏的时代过渡到信息极为丰富的数字化时代。人们 可以获得越来越多的数字化信息，包括文本、数字、图形、图像、声音和视频。 这些信息大都是半结构化或者是非结构化的数据，想从其中迅速有效地获得所需 信息是非常困难的事情。为了方便用户对信息检索，就对要检索的信息直接进行 聚类。文本聚类的研究就是基于这样一种条件下被提出来。 文本聚类技术用来分析被聚类对象的特征，并与各个对象所具有的共同特征 2 进行比较，将那些特征最接近的对象化归为一类，通常称之为“簇”。文本聚类给 人们带来了诸多好处： 首先，通过机器的快速运算可大大缩短对资料的整理时间，有利于文档的归 类与存档管理。 其次，可以应用于信息过滤、信息检索领域，为信息检索提供方便，使人们 能够准确地检索到自己想要的信息，缩短检索时间。 另外，有利于个性化的信息推送，通过使用聚类技术对用户的兴趣进行聚类， 将拥有共同兴趣的用户划为一个小团体，得到不同的小团体，可以按此完成快速 有效的信息分发，如一些商业广告的投放都是针对不同的购买人群的。 因此，聚类技术已成为文本信息挖掘技术中的核心技术。文本聚类作为处理 和组织大量文本数据的关键技术，可以在很大程度上解决信息杂乱和信息爆炸所 带来的问题，而且作为信息过滤、信息检索、搜索引擎、文本数据库、数字化图 书馆等领域的技术基础，文本聚类有着广阔的应用前景。虽然文本聚类问题只是 文本信息处理领域研究的一个方面，但也同时是至关重要的一个方面。它的解决 关系到电子化信息的普及和使用效率，当然也就关系到全国各行各业信息化的程 度，各行各业现代化的水平。由于，文本聚类所涉及理论和应用问题范围十分广 泛，处理起来非常复杂。随着信息时代技术的迅猛发展，研究中遇到的一些老问 题还没有得到解决时，新的问题又不断涌现，层出不穷。 目前，常用的文本聚类技术有基于层次的和基于划分的，本文将在第2 章进 行详细的介绍，并比较它们的优缺点。 1 3 网页消重的发展与现状 国际上对转载文档消重算法的研究最初主要是针对大型文件系统的，1 9 9 3 年， a r i z o n a 大学的m a n b e r 提出了一个s i i 1 】工具，用于在大规模文件系统中寻找内容 相似的文件。s i f 工具提出了近似指纹( a p p r o x i m a t ef i n g e r p r i n t s ) ，就是用基于字符 串匹配的方法来度量文件之间的相似性。这个思路被后来很多的文本复制检测系 统所采用。 19 9 5 年，s t a n f o r d 大学的b r i n 和g a r c i a m o l i n a 等人在“数字图书馆”工程中首 次提出了c o p s ( c o p yp r o t e c t i o ns y s t e m ，文本复制检测机制) 系统与相应算法【2 】， c o p s 系统框架为以后的自然语言文本复制检测系统奠定了基础。 g a r c i a m o l i n a 和s h i v a k u m a r 等人又提出了s c a m ( s t a n f o r dc o p ya n a l y s i s m e t h o d ) 3 原型改进c o p s 系统，用于发现知识产权冲突。s c a m 借鉴了信息检索 技术中的向量空间模型( v e c t o rs p a c em o d e l ) ，使用基于词频统计的方法来度量文本 相似性，后来在对其消重算法作了改进之后【4 】应用于g o o g l e 搜索引擎系统。 g a r c i a m o l i n a 和s h i v a k u m a r 等人还在s c a m 的基础上提出了d s c a m 模型 5 】，将 检测范围从单个注册数据库扩展到分布式数据库上以及在w e b 上探测文本复制的 方法。 同期，贝尔实验室的h e i n t z e 开发了k o a l a 6 系统用于剽窃检测。k o a l a 系统采用与s i f 基本相同的方法，与之类似的方法还有b r o d e r 等人在1 9 9 7 年提出 的s h i n g l i n g 7 】方法。 香港理工大学的s i 和l e o n g 等人建立的c h e c k 原型 8 】采用统计关键词的方 法来度量文本相似性。而且c h e c k 系统首次把文档结构信息引入到文本相似性度 量中。 2 0 0 0 年，m o n o s t o r i 等人建立了m d r ( m a t c hd e t e c tr e v e a l ) 原型 9 】。m d r 采 用后缀树( s u f f i xt r e e ) 来搜寻字符串之问的最大子串。后来，m o n o s t o r i 等人又提出 用后缀向量( s u f f i xv e c t o r ) 存储后缀树 1 0 。 伊利若伊理工在2 0 0 2 年提出的l - m a t c h 11 】方法也是对b r o d e r 的s h i n g l i n g 算 法的一种改进，但它并非从减少比较次数这方面着手，而是从过滤s h i n g l e s 这方面 考虑，过滤掉重复次数较多的s h i n g l e s 。 而卡内基梅隆大学在2 0 0 5 年提出的e r u l e m a k i n g 1 2 算法则首先从文档集合中 按照长度将数据集合分成一个个小的数据集合，然后找出每个小的数据集合中重 复次数最多的文档或完全重复的文档作为该数据集合中的种子，该集合中其他的 文档则优先与种子文档进行比较。 目前几乎所有的消重技术都基于一个基本思想：为每个文档计算出一组指纹 ( f i n g e r p r i n t ) ，若两个文档拥有一定数量的相同指纹，则认为这两个文档的内容重 叠性较高，也即二者是内容转载的。现在提取信息指纹最经典的方法是m d 5 算法， 全称是m e s s a g ed i g e s ta l g o r i t h m5 ( 信息摘要算法) 。在9 0 年代初由m i tl a b o r a t o r y f o rc o m p u t e rs c i e n c e 和r s ad a t as e c u r i t yi n c 的r o n a l dl r i v e s t 开发出来，经m d 2 、 m d 3 和m d 4 发展而来。 随着文本信息处理技术的发展，人们判断和处理近似网页的方法和手段也r 益丰富，各种文本处理技术被应用于其中，如文本分类、聚类技术，全文分段匹 配技术，特征码检索技术，特征串模糊匹配技术，特征句抽取技术，基于链接和 锚文本信息的技术等等。本文提出一种利用最大正文块去除噪声，提取网页有效 信息，并通过实体识别技术进行重复公司信息发现的算法，算法的详细描述及性 能分析将在后续章节展开讨论。 4 1 4 论文的主要研究内容与结构安排 第一章，从互联网信息呈指数增长的形式出发，介绍了网页消重对于搜索引 擎的意义所在，并简单的概括了网页消重技术和文本聚类技术的发展现状。 第二章，从文本表示的向量空间模型，文本相似性度量和特征选择的方法讲 起，而后介绍了适用于文本数据的层次聚类算法和划分聚类算法。 第三章，从网页重复的定义谈起，分析了网页数据与文本数据的不同特点， 即网页数据的噪音问题，并对国内外常用的网页消重进行详细介绍，并分析了它 们的优缺点。 第四章，本文结合b i s e c t i n gk m e a n s 算法的基本思想，引进了k m e m l s + - f 算法 根据距离远近按照不同概率选择初始类中心的方法，提出b i s e c t i n gk m e a n s + + 算 法，并在u c i 数据集上进行实验，给出了对比结果，验证了其在聚类效果和时间 开销上都有不错的表现。 第五章，根据实际应用背景，提出了最大j 下文块算法，该算法能够较好的去 掉网页噪声的影响，提取出网页的正文。并通过对一些新闻网页的测试验证了算 法的提取正确率，并在提取到正文的网页集合中分析比对b i s e c t i n gk m e a n s d - i - 算法 与前n 个高频词算法在网页消重方面的效果。并且根据实际应用中遇到的问题， 结合了实体识别技术，完成了b 2 bf - j p 网站信息抽取项目的公司信息整合子模块。 第六章，结论部分总结了自己的一些心得体会，以及实验过程中遇到的困难 与问题和一些未付诸实施的想法。 2 文本聚类技术的研究 文本聚类是无监督的机器学习问题，所谓聚类就是将数据对象分成多个类， 在同一个类中的对象之间具有较高的相似度，而不同类中的对象差别较大，而数 据集并没有预先定义好的主题类别。目前，主要的聚类分析算法有基于层次的， 基于划分的，基于网格的，基于密度的等等。首先，本文将介绍一种简单高效的 文本表示模型，即向量空间模型( v e c t o rs p a c em o d e l ，v s m ) 。 2 1 向量空间模型 s a l t o n 等人在2 0 世纪6 0 年代末提出了v s m 模型 1 3 】，并成功的应用于著名的 s m a r t 系统。该模型及其相关的技术，包括项的选择、权重赋值策略，以及采用 相关反馈进行查询优化等技术，在自动索引、信息检索等许多领域得到了广泛的 应用。 v s m 的基本概念： ( 1 ) 文档( d o c u m e n t ) ：泛指一般的文本或文本中的片断( 段落、句群或句子) ，一 般指一篇文章。 ( 2 ) 项( t e r m ) ：文档的内容特征常常用它所含有的基本语言单位( 字母、单词、 词组或短语等) 来表示，这些基本的语言单位统称为项，即文档可以用项集( t e r m l i s t ) 表示为d ( t l ，f 2 ，t ) ，其中t ，1 k n 是项。 ( 3 ) 项的权重( t e r mw d g h t ) ：对于含有n 个项的文档d ( t l ，f 2 ，t ) ，项t i 常常被 赋予一定的权重，表示它们在文档d 中的重要程度， 即 d = d ( t l ，w j ；t 2 ，w 2 ；f ，w n ) ，简记为d = d ( h ，w 2 ，w n ) 。项t t 的权重为， 1 k n 。在量化方法上，对权值的计算，比较常用的是采用t f i d f 方法【1 4 】。其 权值计算公式如下： w i = 斫幸l o g ( m m ，) 羔。 l o g ( m m ，) ) 2 ( 2 1 ) 矿是第i 个关键词在文档d 中的出现频率，m 是文档集中的文档总数，胁，是文 档集中含有第i 个关键词的文档数。 ( 4 ) 向量空间模型( v s m ) ：对于给定的文档d = d ( t l ，w l ；f 2 ，w 2 ；f ，w n ) ，由于 项t 。在文档中既可以重复出现又应该有先后次序的关系，分析起来仍有难度，所以 暂不考虑顺序信息，仅要求项t 。互异。这时可以把( t 。，f 2 ，t ) 看成一个n 维的坐 标系，而( w l ，w 2 ，w ) 为对应的坐标值，因此称d ( w l ，w 2 ，) 为文档d 的向量 6 空间模型。 这样，每个文本就被映射到了向量空问中的一个点，因而向量空间中的点的 距离就可以用来衡量其对应文本的相似性。 2 2 文本相似性度量 对于有n 个特征属性的文档集合来说，m 个文档可以看作n 维空问中的m 个 向量。本文用相似系数来度量它们之问的相近程度，用s i m ( d i ，d j ) ，i f ，j m 表 示第b 个文档与第d ，个文档之间的相似系数，常用的文本相似性度量函数【15 】有 以下几种： 1 余弦系数( c o s i n ec o e f f i c i e n t ) 删q p 户一 亿2 ， 2 雅可比系数( j a c c a r dc o e f f i c i e n t ) 跏p q 卜历n 麦篆n 专2n 两 亿3 ， 3 d i c e 系数( d i c ec o e f f i c i e n t ) 跏(di,dj卜东-z绥ak=liklk 亿4 ， & 聊) 2 i 藤 2 - 4 ) 一= 1 胍_ j 七= l， 同时s i m ( d ，d ，) 应满足下面两条性质： ( 1 ) v i ，ji s i m ( d i ，d ) i 1 ，即绝对值总不大于1 。 ( 2 ) v f ，s i m ( d ，d ，) = s i m ( d ，d j ) ，即满足对称性。 不同的相似性度量函数有其不同的使用范围，可是如何确定文档集合的n 个 特征来进行相似性计算，就需要运用特征选择的知识。特征选择的好坏会直接影 响到相似度的计算和算法结果的好坏。 2 3 特征选择 文本的特征表示是文本聚类工作的基础，它是对从文本中抽取出的特征项进 行量化，用向量空问模型表示文档信息。 在文本聚类中，特征空问的维数很高，即使是中等大小的文档，其初始文档 向量都在高维的特征空间进行聚类时，需要大量的计算时间，同时一些不相关的 特征还会制造噪声，对聚类效果造成影响。为了提高聚类的性能，必须把高维的 特征空间压缩到低维的空间，同时弱化不相关特征在聚类中的作用，因此文本特 征选择具有重要的意义。 2 3 1基于阈值的特征选择方法 文本的特征选择主要有两种思路一种是基于阈值的统计方法，该方法计算复 杂度低，速度快，它的基本思想都是对每一个特征，计算出某种统计度量值，从 中抽取一定数量的词作为特征项，用抽取出的特征项作为文档的向量表示，从而 实现维数的降低。一般是设定一个阂值兀将计算的统计度量值按照从大到小的顺 序排列，把度量值小于丁的那些特征过滤掉，剩下的便是有效的特征。常见的有 特征频度方法、文档频度方法、反文档频率权重法、互信息方法、z 2 统计量方法、 期望交叉熵、信息增益方法、文本证据权等。 因为在文本聚类算法中使用特征选择方法来得到文档的向量空间模型，聚类 的前提是无监督学习，所有的文档都没有类标示，而互信息方法、z 2 统计量方法、 期望交叉熵、信息增益方法、文本证据权这些方法都需要基于类别信息，所以特 征频度方法、文档频度方法、反比文档频数权重法更适合于聚类算法。 特征频度也叫做词频，是指特征t 。在一篇文本中出现的次数。这是一种最简单 的特征选择方法。 文档频度是指在文本集合中含有特征t 。的文本数目在整个文本集合中的文本 总数中出现的概率。它依据的假设是稀有词汇和高频词汇对聚类的贡献不大，有 可能是噪音或者是停用词，因此可以删除掉。但是如果某一稀有词汇主要在某一 类文本中出现的话，就有可能把这一类的显著特征过滤掉。该方法能够去掉低频 词和高频词，从而减少特征空间的维数。当低频词是噪音时这种方法很好，可以 提高聚类效果。但是有时候低频词也会带有大量有用的信息，这时候去掉低频词 就会影响聚类的效果。 反文档频率权重法，即t f i d f 方法。它是根据某个词的词频t f 和其出现过 的文本的频率d f 来计算该词在整个文本集合中的权重，然后依据权重来进行特征 选择。权重越高，说明该特征对文本类别的区分能力越好。 t f i d f 实际是t f i d f ，t f 是词频( t e r mf r e q u e n c y ) ，i d f 是反文档频率 ( i n v e r s ed o c u m e n tf r e q u e n c y ) 。t f 表示特征t i 在该文档中出现的频率。 i d f = l o g ( n n ) ，n 表示文本集合中所有的文本数，n 表示包含特征t 。的文本数。 i d f 的基本思想是：如果包含某个特征t 。的文档越少，i d f 就越大，说明特征f 。有 很好的类别区分能力。 t f i d f 方法的计算公式如下式所示： t f i d _ t f ( t k ) i d t l o g ( 南) ( 2 5 ) 为了使t f 值对权重的影响进一步降低，公式( 2 6 ) 对t f 值的计算做出了调整。 删叫= 0 5 + 餐剐xi d f ( t k ) = 0 5 + 餐斟蛔c 斋固 其中t f ( t 。) 表示特征，。在文档中出现的次数，t f m 。( ，。) 表示文档中特征气最大 的出现次数。d f ( t 。) 是出现特征的文档数除以文档集合中的文档数。 2 3 2 基于映射的特征选择方法 基于映射的方法也叫做w r a p p e r 方式：通过空间转换将原始高维空间上的数 据映射到一个新的低维空间上，低维空间上每一维的值由原始空间经过线性或非 线性转换得到。与前面所述方法最大的不同之处在于该方法并不是直接通过判断 单词的重要性然后决定是否保留作为最终的特征，而是直接使用线性或者非线性 的变换将冗余或者无效的信息映射到相对较弱的维度上，从而保证特征提取的效 果。其主要方法有 16 】：奇异值分解( s i n g u l a rv a l u ed e c o m p o s i t i o n ) 、主成份分析 ( p r i m a r yc o m p o n e n ta n a l y s i s ) 、因子分析( f a c t o ra n a l y s i s ) 、独立成份分析 ( i n d e p e n d e n tc o m p o n e n ta n a l y s i s ，i c a ) 、随机映射( r a n d o mp r o j e c t i o n ，r p ) 等。 首先，通过一个例子来看看s v d 分解是如何在实际中被巧妙的使用的。假设， 本文用一个大矩阵 a = a s j a i n 口 f 口w a m ) n m n ( 2 7 ) 来描述这一百力篇文章和五十万词的关联性。这个矩阵中，每一行对应一篇文章， 每- - y 0 对应一个词。 在公式( 2 7 ) 中，m = 1 ，0 0 0 ，0 0 0 ，n = 5 0 0 ，0 0 0 。元素口口是字典中第j 个词在第i 篇文章中出现的加权词频( 比如，t f i d f ) 。因此，这个矩阵非常大，有一百万乘以 五十万，即五千亿个元素。 9 ； 1 ，0 0 0 ，0 0 0 5 0 0 ，0 0 0 图2 1 奇异值分解示意图 f i g u r e2 1s v d s k e t c hm a p 奇异值分解可以把矩阵a 这样一个大矩阵，分解成三个小矩阵相乘，如图2 1 所示。比如把a 分解成一个一百力乘以一百的矩阵u ，一个一百乘以一百的矩阵， 和一个一百乘以五十万的矩阵v 。这三个矩阵的元素总数加起来也不过1 5 亿，仅 仅是原来的三千分之一。相应的存储量和计算量都会小三个数量级以上。 分解得到的三个矩阵有非常清楚的物理含义。第一个矩阵u 中的每一行表示 意思相关的一类词，其中的每个非零元素表示这类词中每个词的相关性，数值越 大越相关。最后一个矩阵v 中的每一列表示同一主题一类文章，其中每个元素表 示这类文章中每篇文章的相关性。中间的矩阵则表示类词和文章类之间的相关性。 因此，只要对关联矩阵a 进行一次奇异值分解，就可以同时完成了近义词分类和 文章的分类，同时得到每类文章和每类词的相关性。 下面，对奇异值分解在数学上的意义进行解释，奇异值分解就是把一个m n 维 实数矩阵a ，用三个矩阵相乘来表示。即存在一个m m 维和甩门维的正交阵u 和v ，使得： a = u z v 丁 ( 2 8 ) 其中，是个m n 维对角阵，其主对角线上的元素是非负的，并按照下列顺 序排列： 仃l 仃2 盯 0h = m i n ( m ，? )( 2 9 ) 矩阵u 和v 称为正交阵，若它们分别满足u = u7 和v = v 7 。对角元素仃i 称为矩阵a 的奇异值，u 和v 分别叫做矩阵a 的左奇异阵和右奇异阵，而 u = 【u 。，u ：，甜。】和v = v 。，v ：，v 。】的列向量b 一口、，i 分别称作矩阵a 的左奇异向 量和右奇异向量。 非零的奇异值对应于非负h e r m i t i a n 阵彳彳+ 和a a 的特征值的正平房根，而且， u ( 或v ) 的列对应于非负h e r m i t i a n 阵彳彳+ ( 或a + a ) 的适当排列的正交特征向量。 1 0 对于聊n 维的矩阵a b ，其f r o b e n i u s 范数定义为： 厂。， 1 1 2 卜b i i f = i k 一硝i ( 2 1 0 ) l 扛ij = lj 在f r o b e n i o u s 范数意义下能最佳逼近m n 维矩阵a 的唯一的m 玎维，且秩 ksr a n k ( a ) 的矩阵由a = u 。v7 给定，而。是通过在内令k 个最大的奇异 值以外的所有其它奇异值都等于零后得到的对角阵。这一最佳逼近的质量由下式 描述。 r1 1 2 a - a ( k ) i i ，2l l i 萎= k - ，2 j ( i i , 州n l ( 2 1 1 ) + l jv 二 二 公式( 2 11 ) 表明，a 似逼近a 的程度取决于( h k ) 个最小的奇异值的平方和。因 此可以得出i a l l ，= q 2 ，这说明奇异值q 包含了有关矩阵a 的秩的特性的有用 信息，矩阵的度量特征与矩阵的奇异值密切相关。 使用向量空间模型，经过特征选择方法，选取有效特征，把文本集合中的文 本转化成向量表示，然后就可以利用各种聚类算法进行聚类，如层次聚类算法， 划分聚类算法，网格聚类算法，密度聚类算法等等，它们在评价两个文本的相似 度时，使用到了文章第2 2 节介绍的文本相似性度量方法。但是不同的聚类算法适 用的数据集合也不尽相同，层次聚类算法和划分聚类算法更适应于文本数据集合， 本文将在第2 4 和2 5 节对这两种算法进行详细介绍。 2 4 层次聚类算法 层次聚类算法【1 7 ，1 8 按照类别嵌套规则组织数据，以形成层次的聚类结构。它 是一种有效的聚类技术，通过将数据对象组成为一棵聚类树从而为用户提供多种 可选的聚类结果，可以根掘需要随时结束聚类操作过程，因而是目前广泛应用的 一种聚类技术。 层次聚类的具体实现过程分为两种形式：自底向上凝聚与自顶向下分裂。凝 聚算法首先把每个对象或者小集合作为一个初始类，然后把这些类别合并到若干 个更粗糙的类别中，如此反复合并直到所有的对象都处在一个大类中，这是一个 由底向上的过程，逐渐由从精细到粗糙；而分裂算法正好相反，其首先把整个样 本集作为一个初始类别，然后把其分解为若干小类别，然后把每个小类别继续依 次分解下去，因而这是一个由顶向下的过程，体现出从粗糙到精细。凝聚与分裂 操作都要基于某种特定的相似性度量机制。由于聚类往往是在缺乏样本总体分布 知识的情况下进行的，因而凝聚算法往往比分裂算法更多地应用于实际中。典型 的有单连接算法，全连接算法和b i r c h ，c u r e ，c h a m e l e o n 等。 单连接算法和全连接算法基本步骤相同，其不同之处只在于单连接算法是计 算类间的最大相似度，而全连接算法则是计算类i 、日j 的最小相似度。 b i r c h i9 ( b a l a n c e di t e r a t i v er e d u c i n ga n dc l u s t e r i n gu s i n gh i e r a r c h i e s ) 算法引 入聚类特征与聚类特征树两个概念来实现综合的利用层次方法地聚类，其优点是 具备可伸缩性，首先扫描数据集并建立一个基于内存的聚类特征树，然后采用某 个聚类算法对聚类特征树的叶子结点进行聚类操作。时间代价为o ( n ) ，n 为样本集 中样本个数，因而速度较快，该算法的主要问题在于其利用半径或直径来控制聚 类的边界，因而无法适应于非球形聚类的情况。 c u r e 2 0 ( c l u s t e r i n gu s i n gr e p r e s e n t a t i v e s ) 通过选择数据空间中固定数目的 具有代表性的点来描述聚类。能够识别非球形或者大小变化较大的簇，对孤立点 的处理也更健壮，对大型数据集具备不降低聚类质量的良好伸缩性，其缺点是不 处理分类属性。r o c k 2 1 】( r o b u s tc l u s t e r i n gu s i n gl i n k s ) 算法实际上是c u r e 算法 针对分类属性的改进版本。 c h a m e l e o n 2 2 算法是一种通过在合并两类时使用更高的标准来提高聚类质量 的聚类算法，如果合并后的类之问的互