模式识别——非线性分类器.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 通过映射 把分类问题转换为线性的 如果是这样 得到则存在超平面w Rk 得到如下分类器 因此 可以把判别函数近似表示为 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 C ai 0 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 Thedecisionhyperpla