- +在此添加单个AI新笔记
决策树 - 算法实现 - 决策树的代码实现
决策树 - 算法实现 - 决策树的代码实现
一、引言
决策树是一种常用的机器学习算法，它可以用于分类和回归任务。决策树的核心思想是通过对数据集的特征进行划分，构建一个树形结构，从而实现对样本的分类或预测。本文将详细介绍决策树的代码实现过程，帮助读者深入理解和掌握这一重要算法。
二、决策树的基本原理
决策树由节点和边组成。节点分为内部节点和叶节点，内部节点表示一个特征上的测试，边表示测试输出，叶节点表示类别或值。决策树的构建过程就是不断选择最优特征进行划分，直到满足停止条件。常用的划分准则有信息增益、信息增益比、基尼指数等。
信息增益
信息增益是基于信息熵的概念。信息熵是衡量数据不确定性的指标，信息增益表示划分前后信息熵的减少量。信息增益越大，说明该特征对分类的贡献越大。信息熵的计算公式为：
[H(D) = -\sum{k = 1}^{K}p{k}\log{2}p{k}]
其中，$D$ 是数据集，$K$ 是类别数，$p_{k}$ 是第 $k$ 类样本在数据集中所占的比例。
信息增益的计算公式为：
[g(D, A) = H(D) - H(D|A)]
其中，$A$ 是特征，$H(D|A)$ 是在特征 $A$ 给定的条件下数据集 $D$ 的条件熵。
三、代码实现步骤
1. 导入必要的库
import numpy as npimport pandas as pd
2. 计算信息熵
def entropy(y):classes, counts = np.unique(y, return_counts=True)probabilities = counts / len(y)entropy_value = -np.sum(probabilities * np.log2(probabilities))return entropy_value
3. 划分数据集
def split_dataset(X, y, feature_index, value):left_X = X[X[:, feature_index] == value]left_y = y[X[:, feature_index] == value]right_X = X[X[:, feature_index]!= value]right_y = y[X[:, feature_index]!= value]return left_X, left_y, right_X, right_y
4. 计算信息增益
def information_gain(X, y, feature_index):parent_entropy = entropy(y)total_samples = len(y)unique_values = np.unique(X[:, feature_index])weighted_entropy = 0for value in unique_values:left_X, left_y, right_X, right_y = split_dataset(X, y, feature_index, value)prob = len(left_y) / total_samplesweighted_entropy += prob * entropy(left_y) + (1 - prob) * entropy(right_y)return parent_entropy - weighted_entropy
5. 选择最优特征
def best_feature(X, y):num_features = X.shape[1]best_info_gain = 0best_feature_index = -1for i in range(num_features):info_gain = information_gain(X, y, i)if info_gain > best_info_gain:best_info_gain = info_gainbest_feature_index = ireturn best_feature_index
6. 创建决策树
def create_tree(X, y, feature_names):if len(np.unique(y)) == 1:return np.unique(y)[0]if X.shape[1] == 0:return np.bincount(y).argmax()best_feature_index = best_feature(X, y)best_feature_name = feature_names[best_feature_index]tree = {best_feature_name: {}}unique_values = np.unique(X[:, best_feature_index])new_feature_names = feature_names.copy()new_feature_names.remove(best_feature_name)for value in unique_values:left_X, left_y, right_X, right_y = split_dataset(X, y, best_feature_index, value)subtree = create_tree(left_X, left_y, new_feature_names)tree[best_feature_name][value] = subtreereturn tree
7. 使用示例
# 示例数据集data = {'Outlook': ['Sunny', 'Sunny', 'Overcast', 'Rain', 'Rain', 'Rain', 'Overcast', 'Sunny', 'Sunny', 'Rain', 'Sunny', 'Overcast', 'Overcast', 'Rain'],'Temperature': ['Hot', 'Hot', 'Hot', 'Mild', 'Cool', 'Cool', 'Cool', 'Mild', 'Cool', 'Mild', 'Mild', 'Mild', 'Hot', 'Mild'],'Humidity': ['High', 'High', 'High', 'High', 'Normal', 'Normal', 'Normal', 'High', 'Normal', 'Normal', 'Normal', 'High', 'Normal', 'High'],'Wind': ['Weak', 'Strong', 'Weak', 'Weak', 'Weak', 'Strong', 'Strong', 'Weak', 'Weak', 'Weak', 'Strong', 'Strong', 'Weak', 'Strong'],'Play': [0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0]}df = pd.DataFrame(data)X = df.iloc[:, :-1].valuesy = df.iloc[:, -1].valuesfeature_names = df.columns[:-1].tolist()# 创建决策树tree = create_tree(X, y, feature_names)print(tree)
四、代码解释
- entropy 函数：计算数据集的信息熵。
- split_dataset 函数：根据指定特征和特征值划分数据集。
- information_gain 函数：计算指定特征的信息增益。
- best_feature 函数：选择信息增益最大的特征。
- create_tree 函数：递归构建决策树。
五、总结
本文通过详细的代码实现，介绍了决策树的构建过程。决策树是一种直观、易于理解的机器学习算法，适用于多种类型的数据。通过信息增益等划分准则，可以有效地选择最优特征，构建出高效的决策树模型。
| 函数名 | 功能 |
|---|---|
| entropy | 计算信息熵 |
| split_dataset | 划分数据集 |
| information_gain | 计算信息增益 |
| best_feature | 选择最优特征 |
| create_tree | 创建决策树 |
通过上述代码和解释，读者可以更好地理解决策树的工作原理，并能够根据实际需求进行修改和扩展。