机器学习 - Stella2019/study GitHub Wiki

Adaboost、GBDT和 Xgboost的区别？

1. 传统GBDT以CART作为基分类器，xgboost还支持线性分类器，这个时候xgboost相当于带L1和L2正则化项的逻辑斯蒂回归（分类问题）或者线性回归（回归问题）。

2. 2传统GBDT在优化时只用到一阶导数信息，xgboost则对代价函数进行了二阶泰勒展开，同时用到了一阶和二阶导数。顺便提一下，xgboost工具支持自定义代价函数，只要函数可一阶和二阶求导。

3． xgboost在代价函数里加入了正则项，用于控制模型的复杂度。正则项里包含了树的叶子节点个数、每个叶子节点上输出的score的L2模的平方和。从Bias-variancetradeoff角度来讲，正则项降低了模型的variance，使学习出来的模型更加简单，防止过拟合，这也是xgboost优于传统GBDT的一个特性。

4. Shrinkage（缩减），相当于学习速率（xgboost中的eta）。xgboost在进行完一次迭代后，会将叶子节点的权重乘上该系数，主要是为了削弱每棵树的影响，让后面有更大的学习空间。实际应用中，一般把eta设置得小一点，然后迭代次数设置得大一点。（补充：传统GBDT的实现也有学习速率）

5. 列抽样（column subsampling）。xgboost借鉴了随机森林的做法，支持列抽样，不仅能降低过拟合，还能减少计算，这也是xgboost异于传统gbdt的一个特性。

6. 对缺失值的处理。对于特征的值有缺失的样本，xgboost可以自动学习出它的分裂方向。

7. xgboost工具支持并行。boosting不是一种串行的结构吗?怎么并行的？注意xgboost的并行不是tree粒度的并行，xgboost也是一次迭代完才能进行下一次迭代的（第t次迭代的代价函数里包含了前面t-1次迭代的预测值）。xgboost的并行是在特征粒度上的。我们知道，决策树的学习最耗时的一个步骤就是对特征的值进行排序（因为要确定最佳分割点），xgboost在训练之前，预先对数据进行了排序，然后保存为block结构，后面的迭代中重复地使用这个结构，大大减小计算量。这个block结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行。

可并行的近似直方图算法。树节点在进行分裂时，我们需要计算每个特征的每个分割点对应的增益，即用贪心法枚举所有可能的分割点。当数据无法一次载入内存或者在分布式情况下，贪心算法效率就会变得很低，所以xgboost还提出了一种可并行的近似直方图算法，用于高效地生成候选的分割点。 Adaboost和gbdt的区别是adaboost对于每个样本有一个权重，样本预估误差越大，权重越大。gradientboosting则是直接用梯度拟合残差，没有样本权重的概念。

Boost 和 Bagging的区别

(1) 训练数据采样: boost是全部基模型使用相同的训练集, 而bagging方法是有放回的独立随机采样(每个基模型使用的训练集是独立分布的). (2) 训练数据权重:boost在训练过程中, 增加易错样本的权重, 样本权重分布不同; bagging所有数据样本权重相同. (3) 训练方式: boost是串行训练,拟合残差, 降低偏差; bagging是并行训练, 降低方差; (4) 目标函数: boost中每个基模型都有相对应的权重, 结果好的权重高; bagging中所有基模型权重相同. (5) Bagging里每个分类模型都是强分类器，因为降低的是方差，方差过高是过拟合 Boosting里每个分类模型都是弱分类器，因为降低的是偏度，偏度过高是欠拟合 (6) Bagging对样本重采样，对每一轮的采样数据集都训练一个模型，最后取平均。由于样本集的相似性和使用的同种模型，因此各个模型的具有相似的bias和variance

Boost方法的缺点

(1) 对异常样本敏感，异常样本可能会在迭代过程中获得较高的权重值，最终影响模型效果; (2) 由于弱学习器之间存在关联关系，难以并行训练模型。

XGBoost与GBDT的区别和联系?

xgboost是一种集成学习算法，属于4类常用的集成方法(blending, bagging, boosting, stacking)中的boosting算法类别。它是一个加法模型，基模型一般选择树模型，但也可以选择其它类型的模型如逻辑回归等。 blending集成方法和其他三种有本质上的区别. blending方法是在所有的基分类器已经知道(训练好)的情况下, 进行合并; 而其他的集成学习方法核心思想是“边学习边集成”, 在训练的同时完成集成策略. xgboost属于梯度提升树(GBDT)模型这个范畴，GBDT的基本想法是让新的基模型（GBDT以CART分类回归树为基模型）去拟合前面模型的偏差(boost类模型优点, 减小偏差)，从而不断将加法模型的偏差降低。相比于经典的GBDT，xgboost做了一些改进，从而在效果和性能上有明显的提升（划重点面试常考）。 (1) GBDT将目标函数泰勒展开到一阶，而xgboost将目标函数泰勒展开到了二阶。保留了更多有关目标函数的信息，对提升效果有帮助。 (2) GBDT是给新的基模型寻找新的拟合标签（前面加法模型的负梯度），而xgboost是给新的基模型寻找新的目标函数（目标函数关于新的基模型的二阶泰勒展开）。 (3) xgboost加入了叶子权重的L2正则化项，因而有利于模型获得更低的方差。 (4) xgboost增加了**自动处理缺失值特征的策略。**通过把带缺失值样本分别划分到左子树或者右子树，比较两种方案下目标函数的优劣，从而自动对有缺失值的样本进行划分，无需对缺失特征进行填充预处理。此外，xgboost还支持候选分位点切割，特征并行等，可以提升性能。

xgboost如何处理缺失值

通常情况下，我们人为在处理缺失值的时候大多会选用中位数、均值或是二者的融合来对数值型特征进行填补，使用出现次数最多的类别来填补缺失的类别特征。

很多的机器学习算法都无法提供缺失值的自动处理，都需要人为地去处理，但是xgboost模型却能够处理缺失值，也就是说模型允许缺失值存在。

原是论文中关于缺失值的处理将其看与稀疏矩阵的处理看作一样。在寻找split point的时候，不会对该特征为missing的样本进行遍历统计，只对该列特征值为non-missing的样本上对应的特征值进行遍历，通过这个技巧来减少了为稀疏离散特征寻找split point的时间开销。在逻辑实现上，为了保证完备性，会分别处理将missing该特征值的样本分配到左叶子结点和右叶子结点的两种情形，计算增益后选择增益大的方向进行分裂即可。可以为缺失值或者指定的值指定分支的默认方向，这能大大提升算法的效率。如果在训练中没有缺失值而在预测中出现缺失，那么会自动将缺失值的划分方向放到右子树。

决策树、RF、xgboost如何处理缺失值？判断特征重要性？缺失值不敏感？

1、随机森林模型怎么处理异常值?

随机森林是已故统计学家Leo Breiman提出的，和gradient boosted tree—样，它的基模型是决策树。在介绍RF时，Breiman就提出两种解决缺失值的方法 (Random forests - classification description):

方法1(快速简单但效果差)：

把数值型变量(numerical variables)中的缺失值用其所对应的类别中 (class)的中位数(median)替换。描述型变量(categorical variables)缺失的部分用所对应类别中出现最多的数值替代(most frequent non-missing value)。以数值型变量为例：

方法2(耗时费力但效果好)：

虽然依然是便用中位数出现次数最多的数来进行替换，方法2引入了权重。即对需要替换的数据先和其他数据做相似度测量(proximity measurement)也就是下面公式中的Weight，在补全缺失点是相似的点的数据会有更高的权重W。以数值型变量为例：

Breiman说明了第二种方法的效果更好，但需要的时间更长，这也是为什么工具包中不提供数据补全的功能，因为会影响到工具包的效率。

2、在训练、验证、测试含有缺失值时怎么办？

在选择分裂属性的时候，训练样本存在缺失值，如何处理？

计算分裂损失减少值时，忽略特征缺失的样本，最终计算的值乘以比例（实际参与计算的样本数除以总的样本数。

假如你使用ID3算法，那么选择分类属性时，就要计算所有属性的熵增(信息增益，Gain)。假设10个样本，属性是a,b,c。在计算a属性熵时发现，第10个样本的a属性缺失，那么就把第10个样本去掉，前9个样本组成新的样本集，在新样本集上按正常方法计算a属性的熵增。然后结果乘0.9（新样本占raw样本的比例），就是a属性最终的熵。

分类属性选择完成，对训练样本分类，发现样本属性缺失怎么办？

将该样本分配到所有子节点中，权重由1变为具有属性a的样本被划分成的子集样本个数的相对比率，计算错误率的时候，需要考虑到样本权重。

比如该节点是根据a属性划分，但是待分类样本a属性缺失，怎么办呢？假设a属性离散，有1,2两种取值，那么就把该样本分配到两个子节点中去，但是权重由1变为相应离散值个数占样本的比例。然后计算错误率的时候，注意，不是每个样本都是权重为1，存在分数。

训练完成，给测试集样本分类，有缺失值怎么办？

分类时，如果待分类样本有缺失变量，而决策树决策过程中没有用到这些变量，则决策过程和没有缺失的数据一样；否则，如果决策要用到缺失变量，决策树也可以在当前节点做多数投票来决定（选择样本数最多的特征值方向）。

如果有单独的缺失分支，使用此分支。把待分类的样本的属性a值分配一个最常出现的a的属性值，然后进行分支预测。根据其他属性为该待分类样本填充一个属性a值，然后进行分支处理。在决策树中属性a节点的分支上，遍历属性a节点的所有分支，探索可能所有的分类结果，然后把这些分类结果结合起来一起考虑，按照概率决定一个分类。待分类样本在到达属性a节点时就终止分类，然后根据此时a节点所覆盖的叶子节点类别状况为其分配一个发生概率最高的类。

2.xgboost怎么处理缺失值?

xgboost处理缺失值的方法和其他树模型不同。根据作者TianqiChen在论文中章节3.4的介绍，xgboost把缺失值当做稀疏矩阵来对待，本身的在节点分裂时不考虑的缺失值的数值。缺失值数据会被分到左子树和右子树分别计算损失，选择较优的那一个。如果训练中没有数据缺失，预测时出现了数据缺失，那么默认被分类到右子树。

这样的处理方法固然巧妙，但也有风险：假设了训练数据和预测数据的分布相同，比如缺失值的分布也相同，不过直觉上应该影响不是很大。

3、什么样的模型对缺失值更敏感？

树模型对缺失值的敏感度低，大部分时候可以在数据缺失时使用。涉及到距离度量(distancemeasurement)时，如计算两个点之间的距离，缺失数据就变得比较重要。因为涉及到"距离"这个概念，那么缺失值处理不当就会导致效果很差，如K近邻算法（KNN）、支持向量机(SVM)。线性模型的代价函数(loss function)往往涉及到距离(distance)的计算，计算预测值和真实值之间的差别，这容易导致对缺失值敏感。神经网络的鲁棒强，对于缺失数据不是非常敏感，但一般没有那么多数据可供使用。贝叶斯模型对于缺失数据也比较稳定，数据量很小的时候选贝叶斯模型。总体来看，对于有缺失值的数据在经过缺失处理后：

数据量很小，朴素贝叶斯数据量适中或者较大，用树横型，优先xgboost 数据量较大，也可以用神经网络避免使用距离度量相关的模型，如KNN和SVM 4.xgboost 判断特征重要程度的三种指标 get_fscore 有三种种评判特征重要程度的方法：

‘weight’ - the number of times a feature is used to split the data across all trees. ‘gain’ - the average gain of the feature when it is used in trees. ‘cover’ - the average coverage of the feature when it is used in trees.

weight - 该特征在所有树中被用作分割样本的特征的次数。

gain - 在所有树中的平均增益。

cover - 在树中使用该特征时的平均覆盖范围。(还不是特别明白)

特征并行

注意XGBoost的并行不不是tree粒度的并行，XGBoost也是⼀次迭代完才能进行下一次迭代的（第t次迭代的损失函数里包含了前面t − 1次迭代的预测值）。XGBoost的并行是在特征粒度上的。我们知道，决策树的学习最耗时的一个步骤就是对特征的值进行排序（因为要确定最佳分割点），XGBoost在训练之前，预先对数据进行了排序，然后保存为block(块)结构，后面的迭代中重复地使用这个结构，大大减小计算量。这个block结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行。

GBDT 和随机森林的区别？

随机森林采用的是bagging的思想，bagging又称为bootstrap aggreagation，通过在训练样本集中进行有放回的采样得到多个采样集，基于每个采样集训练出一个基学习器，再将基学习器结合。随机森林在对决策树进行bagging的基础上，在决策树的训练过程中引入了随机属性选择。传统决策树在选择划分属性的时候是在当前节点属性集合中选择最优属性，而随机森林则是对结点先随机选择包含k个属性的子集，再选择最有属性，k作为一个参数控制了随机性的引入程度。另外，GBDT训练是基于Boosting思想，每一迭代中根据错误更新样本权重，因此是串行生成的序列化方法，而随机森林是bagging的思想，因此是并行化方法。

过拟合的理解

过拟合如果一味的去提高训练数据的预测能力，所选模型的复杂度往往会很高，这种现象称为过拟合。所表现的就是模型训练时候的误差很小，但在测试的时候误差很大。产生的原因过拟合原因

样本数据的问题。样本数量太少抽样方法错误，抽出的样本数据不能有效足够代表业务逻辑或业务场景。比如样本符合正态分布，却按均分分布抽样，或者样本数据不能代表整体数据的分布样本里的噪音数据干扰过大
模型问题模型复杂度高、参数太多决策树模型没有剪枝权值学习迭代次数足够多(Overtraining),拟合了训练数据中的噪声和训练样例中没有代表性的特征. 解决方法
样本数据方面。增加样本数量，对样本进行降维，添加验证数据抽样方法要符合业务场景清洗噪声数据
模型或训练问题控制模型复杂度，优先选择简单的模型，或者用模型融合技术。利用先验知识，添加正则项。L1正则更加容易产生稀疏解、L2正则倾向于让参数w趋向于0. 交叉验证不要过度训练，最优化求解时，收敛之前停止迭代。决策树模型没有剪枝权值衰

为什么会产生过拟合，有哪些方法可以预防或克服过拟合？

一般在机器学习中，将学习器在训练集上的误差称为训练误差或者经验误差，在新样本上的误差称为泛化误差。显然我们希望得到泛化误差小的学习器，但是我们事先并不知道新样本，因此实际上往往努力使经验误差最小化。然而，当学习器将训练样本学的太好的时候，往往可能把训练样本自身的特点当做了潜在样本具有的一般性质。这样就会导致泛化性能下降，称之为过拟合，相反，欠拟合一般指对训练样本的一般性质尚未学习好，在训练集上仍然有较大的误差。欠拟合：一般来说欠拟合更容易解决一些，例如增加模型的复杂度，增加决策树中的分支，增加神经网络中的训练次数等等。过拟合：一般认为过拟合是无法彻底避免的，因为机器学习面临的问题一般是np-hard,但是一个有效的解一定要在多项式内可以工作，所以会牺牲一些泛化能力。过拟合的解决方案一般有增加样本数量，对样本进行降维，降低模型复杂度，利用先验知识(L1,L2正则化)，利用cross-validation，early stopping等等。

特征向量的缺失值处理

缺失值较多.直接将该特征舍弃掉，否则可能反倒会带入较大的noise，对结果造成不良影响。
缺失值较少,其余的特征缺失值都在10%以内，我们可以采取很多的方式来处理:

把NaN直接作为一个特征，假设用0表示；
用均值填充；
用随机森林等算法预测填充

K-meas：

基本K-Means算法的思想很简单，事先确定常数K，常数K意味着最终的聚类类别数，首先随机选定初始点为质心，并通过计算每一个样本与质心之间的相似度(这里为欧式距离)，将样本点归到最相似的类中，接着，重新计算每个类的质心(即为类中心)，重复这样的过程，知道质心不再改变，最终就确定了每个样本所属的类别以及每个类的质心。由于每次都要计算所有的样本与每一个质心之间的相似度，故在大规模的数据集上，K-Means算法的收敛速度比较慢。初始化常数K，随机选取初始点为质心重复计算一下过程，直到质心不再改变计算样本与每个质心之间的相似度，将样本归类到最相似的类中重新计算质心输出最终的质心以及每个类

K- means

KMeans怎么选择聚类中心？如果存在空块怎么办？

选择批次距离尽可能远的K个点首先随机选择一个点作为第一个初始类簇中心点，然后选择距离该点最远的那个点作为第二个初始类簇中心点，然后再选择距离前两个点的最近距离最大的点作为第三个初始类簇的中心点，以此类推，直至选出K个初始类簇中心点。
选用层次聚类或者Canopy算法进行初始聚类，然后利用这些类簇的中心点作为KMeans算法初始类簇中心点。常用的层次聚类算法有BIRCH和ROCK，在此不作介绍

K 值的选择是 K 均值聚类最大的问题之一，这也是 K 均值聚类算法的主要缺。实际上，我们希望能够找到一些可行的办法来弥补这一缺点，或者说找到 K 值的合理估计方法。但是，K 值的选择一般基于经验和多次实验结果。例如采用手肘法，我们可以尝试不同的 K 值，并将不同 K 值所对应的损失函数画成折线，横轴为 K 的取值，纵轴为误差平方和所定义的损失函数

由图可见，K 值越大，距离和越小；并且，当 K=3 时，存在一个拐点，就像人的肘部一样；当 K∈ (1,3) 时，曲线急速下降；当 K>3 时，曲线趋于平稳。手肘法认为拐点就是 K 的最佳值。

手肘法是一个经验方法，缺点就是不够自动化，因此研究员们又提出了一些更先进的方法，其中包括比较有名的 Gap Statistic方法同。 Gap Statistic/方法的优点是，不再需要肉眼判断，而只需要找到最大的 Gap statistic）所对应的 K 即可，因此该方法也适用于批量化作业。在这里我们继续使用上面的损失函数，当分为 K 簇时寸应的损失函数记为 D-。Gap Statistici 定义为

Gap (K=E (ogdk -logdk

其中 E (logD）是 logD 的期望，一般通过蒙特卡洛模拟产生。我们在样本所在的区域内按照均匀分布随机地产生和原始样本数一样多的随机样本，并对这个随机样本做 K 均值，得到一个 D：重复多次就可以计算出 E (logD）的近似值。那么 Gap (K）有什么物理含义呢？它可以视为随机样本的损失与实际样本的损失之差。试想实际样本对应的最佳簇数为 K，那么实际样本的损失应该相对较小，随机样本损失与实际样本损失之差也相应地达到最小值，从而 Gap（取得最大值所对应的 K 值就是最佳的簇数。根据式（5.4) 计算 K=1,2,,9 所对应的 Gap Statistic，

采用核函数。

采用核函数是另一种可以尝试的改进方向。传统的欧式距离度量方式，使得 K 均值算法本质上假设了各个数据簇的数据具有一样的先验概率，并呈现球形或者高维球形分布，这种分布在实际生活中并不常见。面对非凸的数据分布形状时，可能需要引入核函数来优化，这时算法又称为核 K 均值算法，是核聚类方法的一种。核聚类方法的主要思想是通过一个非线性映射，将输入空间中的数据点映射到高位的特征空间中，并在新的特征空间中进行聚类。非线性映射增加了数据点线性可分的概率，从而在经典的聚类算法失效的情况下，通过引入核函数可以达到更为准确的聚类结果

K- means++算法

K 均值的改进算法中，对初始值选择的改进是很重要的一部分。而这类算法中，最具影响力的当属 K- means++算法。原始 K 均值算法最开始随机选取数据集中 K 个点作为聚类中心，而 K- means++按照如下的思想选取 K 个聚类中心。假设已选取了 n 个初始聚类中心（0 <n <K），则在选取第 n+1 个聚类中心时，距离当前 n 个聚类中心越远的点会有更高的概率被选为第 n+1 个聚类中心。在选取第一个聚类中心（m=1) 时同样通过随机的方法。可以说这也符合我们的直觉，聚类中心当然是互相离得越远越好。当选择完初始点后，K- means++后续的执行和经典 K 均值算法相同，这也是对初始值选择进行改进的方法等共同点。

决策树的训练

明白了决策树的结构和工作原理之后，下面就是训练的过程了。在理清楚原理之前，我们先来看下数据。我们根据上面决策树的结构，很容易发现，训练数据应该是这样的表格:

信息熵与信息增益信息熵这个词很令人费解，它英文原文是information entropy，其实一样难以理解。因为entropy本身是物理学和热力学当中的概念，用来衡量物体分散的不均匀程度。也就是说熵越大，说明物体分散得程度越大，可以简单理解成越散乱。比如我们把房间里一盒整理好的乒乓球打翻，那么里面的乒乓球显然会散乱到房间的各个地方，这个散乱的过程可以理解成熵增大的过程。信息熵也是一样的含义，用来衡量一份信息的散乱程度。熵越大，说明信息越杂乱无章，否则说明信息越有调理。信息熵出自大名鼎鼎的信息学巨著《信息论》，它的作者就是赫赫有名的香农。但是这个词并不是香农原创，据说是计算机之父冯诺依曼取的，他去这个名字的含义也很简单，因为大家都不明白这个词究竟是什么意思。之前我们曾经在介绍交叉熵的时候详细解释过这个概念，我们来简单回顾一下。对于一个事件X来说，假设它发生的概率是P(X)，那么这个事件本身的信息量就是: I(X) = −log2P(X) 比如说世界杯中国队夺冠的概率是1/128，那么我们需要用8个比特才能表示，说明它信息量很大。假如巴西队夺冠的概率是1/4，那么只要2个比特就足够了，说明它的信息量就很小。同样一件事情，根据发生的概率不同，它的信息量也是不同的。那么信息熵的含义其实就是信息量的期望，也就是用信息量乘上它的概率: H(X) = −P(X)log2P(X) 同样，假设我们有一份数据集合，其中一共有K类样本，每一类样本所占的比例是$P(K)$，那么我们把这个比例看成是概率的话，就可以写出这整个集合的信息熵: H(D)=−∑K P(K)log2(P(K)) i=1 理解了信息熵的概念之后，再来看信息增益就很简单了。信息增益说白了就是我们划分前后信息熵的变化量，假设我们选择了某一个特征进行切分，将数据集D切分成了D1和D2。那么 H(D) − (H(D2 ) + H(D1 )) 就叫做信息增益，也就是切分之后信息熵与之前的变化量。我们根据熵的定义可以知道，如果数据变得纯粹了，那么信息熵应该会减少。减少得越多，说明切分的效果越好。所以我们就找到了衡量切分效果的方法，就是信息增益。我们根据信息增益的定义，可以很简单地理出整个决策树建立的过程。就是我们每次在选择切分特征的时候，都会遍历所有的特征，特征的每一个取值对应一棵子树，我们通过计算信息增益找到切分之后增益最大的特征。上层的结构创建好了之后，通过递归的形式往下继续建树，直到切分之后的数据集变得纯粹，或者是所有特征都使用结束了为止。这个算法称为ID3算法，它也是决策树最基础的构建算法。这里有一个小细节，根据ID3算法的定义，每一次切分选择的是特征，而不是特征的取值。并且被选中作为切分特征的特征的每一个取值都会建立一棵子树，也就是说每一个特征在决策树当中都只会最多出现一次。因为使用一次之后，这个特征的所有取值就都被使用完了。举个例子，比如拍打声音是否清脆这个特征，我们在一开始就选择了它。根据它的两个取值，是和否都建立了一棵子树。那么如果我们在子树当中再根据这个特征拆分显然没有意义，因为子树中的所有数据的这个特征都是一样的。另外，ID3算法用到的所有特征必须是离散值，因为连续值无法完全切分。如果西瓜的重量是一个特征，那么理论上来说所有有理数都可能是西瓜的质量，我们显然不可能穷尽所有的取值。这一点非常重要，不仅关系到我们实现的决策树是否正确，也直接关系到我们之后理解其他的建树算法。

上一篇文章当中介绍了一种最简单构造决策树的方法——ID3算法，也就是每次选择一个特征进行拆分数据。这个特征有多少个取值那么就划分出多少个分叉，整个建树的过程非常简单。既然我们已经有了ID3算法可以实现决策树，那么为什么还需要新的算法?显然一定是做出了一些优化或者是进行了一些改进，不然新算法显然是没有意义的。所以在我们学习新的算法之前，需要先搞明白，究竟做出了什么改进，为什么要做出这些改进。一般来说，改进都是基于缺点和不足的，所以我们先来看看ID3算法的一些问题。其中最大的问题很明显，就是它无法处理连续性的特征。不能处理的原因也很简单，因为ID3在每次在切分数据的时候，选择的不是一个特征的取值，而是一个具体的特征。这个特征下有多少种取值就会产生多少个分叉，如果使用连续性特征的话，比如说我们把西瓜的直径作为特征的话。那么理论上来说每个西瓜的直径都是不同的，这样的数据丢进ID3算法当中就会产生和样本数量相同的分叉，这显然是没有意义的。其实还有一个问题，藏得会比较深一点，是关于信息增益的。我们用划分前后的信息熵的差作为信息增益，然后我们选择带来最大信息增益的划分。这里就有一个问题了，这会导致模型在选择的时候，倾向于选择分叉比较多的特征。极端情况下，就比如说是连续性特征好了，每个特征下都只有一个样本，那么这样算出来得到的信息熵就是0，这样得到的信息增益也就非常大。这是不合理的，因为分叉多的特征并不一定划分效果就好，整体来看并不一定是有利的。针对这两个问题，提出了改进方案，也就是说C4.5算法。严格说起来它并不是独立的算法，只是ID3算法的改进版本。下面我们依次来看看C4.5算法究竟怎么解决这两个问题。信息增益比首先，我们来看信息增益的问题。前面说了，如果我们单纯地用信息增益去筛选划分的特征，那么很容易陷入陷阱当中，选择了取值更多的特征。针对这个问题，我们可以做一点调整，我们把信息增益改成信息增益比。所谓的信息增益比就是用信息增益除以我们这个划分本身的信息熵，从而得到一个比值。对于分叉很多的特征，它的自身的信息熵也会很大。因为分叉多，必然导致纯度很低。所以我们这样可以均衡一下特征分叉带来的偏差，从而让模型做出比较正确的选择。我们来看下公式，真的非常简单: Gain_ratio = Gain(D,a) IV(a) 这里的D就是我们的训练样本集，a是我们选择的特征，IV(a)就是这个特征分布的信息熵。我们再来看下IV的公式: IV (a) = − ∑V pv log2 pv v=1 解释一下这里的值，这里的V是特征a所有取值的集合。 pv 自然就是每一个v对应的占比，所以这就是一个特征a的信息熵公式。处理连续值 C4.5算法对于连续值同样进行了优化，支持了连续值，支持的方式也非常简单，对于特征a的取值集合V来说，我们选择一个阈值t进行划分，将它划分成小于t的和大于t的两个部分。也就是说C4.5算法对于连续值的切分和离散值是不同的，对于离散值变量，我们是对每一种取值进行切分，而对于连续值我们只切成两份。其实这个设计非常合理，因为对于大多数情况而言，每一条数据的连续值特征往往都是不同的。而且我们也没有办法很好地确定对于连续值特征究竟分成几个部分比较合理，所以比较直观的就是固定切分成两份，总比无法用上好。在极端情况下，连续值特征的取值数量等于样本条数，那么我们怎么选择这个阈值呢?即使我们遍历所有的切分情况，也有n-1种，这显然是非常庞大的，尤其在样本数量很大的情况下。

这份数据是我们队西瓜直径这个特征排序之后的结果，我们可以看出来，训练目标改变的值其实只有3个，分别是直径5，7还有8的时候，我们只需要考虑这三种情况就好了，其他的情况可以不用考虑。我们综合考虑这两点，然后把它们加在之前ID3模型的实现上就好了。

PCA算法两种实现方法

(1) 基于特征值分解协方差矩阵实现PCA算法

输入：数据集X={ x1, x2, x3, …, xn }，需要降到k维。

去平均值(即去中心化)，即每一位特征减去各自的平均值。
计算协方差矩阵(1/n)XXT ,注：这里除或不除样本数量n或n-1,其实对求出的特征向量没有影响。
用特征值分解方法求协方差矩阵(1/n)XXT,的特征值与特征向量。
对特征值从大到小排序，选择其中最大的k个。然后将其对应的k个特征向量分别作为行向量组成特征向量矩阵P。
将数据转换到k个特征向量构建的新空间中，即Y=PX。总结：

1)关于这一部分为什么用 , ,这里面含有很复杂的线性代数理论推导

PCA的数学原理: http://blog.codinglabs.org/articles/pca-tutorial.html

2)关于为什么用特征值分解矩阵，是因为是方阵，能很轻松的求出特征值与特征向量。当然，用奇异值分解也可以，是求特征值与特征向量的另一种方法。

(2) 基于SVD分解协方差矩阵实现PCA算法

输入：数据集X={ x1, x2, x3, …, xn }，需要降到k维。

去平均值，即每一位特征减去各自的平均值。
计算协方差矩阵。
通过SVD计算协方差矩阵的特征值与特征向量。
对特征值从大到小排序，选择其中最大的k个。然后将其对应的k个特征向量分别作为列向量组成特征向量矩阵。
将数据转换到k个特征向量构建的新空间中。

在PCA降维中，我们需要找到样本协方差矩阵XXT的最大k个特征向量，然后用这最大的k个特征向量组成的矩阵来做低维投影降维。可以看出，在这个过程中需要先求出协方差矩阵 XXT,当样本数多、样本特征数也多的时候，这个计算还是很大的。当我们用到SVD分解协方差矩阵的时候，SVD有两个好处：

有一些SVD的实现算法可以先不求出协方差矩阵XXT 也能求出我们的右奇异矩阵V。也就是说，我们的PCA算法可以不用做特征分解而是通过SVD来完成，这个方法在样本量很大的时候很有效。实际上，scikit-learn的PCA算法的背后真正的实现就是用的SVD，而不是特征值分解。

2)注意到PCA仅仅使用了我们SVD的左奇异矩阵，没有使用到右奇异值矩阵，那么右奇异值矩阵有什么用呢？

假设我们的样本是mn的矩阵X，如果我们通过SVD找到了矩阵 XXT 最大的k个特征向量组成的kn的矩阵VT ,则我们可以做如下处理：

可以得到一个mk的矩阵X',这个矩阵和我们原来mn的矩阵X相比，列数从n减到了k，可见对列数进行了压缩。也就是说，左奇异矩阵可以用于对行数的压缩；右奇异矩阵可以用于对列(即特征维度)的压缩。这就是我们用SVD分解协方差矩阵实现PCA可以得到两个方向的PCA降维(即行和列两个方向)。

PCA的理论推导

PCA可以通过两个思路推导，1）最大方差理论；2）最小化降维造成的损失 https://zhuanlan.zhihu.com/p/37777074 他们最终推导的结果相同降维后低维空间的位数d’通常是由用户事先指定，或通过在d’ 值不同的低维空间中对k近邻分类器（或其它开销较小的学习器）进行交叉验证来选取较好的d’ 值。对PCA，还可从重构的角度设置一个阈值，例如t=95%,然后选取使下式成立的最小值d’：

PCA仅需保留投影矩阵与样本的均值向量即可通过简单的向量减法和矩阵向量乘法将新样本投影至低维空间中。显然，低维空间与原始高维空间必有不同，因为对应于最小的d-d’个特征值的特征向量被舍弃了，这是降维导致的结果。但舍弃这部分信息往往是必要的：一方面，舍弃这部分信息之后能使样本的采样密度增大，这正是降维的重要动机；另一方面，当数据收到噪声影响时，最小的特征值所对应的特征向量往往与噪声有关，将它们舍弃能在一定程度上起到去噪的效果。