模式识别(5)

1, aiT y 0 zi ( x ) T 0, ai y 0
定义一个由样本x决策的m维向量：
z( x) [ z1 ( x), z2 ( x),, zm ( x)]
分段线性分类器的检验决策规则
因此处在同一区域的所有样本都有同样的向量值。 例如下图中，处在R1域中所有样本的m维向量(m＝2)为 z＝{1,1}；而在R2或中的样本具有z＝{0,1}；R3域中则 为z＝{0,0}。
g j ( x) max g i ( x),
i 1, 2 ,....., M
则x j
§5.2基于距离的分段线性判别函数
对未知模式x， 把x先代入每类的各子类的判别函数中； 找出一个最大的子类判别函数，M类有M 个最大子类判别函数；
在M个子类最大判别函数中，再找一个最
大的；
则x就属于最大的子类判别函数所属的那一类。
V2 v , v , v ，
2 2 3 2 1 v1 v1 2 2 2 v2 v1 3 v2 v12
3 v12 v2
§5.4用交遇区的样本设计线性分类器
寻找两类紧互对原型对集合的主要步骤：
1. 首先对这两类样本进行聚类分析，找出它们各自的一些相 对密集的子区域，即“原型区” 2. 在每个原型区中找到一个质心或距质心很近的样本作为各
局部练法
具体步骤：
步骤一： 产生初始决策面 首先由紧互对原型对集合中最近的一对， 产生一个初 始决策面的方程。例如可由这两个原型的垂直平分平面作 为初始分界面，表示成H1； 步骤二： 初始决策面最佳化 确定超平面H1能正确分类的所有紧互对原型对，并用 这些原型对代表的聚类中的所有样本组成局部训练样本集， 按所使用的准则设计出线性决策面H1*，该决策面对现有局 部样本集来说是最佳的。对该决策面H1*又可找出它能正确 分类的所有紧互对原型对。如果H1*与H1的分类效果相同， 则 H1*不需要再调整。否则由H1*作为初始决策面，重复上 述过程，直到两者完全相同为止。
这种方法要解决的几个问题是： (1)如何从样本集中找到“交遇区”；
(2)如何利用“交遇区”中的样本设计线 性分类器；
(3)如何进行分类决策。
紧互对原型与交遇区
本节主要提出寻找“交遇区”的一种方法。 首先在每类样本集内进行聚类，将每类样本分为若干聚类。 常用的方法是聚类分析方法。 每个聚类在特征空间中占据一定区域，称为“原型区”。 每个聚类的重心，或最靠近重心的一个样本，称为该聚类的 “原型”。 为了简便计算，每个聚类可用它的原型来表示，每一类则由 若干个原型来表示。通过计算每个原型与其它原型的欧氏距 离来计算近邻关系。
局部训练法
步骤三： 新决策面的产生与最佳化 在找到一个最佳的决策面段后，将相应的局部训练样 本从原紧互对原型对集合中拿走，然后在剩下的紧互对原 型对集合重复上述步骤，产生第二个超平面段。 步骤四： 分段线性分类器 重复上述步骤，直到所有紧互对原型对都被处理完毕，得 到一系列超平面，组成分段线性分类器。 在使用上述方法得到一组超平面作为分段线性分类器的分 界面后，仅对交遇区的样本集进行性能检测有时不能发现 存在的问题，需要使用全体样本对其进行性能检验，观察 其能否对全体样本作出合理的划分？
原型区的代表点，即“原型”。
3. 在两个类别的原型集合中，分别计算不同类原型对之间的 欧氏距离，并找出各原型在对方类型中相距最近的原型对。 4. 从这些最小距离原型关系中找到互为最小距离的原型对， 即为“紧互对原型对”。（用“紧互对原型对”表示交遇 区）
局部训练法
基本思想：边界是由若干个交遇区确定的，在每个 交遇区中只有两种不同类型的样本。将这些“交遇 区”中的两类样本作为新的样本集，由这些样本产 生一个合适的分界面，一般使用分段线性分界面。 具体做法往往是利用处于最紧贴边界的紧互对原型 对产生一初始分界面，然后利用交遇区进行调整， 这种调整属于局部性的调整。
§5.5 本章小结

非线性判别函数与分段线性判别函数 基于距离的分段线性判别函数 分段线性分类器的设计 用交遇区的样本设计分段线性分类器
分段线性分类器的检验决策规则
（1）将每类分为三个聚类 （2）找出紧互对原型对集合 （3）局部训练法得到超平面H1和H2---缺少超平面段？ （4）重复以上算法，得到H3 。。。。
分段线性分类器的检验决策规则
图中Z向量为(1，1，1)、(1，1，0)以及(0，1，0)的区域为 ω 2的决策域，而(0，1，1)(0，0，0)及(0，0，1)区域则为 ω 1的决策域。
模式识别
第五章非线性判别函数
§5.1 引言

线性判别函数：简单、实用，但样本集线性 不可分时错误率可能较大 问题线性不可分：


噪声影响 问题本身 采用非线性分类器 改变特征，使线性可分


新特征 非线性变换
§5.1 引言
由于样本在特征空间分布的 复杂性，许多情况下采用线 性判别函数不能取得满意的 分类效果。－非线性判别函 数 例如右图所示两类物体在二 维特征空间的分布，采用线 性判别函数就无法取得满意 的分类效果。在这种情况下， 可以采用分段线性判别或二 次函数判别等方法，效果就 会好得多。

gi ( x) min x m
l 1, 2,..., i l
l i
（在同类的子类中找最近的均值。） 判别规则：
g j ( x) min gi ( x),i 1,2,...,M
分段线性距离分类器
这是在M类中找最近均值。则把x归于ωj类完成分类。
§5.2基于距离的分段线性判别函数
例：未知x,如图： 先与ω1类各子类的均值比较，即 x m1l ，找一 2 个最近的 g1 ( x ) x m1 与ω2各子类均值比较取 3 最近的 g 2 ( x ) x m2 因g2(x)< g1(x) ，所以 1 m1 x∈ω2类 。 m1 2 1 1 2 1
L
N (z j ) N (z j ) N (z j )
1 2
1
分段线性分类器的检验决策规则
根据L值及N1(zj(x))和N2(zj(x))这三个数据，可对各个区域作相
应决定： 1、如果L>>1/2，则zj区域为ω1的决策域； 2、如果L<<1/2，则zj区域为ω2的决策域； 3、如果L≈1/2，且N1(zj(x))和N2(zj(x))都很小，则zj区域内样本 可作拒绝决策； 4、如果L≈1/2，且N1(zj(x))和N2(zj(x))都很大数量不可忽略， 则对此区域，说明还缺少超平面段，要用该子集的样本再次 进行局部训练法训练，以获得其进一步划分。 5、重复上述过程，直至对所有区域都能合理地确定为哪一类 的决策域，或拒识区域为止。
§5.3分段线性分类器的设计
§5.3分段线性分类器的设计
§5.3分段线性分类器的设计
§5.4用交遇区的样本设计线性分类器
出发点：与前述方法不同，其出发点是类间的分界面必 然处在两类样本的交界处，因此只需找出这些交界处的 样本，然后对这些邻近的不同类样本，按需要确定分界 面即可。 实际上决策面都处在不同类 别样本分布的交界处或邻接 处所在的区域内，譬如右图 中两类物体在特征空间分布 中有若干处很接近或甚至有 交迭。
§5.1 引言

一种特殊的非线性判别函数－分段线性判别函数

决策面由若干超平面段组成，计算比较简单 能逼近各种形状的超曲面，适应能力强
1
Ⅰ
Ⅲ
1
2
Ⅱ
Ⅰ:线性判别 Ⅱ：分段线性判别 Ⅲ：二次判别
§5.2基于距离的分段线性判别函数

出发点：如果两类样本可以划分为线性可分的 若干子类，则可以设计多个线性分类器，实现 分段线性分类器。
分段线性分类器的检验决策规则
例：图中所示样本利用局部训练法产生了H1与H2两个 超平面，将整个特征空间划分成R1、R2与R3三个决策 域。
在R1域中第二类样本占绝大多数， 因此R1可作为第二类样本ω2的决策 域，错误率不会很大。同样，在R3 域中ω1占大多数，R3可作为ω1的决 策域。 问题出在R2域。在R2域中ω1与ω2 两类样本均占相当比例，因此不能简 单地将其确定为哪一类的一个决策域， 而需要对其进行进一步划分。 下面说明使用全体样本进行检验及改 进的具体作法。
i
对每个子类定义一个线性判别函数：
gil ( x) (wil )T x, 其中wil为il子类的权向量。
定义ωi类的线性判别函数为：
gi ( x) max gil ( x)
l 1,2,.....,li
在各子类中找最大的判别函数作为此类的代表， 则对于M类，可定义M个判别函数gi(x),i=1,2,…..M, 因此，决策规则为：
基本思想：用均值作为各类的代表点，用通过 均值连线中点的垂直线对样本集进行分类

§5.2基于距离的分段线性判别函数
§5.2基于距离的分段线性判别函数

把ωi类可以分成li个子类，或者说，把属于ωi 类的样本区 域Ri分为li个子区域。 现在定义mil表示第i类第l个子区域中样本的均值向量，并 以此作为该子区域的代表点。定义判别函数如下：
l 1,2,,li l 1,2,,l j


紧互对原型对位于两类样本的“交遇区”。 用紧互对原型对表示交遇区是合理的。
§5.4用交遇区的样本设计线性分类器
寻找下图的 紧互对原型对？
1类的原型区：
1 1
V1 v , v , v ，
2 1 3 1
2 类的原型区：
1 2 1 2 v1 v2 2 3 v1 v2 3 v13 v2
分段线性分类器的检验决策规则
使用全体样本进行检验及改进的具体方法：
如果现有的决策界面数为m， Hi : aiT y 0, i 1,2,, m 每个超平面可表示为： 每个决策超平面的增广权向量为： ai , i 1,, m