用BP神经网络解决“徽章”问题

用BP神经网络解决“徽章”问题 用BP神经网络解决“徽章”问题 江 南 (福建信息职业技术学院，福建福州，350003) 摘 要:神经网络具有大规模并行处理、自适应性、自组织性及容错性等其他算法无法比拟的优点～在处理分类问题中得到了广泛的应用。BP算法已成为目前应用最为广泛的神经网络学习算法～绝大部分的神经网络模型是采用BP算法或它的变化形式～它是前向神经网络的核心部分～体现了神经网络最精华的部分。文 章介绍了利用BP算法解决一个典型的分类问题——徽章问题。 关键词:BP神经网络、分类问题、学习与训练、徽章问题、matlab 0前言 徽章问题是一个典型的分类问题。它可以用一个具体的例子描述: 在某个国际会议上，参加会议的280名代表都收到会议组织者发给的一枚徽章，徽章的标记为“，”或“,”。会议的组织者声明:每位代表得到徽章“，”或“,”的标记只与他们的姓名有关，并希望代表们能够找出徽章“，”与“,”的分类。由于客观原因，有14名代表没能参加此次会议。按照代表们找出的方法判断，如果他们参加会议将得到的徽章类型。 分类问题是数据挖掘中的一个重要问题，旨在生成一个分类函数或分类模型，该模型能把数据库中的数据项映射到给定类别中的某一个。常用的分类方法主要有贝叶斯法、近邻学习法、决策树法、规则归纳法及神经网络法。而由于神经网络具有大规模并行处理、自适应性、自组织性及容错性等其他算法无法比拟的优点，而得到了广泛的应用。我们借助神经网络中的BP神经网络算法对问题进行分析，BP算法已成为目前应用最为广泛的神经网络学习算法，绝大部分的神经网络模型是采用BP算法或它的变化形式，它也是前向神经网络的核心部分，体现了神经网络最精华的部分。 1.BP神经网络 BP神经网络(Back-propagation Neutral Network) 通常是指基于误差反向传播算法(BP算法)的多层前向神经网络，采用由导师的训练方式。由于它可以实现输入和输出的任意非线性映射，使得它在诸如函数逼近、模式识别、数据压缩等领域有广泛的应用。BP神经网络分类模型图如下: BP网络不仅有输入层节点和输出层节点，而且还有隐含层节点对于输入信号。要先前向传播到隐节点，经过作用函数后，再把隐节点的输出信息传播到输出节点，最后输出结果。节点的作用函数通常选取S型函数，在matlab中，S型函数有tansig(正切S型传递函数)和 logsig (对数S型传递函数 )两种。 BP分类算法的具体过程如下: (1)根据网络要求对输入进行预处理; (2)采用BP网络对已预处理的输入进行学习与训练; (3)用训练好的BP网络对待分类样本进行模式分类。 其中，学习与训练过程是整个分类过程的重点，它由两部分组成，即网络输入信号正向传播和误差信号反向传播。在正向传播中，输入信息从输入层经隐含层逐层计算传向输出层，在输出层的各神经元输出对应输入模式的网络响应;如果输出层得不到期望输出，则误差转入反向传播，按减小期望输出与实际输出的误差原则，从输出层经到中间各层，最后回到输入，层层修正各个连接权值。随着这种误差逆传播训练不断进行，网络对输入模式响应的正确率也不断提高，如此循环直到误差信号达到允许的范围之内或训练次数达到预先设计的次数为止。 BP神经网络算法的学习训练过程如下: 1) 初始化网络，对网络参数及各权系数进行赋值，其中权系数应取随机数; 2) 输入训练样本，计算各层节点的网络输出值，并与真实值相比较，得出网络的输出误差; 3) 依据误差反向传播规则，调整隐层之间以及隐层与输入层之间的权系数; 4) 重复步骤(2)和(3)，直至预测误差满足条件或训练次数达到规定次数。 整个训练学习的过程可以由下面的框图表示: 初始化 给定导师信号 计算个节点网络输出 计算反向误差 权值学习 N 学习结束, Y 对测试样本分类 结束 在建立了有关BP神经网络算法的基本概念后，我们即可以运用Matlab已有的工具箱对BP网络进行训练并最终对所给的数据进行分类。Matlab神经网络工具箱提供了许多函数实现BP算法。 2 解决徽章问题 神经网络数据挖掘方法只能处理数值数据，因此，需要将离散的符号数据转化为数值数据。最简单的方法是建立一个符号和数字值一一对应的对照表。另一种比较复杂的方法是采用合适的哈希函数，根据给定的字符串产生一个唯一的数字值。在这个模型中，由于徽章只和姓名有关，而姓名又是英文字符串，很自然的考虑到用英文字母编码作为特征值来考虑。 给定参加会议代表的姓名及其徽章如下: + Naoki Abe - Myriam Abramson + David W. Aha + Kamal M. Ali - Eric Allender + Dana Angluin - Chidanand Apte + Minoru Asada + Lars Asker + Javed Aslam + Haralabos Athanassiou + Jose L. Balcazar + Timothy P. Barber + Michael W. Barley - Cristina Baroglio + Peter Bartlett - Eric Baum + Welton Becket „„(由于篇幅所限，在此忽略) 未参加会议的代表如下: Merrick L. Furst Jean Gabriel Ganascia William Gasarch Ricard Gavalda Melinda T. Gervasio Yolanda Gil David Gillman Attilio Giordana Kate Goelz Paul W. Goldberg Sally Goldman Diana Gordon Geoffrey Gordon Jonathan Gratch 模型一: 我们先做第一种尝试，将人名的前五个字母进行编号，a ~ z分别对应 0 ~ 25，即每个人名的特征值是一个长度为5的一维向量，总共280个人名就是个5*280的矩阵p，作为网络输入。将题目中的徽章问题量化，假设徽章为，则为1，徽章为,则为0，就形成一个1*280的矩阵t，作为目标输出。这一过程编写一个Java程序完成。 将这些特征值作为训练样本，通过Matlab的工具箱对BP分类算法进行训练，并确定权值，具体程序，注释及结果如下: >> net=newff([0 25;0 25;0 25;0 25;0 25],[100,1],{'logsig','purelin'},'trainlm'); //创建一个神经网络，每个字母所对应的量化值的输入范围0,25，神经网络有2层，第一层有100个神经元，第二层1个，传递函数分别是S型和线性，训练方式trainlm。 >> net=init(net); //初始化神经网络 >> net.trainParam.min_grad= 1e-020; //设定最小梯度值，提高训练效果 >> net=train(net,p,t); TRAINLM, Epoch 0/100, MSE 4.78695/0, Gradient 4628.35/1e-020 TRAINLM, Epoch 25/100, MSE 0.000969475/0, Gradient 4.93588/1e-020 TRAINLM, Epoch 50/100, MSE 6.16266e-005/0, Gradient 4.48141/1e-020 TRAINLM, Epoch 72/100, MSE 4.00219e-031/0, Gradient 1.53435e-013/1e-020 TRAINLM, Maximum MU reached, performance goal was not met. 得到的训练次数与训练精度的关系图如下: 将用于训练的输入数据p代入训练后的神经网络，输出结果为a矩阵 a=sim(net,p) a = Columns 1 through 9 1.0000 0.0000 1.0000 1.0000 0.0000 1.0000 -0.0000 1.0000 1.0000 Columns 10 through 18 1.0000 1.0000 1.0000 1.0000 1.0000 -0.0000 1.0000 -0.0000 1.0000 (后面数据略) 将它和用于训练的目标输出矩阵t对比可以看出，吻合得很好。 下面将14个待分类的人名的前五个字母编码输入神经网络，得到的结果如下: a=sim(net,n) a = Columns 1 through 8 1.3889 0.8504 1.0000 0.9551 -0.0006 -0.0515 1.0000 -0.7714 Columns 9 through 14 1.0776 0.9977 2.0655 0.4673 0.4794 1.0000 可以看到，这个结果不是很好，由很多介于0和1之间的数字，从这里的分析可以看出，选取字母的编码作为特征值是合理的，但需要对特征值的选取进行细化。 模型二: 对所给出的280个人名取特征值，我们将人名的第一个字母的进行编号，a ~ z分别对应 0 ~ 25，并将这些特征值带入到BP网络中去进行训练，具体程序如下: >> net=newff([0 25],[100,1],{'logsig','purelin'},'trainlm'); >> net=train(net,p,t); TRAINLM, Epoch 0/100, MSE 36.4541/0, Gradient 10111.3/1e-010 TRAINLM, Epoch 6/100, MSE 0.115783/0, Gradient 7.80296e-013/1e-010 TRAINLM, Minimum gradient reached, performance goal was not met. >> net.trainParam.min_grad= 1e-020; >> net=train(net,p,t); TRAINLM, Epoch 0/100, MSE 0.115783/0, Gradient 7.80296e-013/1e-020 TRAINLM, Epoch 3/100, MSE 0.115783/0, Gradient 1.18794e-012/1e-020 TRAINLM, Maximum MU reached, performance goal was not met. 从训练情况可以看出，在误差值比较大的时候训练就停止了，将输入p带入训练后的矩阵，发现输出结果与t很不一致，说明这里找不到分类的规律。 模型三: 我们将人名的第二个字母的进行编号，a ~ z分别对应 0 ~ 25，得到特征值矩阵p， 作为训练样本，具体程序及结果如下: >> net=newff([0 25],[100,1],{'logsig','purelin'},'trainlm'); >> net=init(net); >> net.trainParam.epochs = 100; >> net.trainParam.min_grad= 1e-020; >> net=train(net,p,t); TRAINLM, Epoch 0/100, MSE 1.33712/0, Gradient 889.071/1e-020 TRAINLM, Epoch 7/100, MSE 0.00352734/0, Gradient 2.11219e-012/1e-020 TRAINLM, Maximum MU reached, performance goal was not met. >> a=sim(net,p) 训练后的BP神经网络，输入参加训练的数据p，验证数据，可以看出，和所给人名所对应的徽章满足的很好，所得到的数据如下: a = Columns 1 through 8 0.9877 0.0000 0.9877 0.9877 -0.0000 0.9877 0.0000 1.0000 Columns 9 through 16 0.9877 0.9877 0.9877 1.0000 1.0000 1.0000 -0.0000 1.0000 训练次数和训练精度的关系图如下: 可见收敛的速度相当之快。 对于待分类的人名，先将其做同样的量化，如下: >> n=[4 4 8 8 4 14 0 19 0 0 0 8 4 14 ]; >> a=sim(net,n) 用已训练完的BP神经网络对其进行分类，得到的结果如下: a = Columns 1 through 8 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 0.9877 0.0000 Columns 9 through 14 0.9877 0.9877 0.9877 1.0000 1.0000 1.0000 可以看出，也是呈0-1的分布，和分类的要求比较接近。 3 分类方法的确定 通过模型一，模型二和模型三的比较，我们可以看出模型三的特征值的取法所得的BP算法对于所给的280个数据的正确率为100,，并且对于14个待分类的人名计算得到的特征值从数据本身看来非0即1，可见模型三所对应的分类方法有可能是可行的，即我们可以通过对名字的第二个字母的某种进行分类。 我们通过对第二个字母的多种分类方法进行尝试，得到通过第二个字母的元辅音进行分类，即第二个字母是元音为，，为辅音为,，并对280个所给人名进行分类，结果与所给分类方式一致，可见这就是我们要找的分类方法。 用这种分类方法对14个待分类人名进行分类得到的结果如下: 1 1 1 1 1 1 1 0 1 1 1 1 1 1 将这个分类结果与上面我们通过Matlab用BP算法得出的分类结果一致，这再一次证明我们所找到的分类方法就是最好的分类方法。 4 结 语 从以上的分析可以看出，BP神经网络分类算法对解决分类的问题有着很好的效果，它可以达到很高的分类精度，实现了人工智能，而学习过程不需要太多人工的干预。但是在算法实际操作上，选择神经网络的复杂程度与效率有着较大的关系，如果神经网络较为简单，如只有10个节点，收敛速度将变慢，而复杂的网络就对计算机硬件提出了较高的要求，由 于神经网络是采用并行计算，普通计算机在解决此类问题时需要较大的内存和较好的CPU，在P4 1.8G/128M/Win2000/Matlab6.5.1环境下的运行速度约为Dothan 1.6G/512M/WinXP/Matlab7.0.4的三分之一，因此，在使用BP算法时应注意网络大小的合适选择，训练数据的预处理等过程，使算法在计算机上能够运行。 参考文献: [1] 周开利等.神经网络模型及其MATLAB仿真程序设计[M].北京:清华大学出版社，2005. [2] 蒋宗礼.人工神经网络导论[M].北京:高等教育出版社，2003. [3] 朱大奇，史 慧.人工神经网络原理及应用[M].北京:科学出版社，2006. 作者简介:江南(1972— )，女，福建 人，讲师，研究方向:软件开放。