基于改進(jìn)型協(xié)同過(guò)濾算法的研究

徐志超，單劍鋒

(南京郵電大學(xué) 電子與光學(xué)工程、微電子學(xué)院，江蘇 南京 210046)

0 引 言

互聯(lián)網(wǎng)社會(huì)中，人在社會(huì)生產(chǎn)生活中產(chǎn)生了源源不斷的歷史數(shù)據(jù)。文獻(xiàn)[1]中較為全面地論述了推薦算法在電子商務(wù)中的應(yīng)用，并且分析了推薦策略，同時(shí)指出了當(dāng)前策略的優(yōu)缺點(diǎn)和未來(lái)的研究方向。如何從大量的、復(fù)雜、冗余的歷史數(shù)據(jù)中挖掘出有價(jià)值的數(shù)據(jù)，分析這些數(shù)據(jù)的規(guī)律，對(duì)人的生產(chǎn)和生活做一些預(yù)測(cè)和相應(yīng)的建議，這有利于生產(chǎn)力的提高和為人們提供更好的服務(wù)。相比于傳統(tǒng)的軟件工程，大數(shù)據(jù)、人工智能越來(lái)越被大眾所熟悉[2]。大數(shù)據(jù)的應(yīng)用場(chǎng)景在生活中比比皆是，天貓、淘寶等購(gòu)物網(wǎng)站通過(guò)消費(fèi)者的歷史消費(fèi)數(shù)據(jù)對(duì)用戶(hù)進(jìn)行商品個(gè)性化推薦；學(xué)校圖書(shū)館中，根據(jù)不同讀者的借書(shū)數(shù)據(jù)和讀者的角色進(jìn)行個(gè)性化推薦；淘淘網(wǎng)根據(jù)用戶(hù)的影評(píng)和用戶(hù)的歷史觀看數(shù)據(jù)對(duì)用戶(hù)進(jìn)行推薦；內(nèi)容搜索行業(yè)的今日頭條能夠根據(jù)用戶(hù)的歷史閱覽軌跡實(shí)時(shí)推薦用戶(hù)感興趣的內(nèi)容，這大大提升了頭條的用戶(hù)流量。

目前，主流的推薦算法主要有三種，第一種是基于協(xié)同過(guò)濾的推薦算法，主要包括基于內(nèi)存和基于模型兩種?；趦?nèi)存有包括基于用戶(hù)或商品；基于模型主要利用統(tǒng)計(jì)學(xué)、機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘來(lái)研究[3]。文獻(xiàn)[4]提出的基于協(xié)同過(guò)濾算法的高校圖書(shū)館推薦系統(tǒng)，主要利用專(zhuān)業(yè)、角色、學(xué)歷等多維特征構(gòu)建讀者模型，結(jié)合基于商品評(píng)分的系統(tǒng)過(guò)濾算法，相比于單一的基于商品評(píng)分協(xié)同推薦算法，該算法的有效性、實(shí)用性大大提高。第二種是基于內(nèi)容的推薦算法，主要包括基于TF-IDF文本的推薦算法和基于潛在語(yǔ)義分析的推薦算法，但它們都只能基于歷史的文本信息進(jìn)行挖掘。文獻(xiàn)[5]針對(duì)特征高維問(wèn)題,提出一種基于中心詞擴(kuò)展的TF-IDF特征提取算法,增加了特征節(jié)點(diǎn)的表達(dá)能力,實(shí)現(xiàn)了特征降維。第三種是基于圖結(jié)構(gòu)的推薦算法，文獻(xiàn)[6]提出了一種基于隨機(jī)森林修正的加權(quán)二部圖推薦算法。算法經(jīng)過(guò)改進(jìn)和融合后，提高了推薦的準(zhǔn)確度，解決了基于二部圖網(wǎng)絡(luò)結(jié)構(gòu)的算法中僅考慮用戶(hù)與商品之間關(guān)系、忽略興趣偏好影響的問(wèn)題,從而增強(qiáng)了推薦的可解釋性。另外，協(xié)同過(guò)濾算法也可以和其他經(jīng)典算法相結(jié)合，文獻(xiàn)[7]很好地將遺傳算法與協(xié)同過(guò)濾算法進(jìn)行有效結(jié)合。

在計(jì)算仿真平臺(tái)和工具的選擇上，以MapReduce為主的Hadoop體系和基于內(nèi)存計(jì)算的Spark體系在計(jì)算上變得越來(lái)越重要。

針對(duì)傳統(tǒng)的單機(jī)集中式計(jì)算已無(wú)法滿(mǎn)足推薦系統(tǒng)的實(shí)時(shí)性和擴(kuò)展性要求的問(wèn)題,基于主流的大數(shù)據(jù)平臺(tái)Spark在迭代計(jì)算以及內(nèi)存計(jì)算方面的優(yōu)勢(shì),設(shè)計(jì)了基于項(xiàng)目的協(xié)同過(guò)濾算法在Spark上的并行化方案[8-9]。文獻(xiàn)[10-11]都提出了基于Hadoop的協(xié)同過(guò)濾算法，成功提高了算法的運(yùn)行速度，擴(kuò)大了算法輸入數(shù)據(jù)的規(guī)模。由此可見(jiàn)計(jì)算工具的提升，有助于算法性能的提升。

1 協(xié)同過(guò)濾算法

協(xié)同過(guò)濾算法主要是將與目標(biāo)用戶(hù)具有相似特征的用戶(hù)的商品推薦給目標(biāo)用戶(hù)[12]；或者根據(jù)目標(biāo)用戶(hù)歷史消費(fèi)的商品，推薦相類(lèi)似的商品。前者屬于基于用戶(hù)的推薦算法，后者屬于基于商品的推薦算法。協(xié)同過(guò)濾算法大致思路見(jiàn)圖1。

1.1 協(xié)同過(guò)濾算法的相似度

相似度的計(jì)算方法主要有兩種：皮爾森相似度計(jì)算和余弦相似度計(jì)算。

皮爾森相似度[13]計(jì)算公式如下：

(1)

圖1 視頻網(wǎng)站電影智能推薦流程

余弦相似度[13]計(jì)算公式如下：

(2)

相比于余弦相似度計(jì)算公式，皮爾森相似度計(jì)算公式考慮了不同用戶(hù)評(píng)分平均分不同的情況。

1.2 評(píng)分估計(jì)方法

設(shè)U={u1,u2,…,un}為用戶(hù)集合，V={v1,v2,…,vm}為商品集合，ruv表示用戶(hù)u對(duì)商品v的評(píng)分估計(jì)。常見(jiàn)的評(píng)分估計(jì)方法[13]如下：

(3)

(4)

(5)

1.3 基于用戶(hù)的內(nèi)存推薦算法

基于用戶(hù)的內(nèi)存推薦算法主要先計(jì)算用戶(hù)的相似度，然后根據(jù)相應(yīng)的算法求出目標(biāo)用戶(hù)對(duì)目標(biāo)商品的估計(jì)評(píng)分。表1中的數(shù)據(jù)來(lái)自某電商網(wǎng)站的用戶(hù)評(píng)價(jià)商品的部分?jǐn)?shù)據(jù)。表中U表示用戶(hù)，V表示商品，評(píng)分范圍為1至10。表中“-”表示未評(píng)價(jià)，“？”表示待評(píng)價(jià)。

表1 不同用戶(hù)對(duì)已購(gòu)商品的評(píng)分

基于用戶(hù)的協(xié)同過(guò)濾算法，可以計(jì)算出目標(biāo)用戶(hù)Ui對(duì)商品Vj的評(píng)分結(jié)果Rij。以表1中的數(shù)據(jù)為例，可以計(jì)算評(píng)估用戶(hù)U5對(duì)商品V2的評(píng)分。具體步驟如下：第一，分別計(jì)算U5和Ui(i=1,2,3,4)的相似復(fù)雜度；第二，根據(jù)除目標(biāo)用戶(hù)以外的其他用戶(hù)對(duì)目標(biāo)商品的評(píng)分和相似度，計(jì)算目標(biāo)用戶(hù)U5對(duì)目標(biāo)商品V2的相似度r5,2。文中使用余弦計(jì)算用戶(hù)之間的復(fù)雜度，U5和Ui(i=1,2,3,4)的相似復(fù)雜度如下：

0.993

(6)

sim(U5,U2)=0.974

(7)

sim(U5,U3)=0.947

(8)

sim(U5,U4)=0.914

(9)

r52=[sim(U5,U1)r12+sim(U5,U2)r22+sim(U5,U3)r32+sim(U5,U4)r42]/[sim(U5,U1)+sim(U5,U2)+sim(U5,U3)+

sim(U5,U4)]=8.43

(10)

2 推薦系統(tǒng)評(píng)價(jià)準(zhǔn)則

在協(xié)同過(guò)濾算法中，不論是采用基于哪一種推薦算法用于用戶(hù)估計(jì)商品的評(píng)分，或者是用于對(duì)用戶(hù)推薦一個(gè)商品的列表，都需要對(duì)估計(jì)的評(píng)分和推薦的列表進(jìn)行評(píng)價(jià)，檢驗(yàn)實(shí)際評(píng)分值和估計(jì)評(píng)分值之間的誤差。誤差越小，說(shuō)明評(píng)分估計(jì)越準(zhǔn)確，則實(shí)際推薦商品越準(zhǔn)確。文獻(xiàn)[14]對(duì)現(xiàn)有的推薦系統(tǒng)評(píng)價(jià)指標(biāo)進(jìn)行了系統(tǒng)回顧，總結(jié)了推薦系統(tǒng)評(píng)價(jià)指標(biāo)的最新研究進(jìn)展，從準(zhǔn)確度、多樣性、新穎性及覆蓋率等方面進(jìn)行多角度闡述，并對(duì)各自的優(yōu)缺點(diǎn)以及適用環(huán)境進(jìn)行了深入分析。特別討論了基于排序加權(quán)的指標(biāo)，強(qiáng)調(diào)了推薦列表中商品排序?qū)ν扑]評(píng)價(jià)的影響。一般地，對(duì)于用戶(hù)對(duì)商品評(píng)分結(jié)果的檢驗(yàn)可用平均絕對(duì)誤差(MAE)或均方根誤差(RMSE)評(píng)估評(píng)分的誤差程度。

2.1 平均絕對(duì)誤差

MAE[14]用于度量用戶(hù)估計(jì)評(píng)分和真實(shí)值之間的誤差，其表達(dá)式為：

(11)

2.2 均方根誤差

表達(dá)式為：

(12)

其中，U和I分別為用戶(hù)集合和商品集合；pij為真實(shí)值；rij為估計(jì)評(píng)分值。

3 改進(jìn)型的基于用戶(hù)推薦算法

傳統(tǒng)的基于用戶(hù)推薦算法中，只是根據(jù)用戶(hù)對(duì)商品的評(píng)分來(lái)估計(jì)對(duì)其他商品的評(píng)分以及將評(píng)分高的商品推薦給用戶(hù)，單一的評(píng)分尺度往往無(wú)法挖掘用戶(hù)深層次的需求。同時(shí)考慮到用戶(hù)因生活背景、消費(fèi)習(xí)慣等各種因素的不同，帶來(lái)評(píng)分差異的不同。在有些情況下，由于這種評(píng)分差異巨大使得在使用余弦相似度計(jì)算用戶(hù)間的相似度時(shí)，出現(xiàn)了極大的偏差[15]。例如用戶(hù)U1、U2、U3對(duì)4種樣品進(jìn)行評(píng)分，見(jiàn)表2。

表2 不同用戶(hù)對(duì)于不同商品的差異評(píng)分

根據(jù)計(jì)算可知，用戶(hù)U1和用戶(hù)U2的相似度為1，明顯大于U1和U3的相似度。出現(xiàn)這種相似度計(jì)算結(jié)果偏差極大的原因，一方面是不同用戶(hù)自身的評(píng)價(jià)差異性大；另一方面是余弦相似度只是根據(jù)不同用戶(hù)的共同評(píng)分商品計(jì)算的，沒(méi)有考慮到所選商品對(duì)不同用戶(hù)的影響，也就是說(shuō)，所選參與計(jì)算復(fù)雜度的商品有可能偏向用戶(hù)U2，U1和U3雖然參與評(píng)分，但不一定真正感興趣。另外也有可能用戶(hù)U1和U3相對(duì)于用戶(hù)U2來(lái)說(shuō)，更加理性，評(píng)分更加嚴(yán)格，也就是說(shuō)不同用戶(hù)的評(píng)分體系有可能不一致。

根據(jù)這種情況，從相似度本身出發(fā)，提出一種融合型的相似度計(jì)算公式，它由兩部分組成。

3.1 余弦相似度修正型參數(shù)α

余弦相似度修正型參數(shù)α主要是針對(duì)用戶(hù)的評(píng)價(jià)體系不同而造成相似度計(jì)算偏差大的問(wèn)題。其修正后的相似度表達(dá)式為：

(13)

(14)

其中，s為用戶(hù)u、v的共同評(píng)價(jià)商品的集合；|S|為用戶(hù)u、v的共同評(píng)價(jià)商品數(shù)。該修正型參數(shù)α與不同用戶(hù)對(duì)相同商品評(píng)分的差異性呈負(fù)相關(guān)，當(dāng)用戶(hù)評(píng)分差異性大時(shí)，α值偏??；反之，α值偏大。

3.2 用戶(hù)特征屬性向量

改進(jìn)后的余弦相似度表達(dá)式為：

(15)

其中，T為特征屬性的集合。

根據(jù)上述提出的兩種改進(jìn)型余弦相似度計(jì)算方法，提出一種融合型的余弦相似度計(jì)算方法，即：

sim(x,y)=γ*simα(x,y)+(1-γ)simβ(x,y)

(16)

其中，γ是一種平衡參數(shù)，可以看作是一種權(quán)重因子，取值為[0,1]。

4 實(shí)驗(yàn)仿真

在TipDM-HB平臺(tái)進(jìn)行視頻網(wǎng)站的電影推薦建模仿真步驟如下：

(1)導(dǎo)入經(jīng)過(guò)簡(jiǎn)單預(yù)處理的csv數(shù)據(jù)，部分?jǐn)?shù)據(jù)見(jiàn)表3；

(2)構(gòu)建用戶(hù)-商品矩陣，分別根據(jù)余弦相似度公式和融合型的余弦相似度公式計(jì)算商品相似度；

(3)根據(jù)用戶(hù)相似度和用戶(hù)-商品矩陣，使用式4估算測(cè)試用戶(hù)對(duì)不同商品的評(píng)分(步驟2和步驟2被封裝成協(xié)同過(guò)濾算法建模平臺(tái)系統(tǒng)組件)以及將評(píng)分高的電影推薦給用戶(hù)；

(4)部分評(píng)分和推薦結(jié)果見(jiàn)表4，分析電影推薦結(jié)果。

表3 導(dǎo)入的部分用戶(hù)電影評(píng)價(jià)數(shù)據(jù)

表4 控制臺(tái)輸出的對(duì)部分用戶(hù)推薦結(jié)果

根據(jù)表4的推薦結(jié)果分析，用戶(hù)12、用戶(hù)74和用戶(hù)199所推薦電影的評(píng)分都高于7分，這樣的推薦結(jié)果是有意義的，會(huì)產(chǎn)生較好的用戶(hù)體驗(yàn)。改進(jìn)型的基于用戶(hù)協(xié)同過(guò)濾算法有效解決了由于新項(xiàng)目冷啟動(dòng)導(dǎo)致的用戶(hù)推薦不準(zhǔn)確問(wèn)題，提高了推薦的精準(zhǔn)度，進(jìn)而影響平臺(tái)的受歡迎程度。

由MAE誤差曲線(見(jiàn)圖2)可知，對(duì)比傳統(tǒng)的基于用戶(hù)的協(xié)同過(guò)濾算法和改進(jìn)型的基于用戶(hù)的協(xié)同過(guò)濾算法的平均絕對(duì)誤差，在相同的用戶(hù)鄰居個(gè)數(shù)的條件下，改進(jìn)型的協(xié)同過(guò)濾算法的MAE明顯小于傳統(tǒng)的基于用戶(hù)的協(xié)同過(guò)濾算法的MAE。

圖2 改進(jìn)前和改進(jìn)后的MAE誤差曲線

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

由于傳統(tǒng)的余弦復(fù)雜度計(jì)算公式只是從商品評(píng)分本身出發(fā)，沒(méi)有考慮到用戶(hù)的評(píng)價(jià)體系不同和用戶(hù)自身的特征屬性對(duì)商品評(píng)分的影響，因此在計(jì)算用戶(hù)相似度時(shí)出現(xiàn)了極大的偏差。文中提出了一種改進(jìn)型的協(xié)同過(guò)濾算法。第一，提出了一個(gè)余弦相似度修正參數(shù)α，通過(guò)該參數(shù)修正后，在計(jì)算評(píng)分差異大的用戶(hù)之間相似度時(shí)，能夠有比較好的修正作用；第二，提出了用戶(hù)特征屬性向量，該向量能夠考慮到用戶(hù)自身的特征屬性，避免在計(jì)算相似度時(shí)出現(xiàn)較大偏差。通過(guò)上述的融合性相似度計(jì)算公式，能夠解決相似度計(jì)算偏大過(guò)大的問(wèn)題。

根據(jù)TipDM-HB平臺(tái)的仿真數(shù)據(jù)來(lái)看，算法能夠根據(jù)歷史的電影評(píng)分估計(jì)出某用戶(hù)未評(píng)分電影的得分，同時(shí)推送給用戶(hù)評(píng)分比較高的電影。根據(jù)實(shí)驗(yàn)的推薦結(jié)果和MAE曲線可知，改進(jìn)型的協(xié)同過(guò)濾算法的推薦性能有了一定的提升。

盡管該算法改善了傳統(tǒng)的基于用戶(hù)的協(xié)同過(guò)濾算法中出現(xiàn)的余弦相似度計(jì)算偏差的問(wèn)題，但是也存在以下問(wèn)題：第一，引入的用戶(hù)特征向量帶來(lái)了一定的計(jì)算復(fù)雜度；第二，修正參數(shù)α和用戶(hù)特征向量能否進(jìn)行擴(kuò)展，用于改善皮爾森相似度計(jì)算方法。另外，根據(jù)對(duì)待計(jì)算數(shù)據(jù)的觀察，發(fā)現(xiàn)有些數(shù)據(jù)預(yù)處理不到位，簡(jiǎn)單的預(yù)處理只是將數(shù)據(jù)格式進(jìn)行調(diào)整，并沒(méi)有對(duì)有些缺乏主要字段的數(shù)據(jù)進(jìn)行舍棄。同時(shí)考慮到數(shù)據(jù)的復(fù)雜度，可以將數(shù)據(jù)分為合理評(píng)分記錄和不合理評(píng)分記錄，前者使用傳統(tǒng)的相似度進(jìn)行計(jì)算，后者使用改進(jìn)型的相似度進(jìn)行計(jì)算，以有效提升數(shù)據(jù)復(fù)雜度。因此，該算法有待進(jìn)一步完善。