机器学习PLA算法

1、PLAandPOCKET问题描述算法思想设计描述-伪代码-复杂度分析编程-上机调试实验分析-结论，本文是采用这样的顺序描述算法的。本文所写算法对应于一个NP-Hard问题，主要采用近似求解算法和贪心算法的思想。这对应于机器学习中BinaryClassification,PLA,PocketAlgorithm问题描述：银行发信用卡问题。现有一群人，数量为N,(N很大)，假设他们在一个银行中的登记记录数据我们已经得到。对于每个人记录的数据有Xi=(x1,x2，,xn)(对应第i个人的信息，相应的x1,x2，,xn我们可以认为是这个人的一些个人数据的量化值，比如年龄、学历、收入、工作年限等等，他们会

2、对应于一组数值如0.945440.428420.798330.16244-1对应于Xi，X2,%,x4,y)。如果y是-1,则对应于银行没有给他发信用卡。如果是y=1,则是发给了它信用卡。现在由这样的一推数据如何得到一个函数，有这些训练集得到这个目标函数。并用这个目标函数作用于对于一群待发信用卡的人作出判断，一边给银行提供发卡的依据。具体数据见附录Q18Train.m为训练数据集，Q18TestData.m为待判断数据集，这里我们可以叫他测试数据集。对于银行，他之前会设置一个发信用卡的门限值threshold.算法描述和伪代码表述：之前我们都是用PLA(perceptionlearningal

3、gorithm)：它是针对于线性可分的训练集的。也就是这样的所有的数据，比如说是二维数据点，可以用一条直线将他们分成两派，一片是可发卡的数据，直线另一侧则是不可发卡数据。将用户数据加权求和与门限值相比较，作差为正则发卡，为负则不发卡。这里假设一个Hypothesisdatasets,每计算一次都是一个H,如果有错则修正，一直到所有的数据都没有错误，这样的H就是我们的未知的目标函数fodh(x)=signwx-threshold),对于h,.i11,x>0sign(x)=0,x<0这里h可以化简一下，-threshold可以当做w0,因此对应于x0=1dh(x)=sign('

4、四内),iRh(x)=sign(WTX)工-1IPLA的算法描述是：Wt是类似于那条直线的法向量，(Xn(t),yn(t)是一个人的数据记录fort=0,1,2,3.findamistakeofwtcalled(xn(t),yn(t)sign(WXn(t)»(t)trytocorrectthemistakeby皿1-Wt1(t)Xn(t)对于线性可分数据集PLA算法是收敛的证明：Yn(t)WTfXn(t)之mjnYnWTfXn>0,t是代表第t次得到的结果或者第t次所用的数值。WfTWt1=WfT(Wtyn(t)Xn(t)(1)之WfTWt+minynWfTXnWt这里是单增的

5、，如果从向量角度看，两个向n-WfTWt量内积越大，如果排除其模值得快速增大，可以看做是其角度在不断的调整，逐渐变得同向。(2)就是证明其模值变化有限。(2)|WtJ=|Wt+yn(t)Xn(t)二|Wt+2yn(t)WTtXn(t)+|yn(t)Xn(t)4Wt+0+|yn(t)Xn(t),(有错时，)Wt作为法线的直线去判断训练数据集是有错的，Usign(WTtXn)"y")二y(t)WTtXn(t)<022Wti=Wtyn(t)Xn(t)|22£Wt|-maxynXn22Wt|-maxXn这里可以认为每次增加的步长有限，同时也说明令M=maxn,2WW

6、tXn2M两个向量的内积越2W来越大，不是因为其模值快速变化所致。因此可以看出最终得到的Wt是收敛的（对于线性可分数据集）而且可以算出t的取值：WfTWti=WfT(Wtyn(t)Xn(t)将t+1变成T有WfTWr_WfTWrminynWfTXnn_WfTWT2minynWfTXnminynWfTXnnn-WfTW0TminynWfTXnn-TminynWfTXnn而且：|Wt|2引WtJ+max|xn|2M|Wo+Tmax|xn|22三TmaxxnnqWfTWrTmnnynWTfXn一帆帆|WfITmaxllXnlP定义;R2=maxXnwfTP=minynXn,则nWfR2F这是线性可分

7、数据集的PLA终止日的T的次数表达式。PLA算法对于线性可分的数据源是可以最后能得到目标函数的。但是对于线性不可分的数据集，它不会自动的停止。对于非线性不可分的数据集，如果对其分类，它将是一个NP-Hard问题。这里的Pocket算法，则是一种近似算法，他是用贪心算法，每次将PLA修正的wt与pocket记录的pwt比较，对于所有数据集犯错最少的那个作为新的pwt,这样PLA一直进行，得到修正的值wt与pwt比较，如果wt的犯错少，则将pwt更新为wt。如果进行的Pocket算法运行时间足够长，因此我们就可以找到一个算错尽可能少的pwt。并以此来进行对于测试数据集的分类。Pocket算法如果对

8、于线性可分数据集，它会自动停止，并且得到一个wt,线性可分数据集，然后用于测试。本文主要是采用pocket算法0:funpocket2.minitializepocketweightspwtfort=0,1,2,.finda(random)mistakeofwtcalled(xn(t),yn(t)while!flagd<-(Maxnum-1)*rand()+1;Xdrepresentativethedrowdatasxd1=1,xd2.n=Xd1.n-1;y=Xdn,ifsign(Wt'*xd)=yflag<-true;trytocorrectthemistakebyWt1

9、<-Wtyn(t)%(t)ifWt+1makesfewermistakesthanreplacepwtwithWt+1iffunWtError(pwt,dataset)>funWtError(Wt+1,dataset)pwt=Wt+1;untilenoughiterationst=Tmaxstop.returnpwt(asWpocket)%对应于wn的训练集的错误概率计算%funWtError.mfunWtError(wt1,dataset)datasetmatrixnrows,mcolsxn1=1;whilecount<=nxn2.m=datasetcount1.m-1;y

10、n=datasetcountm;ifsign(wn1'*xn)=ynerrFlag<-=errFlag+1;count<-=count+1;reutrnerrFlag/n;关于pocket算法的几点说明：(1)对应于上述算法，在funpocket2.m中initializepocketweightspwtfort=0,1,2,./%finda(random)mistakeofwtcalled(xn(t),yn(t)查找一个随机的带有错误数据的Wt,这样随机找是很慢的可以改进一下，Wt,对应于这个法向量，先判断出相应有错误的数据集，然后再再从这里面进行随机，这样的查找更快些。

11、对应于程序中的实现是采用了这种方式。而不是每次都随机选一行的数据，判断是不是有错，有错在更新，如果一直随机都是没错的那么就相当的耗费时间。(2)pocket算对于线性不可分数据集是不会终止的，也就是说，他是一个NP问题。如果数据集大体上是线性可分数据集，只有一部分点不可分，我们只需要运行足够长的时间，或者pwt进行一定数量的替换，用这种T次更新取代完全更新到正确的t次数的近似和每次遇到好的Wt+1都才用贪心的算法替代pwt,这样也能得到一个比较好的分线结果。复杂度分析对于近似算法解NP问题，这里的时间复杂度:对于t,其时间复杂度为T(ti),finda(random)mistakeofwtca

12、lled(xn(t),yn(t)时间复杂度为T(Wti)对应于wn的训练集的错误概率计算Ter(Wti)Tmax总的时间复杂度：T(n)=£T(ti),i30T(ti)=T(Wti)(1)+2Ter(Wti)T(Wti)=(n+1)十2,I为一个向量与另一个向量的乘积所用时间。Ter(ti)=(n1)3nT(n)=(Tmax+1)(n+1)Ti+2+e(1)+(n+1)Ti+3n,T又是n的函数(一个多项式),Tmax-A00,T(n)-A上限为g的多项式函数。此时如果采用给出的伪代码中的随机选一个来判断数据对于Wt是否有误，这样就像是非确定算法，采用猜测的形式将所有的可能性随机的选

13、一个，结果是YES/NO,NO时继续随机选取，猜算可以在多项式时间内完成；验算其实就计算的有限时间了0(1)0Tmax有限时，就是采用近似的算法，虽然并不一定能够得到一个全局的满足的Wt,但是对于绝大多数的点分类还是可以的，这就是我们想要的。因此，近似的贪心算法思想的pocket算法其时间复杂度是多项式的函数，可以在时间多项式内完成。代码编程(matlab实现)%/%FunRandArray.mfunctionarr=FunRandArray(Maxnum,repeatFlag)%Arraymaxnum,ifnotinput,therepeatflag=1%repeatFlag=0%gener

14、atethethenaviecyclydataset%repeatFlaf=1%,generatetherand,arrmayhavethesamedata%repeatFlaf=2%generatethetheranddatasetvisit,rand('state,sum(100.*clock)*rand(1);arr=(Maxnum-1).*rand(1,Maxnum)+1;arr1=ceil(arr(:,:);flag=0;arr=arr1;%naturesequenceifrepeatFlag=0fori=1:Maxnumarr(i)=i;endelseifrepeatFla

15、g=1elseifrepeatFlag=2%tochangeintothedifferentdataAllData=zeros(1,Maxnum);fori=1:MaxnumALLData(i)=i;end%/%clearthesamedatainthearrfori=1:Maxnumflag=0;forj=1:Maxnumifarr(i)=ALLData(j)flag=1;ALLData(j)=-1;break;endendifflag=0arr(i)=0;endend%/%addthenoexistdatabutin1-400tothearrfori=1:Maxnumifarr(i)=0f

16、orj=1:MaxnumifALLData(j)=-1arr(i)=ALLData(j);ALLData(j)=-1;break;endendendendendendend%/%funWtError.mfunctionerrDataSetLine,errPossablitiy=funWtError(Wn1,DataSet)nm=size(DataSet);errFlag1=0;count=1;xn=ones(1,m);errDataSetLineTemp=zeros(1,n);whilecount<=nxn(1,2:m)=DataSet(count,1:m-1);yn1=xn*Wn1&#

17、39;ifyn1=0%=not=yn1=-1;endifsign(yn1)=DataSet(count,m)%sign()functionerrFlag1=errFlag1+1;errDataSetLineTemp(1,errFlag1)=count;endcount=count+1;enderrDataSetLine=zeros(1,errFlag1);errDataSetLine(1,:)=errDataSetLineTemp(1,1:errFlag1);errPossablitiy=errFlag1/n;%/%funWwtBestfunctionpockWn,flag,errPossab

18、litiy=funWwtBest(Wn1,Wn2,DataSet)nm=size(DataSet);errFlag1=0;errFlag2=0;flag=0;%0Wn1,1Wn2count=1;xn=ones(1,m);whilecount<=nxn(1,2:m)=DataSet(count,1:m-1);yn1=xn*Wn1'yn2=xn*Wn2'ifyn1=0%=not=yn1=-1;endifyn2=0yn2=-1;end%thisiserrorbecausethesignfunctionnotuse.%ifyn1=DataSet(count,m)ifsign(yn

19、1)=DataSet(count,m)errFlag1=errFlag1+1;end%ifyn2=DataSet(count,m)ifsign(yn2)=DataSet(count,m)errFlag2=errFlag2+1;endcount=count+1;enderrPossablitiy=errFlag1/n;pockWn=Wn1;iferrFlag1>errFlag2pockWn=Wn2;flag=1;errPossablitiy=errFlag2/n;end%/%funPocket.mfunctionpockWn,Wn,count,updateTTs,errposs=funPo

20、cket(FData,FunRandArray,funWwtBest,updateTimes,WnrndFlag,DatasetFlag,nn)%parametersannotaion%totheinputparametersrequestifnargin=0|nargin=1|nargin=2error('parametersnumberlacks');endifnargin=3updateTimes=200;WnrndFlag=0;DatasetFlag=0;n=1;endifnargin>7error('inputparameterstoolarger

21、9;);end%initialdataset1=FData;nm=size(dataset1);Wn=zeros(1,m);Wn(1,1)=0;ifWnrndFlag=1rand('state',sum(100*clock)*rand(1);Wn(2,m)=rand(1,m-1);end%trainingsetvisitingsequence%ResultRand=zeros(1,n);%ResultRand=FunRandArray(n,DatasetFlag);xn=ones(1,m);count=0;%countnumbersnoequalCount=0;%pocketW

22、npockWn=zeros(1,m);updateTTs=0;errposs=0;%attheendthepockWn'serrorpossiablityfilename1=strcat('aa_',num2str(updateTimes*rand(1);filename1=strcat(filename1,'.txt')ffile1=fopen(filename1,'w');whileupdateTTs<updateTimes%fromtheerrorDataSet(someWn)randselectaXi%errDataSetL

23、ineisarr1.errFlag,%arr1=thefirstnumberofXinotsatisfyingyn=xn*Wn'%thenumbercorresponingtheDataSet'slinelabelerrDataSetLine,errPossTemp=funWtError(Wn,dataset1);nerr,merr=size(errDataSetLine);rand('state',sum(100*clock)*rand(1);num=ceil(merr-1)*rand(1)+1);xn(2:m)=dataset1(errDataSetLine

24、(1,num),1:m-1);ytemp=xn*Wn'ifytemp=0ytemp=-1;endsigntemp=sign(ytemp);%signtemp,dataset1(ResultRand(num),m)%num,xn,xn*Wn',signtemp,dataset1(num,m)%ifsigntemp=dataset1(ResultRand(num),m)%numifsigntemp=dataset1(errDataSetLine(1,num),m)%Wn(1,1:m)=Wn(1,1:m)+nn.*xn(1,1:m)*dataset1(ResultRand(num),

25、m);Wn(1,1:m)=Wn(1,1:m)+nn*dataset1(errDataSetLine(1,num),m).*xn(1,1:m);%a='before',Wn,pockWntempWn,flag,errposs=funWwtBest(Wn,pockWn,dataset1);%a='after',Wn,tempWnifflag=0updateTTs=updateTTs+1;pockWn=tempWn;fprintf(ffile1,'%stt','updateTTs');fprintf(ffile1,'%dtttr

26、n',updateTTs);fprintf(ffile1,'%stt','pocketWn');fprintf(ffile1,'%ftttrn',pockWn);updateTTs%else%Wn=pockWn;end%pockWn%count=1;endendfclose(ffile1);%pockWn%/%pocketTrainTest.mfunctionerrAverage=pocketTrainTest(LoopNum,FDataTrain,FDTest,FunRandArray,funWwtBest,funWtError,upd

27、ateTimes,WnrndFlag,DatasetFlag,nn)FData=load(FDataTrain);%nm=size(FData);FDataTest=load(FDTest);avgerr=0;errPossArr=zeros(1,LoopNum);%pockWn=zeros(LoopNum,m);pockWnTemp=zeros(1,m);Wn=zeros(1,m);fori=1:1:LoopNumpockWnTemp,Wn,count,updatenum,errposs=funPocket(FData,FunRandArray,funWwtBest,updateTimes,

28、WnrndFlag,DatasetFlag,nn);errDataSetLine,errPossTemp=funWtError(pockWnTemp,FDataTest);%errPossTempavgerr=(avgerr*(i-1)+errPossTemp)/i%errPossTemperrPossArr(1,i)=errPossTemp;enderrAverage=mean(errPossArr(1,:);%/%pocketTrainTest.merrAverage=pocketTrainTest(LoopNum,FDataTrain,FDTest,FunRandArray,funWwt

29、Best,funWtError,updateTimes,WnrndFlag,DatasetFlag,nn)FData=load(FDataTrain);%nm=size(FData);FDataTest=load(FDTest);avgerr=0;errPossArr=zeros(1,LoopNum);pockWnTemp=zeros(1,m);Wn=zeros(1,m);filename=strcat('aa',num2str(updateTimes);filename=strcat(filename,'.txt')ffile=fopen(filename,&

30、#39;w');%filenamefprintf(ffile,'%stt','i');fprintf(ffile,'%stt','pockWnTemp');fprintf(ffile,'%stttrn','avgerr');fori=1:1:LoopNumipockWnTemp,Wn,count,updatenum,errposs=funPocket(FData,FunRandArray,funWwtBest,updateTimes,WnrndFlag,DatasetFlag,nn);err

31、DataSetLine,errPossTemp=funWtError(pockWnTemp,FDataTest);%errPossTempavgerr=(avgerr*(i-1)+errPossTemp)/ifprintf(ffile,'%dt',i);fprintf(ffile,'%ft',pockWnTemp);fprintf(ffile,'%frn',avgerr);%errPossTemperrPossArr(1,i)=errPossTemp;enderrAverage=mean(errPossArr(1,:);fprintf(ffile

32、,'%st','errAverage:');fprintf(ffile,'%ft',errAverage);fclose(ffile);%/%pockettest.mfunctionpockettest()tic;errAverage=pocketTrainTest(2,'Q18Train.m','Q18TestData.m',FunRandArray,funWwtBest,funWtError,50,0,0,1)t1=toc;t1上机调试改正了其中的一些错误。其中最明显的一个错误是符号函数的应用，有个地方忘记应用

33、，导致所有的Wt对应于数据的错误概率都是1,也就是即使最好的分线器，错误概率也是1.通过分析可出错误的地方是判断错误的函数里面忘记加上符号函数。实验分析errAverage=pocketTrainTest(2,'Q18Train.m','Q18TestData.m',FunRandArray,funWwtBest,funWtError,50,0,0,1)更新50次得出的Wt然后验证Testdata数据集，并且得出错误概率，这样运行2个50次，所用时间T=34214s,约为9小日30分，如果运行100次更新，这样运行1次100更新所用时间也差不多这么大。下面是2个

34、50次更新的所得数据：结果如下:CoBAandVindoYpocWn-2.0000-2.351B-3.5190-1,90742,3018avgert=0.1180i=2filenamel-aa_47*2092*txt<'sNew之前有个运行100次更新的数据为:Flfl更新50次和更新100次也有可能得到相同的效果，这都是随机的选取错误概率的原因,因此我们还可以更新100次，并且这样跑上2000次，得出一个平均的错误概率，最坏因此这里我们用平均的情形就是一直在跑，最好的情形就是对于线性可分数据集自动结束。情况来衡量即可。结论实践证明：用近似算法模拟pocket,对于线性不可分数据

35、集可以得到一个比较好的pwt-分类器。如果设置Tmax=50或者100,都可以，但是数值越大运行时间越长。可以很好的解决这个NP问题。附录：数据部分仅是部分数据Trainingdatasets(Q18Train.m)0.945440.428420.798330.16244-10.853650.0841680.56820.49221-10.170950.821270.984440.51486-10.514120.921240.423230.097934-10.281470.714340.0753090.911610.462950.645120.963240.31516-10.977890.801

36、550.902350.74203-10.418250.694190.462460.31523-10.752030.202640.87650.47593-10.317670.168140.971480.7562510.606390.62560.690920.23644-10.747360.588630.852530.49688-10.403880.924360.564770.44963-10.901870.321170.744730.24326-10.730950.25880.434530.9705910.503150.418840.0260940.916231Q18TestData.m0.629260.327830.0104170.7310210.323680.614390.420970.025626-10.159680.833460.975150.32762-10.0235260.302920.0149610.9228810.458040.74520.834060.5493210.20760.84260.417970.0027624-10.894810.303940.457730.007992-10