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

賀懷清 計瑜 惠康華 劉浩翰

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

關鍵詞： 稀疏分段; 支持向量回歸; 基于項目的推薦; 協同過濾; 數據稀疏性; 小樣本

中圖分類號： TN911.1?34 ? ? ? ? ? ? ? ? ? ? ? ?文獻標識碼： 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 ?引 ?言

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

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

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

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

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

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

1 ?算法描述

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

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

1.1 ?稀疏分段算法步驟

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

1.2 ?弱稀疏數據的預測

弱稀疏數據的預測步驟如下：

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

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

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

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

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

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

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

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

1.3 ?強稀疏數據的預測

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

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

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

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

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

2 ?實驗數據與評估

2.1 ?數據集

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

2.2 ?評估方法

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

2.3 ?實驗結果和實驗分析

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

表1 ?弱稀疏數據上SVR模型優勢

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

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

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

表2 ?不同數據集的MAE值

表3 ?數據集屬性

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

3 ?結 ?語

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

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

參考文獻

[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]. 電子科技大學學報，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.