算法研习：决策树算法基本原理分析

决策树(Decision Trees，DT)是一中监督机器学习算法，该算法根据数据的特征进行逐层划分直到划分完所有的特征，这一过程类似于树叶生长过程。决策树算法可用于解决分类和回归问题，在实际数据分析中有着广泛的应用。下面我们从以下5个方面来分析一下决策树算法：

1.什么是决策树

2.几种经典的决策树算法

3.决策树如何解决分类问题

4.决策树的优缺点

5.决策树的实际应用

什么是决策树

DT由节点，分支和叶子组成。每个节点代表一个属性（或特征），每个分支代表一个分裂规则（或决定），每个叶子代表一个结果。

DT对数据采用自上而下的方法，在给定数据集的情况下，他们会尝试对数据之间相似性进行分组和标记，并寻找最佳规则来对它们之间对应的不同的标签进行分类和回归分析，直到达到最大的准确率。

决策树主要有两种类型：分类树和回归树。

分类树的决策变量是离散的 。这种树是通过二进制递归分区的方法构建的。将数据特征划分为不同的分支 ，然后在每个分支上进一步迭代划分最终形成决策树。

回归树的目标变量是连续值，例如房屋的价格，或病人在医院的住院时间等等。

几种经典的决策树算法

比较经典的决策树算法有CART、ID3以及C4.5等等。

CART：CART根据目标变量是分类还是回归分别生成二进制 分类或回归树。它以原始形式处理数据，并且可以在同一DT的不同部分中多次使用相同的变量，这可以揭示变量集之间复杂的相互依赖性。

在分类树的情况下，CART算法使用Gini系数来度量分类任务创建决策点。Gini Impurity通过分裂创建的两个类中的类的混合程度，可以了解分割的精确度（节点“纯度”）。当所有观察属于同一标签时，基尼系数为0（最小值）。另一方面，当所有观察在不同标签之间平均分配时，我们面临最坏情况分割结果，此时基尼系数为1（最大值）。

在回归问题中，CART算法通过最小二乘偏差（LSD）来度量分裂结果，选择最小化所有可能选项的结果的分支进行分裂。LSD 表示观测值与预测值之间的距离平方之和。

ID3(Iterative Dichotomiser 3)：ID3主要用于分类问题，其利用信息增益作为划分标准进行树枝分裂，关于信息增益相关知识此处不做介绍。

C4.5：C4.5是ID3的升级版， C4.5可以用于分类和回归问题。此外，它可以通过忽略缺失数据来处理数据集中的缺失值。与ID3（使用信息增益作为划分标准）不同，C4.5使用增益比率进行拆分。 增益比率是通过在选择属性时考虑分支的数量和大小，减少了具有大量分支的DT的偏差。此外C4.5还包含一种窗口化的技术，该技术最初是为了克服早期计算机的内存限制而开发的。 窗口化意味着算法随机选择训练数据的子集(称为“窗口”)并用该子集构建DT。然后使用该DT对剩余的训练数据进行分类，并且如果它执行正确的分类，则DT结束。否则，将所有错误分类的数据点添加到窗口中，并且循环重复直到训练集中的每个实例被当前DT正确分类。该技术使DT具有更高的准确率。

决策树如何解决分类问题

决策树遵循分而治之思想，将数据拆分为子集，然后将其重复拆分成更小的子集 ，依此类推，直到算法确定子集内的数据足够均匀为止，在解决分类问题时，主要有以下几点：

• 使用决策算法，从根节点开始，根据数据特征上划分数据，从而产生最大的信息增益（IG)。
• 在迭代过程中，我们可以在每个子节点重复这个分裂过程， 这意味着每个叶节点处的样本都属于同一个类。
• 同时我们可以设置树的深度来防止过度拟合 。

决策树分类示例如下图所示：

决策树的优缺点

决策树的优点：

1. 模型复杂度低、易于构建
2. 在分类问题中效率较高
3. 决策树模型易于解释
4. 在许多标准数据集中与其他分类算法准确度不相上下

使用决策树进行分类的缺点：

1. 模型容易过度拟合
2. 决策边界收到数据特征的限制
3. 决策树模型通常偏向于具有大量特征的数据集

决策树的实际应用

• 生物医学工程（用于识别可植入设备中使用的特征的决策树）
• 财务分析（客户对产品或服务的满意度）
• 天文学（对星系进行分类）
• 系统控制
• 制造和生产(质量控制，半导体制造等)
• 药物诊断，心脏病诊断
• 物理学(粒子检测)

参考

1、https://towardsdatascience.com/decision-tree-classification-de64fc4d5aac

2、https://towardsdatascience.com/the-complete-guide-to-decision-trees-28a4e3c7be14