1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
| import numpy as np
class TreeNode:
"""决策树节点"""
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
class DecisionTreeClassifier:
"""CART分类决策树（使用基尼指数）"""
def __init__(self, max_depth=10, min_samples_split=2):
"""
max_depth: 最大深度，防止过拟合
min_samples_split: 最小分裂样本数
"""
self.max_depth = max_depth
self.min_samples_split = min_samples_split
self.root = None
def gini_impurity(self, y):
"""
计算基尼不纯度: Gini = 1 - Σ(p_i^2)
值越小表示纯度越高
"""
_, counts = np.unique(y, return_counts=True)
probs = counts / len(y)
return 1 - np.sum(probs ** 2)
def entropy(self, y):
"""
计算信息熵: H = -Σ(p_i * log2(p_i))
用于ID3算法
"""
_, counts = np.unique(y, return_counts=True)
probs = counts / len(y)
return -np.sum(probs * np.log2(probs + 1e-10))
def split_data(self, X, y, feature, threshold):
"""根据特征和阈值分裂数据"""
left_mask = X[:, feature] <= threshold
right_mask = ~left_mask
X_left, y_left = X[left_mask], y[left_mask]
X_right, y_right = X[right_mask], y[right_mask]
return X_left, y_left, X_right, y_right
def find_best_split(self, X, y):
"""
找到最佳分裂点
遍历所有特征和所有可能的阈值
"""
best_gain = -1
best_feature = None
best_threshold = None
parent_gini = self.gini_impurity(y)
n_samples = len(y)
for feature in range(X.shape[1]):
thresholds = np.unique(X[:, feature])
for threshold in thresholds:
X_left, y_left, X_right, y_right = self.split_data(X, y, feature, threshold)
if len(y_left) == 0 or len(y_right) == 0:
continue
n_left, n_right = len(y_left), len(y_right)
gini_left = self.gini_impurity(y_left)
gini_right = self.gini_impurity(y_right)
weighted_gini = (n_left / n_samples) * gini_left + \
(n_right / n_samples) * gini_right
gain = parent_gini - weighted_gini
if gain > best_gain:
best_gain = gain
best_feature = feature
best_threshold = threshold
return best_feature, best_threshold, best_gain
def build_tree(self, X, y, depth=0):
"""
递归构建决策树
"""
n_samples, n_features = X.shape
n_classes = len(np.unique(y))
if depth >= self.max_depth or \
n_samples < self.min_samples_split or \
n_classes == 1:
leaf_value = np.bincount(y.astype(int)).argmax()
return TreeNode(value=leaf_value)
best_feature, best_threshold, best_gain = self.find_best_split(X, y)
if best_feature is None or best_gain <= 0:
leaf_value = np.bincount(y.astype(int)).argmax()
return TreeNode(value=leaf_value)
X_left, y_left, X_right, y_right = self.split_data(
X, y, best_feature, best_threshold
)
left_child = self.build_tree(X_left, y_left, depth + 1)
right_child = self.build_tree(X_right, y_right, depth + 1)
return TreeNode(
feature=best_feature,
threshold=best_threshold,
left=left_child,
right=right_child
)
def fit(self, X, y):
"""训练决策树"""
self.root = self.build_tree(X, y)
def predict_sample(self, x, node):
"""预测单个样本"""
if node.value is not None:
return node.value
if x[node.feature] <= node.threshold:
return self.predict_sample(x, node.left)
else:
return self.predict_sample(x, node.right)
def predict(self, X):
"""预测多个样本"""
return np.array([self.predict_sample(x, self.root) for x in X])
def print_tree(self, node=None, depth=0):
"""打印树结构（调试用）"""
if node is None:
node = self.root
indent = " " * depth
if node.value is not None:
print(f"{indent}预测: {node.value}")
else:
print(f"{indent}特征{node.feature} <= {node.threshold:.2f}")
print(f"{indent}├─ 左:")
self.print_tree(node.left, depth + 1)
print(f"{indent}└─ 右:")
self.print_tree(node.right, depth + 1)
if __name__ == "__main__":
np.random.seed(42)
X = np.random.randn(100, 2)
y = ((X[:, 0] > 0) & (X[:, 1] > 0)).astype(int)
tree = DecisionTreeClassifier(max_depth=5)
tree.fit(X, y)
predictions = tree.predict(X)
accuracy = np.mean(predictions == y)
print(f"准确率: {accuracy:.2%}")
print("\n树结构:")
tree.print_tree()
|