百面机器学习之经典算法

        首先，逻辑回归处理的是分类问题，线性回归处理的是回归问题，这是两者的最本质的区别。逻辑回归中，因变量取值是一个二元分布，模型学习得出的是 ，即给定自变量和超参数后，得到因变量的期望，并基于此期望来处理预测分类问题。而线性回归中实际上求解的是 ，是对我们假设的真实关系的一个近似，其中代表误差项，我们使用这个近似项来处理回归问题。

        当然逻辑回归和线性回归也不乏相同之处，首先我们可以认为二者都使用了极大似然估计来对训练样本进行建模。线性回归使用最小二乘法，实际上就是在自变量x 与超参数 θ 确定，因变量 y 服从正态分布的假设下，使用极大似然估计的一个化简；而逻辑回归中通过对似然函数的学习，得到最佳参数θ 。另外，二者在求解超参数的过程中，都可以使用梯度下降的方法，这也是监督学习中一个常见的相似之处。

        使用哪一种办法来处理多分类的问题取决于具体问题的定义。首先，如果一个样本只对应于一个标签，我们可以假设每个样本属于不同标签的概率服从于几何分布，使用多项逻辑回归（Softmax Regression ）来进行分类

        当存在样本可能属于多个标签的情况时，我们可以训练 k 个二分类的逻辑回归分类器。第i 个分类器用以区分每个样本是否可以归为第 i 类，训练该分类器时，需要把标签重新整理为“ 第 i 类标签 ” 与 “ 非第 i 类标签 ” 两类。通过这样的办法，我们就解决了每个样本可能拥有多个标签的情况。

首先，我们回顾一下这几种决策树构造时使用的准则。

■ ID3—— 最大信息增益

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

        其中 C k 是样本集合 D 中属于第 k 类的样本子集， | C k | 表示该子集的元素个数， | D | 表示

样本集合的元素个数。

        然后计算某个特征 A 对于数据集 D 的经验条件熵 H ( D | A ) 为

        其中， D i 表示 D 中特征 A 取第 i 个值的样本子集， D ik 表示 D i 中属于第 k 类的样本子集。

        于是信息增益 g ( D , A ) 可以表示为二者之差，可得

        这些定义听起来有点像绕口令，不妨我们用一个例子来简单说明下计算过程。假设共有5 个人追求场景中的女孩，年龄有两个属性（老，年轻），长相有三个属性（帅，一般，丑），工资有三个属性（高，中等，低），会写代码有两个属性（会，不会），最终分类结果有两类（见，不见）。我们根据女孩有监督的主观意愿可以得到表3.1 。

表 3.1 5 个候选对象的属性以及女孩对应的主观意愿

根据上面的式子 计算出 4 个分支结点的信息熵为

于是， 可计算出各个特征的信息增益为

        显然，特征 “ 写代码 ” 的信息增益最大，所有的样本根据此特征，可以直接被分到叶结点（即见或不见）中，完成决策树生长。当然，在实际应用中，决策树往往不能通过一个特征就完成构建，需要在经验熵非0 的类别中继续生长。

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

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

其中

称为数据集 D 关于 A 的取值熵。针对上述问题，我们可以根据上式 求出数据集关于每个特征的取值熵为

于是， 可计算出各个特征的信息增益比为

        信息增益比最大的仍是特征 “ 写代码 ” ，但通过信息增益比，特征 “ 年龄 ” 对应的指标上升了，而特征“ 长相 ” 和特征 “ 工资 ” 却有所下降。

■ CART—— 最大基尼指数（ Gini ）

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

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

还是考虑上述的例子，应用 CART 分类准则，根据上式 可计算出各个特征的Gini 指数为

        在 “ 年龄 ”“ 长相 ”“ 工资 ”“ 写代码 ” 四个特征中，我们可以很快地发现特征 “ 写代码” 的 Gini 指数最小为 0 ，因此选择特征 “ 写代码 ” 作为最优特征， “ 写代码 = 会 ” 为最优切分点。按照这种切分，从根结点会直接产生两个叶结点，基尼指数降为0 ，完成决策树生长。

        通过对比三种决策树的构造准则，以及在同一例子上的不同表现，我们不难总结三者之间的差异。

        首先， ID3 是采用信息增益作为评价标准，除了 “ 会写代码 ” 这一逆天特征外，会倾向于取值较多的特征。因为，信息增益反映的是给定条件以后不确定性减少的程度，特征取值越多就意味着确定性更高，也就是条件熵越小，信息增益越大。这在实际应用中是一个缺陷。比如，我们引入特征“DNA” ，每个人的 DNA 都不同，如果ID3 按照 “DNA” 特征进行划分一定是最优的（条件熵为 0 ），但这种分类的泛化能力是非常弱的。因此，C4.5 实际上是对 ID3 进行优化，通过引入信息增益比，一定程度上对取值比较多的特征进行惩罚，避免ID3 出现过拟合的特性，提升决策树的泛化能力。

        其次，从样本类型的角度， ID3 只能处理离散型变量，而 C4.5 和 CART 都可以处理连续型变量。C4.5 处理连续型变量时，通过对数据排序之后找到类别不同的分割线作为切分点，根据切分点把连续属性转换为布尔型，从而将连续型变量转换多个取值区间的离散型变量。而对于CART ，由于其构建时每次都会对特征进行二值划分，因此可以很好地适用于连续性变量。

        从应用角度， ID3 和 C4.5 只能用于分类任务，而 CART （ Classification and Regression Tree，分类回归树）从名字就可以看出其不仅可以用于分类，也可以应用于回归任务（回归树使用最小平方误差准则）。

        此外，从实现细节、优化过程等角度，这三种决策树还有一些不同。比如，ID3对样本特征缺失值比较敏感，而 C4.5 和 CART 可以对缺失值进行不同方式的处理；ID3 和 C4.5 可以在每个结点上产生出多叉分支，且每个特征在层级之间不会复用，而CART 每个结点只会产生两个分支，因此最后会形成一颗二叉树，且每个特征可以被重复使用；ID3 和 C4.5 通过剪枝来权衡树的准确性与泛化能力，而 CART直接利用全部数据发现所有可能的树结构进行对比。