2. 2. 4基于目标函数的模糊聚类分析 15 第2章聚类分析及：U:应用实例
实际中最常用的是基于目标函数的模糊聚类方法，即把聚类归结成一个带约
束的非线性规划问题，通过优化求解获得数据集的模糊划分和聚类.该方法具有设
计简单、解决问题的范围广、可转化为优化问题而借助经典数学非线性规划理论
求解以及易于在计算机上实现等诸多方面的优点，因而深受广大学者的喜欢，成
为最常用的一种聚类分析方法.伴随着计算机的应用和发展，基于目标函数的模糊
聚类算法成为新的研究热点
在基于目标函数的聚类算法中模糊C均值（FCM，Fuzzy c-Means)类型算法
的理论最为完善、应用最为广泛.模糊C均值类型的算法最早是从硬聚类目标函数
的优化中导出的.为了借助目标函数法求解聚类问题，人们利用均方逼近理论构造
了带约束的非线性规划函数，从此类内平均误差和（WGSS, Within-Groups Sum of
Squared Error) J,成为聚类目标函数的普遍形式.为极小化该目标函数而采取的
Pikard迭代优化方案就是著名的硬C均值（HCM)算法和ISODATA(Iterative
Self-Organizing Data Analysis Technique A)算法?模糊划分概念提出后，Dunn
首先把WGSS函数J,扩展到J2——类内加权平均误差和函数，后来Bezdek又引入
一个参数m，把推广到一个目标函数的无限族，并给出了交替优化（AO,
Alternative Optimization)算法，即为人们所熟知的FCM算法?从此，奠定了 FCM
算法在模糊聚类中的地位.下面我们从以下几个方面来逐步介绍基于目标函数的
模糊聚类分析法['3].
(1)数据集的e划分
给定数据集；^ = ^^,1:，...,1?；1〔/?'-为模式空间中〇个模式的一组有限观测样
本集，X, ?;eiT为观测样本&的特征矢量或模式矢量，对应特征
空间中的一个点，Xkj为特征矢量Xk的第_/维特征上的赋值.对给定样本集X的聚
类分析就是要产生i的C■划分
由上面有关聚类分析的数学模型可知，数据集I的C划分得到的C个子集
如果满足下式的条件，则称之为X的硬C划分
?uZc =jr ~
X0 Xk = < i ^ k < c ‘ (2-27) X, X,\\ 如果用隶属函数//,vt =表示样本X?与子集毛的隶属关系，则 硬C划分也可以用隶属函数表示，即用C个子集的特征函数值构成的矩阵 16 第2帝聚类分析及其应用实例 个矢量间的距离来度量.J、{CJ，P)表示了各类中样本与其典型样本的误差平方和. 利用/?，Ji(?7，P)也可以表示为 J人= 伙 1 k=\\ /=1 32) e Mhc 聚类准则为寻求最佳对以使得在满足& 条件下为最小. 解决这类优化问题最常用的方法是用迭代法求取的近似最小值 Dunn按照Ruspini定义的模糊划分的概念，把硬聚类的目标函数推广到模糊 聚类的情况.为了避免产生平凡解，保证这一推广有意义，Dunn对每一个样本与每 类原型间的距离用其隶属函数平方加权，从而把类内误差平方和目标函数扩展为 类内加权误差平方和目标函数 1 k=\\ /=1 \\l-66) s.tU e Mjc (3)模糊c均值聚类算法 为了优化聚类分析的目标函数，人们提出了现在相当流行和应用广泛的模糊c 均值（FCM, Fuzzy c-means)聚类算法.该算法是从硬c均值（HCM, Hard c-means) 聚类算法发展而来的HCM算法用于求解满足式中的尸)为最小时的分类结 果.以下给出FCM算法的具体步骤?: 初始化：给定聚类类别数C，2 始化聚类原型模式p(°),设置迭代计数器6 = 0; 步骤一：用下面两式计算或更新划分矩阵t/(十 对于V/,A：,如果则有 〉 2 \ ,、 C f Ab) 必=\\L ik (2-34) y=i \\\ 如果3/，r，使得￠￠)=0,则有 = 1,且对y 本 r,ju-p = 0 (2-35) 18 %2章聚类分析及其应用实例 步骤二 ：用下式更新聚类原型模式矩阵 p 产、、二过 ， / = 1,2.--.,C (2-36) 1(\”广 k=\\ 步骤三：如果则算法停止并输出划分矩阵t/和聚类原型尸，否 则令6 = Z) + l，转向步骤一.其中I.I为某种合适的矩阵范数. 对于HCM算法的具体步骤，大家可以参照西安电子科技大学出版社出版的由 高新波著作的〇模糊聚类分析及其应用一书〈.FCM算法还具有另一种形式，即从 初始化模糊划分矩阵开始，先用上一公式计算聚类原型（中心）矩阵，然后用上 上公式更新模糊分类矩阵，直到满足停止准则为止[\ 由以上算法不难看出，整个计算过程就是反复修改聚类中心和分类矩阵的过 程，因此常称这种方法为动态聚类或者逐步聚类法.几经修补，该算法的收敛性已 经得以证明：FCM算法能从任意给定初始点开始沿一个迭代子序列收敛到其目标函 数的局部极小点或鞍点.对于满足下列条件的集合FCM算法可以收敛 到局部最优解，这样的被称作模糊聚类的解集[\ VUeM^^,J^(u\\P') \\jp^r\\j?[u\\p') U = [//? ]??来表示.矩阵t/中的第/行为第/个子集的特征函数，而矩阵t/中的第A 歹J为样本相对于c个子集的隶属函数[“].则工的硬C划分空间为 =jt/e e {0,1}，Va; J//,* = l,V;t;0 < < ?, ▽/} (2-28) I /=1 k=\\ J Ruspini利用模糊集理论把隶属函数//,?从{0,1} 二值扩展到[0,1]区间，从而把 硬C划分概念推广到模糊C划分，因此X的模糊C划分空间为 M,. =|t/ e e [0,4V/，A：;文//,女=1，VA:;0< < n,V/l (2-29) [ /=1 k=\\ J 由于模糊划分可以得到样本分属于各个类别的不确定性程度，建立了对于类 别的不确定性的描述，因此更能客观地反映现实世界在划分结果中，模糊划分 还能指明划分的外围、不同划分块间的衔接和离散的情况，因此能挖掘出更多的A 细节信息[，