C4.5决策树算法C语言实现：从理论到工程实践

1次阅读

没有评论

共计 2342 个字符，预计需要花费 6 分钟才能阅读完成。

C4.5 算法是机器学习中经典的决策树算法，由 Ross Quinlan 在 ID3 算法基础上改进而来。它广泛应用于分类问题，比如医疗诊断、信用评级、客户分群等场景。相比 ID3，C4.5 主要优势在于：

能够处理连续值属性
使用信息增益比代替信息增益，减少属性取值数目带来的偏差
支持缺失值处理
提供剪枝功能避免过拟合

C4.5 算法的核心是选择最优划分属性，这里用信息增益比作为评判标准。下面我们分步骤解释：

计算数据集的经验熵 H(D)，表示当前数据集的不确定性
对于每个属性 A，计算条件熵 H(D|A)，表示在已知属性 A 的情况下数据集的不确定性
计算信息增益 Gain(A) = H(D) – H(D|A)
计算属性 A 的分裂信息 SplitInfo(A)
最终的信息增益比为 GainRatio(A) = Gain(A)/SplitInfo(A)

选择信息增益比最大的属性作为当前节点的划分属性。

首先我们需要设计几个关键数据结构：

// 定义属性类型
typedef enum {DISCRETE, CONTINUOUS} AttributeType;

// 定义属性结构
typedef struct {
    char* name;
    AttributeType type;
    char** categories;  // 离散属性的取值
    int num_categories;
    float split_value;  // 连续属性的分割值
} Attribute;

// 定义数据样本结构
typedef struct {
    float* values;      // 属性值数组
    int class_label;    // 类别标签
} Sample;

// 定义决策树节点结构
typedef struct TreeNode {
    int attribute_index;    // 当前节点划分属性的索引
    float split_value;      // 连续属性的分割值
    struct TreeNode** children; // 子节点指针数组
    int num_children;
    int class_label;        // 叶节点的类别
    bool is_leaf;
} TreeNode;

计算信息增益比的主要函数：

float calculate_gain_ratio(Dataset* dataset, int attribute_index) {
    // 计算原始熵
    float base_entropy = calculate_entropy(dataset);

    // 计算条件熵
    float conditional_entropy = 0.0;
    float split_info = 0.0;

    if (dataset->attributes[attribute_index].type == DISCRETE) {
        // 离散属性处理
        // ... 具体实现代码
    } else {
        // 连续属性处理
        // ... 具体实现代码
    }

    float gain = base_entropy - conditional_entropy;
    return gain / split_info;
}

递归构建决策树的主函数：

TreeNode* build_tree(Dataset* dataset, Attribute* attributes, int num_attributes) {
    // 终止条件 1：所有样本属于同一类
    if (all_samples_same_class(dataset)) {TreeNode* leaf = create_leaf_node(dataset->samples[0].class_label);
        return leaf;
    }

    // 终止条件 2：没有更多属性可供划分
    if (num_attributes == 0) {TreeNode* leaf = create_leaf_node(get_majority_class(dataset));
        return leaf;
    }

    // 选择最优划分属性
    int best_attr = select_best_attribute(dataset, attributes, num_attributes);

    // 创建内部节点
    TreeNode* node = create_internal_node(best_attr);

    // 根据属性类型进行划分
    if (attributes[best_attr].type == DISCRETE) {
        // 离散属性处理
        // ... 具体实现代码
    } else {
        // 连续属性处理
        // ... 具体实现代码
    }

    return node;
}

在 C 语言实现中，性能优化尤为重要：