徽章分类方法探究—数学建模

1、数学建模一周论文 论文题目：徽章分类方法探究 姓名1： 刘景庭 学号： 09312111 姓名2： 刘志猛 学号： 09312115 姓名3： 唐 丽 学号： 09312123 专 业： 自动化 班 级： 093121 指导教师： 乐励华 2011年 12月30日徽章分类方法探究摘要 本文所研究的实际问题是徽章分类问题。结合对参加会议的名单及得到徽章的标记等信息的了解，得知徽章的分类方法是由代表们的姓名的字母和得到的徽章来决定的。本文建立bp神经网络模型，运用matlab拟合数据，对徽章的分类方法问题进行探究与分析，针对各个问题，具体分析方法如下： 针对问题一：帮助参加会议的代表们找出徽章的分

2、类方法。为了探究其分类规律，先将名单中的人名进行分组：带“+”的人名分为一组，-带“-”的人名分为一组。然后通过建立3种不同数学模型，找出徽章的分类方法，对所给出的280个人名取特征值再将题目中的徽章0-1量化，假设徽章带“+”为1, 徽章带“-”则为0。模型1：按人名的第一个字母进行编号，a-z 分别对应 0-25，并将这些特征值带入到bp网络中去进行训练。模型2：按人名的第二个字母进行编号，a-z 分别对应 0-25，并将这些特征值带入到bp网络中去进行训练。模型3：将人名的前五个字母进行编号，a-z 分别对应 0-25，并将这些特征值带入到bp网络中去进行训练。 针对问题二：对分类方法进

3、行分析，如分类的理由、分类的正确与错误率等。通过对3种模型的相关数据进行比较分析各模型的分类的理由、正确性与错误率。据此来评价徽章分类方法的合理性。显然可以看出模型2的特征值的取法所得的bp算法对于所给的280个数据的正确率为100%, 可见模型2所对应的分类方法是可行的，分类方法是通对名字的第二个字母的元辅音进行分类,即第二个字母是元音为“+”,辅音为“-”。针对问题三：按照上述方法对没能参加此次会议的14名代表进行徽章分配。基于上述分析方法，用模型3分类方法对14个待分类人名进行分类得到的结果如下：11111110111111。将这个分类结果与上面我们通过matlab用bp算法得出的分类结

4、果一致, 证明所找的分类方法是最好的分类方法。关键词： bp神经网络模型 徽章分类方法 0-1量化 一、问题的重述在1994年的“机器学习与计算学习理论”的国际会议上，参加会议的280名代表都收到会议组织者发给的一枚徽章，徽章的标记为“”或“”（参加会议的名单及得到的徽章见附表）。会议的组织者声明：每位代表得到徽章“”或“”的标记只与他们的姓名有关，并希望代表们能够找出徽章“”与“”的分类方法。 对于参加会议代表们来说，解决徽章问题的分类方法十分迫切，所以本文就此问题需建立数学模型，并需给出了徽章的合理性分类方法。根据这些信息分析，我们需要解决以下三个问题：1. 请你帮助参加会议的代表找出徽章

5、的分类方法；2. 对你的分类方法进行分析，如分类的理由、分类的正确与错误率等；3. 由于客观原因，有14名代表没能参加此次会议。按照你的方法， 如果他们参加会议，他们将得到什么类型的徽章？ 附表1：参加会议的名单及得到的徽章（见附录7） 附表2：没能参加此次会议的名单（见附录8） 二、符号的假设（1）：连接权系数 （其中，） （2）：阀值（3）：初始步长（4） t：是学习次数；（5） t：总的迭代次数（6）：网络期望输出（7）：网络实际输出（8）：输入模式（9）：各单元的输出（10）：输出层的校正误差三、模型的假设 1假设题中所给人名和徽章的信息真实、有效；2. 假设徽章的

6、分配与参与会议代表们的职位无关； 3. 假设徽章“”或“”的标记只与姓名有关； 四、问题的分析问题一的分析： 问题要求对参加会议的代表找出徽章的分类方法。 首先将名单中的人名进行分组：带“+”的人名分为一组，-带“-”的人名分为一组。然后通过建立3种不同数学模型，依此数据，找出徽章的分类方法，对所给出的280个人名取特征值再将题目中的徽章0-1量化，假设徽章带“+”为1, 徽章带“-”则为0。模型1：按人名的第一个字母进行编号，a-z 分别对应 0-25，并将这些特征值带入到bp网络中去进行训练。模型2：按人名的第二个字母进行编号，a-z 分别对应 0-25，并将这些特征值带入到bp网络中去进

7、行训练。模型3：将人名的前五个字母进行编号，a-z 分别对应 0-25，并将这些特征值带入到bp网络中去进行训练。问题二的分析: 问题要求对分类方法进行分析，如分类的理由、分类的正确与错误率等问题。 通过对3种模型的相关数据进行比较分析各模型的分类的理由、正确性与错误率。据此来评价徽章分类方法的合理性。问题三的分析: 问题要求对通过对模型的了解和求解 ，按照上述方法对没能参加此次会议的14名代表进行徽章分配。根据题目要求，基于上述分析方法，用模型3分类方法对14个待分类人名进行分类。将这个分类结果与上面我们通过matlab用bp算法得出的分类结果进行比较, 找出最好的分类方法。五、模型的建立与

8、求解问题一：帮助参加会议的代表们找出徽章的分类方法。数学模型：bp神经网络模型bp（back propagation）网络是一种按误差逆传播算法训练的多层前馈网络，是目前应用最广泛的神经网络模型之一。bp网络能学习和存贮大量的输入-输出模式映射关系，而无需事前揭示描述这种映射关系的数学方程。它的学习规则是使用最速下降法，通过反向传播来不断调整网络的权值和阈值，使网络的误差平方和最小。bp神经网络模型拓扑结构如图所示： bp神经网络结构示意图模型的建立：人名按字母编号相应特征值的bp神经网络模型学习算法：(1) 根据相关数据,给各连接权系数，及阀值，赋予之间的随机值，其中，。 (2) 随机选取一

9、模式对，提供给网络。(3) 用输入模式,选取权系数及阀值计算出各单元的输出：其中，。(4) 用隐含层输出：(5) 用网络期望输出，网络实际输出计算输出层的校正误差数学表达式为： 。(6) 用，计算隐含层的校准误差：(7) 用，和计算下一次的隐含层和输出层之间新的连接值及神经元值：是初始步长；t是学习次数；t是总的迭代次数，m是一个正数，是一个动量系数，一般取0.9左右。(8) 用，和计算下一次的输入层和隐含层之间的新的连接权值及隐含神经元阀值：(9) 随机选下一个学习模式对提供给网络，返回到第(3)步训练，直至全部m个模式训练完。）(10) 重新从m个学习模式对随机选取一个模式对，返回到第(3

10、)步训练网络，直至满足学习要求。模型1：按人名的第一个字母进行编号，a-z 分别对应 0-25，并将这些特征值 带入到bp网络中去进行训练。模型1的解答： 按人名的第一个字母进行编号，a-z 分别对应 0-25，即每个人名的特征值是一个长度为1的一维列向量,总共280个人名就是个1*280的矩阵p，作为网络输入。将题目中的徽章问题量化，假设徽章为则为1, 徽章为则为0, 就形成一个1*280的矩阵t，作为目标输出。将这些特征值作为训练样本, 通过matlab的工具箱对bp分类算法进行训练，并确定权值，具体程序及结果(见附录1)。结论：从训练情况可以看出，在误差值比较大的时候训练就停止了，将输入

11、p带入训练后的矩阵，发现输出结果与t很不一致，说明这里找不到分类的规律。模型2：按人名的第一个字母进行编号，a-z 分别对应 0-25，并将这些特征值 带入到bp网络中去进行训练。模型2的解答： 按人名的第二个字母进行编号，a-z 分别对应 0-25，即每个人名的特征值是一个长度为1的一维列向量,总共280个人名就是个1*280的矩阵p，作为网络输入。将题目中的徽章问题量化，假设徽章为则为1, 徽章为则为0, 就形成一个1*280的矩阵t，作为目标输出。将这些特征值作为训练样本, 通过matlab的工具箱对bp分类算法进行训练，并确定权值，具体程序及结果(见附录2)。结论：训练后的bp神经网络

12、,输入参加训练的数据p,验证数据，可以看出，和所给人名所对应的徽章满足的很好。模型3：按人名的第一个字母进行编号，a-z 分别对应 0-25，并将这些特征值 带入到bp网络中去进行训练。模型3的解答： 按人名的前五个字母进行编号，a-z 分别对应 0-25，即每个人名的特征值是一个长度为5的一维列向量,总共280个人名就是个5*280的矩阵p，作为网络输入。将题目中的徽章问题量化，假设徽章为则为1, 徽章为则为0, 就形成一个5*280的矩阵t，作为目标输出。将这些特征值作为训练样本, 通过matlab的工具箱对bp分类算法进行训练，并确定权值，具体程序及结果(见附录3)。 结论：将用于训练的

13、输入数据p代入训练后的神经网络，将它和用于训练的目标输出矩阵t对比可以看出，吻合得不是很好。问题二：对分类方法进行分析，如分类的理由、分类的正确与错误率等。问题二的解答：分类理由：模型1：按人名的第一个字母进行编号。 模型2：按人名的第二个字母进行编号。 模型3：按人名的前五个字母进行编号。分类的正确性与错误率： 通过模型1,模型2和模型3的比较，可以看出模型2的特征值的取法所得的bp算法对于所给的280个数据的正确率为100%, 并且对于问题三14个待分类的人名计算得到的特征值从数据本身看来非0即1,可见模型2所对应的分类方法是可行正确的， 通过对第二个字母的元辅音进行分类,即第二个字母是元

14、音为,为辅音为,用此方法并对280个所给人名进行分类,结果与题目所给分类结果是一致的，可见按第二个字母的元辅音进行分类就是我们所要找徽章的分类方法。问题三：按照上述方法对没能参加此次会议的14名代表进行徽章分配。问题三的解答： 对于待分配的14位代表人名，先将其做同样的量化。用已训练完的bp神经网络对其进行分类，得到的结果（见附录4）。将14个待分类的人名的第一个字母编码输入神经网络：可以看出，发现输出结果与t很不一致，说明应用模型1找不到分类的规律。将14个待分类的人名的前五个字母编码输入神经网络：可以看出，这个结果不是很好, 由很多介于0和1之间的数字,从这里的分析可以看出,选取字母的编码

15、作为特征值是合理的，但需要对特征值的选取方案进行细化。 将14个待分类的人名的第二个字母元辅音编码分类方法进行徽章分类得到的结果如下：1 1 1 1 1 1 1 0 1 1 1 1 1 1 （所对应的人名顺序见附录5）可以看出，是呈0-1的分布，和与bp神经网络算法结果很接近，说明模型2的分类方法是可行的。6、 模型的检验对280个所给人名随机任意选取，将选取的名单(见附录5)运用模型2的分类方法重新将徽章进行分类，结果如下：01001 11010 10101 10100通过比对发现结果与题目所给的分配全部相同。通过检验，说明模型2的分类方法是符合科学的，具有可信度。七、模型的改进应考虑到数据

16、的局限性，为了使模型更具说服力，我们应收集更多的参加会议的名单，运用bp神经网络模型算法分析结果的正确性，再将结果与模型2分类方法进行核对，进一步验证徽章分类方法的合理性。另外应提高bp神经网络模型算法的学习速度，加快改善模型的精度。 八、模型的评价模型的优点：1. 本模型应用bp神经网络，得到的结果完全符合实际。2. 应用3种模型进行分析比对，更具说服力。3. 方案详尽明了，步骤清晰，易于理解。4. 模型具有很强的推广性及广阔的应用前景。 模型的缺点：1. 本模型从数学上看它归纳为非线性梯度优化问题，因此不可避免存在局部最小问题。2. 学习算法的收敛速度很慢，通常需要上千次迭代或更多。3.

17、网络隐含节点的个数尚无理论上的指导。 九、参考文献1 姜启源、谢金星、叶俊 数学模型（第三版） 高等教育出版社20032 罗万成 bp神经网络在分类与预测中的应用高等教育出版社20053 周继成，人工神经网络m.北京:科学普及出版社，19934 清华数模讲义数学建模案例分析高等教育出版社 20055 边馥萍，侯文华，梁冯珍数学建模方法与算法高等教育出版社 20046 胡良剑，孙晓君matlab数学实验高等教育出版社 20037 谭永基，蔡志杰，俞文数学模型案例复旦大学出版社 2005十、附 录附录1:按人名的第一个字母进行编号的程序及结果：>> net=newff(0 25,100

18、,1,'logsig','purelin','trainlm');>> net=train(net,p,t);trainlm, epoch 0/100, mse 36.4541/0, gradient 10111.3/1e-010trainlm, epoch 6/100, mse 0.115783/0, gradient 7.80296e-013/1e-010trainlm, minimum gradient reached, performance goal was not met.>> net.trainparam.m

19、in_grad= 1e-020;>> net=train(net,p,t);trainlm, epoch 0/100, mse 0.115783/0, gradient 7.80296e-013/1e-020trainlm, epoch 3/100, mse 0.115783/0, gradient 1.18794e-012/1e-020trainlm, maximum mu reached, performance goal was not met.附录2:按人名的第二个字母进行编号的程序及结果：>> net=newff(0 25,100,1,'logsig&

20、#39;,'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-020trainlm, epoch 7/100, mse 0.00352734/0, gradient 2.11219e-012/1e-020t

21、rainlm, maximum mu reached, performance goal was not met.>> a=sim(net,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附录3:按人名的前五个字母进行编号的程序及结果：>> net=newff(0 25;0 25;0 25;0 25;

22、0 25,100,1,'logsig','purelin','trainlm'); /创建一个神经网络，每个字母所对应的量化值的输入范围025，神经网络有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,

23、 gradient 4628.35/1e-020trainlm, epoch 25/100, mse 0.000969475/0, gradient 4.93588/1e-020trainlm, epoch 50/100, mse 6.16266e-005/0, gradient 4.48141/1e-020trainlm, epoch 72/100, mse 4.00219e-031/0, gradient 1.53435e-013/1e-020trainlm, maximum mu reached, performance goal was not met.输出结果为a矩阵a=sim(ne

24、t,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（后面数据略）附录4:将14个待分类的人名的第二个字母元辅音编码分类方法进行徽章分类的程序及结果:>> n=4 4 8 8 4 14 0 19 0 0 0 8 4 14 ; trainlm, epoch 0/100, mse 4.7

25、8695/0, gradient 4628.35/1e-020trainlm, epoch 25/100, mse 0.000969475/0, gradient 4.93588/1e-020trainlm, epoch 50/100, mse 6.16266e-005/0, gradient 4.48141/1e-020trainlm, epoch 72/100, mse 4.00219e-031/0, gradient 1.53435e-013/1e-020 >> a=sim(net,n) a = columns 1 through 8 1.0000 1.0000 1.0000

26、 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将14个待分类的人名的第二个字母元辅音编码分类方法进行徽章分类得到的结果如下：1 1 1 1 1 1 1 0 1 1 1 1 1 1 附录5:将14个待分类的人名的第二个字母元辅音编码分类方法进行徽章分类得到的结果所对应的人名顺序如下：merrick l. furst(1)jean gabriel ganascia(1) william gasarch(1)ricard gavalda(1)melin

27、da t. gervasio(1)yolanda gil(1)david gillman(1)attilio giordana(0)kate goelz(1)paul w. goldberg(1)sally goldman(1)diana gordon(1)geoffrey gordon(1) jonathan gratch(1)附录6:运用模型2的分类方法重新将徽章进行分类模型的检验随机任意选取的名单： - stuart russell + aurora perez - priscilla - r. bharat rao + dan roth + david pierce + leonard

28、 pitt - armand prieditis + roberto piola + lorien y. pratt + michael redmond - j. r. quinlan + john rachlin - efim kinber + joel ratsaby + foster j. provost - craig knoblock + vijay raghavan - jyrki kivinen - stefan kramer 附录7:附表1：参加会议的名单及得到的徽章+ naoki abe - myriam abramson + david w. aha+ kamal m. a

29、li - 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- shai ben-david + george berg + neil berkman+ malini bhandaru +

30、 bir bhanu + reinhard blasig- avrim blum - anselm blumer + justin boyan+ carla e. brodley + nader bshouty - wray buntine- andrey burago + tom bylander + bill byrne- claire cardie + richard a. caruana + john case+ jason catlett + nicolo cesa-bianchi - philip chan+ mark changizi + pang-chieh chen - zh

31、ixiang chen+ wan p. chiang - steve a. chien + jeffery clouse+ william cohen + david cohn - clare bates congdon- antoine cornuejols + mark w. craven + robert p. daley+ lindley darden - chris darken - bhaskar dasgupta- brian d. davidson + michael de la maza - olivier de vel- scott e. decatur + gerald

32、f. dejong + kan deng- thomas g. dietterich + michael j. donahue + george a. drastal+ harris drucker - chris drummond + hal duncan- thomas ellman + tapio elomaa + susan l. epstein+ bob evans - claudio facchinetti + tom fawcett- usama fayyad + aaron feigelson + nicolas fiechter+ david finton + john fi

33、scher + paul fischer+ seth flanders + lance fortnow - ameur foued+ judy a. franklin + yoav freund + johannes furnkranz+ leslie grate + william a. greene + russell greiner+ marko grobelnik + tal grossman + margo guertin+ tom hancock + earl s. harris jr. + david haussler+ matthias heger + lisa hellers

34、tein + david helmbold+ daniel hennessy + haym hirsh + jonathan hodgson+ robert c. holte + jiarong hong - chun-nan hsu+ kazushi ikeda + masayuki inaba - drago indjic+ nitin indurkhya + jeff jackson + sanjay jain+ wolfgang janko - klaus p. jantke + nathalie japkowicz+ george h. john + randolph jones +

35、 michael i. jordan+ leslie pack kaelbling + bala kalyanasundaram - thomas e. kammeyer- grigoris karakoulas + michael kearns + neela khan+ roni khardon + dennis f. kibler + jorg-uwe kietz- efim kinber - jyrki kivinen - emanuel knill- craig knoblock + ron kohavi + pascal koiran+ moshe koppel + daniel

36、kortenkamp + matevz kovacic- stefan kramer + martinch krikis + martin kummer- eyal kushilevitz - stephen kwek + wai lam+ ken lang - steffen lange + pat langley+ mary soon lee + wee sun lee + moshe leshno+ long-ji lin - charles x. ling + michael littman+ david loewenstern - phil long + wolfgang maass

37、- bruce a. macdonald + rich maclin - sridhar mahadevan- j. jeffrey mahoney + yishay mansour + mario marchand- shaul markovitch - oded maron + maja mataric+ david mathias + toshiyasu matsushima - stan matwin- eddy mayoraz - r. andrew mccallum - l. thorne mccarty- alexander m. meystel + michael a. mey

38、stel - steven minton+ nina mishra + tom m. mitchell + dunja mladenic+ david montgomery - andrew w. moore + johanne morin+ hiroshi motoda - stephen muggleton + patrick m. murphy- sreerama k. murthy + filippo neri - craig nevill-manning- andrew y. ng + nikolay nikolaev - steven w. norton+ joseph o'

39、;sullivan + dan oblinger + jong-hoon oh- arlindo oliveira + david w. opitz + sandra panizza+ barak a. pearlmutter - ed pednault + jing peng+ fernando pereira + aurora perez + bernhard pfahringer+ david pierce - krishnan pillaipakkamnatt + roberto piola+ leonard pitt + lorien y. pratt - armand priedi

40、tis+ foster j. provost - j. r. quinlan + john rachlin+ vijay raghavan - r. bharat rao - priscilla rasmussen+ joel ratsaby + michael redmond + patricia j. riddle+ lance riley + ronald l. rivest + huw roberts+ dana ron + robert s. roos + justinian rosca+ john r. rose + dan roth + james s. royer+ ronit

41、t rubinfeld - stuart russell + lorenza saitta+ yoshifumi sakai + william sakas + marcos salganicoff- steven salzberg - claude sammut + cullen schaffer+ robert schapire + mark schwabacher + michele sebag+ gary m. selzer + sebastian seung - arun sharma+ jude shavlik + daniel l. silver - glenn silverstein+ yoram singer + mona singh +