余 相，陳 亮，胡亞蘭，王 丹

(東華大學 信息科學與技術(shù)學院，上海 201620)

0 引 言

隨著互聯(lián)網(wǎng)的飛速發(fā)展和移動端智能手機的普及，人類進入信息時代。據(jù)中國互聯(lián)網(wǎng)信息中心2017年1月份發(fā)布的互聯(lián)網(wǎng)絡狀況統(tǒng)計報告顯示，截至2016年12月，中國網(wǎng)頁數(shù)量約為2 360億個，比上一年增長11.2%[1]。從巨大的信息量中挑選出人們滿意的項目已經(jīng)越來越難，從數(shù)字化圖書、新聞、音樂、影視作品到電商平臺都存在這樣的問題，用戶選擇的時間成本越來越高，因此推薦系統(tǒng)應運而生。

目前，主流的推薦系統(tǒng)主要分為4類：基于內(nèi)容的推薦、協(xié)同過濾推薦、基于知識的推薦和組合推薦[2]。作為推薦系統(tǒng)中應用最廣泛的算法，協(xié)同過濾技術(shù)已經(jīng)在研究上和應用上取得了巨大的成功。然而，其依然有很多問題需要解決[3]。其中之一便是推薦準確性。

為了使推薦的結(jié)果更加符合用戶實際需求，學者一直在嘗試改進經(jīng)典協(xié)同過濾算法，但是隨著用戶和產(chǎn)品數(shù)量的日益增長，由于用戶并不能對所有商品產(chǎn)生記錄，而是其中很小的一部分，從而導致用戶-項目矩陣十分稀疏，甚至99%以上，用戶-項目矩陣的極度稀疏制約著推薦系統(tǒng)的準確性。稀疏性也是協(xié)同過濾技術(shù)的核心問題，同時用戶、項目的高維增長，對算法的效率也提出了挑戰(zhàn)，需要實時生成推薦，直接影響著推薦系統(tǒng)的可擴展性。

1 問題分析

1.1 稀疏性問題

協(xié)同過濾算法主要是依據(jù)用戶過往的使用記錄來形成推薦，最常見的表現(xiàn)形式是用戶-項目評分矩陣。絕大多數(shù)用戶通過評分操作訪問的信息項目數(shù)量相對于系統(tǒng)中信息項目的總量十分有限，一般都達不到信息項目總數(shù)的1%[3-4]，這就導致了評分矩陣的嚴重稀疏性。稀疏性問題的存在是協(xié)同過濾算法中固有的悖論的表現(xiàn)，即CF推薦系統(tǒng)本身是用于幫助用戶從海量信息空間中選擇最符合用戶興趣的信息，而這種需求將導致信息空間的稀疏，進而稀疏性又反過來影響推薦的生成[5]。

1.2 影響分析

協(xié)同過濾算法的唯一數(shù)據(jù)來源就是評分矩陣，因此算法各不同步驟都是以評分矩陣為基礎(chǔ)執(zhí)行的。稀疏性問題帶來的影響會沿著算法步驟一步步擴散到最終的推薦效果中，下面根據(jù)圖1描述這一過程。

圖1 協(xié)同過濾算法流程

(1)相似度計算：相似度將直接作為后續(xù)鄰居選擇和評分預測的重要依據(jù)。根據(jù)相似度的計算方法可知，用戶的相似性是對兩者評分的交集實現(xiàn)的，當矩陣稀疏率很高時，用戶已有的評分數(shù)據(jù)很少，造成用戶間已評分項目的重合率明顯下降，導致公共參考評分項目集合規(guī)模過小，相似性只能依賴極少數(shù)評分進行度量，造成用戶間的相似度計算結(jié)果非常片面，不能準確反映用戶間的真實相關(guān)性[6]。興趣愛好上原本比較相似的用戶，因為少數(shù)幾個共有項目評分差別較大而變成了非相似用戶；事實上，基于小規(guī)模共有評分的相似度計算無法體現(xiàn)用戶間的真實相似度，繼而影響后續(xù)推薦步驟。

(2)候選集生成、鄰居選擇：選擇目標項目的同類(即鄰居)是評分預測的基礎(chǔ)，雖然稀疏問題不會直接作用于鄰居，但是通過相似度計算間接對鄰居選擇產(chǎn)生影響，項目的相似度不同選出的鄰居集也是不同的，導致真實的鄰居集質(zhì)量下降了，進一步擴散到評分預測中。

(3)評分預測：實現(xiàn)推薦依賴于評分預測，實際上是將鄰居中對目標項目有評分的用戶按相似度加權(quán)求和得出預測評分。數(shù)據(jù)稀疏可能導致相似用戶中很多未對目標項目進行過評分，導致只能依賴少數(shù)鄰居評分實現(xiàn)預測，難以保證評分預測的準確性[6]。

從上述分析可以看出，在稀疏性問題的影響下，相似用戶的評估將大面積失真，相似度計算在評分預測和鄰居選擇中都扮演著重要角色，前述在相似度誤差較大時造成推薦效果差甚至推薦失敗。

1.3 擴展性問題

IBCF算法是以項目相似度為依據(jù)篩選候選集，通過相似度加權(quán)預測用戶對候選集中的項目的評分，根據(jù)預測評分高低確定推薦項目。候選集大小、相似度準確程度都將影響推薦精度。此階段候選集需要對用戶u的n個已評分項目進行操作，每個評分項目平均取m個最相似的鄰居，這樣每個用戶的平均候選集大小為nm，并從中剔除常數(shù)個用戶u已評分的項目，得到項目候選集C。

在MovieLens數(shù)據(jù)集上，當項目的近鄰數(shù)m增加時，IBCF算法候選集變化曲線如圖2所示。曲線大致呈線性增長，當近鄰數(shù)為60時，用戶的候選集大小約為200。同樣的條件下，觀察到候選集大小k在急劇上升時，候選集中用戶感興趣的項目占比卻沒有增長或維持不變，相反用戶感興趣占比在下降，當近鄰數(shù)k=

圖2 候選集大小及感興趣項目比例

60時，占比只有4.9%左右，總體比例非常小。用戶的平均候選集大小是nm，此時的時間復雜度為O(n2)，當用戶的評分記錄增多時，候選集大小呈二次函數(shù)增長，候選集中引入了大量與用戶弱相關(guān)或不相關(guān)的項目，導致推薦準確率下降，評分預測階段對大量不感興趣的項目進行計算，算法執(zhí)行中浪費了大量的CPU和內(nèi)存資源，極大增加了為候選集項目預測評分的時間，當用戶和項目呈高維增長時，將大幅度影響算法性能，直接制約著推薦的橫向擴展性。

2 相似度和關(guān)聯(lián)度

2.1 現(xiàn)有相似度

傳統(tǒng)的皮爾遜相關(guān)系數(shù)只考慮用戶間共有評分的作用，而忽視了非公共評分數(shù)量的作用，導致計算用戶相似性及其具有片面性[7]。如表1所示，按傳統(tǒng)相似度計算，用戶U1與U2的相似度為1，U2與U3的相似度要小于1，這就造成了U1比U3更接近U2的鄰居，然而從相似性的可信度來看，U3應該比U1更接近于U2的鄰居。

表1 評分矩陣示例

(1)

(2)

相似度sim(i,j)采用的是Pearson相關(guān)系數(shù)[9]。其中，Iij為用戶i和j共同評分的項目集合；Ri,c和Rj,c分別表示用戶i和j對項目c的評分；Ri和Rj分別表示用戶i和j的平均評分；|Ii∩Ij|是兩用戶共有評分的數(shù)量；α是控制共有評分項數(shù)量的閾值，用戶間共有評分數(shù)量小于閾值時對傳統(tǒng)相似度進行線性衰減修正。根據(jù)文獻[8]的實驗結(jié)果表明對推薦效果有所提高但并不顯著，文中分析認為不同的用戶的評分分布不一樣，采用全局統(tǒng)一的固定閾值無法適用于所有用戶，這種修正只對少數(shù)用戶起作用。

任磊[10]針對該問題提出了適用不同項目評分數(shù)量分布的重合因子，刻畫了項目間公共評分的重合程度，強調(diào)了共有評分重合度的重要性。其加權(quán)相似度表示為：

(3)

(4)

其中，重合因子c(i,j)中的Ii和Ij分別是項目i和j的評分項目數(shù)量。與文獻[8]的絕對全局閾值不同，式3中的相似度不僅與共有評分數(shù)目有關(guān)，還反比于兩用戶單獨評分數(shù)量，這種度量方式是一種全局動態(tài)修正，適用于每一個用戶。

2.2 “S”型改進相似度

根據(jù)上述問題的分析，用戶間相似性在共有評分數(shù)量達到一定數(shù)量時接近飽和，而文獻[10]中提出的相似度計算方法與這一現(xiàn)象相悖。從實際出發(fā)，當兩用戶各自的獨立評分數(shù)確定時，隨著共有評分數(shù)量的增加，相似度的變化率(即增量的導數(shù))應該是先變大后變小，呈“S”型曲線。實際含義即在共有評分數(shù)量較少時，兩用戶相似度比較小，隨著共有數(shù)量的增加，相似度迅速上升，最后達到飽和，幾乎不再發(fā)生變化，即兩用戶已經(jīng)非常相似，這樣才能體現(xiàn)用戶間相似度的真實變化過程。

數(shù)學中常用“Sigmod”函數(shù)來表示S型曲線，其函數(shù)特性完全符合相似度的理想增長過程，體現(xiàn)共有評分項增長中相似度變化的特性。其函數(shù)表示為：

(5)

截取標準Sigmod函數(shù)某段區(qū)間再經(jīng)過伸縮變換得到變換后的Sigmod函數(shù)。將其引入重合因子中，則改進的相似度計算表示為：

(6)

(7)

其中，a和b分別為兩用戶的單獨評分數(shù)量；c為共有評分數(shù)量；m為變換的平移系數(shù)；k為伸縮系數(shù)，控制著函數(shù)的陡峭程度。

相似度關(guān)于共有評分項的函數(shù)見圖3(b)。共有評分項數(shù)小于10時，相似度增長緩慢，繼而迅速增長，當達到20時，用戶間再增加相同評分數(shù)量相似度飽和，此種情況與相似度理想增長曲線的總體趨勢相符。在此基礎(chǔ)上，將上述相似度計算集成到協(xié)同過濾算法中，相似度計算是后續(xù)評分預測的基礎(chǔ)，因此將直接提升推薦算法的效果。

(a)

(b)

2.3 關(guān)聯(lián)度

從可擴展性問題可知，未考慮到用戶間的差異，將用戶不感興趣的項目加入到候選集，導致候選項目集中大部分項目是無用的，感興趣項目占比很低，故提高感興趣項目的占比是優(yōu)化算法效率的關(guān)鍵。在IBCF算法中，尋找項目的近鄰項目使用的是項目間的相似度信息，相似度信息在很大程度上反映了用戶對該項目的評價是否一致，而較少地考慮項目間依賴或者是順序關(guān)系，這種依賴的關(guān)系是尋找近鄰項目的重要因素[11]。

項目之間的關(guān)聯(lián)關(guān)系在實際中大量存在，這種關(guān)系很大程度上左右著用戶的選擇，而根據(jù)相似度生成候選集無法描述此種關(guān)系。如圖4(a)所示，用戶1瀏覽了項目A、B、C，用戶2的瀏覽記錄有項目B、C、D，后面的用戶3在瀏覽了項目B之后是否想著去瀏覽C?？隙ǖ模敶罅坑脩粼跒g覽了項目B之后去瀏覽項目C，可以認為項目B和項目C之間存在某種意義上的關(guān)聯(lián)關(guān)系。文中從該現(xiàn)象出發(fā)，引入1-頻繁項集的思想，計算項目間的關(guān)聯(lián)度矩陣，并依據(jù)項目的關(guān)聯(lián)度大小來生成候選集。

定義關(guān)聯(lián)度：關(guān)聯(lián)度用來衡量兩項目有聯(lián)系的強弱程度，即用戶在瀏覽了某商品后又瀏覽某一商品的可能性，大小用r表示，rmn的含義是項目m對項目n的關(guān)聯(lián)度，定義為項目m與n的共同用戶數(shù)與項目n的用戶數(shù)之比，實際含義是用戶在瀏覽了項目n后轉(zhuǎn)而去瀏覽m的比例，計算如下：

(8)

其中，Cm、Cn分別是項目m和n的用戶數(shù)。

根據(jù)關(guān)聯(lián)度的定義，可以計算所有項目間的關(guān)聯(lián)度并存儲為關(guān)聯(lián)矩陣Rk*k，如圖4(b)所示。rmn表示項目m對項目n的關(guān)聯(lián)，主對角線全為0，矩陣不是對稱的，即rmn≠rnm，兩項目按照出現(xiàn)順序的不同對用戶產(chǎn)生的影響不同，因此項目帶給用戶的關(guān)聯(lián)度也就不同。

圖4 關(guān)聯(lián)關(guān)系(a)和關(guān)聯(lián)矩陣(b)

針對IBCF依據(jù)相似度生成的項目候選集中感興趣占比太小的問題，在候選集選取過程中引入關(guān)聯(lián)度，使用關(guān)聯(lián)矩陣代替相似度產(chǎn)生候選集。根據(jù)用戶u的已有記錄項目集合i∈Iu，對其中的每一項目計算關(guān)聯(lián)度，以關(guān)聯(lián)度大小排序得到項目的k近鄰居集Nu={i1,i2,…,ik}，從中刪除所有Iu已存在的項目，得到候選集C。這樣候選集中的項目很大程度上與已有項目有強關(guān)聯(lián)，這種關(guān)系能夠大概率擊中用戶在未來的需求或興趣。另一方面，在評分預測的過程中，繼續(xù)使用相似度作為加權(quán)評分中的比重，這樣可以保留傳統(tǒng)協(xié)同過濾的高準確率，又可以避免出現(xiàn)在候選集中引入太多弱相關(guān)的項目而導致的低占比問題。

3 算法評估

3.1 算法流程

如上文所述，文中采用關(guān)聯(lián)度生成項目候選集，對其中的項目使用相似度按式9計算加權(quán)平均預測分，然后根據(jù)預測的評分按高低排序，最后將top-N項目推薦給用戶。

(9)

算法流程如下：

步驟1：在評分矩陣上根據(jù)提出的“S”型相似度計算方法和關(guān)聯(lián)度計算方法，得到項目間的相似度矩陣S和關(guān)聯(lián)矩陣R；

步驟2：在關(guān)聯(lián)矩陣R中，對用戶u的每一項目Iu獲取k最鄰居集Nu={i1,i2,…,ik}，合并所有Nu得到預選集合C'；

步驟3：剔除集合C'中用戶u已有記錄的部分，得到項目候選集C；

步驟4：對候選集中的所有項目e∈C，依據(jù)相似度和式9計算項目e的加權(quán)平均預測評分；

步驟5：對步驟4中所有項目的預測分由高到低排序，將每一用戶u的top-N項目作為用戶u的推薦對象。

3.2 實驗結(jié)果及分析

為了驗證文中算法的效果，選用MovieLens[12]中1M數(shù)據(jù)集，包括了6 040個用戶對3 952部電影的評分。文中采用10折交叉驗證[13]的方法，將數(shù)據(jù)集隨機劃分為10個子集，每次選用其中9份用作訓練、1份作為測試，重復10次，取10次結(jié)果的平均值作為實驗結(jié)果。

實驗一：比較提出的融合“S”型相似度和關(guān)聯(lián)度的協(xié)同過濾算法(CSRCF)和經(jīng)典的協(xié)同過濾(IBCF)的候選集的大小。圖5(a)展示的是在MovieLens數(shù)據(jù)集得到的上述兩種算法生成的平均候選集大小。開始階段，兩種算法的候選集基本相同，隨著近鄰數(shù)的增長，IBCF算法候選集會迅速增大，當近鄰數(shù)達到60時，候選集將達到200左右；而CSRCF算法則增長十分緩慢，當近鄰數(shù)增加到50后，候選集大小幾乎收斂在75左右，僅為前者的1/3。兩者對比之下，發(fā)現(xiàn)文中提出的依據(jù)關(guān)聯(lián)矩陣生成的候選集效果十分顯著，大幅降低了候選集的規(guī)模，避免在評分階段計算過多無效的項目。

實驗二：上述討論了兩種算法在候選集規(guī)模上的區(qū)別，接下來討論在減小候選集規(guī)模時，候選集中感興趣占比會如何變化。由圖5(a)可以看出，初始階段CSRCF比IBCF有著明顯優(yōu)勢，隨著近鄰數(shù)的增加，兩者的用戶感興趣占比都在下降，且保持著較大差距，IBCF僅為不到5%，最后CSRCF的用戶感興趣占比穩(wěn)定在15%左右，比前者高出10%。

綜合上述兩個實驗，可以認為IBCF算法根據(jù)相似度選取項目候選集時引入了不相關(guān)或弱相關(guān)的項目，導致候選集規(guī)模過大且用戶感興趣比例較??；而文中提出的CSRCF算法，從項目間的關(guān)聯(lián)性出發(fā)選取候選集，保證了候選集中的強相關(guān)性，在保證不減少用戶感興趣項目數(shù)量的前提下，大幅減小了候選集的規(guī)模且提升了用戶的感興趣比例，為后續(xù)預測階段減少了不必要的項目評分預測計算。

(a)

(b)

實驗三：為了驗證CSRCF算法的推薦效果，將其與文獻[10]提出的加權(quán)相似度協(xié)同過濾算法(WSBCF)以及傳統(tǒng)的協(xié)同過濾算法(IBCF)進行比較。在離線環(huán)境下，文中采用MAE(平均絕對誤差)[14]作為評估度量，三種算法MAE準確性結(jié)果如圖5(b)所示?？梢钥闯觯S著鄰居規(guī)模的增長，三種推薦算法的MAE都在減小，說明鄰居規(guī)模的增大一定程度上提高了準確性。傳統(tǒng)的IBCF隨著鄰居規(guī)模增大MAE緩慢減小，最后MAE基本穩(wěn)定在0.85左右；WSBCF算法在開始時推薦準確性顯著長，在鄰居規(guī)模為[45,55]內(nèi)達到推薦準確峰值，CSRCF算法在開始階段與WSBCF類似，MAE迅速下降，下降的速率較前者要快，然后在鄰居規(guī)模為35時到達最優(yōu)推薦效果，兩種算法都在鄰居規(guī)模繼續(xù)增大時MAE反而會增大，表明過多的鄰居規(guī)模會導致并不相似的用戶參與評分預測，引入不相關(guān)的評分噪聲導致推薦效果下降。

注意到CSRCF不論是在最優(yōu)推薦效果(MAE約為0.74)還是達到最優(yōu)推薦效果時用戶的鄰居規(guī)模較上述算法都有顯著提升，更小規(guī)模的鄰居用戶在大數(shù)據(jù)量推薦時減少計算負擔；較之前兩種算法，CSRCF算法的MAE值更小且收斂過程中下降得更快，證明提出的CSRCF算法能通過“S”型重合因子準確地描述用戶間相似度與共有評分項的真實關(guān)系，從而提高后續(xù)評分預測的準確性。

4 結(jié)束語

大多數(shù)推薦系統(tǒng)中，相似度是生成候選集和評分預測的基礎(chǔ)，決定著推薦的質(zhì)量。文中以推薦步驟為出發(fā)點，創(chuàng)造性地分離候選集生成和評分預測。針對候選集中存在大量弱或不相關(guān)的項目和用戶感興趣比例較低的問題，引入關(guān)聯(lián)度的概念，使用關(guān)聯(lián)矩陣代替相似度矩陣生成候選集來減小候選集規(guī)模；評分預測階段分析相似度對推薦效果的影響，對傳統(tǒng)相似度和基于加權(quán)相似度無法準確描述相似度的問題進行總結(jié)，詳細闡述了項目間相似度增長的理想曲線，提出了一種細粒度“S”型相似度來刻畫理想相似項目，最后在算法流程中融合關(guān)聯(lián)度和“S”型相似度。實驗結(jié)果表明，關(guān)聯(lián)度的引入減小了候選集規(guī)模，僅為前者的1/3，避免了預測階段對無效的項目進行評分，加快了推薦速度，從算法層面提高了可擴展性，改進的“S”型相似度在推薦準確率上較前者提高了4%。但未考慮在大數(shù)據(jù)環(huán)境下改進算法的時間復雜度，因此下一步將研究如何在分布式環(huán)境下提升該推薦算法的可擴展性。