第04讲智能决策理论与方法-2.ppt

决策理论与方法 4 智能决策理论与方法 2 合肥工业大学管理学院2019年12月27日 2019年12月27日3时59分 决策理论与方法 智能决策理论与方法 智能决策理论与方法 1 智能决策理论的形成背景2 知识发现3 粗糙集理论4 机器学习 2019年12月27日3时59分 决策理论与方法 智能决策理论与方法 机器学习 机器学习是从模拟人类的学习行为出发 研究客观世界和获取各种知识与技能的一些基本方法 如归纳 泛化 特化 类比等 并借助于计算机科学与技术原理建立各种学习模型 从根本上提高计算机智能和学习能力 研究内容是根据生理学 认知科学对人类学习机理的了解 建立人类学习的计算模型或认知模型 发展各种学习理论和学习方法 研究通用的学习算法并进行理论上的分析 建立面向任务且具有特定应用的学习系统 2019年12月27日3时59分 决策理论与方法 智能决策理论与方法 机器学习 归纳学习 泛化 归纳学习是指从给定的关于某个概念的一系列已知的正例和反例中归纳出一个通用的概念描述 泛化 Generalization 是用来扩展一假设的语义信息 使其能够包含更多的正例 泛化所得到的结论并不总是正确的 常用泛化方法 将常量转为变量规则 对于概念F v 如果v的某些取值a b 使F v 成立 则这些概念可被泛化为 对于v的所有值 F v 均成立 2019年12月27日3时59分 决策理论与方法 智能决策理论与方法 机器学习 归纳学习 泛化 消除条件规则 一个合取条件可看作是对满足此概念的可能实例集的一个约束 消除一个条件 则该概念被泛化 添加选项 通过添加更多条件 使得有更多的实例满足概念而使该概念泛化 该规则特别有用的方式是通过扩展某个特定概念的取值范围而增加选项 将合取转为析取规则 2019年12月27日3时59分 决策理论与方法 智能决策理论与方法 机器学习 归纳学习 泛化 爬升概念树规则 通过爬升概念树 低层概念被较高层概念替代 设A表示信息系统中的某个属性如Animal a b 分别为对象u v 在属性A上的取值 若s是概念树上a b 的父结点 则基于概念树爬升的泛化规则表示为 Nick等人给出了一种面向属性的归纳算法 过度泛化问题当某个属性被爬升至过高的概念层会导致冲突的产生 这种现象称为过度泛化 克服过度泛化必须有相应的终止泛化算法的策略 2019年12月27日3时59分 决策理论与方法 智能决策理论与方法 机器学习 归纳学习 泛化 2019年12月27日3时59分 决策理论与方法 智能决策理论与方法 机器学习 归纳学习 决策树 决策树学习是以实例为基础的归纳学习算法 所谓决策树是一个类似流程图的树结构 其中树的内结点对应属性或属性集 每个分枝表示检验结果 属性值 树枝上的叶结点代表所关心的因变量的取值 类标签 最顶端的结点称为根结点 决策树学习采用自顶向下的递归方式 在决策树的内部结点进行属性值比较并根据不同的属性值判断从该结点向下的分支 在叶结点得到结论 从根结点到每个叶结点都有唯一的一条路径 这条路径就是一条决策 规则 当经过一批训练实例集的训练产生一颗决策树 那么该决策树就可以根据属性的取值对一个未知实例集进行分类 所有的决策树都有一等价的ANN表示 也可用SVM实现相同的功能 2019年12月27日3时59分 决策理论与方法 智能决策理论与方法 机器学习 归纳学习 决策树 2019年12月27日3时59分 决策理论与方法 智能决策理论与方法 机器学习 归纳学习 决策树 概念学习系统CLS Hunt 从一颗空的决策树出发 添加新的判定结点来改善原来的决策树 直到该决策树能够正确地将训练实例分类为止 产生根节点T T包含所有的训练样本 如果T中的所有样本都是正例 则产生一个标有 1 的节点作为T的子节点 并结束 如果T中的所有样本都是反例 则产生一个标有 1 的节点作为T的子节点 并结束 选择一个属性A 如何选 根据该属性的不同取值v1 v2 vn将T中的训练集划分为n个子集 并根据这n个子集建立T的n个子节点T1 T2 Tn 并分别以A vi作为从T到Ti的分支符号 以每个子节点Ti为根建立新的子树 2019年12月27日3时59分 决策理论与方法 智能决策理论与方法 机器学习 归纳学习 决策树 2019年12月27日3时59分 决策理论与方法 智能决策理论与方法 机器学习 归纳学习 决策树 ID3算法 Quinlan ID3算法对CLS做了两方面的改进 1 增加窗口技术 2 以信息熵的下降速度 信息增益 作为测试属性选择标准 窗口技术 对于训练集很大的情形可选择其某个子集 称为窗口 构造一棵决策树 如果该决策树对训练集中的其它样本的判决效果很差 则扩大窗口 选择不能被正确判别的样本加入到窗口中 再建立一个新的决策树 重复这个过程得到最终的决策树 显然不同的初始窗口会产生不同的决策树 2019年12月27日3时59分 决策理论与方法 智能决策理论与方法 机器学习 归纳学习 决策树 信息增益 设决策树根结点的样本数据为X x1 x2 xn 称X的两个训练子集PX 对应类标签为1 和NX 对应类标签为 1 为正例集和反例集 并记正例集和反例集的样本数分别为P和N 则样本空间的信息熵为假设以随机变量A作为决策树根的测试属性 A具有k个不同的离散值v1 v2 vk 它将X划分为k个子集 且假设第j个子集中包含Pj个正例 Nj个反例 则第j个子集的信息熵为I Pj Nj 2019年12月27日3时59分 决策理论与方法 智能决策理论与方法 机器学习 归纳学习 决策树 以A为测试属性的期望信息熵为以A为根节点的信息增益是 Gain A I P N E A ID3的策略就是选择信息增益最大的属性作为测试属性 ID3的问题 测试属性的分支越多 信息增益值越大 但输出分支多并不表示该测试属性有更好的预测效果 2019年12月27日3时59分 决策理论与方法 智能决策理论与方法 机器学习 归纳学习 决策树 信息增益率 其中 目前一种比较流行的决策树算法C4 5算法就是以信息增益率作为测试属性的选择条件 生成的决策树往往过大 不利于决策时的应用 需要对其剪枝 Pruning 请参阅相关文献 2019年12月27日3时59分 决策理论与方法 智能决策理论与方法 机器学习 归纳学习 决策树 示例计算确定根结点I P N 10 16log 10 16 6 16log 6 16 5 8log5 3 8log3 3 0 9544E A0 1 2 4 8log 4 8 4 8log 4 8 1 2 6 8log 6 8 2 8log 2 8 3 2 3 8log3 0 9056E A1 1 3 8log3 0 4084E A2 1 3 16log3 0 9056E A3 3 5 8log5 3 8log3 0 9544因此选A1作为起始根结点 A3没有改变任何信息量 无分类价值 可以删除 2019年12月27日3时59分 决策理论与方法 智能决策理论与方法 机器学习 归纳学习 决策树 确定子树根结点当A1 0时 所有对象类标签均为 1 此分支结束 当A1 1时 I P N 6 8log6 8 2 8log2 8 2 3 4log3 0 8112E A0 E A2 1 2 0 5E A3 2 3 4log3 0 8112A0 A2具有相同的分类能力 任取一个均可 若取A0 则当A0 0时 所有对象类标签均为 1 此分支结束 当A0 1时 A2 0 类标签为 1 A2 1 类标签为 1 2019年12月27日3时59分 决策理论与方法 智能决策理论与方法 机器学习 归纳学习 决策树 2019年12月27日3时59分 决策理论与方法 智能决策理论与方法 机器学习 神经网络 神经网络 ArtificialNeuralNetworks 是由具有适应性的简单单元组成的广泛并行互连的网络 它的组织能够模拟生物神经系统对真实世界物体所作出的交互反应 T Koholen 神经网络分为前向型 反馈型 随机型以及自组织型 我们重点介绍一下前向型网络及其学习算法 2019年12月27日3时59分 决策理论与方法 智能决策理论与方法 基本神经元及感知机模型 机器学习 神经网络 wj1 wji wjn yj f iwijxi j x1 xi xn 2019年12月27日3时59分 决策理论与方法 智能决策理论与方法 机器学习 神经网络 神经元函数f的选择线性函数 f x x带限的线性函数 为最大输出 阈值型函数 sigmoid函数 2019年12月27日3时59分 决策理论与方法 智能决策理论与方法 机器学习 神经网络 感知机学习算法 选取f为阈值函数 学习权值向量w 1 初始化 将权值向量和阈值赋予随机量 t 0 2 连接权的修正 设训练样本的输入为x1 xi xn 期望输出为yj 1 进行如下计算 计算网络输出 1 y t f iwij t xi t j t 计算期望输出与实际输出的误差 e t yj y t 若e 0 则说明当前样本输出正确 不必更新权值 否则更新权值和阈值wij t 1 wij t yjxi t j t 1 j t yjt t 1 为学习率 3 返回 2 重复所有的训练样本直到所有的样本输出正确 2019年12月27日3时59分 决策理论与方法 智能决策理论与方法 机器学习 神经网络 多层前向神经网络 包括一个输入层 一个输出层以及多层隐单元 x1 xi xI y1 yk yK 输入层 隐含层 输出层 u1 ui uI v1 vj vJ wji wkj 2019年12月27日3时59分 决策理论与方法 智能决策理论与方法 机器学习 神经网络 隐含层的接受与投射 以隐含层第j个神经元为例 接受 第j个神经元的值来自于前一层网络 本例是输入层 输出值的加权和 即netj iwjiui 投射 将第j个神经元的值经过变换f netj 作为下一层网络 本例是输出层 的输入 一般f x 1 1 e x 因此可得到yk jwkjf netj 上述过程一直持续到所有的输出单元得到输出为止 最后一层的输出就是网络的输出 因此 神经网络是一个黑匣子 2019年12月27日3时59分 决策理论与方法 智能决策理论与方法 机器学习 神经网络 BP算法 BP算法的核心是确定W的调节规则 学习规则 使实际的输出Y1 t 尽可能接近期望的输出Y t 误差函数 对于每种输入模式特征矢量 x1 x2 xI 都有对应的输出矢量 y1 y2 yK 作为训练网络的输出参考基准 如果用符号Xp表示第p个输入模式特征矢量 用符号Yp表示对应的第p个输出基准矢量 在训练时 同时按输入输出矢量对 Xp Yp 给出训练集 p 1 P 对于每个Xp 按照神经元的输入输出公式 一个个一层层地求出网络的实际输出Y1p 则误差函数定义为 2019年12月27日3时59分 决策理论与方法 智能决策理论与方法 机器学习 神经网络 权重调节策略 学习的目标是使E最小或不大于规定的误差 从理论上可用求极值的方法获得权值调整的一种典型规则 其他最流行的网络结构 径向基函数 RBF 神经网络 自组织映射 SOM Hopfield网络等 Matlab提供了一套神经网络工具箱 NeuralNetworksToolbox 其中包含了一组new函数 用以创建各种类型的神经网络 2019年12月27日3时59分 决策理论与方法 智能决策理论与方法 机器学习 神经网络 newcf cascade forwardbackpropagationnetwork newelm Elmanbackpropagationnetwork newff feed forwardbackpropagationnetwork newfftd feed forwardinput delaybackpropnetwork newgrnn generalizedregressionneuralnetwork newhop Hopfieldrecurrentnetwork newlvq learningvectorquantizationnetworknewpnn probabilisticneuralnetwork newrb radialbasisnetwork newrbe exactradialbasisnetwork newsom self organizingmap 2019年12月27日3时59分 决策理论与方法 智能决策理论与方法 机器学习 神经网络 MatLab工具箱之多层前向BP网络示例P 012345678910 实际输出 已学习 plot P T P Y o 2019年12月27日3时59分 决策理论与方法 智能决策理论与方法 机器学习 神经网络 2019年12月27日3时59分 决策理论与方法 智能决策理论与方法 机器学习 支持向量机 提出的背景 相对神经网络的不足 1 大量的控制参数 神经网络的结构 传输函数 损失函数 学习参数 训练算法以及训练代数都需要基于反复试验的方法获得 2 存在过度拟合问题 许多现实的数据包含大量的噪声 如果神经网络规模太大 并且网络训练时间控制不适当 那么神经网络既会获得数据中的有用信息 也会得到不希望的噪声 其结果只能用于训练数据点 而对训练数据以外的样本点缺乏泛化能力 2019年12月27日3时59分 决策理论与方法 智能决策理论与方法 机器学习 支持向量机 3 局部极小值问题 神经网络训练过程中主要使用梯度下降的算法 容易陷入局部极小值 4 收敛速度慢 神经网络主要采用基于梯度的BP学习算法 当用于大规模问题时收敛慢 5 黑箱问题 神经网络没有明确的函数形式解释输入和输出变量之间的相互关系 很难解释神经网络获得的结论 20世纪90年代Vapnik提出了支持向量机 SupportVectorMachines SVM 它被看作是高维空间函数表达的一般方法 使用SVM方法 人们可以在很高维的空间里构造好的分类规则 2019年12月27日3时59分 决策理论与方法 智能决策理论与方法 机器学习 支持向量机 结构化风险最小化与经验风险最小化原则经验风险最小化原则考虑分类问题 样本集为U x1 x2 xl m维空间中的l个向量 每个向量对应一个类别 类别空间Y 1 1 记p x y 表示对象x为y类的概率分布 分类的任务就是寻找分类器f U Y且使期望风险最小 f的期望风险为 在有限样本的情况下 p x y 是未知的 因此期望风险无法计算 常使用经验风险代替 且当l 时两者相等 2019年12月27日3时59分 决策理论与方法 智能决策理论与方法 机器学习 支持向量机 如果成立 则称经验风险最小化原则 EmpiricalRiskMinimization ERM 具有一致性 结构风险最小化原则Vapnik在1971年证明经验风险最小值未必收敛于期望风险最小值 即ERM不成立 因此提出了结构风险最小化原则 StructuralRiskMinimization SRM 为小样本统计理论奠定了基础 2019年12月27日3时59分 决策理论与方法 智能决策理论与方法 机器学习 支持向量机 Vapnik和Chervonenkis通过研究 得出了期望风险和经验风险的如下关系以概率1 成立 即l为样本点数目 参数0 1 h为函数f的维数 简称VC维 在无法求得期望风险的情形下找到了它的一个上界 不等式右边与样本的具体分布无关 即Vapnik的统计学习理论无需假设样本分布 克服了高维分布对样本点需求随维数而指数增长的问题 这是小样本统计理论与经典统计理论的本质区别 也是将Vapnik统计方法称之为小样本统计理论的原因 VC维置信度 2019年12月27日3时59分 决策理论与方法 智能决策理论与方法 机器学习 支持向量机 讨论 1 如果l h较大 则期望风险 实际风险 主要由经验风险来决定 因此对于大样本集经验风险经常能给出较好结果 2 如果比值l h较小 小样本集 则小的经验风险并不能保证有小的期望风险值 必须同时考虑经验风险和置信范围 称之为VC维置信度 VC维在其中起重要作用 实际上置信范围是h的增函数 在样本点数目l一定时 分类器越复杂 即VC维越大 则置信范围越大 导致实际风险与经验风险的差别越大 结论 要想使实际风险最小不仅要使经验风险最小 还同时需要使分类器函数f的VC维h尽可能最小 这就是结构风险最小化原则 因此寻找最小属性集变得非常有意义 2019年12月27日3时59分 决策理论与方法 智能决策理论与方法 机器学习 支持向量机 支持向量分类模型基本分类思想 支持向量机的核心思想是将结构风险最小化原则引入到分类问题中 从线性可分情况下的最优分类超平面发展而来的 其本质是在训练样本中找出具有最优分类超平面的支持向量 在数学上归结为一个求解不等式约束条件的二次规划问题 2019年12月27日3时59分 决策理论与方法 智能决策理论与方法 机器学习 支持向量机 margin与支持向量 设样本集为U x1 x2 xl m维空间中的l个向量 类别空间Y 1 1 xi为输入向量 对应的类标签为yi 1或 1 若样本集是线性可分的 则存在超平面H wx b 0使得 1 当wxi b 1时 yi 1 2 当wxi b 1时 yi 1其中 w为权值向量 b为偏离值 统一 1 2 得 yi wxi b 1对于样本集的任一向量 点 xi 其到超平面H的距离为 2019年12月27日3时59分 决策理论与方法 智能决策理论与方法 机器学习 支持向量机 那么 margin的大小可按下式计算 margin d d d min di i 1 2 l yi 1 d min di i 1 2 l yi 1 若存在样本点xi使得wxi b 1 则称此向量xi为支持向量 此时 d d 1 w margin 2 w 分类模型 寻求最优超平面H 使得margin最大 因此分类问题转为二次凸规划问题 2019年12月27日3时59分 决策理论与方法 智能决策理论与方法 机器学习 支持向量机 线性不可分 可引入核函数将线性不可分问题转换为高维空间的线性可分问题 常见核函数有 d次多项式函数高斯径向基函数神经网络核函数 2019年12月27日3时59分 决策理论与方法 智能决策理论与方法 机器学习 遗传算法 遗传算法 GeneticAlgorithm GA 是一种借鉴生物界自然选择和自然遗传机制的高度并行 随机 自适应搜索算法 它利用结构化的随机交换技术组合群体中各个结构中最好的生存因素 形成最佳代码串并使之一代一代地进化 最终获得满意的优化结果 其基本构成要素有染色体编码 适应度函数 遗传算子 遗传 交叉 变异 以及相关的运行参数 种群规模 20 100 进化代数 100 500 交叉概率Pc 0 4 0 99 变异概率Pm 0 0001 0 1 2019年12月27日3时59分 决策理论与方法 智能决策理论与方法 机器学习 遗传算法 遗传算法基本步骤 1 确定遗传算法的有关参数 群体规模N 最大代数M 交叉概率Pc 变异概率Pm 停机准则 初始化种群 随机产生N条表示可能方案集的染色体 2 是否满足停机准则 若是 终止 3 计算群体中每个个体的适应值 4 复制 根据适应度函数进行选择生成中间群体 5 交叉 以概率Pc选择两个个体进行染色体交换形成新的个体 替代老个体插入群体中 6 变异 按概率Pm选择某条染色体的某一位进行改变形成新的个体 替代老个体插入群体中 7 转到 2 2019年12月27日3时59分 决策理论与方法 智能决策理论与方法 机器学习 遗传算法 遗传算法示例 基于GA的连续属性集离散化问题求解问题描述 基于GA的离散化思想 将连续属性离散化的分割点选择问题转化为分割点组合的寻优问题 首先对分割点空间进行遗传编码 以分割点编码构成染色体 用基于粗糙集理论的适应度函数来启发并指导进化 最终得到较优的能充分体现离散化效果的分割点组合代码串 从而找到离散化连续属性集的全部分割点 2019年12月27日3时59分 决策理论与方法 智能决策理论与方法 机器学习 遗传算法 遗传编码 用编码形式表示决策变量的初始解 把所有分割点表示成确定长度的二进制串 每个分割点与串中的一部分相联系 具体地 设连续属性集C c1 c2 cm 对于任意ci C 选择长度为l i 的二进制编码表示分割点cij j 1 2 ki 1 则表示属性ci的所有分割点的串长为l i ki 1 分割点cij与长度为l i 的二进制编码之间的值对应关系可由下式确定 式中m s 是长度为l i 的二进制编码中第s位的编码值 si为连续属性ci的起点值 ei为其终点值 2019年12月27日3时59分 决策理论与方法 智能决策理论与方法 机器学习 遗传算法 对C 中的所有属性进行编码形成的二进制串长度为 因此 连续属性集离散化问题的搜索空间规模为2l l i 的选择与样本的规模有关 例如 若样本规模为200 连续属性集C c1 c2 c3 k1 k2 4 k3 3 选择l 1 l 2 l 3 5 则l 5 3 5 3 5 2 40 问题的搜索空间规模为240 10120011010010110110110010101111010011110011表示了分割点集的一条染色体 2019年12月27日3时59分 决策理论与方法 智能决策理论与方法 机器学习 遗传算法 适应度函数 体现决策目标的优化方向 从粗糙集理论的角度 离散化往往会破坏信息系统中原来的不可分辨关系 即原来两个可分辨的对象可能变为不可分辨 这样等价类包含的对象数量增加 而等价类数量减少 分类能力可能减弱 因此使离散化后系统的分类能力最大是我们的优化目标 因此可用决策属性d对C 的依赖度作为适应度函数 2019年12月27日3时59分 决策理论与方法 智能决策理论与方法 机器学习 遗传算法 复制算子 把当前群体中的个体按与适应值成比例的概率复制到新的群体中 复制过程应用赌盘技术选择要被复制的串 复制算子的作用效果将提高群体的平均适应值 设种群数为N 则将赌盘分成N份 第i份的比例按如下值确定 2019年12月27日3时59分 决策理论与方法 智能决策理论与方法 机器学习 遗传算法 2019年12月27日3时59分 决策理论与方法 智能决策理论与方法 机器学习 遗传算法 交叉算子 按一定的概率从交配池中任选2条染色体进行多点杂交 随机互换两个染色体某些位上的基因 方法如下 挑选2个染色体串 按概率确定它