機器學習PLA算法.doc

《機器學習PLA算法.doc》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、PLAandPOCKET問題描述--------算法思想設(shè)計描述------偽代碼-----復雜度分析---------編程-----上機調(diào)試--------實驗分析------結(jié)論，本文是采用這樣的順序描述算法的。本文所寫算法對應(yīng)于一個NP-Hard問題，主要采用近似求解算法和貪心算法的思想。這對應(yīng)于機器學習中BinaryClassification，PLA，PocketAlgorithm問題描述：銀行發(fā)信用卡問題?，F(xiàn)有一群人，數(shù)量為N，（N很大），假設(shè)他們在一個銀行中的登記記錄數(shù)據(jù)我們已經(jīng)得到。對于

2、每個人記錄的數(shù)據(jù)有（對應(yīng)第i個人的信息，相應(yīng)的我們可以認為是這個人的一些個人數(shù)據(jù)的量化值，比如年齡、學歷、收入、工作年限等等，他們會對應(yīng)于一組數(shù)值如0.945440.428420.798330.16244-1對應(yīng)于）。如果y是-1，則對應(yīng)于銀行沒有給他發(fā)信用卡。如果是y=1，則是發(fā)給了它信用卡?，F(xiàn)在由這樣的一推數(shù)據(jù)如何得到一個函數(shù)，有這些訓練集得到這個目標函數(shù)。并用這個目標函數(shù)作用于對于一群待發(fā)信用卡的人作出判斷，一邊給銀行提供發(fā)卡的依據(jù)。具體數(shù)據(jù)見附錄Q18Train.m為訓練數(shù)據(jù)集，Q18TestD

3、ata.m為待判斷數(shù)據(jù)集，這里我們可以叫他測試數(shù)據(jù)集。對于銀行，他之前會設(shè)置一個發(fā)信用卡的門限值threshold.算法描述和偽代碼表述：之前我們都是用PLA（perceptionlearningalgorithm）：它是針對于線性可分的訓練集的。也就是這樣的所有的數(shù)據(jù)，比如說是二維數(shù)據(jù)點，可以用一條直線將他們分成兩派，一片是可發(fā)卡的數(shù)據(jù)，直線另一側(cè)則是不可發(fā)卡數(shù)據(jù)。將用戶數(shù)據(jù)加權(quán)求和與門限值相比較，作差為正則發(fā)卡，為負則不發(fā)卡。這里假設(shè)一個Hypothesisdatasets，每計算一次都是一個H，如

4、果有錯則修正，一直到所有的數(shù)據(jù)都沒有錯誤，這樣的H就是我們的未知的目標函數(shù)f。對于h，這里h可以化簡一下，PLA的算法描述是：wt是類似于那條直線的法向量，（）是一個人的數(shù)據(jù)記錄fort=0,1,2,3....findamistakeofwtcalled()trytocorrectthemistakeby對于線性可分數(shù)據(jù)集PLA算法是收斂的證明：，t是代表第t次得到的結(jié)果或者第t次所用的數(shù)值。（1）這里是單增的，如果從向量角度看，兩個向量內(nèi)積越大，如果排除其模值得快速增大，可以看做是其角度在不斷的調(diào)整，

5、逐漸變得同向。（2）就是證明其模值變化有限。（2）這里可以認為每次增加的步長有限，同時也說明兩個向量的內(nèi)積越來越大，不是因為其模值快速變化所致。因此可以看出最終得到的Wt是收斂的（對于線性可分數(shù)據(jù)集）。而且可以算出t的取值：而且：則這是線性可分數(shù)據(jù)集的PLA終止時的T的次數(shù)表達式。PLA算法對于線性可分的數(shù)據(jù)源是可以最后能得到目標函數(shù)的。但是對于線性不可分的數(shù)據(jù)集，它不會自動的停止。對于非線性不可分的數(shù)據(jù)集，如果對其分類，它將是一個NP-Hard問題。這里的Pocket算法，則是一種近似算法，他是用貪心

6、算法，每次將PLA修正的wt與pocket記錄的pwt比較，對于所有數(shù)據(jù)集犯錯最少的那個作為新的pwt，這樣PLA一直進行，得到修正的值wt與pwt比較，如果wt的犯錯少，則將pwt更新為wt。如果進行的Pocket算法運行時間足夠長，因此我們就可以找到一個算錯盡可能少的pwt。并以此來進行對于測試數(shù)據(jù)集的分類。Pocket算法如果對于線性可分數(shù)據(jù)集，它會自動停止，并且得到一個wt，線性可分數(shù)據(jù)集，然后用于測試。本文主要是采用pocket算法（）：//%funpocket2.minitializepoc

7、ketweightspwtfort=0,1,2,....//%finda(random)mistakeofwtcalled(xn(t),yn(t))while!flagd<-(Maxnum-1)*rand()+1;//%X[d]representativethedrowdatasx[d][1]=1,x[d][2..n]=X[d][1..n-1];y=X[d][n],ifsign(Wt'*x[d])~=yflag<-true;//%trytocorrectthemistakeby//%ifWt+1make

8、sfewermistakesthanreplacepwtwithWt+1iffunWtError(pwt,dataset)>funWtError(Wt+1,dataset)pwt=Wt+1;untilenoughiterationst=stop.returnpwt(asWpocket)%對應(yīng)于wn的訓練集的錯誤概率計算%funWtError.mfunWtError(wt1,dataset)datasetmatrixnrows,mcolsxn