1、摘要本文是讨论 1994 年的“机器学习与计算学习理论”的国际会议上参加会议代表的名字与他所得的徽章的规则问题。对于问题一，为了找出名字与徽章的分类规则。首先，我们将 280 名代表按照名字首字母分类，找出每类中比较特殊的名字进行研究，假设关键属性。然后，我们将 280 名代表按照徽章“+”和“-”进行分类、统计，并根据关键属性找出分类规则。这里我们先采用名字的首字母进行分析，通过统计分析，我们发现首字母并不能完全反映我们所要研究的规则。我们继续对名字的第二个字母进行分析，这里我们通过 VC+编程得到统计结果。名字的第二个字母在 a,e,o,i,u范围内，则徽章的种类为“+” ，反之，徽章的种
2、类为“-”。对于问题二，我们根据问题一得出的规则，对参加会议的 280 名代表的名字代入求出正确率为 100%。对于问题三，我们根据问题一得出的规则，对未参加会议的 14 名代表进行了分类，最后只有 Attilio Giordana 的徽章为“-” ，其它代表的徽章都为“+” 。一、 问题的重述1.1 问题的背景 在 1994 年的“机器学习与计算学习理论”的国际会议上，参加会议的 280 名代表都收到会议组织者发给的一枚徽章，徽章的标记为“”或“” （参加会议的名单及得到的徽章见附表） 。会议的组织者声明：每位代表得到徽章“”或“”的标记只与他们的姓名有关，并希望代表们能够找出徽章“”与“”
3、的分类方法。1.2 问题：1. 请你帮助参加会议的代表找出徽章的分类方法；2. 对你的分类方法进行分析，如分类的理由、分类的正确与错误率等；3. 由于客观原因，有名代表（见附表）没能参加此次会议。按照你的方法，如果他们参加会议，他们将得到什么类型的徽章？二、 模型的假设1、 假设 280 名代表都是按照同一个发放徽章的标准分配徽章的；2、 假设 280 名代表的徽章都是发放无误的；3、 假设每个名字的首字母出现都是随机的；4、 假设徽章的分类与性别无关；5、 假设不会出现特殊的名字。三、符号说明 会议代表的名字（i=1,2，280） ；iname. 名字按首字母分类（i=1,2，26） ；ic
4、ls. 满足“+”徽章的字母范围；1R. 满足“-”徽章的字母范围；2 未参加会议的代表的名字（i=1,2，14） 。ip四、模型分析、建立与求解针对问题一：4.1、模型分析：问题研究的是名字与徽章的分类规则，英文名分为“First name”、 “Middle name”和“Last name”三个部分组成。因为 “Middle name”不是所有名字都有或者不止一个，所以，我们先不与考虑。这里我们重点研究“First name ”和“Last name” 。名字本身的属性大致有：首字母、元音字母（包括单元音和双元音） 、辅音字母。这里我们先对“First name”的字母进行研究。我们将名
5、字按照首字母进行分类，并对每个类中徽章“+”和 “-”分别统计，找出两种徽章数目相差较大的作为特殊数据类（见附录一） 。4.2、模型建立：根据附录一中的数据判断，我们发现首字母并不能完全反映我们所要研究的规则。我们继续对“First name”中的第二个字母进行研究。我们以 D 为例：D：（共 23 个）徽章为“+”的名字+ David W. Aha + Dana Angluin + David Cohn+ David Finton + David Haussler + David Helmbold+ Daniel Hennessy + Dennis F. Kibler + Darko Zup
6、anic+ Daniel Kortenkam + David Loewenstern + David Mathias+ Dunja Mladenic + David Montgomery + Dan Oblinger+ David W. Opitz + David Pierce + Dana Ron+ Dan Roth + Daniel L. Silver + David B. Skalak+ Donna Slonim徽章为“-”的名字：- Drago Indjic通过用 VC+软件编程（附录二）对名字的第二个字母进行统计，得：徽章“+” 徽章“-”a、e、o r统计结果不存在交叉同理，用 V
7、C+软件编程（附录三）对全部 26 个类得字母进行同样的统计，得：徽章“+” 徽章“-”a、e、o、i、u c、d、f、h、l、m、n、r、s、t、v、y、.统计结果不存在交叉所以，我们得出结论， “First name”中的第二个字母在a、e 、o、i 、u 范围内，即元音字母，则，徽章为“+” ，反之，不在范围内的，徽章为“-” 。4.3、模型求解：根据以上结论我们得到徽章“+”与名字的第二个字母的关系域为 1Ruioe1、aR徽章“-”与名字的第二个字母的关系域为 2 、 yvtsrnmlhfdc2用 与关系域 和 想与，得：iname1R结论一： ，发放“+”徽章；1Rnaei结论二：
8、 ，发放“-”徽章；2mi针对问题二：分类理由：由于英文名字的特性，分为“First name ”、 “Middle name”和“Last name”三个部分，其中“First name”和“Last name”最重要，所以，我们主要研究这两项。又由于名字本身的特性，分为首字母、元音字母、辅音字母、字长等，我们逐个考虑，最终得到以上结论。正确率：完全正确针对问题三：将 14 个未参加会议的代表的名字代入模型,得：+Merrick L. Furst +Jean Gabriel Ganascia +William Gasarch+Ricard Gavalda +Melinda T. Gervas
9、io +Yolanda Gil+David Gillman -Attilio Giordana +Kate Goelz+Paul W. Goldberg +Sally Goldman +Diana Gordon+Geoffrey Gordon +Jonathan Gratch五、模型检验将参加会议的全部代表代入模型,结果 中满足结论一的名字全部得到“+”徽章；iname满足结论二的名字全部得到“-”徽章。模型检验无误。六、模型评价及改进6.1、模型优点：该模型采用统计法，找出规则，思路简单易懂，规律性很强。6.2、模型缺点：该模型针对的数据量太小，且考虑了“First name”的影响，并找出
10、了结果， 280 个名字的第二个字母并没有包含全部的 26 个字母，模型统一的对没在a,e,o,i,u范围内的名字都发放“-”徽章，结果存在一定的偶然性。6.3、模型改进：模型可以加入对“Middle name”和“Last name”的研究，找出更具体，能针对所有名字发放徽章。模型还应考虑对年龄、性别、国籍等因素的考虑，让模型更具体。七、参考文献1第三届数学建模论文集（网址：http:/ ；2华大学数学建模蒲俊老师上课课件；3静等的数学建模与数学实验（第三版） 。附录附录一：（按首字母数据统计表）：属性 首字母出线 “+”次数 “-”次数 特例(1 表示)字母 次数A 14 2 12 1B
11、11 6 5C 16 3 13 1D 23 22 1 1E 8 1 7 1F 4 3 1G 8 6 2H 8 8 0 1I 1 0 1J 30 27 3 1K 9 7 2L 13 11 2 1M 32 31 1 1N 10 10 0 1O 2 0 2P 13 9 4Q 0 0 0R 19 17 2 1S 24 8 16T 16 10 6U 1 0 1V 2 2 0W 10 9 1 1X 1 1 0Y 4 4 0 1Z 1 0 1总数 280 197 87附录二：#include#includeusing namespace std;void main()char name2220=“David
12、 W. Aha“ , “Dana Angluin“,“David Cohn“ ,“David Finton“,“David Haussler“, “David Helmbold“,“Daniel Hennessy“ , “Dennis F. Kibler“ , “Daniel Kortenkam“,“David Loewenstern“ , “David Mathias“, “Dunja Mladenic“,“David Montgomery“ , “Dan Oblinger“ , “David W. Opitz“,“David Pierce“ , “Dana Ron“ , “Dan Roth
13、“ ,“Daniel L. Silver“ , “David B. Skalak“ , “Donna Slonim“,“Darko Zupanic“;for(int i=0;i#includeusing namespace std;void main()char name19730= /“+”和“- ”的数据分开输入“Aaron Feigelson“, “Aurora Perez“,“Bir Bhanu“,“Bill Byrne“,“Bob Evans“,“Bala Kalyanasundaram“,“Barak A. Pearlmutter“, “Bernhard Pfahringer“,“
14、Carla E. Brodley“,“Carl H. Smith“,“Cullen Schaffer“,“David W. Aha“,“Dana Angluin“,“David Cohn“,“David Finton“,“David Haussler“,“David Helmbold“,“Daniel Hennessy“,“Dennis F. Kibler“,“Daniel Kortenkam“,“David Loewenstern“,“David Mathias“,“Dunja Mladenic“,“David Montgomery“,“Dan Oblinger“,“David W. Opi
15、tz“,“David Pierce“,“Dana Ron“,“Dan Roth“,“Daniel L. Silver“,“David B. Skalak“,“Donna Slonim“,“Darko Zupanic“,“Earl S. Harris Jr.“,“Filippo Neri“,“Fernando Pereira“,“Foster J. Provost“,“George Berg“,“Gerald F. DeJong“,“George A. Drastal“,“George H. John“,“Gary M. Selzer“,“Gary Weiss“,“Haralabos Athan
16、assiou“, “Harris Drucker“,“Hal Duncan“,“Haym Hirsh“,“Hiroshi Motoda“,“Huw Roberts“,“Hiroshi Tanaka“,“Holly Yanco“,“Javed Aslam“,“Jose L. Balcazar“, “Justin Boyan“,“John Case“,“Jason Catlett“,“Jeffery Clouse“,“John Fischer“,“Judy A. Franklin“, “Johannes Furnkranz“,“Jonathan Hodgson“, “Jiarong Hong“,“
17、Jeff Jackson“,“Jorg-Uwe Kietz“,“Johanne Morin“,“Joseph OSullivan“,“Jong-Hoon Oh“,“Jing Peng“,“John Rachlin“,“Joel Ratsaby“,“Justinian Rosca“,“John R. Rose“,“James S. Royer“,“Jude Shavlik“,“Joe Suzuki“,“Janusz Wnek“, “John M. Zelle“,“Jean-Daniel Zucker“,“Kamal M. Ali“,“Kan Deng“, “Kazushi Ikeda“,“Ken
18、 Lang“,“Kimmen Sjolander“,“Karsten Verbeurgt“,“Kenji Yamanishi“,“Lars Asker“,“Lindley Darden“,“Lance Fortnow“,“Leslie Grate“,“Lisa Hellerstein“,“Leslie Pack Kaelbling“,“Long-Ji Lin“,“Leonard Pitt“,“Lorien Y. Pratt“,“Lance Riley“,“Lorenza Saitta“,“Minoru Asada“,“Michael W. Barley“,“Malini Bhandaru“,“
19、Mark Changizi“,“Mark W. Craven“,“Michael de la Maza“,“Michael J. Donahue“,“Marko Grobelnik“,“Margo Guertin“,“Matthias Heger“,“Masayuki Inaba“,“Michael I. Jordan“,“Michael Kearns“, “Moshe Koppel“,“Matevz Kovacic“, “Martinch Krikis“, “Martin Kummer“,“Mary Soon Lee“, “Moshe Leshno“,“Michael Littman“,“M
20、ario Marchand“, “Maja Mataric“,“Michael A. Meystel“,“Michael Redmond“,“Marcos Salganicoff“,“Mark Schwabacher“,“Michele Sebag“,“Mona Singh“,“Mark Staley“,“Mandayam T. Suraj“,“Manfred Warmuth“,“Neil Berkman“,“Nader Bshouty“,“Nicolo Cesa-Bianchi“,“Nicolas Fiechter“,“Nitin Indurkhya“,“Nathalie Japkowicz
21、“,“Nina Mishra“,“Nikolay Nikolaev“,“Naoki Abe“,“Neela Khan“,“Peter Bartlett“,“Pang-Chieh Chen“,“Paul Fischer“,“Pascal Koiran“,“Pat Langley“,“Patrick M. Murphy“,“Patricia J. Riddle“,“Paul Utgoff“, “Paul Vitanyi“,“Reinhard Blasig“,“Richard A. Caruana“,“Robert P. Daley“,“Russell Greiner“,“Robert C. Hol
22、te“,“Randolph Jones“,“Roni Khardon“,“Ron Kohavi“,“Rich Maclin“,“Ronald L. Rivest“,“Robert S. Roos“,“Ronitt Rubinfeld“,“Robert Schapire“,“Robert Sloan“,“Richard S. Sutton“,“Robert Williamson“,“Roberto Piola“,“Susan L. Epstein“, “Seth Flanders“,“Sanjay Jain“,“Sandra Panizza“,“Sebastian Seung“,Satinder
23、 Pal Singh“,“Sean Slattery“,“Sonya Snedecor“,“Timothy P. Barber“,“Tom Bylander“,“Tapio Elomaa“,“Tom Fawcett“,“Tal Grossman“,“Tom Hancock“,“Toshiyasu Matsushima“,“Tom M. Mitchell“,“Tatsuo Unemi“,“Takefumi Yamazaki“,“Vijay Raghavan“,“Von-Wun Soo“,“Welton Becket“,“Wan P. Chiang“,“William Cohen“,“William A. Greene“,“Wolfgang Janko“,“William Sakas“,“Wai Lam“,“Wolfgang Maass“,“Wee Sun Lee“,“Xuemei Wang“,“Yoav Freund“,“Yishay Mansour“,“Yoshifumi Sakai“Yoram Singer“,;for(int i=0;i196;i+)coutnamei1“ “;
