Day 61-62 决策树（ID3）

**决策树（ID3）**

决策树是一种常见的机器学习算法，用于分类问题。它通过递归地将数据集分割成更小的子集，并根据特征选择来构建决策树模型。

### ID3 算法概述ID3（Iterative Dichotomiser3）是由 Ross Quinlan 在1986 年提出的一种决策树算法。它通过递归地将数据集分割成更小的子集，并根据信息增益来选择特征。

### ID3 算法流程1. **初始化**: 初始化决策树根节点。
2. **选择特征**:选择最优特征，根据信息增益来决定。
3. **划分数据集**: 根据选择的特征，将数据集分割成两个子集。
4. **递归**: 对每个子集重复步骤2 和3，直到满足停止条件。

###信息增益信息增益是用于评估特征选择的指标。它表示在使用该特征后数据集的熵减少量。

**熵公式**：

H(D) = -∑p(x)log2p(x)

其中，D 是数据集，x 是类别，p(x) 是类别概率。

**信息增益公式**：

IG(D, A) = H(D) - ∑|D_i|/n * H(D_i)

其中，A 是特征，D_i 是子集，n 是数据集大小。

###代码示例

import numpy as npclass DecisionTree:
 def __init__(self):
 self.tree = {}

 def fit(self, X, y):
 # 初始化决策树根节点 self.tree = {'feature': None, 'value': None, 'left': None, 'right': None}

 # 递归构建决策树 self._build_tree(X, y)

 def _build_tree(self, X, y):
 #选择最优特征 feature = self._choose_feature(X, y)
 if feature is not None:
 # 划分数据集 left_X, right_X, left_y, right_y = self._split_data(X, y, feature)

 # 递归构建子树 self.tree['feature'] = feature self.tree['value'] = np.mean(y)
 if len(left_X) >0:
 self.tree['left'] = DecisionTree()
 self.tree['left'].fit(left_X, left_y)
 if len(right_X) >0:
 self.tree['right'] = DecisionTree()
 self.tree['right'].fit(right_X, right_y)

 def _choose_feature(self, X, y):
 #选择最优特征 features = [i for i in range(X.shape[1])]
 best_feature = None best_gain = -np.inf for feature in features:
 gain = self._information_gain(X[:, feature], y)
 if gain > best_gain:
 best_feature = feature best_gain = gain return best_feature def _split_data(self, X, y, feature):
 # 划分数据集 left_X = []
 right_X = []
 left_y = []
 right_y = []

 for i in range(len(X)):
 if X[i, feature] < np.mean(X[:, feature]):
 left_X.append(X[i])
 left_y.append(y[i])
 else:
 right_X.append(X[i])
 right_y.append(y[i])

 return np.array(left_X), np.array(right_X), np.array(left_y), np.array(right_y)

 def predict(self, X):
 # 预测 predictions = []
 for x in X:
 prediction = self._predict(x)
 predictions.append(prediction)

 return predictions def _predict(self, x):
 # 预测 if 'feature' not in self.tree or self.tree['feature'] is None:
 return self.tree['value']

 feature = self.tree['feature']
 value = self.tree['value']
 left_tree = self.tree['left']
 right_tree = self.tree['right']

 if x[feature] < value:
 return left_tree._predict(x)
 else:
 return right_tree._predict(x)

# 示例使用X = np.array([[1,2], [3,4], [5,6]])
y = np.array([0,0,1])

tree = DecisionTree()
tree.fit(X, y)

print(tree.predict(np.array([[7,8]])))