对这两个式子进行优化。下面我们开始讨论SMO算法,然后给出一个简化版本以便理解它的工作流程,最后才将会给出完整的算法,它比简化版的运行速度要快很多。
我们先对算法进行简化处理,了解基本思路,在基于简单版实现完整版。PlattSMO算法中的外循环要确定优化的最佳alpha对,而简化版却会跳过这个部分,首先在数据集上遍历每一个alpha,然后在剩下的alpha集合中随机选择另一个alpha,从而构建alpha对。这里有一点相当重要,就是我们要同时该表两个alpha。之所以这样是因为约束条件:
#得到每行的类标签和整个数据矩阵defloadDataSet(fileName):dataMat=[]labelMat=[]fr=open(fileName)forlineinfr.readlines():lineArr=line.strip().split('\t')#dataMat.append([float(lineArr[0]),float(lineArr[1])])dataMat.append([float(lineArr[0]),float(lineArr[1])])labelMat.append(float(lineArr[2]))returndataMat,labelMat#i:alpha的下标m:所有alpha的数目,只要函数值不等于输入值i,函数就会随机选择defselectJrand(i,m):j=iwhile(j==i):j=int(random.uniform(0,m))returnj#用于调整大于H或小于L的alpha值defclipAlpha(aj,H,L):ifaj>H:aj=HifL>aj:aj=Lreturnaj
每个函数的功能都写在函数中了。上述工作完成之后,就可以使用SMO算法的第一个版本了,伪代码大致如下:
创建一个alpha向量并将其初始化为0向量
我们对上面的结果进行查看:
alpha中有太多的0了。我们只看非零的元素有一下三个
下面我们观察输入样本中的支持向量:即对应alpha大于0的,有三个