不确定性决策理论与方法概述课件1.ppt

1、不不确确定定性性决决不不确确定定生生的的概概率，率，甚甚至至对对未未来来状状态态都都难难以以把把握握的的决决策策问问题。题。v特特点点：状状态态的的不不确确定定性。性。不不确确定定性性：不不确确定定性性来来自自人人类类的的主主观观认认识识与与客客观观实实际际之之间间存存在在的的差差异。异。事事物物发发生生的的随随机机性、性、人人类类知知识识的的不不完完全、全、不不可可靠、靠、不不精精确确和和不不一一致致以以及及自自然然语语言言中中存存在在的的模模糊糊性性和和歧歧义义性，性，都都反反映映了了这这种种差差异，异，都都会会带带来来不不确确定定性。性。不不确确定定性性就就造造成成了了具具有有相相同同描

2、描述述信信息息的的对对象象可可能能属属于于不不同同概概念。念。v解解决决问问题题的的主主要要理理论论方方法法：人人工工智智能能与与不不确确定定性性理理论论不不确确定定性性叶叶斯斯决决策策准准则则就就难难以以凑凑效。效。下下面面介介绍绍几几种种常常用用的的不不确确定定性性决决策策准准则。则。v悲悲观观准准则则或或极极小小化化极极大大准准则则【Wald,1950】考考察察采采取取行行动动ai，i=1,2,m时时可可能能出出现现的的最最坏坏后后果，果，即即最最大大损损失失si或或最最小小效效用用ui；选选择择行行动动ak，使使得得sk(uk)在在所所有有行行动动中中最最小小(最最大大)。v乐乐观观准

3、准则则考考察察采采取取行行动动ai，i=1,2,m时时可可能能出出现现的的最最好好后后果，果，即即最最小小损损失失oi或或最最大大效效用用vi；选选择择行行动动ak，使使得得ok(vk)在在所所有有行行动动中中最最小小(最最大大)。不不确确定定性性1951】考考察察采采取取行行动动ai，i=1,2,m时时可可能能出出现现的的最最坏坏后后果果和和最最好好后后果，果，即即最最大大损损失失si和和最最小小损损失失oi或或最最小小效效用用ui和和最最大大效效用用vi；设设决决策策人人的的乐乐观观系系数数为为，则则选选择择行行动动ak，使使得得(1-)sk+ok(1-)uk+vk)在在所所有有行行动动中

4、中最最小小(最最大大)。不不确确定定性性age,1951】在在状状态态j下下考考察察采采取取行行动动ai的的损损失失lji或或效效用用uji和，和，并并将将其其与与在在此此状状态态下下采采取取不不同同行行动动时时的的最最小小损损失失sj或或最最大大效效用用uj进进行行比比较，较，其其差差值值的的大大小小定定义义为为后后悔悔值值rji，从从而而形形成成一一个个后后悔悔值值表；表；针针对对后后悔悔值值表，表，应应用用悲悲观观准准则则求求解：解：找找出出不不同同状状态态下下采采取取行行动动ai的的最最大大后后悔悔值值pi，然然后后再再使使所所有有行行动动的的最最大大后后悔悔值值极极小，小，其其所所对

5、对应应的的行行动动记记为为决决策策结结果。果。不不确确定定性性825】Laplace认认为，为，对对真真实实的的自自然然状状态态一一无无所所知知等等价价于于所所有有自自然然状状态态具具有有相相同同的的概概率。率。然然后后借借助助于于贝贝叶叶斯斯准准则则进进行行决决策。策。不不确确定定性性lnor,1954】不不确确定定性性lnor,1954】不不确确定定性性智智能能决决策策理理论论与与环环境境：决决策策问问题题所所涉涉及及的的变变量量规规模模越越来来越越大；大；决决策策所所依依赖赖的的信信息息具具有有不不完完备备性、性、模模糊糊性、性、不不确确定定性性等等特特点，点，使使得得决决策策问问题题难

6、难以以准准确确地地量量化化表表示；示；某某些些决决策策问问题题及及其其目目标标可可能能是是模模糊糊的、的、不不确确定定的，的，使使得得决决策策者者对对自自己己的的偏偏好好难难以以明明确，确，随随着着决决策策分分析析的的深深入，入，对对决决策策问问题题的的认认知知加加深，深，自自己己原原有有的的偏偏好好/倾倾向向得得到到不不断断地地修修正，正，使使得得决决策策过过程程出出现现不不断断调调整整的的情情况。况。v这这时，时，传传统统的的决决策策数数学学模模型型已已经经难难以以胜胜任任求求解解复复杂杂度度过过高高的的决决策策问问题、题、含含有有不不确确定定性性的的决决策策问问题题以以及及半半结结构构化

7、、化、非非结结构构化化的的决决策策问问题，题，因因而而产产生生了了智智能能决决策策理理论、论、方方法法及及技技术。术。智智能能决决策策理理论论与与方方ificial Intelligence,AI)相相关关理理论论方方法，法，融融合合传传统统的的决决策策数数学学模模型型和和方方法法而而产产生生的的具具有有智智能能化化推推理理和和求求解解的的决决策策方方法，法，其其典典型型特特征征是是能能够够在在不不确确定、定、不不完完备、备、模模糊糊的的信信息息环环境境下，下，通通过过应应用用符符号号推推理、理、定定性性推推理理等等方方法，法，对对复复杂杂决决策策问问题题进进行行建建模、模、推推理理和和求求解

8、。解。AI应应用用于于决决策策科科学学主主要要有有两两种种模模式式：针针对对可可建建立立精精确确数数学学模模型型的的决决策策问问题，题，由由于于问问题题的的复复杂杂性，性，如如组组合合爆爆炸、炸、参参数数过过多多等等而而无无法法获获得得问问题题的的解解析析解，解，需需要要借借助助AI中中的的智智能能搜搜索索算算法法获获得得问问题题的的数数值值解；解；针针对对无无法法建建立立精精确确数数学学模模型型的的不不确确定定性性决决策策问问题、题、半半结结构构化化或或非非结结构构化化决决策策问问题，题，需需要要借借助助AI方方法法建建立立相相应应的的决决策策模模型型并并获获得得问问题题的的近近似似解。解。

9、知知识识发发决决策策的的信信息息和和知知识。识。知知识识发发知知识识发发知知识识发发Data Mining w知知识识发发现现问问题：题：如如何何从从数数据据中中将将知知识识挖挖掘掘出出来？来？面面临临许许多多技技术术问问题：题：如如数数据据异异构构问问题题、数数据据具具有有噪噪音音且且信信息息不不完完整、整、使使用用什什么么样样的的挖挖掘掘算算法、法、知知识识如如何何表表示示等等知知识识评评价价问问题：题：数数据据本本身身具具有有权权威威性、性、客客观观性，性，但但知知识识不不具具备。备。知知识识如如何何评评价？价？参参考考KDD e Discovery in Databases,KDD)是

10、是指指从从大大量量数数据据中中提提取取有有用用的的(useful)、新新颖颖的的(novel)、有有效效的的(valid)并并最最终终能能被被人人理理解解(understandable)的的模模式式(patterns)的的处处理理过过程程(process)。v数数据据挖挖掘掘(Data Mining，DM)是是KDD的的核核心心阶阶段段,通通过过实实施施相相关关算算法法获获得得期期望望的的模模式。式。KDKDKDKDKDKDKDented(the system verifies the users hypothesis):including the most common methods of

11、 traditional statistics,like goodness of fit(拟拟合合优优度度)test,tests of hypotheses(假假设设检检验验，e.g.,t-test of means),and analysis of variance(ANOVA，方方差差分分析析或或F-检检验验).vDiscovery-oriented(the system finds new rules and patterns autonomously):prediction methods VS description methods；supervised learning（有有导导师

12、师学学习习）VS unsupervised learningxj,.,xN。xj=xj1,.,xji,.,xjdT Rd，xji表表示示对对象象xj对对应应的的第第i个个特特征征(维维度、度、属属性、性、变变量量)的的值。值。输输出：出：Y=C1,.,Ck,.,CK。Ck表表示示类类标标签。签。模模型：型：Y=f(X,W)或或P(Y|X)=f(X,W)，将将输输入入X映映射射成成类类标标签签Y或或Y的的概概率率分分布。布。W是是可可调调整整的的参参数数向向量。量。模模型型训训练：练：使使用用归归纳纳学学习习方方法法(经经验验风风险险最最小小化化)确确定定模模型型的的结结构构f和和参参数数W，训

13、训练练样样本本集集为为(xi,yi)。：应应用用于于无无标标签签数数据据的的分分类，类，称称为为聚聚类类分分析析或或探探究究性性分分析，析，其其目目标标是是将将无无标标签签数数据据分分类类到到有有限、限、离离散散的的“自自然然状状态态”。“自自然然状状态态”隐隐藏藏了了数数据据的的结结构，构，而而不不是是为为未未观观测测的的样样本本提提供供一一个个精精确确刻刻画画(描描述述而而非非预预测测)。无无监监督督预预测测学学习习(如如关关联联规规则则发发现、现、链链接接分分析析等等)：具具有有预预测测能能力力的的无无监监督督学学习。习。不不确确定定性性决决关关联联规规ion Rules)：关关联联规规

14、则则的的形形式式为为AB，A为为前前件，件，B为为后后件。件。(Day=Friday)and(Product=Diaper)(Product=Beer)为为一一典典型型关关联联规规则则A为为满满足足前前件件的的对对象象集，集，B为为满满足足后后件件的的对对象，象，N为为全全部部对对象象集。集。典典型型方方法：法：Apriori算算法。法。NBASupport|ABAConfidence2022-8-9决策理论与方法-智能决策理论与方法关关联联规规则则发发现现(Awal&Srikant在在1994年年提提出出v主主要要思思想想:一一个个频频繁繁项项集集（支支持持度度超超过过给给定定值值的的项项集

15、）集）的的子子集集一一定定是是频频繁繁的的v例如，若beer,diaper,nuts是频繁的,那么beer,diaper 一定是频繁的.任任一一项项是是非非频频繁繁的，的，则则包包含含该该项项的的超超集集一一定定是是不不频频繁繁的。的。v例如，若beer,diaper是不频繁的,那么beer,diaper,nuts一定是不频繁的.关关联联规规则则发发现现(Afrequent itemsets:the sets of items that have minimum support(Apriori)uA subset of a frequent itemset must also be a fre

16、quent itemset,i.e.,if A B isa frequent itemset,both A and B should be a frequent itemsetuIteratively find frequent itemsets with cardinality from 1 to k(k-itemset)Use the frequent itemsets to generate association rules.关关联联规规则则发发现现(ATID Items100 1 3 4200 2 3 5300 1 2 3 5400 2 5itemset sup.1223334153

17、itemset sup.12233353itemset1 21 31 52 32 53 5itemset sup1 211 321 512 322 533 52itemset sup1 322 322 533 52itemset2 3 5itemset sup2 3 52不不确确定定性性决决聚聚类类算算法法将将数数据据分分割割成成若若干干个个簇，簇，被被大大多多数数人人接接受受的的定定义义是：是：簇簇内内的的相相似似性性尽尽可可能能大大(簇簇内内同同质质性性)，簇簇间间的的相相似似性性尽尽可可能能小小(簇簇间间异异质质性性)。聚聚类类是是一一个个主主观观过过程，程，其其相相似似性性度度量量都都

18、是是根根据据发发现现感感兴兴趣趣的的“簇簇”的的能能力力主主观观选选择择的，的，不不存存在在一一个个绝绝对对的的准准则则适适用用所所有有情情境。境。输输入：入：X=x1,.,xj,.,xN。xj=xj1,.,xji,.,xjdT Rd，xji表表示示对对象象xj对对应应的的第第i个个特特征征(维维度、度、属属性、性、变变量量)的的值。值。聚聚类类)：试试图图将将X分分割割成成K个个簇簇C=C1,.,Ck,.,CK(KN)。满满足足Ci ，i 1,.,k；i 1,.,kCi=X；CiCj=，i,j1,.,k,ij。层层次次聚聚类类：试试图图构构造造一一个个X的的树树状状嵌嵌套套结结构构H=H1,

19、.,HQ(Ql，则则要要么么Ci Cj，要要么么CiCj=。(解解释：释：如如果果两两个个簇簇不不在在同同一一层，层，那那么，么，这这两两个个簇簇要要么么是是包包含含关关系，系，要要么么不不相相交交)2022-8-9决策理论与方法-智能决策理论与方法聚聚n容容的的聚聚类类)：试试图图将将X分分割割成成K个个簇簇C=C1,.,Ck,.,CK(KN)。满满足足Ci ，i 1,.,k；i 1,.,kCi=X；对对象象xj属属于于Ci簇簇的的隶隶属属度度为为ui,j，ui,j满满足：足：,11,1;,KNji jii jijxuCuN聚聚类：类：相相都都是是由由一一些些特特征征来来描描述述的，的，常常

20、表表示示为为多多维维向向量。量。特特征征类类型型包包括括定定量量与与定定性、性、连连续续与与离离散、散、名名词词与与序序数数等。等。特特征征类类型型决决定定着着相相似似性性测测度度机机制。制。聚聚类：类：相相数数型型)特特征征Minkowski(闵闵氏氏)距距离：离：值值较较大大和和波波动动较较大大的的特特征征主主导导着着相相似似性。性。n=1时，时，称称为为绝绝对对距距离离(超超矩矩形形聚聚类类)。n=2时，时，称称为为欧欧几几里里德德距距离离(超超球球面面聚聚类类)。n时，时，称称为为上上确确界界距距离，离，Dij=max|xil-xjl|,l=1.d。1/1|ndnijiljllDxxx

21、ixj聚聚类：类：相相n数数型型)特特征征余余弦弦相相似似性：性：Mahalanobis(马马氏氏)距距离：离：S为为协协方方差差矩矩阵，阵，当当各各个个特特征征是是线线性性无无关关的的时时候，候，Dij就就是是欧欧氏氏距距离。离。计计算算量量较较大。大。cos|Tijijijx xSxxxixjO 1()()TijijijDxxSxx聚聚类：类：相相数数型型)特特征征Pearson相相关关系系数：数：Dij=1-rij(不不能能度度量量两两个个对对象象的的差差异异幅幅度度)，例例如：如：x1=(1,1,1);x2=(2,2,2)x3=(1,1,2);x4=(2,2,3)点点对对称称距距离离(

22、不不能能度度量量两两个个对对象象的的差差异异幅幅度度)：12211()()()()dilijljlijddilijljllxxxxrxxxx1,.,|()()|min|()|()|irjrirjNirjrj ixxxxDxxxxxixjxr聚聚类：类：相相征征取取值值仅仅为为0,1)设设每每个个对对象象都都可可用用d个个特特征征表表示，示，如如果果对对象象有有此此特特征征则则标标记记为为1，否否则则标标记记为为0。对对于于任任意意两两个个对对象象xi,xj，n11、n00、n10、n01分分别别表表示示两两者者都都有、有、两两者者都都无、无、xi有有xj无、无、xi无无xj有有的的特特征征数，

23、数，则：则：或或根根据据不不同同的的情情境，境，w可可以以取取1(Jaccard),2(Sokal),1/2(Gower)。110011001001()ijnnSnnw nn11111001()ijnSnw nn聚聚类：类：相相征征名名词词性性特特征征是是指指取取值值超超过过2个个状状态态的的离离散散型型特特征，征，如如性性别、别、颜颜色色等。等。相相似似性性一一般般采采用用特特征征值值匹匹配配的的办办法法衡衡量。量。11dijijllSSd0,1ijlijSij与 不匹配，与 匹配聚聚类：类：相相n们们遇遇到到的的大大多多数数数数据据对对象象所所包包含含的的特特征征可可能能各各种种类类型型都

24、都有，有，这这时时怎怎么么办？办？将将所所有有特特征征映映射射到到0,1实实数数域；域；将将所所有有特特征征都都映映射射成成二二元元特特征；征；通通用用测测度：度：Sijl表表示示第第l个个特特征征的的相相似似度，度，ijl表表示示是是否否使使用用该该特特征征参参与与测测度。度。11()/()ddijijlijlijlllSS聚聚类：类：相相n于于N个个输输入入数数据据对对象，象，两两两两之之间间的的相相似似性性可可以以表表示示成成一一个个NN阶阶对对称称矩矩阵，阵，称称为为邻邻近近矩矩阵。阵。111111jNiijiNNNjNNSSSSSSSSSS聚聚类：类：主主nnn ns sn概概率率混

25、混合合模模型型n图图模模型型与与谱谱聚聚类类n组组合合搜搜索索技技术术n模模糊糊聚聚类类n基基于于神神经经网网络络n基基于于核核的的方方法法K-meansK-means算法：基于几何中心算法：基于几何中心kixGcardxmilGxlmimi,2,1,)(1)()()1(K-meansK-means算法示例算法示例不不确确定定性性决决连连接接分分析析(Link与与网网站站之之间间网网页页与与网网页页之之间间社社交交网网络络中中的的结结点点之之间间.v需需要要回回答答的的一一个个问问题：题：这这些些连连接接点点谁谁重重要？要？连连接接分分析析 Pa法法(Lary Page,拉拉里里.佩佩奇，奇，

26、google创创始始人人),节节点点代代表表页页面面,有有向向边边代代表表超超链链接接v假假设：设：冲冲浪浪者者随随机机选选择择起起始始页页面面在在以以后后的的每每一一步，步，冲冲浪浪者者以以概概率率d直直接接进进入入目目标标页页面面或或以以1-d的的概概率率通通过过其其它它指指向向目目标标页页面面的的超超链链接接进进入入目目标标页页面。面。d的的经经验验值值约约为为0.85。一一个个页页面面的的重重要要性性取取决决于于指指向向该该页页面面的的页页面面的的重重要要性性随机选择的起始页面随机选择的起始页面d=0.85连连接接分分析析 Pa+1)=(1-d)/n+d q,p P,qp(xq(k)/

27、Nq)vP为为站站点点的的页页面面集，集，n为为所所有有页页面面数，数，Nq为为页页面面q的的出出度，度，xq(k)为为页页面面q的的重重要要性。性。v这这样样就就可可以以计计算算出出所所有有页页面面的的重重要要性。性。记记X=xp|p P，D=1/n,1/n,1/n，M=mpq=1/Nq，Nq表表示示可可直直接接链链接接到到页页面面p的的页页面面q的的出出度，度，则则X(k+1)=(1-d)D+dMX(k)随机选择的起始页面随机选择的起始页面qd=0.85连连接接分分析析 Pa连连接接分分析析 Pa0连连接接分分析析 Pa不不确确定定性性决决Xx对对于于任任意意x U，均均有有x R x（自

28、自反反性性）对对于于任任意意x,y U，x R yy R x（对对称称性性）对对于于任任意意x,y,z U，x R y y R zx R z（传传递递性性）v等等价价类类：若若R是是U上上的的一一个个等等价价关关系，系，对对于于任任意意x U，称称集集合合x=y|y R x,y U为为U关关于于R的的一一个个等等价价类，类，记记为为xR。设设X1,X2,Xn是是U关关于于R的的所所有有等等价价类，类，则则有：有：XiXj=（ij，i,j=1,2,n）X1X2Xn=Uv划划分分：所所有有等等价价类类的的集集合合称称为为U关关于于R的的商商集，集，它它构构成成了了U的的一一个个划划分，分，记记为为

29、U/R。v概概念念：具具有有相相同同特特征征值值的的一一群群对对象象称称为为一一个个概概念念（一一个个等等价价类类就就是是一一个个概概念）念）成成员员：概概念念模模糊糊(如如青青年年)导导致致成成员员模模糊糊v粗粗糙糙成成员员：概概念念清清晰晰(如如感感冒冒)，成成员员模模糊糊(是是否否感感冒冒不不清清楚楚)，具具有有概概率率特特征征(隶隶属属函函数数)，但但不不是是概概率率问问题，题，只只是是由由于于根根据据可可用用知知识识无无法法得得到到准准确确结结论。论。aAaVV 的的二二元元关关系系IND(B)：对对于于任任意意a B，xIND(B)ya(x)=a(y)；x,y U；a(x)表表示示

30、对对象象x的的a属属性性值。值。则则称称IND(B)为为不不可可分分辨辨关关系系。vIND(B)是是等等价价关关系，系，IND(B)的的所所有有等等价价类类的的集集合合记记为为U/B（称称为为知知识识B），含含有有元元素素x的的等等价价类类记记为为B(x)或或xB，同同一一等等价价类类中中的的元元素素是是不不可可分分辨辨的，的，称称IND(B)等等价价类类为为初初等等集集（范范畴）畴），它它是是知知识识库库的的基基本本结结构构单单元元即即概概念念。v设设R是是由由属属性性集集A的的子子集集诱诱导导的的论论域域U上上的的等等价价关关系系族，族，则则称称R为为U上上的的一一个个知知识识库库，记记为

31、为K=(U,R)。YXxUxXRXYRUYR)()/(:YXxUxXRXYRUYR)()/(:XRXPOSR)(XRUXNegR)(粗糙集X粗糙集X)()()()(XXRCardXRCardXR)(1)(XXRRCardUXRCardFniiR1)(niiniiRXRCardXRCardF11)(理理规规则，则，在在粗粗糙糙集集理理论论体体系系中中所所采采用用的的方方法法是是从从一一个个给给定定的的知知识，识，推推导导另另一一个个知知识。识。如如果果知知识识D的的所所有有初初等等范范畴畴都都能能用用知知识识C的的某某些些初初等等范范畴畴来来定定义，义，则则称称知知识识D可可由由知知识识C推推得

32、，得，也也称称D完完全全依依赖赖于于C，记记为为CD。v设设信信息息系系统统I=，A=CD，B C，则则D的的B正正域域定定义义为：为：vD的的B正正域域表表示：示：利利用用知知识识B，能能正正确确地地划划分分到到U/D各各等等价价类类中中的的所所有有对对象象的的集集合合XBDPOSDUXB/)(，D完完全全依依赖赖于于C当当且且仅仅当当D等等价价于于C当当且且仅仅当当(CD)(DC)；D独独立立于于C当当且且仅仅当当(CD)(DC)。v如如果果知知识识D的的部部分分初初等等范范畴畴能能用用知知识识C的的某某些些初初等等范范畴畴来来定定义，义，称称知知识识D部部分分依依赖赖于于知知识识C。v设

33、设信信息息系系统统I=，有：有：则则称称D是是k(0 k 1)度度依依赖赖于于C，记记为为CkD。DUCU/)()()(UCardDPOSCardDkCC性性是是不不同同的，的，在在一一般般分分析析中中常常用用事事先先假假设设的的权权重重来来描描述。述。粗粗糙糙集集理理论论并并不不使使用用事事先先假假设设的的信信息息，而而是是根根据据各各属属性性的的分分类类能能力力不不同，同，确确定定该该属属性性的的重重要要性。性。处处理理方方法法是是将将该该属属性性从从信信息息表表中中移移去，去，分分析析其其对对分分类类能能力力的的影影响，响，影影响响越越大，大，属属性性越越重重要。要。v设设信信息息系系统

34、统I=，对对于于C的的非非空空子子集集B，其其重重要要度度为为v若若B的的重重要要度度为为，则则表表示示B可可以以从从C中中移移去，去，也也即即B是是冗冗余余的。的。重重要要度度可可理理解解为为移移去去B时时所所产产生生的的分分类类误误差。差。v设设信信息息系系统统I=，C中中所所有有D不不可可省省略略的的元元素素构构成成的的集集合合称称为为C的的D核，核，记记作作CoreD(C)。)()(1)()()()(),(DDDDDBCBCCBCCDC策策表表T=，C,D分分别别为为条条件件属属性性和和决决策策属属性，性，B是是C的的任任一一非非空空子子集，集，对对于于经经典典粗粗糙糙集集模模型，型，

35、D对对B的的依依赖赖度度为：为：v则则在在B中中增增加加某某个个属属性性p C-B所所引引起起的的k的的变变化化大大小小为：为：p(D|B)=Bp(D)-B(D)vp(D|B)越越大，大，说说明明在在已已知知属属性性B的的条条件件下，下，p对对决决策策D越越重重要。要。基基于于属属性性依依赖赖度度的的属属性性约约简简算算法法就就是是将将p(D|B)作作为为寻寻找找最最小小属属性性约约简简的的启启发发式式信信息。息。/()()()X U DBCardB XkDCard U对对象象属属于于某某类类时，时，某某个个属属性性的的取取值值不不同，同，对对分分类类产产生生的的影影响响也也不不相相同。同。例

36、例如，如，判判断断人人的的体体形形(瘦、瘦、中、中、胖胖)时，时，体体重重是是重重要要属属性。性。但但若若体体重重属属性性值值为为60Kg时，时，此此人人的的体体形形要要结结合合其其身身高、高、性性别别才才能能确确定，定，但但若若体体重重属属性性值值为为150Kg时，时，我我们们几几乎乎肯肯定定他他是是个个胖胖子，子，这这时时身身高、高、性性别别已已不不重重要，要，也也就就是是说说身身高、高、性性别别的的属属性性值值是是冗冗余余的。的。v什什么么是是值值约约简？简？值值约约简简就就是是移移去去对对分分类类没没有有实实际际价价值值的的冗冗余余的的属属性性值。值。)()(1)()()()(),(D

37、DDDDBCBCCBCCDC不不确确定定性性决决归归纳纳学学叶结点叶结点决决策策学学习习算算法。法。所所谓谓决决策策树树是是一一个个类类似似流流程程图图的的树树结结构，构，其其中中树树的的内内结结点点对对应应属属性性或或属属性性集，集，每每个个分分枝枝表表示示检检验验结结果果(属属性性值值)，树树枝枝上上的的叶叶结结点点代代表表所所关关心心的的因因变变量量的的取取值值(类类标标签签)，最最顶顶端端的的结结点点称称为为根根结结点。点。v决决策策树树学学习习采采用用自自顶顶向向下下的的递递归归方方式，式，在在决决策策树树的的内内部部结结点点进进行行属属性性值值比比较较并并根根据据不不同同的的属属性

38、性值值判判断断从从该该结结点点向向下下的的分分支，支，在在叶叶结结点点得得到到结结论。论。从从根根结结点点到到每每个个叶叶结结点点都都有有唯唯一一的的一一条条路路径，径，这这条条路路径径就就是是一一条条决决策策“规规则则”。v当当经经过过一一批批训训练练实实例例集集的的训训练练产产生生一一颗颗决决策策树，树，那那么么该该决决策策树树就就可可以以根根据据属属性性的的取取值值对对一一个个未未知知实实例例集集进进行行分分类。类。决决策策树：树：CL颗颗空空的的决决策策树树出出发，发，添添加加新新的的判判定定结结点点来来改改善善原原来来的的决决策策树，树，直直到到该该决决策策树树能能够够正正确确地地将

39、将训训练练实实例例分分类类为为止。止。产产生生根根节节点点T，T包包含含所所有有的的训训练练样样本；本；如如果果T中中的的所所有有样样本本都都是是正正例，例，则则产产生生一一个个标标有有“1”的的节节点点作作为为T的的子子节节点，点，并并结结束；束；如如果果T中中的的所所有有样样本本都都是是反反例，例，则则产产生生一一个个标标有有“-1”的的节节点点作作为为T的的子子节节点，点，并并结结束；束；选选择择一一个个属属性性A(如如何何选选?)，根根据据该该属属性性的的不不同同取取值值v1,v2,vn将将T中中的的训训练练集集划划分分为为n个个子子集，集，并并根根据据这这n个个子子集集建建立立T的的

40、n个个子子节节点点T1,T2,Tn，并并分分别别以以A=vi作作为为从从T到到Ti的的分分支支符符号；号；以以每每个个子子节节点点Ti为为根根建建立立新新的的子子树。树。决决策策树：树：决决策策树：树：ID熵熵的的下下降降速速度度(信信息息增增益益)作作为为测测试试属属性性选选择择标标准。准。v信信息息增增益益：设设决决策策树树根根结结点点的的样样本本数数据据为为X=x1,x2,xn，称称X的的两两个个训训练练子子集集PX(对对应应类类标标签签为为1)和和NX(对对应应类类标标签签为为-1)为为正正例例集集和和反反例例集集，并并记记正正例例集集和和反反例例集集的的样样本本数数分分别别为为P和和

41、N，则则样样本本空空间间的的信信息息熵熵为为假假设设以以随随机机变变量量A作作为为决决策策树树根根的的测测试试属属性，性，A具具有有k个个不不同同的的离离散散值值v1,v2,vk，它它将将X划划分分为为k个个子子集，集，且且假假设设第第j个个子子集集中中包包含含Pj个个正正例，例，Nj个个反反例，例，则则第第j个个子子集集的的信信息息熵熵为为I(Pj,Nj)。)log()log(),(NPNNPNNPPNPPNPI决决策策树：树：ID以以A为为根根节节点点的的信信息息增增益益是：是：Gain(A)=I(P,N)-E(A)vID3的的策策略略就就是是选选择择信信息息增增益益最最大大的的属属性性作

42、作为为测测试试属属性。性。vID3的的问问题：题：测测试试属属性性的的分分支支越越多，多，信信息息增增益益值值越越大，大，但但输输出出分分支支多多并并不不表表示示该该测测试试属属性性有有更更好好的的预预测测效效果。果。kjjjjjNPINPNPAE1),()(决决策策树：树：C4.种种比比较较流流行行的的决决策策树树算算法法C4.5算算法法就就是是以以信信息息增增益益率率作作为为测测试试属属性性的的选选择择条条件。件。v生生成成的的决决策策树树往往往往过过大，大，不不利利于于决决策策时时的的应应用，用，需需要要对对其其剪剪枝枝(Pruning)，请请参参阅阅相相关关文文献。献。)()()(AS

43、plitiAGainAgainratiokjjjjjnNPnNPASpliti1)log()(决决策策决决策策决决策策不不确确定定性性决决神神经经cial Neural Networks)是是由由具具有有适适应应性性的的简简单单单单元元组组成成的的广广泛泛并并行行互互连连的的网网络，络，它它的的组组织织能能够够模模拟拟生生物物神神经经系系统统对对真真实实世世界界物物体体所所作作出出的的交交互互反反应应(T.Koholen)。v神神经经网网络络分分为为前前向向型、型、反反馈馈型、型、随随机机型型以以及及自自组组织织型型。我我们们重重点点介介绍绍前前向向型型网网络络及及其其学学习习算算法。法。神神

44、经经神神经经f(x)=x带带限限的的线线性性函函数：数：为为最最大大输输出。出。阈阈值值型型函函数：数：sigmoid函函数：数：xxxxxf|)(xxxf11)(xxxeexforexf11)(11)(神神经经神神经经层、层、一一个个输输出出层层以以及及多多层层隐隐单单元。元。神神经经含含层层第第j个个神神经经元元为为例例)：接接受：受：第第j个个神神经经元元的的值值来来自自于于前前一一层层网网络络(本本例例是是输输入入层层)输输出出值值的的加加权权和，和，即即netj=iwjiui。投投射：射：将将第第j个个神神经经元元的的值值经经过过变变换换f(netj)，作作为为下下一一层层网网络络(

45、本本例例是是输输出出层层)的的输输入，入，一一般般f(x)=1/(1+e-x)。因因此此可可得得到到yk=jwkjf(netj)。上上述述过过程程一一直直持持续续到到所所有有的的输输出出单单元元得得到到输输出出为为止，止，最最后后一一层层的的输输出出就就是是网网络络的的输输出。出。v因因此，此，神神经经网网络络是是一一个个黑黑匣匣子子。神神经经函函数数(RBF)神神经经网网络络l自自组组织织映映射射(SOM)lHopfield网网络络l波波耳耳兹兹曼曼机机（深深度度学学习）习）vMatlab提提供供了了一一套套神神经经网网络络工工具具箱箱(Neural Networks Toolbox)，其其

46、中中包包含含了了一一组组new函函数，数，用用以以创创建建各各种种类类型型的的神神经经网网络。络。神神经经rward backpropagation network.vnewelmElman backpropagation network.vnewfffeed-forward backpropagation network.vnewfftdfeed-forward input-delay backprop network.vnewpnnprobabilistic neural network.vnewrbradial basis network.vnewrbeexact radial basi

47、s network.vnewsomself-organizing mapvnewhopHopfield recurrent network.vnewgrnngeneralized regression neural network.vnewlvqlearning vector quantization network神神经经示示例例P=0 1 2 3 4 5 6 7 8 9 10;&输输入入T=0 1 2 3 4 3 2 1 2 3 4;&期期望望输输出出net=newcf(0 10,5 1,tansig purelin);&创创建建一一个个BP网网络，络，最最小小输输入入为为0，最最大大输输

48、入入为为10，两两隐隐含含层，层，第第一一（5个个神神经经元）元）、二二层层（1个个神神经经元）元）神神经经元元函函数数分分别别为为tansig和和purelin函函数。数。Y=sim(net,P);plot(P,T,P,Y,o)net.trainParam.epochs=50;net=train(net,P,T);Y=sim(net,P);plot(P,T,P,Y,o)神神经经012345678910-0.500.511.522.533.54012345678910-0.500.511.522.533.540510152025303540455010-310-210-110010110250

49、 EpochsTraining-BluePerformance is 0.00225488,Goal is 0不不确确定定性性决决支支持持k提提出出了了支支持持向向量量机机(Support Vector Machines,SVM)，它它被被看看作作是是高高维维空空间间函函数数表表达达的的一一般般方方法。法。使使用用SVM方方法，法，人人们们可可以以在在很很高高维维的的空空间间里里构构造造好好的的分分类类规规则。则。支支持持化化原原则则经经验验风风险险最最小小化化原原则则考考虑虑分分类类问问题。题。样样本本集集为为U=x1,x2,.,xl(m维维空空间间中中的的l个个向向量量)，每每个个向向量量

50、对对应应一一个个类类别，别，类类别别空空间间Y=+1,-1。记记p(x,y)表表示示对对象象x为为y类类的的概概率率分分布。布。分分类类的的任任务务就就是是寻寻找找分分类类器器f：UY且且使使期期望望风风险险最最小。小。f的的期期望望风风险险为：为：在在有有限限样样本本的的情情况况下，下，p(x,y)是是未未知知的，的，因因此此期期望望风风险险无无法法计计算。算。常常使使用用经经验验风风险险代代替，替，且且当当l时时两两者者相相等。等。dxdyyxpyxffR),()()(11()()lempiiiRff xyl)()(limfRfRempl支支持持化化原原则则（Empirical Risk