（c#实现）决策树算法原理和案例

🕗 发布于 2024-07-12 07:23 决策树 c# 人工智能 算法程序员创富

一、引言

决策树（Decision Tree）是一种常用的监督学习算法，广泛应用于分类和回归任务。它的直观性和可解释性使其成为机器学习和数据挖掘领域的重要工具。本文将详细介绍决策树的原理，并通过一个实际案例展示如何使用C#实现决策树算法。

二、决策树的基本原理

1. 决策树的结构

决策树由节点（Node）和边（Edge）组成，其中节点分为三类：

根节点（Root Node）：树的起点，包含整个数据集。
内部节点（Internal Node）：决策点，根据特定特征进行分裂。
叶节点（Leaf Node）：树的终点，表示分类结果或回归值。

2. 决策树的构建

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

选择最佳分裂特征：根据某种分裂准则（如信息增益、基尼指数等）选择最佳特征进行分裂。
分裂节点：根据选定的特征将数据集分成若干子集。
递归构建子树：对每个子集重复上述过程，直至满足停止条件（如节点纯度足够高、树的深度达到预设值等）。

3. 分裂准则

常用的分裂准则包括：

信息增益（Information Gain）：衡量特征对分类结果的不确定性的减少程度，常用于ID3算法。
信息增益率（Information Gain Ratio）：修正了信息增益偏向于选择多值特征的问题，常用于C4.5算法。
基尼指数（Gini Index）：衡量数据集的不纯度，常用于CART算法。

三、决策树的实现案例

1. 案例介绍

我们将使用C#实现一个简单的决策树分类器，来解决“玩游戏”数据集的分类问题。数据集包含多个特征，如天气、温度、湿度、风速等，目标是预测在给定条件下是否适合玩游戏。

2. 数据集

示例数据集如下：

在代码中我们可以这么实现：

using System;
using System.Collections.Generic;

class DecisionTree
{
    public string Attribute { get; set; }
    public Dictionary<string, DecisionTree> Children { get; set; } = new Dictionary<string, DecisionTree>();
    public string Label { get; set; }

    // 计算信息增益
    private static double CalculateEntropy(List<Dictionary<string, string>> data, string attribute)
    {
        Dictionary<string, int> labelCounts = new Dictionary<string, int>();
        foreach (var row in data)
        {
            if (!labelCounts.ContainsKey(row[attribute]))
                labelCounts[row[attribute]] = 0;
            labelCounts[row[attribute]]++;
        }

        double entropy = 0.0;
        foreach (var count in labelCounts.Values)
        {
            double probability = (double)count / data.Count;
            entropy -= probability * Math.Log2(probability);
        }

        return entropy;
    }

    // 选择最佳分裂特征
    private static string ChooseBestAttribute(List<Dictionary<string, string>> data, List<string> attributes)
    {
        double baseEntropy = CalculateEntropy(data, "适合玩游戏");
        double bestInfoGain = 0.0;
        string bestAttribute = null;

        foreach (var attribute in attributes)
        {
            double attributeEntropy = 0.0;
            Dictionary<string, List<Dictionary<string, string>>> attributeValues = new Dictionary<string, List<Dictionary<string, string>>>();

            foreach (var row in data)
            {
                if (!attributeValues.ContainsKey(row[attribute]))
                    attributeValues[row[attribute]] = new List<Dictionary<string, string>>();
                attributeValues[row[attribute]].Add(row);
            }

            foreach (var subset in attributeValues.Values)
            {
                double subsetProbability = (double)subset.Count / data.Count;
                attributeEntropy += subsetProbability * CalculateEntropy(subset, "适合玩游戏");
            }

            double infoGain = baseEntropy - attributeEntropy;
            if (infoGain > bestInfoGain)
            {
                bestInfoGain = infoGain;
                bestAttribute = attribute;
            }
        }

        return bestAttribute;
    }

    // 构建决策树
    public static DecisionTree BuildTree(List<Dictionary<string, string>> data, List<string> attributes)
    {
        DecisionTree tree = new DecisionTree();

        Dictionary<string, int> labelCounts = new Dictionary<string, int>();
        foreach (var row in data)
        {
            if (!labelCounts.ContainsKey(row["适合玩游戏"]))
                labelCounts[row["适合玩游戏"]] = 0;
            labelCounts[row["适合玩游戏"]]++;
        }

        if (labelCounts.Count == 1)
        {
            tree.Label = labelCounts.Keys.GetEnumerator().Current;
            return tree;
        }

        if (attributes.Count == 0)
        {
            tree.Label = GetMajorityLabel(labelCounts);
            return tree;
        }

        string bestAttribute = ChooseBestAttribute(data, attributes);
        tree.Attribute = bestAttribute;

        Dictionary<string, List<Dictionary<string, string>>> attributeValues = new Dictionary<string, List<Dictionary<string, string>>>();
        foreach (var row in data)
        {
            if (!attributeValues.ContainsKey(row[bestAttribute]))
                attributeValues[row[bestAttribute]] = new List<Dictionary<string, string>>();
            attributeValues[row[bestAttribute]].Add(row);
        }

        List<string> remainingAttributes = new List<string>(attributes);
        remainingAttributes.Remove(bestAttribute);

        foreach (var attributeValue in attributeValues.Keys)
        {
            tree.Children[attributeValue] = BuildTree(attributeValues[attributeValue], remainingAttributes);
        }

        return tree;
    }

    // 获取多数标签
    private static string GetMajorityLabel(Dictionary<string, int> labelCounts)
    {
        string majorityLabel = null;
        int maxCount = 0;

        foreach (var label in labelCounts.Keys)
        {
            if (labelCounts[label] > maxCount)
            {
                maxCount = labelCounts[label];
                majorityLabel = label;
            }
        }

        return majorityLabel;
    }

    // 打印决策树
    public void PrintTree(string indent = "")
    {
        if (Label != null)
        {
            Console.WriteLine(indent + "Label: " + Label);
        }
        else
        {
            Console.WriteLine(indent + "Attribute: " + Attribute);
            foreach (var child in Children.Keys)
            {
                Console.WriteLine(indent + "  " + child + ":");
                Children[child].PrintTree(indent + "    ");
            }
        }
    }
}

class Program
{
    static void Main()
    {
        // 示例数据集
        List<Dictionary<string, string>> data = new List<Dictionary<string, string>>
        {
            new Dictionary<string, string> { { "天气", "晴朗" }, { "温度", "高" }, { "湿度", "高" }, { "风速", "弱" }, { "适合玩游戏", "否" } },
            new Dictionary<string, string> { { "天气", "晴朗" }, { "温度", "高" }, { "湿度", "高" }, { "风速", "强" }, { "适合玩游戏", "否" } },
            new Dictionary<string, string> { { "天气", "阴天" }, { "温度", "高" }, { "湿度", "高" }, { "风速", "弱" }, { "适合玩游戏", "是" } },
            new Dictionary<string, string> { { "天气", "雨天" }, { "温度", "适中" }, { "湿度", "高" }, { "风速", "弱" }, { "适合玩游戏", "是" } },
            new Dictionary<string, string> { { "天气", "雨天" }, { "温度", "低" }, { "湿度", "正常" }, { "风速", "弱" }, { "适合玩游戏", "是" } },
            new Dictionary<string, string> { { "天气", "雨天" }, { "温度", "低" }, { "湿度", "正常" }, { "风速", "强" }, { "适合玩游戏", "否" } },
            new Dictionary<string, string> { { "天气", "阴天" }, { "温度", "低" }, { "湿度", "正常" }, { "风速", "强" }, { "适合玩游戏", "是" } },
            new Dictionary<string, string> { { "天气", "晴朗" }, { "温度", "适中" }, { "湿度", "高" }, { "风速", "弱" }, { "适合玩游戏", "否" } },
            new Dictionary<string, string> { { "天气", "晴朗" }, { "温度", "低" }, { "湿度", "正常" }, { "风速", "弱" }, { "适合玩游戏", "是" } },
            new Dictionary<string, string> { { "天气", "雨天" }, { "温度", "适中" }, { "湿度", "正常" }, { "风速", "弱" }, { "适合玩游戏", "是" } },
            new Dictionary<string, string> { { "天气", "晴朗" }, { "温度", "适中" }, { "湿度", "正常" }, { "风速", "强" }, { "适合玩游戏", "是" } },
            new Dictionary<string, string> { { "天气", "阴天" }, { "温度", "适中" }, { "湿度", "高" }, { "风速", "强" }, { "适合玩游戏", "是" } },
            new Dictionary<string, string> { { "天气", "阴天" }, { "温度", "高" }, { "湿度", "正常" }, { "风速", "弱" }, { "适合玩游戏", "是" } },
            new Dictionary<string, string> { { "天气", "雨天" }, { "温度", "适中" }, { "湿度", "高" }, { "风速", "强" }, { "适合玩游戏", "否" } },
        };

        List<string> attributes = new List<string> { "天气", "温度", "湿度", "风速" };

        // 构建决策树
        DecisionTree tree = DecisionTree.BuildTree(data, attributes);

        // 打印决策树
        tree.PrintTree();
    }
}

决策树算法的优势在于其直观性和易解释性，但也存在过拟合等问题，在实际应用中需要结合剪枝等技术进行优化。

原文地址：https://blog.csdn.net/weixin_72139050/article/details/140347268

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：网络安全第一次作业
下一篇：python-长方体边长和（赛氪OJ）

leetcode289:生命游戏
根据，简称为，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。给定一个包含m × n个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态：1即为（live），或0即为
阅读更多2024-10-20
MongoDB数据恢复
注意：两个MongoDB的版本要一致，本文使用的是mongo:4.2.24。先把K8S上面的MongoDB 容器停止（可以把副本改成0）。1、将容器挂载MongoDB的数据目录备份到本地。经常是数据文
阅读更多2024-10-20
C#中实现事务
C#中实现事务
阅读更多2024-10-20
【LeetCode每日一题】——560.和为 K 的子数组
给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的子数组的个数。子数组是数组中元素的连续非空序列。
阅读更多2024-10-20
「漏洞复现」满客宝智慧食堂系统 selectUserByOrgId 未授权访问漏洞
请勿利用文章内的相关技术从事非法测试，由于传播、利用此文所提供的信息而造成的任何直接或者间接的后果及损失，均由使用者本人负责，作者不为此承担任何责任。工具来自网络，安全性自测，如有侵权请联系删除。本次
阅读更多2024-10-20
React面试题目（从基本到高级）
React前端面试常见题目涵盖了React的基础概念、组件、状态管理、生命周期、性能优化等多个方面。
阅读更多2024-10-20
12.个人博客系统（Java项目基于spring和vue）
1 在校学习的学生，可用于日常学习使用或是毕业设计使用 2 毕业一到两年的开发人员，用于锻炼自己的独立功能模块设计能力，增强代码编写能力。 3 亦可以部署为商化项目使用。 4 需要完整资料及源码
阅读更多2024-10-20
YoloV8改进策略：注意力改进|DeBiFormer，可变形双级路由注意力|引入DeBiLevelRoutingAttention注意力模块（全网首发）
本次改进的核心在于将DeBiLevelRoutingAttention模块嵌入到YoloV8的主干网络中，具体位置是在SPPF（Spatial Pyramid Pooling Fast）模块之后。这一
阅读更多2024-10-20
word取消自动单词首字母大写
情况说明：在word输入单词后首字母会自动变成大写取消单词首字母大写步骤：（1）点击菜单栏文件（2）点击“更多”——>“选项”（3）点击“校对”——>“自动更正选项”（4）取消“句首字母大
阅读更多2024-10-20
web前端网页用户注册页面
【代码】web前端网页用户注册页面。
阅读更多2024-10-20