【机器学习】k近邻算法（KNN）【机器学习】决策树（Decision Tree）

【机器学习】朴素贝叶斯（Naive Bayes）

一、概述

决策树（Decision Tree）是有监督学习中的一种算法，并且是一种基本的分类与回归的方法。

决策树有两种：分类树和回归树。（这里主要讨论分类树）

相关概念：

根节点：没有进边，有出边中间节点：既有进边也有出边，但进边有且仅有一条，出边也可以有很多条叶节点：只有进边，没有出边，进边有且仅有一条。每个叶节点都是一个类别标签父节点和子节点在两个相连的节点中，更靠近根节点的是父节点，另一个则是子节点。两者是相对的

将决策树转换成if-then规则的过程是这样的：

由决策树的根节点到叶节点的每一条路径构建一条规则路径上中间节点的特征对应着规则的条件;叶节点的类标签对应着规则的结论;决策树的路径性质：互斥并且完备。也就是说，每一个实例都被有且仅有一条路径或者规则所覆盖。

2. 决策树的构建准备

（1）特征选择

特征选择：就是决定用哪个特征来划分特征空间，其目的在于选取对训练数据具有分类能力的特征。这样可以提高决策树学习的效率。

随着划分过程不断进行，我们希望决策树的分支节点所包含的样本尽可能属于同一类别，也就是节点的纯度（purity）越来越高。

因此在选择划分特征是尽量选择纯度低的特征，能够更好的划分特征空间。即，需要衡量特征的不纯度，度量不纯度的指标有很多种，比如：熵、增益率、基尼值数。（这里我们以熵为主）

计算香农熵

熵定义为信息的期望值。在信息论与概率统计中，熵是表示随机变量不确定性的度量。

假定当前样本集合D中一共有n类样本，则熵的计算公式为：

其中p(xi)是该分类在所有样本中的概率。熵Ent(D)越高，信息的不纯度就越高。也就是混合的数据就越多。

Python代码如下：

import numpy as np# 计算香农熵def calEnt(dataSet):n = dataSet.shape[0] # 数据集总行数iset = dataSet.iloc[:, -1].value_counts() # 标签的所有类别p = iset / n # 每一类标签所占比ent = (-p * np.log2(p)).sum() # 计算信息熵return ent

现有数据如下：

import pandas as pd# 创建数据集def createDataSet():row_data = {'no surfacing': [1, 1, 1, 0, 0],'flippers': [1, 1, 0, 1, 1],'fish': ['yes', 'yes', 'no', 'no', 'no']}dataSet = pd.DataFrame(row_data)return dataSet

由数据标签fish列可以看出，该数据有两类，则表示yes的p(1)为2/5；表示no的p(2)为3/5，因此熵的计算结果为：

ent=0.9709505944546686

信息增益

信息增益（Information Gain）的计算公式其实就是父节点的信息熵与其下所有子节点总信息熵之差。

但这里要注意的是，此时计算子节点的总信息熵不能简单求和，而要求在求和汇总之前进行修正。

信息增益的计算公式为:

假设离散属性a有V种取值，则使用a对样本数据D进行划分，则会产生V个分支节点，其中第v个节点包含了D种所有在属性a上取值为的样本，记为，则||表示样本数据D中类的数据的数量，|D|表示样本D的总数量。

所以对与上述鱼类的数据集中第0列（no surfacing）的计算其信息增益：

（no surfacing）列中有两类1和0，则：

对于D1（no surfacing=1）的计算其熵:

对于D2（no surfacing=0）的计算其熵:

信息增益：

（2）数据集最佳切分函数

划分数据集的最大准则是选择最大信息增益的特征数据进行划分，也就是信息下降最快的方向。

如对特征（no surfacing）计算的信息增益为0.42，对（flipper）计算的信息增益为0.17。

所以我们应该选择第0列（no surfacing）进行切分数据集。

Python代码如下：

"""函数功能：根据信息增益选择出最佳数据集切分的列参数说明：dataSet：原始数据集返回：axis:数据集最佳切分列的索引"""# 选择最优的列进行切分def bestSplit(dataSet):baseEnt = calEnt(dataSet) # 计算原始熵bestGain = 0 # 初始化信息增益axis = -1 # 初始化最佳切分列，标签列for i in range(dataSet.shape[1] - 1): # 对特征的每一列进行循环levels = dataSet.iloc[:, i].value_counts().index # 提取出当前列的所有取值ents = 0 # 初始化子节点的信息熵for j in levels: # 对当前列的每一个取值进行循环childSet = dataSet[dataSet.iloc[:, i] == j] # 某一个子节点的dataframeent = calEnt(childSet) # 计算某一个子节点的信息熵ents += (childSet.shape[0] / dataSet.shape[0]) * ent # 计算当前列的信息熵# print(f'第{i}列的信息熵为{ents}')infoGain = baseEnt - ents # 计算当前列的信息增益# print(f'第{i}列的信息增益为{infoGain}')if infoGain > bestGain:bestGain = infoGain # 选择最大信息增益axis = i # 最大信息增益所在列的索引return axis

（3）按照给定的列划分数据集

通过最佳切分函数返回最佳切分列的索引，我们就可以根据这个索引，构建一个按照给定列切分数据集的函数

"""函数功能：按照给定的列划分数据集参数说明：dataSet：原始数据集axis：指定的列索引value：指定的属性值返回：redataSet：按照指定列索引和属性值切分后的数据集"""def mySplit(dataSet, axis, value):col = dataSet.columns[axis] # 指定列的标签redataSet = dataSet.loc[dataSet[col] == value, :].drop(col, axis=1) # 提取出指定列中指定内容的数据集，除去该列的信息并输出return redataSet

3. 递归构建决策树

决策树的工作原理：

第一次划分数据集：得到原始数据集，然后基于最好的属性值划分数据集，由于特征值可能多于两个，因此可能存在大于两个分支的数据集划分。第一次划分之后，数据集被向下传递到树的分支的下一个节点。在这个节点上，我们可以再次划分数据。因此我们可以采用递归的原则处理数据集。

（1）ID3算法

构建决策树的算法有很多，比如ID3、C4.5和CART，这里我们选择ID3算法。

ID3算法的核心是在决策树各个节点上对应信息增益准则选择特征，递归地构建决策树。具体方法是： 从根节点开始，对节点计算所有可能的特征的信息增益，选择信息增益最大的特征作为节点的特征；由该特征的不同取值建立子节点；再对子节点递归地调用以上方法，构建决策树；直到所有特征的信息增益均很小或没有特征可以选择为止；最后得到一个决策树。递归结束的条件是：没有属性特征可选用来切分或者叶节点中只有一类标签

Python程序如下：

"""函数功能：基于最大信息增益切分数据集，递归构建决策树参数说明：dataSet：原始数据集（最后一列是标签）返回：myTree：字典形式的树"""def createTree(dataSet):featlist = list(dataSet.columns) # 提取出数据集所有的列表头classlist = dataSet.iloc[:, -1].value_counts() # 获取最后一列类标签# 判断最多标签数目是否等于数据集行数，或者数据集是否只有一列if classlist[0] == dataSet.shape[0] or dataSet.shape[1] == 1:return classlist.index[0] # 如果是，返回类标签axis = bestSplit(dataSet) # 确定出当前最佳切分列的索引bestfeat = featlist[axis] # 获取该索引对应的特征myTree = {bestfeat: {}} # 采用字典嵌套的方式存储树信息del featlist[axis] # 删除当前特征valuelist = set(dataSet.iloc[:, axis]) # 提取最佳切分列所有属性值（该列数据里不同的内容）# 采用递归，切分之后的数据集继续宁建树for value in valuelist: # 对每一个属性值递归建树myTree[bestfeat][value] = createTree(mySplit(dataSet, axis, value))return myTree

至此，咱们的简单的决策树已经构建完成

4. 存储决策树

可以调用以上的所有函数，对数据集进行建立决策树，并将决策树存储

# 创建数据集def createDataSet():row_data = {'no surfacing': [1, 1, 1, 0, 0],'flippers': [1, 1, 0, 1, 1],'fish': ['yes', 'yes', 'no', 'no', 'no']}dataSet = pd.DataFrame(row_data)return dataSetdef main():Data_set = createDataSet()# 建立决策树myTree = createTree(Data_set)# 决策树的存储np.save('myTree.npy', myTree)# 数据的打印与树的读取print(Data_set, '\n', myTree, '\n')read_myTree = np.load('myTree.npy', allow_pickle=True).item()print(read_myTree, '\n')if __name__ == '__main__':main()

打印出存储前和读取存储后的决策树。结果如下：

五、使用决策树执行分类

首先导入需要用到的包

其中将上述建树的过程保存在demo1.py文件中，因此需要使用上述函数的采用import demo1 as demo

import demo1 as demo# 导入相应的包from sklearn import treefrom sklearn.tree import DecisionTreeClassifierimport graphviz

建立一个测试实例的分类函数，将测试数据特征便利已经建好的树，来决策测试数据的结果

"""函数功能：对一个测试实例进行分类参数说明：inputTree：已经生成的决策树labels：存储选择的最优特征标签testVec：测试数据列表，顺序对应原数据集返回：classLabel：分类结果"""def classify(inputTree, labels, testVec):firstStr = next(iter(inputTree)) # 获取决策树第一个节点secondDict = inputTree[firstStr] # 下一个字典featIndex = labels.index(firstStr) # 第一个节点所在列的索引for key in secondDict.keys():if testVec[featIndex] == key:if type(secondDict[key]) == dict:classLabel = classify(secondDict[key], labels, testVec)else:classLabel = secondDict[key]return classLabel

基于训练集进行建树，对测试集进行预测，并返回预测后的结果

"""函数功能：对测试集进行预测，并返回预测后的结果参数说明：train：训练集test：测试集返回：test：预测好分类的测试集"""def acc_classify(train, test):inputTree = demo.createTree(train) # 根据训练集生成一棵树labels = list(train.columns) # 数据集所有的列名称result = []for i in range(test.shape[0]): # 对测试集中每一条数据进行循环testVec = test.iloc[i, :-1] # 测试集中的一个实例classLabel = classify(inputTree, labels, testVec) # 预测该实例的分类result.append(classLabel) # 将分类结果追加到result列表中test['predict'] = result # 将预测结果追加到测试集最后一列acc = (test.iloc[:, -1] == test.iloc[:, -2]).mean() # 计算准确率print(f'模型预测准确率为{acc}')return test

构建主函数执行

采用graphviz进行可视化绘制，需要安装graphviz程序包，注意windows系统上安装graphviz不是简单的 pip install graphviz，建议查看该文档。

def main():dataSet = demo.createDataSet() # 使用demo1中建立数据集的函数train = dataSet # 训练（建树）数据集为所有数据test = dataSet.iloc[:3, :] # 测试数据集选用其中的前三行testy = acc_classify(train, test)print(testy)# 特征Xtrain = dataSet.iloc[:, :-1] # 去掉最后的识别类标签的列，即只保留特征数据# 标签Ytrain = dataSet.iloc[:, -1] # 提取出最后一列的内容labels = Ytrain.unique().tolist() # 提出最后一列内容所有的类别Ytrain = Ytrain.apply(lambda x: labels.index(x)) # 将本文转换为数字# 绘制树模型clf = DecisionTreeClassifier()clf = clf.fit(Xtrain, Ytrain)tree.export_graphviz(clf)dot_data = tree.export_graphviz(clf, out_file=None)graphviz.Source(dot_data)# 给图形增加标签和颜色dot_data = tree.export_graphviz(clf, out_file=None,feature_names=['no surfacing', 'flippers'],class_names=['fish', 'not fish'],filled=True, rounded=True,special_characters=True)graphviz.Source(dot_data)# 利用render方法生成图形graph = graphviz.Source(dot_data)graph.render("fish")if __name__ == '__main__':main()

运行结果为预测准确率和测试集数据，由于我们采用的测试集是训练集的部分数据，因此准确率为1.

（PS：这样产生的树往往对训练数据的分类很准确，但对未知的测试数据的分类却没有那么准确，即出现过拟合现象。过拟合的原因在于学习时过多地考虑如何提高对训练数据的正确分类，从而构建出过于复杂的决策树。解决这个问题的办法是考虑决策树的复杂度，对已生成的决策树进行简化，也就是常说的剪枝处理）

最后生成pdf文件：

对比我们的数据集和前期通过字典数据建立的树：

{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}

学习来源：菊安酱的机器学习实战