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

决策理论与方法 不确定性决策理论与方法 合肥工业大学管理学院2019年12月27日 不确定性决策理论与方法 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带来的新问题知识发现问题 如何从数据中将知识挖掘出来 面临许多技术问题 如数据异构问题 数据具有噪音且信息不完整 使用什么样的挖掘算法 知识如何表示等知识评价问题 数据本身具有权威性 客观性 但知识不具备 知识如何评价 参考书推荐 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过程 与原有知识系统合并 挑战 动态与增量挖掘问题 TaxonomyofDataMiningMethods TaxonomyofDataMiningMethods Verification oriented thesystemverifiestheuser shypothesis includingthemostcommonmethodsoftraditionalstatistics likegoodnessoffit 拟合优度 test testsofhypotheses 假设检验 e g t testofmeans andanalysisofvariance ANOVA 方差分析或F 检验 Discovery oriented thesystemfindsnewrulesandpatternsautonomously predictionmethodsVSdescriptionmethods supervisedlearning 有导师学习 VSunsupervisedlearning TaxonomyofDataMiningMethods 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算法 2019年12月27日3时59分 决策理论与方法 智能决策理论与方法 关联规则发现 Apriori算法 Apriori算法由Agrawal Srikant在1994年提出主要思想 一个频繁项集 支持度超过给定值的项集 的子集一定是频繁的例如 若 beer diaper nuts 是频繁的 那么 beer diaper 一定是频繁的 任一项是非频繁的 则包含该项的超集一定是不频繁的 例如 若 beer diaper 是不频繁的 那么 beer diaper nuts 一定是不频繁的 关联规则发现 Apriori算法 ProcedureFindthefrequentitemsets thesetsofitemsthathaveminimumsupport Apriori Asubsetofafrequentitemsetmustalsobeafrequentitemset i e if A B isafrequentitemset both A and B shouldbeafrequentitemsetIterativelyfindfrequentitemsetswithcardinalityfrom1tok k itemset Usethefrequentitemsetstogenerateassociationrules 关联规则发现 Apriori算法 不确定性决策理论与方法 1 不确定性决策概述2 关联规则发现3 聚类分析4 连接分析5 粗糙集分析6 决策树7 神经网络8 支持向量机 聚类 聚类 Clustering 的定义聚类算法将数据分割成若干个簇 被大多数人接受的定义是 簇内的相似性尽可能大 簇内同质性 簇间的相似性尽可能小 簇间异质性 聚类是一个主观过程 其相似性度量都是根据发现感兴趣的 簇 的能力主观选择的 不存在一个绝对的准则适用所有情境 输入 X x1 xj xN xj xj1 xji xjd T Rd xji表示对象xj对应的第i个特征 维度 属性 变量 的值 聚类 聚类的定义硬聚类 基于划分的聚类 试图将X分割成K个簇C C1 Ck CK K N 满足 Ci i 1 k i 1 k Ci X Ci Cj i j 1 k i j 层次聚类 试图构造一个X的树状嵌套结构H H1 HQ Ql 则要么Ci Cj 要么Ci Cj 解释 如果两个簇不在同一层 那么 这两个簇要么是包含关系 要么不相交 2019年12月27日3时59分 决策理论与方法 智能决策理论与方法 聚类 聚类的定义软聚类 基于相容的聚类 试图将X分割成K个簇C C1 Ck CK K N 满足 Ci i 1 k i 1 k Ci X 对象xj属于Ci簇的隶属度为ui j ui j满足 聚类 相似性度量 数据对象与特征 数据对象都是由一些特征来描述的 常表示为多维向量 特征类型包括定量与定性 连续与离散 名词与序数等 特征类型决定着相似性测度机制 聚类 相似性度量 相似性度量方法连续型 包括序数型 特征Minkowski 闵氏 距离 值较大和波动较大的特征主导着相似性 n 1时 称为绝对距离 超矩形聚类 n 2时 称为欧几里德距离 超球面聚类 n 时 称为上确界距离 Dij max xil xjl l 1 d 聚类 相似性度量 相似性度量方法连续型 包括序数型 特征余弦相似性 Mahalanobis 马氏 距离 S为协方差矩阵 当各个特征是线性无关的时候 Dij就是欧氏距离 计算量较大 聚类 相似性度量 相似性度量方法连续型 包括序数型 特征Pearson相关系数 Dij 1 rij 不能度量两个对象的差异幅度 例如 x1 1 1 1 x2 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个输入数据对象 两两之间的相似性可以表示成一个N N阶对称矩阵 称为邻近矩阵 聚类 主要方法 层次聚类方法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 d q p P q p xq k Nq P为站点的页面集 n为所有页面数 Nq为页面q的出度 xq k 为页面q的重要性 这样就可以计算出所有页面的重要性 记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 连接分析 PageRank算法 连接分析 PageRank算法 算例 0 连接分析 PageRank算法 不确定性决策理论与方法 1 不确定性决策概述2 关联规则发现3 聚类分析4 连接分析5 粗糙集分析6 决策树7 神经网络8 支持向量机 粗糙集 预备知识 论域 研究对象的全体成员构成的集合 一般用字母U表示 若X U 则称X是U的子集隶属度 描述一个对象x与某个子集X之间的隶属程度 一般用符号 表示 若x X 则 1 若 则 0 其他 0 1 常用某个函数加以描述 称为隶属度函数 等价关系 R是U上的一个等价关系 当且仅当对于任意x U 均有xRx 自反性 对于任意x y U xRy yRx 对称性 对于任意x y z U xRy yRz xRz 传递性 等价类 若R是U上的一个等价关系 对于任意x U 称集合 x y yRx y U 为U关于R的一个等价类 记为 x R 设X1 X2 Xn是U关于R的所有等价类 则有 Xi Xj i j i j 1 2 n X1 X2 Xn 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有多少种取值就有多少个等价类 显然X1 X2 X1 X2 U商集U T1 X1 X2 粗糙集 预备知识 集合成员 明确的隶属关系模糊成员 概念模糊 如青年 导致成员模糊粗糙成员 概念清晰 如感冒 成员模糊 是否感冒不清楚 具有概率特征 隶属函数 但不是概率问题 只是由于根据可用知识无法得到准确结论 粗糙集 预备知识 粗糙集理论由Pawlak提出 1982 1991 粗糙集理论反映了人们以不完全信息或知识去处理一些不可分辨现象的能力 或依据观察 度量到某些不精确的结果而进行分类数据的能力 PawlakZ Roughsets InternationalJournalofComputerandInformationSciences 1982 11 341 356PawlakZ Roughset TheoreticalAspectsofReasoningaboutData Dordrecht Boston London KluwerAcademicPublishers 1991 粗糙集 理论的提出 知识是主体对论域中的客体进行分类的能力 分类能力越强 主体所具备知识的可靠度越高分类能力受主体分辨能力的影响 因此分类具有近似性 粗糙集 影响分类能力的因素 在信息系统中常描述为属性 很多 不同的因素重要程度不同 其中某些因素起决定性作用 属性重要性 属性约简 具有相同属性的实体 属性取值的不同对分类能力也产生影响 值重要性 值约简 属性之间存在某种依赖关系 决策规则 粗糙集 基本思想 信息系统I可以定义为四元组 其中有限非空集合U是论域 A为关于U的属性集 Va表示属性a的值域 映射f U A V表示对 x U a A 有 f x a V 决策表 若属性集合A可进一步分为两个属性子集的并 条件属性集C和决策属性集D A C D C D 则信息系统也被称为决策表 粗糙集 信息系统与知识 A的任何一个子集B确定一个U上的二元关系IND B 对于任意a B xIND B y a x a y x y U a x 表示对象x的a属性值 则称IND B 为不可分辨关系 IND B 是等价关系 IND B 的所有等价类的集合记为U B 称为知识B 含有元素x的等价类记为B x 或 x B 同一等价类中的元素是不可分辨的 称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 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 X2的R上近似是 p2 p4 p5 而边界域是 p2 p5 粗糙集 经典粗糙集模型 精度 X的R精度反映了我们对于了解集合X的知识的完全程度 R X 1为精确集 0 R 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 p5 X1 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 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 粗糙集 数字特征 为了寻找 IF THEN 形式的推理规则 在粗糙集理论体系中所采用的方法是从一个给定的知识 推导另一个知识 如果知识D的所有初等范畴都能用知识C的某些初等范畴来定义 则称知识D可由知识C推得 也称D完全依赖于C 记为C D 设信息系统I A C D B C 则D的B正域定义为 D的B正域表示 利用知识B 能正确地划分到U D各等价类中的所有对象的集合 粗糙集 知识依赖 设信息系统I D完全依赖于C当且仅当 D等价于C当且仅当 C D D C D独立于C当且仅当 C D D C 如果知识D的部分初等范畴能用知识C的某些初等范畴来定义 称知识D部分依赖于知识C 设信息系统I 有 则称D是k 0 k 1 度依赖于C 记为C kD 粗糙集 知识依赖 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 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 粗糙集 知识依赖 为什么要约简知识 判别 根据条件属性取值确定对象所属的类 实际 确定对象所属的类只需其中几个属性甚至一个属性 而不需要知道对象所有的属性 这与人类对实体的识别是一致的 表明 不同属性在分类时所起的作用是不同的 什么是知识约简 将知识库中某些不必要的等价关系 知识 移去的过程 设信息系统I B C 若 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中增加某个属性p C B所引起的k的变化大小为 p D B B p 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函数 用以创建各种类型的神经网络 神经网络 newcf cascade forwardbackpropagationnetwork newelm Elmanbackpropagationnetwork newff feed forwardbackpropagationnetwork newfftd feed forwardinput delaybackpropnetwork newpnn probabilisticneuralnetwork newrb radialbasisnetwork newrbe exactradialbasisnetwork newsom self organizingmapnewhop Hopfieldrecurrentnetwork newgrnn generalizedregressionneuralnetwork newlvq learningvectorquantizationnetwork 神经网络 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 U Y且使期望风险最小 f的期望风险为 在有限样本的情况下 p x y 是未知的 因此期望风险无法计算 常使用经验风险代替 且当l 时两者相等 支持向量机 如果成立 则称经验风险最小化原则 EmpiricalRiskMinimization ERM 具有一致性 结构风险最小化原则Vapnik在1971年证明经验风险最小值未必收敛于期望风险最小值 即ERM不成立 因此提出了结构风险最小化原则 StructuralRiskMinimization SRM 为小样本统计理论奠定了基础 支持向量机 Vapnik和Chervonenkis通过研究 得出了期望风险和经验风险的如下关系以概率1 成立 即l为样本点数目 参数0 1 h为函数f的维数 简称VC维 在无法求得期望风险的情形下找到了它的一个上界 不等式右边与样本的具体分布无关 即Vapnik的统计学习理论无需假设样本分布 克服了高维分布对样本点需求随维数而指数增长的问题 这是小样本统计理论与经典统计理论的本质区别 也是将Vapnik统计方法称之为小样本统计理论的原因 VC维置信度 支持向量机 讨论 1 如果l h较大 则期望风险 实际风险 主要由经验风险来决定 因此对于大样本集经验风险经常能给出较好结果 2 如果比值l h较小 小样本集 则小的经验风险并不能保证有小的期望风险值 必须同时考虑经验风险和置信范围 称之为VC维置信度 VC维在其中起重要作用 实际上置信范围是h的增函数 在样本点数目l一定时 分类器越复杂 即VC维越大 则置信范围越大 导致实际风险与经验风险的差别越大 结论 要想使实际风