（计算机软件与理论专业论文）聚类分析及其在文本挖掘中的应用.pdf

中文摘要 随着信息技术的发展，以电子形式存在的文本信息已经成为人们主要的信息 来源。人们迫切需要能够从w e b 上快速、有效地发现资源和知识的工具。近年来针 对文本数据的文本挖掘已逐渐成为人们研究的新课题。其中，对于文本聚类的研 究已经引起了广泛的重视，并取得了良好的成果。 本文首先对数据挖掘中的聚类分析做了深入的理论研究，以数学的形式表示 和讨论了聚类分析中样本类型、样本相似度测量、类的定义等基本概念，分析了五 种常用的聚类算法，并对算法性能做了分析与比较。 本文随后对于聚类分析在文本挖掘中的应用文本聚类做了研究，讨论了 将无结构的文本数据转化为聚类算法可以处理的结构化数据的方法和以特征向量 形式表示的文本聚类算法。 最后，给出了一个简单的文本聚类模型，并基于k m e a n s 文本聚类算法，对模 型做了一种设计和实现。 关键词：文本挖掘，聚类分析，文本聚类，k - m e a n s 算法，特征向量 a b s t r a c t w i t ht h ed e v e l o p m e n to fi n f o r m a t i o nt e c h n o l o g y , e l e c t r o n i ct e x t sh a v eb e c o m e m o r ea n dm o r e p o p u l a r a ss o u r c eo f i n f o r m a t i o n p e o p l e n e e ds o m et 0 0 1t of i n dr e s o u r c e a n dk n o w l e d g ef r o mt h e ；- r e bu r g e n t l y t e x tm i n i n gh a db e c o m ean e wp r o m i s i n g r e s e a r c hs h b j e c t ，e s p e c i a l l yi nt e x tc l u s t e r i n g ，i nr e c e n ty e a r s t h i sp a p e rm a k e sd e e p l yr e s e a r c ho nt h et h e o r yo fc l u s t e r i n gf i r s t i nt h i ss e c t i o n t h ep a p e rd i s c u s s e st h eb a s i cc o n c e p t si nc l u s t e r i n gi nt h ef o r mo fm a t h e m a t i c sa n dt h e l l i n t r o d u c e ss e v e r a lu s e f u lc l u s t e r i n ga l g o r i t h m ss u e ha sk - m e a n s ，d a s c a n ，s o ma n d m a k e sa c o m p a r e i nt h e o r y t h e nt h i s p a p e r i sd e d i c a t e di n s t u d y i n gt e x tc l u s t e r i n g ，w h i c h i sa s p e c i a l a p p l i c a t i o n o fc l u s t e r i n gi nt e x t m i n i n g i n t h i ss e c t i o nt h e p a p e rd i s c u s s e s t h e t e c h n i q u e s t o c h a n g et h eu n o r g a n i z e d t e x td a t at o o r g a n i z e d d a t aa n ds o m et e x t c l u s t e r i n 2a l g o r i t h mb a s e do nf e a t u r ev e c t o r a tl a s t ，t h i sp a p e r p r e s e n t sa t e x tc l u s t e r i n gm o d e la n dt h e nm a k eas i m p l ed e s i g n t or e a l i z ei tb a s e do nak i n do f k - m e a n s c l u s t e r i n ga l g o r i t h m k e y w o r d ：t e x tm i n i n g , c l u s t e r i n g , t e x tc l u s t e r i n g , k - m e a n s ，f e a t u r e v e c t o r y6 9 5 6 8 8 创新性声明 本人声明所里交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知。除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果：也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均己在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名；堑j 建 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文 在解密后遵守此规定) 本学位论文属于保密在年解密后适用本授权书。 本人签名：蕉! 逮 导师签名； 日期堕：! ：些 日期! ! ：3 第一章绪论 第一章绪论 1 1 课题背景与意义 近年来数据挖掘引起了广泛的关注，一般晚到数据挖掘，我们很容易联想到数 据库中知识的提取。由于电子形式的信息量的飞速增长，如电子出版物，电子邮 件，w e b 页面( 它可被视为一个巨大的互联的动态文本数据库) 等，文本数据库得到 迅速的发展。 传统的信息检索技术已不适应日益增加的大量文本数据处理的需要。在如今 这个信息激增的年代，网上的搜索引擎动辄返回成千上万条相关的检索结果，由 于大量的信息是按文本方式存在的，用户需要有关的工具完成不同文档的比较， 以及文档重要性和相关性排列，或找出多文档的模式和趋势。怎样在浩如烟海的 信息中找出真正自己感兴趣的话题就必须进行文本挖掘，文本挖掘( t e x tm i n i n 曲 成了数据挖掘的一个很有前途的研究方向。 因为文本处理的特殊性，它不象数据库中是结构化数据，文本处理需要自然 语言理解的支持，而目前机器对自然语言的理解还存在着歧义问题的解决，因此 文本挖掘还不能达到理解的层次。但是文本挖掘目前的研究领域如文本的自动分 类，文本信息的自动抽取( 如自动生成文章摘要) 和文本聚类已经能解决一些如不 同文档的比较及文档重要性和相关性排列等问题。 文本的自动分类是在分析文本内容的基础上给文本分配一个或多个比较合适 的类别。它通常由两个阶段组成：训练阶段和分类阶段。在训练阶段，从训练文 本中学习分类知识，建立分类器类模型：在分类阶段根据分类器将输入文本分到 最可能的类别中。从这个过程可以看出，分类需要事先存在的人工分类好的训练 文档集，也就是说，分类目录是事先确定的。 但是，万维网上信息不断动态变化，经常会出现新的话题很难用已有的分类 体系来刻画。如果重新进行分类，就必须重新建立分类好的训练文档集，而获得 大量带有类别标注的样本的代价是很大的。这时文本的聚类就显得很重要。聚类 分析是文本挖掘的主要手段之一。它的主要作用是( 1 ) 通过对检索结果的聚类，将 检索到的大量网页以一定的类别提供给用户，使用户能快速定位查找的目标。( 2 ) 自动生成分类目录；( 3 ) 通过相似网页的归并便于分析网页的共性。 w e b 文档般是由特殊的标记和文本组成的，因此对文本文档的聚类的研究必 然也可以用在w e b 文档的聚类中，这也就是本文研究的目的。 聚类分析及其在文本挖掘中的应用 1 2 文本挖掘的研究现状 所谓数据挖掘( d a t am i n i n g ) 就是从大量的、不完全的、有噪声的、模糊的、 随机的原始数据中提取隐含在其中的事先未知的但又是潜在有用的信息和知识的 过程。数据挖掘在2 0 世纪9 0 年代获得了突飞猛进的发展。采用数据挖掘技术可 以使公司从关系数据表等格式化好的数据中轻松获取知识，这已是一种常见的商 业行为。但是，由于现实世界中大量信息是以文本形式存在的，能不能用计算机 从文本中发现有用的知识昵? 这就是人们现在所研究的文本挖掘。 文本挖掘属于数据挖掘这一交叉学科的一个具体领域，二者既有联系又有区 别：数据挖掘处理的对象是结构化的数值信息，以便发现不同数据属性的关联规 则，对记录进行聚类及分类处理，构造数据的预测模型，而文本挖掘的主要任务 是分析文档数据库的内容，发现文档数据集中概念、文档之间的相互关系和相互 作用，为用户提供相关知识和信息：此外，文本挖掘处理的是非结构化的文本信 息，而不是数据挖掘中采用的结构化数据信息。文本挖掘技术就成为处理大量的 文本信息的必然选择。 1 2 1 文本挖掘的定义 文本挖掘作为数据挖掘的个新主题，要给它下一个全面、完整、并被普遍 接受的定义还很困难，需要国内外学者开展更多的研究以便进行精确的定义，参 照数据挖掘的概念，文本挖掘定义如下： 文本挖掘是指从大薰文本数据中抽取事先未知的、可理解的、最终可用的信 息或知识的过程。直观地说，当数据挖掘的对象完全由文本数据类型组成时，这 个过程就称为文本挖掘。它超出了基于关键字和相似度的信息检索的范畴，对文 本信息的挖掘主要是发现某些文字出现的规律以及文字与语义、语法间的联系， 用于自然语言的处理，如机器翻译、信息检索、信息过滤等，通常采用信息提取、 文本分类、文本聚类、自动文摘和文本可视化等技术从非结构化文本数据中发现 知识。 文本挖掘作为数据挖掘的一个研究分支，用于基于文本信息的知识发现。它 利用智能算法，如神经网络、基于案例的推理、可能性推理等，并结合文字处理 技术，分析大量的非结构化文本源( 如文档、电子表格、客户电子邮件、问题查询、 网页等) ，抽取或标记关键字概念，文字问的关系，并按照内容对文档进行分类聚 类，获取有用的知识和信息。文本挖掘研究的关键在于文本内容的量化表征。 文本挖掘分为如下几个步骤：( 1 ) 资源发现，即检索所需的文档；( 2 ) 信息选 择和预处理，即从检索到的文本资源中自动挑选和预先处理得到专门的信息：( 3 ) 第一章绪论 概括化，即从单个的文档以及多个文档之间发现普遍的模式；( 4 ) 分析，对挖掘出 的模式进行确认或者解释：最后，得到所需的知识模式。 1 2 2 文本挖掘的分类 文本挖掘可以对上大量文档集合的内容进行总结、分类、聚类、关联分析， 以及利用文档进行趋势预测等。 文本总结是指从文档中抽取关键信息，用简洁的形式对文档内容进行摘要或 解释。这样，用户不需要浏览全文就可以了解文档或文档集合的总体内容。文本 总结在有些场合十分有用，例如，搜索引擎在向用户返回查询结果时，通常需要 给出文档的摘要。但目前，绝大部分搜索引擎采用的方法是简单地截取文档的前 几行。 文本分类是指按照预先定义的主题类别，为文档集合中的每个文档确定一个 类别。这样，用户不但能够方便地浏览文档，而且可以通过限制搜索范围来使文 档的查找更为容易。目前，y a h o o 通过人工来对w e b 上的文档进行分类，这大大影 响了索引的页面数目( y a h o o 索引的覆盖范围远远小于a 1 t a v i s t a 等搜索引擎) 。 利用文本分类技术可以对大量文档进行快速、有效地自动分类。目前，文本分类 的算法有很多种，比较常用的有t f i d f 和n a i v eb a y e s 等方法。 文本聚类与分类的不同之处在于，聚类没有预先定义好的主题类别，它的目 标是将文档集合分成若干个簇，要求同一簇内文档内容的相似度尽可能地大，而 不同簇问的相似度尽可能地小。h e a r s t 等人的研究已经证明了“聚类假设”，即与 用户查询相关的文档通常会聚类得比较靠近，而远离与用户查询不相关的文档。 因此，我们可以利用文本聚类技术将搜索引擎的检索结果划分为若干个簇，用户 只需要考虑那些相关的簇，大大缩小了所需要浏览的结果数量。目前，有多种文 本聚类算法，大致可以分为两种类型：以g - h a c 等算法为代表的层次凝聚法，以 k - m e a n s 等算法为代表的平面划分法。 关联分孝厅是指从文档集合中找出不同词语之间的关系。b r i n 提出了一种从大 量文档中发现一对词语出现模式的算法，并用来在w e b 上寻找作者和书名的出现 模式，从而发现了数千本在a m a z o n 网站上找不到的新书籍。w a n g 等人以w e b 上的 电影介绍作为测试文档，通过使用o e m 模型从这些半结构化的页面中抽取词语项， 进而得到一些关于电影名称、导演、演员、编剧的出现模式。 分布分析与趋势预测是指通过对文档的分析，得到特定数据在某个历史时刻 的情况或将来的取值趋势。f e l d m a n 等人使用多种分布模型对路透社的两万多篇新 闻进行了挖掘，得到主题、国家、组织、人、股票交易之间的相对分布，揭示了 一些有趣的趋势。w u t h r i c h 等人通过分析w e b 上出版的权威性经济文章，对每天 聚类分析及其在文本挖掘中的虑用 的股票市场指数进行预测，取得了良好的效果。 1 3 文本聚类 文本聚类是一种有效的文本挖掘方法，能从大量文本数据中发现潜在的知识和 规律，它既是一个知识获取技术，也是一种文本处理过程。本文在聚类分析的基 础上对文本聚类进行深入的研究。下面分几个方面来探讨下文本聚类研究的意 义。 ( 1 ) 文本的聚类处理是文本有效管理的基础 文本在i n t e r n e t 上是信息资源的一个主要形式，面对这样一个信息海洋，人们 往往会陷入窘迫的境地：一方面收到太多的信息无从选择和消化，淹没在繁杂的 信息中；另一方面是信息迷失，人们难于找到自己真正所需的信息。因此，能够 快速高效地获取所需要的信息是每个人迫切要求，因而对大量的信息自动地提取 其概念空间，提供给人一个清晰的框架，帮助人们进行信息的检索和分类则显得 将必不可少。围绕文本信息这一资源开展的各种学术研究和业界应用非常活跃， 如今年出现的各种i n t e r n e t 搜索引擎、数字图书馆、电子商务等，这些领域的研 究者在进行信息检索和分类的研究上取得了令人可喜的进展，但仍然存在着许多 亟待解决的问题，即处理效果不能令人满意，在相当一定的程度上，人为地干预 成分占的比较大。需要将数据挖掘技术引入文本的检索和分类领域。而文本聚类 作为文本挖掘的基础工作将尤为显得重要。 ( 2 ) 文本聚类是文本挖掘的自身需要 所谓的文本挖掘就是以文本作为数据的处理单元，从文本无序性、多样性、广 泛性中找出可以利用的、有一定关系的、作为信息指导性的潜在模式的过程。而 在这个过程中，必然要将纷繁冗杂的文本信息按照某种特定的方式有序地排列。 其中也不乏有一个体系结构存在，这个层次结构作为类别的合理展示必不可少。 而且，利用计算机对海量的文本聚类及类别标识，是文本挖掘自身的需要，为进 一步进行其他途径的挖掘提供了很好的利用效果。 ( 3 ) 文本聚类的有效标识海量i n t e r n e t 信息检索的有效手段 信息检索是指从大量的文档集合中找到与查询请求相关的、恰当数目的文档子 集。要使检索的结果准确而且精确，就需要对检索的对象进行准确分析，在进行 抽象的过程中起到界定范围的作用；而目前的网上信息检索却远不能达到这种效 果，经常是搜索出成千上万条纪录，远没有达到准而精的效果。因此要对网页做 一个适当而全面的类归并，这不但为使用者提供了方便，而且还有利于信息资源 的合理存储。现在的网页大都是人工的进行归类，面临浩瀚的信息海洋，这样下 去必将耗费大量的人力资源。况且人不是机器，长期从事单一而冗杂的事件，必 第一章绪论 将导致错误的出现。利用机器自动地从事这方面任务已经成为迫切的需要。 1 4 论文内容的安排 目前，国内外对文本聚类的研究主要集中在文本特征的提取、聚类算法的提出、 对聚类结果的评价和聚类结果的表示。本文主要研究中文文本的自动聚类，因此 在文本的预处理过程中也不同于西文的方式。即文本的预处理要依靠自动分词技 术把句子划分为一个个的词单元。在此基础上，进行文本特征的提取。又因为计 算机只能理解a s c i i 字符，而无法理解非格式化的文本内容，我们必须建立文本模 型使聚类算法能进行处理。 本文首先对数据挖掘中的聚类分析做了深入的理论研究，以数学的形式表示 和讨论了聚类分析中样本类型、样本相似度测量、类的定义等基本概念，分析了五 种常用的聚类算法。随后对于聚类分析在文本挖掘中的应用文本聚类做了研 究，讨论了将无结构的文本数据转化为聚类算法可以处理的结构化数据的方法和 以特征向量形式表示的文本聚类算法。最后，设计了一个简单的中文文本聚类模 型，并基于k - m e a n s 文本聚类算法，对模型做了实现。 全文共分六章，文章整体结构以及各章节内容如下： 第一章绪论，介绍了关于文本挖掘与文本聚类的一些背景知识，阐述了此研 究课题的必要性。 第二章论述了聚类分析及其基本概念。 第三章分析和比较了几种常用的聚类算法。 第四章研究了文本聚类的相关问题和技术，讨论了将无结构的文本数据转化 为聚类算法可以处理的结构化数据的方法和以特征向量形式表示的文本聚类算 法。 第五章给出了一个简单的文本聚类模型，并基于k - m e a n s 文本聚类算法，对 模型做了一种设计和实现。 第六章回顾并总结了全文。 第章聚类分析 第二章聚类分析 2 1 聚类分析定义 聚类( c l u s t e r i n g ) 是一个将数据集划分为若干组( c l a s s ) 或类( c l u s t e r ) 的过程，并 使得同一个组内的数据对象具有较高的相似度，而不同组中的数据对象则是不相 似的。相似或不相似的度量是基于数据对象描述的取值来确定的。通常就是利用 ( 各对象问) 距离来进行描述。 将一群( s e t ) 物理的或抽象的对象，根据它们之间的相似程度，分为若干组 ( g r o u p ) ，其中相似的对象构成一组，这一过程就称为聚类过程( c l u s t e r i n g ) ，一个聚 类( c l u s t e r i n g ) ，又称簇，就是由彼此相似的一组对象所构成的集合，不同聚类中 对象通常是不相似的。聚类分析就是从给定的数据集中搜索数据对象之间所存在 的有价值联系。而在许多应用中，一个聚类中所有对象常常被当作一个对象来进 行处理或分析。 聚类分析是一种重要的人类行为。早在儿童时期，个人就是通过不断完善 潜意识中的分类模式，来学会识别不同物体，如：猫和狗，动物和植物等。聚类 分析己被应用到许多领域，其中包括：模式识别、数据分析、图象处理和市场分 析等。通过聚类，人可以辨识出空旷和拥挤的区域，进而发现整个的分布模式， 以及数据属性之间所存在有价值的相关联系。 聚类分析的典型应用主要有：在商业方面，聚类分析可以帮助市场人员发现 顾客群中所存在的不同特征的组群，并可以利用购买模式来描述这些具有不同特 征的顾客组群。在生物学方面，聚类分析可以用来获取动物或植物所存在的层次 结构( t a x o n o m i e s ) ，可根据基因功能对其进行分类以获得对人群中所固有的结构更 深入的了解。聚类还可以从地球观测数据库中帮助识别具有相似的土地使用情况 的区域。此外，还可以帮助分类识别互联网上的文档以便进行信息发现。作为数 据挖掘的一项功能，聚类分析还可以作为一个单独使用的工具，来帮助分析数据 的分布、了解各数据类的特征、确定所感兴趣的数据类以便作进一步分柝。当然 聚类分析也可以作为其他算法( 诸如：分类和定性归纳算法) 的预处理步骤。 数据聚类分析是一个正在蓬勃发展的领域。聚类分析所涉及的领域包括：数 据挖掘、统计学、机器学习、空间数据库技术、生物学和市场学等。由于各应用 数据库所包含的数据量越来越大，聚类分析己成为数据挖掘研究中一个非常活跃 的研究课题。 作为统计学的一个分支，聚类分析已有多年的历史，这些研究主要集中在基 于距离的聚类分析方面。许多统计软件包，诸如：s - p l u s ，s p s s 和s a s ，都包含基于 k 一均值、k 一中心等诸多聚类分析方法。在机器学习中，聚类分析属于一种无( 教师) 聚类分析及其在文本挖掘中的应用 监督的学习方法。与分类学习不同，无( 教师) 监督学习不依靠事先确定的数据类 别，以及标有数据类别的学习训练样本集合。正因为如此，聚类分析是一种观察 式学习法( 1 e a r n i n gb yo b s e r v a t i o n ) ，而不是示例式学习法( t e a m i n gb ye x a m p l e ) 。在 概念聚类方法中，仅当一组对象可以由一个概念所描述时，这些对象方才能构成 一个类。这与基于几何距离表示相似程度并进行聚类的传统聚类方法有所不同。 概念聚类方法主要包含两部分内容：发现适当的类；根据每个类形成相应的 特征描述，这与在分类学习中的方法类似。聚类分析的基本指导思想是最大程度 地实现类中对象相似度最大，类间对象相似度最小。 在数据挖掘中，大多数工作都集中在设计能够有效、高效地对大数据库进行 聚类分析的方法上。相关的研究课题包括：聚类方法的可扩展性、复杂形状和复 杂数据类型的聚类分析及其有效高效性、高维聚类技术，以及混合数值属性与符 号属性数据库中的聚类分析方法等。 2 2 样本类型和相似度测量 聚类分析的目的是揭示样本点之间最本质的“抱团”性质。要想定量地处理 一批样本点，首先必须对这些样本点的性质进行定量的表示。领域专家确定采用 哪些指标特征变量来精确刻画样本的性质，以及如何定义样本之间的相似性测度。 2 2 1 样本类型 一般地，我们常常使用多个指标特征变量来描述一个样本点。指标特征变量 可以分为以下3 种，不同类型的指标特征变量有不同的处理策略。 间隔尺度：使用实数来表示的数量信息，比如温度、浓度、长度等。 有序尺度：特征变量取离散值，没有数量信息，但是具有次序关系，比如成 绩分为优、良、中、及格等。 名义尺度：特征变量取离散值，不仅没有数量信息，而且也没有次序关系， 它仅仅是个名称而已。比如肤色分为黄、白、棕、黑等。 对于间隔尺度的指标特征变量，一个样本点实际上就是r 。空间中的一点，可 以很方便地定义加、减、乘、除以及各种复杂运算，它和我们的直观是很一致的。 而对于名义尺度特征变量就没有这么便利了，因为对于这种特征变量无法定义合 适的运算。所以，现在聚类分析的大部分研究都集中在间隔尺度特征变量上，涉 及一些名义尺度特征变量，对有序尺度特征变量就更少了。 假如我们选择了1 3 个指标特征变量，那么m 个样本点就可以表示成一个m ” 的样本矩阵： 第二章聚类分析 a ，= a 1 1 o l2 a 2 1 0 2 2 2 2 2 相似度测量 l n a 2 ” d “ 式( 2 一i ) 聚类分析按照样本在性质上的亲疏远近的程度进行分类。为了使类分得合理， 必须描述样本之间的亲疏远近的程度。刻画样本点之间的相似性主要有以下两类 函数：距离函数和相似系数。 1 _ 距离函数：设使用n 个指标特征变量来描述样本，那么我们就可以把每个 样本点看作1 1 _ 维空间中的一个点，进而使用某种距离来表示样本点之间的相似性， 距离较近的样本点性质较相似，距离较远的样本点则差异较大。那么，什么样的 函数才能称为距离函数呢? 设q 是样本点集合，如果函数d ：q q r 满足以下条件，我们都称之为 距离函数。 ( 1 ) 正定性d ( x ，_ y ) 0式( 2 2 ) ( 2 ) d ( x ，x j = 0式( 2 3 ) ( 3 ) 对称性d ( x ，y ) = d ( y ，工) ( 4 ) 三角不等式d ( x ，y ) + d ，z ) d g ，z ) 有时我们定义的距离函数不满足三角不等式， 离。聚类分析中常常采用以下3 种距离函数： 明氏( m i n k o w s k i ) 距离 d ( x ，y ) ：i e i x , - 式( 2 4 ) 式( 2 5 ) 从广义的角度我们也称之为距 式( 2 6 ) 当q 取1 ，2 ，无穷大时，则分别得 ( 1 ) 绝对值距离 ( 2 ) 欧式( e u c l i d ) 距离 ( 3 ) 切比雪夫( c h e b y s h e v ) 距离 因为明氏距离直观，计算简便，是实际应用中采用最多的一类距离函数。值 得强调的是欧式距离的一个优点：当坐标轴进行正交旋转时，欧式距离保持不变。 因而如果对原坐标系进行平移和旋转处理后，样本集合仍然能够保持原来的相似 聚类分析及其在义本挖掘中的应用 结构。然而明氏距离也有不足之处： 首先，明氏距离受指标特征变量的量纲影响甚大。例如，一些特征变量采用 厘米为量纲表示身高，另一些特征变量采用米为量纲；还有一些特征变量之间从 根本上缺乏度量的可比性和一致性。使用明氏距离时，特征变量量纲一定要一致， 否则一些特征变量的作用将被淹没。对于量纲相差悬殊或没有一致语义的情况， 可以首先对数据进行标准化处理以统一量纲，然后再计算距离。 其次，明氏距离没有考虑指标特征变量的多重相关性。我们在选择描述样本 的指标特征变量时，为了达到没有遗漏的目的，常常对一种性质用不同的名目多 次描述，这样就会造成信息重叠，片面地强调了某一些性质，其他的一些性质的 作用就会被削弱。克服多重相关性的方法一是慎重选择描述指标特征变量，根据 领域知识或者采用特征变量聚类的方法，选择合适的特征变量集合；或者采用下 述的马氏距离。 马氏( m a l a l a i l o i s l 距离 d 伍，】，) = 一y 厂+ + 一y ) 其中，是样本矩阵a 的协差阵，是总体分布的协差估计量。 马氏距离是明氏距离的改进，它对于一切线性变换是不变的： 离受量纲影响的缺点；马氏距离也部分克服了多重相关性。 式( 2 7 ) 克服了明氏距 马氏距离具有这么多优点，是不是应该在聚类分析中尽量采用呢? 然而以下 考虑使得它无法象想象中应用的那么广泛。在尚未形成类之前，直接采用整体样 本矩阵的均值和协差阵来求马氏距离，效果不是很好。比较好的办法是使用各个 类的协差阵来计算马氏距离，同类样本点之间距离应当采用这一类的协差阵进行 计算。可是这里面隐含了一个循环：类的形成依赖于定义样本点之间的距离，而 合理的马氏距离又依赖于类的形成，而且马氏距离的计算量比较大，对于大规模 的数据不太适用。马氏距离在分类算法比较常用。 兰氏( l a n c e ) 距离 。( ，y ) _ e l x i , 叶- z l f 式( 2 8 ) 兰氏距离克服了明氏距离受量纲影响的缺点，但是没有考虑多重相关性。 2 相似系数：两个样本点愈相似，则相似系数值愈接近1 ；样本点愈不相似 则相似系数值愈接近0 。这样就可以使用相似系数值来刻画样本点性质的相似性。 如果一个函数c ：v x v 一 - l ，1 满足以下条件，我们就称之为相似系数函数。 ( 1 ) c 伍，y 】s 1 ( 2 ) c ( x ，x ) = 1 式( 2 9 ) 式( 2 ，1 0 ) 第一章聚类分析 两种 ( 3 ) c ( x ，y ) = c ( r ，x ) 式( 2 - 11 ) c ( x ，y ) 越接近1 ，两个特征变量问的关系越密切。经常采用的相似系数有以下 a 夹角余弦 c ( x ，y ) = 置+ f i j ( f l2 ) 式f 2 - 1 2 ) 这是受相似形的启发而来的，夹角余弦函数忽律各个向量的绝对长度，着重 从形状方面考虑它们之间的关系。当两个向量的方向相近时，夹角余弦值较大， 反之则较小。特殊地，当两个向量平行时，夹角余弦值为1 ；而正交时余弦值为0 。 b 相关系数 c ( x ，y ) = 协，一i ) + 一f ) 式( 2 一1 3 ) 相关系数是对向量做标准差标准化后的夹角余弦。它表示两个向量的线性相 关的程度。 2 3 类的定义 由于客观事物纷繁芜杂的特性，以及我们在特征提取过程中用来表示样本点 性质的特征变量的不同选择，使得样本点的表示很不相同，在不同的问题中类的 定义也是不同的。要想给类下一个通用，严格的定义看来是不可能的，7 提出以 下几种不同的类的定义，不同的定义适用于不同的应用场合。 设g 表示一个有k 个样本的集合，s ，表示其中的样本，t 和v 为预设闽值。 定义l ：如果对于任意s i ，s ，g ，都有d ( s ，s ，) t ，则g 称为一个类。 定义2 ：如果对于每个s i g ，都有吉；d ( s ，s ，) 只那么g 称为一类。 定义3 ：如果对于每个s i ，s ，g ，都有 高习莩军d p 一) 衄p 鹕) 矿 那么g 称为一类。 定义4 ：对于任意样本s ；，都存在g 中一个样本s ，满足d ( s ；，s i ) t ，财 聚娄分析及其在文本挖掘中的应用 称g 为一个类。 以上几种定义中，定义1 是要求最高的凡是满足定义1 要求的类，肯定满 足其他几种定义；儿是满足定义2 的集合，也必定满足定义3 。 设有类g ，类中共有k 个样本，我们常常从以下几个角度来刻画类的特征： ( 1 ) 均值或中心 扣- 。 z s - 式( 2 1 4 ) ( 2 ) 样本协差阵c ，表示样本点的散布程度 c = 击；p ，一i ，一j ) r 式( 2 - 1 5 ) ( 3 ) 类的直径r r = 击；p ，一i 一j ) 式( 2 ) 2 4 聚类过程 在实际应用聚类分析中，我们根据有无领域知识参与将整个过程分解为三个 环节，每个步骤都有其明确的任务，这样对于整个聚类分析的过程就会有更清晰 的认识。详见图2 1 。 第一步是特征抽取。它的输入是原始样本，由领域专家决定使用哪些特征来 深刻地刻画样本的本质性质和结构。特征抽取的结果是输出一个矩阵，每一行是 一个样本，每一列是一个特征指标变量。 选取特征的优劣将直接影响以后的分析和决策。如果第一步就选择了和聚类 意图根本无关的特征变量，企图得到良好的聚类结果则无异于缘木求鱼。因为无 论后续步骤采用多么优良的聚类算法和阈值选择方案，都不可能计算出执行者的 意图。合理的特征选取方案应当使得同类样本在特征空间中相距较近，异类样本 则相距较远。 在有些应用场合还需要将得到的样本矩阵进行一些后处理工作。比如为了统 一量纲就对变量进行标准化处理，这样采用不同量纲的变量才具有可比性：在有 些场合可能选择的特征变量太多，不利于以后的分析和决策，这时可以先进行一 下降维处理：仅凭经验和领域知识选择的特征变量有可能是相关的，进行主成分 分析就可以消除变量问的相关性，从而得到一些相互独立的特征变量。 第二步是执行聚类算法，获得聚类谱系图。聚类的输入是一个样本矩阵，它 把一个样本想象成特征变量空间中的一个点。聚类算法的目的就是获得能够反映n 第二章聚类分析 维空f b j 中这些样本点之间的最本质的“抱团”性质。这一步没有领域专家的参与， 它除了几何知识外不考虑任何的领域知识，不考虑特征变量在其领域中的特定含 义，仅仅认为它是特征空间中一维而已。 特征提取领域知识 聚类算法 选取阈值领域知识 图2 1 聚类过程示例图 聚类算法的输出一般是一个聚类谱系图，由粗到细地反映了所有的分类情况； 或者直接给出具体的分类方案，包括总共分成几类，每类具体包含那些样本点等 等。 第三步是选取合适的分类阈值。在得到了聚类谱系图之后，领域专家凭借经 验和领域知识，根据具体的应用场合，决定闽值的选取。选定阈值之后，就能够 从聚类谱系图上直接看出分类方案。没有领域专家的参与，不考虑具体的应用背 景，而仅仅依赖于从聚类谱系图出发寻找聚类指数突变点，或者求最小生成树的 长边等等，往往不会得到满意的结果。 领域专家还可以对聚类结果结合领域知识进行进一步的分析，从而加深样本 点和特征变量的认识。 总之，实际应用聚类分析是一个需要多方参与的过程，它无法脱离开领域专 家的参与，聚类算法仅仅是整个聚类流程中的一环而已，光依靠聚类算法专家一 般不会得到满意的效果。关于聚类算法，我们将在下一章中重点讨论几种常用的 聚类分析算法。 2 5 聚类分析中的孤立点问题 孤立点分析是聚类分析中很重要的部分，用来发现数据集中显著不同于其 聚类分析及其在文本挖掘中的应用 它数据的对象。好的聚类算法对孤立点应该是不敏感的，我们可以用能否检测出 孤立点来判断聚类方法的好坏。而且孤立点本身对用户也是有意义的。因为这些 异常数据可能就是用户非常感兴趣而事先所未能预料的信息，包括以下几种模式： 不满足常规类的异常事例；出现在模式边缘的特异点；在不同时刻发生了显著变 化的某个元素或集合等等。通常孤立点分析的一个重要特征就是它可以有效地过 滤大量的不感兴趣的模式，比如一些常识性知识( c o m m o ns e n s e ) 。孤立点分析的主 要应用有：电信和信用卡用户的欺诈检测、发现极高收入或极低收入的客户的行 为模式等等。因此，挖掘并分析这些奇异数据是有重要意义的。 那么什么是孤立点( o u t l i n e r ) 的定义 7 h a w k i n s 给出了孤立点的本质性的定义 【1 2 】：孤立点是在数据集中与众不同的数据，使人怀疑这些数据并非随机偏差，而 是产生于完全不同的机制。聚类算法对孤立点的定义是聚类嵌于其中的背景噪声。 孤立点探测算法对孤立点的定义：孤立点是既不属于聚类也不属于背景噪声的点， 他们的行为与正常的行为有很大不同。 孤立点可能是度量或执行错误所导致的。例如，一个人的年龄为一9 9 9 可能是 程序对未纪录的年龄的缺省设置所产生的。另外，孤立点也可能是固定数据的变 异性结果。例如，一个公司的首席执行官的工资自然远远高于公司其他雇员的工 资，成为一个孤立点。 异常探测方法主要有以下几类。 首先是基于统计( s t a t i s t i c a l - b a s e d ) 的方法。 假设给定的数据集服从一个随机分布( 如正态分布等) ，用不一致性测试 ( d i s c o r d a n c y t e s t ) 识别异常。存在的问题：在许多情况下，用户并不知道这个数据 分布。而且现实数据也往往不符合任何一种理想状态的数学分布：即使在低维( 一 维或二维) 时的数据分布己知，在高维情况下，估计数据点的分布是极其困难的。 其次有基于距离( d i s t a n c e - b a s e d ) 的方法。 k n o r r 提出一种基于距离的异常探测方法。基于距离的异常定义：数据集s 中一 个对象o 称为d b ( p ，d ) 一o u t l i e r ，如果它满足下列性质：数据集s 中至少p * 1 0 0 的对象 与o 的距离大于距离d 。采用不同的参数p 和d ，d b ( p d ) 一o u t l i e r 可以表示所有的基于 距离的异常。 其他方法还有：基于偏差( d e v i a t i o n b a s e d ) 的方法；基于密度d e n s i t y - b a s e d ) 的方法；高维数据的异常探测等。 第三章几种常用聚娄的分析与比较 第三章几种常用聚类算法的分析与比较 3 i 常用聚类算法的分类 目前存在大量的聚类算法。算法的选择取决于数据的类型、聚类的目的和应 用。大体上主要的聚类算法可以划分为这么几类： ( 1 ) 划分方法 给定一个n 个对象，一个划分方法构建对象的k 个划分，每个划分表示个聚 簇，并且k 生n 。给定要构建的划分的数目k ，划分方法首先创建一个初始划分。然 后采用一种迭代的重定位技术，尝试通过对象在划分问移动来改进划分。个好 的划分的一般准则是：在同一个类中的对象之间尽可能“接近”或相关，而不同 类中的对象之间尽可能“远离”或不同。目前比较流行的是k 平均算法，k 一中心 点算法两种启发式的划分方法。 ( 2 ) 层次的方法 层次的方法对给定数据对象集合进行层次的分解。根据层次的分解如何形成， 层次的方法可以分为凝聚的和分裂的。凝聚的方法，也称为自底向上的方法，一 开始将没个对象作为一个单独的一个组，然后相继地合并相近的对象或组，直到 所有的组合并为一个，或者达到一个终止条件。分裂的方法，也称为自顶向下的 方法，一开始将所有的对象置于一个簇中，在迭代的每一步中，一个簇分裂为更 小的簇，直到最终每个对象在单独的一个簇中，或者达到个终止条件。 ( 3 ) 基于密度的方法 绝大多数划分方法基于对象之间的距离进行聚类，这样的方法只能发现球状 的簇，而在发现任意形状的簇上遇到了困难，随之提出了基于密度的方法。其主 要思想是：只要i 临近区域的密度( 对象或者数据点的数目) 超过某个闭值，就继续 聚类。d b s c a n 和o p t i c s 是其中两种有代表性的方法。 ( 4 ) 基于网格的方法 基于网格的方法是把对象空间量化为有限数日的单元，形成了一个网格结构。 所有地聚类操作都在这个网格结构( 即量化的空间) 上进行。这种方法的主要优点 是它的处理速度很快，其处理时间独立于数据对象的数目，只与量化空间的每一 维的单元数目有关。s t i n g 是基于网格方法的一个典型算法。 ( 5 ) 基于模型的方法 基于模型的方法为每个簇假定了一个模型，寻找数据对给定模型的最佳拟合。 一个基于模型的算法可能通过构建反映数据点空间帆布的密度的熟来定位聚类， 也可能基于标准的统计数字自动决定聚类的数日，考虑“噪声”数据或者孤立点， 聚类分析及其在文本挖掘中的应用 从而产生健壮地聚类方法。 3 2 划分的k - m e a n s 聚类算法 k m e a n s 算法以k 为参数，把n 个对象分为k 个聚类，以使聚类内具有较高的 相似度，而且聚类间的相似度较低。相似度的计算根据一个聚类中对象的平均值( k 看作聚类的中心) 来进行。 k - m e a n s 算法的处理流程如下：首先，随机地选择k 个对象，每个对象初始地 代表了一个簇的平均值或中心。对剩余的每个对象，根据其与各个聚类中心的距 离将它赋给最近的簇。然后重新计算每个簇的平均值。这个过程不断重复，直到 准则函数收敛。通常，采用平方误差准则，其定义如下： k e = z i p m ，1 2 式( 3 1 ) 止】p e c ， 其中，e 是数据库中所有对象与相应聚类中心的均方差之和，p 为代表对象空 间中的一个点，m i 为聚类c i 的均值( p 和m 。均是多维的) 。该式所示聚类标准旨在 使所有获得的聚类有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能 的分开。图3 1 给出了k m e a n s 算法的概述。 输入：聚类个数k ，以及包含n 个数据对象的数据库。 输出：满足方差最小标准的k 个聚类。 处理流程： ( 1 1 从1 3 个数据对象中任意选取k 个对象作为初始簇中心； ( 2 ) 循环下述流程( 3 ) 到( 4 ) ，直到每个聚类不再发生变化为止： ( 3 ) 根据每个簇中对象的均值( 中心对象) ，计算每个对象与这些中心对象的距 离，并根据最小距离重新对相应对象进行划分： ( 4 ) 重新计算每个( 有变化) 簇的均值 图3 1k m e a n s 算法 这个算法尝试找出使平方误差函数值最小的k 个划分。当结果是密集的，而 簇与簇之间区别明显时，它的效果较好。对处理大数据集，该算法是相对可伸缩 的和高效率的，因为它的复杂度是o ( n k t ) ，其中，n 是所有对象的数目，k 是簇的 数目，t 是迭代的次数。通常地，k n ，且t l ； ( 4 ) 通过随机采样消除异常数据，即若一个聚类增长太侵，就除去它： ( 5 ) 对部分聚类进行再聚类，落在每个新获得的聚类中的代表点，则根据收缩 聚类分析及其在文本挖掘中的应用 因子口收缩或向聚类中心移动。这些点将要用于代表并描绘出聚类的边界。 ( 6 ) 用相应的簇标签来标记数据。 绝大多数聚类算法或者擅长处理球形和相似大小的聚类，或者在存在孤立点 时变得比较脆弱。c u r e ( c l u s t e r i n g u s i n g r e p r e s e n t a t i v e s ) 解决了偏好球形和相似大 小的问题，在处理孤立点上也更加健壮。 在孤立点存在的情况下，c u r e 也可以产生高质量的聚类结果，支持复杂形状 和不同大小的聚类。该算法只要求对整个数据库的一遍扫描。因此，c u r e 的复杂 度是0 ( n ) 。敏感度分析显示尽管些参数变化可能不影响聚类质量，一般来说， 参数设置确实对聚类结果有显著的影响。 3 4 基于高密度连接区域的d b s c a n 聚类算法 为了发现任意形状的聚类结果，提出了基于密度的聚类方法。这类方法将类 看作是数据空间中被低密度区域分隔开的高密度对象区域。 d b s c a n 是一个基于密度的聚类算法。该算法将具有足够高密度的区域划分 为类，并可以在带有“噪声”的空间数据库中发现任意形状的聚类。它定义类为 密度相连的点的最大集合。 基于密度的聚类中的相关定义如下： 给定对象半径s 内的区域称为该对象的s 邻域。 如果一个对象的s 邻域至少包含最小数目m i n p t s 个对象，则称该对象为核 心对象。 给定一个对象集合d ，如果p 在q 的占一邻域内，而q 是一个核心对象，称 对象p 从对象q 出发是直接密度可达的。 如果存在一个对象链p 。，p ：，p ，p l = g ，p 。= p ，对p ，d ，( 1 i h ) ，p 。 是从p j 关于s 和m i n