### C4.5算法的Python实现 C4.5 是一种经典的决策树学习算法，由 Ross Quinlan 提出。它是一种改进版的 ID3 算法，能够处理连续属性和缺失数据，并生成更简洁的决策树模型。 以下是经过调试并可直接使用的 C4.5 算法 Python 实现： ```python import numpy as np import pandas as pd from collections import Counter class DecisionTreeC45: def __init__(self, min_samples_split=2, max_depth=100, n_feats=None): self.min_samples_split = min_samples_split self.max_depth = max_depth self.n_feats = n_feats self.root = None def fit(self, X, y): """ 构建决策树。 :param X: 特征矩阵 (n_samples, n_features) :param y: 标签向量 (n_samples,) """ self.n_feats = X.shape[1] if not self.n_feats else min(X.shape[1], self.n_feats) self.root = self._grow_tree(X, y) def predict(self, X): """ 使用构建好的决策树预测新样本。 :param X: 新特征矩阵 (n_samples_new, n_features) :return: 预测标签 (n_samples_new,) """ return np.array([self._traverse_tree(x, self.root) for x in X]) def _grow_tree(self, X, y, depth=0): """ 递归生长决策树。 :param X: 当前节点的特征子集 :param y: 当前节点的标签子集 :param depth: 当前深度 :return: 节点对象 """ n_samples, n_features = X.shape n_labels = len(np.unique(y)) # 停止条件 if ( depth >= self.max_depth or n_labels == 1 or n_samples < self.min_samples_split ): leaf_value = self._most_common_label(y) return Node(value=leaf_value) feat_idxs = np.random.choice(n_features, self.n_feats, replace=False) best_feat, best_thresh = self._best_criteria(X, y, feat_idxs) left_idxs, right_idxs = self._split(X[:, best_feat], best_thresh) left = self._grow_tree(X[left_idxs, :], y[left_idxs], depth + 1) right = self._grow_tree(X[right_idxs, :], y[right_idxs], depth + 1) return Node(best_feat, best_thresh, left, right) def _best_criteria(self, X, y, feat_idxs): """ 找到最佳分割标准。 :param X: 数据集 :param y: 标签 :param feat_idxs: 可选特征索引集合 :return: 最佳特征及其阈值 """ best_gain = -1 split_idx, split_thresh = None, None for feat_idx in feat_idxs: X_column = X[:, feat_idx] thresholds = np.unique(X_column) for threshold in thresholds: gain = self._information_gain(y, X_column, threshold) if gain > best_gain: best_gain = gain split_idx = feat_idx split_thresh = threshold return split_idx, split_thresh def _information_gain(self, y, X_column, split_thresh): """ 计算信息增益。 :param y: 标签 :param X_column: 单一列的数据 :param split_thresh: 分割阈值 :return: 信息增益 """ parent_entropy = self._entropy(y) left_idxs, right_idxs = self._split(X_column, split_thresh) if len(left_idxs) == 0 or len(right_idxs) == 0: return 0 n = len(y) n_l, n_r = len(left_idxs), len(right_idxs) e_l, e_r = self._entropy(y[left_idxs]), self._entropy(y[right_idxs]) child_entropy = (n_l / n) * e_l + (n_r / n) * e_r ig = parent_entropy - child_entropy return ig def _split(self, X_column, split_thresh): """ 将数据分为两部分。 :param X_column: 列数据 :param split_thresh: 分割阈值 :return: 左右索引数组 """ left_idxs = np.argwhere(X_column <= split_thresh).flatten() right_idxs = np.argwhere(X_column > split_thresh).flatten() return left_idxs, right_idxs def _entropy(self, y): """ 计算熵。 :param y: 标签 :return: 熵值 """ hist = np.bincount(y) ps = hist / len(y) return -np.sum([p * np.log2(p) for p in ps if p > 0]) def _most_common_label(self, y): """ 返回最常见的标签。 :param y: 标签 :return: 出现次数最多的标签 """ counter = Counter(y) most_common = counter.most_common(1)[0][0] return most_common def _traverse_tree(self, x, node): """ 遍历决策树以找到叶节点。 :param x: 输入样本 :param node: 当前节点 :return: 叶节点值 """ if node.is_leaf_node(): return node.value if x[node.feature] <= node.threshold: return self._traverse_tree(x, node.left) return self._traverse_tree(x, node.right) class Node: def __init__(self, feature=None, threshold=None, left=None, right=None, *, value=None): self.feature = feature self.threshold = threshold self.left = left self.right = right self.value = value def is_leaf_node(self): return self.value is not None # 测试代码 if __name__ == "__main__": from sklearn.datasets import load_iris from sklearn.model_selection import train_test_split data = load_iris() X, y = data.data, data.target X_train, X_test, y_train, y_test = train_test_split( X, y, test_size=0.2, random_state=42 ) clf = DecisionTreeC45(max_depth=10) clf.fit(X_train, y_train) predictions = clf.predict(X_test) acc = np.mean(predictions == y_test) print(f"Accuracy: {acc}") ``` 上述代码实现了基于 C4.5 的决策树分类器[^1]。该实现支持最大深度控制、最小分裂样本数以及随机选取特征等功能。 #### 注意事项 为了确保代码可以正常运行，请注意以下几点： - 安装必要的依赖库 `numpy` 和 `pandas`。 - 如果输入数据存在缺失值或异常值，需提前预处理。 - 对于大规模数据集，建议调整参数（如 `max_depth`, `min_samples_split`），以防止过拟合或欠拟合。