笔者希望该笔记能够记录每个机器学习算法的过拟合问题。
发生过拟合的主要原因可以有以下三点：
（1）数据有噪声
（2）训练数据不足，有限的训练数据
（3）训练模型过度导致模型非常复杂
(参考文献：大白话解释模型产生过拟合的原因)
——————————————————————————
相关内容：
1、 R语言︱ROC曲线——分类器的性能表现评价
2、机器学习中的过拟合问题
3、R语言︱机器学习模型评估方案（以随机森林算法为例）
——————————————————————————
过拟合问题举例
右图在训练数据上拟合完美，但是预测第11个时候，
左图虽然拟合不完全，但是更合理；右图的-953，误差极大。
一、随机森林不会发生过拟合的原因
在建立每一棵决策树的过程中，有两点需要注意 -采样与完全分裂。首先是两个随机采样的过程，random forest对输入的数据要进行行、列的采样。对于行采样，采用有放回的方式，也就是在采样得到的样本集合中，可能有重复的样本。
假设输入样本为N个，那么采样的样本也为N个。这样使得在训练的时候，每一棵树的输入样本都不是全部的样本，使得相对不容易出现over-fitting。
然后进行列采样，从M个feature中，选择m个(m << M)。之后就是对采样之后的数据使用完全分裂的方式建立出决策树，这样决策树的某一个叶子节点要么是无法继续分裂的，要么里面的所有样本的都是指向的同一个分类。一般很多的决策树算法都一个重要的步骤 - 剪枝，但是这里不这样干，由于之前的两个随机采样的过程保证了随机性，所以就算不剪枝，也不会出现over-fitting。 按这种算法得到的随机森林中的每一棵都是很弱的，但是大家组合起来就很厉害了。
可以这样比喻随机森林算法：每一棵决策树就是一个精通于某一个窄领域的专家（因为我们从M个feature中选择m让每一棵决策树进行学习），这样在随机森林中就有了很多个精通不同领域的专家，对一个新的问题（新的输入数据），可以用不同的角度去看待它，最终由各个专家，投票得到结果。
二、（1）数据有噪声
为什么数据有噪声，就可能导致模型出现过拟合现象呢？
所有的机器学习过程都是一个search假设空间的过程！我们是在模型参数空间搜索一组参数，使得我们的损失函数最小，也就是不断的接近我们的真实假设模型，而真实模型只有知道了所有的数据分布，才能得到。
往往我们的模型是在训练数据有限的情况下，找出使损失函数最小的最优模型，然后将该模型泛化于所有数据的其它部分。这是机器学习的本质！
那好，假设我们的总体数据如下图所示：
（我这里就假设总体数据分布满足一个线性模型y = kx b,现实中肯定不会这么简单，数据量也不会这么少，至少也是多少亿级别，但是不影响解释。反正总体数据满足模型y）
此时我们得到的部分数据，其中还有噪声的话，如图所示：
那么由上面训练数据点训练出来的模型肯定不是线性模型（总体数据分布下满足的标准模型），比如训练出来的模型如下：
那么我拿着这个有噪声训练的模型，在训练集合上通过不断训练，可以做到损失函数值为0，但是拿着这个模型，到真实总体数据分布中（满足线性模型）去泛化，效果会非常差，因为你拿着一个非线性模型去预测线性模型的真实分布，显而易得效果是非常差的，也就产生了过拟合现象！
三、训练数据不足，有限的训练数据
当我们训练数据不足的时候，即使得到的训练数据没有噪声，训练出来的模型也可能产生过拟合现象，解释如下：
假设我们的总体数据分布如下：
那么我拿着这个有噪声训练的模型，在训练集合上通过不断训练，可以做到损失函数值为0，但是拿着这个模型，到真实总体数据分布中（满足线性模型）去泛化，效果会非常差，因为你拿着一个非线性模型去预测线性模型的真实分布，显而易得效果是非常差的，也就产生了过拟合现象！ 那么由这个训练数据，我得到的模型是一个线性模型，通过训练较多的次数，我可以得到在训练数据使得损失函数为0的线性模型，拿这个模型我去泛化真实的总体分布数据（实际上是满足二次函数模型），很显然，泛化能力是非常差的，也就出现了过拟合现象！
四、维度灾难的实例讲解
来源于：一文详解分类问题中的维度灾难及解决办法
如果只使用一个特征，例如使用图片的平均红色程度red。
图2展示了只使用一个特征并不能得到一个最佳的分类结果。因此，我们觉得增加第二个特征：图片的平均绿色程度green。
图3. 增加第二个特征仍然不能线性分割，即不存在一条直线能够将猫和狗完全分开
最后，我们决定再增加第三个特征：图片的平均蓝色程度，得到了三维特征空间：
图4. 增加第三个特征实现了线性可分，即存在一个平面完全将猫和狗分开来
在三维特征空间，我们可以找到一个平面将猫和狗完全分开。这意味着三个特征的线性组合可以对10个训练样本进行最佳的分类。
图5. 特征越多，越有可能实现正确分类
以上的例子似乎证明了不断增加特征数量，直到获得最佳分类效果，是构建一个分类器的最好方法。但是，之前图1中，我们认为情况并非如此。我们需要注意一个问题：随着特征维度的增加，训练样本的在特征空间的密度是如何呈指数型下降的？
在1D空间中（图2所示），10个训练样本完全覆盖了1D特征空间，特征空间宽度为5。因此，1D下的样本密度是10/2=5。而在2D空间中（图3所示），同样是10个训练样本，它构成的2D特征空间面积为5x5=25.因此，2D下的样本密度是10/25=0.4。最后在3D空间中，10个训练样本构成的特征空间大小为5x5x5=125，因此，3D下的样本密度为10/125=0.08。
如果我们继续增加特征，整个特征空间维度增加，并变得越来越稀疏。由于稀疏性，我们更加容易找到一个超平面来实现分类。这是因为随着特征数量变得无限大，训练样本在最佳超平面的错误侧的可能性将会变得无限小。然而，如果我们将高维的分类结果投影到低维空间中，将会出现一个严重的问题：
图6. 使用太多特征导致过拟合。分类器学习了过多样本数据的异常特征（噪声），而对新数据的泛化能力不好。
图6展示了3D的分类结果投影到2D特征空间的样子。样本数据在3D是线性可分的，但是在2D却并非如此。事实上，增加第三个维度来获得最佳的线性分类效果，等同于在低维特征空间中使用非线性分类器。其结果是，分类器学习了训练数据的噪声和异常，而对样本外的数据拟合效果并不理想，甚至很差。
这个概念称为过拟合，是维度灾难的一个直接后果。图7展示了一个只用2个特征进行分类的线性分类器的二维平面图。
图7. 尽管训练样本不能全都分类正确，但这个分类器的泛化能力比图5要好。
尽管图7中的简单的线性分类器比图5中的非线性分类器的效果差，但是图7的分类器的泛化能力强。这是因为分类器没有把样本数据的噪声和异常也进行学习。另一方面说，使用更少的特征，维度灾难就能避免，就不会出现对训练样本过拟合的现象。
图8用不同的方式解释上面的内容。假设我们只使用一个特征来训练分类器，1D特征值的范围限定在0到1之间，且每只猫和狗对应的特征值是唯一的。如果我们希望训练样本的特征值占特征值范围的20%，那么训练样本的数量就要达到总体样本数的20%。现在，如果增加第二个特征，也就是从直线变为平面2D特征空间，这种情况下，如果要覆盖特征值范围的20%，那么训练样本数量就要达到总体样本数的45%（0.450.45=0.2）。而在3D空间中，如果要覆盖特征值范围的20%，就需要训练样本数量达到总体样本数的58%（0.580.58*0.58=0.2）。
图8. 覆盖特征值范围20%所需的训练样本数量随着维度增加呈指数型增长
换句话说，如果可用的训练样本数量是固定的，那么如果增加特征维度的话，过拟合就会发生。另一方面，如果增加特征维度，为了覆盖同样的特征值范围、防止过拟合，那么所需的训练样本数量就会成指数型增长。
在上面的例子中，我们展示了维度灾难会引起训练数据的稀疏化。使用的特征越多，数据就会变得越稀疏，从而导致分类器的分类效果就会越差。维度灾难还会造成搜索空间的数据稀疏程度分布不均。事实上，围绕原点的数据（在超立方体的中心）比在搜索空间的角落处的数据要稀疏得多。这可以用下面这个例子来解释：
想象一个单位正方形代表了2D的特征空间，特征空间的平均值位于这个单位正方形的中心处，距中心处单位距离的所有点构成了正方形的内接圆。没有落在单位圆的训练样本距离搜索空间的角落处更距离中心处更近，而这些样本由于特征值差异很大（样本分布在正方形角落处），所有难以分类。因此，如果大部分样本落在单位内接圆里，就会更容易分类。如图9所示：
图9. 落在单位圆之外的训练样本位于特征空间角落处，比位于特征空间中心处的样本更难进行分类。
一个有趣的问题是当我们增加特征空间的维度时，随着正方形（超立方体）的体积变化，圆形（超球体）的体积是如何变化的？无论维度如何变化，超立方体的体积都是1，而半径为0.5的超球体的体积随着维度d的变化为：
图10展示了随着维度d的增加，超球面的体积是如何变化的：
图10. 维度d很大时，超球面的体积趋于零
这表明了随着维度变得越来越大，超球体的体积趋于零，而超立方体的体积是不变的。这种令人惊讶的反直觉发现部分解释了在分类中维度灾难的问题：在高维空间中，大部分的训练数据分布在定义为特征空间的超立方体的角落处。就像之前提到的，特征空间角落处的样本比超球体内的样本更加难以进行正确分类。图11分别从2D、3D和可视化的8D超立方体（2^8=256个角落）的例子论证了这个结论。
图11. 随着维度增加，大部分数量数据分布在角落处
对于8维的超球体，大约98%的数据集中在它256个角落处。其结果是，当特征空间的维度变得无限大时，从样本点到质心的最大、最小欧氏距离的差值与其最小欧式距离的比值趋于零：
因此，距离测量在高维空间中逐渐变得无效。因为分类器是基于这些距离测量的（例如Euclidean距离、Mahalanobis距离、Manhattan距离），所以低维空间特征更少，分类更加容易。同样地，在高维空间的高斯分布会变平坦且尾巴更长。
五、如何解决维度灾害
理论上训练样本时无限多的，那么维度灾难不会发生，我们可以使用无限多的特征来获得一个完美的分类器。训练数据越少，使用的特征就要越少。随着维度增加，训练样本的数量要求随指数增加。
M个特征替换N个特征，M个特征由原始特征组合而成。这种通过对原始特征进行优化的线性或非线性组合来减少问题维度的算法称为特征提取。一个著名的维度降低技术是主成分分析法（PCA），它去除不相关维度，对N个原始特征进行线性组合。
过拟合只在高维空间中预测相对少的参数和低维空间中预测多参数这两种情况下发生。
一项非常有用的被用来测试和避免过拟合的技术是交叉验证。交叉验证将原始训练数据分成多个训练样本子集。在分类器进行训练过程中，一个样本子集被用来测试分类器的准确性，其他样本用来进行参数估计。
