（计算机应用技术专业论文）普通高校招生中一档多投模型及其核心算法研究.pdf

j叫叫-11 _ 【 i 目录 摘要1 a b s t r a c t i i i 第一章绪论1 1 1研究背景及意义1 1 2研究现状2 1 2 1国内志愿填报方式研究现状2 1 2 2国内外档多投模式研究现状4 1 2 3招生模型及相关算法研究现状。5 1 3研究内容6 1 4论文的组织结构7 第二章相关理论与技术基础9 2 1 国内招生录取模式9 2 1 1顺序志愿投档模式9 2 1 2平行志愿投档模式10 2 1 3“考生确认”的一档多投模式一1 1 2 1 4三种模式的区别1 2 2 2招生录取算法1 2 2 2 1g s a ：12 2 2 2t t c a 。1 3 2 3数据仓库与o l a p 技术。1 4 2 3 1数据仓库的概念1 4 2 3 2o l a p 概j 苤。14 2 3 3数据仓库与o l a p 的关系1 5 2 3 4数据仓库与传统数据库的区别1 5 2 4高考招生数据仓库1 6 2 4 1系统结构1 6 2 4 2 s q ls e r v e r2 0 0 8 简介。1 7 2 5本章小结1 7 第三章现行录取模式的数据分析1 8 3 1某省现行招生录取模式介绍18 3 2数据分析18 3 2 1定义评定指标18 3 2 2o l a p 数据分析18 3 3现行录取模式存在的主要问题及原因：2 1 3 4本章小结2 2 第四章以专业为单位的一档多投模型及其核心算法 4 1问题分析 4 2一档多投模型 4 2 1模型描述 4 2 2 模型的基本思想2 4 4 3模型涉及的关键问题及难点2 6 4 4基于变权综合的预录算法2 7 4 4 1 变权综合原理2 7 4 4 2变权综合的决策函数2 7 4 4 3基于变权综合的预录决策函数2 9 4 4 4基于变权综合的预录算法3 0 4 5最小优先志愿号算法31 4 6本章小结3 2 第五章一档多投实验系统3 4 5 1高校招生业务流程3 4 5 2系统实体分析3 4 5 3一档多投实验系统设计3 6 5 3 1系统结构设计3 7 5 3 2高校审录数据流程设计3 8 5 3 3招办确认数据流程设计3 9 5 4数据库设计3 9 5 4 1主要数据库表3 9 5 4 2数据库优化4 3 5 5核心算法的实现问题4 3 5 6本章小结4 4 第六章模拟实验与结果分析4 5 6 1源数据4 5 6 2数据预处理4 5 6 3实验结果分析4 5 6 3 1基于变权综合的预录算法的结果分析4 6 6 3 2最小优先志愿号算法的结果分析4 7 6 4本章小结5 0 ， 第七章总结与展望5 1 7 1全文工作总结5 1 7 2未来工作展望51 参考文献5 3 致 射5 5 硕士期间发表的论文和参与的课题5 7 ， l 摘要 普通高校招生中的一档多投模型 及其核心算法研究 计算机应用技术专业硕士研究生刘驰 指导老师张自力教授 摘要 普通高校招生是国家选拔人才、体现公平竞争、构建社会和谐的一个主要环节，是教育 领域具有政治意义、社会意义和全局意义的一项重要工作。普通高校招生中的志愿填报及投 档方式作为一种招生录取模式，直接关系到考生接受高等教育的机会，事关千家万户的切身 利益，是社会各界密切关注的问题。 恢复高考3 0 余年来，我国普通高校招生录取模式几经变革，但仍存在明显的弊端，迫切 需要一种更为科学、公平的录取方式。国外对高校招生录取模式改革的研究已有较长的历史， 其中，“一档多投”模式得到了广泛的应用，部分西方国家在一档多投招生工作中已取得了重 要成果。这使得一档多投成为当前我国高校招生录取模式改革一个热点研究问题。但是，我国 “一档多投”模式刚刚起步，录取办法还不够完善，对于“大规模”系列的普通高校招生还有 许多问题有待解决。 本文通过某省已搭建好的高考数据仓库平台，对高校招生历史数据进行多维分析，挖掘现 行模式存在的主要问题，构建了一个适合我国普通高校招生的以专业为单位的一档多投模型， 并提出了支持该模型的变权综合预录算法和最小优先志愿号录取算法。最后，设计和实现了一 个一档多投实验系统，利用真实数据，进行了模拟实验。与传统模式的录取结果相比，“一档 多投”能有效降低志愿填报风险，减少高分低就、中高分落榜等现象的发生，较好地解决高校 选拔综合型人才与专业型人才的决策问题。本文的研究成果还可以为我国高考“一档多投”模 式的改革提供必要的理论支撑。 关键词：普通高校招生一档多投录取算法数据仓库 a 一。 j ab s t r a c t o n e - t o - - m a n ym o d e l f o r u n i v e r s i t y r e c r u i t m e n ta n dr e l a t e dc o r e a l g o r i t h m s m a s t e rc a n d i d a t eo fc o m p u t e r a p p l i c a t i o nt e c h n o l o g y ：l i uc h i s u p e r v i s o r ：p r o f z h a n gz i l i a b s t r a c t t h ee n r o l l m e n to fo u rn a t i o n a lc o l l e g e sa n du n i v e r s i t i e si sa l li m p o r t a n tl i n ko fs e l e c t i n gt a l e n t s ， r e f l e c t i n gi nf a i rc o m p e t i t i o n ，c o n s t r u c t i n ga h a r m o n i o u ss o c i e t y , a n di ti sa l s oa ni m p o r t a n tw o r ko f h a v i n gp o l i t i c a ls i g n i f i c a n c e ，s o c i a ls i g n i f i c a n c e a n dg l o b a ls i g n i f i c a n c ei nt h ef i e l do fh i g h e r e d u c a t i o n t h ee n t r a n c ea p p l i c a t i o nm o d ei nu n i v e r s i t ye n r o l l m e n th a sb e e nd i r e c t l yr e l a t e dt o e x a m i n e e so p p o r t u n i t yf o rh i 曲e re d u c a t i o na n dt h ei m m e d i a t ei n t e r e s t sw i t ht h et h o u s a n d su p o n t h o u s a n d s ，a n di ti sa l w a y sp a i dg r e a ta t t e n t i o nb ya l lp a r t i e si nt h es o c i e t y t h ea d m i s s i o nm o d ei nc o l l e g ee n r o l l m e n th a se x p e r i e n c e ds e v e r a lr e f o r m ss i n c et h er e c o v e r y o ft h ec o l l e g ee n t r a n c ee x a m i n a t i o ni n19 7 7 ，b u ti ts t i l lh a ss o m eo b v i o u sd i s a d v a n t a g e s s oi ti si n d i r en e e do fam o r es c i e n t i f i ca n df a i ra d m i s s i o nw a yi nc o l l e g ee n t r a n c ea p p l i c a t i o n t h es t u d yo n t h er e f o r m a t i o no fc o l l e g ee n t r a n c ea p p l i c a t i o nm o d eh a sal o n gh i s t o r yi nt h ed e v e l o p e dc o u n t r i e s ， s o m eo fw h i c hh a v er e f o r m e do n e - t o m a n yc o l l e g ea d m i s s i o nm o d e ( o m c a m ) w h i c hh a sb e e n a p p l i e dw i d e l y , a n ds o m ew e s t e r nc o u n t r i e sh a v em a d ei m p o r t a n ta c h i e v e m e n t so ne n r o l l m e n tw o r k o fo m c a m s ot h eo m c a mi sah o tt o p i ci nt h er e f o r m a t i o no fc o l l e g ea d m i s s i o nm o d en o w h o w e v e r , t h em o d ei nc h i n ai sj u s tu n d e r w a y , w h i c hi sn o tp e 彘c te n o u g h ，a n dh a sal o to f p r o b l e m s t os o l v ef o rm a s ss t u d e n t si no r d i n a r yc o l l e g ee n r o l l m e n ts y s t e m t h r o u g ha nm u l t i d i m e n s i o n a la n a l y s i so nt h eh i s t o r i c a ld a t ao fu n i v e r s i t ye n r o l l m e n tu s i n gt h e p l a t f o r mo fc o l l e g ee n t r a n c ee x a m i n a t i o nd a t aw a r e h o u s ef r o mo n ep r o v i n c e ，w eh a v ef o u n do u tt h e k e yp r o b l e m so ft h ec u r r e n tm o d e ，b u i l dan e wo n e - t o - m a n ym o d e lf o ru n i v e r s i t yr e c r u i t m e n t w h i c hf o c u s e so nt h ep r o f e s s i o n a lc h o i c ea n daf i l ef o rm a n yc o l l e g e s ，w h i c hi ss u i t a b l ef o rt h e c h i n a so r d i n a r yc o l l e g ee n r o l l m e n t , a n dw ea l s op u tf o r w a r dav a r i a b l ew e i g h tc o m p r e h e n s i v e p r e r e c o r d e da l g o r i t h ma n dt h em i n i m u ma p p l i c a t i o nn u m b e rf i s ta l g o r i t h mf o rt h ec o n f i r m a t i o no f p r e r e c o r d e dc a n d i d a t e s ，w h i c hc a r ls u p p o r tt h i sm o d e f i n a l l y ，w ed e s i g na ne x p e r i m e n t a ls y s t e m b a s e do nt h ep r o p o s e dm o d e l t h es i m u l a t i o ne x p e r i m e n tu s i n gt h eh i s t o r i c a ld a t av e r i f i e s t h a t c o m p a r i n gw i t ht h et r a d i t i o n a lm o d e ，t h ep r o p o s e dm o d e li se f f e c t i v et ol o w e rt h er i s ko ft h e v o l u n t a r yr e p o r t i n g ，r e d u c et h en u m b e ro fs t u d e n t sw i t hh i g hm a r k sw h o f a i lt oe n t e rac o l l e g ea n d w h of a i lt oab e t t e rc o l l e g e ，a n ds o l v et h ed e c i s i o np r o b l e mi nt h es e l e c t i o no fc o m p r e h e n s i v et a l e n t s i i i i v t 一 第1 章绪论 第1 章绪论 本章主要对本课题研究的背景和意义进行阐述，并对高校招生录取方式相关 的国内外现状进行了叙述，最后对本论文的主要研究工作及组织结构作了介绍。 1 1研究背景及意义 普通高校招生是国家选拔人才、体现公平竞争、构建社会和谐的重要环节， 是教育领域具有政治意义、社会意义和全局意义的重要工作。普通高校招生中的 志愿填报及投档方式作为一种招生录取模式，关系到考生接受高等教育的机会， 事关千家万户的切身利益，是社会各界密切关注的问题。 据教育部统计【1 】，自1 9 7 7 年恢复高考以来，全国普通高校共招生约6 6 6 1 2 万 人，其中，1 9 7 7 年招生2 7 万人，1 9 7 8 年增至4 0 2 万人，到2 0 1 0 年已达6 5 7 万人， 录取人数分别是1 9 7 7 年、1 9 7 8 年的2 4 3 倍和1 6 4 倍，录取率也由4 7 、6 6 增 至6 9 4 。如今上大学已不是少数人的梦想。高考的恢复，改变了千百万考生的命 运，为我国教育事业做出了积极的贡献。 1 9 9 8 年，教育部推动网上录取，数学建模确定了投档方式为一档一投( 即同 一时刻同一考生的档案只能被投放到一个高校) ，之后各个省( 市、区) 一直在此 模式下采取相应的录取办法完成招生录取工作。传统的顺序志愿投档模式，强调 “志愿优先，遵循分数 的原则，即以考生志愿的排序为前提分批次进行投档， 高校按分数排序进行录取。随着高等教育大众化时代的到来，信息技术的高速发 展，传统录取模式存在的弊端日益凸显 2 , 3 j ，过大的强调第一志愿的重要性，不仅 有失高考录取的公平公正，还增加了志愿填报的风险，造成了高分考生的低就、 落榜、复读现象。2 0 0 6 年，国家统计局北京调查总队在北京市十八个区县进行的 “高校招生制度改革意向 快速调查结果显示：对现行高考录取方式满意者不到 三成。被访者对“根据志愿、按比例投档 录取方式的满意度较低，仅占2 5 5 蝌引。 其实，公众对我国高考录取方式的不满不只是针对投档比例的设置，还有志愿结 构设计、同批次内是否同步投档等问题。为解决这些突出问题，近年来，教育部 和各省( 直辖市、自治区) 教育行政部门、招生考试部门在志愿填报及录取方式 上进行了一些改革。2 0 0 8 年，教育部在全国推广的平行志愿投档模式，在一定程 度上减少了高分低就、落榜现象。但是，“平行志愿”也存在明显不足1 4 ，5 j ：如唯 分数论、退档风险、高校自主权减弱、强化高校之间的等级之分等。无论是平行 志愿还是传统的顺序志愿，都属于线性的投档方式，对于考生来说，尽管每个批 次可以填报多个志愿，看似给了他们表达志愿的愿望，但并未能实现同一批次各 志愿的平行录取，志愿未能得到最大化利用。每年的招生录取工作中，都会有一 两南大学硕十学位论文 些考生“高分低就”，甚至“高分落榜 的遗憾。因此，这样的招生录取方式已 不太能满足国家、社会、家长、考生的真实意愿需求。 一档多投招生模式的出现，成为了上述问题很好的解决方案。一档多投已经 成为一种引人注目的新的录取机制，在国内引起了考生、研究者、招生机构的广 泛关注。这使得一档多投成为当前我国高校招生录取模式改革的一个热点研究问 题。其实，一档多投模式在国外的大学招生录取中早已得到了广泛的应用，并取 得了重要成果【6 ，7 1 。结合理论和招生实践来看，一档多投能大大降低志愿填报风险、 减少高分低就、中高分落榜等现象的发生，能较好地满足考生与高校双方的利益 需求，深受考生和家长的欢迎。但是，我国一档多投模式刚刚起步，缺少完善的 录取办法，对于“大规模”系列的普通高校招生还有许多问题有待解决。就此， 2 0 1 0 年7 月2 9 日，国家公布的国家中长期教育改革和发展规划纲要( 2 0 1 0 2 0 2 0 年) 明确提出，要“完善高等学校招生名额分配方式和招生录取办法，建立健全 有利于促进入学机会公平、有利于优秀人才选拔的多元录取机制 【引。那么，如何 利用信息技术，科学、系统地分析历史数据，挖掘现行录取模式存在的优缺点， 完善我国普通高校招生中的一档多投模式，是一个急需要解决的问题。 因此，本论文在国内招生政策改革大趋势的基础上，结合国外“一档多投 模 式的有益经验，利用某省已搭建好的高考数据仓库平台，对高校招生历年数据进 行多角度分析，构建一个适合我国普通高校招生的一档多投模型，并对相应的支 撑算法进行研究，期望能给我国高考“一档多投”模式的改革提供理论支撑。 1 2研究现状 1 2 1 国内志愿填报方式研究现状 在国内，对高考志愿填报方式改革的研究，是当前教育体制改革下的一个研 究热点。志愿填报方式的合理设置直接影响到考生能否被心仪的院校及专业录取， 甚至会影响考生的命运。下面我们对e l 前采用的志愿填报方式和志愿填报方式研 究的进展情况作以下介绍。 1 ) 志愿填报方式分类 目前我国各省市实行的志愿填报方式形式各异，可按填报途径，填报时间， 志愿结构进行分类。 ( 1 ) 按志愿填报途径分类 考生手工填报志愿卡：传统的手工纸质填报，在计算机不发达的时候采用， 现在只有几个省还在用此方式。如吉林省。 网上填报：目前全国各省( 直辖市、自治区) 大都采取此填报方式。 ( 2 ) 按志愿填报时间分类 2 第1 章绪论 考前填报：即考生在高考前根据自己平时的学习状况以及冲刺阶段模拟考 试的成绩与排名，综合分析评价自己的实力后进行高考志愿的填报，时间 一般安排在5 月上旬。如上海、北京。 考后估分填报：即考生在高考后参考评分标准估计自己的高考分数，进行 高考志愿填报。时间一般安排在6 月中旬，目前有天津、山西、黑龙江、 河南、陕西、辽宁等8 省( 直辖市、自治区) 实行。 考后知分填报：即在高考成绩和批次分数线公布后，考生再进行高考志愿 填报。时间一般安排在6 月下旬至7 月上旬，目前有江苏、山东、湖北、 湖南、浙江省、福建省、广东、广西、内蒙、四川、重庆等共2 1 省( 直 辖市、自治区) 实行。 分批实时填报：在“分段填报的基础上，考生可以实时查看本人在所报 高校中的排名位次和高校各专业的计划数，并做到即时修改即时刷新。第 一次采集志愿录取结束后，公布剩余高校招生计划数再次填报，直至本批 录取结束。目前只有内蒙古实行，实时性要求较高。 ( 3 ) 按志愿结构分类 顺序志愿：是传统的志愿结构，指在某个录取批次设置的高校志愿分为一 志愿、二志愿、三志愿体现“志愿优先，遵循分数”的原则。 平行志愿：是指在某个录取批次设置的高校志愿均为并列的志愿，体现 “分数优先，遵循志愿 的原则。2 0 0 2 年湖南省在第二批次录取中首先试 行平行志愿，2 0 0 3 年全面推开。2 0 0 9 年有包括四川、云南、江西在内的 1 6 个省市推行平行第一志愿。2 0 1 0 年己扩展到2 2 个省份，包括天津、河 南、重庆、西藏、广东、陕西等。 顺序志愿与平行志愿混合：即实行顺序的一、二、三志愿，在二志愿和三 志愿中同时实行多个平行志愿。投档时第一志愿按“志愿优先，按分排 序”的原则进行，二、三志愿按“分数优先，遵循志愿”进行。2 0 0 5 年至 2 0 0 9 年，重庆本科一批实行“1 + 2 + 3 的混合平行志愿模式( 即1 个第一 志愿，2 个平行第二志愿，3 个平行第三志愿) 。 2 ) 志愿填报方式研究进展 2 0 0 4 年，钟笑寒、程娜和何云帆等人最早对中国高考录取机制进行研究呻1 ， 讨论了完全信息时分数不确定时不同填报志愿方式对于不同能力考生录取结果的 影响。聂海峰从完全信息和不完全信息两方面刻画了高考招生博弈，比较了不同 的志愿填报时间的效果，得出：“从考生间博弈的策略复杂性和避免高分低录角度 。 来说，知分填报在完全信息下优于考前填报n 引。 文献【1 1 对平行志愿的分析，提 出了打通不同院校之间的专业志愿模式，可以减少学生的效用损失。2 0 0 7 年，张 两南大学硕十学何论文 天孟等人提出了一种“抢位置”的动态志愿填报模式【l 烈。该模式根据考生成绩的 高低，优先选择高校以及专业，每个考生只能选择一个院校的一个专业。2 0 0 9 年， 张大红等人设计出一种全志愿填报模式【l 引，考生可以填报所有院校的所有专业， 实行专业志愿，明确志愿的优先级，是对现行模式的重大改革。 不管是哪种志愿填报方式，都存在一定的局限性，未能从根本上解决我国高 校招生录取模式存在的突出问题。统一招生录取方式改革的突破点在投档模式， 而一档多投模式是统一招生录取模式改革的关键。 1 2 2国内外一档多投模式研究现状 一档多投已经成为一种引人注目的新的录取机制，引起了考生、研究者、招生 机构的广泛关注。一档多投模式，简单的说，就是将考生的档案投向所报考的所 有院校。 在国外，一档多投模式已在大学招生录取中得到了广泛的应用，部分发达国 家已取得了重要成果。在美国，本科新生录取方式一般采取“择优录取 和“额 满为止”的原则【l4 1 。考生可以报考一所或几所大学，有的考生可能收到多份录取 通知书，他们可根据自己愿望选择最心仪的学校就读。这种方式已在许多西方发 达国家得到应用，不仅体现了高校招生的自主性，而且也充分体现了以考生为本 的精神。2 0 0 3 年，法国对大学预科录取方式进行改革，实行网上一档多投【6 】，大 大降低了志愿填报风险，而之前，预科采用类似我国现行顺序志愿的投档模式。 法国的一档多投的做法是：考生在两个专业方向上各选择6 所学校进行网上志愿 填报，并把1 2 个志愿进行排序，之后招生办根据考生的志愿依次投档，直到考生 的最后一个志愿，学生可根据公布的第一轮录取，表示接受或放弃，如果对第一 轮的录取结果不满意，也可以暂时保留此录取机会，同时等待更靠前的志愿的第 二、三、四轮结果。其实，类似的录取办法已在法国精英工程师学校的招生中实 行多年，证明了“一档多投 能大大减少高分低就、中分落榜等现象的发生 7 1 。 国内一档多投模式的研究起步较晚，目前还处于试点研究阶段。 文献 1 4 】提出了一档多投，即“平行投档，同步录取，自主选择”，近年来不少研 究生学者也相继提到过这种模式，并认为这是一种最理想的录取方式。文献 1 6 】 认为目前方兴未艾的平行志愿模式仅仅是一种过渡阶段，它未来的发展趋势将是 一档多投模式。2 0 0 8 年，重庆4 所市属高职大专单独招生首次试行一档多投；2 0 1 0 年，北京大学、北京航空航天大学和香港大学在联合自主招生中也实行了一档多 投：同年，福建省在艺术类本科提前批也实行了“平行投档，一档多投，高校预 录，考生确认”模式【l 。7 1 。从招生实践来看，试点的“一档多投，考生确认 录取 方式深受考生和家长的欢迎。 4 第1 章绪论 一档多投可根据投档粒度分为以专业为单位的一档多投和以院校为单位的一 档多投；又可根据录取结果分为一档一录的一档多投和一档多录的一档多投。一 档多录是指一档多投后的院校都能录取该考生，然后考生根据录取通知书自主选 择去哪个院校就读。美国的大学基本采用这种招生模式。一档一录即是指投档后 的院校先预录考生，由考生或系统对多个预录结果进行确认。由于我国目前教育 体制的特殊性，一档多录的一档多投模式暂时很难实现。因此，本课题研究的是 一档一录的一档多投问题。 1 2 3招生模型及相关算法研究现状 1 9 6 2 年，g a l ea n ds h a p l e y 最早把大学招生录取问题作为机制设计问题来进行 研究，建立了大学招生模型，提出了g a l e s h a p l e y 机制i l8 1 ，通过数理论，证明了 关于学校和考生任意的偏好，都存在学生和大学录取结果的稳定匹配。聂海峰在 文献 1 9 1 i 1 匾过研究g a l e s h a p l e y 大学招生模型，比较了国外大学招生和高考招生 的不同点，构建了一个高考录取模型。文献【2 0 】通过分析招生者的高考决策心理活 动，提出了一种基于属性重心的招生决策模型，为科目偏好的高考招生提供一个 具体量化方法。王晖等人在文献 2 1 】中介绍了基于p e t r i 网的工作流建模与分析过 程，并将基于p e t r i 网的工作流模型应用到全国高校网上招生录取系统中。这些研 究为分析大学招生录取问题和建模奠定了理论基础。 b a l i n s k i 和s o n m e z 在文献【2 2 】通过研究土耳其的大学招生制度，指出 g a l e s h a p l e y 学生最优算法可以更好地录取学生。a b d u l k a d i r o g l u 和s o n m e z 首次 从机制设计的角度研究了美国公立学校的择校制度，提出了波士顿算法的机制【2 引。 s o n m e z 和e r g i n 在文献【2 4 】中研究了波士顿算法机制下的各种博弈。z h o u 在文献 2 5 1 中证明了按某一种次序对学生进行排序的独裁算法的机制是帕累托最优和抗 策略的。c h e n 和s o n m e z 在文献 2 6 】中用实证的方法比较了招生机制中的波士顿算 法、g a l e s h a p l e y 算法和t o pt r a d i n gc y c l e s 算法，结论显示后两种算法要远优于 波士顿算法，但g a l e s h a p l e y 算法在实际运用中效果最好。 在国内，对高考招生录取算法的研究较少。孙道清等人在文献 2 7 】中分析了高 考调剂志愿算法存在的问题，提出了一种改进的随机算法，并运用到安徽省高考 招生中。谢伟卡在文献 2 8 】中提出了一种适合多个高考总分情况下的最优分档算 法。这些研究的算法在一定程度上起到了积极的作用，但都未能从根本上解决我 国高校与考生之间存在的突出问题。 通过以上研究，我们可以将统一大学招生机制采用的主要录取算法归纳为： g a l e s h a p l e y 算法( g s a ) 、t o pt r a d i n gc y c l e s 算法( t t c a ) 2 9 , 3 0 】、波士顿算法【2 3 ，2 4 和分数独裁算法。从录取算法来看，g s a 和t t c a 采用循环思想，将考生在所报 足也逐渐暴露。“一档多投”则成为一种引人注目的新的录取机制，引起了国内 考生、家长、招生机构的广泛关注。但是，该模式下一个考生被多所高校预录的 确认录取算法还不完善，主要由考生自主确认，这对于“大规模”系列招生中不 好把握确认时机的考生来说，由系统默认确认可能会造成新的不公平，因而它仅 在个别自主、高职单招、艺术类中试点。要解决我国高考一档多投录取方式中的 学校与考生之间最佳匹配问题，有赖于采用g s a 或者t t c a ，国外已在这方面积 累了相关经验，如香港的大学录取模式，美国的医院住院市场，美国波士顿和纽 约公立学校的录取模式等等【2 2 ，2 3 1 。然而，国外的教育体制与国内有所不同，国外 无统一下达的招生计划；区域性比较强，考生一般就近选择高校，不会出现我国 的分省计划导致的考生全国流动。同时，我国一档多投模式改革的研究大都停留 在理论层面，相应的录取算法也未有深入的研究，也并未有专门的实验平台对历 史数据进行整体、全面的分析，引导高考录取方式的改革趋势。因此，科学、系 统地对现行录取方式进行数据分析，借鉴国内外有益经验，对于研究适合我国普 通高校招生的“一档多投 模式及相应录取算法是迫切需要的。 1 3 研究内容 针对现今国内高校招生过程中存在的众多矛盾，深入研究国内外高校招生模 式是有必要的，也是革新现今高招模式所必须的。本文主要在以下几个方面展开 研究： 1 ) 研究国内外志愿填报方式及投档模式 查阅和总结国内外志愿填报及投档模式相关文献，同时参与关于“一档多投 模式改革的专家研讨会，并且对“全国普通高校招生录取管理系统”进行了实地 调查，详细了解招生录取流程，并经常与某省招生自考办公室相关人员沟通，把 握一档多投模式改革的趋势。 6 第1 章绪论 i i 2 ) 现行招生录取方式的数据分析 在已搭建的高考招生数据仓库平台上，对某省2 0 0 0 - - - 2 0 0 9 年的普通高校招生 录取数据进行多维分析，着重考生落榜风险，录取的专业满意度，志愿填报失衡 情况等，挖掘现行志愿填报及投档模式存在的缺陷。 3 ) 构建以专业为单位的一档多投模型 构建一种以专业为单位的一档多投模型，即“专业志愿，一档多投，同步预 录，自动确认 。主要面向招办工作人员、高校招生人员和考生三大群体，由招 办确认完成考生的录取确认。 4 ) 设计支持一档多投模型的相关核心算法 设计相应的预录算法，实现高校专业对考生进行合理排序、预录；设计相应的 录取算法，对一个考生被多个高校专业预录的最终录取确认。 5 ) 设计和实现一档多投实验系统 设计一个以专业为单位的一档多投实验系统，利用历史真实数据进行模拟投 档，对采用“一档多投”模型和传统模式的录取结果进行比较，验证所提办法的 有效性和合理性。 1 4论文的组织结构 论文结构安排如下： 第一章，绪论。阐述本文的研究背景及选题意义，总结研究现状，指出论文的 主要工作，介绍全文结构安排。 第二章，相关理论与技术基础。对现行录取方式涉及的几种模式、录取算法、 数据仓库与o l a p 技术、高考招生数据仓库进行简单的介绍。 第三章，现行录取方式的数据分析。根据招生历史数据，分析现行志愿填报及 投档模式存在的主要问题及原因。 第四章，以专业为单位的一档多投模型及算法。提出此模型，并对其基本思想 及涉及的关键问题及难点进行具体介绍，并提出了支持该模型的基于变权综合的 预录算法和最小优先志愿号算法。 第五章，普通高校招生中的一档多投实验系统。通过对高校招生业务流程，系 统实体的分析，设计了一档多投实验系统的结构、高校审录的数据流程、招办确 认的数据流程及数据库等，并讨论了核心算法的实现问题。 第六章，模拟实验与结果分析。根据高校招生历史数据的模拟投档，与传统模 式下的录取结果进行对比分析。 第七章，总结与展望。总结现有工作，指出未来研究方向。 7 膏 蠢 第2 章相关理论1 孑技术基础 皇曼! 曼蔓曼皇曼曼曼曼曼曼蔓曼皇曼皇曼曼曼曼曼i n i 1 1! 曼蔓曼曼皇曼毫曼蔓皇曼曼曼曼量曼皇曼舅曼曼曼曼曼曼皇皇曼曼曼曼曼舅曼鼍曼曼曼鼍曼曼曼量曼曼曼曼曼曼曼曼 第2 章相关理论与技术基础 在本章中，首先介绍了我国现行高校招生录取工作涉及的几种主要模式，然后 对经典的两种录取算法进行了简单介绍，最后，对本文涉及到的技术知识及工具 平台作了简要阐述，主要包括：数据仓库、o l a p 、s q ls e r v e r2 0 0 8 ，这将为后续 相关章节的叙述作铺垫。 2 1国内招生录取模式 我国的高考主要是统一招生、统一录取，分批次进行。高校招生分为艺术、体 育类院校的招生、普通高校的招生、自主招生等。本文研究的是普通高校的招生。 高校招生录取工作主要由省( 自治区、直辖市) 招生办公室根据考生的成绩、志 愿，按相应的投档模式从高分到低分排序，依次将考生的电子档案投递给高校， 直到满足学校的投档人数要求；高校根据考生的专业志愿、成绩、综合素质等择 优录取，不符合条件的考生将退档处理，将其档案退回省( 直辖市) 招办。目前， 高校招生录取模式大致有：顺序志愿投档模式、平行志愿投档模式和“考生确认 的一档多投模式等。 2 1 1顺序志愿投档模式 顺序志愿是传统的志愿结构，指在相应录取批次有先后顺序的设置多个院校 志愿，如院校志愿为第一志愿、第二志愿、第三志愿计算机投档前，先提取 出所有达到本批次录取控制分数线考生名单，在投档时采用志愿优先算法，将相 同院校志愿的考生按分数进行分别排序，然后根据院校招生计划和投档比例向高 校投档。 图2 - 1 顺序志愿投档模式的流程图 9 两南人学硕十学伊论文 顺序志愿投档模式体现了“志愿优先、遵循分数 的原则【1 9 】，一个简化的流 程如图2 1 所示。将第一志愿报考某一院校a 的所有考生排队，有几所院校就排 几列，从高分到低分按该校招生计划数的1 0 0 1 2 0 内投档。第一志愿录取结束后， 若该考生所填报的第二志愿院校还有剩余计划或录取不满额，则将在第一志愿中 未被录取的考生按他所填报的第二志愿院校进行排序，然后按考生分数从高到低 进行投档，依次类推。由于每一批次考生只能填报一个第一志愿，考生若未被第 一志愿录取，所填第二、三志愿的院校一般已在前续志愿中录取满额，就只能参 加本批次院校志愿的调剂和征集志愿，或者只能降低到下一个批次录取，就出现 所谓的“高分落榜”或“高分低就现象。从近几年的招生数据来看，在第一志 愿投档录取结束后，高校一般能完成该批次招生计划的7 0 以上【4 1 。 2 1 2平行志愿投档模式 平行志愿是指在某个录取批次设置的院校志愿均为并列的志愿( a 、b 、c 等) ， 无第一志愿、第二志愿等之分。在录取投档时，采用分数优先算法，即先按考生 成绩从高分到低分( 总分相同时看单科成绩) 排序，然后根据院校招生计划和投档比 例向高校一次性投档，该算法看重的是考生的总分，尤其是最高总分。平行志愿 根据不同省份的实施情况又可分为完全平行志愿，准平行志愿两种。完全平行志 愿就是我们常说的平行志愿，每个批次每个志愿都是平行第一志愿，这是目前主 要使用的一种模式；准平行志愿是顺序志愿与平行志愿的混合，包括一个第一志 愿、多个并列第二志愿( 即平行志愿) 。 平行志愿投档模式体现了“分数优先、遵循志愿”的原则【5 】，一个简化的流程 如图2 2 所示。投档顺序从排序第一的考生开始，顺序检索各志愿，按院校招生计 划的1 0 0 1 1 0 投档，先检索a 志愿院校计划是否已完成，如未满额，则将该生投 档到a 校，如己录取满额，则检索b 志愿院校，依次类推，然后再投第二个考生。 排序在前的考生在未完成志愿院校的检索和投档时，就不会启动后一位考生的检 索和投档程序，以确保“分数优先 原则的实现。在平行志愿的规则下，考生原 来的第一志愿从一个变为了多个，增加了志愿选择范围和录取机会，大大降低填 报志愿的难度和风险。但是，由于平行志愿是一次性投档，投档后的考生( 0 1 0 ) 仍然存在退档风险。 第2 章相关理论与技术荩础 图2 2 平行志愿投档模式的流程图 2 1 3 “考生确认的一档多投模式 “考生确认 的一档多投模式即“平行投档，一档多投，院校预录，考生确认” 的投档与录取模式【3 1 】，是对平行志愿投档模式的发展创新，目前仅在少数高职单 招、自主招生、艺术类别中试点。一个简化的一档多投模式如图2 3 所示。省招办 根据考生填报志愿的顺序，对符合院校投档条件的考生，将向他们所填报的各所 院校平行投放电子档案；由各招生院校按录取规则进行审录，并提出拟录取名单， 经省高招办审核通过后转为预录取名单；考生在规定时间内对预录结果进行确认， 如同时被多所院校预录取的，只能选择并确认一所，如考生逾期未确认，则由系 统按照考生所填报志愿的先后顺序进行确认。此模式下，考生的投档机会和录取 机会都大大增加了。不但填报志愿更加容易，而且投档后落选的风险也大为降低 【2 3 1 。 两南人学硕十学伊论文 图2 - 3 一档多投模式的流程图 2 1 4 三种模式的区别 目前，我国高校招生录取方式正在经历顺序志愿一平行志愿_ 一档多投 模式的逐渐转变过程。三种模式的区别如表2 1 所示： 表2 1 顺序志愿、平行志愿、一档多投的区别口钉 2 2招生录取算法 2 2 1g s a g a l e s h a p l e y 算法( g s a ) 【18 1 最早是由g a l e 和s h a p l e y 在大学招生模型中提出 来的。他们定义大学招生模型为 c , s ，q ，只，p c ) 五元组： 1 ) 考生集合s = s 。，s ：，s 。) ； 1 2 第2 章相犬理论与技术基础 i i 2 ) 院校集合c = c 1 ，c 2 ，c m ； 3 ) 计划人数向量g = ( q c l , g 咖q 。) ，是院校专业队列c j 的计划招生人数； 4 ) 全体学生的偏好集合p s = e 。，p s ：，p 舳) ，p s t 表示学生& 对所有学校c 和不 上学c o 的严格偏好； 5 ) 全部学校的偏好集合p 。= p c 。，r ：，p 矗) ，p 。表示学校c ，对所有学生s 的严 格偏好； 6 ) 匹配函数：s - - - c u c o ，满足v