基本梳理
根据《机器学习实战》和周志华《机器学习》，总结要点如下：
- SVM本质是要求具有最大间隔距离的超平面；
- 求解最大间隔平面时，需要先求得距离间隔平面最近的点，即“支持向量”(见西瓜书P123对式6.5,式6.6的解释)
- 基于以上，为了求解方便引入拉格朗日乘子得到最大距离公式的对偶式作为新的目标函数以及约束条件；问题：最终目标函数的aj是时怎么出来的？
- 根据3所得的目标函数，求出每个拉格朗日乘子alpha/α,就可以求出超平面模型的参数w，b,进而得到超平面。
- 在4中，拉格朗日乘子αi每个训练样本(xi,yi)相对应；根据计算，ai>0的点即支持向量对应的点(《机器学习实战》与西瓜书P124)
- 在计算3中所得目标函数时，使用SMO算法，关于SMO具体可见西瓜书P124与《机器学习实战》P94
- 以上1-5都是处理“线性可分”的情况
- 在处理“非线性”的情况时，需要引入“核”函数，西瓜书P127。
-
注意：SVM的分类结果用1和-1表示，原因见《机器学习实战》P92
要点整理
-
序列最小优化SMO算法
-
核函数kernel
-
SVM类别一般用-1,1
-
线性可分 N维度 超平面 --- 决策边界
-
支持向量support vector: 离分割超平面最近的那些点； 找到最大化支持向量到分割面的距离的优化方法
- 松弛变量：《机器学习实战》P93
-
SMO算反的工作原理是：每次循环中选择两个alpha进行优化处理。一旦找到一对合适的alpha,那么就增大其中一个同时减小另一个。这里
所谓的“合适”是指两个alpha必须要符合一定的条件，条件之一是这两个alpha必须要在间隔边界之外，第二个
条件是这两个alpha还没有进行过区间化处理或不在边界上。 -
《机器学习实战》P98：由于SMO算法的随机性，运行结果可能会有所不同
代码
只写了一些基本的代码，主要是看以上的整理
# -*- coding: utf-8 -*-
import numpy as np
def loadDataSet(fileName):
"""
https://github.com/yihui-he/SVM/blob/master/testSet.txt
"""
dataMat = []
labelMat = []
fr = open(fileName,'r')
for line in fr.readlines():
lineArr = line.strip().split()
dataMat.append([float(lineArr[0]),float(lineArr[1])])
labelMat.append(float(lineArr[2]))
return dataMat,labelMat
def selectJrand(i,m):
"""
功能：
param: i: alpha的下标
param: m: 所有alpha的数目
只要函数值不等于输入值i，函数就会进行随机选择
"""
j = i
while (j == i):
j = int(np.random.uniform(0,m))
return j
def clipAlpha(aj,H,L):
"""
H和L是什么？？？？？
功能：调整大于H或小于L的alpha值
param: aj:
param: H:
param: L:
"""
if aj > H:
aj = H
if L > aj:
aj = L
return aj
def smoSimple(dataMatIn, classLabels, C, toler, maxIter):
"""
机器学习实战P96代码
param: dataMatIn: 数据集
param: classLabels: 类别标签
param: C:常数C (应该就是松弛变量？？？)
param: toler: 容错率
param: maxIter: 取消前最大的循环次数
"""
# 将列表转化为矩阵；并使泪飙标签向量的每行元素都和数据矩阵中的行一一对应
dataMatrix = np.mat(dataMatIn)
labelMat = np.mat(classLabels).transpose()
m,n = np.shape(dataMatrix)
b = 0
# 构建一个alpha列矩阵，矩阵中元素都初始化为0
alphas = np.mat(np.zeros((m,1)))
# iter_times是没有任何alpha改变的情况下便利数据集的次数
iter_times = 0
# 外循环：控制迭代次数
while (iter_times < maxIter):
# alphaPairsChanged记录alpha是否已进行优化；初始置为0
alphaPairsChanged = 0
# 内循环：对数据集中每个数据向量
for i in range(m):
# fXi是预测的类别
fXi = float(np.multiply(alphas, labelMat).T*(dataMatrix * dataMatrix[i,:].T)) + b
# Ei表示误差： 预测解雇fXi与真实结果比对
Ei = fXi - float(labelMat[i])
# 如果该数据向量可以被优化，则进入优化过程
# 如果误差很大(对正间隔和负间隔都进行测试)，则可以对数据实例所对应的alpha进行优化
# 需要检查alpha不能等于0或C,由于后面alpha小于0或大于C时都将被调整为0或C,所以一旦在if中它们等于这两个值的话，
# (接上一行)则说明他们已经在“边界”上，不值得再进行优化了
if ((labelMat[i] * Ei < -toler) and (alphas[i] < C)) or ((labelMat[i] * Ei > toler) and (alphas[i] > 0)):
# 随机选择第二个alpha，即alpha[j]
j = selectJrand(i, m)
# 同样的方法计算这个alpha的误差
fXj = float(np.multiply(alphas,labelMat).T * (dataMatrix * dataMatrix[j,:].T)) + b
Ej = fXj - float(labelMat[j])
# copy方法激素老的alpha值，以便稍后将新的alpha与老的alpha比较 （第一个alpha还没有进行优化？？）
alphaIold = alphas[i].copy() # copy会分配新的内存
alphaJold = alphas[j].copy()
# 计算L和H,保证alpha在0到C之间
if (labelMat[i] != labelMat[j]):
L = max(0, alphas[j] - alphas[i])
H = min(C, C + alphas[j] - alphas[i])
else:
L = max(0, alphas[j] + alphas[i] - C)
H = min(C,alphas[j] + alphas[i])
# 如果L和H相等，则不做任何改变，直接执行continue
if L == H:
print ("L == H")
continue
# ega是alpha[j]的最优修改量；如果eta=0,说明需要退出for鲟鳇的当前迭代过程(这里是简化处理)
eta = 2.0 * dataMatrix[i,:] * dataMatrix[j,:].T - dataMatrix[i,:] * dataMatrix[i,:].T - dataMatrix[j,:] * dataMatrix[j,:].T
if eta > 0:
print ("eta >= 0")
continue
alphas[j] -= labelMat[j] * (Ei - Ej) / eta
alphas[j] = clipAlpha(alphas[j],H,L)
# 检查alpha[j]是否有轻微改变，如果是，则退出循环
if (abs(alphas[j] - alphaJold) < 0.00001):
print ("j not moving encough ")
continue
# 对alpha[i]进行同样改变，改变的大小一样，但是方向相反(即如果一个增大，另一个就减小) 对alpha[j]的改变在哪进行的？？？
alphas[i] += labelMat[j] * labelMat[i] * (alphaJold - alphas[j])
# 对两个alpha设置一个常数b
b1 = b - Ei - labelMat[i] * (alphas[i] - alphaIold) * dataMatrix[i,:] * dataMatrix[i,:].T - labelMat[j] * (alphas[j] - alphaJold) * dataMatrix[i,:] * dataMatrix[j,:].T
b2 = b - Ej - labelMat[i] * (alphas[i] - alphaIold) * dataMatrix[i,:] * dataMatrix[j,:].T - labelMat[j] * (alphas[j] - alphaJold) * dataMatrix[j,:] * dataMatrix[j,:].T
if (0 < alphas[i]) and (C > alphas[i]):
b = b1
elif (0 < alphas[j]) and (C > alphas[j]):
b = b2
else:
b = (b1 + b2) / 2.0
# 如果程序没有continue，执行到这里，则说明成果地改变了一对alpha，因此改变alphaPairsChanged
alphaPairsChanged += 1
print ("iter_times: %d i: %d, pairs changed %d" %(iter_times, i, alphaPairsChanged))
# 如果两个向量都没被优化，则增加迭代数目，继续下一次循环
if (alphaPairsChanged == 0):
iter_times += 1
else:
# 如果发生了alpha的更新，则将iter_times置为0后继续运行
# 只有在所有数据集上便利maxIter次切不再发生任何alpha修改之后，程序再回停止并退出while循环
iter_times = 0
print ("iteration number: %d" %iter_times)
return b,alphas
if __name__ == '__main__':
dataArr,labelArr = loadDataSet('svm_testSet.txt')
b,alphas = smoSimple(dataArr, labelArr, 0.6, 0.001, 40)
# 输出支持向量的点
for i in range(100):
if alphas[i] > 0.0:
print (dataArr[i],labelArr[i])
由于数学的内容太多，一时看不懂，先整理这些基础的吧。
2018.05.24
网友评论