感知机(perception)与其算法实现（R）

2019-08-08 本文已影响0人 sarai_c7eb

1.感知机模型

感知机是二类分类的线性分类模型，其输入为实例的特征向量，输出为实例的类别，取值为1和-1二值。
感知机对应于输入空间中将实例划分为正负两类的分离超平面，属于判别模型，感知机学习旨在求出将训练数据进行线性划分的分离超平面；

2.感知机算法

输入：训练数据集 $T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$ ，其中 $x_i\in X = R^n$ , $y_i \in Y =\{-1,+1\}$ , $i=1,2,...N$ ;学习率 $\eta$ $(0<\eta\leq 1);$
输出： $w,b$ ;感知机模型 $f(x)=sign(w\cdot x+b)$ .

选取初值 $w_0,b_0$
在训练集中选取数据 $（x_i,j_i）$
如果 $y_i(w\cdot x_i+b)\leq 0$

$\begin{eqnarray} w&\leftarrow& w+\eta y_ix_i \\ b&\leftarrow& b+\eta y_i \end{eqnarray}$

转至（2），直至训练集中没有误分类点。

3.R语言实现

将数据放入到一个excel file。（本文中叫tmp2.csv）
数据内容与书上一致。^[1]

tmp2.csv文件内容
算法流程图

算法流程图
代码实现

#the data set
rc<-read.csv("tmp2.csv")
attach(rc)
data_len<-length(rc[,1])

x_len<-dim(rc)[2]-1
eta  <-1
w    <-rep(0,x_len)
b    <-0
x    <-rep(0,x_len)
judge=function(w,b,x,y) {
  loss <-y*(w%*%x+b)
  update<-loss<=0
  update
}

i <-1
while(i<=data_len){
    x[1]<-rc[i,1]
    x[2]<-rc[i,2]
    y   <-rc[i,3]
    
    update  <-judge(w,b,x,y)
    line    <-i
    update_r<-update

    if(update){
        while(update){
            w<-w+eta*y*x
            b<-b+eta*y
            update<-judge(w,b,x,y)
        }
        i<-1
    }
    else{
        i<-i+1
    }

    cat("i=",line,"update=",update_r,"x,y=",x,y,"w,b=",w,b,"\n")
}

运行结果：

C:\Windows\system32\cmd.exe /c (Rscript perception.r)
i= 1 update= TRUE x,y= 3 3 1 w,b= 3 3 1
i= 1 update= FALSE x,y= 3 3 1 w,b= 3 3 1
i= 2 update= FALSE x,y= 3 4 1 w,b= 3 3 1
i= 3 update= TRUE x,y= 1 1 -1 w,b= 0 0 -2
i= 1 update= TRUE x,y= 3 3 1 w,b= 3 3 -1
i= 1 update= FALSE x,y= 3 3 1 w,b= 3 3 -1
i= 2 update= FALSE x,y= 3 4 1 w,b= 3 3 -1
i= 3 update= TRUE x,y= 1 1 -1 w,b= 1 1 -3
i= 1 update= FALSE x,y= 3 3 1 w,b= 1 1 -3
i= 2 update= FALSE x,y= 3 4 1 w,b= 1 1 -3
i= 3 update= FALSE x,y= 1 1 -1 w,b= 1 1 -3
Hit any key to close this window...

4 感知机学习算法的对偶形式

输入：线性可分数据集 $T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$ ，其中 $x_i\in X = R^n$ , $y_i \in Y =\{-1,+1\}$ , $i=1,2,...N$ ;学习率 $\eta$ $(0<\eta\leq 1);$
输出： $a$ , $b$ ;感知机模型 $f(x)=sign(\sum_{j=1}^Na_jy_jx_j\cdot x+b)$ 。其中 $a=(a_1,a_2,...,a_N)^T$ 。

$a\leftarrow 0,b\leftarrow 0$ ;
在训练集中选取数据 $（x_i,j_i）$
如果 $y_i(\sum_{j=1}^Na_jy_jx_j\cdot x_i+b)\leq 0$

$\begin{eqnarray} a_i&\leftarrow& a_i +\eta \\ b&\leftarrow& b +\eta{y_i} \end{eqnarray}$

转至（2），直至训练集中没有误分类点。

对偶形式中训练实例仅以内积的形式出现（ $\sum_{j=1}^Nx_j\cdot x_i$ ），可预先将实例间的内积计算出来并以矩阵形式存储，这个矩阵就是所谓的Gram矩阵：
$G=[x_i\cdot x_j]_{N\times N}$

对偶形式的基本想法是：
$w,b$ 可以表示为 $x_i,y_i$ 的线性组合形式，通过求解器系数可以得到 $w,b$ ;
$w_0=0，b_0=0$ ，逐步修改 $w,b$ ，设修改了 $n$ 次
$\begin{eqnarray} w&\leftarrow& w+\eta y_ix_i \\ b&\leftarrow& b+\eta y_i \end{eqnarray}$
则 $w,b$ 关于 $x_i,y_i$ 的增量分别是 $a_iy_ix_i$ 和 $a_iy_i$ ,这里 $a_i=n_i\eta$ .
从而，最后的 $w,b$ 可以表示为：
$\begin{eqnarray} w&=& \sum_{i=1}^N a_i y_i x_i \\ b&=& \sum_{i=0}^N a_i y_i \end{eqnarray}$
$a_i\geq0,i=1,2,...N$ ，当 $\eta=1$ 时， $a_i$ 表示第 $i$ 个实例点（数据）由于误分而进行更新的次数，更新次数越多，表明离超平面越近，越难分类；

参考代码

#read the data set
rc<-read.csv("tmp2.csv")
attach(rc)
data_len<-length(rc[,1])

#initial
x_len<-dim(rc)[2]-1
eta  <-1
a    <-rep(0,data_len)
b    <-0
x    <-rep(0,x_len)
t    <-rep(0,x_len)

#Gram marix;
g0<-rep(0,data_len*data_len)
g<-matrix(g0,nrow=3,byrow=F)
for(i in 1:data_len){
    x[1]<-rc[i,1]
    x[2]<-rc[i,2]
    for(j in 1:data_len){
        t[1]<-rc[j,1]
        t[2]<-rc[j,2]
        g[j,i]<-x%*%t
    }
}

#update funtion
judge=function(a,y,i,g,b) {
    cox=a*y;
    sap=g[,i]
    loss <-y[i]*(cox%*%sap+b)
    update<-loss<=0
    update
}

#the main flow
i <-1
while(i<=data_len){
    x[1]<-rc[i,1]
    x[2]<-rc[i,2]
    
    update  <-judge(a,y,i,g,b)
    line    <-i
    update_r<-update

    if(update){
        while(update){
            a[i]<-a[i]+eta
            b <-b+eta*y[i]
            update<-judge(a,y,i,g,b)
        }
        i<-1
    }
    else{
        i<-i+1
    }
    cat("i=",line,"update=",update_r,"x,y=",x,y[i],"a,b=",a,b,"\n")
}

w<-c(a%*%(x1*y),a%*%(x2*y))
cat("the final w=",w,"the final b=",b,"\n")

运行结果

C:\Windows\system32\cmd.exe /c (Rscript perception_new.r)
i= 1 update= TRUE x,y= 3 3 1 a,b= 1 0 0 1
i= 1 update= FALSE x,y= 3 3 1 a,b= 1 0 0 1
i= 2 update= FALSE x,y= 3 4 -1 a,b= 1 0 0 1
i= 3 update= TRUE x,y= 1 1 1 a,b= 1 0 3 -2
i= 1 update= TRUE x,y= 3 3 1 a,b= 2 0 3 -1
i= 1 update= FALSE x,y= 3 3 1 a,b= 2 0 3 -1
i= 2 update= FALSE x,y= 3 4 -1 a,b= 2 0 3 -1
i= 3 update= TRUE x,y= 1 1 1 a,b= 2 0 5 -3
i= 1 update= FALSE x,y= 3 3 1 a,b= 2 0 5 -3
i= 2 update= FALSE x,y= 3 4 -1 a,b= 2 0 5 -3
i= 3 update= FALSE x,y= 1 1 NA a,b= 2 0 5 -3
the final w= 1 1 the final b= -3
Hit any key to close this window...

运行结果和原始形式一致；

参考《统计学习方法》--李航 ↩

感知机(perception)与其算法实现（R）

1.感知机模型

2.感知机算法

3.R语言实现

4 感知机学习算法的对偶形式

猜你喜欢

热点阅读