模式识别第2,3章聚类分析报告

1、第二章 聚类分析2.1 聚类分析的相关概念定义 对一批没有标出类别的模式样本集，按照样本之间的相似程度分类，相似的归为一类，不相似的归为另一类，这种分类称为聚类分析，也称为无监督分类。模式相似/分类的依据 把整个模式样本集的特征向量看成是分布在特征空间中的一些点，点与点之间的距离即可作为模式相似性的测量依据。聚类分析是按不同对象之间的差异，根据距离函数的规律（大小）进行模式分类的。聚类分析的有效性 聚类分析方法是否有效，与模式特征向量的分布形式有很大关系。若向量点的分布是一群一群的，同一群样本密集（距离很近），不同群样本距离很远，则很容易聚类；若样本集的向量分布聚成一团，不同群的样本混在一起，

2、则很难分类；对具体对象做聚类分析的关键是选取合适的特征。特征选取得好，向量分布容易区分，选取得不好，向量分布很难分开。两类模式分类的实例：一摊黑白围棋子 选颜色作为特征进行分类，用“1”代表白，“0”代表黑，则很容易分类；选大小作为特征进行分类，则白子和黑子的特征相同，不能分类（把白子和黑子分开）。特征选择的维数在特征选择中往往会选择一些多余的特征，它增加了维数，从而增加了聚类分析的复杂度，但对模式分类却没有提供多少有用的信息。在这种情况下，需要去掉相关程度过高的特征（进行降维处理）。降维方法设有N个样本，它们的特征维数是n，则有n*n维的相关矩阵R = rij nxn 其中，rij是第i维与

3、第j维特征之间的相关系数： 这里：ii和jj分别是第i个和第j个分量的标准差，ij是第i个和第j个分量的协方差。分析：（1）根据相关系数的性质：（利用柯西不等式证明）（2）rij=0：表示两个分量完全不相关（3）rij=1：表示两个分量完全相关结论：若rij->1，则表明第i维特征与第j维特征所反映的特征规律接近，因此可以略去其中的一个特征，或将它们合并为一个特征，从而使维数降低一维。模式对象特征测量的数字化计算机只能处理离散的数值，因此根据识别对象的不同，要进行不同的数据化处理。连续量的量化：用连续量来度量的特性，如长度、重量、面积等等，仅需取其量化值；量级的数量化：度量时不需要详尽的

4、数值，而是相应地划分成一些有次序的量化等级的值。l 病人的病程 0 代表病程 <= 1个月 1 代表1个月< 病程 <= 6个月2 代表6个月< 病程 <= 12个月 3 代表病程 > 12个月名义尺度：指定性的指标，即特征度量时没有数量关系，也没有明显的次序关系，如黑色和白色的关系，男性和女性的关系等，都可将它们分别用“0”和“1”来表示。超过2个状态时，可用多个数值表示。2.2 模式相似性的测度和聚类准则2.2.1 相似性测度目的：为了能将模式集划分成不同的类别，必须定义一种相似性的测度，来度量同一类样本间的类似性和不属于同一类样本间的差异性。欧氏距离设

5、x和z为两个模式样本，其欧氏距离定义为：D = | x - z | 例：x = (x1, x2)，z = (z1, z2)，则 显然，模式x和z之间的距离越小，它们越相似。欧氏距离的概念和习惯上距离的概念是一致的。马氏距离设x是模式向量，m是均值向量，C为模式总体的协方差矩阵，则马氏距离的表达式： 特点：排除了模式样本之间的相关性问题：协方差矩阵在实际应用中难以计算。一般化的明氏距离模式样本向量xi和xj之间的明氏距离表示为：其中xik和xjk分别表示xi和xj的第k各分量。显然，当m=2时，明氏距离即为欧氏距离。特例：当m=1时，亦称为街坊距离。角度相似性函数表达式：，它表示模式向量x和z之

6、间夹角的余弦，也称为x的单位向量与z的单位向量之间的点积。特点：反映了几何上相似形的特征，对于坐标系的旋转、放大和缩小等变化是不变的。当特征的取值仅为(0,1)两个值时的特例特例：当特征的取值仅为(0, 1)两个值时，夹角余弦度量具有特别的含义，即当模式的第i个分量为1时，认为该模式具有第i个特征；当模式的第i个分量为0时，认为该模式无此特征。这时，xTz的值就等于x和z这两个向量共同具有的特征数目。同时，= x中具有的特征数目和z中具有的特征数目的几何平均因此，在特征取值为0和1的二值情况下，S(x, z)等于x和z中具有的共同特征数目的相似性测度。2.2.2 聚类准则有了模式的相似性测度，

7、还需要一种基于数值的聚类准则，能将相似的模式样本分在同一类，相异的模式样本分在不同的类。试探方法凭直观感觉或经验，针对实际问题定义一种相似性测度的阈值，然后按最近邻规则指定某些模式样本属于某一个聚类类别。例如对欧氏距离，它反映了样本间的近邻性，但将一个样本分到不同类别中的哪一个时，还必须规定一个距离测度的阈值作为聚类的判别准则。聚类准则函数法依据：由于聚类是将样本进行分类以使类别间可分离性为最大，因此聚类准则应是反映类别间相似性或分离性的函数；由于类别是由一个个样本组成的，因此一般来说类别的可分离性和样本的可分离性是直接相关的；可以定义聚类准则函数为模式样本集x和模式类别Sj, j=1,2,c

8、的函数，从而使聚类分析转化为寻找准则函数极值的最优化问题。一种聚类准则函数J的定义其中，c为聚类类别的数目，Sj为第j个类别的样本集合，为属于Sj集合的样本均值向量，Nj为Sj中的样本数目。这里，以均值向量mj为Sj中样本的代表。J代表了属于c个聚类类别的全部模式样本与其相应类别模式均值之间的误差平方和。对于不同的聚类形式，J值是不同的。目的：求取使J值达到最小的聚类形式。2.3 基于试探的聚类搜索算法2.3.1 按最近邻规则的简单试探法算法 给定N个待分类的模式样本x1, x2, , xN，要求按距离阈值T，将它们分类到聚类中心z1, z2, 。第一步：任取一样本xi作为一个聚类中心的初始值

9、，例如令z1 = x1，计算D21 = | x2 - z1 |，若D21 > T，则确定一个新的聚类中心z2 = x2，否则x2属于以z1为中心的聚类；第二步：假设已有聚类中心z1、z2，计算 D31 = | x3 - z1 |，D32 = | x3 - z2 |，若D31 > T且D32 > T，则得一个新的聚类中心z3 = x3，否则x3属于离z1和z2中的最近者······如此重复下去，直至将N个模式样本分类完毕。讨论 这种方法的优点：计算简单，若模式样本的集合分布的先验知识已知，则可通过选取正确的阈值和起始点

10、，以及确定样本的选取次序等获得较好的聚类结果。在实际中，对于高维模式样本很难获得准确的先验知识，因此只能选用不同的阈值和起始点来试探，所以这种方法在很大程度上依赖于以下因素：第一个聚类中心的位置；待分类模式样本的排列次序；距离阈值T的大小；样本分布的几何性质。2.3.2 最大最小距离算法基本思想：以试探类间欧氏距离为最大作为预选出聚类中心的条件。10个模式样本点：x1(0 0), x2(3 8), x3(2 2), x4(1 1), x5(5 3), x6(4 8), x7(6 3), x8(5 4), x9(6 4), x10(7 5)第一步：选任意一个模式样本作为第一个聚类中心，如z1 =

11、 x1；第二步：选距离z1最远的样本作为第二个聚类中心。经计算，| x6 - z1 |最大，所以z2 = x6第三步：逐个计算各模式样本xi, i = 1,2,N与 z1, z2之间的距离，即Di1 = | xi - z1 |，Di2 = | xi z2 |并选出其中的最小距离min(Di1, Di2)，i = 1,2,N第四步：在所有模式样本的最小值中选出最大距离，若该最大值达到|z1 - z2 |的一定比例以上，则相应的样本点取为第三个聚类中心z3，即若maxmin(Di1, Di2), i = 1,2,N >|z1 - z2 |，则z3 = xi否则，若找不到适合要求的样本作为新的

12、聚类中心，则找聚类中心的过程结束。这里，可用试探法取一固定分数，如1/2。在此例中，当i=7时，符合上述条件，故z3 = x7第五步： 若有z3存在，则计算maxmin(Di1, Di2, Di3), i = 1,2,N。若该值超过|z1 - z2 |的一定比例，则存在z4，否则找聚类中心的过程结束。在此例中，无z4满足条件。第六步：将模式样本xi, i = 1,2,N按最近距离分到最近的聚类中心：z1 = x1：x1, x3, x4为第一类z2 = x6：x2, x6为第二类z3 = x7：x5, x7, x8, x9, x10为第三类，最后，还可在每一类中计算个样本的均值，得到更具代表性的

13、聚类中心。2.4 系统聚类法基本思想：将模式样本按距离准则逐步分类，类别由多到少，直到获得合适的分类要求为止。算法：第一步：设初始模式样本共有N个，每个样本自成一类，即建立N类，。计算各类之间的距离（初始时即为各样本间的距离），得到一个N*N维的距离矩阵D(0)。这里，标号(0)表示聚类开始运算前的状态。第二步：假设前一步聚类运算中已求得距离矩阵D(n)，n为逐次聚类合并的次数，则求D(n)中的最小元素。如果它是Gi(n)和Gj(n)两类之间的距离，则将Gi(n)和Gj(n)两类合并为一类，由此建立新的分类：。第三步：计算合并后新类别之间的距离，得D(n+1)。计算与其它没有发生合并的之间的距

14、离，可采用多种不同的距离计算准则进行计算。第四步：返回第二步，重复计算及合并，直到得到满意的分类结果。（如：达到所需的聚类数目，或D(n)中的最小分量超过给定阈值D等。）距离准则函数进行聚类合并的一个关键就是每次迭代中形成的聚类之间以及它们和样本之间距离的计算，采用不同的距离函数会得到不同的计算结果。主要的距离计算准则：聚类准则函数1.最短距离法：设H和K是两个聚类，则两类间的最短距离定义为：其中，du,v表示H类中的样本xu和K类中的样本xv之间的距离，DH,K表示H类中的所有样本和K类中的所有样本之间的最小距离。递推运算：假若K类是由I和J两类合并而成，则2.最长距离法：设H和K是两个聚类

15、，则两类间的最长距离定义为：其中du,v的含义与上面相同。递推运算：假若K类是由I和J两类合并而成，则3.中间距离法：设K类是由I和J两类合并而成，则H和K类之间的距离为：它介于最长距离和最短距离之间。4.重心法：假设I类中有nI个样本，J类中有nJ个样本，则I和J合并后共有nI+nJ个样本。用nI/(nI+nJ)和nJ/(nI+nJ)代替中间距离法中的系数，得到重心法的类间距离计算公式：5.类平均距离法：若采用样本间所有距离的平均距离，则有：递推运算公式：举例设有6个五维模式样本如下，按最小距离准则进行聚类分析：x1: 0, 3, 1, 2, 0；x2: 1, 3, 0, 1, 0；x3:

16、3, 3, 0, 0, 1；x4: 1, 1, 0, 2, 0；x5: 3, 2, 1, 2, 1；x6: 4, 1, 1, 1, 0作业1.画出给定迭代次数为n的系统聚类法的算法流程框图2.对如下5个6维模式样本，用最小聚类准则进行系统聚类分析：x1: 0, 1, 3, 1, 3, 4；x2: 3, 3, 3, 1, 2, 1；x3: 1, 0, 0, 0, 1, 1；x4: 2, 1, 0, 2, 2, 1；x5: 0, 0, 1, 0, 1, 02.5 动态聚类法基本思想：首先选择若干个样本点作为聚类中心，再按某种聚类准则（通常采用最小距离准则）使样本点向各中心聚集，从而得到初始聚类；然

17、后判断初始分类是否合理，若不合理，则修改分类；如此反复进行修改聚类的迭代算法，直至合理为止。K-均值算法思想：基于使聚类性能指标最小化，所用的聚类准则函数是聚类集中每一个样本点到该类中心的距离平方之和，并使其最小化。第一步：选K个初始聚类中心，z1(1)，z2(1)，zK(1)，其中括号的序号为寻找聚类中心的迭代运算的次序号。聚类中心的向量值可任意设定，例如可选开始的K个模式样本的向量值作为初始聚类中心。第二步：逐个将需分类的模式样本x按最小距离准则分配给K个聚类中心中的某一个zj(1)。假设i=j时，则，其中k为迭代运算的次序号，第一次迭代k=1，Sj表示第j个聚类，其聚类中心为zj。第三步

18、：计算各个聚类中心的新的向量值，zj(k+1)，j=1,2,K。求各聚类域中所包含样本的均值向量：其中Nj为第j个聚类域Sj中所包含的样本个数。以均值向量作为新的聚类中心，可使如下聚类准则函数最小：，在这一步中要分别计算K个聚类中的样本均值向量，所以称之为K-均值算法。第四步：若，j=1,2,K，则返回第二步，将模式样本逐个重新分类，重复迭代运算；若，j=1,2,K，则算法收敛，计算结束。讨论K-均值算法的结果受如下选择的影响：所选聚类的数目；聚类中心的初始分布；模式样本的几何性质；读入次序；在实际应用中，需要试探不同的K值和选择不同的聚类中心的起始值。如果模式样本可以形成若干个相距较远的孤立

19、的区域分布，一般都能得到较好的收敛效果。K-均值算法比较适合于分类数目已知的情况。作业/练习（选k=2,z1(1)=x1,z2(1)=x10,用K-均值算法进行聚类分析）ISODATA算法（迭代自组织数据分析算法）与K-均值算法的比较：K-均值算法通常适合于分类数目已知的聚类，而ISODATA算法则更加灵活；从算法角度看， ISODATA算法与K-均值算法相似，聚类中心都是通过样本均值的迭代运算来决定的；ISODATA算法加入了一些试探步骤，并且可以结合成人机交互的结构，使其能利用中间结果所取得的经验更好地进行分类。基本步骤和思路（1）选择某些初始值。可选不同的参数指标，也可在迭代过程中人为修

20、改，以将N个模式样本按指标分配到各个聚类中心中去。（2）计算各类中诸样本的距离指标函数。（3）（5）按给定的要求，将前一次获得的聚类集进行分裂和合并处理（4）为分裂处理，（5）为合并处理），从而获得新的聚类中心。（6）重新进行迭代运算，计算各项指标，判断聚类结果是否符合要求。经过多次迭代后，若结果收敛，则运算结束。算法：第一步：输入N个模式样本xi, i = 1, 2, , N预选Nc个初始聚类中心，它可以不等于所要求的聚类中心的数目，其初始位置可以从样本中任意选取。预选：K = 预期的聚类中心数目；N = 每一聚类域中最少的样本数目，若少于此数即不作为一个独立的聚类；S = 一个聚类域中样本

21、距离分布的标准差；c = 两个聚类中心间的最小距离，若小于此数，两个聚类需进行合并；L = 在一次迭代运算中可以合并的聚类中心的最多对数；I = 迭代运算的次数。第二步：将N个模式样本分给最近的聚类Sj，假若，即|x-zj|的距离最小，则。第三步：如果Sj中的样本数目Sj<N，则取消该样本子集，此时Nc减去1。（以上各步对应基本步骤（1）第四步：修正各聚类中心第五步：计算各聚类域Sj中模式样本与各聚类中心间的平均距离第六步：计算全部模式样本和其对应聚类中心的总平均距离（以上各步对应基本步骤（2）第七步：判别分裂、合并及迭代运算1.若迭代运算次数已达到I次，即最后一次迭代，则置c =0，转

22、至第十一步。2.若，即聚类中心的数目小于或等于规定值的一半，则转至第八步，对已有聚类进行分裂处理。3.若迭代运算的次数是偶数次，或，不进行分裂处理，转至第十一步；否则（即既不是偶数次迭代，又不满足），转至第八步，进行分裂处理。（以上对应基本步骤（3）第八步：计算每个聚类中样本距离的标准差向量其中向量的各个分量为式中， i = 1, 2, , n为样本特征向量的维数，j = 1, 2, , Nc为聚类数，Nj为Sj中的样本个数。第九步：求每一标准差向量j, j = 1, 2, , Nc中的最大分量，以jmax, j = 1, 2, , Nc代表。第十步：在任一最大分量集jmax, j = 1,

23、2, , Nc中，若有jmax>S ，同时又满足如下两个条件之一：1.和Nj > 2(N + 1)，即Sj中样本总数超过规定值一倍以上，2.，则将zj 分裂为两个新的聚类中心和，且Nc加1。 中对应于jmax的分量加上kjmax，其中；中对应于jmax的分量减去kjmax。如果本步骤完成了分裂运算，则转至第二步，否则继续。（以上对应基本步骤（4）进行分裂处理）第十一步：计算全部聚类中心的距离Dij = | zi - zj |，i = 1, 2, , Nc-1 ，j =i+1, , Nc。第十二步：比较Dij 与c 的值，将Dij <c 的值按最小距离次序递增排列，即式中，。第

24、十三步：将距离为的两个聚类中心和合并，得新的中心为：，k = 1, 2, , L式中，被合并的两个聚类中心向量分别以其聚类域的样本数加权，使为真正的平均向量。（以上对应基本步骤（5）进行合并处理）第十四步：如果是最后一次迭代运算（即第I次），则算法结束；否则，若需要操作者改变输入参数，转至第一步；若输入参数不变，转至第二步。在本步运算中，迭代运算的次数每次应加1。算法结束2.6 聚类结果的评价迅速评价聚类结果，在上述迭代运算中是很重要的，特别是具有高维特征向量的模式，不能直接看清聚类效果，因此，可考虑用以下几个指标来评价聚类效果：聚类中心之间的距离；距离值大，通常可考虑分为不同类；聚类域中的样

25、本数目；样本数目少且聚类中心距离远，可考虑是否为噪声；聚类域样本的距离方差；方差过大的样本可考虑是否属于这一类讨论：模式聚类目前还没有一种通用的放之四海而皆准的准则，往往需要根据实际应用来选择合适的方法。作业1.画出ISODATA算法的流程框图2.试用ISODATA算法对如下模式分布进行聚类分析：x1(0, 0), x2(3,8), x3(2,2), x4(1,1), x5(5,3), x6(4,8), x7(6,3), x8(5,4),x9(6,4), x10(7,5)计算机编程编写ISODATA聚类算法程序，对如下数据进行聚类分析：x1(0, 0), x2(3,8), x3(2,2), x

26、4(1,1), x5(5,3), x6(4,8), x7(6,3), x8(5,4), x9(6,4), x10(7,5)第三章 判别函数3.1 线性判别函数3.1.1 用判别函数分类的概念模式识别系统的主要作用：判别各个模式所属的类别；对一个两类问题的判别，就是将模式x划分成1和2两类。l 描述：两类问题的判别函数（以二维模式样本为例）若x是二维模式样本x = (x1 x2)T，用x1和x2作为坐标分量，得到模式的平面图：这时，若这些分属于1和2两类的模式可用一个直线方程d(x)=0来划分d(x) = w1x1 + w2x2 + w3 = 0其中x1、x2为坐标变量，w1、w2、w3为参数方

27、程，则将一个不知类别的模式代入d(x)，有 若d(x) > 0，则若d(x) < 0，则此时，d(x)=0称为判别函数。用判别函数进行模式分类依赖的两个因素（1）判别函数的几何性质：线性的和非线性的函数。线性的是一条直线；非线性的可以是曲线、折线等；线性判别函数建立起来比较简单（实际应用较多）；非线性判别函数建立起来比较复杂。（2）判别函数的系数：判别函数的形式确定后，主要就是确定判别函数的系数问题。只要被研究的模式是可分的，就能用给定的模式样本集来确定判别函数的系数。3.1.2 线性判别函数n维线性判别函数的一般形式：，其中w0 = (w1, w2, , wn)T称为权向量（或参

28、数向量）, x = (x1, x2, , xn)T。d(x)也可表示为：d(x) = wTx，其中，x = (x1, x2, , xn, 1)T称为增广模式向量，w = (w1, w2, , wn+1)T称为增广权向量。分类问题两类情况：判别函数d(x)：多类情况：设模式可分成1, 2, M共M类，则有三种划分方法多类情况1用线性判别函数将属于i类的模式与不属于i类的模式分开，其判别函数为：i = 1, 2, , M，这种情况称为两分法，即把M类多类问题分成M个两类问题，因此共有M个判别函数，对应的判别函数的权向量为wi, i = 1, 2, , M。图例：对一个三类情况，每一类模式可用一个简

29、单的直线判别界面将它与其它类模式分开。例如对的模式，应同时满足：d1(x)>0，d2(x)<0，d3(x)<0，不确定区域：若对某一模式区域，di(x)>0的条件超过一个，或全部di(x)<0，i = 1, 2, , M，则分类失败，这种区域称为不确定区域(IR)。多类情况2采用每对划分，即i/j两分法，此时一个判别界面只能分开两种类别，但不能把它与其余所有的界面分开。其判别函数为：若dij(x)>0，则重要性质：dij = -dji图例：对一个三类情况，d12(x)=0仅能分开1和2类，不能分开1和3类。要分开M类模式，共需M(M-1)/2个判别函数。不确

30、定区域：若所有dij(x)，找不到，dij(x)>0的情况。多类情况3这是没有不确定区域的i/j两分法。假若多类情况2中的dij可分解成：dij(x) = di(x) - dj(x) = (wi wj)Tx，则dij(x)>0相当于di(x)>dj(x)，这时不存在不确定区域。此时，对M类情况应有M个判别函数：即di(x)>dj(x)，i, j = 1,2,M，则，也可写成，若di(x)=maxdk(x), k=1,2,M，则。该分类的特点是把M类情况分成M-1个两类问题。小结：线性可分：模式分类若可用任一个线性函数来划分，则这些模式就称为线性可分的，否则就是非线性可分

31、的。一旦线性函数的系数wk被确定，这些函数就可用作模式分类的基础。多类情况1和多类情况2的比较对于M类模式的分类，多类情况1需要M个判别函数，而多类情况2需要M*(M-1)/2个判别函数，当M较大时，后者需要更多的判别式（这是多类情况2的一个缺点）。采用多类情况1时，每一个判别函数都要把一种类别的模式与其余M-1种类别的模式分开，而不是将一种类别的模式仅于另一种类别的模式分开。由于一种模式的分布要比M-1种模式的分布更为聚集，因此多类情况2对模式是线性可分的可能性比多类情况1更大一些（这是多类情况2的一个优点）。作业（1）在一个10类的模式识别问题中，有3类单独满足多类情况1，其余的类别满足多

32、类情况2。问该模式识别问题所需判别函数的最少数目是多少？作业（2）一个三类问题，其判别函数如下：d1(x)=-x1, d2(x)=x1+x2-1, d3(x)=x1-x2-11.设这些函数是在多类情况1条件下确定的，绘出其判别界面和每一个模式类别的区域。2.设为多类情况2，并使：d12(x)= d1(x), d13(x)= d2(x), d23(x)= d3(x)。绘出其判别界面和多类情况2的区域。3.设d1(x), d2(x)和d3(x)是在多类情况3的条件下确定的，绘出其判别界面和每类的区域。3.2 广义线性判别函数出发点线性判别函数简单，容易实现；非线性判别函数复杂，不容易实现；若能将非

33、线性判别函数转换为线性判别函数，则有利于模式分类的实现。基本思想设有一个训练用的模式集x，在模式空间x中线性不可分，但在模式空间x*中线性可分，其中x*的各个分量是x的单值实函数，x*的维数k高于x的维数n，即若取x* = (f1(x), f2(x), ., fk(x), k>n,则分类界面在x*中是线性的，在x中是非线性的，此时只要将模式x进行非线性变换，使之变换后得到维数更高的模式x*，就可以用线性判别函数来进行分类。描述 一个非线性判别函数可如下表示：其中fi(x), i = 1,2,k是模式x的单值实函数。若定义成广义形式：x* = (f1(x), f2(x), , fk(x),

34、 1)T此时有：d(x*) = wTx*，其中w = (w1, w2, , wk, wk+1)T,该式表明，非线性判别函数已被变换成广义线性，因此只讨论线性判别函数不会失去一般性意义。广义线性判别函数的意义线性的判别函数取fi(x)为一次函数，例如xi，则变换后的模式x*=x，x*的维数k为x的维数n，此时广义线性化后的判别式仍为：d(x) = wTx + wn+1,fi(x)选用二次多项式函数1.x是二维的情况，即x =(x1 x2) T。若原判别函数为：,要线性化为d(x*) = wTx*，须定义：,此时，只要把模式空间x*中的分量定义成x的单值实函数，x*即变成线性可分。此时x*的维数（

35、这里为6）大于x的维数（这里为2）。2.x是n维的情况，此时原判别函数设为：,式中各项的组成应包含x的各个分量的二次项、一次项和常数项，其中平方项n个，二次项n(n-1)/2个，一次项n个，常数项一个，其总项数为：n + n(n-1)/2 + n + 1 = (n+1)(n+2)/2 > n显然，对于d(x*) = wTx*，x*的维数大于x的维数，w分量的数目也与x*的维数相应。x*的各分量的一般化形式为：说明:d(x)的项数随r和n的增加会迅速增大，即使原来模式x的维数不高，若采用次数r较高的多项式来变换，也会使变换后的模式x*的维数很高，给分类带来很大困难。实际情况可只取r=2，或

36、只选多项式的一部分，例如r=2时只取二次项，略去一次项，以减少x*的维数。作业两类模式，每类包括5个3维不同的模式，且良好分布。如果它们是线性可分的，问权向量至少需要几个系数分量？假如要建立二次的多项式判别函数，又至少需要几个系数分量？（设模式的良好分布不因模式变化而改变。）3.3 分段线性判别函数出发点:线性判别函数在进行分类决策时是最简单有效的，但在实际应用中，常常会出现不能用线性判别函数直接进行分类的情况。采用广义线性判别函数的概念，可以通过增加维数来得到线性判别，但维数的大量增加会使在低维空间里在解析和计算上行得通的方法在高维空间遇到困难，增加计算的复杂性。引入分段线性判别函数的判别过

37、程，它比一般的线性判别函数的错误率小，但又比非线性判别函数简单。分段线性判别函数的设计:采用最小距离分类的方法设1和2为两个模式类1和2的聚类中心，定义决策规则：这时的决策面是两类期望连线的垂直平分面，这样的分类器称为最小距离分类器。3.4 模式空间和权空间分类描述: 设有判别函数：d(x)=wTx，其中x=(x1 x2xn 1)T，w=(w1 w2wn wn+1)T, ,判别界面为：wTx=0 ,对两类问题，1类有模式x1 x2，2类有模式x3 x4 ，则应满足如下条件：若将属于2类的模式都乘以(-1)，则上式可写成：因此，若权向量能满足上述四个条件，则wTx=0为所给模式集的判别界面。模式

38、空间:对一个线性方程w1x1+w2x2+w3x3=0，它在三维空间(x1 x2 x3)中是一个平面方程式，w=(w1 w2 w3)T是方程的系数。把w向量作为该平面的法线向量，则该线性方程决定的平面通过原点且与w垂直。若x是二维的增广向量，此时x3=1，则在非增广的模式空间中即为x1, x2 二维坐标，判别函数是下列联立方程的解 w1x1+w2x2+w3=0,x3=1即为这两个平面相交的直线AB,此时，w =(w1 w2)T为非增广的权向量，它与直线AB垂直；AB将平面分为正、负两侧，w离开直线的一侧为正， w射向直线的一侧为负。增广向量决定的平面;非增广向量决定的直线权空间若将方程x1w1+

39、x2w2+w3=0绘在权向量w=(w1 w2 w3)T的三维空间中，则x=(x1 x2 1)T为方程的系数。若以x向量作为法线向量，则该线性方程所决定的平面为通过原点且与法线向量垂直的平面，它同样将权空间划分为正、负两边。在系数x不变的条件下，若w值落在法线向量离开平面的一边，则wTx>0，若w值落在法线向量射向平面的一边，则wTx <0。权空间中判别界面的平面示意图3.5 Fisher线性判别出发点:应用统计方法解决模式识别问题时，一再碰到的问题之一就是维数问题。在低维空间里解析上或计算上行得通的方法，在高维空间里往往行不通。因此，降低维数有时就会成为处理实际问题的关键。问题描述

40、:考虑把d维空间的样本投影到一条直线上,形成一维空间，即把维数压缩到一维。然而，即使样本在d维空间里形成若干紧凑的互相分得开的集群，当把它们投影到一条直线上时，也可能会是几类样本混在一起而变得无法识别。但是，在一般情况下，总可以找到某个方向，使在这个方向的直线上，样本的投影能分得开。问题：如何根据实际情况找到一条最好的、最易于分类的投影线，这就是Fisher判别方法所要解决的基本问题。从d维空间到一维空间的一般数学变换方法:假设有一集合包含N个d维样本x1, x2, , xN，其中N1个属于1类的样本记为子集1， N2个属于2类的样本记为子集2 。若对xn的分量做线性组合可得标量：yn = w

41、Txn, n=1,2,N,这样便得到N个一维样本yn组成的集合，并可分为两个子集1和2 。实际上，w的值是无关紧要的，它仅是yn乘上一个比例因子，重要的是选择w的方向。w的方向不同，将使样本投影后的可分离程度不同，从而直接影响的分类效果。因此，上述寻找最佳投影方向的问题，在数学上就是寻找最好的变换向量w*的问题。Fisher准则函数的定义Fisher准则函数定义为：其中，是两类均值之差，是样本类离散度。显然，应该使JF(w)的分子尽可能大而分母尽可能小，即应寻找使JF(w)尽可能大的w作为投影方向。但上式中并不显含w，因此须设法将JF(w)变成w的显函数。由各类样本的均值可推出：，这样，Fis

42、her准则函数JF(w)的分子可写成：现在再来考察JF(w)的分母与w的关系：因此，将上述各式代入JF(w)，可得：其中Sb为样本类间离散度矩阵，Sw为总样本类离散度矩阵。几个必要的基本参量:1在d维X空间:1)各类样本的均值向量mi:2)样本类离散度矩阵Si和总样本类离散度矩阵Sw其中Sw是对称半正定矩阵，而且当N>d时通常是非奇异的。3)样本类间离散度矩阵Sb Sb是对称半正定矩阵。1.在一维Y空间:1)各类样本的均值2)样本类离散度和总样本类离散度最佳变换向量w*的求取为求使取极大值时的w*，可以采用Lagrange乘数法求解。令分母等于非零常数，即：,定义Lagrange函数为：

43、其中为Lagrange乘子。将上式对w求偏导数，可得：,令偏导数为零，有；即其中w*就是JF(w)的极值解。因为Sw非奇异，将上式两边左乘，可得：上式为求一般矩阵的特征值问题。利用的定义，将上式左边的写成：其中为一标量，所以总是在向量的方向上。因此w*可写成：从而可得：由于我们的目的是寻找最佳的投影方向，w*的比例因子对此并无影响，因此可忽略比例因子R/,有：基于最佳变换向量w*的投影w*是使Fisher准则函数JF(w)取极大值时的解，也就是d维X空间到一维Y空间的最佳投影方向。有了w*，就可以把d维样本x投影到一维，这实际上是多维空间到一维空间的一种映射，这个一维空间的方向w*相对于Fis

44、her准则函数JF(w)是最好的。利用Fisher准则，就可以将d维分类问题转化为一维分类问题，然后，只要确定一个阈值T，将投影点yn与T相比较，即可进行分类判别。我们希望投影后，在一维Y空间中各类样本尽可能分得开些，即希望两类均值之差越大越好，同时希望各类样本部尽量密集，希望类离散度越小越好。Lagrange乘数法（详见相关数学文献）Lagrange乘数法是一种在等式约束条件下的优化算法，其基本思想是将等式约束条件下的最优化问题转化为无约束条件下的最优化问题。问题：设目标函数为y=f(x)，x=(x1, x2, , xn)求其在m(m<n)个约束条件gk(x)=0，k=1,2,m下的极

45、值。描述：引进函数,其中k，k=1,2,m为待定常数。将L当作n+m个变量x1, x2, , xn和1, 2, , m的无约束的函数，对这些变量求一阶偏导数可得稳定点所要满足的方程：3.6 感知器算法出发点：一旦判别函数的形式确定下来，不管它是线性的还是非线性的，剩下的问题就是如何确定它的系数。在模式识别中，系数确定的一个主要方法就是通过对已知样本的训练和学习来得到。感知器算法就是通过训练样本模式的迭代和学习，产生线性（或广义线性）可分的模式判别函数。基本思想采用感知器算法(Perception Approach)能通过对训练模式样本集的“学习”得到判别函数的系数。说明：这里采用的算法不需要对

46、各类别中模式的统计性质做任何假设，因此称为确定性的方法。背景“感知器”一词出自于20世纪50年代中期到60年代中期人们对一种分类学习机模型的称呼，它是属于有关动物和机器学习的仿生学领域中的问题。当时的一些研究者认为感知器是一种学习机的强有力模型，后来发现估计过高了，但发展感知器的一些相关概念仍然沿用下来。感知器的训练算法已知两个训练模式集分别属于1类和2类，权向量的初始值为w(1)，可任意取值。若，若，则在用全部训练模式集进行迭代训练时，第k次的训练步骤为：若且，则分类器对第k个模式xk做了错误分类，此时应校正权向量，使得w(k+1) = w(k) + Cxk，其中C为一个校正增量。若且，同样

47、分类器分类错误，则权向量应校正如下：w(k+1) = w(k) - Cxk ，若以上情况不符合，则表明该模式样本在第k次中分类正确，因此权向量不变，即：w(k+1) = w(k) ，若对的模式样本乘以(-1)，则有：时，w(k+1) = w(k) + Cxk ，此时，感知器算法可统一写成：感知器算法的收敛性只要模式类别是线性可分的，就可以在有限的迭代步数里求出权向量。（证明作为练习）作业及编程用感知器算法求下列模式分类的解向量w:1: (0 0 0)T, (1 0 0)T, (1 0 1)T, (1 1 0)T，2: (0 0 1)T, (0 1 1)T, (0 1 0)T, (1 1 1)T

48、，编写求解上述问题的感知器算法程序。3.7 采用感知器算法的多类模式的分类采用3.1的多类情况3，将感知器算法推广到多类模式。感知器算法判别函数的推导多类情况3：对M类模式存在M个判别函数di,l i = 1,2,M，若，则。设有M种模式类别1，2，M，若在训练过程的第k次迭代时，一个属于i类的模式样本x送入分类器，则应先计算出M个判别函数：，若的条件成立，则权向量不变，即若其中第l个权向量使得，则相应的权向量应做调整，即其中C是一个正常数。权向量的初始值wi(1)，i = 1,2,M可视情况任意选择。讨论：这里的分类算法都是通过模式样本来确定判别函数的系数，但一个分类器的判断性能最终要受并未

49、用于训练的那些未知样本来检验。要使一个分类器设计完善，必须采用有代表性的训练数据，它能够合理反映模式数据的整体。要获得一个判别性能好的线性分类器，究竟需要多少训练样本？直观上是越多越好，但实际上能收集到的样本数目会受到客观条件的限制；过多的训练样本在训练阶段会使计算机需要较长的运算时间；一般来说，合适的样本数目可如下估计：若k是模式的维数，令C=2(k+1)，则通常选用的训练样本数目约为C的1020倍。感知器算法实质上是一种赏罚过程对正确分类的模式则“赏”，实际上是“不罚”，即权向量不变。对错误分类的模式则“罚”，使w(k)加上一个正比于xk的分量。当用全部模式样本训练过一轮以后，只要有一个模

50、式是判别错误的，则需要进行下一轮迭代，即用全部模式样本再训练一次。如此不断反复直到全部模式样本进行训练都能得到正确的分类结果为止。作业用多类感知器算法求下列模式的判别函数：1: (-1 -1)T，2: (0 0)T，3: (1 1)T3.8 可训练的确定性分类器的迭代算法3.8.1 梯度法定义：梯度是一个向量，它的最重要性质就是指出了函数f在其自变量y增加时最大增长率的方向。负梯度指出f的最陡下降方向，利用这个性质，可以设计一个迭代方案来寻找函数的最小值。设函数f(y)是向量y = (y1, y2, , yn)T的函数，则f(y)的梯度定义为：从w(k)导出w(k+1)的一般关系式C是一个正的

51、比例因子（步长）采用梯度法求解的基本思想对感知器算法式中的w(k)、xk随迭代次数k而变，是变量。定义一个对错误分类敏感的准则函数J(w, x)。先任选一个初始权向量w(1)，计算准则函数J的梯度，然后从w(1)出发，在最陡方向（梯度方向）上移动某一距离得到下一个权向量w(2) 。讨论：若正确地选择了准则函数J(w,x)，则当权向量w是一个解时，J达到极小值（J的梯度为零）。由于权向量是按J的梯度值减小，因此这种方法称为梯度法（最速下降法）。为了使权向量能较快地收敛于一个使函数J极小的解，C值的选择是很重要的。若C值太小，则收敛太慢；若C值太大，则搜索可能过头，引起发散。3.8.2 固定增量的

52、逐次调整算法过程说明：设已由前一步迭代得到w(k)的值。读入模式样本xk，判别wT(k)xk是否大于0。在示意图中，xk界定的判别界面为wT(k)xk=0。当w(k)在判别界面的负区域时， wT(k)xk<0。校正： w(k+1)= w(k)+ xk ，这里取C=1。校正后， w(k+1)向量比w(k)向量更接近于模式xk所决定的正区域。讨论：若模式是线性可分的，选择合适的准则函数J(w,x)，算法就能给出解。若模式不是线性可分的，算法的结果就会来回摆动，得不到收敛。作业采用梯度法和准则函数 式中实数b>0，试导出两类模式的分类算法。3.8.3 最小平方误差(LMSE)算法出发点：

53、感知器算法只是当被分模式可用一个特定的判别界面分开时才收敛，在不可分情况下，只要计算程序不终止，它就始终不收敛。即使在模式可分的情况下，也很难事先算出达到收敛时所需要的迭代次数。这样，在模式分类过程中，有时候会出现一次又一次迭代却不见收敛的情况，白白浪费时间。为此需要知道：发生迟迟不见收敛的情况时，到底是由于收敛速度过慢造成的呢，还是由于所给的训练样本集不是线性可分造成的呢？最小平方误差(LMSE)算法，除了对可分模式是收敛的以外，对于类别不可分的情况也能指出来。分类器的不等式方程求两类问题的解相当于求一组线性不等式的解，因此，若给出分别属于1和2的两个模式样本的训练样本集，即可求出其权向量w

54、的解，其性质应满足：，将属于2的模式乘以(-1)，可得对于全部模式都有的条件。设两类模式的训练样本总数为N，写成增广形式，则有不等式组：Xw > 0式中： w = (w1, w2, , wn, wn+1)T其中，0是零向量，是第i个n维模式样本的增广向量，即，它包括分属于1和2中全部供训练用的样本，但属于2类的模式应乘以(-1)，所以，X是一个N*(n+1)阶的矩阵。Ho-Kashyap(H-K)算法lH-K算法是求解Xw=b，式中b=( b1, b2, , bn)T，b的所有分量都是正值。这里要同时计算w和b，我们已知X不是N*N的方阵，通常是行多于列的N*(n+1)阶的长方阵，属于超

55、定方程，因此一般情况下，Xw=b没有唯一确定解，但可求其线性最小二乘解。设Xw=b的线性最小二乘解为w*，即使|Xw*-b|=极小。采用梯度法，定义准则函数：。当Xw=b的条件满足时，J达到最小值。由于上式中包括的项为两个数量方差的和，且我们将使其最小化，因此也称之为最小均方误差算法。使函数J同时对变量w和b求最小。对于w的梯度为：。使，得XT(Xw-b)=0，从而XTXw=XTb。因为XTX为(n+1)*(n+1)阶方阵，因此可求得解：w = (XTX)-1XTb = X#b。这里X#= (XTX)-1XT称为X的伪逆，X是N*(n+1)阶的长方阵。由上式可知，只要求出b即可求得w。利用梯度

56、法可求得b的迭代公式为：根据上述约束条件，在每次迭代中，b(k)的全部分量只能是正值。由J的准则函数式，J也是正值，因此，当取校正增量C为正值时，为保证每次迭代中的b(k)都是正值，应使为非正值。在此条件下，准则函数J的微分为：该式满足以下条件：若Xw(k) b(k) > 0，则若Xw(k) b(k) < 0，则由b的迭代式和微分，有：b(k+1) = b(k) + b(k)b(k) = CXw(k) b(k) + | Xw(k) b(k)|将此式代入w=X#b，有：w(k+1) = X#b(k+1) = X#b(k) +b(k) = w(k) + X#b(k)为简化起见，令e(k) = Xw(k) b(k)，可得H-K算法的迭代式。设初值为b(1)，其每一分量均为正值，则：w(1) = X#b(1)。e(k) = Xw(k) b(k)。w(k+1) = w(k) + X#CXw(k) b(k) + |Xw(k) b(k)|= w(k) + CX#e(k) + |e(k)|。由于X#e(k) = X#Xw(k) b(k) = (XTX)-1XTXw(k) b(k)= w(k) X#b(k) = 0。因此w(k+1) = w(k) + CX#|e(k)|。b(k+1) = b(k) + CX