了解C++默认编写并调用了哪些函数

在class中，如果你自己没声明，编译器会为一个类自动声明(编译器版本的)一个默认构造函数，一个copy构造(拷贝构造)函数和一个copy assignment(拷贝赋值)操作符函数，这些函数都是public且inline的。但是只有当这些函数被调用了，它们才会被编译器创建出来。另外编译器还会提供一个默认的析构函数，这个析构函数是non-virtual的，除非这个class的base class自身声明有virtual 析构函数。

对于编译器提供的copy构造函数和copy assignment操作符函数，都只是单纯地将来源对象的每个non-static成员变量进行浅拷贝到目标对象。

某些情况下即使你自己未声明copy assignment操作符函数，编译器也会拒绝提供

• class内含reference成员
• class内含const成员
• Base class将copy assignment操作符声明未private，编译器将拒绝为其derived class生成一个copy assignment操作符

间隔与支持向量

给定训练样本集$D= {(xi, y_i)}{i=1}^m, y_i \in {-1, +1}$，分类学习最基本的思想就是基于训练集D再样本空间中找到一个划分超平面，将不同类别的样本分开，但能将样本分开来的超平面可能有很多。例如：

对于上图，直观上看，应该去找位于两类训练样本“正中间”的划分超平面，因为该划分超平面对训练样本局部扰动的“容忍”性最好。例如，由于训练集的局限性或噪声的因素，训练集外的样本可能比上图中的训练样本更接近两个类的分隔界，而红色的超平面受影响最小，因此其对未见示例的泛化能力最强。

在样本空间中，划分超平面可通过如下线性方程来描述：

其中$w = (w_1, w_2, \cdots, w_d)$为法向量，决定了超平面的方向，$b$为位移项，决定了超平面与原点之间的距离(其实二维平面上的直线$y = kx + b$本质上也是法向量的形式，其可以转换成$kx - y + b = 0$，即$(k, -1)(x, y)^T + b = 0$)。显然，划分超平面可被法向量$w$和位移$b$确定，下面我们将其记为$(w, b)$，样本空间中任意点$x$到超平面$(w, b)$的距离可写为:

假设超平面$(w, b)$能将训练样本正确分类，即对$(x_i, y_i) \in D$，若$y_i = +1$，则有$w^T x_i + b > 0$(在超平面上方)；若$y_i = -1$，则有$w^T x_i + b < 0$(在超平面下方)。令

可以证明，如果存在超平面$(w, b)$能将训练样本正确分类，则总存在缩放变换，使得上式成立，即总存在满足上式的超平面。下图是一个例子：

在上图中，距离超平面最近的几个训练样本点被称为“支持向量”，两个异类支持向量到超平面的距离之和称为“间隔”，在上图中，间隔为$\gamma = \frac{2}{||w||}$。

欲找到具有“最大间隔”的划分超平面，也就是要找到能满足(1)式约束的$w、b$，使得距离$\gamma$最大，即

显然为了最大化间隔，仅需要最大化$||w||^{-1}$，这等价于最小化$||w||^2$，于是，上式可重写为

这就是支持向量机的基本型

RBF(Radial Basis Function，径向基函数)网络

ART(Adaptive Resonance Theory，自适应谐振网络)

SOM(Self-Organizing Map，自组织映射)网络

级联相关网络

Elman网络

Boltzmann机

经验误差与过拟合

学习器的实际预测输出与样本的真实输出之间的差异称为“误差”，学习器在训练集上的错误称为训练误差(training error)或经验误差(empirical error)，在新样本上的误差称为泛化误差(generalization error)

我们实际希望的，是在新样本上能表现得很好的学习器。当学习器把训练集样本学得“太好”了的时候，很可能把训练集样本自身的一些特点当作了所有潜在样本都具有的一般性质，这样就会导致泛化性能下降，这种现象称为过拟合。

评估方法

使用一个“测试集(testing set)”来测试学习器对新样本的判别能力，然后测试集上的“测试误差”(testing error)作为泛化误差的近似，测试集应该尽可能与训练集互斥，即测试样本尽量不在训练集中出现、未在训练过程中使用过。

留出法

“留出法” (hold-out)直接将数据集 D 划分为两个互斥的集合，其中一个集合作为训练集S，另一个作为测试集T， 即$D = S \bigcup T$，$S \bigcap T = \emptyset$ .在S上训练出模型后，用 T 来评估其测试误差，作为对泛化误差的估计。
训练/测试集的划分要尽可能保持数据分布的一致性，如果从采样 (sampling)的角度来看待数据集的划分过程，则保留类别比例的采样方式通常称为”分层采样” (stratified sampling)。例如通过对D进行分层而获得含70%样本的训练集S和含30%样本的测试集T，若D包含500个正例，500个反例，则分层采样S应包含350个正例，350个反例，T则包含150个正例，150个反例。

单次使用留出法得到的估计结果往往不够稳定可靠，在使用留出法时，一般要采用若干次随机划分、重复进行实验评估后取平均值作 为留出法的评估结果。
常见做法是将大约 $\frac{2}{3}$ ～ $\frac{4}{5}$ 的 样本用于训练，剩余样本用于测试。

交叉验证法

“交叉验证法” (crossvalidation)先将数据集D划分为k个大小相似的互斥子集，即${D = D1 \bigcup D2 \bigcup \dots \bigcup Dk},{Di\bigcap Dj = \emptyset}$ ($i\neq j$). 每个子集Di都尽可能保持数据分布的一致性，即从 D 中通过分层采样得到. 然后，每次用 k-1 个子集的并集作为训练集?余下的那个子集作为测试集;这样就可获得 k 组训练/测试集，从而可进行 k 次训练和测试，最终返回的是这 k 个测试结果的均值。交叉验证法评估结果的稳定性和保真性在很大程度上取决于 k 的取值。

与留出法相似，将数据集 D 划分为 k 个子集同样存在多种划分方式。为减小因样本划分不同而引入的差别，k折交叉验证通常要随机使用不同的划分重复p次，最终的评估结果是这 p次 k折交叉验证结果的均值。
院假定数据集 D 中包含 m 个样本，若令 k=m，则得到了交叉验证法的一个特例:留一法(Leave-One-Out比，简称 LOO)。

自助法

它直接以自助采样法 (bootstrap sampling)为基础。 给定包含 m 个样本的数据集 D ，我们对它进行采样产生数据集 D’: 每次随机从 D 中挑选一个样本，将其拷贝放入 D’ 然后再将该样本放回初始数据集 D 中，使得该样本在下次采样时仍有可能被采到;这个过程重复执行 m 次后，我们就得到了包含 m 个样本的数据集 D’，这就是自助采样的结果。

调参与最终模型

大多数学习算法都有些参数 (parameter)需要设定，参数配置不同，学得模 型的性能往往有显著差别.
对每种参数配置都 训练出模型，然后把对应最好模型的参数作为结果。
学习算法的很多参数是在实数范围内取值，因此，对每种参数配置都训练出模型来是不可行的。现实中常用的做法，是对每个参数选定一个范围和变化步长，例如在 [0，0.2] 范围内以 0.05 为步长，则实际要评估的候选参数值有 5 个，最终是从这 5 个候选值中产生选定值。

给定包含 m 个样本的数据集 D ，在模型评估与选择过程中由于需要留出 一部分数据进行评估测试，事实上我们只使用了一部分数据训练、模型。因此，在模型选择完成后，学习算法和参数配置己选定，此时应该用数据集 D 重新训练模型.这个模型在训练过程中使用了所有 m 个样本，这才是我们最终提交给用户的模型.

性能度量

错误率与精度

查准率、查全率与Fl

ROC 与 AUC

代价敏感错误率与代价曲线

神经元模型

神经网络中最基本的成分是神经元模型。

在这个模型中，神经元接收来自n个其他神经元传递过来的输入信号，这些输入信号通过权重的连接进行传递，神经元接收到的总输入值将与神经元的阈值进行比较，然后通过“激活函数”处理以产生神经元的输出。

理想中的激活函数是阶跃函数，它将输入值映射为输出值为0，1，其中0对应神经元抑制，1对应神经元兴奋。然而，阶跃函数具有不连续、不光滑等不好的性质，因此实际常用Sigmoid函数作为激活函数，典型的Sigmoid函数就是对数几率函数。

把许多个这样的神经元按一定的层次结构连接起来，就得到了神经网络。

感知机与多层网络

感知机由两层神经元组成，输入层接收外界输入信号后传递给输出层(输入层只负责接收信号，不负责处理)，输出层是M-P神经元，亦称“阈值逻辑单元”。感知机能实现逻辑与、或、非运算。例如对于只有两个输入、一个输出的感知机，令$w_1 = w_2 = 1$，$\theta = 1$，则$y = 1·x_1 + 1·x_2 - 1$则当$x_1 = x_2 = 1$时，$y=1$。

给定训练集数据，权重$wi(i=1,2,\cdots,n)$以及阈值$\theta$可通过学习算法得到，阈值$\theta$可看作一个固定输入为$-1$的结点，所对应的连接权重为$w{n+1}$(即$x{n+1} = -1, w{n+1} = \theta$)，这样权重和阈值的学习就可以统一为权重的学习。感知机学习规则非常简单，对训练样例$(x,y)$，若当前感知机的输出为$\hat{y}$，则感知机权重将这样调整:

其中$\eta \in (0,1)$为学习率。

解释：假设$w_i > 0$，$x_i > 0$，预测结果$\hat{y} > y$时，说明需要使得$x_i$分类占的比例变小，此时$\Delta w_i < 0$，$w_i$减小。其他情况同理。

感知机只有输出层神经元进行激活函数处理，即只拥有一层功能神经元，其学习能力非常有限。可以证明，若学习样例是线性可分的，即存在一个超平面能将它们分开，则感知机的学习过程一定会收敛而求得适当的权重向量；否则感知机学习过程将会发生振荡，权重向量难以稳定下来，不能求得合适解，例如感知机甚至不能解决异或这样简单的非线性可分问题

要解决非线性可分问题，需考虑使用多层功能神经元。输出层与输入层之间的一层神经元，被称为隐层或隐含层，隐含层和输出层神经元都是拥有激活函数的功能神经元。

更一般的，常见的神经网络是如下图的层级结构，每层神经元与下一层神经元全互连，神经元之间不存在同层连接，也不存在跨层连接。这样的神经网络结构通常称为多层前馈神经网络

注意，前馈并不意味着网络中信号不能向后传，而指网络拓扑结构上不存在环或回路。输入层神经元仅是接收输入，不进行函数处理，隐含层与输出层包含功能神经元。

神经网络的学习过程，就是根据训练集数据来调整神经元之间的连接权以及每个功能神经元的阈值。

误差逆传播(BP)算法

欲训练多层网络，简单的感知机学习规则显然不够了，需要更强大的学习算法。误差逆传播(Error BackPropagation, 简称BP)算法就是其中的最杰出的代表。BP算法不仅可用于多层前馈神经网络，还可用于其他类型的神经网络，例如训练递归神经网络，但通常说BP网络时，一般是指用BP算法训练的多层前馈神经网络

标准BP算法推导

对于给定的训练集$D = {(xi, y_i)}{i=1}^{m}$，其中$x_i \in R^d, y_i \in R^l$，即输入示例由$d$个属性描述，输出$l$维实值向量。首先定义一下变量：

下图是相关变量在神经网络中的表示：

假设隐层和输出层神经元都使用对数几率函数(以下公式的推导都是在这个前提下进行的，当实际运用中不是使用这个函数时需要自己另行推导公式)，即$f(x) = \frac{1}{1 + e^{-x}}$，对训练例$(x_k, y_k)$，假定神经网络的输出为$\hat{y}_k = (\hat{y}_1^k,\hat{y}_2^k, \cdots,\hat{y}_l^k)$，即

则网络在$(x_k, y_k)$上的均方误差为

对于上面的公式，总过用$dq + lq + q + l$个参数需要确定。BP是一个迭代算法，在迭代的每一轮中采用广义的感知机学习规则对参数进行更新估计，对于任意参数$v$的更新估计式为

BP算法基于梯度下降策略，以隐层到输出层的连接权$w_{hj}$为例子，以目标的负梯度方向对参数进行调整。对均方误差$E_k$，给定学习率$\eta$，有

由于$\betaj = \sum{h=1}^{q} w_{hj}b_h$，则有

对于对数几率函数，有一个很好的性质：

则：

令$gj = - \frac{\partial E_k}{\partial \hat{y}_j^k} \frac{\partial \hat{y}_j^k}{\partial \beta_j} = \hat{y}_j^k(1-\hat{y}_j^k)(y_j^k - \hat{y}_j^k)$，则可得到关于$w{hj}$的更新公式

同理可得到

有时为了做精细调节，计算$\Delta w{hj}、\Delta \theta_j$使用的$\eta$可以和计算$\Delta v{ih}、\Delta \gamma_h$使用的$\eta$可以不同。

标准BP算法流程

对每个训练样例，BP算法执行以下操作：先将输入示例提供给输入层神经元，然后逐层将信号前传，直到产生输出层的结果；然后计算输出层的误差，再将误差逆向传播至隐层神经元，最后根据隐层神经云的误差来对连接权和阈值进行调整。该迭代过程一直进行，直到达到某个停止条件为止，例如训练误差已达到一个很小的值。

累计BP算法

BP算法的目标是要最小化训练集D上的累积误差，即：

但标准BP算法每次仅对一个训练样例更新连接权和阈值，更新的规则也是基于单个 $E_k$ 推导的，如果类似地推导出基于累积误差最小化的更新规则，就得到了累积误差逆传播算法。累积BP算法与标准BP算法都很常用。

一般来说，标准BP算法每次更新都值针对单个样例，参数更新得非常频繁，而且对不同样例进行更新得效果可能出现抵消现象，因此，为了达到同样的累积误差极小点，标准BP算法往往需进行更多次数的迭代。

累积BP算法直接针对累积误差最小化，它在读取整个训练集D一遍后才对参数进行更新。其参数更新的频率低得多，但在很多任务中，累积误差下降到一定程度之后，进一步下降会非常缓慢，这时标准BP往往会更快获得较好的解，尤其是在训练集D非常大时会更明显。

防止过拟合

已证明，只需一个包含足够多神经元的隐层，多层前馈神经网络就能以任意精度逼近任意复杂度的连续函数。然而如何设置隐层神经元的个数仍是个未决问题，实际应用中通常靠“试错法”调整。

正是由于神经网络强大的表示能力，BP神经网络经常遭遇过拟合。有两种策略常用来缓解BP网络的过拟合。

第一种策略是早停：将数据分为训练集和验证集，训练集用于计算梯度、更新连接权和阈值，验证集用来估计误差，若训练集误差降低但验证集误差升高，则停止训练。

第二种策略是“正则化”，其基本思想是在误差目标函数中增加一个用于描述网络复杂度的部分，例如连接权和阈值的平方和(增加连接权和阈值平方和这一项后，训练过程将会偏好比较小的连接权和阈值，使网络输出更加“光滑”，从而对过拟合有所缓解)，令$E_k$表示第k个训练集上的误差，$w_i$表示连接权和阈值，则误差目标函数改变为

其中$\lambda$用于对经验误差与网络复杂度这两项进行折中，通常通过交叉验证法(见模型评估方法那一节)来估计。

全局最小与局部最小

由于上面的神经网络算法是基于梯度下降方法的，所以在寻找最优参数的时候很有可能最后得到的结果是局部最小值而不是全局最小值，我们在参数寻优的过程中是希望找到全局最小。

为了避免陷入局部最小，在现实任务中，人们常采用以下策略来试图“跳出”局部最小，从而进一步接近全局最小。

• 以多种不同参数初始化多个神经网络，按标准方法训练后，取其中误差最小的解作为最终方案。这相当于从多个不同的初始开始搜索，这样就可能陷入不同的局部最小，从中进行选择有可能更接近全局最小的结果。
• 使用“模拟退火”技术，模拟退火在每一步都以一定的概率接受比当前接更差的结果，从而有助于“跳出”局部最小，在每步迭代过程中，接受“次优解”的概率要随着时间的推移而逐渐降低，从而保证算法的稳定性。
• 使用随机梯度下降。使用随机梯度下降，由于每次迭代都是随机选择的部分数据，所以当陷入了局部最小，它计算出来的梯度仍可能不为零，这样就有机会跳出局部最小继续搜索。

此外，遗传算法也常用来训练神经网络以更好逼近全局最小。需注意的是，上述用于跳出局部最小的技术大多是启发式，理论上尚缺乏保障

深度学习

理论上来说，参数越多的模型复杂度越高，这意味着它能完成更复杂的学习任务，但一般情形下，复杂模型的训练效率低，易陷入过拟合。而随着云计算、大数据时代的到来，计算能力的大幅提高可缓解训练低效性，训练数据的大幅增加则可降低过拟合风险。因此，以深度学习为代表的复杂模型开始受到人们的关注。（大型深度学习模型中甚至有上百亿个参数）

典型的深度学习就是很深层的神经网络。典型的深度学习模型就是很深层的神经网络。单隐层的多层前馈网络已具有很强大的学习能力；模型复杂度的增加可通过单纯增加隐层神经元的数目来实现，但从增加模型复杂度的角度来看，增加隐层的数目比增加隐层神经元的数目更有效。然而，多隐层神经网络难以直接用经典算法(例如标准BP算法)进行训练，因为误差在多隐层内逆传播时，往往会“发散”而不能收敛到稳定状态。

深度学习训练方法

无监督逐层训练是多隐层网络训练的有效手段，其基本思想是每次训练一层隐结点，训练时将上一层隐节点的输出作为输入，而本层隐节点的输出作为下一层隐结点的输入，这成为“预训练”；在预训练全部完成后，再对整个网络进行“微调”训练。

“预训练+微调”的做法可视为将大量参数分组，对每组先找到局部看来比较好的设置，然后再基于这些局部较优的结果联合起来进行全局寻优。这样就在利用了模型大量参数所提供的自由度的同时，有效地节省了训练开销。

另一种节省训练开销的策略是“权共享”，即让一组神经元使用相同的连接权，这个策略在卷积神经网络中发挥了重要作用。

深度学习总结

对于深度学习，可看作是对输入信号进行逐层加工，从而把初始的、与输出目标之间联系不大密切的输入表示、转化成与输出目标联系更密切的表示，使得原来仅基于最后一层输出映射难以完成的任务成为可能。换言之，通过多层处理，逐渐将初始“低层”特征表示转化为“高层”特征表示后，用“简单模型”即可完成复杂的分类等学习任务，由此可将深度学习理解为进行“特征学习”或“表示学习”。

以往在机器学习用于现实任务时，描述样本的特征通常需要由人类专家来设计，这成为”特征工程“。特征的好坏对泛化性能有至关重要的影响，人类专家设计出好特征也并非易事；特征学习则通过机器学习技术自身来产生好特征，这使机器学习向“全自动数据分析”又前进了一步。

解决过拟合的一些方法

为了减少过拟合，一般有两种方法：

1、减少一些特征。其手段也分为手动选择要丢掉的特征和使用一些算法来丢掉部分特征。但是减少特征就意味着丢失信息，所以要谨慎丢弃特征。

2、在模型中加入正则化项。使用正则化项时不用删除特征。

正则化项的作用

正则化项的使用其思想是让某些特征的参数尽可能小(这也叫做对某些参数的惩罚)，从而让这个特征所占的重要性变低。

例如某个模型为$f(x) = w1 x + w_2 x^2 + w_3 x^3 + w_4 x^4$ + b，其对应的目标函数是$argmin{(w, b)} \sum{i=1}^{m} [f(x_i) - y_i]^2$，那么可以对目标函数加入正则化项得：$argmin{(w,b)}\sum_{i=1}^{m}[f(x_i) - y_i]^2 + 1000w_3^3 + 1000w_4^4$，来使训练后的模型中$w_3$和$w_4$尽可能小，从而使得特征$x^3$和$x^4$在模型中的作用减小。

但在实际操作中，通常不知道需要让哪些参数尽可能小，所以我们让所有的参数都尽可能小。

通常我们使用两种正则化项：L1正则化和L2正则化

L1正则化

以线性模型为例，加入L1正则化的损失函数形式为: $\sum{i=1}^{m} [wx_i+b-y_i]^2 + \lambda\sum{i=1}^{d}|w_i|$。

L2正则化

同样以线性模型为例，加入L2正则化的损失函数形式为：$\sum{i=1}^{m}[wx_i + b - y_i]^2 + \lambda \sum{i=1}^{d}w_i^2$。

如果是使用标准方程法求解的话，其解的形式为：

而且在加入正则化项后，标准方程法中的括号部分的矩阵一定可逆。

使用正则化项的一些注意

1、$\lambda$不能设置得过大。$\lambda$越大，$w$的自由度就越小，$\lambda$越小，$w$的自由度就越高

2、一般不惩罚常数参数$b$

构建决策树

决策树是一种常见的分类机器学习方法，顾名思义，决策树就是基于树形结构来进行决策，这恰是人类在面临决策问题时一种很自然的处理机制。

在构建一棵决策树时，其决策的过程就是对某个属性的“测试”，每个测试的结果或是导出最终的分类结果，或是导出下一步的判定问题，每一次需要决策的样本是上次的决策结果之后划分出来的样本。

一般，一棵决策树包含一个根结点、若干个内部结点和若干个叶结点。叶结点对应于决策结果，其他每个结点则对应一个属性测试，每个结点包含的样本集合根据属性测试的结果被划分到子结点中，根结点包含样本全集。

决策树学习的目的是为了产生一棵泛化能力强，即处理未见示例能力强的决策树。

构建一棵决策树的伪代码为：

输入：训练集$D={(xi, y_i)}{i=1}^{m}$

​ 属性集$A = {ai}{i=1}^{d}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

void GenerateDTree(D, A) {
  	生成根结点 root;
	if (D中样本全属于同一类别C) {//当前结点包含的样本全属于同一类别，即yi都相同
 		将root标记为C类叶结点;
   		return;
  	}
	if (A == NULL || D中样本在属性A上取值相同) {//没有属性可以选择或者当前所有样本在剩下的属性上取值相同
    		将root标记为叶结点，其类别标记为D中样本最多的类;
    		return;
	}
  	从属性集A中选择最优划分属性a*;
  	for (对于属性a*每一个可能的属性取值v) {
      		为root生成一个分支；令D_v表示D中在属性a*上取值为v的样本子集;
        	if (D_v 为空集) {
           		将分支结点标记为叶结点，其类别标记为D中(注意是D)中样本最多的类;
           		return;
        	} else {
           		GenerateDTree(D_v, A - a*);
        	}
    	}
}

决策树生成的算法是一个递归算法，注意该递归算法的三个返回条件

划分选择

在上面的生成决策树的伪代码中，我们要选择最优的划分属性，那么应该怎么选择最后的划分属性呢？一般而言，随着划分过程不断进行，我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的“纯度”越来越高。所以可以选择使得划分后结点纯度更高的属性作为划分属性，一般有以下几种度量某种属性这种能力的指标：信息增益、增益率、基尼指数。

信息增益

在查看定义信息增益之前，需要先查看信息熵的定义。信息熵是度量样本集合纯度最常用的一种指标。假定当前样本集合$D$中第$k$类样本所占的比例为$p_k \space (k = 1,2, \cdots, |Y|, |Y|表示当前样本中类别的总数)$，则信息熵的定义为：

$Ent(D)$越小，则数据集合$D$的纯度越高

有了信息熵的定义之后，再来看信息增益的定义。假设某个离散属性$a$有$V$个可能的取值${a_1, a_2, \cdots, a_V}$，若使用属性a来对样本集D来划分，则会产生$V$个分支结点。其中第$i$个分支结点包含了D中所有在属性$a$上取值为$a_i$的样本，记为$D_i$。这样可以计算出$D_i$的信息熵，在考虑在不同的分支结点包含的样本数不同，给分支结点赋予权重$|\frac{D_i}{D}|$，即样本数多的分支结点的影响越大。最后可以得到使用属性$a$对样本集D进行划分所获得的“信息增益”:

一般而言，信息增益越大，则意味着使用属性a来进行划分所获得的“纯度提示”越大。若在一次划分中，有多个属性均取得了最大的信息增益，则任选其中之一作为划分属性。

增益率

信息增益准则的特点是对可取值数目较多的属性性有所偏好，例如某种属性有1000个取值，那么这个属性的信息增益率一般就会很大，但是选择这个属性作为划分属性后，每个划分出来的结点可能会因为已经没有多少剩余的样本而很快地被标记为叶结点。那么使用这个有1000个取值的属性划分得到的决策树泛化能力一般不会太好。而增益率则将每个属性的可能取值个数考虑了进去，其定义为：

$IV(a)$称为属性a的“固有值”，属性a的可能取值数目越多(即$V$越大)，则$IV(a)$的取值通常会越大。

需要注意的是，增益率准则对可取值数目较少的属性有所偏好，因此，有些算法并不是直接选择增益率最大的候选划分属性，而是先从候选划分属性中找出信息增益率高于平均水平的属性，再从中选择增益率最高的。

基尼指数

查看基尼指数的定义前，先看一下基尼值的定义。基尼值也是用来描述数据集D的纯度的指标。其具体定义为：

直观来说，$Gini(D)$反映了从数据集D中随机抽取两个样本，其类别标记不一致的概率，因此，$Gini(D)$越小，则数据集$D$的纯度越高。

有了基尼值的定义，再来看属性a的基尼指数的定义：

我们在候选属性集合$A$中，选择那个使得划分后基尼指数最小(注意是最小，信息增益和增益率中是选最大的那个)的属性作为划分属性。

剪枝处理

剪枝处理是决策树学习算法处理过拟合的主要手段。在决策树学习中，为了尽可能正确分类训练样本，结点划分过程不断重复，有时会造成决策树分支过多，这时就可能因训练样本学习得“太好”了，以至于把训练集自身的一些特点也当做所有数据都具有的一般性质而导致过拟合。因此，可通过主动去掉一些分支来降低过拟合的风险。

决策树剪枝的基本策略有预剪枝和后剪枝。

预剪枝

预剪枝是指在决策树生成过程中，对每个结点在划分前先进进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点。那么如何判断泛化性能是否提升呢？可以使用验证集来判断，看剪枝后的决策树在验证集上的表现是否比未剪枝的决策树好。

预剪枝使得决策树的很多分支结点都没有展开，这不仅降低了过拟合的风险，还显著减少了决策树的训练时间开销和测试时间开销。但另一方面，有些分支的当前划分虽不能提升，甚至可能导致泛化性能暂时下降，但在其基础上进行的后续划分却有可能导致性能显著提高，这给预剪枝决策树带来了欠拟合的风险。

后剪枝

后剪枝则是先从训练集中生成一棵完整的决策树，然后自底向上地对每个非叶结点进行判断，若将该非叶结点对应的子树替换为叶结点能带来决策树泛化能力的提升(同样也可使用验证集来判定泛化性能是否提升)，则该非叶结点标记叶结点。

后剪枝决策树通常比预剪枝决策树保留了更多的分支，一般情况下后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树。但后剪枝过程是在生成完全决策树之后进行的，并且要自底向上地对树中的所有非叶结点进行逐一考察，因此其训练时间开销比未剪枝决策树和预剪枝决策树都要大得多。

连续值处理

在决策树中，对于某些取值为连续值的属性，不能直接根据连续属性的可取值来对结点进行划分，此时要将连续值转换为离散值，最简单的策略是采用二分法对连续属性进行处理。

给定样本集$D$和连续属性$a$，假设$a$在$D$上出现了n各不同的取值，将这些值从小到大进行排列，记为${a_1, a_2, \cdots, a_n}$。选定划分点$t$为某两个相邻取值的中点，则数据集可以被划分为两个子集。因此，对于n个不同

取值，共有$n-1$个候选划分点，这些划分点构成集合：

然后，可以像离散属性值一样来考察这些划分点，选取最优的划分点进行样本集的划分。例如可用改造后的信息增益来判断划分点的优劣：

$Gain(D, a, t)$是样本集在连续属性$a$上基于划分点$t$二分后的信息增益。于是，我们就可选择使$G(D, a, t)$

最大化的划分点。

需要注意的是，与离散值属性不同，若当前结点划分属性为连续属性，该属性还可作为其后代结点的划分属性。例如当前结点选择的划分属性为连续属性$a$，并且划分标准为$a \leq 0.5$和$a> 0.5$，则对于使用$a \leq 0.5$划分出来的结点，仍然可以使用属性a最后划分属性，这时可能选择划分标准为$a \leq 0.25$和$0.25 < a \leq 0.5$。

缺失值处理

现实任务中常会遇到不完整的样本，尤其是在属性数目较多的情况下，往往会有大量样本出现缺失值，如果简单地放弃不完整样本，仅使用无缺失值的样本来进行学习，显然是对数据信息的极大浪费。所以要想办法处理缺失值的情况。

如何在属性缺失的情况下进行划分属性选择

给定数据集$D$和属性$a$，令$\overline{D}$表示D中在属性a上没有缺失值的样本子集，显然我们可根据$\overline{D}$来判断属性a的优劣。假设属性a由$V$个可取值${a_1, a_2, \cdots, a_V}$，令$\overline{D_i}$表示$\overline{D}$中在属性a上取值为$a_i$的样本子集。$\overline{D_k}$表示$\overline{D}$中属于第$k$类$(k = {1, 2, \cdots, |Y|}, \space|Y|为\overline{D}中类别总数)$的样本子集。则有：

假定为$D$中的每个样本$x$赋予一个权值$w_x$，并定义：

直观上来看，对属性$a$，$\rho$表示无缺失值样本所占的比例，$\overline{pk}$表示无缺失值样本中第$k$类样本所占的比例，$\overline{r_i}$则表示无缺失值样本中在属性a上取值为$a_i$的样本占的比例。显然有：$\sum{k=1}^{|Y|} \overline{pk} = 1$，$\sum{i=1}^{V} \overline{r_i} = 1$。

基于上述定义，可以将信息增益的计算推广为：

同理也可得到增益率和基尼指数的推广。

给定划分属性，若样本在该属性上的值缺失，如果对样本进行划分

若确定了划分属性为$a$，若样本$x$在划分属性$a$上的取值未知，则将$x$同时划入所有子结点，且样本权值在与属性值$a_i$对应的子结点调整为$\overline{r_i} · w_x$。直观上来看，这就是让同一个样本以不同的概率划入到不同的子结点中去。

多变量决策树

若把每个属性视为坐标空间中的一个坐标轴，则$d$个属性描述的样本就对应了$d$维空间中的一个数据点，对样本分类则意味着在这个坐标空间中寻找不同类样本之间的分类边界。决策树所形成的分类边界有一个明显的特点: 轴平行​，即它的分界边界由若干个和坐标轴平行的分段组成。

显然，分类边界与坐标轴平行时，这样的分类边界使得学习结果具有较好的可解释性。但在学习任务的真实边界比较复杂时，必须使用很多段划分才能获得较好的近似，此时的决策树会相当复杂，由于要进行大量的属性测试，预测时间开销会很大。

若能使用斜的划分边界，则决策树的模型将能得到很大的简化，多变量决策时就是能实现斜划分甚至更复杂划分的决策树。在此类决策树中，非叶结点不再仅对莫个属性，而是对属性的线性组合进行测试；换言之，每个非叶结点是一个形如$\sum_{i=1}^d w_i a_i = t$的线性分类器，其中$w_i$是属性$a_i$的权重。在多变量决策树的学习过程中，不是为每个非叶结点寻找一个最有划分属性，而是试图建立一个合适的线性分类器。

其他

在决策时中，常使用信息增益、增益率、基尼指数作为划分属性选择的标准，除这些意外，人们还设计了许多其他的准则用于决策树划分选择。这些准则虽然对决策树的尺寸有较大影响，但对泛化性能的影响很有限。而使用剪枝的方法和程度对决策树泛化性能的影响相当显著，有实验研究表明，在数据带有噪声时通过剪枝甚至可将决策树的泛化性能提高25%。

有算法试图在决策树中的叶结点嵌入神经网络，例如感知机树在决策树的每个叶结点上训练一个感知机，有的直接在叶结点嵌入多层神经网络。

有一些决策树算法可进行增量学习，即在接收到新样本后对已学得的模型进行调整，而不完全重新学习。主要机制是通过调整分支路径上的划分次序来对树进行部分重构。增量学习可有效降低每次接受到新样本后的训练时间开销，但多步增量学习后的模型与基于全部数据训练而得的模型有较大差别。

切比雪夫大数定律

假设${X_n}$是相互独立的随机变量，如果方差$DX_i$存在，且有一致有上界，则

伯努利大数定律

假设$u_n$是n重伯努利实验中事件A发生的次数，在每次实验中事件A发生的概率为$p$，则

辛钦大数定律

假设${X_n}$是独立同分布的的随机变量序列，如果$EX_i=u$存在，则

中心极限定理

假设${X_n}$是独立同分布的随机变量序列，如果$EX_i=u$，$DX_i = \sigma^2$存在，则${X_n}$服从中心极限定理，有

什么是类别不同平衡问题

类别不平衡就是指分类任务中不同类别的训练样例数目差别很大的情况。例如在二分类任务中有998个正例，2个反例，那么学习方法只需要返回一个永远将新样本预测为反例的学习器，就能达到99.8%的精度，然而这个学习器往往没有价值，因为它不能预测出任何正例。还有，在通过拆分法解决多分类问题时，即使原始问题中不同类别的训练样例数目相当，在使用OvR、MvM策略后产生的二分类任务仍可能出现类别不平衡现象。

处理类别不平衡问题

以logistic回归处理二分类任务为例，分类任务的输出一般都是判断某个样例为正例的概率。假如输出$y$表示样例为正例的概率，则$1-y$就表示样例为反例的概率。

在训练集中，正、反例的数目不同时，令$m^+$表示正例数目，$m^-$表示反例数目。于是，只要分类器的预测概率比例高于$\frac{m^+}{m^-}$就应该判为正例。即：

还有一种形式为将$\frac{m^+}{m^-}$替换为$\frac{cost^+}{cost^-}$，其中$cost^+$表示将正例误分为反例的代价，$cost^-$是将反例误分为正例的代价，这其实就是代价敏感学习的思想。

但是使用这种方法一般要求“训练集时真是样本总体的无偏采样”，而这个要求一般很难实现。除了上面的这个方法还有其他两种方法：“欠采样”和“过采样”。

欠采样即去除一些多的样例，使得正、反样例数目接近，然后再进行学习。欠采样若丢弃样例后，可能丢失一些重要的信息。欠采样的代表算法EasyEnsemble则是利用集成学习机制，将样例多的类别中的样例划分为若干个集合供不同的学习器使用，这样对每个学习器来看都进行了欠采样，但在全局来看却不会丢失重要信息。

过采样即赠加一些样例数较少的类别的样例，使得正、反例数目接近，然后再学习。但是过采样不能简单对初始的样本进行重复采样，否则将会导致严重的过拟合。过采样的代表算法SMOTE是通过对训练集中的样例进行插值来表示额外的样例。