1、基于OJ数据的习题个性化推荐系统毕业设计论文摘要进入大数据的时代，信息的产生、加工、传播变得越来越容易，计算机已经深入到人们现代生活的方方面面，在教育领域，智能教学系统作为一种辅助教学的手段逐渐成为E-Learning领域众多学者的研究重点，但多数智能教学系统缺乏有效的学习资源推荐机制，使得用户无法准确地寻找到满足自身学习需求的学习资源，最终导致用户学习兴趣下降，系统教辅作用无法得到充分地发挥。个性化推荐是缓建信息过载的方法之一，为了解决在海量题库中为学生提供个性化资源推荐的问题，对于传统的基于用户的协同过滤和基于内容的协同过滤，存在很多弊端，难以满足用户的需求。对于基于用户的协同过滤推荐的原
2、则，如果一个用户没有相同喜好的朋友，那该算法的推荐效果总是不令人满意；对于基于内容的协同过滤推荐的原则，就是假设指用户会喜欢和他以前喜欢的东西是比较相似的，如果不是相似的，用该算法做出准确的推荐的可能性非常低。针对以上现象，为了能够更好的达到个性化推荐系统的效果，在相关理论的指导下，本文提出了基于记忆的过滤和基于规则的过滤两种推荐算法，最终实现习题系统对于学生用户的个性化推荐，以避免传统推荐系统因忽略资源本身蕴涵信息而产生的无关推荐，为智能教学系统中的应用提供一种新的发展思路。关键词：个性化推荐，基于用户的协同过滤，基于内容的协同过滤，基于规则的过滤 AbstractEntered the t
3、ime of Big Data, the generation, processing, dissemination of information getting easier. Computer has penetrated into every aspect of modern life , In the field of education , intelligent tutoring system as a means of secondary education is becoming the focus of many scholars study E-Learning in th
4、e field , but most intelligent tutoring system, the lack of effective mechanisms recommended learning resources , making the users can not exactly looking to meet their learning needs of learning resources , resulting in decreased interest users to learn the system and supplementary role can not be
5、fully realized.Personalized recommendation is postponed one of the methods of information overload, in order to solve the massive exam to provide personalized resources recommended questions for the students, the traditional collaborative filtering and user-based content-based filtering, there are m
6、any drawbacks, it is difficult to meet the needs of users. For the principle of user-based collaborative filtering recommendation, if a user does not have the same taste in friends, it is recommended that the algorithm is undesirable of man; for content-based collaborative filtering recommendation p
7、rinciple, means users will like his former favorite things relatively similar, if the self-similarity is small, the possibility of using this method to make accurate recommendation is very low.For the above phenomenon, in order to better achieve the effect of personalized recommendation system, unde
8、r the guidance of the theory, we propose a memory-based filtering and rule-based filtering recommendation algorithm, and ultimately the system for student exercises the users personalized recommended to avoid the recommendation system by ignoring the resource itself contains information generated in
9、dependent of recommendation for intelligent Tutoring system to provide a new development ideas.Key words: Personalized recommendation, User-based collaborative filtering,Content-based collaborative filtering, Rule-based collaborative filtering1 研究目的智能在线学习系统1是个性化推荐的一种应用，本文介绍的是基于OJ数据的习题个性化推荐系统，本章简要介绍个
10、性化推荐的概念、背景与国内外研究现状，并且针对目前流行的推荐方法予以介绍。1.1 研究背景及意义近年来，随着互联网、移动设备等信息技术的迅猛发展，除了企业业务运营中不断积累的交易等业务数据之外，遍布全球的传感器无时无刻不在探测和收集物理世界的各种信息，移动互联网则在不断收集用户的地理位置信息，各种社会媒体中的数以亿计的用户也在随时随地地产生交互信息，这些数据不仅是数量巨大（以TB甚至PB为单位），而且形式繁多，除了企业业务运营信息系统中的结构化数据之外，各种文本、声音、图片、视频、地理位置等各种不同类型的数据决定了数据的多样性。同时，这些时刻变化的来自各种数据源的数据有充满了噪音，对这些数据的
11、管理和分析已经超出了传统的数据管理技术的能力，因此，人们称其为大数据2。在教育领域，智能教学系统（Intellectual Tutoring System）利用人工智能和计算机技术来模拟现实教学过程，使得该系统具备了人力教学所不具备的高效率、高存储、个性化等特点。其广阔的发展前景使得越来越多的专家开始投入到对ITS的研究中，希望可以凭借计算机对知识的有效处理，由计算机代替老师来提高学生学习效率，并最终实现人类对其自身认知过程的终极解码。智能教学系统作为一种辅助教学手段，其中运用传统的个性化推荐方法有其局限性，对于基于用户的协同过滤,推荐的原则必须要求用户会喜欢那些和他有相同喜好的用户喜欢的东西
12、；对于基于内容的协同过滤则有个前提，就是用户会喜欢和他以前喜欢的东西相似的东西，那么我们可以计算一个用户喜欢的物品的自相似度。一个用户喜欢物品的自相似度大，就说明他喜欢的东西都是比较相似的，只有在这种情况下，该方法才会具有较高的推荐效率。 为了能够提高个性化推荐系统的准确率，本论文摒弃单一的协同过滤方法，提出新的推荐方法思路并将其理论应用智能在线学习系统中，更大的发挥在线学习系统个性化推荐的作用，为学生提供更优质的服务。1.2 推荐系统现状目前对于个性化推荐系统的研究正处于高速发展期,相关的推荐算法也已在电子商务领域、个性化搜索等领域得到一定程度的发展和应用。传统的个性化推荐算法包括基于内容的
13、推荐、基于行为的推荐、以及混合推荐算法，其中基于行为的个性化推荐算法凭借其出色的行为分析和兴趣建模，得到了业内专家学者的广泛研究。但具体到在线学习系统领域，系统本身包含的知识评测系统、以及知识表示系统决定了ITS中的个性化推荐模块对知识的依赖多余对用户学习行为的依赖。相比于利益驱动的电子商务领域个性化推荐算法的蓬勃发展，主要应用于教育领域的个性化推荐算法的研究则相对疲软。由于教育领域内知识本身具有很强的语义关系，软件对用户的辅导更多地是强调用户在认知学习中对知识语义间联系的掌握。而应用较为广泛基于行为的个性化推荐算法，其原理则是通过构建邻居矩阵来判断用户的兴趣来为用户进行资源推荐，对于智能教辅
14、而言，单一的基于用户的协同过滤和基于内容的协同过滤算法推荐结果忽略了用户在进行知识学习时表现出的认知特点，其准确度势必降低。因此，本文将在前人的基础上，研究基于记忆的个性化推荐算法，在本系统中，包含两个纬度：其一，基于用户（学生）的协同过滤4，其二，基于内容（习题）的协同过滤，两者都是利用学生用户过去使用在线学习系统的历史提交记录，从而对学生进行习题个性化推荐。将算法研究重点放到对知识结构与习题资源本身的信息的利用和处理上，以解决在ITS系统中为学生从海量资源中进行个性化资源推荐的问题，并将通过实验证明该算法和系统的理论价值与应用价值。1.3 论文内容与章节安排 对于介绍基于OJ数据的习题个性
15、化推荐系统论文以下内容安排如下：第二部分侧重介绍本系统数据处理过程中依据的理论知识背景及技术应用；第三部分讲述了习题推荐系统实现过程中遇到的难题及整个系统的设计思路；第四部分描述系统实现的详细步骤；第五部分总结了本系统设计与实现过程中的心得与体会。2 理论支持与相关技术的应用与背景习题个性化推荐系统所运用的理论来源于集体智慧，本系统中实现该理论的具体方法是基于记忆的协同过滤和基于规则的协同过滤。鉴于开源软件Weka的强大功能和对Java应用程序的支持，我们采用Java作为开发语言，调用Weka程序返回的数据。下面对这些方法的数学原理和工具或平台做具体介绍。2.1 相应的推荐算法及数学原理2.1
16、.1 集体智慧与协同过滤集体智慧 (Collective Intelligence) 7并不是Web2.0时代特有的，只是在Web2.0时代，大家在Web应用中利用集体智慧构建更加有趣的应用或者得到更好的用户体验。集体智慧是指在大量的人群的行为和数据中收集答案，帮助你对整个人群得到统计意义上的结论，这些结论是我们在单个个体上无法得到的，它往往是某种趋势或者人群中共性的部分。协同过滤是利用集体智慧的一个典型方法。要理解什么是协同过滤 (Collaborative Filtering, 简称 CF) 5，首先想一个简单的问题，如果你现在想看个电影，但你不知道具体看哪部，你会怎么做？大部分的人会问问
17、周围的朋友，看看最近有什么好看的电影推荐，而我们一般更倾向于从口味比较类似的朋友那里得到推荐。这就是协同过滤的核心思想。协同过滤一般是在海量的用户中发掘出一小部分和你品位比较类似的，在协同过滤中，这些用户成为邻居，然后根据他们喜欢的其他东西组织成一个排序的目录作为推荐给你。当然其中有一个核心的问题：如何确定一个用户是不是和你有相似的品位？如何将邻居们的喜好组织成一个排序的目录？协同过滤相对于集体智慧而言，它从一定程度上保留了个体的特征，就是你的品位偏好，所以它更多可以作为个性化推荐的算法思想。可以想象，这种推荐策略在 Web 2.0 的长尾中是很重要的，将大众流行的东西推荐给长尾中的人怎么可能
18、得到好的效果，这也回到推荐系统的一个核心问题：了解你的用户，然后才能给出更好的推荐2.2.2 基于记忆的过滤(1) 基于用户的协同过滤 首先，要实现协同过滤，需要以下3个核心步骤：收集用户偏好:从用户的行为和偏好中发现规律，并基于此给予推荐，如何收集用户的偏好信息成为系统推荐效果最基础的决定因素。用户有很多方式向系统提供自己的偏好信息，而且不同的应用也可能大不相同。收集了用户行为数据，我们还需要对数据进行一定的预处理，其中最核心的工作就是：减噪和归一化2。减噪：用户行为数据是用户在使用应用过程中产生的，它可能存在大量的噪音和用户的误操作，我们可以通过经典的数据挖掘算法过滤掉行为数据中的噪音，这
19、样可以是我们的分析更加精确。归一化：如前面讲到的，在计算用户对物品的喜好程度时，可能需要对不同的行为数据进行加权。但可以想象，不同行为的数据取值可能相差很大，比如，用户的查看数据必然比购买数据大的多，如何将各个行为的数据统一在一个相同的取值范围中，从而使得加权求和得到的总体喜好更加精确，就需要我们进行归一化处理。最简单的归一化处理，就是将各类数据除以此类中的最大值，以保证归一化后的数据取值在 0,1 范中。进行的预处理后，根据不同应用的行为分析方法，可以选择分组或者加权处理，之后我们可以得到一个用户偏好的二维矩阵，一维是用户列表，另一维是物品列表，值是用户对物品的偏好，一般是 0,1 或者 -
20、1, 1 的浮点数值。找到相似的用户(通过相似度找到相似用户):1、相似度的计算关于相似度的计算，现有的几种基本方法都是基于向量（Vector）的，其实也就是计算两个向量的距离，距离越近相似度越大。在推荐的场景中，在用户 - 物品偏好的二维矩阵中，我们可以将一个用户对所有物品的偏好作为一个向量来计算用户之间的相似度，或者将所有用户对某个物品的偏好作为一个向量来计算物品之间的相似度。下面我们详细介绍几种常用的相似度计算方法：a 欧几里德距离（Euclidean Distance）6最初用于计算欧几里德空间中两个点的距离，假设 x，y 是 n 维空间的两个点，它们之间的欧几里德距离是：可以看出，当
21、 n=2 时，欧几里德距离就是平面上两个点的距离。当用欧几里德距离表示相似度，一般采用以下公式进行转换：距离越小，相似度越大。b皮尔逊相关系数（Pearson Correlation Coefficient）皮尔逊相关系数一般用于计算两个定距变量间联系的紧密程度，它的取值在 -1，+1 之间。sx, sy是 x 和 y 的样品标准偏差。2、相似邻居的计算介绍完相似度的计算方法，下面我们看看如何根据相似度找到用户 - 物品的邻居，常用的挑选邻居的原则可以分为两类：图 2.1 给出了二维平面空间上点集的示意图。固定数量的邻居：K-neighborhoods 或者 Fix-size neighbor
22、hoods不论邻居的“远近”，只取最近的K个，作为其邻居。如图2.1中的A，假设要计算点1的5个邻居，那么根据点之间的距离，我们取最近的5个点，分别是点2，点3，点4，点7和点5。但很明显我们可以看出，这种方法对于孤立点的计算效果不好，因为要取固定个数的邻居，当它附近没有足够多比较相似的点，就被迫取一些不太相似的点作为邻居，这样就影响了邻居相似的程度，比如图1中，点1和点5其实并不是很相似。基于相似度门槛的邻居：Threshold-based neighborhoods与计算固定数量的邻居的原则不同，基于相似度门槛的邻居计算是对邻居的远近进行最大值的限制，落在以当前点为中心，距离为 K 的区域
23、中的所有点都作为当前点的邻居，这种方法计算得到的邻居个数不确定，但相似度不会出现较大的误差。如图 1 中的 B，从点1出发，计算相似度在 K内的邻居，得到点2，点3，点4和点7，这种方法计算出的邻居的相似度程度比前一种优，尤其是对孤立点的处理。 图2.1 相似邻居计算示意图固定聚类数的邻居: K-means算法是很典型的基于距离的聚类算法，采用距离作为相似性的评价指标，即认为两个对象的距离越近，其相似度就越大。该算法认为簇是由距离靠近的对象组成的，因此把得到紧凑且独立的簇作为最终目标。对应的元素同样可以找到自己的邻居，本系统采用EM聚类分析算法，以下对K-Means聚类分析与EM聚类分析比较：
24、在聚类问题中，给我们的训练样本是，每个，没有了y。K-means算法是将样本聚类成k个簇（cluster），具体算法描述如下：1、 随机选取k个聚类质心点（cluster centroids）为。2、 重复下面过程直到收敛 对于每一个样例i，计算其应该属于的类对于每一个类j，重新计算该类的质心 图2.2 K-means聚类分析示意图如上图所示，K是我们事先给定的聚类数，代表样例i与k个类中距离最近的那个类，的值是1到k中的一个。质心代表我们对属于同一个类的样本中心点的猜测，拿星团模型来解释就是要将所有的星星聚成k个星团，首先随机选取k个宇宙中的点（或者k个星星）作为k个星团的质心，然后第一步对
25、于每一个星星计算其到k个质心中每一个的距离，然后选取距离最近的那个星团作为，这样经过第一步每一个星星都有了所属的星团；第二步对于每一个星团，重新计算它的质心（对里面所有的星星坐标求平均）。重复迭代第一步和第二步直到质心不变或者变化很小。K-means面对的第一个问题是如何保证收敛，前面的算法中强调结束条件就是收敛，可以证明的是K-means完全可以保证收敛性。下面我们定性的描述一下收敛性，我们定义畸变函数（distortion function）如下： J函数表示每个样本点到其质心的距离平方和。K-means是要将J调整到最小。假设当前J没有达到最小值，那么首先可以固定每个类的质心，调整每个样
26、例的所属的类别来让J函数减少，同样，固定，调整每个类的质心也可以使J减小。这两个过程就是内循环中使J单调递减的过程。当J递减到最小时，和c也同时收敛。（在理论上，可以有多组不同的和c值能够使得J取得最小值，但这种现象实际上很少见）。由于畸变函数J是非凸函数，意味着我们不能保证取得的最小值是全局最小值，也就是说k-means对质心初始位置的选取比较感冒，但一般情况下k-means达到的局部最优已经满足需求。但如果你怕陷入局部最优，那么可以选取不同的初始值跑多遍k-means，然后取其中最小的J对应的和c输出。下面累述一下K-means与EM的关系，首先回到初始问题，我们目的是将样本分成k个类，其
27、实说白了就是求每个样例x的隐含类别y，然后利用隐含类别将x归类。由于我们事先不知道类别y，那么我们首先可以对每个样例假定一个y吧，但是怎么知道假定的对不对呢？怎么评价假定的好不好呢？我们使用样本的极大似然估计来度量，这里是就是x和y的联合分布P(x,y)了。如果找到的y能够使P(x,y)最大，那么我们找到的y就是样例x的最佳类别了，x顺手就聚类了。但是我们第一次指定的y不一定会让P(x,y)最大，而且P(x,y)还依赖于其他未知参数，当然在给定y的情况下，我们可以调整其他参数让P(x,y)最大。但是调整完参数后，我们发现有更好的y可以指定，那么我们重新指定y，然后再计算P(x,y)最大时的参数
28、，反复迭代直至没有更好的y可以指定。这个过程有几个难点，第一怎么假定y？是每个样例硬指派一个y还是不同的y有不同的概率，概率如何度量。第二如何估计P(x,y)，P(x,y)还可能依赖很多其他参数，如何调整里面的参数让P(x,y)最大。这里只是指出EM的思想，E步就是估计隐含类别y的期望值，M步调整其他参数使得在给定类别y的情况下，极大似然估计P(x,y)能够达到极大值。然后在其他参数确定的情况下，重新估计y，周而复始，直至收敛。对应于K-means来说就是我们一开始不知道每个样例对应隐含变量也就是最佳类别。最开始可以随便指定一个给它，然后为了让P(x,y)最大（这里是要让J最小），我们求出在给
29、定c情况下，J最小时的（前面提到的其他未知参数），然而此时发现，可以有更好的（质心与样例距离最小的类别）指定给样例，那么得到重新调整，上述过程就开始重复了，直到没有更好的指定。这样从K-means里我们可以看出它其实就是EM的体现，E步是确定隐含类别变量，M步更新其他参数来使J最小化。这里的隐含类别变量指定方法比较特殊，属于硬指定，从k个类别中硬选出一个给样例，而不是对每个类别赋予不同的概率。总体思想还是一个迭代优化过程，有目标函数，也有参数变量，只是多了个隐含变量，确定其他参数估计隐含变量，再确定隐含变量估计其他参数，直至目标函数最优。计算推荐。基于用户的 CF 的基本思想相当简单，基于用户
30、对物品的偏好找到相邻邻居用户，然后将邻居用户喜欢的推荐给当前用户。计算上，就是将一个用户对所有物品的偏好作为一个向量来计算用户之间的相似度，找到 K 邻居后，根据邻居的相似度权重以及他们对物品的偏好，预测当前用户没有偏好的未涉及物品，计算得到一个排序的物品列表作为推荐。图 2 给出了一个例子，对于用户 A，根据用户的历史偏好，这里只计算得到一个邻居 - 用户C，然后将用户C喜欢的物品D 推荐给用户A。 图2.3 基于用户的 CF 的基本原理(2) 基于内容的协同过滤基于内容（物品）的CF的原理和基于用户的CF类似，只是在计算邻居时采用物品本身，而不是从用户的角度，即基于用户对物品的偏好找到相似
31、的物品，然后根据用户的历史偏好，推荐相似的物品给他。从计算的角度看，就是将所有用户对某个物品的偏好作为一个向量来计算物品之间的相似度，得到物品的相似物品后，根据用户历史的偏好预测当前用户还没有表示偏好的物品，计算得到一个排序的物品列表作为推荐。图 3 给出了一个例子，对于物品A，根据所有用户的历史偏好，喜欢物品 A的用户都喜欢物品C，得出物品A和物品C比较相似，而用户C喜欢物品A那么可以推断出用户C可能也喜欢物品C。 图2.4 基于内容的 CF 的基本原理2.2.3 基于规则的过滤基于关联规则的推荐更常见于电子商务系统中，并且也被证明行之有效。其实际的意义为购买了一些物品的用户更倾向于购买另一
32、些物品。基于关联规则的推荐系统的首要目标是挖掘出关联规则，也就是那些同时被很多用户购买的物品集合，这些集合内的物品可以相互进行推荐。 目前关联规则挖掘算法主要从Apriori2和FP-Growth两个算法发展演变而来。Apriori算法思路实现简单，通过迭代不断通过K-1元频繁项目集生成K元频繁项目集，直到不能生成为止，最终可以得到最大频繁项目集。Apriori算法存在的问题是每次迭代都要判断生成K元集合的K-1元子集是否都是频繁项目集，计算量巨大；并且Apriori算法是一个挖掘最大频繁项目集的算法，无法得到全部频繁模式集合。FP-Growth算法通过构建FP-Tree（频繁模式树），去发现频繁模式集。相比于Apriori算法，计算量较少，并且可以得出几乎所有的频繁项目集；但该算法实现起来要比Apriori复杂，并且FP-Gro
