一種基于稀疏分段的協(xié)同過濾推薦算法

賀懷清 計瑜 惠康華 劉浩翰

摘 ?要： 針對數(shù)據(jù)強稀疏性嚴(yán)重制約協(xié)同過濾算法推薦準(zhǔn)確性的問題，提出基于稀疏分段的改進方法。首先利用基于迭代預(yù)測的支持向量回歸在解決小樣本高維數(shù)據(jù)中的優(yōu)勢，對稀疏的[U?I]矩陣中相對弱稀疏的密集數(shù)據(jù)部分預(yù)測缺失評分，然后使用基于項目的插補協(xié)同過濾方法預(yù)測剩余數(shù)據(jù)的缺失評分。在多個公開數(shù)據(jù)集中的實驗表明，該方法適用于強稀疏數(shù)據(jù)集的推薦，與基于項目協(xié)同過濾比較可取得較好的預(yù)測結(jié)果。

關(guān)鍵詞： 稀疏分段; 支持向量回歸; 基于項目的推薦; 協(xié)同過濾; 數(shù)據(jù)稀疏性; 小樣本

中圖分類號： TN911.1?34 ? ? ? ? ? ? ? ? ? ? ? ?文獻標(biāo)識碼： A ? ? ? ? ? ? ? ? ? ? ? ? 文章編號： 1004?373X（2019）09?0090?05

A collaborative filtering recommendation method based on sparseness segmentation

HE Huaiqing， JI Yu， HUI Kanghua， LIU Haohan

（College of Computer Science and Technology， Civil Aviation University of China， Tianjin 300300， China）

Abstract： Since the strong sparsity of data seriously affects the recommendation accuracy of collaborative filtering algorithm， an improved method based on sparseness segmentation is put forward. The support vector regression based on iterative prediction is used to estimate the missing scores for the relatively?weak sparse density data of sparse [U?I] matrix， which has the advantage in predicting the high?dimensional small?sample data. The item?based imputative collaborative filtering method is employed to predict the missing scores of residue data. The experimental results of several public datasets show that the method is suitable for the recommendation of strong?sparse dataset， and can obtain better prediction results than the item?based collaborative filtering method.

Keywords： sparseness segmentation; support vector regression; item?based recommendation; collaborative filtering; data sparsity; small sample

0 ?引 ?言

協(xié)同過濾[1]（Collaborative Filtering，CF）是應(yīng)用最為廣泛的推薦算法，其主要思想是同樣興趣的用戶擁有相同偏好的概率更高，據(jù)此建立[U?I]矩陣預(yù)測用戶對未接觸過物品的興趣度，為其推薦依興趣度排序的物品列表。以往研究表明，預(yù)測誤差的微小改進也會顯著提高推薦的準(zhǔn)確率[2]。而數(shù)據(jù)的強稀疏性是導(dǎo)致算法預(yù)測誤差過大的重要因素[3]，因此許多研究者都在致力于解決這個問題，目前典型的方法有以下幾種：

1） 文獻[4]提出快速插補CF算法。該算法將數(shù)據(jù)集分割為子集來預(yù)測稀疏性大于95%數(shù)據(jù)的[U?I]矩陣缺失評分，但不同子集之間的預(yù)測結(jié)果不參與其他部分的計算。

2） 文獻[5]提出自適應(yīng)填補方法。該算法將基于模型和記憶協(xié)同過濾結(jié)合來預(yù)測缺失評分，需根據(jù)參數(shù)判斷自適應(yīng)使用基于項目的協(xié)同過濾（Item?Based Collaborative Filtering，IBCF）還是基于用戶的預(yù)測。

3） 采用支持向量機（Support Vector Machine，SVM）預(yù)測數(shù)據(jù)，即將有評分?jǐn)?shù)據(jù)的二維[用戶，電影]數(shù)據(jù)看作一個有評分標(biāo)簽[user+movie]元素的特征向量[6]。算法利用了SVM對高維數(shù)據(jù)分類準(zhǔn)確性的優(yōu)點[7]，但SVM時間復(fù)雜度隨數(shù)據(jù)的增加呈指數(shù)增長。

4） 文獻[8]提出結(jié)合全局和局部的稀疏線性方法。它提取不同行為特征的用戶子集對同一項目進行不同的相似度預(yù)測，最終取相似度均值。但在全局整合需要自適應(yīng)權(quán)重才能達到更好的效果。

結(jié)合上述對數(shù)據(jù)細化的方式來解決數(shù)據(jù)稀疏性問題的優(yōu)點，并針對不同方法存在的局限性，將支持向量回歸（Support Vector Regression，SVR）計算精確、IBCF方法速度快和擴展性好的優(yōu)點結(jié)合起來，提出基于稀疏分段的協(xié)同過濾方法，以解決數(shù)據(jù)強稀疏性導(dǎo)致預(yù)測準(zhǔn)確率偏低的問題。

1 ?算法描述

檢測推薦算法的數(shù)據(jù)集有MovieLens，ML?latest，EachMovie，Jester，Lastfm[9?10]等，通過分析和以往研究[4?5]發(fā)現(xiàn)它們由相對密集部分和稀疏部分組成。本文用[U?I]矩陣缺失值占整個矩陣的比例表示稀疏程度：

文獻[4?5]中數(shù)據(jù)稀疏性強的Movielens在本文中稀疏度為94%。結(jié)合上述方法優(yōu)缺點分析，提出稀疏分段的協(xié)同過濾來解決數(shù)據(jù)稀疏性問題。首先根據(jù)數(shù)據(jù)特點對數(shù)據(jù)進行強稀疏和弱稀疏的分割，對弱稀疏部分經(jīng)過填充后輸入迭代預(yù)測的支持向量回歸模型，得到更多的可信評分?jǐn)?shù)據(jù);在下一步使用基于項目的插補協(xié)同過濾方法預(yù)測剩余缺失值。這樣既可以利用支持向量回歸在小樣本數(shù)據(jù)上預(yù)測精確的優(yōu)勢，又在某種程度上解決數(shù)據(jù)大量缺失帶來的稀疏性問題。

1.1 ?稀疏分段算法步驟

數(shù)據(jù)集[U?I]矩陣有[M]個用戶，[N]個項目，[u]代表任意用戶，[i]代表任意項目。本文基于稀疏分段的協(xié)同過濾算法的步驟如下：

1.2 ?弱稀疏數(shù)據(jù)的預(yù)測

弱稀疏數(shù)據(jù)的預(yù)測步驟如下：

Step1：現(xiàn)實數(shù)據(jù)集稀疏度往往高于90%，精確的算法也不能在統(tǒng)計意義上有可信的結(jié)果。為了突出迭代預(yù)測的SVR在高維數(shù)據(jù)小樣本上表現(xiàn)優(yōu)異的優(yōu)勢，需為數(shù)據(jù)集選擇弱稀疏部分，根據(jù)實驗需選擇缺失評分比例約為60%部分，使訓(xùn)練樣本可信度更高，過程如圖1a）所示。數(shù)據(jù)中存在評分多的用戶和流行物品，計算用戶評分項目數(shù)量和項目被評次數(shù)，篩選大于一定次數(shù)（根據(jù)不同數(shù)據(jù)集實驗經(jīng)驗，這個次數(shù)表現(xiàn)約為用戶總數(shù)[110]和項目總數(shù)[110]）的用戶和項目作為樣本，降低該數(shù)據(jù)缺失評分比例。

Step2：對弱稀疏數(shù)據(jù)部分進行預(yù)填充處理，使數(shù)據(jù)更符合迭代支持向量回歸的特性，過程如圖1b）所示。對于用戶[u]，評分項目集合為[Ru]，對其未評分項目[i]，[Ru，i=0]，若在計算中直接將0代入樣本，而0在協(xié)同過濾中表示用戶非常不喜歡[11]，若將此先驗條件代入計算，則不利于打分習(xí)慣的預(yù)測。本文中，第一步預(yù)測之前需將所有[Ru，i=0]的部分暫改為當(dāng)前被評分項目的均值參與運算。

Step3：確定特征向量和分類標(biāo)簽。從弱稀疏矩陣第一個項目計算，直到最后一個項目。對項目[i]，任一用戶[u]的特征向量是當(dāng)前用戶對其他項目的評分構(gòu)成的特征向量，用[xu=Ru，1，Ru，2，…，Ru，N]來表示，且評分標(biāo)簽[yu]是用戶對當(dāng)前項目的評分[Ru，i]。

Step4：為項目[i]建立SVR模型。在弱稀疏矩陣中用SVR算法模型[12]預(yù)測缺失值。若給定訓(xùn)練數(shù)據(jù)集[T=x1，y1， x2，y2， …，xi，yi，…，xl，yl]，[l]為訓(xùn)練樣本個數(shù)，本文[1≤i≤l]，[xi]為特征向量，[yi]為評分標(biāo)簽。需求解的支持向量回歸模型函數(shù)[12]為：

將Step3弱稀疏矩陣中除當(dāng)前用戶[u]外所有用戶的特征向量和標(biāo)簽代入式（2）得到項目[i]的SVR模型，如圖1c）建立模型過程中用高斯核函數(shù)將向量映射到高維非線性空間。

圖1 ?基于稀疏分段方法的預(yù)測過程

Step5：求弱稀疏部分項目[i]的評分預(yù)測，過程如圖1d）所示。對項目[i]的所有用戶評分中，[Ru，i=0]的用戶的特征向量為當(dāng)前用戶除當(dāng)前項目評分外的所有評分，代入模型得到用戶[u]的評分標(biāo)簽[yi]，計算結(jié)果存入[U?I]矩陣。

通過不斷迭代Step4，Step5過程，高維非線性曲面空間會不斷擬合為符合不同用戶的打分習(xí)慣的特征空間曲面，由特征空間曲面模型得到的預(yù)測評分也更精確。第一步預(yù)測結(jié)束時，被挑選的數(shù)據(jù)集弱稀疏部分的缺失評分?jǐn)?shù)據(jù)被全部預(yù)測完成，效果如圖1e）所示。

1.3 ?強稀疏數(shù)據(jù)的預(yù)測

本文使用IBCF方法預(yù)測[U?I]矩陣中剩余缺失值，以往研究也表明在數(shù)據(jù)稀疏性低于90%的情況下協(xié)同過濾算法表現(xiàn)更好[3?4]。

Step1：通過新[U?I]評分?jǐn)?shù)據(jù)得到[N×N]的項目間相似度矩陣。在IBCF方法中尋找當(dāng)前用戶打分過的項目集合并計算集合和項目列表之間的相似度，得到[N×N]的相似度矩陣，表示不同項目間的相似程度，取值范圍為[-1，1]。選擇[k]個最相似項目[{i1，i2，…，ik}]作為[k]近鄰[13]。項目[i，j]間相似度[sim（i，j）]通常使用余弦相似度計算，公式[13]為：

式中：[Ru， N]為用戶[u]對所有項目的評分;[simi，N]為項目[i]與任意項目的相似度。由項目的相似度和用戶打分過的項目評分求內(nèi)積并歸一化得到預(yù)測值。使用[k]個最相似項目代替全部[N]個項目來防止最受歡迎項目總納入計算結(jié)果，本文將此方式叫作K?IBCF。

1.4 ?稀疏分段算法的時間和空間復(fù)雜度分析

[D]為數(shù)據(jù)稀疏度，K?IBCF的時間復(fù)雜度為[ONNMD]，空間復(fù)雜度為[ON2]。本文第一部分未知評分?jǐn)?shù)為[S]，[D]為SVR預(yù)測后數(shù)據(jù)稀疏度，時間復(fù)雜度為[OS2+NNMD]，空間復(fù)雜度為[OS+N2]。稀疏分段方法因SVR使用更多時間和空間資源降低預(yù)測誤差。

2 ?實驗數(shù)據(jù)與評估

2.1 ?數(shù)據(jù)集

本文選擇如下數(shù)據(jù)集評價實驗結(jié)果，MovieLens和ML?latest以及EachMovie是電影數(shù)據(jù)，評分為1～5的離散值。Jester是笑話數(shù)據(jù)，評分為-10～10的實數(shù)，歸一化至0～5范圍。LastFM是音樂數(shù)據(jù)，在本文實驗過程中把用戶聽歌次數(shù)轉(zhuǎn)為0～5的量化值來預(yù)測。對于EachMovie，0值表示不喜歡和未評分，本文去掉未評分信息的不可用數(shù)據(jù)。

2.2 ?評估方法

本文使用五折交叉驗證來評估提出算法的表現(xiàn)。通過計算預(yù)測誤差來衡量不同算法的表現(xiàn)，具體需要計算MAE值：

2.3 ?實驗結(jié)果和實驗分析

不同數(shù)據(jù)集弱稀疏數(shù)據(jù)部分在IBCF和基于稀疏分段的MAE值比較見表1。填均值比填0對SVR的預(yù)測影響更大，因0值在迭代的SVR中代表強烈的不喜歡，而在插補的IBCF中使用余弦公式，0不起作用?？沈炞C迭代預(yù)測的SVR在弱稀疏數(shù)據(jù)部分的預(yù)測優(yōu)勢，使數(shù)據(jù)集合理擴充為非強稀疏的數(shù)據(jù)集，讓IBCF算法在下一步預(yù)測中更好地應(yīng)用。

表1 ?弱稀疏數(shù)據(jù)上SVR模型優(yōu)勢

圖2 ?MovieLens使用[K]?IBCF和稀疏分段方法的MAE值

本文使用五折交叉驗證，因此區(qū)域部分表示5次不同實驗結(jié)果的MAE值的范圍。區(qū)域中的曲線代表MAE平均值。由圖2可得，當(dāng)[k]接近120時MAE值更小，且在不同的[k]近鄰下稀疏分段方法都稍好于K?IBCF方法。[k]值逐漸增大，預(yù)測誤差先減少后呈現(xiàn)增大趨勢，因為選取近鄰越多越準(zhǔn)確，但近鄰超出一定程度，必然使得大眾普遍喜歡的物品被多次納入計算，從而誤差會出現(xiàn)上升趨勢。

本文根據(jù)不同數(shù)據(jù)集的項目數(shù)量對近鄰[k]進行相應(yīng)更改，更好地體現(xiàn)算法在[k]值變化時產(chǎn)生的MAE值變動?；谙∈璺侄蔚姆椒ê蚄?IBCF算法的MAE值對比如表2所示。本文算法在稀疏性非常高時表現(xiàn)更好，通過迭代預(yù)測SVR的方式，合理擴展可信數(shù)據(jù)，避免在數(shù)據(jù)稀疏性為90%以上導(dǎo)致不同算法都很難支撐統(tǒng)計意義的缺點[14]。當(dāng)數(shù)據(jù)稀疏性不是很高時，如表3 Jester特性，缺失評分遠低于90%，傳統(tǒng)算法依然在預(yù)測此類數(shù)據(jù)集的缺失值方面表現(xiàn)突出。

表2 ?不同數(shù)據(jù)集的MAE值

表3 ?數(shù)據(jù)集屬性

由實驗可得，稀疏分段方法在第一步選取的數(shù)據(jù)集適用于SVR模型，使得SVR在弱稀疏數(shù)據(jù)集的應(yīng)用中得到了可信度高的評分。且整個方法沒有使用單一相似度的協(xié)同過濾，避免將所有用戶的打分行為特征都視為同一模型，多次迭代的SVR模型潛在地將用戶行為模式、項目特征與評分的匹配模式呈現(xiàn)多元化。稀疏分段方法在發(fā)揮SVR和IBCF兩個算法優(yōu)點的同時，還能規(guī)避兩個算法的缺點，既能提高預(yù)測準(zhǔn)確性，又能避免全局使用SVR模型過高的時間復(fù)雜度。

3 ?結(jié) ?語

本文通過將數(shù)據(jù)稀疏性分為弱稀疏部分和強稀疏部分，從而將預(yù)測評分的步驟對應(yīng)地分為兩步，結(jié)合SVR模型準(zhǔn)確預(yù)測的特點對弱稀疏部分預(yù)測，利用IBCF算法可擴展性和時間開銷小的特點對強稀疏部分進行預(yù)測。實驗結(jié)果證明，本文算法的適用場景為評分信息分布明顯不均且有大量缺失的情況，尤其在數(shù)據(jù)稀疏性大于90%的情況下可以豐富稀疏矩陣的信息。

本文提出的方法在減小數(shù)據(jù)集預(yù)測誤差的同時，還存在稍高于傳統(tǒng)協(xié)同過濾方法時間開銷的問題。下一步工作中考慮將每個數(shù)據(jù)集的預(yù)測從評分頻率高的數(shù)據(jù)開始預(yù)測起，直到[U?I]矩陣的全局都被逐漸預(yù)測結(jié)束，或者最大化地利用屬性信息，把它們當(dāng)作新的特征向量來預(yù)測評分。

參考文獻

[1] EKSTRAND M D， RIEDL J T， KONSTAN J A. Collaborative filtering recommender systems [J]. Foundations and trends in human?computer interaction， 2011， 4（2）： 81?173.

[2] KOREN Y. Factorization meets the neighborhood： a multifaceted collaborative filtering model [C]// Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Las Vegas： ACM， 2008： 426?434.

[3] KOREN Y， BELL R. Advances in collaborative filtering [M]// Anon. Recommender systems handbook. US： Springer， 2015： 77?118.

[4] SU X， KHOSHGOFTAAR T M， GREINER R. A mixture imputation?boosted collaborative filter [C]// Proceedings of the 21st International Florida Artificial Intelligence Research Society Conference. Florida： ACM， 2008： 312?317.

[5] REN Y， LI G， ZHANG J， et al. The efficient imputation method for neighborhood?based collaborative filtering [C]// Proceedings of the 21st ACM international conference on Information and knowledge management. [S.l.]： ACM， 2012： 684?693.

[6] SHI Y， LARSON M， HANJALIC A. Collaborative filtering beyond the user?item matrix： a survey of the state of the art and future challenges [J]. ACM computing surveys， 2014， 47（1）： 3.

[7] 丁世飛，齊丙娟，譚紅艷.支持向量機理論與算法研究綜述[J]. 電子科技大學(xué)學(xué)報，2011，40（1）：2?10.

DING Shifei， QI Bingjuan， TAN Hongyan. An overview on theory and algorithm of support vector machines [J]. Journal of University of Electronic Science and Technology of China， 2011， 40（1）： 2?10.

[8] CHRISTAKOPOULOU E， KARYPIS G. Local item?item models for top?n recommendation [C]// Proceedings of the 10th ACM Conference on Recommender Systems. [S.l.]： ACM， 2016： 67?74.

[9] MovieLens. GroupLens datasheet [EB/OL]. [2015?12?15]. https：// grouplens.org/datasets/movielens/.

[10] EachMovie. EachMovie collaborative filtering data set [EB/OL]. [1997?02?16]. http：//www.cs.cmu.edu/～lebanon/IR?lab/data.html.

[11] LI Z， PENG J Y， GENG G H， et al. Video recommendation based on multi?modal information and multiple kernel [J]. Multimedia tools and applications， 2015， 74（13）： 4599?4616.

[12] CHANG C C， LIN C J. LIBSVM： a library for support vector machines [J]. ACM transactions on intelligent systems and technology， 2011， 2（3）： 112?115.

[13] WU X， CHENG B， CHEN J. Collaborative filtering service recommendation based on a novel similarity computation method [J]. IEEE transactions on services computing， 2017， 10（3）： 352?365.

[14] HU Y， SHI W， LI H， et al. Mitigating data sparsity using similarity reinforcement?enhanced collaborative filtering [J]. ACM transactions on Internet technology， 2017， 17（3）： 1?20.