基于Spark如何实现SVM算法？这里有一份详尽的开发教程（含代码

内容简介：基于Spark如何实现SVM算法？这里有一份详尽的开发教程（含代码

雷锋网（公众号：雷锋网）按：本文作者谢辉，原文载于作者 个人博客 ，雷锋网已获授权。

支持向量机SVM（SuPPort Vector Machine）是一种有监督的学习模型，它的核心有两个：一、核函数（kernel trick）；二、序列最小优化算法SMO（Sequential minimal optimization）是John Platt在1996年发布的用于训练SVM的有效算法。本文不打算细化SVM支持向量机的详细推倒算法，只涉及以上两点的内容做一个说明，最后给出算法实现和一个实验对比图。

核函数

核函数在处理复杂数据时效果显著，它的做法是将某一个维度的线性不可分数据采取核函数进行特征空间的隐式映射到高维空间，从而在高维空间将数据转化为线性可分，最后回归到原始维度空间实施分类的过程，常见的几个核函数如下：

多项式核：

高斯核（径向基函数）:

线性核：

即是两个矩阵空间的内积。

SMO算法流程

SMO的主要两个步骤就是：

1、选择需要更新的一对α，采取启发式的方式进行选择，以使目标函数最大程度的接近其全局最优值；

2、将目标函数对α进行优化，以保持其它所有α不变。

以上是两个基本步骤，实现具体推到公式如下：

所需要收到的约束条件为：

同时更新α，要求满足如下条件，就可以保证为0的约束

消去α可得

其中

u 的表达式为：

y为第i个特征因素的真实标签值

之后考虑约束条件 0 α>

约束条件的线性表示

依据 y 同号或是异号，可得出上下两个边界为

对于α有

对于α首先可以通过E求得j，之后计算方式可为:

而b的更新为

其中

每次更新完和都需要重新计算b以及对应的和

有了以上的公式，代码实现就比较简单了。

算法实现

完整的Platt-smo算法实现入口:

public SvmResult plattSmo（final SvmResult svmResult） {

double b = svmResult.GEtB（）;

double[] alphas = svmResult.getAlphas（）;

for（int i=0;i

double ei = this.CAlcEk（i, alphas, b）;

if （（（lablesArray[i] * ei<-tolerFactor）

&& （alphas[i]<penaltyFactor））

|| （（lablesArray[i] * ei > tolerFactor） && （alphas[i] > 0））） {

double[] jSelected = this.selectJ（i, ei, alphas, b）; //启发式实现j的选择

int j = （int） jSelected[0];

double ej = jSelected[1];

double alphaIold = alphas[i];

double alphaJold = alphas[j];

double L = 0;

double H = 0;

//边界计算

if （lablesArray[i] != lablesArray[j]） {

L =MATh.max（0, alphas[j] - alphas[i]）;

H = Math.min（penaltyFactor, penaltyFactor + alphas[j]

- alphas[i]）;

} else {

L = Math.max（0, alphas[j] + alphas[i] - penaltyFactor）;

H = Math.min（penaltyFactor, alphas[j] + alphas[i]）;

}

if （L == H） {

logger.info（"L==H"）;

} else {

double eta = （2.0 * this.kernelArray[i][j] - this.kernelArray[i][i] - this.kernelArray[j][j]）;

if （eta >= 0） {

logger.info（"eta>=0"）;

} else {

//双向调整alphas[j]递减

alphas[j] -= lablesArray[j] * （ei - ej） / eta;

if （alphas[j] > H） {

alphas[j] = H;

}

if （L > alphas[j]） {

alphas[j] = L;

}

//更新ej

this.updateEk（j, alphas, b）;

if （Math.abs（alphas[j] - alphaJold）<0.00001） {

logger.info（"j not moving enough"）;

} else {

//双向调整alphas[i]递减

alphas[i] += lablesArray[j] * lablesArray[i]

* （alphaJold - alphas[j]）;

//更新ei

this.updateEk（i, alphas, b）;

//计算b

double b1 = b - ei- lablesArray[i]*（alphas[i]-alphaIold）*this.kernelArray[i][i] - lablesArray[j]*（alphas[j]-alphaJold）*this.kernelArray[i][j];

double b2 = b - ej- lablesArray[i]*（alphas[i]-alphaIold）*this.kernelArray[i][j] - lablesArray[j]*（alphas[j]-alphaJold）*this.kernelArray[j][j];

if （（0<alphas[i]） && （penaltyFactor > alphas[i]））{

b = b1;

}else if （（0<alphas[j]） && （penaltyFactor > alphas[j]））{

b = b2;

}else{

b = （b1 + b2）/2.0;

}

}

}

}

}

}

return new SvmResult（b, alphas）;

}

在以上算法里面重点关注是j的选择，

J的选择:

private double[] selectJ（int i,double ei,double[] alphas,double b）{

int maxK = -1;

double maxDeltaE = 0;

double ej = 0;

int j = -1;

double[] eiArray= new double[2];

eiArray[0] = 1d;

eiArray[1] = ei;

this.eCache[i] = eiArray;

boolean hasValidEcacheList = false;

for（int k=0;k

if（this.eCache[k][0] > 0）{

if（k == i）{

continue;

}

hasValidEcacheList = true;

if（k == this.m）{

k = m-1;

}

double ek = this.calcEk（k, alphas, b）;

double deltaE = Math.abs（ei - ek）;

if （deltaE > maxDeltaE）{

maxK = k;

maxDeltaE = deltaE;

ej = ek;

}

}

}

j = maxK;

if（!hasValidEcacheList || j == -1）{

j = this.selectJRandom（i）;

ej = this.calcEk（j, alphas, b）;

}

if（j == this.m）{

j = m-1;

}

return new double[]{j,ej};

}

首选采取启发式选择j，通过计算deltaE的最大值来逼近j的选择，如果选择不到就随机选择一个j值，在j选择里面有一个Ek的计算方式

private double calcEk（int k,double[] alphas,double b）{

Matrix alphasMatrix = new Matrix（alphas）;

Matrix lablesMatrix = new Matrix（lablesArray）;

Matrix kMatrix = new Matrix（this.kernelArray[k]）;

double fXk = alphasMatrix.MUltiply（lablesMatrix）.dotMultiply（kMatrix.transpose（））.dotValue（） + b;

double ek = fXk - （float）this.lablesArray[k];

return ek;

}

下面再介绍一下核函数计算方式，本文主要采取径向基函数（RBF）实现，如下:

public double[] kernelTrans（double[][] featuresArray,double[] featuresIArray）{

int mCount = featuresArray.length;

double[] kernelTransI = new double[mCount];

Matrix featuresMatrix = new Matrix（featuresArray）;

Matrix featuresIMatrix = new Matrix（featuresIArray）;

if（trainFactorMap.get（"KT"）.equals（"lin"））{

Matrix result = featuresMatrix.dotMultiply（featuresIMatrix.transpose（））;

kernelTransI = result.transpose（）.values（）[0];

}else if（trainFactorMap.get（"KT"）.equals（"rbf"））{

double rbfDelta = （double）trainFactorMap.get（"rbfDelta"）;

for（int j=0;j

Matrix xj = new Matrix（featuresArray[j]）;

Matrix delta = xj.reduce（featuresIMatrix）;

double deltaValue = delta.dotMultiply（delta.transpose（））.dotValue（）;

kernelTransI[j] = Math.exp（（-1.0*deltaValue）/（2*Math.pow（rbfDelta, 2）））;

}

}

return kernelTransI;

}

最后看下测试代码实现:

double[][] datasvs = new double[m][d[0].length];

double[] labelsvs = new double[m];

double[] alphassvs = new double[m];

int n = 0;

for（int i=0;iif（alphas[i] != 0）{

datasvs[n] = d[i];

labelsvs[n] = l[i];

alphassvs[n] = alphas[i];

n++;

}

}

//model test

int errorCount = 0;

for（int i=0;i

double[] kernelTransI = learner.kernelTrans（datasvs, d[i]）;

Matrix kernelTransIM = new Matrix（kernelTransI）;

Matrix labelsvsM = new Matrix（labelsvs）;

Matrix alphassvsM = new Matrix（alphassvs）;

double predict = kernelTransIM.dotMultiply（labelsvsM.multiply（alphassvsM）.transpose（））.dotValue（） + b;

System.out.println（i+"\t"+predict+"\t"+l[i]）;

if（AdaBoost.sigmoid（predict） != l[i]）{

errorCount++;

}

}

测试代码是首先找出所有的支持向量，并提取支持向量下的特征向量和标签向量，采取核函数进行隐式映射，最后计算预测值。

训练结果

本文采取100个二维平面无法线性可分的数据集合，如下：

通过径向基函数映射后采取支持向量预测计算得到的可分平面如下

本算法100个数据训练准确率可达98%。

注：本文算法均来自Peter Harrington的《Machine Learning in action》

———————————————————————————————————————

人工智能之神经网络特训班

20年清华大学神经网络授课导师，带你系统学习人工智能之神经网络！

一站式深入了解深度学习的发展现状、基本原理和主要方法。

课程链接：http://www.mooc.ai/course/65

雷锋网（公众号：雷锋网）相关阅读：

从理论到实践，一文详解 AI 推荐系统的三大算法

监督学习最常见的五种算法，你知道几个？

雷锋网版权文章，未经授权禁止转载。详情见转载须知。

以上所述就是小编给大家介绍的《基于Spark如何实现SVM算法？这里有一份详尽的开发教程（含代码》，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持！

查看所有标签

猜你喜欢:

• 排序算法代码实现-Java
• 数据挖掘领域十大经典算法之―朴素贝叶斯算法（附代码）
• 机器学习——AdaBoost算法（手稿+代码）
• KMP算法，无解释，仅代码
• 动画+原理+代码，解读十大经典排序算法
• 机器学习算法基础（使用Python代码）

本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。