机器学习——决策树（DT）原理，ID3算法、C4.5算法python实现案例_id3 python

目录

一、决策树简介

二、决策树构建

2.1构建方法

   2.2.1  ID3算法

   2.2.2  C4.5算法

   2.2.3  CART算法

2.2决定树的停止条件

2.3决策树剪枝

三、Python实现案例

创建数据集：

3.1  ID3算法

3.2  C4.5算法：

四、总结

---

一、决策树简介

         决策树是一种基于树状结构的机器学习算法，用于分类和回归任务。它通过一系列简单的问题或条件，逐步将数据集划分到不同的类别或值。每个内部节点表示一个特征/属性，每个分支代表一个可能的特征值，而每个叶节点表示一个类别或值。

        决策树易于理解和解释，适用于小型到中等规模的数据集，并且能够处理具有非线性关系的数据。常见的决策树算法包括ID3、C4.5、CART等。

二、决策树构建

2.1构建方法

   2.2.1  ID3算法

ID3（Iterative Dichotomiser 3）算法是由 Ross Quinlan 在 1986 年提出的，是一种基于信息增益的决策树构建算法。该算法通过选择能够产生最大信息增益的特征来进行节点的分裂，直到所有的数据点都属于同一类别或者达到了预定的停止条件，是决策树的一个经典的构造算法，内部使用：信息熵，信息增益，来进行构建：每次迭代选择信息最大的特征属性作为分割属性。
在ID3算法中：

1.节点纯度的度量用 “信息熵”

2.分裂特征的选择用的是信息增益度作为衡量指标

3.信息熵越低——确定性越高——有序——数据越纯

4.信息增益——以A特征分割后,信息熵减少的越多，那就以为和Gain越大，说明分裂后信息的信息熵更低，数据更纯。

信息熵（Entropy）计算公式：

信息条件熵（Conditional Entropy）计算公式：

信息增益（Information Gain）计算公式：

   2.2.2  C4.5算法

C4.5算法是ID3算法的改进版本，由 Ross Quinlan 在 1993 年提出。相比于ID3，C4.5算法使用信息增益比来选择特征，这使得它能够更好地处理具有不同数目属性值的特征。此外，C4.5还可以处理连续特征和缺失值。

相比于ID3，C4.5算法：

1.使用信息增益率来取代ID3算法中的信息增益,

2.在树的构造过程中会进行剪枝操作进行优化

3.能够自动完成对连续属性的离散化处理（可以对连续特征进行分裂）

4.C4.5构建的是多分支的决策树;

5.C4.5算法在选中分割属性的时候选择信息增益率最大的属性

信息增益率计算公式：

   2.2.3  CART算法

CART(classification and regression tree)，分类回归树，它既可以用来解决分类问题也可以用来解决回归问题。

划分标准：使用使得gini系数最小的那个属性来划分样本。

基尼系数：（Gini不纯度）表示在样本集合中一个随机选中的样本被分错的概率。

注意：Gini系数越小表示集合中被选中的样本被分错的概率越小，也就是说集合的纯度越高，反之，集合越不纯。当集合中所有样本只有一个类时，基尼系数为0.

基尼指数计算公式：

对于CART算法：

1.CART与C4.5算法是非常相似的，但是CART支持预测连续的值（即回归）。

2.CART构建二叉树，而C4.5则不一定。显然由于二叉树的原因使得CART5不会出现ID3的问题（倾向于选择属性值多的属性来划分样本）

3.CART用训练集和交叉验证集不断地评估决策树的性能来修剪决策树，从而使训练误差和测试误差达到一个很好地平衡点。

2.2.4三种算法总结对比:

1. ID3、C4.5和CART算法均只适合在小规模数据集上使用
2. ID3、C4.5和CART算法都是单变量决策树
3. 当属性值取值比较多的时候，最好考虑C4.5算法，ID3得出的效果会比较差
4. 决策树分类一般情况只适合小数据量的情况(数据可以放内存)
5. CART算法是三种算法中最常用的一种决策树构建算法**(sklearn中仅支持CART：构造出来的是二叉树)
        三种算法的区别仅仅只是对于当前树的评价标准不同而已，ID3使用信息增益、C4.5使用信息增益率、CART使用基尼系数。

2.2决定树的停止条件

       在构建决策树时，需要设定一些条件来决定何时停止树的生长，以防止过拟合。常见的停止条件包括节点中的样本数量小于阈值、树的深度达到预设值或者信息增益小于阈值等。

2.3决策树剪枝

       剪枝即是删除一些最不可靠的分枝，用多个类的叶节点代替，以加快分类的速度和提高决策树正确分类新数据的能力。常用的剪枝方法有预剪枝和后剪枝:

预剪枝就是提早结束决策树的构造过程，通过选取一个阈值判断树的构造是否停止，因为适当的阈值很难界定，所以预剪枝存在危险，不能保证树的可靠性;

后剪枝是在决策树构造完毕后得到一棵完整的树再进行剪枝，通常的思想是对每个树节点进行错误估计，通过与其子树的错误估计的比较，来判断子树的裁剪，如果子树的错误估计较大，则被剪枝，最后用一个独立的测试集去评估剪枝后的准确率，以此得到估计错误率最小的决策树。

三、Python实现案例

创建数据集：

# 创建示例数据集
dataset = [
    ['青年', '否', '否', '一般', '否'],
    ['青年', '否', '否', '好', '否'],
    ['青年', '是', '否', '好', '是'],
    ['青年', '是', '是', '一般', '是'],
    ['青年', '否', '否', '一般', '否'],
    ['中年', '否', '否', '一般', '否'],
    ['中年', '否', '否', '好', '否'],
    ['中年', '是', '是', '好', '是'],
    ['中年', '否', '是', '非常好', '是'],
    ['中年', '否', '是', '非常好', '是'],
    ['老年', '否', '是', '非常好', '是'],
    ['老年', '否', '是', '好', '是'],
    ['老年', '是', '否', '好', '是'],
    ['老年', '是', '否', '非常好', '是'],
    ['老年', '否', '否', '一般', '否']
]

3.1  ID3算法

import numpy as np
 
def entropy(y):
    # 统计每个类别的出现次数
    _, counts = np.unique(y, return_counts=True)
    # 计算信息熵
    probabilities = counts / len(y)
    entropy = -np.sum(probabilities * np.log2(probabilities))
    return entropy
def find_best_split(X, y):
    best_entropy = np.inf
    best_feature_idx = None
    best_threshold = None
    
    # 对每个特征进行遍历
    for feature_idx in range(X.shape[1]):
        thresholds = np.unique(X[:, feature_idx])
        # 对每个可能的阈值进行遍历
        for threshold in thresholds:
            left_indices = np.where(X[:, feature_idx] <= threshold)[0]
            right_indices = np.where(X[:, feature_idx] > threshold)[0]
            
            # 计算左右子集的信息熵
            left_entropy = entropy(y[left_indices])
            right_entropy = entropy(y[right_indices])
            
            # 计算加权信息熵
            weighted_entropy = (len(left_indices) / len(y)) * left_entropy + \
                                (len(right_indices) / len(y)) * right_entropy
            
            # 如果加权信息熵小于当前最优值，则更新最优值
            if weighted_entropy < best_entropy:
                best_entropy = weighted_entropy
                best_feature_idx = feature_idx
                best_threshold = threshold
    
    return best_feature_idx, best_threshold
class Node:
    def __init__(self, predicted_class):
        self.predicted_class = predicted_class
        self.feature_index = 0
        self.threshold = 0
        self.left = None
        self.right = None
 
def build_tree(X, y):
    # 如果所有样本属于同一类别，则返回叶节点
    if len(set(y)) == 1:
        return Node(predicted_class=y[0])
    
    # 如果样本中只剩下一个特征，则返回叶节点，预测类别为样本中最频繁出现的类别
    if X.shape[1] == 1:
        return Node(predicted_class=np.bincount(y).argmax())
    
    # 寻找最优划分特征及阈值
    best_feature_idx, best_threshold = find_best_split(X, y)
    
    # 根据最优划分特征和阈值划分数据集
    left_indices = np.where(X[:, best_feature_idx] <= best_threshold)[0]
    right_indices = np.where(X[:, best_feature_idx] > best_threshold)[0]
    
    # 如果划分后的数据集为空，则返回叶节点，预测类别为样本中最频繁出现的类别
    if len(left_indices) == 0 or len(right_indices) == 0:
        return Node(predicted_class=np.bincount(y).argmax())
    
    # 递归构建左子树和右子树
    left_subtree = build_tree(X[left_indices], y[left_indices])
    right_subtree = build_tree(X[right_indices], y[right_indices])
    
    # 创建当前节点
    node = Node(predicted_class=None)
    node.feature_index = best_feature_idx
    node.threshold = best_threshold
    node.left = left_subtree
    node.right = right_subtree
    
    return node
def predict(node, sample):
    if node.predicted_class is not None:
        return node.predicted_class
    
    if sample[node.feature_index] <= node.threshold:
        return predict(node.left, sample)
    else:
        return predict(node.right, sample)
 
def test(tree, X_test):
    predictions = []
    for sample in X_test:
        predictions.append(predict(tree, sample))
    return predictions
# 将数据集转换为数组
dataset_array = np.array(dataset)
X = dataset_array[:, :-1]  # 特征
y = dataset_array[:, -1]   # 标签
 
# 构建决策树
tree = build_tree(X, y)
 
# 测试数据
test_data = [
    ['青年', '否', '否', '一般'],
    ['老年', '是', '否', '好'],
    ['中年', '否', '是', '非常好']
]
 
# 进行预测
predictions = test(tree, test_data)
# 进行测试并输出结果
print("测试数据:")
for i, data in enumerate(test_data):
    print(f"样本 {i+1}: {data}，预测结果: {predictions[i]}")
 
# 计算准确率
ground_truth = ['否', '是', '是']  # 测试数据的真实标签
correct_predictions = sum(1 for true, pred in zip(ground_truth, predictions) if true == pred)
accuracy = correct_predictions / len(ground_truth) * 100
print(f"\n准确率: {accuracy:.2f}%")

运行结果：

3.2  C4.5算法：

计算数据集的熵：

# 计算数据集在某个特征上的条件熵
def calculate_conditional_entropy(data, feature_index):
    feature_values = set([row[feature_index] for row in data])
    conditional_entropy = 0
    for value in feature_values:
        subset = [row for row in data if row[feature_index] == value]
        prob = len(subset) / len(data)
        conditional_entropy += prob * calculate_entropy(subset)
    return conditional_entropy

计算数据集在某个特征上的条件熵：

# 计算数据集在某个特征上的条件熵
def calculate_conditional_entropy(data, feature_index):
    feature_values = set([row[feature_index] for row in data])
    conditional_entropy = 0
    for value in feature_values:
        subset = [row for row in data if row[feature_index] == value]
        prob = len(subset) / len(data)
        conditional_entropy += prob * calculate_entropy(subset)
    return conditional_entropy

计算信息增益：

def calculate_information_gain(data, feature_index):
    entropy = calculate_entropy(data)
    conditional_entropy = calculate_conditional_entropy(data, feature_index)
    information_gain = entropy - conditional_entropy
    return information_gain

选择最佳划分特征：

def choose_best_feature(data):
    num_features = len(data[0]) - 1
    best_feature_index = -1
    best_information_gain = 0
    for i in range(num_features):
        information_gain = calculate_information_gain(data, i)
        if information_gain > best_information_gain:
            best_information_gain = information_gain
            best_feature_index = i
    return best_feature_index

递归构建决策树：

# 递归构建决策树
def build_decision_tree(data, features):
    labels = [row[-1] for row in data]
    # 如果所有实例都属于同一类别，则返回该类别
    if len(set(labels)) == 1:
        return labels[0]
    # 如果没有特征可用或者数据集为空，则返回出现次数最多的类别
    if len(data) == 0 or len(features) == 0:
        return max(set(labels), key=labels.count)
    # 选择最佳划分特征
    best_feature_index = choose_best_feature(data)
    best_feature = features[best_feature_index]
    decision_tree = {best_feature: {}}
    # 删除已选特征
    del(features[best_feature_index])
    feature_values = set([row[best_feature_index] for row in data])
    for value in feature_values:
        subset = [row for row in data if row[best_feature_index] == value]
        decision_tree[best_feature][value] = build_decision_tree(subset, features[:])
    return decision_tree

测试决策树模型：

# 测试决策树模型
def predict(decision_tree, instance):
    if isinstance(decision_tree, dict):
        root = list(decision_tree.keys())[0]
        subtree = decision_tree[root]
        root_index = feature_names.index(root)
        root_value = instance[root_index]
        if root_value in subtree:
            return predict(subtree[root_value], instance)
        else:
            return "Unknown"
    else:
        return decision_tree
 
# 测试数据集
test_data = [
    ['青年', '否', '否', '一般'],
    ['中年', '是', '是', '好'],
    ['老年', '否', '是', '好']
]
 
# 特征名称
feature_names = ['年龄', '有工作', '有自己的房子', '信贷情况']
 
# 构建决策树
decision_tree = build_decision_tree(dataset, feature_names[:])
 
# 输出决策树
print("决策树：", decision_tree)
 
# 测试决策树模型
for instance in test_data:
    prediction = predict(decision_tree, instance)
    print("测试实例:", instance, " 预测结果:", prediction)

运行结果：

---

四、总结

        作为机器学习中的一大类模型，树模型一直以来都颇受学界和业界的重视。目前无论是各大比赛各种大杀器的XGBoost、lightgbm、还是像随机森林、AdaBoost等典型集成学习模型，都是以决策树模型为基础的。传统的经典决策树算法包括ID3算法、C4.5算法以及GBDT的基分类器CART算法。

        三大经典决策树算法最主要的区别是其特征选择的准则不同。ID3算法选择特征的依据是信息增益、C4.5是信息增益比，而CART则是基尼指数。作为一种基础的分类和回归方法，决策树可以有以下两种理解方法：可以认为是if-then的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。

        决策树学习算法通常是一个递归地选择最优特征， 并根据该特征对训练数据进行分割，使得对各个子数据集有一个最好的分类的过程。这一过程对应着对特征空间的划分，也对应着决策树的构建。开始，构建根结点，将所有训练数据都放在根结点。选择一个最优特征，按照这一特征将训练数据集分割成子集，使得各个子集有一个在当前条件下最好的分类。如果这些子集已经能够被基本正确分类，那么构建叶结点，并将这些子集分到所对应的叶结点中去，如果还有子集不能被基本正确分类，那么就对这些子集选择新的最优特征，继续对其进行分割，构建相应的结点。如此递归地进行下去，直至所有训练数据子集被基本正确分类，或者没有合适的特征为止。最后每个子集都被分到叶结点上，即都有了明确的类。这就生成了一棵决策树。