基于关联规则挖掘的OJ推荐方法

朱国进 凌晓晨

摘 要： Online Judge系统（简称OJ），是一个编程练习的在线判题系统。练习者可以根据知识点和难度，选择相应的编程题目，提交自己编写的程序代码，得到OJ的评测反馈。为了在OJ上搜寻到合适自己的题目，练习者常常需要花费较长的时间浏览题库。针对这一问题，本文提出一种基于关联规则挖掘的解决方案，其主要流程为：首先，收集OJ中所有练习者已做题目的数据；而后，使用关联规则挖掘的方法，挖掘出题目之间的关联关系；最后，依据目标练习者的做题历史，个性化地为其推荐合适的题目。实验结果表明，本推荐方案可为编程练习者做出有效推荐。相比原先需要从上千道题目中浏览寻找，练习者只需从推荐的3道题目中进行选择即可，极大程度地节约了用户的时间和试错成本。

关键词： 关联规则挖掘；机器学习；推荐系统；数据挖掘

Abstract：Online judge system（OJ） is an online evaluation system. Users can choose programming problems according to knowledge point and difficulty submit solution code and get feedback information. In order to find appropriate problems users often have to spend plenty of time in browsing problem database. To facilitate this process this article uses the recommendation method based on the association rule mining to analyze the history data of users on the OJ and make personalized recommendation for them. The main process of this recommendation system is to collect the history data of all the users except the target users. Then the association rules are applied to get the relationship between the problems users have done. Finally the system makes recommendation for target user based on rules and history data of target users. The simulation results show that this recommendation system can make effective recommendation for users. Compared to random recommendation the usability of the recommendation has improved substantially. Rather than seeking appropriate problems from the massive problem database users now only need to pick one from 3 problems provided by the recommendation system which extremely saves time and trial cost.

Key words： association rule mining；machine learning；recommendation system；data mining

引言

随着计算机技术和互联网的不断发展和普及，越来越多的人倾向于通过在线平台学习和掌握计算机知识。而OJ，由于其题库中涉猎知识面范围广泛、试题数目充足、评判可靠、且论坛等交流资源更加丰富，自问世以来，即为广大专业与非专业编程爱好者和初学者创建提供了理想的聚集环境与空间。

但在实际使用中，编程的初学者面对海量的题库和繁多的知识点，难以在第一时间搜寻到满足自身需求意愿的题目，往往经过几番尝试之后，依旧没有找到适合自己能力水平和兴趣偏好的题目。这势必会影响到该部分用户对于OJ网站的使用。若能利用技术手段对练习者的做题历史数据进行数据挖掘，从而高效地为OJ用户推荐合适的题目即已成为一个亟待探索与研究的新方向。

基于以上需求，本文依据数据挖掘和机器学习的理论，提出一种针对OJ平台设计的推荐方案：使用关联规则挖掘的方法，对OJ用户做题历史的大数据进行分析，从中推导得到题目之间的关联规则；从而能够运用这些关联规则，根据目标用户自身的做题历史，为其定制合适的题目推荐。

关联规则挖掘技术在数据挖掘领域有着至关重要的地位[1]。其概念最早出现于1993年，由Agrawal等人[2]提出，用于发现超市中消费者所购买商品间的隐含联系，也就是“购物篮分析”问题，而后这一技术即快速应用于其它领域。

关联规则挖掘的目的是充分利用积累的数据，找寻这些数据中不同事物间的潜在联系，从而得到表征现实具体联系的关联规则。

利用此原理，便可通过规则更好地理解各題目间的关联，并为用户做出合适的推荐。此外，基于关联规则的推荐还有着同样适用于只有少量历史行为记录的新用户的优点，避免了“冷启动”[3]问题。

实验取得了较好的成果，该研究能服务于广大OJ使用者和程序设计竞赛参赛队员。

1 关联规则

1.1 相关概念

关联规则相关概念的定义[4]可表述如下：

在关联分析时，采用支持度和置信度来量化该过程的成功与否[5]。所以，需要预先设置最小支持度（minSupp）和最小置信度（minConf），针对低于这2个参数值的规则不予挖掘。分析可得原因如下：

（1）若某条规则的支持度太小，则代表性不强；

（2）若某条规则的置信度太小，则可靠性不够。

定义5频繁项集 若某项集X的支持度大于等于预设的最小支持度，即Supp（X） ≥ minSupp，则称该项集X为频繁项集。

定义6项集的维数 该项集中所包含项目的个数。称维数为k的项集为k-项集。

1.2 主要流程

OJ推荐系统的关联规则挖掘可分为3步，步骤内容可分述如下[5]：

（1）参数预设。设置最小支持度minSupp和最小置信度minConf。

（2）发现频繁项集。以OJ上所有用户的历史做题列表作为数据集，挖掘出频繁项集X，满足Supp（X） ≥ minSupp。

1.3 挖掘算法

关联规则挖掘的常见算法有：Apriori算法与其扩展算法[6]，FP-growth算法等。本文选用Apriori算法来挖掘OJ上用户所做题目间的关联，为后续推荐的生成提供依据。

Apriori算法挖掘的是布尔关联规则。所谓布尔关联规则是指所处理的数据只表明了“有”和“无”的关系，而无需具体考虑数据在某些字段上数值的关联。该算法经过大量学者的研究，现已广泛应用于其它领域和问题的研究中，如医疗卫生[7]、决策分析[8]、气象分析[9]等，并且成为了分析事物间关联性问题的有效工具。

根據Apriori算法的思想，就可将（k-1）-项集两两取并集得到一组k-项集，随后通过最小支持度minSupp剪枝去除非频繁项集得到频繁k-项集；重复这一过程，直到没有新的频繁k-项集产生为止。最后，通过频繁项集推导出关联规则，将所得的关联规则根据最小置信度minConf进行过滤，由此得到强关联规则，用于推荐系统。

算法主要包含2部分：发现频繁项集和关联规则生成。其中发现频繁项集的过程可分为连接和剪枝两步。这一过程不断循环，直至演变生成的项集包含了数据集中的所有频繁项。同时，使用支持度作为发现频繁项集的量化指标。以OJ推荐系统为例，连接与剪枝的原理可设计展开如下。

例1 假设有4名学生，历史做题情况分别为（数字代表题目id）：S1 = {1 2 3 4 5 6}，S2 = {2 3 4 5 8}，S3 = {2 3 4 8 9}，S4 = {1 5 7 9}。连接和剪枝过程则如图1和图2所示。

在图1中，第一行列出了所有的1-项集，第二行表示各个1-项集在S1、S2、S3、S4中出现的频次，第三行表示了1-项集在数据集I中的支持度Supp；由于1-项集{6}和{7}的支持度Supp小于设定的minSupp = 0.5，故而将其剪去。

在图2中，剪枝后剩余的1-项集两两取并集得到2-项集及其支持度Supp，不满足Supp ≥ minSupp的2-项集也将会剪去；类似地，先合并、再剪枝，得到3-项集至N-项集，便可获得所有的频繁项集，如{2 3 4}、 {2 3 5}、 {2 4 5}等。

2 基于关联规则的推荐

综上研究后，挖掘得到的关联规则，表明了OJ编程题目之间的联系，将目标用户的历史做题数据集作为规则的前继，规则的后继便是可以向该用户推荐的题目集。

2.1 针对OJ的推荐方法

Apriori算法常用于购物推荐，而OJ推荐上并不完全等同于购物推荐，顾客对于曾经购买的商品可以再次购买，而用户并不会反复选定已经做过的题目。用户的做题数据存在时间上的先后顺序（一般由易到难地进行练习），所以在进行题目的个性化推荐时也要考虑并利用到这种先后顺序。

研究中，假设有3名学生S1，S2，S3，各自的做题情况如图4所示。图4中的每一行代表一位学生的做题情况，每一行里的数字代表做题的题号，题号自左向右的顺序指明了每位学生的做题顺序。

如图4所示，不划分做题周期，就图中提供的这一周期的数据而言，将产生数据集为：{1 3 5 2 4 6}、 {1 2 4 3 5 6}、 {1 3 6 2 4 5}。由于3个数据集的元素相同，将生成链式关联规则{1}{6}，且每一条规则的支持度Supp和置信度Conf 都为1，从而无法通过剪枝过滤掉任何一条关联规则。

基于此，为了使推荐方法能够给出更加细致以及符合预期的结果，需要将每个用户的做题数据集按周期进行划分，再进行关联规则的挖掘。

图5中，将用户的做题数据按周期B划分为2段，将产生如下数据集：{1 3 5}、{ 2 4 6}、 {1 2 4}、{ 3 5 6}、 {1 3 6}、{2 4 5} ，代入Apriori算法后得到的强关联规则可如图6所示。

划分周期后，避免了出现链式关联规则的情况，改进了原有算法对于数据信息挖掘的不足（忽略了时间先后顺序这一信息），提高了关联规则推荐方法对于OJ推荐的适配性。

2.2 候选结果优化

根据规则得到的推荐结果可能有很多个。若将所有结果全部推荐给用户，可能会让用户陷于无所适从的困扰。需要对推荐结果进行排序，将排在前3位的结果推荐给用户，即本文的推荐方法最终将为每位OJ用户推荐3道题。而推荐度就是评价候选结果推荐程度的衡量指标。

关于推荐度，推导可得如下数学公式[10]：

其中，RD为推荐度；R表示一条关联规则；ω1和ω2既可以事先指定，也可以由推荐系统学习得到。公式（1）的作用是对关联规则进行排序，找到最可靠的规则。

根据推荐度RD的数值由大到小对推荐结果依次排序，便可得到合理的推荐序列。

3 实验评估

3.1 实验数据

本文从东华大学的Online Judge系统，DHUOJ（http：//acm.dhu.edu.cn/）上，截取并下载了总计395名学生关于2 317道题的做题情况作为实验的源数据，时间跨度为2015/04/10～2017/01/05，共计65 535条记录。数据（单条）形式可见表1。此处对学生姓名引入了脱名处理。

在此基础上，对数据进行清洗和筛选。这一过程主要包括内容如下。

首先，只保留了学生提交状态为“Accepted”的记录，并且对于同一题，只保留学生第一次Accepted的记录。

其次，为方便之后的关联规则挖掘，将记录中的所有题目进行重新编号，用编号代替题目名称。

最后，得到的可输入算法求取关联规则的数据（单条）形式见表2。

3.2 推荐效果评估标准

分类准确度[11]是评价推荐结果是否正确、而且反映了用户喜好的性能指标。这种指标多用于有着明确二分性的系统中。即，对于某一具体的事物，系统中的所有用户只对其做出“喜欢”或“不喜欢”两种评判。

对于OJ用户而言，编程题可直接划分为“做过”和“未做过”两种状态。因此，OJ即是一种有着明确二分标准的系统。故而，本文可选用准确率和召回率综合而得的F1值来对推荐的准确性进行评估。

对于每名用户的推荐效果，其准确率、召回率在OJ题目推荐中的计算方法如下：

其中，推荐命中的题目表示推荐的题目与用户实际所做题目的交集。

本文保留用户最后所做的3道题作为验证，所以公式（3）中的用户实际做题数在此处为3。

在实验中，每对一名用户做出推荐后都会伴随一次评估，得到一个准确率和召回率。实验结束后，对实验中所得的准确率和召回率求出算术平均。而后根据这2个平均值，计算出OJ上推荐效果的总体F1值。此时，得到总体F1值即为用于评估推荐效果的指標。

3.3 参数评估

本实验中，F1值依赖于minSupp和minConf值的选取。因此，对minSupp指定为0.015～0.035，minConf为0.25～0.75的情况下（共55种情形），运行得到的F1值进行了综合统计、并绘制展示，最终效果如图8所示。

由图8可得，当minConf为0.30时，可获得最大F1值。因此将最小置信度设定为0.30，此时F1值和minSupp的变化趋势则如图9所示。

由图9可知，当minSupp为0.025、minConf为0.30时，可推得最大F1值的峰值为0.446。

3.4 结论分析

若选取minSupp为0.025，minConf为0.30，可为用户做出最佳的有效推荐。在此前提下，以推荐的3题中至少有1题推荐正确为标准，准确率为74.2%。最小支持度的设定是为了保障研究挖掘到的规则质量，若随意调低最小支持度，可能将会对结果产生负面影响。

相比此前要在包含有数千道题的题库中寻找要做的题目，现在这些用户只需从推荐的几道题（至多3道题）中进行选择即可。在一定程度上可以帮助用户节约浏览题库的时间。

由于题库中会存有数千题，而实验中的93名用户仅做了50～100题，若采用随机推荐的方法，准确率和召回率都将非常低（接近0.000）。与其相较之下，本推荐功能已具有一定的成效。

4 结束语

本文提出了一种基于关联规则挖掘的OJ推荐方法，通过分析OJ用户的历史做题数据，使用并针对OJ推荐改进现有的Apriori算法推导出强关联规则、且使用规则，对目标用户进行做题推荐。实验结果显示，本系统可对大多数用户做出有效推荐，即保证用户在推荐的3道题内找到适合自己的编程题目。从根本上解决了随机推荐方法的低准确率问题，相当程度上大幅提高了OJ推荐对于用户的可用性。

参考文献

[1] 王爱平 王占凤 陶嗣干，等. 数据挖掘中常用关联规则挖掘算法[J]. 计算机技术与发展 2010 20（4）：105-108.

[2] AGRAWAL R，SRIKANT R. Fast algorithms for mining association rules[C]//Proceedings of 20th International Conference on Very Large Databases. Santiago de Chile Chile： Morgan Kaufmann 1994：487-499.

[3] 孙冬婷，何涛，张福海. 推荐系统中的冷启动问题研究综述[J]. 计算机与现代化，2012（5）：59-63.

[4] 朱惠. 关联规则中Apriori算法的研究与改进[J]. 电脑知识与技术 2014，10（12）：2697-2701.

[5] HARRINGTON P. 机器学习实战[M]. 李锐，李鹏，曲亚东，译. 北京：人民邮电出版社 2013.

[6] SCHLEGEL B KIEFER T KISSINGER T et al. PcApriori： Scalable apriori for multiprocessor systems[C]// International Conference on Scientific and Statistical Database Management. Baltimore Maryland USA：ACM 2013：1-12.

[7] CUI Xiaoyan YANG Shimeng WANG D. An algorithm of Apriori based on medical big data and cloud computing[C]//2016 4th International Conference on Cloud Computing and Intelligence Systems （CCIS）. Beijing，China：IEEE 2016： 361-365.

[8] 魏茂林. Apriori算法的改进及其在教育决策系统中的应用[D]. 长春：吉林大学，2010.

[9] 黄钧晟. 云计算环境下基于Apriori算法的气象数据关联规则分析研究[D]. 南京：南京信息工程大学 2015.

[10]刘亚波. 关联规则挖掘方法的研究及应用[D]. 长春：吉林大学 2005.

[11]朱郁筱 吕琳媛. 推荐系统评价指标综述[J]. 电子科技大学学报 2012 41（2）：163-175