机器学习中的分类算法详细介绍一（KNN、决策树）

机器学习中的分类算法有：KNN算法、决策树、随机森林、SVM、极限学习机、多层感知机（BP神经网络）、贝叶斯方法。

1、KNN算法

关键知识：数据预处理（数据标准化）、K个邻居（需要由用户指定）、距离计算方式（需要考虑数据的特点）
核心思想：物以类聚人以群分，空间相近则类别相似
可以用于非数值类的统计数据的分类

1.1 算法流程

①准备样本数据（训练数据），对数据进行预处理（如：标准化、缺失值补充等）。
②计算测试样本点（测试数据）到其他每个样本点的距离（有L1距离[马氏距离]、L2距离[欧式距离]、余弦距离等等）。
③对每个测试样本点与所有训练数据的距离进行排序，然后选择出距离最小的K个点 [3] 。
④对K个点所属的类别进行比较，根据少数服从多数的原则，将测试样本点归入在K个点中占比最高的那一类 [3] 。

1.2算法流程示意图

在这里插入图片描述
1、将所有样本数据进行预处理，并构建样本空间；
2、输入一个新的数据Xu,并对Xu进行预处理；
3、计算新数据Xu到其他每个样本点的距离；
4、对新数据到所有样本点的距离进行排序，然后选择出距离最小的K个点，上图选出了5个点，可以得出k=5，W1:4；W2:0；W3:1；
5、对5个点所属的类别进行比较，根据少数服从多数的原则，将新的数据归入W1中。

1.3 优缺点

优点

KNN方法思路简单，易于理解，易于实现，无需估计参数

缺点

1、当样本不平衡时，容易偏向预测多类别。如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数
2、计算量大，需要计算每个测试数据与所有样本数据的距离

1.4 使用技巧

样本不平衡

对多数类数据进行均匀的下采样，使其类别频次与少数类相同

计算量大

对训练数据整体进行下采样，降低其空间密度，最终减少训练数据，但又不影响其分布特性

2、决策树

决策树是一种树形结构，由根结点、内部节点和叶子节点组成。其中每个内部节点表示一个属性上的测试，每个分支代表一个测试输出，每个叶节点代表一种类别。
核心思想：决策树的每一次分叉，都会使数据变得更纯。
关键知识：决策树是一个迭代过程，需要由终止条件；决策树判断纯度增益方式有三种：ID3(信息增益)、C4.5(信息增益率)、CART(基尼系数)

更多信息参考 https://aistudio.baidu.com/aistudio/projectdetail/1700924?ad-from=1636

2.2 算法流程

基本流程如下，针对ID3、C4.5、CART各有差异。
1、构建根节点。（将所有的数据都汇集到一起）
2、遍历树的所有未划分节点，判断当前节点是否需要继续划分
3、遍历当前节点的所有可用特征，尝试用该特征对数据进行划分，计算出划分后的子节点纯度增益信息
4、比较步骤二中各种特征划分后的数据纯度信息，选择纯度增益最大的特征做子节点，并删除本步骤使用的特征（越分叉，可用特征越少；父节点特征，不会在子节点二次利用）
5、回到步骤二

算法流程图如下所示：
在这里插入图片描述
图片引用自https://blog.csdn.net/qq_43517635/article/details/105992863

2.3 ID3算法

以信息增益来度量特征选择，选择信息增益最大的特征进行分裂。算法采用自顶向下的贪婪搜索遍历可能的决策树空间，最终会划分到每一个叶子节点都很纯。
基本概念有信息熵、条件熵、信息增益。熵：描述信息的混乱程度（不确定性），越大表示信息越混乱

信息熵：是度量样本集合“纯度”最常用的一种指标。
计算公式：下面公式中：p(i|t) 代表了节点 t 为分类 i 的概率，信息熵Ent(D)的值越小，其纯度越高。
在这里插入图片描述

条件熵：以某条件对数据进行划分后的信息熵（划分后的数据要乘以其再原始数据中的占比）
计算公式：在这里插入图片描述

信息增益：信息熵 - 条件熵；条件熵小于信息熵；信息增益越大表示使用该特征来划分所获得的“纯度提升越大”
计算公式：公式中 D 是父亲节点，Di 是子节点，Gain(D,a)中的 a 作为 D 节点的属性选择。
在这里插入图片描述

缺点

ID3 没有剪枝策略，容易过拟合；
信息增益准则对可取值数目较多的特征有所偏好，类似“编号”的特征其信息增益接近于 1；
只能用于处理离散分布的特征，对于连续的数值无法进行处理；
没有考虑缺失值。

2.4 C4.5算法

C4.5 算法最大的特点是克服了 ID3 对特征数目的偏重这一缺点，引入信息增益率来作为分类标准，减少了模型对属性值较多时的分类偏好。具体改进有：
1、引入了悲观剪枝方法的后剪枝策略
2、提出了使用信息增益率作为划分标注
3、提出连续特征的离散化（按照阶段范围对数据进行离散，如按照成绩值评出优、良、中、差、等离散类别）
4、提出了对缺失值的处理方法

信息增益率：
计算公式：属性a的可能取值数目越多，则IV(a)越大。
在这里插入图片描述

缺失值处理方法

1、在有缺失值时如何计算信息增益率？
属性完整率*完整属性的信息增益率=有缺失值的信息增益率
例如：100个数据，对于属性A，其中25个属性值缺失，使用75个数据计算出的信息增益为0.3，
属性A的信息增益率为0.75（属性完整率）*0.3（完整属性的信息增益率）

关键点：对于缺失数据计算信息增益率不一定会将该属性选择为叶子节点

2、有缺失值的特征作为叶子节点时该如果操作？
先将有值的数据进行划分，得到其在各个子节点的划分比例。对于有缺失值的属性，按照权重（划分比例）将其分配到子节点中。
例如：100个数据，对于属性A，其中25个属性值缺失，其被作为划分节点，对于有值的属性划分后50个为左叶子、25个为右叶子。
缺失属性的数据同时进入两个叶子节点，只是其在右叶子节点时，每个数据的权重为2/3，而在左叶子节点时，每个数据的权重为1/3

关键点：缺失数据按照权重同时进入多个叶子节点

预剪枝策略

在节点划分前来确定是否继续增长，及早停止增长的主要方法如下。其本质为决策树迭代的终止条件，可补充到ID3算法中
（1）节点内数据样本低于某一阈值；
（2）所有节点特征都已分裂（其父节点把所有可用特征都进行利用）；
（3）节点划后准确率下降了；
（4）预剪枝不仅可以降低过拟合的风险而且还可以减少训练时间，但另一方面它是基于“贪心”策略，会带来欠拟合风险。

悲观后剪枝策略

在已经生成的决策树上进行剪枝，从而得到简化版的剪枝决策树，可以有效抑制过拟合。

用递归的方式从低往上针对每一个非叶子节点，评估用一个最佳叶子节点去代替这课子树是否有益。如果剪枝后与剪枝前相比其错误率是保持或者下降，则这棵子树就可以被替换掉。

后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树。但同时其训练时间会大的多。

缺点

1、剪枝策略可用在优化
2、使用多叉树树，计算效率不足，应使用二叉树
3、计算熵时存在对数运算，在数值离散化时需要进行排序
4、只能用于分类，不能用于回归
5、在构造树的过程中，需要按照属性值进行排序，从中找到合适的分割点，其要求能一次性将数据加载到内存中。

2.5 CART

CART（Classification and Regression Tree，分类回归树），从名字就可以看出其不仅可以用于分类，也可以应用于回归。CART 算法的二分法可以简化决策树的规模，提高生成决策树的效率。其包含的基本过程有分裂，剪枝和树选择：
分裂： Gini 系数作为变量的不纯度量；分裂过程是一个二叉递归划分过程，其输入和预测特征既可以是连续型的也可以是离散型的，CART 没有停止准则，会一直生长下去；
剪枝：采用代价复杂度剪枝，从最大树开始，每次选择训练数据熵对整体性能贡献最小的那个分裂节点作为下一个剪枝对象，直到只剩下根节点。CART 会产生一系列嵌套的剪枝树，需要从中选出一颗最优的决策树；
树选择：用单独的测试集评估每棵剪枝树的预测性能（也可以用交叉验证）。

Gini 系数，越小越好，表示数据越纯（与熵类似，与信息增益和信息增益率相反），反映了从数据集中随机抽取两个样本，其类别标记不一致的概率。基尼指数本质是对信息增益的一种改进方法（为信息熵的一阶泰勒展开），其还是偏向于特征值较多的特征（可以参考信息增益率改进Gini系数，但未必需要改进）。基尼指数可以用来度量任何不均匀分布，是介于 0~1 之间的数，0 是完全相等，1 是完全不纯。

计算公式：在这里插入图片描述
Gini(D)反映了从数据集D中随机抽取两个样本,其类别标记不一致的概率。其值越小，则纯度越高。
而属性a的基尼指数可以定义为如下公式：

优点

1、CART 采用二叉树进行构建，运算速度更快；
2、CART 既可以分类也可以回归；
3、CART 使用 Gini 系数作为变量的不纯度量，减少了以前熵模型中大量的对数运算
4、CART 可用消除类别不平衡所带来的影响；
5、CART 采用“基于代价复杂度剪枝”方法进行剪枝

类别不平衡处理

确保叶子节点与父节点的先验相等，及用叶子节点类别A的数据量除以父节点类别A的数据量得到Ra，依次类推分别得到Rb，Rc，选择最大的Rx所表示的类别来表示当前叶子的类别。其只进行了类内的频次比较，故而消除了类别数量不平衡的影响。
例如：
父节点类别A数为100，类别B数为1000，子节点类别A数位80，类别B数为200
Ra=80/100=0.8，Rb=200/1000=0.2，所以该子节点表示的类别为类别A。

连续值处理方法

CART 分类树采用基尼系数的大小来度量特征的各个划分点
CART 回归树采用方差度量方式来度量特征的各个划分点。对于任意划分特征 A，对应的任意划分点 s 两边划分成的数据集 D1和 D2，求能使D1和 D2各自集合的均方差最小点。

回归应用

回归是指预测一个连续的数值，CART 回归树先以常规方法进行树构建，然后在预测时以数据所对应的叶子节点数据中的标签值的中位数或平均值来作为预测结果。