（信号与信息处理专业论文）鲁棒高斯聚类及其在图像分割中的应用.pdf

摘要 作为无监督模式分类的一个重要分支，聚类分析近年来成为研究的热点，在 许多领域被广泛地应用。应当认识到，无论从理论的发展还是实际的应用来看， 算法如果要应用于科学和工程领域中，就必须是鲁棒的。对于聚类分析而言，鲁 棒性的两个重要内涵就是对噪声和外围点的鲁棒性和对于初始化的鲁棒性。 本文研究了基于高斯估计量的鲁棒聚类及其在图像分割中的应用。首先，针 对模糊c 均值聚类算法对于噪声敏感的缺点，将鲁棒统计学引入聚类分析。提出 了基于高斯估计量的鲁棒估计，并发展出能够对类中心实现鲁棒估计的鲁棒高斯 聚类( r g c ) 算法，以及可以检测不同大小类的多分辨鲁棒高斯聚类( m r r g c ) 算法。这些无约束的鲁棒高斯聚类算法体现了良好的对于噪声的鲁棒性。 其次，为了克服可能性聚类和鲁棒聚类对于初始化敏感、易产生“巧合类” 的弱点，将模糊约束引入鲁棒参数估计理论，提出了基于模糊加权的m 估计，并 发展出模糊鲁棒高斯聚类( f r g c ) 算法。进一步放宽加权函数的约束条件，发展 出比例加权鲁棒高斯聚类( p w r g c ) 算法和多分辨比例加权鲁棒高斯聚类 ( m r p 、r g c ) 算法。这类约束型的聚类算法在保留了参数估计的鲁棒性的同时， 体现了良好的划分能力，实现了对噪声鲁棒性和对初始化鲁棒性的统一。 基于高斯估计量的鲁棒聚类算法还被成功地应用于图像分割。较之f c m ，它 们表现了较强的抑制噪声和处理局部信息的的能力。 关键词：鲁棒聚类m 估计量高斯估计量多分辨图像分割 a b s t r a c t a sa ni m p o r t a n tb r a n c ho fu n s u p e r v i s e dp a t t e r nc l a s s i f i c a t i o n ，c l u s t e r i n ga n a l y s i s h a sd r a w nm u c hm o r ea t t e n t i o nr e c e n t l y , a n dh a sb e e nw i d e l yu s e di nm a n yf i e l d s i t s h o u l db ea l s on o t e dt h a ta l g o r i t h m sm u s tb er o b u s t ，w h e t h e rf r o mt h ep o i n to fv i e wo f t h e o r yd e v e l o p m e n to rp r a c t i c a la p p l i c a t i o n f o rc l u s t e r i n ga n a l y s i s ，t w oi m p o r t a n t m e a n i n g so fr o b u s t n e s sa r et h a ta l g o r i t h m ss h o u l db er o b u s tt o n o i s ea n dr o b u s tt o i n i t i a l i z a t i o n g a u s s i a ne s t i m a t o rb a s e dr o b u s tc l u s t e r i n ga l g o r i t h m sw i t ha p p l i c a t i o n si ni m a g e s e g m e n t a t i o na r es t u d i e d i nt h i s t h e s i s f i r s t l y , t oo v e r c o m et h en o i s es e n s i t i v i t yo f f u z z ycm e a n s ( f c m ) ，r o b u s t s t a t i s t i c si si n t r o d u c e di n t oc l u s t e r i n ga n a l y s i st od e v e l o p r o b u s tg a u s s i a ne s t i m a t o r ，b a s e d o nw h i c hr o b u s t g a u s s i a n c l u s t e r i n g ( r g c ) a l g o r i t h ma n dm u l t i r e s o l u t i o nr o b u s tg a u s s i a nc l u s t e r i n g ( m r r g c ) a l g o r i t h ma r e p r o p o s e d r g cc a na c h i e v er o b u s te s t i m a t i o no fc l u s t e rc e n t e r s ，w h i l em r r g cc a n a l s od e t e c tc l u s t e r sw i t hv a r i o u ss i z e s t h e s eu n s t r a i n e dr o b u s tg a u s s i a n c l u s t e r i n g a l g o r i t h m se x h i b i th i g h r o b u s t n e s st on o i s e s e c o n d l y , d u e t ot h ei n i t i a l i z a t i o n s e n s i t i v i t y a n dt h e t e n d e n c y t o p r o d u c e c o i n c i d e n tc l u s t e r sf o rp o s s i b i l i s t i co rr o b u s tc l u s t e r i n g ，f u z z yc o n s t r a i n ti si n t r o d u c e d i n t or o b u s te s t i m a t i o nt h e o r yt od e v e l o pf u z z yw e i g h t e dm e s t i m a t o r ，b a s e do nw h i c h f u z z yr o b u s tg a u s s i a nc l u s t e r i n g ( f r g c ) a l g o r i t h mi sp r e s e n t e d f u r t h e rr e l a x a t i o no f t h ec o n s t r a i n t so nw e i g h t e df u n c t i o n y i e l d sp r o p o r t i o nw e i g h t e dr o b u s tg a u s s i a n c l u s t e r i n g ( p w r g c ) a l g o r i t h ma n dm u l t i - r e s o l u t i o np r o p o r t i o nw e i g h t e dr o b u s t g a u s s i a n c l u s t e r i n g ( m r p w r g c ) a l g o r i t h m 。t h e s ec l u s t e r i n g a l g o r i t h m s w i t h c o n s t r a i n t se x h i b i t g o o dp a r t i t i o na b i l i t y w h i l e p r e s e r v i n g r o b u s te s t i m a t i o no f p a r a m e t e r s t h e r o b u s t n e s st on o i s ea n dt o i n i t i a l i z a t i o nc a nb ea c h i e v e d s i m u l t a n e o u s l y g a u s s i a ne s t i m a t o rb a s e dr o b u s tc l u s t e r i n ga l g o r i t h m sa r ea l s o a p p l i e di ni m a g e s e g m e n t a t i o n c o m p a r e d t of c m ，t h e ye x h i b i t g o o da b i l i t yt os u p p r e s sn o i s ea n d t od e a l w i t hl o c a li n f o r m a t i o n k e y w o r d s ：r o b u s tc l u s t e r i n g m u l t i r e s o l u t i o n me s t i m a t o r g a u s s i a ne s t i m a t o r i m a g es e g m e n t a t i o n 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书丽使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生 在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕业 离校后，发表论文或使用论文工作成果肘署名单位仍然为西安电子科技大学。学 校有权保留送交论文的复印件，允许查阅和借阅论文：学校可以公布的全部或部 分内容，可以允许采用影印、缩印或其它复制手段保存论文， 本人签名： 导师签名： 矽级 龋乌兰每 日期：之：! 扯幽 日期：迎幺：厶： 第一章绪论 第一章绪论 本章主要介绍了本文研究的背景和意义，概述了聚类分析的理论以及鲁棒聚 类算法的研究进展，列举了聚类分析在图像分割中的应用，最后给出了全文的内 容安排。 ? 1 1 研究背景及意义 模式识别诞生于2 0 世纪2 0 年代，随着4 0 年代计算机的出现，5 0 年代人工智 能的兴起，模式识别在6 0 年代初迅速发展成一门学科。它所研究的理论和方法在 很多科学和技术领域得到了广泛的重视，推动了人工智能系统的发展，扩大了计 算机应用的领域，在向人类智能逼近这一永恒的前沿课题中占有一席之地。可以 说，在高度自动化的今天，模式识别几乎已经进入人类生活的各个领域【6 7 】。 人们为了掌握客观事物，需要将事物按相似的程度组成类别。形象地说，模 式识别就是从待识别的对象中分辨出哪个对象与标本相同或相似，从而正确地将 它们进行分类，把相似而又不完全相同的对象分为一类。可见，分类是建立和识 别模型的重要基础和手段，模式识别与分类是密切相关的 7 4 】。此外，任何一门学 科都要通过分类来建立自己的概念，也要通过分类来发现和总结规律。因此，作 为一种强有力的工具，分类的研究具有十分重要的指导作用。 模式识别又常称为模式分类，从处理问题的性质和解决问题的方法等角度， 模式分类可以分为有监督模式分类和无监督模式分类。其中，有监督模式分类是 指已知某些样本的分类情况，用这些已知样本对分类系统进行学习( 训练) ，使得分 类系统能够对这些已知样本正确分类，然后用已学习好的分类系统对未知样本进 行分类。可见监督分类需要知道学习样本足够多的先验知识。而要做到这一点， 往往要付出相当大的代价。 与有监督分类相对应的是无监督分类，它不需要知道样本的先验知识，也不 需要获取训练样本，通常符合实际的应用要求，因而对无监督模式分类的研究受 到越来越多的重视。聚类分析，作为无监督分类的主要工具，是模式识别这- i i 沿课题的重要组成部分，己经被广泛地应用于其它学科领域和各种工程应用中。 而将各种新技术应用到聚类分析中的方法也层出不穷1 1 1 , 2 , 3 , 4 l 。d u b e s 和j a i n 关于聚 类分析的综述包括了从7 7 份杂志和4 0 本书中摘取地2 5 0 条引文m 】，如此巨大的 文献量说明了聚类分析的重要性和交叉学科性，也足以说明它的发展及应用前景 的广阔性。 鲁棒高斯聚类及其在图像分割中的应用 同时，各种聚类算法已经在许多领域得到了广泛的应用。在图像处理中被用 于图像分割5 , 6 9 , 7 1 , 7 3 】，图像增强1 6 】，图像压缩【7 1 、图像平滑、图像匹配【4 5 l 。在模 式识别中，被用于语音识别【8 1 ，雷达目标识别”。此外，还可以用于模糊推理规则 的建立1 9 1 ，医学诊断等。其中，关于图像分割中的应用将在1 4 节重点介绍。 无论从理论的发展还是实际的应用来看，算法如果要应用于科学和工程领域 中，就必须是鲁棒的。所谓鲁棒性正是要求分布模型的小的偏差不应当对方法的 性能产生显著的负面影响，且方法能够在样本的分布受到噪声和外围点的影响下 仍然有效【圳。因此，将鲁棒统计学引入聚类分析，提高聚类算法的鲁棒性或顽健 性，不仅具有重要的理论价值，还具有实际的应用意义。同时对于其它学科的发 展和应用也具有很强的指导作用。本文的研究正是在这一背景之下诞生的。我们 希望这一研究能够推动鲁棒统计学在聚类算法中的应用以及聚类分析中的模糊集 理论、可能性理论在鲁棒统计学中的延伸，并对聚类图像分割这一应用性极强的 自动化技术起到积极的促进作用。 1 2 聚类分析简介 作为非监督识别的一个重要分支，聚类分析试图根据数据集的内部结构将特 征空间中一组没有类别标记的样本按某种相似性准则划分到若干个子类中，使得 在同一类的样本尽可能的相似，在不同类的样本尽可能不相似。在这一过程中， 没有先验知识和教师的指导，因此从这个意义上讲，聚类又称为无监督分类。从 隶属度的取值形式来看，现有的聚类分析算法大体上分为硬聚类方法、模糊聚类 方法和可能性聚类方法。 硬聚类方法将样本对各个类的隶属度取成0 和l 两种值，取值为0 表示该样 本不属于这一类，取值为l 表示该样本属于这一类。样本只能属于所有类别中的 某一个类别，其隶属度只能取0 或l 。早期的聚类算法都是硬聚类算法口7 1 。硬聚类 算法容易陷入局部极值【1 3 】。 模糊聚类方法所得的分类结果仍旧用样本对各个类的隶属度表示，只是其取 值范围扩展到区间 o ，l 】，样本对所有类别的隶属度之和为l 。该类方法是基于z a d e h 在1 9 6 5 年提出的模糊集理论【3 8 】，兼顾到样本与样本之间的联系，认为每一样本与 各个聚类中心都有一个隶属关系。相对于硬聚类算法，模糊聚类算法能够有效的 对类与类间有交叉的数据集进行聚类，提高了算法的寻优概率，但其收敛速度则 要慢的多。模糊聚类算法的典型代表就是模糊c 均值( f c m ) 1 3 1 ，对于f c m 型 的模糊聚类算法而言，其最大的缺点就是对于噪声和外围点的敏感性。 为了克服噪声和外围点对于聚类结果的影响，具有鲁棒统计特征的聚类算法 相继提出i l 。鲁棒统计学和模糊集理论是最近几十年里独立发展起来的两个学科。 第一章绪论 然而，它们却有相当大的一致性。特别是从鲁棒统计学中的加权函数的概念来看， 它类似于模糊集理论中的隶属度函数，或可能性理论中可能性分布的隶属度函数。 从隶属度的取值方式来看，鲁棒聚类与模糊聚类和可能性聚类相互交叉。它们都 是对于模型的一种“软”判别或参数的“软”估计。因此将鲁棒统计特征引入聚 类分析，更好地改善模糊聚类算法对于外围点和噪声的敏感性问题，成为研究的 重点之一。 1 3 鲁棒聚类算法的发展概况 算法如果要应用于科学和工程领域中，就必须是鲁棒的。鲁棒性的一个重要 内涵就是指分布模型的小的偏差不应当对算法性能产生显著的负面影响。对聚类 分析而言，我们希望算法在数据集的分布受到噪声和外围点的影响下仍能有效， 即具有鲁棒性。这也正是鲁棒统计学应用于聚类分析的一个重要的理论背景。 如前所述，对于f c m 型的模糊聚类算法而言，其最大的缺点就是对于噪声和 外围点的敏感性，这是因为其隶属度的约束方案使得噪声和外围点仍能被分配相 对较高的隶属度值，从而影响聚类的参数估计。具有鲁棒统计特征的聚类算法由 于其加权函数的鲁棒性，使得噪声和外围点对于参数估计的影响得到了有效的控 制，从而成功地应用到模式识别、计算机视觉、工业控制等科学和工程领域中。 在这里我们对鲁棒聚类算法的发展作一简单的概括。 在一篇未发表的会议文章中【3 9 】，o h a s h i 最早尝试改善f c m 型算法对于噪声的 敏感性问题。他将外围点看作一类，通过修改f c m 的目标函数的方法以达到“鲁 棒”f c m 的目的。 d a v 6 在1 4 0 j 中独立的提出噪声聚类( n c ) 方法，引入了噪声类的概念以处理噪 声数据。通过参数替换，n c 法与上面的方法具有相同的目标函数形式。这两种方 法在一定程度上抑制了噪声的影响，提高了基于原型算法的鲁棒性。但其隶属度 仍是依赖于各类相对位置的相对数。 1 9 9 3 年，k r i s h n a p u r a m 和k e l l e r 提出了可能性c 均值( p c m ) 聚类以克服f c m 的隶属度相对数问题m 】。在该算法中，隶属度代表了特征点或特征向量属于各类 的可能性或典型程度，不再有概率约束，因而是绝对数范畴。因而噪声和外围点 不再被赋予较高的隶属度值，从而对参数估计的影响大大降低。因为采用不同的 “带宽”，可能性聚类能够检测不同体积的类。但因为没有概率约束，p c m 对于初 始化较敏感，在图像分割中极易产生“巧合类”现象i ，对此，第三章和第四章 将有进一步的详细论述。 在1 9 9 7 年的一篇经典论文【1 4 j 中，d a v 6 探讨了m 估计量与模糊聚类的关系， 建立了模糊集理论和鲁棒统计学的联系，同时对己有的具有鲁棒统计特征的聚类 鲁棒高斯聚类及其在图像分割中的应用 算法做了评价和比较，引起了人们对于鲁棒聚类特别是鲁棒统计学在聚类分析中 的应用的关注。 同年，在f r i g u i 的博士论文 4 q 中，他对已有的鲁棒统计方法做了比较详细的 介绍，如计算简单，但鲁棒性不够的m 、w 、l 估计量【3 6 l ，鲁棒性较强的最小均 方值法【4 2 1 ，计算复杂的最小体积椭球( m v e ) 法【4 3 1 ，可以自动确定类数的广义最小 体积椭球( g m v e ) 法1 2 0 】等。指出同时实现c 类原型的鲁棒估计即构成了基于原型的 聚类；并提出了鲁棒c 原型( r c p ) 法以克服噪声和外围点的敏感性及竞争凝聚( c a ) 法以确定最优类数等。 此后，很多具有鲁棒统计特征的聚类算法相继提出【2 5 1 ，极大地推动了鲁棒 聚类算法的发展以及鲁棒统计学的应用。 1 4 聚类分析在图像分割中的应用 图像处理是计算机视觉的重要组成部分，由于人眼视觉的主观性使图像适合 用“软判决”手段处理，而训练样本图像的匮乏又需要无监督分析。聚类分析正 好满足这两方面的要求，因此成为图像处理中一个强大的分析工具。 聚类分析在图像处理中最为广泛的应用为图像分割，由于分割问题可以等效 为象素的无监督分类，因此早在7 9 年c o l e m a n 和a n d r e w s 就提出用聚类算法做图 像分割i 4 6 ) 。聚类方法运用于图像分割问题在这3 0 年里不断深化和再认识，其潜在 的工程作用至今仍然具有深远的意义。这里我们列举几个突出的应用实例。 s c h a c h t e r 等人于1 9 7 9 年提出了用局部特征聚类的方法来分割灰度图像【4 8 】，这 篇文章强调的是对每个象素的如何合理地选取特征，而不是选择聚类方法。同 时也提出了可以将图像平面坐标( 空间信息) 作为附加特征引入基于聚类的图像 分割中。 1 9 8 8 年，s i l v e m a a n 和c o o p e r 将凝块聚类应用于图像分割t 4 9 1 ，以无监督地学 习图像模型系数矢量。w u 和l e a h y 也描述了网络流原理在无监督分类中的应用( 5 ， 产生了一种新的划分型聚类算法。 1 9 9 4 年v i n o d 等人设计两个神经网络的组合以进行模式分类1 5 ”。在这两个网 络中，图像的直方图用来加权模式对于原型中心“贡献”程度。因此，相对于一 些模式分类中的参数型密度函数而言，该算法表现出相对很强的鲁棒性。这一算 法也在彩色图像的分割中键到了验证。 j o l i o n 在 2 0 】中提出了一种通过识别超椭球体区域的方法依次从输入模式中提 取类的聚类方法。这一技术被成功地用来进行图像的多阈值选取，但较高的计算 量仍然是这一算法的最大问题。 聚类技术还被成功地应用于深度图像的分割。h o f f m a n 和j a i n 设计了一个深 第一章绪论 度图像分割系统f 5 甜，它在一个六维特征空问中采用均方误差型的聚类方法。随后， f l y n i l 和j a i n 继续发展了这种方法1 5 3 1 ，将其纳入深度图像分割的系统比较方法中。 它可能是最有效的深度图像分割方法之一，并在绝大多少深度图像的分割测试上 获得了成功。 纹理图像的分割一直是研究者的兴趣之一。有很多不同的纹理模型和图像操 作算子运用到图像分割中，n g u y e n 和c o h e n 将图像表示成两个马尔可夫随机场的 谱系结构1 5 ”，从每个图像块中获得一些简单的统计特征以形成特征矢量。然后利 用模糊c 均值方法聚类这些块。此外， 5 5 6 0 等都对纹理图像的分割进行了有益 的尝试。 在医学影像处理中，聚类技术也发挥了重要的作用。由于医学图像具有的极 其繁杂的多样性和负责性，加之目前医学影像设备( c t 、m r j 、p e t 等) 成像技 术上的特定，使得医学图像存在一定的噪声，图像中目标物体部分边缘也有可能 局部不清晰，使得医学图像的分割更加困难。h a l l 对神经网络和模糊聚类技术在 核磁共振图像分割中的应用做了综述和比较【4 ”。如何发展能够克服噪声影响、适 合医学图像分割的聚类方法，具有相当的实用价值。 此后又涌现出如基于二维直方图【6 9 1 、塔型结构6 ”、小波分析【6 2 、分形分维 6 3 】、 空间约束、可能性理论 2 3 i 和有效性指导【6 5 l 等一系列新型的聚类分割方法。在彩 色图俐7 0 , 7 1 1 、序列图像以及航空遥感图像等分割方面也获得了很大的进展。 1 5 本文的主要工作及内容安排 本文对基于高斯估计量的鲁棒聚类算法的理论及其在图像分割中的应用作了 较为系统的研究。研究工作主要分为三部分：第一部分研究无约束的鲁棒高斯聚 类算法，并给出了多分辨率的实现方案；第二部分研究基于约束加权的鲁棒高斯 聚类方法，包括模糊加权鲁棒高斯聚类算法和比例加权鲁棒高斯聚类算法；第三 部分研究鲁棒高斯聚类算法在图像分割中的应用。具体内容安排如下： 第一章：介绍了聚类分析包括鲁棒聚类的研究背景和意义，聚类分析的概念、 鲁棒聚类算法的发展概况，聚类分析在图像分割中的应用。并对本文的内容做了 安排。 第二章；研究无约束的鲁棒高斯聚类算法。针对模糊c 均值聚类( f c m ) 算 法对噪声敏感的缺点，将鲁棒统计学引入聚类分析，提出了基于高斯估计量的鲁 棒估计。并发展出能够对类中心实现鲁棒估计的鲁棒高斯聚类( r g c ) 算法，以 及可以检测不同大小类的多分辨鲁棒高斯聚类( m r r g c ) 算法。 第三章：研究基于约束加权的鲁棒商斯聚类方法。针对可能性c 均值对于初 始化敏感，易产生“巧合类”的缺点，将模糊约束引入鲁棒高斯聚类算法，提出 鲁棒高斯聚类及其在图像分割中的应用 了基于模糊加权的m 估计，并发展出模糊鲁棒高斯聚类( f r g c ) 算法。进一步 放宽加权函数的约束条件，发展出比例加权鲁棒高斯聚类( p w r g c ) 算法和多分 辨比例加权鲁棒高斯聚类( m r p w r g c ) 算法。最后对基于高斯估计量的各种聚 类算法的分类性能和参数估计的准确性进行了综合对比和分析。 第四章：将基于高斯估计量的鲁棒聚类算法应用于图像分割。在分析了基于 f c m 的图像分割的缺点以及鲁棒聚类图像分割的可行性的基础上，推导了鲁棒高 斯聚类( r g c ) 和比例加权鲁棒高斯聚类( p w r g c ) 在图像分割中的算法。同对 分析了鲁棒聚类和可能性聚类在图像分割中易产生“巧合类”的根本原因，指出 了解决方案。 在结束语中对全文工作进行总结，并指出了今后的研究方向。 第二章基于高斯估计量的鲁棒聚类 第二章基于高斯估计量的鲁棒聚类 2 1 引言 自从z a d e h 在1 9 6 5 年提出模糊集理论以来，模糊集理论在实际应用中不断发 展和深化，而用模糊的手段处理聚类分析问题也成为本领域研究的主流。r u s p i n i 率先定义了数据集的模糊划分概念，第一个系统地表述和研究了模糊聚类问题。 基于这一概念，人们提出了多种模糊聚类分析方法。而其中受到普遍欢迎的方法 是基于目标函数的模糊聚类方法。 基于目标函数的模糊聚类方法首先是由r u s p i n i 提出的。1 9 7 4 年d u n n 将硬c 均值聚类算法推广到模糊情形，随后，b e z d e k 3 1 将d u n n 的方法一般化，建立了模 糊c 均值聚类理论。由于将聚类问题归结成一个带约束的非线性规划问题，此类 算法可以转化为优化问题而借助经典数学的非线性规划理论求解，并易于计算机 实现。因此随着计算机的发展和实际问题的需要，基于目标函数的模糊聚类方法 逐渐成为聚类分析的主流。 然而就模糊c 均值聚类算法本身而言，仍存在许多不足。它不能解决噪声数 据的聚类问题，也不能合理分配外围点( o u t l i e r ) 的隶属度值，从而导致原型参数 估计的较大偏差。而在实际应用中，数据集通常含有噪声和外围点而假定的模 型或分布也只是对实际的一种近似。因此鲁棒统计学的概念被引入聚类分析，具 有鲁棒统计特征的聚类算法相继提出以克服这一问题。所谓鲁棒性正是要求分布 模型的小的偏差不应当对方法的性能产生显著的负面影响，且方法能够在数据集 的分布受到噪声和外围点的影响下仍然有效。 鲁棒统计学和模糊集理论是最近几十年里独立发展起来的两个学科。然而， 它们却有相当大的一致性。特别是从鲁棒统计学中的加权函数的概念来看，它类 似于模糊集理论中的隶属度函数，或可能性理论中可能性分布的隶属度函数。它 们都是对于模型的一种“软”判别或参数的“软”估计。最典型的代表就是模糊 集理论中，模糊的方法相对与“硬”的方法，更能适应于输入数据中含噪或有模 型偏差的情况。因此将鲁捧统计特红引入聚类分析，更好地改善模糊聚类算法对 于外围点和噪声的敏感性问题，成为研究的重点之一。 本章针对传统f c m 算法对于噪声和外围点的敏感性，研究了鲁棒统计学和聚 类分析的关系。并将一种简单而有效的m 估计量高斯估计量引入聚类分析， 发展出能够实现对类中心鲁棒估计的鲁棒高斯聚类( r c , c ) 算法，以及能够检测 不同大小类的多分辨鲁棒高斯聚类( m r r g c ) 算法。理论研究和仿真试验表明， 鲁棒高斯聚类及其在图像分割中的应用 基于高斯估计量的鲁棒聚类算法具有清晰的数学意义和合理的物理解释，能够有 效地克服噪声和外围点对于参数估计的影响。对含噪数据的聚类结果，它们优于 传统的f c m 算法。 以下，第二节介绍了经典的模糊c 均值( f c m ) 算法并简要分析了它的优缺 点；第三节研究了鲁棒聚类与m 估计量：基于此，第四节、第五节分别给出了鲁 棒高斯聚类算法和多分辨鲁棒高斯聚类算法。并讨论了它们的性能。最后是小结。 2 2 模糊c 均值聚类算法及其分析 在基于目标函数的模糊聚类方法中，由b e z d e k 提出的模糊c 均值( f c m ) 算 法1 1 3 就是一种最常用最引人关注的数据分析方法。很多基于原型的算法都是由 f c m 算法发展而来。c 均值类型的算法最早是从硬聚类目标函数的优化中导出的。 为了借助目标函数法求解聚类问题，人们利用均方逼近理论构造了带约束的非线 性规划函数，从此平方误差和z 成为聚类目标函数的普遍形式。为极小化该目标 函数而采取的p i c a r d 迭代优化方案就是著名的硬c 均值( h c m ) 算法和i s o d a t a ( i t e r a t i v es e l f - o r g a n i z i n g d a t a a n a l y s i s t e c h n i q u e a ) 算法。模糊划分概念提出后， d u n n 首先把类内平方误差和函数，扩展到以一类内加权平方误差和函数，后来 b e z d e k 又引入一个参数m ，把以推广到一个目标函数的无限族 j 。，1 朋 o o ) ， 并给出了交替优化算法，即为人们所熟知的f c m 算法。从此奠定了f c m 算法在 模糊聚类中的地位。下面予以简要介绍。 2 2 1 模糊c 均值聚类算法 给定数据集x = x i 屯，矗) c 为s 维矢量空间中一组有限观测的样本子 集，以= k ，k ，。， r 为观测样本& 的特征矢量或模式矢量，拜为x 中特征 矢量的总数，c 代表类的数目。c n 的矩阵u = 【l d t k 】称为矢量空间x 的约束模糊c 划分，它需要满足以下条件： m 知： u r w l 【 ( 2 - 1 ) 上式中，代表观测样本以属于爿的第i 个模糊子集隶属程度。基于原型的 模糊聚类算法通过最小化下面的目标函数来实现对于数据集的划分： 月c j ( u ，矿) = ( ) “( 以) 2 ( 2 2 ) t i 悻l 式中v = v 。，v ：，v 。 为类中心矩阵，其中v ( i 1 ，c ) 是第i 类的聚类中，心，d 。k 、【，j v一 廿 ” 。h 0 nvl j l 甜 。 tvio 罅 “ 第二章基于高斯估计量的鲁棒聚类 9 表示样本以到聚类中心v j 的距离，j ( u ，v ) 表示各样本到各聚类中心的加权距离平方 和，权重是样本砘对第i 类隶属度的m 次方，m 【1 ，m ) 是模糊因子。当研- - - ) , 1 + 时， f c m 以概率1 退化成h c m ( 硬c 均值) 算法。而当m 斗o o 时，f c m 算法得到的 隶属度均为1 c ，样本隶属于各类的程度相等，使得类分结果太模糊而得到c 个一 样的聚类原型而失去划分特性。 值得注意的是，对于p 维向量坼和v i ，( d i k ) 2 的一般表达式为： ( d m ) 2 = l i x 一v ，1 1 2 = ( x 一v ，) 7 一( x 一v ，) ， ( 2 3 ) 式中，t 表示矩阵的转置，矩阵a 必须为对称正定矩阵。当a = i ( 单位阵) 时， 上式表示为欧式距离。 f c m 算法就是寻求在满足( 2 - 1 ) 式的情况下，使得目标函数( 2 2 ) 最小的最佳对 ( u ，v ) 。j ( o ，v ) 的条件极值可以由拉格朗日乘子法求得。由此得到f c m 算法的迭 代方案： 初始化初始化原型参数y ( ”，设定迭代停止阈值和迭代计数器6 ：0 步骤一用下述公式计算u ( 6 ) 掣2 万1 p 4 ， ( 争) 石 卜v ，= 1 肚 蟛) _ 1 ，且对，r “，) - 0 ( 瑶) 4 五 t “”= 三= i _ 一，对f _ l ，2 ，c ( 2 5 ) ( 碟) “ k = l 步骤三 如果i l 矿“一v “1 8 占则停止算法并输出划分矩阵和聚类原型，否则令 b = 6 + 1 ，转向步骤一。( 其中i i | j 为某种合适的范数。) 同样t 该算法也具有另一种形式，即从初始化模糊划分矩阵开始，先用式( 2 5 ) 计算聚类原型( 中心) 值，再用公式( 2 - 4 ) 更新模糊划分矩阵，直到满足停止准则 为止。 1 0 鲁棒高斯聚类及其在图像分割中的应用 2 2 2 模糊c 均值聚类算法的分析 通过( 2 4 ) 和( 2 5 ) 式的交替更新，构成了f c m 算法的迭代方案，在大多 数情况下，这种方法简单快速，能够实现规定类数的空间划分。但由条件式( 2 1 ) 可见，f c m 类型的算法需要满足一个点到各集合的隶属度之和为l 的概率约束。 这一约束有利于产生基于均方误差最小化准则下的隶属度迭代方案。同时我们也 应看到，其产生的隶属度是相对数，代表了数据点对于各类的分享程度，因而噪 声与外围点仍然被赋予了相对较高的隶属度，这使得f c m 类型的算法易受到数据 中噪声和外围点的影响，也就是它们的鲁棒性较差。为此人们提出很多解决方案， 如移去隶属度之和为1 的约束，将隶属度表征成为特征点或特征矢量到各类的典 型程度或或该点隶属于该集合的可能性，产生了可能性c 均值( p c m ) 聚类算法 等( 见第三章第二节) 。然而更具一般性的途径是将鲁棒统计学中的m 估计量引入 聚类分析，得到具有鲁棒统计特征的聚类算法以实现对于原型的鲁棒而有效的估 计，则是本章的重点。 2 3 1 鲁棒统计特征 2 3 鲁棒聚类与m 估计量 在统计学体系中，h u b e r 认为，一个鲁棒的算法需要具有以下的三个特征p 6 j ： 1 对于假定的模型，它应当具有合理的有效性和准确性。 2 假定模型的细微偏差对于性能的影响应为很小的程度。 3 假定模型的大的偏差不会造成“大灾难”。 在统计学中，第一个要求是非常重要的，因为工程中通常认为应当设计性能 误差在限定范围内的系统。换言之，当数据是“干净的”并符合假定的模型或分 布时，鲁棒的方法必须产生准确的估计。然而在工程实际中，我们还应当注意到 第二个要求，即分布模型的小的偏差不应当对性能产生显著的负面影响。当应用 于聚类分析时，我们希望算法在数据集的分布受到噪声和外围点的影响下仍能有 效，即具有鲁棒性。这也正是鲁棒统计学应用于聚类分析的一个重要的理论背景。 第三个特性则涉及到“崩溃点”或“破坏点”的概念i l ”，即在最差的情况下，能 够造成估计器完全失效或崩溃的最低的噪声含量。有限采样崩溃点的定义如下： 设z 是个数据点的采样，7 1 是一个估计量( 例如回归或位置估计量) 。现在任意 替代原数据中m 个点所得到的所有可能的破坏样点z 。用偏差( m ，丁，z ) 表示 这样的污染造成的偏差，即 第二章基于高斯估计量的鲁棒聚类旦 b i a s ( m ；t ，z ) 一u p r ( z ) 一丁( z ) ( 2 - 6 ) 这里上确界覆盖了所以可能的污染采样z 。如果偏差是有限的，m 个外围点 就会对r 的估计有任意大的影响，因此会造成估计器的“崩溃”。所以，崩溃点定 义如下 ， ( r ，z ) = m i n 等：b i a s ( m ；t ，z ) 为无限的) ( 2 7 ) jy 换言之，最恶劣情况下的最少部分的污染，都会造成估计器的完全崩溃。显然， 系统设计中总希望能达到最高的崩溃点。然而在理论上，所能达到的最好的崩溃 点是5 0 ，因为对于更高的污染，则不能确保能够区分好点与坏点。以一个简单 的直线为例，如果污染点或破坏点潜在地组成了另一条直线，而当污染比例高于 5 0 时，则不能有效地区分原来的真实的直线和由污染构成的新直线。 由式( 2 7 ) 可见，崩溃点的定义涉及到估计中的任意大误差，因此它允许数据 集中任意大程度的污染或破坏。而这在大多数工程应用中既不可能也不可接受。 人们总希望估计的误差相对于准确值而言是有界的。而且，特征点的值也不能任 意大，特征点的上确界和下确界也都可以获得的。因此定义如下更合适的崩溃点 定义： s ：( 丁，z ) = m i n 詈：b i a s ( m ；t ，z ) f ) ( 2 8 ) v 这里f 代表应用中可以接受的精确度。在使用式( 2 6 ) 计算偏差时，通常在已知特征 点的界内考虑上确界。 2 3 2 基于m 估计量的鲁棒聚类 经典的最小二乘法( l s ) 使用如下的参数估计方案 渤妒诬t ( 2 9 ) 这里一是和观察量相关的冗余，0 是待估计的参数矢量，是观测数据的数 目。在本节的讨论中，x ，和0 都是标量，并且如下定义冗余量： = 一一0 ( 2 - 1 0 ) 显然，最d , - 乘法对于噪声和边缘点极为敏感。因此，统计学中发展出很多鲁棒 的方法来克服最小二乘法对于噪声的敏感性( 如m 。r ，l 估计量等1 5 ) 。 m 估计量( 估计器) 采用了一种对称的正定函数( 鲁棒代价函数) p ( r ) ，并 通过所有点的代价函数的迭加构成目标函数。因此在m 估计量方法中，即需最小 化下面的目标函数： 鲁棒高斯聚类及其在图像分割中的应用 i ，( 口) = e p ( o ) ( 2 - t 1 ) j 一1 如果用( r ) 表示，( r ) 的导数，将上式对参数目求导并设其为零。可以得到上式最 小化的一个必要条件： 萼毗) 嘉= 0 ( 2 1 2 ) 妒( o ) 嘉= ( 2 大多数情况下，式( 2 1 1 ) 的解与式( 2 - 1 2 ) 的解是一致的。由式( 2 1 2 ) 和 式( 2 一1 1 ) 所定义的问题就叫做m 估计量或估计器。而隐式( 2 1 2 ) 表明，我们 可以根据实际问题的需要选择很多的不同形式的函数作为函数( ) ，因此在实际 中，我们更习惯于采用式( 2 1 2 ) 作为m 估计量的表达式。如果参数p 仅由项 组成，那么式( 2 1 2 ) 中的咖d b 就是1 ，因此可以被移去，得到的m 估计就是 对于样本参数的鲁棒估计，容易证明，如果代价函数选作p ( r ) = 1 2 r 2 ( 即 y ( r ) = r ) ，即可得到样本均值的位置估计；而如果代价函数选作p ( r ) = h ( 即 ( ，) = s g n ( r ) ) ，得到的就是样本的中值估计。很多p ( ) 函数( 见表2 1 ) 相继提出 以降低较大冗余对估计的影响 4 】，给定参数0 的初始值，牛顿法就可以通过迭代方 案获得式( 2 1 2 ) 的解。而求解这类问题的另种方法就是进一步发展m 估计量 以得到如下的w 估计量方法。 将w ( r ) 定义成r “r ) = i i f ，( r ) ，将其替代式( 2 1 2 ) 中的| 】c ，( r ) 进行参数估计，可 以得到： ( x j a ) w ( x j 一目) = 0 ( 2 l3 ) 整理得到： w ( x 一o ) x 0 = 上一 w ( x 厂咿) j = l ( 2 1 4 ) 可以认为，p 即是x ，的加权均值，可以通过迭代求解。事实上，这也是m 估 计量的种标准解法。在聚类分析中，我们希望准确地找到各类的中心，如果将 参数目代表各类的中心，x ，代表特征点或特征向量，式( 2 1 4 ) 就实现了原型类中 心的迭代求解。另一方面，可以看到加权函数w ( x ，一口) 本质上是一种可能性隶属 度函数，可以表示各点代表各类的典型性或属于各类的可能性。通过选择不同的 隶属度函数或加权函数w ( x 一目) ，可以对于离原型较近的点赋予其较高的隶属度 值，而对于嗓声或外围点，则分配相对较低的隶属度值。从而起到鲁棒加权的作 用。可见，m 估计量在聚类分析、可能性理论和鲁棒统计学之间建立了一座桥梁。 第二章基于高斯估计量的鲁棒聚类 表2 1m 估计量及其相应函数的示例 估计量代价函数 渺函数w 函数 ，的范围使用的尺度 均值 土，：r1 i r 无 2 中线 hs g n ( r ) s g n ( r ) i r 无 ， 1 ，1 一， ， i r l _ k h u b e r ( k ) o k c a u c h y ( k ) 纠t 村 r1 0 1 c 0 6 a n d r e w s 石1 。( 、1 - e o s x r ， 1 1 h 1 一s l n 万， 一s l n 丌r 石玎，c m a d o l 万+ 2 4 1 算法描述 2 4 鲁棒高斯聚类算法( r g c ) 由上节所述，鲁棒聚类问题可以演化成如何选择合适的加权函数或m 估计量 来实现c 个参数同时估计的问题。选取不同的加权函数可以得到不同的m 估计量， 它们对于数据包括噪声和外围点有着不同的加权选择作用。除了崩溃点外，一个 鲁棒估计量的鲁棒性可以通过几个特性来衡量，例如过失误差的敏感性、有效性、 局部平移的敏感性及投影点位置等，这些特性在f 1 4 】中均有详细的论述。我们总希 望鲁棒估计量具有低的对过失误差的敏感性，对假定分布具有比中值估计量高的 有效性，低的对局部平移的敏感性，和至少有一个有限投影点。而中值估计量并 不具备上述的大部分性质，这主要是因为其p ( ) 函数不是有界的。而别的估计量 则通过对外围点施以有界的影响，实现了鲁棒加权的作用。如t u k e y 双加权估计 量，h a m p e l 估计量等，对于高冗余的点更是赋予零加权( 即具有有限投影点) ，从 鲁棒高斯聚娄及其在图像分割中的应用 而具有更好的鲁棒特性。这些估计量都属于再次下降型估计量。 这里我们采用了一种简单有效而且参数可调的m 估计量高斯估计量，其 加权函数或可能性隶属度函数可以写作： w 。= e x p 一声d 2 ( x ，c