1 class Node(object):
 2     def __init__(self, ):
 3         self.sample_index = None 
 4         self.values = None  
 5         self.feature_id = -1
 6         self.features = None
 7         self.n_samples = 0  
 8         self.left_child = None
 9         self.right_child = None
10         self.criterion_value = 0.
11         self.split_value = None  
12         self.n_leaf = 0  
13         self.leaf_costs = 0.  

 1     def _get_feature_values(self, data):
 2         n_features = data.shape[1]
 3         feature_values = {}
 4         for i in range(n_features):
 5             x_feature = sorted(set(data[:, i]))  # 去重与排序
 6             tmp_values = []
 7             for j in range(1, len(x_feature)):
 8                 tmp_values.append(round((x_feature[j - 1] + x_feature[j]) / 2, 4))  # 计算均值
 9             feature_values[i] = tmp_values
10         return feature_values

1 x = np.array([[3, 4, 5, 6, 7],
2               [2, 2, 3, 5, 8],
3               [3, 3, 8, 8, 9.]])
4 _get_feature_values(x)
5 {0: [2.5], 1: [2.5, 3.5], 2: [4.0, 6.5], 3: [5.5, 7.0], 4: [7.5, 8.5]}

 1 class MyCART(object):
 2     def __init__(self, min_samples_split=2,
 3                  epsilon=1e-5,
 4                  pruning=False,
 5                  random_state=2022):
 6         self.root = None
 7         self.min_samples_split = min_samples_split
 8         self.epsilon = epsilon
 9         self.pruning = pruning
10         self.random_state = random_state
11 
12     def _compute_gini(self, y_class):
13         y_unique = np.unique(y_class)
14         if y_unique.shape[0] == 1:  # 只有一个类别
15             return 0.  # 基尼不纯度为0
16         gini = 0.
17         for i in range(len(y_unique)):  # 取每个类别
18             p = np.sum(y_class == y_unique[i]) / len(y_class)
19             gini += p ** 2
20         gini = 1 - gini
21         return gini

 1 def load_simple_data():
 2     x = np.array([[0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1],
 3                   [1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0],
 4                   [2, 1, 1, 2, 2, 2, 0, 2, 2, 0, 0, 2, 2, 1, 1]]).transpose()
 5     y = np.array([1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1])
 6     return x, y
 7 
 8 def test_gini():
 9     x, y = load_simple_data()
10     dt = MyCART()
11     logging.info(f"标签{y}的Gini指数为: {dt._compute_gini(y)}")
12 #  - INFO: 标签[1 1 1 0 0 0 0 1 1 1 1 1 1 0 1]的Gini指数为:  0.4444

 1     def _compute_gini_da(self, f_id, data):
 2         feature_values = self.feature_values[f_id]  
 3         x_feature = data[:, f_id]  
 4         x_ids = np.array(data[:, -1], dtype=np.int).reshape(-1) 
 5         labels = self._y[x_ids]
 6         min_gini = 99999.
 7         split_id = None
 8         split_sample_idx = None
 9         for i in range(len(feature_values)):  
10             index = (x_feature <= feature_values[i])
11             # 判断特征的取值是否 <= 特征分裂值（即左孩子对应的索引），并以此将当前节点中的样本划分为左右两个部分
12             if np.sum(index) < 1.:  
13                 continue
14             d1, y1 = data[index], labels[index]  # 根据当前特征维度的取值将样本划分为两个部分，左子树
15             d2, y2 = data[~index], labels[~index]  # 右子树
16             gini = len(y1) / len(index) * self._compute_gini(y1) + \
17                    len(y2) / len(index) * self._compute_gini(y2)
18             if gini < min_gini:  # 保存当前特征维度下，能使基尼不纯度最小时的特征取值
19                 min_gini = gini
20                 split_id = i
21                 split_sample_idx = index
22         logging.debug(f"当前特征维度下的最小基尼不纯度为 {min_gini}")
23         return min_gini, split_id, split_sample_idx

 1 x = np.array([[0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1],
 2               [1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0],
 3               [2, 1, 1, 2, 2, 2, 0, 2, 2, 0, 0, 2, 2, 1, 1]]).transpose()
 4 y = np.array([1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1])
 5 dt = MyCART()
 6 dt.feature_values = dt._get_feature_values(x)
 7 dt._y = y
 8 print(dt.feature_values)
 9 # {0: [0.5], 1: [0.5], 2: [0.5, 1.5]}
10 X = np.hstack(([x, np.arange(len(x)).reshape(-1, 1)]))
11 r = dt._compute_gini_da(0, X)
12 print(r)
13 #   (0.3452, 0, array([ True,  True,  True,  True,  True,  True,  
14 #     True, False, False, False, False, False, False, False, False]))

1     def fit(self, X, y):
2         self._y = np.array(y).reshape(-1)
3         self.n_classes = len(np.bincount(y))
4         feature_ids = [i for i in range(X.shape[1])]
5         self.feature_values = self._get_feature_values(X)
6         self._X = np.hstack(([X, np.arange(len(X)).reshape(-1, 1)]))
7         self._build_tree(self._X, feature_ids) 

 1     def _build_tree(self, data, f_ids):
 2         x_ids = np.array(data[:, -1], dtype=np.int).reshape(-1)
 3         node = Node()
 4         node.sample_index = x_ids 
 5         labels = self._y[x_ids]
 6         node.n_samples = len(labels)
 7         node.values = np.bincount(labels, minlength=self.n_classes)
 8         node.features = f_ids
 9         if self.root is None:
10             self.root = node
11         y_unique = np.unique(labels) 
12         if y_unique.shape[0] == 1 or len(f_ids) < 1 \
13                 or node.n_samples <= self.min_samples_split:
14             return node
15         gini = self._compute_gini(labels)
16         node.criterion_value = gini

 1         min_gini = 99999
 2         split_id = None 
 3         split_sample_idx = None
 4         best_feature_id = -1
 5         for f_id in f_ids:
 6             m_gini, s_id, s_s_idx = self._compute_gini_da(f_id, data)
 7             if m_gini < min_gini:
 8                 min_gini = m_gini
 9                 split_id = s_id
10                 split_sample_idx = s_s_idx
11                 best_feature_id = f_id

 1         node.feature_id = best_feature_id
 2         feature_values = self.feature_values[best_feature_id]
 3         node.split_value = feature_values[split_id]
 4         left_data = data[split_sample_idx]
 5         right_data = data[~split_sample_idx]
 6         candidate_ids = deepcopy(f_ids)
 7         candidate_ids.remove(best_feature_id) 
 8         if len(left_data) > 0:
 9             node.left_child = self._build_tree(left_data, candidate_ids)
10         if len(right_data) > 0:
11             node.right_child = self._build_tree(right_data, candidate_ids)
12         return node

 1 def test_cart():
 2     x, y = load_simple_data()
 3     dt = MyCART(min_samples_split=1)
 4     dt.fit(x, y)
 5     dt.level_order()
 6 
 7 标签[1 1 1 0 0 0 0 1 1 1 1 1 1 0 1]的GINI指数为: 0.4444
 8 ========>
 9 当前节点所有样本的索引 [ 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14]
10 当前节点的样本数量 15 当前节点每个类别的样本数 [ 5 10]
11 当前节点状态时特征集中剩余特征 [0, 1, 2] 当前节点中的样本基尼不纯度为 0.4444
12 ----------
13 所有特征维度对应的离散化特征取值为 {0: [0.5], 1: [0.5], 2: [0.5, 1.5]}
14 当前特征维度<0>对应的离散化特征取值为 [0.5]
15 当前样本对应的标签值为[1 1 1 0 0 0 0 1 1 1 1 1 1 0 1]
16 当前特征维度在 x <= 0.5 下对应的基尼不纯度为： 0.3452 =(7/15)* 0.4898 + (8/15)* 0.2188
17 当前特征维度下的最小基尼不纯度为 0.3452
18 ----------
19 所有特征维度对应的离散化特征取值为 {0: [0.5], 1: [0.5], 2: [0.5, 1.5]}
20 当前特征维度<1>对应的离散化特征取值为 [0.5]
21 当前样本对应的标签值为[1 1 1 0 0 0 0 1 1 1 1 1 1 0 1]
22 当前特征维度在 x <= 0.5 下对应的基尼不纯度为： 0.381 =(8/15)* 0.5 + (7/15)* 0.2449
23 当前特征维度下的最小基尼不纯度为 0.3809
24 ----------
25 所有特征维度对应的离散化特征取值为 {0: [0.5], 1: [0.5], 2: [0.5, 1.5]}
26 当前特征维度<2>对应的离散化特征取值为 [0.5, 1.5]
27 当前样本对应的标签值为[1 1 1 0 0 0 0 1 1 1 1 1 1 0 1]
28 当前特征维度在 x <= 0.5 下对应的基尼不纯度为： 0.4444 =(3/15)* 0.4444 + (12/15)* 0.4444

 1 正在进行层次遍历……
 2 第1层的节点为：
 3 当前节点所有样本的索引([ 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14])
 4 当前节点的样本数量(15) 当前节点每个类别的样本数([ 5 10]) 当前节点对应的基尼不纯度为(0.444)
 5 第2层的节点为：
 6 当前节点所有样本的索引([0 1 2 3 4 5 6])
 7 当前节点的样本数量(7) 当前节点每个类别的样本数([4 3]) 当前节点对应的基尼不纯度为(0.49)
 8 当前节点所有样本的索引([ 7  8  9 10 11 12 13 14])
 9 当前节点的样本数量(8) 当前节点每个类别的样本数([1 7]) 当前节点对应的基尼不纯度为(0.219)
10 ......

 1     def _predict_one_sample(self, x):
 2         current_node = self.root
 3         while True:
 4             if not current_node.left_child or \
 5                     not current_node.right_child or \
 6                     current_node.split_value is None \
 7                     or current_node.n_samples < self.min_samples_split:
 8                 return current_node.values
 9             current_feature_id = current_node.feature_id
10             current_feature = x[current_feature_id]
11             split_value = current_node.split_value
12             if current_feature <= split_value:
13                 current_node = current_node.left_child
14             else:
15                 current_node = current_node.right_child

1     def predict(self, X):
2         results = []
3         for x in X:
4             results.append(self._predict_one_sample(x))
5         results = np.array(results)
6         logging.debug(f"原始预测结果为:\n{results}")
7         y_pred = np.argmax(results, axis=1)
8         return y_pred

1 y_pred = dt.predict(np.array([[0, 0, 2],
2                               [0, 1, 1],
3                               [1, 1, 1],
4                               [0, 1, 0],
5                               [0, 1, 2]]))

1 原始预测结果为:
2 [[3 0]
3  [0 2]
4  [0 1]
5  [0 2]
6  [1 1]]
7 CART 预测结果为：[0 1 1 1 0]

 1     def _get_pruning_gt(self, node):
 2 
 3         def _compute_cost_in_leaf(labels):
 4             y_count = np.bincount(labels)
 5             n_samples = len(labels)
 6             cost = 0
 7             for i in range(len(y_count)):
 8                 if y_count[i] == 0:
 9                     continue
10                 cost += y_count[i] * np.log2(y_count[i] / n_samples)
11             return -cost
12 
13         if not node.left_child and not node.right_child:
14             node.leaf_costs = _compute_cost_in_leaf(self._y[node.sample_index])
15             return 9999999.
16         parent_cost = _compute_cost_in_leaf(self._y[node.sample_index])# 计算以当前节点为根节点剪枝后的损失
17         if node.left_child:
18             node.leaf_costs += node.left_child.leaf_costs  # 以当前节点为根节点累计剪枝前所有叶子节点的损失
19         if node.right_child:
20             node.leaf_costs += node.right_child.leaf_costs
21         g_t = (parent_cost - node.leaf_costs) / (node.n_leaf - 1 + 1e-5)  # 计算gt，其中1e-5为平滑项
22         return g_t

 1     def _get_subtree_sequence(self):
 2         subtrees = []
 3         stop = False
 4         while not stop:
 5             if not self.root.right_child and not self.root.left_child:
 6                 stop = True
 7             level_order_nodes = self.level_order(return_node=True)
 8             best_gt = 99999.
 9             best_pruning_node = None
10             for i in range(len(level_order_nodes) - 1, -1, -1):  
11                 current_level_nodes = level_order_nodes[i]
12                 for j in range(len(current_level_nodes)): 
13                     current_node = current_level_nodes[j]
14                     current_node.n_leaf = 0   
15                     current_node.leaf_costs = 0. 
16                     if current_node.left_child is not None:
17                         current_node.n_leaf += current_node.left_child.n_leaf
18                     if current_node.right_child is not None:
19                         current_node.n_leaf += current_node.right_child.n_leaf
20                     elif not current_node.left_child and not current_node.right_child:
21                         current_node.n_leaf = 1
22                     gt = self._get_pruning_gt(current_node)
23                     if gt < best_gt:
24                         best_gt = gt
25                         best_pruning_node = current_node
26             subtrees.append(deepcopy(self.root))
27             if not stop:
28                 best_pruning_node.left_child = None
29                 best_pruning_node.right_child = None  # 剪枝
30         return subtrees

 1 def test_get_subtree():
 2     x, y = load_simple_data()
 3     dt = CART(min_samples_split=1)
 4     dt.fit(x, y)
 5     subtrees = dt._get_subtree_sequence()
 6     logging.debug(f"生成子树个数为：{len(subtrees)}")
 7     for i, tree in enumerate(subtrees):
 8         logging.debug(f"-----正在层次遍历第 {i} 颗子树-----")
 9         dt.root = tree
10         dt.level_order()

 1 正在获取子序列T0,T1,T2,T3...
 2 正在进行层次遍历……
 3 并返回层次遍历的所有结果！
 4 ------------------
 5 当前节点g(t)为:1.2451 当前节点（剪枝后）的损失为：3.2451
 6 当前节点的孩子节点（剪枝前）损失为：2.0
 7 ------------------
 8 当前节点g(t)为:0.4902 当前节点（剪枝后）的损失为：3.2451
 9 当前节点的孩子节点（剪枝前）损失为：2.7548
10 ------------------
11 当前节点g(t)为:2.4482 当前节点（剪枝后）的损失为：6.8965
12 当前节点的孩子节点（剪枝前）损失为：2.0
13 ------------------
14 当前节点g(t)为:0.7968 当前节点（剪枝后）的损失为：4.3485
15 当前节点的孩子节点（剪枝前）损失为：2.7548
16 ------------------
17 当前节点g(t)为:1.8039 当前节点（剪枝后）的损失为：13.7744
18 当前节点的孩子节点（剪枝前）损失为：4.7548
19 本轮T(0)计算结束，最小的g(t)为 0.4902
20 注意：上述剪枝的计算顺序为从下到上，从左到右。上述输出结果也就是对应着8.8.2节中的所有计算过程。

 1     def _pruning_leaf(self):
 2         subtrees = self._get_subtree_sequence()
 3         best_tree = None
 4         max_acc = 0.
 5         for tree in subtrees:
 6             self.root = tree
 7             acc = accuracy_score(self.predict(self.x_test), self.y_test)
 8             if acc > max_acc:
 9                 max_acc = acc
10                 best_tree = tree
11         self.root = best_tree

 1 def test_wine_classification():
 2     x, y = load_wine(return_X_y=True)
 3     x_train, x_test, y_train, y_test = train_test_split(x, y, test_size=0.3, random_state=12)
 4     dt = MyCART(min_samples_split=2, pruning=True, random_state=2020)
 5     dt.fit(x_train, y_train)
 6     y_pred = dt.predict(x_train)
 7     logging.info(f"MyCART Acc on training data：{accuracy_score(y_train, y_pred)}")
 8     y_pred = dt.predict(x_test)
 9     logging.info(f"MyCART Acc on testing data：{accuracy_score(y_test, y_pred)}")
10     model = DecisionTreeClassifier(criterion='gini', random_state=20)
11     model.fit(x_train, y_train)
12     y_pred = model.predict(x_test)
13     logging.info(f"DecisionTreeClassifier Acc on testing data：{accuracy_score(y_test, y_pred)}")

1 MyCART Acc on training data：0.9919
2 MyCART Acc on testing data：0.9444
3 DecisionTreeClassifier Acc on testing data：0.9444