（计算机应用技术专业论文）粒度计算在聚类分析中的应用.pdf

摘要 粒度计算即信息的粒化处理，是关于信息处理的一种新的概念和计算范式， 覆盖了粒度方面的方法、理论、技术等几乎所有的领域，是人工智能领域的研究 热点之一。它模仿人类的思考方式，即人们能从极不相同的粒度上观察和分析同 一问题，而且能够很快地从一个粒度世界跳到另一个粒度世界，往返自如，毫无 困难，在知识发现等领域有着非常广泛的应用。 数据挖掘是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据 中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过 程。聚类分析是一个非常活跃的研究领域，是数据挖掘的主要方法之一。它是一 种无监督分类：没有预定义的类。聚类通过观察式学习，将数据对象分组为多个 类或簇，在同一簇中的对象之间具有较高的相似度，而在不同簇中的对象差别较 大。其广泛应用于文本分类、金融分析、数据评估、基因研究及市场调查分析等 领域。 聚类和粒度具有天然的相通性，如何将粒度计算与聚类分析结合起来目前 仍处于起步阶段，尚未形成一个真正系统的完整的理论框架。本文分析了聚类 分析和粒度计算概况，探讨了聚类分析的粒度原理和基于粒度聚类算法的一般 框架，并基于该框架，提出了一种基于网格密度的文本聚类算法，实验表明， 本文所提出的算法是高效的，并且是可行的。最后从商空间理论和信息粒度的 角度，分析了模糊聚类的相关问题，探讨了模糊聚类的典型算法和聚类分析的 分层递阶结构，并实验分析模糊聚类在文本聚类中的应用。 关键词：数据挖掘；粒度计算；文本聚类；模糊聚类；网格密度；商空问理论 a b s t r a c t g r a n u l a re o m p u t i n g ( g r c ) ，n a m e di n f o r m a t i o ng r a n u l a t i o np r o c e s s i n g ，i san e w n o t i o na b o u ti n f o r m a t i o np r o c e s s i n ga n dan o r m a lf o r mi nc o m p u t i n gi n t e l l i g e n c e i t c o v e r sa l m o s tw i t ha l lr e s e a r c ha r e a sr e l a t e dt o g r a n u l a r i t yi n v o l v i n g m e t h o d ，t h e o r i e sa n dt e c h n o l o g i e s i ti s an e wh o ti s s u er i s i n gi n a r t i f i c i a l i n t e l l i g e n c e i ti m i t a t e sh o wp e o p l et h i n k a sw ek n o w ，p e o p l ec a no b s e r v ea n d a n a l y s i sp r o b l e mf r o mq u i e td i f f e r e n tg r a n u l a r i t y a n dc a ne a s i l yt r a n s f e rf r o mo n e g r a n u l a r i t yw o r l dt oa n o t h e r i th a sb e e ne x t r e m e l yw i d e l ya p p l i e di nk d d d o m a i n e t e d a t am i n i n gi sd e f i n e da sap r o c e s st h a te x t r a c t sc o n n o t a t i v e , u n k n o w na n d u s e f u li n f o r m a t i o n a n d k n o w l e d g e f r o m p r a c t i c a l d a t aw h i c hi s s u b s t a n t i a l ，i n c o m p l e t e , n o i s e ，a m b i g u o u sa n ds t o c h a s t i c c l u s t e r i n ga n a l y s i si s a e x t r e m e l ya c t i v er e s e a r c hd o m a i na n di s o n eo ft h em a i nm e t h o d sa b o u td a t a m i n i n g i ti s 觚u n s u p e r v i s e dl e a r n i n gm e t h o d ：n op r e - d e f i n i t i o nc l a s s c l u s t e r i n gi s t h ep r o c e s so fg r o u p i n gas e to fp h y s i c a lo ra b s t r a c to b j e c t si n t oc l a s s e so fs i m i l a r o b j e c t s ac l u s t e ri sac o l l e c t i o no f d a t ao b j e c t st h a ta r es i m i l a rt oo n e a n o t h e rw i t h i n t h es a m ec l u s t e ra n da r ed i s s i m i l a rt ot h eo b j e c t si no t h e rc l u s t e r s i th a saw i d e l y a p p l i c a t i o ni nt e x tc l u s t e r i n g ，f i n a n c i a la n a l y s i s ，d a t ae v a l u a t i o n ，g e n er e s e a r c ha n d m a r k e td i a g n o s i sa n ds oo n w h i l ec l u s t e r i n ga n a l y s i sa n dg r a n u l a rc o m p u t i n ga r ec o n s i s t e n ti nn a t u r e h o w t oa p p l yg r a n u l a rc o m p u t i n gt oc l u s t e r i n ga n a l y s i si ss t i l li n i t i a lp h a s ea n da c o m p l e t e s y s t e m a t i ca n du n e o n t r o v e r s i a ls t r u c t u r eo fg r ci s s t i l lh a sn o tb e e n f o r m e d t h i sp a p e ra n a l y s e sg r ca n dc l u s t e r i n g sp r o f i l e ，d i s c u s sp r i n c i p l eo f g r a n u l a r i t yi nc l u s t e r i n g a n dag e n e r i cf r a m e w o r ko fc l u s t e r i n gb a s e do n g r a n u l a r i t y b a s e do nt h ef r a m e w o r k ，w ep r o p o s eat e x tc l u s t e r i n ga l g o r i t h m g c b g d ( g r a n u l a r i t yc l u s t e r i n gb a s e do ng r i dd e n s i t y ) t h ee x p e r i m e n tr e s u l t ss h o w t h a ti th a sh j i g hp e r f o r m a n c ea n df e a s i b l e f i n a l l y , w ea n a l y s e sf u z z yc l u s t e r i n g d i s c u s ss o m ec l a s s i c a la l g o r i t h m so ff u z z yc l u s t e r i n ga n dh i e r a r c h ys t r u c t u r eb a s e d o nq u o t i e n ts p a c et h e o r ya n di n f o r m a t i o ng r a n u l a r i t y f u r t h e rm o r e ，t h ea p p l i c a t i o n o f f u z z yc l u s t e r i n gi nt e x tc l u s t e r i n gi ss h o w n k e yw o r d s ：d a t am i n i n g ；g r a n u l a rc o m p u t i n g ；t e x tc l u s t e r i n g ；f u z z yc l u s t e r i n g ；g r i d d e n s i t y ；q u o t i e n ts p a c et h e o r y l i l 独创性声明 本人声明所呈交的学位喧文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得悟镪水徭或其他教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示谢意。 学位论文作者签名：粜劈 签字日期：工唧7 年。缃即日 学位论文版权使用授权书 本学位论文作者完全了解窿觚大谣有关保留、使用学位论文的规定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和 借阅。本人授权恪腑以将学位论文的全部或部分内容编入有关数据库进行 检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者鲐物导师戤锈甲逾 签字日期：一 年口甲月四日 签字日期：加p 夕年乒月矽日 学位论文作者毕业去向： 工作单位：电话： 通讯地址：邮编： 第一章绪论 第一章绪论 本章主要介绍了数据挖掘( d a t am i n i n g ，简称d m ) 和知识发现( k n o w l e d g e d i s c o v e r yi nd a t a b a s e ，简称k d d ) 的基本内容、研究方法和研究现状以及发 展趋势。并重点介绍了数据挖掘中聚类“1 问题。 1 1 数据挖掘概述 人类处在信息“爆炸”时代，我们被“淹没”在数据的海洋之中。人们没 有时间看数据，而且面对浩如烟海的数据，人们往往手足无措。人类的关注已 经成为一种宝贵的资源，因此，如何找到有关方法，自动地分析数据、自动地 对数据分类、自动地对数据汇总、自动地发现和描述数据中的趋势、自动地标 记异常是当今最活跃、最令人激动的研究领域之一，数据挖掘技术正是这一研 究领域中的重要研究内容。 i i 1 数据挖掘的基本概念 数据挖掘是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数 据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识 的过程“”。在这个定义中，要求数据源应该是大量的、真实的、含有噪音的； 所发现的信息和知识是潜在的并隐藏在大量数据背后的、是用户感兴趣的、可 理解、可运用的知识。所以，有时候人们也称数据挖掘为知识挖掘，知识提取 等。 与数据挖掘息息相关的概念是基于数据库的知识发现( k d d ：k n o w l e d g e d i s c o v e r yi nd a t a b a s e s ) 。k d d 于1 9 8 9 年在第一届k d d 会议中提出。由于现 在的工作大部分是基于数据库的，所以在实际研究与应用过程中提起更多的是 k d d 。下面介绍两者各自的概念及相互关系“，这有利于理解后续内容。 人们从不同的层面提出了不同的k d d 定义，一种比较全面的定义形式是： k d d ( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ) 是识别存在于数据库中有效的，新颖 的，具有潜在价值的乃至最终可以理解形式的非平凡过程9 1 。它包括从数据库 粒度计算在聚类分析中的应用 中对数据的选取和采样，清理和预处理，转换和必要的简化，从数据中挖掘产 生模式，直到对得到的模式进行解释和评估等过程。这里所说的数据是一系列 事实的集合，可以是一个或一组数据库、数据仓库、电子表格或其他类型的信 息库，在数据上进行数据清理、集成和规约后的数据。这是k d d 处理的最常用 的数据形式。过程是在k d d 中包含的步骤，如数据的预处理、模式搜索、知识 表示及知识评估、过程优化等。模式是对一个数据子集的狭义描述，是对数据 集合的某个子集所采用某种语言进行的表述，不同于模型。非平凡是指它己经 超越了一般封闭形式的数量计算，包括对结构、模式和参数的搜索。提取的知 识表示为概念、规则、规律、模式、约束和可视化等形式。 从概念可以看出，数据挖掘的范围比k d d 广泛，k d d 是面向数据库的，而 数据挖掘面向的数据形式可以有多种多样，它可以是数据库，还可以是图像， 声音等媒体数据。从过程上看，数据挖掘又可以被看作是从数据库中提取有用 信息这一过程的同义词，它是k d d 的一个步骤。 在进行数据挖掘和知识发现过程中，数据、信息、知识是直接接触的三个 概念，三者之间有联系又有区别”1 。在受到其他因素的作用时，它们之间将会 进行转化。如图1 1 所示。 环境或对象智力与关联 、u 一仓u 一。 图1 1 数据、信息、知识的转化 数据挖掘的本质是知识发现，它所有发现的知识都是隐藏在大量数据之中 的关联信息，所有的知识都是有特定前提和约束条件的，是面向特定领域的， 而且，这些知识还要能够易于被用户理解，能用自然语言表达所发现的结果。 2 第一章绪论 i i 2 数据挖掘的一般过程 整个数据挖掘( d a t am i n i n g ) 过程是由若干挖掘步骤组成，而数据挖掘只是 其中的一个步骤。k d d 的一般过程1 如图1 2 所示： 图1 2k d d 一般过程 由以下步骤组成： ( 1 ) 准备阶段：应用与领域相关的先验知识理解设计开发过程，从用户的观 点认识k d d 过程的目标； ( 2 ) 数据选择：根据用户的要求，选取一个数据集或数据抽样的子集，k d d 的工作主要就是在这些数据上进行的； ( 3 ) 数据预处理：对选择产生的数据集进行再加工，检查数据的完整性与一 致性，除去数据中的噪声，对丢失的数据进行填补； ( 4 ) 数据约简：对经过数据预处理的数据，根据知识发现的任务目标，寻求 能表示数据的有用特征，利用属性约简或变换的方法对其操作，以减少数据量； ( 5 ) 确定数据挖掘方法：根据用户的要求，确定k d d 要发现何种类型的知识， 并依据目标的不同，选择数据挖掘方法，如关联，分类，回归，聚类等； ( 6 ) 选择数据挖掘算法：根据确定的任务和数据挖掘方法，选择合适的数据 挖掘算法，包括确定合适的算法和参数，并使算法与整个k d d 的评判标准相一 致； ( 7 ) 数据挖掘：运用( 6 ) 所选定的知识发现算法，从数据集中搜索用户所需 3 粒度计算在聚类分折中的应用 要的感兴趣的模式，如分类规则、关联规则、回归模型、聚类等； ( 8 ) 模式评估：根据某种兴趣度度量，识别表示知识的真正有兴趣的模式； 这些模式应该具有以下特点：易于被理解，在某种程度上对于新的或测试 数据是有效的，是潜在有用的，是新颖的； ( 9 ) 模式表示：将最终符合条件的模式展现给用户，表示的方法根据所选择 的方法的不同而会有所不同，但可视化技术是一种行之有效的、直观的模式表 示方法。 1 1 3 数据挖掘任务 根据数据分析目标的不同，数据挖掘任务可以分为如下几个类型“”： 1 、探索性数据分析( e x p l o r a t o r yd a t aa n a l y s i s ，e d a ) ：正象名字所暗示 的，这种方法的宗旨就是对数据进行探索，在探索时我们对要寻找什么对没有明 确的想法。通常，e d a 技术是交互式的( i n t e r a c t i v e ) 和可视化的( v i s u a l ) ，对于 维数比较低的数据集来说，有很多种有效的图形化显示方式。但随着维数( 变量 的个数p ) 的增多，可视化变得越来越困难。当p 大于3 或4 时，可以产生数据低维 投影的投影技术( 例如主要分量分析) 是非常有价值的。数量很大的数据集可能不 容易被有效的可视化，然后，可以使用缩放和明细数据的思想来显示或总结“较 低分辨率”的数据样本( 以可能丢失重要细节为代价) 。 2 、描述建模( d e s c r i p t i v em o d e l i n g ) ：描述模型的目标是描述数据( 或产生 数据的过程) 的所有特征。这样的例子包括为数据的总体概率分布建模( 密度估计 ( d e n s i t ye s t i m a t i o n ) ) ： 把p 维空间划分成组( 聚类分析和区隔 ( c l u s t e r a n a l y s i sa n ds e g m e n t a t i o n ) ) ；以及描述变量问的关系( 依赖建模 ( d e p e n d e n c y mo d e l i n g ) ) 。例如在区隔分析中，目标是把相似的记录分成一组， 比如商业数据库的市场区隔。这样做的目的是把记录分成均匀同质( h o m o g e n e o u s ) 小组，以便使相似的人( 如果记录是指人的) 被分到同一组。这可以使广告商或销 售者可以把他们的促销策略指向最可能相应的人群，以提高效率。这里分成的组 数是由研究者决定的，没有对错之分。这与聚类分析不同，在聚类分析中目标是 发现数据( 例如科研数据库) 中的“自然”群体。描述建模己经被应用到很多领域。 3 、预测建模( p r e d i c t i v e m o d e l i n g ) ：预测建模的目标是建立一个模型，这 4 第一章绪论 个模型允许我们根据己知的变量值来预测其他某个变量值。在分类中，被预测的 变量是范畴型的，而在回归中被预测的变量是数值型( q u a n t i t a t i v e ) 的。这里， 预测这个词是取它的一般含义，根本不带有任何时间延续性的暗示。所以，我们 可以预测将来某一天股票的市值，或预测哪一匹马会赢得比赛：我们也可以预测 患者的病情，或焊接的牢固程度。在统计和机器学习中人们己经开发出了大量的 方法来解决预测建模问题，而且这一领域的工作已经取得了重大理论进展，并加 深了对深层推理问题的理解。预测和描述间的关键区别是预测的目标是唯一的变 量( 例如市值、疾病分类) ，而描述问题的模型中并不以任何单一的变量为中心。 4 、寻找模式和规则：上面列出的三类任务都致力于建立模型。还有一些数 据挖掘应用是致力于模式探测的。一个例子是欺诈探测，做法是寻找明显不同于 其他点的数据点，并查出这些数据点所述的不同交易类型，然后通过探测这些包 含特殊交易的空间区域来查出欺诈行为。另一个应用是在天文方面探测异常的星 体或星系，目的是发现以前未知的对象。还有一个应用就是在交易数据库中发现 频繁出现的商品组合( 比如日常用品经常被一起购买) 。这个问题已经吸引了很多 数据挖掘者的注意力，而且己经采用基于关联规则( a s s o c i a t i o nr u l e ) 的算法技 术来解决这样的问题。 5 、根据内容检索：这种情况下，用户有一种感兴趣的模式并且希望在数据 集中找到相似的模式。这种任务对于文本和图像数据集合应用最普遍。对于文本， 模式可能是一系列的关键字，用户希望在庞大的可能相关的文档集合中( 例如网 页) 寻找相关的文档。对于图像，用户可能有一幅样本图像、一幅图像的草图、 或一幅图像的描述，然后希望从庞大的图像集合中发现类似的图像。无论对于两 种情况的哪一种，相似性的定义都非常关键，但搜索策略的细节也很重要。检索 系统的应用例子包括： 在网络中，检索方法被用来定位文档，就象g o o g l e ( w 啊g o o g l e c o m ) 那 样。g o o g l e 系统使用了被称为”p a g e r a n k ”，的数学方法来基于链接模式估计各 网页的相对重要性。 i b m 的开发人员开发了一个称为q b i c ( 根据图像内容查询( q u e r yb yi m a g e c o n t e n t ) ) 的系统，这个系统允许用户使用交互式的方法搜索庞大的图像数据库。 支持以像颜色、纹理和相对位置信息这样的内容描述提出查询。 粒度计算在聚类分析中的应用 1 1 4 数据挖掘功能 数据挖掘的功能与挖掘的e 1 标数据类型是相关的，某些功能只能用在某个 特定的数据类型上，而有些功能则可以应用在多个不同类型的数据库上。对于 数据挖掘任务的确定，必须综合考虑数据挖掘功能，要挖掘的数据类型和用户 的兴趣。 数据挖掘功能用于指定数据挖掘任务中要找的模式类型，其任务一般可以 分为两类：描述和预测。描述性挖掘任务刻画数据库中数据的一般特性。预测 性挖掘任务在当前数据上进行推断，以进行预测”。数据挖掘的功能主要包括 以下几个方面：概念描述：特征化和区分；关联分析；分类；聚类；预测分析； 偏差检测分析；时序演变分析等等。 1 1 4 1 概念描述 概念描述( c o n c e p td e s c r i p t i o n ) 就是通过对与某类对象关联数据的汇总， 分析和比较，对此类对象的内涵进行描述，并概括这类对象的有关特征，例如： 关系数据库中的一个关系( 即一个表) 代表了一个对象集，其中的每个元组可以 看作上一个对象，每个对象有唯一的标示和多个属性值。在一个或者一组属性 上取值相同的对象构成一个对象类。 概念描述分为特征性描述和区别性描述。前者描述某类对象的共同特征， 后者描述不同的类对象之间的区别。 1 1 4 2 关联分析 关联分析( a s s o c i a t i o n ) 即从大量的数据中发现项集之间有趣的关联，相关 关系或者因果结构以及项集的频繁模式。 在数据挖掘的研究领域，关联规则的挖掘有着广泛的应用背景，对于关规 则挖掘的研究开展的比较积极和深入。关联规则最初起源于对超级市场的“购 物篮问题的研究”，是描述数据库中数据项之间某种潜在关联关系的规则( 同时 发生或者从一个对象推出另一个) 。通常关联规则具有如下形式：j j 】，即 6 第一章绪论 “4 4 a a 以- - 4 目 呸k 最“；其中，4 ，i 1 2 朋) 和口，_ ， l 2 雄) 为 属性。关联规则x 寸y 表示事物数据库中满足条件x 的事物在某种程度上也满 足条件y 。 该项应用最早挖掘出的关联规则就是“啤酒和尿布问题”： 年轻父亲+ 啤酒寸尿布( s u p p o r t = 3 0 ，c o n f i d e n c e = 7 0 ) 上述规则表示：该商场中是年轻父亲，且同时购买啤酒和尿布的占3 0 ， 年轻父亲买啤酒的同时有7 0 的可能性买尿布。 关联规则就是辨别这些交易项目之间是否存在某种关联关系。这种关联规 则提供的信息可以用作商品销售目录设计、商场布置、生产安排、针对性的市 场营销等。 1 1 4 。3 分类 分类( c l a s s i f i c a t i o n ) 规则挖掘它的任务是在己知训练数据的特征和分类 结果的前提下，为每一个分类找到一个合理的描述或模型。然后再用这些分类 的描述或模型对类别未知的新的数据进行分类。分类是数据挖掘中一个十分重 要的课题，许多数据挖掘问题本质上都可以等价或转化为分类问题。例如语音 识别( s p e e c hi d e n t i f i c a t i o n ) 、图像识别( i m a g ei d e n t i f i c a t i o n ) 等问题。这 些问题实际上是为某一语音或图像数据找到合理的特征描述。如果把特征集合 当成类别集合，那上述识别问题就是一个分类问题本文的工作重点是围绕着分 类这一数据挖掘的功能展开。 分类是一个两步过程。第一步，建立一个模型，描述预定的数据类集或者 概念集。通过分析属性描述的数据库元组来构造模型。假定每一个元组属于一 个预定义的类，由一个叫做类标号属性的属性确定。为了建立模型，用来分析 的那些数据，称之为训练数据集。该步骤我们也称作有指导的学习，即在告知 每个训练样本属于哪个类之后来确定模型。第二步，使用模型进行分类。对于 分类，我们会在以下章节中作详细介绍。 粒度计算在聚类分析中的应用 1 1 4 4 聚类 聚类( c l u s t e r i n g ) 与分类不同，聚类分析是在预先不知道划定类的情况下， 根据信息相似度原则进行信息聚集的一种方法，是一种基于无指导的学习“1 。 聚类的目的是根据最大化类内的相似性，最小化类间的相似性这一原则合理的 划分数据集合，并用显式或者隐式的方法描述不同的类别。有关聚类将在1 2 中有更加详细介绍。 1 1 4 5 预测分析 预测( p r e d i c t i o n ) 是构造和使用模型评估无标号样本类，或者评估给定样 本可能具有的属性值或值区间。与分类不同，分类是预测的离散值，而预测分 析是用于预测连续或有序值。 1 1 4 6 孤立点分析 在给定的数据库中可能包含一些数据对象，它们与数据的一般行为或模型不 一致。这些数据对象是离群数据( o u t l i e r ) 。大部分数据挖掘方法将离群数据视 为噪声或异常而丢弃。然而，在一些应用中，如入侵检测、欺骗检测，罕见的事 件可能比正常出现的那些更有用。离群数据分析称为离群数据挖掘( o u t l i e r m i n i n g ) 。离群数据的发现主要有三种方法：统计学的方法，它是根据己知的数 据分布模型，使用假设检验米确认离群数据的存在，这种检验需要知道数据的分 布，分布的参数等；基于距离的方法，通过数据间距离的计算，求得离群数据； 基于偏离的方法，它通过数据中某项记录的去除对整个数据的影响及变化来确定 离群数据的存在。 1 1 4 7 演变分析 时序演变分析( t e m p o r a le v o l u t i o na n a l y s i s ) 是描述行为随时间变化的对 象的规律或趋势，并对其建模。序列分析和时间序列说明数据中的序列信息和与 时间相关的序列分析。其中包括时间相关数据的特征化、区分、关联、分类或聚 第一章绪论 类，但这类分析的不同特点包括时间数据分析、序列或周期模式匹配和基于相似 性的数据分析。 1 1 5 数据挖掘的发展趋势和方向 数据挖掘的发展趋势主要有以下几个方面”3 ： 1 数据挖掘将成为企业信息系统基础设施的一种标准能力。随着数据挖掘的 广泛应用和深入开展，企业已经把数据挖掘作为提高自己竞争力的有效手 段。 2 数据挖掘过程将走向标准化。一项技术只有标准化了才能获得广泛应用， 数据挖掘也是一样。标准化数据挖掘过程将使得数据挖掘成为类似关系型 数据库一样的工业标准技术，有助于大规模的分工开发，有利于企业和个 人的使用。 3 数据挖掘的全面可视化。可视化可以帮助人们从大量的数据中发现知识， 帮助人们对所挖掘的知识的理解。数据挖掘的可视化包括数据可视化，数 据挖掘结果可视化，数据挖掘过程可视化和交互式的可视化等等。经过全 面的可视化，数据挖掘工具更加易于使用。 4 处理大量数据的能力。数据挖掘面对的是大量的海量数据，有些挖掘算法 在数据量小的时候表现不错，但是当数据量增加时，性能却下降的很快。 需要我们探索新的算法，使得数据挖掘系统在海量数据面前可以保持合理 的性能，即具有可伸缩性。 5 将致力于多媒体数据，文本数据，地理空间数据等复杂数据类型的处理技 术。 6 与未来的网格技术相结合，研究基于网格的数据挖掘技术，其研究需要将 随着网格技术的发展而日益紧迫。 1 2 聚类 聚类分析是数据挖掘技术中重要的组成部分，它能够在潜在的数据中发现 令人感兴趣的数据分布模式。从技术角度讲，它的主要目的是将数据空间中的 数据点划分到若干个类中，其中将距离相近的数据点划分到相同的类中，而将 9 粒度计算在聚类分析中的应用 距离较远的数据点划分到不同的类中。它是在无监督的情况下根据一定的相似 性或距离计算函数自动的将数据集分成若干类。 1 2 1 问题定义 聚类( c l u s t e r i n g ) 是一种常见的数据分析工具，简单地说，就是将物理 或抽象对象的集合分组成为由类似的对象组成的多个类或簇( c l u s t e r ) 的过程。 由聚类所生成的类是对象的集合，这些对象与同一个类中的对象彼此相似，与 其它类中的对象相异。在许多应用中，可以将一个类中的数据对象作为一个整 体来对待。聚类的严格数学描述如下“： 设被研究的样本集为e ，类c 定义为e 的一个非空子集，即c c e 且 c a 囝聚类就是满足下列两个条件的类q ，c 2 ，g 的集合 c l vc 2 v v g = e e c ，= a ( 对任意i c j ) 由第一个条件可知，样本集e 中的每个样本必定属于某一个类；由第二个 条件可知，样本集e 中的每个样本最多只属于一个类。 1 2 2 数据挖掘对聚类的典型要求 聚类是一个富有挑战性的研究领域，它的潜在应用提出了各自特殊的要求。 数据挖掘对聚类的典型要求如下“”： 1 可伸缩性：许多聚类算法在小于2 0 0 个数据对象的小数据集合上工作得很 好；但是，一个大规模数据库可能包含几百万个对象，在这样的大数据集合样本 上进行聚类可能会导致有偏差的结果。我们需要具有高度可伸缩性的聚类算法。 2 处理不同类型属性的能力：许多算法被设计用来聚类数值类型的数据。 但是，应用可能要求聚类其他类型的数据，如二元数据( b i n a r y ) ，分类标称类 型( c a t e g o r i c a l n o m i n a l ) ，序数型( o r d i n a l ) 数据，或者这些数据类型的混合。 3 发现任意形状的聚类：许多聚类算法基于欧几里得聚类或者曼哈顿聚类 度量来决定聚类。基于这样的距离度量的算法趋向于发现具有相似尺度和密度的 球状簇。但是，一个簇可能是任意形状的。提出能发现任意形状簇的算法是很重 1 0 第一章绪论 要的。 4 用于决定输入参数的领域知识最小化：许多聚类算法在聚类分析中要求 用户输入一定的参数，如希望产生的簇的数目。聚类结果对输入参数十分敏感。 参数通常很难确定，特别是对于包含高维对象的数据集来说，更是如此。要求用 户输入参数不仅加重了用户的负担，也使得聚类的质量难以控制。 5 处理噪声数据的能力：绝大多数现实世界中的数据库中都包含了孤立点， 空缺，未知数据或者错误的数据。一些聚类算法对于这样的数据敏感，可能导致 低质量的聚类结果。 6 对于输入记录的顺序不敏感：一些聚类算法对于输入数据的顺序是敏感 的。例如，同一个数据集合，当以不同的顺序提交给同一个算法时，可能生成差 别很大的聚类结果。开发对于数据输入顺序不敏感的算法具有重要的意义。 7 高维性( h i g hd i m e n s i o n a l i t y ) ：一个数据库或者数据仓库可能包含若干 维或者属性。许多聚类算法擅长处理低维数据，可能只涉及两到三维。人类最多 在三维的情况下能够很好的判断聚类的质量。在高维空间中聚类数据对象是非常 具有挑战性的，特别是考虑到这样的数据可能非常稀疏，而且高度偏斜。 8 基于约束的聚类：现实世界的应用可能需要在各种约束条件下进行聚类。 假设你的工作是在一个城市中为给定数目的自动提款机( a t m ) 选择安装位置。 为了作出决定，你可以对住宅区进行聚类，同时考虑如城市的河流和公路网，每 个地区的客户要求等情况。要找到既满足特定的约束，又具有良好聚类特性的数 据分组是一项具有挑战性的任务。 9 可解释性和可用性：用户希望聚类结果是可解释的，可理解的和可用的。 也就是说，聚类可能需要和特定的语义解释和应用相联系。应用目标如何影响聚 类方法的选择也是一个重要的研究课题。 1 2 3 聚类分析中的数据类型及对象问的相似度 与普通的聚类分析不同，在数据挖掘领域，聚类分析中的数据呈现多样性。 经常出现的数据类型有区间标度变量、二元变量、标称型、序数型和比例标度 型变量等。对于不同的类型，对象间的相异度有着不同的度量方法”1 。 1 区间标度变量 区间标度变量是一种线性标注的连续变量，如重量和高度。为避免度量单 位选择对聚类结果的影响，数据应当先标准化，进行如下变换： 粒度计算在聚类分析中的应用 ( 1 ) 计算平均的绝对偏差0 ： 墨= 丢( i 五，一所，屯f - - m f 卜+ i 一吩i ) 其中而，是f 的n 个度量值，吩是它们的平均值，即 掰，= 昙( 而，+ 而，+ + ) ( 2 ) 计算标准化的度量值z ： 乃2 孚 数据标准化处理后，对象间的相异度通常是基于对象间的距离来计算的。 最常用的距离度量方法是欧几里德距离，它的定义如下： d ( f ，j ) = 其中，i 2 【，薯：，j 和j 2 i t ，x j 2 9o o l 9 勃j 是两个n 维的数据对象。 2 二元变量 一个二元变量只有两个状态：0 或1 ，0 表示该变量为空，1 表示该变量存 在。二元变量分为对称二元变量和非对称二元变量。对称二元变量的两个状态 是等权重的。如性别变量，1 表示男人，0 表示女人。评价两个对象i 和j 之间 相异度的最著名的系数是简单匹配系数，其定义如下： 啪) 2 i 其中q 是对象i 和j 值都为1 的变量数目，r 是对象i 值为1 而对象j 值 为0 的变量数目，s 是对象i 值为0 而对象j 值为1 的变量数目，t 是对象i 和 j 值都为0 的变量数目。非对称二元变量的两个状态是不对称的。如h i v 检测 结果，1 表示阳性，0 表示阴性。评价两个对象i 和j 之间相异度的最著名的系 数是j a c c a r d 系数，其定义如下： d ( i ，_ ，1 ：旦 鼋十r + s 3 标称变量 标称变量是二元变量的推广，它可以具有多个状态值。如m a p c o l o r 是一 个标称变量，它可能有五个状态：红色、黄色、绿色、粉红色和蓝色。两个对 象i 和j 之间的相异度可以用简单匹配方法，其定义如下： m ，班了p - - m 其中m 是i 和j 取值相同的变量数目，p 是全部变量的数目。 4 序数型变量 第一章绪论 离散的序数型变量类似标称变量，但其状态的排序是有意义的。如比赛中 的排名：金牌、银牌和铜牌。其相异度计算包括如下步骤： ( 1 ) 将变量值用1 m 替代，其中m 为有序状态的个数。 ( 2 ) 将每个变量的值域映射到 0 ，1 上，使每个变量有相同的权重。 ( 3 ) 采用区间标度变量的相异度计算方法。 5 比例标度型变量 比例标度型变量在非线性的标度所取的度量值。如指数标度，典型的例子 包括细菌数目的增长、放射性元素的衰变。根据实际情况将比例标度型变量变 换成区间标度型变量，再计算相异度。在许多真实的数据库中，对象是被混合 类型的变量描述的。假设数据集包含p 个不同类型的变量，对象i 和j 之间的 相异度d ( i ，j ) 定义为： p d ( i ，) = 坐f 一 f = l 其中如果矗或b 缺失，或者靠2 勤2 0 ，则指示项啄。u ，否则q 。1 。 j ，) “f 根据其具体类型计算。上述几种数据类型存在于以结构化数据为主的关系 数据库，事务数据库，和数据仓库中。随着数据处理工具、先进数据库技术以 及万维网技术的迅猛发展，大量形式各异的复杂类型的数据不断涌现。如空间 数据、多媒体数据、时间序列数据、文本数据和w e b 数据。这些数据通常需要 采用各种不同的方法将其转化为上述五种数据类型后，再进行聚类分析。 1 2 4 主要聚类方法 目前存在大量的聚类算法“”，算法的选择取决于数据的类型、聚类的目的 和应用。以下将讨论在数据挖掘领域中得到广泛应用的一些聚类算法及其改进 方法，大体上可以分为五大类。 1 2 4 1 基于划分的方法 给定一个包含n 个数据对象的数据库，以及要生成的类的数目k ，一个划 分类的算法将数据对象组织为k 个划分( k n ) ，其中每个划分代表一个类。也 就是说，他讲数据划分为k 个组，同时满足如下要求： ( 1 ) 每个组至少包含一个对象； 粒度计算在聚类分析中的应用 ( 2 ) 每个对象必须属于且只属于一个组。 给定要构建的划分的数目k ，划分方法首先创建一个初始划分。然后采用 一种迭代的重定位技术，尝试通过对象在划分间移动来改进划分。通常一个划 分准则，例如距离，以便在同一个类中的对象是“相似的”，而不同类中的对象 是“相异的”。一个好的划分的一般标准是：在同一个类中的对象之间尽可能“接 近”或相关，而不同类中的对象之间尽可能“远离”或不同。为了达到全局最 优，基于划分的聚类会要求穷举所有可能的划分。最著名与最常用的划分方法 是k - m e a n s “”和k 一中心点。 k - m e a n s 算法的目标是根据输入参数k ，将数据集划分成k 个簇。算法采用 迭代更新的方法：在每一轮中，依据k 个参照点将其周围的点分别组成k 个簇， 而每个簇的质心( 即簇中所有点的平均值，也就是几何中心) 将被作为下一轮迭 代的参照点。迭代使得选取的参照点越来越接近真实的簇质心，所以聚类效果 越来越好。k - m e a n s 算法的处理流程如下。 首先，随机的选择k 个对象，每个对象初始的代表了一个类的平均值或中 心。对剩余的每个对象，根据其与各个类中心的距离，通常，采用平方误差准 则，其定义如下： k e = ( p 一镌) 2 i = 1 p e c , 这里的e 是数据库中所有对象的平方误差的总和，p 是空间中的一点，表 示给定的数据对象，是类c 的平均值( p 和都是多维的) 。这个准则试图使 生成的结果类尽可能的紧凑和独立。k - m e a n s 过程的概述如下： ( 1 ) 任意选择k 个对象作为初始的类中心； ( 2 ) r e p e a t ( 3 ) 根据类中对象的平均值，将每个对象( 重新) 赋给最类似的值； ( 4 ) 更新类的平均值，即计算每个类中对象的平均值； ( 5 ) u n t i l 不再发生变化。 这个算法尝试找出使平方误差函数至最小的k 个划分。当结果类是密集的， 而处于类之间区别明显时，它的效果较好。对处理大数据集，该算法是相对可 伸缩的和高效率的，因为它的复杂度是o ( t k n ) ，其中n 是数据的总数，k 是聚 1 4 第一章绪论 类的个数，t 是算法循环的次数，算法的效率很高。其缺点是：需要用户输入 最终结果的聚类个数k ，而判断一个未知数据集的划分个数通常是很困难的，k 个初始点的选择对最终的聚类结果影响很大。k - m e a n s 方法不适合发现非凸形 状的类，或者大小差别很大的类，而且，它对于“噪声”和孤立点数是敏感的， 少量的该类数据能够对平均值产生极大的影响。 k - m e a n s 算法有很多变种。他们可能在初始k 个平均值的选择、相异度的 计算和计算聚类平均值的策略上有所不同。k - m e a n s 算法也可和其他聚类算法 相结合，达到取得更好聚类效果的目的。例如，可先采用层次的凝聚算法决定 结果类的数目，并找到一个初始的聚类，然后用迭代重定位来改进聚类结果。 1 2 4 2 基于层次的方法 一个层次的聚类方法o ”将数据对象组成一棵聚类树。根据层次分解是自底 向上还是自顶向下形成，层次的聚类方法可以进一步分为凝聚的 ( a 9 9 1 0 m e r a t i v e ) 和分裂的( d i v i s i v e ) 层次聚类。凝聚的层次聚类是自底向上 的策略。首先将每个对象作为一个类，然后合并这些原子类为越来越大的类， 直到所有的对象都在一个类中，或者某个终结条件被满足。分裂的层次聚类是 种自顶向下的策略与凝聚的层次聚类相反，它首先将所有对象置于一个类中， 然后逐渐细分为越来越小的类，直到每个对象自成一类，或者达到了某个终结 条件，例如达到了某个希望的类数目，或者两个最近的类之间的距离超过了某 个阈值。 层次聚类方法尽管简单，但经常会遇到合并或分裂的点选择的困难。这样 的决定是非常关键的，因为一旦一组对象被合并或者分列，下一步的处理将在 新生成的类上进行。已做的处理不能被撤销，聚类之间也不能交换对象。如果 在某一步没有很好的选择合并或分裂的决定，可能会导致低质量的聚类结果。 而且，这种聚类方法不具有很好的可伸缩性，因为合并或分裂的决定需要检查 和估算大量的对象或类。 b i r c h ( b a l a n c ei 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 ) 聚类算法是一个综合的层次聚类方法。它首先将数据集以一种紧凑的压缩格式 存放，然后直接在压缩的数据集( 而不是原始的数据集) 上进行聚类，所以其i o 粒度计算在聚类分析中的应用 成本与