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

本文作者： AI研习社

2017-05-14 14:34

导语：SVM 算法实现指南。

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

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

核函数

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

多项式核：

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

高斯核（径向基函数）:

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

线性核：

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

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

SMO算法流程

SMO的主要两个步骤就是：

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

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

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

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

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

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

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

消去α可得

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

其中

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

u 的表达式为：

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

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

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

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

约束条件的线性表示

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

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

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

对于α有

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

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

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

而b的更新为

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

其中

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

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

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

算法实现

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

public SvmResult plattSmo(final SvmResult svmResult) {
double b = svmResult.getB();
double[] alphas = svmResult.getAlphas();

for(int i=0;i<featuresArray.length;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<this.eCache.length;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<mCount;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;i<alphas.length;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;i<d.length;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++;
}
}