第9章 机器学习与知识发现.ppt

2020 1 14 1 第四篇学习与发现 学习是系统积累经验或运用规律指导自己的行为或改进自身性能的过程 发现是系统从接收的信息中发现规律的过程 人工智能中的机器学习 machinelearning 主要指机器对自身行为的修正或性能的改善 类似于人类的技能训练和对环境的适应 和机器对客观规律的发现 类似与人类的科学发现 2020 1 14 2 机器学习主要分为符号学习连接学习统计学习机器对于客观规律的发现 也称为知识发现 KnowledgeDiscovery KD 数据挖掘 DataMining 是知识发现的一个重要研究和应用领域 目前的机器学习主要是机器的直接发现性学习 而间接性继承机器学习需要 理解 为基础 2020 1 14 3 第9章机器学习与知识发现9 1机器学习概述9 2符号学习9 3神经网络学习9 4知识发现与数据挖掘 2020 1 14 4 9 1机器学习概述 9 1 1机器学习的概念9 1 2机器学习的原理9 1 3机器学习的分类 2020 1 14 5 9 1 1机器学习的概念心理学中对学习的解释是 学习是指 人或动物 依靠经验的获得而使行为持久变化的过程 Simon认为 如果一个系统能够通过执行某种过程而改进它的性能 这就是学习 Minsky认为 学习是在人们头脑中 心理内部 进行有用的变化 TomM Mitchell在 机器学习 一书中对学习的定义是 对于某类任务T和性能度P 如果一个计算机程序在T上以P衡量的性能随着经验E而自我完善 那么 我们称这个计算机程序从经验E中学习 当前关于机器学习的许多文献中也大都认为 学习是系统积累经验以改善其自身性能的过程 2020 1 14 6 总之 学习与经验有关 学习可以改善系统性能 学习是一个有反馈的信息处理与控制过程 因为经验是在系统与环境的交互过程中产生的 而经验中应该包含系统输入 响应和效果等信息 因此经验的积累 性能的完善正是通过重复这一过程而实现的 2020 1 14 7 9 1 2机器学习的原理 图9 1机器学习原理1 记忆学习 基于范例的学习 希望能在积累的经验中发现规律 知识 然后利用知识来指导行为 经验积累过程缓慢经验不可靠 2020 1 14 8 2020 1 14 9 图9 2机器学习原理2 2020 1 14 10 图9 3机器学习原理3 2020 1 14 11 图9 4机器学习原理4 2020 1 14 12 图9 5机器学习原理5 2020 1 14 13 9 1 3机器学习的分类1 基于学习策略的分类 1 模拟人脑的机器学习 符号学习 模拟人脑的宏观心理级学习过程 以认知心理学原理为基础 以符号数据为输入 以符号运算为方法 用推理过程在图或状态空间中搜索 学习的目标为概念或规则等 符号学习的典型方法有 记忆学习 示例学习 演绎学习 类比学习 解释学习等 神经网络学习 或连接学习 模拟人脑的微观生理级学习过程 以脑和神经科学原理为基础 以人工神经网络为函数结构模型 以数值数据为输入 以数值运算为方法 用迭代过程在系数向量空间中搜索 学习的目标为函数 典型的连接学习有权值修正学习 拓扑结构学习 2020 1 14 14 2 直接采用数学方法的机器学习 主要有统计机器学习 贝叶斯学习 贝叶斯网络学习 几何分类学习 支持向量机SVM 2 基于学习方法的分类 1 归纳学习 符号归纳学习 典型的符号归纳学习有示例学习 决策树学习 函数归纳学习 发现学习 典型的函数归纳学习有神经网络学习 示例学习 发现学习 统计学习 2 演绎学习 3 类比学习 典型的类比学习有案例 范例 学习 4 分析学习 典型的分析学习有案例 范例 学习 解释学习 2020 1 14 15 3 基于学习方式的分类 1 有导师学习 监督学习 输入数据中有导师信号 以概率函数 代数函数或人工神经网络为基函数模型 采用迭代计算方法 学习结果为函数 2 无导师学习 非监督学习 输入数据中无导师信号 采用聚类方法 学习结果为类别 典型的无导师学习有发现学习 聚类 竞争学习等 3 强化学习 增强学习 以环境反馈 奖 惩信号 作为输入 以统计和动态规划技术为指导的一种学习方法 2020 1 14 16 4 基于数据形式的分类 1 结构化学习 以结构化数据为输入 以数值计算或符号推演为方法 典型的结构化学习有神经网络学习 统计学习 决策树学习 规则学习 2 非结构化学习 以非结构化数据为输入 典型的非结构化学习有类比学习 案例学习 解释学习 文本挖掘 图像挖掘 Web挖掘等 2020 1 14 17 5 基于学习目标的分类 1 概念学习 即学习的目标和结果为概念 或者说是为了获得概念的一种学习 典型的概念学习有示例学习 2 规则学习 即学习的目标和结果为规则 或者说是为了获得规则的一种学习 典型的规则学习有决策树学习 3 函数学习 即学习的目标和结果为规则 或者说是为了获得函数的一种学习 典型的函数学习有神经网络学习 4 类别学习 即学习的目标和结果为对象类 或者说是为了获得类别的一种学习 典型的类别学习有聚类分析 5 贝叶斯网络学习 即学习的目标和结果是贝叶斯网络 或者说是为了获得贝叶斯网络的一种学习 其又可分为结构学习和参数学习 2020 1 14 18 9 2符号学习 9 2 1记忆学习9 2 2示例学习9 2 3决策树学习9 2 4演绎学习9 2 5类比学习 2020 1 14 19 9 2 1记忆学习记忆学习又称死记硬背学习或机械学习 这种学习方法不要求系统具有对复杂问题求解的能力 也就是没有推理能力 系统的学习方法就是直接记录与问题有关的信息 然后检索并利用这些存储的信息来解决问题 A Av S 2020 1 14 20 记忆学习是基于记忆和检索的办法 学习方法简单 但学习系统需要几种能力 1 能实现有组织的存储信息 2 能进行信息综合 3 能控制检索方向 当存储对象愈多时 其中可能有多个对象与给定的状态有关 这样就要求程序能从有关的存储对象中进行选择 以便把注意力集中到有希望的方向上来 2020 1 14 21 9 2 2示例学习示例学习也称实例学习 它是一种归纳学习 示例学习是从若干实例 包括正例和反例 中归纳出一般概念或规则的学习方法 图9 6第一个拱桥的语义网络 图9 7第二个拱桥的语义网络 2020 1 14 22 图9 8学习程序归纳出的语义网络 图9 9拱桥概念的语义网络 2020 1 14 23 例9 1假设示例空间中有桥牌中 同花 概念的两个示例 示例1 花色 c1 梅花 花色 c2 梅花 花色 c3 梅花 花色 c4 梅花 同花 c1 c2 c3 c4 示例2 花色 c1 红桃 花色 c2 红桃 花色 c3 红桃 花色 c4 红桃 同花 c1 c2 c3 c4 关于同花的一般性规则 花色 c1 x 花色 c2 x 花色 c3 x 花色 c4 x 同花 c1 c2 c3 c4 2020 1 14 24 对于这个问题可采用通常的曲线拟合技术 归纳出规则 x y 2x 3y 1 即z 2x 3y 1 例9 2假设示例空间存放有如下的三个示例 示例1 0 2 7 示例2 6 1 10 示例3 1 5 10 这是三个3维向量 表示空间中的三个点 现要求求出过这三点的曲线 2020 1 14 25 9 2 3决策树学习1 什么是决策树2 怎样学习决策树3 ID3算法 2020 1 14 26 1 什么是决策树决策树 decisiontree 也称判定树 它是由对象的若干属性 属性值和有关决策组成的一棵树 其中的节点为属性 一般为语言变量 分枝 边 为相应的属性值 一般为语言值 从同一节点出发的各个分枝之间是逻辑 或 关系 根节点为对象的某一个属性 从根节点到每一个叶子节点的所有节点和边 按顺序串连成一条分枝路径 位于同一条分枝路径上的各个 属性 值 对之间是逻辑 与 关系 叶子节点为这个与关系的对应结果 即决策 2020 1 14 27 图9 10决策树示意图 规则 A a1且B b1则d1 2020 1 14 28 例9 3下图所示是机场指挥台关于飞机起飞的简单决策树 2020 1 14 29 例9 4下图是一个描述 兔子 概念的决策树 2020 1 14 30 2 怎样学习决策树决策树学习首先要有一个实例集 对实例集的要求 实例集中的实例都含有若干 属性 值 对和一个相应的决策 结论或结果 一个实例集中的实例要求是相容的 即相同的前提不能有不同的结论 对实例集中的结论不能完全相同也不能完全不同 否则该实例集无学习意义 2020 1 14 31 决策树学习的基本方法和步骤 首先 选取一个属性 按这个属性的不同取值对实例集进行分类 并以该属性作为根节点 以这个属性的诸取值作为根节点的分枝 进行画树 然后 考察所得的每一个子类 看其中的实例的结论是否完全相同 如果完全相同 则以这个相同的结论作为相应分枝路径末端的叶子节点 否则 选取一个非父节点的属性 按这个属性的不同取值对该子集进行分类 并以该属性作为节点 以这个属性的诸取值作为节点的分枝 继续进行画树 如此继续 直到所分的子集全都满足 实例结论完全相同 而得到所有的叶子节点为止 2020 1 14 32 决策树学习举例设表9 1所示的是某保险公司的汽车驾驶保险类别划分的部分事例 我们将这张表作为一个实例集 用决策树学习来归纳该保险公司的汽车驾驶保险类别划分规则 2020 1 14 33 表9 1汽车驾驶保险类别划分实例集 2020 1 14 34 将实例集简记为S 1 C 2 C 3 C 4 B 5 A 6 A 7 C 8 B 9 A 10 A 11 B 12 B 其中每个元组表示一个实例 前面的数字为实例序号 后面的字母为实例的决策项保险类别 用 小 中 大 分别代表 21 21且 25 25 这三个年龄段 2020 1 14 35 对于S 我们按属性 性别 的不同取值将其分类 由表9 1可见 这时S应被分类为两个子集 S1 3 C 4 B 7 C 8 B 11 B 12 B S2 1 C 2 C 5 A 6 A 9 A 10 A 于是 我们得到以性别作为根节点的部分决策树 见下图 2020 1 14 36 决策树生成过程 2020 1 14 37 决策树生成过程 2020 1 14 38 决策树生成过程 2020 1 14 39 最后生成的决策树 2020 1 14 40 由决策树所得的规则集 女性且年龄在25岁以上 则给予A类保险 女性且年龄在21岁到25岁之间 则给予A类保险 女性且年龄在21岁以下 则给予C类保险 男性且年龄在25岁以上 则给予B类保险 男性且年龄在21岁到25岁之间且未婚 则给予C类保险 男性且年龄在21岁到25岁之间且已婚 则给予B类保险 男性且年龄在21岁以下且未婚 则给予C类保险 男性且年龄在21岁以下且已婚 则给予B类保险 2020 1 14 41 3 ID3算法ID3算法是一个经典的决策树学习算法 由Quinlan于1979年提出 ID3算法的基本思想是 以信息熵为度量 用于决策树节点的属性选择 每次优先选取信息量最多的属性 亦即能使熵值变成最小的属性 以构造一棵熵值下降最快的决策树 到叶子节点处的熵值为0 此时 每个叶子节点对应的实例集中的实例属于同一类 2020 1 14 42 1 信息熵和条件熵设S是一个实例集 S也可以是子实例集 A为S中实例的一个属性 H S 和H S A 分别称为实例集S的信息熵和条件熵 其计算公式如下 其中 i i 1 2 n 为S中各实例所有可能的结论 lb即log2 其中 ak k 1 2 m 为属性A的取值 Sak为按属性A对实例集S进行分类时所得诸子类中与属性值ak对应的那个子类 2020 1 14 43 2 基于条件熵的属性选择 按性别划分 实例集S被分为两个子类 S男 3 C 4 B 7 C 8 B 11 B 12 B S女 1 C 2 C 5 A 6 A 9 A 10 A 从而 对子集S男而言 对子集S女而言 2020 1 14 44 于是 由公式 9 1 有 2020 1 14 45 又 2020 1 14 46 将以上3式代入公式 9 2 得 用同样的方法可求得 可见 条件熵H S 性别 为最小 所以 应取 性别 这一属性对实例集进行分类 即以 性别 作为决策树的根节点 2020 1 14 47 3 决策树学习的发展继ID3算法之后 1986 1988年相继提出ID4和ID5算法 1993年Quinlan则进一步将ID3发展为C4 5算法 还有著名的决策树学习算法CART ClassificationandRegressionTrees 多变量决策树算法GA NN C4 5算法SVM决策树算法 2020 1 14 48 9 3神经网络学习 9 3 1生物神经元9 3 2人工神经元9 3 3神经网络9 3 4神经网络学习9 3 5BP网络及其学习举例 2020 1 14 49 9 3 1生物神经元 生物神经元的基本结构 2020 1 14 50 9 3 2人工神经元 人工神经元结构模型 人工神经元的输入 输出关系可描述为 2020 1 14 51 神经元特性函数 1 阈值型2 S型3 分段线性型 2020 1 14 52 神经元特性函数 2020 1 14 53 9 3 3神经网络 1 分层前向网络2 反馈前向网络 3 互连前向网络4 广泛互连网络 神经网络结构模型 2020 1 14 54 神经网络至少可以实现如下功能 数学上的映射逼近 数据聚类 压缩通过自组织方式对所选输入模式聚类 优化计算和组合优化问题求解 模式分类 概率密度函数的估计 2020 1 14 55 9 3 4神经网络学习 学习 训练 是神经网络的重要特征之一 神经网络能够通过学习 改变其内部状态 使输入 输出呈现某种规律性 网络学习一般是利用一组称为样本的数据 作为网络的输入 和输出 网络按照一定的训练规则 又称学习规则或学习算法 自动调节神经元之间的连接强度或拓扑结构 当网络的实际输出满足期望的要求 或者趋于稳定时 则认为学习成功 学习规则权值修正学派相关规则 Hebb规则 误差修正规则 学习规则 结构修正学派 2020 1 14 56 Hebb规则 如果神经网络中某一神经元与另一直接与其相连的神经元同时处于兴奋状态 那么两个神经元之间的连接强度应该加强 Wij t 1 修正一次后的某一权值 为正常量 为学习因子Xi t Xj t 分别表示在t时刻i j神经元的状态 2020 1 14 57 最基本的误差修正规则 即 学习规则 步1选择一组初始权值Wij 0 步2计算某一输入模式对应的实际输出与期望输出的误差 步3用下式更新权值 阈值可视为输入恒为 1的一个权值 Wij t 1 Wij t dj yj t xi t 步4返回步2 直到对所有训练模式网络输出均能满足要求 2020 1 14 58 2 学习方法分类 表9 2神经网络学习方法的常见分类 2020 1 14 59 9 3 5BP网络及其学习举例BP Back Propagation 网络的特点 1 BP网络的拓扑结构为分层前向网络 2 神经元的特性函数为Sigmoid型 S型 函数 一般取为 3 输入为连续信号量 实数 4 学习方式为有导师学习 5 学习算法为推广的 学习规则 称为误差反向传播算法 简称BP学习算法 2020 1 14 60 BP网络举例 2020 1 14 61 BP学习算法 步1初始化网络权值 阈值及有关参数 步2计算总误差其中p为样本个数 ykj为输出层节点j对第k个样本的输入对应的输出 称为期望输出 ykj 为节点j的实际输出 如果误差E满足要求 学习成功 步3对样本集中各个样本依次重复以下过程 然后转步2 2020 1 14 62 首先 取一样本数据输入网络 然后按如下公式向前计算各层节点 记为j 的输出 其次 从输出层节点到输入层节点以反向顺序 对各连接权值wij按下面的公式进行修正 2020 1 14 63 中间层的误差项 对受隐藏单元影响的误差 l进行加权求和 每个误差 l权值为wlj wlj这个就是从隐藏单元j到输出单元l的权值 这个权值刻画了隐藏单元j对输出单元l的误差应 负责 的程度 对每个训练样例k 利用有关这个样例的误差Ek的梯度修正权值 对每一个训练样例k 每个权被增加 wij 即 2020 1 14 64 算法中的 j称为节点j的误差 它的来历如下 令 2020 1 14 65 又当j为输出节点时 当j为中间节点时 2020 1 14 66 可以看出 9 3 式中Ek是网络输出ykj j 1 2 n 的函数 而ykj又是权值wij的函数 所以 Ek实际是wij的函数 网络学习的目的就是要使这个误差函数达到最小值 9 4 式及 的定义 就是用梯度下降法 在权值空间沿负梯度方向调整权值wij 以使 9 3 式所示的准则函数达到最小 所以 BP网络的学习过程就是一个非线性优化过程 2020 1 14 67 由于BP网络的输入 x1 x2 xn Rn 输出 y1 y2 ym Rm 所以一个BP网络其实就是一个从n维空间到m维空间的高度非线性映射 通过学习 BP网络可以在任意希望的精度上逼近任意的连续函数 所以BP网络可以作为一种函数估计