機(jī)器學(xué)習(xí)PLA算法

1、PLAandPOCKET問題描述算法思想設(shè)計描述-偽代碼-復(fù)雜度分析編程-上機(jī)調(diào)試實驗分析-結(jié)論，本文是采用這樣的順序描述算法的。本文所寫算法對應(yīng)于一個NP-Hard問題，主要采用近似求解算法和貪心算法的思想。這對應(yīng)于機(jī)器學(xué)習(xí)中BinaryClassification,PLA,PocketAlgorithm問題描述：銀行發(fā)信用卡問題?，F(xiàn)有一群人，數(shù)量為N,(N很大)，假設(shè)他們在一個銀行中的登記記錄數(shù)據(jù)我們已經(jīng)得到。對于每個人記錄的數(shù)據(jù)有Xi=(x1,x2，,xn)(對應(yīng)第i個人的信息，相應(yīng)的x1,x2，,xn我們可以認(rèn)為是這個人的一些個人數(shù)據(jù)的量化值，比如年齡、學(xué)歷、收入、工作年限等等，他們會

2、對應(yīng)于一組數(shù)值如0.945440.428420.798330.16244-1對應(yīng)于Xi，X2,%,x4,y)。如果y是-1,則對應(yīng)于銀行沒有給他發(fā)信用卡。如果是y=1,則是發(fā)給了它信用卡?，F(xiàn)在由這樣的一推數(shù)據(jù)如何得到一個函數(shù)，有這些訓(xùn)練集得到這個目標(biāo)函數(shù)。并用這個目標(biāo)函數(shù)作用于對于一群待發(fā)信用卡的人作出判斷，一邊給銀行提供發(fā)卡的依據(jù)。具體數(shù)據(jù)見附錄Q18Train.m為訓(xùn)練數(shù)據(jù)集，Q18TestData.m為待判斷數(shù)據(jù)集，這里我們可以叫他測試數(shù)據(jù)集。對于銀行，他之前會設(shè)置一個發(fā)信用卡的門限值threshold.算法描述和偽代碼表述：之前我們都是用PLA(perceptionlearningal

3、gorithm)：它是針對于線性可分的訓(xùn)練集的。也就是這樣的所有的數(shù)據(jù)，比如說是二維數(shù)據(jù)點，可以用一條直線將他們分成兩派，一片是可發(fā)卡的數(shù)據(jù)，直線另一側(cè)則是不可發(fā)卡數(shù)據(jù)。將用戶數(shù)據(jù)加權(quán)求和與門限值相比較，作差為正則發(fā)卡，為負(fù)則不發(fā)卡。這里假設(shè)一個Hypothesisdatasets,每計算一次都是一個H,如果有錯則修正，一直到所有的數(shù)據(jù)都沒有錯誤，這樣的H就是我們的未知的目標(biāo)函數(shù)fodh(x)=signwx-threshold),對于h,.i11,x>0sign(x)=0,x<0這里h可以化簡一下，-threshold可以當(dāng)做w0,因此對應(yīng)于x0=1dh(x)=sign('

4、四內(nèi)),iRh(x)=sign(WTX)工-1IPLA的算法描述是：Wt是類似于那條直線的法向量，(Xn(t),yn(t)是一個人的數(shù)據(jù)記錄fort=0,1,2,3.findamistakeofwtcalled(xn(t),yn(t)sign(WXn(t)»(t)trytocorrectthemistakeby皿1-Wt1(t)Xn(t)對于線性可分?jǐn)?shù)據(jù)集PLA算法是收斂的證明：Yn(t)WTfXn(t)之mjnYnWTfXn>0,t是代表第t次得到的結(jié)果或者第t次所用的數(shù)值。WfTWt1=WfT(Wtyn(t)Xn(t)(1)之WfTWt+minynWfTXnWt這里是單增的

5、，如果從向量角度看，兩個向n-WfTWt量內(nèi)積越大，如果排除其模值得快速增大，可以看做是其角度在不斷的調(diào)整，逐漸變得同向。(2)就是證明其模值變化有限。(2)|WtJ=|Wt+yn(t)Xn(t)二|Wt+2yn(t)WTtXn(t)+|yn(t)Xn(t)4Wt+0+|yn(t)Xn(t),(有錯時，)Wt作為法線的直線去判斷訓(xùn)練數(shù)據(jù)集是有錯的，Usign(WTtXn)"y")二y(t)WTtXn(t)<022Wti=Wtyn(t)Xn(t)|22£Wt|-maxynXn22Wt|-maxXn這里可以認(rèn)為每次增加的步長有限，同時也說明令M=maxn,2WW

6、tXn2M兩個向量的內(nèi)積越2W來越大，不是因為其模值快速變化所致。因此可以看出最終得到的Wt是收斂的（對于線性可分?jǐn)?shù)據(jù)集）而且可以算出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、數(shù)據(jù)集的PLA終止日的T的次數(shù)表達(dá)式。PLA算法對于線性可分的數(shù)據(jù)源是可以最后能得到目標(biāo)函數(shù)的。但是對于線性不可分的數(shù)據(jù)集，它不會自動的停止。對于非線性不可分的數(shù)據(jù)集，如果對其分類，它將是一個NP-Hard問題。這里的Pocket算法，則是一種近似算法，他是用貪心算法，每次將PLA修正的wt與pocket記錄的pwt比較，對于所有數(shù)據(jù)集犯錯最少的那個作為新的pwt,這樣PLA一直進(jìn)行，得到修正的值wt與pwt比較，如果wt的犯錯少，則將pwt更新為wt。如果進(jìn)行的Pocket算法運行時間足夠長，因此我們就可以找到一個算錯盡可能少的pwt。并以此來進(jìn)行對于測試數(shù)據(jù)集的分類。Pocket算法如果對

8、于線性可分?jǐn)?shù)據(jù)集，它會自動停止，并且得到一個wt,線性可分?jǐn)?shù)據(jù)集，然后用于測試。本文主要是采用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)%對應(yīng)于wn的訓(xùn)練集的錯誤概率計算%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;關(guān)于pocket算法的幾點說明：(1)對應(yīng)于上述算法，在funpocket2.m中initializepocketweightspwtfort=0,1,2,./%finda(random)mistakeofwtcalled(xn(t),yn(t)查找一個隨機(jī)的帶有錯誤數(shù)據(jù)的Wt,這樣隨機(jī)找是很慢的可以改進(jìn)一下，Wt,對應(yīng)于這個法向量，先判斷出相應(yīng)有錯誤的數(shù)據(jù)集，然后再再從這里面進(jìn)行隨機(jī)，這樣的查找更快些。

11、對應(yīng)于程序中的實現(xiàn)是采用了這種方式。而不是每次都隨機(jī)選一行的數(shù)據(jù)，判斷是不是有錯，有錯在更新，如果一直隨機(jī)都是沒錯的那么就相當(dāng)?shù)暮馁M時間。(2)pocket算對于線性不可分?jǐn)?shù)據(jù)集是不會終止的，也就是說，他是一個NP問題。如果數(shù)據(jù)集大體上是線性可分?jǐn)?shù)據(jù)集，只有一部分點不可分，我們只需要運行足夠長的時間，或者pwt進(jìn)行一定數(shù)量的替換，用這種T次更新取代完全更新到正確的t次數(shù)的近似和每次遇到好的Wt+1都才用貪心的算法替代pwt,這樣也能得到一個比較好的分線結(jié)果。復(fù)雜度分析對于近似算法解NP問題，這里的時間復(fù)雜度:對于t,其時間復(fù)雜度為T(ti),finda(random)mistakeofwtca

12、lled(xn(t),yn(t)時間復(fù)雜度為T(Wti)對應(yīng)于wn的訓(xùn)練集的錯誤概率計算Ter(Wti)Tmax總的時間復(fù)雜度：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的函數(shù)(一個多項式),Tmax-A00,T(n)-A上限為g的多項式函數(shù)。此時如果采用給出的偽代碼中的隨機(jī)選一個來判斷數(shù)據(jù)對于Wt是否有誤，這樣就像是非確定算法，采用猜測的形式將所有的可能性隨機(jī)的選

13、一個，結(jié)果是YES/NO,NO時繼續(xù)隨機(jī)選取，猜算可以在多項式時間內(nèi)完成；驗算其實就計算的有限時間了0(1)0Tmax有限時，就是采用近似的算法，雖然并不一定能夠得到一個全局的滿足的Wt,但是對于絕大多數(shù)的點分類還是可以的，這就是我們想要的。因此，近似的貪心算法思想的pocket算法其時間復(fù)雜度是多項式的函數(shù)，可以在時間多項式內(nèi)完成。代碼編程(matlab實現(xiàn))%/%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上機(jī)調(diào)試改正了其中的一些錯誤。其中最明顯的一個錯誤是符號函數(shù)的應(yīng)用，有個地方忘記應(yīng)用

33、，導(dǎo)致所有的Wt對應(yīng)于數(shù)據(jù)的錯誤概率都是1,也就是即使最好的分線器，錯誤概率也是1.通過分析可出錯誤的地方是判斷錯誤的函數(shù)里面忘記加上符號函數(shù)。實驗分析errAverage=pocketTrainTest(2,'Q18Train.m','Q18TestData.m',FunRandArray,funWwtBest,funWtError,50,0,0,1)更新50次得出的Wt然后驗證Testdata數(shù)據(jù)集，并且得出錯誤概率，這樣運行2個50次，所用時間T=34214s,約為9小日30分，如果運行100次更新，這樣運行1次100更新所用時間也差不多這么大。下面是2個

34、50次更新的所得數(shù)據(jù)：結(jié)果如下:CoBAandVindoYpocWn-2.0000-2.351B-3.5190-1,90742,3018avgert=0.1180i=2filenamel-aa_47*2092*txt<'sNew之前有個運行100次更新的數(shù)據(jù)為:Flfl更新50次和更新100次也有可能得到相同的效果，這都是隨機(jī)的選取錯誤概率的原因,因此我們還可以更新100次，并且這樣跑上2000次，得出一個平均的錯誤概率，最壞因此這里我們用平均的情形就是一直在跑，最好的情形就是對于線性可分?jǐn)?shù)據(jù)集自動結(jié)束。情況來衡量即可。結(jié)論實踐證明：用近似算法模擬pocket,對于線性不可分?jǐn)?shù)據(jù)

35、集可以得到一個比較好的pwt-分類器。如果設(shè)置Tmax=50或者100,都可以，但是數(shù)值越大運行時間越長。可以很好的解決這個NP問題。附錄：數(shù)據(jù)部分僅是部分?jǐn)?shù)據(jù)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