第 1 章 机器学习概论
　　1.1 机器学习的基本定义
　　众所周知， 机器学习 (Machine Learning) 是人工智能的核心研究领域之一，其研究动机是为了让计算机系统具有人的学习能力以便实现人工智能. 那么， 什么是机器学习呢？机器学习是对研究问题进行模型假设， 利用计算机从训练数据中学习得到模型参数， 并*终对数据进行预测和分析的一门学科.
　　目前被广泛采用的机器学习的定义是“利用经验来改善计算机系统自身的性能”. 由于“经验”在计算机系统中主要是以数据的形式存在的， 因此机器学习需要运用机器学习技术对数据进行分析， 这就使得它逐渐成为智能数据分析技术的创新源之一， 并且为此而受到越来越多的关注.
　　那么， 拿什么来进行机器学习呢？当然是拿数据 (训练样本) 来学！设有一组训练样本 (数据)， 记作 fxigni=1. 每个训练样本 xi 2 Rm， 都是通过采样得到的一个模式， 即输入特征空间中的一个向量; 通常是高维度的 (即 m 很大)， 例如一幅图像. 训练样本可以认为是尚未加工的原始知识， 模型则是经过学习 (即加工、整理、归纳等) 后的真正知识表达. 同时假设所有训练样本满足独立同分布条件 (简记为 iid). 如果要想学得好， 这组训练样本要覆盖模型所有可能的分布空间.
　　为什么需要机器学习呢？计算机发明的初衷是解决大规模科学与工程计算中的数学问题， 后来才被应用于各种领域， 包括数据存储、排序等更复杂的数值与非数值计算. 对于人们要解决的各种实际问题， 计算机程序都取得了远远超过人类的成绩. 例如， 人们在使用智能导航软件时， 任意给定出发点和目的地， 导航软件可以很快计算出*优路线， 这一点也远超过人类. 可以肯定地说， 一个实际问题只要有了确定的逻辑和数学模型， 就可以用计算机进行很好的解决， 并且其处理能力是人类所望尘莫及的. 然而， 到目前为止， 还有许多无法用数学或逻辑模型准确描述的问题， 如情感表达、图像识别、小说创作等， 计算机处理的能力一般还不如人类. 这些用计算机难以处理的问题， 是当前人工智能要解决的核心问题. 而机器学习正是解决这类问题的有力工具.
　　1.2 机器学习的基本术语
　　掌握一门学科的基本术语对学好这门学科是至关重要的. 假定我们通过记录的方式获得了一个关于西瓜的训练数据集， 如表 1.1 所示. 我们将以这个数据集中的数据为例对机器学习的基本术语进行具体化， 以便加深对有关概念的理解.
　　表 1.1 西瓜数据集
　　记录表 1.1 中各项数据的集合称为“数据集”或“样本集”， 表格的每一行数据 (这里是对每一个西瓜的描述) 称为一个“示例”或“样本”. 反映事件或对象在某方面的表现或性质的事项， 称为“属性”或“特征”， 如表格中的“色泽”“根蒂”“敲声”等; 而每个属性或特征的取值， 称为“属性值”或“特征值”， 例如表格中的“青绿”“乌黑”等. 属性 (特征) 张成的空间称为“属性空间”(或“样本空间”“输入空间”)， 例如将表格中的“色泽”“根蒂”“敲声”作为三个坐标轴， 则它们张成一个用于描述西瓜的三维空间， 每个西瓜都可在这个空间中找到自己的坐标位置. 由于属性空间中的每个点对应着一个坐标向量， 因此可以把一个示例称为一个“特征向量”(或“属性向量”). 对于表 1.1 中的某一行数据， 利用“色泽”“根蒂”“敲声”三个属性进行取值记录， 可认为该样本的“维数”为 3. 从数据中学得模型的过程称为“学习”或“训练”， 这个过程通过执行某个学习算法来完成．训练过程中使用的数据称为“训练数据”， 其中每个样本称为一个“训练样本”， 训练样本组成的集合称为“训练集”. “标记/标签”用来表示样本的结果信息， 例如表中的“是否好瓜”. “样例”是指既包含样本属性值又包含标签的样本. 注意样例与样本的区别， 后者包括训练样本和测试样本， 样本不一定具有标签. 所有标记结果的集合称为“标记空间/输出空间”.
　　根据已有的众多样本来判断某一样本的输出结果的过程称为“预测”. 当预测结果是离散值时， 如表中的“好瓜”“非好瓜”， 此类学习任务称为“分类”. 特别地， 对只涉及两个类别的“二分类”任务， 通常称其中一个类为“正类”， 另一个类为“负类 ”; 当涉及多个类别时， 则称为“多分类”任务. 若欲预测的是连续值， 例如西瓜成熟度， 此类学习任务称为“回归”. 一般地， 预测任务是希望通过对训练集 f(x1， y1)， (x2， y2)， ， (xn， yn)g 进行学习， 建立一个从输入空间 X 到输出空间 Y 的映射 f : X → Y. 对二分类任务， 通常令 Y = f 1， +1g 或 f0， 1g;对多分类任务， jYj > 2; 对回归任务， Y = R， R 为实数集．
　　没有用于模型训练的样本都可认为是该模型的“新样本”. 学得模型适用于新样本的能力， 称为“泛化”能力. 学得模型后， 使用其进行预测的过程称为“测试”， 被预测的样本称为“测试样本”. 例如在学得映射 f 后， 对测试例 x， 可得到其预测标记 y = f(x).
　　还可以对样本做“聚类”， 也就是将训练集中的样本分成若干组， 每个组称为一个“簇”， 这些自动形成的簇可能对应一些潜在的概念划分， 例如“浅色瓜”“深色瓜”等. 这样的学习过程有助于人们了解数据内在的规律， 能为更深入地分析数据建立基础. 值得注意的是， 在聚类学习中， “浅色瓜”“深色瓜”这样的概念事先是不知道的， 是学习过程中得到的. 而且学习过程中使用的训练样本通常不拥有标记信息.
　　1.3 机器学习算法的分类
　　机器学习的本质是模型的选择和模型参数的确定. 根据训练数据是否拥有标记信息， 学习任务可大致划分为两大类: 监督学习和无监督学习， 分类和回归是监督学习的代表， 且样本拥有标记信息， 而聚类则是无监督学习的代表， 且样本不具有标记信息.
　　1.3.1 监督学习与无监督学习
　　监督学习的样本数据 xi (i = 1， 2， ， n) 带有标签值 yi (i = 1， 2， ， n)， 它从训练样本中学得一个模型， 然后用这个模型对新的样本进行预测推断. 通俗地说， 监督学习就是从训练样本数据中学得一个映射函数 f 以及函数的参数 θ， 建立如下的映射关系:
　　其中， 样本向量 x 是模型的输入值， 标签 y 是模型的输出值. 标签可以是整数， 也可以是实数， 还可以是向量. 确定这个映射的依据是它能够很好地解释训练样本，让映射的输出值与真实的样本标签值之间的误差极小化， 或者让训练样本集的对数似然函数极大化.
　　日常生活中， 监督学习的应用例子很多， 例如人脸识别、垃圾邮件分类、语音识别、手写体辨识等等. 这类问题需要先收集训练样本， 并对样本进行标注， 然后用标注好的样例 (样本 + 标记) 去训练模型， *后用训练好的模型对新的样本进行预测.
　　无监督学习对没有标签的样本数据进行分析， 去发现样本集所具有的内在结构或分布规律. 无监督学习的典型代表是聚类分析、数据降维和表示学习， 它们所处理的样本都不带有标签信息.
　　聚类分析属于分类问题， 但不具有训练过程. 聚类把一批没有标签的样本数据划分成多个“簇”， 使得在某种相似度指标下每个簇内的样本尽量相似， 而不同簇的样本之间尽量不相似. 聚类算法只有输入向量而没有标签值， 也没有训练过程， 我们在后续的章节中将详细介绍各种典型的聚类算法.数据降维也是一种无监督学习方法， 它将 m 维向量空间中的点通过一个函数映射到更低维的维空间中去:
　　通过将数据映射到低维空间， 可以更容易对它们处理和分析. 如果将数据降维到二维或三维空间， 还可以直观地将降维后的样本数据可视化. 我们将在后续章节中详细介绍数据降维的典型代表——主成分分析法.
　　无监督学习的另一类典型算法是表示学习. 表示学习自动从样本中学习出有用的特征， 用于聚类和分类等目的. 典型的表示学习算法有自动编码器和受限玻尔兹曼机， 它们的输入是没有标签值的样本数据， 如图像和语音信号等， 输出值是提取的特征向量.
　　有些应用问题， 对训练样本进行标记具有很高的成本. 如何利用少量有标记样本和大量无标记样本进行学习， 就是所谓的“半监督学习”. 半监督学习的训练样本是有标记样本与无标记样本的混合， 且一般情况下无标记样本的数量远大于有标记样本. 关于半监督学习的原理， 本书不打算详细阐述， 有兴趣的读者可参考有关文献.
　　1.3.2 分类问题与回归问题
　　1. 分类问题
　　在监督学习中， 如果样本标签是离散值， 这类问题称为分类问题， 其预测函数是一个向量到整数的映射: Rm → Z. 通俗地说， 分类问题是用于将事物打上一个标签， 例如判断一幅图片上的动物是一只猫还是一只狗. 在分类问题中， 样本的标签是其类别编号， 一般从 0 或 1 开始编号. 如果类别数为 2， 则称为二分类问题，其类别标签通常设置为 +1 和 1 (也可以设置为 0 和 1)， 分类对应正类样本和负类样本. 例如在图像识别中， 要判断一幅图像是否为人脸， 那么正类样本为人脸，负类样本为非人脸. 分类并没有逼近的概念， *终正确结果只有一个， 错误的就是错误的， 不会有相近的概念. *常见的分类方法是逻辑回归， 或者叫逻辑分类.
　　对于分类问题， 如果预测函数是线性函数， 则称为线性模型， 否则称为非线性模型. 线性模型是 Rm 中的线性划分. 线性函数是超平面 (在二维空间中是直线，
三维空间中是平面). 线性模型的二分类问题使用的预测函数通常是其中 w 是权重向量， b 是偏置项. 后续章节要介绍的线性支持向量机、逻辑斯谛回归等都属于线性模型.
　　非线性模型的预测函数是非线性映射， 其分类边界是 Rm 中的一个超曲面.在实际应用中样本数据一般是非线性的， 因此， 要求决策函数必须具有非线性拟合的能力， 如后续章节中将介绍的人工神经网络、核映射支持向量机、决策树等都属于非线性模型.
　　2. 回归问题
　　在监督学习中， 如果标签值是连续实数， 这类学习问题称为回归问题. 回归问题是对于连续性数据， 从已有的数据分析来预测结果， 它的预测函数是向量到实数的映射: Rm → R. 例如预测房价、未来的天气情况等都属于回归分析问题.
　　预测函数可以是线性函数， 也可以是非线性函数. 如果是线性函数则称为线性回归， 否则称为非线性回归. 回归分析的任务就是对于给定的训练样本集， 选择预测函数的类型， 然后确定函数的参数值， 例如线性模型 y = wTx + b 中的参数 w 和 b. 确定参数的常用方法是构造一个损失函数 (x， θ)， 它表示预测函数的输出值与样本真实标签值之间的误差， 对所有训练样本的误差求平均值， 得到一个关于参数 θ 的极小化问题:
　　其中， .(xi; θ) 是单个样本的损失函数， n 为训练样本数. 极小化损失函数 .(θ) 可以确定参数 θ 的值， 从而确定预测函数. 对于机器学习算法， 关键的一步就是确定损失函数. 一旦确定了损失函数， 问题就转化为求解一个*优化问题， 这在数学上一般有标准的解决方案.
　　1.3.3 生成模型与判别模型
　　按照模型的求解方法， 可以将分类算法分成生成模型和判别模型. 给定样本特征向量 x 和标签 y， 生成模型是对联合概率 p(x， y) 建模， 而判别模型则是对条件概率 p(y j x) 建模. 不使用概率模型的分类器被归为判别模型， 它直接得到决策函数而不关心样本的概率分布.
　　典型的生成模型有高

目录
第1章 机器学习概论 1
1.1 机器学习的基本定义 1
1.2 机器学习的基本术语 2
1.3 机器学习算法的分类 3
1.3.1 监督学习与无监督学习 3
1.3.2 分类问题与回归问题 4
1.3.3 生成模型与判别模型 5
1.3.4 强化学习 6
1.4 机器学习模型的评价指标 6
1.4.1 模型的泛化能力 6
1.4.2 模型的评估方法 7
1.4.3 精度与召回率 8
1.4.4 ROC 曲线与 AUC 9
1.5 机器学习模型的选择 10
1.5.1 正则化技术 10
1.5.2 偏差-方差分解 12
1.6 机器学习应用的基本流程 13
1.7 机器学习的用途及发展简史 14
第2章 数学基础知识 16
2.1 矩阵与微分 16
2.1.1 矩阵的基本运算 16
2.1.2 矩阵对标量的导数 17
2.1.3 矩阵变量函数的导数 18
2.1.4 向量函数的导数 20
2.1.5 矩阵和向量的微分 21
2.1.6 特征值分解和奇异值分解 22
2.2 *优化方法 24
2.2.1 无约束优化方法 24
2.2.2 约束优化与 KKT 条件 27
2.2.3 二次规划 29
2.2.4 半定规划 30
2.3 概率与统计 31
2.3.1 随机变量与概率 31
2.3.2 条件概率与独立性 33
2.3.3 期望、马尔可夫不等式和矩生成函数 34
2.3.4 方差与切比雪夫不等式 35
2.3.5 样本均值与样本方差 37
2.3.6 极大似然估计 39
2.3.7 熵与 KL 散度 39
第3章 线性模型与逻辑斯谛回归 41
3.1 线性模型的基本形式 41
3.1.1 线性回归模型的理论基础 41
3.1.2 线性回归模型的 MATLAB 实现 44
3.2 逻辑斯谛回归模型 46
3.2.1 逻辑斯谛回归的基本原理 46
3.2.2 逻辑斯谛回归的 MATLAB 实现 50
3.3 线性判别分析 53
3.3.1 线性判别分析的基本原理 54
3.3.2 线性判别分析的 MATLAB 实现 58
第4章 支持向量机 64
4.1 支持向量机的算法原理 64
4.1.1 线性可分问题 65
4.1.2 线性不可分问题 69
4.2 核映射 (核函数) 支持向量机 71
4.3 SMO 算法原理及推导 73
4.3.1 子问题的求解 75
4.3.2 优化变量的选择 78
4.4 支持向量回归模型 79
4.5 支持向量机的 MATLAB 实现 82
第5章 人工神经网络 89
5.1 前馈神经网络简介 89
5.1.1 M-P 神经元 89
5.1.2 感知器模型 91
5.1.3 多层前馈网络 95
5.2 误差逆传播算法 98
5.2.1 一个单隐层网络实例 99
5.2.2 误差逆传播 (BP) 算法 103
5.3 神经网络的数学性质与实现细节 109
5.3.1 神经网络的数学性质 109
5.3.2 全局*小与局部极小 110
5.3.3 面临的问题与实现细节 111
5.4 神经网络的 MATLAB 实现 115
第6章 决策树算法 124
6.1 决策树算法的基本原理 124
6.1.1 树模型决策过程 124
6.1.2 决策树算法的基本框架 125
6.1.3 决策树的剪枝 127
6.2 基本决策树算法的改进 130
6.2.1 信息增益与 ID3 决策树 130
6.2.2 增益率与 C4.5 决策树 133
6.2.3 基尼指数与 CART 决策树 135
6.3 连续值处理与属性缺失 137
6.3.1 连续值的处理 137
6.3.2 属性缺失问题 139
6.4 决策树算法的 MATLAB 实现 141
第7章 贝叶斯算法 148
7.1 贝叶斯算法的原理 148
7.1.1 贝叶斯决策 148
7.1.2 朴素贝叶斯算法 149
7.1.3 正态贝叶斯算法 154
7.2 贝叶斯算法的改进 155
7.2.1 半朴素贝叶斯算法 156
7.2.2 TAN 贝叶斯算法 157
7.2.3 贝叶斯网与朴素贝叶斯树 159
7.2.4 加权朴素贝叶斯算法 161
7.3 贝叶斯算法的 MATLAB 实现 162
第8章 k 近邻算法 167
8.1 k 近邻算法的原理 167
8.1.1 k 近邻算法的流程 167
8.1.2 k 近邻的距离函数 169
8.2 k 近邻改进算法简介 171
8.3 k 近邻算法的 MATLAB 实现 173
第9章 数据降维算法 182
9.1 主成分分析法 182
9.1.1 主成分分析的基本原理 182
9.1.2 核主成分分析算法 189
9.1.3 PCA 算法的 MATLAB 实现 190
9.1.4 快速 PCA 算法及其实现 194
9.2 流形学习算法 196
9.2.1 局部线性嵌入及其 MATLAB 实现 197
9.2.2 等距映射与 MDS 算法及其实现 203
第10章 聚类算法 209
10.1 聚类的基本理论 209
10.1.1 问题定义 209
10.1.2 距离计算 210
10.1.3 性能指标 211
10.2 k 均值算法 213
10.2.1 k 均值算法基本原理 213
10.2.2 k 均值算法的 MATLAB 实现 214
10.3 k 中心点算法 217
10.3.1 k 中心点算法基本原理 217
10.3.2 k 中心点算法的 MATLAB 实现 220
10.4 密度聚类算法 221
10.4.1 DBSCAN 算法的基本原理 222
10.4.2 DBSCAN 算法的 MATLAB 实现 224
10.5 层次聚类算法 230
10.5.1 AGNES 算法的基本原理 230
10.5.2 AGNES 算法的 MATLAB 实现 231
第11章 高斯混合模型与 EM 算法 237
11.1 高斯混合模型 237
11.2 EM 算法的理论推导 238
11.3 EM 算法的应用 242
11.4 GMM 的 MATLAB 实现 251
11.4.1 高斯混合模型的生成 251
11.4.2 GM 模型的参数拟合 253
11.4.3 高斯混合聚类实例 255
11.5 高斯混合聚类的改进方法 261
11.5.1 拟合初始值的设定问题 261
11.5.2 聚类簇数 k 值的选择问题 264
11.5.3 高斯混合聚类的正则化 267
第12章 集成学习算法 270
12.1 集成学习概述 270
12.1.1 集成学习的基本概念 270
12.1.2 集成模型的并行生成 271
12.1.3 集成模型的串行生成 272
12.1.4 集成模型的组合策略 273
12.2 Bagging 与随机森林 276
12.2.1 Bagging 算法 276
12.2.2 随机森林算法 278
12.2.3 随机森林的 MATLAB 实现 279
12.3 Boosting 算法 283
12.3.1 AdaBoost 算法的基本原理 283
12.3.2 AdaBoost 的 MATLAB 实现 291
第13章 *大熵算法 298
13.1 熵的来源及相关定义 298
13.2 *大熵模型的定义 300
13.2.1 *大熵原理 300
13.2.2 *大熵模型 302
13.3 *大熵模型的学习算法 304
13.3.1 *大熵算法的基本原理 304
13.3.2 *大熵模型的极大似然估计 308
13.4 模型参数学习的*优化方法 310
13.4.1 梯度下降法和拟牛顿法 310
13.4.2 改进的迭代尺度法 312
13.5 *大熵模型的 MATLAB 实现 316
第14章 概率图算法 322
14.1 隐马尔可夫模型 323
14.1.1 隐马尔可夫模型的定义 323
14.1.2 观测序列概率的计算方法 326
14.1.3 计算模型参数的鲍姆-韦尔奇算法 336
14.1.4 预测隐藏状态序列的维特比算法 343
14.2 条件随机场模型 348
14.2.1 条件随机场的定义 349
14.2.2 线性链条件随机场 350
14.2.3 线性链条件随机场的概率计算 355
14.2.4 线性链条件随机场的学习算法 358
14.2.5 线性链条件随机场的解码算法 360
第15章 强化学习算法 366
15.1 强化学习的模型基础 366
15.1.1 强化学习的基本特征 366
15.1.2 强化学习的建模 367
15.2 强化学习的理论模型 369
15.2.1 探索与利用 369
15.2.2 ε-贪心算法 370
15.2.3 Softmax 算法 371
15.3 马尔可夫决策过程 375
15.4 求解*优策略的动态规划算法 378
15.4.1 策略迭代算法 379
15.4.2 价值迭代算法 381
15.5 求解*优策略的蒙特卡罗法 383
15.5.1 无模型强化学习的定义 383
15.5.2 蒙特卡罗法求解预测问题 384
15.5.3 蒙特卡罗法求解控制问题 386
15.6 求解*优策略的时序差分法 387
15.6.1 时序差分法的基本原理 387
15.6.2 SARSA 算法及 MATLAB 实现 390
15.6.3 Q-学习算法及 MATLAB 实现 397
参考文献 407