模式识别第2-3章-聚类分析.doc

.
第二章 聚类分析
2.1 聚类分析的相关概念
定义 对一批没有标出类别的模式样本集，按照样本之间的相似程度分类，相似的归为一类，不相似的归为另一类，这种分类称为聚类分析，也称为无监督分类。
模式相似/分类的依据
把整个模式样本集的特征向量看成是分布在特征空间中的一些点，点与点之间的距离即可作为模式相似性的测量依据。聚类分析是按不同对象之间的差异，根据距离函数的规律（大小）进行模式分类的。
聚类分析的有效性
聚类分析方法是否有效，与模式特征向量的分布形式有很大关系。若向量点的分布是一群一群的，同一群样本密集（距离很近），不同群样本距离很远，则很容易聚类；若样本集的向量分布聚成一团，不同群的样本混在一起，则很难分类；对具体对象做聚类分析的关键是选取合适的特征。特征选取得好，向量分布容易区分，选取得不好，向量分布很难分开。
两类模式分类的实例：
一摊黑白围棋子 选颜色作为特征进行分类，用“1”代表白，“0”代表黑，则很容易分类；选大小作为特征进行分类，则白子和黑子的特征相同，不能分类（把白子和黑子分开）。
特征选择的维数
在特征选择中往往会选择一些多余的特征，它增加了维数，从而增加了聚类分析的复杂度，但对模式分类却没有提供多少有用的信息。在这种情况下，需要去掉相关程度过高的特征（进行降维处理）。
降维方法
设有N个样本，它们的特征维数是n，则有n*n维的相关矩阵R = [ rij ]nxn 其中，rij是第i维与第j维特征之间的相关系数： 这里：σii和σjj分别是第i个和第j个分量的标准差，λij是第i个和第j个分量的协方差。
分析：（1）根据相关系数的性质：（利用柯西不等式证明）（2）rij=0：表示两个分量完全不相关（3）rij=1：表示两个分量完全相关
结论：若rij->1，则表明第i维特征与第j维特征所反映的特征规律接近，因此可以略去其中的一个特征，或将它们合并为一个特征，从而使维数降低一维。
模式对象特征测量的数字化
计算机只能处理离散的数值，因此根据识别对象的不同，要进行不同的数据化处理。连续量的量化：用连续量来度量的特性，如长度、重量、面积等等，仅需取其量化值；量级的数量化：度量时不需要详尽的数值，而是相应地划分成一些有次序的量化等级的值。
l 病人的病程 0 ~ 代表病程 <= 1个月 1 ~ 代表1个月< 病程 <= 6个月
2 ~ 代表6个月< 病程 <= 12个月 3 ~ 代表病程 > 12个月
名义尺度：指定性的指标，即特征度量时没有数量关系，也没有明显的次序关系，如黑色和白色的关系，男性和女性的关系等，都可将它们分别用“0”和“1”来表示。超过2个状态时，可用多个数值表示。

2.2 模式相似性的测度和聚类准则
2.2.1 相似性测度
目的：为了能将模式集划分成不同的类别，必须定义一种相似性的测度，来度量同一类样本间的类似性和不属于同一类样本间的差异性。
欧氏距离
设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之间夹角的余弦，也称为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 聚类准则
有了模式的相似性测度，还需要一种基于数值的聚类准则，能将相似的模式样本分在同一类，相异的模式样本分在不同的类。
试探方法
凭直观感觉或经验，针对实际问题定义一种相似性测度的阈值，然后按最近邻规则指定某些模式样本属于某一个聚类类别。例如对欧氏距离，它反映了样本间的近邻性，但将一个样本分到不同类别中的哪一个时，还必须规定一个距离测度的阈值作为聚类的判别准则。
聚类准则函数法
依据：由于聚类是将样本进行分类以使类别间可分离性为最大，因此聚类准则应是反映类别间相似性或分离性的函数；由于类别是由一个个样本组成的，因此一般来说类别的可分离性和样本的可分离性是直接相关的；可以定义聚类准则函数为模式样本集{x}和模式类别{Sj, j=1,2,…,c}的函数，从而使聚类分析转化为寻找准则函数极值的最优化问题。
一种聚类准则函数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作为一个聚类中心的初始值，例如令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个模式样本分类完毕。
讨论 这种方法的优点：计算简单，若模式样本的集合分布的先验知识已知，则可通过选取正确的阈值和起始点，以及确定样本的选取次序等获得较好的聚类结果。在实际中，对于高维模式样本很难获得准确的先验知识，因此只能选用不同的阈值和起始点来试探，所以这种方法在很大程度上依赖于以下因素：第一个聚类中心的位置；待分类模式样本的排列次序
；距离阈值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 = 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，即若max{min(Di1, Di2), i = 1,2,…,N} >θ||z1 - z2 ||，则z3 = xi
否则，若找不到适合要求的样本作为新的聚类中心，则找聚类中心的过程结束。这里，θ可用试探法取一固定分数，如1/2。在此例中，当i=7时，符合上述条件，故z3 = x7
第五步： 若有z3存在，则计算max{min(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}为第三类，最后，还可在每一类中计算个样本的均值，得到更具代表性的聚类中心。
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)。计算与其它没有发生合并的之间的距离，可采用多种不同的距离计算准则进行计算。
第四步：返回第二步，重复计算及合并，直到得到满意的分类结果。（如：达到所需的聚类数目，或D(n)中的最小分量超过给定阈值D等。）
距离准则函数
进行聚类合并的一个关键就是每次迭代中形成的聚类之间以及它们和样本之间距离的计算，采用不同的距离函数会得到不同的计算结果。主要的距离计算准则：
聚类准则函数
1.最短距离法：设H和K是两个聚类，则两类间的最短距离定义为：其中，du,v表示H类中的样本xu和K类中的样本xv之间的距离，DH,K表示H类中的所有样本和K类中的所有样本之间的最小距离。递推运算：假若K类是由I和J两类合并而成，则

2.最长距离法：设H和K是两个聚类，则两类间的最长距离定义为：其中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 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, 0
2.5 动态聚类法
基本思想：首先选择若干个样本点作为聚类中心，再按某种聚类准则（通常采用最小距离准则）使样本点向各中心聚集，从而得到初始聚类；然后判断初始分类是否合理，若不合理，则修改分类；如此反复进行修改聚类的迭代算法，直至合理为止。
K-均值算法
思想：基于使聚类性能指标最小化，所用的聚类准则函数是聚类集中每一个样本点到该类中心的距离平方之和，并使其最小化。
第一步：选K个初始聚类中心，z1(1)，z2(1)，…，zK(1)，其中括号内的序号为寻找聚类中心的迭代运算的次序号。聚类中心的向量值可任意设定，例如可选开始的K个模式样本的向量值作为初始聚类中心。
第二步：逐个将需分类的模式样本{x}按最小距离准则分配给K个聚类中心中的某一个zj(1)。假设i=j时，，则，其中k为迭代运算的次序号，第一次迭代k=1，Sj表示第j个聚类，其聚类中心为zj。
第三步：计算各个聚类中心的新的向量值，zj(k+1)，j=1,2,…,K。求各聚类域中所包含样本的均值向量：其中Nj为第j个聚类域Sj中所包含的样本个数。以均值向量作为新的聚类中心，可使如下聚类准则函数最小：
，在这一步中要分别计算K个聚类中的样本均值向量，所以称之为K-均值算法。
第四步：若，j=1,2,…,K，则返回第二步，将模式样本逐个重新分类，重复迭代运算；若，j=1,2,…,K，则算法收敛，计算结束。
讨论 K-均值算法的结果受如下选择的影响：所选聚类的数目；聚类中心的初始分布；模式样本的几何性质；读入次序；在实际应用中需要试探不同的K值和选择不同的聚类中心的起始值。如果模式样本可以形成若干个相距较远的孤立的区域分布，一般都能得到较好的收敛效果。K-均值算法比较适合于分类数目已知的情况。
作业/练习
（选k=2,z1(1)=x1,z2(1)=x10,用K-均值算法进行聚类分析）
ISODATA算法（迭代自组织数据分析算法）
与K-均值算法的比较：K-均值算法通常适合于分类数目已知的聚类，而ISODATA算法则更加灵活；从算法角度看， ISODATA算法与K-均值算法相似，聚类中心都是通过样本均值的迭代运算来决定的；ISODATA算法加入了一些试探步骤，并且可以结合成人机交互的结构，使其能利用中间结果所取得的经验更好地进行分类。
基本步骤和思路
（1）选择某些初始值。可选不同的参数指标，也可在迭代过程中人为修改，以将N个模式样本按指标分配到各个聚类中心中去。（2）计算各类中诸样本的距离指标函数。（3）~（5）按给定的要求，将前一次获得的聚类集进行分裂和合并处理（（4）为分裂处理，（5）为合并处理），从而获得新的聚类中心。（6）重新进行迭代运算，计算各项指标，判断聚类结果是否符合要求。经过多次迭代后，若结果收敛，则运算结束。
算法：
第一步：输入N个模式样本{xi, i = 1, 2, …, N}预选Nc个初始聚类中心，它可以不等于所要求的聚类中心的数目，其初始位置可以从样本中任意选取。预选：K = 预期的聚类中心数目；θN = 每一聚类域中最少的样本数目，若少于此数即不作为一个独立的聚类；θS = 一个聚类域中样本距离分布的标准差；θc = 两个聚类中心间的最小距离，若小于此数，两个聚类需进行合并；L = 在一次迭代运算中可以合并的聚类中心的最多对数；I = 迭代运算的次数。
第二步：将N个模式样本分给最近的聚类Sj，假若，即||x-zj||的距离最小，则。
第三步：如果Sj中的样本数目Sj<θN，则取消该样本子集，此时Nc减去1。（以上各步对应基本步骤（1））
第四步：修正各聚类中心
第五步：计算各聚类域Sj中模式样本与各聚类中心间的平均距离

第六步：计算全部模式样本和其对应聚类中心的总平均距离
（以上各步对应基本步骤（2））
第七步：判别分裂、合并及迭代运算1.若迭代运算次数已达到I次，即最后一次迭代，则置θc =0，转至第十一步。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, 2, …, Nc}中，若有σjmax>θS ，同时又满足如下两个条件之一：1.和Nj > 2(θN + 1)，即Sj中样本总数超过规定值一倍以上，2.，则将zj 分裂为两个新的聚类中心和，且Nc加1。 中对应于σjmax的分量加上kσjmax，其中；中对应于σjmax的分量减去kσjmax。如果本步骤完成了分裂运算，则转至第二步，否则继续。（以上对应基本步骤（4）进行分裂处理）
第十一步：计算全部聚类中心的距离Dij = || zi - zj ||，i = 1, 2, …, Nc-1 ，j =i+1, …, Nc。
第十二步：比较Dij 与θc 的值，将Dij <θc 的值按最小距离次序递增排列，即
式中，。
第十三步：将距离为的两个聚类中心和合并，得新的中心为：
，k = 1, 2, …, L式中，被合并的两个聚类中心向量分别以其聚类域内的样本数加权，使为真正的平均向量。（以上对应基本步骤（5）进行合并处理）
第十四步：如果是最后一次迭代运算（即第I次），则算法结束；否则，若需要操作者改变输入参数，转至第一步；若输入参数不变，转至第二步。在本步运算中，迭代运算的次数每次应加1。[算法结束]
2.6 聚类结果的评价
迅速评价聚类结果，在上述迭代运算中是很重要的，特别是具有高维特征向量的模式，不能直接看清聚类效果，因此，可考虑用以下几个指标来评价聚类效果：聚类中心之间的距离；距离值大，通常可考虑分为不同类；聚类域中的样本数目；样本数目少且聚类中心距离远，可考虑是否为噪声；聚类域内样本的距离方差；方差过大的样本可考虑是否属于这一类
讨论：模式聚类目前还没有一种通用的放之四海而皆准的准则，往往需要根据实际应用来选择合适的方法。
作业
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), x4(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为参数方程，则将一
个不知类别的模式代入d(x)，有 若d(x) > 0，
则若d(x) < 0，则此时，
d(x)=0称为判别函数。
用判别函数进行模式分类依赖的两个因素
（1）判别函数的几何性质：线性的和非线性的函数。线性的是一条直线；非线性的可以是曲线、折线等；线性判别函数建立起来比较简单（实际应用较多）；非线性判别函数建立起来比较复杂。
（2）判别函数的系数：判别函数的形式确定后，主要就是确定判别函数的系数问题。只要被研究的模式是可分的，就能用给定的模式样本集来确定判别函数的系数。
3.1.2 线性判别函数
n维线性判别函数的一般形式：
，其中w0 = (w1, w2, …, wn)T称为权向量（或参数向量）, 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。图例：对一个三类情况，每一类模式可用一个简单的直线判别界面将它与其它类模式分开。例如对的模式，
应同时满足：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
个判别函数。不确定区域：若所有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)=max{dk(x), k=1,2,…,M}，则
。该分类的特点是把M类情况分成M-1
个两类问题。
小结：线性可分：模式分类若可用任一个线性函数来划分，则这些模式就称为线性可分的，否则就是非线性可分的。一旦线性函数的系数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，其余的类别满足多类情况2。问该模式识
别问题所需判别函数的最少数目是多少？
作业（2）
一个三类问题，其判别函数如下：d1(x)=-x1,
d2(x)=x1+x2-1, d3(x)=x1-x2-1
1.设这些函数是在多类情况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 广义线性判别函数
出发点
线性判别函数简单，容易实现；非线性判别函数复杂，不容易实现；若能将非线性判别函数转换为线性判别函数，则有利于模式分类的实现。
基本思想
设有一个训练用的模式集{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), 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*的维数（这里为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，或只选多项式的一部分，例如r=2时只取二次项，略去一次项，以减少x*的维数。
作业
两类模式，每类包括5个3维不同的模式，且良好分布。如果它们是线性可分的，问权向量至少需要几个系数分量？假如要建立二次的多项式判别函数，又至少需要几个系数分量？（设模式的良好分布不因模式变化而改变。）
3.3 分段线性判别函数
出发点:线性判别函数在进行分类决策时是最简单有效的，但在实际应用中，常常会出现不能用线性判别函数直接进行分类的情况。采用广义线性判别函数的概念，可以通过增加维数来得到线性判别，但维数的大量增加会使在低维空间里在解析和计算上行得通的方法在高维空间遇到困难，增加计算的复杂性。引入分段线性判别函数的判别过程，它比一般的线性判别函数的错误率小，但又比非线性判别函数简单。
分段线性判别函数的设计:采用最小距离分类的方法
设μ1和μ2为两个模式类ω1和ω2的聚类中心，定义决策规
则：这时的决策面是两类期
望连线的垂直平分面，这样的分类器称为最小距离分类器。
3.4 模式空间和权空间
分类描述: 设有判别函数：d(x)=wTx，其中x=(x1 x2…xn 1)T，w=(w1 w2…wn wn+1)T, ,判别界面为：wTx=0 ,对两类问题，ω1类有模式{x1 x2}，ω2类有模式{x3 x4} ，则应满足如下条件：
若将属于ω2类的模式都乘以(-1)，则上式可写成：
因此，若权向量能满足上述四个条件，则wTx=0为所给模式集的判别界面。
模式空间:对一个线性方程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+x2w2+w3=0绘在权向量w=(w1 w2 w3)T的三维空间中，则x=(x1 x2 1)T为方程的系数。若以x向量作为法线向量，则该线性方程所决定的平面为通过原点且与法线向量垂直的平面，它同样将权空间划分为正、负两边。在系数x不变的条件下，若w值落在法线向量离开平面的一边，则wTx>0，若w值落在法线向量射向平面的一边，则wTx <0。
权空间中判别界面的平面示意图
3.5 Fisher线性判别
出发点:应用统计方法解决模式识别问题时，一再碰到的问题之一就是维数问题。在低维空间里解析上或计算上行得通的方法，在高维空间里往往行不通。因此，降低维数有时就会成为处理实际问题的关键。
问题描述:考虑把d维空间的样本投影到一条直线上,形成一维空间，即把维数压缩到一维。然而，即使样本在d维空间里形成若干紧凑的互相分得开的集群，
当把它们投影到一条直线上时，也可能会是几类样本混在一起而变得无法识别。但是，在一般情况下，总可以找到某个方向，使在这个方向的直线上，样本的投影能分得开。
问题：如何根据实际情况找到一条最好的、最易于分类的投影线，这就是Fisher判别方法所要解决的基本问题。
从d维空间到一维空间的一般数学变
换方法:假设有一集合Г包含N个d
维样本x1, x2, …, xN，其中N1个属
于ω1类的样本记为子集Г1， N2
个属于ω2类的样本记为子集Г2 。
若对xn的分量做线性组合可得标
量：yn = wTxn, n=1,2,…,N,这样便
得到N个一维样本yn组成的集合，并可分为两个子集Г1’和Г2’ 。实际上，w的值是无关紧要的，它仅是yn乘上一个比例因子，重要的是选择w的方向。w的方向不同，将使样本投影后的可分离程度不同，从而直接影响的分类效果。因此，上述寻找最佳投影方向的问题，在数学上就是寻找最好的变换向量w*的问题。
Fisher准则函数的定义
Fisher准则函数定义为： 其中，是两类均值之差，是样本类内离散度。显然，应该使JF(w)的分子尽可能大而分母尽可能小，即应寻找使JF(w)尽可能大的w作为投影方向。但上式中并不显含w，因此须设法将JF(w)变成w的显函数。由各类样本的均值可推出：
，这样，Fisher准则函数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函数为：其中λ为Lagrange乘子。将上式对w求偏导数，可得：,令偏导数为零，有；
即其中w*就是JF(w)的极值解。因为Sw非奇异，将上式两边左乘，可得：上式为求一般矩阵的特征值问题。利用的定义，将上式左边的写成：
其中为一标量，所以总是在向量的方向上。因此λw*可写成：
从而可得：

由于我们的目的是寻找最佳的投影方向，w*的比例因子对此并无影响，因此可忽略比例因子R/λ,有：
基于最佳变换向量w*的投影
w*是使Fisher准则函数JF(w)取极大值时的解，也就是d维X空间到一维Y空间的最佳投影方向。有了w*，就可以把d维样本x投影到一维，这实际上是多维空间到一维空间的一种映射，这个一维空间的方向w*相对于Fisher准则函数JF(w)是最好的。利用Fisher准则，就可以将d维分类问题转化为一维分类问题，然后，只要确定一个阈值T，将投影点yn与T相比较，即可进行分类判别。我们希望投影后，在一维Y空间中各类样本尽可能分得开些，即希望两类均值之差越大越好，同时希望各类样本内部尽量密集，希望类内离散度越小越好。
Lagrange乘数法（详见相关数学文献）
Lagrange乘数法是一种在等式约束条件下的优化算法，其基本思想是将等式约束条件下的最优化问题转化为无约束条件下的最优化问题。
问题：设目标函数为y=f(x)，x=(x1, x2, …, xn)求其在m(m旦判别函数的形式确定下来，不管它是线性的还是非线性的，剩下的问题就是如何确定它的系数。在模式识别中，系数确定的一个主要方法就是通过对已知样本的训练和学习来得到。感知器算法就是通过训练样本模式的迭代和学习，产生线性（或广义线性）可分的模式判别函数。
基本思想
采用感知器算法(Perception Approach)能通过对训练模式样本集的“学习”得到判别函数的系数。说明：这里采用的算法不需要对各类别中模式的统计性质做任何假设，因此称为确定性的方法。
背景
“感知器”一词出自于20世纪50年代中期到60年代中期人们对一种分类学习机模型的称呼，它是属于有关动物和机器学习的仿生学领域中的问题。
当时的一些研究者认为感知器是一种学习机的强有力模型，后来发现估计过高了，但发展感知器的一些相关概念仍然沿用下来。
感知器的训练算法
已知两个训练模式集分别属于ω1类和ω2类，权向量的初始值为w(1)，可任意取值。若，若，则在用全部训练模式集进行迭代训练时，第k次的训练步骤为：若且，则分类器对第k个模式xk做了错误分类，此时应校正权向量，使得w(k+1) = w(k) + Cxk，其中C为一个校正增量。
若且，同样分类器分类错误，则权向量应校正如下：w(k+1) = w(k) - Cxk ，若以上情况不符合，则表明该模式样本在第k次中分类正确，因此权向量不变，即：w(k+1) = wk) ，若对的模式样本乘以(-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}，编写求解上述问题的感知器算法程序。
3.7 采用感知器算法的多类模式的分类
采用3.1的多类情况3，将感知器算法推广到多类模式。
感知器