Apriori算法在网络教学平台自动推荐学习资源功能中的应用
2016-11-03卢小华刘静
卢小华,刘静
(山西工商学院,山西 太原 030006)
Apriori算法在网络教学平台自动推荐学习资源功能中的应用
卢小华,刘静
(山西工商学院,山西 太原 030006)
主要研究了数据挖据关联规则中挖掘频繁项集的Apriori算法在教学平台中的应用,以学生进入课程中心进行学习的日志记录作为原始数据,采用Apriori算法分析知识网页间的关联,根据关联规则进行学习资源的个性化推荐,从而满足不同学生的学习需求。
关联规则;Apriori算法;教学平台;学习资源推荐
引言
随着信息技术和网络技术的快速发展,各大高校均构建了网络教学平台,但是现有的教学平台缺乏个性化功能设计,不能根据不同需求进行学习资源的自动化推荐,因此在教学平台的设计中,加入数据挖据中基于关联规则的Apriori算法对于提高学生的学习效果是很有意义的。
1 关联规则的相关概念
假设用字母D代表数据库中所有事务的集合,而每个事务用字母T来表示,事务的标识符用TID来表示,且T≠。并假设用字母I来表示数据库中所有数据项的集合,其中每一项用Im来表示,T为I的子集。假定A、B均为项集,均是T的非空子集,且A和B的交集不为空,则说明A和B是相关联的项集,既A=>B。这个推算公式就称为D中A和B的关联规则[1]。
1)D中项集X出现的次数称为支持度计数。
2)在数据事务集合D中,项目集A所在的事务数与D中总的事务数的百分比称之为A在D中的支持度,记作sup(A)[2]。
3)关联规则的一般形式为:A=>B,其含义为A出现的同时也导致B出现。则A=>B的支持度为:support(A=>B)=suppport(A∪B)=P(A∪B)=T(A∪B)/|D|
其中|T(A∪B)|代表A∪B的事务数,|D|表示事务总数,支持度代表了关联规则的频度[3]。
由用户自设的支持度的一个阈值,记作minsup。
是指数据库事务D中A和B同时出现的次数与A出现的次数之比。
confidence(A=>B)=(support(A∪B)/(support(A))
是用户设定的衡量置信度的一个阈值,表示关联规则的最低准确率,记作minconf。
对一个项目集X,如果support(X)≥min_sup,称X为频繁项目集,频繁k项集的集合通常记为Lk[4]。
如果support(A=>B) ≥minsup 且confidence(A=>B)≥minconf,称关联规则A=>B为较强规则。
如果一个项集是频繁的,那么它的所有子集(不包括空集)也一定是频繁的[5]。
2 关联规则挖掘的经典算法—Apriori算法
Apriori算法又叫逐层搜索迭代方法,它是用第k项集搜索第k+1项集[6]。算法的基本思想为:第一,首先对整个事务数据库进行扫描,统计其中每一项出现的次数。第二,找出所有支持度≥用户设定的最小支持度的项集。第三,将满足条件的所有项集作为一个集合赋给频繁1项集L1。第四,通过L1自身连接生成候选项集,将候选项进行计数,与最小支持度进行比较,将满足条件的所有项集作为一个集合赋给频繁2项集的集合L2。第五,采用同样的方法通过L2自身连接查找频繁3项集L3。第六,循环执行以上操作,直到不能产生频繁项集为止。在查找频繁项集的过程中可使用先验性质判断进行剪枝操作。第七,利用以上操作步骤生成的频繁项集计算关联规则[7]。
Apriori算法的核心是使用Lk-1找出LK项,k≥2,主要步骤为连接和剪枝:
1) 连接。将LK-1与其自身通过连接运算生成候选k项集的集合,用Ck来表示。假设l1和l2是LK-1中的项集,li[j] 表示li的第j,如果l1[1]=l2[1])(l1[2]=l2[2])(l1[k-2]=l2[k-2])(l1[k-1]<l2[k-1]) ,则LK-1中的元素l1和l2是可连接的,连接l1和l2产生的结果项集是{l1[1],l1[2],…l1[k-1],l2[k-1]}[8],项集中不能存在重复的项。
2)剪枝步。通过扫描数据库,对Ck项集中每个项进行计数,其中值不小于最小支持度的项都属于Lk。为了节省计算量,使用算法的先验性质,假如Ck中的一个候选k项集的(k-1)项子集不属于LK-1,则将其从Ck中删除。
1)输入事务数据库,用D表示。设定最小支持度阈值,用Minsup表示
2)输出D中的频繁项集。
3)算法伪代码表示如下[9]:
L1=find(D); //L1表示频繁1项集,find (D)表示从数据事务中查找频繁项集
for(i=2; Li-1;i++) //通过频繁i-1项集生成频繁i项集
{Ci=funapr (Li-1); //调用函数funapr (),生成候选项集Ci
for each 事务T∈D//T代表一个事务,通过for循环对每一个事务进行判断
{C1=subset(Ci,T); //取得候选项
for each 候选c∈CT;
c.count++;}
Li={c∈Ci| c.count≥minsup}
}
return L=UiLi
Procedure funapr (Li-1:frequent(i-1)itemset)
{for each项集l1∈Li-1
for each 项集l2∈Li-1
If(l1[1]=l2[1])^(l1[2]=l2[2])…^(l1[k-2]=l2[k-2])^(l1[k-1]<l2[k-1]) then
{ c=l1l2; // 连接操作
If infreqset(c,Li-1) then // 如果不是频繁项集
delete c; //剪枝操作
else add c to Ci;}
Return Ci;
Procedure infreset(c:candidate i itemset; Li-1:frequent(k-1)itemsets)
{ for each(k-1) subset s of c//通过本程序判断s是否为非频繁项集
If s Li-1then //如果子集s不属于Li-1
return true;
else
return false}
1)生成每个频繁项集l的非空子集[10]。
2)如果(support_count(1)/(support_count(s)≥min_conf,则输出规则“s=> (l-s)”,其中min_conf代表最小置信度阈值。
3 Apriori算法在平台教学资源推荐中的应用
Apriori算法挖掘过程分为四步:第一,对于进行挖掘的数据信息进行整理,形成一个计算机能处理的数据库;第二,从数据库中把具有一定价值的数据项整理出来;第三,把整理过的数据项转换成算法能够处理的事务;第四,根据预先所设定的最小支持度得到频繁项集;第五,根据频繁项级级预先设定的最小置信度得到事务间的关联规则[11]。
实例分析:采用Apriori算法挖掘学生进入课程中心进行课程学习的访问日志,找出访问较频繁的知识点页面,判断学生的兴趣。基于学生频繁进行学习的页面,获取学生的学习需求趋势,找出频繁项集,进行个性化学习资源的推荐。
数据收集在数据挖掘前期工作中是非常重要的,收集学生访问平台知识点网页的记录,随机抽取了4条记录,如表1所示。
表1 学生访问知识点网页记录数据表
把数据表转换成事务数据库D,例题中共有4个事务,即|D|=4,其中C代表C语言,CJ代表C++,CS代表C#,J代表计算机基础,P代表Photoshop,转换后记录如表2所示。
表2 学生访问知识点网页的事务数据
将事务数据表转化成布尔矩阵,如表3所示。
表3 学生访问知识点网页的布尔矩阵图
按照算法的两个步骤进行关联规则挖掘, 在本例中假设最小支持度计数为2,即min_sup=2,最小置信度为6 5%。
1)使用候选项集找出所有频繁项集。
在查找L1时,将事务数据库中所有的事务进行扫描,将所有项的出现次数进行统计,从而确定C1,从C1中把大与等于最小支持度阈值的项取出来,组成集合赋给L1,如图1所示:
图1 候选项集C1和频繁项集L1的产生
2) 通过Ll其自身连接产生C2—候选两项集的项集,计算C2中两项集出现的次数,然后将其值与最小支持度比较,不小于最小支持度的项集赋给L2。
图2 候选项集C2和频繁项集L2的产生
3) L2与自身连接生成C3—候选三项集的项集,计算C3中两项集出现的次数,然后将其值与最小支持度比较,不小于最小支持度的项集赋给L3。
图3 候选项集C3和频繁项集L3的产生
4) L3与自身连接不再生成频繁项集,因此算法结束。
通过分析结果发现C语言和C++、C#两门课程之间存在着密切的关联,将得到的关联规则结果存放到关联规则表中,在学生选择学习C语言课程时平台自动推荐学习C++、C#,如图4所示。
图4 平台自动推荐学习资源界面图
4 结语
随着Internet的迅速发展,网络教学平台的应用已成为网络教育的一种主流模式。数据挖掘技术中Apriori算法在教学平台中的应用可以为学生自动推荐个性化的学习资源,从而可以满足不同学习者的学习需求,提高学习效果和质量。
[1]林炳源.基于FP树的关联规则算法改进研究. 林炳源[D].赣州:江西理工大学,2012.
[2]Jiawei Han ,Micheline Kamber ,Jian Pei.Date Mining Concepts and Techiques Third Edition[M].BeiJing:China Machine Press.2012.
[3]李文静.浅谈数据挖掘中的分类算法[J].甘肃科技纵横,2007(3):2.
[4]刘芳.基于双向搜索的关联规则挖掘算法研究[D].重庆:重庆邮电大学,2011.
[5]谢亮.基于主从关系数据模型的关联规则挖掘研究[D].合肥:合肥工业大学,2009.
[6]樊妍妍.基于数据挖掘的个性化在线教学辅助系统的研究与设计[D].合肥:安徽大学,2011.
[7]R obert C ool ey,Bam shad M obasher,Jai deep Sri vast ava[M].D at a Preparat i on f or M i ni ng W orl d W i de W eb Brow si ng Pat t erns. Know l edge and Inf orm at i on Syst em s,1999.
[8]范明.数据挖掘概念与技术[M].孟小峰,译.北京:机械工业出版社,2012.
[9]Fayyad U.Data mining and knowledge discovery in databases implications for scientific databases[C]//International Conference on Scientific Database Management,1997:51-55.
[10](美)谭.斯坦巴赫.数据挖掘技术导论[M].范明等,译.北京:人民邮电出版社,2006.
(编辑:贾娟)
Application of Apriori Calculation in Network Teaching Platform to Automatically Recommend Learning Resources Function
Lu Xiaohua,Liu Jing
(Computer Information Engineering College of Shanxi Technology and Business University,Taiyuan Shanxi 030006)
This paper mainly studies the data digging, according to the association rules Apriori algorithm for mining frequent itemsets in the application of the teaching platform, into the heart of the course on the students to learn the logging as raw data, USES the Apriori algorithm analysis knowledge web page, the correlation between learning resources according to association rules of personalized recommendation, to meet different learning needs of students.
association rule; Apriori calculation; teaching platform; study material recommend
TP311
A
2095-0748(2016)15-0101-04
10.16525/j.cnki.14-1362/n.2016.15.43
2016-07-06
课题项目:山西工商学院《C语言程序设计精品课程建设项目管理研究》,编号:201549
卢小华(1981—),女,山西五台人,工程硕士,现就职于山西工商学院计算机信息工程学院,研究方向:数据挖掘;刘静(1981—),男,山西朔州人,现就职于山西工商学院网络中心,教育技术学专业。