个性化推荐系统设计毕业论文.docx

个性化推荐系统设计毕业论文目录1研究目的11.1 研究背景及意义11.2 推荐系统现状21.3 论文内容与章节安排32理论支持与相关技术的应用与背景42.1 相应的推荐算法及数学原理42.2 Weka的技术介绍与应用152.2.1 Weka系统简介152.2.2 Weka系统的特点与应用153 习题个性化推荐系统的设计原理193.1 研究难题解决193.2 基于记忆的过滤203.2.1 基于用户的协同过滤203.2.2 基于内容的协同过滤223.3 基于规则的过滤223.4 通过比例因子进行优化244 系统的实现254.1 需求分析254.2 概要设计264.2.1 数据采集与预处理阶段264.2.2 数据处理阶段264.3 数据库的设计284.4 推荐系统的总体结构304.5 系统详细设计314.5.1 用户信息管理模块314.5.2 用户推荐模块344.5.3 用户搜索模块364.5.4 系统的开发环境365 总结42参考文献44致谢辞45附录46附录1 英文原文46附录2 中文原文54附录3 部分代码591 研究目的智能在线学习系统1是个性化推荐的一种应用，本文介绍的是基于OJ数据的习题个性化推荐系统，本章简要介绍个性化推荐的概念、背景与国内外研究现状，并且针对目前流行的推荐方法予以介绍。1.1研究背景及意义近年来，随着互联网、移动设备等信息技术的迅猛发展，除了企业业务运营中不断积累的交易等业务数据之外，遍布全球的传感器无时无刻不在探测和收集物理世界的各种信息，移动互联网则在不断收集用户的地理位置信息，各种社会媒体中的数以亿计的用户也在随时随地地产生交互信息，这些数据不仅是数量巨大（以TB甚至PB为单位），而且形式繁多，除了企业业务运营信息系统中的结构化数据之外，各种文本、声音、图片、视频、地理位置等各种不同类型的数据决定了数据的多样性。同时，这些时刻变化的来自各种数据源的数据有充满了噪音，对这些数据的管理和分析已经超出了传统的数据管理技术的能力，因此，人们称其为大数据2。在教育领域，智能教学系统（Intellectual Tutoring System）利用人工智能和计算机技术来模拟现实教学过程，使得该系统具备了人力教学所不具备的高效率、高存储、个性化等特点。其广阔的发展前景使得越来越多的专家开始投入到对ITS的研究中，希望可以凭借计算机对知识的有效处理，由计算机代替老师来提高学生学习效率，并最终实现人类对其自身认知过程的终极解码。智能教学系统作为一种辅助教学手段，其中运用传统的个性化推荐方法有其局限性，对于基于用户的协同过滤,推荐的原则必须要求用户会喜欢那些和他有相同喜好的用户喜欢的东西；对于基于内容的协同过滤则有个前提，就是用户会喜欢和他以前喜欢的东西相似的东西，那么我们可以计算一个用户喜欢的物品的自相似度。一个用户喜欢物品的自相似度大，就说明他喜欢的东西都是比较相似的，只有在这种情况下，该方法才会具有较高的推荐效率。为了能够提高个性化推荐系统的准确率，本论文摒弃单一的协同过滤方法，提出新的推荐方法思路并将其理论应用智能在线学习系统中，更大的发挥在线学习系统个性化推荐的作用，为学生提供更优质的服务。1.2推荐系统现状目前对于个性化推荐系统的研究正处于高速发展期,相关的推荐算法也已在电子商务领域、个性化搜索等领域得到一定程度的发展和应用。传统的个性化推荐算法包括基于内容的推荐、基于行为的推荐、以及混合推荐算法，其中基于行为的个性化推荐算法凭借其出色的行为分析和兴趣建模，得到了业内专家学者的广泛研究。但具体到在线学习系统领域，系统本身包含的知识评测系统、以及知识表示系统决定了ITS中的个性化推荐模块对知识的依赖多余对用户学习行为的依赖。相比于利益驱动的电子商务领域个性化推荐算法的蓬勃发展，主要应用于教育领域的个性化推荐算法的研究则相对疲软。由于教育领域内知识本身具有很强的语义关系，软件对用户的辅导更多地是强调用户在认知学习中对知识语义间联系的掌握。而应用较为广泛基于行为的个性化推荐算法，其原理则是通过构建邻居矩阵来判断用户的兴趣来为用户进行资源推荐，对于智能教辅而言，单一的基于用户的协同过滤和基于内容的协同过滤算法推荐结果忽略了用户在进行知识学习时表现出的认知特点，其准确度势必降低。因此，本文将在前人的基础上，研究基于记忆的个性化推荐算法，在本系统中，包含两个纬度：其一，基于用户（学生）的协同过滤4，其二，基于内容（习题）的协同过滤，两者都是利用学生用户过去使用在线学习系统的历史提交记录，从而对学生进行习题个性化推荐。将算法研究重点放到对知识结构与习题资源本身的信息的利用和处理上，以解决在ITS系统中为学生从海量资源中进行个性化资源推荐的问题，并将通过实验证明该算法和系统的理论价值与应用价值。1.3论文内容与章节安排对于介绍基于OJ数据的习题个性化推荐系统论文以下内容安排如下：第二部分侧重介绍本系统数据处理过程中依据的理论知识背景及技术应用；第三部分讲述了习题推荐系统实现过程中遇到的难题及整个系统的设计思路；第四部分描述系统实现的详细步骤；第五部分总结了本系统设计与实现过程中的心得与体会。2 理论支持与相关技术的应用与背景习题个性化推荐系统所运用的理论来源于集体智慧，本系统中实现该理论的具体方法是基于记忆的协同过滤和基于规则的协同过滤。鉴于开源软件Weka的强大功能和对Java应用程序的支持，我们采用Java作为开发语言，调用Weka程序返回的数据。下面对这些方法的数学原理和工具或平台做具体介绍。2.1相应的推荐算法及数学原理2.1.1集体智慧与协同过滤集体智慧 (Collective Intelligence) 7并不是Web2.0时代特有的，只是在Web2.0时代，大家在Web应用中利用集体智慧构建更加有趣的应用或者得到更好的用户体验。集体智慧是指在大量的人群的行为和数据中收集答案，帮助你对整个人群得到统计意义上的结论，这些结论是我们在单个个体上无法得到的，它往往是某种趋势或者人群中共性的部分。协同过滤是利用集体智慧的一个典型方法。要理解什么是协同过滤 (Collaborative Filtering, 简称 CF) 5，首先想一个简单的问题，如果你现在想看个电影，但你不知道具体看哪部，你会怎么做？大部分的人会问问周围的朋友，看看最近有什么好看的电影推荐，而我们一般更倾向于从口味比较类似的朋友那里得到推荐。这就是协同过滤的核心思想。协同过滤一般是在海量的用户中发掘出一小部分和你品位比较类似的，在协同过滤中，这些用户成为邻居，然后根据他们喜欢的其他东西组织成一个排序的目录作为推荐给你。当然其中有一个核心的问题：如何确定一个用户是不是和你有相似的品位？如何将邻居们的喜好组织成一个排序的目录？协同过滤相对于集体智慧而言，它从一定程度上保留了个体的特征，就是你的品位偏好，所以它更多可以作为个性化推荐的算法思想。可以想象，这种推荐策略在 Web 2.0 的长尾中是很重要的，将大众流行的东西推荐给长尾中的人怎么可能得到好的效果，这也回到推荐系统的一个核心问题：了解你的用户，然后才能给出更好的推荐2.1.2基于记忆的过滤(1)基于用户的协同过滤 首先，要实现协同过滤，需要以下3个核心步骤：收集用户偏好:从用户的行为和偏好中发现规律，并基于此给予推荐，如何收集用户的偏好信息成为系统推荐效果最基础的决定因素。用户有很多方式向系统提供自己的偏好信息，而且不同的应用也可能大不相同。收集了用户行为数据，我们还需要对数据进行一定的预处理，其中最核心的工作就是：减噪和归一化2。减噪：用户行为数据是用户在使用应用过程中产生的，它可能存在大量的噪音和用户的误操作，我们可以通过经典的数据挖掘算法过滤掉行为数据中的噪音，这样可以是我们的分析更加精确。归一化：如前面讲到的，在计算用户对物品的喜好程度时，可能需要对不同的行为数据进行加权。但可以想象，不同行为的数据取值可能相差很大，比如，用户的查看数据必然比购买数据大的多，如何将各个行为的数据统一在一个相同的取值范围中，从而使得加权求和得到的总体喜好更加精确，就需要我们进行归一化处理。最简单的归一化处理，就是将各类数据除以此类中的最大值，以保证归一化后的数据取值在 0,1 范中。进行的预处理后，根据不同应用的行为分析方法，可以选择分组或者加权处理，之后我们可以得到一个用户偏好的二维矩阵，一维是用户列表，另一维是物品列表，值是用户对物品的偏好，一般是 0,1 或者 -1, 1 的浮点数值。找到相似的用户(通过相似度找到相似用户):1、相似度的计算关于相似度的计算，现有的几种基本方法都是基于向量（Vector）的，其实也就是计算两个向量的距离，距离越近相似度越大。在推荐的场景中，在用户 - 物品偏好的二维矩阵中，我们可以将一个用户对所有物品的偏好作为一个向量来计算用户之间的相似度，或者将所有用户对某个物品的偏好作为一个向量来计算物品之间的相似度。下面我们详细介绍几种常用的相似度计算方法：a欧几里德距离（Euclidean Distance）6最初用于计算欧几里德空间中两个点的距离，假设 x，y 是 n 维空间的两个点，它们之间的欧几里德距离是：可以看出，当 n=2 时，欧几里德距离就是平面上两个点的距离。当用欧几里德距离表示相似度，一般采用以下公式进行转换：距离越小，相似度越大。b皮尔逊相关系数（Pearson Correlation Coefficient）皮尔逊相关系数一般用于计算两个定距变量间联系的紧密程度，它的取值在 -1，+1 之间。sx, sy是 x 和 y 的样品标准偏差。2、相似邻居的计算介绍完相似度的计算方法，下面我们看看如何根据相似度找到用户 - 物品的邻居，常用的挑选邻居的原则可以分为两类：图 2.1 给出了二维平面空间上点集的示意图。固定数量的邻居：K-neighborhoods 或者 Fix-size neighborhoods不论邻居的“远近”，只取最近的K个，作为其邻居。如图2.1中的A，假设要计算点1的5个邻居，那么根据点之间的距离，我们取最近的5个点，分别是点2，点3，点4，点7和点5。但很明显我们可以看出，这种方法对于孤立点的计算效果不好，因为要取固定个数的邻居，当它附近没有足够多比较相似的点，就被迫取一些不太相似的点作为邻居，这样就影响了邻居相似的程度，比如图1中，点1和点5其实并不是很相似。基于相似度门槛的邻居：Threshold-based neighborhoods与计算固定数量的邻居的原则不同，基于相似度门槛的邻居计算是对邻居的远近进行最大值的限制，落在以当前点为中心，距离为 K 的区域中的所有点都作为当前点的邻居，这种方法计算得到的邻居个数不确定，但相似度不会出现较大的误差。如图 1 中的 B，从点1出发，计算相似度在 K内的邻居，得到点2，点3，点4和点7，这种方法计算出的邻居的相似度程度比前一种优，尤其是对孤立点的处理。图2.1相似邻居计算示意图固定聚类数的邻居: K-means算法是很典型的基于距离的聚类算法，采用距离作为相似性的评价指标，即认为两个对象的距离越近，其相似度就越大。该算法认为簇是由距离靠近的对象组成的，因此把得到紧凑且独立的簇作为最终目标。对应的元素同样可以找到自己的邻居，本系统采用EM聚类分析算法，以下对K-Means聚类分析与EM聚类分析比较：在聚类问题中，给我们的训练样本是，每个，没有了y。K-means算法是将样本聚类成k个簇（cluster），具体算法描述如下：1、 随机选取k个聚类质心点（cluster centroids）为。2、 重复下面过程直到收敛 对于每一个样例i，计算其应该属于的类对于每一个类j，重新计算该类的质心图2.2K-means聚类分析示意图如上图所示，K是我们事先给定的聚类数，代表样例i与k个类中距离最近的那个类，的值是1到k中的一个。质心代表我们对属于同一个类的样本中心点的猜测，拿星团模型来解释就是要将所有的星星聚成k个星团，首先随机选取k个宇宙中的点（或者k个星星）作为k个星团的质心，然后第一步对于每一个星星计算其到k个质心中每一个的距离，然后选取距离最近的那个星团作为，这样经过第一步每一个星星都有了所属的星团；第二步对于每一个星团，重新计算它的质心（对里面所有的星星坐标求平均）。重复迭代第一步和第二步直到质心不变或者变化很小。K-means面对的第一个问题是如何保证收敛，前面的算法中强调结束条件就是收敛，可以证明的是K-means完全可以保证收敛性。下面我们定性的描述一下收敛性，我们定义畸变函数（distortion function）如下：J函数表示每个样本点到其质心的距离平方和。K-means是要将J调整到最小。假设当前J没有达到最小值，那么首先可以固定每个类的质心，调整每个样例的所属的类别来让J函数减少，同样，固定，调整每个类的质心也可以使J减小。这两个过程就是内循环中使J单调递减的过程。当J递减到最小时，和c也同时收敛。（在理论上，可以有多组不同的和c值能够使得J取得最小值，但这种现象实际上很少见）。由于畸变函数J是非凸函数，意味着我们不能保证取得的最小值是全局最小值，也就是说k-means对质心初始位置的选取比较感冒，但一般情况下k-means达到的局部最优已经满足需求。但如果你怕陷入局部最优，那么可以选取不同的初始值跑多遍k-means，然后取其中最小的J对应的和c输出。下面累述一下K-means与EM的关系，首先回到初始问题，我们目的是将样本分成k个类，其实说白了就是求每个样例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)最大时的参数，反复迭代直至没有更好的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最小），我们求出在给定c情况下，J最小时的（前面提到的其他未知参数），然而此时发现，可以有更好的（质心与样例距离最小的类别）指定给样例，那么得到重新调整，上述过程就开始重复了，直到没有更好的指定。这样从K-means里我们可以看出它其实就是EM的体现，E步是确定隐含类别变量，M步更新其他参数来使J最小化。这里的隐含类别变量指定方法比较特殊，属于硬指定，从k个类别中硬选出一个给样例，而不是对每个类别赋予不同的概率。总体思想还是一个迭代优化过程，有目标函数，也有参数变量，只是多了个隐含变量，确定其他参数估计隐含变量，再确定隐含变量估计其他参数，直至目标函数最优。计算推荐。基于用户的 CF 的基本思想相当简单，基于用户对物品的偏好找到相邻邻居用户，然后将邻居用户喜欢的推荐给当前用户。计算上，就是将一个用户对所有物品的偏好作为一个向量来计算用户之间的相似度，找到 K 邻居后，根据邻居的相似度权重以及他们对物品的偏好，预测当前用户没有偏好的未涉及物品，计算得到一个排序的物品列表作为推荐。图 2 给出了一个例子，对于用户 A，根据用户的历史偏好，这里只计算得到一个邻居 - 用户C，然后将用户C喜欢的物品D 推荐给用户A。图2.3基于用户的 CF 的基本原理(2)基于内容的协同过滤基于内容（物品）的CF的原理和基于用户的CF类似，只是在计算邻居时采用物品本身，而不是从用户的角度，即基于用户对物品的偏好找到相似的物品，然后根据用户的历史偏好，推荐相似的物品给他。从计算的角度看，就是将所有用户对某个物品的偏好作为一个向量来计算物品之间的相似度，得到物品的相似物品后，根据用户历史的偏好预测当前用户还没有表示偏好的物品，计算得到一个排序的物品列表作为推荐。图 3 给出了一个例子，对于物品A，根据所有用户的历史偏好，喜欢物品 A的用户都喜欢物品C，得出物品A和物品C比较相似，而用户C喜欢物品A那么可以推断出用户C可能也喜欢物品C。图2.4基于内容的 CF 的基本原理2.1.3基于规则的过滤基于关联规则的推荐更常见于电子商务系统中，并且也被证明行之有效。其实际的意义为购买了一些物品的用户更倾向于购买另一些物品。基于关联规则的推荐系统的首要目标是挖掘出关联规则，也就是那些同时被很多用户购买的物品集合，这些集合内的物品可以相互进行推荐。目前关联规则挖掘算法主要从Apriori2和FP-Growth两个算法发展演变而来。Apriori算法思路实现简单，通过迭代不断通过K-1元频繁项目集生成K元频繁项目集，直到不能生成为止，最终可以得到最大频繁项目集。Apriori算法存在的问题是每次迭代都要判断生成K元集合的K-1元子集是否都是频繁项目集，计算量巨大；并且Apriori算法是一个挖掘最大频繁项目集的算法，无法得到全部频繁模式集合。FP-Growth算法通过构建FP-Tree（频繁模式树），去发现频繁模式集。相比于Apriori算法，计算量较少，并且可以得出几乎所有的频繁项目集；但该算法实现起来要比Apriori复杂，并且FP-Growth需要将全部数据库事务加载到内存中，而Apriori虽然需要反复读取数据库事务，但是不需要全部载入内存。一般而言，FP-Growth要比Apriori快至少一个数量级。关联规则挖掘中有两个主要的概念，支持度和置信度。支持度是指包含某频繁项目集的事务数和总数据库事务数的百分比。置信度指包含某频繁项目集的事务数和包含被推荐项目集的事务数的百分比。而最小支持度阈值和最小置信度阈值也是决定一个事务集合是否是频繁事务集和一个关联规则是否成立的决定因素。因此这两个阈值也决定了推荐系统的准确率和召回率。基于关联规则的推荐系统一般转化率较高，因为当用户已经购买了频繁集合中的若干项目后，购买该频繁集合中其他项目的可能性更高。缺点在于计算量较大，但是可以离线计算，因此影响不大。同时基于关联规则的推荐系统由于采用用户数据，不可避免的存在冷启动和稀疏性问题。并且存在热门项目容易被过度推荐的问题。此外，基于item的推荐体系多采用1toN的推荐模式，因此实际的关联规则相当于从二元频繁项目集产生（即1to1的模式），1-1这种关联规则的相关性要远低于M-N这种最初关联规则的推荐形式。因此基于关联规则的推荐系统很少被应用于item的推荐体系。2.2Weka的技术介绍与应用2.2.1Weka系统简介WEKA的全名是怀卡托智能分析环境（Waikato Environment for Knowledge Analysis）,它是由怀卡托大学研究而成的，是一个完全开放的数据挖掘工作平台，集合了大量能承担数据挖掘任务的机器学习算法，包括对数据进行预处理、分类、聚类、关联规则、属性选择以及在新的交互式界面上实现可视化等。 WEKA系统的实现源自Eibe Frank等学者在机器学习方面的研究积累，1998年之前的WEKA版本是用C+来实现的，从1998年起，Eibe Frank开始用Java语言重新编写该系统，这一举动还得到了项目组里其它成员以及若干自由软件人的帮助。2005年8月，在第11届ACM SIGKDD国际会议上，怀卡托大学的WEKA小组荣获了数据挖掘和知识探索领域的最高服务奖，WEKA系统得到了社会的广泛认可，被誉为数据挖掘和机器学习历史上的里程碑，是现今最完备的数据挖掘工具之一。2.2.2Weka系统的特点与应用WEKA 是一套免费的提供学术许可、未与其它系统集成的、未汉化的通用软件，作为数据挖掘学术界的典型代表，它有如下特点： (1)跨平台，支持 Windows 与 Unix 等很多操作系统； (2)支持结构化文本文件、支持数据挖掘格式文件(C4.5)、提供数据库接口(JDBC)； (3)可处理连续型、离散型(字符型、日期型)数据； (4)提供空缺值处理、消除噪声、标准化、数据离散化、属性构造、转换变量、拆分数据、数据平衡、样本排序、样本洗牌、数据聚集、维归约、值归约、抽样操作； (5)能完成预处理、分类、聚类、关联、可视化等任务； (6)支持机器学习方法和神经网络方法； (7)提供算法组合、用户算法嵌入、算法参数设置(基本、高级)； (8)能生成基本报告、测试报告、输出格式，实现模型解释、模型比较、数据评分功能； (9)实现数据可视化、挖掘过程可视化及挖掘结果可视化(理解、评估)。 WEKA 的诸多特点可以反映出，WEKA 的功能还是比较完善的。WEKA 数据挖掘平台完整、实用、高水准地实现了许多流行的学习方案，这些方案能够直接运用于一些实际的数据挖掘或研究领域。除此，它还提供了一个 Java 类库形式的框架，这个框架支持嵌入式机器学习的应用，乃至新的学习方案的实现。 在进行 WEKA 数据挖掘实验之前，首先应该来了解一下整个 WEKA 系统的数据挖掘过程。如图 2.5所示，整个 WEKA 数据挖掘系统的过程包括输入要测试的数据集，然后对待测数据进行预处理，再将处理后的数据集置于一种学习方案中并分析其结果或是将已学习到的模型来预测未知的实例，或是将数据集置于不同的学习方案中，针对各种方案的学习结果进行模式评估，以找出最佳性能的学习方案。 下面简单介绍数据挖掘流程的每个层次： (1)数据输入层：是整个数据挖掘的准备阶段，数据输入方式有三种，分别为打开当地文件，数据库导入。其中，打开当地文件的方式可以导入 ARFF,CSV,C4.5,BSI 四种格式文件，它们利用文件载入器导入数据。而从数据库导入数据则必须要装载 JDBC 驱动程序，并利用 SQL 选择语句获取实例。 (2)数据挖掘层：包括预处理，分类，聚类等功能，其中预处理是整个数据挖掘的最重要部分，它包括对数据的装载、对缺失数据项的填补、属性过滤及实例过滤等功能。在该层，先对数据进行预处理，再将处理后的数据集置于学习方案中，进行相应的挖掘任务。 (3)模式评估层：对于数据挖掘的结果进行模式评估，分析并学习数据挖掘结果。 (4)可视化层：实现数据可视化、挖掘过程可视化、挖掘结果可视化，给挖掘提供了良好的辅助工具，提高了挖掘效率。 (5)存储层：以特定的格式对挖掘过后的结果进行存储。 图2.5WEKA 数据挖掘系统3习题个性化推荐系统的设计原理在了解个性化推荐基本算法的基础之上，本节主要将会讲述在开发基于OJ数据的习题个性化推荐系统过程中解决的难题，除此以外将会具体介绍怎样将基于记忆的协同过滤和基于规则的协同过滤两种方法融合之后运用到本系统之中，真正的将用户的历史习题记录利用率达到最大化，进而提高推荐习题对用户的准确率。3.1研究难题解决冷启动问题一直是推荐系统需要解决的难题，本系统针对在线推荐系统中如何为新用户推荐合适的习题内容展开研究，推出了基于群体智慧的行为预测模型，提出了一个三阶段的推荐方法，首先，根据老用户之间的习题内容范围将用户进行分群，使得在同一水平的用户聚集到一个群体中。其次，对于没有历史习题记录的新用户，计算其属于每个用户群的概率。最后，提出一种新颖的度量方法，估计一个用户群的用户对某推荐习题的感兴趣程度的概率，这样就避免了数据稀疏带来的问题。基于一个新用户隶属每个用户群的概率和用户群对推荐习题的概率，就可以预测新用户对某习题的感兴趣程度并进行推荐。该方法有效的解决了冷启动问题和数据稀疏的问题，提高了推荐的效率。基于OJ数据的个性化习题推荐系统的关键点在于利用学生用户的历史习题提交记录，因此系统的核心在于怎样可以整合学生的信息并且运用于系统算法之中。每个用户都有自己的历史提交序列，影响序列的因素有：提交成绩（Result或者Score）、提交题目的难度（Level），利用这两个因素整合出可以体现当前时间点下哪些习题是适合当前学生的序列。利用用户都有自己的历史提交序列，具有下面性质的序列:（1）该序列是一个链表，该链表的每个元素隐含（真正存储不需要六个）有六个个成员变量:变量a题目号（对应题目表中的id）、变量b题目得分（用于进行基于用户的协同过滤）、变量c(对应题目表中的关键词属性知识点，用于下面分析基于习题内容的协同过滤）、变量d(权重信息，用于排序）、变量 e题目难度、f提交次数.权重的计算： 对题目得分和题目难度进行数据归一化；(e*t)/（b*f）(e表示题目难度，t表示答题时间，b表示题目得分Score,f表示提交次数)； 权重决定了习题未来出现在推荐题目中的概率大小。（2）越靠近序列的头部，越有可能出现在候选题中。（用于建立用户的序列模式分析树）；（3）该序列可以在协同过滤中根据余弦求之间的相似性。3.2基于记忆的过滤3.2.1基于用户的协同过滤OJ系统记录了每个学生（对应学号）的历史习题提交记录，通过对OJ系统数据库提供的数据进行预处理后，得到图3.1：表3.1 源数据处理成果班号class学号Number题号content次数f题目难度e答题时间t最高得分s比重p2013010501201301050101105323221.5000 2013010501201301050101105443220.7500 2013010501201301050101105523221.5000 2013010501201301050101106143220.7500 2013010501201301050101106223221.5000 2013010501201301050101108063220.5000 2013010501201301050101108923221.5000 2013010501201301050101109323221.5000 2013010501201301050101109423221.5000 2013010501201301050101109623221.5000 2013010501201301050101110723221.5000 2013010501201301050101114443220.7500 2013010501201301050101115043220.7500 2013010501201301050101115123221.5000 说明： s得分：由学生提交同一个题目的最高得分为标准； f次数：源数据直接整理得到； e题目难度：系统中的题目难度分为五个等级（1、2、3、4、5）。（由于目前源数据中没有将习题进行难度分类，所以该字段的初始化为3）； t答题时间：限制为一个小时，分为三个时间段（10分钟以内，30分钟以内，60分钟以内，分为1，2，3个阶段）（源数据中没有学生答题时间的记录，初始化为2）。系统中Student类的再次初始化，在Student类中包含了学号sId，学生姓名sName，历史习题记录SCMapping,候选题目scmList为null,运行weka之后，得出scmList，利用weka返回的系统过滤结果，利用基于用户的协同过滤，可以得到信息： 我做了A题目，我想看看做了A题目的同学接下来会做哪些题目，weka得分析出和我做题相似的用户学号。基于上述的情景描述，运行一次weka后的系统数据的更新（基于记忆的过滤的应用）：假设我已经知道了groupA和我做的题目相似（gruopA有10个人），系统接收来自weka返回的十个学号，通过对这10个学号的Student类进行搜索对应的SCMap记录，从而找到候选题Contents1（待处理）。 3.2.2基于内容的协同过滤基于内容的 CF 的原理和基于用户的 CF 类似，只是在计算邻居时采用内容本身，而不是从用户的角度，即基于用户对内容的偏好找到相似的内容，然后根据用户的历史偏好，推荐相似的内容给他。系统中Content类的初始化，在Content类中包包含了题号cId,标题title，题目内容detail,历史习题记录scmList,相关习题clist.为null,关键字coreWord,基于内容（习题）的协同过滤，简单而言就是传递信息：我做了A题目，感觉掌握不牢固，还想做同一类型下的题目，weka得告诉我A题目的类型下的题目还有什么。回顾上述的情景描述，运行一次weka后的系统数据会更新。假设我做了A题目，通过weka返回gruopB和A题目类似（gruop有10个题号）;系统接收来自weka返回的十个题号，通过对这10题号进行搜索，从而找到另一部分题目Contents2（待处理）。通过比例因子对Contents1、 Contents2进行加权得到在基于记忆的过滤下的候选题ContentA。3.3 基于规则的过滤最常见的空间关联规则挖掘技术，是所谓的“支持-置信”分析。以消费者在超市购买商品为例，如果把每一个消费者的一次购买看作一个事件， 考虑从商品X到商品Y的关联规则,支持度是指在所有事件中同时购买商品X和商品Y的比例置信度则是在所有购买了商品X的事件中也购买商品Y的比例。如果支持度和置信度都超过了相应的阈值，则从X到Y的规则被认为是有效的。图3.1关联规则示意图习题个性化推荐利用运用关联规则最广的Apriori算法，构建序列模式分析树（得到候选题Contents3），利用学生成绩表进行聚类分析；(得到候选题Contents4)，通过比例因子得到基于规则的过滤下的候选题ContentB。图3.2算法Apriori部分代码3.4 通过比例因子进行优化利用比例因子将上面两种方式得到的ContentA和ContentB进行重新分配，比例因子的作用主要是为了权衡基于记忆的协同过滤和基于规则的协同过滤两种方法的效果，其中的因子不是能够预测出来的，需要的大量的数据作为基础得出大小，从而可以更好的提高推荐系统的效果，并且比例因子的大小需要不断的调节，最好的情况就是能够随着数据的训练，不断的自我优化。在这种情况之下，最终得到每个用户下的候选题目，赋值给Student类下的scmList字段。4系统的实现本论文中提到的习题个性化推荐系统采用3层架构模式，分别为Web显示层，数据访问层和数据库。系统的总体设计架构如图4.1所示：Web显示层数据访问层数据库连接数据库MySQL图4.1系统三层架构图Web 显示层即为JSP页面层，为用户提供应用程序的访问，本论文中的系统以Web页面的形式实现。数据访问层为Web显示层提供数据服务，一般封装操作数据库的选择，添加、更新和删除等操作，同时还为Web显示层提供访问数据库的接口或者函数等。数据库位于系统最底层，它存储系统的所有数据。4.1需求分析在线教学系统作为一种辅助教学的手段，大部分智能教学系统缺乏有效的学习资源推荐机制，使得用户在面对海量资源时，无法准确地寻找到满足自身学习需求的学习资料，进而导致用户学习兴趣下降，无法发挥教辅系统的最大作用。为了能够解决在海量题库中为学生提供个性化资源推荐的问题，本系统将基于用户的协同过滤、基于内容的协同过滤和基于规则的过滤三种常用方法结合在一起。4.2概要设计4.2.1数据采集与预处理阶段算法的实现需要大量的数据支持，因此数据的采集和预处理成为了设计系统的第一步骤，而且在整个系统实现中占据重要的地位。习题个性化推荐系统的信息来源主要指学生信息、习题信息以及学生成绩信息的采集与处理，具体步骤如图4.1所示。其中，信息分析包括图4.2数据采集步骤基础数据来源（初始化系统数据库需要的数据）： 1、习题库：题目难度等级，题号，题目类型，题目关键字2、学生库：学号，学生姓名 3、OJ系统提供的数据：学号，题号，得分S，答题时间T,提交次数F，题目难度E4.2.2数据处理阶段图4.3数据分析（1）数据的预处理（目标：初始化系统中的SCMap类，该类记录了学号、题号、比重（绝对比重），初始化该类的目的提供weka数据分析）：简单而言就是：将源数据中的相同学号和题号的记录整合为一条记录，具体方式参见整合原则难点：比重的计算：(e*t)/（s*f）整合原则： s得分：由学生提交同一个题目的最高得分为标准； f次数：源数据直接整理得到； e题目难度：系统中的题目难度分为五个等级（1、2、3、4、5）。（由于目前源数据中没有将习题进行难度分类，所以该字段的初始化为3）； t答题时间：限制为一个小时，分为三个时间段（10分钟以内，30分钟以内，60分钟以内，分为1，2，3个阶段）（源数据中没有学生答题时间的记录，初始化为2）；处理结果：初始化系统中的三个类，Student,Content,SCMap。（2）数据的处理分析 本系统建立在Java调用开源软件Weak的基础上，通过修改封装Weka中的协同过滤的方法，使之能够成为本系统核心功能习题推荐的主要算法，其主要应用是基于记忆的协同过滤，分别将基于用户的协同过滤和基于内容的协同过滤嵌入系统之中，供系统内部推荐引擎使用。除此之外，基于规则的协同过滤使用Apriori算法。4.3数据库的设计从系统共应用角度出发，系统设计了用户信息表（User）、学生表(Student)、习题表(Content)、用户习题映射表（SCMap）四张表，采用关系型数据库 MYSQL作为存储数据库，其中对应关系如下图4.4所示：图4.4个性化推荐系统数据表关系用户信息表，包含用户id，用户名，密码，班级，性别，状态，电子邮箱等信息：表4.1用户信息表字段名描述类型长度可否为空主键值域Id用户Id值String32NY无dept班级String20YN无account帐户名String20YN学号name姓名String20YN无password密码String20YN无headImg头像String255YN无gender性别String2YN男，女state状态（是否激活）String20YN是，否mobile手机String20YN无email邮箱String20YN无birthday生日Date0YN日期memo说明String255YN无Student表，包含学生学号，班级，候选题目：表4.2学生信息表字段名描述类型长度可否为空主键值域sId学生学号String32NY无Dept班级String20YN无scmList候选题SCMapYNSCMapContent表，包含题号，标题，题目内容，关键字，候选学生：表4.3习题表字段名描述类型长度可否为空主键值域cid题目id值String32NY无Title题目标题String32YN无Detail题目内容String255YN无coreWord关键字String20YN无scmList候选学生SCMapYNSCMapSCMap表，对应id，学号，题号，比重：表4.4学生习题映射表字段名描述类型长度可否为空主键值域Idid值String32NY无Stu学生StudentYNStudentCont题目ContentYNContentscImop可能性String20YN无4.4推荐系统的总体结构图4.5个性化推荐系统结构图系统会预先为每个即将登陆用户创建账户，其中帐户名为每位学生的学号，记录为Student类中的account字段，表示该用户的用户名。未注册的帐户名激活状态为否，当用户第一次登陆时，系统会请求用户注册相关信息并将该用户激活，注册成功即可登陆系统使用相关功能（本系统中未初始化的用户名不能注册登录使用）。当用户首次登陆系统，系统会识别该用户名的历史习题记录，通过基于记忆的过滤和基于规则的过滤，主页自动向用户推荐可能练习的题目，对应系统的个性化推荐模块；除此以外，用户可根据自己的需求，在搜索框内找到自己想要的题目，对应本系统搜索模块。系统会利用用户的历史习题记录，分析判断当前登录用户的行为，并且做出响应，反馈给用户可能需要的题目，用户可以从推荐模块挑选满足需求的题目。整个系统以习题推荐为核心功能，习题搜索做了辅助功能，从而使得该系统更好的满足用户的需求。4.5系统详细设计4.5.1用户信息管理模块4.5.1.1普通用户登录基于OJ数据的习题个性化推荐系统采用传统的登陆注册页面，系统新用户首次登陆系统，后台会进行认证（非系统内记录学生不能进行注册登录），参见下图:图4.6用户登录注册页面图4.7用户登录注册页面当系统内预设的用户首次注册激活账号，此时用户的账号处于激活状态，后台认证该用户，并且返回主页，左上角每一个系统用户都可以对个人信息进行管理：图4.8系统主页图4.9验证用户登陆4.5.1.2系统管理员登录为了方便习题推荐系统内部用户的管理，只有系统管理员可以对所有用户进行增加，删除，修改，查询，支持线上利用模板导入、导出用户到Excel。在这种情况下，该系统可以更好的为同学、老师服务，更好的解决了系统内用户的日常问题：图 4.10用户管理部分代码：图4.11界面代码4.5.2用户推荐模块系统识别用户信息，根据用户ID，从SCMap记录的信息（用户的历史习题记录），运行推荐引擎的算法，最终将习题推荐给最终用户，当用户没有历史习题记录时，本系统会对当前情况下其他用户最有可能出错的题目进行排序并将其推荐用户图4.12习题推荐页面识别用户部分代码 图4.13所示：图4.13识别用户部分代码分析历史习题记录推荐用户部分代码 图 4.14所示：图4.14EM算法部分代码4.5.3用户搜索模块该模块是为了更好的满足用户的日常需求，在系统初始化的时候，系统预先存储相关习题的关键词，用户可根据自己的需求，如下图所示，每一个进入系统的用户可以在搜索框内输入习题的关键词进行搜索相应的题目，系统会返回当前系统内与关键词相关的习题，用户可在返回列表中找到自己所需要的内容。图4.15用户搜索界面部分代码图4.16所示：图4.16习题搜索功能代码4.5.4系统的开发环境(1)开发工具IDE：Myeclipse Version: 10.7.1本体开发工具：weka系统测试工具：谷歌浏览器 版本 31.0.1650.63 (2)数据存储关系数据库：MySQL5.7本体存储：SCMap表 Student表习题存储：SCMap表 Content表(3)SSH(Struts+Spring+Hibernate)首先，SSH不是一个框架，而是多个框架（struts+spring+hibernate）的集成，是目前较流行的一种Web应用程序开源集成框架，用于构建灵活、易于扩展的多层Web应用程序。集成SSH框架的系统从职责上分为四层：表示层、业务逻辑层、数据持久层和域模块层（实体层）。Struts作为系统的整体基础架构，负责MVC的分离，在Struts框架的模型部分，控制业务跳转，利用Hibernate框架对持久层提供支持。Spring一方面作为一个轻量级的IoC容器，负责查找、定位、创建和管理对象及对象之间的依赖关系，另一方面能使Struts和Hibernate更好地工作。图4.17 SSH交互流程由SSH构建系统的基本业务流程是：1、在表示层中，首先通过JSP页面实现交互界面，负责传送请求(Request)和接收响应(Response)，然后Struts根据配置文件(struts-config.xml)将ActionServlet接收到的Reque