分类算法系列⑤：决策树

作者介绍双非本科大三网络工程专业在读阿里云专家博主专注于Java领域学习擅长web应用开发、数据结构和算法初步涉猎Python人工智能开发。

主页@逐梦苍穹

⭐分类算法系列①初识概念

⭐分类算法系列②KNN(K-近邻)算法

⭐分类算法系列③模型选择与调优 (Facebook签到位置预测)

⭐分类算法系列④朴素贝叶斯算法

您的三连支持是我创作的最大动力

1、认识决策树

决策树思想的来源非常朴素程序设计中的条件分支结构就是if-then结构最早的决策树就是利用这类结构分割数据的一种分类学习方法。

怎么理解这句话通过一个对话例子

想一想这个女生为什么把年龄放在最上面判断这就是涉及到决策树的效率

2、决策树的概念

决策树是一种广泛应用于机器学习和数据挖掘领域的监督学习算法用于分类和回归任务。它是一种基于树状图结构来做出决策的模型非常直观且易于解释。在决策树中每个内部节点表示一个属性或特征每个分支代表一个属性测试每个叶子节点表示一个类别标签或回归值。以下是决策树的关键概念和特点

树状结构决策树采用树状结构其中根节点表示整个数据集内部节点表示属性或特征叶子节点表示类别或回归值。每个节点可以有多个子节点但通常不会太深以避免过度拟合。
分裂节点决策树的构建过程涉及选择一个属性或特征将数据集分成不同的子集。这个过程持续递归地进行直到满足停止条件。
属性选择在每个内部节点决策树算法会选择一个最佳属性或特征来进行数据分割。常见的属性选择方法包括信息增益、基尼不纯度和均方误差。
剪枝决策树容易过度拟合训练数据为了避免这种情况可以采用剪枝策略。剪枝是删除某些子树或叶子节点以简化模型并提高泛化能力。
分类与回归决策树可用于分类问题和回归问题。在分类问题中叶子节点表示类别标签。在回归问题中叶子节点表示一个数值。
特征重要性决策树可以提供特征重要性的信息即哪些特征对于分类或回归任务更为关键。这可以帮助特征选择和理解数据。
解释性决策树模型具有很高的解释性因为它们的决策过程可以直观地表示为一系列的规则。这使得决策树在需要解释机器学习模型决策的情况下非常有用。
容易过拟合决策树在训练数据上容易过拟合因此常常需要剪枝等正则化方法来降低模型复杂度。

决策树的一些常见变体包括随机森林通过多个决策树进行集成、梯度提升树通过迭代建立多个决策树以及CART分类与回归树等。

决策树在许多领域都有广泛的应用包括医疗诊断、金融风险评估、自然语言处理、图像处理等。它们的优点包括易于理解、易于可视化、高效计算和适用于各种数据类型。但需要注意的是决策树可能对数据中的噪声敏感并且可能需要进一步的处理来提高性能。

3、决策树分类原理

基本原理

决策树分类原理是一种基于树状结构的监督学习算法用于解决分类问题。其基本原理涉及将数据分成不同的类别以构建树状结构使决策树能够对新数据进行分类。下面是决策树分类的基本原理

初始节点决策树的根节点包含整个训练数据集。初始时所有训练样本都属于同一个类别或标签。
属性选择选择一个最佳属性或特征来进行数据分割。这个选择通常基于某个属性的判别能力目标是将数据分成尽可能纯净的子集。不纯度的度量方式有多种包括信息增益、基尼不纯度和均方误差等。选择属性的过程可以看作是在节点上进行一个属性测试例如如果某个特征的值大于某个阈值则分到左子树否则分到右子树。
分裂节点根据选择的属性将数据集分成多个子集每个子集对应一个分支。这些分支成为决策树的内部节点。
递归构建重复上述过程对每个内部节点递归地选择最佳属性并分割数据直到满足停止条件。停止条件可以是树达到最大深度、节点包含的样本数小于某个阈值、或者数据集在某个节点上已经完全纯净所有样本属于同一类别。
叶子节点当决策树构建完成后所有终止分裂的节点称为叶子节点。叶子节点包含一个类别或标签表示在该节点上的样本属于该类别。
分类对于新的数据点从根节点开始根据每个节点上的属性测试沿着适当的分支移动直到达到叶子节点。最终的叶子节点的类别即为决策树对新数据点的分类结果。

总的来说决策树分类的原理是通过递归地选择属性并分裂数据构建一个树状结构使得每个叶子节点代表一个类别。这样当新的数据点到达树的叶子节点时可以根据叶子节点的类别标签来进行分类预测。决策树分类具有直观性、易解释性和适用性广泛的特点但需要小心处理过拟合问题通常需要剪枝等正则化技术。

数学公式

决策树分类的数学原理涉及到属性选择和分割数据的数学方法以及如何确定叶子节点的类别。以下是决策树分类的主要数学原理

①信息熵Entropy信息熵是一个用于度量数据不纯度或混乱程度的概念。

对于一个二分类问题信息熵的计算公式如下 $eq?H%28X%29%20%3D%20-%5Csum_%7Bi%3D1%7D%5E%7Bc%7D%20p_i%20%5Clog_2%28p_i%29%3D-%5Csum_%7Bk%3D1%7D%5E%7BK%7D%20%5Cfrac%7B%7CC_k%7C%7D%7B%7CX%7C%7D%20%5Clog_2%28%5Cfrac%7B%7CC_k%7C%7D%7B%7CX%7C%7D%29$

其中H(X) 表示数据集 X 的信息熵c 表示类别的数量pi 表示第 i 个类别在数据集中的占比。信息熵越高表示数据集越不纯。

②条件熵 $eq?H%28D%7CA%29%3D%5Csum_%7Bi%3D1%7D%5E%7Bn%7D%20%5Cfrac%7B%7CD_i%7C%7D%7B%7CD%7C%7DH%28D_i%29%3D-%5Csum_%7Bi%3D1%7D%5E%7Bn%7D%5Cfrac%7B%7CD_i%7C%7D%7B%7CD%7C%7D%5Csum_%7Bk%3D1%7D%5E%7BK%7D%20%5Cfrac%7B%7CD_%7Bik%7D%7C%7D%7B%7CD_i%7C%7D%20%5Clog_2%28%5Cfrac%7B%7CD_%7Bik%7D%7C%7D%7B%7CD_i%7C%7D%29$

$eq?C_k$ 表示属于某个类别的样本数

③信息增益Information Gain信息增益是衡量在选择某个属性后信息熵减少的程度。

在决策树中选择信息增益最大的属性来进行分割。

信息增益的计算公式如下 $eq?%5Ctext%7BInformation%20Gain%7D%28X%2C%20A%29%20%3D%20H%28X%29%20-%20%5Csum_%7Bv%20%5Cin%20%5Ctext%7BValues%7D%28A%29%7D%20%5Cfrac%7B%7CX_v%7C%7D%7B%7CX%7C%7D%20%5Ccdot%20H%28X_v%29$

其中X 表示当前节点的数据集A 表示属性Values(A) 表示属性 A 可能的取值Xv 表示属性A 取值为v时的数据子集。

④基尼不纯度Gini Impurity基尼不纯度是另一种用于度量数据不纯度的指标。

对于一个二分类问题基尼不纯度的计算公式如下 $eq?Gini%28X%29%20%3D%201%20-%20%5Csum_%7Bi%3D1%7D%5E%7Bc%7D%20p_i%5E2$

其中Gini(X) 表示数据集 X 的基尼不纯度c 表示类别的数量pi 表示第 i 个类别在数据集中的占比。

基尼不纯度越低表示数据集越纯。

⑤基尼增益Gini Gain基尼增益是衡量在选择某个属性后基尼不纯度减少的程度。

公式 $eq?%5Ctext%7BGini%20Gain%7D%28X%2C%20A%29%20%3D%20Gini%28X%29%20-%20%5Csum_%7Bv%20%5Cin%20%5Ctext%7BValues%7D%28A%29%7D%20%5Cfrac%7B%7CX_v%7C%7D%7B%7CX%7C%7D%20%5Ccdot%20Gini%28X_v%29$

在决策树中选择基尼增益最大的属性来进行分割。基尼增益的计算公式与信息增益类似但使用基尼不纯度来度量。

⑥决策树构建过程决策树的构建过程是通过递归选择最佳属性来分割数据集直到满足停止条件。通常停止条件包括树达到最大深度、节点包含的样本数小于某个阈值或者数据集在某个节点上已经完全纯净所有样本属于同一类别。

⑦剪枝Pruning决策树容易过拟合训练数据为了避免过拟合可以采用剪枝策略。剪枝是删除某些子树或叶子节点以简化模型并提高泛化能力。常见的剪枝方法包括预剪枝和后剪枝。

总的来说决策树分类的数学原理涉及使用信息熵、信息增益、基尼不纯度和基尼增益等指标来选择最佳属性进行数据分割并通过递归构建树状结构来实现分类。这些指标和方法帮助决策树在数据集中找到最佳的属性

4、信息熵的作用

信息熵在信息理论和机器学习中有着重要的作用主要体现在以下几个方面

度量信息不确定性 信息熵用来度量一个随机变量或数据集的信息不确定性。信息熵越高表示不确定性越大反之亦然。在机器学习中我们经常使用信息熵来衡量数据集的纯度或不纯度。例如在决策树中我们选择属性进行划分时通常希望子集的信息熵尽可能低从而提高分类的准确性。
特征选择 在特征工程中我们可以使用信息熵来衡量不同特征对目标变量的贡献。选择具有高信息熵的特征意味着这些特征包含更多关于目标变量的信息因此可能更有用于建立模型。
决策树构建 决策树算法中的属性选择依赖于信息熵。通过计算每个属性的信息增益或信息增益比决策树可以选择最优的属性来进行数据集的划分从而构建出具有良好泛化性能的决策树模型。
编码与压缩 在信息编码和数据压缩中信息熵有助于设计高效的编码方案。香农编码就是一种基于信息熵的数据压缩方法它能够实现最短的编码长度以便节省存储空间和传输带宽。
随机事件分析 在概率论和统计学中信息熵用于描述随机事件的不确定性或信息量。它是衡量信息的一种重要指标可用于研究随机事件的性质和分布。

总之信息熵是一个重要的概念它帮助我们理解和处理信息的不确定性对于数据分析、模型构建和信息处理等领域都具有广泛的应用价值。

5、决策树的划分依据之一信息增益

5.1、定义与公式

特征A对训练数据集D的信息增益g(D,A)定义为集合D的信息熵H(D)与特征A给定条件下D的信息条件熵H(D|A)之差。

即公式为 $eq?g%28D%2CA%29%3DH%28D%29-H%28D%7CA%29$

带入前面提到的公式则 $eq?g%28D%2CA%29$ 为

$eq?g%28D%2CA%29%3D-%5Csum_%7Bk%3D1%7D%5E%7BK%7D%20%5Cfrac%7B%7CC_k%7C%7D%7B%7CD%7C%7D%20%5Clog_2%28%5Cfrac%7B%7CC_k%7C%7D%7B%7CD%7C%7D%29-%28-%5Csum_%7Bi%3D1%7D%5E%7Bn%7D%20%5Cfrac%7B%7CD_i%7C%7D%7B%7CD%7C%7D%20%5Csum_%7Bk%3D1%7D%5E%7BK%7D%20%5Cfrac%7B%7CD_%7Bik%7D%7C%7D%7B%7CD_i%7C%7D%20%5Clog_2%28%20%5Cfrac%7B%7CD_%7Bik%7D%7C%7D%7B%7CD_i%7C%7D%29%29$

用通俗的话来说就是当知道了某一个特征之后对于某一事件的不确定性减少了即信息熵减少了则称为信息增益。

5.2、⭐手动计算案例

下面的案例是一个贷款案例给定多个特征判断是否贷款的可能性

数据情况如下

下面是具体的计算需要计算出决策树的根节点即“知道了哪一个特征之后对于是否贷款的问题减少了最多的不确定性”。

总的信息熵为"是/否" $eq?H%28D_%7Ball%7D%29%3D-%5Csum_%7Bk%3D1%7D%5E%7BK%7D%20%5Cfrac%7B%7CC_k%7C%7D%7B%7CD%7C%7D%20%5Clog_2%28%5Cfrac%7B%7CC_k%7C%7D%7B%7CD%7C%7D%29%3D-%28%5Cfrac%7B6%7D%7B15%7D%5Clog_2%5Cfrac%7B6%7D%7B15%7D+%5Cfrac%7B9%7D%7B15%7D%5Clog_2%5Cfrac%7B9%7D%7B15%7D%29$

下面是条件熵

根据"青年"的过程以此类推最终得出信息增益g(D,A)最高的是条件为"知道是否有房子"这一特征所以就把判断是否有房子作为决策树的根节点树以此延申。

5.3、log值逼近

对数的基本性质

如果想要具体的值可以用泰勒公式或麦克劳林展开式

泰勒公式 $eq?f%28x%29%20%3D%20f%28a%29%20+%20f%27%28a%29%28x%20-%20a%29%20+%20%5Cfrac%7Bf%27%27%28a%29%7D%7B2%21%7D%28x%20-%20a%29%5E2%20+%20%5Cfrac%7Bf%27%27%27%28a%29%7D%7B3%21%7D%28x%20-%20a%29%5E3%20+%20%5Cldots$

麦克劳林公式 $eq?f%28x%29%20%3D%20%5Csum_%7Bn%3D0%7D%5E%7B%5Cinfty%7D%20%5Cfrac%7Bf%5E%7B%28n%29%7D%28a%29%7D%7Bn%21%7D%28x%20-%20a%29%5En$

$eq?%5Clog_x%20y$ 的泰勒公式和麦克劳林公式如下

$eq?%5Clog_x%20y%20%3D%20%5Clog_a%20y%20+%20%5Cfrac%7B1%7D%7B%5Cln%20a%7D%5Cleft%28%5Cfrac%7By%27%7D%7By%7D%5Cright%29%28x%20-%20a%29%20+%20%5Cfrac%7B1%7D%7B2%21%5Cln%20a%7D%5Cleft%28%5Cfrac%7By%27%27%7D%7By%7D%5Cright%29%28x%20-%20a%29%5E2%20+%20%5Cfrac%7B1%7D%7B3%21%5Cln%20a%7D%5Cleft%28%5Cfrac%7By%27%27%27%7D%7By%7D%5Cright%29%28x%20-%20a%29%5E3%20+%20%5Cldots%20+%20O%5Cleft%28%28x%20-%20a%29%5En%5Cright%29$

$eq?%5Clog_x%20y%20%3D%20%5Cfrac%7B1%7D%7B%5Cln%201%7D%5Cleft%28%5Cfrac%7By%27%7D%7By%7D%5Cright%29x%20+%20%5Cfrac%7B1%7D%7B2%21%5Cln%201%7D%5Cleft%28%5Cfrac%7By%27%27%7D%7By%7D%5Cright%29x%5E2%20+%20%5Cfrac%7B1%7D%7B3%21%5Cln%201%7D%5Cleft%28%5Cfrac%7By%27%27%27%7D%7By%7D%5Cright%29x%5E3%20+%20%5Cldots%20+%20O%28x%5En%29$

6、决策树的三种算法实现

决策树是一种常用的机器学习算法用于分类和回归任务。以下是三种常见的决策树算法的实现方式

ID3Iterative Dichotomiser 3算法ID3算法是决策树的早期算法主要用于分类任务。它基于信息熵来选择每个节点的划分属性以最大程度地减少不确定性。以下是ID3算法的关键步骤
- 计算每个属性的信息增益。
- 选择信息增益最高的属性作为划分属性。
- 递归地构建树直到满足终止条件例如达到叶子节点或最大深度。
C4.5算法C4.5算法是ID3算法的改进版本它可以用于分类和回归任务。与ID3不同C4.5使用信息增益比来选择最佳的划分属性。以下是C4.5算法的关键步骤
- 计算每个属性的信息增益比。
- 选择信息增益比最高的属性作为划分属性。
- 处理缺失值。
- 递归地构建树直到满足终止条件。
CARTClassification and Regression Trees算法CART算法是一种多用途的决策树算法可以用于分类和回归任务。与ID3和C4.5不同CART使用基尼不纯度来选择最佳的划分属性。以下是CART算法的关键步骤
- 计算每个属性的基尼不纯度。
- 选择基尼不纯度最低的属性作为划分属性。
- 递归地构建树直到满足终止条件。

这些是三种常见的决策树算法的基本实现方式。每种算法都有其优点和局限性选择哪种算法通常取决于具体的问题和数据集。实际应用中您可以使用机器学习库如scikit-learn中提供的现成实现来构建决策树模型。在使用这些库时您可以轻松选择算法并进行参数调整以获得最佳性能。

7、API

class sklearn.tree.DecisionTreeClassifier(criterion='gini', max_depth=None,random_state=None)

决策树分类器

criterion默认是'gini'系数也可以选择信息增益的熵'entropy'

max_depth树的深度大小

random_state随机数种子

其中会有些超参数max_depth:树的深度大小

其它超参数会结合随机森林讲解

8、⭐两个代码案例

8.1、决策树分类鸢尾花数据集

流程

①获取数据集

②划分数据集

③决策树预估器

④模型评估对比真实值和预测值计算准确率

⑤可视化

代码

# -*- coding: utf-8 -*-
# @Author:︶ㄣ释然
# @Time: 2023/9/1 23:50
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier, export_graphviz

'''
class sklearn.tree.DecisionTreeClassifier(criterion=’gini’, max_depth=None,random_state=None)
    决策树分类器
    criterion:默认是’gini’系数也可以选择信息增益的熵’entropy’
    max_depth:树的深度大小
    random_state:随机数种子
    其中会有些超参数max_depth:树的深度大小
    其它超参数会结合随机森林讲解
'''
def decision_iris():
    """
    用决策树对鸢尾花进行分类
    :return:
    """
    # 1获取数据集
    iris = load_iris()

    # 2划分数据集
    x_train, x_test, y_train, y_test = train_test_split(iris.data, iris.target, random_state=22)

    # 3决策树预估器
    estimator = DecisionTreeClassifier(criterion="entropy")
    estimator.fit(x_train, y_train)

    # 4模型评估
    # 方法1直接比对真实值和预测值
    y_predict = estimator.predict(x_test)
    print("y_predict:\n", y_predict)
    print("直接比对真实值和预测值:\n", y_test == y_predict)

    # 方法2计算准确率
    score = estimator.score(x_test, y_test)
    print("准确率为\n", score)

    # 可视化决策树
    export_graphviz(estimator, out_file="iris_tree.dot", feature_names=iris.feature_names)
if __name__ == '__main__':
    decision_iris()

代码解释

从sklearn.datasets中导入load_iris函数用于加载鸢尾花数据集。
使用load_iris函数加载鸢尾花数据集并将数据集保存在变量iris中。
使用train_test_split函数将数据集划分为训练集和测试集并将特征数据存储在x_train和x_test中将目标数据标签存储在y_train和y_test中。random_state参数用于控制随机划分的种子以确保划分结果可重复。
创建一个决策树分类器DecisionTreeClassifier使用信息熵entropy作为划分标准criterion="entropy"。
使用训练集数据x_train和y_train来拟合决策树模型即训练模型。
使用训练好的模型进行预测将测试集数据x_test输入模型得到预测结果并将预测结果存储在y_predict中。
打印预测结果y_predict以及直接比对真实值和预测值的结果这里使用了布尔运算符==来比较真实标签和预测标签是否相等输出一个布尔数组表示每个样本的分类是否正确。
使用模型的score方法计算分类准确率将测试集数据x_test和真实标签y_test输入模型得到准确率的评估结果。
最后使用export_graphviz函数将训练好的决策树可视化并将可视化结果保存为名为"iris_tree.dot"的文件以便后续生成决策树的图形化表示。

结果

可以看到同样的鸢尾花数据集预测使用决策树比之前的KNN算法准确率提高了很多KNN算法是一种懒算法不适用于数据量稍大的情景。

决策树

8.2、泰坦尼克号乘客生存预测

泰坦尼克号数据

在泰坦尼克号和titanic2数据帧描述泰坦尼克号上的个别乘客的生存状态。这里使用的数据集是由各种研究人员开始的。其中包括许多研究人员创建的旅客名单由Michael A. Findlay编辑。我们提取的数据集中的特征是票的类别存活乘坐班年龄登陆home.dest房间票船和性别。

数据网址http://biostat.mc.vanderbilt.edu/wiki/pub/Main/DataSets/titanic.txt

如果无法访问可以访问阿里云的地址泰坦尼克生存预测数据集_数据集-阿里云天池

完整的数据集文件也可以在本地找到

分析

选择我们认为重要的几个特征 ['pclass', 'age', 'sex']

填充缺失值

特征中出现类别符号需要进行one-hot编码处理(DictVectorizer)

x.to_dict(orient="records") 需要将数组特征转换成字典数据

数据集划分

决策树分类预测

代码

# -*- coding: utf-8 -*-
# @Author:︶ㄣ释然
# @Time: 2023/9/1 23:50
import pandas as pd
from sklearn.feature_extraction import DictVectorizer
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier

'''
class sklearn.tree.DecisionTreeClassifier(criterion=’gini’, max_depth=None,random_state=None)
    决策树分类器
    criterion:默认是’gini’系数也可以选择信息增益的熵’entropy’
    max_depth:树的深度大小
    random_state:随机数种子
    其中会有些超参数max_depth:树的深度大小
    其它超参数会结合随机森林讲解
'''
def decisioncls():
    """
    决策树进行乘客生存预测
    """
    # 1、获取数据
    titan = pd.read_csv("./data/titanic/titanic.csv")

    # 2、数据的处理
    x = titan[['pclass', 'age', 'sex']]

    y = titan['survived']

    # print(x , y)
    # 缺失值需要处理将特征当中有类别的这些特征进行字典特征抽取
    x['age'].fillna(x['age'].mean(), inplace=True)

    # 对于x转换成字典数据x.to_dict(orient="records")
    # [{"pclass": "1st", "age": 29.00, "sex": "female"}, {}]

    dict = DictVectorizer(sparse=False)

    x = dict.fit_transform(x.to_dict(orient="records"))

    print(dict.get_feature_names_out())
    print(x)

    # 分割训练集合测试集
    x_train, x_test, y_train, y_test = train_test_split(x, y, test_size=0.3)

    # 进行决策树的建立和预测
    dc = DecisionTreeClassifier(max_depth=5)

    dc.fit(x_train, y_train)

    print("预测的准确率为", dc.score(x_test, y_test))

    # 可视化决策树
    # export_graphviz(dc, out_file="titanic_tree.dot", feature_names=dict.get_feature_names_out())


if __name__ == '__main__':
    decisioncls()
    # decision_iris()

代码解释

通过pd.read_csv函数从CSV文件中读取泰坦尼克号的数据并将数据存储在名为titan的Pandas DataFrame中。
从titan中选择特征列'pclass'船舱等级、'age'年龄、和'sex'性别作为模型的输入特征x并将'survived'生存情况列作为模型的目标输出y。
处理缺失值使用x['age'].fillna(x['age'].mean(), inplace=True)将'age'列中的缺失值用该列的均值填充。
对特征进行字典特征抽取使用DictVectorizer将特征数据转换为字典数据并进行独热编码以便决策树模型能够处理类别型特征。
打印特征列的名称和转换后的特征数据以查看转换的结果。
使用train_test_split函数将数据集划分为训练集x_train和y_train和测试集x_test和y_test。
创建决策树分类器对象dc设置最大深度为5。
使用训练数据x_train和y_train来训练决策树分类器。
使用测试数据x_test和y_test进行生存情况的预测并计算模型的准确率。
打印模型的预测准确率即模型在测试集上正确预测的比例。