一、决策树简介

        1、决策树的概念

        所谓决策树，就是一个类似于流程图的树形结构。是一种常用的机器学习算法，用于建立预测模型和分类模型。它基于树状结构，通过分析数据特征与目标变量之间的关系，将数据集划分为不同的子集，以逐步构建决策规则。决策树模型具有直观的可解释性和易于理解的特点，因此在许多领域中被广泛应用。

        决策树的结构类似于一颗倒置的树，由节点和边组成。树的顶部被称为根节点，每个节点表示一个特征属性或判断条件。

        从根节点开始，根据不同的特征属性进行分支，直到叶节点，叶节点表示最终的预测结果。决策树的构建过程基于训练数据集。常见的构建算法有ID3、C4.5和CART等。算法通过选择最佳的特征属性来分裂节点，并根据特征属性的取值创建子节点。通过递归的方式，持续地将数据集划分为更小的子集，直到满足停止条件。

        在分类问题中，决策树的叶节点表示不同的类别，对于新的输入数据，通过遵循决策树的路径，可以确定其所属的类别。在回归问题中，叶节点表示一个数值，通过对应的路径可以得到预测的数值。

        2、决策树的优缺点

        优点：计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征数据；

        缺点：可能会产生过度匹配问题；

        适用数据类型：数值型和标称型；

        3、决策树结构

图1-1

                图1-1就是一个简单的决策树，用于判断一个人是否欠贷，其中有房者，婚姻，年收入这几个属性都是特征值，是否欠贷为标签值；

                最上方的椭圆是根节点（无入边，多出边），而下方的椭圆是内部节点（一入多出），方形代表叶子节点（一入无出）；

二、决策树的构建

        1、决策树构建的一般流程

                (1) 、收集数据：可以使用任何方法。
                (2) 、准备数据：树构造算法只是用于标称型数据，因此数值型数据必须离散化。
                (3) 、分析数据：可以使用任何方法，决策树构造完成后，可以检查决策树图形是否符合预期。
                (4) 、训练算法：构造一个决策树的数据结构。
                (5) 、测试算法：使用经验树计算错误率。当错误率达到可接收范围，此决策树就可投放使用。
                (6) 、使用算法：此步骤可以使用适用于任何监督学习算法，而使用决策树可以更好地理解数据的内在含义。

        2、划分选择最优属性

                在构建决策树的时候，通常数据集都会有很多个属性（特征值），因此我们需要通过一些衡量方法来判断哪个属性更适合作为根节点或内部节点。

        （1）、信息增益

        信息增益是一种用于衡量特征选择程度的度量指标，它衡量的是在选择某个特征作为节点进行分裂后，得到的子节点相较于父节点而言所获得的信息量的增加。

        在决策树中，信息是通过熵来衡量的。熵是对数据集纯度的度量，其值越高表示混乱度越大，纯度越低。而信息增益则是父节点熵与子节点熵之差，用于衡量特征选择后纯度的提高程度。

具体计算信息增益的步骤如下：

        a. 计算父节点的熵。将待划分的数据集中的各个类别按照频率计算出现的概率，然后利用公式计算父节点的熵。

        b.对每个特征进行划分，计算每个特征的条件熵。条件熵是在某个特征下划分后的子节点熵的加权平均值。首先，对每个特征的所有可能取值进行计数，并计算各个取值的概率，然后对于每个取值，将该取值下的样本划分为不同的子节点，计算每个子节点的熵，再进行加权平均得到条件熵。

        c.通过父节点的熵减去条件熵，得到信息增益。信息增益越大，表示特征选择后纯度的提高程度越高。

        假定当前样本集合D中第k类样本所占的比例为 pk (K=1, 2, ..., |y|)，则D的信息熵定义为：

        Ent(D)的值越小，则D的纯度越高

        对于决策树的构建过程，会不断选择信息增益最大的特征来进行分裂，直到达到预定的停止条件（如达到指定的树深度或子节点的样本数小于某个阈值）为止。

        需要注意的是，信息增益在处理具有大量类别的特征时可能会存在偏好问题，因为它倾向于选择具有更多取值的特征。

        （2）、增益率

        增益率是在信息增益的基础上引入了对特征取值数目的惩罚，用于解决信息增益偏好于具有更多取值的特征的问题。

其中

称为属性a的“固有值” ，属性a的可能取值数目越多（即V越大），则IV(a)的值通常就越大

增益率能够通过对特征取值数目的惩罚来平衡不同特征的选择。当一个特征有很多取值时，它可能会产生更多的划分，导致分裂信息较大，从而减少其增益率。因此，增益率更倾向于选择取值较少、能够更有效地划分数据集的特征。

        （3）、基尼指数

        基尼指数用于度量在某个节点上随机选择一个样本，其被错误分类到其他类别的概率。它的取值范围在0和1之间，0表示节点纯度最高（即所有样本都属于同一类别），而1表示节点纯度最低（即样本均匀分布在各个类别中）。

        在决策树算法中，我们会计算每个特征的基尼指数，并选择具有最小基尼指数的特征作为节点分割特征。通过不断地分割节点并降低基尼指数，我们可以逐步构建一棵具有高纯度的决策树模型。

三、决策树代码实现

        数据集

本次使用的是根据特征判断肿瘤是恶性或者良好的数据集

图3-1

        图3-1是部分数据集的截图

        决策树算法

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

class DecisionTree:
    def __init__(self, max_depth=None, min_samples_split=2, min_impurity_decrease=0):
        self.max_depth = max_depth                        # 决策树的最大深度
        self.min_samples_split = min_samples_split        # 分裂所需的最小样本数
        self.min_impurity_decrease = min_impurity_decrease# 分裂所需的最小不纯度下降值
        self.root = None                                  # 根节点

    def _impurity(self, y):
        '''计算数据集的不纯度'''
        n = len(y)
        if n == 0: return 0

        p0 = np.sum(y == 0) / n
        p1 = np.sum(y == 1) / n

        impurity = 0
        if p0 > 0: impurity -= p0 * np.log2(p0)
        if p1 > 0: impurity -= p1 * np.log2(p1)

        return impurity

    def _split(self, X, y):
        '''寻找最佳分裂点'''
        n_features = X.shape[1]
        best_feature, best_threshold, best_info_gain = None, None, -np.inf

        for i in range(n_features):
            thresholds = np.unique(X[:, i])
            for threshold in thresholds:
                mask = X[:, i] <= threshold
                y_left, y_right = y[mask], y[~mask]
                if len(y_left) < self.min_samples_split or len(y_right) < self.min_samples_split:
                    continue
                ig = self._impurity(y) - (len(y_left)*self._impurity(y_left) + len(y_right)*self._impurity(y_right)) / len(y)
                if ig > best_info_gain:
                    best_feature, best_threshold, best_info_gain = i, threshold, ig

        return best_feature, best_threshold, best_info_gain

    def _build_tree(self, X, y, depth):
        '''递归构建决策树'''
        node = Node()

        # 判断是否达到最大深度或者样本数过少
        if self.max_depth is not None and depth >= self.max_depth or len(y) < self.min_samples_split:
            node.value = np.argmax(np.bincount(y))
            return node

        # 找到最佳分裂点
        feature, threshold, info_gain = self._split(X, y)

        # 判断是否不纯度下降足够多
        if info_gain < self.min_impurity_decrease:
            node.value = np.argmax(np.bincount(y))
            return node
        
        node.feature = feature
        node.threshold = threshold
        node.info_gain = info_gain

        # 递归构建左右子树
        mask = X[:, feature] <= threshold
        node.left = self._build_tree(X[mask], y[mask], depth+1)
        node.right = self._build_tree(X[~mask], y[~mask], depth+1)

        return node

    def fit(self, X, y):
        '''训练模型'''
        self.root = self._build_tree(X, y, depth=0)

    def _predict_one(self, x, node):
        '''单个样本的预测'''
        if node.value is not None: # 到达叶节点
            return node.value
        if x[node.feature] <= node.threshold:
            return self._predict_one(x, node.left)
        else:
            return self._predict_one(x, node.right)

    def predict(self, X):
        '''批量样本的预测'''
        return np.array([self._predict_one(x, self.root) for x in X])

        训练

data = pd.read_csv('Prostate_Cancer.csv')

X = data.drop(['diagnosis_result'], axis=1).values
y = data['diagnosis_result'].values

X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

clf = DecisionTree()
clf.fit(X_train, y_train)

y_pred = clf.predict(X_test)

sample_data = X_train[-2]
sample_label = y_train[-2]

prediction = clf.predict([sample_data])[0]

# 绘制决策树
plt.figure(figsize=(10, 8))
def plot_tree(node, depth=0):
    if node is None:
        return
    if node.value is not None:
        print('  ' * depth, 'class:', node.value)
    else:
        print('  ' * depth, feature_names[node.feature], '<=', node.threshold, '(IG:', node.info_gain, ')')
        plot_tree(node.left, depth+1)
        plot_tree(node.right, depth+1)
plot_tree(clf.root)
plt.show()

        运行结果

四、实验小结

        本次实验学习到的决策树算法具有易于理解和解释、处理非线性关系、鲁棒性强等优点，但也存在容易过拟合、选择特征受限、对连续性变量不够友好等缺点。在使用决策树算法时需要对其优缺点进行充分的考虑，结合具体问题场景进行选择和调整。