英超

基于Spark如何实现SVM算法这里有一

2019-08-11 04:36:32来源:励志吧0次阅读

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

  按:本文作者谢辉,原文载于作者个人博客,已获授权。

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

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

  多项式核:

  高斯核(径向基函数):

  线性核:

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

  SMO算法流程SMO的主要两个步骤就是:

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

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

  以上是两个基本步骤,实现具体推到公式以下:

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

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

  消去α可得

  其中

  u 的表达式为:

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

  之后考虑约束条件 0αc则

  约束条件的线性表示

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

  对α有

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

  而b的更新为

  其中

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

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

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

  public SvmResult plattSmo(final SvmResult svmResult) {

  double b = tB();

  double[] alphas = tAlphas();

  for(int i=0;ngth;i++){

  double ei = lcEk(i, alphas, b);

  if (((lablesArray[i] * ei -tolerFactor)

  (alphas[i] penaltyFactor))

  ((lablesArray[i] * ei tolerFactor) (alphas[i] 0))) {

  double[] jSelected = lectJ(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 = x(0, alphas[j] - alphas[i]);

  H = n(penaltyFactor, penaltyFactor + alphas[j]

  - alphas[i]);

  } else {

  L = x(0, alphas[j] + alphas[i] - penaltyFactor);

  H = n(penaltyFactor

  , alphas[j] + alphas[i]);

  }

  if (L == H) {

  (L==H);

  } else {

  double eta = (2.0 * rnelArray[i][j] - rnelArray[i][i] - rnelArray[j][j]);

  if (eta = 0) {

  (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

  dateEk(j, alphas, b);

  if (s(alphas[j] - alphaJold) 0.00001) {

  (j not moving enough);

  } else {

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

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

  * (alphaJold - alphas[j]);

  //更新ei

  dateEk(i, alphas, b);

  //计算b

  double b1 = b - ei- lablesArray[i]*(alphas[i]-alphaIold)*rnelArray[i][i] - lablesArray[j]*(alphas[j]-alphaJold)*rnelArray[i][j];

  double b2 = b - ej- lablesArray[i]*(alphas[i]-alphaIold)*rnelArray[i][j] - lablesArray[j]*(alphas[j]-alphaJold)*rnelArray[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;

  ache[i] = eiArray;

  boolean hasValidEcacheList = false;

  for(int k=0;ngth;k++){

  if(ache[k][0] 0){

  if(k == i){

  continue;

  }

  hasValidEcacheList = true;

  if(k == this.m){

  k = m-1;

  }

  double ek = lcEk(k, alphas, b);

  double deltaE = s(ei - ek);

  if (deltaE maxDeltaE){

  maxK = k;

  maxDeltaE = deltaE;

  ej = ek;

  }

  }

  }

  j = maxK;

  if(!hasValidEcacheList || j == -1){

  j = lectJRandom(i);

  ej = lcEk(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(rnelArray[k]);

  double fXk = ltiply(lablesMatrix).dotMultiply(anspose()).dotValue() + b;

  double ek = fXk - (float)blesArray[k];

  return ek;

  }

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

  public double[] kernelTrans(double[][] featuresArray,double[] featuresIArray){

  int mCount = ngth;

  double[] kernelTransI = new double[mCount];

  Matrix featuresMatrix = new Matrix(featuresArray);

  Matrix featuresIMatrix = new Matrix(featuresIArray);

  if(t(KT).equals(lin)){

  Matrix result = tMultiply(anspose());

  kernelTransI = anspose().values()[0];

  }else if(t(KT).equals(rbf)){

  double rbfDelta = (double)t(rbfDelta);

  for(int j=0;jmCount;j++){

  Matrix xj = new Matrix(featuresArray[j]);

  Matrix delta = duce(featuresIMatrix);

  double deltaValue = tMultiply(anspose()).dotValue();

  kernelTransI[j] = p((-1.0*deltaValue)/(2*w(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;ngth;i++){

  if(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;ngth;i++){

  double[] kernelTransI = rnelTrans(datasvs, d[i]);

  Matrix kernelTransIM = new Matrix(kernelTransI);

  Matrix labelsvsM = new Matrix(labelsvs);

  Matrix alphassvsM = new Matrix(alphassvs);

  double predict = tMultiply(ltiply(alphassvsM).transpose()).dotValue() + b;

  intln(i+\t+predict+\t+l[i]);

  if(gmoid(predict) != l[i]){

  errorCount++;

  }

  }

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

  训练结果

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

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

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

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

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

  人工智能之神经络特训班

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

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

  课程链接:

  (公众号:)(公众号:):

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

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

  版权文章,未经授权制止转载。详情见转载须知。

兰州汽车资讯网
合肥星座网
长沙机械网
分享到: