感知器算法(c语言版)
#include
#include
#define C 1
void main()
{
int i,j,k,N1,N2,x[20][2],s[3],d[20],array[20][4],w[4];//s[]用于记录各点坐标乘积;array[]用于存放将输入点变换后的点
printf(" 感知器算法(两类别问题)\n");
printf("请输入第1类坐标点数N1：");
scanf("%d",&N1);
printf("请输入第1类各点的坐标:\n");
for(i=0;i { // scanf("%d",&array[i][0]); scanf("%d%d",&x[i][0],&x[i][1]); } printf("请输入第2类坐标点数N2："); scanf("%d",&N2); printf("请输入第2类各点的坐标:\n"); for(i=0;i { // scanf("%d",&array[i][0]); scanf("%d%d",&x[i+N1][0],&x[i+N1][1]); } /* for(i=0;i { printf("输入的第1类坐标点为"); printf("{%d,%d} ",x[i][0],x[i][1]); } for(i=0;i { printf("输入的第2类坐标点为"); printf("{%d,%d} ",x[i+N1][0],x[i+N2][1]); } */ printf("输入的第1类点为:\n"); for(j=0;j { array[j][0]=1; array[j][1]=x[j][0]; array[j][2]=x[j][1]; array[j][3]=1; printf("(%d,%d,%d)\n",array[j][1],array[j][2],array[j][3]); } printf("输入的第2类点为:\n"); for(j=N1;j<(N1+N2);j++) { array[j][0]=2; array[j][1]=(-1)*x[j][0]; array[j][2]=(-1)*x[j][1]; array[j][3]=-1; printf("(%d,%d,%d)\n",array[j][1],array[j][2],array[j][3]); } printf("取参数C为:%d\n",C); printf("初始向量为:\n"); w[0]=1;w[1]=0;w[2]=0;w[3]=0; printf("{%d,%d,%d}\n",w[1],w[2],w[3]); do { for(i=0;i<(N1+N2);i++) { for(j=0;j<3;j++) s[j]=array[i][j+1]*w[j+1]; d[i]=s[0]+s[1]+s[2]; if(d[i]<=0) { for(k=0;k<3;k++) w[k+1]=C*array[i][k+1]+w[k+1]; } } for(j=(N1+N2-1);j>=0;j--) k=(d[j]<=0)||(d[j+1]<=0); } while(k); //while((d[0]<=0)||(d[1]<=0)||(d[2]<=0)||(d[3]<=0)); printf("优化后的向量w=:("); for(k=0;k<3;k++) printf("%d ",w[k+1]); printf(")\n"); }//程序缺点：不能动态分配内存大小，导致内存使用浪费； 感知器算法求判别函数 一、 实验目的 掌握判别函数的概念和性质，并熟悉判别函数的分类方法，通过实验更深入的了解判别函数及感知器算法用于多类的情况，为以后更好的学习模式识别打下基础。 二、 实验内容 学习判别函数及感知器算法原理，在MATLAB 平台设计一个基于感知器算法进行训练得到三类分布于二维空间的线性可分模式的样本判别函数的实验，并画出判决面，分析实验结果并做出总结。 三、 实验原理 3.1 判别函数概念 直接用来对模式进行分类的准则函数。若分属于ω1，ω2的两类模式可用一方程d (X ) =0来划分，那么称d (X ) 为判别函数，或称判决函数、决策函数。如，一个二维的两类判别问题，模式分布如图示，这些分属于ω1，ω2两类的模式可用一直线方程 d (X )=0来划分。其中 0)(32211=++=w x w x w d X (1) 21,x x 为坐标变量。 将某一未知模式 X 代入（1）中： 若0)(>X d ，则1ω∈X 类； 若0)( 类学习机模型的称呼，属于有关机器学习的仿生学领域中的问题，由于无法实现非线性分类而下马。但“赏罚概念（ reward-punishment concept ）” 得到广泛应用，感知器算法就是一种赏罚过程[2]。 两类线性可分的模式类 21,ωω，设X W X d T )(=其中，[]T 1 21,,,,+=n n w w w w ΛW ，[]T 211,,,,n x x x Λ=X 应具有性质 （2） 对样本进行规范化处理，即ω2类样本全部乘以(－1)，则有： （3） 感知器算法通过对已知类别的训练样本集的学习，寻找一个满足上式的权向量。 感知器算法步骤： （1）选择N 个分属于ω1和 ω2类的模式样本构成训练样本集{ X1 ,…, XN }构成增广向量形式，并进行规范化处理。任取权向量初始值W(1)，开始迭代。迭代次数k=1。 （2）用全部训练样本进行一轮迭代，计算W T (k )X i 的值，并修正权向量。 分两种情况，更新权向量的值： 1. ()，若0≤T i k X W 分类器对第i 个模式做了错误分类，权向量校正为： ()()i c k k X W W +=+1 c ：正的校正增量。 2. 若()，0T >i k X W 分类正确，权向量不变：()()k k W W =+1,统一写为： ???∈<∈>=21T ,0,0)(ωωX X X W X 若若d 机器学习入门- 感知器(PERCEPTRON) POSTED IN 学术_STUDY, 机器学习 本文是基于马里兰大学教授Hal Dame III（Blogger）课程内容的笔记。 感知器(Perceptron)这个词会成为Machine Learning的重要概念之一，是由于先辈们对于生物神经学科的深刻理解和融会贯通。 对于神经(neuron)我们有一个简单的抽象：每个神经元是与其他神经元连结在一起的，一个神经元会受到多个其他神经元状态的冲击，并由此决定自身是否激发。（如下图） Neuron Model (From Wikipedia) 这玩意儿仔细想起来可以为我们解决很多问题，尤其是使用决策树和KNN算法时解决不了的那些问题： ?决策树只使用了一小部分知识来得到问题的答案，这造成了一定程度上的资源浪费。 ?KNN对待数据的每个特征值都是一样的，这也是个大问题。比如一组数据包含100种特征值，而只有其中的一两种是起最重要作用的话，其他的特征值就变成了阻碍我们找到最好答案的噪声(Noise)。 根据神经元模型，我们可以设计这样一种算法。对于每种输入值(1 - D)，我们计算一个权重。当前神经元的总激发值(a)就等于每种输入值(x)乘以权重(w)之和。 neuron sum 我们还可以推导出以下几条规则： ?如果当前神经元的某个输入值权重为零，则当前神经元激发与否与这个输入值无关?如果某个输入值的权重为正，它对于当前神经元的激发值a 产生正影响。反之，如果权重为负，则它对激发值产生负影响。 接下来我们要将偏移量(bias)的概念加入这个算法。有时我们希望我们的神经元激发量a 超过某一个临界值时再激发。在这种情况下，我们需要用到偏移量b。 neuron sum with bias 偏移量b 虽然只是附在式子后面的一个常数，但是它改变了几件事情： ?它定义了神经元的激发临界值 ?在空间上，它对决策边界(decision boundary) 有平移作用，就像常数作用在一次或二次函数上的效果。这个问题我们稍后再讨论。 在了解了神经元模型的基本思路之后，我们来仔细探讨一下感知器算法的具体内容。 感知器算法虽然也是二维分类器(Binary Classifier)，但它与我们所知道的决策树算法和KNN都不太一样。主要区别在于： ?感知器算法是一种所谓“错误驱动(error-driven)”的算法。当我们训练这个算法时，只要输出值是正确的，这个算法就不会进行任何数据的调整。反之，当输出值与实际值异号，这个算法就会自动调整参数的比重。 ?感知器算法是实时(online)的。它逐一处理每一条数据，而不是进行批处理。 perceptron algorithms by Hal Dame III 感知器算法实际上是在不断“猜测”正确的权重和偏移量： ?首先，感知器算法将所有输入值的权重预设为0。这意味着，输入值预设为对结果不产生任何影响。同时，偏移量也被预设为0。 ?我们使用参数MaxIter。这个参数是整个算法中唯一一个超参数(hyper-parameter)。 这个超参数表示当我们一直无法找到准确答案时，我们要最多对权重和偏移量进行几次优化。 ·在一个10类的模式识别问题中，有3类单独满足多类情况1，其余的类别满足多类情况2。问该模式识别问题所需判别函数的最少数目是多少？ 应该是252142 6 *74132 7=+=+ =++C 其中加一是分别3类 和 7类 ·一个三类问题，其判别函数如下： d1(x)=-x1, d2(x)=x1+x2-1, d3(x)=x1-x2-1 (1)设这些函数是在多类情况1条件下确定的，绘出其判别界面和每一个模式类别的区域。 (2)设为多类情况2，并使：d12(x)= d1(x), d13(x)= d2(x), d23(x)= d3(x)。绘出其判别界面和多类情况2的区域。 (3)设d1(x), d2(x)和d3(x)是在多类情况3的条件下确定的，绘出其判别界面和每类的区域。 ·两类模式，每类包括5个3维不同的模式，且良好分布。如果它们是线性可分的，问权向量至少需要几个系数分量？假如要建立二次的多项式判别函数，又至少需要几个系数分量？（设模式的良好分布不因模式变化而改变。） 如果线性可分，则4个 建立二次的多项式判别函数，则102 5 C 个 ·(1)用感知器算法求下列模式分类的解向量w: ω1: {(0 0 0)T , (1 0 0)T , (1 0 1)T , (1 1 0)T } ω2: {(0 0 1)T , (0 1 1)T , (0 1 0)T , (1 1 1)T } 将属于ω2的训练样本乘以（-1），并写成增广向量的形式。 x ①=(0 0 0 1)T , x ②=(1 0 0 1)T , x ③=(1 0 1 1)T , x ④=(1 1 0 1)T x ⑤=(0 0 -1 -1)T , x ⑥=(0 -1 -1 -1)T , x ⑦=(0 -1 0 -1)T , x ⑧=(-1 -1 -1 -1)T 第一轮迭代：取C=1，w(1)=(0 0 0 0) T 因w T (1) x ① =(0 0 0 0)(0 0 0 1) T =0 ≯0，故w(2)=w(1)+ x ① =(0 0 0 1) 因w T (2) x ② =(0 0 0 1)(1 0 0 1) T =1>0，故w(3)=w(2)=(0 0 0 1)T 因w T (3)x ③=(0 0 0 1)(1 0 1 1)T =1>0，故w(4)=w(3) =(0 0 0 1)T 因w T (4)x ④=(0 0 0 1)(1 1 0 1)T =1>0，故w(5)=w(4)=(0 0 0 1)T 因w T (5)x ⑤=(0 0 0 1)(0 0 -1 -1)T =-1≯0，故w(6)=w(5)+ x ⑤=(0 0 -1 0)T 因w T (6)x ⑥=(0 0 -1 0)(0 -1 -1 -1)T =1>0，故w(7)=w(6)=(0 0 -1 0)T 因w T (7)x ⑦=(0 0 -1 0)(0 -1 0 -1)T =0≯0，故w(8)=w(7)+ x ⑦=(0 -1 -1 -1)T 因w T (8)x ⑧=(0 -1 -1 -1)(-1 -1 -1 -1)T =3>0，故w(9)=w(8) =(0 -1 -1 -1)T 因为只有对全部模式都能正确判别的权向量才是正确的解，因此需进行第二轮迭代。 第二轮迭代： 因w T (9)x ①=(0 -1 -1 -1)(0 0 0 1)T =-1≯0，故w(10)=w(9)+ x ① =(0 -1 -1 0)T 感知器的学习算法 1．离散单输出感知器训练算法 设网络输入为n 维向量()110-=n x x x ,,, X ，网络权值向量为()110-=n ωωω,,, W ，样本集为(){}i i d ,X ，神经元激活函数为f ，神经元的理想输出为d ，实际输出为y 。 算法如下： Step1：初始化网络权值向量W ； Step2：重复下列过程，直到训练完成： （2.1）对样本集中的每个样本()d ,X ，重复如下过程： （2.1.1）将X 输入网络； （2.1.2）计算)(T =WX f y ； （2.1.3）若d y ≠，则当0=y 时，X W W ?+=α；否则X W W ?-=α。 2．离散多输出感知器训练算法 设网络的n 维输入向量为()110-=n x x x ,,, X ，网络权值矩阵为{}ji n m ω=?W ，网络理想输出向量为m 维，即()110-=m d d d ,,, D ，样本集为(){}i i D X ,，神经元激活函数为f ， 网络的实际输出向量为()110-=m y y y ,,, Y 。 算法如下： Step1：初始化网络权值矩阵W ； Step2：重复下列过程，直到训练完成： （2.1）对样本集中的每个样本()D X ,，重复如下过程： （2.1.1）将X 输入网络； （2.1.2）计算)(T =XW Y f ； （2.1.3）对于输出层各神经元j （110-=m j ,,, ）执行如下操作： 若j j d y ≠，则当0=j y 时，i ji ji x ?+=αωω，110-=n i ,,, ； 否则i ji ji x ?-=αωω，110-=n i ,,, 。 感知器算法实验--1 一.实验目的 1.理解线性分类器的分类原理。 2.掌握感知器算法，利用它对输入的数据进行 分类。 3.理解BP算法，使用BP算法对输入数据进 行分类。 二. 实验原理 1.感知器算法 感知器算法是通过训练模式的迭代和学习算法，产生线性可分的模式判别函数。感知器算法就是通过对训练模式样本集的“学习”得出判别函数的系数解。在本次实验中，我们主要是采用硬限幅函数进行分类。 感知器的训练算法如下： 设输入矢量{x1,x2,…,x n}其中每一个模式类别已知，它们分别属于ω1类和ω2类。 （1）置步数k=1，令增量ρ为某正的常数，分别赋给初始增广权矢量w(1)的各分量较小的任意值。 （2）输入训练模式x k，计算判别函数值 w T(k) x k。 （3）调整增广权矢量，规则是： a.如果x k ∈ω1和w T (k) x k ≤0，则w(k+1)=w(k)+ ρx k ； b.如果x k ∈ω2和w T (k) x k ≥0，则w(k+1)=w(k)-ρx k ； c.如果x k ∈ω1和w T (k) x k >0，或x k ∈ω2和w T (k) x k <0，则w(k+1)=w(k) （4）如果k 大学模式识别考试题及 答案详解 Document number：PBGCG-0857-BTDO-0089-PTT1998 一、填空与选择填空（本题答案写在此试卷上，30分） 1、模式识别系统的基本构成单元包括：模式采集、特征提取与选择 和模式分类。 2、统计模式识别中描述模式的方法一般使用特真矢量；句法模式识别中模式描述方法一般有串、树、网。 3、聚类分析算法属于（1）；判别域代数界面方程法属于（3）。 （1）无监督分类 (2)有监督分类（3）统计模式识别方法（4）句法模式识别方法4、若描述模式的特征量为0-1二值特征量，则一般采用（4）进行相似性度量。 （1）距离测度（2）模糊测度（3）相似测度（4）匹配测度 5、下列函数可以作为聚类分析中的准则函数的有（1）（3）（4）。 （1）（2） (3) (4) 6、Fisher线性判别函数的求解过程是将N维特征矢量投影在（2）中进行。 （1）二维空间（2）一维空间（3）N-1维空间 7、下列判别域界面方程法中只适用于线性可分情况的算法有（1）；线性可分、不可分都适用的有（3）。 （1）感知器算法（2）H-K算法（3）积累位势函数法 8、下列四元组中满足文法定义的有（1）（2）（4）。 （1）({A, B}, {0, 1}, {A?01, A? 0A1 , A? 1A0 , B?BA , B? 0}, A) （2）({A}, {0, 1}, {A?0, A? 0A}, A) （3）({S}, {a, b}, {S ? 00S, S ? 11S, S ? 00, S ? 11}, S) （4）({A}, {0, 1}, {A?01, A? 0A1, A? 1A0}, A) 二、(15分)简答及证明题 （1）影响聚类结果的主要因素有那些？ （2）证明马氏距离是平移不变的、非奇异线性变换不变的。 答：（1）分类准则，模式相似性测度，特征量的选择，量纲。 （2）证明： 感知器的训练算法实例 将属于ω2的训练样本乘以（-1），并写成增广向量的形式。 x①=(0 0 1)T, x②=(0 1 1)T, x③=(-1 0 -1)T, x④=(-1 -1 -1)T 第一轮迭代：取C=1，w(1)= (0 0 0)T 因w T(1)x①=(0 0 0)(0 0 1)T=0≯0，故w(2)=w(1)+x①=(0 0 1)T 因w T(2)x②=(0 0 1)(0 1 1)T=1>0，故w(3)=w(2)=(0 0 1)T 因w T(3)x③=(0 0 1)(-1 0 -1)T=-1≯0，故w(4)=w(3)+x③=(-1 0 0)T 因w T(4)x④=(-1 0 0)(-1 -1 -1)T=1>0，故w(5)=w(4)=(-1 0 0)T 这里，第1步和第3步为错误分类，应“罚”。 因为只有对全部模式都能正确判别的权向量才是正确的解，因此需进行第二轮迭代。 第二轮迭代： 因w T(5)x①=(-1 0 0)(0 0 1)T=0≯0，故w(6)=w(5)+x①=(-1 0 1)T 因w T(6)x②=(-1 0 1)(0 1 1)T=1>0，故w(7)=w(6)=(-1 0 1)T 因w T(7)x③=(-1 0 1)(-1 0 -1)T=0≯0，故w(8)=w(7)+x③=(-2 0 0)T 因w T(8)x④=(-2 0 0)(-1 -1 -1)T=2>0，故w(9)=w(8)=(-2 0 0)T 需进行第三轮迭代。 第三轮迭代： 因w T(9)x①=(-2 0 0)(0 0 1)T=0≯0，故w(10)=w(9)+x①=(-2 0 1)T 模式识别第三章 感知器算法 一．用感知器算法求下列模式分类的解向量w ： })0,1,1(,)1,0,1(,)0,0,1(,)0,0,0{(:1T T T T ω })1,1,1(,)0,1,0(,)1,1,0(,)1,0,0{(:2T T T T ω 将属于2ω的训练样本乘以（-1），并写成增广向量的形式： T x )1,0,0,0(1 =，T x )1,0,0,1(2=，T x )1,1,0,1(3=，T x )1,0,1,1(4 = T x )1,1-,0,0(5-=，T x )1,1-,1-,0(6-=，T x )1,0,1-,0(7-=，T x )1,1-,1-,1-(8-= 第一轮迭代：取1=C ，T )0,0,0,0()1(=ω 因0)1,0,0,0)(0,0,0,0()1(1==T T x ω不大于0，故T x )1,0,0,0()1()2(1=+=ωω 因1)1,0,0,1)(1,0,0,0()2(2==T T x ω大于0，故T )1,0,0,0()2()3(==ωω 因1)1,1,0,1)(1,0,0,0()3(3==T T x ω大于0，故T )1,0,0,0()3()4(==ωω 因1)1,0,1,1)(1,0,0,0()4(4==T T x ω大于0，故T )1,0,0,0()4()5(==ωω 因1)1,1-,0,0)(1,0,0,0()5(5-=-=T T x ω不大于0，故T x )0,1-,0,0()5()6(5 =+=ωω 因1)1,1-,1-,0)(0,1-,0,0()6(6=-=T T x ω大于0，故T )0,1-,0,0()6()7(==ωω 因0)1,0,1-,0)(0,1-,0,0()7(7=-=T T x ω不大于0，故T x )1-,1-,1,0()7()8(7-=+=ωω 因3)1,1-,1-,1-)(1-,1-,1,0()8(8=--=T T x ω大于0，故T )1-,1-,1,0()8()9(-==ωω 第二轮迭代： 因1)1,0,0,0)(1-,1-,1,0()9(1-=-=T T x ω不大于0，故T x )0,1-,1,0()9()10(1-=+=ωω 因0)1,0,0,1)(0,1-,1-,0()10(2==T T x ω不大于0，故T x )1,1,1,1()10()11(2--=+=ωω 因1)1,1,0,1)(1,1,1,1()11(3=--=T T x ω大于0，故T )1,1,1,1()11()12(--==ωω 因1)1,0,1,1)(1,1,1,1()12(4=--=T T x ω大于0，故T )1,1,1,1()12()13(--==ωω 实验二 感知器准则算法实验 一、实验目的： 1）加深对感知准则算法的基本思想的认识和理解。 2）编程实现批处理感知器算法的程序。 二、实验原理： 1.假设已知一组容量为N 的样本集1y ，2y ，…，N y ，其中N y 为d 维增广样本向量，分别来自1ω和2ω类。如果有一个线性机器能把每个样本正确分类，即存在一个权向量a ，使得对于任何1ω∈y ，都有y a T >0，而对一任何2ω∈y ，都有y a T <0，则称这组样本集线性可分；否则称线性不可分。若线性可分，则必存在一个权向量a ，能将每个样本正确分类。 2.基本方法： 由上面原理可知，样本集1y ，2y ，…，N y 是线性可分，则必存在某个权向量a ，使得 ?????∈<∈>2 1 y ,0y ,0ωωj j T i i T y a y a 对一切对一切 如果我们在来自2ω类的样本j y 前面加上一个负号，即令j y =—j y ，其中2ω∈j y ，则也有 y a T >0。因此，我们令 ???∈∈='21y ,-y ,ωωj j i i n y y y 对一切对一切 那么，我们就可以不管样本原来的类型标志，只要找到一个对全部样本n y '都满足y a T >0，N n ,,3,2,1??=的权向量a 就行了。此过程称为样本的规范化，n y '成为规范化增广样本向量，后面我们用y 来表示它。 我们的目的是找到一个解向量* a ，使得 N n y a n T ,...,2,1,0=> 为此我们首先考虑处理线性可分问题的算法。先构造这样一个准则函数 )()(∑∈-= k y T p y a a J γ 式中k γ是被权向量a 错分类的样本集合。错分类时有0≤y a T ，或0≥-y a T —190 — 感知器学习算法研究 刘建伟，申芳林，罗雄麟 (中国石油大学(北京)自动化研究所，北京 102249) 摘 要：介绍感知器学习算法及其变种，给出各种感知器算法的伪代码，指出各种算法的优点。给出感知器算法在线性可分和线性不可分情况下的误差界定理，讨论各种感知器学习算法的误差界理论，给出各种算法的误差界。介绍感知器学习算法在在线优化场景、强化学习场景和赌博机算法中的应用，并对未解决的问题进行讨论。 关键词：感知器；错误界；赌博机算法；强化学习 Reserch on Perceptron Learning Algorithm LIU Jian-wei, SHEN Fang-lin, LUO Xiong-lin (Research Institute of Automation, China University of Petroleum, Beijing 102249) 【Abstract 】This paper introduces some perceptron algorithms and their variations, gives various pseudo-codes, pionts out advantage among algorithms. It gives mistake bound’s theorems of perceptrons algorithm in linearly separable and unlinearly separable situation. It studies their mistake bounds and works out their bounds. It shows their various applications in the online optimization, reinforcement learning and bandit algorithm, and discusses the open problems. 【Key words 】perceptron; mistake bound; bandit algorithm; reinforcement learning 计 算 机 工 程Computer Engineering 第36卷 第7期 Vol.36 No.7 2010年4月 April 2010 ·人工智能及识别技术·文章编号：1000—3428(2010)07—0190—03 文献标识码：A 中图分类号：TP18 感知器算法[1]由Rosenblatt 提出，其主要功能是通过设计分类器来判别样本所属的类别；通过对训练样本集的学习，从而得到判别函数权值的解，产生线性可分的样本判别函数。该算法属于非参数算法，优点是不需要对各类样本的统计性质作任何假设，属于确定性方法。 1 感知器的主要算法 1.1 感知器算法 感知器算法是非常好的二分类在线算法。该算法求取一个分离超平面，超平面由n w R ∈参数化并用来预测。对于一 个样本x ，感知器算法通过计算?,y w x =预测样本的标签。最终的预测标签通过计算()?sign y 来实现。算法仅在预测错误时修正权值w 。如果正确的标签是1y =，那么权值修正为 w x +；如果1y =?，权值变为w x ?，可以总结为w w yx ←+； 需要注意的是在预测后，尽管算法不能保证修正后的预测准 则会正确分类目前的样本，但在目前样本上的分离超平面的间隔会增加，即算法是保守的不是主动的，感知器算法伪代码如下： Initialize: Set w 1=0 For: i=1, 2,…,m Get a new instance x i Predict i i i ?y =w ,x Get a new label y i Compute L=L(w i ,(x i , y i )) Update: If L=0, w i+1=w i If L=1, w i+1=w i +y i x i Output: m h(x)=w ,x 支持向量机(SVM)也是使用超平面来分类的，但SVM 中 的超平面要求每类数据与超平面距离最近的向量与超平面之间的间隔最大，而感知器不需要间隔最大化。 1.2 平均感知器 平均感知器[2](Averaged Perceptron, AP)算法和感知器算法的训练方法一样。不同的是每次训练样本i x 后，保留先前训练权值{}12,,,n w w w "，训练结束后平均所有权值即 1n i i w w n ==∑ 最终用平均权值作为最终判别准则的权值。平均感知器 算法伪代码如下： Initialization: (w 1, w 2,…, w n )=0 For i=1,2,…, n Receive d i x R ∈, {}i y 1,1+?∈ Predict: ()i t t ?y =sign w x ? Receive correct lable: {}i y 1,1∈+? Update i+1i i i w =w +y x Output n i i=1w=w /n ∑ 参数平均化可以克服由于学习速率过大所引起的训练过 程中出现的震荡现象。 1.3 信任权感知器 信任权(Confidence Weighted, CW)学习[3]是一种新的在线学习算法，它使每个学习参数有个信任度。较小信任度的参数得到更大的更频繁的修正。参数信任权用参数向量的高斯分布表示。每训练一次样本就修正一次参数信任权使样本 作者简介：刘建伟(1966－)，男，副研究员、博士，主研方向：机器学习；申芳林，硕士；罗雄麟，教授、博士生导师 收稿日期：2009-08-12 E-mail ：shenfanglin@https://www.wendangku.net/doc/d82227305.html, 《模式识别》试题库 一、基本概念题 1模式识别的三大核心问题是：（ ）、（ ）、（ ）。 2、模式分布为团状时，选用（ ）聚类算法较好。 3 欧式距离具有（ ）。马式距离具有（ ）。（1）平移不变性（2）旋转不 变性（3）尺度缩放不变性（4）不受量纲影响的特性 4 描述模式相似的测度有( )。（1）距离测度 （2）模糊测度 （3）相似测度 （4） 匹配测度 5 利用两类方法处理多类问题的技术途径有：（1） （2） （3） 。其中最常用的是第( )个技术途径。 6 判别函数的正负和数值大小在分类中的意义是：( )。 7 感知器算法 ( )。（1）只适用于线性可分的情况；（2）线性可分、不可分都适用。 8 积累位势函数法的判别界面一般为( )。（1）线性界面；（2）非线性界面。 9 基于距离的类别可分性判据有：( ).（1）1[]w B Tr S S - （2） B W S S （3） B W B S S S + 10 作为统计判别问题的模式分类，在（ ）情况下，可使用聂曼-皮尔逊判决准则。 11 确定性模式非线形分类的势函数法中，位势函数K(x,xk)与积累位势函数K(x)的关系为 （ ）。 12 用作确定性模式非线形分类的势函数法，通常，两个n 维向量x 和xk 的函数K(x,xk)若 同时满足下列三个条件，都可作为势函数。①（ ）； ②（ ）；③ K(x,xk)是光滑函数，且是x 和xk 之间距离的单调下降函数。 13 散度Jij 越大，说明ωi 类模式与ωj 类模式的分布（ ）。当ωi 类 模式与ωj 类模式的分布相同时，Jij=（ ）。 14 若用Parzen 窗法估计模式的类概率密度函数，窗口尺寸h1过小可能产生的问题是 （ ），h1过大可能产生的问题是（ ）。 15 信息熵可以作为一种可分性判据的原因是：( )。 16作为统计判别问题的模式分类，在（ ）条件下，最小损失判决规则与最 小错误判决规则是等价的。 17 随机变量l(x ρ)=p(x ρ|ω1)/p(x ρ|ω2)，l(x ρ)又称似然比，则E {l( x ρ)|ω2}=（ ）。 在最小误判概率准则下，对数似然比Bayes 判决规则为（ ）。 18 影响类概率密度估计质量的最重要因素（ ）。 19 基于熵的可分性判据定义为)] |(log )|([1x P x P E J i c i i x H ρρωω∑=-=，JH 越（ ），说 明模式的可分性越强。当P(ωi| x ρ) =（ ）(i=1,2,…,c)时，JH 取极大值。 20 Kn 近邻元法较之于Parzen 窗法的优势在于（ ）。上 述两种算法的共同弱点主要是（ ）。 21 已知有限状态自动机Af=(∑，Q ，δ，q0，F)，∑={0，1}；Q={q0，q1}；δ：δ(q0，0)= q1， δ(q0，1)= q1，δ(q1，0)=q0，δ(q1，1)=q0；q0=q0；F={q0}。 现有输入字符串：(a) 00011101011，(b) 1100110011，(c) 101100111000，(d)0010011， 试问，用Af 对上述字符串进行分类的结果为（ ）。 感知器算法作业： 图为二维平面中的4个点，x 1, x 2∈ω1 ，x 3，x 4∈ω2 ，设计使用感知器算法的线性分类器，步长参数设为1. 解：由题知： 112:[1,0][0,1]T T X X ω=-=234:[01][10]T T X X ω=-=，， 所有样本写成增广向量形式，进行规范化处理，属于2ω的样本乘以-1 12[1,0,1][0,1,1]T T X X =-=34[011][101]T T X X =-=--，，，， 步长c=1，任取(1)[0,0,0]T W = 第一轮迭代： 11(1)[0,0,0]0=001T W X -????=≤?????? ， ，故1(2)(1)[1,0,1]T W W X =+=- 20(2)[1,0,1]1=101T W X ????=-?????? ，>，故(3)(2)[1,0,1]T W W ==- 30(3)[1,0,1]1=101T W X ????=--≤????-?? ，，故3(4)(3)[1,1,0]T W W X =+=- 41(4)[1,1,0]0=101T W X -????=-????-?? ，>，故(5)(4)[1,1,0]T W W ==- 第二轮迭代： 1x 2x 3x 4x 11(5)[1,1,0]0=101T W X -????=-?????? ，>，故(6)(5)[1,1,0]T W W ==- 20(6)[1,1,0]1=101T W X ????=-?????? ，>，故(7)(6)[1,1,0]T W W ==- 30(7)[1,1,0]1=101T W X ????=-????-?? ，>，故(8)(7)[1,1,0]T W W ==- 41(8)[1,1,0]0=101T W X -????=-????-?? ，>，故(9)(8)[1,1,0]T W W ==- 该轮迭代的分类结果全部正确，故解向量[1,1,0]T W =- 相应的判别函数为12()d X x x =-+ function Perceptron %UNTITLED Summary of this function goes here % Detailed explanation goes here X=[-1 0 0 -1;0 1 1 0;1 1 -1 -1]; W1=[0 0 0]'; t=0; s=1; while s>0 s=0; for i=1:4 if W1'*X(:,i)<=0; W1=W1+X(:,i); s=s+1; else W1=W1+0; s=s+0; end end t=t+1; end fprintf('迭代次数为',t) 给定样本如下： else j=j+1; end if(j==4) break; end if(y4*X<=0) X=X+c*y4'; j=0; else j=j+1; end if(j==4) break; end end %输出 Y=zeros(1,3); Y(1)=X(1,1);Y(2)=X(2,1);Y(3)=X(3,1); Y X(4,1) 运行程序，结果如下： Y = 0 -1 3 ans = 0 带回运算，知该判别函数可以分出两类。 实验三程序过于重复，改写程序体如下： x1=[1,0,1];x2=[0,1,1];x3=[1,1,0];x4=[0,1,0]; y1=[x1,1];y2=[x2,1];y3=[-x3,-1];y4=[-x4,-1]; %将增光规范化的矩阵写成一个y=[y1;y2;y3;y4]; c=1;X=[1;1;1;1];k=0;i=1;j=0; %大循环控制运行迭代的步数for(i=1:2000) % 内循环用于计算处理判断 for(j=1:4) if(y(j,:)*X<=0) X=X+c*y(j,:)'; k=0; else k=k+1; end if(k==4) break; end end if(k==4) break; end end X' 运行程序，得出结果一致： 习题四 已知两类训练样本为 w 1: (0, 0, 0)T , (1, 0, 0,)T , (1, 0, 1)T , (1, 1, 0)T w 2: (0, 0, 1)T , (0, 1, 1,)T , (0, 1, 0)T , (1, 1, 1)T 设 W (1) = (-1,-2,-2,0)T ，用感知机算法求解判别函数，并绘出判别界面。 解：将属于2w 的训练样本乘以(1)-，并写成增广向量的形式 x1=[0 0 0 1]',x2=[1 0 0 1]',x3=[1 0 1 1]',x4=[1 1 0 1]'; x5=[0 0 -1 -1]',x6=[0 -1 -1 -1]',x7=[0 -1 0 -1]',x8=[-1 -1 -1 -1]'; 迭代选取1C =，(1)(0,0,0,0)w '=，则迭代过程中权向量w 变化如下： (2)(0 0 0 1)w '=；(3)(0 0 -1 0)w '=；(4)(0 -1 -1 -1)w '=；(5)(0 -1 -1 0)w '=；(6)(1 -1 -1 1)w '=；(7)(1 -1 -2 0)w '=；(8)(1 -1 -2 1)w '=；(9)(2 -1 -1 2)w '=； (10)(2 -1 -2 1)w '=；(11)(2 -2 -2 0)w '=；(12)(2 -2 -2 1)w '=；收敛 所以最终得到解向量(2 -2 -2 1)w '=，相应的判别函数为123()2221d x x x x =--+。 第八次迭代：以2x 为训练样本，123(8)1,(8)0,(8)2d d d =-==-，故 112233(9)(8),(9)(8),(9)(8)w w w w w w === 由于第六、七、八次迭代中对312,,x x x 均以正确分类，故权向量的解为： 1．具体应用背景的介绍 感知器是由美国计算机科学家罗森布拉特（F.Roseblatt）于1957年提出的。感知器可谓是最早的人工神经网络。单层感知器是一个具有一层神经元、采用阈值激活函数的前向网络。通过对网络权值的训练，可以使感知器对一组输人矢量的响应达到元素为0或1的目标输出，从而实现对输人矢量分类的目的。 2．分类器设计方法概述及选择依据分析 分类器设计方法概述 感知器是由具有可调节的键结值以及阈值的单一个类神经元所组成，它是各种类神经网络中，最简单且最早发展出来的类神经网络模型，通常被用来作为分类器使用。感知器的基本组成元件为一个具有线性组合功能的累加器，后接一个硬限制器而成，如下图所示： 单层感知器是一个具有一层神经元、采用阈值激活函数的前向网络。通过对网络权值的训练，可以使感知器对一组输入矢量的响应达到元素为0或1的目标输出，从而达到对输入矢量分类的目的。 分类的判断规则是：若感知器的输出为1，则将其归类于C1类；若感知器的输出为0，则将其归类于C2类。判断规则所划分的只有两个判断区域，我们将作为分类依据的超平面定义如下： 感知器分类是通过训练模式的迭代和学习算法，产生线性或非线性可分的模式判别函数。它不需要对各类训练模式样本的统计性质作任何假设，所以是一种确定性的方法。比如固定增量逐次调整算法、最小平方误差算法。 要使前向神经网络模型实现某种功能，必须对它进行训练，让他学会要做的事情， 并把所学到的知识记忆在网络的权值中。人工神经网络的权值的确定不是通过计算，而是通过网络自身的训练来完成的。 感知器的训练过程如下：在输入矢量X的作用下，计算网络的实际输出A 与相应的目标矢量T进行比较，检查A是否等于T，然后比较误差T-A，根据学习规则进行权值和偏差的调整；重新计算网络在新权值作用下的输入，重复权值调整过程，知道网络的输出A等于目标矢量T或训练次数达到事先设置的最大值时结束训练。 感知器设计训练的步骤如下： （1）对于所要解决的问题，确定输入矢量X，目标矢量T，并由此确定各矢量的维数以及确定网络结构大小的参数：r(表示输入矢量维数，神经元的权值向量维数)，s（表示一个输入矢量所对应的输出矢量的维数，或者表示神经元个数），p（表示输入矢量组数，）。 （2）参数初始化：赋给权值矢量W在（-1，1）的随机非0初始值；给出最大循环次数max_epcho。 （3）网络表达式：根据输入矢量X以及最新权矢量W，计算网络输出矢量A。（4）检查输出矢量A与目标矢量T是否相同，如果是，或已达到自大循环次数，训练结束，否则转入（5）。 （5）学习：根据感知器的学习规则调整权矢量，并返回（3）。 步骤一：网络初始化 以随机的方式产生乱数，令w(0)为很小的实数，并且将学习循环n设定为1。步骤二：计算网络输出值 选择依据分析 1.准确率：模型正确预测新数据类标号的能力。 2.速度：产生和使用模型花费的时间。 3.健壮性：有噪声数据或空缺值数据时模型正确分类或预测的能力。 4.伸缩性：对于给定的大量数据，有效地构造模型的能力。 5.可解释性：学习模型提供的理解和观察的层次。 3.感知算法原理及算法步骤 感知器基本原理： 基于模式识别的判别函数分类器的设计 与实现 摘要：本文主要介绍了模式识别中判别函数的相关概念和感知器算法的原理及特点，并例举实例介绍感知器算法求解权向量和判别函数的具体方法，最后按照线性函数判决函数的感知算法思想结合数字识别，来进行设计，通过训练数字样本（每个数字样本都大于120），结合个人写字习惯，记录测试结果，最后通过matlab 编码来实现感知器的数字识别。 关键字：模式识别 判别函数 感知器 matlab 1 引言 模式识别就是通过计算机用数学技术方法来研究模式的自动处理和识别。对于人类的识别能力我们是非常熟悉的。因为我们在早些年就已经会开发识别声音、脸、动物、水果或简单不动的东西的技术了。在开发出说话技术之前，一个象球的东西，甚至看上去只是象个球，就已经可以被识别出来了。所以除了记忆，抽象和推广能力是推进模式识别技术的关键技术。最近几年我们已可以处理更复杂的模式，这种模式可能不是直接基于通过感知器观察出来的随着计算机技术的发展，人类对模式识别技术提出了更高的要求。 本文第二节介绍判别函数分类器，具体介绍了判别函数的概念、特点以及如何确定判别函数的正负； 第三节介绍了感知器的概念、特点并用感知器算法求出将模式分为两类的权向量解和判别函数，最后用matlab 实现感知判别器的设计。 2 判别函数分类器 2.1 判别函数概念 直接用来对模式进行分类的准则函数。若分属于ω1，ω2的两类模式可用一方程d (X ) =0来划分，那么称d (X ) 为判别函数，或称判决函数、决策函数。如，一个二维的两类判别问题，模式分布如图示，这些分属于ω1，ω2两类的模式可用一直线方程 d (X )=0来划分。其中0)(32211=++=w x w x w d X 式中： 21,x x 为坐标变量。 图2-1 两类二维模式的分布 将某一未知模式 X 代入： 若0)(>X d ，则1ω∈X 类； 若0)( 第三章作业3.5 已知两类训练样本为 1:(0 0 0 )',(1 0 0)' ,(1 0 1)',(1 1 0)' ω 2:(0 0 1)',(0 1 1)' ,(0 1 0)',(1 1 1)' ω 设0)' (-1,-2,-2, )1(= W,用感知器算法求解判别函数，并绘出判别界面。 解：matlab程序如下： clear %感知器算法求解判别函数 x1=[0 0 0]';x2=[1 0 0]';x3=[1 0 1]';x4=[1 1 0]';x5=[0 0 1]';x6=[0 1 1]';x7=[0 1 0]';x8=[1 1 1]'; %构成增广向量形式，并进行规范化处理 x=[0 1 1 1 0 0 0 -1;0 0 0 1 0 -1 -1 -1;0 0 1 0 -1 -1 0 -1;1 1 1 1 -1 -1 -1 -1]; plot3(x1(1),x1(2),x1(3),'ro',x2(1),x2(2),x2(3),'ro',x3(1),x3(2),x3(3) ,'ro',x4(1),x4(2),x4(3),'ro');hold on; plot3(x5(1),x5(2),x5(3),'rx',x6(1),x6(2),x6(3),'rx',x7(1),x7(2),x7(3) ,'rx',x8(1),x8(2),x8(3),'rx');grid on; w=[-1,-2,-2,0]';c=1;N=2000; for k=1:N t=[]; for i=1:8 d=w'*x(:,i); if d>0 w=w; t=[t 1]; else w=w+c*x(:,i); t=[t -1]; end end if i==8&t==ones(1,8) w=w syms x y z=-w(1)/w(3)*x-w(2)/w(3)*y-1/w(3); ezmesh(x,y,z,[0.5 1 2]); axis([-0.5,1.5,-0.5,1.5,-0.5,1.5]); title('感知器算法') break; else end end模式识别感知器算法求判别函数
机器学习入门 - 感知器
黄庆明 模式识别与机器学习 第三章 作业
感知器的学习算法
感知器算法实验--1
大学模式识别考试题及答案详解
感知器的训练算法实例
模式识别第三章-感知器算法
模式识别实验 感知器准则算法实验
感知器学习算法研究
模式识别试题2
感知器算法 作业
模式识别感知器算法matlab实现
感知机算法习题
感知器
感知器算法
模式识别作业第三章2(推荐文档)