（计算机应用技术专业论文）调整学习聚类算法的研究.pdf

调整学习聚类算法的研究 摘要 聚类是重要的数据挖掘技术，在海量数据统计、网络分析及医学图形图像 自动监测等领域具有广泛的应用背景。聚类就是根据数据的内在特性将数据对 象划分到不同的组( 或簇) 中，使得属于同簇的数据对象具有相似性，不同簇的 数据对象具有相异性。近几十年来，国内外的研究者们提出了许多聚类算法， 这些算法大多从全局或局部的角度观察聚类，力图发现所有聚类方案的最优结 果。由于处理数据的规模大、类型复杂，因此目前的聚类算法不能满足人们对 聚类质量的要求。同时，经典算法在聚类过程中都有保持问题和数据对象位置 不变的特点。 本文着眼于提高聚类质量，充分地结合经典聚类算法的特点，力图从运动 的角度来分析聚类，提出了基于调整学习的聚类算法，其基本思想是通过调用 调整算子，变换数据对象的位置来构造一系列粗细粒度不同的近似问题。首先 对细粒度近似问题聚类，再利用细粒度问题的聚类结果来引导粗粒度问题的求 解。由于变换能改变问题的拓扑结构，从而使原始问题可以转化为多个简单问 题迭代求解，达到降低问题难度和提高聚类质量的目的。本文在调整学习聚类 算法的基础上分别对f c m 算法和c l a r a n s 算法进行了改进。最后通过多组 仿真数据和3 个实际数据集比较了改进算法与经典算法的聚类质量。实验结果 表明，改进后的算法在时间、空间复杂度不变的情况下聚类质量有了较显著提 l 商。 本文提出的新聚类算法以经典聚类算法为其从属算法并对其改进。为人们 获得高质量聚类结果提供了新思路和新途径，为准确地挖掘出数据集中隐含的 模型和信息提供了保证。因此，本文的研究具有较高的理论和实践意义。 关键词：数据挖掘调整学习聚类算法调整算子 r e s e a r c ho ff i n e - t u n e dl e a r n i n gc l u s t e r i n g a l g o r i t h m a b s t r a c t c l u s t e r i n gi sa ni m p o r t a n tt e c h n i q u ew h i c hi su s e di nv a r i o u sf i e l d ss u c ha s s t a t i s t i c sf o rt r e m e n d o u sd a t a ，a n a l y s i so fn e t w o r k ，a u t o m a t i cs u p e r v i s e do f m e d i c a l i m a g e s c l u s t e r i n gd i v i d e sd a t ao b je c t si n t od i f f e r e n tg r o u p s ( c l u s t e r s ) a c c o r d i n gt o t h ei n t e r n a lc h a r a c t e r i s t i c ss ot h a tt h ee l e m e n t sa t t a c h e dt ot h ed i f f e r e n tc l u s t e r s h a v ed i s s i m i l a r i t i e sa n dt h eo n e sa t t a c h e dt ot h es a m ec l u s t e r sh a v es i m i l a r i t i e s i n r e c e n tt e n y e a r s ，d o m e s t i co ro v e r s e ar e s e a r c h e r sp r e s e n t e dm a n yc l u s t e r i n g a l g o r i t h m st h a tm o s t l yc o n s i d e r e dc l u s t e r i n gi nl o c a lo rw h o l ea n g l ea n dt r i e dt o d i s c o v e rt h ee x c e l l e n tr e s u l t sf r o ma l lc l u s t e r i n gs t r a t e g i e s o w i n gt ot h el a r g es c a l e d a t aa n dt h ec o m p l i c a t e dt y p e s ，t h ec l u s t e r i n ga l g o r i t h m sc a n t s a t i s f yt h ep e o p l ei n t h ea s p e c to fc l u s t e r i n gq u a l i t y m e a n w h i l e ，c l a s s i ca l g o r i t h m sa r ec h a r a c t e r i z e db y k e e p i n gt h eq u e s t i o n sa n dt h el o c a l i t yo fd a t ao b je c t si n v a r i a b l e a i m i n g t o i m p r o v e t h e q u a l i t y o f c l u s t e r i n g ，t h i s t h e s i s a d o p t st h e c h a r a c t e r i s t i c so fc l a s s i cc l u s t e r i n ga l g o r i t h m s ，e n d e a v o r st oa n a l y s e si ti nm o v a b l e a n g l e m e a n w h i l e ，an e wc l u s t e r i n ga l g o r i t h mb a s e do nf i n e t u n e dl e a r n i n g ， w h i c hi sc a l l e dc a t - l ，i sp r o p o s e d t h ee s s e n c eo fc a t - li st oc a l laf i n e t u n e d o p e r a t o rt oc o n s t r u c tas e r i e so fa p p r o x i m a t ep r o b l e mo ft h eo r i g i n a la n dt h e g r a n u l a r i t yo fe a c ha p p r o x i m a t ep r o b l e mi sd i f f e r e n ta n dd e p e n d so nf i n e t u n e d f a c t o r s f i r s t l y ，s o m et h i ng r a n u l a r i t ya p p r o x i m a t ep r o b l e m sa r ec l u s t e r e d ；s e c o n d l y ， t h i c ka p p r o x i m a t ep r o b l e m sa r ec o n s t r u c t e da n ds o l v e db ym e a n so ft h er e s u l t sa t f i r s ts t e p s i n c et r a n s f o r m a t i o nc h a n g e st h et o p o l o g ys t r u c t u r e ，t h eo r i g i n a lp r o b l e m c a nb ec o n v e r t e dt om a n ys i m p l ep r o b l e m sa n dg e tt ot h ed e s t i n a t i o nt h a td i f f i c u l t y i sr e d u c e da n dc l u s t e r i n gq u a l i t yi si m p r o v e d c l a s s i c c l u s t e r i n ga l g o r i t h mf c m a n dc l a r a n sa r ei m p r o v e du n d e rt h ec a t - lf r a m e w o r k n e w c l u s t e r i n g a l g o r i t h m s ，f c ma n dc l a r a n sa r ee x e c u t e do ns e v e r a ls y n t h e t i cd a t a s e ta n d t h r e er e a ld a t a s e t e x p e r i m e n tr e s u l t ss h o wt h a ta l g o r i t h ma f t e rb e t t e r m e n tc a u s e s r e m a r k a b l ei m p r o v e m e n to nc l u s t e r i n gq u a l i t yu n d e rt h ec o n d i t i o no ft h ec o n s t a n t t i m ea n ds p a c ec o m p l e x i t y t h en e wc l u s t e r i n ga l g o r i t h mp r e s e n t e di nt h et h e s i st a k e sc l a s s i cc l u s t e r in g a l g o r i t h m sa si t sa t t a c h e do n e sa n dm a k et h e mi m p r o v e d t h i sp r o v i d e sp e o p l ew i t h n e ww a y sa n dt h o u g h t si nt h ei n t e r e s to fa c q u i r i n gb e t t e rr e s u l t sa n dm i n i n gt h e h i d d e nm o d e l sa n di n f o r m a t i o n t h u s ，r e s e a r c h e so ft h i st h e s i sh a v et h eg r e a t s i g n i f i c a n c ei nt h e o r ya n dp r a c t i c e k e yw o r d s ：d a t am i n i n g ；f i n e t u n e dl e a r n i n g ；c l u s t e r i n ga l g o r i t h m ： f i n e t u n e do p e r a t o r 插图清单 图2 1k 平均算法1 0 图2 2k 中心点聚类代价函数的四种情况l l 图2 3k 一中心点算法1 2 图2 4 在数据集 a , b ，c ，d ，e ) 上的凝聚和分裂层次聚类1 4 图2 5 在基于密度的聚类中密度可达和密度相连1 5 图2 6o p t i c s 的术语1 6 图2 7s t i n g 聚类的层次结构1 8 图3 1 公式( 3 3 ) 的局部搜索解空间2 2 图3 2 调整学习的基本框架2 3 图3 3 调整学习的直观表示2 3 图3 4 算法c a l t 2 5 图3 5 等距调整算子2 6 图3 6 噪声平滑调整算子2 7 图4 1f c m 算法3 0 图4 2f c m 算法的平均目标函数值3 0 图4 3c a n l f c m 算法程序流程图31 图4 4f c m 与c a t - l f c m ( 等距调整算子) 的质量对比3 2 图4 5f c m 与c a t - l f c m ( 噪声平滑调整算子) 的质量对比3 3 图4 6f c m 与c a t - l f c m ( 等距调整算子) 的质量对比3 4 图4 7f c m 与c a t - l f c m ( 噪声平滑调整算子) 的质量对比3 4 图4 8c l a r a n s 图示例3 5 图4 9c l a r a n s 算法3 5 图4 1 0c a t l c a l a r n s 算法程序流程图3 6 图4 。1 l 三种算法在g r o u p l 上的质量对比3 8 图4 1 2 三种算法在g r o u p 2 上的质量对比3 8 图4 1 3 三种算法在i m g s e g 上的质量对比3 9 图4 1 4 三种算法在l t r r e c 上的质量对比3 9 表2 1 二态变量统计表6 表4 1 仿真数据集3 2 表4 2 组l 3 7 表4 3 组2 3 7 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所 知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得金胆王些太堂 或其他教育机构的学位或证书而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文版权使用授权书 本学位论文作者完全了解金魍王些太堂有关保留、使用学位论文的规定，有权保留并向 国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借阅。本人授权金魍些厶 兰l 可以将学位论文的全部或部分论文内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文者签名； 签字日期：沙嘏年j 月日 学位论文作者毕业后去向： 工作单位： 通讯地址： 导师签名： 歹彪 签字日期：勿谚年瑚夕日 电话： 邮编： 致谢 值此论文完成之际，谨向我的导师王浩教授致以最衷心的感谢。本论文是 在他的悉心教导和关怀下完成的。他严肃的科学态度，严谨的治学精神，精益 求精的工作作风，深深地感染和激励着我。在攻读硕士学位期间，他对我的学 习和科研给予了很大的支持和帮助，我所取得的每一点成绩都与他的谆谆教诲 和悉心指导分不开。我以他为榜样，学习他认真严谨的治学态度、豁达宽广的 胸怀、平易近人的处事风格，他是我一生的楷模，他教导我的一切是我一生的 瑰宝。 衷心的感谢我的同学们，与他们交流、讨论及他们为我提供的诸多支持和 帮助使我受益匪浅。 感谢我的父母、丈夫和女儿，他们的支持使我能够安心地完成学业，他们 的关心爱护使我能够踏实、认真地走好人生的每一步。 感谢我的工作单位给我这么一个学习的机会! 作者：金萍 2 0 0 8 年1 1 月l6 日 第一章绪论 1 1数据挖掘 随着数字时代的来临，网络技术、数据库技术迅速发展，数据库管理系统 得到广泛应用，数据库中的数据量急剧增加，人们对数据库的应用已经不再仅 仅满足对数据库进行查询和检索，而是希望能够了解隐藏在海量数据下面对决 策支持有用的模式。数据挖掘( 又称为数据库中的知识发现) 技术便应运而生。 目前数据挖掘技术广泛地应用于市场分析、医疗卫生和科学研究等领域，并且 取得了可观的经济效益和社会效益。 所谓的数据挖掘( d a t am i n i n g ) 就是从大量的、不完全的、有噪声的、模糊 的、随机的实际应用数据中提取出可信的、新颖的、有效的并能够被人们理解 的模式的高级处理过程。这种处理过程包括数据准备、数据挖掘、模式评估与 解释，巩固知识和运用知识五个阶段。其中数据挖掘关键步骤，是对海量数据 中隐藏的特征和趋势进行分析的重要手段。数据挖掘的质量对人类理解数据有 着重要的影响，而数据挖掘的质量受到采用数据挖掘技术的有效性和数据挖掘 所处理的数据的质量及规模这两个重要的因素的影响。 当前数据挖掘领域已经成为国内外研究的重点，大量的关于数据挖掘领域 的前沿知识和相关技术都会出现在著名k d d 、v l d b ( v e r yl a r g ed a t ab a s e ) 、 p a k d d ( p a c i f i c a s i a nk n o w l e d g ed i s c o v e r yd a t a ) 等国际会议中。而国内的研究 更是如火如茶：1 9 9 3 年国家自然科学基金首次支持该领域的研究项目。目前， 国内的许多科研单位和高等院校竞相开展知识发现的基础理论及其应用研究。 最近，业内的一次高级技术调查将数据挖掘和人工智能列为“未来三到五年内 将对工业产生深远影响的五大关键技术 之首，并且还将并行处理体系和数据 挖掘列为未来五年内投资焦点的十大新兴技术前两位。目前世界上比较有影响 的典型数据挖掘系统有：s a s 公司的e n t e r p r i s em i n e r 、i b m 公司的i n t e l l i g e n t m i n e r 、s g i 公司的s e t m i n e r 、s p s s 公司的c l e m e n t i n e 、s y b a s e 公司的w a r e h o u s e s t u d i o 、r u l e q u e s tr e s e a r c h 公司的s e e 5 、还有c o v e r s t o r y 、e x p l o r a 、k n o w l e d g e d i s c o v e r yw o r k b e n c h 、d b m i n e r 、q u e s t 等。还可以访问丛! p ；堕型堕：鱼丛垒婴i 望i 坠g ! 垒垫 c o m 网站，该网站提供了许多数据挖掘系统和工具的性能测试报告。数据挖掘 技术从一开始就是面向应用的。目前在很多领域，数据挖掘都是一个很时髦的 词，尤其是在如银行、电信、保险、交通、零售( 如超级市场) 等商业领域。数 据挖掘所能解决的典型商业问题包括：数据库营销( d a t a b a s em a r k e t i n g ) 、客户 群体划分( c u s t o m e rs e g m e n t a t i o n & c l a s s i f i c a t i o n ) 、背景分析( p r o n l e a n a l y s i s ) 、 交叉销售( c r o s s s e l l i n g ) 等市场分析行为，以及客户流失性分析( c h u r na n a l y s i s ) 、 客户信用记分( c r e d i ts c o r i n g ) 、欺诈发现( f r a u dd e t e c t i o n ) 等等。 1 2 聚类算法的研究与比较 聚类分析作为发现数据分割及模型信息的数据挖掘技术，在海量数据统计、 网络分析及医学图形自动检测等领域具有广泛地应用背景。聚类分析根据数据 的内在特性将数据划分到不同的簇( 或组) 中，使得同簇中的元素尽可能地相似， 而不同簇中的元素尽可能地相异。关于聚类分析的最新研究进展参见文献 【1 1 4 】。现有的聚类算法可以分成以下几类：划分方法( 如k m e a n s ”】、p a m l 6 1 、 c l a r a n s t l 7 , 1 8 】、e m 1 9 , 2 0 ) ；层次方法( 如c h a m e l e o n l 2 1 1 、b r i c h l 2 2 1 、c u r e 2 引、 p d d p 2 4 1 ) ；基于网格方法( w a v e c l u s t e r 2 5 1 、s t i n g t 26 1 、c l i q u e 2 7 1 ) ；基于密度 方法( 如d b s c a n 2 8 - 3 、o p t i c s 32 1 、d e n c l u e t 3 3 1 ) 等。划分方法是一类应用十 分广泛的聚类算法，该算法试图发现数据集的k 个子簇，使得每个子簇的误差 函数最小，因此它又是典型的组合优化问题。研究者们提出了很多启发式方法 设计划分聚类算法。启发式算法具有快速获得聚类结果的优点，但是同时也不 可避免地受到大量局部极小值的影响，从而无法获得较高的聚类结果。同时这 些算法都是在问题不变的情况下对固定位置上的数据对象进行聚类，从这个角 度来看，本文称这些算法为静态算法。 当我们处理具有大量信息的复杂问题时，通常会从问题的一般特性出发， 获得问题的概要，然后再对问题的细节进行评价，得到问题的真正答案。就好 比我们观察远处物体一样。刚开始，由于受到距离和视觉失真等因素的影响， 我们仅仅观察到物体的大概轮廓。但是，我们仍然可以从这个轮廓中得到物体 的一些信息，比如物体的大概尺寸、颜色；物体是静止的还是运动的；物体是 死的还是活的等概要。如果此时让我们确定这个物体到底是什么，可能会得到 错误的答案，但是我们却有了比较接近的选择范围。随着距离的减少，物体的 更多细节信息变的越来越明显。最后，当所有的失真和偏差都移除时，我们可 以知道这个物体到底是什么了。这种观察形式是建立在一系列逐步精化的近似 学习的基础上的，我们称之为调整学习。调整学习概念起源于神经网络模型的 训练应用，逐渐发展成为提高组合优化启发式算法质量的重要方法。目前该方 法被成功地应用于t s p 问题的求解中。为了提高聚类质量本文将逐步求精的调 整学习思想引入到聚类算法设计中。逐步求精调整学习通过调用一个设计合理 的调整算子，构造原始搜索空间的一系列不同粒度的搜索空间。细粒度搜索空 间中大量的局部最优解被“填平 ，从而降低了局部最优解对搜索算法的影响。 在细粒度搜索空间中执行搜索算法获得的解作为粗粒度搜索空间搜索算法的输 入，引导搜索算法产生新的搜索结果。如此继续直到恢复到原始搜索空间。在 逐步求精思想的驱动下，本文给出了聚类算法框架c a t - l ( c l u s t e r i n ga l g o r i t h m b a s e do nf i n e t u n i n gl e a r n i n g ) ，并设计了适合处理聚类问题的噪声平滑调整算 子。最后在框架c a t - l 的支持下，以经典的f c m 算法和c l a r a n s 算法为从 属聚类算法，利用调整学习思想提高这两种算法的聚类质量。在多组仿真和实 2 际数据集上的实验结果显示，改进算法的聚类质量远远高于原算法的聚类质量。 1 3本文结构 第二章首先详细地介绍聚类技术的概念、数据的存储形式、相异度计算方 法、数据挖掘对聚类分析的基本要求，最后详细地介绍和比较了国内外研究者 们提出的若干类聚类算法；第三章介绍基于调整学习思想的聚类算法c a t - l 的 产生背景、基本思想、算法框架及两种调整算子的设计；第四章着重阐述了分 别以经典的f c m 算法、c l a r a n s 算法作为c a t - l 框架的从属聚类算法的实 验结果及相关分析。本文最后总结全文并指出下一步的研究方向。 3 第二章聚类分析技术 2 1 聚类分析中的数据类型 假设要聚类的数据集合包含 个数据对象，这些数据对象可能是人、房子、 文档、国家等。许多基于内存的聚类算法选择以下两种数据结构。 2 1 1 数据矩阵 数据矩阵又称为对象与变量结构，它采用p 个变量( 也称为度量或属性) 表 示刀个数据对象，例如用年龄、身高、体重、性别等表示对象人。这种数据结 构是关系表的形式，或者将其看作成p i 的矩阵( 如公式2 1 所示) 。由于矩阵 的行列分别表示不同的实体，因此该矩阵又被称为二模矩阵。 x l1x 1 2 x l 疗 x 2 1x 2 2 x 2 n x p 1 x p 2 x p n ( 2 1 ) ( 2 2 ) 2 1 2 相异度矩阵 相异度矩阵( d i s s i m i l a r i t ym a t r i x ) 又称为对象对象结构，用来存储刀个对象 两两之间的近似性，其表现形式为一个f i xn 的矩阵( 如公式2 2 所示) 。由于该矩 阵的行列存储同一个实体，因此又被称为单模矩阵。其中d ( i ，) 表示的是对象f 和对象，之间的相异度的非负量化表示，当对象i 与对象，相似或接近时 d ( i ，) = 0 ，当两个对象之间越不相似时d ( i ，) 的值越大。许多聚类算法就是在这 种数据结构的基础上对数据对象进行聚类处理的。 2 2相异度的计算方法 聚类是通过对象之间的相异度来确定数据对象之间是否相似的。在聚类分 析中的数据对象是采用属性值来描述的，不同描述的属性其相异度计算方法是 不同的。下面给出几种聚类分析中常用的相异度计算方法。 2 2 1区间变量及其相异度 区间变量是一个粗略线性标度的连续度量。例如重量、高度、经度和纬度 坐标以及大气温度等。 4 0 、j 2 0 ，、 j ，、j il ， ， o 2 玎 lk d d 假设有行个对象，描述第f 个对象的m 个属性值分别对应于区间变量值 x i 。，x i 2 ，描述第个对象的m 个属性值分别对应于区间变量值x ，l ，x f 2 ，x j 。， f ，j o ，l ，m ) ，那么对象i 和对象。，之间的相异度一般采用它们之间的距离 d ( i ，j ) 来表示。d ( i ，j ) 值越小，说明对象i 和对象越相似，差异越小；d ( i ，j ) 值 越大，说明对象i 和对象，越不相似，差异越大。 距离d ( i ，) 的计算主要有如下三种方法： ( 1 ) e u c l i d e a n 距离 e u c l i d e a n 距离是比较常用的距离计算方法。其具体计算方法为： d ( i ，) = i 薯l x j 。1 2 + i 一2 一x j ：1 2 + + i 。一x j 珊1 2 f ，je 1 ，2 ，z ( 2 3 ) ( 2 ) m a n h a t t a n 距离 m a n h a t t a n 距离采用绝对距离方式来表示数据对象之间的相异度，其具体 的计算方法为： d ( i ，j ) 爿x i i x j li + ix i 2 一x ，2l + + i 一x ，。l，j l ，2 ，m ) ( 2 4 ) ( 3 ) m i n k o w s k i 距离 m i n k o w s k i 距离是e u c l i d e a n 距离和m a n h a t t a n 距离的概化，它的定义如下： d ( i ，j ) = ( i 薯l x j li q + ix i 2 一x ，21 9 + + i 一x ，m1 9 ) 9 ， 1 ，2 ，m ( 2 。5 ) 其中g 为一个正整数，当q = 2 时表示e u c l i d e a n 距离，当q = 1 时表示 m a n h a t t a n 距离。不论采用上述哪种计算方法，区间变量的度量单位的选择对 聚类结果都有直接的影响。例如，将高度的度量单位由米改成英寸，将会得到 完全不同的聚类。一般来说，小度量单位会增大变量的值域，对聚类结果的影 响也就越大。为了避免度量单位选择对聚类质量的影响，数据在聚类之前应当 进行标准化。给定一个变量厂的度量值，可以对其进行下面的操作从而得到标 准化的度量值。 计算平均的绝对偏差s ， 孓= 吉( i 五，一m fi 十l 而一，i + + fx s m 厂i ) ( 2 6 ) 其中i l l , x 2r ，x i 为变量的刀个度量值，m ，是的平均值，即 m f - 吉( x l f + x 2 ，+ + h ) 。 计算标准化的度量值或z s c o r e z g = ( 砑一班r ) s r ( 2 7 ) 2 2 2二态变量及其相异度 二态变量是指只能有两种取值的变量，用1 表示变量存在，而用o 表示变 量不存在。一般情况下，二态变量不能采用适合区间变量的相异度计算方法。 假设有玎个对象，描述每个对象的m 个属性值都是二态变量，那么计算对 象i 和对象之间的相异度通过以下两个步骤来完成： ( 1 ) 统计二态变量的取值 对n 个数据对象的二态变量进行统计，用二维表格的方式表示如下( 表2 1 ) ： t a b l e 2 1b i n a r yv a r i a b l es t a t i s t i c s 表2 1 二态变量统计表 对象_ ， 对 象 i 1 0 求 l 9 s g + s o ， f ，- + t ( 2 ) 计算对象间的相异度 二态变量根据其状态的等价程度可以分为对称和不对称二态变量。如果二 态变量的两个状态是同等价值的，并具有相同的权值，则称该二元变量为对称 的，即两个取值0 或1 没有优先权。例如，属性“性别 有两个值：“男 、“女 。 基于对称二元变量的相似度称为恒定的相似度，一般采用简单匹配系数表示对 象之间的相异度。其计算公式如下： d ( i ，j ) = ( ，+ s ) ( g + ，+ s + f ) = ( 厂+ s ) p ( 2 8 ) 如果二态变量的两个状态不是同等价值的，则称该二元变量为非对称的， 例如疾病检查的肯定和否定的结果、产品检验的合格和不合格等，我们更关注 其中的一个取值，并将该值定义为1 ，另一个取值定义为0 。基于非对称二元变 量的相似度称为非恒定的相似度，一般采用著名的j a c c a r d 系数表示数据对象 之间的相异度，其计算公式如下： d ( i ，j ) = ( ，+ s ) ( g + ，+ s ) ( 2 9 ) 其中，和，同时取0 的情况被认为是不重要的，因此相应的统计值t 被忽略 不计。 2 2 3标称型、序数型和比例标度型变量及其相异度 ( 1 ) 标称型变量 标称变量是二元变量的推广，它具有多于两个的状态值。假设一个标称型 变量的状态数目为m ，这些状态可以用字母、符号或数字表示。两个对象i 和 对象，之间的相异度可以用简单匹配方法来计算： d ( i ，) = ( p - m ) p ( 2 10 ) 其中m 是匹配的数目，即对象，和对象，取相同的变量的数目，p 是全部变 量的数目。 ( 2 ) 序数型变量 序数型变量分为离散的序数型变量和连续的序数型变量，离散的序数型变 6 黧冀 量与标称型变量类似，它有一组有序的状态值表示；而连续的序数型变量是一 个未知标度的连续数据的集合，它关注的是数据之间的顺序而不是数据值。一 个序数型变量的值可以映射为秩，例如，假设一个变量厂有膨，个状态，这些有 序的状态定义了一个排列1 ，2 ，m ，。 假设厂是描述刀个数据对象的一组序数型变量之一，第f 个对象的厂值为 b ，变量厂有个m ，有序状态，关于厂的相异度计算包括如下步骤：首先用对 应的秩，代替置，；然后利用公式( 2 7 ) 对数据值进行标准化处理；最后再利用欧 氏几何空间的任何距离公式计算对象i 和对象，之间的相异度。 ( 3 ) 比例标度型变量 比例标度型变量在非线性的标度取正的度量值，近似地遵循如下公式： 么p 研或4 e 一历 ( 2 1 1 ) 比例标度变量的一般采用与区间标度变量同样的方法来计算相异度。 2 2 4混合型变量及其相异度 以上叙述的几种度量方式是基于这样一个假设的，即所有属性的取值都为 一种数据类型，并且所有属性的取值处于同等重要的地位( 不对称二态变量除 外) ，具有同样的权重。在实际应用中，这种假设往往是不成立的，处理的数据 对象通常是由多种不同类型的属性描述，且其重要程度也不相同。混合型变量 的相异度计算不能简单地采用上述方式进行计算，一般情况下可以有两种处理 方式： ( 1 ) 类型分组、单独聚类 将变量按照属性的类型不同进行分组，对每种类型的变量进行单独的聚类。 这种方法虽然降低了问题规模并可以单独采用某种已知的相异度计算方法来计 算相异度，但是不能保证不同类型变量的聚类结果兼容，从而导致聚类分析失 败。 ( 2 ) 统一处理、一次聚类 将所有的变量一起处理，只进行一次聚类分析。标准化不同类型的变量并 将它们组合到单个相异度矩阵中。 假设有，z 个对象描述每个对象的m 个属性值为区间变量或二态变量，对于 对象而，吒，吒，描述其第七个属性的变量值分别为x a 七，吃，则对象f 和对 象，之间的相异度d ( i ，j ) 可以采用下面的公式计算： d ( i ，歹) = ：，秽谬：。岛 ( 2 1 2 ) 其中： 西幻：o 如果属性宓是不对称的，且稚2 靠2 0。 i1 其他情况 7 巩) = 上生二生如果属性七为区间变量，其中办= l 甩) m a x hx h k m l n hx h k 、。 0 如果属性k 为二态变量，且x ，k = 泓 1 如果属性k 为二态变量，且x ，k x j k 秽代表的是各个属性标准化后的对象f 和对象在第后个属性上的距离。彭表 示第七个属性对计算对象f 和对象之间距离的影响。从苗的取值可以看出， 当属性的取值类型为不对称的二态变量，且对象i 和对象歹在该属性上的取值都 为0 ，则在计算相异度时该属性不予考虑。 2 3数据挖掘对聚类分析的要求 数据聚类是一个富有挑战性的研究领域，它的潜在应用提出了各自特殊的 要求。数据挖掘对聚类的典型要求如下： ( 1 ) 可伸缩性 许多聚类算法在小数量集的处理中能够得到较好的聚类结果，例如：p a m 与c l a r a 。但是实际处理中所要处理的数据集是非常庞大的，在这样的数据 集合样本上进行聚类可能会导致有偏差的结果。因此实际处理中需要具有高度 可伸缩性的聚类算法。 ( 2 ) 处理不同类型属性的能力 目前存在的许多经典算法被设计用来聚类数值类型的数据，但是实际应用 中可能要求聚类其他类型的数据，如二元类型、分类类型或者是混合类型的数 据，这就要求设计的聚类算法能够处理这些数据。 ( 3 ) 发现任意形状 基于欧几里德距离或曼哈坦距离作为度量的聚类算法趋向于发现具有相近 尺度和密度的球状簇。但是实际应用中一个簇的形状可能是任意形状的，因此 提供能够发现任意形状的簇的聚类算法是有重要意义的。 ( 4 ) 最小化输入参数，降低对领域知识的依赖 许多聚类算法都需要用户输入一定量的参数，例如，输入希望得到的聚类 个数等。通常聚类结果对输入的参数很敏感，因此确定算法输入的参数与某个 领域的应用有着密切的关系，算法就不具有普遍性，从而要求聚类算法的设计 者们设计出对参数依赖较小的聚类算法。 ( 5 ) 健壮性和高维性 由于绝大多数现实世界中的数据库都包含了孤立点，空缺值、未知数据或 错误的数据，一些聚类算法对这类数据十分敏感，对这类数据进行聚类可能会 降低聚类质量，因此要求设计对这类数据不敏感的聚类算法来提高聚类质量。 另外，有些聚类算法对输入数据的顺序比较敏感，例如，同一个数据集合以不 8 同的顺序提交给一个算法时，可能会得到完全不同的聚类结果。因此开发对输 入顺序不敏感的聚类算法具有十分重要的意义。高维性是指目前数据库中需要 处理的数据大多是有多个属性组成，针对高维数据进行聚类已经成为一个新的 研究领域，要想从包含大量数据信息的数据库中发掘出有用的信息或模型，需 要开发能够处理高维数据的聚类算法。 ( 6 ) 基于约束的聚类 现实世界的应用可能需要在各种约束条件下进行聚类，要找到既满足特定 约束条件，又具有良好聚类特性的数据分组是一项具有挑战性的任务。 ( 7 ) 可解释性和可用性 用户希望聚类结果是可解释、可理解和可用的，即聚类可能需要特定的语 义解释，并给用户提供一个直观的模型或信息解释。 2 4 主要的聚类算法 目前的文献中存在大量的聚类算法，算法的选择取决于数据的类型、聚类 的目的和应用。从不同的角度看这些算法，可以以不同的标准进行分类。经典 的聚类方法可以分为：划分方法、层次方法、基于密度的方法、基于网格的方 法以及基于模型的方法等。 2 4 1划分方法 给定一个有n 个对象或元组的数据集，划分方法的目的是构建数据集的x 个划分，每个划分表示一个簇( k 刀) ，即它将数据集划分成k 个组，同时满 足以下两个条件：( 1 ) 每个组至少包含一个对象；( 2 ) 每个对象必须属于且只 属于一个组。给定要构建的划分的数目k ，划分方法首先创建一个初始划分， 然后采用迭代的重定位技术，尝试通过对象在划分间移动来改进划分，一个好 的划分的准则是使得在同一个类中的对象之间应该尽可能的相似或相关，而不 同的类之间的对象应该尽可能的相异或不同。该方法的缺点是对于大规模数据 及复杂形状的聚类结果不是很好。 为了达到全局最优，基于划分的聚类会要求穷举所有可能的划分。实际上， 绝大多数应用采用了两个比较流行的启发式算法：( 1 ) k 一平均算法，在该算法 中簇采用簇中对象的平均值来表示。( 2 ) k 中心点，在该算法中簇用接近聚类 中心的一个对象来表示。 ( 1 )k 一平均算法 k 平均算法以k 为参数，把n 个对象分为k 个簇，使簇内具有较高的相似 度，而簇间具有较低的相似度，相似度的计算根据一个簇中对象的平均值( 即簇 的重心) 来进行进行。k 平均算法框架描述见图2 1 。k 平均算法有很多变种， 它们可能在初始k 个平均值的选择、相异度的计算和计算聚类平均值的策略上 9 有所不同。如f a l 3 4 1 、s c s 3 5 1 、k k z 3 6 】、m c q u c e n 【3 7 1 、k + + m e a n s 3 s 1 及k d t r e e 3 9 , 4 0 】 等算法利用多种策略避免了k m e a n s 算法对初始化敏感问题。为了使得 k m e a n s 算法自动定义簇个数k ，l i k a s 等在文献【3 9 】中从k = l 开始执行聚类算 法直到膨次，保留评价函数值最小的结果。而i s o d a t a 则在聚类过程中引入 凝聚和分裂操作达到塞动确定簇个数的目的1 4 1 】。将足平均算法与层次聚类算法 相结合进行聚类得到的聚类质量较高，如b i s e c t i n gk m e a n s 【4 引。 算法：k 一平均算法 输入：簇的数目k 和包含刀个对象的数据集， 输出：便平均误差准则最小的足个簇 1 随机选择k 个对象作为初始的簇重心 2 r e p e a t 2 1 根据簇中对象的平均值，将每个对象( 重 新) 赋予最类似的簇； 2 2 更新簇的平均值，即计算每个簇中对象的 平均值； 3u n t i l 不再发生变化： f i 9 2 1 k 。朋e 口甩s 图2 1k 平均算法 ( 2 ) k 中心点算法 k 中心点算法基本策略：首先为每个簇随机她选择一个代表对象；剩余熬 对象根据其与代表对象的距离分配给最近的一个簇。然后反复地用非代表对象 替代代表对象，以改进聚类的质量。聚类结果的质量用一个代价函数来估计， 该函数度量对象与参照对象之间的平均相异度。为了判断一个非代表对象d 是 否能够替换当前代表对象0 j 对于每个非中心点对象计算它的代价c 肪。在如 下四种情况下c 油被定义为等式2 1 3 2 1 6 ： j 当前隶属于中心点对象q ，如果q 被q 所替换作为中心点，且_ ，离另 一个中心点对象9 ，最近。那么，被重薪分配给o ，。交换代价定义为； c f l h = d ( o j ，o j , 2 ) 一d ( q ，p ) ( 2 13 ) 等式2 1 3 永远是个非负数，这说明在情况中，用非中心点o 。替换d 的代 价小于0 。 ，当前隶属于中心点对象q ，如粲q 被皖所替换作为串心点，且歹离g 最近，那么歹被重新分配给o 。交换代价定义为： c f l h = d ( d ，o h ) - d ( o j ，q ) ( 2 1 4 ) 等式2 1 4 的正负取决于对象，离对象口或d 哪个更近。 当前隶属于中心点对象d 2 ，如果d f 被q 所替换作为中心点，且离 d 2 还是最近，那么对象的隶属关系不变。交换代价定义为： c 洒= 0 ( 2 i s ) j 当前隶属于中心点对象0 f ，2 ，如果q 被q 所替换作为中心点，且j 离q 最