第04讲不确定性决策理论与方法.ppt

决策理论与方法不确定性决策理论与方法,2020年5月18日,不确定性决策理论与方法,1、不确定性决策概述2、关联规则发现3、聚类分析4、连接分析5、粗糙集分析6、决策树7、神经网络8、支持向量机,不确定性决策,不确定性决策：指难以获得各种状态发生的概率，甚至对未来状态都难以把握的决策问题。特点：状态的不确定性。不确定性：不确定性来自人类的主观认识与客观实际之间存在的差异。事物发生的随机性、人类知识的不完全、不可靠、不精确和不一致以及自然语言中存在的模糊性和歧义性，都反映了这种差异，都会带来不确定性。不确定性就造成了具有相同描述信息的对象可能属于不同概念。解决问题的主要理论方法：人工智能与不确定性理论,不确定性决策准则,在决策者无法获取状态的概率时，贝叶斯决策准则就难以凑效。下面介绍几种常用的不确定性决策准则。悲观准则或极小化极大准则【Wald,1950】考察采取行动ai，i=1,2,m时可能出现的最坏后果，即最大损失si或最小效用ui；选择行动ak，使得sk(uk)在所有行动中最小(最大)。乐观准则考察采取行动ai，i=1,2,m时可能出现的最好后果，即最小损失oi或最大效用vi；选择行动ak，使得ok(vk)在所有行动中最小(最大)。,不确定性决策准则,乐观系数法【Hurwicz,1951】考察采取行动ai，i=1,2,m时可能出现的最坏后果和最好后果，即最大损失si和最小损失oi或最小效用ui和最大效用vi；设决策人的乐观系数为，则选择行动ak，使得(1-)sk+ok(1-)uk+vk)在所有行动中最小(最大)。,不确定性决策准则,后悔值极小化极大法【Savage,1951】在状态j下考察采取行动ai的损失lji或效用uji和，并将其与在此状态下采取不同行动时的最小损失sj或最大效用uj进行比较，其差值的大小定义为后悔值rji，从而形成一个后悔值表；针对后悔值表，应用悲观准则求解：找出不同状态下采取行动ai的最大后悔值pi，然后再使所有行动的最大后悔值极小，其所对应的行动记为决策结果。,不确定性决策准则,等概率法【Laplace,1825】Laplace认为，对真实的自然状态一无所知等价于所有自然状态具有相同的概率。然后借助于贝叶斯准则进行决策。,不确定性决策准则,不确定性决策问题举例【Milnor,1954】,不确定性决策准则,不确定性决策问题举例【Milnor,1954】,不确定性决策准则,智能决策理论与方法形成背景,人类面临越来越复杂的决策任务和决策环境：决策问题所涉及的变量规模越来越大；决策所依赖的信息具有不完备性、模糊性、不确定性等特点，使得决策问题难以准确地量化表示；某些决策问题及其目标可能是模糊的、不确定的，使得决策者对自己的偏好难以明确，随着决策分析的深入，对决策问题的认知加深，自己原有的偏好/倾向得到不断地修正，使得决策过程出现不断调整的情况。这时，传统的决策数学模型已经难以胜任求解复杂度过高的决策问题、含有不确定性的决策问题以及半结构化、非结构化的决策问题，因而产生了智能决策理论、方法及技术。,智能决策理论与方法AI的应用模式,智能决策方法是应用人工智能(ArtificialIntelligence,AI)相关理论方法，融合传统的决策数学模型和方法而产生的具有智能化推理和求解的决策方法，其典型特征是能够在不确定、不完备、模糊的信息环境下，通过应用符号推理、定性推理等方法，对复杂决策问题进行建模、推理和求解。AI应用于决策科学主要有两种模式：针对可建立精确数学模型的决策问题，由于问题的复杂性，如组合爆炸、参数过多等而无法获得问题的解析解，需要借助AI中的智能搜索算法获得问题的数值解；针对无法建立精确数学模型的不确定性决策问题、半结构化或非结构化决策问题，需要借助AI方法建立相应的决策模型并获得问题的近似解。,知识发现动机,智能决策的核心是如何获取支持决策的信息和知识。,问题知识获取是基于知识的系统(KBS)的最大瓶颈,知识发现动机,问题推理规则的获取与KBS中知识获取一样难，因而基于案例推理(Case-BasedReasoning)渐渐变成基于案例检索(Case-BasedRetrieving)。,知识发现动机,问题数据分析师与决策者之间对问题的理解存在偏差缺少有创造性的决策建议技术问题：如查询效率(RDBMS),知识发现动机,优点知识独立于问题本身知识的获取主要通过数据挖掘实现有创造性收获,DataMiningwithintheDSS,知识发现动机,KDD带来的新问题知识发现问题：如何从数据中将知识挖掘出来？面临许多技术问题：如数据异构问题、数据具有噪音且信息不完整、使用什么样的挖掘算法、知识如何表示等知识评价问题：数据本身具有权威性、客观性，但知识不具备。知识如何评价？,参考书推荐,KDDx2=(2,2,2)x3=(1,1,2);x4=(2,2,3)点对称距离(不能度量两个对象的差异幅度)：,聚类：相似性度量,相似性度量方法二元型特征(特征取值仅为0,1)设每个对象都可用d个特征表示，如果对象有此特征则标记为1，否则标记为0。对于任意两个对象xi,xj，n11、n00、n10、n01分别表示两者都有、两者都无、xi有xj无、xi无xj有的特征数，则：或根据不同的情境，w可以取1(Jaccard),2(Sokal),1/2(Gower)。,聚类：相似性度量,相似性度量方法名词型(多元)特征名词性特征是指取值超过2个状态的离散型特征，如性别、颜色等。相似性一般采用特征值匹配的办法衡量。,聚类：相似性度量,相似性度量方法混合情形实际上，我们遇到的大多数数据对象所包含的特征可能各种类型都有，这时怎么办？将所有特征映射到0,1实数域；将所有特征都映射成二元特征；通用测度：Sijl表示第l个特征的相似度，ijl表示是否使用该特征参与测度。,聚类：相似性度量,相似性度量的邻近矩阵对于N个输入数据对象，两两之间的相似性可以表示成一个NN阶对称矩阵，称为邻近矩阵。,聚类：主要方法,层次聚类方法k-means概率混合模型图模型与谱聚类组合搜索技术模糊聚类基于神经网络基于核的方法,Givenk,thek-meansalgorithmisimplementedinfoursteps:PartitionobjectsintoknonemptysubsetsComputeseedpointsasthecentroidsoftheclustersofthecurrentpartitioning(thecentroidisthecenter,i.e.,meanpoint,ofthecluster)AssigneachobjecttotheclusterwiththenearestseedpointGobacktoStep2,stopwhentheassignmentdoesnotchange,K=2Arbitrarilypartitionobjectsintokgroups,Updatetheclustercentroids,Updatetheclustercentroids,Reassignobjects,Loopifneeded,Theinitialdataset,PartitionobjectsintoknonemptysubsetsRepeatComputecentroid(i.e.,meanpoint)foreachpartitionAssigneachobjecttotheclusterofitsnearestcentroidUntilnochange,不确定性决策理论与方法,1、不确定性决策概述2、关联规则发现3、聚类分析4、连接分析5、粗糙集分析6、决策树7、神经网络8、支持向量机,连接分析(Link-Analysis),事物之间是普遍联系的网站与网站之间网页与网页之间社交网络中的结点之间.需要回答的一个问题：这些连接点谁重要？,连接分析PageRank算法,Google采用的基本算法(LaryPage,拉里.佩奇，google创始人),节点代表页面,有向边代表超链接假设：冲浪者随机选择起始页面在以后的每一步，冲浪者以概率d直接进入目标页面或以1-d的概率通过其它指向目标页面的超链接进入目标页面。d的经验值约为0.85。一个页面的重要性取决于指向该页面的页面的重要性,连接分析PageRank算法,则页面p的重要性为：xp(k+1)=(1-d)/n+dq,pP,qp(xq(k)/Nq)P为站点的页面集，n为所有页面数，Nq为页面q的出度，xq(k)为页面q的重要性。这样就可以计算出所有页面的重要性。记X=xp|pP，D=1/n,1/n,1/n，M=mpq=1/Nq，Nq表示可直接链接到页面p的页面q的出度，则X(k+1)=(1-d)D+dMX(k),连接分析PageRank算法,连接分析PageRank算法,算例：,0,连接分析PageRank算法,不确定性决策理论与方法,1、不确定性决策概述2、关联规则发现3、聚类分析4、连接分析5、粗糙集分析6、决策树7、神经网络8、支持向量机,粗糙集：预备知识,论域：研究对象的全体成员构成的集合，一般用字母U表示；若XU，则称X是U的子集隶属度：描述一个对象x与某个子集X之间的隶属程度，一般用符号表示，若xX,则=1;若,则=0;其他：01(常用某个函数加以描述，称为隶属度函数),等价关系：R是U上的一个等价关系，当且仅当对于任意xU，均有xRx（自反性）对于任意x,yU，xRyyRx（对称性）对于任意x,y,zU，xRyyRzxRz（传递性）等价类：若R是U上的一个等价关系，对于任意xU，称集合x=y|yRx,yU为U关于R的一个等价类，记为xR。设X1,X2,Xn是U关于R的所有等价类，则有：XiXj=（ij，i,j=1,2,n）X1X2Xn=U划分：所有等价类的集合称为U关于R的商集，它构成了U的一个划分，记为U/R。概念：具有相同特征值的一群对象称为一个概念（一个等价类就是一个概念）,粗糙集：预备知识,piT1pjiffv(pi,T1)=v(pj,T1)，则T1是U上的一个等价关系（类似地可以定义T2,T3,E）X1=p1=p4=p6=p1,p4,p6为U关于T1的一个等价类X2=p2=p3=p5=p2,p3,p5为U关于T1的另一个等价类（T1有多少种取值就有多少个等价类）显然X1X2=;X1X2=U商集U/T1=X1,X2,粗糙集：预备知识,集合成员：明确的隶属关系模糊成员：概念模糊(如青年)导致成员模糊粗糙成员：概念清晰(如感冒)，成员模糊(是否感冒不清楚)，具有概率特征(隶属函数)，但不是概率问题，只是由于根据可用知识无法得到准确结论。,粗糙集：预备知识,粗糙集理论由Pawlak提出1982,1991。粗糙集理论反映了人们以不完全信息或知识去处理一些不可分辨现象的能力，或依据观察、度量到某些不精确的结果而进行分类数据的能力。PawlakZ.,Roughsets.InternationalJournalofComputerandInformationSciences,1982(11):341-356PawlakZ.,RoughsetTheoreticalAspectsofReasoningaboutData,Dordrecht,Boston,London:KluwerAcademicPublishers,1991,粗糙集：理论的提出,知识是主体对论域中的客体进行分类的能力，分类能力越强，主体所具备知识的可靠度越高分类能力受主体分辨能力的影响，因此分类具有近似性(粗糙集)影响分类能力的因素(在信息系统中常描述为属性)很多，不同的因素重要程度不同，其中某些因素起决定性作用(属性重要性：属性约简)具有相同属性的实体，属性取值的不同对分类能力也产生影响(值重要性：值约简)属性之间存在某种依赖关系(决策规则),粗糙集：基本思想,信息系统I可以定义为四元组，其中有限非空集合U是论域，A为关于U的属性集，Va表示属性a的值域，映射f:UAV表示对xU，aA，有：f(x,a)V。决策表：若属性集合A可进一步分为两个属性子集的并：条件属性集C和决策属性集D，A=CD，CD=，则信息系统也被称为决策表。,粗糙集：信息系统与知识,A的任何一个子集B确定一个U上的二元关系IND(B)：对于任意aB，xIND(B)ya(x)=a(y)；x,yU；a(x)表示对象x的a属性值。则称IND(B)为不可分辨关系。IND(B)是等价关系，IND(B)的所有等价类的集合记为U/B（称为知识B），含有元素x的等价类记为B(x)或xB，同一等价类中的元素是不可分辨的，称IND(B)等价类为初等集（范畴），它是知识库的基本结构单元即概念。设R是由属性集A的子集诱导的论域U上的等价关系族，则称R为U上的一个知识库，记为K=(U,R)。,粗糙集：信息系统与知识,对于U的任意子集X，若X恰能由知识R的若干个初等集的并构成，则称X为R-精确集，否则为R-粗糙集。每个粗糙集X都可用两个与之相关的精确集近似表示即X的上近似和下近似，他们是粗糙集理论的两个最基本运算。,粗糙集：粗糙集与近似,下近似由所有包含于X的初等集合的并构成，X的下近似中的元素一定属于X。上近似由与X的交为非空的初等集合的并构成，而上近似中的元素可能属于X。上近似与下近似的差为边界域，粗糙集的边界域为非空，否则为精确集。边界域中的元素根据可用知识没有确定的分类，即它既不能划分到X也不能划分到X的补集。正域与负域,粗糙集：粗糙集与近似,粗糙集：经典粗糙集模型,R1=T1：U/R1=p2,p3,p5，p1,p4,p6；R2=T2,T1：U/R2=p1,p4,p6,p2,p5,p3；R=T1,T2,T3：U/R=(p1,p3,p6,p2,p5,p4;F=E：U/F=p1,p2,p3,p6,p4,p5X1=p1,p2,p3,p6是R粗糙集，X1的R下近似是p1,p3,p6，R上近似是p1,p2,p3,p5,p6，边界域为p2,p5；X2=p4,p5也是R粗糙集，X2的R下近似是p4，X2的R上近似是p2,p4,p5，而边界域是p2,p5。,粗糙集：经典粗糙集模型,精度：X的R精度反映了我们对于了解集合X的知识的完全程度。R(X)=1为精确集，0R(X)1为粗糙集。粗糙度：X的R粗糙度反映了我们对于了解集合X的知识的不完全程度。(精度与概率或隶属度的区别),粗糙集：数字特征,知识R=T1,T2,T3：U/R=(p1,p3,p6,p2,p5,p4;分类F=E：U/F=p1,p2,p3,p6,p4,p5X1=p1,p2,p3,p6是R粗糙集，X1的R下近似是p1,p3,p6，R上近似是p1,p2,p3,p5,p6，R精度为0.6；R粗糙度为0.4；X2=p4,p5也是R粗糙集，X2的R下近似是p4，X2的R上近似是p2,p4,p5，R精度为0.333；R粗糙度为0.667。,粗糙集：数字特征,设F=X1，X2，Xn是论域U上的一个划分，那么根据知识R，F的分类精度如何？F的近似精度：分类的近似精度给出了根据现有知识对对象进行分类时可能正确的决策的百分数。F的近似质量：近似质量给出了能正确分类的百分数。这是一个非常重要的特征数字，它反映了两种分类F和R之间的关系。如果将R看作决策表中的条件属性集，F看成决策属性集，近似质量反映了两者之间的依赖关系。,粗糙集：数字特征,知识R=T1,T2,T3：U/R=(p1,p3,p6,p2,p5,p4;分类F=E：U/F=p1,p2,p3,p6,p4,p5X1=p1,p2,p3,p6是R粗糙集，X1的R下近似是p1,p3,p6，R上近似是p1,p2,p3,p5,p6；X2=p4,p5也是R粗糙集，X2的R下近似是p4，X2的R上近似是p2,p4,p5；F的近似精度为0.5；F的近似质量为0.667。,粗糙集：数字特征,为了寻找“IFTHEN”形式的推理规则，在粗糙集理论体系中所采用的方法是从一个给定的知识，推导另一个知识。如果知识D的所有初等范畴都能用知识C的某些初等范畴来定义，则称知识D可由知识C推得，也称D完全依赖于C，记为CD。设信息系统I=，A=CD，BC，则D的B正域定义为：D的B正域表示：利用知识B，能正确地划分到U/D各等价类中的所有对象的集合,粗糙集：知识依赖,设信息系统I=，D完全依赖于C当且仅当D等价于C当且仅当(CD)(DC)；D独立于C当且仅当(CD)(DC)。如果知识D的部分初等范畴能用知识C的某些初等范畴来定义，称知识D部分依赖于知识C。设信息系统I=，有：则称D是k(0k1)度依赖于C，记为CkD。,粗糙集：知识依赖,R1=T1：U/R1=p2,p3,p5，p1,p4,p6；R2=T2,T1：U/R2=p1,p4,p6,p2,p5,p3；R3=T1,T2,T3：U/R3=(p1,p3,p6,p2,p5,p4;F=E：U/F=p1,p2,p3,p6,p4,p5X1=p1,p2,p3,p6是R3粗糙集，X1的R3下近似是p1,p3,p6，R3上近似是p1,p2,p3,p5,p6；X2=p4,p5也是R3粗糙集，X2的R3下近似是p4，X2的R3上近似是p2,p4,p5。F的R3正域是p1,p3,p4,p6,所以F对R3的依赖度是2/3。,粗糙集：知识依赖,为什么要约简知识？判别：根据条件属性取值确定对象所属的类。实际：确定对象所属的类只需其中几个属性甚至一个属性，而不需要知道对象所有的属性，这与人类对实体的识别是一致的。表明：不同属性在分类时所起的作用是不同的。什么是知识约简？将知识库中某些不必要的等价关系（知识）移去的过程。设信息系统I=，BC，若C(D)=B(D)且B是D独立的，则B为C的D约简，记为REDD(C)。C的D约简是不含任何冗余知识且与C具有相同分类能力的子集（用知识C将对象划分到知识D的初等范畴中的能力）。,粗糙集：知识约简,在确定某个决策目标时，不同属性的重要性是不同的，在一般分析中常用事先假设的权重来描述。粗糙集理论并不使用事先假设的信息，而是根据各属性的分类能力不同，确定该属性的重要性。处理方法是将该属性从信息表中移去，分析其对分类能力的影响，影响越大，属性越重要。设信息系统I=，对于C的非空子集B，其重要度为若B的重要度为，则表示B可以从C中移去，也即B是冗余的。重要度可理解为移去B时所产生的分类误差。设信息系统I=，C中所有D不可省略的元素构成的集合称为C的D核，记作CoreD(C)。,粗糙集：属性重要性与属性核,基于属性依赖度的属性约简：设决策表T=，C,D分别为条件属性和决策属性，B是C的任一非空子集，对于经典粗糙集模型，D对B的依赖度为：则在B中增加某个属性pC-B所引起的k的变化大小为：p(D|B)=Bp(D)-B(D)p(D|B)越大，说明在已知属性B的条件下，p对决策D越重要。基于属性依赖度的属性约简算法就是将p(D|B)作为寻找最小属性约简的启发式信息。,粗糙集：知识约简算法,为什么要约简属性值？在判断某个对象属于某类时，某个属性的取值不同，对分类产生的影响也不相同。例如，判断人的体形(瘦、中、胖)时，体重是重要属性。但若体重属性值为60Kg时，此人的体形要结合其身高、性别才能确定，但若体重属性值为150Kg时，我们几乎肯定他是个胖子，这时身高、性别已不重要，也就是说身高、性别的属性值是冗余的。什么是值约简？值约简就是移去对分类没有实际价值的冗余的属性值。,粗糙集：值约简,IF(T1,No)AND(T3,Normal)THEN(E,Yes)IF(T1,Yes)AND(T3,Normal)THEN(E,Yes)IF(T3,High)THEN(E,Yes)IF(T3,Low)THEN(E,No)IF(T1,Yes)AND(T3,Normal)THEN(E,No)IF(T3,High)THEN(E,Yes),粗糙集：约简示例,IF(T2,Yes)AND(T3,Normal)THEN(E,Yes)IF(T2,No)AND(T3,Normal)THEN(E,Yes)IF(T3,High)THEN(E,Yes)IF(T3,Low)THEN(E,No)IF(T2,No)AND(T3,Normal)THEN(E,No)IF(T3,High)THEN(E,Yes),粗糙集：约简示例,不确定性决策理论与方法,1、不确定性决策概述2、关联规则发现3、聚类分析4、连接分析5、粗糙集分析6、决策树7、神经网络8、支持向量机,归纳学习：决策树,叶结点,决策树：概念,决策树学习是以实例为基础的归纳学习算法。所谓决策树是一个类似流程图的树结构，其中树的内结点对应属性或属性集，每个分枝表示检验结果(属性值)，树枝上的叶结点代表所关心的因变量的取值(类标签)，最顶端的结点称为根结点。决策树学习采用自顶向下的递归方式，在决策树的内部结点进行属性值比较并根据不同的属性值判断从该结点向下的分支，在叶结点得到结论。从根结点到每个叶结点都有唯一的一条路径，这条路径就是一条决策“规则”。当经过一批训练实例集的训练产生一颗决策树，那么该决策树就可以根据属性的取值对一个未知实例集进行分类。,决策树：CLS学习算法,概念学习系统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为根建立新的子树。,决策树：学习结果,决策树：ID3学习算法,ID3算法(Quinlan)：以信息熵的下降速度(信息增益)作为测试属性选择标准。信息增益：设决策树根结点的样本数据为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)。,决策树：ID3学习算法,以A为测试属性的期望信息熵为以A为根节点的信息增益是：Gain(A)=I(P,N)-E(A)ID3的策略就是选择信息增益最大的属性作为测试属性。ID3的问题：测试属性的分支越多，信息增益值越大，但输出分支多并不表示该测试属性有更好的预测效果。,决策树：C4.5学习算法,信息增益率：其中：目前一种比较流行的决策树算法C4.5算法就是以信息增益率作为测试属性的选择条件。生成的决策树往往过大，不利于决策时的应用，需要对其剪枝(Pruning)，请参阅相关文献。,决策树：算例,确定根结点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)=0.9056E(A1)=1-3/8log3=0.4084E(A2)=1-3/16log3=0.9056E(A3)=3-5/8log5-3/8log3=0.9544因此选A1作为起始根结点。A3没有改变任何信息量，无分类价值，可以删除。,决策树：算例,确定子树根结点I(P,N)=-6/8log6/8-2/8log2/8=0.8112E(A0)=E(A2)=1/2=0.5E(A3)=2-3/4log3=0.8112A0，A2具有相同的分类能力，任取一个均可。,决策树：算例,不确定性决策理论与方法,1、不确定性决策概述2、关联规则发现3、聚类分析4、连接分析5、粗糙集分析6、决策树7、神经网络8、支持向量机,神经网络,神经网络(ArtificialNeuralNetworks)是由具有适应性的简单单元组成的广泛并行互连的网络，它的组织能够模拟生物神经系统对真实世界物体所作出的交互反应(T.Koholen)。神经网络分为前向型、反馈型、随机型以及自组织型。我们重点介绍前向型网络及其学习算法。,基本神经元及感知机模型：,神经网络,wj1,wji,wjn,yj,f(iwijxi-j),x1,xi,xn,神经网络,神经元函数f的选择线性函数：f(x)=x带限的线性函数：为最大输出。阈值型函数：sigmoid函数：,神经网络,感知机学习算法：(选取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)，重复所有的训练样本直到所有的样本输出正确。,神经网络,多层前向神经网络：包括一个输入层、一个输出层以及多层隐单元。,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)。因此可得到yk=jwkjf(netj)。上述过程一直持续到所有的输出单元得到输出为止，最后一层的输出就是网络的输出。因此，神经网络是一个黑匣子。,神经网络,神经网络类型BP神经网络径向基函数(RBF)神经网络自组织映射(SOM)Hopfield网络波耳兹曼机（深度学习）Matlab提供了一套神经网络工具箱(NeuralNetworksToolbox)，其中包含了一组new函数，用以创建各种类型的神经网络。,神经网络,newcfcascade-forwardbackpropagationnetwork.newelmElmanbackpropagationnetwork.newfffeed-forwardbackpropagationnetwork.newfftdfeed-forwardinput-delaybackpropnetwork.newpnnprobabilisticneuralnetwork.newrbradialbasisnetwork.newrbeexactradialbasisnetwork.newsomself-organizingmapnewhopHopfieldrecurrentnetwork.newgrnngeneralizedregressionneuralnetwork.newlvqlearningvectorquantizationnetwork,神经网络,MatLab工具箱之多层前向BP网络示例P=012345678910;plot(P,T,P,Y,o),神经网络,不确定性决策理论与方法,1、不确定性决策概述2、关联规则发现3、聚类分析4、连接分析5、粗糙集分析6、决策树7、神经网络8、支持向量机,支持向量机,20世纪90年代Vapnik提出了支持向量机(SupportVectorMachines,SVM)，它被看作是高维空间函数表达的一般方法。使用SVM方法，人们可以在很高维的空间里构造好的分类规则。,支持向量机,经验风险最小化与结构风险最小化原则经验风险最小化原则考虑分类问题。样本集为U=x1,x2,.,xl(m维空间中的l个向量)，每个向量对应一个类别，类别空间Y=+1,-1。记p(x,y)表示对象x为y类的概率分布。分类的任务就是寻找分类器f：UY且使期望风险最小。f的期望风险为：在有限样本的情况下，p(x,y)是未知的，因此期望风险无法计算。常使用经验风险代替，且当l时两者相等。,支持向量机,如果成立，则称经验风险最小化原则（EmpiricalRiskMinimization,ERM）具有一致性。结构风险最小化原则Vapnik在1971年证明经验风险最小值未必收敛于期望风险最小值，即ERM不成立。因此提出了结构风险最小化原则(StructuralRiskMinimization,SRM)，为小样本统计理论奠定了基础。,支持向量机,Vapnik和Chervonenkis通过研究，得出了期望风险和经验风险的如下关系以概率1-成立，即l为样本点数目；参数01；h为函数f的维数，简称VC维。(在无法求得期望风险的情形下找到了它的一个上界)不等式右边与样本的具体分布无关，即Vapnik的统计学习理论无需假设样本分布，克服了高维分布对样本点需求随维数而指数增长的问题。这是小样本统计理论与经典统计理论的本质区别，也是将Vapnik统计方法称之为小样本统计理论的原因。,VC维置信度,支持向量机,讨论：(1)如果l/h较大，则期望风险(实际风险)主要由经验风险来决定，因此对于大样本集经验风险经常能给出较好结果。(2)如果比值l/h较小(小样本集)，则小的经验风险并不能保证有小的期望风险值，必须同时考虑经验风险和置信范围(称之为VC维置信度)。VC维在其中起重要作用，实际上置信范围是h的增函数。在样本点数目l一定时，分类器越复杂，即VC维越大，则置信范围越大，导致实际风险与经验风险的差别越大。结论：要想使实际风险最小不仅要使经验风险最小，还同时需要使分类器函数f的VC维h尽可能最小，这就是结构风险最小化原则。因此寻找最小属性集变得非常有意义。,支持向量机,支持向量分类模型基本分类思想：支持向量机的核心思想是将结构风险最小化原则引入到分类问题中。从线性可分情况下的最优分类超平面发展而来的，其本质是在训练样本中找出具有最优分类超平面的支持向量。在数学上归结为一个求解不等式约束条件的二次规划问题。,支持向量机,margin与支持向量：设样本集为U=x1,x2,.,xl(m维空间中的l个向量)，类别空间Y=+1,-1。xi为输入向量，对应的类标签为yi(+1或-1)。若样本集是线性可分的，则存在超平面H：wx+b=0使得(1)当wxi+b1时，yi=+1(2)当wxi