（计算机应用技术专业论文）模糊聚类新算法的研究.pdf

中文摘要 模糊聚类分析是模糊模式识别范畴中的一个重要分支，是一种无监督的模式 识别方法。在众多的领域得到了广泛的应用。比如分类学、地质学、商业活动、 模式识别和图像处理等很多方面。研究模糊聚类的算法及其应用具有十分重要的 价值，聚类的目标就是在庞大的数据集中发现潜在的数据结构，将类似的样本尽 可能地划分在同一类内。由于模糊聚类得到了样本属于各个类别的不确定性程 度，表达了样本类属的模糊性，即建立起了样本对于类别的不确定性描述，更能 客观地反映现实世界。 如今，模糊聚类已发展成庞大的体系。在实际中用处较大的是基于模糊关系 和相似关系的聚类算法以及基于目标函数的聚类算法。模糊c 均值聚类算法是最 早的目标函数聚类算法，也是目标函数聚类算法中研究得比较充分的算法。但是， 在模糊c 均值聚类算法以往的研究中仍旧存在薄弱环节和不足之处。模糊c 均值 聚类算法及其推广形式的主要缺点是对初始化较敏感，收敛速度较慢，对噪声较 敏感，不适用于类与类之间的样本量相差较大的情形。目前，针对模糊c 均值聚 类算法及其推广形式的不足，己提出了各种各样的算法。本文首先对传统的模糊 c 均值聚类算法进行了分析，讨论了模糊c 均值聚类中隶属度的新解释。其次， 针对区间型数据，提出了相应的区间型数据模糊c 均值聚类算法，将区间长度和 区间中值共同作为模糊聚类的要素，这在一定程度上克服了传统区间型数据模糊 c 均值聚类算法的不足。再次，针对现有关于混合型数据的模糊聚类算法存在的 缺陷，提出了改进的针对混合型数据的模糊c 均值聚类算法。该算法对符号型数 据和模糊数据使用了新的距离测度公式，在此基础上给出了改进的混合型数据模 糊c 均值聚类算法。实验表明新的算法在应对混合型数据的模糊聚类问题上有很 好的结果。最后对聚类有效性问题进行了研究，讨论了三种基于模糊划分的聚类 有效性函数。这三种聚类有效性函数分别依据可能性分布，香农熵和子集测度。 关键词：模糊划分，硬c 均值聚类，模糊c 均值聚类，混合型数据模糊聚类， 聚类有效性 a b s t i 认c t f u z z yc l u s t e r i n ga n a l y s i si sa ni m p o r t a n tb 啪c ho ff u z z yp a t t 锄t e c o g n i t i o n i t l s 锄u n s u p e r v l s e dp a t t e mr e c o g i l i t i o nm e t h o d c l u s t e r i n gm e t h o d sh a v eb e e nw i d e l v a p p i l e di nv a n o u sa r e a ss u c ha s at a x o n o m y ，g e o i o g y ，b u s i n e s s ，p a t t e mr e c o n 印i t i o n a n dl m a g ep r o c e s s i n ge t c s t u d i n g 丘l z z yc l u s t e r i n g 锄di t s 印p i i c a t i o n sa r cv e 珂 i m p o n a n t t h eo b j e c t i v eo fc l u s t e r i n gi st 0f i n dt h ed a t as 仃u c t u r ea n da l s op a n i t i o n t h ed a t as e ti n t o g r o u p sw i t hs i m i l a ri n d i v i d u a l s f l l z z yc l u s t e r i n gd e s c r i b e se a c h s 卸叩l e su n c e n a i n t ) ra n ds u c hu n c e r t a i n 够s o m e t i m e sc a nr e n e c tt 1 1 er e a lw o r l db e t t e r t h e no t h e rm e t h o d s t o d a yf h z z yc l u s t e r i n gh a sb e e nd e v e i o p e dav e d rb i gs y s t 锄i np r a c t i c e ，舵巧 r e l a t i o n ，矗】z z ys i m i l a r i 够a n dg o a l - m n c t i o nc l u s t 喇n ga l g 耐t h m sa r em o s tu s e 如1 f 。u z z yc 。m e 龃sc l u s t e l i n ga l g o r i t h 】mi s eo ft h ee a r l i e s tg o a l 矗m c t i o nc l u s t e r i n g a l g o m m s ， w h i c hh a sa c h i e v e dm u c ha t t e n t i o n h o w e v e r i tr e n l a i l l ss e v e r a l w e a k n e s s e s 锄di n s u 伍c i e n c y t h es i g n i f i c a t i 伽o fs u b j e c t i o nv a l u ei s 0 n eo ft h e w e a k n e s s e s t h em a i nw e a k n e s s e so ff u z z y c l u s t e r i n ga n di t se x p a n d e d n e s sa r e s e n s i t i v et 0 i n i t i a l i z a t i o n ， s l o w i yc o n v e r g e n ta n ds e n s i t i v et 0n o i s e p r e s e n t l v a c c o r d j n gt 0t h ew e a h e s so fn - a d i t i o n a l 丘e 乙秒c m e a n sa l g o r i t h mt h e r ea r em a n y k i n d so fn e wa l g o r i t h n 1 sh a v eb e 衄p r o p o s e d f i r s to fa l l ，t h e 仃a d i t i o n a ln l z z v c m e a n sc l u s t e d n ga l g 硎t h l i li ss t u d i e d 锄dt h em e a n i n go ft h em e n l b e r s h i pd e 酉e e s m f i z z yc m e a n sc l u s t e r i n gi sd i s c u s s e da g a i n s o m ec - m e 柚sc j u s t e 血ga l g 硎t h m s a r ep m p o s e df 0 ri n t e n ，a l v a l u e sd a t a s e t s ，w e i 曲t e d 缸巧c m e 姐sc l u s t e 咖2 a 1 9 0 n t h l nl sp r o p o s e dt 00 v e r c o m et h es h o n c o m i n g so ff i i z z ) ，c m e 锄s c l u s t e r i n g a l g o r i t h l l l s e c o n d ，p r e s e n t s 丘l z 巧c l u s t e r i n ga l g o r i t h mf 0 rm i x e df i e a t u r e so fs v m b 0 1 i c 如df u z z yd a t a w e 百v eam o d i f i e dd i s s i r n j l a r i t ) ，m e a s u r ef o rs ”1 1 b o l i c 柚df i 工z z yd a 脑 髓dt h e ng i v ef c mc l u s t e r i n ga l g o r i t i l i l 硌f o rt l l e s em i 】e d d a t at y p e s a n dt 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 i i li sa p p l j e dt 0r e a ld a t aw i 也f e a n 粗ev a r i a b l e so f s y m b o l i c 锄d 如z z yd a t a n u m e r i c a le x 唧l e si l l u s 仃a t et h a tt h em o d i f i e dd i s s 砌l a r i t v g l v e sb e t t e rr e s u l t s f i n a l l y ，t h ec l u s t e r i i l gv a l i d i 哆p r o b l e m sa r es t u d i e d t h r e e 邯e 胁c t l o n sa r ep r o p o s e d 、v h i c hb a s e do nt h ef k z ) ，p a n i t i o 璐1 1 b o s e 血e ev a l i d i t y 劬c t l o n sa r ep r o p o s e db a s e d0 nt h ec o n c 印t so fp o s s i b i l i s t i cd i s t r i b u t i o n ，s h 咖o n e n 仃d p y 柚ds i l b s e t h 0 0 dm e a s u r e k e y w o r d s ：f u z z ) rp a n i t i o n ，h a r dc m e 加sc l u s t e r i n g ，f u z z ) ，c m e a n sc l u s t e r i n g ， f u z z yc l u s t e r i n gf o rm i x e dd a t a ，c l u s t e r i n gv a l i d i t y 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得苤盗苤堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中 作了明确的说明并表示了谢意。 学位论文作者签名： 玛嘭 签字嗍刁年。弓月o 同 学位论文版权使用授权书 本学位论文作者完全了解苤鲞盘堂有关保留、使用学位论文的规定。 特授权墨盗盘鲎可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 锣哆 导师签名： 签字日期：印年c 7 月6 日 签字日期： 上 1 氏乙骘 6 7 年6 7 月d r 第一章绪论 1 1 聚类分析简介 第一章绪论 在人工智能领域中，通常所说的模式识别包括监督模式识别和非监督模式识 别。监督模式识别是指己知某些样本的分类情况，用这些已知样本对分类系统进 行学习或训练，使分类系统能够对这些已知样本正确分类，然后用已学习好的分 类系统或方法对未知样本进行分类。可见，监督识别需要有学习样本的先验知识。 与监督识别相对应的是非监督模式识别，它不需要样本的先验知识，也不需要获 取训练样本。与分类分析不同，聚类分析输入的是一组未分类记录，并且这些记 录应分成几类事先也不知道。聚类分析就是通过分析数据库中的记录数据，根据 一定的分类规则，合理地划分记录集合，确定每个记录所在类别。它所采用的分 类规则是由聚类分析工具决定的。 聚类就是按照一定的要求和规律对事物进行区分和分类的过程，将数据点的 集合分成若干类或簇，使得每个簇中的数据点之间最大程度地相似，而不同簇中 的数据点最大程度地不同。增强数据集的可理解性，发现数据集中数据之间有效 的内在结构和联系。在这一过程中没有任何关于分类的先验知识，没有教师指导， 仅靠事物间的相似性作为类属划分的准则，因此属于无监督分类的范畴。聚类分 析是用数学方法研究和处理所给定对象的分类。人类要认识世界就必须区别不同 的事物并认识事物间的相似性。聚类分析是多元统计分析的方法之一，也是统计 模式识别中非监督模式识别的一个重要分支。它把一个没有类别标记的样本集按 照某种准则划分成若干个类，即根据样本集的内部结构将其分成不同的几个子 类，使得在同一类的样本尽可能的相似，而在不同类的样本尽可能的不相似。换 句话说，如果将含有胆个样本五j 。的数据集石聚集成c 个子类五以，则要求 五满足： u 工2u 而u t = x n = 西，1 j ，c 确定数据集中样本相似性的常用方法是欧氏距离。目前，人们已经提出了 许多不同的聚类方法来解决聚类问题。聚类分析技术大体上分为硬聚类方法、模 糊聚类方法和可能性聚类方法。 传统的聚类分析 1 ，2 ，3 ，4 】是一种硬划分，它把每个待辨识的对象严格地 划分到某个类中，具有非此即彼的性质，因此这种类别划分的界限是分明的。样 本对各个子类的隶属度取成0 和1 两种值，也就是说样本只能属于所有类别中的 第一章绪论 某一类别。传统的硬聚类方法大体上可分成二大类：启发式和划分式。启发式方 法将数据进行树状分类，常常给出数据集的几种可能的分类情况；划分式则不同， 它将数据按照某种标准划分成单一的结果。划分式技术包括目标函数法( 平方误 差) 、密度估计法( 模型搜寻) 、图结构法和最近邻法。从总体而言，硬聚类算法 具有花费时间少的优点，但其缺点也是很明显的。由于硬聚类方法中样本对各个 子类的隶属度只能是o 或1 这两种值，绝对地割断了样本与样本之间的联系，无 法表达样本在性态和类属方面的中介性，极易陷入局部最优解，使得所得到的聚 类结果与实际要求偏差较大。 硬聚类方法具有非此即彼的性质，因此这种分类的类别界限是分明的。而实 际上大多数对象并没有严格的属性，它们在性态和类属方面存在着模糊性，适合 进行软划分。1 9 6 5 年z a d e h 教授提出的模糊理论为这种软划分提供了有力的分 析工具，人们开始用模糊的方法来处理聚类问题，并称之为模糊聚类分析，它是 聚类分析与模糊理论相结合的产物。模糊聚类方法中 5 ，1 0 6 】的分类结果仍然用 样本对各类的隶属度来表示，只是这时样本对各某个类别的隶属度从只能取o 或 1 扩展到了整个 0 ，l 】区间，样本对所有类别的隶属度之和是1 。模糊聚类方 法顾及到了样本与样本之间的联系，认为每一个样本与各个聚类中心都有一个隶 属关系。所以模糊聚类能够有效地对那些类与类之间有交叉的数据集进行聚类。 与硬聚类方法相比，模糊聚类方法提高了算法的寻优概率，所得的聚类结果明显 地优于硬聚类方法。由于模糊聚类得到了样本属于各个类别的不确定性程度，表 达了样本类属的模糊性，即建立起了样本对于类别的不确定性的描述，能更客观 地反映现实世界，从而成为聚类分析研究的主流。 模糊划分的概念最早由p i n i 提出 6 】，利用这一概念人们提出了多种聚类 方法，比较典型的有：基于相似性关系【7 】和模糊关系 8 ，9 】的方法( 包括聚合法 和分裂法) ，基于模糊等价关系的传递闭包方法【1 0 ，1 1 】、基于模糊图论最大树方 法【1 2 ，1 3 ，1 0 7 】，模糊聚类神经网络 1 4 ，1 5 ，1 6 ，1 0 8 和基于先进的优化算法 的聚类方法，以及基于数据集的凸分解 1 7 】、动态规划【1 8 】和难以辨识关系【1 9 】 等方法。然而由于上述方法不适用于大数据量情况，难以满足实时性要求高的场 合，因此其实际的应用不够广泛，故在该方面的研究也就逐步减少了。实际中受 到普遍欢迎的是基于目标函数的聚类方法，该方法设计简单、解决问题的范围广， 最终还可以转化为优化问题从而借助经典数学的非线性规划理论求解，并易于计 算机实现。 模糊聚类要求每个样本对各个类的隶属度之和为1 ，这一要求是对最终划分 情况的概率约束。但是，这一约束并不能反映出样本的典型性，对含有噪声的数 据集的聚类结果很不理想，而且与硬聚类算法相比，模糊聚类算法的收敛速度要 第一章绪论 慢得多。可能性聚类方法中，聚类结果以样本对各类别的典型程度表示。样本对 某个类别的典型度在区间 0 ，1 】内取值，但可能性聚类不要求每个样本对所有类 别的隶属度之和为l 。可能性聚类不仅顾及到每一个样本与各个聚类中心的隶属 关系，而且考虑到样本的典型性对聚类结果的影响，能够对含有噪声的数据集进 行有效的聚类。可能性聚类方法是聚类分析与可能性理论相结合的结晶。第一个 可能性聚类算法是r k 五s l l i l a p u 硎m 和j m k e l l e r 在1 9 9 3 年提出的。可能性聚类 对初始化非常敏感，往往需要借助其它方法( 如模糊聚类技术) 对数据集进行预 处理，否则容易陷入局部最优解。 随着计算机的发展和实际问题的需要，基于目标函数的聚类方法己成为聚类 分析的主流。这一方面是由于将聚类问题表述成优化问题易于与经典数学的非线 性规划领域联系起来，可用现代数学方法来求解。另一方面是由于算法的求解过 程比较容易用计算机来实现。围绕着目标函数的优化问题，目前主要形成三大方 向。一是建立合适的目标函数表达式，用数学规划方法求解最优值，如硬c 均值 聚类算法，模糊c 均值聚类算法及其推广形式，可能性c 均值聚类算法及其推广 形式等。这类方法的主要缺陷是对初始化较敏感，易于陷入局部极小点，收敛速 度较慢。二是将传统的聚类技术与神经网络相结合，借助神经网络的并行性来提 高算法的收敛速度。目前，针对硬聚类已提出k o h o n 即聚类神经网络，针对模 糊聚类也己提出模糊k o h o n e n 聚类神经网络 1 4 ，1 5 ，1 6 ，1 0 8 】。三是将传统的 聚类技术与现代优化方法相结合以克服算法对初始化敏感和易于陷入局部极小 点的问题。如与模拟退火算法【2 0 ，2 l ，1 0 9 】结合，与遗传算法结合 1 1 0 ，1 1 1 】， 与进化策略结合 1 l l ，2 2 】等。 各种聚类算法己经在许多领域得到了广泛地应用。在图像处理中被用于图像 分割 1 1 0 ，1 1 1 ，2 3 ，2 4 ，1 1 2 】，图像增强 2 5 】，图像压缩【2 6 】，物体的检测 2 7 】 等。在模式识别中，被用于语音识别 2 8 】，雷达目标识别 1 1 2 】，不变性模式识别 【2 9 】。在计算机视觉中被用于曲线拟合 3 0 ，3 l 】。此外，还可以用于概率密度函 数的参数估计 3 2 ，3 3 ，3 4 】，数学模型的建立 3 5 ，3 6 】，模糊推理规则的建立 3 7 ， 3 8 】，医学诊断等3 9 】。 。 1 2 研究的背景和意义 1 2 1 常见聚类算法及其改进算法 ( 1 ) c i 。a r a n s 算法( 随机搜索聚类算法) 划分方法中最早提出的一些算法大多对小数据集合非常有效，但对大的数据 集合没有良好的可伸缩性，如p ：枷。c l 吼是基于c 中心点类型的算法，能 第一章绪论 处理更大的数据集合。c i ，a r a 算法不考虑整个数据集合，而是随机的选择实际 数据的一小部分作为样本，然后用p 枷方法从样本中选择中心点。这样从中选 出的中心点很可能和整个数据集合中选出的非常近似。重复此方法，最后返回最 好的聚类结果作为输出。 c l a r a n s 是c l 吼算法的一个改进算法。它不像c l 肌算法那样每个 阶段选取一个固定样本，它在搜索的每一步都带一定随机性的选取一个样本，在 替换了一个中心点后得到的聚类结果被称为当前聚类结果的邻居，搜索的邻居点 数目被用户定义的一个参数加以限制。如果找到一个比它更好的邻居，则把中心 点移到该邻居节点上，否则把该点作为局部最小量。然后，再随机选择一个点来 寻找另一个局部最小量。该算法的计算复杂度大约是d 伽2 ) ，其中疗是对象的数 目。 ( 2 ) c u i 也算法( 利用代表点聚类) c u i 迮算法选择基于质心和基于代表对象方法之间的中间策略。该算法首先 把每个数据点看成一簇，然后再以一个特定的收缩因子向中心“收缩”它们，即 合并两个距离最近的代表点的簇。它回避了用所有点或单个质心来表示一个簇的 传统方法。将一个簇用多个代表点来表示，使c u r e 算法可以适应非球形的几 何形状。另外，收缩因子降底了噪音对聚类的影响，从而使c u l 迎算法对孤立 点的处理更加健壮，而且能识别非球形和大小变化比较大的簇。c u i 砸的复杂度 是d ( 刀) ，拧是对象的数目。 ( 3 ) b i r c h 算法( 利用层次方法的平衡迭代归约和聚类) b i r c h 是一个综合的层次聚类方法，它用聚类特征和聚类特征树( c f ) 来 概括聚类描述。该算法通过聚类特征可以方便地进行中心、半径、直径及类内、 类间距离的运算。c f 树是一个具有两个参数分支因子b 和阈值t 的高度平衡树， 它存储了层次聚类的聚类特征。分支因子定义了每个非叶子节点的最大数目，而 阈值给出了存储在树的叶子节点中的子聚类的最大直径。c f 树可以动态地构造， 因此不要求所有的数据读入内存，而可在外存上逐个读入数据项。b i i 汇h 算法 通过一次扫描就可以进行较好的聚类，故该算法的计算复杂度是d ( 胛) ，刀是对象 的数目。 ( 4 ) d b s c a n 算法( 基于高密度连接区域的密度聚类方法) d b s c a n 算法可以将足够高密度的区域划分为簇，并可以在带有“噪声 的空间数据库中发现任意形状的聚类。该算法定义簇为密度相连的点的最大集 合。如果采用空间索引，d b s c a n 的计算复杂度是d ( 疗l g 聆) ，这里行是数据库中 对象的数目。否则计算复杂度是d 伽2 ) 。 ( 5 ) s t i n g 算法 第一章绪论 s t i n g ( s t a t i s t a i c a li n f o 咖a t i o ng r i db a s e dm e t h o d ) 是一种基于网格的多分 辨率聚类技术，它将空间区域划分为矩形单元。针对不同级别的分辨率，通常存 在多个级别的矩形单元，这些单元形成了一个层次结构：高层的每个单元被划分 为多个低层的单元。高层单元的统计参数可以很容易的从低层单元的计算得到。 这些参数包括属性无关的参数c d ”从属性相关的参数小( 平均值) 、j ( 标准偏差) 、 朋j 刀( 最小值) 、肌叫最大值) 以及该单元中属性值遵循的分布类型。 s t i n g 算法中由于存储在每个单元中的统计信息提供了单元中的数据不依 赖于查询的汇总信息，因而计算是独立于查询的。该算法主要优点是效率高，且 利于并行处理和增量更新。 ( 6 ) c o b w e b 算法( 简单增量概念聚类算法) 概念聚类是机器学习中的一种聚类方法，大多数概念聚类方法采用了统计学 的途径，在决定概念或聚类时使用概率度量。c o b w e b 以一个分类树的形式创 建层次聚类，它的输入对象用分类属性一值对来描述。 分类树和判定树不同。分类树中的每个节点对应一个概念，包含该概念的一 个概率描述，概述被分在该节点下的对象。概率描述包括概念的概率和形如 尸( 4 = k “g ) 的条件概率，这里4 = 是“属性一值”对，g 是概念类。在分 类树的某个层次上的兄弟节点形成了一个划分。c o b w e b 采用了一个启发式估 算度量，即分类效用，用来指导树的构建。分类效用定义如下： 刀是在树的某个层次上形成一个划分 g ，c 2 ，c 。 的节点、概念或“种类” 的数目。分类效用对类内相似性和类间相异性进行评定： 概率p ( 4 = i c 。) 表示类内相似性。该值越大，共享该“属性一值”对的类 成员比例就越大，就更能预见该“属性一值”对是类成员。 ( 7 ) 模糊聚类算法f c m ( f u z z yc 二m e 锄s ) 以上介绍的几种聚类算法可以导出确定的聚类，也就是悦，一个数据点或者 属于一个类，或者不属于一个类，而不存在重叠的情况。我们可以称这些聚类方 法为确定性分类。在一些没有确定支持的情况中，聚类可以引入模糊逻辑概念。 对于模糊集来说，一个数据点都是以一定程度属于某个类，也可以同时以某种程 度属于另外一个类或者几个类。常用的模糊聚类算法是模糊c 平均值f c m ( f u z z y c m e 姐s ) 算法。该算法是在传统c 均值算法中应用了模糊技术。 由于以上常用聚类算法的性能从可伸缩性、发现聚类的形状、对“噪声 的敏感性、对数据输入顺序的敏感性、高维性和算法效率六个方面各不相同，所 以在不同领域进行数据聚类分析的时候，应当根据不同的实际需要来对各种聚类 算法进行选择，以达到最佳效果。 1 2 2 模糊聚类算法的发展概况 第一章绪论 自从z a d e h 在1 9 6 5 年提出模糊理论，模糊理论在实际应用中的率先工作是 在模式识别领域。由于模式识别中固有的模糊性，将模糊集引入模式识别获得了 巨大的成功。以模糊集为基础处理聚类问题是由b e l l m 加，k a l a b a 和z a d e h 4 0 】 于1 9 6 6 年首先提出的。随后，w e e 2 6 】，f l a l ( e 和t u m e r 4 1 】，g i t i i l a n 和l e v i n e 4 2 也采用模糊理论研究聚类问题。第一个系统地表述和研究模糊聚类的人是著名学 者r - u s p i n i 4 3 ，4 4 ，4 5 】。1 9 6 9 年，r u s p i n i 定义了数据集的模糊划分概念。与此 同时，z a d e h 4 6 】，t a m u r a 等人 4 7 】相继提出了基于相似关系和模糊关系的聚类方 法，这类方法分为聚集法和分裂法，目前人们已经提出了许多不同技巧来应用这 一思想 1 0 6 】。但由于基于模糊关系的聚类算法存在一个缺陷：在数据量很大时， 聚类速度非常慢。这一缺陷限制了算法的实际应用与进一步发展。在九十年代， 基于模糊关系的聚类算法的研究就很少了。 从七十年代到八十年代，人们对模糊矩阵及其传递闭包等问题进行了大量的 研究。到九十年代，尽管还有人作这方面的研究，如1 9 9 6 年k i ml e 4 8 】基于模 糊关系复合提出了一种聚类方法，但是由于这类方法不适宜于大数据集，有关这 方面的工作已经开展的很少。人们也曾试图用图论的方法来研究模糊聚类。如 1 9 7 4 年d m m 4 9 利用图论分析t a i n u r a 等人【4 7 】提出的聚类方法。1 9 9 2 年丁斌 1 1 3 】 提出动态模糊图最大树聚类方法。1 9 9 3 年，z h e n g g l lw u 和r l e a h y 5 0 】提出最优 图论方式的聚类方法。 在将硬聚类方法推广到模糊聚类的情形方面，人们也作了许多工作。如将硬 聚类中常用的肛最近邻法推广到模糊聚类，1 9 8 5 年t a og u 和b u b u i s s o n 5 1 】提出 松弛型缸最近邻法。同年鼬l l e r 等人 5 2 】提出了一种模糊肛最近邻法。在1 9 8 6 年b e z d c k 等人把模糊c 均值聚类算法应用到缸最近邻法中，提出了一种模糊缸 最近邻法。1 9 9 1 年b e r e a u 和b u b u i s s o n 【2 8 提出了另一种形式的模糊缸最近邻法。 还有其它一些模糊聚类方法，如1 9 7 8 年b e z d e k 和h a r r i 5 3 利用数据集的凸分解 来进行模糊聚类。1 9 8 5 年e s o g b u e 【5 4 提出动力学模糊聚类方法。1 9 8 8 年m a n t a l 邪 v a l v e r d e 5 5 】基于难以辨别关系提出了几种模糊聚类方法。 上面叙述了一些模糊聚类方法，由于各种各样的原因，这些方法的应用不是 很广泛。实际中受到普遍欢迎的方法是基于目标函数的模糊聚类方法，它是目标 函数硬聚类方法在模糊情形的应用。基于目标函数的模糊聚类方法首先是由 i 沁s p i n i 5 0 ，5 1 ，5 2 】提出的，但真正行之有效的方法是由d u 皿 5 6 ，5 7 ，5 8 】于 1 9 7 4 年给出的。d u 衄将硬c 均值聚类算法推广到了模糊情形。同年，b e z d e k 5 将功m n 的方法进行了一般化，建立了模糊c 均值聚类理论，并于1 9 8 0 年证明 了模糊c 均值聚类算法的收敛性和讨论了模糊c 均值聚类算法与硬c 均值聚类算 法之间的关系【5 9 】。下面我们从几个方面对目前提出的各种各样的基于目标函数 第一章绪论 模糊聚类算法进行综述。 ( 1 ) 对模糊c 均值聚类算法的收敛性和停止准则的研究：1 9 8 7 年，t u c k e r 6 0 】 发现b e z d e k 对模糊c 均值聚类算法收敛性的结论有误，模糊c 均值聚类算法的 收敛点除了局部最小点外，还有鞍点。t u c k e r 给出了一个例子说明鞍点是存在的。 b e z d e k 及其合作者们【6 1 ，6 2 ，6 3 ，6 4 】重新研究了模糊c 均值聚类算法的收敛性， 并给出了正确的表达式。s e l i m 及其合作者们【6 5 ，6 6 ，6 7 ，6 8 ，6 9 也对模糊c 均值聚类算法的收敛性进行了研究，他们也对模糊c 均值聚类算法的停止准则进 行了讨论。考虑到数据集的概率分布，s a b i n 6 2 】和y a n g 7 l 】从更一般的意义上对 模糊聚类算法的收敛性进行了研究。 ( 2 ) 提高模糊c 均值聚类算法的收敛速度：1 9 8 6 年，c 猢o n 等人 7 2 】提出了近 似模糊c 均值聚类算法，在保证精度相同的情况下所需的c p u 时间仅为模糊c 均值聚类算法的六分之一。1 9 9 2 年，谢维信和刘健庄 1 1 7 】提出了双层模糊c 均 值聚类快速算法，所需的c p u 时间仅为模糊c 均值聚类算法的十三分之一。1 9 9 4 年，勋m e l 和s e l 衄提出了松弛型模糊c 均值聚类算法 6 6 】和内循环型模糊c 均 值聚类算法 6 5 】，并证明了这两种算法的收敛性，这两种算法的收敛速度要比模 糊c 均值聚类算法有所改进。 ( 3 ) 修改目标函数：1 9 8 3 年，w i n d i l 锄扩充了模糊c 均值聚类算法的目标函数， 提出了几何模糊聚类算法 7 3 。1 9 8 5 年，l e s c z y l l s l ( i 等人将s u g e n 0 的模糊积分 引入模糊聚类，提出了不同于模糊c 均值聚类算法的聚类方法 7 4 】。1 9 9 1 年， t r a u w a c t 等人 7 5 】将最大相关原则推广到模糊情形，提出了基于模糊最大相关原 则的聚类算法，该算法将模糊c 均值聚类算法看成一个特例。1 9 9 3 年，y r a n g 7 6 】 给出了另一种形式的模糊最大相关原则聚类算法。 ( 4 ) 修改模糊划分空间：1 9 8 4 年，s e l i n l 和i s m a i l 将硬聚类思想和模糊聚类思 想相结合，提出了三种软聚类( 半模糊聚类) 方法 7 7 】。1 9 9 4 年，l o m e l 和s e l i m 对上述软聚类方法进行了评述，提出了阈值型软聚类算法 7 8 】。p e z d r c y 于1 9 9 6 年提出了条件模糊c 均值聚类算法【7 9 】。 ( 5 ) 给模糊聚类算法融入先验知识：p e z d r c v 认为实际问题常常含有已知信息， 于1 9 8 5 年提出了一种半监督模糊聚类算法 8 0 】。b e n s a i d 等人更深入地考虑了这 一问题，于1 9 9 6 年提出了新型的半监督模糊聚类算法 8 l 】。 ( 6 ) 修改模糊c 均值聚类算法中的距离：模糊c 均值聚类算法中距离采用的是 欧氏距离。将欧氏距离用其它范数代替，1 9 9 1 年j a j u g a l 提出了基于，l 范数的模 糊聚类算法 8 2 】。同年，b 0 b r o u s l 【i 和b e z d e k 更深入地考虑了这一问题，提出了 一般的基于，范数和，岫范数的模糊聚类算法 8 3 】。将统计信息融入模糊聚类中。 1 9 7 8 年，g u s a t a f s 和k e s s e l 引入了模糊协方差矩阵，提出了协方差模糊聚类 第一章绪论 算法。1 9 8 9 年，g a t h 和g e v a 将最大相关原则引入了距离的计算中，提出了一种 模糊聚类算法。模糊c 均值聚类主要适用于球状数据，拓广模糊c 均值聚类适用 范围的工作首先是由b e z d e k 进行的。1 9 8 1 年，b e z d e k 提出了模糊c 族算法 5 】， 采用样本点到族原型的距离来度量样本与各类原型的相似性，当族维数取为0 ， 1 ，2 或2 以上的值时，分别适用于椭球状、线状、平面状、超平面状的数据结 构。1 9 9 0 年，d a v e 提出了模糊c 壳算法【8 4 】，采用点到圆壳的垂直距离的度量 方式，模糊c 壳算法的一些修改算法也相继提出。此外针对关系型数据和模糊数 型数据，分别提出了关系型模糊c 均值聚类算法 8 5 ，8 6 】和模糊数型模糊c 均值 聚类算法 7 6 】。 ( 7 ) 噪声数据的模糊聚类：针对模糊c 均值聚类算法对噪声较敏感的现象，d a v c 将噪声点看成单独的一个类，于1 9 9 1 年提出了噪声型模糊c 均值聚类算法 8 7 】。 幻m 等人 8 8 】将鲁棒性统计理论应用于噪声聚类，提出了最小剪切型模糊c 均值一 聚类算法。 ( 8 ) 混合型数据的聚类：实际问题中，数据集包含的分布可能有好几种。1 9 7 8 年，g u s a t a f s o n 和k e s s e l 提出的协方差模糊聚类算法可对含有椭球状和线状分布 的数据进行聚类。1 9 9 5 年，j a w a h a r 等人对于同时含有几种数据类型的数据结构， 提出了一些算法。 k 五s 1 1 i l 叩1 啪埘和k e l l e r 认为模糊c 均值聚类算法反映不出样本的典型性，不 适用于噪声聚类问题。于是他们于1 9 9 3 年提出了可能性c 均值聚类方法【8 9 】。目 前基于可能性c 均值聚类算法，己提出了许多新的聚类算法以适用不同的聚类模 型。 此外，为了克服模糊聚类算法对初始化较敏感，易于陷入局部极小点的问题， 结合现代优化方法，又提出了许多混合型算法【4 ，1 0 9 ，1 1 0 】；为了克服模糊聚类 算法收敛速度较慢的问题，已提出了模糊聚类神经网络 1 4 ，1 5 ，1 6 ，1 0 8 】。 1 3 模糊聚类的有效性 聚类算法的性能是与数据集密切相关的，没有万能的聚类算法。这也是为什 么新的聚类算法层出不穷的原因。对于给定的数据集，首先需要判断有无聚类结 构，这属于聚类趋势研究的课题，如果己经确认有聚类结构则需要用算法来确定 这些结构，这属于聚类分析研究的课题。得到聚类结构后，则需要分析聚类的结 果是否合理，这属于聚类有效性研究的课题。对聚类分析而言，有效性问题又可 以转化为最佳类别数c 的确定。 人们在运用聚类算法之前需要对数据集的结构进行检测。由于我们面临的是 无标签数据集，没有关于数据集的先验知识，对于要聚类的数据集 第一章绪论 x = “，而，。j 。 ，需要考虑下面三个问题。 问题1 ：x 是否是随机的? 即对于类数c ( 1 c 刀) ，x 是否有聚类结构。 问题2 ：如果x 有聚类结构，如何确定这个结构? 问题3 ：一旦x 被聚类，如何确定聚类结果的有效性? 这里，问题1 称之为“聚类趋势”，问题2 称之为“聚类分析”，问题3 称之 为“聚类有效性”。图1 1 给出了无标签数据集的处理过程。 图l l 无标签数据集处理过程 关于“聚类趋势”问题，我们可以采用一定的技术来检测数据集是否是随机 的，从而决定是否存在聚类结构。 关于“聚类分析”问题，目前我们可以用硬聚类，模糊聚类和可能性聚类等 聚类方法来确定数据集的聚类结构。但聚类分析的结果与被要聚类的数据密切相 关，不同的算法也可能会产生不同的结果。关于不同算法的聚类性能的好坏可以 通过多种方法进行评价。人们曾对c 均值聚类算法，模拟退火算法，遗传算法和 t a b u 搜索算法进行了对比实验。结果表明，尽管c 均值聚类算法的聚类性能总 体上不如其它三种方法，但其运算速度等是其它三种方法无法相比的。 对于给定的数据集，如果己经确认该数据集具有聚类结构，则需要用聚类算 法来最终确定这个结构。大多数聚类算法需要事先确定数据集的分类数。如果分 第一章绪论 类数选取的不合适，可能会使划分的结果与数据集的真正结构不相符，使得某一 类被划分的或大或小。关于数据集的最佳分类数问题属于聚类有效性问题。 历史上有关聚类有效性问题的研究大都是基于硬c 均值和模糊c 均值算法 的，d u b e s 和j a i n 曾对1 9 8 0 年前的研究做过评述。现有的聚类有效性函数按其 定义方式可分为：基于数据集的模糊划分、基于数据集的几何结构和基于数据集 的统计信息三类，这三类的理论基础和特点均列于表1 1 中。 表1 1 三类聚类有效性函数的特点比较 基于模糊划分基于几何结构基于统计信息 一个能较好分类的数一个能较好分类的数最佳分类对应的数据 据集应该是较“分明”据集，每一个子类应结构所提供的统计信 的。因此，模糊划分该是紧致的并且子类息是最好的 理论基础的模糊性越小，聚类与子类应该是尽可能 的结果越可靠分离的。紧致性与分 离性的比值作为聚类 有效性标准 简单、运算量小与数据集的结构密切与数据集分布密切相 优点 相关 关 与数据集的结构特征表述比较复杂、运算性能依赖统计假设与 缺点 缺乏直接联系量大数据分布的一致性 z a d e h 的分离度、d 啪的划分系数v o g e l 等人的p f s 聚 代表性b e z d e k 的划分熵、g u n d e r s o n 的分离系类、j a i n 等人的自举 研究w i l l d h 锄的比例系数数x i e b e l l i 指标法、b e n i 的熵形式有 效性函数 以上三种途径是聚类有效性问题研究的主流，此外还有一些其它的方法，如 基于图论的方法，爬山法等。 在实际的聚类中，即使分类数选取的合适，由于选取的算法不合适或者算法 的参数选取的不合适，也可能得不到数据的真正结构。这促使人们寻找能指导聚 类算法得到更符合实际分类的函数。这方面的工作首先是由h u n t s b e r g e d r 于1 9 8 5 年进行的，他将模糊c 均值聚类算法应用于图像分割，为了得到理想的分割效果， h 岫曲e 瑁e 巧引入了一个指导分割的函数。1 9 9 0 年，c 锄a n 和m 仃i c k e 利用信息 论中的灿c 标准作为对硬聚类的i s o d 觚a 法的分裂、合并的标准。1 9 9 2 年， c b 锄和c h e 岫g 用划分系数来指导聚类过程。1 9 9 6 年，b e n s a i d 等人修改了 x i e b e n i 指标，提出了一个指导分类的新标准，并在其文章中明确指出对聚类有 效性函数的研究不仅能回答数据集的最佳分类问题，而且能有效地指导聚类算法 第一章绪论 得到更符合实际的分类。 目前对模糊聚类有效性问题的研究范围已拓广到椭球状，线状和壳状数据。 基于可能性聚类的聚类有效性函数也被提出。此外对噪声数据也提出了一些聚类 有效性函数。我们主要关注球状分布数据的模糊分类问题。因为这一类问题是最 基本的，对这一类问题的研究结果可直接推广到其它分布型数据的分类上去。 一般而言，对于给定的数据集，选取最佳分类数问题和在已知分类数时，选 取最好的数据划分问题称为聚类有效性问题。聚类有效性问题是聚类分析的瓶 颈。对该问题的有效解决将会对聚类分析的成功应用产生十分深远的影响。这方 面问题的研究目前是，将来仍然是一个急待解决的问题。 1 4 模糊聚类的应用 虽说模糊聚类分析应用于模式识别的时间不长，但它并非一个新领域，早已 被应用在其它学科中。模糊聚类理论的发展更加推动了其在生产实践中的应用， 反过来实际应用的需求又进一步促进了模糊聚类理论的不断丰富和完善。随着理 论的发展，模糊聚类已经在众多的领域获得广泛的应用，并取得了令人满意的效 果和可观的效益。其应用范围涉及到通讯系统中的信道均衡、矢量量化编码中的 码书设计、时间序列的预测、神经网络的训练、参数估计、医学诊断、天气预报、 食品分类、水质分析等领域。本文不再赘述。鉴于模糊聚类在模式识别和图像处 理两个领域中相当成功的应用，以下主要对这两方面详细介绍。 1 4 1 模糊聚类在模式识别中的应用 模式识别中两大主要的分支为有监督的分类和无监督分类，而其中无监督分 类与聚类分析相对应。正是由于模糊聚类与模式识别的天然联系，使得它首先在 模式识别领域获得成功的应用。模糊聚类不需要训练样本，可直接通过机器学习 达到自动分类的目的。 模式识别中一个最重要的问题是特征提取，模糊聚类不但能从原始数据中直 接提取特征