1、引言

决策树（Decision Tree）是一种常见的分类和回归算法，它通过树形结构展示决策规则和分类结果。决策树的每个内部节点表示一个属性上的测试，每个分支代表一个测试输出，每个叶节点代表一种类别。

我理解就是对输入的特征不断做划分

2、决策树的基本原理

2.1

从某个特征出发，对其进行判断，根据不同判断结果开发不同分支，然后进行下一个特征判断，选择特征的依据可以使用信息增益来判断，目的是为了将无序的数据变得有序，使得分支节点的数据尽可能属于同一类别

2.2 信息增益

熵定义为信息的期望值，信息定义为：
$$l(x_i)=-{\log }_{2}p(x_i)$$
其中$p(x_i)$定义为选择$x_i$分类的概率

熵可表示为：
$$H=-\sum _{l=1}^{n}p(x_i)lo{g}_{2}p(x_i)$$
其中$n$是分类数目

熵越大，说明数据分类越多，数据越混乱，举个例子，假设数据只有一种分类，那么$p(x)=1.0$，$lo{g}_{2}p(x)=0.$，$H=0.$

3、决策树的构建方法

使用不同的划分方式衍生出不同的算法，后续两种算法待后续学习补充
信息增益：ID3算法
信息增益比：C4.5算法
基尼系数：CART算法

3.1 建立数据集

def create_dataset() -> tuple:
    """创建示例数据集

    Returns:
        tuple: 数据集和特征标签
    """
    dataset = [
        [1, 1, 'yes'],
        [1, 1, 'yes'],
        [1, 0, 'no'],
        [0, 1, 'no'],
        [0, 1, 'no']
    ]
    feature_labels = ['no_surfacing', 'flippers']  # 特征标签：是否有浮出水面，是否有脚蹼
    return dataset, feature_labels

3.2 计算数据集信息熵

def calculate_shannon_entropy(dataset: List[List]) -> float:
    """计算数据集的香农熵（信息熵）

    Args:
        dataset: 数据集

    Returns:
        float: 香农熵值
    """
    num_entries = len(dataset)
    label_counts = defaultdict(int)

    # 统计每个标签的出现次数
    for entry in dataset:
        label = entry[-1]
        label_counts[label] += 1

    shannon_entropy = 0.0

    # 计算每个类别的概率并累加香农熵
    for count in label_counts.values():
        probability = count / num_entries
        shannon_entropy -= probability * np.log2(probability)

    return shannon_entropy

3.3 划分数据集

def split_dataset_by_feature(dataset: List[List], feature_index: int, feature_value: Any) -> List[List]:
    """根据指定特征和特征值划分数据集

    Args:
        dataset: 原始数据集
        feature_index: 特征索引
        feature_value: 特征值

    Returns:
        List[List]: 划分后的子数据集
    """
    sub_dataset = []

    for entry in dataset:
        if entry[feature_index] == feature_value:
            # 移除当前特征，保留其他特征
            new_entry = entry[:feature_index] + entry[feature_index + 1:]
            sub_dataset.append(new_entry)

    return sub_dataset

3.4 选择最好的数据集划分方式

def select_best_split_feature(dataset: List[List]) -> int:
    """选择最佳划分特征（信息增益最大的特征）

    Args:
        dataset: 数据集

    Returns:
        int: 最佳特征索引
    """
    num_features = len(dataset[0]) - 1  # 特征数量（最后一列是标签）
    num_entries = len(dataset)
    base_entropy = calculate_shannon_entropy(dataset)
    best_info_gain = 0.0
    best_feature_index = -1

    # 遍历所有特征
    for feature_index in range(num_features):
        # 获取该特征的所有值
        feature_values = [entry[feature_index] for entry in dataset]
        unique_values = set(feature_values)
        conditional_entropy = 0.0

        # 计算按该特征划分后的条件熵
        for value in unique_values:
            sub_dataset = split_dataset_by_feature(dataset, feature_index, value)
            probability = len(sub_dataset) / num_entries
            conditional_entropy += probability * calculate_shannon_entropy(sub_dataset)

        info_gain = base_entropy - conditional_entropy

        # 更新最佳特征
        if info_gain > best_info_gain:
            best_info_gain = info_gain
            best_feature_index = feature_index

    return best_feature_index

这里首先遍历数据集，发现有两个特征（‘不浮出水面是否可以生存’和‘是否有脚蹼’），其次遍历每个特征有几个属性（‘不浮出水面是否可以生存’特征有‘是’和‘否’两个属性；‘是否有脚蹼’特征有‘是’和‘否’两个属性），然后划分数据集，从‘不浮出水面是否可以生存’特征的‘否’属性可以得到新的数据集，计算按该特征划分后的条件熵$conditional\_entropy$，最后更新最新特征（这里更新最新特征的依据是选择条件熵最小的）

3.5 构建决策树

从原始数据集基于最好的属性值划分数据集，由于特征值可能多于两个，因此可能存在大于两个分支的数据集划分。第一次划分之后，数据将被向下传递到树分支的下一个节点，在这个节点上，我们可以再次划分数据。因此我们可以采用递归的原则处理数据集。
递归结束的条件是：程序遍历完所有划分数据集的属性，或者每个分支下的所有实例都具有相同的分类。如果所有实例具有相同的分类，则得到一个叶子节点或者终止块。任何到达叶子节点的数据必然属于叶子节点的分类。

def majority_vote(class_list: List[str]) -> str:
    """统计出现次数最多的类别（多数表决）

    Args:
        class_list: 类别列表

    Returns:
        str: 出现次数最多的类别
    """
    class_count = {}

    for class_label in class_list:
        class_count[class_label] = class_count.get(class_label, 0) + 1

    # 按出现次数降序排序
    sorted_classes = sorted(class_count.items(), key=lambda x: x[1], reverse=True)
    return sorted_classes[0][0]  # 返回出现次数最多的类别


def build_decision_tree(dataset: List[List], feature_labels: List[str]) -> Dict:
    """递归创建决策树

    Args:
        dataset: 数据集
        feature_labels: 特征标签列表

    Returns:
        Dict: 决策树字典
    """
    class_labels = [entry[-1] for entry in dataset]

    # 终止条件1：所有样本属于同一类别
    if class_labels.count(class_labels[0]) == len(class_labels):
        return class_labels[0]

    # 终止条件2：没有更多特征可用于划分
    if len(dataset[0]) == 1:
        return majority_vote(class_labels)

    # 选择最佳划分特征
    best_feature_index = select_best_split_feature(dataset)
    best_feature_label = feature_labels[best_feature_index]

    # 创建当前节点
    decision_tree = {best_feature_label: {}}

    # 复制特征标签列表（避免修改原列表）
    remaining_labels = feature_labels.copy()
    remaining_labels.pop(best_feature_index)

    # 获取该特征的所有唯一值
    feature_values = [entry[best_feature_index] for entry in dataset]
    unique_values = set(feature_values)

    # 为每个特征值递归创建子树
    for value in unique_values:
        sub_labels = remaining_labels.copy()
        sub_dataset = split_dataset_by_feature(dataset, best_feature_index, value)

        # 如果子数据集为空，使用多数表决
        if not sub_dataset:
            decision_tree[best_feature_label][value] = majority_vote(class_labels)
        else:
            decision_tree[best_feature_label][value] = build_decision_tree(
                sub_dataset, sub_labels
            )

    return decision_tree

划分结果长这样：

这里我的理解就是先选最能代表这个类的特征，最能代表的话那肯定就是这个特征在这个类别所有特征里出现的最多，熵最低，再依次选其他特征。

3.6 测试算法

def classify_with_tree(decision_tree: Dict, feature_labels: List[str],
                       test_sample: List) -> str:
    """使用决策树进行分类预测

    Args:
        decision_tree: 训练好的决策树
        feature_labels: 特征标签列表
        test_sample: 测试样本特征值

    Returns:
        str: 分类结果
    """
    root_feature = list(decision_tree.keys())[0]
    sub_tree = decision_tree[root_feature]
    feature_index = feature_labels.index(root_feature)

    for value, branch in sub_tree.items():
        if test_sample[feature_index] == value:
            if isinstance(branch, dict):
                return classify_with_tree(branch, feature_labels, test_sample)
            else:
                return branch

    # 如果没有匹配的分支，返回默认值或抛出异常
    raise ValueError("No matching branch found for the test sample")

测试算法

def main():
    """主函数示例"""
    # 创建数据集
    dataset, feature_labels = create_dataset()
    print("Dataset:", dataset)
    print("Feature labels:", feature_labels)
    
    # 构建决策树
    decision_tree = build_decision_tree(dataset, feature_labels.copy())
    print("Decision tree:", decision_tree)

    # 测试分类
    test_sample = [1, 1]
    result = classify_with_tree(decision_tree, feature_labels, test_sample)
    print(f"Classification result for {test_sample}: {result}")

    test_sample = [1, 0]
    result = classify_with_tree(decision_tree, feature_labels, test_sample)
    print(f"Classification result for {test_sample}: {result}")

结果输出

4、决策树的优缺点

优点：计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征数据。
缺点：可能会产生过度匹配问题。适用数据类型：数值型和标称型。

5、决策树的扩展与改进

待更新

6、参考文献

1、周志华.机器学习[M].清华大学出版社,2016.
2、美 哈林顿 Harrington, Peter.机器学习实战[M].人民邮电出版社,2013.