基于K-means的矩陣分解推薦算法

張榮梅, 陳 彬, 張 琦

(河北經貿大學 信息技術學院, 石家莊 050061)

0 引 言

當下，隨著大數據時代的來臨，信息資源過度膨脹，形成了“信息爆炸”的現象。為了緩解這種情況帶來的信息過載、數據冗余、選擇困難等問題，越來越多的專家學者已然開始關注起推薦系統領域的研究。推薦系統是通過分析用戶的歷史數據，以及項目等其它輔助信息，推測出用戶潛在的偏好需求，進而為用戶提供個性化的項目推薦。常見的傳統推薦技術是基于內容的算法、基于協同過濾的算法及混合算法[1]。其中，協同過濾算法應用較為廣泛，Goldberg等人[2]于1992年提出了協同過濾的概念，最初應用在Tapestry System上用于過濾電子郵件。這是通過引入其它用戶的興趣來對當前用戶進行推薦，只是涉及用戶的歷史交易記錄，而不依賴用戶和項目的屬性特征。但協同過濾算法存在數據稀疏[3]和冷啟動問題[4]。于洪等人[5]為了更好地解決物品冷啟動問題，提出了一種附加用戶時間權重的算法，對用戶評論時間與項目發布時間加以計算研究，但由于很多標準數據集中缺少時間戳的屬性，其作用范圍有限。針對于此，為了改進協同過濾算法，本文將K-means聚類算法與矩陣分解技術相結合，提出一種基于K-means的矩陣分解推薦算法(Matrix Decomposition Based on K-means，KMMD)，引入了用戶屬性信息，在提高推薦精度的同時，有效改善用戶冷啟動問題。

1 基于K-means的矩陣分解推薦算法(KMMD)

1.1 Funk-SVD矩陣分解算法

基于內容的推薦和基于用戶畫像的推薦[6]都是聚焦于待推薦用戶自身的屬性信息或交易記錄，并沒有考慮過其它用戶的數據是否會對當前用戶產生推薦影響，在召回率和精確度上不能進一步提高。而矩陣分解[7]作為協同過濾的一種重要方法，不僅將待推薦用戶自身的屬性考慮在內，還吸收借鑒了其它用戶的數據信息，來實施推薦。且矩陣分解算法將龐大的用戶-項目評級矩陣分解為多個矩陣存儲，大大減緩了磁盤存儲壓力。

矩陣分解采用Funk-SVD，是通過將用戶-項目評級矩陣Rm×n進行分解，得到可以表示用戶和項目特征的2個低維的抽象隱因子矩陣：Um×k表示m個用戶的k維隱因子矩陣，Vn×kT表示n個項目的k維隱因子矩陣，使得Um×k·Vn×kT≈Rm×n。使用重構后的評級矩陣來預測用戶對未知項目的評分。對于矩陣中的缺失項，在參數更新時選擇忽略不計，不對其進行操作，而只針對有效數據進行參數訓練。

(1)

其中，損失函數由誤差平方和正則化項組成，引入正則化項可以防止訓練結果的過擬合。

而訓練過程是使用梯度下降降低損失函數，其數學公式可表示為：

(2)

(3)

其中，α是學習率參數，表示每次更新的快慢。

傳統的矩陣分解算法多采用傳統的SVD矩陣分解方式[8]。傳統SVD分解后會得到3個矩陣：U、∑和V。其中，∑是一個對角矩陣，表示U和V矩陣在每個維度上的重構重要度可通過該對角矩陣進行降維，但存在對矩陣求逆等操作，致使計算復雜度高。而本文實驗采用的是Funk-SVD分解方式，借鑒線性回歸的思想，通過最小化均方誤差來尋求最優的用戶和項目的隱含向量表示，其維度可直接調整。Funk-SVD用2個矩陣就可以實現SVD三個矩陣的重構效果，在一定程度上提高了運算效率。

1.2 K-means聚類

由于傳統矩陣分解算法只使用用戶對項目的評級信息，其推薦精度上限難以進一步提升，所以引入用戶屬性信息，經K-means聚類分析再進行矩陣分解運算，提高算法推薦能力。K-means是一種將數據按策略劃分為某幾種類別的聚類算法[9]，其中K表示聚類的類別種數，即質心的數量，means表示均值。K-means聚類之前的預處理過程可分述如下。

(1)提取用戶基本屬性信息，User=(Age,Gender,Occupation)，構建用戶屬性矩陣U。

(2)對于非數值的離散型數據，進行one-hot編碼[10]數值化處理。one-hot編碼是將原某類型屬性按照其種類進行編碼，編碼結果是只有一位為有效值1，其余位都是0。年齡屬性已經是數值型屬性，所以不做處理。性別是二元屬性，分為“男”和“女”，所以分別編碼為[0]和[1]。職業屬于標稱屬性，包含多種類別，按照類別總數S構建長度為S的編碼串，并由先后出現順序為其置“1”編碼，在MovieLens-100K數據集中共出現有21種職業類型，數據集中最先出現的“technician”職業的one-hot編碼為[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1]，緊接著出現的“writer”職業的one-hot編碼為[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0]，以此類推。然后所有屬性拼接組合成稀疏的用戶屬性向量，對于“年齡=24，性別=男，職業=技術員”的用戶User_a=(24, man, technician)，經如上處理后得到的用戶屬性向量為User_a′=[24 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1]。

(3)embedding處理。經由one-hot編碼后的數據必然是稀疏的，所以將其進行embedding處理，即是將原稀疏向量與固定轉換矩陣做內積變換，轉化為稠密向量，即：

(4)

得到由用戶稠密屬性向量構建的用戶屬性矩陣，就可以進行K-means聚類分析了。算法1的設計步驟見如下。

算法1K-means。用于聚類劃分的K-均值算法，其中每個簇的中心(質心)都用簇中所有對象元素的均值來表示[11]

輸入：K表示簇的數目；D為包含n個對象元素的數據集

輸出：K個簇的集合

(1)從D中任意選取K個對象作為初始簇的中心；

(2)repeat

(3)根據簇中對象元素的均值，將每個對象分配到最相似的簇；

(4)更新簇均值，即重新計算每個簇中對象的均值；

(5)until不再發生變化。

采用K-means聚類算法提前對用戶進行聚類分析，可減小構建的用戶-項目評級矩陣規模，若不做預處理，則需要對全部用戶和全部項目信息構建評級矩陣，這樣在矩陣分解時會嚴重降低算法效率，占用大量內存。而通過聚類構建小規模的近鄰用戶-項目矩陣，可加快矩陣分解計算，利于算法模型的整體效率，且額外的聚類代價遠遠小于大規模矩陣分解的消耗代價。

K-means聚類處理為當前用戶構建了近鄰集合，由于興趣偏好相似的用戶傾向于購買相同項目的思想，所以在近鄰用戶中進行數據分析，可有效提高推薦的準確度，實驗證明這樣的設計思路的確對推薦中召回率和精確度有提升效果。

1.3 KMMD算法設計

本文將K-means算法與Funk-SVD矩陣分解算法結合，提出了KMMD算法。算法2的設計流程詳見如下。

算法2KMMD, 基于K-means的矩陣分解算法

輸入：User表示包含m個用戶的用戶屬性(User)數據集；Ua表示當前待推薦用戶的屬性信息；Ratings表示包含m個用戶對n個項目的部分評級數據集；L表示推薦列表長度；K表示聚類簇數

輸出：針對用戶Ua的推薦列表List

(1)對User進行K-means聚類分析，劃分為K個簇：C1,C2,...,CK；

(2)ifUa== 老用戶 then

(3)提取Ua所在簇Ca的所有對象元素，并從Ratings中篩選出這些對象元素的評級數據，構建近鄰用戶-項目評級矩陣R；

(4)將R進行Funk-SVD分解，得到U和V兩個低秩矩陣；

(5)矩陣重構：R’ =U·V；

(6)在重構評級矩陣R’中找到對Ua的重構預測向量ra；

(7)else將Ua與簇中心求相似度，找到Ua歸屬的簇Ca；

(8)從Ratings中篩選出Ca簇中對象元素的評級數據，構建近鄰用戶-項目評級矩陣R；

(9)將R進行Funk-SVD分解，得到U和V兩個低秩矩陣；

(10)矩陣重構：R’=U·V；

(11) 求得Ua與Ca中各對象元素的相似度Sima,i(i∈Ca)；

(12) 加權計算求得Ua的預測評級：

(5)

(13)end if

(14)對ra中各個項目預測值排序，選出前L個項目組成推薦列表List。

2 實驗與結果分析

本實驗采用數據集MovieLens-100K，使用召回率和精確度作為模型評價指標，進行參數影響及參數確定的實驗，得到效果最佳的KMMD算法模型，并將其與2種傳統算法CBbyPortrait和MFbySVD做了對比實驗。研究可得解析詳述如下。

2.1 數據集

基于MovieLens數據集[12]是由明尼蘇達大學的Grouplens研究項目收集整理。數據集獲取地址：http://files.grouplens.org/datasets/movielens/。實驗具體選用的是MovieLens-100K。MovieLens-100K數據集包含943名用戶對1 682部電影的10萬條評分記錄，評分采用5分制(1，2，3，4，5)。該數據集主要包含3個文件：用戶數據文件(u.user)、項目數據文件(u.item)和評分文件(u.data)，其中u.user包含用戶的人口統計信息，字段有：用戶標識(user id)、年齡(age)、性別(gender)、職業(occupation)和郵編(zip code)；u.item包含電影項目的信息，字段有：電影標識(movie id)、電影標題(movie title)、上映日期(release date)、視頻發布日期(video release date)、數據源鏈接(IMDb URL)和類別屬性(genres)；u.data包含完整的評級數據，字段有：用戶標識(user id)、項目標識(item id)、評分(rating)和時間戳(timestamp)。

2.2 模型評估指標

本文采用混淆矩陣[13]中的精確度(Precision)和召回率(Recall)進行算法模型評估。涉及到的參數和計算方法如下：TP(True Positive)表示將正類預測為正類；TN(True Negative)表示將負類預測為負類；FP(False Positive)表示將負類預測為正類，也稱為誤報；FN(False Negative)表示將正類預測為負類，也稱為漏報。

其中，召回率(Recall)和精確度(Precision)的計算公式為：

(6)

(7)

2.3 參數選取

為了得到KMMD算法的最佳效果，首先進行控制變量實驗，測試重要參變量的取值變化對算法效果的影響。KMMD算法的重要參變量有3個：K-means聚類的聚類種數K；矩陣分解的訓練步數Steps；推薦列表長度L。而Funk-SVD的學習率參變量α依據經驗設定為0.000 2。實驗隨機選取MovieLens-100K數據集的80%作為訓練集，余下20%作為測試集。研究中，將分3組進行控制變量實驗。研究內容詳見如下。

(1)Steps固定取50，L固定取10。觀察參數K的變化影響，結果如圖1所示。

(a) 粗粒度范圍

(b) 細粒度范圍

圖1中，實線實心倒三角表示精確度的變化趨勢，虛線實心圓圈表示召回率的變化趨勢。圖1(a)是在[5,100]范圍內粗粒度驗證K值變化對實驗精度的影響，可以看到，隨著K值逐漸增大，召回率和精確度都是先增后降的趨勢，其極值在K取25-35的范圍內取得。為進一步獲取最佳K值的推薦效果，圖1(b)給出了在[25,35]閉區間范圍內細粒度實驗仿真。由實驗結果可知，當K值取29時，算法的當前推薦效果最佳。

(2)K固定取29，L固定取10。觀察參數Steps的變化影響，結果如圖2所示。

圖2 Steps值變化影響

由實驗結果可知，隨著Steps值的增大，召回率和精確度總體趨勢都是下降的，當Steps值取[80,110]區間值時，其實驗效果較好，為方便實驗進行，將Steps值取為100。

(3)Steps固定取100，K固定取29。觀察參數L的變化影響，結果如圖3所示。

圖3 L值變化影響

由實驗結果可知，隨著L值的增大，召回率會呈現遞增趨勢，而精確度總體是呈現遞減趨勢，最終逐漸收斂平穩。為確定L取具體何值時，可使推薦的整體效果較好，研究中還對圖3實驗結果進行F度量表示，即：

(8)

F度量賦予了召回率和精確度相等的權重，是兩者的調和均值。其結果如圖4所示。可知在L值取15時，F值最高，綜合推薦效果最好。

圖4 F度量值變化

2.4 對比實驗

為了驗證KMMD算法模型的真實效果，選取了2種推薦算法模型與本文提出算法進行比較。這2種算法的設計表述如下。

(1)CB(Content-based Recommendation)：基于內容的推薦模型，通過召回用戶日志文件獲取與用戶有過交互的項目信息，再根據項目的屬性特征學習用戶的偏好興趣，可構建用戶畫像，并以此計算用戶與待推薦項目匹配度，推薦與其過去已購買過物品相似度高的商品。

(2)MF(Matrix Factorization)：傳統基于矩陣分解的推薦模型，通過用戶對項目的顯式評分數據構建用戶-項目評分矩陣，使用SVD奇異值分解矩陣后再進行重構，預測用戶對未購買過的商品的評分，進行推薦。

對比實驗在MovieLens-100K數據集下進行，使用了十折交叉驗證法。根據控制變量實驗結果，對KMMD算法的參數選取了K=29，Steps=100，L=15。實驗結果對比見表1。對表1分析后可知，其研究結果的重點陳述見如下。

(1)召回率表現的是推薦效果的靈敏性，從該值的角度來分析，KMMD算法的效果最好，其相較于CB算法提升了15.64%，相較于MF算法提升了154%。說明在靈敏性上，KMMD算法有了很大的提升。

(2)從精確度來看，KMMD算法的效果遠高于其它兩個算法，比CB提升了30.43%，比MF提升了103%。可見，KMMD算法在推薦的精確度上也有很不錯的表現。

由實驗可得，KMMD算法在召回率和精確度上都有很大提升，能為用戶提供更準確的推薦。

表1 召回率和精確度對比

2.5 模型預測

該部分通過實驗驗證提出的KMMD算法可以對新用戶進行有效推薦。實驗是在包含943名用戶的MovieLens-100K數據集基礎上，仿照其數據格式，構造了2名用戶基本屬性數據作為新用戶，作為用戶冷啟動實驗對象，數據如下：

(1)用戶a：年齡=24，性別=男(M)，職業=技術員(technician);

(2)用戶b：年齡=50，性別=女(F)，職業=作家(writer)。

實驗結果見表2。

表2 用戶冷啟動預測

實驗結果說明，KMMD算法可以對新用戶進行項目推薦，結果以評級高低排序。KMMD算法有效改善了用戶冷啟動問題。

3 結束語

將聚類算法與協同過濾思想相結合，提出了一種基于K-means的矩陣分解推薦算法。首先通過實驗分析不同參數對KMMD算法的召回率和精確度變化影響，得出算法的高效率參數配置。并進行對照實驗，比較傳統推薦算法與KMMD算法在MovieLens公開數據集上的實驗效果，得出結論，融合K-means聚類后的矩陣分解算法確實有助于推薦準確度的提高，且在引入用戶屬性數據的條件下，有效改善了用戶冷啟動問題。但該算法對項目冷啟動問題還難以處理。后續工作是將深度學習技術與推薦算法相融合，構建多種推薦算法的組合排序，力求進一步提升推薦算法的準確度，并有效解決項目冷啟動問題。