- 38 - http://xb.szpt.edu.cn 历届全国大学生数学建模竞赛专科组 试题的最优分类 * 王积建 1 ,陈笑缘 2 ,茹永梅 1 (1.浙江工贸职业技术学院, 浙江 温州 325027;2.浙江商业职业技术学院, 浙江 杭州 310053) 摘要:从质量角度对历届(1992~2010)全国大学生数学建模竞赛专科组试题进行综合评价,在模糊综 合评价结果的基础上,使用费歇尔最优分割法对这 24 个赛题进行了分类.如果分为 5 类,那么按照质量从高 到低排列依次为: {2010D,2008C,2006C,2004C,1999D} 、 {2009C,2001D} ; {2010C,2008D,2005D, 2004D,2003C,2002C} ; {2009D,2007C,2007D,2005C,2001C,1999C} ; {2006D,2003D,2002D,2000C, 2000D} . 关键词:CUMCM;试题;最优分割法;聚类分析 中图分类号:O29 文献标志码:B 文章编号:1672-0318(2013)01-0038-06 截止 2011 年, 全国大学生数学建模竞赛已成 功举办了 20 年.由于赛题质量是竞赛成功举办 的关键因素之一,所以通过对赛题质量进行综合 评价和分析,筛选出优质赛题,提炼出影响赛题 质量的指标体系,对于指导今后的命题工作具有 十分重要的意义. 针对全国大学生数学建模竞赛试题质量的综 合评价问题, 在过去 20 年间从来没有研究过.本 课题组受全国大学生数学建模竞赛组委会委托, 对专科组的 24 个赛题进行了质量评价. 首先建立 了综合评价指标体系,然后通过向有关专家和竞 赛指导老师、参赛学生发放问卷,获得评价指标 的相对重要性数据和赛题质量分数.最后通过建 立综合评价模型, 得到了 24 个赛题的综合评价值 及其排序.但由于这些排序结果并不能直接显示 哪些赛题属于"优",哪些赛题属于"良",也 就无法将这些赛题进行恰当地归类,因而无法概 括提取优质赛题的特征. 鉴于此, 本文在综合评 价的基础上,使用费歇尔(Fisher)最优分割法对 这些赛题进行最优分类,为总结提炼优质赛题的 特征做准备. 1 费歇尔最优分割法简介[1-4] 设有序样品依次为 1 2 , ,..., n X X X ( i X 为m 维 向量) . 1)定义类直径.设某一类 G 包含的样品有 { } 1 , ,..., i i j X X X + (i j < ) , 记为 { } = , 1,..., G i i j + . 该 类的均值向量 G X 为: 1 = 1 j G t t i X X j i = - + ? (1) 用(,)Dij表示这一类的直径,常用的直径有: ( ) ( ) ( , )= j t G t G t i D i j X X X X = ? - - ? (2) 当1m=时,也可以定义直径为: ( , )= j t G t i D i j X X = - ? % (3) 其中 G X % 是该类数据的均值、中位数或众数. 收稿日期:2012-04-10 *项目来源:全国大学生数学建模竞赛组委会委托课题《全国大学生数学建模竞赛赛题综合评价》 作者简介:王积建(1966-) ,男,甘肃景泰人,副教授,硕士,从事数学建模和数学教育研究. 深圳职业技术学院学报 2013 年第 1 期No.1, 2013 http://xb.szpt.edu.cn 深圳职业技术学院学报 2013,12(1) - 39 - 2) 定义分类的损失函数. 用(,)bnk表示将n 个有序样品分为 k 类的某一种分法.常记分法 ( , ) b n k 为: { } { } 1 1 1 2 2 2 2 3 , 1,..., 1 , , 1,..., 1 ,..., , 1,..., G i i i G i i i G i i n { } 1,..., 1 ,..., , 1,..., k k k i G i i n 4) 其中, 分点为 1 2 1 1= ... 1 k k i i i n i + 定义上述分类法的损失函数为 [ ] 1 1 1) k t t t L b n k D i i + = = - ? (5) 当,nk固定时, [ ] ( , ) L b n k 越小,表明各类 的离差平方和越小,分类越合理.因此要寻找一 种分法 ( , ) b n k ,使得分类损失函数 [ ] ( , ) L b n k 达 到最小,记*(,)bnk是使得(5)式达到最小的分 类法. 3) [ ] ( , ) L b n k 的递推公式为 { } { } * 2 * * ( ,2) = min (1, 1) ( , ) = min ( 1, 1) j n k j n L b n D j D j n L b n k L b j k D j n ? ? ? ? ? ? ? í é ù é ù - - + ? (6) 4)最优解的求法.首先找分点 k j ,使得(6) 式达到极小,即**1, 1) ( , ) k k L b n k L b j k D j n é ù é ù - - + 于是得到第k 类{},1,..., k k k G j j n = + . 然后找分点 1 k j - ,使它满足 * * 1 1 ( 1, 1) = ( 1, 2) ( , 1) k k k k L b j k L b j k D j j - - é ù é ù 于是得到第 1 k - 类{}111,1,..., 1 k k k k G j j j - - - = + - . 类似地,可以得到所有类 1 2 , ,..., k G G G ,这 就是最优解,即{}*12kbnkGGG.5)分类数k 的确定方法 分类数 k 可以通过 * ( , ) L b n k é ù ? ? 与k的关 系曲线图求得,曲线拐弯处的k 值即为最优分割 数[5] .当曲线拐弯很平缓时,可以选取的k 很多, 这时可以使用均方比[6] 来确定. 2 应用实例 2.1 分类对象 以历届全国大学生数学建模竞赛 (CUMCM) 专科组试题为分类对象. 选取了从 1999 年专科组 独立于本科组竞赛以来,截止 2010 年的 12 年的 C、D 题,一共 24 个赛题,以X1~X24 表示. 计算出 24 个赛题的综合评价值, 并按照综合评 价值从大到小排序, 结果如表 1 的第 3、 4 列所示. 综 合评价值越大,表示赛题质量越好. 为了使用最优分割法对这些赛题进行有序分 类,将所有赛题按照综合评价值从大到小的顺序重 新排列,形成有序样品 B1~B24,见表 2.排序靠 前的赛题质量较好. 2.2 分类过程和结果 1)计算直径.由于样品指标的维数 1 m = ,所 以使用(3)式计算直径,其中 G X % 是该类样品评价 值的均值,按照(1)式直径的计算结果见表 3(使用MATLAB 软件编程计算) . 2)计算最小分类损失函数 * ( , ) L b l k é ù ? ? ,及其 相对应的分点, 3 24 l ? ? , 2 23 k ? ? .计算结 果见表 4 和表 5. 3) 确定k .做*(24, ) L b k é ù ? ? 随k变化的趋势图, 如图 1 所示.从图 1 可以看出,当=7 k 时,曲线开 始变得平缓,所以分为 7 类为好. 4)确定最优分类.将24 个赛题分为 7 类,结果 见表 6. 总之,将24 个赛题分为 7 类的结果为:{ } 1 B , { } 2 3 5 , ,...., B B B , { } 6 7 , B B , { } 8 9 12 , ,..., B B B , { } 13 14 17 , ,..., B B B ,{ } 18 19 21 , ..., B B B , ,{ } 22 23 24 , , B B B . 考虑到本文的研究目的是将这些 24 个赛题的 质量分出等级,以便于能对今后的命题具有指导意 义. 若划分过细, 则不利于提炼类特征. 因此, 将其 划分为 5 个等级,即优、较优、中、较差、差这 5 个等级;或者划分为 3 个等级,即优、中、差这 3 个等级. 分为 5 类的结果为: { } 1 2 5 , ..., B B B , , { } 6 7 , B B , { } 8 9 13 , ..., B B B , ,{ } 14 15 19 , ..., B B B , ,{ } 20 21 24 , ,..., B B B . 分为3类的结果为:{}127,..., B B B , , { } 8 9 17 , ..., B B B , ,{ } 18 19 24 , ..., B B B , . 以上 3 种分类结果汇总见表 2,将其分类结果 标示在原赛题上,结果见表 1 的第 6、7、8 列. - 40 - http://xb.szpt.edu.cn 深圳职业技术学院学报 2013,12(1) 表1所有 24 个赛题的综合评价结果及排序 序号 赛题 综合评价值 排名 赛题题目 分7类分5类分3类1X1 0.1851 11 输油管的布置 4 3 2 2 X2 0.2037 1 对学生宿舍设计方案的评价 1 1 1 3 X3 0.1920 7 卫星和飞船的跟踪测控 3 2 1 4 X4 0.1785 19 会议筹备 6 4 3 5 X5 0.1981 4 地面搜索 2 1 1 6 X6 0.1866 10 NBA 赛程的分析与评价 4 3 2 7 X7 0.1817 15 手机"套餐"优惠几何 5 4 2 8 X8 0.1811 16 体能测试时间安排 5 4 2 9 X9 0.1987 3 易拉罐形状和尺寸的最优设计 2 1 1 10 X10 0.1715 22 煤矿瓦斯和煤尘的监测与控制 7 5 3 11 X11 0.1805 17 雨量预报方法的评价 5 4 2 12 X12 0.1846 12 DVD 在线租赁 4 3 2 13 X13 0.1999 2 饮酒驾车 2 1 1 14 X14 0.1870 9 公务员招聘 4 3 2 15 X15 0.1835 13 SARS 的传播 5 3 2 16 X16 0.1702 24 抢渡长江 7 5 3 17 X17 0.1881 8 车灯线光源的计算 4 3 2 18 X18 0.1762 20 赛程安排 6 5 3 19 X19 0.1825 14 基金使用计划 5 4 2 20 X20 0.1944 6 公交车调度 3 2 1 21 X21 0.1705 23 飞越北极 7 5 3 22 X22 0.1751 21 空洞探测 6 5 3 23 X23 0.1787 18 煤矸石堆积 6 4 3 24 X24 0.1975 5 钻井布局 2 1 1 表2有序样品及其综合评价值 排名 1 2 3 4 5 6 7 8 9 10 11 12 有序样品 B1 B2 B3 B4 B5 B6 B7 B8 B9 B10 B11 B12 综合评价值 0.2037 0.1999 0.1987 0.1981 0.1975 0.1944 0.1920 0.1881 0.1870 0.1866 0.1851 0.1846 分7类122223344444分5类111112233333分3类111111122222排名 13 14 15 16 17 18 19 20 21 22 23 24 有序样品 B13 B14 B15 B16 B17 B18 B19 B20 B21 B22 B23 B24 综合评价值 0.1835 0.1825 0.1817 0.1811 0.1805 0.1787 0.1785 0.1762 0.1751 0.1715 0.1705 0.1702 分7类555556666777分5类344444455555分3类222223333333http://xb.szpt.edu.cn 深圳职业技术学院学报 2013,12(1) - 41 - 表3直径 D(i , j)的计算结果(乘以 10000) j i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 1 0 0.072 0.136 0.190 0.244 0.467 0.854 1.670 2.481 3.192 4.012 4.777 5.606 6.488 7.394 8.293 9.19310.337 11.401 12.847 14.412 16.798 19.274 21.634 2 0 0.007 0.017 0.031 0.169 0.442 1.086 1.722 2.272 2.920 3.523 4.185 4.898 5.636 6.372 7.113 8.079 8.97410.225 11.591 13.731 15.959 18.077 3 0 0.002 0.007 0.110 0.324 0.863 1.384 1.824 2.351 2.836 3.376 3.964 4.576 5.188 5.806 6.633 7.396 8.493 9.69811.636 13.658 15.576 4 0 0.002 0.079 0.242 0.680 1.091 1.426 1.837 2.213 2.638 3.108 3.602 4.097 4.600 5.296 5.936 6.885 7.937 9.68111.504 13.229 5 0 0.048 0.152 0.472 0.760 0.986 1.277 1.542 1.853 2.205 2.581 2.961 3.352 3.919 4.437 5.239 6.139 7.686 9.30910.841 6 0 0.029 0.202 0.354 0.468 0.638 0.794 0.992 1.229 1.491 1.761 2.043 2.482 2.882 3.539 4.287 5.637 7.059 8.398 7 0 0.076 0.138 0.182 0.271 0.354 0.474 0.628 0.806 0.995 1.197 1.537 1.846 2.388 3.014 4.200 5.454 6.631 8 0 0.006 0.012 0.046 0.081 0.146 0.240 0.356 0.484 0.625 0.888 1.124 1.571 2.097 3.143 4.252 5.290 9 0 0.001 0.020 0.040 0.083 0.151 0.238 0.335 0.445 0.663 0.858 1.246 1.707 2.659 3.668 4.607 10 0 0.011 0.022 0.050 0.098 0.161 0.233 0.317 0.497 0.655 0.991 1.394 2.258 3.174 4.020 11 0 0.001 0.013 0.040 0.080 0.127 0.184 0.325 0.448 0.730 1.073 1.846 2.664 3.415 12 0 0.006 0.022 0.047 0.078 0.118 0.230 0.325 0.565 0.858 1.553 2.286 2.953 13 0 0.005 0.016 0.032 0.056 0.139 0.208 0.403 0.647 1.260 1.906 2.488 14 0 0.003 0.010 0.022 0.082 0.130 0.289 0.489 1.028 1.593 2.095 15 0 0.002 0.007 0.050 0.082 0.209 0.371 0.841 1.330 1.757 16 0 0.002 0.031 0.050 0.148 0.275 0.677 1.090 1.445 17 0 0.016 0.024 0.093 0.184 0.515 0.850 1.130 18 0 0.000 0.039 0.093 0.346 0.598 0.803 19 0 0.026 0.060 0.255 0.442 0.586 20 0 0.006 0.121 0.227 0.305 21 0 0.065 0.117 0.152 22 0 0.005 0.009 23 0 0.000 24 0 表4最小分类损失函数 L[b* (l , k)]的计算结果(乘以 10000) k l 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 3 0.007 4 0.017 0.002 5 0.031 0.007 0.002 6 0.169 0.031 0.007 0.002 7 0.272 0.060 0.031 0.007 0.002 8 0.446 0.234 0.060 0.031 0.007 0.002 9 0.598 0.279 0.066 0.038 0.013 0.007 0.002 10 0.650 0.285 0.072 0.044 0.019 0.008 0.003 0.001 11 0.738 0.319 0.106 0.072 0.044 0.019 0.008 0.003 0.001 12 0.821 0.354 0.142 0.074 0.045 0.021 0.009 0.004 0.002 0.001 13 0.941 0.418 0.206 0.086 0.057 0.033 0.021 0.009 0.004 0.002 0.001 14 1.094 0.513 0.300 0.113 0.079 0.050 0.026 0.014 0.009 0.004 0.002 0.001 15 1.210 0.629 0.365 0.152 0.089 0.060 0.036 0.024 0.012 0.007 0.004 0.002 0.001 16 1.338 0.756 0.386 0.174 0.096 0.067 0.043 0.027 0.016 0.011 0.006 0.004 0.002 0.001 17 1.479 0.834 0.409 0.197 0.108 0.079 0.055 0.033 0.021 0.014 0.009 0.006 0.004 0.002 0.001 18 1.742 0.960 0.493 0.281 0.163 0.108 0.079 0.055 0.033 0.021 0.014 0.009 0.006 0.004 0.002 0.001 19 1.978 1.029 0.549 0.337 0.195 0.108 0.079 0.055 0.033 0.022 0.014 0.009 0.006 0.004 0.002 0.001 0.000 20 2.425 1.225 0.707 0.448 0.236 0.146 0.108 0.079 0.055 0.033 0.022 0.014 0.009 0.006 0.004 0.002 0.001 0.000 21 2.951 1.430 0.884 0.503 0.291 0.201 0.114 0.085 0.061 0.039 0.028 0.020 0.014 0.009 0.006 0.004 0.002 0.001 0.000 22 3.997 1.826 1.150 0.670 0.457 0.291 0.201 0.114 0.085 0.061 0.039 0.028 0.020 0.014 0.009 0.006 0.004 0.002 0.001 0.000 23 5.106 2.078 1.256 0.776 0.508 0.296 0.206 0.119 0.090 0.066 0.044 0.033 0.025 0.019 0.014 0.009 0.006 0.004 0.002 0.001 0.000 24 6.144 2.282 1.334 0.854 0.512 0.300 0.210 0.123 0.094 0.070 0.048 0.037 0.028 0.021 0.015 0.010 0.006 0.005 0.003 0.001 0.001 0.000 - 42 - http://xb.szpt.edu.cn 深圳职业技术学院学报 2013,12(1) 表5与最小分类损失函数 L[b* (l , k)]相对应的分点 k l 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 3 2 4 2 3 5 2 3 5 6 2 6 6 6 7 6 6 7 7 7 8 6 6 8 8 8 8 9 6 8 8 8 8 9 9 10 7 8 8 8 8 9 9 9 11 7 8 8 11 11 11 11 11 11 12 7 8 8 11 11 11 11 11 11 12 13 7 8 8 11 11 11 13 13 13 13 13 14 8 8 8 11 13 13 13 13 13 14 14 14 15 8 8 11 11 14 14 14 14 14 14 15 15 15 16 8 8 13 13 14 14 14 15 15 15 15 16 16 16 17 8 11 13 13 14 14 14 15 15 16 16 17 17 17 17 18 8 13 13 13 15 18 18 18 18 18 18 18 18 18 18 18 19 8 13 14 14 15 18 18 18 18 18 18 18 18 18 18 18 18 20 8 13 14 18 18 18 20 20 20 20 20 20 20 20 20 20 20 20 21 8 14 15 18 18 18 20 20 20 20 20 20 21 21 21 21 21 21 21 22 8 18 20 20 20 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 23 8 18 20 20 22 22 22 22 22 22 22 22 22 22 22 23 23 23 23 23 23 24 8 18 20 20 22 22 22 22 22 22 22 22 23 23 23 23 23 23 23 23 23 24 0 5 10 15 20 25 0 1 2 3 4 5 6 7 分类数 损失 函数 值图1损失函数 L[b * (n , k)] (乘以 10000)随k变化的趋势 表6将24 个赛题分为 7 类的分类结果 赛题 个数 类数损失函数 L 值(/10000) 分点 j 值 分类结果 24 7 0.300 22 {B22~B24} 21 6 0.291 18 {B18~B21} 17 5 0.197 13 {B13~B17} 12 4 0.142 8 {B8~B12} 7 3 0.060 6 {B6~B7} 5 2 0.031 2 {B2~B5} 1 1 - - {B1} 2.3 分类结果检验 以划分 7 类为例. 令1,1,2,...,23 i i i B B y x x i + = - = , 其中 i B x 表示有序样品 i B 的综合评价值, i y 表示有 序样品 i B 与1iB+的综合评价值的一阶差分值.将1,2,...,23 i y i = ( ) 用图形表示出来, 如图 2 所示 (横 坐标表示 B1~B23,纵坐标表示一阶差分值 i y ) . 从图 2 可以看出, 1 B 与2B差距很大, 5 B 与6B差距很大, 6 B 与7B差距很大, 7 B 与8B差距很大, 10 B 与11 B 差距很大, 12 B 与13 B 差距很大, 17 B 与18 B 差距很大, 19 B 与20 B 差距很大, 21 B 与22 B 差 距很大,故他们每之间应当成为分界点,这样一来 就要分为 9 类. 由于分类数的限制, 必须减少 2 类. 将B1~B24 的综合评价值用图形表示出来,如图3所示(横坐标表示 B1~B24,纵坐标表示综合 评价值) . 从图 3 可以看出, 在6B与7B,10 B 与11 B , 19 B 与20 B 这三者的落差中, 5 B 与8B之间的落差最大, 这里必须截断,否则类内离差平方和必然增大,故将67,BB合并为一类可以达到截断的目的.而10 B 与11 B 、 19 B 与20 B 可以融入所在类别之中,恰好分 为7类. http://xb.szpt.edu.cn 深圳职业技术学院学报 2013,12(1) - 43 - 0.0000 0.0010 0.0020 0.0030 0.0040 0.0050 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 图2B1~B23 的一阶差分值 0.15 0.16 0.17 0.18 0.19 0.20 0.21 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 图3B1~B24 的综合评价值的变化趋势 综上所述,最优分割法得到的分类结果是符 合实际的. 参考文献: [1] 方开泰. 有序样品的一些聚类方法[J]. 应用数学学 报,1982,5(1) :94-101. [2] 高惠璇.应用多元统计分析[M].北京:北京大学出 版社,2005:253-255. [3] 张世英,黄违洪.最优分割法的适用性及一类有序 样品的聚类方法[J]. 应用数学学报, 1987, 10 (2) : 138-144. [4] 王鹤春,王家斌.基于主成分分析与最优分割理论对 实习成绩综合评定的研究与分析[J]. 数学的实践与认 识,2009,39(12) :21-26. [5] 彭志行,鲍昌俊,赵杨,等.加权马尔可夫链在传染 病发病情况预测分析中的应用[J].数学的实践与认 识,2009,39(27) :92-99. [6] 赵欣,邹良超,倪林.基于有序聚类的模糊加权马尔 可夫模型在降雨预测中的应用[J].江西农业学报, 2009,21(2) :110-113. Optimal Classification of Test Questions in National Mathematical Modeling Contests for College Students WANG Jijian1 , CHEN Xiaoyuan2 , RU Yongmei1 (1. Zhejiang Industrial&Trade Polytechnic, Wenzhou, Zhejiang 325003, China; 2. Zhejiang Vocational College of Commerce, Hangzhou, Zhejiang 310053, China) Abstract: In order to conduct a comprehensive evaluation of the previous (1992~2010) test questions in national mathematical modeling contests for college students in terms of quality, Fisher's optimal segmentation was adopted to classify these 24 test questions on the basis of fuzzy comprehensive evaluation. When classified into 5 categories, the order of their qualities is{2010D, 2008C, 2006C,2004C,1999D};{2009C,2001D}, {2010C,2008D,2005D,2004D,2003C,2002C};{2009D,2007C,2007D,2005C,2001C,1999C}; {2006D,2003D,2002D,2000C,2000D}. Key words: CUMCM; test questions; optimal segmentation; cluster analysis
下载该文档
文档格式：PDF
更新时间：2014-09-06
下载次数：0
点击次数：1
- 38 - http://xb.szpt.edu.cn 历届全国大学生数学建模竞赛专科组 试题的最优分类 * 王积建 1 ,陈笑缘 2 ,茹永梅 1 (1.浙江工贸职业技术学院, 浙江 温州 325027;2.浙江商业职业技术学院, 浙江 杭州 310053) 摘要:从质量角度对历届(1992~2010)全国大学生数学建模竞赛专科组试题进行综合评价,在模糊综 合评价结果的基础上,使用费歇尔最优分割法对这 24 个赛题进行了分类.如果分为 5 类,那么按照质量从高 到低排列依次为: {2010D,2008C,2006C,2004C,1999D} 、 {2009C,2001D} ; {2010C,2008D,2005D, 2004D,2003C,2002C} ; {2009D,2007C,2007D,2005C,2001C,1999C} ; {2006D,2003D,2002D,2000C, 2000D} . 关键词:CUMCM;试题;最优分割法;聚类分析 中图分类号:O29 文献标志码:B 文章编号:1672-0318(2013)01-0038-06 截止 2011 年, 全国大学生数学建模竞赛已成 功举办了 20 年.由于赛题质量是竞赛成功举办 的关键因素之一,所以通过对赛题质量进行综合 评价和分析,筛选出优质赛题,提炼出影响赛题 质量的指标体系,对于指导今后的命题工作具有 十分重要的意义. 针对全国大学生数学建模竞赛试题质量的综 合评价问题, 在过去 20 年间从来没有研究过.本 课题组受全国大学生数学建模竞赛组委会委托, 对专科组的 24 个赛题进行了质量评价. 首先建立 了综合评价指标体系,然后通过向有关专家和竞 赛指导老师、参赛学生发放问卷,获得评价指标 的相对重要性数据和赛题质量分数.最后通过建 立综合评价模型, 得到了 24 个赛题的综合评价值 及其排序.但由于这些排序结果并不能直接显示 哪些赛题属于"优",哪些赛题属于"良",也 就无法将这些赛题进行恰当地归类,因而无法概 括提取优质赛题的特征. 鉴于此, 本文在综合评 价的基础上,使用费歇尔(Fisher)最优分割法对 这些赛题进行最优分类,为总结提炼优质赛题的 特征做准备. 1 费歇尔最优分割法简介[1-4] 设有序样品依次为 1 2 , ,..., n X X X ( i X 为m 维 向量) . 1)定义类直径.设某一类 G 包含的样品有 { } 1 , ,..., i i j X X X + (i j < ) , 记为 { } = , 1,..., G i i j + . 该 类的均值向量 G X 为: 1 = 1 j G t t i X X j i = - + ? (1) 用(,)Dij表示这一类的直径,常用的直径有: ( ) ( ) ( , )= j t G t G t i D i j X X X X = ? - - ? (2) 当1m=时,也可以定义直径为: ( , )= j t G t i D i j X X = - ? % (3) 其中 G X % 是该类数据的均值、中位数或众数. 收稿日期:2012-04-10 *项目来源:全国大学生数学建模竞赛组委会委托课题《全国大学生数学建模竞赛赛题综合评价》 作者简介:王积建(1966-) ,男,甘肃景泰人,副教授,硕士,从事数学建模和数学教育研究. 深圳职业技术学院学报 2013 年第 1 期No.1, 2013 http://xb.szpt.edu.cn 深圳职业技术学院学报 2013,12(1) - 39 - 2) 定义分类的损失函数. 用(,)bnk表示将n 个有序样品分为 k 类的某一种分法.常记分法 ( , ) b n k 为: { } { } 1 1 1 2 2 2 2 3 , 1,..., 1 , , 1,..., 1 ,..., , 1,..., G i i i G i i i G i i n { } 1,..., 1 ,..., , 1,..., k k k i G i i n 4) 其中, 分点为 1 2 1 1= ... 1 k k i i i n i + 定义上述分类法的损失函数为 [ ] 1 1 1) k t t t L b n k D i i + = = - ? (5) 当,nk固定时, [ ] ( , ) L b n k 越小,表明各类 的离差平方和越小,分类越合理.因此要寻找一 种分法 ( , ) b n k ,使得分类损失函数 [ ] ( , ) L b n k 达 到最小,记*(,)bnk是使得(5)式达到最小的分 类法. 3) [ ] ( , ) L b n k 的递推公式为 { } { } * 2 * * ( ,2) = min (1, 1) ( , ) = min ( 1, 1) j n k j n L b n D j D j n L b n k L b j k D j n ? ? ? ? ? ? ? í é ù é ù - - + ? (6) 4)最优解的求法.首先找分点 k j ,使得(6) 式达到极小,即**1, 1) ( , ) k k L b n k L b j k D j n é ù é ù - - + 于是得到第k 类{},1,..., k k k G j j n = + . 然后找分点 1 k j - ,使它满足 * * 1 1 ( 1, 1) = ( 1, 2) ( , 1) k k k k L b j k L b j k D j j - - é ù é ù 于是得到第 1 k - 类{}111,1,..., 1 k k k k G j j j - - - = + - . 类似地,可以得到所有类 1 2 , ,..., k G G G ,这 就是最优解,即{}*12kbnkGGG.5)分类数k 的确定方法 分类数 k 可以通过 * ( , ) L b n k é ù ? ? 与k的关 系曲线图求得,曲线拐弯处的k 值即为最优分割 数[5] .当曲线拐弯很平缓时,可以选取的k 很多, 这时可以使用均方比[6] 来确定. 2 应用实例 2.1 分类对象 以历届全国大学生数学建模竞赛 (CUMCM) 专科组试题为分类对象. 选取了从 1999 年专科组 独立于本科组竞赛以来,截止 2010 年的 12 年的 C、D 题,一共 24 个赛题,以X1~X24 表示. 计算出 24 个赛题的综合评价值, 并按照综合评 价值从大到小排序, 结果如表 1 的第 3、 4 列所示. 综 合评价值越大,表示赛题质量越好. 为了使用最优分割法对这些赛题进行有序分 类,将所有赛题按照综合评价值从大到小的顺序重 新排列,形成有序样品 B1~B24,见表 2.排序靠 前的赛题质量较好. 2.2 分类过程和结果 1)计算直径.由于样品指标的维数 1 m = ,所 以使用(3)式计算直径,其中 G X % 是该类样品评价 值的均值,按照(1)式直径的计算结果见表 3(使用MATLAB 软件编程计算) . 2)计算最小分类损失函数 * ( , ) L b l k é ù ? ? ,及其 相对应的分点, 3 24 l ? ? , 2 23 k ? ? .计算结 果见表 4 和表 5. 3) 确定k .做*(24, ) L b k é ù ? ? 随k变化的趋势图, 如图 1 所示.从图 1 可以看出,当=7 k 时,曲线开 始变得平缓,所以分为 7 类为好. 4)确定最优分类.将24 个赛题分为 7 类,结果 见表 6. 总之,将24 个赛题分为 7 类的结果为:{ } 1 B , { } 2 3 5 , ,...., B B B , { } 6 7 , B B , { } 8 9 12 , ,..., B B B , { } 13 14 17 , ,..., B B B ,{ } 18 19 21 , ..., B B B , ,{ } 22 23 24 , , B B B . 考虑到本文的研究目的是将这些 24 个赛题的 质量分出等级,以便于能对今后的命题具有指导意 义. 若划分过细, 则不利于提炼类特征. 因此, 将其 划分为 5 个等级,即优、较优、中、较差、差这 5 个等级;或者划分为 3 个等级,即优、中、差这 3 个等级. 分为 5 类的结果为: { } 1 2 5 , ..., B B B , , { } 6 7 , B B , { } 8 9 13 , ..., B B B , ,{ } 14 15 19 , ..., B B B , ,{ } 20 21 24 , ,..., B B B . 分为3类的结果为:{}127,..., B B B , , { } 8 9 17 , ..., B B B , ,{ } 18 19 24 , ..., B B B , . 以上 3 种分类结果汇总见表 2,将其分类结果 标示在原赛题上,结果见表 1 的第 6、7、8 列. - 40 - http://xb.szpt.edu.cn 深圳职业技术学院学报 2013,12(1) 表1所有 24 个赛题的综合评价结果及排序 序号 赛题 综合评价值 排名 赛题题目 分7类分5类分3类1X1 0.1851 11 输油管的布置 4 3 2 2 X2 0.2037 1 对学生宿舍设计方案的评价 1 1 1 3 X3 0.1920 7 卫星和飞船的跟踪测控 3 2 1 4 X4 0.1785 19 会议筹备 6 4 3 5 X5 0.1981 4 地面搜索 2 1 1 6 X6 0.1866 10 NBA 赛程的分析与评价 4 3 2 7 X7 0.1817 15 手机"套餐"优惠几何 5 4 2 8 X8 0.1811 16 体能测试时间安排 5 4 2 9 X9 0.1987 3 易拉罐形状和尺寸的最优设计 2 1 1 10 X10 0.1715 22 煤矿瓦斯和煤尘的监测与控制 7 5 3 11 X11 0.1805 17 雨量预报方法的评价 5 4 2 12 X12 0.1846 12 DVD 在线租赁 4 3 2 13 X13 0.1999 2 饮酒驾车 2 1 1 14 X14 0.1870 9 公务员招聘 4 3 2 15 X15 0.1835 13 SARS 的传播 5 3 2 16 X16 0.1702 24 抢渡长江 7 5 3 17 X17 0.1881 8 车灯线光源的计算 4 3 2 18 X18 0.1762 20 赛程安排 6 5 3 19 X19 0.1825 14 基金使用计划 5 4 2 20 X20 0.1944 6 公交车调度 3 2 1 21 X21 0.1705 23 飞越北极 7 5 3 22 X22 0.1751 21 空洞探测 6 5 3 23 X23 0.1787 18 煤矸石堆积 6 4 3 24 X24 0.1975 5 钻井布局 2 1 1 表2有序样品及其综合评价值 排名 1 2 3 4 5 6 7 8 9 10 11 12 有序样品 B1 B2 B3 B4 B5 B6 B7 B8 B9 B10 B11 B12 综合评价值 0.2037 0.1999 0.1987 0.1981 0.1975 0.1944 0.1920 0.1881 0.1870 0.1866 0.1851 0.1846 分7类122223344444分5类111112233333分3类111111122222排名 13 14 15 16 17 18 19 20 21 22 23 24 有序样品 B13 B14 B15 B16 B17 B18 B19 B20 B21 B22 B23 B24 综合评价值 0.1835 0.1825 0.1817 0.1811 0.1805 0.1787 0.1785 0.1762 0.1751 0.1715 0.1705 0.1702 分7类555556666777分5类344444455555分3类222223333333http://xb.szpt.edu.cn 深圳职业技术学院学报 2013,12(1) - 41 - 表3直径 D(i , j)的计算结果(乘以 10000) j i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 1 0 0.072 0.136 0.190 0.244 0.467 0.854 1.670 2.481 3.192 4.012 4.777 5.606 6.488 7.394 8.293 9.19310.337 11.401 12.847 14.412 16.798 19.274 21.634 2 0 0.007 0.017 0.031 0.169 0.442 1.086 1.722 2.272 2.920 3.523 4.185 4.898 5.636 6.372 7.113 8.079 8.97410.225 11.591 13.731 15.959 18.077 3 0 0.002 0.007 0.110 0.324 0.863 1.384 1.824 2.351 2.836 3.376 3.964 4.576 5.188 5.806 6.633 7.396 8.493 9.69811.636 13.658 15.576 4 0 0.002 0.079 0.242 0.680 1.091 1.426 1.837 2.213 2.638 3.108 3.602 4.097 4.600 5.296 5.936 6.885 7.937 9.68111.504 13.229 5 0 0.048 0.152 0.472 0.760 0.986 1.277 1.542 1.853 2.205 2.581 2.961 3.352 3.919 4.437 5.239 6.139 7.686 9.30910.841 6 0 0.029 0.202 0.354 0.468 0.638 0.794 0.992 1.229 1.491 1.761 2.043 2.482 2.882 3.539 4.287 5.637 7.059 8.398 7 0 0.076 0.138 0.182 0.271 0.354 0.474 0.628 0.806 0.995 1.197 1.537 1.846 2.388 3.014 4.200 5.454 6.631 8 0 0.006 0.012 0.046 0.081 0.146 0.240 0.356 0.484 0.625 0.888 1.124 1.571 2.097 3.143 4.252 5.290 9 0 0.001 0.020 0.040 0.083 0.151 0.238 0.335 0.445 0.663 0.858 1.246 1.707 2.659 3.668 4.607 10 0 0.011 0.022 0.050 0.098 0.161 0.233 0.317 0.497 0.655 0.991 1.394 2.258 3.174 4.020 11 0 0.001 0.013 0.040 0.080 0.127 0.184 0.325 0.448 0.730 1.073 1.846 2.664 3.415 12 0 0.006 0.022 0.047 0.078 0.118 0.230 0.325 0.565 0.858 1.553 2.286 2.953 13 0 0.005 0.016 0.032 0.056 0.139 0.208 0.403 0.647 1.260 1.906 2.488 14 0 0.003 0.010 0.022 0.082 0.130 0.289 0.489 1.028 1.593 2.095 15 0 0.002 0.007 0.050 0.082 0.209 0.371 0.841 1.330 1.757 16 0 0.002 0.031 0.050 0.148 0.275 0.677 1.090 1.445 17 0 0.016 0.024 0.093 0.184 0.515 0.850 1.130 18 0 0.000 0.039 0.093 0.346 0.598 0.803 19 0 0.026 0.060 0.255 0.442 0.586 20 0 0.006 0.121 0.227 0.305 21 0 0.065 0.117 0.152 22 0 0.005 0.009 23 0 0.000 24 0 表4最小分类损失函数 L[b* (l , k)]的计算结果(乘以 10000) k l 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 3 0.007 4 0.017 0.002 5 0.031 0.007 0.002 6 0.169 0.031 0.007 0.002 7 0.272 0.060 0.031 0.007 0.002 8 0.446 0.234 0.060 0.031 0.007 0.002 9 0.598 0.279 0.066 0.038 0.013 0.007 0.002 10 0.650 0.285 0.072 0.044 0.019 0.008 0.003 0.001 11 0.738 0.319 0.106 0.072 0.044 0.019 0.008 0.003 0.001 12 0.821 0.354 0.142 0.074 0.045 0.021 0.009 0.004 0.002 0.001 13 0.941 0.418 0.206 0.086 0.057 0.033 0.021 0.009 0.004 0.002 0.001 14 1.094 0.513 0.300 0.113 0.079 0.050 0.026 0.014 0.009 0.004 0.002 0.001 15 1.210 0.629 0.365 0.152 0.089 0.060 0.036 0.024 0.012 0.007 0.004 0.002 0.001 16 1.338 0.756 0.386 0.174 0.096 0.067 0.043 0.027 0.016 0.011 0.006 0.004 0.002 0.001 17 1.479 0.834 0.409 0.197 0.108 0.079 0.055 0.033 0.021 0.014 0.009 0.006 0.004 0.002 0.001 18 1.742 0.960 0.493 0.281 0.163 0.108 0.079 0.055 0.033 0.021 0.014 0.009 0.006 0.004 0.002 0.001 19 1.978 1.029 0.549 0.337 0.195 0.108 0.079 0.055 0.033 0.022 0.014 0.009 0.006 0.004 0.002 0.001 0.000 20 2.425 1.225 0.707 0.448 0.236 0.146 0.108 0.079 0.055 0.033 0.022 0.014 0.009 0.006 0.004 0.002 0.001 0.000 21 2.951 1.430 0.884 0.503 0.291 0.201 0.114 0.085 0.061 0.039 0.028 0.020 0.014 0.009 0.006 0.004 0.002 0.001 0.000 22 3.997 1.826 1.150 0.670 0.457 0.291 0.201 0.114 0.085 0.061 0.039 0.028 0.020 0.014 0.009 0.006 0.004 0.002 0.001 0.000 23 5.106 2.078 1.256 0.776 0.508 0.296 0.206 0.119 0.090 0.066 0.044 0.033 0.025 0.019 0.014 0.009 0.006 0.004 0.002 0.001 0.000 24 6.144 2.282 1.334 0.854 0.512 0.300 0.210 0.123 0.094 0.070 0.048 0.037 0.028 0.021 0.015 0.010 0.006 0.005 0.003 0.001 0.001 0.000 - 42 - http://xb.szpt.edu.cn 深圳职业技术学院学报 2013,12(1) 表5与最小分类损失函数 L[b* (l , k)]相对应的分点 k l 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 3 2 4 2 3 5 2 3 5 6 2 6 6 6 7 6 6 7 7 7 8 6 6 8 8 8 8 9 6 8 8 8 8 9 9 10 7 8 8 8 8 9 9 9 11 7 8 8 11 11 11 11 11 11 12 7 8 8 11 11 11 11 11 11 12 13 7 8 8 11 11 11 13 13 13 13 13 14 8 8 8 11 13 13 13 13 13 14 14 14 15 8 8 11 11 14 14 14 14 14 14 15 15 15 16 8 8 13 13 14 14 14 15 15 15 15 16 16 16 17 8 11 13 13 14 14 14 15 15 16 16 17 17 17 17 18 8 13 13 13 15 18 18 18 18 18 18 18 18 18 18 18 19 8 13 14 14 15 18 18 18 18 18 18 18 18 18 18 18 18 20 8 13 14 18 18 18 20 20 20 20 20 20 20 20 20 20 20 20 21 8 14 15 18 18 18 20 20 20 20 20 20 21 21 21 21 21 21 21 22 8 18 20 20 20 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 23 8 18 20 20 22 22 22 22 22 22 22 22 22 22 22 23 23 23 23 23 23 24 8 18 20 20 22 22 22 22 22 22 22 22 23 23 23 23 23 23 23 23 23 24 0 5 10 15 20 25 0 1 2 3 4 5 6 7 分类数 损失 函数 值图1损失函数 L[b * (n , k)] (乘以 10000)随k变化的趋势 表6将24 个赛题分为 7 类的分类结果 赛题 个数 类数损失函数 L 值(/10000) 分点 j 值 分类结果 24 7 0.300 22 {B22~B24} 21 6 0.291 18 {B18~B21} 17 5 0.197 13 {B13~B17} 12 4 0.142 8 {B8~B12} 7 3 0.060 6 {B6~B7} 5 2 0.031 2 {B2~B5} 1 1 - - {B1} 2.3 分类结果检验 以划分 7 类为例. 令1,1,2,...,23 i i i B B y x x i + = - = , 其中 i B x 表示有序样品 i B 的综合评价值, i y 表示有 序样品 i B 与1iB+的综合评价值的一阶差分值.将1,2,...,23 i y i = ( ) 用图形表示出来, 如图 2 所示 (横 坐标表示 B1~B23,纵坐标表示一阶差分值 i y ) . 从图 2 可以看出, 1 B 与2B差距很大, 5 B 与6B差距很大, 6 B 与7B差距很大, 7 B 与8B差距很大, 10 B 与11 B 差距很大, 12 B 与13 B 差距很大, 17 B 与18 B 差距很大, 19 B 与20 B 差距很大, 21 B 与22 B 差 距很大,故他们每之间应当成为分界点,这样一来 就要分为 9 类. 由于分类数的限制, 必须减少 2 类. 将B1~B24 的综合评价值用图形表示出来,如图3所示(横坐标表示 B1~B24,纵坐标表示综合 评价值) . 从图 3 可以看出, 在6B与7B,10 B 与11 B , 19 B 与20 B 这三者的落差中, 5 B 与8B之间的落差最大, 这里必须截断,否则类内离差平方和必然增大,故将67,BB合并为一类可以达到截断的目的.而10 B 与11 B 、 19 B 与20 B 可以融入所在类别之中,恰好分 为7类. http://xb.szpt.edu.cn 深圳职业技术学院学报 2013,12(1) - 43 - 0.0000 0.0010 0.0020 0.0030 0.0040 0.0050 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 图2B1~B23 的一阶差分值 0.15 0.16 0.17 0.18 0.19 0.20 0.21 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 图3B1~B24 的综合评价值的变化趋势 综上所述,最优分割法得到的分类结果是符 合实际的. 参考文献: [1] 方开泰. 有序样品的一些聚类方法[J]. 应用数学学 报,1982,5(1) :94-101. [2] 高惠璇.应用多元统计分析[M].北京:北京大学出 版社,2005:253-255. [3] 张世英,黄违洪.最优分割法的适用性及一类有序 样品的聚类方法[J]. 应用数学学报, 1987, 10 (2) : 138-144. [4] 王鹤春,王家斌.基于主成分分析与最优分割理论对 实习成绩综合评定的研究与分析[J]. 数学的实践与认 识,2009,39(12) :21-26. [5] 彭志行,鲍昌俊,赵杨,等.加权马尔可夫链在传染 病发病情况预测分析中的应用[J].数学的实践与认 识,2009,39(27) :92-99. [6] 赵欣,邹良超,倪林.基于有序聚类的模糊加权马尔 可夫模型在降雨预测中的应用[J].江西农业学报, 2009,21(2) :110-113. Optimal Classification of Test Questions in National Mathematical Modeling Contests for College Students WANG Jijian1 , CHEN Xiaoyuan2 , RU Yongmei1 (1. Zhejiang Industrial&Trade Polytechnic, Wenzhou, Zhejiang 325003, China; 2. Zhejiang Vocational College of Commerce, Hangzhou, Zhejiang 310053, China) Abstract: In order to conduct a comprehensive evaluation of the previous (1992~2010) test questions in national mathematical modeling contests for college students in terms of quality, Fisher's optimal segmentation was adopted to classify these 24 test questions on the basis of fuzzy comprehensive evaluation. When classified into 5 categories, the order of their qualities is{2010D, 2008C, 2006C,2004C,1999D};{2009C,2001D}, {2010C,2008D,2005D,2004D,2003C,2002C};{2009D,2007C,2007D,2005C,2001C,1999C}; {2006D,2003D,2002D,2000C,2000D}. Key words: CUMCM; test questions; optimal segmentation; cluster analysis