决策树

问题：

1. 决策树节点是如何确定？

2. 决策树构建流程是怎么样？

3. 决策树都有哪些优缺点？

4. 决策树缺点部分该如何进行优化？

1. 决策树节点的确定

    决策树的节点，是依据特征的“纯度”来确定。”纯度“是用 信息熵 / 信息增益 / 信息增益率  / 基尼系数 表示。

    信息熵公式：

                        H(X) = \sum_{i=1}^n - p(x_i)\log_2 p(x_i)  p是某一特征值的概率

    信息增益公式：(偏向值较多的特征属性)

                        IG(X) = H(Y) - H(Y|X)

                        其中 H(Y|X) 是条件熵，指的是 在X特征发生的条件下Y的信息熵

                        H(Y|X) = \sum_{j=1}^n p(x_j) H(Y | x_j)   n是特征X中去重后值的个数

    信息增益率公式：(偏向值较少的特征属性)

                        G_r (X)= \frac{IG(X)}{H(X)}

    基尼系数公式：(表示类别不一致的概率)

                        Gini(X) = 1 - \sum_{i=1}^n p(x_i)

    基尼增益公式：

                        IGini(X) = Gini(Y) - Gini(Y|X)

                        其中 Gini(Y | X) 是条件基尼系数

                         Gini(Y|X) = \sum_{i=1}^n p(x_i)Gini(Y|x_i)

    基尼增益率公式：

                            G_r = \frac{IGini(X)}{Gini(X)}

纯度越纯，信息熵，基尼系数越小，信息增益，信息增益率越大。

纯度越不纯，信息熵，基尼系数越大，信息增益，信息增益率越小。

2. 决策树构建流程

    a.  将所有特征作为一个节点  ——  计算 H(Y)

    b.  遍历当前特征，找到最优的分割点，将数据分为不同的子节点 —— 计算 H(x_i)和  IG(X)

    c. 选择 IG(X) 最大的特征作为子节点

    d. 循环执行 b 和 c ，直到最终的每个子节点都足够“纯” 或是 满足其他停止划分条件

    参考流程图

    参考代码实现

    图例说明

图例数据

a. 在不知道任何条件下，计算数据本身的信息熵

                H(Y) = - \frac{9}{14}log_2 \frac{9}{14}-\frac{5}{14}log_2\frac{5}{14}=0.940

b. 计算每个特征作为节点的信息熵

每个特征作为节点的划分

以天气为例，天气有三个特征属性值

当 outlook = sunny时，H(x) = -\frac{2}{5}log_2\frac{2}{5}-\frac{3}{5}log_2\frac{3}{5}

当 outlook = overcast时，H(x) = 0

当 outlook = rainy时， H(x) = 0.971

当天气作为节点时，H(Y|X) = \frac{5}{14}*0.971+\frac{4}{14}*0+\frac{5}{14}*0.971 = 0.693

信息增益  IG(X=天气) = H(Y) - H(Y|X) = 0.940-0.693 = 0.247

同理

IG(X=温度) =0.029

IG(X=湿度)=0.152

IG(X=风)=0.048

因此，选择 天气  作为节点，再依据这些步骤，递归选择其他节点

3. 决策树优缺点

    优点：决策树构建速度快，比较容易实现，并能够处理缺失值和不相关的特征

    缺点：决策树容易过拟合，而在类别数据不一致时，各判定节点的方法会有不同的属性偏向

4. 决策树缺点优化

    a. 对决策树进行剪枝，剪枝分为 前剪枝 与 后剪枝

    b. 采用 交叉验证 或  正则化 的方法

    c.  使用基于 Bagging思想的 随机森林算法等

5. 决策树常用算法

ID3、C4.5、CART之间的区别

ID3，内部使用信息熵以及信息增益进行构建，每次迭代选择信息增益最大的特征属性作为分割属性。它只支持离散特征属性，不支持连续特征属性。

    优点：实现比较简单，构建速度快

    缺点：依赖特征值数目较多的特征，不会考虑特征之间的关系，以及抗噪性比较差

C4.5，它使用信息增益率进行构建，在树构建中会进行剪枝操作优化，并能自动完成对连续属性离散化处理。

    优点：准确率高，易于理解

    缺点：对数据集多次顺序扫描和排序，效率较低

CART，它使用Gini增益率作为分割属性的标准，可以用于分类和回归，构造的是二叉树

三种算法总结：

    a. 均只适合在小规模数据集上使用，数据集需在内存中

    b. 属性取值较多时，考虑C4.5

    c. CART 是最常用的决策树算法，sklearn仅支持CART

    d. CART构建的一定是二叉树，ID3和C4.5构建的不一定是二叉树

    e. 对当前树评价标准不同，ID3使用信息增益、C4.5使用信息增益率、CART使用基尼系数

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。