【机器学习】决策树算法

简介: 【机器学习】决策树算法

人工智能领域在当今可谓炙手可热,在人工智能与机器学习领域,决策树是一种简单直观却又功能强大的分类与回归方法。它的思想是通过构建一棵树状模型来进行决策或数据分类,其结构主要是以二叉树的形式为主。决策树是一种常用的机器学习算法,用于分类和回归任务。它通过学习简单的决策规则推断出目标值。

算法引入

小明大学毕业了,去了一家银行当行长,上班第一天就有了10人申请了贷款,刚刚入行的小明仔细地整理了客户信息。包括是否有工作,是否有房子,是否信誉良好,经过了深思熟虑,小明对这10份申请给出了批复。

小明想能不能让AI根据自己所做出的规律进行自动批复,这样小明就大大减少了工作量,又可以上班摸鱼了。申请人的信息如下:

image.png

根据上面信息我们能不能推出某一个规律,使规律都满足上面的结果,如果我们按照是否有工作分类,有工作的批准,没工作的不批准,显然不行,在第5个申请人没有工作也批准了。那么我们按照有无房子分类?在第7、10个申请人没有房子也通过了申请,那按照信誉?第9个申请人信誉很好也被拒绝了。那么我们如何进行批准,这就是要我们的决策树出马了。

基尼系数

那么在建树的时候,谁当那个头结点呢,这就要引出了我们的基尼系数的概念。


根据上面的公式我们可以计算出Gini=1-(5/10)^2-(5/10)^2=0.5。


Gini(工作,是)=1-(4/4)^2-0=0,Gini(工作,否)=1-(2/6)^2-(4/6)^2=0.44。


根据加权方式求和:Gini(工作)=4/10*(Gini(工作,是))+6/10*(Gini(工作,否))=0.27。


Gini(房子,是)=1-(4/5)^2-(1/5)^2=0.32,Gini(房子,否)=1-(2/5)^2-(3/5)^2=0.48。


根据加权方式求和:Gini(房子)=5/10*(Gini(房子,是))+5/10*(Gini(房子,否))=0.4。


Gini(信誉,一般)=1-(2/4)^2-(2/4)^2=0.5,Gini(信誉,良好)=1-(1/2)^2-(1/2)^2=0.5,Gini(信誉,很好)=1-(3/4)^2-(1/4)^2=0.375。


根据加权方式求和:Gini(信誉)=4/10*(Gini(信誉,一般))+2/10*(Gini(信誉,良好))+4/10*(Gini(信誉,很好))=0.45。


我们比较这三个数Gini(工作)=0.27、Gini(房子)=0.4、Gini(信誉)=0.45。我们发现这个三个数字中Gini(工作)=0.27最小,所以我们按照它来建立决策树。

60e8b66d2854491a9f47e38e56e3469a.png

此时头结点建立完成,然后我们在没有工作的里面,有2个客户是被批准的,4个客户被拒绝了,那么我们在此基础上继续进行分类,继续求解Gini(房子),Gini(信誉)。Gini(房子,是)=1-(2/2)^2- 0=0,Gini(房子,否)=1- 0 -(4/4)^2=0。根据加权方式求和:Gini(房子)=2/6*(Gini(房子,是))+4/6*(Gini(房子,否))=0。此时Gini(信誉)就不用算了,Gini(房子)已经达到最小0了,下一个结点就放是否有房子,那么此时最终的决策树就出来了。


先根据是否有工作进行判断,如果有,那么直接进行批准,没有的话,再进行判断是否有房子,有房子的话直接批准,没有房子的话直接拒绝,当然,我们这个例子没有涉及到信誉一项,如果在没有房子的人里面还有被批准的,那么需要再加一个内部节点信誉,再根据信誉的三个分类:一般、良好、很好,进行批复。这些判断是建立在前一项的基础之上的,只有进行了前一项的判断才能进行下一项的判断,进而给出批复。

8f1e1f9b8b104c6aa3d84637fd1a8e2a.png


决策树算法概述

决策树通过树状图的形式模拟决策过程,在每一个结点都会有分支(除了叶子结点),每个内部节点都代表一个属性上的判断,如果为是则走一个分支,如果为否则走另外一个分支。每个分支代表判断的结果,每个叶节点代表一种决策结果。

决策树的关键概念

- 节点(Node):决策树中的一个决策点。

- 根节点(Root):决策树的起始点。

- 分支(Branch):从一个节点到另一个节点的连接。

- 叶节点(Leaf):没有子节点的节点,是一棵树最下面的结点。代表最终决策。

- 路径(Path):从根节点到叶节点的一系列决策。

决策树的构建

构建决策树通常涉及以下步骤:

1. 选择最佳属性:使用某种度量(如信息增益、基尼不纯度)选择最佳属性进行分割。

2. 创建节点:为所选属性的每个可能值创建一个分支。

3. 分割数据:根据属性值将数据分割成不同的子集。

4. 递归构建:对每个子集递归地重复上述步骤,直到满足停止条件(如所有数据属于同一类别,或已达到树的最大深度)。

代码实现

1. 定义决策树节点

 class TreeNode:
    def __init__(self, feature_index=None, threshold=None, left=None, right=None, *, value=None):
        self.feature_index = feature_index  # 特征索引
        self.threshold = threshold          # 阈值
        self.left = left                     # 左子树
        self.right = right                   # 右子树
        self.value = value                   # 节点值(叶节点时的分类结果)

2. 计算信息增益

def information_gain(X, y, split_feature_index, threshold):
    # 计算信息熵
    def calculate_entropy(y):
        # 实现信息熵的计算
        pass
 
    # 划分数据集
    left_indices = [i for i in range(len(X)) if X[i][split_feature_index] < threshold]
    right_indices = [i for i in range(len(X)) if X[i][split_feature_index] >= threshold]
 
    # 计算信息增益
    total_entropy = calculate_entropy(y)
    left_entropy = calculate_entropy([y[i] for i in left_indices])
    right_entropy = calculate_entropy([y[i] for i in right_indices])
    weight_left = len(left_indices) / len(X)
    weight_right = len(right_indices) / len(X)
 
    information_gain = total_entropy - (weight_left * left_entropy + weight_right * right_entropy)
    return information_gain

3. 选择最佳分割特征

def best_split(X, y):
    best_feature = None
    best_threshold = None
    max_information_gain = -1
 
    for feature_index in range(X.shape[1]):
        for i in range(X.shape[0]):
            threshold = X[i][feature_index]
            gain = information_gain(X, y, feature_index, threshold)
            if gain > max_information_gain:
                best_feature = feature_index
                best_threshold = threshold
                max_information_gain = gain
 
    return best_feature, best_threshold


4. 构建决策树

def build_tree(X, y, max_depth=None, current_depth=0):
    if len(np.unique(y)) == 1 or current_depth == max_depth:
        return TreeNode(value=np.argmax(np.unique(y)))
 
    best_feature, best_threshold = best_split(X, y)
    if best_feature is None:
        return TreeNode(value=np.argmax(np.unique(y)))
 
    left_indices = [i for i in range(len(X)) if X[i][best_feature] < best_threshold]
    right_indices = [i for i in range(len(X)) if X[i][best_feature] >= best_threshold]
 
    left_X = [X[i] for i in left_indices]
    left_y = [y[i] for i in left_indices]
    right_X = [X[i] for i in right_indices]
    right_y = [y[i] for i in right_indices]
 
    left_child = build_tree(left_X, left_y, max_depth, current_depth + 1)
    right_child = build_tree(right_X, right_y, max_depth, current_depth + 1)
 
    return TreeNode(feature_index=best_feature, threshold=best_threshold, left=left_child, right=right_child)

5. 决策树预测

def predict(tree, x):
    if tree.value is not None:
        return tree.value
    if x[tree.feature_index] < tree.threshold:
        return predict(tree.left, x)
    else:
        return predict(tree.right, x)

决策树的评估指标:

  • 准确率:正确分类的样本数占总样本数的比例。
  • 精确度:预测为正的样本中实际为正的比例。
  • 召回率:实际为正的样本中预测为正的比例。
  • F1分数:精确度和召回率的调和平均。

决策树的优缺点

优点:

- 易于理解和解释。

- 可以处理数值和类别数据。

- 不需要数据标准化。

- 可以可视化。

缺点:

- 容易过拟合。

- 对于某些数据集,构建的树可能非常大。

- 对于缺失数据敏感。

决策树的优化

- 剪枝:通过减少树的大小来减少过拟合。

- 集成方法:如随机森林和梯度提升树,可以提高模型的泛化能力。


下一篇文章更新决策树算法ID3、C4.5、CART的介绍以及实现。执笔至此,感触彼多,全文将至,落笔为终,感谢各位的支持。


相关文章
|
23天前
|
机器学习/深度学习 人工智能 自然语言处理
【MM2024】阿里云 PAI 团队图像编辑算法论文入选 MM2024
阿里云人工智能平台 PAI 团队发表的图像编辑算法论文在 MM2024 上正式亮相发表。ACM MM(ACM国际多媒体会议)是国际多媒体领域的顶级会议,旨在为研究人员、工程师和行业专家提供一个交流平台,以展示在多媒体领域的最新研究成果、技术进展和应用案例。其主题涵盖了图像处理、视频分析、音频处理、社交媒体和多媒体系统等广泛领域。此次入选标志着阿里云人工智能平台 PAI 在图像编辑算法方面的研究获得了学术界的充分认可。
【MM2024】阿里云 PAI 团队图像编辑算法论文入选 MM2024
|
11天前
|
机器学习/深度学习 算法 Java
机器学习、基础算法、python常见面试题必知必答系列大全:(面试问题持续更新)
机器学习、基础算法、python常见面试题必知必答系列大全:(面试问题持续更新)
|
19天前
|
机器学习/深度学习 人工智能 算法
【玉米病害识别】Python+卷积神经网络算法+人工智能+深度学习+计算机课设项目+TensorFlow+模型训练
玉米病害识别系统,本系统使用Python作为主要开发语言,通过收集了8种常见的玉米叶部病害图片数据集('矮花叶病', '健康', '灰斑病一般', '灰斑病严重', '锈病一般', '锈病严重', '叶斑病一般', '叶斑病严重'),然后基于TensorFlow搭建卷积神经网络算法模型,通过对数据集进行多轮迭代训练,最后得到一个识别精度较高的模型文件。再使用Django搭建Web网页操作平台,实现用户上传一张玉米病害图片识别其名称。
43 0
【玉米病害识别】Python+卷积神经网络算法+人工智能+深度学习+计算机课设项目+TensorFlow+模型训练
|
27天前
|
机器学习/深度学习 算法 决策智能
【机器学习】揭秘深度学习优化算法:加速训练与提升性能
【机器学习】揭秘深度学习优化算法:加速训练与提升性能
|
23天前
|
机器学习/深度学习 算法 Python
探索机器学习中的决策树算法:从理论到实践
【10月更文挑战第5天】本文旨在通过浅显易懂的语言,带领读者了解并实现一个基础的决策树模型。我们将从决策树的基本概念出发,逐步深入其构建过程,包括特征选择、树的生成与剪枝等关键技术点,并以一个简单的例子演示如何用Python代码实现一个决策树分类器。文章不仅注重理论阐述,更侧重于实际操作,以期帮助初学者快速入门并在真实数据上应用这一算法。
|
28天前
|
机器学习/深度学习 算法 大数据
机器学习入门:梯度下降算法(下)
机器学习入门:梯度下降算法(下)
|
20天前
|
机器学习/深度学习 算法 数据处理
EM算法对人脸数据降维(机器学习作业06)
本文介绍了使用EM算法对人脸数据进行降维的机器学习作业。首先通过加载ORL人脸数据库,然后分别应用SVD_PCA、MLE_PCA及EM_PCA三种方法实现数据降维,并输出降维后的数据形状。此作业展示了不同PCA变种在人脸数据处理中的应用效果。
25 0
|
2月前
|
机器学习/深度学习 算法 TensorFlow
交通标志识别系统Python+卷积神经网络算法+深度学习人工智能+TensorFlow模型训练+计算机课设项目+Django网页界面
交通标志识别系统。本系统使用Python作为主要编程语言,在交通标志图像识别功能实现中,基于TensorFlow搭建卷积神经网络算法模型,通过对收集到的58种常见的交通标志图像作为数据集,进行迭代训练最后得到一个识别精度较高的模型文件,然后保存为本地的h5格式文件。再使用Django开发Web网页端操作界面,实现用户上传一张交通标志图片,识别其名称。
86 6
交通标志识别系统Python+卷积神经网络算法+深度学习人工智能+TensorFlow模型训练+计算机课设项目+Django网页界面
|
28天前
|
机器学习/深度学习 算法
机器学习入门(三):K近邻算法原理 | KNN算法原理
机器学习入门(三):K近邻算法原理 | KNN算法原理
|
28天前
|
机器学习/深度学习 算法 API
机器学习入门(五):KNN概述 | K 近邻算法 API,K值选择问题
机器学习入门(五):KNN概述 | K 近邻算法 API,K值选择问题