一、实验介绍

1.1 实验背景

决策树是一种经典的机器学习算法，广泛应用于分类和回归任务。本实验基于贷款审批场景，使用决策树算法对申请人数据进行分类预测，判断是否应该批准贷款申请。

1.2 实验目标

• 理解决策树算法的基本原理和实现过程

• 掌握信息增益和熵的计算方法

• 实现完整的决策树分类器

• 在真实数据集上进行训练和测试

• 分析模型性能并解释预测结果

1.3 数据集说明

实验使用两个数据文件：

• dataset.txt：训练数据，包含16条记录

• testset.txt：测试数据，包含7条记录

特征维度：

• 年龄段：0=青年，1=中年，2=老年

• 有工作：0=否，1=是

• 有自己的房子：0=否，1=是

• 信贷情况：0=一般，1=好，2=非常好

• 类别标签：0=拒绝贷款，1=批准贷款

二、决策树算法原理

2.1 算法概述

决策树是一种树形结构，其中：

• 内部节点表示特征属性

• 分支代表特征取值

• 叶节点代表分类结果

2.2 核心步骤

2.2.1 特征选择

使用信息增益来选择最佳分裂特征，信息增益计算公式：

2.2.2 熵的计算

熵表示数据的不确定性，计算公式：

其中p_i是第i类样本所占比例。

2.2.3 递归构建

1. 从根节点开始，选择最佳分裂特征

2. 根据特征阈值分割数据

3. 对子节点递归执行上述过程

4. 直到满足终止条件

2.2.4 终止条件

• 节点样本属于同一类别

• 没有更多特征可用

• 达到最大深度限制

• 样本数量小于最小分裂阈值

三、实现详解

3.1 环境搭建

import numpy as np
from collections import Counter

所需库：

• numpy：数值计算和数组操作

• collections.Counter：统计标签出现频率

3.2 核心代码实现

3.2.1 节点类定义

class Node:
    def __init__(self, feature=None, threshold=None, left=None, right=None, value=None):
        self.feature = feature      # 分裂特征索引
        self.threshold = threshold  # 分裂阈值
        self.left = left            # 左子树
        self.right = right          # 右子树
        self.value = value          # 叶节点的预测值

作用：定义决策树节点结构，存储分裂信息和子节点引用。

3.2.2 决策树类初始化

class DecisionTree:
    def __init__(self, max_depth=10, min_samples_split=2):
        self.max_depth = max_depth
        self.min_samples_split = min_samples_split
        self.root = None

作用：初始化决策树参数，设置最大深度和最小分裂样本数。

3.2.3 递归构建决策树

def _build_tree(self, X, y, depth):
    n_samples, n_features = X.shape
    
    # 终止条件检查
    if (depth >= self.max_depth or 
        len(np.unique(y)) == 1 or 
        n_samples < self.min_samples_split):
        return Node(value=self._most_common_label(y))
    
    # 寻找最佳分裂
    best_feature, best_threshold = self._best_split(X, y, n_features)
    
    if best_feature is None:
        return Node(value=self._most_common_label(y))
    
    # 递归构建子树
    left_indices, right_indices = self._split(X[:, best_feature], best_threshold)
    left = self._build_tree(X[left_indices], y[left_indices], depth + 1)
    right = self._build_tree(X[right_indices], y[right_indices], depth + 1)
    
    return Node(best_feature, best_threshold, left, right)

作用：核心递归函数，根据终止条件决定返回叶节点或继续分裂。

3.2.4 寻找最佳分裂

def _best_split(self, X, y, n_features):
    best_gain = -1
    best_feature, best_threshold = None, None
    
    for feature_idx in range(n_features):
        feature_values = X[:, feature_idx]
        thresholds = np.unique(feature_values)
        
        for threshold in thresholds:
            gain = self._information_gain(y, feature_values, threshold)
            if gain > best_gain:
                best_gain, best_feature, best_threshold = gain, feature_idx, threshold
    
    return best_feature, best_threshold

作用：遍历所有特征和阈值，找到信息增益最大的分裂方式。

3.2.5 计算信息增益

def _information_gain(self, y, feature_values, threshold):
    parent_entropy = self._entropy(y)
    left_indices, right_indices = self._split(feature_values, threshold)
    
    if len(left_indices) == 0 or len(right_indices) == 0:
        return 0
    
    n = len(y)
    entropy_left = self._entropy(y[left_indices])
    entropy_right = self._entropy(y[right_indices])
    child_entropy = (len(left_indices)/n)*entropy_left + (len(right_indices)/n)*entropy_right
    
    return parent_entropy - child_entropy

作用：计算特定分裂方式的信息增益，用于评估分裂质量。

3.2.6 计算熵

def _entropy(self, y):
    y_int = y.astype(int)
    hist = np.bincount(y_int)
    ps = hist / len(y)
    return -np.sum([p * np.log2(p) for p in ps if p > 0])

作用：计算数据集的熵，衡量数据的不纯度。

3.2.7 预测方法

def predict(self, X):
    return np.array([self._traverse_tree(x, self.root) for x in X])

def _traverse_tree(self, x, node):
    if node.value is not None:
        return node.value
    if x[node.feature] <= node.threshold:
        return self._traverse_tree(x, node.left)
    return self._traverse_tree(x, node.right)

作用：对新样本进行预测，从根节点开始遍历决策树。

四、实验结果分析

4.1 实现结果

4.2 模型性能

实验结果显示：

• 测试集准确率：100%

• 所有7个测试样本均被正确分类

• 模型表现出优秀的泛化能力

4.2 结果分析

从预测结果可以看出：

1. 有工作和有房产的申请人更容易获得贷款批准

2. 信贷情况良好是重要的批准因素

3. 即使年龄较大，但有工作或信贷良好仍可能获批

4. 模型学习到了合理的审批规则

附：完整代码

import numpy as np
from collections import Counter

class Node:
    """决策树节点类"""
    def __init__(self, feature=None, threshold=None, left=None, right=None, value=None):
        self.feature = feature
        self.threshold = threshold
        self.left = left
        self.right = right
        self.value = value

class DecisionTree:
    """决策树分类器"""
    
    def __init__(self, max_depth=10, min_samples_split=2):
        self.max_depth = max_depth
        self.min_samples_split = min_samples_split
        self.root = None
        
    def fit(self, X, y):
        """训练决策树"""
        y = y.astype(int)
        self.root = self._build_tree(X, y, depth=0)
    
    def _build_tree(self, X, y, depth):
        """递归构建决策树"""
        n_samples, n_features = X.shape
        
        # 终止条件
        if (depth >= self.max_depth or 
            len(np.unique(y)) == 1 or 
            n_samples < self.min_samples_split):
            return Node(value=self._most_common_label(y))
        
        # 寻找最佳分裂
        best_feature, best_threshold = self._best_split(X, y, n_features)
        
        if best_feature is None:
            return Node(value=self._most_common_label(y))
        
        # 递归构建子树
        left_indices, right_indices = self._split(X[:, best_feature], best_threshold)
        left = self._build_tree(X[left_indices], y[left_indices], depth + 1)
        right = self._build_tree(X[right_indices], y[right_indices], depth + 1)
        
        return Node(best_feature, best_threshold, left, right)
    
    def _best_split(self, X, y, n_features):
        """寻找最佳分裂特征和阈值"""
        best_gain = -1
        best_feature, best_threshold = None, None
        
        for feature_idx in range(n_features):
            feature_values = X[:, feature_idx]
            thresholds = np.unique(feature_values)
            
            for threshold in thresholds:
                gain = self._information_gain(y, feature_values, threshold)
                if gain > best_gain:
                    best_gain, best_feature, best_threshold = gain, feature_idx, threshold
        
        return best_feature, best_threshold
    
    def _information_gain(self, y, feature_values, threshold):
        """计算信息增益"""
        parent_entropy = self._entropy(y)
        left_indices, right_indices = self._split(feature_values, threshold)
        
        if len(left_indices) == 0 or len(right_indices) == 0:
            return 0
        
        n = len(y)
        entropy_left = self._entropy(y[left_indices])
        entropy_right = self._entropy(y[right_indices])
        child_entropy = (len(left_indices)/n)*entropy_left + (len(right_indices)/n)*entropy_right
        
        return parent_entropy - child_entropy
    
    def _split(self, feature_values, threshold):
        """根据阈值分割数据"""
        left_indices = np.argwhere(feature_values <= threshold).flatten()
        right_indices = np.argwhere(feature_values > threshold).flatten()
        return left_indices, right_indices
    
    def _entropy(self, y):
        """计算熵"""
        y_int = y.astype(int)
        hist = np.bincount(y_int)
        ps = hist / len(y)
        return -np.sum([p * np.log2(p) for p in ps if p > 0])
    
    def _most_common_label(self, y):
        """返回最常见的标签"""
        y_int = y.astype(int)
        return Counter(y_int).most_common(1)[0][0]
    
    def predict(self, X):
        """预测"""
        return np.array([self._traverse_tree(x, self.root) for x in X])
    
    def _traverse_tree(self, x, node):
        """遍历决策树进行预测"""
        if node.value is not None:
            return node.value
        if x[node.feature] <= node.threshold:
            return self._traverse_tree(x, node.left)
        return self._traverse_tree(x, node.right)

def load_data():
    """加载数据"""
    train_data = np.loadtxt('dataset.txt', delimiter=',')
    test_data = np.loadtxt('testset.txt', delimiter=',')
    
    X_train = train_data[:, :-1].astype(float)
    y_train = train_data[:, -1].astype(int)
    X_test = test_data[:, :-1].astype(float)
    y_test = test_data[:, -1].astype(int)
    
    return X_train, y_train, X_test, y_test

def print_feature_info():
    """打印特征信息"""
    print("数据特征说明")
    print("-" * 50)
    features = [
        ("年龄段", ["青年", "中年", "老年"]),
        ("有工作", ["否", "是"]),
        ("有自己的房子", ["否", "是"]),
        ("信贷情况", ["一般", "好", "非常好"]),
        ("是否给贷款", ["否", "是"])
    ]
    
    for name, values in features:
        value_desc = " | ".join([f"{i}={v}" for i, v in enumerate(values)])
        print(f"  {name}: {value_desc}")

def print_results(y_true, y_pred, X_test):
    """打印预测结果"""
    print("\n预测结果分析")
    print("-" * 50)
    
    accuracy = np.mean(y_true == y_pred)
    print(f"测试集样本数: {len(y_true)}")
    print(f"模型准确率: {accuracy:.1%}")
    
    print(f"真实标签: {list(y_true.astype(int))}")
    print(f"预测标签: {list(y_pred.astype(int))}")
    
    print("\n详细预测结果:")
    print("-" * 50)
    
    age_names = ['青年', '中年', '老年']
    
    for i in range(len(X_test)):
        features = X_test[i].astype(int)
        true_label = y_true[i]
        pred_label = y_pred[i]
        correct = "正确" if true_label == pred_label else "错误"
        
        age = age_names[features[0]]
        work = "有" if features[1] == 1 else "无"
        house = "有" if features[2] == 1 else "无"
        credit = ["一般", "好", "非常好"][features[3]]
        result = "批准" if pred_label == 1 else "拒绝"
        
        print(f"样本{i+1:2d}: {age}, {work}工作, {house}房, 信贷{credit} -> {result} ({correct})")

def main():
    """主函数"""
    print("=" * 50)
    print("决策树分类器 - 贷款审批预测")
    print("=" * 50)
    
    # 加载数据
    print("\n数据加载中...")
    X_train, y_train, X_test, y_test = load_data()
    print(f"训练数据: {len(X_train)} 条记录")
    print(f"测试数据: {len(X_test)} 条记录")
    
    # 显示特征信息
    print_feature_info()
    
    # 训练模型
    model = DecisionTree(max_depth=5)
    model.fit(X_train, y_train)
    
    # 预测
    y_pred = model.predict(X_test)
    
    # 显示结果
    print_results(y_test, y_pred, X_test)
    
    print("\n" + "=" * 50)
    print("预测分析完成")
    print("=" * 50)

if __name__ == "__main__":
    main()

五、实验总结

5.1 收获

1. 深入理解决策树原理：通过手动实现，深入理解了信息增益、熵计算等核心概念

2. 掌握递归算法设计：决策树的构建过程是典型的递归应用

3. 数据处理能力：学会了如何加载、预处理和转换机器学习数据

4. 模型评估方法：掌握了准确率计算和结果分析方法