李瑞 馮鋒

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

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

中圖分類號(hào)：TP391.3

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：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ù)測(cè)用戶的偏好，有助于提高用戶對(duì)推廣項(xiàng)目的滿意度，可以看出，推薦系統(tǒng)在一些商業(yè)模式中扮演著非常重要的角色。推薦系統(tǒng)常采用協(xié)同過濾算法，其具有簡(jiǎn)單、易于實(shí)現(xiàn)的優(yōu)點(diǎn)，被廣泛用于各類推薦系統(tǒng)的開發(fā)中。協(xié)同過濾算法可以分為兩類：基于內(nèi)存的協(xié)同過濾算法和基于模型的協(xié)同過濾算法。前者根據(jù)用戶或項(xiàng)目之間的相似性進(jìn)行預(yù)測(cè)，而后者通過定義一個(gè)參數(shù)模型來描述用戶與物品，用戶與用戶（或者物品與物品）之間的關(guān)系，然后通過優(yōu)化過程得到模型參數(shù)進(jìn)行預(yù)測(cè)。盡管協(xié)同過濾算法非常經(jīng)典，但由于其存在冷啟動(dòng)，數(shù)據(jù)稀疏和可伸縮性等缺點(diǎn)，使得推薦時(shí)難以實(shí)現(xiàn)較高的精度。

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

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

1相關(guān)工作

1.1相關(guān)研究

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

1.2 SVD++模型背景介紹

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

2算法研究

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

2.1相似用戶聚類

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

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

步驟1：輸入用戶一條目評(píng)價(jià)矩陣，以及k個(gè)聚類，隨機(jī)選取k個(gè)用戶初始聚類中心;

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

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

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

步驟5：輸出k個(gè)集群，表示為一個(gè)中心項(xiàng)評(píng)價(jià)矩陣。

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

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

2.2利用SVD++補(bǔ)全矩陣

將用戶通過聚類分成不同的集群后，我們將每個(gè)集群里的用戶評(píng)分矩陣通過SVD++模型進(jìn)行降維，對(duì)未評(píng)價(jià)項(xiàng)目進(jìn)行評(píng)分預(yù)測(cè)來填補(bǔ)矩陣。

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

bui=μ+bu+bi

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

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

（2）其中Nu為用戶u所產(chǎn)生隱式反饋行為的項(xiàng)目集合，yj為用戶隱式評(píng)價(jià)了電影j反映出的個(gè)人喜好偏置，Nu|-1/2是一個(gè)經(jīng)驗(yàn)公式。模型參數(shù)bu，bi，qi，pu，yj，通過梯度下降法優(yōu)化公式（3）獲得：

（3）

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

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

3結(jié)束語(yǔ)

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

參考文獻(xiàn)（References）：

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

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

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

基金項(xiàng)目：寧夏重點(diǎn)研發(fā)計(jì)劃重點(diǎn)項(xiàng)目（2018BFG02003）

作者簡(jiǎn)介：李瑞（1995-），女，寧夏銀川人，碩士研究生，主要研究方向?yàn)樾畔⑾到y(tǒng)工程。

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