人工智能创新实验教程 课件 第4、5章 k-近邻算法、决策树算法

宁夏大学

第四章k-近邻算法K-近邻算法www.islide.cc2目录

CONTENT01引言02算法概述03实验数据04算法实战05本章小结01引言引言

古人云：“近朱者赤，近墨者黑”。其实机器学习中的kNN算法的核心思想就是这句流传至今的名言。kNN算法又称为K近邻算法，是众多机器学习算法中少有的懒惰学习算法，该算法不仅可以用来回归也可以用来分类。本章将学习k近邻算法的基本理论，使用距离测量的方法分类物品，编写构造knn分类器python代码，利用实际的例子讲解如何使用k-近邻算法对糖尿病数据集进行分类预测。02算法概述算法概述1、基本概念​k-近邻算法（k-NearestNeighbouralgorithm），又称为KNN算法，是数据挖掘技术中原理最简单的算法。KNN的工作原理：给定一个已知标签类别的训练数据集，输入没有标签的新数据后，在训练数据集中找到与新数据最邻近的k个实例，如果这k个实例的多数属于某个类别，那么新数据就属于这个类别。可以简单理解为：由那些离X最近的k个点来投票决定X归为哪一类。算法概述

简单地说，k近邻算法采用测量不同特征值之间的距离方法进行分类。​上图中有红色三角和蓝色方块两种类别，现在需要判断绿色圆点属于哪种类别。​当k=3时，绿色圆点属于红色三角这种类别；​当k=5时，绿色圆点属于蓝色方块这种类别。算法概述

要度量空间中点距离的话，有好几种度量方式，比如常见的曼哈顿距离计算，欧式距离计算等等。不过通常KNN算法中使用的是欧式距离，这里只是简单说一下，拿二维平面为例，二维空间两个点的欧式距离计算公式如下：如果是多个特征扩展到N维空间，怎么计算？可以使用欧氏距离（也称欧几里得度量），如下所示：算法概述k-近邻算法步骤如下：(1)计算已知类别数据集中的点与当前点之间的距离；(2)按照距离递增次序排序；(3)选取与当前点距离最小的k个点；(4)确定前k个点所在类别的出现频率；(5)返回前k个点出现频率最高的类别作为当前点的预测类别。03实验数据准备数据数据集介绍DiabetesData也称糖尿病数据集是一类多重变量分析的数据集。通过对442例糖尿病患者的年龄、性别、体重指数、平均血压以及兴趣反应等10个属性进行分析，预测基线一年后疾病进展的定量测量值。本章将从糖尿病数据集中选取部分作为实验数据，并存放于diabetes.csv文本文件中。8个属性变量和标记值具体介绍如右图：处理数据导入数据集，并将数据进行归一化且将数据集进行划分为训练集和测试集，具体操作如下所示：数据归一化为避免其中某个特征数据过大而影响整体，接下来要进行数值归一化的处理，使得这四个特征的权重相等。数据归一化的处理方法有很多种，比如0-1标准化、Z-score标准化、Sigmoid压缩法等等，在这里我们使用最简单的0-1标准化，公式如下：将该计算公式封装为minmax（）函数。处理数据集

归一化数据集后，按照一定比例地要求，将原始数据集分为训练集和测试集两部分。为保证数据地随机分配，采用打乱索引的方式打乱数据顺序。04案例实战k-近邻实现预测测试集并计算准确率

接下来，构建针对于心脏病数据集的分类器，上面我们已经将原始数据集进行归一化处理然后也切分了训练集和测试集，所以我们的函数的输入参数就可以是train、test和k(k-近邻算法的参数，也就是选择的距离最小的k个点)。结果分析准确度分数：调用datingClass()函数后，当k=9时，判断是否患糖尿病的预测准确率达到0.75预测结果下图即为测试集的预测情况：对比outcome和predict两列属性值情况，两者一致则为预测正确，否则即为错误。05本章小结本章小结

本章详细介绍了k近邻的相关理论，阐述了k-近邻算法的工作流程，通过一个糖尿病数据集讲述了如何使用k-近邻算法实现分类训练与预测。K-近邻算法是基于实例的学习，使用算法时我们必须有接近实际数据的训练样本数据。k-近邻算法必须保存全部数据集，如果训练的数据集很大，必须使用大量的存储空间。此外，由于必须对数据集中的每个数据计算距离值，实际使用时可能非常耗时。k-近邻算法的另一个缺陷是它无法给出任何数据的基础结构信息，因此我们也无法知晓平均实例样本和典型实例样本具有什么特征。下一章我们将使用决策树方法处理分类问题，该算法可以解决这个问题。www.islide.ccThanks

宁夏大学

第5章决策树算法决策树算法www.islide.cc23目录

CONTENT01引言02算法概述03实验数据04算法实战05本章小结01引言引言——故事导入

某公司想招聘机器学习算法工程师，HR可能会先看应聘者是否在顶级会议上发表过论文，如果发表过的话则直接录用；否则，看应聘者是否为研究生。如果是并且读研期间做的项目是和机器学习有关的，则录用；若不是研究生，则看成绩是否是年纪前10，是的话则录用否则留待考察。

决策树的工作原理与上述过程类似，即为达到目标根据一定的条件进行不断选择。

究竟何为决策树？

决策树，顾名思义，就是一种树形结构，其中树中的每个内部节点表示一个属性的判断，每个分支代表一个判断结果的输出，每个叶节点代表一种分类结果。引言

决策树算法作为一种非参数的监督学习方法，它主要用于分类，应用十分广泛。在风险评估、数据分类、专家系统等领域均有涉及，例如：专家系统中经常使用决策树，而且决策树给出的结果往往可以匹敌在当前领域具有几十年工作经验的人类专家。

第四章介绍的k-近邻算法可以完成很多分类任务，但是它最大的缺点就是无法给出数据的内在含义。而本章所讲的决策树，主要优势就是数据形式容易理解，具有非常好的可解释性。

本章将学习如何从一堆原始数据中构造决策树，讨论构造决策树的方法，编写构造树的Python代码，递归建立分类器以及使用graphviz包绘制决策树图。02算法概述算法定义

决策树是附加概率结果的一个树状的决策图，是直观的运用统计概率分析的图法。机器学习中决策树是一个预测模型，它表示对象属性和对象值之间的一种映射，树中的每一个内部节点表示对象属性的判断条件，其分支表示符合节点条件的对象，其叶子节点表示对象所属的预测结果。

这里为方便理解，以银行客户贷款资格评估为例：算法定义通过上面的例子，很容易理解一下两点：一、决策树算法的本质就是树形结构。这里需要了解以下三个有关树结构的概念：​ （1）根节点：就是树最顶端的节点，没有进边，只有出边。​ （2）中间节点：既有进边也有出边，但进边有且仅有一条，而出边可以有很多条。​ （3）叶节点：树最底部的节点，也就是决策结果，每个叶节点代表一个类别标签。只有进边，没有出边，进边有且只有一条。二、决策树其实就是一个if-then规则的集合。

由决策树的根节点到叶节点的每一条路径构建出一条规则，路径上中间节点的特征对应着规则的条件，叶节点的类标签对应着规则的结论。

决策树的路径或者其对应的if-then规则集合有一个重要的性质：互斥并且完备。

接下来将讲解决策树如何构建？1、特征选择

特征选择就是决定用哪个特征来划分特征空间，其目的在于选取对训练数据具有分类能力的特征，这样可以提高决策树学习的效率。如果利用一个特征进行分类的结果与随机分类的结果没有很大的差别，则称这个特征是没有分类能力的，经验上扔掉这些特征对决策树学习的精度影响不会很大。

那如何来选择最优的特征来划分呢？

一般而言，随着划分过程不断进行，要求决策树的分支节点所包含的样本尽可能属于同一类别，也就是节点的纯度越来越高。下面三个图表示的是纯度越来越低的过程，最后一个表示的是纯度最低的状态。1.1香农熵及计算函数

1.2信息增益

1.3信息增益率

1.4Gini系数

2.1决策树的生成

得到原始数据集后，依据特征选择的要求，利用最大信息增益的属性值划分数据集。由于特征值可能多于两个，因此可能存在大于两个分支的数据集划分。第一次划分之后，数据集被向下传递到树的分支的下一个结点。在这个结点上，再次划分数据，即采用递归的原则处理数据集。递归结束的条件是：程序遍历完所有的特征列，或者每个分支下的所有实例都具有相同的分类。如果所有实例具有相同分类，则得到一个叶节点。任何到达叶节点的数据必然属于叶节点的分类，即叶节点里面必须是标签。2.1决策树的生成构造流程如下：​

（1）开始：构建根节点，将所有训练数据都放在根节点，选择一个最优特征，按着这一特征将训练数据集分割成子集，使得各个子集有一个在当前条件下最好的分类。​

（2）如果这些子集已经能够被基本正确分类，那么构建叶节点，并将这些子集分到所对应的叶节点去。​

（3）如果还有子集不能够被正确的分类，那么就对这些子集选择新的最优特征，继续对其进行分割，构建相应的节点。递归进行，直至所有训练数据子集被基本正确的分类，或者没有合适的特征为止。

（4）每个子集都被分到叶节点上，即都有了明确的类，生成一棵决策树。2、决策树的生成

构建决策树的算法有很多，比如ID3、C4.5和CART。这三个都是非常著名的决策树算法，三者的区别简言之，即ID3使用信息增益作为选择特征的准则；C4.5使用信息增益比作为选择特征的准则；CART使用Gini指数作为选择特征的准则。本实验选用ID3算法来进行相关实验。

ID3算法的核心是在决策树各个节点上对应信息增益准则选择特征，递归地构建决策树。具体流程如下：​

（1）从根节点开始，对节点计算所有可能的特征的信息增益，选择信息增益最大的特征作为节点的特征，由该特征的不同取值建立子节点。​

（2）再对子节点递归地调用以上方法，构建决策树。​

（3）直到所有特征的信息增益均很小或没有特征可以选择为止，从而得到一棵决策树。3、决策树的剪枝

决策树生成算法递归地产生决策树，直到不能继续下去未为止。这样产生的树往往对训练数据的分类很准确，但对未知的测试数据的分类却没有那么准确，非常容易出现过拟合现象。过拟合的原因在于学习时过多地考虑如何提高对训练数据的正确分类，从而构建出过于复杂的决策树。解决这个问题的办法是考虑决策树的复杂度，对已生成的决策树进行简化，也就是常说的剪枝处理。3、决策树的剪枝

剪枝策略有预剪枝和后剪枝两种.

预剪枝指在完全正确分类之前，决策树会较早地停止树的生长，其中停止生长的方法分为通用的停止和严格的停止两种，通用停止即当所有样本均属同一类或样本的所有的特征值都相同时，终止递归，严格停止则限制深度、叶子节点个数、叶子节点样本数、信息增益量等，比如指定到某一具体数值后不再进行分裂。

与预剪枝不同，后剪枝首先通过完全分裂构造完整的决策树，允许过拟合，然后采取一定的策略来进行剪枝操作。常用的后剪枝策略包括：降低错误剪枝、悲观错误剪枝、基于错误剪枝、最小错误剪枝等，其中常用方法是降低错误剪枝，是最简单粗暴的一种后剪枝方法，其目的减少误差样本数量。4、决策树的存储和可视化

构造决策树是很耗时的任务，即使处理很小的数据集，也要花费几秒的时间，如果数据集很大，将会耗费很多计算时间。因此为了节省时间，建好树之后立马将其保存，后续使用直接调用即可。

决策树的主要优点就是直观易于理解，如果不能将其直观地显示出来，就无法发挥其优势。python目前并没有提供绘制树的工具，所以必须自行绘制树形图。可通过Matplotlib包来一步步实现，也可通过sklearn中的Graphviz包实现。前者需要绘制节点，标注有向边属性值，以及计算叶子节点数目等，而且还需要实现递归，操作难度较大。而后者具有一些封装好的函数辅助绘制，可大大降低绘制的工作量，故本实验采取后者的方式。03实验数据1、数据集介绍

隐形眼镜数据集是非常著名的数据集，它包含很多患者眼部状况的观察条件以及医生推荐的隐形眼镜的类型。其中，隐形眼镜类型包括硬材质(hard)、软材质(soft)以及不适合佩戴隐形眼镜(nolenses)。特征有四个：age（年龄）、prescript（症状）、astigmatic（是否散光）、tearRate（眼泪数量）。​

数据来源于UCI数据库：/ml/datasets/lenses。为了更容易地显示数据，本实验从UCI数据库中选取部分作为实验数据，并存放于lenses.txt文本文件中。2、导入数据集

利用数据分析的pandas包，将lenses.txt文本文件解析为tab键分隔的数据行。

文本数据处理后如右图所示：3、划分训练集和测试集

导入数据集后，按照一定比例地要求，将原始数据集分为训练集和测试集两部分。为保证数据地随机分配，采用打乱索引的方式打乱数据顺序。值得注意的是，由于这里采用随机索引的方式，导致每次切分的数据集并不相同。

本实验以0.8的比例（rate=0.8）划分数据集，划分后的训练集（左图）和测试集（右图）如下所示：04案例实战1、计算香农熵

根据熵的计算公式，将该计算公式封装为calEnt（）函数。2、数据集最佳切分函数

根据ID3算法，以最大信息增益作为切分数据集的依据。遍历数据集中的所有特征列，先对每一特征列下的所有取值进行循环，求出信息熵，进而求出所在列的信息增增益，最终通过判断找到最大信息增益以及其所在列的特征。3、按照给定列切分数据集

通过最佳切分函数返回最佳切分列的索引，根据这个索引，构建一个按照给定列切分数据集的函数。4、递归构建决策树

依据最大信息增益原则，找到代表根节点的特征，进而对数据集进行切分，创造决策树的分支。再将切分后的数据集作为再次判断的数据集，寻找具有最大信息增益的特征，再进行进一步划分。如此进行，即采用递归的方式不断进行，直至所有特征的信息增益均很小或没有特征可以选择为止，停止决策树生长。5、利用训练集生成决策树调用函数生成决策树。此时，生成的决策树是采用字典嵌套的方式进行存储，如下图所示：6、保存决策树

鉴于本实验数据的限制，以及本实验核心在于决策树的构建，故决策树剪枝部分的内容大家课后进行自我补充学习。这里直接进入决策树的保存步骤，使用numpy包里面的save()函数，直接把字典形式的数据保存为.npy文件，调用的时候直接使用load()函数即可。7、预测测试集并计算准确率

对测试集中每一条数据进行循环，进而实现对每一个测试实例进行分类，并将预测结果追加到测试集最后一列。7、预测测试集并计算准确率

调用acc_classify()函数后，隐形眼镜数据集的预测准确率达到0.6。下图即为测试集的预测情况：

从图中通过对class列和predict列的对比可见，第0、1、4行数据分类正确，第2、3行分类错误，即可再次证明其准确率为0.6.8、使用sklearn中graphviz包实现决策树的绘制

使用sklearn中的DecisionTreeClassifier()函数来构建决策树，但值得注意的是，它默认使用CART算法，这里可将其特征选择标准criterion参数值改为entropy，即ID3的信息增益。再通过export_graphviz()方法生成dot_data，此时的dot_data是一个字符串类型的数据，里面的内容则是之后要进行可视化的内容。最后利用graphviz.Source()将dot_data转换成可视化的格式。8、使用sklearn中graphviz包实现决策树的绘制完成绘制的决策树图，如右图所示：

从右图我们可以得出，

从根节点出发，判断眼泪数量是否满足小于等于0.5条件，若满足，则去向左