面向稀疏數據的協同過濾用戶相似度計算研究

武 森，董雅賢，魏桂英，高曉楠

北京科技大學 經濟管理學院，北京100083

互聯網和信息技術的普及與應用，使得海量信息不斷產生與傳播，信息過載成為普遍關心的問題。推薦系統因其能有效過濾信息，滿足用戶個性化服務的需求，在視頻、音樂、電子商務等領域起到關鍵作用。協同過濾是一種重要和應用廣泛的推薦算法，其基本假設是用戶興趣具有延續性，即若過去兩用戶的偏好相似，則未來其偏好也具有相似性。協同過濾首先計算用戶或項目間相似度，在此基礎上，預測目標用戶對目標項目的評分并進行有效推薦，因此合理的相似度計算成為實現精準推薦的關鍵。

隨著用戶數目與項目數量的增加，用戶-項目評分矩陣稀疏程度加劇，例如，公開數據集MovieLenslatest-small 僅具有一個或兩個共同評分項的用戶對數目達到19%。傳統數值相似度計算方法如皮爾遜相關系數（Pearson correlation coefficient，PCC）、余弦相似度（cosine similarity，COS）、修正余弦相似度（adjusted cosine similarity，ACOS）等首先查找共同評分項，進而由共同評分項評分數值計算相似度。稀疏數據中共同評分項的減少將導致傳統數值相似度度量方法難以準確計算用戶或項目間的相似度，因此推薦效果隨之降低。與數值相似度不同，結構相似度依據用戶是否曾對項目進行評分這一行為計算相似度，主要度量兩用戶評分項是否相關。杰卡德相似度（Jaccard）為常用的結構相似度計算方法，衡量用戶共同評分項占比，計算簡單，但由于其完全忽視評分數值，獲得的結構相似度區分度低，難以辨別不同用戶之間相似性的差異。綜合相似度[通過融合結構相似度與數值相似度綜合用戶評分的結構信息與數值信息，可同時衡量用戶評分相關性與偏好一致性，改善數值相似度在稀疏數據中受共同評分項稀少影響難以準確計算相似度的問題。然而現有綜合相似度大多依托于Jaccard，因此未能徹底解決區分度較弱的不足，且未能有效避免稀疏數據中數值相似度影響綜合相似度準確性，相似度計算可靠性有待提升。

針對稀疏數據難以準確計算相似度的問題，本文提出稀疏余弦相似度（sparse cosine similarity，SCS）提高稀疏數據中用戶相似度計算準確性。稀疏余弦相似度首先定義稀疏集合相似度（sparse set similarity，SSS）以度量稀疏數據中的用戶結構相似度。稀疏集合相似度通過結合數值度量，增強區分度以優化結構相似度計算。進一步，設置稀疏集合相似度閾值，針對稀疏集合相似度大于閾值的高相關用戶與不滿足閾值要求的低相關用戶，分別定義數值相似度計算方法，降低數值相似度對評分稀疏用戶綜合相似度的影響，以規避數據稀疏時對數值相似度的誤導。最終，稀疏余弦相似度利用稀疏集合相似度閾值與調整系數平衡結構相似度與數值相似度貢獻，克服傳統數值相似度計算方法由于依賴共同評分項，在稀疏數據中計算準確性受到較大影響的問題，且改善原有結構相似度區分度弱的問題。

1 相關工作

協同過濾因其不用考慮推薦項目的內容、技術易于實現等優點被廣泛使用。隨著用戶、項目數量的劇增，用戶-項目評分矩陣的稀疏性導致協同過濾推薦的準確性降低。針對這種情況，學者提出多種解決方法，其中包括數據填充、降維以及新相似度計算方法。

數據填充即針對缺失評分進行填補，利用平均數、中位數等可實現填補，但這種方法將所有缺失的評分填補為相同的值，與實際情況不符。還有學者將聚類等方法應用于數據填充，如對用戶進行聚類，將簇內用戶評分均值用于數據填充，然而數據稀疏將影響聚類效果，進而影響用戶評分填充效果。

矩陣分解是經典的降維方法，可分為奇異值分解（singular value decomposition，SVD）、概率矩陣分解（probabilistic matrix factorization，PMF）、非負矩陣分解（nonnegative matrix factorization，NMF）等。針對用戶-項目評分矩陣的分解，NMF 的純加性具有更好的解釋性，因此成為推薦領域最受歡迎的降維工具之一。矩陣分解將用戶-項目評分矩陣分解為低維矩陣，降低計算數據的維度，但可能導致信息丟失。

相似度計算方法將直接影響協同過濾推薦效果，作為實現有效推薦的關鍵步驟，受到學者廣泛研究。為解決數據稀疏問題，新相似度計算方法層出不窮。其中，一部分學者在相似度計算過程中融入更多信息，通過豐富信息量來增強稀疏數據中相似度的可靠度。如提取用戶隱含評分、上下文信息、用戶年齡、教育水平、用戶興趣主題等用于用戶相似度計算。然而這些信息的可獲取性將影響這類相似度計算方法的適用性。另有許多學者則針對稀疏的評分數據設計新相似度計算方法以提高用戶相似度計算準確度，可分為數值相似度、結構相似度、綜合相似度。

1.1 數值相似度

COS將用戶評分視為向量，將兩個評分向量之間的角度的余弦值用作相似度值，如式（2）所示。

但是，COS 未考慮不同用戶的評級偏好，ACOS則針對這一問題進行了改進，如式（3）所示。

PCC、COS、ACOS 都屬于對稱相似度，即、之間的相互影響力相同。有學者認為用戶間相互影響力存在差異，并提出不對稱余弦相似度。

上述傳統的數值相似度計算依賴用戶對共同評分項的評分數值，具有以下缺點：首先，僅使用共同評分項評分數值，未使用非共同評分項評分數值，信息利用不充分；其次，共同評分項稀少時無法準確計算相似度。然而在實際推薦場景中，用戶項目評分矩陣稀疏，用戶間共同評分項稀少影響相似度計算準確性進而影響推薦效果。以算例分析稀疏數據對用戶相似度計算的影響。

假設用戶集合{,,,,}對各項目的評分如表1 所示。

表1 用戶-項目評分矩陣算例Table 1 Example of user-item rating matrix

針對表1 中部分用戶的評分進行詳細分析，結果如表2 所示。以(,)表示用戶、間的相似度。{,}共同評分項數、共同評分項所占比例均大于{,}，且{,}共同評分項評分差距較小，因此(,)應大于(,)。同理，(,)應大于(,)。針對表1計算用戶相似度，部分結果如表3所示。

表2 部分用戶評分分析Table 2 Analysis of partial user ratings

表3 部分用戶相似度計算結果Table 3 Similarity measure of partial users

表3 中，PCC(,)小于PCC(,)，COS(,)小于COS(,)，COS(,)小于COS(,)，ACOS(,)小于ACOS(,)。對比表2 分析結果與表3計算結果，數據稀疏時受共同評分項數稀少影響，數值相似度計算結果不合理。

1.2 結構相似度

結構相似度根據用戶是否曾對項目進行評分計算相似度，其受數據稀疏影響較小，但不考慮具體評分數值，易損失信息。Jaccard 是經典的結構相似度，可以找到傾向于共同評價的高度相關的用戶，但未考慮評分數值，無法判斷用戶偏好的一致性且區分度較弱。如，表1 中{,}與{,}共同評分項評分差距不同，因此(,)應不同于(,)，然而Jaccard(,)=Jaccard(,)=0.4。

1.3 綜合相似度

綜合相似度結合數值相似度與結構相似度，往往可彌補這兩類相似度的缺點，提高稀疏數據用戶相似度計算準確性。Bobadilla 等提出了一種綜合相似度度量方法，該方法結合Jaccard 和數值相似度MSD（mean squared differences），稱為JMSD（Jaccard mean squared differences）。Liu 等提出數值相似度PSS（proximity significance singularity），并結合改進的Jaccard 形成綜合相似度NHSM（new heuristic similarity model）以提高稀疏數據中用戶相似度計算準確性。Wang 等利用KL 散度（Kullback Leibler divergence）改進PSS，以共同評分項占比計算結構相似度，最終形成的綜合相似度適用于稀疏數據用戶相似度計算。Patra 等提出一種結合Jaccard 和巴氏系數的綜合相似度計算方法，稱為BCF（Bhattacharyya coefficient in collaborative filtering）。巴氏系數利用用戶所有評分信息克服共同評分的限制，有助于計算稀疏數據中用戶數值相似度。Bag 等提出噪聲識別與較正的方法，與巴氏系數集成，針對無噪聲稀疏數據展開推薦。Mu 等為了緩解稀疏問題引入海林格距離和Jaccard，以降低共同評分項稀少給相似度計算帶來的影響。Bag 等認為目標用戶單獨評分項數與其他用戶單獨評分項數對用戶相似度計算的作用不同并提出一種不對稱的JMSD 稱為RJMSD（relevant Jaccard mean square distance）。

綜合相似度同時考慮用戶評分結構與評分數值，受數據稀疏影響較小，然而未能有效避免共同評分項稀少時數值相似度誤導。已有綜合相似度研究通常利用調整系數調節結構相似度與數值相似度的權重來結合兩種相似度計算結果。假設(,)與(,)分別表示用戶、的結構相似度與數值相似度，則用戶、的綜合相似度(,)大多如式（4）所示。

若以融合Jaccard 與ACOS 構成綜合相似度。以表1 數據為例，經計算小于0.88 時，(,)大于(,)，顯然不合理。而取值越大代表綜合相似度涵蓋的數值信息越少，即對用戶偏好一致性的判斷越弱。若為緩解共同評分項稀少時數值相似度的誤導，將調整得過大，則會弱化共同評分項繁多時綜合相似度判斷偏好一致性的作用。因此，這類綜合相似度難以有效避免數據稀疏時數值相似度的誤導。

現有綜合相似度主要借助用戶共同評分項占比計算結構相似度，再進一步與數值相似度結合，未能有效提升結構相似度區分度，且受數據稀疏影響嚴重的數值相似度會影響綜合相似度的計算結果。因此，提出一種新的綜合相似度計算方法——SCS。SCS 首先定義融入數值信息的結構相似度計算方法SSS，增強結構相似度的區分度。相較于原有綜合相似度僅依靠調整系數調節結構相似度與數值相似度權重，難以規避稀疏數據數值相似度極端值影響，SCS 利用閾值與調整系數實現綜合相似度中結構相似度與數值相似度權重的雙重調節，規避共同評分項稀少時數值相似度對綜合相似度的誤導，提高稀疏數據中用戶相似度的準確性，提升推薦效果。

2 面向稀疏數據的協同過濾用戶相似度SCS

2.1 融合數值信息的結構相似度SSS

為改進結構相似度區分度低的問題，首先新定義了集合聚合度和集合離差度，進而提出通過集合聚合度與集合離差度融合數值信息的結構相似度SSS，作為提出面向稀疏數據的協同過濾用戶相似度SCS 的基礎。

（集合聚合度（set aggregation，SA））假設用戶集合包含||個對象，的集合聚合度()如式（5）所示。

其中，表示中所有用戶評分項集合的交集的對象個數，即中用戶共同評分項的個數，表示中所有用戶評分相等的項目個數。以表1 為例，令={,}，則()=2×2+2×0=4。

集合聚合度從集合結構和數值兩方面提煉集合內信息，統計集合結構的相似信息，統計集合內數值相等信息，且由于只針對共同評分項判斷評分是否相等，因此，必小于等于。集合聚合度綜合集合結構與數值信息，且結構信息對集合聚合度影響更大。

（集合離差度（set deviation，SD））假設表示由各項目評分的最大值組成的最大值向量，表示由各項目評分的最小值組成的最小值向量，的集合離差度()如式（6）所示。

其中，表示中僅有部分用戶進行評分的項目個數，如式（7）所示。

其中，各用戶可對個項目進行評分，|X|表示中對項目進行評分的用戶個數。

式（6）中，(,) 表示的最大值向量與最小值向量間的余弦距離，如式（9）所示。

式（6）中，()表示的平均絕對離差，如式（10）所示。

集合離差度從集合結構與數值兩方面提煉集合內信息，描述集合結構的差異信息，()描述集合內數值差異，且由于數據稀疏，將縮小數值差異在集合離差度中的比重，使集合離差度將以結構差異信息主導。以表1 為例，令={,}，則()=3+0.030 5×2=3.061。

（稀疏集合相似度（SSS））假設()表示的集合聚合度，提煉集合結構相似與數值相等的信息。()表示的集合離差度，提煉集合結構差異與數值離散的信息。將()與()結合，的稀疏集合相似度()如式（11）所示。

以表1為例，令={,}，則()=1.307，={,}，則()=1.32。相比于Jaccard，稀疏集合相似度利用集合聚合度、集合離差度在考量評分結構的同時增加了數值度量，有效提升區分度。集合聚合度只針對共同評分項判斷評分是否相等，結構信息對集合聚合度影響更大；集合離差度利用集合最大值與最小值的余弦距離縮小評分數值信息在其計算中的比重。因此綜合集合聚合度與集合離差度的稀疏集合相似度仍以度量評分結構為主的同時，又因增加了數值度量而較Jaccard 更具有區分度。

2.2 SSS 與數值相似度進一步結合的SCS

當={,}時，()表示用戶、的稀疏集合相似度，此時稀疏集合相似度側重于計算兩用戶的結構相似度。結構相似度主要度量兩用戶評分項是否相關，難以判斷兩用戶偏好是否一致。將稀疏集合相似度與數值相似度進一步結合則可同時實現對相關性與偏好一致性的衡量。然而針對稀疏數據，數值相似度計算不靈敏，其相似度計算結果常產生誤導。例如，假設用戶、用戶、用戶的評分向量分別是（5，—，—，1，—）、（3，1，—，—，—）與（5，—，2，—，4）（“—”表示未進行評分），此時(,)=(,)=(,)=1，(,)=(,)=(,)=1，然而用戶、對第一項的偏好存在較大差異，而用戶、對第一項的偏好是相似的，顯然在稀疏數據中傳統數值相似度COS 與ACOS 計算結果與實際情況不相符。特別地，若目標用戶與其他用戶皆僅存在一個共同評分項，依據COS 則目標用戶與其他用戶相似度皆為1，表現為高度相似，此時數值相似度產生誤導。現有綜合相似度大多如式（4）所示，利用調整系數融合結構相似度與數值相似度，其準確性受數值相似度準確性與結構相似度準確性共同影響，未能有效避免共同評分項稀少時數值相似度誤導。

稀疏集合相似度取值受共同評分項占比影響，因此進一步設置稀疏集合相似度閾值，借助衡量用戶相關性的稀疏集合相似度將用戶區分為高相關用戶與低相關用戶。若稀疏集合相似度高于閾值，即用戶評分結構存在較大相關性，稱為高相關用戶，此時用戶間共同評分項所占比例較大，數值相似度可有效衡量偏好一致性；若稀疏集合相似度低于閾值，即用戶評分結構相關性較低，稱為低相關用戶，此時用戶間共同評分項所占比例較小，共同評分項相對較少，數值相似度計算結果更易產生誤導，因此針對不同用戶的數值相似度采用差異化處理，更有助于綜合衡量用戶相似度。基于上述思想提出稀疏余弦相似度SCS。

（稀疏余弦相似度（SCS））假設(,)表示用戶、的稀疏集合相似度，用戶、的稀疏余弦相似度(,)如式（12）所示。

其中，(,)表示用戶、的數值相似度，如式（13）所示。

以表1 為例，若令SCS 閾值為0.5，則用戶為用戶的低相關用戶，用戶為用戶的高相關用戶，此時若令調整系數為0.5，則(,)為0.124，(,)為0.377，即用戶與用戶更為相似，與表1 中用戶數據特征一致。

SSS 可衡量用戶評分的結構相似度，ACOS 則常用于計算兩用戶評分的數值相似度。由于ACOS 受數據稀疏影響較大，共同評分項較多、占比較高時，ACOS 計算結果較為準確，而共同評分項較少、占比較低時計算結果更易產生誤導。因此，針對共同評分項繁密的高相關用戶，引入調整系數平衡結構相似度與數值相似度比重，同時衡量評分相關性與偏好一致性；由于共同評分項稀疏的低相關用戶的數值相似度更易產生誤導，故而僅以結構相似度計算綜合相似度，避免數值相似度對用戶相似度產生誤導。

簡言之，稀疏余弦相似度首先提出綜合考慮數值信息與結構信息的稀疏集合相似度，增強了結構相似度區分度；進而，設置稀疏集合相似度閾值區分高相關用戶與低相關用戶，針對不同用戶定義差異化的數值相似度計算方法；最終，稀疏余弦相似度利用閾值與調整系數雙層調節稀疏集合相似度與數值相似度，可有效度量稀疏數據中用戶相似度。

2.3 SCS 時間復雜度、空間復雜度分析

假設推薦系統中含有個用戶、個商品，在構建用戶相似度矩陣時需分別計算用戶兩兩間相似度，因此基礎的時間復雜度為()，利用稀疏余弦相似度構建用戶相似度矩陣的時間復雜度同樣為()，與COS、Jaccard、ACOS 一致，未增加時間復雜度。而空間復雜度主要來源于存儲用戶相似度矩陣，利用稀疏余弦相似度構建的用戶相似度矩陣的空間復雜度為()，與COS、Jaccard、ACOS一致，未增加空間復雜度。

3 實驗與結果分析

3.1 數據集

表4 數據集描述Table 4 Description of datasets

實驗采用隨機劃分的方式將80%的數據作為訓練集，20%的數據作為測試集。實驗中取5 次實驗的算術平均值作為最終結果。

3.2 評價指標

采用平均絕對誤差（mean absolute error，MAE）與均方根誤差（root mean squared error，RMSE）作為衡量評分預測準確性的標準，二者反映協同過濾利用最近鄰計算的預測評分與用戶實際評分的貼近程度，值越小，表示基于所使用的相似度計算方法的協同過濾推薦性能越好。MAE 如式（14）所示，RMSE如式（15）所示。

其中，r表示用戶U對項目I的實際評分；R表示相應的預測評分；表示測試集的樣本數量。

3.3 各相似度效果對比

為驗證SCS 有效性，采用6 種廣泛應用的經典相似度計算方法以及1 種新穎不對稱相似度RJMSD 與SCS 在不同數據集進行實驗對比，選取當前目標用戶不同最近鄰數，進行多次實驗，以排除偶然因素。實驗中SCS 需要預先設置閾值，給定取值范圍={0,0.1,0.2,…,1.0}，分別計算SCS 對應的預測精度，將MAE、RMSE 最小時閾值的值視為最優取值。實驗結果如圖1、圖2 所示。對比實驗用到的相似度計算方法見表5。

表5 對比方法描述Table 5 Description of comparison methods

圖1 不同相似度MAE 對比Fig.1 Comparison of MAE with different similarities

圖2 不同相似度RMSE 對比Fig.2 Comparison of RMSE with different similarities

在MovieLens-100K、MovieLens-latest-small 中，SCS 在MAE 與RMSE 兩個指標均取得最優效果。在FilmTrust中，SCS 在MAE 指標取得最優結果，而針對RMSE 指標在=80、100 時，其表現不如COS，其余最近鄰數下均取得最優效果，且針對RMSE 指標，COS、PCC、SCS、Jaccard 效果皆較為接近。綜合三個數據集實驗結果，原有相似度計算方法受數據稀疏影響較大，由稀疏數據計算相似度時計算結果易產生誤導，而數據稀疏對SCS 計算效果影響較小，針對稀疏數據SCS 可以更準確地計算用戶相似度，優于原有相似度計算方法。

此外，對比SCS 與利用降維解決稀疏問題常用的基于NMF 的推薦方法，由于NMF 不涉及最近鄰數，對比兩種方法在MAE 與RMSE 下的最優值與均值，如表6 所示。

表6 SCS 與NMF 推薦效果對比Table 6 Recommended performance comparison of SCS and NMF

針對MAE 指標，SCS 在三個數據集中均明顯優于NMF，MAE 平均降低0.05。針對RMSE 指標，在MovieLens-latest-small數據集中，SCS效果優于NMF，RMSE 平均降低0.02；在MovieLens-100K 數據集中，SCS 效果不及NMF，RMSE 平均提升0.02；在FilmTrust數據集中，SCS 與NMF 效果分別在最優值與均值取得最佳結果且差異較小。整體來看，SCS 優于NMF，可針對稀疏數據準確地進行推薦。

3.4 參數β 變化對SCS 推薦效果的影響

為了進一步說明SCS 推薦效果隨參數的變化趨勢，令閾值為0，選取當前目標用戶不同最近鄰數，比較不同數據集中取值變化對推薦效果的影響，實驗結果如圖3、圖4 所示。

圖3 β 的變化對稀疏余弦相似度MAE 的影響Fig.3 Influence of β on sparse cosine similarity MAE

圖4 β 的變化對稀疏余弦相似度RMSE 的影響Fig.4 Influence of β on sparse cosine similarity RMSE

在MovieLens-100K 中，取值范圍在[0.6，0.8]時，易取得最優效果；在MovieLens-latest-small 中，取值范圍在[0.7，0.8]時，易取得最優效果；在Film-Trust 中，取值范圍為0.9 時，易取得最優效果。且隨著變化，MAE 與RMSE 變化不明顯，即較為穩健。在三個數據集中，隨著稀疏程度提升，取得最優推薦效果的值也隨之提升，且推薦效果隨提升而提升的趨勢越明顯，即隨數據稀疏程度提升，數值相似度產生較大誤導，提高綜合相似度中結構相似度占比并降低數值相似度影響有助于提升推薦效果。

3.5 參數b變化對SCS 推薦效果的影響

為了進一步說明SCS 推薦效果隨參數的變化趨勢，令取各數據集最優效果時取值，選取當前目標用戶不同最近鄰數，比較不同數據集中稀疏集合相似度閾值取值變化對推薦效果的影響，實驗結果如圖5、圖6 所示。

圖5 b 的變化對稀疏余弦相似度MAE 的影響Fig.5 Influence of b on sparse cosine similarity MAE

圖6 b 的變化對稀疏余弦相似度RMSE 的影響Fig.6 Influence of b on sparse cosine similarity RMSE

在MovieLens-100K 中，取值范圍在[0.2，0.3]時，易取得最優效果；在MovieLens-latest-small 中，取值為0.1 時，取得最優效果；在FilmTrust 中，取值為0.7 時取得最優效果。且隨著變化，MAE 與RMSE 變化不明顯，即取值對SCS 效果影響較小。由于SSS 取值必大于0，若令=0，即將全部用戶視為高相關用戶，與現有綜合相似度計算方法相同；當＞0 時，閾值可將用戶劃分為高相關用戶與低相關用戶。在三個數據集中，通過增加稀疏集合相似度閾值，區分高相關用戶與低相關用戶相似度計算方法后，SCS 推薦效果均有所提升，且隨著稀疏程度提升，增添稀疏集合相似度閾值對SCS 提升效果越強。

4 結束語

本文針對稀疏數據難以準確計算用戶相似度，進而影響協同過濾推薦效果的問題，構造了稀疏余弦相似度。該方法首先通過融合用戶評分結構信息與數值信息構造稀疏集合相似度，提高結構相似度區分度；接著，針對稀疏集合相似度設置閾值區分目標用戶的高相關用戶與低相關用戶；然后，針對不同用戶采用差異化的數值相似度計算方式；最后，綜合結構和數值相似度形成稀疏余弦相似度，通過閾值與調整系數實現稀疏數據中相似度計算的雙層調節，可有效度量評分稀疏時的用戶相似度，提升推薦效果。本文采用MAE 與RMSE 指標來評價不同相似度計算方法的表現，在公開數據集MovieLens-100K、MovieLens-latest-small、FilmTrust 上的實驗表明，相比已有相似度計算方法，稀疏余弦相似度受數據稀疏影響較小，可以更準確地計算稀疏數據中的用戶相似度，提升推薦結果的準確率。