协同过滤推荐使用非负矩阵分解在GPU-Accelerated火花的平台

文摘

非负矩阵分解(NMF)引入了一种有效的方式来减少数据压缩的复杂性及其能力从数据集,提取高度可说明的部分,它也被应用于各个领域,如建议,图像分析,文本聚类。然而,随着矩阵的大小增加,非负矩阵分解的处理速度非常缓慢。为了解决这个问题,本文提出了一种基于GPU的并行算法的NMF火花的平台,使充分利用内存计算模式和GPU加速的优点。新GPU-accelerated NMF火花平台评估在4-node火花异构集群中每个节点使用谷歌计算引擎通过配置一个NVIDIA K80 CUDA设备,和实验结果表明它具有竞争力的计算时间在现有解决方案的各种矩阵的订单。此外,GPU-accelerated NMF-based并行协同过滤(CF)算法提出,利用数据降维的优势和NMF的特征提取,以及CUDA的多核并行计算模式。使用真实MovieLens数据集,实验结果表明,并行化的NMF-based协同过滤火花的平台上有效地优于传统的基于用户和基于项目CF与更高的处理速度和更高的推荐精度。

1。介绍

近年来,数据的规模成倍地增加。在全球范围内,它正在成为一个趋势研究和发展大数据技术,使用大数据来促进经济发展,改善社会治理,改善政府服务和管理能力。如何有效地从海量数据中提取知识,理解和分析,最后作出预测是当前热门的研究话题。

对大数据处理作为一种重要的数学工具,非负矩阵分解是矩阵分解方法,将非负矩阵分解成两个低秩矩阵约束非负元素(1,2]。这导致的减少表示原始数据,可以看到作为特征提取或降维技术。NMF的广泛使用是由于其能力提供新的见解和相关信息的复杂的潜在关系实验数据集。自从李和Seung性质的论文(1),NMF一直得到广泛的研究,大量的应用于科学和工程。它已成为一种重要的数学方法在机器学习和数据挖掘和已广泛应用于特征提取,图像分析(3),音频处理(4),推荐系统(5,6)、模式识别、数据聚类(7],话题建模[8),文本挖掘(9,生物信息学10),等等。不像其他分解方法(例如,PCA、ICA圣言,矢量量化,等等),NMF可以解释为一个数据的器件表示因为只有添加剂组合是允许的。与PCA和ICA, NMF严格要求的条目生成的矩阵非负。很有意义的一个约束在许多应用程序中,数据表示的是纯粹的添加剂;例如,电子商务网站的用户评级通常是负的值,和图像像素值都是非负的。

NMF的主要问题是,原始矩阵通常是高阶矩阵,这使得计算复杂度非常高。因此,并行算法的NMF逐渐吸引了更多的关注,和一些平行NMF算法已经提出。尽管NMF的并行化可以提高计算效率在一定程度上,并行算法应该匹配机器硬件架构,应该具有很强的可伸缩性,即增加有效利用处理器资源的能力。

加速HPC应用程序目前正在广泛研究使用新的硬件技术,如最近的中央处理单元(cpu)获得多个处理器核心并行计算,图形处理单元(gpu)并行处理庞大的数据块,和混合cpu / gpu计算HPC的这是一种很常见的解决方案。gpu比其他HPC加速器越来越关注由于其高计算能力,强大的性能,功能,和较低的价格。现代GPU不仅是一个强大的图形引擎也是一种高度并行可编程处理器具有峰值运算和内存带宽11]。他们现在加速图形和一些应用程序使用数据并行性(GPGPU)由于高可用性的应用程序编程接口(api),如统一计算设备架构(CUDA)和开放计算语言(OpenCL)。

火花是一个分布式内存计算框架,提出了AMPLab的加州大学伯克利分校,2009年是基于框架的处理大量的数据在内存中(12,13]。它支持四种编程语言一样,Scala、Java、Python和r .弹性分布式数据集(抽样)是一种新概念提出的数据收集的火花。抽样可以支持粗粒度的写操作(14]。引发特定抽样缓存到内存中,下一个操作可以直接从内存中读取。数据没有写入磁盘,节省大量的磁盘I / O开销。实验性能评估确认,火花的表现增加了几十甚至100倍与Hadoop相比,依靠MapReduce模型(15,16)和数据被存储在一个叫HDFS的分布式文件系统,而不是在内存中。

目前,一些平行的非负矩阵分解的方法已被提出,例如,高性能方法使用消息传递接口(MPI) [17],GPU-accelerated方法[9,18),和Hadoop-based MapReduce方法(10,19]。这些方法主要是利用多核系统的特征,还有可能提高性能通过利用内存、CPU和GPU资源结合在一起。

同时,协同过滤方法的自动预测(过滤)的利益用户通过收集来自集团用户的偏好(合作)。协同过滤方法的基本假设是,如果一个人有相同的意见作为B一个问题,更可能是B的意见不同的问题比一个随机选择的人。通过计算两个用户之间的相似度的数据,我们可以得到两个用户之间的相似度。虽然传统协同过滤是非常成功的推荐系统,随着数据的增加,推荐算法一直面临着各种问题,如可伸缩性问题,冷启动问题,矩阵稀疏问题。

为了解决上述问题,本文提出了结合Spark-based和基于GPU加速模型开发可扩展的NMF并行算法,利用GPU和内存计算,获得一个高度可扩展并行NMF算法。此外,本文提出了一种基于NMF的协同过滤方法,并行和迁移到火花平台配备GPU执行,有效地提高了计算效率,从而能够更快地更新推荐结果和产生更准确的推荐结果。的实验结果表明,该并行NMF-based协同过滤有效地提高了计算效率和准确性。

剩下的纸是组织如下。部分2调查相关工作。部分3介绍了NMF的数学基础,描述了通用并行NMF的原则。部分4描述了GPU-accelerated火花平台的架构和礼物GPU-accelerated NMF火花。部分5介绍了基于NMF的协同过滤算法。部分6提出了绩效评估的结果GPU-accelerated NMF火花和协作filtering-based NMF,紧随其后的是结论部分7。

2。相关工作

2.1。混合大数据处理模型

由于硬件设备的多样性在高性能计算系统中,为了解决现实世界的复杂的应用程序,不同的计算模式的混合成为一个主要的方向,如混合CPU / GPU和CPU / FPGA。从模型的角度来看,有混合MapReduce / CUDA模型(20.),混合MapReduce /麦克风模型(21),混合OpenMP / MPI模型(22),等等。近年来,学术界和产业界的实践经验表明,基于异构计算平台的CPU / GPU系统有很大的发展潜力,吸引了越来越多的关注11,23]。

2.2。平行的非负矩阵分解

处理大型数据集通过非负矩阵分解,有三个主要方向。第一节课的算法称为在线NMF算法(6,24,25),这是最古老的通过NMF方法处理高维数据处理。第二类称为分布式NMF算法,通过网络分发数据这几个小规模的数据可以并发执行。第三类算法称为压缩NMF算法(26,27),执行结构化随机压缩项目数据在低维流形。在本文中,我们只关注分布式NMF。

非负矩阵分解通常是通过交替迭代解决(2),这使得它适合并行化。三个方面限制的可伸缩性并行NMF算法如下:计算过程之间的同步,数据加载和数据传输,并行粒度划分。目前,一些并行算法提出了加快非负矩阵因子分解。

Janecek等人使用线性代数工具如布拉斯特区,LAPACK, ARPACK实现多线程程序在单个计算机执行高效NMF [28]。洛佩斯和里贝罗实现了一个基于gpu的机器学习库命名GPUMLib,其中包含的一个实现GPU-accelerated NMF [29日]。Kysenko等人也应用GPU-accelerated NMF文本挖掘(9]。巴腾堡蛋糕和韦塞尔并行NMF实现,使用共享内存多核系统的特点,基于OpenMP和许多核心基于CUDA GPU技术,应用到音频信号处理,但它只能适用于单个节点(30.]。一个平行的NMF基于MPI的组合和GPU实现(18),和用于生物序列比较。唐等人提出了一个混合并行分层NMF算法基于OpenMP和MPI (31日]。

使用一些高性能计算软件包,如ParMETIS ScaLAPACK, HPSEPS,我们可以开发非负矩阵分解并行算法基于MPI / OpenMP / GPU使用这些软件包,它最终是不适合实际的大数据处理在互联网时代。基于开源的大数据处理框架,比如Hadoop和火花,这是一个更合适的想法发展NMF的并行算法,使其适合互联网大数据处理。在[10),廖等人意识到基于MapReduce的分布式NMF进行生物数据处理。太阳等人意识到大规模NMF基于MapReduce (32,刘等人还提出了一个分布式NMF基于使用Hadoop MapReduce处理大规模网络数据流的方法(19]。在我们以前的工作(33),我们提出了一个并行NMF算法在火花的平台,使充分利用内存计算模式的优点。

2.3。并行和分布式协同过滤

许多电子商务公司已经注册推荐系统和他们的服务,例如,由亚马逊产品推荐(http://www.amazon.com和淘宝http://www.taobao.com由Netflix()和电影推荐http://www.netflix.com)。实现和算法的协同过滤推荐系统的应用面临着几个挑战。首先是处理数据集的大小。第二个来自评分矩阵的稀疏,这意味着每个用户只额定数量相对较小的项目。随着大量数据的增加和复杂的数据,它是面对效率低的问题。因此,高效的协同过滤算法是必要的。

最近,极大的兴趣已转向并行和分布式协同过滤算法的实现。他们可以分为几类:(1)分布式内存的实现,如基于mpi并行实现提出了(34,35];(2)共享内存实现,比如MPI实现(36,37];(3)基于gpu实现,如38,39];(4)基于平台的实现,比如Hadoop所实现的基于平台的协同过滤(40,41];和(5)异构实现,如纳提出的混合OpenMP + MPI实现et al。42]和Karydi Margaritis [43]。

另一方面,这些挑战的协同过滤很好的照顾了矩阵分解(MF)。矩阵分解方法最近收到更大的接触作为潜变量分解无监督学习方法和降维44]。这是一个强大的技术发现隐藏在数据背后的结构。有几个矩阵分解模型,可用于协同过滤推荐,例如,奇异值分解(计算)45,46),主成分分析(PCA) (47),概率矩阵分解(及)48),而非负矩阵分解(49]。然而,有效的协同过滤算法也要求快速矩阵分解的地方。

总之,高维NMF是耗时的,迫切需要高性能的并行化解决方案。目前,没有灵活的分布式处理框架考虑内存计算模式和GPU技术NMF在同一时间。考虑火花分布式处理框架,结合GPU强大的计算优势和大容量内存,大规模并行NMF算法将使该算法很容易适应互联网大数据的处理。我们所知,这是第一NMF-based协同过滤实现并行化和迁移到火花平台配备GPU。实验结果验证NMF-based的并行协同过滤火花的平台上有效地提高了计算效率和精度。

3所示。平行的非负矩阵分解

3.1。非负矩阵分解

非负矩阵分解寻求近似一个负的 矩阵(在这种情况下,一个矩阵非负,如果所有的元素都是非负的)的产品 非负矩阵和的维度 和 ,分别与给定,通常最大等级低 。通常情况下,选择来满足 这样可以被认为是一个压缩形式的原始数据。无监督学习的基础和数据简化算法与应用图像识别,语音识别,数据挖掘和协同过滤,等等。

NMF能代表大输入数据集的线性组合减少元素的命名集合因素。通过这种方式,包含组降低因素,存储等因素的线性组合系数重建 。NMF反复修改和直到他们的产品接近 。这样的修改,由矩阵产品和其他代数操作,来自最小化代价函数,描述之间的距离和 。Lee Seung提出了两个基于乘法的NMF算法更新规则的目标函数的平方欧氏距离(SED)和广义Kullback-Leibler散度(分别为GKLD) (1,2]:

然后,NMF的目标转化为优化如下:或 ,和 。

在本文中,我们定义SED作为目标函数,我们有 ,导致矩阵的更新规则吗和 :

3.2。平行的非负矩阵分解

之前描述我们的实验研究中,我们简要介绍了主要的NMF现有的并行技术。通过分析方程(1)和(2),我们可以得到迭代计算的基本原理NMF并行的方式。矩阵运算块中执行。基于块的并行矩阵更新规则和在多个流程如图1和的大小可以根据硬件配置调整。在初始化的时候,最初的和生产。因为SVD-based初始化已经被证明是更有效的迭代和(50),我们生成初始和通过计算的方法。如你所见,矩阵的大小是 ,矩阵块的大小是 ,和矩阵块的大小是 ,最后更新的矩阵块是获得。如图1 (b),新的矩阵用于计算新矩阵块等等。矩阵和或者更新。

从分析可以看出,原始矩阵相当于一个只读变量,这是所有进程之间共享。迭代的矩阵和需要所有进程之间的同步。算法通过迭代挤整个矩阵或每个处理器,然后执行本地更新计算更新或 。

4所示。GPU-Accelerated NMF的火花

4.1。火花

从概念上讲,Apache火花是一个开放源码的内存数据分析集群计算框架(12,13]。MapReduce-like集群计算引擎,火花也具有良好的可扩展性和容错性等特点MapReduce。主要的抽象的火花是抽样,使火花是够资格的过程迭代工作,包括PageRank算法和k - means算法。抽样是独一无二的火花,从而引发有别于传统的MapReduce引擎。此外,抽样的基础上,应用火花能保持数据在内存中跨查询和自动重构数据丢失时失败。抽样是一个只读的数据集合,它可以是一个文件存储在外部存储系统,如HDFS或派生的其他抽样生成的数据集。抽样储存很多信息,比如它的分区,和一组依赖父母抽样称为血统。的帮助下血统,火花迅速和有效地恢复丢失的数据。引发了巨大的性能处理迭代计算,因为它可以重用中间结果和跨多个并行操作将数据保存在内存中。

4.2。GPU-Accelerated火花的平台

现在现代gpu通用计算的能力。由于Nvidia的CUDA GPU的流行,它可以被视为一个C / c++扩展,我们将主要遵循CUDA术语引入GPU计算。当前一代又一代的gpu作为加速器的cpu和cpu和gpu之间的数据传输通过PCI-E公交车。NVIDIA GPU编程通常是支持NVIDIA CUDA的环境。一个程序在主机(CPU)可以调用内核执行CUDA GPU要调用的函数。

GPU是一个多核处理器设计并行的计算密集型任务。它有非常高的计算处理能力和数据吞吐量。在科学研究和实际应用,可平行的计算任务模块用更少的逻辑处理系统中经常被移植到GPU执行,和一个大的执行性能改进通常可以实现。

然而,火花集群将慢下来当处理非常大规模的数据集,特别是当节点数不是很高。与此同时,越来越多的开发人员使用gpu的并行计算来获取高吞吐量和性能。火花结合GPU,混合架构正迅速成为一个新兴的技术,嵌入GPU的火花,实现CPU / GPU集成和构建一个高效的异构并行系统。

CPU / GPU异构并行集群,CUDA-based GPU加速技术,和火花计算任务由GPU加速。基本思想是,火花抽样的操作的一部分转移到GPU核心。GPU代码执行流程如下:(1)从主内存复制数据到GPU全局内存;(2)GPU是由CPU指令;(3)GPU并行处理在每个核心;和(4)GPU内存返回结果。根据这一观点,结合火花工作流,GPU代码封装,然后引发工人和GPU之间的数据传输。Spark-GPU核聚变的基本原理如图2。

从编程语言的角度来看,由于GPU程序通常是在C / c++开发语言和火花的平台使用Java语言程序开发,Java的JNI (Java Native Interface)技术提供了一种解决桥梁GPU和火花通过代码封装为职工实现接口调用。可以使用几个JNI GPU编程工具。例如,JCuda (http://www.jcuda.org)是一个开发工具包,提供了CUDA运行时绑定,目前包括多个包,如JCublas JCufft, JCurand, JCusparse, JCusolver, JCudpp JNpp、JCudnn等。它是方便的在Java语言编写GPU的程序。其他用户定义的GPU用C / c++编写的程序也可以被称为后打包成Java函数。

对于开发人员,双向传输通道和主存之间的GPU全局内存。如果抽样的操作转移到GPU核心,主存储器之间的高速数据传输和GPU全局内存是必需的,也是由函数封装,实现作为显示在图2。

4.3。GPU-Accelerated NMF

我们证明了矩阵方程的迭代过程(3)和(4)和图1的主要原理,基于gpu的并行NMF呈现在图3。基于gpu的并行NMF的基本思想是设计几个内核函数实现矩阵的更新规则和 。 和blockwise-transferred。在图3,用红线圈起的部分操作表示CUDA内核,“·∗”和“·/”表示逐点矩阵运算,乘法,分别和分裂。大多数的矩阵运算可以实现使用的库Cublas Cusparse,连同两个自定义操作,点乘法和点。为了减少编程困难,使用JNI技术转让CUDA程序的Java函数封装、被执行人火花。

4.4。GPU-Accelerated NMF的火花

火花有优点在迭代计算和GPU具有向量和矩阵的数值计算。Spark-GPU融合平台,快速内存读写结合GPU加速,发挥各自优势,提高性能。NMF计算启动和控制火花司机。工人们计算迭代并行任务在一个分布式的方式。员工以最高的速度优化使用GPU设备和运行GPU内核函数来完成这个任务。所有中间结果写入到内存中每个迭代和交换在工人和发送到GPU全局内存。直到迭代终止,任务完成后,结果将被写入到HDFS。

整个算法中描述的算法1。矩阵播放所有执行者,每个工人获得相应的矩阵块或从抽样。火花的平台,触发动作操作结束后,所有累积的运营商形成一个有向无环图。任务分为不同阶段根据不同抽样之间的依赖关系。一个阶段由一系列函数执行管道。通过抽样的各阶段GPU-accelerated NMF列出如下:阶段1:读取和转换矩阵和 ;执行mapPartition函数来更新块;阶段2:所有块的拼接后通过执行一个迭代收集操作;阶段3:读取和转换矩阵和 ;执行mapPartition函数来更新块;阶段4:所有块的拼接后通过执行一个迭代收集操作,准备下一次迭代。

然后,迭代粗加工的上述四个阶段。在内存中缓存数据的方法在文件系统为每个迭代中要快得多。当达到收敛条件时,终止矩阵更新,结果被写入HDFS。

5。基于NMF的协同过滤算法

5.1。传统的协同过滤算法

协同过滤推荐算法可以分为两类:基于用户的CF和基于项目CF。基于协同过滤的推荐过程可以被描述为三个阶段:阶段1:收集用户首选项。预处理后的用户行为数据,根据不同的行为分析方法,你可以选择分组或加权获得“user-item”偏好矩阵的大小是 ,在哪里用户的数量,是物品的数量,矩阵元素表示 - - - - - -用户的偏好 - - - - - -th项目,通常是一个浮点数的范围(1、5)或二进制值0或1。价值高度依赖项的内容。如果在电子商务项目是一种商品,值表示用户是否购买。有时,这意味着用户是否关注与否,或兴趣是喜欢或不喜欢,兴趣是高或低。阶段2:发现类似的用户或项目。在“user-item”偏好矩阵,用户对所有项目的偏好作为一个向量来计算用户之间的相似度获得相似矩阵 。为一个特定的用户 ,从剩下的用户在系统中,相似度值对应于用户在降序排序;的 - - - - - -最近邻用户相似度值最大的选择形成了最近邻用户设置 。基于项目的CF,所有用户的偏好一个项目被视为一个向量来计算项目之间的相似度。一般来说,有三种常见的计算相似度的方法:欧几里得距离,皮尔逊相关系数和余弦相似性。本文使用皮尔逊相关系数为例(44]。我们选择皮尔逊相关系数的原因是,与欧氏距离不同,皮尔逊相关系数能够降低分数膨胀的错误,在推荐相关领域。使用皮尔逊相关系数的相似性计算公式提出了如下: 在哪里和表示两个用户, 相似的用户吗和 ,和和的评级 - - - - - -项目由用户给出和 。阶段3:生成预测矩阵和头n个推荐结果。使用的得分上的最近邻项目,具体项目用户的分数是通过加权平均计算的相似之处。假设用户的最近邻集合 ;用户的预测评分的项表示为 ,所示如下方程: 在哪里项目由用户的平均评级吗 , 是用户之间的相似性和用户 , 是项目的评级吗由用户 ,和项目由用户的平均评级吗 。然后,用户的项目没有根据预测分数,分数或购买并获得头n个项目推荐数据集和给用户推荐他们吗 。

5.2。基于NMF的协同过滤算法

提出的基于NMF的协同过滤算法本文可以分为两个过程:矩阵分解降维与协同过滤。(1)矩阵分解和降维步骤1:使用基于gpu的NMF、大规模用户偏好矩阵两个矩阵的乘积来近似和 。基本矩阵代表项目特征矩阵,其中包含的设置因素(是NMF的等级)和投影矩阵代表用户特征矩阵,它存储的线性组合系数的因素。步骤2:根据矩阵 ,投影向量的目标用户评级向量对应基础矩阵可以计算并表示 。然而,选择一个合适的数量的潜在因素会影响NMF的效果。在本文中,为了提高协作filtering-based建议,我们需要选择最优排序NMF。根据同表象相关系数(51),我们多次重复NMF每等级和计算出类似的结果,换句话说,确定集群的稳定性如何,因为最初的种子是随机的。我们选择最高的之前同表象系数下降。(2)协同过滤步骤1:GPU-accelerated用户相似性计算,每个用户分配一个线程在CUDA编程模型中,核函数是用来计算皮尔逊相关系数,和之间的相似性和投影矩阵的每一列并行计算得到用户相似矩阵 。步骤2:前用户价值最高的相似形式最近邻集为用户 。步骤3:使用的邻居在最近的邻居集和相应的原始分数进行加权计算生成分数预测矩阵 。步骤4:排序和使用预测矩阵得到头n个推荐结果 。

6。业绩评估

6.1。实验设置

为我们的实验中,我们使用四个n1-standard-4谷歌计算引擎实例,每个实例配置了4个vCPU 15 GB内存和100 GB的SSD硬盘asia-east1地区。每个实例也配置了NVIDIA K80 2496 CUDA GPU核心和12 GB全局内存。4-node集群,64位安装Ubuntu 16.04 LTS,和其他软件包包括Hadoop 2.7, 2.3, 9.0 JDK 1.8, CUDA。

6.2。数据集

MovieLens数据集(https://grouplens.org/datasets/movielens/)GroupLens研究小组提供的用于实验。它包含130642部电影取得的分数7120用户。我们随机选择不同大小的数据集进行测试。每个用户必须至少20电影,评级的范围从1到5,和更高的评级是用户更满意。在实验中,电影评级是转化成得分矩阵。如果用户没有电影,速度相应矩阵元素值为0;因此,得分矩阵是一个典型的稀疏矩阵。在我们的实验中,数据集我们随机选择需要进一步划分为训练集和一个测试集通过将非零元素,和70%的数据集作为训练集,另30%作为测试集,确保矩阵和矩阵有相同大小的矩阵呢 。

6.3。基线算法

连环NMF。串行NMF算法只在单个执行线程使用CPU。根据方程(3)和(4),交替更新的方法和是用来获得通过执行多个迭代分解结果。基于gpu的NMF。基于GPU的NMF算法也是在一个线程执行,但GPU设备支持。如你所见图3交替更新和是由GPU加速的,使用的库实现Cublas Cusparse,连同两个自定义操作,点乘法和点。Spark-based NMF没有GPU的支持。对于这个算法,计算NMF火花集群,每个节点没有GPU设备。类似于算法1的两个阶段 和 ,没有GPU支持更新和在每个迭代中,只有CPU的矩阵运算。

6.4。评价指标的建议

为了精确测量算法的性能,除了运行时间,预测分数和推荐结果的精度也会考虑。在本文中,我们使用均方根误差(RMSE)和平均绝对误差(MAE)测量的准确性预测分数。测量的推荐结果的准确性,准确率(精度)和召回率(召回)通常用于测量,在一起F测量综合考虑这两个指标之间的矛盾。

RMSE措施基于预测的准确性预测分数之间的均方根误差和实际得分。RMSE值越小,更准确的预测结果和推荐算法的质量就越高。预测分数设置 通过培训,获得与实际用户偏好分数设置 在测试集。因此,RMSE的定义是

美措施基于预测的准确性预测分数之间的平均误差和实际得分,这被定义为

在我们的实验中,我们使用三个评价指标来评估性能:精度,回忆,F-measure。项目中从来没有购买或评价,项目预测评级最高的选择形成了头n个推荐列表。我们定义设定的项目推荐给用户和定义实际上喜欢由用户设置的项目在测试集。准确性意味着相关项目的推荐项目的比例。简单地说,它是建议命中率(打击意味着推荐项目测试集的分数,分数超过某一阈值)。我们定义组的所有用户,推荐精度精度的定义是:

正确的比例推荐项目所有项目的推荐结果被定义为回忆:

F测量精度和召回的加权调和平均数,定义如下:

在这篇文章中,训练数据由NMF映像,然后头n个推荐结果是根据算法生成的分段吗5.2。测试数据只是用于计算各种推荐评价指标,如RMSE,美,精度,回忆,没有突出的测试数据由训练数据的潜在空间。

6.5。NMF的结果分析

在实验中,我们使用四个算法进行性能评估:(i)串行NMF,(2)基于GPU的NMF, (3) Spark-based NMF没有GPU的支持,及(iv) Spark-based NMF GPU支持提出和发展在Spark-GPU融合平台。我们设计了三个验证新算法的性能比较。我们选择一些典型的矩阵维度,和迭代的数量是100。

6.5.1。GPU加速的性能

我们进行了基于gpu的NMF在单个节点,我们不同的矩阵尺寸见图4。我们测量了计算时间,然后我们还在同一个节点执行串行NMF等计算GPU加速验证GPU加速的有效性。加速被定义为单节点的计算时间比串行方法单节点GPU计算时间的方法;也就是说, 。加速随矩阵维度,我们获得的最大加速45 x GPU与CPU相比。

6.5.2。性能NMF的火花

在这个评估中,我们开始了火花集群,和工人的数量节点是不同的从1,2,3,4。我们不同的矩阵维度从800∗800,800∗1600,800∗3200、1600∗1600和800 6400到1600∗∗3200和测量NMF的计算时间火花的平台,和结果如图所示5。当节点的数量是4,我们设置了许多火花执行人16日,与矩阵维度的增加,4个节点的优势越来越明显。与3-node火花平台相比,4个节点的计算时间节省了50%的时间。

6.5.3。性能NMF的火花与GPU的支持

在最后的评估中,我们开始了火花集群、节点的数量是4,和我们不同的矩阵维度从6400∗6400,3200∗25600,和6400年相比25600年12800到6400∗∗non-GPU支持GPU支持。从图可以看出64-node火花的平台,NMF与GPU的计算时间小于NMF的GPU。当矩阵的大小是6400∗25600,NMF火花与GPU的支持可以节省大约10.8%的时间。NMF GPU-accelerated火花的平台上明显显示了执行效率。

由于NMF的数学基础和blockwise-based并行的原则,有频繁的数据分布和数据收集在所有执行者,沟通成本是非常高的NMF的火花。然而,相比数据分布和数据收集的执行花更少的时间函数由于GPU加速。从时间的角度分析,通信和数据交换NMF并行算法的瓶颈。NMF GPU-accelerated火花的平台上改进仍有很大潜力。

6.6。协同过滤的结果分析

在实验中,我们比较了三种算法的性能:传统的基于用户的CF,传统的基于CF, NMF-based CF提出。矩阵的大小变化从400∗800,400∗1600、800∗1600和800 3200到1200∗∗3200进行测试。迭代的数量是100,我们为每个用户选择50项位推荐列表。

6.6.1。预测精度的比较分数

为了比较预测精度,我们RMSE和梅的三个算法相比,如图7(一)和7 (b),分别。在五个不同的得分矩阵大小,NMF-CF明显比User-CF Item-CF RMSE和梅。结果RMSE NMF-CF美是最小的,而Item-CF算法获得最大预测误差和最糟糕的预测效果。当矩阵的大小是400∗800,与Item-CF算法相比,NMF-CF RMSE的结果是减少了31.64%,和梅NMF-CF减少了28.5%。

6.6.2。比较推荐的准确性

推荐的精度、召回和F测量的三个算法如图8(一个)- - - - - -8 (c),分别。在五个不同的得分矩阵大小,当矩阵的大小增加时,所有指标三个算法也有所下降。NMF-CF优于User-CF和Item-CF算法在所有三个指标,并明确表明CF建议基于NMF的质量是最好的。然而,随着矩阵大小的增加 ,特别的增加 ,这意味着项目数量的增加,我们只在协同过滤推荐50项。在计算两个指标精度和召回,我们与30%的测试集,和推荐商品的命中率将低,和NMF的优点是越来越小。当矩阵的大小是1600∗3200,NMF-CF和User-CF算法的结果几乎是一样的。Item-CF算法的推荐效果一直是最坏的打算。

6.6.3。比较推荐的运行时间

首先,我们只评估NMF-CF算法的运行时间,我们考虑两个条件引发平台:(i) CPU-based NMF-CF(只有1个节点使用)和(2)CPU +基于gpu的NMF-CF(4节点使用)。场景5矩阵的大小,运行时间的结果如图9。从图可以看出,当采用GPU加速,NMF的计算时间明显减少。矩阵尺寸变大,并行效率越来越高,加速效果也越来越好。当矩阵的大小是1600∗3200,由于利用GPU, CPU +基于GPU的方法是CPU-based方法相比减少了44.8%,这也证明了NMF-CF GPU的加速性能。

然后,运行时间比较4-node火花的平台中执行了GPU支持三个算法。在所有的三个算法,GPU是用来计算皮尔逊相关系数,使用GPU计算NMF NMF-CF算法。运行时间对比结果如图10。从图可以看出,随着矩阵大小的增加,每一个算法的运行时间增加了。NMF-CF推荐算法的运行时间显著优于User-CF和Item-CF算法。当矩阵的大小是1600∗3200,NMF-CF算法的运行时间减少了33.3%相比Item-CF算法和User-CF算法相比减少了22.5%。

总的来说,与传统CF相比,NMF-CF推荐算法包含得分矩阵的分解的过程成和 ,这似乎是一个耗时的操作。事实上,当计算相关系数后,它将NMF-CF节省大量时间。由于矩阵的大小是 ,的价值反映出的数量特性或话题,的价值通常是非常小的(它通常需要2到10)的价值,和矩阵的大小很小,通过计算相关系数来获得 - - - - - -最近的邻居为每个用户花更少的时间在NMF-CF算法比User-CF算法或Item-CF算法。此外,除了增加精度,NMF-based CF推荐算法使用gpu并行运行和运行计算时间仍然是最短的。

7所示。结论

在异构的CPU / GPU集群、节点有大量内存资源和GPU多核资源,分布式存储节点之间的优势和在节点应该利用数据共享。异构并行计算是一种有效和可行的并行编程策略。一个GPU-accelerated NMF算法火花的平台上设计了本文解决的问题处理速度低NMF矩阵的大小增加。通过绩效评估,实验结果证明,Spark-based内存中的计算和GPU的组合具有较高的执行效率。另一方面,推荐系统已经广泛应用于许多领域,但随着用户数量和项数的增加,计算速度也变得缓慢和推荐的准确性下降。虽然传统协同过滤是非常成功的推荐系统,随着数据的增加,推荐算法一直面临着各种问题,如可伸缩性问题,冷启动问题,矩阵稀疏问题。本文实现了NMF算法协同过滤推荐,NMF相结合,传统的协同过滤方法,分解原始分数数据基础矩阵和投影矩阵,并引发平台上并行运行在GPU加速。实验矩阵与不同大小显示并行NMF协同过滤推荐算法不仅提高了预测和推荐精度,而且大大提高了计算效率。

数据可用性

使用的数据来支持本研究的发现可以从相应的作者。

的利益冲突

作者宣称没有利益冲突。

确认

这项工作得到了国家自然科学基金资助下61602169和61602169号,中国的国家重点研发项目批准号下2018 yfb1402800,湖南省自然科学基金批准号下2018年jj2135以及湖南省教育科学研究基金部门批准号18 a186。

引用

1. d·d·李和h . s . Seung“学习对象的部分非负矩阵分解,“自然,卷401,不。6755年,第791 - 788页,1999年。视图:出版商的网站|谷歌学术搜索
2. d·d·李和h . s . Seung“非负矩阵分解算法,”神经信息处理系统13的进步,论文从神经信息处理系统(少量)2000t·k·利恩,t . g . Dietterich诉Tresp, Eds。麻省理工学院出版社,页556 - 562年,丹佛,有限公司,2000年美国。视图:谷歌学术搜索
3. a . Falini g可以见到效果,c . Tamborrino et al .,“显著为高光谱图像检测通过sparse-non negative-matrix-factorization和小说距离措施,”学报2020年IEEE会议进化和自适应智能系统,eai 2020IEEE,页1 - 8,巴里,意大利,2020年。视图:谷歌学术搜索
4. 诉Leplat: Gillis, a . m . s .盎”盲音频源分离与最小的体积beta-divergence NMF,”IEEE信号处理卷,68年,第3410 - 3400页,2020年。视图:出版商的网站|谷歌学术搜索
5. 夏罗x, m .周y,问:朱,“一个有效的非负matrix-factorization-based方法协同过滤推荐系统,”IEEE工业信息,10卷,不。2、1273 - 1284年,2014页。视图:谷歌学术搜索
6. Rendle和l . Schmidt-Thieme“在线更新正规化内核为大规模的推荐系统,矩阵分解模型”学报2008年ACM大会在推荐系统中,RecSys 2008p . Pu, d . g .桥b . Mobasher f·里奇,Eds。ACM,页251 - 258年,2008年瑞士洛桑。视图:谷歌学术搜索
7. m . y . Chen Rege说,m .盾和j .华“非负矩阵分解semi-supervised数据聚类,知识和信息系统,17卷,不。3、355 - 379年,2008页。视图:出版商的网站|谷歌学术搜索
8. j . Choo c·李,c . k . Reddy和h .公园,“乌托邦:用户驱动的话题建模基于交互的非负矩阵分解,“IEEE可视化和计算机图形学,19卷,不。12日,第2001 - 1992页,2013年。视图:谷歌学术搜索
9. 诉Kysenko k·鲁普,o .马尔琴科s Selberherr和a . Anisimov“GPU-accelerated非负矩阵分解为文本挖掘,”自然语言处理和信息Systems-17th国际会议上的应用自然语言信息系统,NLDB 2012年,格罗宁根,荷兰,2012年6月代谢途径。程序,在计算机科学课堂讲稿g . Bouma a性的话,e . Metais和h . Wortmann, Eds。,卷。7337,pp. 158–163, Springer, Berlin, Germany, 2012.视图:谷歌学术搜索
10. j·r·廖y . Zhang关,s .周”CloudNMF:非负矩阵分解的mapreduce实现大规模生物数据集”基因组学、蛋白质组学和生物信息学,12卷,不。1,48-51,2014页。视图:出版商的网站|谷歌学术搜索
11. 米塔尔和j·s .检查者CPU-GPU异构计算技术的调查,“ACM第一版。测量员卷,47号4、1 - 69、2015页。视图:出版商的网站|谷歌学术搜索
12. m . Zaharia m . Chowdhury m·j·富兰克林,美国Shenker,斯托伊卡,“火花:集群计算工作集,”第二届USENIX车间在云计算的热点话题,HotCloud 10e . m .那鸿书和d .徐Eds。,USENIX Association, Boston, MA, USA, 2010.视图:谷歌学术搜索
13. m . Zaharia r . s .鑫p·温德尔et al .,“Apache火花,”ACM的通信卷,59号11日,56 - 65,2016页。视图:出版商的网站|谷歌学术搜索
14. m . Zaharia m . Chowdhury t Das et al .,“弹性分布式数据集:内存中的集群计算的容错抽象,”第九届USENIX学报》研讨会上网络系统设计和实现,NSDI 2012页,15-28 USENIX协会,CA,圣何塞美国,2012年。视图:谷歌学术搜索
15. j·迪恩和s .格玛沃特”MapReduce,“ACM的通信,51卷,不。1,第113 - 107页,2008。视图:出版商的网站|谷歌学术搜索
16. b, g . Fedak m . Tang和h他,“可用性通过互联网/网络感知mapreduce,”信息科学卷,379年,第111 - 94页,2017年。视图:出版商的网站|谷歌学术搜索
17. Kannan r、g·巴拉德和h .公园,“非负矩阵分解,高性能并行算法”21 ACM SIGPLAN学报》研讨会上并行编程的原理和实践,PPoPP 2016西班牙巴塞罗那,页1 - 11,2016。视图:谷歌学术搜索
18. e . Mejia-Roa d . Tabas-Madrid j . Setoain c·加西亚,f . Tirado公元Pascual-Montano,“NMF-mGPU:非负矩阵分解在multi-GPU系统”,BMC生物信息学,16卷,页1 - 2015。视图:出版商的网站|谷歌学术搜索
19. h . c . Liu Yang j .风扇l .他和y王,“分布式非负矩阵分解为网络级二元数据分析在mapreduce,”19国际会议的程序在万维网上,WWW 2010,m . Rappa p·琼斯,j . Freire, s . Chakrabarti Eds。ACM,页681 - 690年,罗利数控,美国,2010年。视图:谷歌学术搜索
20. h .江y, z俏,K.-C。李、w·罗和J.-L。Gaudiot”,加速multi-GPU mapreduce框架系统,”集群计算,17卷,不。2、293 - 301年,2014页。视图:出版商的网站|谷歌学术搜索
21. 郭t高,y, b . Zhang et al .,“节约内存和skew-tolerant mapreduce MPI超级计算系统”IEEE并行和分布式系统没有,卷。31日。12日,第2748 - 2734页,2020年。视图:出版商的网站|谷歌学术搜索
22. m .中士m . Dagrada p . Carribault j . Jaeger m . Perache和g . Papaure“有效沟通/计算重叠与MPI + OpenMP运行时合作,”Euro-Par 2018:并行处理- 24日国际会议上并行和分布式计算,第27 - 31 8月,2018年,意大利都灵,课堂讲稿在计算机科学m . Aldinucci l . Padovani, m . Torquati Eds。,卷。11014, pp. 560–572, Springer, Berlin, Germany, 2018.视图:谷歌学术搜索
23. j·a·斯图亚特·j·d·欧文斯,“Multi-GPU mapreduce GPU集群”25日IEEE国际研讨会上并行计算和分布式处理,IPDPS 2011IEEE,页1068 - 1079年,安克雷奇,正义与发展党,美国,2011。视图:谷歌学术搜索
24. 罗n .关道,z, b .元,“在线非负矩阵分解与鲁棒随机近似,”IEEE反式。神经网络学习。系统。,23卷,不。7,1087 - 1099年,2012页。视图:谷歌学术搜索
25. d, l, m . Lv h·史和g·陈,“分层检测和跟踪在线NMF主题层次结构在文本流,”模式识别卷,76年,第214 - 203页,2018年。视图:出版商的网站|谷歌学术搜索
26. n . Halko p·g . Martinsson和j·a . Tropp“发现与随机性结构:概率算法构造近似矩阵分解,“暹罗审查,53卷,不。2、217 - 288年,2011页。视图:出版商的网站|谷歌学术搜索
27. m·珀和g Sapiro压缩非负矩阵分解是快速和准确,”IEEE信号处理,卷64,不。9日,第2283 - 2269页,2016年。视图:出版商的网站|谷歌学术搜索
28. a . Janecek s s Grotthoff, w . n .匪徒libNMF-a库为非负矩阵分解,“计算和信息,30卷,不。2、205 - 224年,2011页。视图:谷歌学术搜索
29. n·洛佩斯和b·里贝罗”使用图形处理单元,非负矩阵分解实现”智能数据工程与自动化学习-理想2010,11日国际会议,佩斯利,英国,2010年9月1 - 3日。程序,在计算机科学课堂讲稿查尔斯c Fyfe p .天奴,d . et al .,。,卷。6283,pp. 275–283, Springer, Berlin, Germany, 2010.视图:谷歌学术搜索
30. 巴腾堡蛋糕和d·韦塞尔“加速非负矩阵分解的音频源分离多核和许多核心架构,”学报》国际社会对音乐信息检索会议10日ISMIR 2009年,科比国际会议中心吉井,k Hirata、g . Tzanetakis和k, Eds。,pp. 501–506, International Society for Music Information Retrieval, Kobe, Japan, 2009.视图:谷歌学术搜索
31. l . b . Tang Bobelin h .他,“非负矩阵分解的并行算法基于混合MPI和OpenMP编程模型,”计算机科学,44卷,不。3,51-54,2017页。视图:谷歌学术搜索
32. z太阳、t·李和n . Rishe“大规模矩阵分解使用mapreduce,”ICDMW 2010年,第十届IEEE国际会议数据挖掘研讨会w .风扇,w•许g . i韦伯et al .,。,pp. 1242–1248, IEEE Computer Society, Sydney, Australia, 2010.视图:谷歌学术搜索
33. l . b . Tang康、y .夏和l .张“GPU-accelerated大规模使用火花,非负矩阵分解”协同计算:网络、应用程序和Worksharing-14th EAI国际会议,CollaborateCom 2018年,上海,中国,2018年,12月1 - 3,程序,计算机科学研究所的课堂讲稿,社会信息和通信工程殷,h·高,x, y,和m·伊克巴尔,Eds。,卷。268,pp. 189–201, Springer, Berlin, Germany, 2018.视图:谷歌学术搜索
34. Kwon和h秋,“可伸缩co-clustering算法”算法和并行处理架构,国际会议10日ICA3PP 2010年釜山,韩国,可能研讨会,2010。程序。第一部分,在计算机科学课堂讲稿c .许,l·t·杨j . h .公园和美国唷,Eds。,卷。6081, pp. 32–43, Springer, Berlin, Germany, 2010.视图:谷歌学术搜索
35. 张y, z . Liu e . y . Chang和m .太阳”PLDA +:平行潜在狄利克雷分配数据放置和管道处理,”ACM反式。智能。系统。抛光工艺。,卷2,不。3,1-26,2011页。视图:出版商的网站|谷歌学术搜索
36. 大肠Karydi和k . g . Margaritis“多线程实现边坡的协同过滤算法,”人工智能应用和创新——8日联合会WG 12.5国际会议,2012年AIAI哈尔基季基上,是希腊,研究,2012年9月,我一部分,联合会信息和通信技术的进步l . s . Iliadis、i Maglogiannis和h·帕帕多普洛斯Eds。卷,381年,页117 - 125,施普林格,柏林,德国,2012年。视图:谷歌学术搜索
37. c . h . Yu谢长廷、s . Si和i . s . Dhillon”可伸缩坐标下降为推荐系统并行矩阵分解方法,”12日IEEE国际会议上的数据挖掘,ICDM 2012m·j·海岬,a .摘要j . x,高堡,g . i .韦伯和吴x, Eds。,页765 - 774,IEEE计算机协会,布鲁塞尔,比利时,2012年。视图:谷歌学术搜索
38. k·加藤和t . Hosino多个图形处理器,再解决问题”学报第十届IEEE /集群ACM国际会议上,云计算和网格计算,CCGrid 2010年,2010年5月17日—20日,页769 - 773,IEEE计算机协会,墨尔本,维多利亚,澳大利亚,2010年。视图:谷歌学术搜索
39. 刘y z . Wang, s .赵”multi-GPU平台上高效的并行协同过滤算法,”《华尔街日报》的超级计算,卷72,不。6,2080 - 2094年,2016页。视图:出版商的网站|谷歌学术搜索
40. j .江陆j . g . Zhang, g .长,“扩大基于项目协同过滤推荐算法基于hadoop,”2011年世界大会服务,服务,页490 - 497,IEEE计算机协会,华盛顿特区,2011年美国。视图:谷歌学术搜索
41. s . Schelter c·博登,诉Markl“可伸缩的相似性社区和mapreduce方法,”第六届ACM会议推荐系统,RecSys 12p·坎宁安,n . j·赫尔利的家伙,和s . s . Anand, Eds。ACM,页163 - 170年,都柏林,爱尔兰,2012。视图:谷歌学术搜索
42. 答:纳斯利瓦斯塔瓦,和n . p . k . Katta“分布式可扩展的协同过滤算法,”Euro-Par 2011平行Processing-17th国际会议,2011年Euro-Par,波尔多,法国,2011年9月29日8月2日,第一部分,在计算机科学课堂讲稿、大肠Jeannot r . Namyst Eds和j .罗马。,卷。6852,pp. 353–365, Springer, Berlin, Germany, 2011.视图:谷歌学术搜索
43. 大肠Karydi和k . g . Margaritis坡一个协同过滤算法的并行实现,”学报16泛希腊信息学大会,PCI 2012,页174 - 179,IEEE计算机协会,2012年希腊、比雷埃夫斯。视图:谷歌学术搜索
44. y科伦、r·贝尔和c . Volinsky“推荐系统,矩阵分解技术”电脑,42卷,不。8日,30-37,2009页。视图:出版商的网站|谷歌学术搜索
45. 锣,h .你们,戴y”结合奇异值分解和基于项目的协同过滤推荐系统,”程序的第二国际研讨会知识发现和数据挖掘,WKDD 2009,页769 - 772,IEEE计算机协会,莫斯科,俄罗斯,2009。视图:谷歌学术搜索
46. h . Polat和w·杜SVD-based协同过滤与隐私,”学报2005年ACM研讨会上应用计算(囊)h·哈达德,l . m . Liebrock a . Omicini和r·l·温赖特,Eds。ACM,页791 - 795年,圣达菲,海里,美国,2005。视图:谷歌学术搜索
47. k·戈德堡,t·罗德·d·古普塔,c·珀金斯”Eigentaste:一个常数时间协同过滤算法,”信息检索,4卷,不。2、133 - 151年,2001页。视图:出版商的网站|谷歌学术搜索
48. r . Salakhutdinov和a . Mnih“概率矩阵分解,”神经信息处理系统20的进步,美国21年会上神经信息处理系统j·c·普拉特·d·科勒,y歌手,和s . t . Roweis, Eds。,pp. 1257–1264, Curran Associates, Inc., Vancouver, British Columbia, Canada, 2007.视图:谷歌学术搜索
49. n . Thai-Nghe l . Drumond t·霍法,a . Nanopoulos和l . Schmidt-Thieme”矩阵和张量分解预测学生的表现,”CSEDU 2011 -第三届国际会议的程序在计算机支持的教育a . Verbraeck, m . Helfert j . Cordeiro和b . Shishkov, Eds。,卷。1,pp. 69–78, SciTePress, Noordwijkerhout, Netherlands, 2011.视图:谷歌学术搜索
50. c . Boutsidis和大肠Gallopoulos”,基于奇异值分解的初始化:非负矩阵分解的先机,“模式识别第41卷。。4、1350 - 1362年,2008页。视图:出版商的网站|谷歌学术搜索
51. j。深色,p . Tamayo, t·r·戈卢布,j . p . Mesirov”Metagenes和分子模式发现使用矩阵分解,“美国国家科学院院刊》上,卷101,不。12日,第4169 - 4164页,2004年。视图:出版商的网站|谷歌学术搜索

版权

版权©2021 Bing唐等。这是一个开放的分布式下文章知识共享归属许可,它允许无限制的使用、分配和复制在任何媒介,提供最初的工作是正确引用。