| 操作系统 办公 实用知识 设计 开发 WEB开发 移动开发 数据库 软件工程 网管 安全 管理 信息化 答疑 渠道 |
基于数据挖掘的课程相关 性方法研究与实现随着基于网络的信息系统的大范围应用，大量的历史数据为辅助决策奠定了极好的基础。在基于校园网络的教学管理系统中，随着应用，有关教学的信息已具备形成一个教学信息数据仓库的条件。另一方面，教学规模的扩大，教务管理人员以及任课教师很难再像从前那样直接根据学生的成绩数据分布找出诸如前期课程与后继课程的关系，并据此进行教学进程的决策。因此借助于相应的数据挖掘工具，发现数据中隐藏的课程相关规律或模式，为决策提供支持，是非常必要的，也是可行的。 关联规则是当前数据挖掘研究的主要模式之一，侧重于确定数据中不同领域之间的联系，找出满足给定支持度和可信度阈值的多个域之间的依赖关系。挖掘关联规则是指在数据仓库中挖出具有这种形式的规则：由于某些事件的发生而引起另外一些事件的发生。例如，在学生成绩数据库中，我们可以发现 “《离散数学》成绩80分以上的学生,《数据结构》成绩也是80分以上的可能性是66%”，这样，我们可以加强《离散数学》课的教学，以此来提高《数据结构》课的教学效果。 1. 课程相关的关联规则的形式定义 我们以学生成绩库中的学生成绩为例来形式化地描述课程相关的关联规则。 设I={i1， i2， ...， iM}为学生课程的集合，D={ t1， t2， ...， tN，... }为学生的成绩库记录的集合，其中ti ÍI(1≤i≤N)并且只含有满足条件的课程名，例如满足课程成绩为优或者成绩高于80分。 其关联规则是形如下式的蕴含式： 其中{p1，p2，…pn}ÌI，{q1，q2，…qm}ÌI， {p1，p2，…pn}∩{q1，q2，…qm}=Φ。 下面给出可信度和支持度的定义。设每个规则蕴含式的左部{p1，p2，…pn}定义的项集为B，右部{q1，q2，…qm}定义的项集为H，它们都是原始项集I的子集。令G=H∪B，表示同时支持H和B的项集。定义规则的可信度C=|G| / |B|，支持度S=|G| / |D|。例如，在1000条学生成绩记录中有300条显示《离散数学》成绩优秀，而这300条记录中又有150条《数据结构》成绩优秀，则规则《离散数学》成绩优秀就会《数据结构》成绩优秀的可信度C=150/300=0.5，支持度S=150/1000=0.15。 从语义的角度来分析，规则的可信度表示这条规则的正确程度；支持度表示用这条规则可以推出百分之几的目标，即这一规则对于整体数据的重要程度。用户可以定义二个阈值，要求数据挖掘系统所生成的规则的支持度和可信度都不小于给定的阈值。 这样，我们就用蕴含式，支持度和可信度唯一标识了每一个挖掘出来的关联规则。例如，我们可以这样表示上面提到的例子： 《离散数学》成绩优秀→《数据结构》成绩优秀，C=0.50，S=0.15 2．数据挖掘算法 经典的Apriori算法，其关联规则的开采问题可以分解成以下两个子问题： ②利用频繁项目集生成所需要的关联规则。对于每一个频繁项目集A，找出A的所有非空子集a，如果比率support(A)/support(a)≥minconf，就生成关联规则a→(A-a)。 由于第2个子问题较为容易和直观，目前大量的研究工作主要都集中在第1个子问题上。 针对我们的特定问题，我们采用了如下方式。 2.1事务数据库数据结构 在经典的数据挖掘方法中，事务数据库多采用横向结构，如学生成绩数据库： 其中，每个学生为一个事务，该事务包含此学生的所有数据。但是这样的结构并不符合 我们通常的管理系统的结构。目前我们使用的学生成绩管理系统采用的结构为纵向结构，如下表，每个学生可以有多条纪录，每条纪录包含有相对较多的信息。考虑到该数据库很庞大，若将其转换成横向方式会花费较多的时间，同时形成一个新的数据库也会占用很多的存储空间，因此我们决定采用原数据库的结构，只在挖掘算法上加以调整。 2.2挖掘算法 挖掘算法采用经典的Apriori算法，考虑到采用纵向数据结构，在算法上作了一些调整。 算法如下： L1=find-frequent_l_itemsets(D); For(k=2;Lk-1≠Ф,k++){ Ck=apriori_gen(Lk-1,min_sup); for each c∈Ck { // scan D for counts c.count++; } Lk={c∈Ck|c.count≥min_sup} } return L=∪kLk; procedere apriori_gen(Lk-1:frequent(k-1)-itemsets;min_sup:minimum support threshold) for each itemset l1∈Lk-1 for each itemset l2∈Lk-1 if (l1[1]=l2[1])∧(l1[2]=l2[2])∧ … (l1[k-2]=l2[k-2])∧(l1[k-1]=l2[k-1]) then { c=l1 join l2; file://join step;generate candidates if has_infrequent_subset(c,Lk-1) then delete c file://prune step:remove unfruitful candidate else add c to Ck; } return Ck;
procedure has_infrequent_subset(c:candidate k-itemset; Lk-1:frequent(k-1)-itemset)； for each (k-1)-subset s of c if s Lk-1 then return TRUE; return false; Apriori方法在由候选频繁项目集确定频繁项目集时只需扫描一遍数据库即可得到所需结果，但由于我们的数据库采用纵向结构，每个事务的数据分布在许多条纪录中，故我们改进算法，为侯选频繁项目集的每一个项目，逐遍扫描事务库，以得到所需数据。 由于事务数据库十分庞大，目前的研究大都围绕着减少扫描事务库的次数来缩小挖掘的时间[2][3][4][5]，而我们却反其道而行之，此方法是否可行呢？为此我们采取了两项技术： (1) 从数据库实现技术上着手，通过SQL中数据查询的集合特性、查询的可嵌套性，在循环中设计了一条SQL语句： select count(*) from k1999 where(km=kc1 and (xh in(select xh from k1999 where km=kc2 and (xh in(select xh from k1999 where km=kc3 and ……..kscj>80)) and kscj>80)) and kscj>80)； 语句中kc1,kc2,…为不同课程。 该语句可以一次求出几门功课同时为优秀的学生人数，有效地减少了程序的循环量和信息搜索量，从而大大地提高程序的运行效率。 而相对于经典Apriori方法，虽然求每个频繁项目集只需扫描一遍数据库，但在其扫描过程中需要求出每个事务所包含的候选项目，再对其统计、累加，也需要花费一定的时间，因此从这一方面看，我们采取的方法是可行的。 (2) 采用分时挖掘的方法，如下所述。 3. 分时挖掘方法 事务数据库通常是逐年生成的，其中很多数据是我们在进行挖掘时已经使用过的，而且也已经产生了许多有效数据，若我们在以后的挖掘中丢掉以前的数据重新进行，既浪费了资源又浪费了时间； 因此我们提出分时挖掘的方法，即将前面挖掘时产生的数据保留下来，以后在挖掘时只对新数据进行处理，可很大地提高挖掘速度。 如：第一次挖掘时使用了1997，1998，1999，2000四个学年的数据，生成频繁1项集如下： 由频繁1项集生成频繁2项集如下：
以此类推，将生成的n个项集在挖掘结束时保留下来，如在2001年结束时我们再进行挖掘，则我们只需扫描2001年的数据，将这一年的数据如选课人数、成绩优秀人数累加到原来的数据上，重新计算支持度即可。 这只是理想情况，即支持度不变的情况。但通常情况下支持度是需要随机调整的。 我们在研究中发现：从候选频繁2项集得到频繁2项集时开销最大，从而导致了算法效率的瓶颈，解决了这一问题，可以提升挖掘速度。因此我们只考虑候选频繁2项集的分时挖掘。挖掘算法如下： Open history_record; file://check history_record If empty then { C1=find-candidate-frequent_l_itemsets(D); C2=apriori_gen(L1,least_sup); file://set least_sup that you recognized For each c∈Ck { file://scan D for counts c.count++; } } else { if have_new_data then { file://check D locate new_data; For each c∈Ck { file://scan new_data in D for counts c.count++; } } else { L2=filter(c∈C2|sup≥min_sup); For(k=3;Lk-1≠Ф,k++){ Ck=apriori_gen(Lk-1,min_sup); for each c∈Ck { file://scan D for counts c.count++; } Lk={c∈Ck|c.count≥min_sup} } } return L=∪kLk; apriori_gen(Lk-1,0)函数未变。 系统需要再设置一个支持度least_sup，这一支持度是用户认可的最小的，而且在系统运行中不可改变的，也可以定义为0。这样，在每一个不同的时间进行数据挖掘时，系统中会永久保留支持度为0（或用户设定的任意数）的候选1项集和候选2 项集，当系统需要运行时，首先采用数据库的过滤技术，可以很快得到频繁2项集。突破了这一瓶颈，系统运行速度将得到较大的提升。 4．结束语 通过研究，我们使用上述算法进行课程相关性分析，设定其不变的最小支持度least_sup为0.2，较之使用传统方法，挖掘速度有较大提高。同时进一步证明了关联规则在课程相关性分析上的有效性和实用性，这将为学生在课程学习中进行有关的决策提供一定的帮助。 作者简介： 曲守宁： 济南大学计算机应用技术学科关键岗位教授，男，1962年9月生，硕士生导师，信息学院副院长，山东省计算机学会理事、济南市计算机学会理事。主要从事网络数据库及信息系统方面的教学科研工作，承担国家863计划、国家面向21世纪教学改革项目和省部级计划项目5项，发表论文30多篇，获省部级成果奖4项。
今日推荐
|
重点推荐
领军企业技术文库
+更多领军技术文库
最新专题
电子杂志订阅
| ||||||||
