模式识别级研给学生的终.ppt

4.重心距离：两类的均值之间的距离 5.类平均距离：两类中各个元素两两之间的距离平方相加后取平均值 上式推广为一般情况： 6.离差平方和： (1)设N个样本原分q类，则定义第i类内的离差平方和为： (2)离差平方和增量：设样本已分成ωp、ωq两类，若把ωp、ωq合并为ωr类，则定义离差平方： 二、系统聚类算法 (1)初始分类。 假设有N个样本，每个样本自成一类，则有N类：G1(0)，G2(0)，…，GN(0){Gi(k)表示第k次合并时的第i类，此步k=0}。 　 (2)计算各类之间的距离, 得m×m维的距离矩阵D(k), m为类别个数(初始时m=N，k=0)。  (3) 找出距离矩阵D(k)中类间距离最小的元素，如果它对应着Gi(k)和Gj(k)，则将类Gi(k)与Gj(k)合并为一类，由此得到新的聚类G1(k+1)，G2(k+1)，…。令k=k+1，m=m－1，计算距离矩阵D(k)。 (4) 若D(k)中类间距离最小值大于距离阈值T，则算法停止，所得分类即为聚类结果(或者，如果所有的样本被聚成两类, 则算法停止)；否则，转(3)。 系统聚类法将样本逐步聚类，类别由多到少。 系统聚类算法的特点是在聚类过程中类的中心不断地调整，但样本一旦归到某个类以后就不会再改变了。  三、系统聚类举例，如下图所示 (1)设全部样本分为6类； (2)作距离矩阵D(0)，见下表； ω1 ω2 ω3 ω4 ω5 ω2 9 ω3 1 16 ω4 49 16 64 ω5 25 4 36 4 ω6 64 25 81 1 9 (3)求最小元素； (4)把ω1,ω3合并ω7=(1,3)；ω4,ω6合并ω8=(4,6)； (5)作距离矩阵D(1)； ω7 ω2 ω8 ω2 9 ω8 49 16 ω5 25 4 4 (6)若合并的类数没有达到要求，转(3)；否则停止。 (3)求最小元素。 (4)ω8,ω5,ω2合并, ω9=（2,5,4,6）。 4.3 分解聚类 分解聚类：把全部样本作为一类，然后根据相似性、相邻性分解。 通俗地说，分解聚类法是首先把全部样本当作一类， 然后再分为两类，三类， ?，直至所有的样本自成一类为止。 目标函数：两类均值(重心)方差 N：总样本数， N1：ω1类样本数， N2：ω2类样本数。 下面介绍一分为二的方法： 设有N个样本当作一类记为ω, 将它分成两个子类ω1 和ω2且各有N1 和N2个样本, 记ω, ω1, ω2 的重心分别为 , , 。 ω, ω1, ω2 的离差平方和分别为： “一分为二”的思想就是要使S1+S2 尽可能小, 或使S- S1- S2 尽可能大。 可以证明(此略)： N：总样本数， N1：ω1类样本数， N2：ω2类样本数。 把上面两类均值(重心)的方差E作为目标函数，选择某种分法使得E达到最大。 分解聚类框图 初始分类 调整分类方案 最终结果 目标函数E 达到最优？ 对分法(一分为二法中的一种)： 一开始所有N个样品均在ω1 中，然后找一个样品把它归入ω2 使E达到最大，接着再找第二个样品归入ω2 使E 达到最大，如此继续下去(某样品一旦归入ω2后，该样品在以后的划分中就不再回到ω1) 。 令E(k)表示ω2 中有k个样品，那么一定存在k*使得： V(k*)= max E(k) 于是将前k*次进入ω2 的样品归为一类，其余n- k*个样品为另一类。再将上述步骤应用于每个子类直至每个样品都自成一类。 1≤k≤N-1 ? 讨论： 2、第二种情况：Σi＝ Σ相等，即各类协方差相等。 未知x，把x与各类均值相减，把x归于最近一类。最小距离分类器。 讨论：针对ω1，ω2二类情况，如图： 3、第三种情况(一般情况)：Σ?为任意，各类协方差矩阵不等，二次项xT Σ? x与i有关。所以判别函数为二次型函数。 协方差矩阵不等，决策面是二次曲面(可能是超球面、超椭球面、超双曲面、超抛物面)。当x是二维模式时，判决面为二次曲线。 协方差矩阵相等，决策面是超平面。当x是二维模式时，决策面为直线。 下面各图示出了二维特征空间两类问题的决策面的各种形式，图中的圆、椭圆表示等概密点轨迹。 (a)图：由于ω2类的方差小， ω2类的模式更集中于μ2，决策面是包围μ2的一个圆 （b)图：决策面是包围μ2一个椭圆 R1 R2 R1 (c)图： 类ω1和ω2的x1的方差相同，但ω1的x2方差较ω2的x2方差大，从而x2值较大的模式更可能来自ω1类，