c45决策树算法python

### C4.5决策树算法的Python实现 C4.5是一种经典的分类算法，由Ross Quinlan开发。它基于ID3算法改进而来，能够处理连续属性并支持剪枝操作以减少过拟合[^1]。 以下是使用Python实现C4.5决策树的一个基本框架： #### 数据预处理 为了构建一棵决策树，数据集通常需要经过编码和标准化处理。对于类别型特征，可以将其转换为数值形式；而对于连续型变量，则需通过离散化或其他方法进行分割[^2]。 ```python import numpy as np from math import log def entropy(dataset): """计算给定数据集的经验熵""" num_entries = len(dataset) label_counts = {} for feat_vec in dataset: current_label = feat_vec[-1] if current_label not in label_counts.keys(): label_counts[current_label] = 0 label_counts[current_label] += 1 ent = 0.0 for key in label_counts: prob = float(label_counts[key]) / num_entries ent -= prob * log(prob, 2) return ent ``` 上述函数用于计算信息增益中的重要参数——经验熵[^3]。 #### 构建决策树的核心逻辑 下面展示的是如何递归地创建一颗完整的C4.5决策树结构： ```python def choose_best_feature_to_split(dataset): """选择最优划分特征""" num_features = len(dataset[0]) - 1 base_entropy = entropy(dataset) best_info_gain_ratio = 0.0 best_feature = -1 for i in range(num_features): unique_vals = set([example[i] for example in dataset]) new_entropy = 0.0 split_info = 0.0 for value in unique_vals: sub_dataset = split_dataset(dataset, i, value) prob = len(sub_dataset)/float(len(dataset)) new_entropy += prob * entropy(sub_dataset) split_info -= prob * log(prob, 2) info_gain = base_entropy - new_entropy if (split_info == 0): continue info_gain_ratio = info_gain / split_info if(info_gain_ratio > best_info_gain_ratio): best_info_gain_ratio = info_gain_ratio best_feature = i return best_feature def create_tree(dataset, labels): class_list = [example[-1] for example in dataset] if class_list.count(class_list[0]) == len(class_list): return class_list[0] if len(dataset[0]) == 1: return majority_vote(class_list) best_feat = choose_best_feature_to_split(dataset) best_feat_label = labels[best_feat] my_tree = {best_feat_label:{}} del(labels[best_feat]) feat_values = [example[best_feat] for example in dataset] unique_vals = set(feat_values) for value in unique_vals: sub_labels = labels[:] my_tree[best_feat_label][value] = create_tree(split_dataset\ (dataset,best_feat,value),sub_labels) return my_tree ``` 以上代码片段展示了如何利用信息增益率来选取最佳分裂节点，并逐步建立子树直至满足停止条件为止[^4]。 #### 测试模型性能 最后一步是对训练好的模型进行评估测试其泛化能力: ```python def classify(input_tree,feat_labels,test_vector): first_str = list(input_tree.keys())[0] second_dict = input_tree[first_str] feat_index = feat_labels.index(first_str) for key in second_dict.keys(): if test_vector[feat_index]==key: if type(second_dict[key]).__name__=='dict': class_label=classify(second_dict[key],feat_labels,test_vector) else:class_label=second_dict[key] return class_label ``` 此部分定义了一个简单的预测过程，输入待测样本向量即可得到对应的分类标签[^5]。

决策树是一种常用的分类算法，其中C4.5决策树算法是决策树的一种改进算法。下面是一个基于Python的C4.5决策树算法的实现示例： 首先，我们需要定义一个节点类，用于存储每个节点的信息和属性。 ```python class Node: def __init__(self, attribute=None, threshold=None, label=None, left=None, right=None): self.attribute = attribute # 属性名 self.threshold = threshold # 划分阈值 self.label = label # 叶子节点的类别 self.left = left # 左子节点 self.right = right # 右子节点 ``` 然后，我们需要定义一个C4.5决策树算法类，其中包含以下方法： 1. `__init__`：初始化决策树模型。 2. `entropy`：计算数据集的熵。 3. `conditional_entropy`：计算数据集在某个属性上的条件熵。 4. `information_gain`：计算信息增益。 5. `majority_vote`：统计数据集中出现最多的类别。 6. `build_tree`：构建决策树。 7. `predict`：预测新样本的类别。 ```python import numpy as np from collections import Counter class C45DecisionTree: def __init__(self, max_depth=5, min_samples_split=2): self.max_depth = max_depth # 最大深度 self.min_samples_split = min_samples_split # 最小分割样本数 def entropy(self, y): """计算数据集的熵""" counter = Counter(y) probs = [count / len(y) for count in counter.values()] return -sum(p * np.log2(p) for p in probs) def conditional_entropy(self, X, y, feature_idx, threshold): """计算数据集在某个属性上的条件熵""" left_mask = X[:, feature_idx] < threshold right_mask = X[:, feature_idx] >= threshold left_probs = len(y[left_mask]) / len(y) right_probs = len(y[right_mask]) / len(y) left_entropy = self.entropy(y[left_mask]) right_entropy = self.entropy(y[right_mask]) return left_probs * left_entropy + right_probs * right_entropy def information_gain(self, X, y, feature_idx, threshold): """计算信息增益""" parent_entropy = self.entropy(y) child_entropy = self.conditional_entropy(X, y, feature_idx, threshold) return parent_entropy - child_entropy def majority_vote(self, y): """统计数据集中出现最多的类别""" counter = Counter(y) most_common = counter.most_common(1) return most_common[0][0] def build_tree(self, X, y, depth=0): """构建决策树""" # 判断是否达到最大深度或最小分割样本数 if depth >= self.max_depth or len(y) < self.min_samples_split: return Node(label=self.majority_vote(y)) n_features = X.shape[1] best_feature, best_threshold, best_gain = None, None, 0 for feature_idx in range(n_features): # 计算每个属性的信息增益 thresholds = np.unique(X[:, feature_idx]) for threshold in thresholds: gain = self.information_gain(X, y, feature_idx, threshold) if gain > best_gain: best_feature, best_threshold, best_gain = feature_idx, threshold, gain # 判断是否需要划分 if best_gain > 0: left_mask = X[:, best_feature] < best_threshold right_mask = X[:, best_feature] >= best_threshold left_node = self.build_tree(X[left_mask], y[left_mask], depth + 1) right_node = self.build_tree(X[right_mask], y[right_mask], depth + 1) return Node(attribute=best_feature, threshold=best_threshold, left=left_node, right=right_node) # 无法划分，返回叶子节点 return Node(label=self.majority_vote(y)) def predict(self, X): """预测新样本的类别""" node = self.root while node.label is None: if X[node.attribute] < node.threshold: node = node.left else: node = node.right return node.label ``` 最后，我们可以使用该算法对一个数据集进行分类。 ```python # 导入数据集 from sklearn.datasets import load_iris iris = load_iris() X = iris.data y = iris.target # 构建决策树 model = C45DecisionTree(max_depth=5, min_samples_split=2) model.root = model.build_tree(X, y) # 对新样本进行分类 new_sample = [5.0, 3.6, 1.3, 0.25] label = model.predict(new_sample) print(label) ``` 以上代码输出结果为 `0`，表示该新样本属于第一类。