本文介绍决策树（Decision Tree）算法在机器学习中的基本原理、特点、注意事项，以及如何从零实现决策树模型的完整步骤。
1. 决策树算法的基本原理
决策树是一种树状结构的监督学习算法，用于分类和回归任务。它通过学习决策规则，从数据中建立模型，以对目标变量进行预测。
1.1 树结构
决策树由节点和边构成，其中：
- 根节点：没有输入边的节点。
- 内部节点：包含一个测试条件，根据特征对样本进行分裂。
- 叶节点：输出预测结果，不再分裂。
1.2 划分标准
在决策树中，选择最佳特征和分裂点以最大化信息增益或基尼不纯度。
1.2.1 信息增益
信息增益衡量在选择某个特征后，数据集不确定性的减少程度。其公式为：
\[\text{信息增益}(D, A) = H(D) - \sum_{v \in \text{values}(A)} \frac{|D_v|}{|D|} H(D_v)\]其中，( H(D) ) 为熵，衡量数据集 ( D ) 的不确定性。
1.2.2 基尼不纯度
基尼不纯度用于衡量样本的混杂程度，公式为：
\[Gini(D) = 1 - \sum_{k=1}^{n} p_k^2\]其中，( p_k ) 为类别 ( k ) 的样本比例。
1.3 类别选择
通过递归地选择最优分裂特征和阈值构建树，直至达到停止条件：
- 所有样本属于同一类别。
- 样本数小于预设阈值。
- 达到最大树深度。
1.4 特点和注意事项
- 易于理解和解释：直观地展现特征对预测的影响。
- 处理多种数据类型：可处理数值和类别特征。
- 容易过拟合：树过于复杂时可能对训练数据拟合得过于紧密。
2. 实现步骤
我们使用 iris 数据集进行决策树的实现。
2.1 数据准备
加载数据集，分割训练集和测试集。
import numpy as np
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score, confusion_matrix, classification_report
# 加载iris数据集
data = load_iris()
X = data.data # 特征数据
y = data.target # 目标标签
# 将数据集分为训练集和测试集，80%用于训练，20%用于测试
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)
2.2 模型训练
实现决策树算法。
class DecisionTree:
def __init__(self, max_depth=None):
self.max_depth = max_depth
self.tree = None
def fit(self, X, y):
self.tree = self._grow_tree(X, y)
def _grow_tree(self, X, y, depth=0):
num_samples_per_class = [np.sum(y == i) for i in np.unique(y)]
predicted_class = np.argmax(num_samples_per_class)
node = {
'predicted_class': predicted_class
}
if depth < self.max_depth:
idx, threshold = self._best_split(X, y)
if idx is not None:
indices_left = X[:, idx] < threshold
X_left, y_left = X[indices_left], y[indices_left]
X_right, y_right = X[~indices_left], y[~indices_left]
node['feature_index'] = idx
node['threshold'] = threshold
node['left'] = self._grow_tree(X_left, y_left, depth + 1)
node['right'] = self._grow_tree(X_right, y_right, depth + 1)
return node
def _best_split(self, X, y):
m, n = X.shape
if m <= 1:
return None, None
num_parent = [np.sum(y == c) for c in np.unique(y)]
best_gini = 1.0 - sum((n / m) ** 2 for n in num_parent)
best_idx, best_thr = None, None
for idx in range(n):
thresholds, classes = zip(*sorted(zip(X[:, idx], y)))
num_left = [0] * len(num_parent)
num_right = num_parent.copy()
for i in range(1, m):
c = classes[i - 1]
num_left[c] += 1
num_right[c] -= 1
gini_left = 1.0 - sum(
(num_left[x] / i) ** 2 for x in range(len(num_parent))
)
gini_right = 1.0 - sum(
(num_right[x] / (m - i)) ** 2 for x in range(len(num_parent))
)
gini = (i * gini_left + (m - i) * gini_right) / m
if thresholds[i] == thresholds[i - 1]:
continue
if gini < best_gini:
best_gini = gini
best_idx = idx
best_thr = (thresholds[i] + thresholds[i - 1]) / 2
return best_idx, best_thr
def predict(self, X):
return [self._predict(inputs) for inputs in X]
def _predict(self, inputs):
node = self.tree
while 'threshold' in node:
if inputs[node['feature_index']] < node['threshold']:
node = node['left']
else:
node = node['right']
return node['predicted_class']
2.3 模型预测
对测试集进行预测。
# 创建决策树模型
dt = DecisionTree(max_depth=3)
# 训练模型
dt.fit(X_train, y_train)
# 预测测试集
y_pred = dt.predict(X_test)
2.4 模型评估
使用测试数据集评估模型性能。
accuracy = accuracy_score(y_test, y_pred)
conf_matrix = confusion_matrix(y_test, y_pred)
class_report = classification_report(y_test, y_pred)
print("\nAccuracy:", accuracy)
print("Confusion Matrix:\n", conf_matrix)
print("Classification Report:\n", class_report)
3. 优缺点
3.1 优点
- 直观性：模型易于解释和可视化。
- 灵活性：可用于分类和回归任务。
- 无需特征缩放：不要求特征缩放和归一化。
3.2 缺点
- 过拟合风险：复杂树结构容易过拟合训练数据。
- 对噪声敏感：对数据中的小变化敏感，可能影响树的结构。
决策树是一种灵活和易于理解的算法，在很多应用中都非常有效。然而，过拟合是一个常见问题，因此通常结合集成方法（如随机森林和梯度提升树）使用以提升性能。
