ID3算法
- 算法流程描述
-
- 算法流程
- python实现代码
-
- 各方法的解释
- 代码
- 数据集介绍
- 训练数据和测试数据划分
- 结果分析
-
- 分类准确率及决策树
- 优点和缺点
- 改进的算法：
-
- C4.5算法
- CART算法
算法流程描述
ID3算法是一种贪心算法，用来构造决策树。它以信息熵的下降速度为选取测试属性的标准，即在每个节点选取还尚未被用来划分的具有最高信息增益的属性作为划分标准，然后继续这个过程，直到生成的决策树能完美分类训练样例。
算法流程
- 输入需要分类的数据集和类别标签和靶标签。
- 检验数据集是否只有一列，或者是否最后一列(靶标签数据默认放到最后一列)只有一个水平(唯一值)。是则返回唯一值水平或者占比最大的那个水平。
-
调用信息增益公式，计算所有节点的信息增益，得到最大信息增益所对应的类别标签。
信息熵公式：
信息增益公式：
机器学习之ID3算法（小白入门级别）算法流程描述数据集介绍训练数据和测试数据划分结果分析优点和缺点改进的算法： 
机器学习之ID3算法（小白入门级别）算法流程描述数据集介绍训练数据和测试数据划分结果分析优点和缺点改进的算法： - 建立决策树字典用以保存该次叶节点数据信息。
- 进入循环：按照该类别标签的不同水平，依次计算子数据集；对子数据集重复(1),(2),(3),(4),(5)步。
- 返回决策树字典。
该算法使用python语言实现，最终生成的决策树实际上是一个大的递归函数，其结果是一个多层次的字典。
python实现代码
各方法的解释
LoadDataSet函数用来载入数据。
ID3Tree类中，_best_split用来遍历标签并计算最大信息增益对应的标签；_entropy就是计算熵；_split_dataSet用于切割数据集；_top_amount_level是递归终止条件触发时的返回值。即只有一个特征列的一个level的子集时，如果对应的purchase还有买和不买(level)，就返回最大占比的level；mktree主程序，递归生成决策树，并将其保存在tree字典中；predict主程序，用于预测分类；_unit_test，单元测试程序，用于测试上面一些函数。
代码
import numpy as np
import pandas as pd
import json
from divideData import divide_data
# 用于载入数据
class LoadDataSet(object):
def load_dataSet(self):
data = pd.read_csv("./train_ID3data.txt", sep="\t", header=None) # 返回DataFrame类型：二维标记数据结构
data.rename(columns={0: "age", 1: "income", 2: "student", 3: "reputation", 4: "purchase"}, inplace=True) # 修改列名
return data
class ID3Tree(LoadDataSet):
"""主要的数据结构是pandas对象"""
__count = 0
def __init__(self):
super().__init__()
"""认定最后一列是标签列"""
self.dataSet = self.load_dataSet()
self.gain = {}
def _entropy(self, dataSet):
"""计算给定数据集的熵"""
labels = list(dataSet.columns) # 获取列名，即属性标签
level_count = dataSet[labels[-1]].value_counts().to_dict() # 统计分类属性标签的各类水平
entropy = 0.0
for key, value in level_count.items(): # 对每一种分类都计算
prob = float(value) / dataSet.shape[0] # 使用某类数量除dataSet.shape[0]（行数），即某分类个数/总数
entropy += -prob * np.log2(prob) # 计算信息熵
return entropy # 返回信息熵
def _split_dataSet(self, dataSet, column, level):
"""根据给定的column和其level来获取子数据集"""
subdata = dataSet[dataSet[column] == level] # 选出某列值为level的行数据，构建数据子集
del subdata[column] # 删除这个划分字段列
return subdata.reset_index(drop=True) # 重建索引
def _best_split(self, dataSet):
"""计算每个分类标签的信息增益"""
best_info_gain = 0.0 # 求最大信息增益
best_label = None # 求最大信息增益对应的标签(字段)
labels = list(dataSet.columns)[: -1] # 不包括最后一个靶标签
init_entropy = self._entropy(dataSet) # 先求靶标签的香农熵
for _, label in enumerate(labels): # enumerate() 函数用于将一个可遍历的数据对象(如列表、元组或字符串)组合为一个索引序列，同时列出数据和数据下标，一般用在 for 循环当中
# 根据该label(也即column字段)的唯一值(levels)来切割成不同子数据集，并求它们的香农熵
levels = dataSet[label].unique().tolist() # 获取该分类标签的不同level
label_entropy = 0.0 # 用于累加各水平的信息熵；分类标签的信息熵等于该分类标签的各水平信息熵与其概率积的和。
for level in levels: # 循环计算不同水平的信息熵
level_data = dataSet[dataSet[label] == level] # 获取该水平的数据集
prob = level_data.shape[0] / dataSet.shape[0] # 计算该水平的数据集在总数据集的占比
# 计算香农熵，并更新到label_entropy中
label_entropy += prob * self._entropy(level_data) # _entropy用于计算香农熵
# 计算信息增益
info_gain = init_entropy - label_entropy # 代码至此，已经能够循环计算每个分类标签的信息增益
# 用best_info_gain来取info_gain的最大值，并获取对应的分类标签
if info_gain > best_info_gain:
best_info_gain = info_gain
best_label = label
# 这里保存一下每一次计算的信息增益，便于查看和检查错误
# Python 字典 setdefault() 函数和 get()方法类似, 如果键不存在于字典中，将会添加键并将值设为默认值。
self.gain.setdefault(self.__count, {}) # 建立本次函数调用时的字段，设其value为字典
self.gain[self.__count][label] = info_gain # 把本次函数调用时计算的各个标签数据存到字典里
self.__count += 1
return best_label
def _top_amount_level(self, target_list):
"""返回数量最多的水平"""
class_count = target_list.value_counts().to_dict() # 计算靶标签的不同水平的样本量，并转化为字典
# 字典的items方法可以将键值对转成[(), (), ...]，可以使用列表方法
sorted_class_count = sorted(class_count.items(), key=lambda x: x[1], reverse=True) # 将字典中各水平按数量降序排列
return sorted_class_count[0][0] # 返回最大数量的水平
def mktree(self, dataSet):
"""创建决策树"""
target_list = dataSet.iloc[:, -1] # target_list 靶标签的那一列数据
# 程序终止条件一: 靶标签(数据集的最后一列因变量)在该数据集上只有一个水平，返回该水平
if target_list.unique().shape[0] <= 1:
return target_list[0] # ！！！
# 程序终止条件二: 数据集只剩下靶标签这一列数据；返回数量最多的水平
if dataSet.shape[1] == 1:
return self._top_amount_level(target_list)
# 不满足终止条件时，做如下递归处理
# 1.选择最佳分类标签
best_label = self._best_split(dataSet)
# 2.递归计算最佳分类标签的不同水平的子数据集的信息增益
# 各个子数据集的最佳分类标签的不同水平...
# ...
# 直至递归结束
best_label_levels = dataSet[best_label].unique().tolist() # 返回best_label列中的所有水平值
tree = {best_label: {}} # 生成字典，用于保存树状分类信息；这里不能用self.tree = {}存储
for level in best_label_levels:
level_subdata = self._split_dataSet(dataSet, best_label, level) # 获取该水平的子数据集
tree[best_label][level] = self.mktree(level_subdata) # 返回结果
return tree
def predict(self, tree, labels, test_sample):
"""
对单个样本进行分类
tree: 训练的字典
labels: 除去最后一列的其它字段
test_sample: 需要分类的一行记录数据
"""
firstStr = list(tree.keys())[0] # tree字典里找到第一个用于分类键值对
secondDict = tree[firstStr] # 第一个分类之后的字典存起来
featIndex = labels.index(firstStr) # 找到第一个分类的索引
for key in secondDict.keys():
if test_sample[featIndex] == key: # 找到test_sample在当前分类下的值
if secondDict[key].__class__.__name__ == "dict": # 后面仍为字典类型，即仍需分类
classLabel = self.predict(secondDict[key], labels, test_sample) # 继续分类
else: # 否则就直接返回该处的yes/no
classLabel = secondDict[key]
return classLabel
def _unit_test(self):
divide_data()
self.tree = self.mktree(self.dataSet) # 到此行，用于测试主程序mktree
labels = ["age", "income", "student", "reputation"]
test_data = pd.read_csv("./test_ID3data.txt", sep="\t", header=None)
target_list = (test_data.iloc[:, -1]).values.tolist() # 获取靶标签
test_list = (test_data.iloc[:, [0, 1, 2, 3]]).values.tolist() # 获取其他四列数据
sum = 0
right = 0
for test_sample in test_list:
outcome = self.predict(self.tree, labels, test_sample) # 预测分类
if outcome == target_list[sum]:
right = right+1
sum = sum + 1
accuracy_rate = right/sum
print("模型准确率：", accuracy_rate)
model = ID3Tree()
model._unit_test()
print(json.dumps(model.gain, indent=" ")) # 可以查看每次递归时的信息熵
print(json.dumps(model.tree, indent=" ")) # 查看树
数据集介绍
代码中使用的数据是一张包含用户信息和购买决策的表，来源于网络。对于第0条和第7条数据，唯一的区别是income不同，于是可以认为，此时income不具有参考价值，而应考察student值或reputation的信息，这也是为什么生成的树中不包含income这一节点。这张表已经对1024个样本进行了分组统计，具体数据如下：
| — | count | age | income | student | reputation | purchase |
|---|---|---|---|---|---|---|
| 64 | 青年 | 高 | 否 | 良 | 不买 | |
| 1 | 64 | 青年 | 高 | 否 | 优 | 不买 |
| 2 | 128 | 中年 | 高 | 否 | 良 | 买 |
| 3 | 60 | 老年 | 中 | 否 | 良 | 买 |
| 4 | 64 | 老年 | 低 | 是 | 良 | 买 |
| 5 | 64 | 老年 | 低 | 是 | 优 | 不买 |
| 6 | 64 | 中年 | 低 | 是 | 优 | 买 |
| 7 | 128 | 青年 | 中 | 否 | 良 | 不买 |
| 8 | 64 | 青年 | 低 | 是 | 良 | 买 |
| 9 | 132 | 老年 | 中 | 是 | 良 | 买 |
| 10 | 64 | 青年 | 中 | 是 | 优 | 买 |
| 11 | 32 | 中年 | 中 | 否 | 优 | 买 |
| 12 | 32 | 中年 | 高 | 是 | 良 | 买 |
| 13 | 64 | 老年 | 中 | 否 | 优 | 不买 |
训练数据和测试数据划分
使用sklearn.model_selection.train_test_split来随机划分训练集和测试集，在本次实验中，将购买决策信息表的数据按7:3的比例划分为训练集和测试集。使用训练集进行模型的训练，测试集用于测试模型的准确性。
divideData.py文件具体代码如下：
import numpy as np
from sklearn.model_selection import train_test_split
import random
def divide_data():
my_matrix = np.loadtxt(open("ID3data.txt"),dtype=str,delimiter="\t")
X, y = my_matrix[:,:-1],my_matrix[:,-1]
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=int(random.random()*100))
train= np.column_stack((X_train,y_train))
np.savetxt('train_ID3data.txt', train, fmt='%s', delimiter='\t')
test = np.column_stack((X_test, y_test))
np.savetxt('test_ID3data.txt', test, fmt='%s', delimiter='\t')
print("训练集与数据集划分完成，比例为7:3！")
结果分析
分类准确率及决策树
经过多次测试，在不同训练集和测试集下构建多个决策树，并计算出准确率（在第十次测试时修改测试集的一个属性的标签），结果如下：
| 测试序号 | 准确率 |
|---|---|
| 1 | 1.0 |
| 2 | 1.0 |
| 3 | 1.0 |
| 4 | 1.0 |
| 5 | 1.0 |
| 6 | 1.0 |
| 7 | 1.0 |
| 8 | 1.0 |
| 9 | 1.0 |
| 10 | 0.9968 |
分类结果准确率
第6次测试递归的信息熵
生成的决策树
由结果分析可知，ID3算法充分发挥了信息增益的优点，使构建的决策树最小，仅有三层，同时准确率非常高，这也与数据的完整和无噪声密切相关。但是也存在着缺陷，比如该模型处理大量缺失值的数据时会报错。
优点和缺点
优点：算法简单，核心是根据“最大信息熵增益”原则选择划分当前数据集的最好特征。
缺点：只能处理离散型属性，并且倾向于选择取值较多的属性。因为信息增益反映的给定一个条件以后不确定性减少的程度，必然是分得越细的数据集确定性更高，也就是条件熵越小，信息增益越大。
改进的算法：
C4.5算法
C4.5算法流程与ID3相类似，只不过将信息增益改为信息增益比，以解决偏向取值较多的属性的问题，另外它可以处理连续型属性。
信息增益率：
其中IV(a)的计算方式如下：
CART算法
相比ID3和C4.5，CART应用要多一些，既可以用于分类也可以用于回归。CART分类时，使用基尼指数（Gini）来选择最好的数据分割特征，Gini描述的是纯度，与信息熵的含义相似。Gini指数越小表示集合中被选中的样本被分错的概率越小，也就是说集合的纯度越高，反之，集合越不纯。
对于给定的样本集合D，其基尼指数为：
如果样本集合D根据特征A是否取某一可能值a被分为两部分，则在特征A的条件下，集合D的基尼指数定义为：