《模式识别原理与应用》课件第6章

第6章聚类分析6.1

模式相似性测度与聚类准则6.2

基于试探的聚类算法6.3层次聚类法6.4动态聚类法6.5分解法习题6.1模式相似性测度与聚类准则

聚类分析是以模式相似性为基础,按照某种聚类准则进行判决。本节主要介绍模式相似性测度与聚类准则。6.1.1模式相似性测度分类在实际工作中经常出现,例如,在古生物研究中,根据骨骼的形状和大小对它们进行分类;在地质勘探中,根据矿石标本的物探和化探指标对标本进行分类,等等。其中,骨骼的形状和大小、标本的物探和化探指标是描述样本特征的具体参数,是分类的依据。根据测量尺度的不同,模式特征的数值化测量结果主要分为以下三种类型:

(1)物理量:特征用连续的量来表示,如长度、重量、压力等。

(2)次序量:特征度量没有明确的数量表示,只有次序关系。例如,评价茶叶的质量分成优、良、中、差四等,其中,有次序关系,没有数量表示。

(3)名义量:特征度量既没有数量表示也没有次序关系。例如,电路中的开和关;医疗诊断中的“+”和“-”;天气中的晴天和雨天,等等。为了对模式进行分类,需要定义相似性测度来度量各模式之间的相似性和差异性。一种方法是将每一个样本看成m维特征空间的一个点,并在该空间定义距离,距离较近的点归为一类,距离较远的点划分为不同的类。另一种方法是利用相似系数,特征越接近的样本之间的相似系数越大(接近于1),把它们归为一类;反过来,彼此无关的样本之间的相似系数接近于0,把它们划分为不同的类。在聚类分析中正确选择距离与相似系数是非常重要的,它直接影响到分类的效果。

1.距离用dij表示第i个样本与第j个样本之间的距离,一般要求距离满足三个条件(即距离三公理):

(1)非负性:dij≥0(i,j),当且仅当第i个样本与第j个样本的各个特征相同时,dij=0;

(2)对称性:dij=dji(i,j);

(3)三角不等式:(6-1)在模式识别中定义的有些距离并不满足“三角不等式”,只是在广义的角度上也称它为距离。在有些场合,“三角不等式”加强为(6-2)第5章已经给出了几种常用的距离,包括欧几里德(Euclidean)距离、加权欧几里德距离、汉明(Haming)距离、马氏(Mahalanobis)距离、明可夫斯基(Minkowsky)距离和切比雪夫(Chebyshev)距离等。

2.相似系数用cij表示向量yi与yj的相似系数,一般规定:

(1)cij=±1yi=ayj,a≠0是一常数;

(2)|cij|≤1,对一切i,j;

(3)cij=cji,对一切i,j,其中,|cij|越接近于1,yi与yj的关系越密切。当特征用连续的量来表示时,常用的相似系数有如下几种。

1)夹角余弦夹角余弦是受相似形的启发而产生的。向量(xi1,xi2,…,xin)T与(xj1,xj2,…,xjn)T之间的夹角余弦的定义为(6-3)

2)相关系数相关系数是将数据标准化后的夹角余弦,即(6-4)其中,为第k个分量的平均值(k=1,2,…,n)。可以借助于相似系数来定义距离,例如:(6-5)

3)指数相似系数指数相似系数定义为(6-6)其中,为相应分量的方差。指数相似系数不受量纲变化的影响。

4)特征向量的各分量为非负时的几种相似系数当特征向量的各分量非负时,还有下列几种相似系数:(6-7)(6-8)(6-9)

5)列联系数和关联系数对于名义量,它们之间的相似系数通过列联表来定义。设名义量yi取值是t1,t2,…,tp,yj取值是r1,r2,…,rq,用nkl表示yi取tk、yj取rl的样本数,列成表6-1的形式,称为列联表。令(6-10)其中(6-11)(6-12)(6-13)利用χ2可以定义名义量之间的相似系数:列联系数(6-14)关联系数(6-15)(6-16)(6-17)表6-1列联表6.1.2聚类准则在模式分类中,可以有多种不同的聚类方法,将未知类别的N个样本划分到m类中去,从而,需要确定一种聚类准则来评价各种聚类方法的优劣。事实上,聚类的优劣只是就某种评价准则而言的,很难找到对各种准则均表现优良特性的聚类方法。

聚类准则的确定主要有两种方式:

(1)试探方式。凭直观和经验,针对实际问题给定一种模式相似性测度的阈值,按最近邻规则指定待分类样本属于某一类别。例如,以欧氏距离作相似性的度量,将一个样本分到某一类时,凭直观和经验规定一个距离阈值作为聚类的判别准则。

(2)聚类准则函数法。定义一种聚类准则函数J,其函数值与样本的划分有关,当J取得极值时,就认为得到了最佳划分。常用的聚类准则函数为误差平方和准则与类间距离和准则。假设有N个样本,在某种相似性测度的准则下属于类ω1,ω2,…,ωm,类ωi中有Ni个样本。

1.误差平方和准则误差平方和准则也可以称为类内距离准则,是一种简单而又应用广泛的聚类准则。类ωi的均值为(6-18)误差平方和定义为(6-19)

J是样本与聚类中心的函数,表示各样本到其被划归类别的中心的距离之平方和。对应一种划分,可求得一个误差平方和J。以误差平方和作为准则时,目的就是要找到使J值最小的那种划分。误差平方和准则适用于同类样本比较密集,各类样本数目相差不大,且类间距离较大的情况。当各类样本数相差很大且类间距离较小时,采用误差平方和准则,就有可能将样本数多的一类拆成两类或多类,从而出现错误聚类。

2.类间距离和准则

全部样本的均值μ为(6-20)类间距离和定义为(6-21)加权的类间距离和定义为(6-22)对应一种划分，可求得一个类间距离和。类间距离和准则是找到使类间距离和达到最大的那种划分。6.2基于试探的聚类算法确定一种聚类准则后,每一种分类方法对应于一个J值,其中使J取得极值的分类,就被认为是最佳分类。这种处理方式的计算量太大,可以对某些关键性的参数进行试探性地选取,使聚类准则函数达到最优,这类方法可称为基于试探的聚类算法。6.2.1基于最近邻规则的试探法设待分类样本集为{x1,x2,…,xN},按最近邻规则进行聚类,算法具体步骤如下:

(1)选取任意一个样本作为第一个聚类中心z1,例如,令ω1类的中心z1=x1,选定一非负的类内距离阈值T。

(2)计算下一个样本x2到z1的距离d21。若d21>T,则建立一新的聚类中心z2,且ω2类的中心z2=x2;若d21≤T,则认为x2在以z1为中心的邻域中,即x2属于ω1类。

(3)假定已有m类的中心z1,z2,…,zm,计算尚未确定类别的样本xi到m类中心zj(j=1,2,…,m)的距离dij。如果所有的dij均满足dij>T,则建立一新的聚类中心zm+1,且ωm+1类的中心zm+1=xi;否则将xi划分到距离其最近的聚类中心所代表的类中。

(4)检查是否所有的样本已经确定类别,如果都已确定类别,则转下一步;否则返回(3)。

(5)按照某种聚类准则评价聚类结果,如果不满意,则重新选取第一个聚类中心和类间距离阈值T,返回(2);如果满意,则算法结束。这种方法的聚类结果与第一个聚类中心的选取、待分类样本的排列次序、阈值T的大小以及样本分布的几何特性有关。图6-1表示了距离阈值T的大小和初始聚类中心位置对聚类结果的影响。图6-1距离阈值和初始类心对聚类结果的影响6.2.2最大最小距离聚类算法最大最小距离聚类算法是另一种简单的试探法,以类间距离最大作为选取新的聚类中心的条件,以最小距离原则进行样本归类。这种算法通常采用欧氏距离,算法具体步骤如下:

(1)选取任意一个样本作为第一个聚类中心z1。

(2)选取距离z1最远的样本作为第二个聚类中心z2。

(3)计算所有未作为聚类中心的样本xi与z1、z2的距离di1,di2,并设di=min(di1,di2),若存在则建立第三个聚类中心z3,且z3=xl。其中:d(z1,z2)为z1与z2之间的距离;θ可用试探法取为一固定分数,例如,。(4)假定已有m个聚类中心z1,z2,…,zm,计算尚未作为聚类中心的各样本xi到m类中心zj(j=1,2,…,m)的距离dij,并计算如果dJ>θ·d(z1,z2),则建立第m+1个聚类中心zm+1,且zm+1=xJ,并转(4);否则转下一步。

(5)将全部样本按最近距离原则划分到各类中。

(6)按照某种聚类准则评价聚类结果,如果不满意,则重新选取第一个聚类中心和θ值,返回(2);如果满意,则算法结

【例6.1】

10个样本数据如图6-2所示,用最大最小距离聚类算法对样本集分类。

解

(1)给定θ=1/2,选取任意一个样本作为第一个聚类中心z1,令z1=x1。

(2)计算其他样本到z1的距离,可得x6距离z1最远,则建立第二个聚类中心z2=x6。

(3)计算所有未作为聚类中心的样本与z1、z2的距离,根据最大最小距离聚类算法,得到第三个聚类中心z3=x7。

(4)判断出不再有新的聚类中心,将全部样本按最近距离原则划分到各类中,得到{x1,x3,x4}为第一类,{x2,x6}为第二类,{x5,x7,x8,x9,x10}为第三类。

(5)通过直观判断,认为本次分类结果比较合理,对样本集的分类完成。图6-2最大最小距离聚类算法示例6.3层次聚类法

6.3.1层次聚类法概述层次聚类法(HierarchicalClusteringMethod)又称为系统聚类法,是一种常用的聚类方法。这种方法的基本思想是:首先将N个样本各自看成一类,计算类与类之间的距离,选择距离最小的一对合并成一个新类;计算新类和其他类之间的距离,再将距离最近的两类合并;这样每次减少一类,直至所有的样本划分成两类为止,或者直到满足分类要求。层次聚类算法的具体步骤如下:

(1)初始分类。假设有N个样本,每个样本自成一类,则有N类:G01,G02,…,G0N(Gki表示第k次合并时的第i类,此步k=0)。(2)计算各类之间的距离,得m×m维的距离矩阵Dk,m为类别个数(初始时m=N,k=0)。

(3)已求得距离矩阵Dk,找出Dk中类间距离最小的元素,如果它对应着Gki和Gkj,则将类Gki与Gkj合并为一类,由此得到新的分类Gk+11,Gk+12,…,并令m=m－1,计算距离矩阵Dk+1。

(4)若Dk+1中类间距离最小值大于距离阈值T,则算法停止,所得分类即为聚类结果(或者,如果所有的样本被聚成两类,则算法停止);否则转(3)。层次聚类法将样本逐步聚类,类别由多到少。层次聚类算法的特点是在聚类的过程中类心不断地调整,但样本一旦划到某个类以后就不会再改变了。6.3.2类与类之间的距离层次聚类算法中,需要计算各类之间的距离构成距离矩阵。类与类之间的距离有许多定义的方法,例如可定义为两类之间最近的距离,或者定义为两类重心之间的距离等,采用不同的定义就产生了层次聚类的不同过程。下面介绍常用的8种类间距离定义方法。

1.最短距离法用dij表示样本xi和样本xj之间的距离,G1,G2,…表示类,定义类与类之间的距离为两类相距最近的样本之间的距离,用Dpq表示类Gp与类Gq的距离,则(6-23)若Gpq是Gp与Gq合并而得,则递推可得Gi与Gpq的距离为(6-24)

2.最长距离法最长距离法就是类与类之间的距离用两类样本之间最远的距离来表示,即(6-25)若Gpq是Gp与Gq合并而得,则递推可得Gi与Gpq的距离为(6-26)

3.中间距离法

设某一步将Gp与Gq合并为类Gpq,需要计算Gpq与任意一类Gi的距离。不失一般性,假设Diq>Dip。按最短距离法,Di,pq=Dip;按最长距离法,Di,pq=Diq。如图6-3所示,三角形的三个边是Dip、Diq

、Dpq,直观上看,在Dip与Diq之间,选择边Dpq的中线为好。图6-3中间距离法示意图由初等几何可知,中线长度的平方等于。若把这个中线长度作为类Gpq与类Gi之间的距离Di,pq,则有递推公式:(6-27)

Di,pq介于最短距离和最长距离之间。由于式(6-27)中出现的全是距离的平方,为了计算方便,在层次聚类中,若采用中间距离法,一般用距离的平方代替距离,进行比较。中间距离法还可以推广为更一般的形式,即(6-28)其中,－1/4≤β≤0。

4.重心法重心法用一个类的重心(该类样本的均值)代表该类,类与类之间的距离就用重心之间的距离来表示。设Gp与Gq的重心分别是xp和xq,则Gp与Gq之间的距离是Dpq=d(xp,xq)。设某一个类Gp与Gq的重心分别是xp和xq,它们的样本数分别为np与nq,将类Gp与Gq合并为Gpq,则类Gpq的样本数为npq=np+nq,它的重心xpq为(6-29)进一步假设类Gi的重心为xi。采用欧氏距离时,类Gi与Gpq的距离满足:(6-30)其中,(6-31)则(6-32)式(6-32)是重心法的递推公式。

5.类平均距离法类平均距离法是将两类之间的距离平方定义为这两类样本两两之间的距离平方的平均,即(6-33)将类Gp与Gq合并为Gpq,由式(6-33)可得,类Gk与Gpq的距离平方为(6-34)于是,类平均距离法的递推公式为(6-35)类平均距离法充分利用各样本的信息,从而成为层次聚类法中效果比较好的方法之一。

6.可变类平均法可变类平均法是在类平均距离法的递推公式(6-35)中加入Dpq的影响,把递推公式修正为(6-36)()

7.可变法

可变法是在中间距离法的推广递推公式(6-28)中将前两项的系数也依赖于β,即(6-37)可变类平均法与可变法的分类效果依赖于β的选择,有一定的主观性,在实际中使用并不多。

8.离差平方和法设将N个样本分成k类G1,G2,…,Gk,用xit表示Gt中的第i个样本,nt表示Gt中的样本个数,xt是Gt的重心,则在Gt中的样本的类内离差平方和为(6-38)聚类过程中,将两类合并,离差平方和就会增大。把两类合并所增加的离差平方和定义为两类距离平方,即将类Gp与Gq合并为Gpq时,定义D2pq=Spq－Sp－Sq,且有(6-39)可以证明,离差平方和法有递推公式如下:(6-40)公式中各符号意义同前。以上给出了8种类与类之间的距离,并且得到不同的递推公式,这些递推公式具有统一的形式:(6-41)其中,系数αp、αq、β、γ对于不同的方法有不同的取值。表6-2列出了上述8种方法中四个参数的取值。表6-2递推公式中的参数

方法αpαqβγ最短距离法1/21/20-1/2最长距离法1/21/201/2中间距离法1/2½－1/4≤β≤00重心法np/npqnq/npq-αpαq0类平均距离法np/npqnq/npq00可变类平均法<10可变法(1－β)/2(1－β)/2<10离差平方和法06.4动态聚类法

6.4.1动态聚类法的基本思想在层次聚类法中,样本一旦归入某个类以后就不再改变了,因此要求分类方法的准确度要高。动态聚类法就是,先选择一些初始聚类中心,让样本按某种原则划分到各类中,得到初始分类;然后,用某种原则进行修正,直到分类比较合理为止。动态聚类法的流程框图如图6-4所示,其中,每一部分都有很多种方法,不同的组合方式可得到不同动态聚类算法。动态聚类法有三个要点:

(1)选定某种相似性测度作为样本间的相似性度量;

(2)确定某个评价聚类结果质量的准则函数;

(3)给定某个初始分类,用迭代的算法找出使准则函数取极值的聚类结果。下面简要介绍几种典型的动态聚类法:K均值算法和迭代自组织的数据分析算法,以及基于LBG算法的聚类分析。图6-4动态聚类法的流程框图6.4.2

K均值算法

K均值算法使用的聚类准则函数是误差平方和准则,通过反复迭代优化聚类结果,使所有样本到各自所属类别的中心的距离平方和达到最小。

K均值算法的步骤如下:

(1)任选K个初始聚类中心:z(1)1,z(1)2,…,z(1)K,其中,上角标表示聚类过程中的迭代运算次数。

(2)假设已进行到第r次迭代。若对某一样本x有(6-42)则x∈S(r)j。其中,S(r)j是以z(r)j为聚类中心的样本子集。以此种方法,即最小距离原则,将全部样本分配到K个聚类中。

(3)计算重新分类后的各聚类中心:(6-43)式中,n(r)j为S(r)j中所包含的样本数。

(4)若z(r+1)j=z(r)j,j=1,2,…,K,则结束;否则转(2)。因为在第(3)步要计算K个聚类的样本均值,故称做K均值算法。该算法的特点是选一批代表点(初始聚类中心)后,计算所有样本到聚类中心的距离,将所有样本按最小距离原则划分类别,形成初始分类,再重新计算各聚类中心,这是一种批处理方法。另一种方法是逐个处理法,每读入一个样本就把它归于距离最近的一类,形成新的分类并计算新的聚类中心,然后再读入下一个样本归类,即每个样本的归类都改变一次聚类中心。

K均值算法的分类结果与所选聚类中心的个数K和初始聚类中心选择有关,因此在实际应用中需试探不同的K值和选择不同的初始聚类中心。初始聚类中心的选取方法一般有如下几种:

(1)用样本集的前K个样本作为初始聚类中心。

(2)将全部样本随机分成K类,计算每类重心,把这些重心作为每类的初始聚类中心。

(3)凭经验选初始聚类中心。根据问题的性质、数据分布,选择从直观上看来较合理的K个初始聚类中心。

(4)按密度大小选代表点。以每个样本作为球心,以d为半径作球形,落在球内的样本数称为该点的密度,并按密度大小排序。首先选密度最大的样本点作为第一个代表点,即第一个初始聚类中心。再考虑第二大密度点,若第二大密度点距第一个代表点的距离大于d1(预先规定的一个正数),则把第二大密度点作为第二个代表点,否则不能作为代表点。这样按密度大小依次考察下去,选择K个样本作为初始聚类中心。

(5)将相距最远的K个样本作为初始聚类中心。此外,K均值算法的分类结果受到样本的几何性质和读入次序的影响。如果样本的几何特性能使它们形成几个相距较远的孤立区,那么算法一般能够收敛。

【例6.2】模式分布如图6-5所示,试用K均值法进行聚类。取K=2。图6-5

K均值算法例题样本集解(1)选取z(1)1=x1=(0,0)T,z(1)2=x2=(1,0)T。

(2)因为‖x1－z(1)1‖<‖x1－z(1)2‖,所以x1∈S(1)1;因为‖x2－z(1)1‖>‖x2－z(1)2‖,所以x2∈S(1)2;因为‖x3－z(1)1‖<‖x3－z(1)2‖,所以x3∈S(1)1;

得S(1)1={x1,x3}

(3)计算新的聚类中心

(4)因为z(2)i≠z(1)i,i=1,2,所以回到(2)按新的聚类中心重新分类(用(2′)表示)。(2′)由新的聚类中心,有，所以，所以得(3′)计算新的聚类中心

(4′)因为z(3)i≠z(2)i,i=1,2,所以回到(2′)(用(2″)表示)。

(2″)按新的聚类中心进行分类,分类结果与上一次迭代相同S(3)1=S(2)1,S(3)2=S(2)2。

(3″)计算聚类中心。

(4″)因为聚类中心与上一次相同,算法结束。6.4.3迭代自组织的数据分析算法迭代自组织的数据分析算法(IterativeSelfOrganizingDataTechniqueAlgorithm)简称ISODATA算法。类似于K均值算法,

ISODATA算法的聚类中心也是通过样本均值的迭代运算来决定的。与K均值算法不同的是,ISODATA算法增加了一些试探性步骤和人机交互的“自组织”处理方式,在迭代过程中可将一类分成两类,亦可能将两类合为一类,即分裂和合并处理。迭代自组织算法流程图如图6-6所示。图6-6迭代自组织算法流程图

ISODATA算法的具体步骤如下:

(1)读入包含N个模式的样本集{x1,x2,…,xN},选择m个初始聚类中心{z1,z2,…,zm}。其中,m不一定等于预期的聚类中心数目。参数设计如下:

K——预期的聚类中心数目;

θN——一个聚类中最少的样本数目,即如少于此数就不作为一个独立的聚类;

θs——聚类中样本单个分量的标准方差的上限,若某个聚类中样本单个分量的标准方差的最大值大于此数,则可能分裂该聚类的中心。

θc——两聚类中心之间的最小距离,如小于此数,合并两个聚类;

L——在一次迭代过程中,最多可以合并的聚类中心的对数;

I——最大的迭代次数。

(2)根据最小距离准则,将样本x1,x2,…,xN分别归入最近的聚类,若(6-44)即距离d(x,zj)最小,则x∈Sj。其中,Sj是以zj为聚类中心的样本子集。

(3)如果Sj(j=1,2,…,m)中的样本数目Nj<θN,则取消Sj,令m=m－1,并转入(2);否则转入下一步。

(4)调整聚类中心:(6-45)(5)计算各聚类中样本与聚类中心之间的平均距离:(6-46)(6)计算全部模式样本与相应聚类中心之间的平均距离:(6-47)

(7)判断分裂、合并和迭代运算等步骤:①如果迭代运算次数已达最大的迭代次数I,即最后一次迭代,令θc=0,转入(11),结束迭代运算。②如聚类中心的数目小于等于规定值的一半,即m≤K/2,则转入(8),分裂已有的聚类。③如迭代运算的次数是偶数,或者m≥2K,则不进行分裂处理,转入(11);否则,转入(8),分裂已有的聚类。分裂处理:

(8)计算聚类Sj中样本的标准方差向量:(6-48)向量σj的第i个分量为(6-49)其中:d为样本的维数;样本xk=(xk1,xk2,…,xkd)T;Sj的中心zj=(zj1,zj2,…,zjd)T。

(9)找出标准方差向量σj=(σj1,σj2,…,σjd)T中的最大分量,记为σj,max,j=1,2,…,m。

(10)检测最大分量集{σj,max,j=1,2,…,m}中所有的元素,如σj,max>θs(该值给定),同时又满足以下两个条件中的一个:①和Nj>2(θN+1),即Sj中样本总数超过规定值的一倍以上;②m≤K/2,则将Sj的中心zj分裂为两个新的聚类中心z+j和z－j,且令m=m+1,其中,z+j和z－j的计算如下:①选定一个p值,0<p≤1;②令γj=pσj或γj=(0,…,pσj,max,…,0)T;③z+j=zj+γj,z－j=zj－γj。如果本步完成了分裂运算,则转入(2),否则转入(11)。合并处理:

(11)计算全部聚类中心之间的距离:；(6-50)

(12)比较Dij与θc值,将Dij<θc的前L个值递增排列,即其中,Di1j1≤Di2j2≤…≤DiLjL。

(13)从最小的Di1j1开始,对于每个Diljl,合并相应的两个聚类中心zil和zjl,新的聚类中心为(6-51)并令m=m－L。

(14)如果迭代运算次数已达最大的迭代次数I,即最后一次迭代,则算法结束;否则,如果需要由操作者改变输入参数,转入(1),设计相应的参数;否则,转入(2)。到了本步运算,迭代运算的次数加1。6.4.4基于LBG算法的聚类分析

LBG算法是K均值算法的推广。LBG算法是矢量量化中的一种重要码书生成算法,先选取初始码书,通过对训练样本的量化、聚类、迭代,产生局部最优的码书。这里,把LBG算法应用于聚类分析,具体步骤如下:

(1)设样本集为{x1,x2,…,xN}。给定初始聚类中心{z(0)i|i=1,2,…,K},并置r=0,设起始平均失真D(-1)→∞,给定计算停止门限ε(0<ε<1)。

(2)设已进行到第r次迭代。若对每一样本x有(6-52)则x∈S(r)j,其中,S(r)j是以z(r)j为聚类中心的样本子集。以此种方法将全部样本分配到K个聚类中。

(3)计算平均失真与相对失真。平均失真为(6-53)其中,距离d(z(r)j,xi)取为欧氏距离。相对失真为(6-54)若≤ε,则停止,当前聚类为设计好的最终聚类;否则,进行(4)。

(4)计算各聚类中心的新向量值(6-55)式中,Nj为S(r)j中所包含的样本数,并置r=r+1,返回到(2),将全部样本重新分类,重复迭代计算。初始聚类中心的选取算法有随机法、分裂法等,其中分裂法效果显著。随机法就是随机地选取K个样本作为初始聚类中心。分裂法将在6.5节中介绍。事实上,在矢量量化中,最终聚类的各个聚类中心组成码书。6.5分解法

在层次聚类中,类别由多到小。分解法的思想是类别由小到多,也就是说,开始把全体样本看成一类,然后分成两类、三类……直至所有的样本各自为一类,或者分类比较合理为止。6.5.1一分为二法一分为二法是将一个聚类分解为两子类,然后对其子类又一分为二。设某类G中有n个样本,它的两个子类G1、G2各有n1和n2个样本;两类重心为z1和z2,G的重心为z。类G、G1与G2的离差平方和分别为(6-56)(6-58)一般要求S1+S2尽可能的小,或S－(S1+S2)尽可能的大。可以证明:或者，(6-59)以E=S－(S1+