第六章模糊聚类

模糊聚类分析的理论与方法1第六章模糊聚类6.1概述一、模式识别模式识别能力可以说是人类的一种基本功能。所谓模式是对事物的客体的描述。可以把模式识别理解为对输入数据的鉴别，这种鉴别是通过对事物特征的检索来获取的。可以把模式识别过程分为三个阶段：数据获取、数据预处理以及决策分类。在数据获取阶段，物理变量被转换为一个测定的数据集合。这些数据经过数据预处理后，提取出一组特征值。决策分类器实际上是一组决策函数，它们依据事物的特征对事物做出分类。数据预处理的一个功能是把采集到的数据转换为适合计算机分析的数学模式，相应地获得了模式矢量。模式矢量呈现为模式空间中的一个点。设模式矢量具有n维分量，则模式X可以表示为12nXXXX⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎣⎦M(6.1)式中下标n表示维数。模式空间X表示为11121121222212TnTnTmmmnmXXXXXXXXXXXXX⎡⎤⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥==⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦LLMMMMML(6.2)式中，TiX表示模式矢量iX的转置，即()12,,,TiiiinXXXX=L，1,,im=L。特征提取的作用是降低维数，特征矢量表示为()12,,,TiiiirXXXX=L，1,,im=L式中，rn。在决策分类中，具有同种特征的模式矢量被聚合，不同的聚类表示不同类别的模式。决策分类器以一组决策函数来划定不同的模式类别。决策后的输出位于分类空间之中。如果打算将输入模式分为c类，则分类空间是c维的。对于如上所述，我们可以扼要地用图6.1.1来表明。第六章模糊聚类2二、聚类和聚类方法设数据集X中含有n个样本（n个元），表示为xk(k=1,K,n)。聚类问题是要把{x1,x2,K,xn}区分为X中的c个子集，2≤c≤n，要求相似的样本应尽量在同一类，不相似的样本应在不同的类。聚类数c通常是预先不知道的。粗略说来，可以把聚类方法区分为3种：谱系聚类法，图论方法以及目标函数法。谱系聚类法设数据集X中有n个样本，我们欲将这n个样本划分为c类。首先，我们可以将这n个样本划分为n类，每一类只含有一个样本。然后，我们依次将这些样本划分为n-1,n-2,K,（n-j+1）类（j=1,2,K,n）。对于任意两个样本x1和x2，它们必会在某个层次（即j取为某一确定值）被聚合于同一类之中。如果聚类过程具有如下的性质，当两个样本在j=j1层处于同一类中，在更高的层j=j2（j2j1）这两个样本也处在同一类中，则我们称这样的聚类过程为谱系聚类。谱系聚类法具有两种类型：聚集法和分裂法。聚集法从n个只含单一样本的聚类开始，然后逐步地将这些类合并。聚集法的过程是从下往上。分裂法的过程则是从上往下。它的开始点是把所有的样本考虑为同一类，然后逐步地分裂为多个类别。聚集法的计算比较简单，但当样本数很多而且只需划分为很少的类别时，使用分裂法可以省去很多重复的计算。对于谱系聚类，我们可以用图6.1.2来表示。数据获取数据预处理决策分类第一阶段第三阶段第二阶段X（r）分类结果物理变量XN图6.1.1模式识别的过程图6.1.2谱系聚类μ模糊聚类分析的理论与方法3图论方法在图论方法中，数据集的各个样本构成图中的节点，连接节点的边的加权系数反映了两个节点的相似性，各组节点间的连结度测度被采用作为聚类准则。聚类方法常常采用在昀小生成树中去掉割边来形成多个子图。目标函数法在目标函数法中，使用目标函数来测度聚类的效果，昀佳聚类对应于求取目标函数的极值。在本章的6.2节，我们将具体谈及在实现模糊聚类时目标函数法的应用。三、距离度量在聚类分析中，一个重要的问题是建立起合理的相似性测度。通常，我们用距离的概念来衡量样本间的相似性和类与类之间的相似性。设数据集X是空间RP的一个子集合，X=(x1,x2,…,xn)∈RP，又设xk,xl∈X。我们用dkl来表示样本xk和xl之间的距离度量。距离度量d是一个映射，d:X×X→R+，它满足如下4条性质：01≥°kld；lkklxxd==°，当且仅当02；lkkldd=°3；jlkjklddd+≤°4。在聚类分析中，对性质°4不一定要求满足。类与类之间的距离有如下几种定义。昀小距离：()min,,minkiljijklxxddρρρρ∈∈=(6.3)式中，iρ表示第i类，jρ表示第j类。昀大距离：()max,,maxkiljijklxxddρρρρ∈∈=(6.4)平均距离：1(,)kiljavgijklxxijddkkρρρρ∈∈=∑∑(6.5)这里，ki和kj分别为类别iρ，jρ中的样本数。中值距离：第六章模糊聚类4jijimeanMMd−=),(ρρ(6.6)式中，Mi和Mj分别为第i类和第j类中的样本数据的中值。四、模糊聚类经典的聚类算法将每一个辨识对象严格地划分为属于某一个聚类。但是实际上，某些对象并不具有严格的属性，它可能位于两种聚类之间，这时采用模糊聚类可能会获得更好的结果。经典聚类的结果将数据集X划分为若干个普通子集，记为Si（i=1,…,c）。样本xk属于哪一类以特征函数iSμ来表示，且(){}:0,1iSixXμ→模糊聚类将数据集X划分为若干个模糊集合，记为Si（i=1,…,c）。样本xk的从属程度以隶属函数iSμ%来表示，且()[]:0,1iSixXμ→%我们用图6.1.3来说明经典聚类和模糊聚类的不同。对于图6.1.3（a）绘出的蝶形数据结构，图6.1.3（b）是经典聚类的结果，图6.1.3（c）是模糊聚类的结果。由图（c）可见，模糊聚类的优点是不但能明确指出每一种聚类的中心，同时还能指明聚类的外围，不同聚类之间的衔接和离散的情况。（a）蝶形数据结构x2x5x6x3x7x4x1x8x9x11x14x10x12x15x13模糊聚类分析的理论与方法5图6.1.3硬聚类与模糊聚类的对比6.2模糊分类一、硬分类（CrispC-Partition）欲将数据集X={x1,x2,…,xk,…,xn}分为c类，使得X中的任意样本xk必须完全属于某一类，以及每一类至少包含一个样本。这种问题的分类结果可以用一个c×n阶矩阵U来表示，U中的元uik为10kiikkixAuxA∈⎧=⎨∉⎩当当式中，),,1(ciAiL=表示第i类。矩阵U具有如下性质：（c）蝶形数据的模糊聚类0.860.860.940.990.140.940.970.880.060.010.060.500.030.120.14（b）蝶形数据的硬聚类x10x0011111110000第六章模糊聚类6{}10,1iku°∈；121,cikiuk°==∀∑；130,nikkuni°=∀∑。[例6.2.1]设{}54321,,,,xxxxxX=。若分类结果为{x1,x5}，{x3,x4}，{x2}，则分类矩阵U为12345123100010011001000xxxxxAUAA⎡⎤=⎢⎥⎢⎥⎢⎥⎣⎦若分类矩阵为⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=010001010000011U则分类结果为{x1,x2}，{x3,x5}，{x4}。二、模糊分类（FuzzyC-Partition）当上述分类矩阵的元的取值并非限于{0，1}二值，而是位于[0，1]区间，则演变为模糊分类。对应的矩阵U是模糊矩阵，且具有如下性质：[]10,1iku°∈；121,cikiuk°==∀∑；130,nikkuni°=∀∑。[例6.2.2]设{}123,,Xxxx=，c=2，则下列两种情况是可能存在的模糊分类：110.5000.51U⎡⎤=⎢⎥⎣⎦以及⎥⎦⎤⎢⎣⎡=1.07.02.09.03.08.02U模糊聚类分析的理论与方法7我们可以用图6.2.1来表明硬分类和模糊分类的差别。在硬分类时，样本只能落入3个顶点（100，010，001）中的一个。在模糊分类时，样本可以散布于图示的平面之中。图6.2.1c=3时分类结果的几何图示对于硬分类的情况，若试图将n个数据样本分为c类且每类不空，则存在有M个可能的分类结果：⎥⎥⎦⎤⎢⎢⎣⎡−⎟⎟⎠⎞⎜⎜⎝⎛=∑=−cjnjcjjccM1)1(!1当n=25,c=10时，大概有1018个不同的分类结果。对于模糊分类的情况，则潜在有无限多个分类结果。实际上，每一个模糊分类矩阵都可以用若干个硬分类矩阵来表示，例如：⎥⎦⎤⎢⎣⎡+⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡=110013.0011087.013.0187.00U三、聚类准则我们希望在众多可能的分类中寻求合理的分类结果，为此，就要确定合理的聚类准则。在硬分类时，常使用的准则是昀小平方误差和。设U=[uik]为硬分类矩阵，vi(i=1,…,c)是第i类的聚类中心，也可以将vi理解为样本。定义目标函数为()21(,)kicikixSJUVd=∈⎛⎞=⎜⎟⎝⎠∑∑(6.7)式中，dik表示第i类中样本xk到聚类中心vi的距离。J(U,V)表示了各类中样本到聚类中心的距离平方和。利用}1,0{∈iku，),(VUJ也可以表示为∑∑===nkciikikduVUJ112)(),((6.8)第六章模糊聚类8聚类准则为寻求昀佳组对(U,V)，以使得J(U,V)为昀小。解决这类优化问题昀常用的方法是用迭代算法来求取J(U,V)的近似昀小值。类似于硬分类的情况，对于模糊分类我们定义目标函数为∑∑===nkciikmikduVUJ112)()(),((6.9)式中U=[uik]为模糊分类矩阵，]1,0[∈iku，vi表示第i类聚类中心(i=1,…,c)，[)∞∈,1m是加权指数。),(VUJ表示了各类中样本到聚类中心的加权距离平方和，权重是样本kx对第i类隶属度的m次方。设kx和iv都是p维向量，即PRvx∈∀,，A为P×P矩阵，即PPMA∈，则2)(ikd的一般表达式为)()()(22ikTikikikvxAvxvxd−−=−=(6.10)式中，T表示矩阵的转置，矩阵A必须取为对称正定矩阵。当取A=I（幺矩阵）时，上式表示为欧氏距离。聚类准则取为求),(VUJ的极小值：{}),(minVUJ(6.11)由于矩阵U中各列都是独立的，因此{}()()211min(,)minncmikikkiJUVud==⎧⎫=⎨⎬⎩⎭∑∑()()211minncmikikkiud==⎧⎫=⎨⎬⎩⎭∑∑上述极值的约束条件为等式11=∑=ciiku，可以用拉格朗日乘数法来求解：()()2111ccmikikikiiFuduλ==⎛⎞=+−⎜⎟⎝⎠∑∑昀优化的一阶必要条件为110cikiFuλ=∂⎛⎞=−=⎜⎟∂⎝⎠∑(6.12.a)()()120mstststFmuduλ−∂⎡⎤=−=⎣⎦∂(6.12.b)由式(6.12.b)得模糊聚类分析的理论与方法9112)(−⎥⎥⎦⎤⎢⎢⎣⎡=mststdmuλ(6.13)上式代入式(6.12.a)得()()1111112111121111=⎪⎪⎭⎪⎪⎬⎫⎪⎪⎩⎪⎪⎨⎧⎥⎥⎦⎤⎢⎢⎣⎡⎟⎠⎞⎜⎝⎛=⎥⎥⎦⎤⎢⎢⎣⎡⎟⎠⎞⎜⎝⎛=∑∑∑=−−−=−=cjmjtmmjtcjmcjjtdmdmuλλ因而()∑=−−⎥⎥⎦⎤⎢⎢⎣⎡=⎟⎠⎞⎜⎝⎛cjmjtmdm1)1(121111λ将上式代入式(6.13)得∑=−⎟⎟⎠⎞⎜⎜⎝⎛=cjmjtststddu1)1(21考虑到ikd可能为0，应分两种情况加以讨论。对k∀，定以集合kI和kI~为{}{}kkikkIcIdciiI−==≤≤=,,2,1~0,1|L使得),(VUJ为昀小的iku值为2(1)11ikmcikjjkudd−==⎛⎞⎜⎟⎜⎟⎝⎠∑当∅=kI(6.14.a)0,ikkuiI=∀∈%以及1kikiIu∈=∑当∅≠kI(6.14.b)用类似的方法可以获得),(VUJ为昀小时iv的值。令0),(=∂∂VUJvi第六章模糊聚类10得到()[]()[]()0)(0)(20)()(111=−=−−=−−∂∂∑∑∑===nkikmiknkikmiknkikTikimikvxuvxAuvxAvxvu由此得()cixuuvnkkmiknkmiki,,1)(111L==∑∑==(6.15)若数据集X、聚类类别数c和权重m值已知，就能由式(6.14)和式(6.15