Decision Tree and Random Forest

阅读数：1343次 2024-06-25

字数统计: 5.4k字 | 阅读时长≈ 24分

决策树（decision tree）是一种基本的分类与回归方法，本文主要讨论用于分类的决策树。决策树学习通常包括三个步骤：特征选择，决策树的生成和决策树的修剪。而随机森林则是由多个决策树所构成的一种分类器，更准确的说，随机森林是由多个弱分类器组合形成的强分类器。

1. 相关知识

本小节简单介绍在构建随机森林预测模型过程中所需要用到一些知识。

网格搜索（Grid Search）和交叉验证（Cross-Validation）是机器学习模型优化和评估中常用的两种技术。

网格搜索（Grid Search）

网格搜索是一种系统地遍历预定义的超参数组合，以找到使模型性能最优的超参数设置的方法。超参数是模型训练过程中不能通过数据直接学习到的参数，比如决策树的最大深度、随机森林中树的数量等。

主要步骤：

定义超参数搜索空间：确定需要优化的超参数及其可能的取值范围。
遍历所有组合：对于每一个超参数组合，训练模型并评估其性能。
选择最佳组合：记录每个超参数组合的性能，选出最优的那一个。

例如，如果要对随机森林的超参数进行网格搜索，可以设置如下搜索空间：

树的数量（tree_counts）：[10, 20, 30]
最大深度（max_depths）：[10, 15, 20]
最小分裂样本数（min_samples_split）：[2, 5, 10]
最小叶子节点样本数（min_samples_leaf）：[1, 2, 4]

网格搜索将遍历这些所有可能的组合，并找到使模型性能最佳的参数组合。

交叉验证（Cross-Validation）

交叉验证是一种评估模型泛化能力的技术，通过将数据集划分为多个子集，并多次训练和测试模型来获得更稳定和可靠的评估结果。

主要步骤：

划分数据集：将数据集划分为k个子集（称为折叠，folds）。
训练和测试：依次选择一个子集作为测试集，其余子集作为训练集，训练模型并评估性能。
平均性能：对每个折叠的性能进行平均，得到模型的总体性能指标。

最常用的交叉验证方法是k折交叉验证（k-fold cross-validation），其中k是折叠数。例如，5折交叉验证将数据集分为5个部分，每次使用其中一个部分作为测试集，其他4个部分作为训练集，重复5次，最终取5次测试结果的平均值作为模型的性能指标。

数据增强

数据增强技术如缩放、平移、旋转等通常应用于图像数据集，以增加训练数据的多样性和提高模型的鲁棒性。然而，这些技术并不总是适用于所有类型的数据。对于非图像数据（如表格数据、时间序列数据等），这些特定的增强操作可能并不适用，甚至可能会导致模型性能下降。

在使用随机森林（Random Forest）处理数据时，如果你的数据集不是图像数据，则可能需要使用不同的数据增强方法。随机森林本身通过引入数据子集（bagging）和特征子集（feature bagging）来增加模型的鲁棒性，并不需要额外的数据增强操作

主成分分析算法（PCA）

Principal Component Analysis(PCA)是最常用的线性降维方法，它的目标是通过某种线性投影，将高维的数据映射到低维的空间中表示，并期望在所投影的维度上数据的方差最大，以此使用较少的数据维度，同时保留住较多的原数据点的特性。

通俗的理解，如果把所有的点都映射到一起，那么几乎所有的信息（如点和点之间的距离关系）都丢失了，而如果映射后方差尽可能的大，那么数据点则会分散开来，以此来保留更多的信息。可以证明，PCA是丢失原始数据信息最少的一种线性降维方式。（实际上就是最接近原始数据，但是PCA并不试图去探索数据内在结构）

使用PCA的优点包括：

降低数据维度：减少特征数量，降低模型复杂度，减少计算成本。
去除冗余信息：消除多重共线性，提取数据中的主要成分。
增强模型性能：在某些情况下，通过降维可以提高模型的泛化能力。

然而，PCA也有一些注意事项：

解释性降低：降维后的特征可能失去原有的物理意义，解释性降低。
信息丢失：降维过程中可能会丢失部分信息，尤其是当主要成分无法完全代表原始数据时。
数据标准化：在应用PCA之前，需要对数据进行标准化处理，以确保各特征具有相同的尺度。

在使用PCA时，一般的步骤如下：

数据标准化：将数据标准化为均值为0、方差为1。
计算协方差矩阵：计算数据的协方差矩阵，描述各特征之间的线性关系。
特征值分解：对协方差矩阵进行特征值分解，得到特征值和特征向量。
选择主成分：根据特征值大小选择前k个主成分，构建降维后的数据集。

决策树

基本概念

决策树是一种树形结构的模型，用于对数据进行分类或回归。它通过一系列的决策规则（节点上的条件判断）将数据划分成不同的分支，最终在叶节点上给出预测结果。

数据结构:
- 定义节点结构，包含特征索引、阈值、左子树、右子树、预测值等。
算法实现:
- 递归地构建决策树。
- 使用信息增益（如Gini指数或信息熵）选择最佳特征和阈值。
- 实现剪枝算法（如预剪枝或后剪枝）。
接口函数:
- 训练函数：接受训练数据和标签，构建决策树。
- 预测函数：接受测试数据，返回预测结果。

构建过程

选择最佳分裂点：从所有特征中选择一个最佳特征及其分裂点（阈值），根据该特征将数据集分成两个子集。最佳分裂点通常通过某种度量标准（如信息增益、基尼系数）来确定。
递归分裂：对每个子集重复上述过程，直到满足停止条件（如达到最大深度、节点纯净、样本数小于最小样本数等）。
终止条件：如果达到最大深度或节点中的样本足够纯净，则停止分裂。此时，叶节点的预测结果可以通过多数投票（分类任务）或均值（回归任务）来确定。

示例

假设有一个数据集，其中每个样本有两个特征：年龄和收入。目标是预测某人是否会购买某商品。

根节点根据“年龄 < 30”进行第一次分裂。
分裂后的左子节点根据“收入 < 50000”进行第二次分裂。
最终叶节点分别表示“购买”和“不购买”的决策。

优缺点

优点：
- 简单易理解，直观的树形结构。
- 不需要大量的数据预处理（如归一化、缺失值处理）。
- 可以处理数值型和分类型数据。
缺点：
- 容易过拟合（尤其是深树）。
- 对于少数类样本的分类效果不好。
- 对噪声数据敏感。

随机森林

基本概念

随机森林是由多棵决策树组成的集成模型。通过构建多个决策树并结合它们的预测结果，随机森林通常可以获得比单一决策树更好的预测性能和泛化能力。

数据结构:
- 使用多个决策树。
算法实现:
- 使用Bootstrap抽样法生成多个数据集。
- 在每个数据集上训练一个决策树。
- 实现投票机制：对每个测试样本，由所有决策树进行投票，输出最多的类别。
接口函数:
- 训练函数：接受训练数据和标签，构建随机森林。
- 预测函数：接受测试数据，返回预测结果。

构建过程

自助法（Bootstrap）抽样：从原始数据集中有放回地抽取多个子样本集，每个子样本集用于训练一棵决策树。
构建多棵决策树：对每个子样本集构建一棵决策树。为了增加多样性，通常在每个节点分裂时随机选择部分特征进行选择最佳分裂点（称为随机特征选择）。
预测

：
- 分类任务：将每棵树的预测结果进行多数投票，选择票数最多的类别作为最终预测结果。
- 回归任务：将每棵树的预测结果取平均值作为最终预测结果。

示例

假设有一个数据集，其中每个样本有两个特征：年龄和收入。目标是预测某人是否会购买某商品。

从原始数据集中抽取多个子样本集，每个子样本集用于训练一棵决策树。
每棵树根据不同的分裂规则进行训练。
对于新的样本，通过每棵树进行预测，并将预测结果进行多数投票。

优缺点

优点：
- 通常比单棵决策树具有更好的预测性能和泛化能力。
- 能够有效减少过拟合问题。
- 可以处理高维数据和大规模数据。
缺点：
- 训练和预测速度较慢（由于需要构建和预测多棵树）。
- 模型较复杂，不易解释。

2. 程序实现

决策树（Decision Tree）

1. 构造函数 `DecisionTree::DecisionTree`

DecisionTree::DecisionTree(int max_depth, int min_samples_split, int min_samples_leaf)
    : max_depth(max_depth), min_samples_split(min_samples_split), min_samples_leaf(min_samples_leaf), root(nullptr) {}

参数：
- max_depth：树的最大深度。
- min_samples_split：一个节点拆分所需的最小样本数。
- min_samples_leaf：一个叶节点所需的最小样本数。

2. 训练 `DecisionTree::train`

void DecisionTree::train(const std::vector<std::vector<double>>& data, const std::vector<int>& labels) {
    root = build_tree(data, labels, 0);
}

调用 build_tree 方法从根节点开始构建决策树。

3. 预测 `DecisionTree::predict`

int DecisionTree::predict(const std::vector<double>& sample) const {
    return predict_sample(root, sample);
}

通过递归调用 predict_sample 方法从根节点开始预测样本的分类。

4. 构建树 `DecisionTree::build_tree`

TreeNode* DecisionTree::build_tree(const std::vector<std::vector<double>>& data, const std::vector<int>& labels, int depth) {
    if (depth >= max_depth || is_pure(labels) || data.size() < min_samples_split) {
        TreeNode* leaf = new TreeNode();
        leaf->prediction = majority_vote(labels);
        return leaf;
    }

    int best_feature;
    double best_threshold;
    find_best_split(data, labels, best_feature, best_threshold);

    TreeNode* node = new TreeNode();
    node->feature_index = best_feature;
    node->threshold = best_threshold;

    std::vector<std::vector<double>> left_data, right_data;
    std::vector<int> left_labels, right_labels;
    split_data(data, labels, best_feature, best_threshold, left_data, left_labels, right_data, right_labels);

    if (left_data.size() < min_samples_leaf || right_data.size() < min_samples_leaf) {
        TreeNode* leaf = new TreeNode();
        leaf->prediction = majority_vote(labels);
        return leaf;
    }

    node->left = build_tree(left_data, left_labels, depth + 1);
    node->right = build_tree(right_data, right_labels, depth + 1);

    return node;
}

核心逻辑

：
- 判断当前深度是否超过最大深度，数据是否纯净，或样本数量是否少于最小拆分样本数。
- 找到最佳拆分点。
- 递归构建左右子树。

5. 数据拆分 `DecisionTree::split_data`

void DecisionTree::split_data(const std::vector<std::vector<double>>& data, const std::vector<int>& labels, int feature, double threshold,
    std::vector<std::vector<double>>& left_data, std::vector<int>& left_labels,
    std::vector<std::vector<double>>& right_data, std::vector<int>& right_labels) {
    for (size_t i = 0; i < data.size(); ++i) {
        if (data[i][feature] < threshold) {
            left_data.push_back(data[i]);
            left_labels.push_back(labels[i]);
        }
        else {
            right_data.push_back(data[i]);
            right_labels.push_back(labels[i]);
        }
    }
}

根据最佳特征和阈值将数据分成左子树和右子树。

6. 查找最佳拆分点 `DecisionTree::find_best_split`

void DecisionTree::find_best_split(const std::vector<std::vector<double>>& data, const std::vector<int>& labels,
    int& best_feature, double& best_threshold) {
    double best_gain = -1.0;
    int num_features = data[0].size();

    for (int feature = 0; feature < num_features; ++feature) {
        std::vector<double> values;
        for (const auto& sample : data) {
            values.push_back(sample[feature]);
        }

        std::sort(values.begin(), values.end());
        for (size_t i = 1; i < values.size(); ++i) {
            double threshold = (values[i - 1] + values[i]) / 2;
            double gain = calculate_gain(data, labels, feature, threshold);

            if (gain > best_gain) {
                best_gain = gain;
                best_feature = feature;
                best_threshold = threshold;
            }
        }
    }
}

计算每个特征的每个可能阈值的增益，选择增益最大的特征和阈值作为最佳拆分点。

7. 计算信息增益 `DecisionTree::calculate_gain`

double DecisionTree::calculate_gain(const std::vector<std::vector<double>>& data, const std::vector<int>& labels, int feature, double threshold) {
    std::vector<std::vector<double>> left_data, right_data;
    std::vector<int> left_labels, right_labels;
    split_data(data, labels, feature, threshold, left_data, left_labels, right_data, right_labels);

    double p_left = static_cast<double>(left_labels.size()) / labels.size();
    double p_right = static_cast<double>(right_labels.size()) / labels.size();

    return entropy(labels) - p_left * entropy(left_labels) - p_right * entropy(right_labels);
}

通过计算左右子树的熵来计算信息增益。

8. 计算熵 `DecisionTree::entropy`

double DecisionTree::entropy(const std::vector<int>& labels) const {
    std::unordered_map<int, int> label_counts;
    for (int label : labels) {
        label_counts[label]++;
    }

    double entropy = 0.0;
    for (const auto& pair : label_counts) {
        double p = static_cast<double>(pair.second) / labels.size();
        entropy -= p * std::log2(p);
    }
    return entropy;
}

根据类别的概率计算熵。

9. 判断纯净度 `DecisionTree::is_pure`

bool DecisionTree::is_pure(const std::vector<int>& labels) const {
    return std::all_of(labels.begin(), labels.end(), [&labels](int label) { return label == labels[0]; });
}

判断所有标签是否相同。

10. 多数投票 `DecisionTree::majority_vote`

int DecisionTree::majority_vote(const std::vector<int>& labels) const {
    std::unordered_map<int, int> label_counts;
    for (int label : labels) {
        label_counts[label]++;
    }

    return std::max_element(label_counts.begin(), label_counts.end(),
        [](const std::pair<int, int>& a, const std::pair<int, int>& b) {
            return a.second < b.second;
        })->first;
}

返回标签中出现次数最多的类别。

11. 保存树 `DecisionTree::save`

void DecisionTree::save(std::ofstream& ofs) const {
    save_node(root, ofs);
}

保存树的结构到文件。

12. 加载树 `DecisionTree::load`

void DecisionTree::load(std::ifstream& ifs) {
    root = load_node(ifs);
}

从文件加载树的结构。

随机森林（Random Forest）

1. 构造函数 `RandomForest::RandomForest`

RandomForest::RandomForest(int num_trees, int max_depth, int min_samples_split, int min_samples_leaf)
    : num_trees(num_trees), max_depth(max_depth), min_samples_split(min_samples_split), min_samples_leaf(min_samples_leaf) {
    std::srand(std::time(nullptr)); // 初始化随机种子
}

参数

：
- num_trees：森林中树的数量。
- max_depth：每棵树的最大深度。
- min_samples_split：一个节点拆分所需的最小样本数。
- min_samples_leaf：一个叶节点所需的最小样本数。

2. 训练 `RandomForest::train`

void RandomForest::train(const std::vector<std::vector<double>>& data, const std::vector<int>& labels) {
    trees.clear();
    for (int i = 0; i < num_trees; ++i) {
        std::vector<std::vector<double>> bootstrap_data;
        std::vector<int> bootstrap_labels;
        bootstrap(data, labels, bootstrap_data, bootstrap_labels);

        DecisionTree tree(max_depth, min_samples_split, min_samples_leaf);
        tree.train(bootstrap_data, bootstrap_labels);
        trees.push_back(tree);
    }
}

通过自助法（bootstrap）生成数据子集来训练每棵树。

3. 预测 `RandomForest::predict`

int RandomForest::predict(const std::vector<double>& sample) const {
    std::vector<int> predictions;
    for (const auto& tree : trees) {
        predictions.push_back(tree.predict(sample));
    }

    return majority_vote(predictions);
}

每棵树对样本进行预测，然后通过多数投票确定最终分类。

4. 自助法 `RandomForest::bootstrap`

void RandomForest::bootstrap(const std::vector<std::vector<double>>& data, const std::vector<int>& labels,
    std::vector<std::vector<double>>& bootstrap_data, std::vector<int>& bootstrap_labels) const {
    size_t n = data.size();
    for (size_t i = 0; i < n; ++i) {
        size_t index = std::rand() % n;
        bootstrap_data.push_back(data[index]);
        bootstrap_labels.push_back(labels[index]);
    }
}

从原始数据中随机采样生成新的训练数据集。

5. 准确率计算 `RandomForest::accuracy`

double RandomForest::accuracy(const std::vector<std::vector<double>>& data, const std::vector<int>& labels) const {
    int correct = 0;
    for (size_t i = 0; i < data.size(); ++i) {
        if (predict(data[i]) == labels[i]) {
            correct++;
        }
    }
    return static_cast<double>(correct) / data.size();
}

计算模型在数据集上的准确率。

6. 打印混淆矩阵 `RandomForest::print_confusion_matrix`

void RandomForest::print_confusion_matrix(const std::vector<std::vector<double>>& data, const std::vector<int>& labels) const {
    std::unordered_map<int, std::unordered_map<int, int>> matrix;
    int num_classes = 0;
    for (size_t i = 0; i < data.size(); ++i) {
        int actual = labels[i];
        int predicted = predict(data[i]);
        matrix[actual][predicted]++;
        num_classes = std::max(num_classes, std::max(actual, predicted) + 1);
    }

    std::cout << "Confusion Matrix:" << std::endl;
    for (int i = 0; i < num_classes; ++i) {
        for (int j = 0; j < num_classes; ++j) {
            std::cout << matrix[i][j] << " ";
        }
        std::cout << std::endl;
    }
}

打印混淆矩阵，显示预测结果与实际标签的对比。

7. 计算性能指标 `RandomForest::calculate_metrics`

void RandomForest::calculate_metrics(const std::vector<std::vector<double>>& data, const std::vector<int>& labels) const {
    std::unordered_map<int, int> true_positives, false_positives, false_negatives;
    for (size_t i = 0; i < data.size(); ++i) {
        int actual = labels[i];
        int predicted = predict(data[i]);
        if (predicted == actual) {
            true_positives[actual]++;
        }
        else {
            false_positives[predicted]++;
            false_negatives[actual]++;
        }
    }

    for (const auto& tp : true_positives) {
        int label = tp.first;
        int tp_count = tp.second;
        int fp_count = false_positives[label];
        int fn_count = false_negatives[label];
        double precision = tp_count / static_cast<double>(tp_count + fp_count);
        double recall = tp_count / static_cast<double>(tp_count + fn_count);
        double f1_score = 2 * (precision * recall) / (precision + recall);
        std::cout << "Label: " << label << " Precision: " << precision << " Recall: " << recall << " F1-Score: " << f1_score << std::endl;
    }
}

计算每个类别的精确率、召回率和F1分数。

8. 交叉验证 `RandomForest::cross_validate`

void RandomForest::cross_validate(const std::vector<std::vector<double>>& data, const std::vector<int>& labels, int k) {
    std::vector<int> indices(data.size());
    std::iota(indices.begin(), indices.end(), 0);
    std::shuffle(indices.begin(), indices.end(), std::mt19937{ std::random_device{}() });

    int fold_size = data.size() / k;
    double total_accuracy = 0.0;

    for (int i = 0; i < k; ++i) {
        std::vector<std::vector<double>> train_data, test_data;
        std::vector<int> train_labels, test_labels;

        for (int j = 0; j < data.size(); ++j) {
            if (j >= i * fold_size && j < (i + 1) * fold_size) {
                test_data.push_back(data[indices[j]]);
                test_labels.push_back(labels[indices[j]]);
            }
            else {
                train_data.push_back(data[indices[j]]);
                train_labels.push_back(labels[indices[j]]);
            }
        }

        train(train_data, train_labels);
        double acc = accuracy(test_data, test_labels);
        total_accuracy += acc;

        std::cout << "Fold " << i + 1 << " Accuracy: " << acc << std::endl;
    }

    std::cout << "Average Accuracy: " << total_accuracy / k << std::endl;
}

对数据进行k折交叉验证，评估模型性能。

9. 网格搜索 `RandomForest::grid_search`

void RandomForest::grid_search(const std::vector<std::vector<double>>& data, const std::vector<int>& labels) {
    std::vector<int> tree_counts = { 10, 20, 30 };
    std::vector<int> max_depths = { 10, 15, 20 };
    std::vector<int> min_samples_split = { 2, 5, 10 };
    std::vector<int> min_samples_leaf = { 1, 2, 4 };

    double best_accuracy = 0.0;
    int best_tree_count = 0;
    int best_max_depth = 0;
    int best_min_samples_split = 0;
    int best_min_samples_leaf = 0;

    for (int tree_count : tree_counts) {
        for (int max_depth : max_depths) {
            for (int min_split : min_samples_split) {
                for (int min_leaf : min_samples_leaf) {
                    RandomForest forest(tree_count, max_depth, min_split, min_leaf);
                    std::vector<int> indices(data.size());
                    std::iota(indices.begin(), indices.end(), 0);
                    std::shuffle(indices.begin(), indices.end(), std::mt19937{ std::random_device{}() });

                    int k = 5;
                    int fold_size = data.size() / k;
                    double total_accuracy = 0.0;

                    for (int i = 0; i < k; ++i) {
                        std::vector<std::vector<double>> train_data, test_data;
                        std::vector<int> train_labels, test_labels;

                        for (int j = 0; j < data.size(); ++j) {
                            if (j >= i * fold_size && j < (i + 1) * fold_size) {
                                test_data.push_back(data[indices[j]]);
                                test_labels.push_back(labels[indices[j]]);
                            }
                            else {
                                train_data.push_back(data[indices[j]]);
                                train_labels.push_back(labels[indices[j]]);
                            }
                        }

                        forest.train(train_data, train_labels);
                        double acc = forest.accuracy(test_data, test_labels);
                        total_accuracy += acc;
                    }

                    double avg_accuracy = total_accuracy / k;
                    if (avg_accuracy > best_accuracy) {
                        best_accuracy = avg_accuracy;
                        best_tree_count = tree_count;
                        best_max_depth = max_depth;
                        best_min_samples_split = min_split;
                        best_min_samples_leaf = min_leaf;
                    }
                }
            }
        }
    }

    std::cout << "Best Accuracy: " << best_accuracy << " with Trees: " << best_tree_count
        << ", Max Depth: " << best_max_depth
        << ", Min Samples Split: " << best_min_samples_split
        << ", Min Samples Leaf: " << best_min_samples_leaf << std::endl;
}

通过网格搜索找到最佳超参数组合。

10. 保存模型 `RandomForest::save_model`

void RandomForest::save_model(const std::string& filename) const {
    std::ofstream ofs(filename);
    if (!ofs.is_open()) {
        throw std::runtime_error("Could not open file to save model");
    }
    ofs << num_trees << " " << max_depth << " " << min_samples_split << " " << min_samples_leaf << "\n";
    for (const auto& tree : trees) {
        tree.save(ofs);
    }
}

功能：将随机森林模型保存到文件中。
步骤

：
1. 打开文件进行写操作。
2. 写入随机森林的参数：树的数量、最大深度、最小样本分裂数和最小样本叶数。
3. 依次保存每棵决策树的结构。

11. 加载模型 `RandomForest::load_model`

void RandomForest::load_model(const std::string& filename) {
    std::ifstream ifs(filename);
    if (!ifs.is_open()) {
        throw std::runtime_error("Could not open file to load model");
    }
    ifs >> num_trees >> max_depth >> min_samples_split >> min_samples_leaf;
    trees.resize(num_trees, DecisionTree(max_depth, min_samples_split, min_samples_leaf));
    for (auto& tree : trees) {
        tree.load(ifs);
    }
}

功能：从文件加载随机森林模型。
步骤

：
1. 打开文件进行读操作。
2. 读取随机森林的参数：树的数量、最大深度、最小样本分裂数和最小样本叶数。
3. 调整森林的大小，并加载每棵决策树的结构。

12. `DecisionTree::save_node` 和 `DecisionTree::load_node`

这些是辅助方法，用于递归地保存和加载决策树的节点。

保存节点

void DecisionTree::save_node(TreeNode* node, std::ofstream& ofs) const {
    if (!node) {
        ofs << "null\n";
        return;
    }
    ofs << node->feature_index << " " << node->threshold << " " << node->prediction << "\n";
    save_node(node->left, ofs);
    save_node(node->right, ofs);
}

功能：递归地保存树节点。
步骤

：
1. 如果节点为空，写入“null”表示叶节点。
2. 否则，写入节点的特征索引、阈值和预测值。
3. 递归保存左子节点和右子节点。

加载节点

TreeNode* DecisionTree::load_node(std::ifstream& ifs) {
    std::string token;
    ifs >> token;
    if (token == "null") {
        return nullptr;
    }
    TreeNode* node = new TreeNode();
    node->feature_index = std::stoi(token);
    ifs >> node->threshold >> node->prediction;
    node->left = load_node(ifs);
    node->right = load_node(ifs);
    return node;
}

功能：递归地加载树节点。

步骤：

读取一个标记，如果是“null”，返回空节点。
否则，创建一个新节点并读取特征索引、阈值和预测值。
递归加载左子节点和右子节点。

本文作者： hzr
本文链接： https://HZR0709.github.io/2024/06/25/Decision-Tree-and-Random-Forest/
版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！

1. 相关知识

网格搜索（Grid Search）

主要步骤：

交叉验证（Cross-Validation）

主要步骤：

数据增强

主成分分析算法（PCA）

决策树

基本概念

构建过程

示例

优缺点

随机森林

基本概念

构建过程

示例

优缺点

2. 程序实现

决策树（Decision Tree）

1. 构造函数 DecisionTree::DecisionTree

2. 训练 DecisionTree::train

3. 预测 DecisionTree::predict

4. 构建树 DecisionTree::build_tree

5. 数据拆分 DecisionTree::split_data

6. 查找最佳拆分点 DecisionTree::find_best_split

7. 计算信息增益 DecisionTree::calculate_gain

8. 计算熵 DecisionTree::entropy

9. 判断纯净度 DecisionTree::is_pure

10. 多数投票 DecisionTree::majority_vote

11. 保存树 DecisionTree::save

12. 加载树 DecisionTree::load

随机森林（Random Forest）

1. 构造函数 RandomForest::RandomForest

2. 训练 RandomForest::train

3. 预测 RandomForest::predict

4. 自助法 RandomForest::bootstrap

5. 准确率计算 RandomForest::accuracy

6. 打印混淆矩阵 RandomForest::print_confusion_matrix

7. 计算性能指标 RandomForest::calculate_metrics

8. 交叉验证 RandomForest::cross_validate

9. 网格搜索 RandomForest::grid_search

10. 保存模型 RandomForest::save_model

11. 加载模型 RandomForest::load_model

12. DecisionTree::save_node 和 DecisionTree::load_node

1. 构造函数 `DecisionTree::DecisionTree`

2. 训练 `DecisionTree::train`

3. 预测 `DecisionTree::predict`

4. 构建树 `DecisionTree::build_tree`

5. 数据拆分 `DecisionTree::split_data`

6. 查找最佳拆分点 `DecisionTree::find_best_split`

7. 计算信息增益 `DecisionTree::calculate_gain`

8. 计算熵 `DecisionTree::entropy`

9. 判断纯净度 `DecisionTree::is_pure`

10. 多数投票 `DecisionTree::majority_vote`

11. 保存树 `DecisionTree::save`

12. 加载树 `DecisionTree::load`

1. 构造函数 `RandomForest::RandomForest`

2. 训练 `RandomForest::train`

3. 预测 `RandomForest::predict`

4. 自助法 `RandomForest::bootstrap`

5. 准确率计算 `RandomForest::accuracy`

6. 打印混淆矩阵 `RandomForest::print_confusion_matrix`

7. 计算性能指标 `RandomForest::calculate_metrics`

8. 交叉验证 `RandomForest::cross_validate`

9. 网格搜索 `RandomForest::grid_search`

10. 保存模型 `RandomForest::save_model`

11. 加载模型 `RandomForest::load_model`

12. `DecisionTree::save_node` 和 `DecisionTree::load_node`