《机器学习PLA算法.doc》由会员分享，可在线阅读，更多相关《机器学习PLA算法.doc（17页珍藏版）》请在金锄头文库上搜索。
1、PLA and POCKET问题描述-算法思想设计描述-伪代码-复杂度分析-编程-上机调试-实验分析-结论，本文是采用这样的顺序描述算法的。本文所写算法对应于一个NP-Hard问题，主要采用近似求解算法和贪心算法的思想。这对应于机器学习中Binary Classification，PLA ，Pocket Algorithm问题描述：银行发信用卡问题。现有一群人，数量为N，（N很大），假设他们在一个银行中的登记记录数据我们已经得到。对于每个人记录的数据有（对应第i个人的信息，相应的我们可以认为是这个人的一些个人数据的量化值，比如年龄、学历、收入、工作年限等等，他们会对应于一组数值如0.94544
2、 0.42842 0.79833 0.16244 -1 对应于）。如果y是-1，则对应于银行没有给他发信用卡。如果是y=1，则是发给了它信用卡。现在由这样的一推数据如何得到一个函数，有这些训练集得到这个目标函数。并用这个目标函数作用于对于一群待发信用卡的人作出判断，一边给银行提供发卡的依据。具体数据见附录Q18Train.m为训练数据集， Q18TestData.m为待判断数据集，这里我们可以叫他测试数据集。对于银行，他之前会设置一个发信用卡的门限值threshold.算法描述和伪代码表述：之前我们都是用PLA（perception learning algorithm）：它是针对于线性可分的
3、训练集的。也就是这样的所有的数据，比如说是二维数据点，可以用一条直线将他们分成两派，一片是可发卡的数据，直线另一侧则是不可发卡数据。将用户数据加权求和与门限值相比较，作差为正则发卡，为负则不发卡。这里假设一个Hypothesis datasets ，每计算一次都是一个H，如果有错则修正，一直到所有的数据都没有错误，这样的H就是我们的未知的目标函数f。对于h，这里h可以化简一下，PLA的算法描述是：wt是类似于那条直线的法向量，（）是一个人的数据记录for t=0,1,2,3.find a mistake of wt called ( )try to correct the mistake by
4、 对于线性可分数据集PLA算法是收敛的证明：，t是代表第t次得到的结果或者第t次所用的数值。 （1）这里是单增的，如果从向量角度看，两个向量内积越大，如果排除其模值得快速增大，可以看做是其角度在不断的调整，逐渐变得同向。（2）就是证明其模值变化有限。（2）这里可以认为每次增加的步长有限，同时也说明两个向量的内积越来越大，不是因为其模值快速变化所致。因此可以看出最终得到的Wt是收敛的（对于线性可分数据集）。而且可以算出t的取值：而且： 则这是线性可分数据集的PLA终止时的T的次数表达式。 PLA算法对于线性可分的数据源是可以最后能得到目标函数的。但是对于线性不可分的数据集，它不会自动的停止。对于
5、非线性不可分的数据集，如果对其分类，它将是一个NP-Hard问题。这里的Pocket算法，则是一种近似算法，他是用贪心算法，每次将PLA修正的wt与pocket记录的pwt比较，对于所有数据集犯错最少的那个作为新的pwt，这样PLA一直进行，得到修正的值wt与pwt比较，如果wt的犯错少，则将pwt更新为wt。如果进行的Pocket算法运行时间足够长，因此我们就可以找到一个算错尽可能少的pwt。并以此来进行对于测试数据集的分类。Pocket算法如果对于线性可分数据集，它会自动停止，并且得到一个wt，线性可分数据集，然后用于测试。本文主要是采用pocket算法（）：/%funpocket2.mi
6、nitialize pocket weights pwtfor t=0,1,2,. /%find a (random) mistake of wt called (xn(t),yn(t)while !flagd-(Maxnum-1)*rand()+1;/%Xd representative the d row datas xd1=1,xd2.n=Xd1.n-1;y=Xdn,if sign(Wt*xd)=yflagfunWtError(Wt+1,dataset)pwt=Wt+1;until enough iterations t= stop.return pwt (as Wpocket)%对应于
7、wn的训练集的错误概率计算%funWtError.m funWtError(wt1,dataset)dataset matrix n rows ,m colsxn1=1;while count=nxn2.m=datasetcount1.m-1;yn=datasetcountm;if sign(wn1*xn)=ynerrFlag-=errFlag+1;count-=count+1;reutrn errFlag/n;关于pocket算法的几点说明：（1）对应于上述算法，在funpocket2.m中initialize pocket weights pwtfor t=0,1,2,./%find a
8、(random) mistake of wt called (xn(t),yn(t)查找一个随机的带有错误数据的Wt，这样随机找是很慢的可以改进一下，Wt，对应于这个法向量，先判断出相应有错误的数据集，然后再再从这里面进行随机，这样的查找更快些。对应于程序中的实现是采用了这种方式。而不是每次都随机选一行的数据，判断是不是有错，有错在更新，如果一直随机都是没错的那么就相当的耗费时间。（2）pocket算对于线性不可分数据集是不会终止的，也就是说，他是一个NP问题。如果数据集大体上是线性可分数据集，只有一部分点不可分，我们只需要运行足够长的时间，或者pwt进行一定数量的替换，用这种T次更新取代完全
9、更新到正确的t次数的近似和每次遇到好的Wt+1都才用贪心的算法替代pwt，这样也能得到一个比较好的分线结果。复杂度分析对于近似算法解NP问题，这里的时间复杂度：对于，其时间复杂度为，find a (random) mistake of wt called (xn(t),yn(t)时间复杂度为对应于wn的训练集的错误概率计算总的时间复杂度：，为一个向量与另一个向量的乘积所用时间。 ，又是n的函数（一个多项式），。此时如果采用给出的伪代码中的随机选一个来判断数据对于Wt是否有误，这样就像是非确定算法，采用猜测的形式将所有的可能性随机的选一个，结果是YES/NO，NO时继续随机选取，猜算可以在多项式
10、时间内完成；验算其实就计算的有限时间了。有限时，就是采用近似的算法，虽然并不一定能够得到一个全局的满足的Wt，但是对于绝大多数的点分类还是可以的，这就是我们想要的。 因此，近似的贪心算法思想的pocket算法其时间复杂度是多项式的函数，可以在时间多项式内完成。代码编程(matlab实现)%/%FunRandArray.m function arr= FunRandArray(Maxnum,repeatFlag)%Arraymaxnum,if not input ,the repeatflag=1%repeatFlag=0 %generate the the navie cycly data s
11、et%repeatFlaf=1 % ,generate the rand ,arr may have the same data%repeatFlaf=2 %generate the the rand data set visit, rand(state,sum(100.*clock)*rand(1); arr=(Maxnum-1).*rand(1,Maxnum)+1; arr1=ceil(arr(:,:); flag=0; arr=arr1;%nature sequence if repeatFlag=0 for i=1:Maxnum arr(i)=i; end else if repeat
12、Flag=1 else if repeatFlag=2 %to change into the different data AllData=zeros(1,Maxnum); for i=1:Maxnum ALLData(i)=i; end %/ %clear the same data in the arr for i=1:Maxnum flag=0; for j=1:Maxnum if arr(i)=ALLData(j) flag=1; ALLData(j)=-1; break; end end if flag=0 arr(i)=0; end end %/ %add the no exist data b
