（计算机应用技术专业论文）高维稀疏聚类知识发现及其在连锁超市中的应用.pdf

二二期43 上海大学 本论文经答辩委员会全体委员审查， 确认符合上海大学硕士学位论文质量要求。 答辩委员会签名： 主任： 搬 ( 工作靴职称) 者祷芝 颈：锈舻嘲，呼彖良识舻谢，岬眠劾艮 导厩产口叭 答辩日期：彻乒；乒 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发表 或撰写过的研究成果。参与同一工作的其他同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 签名：日期塑兰：! ：! 生 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定。即：学校有权保留 论文及送交论文复印件，允许论文被查阅和借阅：学校可以公布论文的全部或部 分内容。 ( 保密的论文在解密后应遵守此规定) 签名：塑生垒导师签名：i 竖! 墼日期： z 3 挚 摘要 数据挖掘是从大量数据中提取人们感兴趣的信息和知识。这些知识往往是隐 含的、有用的、尚未发现的信息和知识。数据挖掘已经引起了人们的广泛关注， 目前成为国内外数据库和信息决策领域的最前沿研究方向。聚类是数据挖掘领域 最为常用的技术之一，用于发现在数据库中未知的对象类。聚类是现实世界中普 遍存在的现象，其应用非常广泛。 本文主要围绕高维聚类对数据挖掘的理论和方法进行了以下几方面的工作： 首先归纳了数据挖掘技术的发展状况，包括数据挖掘的定义、数据挖掘的流 程、功能等基本概念和技术，而且还探讨了数据仓库和数据挖掘的关系。数据仓 库作为一种新型的数据存储方式，为数据挖掘提供了新的支持平台，其内在的对 决策的支持能力，为数据挖掘开辟了新的空间。 其次对聚类问题进行深入地研究。迄今为止，人们提出了许多用于大规模数 据库的聚类算法。其中大多数算法可以高效地处理低维数据，但是随着数据的维 数增加，它们的执行效率将会急剧下降。而少数可以处理高维数据的算法却存在 效率低下或聚类结果质量差等问题。通过对高维聚类问题的深入研究及对已有高 维聚类算法的分析比较，本文提出了一种可以高效地处理高维稀疏聚类问题的基 于特征标识的聚类方法( s c m ) 。 最后论述了s c m 聚类方法在连锁超市中的应用，其中构建了同时支持营销 分析及多维数据分析的数据模型，基于该数据模型的数据存储，直接为发现聚类 知识提供了高质量的数据源。 关键字：数据挖掘、知识发现、聚类、高维数据 a b s t r a c t d a t am i n i n gi st od i s c o v e r yt h ei n t e r e s t i n gi n f o r m a t i o na n dk n o w l e d g e ，w h i c hi s u s e f u l ，c o n n o t a t i v e ，a n du n p r e d i c t a b l e ，f r o mn u r n e r o u sd a t a p r e s e n t l y ，d a t am i n i n g h a sa t t r a c t e dl o t so fa t t e n t i o n sa n db e c o m e so n eo ft h e i n t e r n a t i o n a la d v a n c e d d i r e c t i o n si nt h ef i e l do fd a t a b a s ea n di n f o r m a t i o nd e c i s i o n a saf r e q u e n t l yu s e d t e c h n o l o g yi nd a t am i n i n g ，c l u s t e r i n gi s u s e dt of i n dt h eu n k n o w no b j e c tc l a s si n d a t a b a s e c l u s t e r i n gi sau b i q u i t o u sp h e n o m e n o n i nr e a l i s t i cw o r l d ，a n di sa p p l i e dt o v a r i o u sa r e a s t h i sd i s s e r t a t i o ni s m a i n l yo nt h et h e o r ya n dm e t h o do fd a t am i n i n gb a s e d c l u s t e r i n gl a r g e d a t a s e tc h a r a c t e r i s t i co fh i g hd i m e n s i o n a l lt h ew o r kc a nb e c o n c l u d e da sf o l l o w s ： f i r s t l y ，t oi n d u c et h er e s e a r c hw o r k a n d d e v e l o p m e n t o fd a t am i n i n g ，i n c l u d e d e l e m e n t a r yc o n c e p t sa n dt e c h n i q u e sl i k et h ed a t am i n i n gd e f i n i t i o n ，f u n c t i o n sa n d m i n i n gp r o c e s s e s t h er e l a t i o n s h i po f d a t am i n i n ga n dd a t aw a r e h o u s ei ss u r v e y e d a l s o a st h en o v e lm a n n e ro fd a t as t o r a g e ，d a t aw a r e h o u s ep r o v i d e san e ws u p p o r t p l a t f o r m f o rd a t am i m n g i na d d i t i o n ，d a t aw a r e h o u s eb l a z e st h en e w p l a c ef o rd a t a m i n i n g ，b e c a u s e i ts u p p o r t sd e c i s i o n s e c o n d l y ，t om a i n l yd i s c u s sc l u s t e r i n g s of a r ，m a n yc l u s t e r i n ga l g o r i t h m sh a v e b e e nd e v e l o p e d a l t h o u g hl o t so ft h e mc a ne f f i c i e n t l yp e r f o r mi nl o wd i m e n s i o n d a t a s e t ，t h e i rp e r f o r m a n c ei sr a p i d l yd e g r a d e df o ri n c r e a s i n gd i m e n s i o n a l i t y af e w a l g o r i t h m sc a nd e a lw i t hl a r g ea n dh i g hd i m e n s i o nd a t a b a s e ，b u tt h e yi n e f f i c i e n t l y e x e c u t eo rh a v eg r e a td i f f i c u l t yi ng e e i n g t o p - q u a l i t yr e s u l t s t h i sd i s s e r t a t i o ns t u d i e s m a i nc h a r a c t e r i s t i c so fc l u s t e r i n g h i g h d i m e n s i o nd a t a b a s e ，t h e n a n a l y z e s a n d c o m p a r e s t h ea d v a n t a g ea n dd e f i c i e n c yo ft h e p r o p o s e dc l u s t e r i n ga l g o r i t h m si nh i 曲 d i m e n s i o nd a t a a n dt h e n ，as i g n a t u r e b a s e dc l u s t e r i n gm e t h o d ( s c m ) i s p r o p o s e d ， w h i c hi se f f i c i e n ta n de f f e c t i v ei nc l u s t e r i n gl a r g ed a t a b a s ew i t hh i g hd i m e n s i o na n d l a r g es p a r s e n e s s f i n a l l y , s c mm e t h o dw i l lb ea p p l i e dt o t h es y s t e mo fs u p e r m a r k e t t h ed a t a m o d ei sc o n s t r u c t e d ，w h i c hs u p p o r tn o to n l ys a l ea n a l y s i sb u ta l s om u l t i d i m e n s i o n a l d a t aa n a l y s i s d a t as t o r a g eo nt h eb a s i so f t h i sd a t am o d e d i r e c t l yp r o v i d e st o p - q u a l i t y d a t as o u r c ef o r c l u s t e r i n gk n o w l e d g ed i s c o v e r y k e y w o r d s ：d a t am i n i n g ；k n o w l e d g ed i s c o v e r y ；c l u s t e r i n g ；h i g hd i m e n s i o n d a t a 1 1 1 引言 第一章绪论 进入九十年代，伴随着因特n ( i n t e m e t ) 的出现和发展，以及随之而来的企业 内部网f i n t r a n e t ) 和企业外部网( e x t r a n e t ) 以及虚拟私有网( v p n ：v i r t u a p r i v a t e n e t w o r k ) 的产生和应用，将整个世界联成一个小小的地球村，人们可以跨越时空、 地域在网上交换数据信息和协同工作。这样，展现在人们面前的己不是局限于本 部门，本单位和本行业的庞大数据库，而是浩瀚无垠的信息海洋，数据洪水正向 人们滚滚涌来。当数据量极度增长时，如果没有有效的计算机及信息技术来提取 有用信息和知识，人们也会感到面对信息海洋像大海捞针一样束手无策。据估计， 一个大型企业数据库中数据，只有百分之七得到很好应用。【l j 现在，数据可以存放不同类型的数据库中。最近出现的一种数据库结构是数 据仓库，它是种多个异种数据源在单个站点以统一的模式组织的存储，以支持 管理决策。数据仓库技术包括数据清理、数据集成和联机分析处理( 0 l a p ) 。联 机分析处理是一种分析技术，具有汇总、合并和聚集功能，以及从不同的角度观 察信息的能力。尽管联机分析处理工具支持多维分析和决策，但对于深层次的分 析，如数据分类、聚类和数据随时间变化的特征，仍然需要借助其它的分析工具。 而与此同时，拥有这些数据库的决策者们，在做决策时不是基于数据库中蕴 含的大量信息，而是基于决策者的直觉。让我们在考察一下当前解决这个问题的 方法之一：专家系统技术。这种技术的一个很大的特点就是：用于辅助决策的系 统信息依赖于用户或某一领域的专家手工输入的知识，这个过程一方面是十分费 时的；另一方面它也是很难避免这样或勇b 样的人为的偏见和错误的。面传统的查 询、报表工具无法满足发掘这些信息的需求，人们需要一种新的数据分析技术来 处理大量数据并从中抽取有价值的潜在信息，于是，从数据库中发现知识( k d d ： k n o w l e d g ed i s c o v e ri nd a t a b a s e ) 及其核心技术一数据挖掘( d m ：d a t am i n i n g ) 便应运而生了。 1 2 数据挖掘综述 数据库知识发现是从大量原始数据中挖掘出隐含的、有用的、尚未发现的信 息和知识，它不仅被许多研究人员看作是数据库系统和机器学习等方面一个重要 的研究课题，而且被许多工商界人士看作是一个能带来巨大回报的重要领域。【】 数据库知识发现是一个交互性、循环反复的整体过程，包括数据准备、数据 挖掘和发现的结果解释、评估等诸多环节。其中数据挖掘是专门负责发现知识的 核心环节，也是目前研究人员主要努力的方向。由于在产业界、媒体和数据库研 究界，“数据挖掘”比术语“数据库知识发现”更流行，因此，在本论文中选用 术语数据挖掘。 1 2 1 数据挖掘 简单的讲，数据挖掘( d a t a m i n i n g ) 就是从大量的、不完全的、有噪音的、模 糊的、随机的实际应用的数据集中，整理出或者说挖掘出有效的、新颖的、潜在 有用的，以及最终可理解模式的高级处理的过程。 3 - 7 1 一个典型的数据挖掘系统如图1 1 。其中数据库、数据仓库或者是其他一些 信息存储媒介为数据挖掘的工作对象：服务器主要是响应数据挖掘引擎的请求， 提取相应的数据：领域知识库主要用来指导挖掘的过程，以及用来评价挖掘出来 的候选模式：数据挖掘引擎是整个系统的核心部分，可以由以下模块组成：分类 模块、关联规则模块、聚类分析模块、时序模块和异常分析模块等；模式评价模 块主要是根据一定的度量标准来与数据挖掘模块交互，使得数据挖掘向着我们感 兴趣的方向进行：图形用户界面主要是为方便用户与数据挖掘系统的交互，由用 户提出挖掘任务、指定重要的挖掘参数以及由当前返回的结果指导进行更进一步 的挖掘工作。 图1 1 典型的数据挖掘系统结构 1 2 2 数据挖掘的流程 数据挖掘的流程可以理解为三个阶段：数据准备、数据挖掘过程、挖掘结果 的解释和评估。 数据准备 在现实世界中的数据一般是脏的、不完整的和不一致的。数据准备技术可以 改进数据的质量，从而有助于提高其后的挖掘过程的精度和性能。由于高质量的 决策必然依赖于高质量的数据，因此数据准各是知识发现过程的重要步骤。检测 数据异常、尽早地调整数据，并规约待分析的数据，将在决策过程得到高回报。 数据准备阶段的工作包括四个方面的内容：数据清理、数据集成、数据变换、数 据规约。 数据清理( d a t ac l e a t i n g ) ：主要试图填充空缺的值，识别孤立点、消除噪音， 并纠正数据中的不一致。数据清理可以提高数据的质量，从而得到更正确的数据 挖掘结果。 数据集成( d a t a i n t e g r a t i o n ) ：将多个数据源中的数据集合起来存放在个一致 的数据存储( 如数据仓库) 中。这些数据源可能包含多个数据库( 如：s q ls e r v e r 、 o r a c l e 、a c c e s s 、s y b a s e 、m y s q l 等) ，数据立方体或一般文件( 如文本文 件等) 。 数据变换( d a t at r a n s f o r m a t i o n ) ；将某一个数据进行某种转换操作，然后将转 换后的值作为新的变量存放在样本数据中，而转换的目的是为了把数据和将来要 建立的模型拟和的更好。 数据规约( d a t ar e d u c t i o n ) ：我们都知道用于数据分析的数据集如果太大就会 降低挖掘的速度和影响挖掘的结果，于是就用数据规约得到数据集的压缩表示， 它小得多，但能产生同样的( 或几乎同样的) 分析结果。 数据挖掘过程 在此过程中挖掘算法的选择是一个核心的步骤，一般不会存在一个普遍适用 的数据挖掘算法，一个算法在一个领域非常有效，但在另一个领域却可能不太适 合。所以，在面对一个实际的领域，如何从众多的数据挖掘算法中精选有效的算 法就自然成为研究与开发任务首先要解决的一个核心问题。具体的数据采掘算法 有关联规则、特征规则、聚类规则、分类规则、序列规则等。 数据评价 任何个数据挖掘算法总有其优点和缺点，我们称之为正特性和负特性，一 个公正的算法评价无疑应该不仅考虑算法的正特性( 如：精确性) ，而且同时也应 该考虑算法的负特性( 如：存储空间、运行时间、训练和测试时间) ，数据挖掘算 法的评价标准大多采用兴趣度( i n t e r e s t i n g n e s s ) ，就是要求所挖掘出的模式是新颖 的、有效的、可理解的和有用的。在此过程中用一种通用的数据采掘评价的架构 来比较不同模型的效果：预报各种不同类型分析工具的结果。在进行各种比较和 预报的评价之后，给出一系列标准的图表，供用户进行定量评价。 具体的知识发现的简易信息流程图如下( 图1 2 ) ： 图1 2 简易的规则采掘信息流程 在此过程中要注意以下一些事项： 数据挖掘在整个过程中仅仅是一个步骤，挖掘结果质量的好坏有两个影响要 素：所采用的数据挖掘技术的有效性；用于挖掘的数据质量和数量( 数据量的大 小) ，如果在知识发现过程中，有其中一项选择不当。则挖掘的结果肯定不太理 想。 整个过程是一个不断反馈的过程。如果用户在过程中发现选择的数据不太 好，或者所使用的挖掘算法产生不了期望的结果，这时用户需要重复先前的步骤， 或者从新开始。在这反复过程中。不断地优先问题的解决方案，这样挖掘结果不 断地趋近于事物的本质。 1 2 3 数据挖掘功能 数据挖掘功能用于指定数据挖掘任务中要找的模式类型。数据挖掘任务一般 和可以分两类：描述和预测。描述性挖掘任务刻划数据库中数据的一般特性。预 测性挖掘任务是在当前数据上进行推断，以进行预测。 2 1 在某些情况下，用户不知道他们的数据中什么类型的模式是有趣的，因此可 能想搜索多种不同的模式。这样，重要的是，数据挖掘系统要能够挖掘多种类型 的模式，以适应不同的用户需求或不同的应用。因此，数据挖掘系统应当能够发 现各种粒度( 即不同的抽象层) 的模式。数据挖掘系统应当允许用户给出提示，指 导或聚焦有趣模式的搜索。由于有些模式并非对数据库中的所有数据都成立，通 常每个被发现的模式带上一个确定性或“可信性”度量。 数据挖掘功能以及它们可以发现的模式类型如下： 1 ) 概念类描述：特征化和区分 数据可以和类或概念相关联。这种类或概念的描述称为类，概念描述 ( c l a s s c o n c e p td e s c r i p t i o n ) 。这种描述可以通过下述方法得到：1 ) 数据特征化，一 般地汇总所研究类( 通常称为目标类( t a r g e tc l a s s ) ) 的数据；2 ) 数据区分，将目标 类与一个或多个比较类( 通常称为对比类( c o n t r a s t i n gc l a s s ) ) 进行比较；3 ) 数据特 证化和比较。 数据特征化( d a t ac h a r a c t e r i z a t i o n ) 是目标类数据的一般特性的汇总。通常， 用户指定类的数据通过数据库查询收集。数据特征的输出可以用多种形式提供。 包括：饼图、条图、曲线、多维数据立方休和包括交叉表在内的多维表。结果描 述也可以用概化关系( g e n e r a l i z e dr e l a t i o n ) 或规则形式( 称作特征规则) 提供。 数据区分( d a md i s c r i m i n a t i o n ) 是将目标类对象的一般特性与一个或多个对 比类对象的一般特性比较。目标类和对比类由用户指定，而对应的数据通过数据 库查询检索。区分描述的输出形式类似予特征描述，但区分描述应当包括比较度 量，帮助区分目标类和对比类。用规则表示的区分描述称为区分规则( d i s e r i m i n a n t r u l e ) 。用户应当能够对特征和区分描述的输出进行操作。 2 1 关联分析 关联分析( a s s o c i a t i o na n a l y s i s ) 发现关联规则，这些规则展示属性- 值频繁地在 给定数据集中起出现的条件。关联分析广泛用于购物篮或者事务数据分析。 更形式地。关联规则( a s s o c i a t i o nr u l e ) 是形如x j y ，即 “ ，、n 以 b i n 毛，的规则，其中，a i ( i e 1 ，m ) ) ，岛u e “d 是属性 值对。关联规则x ，y 解释为“满足x 中条件的数据库元组多半也满足y 中条件”。 3 1 分类和预测 分类( c l a s s i f i c a t i o n ) 是这样的过程，它找出描述并区分数据类或概念的模型 ( 或函数) ，以便能够使用模型预测类标记未知的对象类。 分类可以用来预测数据对象的类标记。然而，在某些应用中，人们可能希望 预测某些空缺的或不知道的数据值，而不是类标记。当被预测的值是数值数据时， 通常称之为预期l j ( p r e d i c t i o n ) 。尽管预测可以涉及数据值预测和类标记预测，通常 预测限于值预测，并因此不同于分类。预测也包含基于可用数据的分布趋势识别。 相关分析( r e l e v a n c ea n a l y s i s ) 可能需要在分类和预测之前进行，它试图识别对 于分类和预测无用的属性。这些属性应当排除。 4 ) 聚类分析 聚类分析与分类和预测不同，聚类( c l u s t e r i n g ) 分析数据对象，而不考虑己知 的类标记。一般情况下，训练数据中不提供类标记，因为不知道从何开始。对象 根据最大化类的相似性、最小化类问的相似性的原则进行聚类或分组，即对象的 簇( 聚类) 这样形成，使得在一个簇中的对象具有很高的相似性，而与其他簇中的 对象很不相似。所形成的每个簇可以看作一个对象类，由它可以导出规则。聚类 也便于分类编$ 1 j ( t a x o n o m yf o r m a t i o n ) ，将观察到的内容组织成类分层结构，把类 似的事件组织在一起。 5 ) 孤立点分析 数据库中可能包含一些数据对象，它们与数据的一般行为或模型不一致。这 些数据对象是孤立点( o u t l i e r ) 。大部分数据挖掘方法将孤立点视为噪声或异常而 丢弃。然而，在一些应用中( 如欺骗检测) ，罕见的事件可能比正常出现的那些更 有趣。孤立点数据分析称作孤立点挖掘( o u t l i e rm i n i n g ) 。孤立点可以使用统计试 验检测。它假定一个数据分布或概率模型，并使用距离度量，到其他聚类的距离 很大的对象被视为孤立点。基于偏差的方法通过考察一群对象主要特征上的差别 识别孤立点，而不是使用统计或距离变量。 6 ) 演变分析 数据演变分析( e v o l u t i o na n a l y s i s ) 描述行为随时间变化的对象的规律或趋势， 并对其建模。尽管这可能包括时间相关数据的特征化、区分、关联、分类或聚类， 这类分析的不同特点包括时间序列数据分析、序列或周期模式匹配和基于类似性 的数据分析。 1 2 4 数据挖掘的应用 d m ( k d d ) 的工具和软件己在各个部门得到很好的应用，并收到明显的效 益。 金融方面：银行信用卡和保险行业，预测存，贷款趋势，优化存贷款策略，用 d m 将市场分成有意义的群组和部门，从而协助市场经理和业务执行人员更好地 集中于有促进作用的活动和设计新的市场运动。 在客户关系管理方面：d m 能找出产品使用模式或协助了解客户行为，从而 可以改进通道管理( 如银行分支和a t m 等) 。又如正确时间销售( r i g h tt i m e m a r k e t i n g ) 就是基于顾客生活周期模型来实施的。 在零售业市场营销方面：是数据挖掘技术应用最早也是最重要的领域，d m 用于顾客购货篮的分析可以协助货架布置，促销活动时间，促销商品组合以及了 解滞销和畅销商品状况等商业活动。通过对种厂家商品在各连锁店的市场共享 分析、客户统计以及历史状况的分析，可以确定销售和广告业务的有效性。 在过程控制质量监督保证方面：d m 协助管理大数量变量之间的相互作用， d m 能自动发现出某些不正常的数据分布，暴露制造和装配操作过程中变化情况 和各种因素，从而协助质量工程师很快地注意到问题发生范围和采取改正措施。 在远程通讯部门：基于d m 的分析协助组织策略变更以适应外部世界的变 化，确定市场变化模式以指导销售计划在网络容量利用方面，d m 能提供对客户 组类服务使用的结构和模式的了解，从而指导容量计划人员对网络设旋作出最佳 投资决策。 化学制药行业：从各种文献资料总自动抽取有关化学反应的信息，发现新的 有用化学成分。在遥感领域针对每天从卫星上及其它方面来的巨额数据，对气象 预报，臭氧层监测等能起很大作用。 军事方面：使用d m 进行军事信息系统中的目标特征提取、态势关联规则挖掘 等。 总之，d m 可广泛应用于银行金融、零售与批发、制造、保险、公共设施、 政府、教育、远程通讯、软件开发、运输等各个企事业单位及国防科研上。据报 导，d m 的投资回报率有达4 0 0 甚至1 0 倍的事例。 1 2 5 数据挖掘与数据仓库 数据仓库技术是近十几年来信息技术领域迅速发展起来的一种数据组织和 管理技术。数据仓库是一种语义上致的数据存储，它充当决策支持数据模型的 物理实现，并存放企业战略所需信息，以用于支持分析型的数据处理。数据仓库 为数据挖掘创造了更方便的数据条件，体现在：c 2 8 j 1 ) 从个企业的角度看，数据仓库集成了企业内各部门的全面的、综合的 数据，基于数据仓库的数据挖掘能更好的满足高层战略决策的要求。而且数据仓 库大大地降低了数据挖掘地阻碍。数据挖掘一般要求大量的数据准备工作，而数 据仓库中的数据已经被充分收集起来，进行了整理、合并，并且有些还进行了初 步的分析处理。这样，可以集中精力于数据挖掘核心处理阶段。另外，数据仓库 中对数据不同粒度的集成和综合，更有效地支持了多层次、多种知识的挖掘。 2 ) 数据仓库是面向决策支持的，因此它的体系结构努力保证了查询和分析 的实时性；而一般的联机事务处理系统则主要要求更新的实时性。一般的数据仓 库设计成只读方式，最终用户不能更新数据。数据仓库中的数据更新由专门的一 套机制来实现。数据仓库对查询的强大支持使数据挖掘效率更高，挖掘过程可以 做到实时交互，使决策者的思维保持连续，有可能发现更深入、更有价值的知识。 总之，数据仓库为数据挖掘提供了更广阔的空间。收集、集成、预处理和存 储在数据仓库与数据集市中的数据，为数据挖掘提供了高质量的、有价值的数据 源，使得数据挖掘能更专注于知识的发现。因此，将数据仓库与数据挖掘结合在 一起来更好地支持分析决策，得到了研究领域地普遍关注。 2 1 聚类概述 第二章聚类 聚类( c l u s t e r i n g ) 是数据挖掘领域最为常见的技术之一，用于发现在数据库 中未知的对象类。通过聚类过程形成的每一个组称为一个类( c l u s t e r ) 。在数据 挖掘之前，对象类划分的数量与类型均是未知的，因此在数据挖掘后一般需要对 数据挖掘结果进行合理的分析与解释。聚类是现实世界中普遍存在的现象，其应 用也非常广泛，包括模式识别，数据分析，图象处理，以及市场研究。 s - i o 通过聚类，人能够识别密集的和稀疏的区域，因而发现全局的分布模式以及 数据属性之间有趣的相互关系。在商务上，聚类能够帮助市场分析人员从客户基 本库中发现不同的客户群，并且用购买模式来刻画不同的客户群的特征。在生物 学上，聚类能够用于推导植物和动物的分类，对基因进行分类，获得对种群中固 有结构的认识。聚类在地球观测数据库中相似地区的确定，汽车保险单持有者的 分组，及根据房子的类型、价值和地理位置对一个城市中房屋的分组上也可以发 挥作用。聚类也能用于对w e b 上的文档进行分类以发现信息。作为个数据挖 掘的功能，聚类分析能作为一个独立的工具来获得数据分布的情况，观察每个簇 的特点，集中对特定的某些簇做进一步的分析。此外，聚类分析可以作为其他算 法( 如特征和分类等) 的预处理步骤，这些算法再在生成的簇上进行处理。 在聚类知识发现方面，研究工作已经集中在为大型数据库的有效的、实际的 聚类分析寻找适当的方法。活跃的研究主题集中在聚类方法的可伸缩性，对复杂 形状和类型的数据的聚类有效性，高维聚类分析技术，以及针对大型数据库中混 合数值和分类数据的聚类方法。 2 2 聚类中的数据类型 聚类是将相近相似的对象聚成类，为此需要确切地描述和度量有关属性， 并从中比较对象间的相似程度，把最接近的对象归并成一类。而确定对象之间是 否相似，是通过计算对象之间的相似度来完成的。在描述对象的属性取值类型不 同时，相似度的计算方法也不相同。本节将讨论对象属性取值分别为区间标度变 量、二元变量和混合类型时相似度的计算方法。 但在给出相似性的计算方法之前，我们首先要论述一下数据的中心化与标准 化。这是由于表示对象的各种属性的变量往往使用不同的度量单位，其观测值也 可能相差十分悬殊。这样，绝对值大的变量其影响可能会覆盖绝对值小的变量， 记第j 个属性的极差为： r ，2 17 i 警。x ) _ 1 曼i | n 。( 。f j l 玉s ” v 1 曼 则对1 1 个对象的第j 个属性实旋的极差标准化为： 磅= 譬 ，一( 2 肌4 ) j 经变换后各变量的均值均为0 ，极差均为1 。 3 ) 极差正规化 它的变换式为： x ，：b 。2 一 j ：】，2 ，月 (215)ii x # - r a i n ( x ；) 2 ； 8 j 经变换后备变量的最小值均为0 ，极差均为1 。 经标准化变换后，各变量基点相同，变化范围也相等了。不过，在特定的应 用中，数据标准化也可能没有用。因此是否和如何进行标准化的选择最后还要交 由用户决定。 2 2 2 区间标度变量及其相似度 区间标度变量是一个粗略线性标度的连续变量。典型的例子包括高度、长度、 宽度和重量，经度和纬度坐标，以及大气温度。 在标准化处理后，对象间的相似度是基于对象问的距离来计算的。假设有n 个对象，描述第i 个对象的n 1 个属性值分别对应于区间标度变量值x d ，j 2 ，z 咖， 描述第j 个对象的1 1 1 个属性值分别对应于区间标度变量值x ，l x y 2 ，x 砌， o tf l ，2 ，彬。那么对象i 与j 之闻的相似度般以它们之问的距离d 协) 来表示。 距离越近，表明对象i 与i 之间越相似，差异越小：距离越远，表明对象i 与j 之间越不相似，差异越大。 最常用的距离度量方法是欧几里得距离，它的定义如下： d 削相一。川2 + i x i 2 - x j 2 j 2 + + i x i m - x j m l 2 ( 2 1 ) 另一个著名的度量方法是曼哈坦距离，它的定义如下： d o j ) 2 x i l 一。川+ 嘞一x j 2 + + 一。一 ( 2 - 2 ) 上面的两个距离度量方法都满足对距离函数的如下数学要求： 1 ) d ) o ：距离是一个非负的数值。 2 ) a ( u ) = o ：一个对象与自身的距离是0 。 3 ) d ) = d ) ：距离函数具有对称性。 4 ) d ) d ( u ) + d ) ：从对象i 到对象j 的直接距离不会大于途经任何其他 对象h 的距离( 三角不等式) 。 明考斯基距离是欧几里得距离和曼哈坦距离的概化，它的定义如下： d ( i j ) = ( i x i l 一。，1 2 一x j 2 h 一+ 一扩) v 9 ( 2 3 ) 这里的q 是一个正整数。当q = 1 时，它表示曼哈坦距离，当q = 2 时，它表示欧 几里得距离。 2 2 3 二元变量及其相似度 二元变量指只有两种取值的变量一般用i 来表示该变量存在，用0 来表示 该变量为空。像处理区间标度变量一样来对待二元变量会误导聚类结果，所以要 采用特定的方法来计算其相似度。 假设二元变量取值统计如下，q 是对于对象f 和f 值都为1 的变量的数目；r 是对于对象f 值为i 而对象，值为0 的变量的数目；s 是对于对象f 值为0 而对象 值为1 的变量的数目；t 是对于对象i 和，值都为0 的变量的数目。变量的总数 是p ，p = q + r + 5 + f 。 二元变量分为对称的二元变量和不对称的二元变量。如果一个二元变量的两 个状态是同等价值的，并有相同的权重，那么该二元变量是对称的，也就是两个 取值0 或1 没有优先权。基于对称二元变量的相似度称为恒定的相似度，即当一 些或者全部二元变量编码改变时，计算结果不会发生变化。对恒定的相似度来说， 评价两个对象i 和j 之间相似度的最著名的系数是简单匹配系数，其定义如下： 4 u ) 3 i ( 2 4 ) 如果两个状态的输出不是同样重要，那么该二元变量是不对称的。在这种情 况，二元变量经常被认为好像只有一个状态。基于不对称二元变量的相似度称为 非恒定的相似度。对非恒定的相似度，最著名的评价系数是j a c c a r d 系数，在它 的计算中，负匹配的数目t 被认为是不重要的，因此被忽略。 j 僻篇 2 _ 5 ) 当对称的二元变量和非对称的二元变量出现在同一个数据集中，将应用下面 描述的混台变量方法。 2 2 4 混合类型的变量 在前面所讨论的都是最基本、最理想化的情况。即同种类型变量描述的对象 之间的相似度的方法。但是在许多实际应用中，往往并不是这种理想化的情况， 对象常是被混合类型的变量描述的。一般来说，一个数据库可能包含上面列出的 全部变量类型。 计算用混合类型变量描述的对象之间的相似度有两种方法。一种方法是将变 量按类型分组，对每种类型的变量进行单独的聚类分析。如何这些分析得到兼容 的结果，这种方法是可行的。但是在实际的应用中，这种情况是不大可能的。 一个更可取的方法是将所有的变量一起处理，只进行一次聚类分析。一种技 术将不同类型的变量组合在单个相似度矩阵中，把所有有意义的变量转换导共同 的值域区间f o 。o ，1 。1 上。 假设数据集包含p 个不同类型的变量，对象i 和j 之间的相似度d ) 定义为 ( 2 6 ) 其中，d 妒表示在各属性取值标准化后对象i 和对象j 在第k 个属性上的距 离。d 矿) 表示在计算对象i 和对象j 之间的距离时是否考虑第k 个属性上的影响。 它们的取值情况分别如下： o 如果属性厂为= 元变量- 且弩。毛r 1 ，如果属性，为二元变量，且。矿0 r = i 之篁：! 望兰一，如果属性，为区问标度变量 ”4 。h 。h f 一”1 “ w 。 一0 ，如果羼伤馒为不对称二元变量，且v ；i 矿= o ” 1 1 ，其他情况 这样，当描述对象的变量是不同类型时，对象之间的相似度也能够进行计算。 2 3 聚类的主要方法 目前在文献中存在大量的聚类算法。算法的选择取决于数据的类型、聚类的 目的和应用。大体上，主要的聚类算法可以划分为如下几类： 2 3 1 划分聚类算法 划分聚类也叫分割聚类。给定一个1 3 个对象或元组的数据库，一个分割方法 构建数据的k 个划分，每个划分表示一个聚类，并且k n 。也就是说，它将数 据划分为k 个组，同时满足如下的要求：( 1 ) 每个组至少包含一个对象：( 2 ) 每 个对象必须属于且只属于一个组。但是在某些模糊划分技术中第二个要求可以放 宽。 给定要构建的划分数目k ，划分方法首先创建一个初始划分。然后采用一种 迭代的重定位技术，尝试通过对象在划分间移动来改进划分。个好的划分的一 般标准是：在同一个类中的对象之间尽可能接近或相关，而不同类中的对象之间 尽可能远离或不同。划分聚类方法输出的是多个互不相交的聚类集，如：k 均值 算法、c l a r a 算法、c l a r a n s 算法。 k 均值算法思想是：给定类的个数k 将n 个对象分到k 个类中去，使得类内 对象之间的相似性最大，而类之间相似性最小；k m e d o i d s 方法选取一个对象 m e d o i d 来代替聚类中心的作用，这样的一个m e d o i d 就标识了这个类。这种算法 计算量要比k 均值要大，一般只适合小数据量；c l a r a 算法是一种基于采样的方 法，能够处理大量的数据，算法思想就是用实际数据的抽样来代替整个数据，然 后再在这些抽样数据上利用k m e d o i d s 算法。c l a r a 算法的效率取决于采样的大 小，一般不太可能得到最佳的结果。因此在c l a r a 算法的基础上，提出了c l a r a n s 算法。与c l a r a 算法不同的是：c l a r a 算法寻找最佳的m e d o i d s 过程中，采样都是 不变的。而c l a r a n s 算法在每次循环过程中所采用的采样都是不一样的。 总体来说，在聚类的形状为凸形，大小和密度相似，并且聚类的数目可以合 理估计的情况下，上述各种分割聚类算法都是比较有效的，能够形成合理的聚类 结果。 2 3 2 层次聚类算法 层次聚类算法就是把数据库分成多个层次，然后对不同层次的数据采用划分 聚类，输出的是一棵层次化的分类树，层次的方法可以分为凝聚的和分裂的。凝 聚的方法，也称为自底向上的方法，一开始将每个对象作为单独的一个组，然后 相继地合并相近的对象或组，直到所有的组合并为一个( 层次的最上层) ，或者达 到一个终止条件。分裂的方法，也称为自顶向下的方法，一开始将所有的对象置 于一个类中。在迭代的每一步中，一个类被分裂为更小的类，直到最终每个对象 在单独的一个类中，或者达到一个终止条件。 层次的方法的缺陷在于，一旦一个步骤( 合并或者分裂) 完成，它就不能被撤 消。这个严格规定是有用的，由于不用担心组合数目的不同选择，计算代价会较 小。但是，该技术的一个主要问题是它不能更正错误的决定。有两种方法可以改 进层次聚类的结果：( 1 ) 在每层划分中，仔细分析对象间的“联接，例如：c u r e 和c h a m e l e o n 中的做法。( 2 ) 综合层次凝聚和迭代的重定位方法。首先用自底向 上的层次算法，然后用迭代的重定位来改进结果，例如在b i r c h 中。 典型的层次聚类算法有：b i r c h 、c u r e 、r o c k 等聚类算法。 b i r c h 算法是一个综合的层次聚类方法。首先把层次聚类的形成过程到结 果看作一棵树然后再用其他的聚类方法来进行修剪。在这个算法中引入了两个 概念：聚类特征和聚类特征树( c f 树) ，c f 定义为： c f = ( n ，l s ，s s ) 这里n 是子类中点的数日，西是n 个点的线性和( y ? ，- j ) ，s s 是数据点的平 l 方和( y 7 石f ) 。它们用于概括聚类描述。一个c f 树是高度平衡的树，它存储 一l i 了层次聚类的特征。这些结构辅助聚类方法在大型数据库中取得较高的速度和可 伸缩性。b r i c h 算法对增量或动态聚类也非常有效，采用了一种多阶段聚类技 术：数据集合的单遍扫描产生了一个基本的聚类，一或多遍的额外扫描可以进一 步地改进聚类质量。这个算法的计算复杂性是d ( 一) 。 c u r e 算法是采用了一种新颖的层次聚类算法，该算法选择基于质心和基于 代表对象方法之间的中间策略。它不同单个质心或对象来代表一个聚类，而是选 择数据空间中固定数目的具有代表性的点。每个类有多于一个的代表点使得 c u r e 算法可以适应非球形的几何形状。类的收缩或凝聚可以有助于控制孤立点 的影响。因此，c u r e 对孤立点的处理更加健壮，而且可以识别非球形和大小变 化较大的类。对于大型数据库，它也具有良好的伸缩性，而且没有牺牲聚类品质。 针对大型数据库，c u r e 采用随机取样和划分两种方法的组合：一个随机样本首 先被划分，每个划分被部分聚类。 由于c u r e 算法不处理分类属性，r o c k 算法是一个可选的凝聚的层次聚 类算法，适用于分类属性。它通过将凝聚的互连性与用户定义的静态互连性模型 相比较来度量两个类的相似度。r o c k 首先根据相似度闽值和共享近邻的概念从 给定的数据相似度矩阵构建一个稀疏的图，然后在这个稀疏图上执行一个层次聚 类算法。 2 3 3 基于密度的聚类算法 基于密度的方法与其他方法的一个根本区别是：它不是基于各种各样距离 的，而是基于密度的。这样就能克服基于距离的算法只能发现“类圆形”的聚类 的缺点，可以发现任意形状的聚类结果。这个方法的思想就是：只要一个区域中 的点的密度大于某个闺值，就把它加到与之相近的聚类中。 代表算法有：d b s c a n 算法、o p t i c s 算法、d e c l u e 算法、c l i q u e 算法 等。 算法是将密度足够大的那部分记录组成类，并可以在带有“噪声”的空间数 据库中发现任意形状的聚类。它定义类为密度相连的点的最大集合。在这个算法 中使用了e p s 和m i n p t s 两个全局变量。d b s c a n 需要由用户主观来选择参数， 并且聚类的结果对这两个参数非常敏感，从而影响了最终的聚类结果。如果采用 了空间索引，d b s c a n 的计算复杂度是o ( n l o g 。) ，这里n 是