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

林建輝,王茜冉,詹可強

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

0 引言

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

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

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

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

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

(1)

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

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

1.1 用戶/項目的近鄰與時間權重聚類

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

1.1.1 近鄰聚類

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

(2)

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

1.1.2 時間權重

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

(3)

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

1.1.3 結合時間權重的近鄰聚類

通過時間權重可以衡量用戶在不同時間階段的評價差異,結合時間權重的近鄰聚類能夠將目標用戶在相近時間段內有過共同興趣愛好的用戶進行聚類,具體公式為:

(4)

式中,TNBR{ua,ui}表示目標用戶ua結合時間權重的近鄰聚類集合.

1.2 差異協(xié)調因子

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

1.2.1 差異均值

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

(5)

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

1.2.2 差異方差

差異方差描述的是用戶之間對共同評價的差異標準方差,是項目受到用戶喜愛的標準差異標準方差,表達式為:

(6)

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

1.3 預測推薦

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

(7)

(8)

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

1.4 算法描述

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

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

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

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

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

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

2 實驗與結果分析

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

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

2.2 推薦的評價準則

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

(9)

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

(10)

(11)

2.3 實驗結果分析

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

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

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

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

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

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

3 結語

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