知网论文查重摘  要

ACM是世界级竞赛，其含金量和训练方法十分值得推广。为了满足大家提升程序设计能力的需求，出现了各式各样的在线题目评测系统^[13]如国外的topcoder，codeforces，国内的pku OJ等等。然而当今许多计算机专业的学生对ACM和编程缺乏兴趣，导致编程能力一般，专业水平也一直下降。其中很大一部分同学是由于各大OJ中各种类型的题目太多，同学们在得到大量训练机会的同时，也面临着信息过载问题，此外由于本身对该方面的经验缺乏，也导致他们做题的时候过于盲目，做不适合他们的题目，导致受打击，而过早的失去了自信。对于专业的ACM队员在进行专题训练的时候，由于题目太多也面临着难以挑选出所需的题目，导致训练效率低下。

而推荐引擎是解决这类问题的有效工具，本文利用大数据相关的技术，利用先对用户和题目进行建模，并利用协同过滤算法实现了一个个性化推荐策略，并根据数据的实际分布情况对模型效果进行评估和优化，之后利用web技术搭建了一套完整的推荐引擎。最后通过抽样检验，实地测评以及准确率计算的等方法对结果进行评定，发现推荐引擎对提升训练效率和激发学生们做题热情上有着明显的作用和意义。

知网论文查重

绪论

随着互联网的迅猛发展，接入互联网的服务器数量和网页数量都是指数型的再增长，海量的信息顷刻间爆炸式的出现在了我们的眼前。例如淘宝上有数千万的商品，Netflix上有数万部的影片^[1]，codeforces和topcoder上有成千上万的问题。在给用户带来便利的的同时，也使得用户暴露在海量的信息浪潮中，而难以从中获取对自己有价值的信息，从而导致无法做出合理的选择^[4]。这也就是所谓的信息过载的现象。

目前工业界解决这方面的问题，主要有两种办法。其中一个是搜索引擎。但是使用搜索引擎的用户，往往需要事先对自己的目的比较明确才能够搜到比较满意的结果。此外用户使用相同的query进行检索时，得到的结果往往是非个性化的，千篇一律的结果。所以用搜索引擎还是无法很好的解决问题。^[3]

此外另外一个就是推荐引擎，推荐引擎的核心就是根据用户曾经的行为信息，去猜测用户的偏好，并讲用户从未用过的且评分高的产品推荐给用户。而评估的方法主要是通过用户的注册信息等静态类的信息，以及用户的点击浏览等一系列动态的行为进行分析，进而起到预测用户兴趣点并引导用户发现自己的信息需求。

ACM是世界级的竞赛，其含金量和训练方法十分值得推广。然而如今好多计算机专业的学生对编程缺乏兴趣，导致编程能力一般，专业水平也一直下降。其中一个很重要的原因就是，当他们在做题的时候，没有人指导，过于盲目，做不适合他们水平段的题目导致过受打击，过早失去自信。于是决定研发这套OJ题目推荐系统，一方面能够为初学者推荐适合他们的题目，提高大家对编程的热情，让更多的计科学生喜欢编程喜欢上OJ。另一方面，为专业的ACM选手在正式训练之余，进行补充训练，提高熟练度，一方面也会ACMer进行专题训练时推荐相似的题型，为训练提升帮助。

第1章 相关技术与理论基础介绍

第1.1节 推荐系统

推荐系统在最早被大多数业界的人们所接受的定义是:”它是利用电子商务网站向客户提供商品信息和建议，帮助用户决定应该购买什么产品，模拟销售人员帮助客户完成购买过程”。^[2]  

推荐系统有3个组成要素^[9]：推荐候选集，用户和推荐方法。业界常见的推荐系统模型如图1.1所示。推荐系统先提取推荐候选集中的物品特征信息，之后用用户历史的兴趣和偏好与之进行匹配，在这过程中利用相关的推荐算法进行过滤和挑选，为用户计算出可能感兴趣的推荐物品，之后作为推荐的候选集。推荐的本质是利用相关的方式为用户和物品建立一个桥梁，从而将他们连接起来。然而由于推荐系统的种类繁多，他们的目的的不尽相同，于是不同的系统往往使用不同的方式。

推荐系统可以理解成一种连接器，^[5]能够轻松的建立用户和物品之间的一种联系。推荐系统和搜索引擎最大的区别是，搜索引擎是用户有着明确的目标的情况下，通过对海量信息的检索，来获取所需要的东西，而推荐引擎则是要以来用户以往的行为数据和注册信息等等，对用户建立用户画像，并通过协同过滤等一系列算法产生对于指定用户的推荐物品，本质上是对用户喜好的一种猜测。推荐引擎一般都是作为一个独立的服务存在于不同的网站中。在当今互联网界的各大平台中随处可见推荐引擎的应用。当然这些个性化推荐引擎的本质就是通过对于用户行为日志和偏好信息的掌握，来为用户展示不同的页面。来提高网站的点击率和转换率。常见的推荐引擎如，淘宝，京东，亚马逊，facebook的推荐引擎等均为公司的发展带来了巨大的收益。

图1.1

第1.2节 Online Judge 系统 

Online Judge System（简称OJ）是一个高效的在线判题平台，常见的OJ系统有如Codeforces,topcoder, pku oj以及各个学校的OJ系统等，一般都包括比赛组织，在线判题，在线竞赛,ACM论坛，新闻发布，提交结果查询等功能。用户可以在线提交指定语言(如C,C++,java)源代码。系统的判题内核会在后台先对用户提交的代码进行编译和执行，然后通过预先设计的测试样例来对程序的正确性进行检验^[13]。

一个用户在OJ中提交的程序，在OJ系统执行中会收到比较严格的限制，包括运行事件，内存使用限制和安全限制等等。Online Juge系统会捕捉并且保存用户程序的执行结果，然后提交给一个判题核心程序。判题核心程序会对用户的输出数据与标准输出样例进行比较，有多解的程序会检验程序的输出数据是否满足一定的逻辑条件，进而验证程序的正确性。

ACM/ICPC国际大学生程序设计大赛和OI信息学竞赛的自动判题和rank是Online Judge系统最开始使用的地方。如今Online Judge系统不单单用于比赛中，更是已经广泛运用在全球高校的编程训练、数据结构和算法那学习，以及作业自动提交判断等各个领域。

第1.3节 推荐策略

推荐系统中最为关键和核心的部分是推荐策略。而推荐算法的本质就是通过一定的方式将物品和用户联系起来，而不同的推荐系统利用了不同的方式。无论是学术界还是工业界都对这个问题给予了很高的关注。如今各种各样的推荐策略已经出现，主要包括：基于内容推荐，基于用户的协同过滤推荐，基于物品的协同过滤推荐，利用用户标签推荐^[8]，利用社交网络推荐等^[5]。

1.3.1 基于内容推荐

基于内容的推荐依据用户的历史行为包括发生过行为对象等，而猜测用户的偏好，使用相关算法策略寻找出其他一些与用户曾经发生过行为的对象类似的对象，并推荐给用户。这种策略，首先分别对用户选择的对象，和推荐候选集进行特征提取，之后进行相似度的计算，相似度较高的对象就可以作为推荐结果向用户进行推荐。比如在电商系统中，往往会有商品推荐的模块。系统往往会用户的注册信息等个人信息，并利用前段买点等方式对曝光点击购买等行为信息进行收集。之后对收集到的信息进行数据分析，从中找到共性，猜测用户的偏好和兴趣点。最后从商品库中选择和用户兴趣点相似商品作为推荐的候选集。

其中对象内容特征和用户特征间的相似度计算是该策略的一个关键部分。可以用以下公式(1)表示。

(1·1)

Score的计算有各种各样不同的计算方法，比如余弦相似度（下图公式2），Jaccord公式，以及适合数据较为稀疏情况下的信息熵公式^[6]等等。

(1.2)

经过计算得到的用户排序对象可以用u(c, s)来表示，最前面的几个对象将作为作为推荐的候选集。

基于内容的推荐策略中的其他一个关键就是对推荐对象和用户模型的内容特征描述。其中对推荐对象内容进行特征提取，常见的比如对一些文本特征进行提取。除此之外利用词频-倒排文档频率，以及利用一些常用的机器学习算法比如决策树，贝叶斯分类，神经网络等进行特征的提取在工业界中也已经得到了广泛的运用。

1.3.2 基于用户的协同过滤推荐

该推荐策略的核心思想是用户基于与自己相似的人的推荐来选择特定的一个推荐对象。^[7]在在线个性化推荐系统中，当一个用户S有个性化推荐需求时，往往会先找到和他有相似兴趣的其他用户，然后把那些用户喜欢的、而用户S没有听说过的物品推荐给S。该推荐过程如下图1.2所示。

图1.2

基于用户的协同过滤推荐的工作可以分为两大部分[10]，首先是利用最近邻算法（KNN）计算出离得最近的邻居，之后就是推荐结果的产生。其核心就是最近邻居的查询。度量用户之间的相似性是找到最近邻居的必备条件。用户i和用户j之间的相似性几位sim(i,j)。   设用户i和用户j在m维空间对象中的特征向量如式（3），可计算出用户间相似度。

(1.3)

然而余弦相似度算法没有对各个用户的评分尺度问题进行考虑，影响了结果的准确性。为此我们可以通过利用减去用户对推荐对象的评分的方法来对余弦相似度度量方法进行修正。如式（4）

(1.4)

在用户相似度计算完成后，UserCF算法会将和用户偏好最为相似的几个个用户喜好的物品作为推荐的候选集。如下公式度量了UserCF算法中用户u对物品j的感兴趣程度。^[6]设用户u的最近邻居集合N表示，由用户u对最近邻居集合N中项目评分可以计算得到用户u对推荐对象i的预测评分，sim（u,n）表示用户u和用户n之间的相似性可以用sim(u, n)进行表示，表示用户n对推荐对象i的评分。和分别表示用户u和用户n对关于对象的平均评分。之后的结果可作为推荐的候选集反馈给用户。