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

1,第5章非线性判别函数,实际问题经常不是线性可分的，即决策面是非线性函数。,常用方法：,分段线性函数，见P83图5-3，采用距离为分类标准，一般要求对样本的分布有所了解。,关键是子类数目，权值确定也比较复杂。,直接使用非线性判别函数，如神经网络方法。,非线性支持向量机，公认是比较好的分类器设计方法。,异或(XOR)问题,不存在决策线将两类分开.,2,而与和或问题是线性可分的,两层感知器,对于问题,可以划两条线，而不是一条线。见下页图形,3,B类位于阴影区域之外，而A类位于阴影区域之内。,分类器可以采用两阶段的设计方法。,阶段1划两条线（超平面）,每条线由一个感知器实现,阶段2根据y1,y2的值确定x相对两条线的位置,等价地:阶段1实现如下影射,4,决策在变换后的数据y域进行:,可以再划一条线，将两类分开，该线用一个感知器实现。,阶段1实现了一个映射，将线性不可分问题转化为线性可分问题。,神经网络的结构如下图所示。,5,这是一个两层感知机，包含一个隐层和一个输出层。激活函数为,图中的神经元实现以下直线（超平面）,误差反向传播算法,迭代计算连接权值的算法程序，使代价函数最小化,6,优化过程需要计算导数，不连续的激活函数存在问题,可以采用下面的连续函数近似，也可以采用其他函数,函数中的a决定了函数的近似程度。,有两种训练方法,批量训练方法：所有样本一起计算误差，统一调节权值,单样本训练方法：每个样本误差调节一次权值,7,8,主要问题:算法可能收敛到局部极小值,9,过拟合问题网络把噪声的信息也学来了，推广能力差,10,广义线性判别函数,回忆异或问题，映射,激活函数把非线性问题变换成线性问题。,一般情况，是否存在函数与合适的k，通过映射,把分类问题转换为线性的？,如果是这样，得到则存在超平面wRk，得到如下分类器,因此，可以把判别函数近似表示为,11,径向基函数网络RadialBasisFunctionNetworks(RBF),选择非线性函数为径向基函数,径向基函数示意图,12,等价于激活函数为RBF函数的单层神经网络,13,例:用RBF网络解决异或(XOR)问题,定义RBF函数的中心和宽度为,隐层神经元输出为,14,RBF网络的分类结果,15,RBF网络训练,固定中心:在数据点中间随机选择中心，宽度i心也是固定的，那么,变成典型的线性分类器设计问题,中心训练是非线性优化问题，可以采用监督学习和非监督学习相结合的方法进行分类器设计。,RBF网络具有局部性质，收敛速度快但推广能力弱。,多层感知器与RBF网络比较,采用聚类分析方法确定中心，再用监督学习方法进行线性分类器设计。,多层感知器具有全局性质，收敛速度慢但推广能力强。,16,非线性支持向量机,特征向量的维数增加可以增大样本线性可分的概率。,采用下面的非线性映射,在Rk空间采用支持向量机分类,需要在高维空间计算内积，计算复杂性增加,解决方法：高维空间内积表示成低维空间内积的函数,17,Mercer定理,则对任意函数,H空间内积定义为,下式成立,（5-50）,反之若（5-50）式成立，则K(x,x)一定对应某个空间H的内积,K(x,x)是对称的，称为核函数。,常用的核函数,多项式核函数,RBF核函数,Sigmoid核函数,18,非线性支持向量机分类步骤,Step1:选择核函数。隐含着一个到高维空间的映射，虽然不知道具体形式。,Step2:求解优化问题,s.t.Cai0，i=1,2,N,(5-48）,结果得到隐式组合,Step3：对给定样本x进行分类,19,非线性支持向量机结构,20,21,决策树DecisionTrees,Thisisafamilyofnon-linearclassifiers.Theyaremultistagedecisionsystems,inwhichclassesaresequentiallyrejected,untilafinallyacceptedclassisreached.,决策树属于非线性分类器。它是多阶段的决策系统，决策过程顺序拒绝一些类，一直达到最终接受的类为止。,Thefeaturespaceissplitintouniqueregionsinasequentialmanner.,通过顺序划分方法将特征空间分解为唯一的区域（属于唯一的一个类）。,Uponthearrivalofafeaturevector,sequentialdecisions,assigningfeaturestospecificregions,areperformedalongapathofnodesofanappropriatelyconstructedtree.,对于未知类别的特征向量，通过顺序决策，将其分派到特定的区域，该过程通过对事先构造树的节点路径搜索来实现。,Thesequenceofdecisionsisappliedtoindividualfeatures,andthequeriesperformedineachnodeareofthetype:,对每个特征顺序决策，每个节点进行下面类型的判定：,isfeature,a是预先选择的阈值参数,Thefiguresbelowaresuchexamples.,ThistypeoftreesisknownasOrdinaryBinaryClassification.,Thedecisionhyperplan