Svm实现多类分类原理

1.支持向量机分类算法最初只用于解决二分类问题，缺乏处理多分类问题的能力。后来随着需求的变化，需要svm处理多分类分为。目前构造多分类支持向
量机分类器的方法主要有两类: 一类是“同时考虑所有分类”方法，另一类是组合二分类器解诀多分类问题。
第一类方法主要思想是在优化公式的同时考虑所有的类别数据，J.Weston 和C.Watkins 提出的“K-Class 多分类算法”就属于这一类方法。该算法在经典的SVM理论的基础上，重新构造多类分类型，同时考虑多个类别,然后将问题也转化为-个解决二次规划(Quadratic Programming,简称QP)问题，从而实现多分类。该算法由于涉及到的变量繁多，选取的目标函数复杂，实现起来比较困难，计算复杂度高。
第二类方法的基本思想是通过组合多个二分类器实现对多分类器的构造，常见的构造方法有“一对一”(one-against-one)和“一对其余”(one-against-the rest两种。其中“一对一”方法需要对n类训练数据两两组合，构建n(n- 1)/2个支持向量机，每个支持向量机训练两种不同类别的数据，最后分类的时候采取“投票”的方式决定分类结果。“一对其余”方法对n分类问题构建n个支持向量机，每个支持向量机负责区分本类数据和非本类数据。该分类器为每个类构造一个支持向量机，第k个支持向量机在第k类和其余n-1个类之间构造一个超平面，最后结果由输出离分界面距离wx+ b最大的那个支持向量机决定。

本文将上述“一对其余”的SVM多分类方法对莺尾花数据进行分类识别，并设法减少训练样本个数，提高训练速度。

代码实现

#-*- coding:utf-8 -*-
'''
@project: exuding-bert-all
@author: exuding
@time: 2019-04-23 09:59:52
'''
#svm 高斯核函数实现多分类
import matplotlib.pyplot as plt
import numpy as np
import tensorflow as tf
from sklearn import datasetssess = tf.Session()#加载数据集，并为每类分离目标值
iris = datasets.load_iris()
#提取数据的方法
x_vals = np.array([[x[0],x[3]] for x in iris.data])y_vals1 = np.array([1 if y==0 else -1 for y in iris.target])
y_vals2 = np.array([1 if y==1 else -1 for y in iris.target])
y_vals3 = np.array([1 if y==2 else -1 for y in iris.target])
#合并数据的方法
y_vals = np.array([y_vals1,y_vals2,y_vals3])
#数据集四个特征，只是用两个特征就可以
class1_x = [x[0] for i,x in enumerate(x_vals) if iris.target[i]==0]
class1_y = [x[1] for i,x in enumerate(x_vals) if iris.target[i]==0]
class2_x = [x[0] for i,x in enumerate(x_vals) if iris.target[i]==1]
class2_y = [x[1] for i,x in enumerate(x_vals) if iris.target[i]==1]
class3_x = [x[0] for i,x in enumerate(x_vals) if iris.target[i]==2]
class3_y = [x[1] for i,x in enumerate(x_vals) if iris.target[i]==2]
#从单类目标分类到三类目标分类，利用矩阵传播和reshape技术一次性计算所有的三类SVM，一次性计算，y_target的占位符维度是[3,None]
batch_size = 50
x_data = tf.placeholder(shape = [None,2],dtype=tf.float32)
y_target = tf.placeholder(shape=[3,None],dtype=tf.float32)
#TODO
prediction_grid = tf.placeholder(shape=[None,2],dtype=tf.float32)
b = tf.Variable(tf.random_normal(shape=[3,batch_size]))
#计算高斯核函数 TODO
gamma = tf.constant(-10.0)
dist = tf.reduce_sum(tf.square(x_data),1)
dist = tf.reshape(dist,[-1,1])
sq_dists = tf.add(tf.subtract(dist,tf.multiply(2.,tf.matmul(x_data,tf.transpose(x_data)))),tf.transpose(dist))
my_kernel = tf.exp(tf.multiply(gamma,tf.abs(sq_dists)))
#扩展矩阵维度
def reshape_matmul(mat):v1 = tf.expand_dims(mat,1)v2 = tf.reshape(v1,[3,batch_size,1])return (tf.matmul(v2,v1))
#计算对偶损失函数
model_output = tf.matmul(b,my_kernel)
first_term = tf.reduce_sum(b)
b_vec_cross = tf.matmul(tf.transpose(b),b)
y_target_cross = reshape_matmul(y_target)
second_term = tf.reduce_sum(tf.multiply(my_kernel,tf.multiply(b_vec_cross,y_target_cross)),[1,2])
loss = tf.reduce_sum(tf.negative(tf.subtract(first_term,second_term)))
#创建预测核函数
rA = tf.reshape(tf.reduce_sum(tf.square(x_data),1),[-1,1])
rB = tf.reshape(tf.reduce_sum(tf.square(prediction_grid),1),[-1,1])
pred_sq_dist = tf.add(tf.subtract(rA,tf.multiply(2.,tf.matmul(x_data,tf.transpose(prediction_grid)))),tf.transpose(rB))
pred_kernel = tf.exp(tf.multiply(gamma,tf.abs(pred_sq_dist)))
#创建预测函数，这里实现的是一对多的方法，所以预测值是分类器有最大返回值的类别
prediction_output = tf.matmul(tf.multiply(y_target,b),pred_kernel)
prediction = tf.arg_max(prediction_output-tf.expand_dims(tf.reduce_mean(prediction_output,1),1),0)
accuracy = tf.reduce_mean(tf.cast(tf.equal(prediction,tf.arg_max(y_target,0)),tf.float32))
#准备好核函数，损失函数，预测函数以后，声明优化器函数和初始化变量
my_opt = tf.train.GradientDescentOptimizer(0.01)
train_step = my_opt.minimize(loss)
init = tf.initialize_all_variables()
sess.run(init)
#该算法收敛的相当快，所以迭代训练次数不超过100次
loss_vec = []
batch_accuracy = []
for i in range(100):rand_index = np.random.choice(len(x_vals),size=batch_size)rand_x = x_vals[rand_index]rand_y = y_vals[:,rand_index]sess.run(train_step,feed_dict={x_data:rand_x,y_target:rand_y})temp_loss = sess.run(loss,feed_dict={x_data:rand_x,y_target:rand_y})loss_vec.append(temp_loss)acc_temp = sess.run(accuracy,feed_dict={x_data:rand_x,y_target:rand_y,prediction_grid:rand_x})batch_accuracy.append(acc_temp)if(i+1)%25 ==0:print('Step #' + str(i+1))print('Loss #' + str(temp_loss))x_min,x_max = x_vals[:,0].min()-1,x_vals[:,0].max()+1
y_min,y_max = x_vals[:,1].min()-1,x_vals[:,1].max()+1
xx,yy = np.meshgrid(np.arange(x_min,x_max,0.02),np.arange(y_min,y_max,0.02))
grid_points = np.c_[xx.ravel(),yy.ravel()]
grid_predictions = sess.run(prediction,feed_dict={x_data:rand_x,y_target:rand_y,prediction_grid:grid_points})
grid_predictions = grid_predictions.reshape(xx.shape)
#绘制训练结果，批量准确度和损失函数
#等高线图
plt.contourf(xx,yy,grid_predictions,cmap=plt.cm.Paired,alpha=0.8)
plt.plot(class1_x,class1_y,'ro',label = 'I.setosa')
plt.plot(class2_x,class2_y,'kx',label = 'I.versicolor')
plt.plot(class3_x,class3_y,'gv',label = 'T.virginica')
plt.title('Gaussian Svm Results on Iris Data')
plt.xlabel('Pedal Length')
plt.ylabel('Sepal Width')
plt.legend(loc='lower right')
plt.ylim([-0.5,3.0])
plt.xlim([3.5,8.5])
plt.show()plt.plot(batch_accuracy,'k-',label='Accuracy')
plt.title('Batch Accuracy')
plt.xlabel('Generation')
plt.ylabel('Sepal Width')
plt.legend(loc = 'lower right')
plt.show()plt.plot(loss_vec,'k--')
plt.title('Loss per Generation')
plt.xlabel('Generation')
plt.ylabel('Loss')
plt.show()