资源站 wordpress,wordpress修改主页模板,做venn图的网站,网站模板带手机站C4.5决策树是一种广泛使用的机器学习算法#xff0c;它用于分类任务。它是在ID3算法的基础上改进的#xff0c;主要通过生成决策树来构建分类模型。C4.5通过以下步骤工作#xff1a;
1. 数据集分裂
C4.5通过选择具有最高信息增益率的特征来分裂数据集。信息增益率#xf…C4.5决策树是一种广泛使用的机器学习算法它用于分类任务。它是在ID3算法的基础上改进的主要通过生成决策树来构建分类模型。C4.5通过以下步骤工作
1. 数据集分裂
C4.5通过选择具有最高信息增益率的特征来分裂数据集。信息增益率Gain Ratio是在决策树构建过程中用于选择最优分裂特征的度量标准。它是基于信息增益进行的改进旨在解决信息增益偏向于取值较多的属性的问题。具体实现信息增益率需要以下几个步骤
1. 计算数据集的熵Entropy
熵用于衡量数据集的纯度或混乱度。假设数据集 ( S (S (S) 中有 ( n (n (n) 类那么熵 ( E n t r o p y ( S ) (Entropy(S) (Entropy(S)) 的计算公式为 E n t r o p y ( S ) − ∑ i 1 n p i log 2 ( p i ) Entropy(S) - \sum_{i1}^{n} p_i \log_2(p_i) Entropy(S)−i1∑npilog2(pi) 其中 ( p i (p_i (pi) 是第 ( i (i (i) 类在数据集 ( S (S (S) 中出现的概率。
熵越高数据集的混乱度越高熵越低数据集越接近纯净。
2. 计算信息增益Information Gain
信息增益度量的是某个属性 ( A (A (A) 在分裂数据集 ( S (S (S) 后带来的熵的减少。计算步骤如下 假设属性 ( A (A (A) 有 ( v (v (v) 个不同取值将数据集 ( S (S (S) 按照 ( A (A (A) 的不同取值划分为 ( v (v (v) 个子集 ( S 1 , S 2 , . . . , S v (S_1, S_2, ..., S_v (S1,S2,...,Sv)。 计算划分后数据集的条件熵 E n t r o p y ( S ∣ A ) ∑ j 1 v ∣ S j ∣ ∣ S ∣ E n t r o p y ( S j ) Entropy(S|A) \sum_{j1}^{v} \frac{|S_j|}{|S|} Entropy(S_j) Entropy(S∣A)j1∑v∣S∣∣Sj∣Entropy(Sj) 其中 ( ∣ S j ∣ (|S_j| (∣Sj∣) 是子集 ( S j (S_j (Sj) 中样本的数量 ( ∣ S ∣ (|S| (∣S∣) 是原始数据集的样本数量。 计算信息增益 G a i n ( S , A ) E n t r o p y ( S ) − E n t r o p y ( S ∣ A ) Gain(S, A) Entropy(S) - Entropy(S|A) Gain(S,A)Entropy(S)−Entropy(S∣A) 信息增益表示属性 ( A (A (A) 划分数据集后带来的熵的减少。信息增益越大意味着通过该属性的划分能让数据集变得更加纯净。
3. 计算分裂信息Split Information
分裂信息衡量的是属性 ( A (A (A) 划分数据集的固有不确定性。它的计算公式为 S p l i t I n f o ( A ) − ∑ j 1 v ∣ S j ∣ ∣ S ∣ log 2 ( ∣ S j ∣ ∣ S ∣ ) SplitInfo(A) - \sum_{j1}^{v} \frac{|S_j|}{|S|} \log_2\left(\frac{|S_j|}{|S|}\right) SplitInfo(A)−j1∑v∣S∣∣Sj∣log2(∣S∣∣Sj∣) 分裂信息越大表示属性 ( A (A (A) 的取值越多数据集的划分越细致。
4. 计算信息增益率Gain Ratio
信息增益率是在信息增益的基础上除以分裂信息来防止属性值过多的偏倚。公式为 G a i n R a t i o ( A ) G a i n ( S , A ) S p l i t I n f o ( A ) Gain\ Ratio(A) \frac{Gain(S, A)}{SplitInfo(A)} Gain Ratio(A)SplitInfo(A)Gain(S,A) 信息增益率通过对信息增益进行归一化避免选择取值较多的属性如ID号、日期等导致的偏倚。最终在构建决策树时选择信息增益率最高的属性作为最优分裂属性。
5. 选择最优特征
在所有候选特征中计算每个特征的信息增益率并选择具有最大信息增益率的特征进行数据集划分。
例子
假设我们有一个小数据集 ( S (S (S) 包含水果分类问题属性 ( A (A (A) 可能是水果的颜色取值为红色、绿色、黄色等。在计算信息增益时属性颜色可能划分出多个子集红色的水果、绿色的水果等然后通过计算该划分带来的熵减少量得到信息增益。最终通过计算分裂信息得到信息增益率。这个过程会在所有候选属性上执行从而选择最佳分裂特征。
特点
1. 处理连续属性
C4.5可以处理连续属性。它通过计算属性的多个分裂点并找到能带来最大信息增益率的分裂点来处理数值型数据。例如它可以把数值型属性转换为“ 某个阈值”和“ 某个阈值”的二元划分。
2. 处理缺失值
C4.5能够处理数据集中存在缺失值的情况。它通过估算该特征对分类的贡献进行处理而不是简单地删除缺失数据。
3. 剪枝Pruning
决策树的一个问题是容易过拟合。C4.5通过后剪枝方法来减少树的复杂性从而提高泛化能力。剪枝通过在构建树后删除那些对分类贡献较小的分支来实现。
总结
C4.5通过使用信息增益率来选择最优的分裂特征能够处理连续值和缺失值并通过后剪枝来防止过拟合。这使得它比ID3更加灵活和实用尤其在复杂的实际应用中。
全部代码
import numpy as np
from collections import Counter
from TreeDisp import visualize_tree# 计算熵
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):left_indices X[:, feature_index] thresholdright_indices X[:, feature_index] thresholdreturn X[left_indices], X[right_indices], y[left_indices], y[right_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)return - (p_left * np.log2(p_left) p_right * np.log2(p_right))def Gain_Ratio(y, y_left, y_right):return information_gain(y, y_left, y_right)/Split_Information(y, y_left, y_right)# 选择最佳分裂点
def best_split(X, y):best_gain_ratio -1best_feature_index 0best_threshold 0n_features X.shape[1]for feature_index in range(n_features):thresholds np.unique(X[:, feature_index])for threshold in thresholds:X_left, X_right, y_left, y_right split_dataset(X, y, feature_index, threshold)if len(y_left) 0 or len(y_right) 0:continuegain_ratio Gain_Ratio(y, y_left, y_right)if gain_ratio best_gain_ratio:best_gain_ratio gain_ratiobest_feature_index feature_indexbest_threshold thresholdreturn best_feature_index, best_threshold# 构建决策树节点
class Node:def __init__(self, feature_indexNone, thresholdNone, leftNone, rightNone, valueNone):self.feature_index feature_index # 用于分裂的特征索引self.threshold threshold # 分裂点self.left left # 左子树self.right right # 右子树self.value value # 叶节点的值类标签# 递归构建决策树
def build_tree(X, y, depth0, max_depth10):n_samples, n_features X.shapen_labels len(np.unique(y))# 停止条件数据纯度高或达到最大深度if n_labels 1 or depth max_depth:leaf_value Counter(y).most_common(1)[0][0]return Node(valueleaf_value)# 找到最佳分裂点feature_index, threshold best_split(X, y)# 分裂数据集X_left, X_right, y_left, y_right 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.valuefeature_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_depth10):tree build_tree(X_train, y_train, max_depthmax_depth)dot_tree visualize_tree(tree, iris.feature_names)dot_tree.render(iris_tree_1, formatpng, cleanupTrue) # 将图保存为 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_train, X_test, y_train, y_test train_test_split(X, y, test_size0.3, random_state42)# 使用手动实现的决策树进行训练和预测
y_pred decision_tree_classifier(X_train, y_train, X_test, max_depth5)# 评估模型
accuracy accuracy_score(y_test, y_pred)
print(fAccuracy: {accuracy * 100:.2f}%)
