机器学习--决策树

一、决策树简介

        决策树是一种常用的机器学习算法，用于分类和回归任务。它通过一系列的决策节点将数据集划分成不同的子集，直到达到某个终止条件。每个决策节点代表一个属性测试，每个分支代表测试结果的一个可能取值，而每个叶子节点代表一个类别标签或回归值。决策树的构建过程通常采用递归分割，基于某些指标（如信息增益、基尼不纯度等）来选择最佳的属性进行分割。决策树易于理解和解释，具有很好的可解释性，但可能会过拟合训练数据。为了减少过拟合，可以通过剪枝、设置树的最大深度、最小样本拆分等方式来调节决策树模型。下面通过一个简单的例子来阐述它的执行流程。                  

        决策树的特点：

优点：计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征数据。

缺点：可能会产生过度匹配的问题

适用数据类型：数值型和标称型

二、决策树的构造

        决策树的构造过程主要包括以下几个步骤：

1. 选择划分属性： 从训练数据集中选择一个属性作为当前节点的划分属性。选择划分属性的准则通常是根据某种指标（如信息增益、基尼不纯度）来衡量划分后数据集的纯度或不确定性减少程度。

2. 划分数据集： 根据选定的划分属性将数据集划分成不同的子集，每个子集对应划分属性的一个取值。这一步将构造出当前节点的子节点，并将数据集按照划分属性的不同取值划分到相应的子节点中。

3. 递归构建子树： 对每个子节点重复上述过程，选择划分属性、划分数据集，直到满足终止条件。终止条件可以是节点中样本的数量小于某个阈值、节点中样本的类别纯度达到某个阈值，或者达到了树的最大深度等。

4. 剪枝： 为了避免过拟合，可以对构建好的决策树进行剪枝。剪枝的目的是去掉一些不必要的节点和分支，简化模型，提高泛化能力。常用的剪枝方法有预剪枝（在构建过程中就进行剪枝）和后剪枝（在构建完成后对决策树进行剪枝）两种。

5. 生成决策规则： 最终得到的决策树可以转化为一系列的决策规则，这些规则可以被用来对新的数据进行分类或回归预测。

        在构造决策树时，需要选择合适的划分属性、终止条件和剪枝策略，以达到构建出泛化能力强的模型的目的。同时，决策树的构造过程可以通过递归算法实现，也可以采用迭代的方式进行。

三、划分选择

        1、熵与条件熵

                熵（Entropy)是表示随机变量不确定性的度量。说简单点就是物体内部的混乱程度。

                熵的定义如下：

                在决策树中，熵越高表示数据集的不确定性越大，即数据集中包含的不同类别的样本数量相对均衡，难以进行有效的划分；而熵越低表示数据集的纯度越高，即数据集中的样本大部分属于同一类别，易于进行划分。

                条件熵是信息论中的一个概念，用于衡量在给定某个特征条件下的信息不确定性。在决策树算法中，条件熵通常用于衡量在某个特征的取值已知的情况下，对数据集进行分类所需要的信息量。

                具体来说，假设我们有一个数据集，其中包含多个类别的样本，而我们想要根据某个特征来对这些样本进行分类。条件熵就是在已知该特征的取值情况下，对每个取值所对应的子集进行分类所需要的信息量的期望值。

                条件熵的计算公式如下：

                其中，(H(Y|X))表示在特征(X)已知的条件下，对目标变量(Y)的条件熵，(P(x,y))表示特征(X)取值为(x)且目标变量(Y)取值为(y)的样本的概率，(P(y|x))表示在特征(X)取值为(x)的条件下，目标变量(Y)取值为(y)的样本的概率。

                通过计算条件熵，我们可以评估在特征已知的情况下，对数据集进行分类所需要的平均信息量。在决策树算法中，通常会选择能够使得条件熵最小化的特征作为划分标准，因为这样可以使得分类结果更加纯净。

        2、ID3算法（信息增益）

                信息增益