【机器学习3】有监督学习经典分类算法

1 支持向量机

在现实世界的机器学习领域， SVM涵盖了各个方面的知识， 也是面试题目中常见的基础模型。

SVM的分类结果仅依赖于支持向量，对于任意线性可分的两组点，它
们在SVM分类的超平面上的投影都是线性不可分的。

2逻辑回归

2.1逻辑回归与线性回归

逻辑回归处理的是分类问题， 线性回归处理的是回归问题， 这是两者的最本质的区别。 逻辑回归中给定自变量和超参数后， 得到因变量的期望， 并基于此期望来处理预测分类问题。 逻辑回归与线性回归最大的区别， 即逻辑回归中的因变量为离散的，而线性回归中的因变量是连续的。 并且在自变量x与超参数θ确定的情况下， 逻辑回归可以看作广义线性模型（Generalized Linear Models）在因变量y服从二元分布时的一个特殊情况； 而使用最小二乘法求解线性回归时， 我们认为因变量y服从正态分布。
逻辑回归和线性回归的相同之处二者都使用了极大似然估计来对训练样本进行建模，另外， 二者在求解超参数的过程中， 都可以使用梯度下降的方法。

2.2 逻辑回归处理多标签的分类

如果一个样本只对应于一个标签， 我们可以假设每个样本属于不同标签的概率服从于几何分布， 使用多项逻辑回归（Softmax Regression）来进行分类：

一般来说， 多项逻辑回归具有参数冗余的特点， 即同时加减一个向量后预测结果不变。 特别地， 当类别数为2时：

利用参数冗余的特点， 我们将所有参数减去θ1， 式子变为：

整理后的式子与逻辑回归一致。 因此， 多项逻辑回归实际上是二分类逻辑回归在多标签分类下的一种拓展。
当存在样本可能属于多个标签的情况时， 我们可以训练k个二分类的逻辑回归分类器。 第i个分类器用以区分每个样本是否可以归为第i类， 训练该分类器时， 需要把标签重新整理为“第i类标签”与“非第i类标签”两类。

3决策树

决策树的生成包含了特征选择、 树的构造、 树的剪枝三个过程。将决策树应用集成学习的思想可以得到随机森林、 梯度提升决策树等模型。

3.1几种常用的决策树对比

常用的决策树算法有ID3、 C4.5、 CART

3.1.1 ID3最大信息增益

对于样本集合D， 类别数为K， 数据集D的经验熵表示为：

其中Ck是样本集合D中属于第k类的样本子集， |Ck|表示该子集的元素个数， |D|表示样本集合的元素个数。
计算某个特征A对于数据集D的经验条件熵H(D|A)为：

Di表示D中特征A取第i个值的样本子集， Dik表示Di中属于第k类的样本子集。
信息增益g(D,A)可以表示为二者之差， 可得：

3.1.2 C4.5最大信息增益比

特征A对于数据集D的信息增益比定义为：

3.1.3 CART最大基尼指数（ Gini）

Gini描述的是数据的纯度， 与信息熵含义类似。

CART在每一次迭代中选择基尼指数最小的特征及其对应的切分点进行分类。但与ID3、 C4.5不同的是， CART是一颗二叉树， 采用二元切割法， 每一步将数据按特征A的取值切成两份， 分别进入左右子树。 特征A的Gini指数定义为:

通过对比三种决策树的构造准则， 我们不难总结三者之间的差异。

区别	ID3	C4.5	CART
评价标准	信息增益	信息增益比	基尼指数
样本类型	离散型变量	连续型变量	连续型变量
应用角度	分类	分类	分类/回归
缺失值	对样本特征缺失值敏感	对缺失值进行不同方式的处理	对缺失值进行不同方式的处理
实现	在每个结点上产生出多叉分支，每个特征在层级之间不会复用	在每个结点上产生出多叉分支，每个特征在层级之间不会复用	每个结点只会产生两个分支，且每个特征可以被重复使用
优化过程	通过剪枝来权衡树的准确性与泛化能力	通过剪枝来权衡树的准确性与泛化能力	直接利用全部数据发现所有可能的树结构进行对比

3.2不同剪枝方法的区别和联系

一棵完全生长的决策树会面临一个很严重的问题， 即过拟合。 需要对决策树进行剪枝， 剪掉一些枝叶， 提升模型的泛化能力。决策树的剪枝通常有两种方法， 预剪枝（Pre-Pruning） 和后剪枝（PostPruning）

3.2.1 预剪枝

预剪枝， 即在生成决策树的过程中提前停止树的增长。
预剪枝的核心思想是在树中结点进行扩展之前， 先计算当前的划分是否能带来模型泛化能力的提升， 如果不能， 则不再继续生长子树。 预剪枝对于何时停止决策树的生长有以下几种方法。

3.2.2后剪枝

后剪枝， 是在已生成的过拟合决策树上进行剪枝， 得到简化版的剪枝决策树。
后剪枝的核心思想是让算法生成一棵完全生长的决策树， 然后从最底层向上计算是否剪枝。剪枝过程将子树删除， 用一个叶子结点替代， 该结点的类别同样按照多数投票的原则进行判断。
常见的后剪枝方法包括错误率降低剪枝（Reduced Error Pruning， REP） 、 悲
观剪枝（Pessimistic Error Pruning， PEP） 、 代价复杂度剪枝（Cost Complexity Pruning， CCP） 、 最小误差剪枝（Minimum Error Pruning， MEP） 、 CVP（Critical Value Pruning） 、 OPP（Optimal Pruning） 等方法