5.4局部训练法 口基本思想：寻找两类中最靠近的样本子集，用它 们设计分类器。 第五章非线性判别函数 ■两类样本在特征空间分布中有若干区域很接近或 甚至有交迭(“交遇区”)。用这些区域中的样本 2009-11-17 (代替整个样本集)进行训练以决定判别函数。 5.4局部训练法 5.4局部训练法 口基本思想：寻找两类中最靠近的样本子集，用它 口紧互对原型对与交遇区 们设计分类器。 ■其实质是先在每类样本集内进行分片划分(“原型 ■两类样本在特征空间分布中有若干区战很接近或 区”)，所使用的方法是聚类方法； 甚至有交迭(“交遇区”)。用这些区域中的样本 ■划分的目的是使每类样本划分成小片后，找到位 (代替整个样本集)进行训练以决定判别函数。 于本类样本占领区域边界上的小片原型区。 ■需要解决的几个问题： ■找边界子集的方法是通过在另一类样本子集中找 近邻的方法实现的。如果发现分属两类的两个原 口如何从样本集中找到“交逼区"： 型互为最近邻，则它们所在区域就属于交遇区。 口如何利用“交遇区”中的样本设计线性分类器： 交遇区就是由这些位于边界上的原型集组成， 口如何进行分类决策， ■每个小片（原型区）都找出一质心(“原型")， 用它代表这个小片。通过计算每个原型与其它原 型的欧氏距离来计算近邻关系。 5.4局部训练法 5.4局部训练法 口紧互对原型对与交逼区 口求紧互对原型集合的方法 ■互对原型之间的（欧式）距离：d",) ■先对两类样本进行聚类分析，从而找出它们各自 ■紧互对原型对需满足 分布相对密集的一些子区域(“原型区”)。 ■在每个原型区中找到质心或距质心最近的样本作 d,）=mid,y)=m鸣dg) 为各原型区的代表，点(“原型”)。 ■分别计算原型集合中互对原型之间的欧氏距离 并找出各原型在对方类型中相距最近的原型， ■从这些最小距离原型关系中找到互为最小距离的 原型对（即“紧互对原型对”）。紧互对原型对的 集合组成“交遇区”。（有时可将找一个最近的原 型改成找k个最近的原型一k紧互对原型对。)
第五章 非线性判别函数 2009-11-17 2 5.4 局部训练法 基本思想：寻找两类中最靠近的样本子集，用它 们设计分类器。 两类样本在特征空间分布中有若干区域很接近或 甚至有交迭（“交遇区”）。用这些区域中的样本 （代替整个样本集）进行训练以决定判别函数。 3 5.4 局部训练法 基本思想：寻找两类中最靠近的样本子集，用它 们设计分类器。 两类样本在特征空间分布中有若干区域很接近或 甚至有交迭（“交遇区”）。用这些区域中的样本 （代替整个样本集）进行训练以决定判别函数。 需要解决的几个问题： 如何从样本集中找到“交遇区”； 如何利用“交遇区”中的样本设计线性分类器； 如何进行分类决策。 4 5.4 局部训练法 紧互对原型对与交遇区 其实质是先在每类样本集内进行分片划分（“原型 区”），所使用的方法是聚类方法； 划分的目的是使每类样本划分成小片后，找到位 于本类样本占领区域边界上的小片原型区。 找边界子集的方法是通过在另一类样本子集中找 近邻的方法实现的。如果发现分属两类的两个原 型互为最近邻，则它们所在区域就属于交遇区。 交遇区就是由这些位于边界上的原型集组成。 每个小片（原型区）都找出一质心（“原型”）， 用它代表这个小片。通过计算每个原型与其它原 型的欧氏距离来计算近邻关系。 5 5.4 局部训练法 紧互对原型对与交遇区 互对原型之间的（欧式）距离： 紧互对原型对需满足 6 5.4 局部训练法 求紧互对原型集合的方法 先对两类样本进行聚类分析，从而找出它们各自 分布相对密集的一些子区域（“原型区”）。 在每个原型区中找到质心或距质心最近的样本作 为各原型区的代表点（“原型”）。 分别计算原型集合中互对原型之间的欧氏距离， 并找出各原型在对方类型中相距最近的原型。 从这些最小距离原型关系中找到互为最小距离的 原型对（即“紧互对原型对”）。紧互对原型对的 集合组成“交遇区”。（有时可将找一个最近的原 型改成找 k 个最近的原型 — k紧互对原型对。）
5.4局部训练法 5.4局部训练法 口利用紧互对原型对设计局部超平面 口利用紧互对原型对设计局部超平面 1.产生初始超平面 2.初始决策面最佳化 由紧互对原型对集合中最近的一对(vmy),产 确定H,'能正确分类的所有紧互对原型对，并由 生一个初始决策面；如可由这两个原型的垂直平 相应的原型区中的所有样本组成局部训练的样本 分平面作为初始分类面，表示成H,方程是 集，设计出线性决策面H。 -r+到r-)-0 对决策面H,”也可找出它能正确分类的所有紧互 对原型对。 如果H与H'的分类效果相同，则不需调整 H;否则将H作为初始决策面重复上述过程 直到所包罗的局部训练样本集不再发生变化为止 记最后所得超平面为H1, 5.4局部训练法 5.4局部训练法 口利用紧互对原型对设计局部超平面 口示例1 3.新决策面的产生与最佳化 将被H]正确分类的紧互对原型对撒走，然后在 剩下的紧互对原型对集合中重复上述步骤，产生 另一个超平面分界面H2: 4.序贯处理 H2 重复上述步骤，直到处理完所有紧互对原型对； 得到一系列超平面，组成分段线性分类器。 11 12 5.4局部训练法 5.4局部训练法 口决策规则 口决策规则 ■设最后得到m个超平面，每段超平面的方程为 ■对(x)的每一种可能的取值Z=1…,2m)，统 计其在两类样本集中出现的次数，记为N(亿)和 H:ay=0,i=l,2,…,m N(); ■记样本x与第i个超平面的法向量的内积为 ■定义比值函数表示每个可能取值中⊙]类的样本所 (x)= ay>0 占比例： 0,ay≤o L,= N,(e) 则得到 N(3)+N2(3) 二（三[(2(x2n( m维二值向量，共2m种可能取值
7 5.4 局部训练法 利用紧互对原型对设计局部超平面 1. 产生初始超平面 由紧互对原型对集合中最近的一对 (v1 m,v2 n)，产 生一个初始决策面；如可由这两个原型的垂直平 分平面作为初始分类面，表示成 H1 ′，方程是 0. 2 1 1 2 1 2 m n T m n x v v v v 8 5.4 局部训练法 利用紧互对原型对设计局部超平面 2. 初始决策面最佳化 确定 H1 ′能正确分类的所有紧互对原型对，并由 相应的原型区中的所有样本组成局部训练的样本 集，设计出线性决策面 H1 * 。 对决策面 H1 * 也可找出它能正确分类的所有紧互 对原型对。 如果 H1 * 与 H1 ′的分类效果相同，则不需调整 H1 * ；否则将 H1 * 作为初始决策面重复上述过程， 直到所包罗的局部训练样本集不再发生变化为止, 记最后所得超平面为H1 。 9 5.4 局部训练法 利用紧互对原型对设计局部超平面 3.新决策面的产生与最佳化 将被 H1 正确分类的紧互对原型对撤走，然后在 剩下的紧互对原型对集合中重复上述步骤，产生 另一个超平面分界面 H2 ； 4. 序贯处理 重复上述步骤，直到处理完所有紧互对原型对； 得到一系列超平面，组成分段线性分类器。 10 5.4 局部训练法 示例1 11 5.4 局部训练法 决策规则 设最后得到 m 个超平面，每段超平面的方程为 记样本 x 与第 i 个超平面的法向量的内积为 则得到 H : 0,i 1,2, ,m; T i ai y , 0, 0 1, 0 ( ) a y a y x T i T i i z 1 2 ( ) ( ), ( ),.... ( ) . m z zz z x xx x m维二值向量，共2m种可能取值 12 5.4 局部训练法 决策规则 对 z(x) 的每一种可能的取值 zj (j=1,…,2m) ，统 计其在两类样本集中出现的次数，记为 N1(zj ) 和 N2(zj )； 定义比值函数表示每个可能取值中ω1类的样本所 占比例： 1 1 2 ( ) . () () j j j j N z L Nz Nz
5.4局部训练法 5.4局部训练法 口决策规则 口示例2 H ■确定决策域 1.如果L,>1/2,则z对应的区域为01的决策域； 2.如果L<1/2,则乙对应的区域为⊙2的决策域： 3.如果L≈1/2，且N()和N()都很小，则对 值为的样本可作拒绝决策； 4.如果L≈12，且N(z)和N(z)较大不可忽 略，则对此区域，用该子集的样本再次进行局部 图中的样本采用上述方法后，决策平面由三个超平 训练法训练，以获得其进一步划分。 面，即H,H与A组成。对训练样本的决策规划：2 )重复上述过程，直至对所有区域都能合理地确定 向量为(1,1,1)，(1,1,0)以及(0,1,0)的区域为02的 决策域，而(0,1,1)，(0,0,0)及(0,0,1)区域则为o1 为哪一类的决策域，或拒识区域为止。 的决策域
13 5.4 局部训练法 决策规则 确定决策域 1. 如果 Lj >>1/2，则 zj 对应的区域为ω1的决策域； 2. 如果 Lj <<1/2，则 zj 对应的区域为ω2 的决策域； 3. 如果 Lj ≈ 1/2，且 N1(zj ) 和 N2(zj ) 都很小，则对 值为 zj 的样本可作拒绝决策； 4. 如果 Lj ≈ 1/2，且 N1(zj ) 和 N2(zj ) 较大不可忽 略，则对此区域，用该子集的样本再次进行局部 训练法训练，以获得其进一步划分。 重复上述过程，直至对所有区域都能合理地确定 为哪一类的决策域，或拒识区域为止。 14 5.4 局部训练法 示例2 图中的样本采用上述方法后，决策平面由三个超平 面，即H1,H2与H3组成。对训练样本的决策规划：z 向量为(1,1,1),(1,1,0)以及(0,1,0)的区域为ω2的 决策域，而(0,1,1),(0,0,0)及(0,0,1)区域则为ω1 的决策域
