模式识别——非线性分类器

1、1v第第5 5章章 非线性判别函数非线性判别函数实际问题经常不是线性可分的，即决策面是非线性函数。实际问题经常不是线性可分的，即决策面是非线性函数。v常用方法：常用方法： 分段线性函数，见分段线性函数，见P P8383 图图5 5- -3 3，采用距离为分类标准，一般要求对样本的，采用距离为分类标准，一般要求对样本的分布有所了解。分布有所了解。 v关键是子类数目，权值确定也比较复杂。关键是子类数目，权值确定也比较复杂。直接使用非线性判别函数，如神经网络方法。直接使用非线性判别函数，如神经网络方法。非线性支持向量机，公认是比较好的分类器设计方法。非线性支持向量机，公认是比较好的分类器设计方法。v

2、异或异或( (XOR) )问题问题x1x2XORClass000B011A101A110Bv不存在决策线将两类分开不存在决策线将两类分开. .2v而与和或问题是线性可分的而与和或问题是线性可分的v两层感知器两层感知器对于问题对于问题, , 可以划两条线，而不是一条线。见下页图形可以划两条线，而不是一条线。见下页图形3 B B类位于阴影区域之外，而类位于阴影区域之外，而A A类类位于阴影区域之内。位于阴影区域之内。 分类器可以采用两阶段的设计分类器可以采用两阶段的设计方法。方法。 阶段阶段1 1 划两条线（超平面）划两条线（超平面） 12( )( )0ggxx每条线由一个感知器实现每条线由一个感

3、知器实现0( )0( ) 1, 21( )0iiiigyf gigxxx 阶段阶段2 2 根据根据 y1, y2 的值确定的值确定 x 相对两条线的位置相对两条线的位置1st phase2ndphasex1x2y1y2000(-)0(-)B(0)011(+)0(-)A(1)101(+)0(-)A(1)111(+)1(+)B(0)v 等价地等价地: : 阶段阶段1 1 实现如下影射实现如下影射12, Tyyxy4v决策在变换后的数据决策在变换后的数据 y y 域进行域进行: :v 可以再划一条线，将两类分开，可以再划一条线，将两类分开，该线用一个感知器实现。该线用一个感知器实现。 阶段阶段1 1

4、实现了一个映射，将线性实现了一个映射，将线性不可分问题转化为线性可分问题。不可分问题转化为线性可分问题。 神经网络的结构如下图所示。神经网络的结构如下图所示。5 这是一个两层感知机，包这是一个两层感知机，包含一个隐层和一个输出层。含一个隐层和一个输出层。激活函数为激活函数为00( )10 xf xx 图中的神经元实现以下直图中的神经元实现以下直线（超平面）线（超平面）0212)(023)(021)(21212211yyygxxxgxxxg误差反向传播算法误差反向传播算法v迭代计算连接权值的算法程序，使代价函数最小化迭代计算连接权值的算法程序，使代价函数最小化60001)(xxxf)exp(11

5、)(axxfv优化过程需要计算导数，不连续的激活函数存在问题优化过程需要计算导数，不连续的激活函数存在问题v可以采用下面的连续函数近似，也可以采用其他函数可以采用下面的连续函数近似，也可以采用其他函数v函数中的函数中的 a 决定了函决定了函数的近似程度。数的近似程度。v有两种训练方法有两种训练方法批量训练方法：所有批量训练方法：所有样本一起计算误差，样本一起计算误差，统一调节权值统一调节权值单样本训练方法：每单样本训练方法：每个样本误差调节一次个样本误差调节一次权值权值78 主要问题主要问题: : 算法可能收敛到局部极小值算法可能收敛到局部极小值9 过拟合问题网络把噪声的信息也学来了，推广能力

6、差过拟合问题网络把噪声的信息也学来了，推广能力差1012( )( )f gf gxxyx(.)fv 广义广义线性判别函数线性判别函数回忆异或问题，映射回忆异或问题，映射激活函数把非线性问题变换成线性问题。激活函数把非线性问题变换成线性问题。一般情况，是否存在函数与合适的一般情况，是否存在函数与合适的 k k，通过映射，通过映射1( ).( )kffxxyx把分类问题转换为线性把分类问题转换为线性的？的？如果是这样，得到如果是这样，得到 则存在超平面则存在超平面 wRk k，得到如下分类器，得到如下分类器0102If 0, 0, TTwww yxw yx因此，可以把判别函数近似表示为因此，可以把

7、判别函数近似表示为01( )( ) () 0ki iigww fxx11v径向基函数网络径向基函数网络 Radial Basis Function Networks (RBF)选择非线性函数为径向基函数选择非线性函数为径向基函数22( )exp2iiifxcx径向基函数示意径向基函数示意图图12222exp)(iiicxxfv等价于激活函数为等价于激活函数为RBFRBF函数的单层神经网络函数的单层神经网络 131212110, , 102 cc2122exp()exp() xcyxc368. 0368. 010 ,368. 0368. 001135. 0111 ,1135. 000v例例: :

8、用用RBFRBF网络解决异或网络解决异或(XOR)问题问题 定义定义RBFRBF函数的中心和宽度为函数的中心和宽度为隐层神经元输出为隐层神经元输出为x1x2XORClass000B011A101A110B142212( )exp()exp()10g xxcxc01yyyg21)(RBFRBF网络的分类结果网络的分类结果150( )Tgwxw yvRBF 网络训练网络训练 固定中心固定中心: 在数据点中间随机选择中心，宽在数据点中间随机选择中心，宽度度i心也是固定的，那么心也是固定的，那么 变成典型的线性分类器设计问题变成典型的线性分类器设计问题 中心训练是非线性优化问题，可以采用监督学习和非中

9、心训练是非线性优化问题，可以采用监督学习和非监督学习相结合的方法进行分类器设计。监督学习相结合的方法进行分类器设计。 RBF 网络具有局部性质，收敛速度快但推广能力弱。网络具有局部性质，收敛速度快但推广能力弱。v多层感知器与多层感知器与RBF 网络比较网络比较 采用聚类分析方法确定中心，再用监督学习方法进行采用聚类分析方法确定中心，再用监督学习方法进行线性分类器设计。线性分类器设计。 多层感知器具有全局性质，收敛速度慢但推广能力强。多层感知器具有全局性质，收敛速度慢但推广能力强。16v非线性支持向量机非线性支持向量机 特征向量的维数增加可以增大样本线性可分的概率。特征向量的维数增加可以增大样本

10、线性可分的概率。 采用下面的非线性映射采用下面的非线性映射, dkRRkdxy在在Rk空间采用支持向量机分类空间采用支持向量机分类1,11max ( )()2NNiij ijijii jQy yyy需要在高维空间计算内积，计算复杂性增加需要在高维空间计算内积，计算复杂性增加解决方法：高维空间内积表示成低维空间内积的函数解决方法：高维空间内积表示成低维空间内积的函数212Let , TxxRx2131 222Let 2xx xRxxy2Then()TTijijy yx x17vMercer 定理定理 Let ( )Hxy x 则对任意函数则对任意函数( , )( ( )( )Kx x x x H

11、空间内积定义为空间内积定义为2( )0and( )ggd xxx 下式成立下式成立(,)()()0ggd dx xxxx x（5-50）反之若（反之若（5-50）式成立，则）式成立，则 K(x , x) 一定对应某个空间一定对应某个空间H的内积的内积vK(x , x) 是对称的，称为核函数。是对称的，称为核函数。v常用的核函数常用的核函数多项式核函数多项式核函数( , )( 1) , 0qKqx xx xRBF核函数核函数Sigmoid 核函数核函数22( , )exp/Kx xxx( , )tanh( ()Kvcx xx x181()sNiiiiyw xu非线性支持向量机分类步骤非线性支持向

12、量机分类步骤 Step 1:Step 1: 选择核函数。隐含着一个到高维空间的映射，虽然选择核函数。隐含着一个到高维空间的映射，虽然不知道具体形式。不知道具体形式。 Step 2:Step 2: 求解优化问题求解优化问题1,11max ( )( ,)2NNiij ijijii jQy y Kx xs. t. C i 0，i=1,2,N10Ni iiy(5-48）结果得到隐式组合结果得到隐式组合 Step 3Step 3： 对给定样本对给定样本 x 进行分类进行分类121() if ( ) , )( )0sNiiiigy (b xx x19非线性支持向量机结构非线性支持向量机结构2021v决策树

13、Decision TreesThis is a family of non-linear classifiers. They are multistage decision systems, in which classes are sequentially rejected, until a finally accepted class is reached. 决策树属于非线性分类器。它是多阶段的决策系统，决策过程顺序拒绝一决策树属于非线性分类器。它是多阶段的决策系统，决策过程顺序拒绝一些类，一直达到最终接受的类为止。些类，一直达到最终接受的类为止。The feature space is

14、split into unique regions in a sequential manner.通过顺序划分方法将特征空间分解为唯一的区域（属于唯一的一个类）。通过顺序划分方法将特征空间分解为唯一的区域（属于唯一的一个类）。Upon the arrival of a feature vector, sequential decisions, assigning features to specific regions, are performed along a path of nodes of an appropriately constructed tree.对于未知类别的特征向量，通过

15、顺序决策，将其分派到特定的区域，该过对于未知类别的特征向量，通过顺序决策，将其分派到特定的区域，该过程通过对事先构造树的节点路径搜索来实现。程通过对事先构造树的节点路径搜索来实现。The sequence of decisions is applied to individual features, and the queries performed in each node are of the type:对每个特征顺序决策，每个节点进行下面类型的判定：对每个特征顺序决策，每个节点进行下面类型的判定：axivis feature 是预先选择的阈值参数是预先选择的阈值参数vThe figures below are such