1、支持向量机 SVM

2、逻辑回归

问题一：逻辑回归相比于线性回归，有何异同？

逻辑回归与线性回归的区别：

• 最本质的区别：逻辑回归处理的是分类问题，线性回归处理的是回归问题
• 最大的区别：逻辑回归的因变量是离散的，逻辑回归的因变量是连续的

逻辑回归与线性回归的相同点：

• 二者都使用了极大似然估计来对训练样本进行建模
• 在求解超参数的过程中，都可以使用梯度下降的方法（因为都是监督学习）

问题二：当使用逻辑回归处理多标签的分类问题时，有哪些常见做法，分别应用于哪些场景，它们之间又有怎样的关系?

• 如果一个样本只对应于一个标签：
  • 可以假设每个样本属于不同标签的概率服从几何分布，使用多项逻辑回归进行分类
• 如果存在样本可能属于多个标签的情况：
  • 可以训练 k 个二分类的逻辑回归分类器
  • 第 i 个分类器用以区分每个样本是否可以归为第 i 类。训练该分类器时需要将标签重新整理为“第 i 类标签”和“非第 i 类标签”

3、决策树

决策树是一种自上而下，对样本数据进行树形分类的过程

• 决策树是一种监督模型，常被用于分类问题 or 回归问题

决策树的组成：

• 节点：
  • 内部节点：表示一个特征 or 属性
  • 叶节点：表示类别
• 有向边

决策树的生成过程：

• 特征选择
• 树的构造
• 树的剪枝

问题一：决策树有哪些常用的启发函数？

从若干不同的决策树中选取最优的决策树是一个 NP 完全问题，在实际中通常采用启发式学习的方法去构建一棵满足启发式条件的决策树。
不同决策树算法在构建树时所采用的启发式函数不同，即根据不同的准则来选取最优特征（和最优切分点）进行节点分裂

ID3——最大信息增益

ID3 算法根据最大信息增益的原则来选择最优特征，将样本划分到不同的子节点

信息增益的计算方法：

• 样本集合 D，类别数 K
• 数据集 D 的经验熵
  • 是数据集 D 中类别为 k 的样本数
• 特征 A 对于数据集 D 的经验条件熵
  • 是数据集 D 中特征 A 取值为第 i 个值时的样本子集
  • 是 中类别为 k 的样本子集
• 特征 A 对于数据集 D 的信息增益
  • 即用特征 A 对样本集合进行划分后不确定性的减少程度

C4.5 ——最大信息增益比

C4.5 算法根据最大信息增益比的原则来选择最优特征，将样本划分到不同的子节点

信息增益比的计算方法：

• 特征 A 对于数据集 D 的信息增益
• 数据集 D 关于特征 A 的取值熵
• 特征 A 对于数据集 D 的信息增益比

CART——最小基尼指数

CART 算法在每次迭代中选取基尼指数最小的特征及其对应的切分点，将样本划分到不同的子节点
CART 是一棵二叉树，每次按最优特征及最优切分点将节点分裂为左右子树

基尼指数（Gini）的计算方法：

• 基尼指数
  • 基尼指数描述的是数据的纯度，样本分布越集中，基尼指数越小
• 对于二分类问题，基尼指数
• 特征 A 的基尼指数
  • 特征 A 不同切分点划分出不同的 ，就有不同的基尼指数

三种决策树算法的差异：

评价标准（节点分裂的特征选择标准）：

• ID3 选择信息增益最大的特征最为最优特征
  • ID3 会倾向于选择取值较多的特征：因为信息增益反映的是给定条件后不确定性减少的程度，特征取值越多就意味着确定性越高，即条件熵越小，信息增益越大
    • 但这可能导致分类的泛化能力弱
• C4.5 选择信息增益比最大的特征作为最优特征
  • C4.5 是 ID3 的改进，在一定程度上对取值较多的特征进行惩罚，避免 ID3 出现过拟合的特性，提升决策树的泛化能力
• CART3 选择基尼指数最小的特征及其切分点作为最优特征和最优切分点

样本类型：

• ID3 只能处理离散型变量，不能处理连续型变量
• C4.5、CART 可以处理离散型、连续型变量

应用：

• ID3、C4.5 只能用于分类任务
• CART（分类回归树）既可以用于分类任务，也可以用于回归任务
  • 分类任务：采用基尼指数最小化进行特征选择
  • 回归任务：采用平方误差最小化进行特征选择

实现细节、优化过程：

• ID3 对样本特征缺失值比较敏感；C4.5 和 CART 可以对缺失值进行不同方式的处理
• ID3 和 C4.5 可以在每个节点熵产生多叉分支，且每个特征在层级之间不会复用；CART 每个节点只会产生两个分支，形成一棵二叉树，且每个特征可以被重复使用
• ID3 和 C4.5 通过剪枝来权衡树的准确性和泛化能力；CART 直接利用全部数据发现所有可能的树结构进行对比

问题二：如何对决策树进行剪枝？

剪枝的作用：避免决策树过拟合，提升模型泛化能力
两种剪枝方法：

• 预剪枝：在生成决策树的过程中提前停止树的增长
• 后剪枝：在已生成的过拟合决策树上进行剪枝

预剪枝

预剪枝的核心思想：在树中节点进行扩展之前，先计算当前的划分是否能带来模型泛化能力的提升，如果不能，则不再继续生长子树

• 此时，一个节点中可能存在不同类别的样本，按照多数投票的原则判断该节点所属的类别

预剪枝对于何时停止决策树的生长有几种不同方法：

• 当树达到一定深度的时候，停止树的生长
• 当达到当前节点的样本数量小于某个阈值时，停止树的生长
• 计算每次分裂对测试集的准确度提升，当小于某个阈值时，不再继续扩展

预剪枝的优点：

• 思想直接、算法简单、效率高，适合解决大规模问题

预剪枝的缺点：

• 如何准确估计何时停止树的生长，针对不同问题会有很大差别，需要一定的经验判断
• 存在欠拟合的风险

后剪枝

后剪枝的核心思想：让算法生成一棵完全生长的决策树，然后从最底层向上计算是否剪枝

• 剪枝过程将子树删除，用一个叶子节点代替，该节点的类别同样按照多数投票的原则进行判断

后剪枝决定是否剪枝的方法：eg. 如果剪枝后，在测试集上的准确率有所提升，则进行剪枝

后剪枝的优点：

• 相比预剪枝，后剪枝通常能得到泛化能力更强的决策树

后剪枝的缺点：

• 时间开销会更大

CART 的剪枝方法：CCP 代价复杂度剪枝

1. 从完整决策树 开始，生成一个子树序列 ，其中，裁剪 中关于训练数据集误差增加最小的分支以得到 ， 是树的根节点
2. 在子树序列中，根据真实误差最小化选择最佳的决策树。有两种策略：
   • 使用独立的剪枝数据集（测试集）
   • 不使用额外的测试集，而是基于 k 折交叉验证，将训练数据集分为 k 份，前 k-1 份用于生成决策树，最后一份用于选择最优的剪枝树。重复进行 N 此，再从这 N 个子树中选择最优的子树