机器学习Decision Tree

    研究了一个星期多的DecisionTree，简单的做一下记录。

    决策树的目的是为了产生一颗泛化能力强，处理未见实例强的决策树，基本流程就是分治。

    下面是决策树学习的基本算法（参考南京大学机器学习周志华教授课件）：

决策树算法

    主要讲解一下ID3决策树，ID3是通过information entropy or Gini计算最大样本信息增益，之后对样本通过该特征进行划分，以此递归形成决策树。

    递归的三种终止方式：1：信息增益为负，2：所有样本的特征值都相同，3：所有样本属性相同。

    information entropy的计算方式（参考南京大学机器学习课件）:

entropy

Gini计算方式（参考南京大学机器学习课件）：

Gini

    两个计算方式同样都是结果越小，样本纯度越高，信息增益是对样本进行划分之后，对新结点的熵或基尼不纯度赋予权重之后想加，和原来的进行比较。看增益是多少。

    信息增益计算方式（参考南京大学机器学习课件）:

信息增益

信息增益率（参考南京大学机器学习课件）：

信息增益率

    由此两个增益公式可以得到一个启发式：通过信息增益高于平均水平的，找到信息增益率最高的最为分割数据的特征属性。

    之后就可以通过不断递归样本，进行决策树的构建。

    由于决策树会对样本进行充分的训练，很有可能生成的决策树对样本出现过拟合的情况，所以要对决策树进行剪枝处理：

    剪枝主要是通过合并子节点来计算预测准确率有没有提升，如果有提升，就舍弃子节点，合并到一个节点上，具体的剪枝方式有预剪枝和后剪枝。

    预剪枝：在构建决策树的时候，从头部开始进行测试，是不是要剪枝

    后剪枝：构建完成之后，从子叶结点往根部开始进行测试，是不是要剪枝

    当然为了避免过拟合，还可以对决策树进行超参数的规划。不过这样做会增加决策树欠拟合的风险，不过可以通过GridsearchCV来测量最佳的超参数规划方式，达到最佳的预测效果。

     一般在构建决策树的时候，要对样本进行离散化处理，就是通常说的哑变量计算。主要是为了将那些不回归的数据离散化之后，容易Building。但是对于哪些连续性数据，就没办法进行离散化处理了，因为无法对其进行维度的提升。

    处理方式为：取两个临近值的中值对数据分割为两部分，之后进行类似于回归算法一样的计算。

    但是还有一部分数据是缺失的，对于缺失数据：如果样本量超级大，缺失量超级小，那么缺失数据可以忽略不计，因为可能出现重复数据。但是如果缺失量很大，或者说缺失了非常重要的特征属性，那么还是建议联系DBA把丢失的数据找回来，或者可以在数据由有缺失的时候，计算到缺失列了，将剩下的特征值按照决策树子节点数据量的权重对其进行加权，然后分别怼入子节点。

    如果样本不大，可以在构建之前对数据进行预分类，可以让决策树加速构建。但是样本如果很大，就不建议对其进行预分类了，因为预分类所消耗的时间，比加速节省的时间还要大。

    以上是对分类问题的决策树构建

    对于回归问题

    主要是计算Mean Square Error将样本通过方差最小的方式进行划分。

    之后将怼入到叶子叶结点的数据求平均值。

参考文献：

[1]Aurelien Geron.hands-On Machine learning with Scikit-Learn & TensorFlow[learning ].南京大学出版社，2017-10：167-179.

[2]周志华.机器学习[learning].清华大学出版社，2016-01:73-95.

[3]Toby Segaran.集体智慧编程[learning].电子工业出版社，2015-03:142-165.