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

王 永，鄧永恒，李曉光

重慶郵電大學(xué) 經(jīng)濟管理學(xué)院，重慶 400065

1 引言

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

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

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

本文在計算用戶相似性時，為了考慮用戶間的非對稱關(guān)系和用戶偏好行為，在常見的相似性方法上引入了兩個權(quán)重因子，提出了一種考慮用戶偏好的非對稱推薦算法。非對稱因子強調(diào)了目標(biāo)用戶與其他用戶間的共同評分項所占比例，將對稱的用戶相似性轉(zhuǎn)化為非對稱的用戶相似性，用于區(qū)分用戶間在評分?jǐn)?shù)量上的差別。偏好因子反映了用戶對所評項目的某種評分偏好，用于解決某些極端用戶習(xí)慣對項目評高分或低分的問題，使計算結(jié)果更為客觀真實。在真實數(shù)據(jù)集上的實驗結(jié)果顯示，本文所提出的方法在一定程度上能緩解傳統(tǒng)相似性度量方法所存在的偏好問題，降低了推薦誤差，推薦結(jié)果更為準(zhǔn)確。

2 問題分析

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

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

表1 用戶-項目評分矩陣

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

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

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

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

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

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

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

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

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

3.1 權(quán)重因子

（1）非對稱因子

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

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

Sigmoid函數(shù)具有單調(diào)性、非線性等性質(zhì)，且對于差異較大的自變量，輸出值之間有很高的分辨度，因此在式（1）的基礎(chǔ)上，結(jié)合Sigmoid函數(shù)設(shè)計非對稱因子如下：

（2）偏好因子

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

對于用戶u的所有評分?jǐn)?shù)據(jù)，其均值rˉu反映了分值樣本的一般水平；標(biāo)準(zhǔn)差δu反映的是偏離均值的平均距離，是一種集中程度的體現(xiàn)。通過這些統(tǒng)計量，可發(fā)現(xiàn)用戶評分偏好的存在：u的均值越高（或越低）、數(shù)據(jù)分布越集中，其評高分（或低分）的偏好就越明顯。

為了消除評分偏好對用戶相似性度量的影響，引入用戶評分的均值和標(biāo)準(zhǔn)差去構(gòu)造偏好因子，使得最終的相似性結(jié)果更為客觀。其公式為：

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

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

3.2 產(chǎn)生推薦列表

推薦的過程如下：

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

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

步驟3產(chǎn)生推薦列表。根據(jù)項目預(yù)測值，系統(tǒng)可為目標(biāo)用戶進行項目推薦，即取項目預(yù)測值最高的前N個項目作為用戶感興趣的推薦列表。

4 算法分析

（1）考慮用戶評分?jǐn)?shù)量

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

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

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

（3）優(yōu)化鄰居用戶的選擇

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

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

（4）算法性能分析

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

表2 各對比算法的時間復(fù)雜度

圖3 引入權(quán)重因子后的用戶相似性值

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

5 實驗結(jié)果與分析

5.1 數(shù)據(jù)集

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

5.2 評估指標(biāo)

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

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

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

圖4 MAE的結(jié)果比較

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

其中，m表示待預(yù)測的目標(biāo)用戶數(shù)量。在實驗中，算法假定出現(xiàn)在推薦列表的項目的評分值必須高于目標(biāo)用戶的平均評分，否則不予推薦。

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

5.3 結(jié)果分析

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

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

圖5 RMSE的結(jié)果比較

圖6 F1-Measure的結(jié)果比較

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

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

6 結(jié)論

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

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