决策树id3代码c++

决策树ID3算法是一种经典的机器学习算法，用于构建分类决策树。下面是一个简化的ID3算法的C代码实现。

首先，需要定义一个节点结构体，用于表示决策树的每个节点的属性。

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    int is_leaf; // 是否是叶子节点
    int label; // 叶子节点的类别标签
    int feature; // 当前节点的划分特征
    char value[20]; // 当前节点划分特征的取值
    struct node** children; // 当前节点的子节点
} Node;

接下来，实现一个函数用于计算数据集的熵。

// 计算数据集的熵
double calc_entropy(int* labels, int num_examples) {
    int i;
    double entropy = 0.0;
    int count[10] = {0}; // 假设类别标签的取值为0~9

    for (i = 0; i < num_examples; i++) {
        count[labels[i]]++;
    }

    for (i = 0; i < 10; i++) {
        if (count[i] > 0) {
            double prob = (double) count[i] / num_examples;
            entropy -= prob * log2(prob);
        }
    }

    return entropy;
}

接下来，实现主要的ID3算法过程，包括选择最佳划分特征、计算信息增益、递归构建决策树的子树等。

// 选择最佳特征
int choose_best_feature(int** features, int* labels, int num_examples, int num_features) {
    double min_entropy = INFINITY;
    int best_feature = -1;
    int i, j;

    double base_entropy = calc_entropy(labels, num_examples);

    for (i = 0; i < num_features; i++) {
        double new_entropy = 0.0;
        int* counts = (int*) calloc(10, sizeof(int)); // 假设特征的取值为0~9

        // 根据特征的取值对数据进行划分，并统计类别标签的数量
        for (j = 0; j < num_examples; j++) {
            counts[features[j][i]]++;
        }

        // 根据特征的不同取值计算新的熵
        for (j = 0; j < 10; j++) {
            int count = counts[j];
            int k;

            if (count > 0) {
                double prob = (double) count / num_examples;
                int* new_labels = (int*) calloc(count, sizeof(int));
                int index = 0;

                // 从原始数据集中筛选符合特征取值的样本
                for (k = 0; k < num_examples; k++) {
                    if (features[k][i] == j) {
                        new_labels[index] = labels[k];
                        index++;
                    }
                }

                double subset_entropy = calc_entropy(new_labels, count);
                new_entropy += prob * subset_entropy;

                free(new_labels);
            }
        }

        // 计算信息增益，选择熵减最大的特征作为最佳划分特征
        double info_gain = base_entropy - new_entropy;
        if (info_gain < min_entropy) {
            min_entropy = info_gain;
            best_feature = i;
        }

        free(counts);
    }

    return best_feature;
}

// 构建决策树
Node* build_tree(int** features, int* labels, int num_examples, int num_features) {
    Node* root = (Node*) malloc(sizeof(Node));
    root->is_leaf = 0;

    // 如果所有样本都属于同一类别，则直接作为叶子节点返回
    int all_same = 1;
    int i;

    for (i = 1; i < num_examples; i++) {
        if (labels[i] != labels[i - 1]) {
            all_same = 0;
            break;
        }
    }

    if (all_same) {
        root->is_leaf = 1;
        root->label = labels[0];
        return root;
    }

    // 如果所有特征都已经用完，则选择样本数最多的类别作为叶子节点返回
    if (num_features == 0) {
        root->is_leaf = 1;
        int max_count = 0;
        int max_label = -1;
        int* counts = (int*) calloc(10, sizeof(int)); // 假设类别标签的取值为0~9

        for (i = 0; i < num_examples; i++) {
            counts[labels[i]]++;
        }

        for (i = 0; i < 10; i++) {
            if (counts[i] > max_count) {
                max_count = counts[i];
                max_label = i;
            }
        }

        root->label = max_label;
        free(counts);

        return root;
    }

    // 选择最佳划分特征
    int best_feature = choose_best_feature(features, labels, num_examples, num_features);

    root->feature = best_feature;
    root->children = (Node**) malloc(10 * sizeof(Node*)); // 假设特征的取值为0~9

    // 根据最佳划分特征的不同取值递归构建子树
    for (i = 0; i < 10; i++) {
        int count = 0;
        int** new_features = (int**) malloc(num_examples * sizeof(int*));
        int* new_labels = (int*) malloc(num_examples * sizeof(int));
        int j;

        for (j = 0; j < num_examples; j++) {
            if (features[j][best_feature] == i) {
                new_features[count] = (int*) malloc((num_features - 1) * sizeof(int));
                memcpy(new_features[count], features[j], best_feature * sizeof(int));
                memcpy(new_features[count] + best_feature, features[j] + best_feature + 1, (num_features - best_feature - 1) * sizeof(int));
                new_labels[count] = labels[j];
                count++;
            }
        }

        if (count > 0) {
            root->children[i] = build_tree(new_features, new_labels, count, num_features - 1);
        } else {
            root->children[i] = (Node*) malloc(sizeof(Node));
            root->children[i]->is_leaf = 1;

            int max_count = 0;
            int max_label = -1;
            int* counts = (int*) calloc(10, sizeof(int)); // 假设类别标签的取值为0~9

            for (j = 0; j < num_examples; j++) {
                counts[labels[j]]++;
            }

            for (j = 0; j < 10; j++) {
                if (counts[j] > max_count) {
                    max_count = counts[j];
                    max_label = j;
                }
            }

            root->children[i]->label = max_label;
            free(counts);
        }

        free(new_features);
        free(new_labels);
    }

    return root;
}

以上是决策树ID3算法的C代码实现，可以根据实际问题进行调整和扩展。在实际应用中，还需要考虑特征的选择、剪枝等问题，以提高决策树的性能和泛化能力。