第6章 机器学习与知识发现 6.1 机器学习概述 6.2 符号学习 6.3 神经网络学习 6.4 知识发现与数据挖掘

6.1 机器学习概述 6.1.1 机器学习的概念 心理学中对学习的解释是：学习是指（人或动物）依靠经验的获得而使行为持久变化的过程。 Simon认为：如果一个系统能够通过执行某种过程而改进它的性能，这就是学习。 Minsky认为：学习是在人们头脑中（心理内部）进行有用的变化。 Tom M. Mitchell在《机器学习》一书中对学习的定义是：对于某类任务T和性能度P，如果一个计算机程序在T上以P衡量的性能随着经验E而自我完善，那么，我们称这个计算机程序从经验E中学习。 当前关于机器学习的许多文献中也大都认为：学习是系统积累经验以改善其自身性能的过程。

总之： ① 学习与经验有关； ② 学习可以改善系统性能； ③ 学习是一个有反馈的信息处理与控制过程。因为经验是在系统与环境的交互过程中产生的，而经验中应该包含系统输入、响应和效果等信息。因此经验的积累、性能的完善正是通过重复这一过程而实现的。

6.1.2 机器学习的原理 图 9-1 机器学习原理1

图 9-2 机器学习原理2  

图 9-3 机器学习原理3

图 9-4 机器学习原理4

图 9-5 机器学习原理5

6.1.3 机器学习的分类 1. 基于学习策略的分类 （1）模拟人脑的机器学习 ●符号学习：模拟人脑的宏观心理级学习过程，以认知心理学原理为基础，以符号数据为输入，以符号运算为方法，用推理过程在图或状态空间中搜索，学习的目标为概念或规则等。符号学习的典型方法有：记忆学习、示例学习、演绎学习、类比学习、解释学习等。 ●神经网络学习（或连接学习）：模拟人脑的微观生理级学习过程，以脑和神经科学原理为基础，以人工神经网络为函数结构模型，以数值数据为输入，以数值运算为方法，用迭代过程在系数向量空间中搜索，学习的目标为函数。典型的连接学习有权值修正学习、拓扑结构学习。

（2）直接采用数学方法的机器学习 ●主要有统计机器学习。 2. 基于学习方法的分类 （1）归纳学习 ● 符号归纳学习：典型的符号归纳学习有示例学习，决策树学习。 ● 函数归纳学习（发现学习）：典型的函数归纳学习有神经网络学习、示例学习，发现学习，统计学习。 （2）演绎学习 （3）类比学习：典型的类比学习有案例（范例）学习。 （4）分析学习：典型的分析学习有案例（范例）学习、解释学习。

3. 基于学习方式的分类 （1）有导师学习（监督学习）：输入数据中有导师信号，以概率函数、代数函数或人工神经网络为基函数模型，采用迭代计算方法，学习结果为函数。 （2）无导师学习（非监督学习）：输入数据中无导师信号，采用聚类方法，学习结果为类别。典型的无导师学习有发现学习、聚类、竞争学习等。 （3）强化学习（增强学习）：以环境反馈（奖/惩信号）作为输入，以统计和动态规划技术为指导的一种学习方法。

4. 基于数据形式的分类 （1）结构化学习：以结构化数据为输入，以数值计算或符号推演为方法。典型的结构化学习有神经网络学习、统计学习、决策树学习、规则学习。 （2）非结构化学习：以非结构化数据为输入，典型的非结构化学习有类比学习、案例学习、解释学习、文本挖掘、图像挖掘、Web挖掘等。

（1）概念学习：即学习的目标和结果为概念，或者说是为了获得概念的一种学习。典型的概念学习有示例学习。 5. 基于学习目标的分类 （1）概念学习：即学习的目标和结果为概念，或者说是为了获得概念的一种学习。典型的概念学习有示例学习。 （2）规则学习：即学习的目标和结果为规则，或者说是为了获得规则的一种学习。典型的规则学习有决策树学习。 （3）函数学习：即学习的目标和结果为规则，或者说是为了获得函数的一种学习。典型的函数学习有神经网络学习。 （4）类别学习：即学习的目标和结果为对象类，或者说是为了获得类别的一种学习。典型的类别学习有聚类分析。 （5）贝叶斯网络学习：即学习的目标和结果是贝叶斯网络，或者说是为了获得贝叶斯网络的一种学习。其又可分为结构学习和参数学习。

6.2 符号学习 6.2.1 记忆学习 记忆学习方法简单, 但学习系统需要几种能力：  (1) 能实现有组织的存储信息。 (2) 能进行信息综合。 (3) 能控制检索方向。 当存储对象愈多时, 其中可能有多个对象与给定的

示例学习也称实例学习, 它是一种归纳学习。示例学习是从若干实例(包括正例和反例)中归纳出一般概念或规则的学习方法。 6.2.2 示例学习 示例学习也称实例学习, 它是一种归纳学习。示例学习是从若干实例(包括正例和反例)中归纳出一般概念或规则的学习方法。 图 9-7 第二个拱桥的语义网络 图 9-6 第一个拱桥的语义网络

图 9-9 拱桥概念的语义网络 图 9-8 学习程序归纳出的语义网络

花色(c1，梅花)∧花色(c2，梅花)∧花色(c3，梅花)∧花色(c4，梅花)→同花(c1，c2，c3，c4) 示例2： 例 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)

例9.2 假设示例空间存放有如下的三个示例： 示例1：(0，2，7) 示例2：(6，-1，10) 示例3：(-1，-5，-10) 这是三个3维向量，表示空间中的三个点。现要求求出过这三点的曲线。 对于这个问题可采用通常的曲线拟合技术，归纳出规则： (x，y，2x+3y+1) 即 z＝2x＋3y＋1

6.2.3 决策树学习 1．什么是决策树 决策树(decision tree)也称判定树，它是由对象的若干属性、属性值和有关决策组成的一棵树。其中的节点为属性（一般为语言变量），分枝为相应的属性值（一般为语言值）。从同一节点出发的各个分枝之间是逻辑“或”关系；根节点为对象的某一个属性；从根节点到每一个叶子节点的所有节点和边，按顺序串连成一条分枝路径，位于同一条分枝路径上的各个“属性-值”对之间是逻辑“与”关系，叶子节点为这个与关系的对应结果，即决策。

决策树示意图

例9.3 　下图所示是机场指挥台关于飞机起飞的简单决策树。

例9.4 　下图是一个描述“兔子”概念的决策树。

2. 怎样学习决策树 决策树学习的基本方法和步骤： 首先，选取一个属性，按这个属性的不同取值对实例集进行分类；并以该属性作为根节点，以这个属性的诸取值作为根节点的分枝，进行画树。 然后，考察所得的每一个子类，看其中的实例的结论是否完全相同。如果完全相同，则以这个相同的结论作为相应分枝路径末端的叶子节点；否则，选取一个非父节点的属性，按这个属性的不同取值对该子集进行分类，并以该属性作为节点，以这个属性的诸取值作为节点的分枝，继续进行画树。 如此继续，直到所分的子集全都满足：实例结论完全相同，而得到所有的叶子节点为止。

● 决策树学习举例 设表9.1 所示的是某保险公司的汽车驾驶保险类别划分的部分事例。我们将这张表作为一个实例集，用决策树学习来归纳该保险公司的汽车驾驶保险类别划分规则。

表9.1 汽车驾驶保险类别划分实例集

将实例集简记为 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” 这三个年龄段。

对于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)} 于是，我们得到以性别作为根节点的部分决策树（见下图）。

决策树生成过程

决策树生成过程

决策树生成过程

最后生成的 决策树

由决策树所得的规则集： ① 女性且年龄在25岁以上，则给予A类保险； ② 女性且年龄在21岁到25岁之间，则给予A类保险； ③ 女性且年龄在21岁以下，则给予C类保险； ④ 男性且年龄在25岁以上，则给予B类保险； ⑤ 男性且年龄在21岁到25岁之间且未婚，则给予C类保险； ⑥ 男性且年龄在21岁到25岁之间且已婚，则给予B类保险； ⑦ 男性且年龄在21岁以下且未婚，则给予C类保险； ⑧ 男性且年龄在21岁以下且已婚，则给予B类保险。

3. ID3算法 ID3算法是一个经典的决策树学习算法，由Quinlan于1979年提出。ID3算法的基本思想是，以信息熵为度量，用于决策树节点的属性选择，每次优先选取信息量最多的属性，亦即能使熵值变成最小的属性，以构造一棵熵值下降最快的决策树，到叶子节点处的熵值为0。此时，每个叶子节点对应的实例集中的实例属于同一类。

（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对应的那个子类。

（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女而言,

于是, 由公式(9-1)有:

又

将以上3式代入公式(9-2)得: 用同样的方法可求得: 可见, 条件熵H(S|性别)为最小,所以,应取“性别”这一属性对实例集进行分类, 即以“性别”作为决策树的根节点。

6.3 神经网络学习 6.3.1　生物神经元  生物神经元的基本结构

6.3.2　人工神经元 人工神经元结构模型 人工神经元的输入、 输出关系可描述为：

神经元特性函数 1. 阈值型 2. S型 3. 分段线性型

神经元特性函数

6.3.3 神经网络 　1. 分层前向网络 2. 反馈前向网络 3. 互连前向网络　4. 广泛互连网络 神经网络 结构模型

神经网络至少可以实现如下功能： ——数学上的映射逼近 ——数据聚类、压缩 通过自组织方式对所选输入模 式聚类 ——优化计算和组合优化问题求解 ——模式分类 ——概率密度函数的估计

6.3.4 神经网络学习 1. 学习规则 步2 计算某一输入模式对应的实际输出与期望输出的误差。 6.3.4　神经网络学习 　1. 学习规则 Hebb规则： 最基本的误差修正规则,即δ学习规则： 　　 步1 选择一组初始权值Wij(0)。 步2 计算某一输入模式对应的实际输出与期望输出的误差。 步3 用下式更新权值(阈值可视为输入恒为-1的一个权值) Wij(t＋1)=Wij(t)＋η［dj－yj(t)］xi(t) 步4 返回步2，直到对所有训练模式网络输出均能满足要求。

2. 学习方法分类  表 9.2 神经网络学习方法的常见分类

9.3.5 BP网络及其学习举例 BP(Back-Propagation)网络的特点： (1) BP网络的拓扑结构为分层前向网络。 　 (2) 神经元的特性函数为Sigmoid型(S型)函数, 一般取为 (3) 输入为连续信号量(实数)。 (4) 学习方式为有导师学习。 　(5) 学习算法为推广的δ学习规则, 称为误差反向传播算法, 简称BP学习算法。

BP学习算法：  步1 初始化网络权值、 阈值及有关参数。 步2 计算总误差 　步1 初始化网络权值、 阈值及有关参数。 步2 计算总误差 其中ykj为输出层节点j对第k个样本的输入对应的输出（称为期望输出），ykj′为节点j的实际输出。 步3 对样本集中各个样本依次重复以下过程，然后转步2。　

首先，取一样本数据输入网络，然后按如下公式向前计算各层节点(记为j)的输出： 其次，从输出层节点到输入层节点以反向顺序，对各连接权值wij按下面的公式进行修正： 对于输出节点 对于中间节点

例 9.5 设计一个BP网络, 对下表所示的样本数据进行学习, 使学成的网络能解决类似的模式分类问题。 输入 输出 x1 x2 x3 y1 y2 y3 0.3 0.8 0.1 0.7 0.1 0.3 0.6 0.6 0.6 1 0 0 0 1 0 0 0 1

BP网络举例

6.4 知识发现与数据挖掘 6.4.1 知识发现的一般过程 1. 数据准备 2. 数据挖掘 3. 解释和评价 4. 知识表示

6.4.2 知识发现的对象 1. 数据库 2. 数据仓库 数据仓库的基本特征： ① 数据仓库的数据是面向主题的； ② 数据仓库的数据是集成的； ③ 数据仓库的数据是稳定的； ④ 数据仓库的数据是随时间不断变化的。 3. Web信息 4. 图像和视频数据

6.4.3 知识发现的任务 1. 数据总结 2. 概念描述 3. 分类（classification） 4. 聚类（clustering） 5. 相关性分析 6. 偏差分析 7. 建模

6.4.4 知识发现的方法 1. 统计方法 2. 机器学习方法 3. 粗糙集及模糊集 4. 智能计算方法 5. 可视化