机器学习LA算法.docVIP

PLA and POCKET 问题描述--------算法思想设计描述------伪代码-----复杂度分析---------编程-----上机调试--------实验分析------结论，本文是采用这样的顺序描述算法的。 本文所写算法对应于一个NP-Hard问题，主要采用近似求解算法和贪心算法的思想。 这对应于机器学习中Binary Classification，PLA ，Pocket Algorithm 问题描述： 银行发信用卡问题。现有一群人，数量为N，（N很大），假设他们在一个银行中的登记记录数据我们已经得到。对于每个人记录的数据有（对应第i个人的信息，相应的我们可以认为是这个人的一些个人数据的量化值，比如年龄、学历、收入、工作年限等等，他们会对应于一组数值如0.94544 0.42842 0.79833 0.16244 -1 对应于）。如果y是-1，则对应于银行没有给他发信用卡。如果是y=1，则是发给了它信用卡。现在由这样的一推数据如何得到一个函数，有这些训练集得到这个目标函数。并用这个目标函数作用于对于一群待发信用卡的人作出判断，一边给银行提供发卡的依据。 具体数据见附录Q18Train.m为训练数据集， Q18TestData.m为待判断数据集，这里我们可以叫他测试数据集。对于银行，他之前会设置一个发信用卡的门限值threshold. 算法描述和伪代码表述： 之前我们都是用PLA（perception learning algorithm）：它是针对于线性可分的训练集的。也就是这样的所有的数据，比如说是二维数据点，可以用一条直线将他们分成两派，一片是可发卡的数据，直线另一侧则是不可发卡数据。将用户数据加权求和与门限值相比较，作差为正则发卡，为负则不发卡。 这里假设一个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 对于线性可分数据集PLA算法是收敛的证明： ，t是代表第t次得到的结果或者第t次所用的数值。 （1）这里是单增的，如果从向量角度看，两个向量内积越大，如果排除其模值得快速增大，可以看做是其角度在不断的调整，逐渐变得同向。（2）就是证明其模值变化有限。 （2） 这里可以认为每次增加的步长有限，同时也说明两个向量的内积越来越大，不是因为其模值快速变化所致。因此可以看出最终得到的Wt是收敛的（对于线性可分数据集）。 而且可以算出t的取值： 而且： 则 这是线性可分数据集的PLA终止时的T的次数表达式。 PLA算法对于线性可分的数据源是可以最后能得到目标函数的。但是对于线性不可分的数据集，它不会自动的停止。对于非线性不可分的数据集，如果对其分类，它将是一个NP-Hard问题。这里的Pocket算法，则是一种近似算法，他是用贪心算法，每次将PLA修正的wt与pocket记录的pwt比较，对于所有数据集犯错最少的那个作为新的pwt，这样PLA一直进行，得到修正的值wt与pwt比较，如果wt的犯错少，则将pwt更新为wt。如果进行的Pocket算法运行时间足够长，因此我们就可以找到一个算错尽可能少的pwt。并以此来进行对于测试数据集的分类。 Pocket算法如果对于线性可分数据集，它会自动停止，并且得到一个wt，线性可分数据集，然后用于测试。 本文主要是采用pocket算法（）： //%funpocket2.m initialize pocket weights pwt for t=0,1,2,.... //%find a (random) mistake of wt called (xn(t),yn(t)) while !flag d-(Maxnum-1)*rand()+1; //%X[d] representative the d row datas x[d][1]=1,x[d][2..n]=X[d][1..n-1]; y=X[d][n], if sign(Wt*x[d])~=y flag-true; //%try to correct the mistake by //%if Wt+1 makes fewer mistakes than replace pwt with Wt+1 if funWtError(pwt,data