Py 机器基础及其实践 2

第5章感知机与支持向量机5.1线性可分的感知机5.3线性SVM算法实现5.2SVM5.4非线性SVM与核函数5.6本章小结15.5SVM算法实现---鸢尾花的分类5.1线性可分的感知机1.感知机模型假设输入样本空间，输出空间是Y={+1,-1}，输入样本表示样本的特征向量，即输入空间的样本点；输出表示样本的类别。从输入样本空间到输出样本空间的函数可表示为：该函数称为感知机（Perceptron），其中，称为权值（Weight）或权值向量（WeightVector），称为偏置（Bias），sign为符号函数，即这个超平面将特征空间划分为两部分，这两部分的样本点分别被分成正、负两例，超平面S就是分离超平面，如图5-1所示。图5-1中，方块和圆形分别代表不同的类别，实线表示区分两种类别的超平面，理论上这种超平面有无数条，都可能是感知机的解。判决函数若f(x)>0，则属于正例；若f(x)<0，则属于负例。在特征空间中，令判决函数g(x)=，线性方程是一个超平面S，其中w是超平面的法向量，b是超平面的截距。这个超平面将特征空间划分为两部分，这两部分的样本点分别被分成正、负两例，超平面S就是分离超平面。2模型参数学习任意一点(x,y)到直线的距离为，因此二维样本点(x,y)到线性方程的距离为，其中，。，对于误分样本点(xi,yi)，当时，有；当时，有。因此，

于是误分样本点到超平面S的距离为：若超平面S的误分样本点个数为N，则误分样本点到超平面S的总距离为：采用随机梯度下降法（StochasticGradientDescent，SGD）学习参数w和b：参数w和b的迭代更新公式：输入：训练数据集D={(x1,y1),(x2,y2),…,(xN,yN)}、迭代次数、学习率，其中：，Y={+1,-1}。过程：（1）初始化参数：，b=0。（2）对于j=1,2,…,N，当为空集，即没有误分样本点，则结束循环，否则转到第（3）步执行。（3）任意取X中的样本点(xi,yi)更新参数。输出：感知机模型参数w和b，并利用计算分类的准确率。利用以上感知机算法对样本进行分类，其散点图及分类结果如图5-4所示。5.1.3手工设计感知机模型感知机可用于解决线性可分的问题。已知正样本点x1=(3,3)T,x2=(6,5)T,负样本点x3=(2,1)T，用感知机学习算法的原始形式求感知机模型f(x)=sign(w⋅x+b)。这里,w=(w(1),w(2))T,x=(x(1),x(2))T。初始时，w0=(0,0)T,b0=0。1.构建损失函数minL(w,b)=−∑yi(w⋅xi+b)2.利用梯度下降法求解w,b。设步长为1，取初值

w0=(0,0)T,b0=0

(1)对于

x1,由于y1(w0⋅x1+b0)=0

，则表明未被正确分类，更新w,b。w1=w0+x1y1=(3,3)T,b1=b0+y1=1，得到线性模型w1x+b1=3x(1)+3x(2)+1（2）对

x1,x2

，显然

yi(w1⋅xi+b1)>0

，则表明被正确分类，不作修改。对于x3，有yi(w1⋅xi+b1)<0，则表明被误分类，更新w，b。w2=w1+x3y3=(1,2)T,b2=b1+y3=0，得到

线性模型w2x+b2=x(1)+2x(2)（4）对于

x1

，显然有yi(w3⋅xi+b3)<0

，被误分类，更新w、b。w4=w3+x1y1=(-1,1)T+(3,3)T=(2,4)T,b4=b3+y1=2得到线性模型w4x+b4=2x(1)+4x(2)+2（5）对于x1，x2，显然

yi(w4⋅xi+b4)>0

，被正确分类，不作修改。对于x3，有yi(w4⋅xi+b4)<0，被误分类，更新

w、bw5=w4+x3y3=(2,4)T-(2,1)T=(0,3)T,b5=b4+y3=1得到线性模型w5x+b5=3x(2)+1按以上步骤执行下去，直到w12=(-4,7)T,b12=-2迭代次数误分类点wbwx+b1x1(3,3)T13x(1)+3x(2)+12x3(1,2)T0x(1)+2x(2)3x3(-1,1)T-1-x(1)+x(2)-14x1(2,4)T22x(1)+4x(2)+25x3(0,3)T13x(2)+16x3(-2,2)T0-2x(1)+2x(27x1(1,5)T1x(1)+5x(2)+18x3(-1,4)T0-x(1)+4x(2)9x3(-2,8)T-1-3x(1)+3x(2)-110x1(0,9)T09x(2)11x3(-2,8)T-1-2x(1)+8x(2)-112x3(-4,7)T-2-4x(1)+7x(2)-2表5-1感知机模型求解的迭代过程对于二维数据，其感知机算法实现如下：whileTrue:flag=True#标记是否存在误分类样本foriinrange(len(x_train)):#遍历训练样本xi=x_train[i]yi=y_train[i]#判断yi*(wx+b)<=0ifyi*(np.inner(self.w,xi)+self.b)<=0:#若存在误分类样本flag=False#将flag标记为False#更新w和b的值self.w+=self.rate*np.dot(xi,yi)self.b+=self.rate*yiifflag:break#输出w和bprint('w='+str(self.w)+',b='+str(self.b))【例5.1】两类学习样本M1和M2的特征数据如表5-1所示，请利用Python编写感知机求线性判别函数的程序，求出两类模式的线性判别函数权向量。deffit_raw_mod(w,train_data,lr=1,max_epoch=None,min_error_rate=0.15):

"""

原始模式的感知机训练方法，当达到最大迭代次数或错误率降到最小范围退出

train_data：训练数据集

lr：学习率

max_epoch：最大迭代次数

min_error_rate：最小错误率

"""

w=np.zeros(train_data.shape[1]-1)#根据训练集维度初始化权重系数

epoch=1#记录迭代次数

whileTrue:

error_count=0#记录错误分类样本数

forsampleintrain_data:

xi=sample[0:-1]

yi=sample[-1]

distance=yi*(np.inner(w,xi)+b)#yi*(w⋅xi*+b)

ifdistance<=0:#对于判断错误的样本点

w+=lr*sample[-1]*sample[0:-1]

b+=lr*sample[-1]

error_count+=1

#每完成一次迭代之后，验证一次准确率，准确率达标则退出

current_error_rate=float(error_count)/train_data.shape[0]

ifcurrent_error_rate<=min_error_rate:

break

ifisinstance(max_epoch,int)andepoch>=maxepoch:

break

epoch+=1

print('w:{0},b:{1}'.format(w,b))

show_graph(train_data)5.2SVM学习基础学习认知能力信息素养高支持向量机是Cortes和Vapnik于1995年提出的一种基于统计学习的二分类模型。它是一种监督学习方法，在学习过程中通过最大化分类间隔使得结构风险最小化。从图5-2可以看出，能将不同样本分开的超平面有很多，但只有一条超平面位于两类样本的“正”中间，这个超平面通常用一个方程d(X)=0来表示，d(X)被称为判决函数或决策函数。图5-1所示是两类线性可分的样本数据分布及划分的示例。图中的线段就是对样本分隔的超平面。5.2SVM1.间隔最大化在对样本数据分类时，超平面离数据点的间隔越大，产生误差的可能性就会越小，也就是分类的确信度越大。因此，为了使分类的确信度尽可能高，需要让选择的超平面尽可能地最大化这个间隔。以最大间隔把两类样本分开的超平面，称之为最大间隔超平面。分类问题中的最大间隔、支持向量表示如图5-5所示。5.2SVM支持向量就是离最大间隔超平面最近的样本点，根据前面得到的支持向量到超平面的距离为将上式进行变换，进而有：5.2SVMSVM算法的目标就是最大化这个几何间隔d：间隔最大化问题就是求最优化问题：5.2SVM这是一个凸二次规划问题，不容易求解，可用拉格朗日乘子法对其对偶问题进行求解。对上面的公式构造拉格朗日函数：其中，。原问题与对偶问题有相同的解：调整w和b，使拉格朗日函数取最小值。5.2SVM将上式代入拉格朗日函数：下面调整参数，使目标函数取得最大值：对任意的支持向量（xs,ys），有：5.2SVM输入：训练数据集D={(x1,y1),(x2,y2),…,(xN,yN)}、迭代次数、惩罚因子C、学习率，其中：，

。过程：（1）初始化参数：，b=0。（2）对于j=1,2,…,N：①计算误差向量，其中。②取出误差最大的一项，即。③如果

，则退出循环；否则对该样本数据利用随机梯度下降算法进行优化：

输出：SVM模型参数w和b，并利用计算分类的准确率。5.3线性SVM算法实现1分别随机生成两类样本数据各20条，绘制散点图#生成二维正态分布的样本数据mu=np.array([3,5])Sigma=np.array([[1,0],[0,2]])#半正定矩阵Q=np.linalg.cholesky(Sigma)sigma=np.array([2,4])x1=np.random.normal(0,1,(20,2))5.3线性SVM算法实现为了训练SVM算法中的w和b参数，可利用cvxopt模块库中的solvers.qp函数求解，其格式为cvxopt.solvers.qp(P,q[,G,h[,A,b[,solver[,initvals]]]])。二次规划问题的标准形式如下：Gx≤b表示的是所有的不等式约束，同样，若存在诸如x≥0的限制条件，也可以通过乘以−1转换为≤的形式。Ax=b表示所有的等式约束。5.3线性SVM算法实现#y的内积r=np.inner(y,y)#定义凸优化pq方法p=matrix(r*m)#目标函数q=matrix(np.ones(40)*-1)A=matrix(y.reshape(1,-1))#定义等式约束b=matrix(0.)#定义不等式约束g=matrix(np.vstack((np.eye(40)*-1,np.eye(40))))h=matrix(np.vstack((np.zeros(len(y)).reshape(-1,1),np.ones(len(y)).reshape(-1,1)*C)))5.4非线性SVM与核函数所谓线性不可分，是指用线性分类器进行划分时，存在一些样本会被误分类的情况。对于在有限维度向量空间中线性不可分的样本，我们将其映射到更高维度的向量空间里，再通过间隔最大化的方式，学习得到支持向量机，就是非线性SVM。5.4非线性SVM与核函数对于图5-7中线性不可分问题，在原空间中无法用一条直线将正例和副例正确分隔开来，但可通过一个圆形曲线分隔开来，这就属于非线性分类问题。而求解分隔超曲面要比求解分隔超平面复杂得多，但我们可以将这样的非线性分类问题通过非线性变换，将原空间中的数据映射到高维的空间H中5.4非线性SVM与核函数序列最小优化（SequentialMinimalOptimization，SMO）算法作为非线性SVM的典型代表，于1998年由JohnPlatt提出，目前被广泛应用于各领域。SMO算法的思想是将大的优化问题转换为多个小优化问题，这些小的优化往往很容易求解，并且对其进行顺序求解和作为整体求解的结果是完全一致的。输入：训练数据集D={(x1,y1),(x2,y2),…,(xN,yN)}、迭代次数、容错误差，其中：，={+1,-1}。过程：（1）初始化参数：，，计算核矩阵：

5.4非线性SVM与核函数2）对于j=1,2,…,N：①选择违反KKT条件最严重的样本点(xi,yi)，若违反程度小于容错误差，则退出循环。②否则，选择其他任何一个样本点，其对应下标为j，针对和，构造一个新的只有两个变量的二次规划问题，并求出解析解。具体地说，就是更新参数：5.4非线性SVM与核函数③利用更新、b1：④利用和进一步更新b1、b2和ei：⑤利用和更新预测向量：5.4非线性SVM与核函数根据SMO算法描述，我们来实现SVM分类器。在构造SVM分类器之前，首先加载样本数据，观察散点图的分布情况，如图5-8所示。#利用测试样本进行评测error_count=0test_dat_mat=np.mat(test_data)test_label_mat=np.mat(test_label).transpose()rows,cols=np.shape(test_dat_mat)foriinrange(rows):kernel_eval=kernel_value(sv_sample,test_dat_mat[i,:],('rbf',k))pre=kernel_eval.T*np.multiply(sv_label,lambdas[sv_index])+b#预测值

ifnp.sign(pre)!=np.sign(test_label[i]):error_count+=1accuracy=100*(1-float(error_count)/rows)print("准确率:%%%f"%(accuracy))总迭代次数:141[01256712192023343637384143454651]有19个支持向量准确率:%100.0000005.4SVM回归SVM也可以用于解决回归问题。假定训练数据集D={(x1,y1),(x2,y2),…,(xN,yN)}，回归模型就是要让与y尽可能接近，以确定w和b的值。f(x)-与f(x)+之间的区域称为街道或管道区域。最小化误差函数的优化目标为：5.6SVM算法实现──鸢尾花的分类SVM可分为两类：支持向量机分类（SupportVectorClassification，SVC）和支持向量机回归（Supp