考慮非對稱用戶偏好的推薦算法

王 永，鄧永恒，李曉光

重慶郵電大學 經濟管理學院，重慶 400065

1 引言

隨著互聯網技術及其信息科技的蓬勃發展，推薦技術已成功應用于電子商務領域，解決了如何從日益激增的互聯網信息中挖掘出對線上用戶有價值的信息，并快速高效地推薦給目標用戶[1]。推薦系統（RS）的核心任務是通過分析目標用戶對已評產品或項目的偏好行為，去預測該用戶在未評產品或項目上的喜愛程度，以滿足用戶的個性化需求。協同過濾（CF）算法[2]因其擁有簡單又高效的特點，在推薦系統中應用最為廣泛，深受研究者的青睞，是傳統推薦技術之一。算法假定用戶過去的偏好行為將會對其未來的偏好行為有重大影響，且具有相同或相似興趣偏好的用戶信息需求也是相似的。

在推薦算法中，計算用戶或項目間的相似性是算法的首要任務，也是最為核心的步驟。因此，相似性度量方法的選擇將直接決定推薦系統的好壞，對用戶體驗有重大影響。常見的用戶相似性度量方法，如余弦相似性、皮爾遜相關系數等，在一定時期取得了較大成功，但隨著應用環境的變化，它們已無法滿足用戶對推薦系統的精度要求。為改善推薦質量，確保推薦系統的時效性，許多研究者在不同的應用環境下提出了一些新的用戶相似性度量方法。為了解決啟發式相似性度量方法PIP[3]未考慮用戶對項目評分的全局偏好行為的問題，Haifeng Liu等人提出了一種新的啟發式方法NHSM[4]。為了充分利用用戶的所有評分信息，一些研究者從項目概率分布的角度提出了一種新的相似性度量方法[5-6]。程偉杰等人通過利用動態調節權重將基于全部評分信息的用戶相似性方法與傳統用戶相似性相結合，提出了一種混合的用戶相似性方法[7]。張滬寅等人將用戶間的共同評分項數目和PCC相似度閾值作為條件，提出了一種基于多分段改進 PCC的相似度計算方法[8]。上述算法都對共同評分項的數量沒有任何要求，能充分利用用戶所有評分值，較好地解決了數據稀疏性問題。為了解決推薦系統中數據的高稀疏與高維度問題，陶維成等人首先將灰色關聯度理論應用到協同過濾中去計算用戶間的相似性，然后對用戶進行灰色關聯度聚類[9]。該方法具有良好的運算效率，有效緩解了用戶冷啟動問題。李道國等人[10]通過分析用戶評分時間，并結合用戶評分方差相似性來改進傳統相似性方法計算不準確的問題，且優化了最近鄰居集的篩選方式。王穎等人從鄰居用戶選擇的角度出發，考慮數據稀疏度對鄰居個數和對稱關系的影響，提出了一種融合用戶自然最近鄰的推薦算法，該方法在鄰居選擇和推薦精準度方面具有一定優越性[11]。余以勝等人[12]將社群挖掘的思想引入到個性化情報信息推薦中，計算了在不同興趣細粒度社群中的用戶相似性，從而有效地提升了推薦算法的精確度。為了同時考慮用戶興趣偏好受時間和頻率共同影響問題，李紅巍設計了一種基于本體相似度和時間衰減的動態個性化推薦算法[13]。該算法不僅能計算用戶興趣點的時間衰減規律，還考慮了不同興趣點訪問頻率對興趣點關注程度的影響，從而提升了整個系統的推薦效率。

上述相似性度量方法均假定相似性是一種對稱的模式，即sim(u,v)=sim(v,u)。這些方法使用共同評分進行計算，計算用戶間的影響是對等的。在鄰居群體選擇階段，依據這種對稱的相似度作為篩選標準，會把一部分原本不相似的用戶納為鄰居；而預測階段又是以最近鄰居集為基礎的，從而使預測結果的準確性受到干擾。此外，用戶在評分時存在某種偏好，如有的用戶的評分普遍偏高，而有的普遍偏低。評分偏好的差異導致相同分數表示的興趣度存在較大差別。若未考慮偏好因素，將來自不同偏好的用戶的相同評分值視為價值相同，則計算得到的相似性結果不夠客觀。上述方法的設計中，并未考慮這些因素，所以，基于對稱模式的相似性方法在度量的全面性、綜合性方面存在不足。

本文在計算用戶相似性時，為了考慮用戶間的非對稱關系和用戶偏好行為，在常見的相似性方法上引入了兩個權重因子，提出了一種考慮用戶偏好的非對稱推薦算法。非對稱因子強調了目標用戶與其他用戶間的共同評分項所占比例，將對稱的用戶相似性轉化為非對稱的用戶相似性，用于區分用戶間在評分數量上的差別。偏好因子反映了用戶對所評項目的某種評分偏好，用于解決某些極端用戶習慣對項目評高分或低分的問題，使計算結果更為客觀真實。在真實數據集上的實驗結果顯示，本文所提出的方法在一定程度上能緩解傳統相似性度量方法所存在的偏好問題，降低了推薦誤差，推薦結果更為準確。

2 問題分析

為了利用用戶-項目評分矩陣中的數據去度量用戶間的相似性，常見的用戶相似性度量方法，如余弦相似性（COS）[14]、Pearson相關系數（PCC）[15]和均方差（MSD）[16]等被提出。但這些常見的相似性方法都存在同一個假設：每個用戶都被分配同等權重的相似性，用戶間不存在任何偏好，用戶相似性完全對稱，即sim(u,v)=sim(v,u)。然而，在實際情況下，用戶間明顯存在不同的偏好行為，即便兩用戶十分相似，用戶間也有細微的評分偏好差別。因此，本文認為用戶間的相似性應該是不對稱，用戶間存在不同的評分偏好。

為了更好展示一些常見的相似性方法所普遍存在的問題，設計了一個示例來加以闡述。在表1用戶-項目評分矩陣中，共有5個用戶和6個項目，其中“—”表示用戶未對項目評分。根據表1數據，采用常見的相似性度量方法COS、PCC和MSD計算用戶間的相似性，相關結果見圖1，其中“*”表示用戶相似性值無法被計算。

表1 用戶-項目評分矩陣

從圖1的相似性結果可知，這三種相似性度量方法各自都存在一些問題。對這些問題詳細分析如下：

圖1 不同方法的用戶相似性值

（1）問題1：僅利用共同評分項

從圖1中可知，所有用戶相似性矩陣都是對稱的，即對任意兩用戶而言，存在sim(u,v)=sim(v,u)。其原因在于這些方法只利用了兩用戶間的共同評分項，而忽略他們的其他評分的影響。從表1可以看到，用戶U1和U3的評分分別為（4，4，—，—，—，—）和（4，4，5，5，3，3），用戶U1的所有評分和用戶U3完全對應相等，但用戶U3只有1/3的評分能和用戶U1完全匹配。存在這種差異的原因在于，這些相似性度量方法所計算出的相似性值往往只由評分數量較少的那個用戶決定，而忽略用戶各自的評項目數量也對相似性結果有重要影響。因此，本文用一種非對稱方法去計算用戶間的相似性更為合理。

（2）問題2：未考慮用戶評分偏好

這個問題主要為了凸顯PCC方法的缺陷。從PCC的結果矩陣圖1（b）可知，用戶U1和U3的相似性值為0，這意味著用戶U1和U3完全不相似。然而，從表1中可發現用戶U1和U3在項目I1和I2上有相同的評分，說明用戶U1和U3間其實存在一定的相似性，而PCC方法卻計算出了一個完全錯誤的相似性結果。

此外，從表1中還可看出，用戶U2和用戶U3應該比用戶U1和用戶U3更為相似，而從圖1中的所有相似性方法的值上看，COS和MSD的結論正好相反，且PCC的兩結果過于極端。由此說明，這些方法僅考慮用戶間的共同評分項而忽略用戶本身的評分數量，會造成相似性結果不準確。本文認為用戶U3對用戶U1的影響和用戶U1對用戶U3是完全不同的，用戶相似性的值不應該是1或0。因此，本文將用戶評分偏好的問題考慮在內。

3 考慮用戶偏好的非對稱推薦算法

本文算法包括兩個核心步驟：（1）計算考慮用戶偏好的非對稱用戶相似性；（2）產生推薦列表。本文主要在常見的相似性方法（COS、PCC和MSD）上，引入兩個權重因子到用戶相似性計算中，有效地彌補了改進前相似性方法未考慮用戶間共同評分項在目標用戶所評項目中的比例以及用戶評分偏好的問題，降低了預測誤差，提高了推薦質量。

3.1 權重因子

（1）非對稱因子

對于用戶u和v，對稱模式的相似度算法可概括為sim(u,v)=sim(v,u)。由表達式可知，對稱的算法對輸入內容和次序不敏感。同時，實際上參與運算的是共同評分項的分值信息，這組信息是數值的、等長的，不會直接影響對稱性。若用戶u和v的評分總數不同，其共同評分數占二者評分總數的比例也是不同的。由此，可利用絕對數量、占比等方面的差異，構造一個作用于算法外部的因子，從而調節對稱性。

用Iu，Iv分別表示用戶u和v所評分項目的集合，用戶u的評分總數用|Iu|表示，共同評分的數量占用戶u評分總數的比例為：

Sigmoid函數具有單調性、非線性等性質，且對于差異較大的自變量，輸出值之間有很高的分辨度，因此在式（1）的基礎上，結合Sigmoid函數設計非對稱因子如下：

（2）偏好因子

不同用戶對項目進行評分時，都存在一定的個人標準和偏好取向。例如，有的用戶對所評項目的評分普遍偏高，而有的普遍偏低。由于這種偏好的作用，不同用戶之間，即使評分的分值相同，實際的興趣度可能有較大的區別。如前面的示例中，用戶U3和U4對項目I5的評分均為3分，在U3的所有評分中3為其最低評分，代表其最低的興趣程度；而對于U4，3分是最高評分，表示U4對該項目可能最感興趣。可見，正是評分偏好的存在，分值不能直接等同于用戶的感興趣程度。

對于用戶u的所有評分數據，其均值rˉu反映了分值樣本的一般水平；標準差δu反映的是偏離均值的平均距離，是一種集中程度的體現。通過這些統計量，可發現用戶評分偏好的存在：u的均值越高（或越低）、數據分布越集中，其評高分（或低分）的偏好就越明顯。

為了消除評分偏好對用戶相似性度量的影響，引入用戶評分的均值和標準差去構造偏好因子，使得最終的相似性結果更為客觀。其公式為：

其中，rui表示用戶u對項目i的評分值。

將上述兩種權重因子引入到第二部分所提到的常見的用戶相似性中，得到修正后的公式如下：

3.2 產生推薦列表

推薦的過程如下：

步驟1形成最近鄰居集（見圖2）。根據修正后的公式可計算出任意兩用戶間的相似性值，進而獲得用戶間的相似性矩陣S。根據相似性矩陣中值的大小，得到用戶u的前K個相似性值最大的最近鄰居用戶，最終形成最近鄰居集Ku={u1,u2,…,uk}。

步驟2計算預測值。設用戶u的最近鄰居集為Ku，則用戶u對未評分項目i的預測評分值Pui的計算公式如下：

步驟3產生推薦列表。根據項目預測值，系統可為目標用戶進行項目推薦，即取項目預測值最高的前N個項目作為用戶感興趣的推薦列表。

4 算法分析

（1）考慮用戶評分數量

在本文算法中，引入一個非對稱因子A(u,v)去評估用戶v對用戶u的影響。在式（2）中，利用用戶u和v的共同評分項在目標用戶u所評數量中的比例去度量用戶u和v間的非對稱性。若共同評分的比例較大（接近1），則用戶v對用戶u有十分重大的影響；若共同評分的比例較小（接近0），則用戶v對用戶u幾乎無影響。對于A(v,u)，共同評分的比例值取決于用戶間的共同評分項和用戶v所評項目的數量。顯然，sim(u,v)≠sim(v,u)，即用戶u和用戶v的相似性值有別于用戶v和用戶u的值。因此，式（1）為相似性度量方法提供了一個高效的方案去強調用戶間的相似性是非對稱的，使得這些相似性方法計算出的結果更加符合實際情況。

（2）消除極端用戶評分偏好

為了加強所提算法的精確度，本文算法引入偏好因子去消除極端用戶評分偏好的影響。在式（3）中，通過利用用戶的平均評分和評分標準差去衡量用戶間的偏好差異。若用戶間的平均評分或評分標準差較大，則用戶間的偏好存在很大差異。根據式（3）可知，P(u,v)計算出的值很小，能較好地削弱極端用戶評分偏好的影響。

（3）優化鄰居用戶的選擇

最近鄰居集的選擇是通過用戶相似性值進行篩選的，因而鄰居集的選擇將直接影響后續對項目值的預測以及推薦。若用戶u和v的相似性是對稱的，且相似性的值很大，則這兩用戶必互為最近鄰居。但依據式（2），假設用戶u的評分數量遠大于用戶v的數量，則A(u,v)?A(v,u)，最終可能會導致用戶u是用戶v的最近鄰居，而用戶v未必是用戶u的最近鄰居，以達到獲得優化鄰居的目的。

根據所提算法的公式（5）～（7），本文利用表1中的評分數據計算得到相應的相似性矩陣。從圖3相似性結果可知，加入兩個權重因子后，用戶相似性的值變動幅度不大，消除了各自評分偏好的影響，且用戶相似性是非對稱的。引入因子后的模型修正了常見的相似性方法所存在的缺陷，能更好地突出每個用戶的偏好行為。然而，不可否認的是改進后的模型計算出的相似性值仍存在一定問題，這是由這些相似性度量方法本身所引起的。因為這些常見的方法太過于依賴用戶間的共同評分項，而不能充分利用用戶的所有評分信息。若將本文的兩個權重因子加入到更佳的相似性模型中，其推薦精度將會更高，這里將不再對比。

（4）算法性能分析

時間復雜度是評估算法效率的一種方式。表2列舉了原算法和改進算法的時間復雜度，結果所示，這些方法的時間復雜度均為線性階，即O(n)。

表2 各對比算法的時間復雜度

圖3 引入權重因子后的用戶相似性值

調整后的算法與原算法相比，時間復雜度保持不變，時效上的波動較小；但調整后的算法在度量全面性、削弱偏好影響、鄰居集優化等方面的提升是可見的；所以，加入非對稱因子和偏好因子進行改進，可以獲得更優的綜合性能。

5 實驗結果與分析

5.1 數據集

為了驗證本文所提算法的高效性，使用MovieLens數據集（http：//www.grouplens.org）——ML-1M和Yahoo提供的公開數據集Yahoo Music（https：//webscope.sandbox.yahoo.com）作為本文算法測試和驗證的數據集。其中MovieLens數據集包括了6 040位用戶的基本信息，如性別、年齡、職業等；3 900部電影的基本信息，如電影名稱、電影類別等；1 000 209條電影評分，評分區間為1～5，且每個用戶至少評過20部及其以上的電影。Yahoo Music數據集包括15 400位用戶和1 000首音樂的基本信息和183 179條音樂評分。為了測試推薦算法的性能，將數據集劃分為兩部分：訓練集和測試集，大小比例為8∶2。

5.2 評估指標

衡量推薦算法好與壞的指標常用平均絕對誤差MAE（Mean Absolute Error）和根均方誤差RMSE（Root Mean Squared Error）去度量預測評分值和實際評分值間的偏差，以此來反映推薦算法的準確性。誤差值越小，推薦精度越高。其公式如下[5]：

其中，rui和分別為用戶u對項目i的實際評分值和預測評分值；n為待預測項目的個數。

為了對以下公式描述方便，首先介紹兩個變量，分別是IRup和IRua。IRup表示推薦系統為目標用戶u提供的預測推薦列表。IRua是在測試集中用戶u的真實推薦列表。下面，本文將介紹評估算法預測準確性的三個重要指標：Precision、Recall和F1-Measure值。

圖4 MAE的結果比較

Precision定義為同時包含在IRup和IRua中的項目數與IRup中的所有項目數的比值。而Recall表示為同時包含在IRup和IRua中的項目數與IRua中的所有項目數的比值[6]。其表達式如下：

其中，m表示待預測的目標用戶數量。在實驗中，算法假定出現在推薦列表的項目的評分值必須高于目標用戶的平均評分，否則不予推薦。

F1-Measure值是一個綜合評估Precision和Recall結果的指標，使得最終計算出的實驗結果更為可靠。其公式如下：

5.3 結果分析

選取常用的相似性模型（COS[12]、PCC[13]和MSD[14]），首先分別測試每個因子引入到模型中后對預測結果的影響，之后再測試綜合兩因子后的預測效果，并與一些近年來提出的相似性方法（JMSD[4]、PIP[3]和NHSM[4]）作對比。由于不同的鄰居個數K對測試結果有不同的影響，因此在實驗中設置K值從20增加到100，間隔為20。實驗結果如圖4至圖6所示。

MAE和RMSE主要反映的是推薦系統的預測誤差精度。在圖4中，在兩個數據集上，引入兩個權重因子后的相似性方法的MAE值均優于其他對比方法，且AP-PCC方法的誤差值比其他任何相似性方法都低，推薦效果最佳。隨著K值（用戶鄰居數）的增加，所有方法的誤差均在逐漸降低。Movielens數據集上，引入兩因子后，AP-PCC方法表現最佳，其誤差范圍為：0.704≤MA E≤0.716；在Yahoo Music數據集上，當 K 值大于120時，AP-COS的MAE最小，范圍為：1.251≤MAE≤1.265。在圖5中也可以得出類似的結論，表明本文提出的兩個權重因子有效改善了預測模型的RMSE誤差。預測誤差較低，有效提高了推薦系統的質量。

圖5 RMSE的結果比較

圖6 F1-Measure的結果比較

F1-Measure主要是用于評估推薦質量的好壞。從圖6可知，每個相似性方法的F1值都隨著K值的增加而增加。圖6（a）所示，在Movielens數據集中，AP-PCC的F1值最高且基本維持在0.726水平上；AP-COS、AP-MSD方法的F1曲線有所重合，接近0.718；而其他如COS、MSD、PIP和NHSM等方法的F1值均低于0.63。圖6（b）所示，在Yahoo Music數據集上，改進后方法的F1曲線均處于更高的區間，AP-PCC表現最優，其值分布在0.277到0.282之間。上述結果說明，兩權重因子的引入能有效地提高相似性模型的推薦結果。

綜上所述，引入兩權重因子后的相似性方法在各個評估指標上均優于其他對比方法。因此，本次實驗結果驗證了本文提出的兩個權重因子對改進相似性模型有積極的作用，可以有效提高推薦系統的綜合性能。

6 結論

為了解決相似性度量方法普遍所存在的用戶偏好問題，本文在常見的相似性方法中，引入兩個權重因子到其相似性計算中，提出了一種考慮用戶偏好的非對稱推薦算法。第一個權重因子（非對稱因子）將目標用戶與其他用戶間的共同評分項所占的比例考慮在內，將完全對稱的用戶相似性轉化為非對稱，這彌補了相似性方法為每個用戶都分配同等權重的相似性，即考慮了不同用戶對所評項目的數量。

第二個權重因子（偏好因子）利用用戶間的均值和標準差去消除極端用戶的評分偏好。在引入這兩個權重因子后，與引入前的方法相比，引入后的方法有效地緩解修正前方法所存在的用戶偏好問題，能更為精準地為目標用戶篩選鄰居用戶，實現最佳的項目推薦。在數據集MovieLens上的實驗結果表明，引入兩因子后的相似性方法要優于其他所對比的相似性方法，其中APPCC方法能極大地降低了預測誤差，有效地提高了推薦系統的質量。