选课算法（精选4篇）
选课算法 篇1
0 引 言
选课是学分制实施过程中非常重要的一个组成部分,在绝大多数选课系统中所使用的算法都是抽签算法,该算法虽然公平、合理,但由于抽签时的随机性太大,因而最终的选课结果可能与学生的期望结果相差较大。基于此,本文提出了一种参考权值的抽签方法,从而使得选课结果更加合理、科学,更加体现人性化管理理念[1]。
1 抽签算法基本思想
抽签算法是把整个选课过程分为两个阶段:预选课阶段和抽签确定阶段[2]。在预选课阶段,学校教务管理部门首先要设置选课的基本条件(对学生选课资格的限制和对所选课程的限制等)和选课时间(起止时间)。然后每位学生按预先设置的选课规则进行选课;抽签确定阶段,预选结束后,并不会立即得到自己期望的结果,自己所选课程能否有效,还需等待教务管理员根据选课的实际情况进行抽签处理,处理完成后才可生成有效课表。
在抽签时,首先应规定一个开课人数限制的底限和上限,假设某门课程的选课人数达不到开课规定人数,可以让学生重选或取消该门课程的开课资格。当开课底限达到了,然后再看某门课程的选课人数是否超过上限,没有超过上限时,则将所有学生全部列入课表,如果超过了上限,则采用平均分布概率进行相应处理,对没有抽中签的同学,学校教务部门可另行通知重新选课[3]。在整个过程中,选课结果和选课的时间先后没有任何关系。
2 抽签算法评估
该算法尽最大的限度满足了学生选课的基本愿望与要求,使得每个学生在选择过程中保持平等的选择权利,最终的结果也相对平等、合理、科学。但是抽签后的结果很难达到所有同学所期望的满意度,因为它没有考虑体现人性化的管理理念[4]。为此,对原始的抽签算法进行的改进,形成一个改进的抽签算法即基于权重的抽签算法。
3 基于权重抽签算法的设计
传统的抽签算法在抽签阶段利用了平均分布概率算法,使得选课的最终结果和选课时间的先后毫无关系,进而保证选课的公平性。但这种算法具有随机不确定性,最终的选课结果与学生的期望值差异较大,缺乏人性化管理理念,给选课后期的教务管理工作带来较大的麻烦。因而。为了在公平的基础上使得选课的结果更加体现学生的期望,在该系统中采用一种改进的抽签算法来解决这一问题,即采用权重抽签算法来实现[5]。
这里的权重包含2种含义:其一,是给参选的每门课程规定若干个期望选中权值;其二,是给每个参选学生赋予相应的权值,而且该权值会随时发生变化。
在选课前必须给每门参选课程设置3种期望权重值:期望选中概率高权重为8;期望选中概率一般权重为5;期望选中概率低权重为3。在预选课阶段,可以将参选学生的权值导入系统,学生选择每门课程时,必须要选择相应的权重值,为了使其更加合理,应规定,同一学生所选的课程对应的权重不能全部相同,否则,所有结果无效[6]。选课结束后,分以下几种情况处理:第1种,如果某门课程的选课人数超过最低底限而小于该门课程允许的最大容量时,则将所有选课学生列入最终名单;第2种,如果所选人数超过规定的最大容量时,则抽取选课时选择权重值高的同学列入最终名单,若该名单中人数小于等于规定的最大容量时,则将该名单中的学生列入最终名单,然后删除权重值小的记录,安排重选;如果按照课程权重值筛选的名单中人数仍然超出该课程的最大容量时,则参考学生的权重值,即把在该名单中学生权重值高的列入最终的选课名单[7]。因而在这种方法中,抽签时采用了参考权重的抽签思想,更加体现了学生选课的期望,更加科学化、合理化、人性化。该算法具体描述如下:
(1) 给每门参选课程设置期望权重值。
(2) 学生入学时,给每个学生一个平均权值。
(3) 参选课程数据、参选学生数据初始化。
(4) 学生选课。
(5) 如果某门课程的选课人数小于开课限制人数时,转(7)。
(6) 如果某门课程的选课人数大于该门课程的人数容量时,抽取选择课程期望权重值大的记录,删除权重值小的记录,转(9);若抽取人数小于等于规定的最大容量时,转(10);然后删除权重值小的记录,转(9);若按照课程权重值筛选的名单中人数仍然超出该课程的最大容量时,则参考学生的权重值,即把在该名单中学生权重值高的列入最终的选课名单,转(10)。
(7) 选择某门课程失败,转(9),但确实有特殊原因要求选择该课程,则转(8)。
(8) 临时增加选课记录,修改确认记录数。
(9) 修改选课状态信息,通知学生重新选择。
(10) 生成最终选课信息表。
基于权重抽签算法的流程图如图1所示。
4 学生权重值的动态变更
学生入学时,学校给每个学生赋予一个权重的平均值Q。
(1) 学生权重值有大的变更时根据其参与在教学活动中的奖惩为条件。具体设置如下:
上学期所选课程全部合格时权重值加1,记为q(1);
上学期受到奖励1次,则权重值加2,记为q(2);
上学期参加1次学校组织的大型活动,则权重值增加1,记为q(3);
上学期四、六级考试通过,则权重值增加1,记为q(4);
上学期受到纪律处分1次,则权重值减3,记为q(5);
上学期专业课不及格1门,则权重值减1,记为q(6);
上学期选修课1门不及格,则权重值减1,记为q(7);
上学期选修课缺课1门,则权重值减0.5,记为q(8);
上学期缺考1门课程,则权重值减3,记为q(9);
学生学籍异动1次,则权重值减6,记为q(10)。
(2) 对当前权值进行更新undefined。
5 结 语
该算法的实现受到了学生的一致好评,使得选课结果更加合理,具体体现在以下几个方面:
首先,体现了人性化管理理念。避免了传统抽签算法中抽签的随机不确定性,最大限度体现了学生选择课程的主观意愿,具有极强的人性化理念[8]。
其次,避免了学生盲目选课。在以往的选课中,学生对于课程的选择茫无头绪,对能不能选中没有任何的把握,而权重抽签算法就要求学生选择课程的权值,这样在抽签时基本保证了期望值高的学生能够选择到该课程[9]。
最后,有利于教学管理和加强学风。 由于学生权重值的变化与学生平时参与的教学活动及其参与的各种有益活动有关,所以要想保证权值较高,必须平时严格要求自己,端正学习态度[10]。有利于学校的管理和学习风气的加强。
参考文献
[1]黄海东.网上选课系统的算法分析与改进[J].湖南职业技术学院学报,2009(1):27-28.
[2]关慧,由德凯,侯建梅.网上选课系统的设计与实现[J].沈阳化工学院学报,2004,18(4):295-298.
[3]李冰颖,夏利民,舒远仲.学分制模式下网上选课系统的算法探析[J].江西科学,2004,22(5):358-360.
[4]刘军,阳小华,黄洁.基于.NET组件技术的选课管理系统的设计[J].电脑开发与应用,2006,19(2):53-55.
[5]李金良.浙江师范大学选课系统负载平衡研究[J].计算机时代,2006(7):42-43.
[6]杨海龙.网上教务管理系统的设计与实现[J].中国科技信息,2005(8):16.
[7]章发太,陈维斌,吴金龙.华侨大学网上选课系统的设计与实现[J].计算机与现代化,2002(11):61-63.
[8]赵波.选课管理系统的设计与开发[J].云南民族学院学报:自然科学版,2002,11(4):245-248.
[9]梁里宁.网上选课系统的设计与实现[J].暨南大学学报:自然科学版,2002,23(5):39-42.
[10]尹秋菊.基于WEB混合模式信息系统研究应用[J].计算机系统应用,2002(3):13-15,8.
志愿选课算法分析与最优决策 篇2
为了解决选课报名人数虚高、凭运气选课等问题, 最大限度地满足学生的选课意愿。本学期刚刚采用的志愿法选课方式, 将学生的选课意愿引入到选课优先级的计算中, 让学生的选课意愿影响课程的选中率。
1 志愿选课算法分析
1.1 平均分布概率算法
根据概率学和统计学的规律, 动态生成分布均匀并体现随机特性的“签”, 并结合实际选课人数N、课程容量M来决定该课程的选课最终结果。
具体操作过程如下:当选课人数超出课程容量时 (N>M) , 由系统对每个选该门课程的学生分配一个随机数 (K) , 按大小排序, 较小的保留。保留的选课记录有效, 即为选中该门课程。
(1) 预选:每个学生选择自己的课程, 并按志愿排序。一共分为三个志愿, 志愿优先级依次为:第一志愿, 第二志愿, 第三志愿。
(2) 正选:计算机按课程进行处理, 对于每门课程, 按志愿优先级进行处理。
(1) 第一志愿。
处理对象:第一志愿选课人数N1, 课程容量M1。
若第一志愿选课人数不大于于该课程的限选人数 (N1≤M1) , 则全部选中。
若第一志愿选课人数超过该课程的限选人数 (N1>M1) , 采用平均分布概率算法来进行处理。
(2) 第二志愿。
处理对象:第二志愿选课人数N2, 课程容量M2=max{0, M1-N1}。
若第二志愿选课人数不大于于该课程的限选人数 (N2≤M2) , 则全部选中。
若第二志愿选课人数超过该课程的限选人数 (N2>M2) , 采用平均分布概率算法来进行处理。
(3) 第三志愿。
处理对象:第三志愿选课人数N3, 课程容量M3=max{0, M2-N2}。
若第三志愿选课人数不大于于该课程的限选人数 (N2≤M2) , 则全部选中。
若第三志愿选课人数超过该课程的限选人数 (N2>M2) , 采用平均分布概率算法来进行处理。
1.2 志愿法选课中的不足之处
就像高考填报志愿一样, 志愿法选课也存在风险。如果志愿填报得不好, 比如一味填报热门课程, 很可能一门课程都选不上。但是为了让选课结果使自己更加满意, 我们建立了志愿法选课的模型, 利用动态规划和目标规划提出优化方案, 并编程实现, 得到一个合理的志愿分配方案, 使选课的结果最让人满意。
1.3 动态规划模型的建立
设总共要选n门课程, 每门课程的课容量为ai, 个人偏好为ci, 目前报本门课程为第一志愿的人数共有bi1, 第二志愿人数bi2, 第三志愿人数bi3, 用以上介绍的算法选人, pi为能选上这门课的概率 (i=1, 2, …n) , 若选本门课程, 则xi=1, 否则xi=0。要使选课的结果最优, 即求x1, x2, …, xn, 使max f=c1p1x1+c2p2x2+…+cnpnxn。约束条件:第一志愿限一门, 第二志愿限一门, 第三志愿可选多门。
要用动态规划方法求解, 首先把选课过程划分为三个时段:选择第一志愿阶段、选择第二志愿阶段和选择第三志愿阶段。
按照每门课的课容量和填报三个志愿的人数的关系, 可把不同的课程分为四种类型。
如表1所示。
在第一志愿阶段中的状态是第一类和
第二类的所有课程 (图中课程1、课程2、课程i等属第一类或第二类课程) 。
在第二志愿阶段中的状态是由第一阶段到达第二类和第三类的所有课程 (图中课程m、课程m+1、课程k等属第二类或第三类课程, 且出发地与目的地不相同) 。
在第三志愿阶段中的状态是由第二阶段到达第三类和第四类的所有课程 (图中课程t、课程t+1、课程s等属第二类或第三类课程, 且出发地与目的地不相同) 。
如图1所示。
1.4 动态规划模型的求解
用顺序解法求解。v表示课程。
阶段k=1时:
阶段k=2时:
f2 (v1到m) =f1 (v1) +cmpm, u2 (v1到m) =v1
f2 (vi到k) =f1 (vi) +ckpk, u2 (vi到k) =vi
阶段k=3时:
f3 (v{1, m}到t) =f2 (v到1m) +ctp到t, u3 (v{1, m}t) =v到1m…
f到3 (v{i, k}到s) =f2 (v到ik) +csps, u3 (v{i, k}s) =vi到k
max (f可求得使其为3) 为最优值, 逆推, 最优值的最优决策。
1.5 动态规划程序实现
(1) 优化决策实例。
如图2所示。
(2) 对结果的解释和说明。
如图2所示, 输入自己对十门课程喜欢程度, 然后由教学门户查得每门课的课程容量和第一、二、三志愿选课人数。程序根据输入的数据, 经规划后给出第一、二、三志愿的安排, 并给出最优安排下的满意程度。对于那些确定选不上及在第一二志愿已使用的情况下第三志愿肯定远不上的课程, 程序判断为不选。
图2所示最优规划, 与使用枚举法得出的结果一致。
由于该优化实现是建立在已知第一、二、三志愿的基础上的, 而实际选课时这些数据是实时变化的, 因此模型只能在一定程度上给出参考, 且越接近选课结束时间得到的优化方案参考价值越大。
2 结语
我们最终放弃了高维模型。
编程实现也是一个难点。由于选不同课程人数和课容量有众多种情况, 在最初编程时有很多不完善的地方。调试阶段花的时间是编程的3倍左右, 期间通过不断地测试数据一一修改不完善的地方, 最终程序已经比较完善。
志愿选课法刚推出的几天, 我们便以敏锐的洞察力, 选取了以它作为背景的研究题目。从确定选题之后, 探讨了选课时可能出现的各种状况, 并一步步简化模型, 由最初设想的不确定性决策分析到随机型限期采购问题再到最长路径动态规划, 并最终确定模型为0-1目标规划+多阶段动态规划。我们深深地体会到, 在建模和求解的过程中, 最大的问题并不是模型的建立, 而是模型的求解。面对高维动态规划, 理论上求解的复杂性及计算机实现上的各种问题让图2
摘要：本文以新的选课方式为背景, 结合同学们在选课中的偏好和需求, 对志愿法选课建立模型, 提出志愿优化分配的算法, 使得合理分配志愿而选课满意程度高。
关键词：选课算法,志愿法选课,目标规划,动态规划
参考文献
[1]胡运权.运筹学基础[M].清华大学出版社.
[2]王焕刚.运筹学动态规划讲义[J].清华大学自动化系.
[3] (美) Sharon Allen.数据建模基础教程[M].清华大学出版社.
[4]李舒亮.网络选课系统中常用算法分析[J].新宇高专学报.
选课算法 篇3
目前在高校中大多都已经实行了选课制,随着网络的普及,网上选课系统的出现,随之而来的选课算法也不断地出现和改进,而且越来越体现出选课的公平和公正性。最简单的先来先服务算法是根据选课时间的先后进行选课操作,当选课人数达到最大限选人数时即结束;若学生为了选到自己喜欢的课都在同一时间段内进行选课,容易造成网络拥堵,而且由于网速的问题也可能出现学生先选的不一定先得到服务[1]。抽签算法主要用于处理选课人数超过限选人数的情况。对于抽签算法,抽签的方法又不尽相同,总结起来有随机抽取、按权重高低抽取和各种优先排列抽取等[2]。目前常用的优先排列抽取主要有专业优先算法,成绩优先算法,按名额分配比例算法,志愿分级筛选算法等。长期实践表明,不同的算法各有其优缺点,适合于不同的选课处理。
由于学生每学期的权重值区分不大,按权重高低抽取方式的抽签算法也不是很实用或实用于很小的范围。专业优先算法比较适用专业选修课的选课处理,适用于小范围的专业课选课,不适合全校性公共课选课。而按名额比例分配算法类似于平均主义,没有真正考虑到学生的需求,该算法在具体的实现上还比较复杂。志愿分级筛选算法原理清晰,是目前网络选课的主流算法,该算法实现起来较容易,而且操作简单,系统开销也不大,运算速度较快,是性能优越的选课算法[3]。
1 志愿分级筛选算法
志愿分级筛选算法采用实时选课处理和后台批处理相结合的方法来实现的,即分为预选和正选两个阶段。
1.1 预选阶段
在指定的时间内,学生登录选课系统进行选课操作。此时在选课过程中允许每个学生在选课时对于有多个课程班(课程名称、任课教师、上课时间和上课地点相同的学生称为一个课程班)的课程或要求学生选课必须有多个(一般3个)志愿时,可以有3个优先级不同的志愿选择,其原理类似于高考录取时数据的处理[4]。预选课期间每个学生都具有平等的选课权利,当预选结束后,才进行后台正选处理。这样就防止了学生集中时间登录选课,克服了先来先服务算法的弊病。
1.2 正选阶段
计算机按不同的志愿相继进行处理。首先处理第一志愿,若第一志愿人数(N1)超过该课程限选人数(M),即N1>M时,采用平均分布概率算法来进行处理,从N1人中筛选出M人,此时不再处理二、三志愿;若第一志愿人数(N1)小于等于该课程限选人数(M),即N1≤M时,全部选中。当所有第一志愿课程班遍历完后,对于未选满的课程班再遍历第二志愿,此时第二志愿的最大限选人数是M-N1,处理方法同第一志愿,以此类推,接着再遍历第三志愿[5,6]。如果该门课名额未满,可以公布选课结果进行补报,若补报后选课总人数超过该门课的限选人数时,先前处理的有效选课记录不参加下一轮筛选,后来补报的学生采用平均分布概率算法来进行处理,若有需要,选课将采用多轮筛选。经过预选和正选两个阶段后,可能有少数学生3个志愿都未选中,此时需人工干预处理,最终产生课表[7]。
1.3 志愿分级筛选算法优缺点
该算法是当所有学生预选均结束后,才进行处理的,选课结果与选课先后次序无关,从而可以缓解学生之间抢先选课的矛盾,而且选课结果分布均匀,落选的机会少,做到了选课的公平。
由于学生的情况各不相同,有的学生对整个大学学习有一个完整的计划,而且在此计划前提下,能够有较高的积极性并在选择的课程上取得较好的成绩。而一部分学生是没有计划的,只是选择人多的热门课程或认为容易通过的课程,这部分学生的学习成绩通常是较差的,他们只是跟着感觉走,甚至不考虑自己的研究方向,不考虑课程本身的学习前提或课程的性质。
第一志愿往往表现出学生学习的热情,有些学生对该门课程十分感兴趣,尤其一些学习成绩优异,有很强上进心的学生。当第一志愿人数超过该课程限选人数时,采用的是平均分布概率算法,在分配随机数时,虽然是系统自动筛选的,但一些渴望学习的学生有可能就会失去选修该门课的机会,会打消学习的积极性。对于这种情况,在进行筛选的时候应该给予考虑,应该尽量满足有计划、学习好的学生的选课要求,以鼓励他们完成自己的学业,实现人生目标。
2 志愿分级筛选算法的改进
这里主要从选课前准备工作、预选和正选三方面进行改进。
2.1 选课前准备工作
在选课之前,最好是在上一学期的期末发布下一学期选课信息和各门课程的相关介绍;有条件的还可以使用选课推荐系统对学生进行课程的推荐[8],这样选课不再盲目,还可以帮助学生选择自己感兴趣的课程,提高学生的学习积极性。
2.2 预选阶段
在预选课期间,固定时间进行选课统计,随时发布预选课信息,如各门课限选人数,目前预选人数,积分排名等。学生可以在预选课期间自行调整,可以使学生第一志愿选中率提高。
2.3 正选阶段
对正选时使用的志愿分级筛选算法进行了改进,改进后的算法如下:
若第一志愿人数(N1)小于等于该课程限选人数(M),即N1≤M时,全部选中,不再处理二、三志愿;当第一志愿人数(N1)超过该课程限选人数(M)时,即N1>M时,进行如下处理:
首先查看学生的积分,统计积分大于等于θ的学生人数为N11,则积分小于θ的学生人数为N1-N11。这里的阈值θ,一般已经存在默认值,即程序运行前已经初始化。根据学校的不同情况,不同的积分规则设定的方法可以不同。例如按积分排序,取前10%的学生中最低分,或按以往的经验来确定等。若N11≤M,则全部选中,再在未选中的学生中使用平均分布概率算法选出M-N11名学生;若N11>M,则使用平均分布概率算法选出M名学生,添加到正选表中,流程图如图1所示。
当所有第一志愿课程班遍历完后,对于未选满的课程班再遍历第二志愿,此时第二志愿的最大限选人数是M-N1,处理方法同第一志愿,以此类推,接着再遍历第三志愿。
其中学生积分的设置是根据学生学习成绩,该门课程的前驱课选课情况等,可依据本校的实际情况而定,积分的判断值也可根据各校的不同而定。
该算法可以保证积分高的学生优先入选,与先前的算法相比较,参加随机筛选的人数相对减少。所以在进行平均分布概率算法时,产生的随机数的数量减少,即改进后算法中平均分布概率算法的时间复杂度是O(N1-N11),和改进前该算法的时间复杂度O(N1)相比,提高了筛选速度和运行效率。
经验表明:优秀的学生只占少数,一般情况下能够全部选中,而且剩下的名额数量还很多,即流程图中大多执行的是①②③。
以第一志愿人数(N1) 100人为例,其中前10名学生积分最大值为3,最小值为1,设定θ值为1,由于第11到第30名学生积分值是1,所以积分大于等于θ的学生人数占30%),该课程限选人数(M)为80,分别对改进前后的算法进行的测试。采用原算法产生随机数为100,优秀学生选中率为66.7%,其他学生选中率为85.7%;采用改进后算法产生随机数为80,优秀学生选中率为100%,其他学生选中率为71.4%。由此表明,改进后的选课算法可以满足大多数学生选课的愿望,减少了优秀学生落选的几率。
3 结 语
实践证明,用改进后志愿分级筛选算法设计的选课系统,更加适合学生学习的需求,使优等生可以优先选到自己感兴趣的课程。与此同时,其他学生为了选到自己满意的课程也会努力学好前驱课程,这样更好地激发了学生的学习积极性,提高了学生的学习热情。
参考文献
[1]黄海东.网上选课系统的算法分析与改进[J].淮南职业技术学院学报,2009,9(1):27-28.
[2]Ferland J A,Fleruent C.SAPHIR:Adecision support sys-temfor coursescheduling[J].Interfaces,1994,24(2):105-111.
[3]赵波.选课管理系统的设计与开发[J].云南民族学院学报:自然科学版,2002,11(4):245-248.
[4]杨海荣.基于校园网的网上选课系统的设计与实现[J].湖南税务高等专科学校学报,2003(9):55-57.
[5]李冰颖,夏利民,舒远仲.学分制模式下网上选课系统的算法探析[J].江西科学,2004,22(5):358-360.
[6]关慧,由德凯,侯建梅.网上选课系统的设计与实现[J].沈阳化上学院学报,2004,18(4):295-298.
[7]徐明.志愿随机筛选算法在选课系统中的应用[J].南通纺织职业技术学院学报,2007,7(4):33-35.
选课算法 篇4
同时,教学管理的发展也使教育研究的相关人员认识到,仅仅是选课系统的简单实现是远远不够的,如何通过学生的选课数据,经过分析和整理,得到学生选课的一些内部规律,使之为教学管理服务,应该是系统实现功能的深层次目标。这些规律可能是选课中课程直接相关联的信息,比如两门课之间的关联程度。也可能是学生学习兴趣的一个调查展示,比如某一学科的学生喜欢选哪一种类型的课程。还有可能是某些意想不到的关联情况。通过这些内在的人工无法直接得到的信息,教学管理人员可以更好的安排课程的编排思路、开课时间等等,来更好的为教学服务,最终提升学生对选课的满意度。本文引入关联规则挖掘算法FP-growth,介绍了使用该算法找出课程之间关联的方法。
1 关联规则介绍
关联规则技术是数据挖掘的最重要的组成部分之一,它用于发现大量数据中项集之间的有意义的关联和相关联系。关联规则由Agrawal等学者在1993年提出,主要的目的是从庞大的交易记录数据库中,寻找出商品项目之间的关联性[1]。这些学者提出了一种数学模型,来说明关联规则的问题定义,其描述如下:令I={I1,I2,…,In},I为所有商品项目(Items)的集合;T为每笔交易记录项目的集合,T为I的子集(T哿I);TID为每一笔交易记录的编号。关联规则的形式为“X圯Y[Support,Confidence]”,其中X、Y为项的集合,X奂I,Y奂I,X∩Y=覫,意义为“if X then Y”,X表示为因(antecedent),Y表示果(consequent)。关联规则中包含两个重要的因素:
1)支持度(Support):支持度(X)是包含项集X的交易总数占全部交易总数的比例,即X在所有交易中出现的概率。而支持度(X圯Y)表示X和Y这两个项集在所有交易中同时出现的概率。
2)可信度(Confidence):表示某事件的发生的情况下发生另一事件的概率,用来表示关联的强度。Confidence(X圯Y)表示在包含X的交易中,同时也包含Y的概率。
关联规则挖掘所要做的工作就是找出支持度和可信度分别大于用户给定的最小支持度和最小可信度的规则,因为只有满足这两个条件的规则才具有意义。关联规则挖掘工作通常主要分两个阶段:
1)找出数据库中所有频繁项目集(Frequent itemsets)。就是找出所有满足最小支持度的项目集(若一个项目集含有K个项目,则称为K-项集;若K-项集满足最小支持度,则称为K-频繁项目集)。表1示例数据库
2)根据第一阶段产生的频繁项目集产生关联规则。例如{B,C,E}为3-频繁项目集,且{B,C}圯{E}满足最小可信度,表示此关联规则成立。
2 FP-growth算法
频繁模式增长FP-growth(frequent pattern-growth)算法是由Han等人于2000年提出[2],该算法是一个很有影响力的频繁模式挖掘算法。
算法只需要扫描2次数据库:第一次扫描数据库,得到1-频繁项集;第二次扫描数据库,利用1-频繁项集过滤掉数据库中的非频繁项,同时生成FP-tree。由于FP-tree蕴涵了所有的频繁项集,其后的频繁项集的挖掘只需要在FP-tree上进行。
整个挖掘过程由两个阶段组成:第一阶段建立FP-tree,即将数据库中的事务构造成一棵FP-tree;第二阶段为挖掘FP-tree,即针对FP-tree挖掘频繁模式和关联规则。
第一阶段,FP-tree的创建。图1描述了一个基于表1所示的示例数据库构造的FP-tree的例子。
第二阶段,FP-tree的挖掘。表2列举了图1所示FP-tree挖掘的结果(最小支持度计数为2)。
算法:FP-tree构造算法
输入:事务数据集,最小支持度min_sup。
输出:FP-tree
步骤:
1)扫描事务数据集一次,得到所有频繁1-项集和及其每个的支持度,并按支持度降序排序将其存入频繁项目头指针表header table中。
2)创建FP-tree的根结点,以“null”来标记它。对于中的每个事务执行下面的操作:
a)去掉事务中的不频繁项;
b)剩下的频繁项目按照header table中的次序重新进行排列,设排序后的结果为[ρ|Р],其中ρ表示第一个项目,P表示剩余项目的列表;
c)调用子程序insert_tree([ρ|Р,T])。
子程序insert_tree([ρ|Р,T])的执行过程为:
d)如果T有子女N使得N.item_name=ρ.item_name,则N的计数加1;
e)否则创建一个新结点N,N.item_name=ρ.item_name,并将其计数设置为1,N的父指针链结到T,N的node_link链接到具有相同item_name的下一个结点。
f)如果Р非空,递归地调用insert_tree(Р,N)。
对FP-tree的挖掘通过调用FP_gorwth(FP_tree,)过程来实现。该过程实现如下:
procedure FP-growth(FP-tree,α)
if tree含单个路径P then
for路径P中每个节点组合(记为β)
产生模式β∪α,其支持度support=β中节点的最小支持度;
else for each ai在Tree的头部{
产生一个模式β=ai∪α,其支持度support=ai.support
构造β的条件模式基,然后构造β的条件FP-treeβ;
if Treeβ≠覫then
调用FP-growth(Treeβ,β);}
3 FP-growth算法在学生选课中的应用
将关联规则挖掘应用在选课系统中,可以用来分析在选课时学生会同时选择哪些课程,进而分析出其中的原因,供学生及相关教务人员参考。
一般来讲,高校选课系统数据库中主要包含以下一些数据表:
学生情况表(学号,姓名,系别、班级、密码)
教师信息表(教师ID、教师姓名、系别、密码、教师简介)
管理员表(用户ID、用户名、密码、系部)
课程表(课程编号、课程名称、开设系部)
系表(系号、系名)
开课信息表(课程编号、课程名称、教师、开课时间、上课地点、限选人数、己选人数、选课、退课)
学生选课结果表(学号、姓名、课程号、课程名、成绩)
使用关联规则算法FP-growth分析学生选课数据主要包括以下过程:
1)数据预处理
将学生选课表中的一些冗余数据进行清除,并将一些数据空缺用相关数据填充。删除一些冗余的数据项,例如有的数据项是空缺的,对其进行相关查找和对照,然后填充。消除噪声数据,例如,在选课系统的数据中,有的学生同时选择了两门一样的课程,这是不允许的,将它作为噪声数据进行处理。
2)数据集成
设计一致的数据存储过程,在对数据库的结构和挖掘的应用考虑之后,设计其存储方式,建立数据结构及存储模型,将存在于不同结构的数据库的数据集成在数据存储中。比如,在选课系统中,有些数据存储在SQLServer2000中,有些存储在Access2000中,可以将其集中存储在SQLServer2000中。设计存储的时候,要充分为将来要做的挖掘工作考虑。
3)数据变换
按照选定的主题将数据项进行变换。比如,在选课表中每位学生选一门课程就会有一条记录,这样的格式不适合将要进行的数据挖掘,必须转换成每一个学生的选课为一条记录。
4)关联规则的挖掘
将FP-growth算法应用在学生选课中,挖掘出选修课程之间隐含着的关联[3]。
调用FP-growth算法挖掘的过程如下:
4 实验及结果
我们以FP-growth算法为基础,对某高校2004级学生大学期间的选修课程数据进行了分析。试验设定最小支持度为0.15,最小置信度为0.6,表3列举了程序运行的部分结果。
以规则{钢琴经典作品赏析}→{欧美经典歌曲赏析}、{旅游景观审美}→{世界自然与文化遗产}为例,对挖掘的结果可以作出如下解释:选修《钢琴经典作品赏析》课程的同学有65%的可能性也会选修《欧美经典歌曲赏析》,选修《旅游景观审美》的同学有63%的可能性也会选修《世界自然与文化遗产》。挖掘的结果可以为学生选课提供指导。
摘要：关联规则技术是数据挖掘的最重要的组成部分之一,它用于发现大量数据中项集之间的有意义的关联和相关联系。本文介绍了使用关联规则挖掘算法FP-growth分析学生选课数据的方法。
关键词：学生选课,数据挖掘,关联规则,FP-growth
参考文献
[1]R Agrawal,T Imielinski,A Swami.Mining association rules between sets of items in large databases[M].Washington,D.C.SIG-MODp93,207-216.
[2]Jiawei Han,Micheline Kambr.Data Mining Concepts and Techniques[M].San Francisco:Morgan Kaufmann Publishers,2000.