基于改進K-means和優(yōu)化評分的協(xié)同過濾推薦算法

施天虎，徐洪珍

(東華理工大學(xué) 信息工程學(xué)院，南昌 330013)

隨著互聯(lián)網(wǎng)的不斷發(fā)展，人們由信息匱乏時代過渡到了信息過載時代.用戶在搜索信息時通常無法直接有效地獲取他們需要的內(nèi)容.為了解決信息過載，推薦算法應(yīng)運而生[1]，其通過對用戶的歷史行為數(shù)據(jù)進行分析，精確定位用戶需求，為用戶提供智能化推薦[2].

協(xié)同過濾推薦算法是目前應(yīng)用較為廣泛的推薦算法，它通過對用戶歷史行為數(shù)據(jù)的挖掘發(fā)現(xiàn)用戶的偏好.該算法不需要額外的專業(yè)知識，可以通過統(tǒng)計學(xué)習(xí)的方法得到較好的推薦效果.基于用戶的協(xié)同過濾推薦算法是在購買行為類似的用戶間進行推薦[3]，利用已有的用戶歷史行為數(shù)據(jù)，計算用戶間的相似度，并選擇相似度高的用戶作為最近鄰，根據(jù)最近鄰預(yù)測評分[4].

雖然傳統(tǒng)的基于用戶的協(xié)同過濾推薦算法取得了廣泛應(yīng)用，但仍存在一些缺點，如用戶對項目的實際評分數(shù)據(jù)稀疏，用戶相似度計算不準確，推薦效率不佳[5]等.文獻[6]使用改進的蜂群優(yōu)化聚類算法對用戶進行聚類，在用戶所在簇內(nèi)計算相似度.文獻[7]將用戶進行聚類后使用Slope One算法填充空值，然后使用協(xié)同過濾算法進行評分預(yù)測.文獻[8]將標簽信息融合到Slope One算法，同時參考k近鄰算法思想，選取閾值過濾后的k近鄰項目參與平均評分偏差計算.文獻[9]利用花朵授粉優(yōu)化的模糊聚類算法對用戶聚類，在相似度計算上使用項目偏好信息和評分矩陣相似度進行加權(quán)求和，融合時間因素進行預(yù)測評分.文獻[10]將用戶模型數(shù)據(jù)密度，距離與用戶活躍度相結(jié)合計算權(quán)值，對用戶進行聚類，根據(jù)聚類結(jié)果與用戶評分預(yù)測用戶可能感興趣的對象.文獻[11]通過改造GROUSE算法對評分矩陣進行填充，然后對用戶進行模糊C均值聚類，并在預(yù)測評分計算中引入類別加權(quán)度，對評分進行加權(quán)修正.

上述方法雖然都在一定程度上改善了推薦效果，但未解決數(shù)據(jù)的稀疏性問題，且沒有同時考慮推薦的時效性問題，導(dǎo)致推薦效果不佳.文中提出基于改進K-means和優(yōu)化評分的用戶協(xié)同過濾推薦算法，首先建立用戶-項目評分矩陣，在其中加入項目類別評分，并使用Weight Slope One算法填充評分缺失值以降低數(shù)據(jù)的稀疏性；然后改進K-means聚類算法，在新的評分矩陣里對用戶數(shù)據(jù)進行聚類，對目標用戶，僅在其聚類所在簇內(nèi)計算與其他用戶的相似度，根據(jù)相似度高低得到最近鄰，并在預(yù)測評分計算中加入時間權(quán)重.使用MovieLens-100K數(shù)據(jù)集的實驗結(jié)果表明，所提算法較好解決了評分數(shù)據(jù)稀疏，推薦時效性差的問題，且推薦效果具有明顯提升.

1 相關(guān)知識

1.1 基于用戶的協(xié)同過濾推薦算法

用戶在考慮購買某商品時，常常會聽取有和自己類似需求的其他用戶意見，購買相似用戶高評分的物品.基于用戶的協(xié)同過濾推薦就是根據(jù)此思想將商品推薦給相似的用戶[12].

假如，設(shè)用戶1喜好物品a、b、c、d，用戶3喜好物品a、b、d，由此可以判斷用戶1與用戶3為相似用戶，故用戶1所喜好的物品c也可能被用戶3所喜好，于是將物品c推薦給用戶3.其原理如圖1.

圖1 基于用戶的協(xié)同過濾推薦

1.2 K-means聚類算法

K-means算法是一種常見的、基于劃分的聚類算法，將數(shù)據(jù)劃分為多個不同的簇，使相互距離近的數(shù)據(jù)劃分為一簇，而簇間距離盡可能大.數(shù)據(jù)間的距離使用歐式距離[13]表示為：

(1)

1.3 Weight Slope One算法

Weight Slope One算法是協(xié)同過濾算法的一種，用來預(yù)測用戶對給定項目的評分,文中使用該算法預(yù)測評分矩陣中用戶未評分項的評分，并用得到的預(yù)測評分來替代評分矩陣上對應(yīng)的空值.

算法思想基于線性回歸分析，首先根據(jù)用戶相同評分項計算評分偏差值，再以共同評分數(shù)量表示權(quán)重，并將所得評分偏差結(jié)合用戶評分，最終加權(quán)計算用戶對物品的預(yù)測評分.

2 基于改進K-means和優(yōu)化評分的協(xié)同過濾推薦算法

首先解決評分數(shù)據(jù)的稀疏性問題，然后對用戶使用改進的K-means算法進行聚類，對目標用戶在其聚類所在簇內(nèi)計算相似度得到最近鄰，引入時間權(quán)重計算預(yù)測評分.

2.1 建立用戶評分矩陣

根據(jù)用戶歷史評分建立用戶-項目評分矩陣，假設(shè)有用戶集合U={u1,u2,...,um}，項目集合I={i1,i2,...,in}，則評分矩陣為Rm,n為：

(2)

式中：ri,j為用戶i對項目j的評分.

2.2 融入項目類別評分

實際的用戶評分數(shù)據(jù)往往缺失值較多，這嚴重降低了協(xié)同過濾算法的推薦效果.為此，根據(jù)用戶的評分數(shù)據(jù)，把用戶對每個類別所有項目的評分均值來表示用戶對該項目類別的評分，并將所得項目類別評分加入到用戶-項目評分矩陣中，設(shè)有項目類別集合C={c1,c2,...,cz}，其中rci,y表示用戶i對類別y的評分，此時評分矩陣為：

(3)

2.3 使用Weight Slope One算法填充評分矩陣

使用Weight Slope One算法填充評分矩陣，首先根據(jù)用戶相同評分項計算評分偏差值，再根據(jù)用戶對項目的評分和項目間的評分偏差計算用戶對物品的預(yù)測評分，最后用得到的預(yù)測評分填充評分矩陣中的空值，具體過程如下：

(1)在評分矩陣中，對用戶u，設(shè)其所有已評分項集合為Iu，待評分項為j，Ui,j為對項目i與j均有評分的用戶集合，numi,j為Ui,j內(nèi)用戶的數(shù)量，則項目i和項目j之間的評分偏差計算：

(4)

(2)根據(jù)用戶對項目的評分和項目間的評分偏差，計算Weight Slope One算法中用戶U對項目j的預(yù)測評分：

(5)

(3)在評分矩陣加入項目類別評分后，針對其中的未評分項，使用式(5)計算其預(yù)測評分，并用計算出的預(yù)測評分替代空值，獲得新的評分矩陣.填充評分空值一方面緩解數(shù)據(jù)稀疏性大的問題，另一方面，避免數(shù)據(jù)嚴重失衡導(dǎo)致K-means聚類效果不佳.

2.4 改進初始中心選取的K-means聚類

為了優(yōu)化推薦效果，在計算用戶相似度前先將其進行聚類，盡可能將相似的用戶劃分為一簇，而用戶相似度計算僅考慮該目標用戶所在的簇，以期獲得最佳的最近鄰.

K-means算法中初始聚類中心的選擇很大程度上決定聚類效果好壞，傳統(tǒng)K-means算法隨機選擇初始中心，若初始聚類中心存在離群點或者選擇多個距離接近的點，則聚類效果往往不佳，算法結(jié)果不穩(wěn)定[14].對此做出改進，設(shè)置一個密度距離d和密度閾值q，若一個點為中心，在以距離d為半徑的范圍內(nèi)，點的數(shù)量大于閾值q，則稱該點滿足密度.以此避免離群點，此外，初始聚類中心間距應(yīng)盡量大，以選取K個滿足密度，又彼此間距離盡可能大的點為目標，改進的初始聚類中心選擇方法描述如下：

(1) 在所有滿足密度的點中，隨機選擇一個點作為初始聚類中心.

(2) 在所有滿足密度的點中，選擇與其他初始聚類中心距離(與多個點的距離表示為與這些點距離的乘積)最大的點作為下一個初始聚類中心.

重復(fù)步驟(2)，直到找到K個初始聚類中心.

改進后K-means算法的具體步驟描述如下：

(1) 使用上述方法選取K個初始聚類中心.

(2) 計算所有數(shù)據(jù)到各聚類中心點的距離，并將每個數(shù)據(jù)對象歸類到距離最近的中心點所在簇.

(3) 計算所有簇的平均值并將其設(shè)為新的簇中心點.

(4) 不斷迭代，重復(fù)步驟(2)、(3)，直到K個中心點不再變化或達到最大迭代次數(shù)為止.

該方法選取滿足密度的點可以避免選擇到離群點，并且彼此距離盡可能遠.對用戶數(shù)據(jù)進行聚類后，在目標用戶所在簇內(nèi)計算相似度以獲取最近鄰，以此減小評分數(shù)據(jù)所占內(nèi)存并且提高算法推薦效率和推薦精度.

2.5 引入時間權(quán)重的預(yù)測評分

用戶間的相似程度一般使用皮爾孫系數(shù)[15]表示，其結(jié)果具有歸一化和去中心化的特性.皮爾孫系數(shù)計算公式為：

(6)

傳統(tǒng)的協(xié)同過濾推薦方法往往將用戶的歷史數(shù)據(jù)同等對待，忽略時間因素.然而，現(xiàn)實中用戶的興趣通常不是保持不變，而是隨著時間進行波動，如同人的記憶隨時間削減,因此，用戶最近所評分的項目往往更能體現(xiàn)用戶的興趣.

設(shè)tu,i為用戶u對項目i評分的時間，tu,o為用戶最開始進行項目評分的時間，這兩個時間均以從1970年至今的時間戳表示，以月為單位.定義該評分的權(quán)重Wu,i為：

(7)

該權(quán)重的值在評分時間較近時更大，而在評分較為久遠時值更小.將其引入到相似度計算中能夠更好地體現(xiàn)用戶的相似性，此時相似度為：

(8)

根據(jù)式(8)計算用戶相似度得到最近鄰Nu，根據(jù)最近鄰進行評分預(yù)測，最終預(yù)測評分Pu,i為：

(9)

2.6 算法流程

算法輸入用戶的評分數(shù)據(jù)，輸出目標用戶的預(yù)測評分，具體的算法步驟描述如下：

輸入：目標用戶u，用戶評分矩陣R，用戶評分時間T，聚類個數(shù)K，密度半徑d，閾值q.

輸出：目標用戶u的預(yù)測評分.

Step1：計算用戶對不同項目類別的評分，并將其加入到評分矩陣R中.

Step2：使用Weight Slope One算法，對評分矩陣R中的評分空值，根據(jù)式(5)計算預(yù)測評分，并使用得到的預(yù)測評分替代空值.

Step3：設(shè)置聚類個數(shù)K，密度半徑d，閾值q，使用基于改進初始中心選取的K-means聚類算法對評分矩陣R中的用戶數(shù)據(jù)進行聚類，得到K個簇.

Step4：對目標用戶u，根據(jù)式(1)計算其與各簇的距離并將其劃分到最近的簇中.

Step5：根據(jù)式(8)計算目標用戶u與簇內(nèi)用戶的相似度，取前n個作為u的最近鄰Nu.

Step6：根據(jù)式(9)和最近鄰Nu，計算目標用戶u的預(yù)測評分.

3 實驗與分析

3.1 實驗數(shù)據(jù)

文中采用MovieLens-100K數(shù)據(jù)集進行仿真實驗，該數(shù)據(jù)集包含943個用戶對1 682部影片的共100 000條評分[15]，數(shù)據(jù)密度約為6.3%.取前80%條數(shù)據(jù)作為訓(xùn)練集，后20%條數(shù)據(jù)作為測試集.

3.2 評價指標

采取平均絕對偏差(mean absolute error，MAE)和均方誤差(root-mean-square error，RMSE)作為推薦效果優(yōu)劣的評價指標，二者表示實際評分與預(yù)測評分的差異度，MAE和RMSE值越小，表示算法的推薦效果越佳.設(shè)用戶的實際評分為S={s1,s2,...,sn}，預(yù)測所得評分P={p1,p2,...,pn}，MAE和RMSE計算公式分別為：

(10)

(11)

3.3 實驗結(jié)果與分析

實驗根據(jù)文獻[4]的研究情況，可得MovieLens-100K數(shù)據(jù)集的最佳聚類數(shù)為7，為了獲取最佳的密度半徑d和密度閾值q，計算d和q在不同最近鄰下取不同值時結(jié)果的MAE值平均數(shù).其結(jié)果如表1.

表1 參數(shù)對比

根據(jù)表1，q取140，d取16時聚類效果最佳,將用戶數(shù)據(jù)進行聚類后，根據(jù)用戶相似度計算用戶的最近鄰并預(yù)測評分，分別使用皮爾孫系數(shù)和引入時間權(quán)重的相似度計算方法來預(yù)測評分，計算不同最近鄰下的MAE和RMSE值.結(jié)果如圖2、3.

圖2 不同相似度下的MAE值

圖3 不同相似度下的RMSE值

根據(jù)圖2、3，可以看出在最近鄰取10～50，兩個方法預(yù)測評分的MAE值和RMSE值均呈總體上升態(tài)勢，而引入時間權(quán)重的相似度計算方法在不同最近鄰下效果均優(yōu)于皮爾孫系數(shù)，其平均MAE值降低了約3.7%，平均RMSE值降低了約5.1%.可見加入時間因素后推薦效果具有明顯優(yōu)化.

為了證明文中算法能夠有效提升協(xié)同過濾推薦推薦效果，實驗選取傳統(tǒng)基于用戶的協(xié)同過濾推薦算法(User-CF)、文獻[4]提出的基于用戶聚類與Slope One填充的協(xié)同推薦算法(CFUICF)、文獻[15]提出的優(yōu)化聚類的協(xié)同過濾推薦算法(FPAFCM)、文獻[16]提出的基于用戶模糊聚類的綜合信任推薦算法(FCMTCF)，將這些算法的MAE值和RMSE值做對比.對比結(jié)果如圖4、5.

圖4 MAE對比

圖5 RMSE對比

通過圖4、5可以看出，實驗所選的User-CF、CFUICF、FPAFCM、FCMTCF及文中算法的MAE和RMSE值都隨著最近鄰的變大而漸漸趨于穩(wěn)定.文中算法在不同最近鄰下的MAE和RMSE值幾乎均小于其他算法，比較可得其平均MAE值比上述算法分別低8.5%、5.3%、5.5%、7.9%，而平均RMSE值比上述算法分別低9.1%、5.1%、5.7%、8.4%說明文中算法可以有效提高推薦質(zhì)量.

4 結(jié)論

文中將用戶對項目類別的評分加入到用戶評分矩陣中，并使用Weight Slope One算法預(yù)測的評分來替代未評分項，降低數(shù)據(jù)稀疏性的同時提高了用戶相似度計算的準確性.然后對用戶數(shù)據(jù)使用基于改進初始中心選取的K-means算法進行聚類，將其分為K個不同的簇，對目標用戶在其所在簇內(nèi)計算用戶相似度，提高了算法運行效率，并且獲得更佳的最近鄰.為保證推薦的時效性，將時間權(quán)重加入到用戶評分預(yù)測中.實驗結(jié)果表明，文中算法使推薦的準確性得到有效提高.但文中算法僅考慮用戶的評分數(shù)據(jù)，而忽略用戶屬性，因此未來的工作是將用戶本身的屬性(用戶的年齡，性別，職業(yè)等)也納入算法考慮范圍，以進一步提升算法的準確性和可信性.