3.3.1　文本分类方法

文本分类任务是自然语言处理领域中一个非常经典的问题，从早期专家系统分类，过渡到了基于统计学习的大规模文本分类，任务也从简单的二分类学习方法扩展到多分类学习问题。前面的特征工程完成文本预处理、特征提取、文本表示环节，建立学习方法的特征空间[7]。本小节介绍基本分类思想，结合线性分类的相关模型，最后介绍集成学习模型的介绍。

1.基本分类思想

（1）K近邻

K近邻代表着一类非常朴素的分类思想，就是样本在特征空间中，以其最相邻的K个样本中占多数的类别，形象地说是“投多数票的类别”为自己的分类标签。K近邻模型搭建依赖于距离度量、K值选择、分类决策规则三个部分。

在距离度量计算方面，最为常见的度量为欧氏距离。假设两个特征向量分别用x=[x₁, x₂, ..., x_n]和y=[y₁, y₂, ..., y_n]表示，那么欧式距离的计算公式为

更一般化的距离度量为闵可夫斯基距离（Minkowski Distance），其计算公式为

其中，p是一个变参数。当p=1时，为曼哈顿距离；当p=2时，为欧氏距离；当p→∞时，为切比雪夫距离。

还可以用马哈拉诺比斯距离(Mahalanobis Distance)来度量，简称马氏距离，表示数据的协方差距离。给定一个样本集合X={x₁, x₂,..., x_i,..., x_n}，样本数量为n，每个样本的大小为m，x_i=(x_1i, x_2i, ..., x_mi) T。那么样本x_i与x_j的马哈拉诺比斯距离定义为，

其中，i, j=1, 2,..., m，S为协方差矩阵。当S为单位矩阵时，即样本数据各个分量相互独立且各个分量的方差为1，由式（3.4）可以看出马氏距离就是欧式距离，所以马氏距离是欧式距离的扩展。

考虑到样本集处于不同的特征空间，为了消除特征量纲的影响，需要对输入的样本特征向量进行标准化或滤除噪声。假设μ_i、σ_i分别为第i维特征对应的均值和方差，那么特征x_i归一化表示为

假设特征y_i归一化后用表示，归一化距离也被称为标准化欧氏距离（Standardized Eucli-dean distance），可用如下式子计算：

K近邻存在多种变形，通常用交叉验证选择最优K值。根据使用场景中的特征权重采用不同的距离度量方式。距离计算需要巨大开销，可用树结构加快最近邻样本搜索，找出一个样本的K个最近邻点。由于K近邻面临的样本特征可能很多，容易引发维数灾难，因此常常需要通过特征选择降维。分类决策规则通常是“多数表决”，统计最近邻点的类别频数，根据频数为样本类别打标签，最终输出最佳类别，这种策略对应于前述经验风险最小化的学习策略。因此，分类的关键在于如何找到合适的样本特征组合，并在某种距离度量方式下完成计算。一个基本K近邻的算法如下：

①计算测试数据与各个训练数据之间的距离。

②按照距离由近到远的顺序排序。

③选取距离最小的K点。

④确定前K个点所在类别的比例。

⑤选择比重最大的点作为当前K的类别。

（2）决策树

决策树基于特征选择和信息论进行分类的方法，也是后续集成学习模型（如随机森林、GBDT、XGBoost等）的基础。由于近邻方法无法给出数据的内在含义，决策树却可以通过if-then规则对数据特征的理解，在树状模型结构下像专家系统一样逐级判断，完成对样本归纳分类。决策树的基本分类思想可以用图3-5进行描述，描述了自顶向下递归方式的决策树构造过程。

决策树分类学习包括特征选择、决策树生成和决策树修剪3个步骤。特征选择依据信息增益、信息增益比、基尼系数，对应三种不同方法。

①ID3方法。根据样本集中类别与特征的互信息计算信息增益。假设有一组数据，设D为某一个特征类别，则根据熵的定义可以得到D的熵为

图3-5　决策树算法逻辑示例

其中，p_i表示第i个类别在整个训练元组发生的概率，在离散的随机过程中，p_i可以用出现的数量除以整个数据的总数量n的比值作为估计。由于对初始数据可以划分的类别不止一项，于是我们需要对已经进行D分类的数据再次分类。假设此次的类别为A，则特征A对数据集D划分的条件熵为

j={1, 2, ..., m}表示属性A的取值，共有m种取值。D_j表示取值j的样本集合。

一般来说，信息增益越大，那么用属性A划分获得纯度提升越大。因此，二者的差值即为信息增益

信息增益第一项是集合的经验熵，第二项是给定特征条件下D的经验条件熵。ID3算法采用信息增益度量，其目标是如何分裂来使∆A值达到最大，增益高的特征则被选择用于数据划分。从式子（3.37）和（3.38）可以看出，j的取值越多，信息增益的值越大，也就是说ID3算法偏向于选择取值多的特征进行划分。然而如果该属性的样本数比较少，尽管有很高的信息增益，这样的划分也不具有良好的泛化能力。

②C4.5决策树算法。C4.5算法是ID3算法的延伸和优化。从前面的内容可知，ID3方法优先选择有较多取值的特征，为了避免特征值多导致信息增益大的问题，C4.5采用信息增益率（Gain Ratio）指标选择划分属性，并引入“分裂信息（Split Information）”来惩罚取值较多的分类。分裂信息用来衡量特征分裂数据的广度和均匀性。信息增益率和分裂信息的计算分别对应式（3.39）和（3.40）。增益率本身对可取值数目较少的属性有所偏好，为避免这一不足，首先需要从候选划分特征中找出信息增益高于平均水平的特征，再筛选出增益率最高的特征。

③CART算法。对分类树而言，除了上述两种基于信息熵的方法以外，还可以用基尼系数（Gini）来度量决策条件的合理性。基尼系数衡量模型的不纯度，系数值越高，不纯度越低，特征越好，因此选择划分后基尼系数最小的特征作为划分特征。假设样本集合D，个数为|D|，假设有K个类别，第k个类别的数量为|C_k|，那么样本D的基尼系数的表达式为

根据特征A的某个值a，将D分割成D₁和D₂两部分（个数分别为|D₁|和|D₂|），则在特征A的条件下，集合D的基尼系数为

在所有可能的特征A以及所有可能的切分点a中，选择Gini系数最小的特征及其对应的切分点作为最优特征与最优切分点。继续对现结点进行切分，再分配特征，递归计算Gini系数，直至决策树生成。算法流程如下：

①遍历所有特征在根节点的Gini系数，选取最优特征作为分节点，并将当前特征从特征中移除。

②遍历所有特征在每个叶节点的Gini系数，并分别挑选最优特征作为分节点，并将使用的特征在当前子树中移除。

③直至无特征待选为止。

对于以上决策树方法，基尼系数趋向于选择孤立数据集中数量多的类，将它们分到一个叶节点中，而熵偏向于构建一棵分支平衡的树，因此要根据实际情况选择划分方法。上述方法如果不做任何限制，决策树拟合所有样本过程中产生“过拟合”现象，意味着不必要的决策分支出现了，因此需要进行“剪枝”提升泛化能力。

（3）朴素贝叶斯

前面两种分类讨论的都是“事实确定”的硬分类方法，分类事实明确，比如鸭梨是水果，而不是电视。但是多数时候我们只能基于概率论做概率意义上最优决策的软分类，比如“梅西多出现在体育新闻里，而不多见于政治新闻”。这种情况下最简单的分类方法就是基于贝叶斯决策理论的朴素贝叶斯方法。假设变量间相互独立，朴素贝叶斯方法就是根据贝叶斯定理（详见本书附录A）计算后验概率最大的事件用于文本分类。

朴素贝叶斯方法的基本思想是，对于给出的待分类项，求解此项出现的条件下各个类别出现的概率，待分类项的类别就是概率最大的类别。具体地，假设样本数据集有m个样本，用D={d₁, d₂,..., d_m}表示，每个样本有n个特征，对应特征集合为X={x₁, x₂, ..., x_n}。模型类别集合为Y={y₁, y₂, ..., y_k}，共有k个分类结果。分类结果Y条件下各特征x_i，i=1, 2, ...,n相互独立，如图3-6所示。假设待分类项为X，计算条件概率P(y₁|X), P(y₂|X),...,P(y_k|X)，如果类别满足P(y_i|X)=max(P(y₁|X), P(y₂|X),...,P(y_k|X))，则X∈y_j,i=1, 2,...,k。那么问题的关键就是如何计算上述各个条件概率？

图3-6　朴素贝叶斯分类模型样本假设

假设X={x₁, x₂,..., x_n}为一个待分类项，设模型的类别集合为Y={y₁, y₂, ..., y_k}，共有k个分类结果。计算条件概率p(y₁|x), p(y₂|x), ..., p(y_k|x)，如果找到满足如下条件的类别，即p(y_k|x)=max{p(y₁|x), p(y₂|x), ..., p(y_k|x)}，则x∈y_k。那么问题的关键就是如何计算上述各个条件概率。

通过训练样本学习可以得到朴素贝叶斯先验概率

其中，c_i表示样本集中y_i标签出现的次数。统计得到各类别下各个特征属性的条件概率估计，即P(X=x_i|Y=y_j)，其中，i=1, 2,..., n，j=1, 2, ..., k。根据贝叶斯定理，有

由于分母对所有类别为常数，我们只要将分子最大化即可，又因为各特征之间彼此独立，那么

通过找到使分子最大的类别y_i，则待分类项属于该类别。

朴素贝叶斯分类器的缺点是条件独立性假设太强，但由于模型简单，并且能有效防止过拟合，当样本较少时可以作为首选的分类测试方法。针对文本分类，可以利用一定的分词规则将文本切成一个个单词，然后去除停用词，如“了”“的”等没有实际语义的元素，选出尽可能能标识分类的词汇，降低维度选取样本特征，再应用朴素贝叶斯分类方法进行分类测试。

（4）线性回归

线性回归分类是一种几何直观的分类思想，利用决策超平面对样本特征空间的实例进行分类。一个线性模型由判别函数和非线性决策函数组成，假设有一个m维向量{x₁, x₂,…, x_m}T，可以由如下式子表示，

为了简化书写，可简化为，

其中，w=(w₀, w₁,..., w_m)T, x=(1, x₁,..., x_m)，为判别函数，可表示为f(x,w)。由于分类输出结果为类别标签，而f(x,w)是实数值，通过引入一个非线性决策函数g来预测分类结果y。决策函数可形象地表示为图3-7超平面中的直线l。

图3-7　线性分类示意图

当坐标点落在直线l上方时，则分类为C₁，坐标点落在直线l下方时，则分类为C₂。其他的分类方法也是基于线性分类思想，根据决策函数g、损失函数或学习策略的不同，产生了感知器、对数几率回归、最大熵、支撑向量机等分类模型。

2.从线性分类出发

（1）感知器

基于线性划分思想的分类模型由线性判别函数和非线性决策函数组成，在判别函数f相同的情况下，当决策函数g为符号函数（用sign表示）时就是感知器。感知器是模拟生物神经元的机器模型，是最简单的人工神经网络。

感知器算法的目标是找到能够准确分离正负例样本训练数据集的超平面。对于二分类问题，给定N个样本的训练集D，样本用(x_i, y_i)表示，i∈[1, N]。其中，x_i∈Rn，表示第i个样本在n个特征上的取值，y_i∈{−1,+1}表示样本是正例（+1）还是负例（-1）。线性回归模型用wx+b表示，模型参数为w和b，如果样本(x_i, y_i)满足wx_i+b>0，则y_i=−1，若wx_i+b<0，则y_i=−1，即∀i∈[1, N]，满足y_if(x_i,w,b)>0，y_i∈{−1,+1}。如果线性回归模型用f(x, w, b)表示，感知机可表示为

为了学习模型参数，需要建立损失函数。感知器参数学习的策略是最小化误分类点到超平面的距离，不考虑分母项。假设训练数据集有M个误分类点，损失函数可表示为

对分错的样本进行权重更新，是一种错误分类点驱动方法。利用随机梯度下降法最小化损失函数L(w, b)，学习算法包括原始形式和对偶形式。采用不同的初值或选取不同的误分类点，得到的参数解可能不同。训练过程中，随机选取部分误分类点使梯度下降，设学习率为η，训练优化步骤如下：

①选取初始w₀, b₀；

②选取训练集(x_i, y_i), i∈[1, N]；

③y_i(wx_i+b)≤0，则更新权值参数w和b；

④转至②，直至训练数据集没有误分类点，得到超平面最优参数w和b。

感知器解决的是线性分类凸优化问题，训练简单高效，具有可解释性，但是在有限假设类空间表示能力不足。有时候我们可能面对复杂的场景，比如分类决策的置信度计算问题，需要将二值分类问题通过概率值（比如sigmoid函数）计算进行决策，这就需要后面介绍的对数几率回归；根据点到判别函数的距离或投影距离进行分类，也就导出最大熵、SVM方法。

（2）对数几率回归

对于二分类问题建模，引入非线性决策函数g来预测类别y的类后验概率p(y=1|x)，也被称为条件概率，此时特征为x、g称为激活函数，它的目的是把线性函数的值归一化到[0, 1]之间，如式子（3.51）所示。模型称为对数几率回归，通常也称为逻辑回归（Logistic Regresssion, LR），表示具有特征x的样本被分为某类别的概率。

选择恰当的激活函数能让后验概率估计更为简单。由于单位阶跃函数不连续，为便于计算，激活函数选取近似单位阶跃函数的对数几率函数，也称为sigmoid函数，由于其连续且单调可微，可把线性预测转变为概率估计。假设给定N个训练样本，x=(x₁, x₂, ..., x_N)，y=(y₁, y₂, ..., y_N)，样本点用(x_i, y_i)表示，i∈[1, N]。Sigmoid函数σ(x)=将第i个样本的特征向量x_i与该样本为正例的概率联系起来，将其代入式子（3.51）中，结果如式子（3.52）所示。其中，σ(x_i)表示样本x_i为正例的可能性，则1−σ(x_i)表示样本x_i为负例的可能性，w和b为模型参数。

两者的比值称为几率（Odds），即事件发生的概率与该事件不发生的概率的比值，反映了样本x为正例的相对可能性。几率取对数为对数几率（Log Odds，也称为Logit），这就是对数几率回归模型名称的来历。对数几率回归表示为

对数几率模型采用最大似然估计（详见附录）来求解参数w和b。为便于讨论，令β=(w;b)，=(x ;1)，则wTx+b可简写为。再令p₁(;β)=p(y=+1| ;β)，p₀(;β)=p(y=−1|。; β)=1−p₁(; β)似然函数表示样本为真实的概率，对数似然函数可用如下式子表示

假设存在β，使得所有样本似然函数达到最大，此时β为最优参数。由于最优化问题倾向于解决最小值问题，可以引入一个负号转换为梯度下降法求解。梯度下降法求解参数的流程如下：

①按照输入的特征数量创建参数并初始化；

②计算损失；

③更新损失；

④重复②-③直至停止。

与朴素贝叶斯相比，对数几率回归没有条件独立假设，可运用梯度下降法来优化参数，模型输出样本为正例的概率，当f(x)＞0.5表示x被分为正例，f(x)＜0.5则被分为反例。对于多分类情况，概率向量通过softmax函数得到。

从本书附录A中的最大熵原理可知，在给定约束条件下熵最大的模型就是我们要找的模型。从最大熵原理的角度也可以推导出对数几率回归模型。对数几率回归是求条件概率分布关于样本数据的对数似然最大化。与对数几率回归类似，最大熵模型是在给定训练数据的条件下，求解分类模型的条件概率分布P(Y|X)，其中X为输入特征，Y为类别标签。两者的不同之处在于条件概率分布的表示上。最大熵模型联合P(Y|X)和边缘分布P(X)的经验分布，用特征函数f(x, y)表示x和y之间的关系，即前面所说的约束条件，它定义了给定输入变量x条件下输出y的条件概率分布：

其中，D(y)表示类别y的集合，类别总数为N，θ为模型参数。当y为二元结果{y₀, y₁}时，定义特征函数为“仅在y=y₁时取x的特征g(x)，在y=y₀时返回0”。将特征函数带入最大熵模型中，结果如式（3.56）所示。从该公式可以看出，最大熵模型与对数几率回归模型是等价的。

图3-8　SVM的超平面分类示意图

（3）SVM

当样本特征空间从二维扩展到高维时，这种情况下如何寻找线性几何划分超平面？SVM方法给出了获取最大化超平面间隔的思路：找到距离分类超平面最近的点，通过最大化这些点之间的间隔来求解。以线性可分的支持向量机二分类为例，两类数据点距离超平面的间隔如图3-8表示。

在支撑向量机中，由于边界点直接决定于分类线，每个数据点也是一个向量，所以边界点叫作支持向量（Support Vector）。支撑向量的定义是距离超平面最近且满足一定条件的几个训练样本点。我们知道，在n维空间中，向量x=(x₁, x₂, ..., x_n)到直线wTx+b=0的距离为，其中，||w||=。给定N个样本的训练集D，样本用（x_i, y_i)表示，i∈[1, N]。假设支撑向量到超平面的距离为d，那么其他点到超平面的距离大于d，如图3-8所示。于是可以给出

||w||×d为×正数，为了方便推导，我们暂且令它为1。稍做转化并将两个方程合并，得到

样本中支撑向量满足|wTx+b|=1，这些点到超平面的距离可以写为

最大化这个距离

进一步结合|wTx+b|=1，最优化问题变为

在实际应用中，完全线性可分的样本是很少的，如果遇到无法完全线性可分的样本，我们允许部分样本点不满足约束条件，因此引入一个松弛变量ε_i≥0。增加软间隔后优化目标变为

其中，C是一个大于零的常数。当C趋于无穷大，ε_i趋于零时，SVM变为线性可分SVM。

为了求解上述有约束的最优化问题，优化参数策略是应用拉格朗日乘子法和对偶性。由于目标函数为二次，约束条件为线性，所以最优化是一个凸二次规划问题，可以直接使用QP（Quadratic Programming）优化包求解。

当二分类样本极其不平衡时，可以将个数比例极小的部分当作异常点来处理，比如One Class SVM无监督学习，它采用了一个超球体而不是超平面来划分。在特征空间中对超球体的体积进行期望最小化，而超球体以外的部分则是异常点。这类情况在文本分类中也经常遇见。针对文本类样本的高维特征，SVM方法提供了另一种思路，定义非线性映射函数将数据映射到高维空间，即通过核函数法对两个向量进行数学运算以获得它们在高维空间的内积值，然后在映射后的空间执行线性分类。

（4）讨论与小结

根据前面的介绍，我们制作一批专利文本数据集，初步运用分类方法。首先进行文本预处理，文本特征选择和采样，这些决定了最终算法模型效果的好坏。本试验目标是将每一个专利文本分类到对应的国际类别标签（IPC）。由于专利文本与IPC分类相关的技术、关键词、产品名称等不同维度特征，直接采用过滤法进行特征选择。为了保证模型对于特征的敏感程度，尽可能地挑选了与分类数据相关的特征及特征组合字段。

Type：专利文本类型，包含发明、实用新型与外观三类。

Tfidf_cnt:计算词汇Tfidf值，并采用简单做了计数处理。

Tech、Problem、Func：使用了预处理的文本字段的词组合特征，与IPC分类描述相关。

AgentList与ApplicantList特征分别是对代理人和申请人数量的统计。就经验而言，代理人与申请人的属性与IPC分类存在较强的关系，因此也将它们的统计数量作为特征之一。

这里有两点需要特殊说明。一方面，在特征分析阶段，相关性交差、过于稀疏的特征无法适用于分类模型，可以直接排除；另一方面，在模型训练的过程中，较为简单的二进制特征与计数式连续型特征，其特征间数值范围基本保持在同等量级下。可以直接使用生成后的数值型特征作为模型训练的输入。而类别型特征，则需要将它们变化成向量，再进行计算。单类别特征如果种类繁多，会导致距离过大或过于稀疏，可以利用分箱等方法重新构建特征，或者在相关性较弱判断的情况下，抛弃当前特征。

将上述特征输入本节讨论的三个模型，分类结果如表3-3所示。尽管看起来三种方法相差不大，如果结合特征组合、可解释性需要，选择合适的模型算法就变得非常重要。

表3-3　感知器、LR和SVM模型分类结果对比

3.从决策树到集成学习

前面提到的决策树在可解释性和线性不可分样本分类中非常有效，但非常容易发生过拟合，泛化能力不好。那么是否可以扬长补短呢？目前人们普遍采用集成学习的方式。集成学习（Ensemble Learning）模型通过结合多个弱分类器的预测结果来改善泛化能力和鲁棒性，其中的弱分类器就是决策树。根据个体学习器的生成方式，大致分为两大类。一类是个体学习器间不存在强依赖关系并可同时生成的并行化方法，其中的代表是Bagging类“随机森林（Random Forest）”方法。另一类是个体学习器之间存在强依赖关系、必须串行生成的序列化方法，其中的代表是Boosting类方法。

（1）Bagging类

Bagging是Bootstrap Aggregating的缩写，基本思想是随机有放回的选择训练样本然后构造分类器，最后组合。可以简单地理解为：放回抽样，多数表决，并列生成，各分类器不存在强依赖关系。

随机森林是这种思路的具体实现，如图3-9所示，基本学习单元是决策树。随机采样样本，也随机选择特征。每一组随机采样都可以生成一个决策树，依靠多个决策树（视为决策森林），收集各树子节点对类别的投票，然后选择获得最多投票的类别作为分类结果。基于Bagging的随机森林，各分类相互独立。在树的建立过程中，随机选择特征子集来使各个树不同，因此防止过拟合能力更强。

学习策略方面，Bagging思想是利用Bootstrap方法采取有放回的重采样，为了保证抗过拟合能力，采用了行抽样和列抽样的随机化方法。对于行采样，采用有放回的方式，在训练的时候，每一棵树的输入样本都不是全部的样本；列采样是从M个特征中，选择m个特征（m<<M）。采样之后的数据使用完全分裂的方式建立决策树，子节点要么无法继续分裂，要么所有样本归属同一类。由于之前的两个随机采样的过程保证了随机性，一般不剪枝也不会出现过拟合。由于决策树具有可解释性，对于选择的特征可以分析其重要程度。一般来说，当某一特征在所有树中离树根的平均距离越近，这一特征在分类任务中就越重要。随机森林构建CART决策树，特征选择基于基尼系数。假设某个特征在决策树的节点向下分裂，前后的基尼系数差为Vim，如果分裂k次，则特征重要性计量为。在随机森林共有n棵树用到该特征，那么计算森林中所有特征的重要性总和为。最后把所有M个特征重要性评分归一化，就可以得到该特征的重要性计量。

图3-9　随机森林的算法逻辑

优化算法为投票制，通过决策树来投票（平均），投票机制有一票否决制、少数服从多数、加权多数等。具体流程包括四个部分：

①随机选择样本（放回抽样），生成出M个数据集；

②随机选择样本特征；

③构建决策树，训练出M棵不剪枝决策树，以信息增益或基尼系数作为划分标准；

④每棵树预测耦合后的总体结果投票，即为随机森林对于输入数据的判断结果。

（2）Boosting类

集成学习的另一大类即Bagging类方法，当个体学习器之间存在强依赖关系，不同的分类器通过串行训练而获得，根据已训练的分类器的性能来进行训练。此外，Bagging方法各决策树权值是一样的，而Boosting是所有决策树加权求和的结果，每个权重代表决策树在上一轮迭代中的成功度。

在Boosting类算法中，Adaboost（Adaptive Boosting）是最著名的算法之一，用弱分类器线性组合构造强分类器。关注被错分的样本，且准确率高的弱分类器有更大的权重。弱分类器一般选择非线性且深度小的决策树。

其中F(x)是强分类器，f_i(x)是弱分类器，a_i是弱分类器的权重，T为弱分类器数量，x表示输入，输出为1或-1，分别对应正负例样本。

如图3-10所示，训练样本同样带有权重，初始时所有样本的权重相等，被前面的弱分类器错分的样本会加大权重，接下来的弱分类器会更加关注错分样本，精度越高的弱分类器权重越大。弱分类器和它们的权重值通过训练算法得到。依次训练每一个弱分类器，并得到它们的权重值。强分类器的输出值也为+1或-1，对应于正样本和负样本。

图3-10　Boosting类算法的工作逻辑

假设二分类的训练数据集

T={(x₁, y₁),(x₂, y₂),...,(x_n, y_n)},x_i∈X⊆Rn, y_i∈Y={−1,+1}, i=1, 2, ..., n

其中，X为样本点取值集合，Y为类别集合，n表示样本量大小。

Adaboost算法基本流程如下：

①初始化训练数据。

假设训练样本数量为N，为每一个训练样本赋予同样的权重w，即w=1/N，并且满足样本权重之和为1，即=1。

②训练弱分类器m=1, 2,..., M，共有M个弱分类器。计算它对训练样本的错误率，并计算弱分类器m对训练数据的最终权重。

训练弱分类器m

G_m(x)→{−1,+1}

其中，D_m为弱分类器m的训练数据集，G_m(x)为其输出结果。

计算G_m(x)在训练集上的误差率

其中，w_{m, i}表示弱分类器m在样本x_i中的权重值。

计算相关系数

更新训练数据的权重分布（z_m归一化因子）

③重复过程②直至达到停止条件。停止条件包括弱分类器数量、最后一次分类器的误差率小于某个阈值或分错样本的数量等。

④按照每个弱分类器的话语权大小合并成一个强分类器，至此模型训练结束。

Adaboost算法是利用前一轮的弱学习器的误差来更新样本权重值，然后一轮一轮的迭代。每一次迭代要重新计算整个样本集，效率较低。一种改进的Boosting类方法是梯度提升决策树（Gradient Boosting Decision Tree, GBDT）。其中，GB（Gradient Boosting）是一个算法框架，弱学习器必须是CART回归树，而且GBDT在模型训练的时候，采用损失函数的梯度拟合残差并迭代计算，对所有CART回归树（不是分类树）权重组合，可以用于分类。

学习策略上，GBDT模型为M个生成决策树加法模型，θ_m为决策树参数。

首先确定初始提升树f₀(X)=0，则第m步的模型为

通过不断迭代拟合样本真实值与当前分类器的残差Y−F_m(X)来逼近真实值，h_m(X)优化目标就是F_m−1(X)+a_mh_m(X)和Y的差距。

这里L()为损失函数。GBDT的负梯度就是残差，所以说对于回归问题，我们要拟合的就是残差。通过经验风险极小化，让残差尽可能地小，找到最优划分点，确定回归树的参数。得到一棵回归树h_m(x_i)，其中残差将作为下一步迭代的目标值，更新F_m(x)。

不同于随机森林是把各个树的结果求平均，GBDT是将各个树结果求和。假设完成前k次决策树的学习后，即前k棵树是已知的，则当前的学习器为

即对于样本x_i，通过sigmoid函数转换成分类预测结果为

不同于随机森林是把各个树的结果求平均，GBDT是将各个树结果进行求和。更新预测结果公式为y_1−i=y_{1: i−1}+step×y_i，其中y_1−i为前i次迭代的综合预测结果，y_i为本次预测结果，step为学习率，一般而言学习率取值在0～1之间。对于两类分类，以对数损失函数为例。可以求出其梯度如式（3.74）所示，其余计算方法与回归算法一致。

GBDT每轮迭代数据都与上一轮结果有关，偏差不会很大，但联系紧密的数据拟合会使得方差过大，要浅一点的树来降低方差。由于GBDT选择特征和特征值使得误差最小的点作为分割点，因此也可以用作特征选择和降维。

分类树中最佳划分点的判别标准是熵或者基尼系数，但是在回归树中的样本标签是连续数值，所以再使用熵之类的指标不再合适，取而代之的是平方误差，它能很好地评判拟合程度。回归树选择的损失函数一般是均方差（最小二乘）或者绝对值误差，而在分类算法中一般的损失函数选择对数函数来表示。重复上述步骤，直至训练停止，最终得到一个强学习器。目前GBDT算法比较好的工程实现之一是XGBoost（eXtreme Gradient Boosting）。XGBoost是一个大规模、分布式的通用GBDT库，对于GBDT做了大量的优化。首先为了防止模型过拟合，XGBoost将树模型的复杂度加入正则化项中，在训练过程中对子节点个数惩罚，相当于在训练过程中进行剪枝，控制模型的复杂度；其次，XGBoost分类器采用均方误差损失函数，利用泰勒公式的二阶导数信息，加快收敛速度，而普通的GBDT只用到一阶导数；XGBoost还支持特征级别的并行计算。在进行节点分裂时，各特征的增益计算就可以开启多线程运行。这些都加速了XGBoost的计算速度，减小内存消耗。

除了XGBoost，2017年微软亚洲研究院推出开源的LightGBM(LGB)[8]，也进一步推动了GBDT的工业级应用[1]。LightGBM本身使用的是直方图加回归树的方式，在类别特征分割时，利用直方图有限优化特征分类的方式，减少不同组合的可能性。而对于排好序的直方图，回归树又可以寻找到最好的分割点。既保证了准确度，又优化了运算速度。

（3）讨论与小结

我们来对比本节讨论的分类算法之间的效果，仍然采用上一小节的数据集，XGBoost与LightGBM采用尽可能相同参数进行比较。结果如表3-4所示，决策树与随机森林的对比结果可以看出，除AUC之外，相对同等情况下随机森林的结果会明显优于决策树。这是因为随机森林本身就是多颗决策树组成的投票模型。当然，考虑到决策树本身容易过拟合的特点，当前随机森林模型AUC低于决策树，可能是由于决策树模型过拟合导致的。相比之下，XGBoost和LightGBM的各项评估指标更佳。迭代过程中，LightGBM的直方图计算方式在生成树过程中速度会优于XGBoost，当然这并不能说明LightGBM的效果就会优于XGBoost。由于数据样本较少，迭代次数较多也容易导致模型出现过拟合。总的来说，作为工业上实现的XGBoost和LightGBM，都可以通过模型参数调整实现数据的强拟合与泛化，但是XGBoost的耗时往往更多。当然，对于较大的数据与更多的特征维度，两者区别可能并没有那么大。

目前，文本分类主要是针对唯一分类问题，也就是每个样本只能分配于一个类别。如果要求样本可以属于多个类别，那么就涉及多标记学习问题，这也是文本分类任务的研究热点。

表3-4　不同算法结果对比

[1] https://lightgbm.readthedocs.io/en/latest/