基于SVD与层次聚类的协同过滤推荐算法实现

徐泽兵　王忠

摘要：在如今这个信息爆炸的时代，我们要面对“信息过载”这一难题；以个性化推荐技术为核心的推荐系统有效的解决这一问题，其中协同过滤算法是目前应用最广泛也是最成熟的个性化推荐技术。基于此，本文提出一种基于SVD与层次聚类中的BIRCH算法来实现协同过滤算法。该算法在MovieLens数据集上的实验数据表明该算法有效的提高了推荐的质量。

关键词：个性化推荐；SVD；BIRCH算法

中图分类号：TP312 文献标识码：A 文章编号：1007-9416（2018）01-0130-02

最近几年，协同过滤算法[1]是比较成功并具有代表性的推荐算法，目前协同过滤算法大致分为两类：一是基于内存的协同过滤算法；二是基于模型的协同过滤算法。

本文针对数据的稀疏性、可扩展性等问题提出了基于奇异值分解与BIRCH层次聚类算法[2]的协同过滤算法。并且使用物理学上的能量守恒定律来确定SVD在降维时保存尽可能多的信息。使用BIRCH聚类算法缩小查询最近邻时的范围。实验表明，本文算法能够提高推荐质量。

1 传统的基于用户的协同过滤算法

在传统的基于用户的协同过滤算法中，我们完成推荐的过程一般分为下面几个步骤：第一：构建评分矩阵：第二：计算相似度，确定K个最近邻；第三：完成预测评分，实现推荐。因此我们完成的推荐的第一步就是对数据进行初始化，构建评分矩阵。

1.1 数据初始化

将用户集及评分项目集合构造出一个评分矩阵，其中代表有m个用户，代表有n个项目，表示用户对项目的评分值。

1.2 获取最近邻集合

基于用户的协同过滤算法完成推荐功能的第二步是为目标用户找到最近邻的集合，最近邻集合的确定是通过计算相似度来确认的，皮尔森相关系数在计算相似度时更加的准确，设来表示用户u与v之间的相似度，公式如下：

2 基于SVD与BIRCH层次聚类的协同过滤算法

在本节中将对本文提出的改进算法进行详细叙述，本算法的主要思想为：首先，通过奇异值分解对原始的用户评分矩阵进行预处理：构造出用户相关矩阵；其次，利用BIRCH算法进行归类，形成K个用户簇；之后根据目标用户确定目标簇并确定最近邻；最后实现top-N推荐。以下将详细叙述该算法的过程：

2.1 构造用户相关矩阵

在利用SVD进行降维时，所选择的降维维数k很重要，在本文中我们将保存原始矩阵的多少能量定义为能量阈值s。我们确定了s的值之后，就可以反向确定维度值k。此能量阈值的值为对角矩阵的前k个奇异值的能量除以全部奇异值的能量的结果。

确定k值之后，我們就可以将对角矩阵只保留前k个奇异值形成新的对角矩阵，从中取前k列变成，从中取前k行变成，其中k远远小于m和n的值，这样就达到了降维的目的。

经过上面的一系列矩阵分解降维处理之后，我们得到了用户特征矩阵，后面的分析都是基于此矩阵。

2.2 使用BIRCH算法对用户矩阵进行分类

在经过上一节的SVD处理之后我们得到用户特征矩阵，为了更加高效的获取到目标用户的最近邻，使用BIRCH算法对该矩阵进行聚类。主要思想是：利用树结构帮助我们进行快速的聚类，一般把其称作聚类特征树（CFTree）。该树的任一节点都是由若干个聚类特征（CF）组成的。流程如下为：

（1）在内存中构建CF树；

（2）以CF树叶元项对应的子簇为基础，实现数据点的聚类；

2.3 改进算法的描述

综合第二节的传统协同过滤算法以及本节前面对SVD以及BIRCH算法的描述，我们可以对本文改进算法进行简要描述：

输入：用户-项目评分矩阵，目标用户；输出：对目标用户进行Top-N推荐。

（1）对用户-项目矩阵进行SVD降维处理，根据公式得到用户特征矩阵；

（2）对用户特征矩阵进行BIRCH聚类，然后确定和目标用户相似的簇；

（3）根据皮尔森相关系数确定最近邻集合；

（4）对目标用户未评分的项目进行评分；

（5）根据预测评分结果实现Top-N推荐。

3 实验结果及分析

本文采用的数据实验集为MovieLens数据集。该数据集中的信息包含了一共943个用户对于1682部电影的十万条评分。评分值是1至5的整数，数字越高代表评分越高。

3.1 算法推荐质量度量标准

平均绝对误差（MAE）是常用的评判标准，其原理是计算用户对项目的预测评分值与实际评分值之间的偏差。MAE的值越小，代表推荐的质量越高。设预测评分集合为，实际评分集合为，公式如4-2所示：

3.2 实验结果及分析

在对用户-项目矩阵进行奇异值分解时，选择适当的降维维数很重要，过低会损失过多的信息量，过高的话失去降维的意义。通过实验当选择k为17时，MAE的值最低，推荐的性能最好。

为了验证改进算法的性能，我们将该算法与knn算法以及基于SVD的推荐算法进行比较，在取不同的近邻个数的情况下各算法的推荐性能：

由图1所示，当我们的近邻个数达到一定数目后，我们的改进算法推荐效果更加高效。

4 结语

本文提出的基于SVD与BIRCH层次聚类的协同过滤算法的优势有：第一，SVD对原始矩阵进行降维处理，有效的解决了数据稀疏性的问题；第二，BIRCH算法在求目标用户的最近邻时，缩小了搜索范围，有效提高算法运行时间。当然算法也有不足之处，例如当数据量过大时，SVD算法的效率会有所降低，这也是之后论文的研究改进方向。

参考文献

[1]杨阳，向阳，熊磊.基于矩阵分解与用户近邻模型的协同过滤推荐算法[J].计算机应用，2012，32（2）：395-398.

[2]蒋盛益，李霞.一种改进的BIRCH聚类算法[J].计算机应用，2009，29（1）：293-296.