机器学习入门基础（微课版）课件 黄海广 第7-15章-机器学习实践 -关联规则

机器学习-机器学习实践

01数据集划分02评价指标03正则化、偏差和方差本章目录01数据集划分02评价指标1.数据集划分03正则化、偏差和方差训练集（TrainingSet）：帮助我们训练模型，简单的说就是通过训练集的数据让我们确定拟合曲线的参数。

验证集（ValidationSet）：也叫做开发集（DevSet），用来做模型选择（modelselection），即做模型的最终优化及确定的，用来辅助我们的模型的构建，即训练超参数，可选；测试集（TestSet）：为了测试已经训练好的模型的精确度。三者划分：训练集、验证集、测试集机器学习：60%，20%，20%；70%，10%，20%深度学习：98%，1%，1%（假设百万条数据）1.数据集划分数据集训练集验证集测试集交叉验证1.使用训练集训练出k个模型2.用k个模型分别对交叉验证集计算得出交叉验证误差（代价函数的值）3.选取代价函数值最小的模型4.用步骤3中选出的模型对测试集计算得出推广误差（代价函数的值）数据不平衡是指数据集中各类样本数量不均衡的情况.常用不平衡处理方法有采样和代价敏感学习采样欠采样、过采样和综合采样的方法不平衡数据的处理SMOTE(SyntheticMinorityOver-samplingTechnique)算法是过采样中比较常用的一种。算法的思想是合成新的少数类样本，而不是简单地复制样本。算法过程如图：不平衡数据的处理（a）原始样本（b）选定少类样本

（d）增加样本代价敏感学习不平衡数据的处理代价敏感学习是指为不同类别的样本提供不同的权重，从而让机器学习模型进行学习的一种方法比如风控或者入侵检测，这两类任务都具有严重的数据不平衡问题，可以在算法学习的时候，为少类样本设置更高的学习权重，从而让算法更加专注于少类样本的分类情况，提高对少类样本分类的查全率，但是也会将很多多类样本分类为少类样本，降低少类样本分类的查准率。01数据集划分02评价指标2.评价指标03正则化、偏差和方差预测值PositiveNegtive实际值PositiveTPFNNegtiveFPTN1.正确肯定（TruePositive,TP）：

预测为真，实际为真2.正确否定（TrueNegative,TN）：预测为假，实际为假3.错误肯定（FalsePositive,FP）：

预测为真，实际为假4.错误否定（FalseNegative,FN）：预测为假，实际为真混淆矩阵（confusion_matrix）评价指标

评价指标有100张照片，其中，猫的照片有60张，狗的照片是40张。输入这100张照片进行二分类识别，找出这100张照片中的所有的猫。正例（Positives）：识别对的负例（Negatives）：识别错的

预测值PositiveNegtive实际值PositiveTP=40FN=20NegtiveFP=10TN=30识别结果的混淆矩阵评价指标

正确率（Accuracy）=(TP+TN)/STP+TN=70，S=100，则正确率为：Accuracy=70/100=0.7

精度（Precision）=TP/(TP+FP)TP=40，TP+FP=50。Precision=40/50=0.8

召回率（Recall）=TP/(TP+FN)TP=40，TP+FN=60。则召回率为：Recall=40/60=0.67项目符号猫狗的例子识别出的正例TP+FP40+10=50识别出的负例TN+FN30+20=50总识别样本数TP+FP+TN+FN50+50=100识别对了的正例与负例真正例+真负例=TP+TN40+30=70识别错了的正例与负例伪正例+伪负例=FP+FN10+20=30实际总正例数量真正例+伪负例=TP+FN40+20=60实际总负例数量真负例+伪正例=TN+FP30+10=40评价指标ROC和PR曲线01数据集划分02评价指标3.正则化、偏差和方差03正则化、偏差和方差

梯度

梯度为什么要标准化/归一化？提升模型精度：不同维度之间的特征在数值上有一定比较性，可以大大提高分类器的准确性。加速模型收敛：最优解的寻优过程明显会变得平缓，更容易正确的收敛到最优解。3.正则化、偏差和方差w1w1w2Jw1w2Jw1w2w2BeforeNormalizationAfterNormalizationx1x2r=1x1x2Normalization3.正则化、偏差和方差归一化（最大-最小规范化）

将数据映射到[0,1]区间Z-Score标准化

处理后的数据均值为0，方差为1数据归一化的目的是使得各特征对目标变量的影响一致，会将特征数据进行伸缩变化，所以数据归一化是会改变特征数据分布的。数据标准化为了不同特征之间具备可比性，经过标准化变换之后的特征数据分布没有发生改变。就是当数据特征取值范围或单位差异较大时，最好是做一下标准化处理。3.正则化、偏差和方差需要做数据归一化/标准化线性模型，如基于距离度量的模型包括KNN(K近邻)、K-means聚类、感知机和SVM、神经网络。另外，线性回归类的几个模型一般情况下也是需要做数据归一化/标准化处理的。不需要做数据归一化/标准化决策树、基于决策树的Boosting和Bagging等集成学习模型对于特征取值大小并不敏感，如随机森林、XGBoost、LightGBM等树模型，以及朴素贝叶斯，以上这些模型一般不需要做数据归一化/标准化处理。3.正则化、偏差和方差过拟合和欠拟合欠拟合过拟合正合适过拟合的处理1.获得更多的训练数据使用更多的训练数据是解决过拟合问题最有效的手段，因为更多的样本能够让模型学习到更多更有效的特征，减小噪声的影响。2.降维即丢弃一些不能帮助我们正确预测的特征。可以是手工选择保留哪些特征，或者使用一些模型选择的算法来帮忙（例如PCA）。3.正则化正则化(regularization)的技术，保留所有的特征，但是减少参数的大小（magnitude），它可以改善或者减少过拟合问题。4.集成学习方法集成学习是把多个模型集成在一起，来降低单一模型的过拟合风险。通过这张图可以看出，各种不同算法在输入的数据量达到一定级数后，都有相近的高准确度。于是诞生了机器学习界的名言：成功的机器学习应用不是拥有最好的算法，而是拥有最多的数据！

数据决定一切

数据大小准确率欠拟合的处理1.添加新特征当特征不足或者现有特征与样本标签的相关性不强时，模型容易出现欠拟合。通过挖掘组合特征等新的特征，往往能够取得更好的效果。2.增加模型复杂度简单模型的学习能力较差，通过增加模型的复杂度可以使模型拥有更强的拟合能力。例如，在线性模型中添加高次项，在神经网络模型中增加网络层数或神经元个数等。3.减小正则化系数正则化是用来防止过拟合的，但当模型出现欠拟合现象时，则需要有针对性地减小正则化系数。

正则化

正则化

正则化x[2]x[3]x[1]a[L]DropOut

keep-prob=1(没有dropout)keep-prob=0.5(常用取值，保留一半神经元)在训练阶段使用，在测试阶段不使用！Dropout正则化正则化Earlystopping代表提早停止训练神经网络

正则化大部分的计算机视觉任务使用很多的数据，所以数据增强是经常使用的一种技巧来提高计算机视觉系统的表现。计算机视觉任务的数据增强通常以下方法实现：(1)随意翻转、镜像。(2)随意裁剪。(3)扭曲变形图片。(4)颜色转换，然后给R、G和B三个通道上加上不同的失真值。产生大量的样本，进行数据增强。偏差和方差方差Variance：描述的是预测值的变化范围，离散程度，也就是离其期望值的距离。方差越大，数据的分布越分散，如右图右列所示。偏差Bias：描述的是预测值（估计值）的期望与真实值之间的差距。偏差越大，越偏离真实数据，如右图第二行所示。低方差高方差高偏差低偏差偏差和方差总体误差方差偏差2最优模型复杂度模型复杂度误差方差、偏差和模型复杂度右图是模型复杂度与误差的关系，一般来说，随着模型复杂度的增加，方差会逐渐增大，偏差会逐渐减小，在虚线处，差不多是模型复杂度的最恰当的选择，其“偏差”和“方差”也都适度，才能“适度拟合”。偏差和方差训练集误差和交叉验证集误差近似时：偏差/欠拟合交叉验证集误差远大于训练集误差时：方差/过拟合x1x2x1x2x1x2UnderfittingGoodfitOverfitting偏差和方差1.获得更多的训练实例——解决高方差2.尝试减少特征的数量——解决高方差3.尝试获得更多的特征——解决高偏差4.尝试增加多项式特征——解决高偏差5.尝试减少正则化程度λ——解决高偏差6.尝试增加正则化程度λ——解决高方差x1x2参考文献[1]AndrewNg.MachineLearning[EB/OL].StanfordUniversity,2014./course/ml[2]PeterHarrington.机器学习实战[M].北京:人民邮电出版社,2013.[3]TOMMMICHELLE.MachineLearning[M].NewYork:McGraw-HillCompanies,Inc,1997.[4]HastieT.,TibshiraniR.,FriedmanJ.TheElementsofStatisticalLearning[M].NewYork:Springer,2001.[5]CHRISTOPHERM.BISHOP.PatternRecognitionandMachineLearning[M].NewYork:Springer,2006.[6]KohaviR.,ScalinguptheaccuracyofnaïveBayesclassifiers:Adecision-treehybrid[C]//Proceedingsofthe2ndInternationalConferenceonKnowledgeDiscoveryandDataMining(KDD),Portland,OR,202-207,1996.[7]李航.统计学习方法[M].北京:清华大学出版社,2019.[8]CHAWLANV,BOWYERKW,HALLLO,etal.SMOTE:SyntheticMinorityOver-samplingTechnique[J].JournalofArtificialIntelligenceResearch,2002,16:321–357.谢谢！机器学习-KNN算法

01距离度量02KNN算法本章目录03KD树划分04KD树搜索01距离度量02KNN算法03KD树划分04KD树搜索1.距离度量距离度量欧氏距离(Euclideandistance)

电影分类距离度量曼哈顿距离(Manhattandistance)

想象你在城市道路里，要从一个十字路口开车到另外一个十字路口，驾驶距离是两点间的直线距离吗？显然不是，除非你能穿越大楼。实际驾驶距离就是这个“曼哈顿距离”。而这也是曼哈顿距离名称的来源，曼哈顿距离也称为城市街区距离(CityBlockdistance)。距离度量切比雪夫距离(Chebyshevdistance)

二个点之间的距离定义是其各坐标数值差绝对值的最大值。国际象棋棋盘上二个位置间的切比雪夫距离是指王要从一个位子移至另一个位子需要走的步数。由于王可以往斜前或斜后方向移动一格，因此可以较有效率的到达目的的格子。上图是棋盘上所有位置距f6位置的切比雪夫距离。距离度量闵可夫斯基距离(Minkowskidistance)

距离度量汉明距离(Hammingdistance)

汉明距离是使用在数据传输差错控制编码里面的，汉明距离是一个概念，它表示两个（相同长度）字对应位不同的数量，我们以表示两个字之间的汉明距离。对两个字符串进行异或运算，并统计结果为1的个数，那么这个数就是汉明距离。距离度量余弦相似度

01距离度量02KNN算法03KD树划分04KD树搜索2.KNN算法2.KNN算法

2.KNN算法

2.KNN算法算法流程如下：1.计算测试对象到训练集中每个对象的距离2.按照距离的远近排序3.选取与当前测试对象最近的k的训练对象，作为该测试对象的邻居4.统计这k个邻居的类别频次5.k个邻居里频次最高的类别，即为测试对象的类别K=3K=501距离度量02KNN算法03KD树划分04KD树搜索3.K-D-Tree划分KD树划分

①KD树划分

①②②KD树划分

①②②③③KD树划分

①②②③③④KD树划分

①③③④②②KD树划分

样本空间结构图01距离度量02KNN算法03KD树划分04KD树搜索4.K-D-Tree搜索KD树搜索

1.首先要找到该目标点的叶子节点，然后以目标点为圆心，目标点到叶子节点的距离为半径，建立一个超球体，我们要找寻的最近邻点一定是在该球体内部。搜索（4,4）的最近邻时。首先从根节点（6,4）出发，将当前最近邻设为（6,4），对该KD树作深度优先遍历。以（4,4）为圆心，其到（6,4）的距离为半径画圆（多维空间为超球面），可以看出（7,2）右侧的区域与该圆不相交，所以（7,2）的右子树全部忽略。KD树搜索

2.返回叶子结点的父节点，检查另一个子结点包含的超矩形体是否和超球体相交，如果相交就到这个子节点寻找是否有更加近的近邻,有的话就更新最近邻。接着走到（6,4）左子树根节点（4,5），与原最近邻对比距离后，更新当前最近邻为（4,5）。以（4,4）为圆心，其到（4,5）的距离为半径画圆，发现（6,4）右侧的区域与该圆不相交，忽略该侧所有节点，这样（6,4）的整个右子树被标记为已忽略。KD树搜索

3.如果不相交直接返回父节点，在另一个子树继续搜索最近邻。4.当回溯到根节点时，算法结束，此时保存的最近邻节点就是最终的最近邻。遍历完（4,5）的左右叶子节点，发现与当前最优距离相等，不更新最近邻。所以（4,4）的最近邻为（4,5）。参考文献[1]AndrewNg.MachineLearning[EB/OL].StanfordUniversity,2014./course/ml[2]李航.统计学习方法[M].北京:清华大学出版社,2019.[3]周志华.机器学习[M].北京:清华大学出版社,2016.[4]CoverTM,HartPE.Nearestneighborpatternclassification[J].IEEETrans.inf.theory,1953,13(1):21-27.[5]HastieT.,TibshiraniR.,FriedmanJ.TheElementsofStatisticalLearning[M].NewYork:Springer,2001.[6]CHRISTOPHERM.BISHOP.PatternRecognitionandMachineLearning[M].NewYork:Springer,2006.[7]StephenBoyd,LievenVandenberghe,ConvexOptimization[M].Cambridge:CambridgeUniversityPress,2004.谢谢！机器学习-决策树

本章目录01

决策树原理02ID3算法03C4.5算法04

CART算法1.决策树原理01

决策树原理02ID3算法03C4.5算法04

CART算法长相能帅不帅家庭背景好能不好人品好上进心能不能有无不能不好1.决策树原理决策树：从训练数据中学习得出一个树状结构的模型。决策树属于判别模型。决策树是一种树状结构，通过做出一系列决策（选择）来对数据进行划分，这类似于针对一系列问题进行选择。决策树的决策过程就是从根节点开始，测试待分类项中对应的特征属性，并按照其值选择输出分支，直到叶子节点，将叶子节点的存放的类别作为决策结果。根节点

(rootnode)叶节点(leafnode)1.决策树原理根节点(rootnode)非叶子节点

(non-leafnode)(代表测试条件，对数据属性的测试)分支

(branches)

(代表测试结果)叶节点(leafnode)(代表分类后所获得的分类标记)决策树算法是一种归纳分类算法，它通过对训练集的学习，挖掘出有用的规则，用于对新数据进行预测。决策树算法属于监督学习方法。决策树归纳的基本算法是贪心算法，自顶向下来构建决策树。贪心算法：在每一步选择中都采取在当前状态下最好/优的选择。在决策树的生成过程中，分割方法即属性选择的度量是关键。1.决策树原理优点：推理过程容易理解，计算简单，可解释性强。比较适合处理有缺失属性的样本。可自动忽略目标变量没有贡献的属性变量，也为判断属性变量的重要性，减少变量的数目提供参考。缺点：容易造成过拟合，需要采用剪枝操作。忽略了数据之间的相关性。对于各类别样本数量不一致的数据，信息增益会偏向于那些更多数值的特征。决策树的特点算法支持模型树结构特征选择连续值处理缺失值处理剪枝特征属性多次使用ID3分类多叉树信息增益不支持不支持不支持不支持C4.5分类多叉树信息增益率支持支持支持不支持CART分类回归二叉树基尼指数均方差支持支持支持支持1.决策树原理决策树的三种基本类型建立决策树的关键，即在当前状态下选择哪个属性作为分类依据。根据不同的目标函数，建立决策树主要有一下三种算法：ID3(IterativeDichotomiser)、C4.5、CART(ClassificationAndRegressionTree)。2.ID3算法01

决策树原理02ID3算法03C4.5算法04

CART算法2.ID3算法ID3算法最早是由罗斯昆（J.RossQuinlan）于1975年提出的一种决策树构建算法，算法的核心是“信息熵”，期望信息越小，信息熵越大，样本纯度越低。。ID3算法是以信息论为基础，以信息增益为衡量标准，从而实现对数据的归纳分类。ID3算法计算每个属性的信息增益，并选取具有最高增益的属性作为给定的测试属性。ID3算法2.ID3算法ID3算法其大致步骤为：初始化特征集合和数据集合；计算数据集合信息熵和所有特征的条件熵，选择信息增益最大的特征作为当前决策节点；更新数据集合和特征集合（删除上一步使用的特征，并按照特征值来划分不同分支的数据集合）；重复2，3两步，若子集值包含单一特征，则为分支叶子节点。

信息熵

信息熵

右边数据中：

数量是否信息熵15960.971年龄有工作有房子信用类别0青年否否一般否1青年否否好否2青年是否好是3青年是是一般是4青年否否一般否5中年否否一般否6中年否否好否7中年是是好是8中年否是非常好是9中年否是非常好是10老年否是非常好是11老年否是好是12老年是否好是13老年是否非常好是14老年否否一般否按年龄划分信息熵

年龄有工作有房子信用类别0青年否否一般否1青年否否好否2青年是否好是3青年是是一般是4青年否否一般否5中年否否一般否6中年否否好否7中年是是好是8中年否是非常好是9中年否是非常好是10老年否是非常好是11老年否是好是12老年是否好是13老年是否非常好是14老年否否一般否

年龄数量是否信息熵青年5230.9710中年5320.9710老年5410.7219

年龄有工作有房子信用

条件熵

条件熵

年龄有工作有房子信用类别0青年否否一般否1青年否否好否2青年是否好是3青年是是一般是4青年否否一般否5中年否否一般否6中年否否好否7中年是是好是8中年否是非常好是9中年否是非常好是10老年否是非常好是11老年否是好是12老年是否好是13老年是否非常好是14老年否否一般否

信息增益

信息增益

年龄有工作有房子信用类别0青年否否一般否1青年否否好否2青年是否好是3青年是是一般是4青年否否一般否5中年否否一般否6中年否否好否7中年是是好是8中年否是非常好是9中年否是非常好是10老年否是非常好是11老年否是好是12老年是否好是13老年是否非常好是14老年否否一般否ID3算法缺点ID3没有剪枝策略，容易过拟合；信息增益准则对可取值数目较多的特征有所偏好，类似“编号”的特征其信息增益接近于1；只能用于处理离散分布的特征；没有考虑缺失值。3.C4.5算法01

决策树原理02ID3算法03C4.5算法04

CART算法3.C4.5算法C4.5算法C4.5算法是Ross对ID3算法的改进。用信息增益率来选择属性。ID3选择属性用的是子树的信息增益，而C4.5用的是信息增益率。在决策树构造过程中进行剪枝。对非离散数据也能处理。能够对不完整数据进行处理。

备注：信息增益信息增益率信息增益率

年龄有工作有房子信用类别0青年否否一般否1青年否否好否2青年是否好是3青年是是一般是4青年否否一般否5中年否否一般否6中年否否好否7中年是是好是8中年否是非常好是9中年否是非常好是10老年否是非常好是11老年否是好是12老年是否好是13老年是否非常好是14老年否否一般否

C4.5的剪枝过拟合的原因：为了尽可能正确分类训练样本，节点的划分过程会不断重复直到不能再分，这样就可能对训练样本学习的“太好”了，把训练样本的一些特点当做所有数据都具有的一般性质，从而导致过拟合。剪枝的基本策略有“预剪枝”（prepruning）和“后剪枝”（post-pruning）通过剪枝处理去掉一些分支来降低过拟合的风险。C4.5的剪枝预剪枝（prepruning）预剪枝不仅可以降低过拟合的风险而且还可以减少训练时间，但另一方面它是基于“贪心”策略，会带来欠拟合风险。编号色泽根蒂敲声纹理脐部触感好瓜1青绿蜷缩浊响清晰凹陷硬滑是2乌黑蜷缩沉闷清晰凹陷硬滑是3乌黑蜷缩浊响清晰凹陷硬滑是6青绿稍蜷浊响清晰稍凹软粘是7乌黑稍蜷浊响稍糊稍凹软粘是10青绿硬挺清脆清晰平坦软粘否14浅白稍蜷沉闷稍糊凹陷硬滑否15乌黑稍蜷浊响清晰稍凹软粘否16浅白蜷缩浊响模糊平坦硬滑否17青绿蜷缩沉闷稍糊稍凹硬滑否编号色泽根蒂敲声纹理脐部触感好瓜4青绿蜷缩沉闷清晰凹陷硬滑是5浅白蜷缩浊响清晰凹陷硬滑是8乌黑稍蜷浊响清晰稍凹硬滑是9乌黑稍蜷沉闷稍糊稍凹硬滑否11浅白硬挺清脆模糊平坦硬滑否12浅白蜷缩浊响模糊平坦软粘否13青绿稍蜷浊响稍糊凹陷硬滑否训练集验证集C4.5的剪枝预剪枝基于表生成未剪枝的决策树平坦纹理色泽好瓜坏瓜根蒂色泽脐部坏瓜坏瓜坏瓜坏瓜好瓜好瓜好瓜好瓜好瓜乌黑凹陷硬挺稍糊清晰蜷曲稍蜷模糊青绿稍凹浅白青绿乌黑浅白①⑥⑤④③②剪枝策略在节点划分前来确定是否继续增长，及早停止增长主要方法有：节点内数据样本低于某一阈值；所有节点特征都已分裂；节点划分前准确率比划分后准确率高。C4.5的剪枝预剪枝平坦坏瓜脐部凹陷稍凹①④③②好瓜好瓜验证集精度脐部=?划分前:42.9%划分后:71.4%预剪枝决策:划分验证集精度根蒂=?划分前:71.4%划分后:71.4%预剪枝决策:禁止划分验证集精度色泽=?划分前:71.4%划分后:57.1%预剪枝决策:禁止划分{1,2,3,14}{6,7,15,17}{10,16}剪枝策略在节点划分前来确定是否继续增长，及早停止增长主要方法有：节点内数据样本低于某一阈值；所有节点特征都已分裂；节点划分前准确率比划分后准确率高。预剪枝的决策树C4.5的剪枝后剪枝编号色泽根蒂敲声纹理脐部触感好瓜1青绿蜷缩浊响清晰凹陷硬滑是2乌黑蜷缩沉闷清晰凹陷硬滑是3乌黑蜷缩浊响清晰凹陷硬滑是6青绿稍蜷浊响清晰稍凹软粘是7乌黑稍蜷浊响稍糊稍凹软粘是10青绿硬挺清脆清晰平坦软粘否14浅白稍蜷沉闷稍糊凹陷硬滑否15乌黑稍蜷浊响清晰稍凹软粘否16浅白蜷缩浊响模糊平坦硬滑否17青绿蜷缩沉闷稍糊稍凹硬滑否编号色泽根蒂敲声纹理脐部触感好瓜4青绿蜷缩沉闷清晰凹陷硬滑是5浅白蜷缩浊响清晰凹陷硬滑是8乌黑稍蜷浊响清晰稍凹硬滑是9乌黑稍蜷沉闷稍糊稍凹硬滑否11浅白硬挺清脆模糊平坦硬滑否12浅白蜷缩浊响模糊平坦软粘否13青绿稍蜷浊响稍糊凹陷硬滑否训练集验证集在已经生成的决策树上进行剪枝，从而得到简化版的剪枝决策树。后剪枝决策树通常比预剪枝决策树保留了更多的分支。一般情况下，后剪枝的欠拟合风险更小，泛化性能往往优于预剪枝决策树。C4.5的剪枝后剪枝基于表生成未剪枝的决策树平坦纹理色泽好瓜坏瓜根蒂色泽脐部坏瓜坏瓜坏瓜坏瓜好瓜好瓜好瓜好瓜好瓜乌黑凹陷硬挺稍糊清晰蜷曲稍蜷模糊青绿稍凹浅白青绿乌黑浅白①⑥⑤④③②{6,7,15}{7,15}{1,2,3,14}剪枝方法在已经生成的决策树上进行剪枝，从而得到简化版的剪枝决策树。C4.5采用的悲观剪枝方法，用递归的方式从低往上针对每一个非叶子节点，评估用一个最佳叶子节点去代替这课子树是否有益。如果剪枝后与剪枝前相比其错误率是保持或者下降，则这棵子树就可以被替换掉。C4.5通过训练数据集上的错误分类数量来估算未知样本上的错误率。后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树。C4.5的剪枝后剪枝后剪枝的决策树剪枝方法在已经生成的决策树上进行剪枝，从而得到简化版的剪枝决策树。C4.5采用的悲观剪枝方法，用递归的方式从低往上针对每一个非叶子节点，评估用一个最佳叶子节点去代替这课子树是否有益。如果剪枝后与剪枝前相比其错误率是保持或者下降，则这棵子树就可以被替换掉。C4.5通过训练数据集上的错误分类数量来估算未知样本上的错误率。后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树。平坦色泽好瓜坏瓜根蒂脐部坏瓜坏瓜好瓜好瓜好瓜凹陷硬挺蜷曲稍蜷稍凹浅白青绿乌黑①⑥⑤④③②{1,2,3,14}{7,15}原分支“色泽”的验证集精度剪枝前:57.1%剪枝后:71.4%后剪枝决策:剪枝原分支“纹理”的验证集精度剪枝前:42.9%剪枝后:57.1%后剪枝决策:剪枝C4.5的缺点缺点剪枝策略可以再优化；C4.5用的是多叉树，用二叉树效率更高；C4.5只能用于分类；C4.5使用的熵模型拥有大量耗时的对数运算，连续值还有排序运算；C4.5在构造树的过程中，对数值属性值需要按照其大小进行排序，从中选择一个分割点，所以只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时，程序无法运行。4.CART算法01

决策树原理02ID3算法03C4.5算法04

CART算法4.CART算法CARTClassificationandRegressionTree(CART)是决策树的一种。用基尼指数来选择属性（分类），或用均方差来选择属性（回归）。顾名思义，CART算法既可以用于创建分类树，也可以用于创建回归树，两者在构建的过程中稍有差异。如果目标变量是离散的，称为分类树。如果目标变量是连续的，称为回归树。CART算法-分类连续特征处理…………

…………第1次划分

第2次划分

CART算法-分类离散特征处理……………………第1次划分

第2次划分

CART的特征会多次参与节点的建立，而在ID3或C4.5的一颗子树中，离散特征只会参与一次节点的建立。房子是否工作是有无3,7,8,9,10,110,1,2,4,5,6,12,13,144,12,130,1,5,6,14

CART算法-分类基尼指数

年龄有工作有房子信用类别0青年否否一般否1青年否否好否2青年是否好是3青年是是一般是4青年否否一般否5中年否否一般否6中年否否好否7中年是是好是8中年否是非常好是9中年否是非常好是10老年否是非常好是11老年否是好是12老年是否好是13老年是否非常好是14老年否否一般否分类时用基尼指数来选择属性粗垂直线表示根节点的决策边界（深度0）：花瓣长度=2.45厘米。由于左侧区域是纯净的（仅Iris-Setosa），因此无法进一步拆分。然而，右侧区域是不纯的，因此深度为1的右侧节点将其分割成花瓣宽度=1.75厘米（由虚线表示）。由于max_depth设置为2，因此决策树会在那里停止。但是，如果将max_depth设置为3，那么两个深度为2的节点将各自添加另一个决策边界（由点虚线表示）。150个鸢尾花样本进行分类，特征为花萼的长度和宽度决策树原理CART算法-回归

CART算法-回归预测方式对于决策树建立后做预测的方式，上面讲到了CART分类树采用叶子节点里概率最大的类别作为当前节点的预测类别。而回归树输出不是类别，它采用的是用最终叶子的均值或者中位数来预测输出结果。CART剪枝CART算法采用一种“基于代价复杂度的剪枝”方法进行后剪枝，这种方法会生成一系列树，每个树都是通过将前面的树的某个或某些子树替换成一个叶节点而得到的，这一系列树中的最后一棵树仅含一个用来预测类别的叶节点。然后用一种成本复杂度的度量准则来判断哪棵子树应该被一个预测类别值的叶节点所代替。这种方法需要使用一个单独的测试数据集来评估所有的树，根据它们在测试数据集熵的分类性能选出最佳的树。CART算法CART剪枝具体流程:(1)计算每一个结点的条件熵(2)递归的从叶子节点开始往上遍历,减掉叶子节点,然后判断损失函数的值是否减少,如果减少,则将父节点作为新的叶子节点(3)重复(2),直到完全不能剪枝.平坦纹理色泽好瓜坏瓜根蒂色泽脐部坏瓜坏瓜坏瓜坏瓜好瓜好瓜好瓜好瓜好瓜乌黑凹陷硬挺稍糊清晰蜷曲稍蜷模糊青绿稍凹浅白青绿乌黑浅白①⑥⑤④③②决策树差异总结划分标准的差异：ID3使用信息增益偏向特征值多的特征，C4.5使用信息增益率克服信息增益的缺点，偏向于特征值小的特征，CART使用基尼指数克服C4.5需要求log的巨大计算量，偏向于特征值较多的特征。使用场景的差异：ID3和C4.5都只能用于分类问题，CART可以用于分类和回归问题；ID3和C4.5是多叉树，速度较慢，CART是二叉树，计算速度很快；样本数据的差异：ID3只能处理离散数据且缺失值敏感，C4.5和CART可以处理连续性数据且有多种方式处理缺失值；从样本量考虑的话，小样本建议C4.5、大样本建议CART。C4.5处理过程中需对数据集进行多次扫描排序，处理成本耗时较高，而CART本身是一种大样本的统计方法，小样本处理下泛化误差较大；样本特征的差异：ID3和C4.5层级之间只使用一次特征，CART可多次重复使用特征；剪枝策略的差异：ID3没有剪枝策略，C4.5是通过悲观剪枝策略来修正树的准确性，而CART是通过代价复杂度剪枝。参考文献

[1]QUINLANJR.Introductionofdecisiontrees[J].MachineLearning,1986,1(1):81-106.[2]QUINLANJR.C4.5:programsformachinelearning[M].Boston:MorganKaufmann,1993.[3]BREIMANL,FRIEDMANJH,OLSHENRA,etal.Classificationandregressiontrees[M].NewYork:ChapmanandHall/CRC,1984[4]李航.统计学习方法[M].北京:清华大学出版社,2019.[5]周志华.机器学习[M].北京:清华大学出版社,2016.[6]HastieT.,TibshiraniR.,FriedmanJ.TheElementsofStatisticalLearning[M].NewYork:Springer,2001.[7]PeterHarrington.机器学习实战[M].北京:人民邮电出版社,2013.[8]CHRISTOPHERM.BISHOP.PatternRecognitionandMachineLearning[M].NewYork:Springer,2006.谢谢！机器学习-集成学习

本章目录01

集成学习方法概述02AdaBoost和GBDT算法03XGBoost04LightGBM1.集成学习方法概述01

集成学习方法概述02AdaBoost和GBDT算法03XGBoost04LightGBMBagging从训练集中进行子抽样组成每个基模型所需要的子训练集，对所有基模型预测的结果进行综合产生最终的预测结果：集成学习模型n……模型1模型2预测n……预测1预测2训练数据最终预测结果测试数据Boosting训练过程为阶梯状，基模型按次序一一进行训练（实现上可以做到并行），基模型的训练集按照某种策略每次都进行一定的转化。对所有基模型预测的结果进行线性综合产生最终的预测结果。集成学习模型n最终预测结果模型2预测n……预测1预测2转化模型1模型3转化转化训练数据测试数据集成学习模型n……模型1模型2预测n……预测1预测2训练数据第二层数据Stacking最终预测结果Stacking将训练好的所有基模型对训练基进行预测，第j个基模型对第i个训练样本的预测值将作为新的训练集中第i个样本的第j个特征值，最后基于新的训练集进行训练。同理，预测的过程也要先经过所有基模型的预测形成新的测试集，最后再对测试集进行预测。测试数据RandomForest（随机森林）用随机的方式建立一个森林。随机森林算法由很多决策树组成，每一棵决策树之间没有关联。建立完森林后，当有新样本进入时，每棵决策树都会分别进行判断，然后基于投票法给出分类结果。优点在数据集上表现良好，相对于其他算法有较大的优势易于并行化，在大数据集上有很大的优势；能够处理高维度数据，不用做特征选择。随机森林RandomForest（随机森林）是Bagging的扩展变体，它在以决策树为基学习器构建Bagging集成的基础上，进一步在决策树的训练过程中引入了随机特征选择，因此可以概括随机森林包括四个部分：随机选择样本（放回抽样）；随机选择特征；构建决策树；随机森林投票（平均）。随机森林训练数据Bootstrap随机抽取决策树1最终预测结果测试数据决策树n……决策树2预测1预测n……预测2随机选择样本和Bagging相同，采用的是Bootstraping自助采样法；随机选择特征是指在每个节点在分裂过程中都是随机选择特征的（区别与每棵树随机选择一批特征）。这种随机性导致随机森林的偏差会有稍微的增加（相比于单棵不随机树），但是由于随机森林的“平均”特性，会使得它的方差减小，而且方差的减小补偿了偏差的增大，因此总体而言是更好的模型。随机森林数据集自助采样自助采样自助采样Bootstraping2.AdaBoost和GBDT算法01

集成学习方法概述02AdaBoost和GBDT算法03XGBoost04LightGBMAdaBoost算法AdaBoost（AdaptiveBoosting，自适应增强），其自适应在于：前一个基本分类器分错的样本会得到加强，加权后的全体样本再次被用来训练下一个基本分类器。同时，在每一轮中加入一个新的弱分类器，直到达到某个预定的足够小的错误率或达到预先指定的最大迭代次数。后一个模型的训练永远是在前一个模型的基础上完成！Adaboost算法算法思想初始化训练样本的权值分布，每个样本具有相同权重；训练弱分类器，如果样本分类正确，则在构造下一个训练集中，它的权值就会被降低；反之提高。用更新过的样本集去训练下一个分类器；将所有弱分类组合成强分类器，各个弱分类器的训练过程结束后，加大分类误差率小的弱分类器的权重，降低分类误差率大的弱分类器的权重。AdaBoost算法弱分类器1权重提高弱分类器3权重提高弱分类器2弱分类器组成了强分类器Adaboost算法算法思想：后一个模型的训练永远是在前一个模型的基础上完成模型n模型1模型2带权重n的训练集带权重2的训练集带权重1的训练集训练数据结合策略弱学习器1基于学习的误差率1更新学习器权重1弱学习器2基于学习的误差率2更新学习器权重2弱学习器n基于学习的误差率n更新学习器权重n根据权重1更新样本权重2根据权重n-1更新样本权重n强学习器相同方式更新……GBDT算法GBDT（GradientBoostingDecisionTree）是一种迭代的决策树算法，该算法由多棵决策树组成，GBDT的核心在于累加所有树的结果作为最终结果，所以GBDT中的树都是回归树，不是分类树，它是属于Boosting策略。GBDT是被公认的泛化能力较强的算法。GBDT由三个概念组成：RegressionDecisionTree（即DT）、GradientBoosting（即GB），和Shrinkage（缩减）

GBDT算法

前向分步算法：

初始化提升树

真实值损失函数备注：损失函数选择：如分类用指数损失函数,回归使用平方误差损失。GBDT算法GBDT算法

前向分步算法：前向分步算法：

回归使用平方误差损失注意：提升树算法中的基学习器CART树是回归树

GBDT算法

GBDT算法

s1.52.53.54.55.56.57.58.59.5m(s)15.7212.078.365.783.911.938.0111.7315.74xy15.5625.735.9146.456.867.0578.988.799109.05GBDT算法

x<6.56.248.91

x<6.5x<3.58.915.726.46

x<3.5-0.520.22

xyy-f(x)15.56-0.6825.7-0.5435.91-0.3346.40.1656.80.5667.050.8178.9-0.0188.7-0.21990.09109.050.14GBDT算法

x<3.50.15-0.22

x<4.5-0.160.11

x<6.50.07-0.11

x<2.5-0.150.04

x<6.5x<4.58.95x<3.5x<2.55.636.836.565.82GBDT算法

损失函数的负梯度在当前模型的值作为提升树的残差的近似值来拟合回归树GBDT算法

GBDT算法01

集成学习方法概述02AdaBoost和GBDT算法03XGBoost04LightGBM3.XGBoost3.XGBoostXGBoost

是大规模并行boostingtree的工具，它是目前最快最好的开源boostingtree工具包，比常见的工具包快10倍以上。XGBoost和GBDT两者都是boosting方法，除了工程实现、解决问题上的一些差异外，最大的不同就是目标函数的定义。

3.XGBoost

3.XGBoost

加入新的预测函数

1,2,34,5,67,8,9

3.XGBoost

3.XGBoost

分数越小，代表这个树的结构越好3.XGBoost

3.XGBoost分裂后左子树分数分裂后右子树分数分裂前左、右子树的分数：不分割可以拿到的分数加入新叶子节点引入的复杂度代价3.XGBoost

XGBoost的分裂方式4.LightGBM01

集成学习方法概述02Adaboost和GBDT算法03XGBoost04LightGBM4.LightGBMLightGBM

由微软提出，主要用于解决GDBT在海量数据中遇到的问题，以便其可以更好更快地用于工业实践中，其相对XGBoost具有训练速度快、内存占用低的特点。LightGBM与XGBoost相比，主要有以下几个优势：1）更快的训练速度2）更低的内存消耗3）更好的准确率4）分布式支持，可快速处理海量数据4.LightGBMLightGBM

的主要改进LightGBM与XGBoost相比，主要有以下几个改进：基于梯度的单边采样算法（Gradient-basedOne-SideSampling,GOSS）；互斥特征捆绑算法（ExclusiveFeatureBundling,EFB）；直方图算法（Histogram）；基于最大深度的Leaf-wise的垂直生长算法；LightGBM=XGBoost+GOSS+EFB+Histogram4.LightGBM基于梯度的单边采样算法（Gradient-basedOne-SideSampling,GOSS）主要思想是通过对样本采样的方法来减少计算目标函数增益时候的复杂度。GOSS算法保留了梯度大的样本，并对梯度小的样本进行随机抽样，为了不改变样本的数据分布，在计算增益时为梯度小的样本引入一个常数进行平衡。如果一个样本的梯度很小，说明该样本的训练误差很小，或者说该样本已经得到了很好的训练(well-trained)。4.LightGBM基于梯度的单边采样算法（Gradient-basedOne-SideSampling,GOSS）

4.LightGBM

样本序号样本的特征取值样本的一阶导样本的二阶导123456780.12.12.53.03.04.04.55.00.010.030.060.050.040.70.60.070.20.040.050.020.080.020.030.03binibin1bin2bin31*31*3+110.03*30.05*3+0.70.60.04*30.12*3+0.020.03bin1bin2bin3bin序号bin样本的之和bin内所有样本的一阶导之和bin内所有样本的二阶导之和可能的候选点分裂点个数等于样本取值个数减一

4.LightGBM互斥特征捆绑算法（ExclusiveFeatureBundling,EFB）高维特征往往是稀疏的，而且特征间可能是相互排斥的（如两个特征不同时取非零值），如果两个特征并不完全互斥（如只有一部分情况下是不同时取非零值），可以用互斥率表示互斥程度。EFB算法指出如果将一些特征进行融合绑定，则可以降低特征数量。论文给出特征合并算法，其关键在于原始特征能从合并的特征中分离出来。4.LightGBM互斥特征捆绑算法（ExclusiveFeatureBundling,EFB）高维特征往往是稀疏的，而且特征间可能是相互排斥的（如两个特征不同时取非零值），如果两个特征并不完全互斥（如只有一部分情况下是不同时取非零值），可以用互斥率表示互斥程度。EFB算法指出如果将一些特征进行融合绑定，则可以降低特征数量。1030

20假设Bundle中有两个特征值，A取值为[0,10]，B取值为[0,20]，为了保证特征A、B的互斥性，我们可以给特征B添加一个偏移量转换为C[10,30]，Bundle后的特征其取值为[0,30]，这样便实现了特征合并。4.LightGBM直方图算法

4.直方图算法

123456780.12.12.53.03.04.04.55.00.010.030.060.050.040.70.60.070.20.040.050.020.080.020.030.03样本序号样本的特征取值样本的一阶导样本的二阶导123456780.12.12.53.03.04.04.55.00.010.030.060.050.040.70.60.070.20.040.050.020.080.020.030.03binibin1bin2bin33320.10.790.670.290.120.06bin1bin2bin3bin序号bin样本的之和bin内所有样本的一阶导之和bin内所有样本的二阶导之和可能的候选点分裂点个数等于bins个数减一可能的候选点分裂点个数等于样本取值个数减一4.LightGBM直方图加速在构建叶节点的直方图时，我们还可以通过父节点的直方图与相邻叶节点的直方图相减的方式构建，从而减少了一半的计算量。即：一个叶子节点的直方图可以由它的父亲节点的直方图与其兄弟的直方图做差得到。如节点分裂成两个时，右边叶子节点的直方图等于其父节点的直方图减去左边叶子节点的直方图。从而大大减少构建直方图的计算量。4.LightGBM直方图算法父节点10个样本，2个特征。①父节点特征的直方图②左子节点特征的直方图③右子节点特征的直方图3037353-3=01217-0=723-1=25-2=32-1=1

直方图算法还可以进一步加速：一个叶子节点的直方图可以由它的父亲节点的直方图与其兄弟的直方图做差得到。

4.LightGBM建树过程的两种方法：Level-wise和Leaf-wiseXGBoost通过Level-wisetreegrowth策略来生长树。同一层所有节点都做分裂，最后剪枝LightGBM

通过leaf-wise(best-first)策略来生长树。它将选取具有最大deltaloss的叶节点来生长。

Level-wisetreegrowthLeaf-wisetreegrowth…………基于最大深度的Leaf-wise的垂直生长算法参考文献

[1]李航.统计学习方法[M].北京:清华大学出版社,2019.[2]周志华.机器学习[M].北京:清华大学出版社,2016.[3]QuinlanJR.Bagging,Boosting,andC4.5[C]//ProceedingsoftheThirteenthNationalConferenceonArtificialIntelligenceandEighthInnovativeApplicationsofArtificialIntelligenceConference,AAAI96,IAAI96,Portland,Oregon,August4-8,1996,Volume1.1996.[4]BREIMANL.Randomforests[J].Machinelearning,2001,45(1):5–32.[5]RidgewayG.SpecialInvitedPaper.AdditiveLogisticRegression:AStatisticalViewofBoosting:Discussion[J].AnnalsofStatistics,2000,28(2):393-400.[6]FRIEDMANJH.Stochasticgradientboosting[J].ComputationalStatistics&DataAnalysis,2002,38.参考文献

[7]FRIEDMANJH.Greedyfunctionapproximation:Agradientboostingmachine[J].Annalsofstatistics,2001:1189–1232.[8]MACQUEENJ,OTHERS.Somemethodsforclassificationandanalysisofmultivariateobservations[C]//ProceedingsofthefifthBerkeleysymposiumonmathematicalstatisticsandprobability.Oakland,CA,USA,1(14):281–297.[9]CHENT,GUESTRINC.XGBoost:AScalableTreeBoostingSystem[C]//Proceedingsofthe22NdACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMining.ACM:785–794.[10]NIELSENDidrik.TreeBoostingWithXGBoost-WhyDoesXGBoostWin“Every”MachineLearningCompetition?[J],2016.[11]PolyakBT.Newton'smethodanditsuseinoptimization[J].EuropeanJournalofOperationalResearch,2007,181(3):1086-1096.[12]KEG,MENGQ,FINLEYT,etal.LightGBM:AHighlyEfficientGradientBoostingDecisionTree[J].2017:9.谢谢！机器学习-人工神经网络

本章目录01

发展历史02感知机算法03BP算法1.人工神经网络发展历史01

发展历史02感知机算法03BP算法1.人工神经网络发展历史发展历史1943年，心理学家McCulloch和逻辑学家Pitts建立神经网络的数学模型，MP模型神经元数学模型神经元生理结构输入层输出层隐藏层1.人工神经网络发展历史1960年代，人工网络得到了进一步地发展感知机和自适应线性元件等被提出。M.Minsky仔细分析了以感知机为代表的神经网络的局限性，指出了感知机不能解决非线性问题，这极大影响了神经网络的研究。单层感知机的数学模型......

1.人工神经网络发展历史1982年，加州理工学院J.J.Hopfield教授提出了Hopfield神经网络模型，引入了计算能量概念，给出了网络稳定性判断。离散Hopfield神经网络模型……1.人工神经网络发展历史1986年，Rumelhart和McClelland为首的科学家提出了BP（BackPropagation）神经网络的概念，是一种按照误差逆向传播算法训练的多层前馈神经网络，目前是应用最广泛的神经网络。BP神经网络模型输入层输出层隐层..................1.人工神经网络发展历史极限学习机(ExtremeLearningMachine,ELM)，是由黄广斌提出的用于处理单隐层神经网络的算法优点：1.学习精度有保证2.学习速度快

11

1个输出层神经元

2.感知器算法01

发展历史02感知机算法03BP算法2.感知机算法

需要学习的目标函数是

......输入权重偏置求和求和输出

2.感知机算法

2.感知机算法算法演示分类问题

单层感知机只能处理线性问题，无法处理非线性问题！！2.感知器算法01

发展历史02感知机算法03BP算法3.BP算法输入层输出层隐层..................

隐层神经元激活函数神经网络模型3.BP算法常见激活函数选择：Sigmoid函数Tanh函数ReLU函数LeakyReLU函数激活函数3.BP算法最常用Sigmoid函数的优缺点：优点：1.函数处处连续，便于求导2.可将函数值的范围压缩至[0,1]，可用于压缩数据，且幅度不变3.便于前向传输缺点：1.在趋向无穷的地方，函数值变化很小，容易出现梯度消失，不利于深层神经

的反馈传输2.幂函数的梯度计算复杂3.收敛速度比较慢3.BP算法主要步骤

第一步，对样本明确预测输出值与损失函数第二步，明确参数调整策略第三步，计算输出层阈值的梯度第四步，计算隐层到输出层连接权值的梯度第五步，计算隐层阈值的梯度第六步，计算输入层到隐层连接权值的梯度第七步，引出归纳结论3.BP算法第一步，明确损失函数

输入层输出层隐层..................

预测均方误差

3.BP算法算法步骤

第二步，明确参数调整策略输入层输出层隐层..................3.BP算法

利用链式法则，可得

其中，所以，更新公式

输入层输出层隐层..................

对阈值求导

3.BP算法

利用链式法则，可得

其中，可得综上可得

输入层输出层隐层............

......

对权重求导误差

3.BP算法

利用链式法则，可得

其中，所以有令更新公式输入层输出层隐层..................

对阈值求导

误差

3.BP算法

输入层输出层隐层..................

对权重求导

误差

3.BP算法第七步，引出结论

3.BP算法第七步，引出结论只要知道上一层神经元的阈值梯度，即可计算当前层神经元阈值梯度和连接权值梯度。随后可以计算输出层神经元阈值梯度，从而计算出全网络的神经元阈值和连接权值梯度。最终达到训练网络的目的。3.BP算法算法流程回顾：1.将输入样本提供给输入层神经元2.逐层将信号前传至隐层、输出层，产生输出层的结果3.计算输出层误差4.将误差反向传播至隐藏层神经元5.根据隐层神经元对连接权重和阈值进行调整6.上述过程循环进行，直至达到某些停止条件为止输入层输出层隐层..................信号前传误差后传3.BP算法优点：1.能够自适应、自主学习。BP可以根据预设参数更新规则，通过不断调整神经网络中的参数，已达到最符合期望的输出。2.拥有很强的非线性映射能力。3.误差的反向传播采用的是成熟的链式法则，推导过程严谨且科学。4.算法泛化能力很强。缺点：1.BP神经网络参数众多，每次迭代需要更新较多数量的阈值和权值，故收敛速度比较慢。2.网络中隐层含有的节点数目没有明确的准则，需要不断设置节点数字试凑，根据网络误差结果最终确定隐层节点个数3.BP算法是一种速度较快的梯度下降算法，容易陷入局部极小值的问题。参考文献

[1]李航.统计学习方法[M].北京:清华大学出版社,2019.[2]周志华.机器学习[M].北京:清华大学出版社,2016.[3]AndrewNg.MachineLearning[EB/OL].Sta