0 引言

个性化推荐系统是一种基于大规模数据挖掘的智能平台，可以为用户提供完整的个性化决策支持和信息服务。其主流算法包括：协同过滤推荐、基于内容推荐、基于关联规则推荐、基于效用推荐、基于知识推荐、组合推荐等^[1]。

协同过滤推荐算法是个性化推荐系统中应用最早和最为成功的算法之一。协同过滤推荐算法主要有两类：基于用户的协同过滤推荐算法和基于项目的协同过滤推荐算法。协同过滤推荐算法主要通过获取用户的偏好信息，计算用户间 (或项目间) 的相似性和根据相似度预测目标用户对目标项目的评分来实现^[2]。

协同过滤推荐算法的关键步骤是计算用户间 (或项目间) 的相似性。国内外学者围绕协同过滤算法中相似性度量方面开展了一系列的研究。如Ahn^[3]提出修正余弦相似性度量方法 (Ajusted Cosine Correlation, ACC)，部分改进了余弦相似性的缺陷; Shardanand等^[4]考虑到评分的正负性，提出了约束皮尔逊相关系数 (Constrained Pearson Correlation Coefficient, CPCC); Herlocker等^[5]提出了权重皮尔逊相关系数 (Weighted Pearson Correlation Coefficient, WPCC)，将共同评分项目数量考虑在内; Jamali等^[6]提出了将传统的皮尔逊相关系数与Sigmoid函数相结合形成一种基于Sigmoid函数的相似性度量方法 (Sigmoid-based Pearson Correlation Coefficient, SPCC) 能减弱共同评分项目少的用户 (或项目) 之间的相似性; Bobadilla等^[7]提出了将均值平方差异函数 (Mean Square Difference, MSD) 与Jaccard系数结合形成基于Jaccard系数的均方差异系数 (Jaccard-based Mean Square Difference, JMSD)。上述方法遇到冷启动问题 (即新用户和新项目的评分信息少的情况) 时，其准确性受到影响。

本文仅围绕协同过滤推荐算法中项目相似性度量进行分析与改进，提出一种新的项目相似性度量方法，该度量方法能够解决冷启动问题。该项目相似性度量方法由评分相似性和结构相似性两部分构成，其中，评分相似性部分充分考虑两个项目评分之间的评分差 (用Proximity记，详见1.3节)、项目评分与评分中值之差 (用Significance记，详见1.3节)，以及项目评分与其他评分平均值之差 (用Singularity记，详见1.3节)；结构相似性部分定义共同评分项目占所有项目比重并惩罚活跃用户的IIF (Inverse Item Frequency) 系数，形成一种新的项目相似性度量方法 (IIF-based Proximity-Significance-Singularity, IPSS)。将IPSS度量方法融入到基于项目的协同过滤推荐算法，提出基于IPSS-ITEM的协同过滤推荐算法 (IPSS-based Item Collaborative Filtering, ICF_IPSS)。为了验证该协同过滤推荐算法的有效性，在Movie Lens和Jester等2个数据集测试，该算法在预测准确率和分类准确率方面面对冷启动情况时均表现出较好效果。

1 基于IPSS-ITEM的协同过滤推荐算法 1.1 基于项目的协同过滤推荐算法

基于项目的协同过滤推荐算法是基于此类假设：若大多数喜欢项目i的用户也喜欢项目j，则i和j就有较高相似度。算法步骤^[8]如下：

步骤1   目标项目最近邻搜寻。在计算项目之间的相似性基础上，根据相似性由高到低找出目标项目i的前k个最近项目构成最近邻集合。

步骤2   产生推荐。根据目标用户对目标项目的最近邻项目的评分及其之间相似性加权计算预测评分 (式 (1))，以此构建Top-N推荐列表。

假设项目i有k个最近项目，S是最近邻集合，融合项目间相似性sim(i, j) 计算目标用户u对目标项目i的预测评分：

$ {P_{ui}} = \frac{{\sum\limits_{j \in S} {sim\left( {i, j} \right) \times {R_{uj}}} }}{{\sum\limits_{j \in S} {\left| {sim\left( {i, j} \right)} \right|} }} $

(1)

其中： sim(i, j) 代表项目i和最近项目j的相似度，R_uj代表用户 u对项目j的评分。

1.2 传统项目相似性度量方法分析

用于度量项目间相似性的方法有很多，这些方法多是从余弦相关性 (Cosine Correlation, CC) 和皮尔逊相关性 (Pearson Correlation Coefficient, PCC) 方法变形而来，本文以这两种最传统的相似性度量方法为例，分析其缺点。

1) 余弦相关性 (CC)。

将n个用户对项目i和项目j的评分视为n维向量，项目i和项目j的相似性即为相应两个n维向量的夹角余弦，定义为:

$ sim\left( {i, j} \right) = \frac{{\sum\limits_{u \in {U_{ij}}} {{R_{ui}}{R_{uj}}} }}{{\sqrt {\sum\limits_{u \in {U_{ij}}} {R_{ui}^2} } \sqrt {\sum\limits_{u \in {U_{ij}}} {R_{uj}^2} } }} $

(2)

其中R_ui 代表用户u对项目i的评分。

2) 皮尔逊相关性 (PCC)。

该方法通过计算两个项目之间的皮尔逊相关系数来确定项目间相似性，定义为:

$ sim\left( {i, j} \right) = \frac{{\sum\limits_{u \in {U_{ij}}} {\left( {{R_{ui}}-{{\bar R}_i}} \right)\left( {{R_{uj}}-{{\bar R}_j}} \right)} }}{{\sqrt {\sum\limits_{u \in {U_{ij}}} {{{\left( {{R_{ui}}-{{\bar R}_i}} \right)}^2}} \sqrt {\sum\limits_{u \in {U_{ij}}} {{{\left( {{R_{uj}} - {{\bar R}_j}} \right)}^2}} } } }} $

(3)

其中：$ {\overline R _i}$和${\overline R _j} $分别表示共同评分过项目i与项目j的用户对项目i与项目j的平均评分^[10]。

在实际推荐系统中，会出现冷启动情况，即共同评分过项目i与项目j的用户量很少甚至没有，因此，传统项目间相似性度量方法存在一定的弊端。如果共同评分过项目i与项目j的用户数量为1，不管该用户对项目 i与项目j的评分值为多少，用式 (2) 计算的结果总为1，扩大了项目间的相似性 (即本来相似性较低的两个项目的相似性度量结果较高)。而对于式 (3)，分子分母总为0，公式没有意义，不能计算项目间相似性。传统的相似性度量方法在计算项目相关性时都会存在一定的误差，计算结果可能会扩大或缩小项目间相关性 (即本来相似性较高的两个项目的相似性度量结果较低)。

1.3 IPSS的项目相似性度量方法

基于项目的协同过滤推荐算法的关键步骤是计算项目间相似性，以此搜索目标项目的k 个最近项目。本文提出了一种新的项目相似性度量方法 (IPSS)，能够有效解决其他协同过滤推荐算法遇到冷启动情况效果不佳的问题。

IPSS相似性度量方法由评分相似性和结构相似性两部分构成，其中，评分相似性部分充分考虑两个项目评分之间的评分差、项目评分与评分中值之差，以及项目评分与其他评分平均值之差；结构相似性部分定义共同评分项目占所有项目比重并惩罚活跃用户的IIF系数，形成一种新的项目相似性度量方法。

在评分相似性部分，融合了两个项目评分之间的评分差 (Proximity)、项目评分与评分中值之差 (Singularity)，以及项目评分与其他评分平均值之差 (Significance) 等3个因素，项目i和j间的评分相似性PSS(i, j) 定义为：

$ PSS\left( {i, j} \right) = \sum\limits_{u \in {U_{ij}}} {PS{S_u}} \left( {{R_{ui}}, {R_{uj}}} \right) $

(4)

其中: U_ij为所有评价过项目i和j用户的集合。PSS_u(R_ui, R_uj) 为用户u对项目i 和j间的评分相似性。

用户u对项目i和j 间的评分相似性PSS_u(R_ui, R_uj) 定义为:

$ \begin{array}{l} PS{S_u}\left( {{R_{ui}}, {R_{uj}}} \right) = {\mathop{\rm \mathit{Proximity}}\nolimits} \left( {{R_{ui}}, {R_{uj}}} \right) \cdot \\ \;\;Significance\left( {{R_{ui}}, {R_{uj}}} \right) \cdot Singularity\left( {{R_{ui}}, {R_{uj}}} \right) \end{array} $

(5)

其中: Proximity(R_ui, R_uj) 反映两个项目评分之间的评分差，其定义为:

$ {\rm\mathit{{Proximity}}}\left( {{R_{ui}}, {R_{uj}}} \right) = 1-\frac{1}{{1 + \exp \left( {-\left| {{R_{ui}}-{R_{uj}}} \right|} \right)}} $

(6)

从式 (6) 和Sigmoid函数的性质可知，Proximity的值在 (0, 1/2]变化，若评分差|R_ui－R_uj|越大，则两个项目之间的Proximity值越小，进而两个项目间相似性越小。

Significance(R_ui, R_uj) 反映项目评分与评分中值之差，其定义为:

$ \begin{array}{l} Significance\left( {{R_{ui}}, {R_{uj}}} \right) = \\ \;\;\;\;\;\;\;\frac{1}{{1 + \exp \left( {-\left| {{R_{ui}}-{R_{{\rm{med}}}}} \right| \cdot \left| {{R_{uj}}-{R_{{\rm{med}}}}} \right|} \right)}} \end{array} $

(7)

其中: R_med代表评分范围的评分中值，若评分范围为{1, 2, 3, 4, 5}，则R_med=3。

从式 (7) 可以看出，两个评分距离评分中值越远，则该评分越具有意义。Significance的值在|R_ui－R_med|·|R_uj－R_med|越大，则Significance值越大，进而计算评分相似性时更有意义。

Singularity(R_ui, R_uj) 反映用户u对项目i和j的评分平均值与用户u对所有项目评分平均值之差，其定义为:

$ \begin{array}{l} Singularity\left( {{R_{ui}}, {R_{uj}}} \right) = \\ \;\;\;\;\;1\;-\;\frac{1}{{1 + \exp \left( {-\left| {\left( {{R_{ui}}{\rm{ + }}{R_{uj}}} \right)/2-{{\bar R}_u}} \right|} \right)}} \end{array} $

(8)

其中${\overline R _u} $表示用户u对所有项目评分的平均值。

从式 (8) 可以看出，Singularity值在 (0, 1/2]变化，若$ \left| {\left( {{R_{ui}} + {R_{uj}}} \right)/2-{{\bar R}_u}} \right|$的值越大，则Singularity值越小，进而两个项目间相似性越小。

在考虑评分相似性基础上，结构相似性部分定义了共同评分项目占所有项目比重并惩罚活跃用户的IIF系数，IIF系数是在修正IUF (Inverse User Frequence) 系数 (是由Breese提出^[11]) 基础上形成。一方面，衡量共同评分的比重；另一方面，惩罚活跃用户的影响。在计算项目间相似性时，活跃用户对项目间相似性计算的贡献应该小于非活跃用户，通过1/[ln (1+|N_u(i, j|)]惩罚了项目i和项目j共同评分用户集合中活跃用户对项目间相似性的影响。

IIF系数定义为：

$ IIF\left( {i, j} \right) = \frac{{\sum\limits_{u \in {U_{ij}}} {\frac{1}{{\ln \left( {1 + \left| {{N_u}\left( {i, j} \right)} \right|} \right)}}} }}{{\sqrt {\left| {N\left( i \right)} \right| \cdot \left| {N\left( j \right)} \right|} }} $

(9)

其中: N_u(i, j) 代表既评价过项目i又评价过项目j的用户数，N(i) 和N(j) 分别代表评价过项目i和项目j的用户数。

IPSS相似性度量函数是由评分相似性和结构相似性组成，由式 (4) 和式 (9) 共同定义IPSS相似性度量函数为：

$ IPSS\left( {i, j} \right) = PSS\left( {i, j} \right) \cdot IIF\left( {i, j} \right) $

(10)

1.4 基于IPSS-ITEM的协同过滤推荐算法

基于IPSS-ITEM的协同过滤推荐算法步骤如下：

输入  用户-项目-评分数据集；

输出  预测评分矩阵，推荐列表。

步骤1   将用户-项目-评分数据集转换为用户-项目评分矩阵R_m×n，其中m 为用户数量， n为项目数量；

步骤2   在评分矩阵R上计算项目i和项目j的评分相似性PSS(i, j)(见式 (4))，结构相似性IIF(i, j)(见式 (9))，将PSS(i, j) 和IIF(i, j) 结合形成项目i和项目j的相似性 (见式 (10))，以此产生项目相似性矩阵Sim_Matrix_n×n；

步骤3   对于目标项目，根据相似性大小选取相似性最高的前k个项目作为最近邻集，用式 (1) 计算目标用户对目标项目的预测评分，并得出推荐列表。

该算法计算项目间相似性时，以Sigmoid函数作为基础进行项目间相似性的计算，能够有效解决冷启动情况下，传统的相似性度量方法在计算项目间相似性时计算结果可能会扩大 (即本来相似性较低的两个项目的相似性度量结果较高) 或缩小 (即本来相似性较高的两个项目的相似性度量结果较低) 项目间相似性的问题。该算法需要计算所有n 个项目间的相似度，每对项目相似度的计算又需要在维度为用户数m的向量之间计算，所以时间复杂度为O(m×n)，而m和n的数量级相同，所以时间复杂度为O(n²)。

2 实验结果与分析

为了评估IPSS相似性度量方法对协同过滤推荐算法的影响，本文在Movie Lens和Jester数据集上比较基于IPSS-ITEM的协同过滤推荐算法 (ICF_IPSS) 和基于其他相似性度量函数的协同过滤推荐算法 (如基于余弦相关性的项目协同过滤算法 (Cosine Correlation-based Item Collaborative Filtering, ICF_CC)^[9]、基于皮尔逊相关性的项目协同过滤算法 (Pearson Correlation Coefficient-based Item Collaborative Filtering, ICF_PCC)^[10]、基于修正余弦相关性的项目协同过滤算法 (Adjusted Cosine Correlation-based Item Collaborative Filtering, ICF_ACC)^[3]、基于约束皮尔逊相关性的项目协同过滤算法 (Constrained Pearson Correlation-based Item Collaborative Filtering, ICF_CPCC)^[4]、基于加权皮尔逊相关性的项目协同过滤算法 (Weighted Pearson Correlation-based Item Collaborative Filtering, ICF_WPCC)^[5]、基于Sigmoid函数的相关性的项目协同过滤算法 (Sigmoid-based Pearson Correlation-based Item Collaborative Filtering, ICF_SPCC)^[6]、基于Jaccard系数的均方差异系数的项目协同过滤算法 (Jaccard-based Mean Square Difference-based Item Collaborative Filtering, ICF_JMSD)^[7]) 的预测准确率和分类准确率，以此验证IPSS相似性度量方法的有效性。

2.1 实验数据集和性能评价指标

本文比较ICF_IPSS与其他协同过滤推荐算法在Movie Lens (http://www.grouplens.org) 和Jester (http://eigentaste.berkeley.edu/dataset/) 两个数据集进行测试，以此评估ICF_IPSS的性能。Movie Lens和Jester数据集的概述见表 1。

一般地，评估协同过滤推荐算法的性能，主要采用预测准确率和分类准确率两个指标。预测准确率分为平均绝对偏差 (Mean Absolute Error, MAE) 和均方根误差 (Root Mean Square Error, RMSE)，MAE和RMSE的值越小，预测的准确率越高。通常情况下网站会为用户返回一个推荐列表，叫作Top-N推荐^[12]。Top-N推荐的分类准确率经常用两个常用的指标衡量：准确率和召回率^[13]，见表 2。

2.2 实验结果与讨论 2.2.1 预测准确率

预测准确率反映算法对于未评分项目的预测结果的准确程度，最近邻居数量的不同会导致预测准确率存在一定差异，将最近邻数量K 作为自变量，分析基于不同相似性度量方法的协同过滤算法的推荐效果。实验结果显示，与传统的协同过滤推荐算法比较，ICF_IPSS可以显著提高推荐的有效性。

图 1给出了在Movie Lens数据集下，不同邻居数情况下，基于各种相似性度量方法 (图例中各算法名称中的“ICF_”省略) 的协同过滤的推荐准确度比较。

在图 1中，MAE和RMSE的值随着K的增多而减少。可以看出，ICF_IPSS的MAE值比其他基于经典相似性度量方法的协同过滤推荐的MAE值低，在K=10时，ICF_IPSS的MAE值分别比ICF_CC，ICF_PCC，ICF_ACC，ICF_CPCC，ICF_WPCC，ICF_SPCC，ICF_JMSD低10.83%，14.24%，7.20%，1.39%，1.94%，15.52%，3.06%。ICF_IPSS的RMSE值比大多数基于经典相似性度量方法的协同过滤推荐的RMSE值低，只有当最近邻个数大于等于10以后，ICF_IPSS的RMSE值略大于ICF_CPCC的RMSE值 (K=10时，RMSE_IPSS=1.098 5, RMSE_CPCC=1.096 5)。在K=10时，ICF_IPSS的RMSE值分别比ICF_CC，ICF_PCC，ICF_ACC，ICF_CPCC，ICF_WPCC，ICF_SPCC，ICF_JMSD低7.37%，9.42%，4.90%，-0.18%，1.12%，10.51%，1.20%。

图 2给出了在Jester数据集下预测准确率的实验效果。可以看出在邻居数量从5到50的情况下，基于传统相似性度量的推荐算法的MAE≥3.628 7，RMSE≥4.575 8，相比之下，ICF_IPSS的MAE和RMSE值 (MAE≥3.483 9，RMSE≥4.497 4) 明显小于传统方法。在K=10时，ICF_IPSS的MAE值分别比ICF_CC，ICF_PCC，ICF_ACC，ICF_CPCC，ICF_WPCC，ICF_SPCC，ICF_JMSD低11.01%，5.26%，6.97%，10.93%，5.26%，5.26%，17.07%。在K=10时，ICF_IPSS的RMSE值分别比ICF_CC，ICF_PCC，ICF_ACC，ICF_CPCC，ICF_WPCC，ICF_SPCC，ICF_JMSD低9.42%，3.76%，4.00%，9.33%，3.76%，3.76%，13.80%。

2.2.2 分类准确率

在Top-N推荐中，不同的推荐数量会有不同的推荐效果。将推荐项目数量N作为自变量，分析基于不同相似性度量方法的协同过滤算法的推荐效果。

图 3显示了Movie Lens数据集下不同推荐项目数量对应的准确率和召回率。从图 3中可以看出，ICF_IPSS可以得到最好的推荐分类准确率，而且与其他方法相比效果非常明显; 此外，可以看出，准确率将会随着推荐数量的增加而下降。ICF_WPCC和ICF_JMSD是推荐效果最好的两种传统方法，然而，与ICF_JMSD相比，当N=10时，ICF_IPSS的准确率提升67.79%;召回率会随着推荐数量的增加而上升，与ICF_JMSD相比，当N=10时，ICF_IPSS的召回率提升67.86%。

图 4显示了在Jester数据集下不同推荐项目数量对应的准确率和召回率，同样地，基于ICF_IPSS能够得到最好的推荐效果。从图中可以看出，ICF_ACC是ICF_IPSS的有力竞争者，然而，与ICF_ACC相比，当N>=10时，ICF_IPSS的准确率提升7.46%，召回率提升7.45%。可以看出，ICF_IPSS可以比其他经典方法得到更好的推荐效果。

3 结语

协同过滤推荐算法是个性化推荐系统中应用最广泛、效果最好的算法之一，但传统协同过滤推荐算法遇到冷启动情况效果不佳。有效地改进与修正项目间相似性度量方法，能够有效解决冷启动情况下项目协同过滤算法的效果不佳问题。本文提出一种新的项目相似性度量方法。该项目相似性度量方法由评分相似性和结构相似性两部分构成，其中，评分相似性部分充分考虑两个项目评分之间的评分差、项目评分与评分中值之差，以及项目评分与其他评分平均值之差；结构相似性部分定义了评分项目占所有项目比重并惩罚活跃用户的IIF系数，形成一种新的项目相似性度量方法——IPSS度量方法。将IPSS度量方融合在项目协同过滤推荐算法，提出基于IPSS的项目协同过滤算法 (ICF_IPSS)，其在冷启动情况下具有较好的表现。在Movie Lens和Jester数据集的测试实验结果表明基于IPSS的项目协同过滤算法在预测准确率和分类准确率方面均优于基于其他相似性度量的项目协同过滤算法 (如ICF_CC、ICF_PCC、ICF_ACC、ICF_CPCC、ICF_WPCC、ICF_SPCC、ICF_JMSD)。算法的时间复杂度为O(n²)。如何有效提高算法复杂度将是今后研究的重点。