基于用戶聚類和時間隱語義模型的推薦算法研究*

吳 祺 聶文惠

（江蘇大學計算機與通信工程學院 鎮(zhèn)江 212000）

1 引言

隨著社會的發(fā)展和網(wǎng)絡技術的不斷進步，信息數(shù)據(jù)呈現(xiàn)爆發(fā)式增長，傳統(tǒng)的協(xié)同過濾推薦算法已經(jīng)無法滿足人們?nèi)粘５男枨?，人們無法從海量的數(shù)據(jù)中快速獲得自己想要的信息，即產(chǎn)生“信息過載”問題［1］。如何更準確更快速地幫助用戶獲取有效信息成為當前研究的熱點，個性化推薦也就應運而生。

協(xié)同過濾算法［2］是目前推薦系統(tǒng)中應用最為廣泛最為成熟的算法之一，它的核心思想是通過尋找擁有相同興趣愛好的用戶繼而通過相似用戶的興趣愛好為該用戶推薦可能感興趣的信息。隨著用戶數(shù)量和物品數(shù)量呈現(xiàn)指數(shù)型增長，用戶對物品的評分數(shù)據(jù)變得稀疏，傳統(tǒng)的協(xié)同過濾算法在處理稀疏矩陣時推薦準確率較低［3］。

用戶聚類是通過聚類算法將用戶對象的集合分成由類似對象組成的多個類的過程。K-means算法是常見的聚類算法之一，其將具有相同屬性特征的用戶歸為一類［4］，這樣一方面使得無歷史行為的新用戶獲得推薦，即解決“冷啟動”問題，另一方面降低了矩陣稀疏程度和矩陣規(guī)模，提高隱語義模型預測的準確度。

針對數(shù)據(jù)稀疏性問題，國內(nèi)外學者提出多種解決方法。Su、Khoshgoftaar 等［5］用線性回歸、均值填補和貝葉斯分類等多種方法以緩解用戶-評分矩陣的稀疏問題，但使用均值填補稀疏矩陣給用戶評分預測帶來較大的誤差；Hao、Li等［6］提出利用用戶評分偏好相似性和特征矩陣來預測商品評分，該方法當數(shù)據(jù)非常稀疏時，算法的穩(wěn)定性和準確性下降。在解決稀疏性問題中矩陣分解算法也具有較好的效果，其中SVD 算法是最早的矩陣分解算法，由Billsus 等［7］將其引入推薦系統(tǒng)。該算法計算復雜度較高，難以應用于大規(guī)模評分矩陣［8］。2006 年Simon Funk 在博客上發(fā)布Funk-SVD 算法，后來被稱為隱語義模型（LFM）［9］。隱語義模型是近幾年推薦系統(tǒng)領域較為熱門的話題，它主要是利用矩陣分解建立隱含特征與用戶和隱含特征與物品之間的關系，進而通過隱含特征將用戶與物品聯(lián)系起來［10］，最終預測用戶對物品的偏好，大大緩解了協(xié)同過濾算法由于數(shù)據(jù)稀疏引起的推薦準確率低的問題。當然該模型還存在著一些不足，如沒有考慮時間因素對用戶評分的影響。

本文將K-means 聚類算法和隱語義模型相結合，提出基于用戶聚類和時間隱語義模型的推薦算法（K-T-LFM）。該算法既克服了新用戶冷啟動和數(shù)據(jù)稀疏性的問題，同時也考慮了時間因素對用戶興趣的影響。

2 基于用戶聚類和時間隱語義模型的推薦算法

基于用戶聚類和時間隱語義模型的推薦算法（K-T-LFM）融合了K-means 聚類算法和隱語義模型，本文首先介紹用戶聚類和隱語義模型，然后提出使用融合時間函數(shù)的隱語義模型對缺失矩陣進行填充，基于目標聚類用戶通過協(xié)同過濾算法產(chǎn)生推薦。

2.1 用戶聚類

用戶聚類主要是根據(jù)用戶的特征屬性對用戶進行聚類，從而找到相似的用戶群體。日常生活中具有相近特征屬性的用戶往往會有相似的興趣愛好，不同特征屬性類別的用戶往往興趣愛好差異性較大［11］?？紤]到用戶的特征屬性是相對客觀穩(wěn)定的，本文通過引入用戶特征進行聚類來降低不相關用戶對目標用戶的影響。同時在用戶初次登陸APP應用時，通過用戶的屬性特征聚類可以解決冷啟動的問題，為該用戶推薦相似用戶的興趣愛好。

考慮到用戶的特征屬性比較多，本文依據(jù)用戶以下幾個主要特征進行聚類［12］：

1）性別。不同性別的人大體上興趣偏好差異很大，男女可以分別記為｛1，2｝；

2）年齡。人在不同年齡段有不同的生活履歷和遭遇，因此不同年齡的人對生活的態(tài)度也不同，可以將年齡段分為12 歲以下，13-17 歲，18-29 歲，30-39 歲，40-49 歲，50-59 歲，60 歲以上，分別記為｛0，1，2，3，4，5，6｝；

3）職業(yè)。不同職業(yè)的人有不同的價值觀念和興趣愛好，看待事物的角度也不同，按照職業(yè)的不同分別記為｛0，1，2，…，n｝。

建立用戶特征數(shù)據(jù)表，記錄用戶的性別，年齡，職業(yè)信息，然后采用最大-最小準則算法確定初始質心改進的K-means算法進行聚類。

改進的K-means算法用戶聚類過程：輸入：用戶特征數(shù)據(jù)集u，聚類個數(shù)k

輸出：k個依據(jù)用戶特征數(shù)據(jù)劃分的聚類

1）定義聚類的個數(shù)k；

2）隨機選擇一個點作為質心，選取距離這個點最遠的點作為第二個質心，然后計算每個點到兩個質心的距離，選取距離較小的加入到集合V 中，在集合V 中選取距離最遠的點作為下一個質心，以此類推，直至選擇第k個質心；

3）計算其它點到每個質心的距離，選擇距離最近的質心作為一類；

4）計算每個聚類的中心點，作為新的質心；

5）Repeat 3），4）；

6）達到最大迭代次數(shù)或者質心基本不發(fā)生變化則用戶聚類結束。

通過用戶聚類不僅解決了用戶初次登錄冷啟動的問題，同時通過降低用戶數(shù)據(jù)的維度，緩解數(shù)據(jù)稀疏性，提高了使用隱語義模型預測的準確率。

2.2 隱語義模型

隱語義模型主要是針對SVD 算法填充稀疏矩陣需要大量存儲空間的缺點改進而來，它能有效地挖掘用戶與物品間的隱藏關系。將其應用在推薦系統(tǒng)的預測中具有預測精度高和占用內(nèi)存小的優(yōu)點。該模型通過矩陣分解將用戶評分矩陣分解為兩個低維評分子矩陣，分別為用戶隱含特征矩陣和物品隱含特征矩陣：

其中P∈Rf×m,Q∈Rf×n分別為用戶隱含特征矩陣和物品隱含特征矩陣。用戶u 對物品i的評分預測公式為

其中rui表示用戶u對物品i的評分，puf表示用戶u的興趣和第f個隱類的關系，qif表示電影i和第f個隱類的關系。

定義其損失函數(shù)為

其中λ(| |pu||2+||qi||2)是為了防止過擬合，λ是正則化參數(shù)。但是隨著時間的推移，用戶的興趣愛好可能發(fā)生變化，進而影響了推薦的準確率。

2.3 時間隱語義模型

2.3.1 時間權值的選擇

德國心理學家艾賓浩斯提出人類遺忘曲線［13］，主要依據(jù)是：隨著時間的推移，人的記憶會隨之發(fā)生變化，曲線描述了人類大腦對事物的遺忘規(guī)律，用戶對新事物的興趣隨著時間推移同樣遵循遺忘規(guī)律。

考慮到時間因素對用戶興趣的影響，采用指數(shù)時間函數(shù)來表示，突出用戶近期興趣偏好所占的權重［14］，考慮到存在一些經(jīng)典的物品隨著時間推移依然受歡迎，所以在傳統(tǒng)的指數(shù)函數(shù)上進行了一定的優(yōu)化，使得隨著時間的推移，用戶對物品的興趣并不會最終趨近于0。該時間函數(shù)定義如下：

其中，Tu,i表示用戶u對項目i的評分時間，Tk表示過去的某一個固定時間，時間函數(shù)f(tu,i)的取值范圍是（0.5，1），表示用戶興趣的時間權重。

2.3.2 融合時間因素的隱語義模型

傳統(tǒng)的隱語義模型在預測用戶評分時沒有考慮時間因素的影響，因此在用戶隱含特征子矩陣加入式（4）的時間函數(shù)。結合式（2）用戶u 在tu,i時間點對物品i的評分預測公式為

其中，puf(tu,i)表示隨時間變化的用戶偏好的特征子矩陣，其值用以下公式表示：

其中，a為調節(jié)時間函數(shù)的參數(shù)。

本文在用戶隱含特征子矩陣中加入時間函數(shù)，考慮了用戶對于未評分物品的興趣隨時間產(chǎn)生的變化，避免了填充缺失矩陣時使用全局平均值或評分中位值帶來的誤差。

2.4 基于用戶聚類和時間隱語義模型的推薦算法

本文結合K-means 算法和隱語義模型進行推薦，基于用戶的屬性特征通過改進的K-means算法對用戶進行聚類，對每個用戶聚類使用融合時間函數(shù)的隱語義模型進行預測，最后結合傳統(tǒng)的協(xié)同過濾推薦算法進行推薦。

基于用戶聚類和時間隱語義模型的推薦算法（K-T-LFM）具體流程如下：

輸入：用戶u，評分矩陣R，用戶u 對物品i 的評分時間戳t，用戶分類的簇數(shù)k。

輸出：向目標用戶推薦的N個物品。

步驟1：結合用戶的特征屬性使用最大-最小準則改進的K-means算法對用戶進行聚類，將具有相似特征屬性的用戶聚為一類；

步驟2：根據(jù)用戶聚類構建相應的用戶-物品評分矩陣，在各評分矩陣中使用融合時間函數(shù)的隱語義模型，對聚類中數(shù)據(jù)缺失的用戶-物品評分矩陣進行填充預測；

步驟3：基于完成填充預測的用戶-物品評分矩陣，計算用戶間的相似度，選出M 個最相似用戶作為最近鄰居；

步驟4：根據(jù)M 個最近鄰居的評分數(shù)據(jù)來預測當前用戶u對未評分物品的評分數(shù)據(jù)；

步驟5：選擇預測評分topN 的物品向用戶推薦。

3 實驗與分析

3.1 數(shù)據(jù)集簡介

本文采用的數(shù)據(jù)集是來自美國明尼蘇達大學GroupLens 小組提供的MoviesLens 數(shù)據(jù)集［15］。主要是使用MovieLens 數(shù)據(jù)集中的ratings.data 和movie.data兩個文件數(shù)據(jù)，其中rating.dat文件包含了6040個用戶對3900 部電影的1000209 條評分，users.dat文件包含6040 個用戶的性別、年齡、職業(yè)等信息。整個數(shù)據(jù)的評分矩陣稀疏度為94.88%。實驗過程中，將數(shù)據(jù)集按照70%和30%的比例分為訓練集和測試集。

3.2 評價指標

本文采用的評價指標是均方根誤差（RMSE），RMSE［16］是衡量系統(tǒng)性能的一個重要指標，RMSE值是預測值與真實值偏差的平方與觀測次數(shù)n 比值的平方根，用來衡量觀測值同真值之間的偏差，因此RMSE 的值越低表示算法的預測準確率越高。其公式如下：其中，|U|是測試集提供的評分總數(shù)量，rui是用戶u對物品i的實際評分，rui是預測評分。

3.3 實驗結果

1）隱特征維度L對RMSE的影響

實驗中通過確保LFM 模型其它參數(shù)不變的情況下（其中學習速率為0.02，正則化參數(shù)λ=0.05，迭代次數(shù)n=50，調節(jié)參數(shù)a=0.5），改變LFM 的隱特征維度L，觀察預測誤差RMSE的值，實驗分布曲線如圖1所示。

圖1 不同隱特征維度L對RMSE影響

由圖1 可以看出，當隱特征維度小于40 時，RMSE 值隨著隱特征維度的增加而減小，當隱特征維度L 大于40 之后，LFM 模型的RMSE 的值趨近于穩(wěn)定，所以實驗中設置L為40。

2）調節(jié)參數(shù)a和迭代次數(shù)n對RMSE的影響

實驗中將LFM模型的隱特征維度L設置為40，學習速率為0.02，正則化參數(shù)λ=0.05，觀察調節(jié)參數(shù)a 和迭代次數(shù)n 對RMSE 的影響，實驗分布曲線如圖2。

圖2 不同調節(jié)參數(shù)a對RMSE的影響

由圖2可以看出，隨著迭代次數(shù)n的增加，調節(jié)參數(shù)取0.5 時RMSE 始終最低，且迭代次數(shù)n 在40之后值趨于穩(wěn)定，所以設置LFM 模型的調節(jié)參數(shù)為0.5，迭代次數(shù)為50。

3）聚類個數(shù)K對RMSE值的影響

實驗中在保持設定的LFM 模型參數(shù)不變的情況下，改變聚類的個數(shù)K，觀察聚類個數(shù)K 對RMSE的影響，實驗分布曲線如圖3。

圖3 不同聚類個數(shù)K對不同算法RMSE的影響

圖3 可以看出，在保持目前參數(shù)的情況下，隨著聚類個數(shù)的增加，考慮時間因素的算法（K-T-LFM）的RMSE 值始終低于未考慮時間因素的算法（K-LFM），所以考慮時間因素的隱語義模型整體性能優(yōu)于傳統(tǒng)的隱語義模型，并且聚類個數(shù)在20～25之間準確率最高，設置聚類個數(shù)為25。

4）不同算法的RMSE值比較

實驗中在保持設定的LFM 模型的參數(shù)和聚類個數(shù)K 不變的情況下，改變最近鄰居數(shù)M，觀察隨著最近鄰居數(shù)M 的增加不同算法的RMSE 值，實驗分布曲線如圖4。

圖4 不同鄰居個數(shù)下不同算法的RMSE比較

采用多種算法對數(shù)據(jù)集進行測試，隨著最近鄰居個數(shù)M 的增加，從圖4 中可以看出，本文提出的基于用戶聚類和時間隱語義模型的推薦算法（K-T-LFM）的RMSE 值均小于隱語義模型（LFM）和基于用戶的協(xié)同過濾算法（UCF），可以說明其在準確率方面能達到比較好的效果，優(yōu)于其它兩種算法。

4 結語

針對傳統(tǒng)推薦算法數(shù)據(jù)稀疏情況下推薦準確率低的問題，本文提出融合K-means算法和隱語義模型來預測填補稀疏矩陣，同時考慮時間因素對用戶的興趣偏好的影響，在隱語義模型中融入時間函數(shù)，提出基于用戶聚類和時間隱語義模型的推薦算法（K-T-LFM）。通過實驗對比，本文提出的混合推薦算法相較于其它算法具有較好的準確度。后續(xù)研究工作中考慮將物品信息融入算法中，以進一步提高算法推薦的準確度。