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

决策理论与方法——不确定性决策理论与方法合肥工业大学管理学院2019年8月29日不确定性决策理论与方法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】a1a2a3a4θ12343θ22301θ34344θ43344不确定性决策准则不确定性决策问题举例【Milnor,1954】a1a2a3a4最小损失后悔值a1a2a3a4θ1234320121θ2230102301θ3434431011θ4334430011最大损失（悲观）4344a2最大后悔值pi2321最小损失（乐观）2301a3a4乐观系数4-234-44-30.25，a2；0.25，a3等概率2.753.003.003.00a1不确定性决策准则公理悲观准则乐观系数后悔值等概率1.完全序2.标号无关性3.标度无关性4.强优势原则5.无关方案独立6.后果加常无关性7.后果排序无关性8.状态行复制无关性智能决策理论与方法—形成背景人类面临越来越复杂的决策任务和决策环境：决策问题所涉及的变量规模越来越大；决策所依赖的信息具有不完备性、模糊性、不确定性等特点，使得决策问题难以准确地量化表示；某些决策问题及其目标可能是模糊的、不确定的，使得决策者对自己的偏好难以明确，随着决策分析的深入，对决策问题的认知加深，自己原有的偏好/倾向得到不断地修正，使得决策过程出现不断调整的情况。这时，传统的决策数学模型已经难以胜任求解复杂度过高的决策问题、含有不确定性的决策问题以及半结构化、非结构化的决策问题，因而产生了智能决策理论、方法及技术。智能决策理论与方法—AI的应用模式智能决策方法是应用人工智能(ArtificialIntelligence,AI)相关理论方法，融合传统的决策数学模型和方法而产生的具有智能化推理和求解的决策方法，其典型特征是能够在不确定、不完备、模糊的信息环境下，通过应用符号推理、定性推理等方法，对复杂决策问题进行建模、推理和求解。AI应用于决策科学主要有两种模式：针对可建立精确数学模型的决策问题，由于问题的复杂性，如组合爆炸、参数过多等而无法获得问题的解析解，需要借助AI中的智能搜索算法获得问题的数值解；针对无法建立精确数学模型的不确定性决策问题、半结构化或非结构化决策问题，需要借助AI方法建立相应的决策模型并获得问题的近似解。知识发现—动机智能决策的核心是如何获取支持决策的信息和知识。问题知识获取是基于知识的系统(KBS)的最大瓶颈推理机知识工程师领域专家决策者知识库问题请求推理结果知识发现—动机问题推理规则的获取与KBS中知识获取一样难，因而基于案例推理(Case-BasedReasoning)渐渐变成基于案例检索(Case-BasedRetrieving)。推理机决策者案例库问题请求推理结果规则库知识工程师领域专家知识发现—动机决策者数据分析师数据中心不一定满意的决策决策支持查询查询结果问题数据分析师与决策者之间对问题的理解存在偏差缺少有创造性的决策建议技术问题：如查询效率(RDBMS)知识发现—动机推理机数据挖掘工具数据中心决策者知识库问题请求推理结果背景知识领域专家优点知识独立于问题本身知识的获取主要通过数据挖掘实现有创造性收获DataMiningwithintheDSS知识发现—动机KDD带来的新问题知识发现问题：如何从数据中将知识挖掘出来？面临许多技术问题：如数据异构问题、数据具有噪音且信息不完整、使用什么样的挖掘算法、知识如何表示等知识评价问题：数据本身具有权威性、客观性，但知识不具备。知识如何评价？参考书推荐KDD&DM知识发现(KnowledgeDiscoveryinDatabases,KDD)是指从大量数据中提取有用的(useful)、新颖的(novel)、有效的(valid)并最终能被人理解(understandable)的模式(patterns)的处理过程(process)。数据挖掘(DataMining，DM)是KDD的核心阶段,通过实施相关算法获得期望的模式。KDD过程理解、定义用户的目标和KDD运行的环境。KDD过程（1）选取可用的数据；（2）定义附加的、必须的数据，如领域知识；（3）数据集成为一个数据集，供KDD使用。KDD过程（1）缺失值处理（2）剔除噪声或异常数据KDD过程（1）维数约简(特征选择与抽取，数据采样)（2）属性转换(离散化和泛化)（3）数据编码KDD过程(1)确定数据挖掘类型，如分类、聚类、回归；(2)选择特定的方法；(3)执行数据挖掘算法。KDD过程评估和解释所挖掘的模式，重点是可理解性、有用性.KDD过程与原有知识系统合并。挑战:动态与增量挖掘问题。TaxonomyofDataMiningMethodsTaxonomyofDataMiningMethodsVerification-oriented(thesystemverifiestheuser‘shypothesis):includingthemostcommonmethodsoftraditionalstatistics,likegoodnessoffit(拟合优度)test,testsofhypotheses(假设检验，e.g.,t-testofmeans),andanalysisofvariance(ANOVA，方差分析或F-检验).Discovery-oriented(thesystemfindsnewrulesandpatternsautonomously):predictionmethodsVSdescriptionmethods；supervisedlearning（有导师学习）VSunsupervisedlearningTaxonomyofDataMiningMethods分类有监督学习无监督学习父母、老师教我们认识世界的万事万物。人类认识新生事物。标签化TaxonomyofDataMiningMethods有监督学习输入：X={x1,...,xj,...,xN}。xj={xj1,...,xji,...,xjd}T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，训练样本集为(xi,yi)。TaxonomyofDataMiningMethods无监督学习无监督分类(聚类)：应用于无标签数据的分类，称为聚类分析或探究性分析，其目标是将无标签数据分类到有限、离散的“自然状态”。“自然状态”隐藏了数据的结构，而不是为未观测的样本提供一个精确刻画(描述而非预测)。无监督预测学习(如关联规则发现、链接分析等)：具有预测能力的无监督学习。不确定性决策理论与方法1、不确定性决策概述2、关联规则发现3、聚类分析4、连接分析5、粗糙集分析6、决策树7、神经网络8、支持向量机关联规则发现关联规则(AssociationRules)：关联规则的形式为A→B，A为前件，B为后件。(Day=Friday)and(Product=Diaper)→(Product=Beer)为一典型关联规则A为满足前件的对象集，B为满足后件的对象，N为全部对象集。典型方法：Apriori算法。NBASupport||||||ABAConfidence2019年8月29日8时22分决策理论与方法-智能决策理论与方法关联规则发现(Apriori算法)Apriori算法由Agrawal&Srikant在1994年提出主要思想:一个频繁项集（支持度超过给定值的项集）的子集一定是频繁的例如，若{beer,diaper,nuts}是频繁的,那么{beer,diaper}一定是频繁的.任一项是非频繁的，则包含该项的超集一定是不频繁的。例如，若{beer,diaper}是不频繁的,那么{beer,diaper,nuts}一定是不频繁的.关联规则发现(Apriori算法)ProcedureFindthefrequentitemsets:thesetsofitemsthathaveminimumsupport(Apriori)Asubsetofafrequentitemsetmustalsobeafrequentitemset,i.e.,if{AB}isafrequentitemset,both{A}and{B}shouldbeafrequentitemsetIterativelyfindfrequentitemsetswithcardinalityfrom1tok(k-itemset)Usethefrequentitemsetstogenerateassociationrules.关联规则发现(Apriori算法)TIDItems100134200235300123540025DatabaseDitemsetsup.{1}2{2}3{3}3{4}1{5}3itemsetsup.{1}2{2}3{3}3{5}3ScanDC1L1itemset{12}{13}{15}{23}{25}{35}itemsetsup{12}1{13}2{15}1{23}2{25}3{35}2itemsetsup{13}2{23}2{25}3{35}2L2C2C2ScanDC3L3itemset{235}ScanDitemsetsup{235}2不确定性决策理论与方法1、不确定性决策概述2、关联规则发现3、聚类分析4、连接分析5、粗糙集分析6、决策树7、神经