（计算机软件与理论专业论文）利用单词超团的二分图文本聚类算法.pdf

利用单词超团的二分图文本聚类算法 论文题目 专业 硕士生 指导教师 利用单词超团的二分图文本聚类算法 计算机软件与理论 曲超 汤庸教授 摘要 自九十年代产生以来，数据挖掘技术的研究已经比较深入，研究范围涉及到 关联分析、分类分析、聚类分析、趋势分析等多个方面。在常见的非结构化数据 如文本、图像、视频中，文本数据是应用最为广泛的一种形式，因此文本挖掘成 为了数据挖掘领域中的一个重要组成部分。 本文通过对传统信息检索技术中文本挖掘的介绍，在传统的文本挖掘基础上 提出了一种新型的、更有效的聚类算法基于单词超团的二分图聚类算法。超 团是一种特殊的频繁项集，其中附加了整体相似度的约束，利用超团的这种特性， 将其应用于文本聚类，在给定的文本集中挖掘单词最大超团，可以保证每个单词 超团内部任意两个元素的相似度不低于事先给定的下界，从某种意义上来讲保留 了文档中的简单语意。因此将单词超团作为文本向量的扩展特征在聚类过程中加 以使用，能够保证在聚类过程中提高结果的准确性。 本文完成了理论的提出和对整个过程的设计和实现，其中利用单词超团集合 进行文本聚类的方法划分为三个步骤：挖掘最大单词超团集合，构成二分图结构 和对图进行划分。在此基础上，通过对现实世界提取的若干数据集的测试，根据 得到的聚类划分评测指标n m i 、c e 、e r r 、f - m e a s u r e 与标准二分图聚类结果的 比较证实了单词超团聚类划分的优越性。 关键词：文本聚类，单词超团，二分图划分 型旦望旦塑里塑三坌堕塞查窭耋墨堡 t i t l e ： l l a j o r ： n a m e ： s u p e r v i s o t ： w o r dh y p e r c l i q u ea n db i p a r t i t eg r a p hp a r t i t i o nb a s e d c l u s t e r i n ga l g o r i t h m c o m p u t e rs c i e n c ea n ds o f t w a r e q uc h a o p r o f t a n gy o n g s i n c e9 0 t h ec o n c e p to fd a t am i n i n gw a sp r o d u c e d ，t h er e s e a r c h e so nd a t a m i n i n gh a v eb e e nv e r yd e e p ，a n di n v o l v e d a s s o c i a t i o na n a l y s i s ，c a t e g o r i z a t i o n a n a l y s i s ，c l u s t e ra n a l y s i s ，t r e n da n a l y s i sa n ds oo n t e x td a t ai sa k i n do fi n f o r m a t i o n f o r mu s e dm o s ts p r e a da m o n gc o m m o nu n s t r u c t u r e dd a t a s ot e x tm i n i n gb e c o m e sa m o s ti m p o r t a n tp a r to ft h ed o m a i n t h i sp a p e rd e s c r i b e san e wk i n do ff o r m u l a t i o nf o fd o c u m e n tc o c l u s t e r i n gs u c h t h a tw o r dh y p e r c l i q u ea n db i p a r t i t eg r a p hp a r t i t i o nb a s e dc l u s t e r i n ga l g o r i t h m b r o u g h to u tf r o mt h et r a d i t i o n a lt e x tm i n i n gi nt h ed o m a i no f i n f o r m a t i o nr e t r i e v a l h y p e r c l i q u ei sas p e c i a lt y p eo ff f e q u e n ti t e m s e t ，t h a ta n o v e r a l ls i m i l a r i t yw a su s e di n i t ，b a s eo nt h ea t t r i b u t eo ft h eh y p e r c l i q u e ，w eu s ei tt ot h ed o c u m e n t sc l u s t e r i n g w e m i n et h eg i v e nd o c u m e n t sf o rm a x i m a lw o r dh y p e r c l i q u ep a t t e r ns e ta n d i tg u a r a n t e e d a n yt w oo f t h ei t e m si nt h es a m ei t e ms e th a v e s i m i l a r i t i e sn o tl e s st h a nt h es p e c i f i e d v a l u e ，w h i c hm i g h tk e e pt h es i m p l es e m a n t i co f t h ed o c u m e n t s u s et h e ma se x p e n d e i g e n v o c t o r si nd o c u m e n t sd t e f i n gs h o u l db ei m p r o v et h er e s e t a f t e rb r o u g h to u tt h et h e o r y , w ed e s i g n e dt h ee x p e r i m e n tw h i c hc o n s i s t st h r e e s t e p s ：m i l l em a x w o r dh y p e r c l i q u ep a t t e r ns e t , f o r mt h eb i p a r t i t ea n dt h e np a r t i t i o ni t w eu s ef o u rs c a l a rq u a n t i t i e sn m ! ，c e ，e r r ，f - m e a s u r et oc o m p a r ew i t ht h e n o - h y p e r c l i q u eb i p a r t i t ep a r t i t i o na n dd r a wt h ec o n c l u s i o n k e yw o r d s ：d o c u m e n t sc l u s t e r i n g ，w o r dh y p e r c l i q u e ，b i p a r t i t ep a r t i t i o n 一 利用单词超团的二分图文本聚类算法 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的作品成果。对本文的研究作出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 签名：垫蝗 日期：2 巫年卫月_ 2 上日 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保留 学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权将学 位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查 阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩印或其 他方法保存学位论文。 学位论文作者始均起 导师躲 日期：2 词年f 阳2 珀 日期：年月 日 利用单词超团的二分图文本聚类算法 第1 章前言 随着计算机网络的大规模普及和信息技术的飞速发展，互联网已经成为了 一个巨大的信息空间，为用户提供了极具价值的信息资源。面对信息的爆炸式膨 胀，在处理和使用过程中如何有效地组织和管理这些信息，并快速、准确、全面 地从中找到所需要的内容是当前信息科学领域面临的一大挑战。 1 1 研究背景和信息检索现状 由于互联网的大规模普及和企业信息化程度的不断提高，文本信息的快速 积累使公司、政府和科研机构在信息处理和使用中面临前所未有的挑战。一方面， 互联网和企业信息系统每天都不断产生大量文本数据，这些文本资源中蕴含着许 多有价值的信息；而另一方面因为技术手段的落后，从大量数据资源中获取需要 的信息十分困难。面对海量、分布、动态、异质、复杂、非结构化的丰富信息资 源，用户如何从中查找、抽取自己想要的数据和有用信息成为至关重要的问题。 搜索引擎的出现，大大提高了人们搜集信息的能力。搜索服务已经成为所 有互联网用户中使用最多的服务之一。随着互联网上信息的日益丰富，人们越来 越依赖搜索引擎来寻找所需信息。在搜索引擎的背后，是信息检索技术在起作用。 1 1 1 信息检索技术简介 信息检索( i n f o r m a t i o nr e t r i e v a n 这一专业术语最早是由c a l v i n n m o o e r s 在 1 9 5 0 年的z a t o rt e e h n i e a lb u l l e t i n ( n o 4 5 1 中公开提出的。信息检索最初主要是应 用于图书馆中的文献检索，1 9 5 4 年世界上第一个计算机文献检索系统是由美国 海军兵器中心( n a r s ) 图书馆在i b m 7 0 1 型计算机上成功建立的。随着计算机技 利用单词超团的二分幽文本聚类算法 术与互联网的发展，信息检索系统也由简单的批处理方式文件检索发展到七十年 代后的联机情报检索，以至于到现在出现的大规模的互联网信息检索和数字图书 馆等领域。 信息检索技术是指按照某一特定方式组织和存贮信息，并根据用户的需求 查找出有关信息或对信息进行分类等过程，又称信息存贮与检索、情报检索。信 息检索包括3 个主要过程： 1 对信息内容进行分析与编码，产生信息的相关记录以及检索标识。 2 信息组织存贮，将全部记录以文件、数据库等形式组成信息的有序 集合。 3 用户需求处理和检索结果输出。 影响检索系统性能的因素有很多，其中最主要的是建立的信息检索模型，其中包 括文档和查询条件的表示方法、评价文档和用户查询相关性的匹配策略、查询结 果的显示方法和对用户查询进行相关反馈的机制等。经过研究人员的不断努力， 一些有效的信息检索模型陆续被提出并逐渐应用到相关的检索系统中。其中影响 比较大的检索模型包括：布尔逻辑模型、向量空间模型、概率模型以及最近提出 的语言模型检索方法。现今乃至未来，信息检索技术都将对我们科学研究和日常 生活产生积极而又重要的影响。， 1 1 2 信息检索的发展方向 目前，信息检索的对象从相对封闭、稳定、一致的由数据库集中管理的信息 内容扩展到开放、动态、更新快、分布广泛、管理松散的w e b 内容；信息检索的 用户也由原来的专业人员扩展到包括各行各业人士的普通大众，他们对信息检索 技术从检索结果到检索方式都提出了更高、更多样化的要求。同时互联网规模的 急剧增大以及存储系统规模的日益增加也推动了现有的信息检索技术的发展。未 来的信息检索技术将向着以下几个方向发展： 一、智能化 智能化是网络贫息检索未来发展的主要方向。智能检索是基于自然语言的一 利用单词超团的二分图文本聚类算法 种检索形式，机器系统首先对用户提供的以自然语言为基础的表述要求进行分 析，而后形成对应的检索策略进行搜索。近几年来，智能信息检索( i n t e l l i g e n t i n f o r m a t i o nr e t r i e v a l ) 作为人工智能( a i ) 领域的一个独立研究分支得到了长 足发展。在i n t e r n e t 技术迅速普及的今天，面向i n t e r n e t 的信息获取与精化技 术已成为当代计算机科学与技术领域中迫切需要研究和解决的课题，将人工智能 技术应用于这一领域是人工智能技术走向应用的一个必然过程。 二、可视化 据统计，人获取信息有7 0 一8 0 是通过视觉完成的，2 0 靠听觉，1 0 靠 触觉。用图像取代文字来实现检索结果的表示，其优点在于：图像的表达方式更 生动、形象、准确、效率更高，能从多种角度来表达检索结果的有关信息，而纯 文字的表达方式是模糊的、一维的，不够准确和形象。 、简单化 未来家用微机将朝着智能化、网络化、人性化和绿色环保等方向发展；操作 系统的用户友好性将不断增强，使用户学习和进行网络信息检索更加容易；对于 信息检索技术来说，自动标引、自动文摘、自动跟踪、自动漫游、机器翻译、动 态链技术、数据挖掘和信息推拉等技术也必须向用户友好性方面发展，使之更利 于用户的使用，提供更方便快捷的检索服务。 四、多样化 多样化首先表现为信息形态多样化，如文本、声音、图形、图像等。多样化 同时也表现为检索工具的服务多元化。检索工具己不仅仅提供单纯的检索功能， 与此同时也正在向其他服务范畴延伸以多种形式满足用户的需要。多样化还表现 为信息检索可以间接地服务于其他行业。例如数据挖掘技术可以通过分析历史数 据的变化趋势，对未来发展方向进行预测，或者发现大量数据中潜在的模式规律， 为社会的发展规划提供可靠的依据。 1 2 研究内容、方法和意义 在现实世界中，可获取的大部份信息是以文本形式存储在文本数据库中的， 利f l f i 单词超团的二分图文本聚类算法 由来自各种数据源的大量文档组成，如新闻文档、研究论文、书籍、数字图书馆、 电子邮件和w e b 页面。由于电子形式的文本信息飞速增长，文本挖掘已经成为 信息领域的研究热点该课题就是以此为基础进行的相关理论的研究。 1 2 1 研究的内容和方法 作为一种无监督的机器学习方法，聚类技术已经成为对文本信息进行有效 地组织、摘要和导航的重要手段，为越来越多的研究人员所关注。学术界不断进 行研究和探讨力求寻找到一种更准确、更高效的聚类算法来达到更好的聚类效 果。 “超团”( h y p e r c l i q u e ) 是近期h u ix i o n g ( 美国新泽西州立大学管理科学 与信息系统系助理教授，已经在国际会议和期刊上发表了三十余篇论文。担任过 多个国际顶尖会议程序委员会委员副主席，包括s i g k d d 0 6 ，s i a ms d m 0 6 ， i e e ei c d m 0 6 ，a c mc i 删0 6 ，i e e ei c d e 0 7 ，是i e e e 和a c m 会员。) 等人在 频繁项集( f r e q u e n ti t e ms e t ) 的基础上提出的一个较新的概念，是一种特殊的 频繁项集。其目的是为了解决以往对具有偏斜分布( s k e w e dd i s t r i b u t i o n ) 的 数据集进行关联规则挖掘时碰到的两大问题。由于超团中附加了整体相似度的约 束，保证了内部任意两个元素的相似度( 比如用j a c c a r dm e a s u r e 测量) 不低于事 先给定的下界。基于超团的这种特性，在文档一单词矩阵空问中利用给定的支持 度和关联度计算出一定数量的单词超团并作为文档向量特征结构的扩展，在保证 局部相似度不低于给定值的前提下对整体文档集做相似度的测量，从而提高聚类 的准确性。 在利用超团建立特征结构的同时，采用二分图的方法对特征矩阵进行聚类划 分。图划分在很多领域已经成为一种重要的聚类方法，在大量的数据挖掘应用中 数据对象两两之间的相似度可以以图的模型来表示，进而对数据对象的聚类可以 映射为对图的划分。图划分聚类经过十几年的不断研究和发展出现了很多不同的 分支，例如按照划分方法分为标准分割( n o r m a l i z e dc u t ) 和度分割( r a t i oc u t ) ； 按照划分块结构分类的平衡划分和非平衡划分等。 利用单词超团的二分图文本聚类算法 1 2 2 研究的意义 传统聚类方法首先利用文档间的相似度进行聚类，然后对各个类产生描述。 由此可见，文档之间相似度的计算是关键，不同的特征结构对聚类的结果会产生 不同的影响。传统相似度仅仅考虑二者之间的关联，而对于这种以向量空间模型 表示的文档高维数据，两篇距离很近的文档并不一定属于同一主题。这也就是所 谓的高维诅咒问题( c u r s eo f d i m e n s i o n a l i t y ) 。这样产生的文档群并不一定属于同 一主题，因而产生的类名通常不准确，不利于用户的信息选择。其面临的问题主 要表现在： 1 、对于文档向量两两之间相似度的比较随着文档数量的增加其复杂度 呈指数函数增加。这对于海量信息的聚类来说无疑是一种灾难，同时对于时l 日j 要 求相对较高的环境，如w e b 挖掘，也是不可忍受的。 2 、 对于特征结构的选取，不同的方法会产生不同的结果，不同的结果 之间会有所交叉。一些方法在提高了某一方面的性能的同时却降低了另一方面的 性能，而另外一些却与之相反。 3 、对于文档的聚类，只以其中的线性部分作为特征，不能正确表述实 际的语意，因而在聚类时容易出现误差。对于自然语意的文本映射到某一向量空 间时，必然导致信息的丢失，进而影响聚类的效果。 该项目就是基于以上的问题来研究一种正确率相对较高的聚类算法。本题 目重点研究如何用利用文档中单词的关联模式来评估文档闯的相似度及主题类 别预测。利用图划分策略可以大大降低文档相似度比较的算法复杂度，同时利用 超团作为特征结构的扩展可以在一定范围内减少语言信息的丢失，提高聚类效 果。 1 3 论文的组织结构 本文共由五个章节组成： 第一章概要介绍了信息检索技术的现状和发展趋势，面对信息检索技术逐 利用单词超团的二分图文本聚类算法 渐向智能化、可视化、简单化和多样化的方向发展，提出了该课题的研究内容、 方法和意义； 第二章主要介绍课题所属的研究范围文本挖掘。作为信息检索技术的 一个分支，文本挖掘经历了一个漫长的发展过程，在文本挖掘技术中，文本聚类 是一个重要的研究方向，该部分同时也介绍了文本聚类的相关技术； 第三章是本文的主体部分，详细阐述了本文的核心问题单词超团在文 本聚类中的应用，通过对超团的有关概念的介绍，进步引入了如何利用单词超 团来进行特征向量的扩展，同时介绍图聚类在该课题中的应用； 第四章是对本文的材料支撑的一个描述，主要描述了在给定数据集上该算 法的设计与实现以及实际处理结果； 第五章总结全文，并对文本聚类的研究前景和进一步努力的方向做出展望。 利用单词超团的二分幽文本聚类算法 第2 章文本挖掘与文本聚类 本章通过介绍文本挖掘技术指出文本聚类是文本挖掘中的一个重要研究领 域，并分别介绍了文本聚类的相关定义、发展和应用，同时本章重点描述了文本 聚类性能的评测指标。 2 i 文本挖掘 文本挖掘已经成为数据挖掘领域中一个新兴而同益重要的研究领域。与一般 数据挖掘方法以关系、事务和数据仓库的结构数据为研究目标所不同的是，文本 挖掘所研究的内容是由来自各种数据源的大量异构、动态、复杂的文档组成，包 括新闻、研究论文、书籍、报告、各类文献、技术档案、数字图书馆、电子邮件、 w e b 页面等。这些文档可能包含标题、作者、出版日期等结构化数据，也可能包 含摘要、关键字和内容等非结构化的文本成分，并且这些文档的内容是属于人类 所使用的自然语言系统，计算机很难对其语义进行处理。因此传统的信息检索技 术已不能适应日益增加的大量文本数据处理的需要，为此人们提出文本挖掘的方 法来进行不同的文档比较，以及文档重要性和相关性的排列，或找出多文档包含 的模式或从中进行趋势分析。 2 1 1 文本挖掘的发展过程 长期以来，文本分类都是自然语言处理的一个重要的研究和应用领域。最初， 检索系统借用数据库系统查询的方法，采用布尔逻辑模型，使用语词的布尔逻辑 组合作为查询条件，从文档数据库中检索出满足查询条件的文档。由于布尔模型 来自于数据库管理系统( d b m s ) ，所以只能查找结构化的精确数据信息，而不能 利用单词超团的二分图文本聚类算法 很好地解决无结构的文本信息的检索问题，也不能实现查询条件与文档的部分匹 配。因此s a l t o n 等人在1 9 6 8 年提出了向量空间模型，并开发了基于向量空间模 型的实验检索系统( s 姒r t ) 。1 9 7 6 年按照文档与查询条件相关和不相关的关系 r o b e r s o n 提出了概率模型，基于概率模型的检索系统中通过概率排序原理计算 文档与查询条件的相似性，即通过估计文档与用户查询条件的相关概率对文档集 合进行排序。二十世纪八十年代以后到九十年代末期发展出来的检索模型都是上 述三种经典信息检索模型发展而来的 1 。 进入九十年代，随着信息技术的迅猛发展，以及计算机可读形式的文字信息 的急剧增加，为基于机器学习的文本分类方法准备了更加充分的资源和更广阔的 发展空问。近些年来文本分类技术取得了重大的进展，提出了多种特征抽取方法 和分类方法，如回归模型、k 最近邻( k n e a r e s t n e i g h b o r ，k n m 、支持向量机( s v m ) 、 朴素贝叶期( n a i v eb a y e s ，n b ) 、最大熵模型等1 2 1 。语言模型研究最初是为了利 用统计技术计算文本内部词汇i 日j 的依赖关系帮助语音识别系统提高识别率。1 9 9 8 年，出现了将统计语言模型和信息检索相结合的新的思路。最初提出的语言模型 检索方法现在经常被称为“查询条件生成概率模型”。在这个模型中，作为启发 规则性质的计算因子引入的一些统计信息比如词频信息( t e r mf r e q u e n c y ) 和文 档频率( d o c u m e n tf r e q u e n c y ) 等成为语言模型检索方法中的有机组成部分。尽管 语言模型还只是很简单的模型，但是在检索效果方面已经可以和目前性能最好的 检索模型相当或者更好，这些已经被大量实验数据所证明。这个经典的基于语言 模型的信息检索模型为信息检索领域开辟了一个很有前景同时也具有相当挑战 性的方向。这个新的检索模型提出后受到了广泛的关注，在此之后不少学者和研 究人员在此基础上提出了众多的改进方法或者模型 1 。 2 1 2 文本挖掘技术分析 文本挖掘( t m ，t e x tm i n i n g ) 的基本思想是：首先利用文本切分技术，抽取 文本特征，将文本数据转化为能表达文本内容的结构化数据，然后利用聚类、分 类技术和关联分析等数据挖掘技术，形成结构化文本，并根据该结构发现新的概 利用单词超团的二分图文本聚类算法 念和获取相应的关系。 文本挖掘不但要处理大量的结构化和非结构化的文档数据，而且还要对其中 复杂的自然语义关系加以处理，因此，现有的数据挖掘技术无法直接应用于其上。 对于非结构化问题，存在两种主要的解决办法：一条途径是发展全新的数据挖掘 理论和算法，直接对非结构化数据进行挖掘。由于数据结构的复杂性，导致理论 和算法的复杂性很高；另一条途径就是将非结构化问题结构化，利用现有的数据 挖掘技术进行挖掘，目前的文本挖掘一般采用该途径进行。对于语义关系，则需 要集成计算语言学和自然语言处理等成果进行分析。其主要过程包括： 1 数据预处理。主要包括s t e m m i n g ( 英文) 、分词( 中文) 、特征提取和特 征表示。与通常的结构化数据相比，文本数据只有有限的结构，或者根本就没有 结构。此外，文档的内容是人类所使用的自然语言，计算机很难对其语义进行处 理。因此，币是由于文本信息源的这些特殊性使得数拐预处理技术在文本挖掘中 更加重要。 2 挖掘分析。文本转换为向量形式并经特征提取以后，便可以代替原始文 本的特征结构进行挖掘分析。常用的文本挖掘分析技术有：文本结构分析、文本 摘要、文本分类、文本聚类、文本关联分析、分布分析和趋势预测等。 3 结果输出。按照用户需求进行挖掘后的数掘需要将结果反馈给终端用户， 通常可以采用文本、图形、声音甚至多媒体的形式加以反馈，有时可能根据用户 要求对结果进行进一步的处理【3 】。 2 2 文本聚类 2 2 。1 聚类 聚类就是按照事物间的相似性进行区分和分类的过程。在统计方法中，聚类 也称聚类分析，主要研究基于几何距离的聚类。在机器学习中聚类称作无监督学 习或无教师归纳。聚类与分类类似，都是将数据进行分组。但与分类不同的是， 利用单词超团的二分图文本聚类算法 聚类中的组不是预先定义的，而是根据实际数据的特征按照数据之间的相似性来 定义的。聚类中的组也称为簇。有些学者认为聚类是一种特殊类型的分类，但多 数人认为聚类与分类是不同的。因此，可以认为聚类学习和分类学习的不同主要 在于：分类学习的训练文本或对象具有类标号，而用于聚类的文本没有类标号， 由聚类学习算法自动确定。 聚类分析源于许多研究领域，包括数据挖掘、统计学、机器学习、模式识别 等。它是数据挖掘的一个重要手段，但也能作为一个独立的工具来获得数据之间 相似或不相似的情况，概括出每个簇的特点，或者集中注意力对特定的某些簇做 进一步的分析。此外，聚类分析也可以作为其他分析算法( 如关联规则、分类等) 的预处理步骤，这些算法在生成的簇上进行处理。下面给出聚类形式化的定义。 定义2 1 ( 聚类) 聚类分析的输入可以用一组有序对( 影s ) 或( 形d ) 表示， 这里) c 表示一组样本，s 和d 分别是度量样本问相似度或相异度( 距离) 的标准。 聚类系统的输出是一个分区，若c = c - ，c 2 ，q ，其中g ，( i = 1 ，2 ， k ) 是? c 的子集，满足：c ，u c 2 u u g - - z 和c i n g = f ，i j 。c 中的成员c j ， c 2 ，g 叫做聚类。 2 2 2 文本聚类步骤及方法 文本聚类通常包括以下三个步骤： ( 1 ) 获取结构化的文本集。结构化的文本集是由一组经过预处理的文本特 征向量组成。从文本集中选取的特征向量的好坏直接影响到聚类的质量。如果选 取的特征与聚类目标无关，那么就难以得到良好的聚类结果。对于聚类任务，合 理的特征选择策略应是使同类文本在特征空间中相距较近，异类文本相距较远。 ( 2 ) 执行聚类算法，获得聚类谱系图。聚类算法的原则是获取能够反映特 征空间样本点之间的某些点彼此接近而另外一些远离的性质，即“物以类聚”的 性质。 ( 3 ) 选取合适的聚类阈值。在得到聚类谱系图后，凭借经验，并结合具体 的应用场合确定阙值。样本点经过聚类算法计算后，应呈现一种分割状态，但各 利用单词超团的二分图文本聚类算法 个样本域之间通常不存在明显的界限，因此需要确定一个阈值来作为划分边界的 标准。阈值确定后，就可以直接从谱系图中得到聚类结果。 文本聚类所采用的方法包括以下几类： 层次聚类算法：把类别看作是有层次的，即随着类别层次的变化，类别中的 对象也相应发生变化。层次聚类结果形成一棵类别树，每个类结点还包含若干子 结点，兄弟结点是对其父结点的划分，因此该方法允许在不同的粒度上对数据进 行分类。按照类别树的生成方式，可将层次聚类法分为两种，一种是融合方法 ( 自底向上法) ，另一种是分裂方法( 自顶向下法) 。 分割聚类算法：分割聚类算法将数据集分成若干子集。由于在计算上不可能 搜索全部可能子集空问，因此往往采用一定迭代优化的启发式方法，这就意味着 反复在k 类之间重新定位每类的类别中心，以及重新分配每类中的对象。与层次 聚类不同的是这类算法反复调整聚类结果束进行聚类优化。典型的算法有 k - m e a n s 方法。 基于密度的聚类算法：这种算法认为，类别是向任意方向按相同密度扩张的 连通区域。因此基于密度的聚类算法可以发现任意形状的类别，同时此算法对噪 声有自然的抵制作用。这种算法主要需要考虑数据空m 的密度、连通性与边界区。 其中典型的基于密度的算法是d b s c a n 算法。 基于网格的聚类算法：为了减少搜索复杂度，需要考虑多边形分段区域。一 个分段区域就是空间中的一个划分的小的超立方体，而利用划分空间进行聚类的 方法通常就称为网格聚类算法。每一个分段区域就称为一个单元。网格聚类算法 把对数据的分割转换成对空间的分割。数据分割是通过数据点之间的关系导致空 间的分割而产生的，但是空间分割则是基于输入数据累加的空间小超立方体( 网 格) 。 除此之外还有核聚类算法、基于遗传算法的聚类方法等，本课题研究的也是 一种新兴的聚类算法，即基于超团的聚类算法。不同的聚类算法适用于不同的样 本环境，同时也有着不同的聚类结果。 利用单词超团的二分图文本聚类算法 2 2 3 文本聚类质量评测 文本聚类是无教师的机器学习，聚类没有预先定义好的主题类别，它的目标 是将文档集合分成若干个簇，要求同一簇内文档内容的相似度尽可能大，而不同 簇间的相似度尽可能小。对于聚类结果的评测有着不同的标准，在信息检索领域 中，除了时间和空间等运行效率方面的评测外，更重要的是对信息检索系统的检 索性能进行评测。研究者可以通过测试的结果选择较好的检索技术，或验证检索 系统在真实环境中运行时的效果，以辅助系统的设计、研究和改进。因此检索系 统的性能评测对于检索系统的研制和发展是至关重要的。现在通用的评测标准主 要包括以下几类【4 】【5 】： 1 查准率( p r e c i s i o n ) 它是指检出的相关文献量与检出文献总量的比率，是衡量信息检索系统检出 文献准确度的尺度。假设给定一个查询q ，在某数据集合上有n q 个文档是符合q 所隐含的信息需求的。某个检索系统返回的结果中，有n 。一个是符合要求的， 也就是说在正确的个文档的范围之内；另有n 一一个不符合要求，即落在n q 个文档的范围之外。检索系统一共返回了( n 。一+ n h c o 一) 个结果。查准率定义为： p r e c 妇加。- ! 二。l n 一。n 2 召回度( r e c a l l ) 公式( 2 - - 1 ) 召回度反映了检索系统对某个查询返回的结果中正确结果占全部正确结果 的比例。定义为： r e 翻玎，盟鲤 n 。 公式( 2 2 ) 查准率和召回度是两个互相矛盾的指标。如果我们画出r e c a l l - p r e c i s i o n 图， 就会发现随着召回度的增加，查准率不断下降。因此，在执行检索时需要权衡考 虑这两个指标。如果单纯追求查准率，例如只取把握最大的少数文档作为结果， 那么查准率很高，但召回度被牺牲，用户看到的信息可能很不全面，无法满足要 求或者被误导。反之，如果单纯追求召回度，就会引入大量无关结果，牺牲查准 率，用户会被淹没在结果中，同样无法满足要求【6 】网，因此，需要根据不同的 利j j 啦诃超团的二分图文本聚类算法 信息需求，考虑不同的检索策略，以得到合乎需要的性能指标。 3 正规化的互信息( n o r m a l i z e dm u t u a lm f o r m a t i o n ，n m l ) 正规化的互信息是对查准率和召回度统计信息的一种均衡性度量，用来避免 真实聚类和算法结果因共享信息所导致的噪音。我们可以把某一样本的聚类划分 结果的编号看作真实聚类中按概率分布的变量，这样我们可以假设t 为真实类 别编号，同时假设c 为划分后的类别编号。则n m i 可以定义为： 公式( 2 3 ) 其中h ( ) ( ) 表示x 中的平均信息量；i ( x ，y ) 表示j 与j ，的平均互信息量定义为： 慨y ) = 善n 荟mp 咄) l 0 9 2 面p ( x 丽, y j ) 由上可以得到 公式( 2 4 ) 公式( 2 - - 5 ) 4 条件熵( c o n d i t i o n a le n t r o p y ，c e ) 条件熵表示在已知c 的条件下在t 中保存的有效信息，定义如下： c e = h ( tl c ) = h ( t ，c ) 一( c ) 公式( 2 6 ) 通常c e 的取值范围依赖于真实类别的个数t ，为了达到测量尺度的正规化，通 常采用正规化的条件熵( n o r m a l i z e dc o n d i t i o n a le n t r o p y ，n c e ) n c e ，丝! ! ! 兰2 。h ( t , c ) - h ( c ) h 妊、h i f ) 公式( 2 7 ) 5 错误率( e r r o rr a t e ) 错误率表示划分块中与占比率最大的实际类别样本不同的样本所占的比例， 即划分到错误聚类中的样本比率。可以看作是h ( t c ) 的一个简化。 脚= 砉b 掣 钎 f | f ? ；0 公式( 2 8 ) 6 f m e a s u r e f - m e a s u r e 包含了查准率和召回度的内部信息关联【8 】。我们将每个簇看作是 器 = 打m 掰 瑚 利用单词超团的= 分图文本聚类算法 一个查询结果，同时将每个类别看作希望得到的文档集，这样我们可以按照如下 公式计算每个给定类别的查准率和召回度： 公式( 2 9 ) 公式( 2 1 0 ) 其中c + ，表示第j 个真实类别对应第i 个划分块的查准率，r 口表示第j 个真实 类别对应第i 个划分块的召回度；c 。表示第j 个真实类别划分到第i 个划分块中 的文档个数；c ；+ 和c + ，分别表示第i 个划分块中文档的个数和第j 个真实类别 中文档的个数。由于同一篇文档在聚类过程中可能被划分在多个划分块中，因此 c + ，通常会大于第j 个真实类别中文档的数目。 聚类划分i 和真实类别之间的f - m e a s u r e 可以定义如下： f = 2 p o r o 公式( 2 - - 1 1 ) i ”p i i + r “ 对于整体划分来说，f - m e a s u r e 是一个加权的平均值，当划分结果和真实类 别完全相同的情况下其值才为1 。下面给定义： 叫c + ，掣) 公式( 2 1 2 ) 由于查准率和召回度具有一定的不完整性和片面性，而其他的测量尺度在 此基础上加以调整，在一定范围内可以较准确地反映划分性质的好坏，因此本文 后面的内容主要以正规化的互信息、条件熵、错误率和f - m e a s u r e 作为超团算法 与普通算法之间衡量性能的尺度。 2 2 4 文本聚类的主要应用 1 文档聚类可以作为多文档自动文摘等自然语言处理应用的预处理步骤。 一“ 皇 g g g i - 只 硒 利用学词超团的二分图文本聚类算法 通过对本进行聚类处理，消除冗余信息，生成简明扼要的摘要文档。例如哥伦比 亚大学开发的多文档文摘系统n e w sb l a s t e r 。 2 对搜索引擎的返回结果进行聚类，提高用户获取目标信息的速度和准确 度。系统利用用户输入的检索关键词进行检索，而后对检索到的文档进行聚类处 理，并将各个类别的相关特征反映给用户，用户根据这些特征选择目标聚类，从 而可以缩小检索的范围，用户只需关注比较有希望的主题。另外这种方法也可以 为用户二次检索提供线索。 3 挖掘用户的偏好信息。对用户感兴趣的文档( 如用户浏览器c a c h e 中的 网页) 聚类，从而发现用户的兴趣模式并根据这些偏好信息，进行信息过滤和信 息主动推荐等服务。 4 数字图书馆服务。通过s o m 神经网络等方法，可以将高维空间的文档 拓扑保序地映射n - 维空间，使得聚类结果可视化和便于理解；。 5 文梢集合的自动整理。例如基于聚类的文档浏览系统，可以大大提高浏 览的效率，或者如微软的利用聚类技术对用户提出的查询记录进行聚类，并利用 结果更新搜索引擎网站的f a o 9 1 。 利用单词超团的二分图文本聚类算法 第3 章单词超团的理论设计 本章首先介绍了超团的相关理论，在此基础上提出了单词超团应用于文本 聚类的设想和预期目标；本章的后半部分主要是对该目标的实现过程的描述，其 中包括单词超团作为文档向量的扩展特征的设计和实现，以及对于超团节点的权 值的设定。 3 1 超团的定义 “超团”( h y p e r c l i q u e ) 是近期h u ix i o n g 等人在频繁项集( f r e q u e n ti t e m s e t ) 的基础上提出的一个较新的概念，是一种特殊的频繁项集 5 儿l o 。下面我 们对相关概念加以解释。 3 1 1 关联规则 定义3 1 设，一妊，f ：，i 。 为所有项目的集合，设h 是一个由项目构成的集 合，称为项集。事务t 是一个项目子集，每一个事务具有唯一的事务标识t i d 。 事务t 包含项集a ，当且仅当a t 。如果项集a 中包含k 个项目，则称其为k 项集。d 为事务数据库，项集h 在事务数据库d 中出现的次数占d 中总事务的百 分比叫做项集的支持度( s u p p o r t ) 。如果项集的支持度超过用户给定的最小支持 度阈值，就称该项集是频繁项集( 或大项集) 。 利用单词超幽的二分图文本聚类算法 关联规则就是形如x y 的逻辑蕴含关系，其中x c ，l ，c ，且 盖n y 一妒，x 称作规则的前件，y 是结果，对于关联规则x y ，存在支持度和 信任度。 定义3 2 关联规则支持度 是指规则中所出现模式的频率，如果事务数据库有s 的事务包含x y ，则称 关联规则j y 在d 中的支持度为s ，实际上，可以表示为概率p ( x y ) ，郎 s u p p o r t ( x u y ) = p ( x y ) 。 定义3 3 信任度 是指蕴含的强度，即事务d 中c 的包含x 的交易同时包含x y 。若x 的支持 度是s u p p o r t ( x ) ，则规则的信任度定义为： 训并叫；篙 关联规则开采问题可以描述为从数据集合中生成满足下列两个条件的规则： 1 规则的支持度( s u p p o r t ) ，关联规则开采规则的支持度大于给定的阂值 最小支持度m i n s u p ； 2 规则的信任度大于给定的阙值最小置信度m i n c o n f 。 如果最小支持度和规则的信任度设定的阈值过小，则在挖掘关联规则时将会 出现大量的关联结果，甚至包括关联并不是很紧密的低端规则，这样将会使挖掘 陷入高度复杂的时间和空间复杂度中；反之如果最小支持度和规则的信任度设定 的阈值过大，很多关联规则将被忽略掉，这将导致错过许多挖掘过程感兴趣的规 则，达不到预期的效果。基于这种原因超团理论提出了新的关联规则的信任度。 3 1 2 超团( h y p e r c l i q u ep a t t e r n ) 为了衡量数据集中所有项目的全局性关联信息，作为一个内部项目具有更高 利用单词超团的= 分图文本聚类算法 关联程度的新的关联集合，超团的概念被提了出来。其特点在于，当超团内的某 个项目在事务中出现时，与其属于同一超团的其他全部项目都具有不低于某一特 定值的概率出现在这一事务中。超团信任度就是基于表达这一关联的强度而进行 定义的，同时他给定了一个超团中任意两个项目之间的最小信任度。 定义3 4 超团信任度( h - c o n f i d e n c e ) 项目集h 。的超团信任度| i l c d 矿( p ) 反映项目集p 中全部项目的整体关联程 度，定义为： i l o 咧( p ) 一m 缸 聊矿扛。一i ，i 。) ，咿在：一f l 玉，i 。 ，鲫矿信。一玉，i ，一1 ) ) 其中c o n f 为普通意义上的信任度。 定义3 5 超团 对于一个项目集p ，如果称之为一个超团当且仅当 s u p p o r t ( p ) z0 并且i l c d 巧( p ) 乏h 。 其中口和h 。分别是用户自定义的支持度阈值和超团信任度阈值。 作为一个项目集p 如果满足超团的定义，则该项目集称之为一个超团，其中 每个项目的支持度不低于秽，且任意两个项目之闻的的信任度均不低于h 。；对 于p 的子集d 中的项目，同样满足超团的定义，因此也可以称之为超团。但实 际挖掘中我们真正感兴趣的是项目集p 本身而不是它的子集。一个超团子集并不 能反映整体的关联程度，因此我们需要给出一个最大超团的定义。 定义3 6 最大超团( m a x i m a lh y p e r c l i q u ep a t t e r n ，m h p ) 【1 1 】 对于一个超团 i p ，如果任意一个包含它的集合都不能够满足超团的定义则 我们称h p 是一个最大超团，即 v p p p m h p p e m p h p e h p 并且v p3 p ，p 隹j l 删p 最大超团依赖于给定的支持度和超团信任度，对于不同的支持度和超团信任 度，一个项目集所包含的超团的数目和各个超团的大小是不相同的，下面给出一 个超团的例子。 项目集合i = a b ，c , d ，e ，在该项目集合上存在若干事务t i ( i = - i ，2 1 0 ) ， 每个事务产生的项集如下： 利用单词超团的二分图文本聚类算法 表3 1 示例数据集 t a b l e3 - 1 as a m p l ed a t as e t 事务i d项集事务i d项集 1c e 6b e 2 a b ，c ，e 7b 3 b ，c ，d ，e 8 a c ，e 4b c9 八c ，d 5a b1 0a d 由表3 1 ，我们可以得到各个项目以及按照任意关联规则得到的支持度： 表3 2 示例数据集