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

1、决策理论与方法 智能决策理论与方法(1), 19 2020 .,不确定性决策,不确定性决策：指难以获得各种状态发生的概率，甚至对未来状态都难以把握的决策问题。 特点：状态的不确定性。 不确定性：不确定性来自人类的主观认识与客观实际之间存在的差异。事物发生的随机性、人类知识的不完全、不可靠、不精确和不一致以及自然语言中存在的模糊性和歧义性，都反映了这种差异，都会带来不确定性。不确定性就造成了具有相同描述信息的对象可能属于不同概念。 解决问题的主要理论方法：人工智能与不确定性理论,智能决策理论与方法,1、智能决策理论的形成背景 2、知识发现 3、粗糙集理论 4、机器学习,智能决策理论与方法形成背景

2、,人类面临越来越复杂的决策任务和决策环境： 决策问题所涉及的变量规模越来越大； 决策所依赖的信息具有不完备性、模糊性、不确定性等特点，使得决策问题难以全部定量化地表示出来； 某些决策问题及其目标可能是模糊的、不确定的，使得决策者对自己的偏好难以明确，随着决策分析的深入，对决策问题的认知加深，自己原有的偏好/倾向得到不断地修正，使得决策过程出现不断调整的情况， 这时，传统的决策数学模型已经难以胜任求解复杂度过高的决策问题、含有不确定性的决策问题以及半结构化、非结构化的决策问题，因而产生了智能决策理论、方法及技术。,智能决策理论与方法AI的应用模式,智能决策方法是应用人工智能(Artificial

3、 Intelligence, AI)相关理论方法，融合传统的决策数学模型和方法而产生的具有智能化推理和求解的决策方法，其典型特征是能够在不确定、不完备、模糊的信息环境下，通过应用符号推理、定性推理等方法，对复杂决策问题进行建模、推理和求解。AI应用于决策科学主要有两种模式： 针对可建立精确数学模型的决策问题，由于问题的复杂性，如组合爆炸、参数过多等而无法获得问题的解析解，需要借助AI中的智能搜索算法获得问题的数值解； 针对无法建立精确数学模型的不确定性决策问题、半结构化或非结构化决策问题，需要借助AI方法建立相应的决策模型并获得问题的近似解。,智能决策理论与方法,1、智能决策理论的形成背景 2

4、、知识发现 3、粗糙集理论 4、机器学习,知识发现动机,智能决策的核心是如何获取支持决策的信息和知识。,问题 知识获取是基于知识的系统(KBS)的最大瓶颈,知识发现动机,问题 推理规则的获取与KBS中知识获取一样难，因而基于案例推理(Case-Based Reasoning)渐渐变成基于案例检索(Case-Based Retrieving)。,知识发现动机,问题 数据分析师与决策者之间对问题的理解存在偏差 缺少有创造性的决策建议 技术问题：如查询效率(RDBMS),知识发现动机,优点 知识独立于问题本身 知识的获取主要通过数据挖掘实现 有创造性收获,Data Mining within the

5、 DSS,知识发现动机,KDD带来的新问题 知识发现问题：如何从数据中将知识挖掘出来？面临许多技术问题：如数据异构问题、数据具有噪音且信息不完整、使用什么样的挖掘算法、知识如何表示等 知识评价问题：数据本身具有权威性、客观性，但知识不具备。知识如何评价？,参考书推荐,为什么要开展数据挖掘？,信息技术的广泛应用产生了大量的数据： 流数据（生产数据、监控数据、传感数据） 各种(时间)序列数据（证券交易，基因序列） 对象关系数据（社交网络，分子结构） 管理数据（MIS，ERP：财务、人力资源、客户关系） 空间数据（GIS、GPS） 多媒体数据（视频监控，视频分享） 文本数据（学术论文，新闻，微博，博

6、客） 万维网数据（内容，结构，使用，交易数据） ,为什么要开展数据挖掘？,Big Data大数据时代 第一，数据体量（Volume）巨大 。从TB级别，跃升到PB级别。 第二，数据类型繁多（Variety） 。网络日志、视频、图片、地理位置信息等等。 第三，价值（Value）密度低。以视频为例，连续不间断监控过程中，可能有用的数据仅仅有一两秒。 第四，处理速度（Velocity）快。1秒定律。 We are drowning in data, but starving for knowledge!, 19 2020 .,电子商务新进展：数据挖掘,KDD 若 ,则=0; 其他： 01(常用某个函

7、数加以描述，称为隶属度函数),预备知识相关名词解释,等价关系：R是U上的一个等价关系，当且仅当 对于任意xU，均有x R x（自反性） 对于任意x, yU，x R yy R x（对称性） 对于任意x, y, zU，x R y y R zx R z（传递性） 等价类：若R是U上的一个等价关系，对于任意xU，称集合x=y| y R x, y U为U关于R的一个等价类，记为xR。设X1, X2, , Xn是U关于R的所有等价类，则有： XiXj=（ij，i, j=1,2,n） X1X2Xn=U 划分：所有等价类的集合称为U关于R的商集，它构成了U的一个划分，记为U/R。 概念：具有相同特征值的一群对

8、象称为一个概念（一个等价类就是一个概念）,预备知识相关名词解释,pi T1 pj iff v(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,预备知识成员,集合成员：明确的隶属关系 模糊成员：概念模糊(如青年)导致成员模糊 粗糙成员：概念清晰(如感冒)，成员模糊(是否感冒不清楚)，具有概率特征(隶属函数)，

9、但不是概率问题，只是由于根据可用知识无法得到准确结论。,粗糙集理论的提出,粗糙集理论由Pawlak提出1982,1991。粗糙集理论反映了人们以不完全信息或知识去处理一些不可分辨现象的能力，或依据观察、度量到某些不精确的结果而进行分类数据的能力。 Pawlak Z., Rough sets. International Journal of Computer and Information Sciences, 1982(11): 341-356 Pawlak Z., Rough setTheoretical Aspects of Reasoning about Data, Dordrecht,

10、 Boston, London: Kluwer Academic Publishers,1991,基本思想,知识是主体对论域中的客体进行分类的能力，分类能力越强，主体所具备知识的可靠度越高 分类能力受主体分辨能力的影响，因此分类具有近似性 (粗糙集) 影响分类能力的因素(在信息系统中常描述为属性)很多，不同的因素重要程度不同，其中某些因素起决定性作用 (属性重要性：属性约简) 具有相同属性的实体，属性取值的不同对分类能力也产生影响 (值重要性：值约简) 属性之间存在某种依赖关系(决策规则),信息系统与知识,信息系统I可以定义为四元组，其中有限非空集合U是论域，A为关于U的属性集， ，Va表示属

11、性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)等价类为初等集（范畴），它是知识库的

12、基本结构单元即概念。 设R是由属性集A的子集诱导的论域U上的等价关系族，则称R为U上的一个知识库，记为K=(U, R)。,粗糙集与近似,对于U的任意子集X，若X恰能由知识R的若干个初等集的并构成，则称X为R-精确集，否则为R-粗糙集。 每个粗糙集X都可用两个与之相关的精确集近似表示即X的上近似和下近似，他们是粗糙集理论的两个最基本运算。,粗糙集与近似,下近似 由所有包含于X的初等集合的并构成， X的下近似中的元素一定属于X。 上近似 由与X的交为非空的初等集合的并构成，而上近似中的元素可能属于X。 上近似与下近似的差为边界域，粗糙集的边界域为非空，否则为精确集。边界域中的元素根据可用知识没有确

13、定的分类，即它既不能划分到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, p5 X1=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，X

14、2的R上近似是p2, p4, p5，而边界域是p2, p5。,粗糙集数字特征,精度： X的R精度反映了我们对于了解集合X的知识的完全程度。R(X)=1为精确集， 0R(X)1为粗糙集。 粗糙度：X的R粗糙度反映了我们对于了解集合X的知识的不完全程度。(精度与概率或隶属度的区别) 隶属度：是根据可用知识R，对象x隶属于概念X的条件概率。,粗糙集数字特征,知识R=T1, T2, T3：U/R=(p1, p3, p6, p2, p5,p4; 分类F=E：U/F=p1, p2, p3, p6, p4, p5 X1=p1, p2, p3, p6是R粗糙集，X1的R下近似是p1, p3, p6，R上近似是

15、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； p2隶属于X1的隶属度为0.25。,粗糙集数字特征,设F=X1，X2，Xn是论域U上的一个划分，那么根据知识R，F的分类精度如何？ F的近似精度：分类的近似精度给出了根据现有知识对对象进行分类时可能正确的决策的百分数。 F的近似质量：近似质量给出了能正确分类的百分数。这是一个非常重要的特征数字，它反映了两种分类F和R之间的关系。如果将R看作决策表中的条件属性集，F看成决策属性集，近似质

16、量反映了两者之间的依赖关系。,粗糙集数字特征,知识R=T1, T2, T3：U/R=(p1, p3, p6, p2, p5,p4; 分类F=E：U/F=p1, p2, p3, p6, p4, p5 X1=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”形式的推理规则，在粗糙集理论体系中所采用的方法是从一个给定的知识，推导另一个知识。如果

17、知识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

18、； 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, p5 X1=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。,知识约简,为什么要约简知识？ 判别：根据条件属性取

19、值确定对象所属的类。 实际：确定对象所属的类只需其中几个属性甚至一个属性，而不需要知道对象所有的属性，这与人类对实体的识别是一致的。 表明：不同属性在分类时所起的作用是不同的。 什么是知识约简？ 将知识库中某些不必要的等价关系（知识）移去的过程。 设信息系统I=，BC，若C(D)=B(D)且B是D独立的，则B为C的D约简，记为REDD(C)。 C的D约简是不含任何冗余知识且与C具有相同分类能力的子集（用知识C将对象划分到知识D的初等范畴中的能力）。,属性重要性与属性核,在确定某个决策目标时，不同属性的重要性是不同的，在一般分析中常用事先假设的权重来描述。粗糙集理论并不使用事先假设的信息，而是根

20、据各属性的分类能力不同，确定该属性的重要性。处理方法是将该属性从信息表中移去，分析其对分类能力的影响，影响越大，属性越重要。 设信息系统I=，对于C的非空子集B，其重要度为 若B的重要度为，则表示B可以从C中移去，也即B是冗余的。重要度可理解为移去B时所产生的分类误差。 设信息系统I=，C中所有D不可省略的元素构成的集合称为C的D核，记作CoreD(C)。,知识约简算法,基于属性依赖度的属性约简：设决策表T=，C,D分别为条件属性和决策属性，B是C的任一非空子集，对于粗糙集的VP-MD模型，D对B的依赖度为： 则在B中增加某个属性pC-B所引起的k的变化大小为： p(D|B)= Bp(D)-B(D) p(D|B)越大，说明在已知属性B的条件下，p对决策D越重要。基于属性