基于聚類和SVD++的電影推薦系統的研究六

李瑞 馮鋒

摘要：傳統的協同過濾算法存在著冷啟動、數據稀疏性和可擴展性等關鍵問題，這都使得用戶的歷史播放列表數據信息難以獲得，從而導致推薦電影時精度較低。文章將聚類算法與SVD++模型相結合，通過K-means聚類算法將相似用戶根據評分聚類的同時，并利用SVD++模型對聚類后的每個集群中的評分矩陣進行分解，從而解決相似用戶查找效率低和評分矩陣數據稀疏性的問題，使得電影推薦系統具有較高的精度。

關鍵詞：推薦系統;協同過濾;聚類;SVD++：數據稀疏性

中圖分類號：TP391.3

文獻標識碼：A

文章編號：1006-8228（2020）09-88-04

Research ori movie recommendation system using clustering and SVD++

Li Rui， Feng Feng

（School of Information Engineering， Ningxia University， Yinchuan， Ningxia 750021， China）

Abstract： There are key problems existed in traditional collaborative filtering algorithms， such as cold start. data sparsity andscalability， which make the user's historical data information difficulty to obtain， thereby resulting in lower accuracy of movierecommendation. In order to solve this problem， this paper combines the clustering algorithm with the SVD++ model. By using theK-means clustering algorithm to cluster similar users according to ratings， and using the SVD++ model to decompose the scorematrix in each cluster after clustering. the problems of low search efficiency of similar users and sparse score matrix data will besolved， so that the movie recommendation system can obtain higher accuracy.

Key words： recommendation system; collaborative filtering; clustering; SVD ++; data sparsitv

0引言

如今，推薦系統已經成為互聯網相關服務行業和在線產品銷售公司最有前途的技術之一，YouTube、谷歌、Facebook、淘寶和今日頭條等系統中都有推薦系統的身影。這些推薦系統根據用戶的行為數據來預測用戶的偏好，有助于提高用戶對推廣項目的滿意度，可以看出，推薦系統在一些商業模式中扮演著非常重要的角色。推薦系統常采用協同過濾算法，其具有簡單、易于實現的優點，被廣泛用于各類推薦系統的開發中。協同過濾算法可以分為兩類：基于內存的協同過濾算法和基于模型的協同過濾算法。前者根據用戶或項目之間的相似性進行預測，而后者通過定義一個參數模型來描述用戶與物品，用戶與用戶（或者物品與物品）之間的關系，然后通過優化過程得到模型參數進行預測。盡管協同過濾算法非常經典，但由于其存在冷啟動，數據稀疏和可伸縮性等缺點，使得推薦時難以實現較高的精度。

本文通過用融合聚類算法和降維的協同過濾進行電影推薦，主要采用k-means算法和SVD++模型。其中k-means算法將是一種迭代求解的聚類分析算法，而SVD++是一種降維技術，它可以提高推薦系統的可擴展性[1]。通過k-means算法和SVD++模型分別對偏好相似的用戶進行聚類，對評分矩陣降維，從而提高電影推薦系統的性能，并且克服推薦系統的數據稀疏性和可擴展性問題。

為了結合k-means算法與SVD++模型，我們對電影推薦系統架構進行了設計，系統由三個模塊組成：用戶行為記錄模塊、模型分析模塊和推薦算法模塊。用戶行為記錄模塊主要是保存不同類型的用戶行為數據如瀏覽、收藏等;模型分析模塊主要是根據用戶的行為數據分析用戶潛在的興趣及其程度;推薦算法模塊通過計算將用戶最有可能感興趣的電影推薦給用戶。電影推薦整體架構如圖1所示。

1相關工作

1.1相關研究

在過 去的十幾年里，許多研究人員對推薦算法進行了廣泛的研究來解決推薦系統的數據稀疏性問題。如基于項目遞歸的有爭議相似性概念，并將其與協同過濾算法結合，以解決協同過濾算法的數據稀疏性問題[2];從用戶角度出發，結合用戶屬性相似度、用戶興趣相似度和傳統用戶評價相似度進行推薦來緩解這個問題[3];Yang等人[4]提出了在用戶相似度計算過程中，將離散內容與適當的興趣度相結合，以提高推薦的質量，并且在極端數據稀疏的情況下可以較好地保持良好的性能;Zarzour等人[5]采用改進的k-means聚類算法，并結合主成分分析來提高大數據的推薦精度。Huang等人[6]利用線性回歸模型在用戶一物品評價矩陣中填充未評價數據，緩解了數據稀疏性，找到更可靠的用戶鄰域，從而提高評級預測的準確性。

1.2 SVD++模型背景介紹

傳統的SVD通過矩陣分解的方式將數據最終轉化為特征向量，通過提取數據集合特征值，減少數據運算量，以提高算法準確度。但是，由于在計算過程中存在所占內存空間大、計算時間長的問題，使得其發展過程中出現瓶頸。直到2006年Netflix prize后，Simon Funk在博客上公開發布了一種改進的方法Funk-SVD，該方法后來被稱為潛在因子模型（LFM）。LFM與傳統SVD的最大區別在于傳統的SVD將矩陣分解為三個子矩陣（U∑VT），而LFM模型將復雜的評分矩陣分解為兩個低維矩上考慮了用戶偏見和項目偏置的這些與物品和用戶無關的系統陣P和Q相乘的形式（pTQ），以預測用戶對產品的評估。將LFM模型添加到SVD算法可以提高預測精度并減少所需的存儲空間，并在離線進行訓練過程中提供在線推薦計算所需的數據，可以一定程度上提高推薦效率。后續提出的BiasSVD，又在LSM模型的基礎上考慮了用戶偏見和項目偏置這些與物品和用戶無關的系統因素。而SVD++模型則基于BiasSVD，并考慮到用戶對項目的顯式歷史評分能表現出用戶喜愛程度外的隱藏信息，如瀏覽記錄或者收藏列表，這些隱藏信息等在一定程度上同樣可以從側面反應用戶的偏好，所以，使用SVD++做評分預測更加精確。

2算法研究

我們將聚類算法與SVD++模型相結合，首先采用k-means算法將相似用戶根據評分進行聚類，并對聚類后每一個集群中的評分矩陣根據SVD++模型進行矩陣分解，從而解決矩陣稀疏性問題。在進行矩陣分解后，對每一個集群中再次根據評分聚類，反復迭代直到收斂。最后，根據改進的余弦相似度度量方法，依據評分計算兩個用戶間的相似度，進而形成推薦列表。

2.1相似用戶聚類

k-means算法是一種無監督的聚類算法，通過迭代求解聚類問題。首先隨機選擇k個對象作為初始聚類中心，計算每個對象與每個子聚類中心之間的距離，然后把每個對象分配給最靠近它的聚類中心。用它聚類后，類內的相似度較高，類外的相似度較低。我們使用k-means算法來隨機創建k個集群，每個集群包含的用戶在評級方面有相似的偏好。因此，考慮集群與包含所有用戶的人群相比包含更少的用戶，用戶集群過程有助于提高推薦性能。

為了適應傳統的k-means方法作為推薦系統的相似用戶聚類技術，需對其部分步驟改進。①隨機選取k個用戶作為k個集群的初始中心。②根據用戶與每個集群中心之間的距離，將其余用戶分配到最近的集群。使用相似度度量來計算距離值。③計算用戶集群的新平均值，為每個集群定義新中心。④對每個用戶，重新計算距離，以便定義應該將用戶添加到哪個集群。⑤根據用戶的距離重新分配用戶，直到滿足終止條件。用戶聚類的具體步驟如下。

步驟1：輸入用戶一條目評價矩陣，以及k個聚類，隨機選取k個用戶初始聚類中心;

步驟2：計算聚類中心和用戶之間的距離，將用戶分配到離它最近的集群;

步驟3：對于每個相似用戶的集群，進行新的分區中心的平均值計算，使用新的分區中心將用戶重新分配到新的集群中;

步驟4：重復步驟3，直到算法收斂到一個穩定的分區;

步驟5：輸出k個集群，表示為一個中心項評價矩陣。

如何從初始用戶一項目評分矩陣中獲得新的聚類中心一項目評價矩陣，首先我們可以統計用戶對項目的評價，得到如表1所示用戶一項目評價表。其中，列表示項目，行表示用戶，rij表示用戶i對項目j的評分。

經過用戶聚類算法，可以得到如表2所示的聚類中心一項目評級表。其中，列表示項目，行表示用戶的集群中心，pij表示用戶集群i對項目j的平均評級。

2.2利用SVD++補全矩陣

將用戶通過聚類分成不同的集群后，我們將每個集群里的用戶評分矩陣通過SVD++模型進行降維，對未評價項目進行評分預測來填補矩陣。

在根據評分做推薦的研究中，人們發現一個評分矩陣的固有屬性等和用戶無關。就電影評分矩陣來說，有的人習慣給好評，有的人就比較苛刻評分總是很低。對于電影本身來說，有的電影十分經典，很受歡迎，評分很高，而有的電影小眾不被人們喜歡。koren等人[7]為了讓自己的模型可以體現這個現象，引入基準預測的概念。對于一個未知的評分rui其基準預測具體被定義為如下公式：

bui=μ+bu+bi

（l）其中，μ為所有已知評分的平均值，bu和bi分別代表用戶u和項目i的評分偏置。例如，假設我們需要對用戶Tom觀看電影《蜘蛛俠》的評級進行基準預測，現在整個網站的電影評分μ為3.9星，《蜘蛛俠》比一般的電影要好，所以它的評級往往比一般電影高0.5星，而Tom是一個很挑剔的用戶，他每次給出評分傾向于比平均水平低0.2星。因此，通過計算3.9-0.2+0.5，Tom對《蜘蛛俠》的評級的基線估計將是4.2顆星。

我們采用SVD++模型，通過降維的思想將稀疏的評分矩陣分解為用戶因子矩陣P∈Rf*m和項目因子矩陣Q∈Rfxn相乘形式，其中f<

（2）其中Nu為用戶u所產生隱式反饋行為的項目集合，yj為用戶隱式評價了電影j反映出的個人喜好偏置，Nu|-1/2是一個經驗公式。模型參數bu，bi，qi，pu，yj，通過梯度下降法優化公式（3）獲得：

（3）

最后，通過聚類算法和SVD++模型運算反復迭代趨于穩定后，我們使用改進余弦相似度進行相似用戶的計算，生成推薦列表。改進的余弦相似度計算公式為：

（4）其中，sim（i，j）表示用戶i與用戶j的相似度，Iij是用戶i和用戶j對同一項目都評過分的項目集合。Ii，Ij分別是用戶i和用戶j對項目評過分的集合，Ri，r，Rj，r分別是用戶i，用戶j對項目r的評分，Ri，Rj分別表示用戶i和用戶j的對所有評分項目的平均值。

3結束語

本文通過將k-means算法與SVD++模型相結合。首先，通過將用戶聚類再進行相似用戶查找，比一般直接在所有用戶中查找減少了計算時間，提高了查找效率。其次，利用SVD++模型對聚類后每個集群中的用戶電影評分矩陣進行分解，并在評分預測時考慮了顯示反饋和隱式反饋，緩解數據稀疏性問題，提高了推薦系統的預測精度。此外，我們還通過降維降低了計算復雜性。但由于本系統根據用戶的評分進行聚類，而用戶首次進入系統時所有的電影評分為0，此時不能為用戶準確地推薦適合的電影。因此，在后續的工作中，我們將通過為用戶推薦本系統中較為熱門的電影或結合其他推薦算法解決這個問題。另外，本文目前僅是提出了這樣的想法，下一步我們將會在豆瓣上爬取的數據集和MovieLens等數據集上驗證算法的實際效果，并將算法應用到電影推薦系統中。

參考文獻（References）：

[1] Koren Y， Bell R， Volinsky C. Matrix factorizationtechniques for recommender systems[J]. Computer，2009.42（8）：30-37

[2]張學勝.面向數據稀疏的協同過濾推薦算法研究[D]，中國科學技術大學碩士學位論文，2011.

[3]高倩，何聚厚.改進的面向數據稀疏的協同過濾推薦算法[J].計算機技術與發展，2016.26（3）：63-66

[4] Weiyangj， Shuqin L I， Xinyu L I， et al. CollaborativeFiltering Recommendation Algorithm Based onDiscrete Quantity and User Interests Approach Degree[J]. computer engineering，2018.

[5]Zarzour H， Maazouzi F， Soltani M. et al. An improvedcollaborative filtering recommendation algorithm for bigdata[C]//IFIP International Conference on Computa-tional Intelligence and Its Applications. Springer， Cham，2018：660-668

[6] Huang M， Wang Y， Zhou L. Collaborative FilteringAlgorithm based on Linear Regression Filling[C]//2019 IEEE 3rd Information Technology， Networking，Electronic and Automation Control

Conference（ITNEC）.IEEE，2019：1831-1834

收稿日期：2020-05-21

基金項目：寧夏重點研發計劃重點項目（2018BFG02003）

作者簡介：李瑞（1995-），女，寧夏銀川人，碩士研究生，主要研究方向為信息系統工程。

通訊作者：馮鋒（1971-），男，寧夏銀川人，博士，教授，碩士生導師，主要研究方向：信息系統工程、物聯網技術及應用。