基于ID3算法和后剪枝的决策树实验

机器学习决策树

机器学习要求使用一个六属性，1000条数据的car数据集建立决策树，这里记录手搓决策树代码实现以及一些性能度量和个人感悟。

一、实验结论

决策树（未剪枝）

这里是使用自己的决策树建立方法建立的决策树，在训练集占比为0.8并且分层划分决策树中第一轮生成的决策树的可视化图像。这张图片中的决策树并未使用剪枝算法，但是由于使用信息增益建树，而在建树过程中就写了逻辑如果信息增益为0就直接划分成叶节点，所以这里也算是进行了一个小小的预剪枝，所以树枝并不会完全划分六个属性。

决策树（剪枝，信息增益阈值设置0.2）

使用后剪枝方法对已经生成的决策树进行剪枝，剪枝按照信息增益来设置,如果信息增益低于某个设定好的阈值，就会将改属性改成叶节点，叶节点的选择按照原本属性划分中最多的标记数赋值，并且使用递归剪枝，能够多层剪枝，这里图像输出时设置的剪枝阈值为0.2，所以减去了较多分支，生成的决策树也比较简单。

决策树（sklearn库方法）

不同数据集分层划分，获得四个标记的查准率，查全率，准确率，F1以及平均值曲线

观察上图，0.8划分的性能中，使用sklearn输出pr曲线

使用sklearn对性能进行评测。
图一是使用sklearn随机划分训练集测试集，后剪枝后生成的决策树。
图二是根据不同的训练集划分占比，计算分层抽样生成决策树10次平均的查准率，查全率，F 1，准确度，以及这几者平均值的曲线
图三是找到性能最好的训练集划分比例，绘制出的pr曲线

二、具体实现

1.信息增益建树

树节点定义

记录本节点的分类属性，本节点的具体值，标记值，以及该节点的子节点

class Node:
    def __init__(self, attribute=None, value=None, label=None):
        self.attribute = attribute
        self.value = value
        self.label = label
        self.children = {}

信息熵计算

从数据集里读取最后一列的标记，然后计数总共有多少标记，之后通过公式计算返回信息熵。

def entropy(data):
    labels = [row[-1] for row in data]
    label_counts = Counter(labels)
    entropy = 0
    for label in label_counts:
        label_prob = label_counts[label] / len(labels)
        entropy += -label_prob * math.log2(label_prob)
    return entropy

信息增益计算

根据给定的属性计算数据集的信息增益。数据集和属性作为参数。根据属性的索引找到数据集中对应的属性列。然后，提取该属性列中的不同取值,然后开始计算信息熵，获得信息熵之后，用原本的信息熵减去以这个属性划分之后的信息熵。

def information_gain(data, attribute):
    attribute_index = attribute_names.index(attribute)
    attribute_values = set([row[attribute_index] for row in data])
    subset_entropy = 0
    for value in attribute_values:
        subset = [row for row in data if row[attribute_index] == value]
        subset_entropy += len(subset) / len(data) * entropy(subset)
    return entropy(data) - subset_entropy

建树

检查标签列表中是否只有一个唯一的标签值。如果是，则创建一个叶节点，将该标签值作为节点的标签.

如果属性列表为空，则计算标签列表中出现频率最高的标签，并创建叶节点，返回该节点作为树的一个分支。

选择最佳属性，使用信息增益函数计算得到的。信息增益越大，意味着选择该属性可以使得样本的分类更加纯净.创建节点，将最佳属性作为节点的属性，根据最佳属性在数据集中的位置，提取该属性的所有可能取值，并遍历每个取值.针对每个取值，根据属性值将数据集分割为子集。如果子集为空，说明该取值在当前属性下没有样本，创建一个叶节点，并将出现频率最高的标签作为节点的标签。如果子集不为空，说明该取值在当前属性下有样本。创建一个新的属性列表，移除最佳属性，剩下的属性存储在 remaining_attributes 列表中。

之后递归调用。

def build_tree(data, attributes):
    labels = [row[-1] for row in data]
    if len(set(labels)) == 1:
        return Node(label=labels[0])
    if len(attributes) == 0:
        majority_label = Counter(labels).most_common(1)[0][0]
        return Node(label=majority_label)
    best_attribute = max(attributes, key=lambda attr: information_gain(data, attr))
    node = Node(attribute=best_attribute)
    attribute_index = attribute_names.index(best_attribute)
    attribute_values = set([row[attribute_index] for row in data])
    for value in attribute_values:
        subset = [row for row in data if row[attribute_index] == value]
        if len(subset) == 0:
            majority_label = Counter(labels).most_common(1)[0][0]
            node.children[value] = Node(label=majority_label)
        else:
            remaining_attributes = [attr for attr in attributes if attr != best_attribute]
            node.children[value] = build_tree(subset, remaining_attributes)
    return node

2.后剪枝

生成决策树后，设置信息增益阈值剪枝。

首先检查当前节点是否有子节点，如果没有子节点，则直接返回。在遍历完所有子节点后，计算当前节点的信息增益，判断当前节点的子节点的标签是否一致，或者当前节点的信息增益是否小于设定的阈值。如果子节点的标签一致或者信息增益小于阈值，则进行剪枝操作。将当前节点的所有子节点合并为一个叶节点，该叶节点的标签值为当前节点子节点中出现频率最高的标签值。

Nodes before pruning: 45, Nodes after pruning: 27
Nodes before pruning: 87, Nodes after pruning: 76
Nodes before pruning: 130, Nodes after pruning: 86
Nodes before pruning: 161, Nodes after pruning: 161
Nodes before pruning: 171, Nodes after pruning: 110
Nodes before pruning: 187, Nodes after pruning: 187
Nodes before pruning: 191, Nodes after pruning: 191
Nodes before pruning: 230, Nodes after pruning: 230
Nodes before pruning: 239, Nodes after pruning: 239

这里每个输出是按照不同的训练集比例划分，比例为
可以看到随着训练集比例不断增加，建立的树节点也越多，剪枝剪去的节点数目也越多。而训练集比例越大，节点越多，也越不好剪枝，因为拆出来的训练数据纯度也会越低。

def postorder_prune(node):
        if not node.children:
            return        
        for child in node.children.values():
            postorder_prune(child)
        node.gain = information_gain(validation_data, node.attribute)
        if is_label_consistent(node, validation_data) or node.gain <= gain_threshold:
            merge_subtree(node)   
    num_nodes_before_pruning = count_nodes(tree)
    postorder_prune(tree)
    num_nodes_after_pruning = count_nodes(tree)
    print(f"Nodes before pruning: {num_nodes_before_pruning}, Nodes after pruning: {num_nodes_after_pruning}")

合并函数

def merge_subtree(node):
       node.label = Counter([row[-1] for row in validation_data]).most_common(1)[0][0]
       node.children = {}

3.可视化

检查当前节点是否为叶节点。

• 是，将当前节点添加到图中，标签为取值。

• 否，将当前节点添加到图中，标签为属性。

• 添加从当前节点到子节点的有向边，边的标签为子节点的取值。

递归调用”visualize_tree”函数，将子节点作为参数，以便绘制子节点的子树。最后返回绘制完成的图。

def visualize_tree(node, graph=None):
    if graph is None:
        graph = graphviz.Digraph()   
    if node.label is not None:
        graph.node(str(id(node)), label=node.label, shape='box')
    else:
        graph.node(str(id(node)), label=node.attribute)    
    for value, child in node.children.items():
        if child.label is not None:
            graph.node(str(id(child)), label=child.label, shape='box')
        else:
            graph.node(str(id(child)), label=child.attribute)
        graph.edge(str(id(node)), str(id(child)), label=value)
        visualize_tree(child, graph)   
    return graph

4.评估决策树

1.分层抽样

使用sklearn库函数 StratifiedShuffleSplit，对数据集的划分进行分层抽样和交叉验证。

sss = StratifiedShuffleSplit(n_splits=num_train, test_size=0.2, random_state=0)

2.交叉验证

使用sklearn库中StratifiedShuffleSplit的split方法，交叉验证的迭代，在每次迭代中，将数据集划分为训练集和测试集的索引。

之后就正常的按照索引划分数据集，建立决策树，然后计算性能指标，最后算出平均值。由于上面调用函数的时候num_train是10，所以会进行十次洗牌划分数据集，相当于计算十次建树最后得到的性能指标的平均值。

for train_index, test_index in sss.split(X, y):
    train_data = data[train_index]
    test_data = data[test_index]
    tree = build_tree(train_data, attribute_names)
    post_pruning(tree, validation_data=test_data, gain_threshold=0.01)
    y_true, y_pred = get_classification_results(tree, test_data)
    precision = precision_score(y_true, y_pred, average='macro')
    recall = recall_score(y_true, y_pred, average='macro')
    f1_score = f1_score(y_true, y_pred, average='macro')
    accuracy = accuracy_score(y_true, y_pred)
    precision_list.append(precision)
    recall_list.append(recall)
    f1_score_list.append(f1_score)
    accuracy_list.append(accuracy)
avg_precision = np.mean(precision_list)
avg_recall = np.mean(recall_list)
avg_f1_score = np.mean(f1_score_list)
avg_accuracy = np.mean(accuracy_list)

3.性能指标计算公式

正常遍历测试集，获得决策树对测试集的预测结果，根据结果计算预测正确错误的相关标记个数。根据这些个数计算查准率，查全率，f1,和正确性。

for i, instance in enumerate(test_data):
       predicted_label = classify_instance(instance, tree)
       actual_label = instance[-1]
       if predicted_label == actual_label:
           true_positives += 1
       else:
           if predicted_label is not None:
               false_positives += 1
           else:
               false_negatives += 1
   
   precision = true_positives / (true_positives + false_positives)
   recall = true_positives / (true_positives + false_negatives)
   f1_score = 2 * (precision * recall) / (precision + recall)
   accuracy = true_positives / test_size

4.性能图像

为了观测不同训练集与测试集划分比例对结构的影响，设置不同划分比例，之后输出性能图像，获得如下图像。该图像为十次洗牌按照训练集0.8，分层划分数据集，得到的查准率，查全，准确，f1和四者平均值的的曲线图。

train_ratios = [0.1,0.2,0.3,0.4,0.5,0.6, 0.7, 0.8, 0.9]
results = []
for train_ratio in train_ratios:
    precision, recall, f1_score, accuracy = evaluate_decision_tree(data, attribute_names, train_ratio)
    results.append((train_ratio, precision, recall, f1_score, accuracy))

根据图像可以得知，当训练集占0.8时，得到的决策树性能平均表现较好，所以后续选择测试在训练集占比0.8时，尝试画出pr曲线图。

5.pr曲线图

由于决策树是一个多分类问题，于是还需要对测试集进行多分类标签二进制化，然后调用precision_recall_curve这个函数，对测试集正确结果和预测结果进行匹配，计算出查准率，查全率等等，然后绘制图像。得到的图像如上图，然后再计算出折线面积，输出不同属性的pr曲线面积，根据面积评判决策树性能。

y_pred = tree_classifier.predict(X_test)
y_test_bin = label_binarize(y_test, classes=tree_classifier.classes_)
precision = dict()
recall = dict()
n_classes = len(tree_classifier.classes_)
for i in range(n_classes):
    precision[i], recall[i], _ = precision_recall_curve(y_test_bin[:, i], tree_classifier.predict_proba(X_test)[:, i])

label_binarize 将多分类标签转换为二进制形式。
例如，如果有三个类别 [A, B, C]，那么对于每个样本的标签 [A, B, C, A]，经过 label_binarize 处理后，会转换为二进制形式的数组 [[1, 0, 0], [0, 1, 0], [0, 0, 1], [1, 0, 0]]，其中每一行表示一个样本的标签是否属于对应类别。

for i in range(n_classes):
    plt.plot(recall[i], precision[i], marker='o', label=tag[i])
    area_i = precision[i].mean() * recall[i].mean()
    areas.append(area_i) 
    plt.text(0.5, 0.05*(i+1), f'Area({tag[i]}): {area_i:.2f}', fontsize=10) 

可以看到这里的pr图，能够大概反应pr图像趋势，整体来看，表现最好的是nacc和acc ,其次才是good和vgood，大概分布是符合数据集中的数据分布的。

三、小组性能指标对比

这里获得四种策略最佳性能表现对应的训练集&验证集划分比例

也可以看到随着训练集占比不断增加，决策树整体性能是越来越好的，但性能变化梯度在不断减小，在0.8与0.9之间，性能可能会略有下降。我们认为训练集越多，训练的数据越完善，并且剪枝的概率也会相应减小，于是决策树拥有更多节点准确预测，但是当训练集过多，有些数据对节点的加入帮助并不大，所以梯度会降低，并且训练数据过多可能会出现过拟合的现象。

• unacc 基尼后>ID3预>基尼预>ID3后
• acc ID3后>基尼后>信息预>基尼预
• good 基尼后>Id3预>Id3后>基尼预
• vgood ID3预>ID3后>基尼后>基尼预

在尽量控制其他变量相同，发挥基尼指数、信息增益、预剪枝、后剪枝算法排列组合最好性能的时候，输出他们各自pr曲线，按照曲线的面积大小对获得的结果进行排序分析。我们小组认为
后剪枝的表现比预剪枝稍好，由于其在生成完整的决策树之后再剪枝，能够充分利用数据集。
而ID3的表现也比基尼指数划分属性表现稍好，二者都属于贪心策略建树，但是信息增益使用log函数，其梯度变化更加符合实际过程中的数据趋势。但ID3的计算对比基尼指数也更为复杂，实际应用中因做出取舍。

四、实验收获

整体实验完成之后，对决策树的理解更加深入，尤其是递归算法，通过递归算法建树，后剪枝什么的。并且对查准率，查全率，f1和准确率的计算更加熟悉，之前看机器学习论文，在介绍完实现之后都会有一个章节介绍测试结果，当时对这种评价指标没有很多的理解，但是这次实验做完对于机器学习算法评价函数的必要性有很大的认识。