基于差異化資源分配的二部圖推薦算法

張功國，江 洋，成振華，劉 穎

(1.重慶郵電大學(xué)通信與信息工程學(xué)院，重慶400065;2.重慶市質(zhì)量和標(biāo)準(zhǔn)化研究院，重慶400023;3.重慶信科設(shè)計(jì)有限公司，重慶401121)

1 引言

隨著大數(shù)據(jù)時(shí)代的到來，信息過載問題變得越來越嚴(yán)重，推薦系統(tǒng)是用于解決信息過載的有效途徑，它用來給用戶推薦可能感興趣的事務(wù)[1]。推薦算法是推薦系統(tǒng)的核心，它用于處理輸入信息并將其形成推薦信息。近年來，基于二部圖的推薦算法受到了很多研究者的關(guān)注，該算法借鑒了物理學(xué)上熱傳導(dǎo)和物質(zhì)擴(kuò)散的思想[2]。周濤等人最早提出了一種基于二部圖的物質(zhì)擴(kuò)散推薦算法[3]，該算法傾向于給用戶推薦流行項(xiàng)目；文獻(xiàn)[4]在此基礎(chǔ)上對項(xiàng)目的初始資源進(jìn)行修正，引入一個(gè)參數(shù)β，通過把項(xiàng)目初始資源k(o)調(diào)整為k(o)β，抑制了流行項(xiàng)目的影響，從而提高了算法推薦的多樣性；Becatti等人在文獻(xiàn)[5]中按照一定的重啟動條件設(shè)定，在二部圖網(wǎng)絡(luò)結(jié)構(gòu)中加入隨機(jī)的游走過程，由此來尋找最佳的待推薦節(jié)點(diǎn)；He[6]等人考慮到項(xiàng)目對于用戶的吸引作用，提出在二部圖推薦系統(tǒng)中加入反饋調(diào)節(jié)，在多個(gè)數(shù)據(jù)集中實(shí)現(xiàn)了推薦新穎度的提高。

本文結(jié)合已有研究提出了一種基于差異化資源分配的二部圖推薦算法。分別對項(xiàng)目初始資源和資源分配系數(shù)進(jìn)行了差異化設(shè)置，通過實(shí)驗(yàn)驗(yàn)證了該算法相比其它類似的算法在推薦精度和多樣性上都有所提升。

2 傳統(tǒng)二部圖推薦算法

將推薦系統(tǒng)建模成二部圖，其中節(jié)點(diǎn)的兩個(gè)集合分別代表用戶集U和項(xiàng)目集O，當(dāng)用戶選擇了項(xiàng)目則將它們相連，即兩者形成連邊[7]。一個(gè)由n個(gè)用戶U={u1，u2…un}和m個(gè)項(xiàng)目O={o1，o2，…，om}構(gòu)成的二部圖可以用鄰接矩陣A={aαi}n，m表示，如果用戶uα選擇了項(xiàng)目oi則aαi=1，未選擇則aαi=0。二部圖推薦算法認(rèn)為，用戶選擇過的項(xiàng)目有向其推薦其它項(xiàng)目的能力，這樣的能力可以在二部圖中進(jìn)行傳遞，從而產(chǎn)生推薦。

傳統(tǒng)二部圖推薦算法具體步驟如下：

1)項(xiàng)目初始資源配置

設(shè)用戶uα為目標(biāo)用戶，則各項(xiàng)目初始資源值的表達(dá)式如式(1)所示

f(oi)=aαi

(1)

如果用戶uα選擇了項(xiàng)目oi則aαi=1，即該項(xiàng)目的初始資源為1，未選擇則aαi=0。

2)項(xiàng)目將資源傳遞給用戶

在傳統(tǒng)二部圖推薦算法中，第一次資源流轉(zhuǎn)采用均勻分配的方式由項(xiàng)目流向用戶，項(xiàng)目oi的初始資源f(oi)≥0，則經(jīng)過第一次資源流轉(zhuǎn)，任意用戶uβ獲得的資源如式(2)所示

(2)

其中，aβi為鄰接矩陣A={aαi}n，m中的對應(yīng)元素，k(oi)為項(xiàng)目oi的度即該項(xiàng)目被多少用戶選擇過。

3)用戶將資源再次傳遞給項(xiàng)目

用戶將第一階段獲得的資源傳遞給相對應(yīng)的項(xiàng)目，也采用均勻分配原則。在該過程中任意項(xiàng)目oj所獲得的資源如式(3)所示

(3)

其中，k(uβ)為用戶uβ的度，即該用戶選擇過多少項(xiàng)目。

4)生成推薦列表

將目標(biāo)用戶未選擇過的項(xiàng)目按照f(oj)的大小進(jìn)行排序，將所獲資源最多的前L項(xiàng)推薦給用戶，L為推薦列表長度。

如圖1所示，(a)表示該二部圖由四個(gè)用戶和三個(gè)項(xiàng)目組成，x，y，z分別表示三個(gè)項(xiàng)目的初始資源，(b)表示經(jīng)第一步資源流轉(zhuǎn)后每個(gè)用戶所獲得的相應(yīng)資源值，(c)表示經(jīng)兩步資源流轉(zhuǎn)以后每個(gè)項(xiàng)目最終所獲得的資源。則三個(gè)項(xiàng)目的最終資源x′、y′、z′如式(4)所示

(4)

圖1 基于二部圖的資源分配推薦算法資源流轉(zhuǎn)圖

3 基于差異化資源分配的二部圖推薦算法

傳統(tǒng)二部圖推薦算法在進(jìn)行初始資源設(shè)置時(shí)往往僅依靠項(xiàng)目是否被目標(biāo)用戶選擇而進(jìn)行0/1設(shè)置，這樣會丟失系統(tǒng)里面的很多有用信息；另外在進(jìn)行資源流轉(zhuǎn)時(shí)也僅僅依靠項(xiàng)目度和用戶度來平均分配，這樣會導(dǎo)致推薦有失準(zhǔn)確性。針對以上問題，提出一種基于差異化資源分配的二部圖推薦算法，新算法具體如下：

步驟一：初始資源差異化設(shè)置

在現(xiàn)實(shí)生活中可能存在著惡意評分等特殊因素，在這種情況下評分不能代表用戶的真實(shí)偏好[8]。利用規(guī)范化對評分進(jìn)行處理，消除評分不利影響。評分規(guī)范化的預(yù)處理方法如式(5)所示

(5)

其中，rαi為用戶uα對項(xiàng)目oi的初始評分，Pi為項(xiàng)目oi得到的平均評分值，Qα為用戶uα對所有項(xiàng)目評分的均值，預(yù)處理以后更能體現(xiàn)用戶的真實(shí)喜好。若Pi>Qα則代表項(xiàng)目oi受用戶的喜愛，因此對評分進(jìn)行增強(qiáng)修正，反之對評分進(jìn)行削弱修正。

為了減小由于用戶評分尺度不同而帶來的計(jì)算誤差，進(jìn)一步優(yōu)化評分?jǐn)?shù)據(jù)，采用最大最小值法[9]進(jìn)行修正，如式(6)所示

(6)

其中，rmax、rmin分別表示用戶uα在系統(tǒng)中給出的最大和最小評分值，為了預(yù)防分母為0，設(shè)定極小值p為0.001，同時(shí)為了實(shí)驗(yàn)方便，設(shè)定極小值q為0.01。

傳統(tǒng)的大多數(shù)推薦算法都沒有考慮到“興趣偏移”問題，即用戶的興趣會隨著時(shí)間的變化而改變，項(xiàng)目的流行度也會隨時(shí)代而變。時(shí)間因素在推薦系統(tǒng)中也是一個(gè)重要信息，對用戶的喜好有著很大的影響。本文基于德國心理學(xué)家艾賓浩斯所提出的記憶遺忘曲線[10]，將時(shí)間衰減函數(shù)定義為式(7)所示(時(shí)間計(jì)量單位為天)

(7)

其中，fα，i(t)表示當(dāng)時(shí)間為t時(shí)，用戶uα對項(xiàng)目oi“興趣偏移”的衰減率，tα表示用戶uα在系統(tǒng)中初次評分的時(shí)間，tα，i表示用戶uα對項(xiàng)目oi進(jìn)行評分操作的時(shí)間。fα，i(t)的取值范圍在e-1到1之間，符合衰減率的要求。

經(jīng)過評分規(guī)范化、最大最小值修正以及時(shí)間衰減函數(shù)的量化，最終實(shí)現(xiàn)了項(xiàng)目初始資源的差異化設(shè)置，如式(8)所示

(8)

步驟二：第一階段資源分配

在基于二部圖的推薦算法中，項(xiàng)目將資源根據(jù)用戶項(xiàng)目相互之間的選擇關(guān)系平均分配給相應(yīng)的用戶，考慮到以下兩點(diǎn)：①如果兩個(gè)用戶共同選擇的項(xiàng)目數(shù)比較多，那么他們的興趣相似性可能比較高；②如果兩個(gè)用戶對項(xiàng)目的評分大小比較接近，代表其偏好更加的相近?；诖?，本文利用修正后的用戶評分相似性函數(shù)對第一階段資源分配系數(shù)進(jìn)行差異化設(shè)置，使得與目標(biāo)用戶興趣相似的用戶能夠得到更多的資源。

兩個(gè)用戶共同選擇的項(xiàng)目比例如式(9)所示

(9)

其中，Iα和Iβ分別表示用戶uα和uβ所選擇的項(xiàng)目的集合，兩個(gè)用戶共同選擇的項(xiàng)目比例越大，他們的興趣就可能越相近。

交互用戶指的是有公共選擇的用戶，他們的交互關(guān)系指的是對于項(xiàng)目的喜愛程度是否一致。本文通過積極評分還是消極評分判定用戶交互成功還是失敗。如果用戶對項(xiàng)目評分小于他給出的評分均值，說明它為消極評分；反之則為積極評分。倘若用戶uα和uβ對相同項(xiàng)目oi給出的都是積極或消極評分，說明交互用戶間持有相同觀點(diǎn)，他們交互是成功的；反之交互是失敗的。交互關(guān)系判定方法如式(10)所示

(10)

計(jì)算兩個(gè)用戶評分相似性，需要收集雙方交互間歷史總記錄。假設(shè)s和f分別代表交互用戶彼此間成功和失敗次數(shù)。即每次交互用戶間項(xiàng)目交互成功，那么s+1(i∈Is)，否則f+1(i∈If)。

結(jié)合項(xiàng)目比例系數(shù)、交互關(guān)系以及評分偏差，最終得到用戶評分相似性函數(shù)，如式(11)所示

(11)

其中，Is表示兩用戶交互成功的項(xiàng)目集合，If表示交互失敗的項(xiàng)目集合。

利用新構(gòu)建的用戶評分相似性函數(shù)得到第一階段的資源分配系數(shù)，如式(12)所示

(12)

Hα，βi表示用戶uβ與目標(biāo)用戶uα的相似度占所有選擇了項(xiàng)目oi的用戶與目標(biāo)用戶uα的相似度之和的比例，取值在0到1之間，Hα，βi越大表示在所有已經(jīng)選擇項(xiàng)目oi的用戶群體中，用戶uα與uβ比其他用戶更為相似，則項(xiàng)目oi上的初始資源就會較多的傳遞到用戶uβ。

假設(shè)選定用戶uα為目標(biāo)用戶并為其推薦，則在第一階段資源流轉(zhuǎn)以后傳遞到任意用戶uβ的資源量如式(13)所示

(13)

步驟三：第二階段資源分配

在第二階段資源分配中，推薦者是與目標(biāo)用戶有共同選擇的用戶，這些用戶更傾向于推薦自己喜愛的項(xiàng)目。因此在第二階段資源分配中也加入了用戶的顯性偏好，把資源分配系數(shù)定義成用戶對項(xiàng)目的評分比例zβ，j，如式(14)所示

(14)

其中，Max(β)是用戶uβ在系統(tǒng)中給出的最大評分，zβ，j越大則認(rèn)為用戶更加愿意推薦該項(xiàng)目給其他用戶。由此所有作為鄰居用戶的推薦者推薦的項(xiàng)目都是各自認(rèn)為最好的，并且避免了用戶的評分尺度不一的問題。則在第二階段資源流轉(zhuǎn)后傳遞到任意項(xiàng)目oj的資源如式(15)所示

(15)

其中，k(uβ)為用戶uβ的度，f(uβ)由步驟二所得。

步驟四：推薦：

將目標(biāo)用戶未選擇過的項(xiàng)目按照f(oj)的大小進(jìn)行排序，將所獲資源最多的前L項(xiàng)推薦給用戶，L為推薦列表長度。

4 實(shí)驗(yàn)分析

4.1 實(shí)驗(yàn)數(shù)據(jù)

在選擇數(shù)據(jù)集時(shí)本文選用了推薦系統(tǒng)中最經(jīng)典的MovieLens數(shù)據(jù)集和Netflix數(shù)據(jù)集。前者由943個(gè)用戶和1682部電影組成，用戶使用整數(shù)1-5對電影進(jìn)行評分，評分越大表示用戶喜愛程度越強(qiáng)。后者曾用于全球推薦系統(tǒng)競賽，原始的Netflix數(shù)據(jù)集非常大，本文從中截取了一個(gè)由 10000個(gè)用戶和6000個(gè)電影組成的數(shù)據(jù)子集，該數(shù)據(jù)集相對MovieLens數(shù)據(jù)集的選擇關(guān)系要復(fù)雜很多。在實(shí)驗(yàn)中，將數(shù)據(jù)集隨機(jī)分成兩部分：80%作為訓(xùn)練集，用于建立推薦模型，其余20%作為測試集，用于驗(yàn)證模型性能。為了確保結(jié)果更加準(zhǔn)確，實(shí)驗(yàn)均采用五折交叉法驗(yàn)證測試。

4.2 評價(jià)指標(biāo)

準(zhǔn)確率是指推薦算法的結(jié)果中用戶實(shí)際選擇的項(xiàng)目占推薦結(jié)果的項(xiàng)目總數(shù)的比例，定義如式(16)所示

(16)

其中，hits是為目標(biāo)用戶準(zhǔn)確推薦的項(xiàng)目的數(shù)量，recset是推薦列表的長度。準(zhǔn)確率越大，說明該推薦結(jié)果越能反映出用戶的喜好。

召回率指的是推薦結(jié)果中實(shí)際的項(xiàng)目命中數(shù)占在理論上最大的可能命中數(shù)的比例，定義如式(17)所示

(17)

其中，hits是為目標(biāo)用戶準(zhǔn)確推薦的項(xiàng)目的數(shù)量，testset是理論上最大的可能命中數(shù)。召回率越大，說明推薦結(jié)果對用戶的喜好的覆蓋率高，即推薦系統(tǒng)能夠更大程度的滿足用戶的需求。

通常情況下Pr ecision和Re call都是越高越好，然而事實(shí)上兩者在某些情況下是相互矛盾的。F1是Pr ecision和Re call的加權(quán)調(diào)和平均，能夠有效的在準(zhǔn)確率和召回率之間取得平衡。其定義如式(18)所示

(18)

F1的值越高，說明推薦算法的綜合準(zhǔn)確性越好。

本文使用漢明距離(Hamming distance，HD)來評估推薦算法的多樣性，它描述了用戶間推薦列表之間的差異性。如式(19)所示

(19)

其實(shí)，m表示用戶數(shù)，L表示推薦列表的長度，Q=|βi∩βj|表示兩用戶的推薦列表中的相同項(xiàng)目的數(shù)量，HD越大表明推薦結(jié)果越多樣化。

4.3 實(shí)驗(yàn)結(jié)果與分析

將本文所提出的基于差異化資源分配的二部圖推薦算法(BGRA)與基于熱傳導(dǎo)的二部圖推薦算法(HC)、基于物質(zhì)擴(kuò)散的二部圖推薦算法(MD)、基于物質(zhì)擴(kuò)散與熱傳導(dǎo)的混合推薦算法(HPH)以及文獻(xiàn)[11]提出的基于二部圖網(wǎng)絡(luò)的非均勻資源分配推薦算法(NURA)進(jìn)行對比實(shí)驗(yàn)。

首先比較各個(gè)算法的推薦集質(zhì)量，評價(jià)指標(biāo)包括準(zhǔn)確率Pr ecision、召回率Re call和F1系數(shù)。

圖2 Precision值對比結(jié)果

如圖2所示，在兩個(gè)數(shù)據(jù)集中當(dāng)推薦列表長度較小時(shí)，BGRA算法的準(zhǔn)確率和HPH(α=0.5)、NURA表現(xiàn)差不多，隨著推薦列表長度的增加，BGRA的準(zhǔn)確率明顯要高于其它幾種算法，證明BGRA有著較好的準(zhǔn)確率。只考慮推薦多樣性的HC算法明顯要比其中幾種算法的推薦準(zhǔn)確率低。

圖3 Recall值對比結(jié)果

如圖3所示，隨著推薦列表長度的增加幾種算法的召回率都有所上升，這是因?yàn)殡S著推薦列表的增加，算法能夠預(yù)測到的用戶喜愛的電影數(shù)量變多，相應(yīng)的未能命中的數(shù)量就少了。在MovieLens數(shù)據(jù)集中，BGRA、HPH、NURA三種算法的召回率表現(xiàn)相似。但在相對復(fù)雜的Netflix數(shù)據(jù)集中，BGRA算法在召回率的總體表現(xiàn)要優(yōu)于其它幾種算法。

圖4 F1值對比結(jié)果

如圖4所示，各個(gè)算法的F1系數(shù)變化曲線轉(zhuǎn)折點(diǎn)均在推薦列表長度為20的時(shí)候。只注重推薦多樣性的HC算法依然是幾種算法中F1系數(shù)表現(xiàn)最差的。在MovieLens數(shù)據(jù)集中，BGRA算法在F1系數(shù)方面并不太理想，但在Netflix數(shù)據(jù)集中優(yōu)于其它四種算法。

其次在推薦多樣性比較中，如圖5所示。HC算法的推薦多樣性要比MD、HPH算法好很多，在Netflix數(shù)據(jù)集中本文提出的BGRA算法要好于其它幾種算法，這主要是因?yàn)樵谫Y源流轉(zhuǎn)過程中加入了分配系數(shù)的差異化設(shè)置，使得算法推薦出來的電影更具多樣化。

圖5 HD值對比結(jié)果

5 結(jié)束語

本文提出了一種基于差異化資源分配的二部圖推薦算法。首先利用評分規(guī)范化、最大最小值法以及時(shí)間遺忘曲線對項(xiàng)目的初始資源進(jìn)行了差異化設(shè)置。然后分別利用用戶評分相似性函數(shù)和用戶偏好函數(shù)對兩個(gè)階段的分配系數(shù)進(jìn)行了差異化設(shè)置，使資源流轉(zhuǎn)變得更加合理。最后通過實(shí)驗(yàn)證明在較復(fù)雜的數(shù)據(jù)集中算法的準(zhǔn)確率和多樣性都有很大的提升。但是隨著數(shù)據(jù)量的增加，推薦需要的開銷變大，因此下一步研究的重點(diǎn)是如果改善推薦的可擴(kuò)展性。