SVM python 实现

即刻关注我们，发现世界的美好

前言

上期我们学习了SVM的原理，下面我们将进一步学习用Python如何实现SVM。

这一块实现原理：选取一对ai、aj，由于ai和aj之间存在线性关系

（ai*yi+aj*yj = t），然后ai用aj来表示，代入目标函数L中，观察可知L是一个关于aj的二次函数，开口向下，这样通过调整aj的大小，可以求得L的最大值，这里实现时采用的是每一次计算对于aj增加一个微小的值，然后判断L是否一直在增大，达到最高点记录下aj的大小，然后保证alpha向量所有的aj都被调整过，这时结束循环。

Python实战

def train_a(x, label, a, used, length, step):

"""

x 标识测试数据

label 标签

a 标识 alpha

used 表示 被计算过的数

length 表示跨度，在这个0-length的跨度内找最大值

step 表示步长

"""

for i inrange(0,len(a)):

max_value =-1

max_j = 0

max_index =-1

if used[i]== 0:

used[i]= 1

# 选aj

for jin range(0,len(a)):

ifj != i and used[j] == 0:

used[j] = 1

# 确定ai的值

for d in range(1,length):

a[i] = d/step

oldja = a[j]

aj = cal_aj(a,i,label,j)

if aj >= 0:

k =calculate(a,x,label)

if k> max_value:

# 选取最大值

max_value = k

max_index = d

max_j = j

else:

a[j]=oldja

if max_index > -1 :

# 找到第一个符合条件的aj就可以

a[i] = max_index/step

a[max_j] = cal_aj(a,i,label,max_j)

break

else:

# 如果没找到 需要回溯

used[j]=0

#a[j] = oldaj

return a

上面这种实现，非常暴力，因此引入另一种实现方式，基于目标函数一次优化两个alpha变量，这两个alpha变量对应的label值是相反的，因为只有这样在才能取一对alpha都大于零并满足等式约束条件，推导过程这里就略去，和下面的SMO推导过程类似，但简化了不少。大体思路是由于一对alpha是线性关系，经过线性变换代入到L中，可以发现对于单独alpha是一个二次函数，求其导数为零，即可确定一对alpha的值。

推导出的公式如下：

关键代码如下：

def calculate_alpha_i(i,j):

return-1*(label[i]*mul_i_j(sub_i_j(x[i],x[j]),sub_i_j(t_mul_x(get_t(i,j),x[j]),sum_c(i,j)))+label[i]*label[j]-1)/(mul_i_j(x[i],x[i])+mul_i_j(x[j],x[j])-2*mul_i_j(x[i],x[j]))

def cal_alpha():

i,j = random_get()

while i!=-1 and j!=-1:

alpha_i=calculate_alpha_i(i,j)

alpha_j=(get_t(i,j)-alpha_i*label[i])*label[j]

alpha[i]=alpha_i

alpha[j]=alpha_j

i,j=random_get()

源代码上传到 GitHub上svm python实现

https://github.com/parker78/machine-learning/blob/master/svm-learn.ipynb

DIG