MLlib分类与回归算法详解

MLlib支持二元分类、多类分类、回归分析等多种算法。表4-12列出了问题类别及其相关算法，同时下文将对这些算法模型进行介绍。

表4-12 问题类别及相关算法

1.线性模型

（1）数学公式

许多标准机器学习方法可以被转换为凸优化问题，即一个为凸函数f找到最小值的任务，这个函数f依赖于一个有d个值的向量变量w（代码中的weights）。这是一个min_w∈R^df（w）优化问题，其目标函数具有如下形式：

向量x_i∈R^d是训练数据样本，其中1≤i≤n。y_i∈R是相应的类标签，也是想要预测的目标。如果L（w；x，y）能被表述为wTx和y的一个函数，则称该方法是线性的。有几个MLlib分类和回归算法属于该范畴，下面将一一讨论。

目标函数f包括两部分：控制模型复杂度的正则化因子和度量模型误差的损失函数。损失函数L（w；.）是典型关于w的凸函数。事先锁定的正则化参数λ≥0（代码中的regParam）承载了在最小化损失量（训练误差）和最小化模型复杂度（避免过渡拟合）两个目标之间的权衡取舍。

表4-13概述了MLlib支持的损失函数、梯度和子梯度。

表4-13 MLlib支持的损失函数及梯度和子梯度

正则化因子的目标是获得简单模型和避免过度拟合。在MLlib中，支持表4-14所示的正则化因子。

表4-14 正则化因子

表中，sign（w）是一个代表w中所有实体的类标签（signs（±1））的向量。

与L1正则化问题比较，由于L2的平滑性原因，L2正则化问题一般较容易解决。但是，由于可以强化权重的稀疏性，L1正则化更能产生较小的和更容易解释的模型，而后者在特征选择是非常有用的。不正则化而去训练模型是不恰当的，尤其是在训练样本数量较小的时候。

（2）二元分类

二元分类将数据项划分为两类：正例和反例。MLlib支持两种二元分类的线性方法：线性支持向量机和逻辑回归。对两种方法来说，MLlib都支持L1、L2正则化。在MLlib中，训练数据集用一个LabeledPoint格式的RDD来表示。需要注意，本书中的数学公式里，约定训练标签y为+1（正例）或-1（反例）。但是在MLlib中，为了与多类标签保持一致，反例标签是0而不是-1。

● 线性支持向量机（SVM）

对于大规模的分类任务来说，线性支持向量机是标准方法。它是上面“数学公式”内容中所描述的线性方法，其损失函数是hinge loss：

L（w；x，y）：=max{0，1-yw^Tx}

默认配置下，线性SVM使用L2正则化训练。此外SVM也支持L1正则化。通过这种方式，问题变为线性规划问题。

线性支持向量机算法的产出是一个SVM模型。给定新数据点X，该模型基于w^Tx的值来预测。默认情形下，w^Tx≥0时为正例，否则为反例。

【例4-51】演示了如何加载数据集、运用算法对象的静态方法执行训练算法以及运用模型预测来计算训练误差。

【例4-51】训练算法使用示例

默认配置下，SVMWithSGD.train将正则化参数设置为1.0来进行L2正则化。如果想配置算法参数，我们可以直接生成一个SVMWithSGD对象然后调用setter方法。所有其他MLlib算法都支持这种自定义化方法。举例来说，下面代码生了一个用于SVM的L1正则化变量，其正则化参数为0.1，且迭代次数为200，如【例4-52】所示。

【例4-52】调整算法配置参数示例。

LogisticRegressionWithSGD的使用方法与SVMWithSGD相似。

● 逻辑回归

逻辑回归广泛运用于二元因变量预测。它是上面“数学公式”内容中所描述的线性方法，其损失函数是logistic loss：

L（w；x，y）：=log（1+exp（-yw^Tx））

逻辑回归算法的产出是一个逻辑回归模型。给定新数据点X，该模型运用如下的逻辑函数来预测：

在这里，z=w^Tx。默认情况下，若f（w^Tx）>0.5，输出是正例，否则是反例。与线性支持向量机不同之处在于，线性回归模型f（z）的输出含有一个概率解释（即x是正例的概率）。

MLlib支持常用的二元分类评估度量方法（在PySpark中不可用），包括精度、召回率、F度量、接收者特征操作曲线、精度-召回率曲线和AUC。AUC常用来比较不同模型的性能，精度/召回率/F度量用来决定阈值时为预测指定的恰当阈值。

二元逻辑回归能够被推广至多元逻辑回归从而训练和预测多元分类问题。举个例子，对于可能有K个结果的问题，可以选择其中一个结果作为中心点，其他K-1个结果可以分别地对这个中心点进行回归。在MLlib中，一般选取第一个类（0）作为中心类。

对于多元分类问题，该算法将输出一个多项式逻辑回归模型，在这个模型中包含K-1个二元逻辑回归模型对第一个类的回归。给一个新的数据点，这K-1个模型将会被运行，最大概率的类将被选择作为预测类。

这里实现了两个算法来解决逻辑回归问题：mini-batch梯度下降和L-BFGS算法。对于更快的收敛，推荐使用L-BFGS算法解决问题。【例4-53】演示了如何装载多元样本数据集，把它分为训练和测试数据集，并使用LogisticRegressionWithLBFGS拟合逻辑回归模型，然后评估模型测试的数据集并保存到磁盘。

【例4-53】逻辑回归算法示例。

（3）回归

● 线性最小二乘法、Lasso和岭回归

最小二乘法是回归问题中最常用的公式。它是上面“数学公式”内容中所描述的线性方法，其损失函数是平方损失（squared loss）：

根据正则化参数类型的不同，将相关算法分为不同的回归算法：

■ 普通最小二乘法或线性最小二乘法：未正则化。

■ 岭回归算法：使用L2正则化。

■ Lasso算法：使用L1正则化。所有相关模型，其平均损或训练误差计算公式为：

【例4-54】不同回归算法示例。

RidgeRegressionWithSGD和LassoWithSGD能够和LinearRegressionWithSGD以相同的方式使用。为了运行以上的代码，必须确保在构建文件时加入spark-mllib依赖。

● 流的线性回归

当数据以流的形式传入，且当收到新数据更新模型参数时，在线拟合回归模型是有用的。MLlib使用普通最小二乘法实现流的线性回归。这种拟合的处理机制与离线方法相似，但其拟合发生于每一数据块到达时之外，目的是为了持续更新以反应流中数据。

下面的过程演示了如何从两个文本流中加载训练数据和验证数据，将其解析为LabeledPoint流，并基于第一个流在线拟合线性回归模型，然后在第二个流上进行预测。

首先，导入用来解析输入数据和创建模型的类。

import org.apache.spark.mllib.linalg.Vectors

import org.apache.spark.mllib.regression.LabeledPoint

import org.apache.spark.mllib.regression.StreamingLinearRegressionWithSGD

然后，创建训练集和测试集的输入流。假定一个StreamingContext已经被创建，对这个过程来说，在流中使用了含类标签的点，但在实际应用中，也可能使用不含有类标签的数据作为测试集。

val trainingData=ssc.textFileStream（"/training/data/dir"）.map（LabeledPoint.parse）.cache（）

val testData=ssc.textFileStream（"/testing/data/dir"）.map（LabeledPoint.parse）

将权重初始化为0来创建模型。

val numFeatures=3

val model=new StreamingLinearRegressionWithSGD（）

.setInitialWeights（Vectors.zeros（numFeatures））

接下来，启动用于训练和测试的流并开始任务，打印其正确的类标签结果来观察结果。

model.trainOn（trainingData）

model.predictOnValues（testData.map（lp=>（lp.label，lp.features）））.print（）

ssc.start（）

ssc.awaitTermination（）

可以在训练目录和测试目录中存入文本数据来模拟流事件。每一行数据应该是一个（y，[x1，x2，x3]）格式的数据点，其中y是类标签，而x1，x2，x3是特征。每当一个文本文件放入/training/data/dir目录时模型会更新。每当一个文本文件放入到/testing/data/dir目录时，可以观察到预测结果。在训练目录中放入越多数据，预测的结果越好。

（4）面向开发者的实现

在具体场景之外，MLlib还实现了随机梯度下降的一个简单分布式版本，该实现基于底层的梯度下降功能单元。所有提供的算法接收一个正则化参数（regParam）和不同的随机梯度下降相关参数（stepSize，numIterations，miniBatchFraction）作为输入。每一个算法都支持三种可能正则化方法（分别是不正则化，L1正则化，L2正则化），算法如下。

● SVMWithSGD

● LogisticRegressionWithLBFGS

● LogisticRegressionWithSGD(www.xing528.com)

● LinearRegressionWithSGD

● RidgeRegressionWithSGD

● LassoWithSGD

2.朴素贝叶斯

朴素贝叶斯是一种简单的多类分类方法，它假定分类特征之间两两不相关。朴素贝叶斯在训练上非常有效率。对于训练集中的每一条记录，它计算每一个特征在类标签上的条件概率分布，然后运用贝叶斯理论计算某一观察在类标签的条件概率分布，并用之来预测。

MLlib支持多模朴素贝叶斯（Multinomial Naive Bayes），将其主要用于文档分类的算法。用于此场景时，每个观察者是一个文档，每个特征代表一个单词，特征的值是单词的频率。特征值必须是非负的单词出现频率。附加的平滑处理可通过设置参数λ（默认值为1.0）来完成。对于文档分类，输入的特征向量通常是稀疏的，并且能够获得稀疏输入的特有优势。由于训练数据只是用一次，因此没有必要缓冲它。

NaiveBayes实现了多模朴素贝叶斯算法。它接收一个LabeledPoint格式的RDD和一个可选的平滑参数lambda作为输入，输出一个用于评估和预测的NaiveBayesModel模型。代码片段如【例4-55】所示。

【例4-55】朴素贝叶斯模型示例。

3.决策树

决策树及其家族是解决分类和回归机器学习任务的热点算法。决策树方法易于解释和处理分类特征、能够扩展处理多类分类、不需要特征变换以及能够捕获非线性特征关系，使得决策树得到广泛应用。该体系中的算法如随机森林等都是分类和回归任务中的高性能算法。

MLlib中的决策树支持二元和多类分类，支持连续特征和分类特征的回归。决策树通过对数据分区，可以分布式实现数百万样本分类操作。

（1）基础算法

决策树是一种将特征空间以迭代的方式进行二元切分的贪心算法。树为每个最底层分区（叶子分区）分配一个类标签。每一次切分都贪心地从可能切分集合中选择一个最佳切分，目的是从树节点中获得最大信息增益。换言之，在每一节点的切分都是基于arg max IG（D，s）原则选择，在这里IG（D，s）是每次切分产生的信息增益。

● 节点不纯度和信息增益

对小数据集的单机实现来说，每一连续特征的切分备选方案通常是一系列唯一值。一些实现先对特征值排序，然后使用排序后的唯一值作为切分备选方案，以更快地执行树计算。

对于巨大的分布式数据集来说，特征值排序代价很高。实际的实现是在数据抽样上执行分位数计算，来获得一个近似的切分备选方案集。排序的切分创建箱，装箱的最大数量通过maxBins参数指定。

注意，装箱数量不能大于样本数量N（maxBins的默认值是100）。如果条件不满足，决策树自动地减少装箱数量。

● 切分备选方案

对一个具有M个可能值（分类标签）的分类特征来说，切分方法是从2^M-1-1种备选切分方案中选择一种。对于二元分类和回归，可以根据类标签调和均值将特征值排序，如此可以将备选分类方案的数量降低到M-1个。比如，对某个具有分类值A/B/C的分类特征，A/B/C在标签1上的比例依次是0.2/0.6/0.4，其分类值排序是A、C、B。对二元分类来说，可能切分备选方案是“A|C，B”和“A，C|B”，其中的竖线是分隔符。

对于多类分类，最多可以有2^M-1-1种备选切分方案供使用。当2^M-1-1大于maxBins参数时，使用一种类似于二元分类和回归的启发式方法。这M个特征值根据不纯度排序，然后从结果的M-1个切分备选方案中选择，其中不纯度指样本在构建树时被错误分类的可能性。

● 停止规则

当如下的两个条件之一满足时，停止递归树构造。

■ 节点深度已经等于训练参数maxDepth。

■ 在节点上已经没有切分备选方案能够获得信息增益。

（2）实现细节

● 最大内存需求

为了快速处理，决策树算法对树同一等级上的所有节点同时执行直方图计算。于是随着树的深度越来越深，对内存的需求也越大，可能会导致内存溢出。为了缓解该问题，训练参数maxMemoryInMB（在主节点上翻倍）限定了工作节点上的用于直方图计算的最大内存。保守地将默认值设置为128MB，在大多数场景下，决策算法可以正常工作。一旦某一等级上所需内存超过maxMemoryInMB阈值，在该等级之下的所有训练任务都被拆分为较小的多个任务。需要注意，如果有更大的内存，增加maxMemoryInMB能减少数据转移从而加快训练进度。

● 特征值装箱

通过增大maxBins^[3]使得算法考虑更多的切分备选方案，从而进行更细粒度的决策。但是，它也增加了计算量和通信量。需要注意，对任意分类特征来说，maxBins参数的最小值也必须是最大标签数M。

● 规模自适应

计算量随着训练样本数量、特征数量、maxBins参数值近似线性地增长。通信量随着特征数量和maxBins参数值也近似线性地增长。算法实现可以接收稀疏数据和密集数据。但是，并未针对稀疏数据进行优化。

（3）示例

1）下面的【例4-56】分类的例子演示了如何加载LIBSVM数据文件，将它解析为LabeledPoint的RDD，然后使用基尼系数的决策树进行分类，作为杂质测量，其中树的最大深度为5。测试计算误差来衡量算法的准确性。

【例4-56】使用决策树分类示例。

2）下面【例4-57】演示了如何加载LIBSVM数据文件，将它解析为LabeledPoint的RDD，然后进行回归和方差计算，作为杂质测量，其中树的最大深度为5。计算均方误差（MSE）结束时评估拟合优度。

【例4-57】使用决策树回归示例。

4.树的集合体

整体方法是一种学习算法，是由一组其他的基础模型组成的集成模型。MLlib支持两种主要的集成学习算法：梯度上升树（GradientBoostedTrees）和随机森林（RandomForest）。这两个算法都使用决策树作为基础模型。Gradient-Boosted Trees（GBT）和Random Forest算法都是集成学习算法，但是训练的过程却不同。

1）GBT一次只训练一棵树，RandomForest算法可以并行的训练多棵树，所以对比随机森林算法，GBT会花费更长的时间去训练。另一方面来说，对于更浅的树选择GBT算法更加合理，因为训练一棵树花费的时间更短。

2）RandomForest算法不容易过拟合。

3）RandomForest算法更加容易调整，因为当树的数量改变时就可以提高性能。当树的数量变的足够大时，GBT的性能将会降低。

总的来说，RandomForest和RandomForest这两个算法效率都很高，要根据实际的数据选择合适的算法。

（1）随机森林算法（Random Forest）

随机森林分别地训练一组决策树，所以训练可以并行完成。训练过程注入随机性算法，以便使每个决策树略有不同。结合预测，减少每棵树预测的方差，以提高测试数据的性能。为了预测一个新实例，随机森林算法必须将所有的决策树的预测进行聚合，这个聚合的过程在分类和回归中的具体表现略有不同，下面的算法例子会以分类和回归做不同的说明。

在介绍算法的具体使用过程之前，先来了解一下随机森林算法中用到的参数。

● numTrees：森林里树木的数量。增加树木的数量将减少预测的方差的大小，并提高模型的测试时间的准确性。训练时间也会随着树木的数量增加线性增长。

● maxDepth：森林里每棵树的最大深度。增加深度使模型更具表达性和更加的强大。然而，深度更大的树训练的时间更长，也更容易过度拟合。一般来说，当使用随机森林时比使用一个单一的决策树时更加适合深度更大的数，因为一棵树比随机森林更加容易过拟合。

● subsamplingRate：该参数指定用于在森林中训练每棵树的数据集大小，是一个比例值，具体的数据集大小会随着原始数据的大小而改变。一般默认推荐1.0，减少这个值可以加快训练速度。

● featureSubsetStrategy：该参数指定了对每个树节点进行分裂策略的数量，减少这个数字将加速训练，但如果太低了则会影响性能。

下面的【例4-58】演示了如何加载LIBSVM数据文件，作为LabeledPoint的RDD进行解析，然后使用一个随机森林执行分类。测试误差计算用来衡量算法的准确性。

【例4-58】随机森林进行分类示例。

下面的【例4-59】演示了如何加载LIBSVM数据文件，作为LabeledPoint的RDD进行解析，然后使用一个随机森林执行回归。计算均方误差（MSE）结束时评估拟合优度。

【例4-59】随机森林进行回归示例。

（2）梯度上升树（GBT）

梯度上升树（GBT）是决策树的集合体。GBT迭代训练决策树是为了减少损失函数。梯度增加算法迭代地训练一系列决策树。在每次迭代中，该算法使用当前的整体预测每个训练实例的标签，然后将预测与真正的标签进行比较。MLlib使用连续和分类功能支持GBT的二元分类和回归。MLlib实现GBT是使用现有的决策树来实现的。需要注意的是GBT不支持多元分类问题，对于多元分类问题，可使用决策树或者随机森林算法。

表4-15列出了在MLlib中的GBT支持的损失函数。注意，每个损失函数只适用于分类或回归中的一个而不是两个。

表4-15 loss表

下面先介绍一下GBT算法设计的参数。

● loss：参考表4-15，不同的loss适用于不同的任务。对于一个数据集，不同的Loss会得到显著不同的结果。

● numIterations：这个参数为树集合体中树的数量，每次迭代都会产生一棵树。增加这个值会使得训练数据更加的精确，但会付出比较大的代价。如果这个值过大会使得测试训练时间过长。

● learningRate：如果该算法的行为不是很稳定，减小这个值可以提高稳定性。

● algo：使用树的[Strategy]参数对算法或者分类以及回归任务进行设置。

Gradient Boosting算法在训练很多树时容易过拟合。为了防止过拟合，在训练时进行验证是非常有用的，runWithValidation提供了这个功能。runWithValidation方法需要提供一对RDD作为参数，一个作为训练集，一个作为验证集。

当验证的错误不超过一定的公差（由BoostingStrategy提供的参数validationTol进行设置）训练将会停止。在实践中验证错误刚开始减少之后就会增加。验证错误不一定会单调的改变，建议用户设置一个足够大的，并且使用evaluateEachIteration来检查检验曲线以优化迭代的数量。

下面的【例4-60】演示了如何加载LIBSVM数据文件，作为LabeledPoint的RDD进行解析，然后使用梯度上升树（GBT）进行分类。测试误差计算来衡量算法的准确性。

【例4-60】梯度上升树（GBT）分类示例。

下面的【例4-61】演示了如何加载LIBSVM数据文件，作为LabeledPoint的RDD进行解析，然后使用一个以平方误差作为loss函数的梯度上升算法（GBT）执行回归。计算均方误差（MSE）结束时评估拟合优度。

【例4-61】梯度上升算法（GBT）回归示例。