（系统工程专业论文）Kmeans聚类算法研究及应用.pdf

武汉理i ：大学硕士学侮论文 摘要 聚类分析是数据挖掘中的一个重要研究领域，是一种数据划分或分组处理的 重要手段和方法。聚类无论在商务领域，还是在生物学、w e b 文档分类、图像 处理等其他领域都得到了有效的应用。目前聚类算法大体上分为基于划分的方 法、基于层次的方法、基于密度的方法、基于网格的方法、基于模型的方法以及 模糊聚类。 k m e a n s 算法是聚类算法中主要算法之一，它是一种基于划分的聚类算法。 本文在该算法的研究基础上，试图将该算法进行改进。同时在算法应用方面，将 聚类技术用于客户细分方面，客户细分是企业能够进行有效客户管理的前提和依 据，因此这方面的研究具有实际指导意义。 本文第一部分，主要阐述所研究对象的背景资料以及本文所要达到的目的， 并说明研究的思路和整体内容。 第二部分，主要介绍聚类分析的基础知识和聚类分析的基本方法，分析现有 的不同算法，相互比较得出各个算法的优缺点。分析了基于划分的典型算法 k - m e a n s 算法，对其优点和缺点进行了详细的分析 第三部分为本文的应用部分，将聚类技术应用于客户细分，通过层次分析法 建立客户的价值体系，量化客户价值；在此基础上应用聚类技术，将客户划分成 不同的类，由此来有效的开展客户管理，具有一定的实际意义。目前己经有一些 客户价值评价体系，但度量模型不够成熟。衡量指标一般是客户对于企业的直接 利润贡献，定量上也存在一定的难度。本文运用数据挖掘的方法，从企业的实际 情况出发，通过一系列可操作的客户价值评价指标，建立适合企业发展的客户价 值评价模型，并由此来度量客户价值、细分客户，建立客户价值管理的决策支持 系统。 第四部分为本文的核心章节。主要对k m e a n s 算法进行了改进。改进的算法 a 有效的解决了算法对初始值k 的依赖，能够自动生成类数k ；同时该算法对 初始中心点选取比较严格，各中心点的距离较远，这样避免了初始聚类中心会选 到一个类上，一定程度上克服了算法限入局部最优状态。为能进一步提高算法的 计算效率，提出了改进算法b ，该算法结合了抽样技术和层次凝聚算法对原算法 进行了改进，得到的新算法b 更有效。 最后，叙述了论文的主要工作，并指出进一步的研究方向。 关键词：聚类分析，k m e a n s 算法，客户细分 武汉理i ：大学硕士学何论文 a b s t ra c t c l u s t e r i n gi sam a j o rf i e l di nd a t am i n i n gw h i c ha l s oi sa ni m p o r t a n tm e t h o do f d a t ap a r t i t i o no rg r o u p i n g c l u s t e r i n gn o wh a sb e e na p p l i e di n t ov a r i o u sw a y si n c o m m e r c e ，m a r k e ta n a l y s i s ，b i o l o g y , w e bc l a s s i f i c a t i o na n ds oo n a n dc l u s t e r i n g a l g o r i t h m si n c l u d e sp a r t i t i o n i n g , h i e r a r c h i c a l ，d e n s i t y - b a s e d ，g r i d b a s e d ，m o d e l - b a s e d a l g o r i t h ma n df u z z yc l u s t e r i n g k - m e a n sa l g o r i t h mi so n eo ft h ee s s e n t i a lc l u s t e r i n ga l g o r i t h m s i ti sal 【i n do f c l u s t e r i n ga l g o r i t h mb a s e do np a r t i t i o n i n gm e t h o d t h et h e s i si sp l a n n e dt oi m p r o v e t h ea l g o r i t h mb a s e do nt h er e s e a r c h ，w h i l eo nt h ea p p l i c a t i o na s p e c t ，t h et h e s i st a k e t h ea l g o r i t h mi n t ot h ec u s t o m e rs e g m e n t a t i o nu s e c u s t o m e rs e g m e n t a t i o ni st h e e s s e n t i a le l e m e n tf o rt h ee n t e r p r i s et ot a k eo u tc r m i nt h ef i r s tp a r to ft h ep a p e r ，i ts h o w st h em a i ne l a b o r a t i o no b j e c to fs t u d y b a c k g r o u n dm a t e r i a la sw e l la st h eg o a lt h i sa r t i c l em u s ta c h i e v e ，a n ds h o w st h e r e s e a r c ht h em e n t a l i t ya n dt h eo v e r a l lc o n t e n t t h es e c o n d p a r tm a i n l yi n t r o d u c e st h eb a s i ck n o w l e d g eo fc l u s t e r i n ga n d m e t h o d sf o rc l u s t e r i n ga n a l y s i s ，o nt h eb a s i so ft h ed i f f e r e n ta l g o r i t h m sa n a l y s i s ， g e t t i n gt h ea d v a n t a g e sa n dd i s a d v a n t a g e st h r o u g hc o m p a r eo fd i f f e r e n ta l g o r i t h m s t h et h i r dp a r ti n t r o d u c et h ea p p l i c a t i o no ft h ea l g o r i t h m ，t h et h e s i sa p p l i e st h e c l u s t e r i n gt e c h n o l o g yi nt h eu s eo ft h ec u s t o m e rs e g m e n t a t i o n ，f i r s tb u i l d i n gt h e c u s t o m e rv a l u es y s t e mt h r o u g ha h p ；q u a n t i f yc u s t o m e rv a l u e ；t h e nd i v i d ec u s t o m e r i n t od i f f e r e n tc l a s s i f i c a t i o n su s i n gc l u s t e r i n gt e c h n o l o g y , s oc a nt a k eo u tt h ee f f i c i e n t c r ma c c o r d i n gt ot h ed e f e r e n tc u s t o m e rc l a s s i f i c a t i o n c u r r e n t l yt h e r ea r es o m e e v a l u a t i n gs y s t e m so fc u s t o m e rv a l u e ，b u td o n eo ft h e mc a nb ep u ti n t op r a c t i c e e f f i c i e n t l y , t h et h e s i sb u i l ta ne v a l u a t i n gs y s t e mo fc u s t o m e rv a l u ew h i c hi si nl i n e w i t ht h ed e v e l o p m e n to ft h ee n t e r p r i s e ，u s i n gt h em e t h o do fd a t am i n i n g , b a s e do nt h e p r a c t i c a ls i t u a t i o no ft h ee n t e r p r i s ea n dt h r o u g hs e r i e so fp r a c t i c a le v a l u a t i n gi n d e xo f c u s t o m e rv a l u e ，t h ee v a l u a t i n gs y s t e mc a l lb eu s e dt o q u a n t i f yc u s t o m e rv a l u e ， s e g m e n tc u s t o m e ra n db u i l dd e c i s i o ns u p p o r t i n gs y s t e mo ft h ec u s t o m e rv a l u e m a n a g e m e n t ， t h ef o u r t hp a r ti st h ec u r ep a r t ，m a i n l ya n a l y s i st h et y p i c a la l g o r i t h m 一一k - m e a n s ， t h et h e s i sp r o p o s e dt w oa l g o r i t h m st oi m p r o v et h ek - m e a n sa l g o r i t h m i m p r o v e d u 武汉理 大学硕士学何论文 a l g o r i t h m sa c a n g e tt h eka u t o m a t i c a l l y , a n dc a nc n s u r ea c h i e v et h eg l o b a lo p t i m u m v a l u et os o m ed e g r e e i m p r o v e da l g o r i t h mbw h i c hc o m b i n e dt h es a m p l et e c h n o l o g y a n d a r r a n g e m e n ta g g l o m e r a t i o na l g o r i t h m i sm u c he f f i c i e n tt h a nt h ek - m e a n s a l g o r i t h m a tt h ee n d ，r e c o u n tt h em a i nj o bo ft h et h e s i s ，a n dp o i n tt h ef u r t h e rr e s e a r c h d i r e c t i o n , k e y w o r d s ：c l u s t e r i n g , k - m e a n sa l g o r i t h m ，c u s t o m e rs e g m e n t a t i o n i 武汉理i ：大学硕士学位论文 1 1 选题的目的和意义 第1 章导论 面对信息技术的日新月异，人们利用信息技术生产和搜集数据的能力大幅度 提高，大量的数据库被用于商业管理、政府办公、科学研究和工程开发等等，要 想使数据真正成为一个公司的资源，只有充分利用它为公司自身的业务决策和战 略发展服务才行，否则大量的数据可能成为包袱，数据挖掘和知识发现技术应运 而生，并得以蓬勃发展，越来越显示出其强大的生命力。 数据挖掘( d a t am i n i n g ) 就是从大量的、不完全的、有噪声的、模糊的、随机 的数据中，提取隐含在其中的、人们事先不知道的，但又是潜在有用的信息和知 识的过程。人们把原始数据看作是形成知识的源泉，就像从矿石中采矿一样。原 始数据可以是结构化的，如关系数据库中的数据，也可以是半结构化的，如文本、 图形、图像数据，甚至是分布在网络上的异构型数据。发现知识的方法可以是数 学的，也可以是非数学的；可以是演绎的，也可以是归纳的。挖掘出的知识可以 被用于信息管理、查询优化、决策支持、过程控制等，还可以用于数据自身的维 护。因此，数据挖掘是- - t 交叉学科，涉及人工智能技术、统计技术与数据库技 术等多种技术。它汇聚了不同领域的研究者，尤其是数据库、人工智能、数理统 计、可视化、并行计算等方面的学者和工程技术人员。 聚类分析将大量数据划分为性质相同的子类，便于了解数据的分布情况。因 此，它广泛应用于模式识别、图像处理、数据压缩等许多领域，例如： 在市场分析中，通过聚类分析能帮助决策者识别不同特征的客户群以及 各客户群的行为特征； 在生物工程研究中，聚类分析能够用于推导动植物的分类，按照功能对 基因进行划分并获取种群中的固有结构特征； 在非关系数据库领域( 如空间数据库领域) ，聚类分析能够识别具有相同 地理特征的区域以及该区域的环境和人的特征： 在w e b 信息检索领域，聚类分析能够对w e b 文档进行分类，提高检索 效率。 本文主要将聚类分析技术应用于企业的客户细分中，各企业的竞争主要是客 户源的争夺，通过对客户的价值进行多角度的量化分析，可以帮助企业把有效的 精力集中在最有价值的客户和最有发展潜力的客户身上，优先配置资源，同他们 武汉理 大学硕士学位论文 建立稳定的客户关系，全面提升企业的盈利能力和竞争能力。因此这方面的研究 具有现实的指导意义。 选择聚类分析中的主要聚类方法k m e a i l s 法，对其进行改进，因为至今为 止没有一个方法是完美的，所以在使用的时候需要对其进行改进，改进后的算法 具有可行性，能够指导实践中的应用。 1 2 国内外相关研究综述 聚类分析作为统计学的一个分支，己被广泛地研究了多年，主要集中在基 于距离的聚类分析。基于k 均值、k - m e d o i d s ( k - q b 心点) 和其他一些方法的聚类 分析工具已经被加入到许多统计分析软件包或系统中。 在机器学习领域，聚类是无指导学习的一个例子。与分类不同，聚类和无指 导学习不依赖预先定义的类和带类标号的训练实例。由于这个原因，聚类是观察 式学习，而不是示例式学习。在概念聚类中，一组对象只有当它们可以被一个概 念描述时才形成一个簇，这不同于基于几何距离度量相似度的传统聚类。 聚类分析的研究工作集中在为大型数据库的有效和实际的聚类分析寻求适 当的方法，目前的研究方向包括下列几个方面： ( 1 ) 算法的可伸缩性：在很多聚类算法中，数据对象小于2 0 0 个的小数据 集合上鲁棒性执行多种数据模型；而对于包含几百万个数据对象的大规模数据库 进行聚类时，将会导致有不同的偏差结果，这就需要聚类算法具有高度的可伸缩 性，能有效地处理海量数据。 ( 2 ) 处理不同类型属性的能力：设计的很多算法是用于聚类数值类型的数 据，但在实际应用中可能要求聚类其他类型的数据，如分类标称类型 ( c a t e g o f i c a l n o m i n a l ) ，序数型( o r d i n a l ) ，二元( b i n a r y ) 数据，或者这些数据 类型的混合。 ( 3 ) 发现任意形状的聚类：许多聚类算法是基于欧几里德距离，趋向于发现 具有相近密度和尺寸的球状簇。但一个簇可能是任意形状的，提出能发现任意形 状簇的算法非常重要。 ( 4 ) 用于决定输入参数的领域知识最小化：在聚类分析中，许多聚类算法要 求用户输入一定的参数，如希望簇的数目。聚类结果对于输入参数很敏感，通常 参数较难确定，尤其是对于含有高维对象的数据集更是如此。要求入工输入参数 不但加重了用户的负担，而且也使聚类质量难以控制。 ( 5 ) 对于输入记录顺序不敏感：一些聚类算法对于输入数据的顺序是敏感 的。如对于同一个数据集合，以不同的顺序提交给同一个算法时，可能产生差别 很大的聚类结果。研究和开发对数据输入顺序不敏感的算法具有重要的意义。 2 武汉理 大学硕士学位论文 ( 6 ) 高维性：一个数据库可能含有若干维或者属性。很多聚类算法擅长处理 低维数据，一般只涉及两到三维。通常最多在三维的情况下能够很好地判断聚类 的质量。聚类数据对象在高维空间是非常有挑战性的，尤其是考虑到这样的数据 可能高度偏斜，非常稀疏。 ( 7 ) 处理噪声数据的能力：在现实应用中绝大多数的数据都包含了孤立点， 空缺、未知数据或者错误的数据。有些聚类算法对于这样的数据敏感，将会导致 质量较低的聚类结果。 ( 8 ) 基于约束的聚类：在实际应用中有可能需要在各种约束条件下进行聚 类。既要找到满足特定的约束，又要具有良好聚类特性的数据分组是一项具有挑 战性的任务。 ( 9 ) 可解释性和可用性：通常用户希望聚类结果是可解释的，可理解的和可 用的。因此，应用目标如何影响聚类方法的选择也是一项重要的研究课题。 同时，聚类方法存在下列主要问题，也需要进一步研究解决。 ( 1 ) 初始敏感性：初始值的选择以及输入顺序对聚类算法的最终结果影响很 大。在数据挖掘领域中可采取的措施：可以用多组不同的初始值并进行多次迭代， 最终选取其中最佳者作为计算结果，但是不能保证一定达到全局最优解。 ( 2 ) 最优解：聚类过程的本质是一个优化的过程，通过一种迭代运算使得系 统的目标函数达到一个最优解。然而这个目标函数在状态空间中是一个非凸函 数，它有许多极小值，而其中只有一个是全局最小值，其它都是局部最小值。优 化的目标就是达到全局最优，因此一个非凸函数的优化问题是待解决的研究课 题。 ( 3 ) 算法的效率问题：提高算法的效率问题是当前聚类领域中研究的又一个 重要问题。通过改进现有的聚类算法，使之具有增量聚类的能力，并具有较好的 伸缩性，在处理大数据库时，对数据库仅扫描一次，以提高算法的效率。 ( 4 ) 小波变换聚类算法的研究：目前有关聚类的研究成果大都是对k 均值 算法、模糊c 均值算法及s o f m 算法的推广和改进，这些研究成果对聚类的 性能都有不同程度的提高。然而对小波聚类算法及其改进方法的研究文献极少。 由于它符合一个好的聚类算法的许多要求，因此对小波聚类算法的进一步研究与 开发将会取得意想不到的成果。 ( 5 ) 基于不同媒体的挖掘：目前大多数聚类挖掘算法都是基于关系数据库或 事务数据库的算法，设计应用于其它类型数据库( 如面向对象数据库、面向属性 的数据库、时念数据库、文本数据库、异质数据库、w e b 数据库、多维数据库、 地理数据库、数据仓库等) 的聚类挖掘算法也将是十分有意义的工作。 武汉理i ：大学硕士学位论文 1 3 研究内容和研究方法 本文的主要研究工作，在理论研究方面，改进了k - m e a n s 算法本身存在的 一些不足。 k m e a n s 聚类问题是一个n p 问题( 难解的非指数问题) ，即问题的复杂度随 着比特位数的增长而指数上升，它与其他诸多的聚类和位置问题息息相关。但是 该算法却有以下缺点： 算法需要用户指定参数k 的值，而不同的k 值对聚类分析的效率和结 果有较大的影响： 算法的初始中心点选择与算法的运行效率密切相关，而随机选取中心点 有可能导致迭代次数很大或者限于某个局部最优状态； 只擅长于处理球状分布的数据； 对异常偏离的数据敏感； 算法只适合处理数值属性的数据，对于分类属性的数据处理效果不佳； 搜索策略效率低，面对大型数据库的处理该算法的开销大。 本文针对典型的k m e a n s 算法第点、点和第点三个方面的缺陷进行 研究。由于传统的k m e a n s 算法聚类结果受到初始聚类中心点选择的影响，因 此在传统的k - m e a n s 算法的基础上进行改进，改进的算法a 有效地解决了算法 对初始值k 的依赖，能够自动生成类数k ；同时该算法对初始中心点选取比较 严格，各中心点的距离较远，这就避免了初始聚类中心会选到一个类上，一定程 度上克服了算法限入局部最优状态。算法b 针对第点进行改进，结合了抽样 技术和层次凝聚算法对原算法进行了改进，得到的新算法b 更有效。 在算法的应用方面，将聚类技术应用于客户细分，通过层次分析法建立客户 的价值体系，量化客户价值：在此基础上应用聚类技术，将客户划分成不同的类， 由此来有效地开展客户管理，具有一定的实际意义。目前己经有一些客户价值评 价体系，但度量模型不够成熟。衡量指标一股是客户对于企业的直接利润贡献， 定量上也存在一定的难度。本文将运用数据挖掘的方法，从企业的实际情况出发， 通过一系列可操作的客户价值评价指标，建立适合企业发展的客户价值评价模 型，并由此来度量客户价值、细分客户，建立客户价值管理的决策支持系统。 本文在理论研究部分以发现问题、提出问题、分析问题、解决问题的思路为 一条线索，采取实证分析与理论分析相结合的研究方法，将理论研究与应用研究 有机地结合在一起，通过已有的k - m e a n s 改进算法的启示，针对算法仍存在的 不足进行研究，得出新的算法。 全文在借鉴前人研究成果的基础上，遵循聚类基本要求，逐步完成研究工作。 4 武汉理工大学硕士学位论文 第2 章数据挖掘中的聚类分析 乏1 聚类分析的基础知识 2 1 1 类的定义及表示 ( 1 ) 类的定义 在对数据对象进行聚类的时候，首先要给类定义。由于客观事务纷繁芜杂的 特性，以及我们在特征提取过程中用来表示样本点性质的特征变量的不同选择， 使得样本点的表示很不相同，在不同的问题中类的定义也是不同的。以下提出几 种不同的类的定义。 定义：设g 表示一个有k 个样本的集合，s 表示其中的样本，t 和v 为 预设阀值，则 如果对于任意墨，s f g ，都有d 岱f ，s j ) s r ，则g 称为一类； 如果对每个墨g ，都有f i _ j d ( s ，s ) s t 那么g 称为一类； 如果对于任意s 一g ，都有云南莩；d ( 墨, s 1 ) 5 丁 且d ( s ，s ，) s t ，那么g 称为一类。 对于任意样本s ；，都存在g 中的一个样本s ，满足d ( s ；，s ，) s 丁，则 称g 为一类。 显然，以上几种定义均通过限制元素间的距离来定义类，只是限制方法有 所不同，定义是要求最高的，凡是满足定义要求的类，肯定满足其他几种定 义；凡是满足定义的集合，也必定满足定义。 ( 2 ) 类的表示 聚类的表示方法一般有以下几种： 自然语言描述：直接用自然语言描述符合某些条件的数据点属于某个类。 d n f 描述：用析取范式表示简洁、准确，例如： ( 1 8 p t 3 0 ) v ( 8 0 0 a m 2 0 0 0 ) 聚类谱系图：大部分的聚类算法的输出结果为一个聚类谱系图，它可以 详细展示从总体归为一类到所有样本点自成一类之间所有的中间情况，如果聚类 谱系图的每个类均标有其平台高度，则称之为标度聚类谱系图。 5 武汉理工大学硕士学位论文 2 1 2 相似性测度 聚类分析按照样本在性质上的亲疏远近进行分类。为了使类分得合理，必须 描述样本之间的亲疏远近的程度。刻画样本点之间的相似性主要有距离和相似系 数： ( 1 ) 距离：设使用n 个指标特征变量来描述样本，那么我们就可以把每个 样本点看作n 维空间的一个点，进而使用某种距离来表示样本点之间的相似性， 距离较近的样本点性质较相似，距离较远的样本点差异较大。 距离函数：设q 是样本点集合，如果函数满足以下条件，我们称之为距离函 数： 正定性d ( x ，y ) 0 ，i fx ，y d ( x ，】，) - 0 ，i fx = y 对称性d ( x ，y ) - d ( y ，x ) 三角不等式o ( x ，l ，) + d ( y ，z ) - d ( x ，z ) 有时我们定义的距离函数不满足三角不等式，从广义的角度我们也称为距 离。而在另外一些场合，条件被减弱为 4 d 僻，y ) sm a x ( d ( x ，z ) ，d ( z ，y ) ) 对于一切的z 使用条件4 替代条件得到的距离，我们称之为极端距离，它在系统聚类法 的分析中有很重要的应用。 ( 2 ) 聚类分析中常用以下三种距离函数： 明氏( m i n k o w s k i ) 距离 d q ( x , y ) 。 驴一y , 1 9 9 “ 当q 取1 ，2 ，o 。时，则分别得绝对距离、欧式( e u c l i d ) 距离、切比雪夫 ( c h e b y s h e v ) 距离。 马氏( m a h a l a n o i s ) 距离 d ( x ，l ，) = ( x l ，) 7 x 罗4 ( x l ，) 1 2 是样本矩阵a 的协方差阵，是总体分布的协差估计量。马氏距离是明氏 距离的改进，它对于一切线性变换是不变的，克服了明氏距离受量纲影响的缺点； 马氏距离也部分克服了多重相关性。 兰氏( l a n c e ) 距离 叫 y ) 一萃嘲 1 3 6 武汉理e 大学硕士学位论文 兰氏距离克服了明氏距离受量纲影响的缺点，但没有考虑多重相关性。 聚类分析中不仅要将样本点聚类，在有些场合还需要对特征变量进行聚类。 特征变量之间的相似性测度除了可以使用上述的距离函数之外，更常用的是相似 系数函数。 ( 2 ) 相似系数： 如果一个函数c ：v x v 一 一1 ，1 满足以下条件，我们就称之为相似系数函 数。 c ( x ，l ，) s 1 c ( x ，l ，) - 1 c ( x ，y ) 一c o ，石) c ( x ，y ) 越接近1 ，两个特征变量间的关系越密切。经常采用的相似系数有 以下两种： 夹角余弦 置v “置班万丽万 1 4 这是受相似形的启发而来的，夹角余弦函数忽略各个向量的绝对长度，着重 从形状方面考虑它们之间的关系。当两个向量方向相近时，夹角余弦值较大。反 之则较小。特殊的当两个向量平行时，夹角余弦值为1 ，而正交时余弦值为0 。 相关系数 ( 置一贾) 一而 呼。再菰丽 1 5 相关系数是对向量做标准差标准化后的夹角余弦。它表示两个向量的线性相 关程度。 2 1 - 3 类问的测度函数 类问的测度一般使用距离作为测度函数。一般有如下六种： 最短距离法：也叫单连接( s i n g l el i n k ) 法或最近邻( n e a r e s tn e ：i g h b o r ) 连接，使用两类间的最近两点的距离来描述两类问的相似程度。 d ( g ，g 2 ) 一m i n n ( x ，y ) p g l ，y e g 2 最长距离法：也叫完全连接( c o m p l e t el i n k ) 或最远紧邻连接，使用两类 间的最远两点的距离来描述两类问的相似程度。 7 武汉理【大学硕士学位论文 为一类，然后遵循某种最优准则将它分为两类，一直分裂为每个样本点各成一类。 是否需要分裂操作，同时使用一个分类函数的值来控制。当一类分得比较合理时， 分类函数的值最小，反之则较大。分裂法试图寻求一种分类方案，使得分类函数 值达到极小。 加x 法( a d d i n g ) ：设已经存在一个分类方案( 使用聚类谱系图或分类树表 示) ，每次加入一个新样本，按照某种规则确定其在分类系统的合适位置，当样 本全部加入之后，分类即告结束。 除了以上提到的策略之外，还有其他的一些方法，例如应用模糊数学理论的 模糊聚类法、应用最小支撑树的图论法等等。 2 1 5 聚类的一般步骤 第一步是特征提取。它的输入是原始样本，由领域专家决定使用哪些特征来 深刻地刻画样本的本质性质和结构。特征提取的结果是输出一个矩阵，每一行是 一个样本，每一列是一个特征指标变量。 选取特征的优劣将直接影响以后的分析和决策。如果第一步就选择了与聚类 意图毫不相关的特征变量，试图得到良好的聚类结果则无异于缘木求鱼。因为无 论后续步骤采用多么优良的聚类算法和阀值选择方案，都不可能计算出执行者的 意图。合理的特征选取方案应当使得同类样本在特征空间中相距较近，异类样本 则相距较远。 在有些场合还需要将得到的样本矩阵进行一些后处理工作。比如为了统一量 纲就对变量进行标准化处理，这样采用相同量纲的变量才具有可比性，在有些场 合可能选择的特征变量太多，不利于以后的分析和决策，这时可以先进行一下降 维处理，仅凭经验和领域知识选择的特征变量有可能是相关的，进行主成分分析 就可以消除变量间的相关性，从而得到一些相互独立的特征变量。 下来是执行聚类算法，获得聚类谱系图。聚类的输入是一个样本矩阵，它把 一个样本想象成为特征变量空间中的点。 聚类算法的目的就是获得能够反映n 维空间中这些样本点的最本质的 “簇”的性质。这一步没有领域专家的参与，它除了集合知识外不考虑任何的领 域知识，不考虑特征变量在其领域中的特定含义，仅仅认为它是特征空间中的一 维而已。 聚类算法的输入一般是一个聚类谱系图，由粗到细地反映了所有的分类情况 或者直接给出分类方案，包括总共分为几类，每类具体包含那些样本点等等。 最后是选取合适的分类阀值。在得到了聚类谱系图后，领域专家凭借经验和 领域知识，根据具体的应用场合，决定阀值的选取。选定阀值以后，就能够从聚 9 武汉理 大学硕士学位论文 类谱系图上直接看出分类方案。没有领域专家的参与，不考虑具体的应用背景， 而仅仅依赖从聚类谱系图出发寻找聚类指数的突变点或者求最小生成树的长边 等等，往往不会得到满意的结果。领域专家还可以对聚类结果结合领域知识进行 进一步的分析，从而加深样本点和特征变量的认识。实际应用聚类分析是一个需 要多方参与的过程，它无法脱离领域专家的参与，聚类算法仅仅是整个聚类流程 中的一个环节而已，光依靠聚类算法专家一般不会得到令人满意的结果。 2 2 聚类分析的方法 常见的聚类分析的方法有四类：划分方法，层次方法、基于密度的方法和 基于网格的方法。 2 2 1 基于层次的方法( h i e r a c h i c a lc l u s t e r i n gm e t h o d s ) t 1 1 【2 层次聚类法也称系统聚类法，是目前实际工作中用得最多的一类算法。 ( 1 ) 层次聚类的步骤 层次聚类是将类由多变少的一种方法，分类的步骤如下： 各样品各成一类，这时有n 类 计算各样品之间的距离，将最近的两个样品归为一类； 计算新类与其余各类的距离，再将距离最近的两类合并，这时如果类的 个数仍大于1 ，则再继续重复上述步骤，直到所有样品归为一类，则停止。 样品之间的距离有不同的定义方法，类与类之间也同样有不同的距离的定义 方法，这样就产生了不同的层次聚类方法。 ( 2 ) 常用的层次聚类方法 最短距离法 两个类q 和q 的距离d 。定义为d 。；m i n d ，j 墨e g p ，q ，即类 g 。和g q 中相距最近的两个样品的距离。用这个距离做层次聚类，称为最短距离 法。 最长距离法 最长距离法与最短距离法的并类步骤完全一样，也是各类先自成一类，然后 将距离最小的两类合并。即定义两个类q 和g q 的距离d ，为： d 。= m a x d 口q ，工，q ) 。设某一步将类g ，和q 合并为g ，则q 与某一类 g 的距离为d k m a x d 肿，d k ，然后再将距离最近的两类合并，直到所有的样 品都归在一类为止。 1 0 武汉理e 大学硕士学位论文 ( 曼) 中l 司距离法 设某一步将g v 和q 合并为g r ，计算某一类q 与g ，之间的距离。 一哇瑶+ 三磁一i 1 。 l 9 用这个距离做聚类，称为中问距离法。中间距离法可以推广到一般的情形， 。哇瑶+ 三瑶+ 卢d 。z ，- ；，i 1s p s 。 1 1 0 当芦一- 1 4 时，就为中间距离法。使用中间距离法聚类的时候，聚类的结果 与类的形成的过程有关。 重心法 从物理的观点来看，一个类用它的重心来代表比较合理，这时，类与类之间 的距离就可用重心之问的距离来表示。设嘭和q 的重心分别是i - 和巧，则 q 和q 之间的距离是：d ，- d 。- 。- 设某一步将q 和q 并成g ，各类的样品数目分别是一，n 。和n ，一以，+ n q ，相 应的重心是了_ 和i ，则x r 。丢o ，x ，+ 工e ) 设某一类q ，其重心是石，则 驴( n 卫d 2 + 鲁瑶一警d 。2 声 。 此为重心法距离推算公式。 类平均法 类平均法定义两类删的距离平方等于两类中元素两两之间的平均平方 距离一队d m 2 ”i t _ 嘉q 露 u 2 萎黧：= = 苎曼和q 的样品数。其递推公式为巩一e 瑶+ 鲁瑶乒 离差平方和法 ”7”7 这个方法首先是由w a r d 提出来的，思想来自方差分析，如果类分得正确， 同类样品的离差平方和应当较小，类与类之问的离差平方和应当较大。 设将咒个样品分成k 类，g 1 ，g 2 ，q ，用兄表示g 中的第f 个样品，表 示q 样品的个数，i 是g ：的重心，则在g 中样品的离差平方和 墨一窆( 以一习( x i t 一_ ) 总的类内离差平方和： s - 艺( 以一_ ) ( 也一- ) 1 1 3 1 1 武汉理工大学硕士学位论文 定义类间的距离为： d 2 5 i n p n q ( 石一x q ) 7 ( 一x p 一一x q ) 1 1 4 距离的递推公式：， 壤。inp+ink2+石即q+ink2一石nik2nr nnnn 1 1 5 + ，+ 以，+ 。 11 其中，n 。，n ， 分别为g ，嚷，q ，q 的样品数。 以上六种层次聚类法，w i s h a r t 首先将它们统一： 聪t 口，壤+ 瑶+ 卢嚷+ y i 瑶一2 l 1 1 6 其中g ，- qu q 。不同参数代入，得到不同的层次聚类法；参数列表如下： ， 表2 - 1 层次聚类法参数表 方法 口， a 口卢 r 最短距离法1 21 201 2 最长距离法1 21 201 2 中间距离法1 2l ，2 一一1s 艿s 0 o 4 重心法 玎，i n , n 。h r - ( n ，) 杉 o 类平均法 h ，n ， n 口n ， 0 o 离差平方和法 0 女+ h 。) ( n t + ，l ，)( r t i + k ) ( + 胛，)一玎i “，+ n ，) 0 2 2 2 基于划分的方法【3 】 k - m e a n s 方法和k - m e d o i d 方法是最典型的划分方法。算法的处理思路基本 相同，即给定一个数据库d ，用户输入要获得聚类簇的个数k 。开始任意将d 划分为k 个部分，然后通过更新簇的中心来调整划分，当整体差异函数收敛的时 候结束处理过程。它们之问的差别是簇中心的表示方法，划分调整策略和整体差 异函数的定义。 k - m e a n s 方法之后的章节会有详细介绍，这里主要对k - m e d o i d 算法做主要 说明。k 中心算法有三种实现方式p a m ，c l a r a 和c l a r a n s 。p a m ( p a r t i t i o n a r o u n dm e d o i d ) 方法：对于一个数据库d ，d 中含有个元素：作为参数需要 给出要生成的簇的个数k o k s ) 。p a m 方法首先随机选择k 个对象作为簇 的中心，对于每一个中心点o j j ，p a m 方法试图用所有n k 个非中心点替换 它。如果平方误差减小则替换发生。p a m 方法对于小数掘库处理能得到很好的 结果，但是它的计算代价非常高。需要用n k 个点替换k 个点，每次替换都要 武汉理工大学硕士学位论文 检验一k 次代价函数，所以复杂度是o ( n ( 一七) 2 ) 。 c l a r a ( c l u s t e r i n gl a r g e a p p l i c a t i o n ) 方法：是p a m 方法的增强版，专 门用于处理大量数据。c l a r a 方法的思想是：从所有的数据中取出5 组样本， 对每个样本实行p a m 算法。比较5 组的平方一误差，选取最小的作为输出结果。 c l a r a 方法的确在处理大数据量时提高了运算速度，但是它所得出来的结果只 是关于样本点最优的，并不是所有数据的最优解。c l a r a 方法结果的优劣依赖 于采样方法。 c l a r a n s ( c l u s t e r i n gl a r g ea p p l i c a t i o nb a s e du p o nr a nd o m i z e ds e a r c h ) 方法是c l a r a 方法的加强版，用以提高结果的质量和伸缩性。c l a r a n s 方 法的思想是：任意从k 个中心点中取出一个点，从n k 中任意取一个点去替换 它，如果替换成功则重新开始。如果尝试几次( 参数由人给出) 没有发现更好的 的结果，就认为已经达到局部最优。c l a r a n s 方法的复杂度是o ( n 2 ) 。实 验显示c i a r a n s 方法比p a m 和c i a r a 更有效。 2 2 3 基于密度的方法【4 基于密度的方法是通过对象的密度来识别簇的，它可以发现任意形状的簇。 g d b s c a n 、o p t i c s 和d e n c l u e 是三种典型的密度方法。g d b s c a n 方法 是检验每一个对象邻居的个数是否超过用户给定的闽值，当达到阈值时就认为这 个对象周围足够密集。o p t i c s 方法并不是显式地进行聚类，而是为自动和交互 的聚类分折计算出一个簇次序。由于要对对象的邻域进行分析，d b s c a n 方法 和o p t i c s 方法都是用空间索引结构( r 树) 来加速邻域的查询速度。d e n c l u e 方法能有效的处理高维度数据，它是通过影响函数来取定空间密度，它使用了网 格单元和树型存储，处理速度快，d e n c l u e 方法对用户确定的参数非常敏感。 2 2 4 基于网格的方法 5 1 网格算法使用网格技术把数据空间划分为有限的格子，所有的操作都在格子 上进行。网格算法的特点是处理的花费与对象数目有关，只依赖于网格数目，典 型的基于网格的方法有s t i n g 方法、w a v e c l u s t e r 方法和c l i q u e 方法。 s t i n g ( s t a t i s t i c a li n f o r m a t i o ng r i d ) 方法使用分层统计信息结构。它的思想 是：提前将与网格相关的统计信息计算出来存储在分层的结构中。这些信息独立 于聚类的查询。s t i n g 方法把对象空间化为许多矩形的格子，划分时是按照层 次顺序进行的，高层的格子被化为许多低层次的格子。这样高层网格的统计信息 可以从它的子网格获得。每一个网格中储存以下统计信息：平均值m ；标准偏差 s ；最小值m i n ；最大值m a x ；分布类型：d i s t r i b u t i o n 。处理查询的时候，s t i n g 武汉理_ t 大学硕士学位论文 方法从最高层开始，检查与查询相关的每一个网格，根层处理完之后就处理下一 层，这时候只处理上一层相关的网格的子网格，算法一直处理到网格的最底层结 束。输出结果由最底层网格构成。 w a v e c l u s t e r 方法的主要思想是把多维数据看作一个多维信号来处理。它首 先将数据空间划分成网格结构，然后通过小波变换将数据空间变换成频域空问， 在频域空间通过与一个核函数作卷积后，数据的自然聚类属性就显现出来。 w a v e c l u s t e r 方法是一个多分辨率的算法，高分辨率可以获得细节的信息，低分 辨率可以获得轮廓信息。方法的时间复杂度是o ( n ) ，其中n 是数据库中对象的 个数。 c l i q u e 方法是一种密度与网格相结合的算法，它可以发现高维度数据空间 中的聚类簇。c l i q u e 方法采用了先验方法：在一个k 维空间中，如果一个区域 是密集的，那么在k 一1 维子空间它也是密集的。若是反过来思考：k 一1 维空间的 密集区域一定包含在k 维空间的密集区域的候选区。c l i q u e 方法的工作过程 是：第一步将数据空间化成许多互不相交的网格，第二步根据空间的每一维度判 定网格是否是密集的，第三步将所有密集的网格求交集，检查交集的连通性，生 成簇的最小覆盖。c l i q u e 方法的复杂度是d 加) ，行是数据库中对象的个数。 处理时间与数据的维度成线性关系。 2 3k m e a n s 算法 k m e a n s 算法是很典型的基于距离的聚类算法，采用距离作为相似性的评价 指标，即认为两个对象的距离越近，其相似性就越大。该类算法认为簇是由距离 靠近的对象组成的，因此把得到紧凑且独立的簇作为最终目标。 2 3 1k - m e a n s 算法的基本原理【6 l k m c a n s 算法是硬聚类算法，是典型的基于原型的