决策树是一种用于分类和回归任务的非参数监督学习算法。它是由根节点、分支、内部节点和叶节点组成的分层树结构。从上图可以看出，决策树是从根节点开始的，根节点没有任何传入分支。根节点的传出分支然后馈送内部节点（也称为决策节点）。两种类型的节点都根据可用能力执行评估以形成同质子集，这些子集由叶节点或终端节点表示。叶节点代表数据集中所有可能的结果。决策树的类型Hunt算法于1960年代提出，最初在心理学上用于模拟人类学习，为许多常用的决策树算法奠定了基础，例如：ID3：该算法的开发归功于RossQuinlan，全称是《IterativeDichotomiser3》（《迭代二分法3》）。该算法使用信息熵和信息增益作为评价候选分裂的指标。C4.5：该算法是ID3的后期扩展，也是昆兰开发的。它可以使用信息增益或增益比来评估决策树中的割点。CART：术语“CART”代表“分类和回归”，由LeoBreiman创造。该算法通常利用“基尼杂质”来确定理想的分裂属性。基尼不纯度衡量随机选择的属性被错误分类的频率。使用这种评价方法时，基尼杂质越小越好。决策树构建的详细构建过程可以参考：决策树构建原理案例数据集准备泰坦尼克号数据集数据处理数据集幸存者统计决策树构建与可视化#预定预测目标变量名Target=["Survived"]##定义模型的自变量名train_x=["Pclass","Sex","SibSp","Parch","Embarked","Age_band","re??"]##将训练集拆分为Trainingset和验证集X_train,X_val,y_train,y_val=train_test_split(data[train_x],data[Target],test_size=0.25,random_state=1)##首先使用默认参数建立决策树模型dtc1=DecisionTreeClassifier(random_state=1)##使用训练数据进行训练dtc1=dtc1.fit(X_train,y_train)##输出其在训练数据和验证数据集上的预测精度dtc1_lab=dtc1.predict(X_train)dtc1_pre=dtc1.predict(X_val)##可视化得到的决策树结构dot_data=StringIO()export_graphviz(dtc1,out_file=dot_data,feature_names=X_train.columns,filled=True,rounded=True,special_characters=True)graph=pydotplus.graph_from_dot_data(dot_data.getvalue())图片(graph.create_png())Unpruneddecisiontree观察上图所示的模型结构，可以发现该模型是一个非常复杂的决策树模型，决策树的层数远超10层。所以，用这个决策树得到的规则会很复杂。模型的可视化进一步证明得到的决策树模型存在严重的过拟合问题，需要对模型进行剪枝来简化模型。该模型在训练集上有74个错误样本，在测试集上有50个错误样本。观察图1所示的模型结构可以发现，该模型是一个非常复杂的决策树模型，决策树的层数远不止10层，所以利用这个决策树得到的规则可以会很复杂。模型的可视化进一步证明得到的决策树模型存在严重的过拟合问题，需要对模型进行剪枝来简化模型。决策树过拟合问题决策树学习使用“一对一”策略并执行贪婪搜索以识别决策树内的最佳分割点。然后以自上而下的回归方式重复此拆分过程，直到所有或大多数记录都标有特定的类标签。是否将所有数据点分类为同类子集在很大程度上取决于决策树的复杂性。较小的决策树更容易访问无法拆分的叶节点，即单个类中的数据点。然而，随着决策树规模的增长，保持这种纯度变得越来越困难，并且通常会导致落在给定子树中的数据太少。这种情况称为数据碎片，通常会导致数据过度拟合。因此，通常选择小型决策树，这符合奥卡姆剃刀原则的“简单有效原则”，即“非必要不增加实体”。换句话说，我们只应在必要时增加决策树的复杂性，因为最简单的往往是最好的。为了降低复杂度并防止过度拟合，通常采用剪枝算法；这个过程删除了不太重要的特征的分支。然后，通过交叉验证评估模型的拟合度。另一种保持决策树准确性的方法是使用随机森林算法形成一个集成；这种分类方法可以导致更准确的预测，尤其是在决策树分支彼此不相关的情况下。决策树的剪枝决策树的剪枝有两种思路：预剪枝（Pre-Pruning）后剪枝（Post-Pruning）预剪枝（Pre-Pruning）预剪枝是构建决策树的过程，划分前先对每个节点进行估计，如果对当前节点的划分不能提高决策树模型的泛化性能，则不对当前节点进行划分，将当前节点标记为叶节点。当熵不能进一步减少时，所有决策树构建方法都会停止创建分支的过程。为了避免过拟合，可以设置一个阈值。熵减少的量小于这个阈值，即使可以继续降低熵，也停止进一步的分支。但这种方法在实践中效果不佳。决策树模型的剪枝操作主要用到DecisionTreeClassifier()函数中的max_depth：指定决策树的最大深度max_leaf_nodes：指定模型的最大叶节点数min_sample_split：指定节点的最小样本数themodelallowsplitmin_samples_leaf:指定模型的一个叶子节点上需要的最小样本数这里使用参数网格搜索的方法对模型中的四个参数进行搜索，在验证集上的预测精度为准则。获得更合适的模型参数组合。params={'max_depth':np.arange(2,12,2),'max_leaf_nodes':np.arange(10,30,2),'min_samples_split':[2,3,4],'min_samples_leaf':[1,2]}clf=DecisionTreeClassifier(random_state=1)gcv=GridSearchCV(estimator=clf,param_grid=params)gcv.fit(X_train,y_train)model=gcv.best_estimator_model.fit(X_train,y_train)##视觉决策树修剪后的树结构.create_png())预剪枝后的决策树从剪枝后的决策树模型可以发现，这个模型相比未剪枝的模型有了很大的简化。该模型在训练集上有95个错误样本，但在测试集上只有47个错误样本。训练数据集混淆矩阵测试数据集混淆矩阵后剪枝（Post-Pruning）剪枝是在决策树构建完成后进行的。剪枝的过程是检查一组具有相同父节点的节点，判断它们合并后熵的增加是否小于某个阈值。如果真的很小，可以把这组节点合并成一个节点，这个节点包含了所有可能的结果。后修剪是迄今为止最常见的做法。后剪枝的剪枝过程是删除一些子树，用它们的叶节点代替。叶节点标识的类别由多数类标准确定。所谓多数原则，就是在剪枝过程中，删除部分子树，用叶节点代替。这个叶节点标识的类别是由这个子树中大多数训练样本所属的类别标识的。确定的类别称为Itisamajorityclass，（多数类在很多英文文献中也多次出现）。后剪枝算法有很多，这里简单总结如下：idea很直接，完整的决策树不是过拟合了吗？我将制作另一个测试数据集来纠正它。对于完整决策树中的一个非叶子节点的每个子树，我们尝试用一个叶子节点替换它，叶子节点的类别替换为该子树覆盖的训练样本中存在最多的类，所以即生成一棵简化的决策树，然后比较两棵决策树在测试数据集中的表现。如果简化后的决策树在测试数据集中的错误较少，则可以将子树替换为叶节点。算法以自下而上的方式遍历所有子树，直到没有子树可以被替换以提高测试数据集的性能时，算法可以终止。PessimisticErrorPruning（PEP，悲观剪枝）PEP剪枝算法是在C4.5决策树算法中提出的，用一个叶子节点代替一个子树（有多个叶子节点）（我研究过很多文章好像是用子树的根），与REP剪枝方法相比，它不需要单独的测试数据集。PEP算法首先确定这片叶子的经验误差率（empirical）为（E+0.5）/N，0.5为调整系数。对于有L个叶子的子树，错误数和子树的实例数应该是错误数和叶子的实例数之和，则子树的错误率为e然后是叶子节点用于替换子树，新叶子节点的类别由原子树节点的最优叶子节点决定，J为被替换叶子节点的误判次数，但还要加上0.5，即KJ+0.5。是否应该替换的最终判断标准是被替换子树的错误数-标准差>新叶子错误数的标准差，因为子树的错误数是一个随机变量，可以近似为验证后的二项分布。可以根据二项分布的标准差公式计算出标准差，从而判断是否应该剪掉分支。子树中有N个实例，即进行了N次实验，每次实验的错误概率为e，符合B(N,e)的二项分布。根据公式，均值为Ne，方差为Ne(1-e)，标准差为方差的平方根。Cost-ComplexityPruning（CCP，成本复杂性剪枝）在决策树中，这种剪枝技术由成本复杂性参数ccp_alpha参数化。ccp_alpha的值越大，剪枝的节点越多。简单来说，成本复杂度是一个门槛。如果模型的整体不纯度提高了大于此阈值的值，则模型只会将节点进一步拆分为其子节点，否则它会停止。当CCP值较低时，即使杂质减少不多，模型也会将节点拆分为子节点。随着树的深度增加，这一点很明显，也就是说，当我们沿着决策树向下移动时，我们看到分裂对模型整体不纯的变化贡献不大。然而，更高的拆分保证了类的正确分类，即更高的准确性。当CCP值较低时，会创建更多节点。节点越高，树的深度就越高。下面的代码(ScikitLearn)说明了如何调整alpha以获得具有更高准确率分数的模型。path=model_gini.cost_complexity_pruning_path(X_train,y_train)ccp_alphas,杂质=path.ccp_alphas,path.impuritiesfig,ax=plt.subplots(figsize=(16,8))ax.plot(ccp_alphas[:-1],杂质[:-1],marker='o',drawstyle="steps-post")从结果可以看出，如果alpha设置为0.04，测试集的准确率是最好的，我们将重新训练模型.clf_ccp=DecisionTreeClassifier(random_state=1,ccp_alpha=0.04)clf_ccp.fit(X_train,y_train)对决策树进行剪枝后，可以看到模型的深度很浅，可以达到很好的效果。该模型在训练集上有140个错误样本，但在测试集上只有54个错误样本。训练数据集的混淆矩阵测试数据集的混淆矩阵
