ID3决策树算法实战：如何高效分类未知样本

1次阅读

共计 3594 个字符，预计需要花费 9 分钟才能阅读完成。

决策树算法是机器学习中常用的分类方法，它通过树形结构对数据进行分类或回归。ID3（Iterative Dichotomiser 3）是决策树算法的一种，由 Ross Quinlan 在 1986 年提出。它主要用于处理离散型特征，通过信息增益选择最佳分裂属性，构建决策树。

ID3 算法的特点包括：

易于理解和解释，生成的树形结构直观
可以处理多分类问题
对噪声数据有一定的鲁棒性
倾向于选择取值较多的属性

信息熵是度量样本集合纯度的指标，熵越小说明样本纯度越高。计算公式为：

Entropy(D) = -Σ(p_k * log2(p_k))

其中，D 是样本集合，p_k 是第 k 类样本所占比例。

信息增益表示使用某个特征进行划分后，信息熵的减少量。ID3 算法选择信息增益最大的特征作为当前节点的分裂特征。计算公式为：

Gain(D, A) = Entropy(D) - Σ(|D_v|/|D| * Entropy(D_v))

其中，A 是某个特征，D_v 是特征 A 取值为 v 的子集。

所有特征必须是离散型
处理缺失值（删除或填充）
数据需要转换为数值形式

计算当前数据集的信息熵
对每个特征计算信息增益
选择信息增益最大的特征作为分裂节点
对每个特征值创建分支，递归构建子树
终止条件：
所有样本属于同一类别
没有剩余特征可分
分支下样本数为 0

从根节点开始
根据样本特征值选择对应分支
递归遍历直到叶节点
返回叶节点的类别标签

import numpy as np
from collections import Counter

class TreeNode:
    """决策树节点类"""
    def __init__(self, feature=None, value=None, results=None, children=None):
        self.feature = feature  # 分裂特征
        self.value = value      # 特征值
        self.results = results  # 叶节点的类别分布
        self.children = children or {}  # 子节点

class ID3DecisionTree:
    """ID3 决策树实现"""

    def __init__(self, max_depth=None):
        self.max_depth = max_depth
        self.root = None

    def _entropy(self, y):
        """计算信息熵"""
        counts = np.bincount(y)
        probs = counts / len(y)
        return -np.sum([p * np.log2(p) for p in probs if p > 0])

    def _information_gain(self, X, y, feature_idx):
        """计算信息增益"""
        parent_entropy = self._entropy(y)

        # 按特征值分组
        unique_values = np.unique(X[:, feature_idx])
        child_entropy = 0

        for value in unique_values:
            mask = X[:, feature_idx] == value
            child_y = y[mask]
            if len(child_y) > 0:
                prob = len(child_y) / len(y)
                child_entropy += prob * self._entropy(child_y)

        return parent_entropy - child_entropy

    def _choose_best_feature(self, X, y, feature_indices):
        """选择最佳分裂特征"""
        best_gain = -1
        best_feature = None

        for feature_idx in feature_indices:
            gain = self._information_gain(X, y, feature_idx)
            if gain > best_gain:
                best_gain = gain
                best_feature = feature_idx

        return best_feature

    def _build_tree(self, X, y, feature_indices, depth=0):
        """递归构建决策树"""
        # 终止条件
        if len(np.unique(y)) == 1:
            return TreeNode(results=Counter(y))

        if len(feature_indices) == 0:
            return TreeNode(results=Counter(y))

        if self.max_depth and depth >= self.max_depth:
            return TreeNode(results=Counter(y))

        # 选择最佳分裂特征
        best_feature = self._choose_best_feature(X, y, feature_indices)
        if best_feature is None:
            return TreeNode(results=Counter(y))

        # 创建节点
        node = TreeNode(feature=best_feature)
        remaining_features = [f for f in feature_indices if f != best_feature]

        # 递归构建子树
        for value in np.unique(X[:, best_feature]):
            mask = X[:, best_feature] == value
            X_subset = X[mask]
            y_subset = y[mask]

            if len(y_subset) == 0:
                node.children[value] = TreeNode(results=Counter(y))
            else:
                node.children[value] = self._build_tree(X_subset, y_subset, remaining_features, depth + 1)

        return node

    def fit(self, X, y):
        """训练决策树"""
        self.root = self._build_tree(X, y, list(range(X.shape[1])))

    def predict(self, X):
        """预测样本类别"""
        return np.array([self._predict_sample(x) for x in X])

    def _predict_sample(self, x):
        """预测单个样本"""
        node = self.root
        while node.results is None:
            value = x[node.feature]
            if value in node.children:
                node = node.children[value]
            else:
                break

        if node.results:
            return max(node.results.items(), key=lambda x: x[1])[0]
        else:
            return None

# 示例数据
X_train = np.array([[1, 1],  # 晴天, 高温
    [1, 1],  # 晴天, 高温
    [2, 1],  # 阴天, 高温
    [3, 2],  # 雨天, 中温
    [3, 3],  # 雨天, 低温
    [3, 2],  # 雨天, 中温
    [2, 3],  # 阴天, 低温
    [1, 2],  # 晴天, 中温
])

y_train = np.array([0, 0, 1, 1, 1, 0, 1, 0])  # 0: 不去, 1: 去

# 构建决策树
tree = ID3DecisionTree()
tree.fit(X_train, y_train)

# 预测未知样本
X_test = np.array([[1, 2],  # 晴天, 中温
    [3, 1]   # 雨天, 高温
])

predictions = tree.predict(X_test)
print(f"预测结果: {predictions}")  # 输出: [0 1]

ID3 算法的时间复杂度主要取决于：