统计学习方法随笔及R语言实现（一）
写在前面的
为什么要开始这一系列的推文呢？我逐渐意识到，目前国内搞生物信息学的群体主要分为两个流派。一个流派是研究生物信息学算法、开发生物信息学软件。另外一个流派是利用生物信息学技术解决某一实际的生物学问题。如果站在几年前看这两个流派，那个时候这两个流派应该还算有区别的，尤其是用生物信息学技术去解决实际生物问题的流派，可能这个流派中会有较多的人只关心软件怎么用，网上发的脚本怎么跑，能得到一个什么样的结果？他们不去过问这里面为什么是这么用，为什么是这么运行，为什么可以得到这样的结果。而我的研一阶段，刚开始也是主要用生物信息软件去解决一些问题。只是我平时乐于写脚本，乐于思考为什么要这么做。所以我在研一后期开始着手自己开发一些程序。现在程序也造出来了，但是还不能发表。因为我还不确定我的数学模型是否合理，给出的结果是否在具有统计学或者数学意义下具有生物学意义。于是乎，研二的我决定做出一些突破。向算法迈进。
感知机模型及其R语言实现
这个系列从感知机开始一方面是因为自己以前买了李航大神的统计学习方法，平时也在看。另外一方面是我线性代数的知识还在（虽然平时用的少，有部分也有忘却，不过会查书捡回来，这里也非常感谢连明哥平时的推文、周末的直播。因为他所作的这些潜移默化地帮助了我对知识的理解、感悟！）。再者，感知机模型很简单，写出来也适合新手看。那么废话不多说，我们直接开干。
什么是感知机模型
感知机模型是一类二分类的线性分类模型。我们通过输入实例的特征向量，模型会根据输入输出对实例的判断。这种判断结果非黑即白，要么是1，要么是0。用更广义的角度说则是，感知机模型通过训练数据将实例空间进行线性划分，划分为正负两类的分离超平面。这里的重点是：1.你的训练数据一定是能够线性划分的，即所有正实例点集所构成的凸壳与负实例点集所构成的凸壳互不相交。2.你要分类的实例也是具有同质性的实例。3.感知机最后输出的结果要么是1，要么是0。二者条件不满足，就不能用感知机模型。
感知机模型的算法
读完前面你可能似懂非懂，懂的是你知道这玩意儿是干啥的，不懂的是你不知道它咋干的。我们继续探究它咋干的，现在我们先定义一个训练数据集。假设有如下训练点集X及其对应标记Y，通过感知机模型找到两个参数w与b使得满足如下：
据前面所述原理，感知机将会通过训练数据给出一个线性划分的正负分离超平面。那么感知机则会在训练数据中一个一个随机取出数据尝试构建这样的线性划分空间。比如，先定义w0=0,b0=0后，当感知机拿到点(x11,x12)及对应标记y1时，感知机模型得到了一个w1,b1。可以区分该点，但是用w1,b1去分类(x21,x22)时，发现分类结果与y2乘积小于0。那么我们把分类结果不正确的点（x21,x22）称为误分类点。感知机又会在这个时候根据误分类点，来调整w1,b1的值。直到产生w2,b2使得对(x21,x22)分类正确。所以这个过程我们可以理解为感知机学习算法是根据误分类驱动的。所以我们总结一下感知机学习算法的原始形式：
原始形式算法：输入训练数据集；输出w,b;
1.选取初值w0,b0;
2.随机选择训练数据(xi,yi)
3.如果yi(wxi+b)<=0 w=w+yixi b=b+yi 返回2，直到没有误分类点。这里，解释一下为什么令w=w+yixi；b=b+yi可以纠正误分类点：由于出现了yi(wxi+b)<=0，才判断产生了误分类点。以我们前文为例子，根据矩阵内积有：
也就是说这样做会为原始结果增加一个正部，经过不断调整，正部增量越大，误分类点最后会成为正确分类的点。
下面利用R语言来实现感知机模型的原始形式。
#训练数据集，其中trainData对应X，aim对应Y。
trainData<-matrix(c(3,2,3,3,1,4,1,1,1.2,5,1,1,0.7,0.3,0.7,1.5),ncol = 2,byrow = T)
aim<-c(1,1,1,-1,1,-1,-1,-1)
#COU是记录正确分类的点的个数，当COU等于length(aim)时，代表感知机模型构建成功
COU<-0;
atleast<-length(aim)
#给定w,b初值
w<-matrix(c(0,0),ncol = 1,byrow = T);
b<-0
while (lost<atleast) {
#循环中当w,b更新后重新计算分类点要更新COU归零计算
COU<-0
for (i in 1:nrow(trainData)) {
#%*%是R语言中计算向量内积符号
if(aim[i]*(trainData[i,] %*% w + b)<=0){
y <- matrix(c(aim[i],aim[i]),ncol = 1,byrow = T)
w <- w + 1*trainData[i,]*y
b <- b + 1*aim[i]
}
else{
COU <- COU + 1
}
}
}
最后输出w= 2.6,1.0, b= -4, 对应分类模型2.6x1+x2-4=0
感知机模型的对偶形式
另外，感知机模型还有对偶形式，这个形式本质上与原始形式无区别。对偶形式主要是利用xi与yi的线性组合来表示w和b。通过观察原始形式，我们不难看出，当出现误分类点时，w=w+yixi，也就是说每个点被误分类时，都会加一次自身与对应标记的积。而训练数据中有的点是很容易被分类的，有的点是很难被分类的。比如，距离正负分离超平面越近的点越难被分类，那么它们被调整的次数就很多。也就是说它们加上自身与对应标记的积的次数就越多。换句话说，我们只需要关注每个点与对应标记的积的累加次数就可以控制w的值。这样w可以表示为
#给定数据集
trainData<-matrix(c(3,2,3,3,1,4,1,1,1.2,5,1,1,0.7,0.3,0.7,1.5),ncol = 2,byrow = T)
aim<-c(1,1,1,-1,1,-1,-1,-1)
COU<-0
#定义每个样本点的alpha初值
a<-rep(0,length(aim))
b<-0
#用yi,xi的线性组合定义w
for (i in 1:length(aim)) {
w<-a[i]*aim[i]*trainData[i,]
}
while (COU<length(aim)) {
COU<-0
w<-c(0,0)
for (i in 1:length(aim)) {
w<-w+a[i]*aim[i]*trainData[i,]
}
for (i in 1:nrow(trainData)) {
#如果出现误分类点只需让误分类点对应的alpha值加1
if(aim[i]*(w %*% trainData[i,] +b)<=0){
a[i]<-a[i]+1
b<-b+aim[i]
}
else{
COU<-COU+1
}
}
}
最后输出w=1.4,2.4 ,b=-6。最后产生分类模型1.4x1+2.4x2-6=0，为什么这个分类模型和上面不一样呢？其实这两个分类模型都是正确的，只是因为受迭代顺序的影响。如果训练数据越多，可划分的正负分离超平面区间越小，那么不同的方法最后得到结果会越接近。
备注
其实感知机模型的对偶形式可以通过求解训练数据构成Gram矩阵减少计算次数。最后对于感知机模型的收敛性证明，我现在暂时还没有能力去证明。李航大神书中通过证明Novikoff定理证明了感知机模型的收敛性。最后表明，误分类次数是有上界的，当训练数据线性可分时，经过有限次数搜索可以找到将训练数据完成正确分开的分离超平面。
参考
《统计学习方法》 李航
作者信息
熊东彦，中国科学院武汉病毒研究所在读研究生。擅长方向：转录组分析、宏基因组分析、R语言编程、Perl语言编程。近期更新内容:生物信息分析小技巧。
往期精彩推文
