工程科学与技术   2018, Vol. 50 Issue (5): 189-195

1. 安徽大学 计算机科学与技术学院，安徽 合肥 230601;
2. 计算智能与信号处理教育部重点实验室（安徽大学），安徽 合肥 230039

Collaborative Filtering Algorithm Based on Positive Correlation and Negative Correlation Nearest Neighbors
XU Yi1,2, TANG Yimin1, WANG Ran1
1. School of Computer Sci. and Technol., Anhui Univ., Hefei 230601, China;
2. Key Lab. of Intelligent Computing & Signal Processing(Anhui Univ.), Ministry of Education, Hefei 230039, China
Abstract: Collaborative filtering algorithm is one of the most widely and successfully used recommendation algorithm. Traditional collaborative filtering algorithm only considers the positive correlation nearest neighbors while ignore the influence of negative correlation nearest neighbors when predicting item rating, which has caused problems like low accuracy and low diversity. In order to resolve these problems, based on positive correlation and negative correlation neighbors a collaborative filtering algorithm is proposed. Firstly, the algorithm computes the similarities and Coefficient of Variation between users and sorts the neighbors according to the similarities which were modified by the Coefficient of Variation. Secondly, the positive nearest neighbors and the negative nearest neighbors are selected based on dynamic weight value α and threshold value β, then item ratings are predicted based on the positive nearest neighbors and the negative nearest neighbors respectively. Finally, the last prediction result is acquired by combining predicting ratings based on the positive nearest neighbors and the negative nearest neighbors with weight. The experiments are tested on the MovieLens with three metrics, and the result show that this approach is achieved great improvement of the accuracy and diversity of recommendation effectively.
Key words: collaborative filtering    positive correlation nearest neighbors    negative correlation nearest neighbors

1 传统的协同过滤算法 1.1 构建评分矩阵

1.2 相似度计算

 $sim(i,j) = \frac{{\displaystyle\sum\limits_{p \in {P_{ij}}} {({r_{ip}} - {\overline {r}_i} )({r_{jp}} - {\overline {r}_{j}} )} }}{{\sqrt {\displaystyle\sum\limits_{p \in {P_{ij}}} {{{({r_{ip}} - {\overline {r}_i} )}^2}} } \sqrt {\displaystyle\sum\limits_{p \in {P_{ij}}} {{{({r_{jp}} - {\overline {r}_j} )}^2}} } }}$ (1)

 $sim(i,j) = \frac{{\displaystyle\sum\limits_{p \in {P_{ij}}} {({r_{ip}} - {\overline {r}_i} )({r_{jp}} - {\overline {r}_j} )} }}{{\sqrt {\displaystyle\sum\limits_{p \in {P_i}} {{{({r_{ip}} - {\overline {r}_i} )}^2}} } \sqrt {\displaystyle\sum\limits_{p \in {P_j}} {{{({r_{jp}} - {\overline {r}_j} )}^2}} } }}$ (2)

1.3 评分预测

 $pred(i,p) = {\overline {r}_i} + \frac{{\displaystyle\sum\limits_{j \in N} {sim(i,j) \cdot ({r_{jp}} - {\overline r}_j )} }}{{\displaystyle\sum\limits_{j \in N} {sim(i,j)} }}$ (3)

2 基于正相关和负相关最近邻居的协同过滤算法 2.1 相似度计算

 $C{V_i} = \frac{{\sqrt {\displaystyle\frac{1}{{\left| {{p_i}} \right|}}{{\displaystyle\sum\limits_{p \in {P_i}} {({r_{ip}} - {\overline {r}_i} )} }^2}} }}{{\overline r_i} }$ (4)

 $\lambda (i,j) = 1 - \left| {C{V_i} - C{V_j}} \right|$ (5)

 $simCV(i,j) = \lambda (i,j) \cdot sim(i,j)$ (6)

 图1 用户相似度计算流程 Fig. 1 User similarity calculation flow chart

2.2 邻居选取

Step 1 根据用户–项目评分矩阵 ${ R}$ 计算出目标用户 $a$ 与其他用户 $x$ 的相似度 $simCV(a,x)$

Step 2 将Step 1中 $simCV(a,x) \ge 0$ 的邻居放入正相关邻居列表 $P$ 中， $simCV(a,x) < 0$ 的邻居放入负相关邻居列表 $N$ 中；对 $P$ 中的元素按相似度从大到小排序，对 $N$ 中的元素按相似度从小到大排序。

Step 3 对于给定需要选取的正相关最近邻居个数 $s$ ，取 $P$ 列表中的前 $s$ 个正相关邻居加入正相关最近邻居 $Pos$ 列表中；同时遍历列表 $N$ 中的负相关邻居，若目标用户的相似度绝对值大于等于给定的 $\beta$ 参数且 $Neg$ 列表个数小于等于 $s$ ，则加入负相关最近邻居 $Neg$ 列表中。

Step 4 输出 $Pos$ 列表和 $Neg$ 列表。

 图2 基于正相关最近邻居和负相关最近邻居的邻居选取算法流程 Fig. 2 Positive correlation and negative correlation nearest neighbors selection flow chart

2.3 预测评分

 $pre{d_{{Pos}}}(i,p) = {\overline {r}_i} + \frac{{\displaystyle\sum\limits_{j \in Pos} {simCV(i,j) \cdot ({r_{jp}} - {\overline {r}_j} )} }}{{\displaystyle\sum\limits_{j \in Pos} {simCV(i,j)} }}$ (7)

 $pre{d_{Neg}}(i,p) = {\overline {r}_i} - \frac{{\displaystyle\sum\limits_{j \in Neg} {simCV(i,j) \cdot ({r_{jp}} - {\overline {r}_j} )} }}{{\displaystyle\sum\limits_{j \in Neg} {simCV(i,j)} }}$ (8)

 $pred(i,p) = \alpha \cdot pre{d_{Pos}}(i,p) + (1 - \alpha ) \cdot pre{d_{Neg}}(i,p)$ (9)

 $\alpha = \frac{{\left| {Pos} \right|}}{{\left| {Pos} \right| + \left| {Neg} \right|}}$ (10)

 图3 评分预测流程 Fig. 3 Ratings prediction flow chart

3 实验及结果分析

3.1 数据集

3.2 评价标准

$MAE$ 的定义公式：

 ${MAE} = \frac{{\displaystyle\sum\limits_{p \in {T_i}} {\left| {{R_{i,p}} - {P_{i,p}}} \right|} }}{{\left| {{T_i}} \right|}}$ (11)

$RMSE$ 的定义公式：

 ${RMSE} = \sqrt {\frac{{\displaystyle\sum\limits_{p \in {T_i}} {{{({R_{i,p}} - {P_{i,p}})}^2}} }}{{\left| {{T_i}} \right|}}}$ (12)

 ${Diversification = }\frac{{\displaystyle2\sum\limits_{i \ne j} {(1 - \frac{{\left| {{L_i} \cap {L_j}} \right|}}{{\left| {{L_i}} \right|}})} }}{{n(n - 1)}}$ (13)

3.3 阈值 $\beta$ 取值及实验对比

 图4 基于不同阈值β的MAE实验结果 Fig. 4 MAE with different β

$MAE$ 值、 $RMSE$ 值的对比实验结果分别如图56所示。

 图5 MAE对比结果 Fig. 5 Comparison results of MAE

 图6 RMSE对比结果 Fig. 6 Comparison results of RMSE

 图7 多样性对比结果 Fig. 7 Comparison of Diversification

4 结　论

 [1] Meng Xiangwu,Liu Shudong,Zhang Yujie,et al. Research on social recommender system[J]. Journal of Software, 2015, 26(6): 1356-1372. [孟祥武,刘树栋,张玉洁,等. 社会化推荐系统研究[J]. 软件学报, 2015, 26(6): 1356-1372.] [2] Zhang Jia,Lin Yaojin,Lin Menglei,et al. An effective collaborative filtering algorithm based on user preference clustering[J]. Applied Intelligence, 2016, 45(2): 230-240. DOI:10.1007/s10489-015-0756-9 [3] Wu Xiaokun,Cheng Bo,Chen Junliang. Collaborative filtering service recommendation based on a novel similarity computation method[J]. IEEE Transactions on Services Computing, 2017, 10(3): 352-365. DOI:10.1109/TSC.2015.2479228 [4] Meng Xiangwu,Hu Xun,Wang Licai,et al. Mobile recommender systems and their applications[J]. Journal of Software, 2013, 24(1): 91-108. [孟祥武,胡勋,王立才,等. 移动推荐系统及其应用[J]. 软件学报, 2013, 24(1): 91-108.] [5] Wei Jian,He Jianhua,Chen Kai,et al. Collaborative filtering and deep learning based recommendation system for cold start items[J]. Expert Systems with Applications, 2017, 69: 29-39. DOI:10.1016/j.eswa.2016.09.040 [6] Bok K,Lim J,Yang H,et al. Social group recommendation based on dynamic profiles and collaborative filtering[J]. Neurocomputing, 2016, 209(C): 3-13. [7] Li Hongtao,He Keqing,Wang Jian,et al. A friends recommendation algorithm based on formal concept analysis and random walk in social network[J]. Journal of Sichuan University(Engineering Science Edition), 2015, 47(6): 131-138. [李宏涛,何克清,王健,等. 基于概念格和随机游走的社交网朋友推荐算法[J]. 四川大学学报(工程科学版), 2015, 47(6): 131-138.] [8] Gasmi I,Seridi-Bouchelaghem H,Hocine L,et al. Collaborative filtering recommendation based on dynamic changes of user interest[J]. Intelligent Decision Technologies, 2015, 9(3): 271-281. DOI:10.3233/IDT-140221 [9] Su Jahwung,Chang Weiyi,Tseng V S. Effective social content-based collaborative filtering for music recommendation[J]. Intelligent Data Analysis, 2017, 21: S195-S216. DOI:10.3233/IDA-170878 [10] Zhang Yuchuan,Liu Yuzhao.A collaborative filtering algorithm based on time period partition[C]//Third International Symposium on Intelligent Information Technology and Security Informatics.New York:IEEE,2010:777–780. [11] Huang Chuangguang,Yin Jian,Wang Jing,et al. Uncertain neighbors’collaborative filtering recommendation algorithm[J]. Chinese Journal of Computers, 2010, 33(8): 1369-1377. [黄创光,印鉴,汪静,等. 不确定近邻的协同过滤推荐算法[J]. 计算机学报, 2010, 33(8): 1369-1377.] [12] He Liang,Wu Faqing.A time-context-based collaborative filtering algorithm[C]//IEEE International Conference on Granular Computing.New York:IEEE,2009:209–213. [13] Jiang Bo,Zhang Xiaoxiao,Pan Weifeng,et al.BIGSIR:A bipartite graph based service recommendation method[C]//Services.New York:IEEE,2013:363–369. [14] Lien D T,Phuong N D.Collaborative filtering with a graph-based similarity measure[C]//International Conference on Computing,Management and Telecommunications.New York:IEEE,2014:251–256. [15] Liu Qi,Chen Enhong. Collaborative filtering through combining bipartite graph projection and ranking[J]. Journal of Chinese Computer Systems, 2010, 31(5): 835-839. [刘淇,陈恩红. 结合二部图投影与排序的协同过滤[J]. 小型微型计算机系统, 2010, 31(5): 835-839.] [16] Wu Lei,Fang Qing,Jin Zhou. Improved personalized recommendation based on causal association rule and collaborative filtering[J]. International Journal of Distance Education Technologies, 2016, 14(3): 21-33. DOI:10.4018/IJDET [17] Patra B K,Launonen R,Ollikainen V,et al. A new similarity measure using Bhattacharyya coefficient for collaborative filtering in sparse data[J]. Knowledge-Based Systems, 2015, 82(C): 163-177. [18] Yang Chong,Yu Xiaohui,Liu Yang,et al. Collaborative filtering with weighted opinion aspects[J]. Neurocomputing, 2016, 210(C): 185-196. [19] Liu Qi,Chen Enhong,Xiong Hui,et al. Enhancing collaborative filtering by user interest expansion via personalized ranking[J]. IEEE Transactions on Systems Man & Cybernetics Part B Cybernetics A Publication of the IEEE Systems Man & Cybernetics Society, 2012, 42(1): 218-233. [20] Schafer J B,Dan F,Herlocker J,et al. Collaborative filtering recommender systems[J]. Acm Transactions on Information Systems, 2004, 22(1): 5-53. DOI:10.1145/963770 [21] Bedeian A G,Mossholder K W. On the use of the coefficient of variation as a measure of diversity[J]. Organizational Research Methods, 2000, 3(3): 285-297. DOI:10.1177/109442810033005 [22] Chen Hao,Li Zhongkun,Hu Wei. An improved collaborative recommendation algorithm based on optimized user similarity[J]. Journal of Supercomputing, 2016, 72(7): 2565-2578. DOI:10.1007/s11227-015-1518-5 [23] Xie Feng,Chen Zhen,Shang Jiaxing,et al.Item similarity learning methods for collaborative filtering recommender systems[C]//IEEE,International Conference on Advanced Information Networking and Applications.New York:IEEE,2015:896–903. [24] Shang Mingsheng,Zhang Zike,Zhou Tao,et al. Collaborative filtering with diffusion-based similarity on tripartite graphs[J]. Physica A Statistical Mechanics & Its Applications, 2009, 389(6): 1259-1264.