蘇曉云，祝永志

(曲阜師范大學(xué) 信息科學(xué)與工程學(xué)院，山東 日照 276826)

0 引 言

在互聯(lián)網(wǎng)和信息技術(shù)飛速發(fā)展的背景下，網(wǎng)絡(luò)中的數(shù)據(jù)呈現(xiàn)爆炸性增長(zhǎng)的趨勢(shì)，同時(shí)也存在大量冗余，如何從這些過(guò)量數(shù)據(jù)中高效準(zhǔn)確地提取出所需信息成為當(dāng)前亟待解決的難題。推薦系統(tǒng)正是解決這一難題的重要手段。

推薦系統(tǒng)[1]旨在為用戶提供個(gè)性化的產(chǎn)品或服務(wù)推薦，通過(guò)處理日益增多的過(guò)載信息來(lái)改善當(dāng)前難以從大量冗雜數(shù)據(jù)中檢索有效信息的狀況，從而提供個(gè)性化服務(wù)。早期研究人員就開(kāi)始關(guān)注明確依賴評(píng)級(jí)結(jié)構(gòu)的推薦問(wèn)題[2]，基于項(xiàng)目間或項(xiàng)目與用戶間交互的相關(guān)信息來(lái)對(duì)用戶興趣進(jìn)行預(yù)測(cè)，進(jìn)而向特定的用戶推薦最適合的項(xiàng)目，以生成個(gè)性化推薦。

1 相關(guān)研究

推薦算法是推薦系統(tǒng)的核心，協(xié)同過(guò)濾[3]是推薦算法中最流行的方法，它從用戶行為中收集大量的數(shù)據(jù)來(lái)進(jìn)行預(yù)測(cè)，依賴于用戶和項(xiàng)目之間的關(guān)系；混合推薦算法是指綜合不同推薦算法的優(yōu)勢(shì)從而提高推薦算法準(zhǔn)確性的一種推薦方法。

近年來(lái)，國(guó)內(nèi)外研究人員對(duì)推薦算法的研究呈現(xiàn)出多樣化的趨勢(shì)。如文獻(xiàn)[4]在傳統(tǒng)矩陣分解模型SVD的基礎(chǔ)上提出了最小二乘ALS算法；文獻(xiàn)[5]將協(xié)同過(guò)濾應(yīng)用到Spark平臺(tái)上，實(shí)現(xiàn)了算法并行化；文獻(xiàn)[6]基于用戶相似度定義了一種社交網(wǎng)絡(luò)中的屬性相似度，改進(jìn)了協(xié)同過(guò)濾算法；文獻(xiàn)[7]提出了一種基于用戶行為特征的動(dòng)態(tài)加權(quán)混合推薦算法，有效降低了推薦的誤差，提高了推薦精度。

文中將基于項(xiàng)目的協(xié)同過(guò)濾推薦算法(ItemBase CF)與基于矩陣分解的最小二乘法(ALS)進(jìn)行動(dòng)態(tài)加權(quán)混合，并將該混合算法在Spark平臺(tái)上進(jìn)行實(shí)現(xiàn)，以提高算法的并行性和擴(kuò)展性，以及推薦準(zhǔn)確性。

2 協(xié)同過(guò)濾推薦算法

2.1 ItemBase協(xié)同過(guò)濾推薦算法

2.1.1 相似度計(jì)算

ItemBase CF根據(jù)項(xiàng)目間的相似性，對(duì)于給定的某個(gè)用戶根據(jù)其歷史行為信息，將相似度最高的物品推薦給用戶[8]。計(jì)算物品之間相似度的方法[9]主要有：

(1)余弦相似度。

(1)

(2)修正的余弦相似度。

(2)

(3)Pearson相關(guān)性相似度。

(3)

2.1.2 評(píng)分預(yù)測(cè)

在ItemBase CF中采用基于項(xiàng)目均值的加權(quán)平均值來(lái)計(jì)算預(yù)測(cè)評(píng)分[10]，公式如下：

(4)

ItemBase CF通過(guò)計(jì)算項(xiàng)目間的相似度，將相似度較高的前k個(gè)項(xiàng)目作為該項(xiàng)目的近鄰集合[11]，通過(guò)調(diào)整k值的大小可以改善推薦結(jié)果的精確度。

2.2 基于ALS的協(xié)同過(guò)濾推薦算法

基于矩陣分解的ALS協(xié)同過(guò)濾推薦算法[12]的原理是通過(guò)最小化Frobenius損失函數(shù)找到兩個(gè)低秩矩陣U、V來(lái)最大程度逼近原矩陣R，即：

(5)

其中，Rm×n為原始評(píng)分矩陣；Um×d為用戶特征矩陣；Vd×n為項(xiàng)目特征矩陣，d?min(m,n)。

Frobenius損失函數(shù)如下：

(6)

為防止過(guò)擬合問(wèn)題，加入正則化參數(shù)，如下：

(7)

在求解過(guò)程中，通過(guò)交替迭代的方法，先固定V,將L(U,V)對(duì)ui求偏導(dǎo)，得到：

ui=(VTV+λI)-1VTri

(8)

同理，對(duì)vj求偏導(dǎo)得到：

vj=(UTU+λI)-1UTrj

(9)

式8、式9中，ri表示由用戶i的評(píng)分組成的向量；rj表示由項(xiàng)目j組成的評(píng)分向量；I表示d×d的單位矩陣。

在上述過(guò)程中不斷迭代，直到RMSE值最小或達(dá)到最大迭代次數(shù)[13]為止，將迭代產(chǎn)生的特征向量相乘得到R'=UVT。

3 混合協(xié)同過(guò)濾推薦算法IACF

3.1 由單機(jī)轉(zhuǎn)向Spark分布式平臺(tái)

傳統(tǒng)的單機(jī)環(huán)境目前已不能滿足大數(shù)據(jù)日益增長(zhǎng)的需求，在運(yùn)行具有較高復(fù)雜性的推薦算法時(shí)，實(shí)際效率是差強(qiáng)人意的。利用分布式平臺(tái)將規(guī)模較大較復(fù)雜的作業(yè)分配給不同的節(jié)點(diǎn)，能夠充分利用其存儲(chǔ)和計(jì)算性能。

Spark分布式平臺(tái)是基于內(nèi)存的通用并行大數(shù)據(jù)計(jì)算引擎，在迭代速度上優(yōu)于MapReduce[14]，通過(guò)彈性分布式數(shù)據(jù)集(RDD)進(jìn)行數(shù)據(jù)操作,將算法流程中的任何一個(gè)點(diǎn)映射到集群節(jié)點(diǎn)的內(nèi)存中，后續(xù)過(guò)程不必反復(fù)從磁盤(pán)中讀取數(shù)據(jù)，適用于多次迭代算法[15]。

Spark的工作原理如圖1所示。

圖1 Spark工作原理

3.2 混合推薦原理

基于項(xiàng)目的協(xié)同過(guò)濾算法與基于矩陣分解的ALS算法各有其優(yōu)勢(shì)，文中采用動(dòng)態(tài)加權(quán)的方式將兩種算法的預(yù)測(cè)結(jié)果進(jìn)行混合，得到混合協(xié)同過(guò)濾推薦算法IACF(ItemBase_ALS collaborative filter)。該算法的主要原理是根據(jù)加權(quán)公式將ItemBase CF的評(píng)分Iui和ALS算法的評(píng)分Aui進(jìn)行混合，得到最終預(yù)測(cè)評(píng)分Rui，加權(quán)公式如下：

Rui=λIui+(1-λ)Aui

(10)

其中，λ是加權(quán)因子，其取值會(huì)影響最終混合結(jié)果的精確性。

基于項(xiàng)目的協(xié)同過(guò)濾算法與項(xiàng)目近鄰的選取有關(guān)；ALS算法與迭代次數(shù)、隱含特征因子的個(gè)數(shù)及正則項(xiàng)系數(shù)lambda有關(guān)。通過(guò)多次實(shí)驗(yàn)驗(yàn)證得知，隱含特征因子對(duì)算法準(zhǔn)確性影響較大，因此文中選擇隱含特征因子作為關(guān)鍵影響因素，固定迭代次數(shù)和lambda。在混合算法中，通過(guò)調(diào)整項(xiàng)目近鄰n和隱藏特征因子r的取值來(lái)確定λ，如下：

(11)

(12)

3.3 算法描述

ItemBase CF和ALS混合協(xié)同過(guò)濾推薦算法(IACF)描述如下：

輸入：用戶-項(xiàng)目評(píng)分矩陣；

輸出：預(yù)測(cè)結(jié)果評(píng)分。

(1)利用修正的余弦相似度公式(式2)計(jì)算項(xiàng)目間相似度；

(2)根據(jù)步驟1中的結(jié)果選擇相似度最高的k個(gè)項(xiàng)目作為項(xiàng)目近鄰，通過(guò)評(píng)分預(yù)測(cè)公式(式4)進(jìn)行預(yù)測(cè)，得出預(yù)測(cè)結(jié)果Iui；

(3)調(diào)整隱藏特征r的個(gè)數(shù)，選擇ALS算法進(jìn)行預(yù)測(cè)，得出預(yù)測(cè)結(jié)果Aui；

(4)根據(jù)式11確定λ；

(5)根據(jù)加權(quán)公式(式10)將步驟2、3的結(jié)果進(jìn)行混合，得出最終預(yù)測(cè)結(jié)果。

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

4.1 實(shí)驗(yàn)數(shù)據(jù)與環(huán)境

采用Grouplens提供的MovieLens數(shù)據(jù)集中約700位用戶對(duì)9 000部電影的最新評(píng)分?jǐn)?shù)據(jù)集，約10萬(wàn)條，評(píng)分范圍為1～5分，分值越高表示用戶對(duì)該電影的喜好程度越高。評(píng)分?jǐn)?shù)據(jù)集格式如表1所示。

表1 評(píng)分?jǐn)?shù)據(jù)表格式

實(shí)驗(yàn)環(huán)境是在VirtureBox虛擬機(jī)上架設(shè)的三個(gè)節(jié)點(diǎn)的Hadoop集群，系統(tǒng)為Ubuntu16.04，Spark為2.1.0版本運(yùn)行在Hadoop集群上，其依賴于Yarn，HDFS作為存儲(chǔ)平臺(tái)，采用Python語(yǔ)言進(jìn)行實(shí)驗(yàn)編程。

4.2 評(píng)價(jià)指標(biāo)

預(yù)測(cè)評(píng)分的精準(zhǔn)度主要通過(guò)均方根誤差(RMSE)和平均絕對(duì)誤差(MAE)兩種指標(biāo)體現(xiàn)，兩者的值越小，表示預(yù)測(cè)準(zhǔn)確度越高。若pui表示預(yù)測(cè)評(píng)分，rui表示實(shí)際評(píng)分，N表示測(cè)試集中評(píng)分個(gè)數(shù)，有如下定義：

(13)

(14)

4.3 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

實(shí)驗(yàn)首先將評(píng)分?jǐn)?shù)據(jù)集按照8∶2的比例劃分為訓(xùn)練集和測(cè)試集，將訓(xùn)練集用于預(yù)測(cè)評(píng)分，測(cè)試集中的數(shù)據(jù)作為參考來(lái)評(píng)估算法預(yù)測(cè)的準(zhǔn)確性。

設(shè)置兩組實(shí)驗(yàn)，涉及到ALS算法時(shí)按經(jīng)驗(yàn)選取迭代次數(shù)為20進(jìn)行迭代直到收斂，lambda=0.01。

第一組實(shí)驗(yàn)比較傳統(tǒng)的ItemBase CF與混合協(xié)同過(guò)濾算法IACF，固定ALS算法的隱藏特征數(shù)r，改變項(xiàng)目近鄰數(shù)n分別進(jìn)行實(shí)驗(yàn)，結(jié)果如圖2和圖3所示。

圖2 Itembase CF與IACF算法的RMSE變化趨勢(shì)

圖3 Itembase CF與IACF算法的MAE變化趨勢(shì)

從圖中可以看出，傳統(tǒng)ItemBase的RMSE最小值為1.053 7，MAE最小值為0.816 6，其變化趨勢(shì)大致相同，都隨近鄰數(shù)n的增大而減??；而混合算法IACF的RMSE最小值為0.899 0，MAE最小值為0.698 2，二者均大幅度下降，推薦準(zhǔn)確度明顯提高，且與傳統(tǒng)ItemBase算法的變化規(guī)律基本相同，隨近鄰數(shù)n的增加而減小，即λ的值越大，其RMSE和MAE越小，達(dá)到一定程度時(shí)趨于平穩(wěn)。

第二組實(shí)驗(yàn)比較ALS協(xié)同過(guò)濾算法與混合協(xié)同過(guò)濾算法IACF，通過(guò)確定的項(xiàng)目近鄰數(shù)n，調(diào)整隱藏特征因子r來(lái)分別進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖4和圖5所示。

圖4 ALS與IACF算法的RMSE變化趨勢(shì)

圖5 ALS與IACF算法的MAE變化趨勢(shì)

從圖中可以看出，r=12時(shí)，傳統(tǒng)ALS算法RMSE最小值為0.915 6，r=8時(shí)，MAE最小值為0.706；融合了ItemBase的IACF算法，其RMSE和MAE值均有所減小，RMSE范圍在0.899 0～0.905 0之間，MAE值保持在0.697 6～0.705 9間，推薦準(zhǔn)確度明顯提高。

綜合兩組實(shí)驗(yàn)結(jié)果，混合協(xié)同過(guò)濾算法IACF在Spark上的實(shí)現(xiàn)保證了算法的可擴(kuò)展性，動(dòng)態(tài)加權(quán)混合提高了算法推薦的準(zhǔn)確性。

5 結(jié)束語(yǔ)

文中實(shí)現(xiàn)了由單機(jī)環(huán)境到分布式平臺(tái)的轉(zhuǎn)變，并提出了一種混合協(xié)同過(guò)濾推薦算法IACF。該算法將ItemBase CF和ALS算法根據(jù)各自特點(diǎn)選取不同特征組合構(gòu)造加權(quán)公式進(jìn)行融合，通過(guò)調(diào)節(jié)不同參數(shù)來(lái)動(dòng)態(tài)改變不同維度的權(quán)重，從而突出某一算法的特性，使得改進(jìn)后的IACF能夠滿足不同需求。實(shí)驗(yàn)結(jié)果表明，IACF算法在分布式平臺(tái)Spark上的實(shí)現(xiàn)提高了算法的并行性與可擴(kuò)展性，同時(shí)在評(píng)分預(yù)測(cè)及推薦精度上也有所改善。