第04讲智能决策理论与方法ppt课件

1、决策实际与方法 智能决策实际与方法(1)合肥工业大学管理学院Saturday, March 12, 2022不确定性决策不确定性决策：指难以获得各种形状发生的概率，甚至对未来形状都难以把握的决策问题。特点：形状的不确定性。不确定性：不确定性来自人类的客观认识与客观实践之间存在的差别。事物发生的随机性、人类知识的不完全、不可靠、不准确和不一致以及自然言语中存在的模糊性和歧义性，都反映了这种差别，都会带来不确定性。不确定性就呵斥了具有一样描画信息的对象能够属于不同概念。 处理问题的主要实际方法：人工智能与不确定性实际.智能决策实际与方法1、智能决策实际的构成背景2、知识发现3、粗糙集实际4、机器学

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

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

4、构成背景2、知识发现3、粗糙集实际4、机器学习.知识发现动机智能决策的中心是如何获取支持决策的信息和知识。问题知识获取是基于知识的系统(KBS)的最大瓶颈推理机知识工程师领域专家决策者知识库问题恳求推理结果.知识发现动机问题推理规那么的获取与KBS中知识获取一样难，因此基于案例推理(Case-Based Reasoning)渐渐变成基于案例检索(Case-Based Retrieving)。推理机决策者案例库问题恳求推理结果规那么库知识工程师领域专家.知识发现动机决策者数据分析师数据中心不一定称心的决策决策支持查询查询结果问题数据分析师与决策者之间对问题的了解存在偏向短少有发明性的决策建议技术

5、问题：如查询效率(RDBMS).知识发现动机推理机数据发掘工具数据中心决策者知识库问题恳求推理结果背景知识领域专家优点知识独立于问题本身知识的获取主要经过数据发掘实现有发明性收获.Data Mining within the DSS.知识发现动机KDD带来的新问题知识发现问题：如何从数据中将知识发掘出来？面临许多技术问题：如数据异构问题、数据具有噪音且信息不完好、运用什么样的发掘算法、知识如何表示等知识评价问题：数据本身具有权威性、客观性，但知识不具备。知识如何评价？.参考书引荐.为什么要开展数据发掘？信息技术的广泛运用产生了大量的数据：流数据消费数据、监控数据、传感数据各种(时间)序列数据证

6、券买卖，基因序列对象关系数据社交网络，分子构造管理数据MIS，ERP：财务、人力资源、客户关系空间数据GIS、GPS多媒体数据视频监控，视频分享文本数据学术论文，新闻，微博，博客万维网数据内容，构造，运用，买卖数据.为什么要开展数据发掘？Big Data大数据时代第一，数据体量Volume宏大 。从TB级别，跃升到PB级别。第二，数据类型繁多Variety 。网络日志、视频、图片、地理位置信息等等。第三，价值Value密度低。以视频为例，延续不延续监控过程中，能够有用的数据仅仅有一两秒。第四，处置速度Velocity快。1秒定律。We are drowning in data, but sta

7、rving for knowledge! .2022年7月15日电子商务新进展：数据发掘KDD & DM知识发现(Knowledge Discovery in Databases ,KDD) 是指从大量数据中提取有用的(useful)、新颖的(novel)、有效的(valid)并最终能被人了解(understandable)的方式(patterns)的处置过程(process)。 数据发掘(Data Mining，DM) 是KDD的中心阶段, 经过实施相关算法获得期望的方式。.KDD过程了解、定义用户的目的和KDD运转的环境。.KDD过程1选取可用的数据；2定义附加的、必需的数据，如领域知识；

8、3数据集成为一个数据集，供KDD运用。.KDD过程1缺失值处置2剔除噪声或异常数据.KDD过程1维数约简(特征选择与抽取，数据采样)2属性转换 (离散化和泛化)3数据编码.KDD过程(1)确定数据发掘类型，如分类、聚类、回归； (2) 选择特定的方法； (3) 执行数据发掘算法。.KDD过程评价和解释所发掘的方式，重点是可了解性、有用性.KDD过程与原有知识系统合并。挑战: 动态与增量发掘问题。.数据预处置空值估算空值是指属性值未知且不可用、与其它任何值都不一样的符号。在样本数据集中，空值在一切非主码属性中都能够出现。空值出现的主要缘由：在信息搜集时忽略了一些以为不重要的数据或信息提供者不情愿

9、提供，而这些数据对以后的信息处置能够是有用的；某些属性值未知；数据模型的限制。.数据预处置空值估算空值处置的常用方法：从训练集中移去含未知值的实例；用某个最能够的值进展交换；基于样本中其它属性的取值和分类信息，构造规那么来预测丧失的数据，并用预测结果“填补丧失值；运用贝叶斯公式确定未知值的概率分布，选择一最能够的值填补空值或根据概率分布用不同值填补空值构成多个对象；将含有未知值的一个给定样本数据集转换成一个新的、能够不相容的但每个属性值均知的数据集，方法是将某个属性的未知值用一切该属性的能够值交换构成多个数据集。.数据预处置延续属性离散化问题描画 设 为一样本数据集， 为非空有限集合，C是条件

10、属性集，D是决策属性集。假设对于恣意有 ， R是实数集，那么 为延续属性。设 是 上的分割点集合，记为其中 ， 为一整数，表示离散化程度，可以看作按属性将论域中的对象分成 类。3kiki-121.数据预处置延续属性离散化对于需求离散化的延续属性集 ，其分割点集合记为将ci属性的延续取值映射到离散空间，即对于恣意假设其属性ci 的取值在区间 内，那么将属性值重新标志为j。这样就把原来含有延续属性的样本数据集A转换成离散化的数据集 。因此离散化问题本质上可归结为利用选取的分割点对属性的值域空间进展划分的问题。.数据预处置延续属性离散化离散化方法典型的有等区间方法、等信息量方法、基于信息熵的方法、H

11、olte的1R离散化方法、统计实验方法、超平面搜索方法以及用户自定义区间等。运用不同的准那么可将现有的离散化方法分为部分与全局方法(论域空间)、静态与动态方法(属性空间)和有导师与无导师方法(能否依赖决策属性)。(1)等区间离散化方法等区间分割是将延续属性的值域等分成 ( )个区间, 普通由用户确定。.数据预处置延续属性离散化 假设某个属性的最大属性值为xmax，最小属性值为xmin，用户给定的分割点参数为k，那么分割点间隔为=(xmax-xmin)/k， 所得到的属性分割点为xmin+i，i=1,2,k。(2)等信息量离散化方法 等信息量分割首先将丈量值进展排序，然后将属性值域分成k个区间，

12、每个区间包含一样数量的丈量值。假设某个属性的最大属性值为xmax ，最小属性值为xmin ，用户给定的分割点参数为k，样本集中的对象个数为n，那么需求将样本集中的对象按该属性的取值从小到大陈列，然后按对象数平均划分为k段即得到分割点集，每两个相邻分割点之间的对象数均为n/k。 .数据预处置延续属性离散化(3)统计实验方法统计实验方法根据决策属性分析区间划分之间的独立程度，确定分割点的有效性。对于恣意分割点 ，均可将 分成2个区间 和 ，两区间的独立程度为：其中：r是决策类数目nij是在第l区间中属于第j决策类的对象数.数据预处置延续属性离散化 假设 ，那么取 基于统计实验的离散化方法是将 值较

13、大的分割点作为有效分割点。.Taxonomy of Data Mining Methods.Taxonomy of Data Mining MethodsVerification-oriented (the system verifies the users hypothesis): including the most common methods of traditional statistics, like goodness of fit(拟合优度) test, tests of hypotheses (假设检验，e.g., t-test of means), and analysis

14、of variance (ANOVA，方差分析或F-检验).Discovery-oriented (the system finds new rules and patterns autonomously): prediction methods VS description methods；supervised learning有导师学习 VS unsupervised learning.KDD Goals & Methods归纳总结(Induction & Summarization)：从泛化的角度总结数据，即从低层次数据笼统出高层次的描画的过程。主要方法：归纳、泛化。泛化(General

15、ization)是用来扩展一假设的语义信息，使其可以包含更多的正例，运用于更多的对象。动物哺乳类鸟类企鹅食肉类蹄类飞禽类走禽类虎印度豹长颈鹿斑马信天翁鹰驼鸟动物世界概念树第1层第2层第3层第4层.KDD Goals & Methods关联规那么(Association Rules)：关联规那么的方式为AB，A为前件，B为后件。 (Day=Friday) and (Product= Diaper) (Product=Beer)为一典型关联规那么 A为满足前件的对象集，B为满足后件的对象，N为全部对象集。典型方法：Apriori算法。.关联规那么发现(Apriori算法)Apriori算法由Agr

16、awal & Srikant在1994年提出主要思想:一个频繁项集支持度超越给定值的项集的子集一定是频繁的例如， 假设beer, diaper, nuts是频繁的, 那么beer, diaper 一定是频繁的. 任一项为哪一项非频繁的，那么包含该项的超集一定是不频繁的。例如， 假设beer, diaper是不频繁的, 那么 beer, diaper, nuts一定是不频繁的.关联规那么发现(Apriori算法)ProcedureFind the frequent itemsets: the sets of items that have minimum support (Apriori)A s

17、ubset of a frequent itemset must also be a frequent itemset, i.e., if A B is a frequent itemset, both A and B should be a frequent itemsetIteratively find frequent itemsets with cardinality from 1 to k (k-itemset)Use the frequent itemsets to generate association rules.关联规那么发现(Apriori算法)Database DSca

18、n DC1L1L2C2C2Scan DC3L3Scan D.KDD Goals & Methods分类(Classification，等价关系，判别)：按类标签(为数据库中的某属性集，普通仅包含一个属性)对数据库中的对象进展分类，具有一样标签值或标签值在指定区间内的对象属于同类。分类规那么是判别某个对象属于某类的充分条件即对象具有某类的属性时那么表示该对象属于该类。其规那么方式普通为IF LogicExp Then A类 Else B类。主要方法：决策树、ANN、粗糙集、SVM等。分别引见.KDD Goals & Methods聚类(Clustering,相容关系)：聚类也叫分段，就是将数据库

19、中的实体分成假设干组或簇，簇内实体类似性最大，簇间类似性最小。对象类似的判别方法有多种如间隔法。典型方法：K-means聚类方法的中心问题是样品间的类似性度量，通常用间隔来度量。.聚类(K-means算法)聚类分析中的常用间隔(1)欧氏(Euclidean)间隔(2)绝对间隔 在实践运用时常分析两个样品之间的相对间隔，这时需求对样品数据进展规范化处置，然后用规范化数据计算间隔。.聚类(K-means算法)对于给定的n个样品，先粗略地构成k(kn)个分割，使得每个分割对应一个类、每个类至少有一个样品并且每个样品准确地属于一个类，然后按照某种原那么进展修正，直至分类比较合理为止。详细步骤如下：(1

20、)聚点的选择：聚点是一批有代表性的样品，它的选择决议了初始分类。首先确定分类数k，然后选择k个有代表性的样品作为每个类的初始元素即聚点。聚点可由用户根据阅历选择，也可随机选择，或将全部样品人为地或随机地分成k类，以每类的重心作为聚点。.聚类(K-means算法)(2)初始聚类有了聚点集合后，可根据以下最接近原那么实现初始分类：假设对于某样品x出现 ，那么x恣意归于Gi(0) 或Gj(0) 类。这样就得到了样品空间的初始分类：.聚类(K-means算法)(3)迭代过程设聚类构成的一个分类为那么可从G(m)出发计算新的聚点集合L(m+1)。普通可以以G(m)中各类的重心作为新的聚点。其中根据新的聚

21、点集，对样品空间重新聚类，构成新的分类：其中.聚类(K-means算法)(4)迭代终止 随着m的增大，分类趋于稳定。当G(m+1)=G(m)或在一定的精度范围内近似有G(m+1)=G(m)，那么递推过程终了。.聚类(K-means算法)m-male，f-femalemfmmmmmmmfmmmmmmmmmffmmmmmmmmmmmfmmmmmmmmmmmmmmmmmmmf16K64K32K20304050ageincome聚类模型.KDD Goals & Methods回归(Regression)：根据历史数据拟合一函数将属性集映射到相应的值集。回归可以看作一种分类，区别是分类的类标签值是离散的

22、，而回归是延续的。neurallinerprofit010005000mins 回归模型.KDD Goals & MethodsSequence, trend and evolution analysisTrend, time-series, and deviation analysis: e.g., regression and value predictionSequential pattern mininge.g., first buy digital camera, then buy large SD memory cardsPeriodicity analysisMotifs and

23、 biological sequence analysisApproximate and consecutive motifsSimilarity-based analysisMining data streamsOrdered, time-varying, potentially infinite, data streams.KDD Goals & Methods异常探测(Outlier Detection)：Outlier: A data object that does not comply with the general behavior of the dataNoise or ex

24、ception? One persons garbage could be another persons treasureMethods: by product of clustering or regression analysis, Useful in fraud detection, rare events analysis.KDD Goals & MethodsStructure and Network AnalysisGraph mining：Finding frequent subgraphs, trees, substructuresInformation network an

25、alysis：Social networksMultiple heterogeneous networks： friends, family, classmates, Links carry a lot of semantic information: Link miningWeb miningWeb is a big information network: from PageRank to GoogleAnalysis of Web information networks，Web community discovery, opinion mining, usage mining, .智能

26、决策实际与方法1、智能决策实际的构成背景2、知识发现3、粗糙集实际4、机器学习.预备知识相关名词解释论域：研讨对象的全体成员构成的集合，普通用字母U表示；假设XU，那么称X是U的子集隶属度：描画一个对象x与某个子集X之间的隶属程度，普通用符号表示，假设xX, 那么=1;假设 ,那么=0;其他： 01(常用某个函数加以描画，称为隶属度函数).预备知识相关名词解释等价关系：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，称

27、集合x=y| y R x, y U为U关于R的一个等价类，记为xR。设X1, X2, , Xn是U关于R的一切等价类，那么有：XiXj=ij，i, j=1,2,nX1X2Xn=U划分：一切等价类的集合称为U关于R的商集，它构成了U的一个划分，记为U/R。概念：具有一样特征值的一群对象称为一个概念一个等价类就是一个概念.预备知识相关名词解释pi T1 pj iff v(pi, T1)=v(pj, T1)，那么T1是U上的一个等价关系类似地可以定义T2, T3, EX1=p1=p4=p6=p1, p4, p6为U关于T1的一个等价类X2=p2=p3=p5=p2, p3, p5为U关于T1的另一个等

28、价类T1有多少种取值就有多少个等价类显然 X1X2=; X1X2=U商集U/T1=X1, X2UT1 T2T3Ep1NYNormalYp2YNNormalYp3YYHighYp4NYLowNp5YNNormalNp6NYHighY.预备知识成员集合成员：明确的隶属关系模糊成员：概念模糊(如青年)导致成员模糊粗糙成员：概念明晰(如感冒)，成员模糊(能否感冒不清楚)，具有概率特征(隶属函数)，但不是概率问题，只是由于根据可用知识无法得到准确结论。.粗糙集实际的提出粗糙集实际由Pawlak提出1982,1991。粗糙集实际反映了人们以不完全信息或知识去处置一些不可分辨景象的才干，或根据察看、度量到某

29、些不准确的结果而进展分类数据的才干。Pawlak Z., Rough sets. International Journal of Computer and Information Sciences, 1982(11): 341-356Pawlak Z., Rough setTheoretical Aspects of Reasoning about Data, Dordrecht, Boston, London: Kluwer Academic Publishers,1991.根本思想知识是主体对论域中的客体进展分类的才干，分类才干越强，主体所具备知识的可靠度越高 分类才干受主体分辨才干的影

30、响，因此分类具有近似性 (粗糙集)影响分类才干的要素(在信息系统中常描画为属性)很多，不同的要素重要程度不同，其中某些要素起决议性作用 (属性重要性：属性约简)具有一样属性的实体，属性取值的不同对分类才干也产生影响 (值重要性：值约简)属性之间存在某种依赖关系(决策规那么).信息系统与知识信息系统I可以定义为四元组，其中有限非空集合U是论域，A为关于U的属性集， ，Va表示属性a的值域，映射f: UAV表示对xU，aA，有： f(x, a)V。决策表：假设属性集合A可进一步分为两个属性子集的并：条件属性集C和决策属性集D，A=CD，CD=，那么信息系统也被称为决策表。UT1 T2T3Ep1NY

31、NormalYp2YNNormalYp3YYHighYp4NYLowNp5YNNormalNp6NYHighY.信息系统与知识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上的一个知识库，记

32、为K=(U, R)。.粗糙集与近似对于U的恣意子集X，假设X恰能由知识R的假设干个初等集的并构成，那么称X为R-准确集，否那么为R-粗糙集。每个粗糙集X都可用两个与之相关的准确集近似表示即X的上近似和下近似，他们是粗糙集实际的两个最根本运算。.粗糙集与近似下近似由一切包含于X的初等集合的并构成， X的下近似中的元素一定属于X。上近似由与X的交为非空的初等集合的并构成，而上近似中的元素能够属于X。上近似与下近似的差为边境域，粗糙集的边境域为非空，否那么为准确集。边境域中的元素根据可用知识没有确定的分类，即它既不能划分到X中也不能划分到X的补集中。正域与负域.经典粗糙集模型论域U粗糙集X粗糙集X.

33、经典粗糙集模型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精度

34、反映了我们对于了解集合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, 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粗糙集，

35、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看成决策属性集，近似质量反映了两者之间的依赖关系。.粗糙集数字特征知识R=T1, T2, T3：U/R=(p1, p3, p6, p2,

36、 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

37、=，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

38、, 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。条件属性子集T1T2T3T1,T2 T1,T3 T2,T3T1,T2,T3依赖度k001/21/62/32/32/3.知识约简为什么要约简知识？判别：根据条件属性取值确定对象所属的类。实践：确定对象所属的类只需其中几个属性甚至一个属性，而不需求知道对象一切的属性，这与人类对实体的识别是一致的。阐明：不同属性在分类时所起的作用是不同的。什么是知识约简？将知识库中某些不用要的等价关系知识移去的过程。设信息系统I=，BC，假设C(D)=B(D)且B是D独立的，那么B为C的D约简，记为REDD(C)。C的D约简是不含任何