基于聚類與差異協(xié)調(diào)的協(xié)同過濾推薦算法

林建輝,王茜冉,詹可強(qiáng)

(福建信息職業(yè)技術(shù)學(xué)院 物聯(lián)網(wǎng)與人工智能學(xué)院,福建 福州 350000)

0 引言

2022年發(fā)布的第49次中國互聯(lián)網(wǎng)發(fā)展?fàn)顩r統(tǒng)計報告[1]顯示,截至2021年12月,我國網(wǎng)民規(guī)模達(dá)10.32億,上網(wǎng)比例達(dá)99%,網(wǎng)絡(luò)視頻用戶、購物用戶和新聞用戶分別達(dá)9.75億、8.42億和7.71億,大數(shù)據(jù)網(wǎng)絡(luò)信息時代正悄然而至.協(xié)同過濾推薦算法[2]成為大數(shù)據(jù)時代信息過載[3]問題的福音,在數(shù)據(jù)海洋中為用戶預(yù)測推薦節(jié)省了寶貴的時間.然而,為目標(biāo)用戶/項目提供準(zhǔn)確的預(yù)測推薦,前提需要度量選取用戶/項目的有效近鄰,通過有效近鄰,才能準(zhǔn)確地為目標(biāo)用戶/項目做出相關(guān)的推薦.

針對用戶/項目的相似性度量問題,國內(nèi)外學(xué)者提出了不同的觀點(diǎn).Gediminas等[4]將用戶/項目的屬性視作一個向量,用夾角余弦計算兩個向量的相似性,提出余弦相似性度量用戶/項目相似性的觀點(diǎn).Ahn等[5]針對不同用戶/項目的評價差異,通過減去平均值的方法提出修正余弦相似性度量用戶/項目的相似性觀點(diǎn).YUE XI等[6]用皮爾遜相關(guān)系數(shù)度量兩組線性用戶/項目的評價相似性.Shardanand等[7]在Schafer的基礎(chǔ)上分別提出考慮評分正負(fù)性的約束皮爾遜相關(guān)系數(shù)和考慮共同評分項的權(quán)重皮爾遜相關(guān)系數(shù).張曉琳等[8]針對用戶/項目的共同評價項提出杰卡德相似性度量的方法.事實(shí)上,由于用戶/項目評價差異、數(shù)據(jù)稀疏性等問題,導(dǎo)致用戶/項目的相似性度量不夠準(zhǔn)確.

本文提出基于聚類與差異協(xié)調(diào)的協(xié)同過濾推薦算法,通過目標(biāo)用戶近鄰聚類可以有效縮減近鄰搜索的時間與空間,結(jié)合時間權(quán)重的近鄰聚類,減少用戶在每個時間階段的風(fēng)格特色、人文喜好上差異的影響.通過評價差異因子協(xié)調(diào)目標(biāo)與近鄰的評價差異,完成預(yù)測推薦.實(shí)驗結(jié)果表明,該算法能夠提高協(xié)同過濾推薦系統(tǒng)的推薦質(zhì)量和準(zhǔn)確度.

1 基于聚類與差異協(xié)調(diào)的協(xié)同過濾推薦算法

在協(xié)同過濾推薦算法中,m個用戶用集合U={u1,u2,…,um}表示,n個項目用集合I={i1,i2,…,in}表示,用戶對項目的評分?jǐn)?shù)據(jù)集用一個m×n階的矩陣R表示[9].其形式為:

(1)

其中,Ri,j(1≤i≤m,1≤j≤n)表示用戶ui對項目ij的評分,協(xié)同過濾推薦就是根據(jù)已知的用戶和項目等數(shù)據(jù)為不同用戶做出個性化的推薦.

傳統(tǒng)的相似性度量需要通過計算用戶/項目的評價數(shù)值,例如余弦相似性、皮爾遜相關(guān)系數(shù)和修正余弦相似性等.實(shí)際上用戶評價存在個人尺度或者評價習(xí)慣,有的用戶傾向于給高分,有的用戶傾向于給低分.那么,在計算習(xí)慣給高分和習(xí)慣給低分的兩個用戶相似性時,通過傳統(tǒng)相似方法得到的結(jié)果必然是兩個用戶不相似,或者相似性低.而事實(shí)上,兩個用戶的興趣愛好極大可能相似.本文采用聚類方式篩選出目標(biāo)相似的用戶,結(jié)合時間權(quán)重聚類,完成目標(biāo)用戶在相近時間段內(nèi)有過共同興趣愛好的用戶聚類.

1.1 用戶/項目的近鄰與時間權(quán)重聚類

大數(shù)據(jù)時代,協(xié)同過濾需要在用戶/項目的數(shù)據(jù)集里計算出用戶/項目的相似性,需要耗費(fèi)大量的計算資源,且計算結(jié)果可能存在不確定性.本文通過近鄰與時間權(quán)重共同聚類的方法,將用戶/項目共同評分過的近鄰進(jìn)行聚類,進(jìn)而縮減近鄰的搜索時間與空間.

1.1.1 近鄰聚類

近鄰用戶的搜索選取是協(xié)同過濾推薦的基礎(chǔ),從大數(shù)據(jù)庫中快速而準(zhǔn)確地選取近鄰是推薦系統(tǒng)近鄰選取的目標(biāo).對目標(biāo)用戶的近鄰進(jìn)行聚類的方法可表示為:

(2)

式中,NBR{ua,ui}表示目標(biāo)用戶ua的近鄰聚類集合;Ia∩Ii是用戶ua與ui共同評分的項目集合;Ia∪Ii是用戶ua與ui有評分的項目集合,Ia和Ii分別表示用戶ua與ui的評分的項目集合.該式表述的是兩用戶共同評分項目在兩用戶所有評分項目中的占比,占比越大,表示兩用戶對項目的選擇就越接近,通過近鄰聚類可以有效地將目標(biāo)用戶的最近鄰進(jìn)行聚類.

1.1.2 時間權(quán)重

每個時間階段的用戶在風(fēng)格特色、人文喜好上或多或少都存在著差異,衡量用戶在不同時間階段的評價差異的公式為:

(3)

式中,T(ua,ui)表示用戶ua與ui評價時間權(quán)重,取值范圍為0到1,兩用戶的評價時間越接近,該時間權(quán)重值越大,表示兩用戶的相似程度越大.tua-tui表示兩用戶評價同一項目的時間差值,該差值越小說明兩用戶在某個時間范圍內(nèi)興趣愛好越接近.

1.1.3 結(jié)合時間權(quán)重的近鄰聚類

通過時間權(quán)重可以衡量用戶在不同時間階段的評價差異,結(jié)合時間權(quán)重的近鄰聚類能夠?qū)⒛繕?biāo)用戶在相近時間段內(nèi)有過共同興趣愛好的用戶進(jìn)行聚類,具體公式為:

(4)

式中,TNBR{ua,ui}表示目標(biāo)用戶ua結(jié)合時間權(quán)重的近鄰聚類集合.

1.2 差異協(xié)調(diào)因子

傳統(tǒng)的相似性度量無法衡量用戶的評價習(xí)慣,因而在度量用戶間的相似性時往往不夠準(zhǔn)確.本文結(jié)合時間權(quán)重的近鄰聚類方法聚類目標(biāo)用戶的近鄰,通過用戶間評價的差異均值或差異方差衡量用戶的評價差異.

1.2.1 差異均值

差異均值描述的是用戶之間對共同評價的差異平均值,是項目受到用戶喜愛的差異平均值,表達(dá)式為:

(5)

式中,AverDif(ua,ui)表示用戶ua和用戶ui的差異均值,Ri,j表示用戶ui對項目ij的評分,Ra,j表示用戶ua對項目ij的評分,n是用戶之間共同評價項目的總數(shù).

1.2.2 差異方差

差異方差描述的是用戶之間對共同評價的差異標(biāo)準(zhǔn)方差,是項目受到用戶喜愛的標(biāo)準(zhǔn)差異標(biāo)準(zhǔn)方差,表達(dá)式為:

(6)

式中,s2Dif(ua,ui)表示用戶ua和用戶ui的差異方差.

1.3 預(yù)測推薦

對目標(biāo)用戶ua的未評分項目進(jìn)行預(yù)測,首先需要找到目標(biāo)用戶的最近鄰,借助公式(4)可得到用戶/項目的共同評分的近鄰與時間權(quán)重聚類用戶集合TNBR,且可調(diào)整與目標(biāo)用戶ua最近鄰的數(shù)量.根據(jù)公式(7)和(8)可計算目標(biāo)用戶ua對未評分項目的預(yù)測評分,在后續(xù)的實(shí)驗中會對計算結(jié)果進(jìn)行對比分析.

(7)

(8)

公式(7)和(8)式中,Pa,j為目標(biāo)用戶ua對未知評分項目ij的預(yù)測評分;K是近鄰總數(shù),n是用戶之間共同評價項目總數(shù).根據(jù)上式計算目標(biāo)用戶ua對未評分項目的預(yù)測評分,最終將評分最高的前N個項目作為目標(biāo)用戶ua的推薦結(jié)果.

1.4 算法描述

本文提出的基于聚類與差異協(xié)調(diào)的協(xié)同過濾推薦算法(CF-TNBRD),通過近鄰與時間權(quán)重共同聚類的方法,縮減近鄰的搜索時間與空間,改善了傳統(tǒng)通過計算用戶相似性選取近鄰不夠準(zhǔn)確的問題,最后通過差異協(xié)調(diào)因子協(xié)調(diào)用戶/項目間的評價差異.其算法流程如下:

(1)由用戶、項目評分等數(shù)據(jù)構(gòu)造出用戶-項目評分矩陣;

(2)結(jié)合用戶-項目的評價時間屬性,對目標(biāo)用戶進(jìn)行評分與時間權(quán)重的近鄰聚類,根據(jù)需求選取最近鄰聚類數(shù)量;

(3)根據(jù)公式(5)和(6)對聚類的最近鄰計算用戶間的差異;

(4)根據(jù)預(yù)測公式(7)和(8)進(jìn)行預(yù)測評分;

(5)選取評分最高的前N個項目作為推薦結(jié)果,完成推薦.

2 實(shí)驗與結(jié)果分析

2.1 實(shí)驗數(shù)據(jù)集

實(shí)驗采用的數(shù)據(jù)集[9]包括:①美國明尼蘇達(dá)大學(xué)GroupLenps研究項目組提供的MovieLensML-100K數(shù)據(jù)集,包含了943個用戶對1 682部電影共100 000條的評分記錄;②百度電影推薦系統(tǒng)比賽使用數(shù)據(jù)集,包含了15萬用戶對15 000部電影約1百萬條的評分記錄,實(shí)驗隨機(jī)選擇了943位用戶對1 682部電影共62 507條的評分記錄.兩個實(shí)驗數(shù)據(jù)集的評分范圍均為1～5,數(shù)值越大表示用戶對電影的喜歡程度越大.實(shí)驗隨機(jī)選取數(shù)據(jù)集中的80%作為訓(xùn)練集,20%作為測試集.

2.2 推薦的評價準(zhǔn)則

本文采用的評價準(zhǔn)則是廣泛應(yīng)用于評價協(xié)同過濾推薦算法的平均絕對誤差[10](MAE)和精確度(Precision)[11],MAE通過計算預(yù)測評分與實(shí)際評分的平均誤差來衡量推薦質(zhì)量,MAE越小,說明推薦質(zhì)量越好.其計算公式如(9)所示,式中,Pa,j表示預(yù)測用戶對項目的評分值,Ra,j表示實(shí)際的用戶對項目的評分值為,T為測試集的項目數(shù)量.

(9)

Precision是通過計算預(yù)測評分與實(shí)際評分相等的數(shù)量占整個測試集的比率來衡量推薦的準(zhǔn)確度,Precision指標(biāo)值越大,說明推薦準(zhǔn)確性越好.其計算公式如(10)和(11)所示,用Nj表示用戶對項目j預(yù)測評分值與實(shí)際評分值的關(guān)系,當(dāng)預(yù)測用戶對項目評分值與實(shí)際評分值相等時用1表示,否則用0表示.

(10)

(11)

2.3 實(shí)驗結(jié)果分析

實(shí)驗將所提算法、基于聚類與差異均值協(xié)調(diào)協(xié)同過濾推薦算法(CF-TNBRAD)、基于聚類與差異方差協(xié)調(diào)協(xié)同過濾推薦算法(CF-TNBRS2D)與傳統(tǒng)的基于用戶的協(xié)同過濾算法(UCF)[12]進(jìn)行對比.取橫坐標(biāo)為聚類近鄰數(shù),其值從5逐漸增加到40,縱坐標(biāo)分別為MAE和Precision,實(shí)驗結(jié)果如圖1和圖2所示.

(a)MovieLens數(shù)據(jù)集下各算法MAE對比結(jié)果

(b)百度電影數(shù)據(jù)集下各算法MAE對比結(jié)果

(a)MovieLens數(shù)據(jù)集下各算法Precision對比結(jié)果

(b)百度電影數(shù)據(jù)集下各算法Precision對比結(jié)果

從圖1(a)和(b)的實(shí)驗結(jié)果可知,各算法隨著目標(biāo)用戶近鄰個數(shù)的增加,MAE逐漸降低,而本文算法MAE要比UCF算法低,表明了本文算法在推薦質(zhì)量上優(yōu)于UCF算法.從圖2(a)和(b)的實(shí)驗結(jié)果可知,各算法隨著目標(biāo)近鄰數(shù)的增加,Precision逐漸提高,而本文算法Precision要比UCF高,表明了本文算法在推薦準(zhǔn)確度上優(yōu)于UCF.綜上,本文算法在總體上優(yōu)于傳統(tǒng)基于用戶的協(xié)同過濾算法(UCF),能夠提高推薦系統(tǒng)的推薦質(zhì)量和準(zhǔn)確度.

3 結(jié)語

最近鄰的有效選取是推薦系統(tǒng)預(yù)測中最為關(guān)鍵的環(huán)節(jié)之一,傳統(tǒng)推薦算法在用戶相似性度量方面存在不足.本文提出基于聚類與差異協(xié)調(diào)的的協(xié)同過濾推薦算法,采用用戶間共同評分與評分時間屬性相結(jié)合的方式將目標(biāo)用戶的最近鄰進(jìn)行聚類,改善最近鄰的有效選取.通過評價差異協(xié)調(diào)因子協(xié)調(diào)用戶之間的評價差異,實(shí)現(xiàn)目標(biāo)用戶的評分預(yù)測.實(shí)驗結(jié)果表明,所提算法能夠提高推薦系統(tǒng)的推薦質(zhì)量和準(zhǔn)確度.