第04讲-智能决策理论与方法-1(1)解析.ppt

决策理论与方法 4 智能决策理论与方法 1 合肥工业大学管理学院2020年4月21日 2020年4月21日8时21分 决策理论与方法 智能决策理论与方法 不确定性决策 不确定性决策 指难以获得各种状态发生的概率 甚至对未来状态都难以把握的决策问题 特点 状态的不确定性 不确定性 不确定性来自人类的主观认识与客观实际之间存在的差异 事物发生的随机性 人类知识的不完全 不可靠 不精确和不一致以及自然语言中存在的模糊性和歧义性 都反映了这种差异 都会带来不确定性 不确定性就造成了具有相同描述信息的对象可能属于不同概念 解决问题的主要理论方法 人工智能与不确定性理论 2020年4月21日8时21分 决策理论与方法 智能决策理论与方法 智能决策理论与方法 1 智能决策理论的形成背景2 知识发现3 机器学习4 不确定性理论 2020年4月21日8时21分 决策理论与方法 智能决策理论与方法 智能决策理论与方法 形成背景 人类面临越来越复杂的决策任务和决策环境 决策问题所涉及的变量规模越来越大 决策所依赖的信息具有不完备性 模糊性 不确定性等特点 使得决策问题难以全部定量化地表示出来 某些决策问题及其目标可能是模糊的 不确定的 使得决策者对自己的偏好难以明确 随着决策分析的深入 对决策问题的认知加深 自己原有的偏好 倾向得到不断地修正 使得决策过程出现不断调整的情况 这时 传统的决策数学模型已经难以胜任求解复杂度过高的决策问题 含有不确定性的决策问题以及半结构化 非结构化的决策问题 因而产生了智能决策理论 方法及技术 2020年4月21日8时21分 决策理论与方法 智能决策理论与方法 智能决策理论与方法 AI的应用模式 智能决策方法是应用人工智能 ArtificialIntelligence AI 相关理论方法 融合传统的决策数学模型和方法而产生的具有智能化推理和求解的决策方法 其典型特征是能够在不确定 不完备 模糊的信息环境下 通过应用符号推理 定性推理等方法 对复杂决策问题进行建模 推理和求解 AI应用于决策科学主要有两种模式 针对可建立精确数学模型的决策问题 由于问题的复杂性 如组合爆炸 参数过多等而无法获得问题的解析解 需要借助AI中的智能搜索算法获得问题的数值解 针对无法建立精确数学模型的不确定性决策问题 半结构化或非结构化决策问题 需要借助AI方法建立相应的决策模型并获得问题的近似解 2020年4月21日8时21分 决策理论与方法 智能决策理论与方法 智能决策理论与方法 1 智能决策理论的形成背景2 知识发现3 机器学习4 不确定性理论 2020年4月21日8时21分 决策理论与方法 智能决策理论与方法 知识发现 动机 智能决策的核心是如何获取支持决策的信息和知识 问题知识获取是基于知识的系统 KBS 的最大瓶颈 2020年4月21日8时21分 决策理论与方法 智能决策理论与方法 知识发现 动机 问题推理规则的获取与KBS中知识获取一样难 因而基于案例推理 Case BasedReasoning 渐渐变成基于案例检索 Case BasedRetrieving 2020年4月21日8时21分 决策理论与方法 智能决策理论与方法 知识发现 动机 问题数据分析师与决策者之间对问题的理解存在偏差缺少有创造性的决策建议技术问题 如查询效率 RDBMS 2020年4月21日8时21分 决策理论与方法 智能决策理论与方法 知识发现 动机 优点知识独立于问题本身知识的获取主要通过数据挖掘实现有创造性收获 2020年4月21日8时21分 决策理论与方法 智能决策理论与方法 知识发现 动机 KDD带来的新问题知识发现问题 如何从数据中将知识挖掘出来 面临许多技术问题 如数据异构问题 数据具有噪音且信息不完整 使用什么样的挖掘算法 知识如何表示等知识评价问题 数据本身具有权威性 客观性 但知识不具备 知识如何评价 2020年4月21日8时21分 决策理论与方法 智能决策理论与方法 知识发现 基本概念 知识发现 KnowledgeDiscoveryinDatabases KDD 从大量数据中提取隐含的 预先未知 新颖 有潜在应用价值的 可信 有效 并最终能被人理解的模式的非平凡过程 也称为数据挖掘 DataMining 此过程主要包含三个阶段 数据准备阶段 数据挖掘阶段 解释评价阶段 2020年4月21日8时21分 决策理论与方法 智能决策理论与方法 知识发现 基本概念 数据准备阶段一般包含数据选取 预处理和数据变换等任务 数据选取 根据用户的需要从原始数据集中抽取一组样本数据确定挖掘任务的操作对象 常见数据源 关系型数据库数据 如营销数据库文本数据 内容挖掘 如Web内容挖掘 寻找相似页面 Web数据 站点结构数据 如Web结构挖掘 优化站点设计 站点导航 自适应站点 站点使用数据或点击流数据 如Web使用挖掘 用户聚类 页面聚类 个性化推荐等 空间数据 图像数据 视频数据等 2020年4月21日8时21分 决策理论与方法 智能决策理论与方法 知识发现 基本概念 数据预处理 噪音数据处理 空值处理 属性类型转化噪音数据处理 噪音数据往往是因输入错误而导致的 或受某种外界因素干扰而有意识提供的错误数据 如何剔除噪音数据 噪音数据与系统中的一些小概率数据统称为 异常数据 Outlier 如何区分噪音数据和小概率数据 空值处理 有些数据由于 不重要 不知道或 不愿意 而没有获得 引起某些属性值未知 称此类值为空值 如何处理这些缺失值 属性类型转化 连续属性离散化或将离散属性拟合成连续属性等 2020年4月21日8时21分 决策理论与方法 智能决策理论与方法 知识发现 基本概念 数据变换 数据约简 通过某种方法降低算法的搜索空间 垂直约简 也称特征选择 属性约简 使用降维或变换方法减少变量数目 是典型的组合优化问题 水平约简是通过对对象的分析 包括离散化 泛化等 合并具有相同属性值的对象 减少对象数目 2020年4月21日8时21分 决策理论与方法 智能决策理论与方法 知识发现 基本概念 数据挖掘阶段 应用相关算法从准备好的数据中寻找数据中隐含的对信息利用如预测 决策等有价值的模式 需要考虑的问题 任务的确定 分类 聚类 关联规则发现等 方法的选择 统计方法 机器学习方法 不确定性方法 数据库技术等 是知识发现的核心 也是被研究最广泛的内容 数据挖掘方法很多 需要我们对它们的适用条件 前提假设有充分的了解 运行效率分析 不同的算法其效率存在很大差异 算法设计与选择往往就是精度与效率之间的权衡 2020年4月21日8时21分 决策理论与方法 智能决策理论与方法 知识发现 基本概念 数据挖掘任务及常采用的方法 归纳总结 从泛化的角度总结数据 即从低层次数据抽象出高层次的描述的过程 主要方法 归纳学习 发现关联规则 关联规则的形式为A B A为前件 B为后件 Day Friday and Product Nappies Product Beer 为一典型关联规则A为满足前件的对象集 B为满足后件的对象 N为全部对象集 典型方法 Apriori算法 2020年4月21日8时21分 决策理论与方法 智能决策理论与方法 知识发现 基本概念 分类 等价关系 判别 按类标签 为数据库中的某属性集 一般仅包含一个属性 对数据库中的对象进行分类 具有相同标签值或标签值在指定区间内的对象属于同类 分类规则是判断某个对象属于某类的充分条件即对象具有某类的属性时则表示该对象属于该类 其规则形式一般为IFLogicExpThenA类ElseB类 主要方法 逻辑回归 判别分析 决策树 ANN 粗糙集 SVM等 聚类 相容关系 聚类也叫分段 就是将数据库中的实体分成若干组或簇 每簇内的实体是相似的 规则形式为IFO1与O2相似ThenO1 O2在同一簇 对象相似的判断方法有多种如距离法 典型方法 K means 2020年4月21日8时21分 决策理论与方法 智能决策理论与方法 知识发现 基本概念 发现特征规则 特征规则是刻划某个概念的特征的断言 它相当于分类规则的逆命题 例如病症是某种疾病的特征 规则一般形式是 IFA类Then特征表达式 序列模式发现 它与关联规则相似 不同之处在于事件的发生有前后顺序 该规则一般形式为 At i Bt j 其中t i t j 例如序贯规则JacketandTie Shoes表示客户在买了 夹克 和 领带 之后就会买 鞋 2020年4月21日8时21分 决策理论与方法 智能决策理论与方法 知识发现 基本概念 偏离探测 探测测量值与期望值之间的差别并对其进行解释 常有三种偏离类型 随时间偏离 以历史值为期望值 与标准偏离 以标准值为期望值 与预测偏离 以预测值为期望值 回归 根据历史数据拟合一函数将属性集映射到相应的值集 回归可以看作一种分类 区别是分类的类标签值是离散的 而回归是连续的 2020年4月21日8时21分 决策理论与方法 智能决策理论与方法 知识发现 基本概念 2020年4月21日8时21分 决策理论与方法 智能决策理论与方法 知识发现 基本概念 数据挖掘方法 2020年4月21日8时21分 决策理论与方法 智能决策理论与方法 知识发现 基本概念 解释与评价阶段 结果筛选 过滤 移去 不感兴趣的或显而易见的模式 利用描述规则特征的数值如信度 支持度或兴趣度等 定义某个阈值 对规则进行筛选 指定语义约束 规则的前件或后件只包含感兴趣的属性 或者指定属性间的依赖性约束 完全依靠用户对处理结果进行筛选 2020年4月21日8时21分 决策理论与方法 智能决策理论与方法 知识发现 基本概念 结果评价 确定所发现模式的可信度 基本方法是将样本数据集分成二部分 一部分是训练集用来发现模式 另一部分是测试集 分析结果的可信度 处理结果维护 信息处理所涉及的样本数据集常常是动态变化的 因此需要对所处理的结果进行维护以保证结果与数据的变化相一致 维护可以对数据变化引起的特殊问题重新应用所建立的处理方法 或者应用某种增量处理算法 2020年4月21日8时21分 决策理论与方法 智能决策理论与方法 知识发现 空值估算 空值是指属性值未知且不可用 与其它任何值都不相同的符号 在样本数据集中 空值在所有非主码属性中都可能出现 空值出现的主要原因 在信息收集时忽略了一些认为不重要的数据或信息提供者不愿意提供 而这些数据对以后的信息处理可能是有用的 某些属性值未知 数据模型的限制 2020年4月21日8时21分 决策理论与方法 智能决策理论与方法 知识发现 空值估算 空值处理的常用方法 从训练集中移去含未知值的实例 用某个最可能的值进行替换 基于样本中其它属性的取值和分类信息 构造规则来预测丢失的数据 并用预测结果 填补 丢失值 应用贝叶斯公式确定未知值的概率分布 选择一最可能的值填补空值或根据概率分布用不同值填补空值形成多个对象 将含有未知值的一个给定样本数据集转换成一个新的 可能不相容的但每个属性值均已知的数据集 方法是将某个属性的未知值用所有该属性的可能值替换形成多个数据集 2020年4月21日8时21分 决策理论与方法 智能决策理论与方法 知识发现 空值估算 基于对象相似的空值估算方法 定义对于任意对象 属性子集 称为对象x的B相关属性集 称为x关于B的特征值组 2020年4月21日8时21分 决策理论与方法 智能决策理论与方法 知识发现 空值估算 定义设为非空属性子集 SB是U上的二元关系 对于任意及 有则称SB是U上的相似关系 定义对于数据集及任意对象 若 则称x与y相容 所有与x相容的对象集称为相容类 记为SB x 2020年4月21日8时21分 决策理论与方法 智能决策理论与方法 知识发现 空值估算 2020年4月21日8时21分 决策理论与方法 智能决策理论与方法 知识发现 空值估算 从以上分析可以看出 SB关系是关于属性集B等价关系 即对于任意两个对象 x y关于B等价当且仅当对于任意属性 有 的一种推广即x与y关于B描述相同当且仅当且 2020年4月21日8时21分 决策理论与方法 智能决策理论与方法 知识发现 空值估算 缺失值填补的一般性陈述 对于任意对象 其属性a的可能值记为v x a 则 缺失值填补算法 输入 含有缺失值的数据集输出 填补缺失值后的数据集 输入数据集 2020年4月21日8时21分 决策理论与方法 智能决策理论与方法 知识发现 空值估算 对于每个对象x计算其相容类SB x 对于每个属性a A 每个对象x U 计算v x a IF v x a 1THENELSE IF v x a 1THENELSE 2020年4月21日8时21分 决策理论与方法 智能决策理论与方法 知识发现 空值估算 若数据集内容不再变化至 否则返回 若数据集中存在a x 则用投票策略确定a x 否则退出 该方法既没有将含空值的对象移去 也没有形成多个数据集 与统计方法相比充分考虑了数据之间的相容性和属性之间的依赖关系 2020年4月21日8时21分 决策理论与方法 智能决策理论与方法 知识发现 连续属性离散化 问题描述设为一样本数据集 为非空有限集合 C是条件属性集 D是决策属性集 假设对于任意有 R是实数集 则为连续属性 设是上的分割点集合 记为其中 为一整数 表示离散化程度 可以看作按属性将论域中的对象分成类 2020年4月21日8时21分 决策理论与方法 智能决策理论与方法 知识发现 连续属性离散化 对于需要离散化的连续属性集 其分割点集合记为将ci属性的连续取值映射到离散空间 即对于任意若其属性ci的取值在区间内 则将属性值重新标记为j 这样就把原来含有连续属性的样本数据集A转换成离散化的数据集 因此离散化问题本质上可归结为利用选取的分割点对属性的值域空间进行划分的问题 2020年4月21日8时21分 决策理论与方法 智能决策理论与方法 知识发现 连续属性离散化 离散化方法典型的有等区间方法 等信息量方法 基于信息熵的方法 Holte的1R离散化方法 统计试验方法 超平面搜索方法以及用户自定义区间等 应用不同的准则可将现有的离散化方法分为局部与全局方法 论域空间 静态与动态方法 属性空间 和有导师与无导师方法 是否依赖决策属性 1 等区间离散化方法等区间分割是将连续属性的值域等分成 个区间 一般由用户确定 2020年4月21日8时21分 决策理论与方法 智能决策理论与方法 知识发现 连续属性离散化 假设某个属性的最大属性值为xmax 最小属性值为xmin 用户给定的分割点参数为k 则分割点间隔为 xmax xmin k 所得到的属性分割点为xmin i i 1 2 k 2 等信息量离散化方法等信息量分割首先将测量值进行排序 然后将属性值域分成k个区间 每个区间包含相同数量的测量值 假设某个属性的最大属性值为xmax 最小属性值为xmin 用户给定的分割点参数为k 样本集中的对象个数为n 则需要将样本集中的对象按该属性的取值从小到大排列 然后按对象数平均划分为k段即得到分割点集 每两个相邻分割点之间的对象数均为n k 2020年4月21日8时21分 决策理论与方法 智能决策理论与方法 知识发现 连续属性离散化 3 统计试验方法统计试验方法根据决策属性分析区间划分之间的独立程度 确定分割点的有效性 对于任意分割点 均可将分成2个区间和 两区间的独立程度为 其中 r是决策类数目nij是在第l区间中属于第j决策类的对象数 2020年4月21日8时21分 决策理论与方法 智能决策理论与方法 知识发现 连续属性离散化 若 则取基于统计试验的离散化方法是将值较大的分割点作为有效分割点 2020年4月21日8时21分 决策理论与方法 智能决策理论与方法 知识发现 关联规则发现 Apriori算法 TheApriorimethod ProposedbyAgrawal Srikant1994Asimilarlevel wisealgorithmbyMannilaetal 1994Majoridea AsubsetofafrequentitemsetmustbefrequentE g if beer diaper nuts isfrequent beer diaper mustbe Anyoneisinfrequent itssupersetcannotbe Apowerful scalablecandidatesetpruningtechnique Itreducescandidatek itemsetsdramatically fork 2 2020年4月21日8时21分 决策理论与方法 智能决策理论与方法 知识发现 关联规则发现 Apriori算法 关联规则的例子 ForruleA C support support A C 50 confidence support A C support A 66 6 TheAprioriprinciple Anysubsetofafrequentitemsetmustbefrequent Min support50 Min confidence50 2020年4月21日8时21分 决策理论与方法 智能决策理论与方法 知识发现 关联规则发现 Apriori算法 ProcedureFindthefrequentitemsets thesetsofitemsthathaveminimumsupport Apriori Asubsetofafrequentitemsetmustalsobeafrequentitemset i e if A B isafrequentitemset both A and B shouldbeafrequentitemsetIterativelyfindfrequentitemsetswithcardinalityfrom1tok k itemset Usethefrequentitemsetstogenerateassociationrules 2020年4月21日8时21分 决策理论与方法 智能决策理论与方法 知识发现 关联规则发现 Apriori算法 AlgorithmJoinStepCkisgeneratedbyjoiningLk 1withitselfPruneStepAny k 1 itemsetthatisnotfrequentcannotbeasubsetofafrequentk itemset henceshouldberemoved Ck Candidateitemsetofsizek Lk frequentitemsetofsizek 2020年4月21日8时21分 决策理论与方法 智能决策理论与方法 知识发现 关联规则发现 Apriori算法 Pseudocode 正式代码见附件1 Ck CandidateitemsetofsizekLk frequentitemsetofsizekL1 frequentitems for k 1 Lk k dobeginCk 1 candidatesgeneratedfromLk foreachtransactiontindatabasedoincrementthecountofallcandidatesinCk 1thatarecontainedintLk 1 candidatesinCk 1withmin supportendreturn kLk 2020年4月21日8时21分 决策理论与方法 智能决策理论与方法 知识发现 关联规则发现 Apriori算法 2020年4月21日8时21分 决策理论与方法 智能决策理论与方法 知识发现 聚类 K means算法 聚类分析是把研究对象按照一定的规则分成若干类别 并使类之间的差别尽可能地大 类内的差别尽可能地小 换句话说 使类间的相似性最小 而类内的相似性最大 聚类方法的核心问题是样品间的相似性度量 通常用距离来度量 2020年4月21日8时21分 决策理论与方法 智能决策理论与方法 知识发现 聚类 K means算法 聚类分析中的常用距离 1 欧氏 Euclidean 距离 2 绝对距离 3