作业2-线性分类器第一章感知机算法 (2)1.1算法原理 (2)1.2程序代码 (2)1.3运行结果及解释 (4)第二章最小二乘算法 (6)2.1算法原理 (6)2.2程序代码 (7)2.3运行结果及解释 (8)第三章支持矢量机算法 (10)3.1算法原理 (10)3.2程序代码 (11)3.3运行结果及解释 (13)第四章三种方法比较 (16)理解和体会 (18)附录 (18)主程序代码：stp2.m (18)生成样本数据代码createSample.m (20)绘图代码plotData.m： (21)第一章 感知机算法1.1 算法原理对于两类的情况，线性分类器是一个超平面: *T =w x 0 ，其中*w 是法向量，x 是训练集的增广向量（每一个训练样本的最后一维值为1），应该满足如下条件：*1*2T T w w >∀∈<∀∈w x 0x w x 0x该算法的代价函数定义为()()TYJ δ∈=∑xx w wx 其中Y 是所有的被分错的训练样本的集合，而针对每一个分错的样本x ，其对应的δx 满足:1211w w δδ=-∈=+∈x x x x ，因此()J w 一定大于0的。
现在的目标就是求解优化函数min ()J w ，为了简单起见，采用梯度下降法，()()YJ δ∈∇=∑w xx w x ，迭代步骤为(1)()()tYt t αδ∈+=-∑xx w w x ，其中t α是迭代步长，同样为了简单起见，可以取一个较小的常数（太大会导致迭代在最小值附近振荡，太小会导致迭代很慢）1.2 程序代码function [w, ws, miss] = perceptron( data, nSample, dim, alpha, nStep) %% 感知机算法 %% 输入 % data 训练数据% nSample 训练的个数，是一个向量（每个类的个数） % dim 代表特征的个数 % alpha 迭代步长 % nStep 迭代次数 % %% 输出% w 线性分类结果 w'x = 0; (x 是增广向量) % ws 迭代过程ws 的变化情况 % miss 迭代过程中分错数的变化情况%% 初始化权重向量 w = rand(dim+1, 1); ws = zeros(dim+1, nStep);miss = zeros(1, nStep);data1 = data{1, 1};data2 = data{1, 2};%% 感知机算法流程for i = 1 : nStep% 做第i次迭代ws(:, i) = w; % 存储当前w的值missNum = 0;% 第一类分错统计for k = 1 : nSample(1)% 遍历当前组的第k个实例x = data1(:, k);if(w' * x < 0)w = w + alpha * x; % 修改w，分错了x，（x属于第一类，本应该满足w'x > 0）missNum = missNum + 1;endend% 第二类分错统计for k = 1 : nSample(2)% 遍历当前组的第k个实例x = data2(:, k);if(w' * x > 0)w = w - alpha * x;missNum = missNum + 1;endendmiss(i) = missNum;endend1.3运行结果及解释对上述函数，生成实例的系数为{[2.0 0.8; -1.5 1.7;], [-1.7 1; 1.3 -0.6;]};分别代表两类数据的两个特征的正太分布的均值和系数。
α=，迭代201次的结果如下图1-1：当算法取步长0.001图1-1 感知机算法结果图图1-1的左边部分为分错次数变化图，说明了算法效果还不错，分错次数一开始降得很快，但因为两类数据不能完全分开，导致错误次数始终不能降到0，从右图中也可以看出，决策线从初始的绿色逐渐变回红色，不断地调整。
α=时，迭代201次结果如下图1-2所示：当取算法步长1图1-2 感知机算法结果图可以发现，由于步长太大的时候，分错样本数发生振荡，因此，梯度下降法不能把步长取太大。
α=，迭代201次的结果如下图1-1：生成样本系数修改为当算法取步长0.001{[2.0 0.8; -1.8 0.9;],[-1.9 1; 1.9 -0.6;]};时候两类可以完全分开，发现算法很快就得到了一条决策线（但是这根线离蓝色类很近，直观上讲并不是最佳的线）图1-3 感知机算法结果图下面给出三维的分类结果：图1-4 感知机算法三维分类结果图第二章 最小二乘算法2.1 算法原理此算法采用了不一样的代价函数，定义为：22()TJ =w y -w x ，其中y 的第i 项i y 代表每一个样本对应的函数值，可以用两种方式定义，第一种：1211T i i i Ti i i w w ==+∀∈==-∀∈y w x x y w x x （此种情况，就不考虑两类的权重），第二种：21211122/()/()T i i i Ti i i N N N w N N N w ==+∀∈==-+∀∈y w x x y w x x （此种情况，考虑了两类的权重）第二种方法中，12,N N 分别代表第一类和第二类的样本数量。
分析优化函数min ()J w ，目的是求解T =y x w ，则有：1()T T T -=⇒=⇒=y x w xy xx w w xx xy ，这个叫做求伪逆。
下面思考，这两种方法有什么不同呢？事实上，对于第一种方案，min ()J w 的效果就是得到三条平行的超平面，1211T T T w w =+∈==-∈w x x w x w x x ，第一个平面是第一类的线性拟合结果，第二个平面是决策面，第三个平面是第二类的线性拟合结果，这种情况下，决策面刚好位于两个拟合平面的中央。
对于第二种情况，得到的三个超平面变为21211122/()/()T T T N N N w N N N w =+∈==-+∈w x x w x w x x ，故而当12N N > 时， 决策面就更靠近第一类所拟合的超平面这是因为此时：212112/()/()N N N N N N +<+2.2程序代码function [w, ww] = meanSquareError( data, nSample, dim) %% mse算法最小化 ||y - w'x||%% 输入% data 训练数据% nSample 训练的个数，是一个向量（每个类的个数）% dim 代表特征的个数%%% 输出% w 线性分类结果 w'x = y; (y 值为1，或-1)% ww 带权重的，（y 值为 n1/n, -n2/n）%% 最小二乘流程n1 = nSample(1);n2 = nSample(2);n = n1 + n2;x = zeros(dim+1, n);y = zeros(n, 1);x(:, 1 : n1) = data{1, 1};x(:, n1+1 : n) = data{1, 2};%% 没有权重的情况y(1:n1, 1) = 1;y(n1+1 : n) = -1;% 最小二乘公式，伪逆w = inv(x * x') * x * y;%% 有权重的情况y(1:n1, 1) = n2 / n;y(n1+1 : n) = -n1 / n;% 最小二乘公式，伪逆ww = inv(x * x') * x * y;end2.3运行结果及解释针对生成系数{[2.0 0.8; -1.8 0.9;], [-1.9 1; 1.9 -0.6;]}; 一类有1000个样本，二类只有300个样本时，运行结果如下：图2-1 最小二乘算法结果图可以看到，两种方法生成了同样的拟合直线，但是在不带权重的条件下，决策面在两条拟合线的中央，而带权重的时候，决策面偏向了蓝色区域（第一类）。
当两类的样本数量一样的时候，就可以得到一样的结果。
图2-2 最小二乘算法结果图图中‘+’型黄色直线和实型黄色直线也重合了，验证了2.1节中理论的正确性。
下面给出三维的结果图：图2-3 最小二乘算法三维结果图图2-4 最小二乘算法三维结果图第三章 支持矢量机算法3.1 算法原理目的是最大化每一类的所有样本点到决策面的欧几里得距离中的最小距离。
可以参考july 的博客/v_july_v/article/details/7624837。
决策面函数()T g =x w x ，那么样本点x 到决策面的欧几里得距离是()g x w，我们可以通过缩放w ，使得第一类最接近决策面的样本点1x 满足是1()1g =x ，第二类最接近决策面的样本点2x 满足是2()1g =-x 。
也就是说优化问题变成了221()2()1J subject to Y =⋅≥T minimize w w w x ， 这是一个凸优化的问题，可以用cvx 工具箱解决。
cvx 工具箱的下载地址：/cvx/download/，当样本不可分的时候，如下图：图3-1 svm 算法不可分情况图使用凸优化求解的时候会发生不可解的情况。
就需要把优化问题转换为2211()2()11,2,...,01,2,...,N i i i i J C Y i Nsubject to i N ξξξ==+⋅≥-=≥=∑T minimize w w w x 其中C 是一个常量，用于控制决策面的结果（具体效果见3.3节），这也是一个凸优化的问题，可直接使用cvx 工具箱求解。
3.2 程序代码function [ out, cvx_optval] = stpCvxSvm(data, nSample, dim, type)%% svm 的优化求解，使用cvx 工具箱% min ||w|| s.t. y .* (w' * x) >= 1 (x 是增广向量)%%% 输入% data 训练数据% nSample 训练的个数，是一个向量（每个类的个数）% dim 代表特征的个数% type 表示svm 类型，如果为1表示训练集完全可分，否则不可分%%% 输出% out 线性分类结果 out'x = y; (y 值为1，或-1)% cvx_optval cvx 输出结果%% 初始化数据n1 = nSample(1);n2 = nSample(2);n = n1 + n2;x = zeros(dim+1, n);y = zeros(n, 1);x(:, 1 : n1) = data{1, 1};x(:, n1+1 : n) = data{1, 2};y(1:n1, 1) = 1;y(n1+1 : n) = -1;%% 核心代码，调用cvx 工具箱，优化该QP 问题if type == 1cvx_beginvariable w(dim+1, 1);minimize( norm(w, 2));subject toy .* (x' * w)>= 1;cvx_endelsecvx_beginvariables w(dim+1, 1)rho(n);minimize( norm(w, 2) + 1 * sum(rho) ); subject toy .* (x' * w) >= 1 - rho;rho >= 0;cvx_endendout = w;end3.3运行结果及解释对于二维情况，在线性可分的时候，结果如下：图3-2 svm算法线性可分结果图可以看到，决策线（黄色线）位于两类的支持向量的中央。
