一种基于典型度和难度的题目推荐方法及其推荐装置

摘要

本发明公开了一种基于典型度和难度的题目推荐方法，方法包括：计算每个目标用户在每一类型题目上的做题情况，包括：题目的数量、难度以及目标用户在此类型题目上的通过率；根据目标用户特征向量，计算任意目标用户特征向量之间的相似性，并对每个目标用户，选择若干相似度最高的用户作为最近邻；依据最近邻用户的做题情况，预测目标用户对未做题目的评分；对目标用户，选择若干评分最高的目标题目作为目标用户的推荐结果。装置包括：计算模块、第一选择模块、评分模块和第二选择模块，本发明实现利用题目具有“难度”的特点来改进传统推荐方法，获得了较好的效果。本发明将来可以应用到学习网站中，帮助用户选择学习内容，制定个性化学习方案。

说明书

技术领域

本发明涉及数据挖掘、机器学习和信息检索领域，涉及协同过滤的推荐领域，尤其涉 及一种基于典型度和难度的题目推荐方法及其推荐装置。

背景技术

目前，已经有比较成熟的推荐系统和推荐算法，当前主流的推荐算法主要分为协同过 滤推荐(collaborativefiltering，CF)、基于内容的推荐(contentbased，CB)和混合推荐 方法(hybridmethods)。混合推荐算法即综合前两者，达到更好的效果。

在基于内容的推荐系统中，物品可以被描述为一系列属性值的向量，而描述物品特征 的属性值被称为“内容”。基于内容的推荐系统就是根据用户的历史评分行为，发现用户 偏好，并推荐与其偏好相近似的物品。这种方法主要用于推荐能以文本描述的物品，比如： 文献资料、新闻等等。

协同过滤算法通过用户之间的相似性或物品之间的相似性来预测用户对未知物品的 评分。主要依据用户之间相似性的被称为基于用户的最近邻推荐；主要依据物品间相似度 的被称为基于物品的最近邻推荐。协同过滤推荐方法成立的前提是假设用户的兴趣爱好长 期不变。

不论是基于内容的推荐系统，还是传统的协同过滤推荐系统，将其应用到知识推荐领 域时都有其不足。基于内容的推荐系统要能够准确地描述所推荐的物品的特征，并将其与 用户偏好对应起来，当面临类似题目这样特征较为模糊的数据时，就难以准确描述，以 致使推荐不准确。传统协同过滤方法不需要准确描述物品，却需要大量的评分数据，当将 其应用到推荐知识、推荐题目这一方面时，很难有足够的评分数据。

发明内容

本发明提供了一种基于典型度和难度的题目推荐方法及其推荐装置，本发明能够有效 克服传统推荐技术在应用到知识推荐上时，物品特征难以描述、评分信息少、且未充分考 虑题目难度这一重要特征的技术性问题，详见下文描述：

一种基于典型度和难度的题目推荐方法，所述题目推荐方法包括以下步骤：

计算每个目标用户在每一类型题目上的做题情况，包括：题目的数量、难度以及目标 用户在此类型题目上的通过率；

根据目标用户特征向量，计算任意目标用户特征向量之间的相似性，并对每个目标用 户，选择若干相似度最高的用户作为最近邻；

依据最近邻用户的做题情况，预测目标用户对未做题目的评分；

对目标用户，选择若干评分最高的目标题目作为目标用户的推荐结果。

其中，所述题目推荐方法还包括：

排除错误或无效的数据，然后按提交时间从小到大排序；

统计数据涉及的用户与题目，形成一个用户集合和一个题目集合。

其中，所述目标用户特征向量具体为：

＜type₁:typicality₁,type₂:typicality₂,…,type_i:typicality_i…,type_n:typicality_n＞

其中，type_i代表题目类型；typicality_i是目标用户在type_i类型题目上的典型度；i为题 目类型编号；n为题目类型总数。

一种基于典型度和难度的题目推荐装置，所述题目推荐装置包括：

计算模块，用于计算每个目标用户在每一类型题目上的做题情况，包括：题目的数量、 难度以及目标用户在此类型题目上的通过率；

第一选择模块，用于根据目标用户特征向量，计算任意目标用户特征向量之间的相似 性，并对每个目标用户，选择若干相似度最高的用户作为最近邻；

评分模块，用于依据最近邻用户的做题情况，预测目标用户对未做题目的评分；

第二选择模块，用于对目标用户，选择若干评分最高的目标题目作为目标用户的推荐 结果。

其中，所述题目推荐装置还包括：

预处理模块，用于排除错误或无效的数据，然后按提交时间从小到大排序；统计数据 涉及的用户与题目，形成一个用户集合和一个题目集合。

本发明提供的技术方案的有益效果是：

1、本发明为推荐系统在用户学习过程中的应用提供了新思路，在传统的用户特征表 示中引入做题难度来代表其能力水平，在一定程度上改善了传统推荐方法在题目推荐上的 效果。

2、跟基于用户的协调过滤方法相比，本发明能更好的描述用户特征，得到更准确的 题目推荐结果，能帮助用户选择学习内容，提高学习效率。

附图说明

图1为一种基于典型度和难度的题目推荐方法的流程图；

图2为难度系数引入比例的影响示意图；

图3为距离相似度的比较示意图；

图4为余弦相似度的比较示意图；

图5为一种基于典型度和难度的题目推荐装置的结构示意图；

图6为一种基于典型度和难度的题目推荐装置的另一结构示意图。

附图中，各标号所代表的部件列表如下：

1：计算模块；2：第一选择模块；

3：评分模块；4：第二选择模块；

5：预处理模块。

具体实施方式

为使本发明的目的、技术方案和优点更加清楚，下面对本发明实施方式作进一步地详 细描述。为了方便描述，本发明实施例中称要被推荐题目的用户为目标用户，称要被推荐 的一道题目为目标题目。

实施例1

本发明实施例提供了一种基于典型度和难度的题目推荐方法，参见图1，该题目推荐 方法包括以下步骤：

101：预处理数据；

本发明实施例处理的初始数据是用户做题的提交记录。首先排除错误或无效(例如： 缺失关键数据项)的数据，然后按提交时间从小到大排序。完成上述步骤后，统计数据涉 及的用户与题目，形成一个用户集合和一个题目集合。

102：对题目集合进行分类，计算题目的难度，以生成题目描述；

在本发明实施例中，使用题目的类型标签(如“动态规划”、“计算几何”，“组合数 学”……)对题目集合进行分类。此外，还要计算每道题目的难度。在本发明实施例中， 题目的难度被描述为被提交次数和通过率两个因素的函数，而这两个因素均可通过对步骤 101得到的数据统计得出。当题目的难度和类型已知后，将每道题目描述成一个二元组：< 类型，难度>。

103：计算每个目标用户在每一类型题目上的做题情况，即所做此类型题目的数量， 难度以及该用户在此类型题目上的通过率；

根据上述做题情况，计算该目标用户在此类型题目上的典型度；目标用户在每一类型 题目上的典型度形成该目标用户的特征描述(即特征向量)：

＜type₁:typicality₁,type₂:typicality₂,…,type_i:typicality_i…,type_n:typicality_n＞

其中，type_i代表题目类型，typicality_i是该目标用户在type_i类型题目上的典型度，i为 题目类型编号；n为题目类型总数。

104：根据目标用户特征向量，计算任意目标用户特征向量之间的相似性，并对每个 目标用户，选择若干相似度最高的用户作为其“最近邻”；

首先利用步骤103形成的用户特征向量，计算任意两个目标用户特征向量之间的相似 度，以此作为两目标用户间的相似度；然后对每个目标用户，选择若干相似度最高的用户 作为其“最近邻”。此处的“最近邻”，即传统协同过滤方法中所描述的最近邻，将作为预 测目标用户对目标题目评分的主要依据。

105：依据最近邻用户的做题情况，预测目标用户对未做题目的评分。

在本发明实施例中，针对目标题目和目标用户，计算做了此目标题目的最近邻用户数 目，将其归一化到[0，1]后作为用户对此目标题目的预测评分。

106：对目标用户，选择若干评分最高的目标题目作为对该目标用户的推荐结果。

该步骤106依据步骤105和步骤103。目标用户做题的频度越高，对其推荐题目的数 量越多，用户做题的频度由步骤103获得。确定了推荐数目后，根据步骤105产生的预测 评分，选择相应数量最高分的题目作为推荐结果。

本发明以实验数据中用户最后的提交时间为界，获取之后一段时间内目标用户的做题 情况，通过比较推荐结果跟实际做题情况，评价推荐的准确性。

综上所述，本发明实施例通过步骤101-步骤106充分考虑了题目难度这一重要特征， 改进了传统推荐方法，获得了较好的效果。

实施例2

下面结合具体的计算公式、例子对实施例1中技术方案进行详细描述，详见下文：

201：预处理数据；

即，排除一些不合法数据，例如：一些缺失了关键数据项的数据；另外，统计形成初 始的用户集合和题目集合，以明确本发明实施例处理的数据范围。

202：对题目集合进行分类，计算题目的难度；

通常，被越多人做的题目越简单，通过率越高的题越简单，此两者比较，前者更重要， 因为有些题目通过率很高，但只有个别人提交，这种题目往往并不简单。除此之外，不同 类别的题目之间有差异，例如：计算几何类的题目，由于解题的代码量大，细节问题多， 导致此类题目整体的通过率不高。综合以上这些实际情况，题目的难度系数通过公式(1) 计算。

${\mathrm{df}}_i=1.0-(\frac{3·{\mathrm{subCnt}}_i}{4·{\mathrm{mxSub}}_j}+\frac{{\mathrm{acRate}}_i}{4·{\mathrm{mxAc}}_j})---\left(1\right)$

其中，j为题目p_i所属的题目类别编号；mxSub_j是j类题目中，被提交次数最多的题 目的提交次数；mxAc_j是j类题目中，通过率最高的题目的通过率。subCnt_i和acRate_i分别 代表题目p_i的被提交次数和通过率。按上式计算出来的题目难度系数属于[0,1]。

203：计算用户特征向量；

用户特征向量即用户在每类题目上的典型度。

依据TyCo的计算方法(Cai,Yi,Leung,Ho-fung,LiQ,etal.TyCo:Towards Typicality-basedCollaborativeFilteringRecommendation[C]//201022ndInternational ConferenceonToolswithArtificialIntelligenceIEEEComputerSociety,2010:97-104)，用户在 一类题目对应用户组中的典型度，取决于两个因素，一个是用户对此类型题目的平均评分， 另一个是用户做这类题目的频繁程度。用户对此类题目评分越高，则对这类题目越感兴趣； 用户做此类题目越频繁，则对此类题目越感兴趣。按照以上两个因素分别计算出两个值， 用户在此类题目对应用户组中的典型度将是这两个值的平均值。用户u_i在第j类题目对应 用户组中的典型度v_i，j计算公式如式2所示。

$v_{i,j}=\frac{1}{2}({\bar{R}}_{i,j}+\frac{S_{i,j}}{{\Sigma }_{k=1}^n{S}_{i,k}})---\left(2\right)$

其中，是用户u_i对所做第j类题目的平均评分；S_i,j是用户u_i做j类题目的数量；S_i,k为用户u_i做k类题目的数量；n为题目类型总数。

事实上，在该应用场景中，用户对每道题目只有通过与未通过两种结果，通过评分为 1，否则为0；因此，用户对每类题目的平均评分R_i,j都是1，并不能代表用户的偏好或是 能力水平。

TyCo的应用场景主要是预测电影评分，而本发明实施例提出的(DF_TyCo)方法主要 用于题目推荐。难度是题目所特有的一个重要特征，用户所做题目的难度，在一定程度上 代表了用户的能力水平。本发明实施例中用户典型度计算公式如式3所示。

$v_{i,j}=\beta \frac{S_{i,j}}{{\Sigma }_{k=0}^{n-1}{S}_{i,k}}+(1-\beta )\frac{D_{i,j}}{{\Sigma }_{k=0}^{n-1}{D}_{i,k}}---\left(3\right)$

其中，n是题目类别总数；D_i,j为用户u_i做第j类题目的题目难度总和；S_i,j为用户u_i做 第j类题目的数量；β为待定系数，通过实验确定最优值；S_i,k为用户u_i做第k类题目的数 量；D_i,k为用户u_i做第k类题目的题目难度总和。

公式2与公式3相比，去掉了平均评分因素，增加了题目难度因素，是DF_TyCo相 对于TyCo在题目推荐应用方面的改进。

204：计算用户相似度；

该步骤利用用户特征向量来计算任意两用户之间的相似度。本发明实施例分别采用了 余弦相似度公式和距离相似度公式，并通过实验对比其效果。相似度计算公式中的两个输 入向量分别是两个用户的特征向量，即：和 其中，v_i,k为用户u_i在第k类题目上的典型度；v_j,k为用户u_j在 第k类题目上的典型度。输入向量确定后，相似度的具体计算过程为本领域技术人员所公 知，本发明实施例对此不做赘述。

205：选择最近邻；

求出了用户之间的相似度之后，为每个用户选取与其最相似的若干用户形成该用户的 “最近邻”。本发明实施例为每个用户选取固定数量的相似用户作为其最近邻。最近邻用 户过多或过少都会影响推荐的效果，本发明实施例中通过多次对比实验选择一个最优值， 本发明实施例对最近邻的个数不做限制。

206：预测用户对题目评分；

目标用户对目标题目的评分根据其最近邻来计算。目标用户的最近邻用户做过的题目， 目标用户也可能会做，并且越相似的用户，其做题情况越有参考价值。本发明实施例认为， 任意用户对其提交并通过的题目评分为1，其余的题目评分为0，然后以最近邻用户和目 标用户之间的相似度为权值，做加权平均，得到的结果便是目标用户对目标题目的预测评 分。

207：选择推荐题目。

此处有两种方法，一种是选择一个阈值，将目标用户评分超过阈值的题目作为推荐结 果，另一种是为每个目标用户推荐固定数量的题目。本发明实施例中，采用为每个目标用 户推荐固定数量的题目为例进行说明。

将实验数据按照时间，划分为测试集和训练集，利用训练集中的数据产生推荐结果， 与测试集中的数据对比，衡量推荐的准确性。

综上所述，本发明实施例通过上述步骤201-步骤207利用题目具有“难度”的特点来 改进传统推荐方法，获得了较好的效果。本发明实施例将来可以应用到学习网站中，帮助 用户选择学习内容，制定个性化的学习方案。

实施例3

下面结合具体的实例、计算公式、附图对实施例1、2中的技术方案进行可行性验证， 详见下文描述：

实验中，让最近邻用户的数目K的值分别为5、10，…，70，观察实验结果，以探究 K值对实验结果的影响；在一定的K值下，改变用户做题难度在描述用户特征时的权重因 子，观察实验结果并计算其准确率。

本发明采用F值(F-measure)和用户准确率(PU)来评价实验结果。为了描述方便， 称“给用户u_x推荐一道题目p_y”为一次推荐。

若产生的推荐总数为recomNum，准确推荐的数目为accuate，测试集中所有用户做题 总数为realSum，则准确度pred和召回率recall计算方法分别如公式(4)、公式(5)所示。

$pred=\frac{accuate}{recomNum}---\left(4\right)$

$recall=\frac{accuate}{realSum}---\left(5\right)$

有了pred和recall就可以计算F值，F值的计算方法如公式(6)所示。

$F=2\times \frac{pred\times recall}{pred+recall}---\left(6\right)$

其中，pred和recall分别从两个方面反映了结果的好坏，F值是二者的综合体现，实 验中，F值越大，结果越好。

用户准确率是指能被准确推荐的目标用户占所有目标用户的百分比。给每个目标用户 固定推荐10道题目，若对于某个目标用户来说，至少有一道题目是推荐准确的，则称该 目标用户被准确推荐了。用户准确率计算公式如公式(7)所示：

$PU=\frac{predUser}{allUser}---\left(7\right)$

其中，predUser为被准确推荐的用户数，allUser为被推荐过的用户总数。

如图2所示，用户特征被描述为在每一类题目上的典型度。引入难度系数，即以用户 所做题目的难度为用户特征的一部分。从图2可以看出，引入难度能够改善实验结果，说 明在推荐中，引入题目难度，是合理的。实验结果表明，随着权重因子从0逐渐增大至1.0， 用户准确率呈现先升后降的趋势，尤其当权重因子在0.85左右，即用户所做题难度占用户 特征的85％、其余因素占15％时效果最好，从而证明在此应用场景下，引入题目难度，能 够改善传统推荐的效果。

TyCo是基于典型度的协同过滤方法，将其引入到推荐系统中，能够改善传统推荐方法 的实验结果。本发明实施例中，在此基础上，引入题目难度，进一步改善了将推荐系统应 用到题目推荐中时的实验结果。

事实上，跟UBCF方法相比，TyCo引入了典型度的概念，改善了传统的协同过滤方 法，而本发明实施例在TyCo的基础上，引入了题目难度，再一次改善了结果。图3和图4 分别展示了在不同的相似度计算公式下，本发明实施例和基于典型度的协同过滤方法 (TyCo)、基于用户的协同过滤方法(UBCF)的比较，从图中能够看出，在K取各个值 的时候，本方法()都能较其他方法取得更好的结果。证明本方法在准确度上要优于另外 两者。

实施例4

一种基于典型度和难度的题目推荐装置，参见图5，该题目推荐装置包括：

计算模块1，用于计算每个目标用户在每一类型题目上的做题情况，包括：题目的数 量、难度以及目标用户在此类型题目上的通过率；

第一选择模块2，用于根据目标用户特征向量，计算任意目标用户特征向量之间的相 似性，并对每个目标用户，选择若干相似度最高的用户作为最近邻；

评分模块3，用于依据最近邻用户的做题情况，预测目标用户对未做题目的评分；

第二选择模块4，用于对目标用户，选择若干评分最高的目标题目作为目标用户的推 荐结果。

其中，参见图6，该题目推荐装置还包括：

预处理模块5，用于排除错误或无效的数据，然后按提交时间从小到大排序；统计数 据涉及的用户与题目，形成一个用户集合和一个题目集合。

本发明实施例通过上述模块实现了利用题目具有“难度”的特点来改进传统推荐方法， 获得了较好的效果。本发明实施例将来可以应用到学习网站中，帮助用户选择学习内容， 制定个性化的学习方案。

本发明实施例对各器件的型号除做特殊说明的以外，其他器件的型号不做限制，只要 能完成上述功能的器件均可。

本领域技术人员可以理解附图只是一个优选实施例的示意图，上述本发明实施例序号 仅仅为了描述，不代表实施例的优劣。

以上所述仅为本发明的较佳实施例，并不用以限制本发明，凡在本发明的精神和原则 之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。