文档介绍：PLAandPOCKET
问题描述算法思想设计描述伪代码复杂度分析编程上机调试
实验分析结论，本文是采用这样的顺序描述算法的。
本文所写算法对应于一个NP-Hard问题，主要采用近似求解算法和贪心算法的思想。这对应于机器学习中BinaTminyWTX
nfn
n
WTW
1>—>IWflliWTii
定义;
R2=max
"n
n
WT
||X||2,p=minyfX,则
八n
n
这是线性可分数据集的PLA终止时的T的次数表达式。
PLA算法对于线性可分的数据源是可以最后能得到目标函数的。但是对于线性不可分的数据集，它不会自动的停止。对于非线性不可分的数据集，如果对其分类，它将是一个NP-Hard问题。这里的Pocket算法，则是一种近似算法，他是用贪心算法，每次将PLA修正的wt与pocket记录的pwt比较,对于所有数据集犯错最少的那个作为新的pwt,这样PLA一直进行，得到修正的值wt与pwt比较，如果wt的犯错少，则将pwt更新为wt。如果进行的Pocket算法运行时间足够长，因此我们就可以找到一个算错尽可能少的pwt。并以此来进行对于测试数据集的分类。
Pocket算法如果对于线性可分数据集，它会自动停止，并且得到一个wt，线性可分数据集，然后用于测试。
本文主要是采用pocket算法()：
//%
initializepocketweightspwt
fort=0,1,2,
//%finda(random)mistakeofwtcalled(xn(t),yn(t))while!flag
d<-(Maxnum-1)*rand()+1;
//%X[d]representativethedrowdatas
x[d][1]=1,x[d][2..n]=X[d][1..n-1];
y=X[d][n],
ifsign(Wt'*x[d])~=yflag<-true;
//%trytocorrectthemistakeby
W<---W+y(t)x(t)
t+1tnn
//%ifWt+1makesfewermistakesthanreplacepwtwithWt+1iffunWtError(pwt,dataset)>funWtError(Wt+1,dataset)
pwt=Wt+1;
untilenoughiterationst=Tstop.
max
returnpwt(asWpocket)
%对应于wn的训练集的错误概率计算
%(wt1,dataset)datasetmatrixnrows,mcolsxn[1]=1;
whilecount<=n
xn[2..m]=dataset[count][1..m-1];yn=dataset[count][m];
ifsign(wn1'*xn)~=ynerrFlag<-=errFlag+1;
count<-=count+1;
reutrnerrFlag/n;
关于pocket算法的几点说明：
(1)对应于上述算法，
initializepocketweightspwt
fort=0,1,2,
//%finda(random)mistakeofwtcalled(xn(t),yn(t))
查找一个随机的带有错误数据的Wt,这样随机找是很慢的可以改进一下，Wt,对应于这个法向量，先判断出相应有错误的数据集，然后再再从这里面进行随机，这样的查找更快些。对应于程序中的实现是采用了这种方式。而不是每次都随机选一行的数据，判断是不是有错，有错在更新，如果一直随机都是没错的那么就相当的耗费时间。
(2)pocket算对于线性不可分数据集是不会终止的，也就是说，他是一个NP问题。
如果数据集大体上是线性可分数据集，只有一部分点不可分，我们只需要运行足够长的时间，
或者pwt进行一定数量的替换，用这种T次更新取代完全更新到正确的t次数的近似和每次遇到好的Wt+1都才用贪心的算法替代pwt，这样也能得到一个比较好的分线结果。
复杂度分析
对于近似算法解NP问题，这里的时间复杂度：
对于t，其时间复杂度为T(t),
ii
finda(random)mistakeofwtcalled(xn(t),yn(t))时间复杂度为T(W)
ti
对应于wn的训练集的错误概率计算Ter(W)
ti
总的时间复杂度：T(n)二虹ax(t)，
i
i=0
T(t)二T(W)+9(l)+2Ter(W)
ititi
T(W)二(n+1)T+2，T为一个向量与另一个向量的乘积所用时间。
tiii
Ter(t