﻿ 基于用户聚类与项目划分的优化推荐算法
 计算机系统应用  2019, Vol. 28 Issue (6): 159-164 PDF

Optimal Recommendation Algorithm Based on User Clustering and Project Partition
SHEN Jin-Xiang, BAO Mei-Ying
College of Computer and Network Engineering, Shanxi Datong University, Datong 037009, China
Foundation item: National Natural Science Foundation of China (11871314); Young Science and Technology Fund of Shanxi Province (2015021101); Scientific Research Fund of Shanxi Datong University (2017K7)
Abstract: The traditional collaborative filtering recommendation algorithm does not fully consider the impact of user attributes and item classification on similarity calculation, which results in data sparsity and low recommendation accuracy. This study proposes a collaborative filtering recommendation algorithm based on user attribute clustering and item partitioning. The algorithm fully considers the similarity calculation which has an important impact on recommendation accuracy. Firstly, users are clustered by user identity attributes using clustering algorithm, and then the items are classified. In the similarity calculation, category similarity is added. Considering the number of users scored jointly, comprehensive similarity is calculated by weighted coefficient. Finally, combined with average similarity, the nearest neighbor is synthesized by threshold method. The experimental results show that the proposed algorithm can effectively improve the recommendation accuracy and provide more accurate items for users.
Key words: recommender system     collaborative filtering     clustering algorithm     similarity calculation

1 传统协同过滤推荐算法原理

(1) 构建用户-项目评分矩阵. 可由m×n的评分矩阵表示, mn分别表示用户和项目的值, 任一用户i对任一项目j的评分用rij表示. 当然, 实际的评分矩阵是极稀疏的.

(2) 最近邻的选取. 此步是协同过滤算法的核心, 通过计算项目间或用户间的相似度, 选取与目标用户最相似的最近邻集合为目标用户的最近邻. 余弦相似度及修正的余弦相似度和Pearson相关相似度是常用的计算方法. 余弦相似度计算如式(1)所示.

 $Sim\left( {i,j} \right) = \cos \left( {i,j} \right) = \frac{{i \cdot j}}{{\left\| i \right\| \cdot \left\| j \right\|}}$ (1)

Pearson相关相似度计算, 以项目之间相似度计算为例如式(2)所示, 用户之间相似度计算同理.

 $\mathop {Sim}\nolimits^b (\mathop I\nolimits_i ,\mathop I\nolimits_j ) = \frac{{\sum\nolimits_{u \in \mathop U\nolimits_{ij} } {\left( {\mathop r\nolimits_{ui} - \overline {\mathop r\nolimits_i } } \right) \cdot \left( {\mathop r\nolimits_{uj} - \overline {\mathop r\nolimits_j } } \right)} }}{{\sqrt {\sum\nolimits_{u \in \mathop U\nolimits_{ij} } {{{\left( {\mathop r\nolimits_{ui} - \overline {\mathop r\nolimits_i } } \right)}^2}} } \sqrt {\sum\nolimits_{u \in \mathop U\nolimits_{ij} } {{{\left( {\mathop r\nolimits_{uj} - \overline {\mathop r\nolimits_j } } \right)}^2}} } }}\;\;$ (2)

(3) 产生推荐结果. 通过步骤(2)的计算结果, 将未评分项目中的预测评分较高的N个项目作为推荐结果.

2 基于用户属性聚类的User-based协同过滤推荐算法 2.1 问题分析及改进思路

2.2 改进算法的设计与实现

(1) 用户身份属性数据预处理. 用户身份属性数据主要包括年龄、性别、职业、专业等. 年龄定义为数值数据. 性别定义为二元数据, 即输入性别数据时, 可以根据实际内容对应转化为二元数据0和1(输入性别: 男或1). 职业、专业等数据定义为标称型数据, 使用数值标号的形式进行标准化. 通过以上方式完成用户身份属性数据的预处理工作, 用户属性表达形式为User=(35, 1, 12, 6), 表示用户是年龄为35左右从事数学专业的男教师.

(2) 采用K-means聚类算法实现用户身份属性聚类. 主要实现流程如图1所示. 算法的时间复杂度T(n)=O(n×k×t), n代表对象总数, k代表类簇的个数, t代表迭代次数.

 图 1 K-means聚类算法的流程

(3)对用户属性数据聚类处理后, 再进一步实现User-based协同过滤推荐算法.

3 基于项目划分的Item-based协同过滤推荐算法 3.1 问题分析及改进思路

3.2 改进算法的设计与实现

 ${{Sim}}\left( {{{{I}}_{{i}}},{{{I}}_{{j}}}} \right) = (1 - {{\alpha }}){{Si}}{{{m}}_{{r}}}\left( {{{{I}}_{{i}}},{{{I}}_{{j}}}} \right) + {{\alpha Si}}{{{m}}_{{c}}}\left( {{{{I}}_{{i}}},{{{I}}_{{j}}}} \right)$ (3)

(1) 项目划分类别相似度计算. 结合如上讨论, 将项目划分的类别表示为p={p1, p2, p3, …, pm}, 项目Ii所属类别Pi={px, py, …}, 项目之间同属的相同类别越多相似性越近, 但不同类别的相关性情况也要考虑, 例如男生喜欢看武侠小说, 女生喜欢看爱情小说, 男生和武侠小说虽然不是同一类, 但彼此之间的相似度显然比同属于一类的武侠小说与爱情小说的相似度更高, 通过分析思考定义m×m的项目类别相似性矩阵Smm, 如式(4)所示.

 $\mathop {{S}}\nolimits_{{{mm}}} = \left[ {\begin{array}{*{20}{c}} {\mathop s\nolimits_{11} }& \cdots &{\mathop s\nolimits_{1m} }\\ \vdots & \ddots & \vdots \\ {\mathop s\nolimits_{m1} }& \cdots &{\mathop s\nolimits_{mm} } \end{array}} \right]$ (4)

 $S(\mathop p\nolimits_i ,\mathop p\nolimits_j ) = \dfrac{{\mathop v\nolimits_i \cap \mathop v\nolimits_j }}{{\mathop v\nolimits_i \cup \mathop v\nolimits_j }}$ (5)

 $\mathop {Sim}\nolimits_c (\mathop I\nolimits_i ,\mathop I\nolimits_j ) = \left\{ {\begin{array}{*{20}{l}} {\dfrac{{\mathop p\nolimits_i \cap \mathop p\nolimits_j }}{{\mathop p\nolimits_i \cup \mathop p\nolimits_j }}\quad \mathop p\nolimits_i \cap \mathop p\nolimits_j \ne \varphi }\\ {\max (s(\mathop p\nolimits_i ,\mathop p\nolimits_j ))\quad \mathop p\nolimits_i \cap \mathop p\nolimits_j = \varphi } \end{array}} \right.$ (6)

(2)考虑项目共同评分用户数对相似度的影响, 改进评分相似度计算. 对传统Pearson相似度计算公式(2)结合共同评分用户数, 融入相似度计算如式(7)所示.

 $\mathop {Sim}\nolimits_r (\mathop I\nolimits_i ,\mathop I\nolimits_j ) = \frac{{\mathop U\nolimits_i \cap \mathop U\nolimits_j }}{{\mathop U\nolimits_i \cup \mathop U\nolimits_j }}*\mathop {Sim}\nolimits^b (\mathop I\nolimits_i ,\mathop I\nolimits_j )$ (7)

(3) 确定最近邻. 采用综合相似度计算公式分别计算目标项目Ii与其它所有项目的综合相似度值Sim(Ii, Ij)(1≤jn, 其中ji), 结果进行排序并选取最相似的前K个项目为目标项目Ii的最近邻居集合, 显然K值的选取直接影响推荐结果的质量. 结合如上讨论, 采用项目相似性邻居选取阈值β动态选取最近邻, 考虑平均相似度因素, 得到最近邻算法如式(8)所示.

 $K(\mathop I\nolimits_i ) = \left\{ {\mathop I\nolimits_j \left| {Sim(\mathop I\nolimits_i ,\mathop I\nolimits_j )} \right. - \overline {\mathop {Sim}\nolimits_{\mathop I\nolimits_i } } > \beta ,j \ne i} \right\}$ (8)

4 实验结果及分析 4.1 实验数据

4.2 实验评估标准

 $MAE = \frac{{\sum\nolimits_{i = 1}^N {\left| {\mathop P\nolimits_i - \mathop R\nolimits_i } \right|} }}{N}$ (9)
4.3 实验结果及分析

(1) 基于用户属性聚类的User-based协同过滤推荐算法, 改进后是否能够提高推荐质量, 聚类个数K值及最近邻居个数都需要通过实验确定. 实验采用1 MB的数据集, 以MAE值作为推荐算法质量的衡量标准, 确定K值实验结果如图2所示.

 图 2 确定聚类个数K值

 图 3 确定近邻个数N值

 图 4 传统算法与改进算法推荐效果比较

(2)基于项目划分的User-based协同过滤推荐算法, 改进后的算法采用综合相似度的计算方法计算项目相似度, 通过实验确定系数α的权值, 实验结果如图5.

(3)将基于用户属性聚类与项目划分的协同过滤推荐算法(即改进算法)与传统的协同过滤推荐算法(CFRA), 并同时选取文献[8,15,16]提出的算法(分别简写为SCCF、CRF、UCSP)通过实验与本文所提出的算法进行比较, 各算法的推荐效果对比实验结果见表1.

 图 5 确定加权系数α的值

5 结论

 [1] 黄立威, 江碧涛, 吕守业, 等. 基于深度学习的推荐系统研究综述. 计算机学报, 2018, 41(7): 1619-1647. [2] Frémal S, Lecron F. Weighting strategies for a recommender system using item clustering based on genres. Expert Systems with Applications, 2017, 77(7): 105-113. [3] 黎新志, 高茂庭. 基于用户分类的隐含因子模型研究. 计算机应用研究, 2018, 35(8): 2289-2292. DOI:10.3969/j.issn.1001-3695.2018.08.012 [4] 王志虎, 黄曼莹. 基于用户历史行为的协同过滤推荐算法. 微电子学与计算机, 2017, 34(5): 132-136. [5] 石进平, 李劲, 和凤珍. 基于社交关系和用户偏好的多样性图推荐方法. 计算机科学, 2018, 45(S1): 423-427. [6] Katarya R, Verma O P. A collaborative recommender system enhanced with particle swarm optimization technique. Multimedia Tools and Applications, 2016, 75(15): 9225-9239. DOI:10.1007/s11042-016-3481-4 [7] 王光, 张杰民, 董帅含, 等. 基于内容的加权粒度序列推荐算法. 计算机工程与科学, 2018, 40(3): 564-570. DOI:10.3969/j.issn.1007-130X.2018.03.024 [8] 孙辉, 马跃, 杨海波, 等. 一种相似度改进的用户聚类协同过滤推荐算法. 小型微型计算机系统, 2014, 35(9): 1967-1970. DOI:10.3969/j.issn.1000-1220.2014.09.006 [9] 于琨, 孙波, 海本斋. 基于超图排序和组稀疏最优化的推荐系统. 计算机工程与设计, 2018, 39(7): 1996-2001. [10] 杨丰瑞, 郑云俊, 张昌. 结合概率矩阵分解的混合型推荐算法. 计算机应用, 2018, 38(3): 644-649. [11] 田保军, 胡培培, 杜晓娟, 等. Hadoop下基于聚类协同过滤推荐算法优化的研究. 计算机工程与科学, 2016, 38(8): 1615-1624. DOI:10.3969/j.issn.1007-130X.2016.08.016 [12] 丁少衡, 姬东鸿, 王路路. 基于用户属性和评分的协同过滤推荐算法. 计算机工程与设计, 2015, 36(2): 487-491, 497. [13] 杨尚君, 孙永维, 庞宇. 基于改进鱼群算法的多无人机任务分配研究. 计算机仿真, 2015, 32(1): 69-72, 102. DOI:10.3969/j.issn.1006-9348.2015.01.015 [14] 王颖, 王欣, 唐万梅. 融合用户自然最近邻的协同过滤推荐算法. 计算机工程与应用, 2018, 54(7): 77-83. [15] 杨兴雨, 李华平, 张宇波. 基于聚类和随机森林的协同过滤推荐算法. 计算机工程与应用, 2018, 54(16): 152-157. DOI:10.3778/j.issn.1002-8331.1712-0089 [16] 高茂庭, 段元波. 结合用户聚类和评分偏好的推荐算法. 计算机应用研究, 2018, 35(8): 2260-2264. DOI:10.3969/j.issn.1001-3695.2018.08.005