李瑞 馮鋒

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

關(guān)鍵詞：推薦系統(tǒng);協(xié)同過濾;聚類;SVD++：數(shù)據(jù)稀疏性

中圖分類號：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引言

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

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

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

1相關(guān)工作

1.1相關(guān)研究

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

1.2 SVD++模型背景介紹

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

2算法研究

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

2.1相似用戶聚類

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

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

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

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

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

步驟4：重復(fù)步驟3，直到算法收斂到一個穩(wěn)定的分區(qū);

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

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

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

2.2利用SVD++補全矩陣

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

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

bui=μ+bu+bi

（l）其中，μ為所有已知評分的平均值，bu和bi分別代表用戶u和項目i的評分偏置。例如，假設(shè)我們需要對用戶Tom觀看電影《蜘蛛俠》的評級進行基準預(yù)測，現(xiàn)在整個網(wǎng)站的電影評分μ為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所產(chǎn)生隱式反饋行為的項目集合，yj為用戶隱式評價了電影j反映出的個人喜好偏置，Nu|-1/2是一個經(jīng)驗公式。模型參數(shù)bu，bi，qi，pu，yj，通過梯度下降法優(yōu)化公式（3）獲得：

（3）

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

（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結(jié)束語

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

參考文獻（References）：

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

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

[3]高倩，何聚厚.改進的面向數(shù)據(jù)稀疏的協(xié)同過濾推薦算法[J].計算機技術(shù)與發(fā)展，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

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

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

通訊作者：馮鋒（1971-），男，寧夏銀川人，博士，教授，碩士生導師，主要研究方向：信息系統(tǒng)工程、物聯(lián)網(wǎng)技術(shù)及應(yīng)用。