改進(jìn)Mini Batch K-Means時間權(quán)重推薦算法

徐慧君,王 忠,馬麗萍,饒 華,何承恩

(四川大學(xué) 電氣工程學(xué)院,成都 610065)

0 概述

互聯(lián)網(wǎng)高速發(fā)展帶來的信息過載問題推動了人們對推薦系統(tǒng)的研究,而決定推薦系統(tǒng)是否成功的關(guān)鍵是推薦算法[1]。目前推薦算法應(yīng)用最廣泛的是協(xié)同過濾算法,該算法只需用戶歷史評分?jǐn)?shù)據(jù),就可以向用戶推薦[2]。協(xié)同過濾算法主要有基于近鄰的過濾算法和基于模型的過濾算法[3]。

基于近鄰的協(xié)同過濾算法由于推薦時需要查找與目標(biāo)用戶的最相似用戶[4],在大型推薦系統(tǒng)中,用戶的歷史行為數(shù)據(jù)一般十分龐大,因此在進(jìn)行推薦時,需要耗費(fèi)巨大的計(jì)算和時間資源尋找最相似用戶,算法的時間復(fù)雜度高,可擴(kuò)展性低[5]。目前,推薦系統(tǒng)中用戶和項(xiàng)目的數(shù)據(jù)量巨大,但是在推薦系統(tǒng)中一個用戶往往只對其中占比很少的項(xiàng)目進(jìn)行評分,導(dǎo)致用戶有效評分?jǐn)?shù)據(jù)少,用戶評分?jǐn)?shù)據(jù)矩陣十分稀疏,算法面臨數(shù)據(jù)稀疏問題[6]。此外,用戶興趣度隨著時間推移發(fā)生偏移同樣不可忽視[7],用戶興趣度偏移往往導(dǎo)致算法的推薦項(xiàng)目不符合用戶最新興趣點(diǎn),使得算法推薦偏離用戶的實(shí)際需求。

針對協(xié)同過濾推薦算法存在的上述問題,許多研究者進(jìn)行了大量研究。文獻(xiàn)[8]采取評分矩陣降維技術(shù)來改善數(shù)據(jù)稀疏性,但是該降維方法時間復(fù)雜度較高。文獻(xiàn)[9]采取基于缺失值填充的技術(shù),為用戶未評分項(xiàng)目設(shè)置一個固定的值,即用戶評分的均值,雖然在某種程度上解決了數(shù)據(jù)稀疏問題,但是該算法中用戶的個人興趣得不到體現(xiàn)。文獻(xiàn)[10]采用關(guān)系模糊減法聚類作為一級建模,然后挖掘各個聚類內(nèi)的關(guān)聯(lián)規(guī)則,提出了基于模型的二級技術(shù),較好地緩解數(shù)據(jù)稀疏性和可擴(kuò)展性問題,但該方法需用到項(xiàng)目具體信息屬性的獲取形式各異,并且信息屬性獲取難度較大。文獻(xiàn)[11]采用基于FCM聚類的Slope one算法對未評分項(xiàng)目進(jìn)行預(yù)測填充,但該方法用戶興趣偏移影響仍舊存在。文獻(xiàn)[12]提出將時間權(quán)重函數(shù)和時間窗口相結(jié)合的推薦算法,將近期數(shù)據(jù)和早期反復(fù)出現(xiàn)的數(shù)據(jù)相結(jié)合作為用戶興趣時間權(quán)重計(jì)算依據(jù),形成一種新的時間權(quán)重參數(shù)衡量用戶興趣變化。文獻(xiàn)[13]利用用戶消費(fèi)時間采取基于時序消費(fèi)行為的最近鄰建模方法,更精確地確定用戶最近鄰。文獻(xiàn)[14]利用用戶屬性和項(xiàng)目流行度計(jì)算用戶偏好,融合時間因素引入用戶相似度計(jì)算,消除時間因素帶來算法推薦性能下降的影響。以上研究雖然考慮到了用戶興趣偏移現(xiàn)象,但仍然存在數(shù)據(jù)稀疏性和擴(kuò)展性弱等問題。

上述研究各有側(cè)重,雖然在一定程度上解決了數(shù)據(jù)稀疏性以及用戶興趣度偏移的影響,但是仍存在以下問題:評分矩陣缺失項(xiàng)往往利用固定值評分進(jìn)行填充,忽略了用戶的個性化,填充數(shù)據(jù)可靠性有待考量;在改善用戶興趣偏移問題時,算法的時間復(fù)雜度過高,算法仍然存在實(shí)時性不高和可擴(kuò)展性弱問題;在進(jìn)行用戶興趣度漂移融合時造成最近鄰用戶相似度偏低,導(dǎo)致算法的推薦精度降低。

針對上述研究存在的問題,本文引入Pearson相關(guān)系數(shù)改進(jìn)傳統(tǒng)Mini Batch K-Means聚類距離迭代計(jì)算方法MBKT-CF,利用改進(jìn)后聚類算法對缺失項(xiàng)預(yù)測評分填充,采取牛頓冷卻時間權(quán)重函數(shù)擬合用戶興趣度漂移改進(jìn)用戶相似度計(jì)算,最終得到項(xiàng)目預(yù)測評分。

1 改進(jìn)算法

1.1 改進(jìn)的Mini Batch K-Means聚類算法填充

運(yùn)用機(jī)器學(xué)習(xí)中的Mini Batch K-Means聚類算法對用戶評分?jǐn)?shù)據(jù)進(jìn)行聚類,在結(jié)果簇上尋找目標(biāo)用戶的最近鄰集合,能夠縮短算法計(jì)算相似用戶所花費(fèi)的時間,有利于改進(jìn)協(xié)同過濾推薦算法可擴(kuò)展性[15]。本文選擇時間復(fù)雜度較低的Mini Batch K-Means算法確定用戶最近鄰[16],并對算法中質(zhì)心距離迭代方法進(jìn)行改進(jìn),采取基于Pearson相關(guān)系數(shù)計(jì)算各向量與質(zhì)心距離替代傳統(tǒng)的歐氏距離,Pearson相關(guān)系數(shù)計(jì)算方法如下:

(1)

下文詳細(xì)介紹改進(jìn)Mini Batch K-Means聚類確定用戶最近鄰算法,具體步驟如下:

輸入填充矩陣Rm×n={r1,r2,…,rm},聚類簇?cái)?shù)k

輸出聚類簇K={K1,K2,…,Kk,},用戶最近鄰Nner

步驟1從填充矩陣Rm×n隨機(jī)選取初始的k個質(zhì)心向量:{μ1,μ2,…,μk}。

步驟2根據(jù)Pearson相關(guān)系數(shù)計(jì)算公式計(jì)算評分矩陣Rm×n,樣本ri(i=1,2,…,m)和各個質(zhì)心向量μj(j=1,2,…,k)的相似度距離:dij=sim(ri,μj),將ri標(biāo)記為dij對應(yīng)的類別λi,此時更新Kλi=Kλi∪{ri}。

步驟3完成所有樣本遍歷之后,每次從樣本ri(i=1,2,…,m)隨機(jī)抽取部分樣本點(diǎn)組成一個Batch,通過計(jì)算Batch的平均值得到新的聚類中心,將Batch的數(shù)據(jù)全部分配給該聚類中心。

步驟4重復(fù)步驟1、步驟2,隨著迭代次數(shù)增多,聚類中心的變化減小,最終收斂至穩(wěn)定狀態(tài)或者完成指定次數(shù),直到不再發(fā)生變化。

步驟5計(jì)算目標(biāo)用戶到k個簇的距離,找到距離最近的一個簇。

步驟6根據(jù)式(1)計(jì)算目標(biāo)用戶與簇中各個用戶的相似度,取相似度最高的N個用戶作為最近鄰居集合Nner。

通過上述改進(jìn)型聚類確定用戶最近鄰,可以將評分習(xí)慣比較相似的用戶分配到同一個聚類簇中,選取與目標(biāo)用戶相似度距離最近的簇中與目標(biāo)用戶相似度最高的若干用戶確定最近鄰。根據(jù)最近鄰用戶相似度、目標(biāo)用戶的平均評分,計(jì)算目標(biāo)用戶對于項(xiàng)目i的預(yù)測評分。這樣的預(yù)測填充數(shù)據(jù)具有較好的相關(guān)性,也能較好地體現(xiàn)用戶的評分個性化,預(yù)測評分計(jì)算如下:

(2)

其中,V為用戶最近鄰集合。

通過上述項(xiàng)目預(yù)測評分方法,得到每個用戶對未評分項(xiàng)目的評分值,實(shí)現(xiàn)稀疏矩陣填充,即任意用戶u對項(xiàng)目i的評分如下:

(3)

1.2 牛頓冷卻定律時間權(quán)重相似度的改進(jìn)

由于用戶在不同時間點(diǎn)的興趣度是不同的,其在不同時間段的評分能夠反映用戶的興趣度變化。用戶最近的評分更能代表用戶當(dāng)前的興趣度,因此其最近的評分相比較早期的評分對推薦系統(tǒng)的影響更大,應(yīng)被賦予更高的時間權(quán)重?；谝陨纤枷?本文提出基于牛頓冷卻定律時間權(quán)重函數(shù)。

牛頓冷卻定律是指當(dāng)物體表面與周圍溫度存在溫度差時,單位時間單位面積散失的熱量與溫度差成正比[17],數(shù)學(xué)表達(dá)式如下:

(4)

其中,T(t)為t時刻物體的溫度,H為室溫,α為自定義比例系數(shù),代表物體溫度變化速度,通常α>0。

為進(jìn)一步理解牛頓冷卻定律,對上述微分方程進(jìn)行積分,即:

(5)

ln|T(t)-H|=-αt+B

(6)

對式(6)進(jìn)行轉(zhuǎn)化,可得:

T(t)-H=C·e-αt

(7)

根據(jù)初始條件對式(7)進(jìn)行求解,初始條件:T(0)為物體初始溫度;H為周圍環(huán)境溫度;t0為初始時刻,代入上式可得:

T(t0)=H+C·e-αt0

(8)

繼續(xù)變化最終可得:

T(t0)=H+(T(t0)-H)·e-α(t0-t)

(9)

根據(jù)式(9)定義,將推薦算法中用戶興趣度隨時間變化關(guān)系類比于牛頓冷卻定律物體溫度關(guān)于室溫變化關(guān)系。將用戶對于所有物品的平均評分值類比于室溫,用戶某時刻對于物品的興趣度類比于物體溫度,將用戶興趣隨時間變化率類比于物品溫度隨室溫變化率α,可得到用戶興趣度隨時間變化的一般規(guī)律[18],即:

(10)

其中,f(ui,t)為t時刻用戶u對項(xiàng)目i的評分,ti為開始推薦時間戳,t0為用戶u對項(xiàng)目i評分時間戳,α為用戶興趣度變化率。

在計(jì)算用戶相似度時,將基于牛頓冷卻定律的用戶興趣度變化融合到相似度計(jì)算公式中,即:

(11)

1.3 評分預(yù)測

在改進(jìn)聚類算法產(chǎn)生的聚類簇中,根據(jù)牛頓冷卻時間權(quán)重改進(jìn)相似度計(jì)算,計(jì)算目標(biāo)用戶與簇中各個用戶之間的相似度,選取與目標(biāo)用戶相似度最高的若干用戶作為目標(biāo)用戶預(yù)測評分的最終最近鄰集合,融合時間權(quán)重加權(quán)計(jì)算目標(biāo)用戶u對于項(xiàng)目i的預(yù)測評分,即:

(12)

其中,Nu表示用戶u的最近鄰集合。

1.4 算法步驟

基于改進(jìn)Mini Batch K-Means聚類的時間權(quán)重協(xié)同過濾算法基本步驟如下:

輸入目標(biāo)用戶u,用戶-項(xiàng)目評分矩陣Rm×n,用戶近鄰數(shù)ktop,top-N推薦項(xiàng)目個數(shù)Ntop

輸出推薦結(jié)果Ntop個項(xiàng)目集Itop

步驟1對初始評分矩陣Rm×n進(jìn)行改進(jìn)型Mini Batch K-Means聚類,確定初始用戶最近鄰。

步驟2根據(jù)步驟1得到的用戶最近鄰,采用式(2)對評分矩陣未評分項(xiàng)進(jìn)行預(yù)測評分。

步驟3基于步驟2計(jì)算得到的預(yù)測評分,根據(jù)式(3)對Rm×n進(jìn)行矩陣填充。

步驟4根據(jù)式(10)計(jì)算用戶對項(xiàng)目的融合時間參數(shù)的評分。

步驟5基于步驟4得到的評分,根據(jù)式(11)對填充后評分矩陣計(jì)算基于時間權(quán)重相似度,得到用戶相似度。

步驟6根據(jù)步驟5得到的用戶相似度,選取與目標(biāo)用戶u最相似的ktop個用戶作為用戶最終近鄰集Uner。

步驟7在Uner中,根據(jù)式(12)計(jì)算目標(biāo)用戶u對候選項(xiàng)目的最終預(yù)測評分,選取分值最高的前Ntop個項(xiàng)目集Itop推薦給目標(biāo)用戶u。

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

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

為驗(yàn)證本文提出的改進(jìn)算法的推薦性能,采用MovieLens數(shù)據(jù)集ml-100k作為實(shí)驗(yàn)的測試數(shù)據(jù)集。數(shù)據(jù)集評分矩陣稀疏度為93.7%,包含943個用戶對1 682部電影的100 000條評分?jǐn)?shù)據(jù),評分范圍為1分～5分,分值高低代表用戶對電影的偏好度高低。其中,每條數(shù)據(jù)含有評分時間戳,表示用戶評分時的不同時間點(diǎn),用于計(jì)算所提算法的時間權(quán)重。數(shù)據(jù)集評分?jǐn)?shù)據(jù)結(jié)構(gòu)如表1所示。

表1 數(shù)據(jù)集評分?jǐn)?shù)據(jù)結(jié)構(gòu)Table 1 Scoring data structure of dataset

2.2 評價(jià)指標(biāo)

本文采取準(zhǔn)確率(Precision)、召回率(Recall)、F1指標(biāo)、平均絕對誤差(Mean Absolute Error,MAE)來衡量推薦算法性能。

1)準(zhǔn)確率是指在最終推薦列表中用戶感興趣項(xiàng)目占列表所有已推薦項(xiàng)目的比值,表示用戶對被推薦項(xiàng)目真正感興趣的可能性。

(13)

其中,R(u)表示為用戶u推薦R個物品,T(u)為用戶真正感興趣的項(xiàng)目集,U為測試集所有用戶集。

2)召回率是指在實(shí)際推薦中用戶真正感興趣的項(xiàng)目在用戶所有感興趣項(xiàng)目中的比值,表示用戶感興趣的一個項(xiàng)目被系統(tǒng)實(shí)際推薦的可能性。

(14)

3)F1指標(biāo)結(jié)合準(zhǔn)確率和召回率,能更加全面地評價(jià)算法的性能,其值越大,表示該算法綜合推薦性能越優(yōu)越。計(jì)算公式如下:

(15)

4)MAE表示用戶對項(xiàng)目的預(yù)測評分與實(shí)際評分之間的平均誤差。MAE值越小,表明預(yù)測結(jié)果與真實(shí)結(jié)果越接近[19]。

(16)

其中,Pi表示項(xiàng)目i的預(yù)測評分,Qi表示項(xiàng)目i的實(shí)際評分,N表示測試集中用戶對項(xiàng)目評分個數(shù)。

2.3 結(jié)果及分析

為驗(yàn)證本文MBKT-CF算法的性能,將該算法和文獻(xiàn)[20]融合時間因素、用戶評分特性的協(xié)同過濾算法(TP-CF)、文獻(xiàn)[21]基于MI聚類的協(xié)同推薦算法(MI-CF)以及傳統(tǒng)基于用戶的協(xié)同過濾算法(UBCF)在數(shù)據(jù)集上進(jìn)行比較。

實(shí)驗(yàn)采取機(jī)器學(xué)習(xí)實(shí)驗(yàn)中常用的五折交叉驗(yàn)證法,隨機(jī)選取數(shù)據(jù)集的80%數(shù)據(jù)作為訓(xùn)練集,20%的數(shù)據(jù)作為測試集。設(shè)計(jì)3組實(shí)驗(yàn),為降低隨機(jī)性給實(shí)驗(yàn)數(shù)據(jù)造成的影響,進(jìn)行5次五折交叉驗(yàn)證,取其平均值作為最終實(shí)驗(yàn)數(shù)據(jù),實(shí)驗(yàn)通過Python語言和Pycharm軟件完成。

實(shí)驗(yàn)1確定聚類算法最佳簇?cái)?shù)

為使MI-CF和MBKT-CF達(dá)到更好的實(shí)驗(yàn)效果,需要提前確定2個算法取得最小的MAE值下的最佳聚類簇?cái)?shù)。為此,本文實(shí)驗(yàn)通過計(jì)算2個算法在不同聚類簇?cái)?shù)下的MAE值,找到最合理的聚類簇?cái)?shù)。初始設(shè)置用戶最近鄰集個數(shù)為15,橫軸表示聚類簇?cái)?shù),范圍從2增加到20,間隔為2,縱軸表示MAE值,實(shí)驗(yàn)結(jié)果如圖1所示。

圖1 MAE與聚類簇?cái)?shù)的關(guān)系

從圖1可以看出,隨著聚類簇?cái)?shù)的增加,兩種推薦算法的MAE值變化趨勢一致,都是先減小后增加,最后趨于平緩。其中MI-CF的MAE值在簇?cái)?shù)為12時達(dá)到最低,因此其最合理簇?cái)?shù)k取12。對于MBKT-CF,當(dāng)簇?cái)?shù)為16時,MAE值最小,因此該算法的最合理簇?cái)?shù)k為16。

實(shí)驗(yàn)2稀疏矩陣填充

為緩解協(xié)同過濾推薦算法的數(shù)據(jù)稀疏性問題,需要對初始用戶稀疏評分矩陣進(jìn)行基于改進(jìn)Mini Batch K-Means聚類算法預(yù)測填充。填充后的數(shù)據(jù)集詳細(xì)信息如表2所示。

表2 數(shù)據(jù)集填充后具體信息Table 2 Specific information of filled dataset

從表2可以看出,填充后的評分矩陣有效評分?jǐn)?shù)量從100 000條提高到800 000條,評分?jǐn)?shù)量提升了7倍,每部電影最少評分記錄從20提高到40,數(shù)據(jù)稀疏度從原始的93.7%下降到50.4%,評分矩陣稀疏性得到較好改善。

實(shí)驗(yàn)3算法精度對比實(shí)驗(yàn)

圖2給出各算法的Precision隨著近鄰數(shù)變化的趨勢,Precision值越大說明評分預(yù)測的準(zhǔn)確率越高。從圖2可以看出,隨著近鄰個數(shù)N的增加,在同一個近鄰數(shù)下,MBKT-CF的Precision均高于其他3種推薦算法,具有最高的推薦準(zhǔn)確率。并且UBCF與MI-CF的Precision隨著N的增加均呈現(xiàn)下降趨勢,而MBKT-CF的Precision下降后也能保持在較高水平。這說明本文算法的分類準(zhǔn)確度相比UBCF、MI-CF、TP-CF算法均有較為顯著提升,具有更高的推薦準(zhǔn)確性。

圖2 Precision與近鄰個數(shù)的關(guān)系

Fig.2Relationship of Precision and the numberof neighbors

圖3展示了各算法召回率的變化情況。隨著近鄰數(shù)N的增加,在同一個近鄰數(shù)下,MBKT-CF的Recall均優(yōu)于其他3種推薦算法。與此同時,傳統(tǒng)UBCF的Recall隨著N的增加呈現(xiàn)前期短暫上升后期緩慢下降趨勢,最終趨于穩(wěn)定。而其余3種算法的Recall呈現(xiàn)一定程度上升,在N>60后,逐漸趨于穩(wěn)定。這表明,相比較UBCF、MI-CF、TP-CF,MBKT-CF在召回率上同樣取得良好的效果。

圖3 Recall與近鄰個數(shù)的關(guān)系

結(jié)合圖2和圖3可以發(fā)現(xiàn),各算法的Precision和Recall隨著近鄰數(shù)N變化的變化趨勢是相反的。因?yàn)樵谕扑]算法中,召回率和準(zhǔn)確率往往是相悖的,提高準(zhǔn)確率是以犧牲一定的召回率為代價(jià)的。基于此,圖4給出了結(jié)合準(zhǔn)確率和召回率的綜合指標(biāo)F1值變化。在不同近鄰數(shù)下,MBKT-CF的F1值均大于其余3種推薦算法。其中,前期F1值隨著N的增加而增加,當(dāng)近鄰數(shù)N達(dá)到60時,MBKT-CF的F1指標(biāo)值達(dá)到最大的0.125 34,之后F1值呈現(xiàn)下降趨勢,最終趨于平緩。由此可見,MBKT-CF綜合指標(biāo)相比較其余傳統(tǒng)推薦算法均有一定提升,綜合推薦準(zhǔn)確度在4種推薦算法中最高。

圖4 F1與近鄰個數(shù)的關(guān)系

除比較改進(jìn)算法與其余協(xié)同過濾算法的預(yù)測評分準(zhǔn)確度外,本文也對各算法的MAE進(jìn)行比較,如圖5所示。從圖5可以看出,UBCF、MI-CF、TP-CF3種算法的MAE值均比較大,而MBKT-CF的MAE較小。而且隨著近鄰數(shù)N的增加,其MAE值呈現(xiàn)下降趨勢,最終收斂到穩(wěn)定狀態(tài),下降后的MAE值均小于其余3種算法的MAE值。由此可見,本文改進(jìn)算法的MAE值明顯降低,算法的預(yù)測精確度最高。

圖5 MAE與近鄰個數(shù)的關(guān)系

綜上所述,與UBCF、MI-CF、TP-CF算法相比,MBKT-CF算法由于采用基于Pearson相關(guān)系數(shù)替代Mini Batch K-Means聚類算法的歐式距離,使得最近鄰內(nèi)用戶的相似性更高,因此預(yù)測評分填充稀疏矩陣時更準(zhǔn)確。之后對填充后的評分矩陣融合牛頓冷卻時間權(quán)重函數(shù)擬合用戶興趣度的變化,較好地改善了用戶興趣漂移問題,預(yù)測評分更趨近于用戶的實(shí)際評分,推薦算法的推薦準(zhǔn)確度和精確度均得到一定的提高。

3 結(jié)束語

本文提出改進(jìn)的Mini Batch K-Means時間權(quán)重推薦算法,通過基于Pearson相關(guān)系數(shù)對改進(jìn)Mini Batch K-Means聚類算法缺失項(xiàng)進(jìn)行預(yù)測評分填充,數(shù)據(jù)稀疏度由93.7%下降到50.4%,較好地緩解了數(shù)據(jù)稀疏性,提高算法可擴(kuò)展性。考慮到用戶興趣度漂移,融合牛頓冷卻時間權(quán)重函數(shù)改進(jìn)用戶相似度,進(jìn)而得到項(xiàng)目最終預(yù)測評分。實(shí)驗(yàn)結(jié)果表明,與UBCF、MI-CF、TP-CF等算法相比,改進(jìn)MBKT-CF算法的準(zhǔn)確率、召回率、F1值均取得最優(yōu),同時,MAE值在各個算法中最低,擁有比其他協(xié)同過濾算法更高的推薦精確度和準(zhǔn)確度,具有良好的推薦性能。下一步將在有效提高本文算法推薦準(zhǔn)確性的同時,將算法移植到云計(jì)算平臺,提升算法的應(yīng)用性。