关联规则Apriori算法在个性化学习系统中的应用研究

缪广寒

摘 要 关联算法是实现学习系统的个性化、自主化的有效工具，利用Apriori算法我们可以在学习系统中寻找到学生的学习规律，进而实现个性化的学习推荐，是为个性化学习系统不可取少的功能模块。

关键词 Apriori算法；个性化学习系统；AprioriTid算法；数据挖掘

中图分类号：TP311 文献标识码：A 文章编号：1671-7597（2014）05-0047-02

目前，众多的学习系统大多类似，主要表现在：通用型较多，有专业特色的开发者少；理论类多，实践类少；大众类多，个性化少。而对于目前的个性化系统来说，由于缺乏一个可以量化的个性化的标准，所以在具体实现上很难真正的实现个性化学习，即在内容上、模块上、结构上很难有较为系统、全面、高质量的系统出现。同时，人们的网络学习已经不再满足于传统书本的电子化。交互性、自主性、个性、多元化等各种学习特征急需实现。因此，许多教育学者协同学习系统开发者们都不断投入到个性化学习系统中的个性化的开发建设中去，希望能在技术层面解决个性化需求与海量学习资源之间的矛盾，实时给网络学习者个性化的学习指导，实现真正的因材施教。

基于上述问题的解决，本文构建设计了一个课外体育的个性化学习系统，并利用数据挖掘技术中Apriori算法来改进当前的个性化学习系统的学习模式，对每一个网络学习者提供个性化的学习进程。

1 个性化学习系统及其技术支持

个性化学习是指根据学习者的个性特征实施教育活动，充分发挥学习者的主动性，促进学生全面、自由、协调的发展，从而进一步发展学生的个性和潜能激发。个性化学习是一种创造性、实践性和探索性的学习方式，它的根本目标是让每个学生获得个性发展，实现个性化学习的关键主要是看个性化系统能否适应学生的个性化差异，其中包括学生的学习能力的差异、学习兴趣的差异、学习适应性差异和学习经验差异。

为了满足学习者个性化、自主式学习要求，网络学习系统平台也在不断的发展改进，以各种技术支撑的学习系统应运而生，如自适应学习系统、课程点播系统系统、课程视频会议等，还有以建设个性化学习环境为主的WEB2.0技术，RSS聚合技术、Ajax技术、Ontology本体检索技术、数据挖掘技术、数据库技术等应运而生。可以说从国家到学校，各种相关研究和投入已经多有尝试，颇具规模。

要实现学习系统个性关键在于从信息资源的海洋中得到关于学习者对系统资源使用模式的相关知识，并进一步结合这些知识根据学习者的个人兴趣特征实现对学习者的个性化推荐，提供相应资源。目前这些功能的实现主要采用数据挖掘技术来实现。其中，关联规则就是数据挖掘技术中的一个重要分析模式。

1.1 关联规则

数据关联是指数据库中存在的一类重要的可被发现的知识。如果两个或多个变量的取值之间存在某种规律性，就可称之为关联。数据挖掘中的关联规则实在满足一定支持度和置信度算法的同时在事务数据库数量庞大的关联规则中找到强规则。Apriori算法是一个典型的关联规则算法 ，也称广度优先算法。是R Agrawal和R Srikant 于1994年提出的。

1.2 Apriori算法

Apriori算法的基本思想是：1）找出所有的频集，这些项集出现的频繁性至少和预定义的最小支持度一样；2）从频繁项集发现强关联规则。从一开始找到的频繁项集的规则中找出只包含集合的项的所有规则。扫描项集，使用递归的方法找出所有频繁项集，为了生成所有频集，使用了递归的方法。具体算法伪代码如下：

Input：数据库D；最小支持度MinSuport_count。

Output：数据库D中的频繁项集I。

Begin

a、获得所有支持度不小于 MinSupport的1-项目集

Im=large1-Itemsets；

b、找出数据库D 中所有的频繁项集I

FOR（k=2；Ik-1≠Ф；k++）DO

Ck=apriori_gen（Ik-1）；

FOR 所有transactions l ∈D DO

Ct=subset（CK，t）；

FOR 所有候选 c∈Ct DO

c.count++

END

END

Ik={ c ∈Ck|c.count≥MinSuport_count}

END

I=∪Ik

End

其中，apriori_gen（Ik-1）算法按照上一次迭代发现新的候选项集，分为链接和修剪两个部分。具体描述如下：

1.2.1 链接

Begin

FOR 所有项目集 p∈Lk-1 DO

FOR 所有项目集 q∈Lk-1 DO

IF p.item1=q.item1，p.item2=q.item2…p.itemk-2=

q.itemk-2， p.itemk-1=q.itemk-1， THEN {

C=p∪q； //链接，产生候选集

IF has_infrequent_subset（c，Ik-1） THEN

Delete c； // 修剪。去掉无用候选项

ELSE add c to Ck}

Return Ck

End

1.2.2 修剪

在上述算法中，语句“IF has_infrequent_subset（c，Lk-1） THEN删除”是判断c 是否需要加入到 k-候选集中，不需要就修剪掉。endprint

Begin

FOR each （k-1）-subsets of c DO

IF S ? Ik-1 THEN

Return true；

Return False；

END

End

2 使用Apriori 算法获得学习者的学习规则

关联规则挖掘算法可以应用在学生的成绩分析上，如知识点与测试成绩之间函数关系。通过对篮球课程的活动记录与相应的测试成绩的数据分析，我们可以找到一些对今后指导学生课外学习的有用规律。其具体流程如下。

2.1 整理数据

学生的学习记录库中记录了学生的个人信息与基本学习过程信息。如学生姓名、学号、学习风格、学习时间、学习路径、测试成绩等内容。整理数据的目的是为了使学生的数据记录等符合Apriori算法所需的项目集开展数据挖掘，首先需要将关系表转换成相应的事务数据库。

2.2 生成事物数据库选择自主学习内容，以代码代替

2.3 生成频繁项集

通过以上的对应抽象，我们可知事务集，假设最小支持度为25%，使用Apriori算法寻找D的所有频繁项集。

2.4 关联规则生成

在Apriori算法中，对于每一个频繁k-项集都要找出其中所有可能的真子集，计算出相应规则的置信度。当我们发现某一规则的置信度大于设定的最小置信度就导出该规则。其中，每验证一个项子集都要重新扫描一遍Ik-1。在对某学生的篮球学习记录中分析，最小置信度阈值设置为75%则可以发现强规则I01∧I08→I03。此规则告诉我们发现如果某生的运球技能与防守战术同时成绩优秀，则发现的该生在实践活动中的投篮技能成绩也一般为优秀。通过该例，我们可以发现数据关联算法可以发现学生学习中的一些隐藏的学习规律，而这些规律正好可供学习系统给学习者提供下一步个性化学习方案。

3 多项目集的Apriori算法改进

我们发现，由于Apriori算法对数据库的扫描次数过多，所以在有限的内存容量下存放大量的事务数据时，系统I/O负载会变大，每次扫描数据库的时间就会越长。此外，如果学习系统中某一课程的知识节点太多而导致分析的频繁项集个数太多会产生大量的侯选项集。这会导致运算时间显著增加。所以根据不同的课程，我们可以改进Apriori算法，采用减低候选项目数量的方法，我们称之为AprioriTid。此算法无需此次扫描数据库，当第一次扫描数据库之后，第二次只需要扫描前一次产生的项目集而不再需要完全的扫描数据库，这样就可以有效的减少了I/O负载和数据运算时间。

具体改进为在事务集TID中。当k=1时，C1扫描数据库D，C1=数据库D，但当k>1时，有算法产生Ck，Ck=apriori-gen（Lk-1）。

此外，我们还可以在AprioriTid的基础上通过把项目集中一些无关的属性先去掉以及通过把两个元素结合在一起组成一个新属性的办法来减少工作量，又或者在产生频繁k-项集以后去掉一些非频繁项集来简化扫描时间。以上两种方法的结合使用类似于矩阵中逐渐去掉行与列。

4 现存的问题与思考

利用Apriori算法与AprioriTid算法，我们可以有效的挖掘出个性化学习中学习者的学习关联，掌握学生的学习动态，进而更深入了了解学生的学习规律与特点。但是在分布式计算与学习增量的情况下，我们不得不需要进一步地改进算法，以适合当前及未来的个性化学习系统发展的趋势。

参考文献

[1]刘美玲.基于数据挖掘技术的个性化学习系统研究[D].扬州：扬州大学，2009.

[2]盛立，高明，刘希玉.一种高效的关联规则的算法研究[J].滨州学院学报，2005（12）.

[3]盛立，刘希玉，高明.数据关联规则中AprioriTid[J].山东师范大学学报（自然科学版），2005（10）.

[4]李曼.Web日志挖掘技术在心灵家园网中的应用研究[D].河南：河南大学，2013.

[5]何月顺.关联规则挖掘技术的研究及应用[D].江苏：南京航空航天大学，2010.

[6]王志强.基于远程教育网站的信息采集与数据挖掘技术研究[D].上海：华东师范大学，2007.endprint

Begin

FOR each （k-1）-subsets of c DO

IF S ? Ik-1 THEN

Return true；

Return False；

END

End

2 使用Apriori 算法获得学习者的学习规则

关联规则挖掘算法可以应用在学生的成绩分析上，如知识点与测试成绩之间函数关系。通过对篮球课程的活动记录与相应的测试成绩的数据分析，我们可以找到一些对今后指导学生课外学习的有用规律。其具体流程如下。

2.1 整理数据

学生的学习记录库中记录了学生的个人信息与基本学习过程信息。如学生姓名、学号、学习风格、学习时间、学习路径、测试成绩等内容。整理数据的目的是为了使学生的数据记录等符合Apriori算法所需的项目集开展数据挖掘，首先需要将关系表转换成相应的事务数据库。

2.2 生成事物数据库选择自主学习内容，以代码代替

2.3 生成频繁项集

通过以上的对应抽象，我们可知事务集，假设最小支持度为25%，使用Apriori算法寻找D的所有频繁项集。

2.4 关联规则生成

在Apriori算法中，对于每一个频繁k-项集都要找出其中所有可能的真子集，计算出相应规则的置信度。当我们发现某一规则的置信度大于设定的最小置信度就导出该规则。其中，每验证一个项子集都要重新扫描一遍Ik-1。在对某学生的篮球学习记录中分析，最小置信度阈值设置为75%则可以发现强规则I01∧I08→I03。此规则告诉我们发现如果某生的运球技能与防守战术同时成绩优秀，则发现的该生在实践活动中的投篮技能成绩也一般为优秀。通过该例，我们可以发现数据关联算法可以发现学生学习中的一些隐藏的学习规律，而这些规律正好可供学习系统给学习者提供下一步个性化学习方案。

3 多项目集的Apriori算法改进

我们发现，由于Apriori算法对数据库的扫描次数过多，所以在有限的内存容量下存放大量的事务数据时，系统I/O负载会变大，每次扫描数据库的时间就会越长。此外，如果学习系统中某一课程的知识节点太多而导致分析的频繁项集个数太多会产生大量的侯选项集。这会导致运算时间显著增加。所以根据不同的课程，我们可以改进Apriori算法，采用减低候选项目数量的方法，我们称之为AprioriTid。此算法无需此次扫描数据库，当第一次扫描数据库之后，第二次只需要扫描前一次产生的项目集而不再需要完全的扫描数据库，这样就可以有效的减少了I/O负载和数据运算时间。

具体改进为在事务集TID中。当k=1时，C1扫描数据库D，C1=数据库D，但当k>1时，有算法产生Ck，Ck=apriori-gen（Lk-1）。

此外，我们还可以在AprioriTid的基础上通过把项目集中一些无关的属性先去掉以及通过把两个元素结合在一起组成一个新属性的办法来减少工作量，又或者在产生频繁k-项集以后去掉一些非频繁项集来简化扫描时间。以上两种方法的结合使用类似于矩阵中逐渐去掉行与列。

4 现存的问题与思考

利用Apriori算法与AprioriTid算法，我们可以有效的挖掘出个性化学习中学习者的学习关联，掌握学生的学习动态，进而更深入了了解学生的学习规律与特点。但是在分布式计算与学习增量的情况下，我们不得不需要进一步地改进算法，以适合当前及未来的个性化学习系统发展的趋势。

参考文献

[1]刘美玲.基于数据挖掘技术的个性化学习系统研究[D].扬州：扬州大学，2009.

[2]盛立，高明，刘希玉.一种高效的关联规则的算法研究[J].滨州学院学报，2005（12）.

[3]盛立，刘希玉，高明.数据关联规则中AprioriTid[J].山东师范大学学报（自然科学版），2005（10）.

[4]李曼.Web日志挖掘技术在心灵家园网中的应用研究[D].河南：河南大学，2013.

[5]何月顺.关联规则挖掘技术的研究及应用[D].江苏：南京航空航天大学，2010.

[6]王志强.基于远程教育网站的信息采集与数据挖掘技术研究[D].上海：华东师范大学，2007.endprint

Begin

FOR each （k-1）-subsets of c DO

IF S ? Ik-1 THEN

Return true；

Return False；

END

End

2 使用Apriori 算法获得学习者的学习规则

关联规则挖掘算法可以应用在学生的成绩分析上，如知识点与测试成绩之间函数关系。通过对篮球课程的活动记录与相应的测试成绩的数据分析，我们可以找到一些对今后指导学生课外学习的有用规律。其具体流程如下。

2.1 整理数据

学生的学习记录库中记录了学生的个人信息与基本学习过程信息。如学生姓名、学号、学习风格、学习时间、学习路径、测试成绩等内容。整理数据的目的是为了使学生的数据记录等符合Apriori算法所需的项目集开展数据挖掘，首先需要将关系表转换成相应的事务数据库。

2.2 生成事物数据库选择自主学习内容，以代码代替

2.3 生成频繁项集

通过以上的对应抽象，我们可知事务集，假设最小支持度为25%，使用Apriori算法寻找D的所有频繁项集。

2.4 关联规则生成

在Apriori算法中，对于每一个频繁k-项集都要找出其中所有可能的真子集，计算出相应规则的置信度。当我们发现某一规则的置信度大于设定的最小置信度就导出该规则。其中，每验证一个项子集都要重新扫描一遍Ik-1。在对某学生的篮球学习记录中分析，最小置信度阈值设置为75%则可以发现强规则I01∧I08→I03。此规则告诉我们发现如果某生的运球技能与防守战术同时成绩优秀，则发现的该生在实践活动中的投篮技能成绩也一般为优秀。通过该例，我们可以发现数据关联算法可以发现学生学习中的一些隐藏的学习规律，而这些规律正好可供学习系统给学习者提供下一步个性化学习方案。

3 多项目集的Apriori算法改进

我们发现，由于Apriori算法对数据库的扫描次数过多，所以在有限的内存容量下存放大量的事务数据时，系统I/O负载会变大，每次扫描数据库的时间就会越长。此外，如果学习系统中某一课程的知识节点太多而导致分析的频繁项集个数太多会产生大量的侯选项集。这会导致运算时间显著增加。所以根据不同的课程，我们可以改进Apriori算法，采用减低候选项目数量的方法，我们称之为AprioriTid。此算法无需此次扫描数据库，当第一次扫描数据库之后，第二次只需要扫描前一次产生的项目集而不再需要完全的扫描数据库，这样就可以有效的减少了I/O负载和数据运算时间。

具体改进为在事务集TID中。当k=1时，C1扫描数据库D，C1=数据库D，但当k>1时，有算法产生Ck，Ck=apriori-gen（Lk-1）。

此外，我们还可以在AprioriTid的基础上通过把项目集中一些无关的属性先去掉以及通过把两个元素结合在一起组成一个新属性的办法来减少工作量，又或者在产生频繁k-项集以后去掉一些非频繁项集来简化扫描时间。以上两种方法的结合使用类似于矩阵中逐渐去掉行与列。

4 现存的问题与思考

利用Apriori算法与AprioriTid算法，我们可以有效的挖掘出个性化学习中学习者的学习关联，掌握学生的学习动态，进而更深入了了解学生的学习规律与特点。但是在分布式计算与学习增量的情况下，我们不得不需要进一步地改进算法，以适合当前及未来的个性化学习系统发展的趋势。

参考文献

[1]刘美玲.基于数据挖掘技术的个性化学习系统研究[D].扬州：扬州大学，2009.

[2]盛立，高明，刘希玉.一种高效的关联规则的算法研究[J].滨州学院学报，2005（12）.

[3]盛立，刘希玉，高明.数据关联规则中AprioriTid[J].山东师范大学学报（自然科学版），2005（10）.

[4]李曼.Web日志挖掘技术在心灵家园网中的应用研究[D].河南：河南大学，2013.

[5]何月顺.关联规则挖掘技术的研究及应用[D].江苏：南京航空航天大学，2010.

[6]王志强.基于远程教育网站的信息采集与数据挖掘技术研究[D].上海：华东师范大学，2007.endprint