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

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

0 引 言

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

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

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

1 問題分析

1.1 稀疏性問題

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

1.2 影響分析

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

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

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

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

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

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

1.3 擴(kuò)展性問題

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

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

圖2 候選集大小及感興趣項(xiàng)目比例

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

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

2.1 現(xiàn)有相似度

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

表1 評分矩陣示例

(1)

(2)

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

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

(3)

(4)

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

2.2 “S”型改進(jìn)相似度

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

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

(5)

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

(6)

(7)

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

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

(a)

(b)

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

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

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

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

(8)

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

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

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

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

3 算法評估

3.1 算法流程

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

(9)

算法流程如下：

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

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

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

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

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

3.2 實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

(a)

(b)

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

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

4 結(jié)束語

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