决策树C4.5如何处理缺省值

在有缺省数据的情况下，处理方式是影响模型准确性和性能的关键因素。C4.5算法在处理缺省数据（缺失值）方面提供了一个相对灵活和有效的方案，而这种处理方式也是它比ID3算法改进的一个重要方面。让我们深入探讨如何在数据集中考虑缺省数据，以及C4.5的具体实现方法。

一、缺省数据的常见处理策略

在处理缺失值时，一般有几种常见的策略：

1. 删除缺失数据:

   • 将包含缺失值的样本直接删除。
   • 优点：简单直接，适合少量缺失数据的情况。
   • 缺点：当缺失数据较多时，可能会丢失大量信息，影响模型性能。

2. 填补缺失值:

   • 使用某种策略填补缺失值，如用平均值、众数、中位数等来填充。
   • 优点：保留了样本数据。
   • 缺点：可能引入噪音或错误信息，影响模型的准确性。

3. 模型预测填补:

   • 使用回归或分类模型预测缺失值，然后填补数据。
   • 优点：相对较为精确。
   • 缺点：复杂度较高，需要构建额外的模型。

4. 不做处理，直接交给模型处理:

   • 一些算法（如C4.5）能够直接处理缺失值，无需删除或填充。

二、C4.5处理缺失值的方法

C4.5在构建决策树时，可以在有缺失值的情况下直接进行分裂，而不需要对数据进行删除或填补。它采用了概率估计的方法，根据已知样本的信息部分进行分裂和分类。C4.5的缺失值处理可以分为两部分：分裂时的处理 和 分类时的处理。

1. 分裂时处理缺失值:

当某个属性在样本中有缺失值时，C4.5不会简单地忽略这些样本，而是利用剩余的信息部分计算信息增益率。处理方式如下：

• 对属性选择计算信息增益率时：
  当在计算某个属性的熵时，如果某个样本的该属性缺失，C4.5会对这个样本进行加权处理。也就是说，它根据该样本在其余属性上的分布，给它一个概率权重，而不是简单地忽略这些样本。
  权重的计算：样本被分配到不同的分裂分支时，使用的权重是该样本可以落入某个分支的可能性。这种做法确保了即使有缺失值，分裂过程仍然可以顺利进行。

• 分裂后的样本处理：
  当一个属性用于分裂节点，而部分样本在该属性上有缺失值时，C4.5会根据已知样本分布将这些缺失值样本按照一定的权重分配到每个子节点中，而不是直接丢弃。这样，缺失值的影响被最小化，并且能够保留更多的信息。

2. 分类时处理缺失值:

当决策树训练完毕，用来对新样本进行分类时，如果新样本的某些属性缺失，C4.5也可以有效处理：

• 加权投票机制：
  在分类阶段，如果一个样本在某个节点的分裂属性上有缺失值，C4.5会通过“加权投票”的方式，将该样本分配到多个可能的子节点中。每个子节点的权重基于该节点上的已知样本的比例。然后，算法继续沿着各个子节点向下走，并根据这些分支的权重得出最终的分类决策。

3. C4.5的优势

相比其他方法（如删除样本或填补数据），C4.5的缺失值处理有几个显著优势：

• 灵活性高：不需要删除数据，也不需要对缺失值进行填补，能够直接处理含有缺失值的数据集。
• 保留数据完整性：通过加权分配样本到不同的子节点中，最大限度地利用了数据集中的每个样本，即使它有缺失值。
• 避免信息损失：通过加权估计的方式保留了每个样本的贡献，防止了简单删除样本或填补缺失值带来的信息损失。

三、C4.5处理缺失值的算法细节

假设我们有一个样本 (S)，其中有一些样本在特征 (A) 上缺失，C4.5在处理时的步骤：

1. 分裂时：

   • 计算信息增益率时，只用特征 (A) 非缺失的样本来计算。
   • 将缺失值样本按照其余已知属性的分布，按概率分配到每个可能的子节点中。

2. 分类时：

   • 若测试样本在分裂节点上的特征值缺失，将该样本根据训练集中已知样本的分布，按概率分配到所有可能的子节点中，并根据加权结果进行分类。

总结

C4.5通过加权的方式有效处理缺失值，无需删除或填补缺失数据。这种灵活性使得它在应对真实世界中的数据集时表现优越，因为真实数据往往存在一定的缺失信息。C4.5的这种策略既能最大限度利用样本信息，又能减少信息损失，确保决策树的泛化能力更强。

全部代码

import numpy as np
from collections import Counter
from TreeDisp import visualize_tree
import pandas as pd

# 计算熵
def entropy(y):
    counts = np.bincount(y)
    probabilities = counts / len(y)
    return -np.sum([p * np.log2(p) for p in probabilities if p > 0])


# 根据特征值划分数据集，考虑缺失值情况
def split_dataset(X, y, feature_index, threshold):
    known_indices = ~np.isnan(X[:, feature_index])
    missing_indices = np.isnan(X[:, feature_index])

    left_indices = X[:, feature_index] <= threshold
    right_indices = X[:, feature_index] > threshold

    return X[known_indices & left_indices], X[known_indices & right_indices], y[known_indices & left_indices], y[
        known_indices & right_indices], X[missing_indices], y[missing_indices]


# 计算信息增益
def information_gain(y, y_left, y_right):
    p_left = len(y_left) / len(y)
    p_right = len(y_right) / len(y)
    return entropy(y) - (p_left * entropy(y_left) + p_right * entropy(y_right))


# 计算分裂信息
def Split_Information(y, y_left, y_right):
    p_left = len(y_left) / len(y)
    p_right = len(y_right) / len(y)
    if p_left == 0 or p_right == 0:
        return 1  # 避免除以0错误
    return -(p_left * np.log2(p_left) + p_right * np.log2(p_right))


def Gain_Ratio(y, y_left, y_right):
    split_info = Split_Information(y, y_left, y_right)
    if split_info == 0:
        return 0
    return information_gain(y, y_left, y_right) / split_info


# 选择最佳分裂点，考虑缺失值
def best_split(X, y):
    best_gain_ratio = -1
    best_feature_index = 0
    best_threshold = 0
    n_features = X.shape[1]

    for feature_index in range(n_features):
        thresholds = np.unique(X[~np.isnan(X[:, feature_index]), feature_index])
        for threshold in thresholds:
            X_left, X_right, y_left, y_right, X_missing, y_missing = split_dataset(X, y, feature_index, threshold)
            if len(y_left) == 0 or len(y_right) == 0:
                continue

            # 加权处理缺失值样本
            weight_left = len(y_left) / (len(y_left) + len(y_right))
            weight_right = len(y_right) / (len(y_left) + len(y_right))

            y_left = np.concatenate([y_left, y_missing[:int(weight_left * len(y_missing))]])
            y_right = np.concatenate([y_right, y_missing[int(weight_left * len(y_missing)):]])

            gain_ratio = Gain_Ratio(y, y_left, y_right)
            if gain_ratio > best_gain_ratio:
                best_gain_ratio = gain_ratio
                best_feature_index = feature_index
                best_threshold = threshold

    return best_feature_index, best_threshold


# 构建决策树节点
class Node:
    def __init__(self, feature_index=None, threshold=None, left=None, right=None, value=None):
        self.feature_index = feature_index  # 用于分裂的特征索引
        self.threshold = threshold  # 分裂点
        self.left = left  # 左子树
        self.right = right  # 右子树
        self.value = value  # 叶节点的值（类标签）


# 递归构建决策树
def build_tree(X, y, depth=0, max_depth=10):
    n_samples, n_features = X.shape
    n_labels = len(np.unique(y))

    # 停止条件：数据纯度高或达到最大深度
    if n_labels == 1 or depth == max_depth:
        leaf_value = Counter(y).most_common(1)[0][0]
        return Node(value=leaf_value)

    # 找到最佳分裂点
    feature_index, threshold = best_split(X, y)

    # 分裂数据集
    X_left, X_right, y_left, y_right, X_missing, y_missing = split_dataset(X, y, feature_index, threshold)

    # 构建左、右子树
    left_subtree = build_tree(X_left, y_left, depth + 1, max_depth)
    right_subtree = build_tree(X_right, y_right, depth + 1, max_depth)

    return Node(feature_index, threshold, left_subtree, right_subtree)


# 预测新样本，考虑缺失值
def predict(sample, tree):
    if tree.value is not None:
        return tree.value
    if np.isnan(sample[tree.feature_index]):  # 处理缺失值
        left_prediction = predict(sample, tree.left)
        right_prediction = predict(sample, tree.right)
        return left_prediction if np.random.rand() < 0.5 else right_prediction  # 随机选择一个分支
    feature_value = sample[tree.feature_index]
    if feature_value <= tree.threshold:
        return predict(sample, tree.left)
    else:
        return predict(sample, tree.right)


# 使用决策树模型进行训练和预测
def decision_tree_classifier(X_train, y_train, X_test, max_depth=10):
    tree = build_tree(X_train, y_train, max_depth=max_depth)
    dot_tree = visualize_tree(tree, iris.feature_names)
    dot_tree.render('iris_tree_with_missing_values', format='png', cleanup=True)  # 保存带缺失值的树为PNG
    predictions = [predict(sample, tree) for sample in X_test]
    return np.array(predictions)


# 测试手动实现的决策树
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score

# 加载数据集
iris = load_iris()
X = iris.data
y = iris.target



# 引入缺失值
X[np.random.randint(0, X.shape[0], 20), np.random.randint(0, X.shape[1], 20)] = np.nan

# 将数据转换为 DataFrame
df = pd.DataFrame(data=X, columns=iris.feature_names)
df['target'] = y

# 将 DataFrame 保存为 CSV 文件
df.to_csv(r"E:\MachineLearning\Data\Iris_NAN.csv", index=False)

# 划分训练集和测试集
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)

# 使用手动实现的决策树进行训练和预测
y_pred = decision_tree_classifier(X_train, y_train, X_test, max_depth=5)

# 评估模型
accuracy = accuracy_score(y_test, y_pred)
print(f'Accuracy with missing values: {accuracy * 100:.2f}%')