基于概念格的稀疏数据协同过滤校正自然噪声方法

朵 琳, 杨 丙

(昆明理工大学 信息工程与自动化学院, 昆明 650504)

近年来, 推荐系统[1-3]被广泛应用于电子商务网站中. 推荐系统能从大量的信息中获取有用的数据, 帮助用户找到所需的产品或服务. 但目前的推荐系统仍存在许多问题, 如数据稀疏[4-5]、 自然噪声和冷启动[6-7]等. 在推荐系统领域中关于自然噪声的研究目前较少. O’Mahony等[8]提出了先从用户-项目评级矩阵中消除自然噪声, 然后应用协同过滤预测未评级项目级别的方法解决自然噪声, 但评级数据的稀疏性随之增大, 因此, 消除自然噪声的方法不能提供更高的推荐精度； Toledo等[9]对自然噪声进行了检测, 然后应用Pearson相关系数 (Pearson’s correlation coefficient, PCC)[10]重新预测方法校正自然噪声; Year等[11]提出了将模糊模型与重新预测方法相结合, 用于管理自然噪声, 之后又提出了群组推荐系统[12-13], 通过重新预测、 模糊分析、 全局和局部噪声管理的方法解决自然噪声. 上述方法都使用PCC重新预测方法解决自然噪声, 只适用于密集的数据集, 但在稀疏数据集中, PCC所涉及的共同评级较少或不存在, 导致预测值的精度较低[14], 反而会增加噪声问题.

为解决目前PCC重新预测方法在稀疏数据中预测精度较低的问题, 本文提出一种基于概念格的稀疏数据协同过滤(collaborative filtering of sparse data based on concept lattice, CFSD-CL)校正自然噪声的方法, 解决了推荐系统中的自然噪声和数据稀疏性问题, 同时, 由于概念格在数据处理和分析方面的优势, 该方法更直观.

1 预备知识

1.1 推荐系统中的自然噪声

推荐系统数据集中的噪声分为恶意噪声和非恶意噪声(自然噪声), 恶意噪声是由外部代理有意引入, 从而产生有偏差的推荐结果. 自然噪声是由用户不自觉引入的, 也会影响推荐结果. 目前已有很多在推荐系统模型中去除恶意噪声的方法, 但在自然噪声方面的研究较少. 自然噪声在推荐数据集出现的原因可能有两方面[15]： 1) 用户兴趣随着时间改变; 2) 用户引入不精确的评级. 导致第二个原因的因素有： 情绪状态、 环境、 个人条件或社会影响. 由于自然噪声由不同的来源产生, 所以自然噪声的识别较困难.

1.2 协同过滤推荐

协同过滤推荐技术是一种常用的推荐技术, 其通过计算相似度识别用户或项目的邻域[16], 并预测未评级项目的评级. 常用的相似度计算方法为PCC, 采用

(1)

1.3 概念格

形式概念分析(formal concept analysis, FCA)[17-19]是一种数据分析和知识表示的方法. 概念格[20]是FCA中的一个基本结构, 是数据分析与规则提取的有效工具, 广泛应用于各领域.

定义1形式背景定义为一个三元组K=(G,M,I), 也称为二元背景, 其中,G是对象集合,M是属性集合,I是G和M之间的一个关系,I⊆G×M, ∀g∈G及∀m∈M, 若对象g和属性m具有关系I, 则记为gIm.

定义2在形式背景的对象集A⊆G和属性集B⊆M之间定义如下两个映射：

V(A)={m∈M|∀g∈A,gIm},D(B)={g∈G|∀m∈B,gIm}.

若二元组Z=(A,B)满足V(A)=B,D(B)=A, 则二元组Z称为形式概念, 形式概念构成了概念格中的节点, 其中A是形式概念Z的外延, 记为Ext(Z),B是其内涵, 记为Int(Z).

定义3若(X1,B1),(X2,B2)是形式背景K的两个概念, 并满足(X1,B1)≤(X2,B2)⟺X1⊆X2(⟺B1⊇B1), 其中: “≤”为一个偏序关系;K的所有偏序集称为概念格; (X1,B1)是(X2,B2)的子概念; (X2,B2)是(X1,B1)的父概念.

2 方 法

2.1 自然噪声检测

在自然噪声检测中, 首先将用户和项目分为弱类、 平均类、 强类和可变类. 预先设置4个阈值ku,vu,ki,vi用于用户和项目分类. 设U和I分别是用户和项目集合, 通过阈值可将每个用户u评级分组到下列集合Wu,Au,Su中:

1) 弱评级集合Wu={r(u,i)|∀i∈I,r(u,i)≤ku};

2) 平均评级集合Au={r(u,i)|∀i∈I,ku

3) 强评级集合Su={r(u,i)|∀i∈I,r(u,i)≥vu}.

同理, 可将每个项目i评级分组到下列集合Wi,Ai,Si中:

1) 弱评级集合Wi={r(u,i)|∀u∈U,r(u,i)≤ki};

2) 平均评级集合Ai={r(u,i)|∀u∈U,ki

3) 强评级集合Si={r(u,i)|∀u∈U,r(u,i)≥vi}.

本文研究在1～5的评分等级上进行, 将阈值ku和vu、ki和vi均设为2和4, 即1和2评级判为弱评级, 3评级判为平均评级, 4和5评级判为强评级, 用于所有用户和项目的分类. 表1为用户-项目分类, 根据表1的标准, 使用集合Wu,Au,Su或Wi,Ai,Si的基数对每个用户或项目分类. 当用户的弱评级基数大于等于其平均评级和强评级基数之和时, 他的评级在评级量表中就会偏到较低的一端, 则该用户被认为是弱用户.

表1 用户-项目分类

类似地, 将用户和项目分为弱类、 平均类、 强类和可变类. 用户、 项目和评级被分类后, 通过分析类之间存在的矛盾寻找有噪声的评级. 表2定义了用户-项目-评级类之间的关系.

表2 用户-项目-评级类之间的关系

检测过程假设对来自推荐数据集的一个评级r(u,i), 如果用户u的类和项目i的类属于同一类, 则评级r(u,i)必属于同一类评级. 如果不符合该条件, 则评级r(u,i)被标记为自然噪声. 自然噪声检测算法步骤如下.

算法1自然噪声检测.

输入： 含自然噪声的用户-项目评级矩阵;

输出： 自然噪声集合noise;

1)Wu={ },Au={ },Su={ },Wi={ },Ai={ }, noise={ }；

2) for (everyu∈U);

3) for (everyi∈I);

4) if (r(u,i)≤ku);

5) 将r(u,i)加入集合Wu;

6) else if (ki

7) 将r(u,i)加入集合Au;

8) else;

9) 将r(u,i)加入集合Su;

10) if (|Wu|≥|Au|+|Su|);

11)u为弱用户;

12) else if (|Au|≥|Wu|+|Su|);

13)u为平均用户;

14) else if (|Su|≥|Au|+|Wu|);

15)u为强用户;

16) else;

17)u为可变用户;

18) 重复以上循环, 对每个项目i进行分类;

19) for (everyr(u,i));

20) if (u为弱用户,i为弱项目,r(u,i)不为弱评级);

21) 将r(u,i)加入集合noise;

22) if (u为平均用户,i为平均项目,r(u,i)不为平均评级);

23) 将r(u,i)加入集合noise;

24) if (u为强用户,i为强项目,r(u,i)不为强评级);

25) 将r(u,i)加入到集合noise.

2.2 自然噪声校正

图1 用户-项目评级矩阵Fig.1 User-item rating matrix

图2 用户-项目评级形式背景Fig.2 User-item rating context

图3 概念格Fig.3 Concept lattice

图4 外延格Fig.4 Epitaxial lattice

图5 内涵格Fig.5 Connotative lattice

在概念格中, 采用由顶部到底部的搜索方法, 还可以查找用户u的评级项目范围Iu, 其定义如下：

Iu={Int(Z)|u∈Ext(Z), max{|Int(Z)|},Z∈Lc}.

(2)

计算用户u与用户v的相似度. 其中:Iu表示用户u的评级项目集合;Iv表示用户v的评级项目集合; |Iu|和|Iv|表示评级项目的个数;r(u,i)表示用户u对项目i的评级. 由式(2)可见, 本文提出的相似度计算方法只需使用用户的评级项目集合, 避免了用户间共同评级项目的影响.

(3)

算法2CFSD-CL预测.

输入： 用户-项目评级矩阵;

输出： 预测评级值;

2) 基于用户-项目评级矩阵, 构造概念格Lc；

3) for (everyZ∈Lc)；

4) if (i∈Int(Z) and max{|Ext(Z)|});

6) if (u∈Ext(Z) and max{|Int(Z)|});

7)Iu=Int(Z);

9) for (everyZ∈Lc);

10) if (v∈Ext(Z) and max{|Int(Z)|});

11)Iv=Int(Z);

2.3 时间复杂度分析

CFSD-CL校正自然噪声方法的时间复杂度主要为算法1的自然噪声检测和算法2的CFSD-CL预测. 由算法1可知, 双重嵌套循环时间复杂度与用户-项目评级矩阵有关, 用Un表示用户-项目评级矩阵中用户的个数, 用In表示用户-项目评级矩阵中项目的个数, 则双重嵌套循环时间复杂度为O(Un×In). 单个循环时间复杂度与评级的个数有关, 用Rn表示评级的个数, 则单个循环时间复杂度为O(Rn). 于是算法1的时间复杂度为max{O(Un×In),O(Rn)}. 在算法2中, 单个循环时间复杂度与概念格中形式概念的个数有关, 用Zn表示形式概念的个数, 单个循环时间复杂度为O(Zn). 双重嵌套循环主要用于计算相似度, 相似度的计算次数和目标用户可能的最近邻个数有关, 用Vn表示可能的最近邻个数, 则双重嵌套循环的时间复杂度为O(Vn×Zn), 于是算法2的时间复杂度为max{O(Vn×Zn),O(Zn)}.

3 实验设置

为验证本文提出的CFSD-CL校正自然噪声方法的有效性, 使用电影数据集MOVIELENS 100K进行实验.

3.1 数据集

MOVIELENS 100K数据集包含943名用户对1 682部电影的100 000个匿名评分, 分值为1～5. 用户对电影的喜欢程度用分值大小表示, 评分为1表示用户非常不喜欢该部电影, 评分为5表示用户非常喜欢该部电影. 原始数据集中可用评级的密度较大, 由于该模型需在不同高度稀疏的数据集上进行测试, 因此从MOVIELENS数据集中随机抽取300个用户对500个随机电影的评分, 生成了一个新的样本数据集, 生成样本数据集的可用评级数为11 328, 稀疏度约为92%. 随后可用评级被随机更改为零, 以形成稀疏度不同的数据集验证本文算法的性能.

3.2 评价指标

由于需要通过预测精度评价算法的性能, 所以采用平均绝对误差(mean absolute error , MAE)和均方根误差(rooted mean squared error, RMSE)度量算法的预测精度. MAE表示预测用户评级与实际用户评级间的偏差, 可用于度量预测的精度. 通常情形下, MAE越小预测的精度越高, 计算公式为

(4)

其中:n表示预测的所有评分个数;ri表示项目i的实际评分值;pi表示项目i的预测评分值.

均方误差(MSE)的计算方法是将实际评分值和预测评分值之差的平方和除以测试集中的评分集合. RMSE通过取MSE的平方根得到, 其反映了实际值与预测值之间的偏离程度, RMSE越小预测的精度越高, 计算公式为

(5)

4 实验结果及分析

4.1 用户-项目分类

根据算法1对样本数据集的用户和项目进行分类, 结果如图6所示. 由图6可见, 在样本数据集中, 10名用户被划分为弱用户, 14名用户为平均用户, 225名用户为强用户, 有51名用户未分类到任何类中； 同样, 有68个弱项目, 42个平均项目, 296个强项目, 94个项目未被分到任何类中.

4.2 噪声评级修正

采用CFSD-CL方法对样本数据集中的自然噪声进行校正的数量如图7所示. 由图7可见, 在样本数据集中, 11 328个可用的评级中检测出了821个噪声评级, 7.25%的评级是有噪声的. 利用噪声校正算法, 有465个评级从平均校正为强, 306个评级从弱校正为强, 34个评级从弱校正为平均, 6个评级从平均校正为弱, 10个评级从强校正为平均.

图6 样本数据集用户-项目分类Fig.6 Classification of users and items for sample dataset

图7 样本数据集修正评级数量Fig.7 Number of modified ratings for sample dataset

4.3 性能比较

为了验证CFSD-CL校正自然噪声方法的有效性, 将CFSD-CL校正自然噪声方法和现有的PCC重新预测方法在数据集上分别进行实验, 在最近邻和稀疏度的影响下对MAE和RMSE值进行比较.

4.3.1 最近邻的影响 先采用CFSD-CL校正自然噪声方法和PCC重新预测方法对样本数据集中的自然噪声进行检测并校正, 然后对未评级的项目进行预测. 当最近邻数为5,7,9,11,13,15时, 分别对MAE和RMSE值进行比较, 结果分别如图8和图9所示. 由图8和图9可见, 两种方法的MAE和RMSE值受最近邻影响的变化趋势相同, 本文方法的MAE和RMSE值均小于PCC重新预测方法, 因此, 本文提出的噪声修正方法比PCC重新预测方法的性能更好, 预测精度更高.

图8 不同最近邻的MAE比较Fig.8 MAE comparison for different nearest neighbors

图9 不同最近邻的RMSE比较Fig.9 RMAE comparison for different nearest neighbors

4.3.2 稀疏度的影响 为了验证本文方法在稀疏场景下的有效性, 本文将样本数据集中的可用评级随机更改为零, 以形成5个稀疏度不同的数据集, 稀疏度分别为92%,95%,97%,98%,99%. 然后将CFSD-CL校正自然噪声方法和PCC重新预测方法分别在5个稀疏度不同的数据集上进行实验, 最后分别比较不同方法的MAE和RMSE值, 结果分别如图10和图11所示. 由图10和图11可见, 随着稀疏度的增加, 两种方法的MAE和RMSE值不断增加. 本文方法的MAE和RMSE值均小于PCC重新预测方法, 在稀疏度很高的情形下也有较大优势, 因此, 本文提出的自然噪声校正方法优于PCC重新预测方法.

图10 不同稀疏度的MAE比较Fig.10 MAE comparison for different sparsity

图11 不同稀疏度的RMSE比较Fig.11 RMSE comparison for different sparsity

综上所述, 本文提出了一种CFSD-CL校正自然噪声的方法, 解决了推荐系统中存在的自然噪声和数据稀疏的问题. 本文加入了概念格的思想, 在预测评分值时能方便、 直观地查找目标用户的最近邻范围和用户偏好.