盛 偉， 余 英， 王保云

(云南師范大學(xué) 信息學(xué)院， 云南 昆明 650500)

基于相似用戶索引和ALS矩陣分解的推薦算法研究

盛 偉， 余 英， 王保云

(云南師范大學(xué) 信息學(xué)院， 云南 昆明 650500)

針對(duì)交替最小二乘法(ALS)在處理大數(shù)據(jù)集時(shí)所面臨的處理速度和計(jì)算資源問題，提出了基于相似用戶索引的分布式矩陣分解推薦算法。首先算法基于用戶的評(píng)分行為找到用戶之間的最近鄰，然后使用Spark平臺(tái)運(yùn)行提出的算法，并產(chǎn)生推薦。在GroupLens網(wǎng)站上提供的MovieLens數(shù)據(jù)集上進(jìn)行仿真實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明，提出的算法能夠有效解決ALS對(duì)于大數(shù)據(jù)集運(yùn)行效率低及在云環(huán)境中可擴(kuò)展性較差的問題。

交替最小二乘法； 最近鄰； 推薦算法； Spark

個(gè)性化推薦系統(tǒng)如同一個(gè)信息過濾器，只把有用的信息提供給用戶，有效解決了信息過載的問題。協(xié)同過濾算法[1]是最成功的個(gè)性化推薦技術(shù)之一，被廣泛應(yīng)用于很多領(lǐng)域。然而，在現(xiàn)實(shí)生活中用戶和物品的數(shù)量龐大，而消費(fèi)者通常只對(duì)一小部分物品進(jìn)行評(píng)分，造成了評(píng)分矩陣嚴(yán)重稀疏，這導(dǎo)致傳統(tǒng)協(xié)同過濾算法可以利用的數(shù)據(jù)非常有限，推薦精度較差。在用戶和物品不斷增加的同時(shí)，評(píng)分矩陣的維度也變得極高，這使得傳統(tǒng)協(xié)同過濾算法的計(jì)算復(fù)雜度急劇增加，由此產(chǎn)生了可擴(kuò)展性較差的問題。針對(duì)數(shù)據(jù)稀疏性問題，李紅梅等[2]提出利用LSH快速獲取目標(biāo)用戶的近鄰用戶集合，然后采用加權(quán)方法來預(yù)測(cè)用戶評(píng)分并產(chǎn)生推薦；LIKA B等[3]提出了分類算法與相似度技術(shù)相結(jié)合的模型。針對(duì)可擴(kuò)展性較差的問題，孫天昊等[4]在分布式平臺(tái)下，提出改進(jìn)聚類協(xié)同過濾推薦算法。近年來，隱語義模型(Latent Factor Model，LFM)[5]受到越來越多的關(guān)注，矩陣分解技術(shù)是其中最常用的一種方法，這是一類有效解決數(shù)據(jù)稀疏性問題的推薦算法，基于它的推薦模型獲得了Netflix Prize推薦比賽冠軍。此后，該方法被應(yīng)用于更多的推薦系統(tǒng)研究中[6-7]。在眾多基于矩陣分解的方法中，交替最小二乘(Alternating Least Squares，ALS)算法最為流行，它非常容易實(shí)現(xiàn)并行化計(jì)算?？墒?，隨著用戶數(shù)量的增加，ALS需要計(jì)算更多用戶的評(píng)分集信息，計(jì)算量會(huì)迅速增大，ALS在大數(shù)據(jù)集下的可擴(kuò)展性更加不理想。

大數(shù)據(jù)計(jì)算平臺(tái)的更新及數(shù)據(jù)的增長(zhǎng)進(jìn)一步促進(jìn)了推薦系統(tǒng)的快速發(fā)展。Spark是一個(gè)高效的分布式計(jì)算平臺(tái)，不同于需要過多的文件讀取操作的MapReduce，可以將任務(wù)中間輸出結(jié)果保存在內(nèi)存中，因此Spark能更好地適用于數(shù)據(jù)挖掘、矩陣分解等需要迭代的算法。

本文提出一種基于相似用戶索引的分布式矩陣分解推薦算法，結(jié)合分布式計(jì)算特點(diǎn)，利用位置敏感哈希(Locality Sensitive Hashing，LSH)處理高維數(shù)據(jù)的良好特性來快速尋找用戶之間的近鄰集合，并將其植入到ALS矩陣分解推薦技術(shù)中，降低了計(jì)算復(fù)雜度，改善了算法可擴(kuò)展性較差的問題并且在一定程度上提高了推薦精度。

1 基于相似用戶索引和ALS矩陣分解的推薦算法

首先將己知用戶-物品評(píng)分?jǐn)?shù)據(jù)集分為訓(xùn)練集T1和測(cè)試集T2，訓(xùn)練集用來學(xué)習(xí)矩陣特征并構(gòu)建LSH模型，測(cè)試集用來評(píng)價(jià)推薦結(jié)果。本文提出的算法分為兩個(gè)階段進(jìn)行，分別是LSH的相似用戶索引構(gòu)建和基于ALS的矩陣分解推薦。以上階段均在Spark集群下進(jìn)行分布式計(jì)算，算法流程如圖1所示。

圖1 基于相似用戶索引和ALS矩陣分解的推薦算法流程圖

Spark是UC Berkeley AMP Lab開源的通用并行計(jì)算框架。Spark立足于內(nèi)存計(jì)算，提供了批處理、實(shí)時(shí)數(shù)據(jù)處理、機(jī)器學(xué)習(xí)以及圖算法等一站式服務(wù)，非常適合于各種迭代算法和交互式數(shù)據(jù)挖掘。Spark中使用了彈性分布式數(shù)據(jù)集(Resilient Distributed Datasets，RDD)[8]抽象分布式計(jì)算，即使用RDD以及對(duì)應(yīng)的相關(guān)操作來執(zhí)行分布式計(jì)算；并且基于RDD之間的依賴關(guān)系組成Lineage以及CheckPoint等機(jī)制來保證整個(gè)分布式計(jì)算的容錯(cuò)性。

Spark運(yùn)行架構(gòu)如圖2所示，用戶將任務(wù)提交給Driver，Driver將任務(wù)分發(fā)到所有的Worker節(jié)點(diǎn)。Worker節(jié)點(diǎn)根據(jù)Driver提交過來的任務(wù)，算出位于本地的那部分?jǐn)?shù)據(jù)，將數(shù)據(jù)以RDD的形式保存到內(nèi)存中，然后對(duì)RDD進(jìn)行接下來的計(jì)算。用戶提交的任務(wù)一般在Cluster Manager中運(yùn)行，目前Spark支持Standalone、Mesos和YARN等不同的Cluster Manager，本文選擇的是Standalone模式。

圖2 Spark運(yùn)行架構(gòu)圖

1.1 基于LSH的相似用戶索引構(gòu)建

建立相似用戶索引，不僅可以過濾掉與目標(biāo)用戶不相關(guān)的評(píng)分信息，還降低了推薦算法需要計(jì)算的評(píng)分矩陣維度。因此，基于相似用戶索引的推薦算法能夠快速為用戶產(chǎn)生推薦。

針對(duì)上述問題，本文引入LSH[9-10]對(duì)相似用戶建立索引。LSH是當(dāng)前最流行的近似最近鄰快速查找技術(shù)之一，它使用哈希的方法把數(shù)據(jù)從原空間哈希到一個(gè)新的空間中，如果數(shù)據(jù)在原空間中相似，那么哈希到新的空間中的數(shù)據(jù)也保持一定的相似性。LSH通過原始評(píng)分矩陣，能夠?qū)⒃u(píng)分行為相似的用戶以一定的概率散列到同一個(gè)桶中。

定義(位置敏感哈希) 存在函數(shù)族H={h:S→U}，對(duì)于任意的數(shù)據(jù)點(diǎn)p,q∈S，都有：

若p∈B(q,r1)，則Pr[hi(p)=hi(q)]>p1；

若p∈B(q,r2)，則Pr[hi(p)=hi(q)]>p2；

如果滿足條件p1>p2和r1

對(duì)評(píng)分?jǐn)?shù)據(jù)處理之前，首先需要將評(píng)分?jǐn)?shù)據(jù)向量化。通常評(píng)分?jǐn)?shù)據(jù)向量化是對(duì)用戶評(píng)分行為的提取，通過相關(guān)計(jì)算將評(píng)分?jǐn)?shù)據(jù)轉(zhuǎn)化成對(duì)應(yīng)的高維向量。常用的向量度量方式有：歐式距離、杰卡德距離以及余弦距離等。在這些度量方式中余弦距離在實(shí)際應(yīng)用中有較好的效果。

在余弦距離的度量下，Chairkar M S[11]于2002年提出了超平面的思想，通過隨機(jī)的超平面將原始數(shù)據(jù)空間進(jìn)行劃分，其中每一個(gè)空間構(gòu)成一個(gè)散列桶，而位于每個(gè)桶內(nèi)的數(shù)據(jù)被認(rèn)為具有很大的相似性。因此我們選用超平面的思想方法對(duì)評(píng)分?jǐn)?shù)據(jù)進(jìn)行哈希。Chairkar M S設(shè)計(jì)了一族哈希函數(shù)，使得落入平面一側(cè)的向量被哈希為1，另一側(cè)被哈希成為0，哈希函數(shù)如公式(1)所示：

(1)

其中v是待哈希的向量，u是隨機(jī)生成的向量。

當(dāng)數(shù)據(jù)量變得很大時(shí)，用戶評(píng)分行為向量的維度也變得很高，單機(jī)模式的LSH構(gòu)建會(huì)因?yàn)閮?nèi)存的限制而變得很慢，甚至無法繼續(xù)運(yùn)行。本文利用Spark平臺(tái)將LSH構(gòu)建過程分布化和并行化，以適應(yīng)海量高維數(shù)據(jù)的計(jì)算需求?；赟park的LSH索引模型構(gòu)造算法描述如下：

輸入：評(píng)分?jǐn)?shù)據(jù)T1，哈希函數(shù)數(shù)目K，哈希表數(shù)L；

輸出：LSH索引模型，

① var sc=new sparkContext( )，

② val data=sc.textFile("...",numPartion)，

③ 數(shù)據(jù)經(jīng)過map生成sparseVectorData:RDD[user_id,SparseVector],SparseVector是序列，

④ Hasher(K*L,seed)隨機(jī)生成K*L個(gè)哈希函數(shù)Hash(u:SparseVector)利用隨機(jī)生成的哈希函數(shù)和公式(1)對(duì)每個(gè)向量生成hash signature (e.g.11110010)，

⑤ 保存哈希過的向量hashTables：RDD[((hashTableId,hashValue),user_id)]，

⑥ 輸出LSH模型。

代碼中：第①—②行初始化SparkContext，從HDFS中讀入數(shù)據(jù)；第③行根據(jù)原始評(píng)分?jǐn)?shù)據(jù)生成每個(gè)用戶對(duì)所有已評(píng)分項(xiàng)目的評(píng)分記錄向量；第④—⑤行利用隨機(jī)超平面的思想對(duì)原始數(shù)據(jù)進(jìn)行劃分。

1.2 基于ALS的矩陣分解推薦算法

在協(xié)同過濾推薦系統(tǒng)中，輸入數(shù)據(jù)可以用一個(gè)m行n列的評(píng)分矩陣T來表示，本文稱之為User-Item矩陣，其中m表示用戶數(shù)目，n表示物品數(shù)目。真實(shí)生活中消費(fèi)者產(chǎn)生的評(píng)分?jǐn)?shù)據(jù)非常少，造成User-Item矩陣極為稀疏。矩陣分解的核心思想是把稀疏的User-Item評(píng)分矩陣分解為兩個(gè)低維度的矩陣P和Q，用一個(gè)重構(gòu)的低秩預(yù)測(cè)矩陣X=PQT來逼近原來的評(píng)分矩陣，逼近的目標(biāo)是使預(yù)測(cè)矩陣和原始矩陣之間誤差的平方最小，其中P為m×d(d表示特征個(gè)數(shù)，也即為低維度矩陣的維度)的用戶特征向量矩陣，Q為n×d的物品特征向量矩陣。預(yù)測(cè)方法如公式(2)所示：

(2)

其中pu和qi分別為用戶u和物品i的特征向量，rui為用戶u對(duì)物品i的預(yù)測(cè)評(píng)分。當(dāng)矩陣中含有大量空值時(shí)，此模型容易導(dǎo)致過擬合問題。許多研究者建議采用一個(gè)正則化[12]模型來避免過擬合問題。其需要優(yōu)化的函數(shù)如式(3)：

(‖pu‖2+‖qi‖2)，

治療前，體表光學(xué)檢測(cè)(OSMS)誤差X方向平移和Y方向旋轉(zhuǎn)與治療前CBCT驗(yàn)證誤差比較，差異無統(tǒng)計(jì)學(xué)意義，t=1.48,P=0.14；t=0.72,P=0.47。治療前，體表光學(xué)檢測(cè)誤差Y方向平移、Z方向平移、X方向旋轉(zhuǎn)和Z方向旋轉(zhuǎn)與治療前CBCT驗(yàn)證誤差比較差異有統(tǒng)計(jì)學(xué)意義，t值分別為4.97、2.13、7.05和2.29，P值分別為0、0.03、0和0.02。

(3)

其中λ是正則化系數(shù)，K代表已有評(píng)分記錄，rui為用戶u對(duì)項(xiàng)目i的真實(shí)評(píng)分。ALS算法是求解上述模型最常用的方法。

ALS算法基本求解思想是固定P求解Q，然后固定Q求解P，重復(fù)交替上述兩步直到算法收斂。ALS算法易于實(shí)現(xiàn)并行化，然而隨著評(píng)分?jǐn)?shù)據(jù)的增加，它需要更多的計(jì)算時(shí)間，大數(shù)據(jù)集下推薦效率不高。因此本文采用LSH和ALS相結(jié)合的算法。對(duì)于評(píng)分矩陣T，可以利用LSH算法對(duì)具有相似評(píng)分記錄的用戶進(jìn)行粗略劃分，得到相應(yīng)的相似用戶評(píng)分?jǐn)?shù)據(jù)。然后為了產(chǎn)生項(xiàng)目推薦結(jié)果，可以利用相似用戶的評(píng)分?jǐn)?shù)據(jù)進(jìn)行ALS推薦。這樣不僅減少了ALS算法的計(jì)算量，改善了算法可擴(kuò)展性較差的問題，也提高了推薦精度。算法描述如下：

輸入：原始評(píng)分矩陣T1，評(píng)分測(cè)試集T2，LSH索引模型LSHModel；

輸出：推薦列表，

① var sc=new sparkContext( )，

② val data=sc.textFile("...",numPartion)，

③ 讀入T2生成TestRatings：RDD[Rating],Rating是序列，

④ LSHModel.getCandidates(TestRatings:RDD[(Int,Int,Double)])生成相似用戶集合U，

⑤ 讀入T1根據(jù)U生成候選集Hratings:RDD[Rating]，

⑥ ALS.train(Hratings,rank,numIter,lambda)對(duì)評(píng)分?jǐn)?shù)據(jù)Hratings進(jìn)行numIter次訓(xùn)練，rank是用戶因子矩陣和項(xiàng)目因子矩陣的維度，lambda是正則化因子，

⑦ recommendProducts(r,i)為用戶r產(chǎn)生i個(gè)初始推薦，

⑧ 輸出推薦列表。

代碼中：第①—②行初始化SparkContext，從HDFS中讀入數(shù)據(jù)；第③行讀取并生成評(píng)分測(cè)試集；第④—⑤行評(píng)分測(cè)試數(shù)據(jù)集通過算法1的LSH模型的LSH映射獲得相似用戶集合，最后生成評(píng)分?jǐn)?shù)據(jù)候選集合。第⑥—⑦行ALS算法訓(xùn)練候選集合生成ALS推薦模型，完成測(cè)試數(shù)據(jù)集的用戶TOP-N推薦。

2 實(shí)驗(yàn)及結(jié)果分析

根據(jù)上述研究，利用4臺(tái)計(jì)算機(jī)搭建Spark分布式集群，其中一臺(tái)計(jì)算機(jī)作為Master節(jié)點(diǎn)，另外3臺(tái)作為Slave節(jié)點(diǎn)負(fù)責(zé)運(yùn)算。每個(gè)節(jié)點(diǎn)內(nèi)存為2 GB，2核，安裝CentOS 6.7操作系統(tǒng)和Spark 1.4.1。程序采用IntelliJ IDEA集成開發(fā)環(huán)境完成。從GroupLens網(wǎng)站(http://www.gouplens.org)下載MovieLens 100 KB和1 MB兩個(gè)不同大小的數(shù)據(jù)集作為本文的數(shù)據(jù)源，其中100 KB數(shù)據(jù)集包含了943個(gè)用戶對(duì)1 682部電影的評(píng)分，共100 000條評(píng)分記錄；1 MB數(shù)據(jù)集包含6 040個(gè)用戶對(duì)3 900部電影的評(píng)分，共1 000 209條評(píng)分記錄。

實(shí)驗(yàn)采用加速比S=L1/Ln衡量同一數(shù)據(jù)集下增加節(jié)點(diǎn)時(shí)本文算法的運(yùn)行效率，其中L1為單個(gè)節(jié)點(diǎn)完成任務(wù)所需的時(shí)間，Ln為n個(gè)節(jié)點(diǎn)完成任務(wù)所需的時(shí)間。實(shí)驗(yàn)過程中，從1個(gè)節(jié)點(diǎn)增加到4個(gè)節(jié)點(diǎn)，分別測(cè)試100 KB和1 MB數(shù)據(jù)集在單機(jī)模式下的運(yùn)行時(shí)間以及在不同規(guī)模Spark集群下的運(yùn)行時(shí)間，獲取其完成運(yùn)算所需時(shí)間L1—L4，繪制加速比曲線圖如圖3所示。

從圖3可以看出，隨著Spark集群節(jié)點(diǎn)數(shù)目的增加，兩組數(shù)據(jù)集的加速比值都在增大，因此增加節(jié)點(diǎn)數(shù)目可以提高算法執(zhí)行效率。100 KB數(shù)據(jù)集的加速比值較小，加速比曲線增長(zhǎng)緩慢，1 MB數(shù)據(jù)集的加速比值較大。針對(duì)同一節(jié)點(diǎn)，數(shù)據(jù)量很小的情況下加速比不明顯，隨著數(shù)據(jù)量增加，加速比曲線提升明顯，可以預(yù)期處理更大規(guī)模數(shù)據(jù)集時(shí)，本文算法執(zhí)行效率會(huì)進(jìn)一步提升。

實(shí)驗(yàn)采用均平方根差RMSE[13]作為本文算法推薦質(zhì)量的評(píng)價(jià)指標(biāo)。RMSE的值越小，表明算法的推薦準(zhǔn)確率越高，其公式為

(4)

其中N為物品數(shù)量，ri為真實(shí)的評(píng)分，pi為預(yù)測(cè)的分?jǐn)?shù)。從100 KB數(shù)據(jù)集中分別選取用戶數(shù)量為100、300、700和943作為4組實(shí)驗(yàn)數(shù)據(jù)(表1)。本文實(shí)現(xiàn)的算法與傳統(tǒng)矩陣分解算法的比較如圖4所示。

表1 4組實(shí)驗(yàn)數(shù)據(jù)量

圖3 加速比曲線圖 圖4 RMSE值

從圖4可看出，隨著用戶數(shù)據(jù)逐漸增大，ALS推薦算法的推薦精度也在逐漸提高，所以ALS算法在處理大規(guī)模數(shù)據(jù)集時(shí)在推薦精度上有顯著優(yōu)勢(shì)。然而，由于數(shù)據(jù)量巨大，ALS算法需要計(jì)算很多不相關(guān)信息，推薦精度還有進(jìn)一步提升的空間。本文算法利用LSH技術(shù)找到用戶最近鄰，過濾掉不相似用戶的評(píng)分信息，在此數(shù)據(jù)集的基礎(chǔ)上再進(jìn)行推薦，在改善ALS算法復(fù)雜度的同時(shí)，推薦結(jié)果也更加精確。

3 結(jié) 語

本文針對(duì)ALS矩陣分解算法存在的計(jì)算開銷大及可擴(kuò)展性較差的問題，結(jié)合Spark分布式計(jì)算和LSH快速處理高維數(shù)據(jù)的特點(diǎn)，提出了基于相似用戶索引的分布式矩陣分解推薦算法。利用LSH找到用戶之間的最近鄰集合，ALS通過這些用戶的評(píng)分?jǐn)?shù)據(jù)重新排列用戶的喜好列表，形成最后的推薦，降低了時(shí)間復(fù)雜度。同時(shí)，算法在大數(shù)據(jù)環(huán)境下具有良好的可擴(kuò)展性。后續(xù)研究將結(jié)合其他用戶信息或者項(xiàng)目信息進(jìn)行更準(zhǔn)確地推薦。

[1] LIU Zhao-bin,QU Wen-yu,LI Hai-tao,et al.A hybrid collaborative filtering recommendation mechanism for P2P networks[J].Future generation computer systems,2010,26(8):1409-1417.

[2] 李紅梅,郝文寧,陳剛.基于改進(jìn)LSH的協(xié)同過濾推薦算法[J].計(jì)算機(jī)科學(xué),2015,42(10):256-261.

[3] LIKA B,KOLOMVATSOS K,HADJIEFTHYMIADES S.Facing the cold start problem in recommender systems[J].Expert Systems with Applications,2014,41(4):2065-2073.

[4] 孫天昊,黎安能,李明,等.基于Hadoop分布式改進(jìn)聚類協(xié)同過濾推薦算法研究[J].計(jì)算機(jī)工程與應(yīng)用,2015,51(15):124-128.

[5] KOREN Y,BELL R,VOLINSKY C.Matrix factorization techniques for recommender systems[J].Computer,2009,42(8):30-37.

[6] JAMALI M,ESTER M.A matrix factorization technique with trust propagation for recommendation in social networks[C]// Proceedings of the fourth ACM conference on Recommender systems.ACM,2010:135-142.

[8] ZAHARIA M,CHOWDHURY M,DAS T,et al.Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing[C]//Proceedings of the 9th USENIX conference on Networked Systems Design and Implementation. USENIX Association,2012:2.

[9] ANDONI A,INDYK P.Near-optimal hashing algorithms for near neighbor problem in high dimensions[C]//Proceedings of the Symposium on the Foundations of Computer Science,2006:459-468.

[10] SLANEY M,CASEY M.Locality-sensitive hashing for finding nearest neighbors [lecture notes][J].IEEE Signal Processing Magazine,2008,25(2):128-131.

[11] CHARIKAR M S.Similarity estimation techniques from rounding algorithms[C]//Proceedings of the thiry-fourth annual ACM symposium on Theory of computing.ACM,2002:380-388.

[12] PATEREK A.Improving regularized singular value decomposition for collaborative filtering[C]//Proceedings of KDD cup and workshop,2007:5-8.

[13] RICCI F,ROKACH L,SHAPIRA B,et al.Recommender systems Handbook[M].Berlin:Springer-Verlag,2011:109.

[責(zé)任編輯：魏 強(qiáng)]

ALS-based matrix factorization recommendation algorithm with similar user index

SHENG Wei, YU Ying, WANG Bao-yun

(School of Information Science and Technology, Yunnan Normal University, Kunming 650500, China)

In order to solve the bottleneck problems of processing speed and resource allocation of Alternating Least Squares (ALS), a distributed parallel matrix factorization recommendation approach with similar user index was proposed. First, the approach found nearest neighbors among the users based on their ratings; Then, Spark was employed to implement the proposed approach, and the recommendation to the user is produced. Simulate experiments in MovieLens datasets provided by GroupLens website show that the proposed algorithm can resolve the issue of low execution efficiency of ALS for large-scale datasets and the worse scalability in clouds.

alternating least squares; nearest neighbors; recommendation algorith; Spark

1673-2944(2016)06-0047-06

2016-05-06

2016-06-13

云南省教育廳科學(xué)研究基金資助項(xiàng)目(2014Y145)

盛偉(1988—)，男，江蘇省豐縣人，云南師范大學(xué)碩士研究生，主要研究方向?yàn)橥扑]系統(tǒng)；[通信作者]余英(1965—)，女，云南省昆明市人，云南師范大學(xué)副教授，碩士生導(dǎo)師，碩士，主要研究方向?yàn)榫W(wǎng)絡(luò)通信；王保云(1977—)，男，云南省玉溪市人，云南師范大學(xué)講師，博士，主要研究方向?yàn)闄C(jī)器學(xué)習(xí)。

TP391.3

A