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

作者: sarai_c7eb | 来源:发表于2019-08-08 23:10 被阅读0次

感知机(perception)与其算法实现（R）
【机器学习概述】第四篇上、深度学习
感知机
统计学--感知机
spark 实现感知机算法
反馈神经网络
机器学习（一）-感知机
Spark 实现优化的线性感知机算法：Pocket PLA
感知机
1、深度学习入门-感知机

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.感知机模型感知机是二类分类的线性分类模型，其输入为实例的特征向量，输出为实例的类别，取值为1和-1二值。感知...
【机器学习概述】第四篇上、深度学习
理论知识：一、Perception algorithm感知器算法,英文wiki: 感知机是生物神经细胞的简单抽象...
感知机
感知机感知机模型感知机学习策略感知机学习算法算法的收敛性感知机学习算法的对偶形式感知机实现二分类模型 ...
统计学--感知机
参考李航的统计学习感知机学习算法 Python实现感知机代码 Python代码实现对偶形式
spark 实现感知机算法
spark 实现感知机算法感知机感知机是二分类的线性分类问题，由Rosenblatt在1957年提出，虽然年代...
反馈神经网络
1、Reference 多层感知机MLP（机器学习5）多层感知机原理详解 & Python与R实现深度学习笔记——...
机器学习（一）-感知机
形象描述感知机感知机（Perception）是神经网络和 SVM（支持向量机）的基础，是一种二分类的线性分类模型...
Spark 实现优化的线性感知机算法：Pocket PLA
Spark 实现优化的线性感知机算法：Pocket PLA 普通感知机存在的问题在上一篇文章中我们实现了普通的感...
感知机
感知机感知机算法是很多算法的鼻祖，比如支持向量机算法，神经网络与深度学习。在学习感知机的构造时可以学习到深度学习...
1、深度学习入门-感知机
感知机是什么？感知机（perceptron）：感知机是神经网络（深度学习）的起源算法，学习感知机的构造是通向神...