最新第五章机器学习

第五章机器学习 一 概述二 主要策略与基本结构三 常用的学习方法四 数据挖掘和知识发现方法五 数据挖掘开发工具简介 当前人工智能和神经计算的核心研究课题之一 教学要求 了解机器学习的定义 发展史及意义 理解掌握机器学习的基本结构 理解常用机器学习的方法原理 初步了解数据挖掘及知识发现的知识 第五章机器学习 一 概述定义 发展史 意义等二 主要策略与基本结构三 常用的学习方法四 数据挖掘和知识发现方法五 数据挖掘开发工具简介 1机器学习的定义 什么是机器学习 Simon 1983 学习就是系统中的变化 这种变化使系统比以前更有效地去做同样的工作 Minsky 1985 学习是在我们头脑中 心里 进行有用的变化 学习是一种具有多侧面的现象 学习的过程有 获取新的陈述性知识 通过教育或实践发展机械技能和认知能力 将新知识组织成为通用化和有效的表达形式 借助观察和实验发现新的事实和新的理论 基本形式知识获取和技能求精 学习的本质就是获取新的知识 包括物理系统和行为的描述和建模 构造客观现实的表示 知识获取 通过实践逐渐改造机制和认知技能 例 骑自行车 这些技能包括意识的或机制的协调 这种改进又是通过反复实践和从失败的行为中纠正偏差来进行的 技能求精 知识获取的本质可能是一个自觉的过程 其结果是产生新的符号知识结构和智力模型 技能求精是下意识地借助于反复地实践来实现的 机器学习是研究计算机怎样模拟或实现人类的学习行为 以获取新的知识或技能 重新组织已有的知识结构使之不断改善自身的性能 2为什么要研究机器学习 人工智能主要是为了研究人的智能 模仿其机理将其应用于工程的科学 在这个过程中必然会问道 人类怎样做才能获取这种特殊技能 或知识 例子 机器人跳舞机器人演奏 现在的人工智能系统还完全没有或仅有很有限的学习能力 系统中的知识由人工编程送入系统 知识中的错误也不能自动改正 也就是说 现有的大多数人工智能是演绎的 没有归纳推理 因而不能自动获取和生成知识 未来的计算机将有自动获取知识的能力 它们直接由书本学习 通过与人谈话学习 通过观察学习 它们通过实践自我完善 克服人的存储少 效率低 注意力分散 难以传送所获取的知识等局限性 一台计算机获取的知识很容易复制给任何其它机器 机器学习在AI研究中是较为年轻的分支 发展过程大体可分为4个时期 第一阶段50年代中到60年代中期 热烈时期 3机器学习的发展史 第二阶段从60年代中至70年代中期 机器学习的冷静时期 第三阶段从70年代中至80年代中期 复兴时期 机器学习的最新阶段始于1986年 机器学习已成为新的边缘学科并在高校形成一门课程 结合各种学习方法 取长补短的多种形式的集成学习系统研究正在兴起 各种学习方法的应用范围不断扩大 一部分已形成商品 归纳学习的知识获取工具已在诊断分类型专家系统中广泛使用 与机器学习有关的学术活动空前活跃 国际上除每年一次的机器学习研讨会外 还有计算机学习理论会议以及遗传算法会议 男 1973年11月生 分别于1996年6月 1998年6月和2000年12月于南京大学计算机科学与技术系获学士 硕士和博士学位 2001年1月起留校任教 2002年3月破格晋升副教授 2003年11月被聘任为教授 2004年4月获博士生导师资格 现任人工智能教研室主任 机器学习与数据挖掘研究组负责人 南京航天航空大学兼职教授 澳大利亚Deakin大学名誉研究员 复旦大学智能信息处理重点实验室学术委员会委员 第五章机器学习 一 概述二 主要策略与基本结构三 常用的学习方法四 数据挖掘和知识发现方法五 数据挖掘开发工具简介 学习是一项复杂的智能活动 学习过程与推理过程是紧密相连的 按照学习中使用推理的多少 机器学习所采用的策略大体上可分为4种 机械学习通过传授学习类比学习通过事例学习 1机器学习的主要策略 其它策略见 机器学习策略综述 一文 2机器学习的基本结构 图1学习系统的基本结构 环境向系统的学习环节提供某些信息 学习环节利用这些信息修改知识库 以增进系统执行部分完成任务的效能 执行环节利用知识库中的知识完成某种任务 同时把获得的信息反馈给学习环节 在具体的应用中 环境 知识库和执行部分决定了具体的工作内容 学习部分所需要解决的问题完全由上述3部分确定 下面我们分别叙述这3部分对设计学习系统的影响 影响学习系统设计的最重要的因素是环境向系统提供的信息质量 如果信息的质量比较高 与一般原则的差别比较小 则学习部分比较容易处理 如果向学习系统提供的是杂乱无章的指导执行具体动作的具体信息 则学习系统需要在获得足够数据之后 删除不必要的细节 进行总结推广 形成指导动作的一般原则 放入知识库 知识库是影响学习系统设计的第二个因素 知识的表示有多种形式 比如特征向量 一阶逻辑语句 产生式规则 语义网络和框架等等 这些表示方式各有其特点 在选择表示方式时要兼顾以下4个方面 1 表达能力强 2 易于推理 3 容易修改知识库 4 知识表示易于扩展 执行部分是整个学习系统的核心 因为执行部分的动作就是学习部分力求改进的动作 同执行部分有关的问题有3个 复杂性 反馈和透明性 第五章机器学习 一 概述二 主要策略与基本结构三 常用的学习方法四 数据挖掘和知识发现方法五 数据挖掘开发工具简介 1 学习模式机械学习是最简单的机器学习方法 记忆 即把新的知识存储起来 供需要时检索调用 而不需要计算和推理 机械学习是最基本的学习过程 因为任何学习系统都必须记住它们获取的知识 在机械学习系统中 知识的获取是以较为稳定和直接的方式进行的 不需要系统进行过多的加工 3 1机械学习 当系统的执行部分解决好问题之后 系统就记住该问题及其解 这样 可把学习系统的执行部分抽象地看成某个函数 该函数在得到自变量输入值 X1 X2 Xn 之后 计算并输出函数值 Y1 Y2 Yp 机械学习在存储器中简单地记忆存储对 X1 X2 Xn Y1 Y2 Yp 当需要f X1 X2 Xn 时 执行部分就从存储器中把 Y1 Y2 Yp 简单地检索出来而不是重新计算它 其学习模式如下 一个决定受损汽车修理费用的汽车保险程序 这个程序的输入是被损坏的汽车的描述 包括制造厂家 生产年代 汽车的种类以及记录汽车被损坏部位和损坏程度的一个表 程序的输出是保险公司应付的修理费用 这个系统是个机械记忆系统 为了估算损坏汽车的修理费用 程序系统必须在存储器中查找同一厂家 同一生产年代 损坏的部位和程度相同的汽车 然后把对应的费用提交给用户 如果系统没有发现这样的汽车 则它使用保险公司公布的赔偿规则估算出一个修理费用 然后把厂家 生产日期和损坏情况等特征与估算出的费用保存起来 以便将来查找使用 2存在的主要问题对于机械学习 需要注意3个重要的问题 存储组织 稳定性和存储与计算之间的权衡 a 存储组织信息 显然 只有当检索一个项目的时间比重新计算一个项目的时间短时 机械学习才有意义 检索的越快 其意义也就越大 因此 采用适当的存储方式 使检索速度尽可能地快 是机械学习中的重要问题 在数据结构与数据库领域 为提高检索速度 人们研究了许多数据存储方式 如索引 排序 杂凑等等 在机械学习中我们可以充分利用这些成果来实现我们的要求 b 环境的稳定性与存储信息的适用性问题 在急剧变化的环境下机械学习策略是不适用的 做为机械学习基础的一个重要假定是在某一时刻存储的信息必须适用于后来的情况 然而如果信息变换得特别频繁 这个假定就被破坏了 例如在保险公司的确定被损坏汽车的修理费用的程序中 50年代收集保存的有关汽车特征和修理费用的情况 90年代就很少适用了 因为50年代生产汽车的厂家和所产汽车的牌号在90年代已经有很多不存在了 由于通货膨胀和货币贬值 所要查询的修理费用也不适用了 因此机械学习系统必须保证所保存的信息适应于外界环境变化的需要 这也就是所谓的信息适用性问题 c 存储与计算之间的权衡 因为机械学习的根本目的是改进系统的执行能力 因此对于机械学习来说很重要的一点是它不能降低系统的效率 比方说 如果检索一个数据比重新计算一个数据所花的时间还要多 那么机械学习就失去了意义 通过总结工作和训练经验进行学习 是学习的一个好方法 本节通过对一个检查莎士比亚剧本精确性的过程 用解释学习来说明该学习方法 通过该过程可看到使用解释能了解事情的因果关系 3 2基于解释的学习 如同教师向学生提供先例 让学生练习 并期望学生在练习后能够发现一般原理一样 让机器设法找出先例与练习间的因果关系 并应用先例去处理练习 把工作上升为原理 然后把这些原理存储起来供需要时检索调用 例 一个关于Greed 贪婪 的练习 这是关于一位软弱贵族与一位贪婪女人的练习 该贵族与该女人结了婚 解释一下为什么这位贵族很可能想当国王 机器解释学习的基本原理 贪婪女人 1 已知一些事实如下 2 解释转换运用类比解题建造一个解释样板 用于考虑例中的因果链以及所有与该因果链紧接的链 可解释有关结婚 贪婪 软弱等链如何导致麦克佩斯想当国王的链 本练习中的贵族是软弱的 而他的妻子是贪婪的 具体例中 麦克佩斯软弱 而他的妻子麦克佩斯夫人很贪婪 考虑到这些特性 我们假定 两个类比状态中原因间的相似导致它们结果的相似 3 具体化链 一个被上升的具体化链如图 a 所示 其简化表示如图 b 所示 谋杀事件的具体化链表示 下面建立基于解释的学习 并从中学习新规则 4 使用语义框架具体化链 使用合适描述予以表达人物特性 其动机以及随之发生的行动 例如 麦克佩斯和邓肯可由节点来说明 两节点间用谋杀链连接 如图 a 所示 谋杀 5 使用语义网对具体化链进一步的解释 这里对谋杀可用更多的说明 因为麦克佩斯用到一把刀 故可把谋杀当作一个概念节点 并与它的一些描述链相连 如图 b 所示 1 归纳学习系统的模型可把归纳学习形式化地描述为使用训练实例 从而导出一般规则的搜索问题 全体可能的实例构成实例空间 全体可能的一般规则构成规则空间 归纳的过程就是完成实例空间与规则空间之间协调的搜索比较过程 归纳学习的 双空间 模型可表示为下图的形式 3 3归纳学习 2 归纳学习系统的执行过程 归纳学习系统的执行过程可大致描述为 根据规则空间提供的一般规则 由实验规划过程通过对实例空间的搜索 完成实例选择 并将选中的活跃实例提交解释过程 解释过程对实例经过适当的转换 将活跃实例变换为规则空间中的特定概念 以引导对规则空间的搜索 3 归纳学习方法 一般归纳学习包括示例学习和发现学习两类 1 示例学习 又称实例学习 它通过环境取得的若干实例中 包括从相关的正例和反例中归纳出一般性概念或规则的方法 2 发现学习往往来自于观察学习过程 观察取自于有关环境的大量数据 实例以及经验数据的了解与分析 发现即经过搜索而归纳出规则 这是一种没有教师指导的归纳学习 其学习形式包括概念聚类 结构分类 数据拟合 发现自然定律以至建立系统行为的理论 1 示例概念学习 针对产生概念的正例集合与反例集合 由归纳推理 得出覆盖所有正例并排除所有反例的概念描述 并可用规则形式或决策树的方法来表示这种概念的描述 例如 要让示例学习系统学到关于虎的概念 可以先提供给程序以各种动物 并告知程序哪些动物是虎 哪些不是虎 系统学习后便概括出虎的概念模型和类型定义 利用这个类型定义 就可作为动物世界中识别虎的分类准则 这种构造类型定义的学习 又称为概念学习 示例归纳学习 2 示例归纳学习举例 示例学习不仅可以学习概念 也可获得规则 因此 示例学习又可以看作是实例空间和规则空间相互作用的过程 例如 给出肺炎与肺结核两种病的一些病例 构成实例空间 每个病例都含有五种症状 发烧 无 低 高 咳嗽 轻度 中度 剧烈 X光所见阴影 点状 索条状 片状 空洞 血沉 正常 快 听诊 正常 干鸣音 水泡音 肺炎和肺结核的部分病例集见下表 表肺病实例集 血沉是指在一定条件下 人体血液内红细胞沉降的速度 通过上述示例学习得到如下诊断规则 血沉 正常 听诊 干鸣音 水泡音 诊断 肺炎 血沉 快 诊断 肺结核于是从病例中归纳 产生了诊断规则 即实现了实例空间到规则空间的作用过程 1 发现和观察学习过程 这类代表性系统如AM系统 1977年 BACON系统等 这类系统有时不仅能发现人们所知而未见的规律或规则 甚至能发现客观事物中被人们忽略的新概念 例如 利用BACON实验数据分析的学习系统 人们不仅发现了欧姆定律 牛顿万有引力定律 开普勒行星运动定律等 还发现一些早期化学家发现的定理 如普罗斯特定律 吕萨克定律等 发现和观察学习 2 发现和观察学习举例 例如 利用BACON实验数据分析的学习系统 其思想是利用一些算子反复构造一些新的项 当这些项中有一个是常数时 就得到概念 项 常数 的规律 例如 对开普勒定律 行星绕太阳运动周期为p与行星到太阳的距离d有关 即有公式 R d3 p2其中R为常数 计算过程如下表所示 由上表 对开普勒定律公式R d3 p2发现过程为 p和d都是递增 并且非线性互相依赖 触发建立新项d p的算子 d和d p的递增方向刚好相反 触发建立新项 d p d d2 p的算子 d p和d2 p的递增方向刚好相反 触发建立新项 d p d2 p d3 p2的算子 项d3 p2是常数 则得到行星运动定律 行星运动定律的发现 第五章机器学习 一 概述二 主要策略与基本结构三 常用的学习方法四 知识发现和数据挖掘五 数据挖掘开发工具简介 Motivation Whydatamining 动机 背景 发生在数据库上的 成长的烦恼 数据库的发展给自己引出了麻烦 数据爆增103T没有数据时千方百计搜集管理数据 上世纪60 70年代层次库 网状库 有了数据扩充能力 搜集管理更多数据 上世纪80 90年代关系库 OODB 数据太多了 管不下来 上世纪 90年代 现在KDD DM 作科研找项目也类似 WeareDataRichbutInformationPoor Databasesaretoobig Terrorbytes 2020 4 13 54 一 提出1989年8月 在美国底特律召开的第11届国际AI会议专题讨论会上 知识发现概念被首次提出 数据挖掘概念 又称数据开采或数据采掘 于1995年在加拿大召开的第一届KDD和DM国际学术会议上被提出 知识发现和数据挖掘是人工智能 机器学习与数据库技术相结合的产物 目前 国内外学术界和企业界 都十分重视对它们的研究与开发 知识发现 尿布和啤酒故事 美国一家大型超市 经过计算机对商场以往销售记录数据的分析 归纳 整理 运算后发现了这样一条规律 在超市中购买尿布的多为青年男性 他们往往在购买尿布之后还要顺手买上一听啤酒 于是超市便改变了以往婴儿用品区域与啤酒类商品区域 相隔千里 的布局 将二者相邻而置 结果两种商品的销量都立竿见影地大幅度上升 这是数据挖掘运用于现实生活中的最为简单的一个事例 人们给KDD下过很多定义 内涵也各不相同 目前公认的定义是由Fayyad等人提出的 所谓基于数据库的知识发现 KDD 是指从大量数据中提取有效的 新颖的 潜在有用的 最终可被理解的模式的高级处理过程 二 KDD定义 三 KDD的处理过程 知识发现大致分为3部分 数据准备 数据挖掘 结果解释和评价 1 数据准备 所谓数据准备 则又包含三个子过程 它们是数据选择 数据预处理和数据变换 数据选择 目的是确定与任务相关目标数据 根据用户需要 从原始数据库中抽取一组有用的数据 数据预处理 包括消除噪声 推导计算并补充缺值数据 消除重复记录 完成数据类型转换等 例如 把连续值数据转换为离散型的数据 以便于符号归纳 或是把离散型的转换为连续值型的 以便于神经网络归纳等 数据变换 目的在于消减数据维数 即从初始特征中找出真正有用的特征 减少特征变量个数 2 数据挖掘 首先要确定挖掘的任务或目的是什么 如数据总结 分类 聚类 关联规则发现或序列模式发现等 然后 决定采用什么样的挖掘算法 为了提高挖掘效率 一要针对数据类型不同的特点 二要针对用户或实际运行系统的要求来选用相关合适的算法来开采 例如 有的用户可能希望获取描述型的 容易理解的知识 而有的用户或系统的目的要求获取预测准确度 需要尽可能高的预测型知识 完成系统分析和这些准备工作后 就可实施数据挖掘操作了 3 结果解释和评价 数据挖掘出来的模式 经过用户或机器的评价 可能存在冗余或无关的模式 这时就需要将其剔除 也有可能得到的模式不满足用户要求 这时则需要系统退回到发现过程之前 重新选择数据 采用新的数据变换方法 设定新的参数值 甚至换一种开采算法 一 定义数据挖掘定义由W J Frawley G Piatetsky等提出 从大量数据中开采出隐含的 事先未知的 对决策有潜在价值的知识与规则 这些规则蕴含了数据库中一组对象之间的特定关系 揭示出一些有用的信息和知识 这些信息和知识可表示为相关的概念 规则 规律和模式 从而为系统决策 策划提供知识依据 数据挖掘 2 数据挖掘内容采用DM 能够发现下列各种知识 广义型知识 反映同类事物共同性质的知识 特征型知识 反映事物各方面的特征知识 差异型知识 反映不同事物之间属性差别的知识 关联型知识 反映事物之间关联或依赖的知识 预测型知识 根据历史和当前的数据推测未来数据 偏离型知识 揭示事物偏离常规的异常现象 3 数据挖掘系统基本结构数据挖掘是从大型数据库提取知识 并表示为概念 规则 规律 模式等形式 典型的数据挖掘系统结构如下图所示 4 数据挖掘系统基本过程可分为数据集成 数据选择 数据预处理等步骤 数据集成 将多文件或多数据库运行环境中的数据进行合并处理 解决语义模糊性 处理数据中的遗漏 清洗脏数据等 数据选择 目的在于辨别出需要分析的数据集合 缩小处理范围 提高DM的质量 预处理 为了克服目前DM工具的局限性 主要是通过净化 转换 群聚 分类等手段降低数据的复杂性 并且重新加以组织 其次 研究开发一种或多种DM工具 如IBM的IDM和SGI的MineSet等 最后 用DM工具来发现未知的知识 并运用知识作为决策支持 达到预定目标 5 数据挖掘的任务按照数据挖掘技术所能够发现的规则 将常见的数据挖掘任务分为七种类型 特征规则 特征规则是把由所有数据满足的概念特征化 特征规则挖掘能够总结并发现由用户指定的数据集的一般特征 如特定疾病的症状等 辨识规则 发现一个数据集 目标类 与另一个数据集 对比类 区分开来的特性或性质 例如为把一种疾病与另一种疾病区分开 辨识规则总结区分这些疾病的症状 互联规则 描述对象集之间的关联关系 分类规则 把被分类数据映射到一组已知的类 例如 根据汽