曹景振 贾新磊 李松丹

摘 要：针对ACM在线评测平台中练习题目数量较多，新用户选题盲目的问题，文章主要研究了基于物品（item-based）的协同过滤算法，根据在线评测推荐系统的特性采用了余弦相似性来计算题目之间的相似程度，并且在此基础上加入时间权重和难度权重。实验结果表明，改进后的算法比原有推荐算法的推荐质量和准确度有显著提高。最后将改进后的推荐算法部署到在线评测平台上，帮助用户选到合适的题目练习，提高用户编写程序解决问题的能力。

关键词：协同过滤；个性化推荐；ACM在线评测；时间权重；难度权重

随着ACM-ICPC和CCPC等大学生程序设计竞赛的发展，越来越多的高校搭建了ACM在线评测（Online Judge，OJ）平台。在线评测平台题目较多，刚入门的用户往往存在选题盲目的问题，针对此问题，通过利用所有用户的历史做题记录来实现智能题目推荐系统，来帮助新手选择题目，提高学生编写程序、分析和解决问题的能力。

本文主要研究基于物品的协同过滤算法在ACM在线评测平台的题目推荐系统中的改进及应用，目的是在现推荐算法研究成果的基础上，根据在线评测平台特性改进推荐系统算法，进一步提高推荐质量，帮助用户选到更适合的题目。

1 推荐系统概述

推荐系统主要是根据用户抽象的兴趣特点和具体的历史购买行为，向用户推荐其可能感兴趣的信息或者物品。互联网迅速发展也带来了网上信息量的大幅度增长，出现了信息超载问题，为用户产生了困扰，而内容提供商把优质的内容正确推送给感兴趣的用户的操作难度不断加大。而个性化推荐系统恰恰可以解决这个问题，对海量数据进行挖掘，研究用户的兴趣偏好，并对其用户兴趣进行建模，由系统发现用户的兴趣点，从而引导用户发现自己的信息需求。

1.1 主要算法

推荐算法毫无疑问是推荐系统中最重要、最核心的组成部分，对推荐系统具体表现的优劣起着决定性的作用。目前主要的推荐算法包括：协同过滤推荐，基于内容推荐，基于知识推荐，基于关联规则推荐和多种推荐算法组合推荐[1]。每种推荐算法都有自己的优缺点，也有自己具体的适用环境。

1.2 应用现状

推荐系统在互联网上有非常好的应用，如电子商务、新闻资讯等方面。电子商务网站，如亚马逊、淘宝等，利用个性化推荐系统，像实体店中的导购一样为消费者提供推荐服务，帮助客户完成购买行为。新闻资讯类如广告语为“你关心的，才是头条！”的今日头条，就通过其成熟的推荐系统为用户定制个性化的新闻资讯和短视频等，其应用一经推出，便迅速获得海量的用户，用户粘性在所有移动应用中名列前茅。

2 基于物品的协同过滤推荐算法

协同过滤推荐技术被认为是推荐系统算法中应用最为成功的技术之一。它通常采用最近邻（K-Nearest-Neighbor，KNN）算法，利用用户的历史记录来计算用户之间的距离，然后利用目标用户的最近邻用户对物品评价来预测目标用户对其他未评价物品的感兴趣程度，系统从而根据这一感兴趣程度来对目标用户进行推荐。协同过滤的优点是对推荐物品本身没有特殊的要求，能处理一些数据结构不规则或不完整，不方便用二维逻辑来表现的复杂对象，如电影、新闻、题目等，因此适合ACM在线判题平台的题目推荐系统使用。

基于物品的协同过滤的原理是通过分析用户的历史行为记录来计算物品间的相似度，而不是利用物品的内容属性，然后再根據物品的相似度和用户的历史行为为用户生成推荐内容。

2.1 建立数据模型

分别从OJ平台的服务器数据库里读取用户字典，题目数据，难度数据及每个用户最后AC的25道题目的数据，生成矩阵或者列表，作为协同过滤算法模型的输入数据。用户字典列表包括用户编号与用户ID。题目数据矩阵包括所有正确提交的提交用户和题号。

模型建立完成后，对题目数据矩阵通过矩阵相乘的方式进行时间权重和难度权重的赋权。

2.1.1 时间权重

现有的基于物品的协同过滤算法的题目推荐系统在推荐内容计算过程中，往往将用户做题历史数据等同对待，这样不能挖掘出用户当下的做题爱好。因为随着时间的推移，用户的做题兴趣会不断变化，做题水平会不断提高，所以一个用户感兴趣的题目最可能和他近期做过的题目相似。为此引入时间权重，增加近期的做题历史数据在推荐题目生成过程中的重要性，来提高推荐系统的推荐准确率。

在实际运算中，取每个用户最后25次正确的提交，计算最终推荐度时，让每次提交有不同的权重，即倒数第n次正确提交的题目所占权重为l/log（n+l），这样能保证越靠后的提交权重越大。

2.1.2 难度权重

现实中基于物品的协同过滤推荐算法应用往往会增加对流行物品的惩罚度，因为流行物品往往和任意物品的相似度都很高。其逻辑在OJ上也是同样适用的，即OJ题目中的简单题难度较低，很容易解答，一般是仅供练习编程语言语法的题目，而且通常做过这些题目的用户比较多，这种题目的历史提交数据会对推荐系统的推荐结果造成干扰。因此对简单题进行降权，来使推荐题目质量更高，使用户做推荐的题目时，通过题目难度的适当增加或者题目知识点的有效扩宽，来提升自己的编程能力。

可以通过计算AC率，即某道题目所有提交系统判定正确的次数占总提交次数的百分比，来粗略为该题目难度赋值，也可以由经验丰富的用户手动对每道题自定义难度数值，这样推荐效果会更好。

2.2 相似度计算

基于物品的协同过滤算法首先要计算题目之间的相似度，目前常用的几种计算相似度（Simlarity， sim）的方法如下。

（1）基于余弦的相似度计算，通过计算两个向量之间的夹角余弦值来表示物品之间的相似程度，公式如下：

公式中的分子为两个向量的内积，即两个向量相同位置的数字相乘。

（2）调整的余弦相似度计算，由于基于余弦的相似度计算没有考虑不同用户的打分情况，可能有的用户偏向于给高分，而有的用户偏向于给低分，该方法通过减去用户打分的平均值消除不同用户打分习惯的影响，公式如下：

2.3 寻找k最近邻

上面已经计算出题目之间的相似度，为了减少计算时间，只保留选择每个题目最近邻的k 个题目。在保留相似度矩阵中每行前k+l个元素（k个最近邻居加上题目本身），其他元素全部置0。并且为了减少后面计算量及去除一些相似度较低的元素，在这将前一步计算出的稠密矩阵转换为稀疏矩阵。

2.4 获得推荐矩阵

将相似度矩阵乘以用户题目完成情况矩阵，得到一个格式为题目数行，用户数列的矩阵，题目完成情况的值只存在0和1两种情况，所以第α行第b列的元素表示的就是第b个用户所做的所有题目与第α道题目的相似度之和。然后求任意题目与其它所有题目的相似度之和，将两个矩阵相除，就得到了推荐矩阵。然后将用户已经做过的题目通过在矩阵中置0值的方法去掉后，将对矩阵每列的值进行升序排序，越靠前的题目推荐程度越大，最后选出前k个题目，将其题号输出给用户。

3 推荐算法优化效果分析

推荐系统算法的效果检验一般采用将现有的所有数据按比例分为训练集和比较集P，然后将训练集的数据经过设计好的推荐系统处理，得出结果集S，并将结果集与比较集进行比较，通过计算APC平均预测覆盖率来比较优化前推荐算法与优化后推荐算法的推荐效果[3]。APC公式如下：

3.1 数据集

测试采用了信阳师范学院OJ从2017年5月至今所有用户的正确解题数据作为实验的数据集，截至2017年11月19日，数据库中约有1 500道题，450名用户，总共34 100条解题记录，其中正确的解题记录有22 815条，占总解题记录的67.5%。

3.2 测试对比

将OJ用户的解题数据分为训练集和比较集，分别用优化前和优化后的协同过滤算法产生推薦结果，推荐结果和比较集对比得到平均预测覆盖率APC，如图1所示。测试中，训练集和比较集的比例为8：2，算法选取解题个数大于10的用户解题数据，推荐给用户题目个数为5道。

通过数据比较，优化后的算法的推荐质量较原有算法有显著提高。

4 结语

本文通过在原有推荐系统的算法上，结合ACM在线评测系统特性，添加了时间权重和难度权重，提高了推荐质量，为每一个用户提供更好的个性化题目推荐。时间权重考虑到用户的近期兴趣变化，使推荐结果更接近实际，最终提高了推荐准确率；难度权重使推荐结果更能帮助用户选到有水平的好题目，进行练习从而提高编程水平。

并且推荐系统的个性化推荐方面还可以进一步改进，比如添加推荐风格，用户可以选择（对算法部分）单一钻研或广泛涉猎等不同风格，推荐系统也会因此改变对该用户的推荐题目的整体倾向。或者进行多种推荐算法组合推荐使用，进一步提高推荐准确率。

[参考文献]

[1]陶彩霞，袁海.灵活适应不同业务的个性化推荐系统研究[J]电信科学，2014 （8）：131-135.

[2]杨永权.基于协同过滤技术的个性化图书推荐系统研究[J]河南图书馆学刊，2014 （6）：119-122.

[3]孙权，贺细平.协同过滤算法在ACM在线评测推荐系统中的应用研究[J]电脑与信息技术，2015（6）：11-14.