基于主成分分析的高校排课算法研究

基于主成分分析的高校排课算法研究

赵高长a，覃飞b

(西安科技大学a.理学院; b.教务处, 西安710054)

摘要：通过充分市场调研，搜集目前高校排课所涉及的各种因素，然后对所有因素进行定性分析，提取出具有研究价值的几种因素，运用统计学方法，包括SPSS相关性分析法及主成分分析法，对影响排课效果的各因素进行定量分析，给出了一种排课主因素选择模型，最终找到制约排课效果的核心关键因素，得到了排课过程中所需考虑的软约束指标及其优先级顺序。本文解决了排课过程考虑因素多、过程复杂的问题，为高校排课完全自动化奠定了理论基础，同时也对其他类似二分图匹配问题有一定的指导作用。

关键词：主成分分析; 相关性分析; 软约束指标; 二分图

收稿日期:2014-12-08

基金项目:国家自然科学基金资助(41271518)

作者简介:赵高长(1965-)，男，陕西大荔人，教授，主要从事数学教学与算法应用研究。

中图分类号：TP301.6文献标志码：A

0引言

高校排课是一项既基本又至关重要的教学管理工作，是高校建立稳定教学秩序的基本保证。高校排课问题一直以来是国内外广大学者的研究课题，随着高等教育改革的不断深入，办学规模的迅速扩大，新的教育体制对排课提出了更高的要求，因此排课问题变得更加的复杂、棘手。那么，如何做好排课工作呢？光是靠排课模型的改进和排课算法的完善是不够的，不同的学校，由于环境的不同，实际情况的多样性，对排课的要求就不一样，所采用的排课模型和算法也就不同，但是目的都是为了找出适合自己学校的最佳排课方案，那么首要解决的就是掌握影响排课效果的各种因素，抓住重点，从实际情况出发进行分析，掌握各因素间的关联及其重要性，为后期排课问题的求解建立理论基础。

排课问题可以看作是一个资源的合理分配问题，是维持学校教学工作正常运行的基本保障。排课的合理性和可行性要求：在任意一段时间内，教师不冲突，授课不冲突，授课的班级不冲突，教室占用不冲突等。这是一个典型的多因素组合优化和不确定性调度问题，是解决对时间和空间资源争夺而引起的冲突问题。排课问题的求解就是找出各个因素之间的关联关系，充分的利用教学资源，课程、教室、教师、学生、时间、教学区域、院系等各因素之间的关系，坚持以人为本，效率优先，严格执行教学计划，正确落实教学任务，合理、有序、系统的做好排课工作。

早在50年代末，国外就有人开始研究排课问题。1962年，Gotlieb曾提出一个课表问题的数学模型，并使用匈牙利算法求解[1]；此后，人们对排课问题的因素分析、排课算法、解的存在性等问题做了很多深入探讨,使得人们对排课问题有更加深入的认识。近40年来,人们利用计算机的优越性，也对课表问题的计算机解法做了许多尝试。此外,有些文献通过图论知识，运用图的染色方法尝试解决排课问题[2]；早在70年代S.Even证明了排课问题是一个NP完全问题[3]，即此算法的计算时间是呈指数增长的，这一论断确立了排课问题的理论深度。其实好多研究都是从理论基础上分析研究，但是实际的复杂度远远超乎想象。进入90年代,国外对排课问题的研究仍然非常活跃。如印度Vastapur大学管理学院的Arabinda Tripathy、加拿大Montreal大学的Jean Anbin和JacquesA.Ferland以及Charles Fleutent等[4]。渐曲inda知pathy的工作是针对以“人”为单位进行课表编排的,他运用拉格朗日松弛法和分支定界技术求解,这种方法的缺点是为减少变量的个数，人为造成科目间的冲突。在国内，对课表问题的研究开始于80年代初期，具有代表性的有：南京工学院的UTSS(A University Timetable Scheduling System)系统，清华大学的TISER(Timetable SchedulER)系统，大连理工大学的智能教学组织管理与课程调度系统等[5]。这些系统都是模仿手工排课过程，以“班”为单位，运用启发式函数来进行编排的；但是这些课表编排系统往往比较依赖于各个学校的教学体制，不宜进行大面积推广。如今，排课问题依然是广大学者喜爱研究的课题，新的算法和方法不断涌现，使得排课工作不段完善和健全，充分的提升了教学质量，适应了发展的需求。

本文的目的是了解和分析目前影响排课效果的各种因素，找出制约排课效果的各因素间的内在联系，探索出潜在的真正因素，分析出各因素对排课效果的影响程度。把理论分析得到的结论和实际情况相比较，分析其合理性，通过对比，寻找出现有排课现状的一些不足，加以完善。本文给出了排课问题建模时的理论依据，验证了其合理性和可靠性，文章所得到的结论能使排课模型的建立变得更加完善；使排课问题得到更完美的解决。

1模型准备

通过一个月左右对不同高校师生及教务工作人员的的调研及材料的整理和分析，基本掌握了当前形势下所有的制约排课效果的各种因素，进行初步的定性分析。可得下面汇总表：

表1　因素汇总表

对调研的所有这些因素进行分析，归纳总结如下，具体的可归为以下几类：

(1)教学计划。规定了各个专业的课程性质及其各学期课程的分布情况，是安排教学进程和落实教学任务的核心文件，具有一定的稳定性和权威性，对排课效果影响显著。

(2)教师资源。反映在这么几个方面：教师的数量、教师工作量的不平衡和教师的个性化要求，满足教师的个性化要求是学校以人为本的具体体现。

(3)合班问题的合理性分析。对排课效果的影响主要指合班的数量和合班的方式，经验总结合班问题是排课的难点，一般合班数量越多课表越难安排。

(4)教室资源。指各种教室数量，教室属性。如体育场地、实验室、设计室、多媒体及非多媒体教室等。

(5)课程性质。包括课程的学分高低及周学时安排，对排课效果影响显著，多学时，高学分的课程需要优先考虑安排；而且需安排在教学黄金时间段。

(6)时间因素。指不同类别课程上课时间的安排，某些重要的公选课及专业课需安排在上课黄金时间，有些特殊要求的课安排需考虑实际要求。[6]

这次共发出550份问卷，最终回收524份，为了获得好的实验效果，首先对所获得的500多份调查问卷进行整理排查，去除一部分填写不完整度过高，数据缺乏可靠性问卷，在对问卷按院校进行归类，去除院校数量特别少的问卷，在将问卷进行打乱，从其中随机抽取100份问卷样本作为分析材料。

对满意度Y及各因素(Xi),通过SPSS进行相关分析得下表。

表2　Y与X的相关性分析(部分)：

**.在置信度(双测)为 0.01 时，相关性是显著的。

*.在置信度(双测)为 0.05 时，相关性是显著的。

根据相关性分析(correlation analysis)原理，Spearman等级相关系数r在(-1，1)之间，其绝对值越接近于1，表示相关密切程度越大，由表可以看出自变量X10与Y相关性显著相关(P=0.003<0.01)但是r=0.298表示比起其他因素(如X1与Y显著相关：r=0.794)与Y相关性不强，X11与Y不相关(r=0.151)，X13，X16，X17，X18(P>0.5，)与因变量Y基本不相关 ，表示对排课效果的影响甚微，姑且我们进行因素剔除，一般在相关性分析时，如果因素比较多，就可以考虑剔除相关性低于0.5的因素(X10，X11，X13，X16，X17，X18)。得到初步判定影响排课效果的主要因素14个，但是这些因素之间又存在着关联和影响，仍需我们探索，下面通过因子分析法来寻找因素间的联系。

2建立模型

因子分析中有多种确定因子变量的方法，其中主成分模型的主成分分析法是使用最普遍的因子分析方法之一。主成分分析通过坐标变换将原有的P个相关变量xi作线性变化，转换为另外一组不相关的变量，可以表示为：

(1)

其中u1k+u2k+…+upk=1,(k=1,2,3,…,p)，F1,F2…,Fp为原有变量的第1、第2、…第p个主成分。其中F1在总方差中占的比例最大，综合原有变量的能力最强，其主成分在总方差中占的比例最大，综合原有变量的能力最强，其余主成分在总方差中占的比例逐渐减少，即综合原有变量的能力依次减弱。主成分分析就是选取前几个方差最大的主成分，这样达到了因子分析较少变量的目的，同时又能以较少的变量反映原有变量的绝大部分信息。

主成分分析步骤如下[7]：

(1)数据的标准化处理

(2) 计算数据[xij]n×p的协方差矩阵R。

(3)求R的前m个特征值：λ1≥λ2≥…≥λm，以及对应的特征值向量u1,u2,…um。

(4)求m个变量的因子载荷矩阵。

(2)

用因子的累积方差贡献率确定m

前m个因子的累计方差贡献率计算方法为：

(3)

若数据已经标准化，则

(4)

一般方差的累计贡献率应在85%以上表示主成分法效果良好。本例分析结果如下：

表3　主成分表

提取方法：主成份分析。

表3给出了每个公因子所解释的方差，以及所解释方差的累计和，前6个因子提取平方和累积91.51%，远远高于85%，可以很好的解释基本所有变量所涵盖的信息。旋转后的累计贡献率也为91.51%，由此可以看出，影响排课的14个主要因素实际上可以用6个潜藏的本质因素所解释，这就是我们所寻找的潜在因素。本例中，累计贡献率高于90%，说明主成分分析的效果很好。

图1　因子贡献率的走势

图1是初始特征值的碎石图，是按照上面的“初始特征值”栏下的“合计列”作出的图形，并按照降序排列，观察看出，第六个因子后特征值变化趋缓，故而选取6个公因子较为合适。

表4　旋转成分矩阵表

提取方法 :主成分分析法。

旋转法 :具有 Kaiser 标准化的正交旋转法，旋转在 7 次迭代后收敛。

通过上面表4分析已经得出影响高校排课效果的6大主要因素，通过旋转成分矩阵，我们将相关联程度大的因素归类，第一主成分包括因素(X3，X4，X20，X6，X15)，第二主成分包括因素(X8，X9，X1)，第三主成分包括因素(X19，X12)，第四主成分包括(X14)，第五主成分(X2，X7)，第六主成分(X5)。

其中第一主成分的得分最高为最主要因素,其次为第二主成分,依次排之。其每个主成分的得分可由因子得分系数矩阵得出:

表5　成分得分矩阵表

提取方法 :主成分分析法。

旋转法 :具有 Kaiser 标准化的正交旋转法。

由表5看出，第一主成分中因素X3=0.537，X4=0.521得分最高，第二主成分X8=0.677，第三主成分X19=0.756，第四主成分X14=0.897，第五主成分X2=0.816，第六主成分X5=0.935最高。这些得分最高表示对主成分的贡献最大 ，起决定性作用。本课题中，指这些因素是制约排课效果软约束中最具代表性的，是建模的依据。

通过问卷分析，我们寻找出潜在的共同因素，命名为第一主成分因子：课程性质因素，反映了课程的学分，课程的属性，如公选课，专业课和选修课，排课时需考虑，公选课为全校都必须学的主要基础课程，需优先考虑安排，其次专业课，要安排在适合的最佳学习时间，选修课，可以放在晚上或周末学习。第二主成分因子：时间因素，反映上课时间的的安排，课程的时间分布，对排课效果影响甚大。第三主成分因子：教师因素，反映教师的工作量及个性化要求。满足教师个性化要求是学校以人为本的重要体现，排课时需考虑每个老师的具体情况，排课要做到人性化安排，尽可能让老师满意。第四主成分因子：教室因素，反映教室属性与所上课程属性一致，一般学校的多媒体教室和体育场所及实验室资源比较短缺，因此对此类有需求的课程需重点考虑，优先安排。第五主成分因子：学时因素，学时大的课程理论上需优先考虑排课，会产生好的排课效果。第六主成分因子：合班情况，反映教室所容纳的人数，包括合班的数量及合班的方式，实践证明合班数量越多，课表就越难安排。

3结语

本文从影响排课效果的各因素出发，详细进行了探讨，先结合现状和定性分析，给出了排课问题所考虑的各个因素的初步判定，并进行因素汇总和分类，给出了分析结果，其次从具有研究价值排课问题的软约束出发，以调查问卷的形式将问题进行量化，并运用统计学方法，采用SPSS19.0进行数据处理，得到了我们预期的效果，定性分析与定量分析相结合，定量分析的结果验证了定性分析的理论，使得我们对影响排课效果的因素有了更深入的认识和理解，明白了其关联和重要性，同时通过调查也了解到当前形势下高校的排课现状，这对做好排课工作是非常有意义的。我们接着介绍了一种基于主成分分析的排课因素优先级排序模型，这部分的研究是以建立在各因素统计分析的结果之上的，目的是为了更科学的搞明白制约排课效果的诸因素的重要程度，为我们提供了排课问题的一种新思路，在进行排课建模时，完全可以按主成分分析的结果，选取每个主成分中得分系数最大的，即权重最大的作为代表，具有很好的解释性，即诸因素影响排课效果的优先级排序：由大到小为教室属性，合班数量，课程性质，教师工作量，周学时，时间安排，学分数。在以后排课中，不会盲目的考虑一些制约条件，本文的研究给出了明确的方向，是排课问题的核心，为排课工作的顺利展开奠定了理论依据，同时也对当前形势下的高校排课情况有了全面而科学的认识。

参考文献:

[1]GareyM R,JohnsonD S. Compute and Intractability: A Guide to the theory of NP completeness [M]. San francisco:W. H, Freem an Co.1979.

[2]王仲华,卢娇丽. 图论在高校排课问题中的应用研究[J].太原师范大学学报(自然科学报),2010(3)：39-42.

[3]张春梅,行飞,梁治安. 课表的多指标数学模型及解决方法[J]. 内蒙古大学学报(自然科学报),2004(3):139-144.

[4]赵静,但琦. 数学建模与数学实验[M]. 北京: 高等教育出版社,2003.

[5]卢志翔,蓝玉龙,周秀梅. 高校排课系统的算法与研究[J]. 教育前沿(理论版),2008(12)：106-107.

[6]王俊生,戴云龙. 基于层次分析法的自动排课优先级模型[J]. 现代教育技术报,2009(11):32-35.

[7]骆方,刘红云,黄崑.SPSS数据统计与分析[M]. 北京：清华大学出版社,2011.

责任编辑：程艳艳

Research on Algorithm of University Course Scheduling Based on Principal Component Analysis

ZHAO Gaochanga，QIN Feib

(a. College of Science; b. Office of Academic Affairs, Xi’an University of Science and Technology, Xi’an 710054, China)

Abstract：By adequate market survey, all factors that current universities’ course scheduling concern are collected, then analyzed qualitatively, several factors with great research value are extracted. This research utilizes statistics method, including SPSS correlation analysis and principal component analysis, to make a qualitative analysis on each factor influencing the effectiveness of course scheduling, presents a selection model of main factors, finds out the key factors restricting effectiveness of course scheduling and obtains the soft constraint index and its priority order that need considering in the process of course arrangement. This paper solves such problems as numerous factors and complex procedures, which lays a theoretical foundation for full automation of universities’ course scheduling and provides a guiding role for other similar bipartite graph matching problems.

Keywords：principal component analysis； correlation analysis； soft constraint index； bipartite graph