按照上面的套路，我们先取色泽作为划分特征，计算一下对应的信息增益。
首先，系统当前有8个好瓜，9个坏瓜，所以对应 信息熵为：
我们再选色泽作为划分特征，计算一下子集信息熵的期望：
其中：
带入上式，得：
再依次计算出其他特征对应的信息增益，取信息增益最大的那个特征作为首选条件，再如此继续划分下去，就可以得到一个树形结构的分支图，即我们要的决策树。
退出条件：
1.划分子集的信息熵为0；
2.无可用特征，取当前集合占比最大的作为标签。
下面我们用Python来实现。首先要把图4.1的文字转为csv文件的格式：
我们只要从csv里读取数据，就能进行后续的分析了。ID3的Python实现如下： import numpy as np import math class DTree: def __init__(self, type=0): self.dataset = '' self.model = '' def load_data(self, data): dataset = np.loadtxt(data, delimiter=',', dtype=str) self.dataset = dataset def get_entropy(self, dataset): # 统计总数及正反例个数 sum_num = len(dataset[1:]) p1 = dataset[1:, -1].astype(int).sum() / sum_num p2 = 1 - p1 # 如果p1或p2有一个为0，说明子集纯度为0,，直接返回0 if p1==0 or p2==0: return 0 # 使用公式计算信息熵并返回 return -1*(p1*math.log2(p1) + p2*math.log2(p2)) def get_max_category(self, dataset): pos = dataset[1:, -1].astype(int).sum() neg = len(dataset[1:, -1]) - pos return '1' if pos > neg else '0' def dataset_split(self, dataset, feature, feature_value): index = list(dataset[0, :-1]).index(feature) # 遍历特征所在列，剔除值不等于feature_value的行 j = 0 for i in range(len(dataset[1:, index])): if dataset[1:, index][j] != feature_value: dataset = np.delete(dataset, j+1, axis=0) j -= 1 j += 1 # 删除feature所在列 return np.delete(dataset, index, axis=1) def get_best_feature(self, dataset, E): feature_list = dataset[0, :-1] feature_gains = {} for i in range(len(feature_list)): # 分别统计在每个特征值划分下的信息增益 feature_values = np.unique(dataset[1:, i]) feature_sum = len(dataset[1:, i]) # 累加子集熵 sub_entropy_sum = 0 for value in feature_values: # 按值划分子集 subset = self.dataset_split(dataset, feature_list[i], value) subset_sum = len(subset) # 计算子集熵 sub_entropy = self.get_entropy(subset) # 权重 w = subset_sum/feature_sum # 汇总当前特征下的子集熵*个数权重 sub_entropy_sum += w*sub_entropy # 根据算公式计算信息增益 feature_gains[feature_list[i]] = E-sub_entropy_sum # 返回最大信息增益对应的特征及索引 max_gain = max(feature_gains.values()) for feature in feature_gains: if feature_gains[feature] == max_gain: index = list(feature_list).index(feature) return feature, index def build_tree(self, dataset): # 计算数据集信息熵 E = self.get_entropy(dataset) # 设置退出条件 # 1.如果集合的信息熵为0，则返回当前标签 if E == 0: return dataset[1][-1] # 2.特征数为1，说明无可划分特征，返回当前集合中占比最多的标签 if len(dataset[0]) == 2: # 特征+标签 return self.get_max_category(dataset) # 获取最佳特征 feature, index = self.get_best_feature(dataset, E) # 按特征划分子集 tree = {feature:{}} # 获取特征值 feature_values = np.unique(dataset[:, index][1:]) # 按特征值划分子集 for value in feature_values: subset = self.dataset_split(dataset, feature, value) subtree = self.build_tree(subset) tree[feature][value] = subtree return tree def train(self): self.model = self.build_tree(self.dataset) return self.model def predict(self, tree, testset): pass dtree = DTree() dtree.load_data('data4_1.csv') tree_model = dtree.train() print(tree_model)