《机器学习》学习笔记.pdf

《《机器学习》学习笔记.pdf》由会员分享，可在线阅读，更多相关《《机器学习》学习笔记.pdf（138页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、机器学习机器学习 学习笔记（学习笔记（1 1）-绪论绪论机器学习是目前信息技术中最激动人心的方向之一，其应用已经深入到生活的各个层面且与普通人的日常生活密切相关。本文为清华大学最新出版的机器学习教材的 Learning Notes，书作者是南京大学周志华教授，多个大陆首位彰显其学术奢华。本篇主要介绍了该教材前两个章节的知识点以及自己一点浅陋的理解。1 1 绪论绪论傍晚小街路面上沁出微雨后的湿润，和熙的细风吹来，抬头看看天边的晚霞，嗯，明天又是一个好天气。走到水果摊旁，挑了个根蒂蜷缩、敲起来声音浊响的青绿西瓜，一边满心期待着皮薄肉厚瓢甜的爽落感，一边愉快地想着，这学期狠下了工夫，基础概念弄得清清

2、楚楚，算法作业也是信手拈来，这门课成绩一定差不了！哈哈，也希望自己这学期的 machine learning 课程取得一个好成绩！1.11.1 机器学习的定义机器学习的定义正如我们根据过去的经验来判断明天的天气，吃货们希望从购买经验中挑选一个好瓜，那能不能让计算机帮助人类来实现这个呢？机器学习正是这样的一门学科，人的“经验”对应计算机中的“数据”，让计算机来学习这些经验数据，生成一个算法模型，在面对新的情况中，计算机便能作出有效的判断，这便是机器学习。另一本经典教材的作者 Mitchell 给出了一个形式化的定义，假设：P：计算机程序在某任务类 T 上的性能。T：计算机程序希望实现的任务类。E

3、：表示经验，即历史的数据集。若该计算机程序通过利用经验 E 在任务 T 上获得了性能 P 的改善，则称该程序对 E 进行了学习。1.21.2 机器学习的一些基本术语机器学习的一些基本术语假设我们收集了一批西瓜的数据，例如：（色泽=青绿;根蒂=蜷缩;敲声=浊响)，(色泽=乌黑;根蒂=稍蜷;敲声=沉闷)，(色泽=浅自;根蒂=硬挺;敲声=清脆)每对括号内是一个西瓜的记录，定义：所有记录的集合为：数据集。每一条记录为：一个实例（instance）或样本（sample）。例如：色泽或敲声，单个的特点为特征（feature）或属性（attribute）。对于一条记录，如果在坐标轴上表示，每个西瓜都可以用坐

4、标轴中的一个点表示，一个点也是一个向量，例如（青绿，蜷缩，浊响），即每个西瓜为：一个特征向量（featurevector）。一个样本的特征数为：维数（dimensionality），该西瓜的例子维数为 3，当维数非常大时，也就是现在说的“维数灾难”。在计算机程序学习经验数据生成算法模型的过程中，每一条记录称为一个“训练样本”，同时在训练好模型后，我们希望使用新的样本来测试模型的效果，则每一个新的样本称为一个“测试样本”。定义：所有训练样本的集合为：训练集（trainning set），特殊。所有测试样本的集合为：测试集（test set），一般。机器学习出来的模型适用于新样本的能力为：泛化能力

5、（generalization），即从特殊到一般。在西瓜的例子中，我们是想计算机通过学习西瓜的特征数据，训练出一个决策模型，来判断一个新的西瓜是否是好瓜。可以得知我们预测的是：西瓜是好是坏，即好瓜与差瓜两种，是离散值。同样地，也有通过历年的人口数据，来预测未来的人口数量，人口数量则是连续值。定义：预测值为离散值的问题为：分类（classification）。预测值为连续值的问题为：回归（regression）。在我们预测西瓜是否是好瓜的过程中，很明显对于训练集中的西瓜，我们事先已经知道了该瓜是否是好瓜，学习器通过学习这些好瓜或差瓜的特征，从而总结出规律，即训练集中的西瓜我们都做了标记，称为标记

6、信息。但也有没有标记信息的情形，例如：我们想将一堆西瓜根据特征分成两个小堆，使得某一堆的西瓜尽可能相似，即都是好瓜或差瓜，对于这种问题，我们事先并不知道西瓜的好坏，样本没有标记信息。定义：训练数据有标记信息的学习任务为：监督学习（supervised learning），容易知道上面所描述的分类和回归都是监督学习的范畴。训练数据没有标记信息的学习任务为：无监督学习（unsupervised learning），常见的有聚类和关联规则。2 2 模型的评估与选择模型的评估与选择2.12.1 误差与过拟合误差与过拟合我们将学习器对样本的实际预测结果与样本的真实值之间的差异成为：误差（error）。定

7、义：在训练集上的误差称为训练误差（training error）或经验误差（empirical error）。在测试集上的误差称为测试误差（test error）。学习器在所有新样本上的误差称为泛化误差（generalization error）。显然，我们希望得到的是在新样本上表现得很好的学习器，即泛化误差小的学习器。因此，我们应该让学习器尽可能地从训练集中学出普适性的“一般特征”，这样在遇到新样本时才能做出正确的判别。然而，当学习器把训练集学得“太好”的时候，即把一些训练样本的自身特点当做了普遍特征；同时也有学习能力不足的情况，即训练集的基本特征都没有学习出来。我们定义：学习能力过强，以至

8、于把训练样本所包含的不太一般的特性都学到了，称为：过拟合（overfitting）。学习能太差，训练样本的一般性质尚未学好，称为：欠拟合（underfitting）。可以得知：在过拟合问题中，训练误差十分小，但测试误差教大；在欠拟合问题中，训练误差和测试误差都比较大。目前，欠拟合问题比较容易克服，例如增加迭代次数等，但过拟合问题还没有十分好的解决方案，过拟合是机器学习面临的关键障碍。2.22.2 评估方法评估方法在现实任务中，我们往往有多种算法可供选择，那么我们应该选择哪一个算法才是最适合的呢？如上所述，我们希望得到的是泛化误差小的学习器，理想的解决方案是对模型的泛化误差进行评估，然后选择泛化

9、误差最小的那个学习器。但是，泛化误差指的是模型在所有新样本上的适用能力，我们无法直接获得泛化误差。因此，通常我们采用一个“测试集”来测试学习器对新样本的判别能力，然后以“测试集”上的“测试误差”作为“泛化误差”的近似。显然：我们选取的测试集应尽可能与训练集互斥，下面用一个小故事来解释 why：假设老师出了 10 道习题供同学们练习，考试时老师又用同样的这 10 道题作为试题，可能有的童鞋只会做这 10 道题却能得高分，很明显：这个考试成绩并不能有效地反映出真实水平。回到我们的问题上来，我们希望得到泛化性能好的模型，好比希望同学们课程学得好并获得了对所学知识”举一反三”的能力；训练样本相当于给同

10、学们练习的习题，测试过程则相当于考试。显然，若测试样本被用作训练了，则得到的将是过于”乐观”的估计结果。2.32.3 训练集与测试集的划分方法训练集与测试集的划分方法如上所述：我们希望用一个“测试集”的“测试误差”来作为“泛化误差”的近似，因此我们需要对初始数据集进行有效划分，划分出互斥的“训练集”和“测试集”。下面介绍几种常用的划分方法：2.3.12.3.1 留出法留出法将数据集 D 划分为两个互斥的集合，一个作为训练集 S，一个作为测试集 T，满足 D=ST 且ST=，常见的划分为：大约 2/3-4/5 的样本用作训练，剩下的用作测试。需要注意的是：训练/测试集的划分要尽可能保持数据分布的

11、一致性，以避免由于分布的差异引入额外的偏差，常见的做法是采取分层抽样。同时，由于划分的随机性，单次的留出法结果往往不够稳定，一般要采用若干次随机划分，重复实验取平均值的做法。2.3.22.3.2 交叉验证法交叉验证法将数据集 D 划分为 k 个大小相同的互斥子集，满足 D=D1D2Dk，DiDj=（ij），同样地尽可能保持数据分布的一致性，即采用分层抽样的方法获得这些子集。交叉验证法的思想是：每次用 k-1 个子集的并集作为训练集，余下的那个子集作为测试集，这样就有 K 种训练集/测试集划分的情况，从而可进行 k 次训练和测试，最终返回 k 次测试结果的均值。交叉验证法也称“k 折交叉验证”，

12、k 最常用的取值是 10，下图给出了 10 折交叉验证的示意图。与留出法类似，将数据集 D 划分为 K 个子集的过程具有随机性，因此 K 折交叉验证通常也要重复 p 次，称为 p 次 k 折交叉验证，常见的是 10 次 10 折交叉验证，即进行了 100 次训练/测试。特殊地当划分的 k 个子集的每个子集中只有一个样本时，称为“留一法”，显然，留一法的评估结果比较准确，但对计算机的消耗也是巨大的。2.3.32.3.3 自助法自助法我们希望评估的是用整个 D 训练出的模型。但在留出法和交叉验证法中，由于保留了一部分样本用于测试，因此实际评估的模型所使用的训练集比 D 小，这必然会引入一些因训练样

13、本规模不同而导致的估计偏差。留一法受训练样本规模变化的影响较小，但计算复杂度又太高了。“自助法”正是解决了这样的问题。自助法的基本思想是：给定包含 m 个样本的数据集 D，每次随机从 D 中挑选一个样本，将其拷贝放入 D，然后再将该样本放回初始数据集 D 中，使得该样本在下次采样时仍有可能被采到。重复执行 m 次，就可以得到了包含 m 个样本的数据集 D。可以得知在 m 次采样中，样本始终不被采到的概率取极限为：这样，通过自助采样，初始样本集 D 中大约有 36.8%的样本没有出现在 D中，于是可以将 D作为训练集，D-D作为测试集。自助法在数据集较小，难以有效划分训练集/测试集时很有用，但由

14、于自助法产生的数据集（随机抽样）改变了初始数据集的分布，因此引入了估计偏差。在初始数据集足够时，留出法和交叉验证法更加常用。2.42.4 调参调参大多数学习算法都有些参数(parameter)需要设定，参数配置不同，学得模型的性能往往有显著差别，这就是通常所说的”参数调节”或简称”调参”(parameter tuning)。学习算法的很多参数是在实数范围内取值，因此，对每种参数取值都训练出模型来是不可行的。常用的做法是：对每个参数选定一个范围和步长，这样使得学习的过程变得可行。例如：假定算法有 3 个参数，每个参数仅考虑 5 个候选值，这样对每一组训练/测试集就有 5*5*5=125个模型需考

15、察，由此可见：拿下一个参数（即经验值）对于算法人员来说是有多么的 happy。最后需要注意的是：当选定好模型和调参完成后，我们需要使用初始的数据集 D 重新训练模型，即让最初划分出来用于评估的测试集也被模型学习，增强模型的学习效果。机器学习机器学习 学习笔记（学习笔记（2 2）-性能度量性能度量本篇主要是对第二章剩余知识的理解，包括：性能度量、比较检验和偏差与方差。在上一篇中，我们解决了评估学习器泛化性能的方法，即用测试集的“测试误差”作为“泛化误差”的近似，当我们划分好训练/测试集后，那如何计算“测试误差”呢？这就是性能度量，例如：均方差，错误率等，即“测试误差”的一个评价标准。有了评估方法

16、和性能度量，就可以计算出学习器的“测试误差”，但由于“测试误差”受到很多因素的影响，例如：算法随机性或测试集本身的选择，那如何对两个或多个学习器的性能度量结果做比较呢？这就是比较检验。最后偏差与方差是解释学习器泛化性能的一种重要工具。2.52.5 性能度量性能度量性能度量（performance measure）是衡量模型泛化能力的评价标准，在对比不同模型的能力时，使用不同的性能度量往往会导致不同的评判结果。本节除 2.5.1 外，其它主要介绍分类模型的性能度量。2.5.12.5.1 最常见的性能度量最常见的性能度量在回归任务中，即预测连续值的问题，最常用的性能度量是“均方误差”（mean s

17、quared error）,很多的经典算法都是采用了 MSE 作为评价函数，想必大家都十分熟悉。在分类任务中，即预测离散值的问题，最常用的是错误率和精度，错误率是分类错误的样本数占样本总数的比例，精度则是分类正确的样本数占样本总数的比例，易知：错误率+精度=1。2.5.22.5.2 查准率查准率/查全率查全率/F1/F1错误率和精度虽然常用，但不能满足所有的需求，例如：在推荐系统中，我们只关心推送给用户的内容用户是否感兴趣（即查准率:precision），或者说所有用户感兴趣的内容我们推送出来了多少（即查全率:recall）。因此，使用查准/查全率更适合描述这类问题。对于二分类问题，分类结果混

18、淆矩阵与查准/查全率定义如下：初次接触时，FN 与 FP 很难正确的理解，按照惯性思维容易把 FN 理解成：False-Negative，即将错的预测为错的，这样 FN 和 TN 就反了，后来找到一张图，描述得很详细，为方便理解，把这张图也贴在了下边：正如天下没有免费的午餐，查准率和查全率是一对矛盾的度量。例如我们想让推送的内容尽可能用户全都感兴趣，那只能推送我们把握高的内容，这样就漏掉了一些用户感兴趣的内容，查全率就低了；如果想让用户感兴趣的内容都被推送，那只有将所有内容都推送上，宁可错杀一千，不可放过一个，这样查准率就很低了。“P-R 曲线”正是描述查准/查全率变化的曲线，P-R 曲线定义

19、如下：根据学习器的预测结果（一般为一个实值或概率）对测试样本进行排序，将最可能是“正例”的样本排在前面，最不可能是“正例”的排在后面，按此顺序逐个把样本作为“正例”进行预测，每次计算出当前的P 值和 R 值，如下图所示：P-R 曲线如何评估呢？若一个学习器 A 的 P-R 曲线被另一个学习器 B 的 P-R 曲线完全包住，则称：B 的性能优于 A。若 A 和 B 的曲线发生了交叉，则谁的曲线下的面积大，谁的性能更优。但一般来说，曲线下的面积是很难进行估算的，所以衍生出了“平衡点”（Break-Event Point，简称 BEP），即当 P=R 时的取值，平衡点的取值越高，性能更优。P 和 R

20、 指标有时会出现矛盾的情况，这样就需要综合考虑他们，最常见的方法就是 F-Measure，又称 F-Score。F-Measure 是 P 和 R 的加权调和平均，即：特别地，当=1 时，也就是常见的 F1 度量，是 P 和 R 的调和平均，当 F1 较高时，模型的性能越好。有时候我们会有多个二分类混淆矩阵，例如：多次训练或者在多个数据集上训练，那么估算全局性能的方法有两种，分为宏观和微观。简单理解，宏观就是先算出每个混淆矩阵的 P 值和 R值，然后取得平均 P 值 macro-P 和平均 R 值 macro-R，再算出 F或 F1，而微观则是计算出混淆矩阵的平均 TP、FP、TN、FN，接着

21、进行计算 P、R，进而求出 F或 F1。2.5.32.5.3 ROCROC 与与 AUCAUC如上所述：学习器对测试样本的评估结果一般为一个实值或概率，设定一个阈值，大于阈值为正例，小于阈值为负例，因此这个实值的好坏直接决定了学习器的泛化性能，若将这些实值排序，则排序的好坏决定了学习器的性能高低。ROC 曲线正是从这个角度出发来研究学习器的泛化性能，ROC（Receiver Operating Characteristic）曲线与 P-R 曲线十分类似，都是按照排序的顺序逐一按照正例预测，不同的是 ROC 曲线以“真正例率”（True Positive Rate，简称 TPR）为横轴，纵轴为“

22、假正例率”（False Positive Rate，简称 FPR），ROC 偏重研究基于测试样本评估值的排序好坏。简单分析图像，可以得知：当 FN=0 时，TN 也必须 0，反之也成立，我们可以画一个队列，试着使用不同的截断点（即阈值）去分割队列，来分析曲线的形状，（0,0）表示将所有的样本预测为负例，（1,1）则表示将所有的样本预测为正例，（0,1）表示正例全部出现在负例之前的理想情况，（1,0）则表示负例全部出现在正例之前的最差情况。限于篇幅，这里不再论述。现实中的任务通常都是有限个测试样本，因此只能绘制出近似 ROC 曲线。绘制方法：首先根据测试样本的评估值对测试样本排序，接着按照以下规

23、则进行绘制。同样地，进行模型的性能比较时，若一个学习器 A 的 ROC 曲线被另一个学习器 B 的 ROC 曲线完全包住，则称 B 的性能优于 A。若 A 和 B 的曲线发生了交叉，则谁的曲线下的面积大，谁的性能更优。ROC 曲线下的面积定义为 AUC（Area Under ROC Curve），不同于 P-R 的是，这里的 AUC 是可估算的，即 AOC 曲线下每一个小矩形的面积之和。易知：AUC 越大，证明排序的质量越好，AUC 为 1 时，证明所有正例排在了负例的前面，AUC 为 0 时，所有的负例排在了正例的前面。2.5.42.5.4 代价敏感错误率与代价曲线代价敏感错误率与代价曲线上

24、面的方法中，将学习器的犯错同等对待，但在现实生活中，将正例预测成假例与将假例预测成正例的代价常常是不一样的，例如：将无疾病有疾病只是增多了检查，但有疾病无疾病却是增加了生命危险。以二分类为例，由此引入了“代价矩阵”（cost matrix）。在非均等错误代价下，我们希望的是最小化“总体代价”，这样“代价敏感”的错误率（2.5.1节介绍）为：同样对于ROC曲线，在非均等错误代价下，演变成了“代价曲线”，代价曲线横轴是取值在0,1之间的正例概率代价，式中 p 表示正例的概率，纵轴是取值为0,1的归一化代价。代价曲线的绘制很简单：设 ROC 曲线上一点的坐标为(TPR，FPR)，则可相应计算出 FN

25、R，然后在代价平面上绘制一条从(0，FPR)到(1，FNR)的线段，线段下的面积即表示了该条件下的期望总体代价；如此将 ROC 曲线土的每个点转化为代价平面上的一条线段，然后取所有线段的下界，围成的面积即为在所有条件下学习器的期望总体代价，如图所示：机器学习机器学习 学习笔记（学习笔记（3 3）-假设检验、方差与偏差假设检验、方差与偏差在上两篇中，我们介绍了多种常见的评估方法和性能度量标准，这样我们就可以根据数据集以及模型任务的特征，选择出最合适的评估和性能度量方法来计算出学习器的“测试误差“。但由于“测试误差”受到很多因素的影响，例如：算法随机性(例如常见的 K-Means)或测试集本身的选

26、择，使得同一模型每次得到的结果不尽相同，同时测试误差是作为泛化误差的近似，并不能代表学习器真实的泛化性能，那如何对单个或多个学习器在不同或相同测试集上的性能度量结果做比较呢？这就是比较检验。最后偏差与方差是解释学习器泛化性能的一种重要工具。本篇延续上一篇的内容，主要讨论了比较检验、方差与偏差。2.62.6 比较检验比较检验在比较学习器泛化性能的过程中，统计假设检验（hypothesis test）为学习器性能比较提供了重要依据，即若 A 在某测试集上的性能优于 B，那 A 学习器比 B 好的把握有多大。为方便论述，本篇中都是以“错误率”作为性能度量的标准。2.6.12.6.1 假设检验假设检验

27、“假设”指的是对样本总体的分布或已知分布中某个参数值的一种猜想，例如：假设总体服从泊松分布，或假设正态总体的期望 u=u0。回到本篇中，我们可以通过测试获得测试错误率，但直观上测试错误率和泛化错误率相差不会太远，因此可以通过测试错误率来推测泛化错误率的分布，这就是一种假设检验。2.6.22.6.2 交叉验证交叉验证 t t 检验检验2.6.32.6.3 McNemarMcNemar 检验检验MaNemar 主要用于二分类问题，与成对 t 检验一样也是用于比较两个学习器的性能大小。主要思想是：若两学习器的性能相同，则 A 预测正确 B 预测错误数应等于 B 预测错误 A 预测正确数，即 e01=

28、e10，且|e01-e10|服从 N（1，e01+e10）分布。因此，如下所示的变量服从自由度为 1 的卡方分布，即服从标准正态分布 N（0,1）的随机变量的平方和，下式只有一个变量，故自由度为 1，检验的方法同上：做出假设求出满足显著度的临界点给出拒绝域验证假设。2.6.42.6.4 FriedmanFriedman 检验与检验与 NemenyiNemenyi 后续检验后续检验上述的三种检验都只能在一组数据集上，F 检验则可以在多组数据集进行多个学习器性能的比较，基本思想是在同一组数据集上，根据测试结果（例：测试错误率）对学习器的性能进行排序，赋予序值 1,2,3，相同则平分序值，如下图所示

29、：若学习器的性能相同，则它们的平均序值应该相同，且第 i 个算法的平均序值 ri 服从正态分布N（k+1）/2，（k+1）(k-1)/12），则有：服从自由度为 k-1 和(k-1)(N-1)的 F 分布。下面是 F 检验常用的临界值：若“H0：所有算法的性能相同”这个假设被拒绝，则需要进行后续检验，来得到具体的算法之间的差异。常用的就是 Nemenyi 后续检验。Nemenyi 检验计算出平均序值差别的临界值域，下表是常用的 qa 值，若两个算法的平均序值差超出了临界值域 CD，则相应的置信度 1-拒绝“两个算法性能相同”的假设。2.72.7 偏差与方差偏差与方差偏差-方差分解是解释学习器泛

30、化性能的重要工具。在学习算法中，偏差指的是预测的期望值与真实值的偏差，方差则是每一次预测值与预测值得期望之间的差均方。实际上，偏差体现了学习器预测的准确度，而方差体现了学习器预测的稳定性。通过对泛化误差的进行分解，可以得到：期望泛化误差期望泛化误差=方差方差+偏差偏差偏差刻画学习器的拟合能力偏差刻画学习器的拟合能力方差体现学习器的稳定性方差体现学习器的稳定性易知：方差和偏差具有矛盾性，这就是常说的偏差-方差窘境（bias-variance dilamma），随着训练程度的提升，期望预测值与真实值之间的差异越来越小，即偏差越来越小，但是另一方面，随着训练程度加大，学习算法对数据集的波动越来越敏感

31、，方差值越来越大。换句话说：在欠拟合时，偏差主导泛化误差，而训练到一定程度后，偏差越来越小，方差主导了泛化误差。因此训练也不要贪杯，适度辄止。机器学习机器学习 学习笔记（学习笔记（4 4）-线性模型线性模型前一部分主要是对机器学习预备知识的概括，包括机器学习的定义/术语、学习器性能的评估/度量以及比较，本篇之后将主要对具体的学习算法进行理解总结，本篇则主要是第 3 章的内容线性模型。3 3、线性模型、线性模型谈及线性模型，其实我们很早就已经与它打过交道：根据给定的（x，y）点对，求出一条与这些点拟合效果最好的直线 y=ax+b，之前我们利用下面的公式便可以计算出拟合直线的系数 a,b（3.1

32、中给出了具体的计算过程），从而对于一个新的 x，可以预测它所对应的 y 值。前面我们提到：在机器学习的术语中，当预测值为连续值时，称为“回归问题”，离散值时为“分类问题”。本篇先从线性回归任务开始，接着讨论分类和多分类问题。3.13.1 线性回归线性回归线性回归问题就是试图学到一个线性模型尽可能准确地预测新样本的输出值，例如：通过历年的人口数据预测 2017 年人口数量。在这类问题中，往往我们会先得到一系列的有标记数据，例如：200013 亿201615 亿，这时输入的属性只有一个，即年份；也有输入多属性的情形，假设我们预测一个人的收入，这时输入的属性值就不止一个了，例如：（学历，年龄，性别，

33、颜值，身高，体重）15k。有时这些输入的属性值并不能直接被我们的学习模型所用，需要进行相应的处理，对于连续值的属性，一般都可以被学习器所用，有时会根据具体的情形作相应的预处理，例如：归一化等；对于离散值的属性，可作下面的处理：若属性值之间存在“序关系”，则可以将其转化为连续值，例如：身高属性分为“高”“中等”“矮”，可转化为数值：1，0.5，0。若属性值之间不存在“序关系”，则通常将其转化为向量的形式，例如：性别属性分为“男”“女”，可转化为二维向量：（1，0），（0，1）。（1）当输入属性只有一个的时候，就是最简单的情形，也就是我们高中时最熟悉的“最小二乘法”（Euclidean dista

34、nce），首先计算出每个样本预测值与真实值之间的误差并求和，通过最小化均方误差 MSE，使用求偏导等于零的方法计算出拟合直线 y=wx+b 的两个参数 w 和 b，计算过程如下图所示：（2）当输入属性有多个的时候，例如对于一个样本有 d 个属性（x1,x2xd）,y，则 y=wx+b需要写成：通常对于多元问题，常常使用矩阵的形式来表示数据。在本问题中，将具有 m 个样本的数据集表示成矩阵 X，将系数 w 与 b 合并成一个列向量，这样每个样本的预测值以及所有样本的均方误差最小化就可以写成下面的形式：同样地，我们使用最小二乘法对 w 和 b 进行估计，令均方误差的求导等于 0，需要注意的是，当一

35、个矩阵的行列式不等于 0 时，我们才可能对其求逆，因此对于下式，我们需要考虑矩阵（X的转置*X）的行列式是否为 0，若不为 0，则可以求出其解，若为 0，则需要使用其它的方法进行计算，书中提到了引入正则化，此处不进行深入。另一方面，有时像上面这种原始的线性回归可能并不能满足需求，例如：y 值并不是线性变化，而是在指数尺度上变化。这时我们可以采用线性模型来逼近 y的衍生物，例如 lny，这时衍生的线性模型如下所示，实际上就是相当于将指数曲线投影在一条直线上，如下图所示：更一般地，考虑所有 y 的衍生物的情形，就得到了“广义的线性模型”（generalized linear model），其中，g

36、（*）称为联系函数（link function）。3.23.2 线性几率回归线性几率回归回归就是通过输入的属性值得到一个预测值，利用上述广义线性模型的特征，是否可以通过一个联系函数，将预测值转化为离散值从而进行分类呢？线性几率回归正是研究这样的问题。对数几率引入了一个对数几率函数（logistic function）,将预测值投影到 0-1 之间，从而将线性回归问题转化为二分类问题。若将 y 看做样本为正例的概率，（1-y）看做样本为反例的概率，则上式实际上使用线性回归模型的预测结果器逼近真实标记的对数几率。因此这个模型称为“对数几率回归”（logisticregression），也有一些书籍

37、称之为“逻辑回归”。下面使用最大似然估计的方法来计算出 w和 b 两个参数的取值，下面只列出求解的思路，不列出具体的计算过程。3.33.3 线性判别分析线性判别分析线性判别分析（Linear Discriminant Analysis，简称 LDA）,其基本思想是：将训练样本投影到一条直线上，使得同类的样例尽可能近，不同类的样例尽可能远。如图所示：想让同类样本点的投影点尽可能接近，不同类样本点投影之间尽可能远，即：让各类的协方差之和尽可能小，不用类之间中心的距离尽可能大。基于这样的考虑，LDA 定义了两个散度矩阵。类内散度矩阵（within-class scatter matrix）类间散度矩

38、阵(between-class scaltter matrix)因此得到了 LDA 的最大化目标：“广义瑞利商”（generalized Rayleigh quotient）。从而分类问题转化为最优化求解 w 的问题，当求解出 w 后，对新的样本进行分类时，只需将该样本点投影到这条直线上，根据与各个类别的中心值进行比较，从而判定出新样本与哪个类别距离最近。求解 w 的方法如下所示，使用的方法为乘子。若将 w 看做一个投影矩阵，类似 PCA 的思想，则 LDA 可将样本投影到 N-1 维空间（N 为类簇数），投影的过程使用了类别信息（标记信息），因此 LDA 也常被视为一种经典的监督降维技术。3

39、.43.4 多分类学习多分类学习现实中我们经常遇到不只两个类别的分类问题，即多分类问题，在这种情形下，我们常常运用“拆分”的策略，通过多个二分类学习器来解决多分类问题，即将多分类问题拆解为多个二分类问题，训练出多个二分类学习器，最后将多个分类结果进行集成得出结论。最为经典的拆分策略有三种：“一对一”（OvO）、“一对其余”（OvR）和“多对多”（MvM），核心思想与示意图如下所示。OvO：给定数据集 D，假定其中有 N 个真实类别，将这 N 个类别进行两两配对（一个正类/一个反类），从而产生 N（N-1）/2 个二分类学习器，在测试阶段，将新样本放入所有的二分类学习器中测试，得出 N（N-1）

40、个结果，最终通过投票产生最终的分类结果。OvM：给定数据集 D，假定其中有 N 个真实类别，每次取出一个类作为正类，剩余的所有类别作为一个新的反类，从而产生 N 个二分类学习器，在测试阶段，得出 N 个结果，若仅有一个学习器预测为正类，则对应的类标作为最终分类结果。MvM：给定数据集 D，假定其中有 N 个真实类别，每次取若干个类作为正类，若干个类作为反类（通过 ECOC 码给出，编码），若进行了 M 次划分，则生成了 M 个二分类学习器，在测试阶段（解码），得出 M 个结果组成一个新的码，最终通过计算海明/欧式距离选择距离最小的类别作为最终分类结果。3.53.5 类别不平衡问题类别不平衡问题

41、类别不平衡（class-imbanlance）就是指分类问题中不同类别的训练样本相差悬殊的情况，例如正例有 900 个，而反例只有 100 个，这个时候我们就需要进行相应的处理来平衡这个问题。常见的做法有三种：1.在训练样本较多的类别中进行“欠采样”（undersampling）,比如从正例中采出 100 个，常见的算法有：EasyEnsemble。2.在训练样本较少的类别中进行“过采样”（oversampling）,例如通过对反例中的数据进行插值，来产生额外的反例，常见的算法有 SMOTE。3.直接基于原数据集进行学习，对预测值进行“再缩放”处理。其中再缩放也是代价敏感学习的基础。机器学习机

42、器学习 学习笔记（学习笔记（5 5）-决策树决策树上篇主要介绍和讨论了线性模型。首先从最简单的最小二乘法开始，讨论输入属性有一个和多个的情形，接着通过广义线性模型延伸开来，将预测连续值的回归问题转化为分类问题，从而引入了对数几率回归，最后线性判别分析 LDA 将样本点进行投影，多分类问题实质上通过划分的方法转化为多个二分类问题进行求解。本篇将讨论另一种被广泛使用的分类算法决策树（Decision Tree）。4 4、决策树、决策树4.14.1 决策树基本概念决策树基本概念顾名思义，决策树是基于树结构来进行决策的，在网上看到一个例子十分有趣，放在这里正好合适。现想象一位捉急的母亲想要给自己的女娃

43、介绍一个男朋友，于是有了下面的对话：女儿：多大年纪了？母亲：26。女儿：长的帅不帅？母亲：挺帅的。女儿：收入高不？母亲：不算很高，中等情况。女儿：是公务员不？母亲：是，在税务局上班呢。女儿：那好，我去见见。这个女孩的挑剔过程就是一个典型的决策树，即相当于通过年龄、长相、收入和是否公务员将男童鞋分为两个类别：见和不见。假设这个女孩对男人的要求是：30 岁以下、长相中等以上并且是高收入者或中等以上收入的公务员，那么使用下图就能很好地表示女孩的决策逻辑（即一颗决策树）。在上图的决策树中，决策过程的每一次判定都是对某一属性的“测试”，决策最终结论则对应最终的判定结果。一般一颗决策树包含：一个根节点、若

44、干个内部节点和若干个叶子节点，易知：*每个非叶节点表示一个特征属性测试。*每个分支代表这个特征属性在某个值域上的输出。*每个叶子节点存放一个类别。*每个节点包含的样本集合通过属性测试被划分到子节点中，根节点包含样本全集。4.24.2 决策树的构造决策树的构造决策树的构造是一个递归的过程，有三种情形会导致递归返回：(1)当前结点包含的样本全属于同一类别，这时直接将该节点标记为叶节点，并设为相应的类别；(2)当前属性集为空，或是所有样本在所有属性上取值相同，无法划分，这时将该节点标记为叶节点，并将其类别设为该节点所含样本最多的类别；(3)当前结点包含的样本集合为空，不能划分，这时也将该节点标记为叶

45、节点，并将其类别设为父节点中所含样本最多的类别。算法的基本流程如下图所示：可以看出：决策树学习的关键在于如何选择划分属性，不同的划分属性得出不同的分支结构，从而影响整颗决策树的性能。属性划分的目标是让各个划分出来的子节点尽可能地“纯”，即属于同一类别。因此下面便是介绍量化纯度的具体方法，决策树最常用的算法有三种：ID3，C4.5 和 CART。4.2.14.2.1 ID3ID3 算法算法ID3 算法使用信息增益为准则来选择划分属性，“信息熵”(information entropy)是度量样本结合纯度的常用指标，假定当前样本集合 D 中第 k 类样本所占比例为 pk，则样本集合 D 的信息熵信

46、息熵定义为：假定通过属性划分样本集 D，产生了 V 个分支节点，v 表示其中第 v 个分支节点，易知：分支节点包含的样本数越多，表示该分支节点的影响力越大。故可以计算出划分后相比原始数据集D 获得的“信息增益信息增益”（information gain）。信息增益越大，表示使用该属性划分样本集 D 的效果越好，因此 ID3 算法在递归过程中，每次选择最大信息增益的属性作为当前的划分属性。4.2.24.2.2 C4.5C4.5 算法算法ID3 算法存在一个问题，就是偏向于取值数目较多的属性，例如：如果存在一个唯一标识，这样样本集 D 将会被划分为|D|个分支，每个分支只有一个样本，这样划分后的信

47、息熵为零，十分纯净，但是对分类毫无用处。因此 C4.5 算法使用了“增益率”（gain ratio）来选择划分属性，来避免这个问题带来的困扰。首先使用 ID3 算法计算出信息增益高于平均水平的候选属性，接着 C4.5 计算这些候选属性的增益率，增益率增益率定义为：4.2.34.2.3 CARTCART 算法算法CART 决策树使用“基尼指数”（Gini index）来选择划分属性，基尼指数反映的是从样本集 D中随机抽取两个样本，其类别标记不一致的概率，因此 Gini(D)越小越好，基尼指数定义如下：进而，使用属性划分后的基尼指数为：4.34.3 剪枝处理剪枝处理从决策树的构造流程中我们可以直观

48、地看出：不管怎么样的训练集，决策树总是能很好地将各个类别分离开来，这时就会遇到之前提到过的问题：过拟合（overfitting），即太依赖于训练样本。剪枝（pruning）则是决策树算法对付过拟合的主要手段，剪枝的策略有两种如下：*预剪枝（prepruning）：在构造的过程中先评估，再考虑是否分支。*后剪枝（post-pruning）：在构造好一颗完整的决策树后，自底向上，评估分支的必要性。评估指的是性能度量，即决策树的泛化性能。之前提到：可以使用测试集作为学习器泛化性能的近似，因此可以将数据集划分为训练集和测试集。预剪枝表示在构造数的过程中，对一个节点考虑是否分支时，首先计算决策树不分支时

49、在测试集上的性能，再计算分支之后的性能，若分支对性能没有提升，则选择不分支（即剪枝）。后剪枝则表示在构造好一颗完整的决策树后，从最下面的节点开始，考虑该节点分支对模型的性能是否有提升，若无则剪枝，即将该节点标记为叶子节点，类别标记为其包含样本最多的类别。上图分别表示不剪枝处理的决策树、预剪枝决策树和后剪枝决策树。预剪枝处理使得决策树的很多分支被剪掉，因此大大降低了训练时间开销，同时降低了过拟合的风险，但另一方面由于剪枝同时剪掉了当前节点后续子节点的分支，因此预剪枝“贪心”的本质阻止了分支的展开，在一定程度上带来了欠拟合的风险。而后剪枝则通常保留了更多的分支，因此采用后剪枝策略的决策树性能往往优

50、于预剪枝，但其自底向上遍历了所有节点，并计算性能，训练时间开销相比预剪枝大大提升。4.44.4 连续值与缺失值处理连续值与缺失值处理对于连续值的属性，若每个取值作为一个分支则显得不可行，因此需要进行离散化处理，常用的方法为二分法，基本思想为：给定样本集 D 与连续属性，二分法试图找到一个划分点 t将样本集 D 在属性上分为t 与t。*首先将的所有取值按升序排列，所有相邻属性的均值作为候选划分点（n-1 个，n 为所有的取值数目）。*计算每一个划分点划分集合 D（即划分为两个分支）后的信息增益。*选择最大信息增益的划分点作为最优划分点。现实中常会遇到不完整的样本，即某些属性值缺失。有时若简单采取