《智能决策理论与方法(ppt 55页)》由会员分享，可在线阅读，更多相关《智能决策理论与方法(ppt 55页)（54页珍藏版）》请在金锄头文库上搜索。
1、决策理论与方法(4) 智能决策理论与方法(2),合肥工业大学管理学院 2020年12月9日,决策理论与方法-智能决策理论与方法,智能决策理论与方法,1、智能决策理论的形成背景 2、知识发现 3、粗糙集理论 4、机器学习,决策理论与方法-智能决策理论与方法,机器学习,机器学习是从模拟人类的学习行为出发，研究客观世界和获取各种知识与技能的一些基本方法（如归纳、泛化、特化、类比等），并借助于计算机科学与技术原理建立各种学习模型，从根本上提高计算机智能和学习能力。研究内容是根据生理学、认知科学对人类学习机理的了解，建立人类学习的计算模型或认知模型；发展各种学习理论和学习方法，研究通用的学习算法并进行理
2、论上的分析；建立面向任务且具有特定应用的学习系统。,决策理论与方法-智能决策理论与方法,机器学习归纳学习：泛化,归纳学习是指从给定的关于某个概念的一系列已知的正例和反例中归纳出一个通用的概念描述。 泛化(Generalization)是用来扩展一假设的语义信息，使其能够包含更多的正例。泛化所得到的结论并不总是正确的。 常用泛化方法： 将常量转为变量规则：对于概念F(v)，如果v的某些取值a,b,使F(v)成立，则这些概念可被泛化为：对于v的所有值，F(v)均成立：,决策理论与方法-智能决策理论与方法,机器学习归纳学习：泛化,消除条件规则：一个合取条件可看作是对满足此概念的可能实例集的一个约束。
3、消除一个条件，则该概念被泛化。 添加选项：通过添加更多条件，使得有更多的实例满足概念而使该概念泛化。该规则特别有用的方式是通过扩展某个特定概念的取值范围而增加选项。 将合取转为析取规则,决策理论与方法-智能决策理论与方法,机器学习归纳学习：泛化,爬升概念树规则：通过爬升概念树，低层概念被较高层概念替代。设A表示信息系统中的某个属性如Animal，a,b,分别为对象u,v,在属性A上的取值，若s是概念树上a,b,的父结点，则基于概念树爬升的泛化规则表示为： Nick等人给出了一种面向属性的归纳算法。 过度泛化问题 当某个属性被爬升至过高的概念层会导致冲突的产生，这种现象称为过度泛化。克服过度泛化
4、必须有相应的终止泛化算法的策略。,决策理论与方法-智能决策理论与方法,机器学习归纳学习：泛化,决策理论与方法-智能决策理论与方法,机器学习归纳学习：决策树,决策树学习是以实例为基础的归纳学习算法。所谓决策树是一个类似流程图的树结构，其中树的内结点对应属性或属性集，每个分枝表示检验结果(属性值)，树枝上的叶结点代表所关心的因变量的取值(类标签)，最顶端的结点称为根结点。 决策树学习采用自顶向下的递归方式，在决策树的内部结点进行属性值比较并根据不同的属性值判断从该结点向下的分支，在叶结点得到结论。从根结点到每个叶结点都有唯一的一条路径，这条路径就是一条决策“规则”。 当经过一批训练实例集的训练产生
5、一颗决策树，那么该决策树就可以根据属性的取值对一个未知实例集进行分类。所有的决策树都有一等价的ANN表示；也可用SVM实现相同的功能。,决策理论与方法-智能决策理论与方法,机器学习归纳学习：决策树,决策理论与方法-智能决策理论与方法,机器学习归纳学习：决策树,概念学习系统CLS(Hunt)：从一颗空的决策树出发，添加新的判定结点来改善原来的决策树，直到该决策树能够正确地将训练实例分类为止。 产生根节点T，T包含所有的训练样本； 如果T中的所有样本都是正例，则产生一个标有“1”的节点作为T的子节点，并结束； 如果T中的所有样本都是反例，则产生一个标有“-1”的节点作为T的子节点，并结束； 选择一
6、个属性A(如何选?)，根据该属性的不同取值v1,v2,vn将T中的训练集划分为n个子集，并根据这n个子集建立T的n个子节点T1,T2,Tn，并分别以A=vi作为从T到Ti的分支符号； 以每个子节点Ti为根建立新的子树。,决策理论与方法-智能决策理论与方法,机器学习归纳学习：决策树,决策理论与方法-智能决策理论与方法,机器学习归纳学习：决策树,ID3算法(Quinlan)：ID3算法对CLS做了两方面的改进：(1)增加窗口技术；(2)以信息熵的下降速度(信息增益)作为测试属性选择标准。 窗口技术：对于训练集很大的情形可选择其某个子集(称为窗口)构造一棵决策树，如果该决策树对训练集中的其它样本的判
7、决效果很差，则扩大窗口，选择不能被正确判别的样本加入到窗口中，再建立一个新的决策树，重复这个过程得到最终的决策树，显然不同的初始窗口会产生不同的决策树。,决策理论与方法-智能决策理论与方法,机器学习归纳学习：决策树,信息增益 ：设决策树根结点的样本数据为X=x1,x2,xn，称X的两个训练子集PX(对应类标签为1)和NX (对应类标签为-1)为正例集和反例集，并记正例集和反例集的样本数分别为P和N，则样本空间的信息熵为 假设以随机变量A作为决策树根的测试属性，A具有k个不同的离散值v1,v2,vk，它将X划分为k个子集，且假设第j个子集中包含Pj个正例，Nj个反例，则第j个子集的信息熵为I(P
8、j,Nj)。,决策理论与方法-智能决策理论与方法,机器学习归纳学习：决策树,以A为测试属性的期望信息熵为 以A为根节点的信息增益是： Gain(A)=I(P,N)-E(A) ID3的策略就是选择信息增益最大的属性作为测试属性。 ID3的问题：测试属性的分支越多，信息增益值越大，但输出分支多并不表示该测试属性有更好的预测效果。,决策理论与方法-智能决策理论与方法,机器学习归纳学习：决策树,信息增益率： 其中： 目前一种比较流行的决策树算法C4.5算法就是以信息增益率作为测试属性的选择条件。 生成的决策树往往过大，不利于决策时的应用，需要对其剪枝(Pruning)，请参阅相关文献。,决策理论与方法
9、-智能决策理论与方法,机器学习归纳学习：决策树,示例计算 确定根结点 I(P，N)=-10/16log(10/16)-6/16log(6/16)=-5/8log5-3/8log3+3=0.9544 E(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.9056 E(A1)=1-3/8log3=0.4084 E(A2)=1-3/16log3=0.9056 E(A3)=3-5/8log5-3/8log3=0.9544 因此选A1作为起始根结点。A3没有改变任何信息量，无分类价值，可以删除。,决策理
10、论与方法-智能决策理论与方法,机器学习归纳学习：决策树,确定子树根结点 当A1=0时，所有对象类标签均为-1，此分支结束。 当A1=1时， I(P,N)=-6/8log6/8-2/8log2/8=2-3/4log3=0.8112 E(A0)=E(A2)=1/2=0.5 E(A3)=2-3/4log3=0.8112 A0，A2具有相同的分类能力，任取一个均可。若取A0，则 当A0=0时，所有对象类标签均为+1，此分支结束。 当A0=1时， A2=0，类标签为+1； A2=1，类标签为-1。,决策理论与方法-智能决策理论与方法,机器学习归纳学习：决策树,决策理论与方法-智能决策理论与方法,机器学习
11、神经网络,神经网络(Artificial Neural Networks)是由具有适应性的简单单元组成的广泛并行互连的网络，它的组织能够模拟生物神经系统对真实世界物体所作出的交互反应(T.Koholen)。 神经网络分为前向型、反馈型、随机型以及自组织型。我们重点介绍一下前向型网络及其学习算法。,决策理论与方法-智能决策理论与方法,基本神经元及感知机模型：,机器学习神经网络,wj1,wji,wjn,yj,f(iwijxi-j),x1,xi,xn,决策理论与方法-智能决策理论与方法,机器学习神经网络,神经元函数f的选择 线性函数：f(x)=x 带限的线性函数：为最大输出。 阈值型函数： sigm
12、oid函数：,决策理论与方法-智能决策理论与方法,机器学习神经网络,感知机学习算法：(选取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)+yj t=t+1(为学习率) (3)返回(2)，
13、重复所有的训练样本直到所有的样本输出正确。,决策理论与方法-智能决策理论与方法,机器学习神经网络,多层前向神经网络：包括一个输入层、一个输出层以及多层隐单元。,x1,xi,xI,y1,yk,yK,输入层,隐含层,输出层,u1,ui,uI,v1,vj,vJ,wji,wkj,决策理论与方法-智能决策理论与方法,机器学习神经网络,隐含层的接受与投射(以隐含层第j个神经元为例)： 接受：第j个神经元的值来自于前一层网络(本例是输入层)输出值的加权和，即netj=iwjiui。 投射：将第j个神经元的值经过变换f(netj)，作为下一层网络(本例是输出层)的输入，一般f(x)=1/(1+e-x)。因此可
14、得到yk=jwkjf(netj)。 上述过程一直持续到所有的输出单元得到输出为止，最后一层的输出就是网络的输出。 因此，神经网络是一个黑匣子。,决策理论与方法-智能决策理论与方法,机器学习神经网络,BP算法：BP算法的核心是确定W的调节规则(学习规则)，使实际的输出Y1(t)尽可能接近期望的输出Y(t)。 误差函数：对于每种输入模式特征矢量(x1,x2,xI),都有对应的输出矢量(y1,y2,yK)作为训练网络的输出参考基准。如果用符号Xp表示第p个输入模式特征矢量，用符号Yp表示对应的第p个输出基准矢量。在训练时，同时按输入输出矢量对(Xp,Yp)给出训练集(p=1,P)。对于每个Xp，按照
15、神经元的输入输出公式，一个个一层层地求出网络的实际输出Y1p，则误差函数定义为：,决策理论与方法-智能决策理论与方法,机器学习神经网络,权重调节策略：学习的目标是使E最小或不大于规定的误差。从理论上可用求极值的方法获得权值调整的一种典型规则： 其他最流行的网络结构：径向基函数(RBF)神经网络、自组织映射(SOM)、Hopfield网络等。 Matlab提供了一套神经网络工具箱(Neural Networks Toolbox)，其中包含了一组new函数，用以创建各种类型的神经网络。,决策理论与方法-智能决策理论与方法,机器学习神经网络,newcfcascade-forward backprop
16、agation network. newelmElman backpropagation network. newfffeed-forward backpropagation network. newfftdfeed-forward input-delay backprop network. newgrnngeneralized regression neural network. newhopHopfield recurrent network. newlvqlearning vector quantization network newpnnprobabilistic neural network. newrbradial basis network. newrbeexact radial basis network. newsomself-organizing map,决策理论与方法-智能决策理论与方法,机器学习神经网络,MatL
