一、决策树基本概念

决策树是一种树形结构，由节点和边组成。节点包括内部节点和叶节点，内部节点表示一个特征上的测试，边表示测试输出的分支，叶节点表示类别或值。例如，在一个判断水果是苹果还是橙子的决策树中，可能内部节点是颜色测试，如果颜色是红色，可能有分支指向其他特征测试（如形状）或者直接指向叶节点 “苹果”。

1.决策树的结构

1. 根节点：是决策树的起始点，它包含了整个数据集，决策树从这里开始对数据进行划分。在这个节点上，根据一定的规则（如信息增益、基尼指数等）选择一个特征来对数据进行首次分割。例如，在预测一个人是否会购买某产品的决策树中，根节点可能基于 “年龄” 这个特征开始对所有客户数据进行划分。
2. 内部节点：除根节点外，内部节点代表对一个特征的测试。每个内部节点都对应一个特征，根据该特征的不同取值，将数据划分到不同的分支上。比如在上述购买产品的例子中，一个内部节点可能是对 “收入” 这个特征的测试，将客户按照不同的收入区间划分到不同的分支。每个内部节点都通过一定的准则（如最大化信息增益等）来确定选择哪个特征进行测试。
3. 叶节点：也称为终端节点，是决策树的结束点。叶节点不再进行特征测试，每个叶节点都对应一个类别标签（在分类问题中）或一个数值（在回归问题中）。例如，在分类问题中，叶节点可能表示 “会购买产品” 或 “不会购买产品”；在回归问题中，叶节点可能表示预测的产品价格数值。

2.决策树的组成

    1.分支：连接各个节点的边，代表从一个节点到另一个节点的路径。每个分支对应着某个特征的一个特定取值或取值范围，数据根据在节点上的特征测试结果，沿着相应的分支从根节点流向叶节点。

    2.特征：用于对数据进行划分的属性或变量。在决策树的构建过程中，需要从众多的特征中选择出对分类或回归任务最有帮助的特征，来决定在每个内部节点上进行何种测试。例如在判断水果是苹果还是橙子的决策树中，颜色、形状、大小等都可以作为特征。

    3.阈值：在每个内部节点上，针对选定的特征，会有一个用于划分数据的阈值。当特征的值大于或小于这个阈值时，数据会被分配到不同的分支。例如，以年龄为特征划分人群是否购买某产品，可能设定年龄大于 30 岁为一个分支，小于等于 30 岁为另一个分支，这里 30 岁就是阈值。

    4.类别或值：这是决策树的输出结果。在分类问题中，叶节点对应着不同的类别，如 “是”“否”，或者具体的类别名称，如 “苹果”“橙子” 等；在回归问题中，叶节点对应着一个具体的数值，如预测的房价、温度等。

二.信息论

信息论是一门研究信息的量化、传输、存储和处理的学科，为决策树中特征选择等提供了理论依据。以下是信息论的一些基础概念：

1.信息熵

     定义：信息熵是用来衡量一个随机变量不确定性的度量。对于一个离散型随机变量X，其取值为x1​,x2​,⋯,xn​，对应的概率分别为p(x1​),p(x2​),⋯,p(xn​)，则信息熵H(X)的计算公式为H(X)=−∑i=1n​p(xi​)log2​p(xi​)。信息熵的值越大，说明随机变量的不确定性越高。

      示例：在抛一枚均匀硬币的试验中，结果有正面和反面两种，且概率均为0.5，根据信息熵公式可得H(X)=−(0.5log2​0.5+0.5log2​0.5)=1比特。若硬币不均匀，正面概率为0.8，反面概率为0.2，则H(X)=−(0.8log2​0.8+0.2log2​0.2)≈0.72比特。可见，均匀硬币结果的不确定性更大，信息熵更高。

2.条件熵

      定义：在已知随机变量Y的条件下，随机变量X的不确定性的度量称为条件熵，记为H(X∣Y)。其计算公式为H(X∣Y)=−∑y∈Y​p(y)∑x∈X​p(x∣y)log2​p(x∣y)，它表示在给定Y的取值后，X的信息熵的期望。

3.信息增益

      定义：信息增益是指在一个特征给定的情况下，信息熵的减少量。它是衡量一个特征对于分类任务重要性的指标。对于数据集D和特征A，信息增益IG(D,A)=H(D)−H(D∣A)，其中H(D)是数据集D的信息熵，H(D∣A)是在特征A给定的条件下数据集D的条件熵。信息增益越大，说明该特征对分类的贡献越大，越适合作为决策树的划分特征。

三.决策树的算法

1.ID3 算法

算法原理：以信息熵为基础，通过计算每个特征的信息增益来选择划分属性，从根节点开始，递归地构建决策树。

特征选择指标：信息增益。信息增益越大，说明该特征对分类的贡献越大，越适合作为划分特征。

树的生成过程：从根节点开始，计算所有特征的信息增益，选择信息增益最大的特征作为根节点的划分特征，然后按照该特征的不同取值将数据集划分为不同的子集，对每个子集递归地重复上述过程，直到子集的类别完全相同或没有可划分的特征为止。

导入库

import numpy as np
import pandas as pd
from sklearn.preprocessing import LabelEncoder
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier
from sklearn.metrics import accuracy_score

定义ID3算法的决策树类：

class ID3DecisionTree:
    def __init__(self):
        self.tree = None

    def fit(self, X, y):
        data = np.column_stack((X, y))
        self.tree = self._build_tree(data)

    def _build_tree(self, data):
        labels = data[:, -1]
        if len(np.unique(labels)) == 1:
            return labels[0]
        if data.shape[1] == 1:
            return np.bincount(labels.astype(int)).argmax()
        best_feature_index = self._choose_best_feature(data)
        best_feature_values = np.unique(data[:, best_feature_index])
        tree = {best_feature_index: {}}
        for value in best_feature_values:
            sub_data = data[data[:, best_feature_index] == value]
            sub_data = np.delete(sub_data, best_feature_index, axis=1)
            tree[best_feature_index][value] = self._build_tree(sub_data)
        return tree

    def _choose_best_feature(self, data):
        num_features = data.shape[1] - 1
        base_entropy = self._calc_entropy(data[:, -1])
        best_info_gain = 0
        best_feature_index = -1
        for i in range(num_features):
            feature_values = np.unique(data[:, i])
            new_entropy = 0
            for value in feature_values:
                sub_data = data[data[:, i] == value]
                prob = sub_data.shape[0] / float(data.shape[0])
                new_entropy += prob * self._calc_entropy(sub_data[:, -1])
            info_gain = base_entropy - new_entropy
            if info_gain > best_info_gain:
                best_info_gain = info_gain
                best_feature_index = i
        return best_feature_index

    def _calc_entropy(self, labels):
        unique_labels, counts = np.unique(labels, return_counts=True)
        probabilities = counts / len(labels)
        entropy = -np.sum(probabilities * np.log2(probabilities))
        return entropy

    def predict(self, X):
        predictions = []
        for sample in X:
            prediction = self._classify(self.tree, sample)
            predictions.append(prediction)
        return np.array(predictions)

    def _classify(self, tree, sample):
        feature_index = list(tree.keys())[0]
        sub_tree = tree[feature_index]
        value = sample[feature_index]
        if value in sub_tree:
            if isinstance(sub_tree[value], dict):
                return self._classify(sub_tree[value], sample)
            else:
                return sub_tree[value]
        else:
            return np.bincount([v for v in sub_tree.values() if not isinstance(v, dict)]).argmax()

数据预处理：

label_encoders = {}
for column in df.columns:
    le = LabelEncoder()
    df[column] = le.fit_transform(df[column])
    label_encoders[column] = le

X = df.iloc[:, :-1].values
y = df.iloc[:, -1].values

使用ID3算法构建决策树：

id3_tree = ID3DecisionTree()
id3_tree.fit(X_train, y_train)
id3_predictions = id3_tree.predict(X_test)
id3_accuracy = accuracy_score(y_test, id3_predictions)
print(f"ID3算法准确率: {id3_accuracy}")

2.C4.5 算法

    算法原理：在 ID3 算法的基础上进行了改进，采用信息增益率作为特征选择指标，以克服 ID3 算法中倾向于选择取值较多特征的问题。

    特征选择指标：信息增益率。信息增益率通过在信息增益的基础上，除以该特征的固有值（特征取值的熵）来得到，它综合考虑了信息增益和特征取值的多样性。

    树的生成过程：与 ID3 算法类似，从根节点开始，计算所有特征的信息增益率，选择信息增益率最大的特征作为划分特征，然后递归地构建决策树。在构建过程中，对于连续型特征，C4.5 算法会先对其进行离散化处理；对于缺失值，也有相应的处理机制。

C4.5 算法是在 ID3 算法基础上进行改进，采用信息增益率来选择划分特征。

构建决策树：

class C45DecisionTree:
    def __init__(self):
        self.tree = None

    def fit(self, X, y):
        data = np.column_stack((X, y))
        self.tree = self._build_tree(data)

    def _build_tree(self, data):
        labels = data[:, -1]
        # 如果所有样本属于同一类别，返回该类别
        if len(np.unique(labels)) == 1:
            return labels[0]
        # 如果没有特征可划分，返回出现次数最多的类别
        if data.shape[1] == 1:
            return Counter(labels).most_common(1)[0][0]
        # 选择最佳划分特征
        best_feature_index = self._choose_best_feature(data)
        best_feature_values = np.unique(data[:, best_feature_index])
        tree = {best_feature_index: {}}
        for value in best_feature_values:
            sub_data = data[data[:, best_feature_index] == value]
            sub_data = np.delete(sub_data, best_feature_index, axis=1)
            tree[best_feature_index][value] = self._build_tree(sub_data)
        return tree

计算熵：_calc_entropy 方法用于计算数据集的熵：

 def _calc_entropy(self, labels):
        unique_labels, counts = np.unique(labels, return_counts=True)
        probabilities = counts / len(labels)
        entropy = -np.sum(probabilities * np.log2(probabilities))
        return entropy

预测：

    def predict(self, X):
        predictions = []
        for sample in X:
            prediction = self._classify(self.tree, sample)
            predictions.append(prediction)
        return np.array(predictions)

    def _classify(self, tree, sample):
        feature_index = list(tree.keys())[0]
        sub_tree = tree[feature_index]
        value = sample[feature_index]
        if value in sub_tree:
            if isinstance(sub_tree[value], dict):
                return self._classify(sub_tree[value], sample)
            else:
                return sub_tree[value]
        else:
            return Counter([v for v in sub_tree.values() if not isinstance(v, dict)]).most_common(1)[0][0]
 

数据预处理，将类别型数据转换为数值型：

    for column in df.columns:
        df[column] = pd.Categorical(df[column]).codes

    X = df.iloc[:, :-1].values
    y = df.iloc[:, -1].values

    model = C45DecisionTree()
    model.fit(X, y)
    predictions = model.predict(X)
    print("预测结果:", predictions)
    

3.CART 算法（分类与回归树）

    算法原理：既可以用于分类任务，也可以用于回归任务。在分类时，采用基尼指数来选择划分特征；在回归时，采用平方误差来衡量划分的好坏。

四.总结

决策树是机器学习领域中极具代表性的有监督学习算法，在数据处理与决策分析中应用广泛。其基本结构由根节点、内部节点和叶节点构成，通过节点间的分支连接，实现对数据的逐步划分与决策 。组成要素包含特征、划分条件、决策规则等，这些要素共同决定了决策树的分类或回归逻辑。

在算法层面，ID3、C4.5 和 CART 是常见的决策树算法。ID3 以信息增益为特征选择指标，理论简洁但易倾向选择取值多的特征；C4.5 采用信息增益率，克服了 ID3 的部分缺陷，能处理连续型特征和缺失值；CART 算法则使用基尼指数（分类）或平方误差（回归），生成二叉树，应用灵活且计算效率较高。

从应用角度，决策树既能解决分类问题，如邮件分类、疾病诊断，也能处理回归问题，如房价预测。通过编写代码，可实现不同算法构建决策树，在训练后对测试集进行预测并计算准确率，以评估模型性能。