第4章 分类 上
面试官：说说分类与回归有什么区别？
程序员大树：分类是用来确定对象属于哪个类的，比如预测天气晴天与否。
回归用来预测一个具体的值，比如预测未来天气多少度。具体的区别方法如下：
（1）输入变量与输出变量均为连续变量的预测问题是回归问题（2）输出变量为有限个离散变量的预测问题为分类问题
（3）输入变量与输出变量均为变量序列的预测问题为标注问题
辨别分类和回归最有效的办法是看输出是否连续。这里将它们的特性简单列举如下：
| 特性 | 分类 | 回归 |
| 输出类型 | 离散数据 | 连续数据 |
| 目的 | 寻找决策边界 | 找到最优拟合 |
| 评价方法 | 精度、混淆矩阵、准确率（Accuracy）、FPR、FNR、Recall、Precision、F-score、MAP（Mean Average Precision）、ROC曲线和AUC | SSE、拟合优度、(r)MSE（(root) mean square error）、MAE（Mean Average Precision）、CC/PCC（Person's Correlation Coefficient） |
面试官：分类问题解决的一般思路是什么？怎么评价分类结果的好坏？
程序员大树：分类问题一般包括学习和分类两个步骤。学习过程中，根据已知的训练数据，使用有效方法训练一个分类器；在分类时，使用学习到的分类器对新的输入进行分类。(x1,y1),(x2,y2),...(xn,yn)
怎么评价分类结果的好坏？
程序员大树：评价分类器性能的指标一般是准确率(accuracy)，其含义是正确分类的样本数与总样本数之比。
对于二分类，常用指标是精准率(precision)和召回率(recall)。
首先定义四种总数：
TP: 将正类预测为正类数；
FN：将正类预测为负类数；
FP：将负类预测为正类数；
TN：将负类预测为负类数。
精确率的定义是：
精确率越高，模型分类效果越好。
召回率定义是：
召回率越高，代表实际负样本被预测出来的概率越高。
F1越高，说明整体表现越好。
另外，ROC曲线是显示分类器TPR和FPR的一种图形化方法。ROC曲线下方面积为AUC，是一种评价模型平均性能的方法，若模型完美，则面积为1。AUC面积越大，模型的分类效果越好。
面试官：有哪些解决分类问题的方法？
程序员大树：
主要有决策树分类法、基于规则的分类法、最近邻分类法、神经网络、支持向量机和朴树贝叶斯法。
4.1 如何使用决策树进行分类？
面试官：什么是决策树模型？
程序员大树：
决策树是一种对实例进行分类的树形结构。决策树由结点和有向边组成。树中包含三种结点：
根结点：没有入边，但有零条或多条出边。内部结点：恰有一条入边和两条或多条出边。
叶结点或终结点：恰有一条入边，但没有出边。
在决策树中，非叶结点（包括根结点和内部结点）包含属性测试条件，用来区分不同特征的记录。
对记录进行分类时，从树的根结点开始，用测试条件检验记录，选择合适的分支，沿着该分支到达另一个内部结点，使用新的测试条件，或者到达叶结点。到叶结点后，叶结点的类称号就是该记录的分类结果。
面试官：怎么进行决策树的特征选择？
程序员大树：如果选取对训练数据有分类能力的特征，可以大大提高决策树的学习效率。特征选择的准则是信息增益或信息增益比。 （I）信息增益。信息增益表示得知特征X的信息而使得类Y的信息不确定性减少的程度。可以将集合D的经验嫡H(D)与特征A给定条件下D的经验条件嫡H(D|A)之差，定义为特征A对训练数据集D的信息增益g(D,A)，即
我们可以用算法计算信息增益。
输入：训练数据集D和特征A:
输出：特征A对训练数据集D的信息增益g(D,A)
（1）计算数据集D的经验熵H(D)。设有K个类
，k=1,2,3,...K。|D|为其样本个数。
（2）计算特征A对数据集D的经验条件熵H(D|A)。记子集
中属于类的样本集合是
。
（3）计算信息增益)
（II）信息增益比。因为信息增益大小是对训练集而言的，并没有绝对的意义，使用信息增益比可以进行校正。特征A对训练集D的信息增益比，定义为其信息增益与训练集D的经验熵H(D)之比：
面试官：有哪些决策树的生成算法？请介绍一下。
程序员大树：
决策树主要的生成算法主要有ID3算法以及C4.5算法。
（一）ID3算法。ID3算法的核心是在决策树各个结点使用信息增益准则选择特征，递归构建决策树。算法流程如下：
输入：训练集D，特征集A，阈值
输出：决策树T。
（1）若D中所有实例属于同一类，或 A=
（2）否则，计算A中各特征计算对D的信息增益，选增益最大的一个特征
（3）对第i个子节点，以
因为ID3算法只有树的生成，所以容易过拟合。
（二）C4.5算法。C4.5对ID3进行了改进，在生成过程中，使用信息增益比来选择特征。
算法流程如下：
输入：训练集D，特征集A，阈值
输出：决策树T。
（1）若D中所有实例属于同一类，或A=
（2）否则，计算A中各特征计算对D的信息增益比，选增益比最大的一个特征
（3）对第i个子节点，以
面试官：决策树为什么要剪枝？怎么进行剪枝？
程序员大树：使用生成算法生成决策树时，为了使训练数据更准确，往往会出现过拟合的情况，原因是为了正确分类，构建出了更复杂的决策树。所以要将已生成的决策树进行简化，这个过程就是剪枝。剪枝会将一些子树的结点裁掉，减小树的规模，从而简化树。决策树剪枝通过极小化损失函数实现。
决策树的损失函数 定义为：
输入：生成算法产生的整个树T，参数
输出：修剪后的子树
（1）计算每个结点的经验熵。
（2）递归地从树的叶结点向上回缩。若回缩后的损失函数值更小一些，则进行剪枝，即将父节点变设置成叶子节点
（3）重复（2），直到不能继续为止，得到损失最小的子树
面试官：有没有听说过CART算法？具体是怎么做的？
程序员大树：CART是分类与回归树模型，可以根据输入的随机变量X条件下输出随机变量Y的条件概率分布。
CART算法主要是由两步组成：
（1）决策树的生成：基于训练集生成决策树，生成的决策树尽可能地膨胀。 （2）决策树剪枝：用验证集，对已生成的树剪枝，用损失函数最小作为标准，选择最优子树。
CART算法具体过程：
输入：训练集D，基尼系数的阈值，样本个数阈值。
输出：决策树T。
算法从根节点开始，用训练集递归建立CART分类树。
(1)、对于当前节点的数据集为D，如果样本个数小于阈值或没有特征，则返回决策子树，当前节点停止递归。
(2)、计算样本集D的Gini系数，如果Gini系数小于阈值，则返回决策树子树，当前节点停止递归。
(3)、计算当前节点现有的各个特征的各个特征值对数据集D的Gini系数。
(4)、在所有可能的特征A以及它们所有可能的切分点a中，选择Gini系数最小的特征及其对应的切分点作为最优特征与最优切分点。依最优特征与最优切分点，从现结点生成两个子结点，将训练数据集依特征分配到两个子结点中去。
(5)、对左右的子节点递归的调用1-4步，生成决策树。
查看6道真题和解析