### 决策树算法的基础实现 决策树是一种强大的分类工具，它通过递归地分割数据集来构建模型[^3]。以下是使用基础 Python 语言实现决策树算法的代码示例，该实现是一个简化的版本，旨在帮助初学者理解其核心逻辑。 #### 数据集准备 首先需要定义一个数据集和对应的标签列表，用于训练决策树模型。 ```python # 定义数据集 dataset = [ ['青年', '否', '否', '一般'], ['青年', '否', '否', '好'], ['青年', '是', '否', '好'], ['青年', '是', '是', '一般'], ['青年', '否', '否', '一般'], ['中年', '否', '否', '一般'], ['中年', '否', '否', '好'], ['中年', '是', '是', '好'], ['中年', '否', '是', '非常好'], ['中年', '否', '是', '非常好'], ['老年', '否', '是', '非常好'], ['老年', '否', '是', '好'], ['老年', '是', '否', '好'], ['老年', '是', '否', '非常好'], ['老年', '否', '否', '一般'] ] # 定义标签 labels = ['年龄', '有工作', '有自己的房子', '信贷情况'] ``` #### 计算信息熵 信息熵是决策树分裂节点的核心指标之一，用于衡量数据的不确定性。 ```python import math def calc_entropy(dataset): num_entries = len(dataset) label_counts = {} for feat_vec in dataset: current_label = feat_vec[-1] if current_label not in label_counts.keys(): label_counts[current_label] = 0 label_counts[current_label] += 1 entropy = 0.0 for key in label_counts: prob = float(label_counts[key]) / num_entries entropy -= prob * math.log(prob, 2) return entropy ``` #### 划分数据集 根据某个特征的不同取值，将数据集划分为若干子集。 ```python def split_dataset(dataset, axis, value): ret_dataset = [] for feat_vec in dataset: if feat_vec[axis] == value: reduced_feat_vec = feat_vec[:axis] reduced_feat_vec.extend(feat_vec[axis+1:]) ret_dataset.append(reduced_feat_vec) return ret_dataset ``` #### 选择最佳划分特征 通过计算每个特征的信息增益，选择信息增益最大的特征作为划分标准。 ```python def choose_best_feature_to_split(dataset): num_features = len(dataset[0]) - 1 base_entropy = calc_entropy(dataset) best_info_gain = 0.0 best_feature = -1 for i in range(num_features): feat_list = [example[i] for example in dataset] unique_vals = set(feat_list) new_entropy = 0.0 for value in unique_vals: sub_dataset = split_dataset(dataset, i, value) prob = len(sub_dataset) / float(len(dataset)) new_entropy += prob * calc_entropy(sub_dataset) info_gain = base_entropy - new_entropy if info_gain > best_info_gain: best_info_gain = info_gain best_feature = i return best_feature ``` #### 构建决策树 递归地构建决策树，直到满足停止条件（如所有样本属于同一类或没有更多特征可用）。 ```python def majority_count(class_list): class_count = {} for vote in class_list: if vote not in class_count.keys(): class_count[vote] = 0 class_count[vote] += 1 sorted_class_count = sorted(class_count.items(), key=lambda x: x[1], reverse=True) return sorted_class_count[0][0] def create_tree(dataset, labels): class_list = [example[-1] for example in dataset] if class_list.count(class_list[0]) == len(class_list): return class_list[0] if len(dataset[0]) == 1: return majority_count(class_list) best_feat = choose_best_feature_to_split(dataset) best_feat_label = labels[best_feat] my_tree = {best_feat_label: {}} del(labels[best_feat]) feat_values = [example[best_feat] for example in dataset] unique_vals = set(feat_values) for value in unique_vals: sub_labels = labels[:] my_tree[best_feat_label][value] = create_tree(split_dataset(dataset, best_feat, value), sub_labels) return my_tree ``` #### 示例输出 以下为生成的决策树结构： ```python my_tree = create_tree(dataset, labels.copy()) print(my_tree) ``` ### 注意事项 上述代码实现了决策树的核心逻辑，但并未包含剪枝等优化技术。在实际应用中，建议结合集成方法（如随机森林）或使用成熟的库（如 `sklearn`）来提升模型性能[^3]。