基于改進(jìn)NSGA-II的推薦算法

張海潮，楊連賀

(天津工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，天津 300387)

0 引 言

推薦算法是根據(jù)用戶偏好需求模型來(lái)進(jìn)行項(xiàng)目推薦,與用戶偏好需求越匹配的項(xiàng)目則越傾向于推薦給用戶[1]。傳統(tǒng)的推薦算法大多只將準(zhǔn)確率作為評(píng)價(jià)指標(biāo)[2]。這類基于準(zhǔn)確率的推薦算法雖然能夠保證一定的準(zhǔn)確率，但會(huì)導(dǎo)致一些無(wú)用的推薦。因此，許多研究人員致力于推薦長(zhǎng)尾項(xiàng)目或流行度低的項(xiàng)目[3]，而這類推薦會(huì)導(dǎo)致準(zhǔn)確率降低。在推薦算法中，提高準(zhǔn)確率和增加多樣性是兩個(gè)相互矛盾的性能指標(biāo)，為了使這兩個(gè)指標(biāo)都盡可能地達(dá)到最優(yōu)化，需要在其中進(jìn)行協(xié)調(diào)和折衷處理。因此許多研究人員將多目標(biāo)優(yōu)化引入了推薦系統(tǒng)[4]。文獻(xiàn)[5]提出了一個(gè)多目標(biāo)推薦框架，該框架在推薦長(zhǎng)尾項(xiàng)目的同時(shí)盡可能地降低精度的損失。文獻(xiàn)[6]提出了一種多目標(biāo)模擬退火方法，有效地緩解了長(zhǎng)尾問題。文獻(xiàn)[7]提出了一種推薦系統(tǒng)的多目標(biāo)進(jìn)化算法，該算法相較于傳統(tǒng)算法具有良好的推薦多樣性。文獻(xiàn)[8]提出了一種基于SVD和多目標(biāo)免疫優(yōu)化的推薦算法，改善了推薦系統(tǒng)的準(zhǔn)確性-多樣性的困境。

遺傳算法是一種全局隨機(jī)搜索和優(yōu)化方法[9]。其中NSGA-II算法由于其自身的簡(jiǎn)單有效性，已成功地應(yīng)用于大量多目標(biāo)優(yōu)化問題[10]。

本文首先通過概率矩陣模型對(duì)目標(biāo)用戶產(chǎn)生推薦候選集，將推薦結(jié)果的準(zhǔn)確率和多樣性作為目標(biāo)函數(shù)，把推薦問題轉(zhuǎn)化為多目標(biāo)優(yōu)化問題，并根據(jù)改進(jìn)的NSGA-II算法對(duì)目標(biāo)用戶產(chǎn)生一組推薦，實(shí)驗(yàn)結(jié)果表明了所提算法的有效性。

1 相關(guān)技術(shù)

1.1 概率矩陣分解模型

概率矩陣分解(probabilistic matrix factorization)是從概率的角度來(lái)預(yù)測(cè)用戶對(duì)物品的評(píng)分，是隱語(yǔ)義模型的概率化形式[11]。該模型假設(shè)用戶U和項(xiàng)目V的特征矩陣均服從高斯分布，通過評(píng)分矩陣中的已知值得到U和V的特征矩陣，并用特征矩陣去預(yù)測(cè)評(píng)分矩陣中的未知值。

本文利用概率矩陣分解模型預(yù)測(cè)評(píng)分矩陣中的未知值，并根據(jù)預(yù)測(cè)評(píng)分對(duì)目標(biāo)用戶產(chǎn)生推薦項(xiàng)目的候選集。

1.2 多目標(biāo)優(yōu)化

多目標(biāo)優(yōu)化問題是指使多個(gè)目標(biāo)在給定區(qū)域盡可能同時(shí)達(dá)到最優(yōu)，然而這些目標(biāo)通常是相互沖突和影響的。多目標(biāo)優(yōu)化問題描述如下

(1)

式中：x=(x1,x2,…,xn)T是決策向量，Ω是x的向量空間，m是目標(biāo)個(gè)數(shù)。Pareto支配、Pareto最優(yōu)解、Pareto最優(yōu)解集、Pareto前沿定義請(qǐng)參見文獻(xiàn)[12]。

1.3 NSGA-II算法

算法首先隨機(jī)產(chǎn)生大小為N的父代種群P0，種群根據(jù)非支配性進(jìn)行排序，每個(gè)個(gè)體都被分配一個(gè)適應(yīng)度，使用錦標(biāo)賽選擇、交叉和變異操作產(chǎn)生了大小為N的子代種群Q0。由于引入了精英策略，自初代后的過程有所不同。圖1 描述的是第t代的過程，首先將第t代的父代種群Pt和通過交叉變異產(chǎn)生的子代種群Qt合并為Rt，Rt通過快速非支配排序得到一系列非支配Pareto解集，分別為F1,F2,F3…,它們的等級(jí)依次降低，首先選擇F1進(jìn)入種群Pt+1，如果F1小于N，則繼續(xù)選擇F2進(jìn)入Pt+1，直到F1+F2+…+Fi剛好大于或等于N，這里稱Fi為臨界層，再對(duì)臨界層計(jì)算擁擠距離，優(yōu)先選擇擁擠度小的個(gè)體先進(jìn)入Pt+1，直至達(dá)到最大迭代次數(shù)。

圖1 NSGA-II算法過程

2 存在的問題

2.1 擁擠距離計(jì)算

NSGA-II算法的排擠機(jī)制是建立在個(gè)體的擁擠距離之上的。擁擠距離用于估計(jì)總體中某一特定個(gè)體周圍的解的密度，第i個(gè)個(gè)體的擁擠距離是它所在層級(jí)的兩個(gè)相鄰個(gè)體在每個(gè)目標(biāo)上的距離之和。在同一層級(jí)上的個(gè)體，擁擠距離大的個(gè)體被優(yōu)先選擇。這一策略保留了擁擠度較小的個(gè)體。但是該策略存在一定的局限性：由于擁擠距離只計(jì)算了一次，如果擁擠距離較小的多個(gè)個(gè)體集中在了一個(gè)區(qū)域，那么這些個(gè)體將同時(shí)被刪除。

2.2 交叉變異算子

遺傳算法在進(jìn)化代數(shù)接近終止代數(shù)時(shí)，種群接近于一個(gè)齊次種群。這是由于在選擇交叉?zhèn)€體時(shí)采取精英策略，適應(yīng)度好的個(gè)體更容易進(jìn)入交配池，所以在交配池中會(huì)出現(xiàn)重復(fù)的個(gè)體，因此，迭代次數(shù)越多，個(gè)體的重復(fù)率越大。一般會(huì)通過變異操作改善這種情況，但是傳統(tǒng)的變異算子會(huì)設(shè)定一個(gè)固定值，且變異概率較小，即使進(jìn)行了變異操作，也會(huì)出現(xiàn)種群過早收斂的現(xiàn)象。

3 改進(jìn)的NSGA-II算法

3.1 改進(jìn)的擁擠距離計(jì)算

為了改善上述關(guān)于擁擠距離計(jì)算中存在的問題，本文提出了一種動(dòng)態(tài)調(diào)整擁擠距離的方法。計(jì)算過程如下：

(1)計(jì)算相鄰兩個(gè)個(gè)體之間的歐式距離。假設(shè)有n個(gè)個(gè)體，第k(k∈(2,n-1)) 個(gè)個(gè)體和第k+1個(gè)個(gè)體之間的擁擠距離為

(2)

式中：m為目標(biāo)的數(shù)目，fi(k) 為第k個(gè)個(gè)體在第i個(gè)目標(biāo)上的值，fimin為第i個(gè)目標(biāo)的最小值，fimax為第i個(gè)目標(biāo)的最大值。

(2)找到最小擁擠距離I[k,k+1]， 比較I[k-1,k] 與I[k+1,k+2] 的擁擠距離，若I[k-1,k] 小，則淘汰個(gè)體k，否則，淘汰個(gè)體k+1。

(3)更新?lián)頂D距離。

(4)判斷是否滿足需要個(gè)體的數(shù)目。若不滿足，則返回(2)，否則，終止。

例如，在圖2中，I[D,E] 的擁擠距離最小，則比較I[C,D] 與I[E,F] 的擁擠距離，因I[E,F] 的擁擠距離更小，故淘汰個(gè)體E，刪除I[D,E] 與I[E,F] 的擁擠距離，并重新計(jì)算I[D,F] 的擁擠距離。

圖2 改進(jìn)的擁擠距離計(jì)算

3.2 改進(jìn)的交叉變異算法

針對(duì)遺傳算法中種群過早收斂的問題，本文設(shè)計(jì)了一種基于近親系數(shù)的交叉變異算法。該算法同時(shí)考慮了進(jìn)化代數(shù)對(duì)交叉變異的影響。為方便描述，本文有如下定義：

定義1 近親系數(shù)

(3)

式中：F(Xi,Xj) 表示兩個(gè)個(gè)體的近親系數(shù)，l是個(gè)體基因的長(zhǎng)度，xik表示個(gè)體Xi的第k個(gè)基因，μk表示第k個(gè)等位基因的權(quán)重，μk在本文中取1/l。

定義2 近親個(gè)體：若兩個(gè)個(gè)體的近親系數(shù)大于設(shè)定閾值，則認(rèn)為這兩個(gè)個(gè)體為近親個(gè)體。

交叉變異算法描述如下：

(1)隨機(jī)選擇兩個(gè)父代個(gè)體Xi和Xj(個(gè)體長(zhǎng)度為l)，找到兩個(gè)個(gè)體相同的等位基因集Ns和不同的等位基因集Nd。

(2)計(jì)算近親系數(shù)，判斷兩個(gè)父代個(gè)體是否屬于近親個(gè)體，若是，則返回步驟(1)，否則執(zhí)行步驟(3)。

(3)將Ns中的基因傳入子代個(gè)體，并在基因集Nd中隨機(jī)選擇l-|Ns| 個(gè)基因傳入子代個(gè)體。

(4)根據(jù)相同等位基因的個(gè)數(shù)計(jì)算需要變異基因的個(gè)數(shù)，計(jì)算公式如下

(4)

式中：Nv表示需要變異的個(gè)數(shù)。

(5)根據(jù)相同等位基因的個(gè)數(shù)以及當(dāng)前迭代次數(shù)ei計(jì)算變異概率，計(jì)算公式如下：

(5)

式中：α為一個(gè)0～1的系數(shù)，eva為總的迭代次數(shù)。

(6)根據(jù)變異個(gè)數(shù)和變異概率進(jìn)行變異。

例如，A和B是兩個(gè)父代個(gè)體，首先找到它們相同的等位基因集并傳入子代C中(相同基因?yàn)?,18,9,2)，再?gòu)牟煌牡任换蚣须S機(jī)選擇6個(gè)基因傳入子代中(例如：7,35,24,6,16,8)，根據(jù)式(4)和式(5)計(jì)算變異基因個(gè)數(shù)和變異概率，分別為2和p′v， 如圖3所示，在位置2和位置6進(jìn)行了變異。

圖3 改進(jìn)的交叉變異算法

4 多目標(biāo)推薦算法

4.1 目標(biāo)函數(shù)

推薦系統(tǒng)主要關(guān)注的是推薦的準(zhǔn)確率，這里用f1表示推薦的準(zhǔn)確率，公式如下

(6)

式中：R表示對(duì)用戶i的推薦列表，Rij表示用戶i對(duì)項(xiàng)目j的預(yù)測(cè)評(píng)分。

除了推薦的準(zhǔn)確率，我們也希望能夠增加推薦的多樣性，這里用f2表示推薦的多樣性。公式如下

(7)

式中：s(j,k) 表示項(xiàng)目j和項(xiàng)目k的相似度。

為提高推薦的準(zhǔn)確率，應(yīng)該使f1盡可能大。為了提高推薦的多樣性，應(yīng)該使f2盡可能小。但是準(zhǔn)確度和多樣性是兩個(gè)互相沖突的目標(biāo)，因此推薦問題轉(zhuǎn)換成了多目標(biāo)優(yōu)化問題

min{-f1,f2}

(8)

4.2 算法流程

Input：Rm×n，User_ID，eva，L，N//輸入評(píng)分矩陣，目標(biāo)用戶ID，最大迭代次數(shù)，推薦列表長(zhǎng)度，種群規(guī)模。

Output：set[]為目標(biāo)用戶的推薦解集。

步驟1 使用PMF算法產(chǎn)生候選集S；

步驟2 從S中產(chǎn)生N組初始種群P0，并計(jì)算初始種群中個(gè)體的f1和f2的值；

步驟3 將Pt(初代為P0)進(jìn)行快速非支配排序，使用錦標(biāo)賽選擇機(jī)制產(chǎn)生規(guī)模為N的種群Peli；

步驟4 根據(jù)3.2節(jié)介紹算法對(duì)Peli進(jìn)行交叉變異操作，得到子代種群Qt(初代為Q0)，大小為N；

步驟5 將Pt和Qt合并為Rt，大小為2N，對(duì)Rt進(jìn)行快速非支配排序，得到的層級(jí)為F1,F2,F3…。先將F1中的個(gè)體加入到下一次迭代種群Pt+1，若 |F1|

步驟6 根據(jù)3.1節(jié)中介紹的算法對(duì)Fm進(jìn)行擁擠距離計(jì)算，每次刪除一個(gè)擁擠度最大的個(gè)體并更新?lián)頂D距離，直至Fm中剩余N-(|F1|+|F2|+…+|Fm-1|) 個(gè)個(gè)體為止；

步驟7 判斷是否達(dá)到迭代次數(shù)，若沒有，則返回步驟3，否則，終止。

4.3 算法復(fù)雜度分析

假設(shè)目標(biāo)函數(shù)數(shù)目為M，種群大小為N，則改進(jìn)的NSGA-II算法的時(shí)間復(fù)雜度計(jì)算如下：

非支配排序的時(shí)間復(fù)雜度為O(M×(2N)2)； 擁擠距離計(jì)算的時(shí)間復(fù)雜度為O(M(2N)log(2N))； 同一層級(jí)選擇的時(shí)間復(fù)雜度為O(2Nlog(2N))； 交叉變異的時(shí)間復(fù)雜度為O(N)， 所以算法總體的時(shí)間復(fù)雜度為O(M×(2N)2)。

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

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

為了驗(yàn)證提出的算法的有效性，本文分別在Movielens數(shù)據(jù)集和Jester數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)。Movielens數(shù)據(jù)集包含了943名用戶對(duì)1682部電影的10萬(wàn)條評(píng)分?jǐn)?shù)據(jù)，所有的評(píng)分值落在[0,5]區(qū)間內(nèi)，每位用戶至少對(duì)20部電影評(píng)分。Jester數(shù)據(jù)集包含63 978名用戶對(duì)150條笑話的超過170萬(wàn)條評(píng)論，所有評(píng)分值落在[-10,10]區(qū)間內(nèi)，本文將評(píng)分值映射到[0,5]區(qū)間上。在本實(shí)驗(yàn)中，將數(shù)據(jù)集隨機(jī)劃分80%的數(shù)據(jù)作為訓(xùn)練集，20%的數(shù)據(jù)作為測(cè)試集。

5.2 參數(shù)設(shè)置

本文參數(shù)設(shè)置見表1。

表1 實(shí)驗(yàn)參數(shù)

5.3 評(píng)價(jià)指標(biāo)

本文采用推薦系統(tǒng)中常用的度量指標(biāo)，準(zhǔn)確率、多樣性和新穎度作為推薦結(jié)果的評(píng)價(jià)指標(biāo)

(9)

(10)

pop=log(1+N(i))

(11)

其中，R表示所有用戶的集合，R(u) 表示在訓(xùn)練集上通過訓(xùn)練推薦給用戶的列表，T(u) 表示在測(cè)試集上用戶的評(píng)價(jià)過的項(xiàng)目列表。s(i,j) 表示項(xiàng)目i和項(xiàng)目j的相似度。N(i) 表示評(píng)論項(xiàng)目i的用戶數(shù)目。

5.4 實(shí)驗(yàn)結(jié)果

算法對(duì)目標(biāo)用戶產(chǎn)生一組推薦列表，圖4給出了用戶1的帕累托前沿。

圖4 用戶1的帕累托前沿

圖4中每一個(gè)點(diǎn)都代表對(duì)目標(biāo)用戶的一組推薦列表，由于算法是在準(zhǔn)確率和多樣性之間進(jìn)行權(quán)衡，所以f1越大，f2就越小。同理，f1越小，f2就越大。

為了驗(yàn)證所提算法的有效性，下面將本文算法與PMF算法和未改進(jìn)的基于NSGA-II的推薦算法進(jìn)行比較。本文算法和基于NSGA-II的推薦算法隨機(jī)從測(cè)試集中取50個(gè)用戶，并求出對(duì)每個(gè)用戶產(chǎn)生的20組解在評(píng)測(cè)指標(biāo)上的平均值，實(shí)驗(yàn)結(jié)果如圖5所示。

圖5 3種算法評(píng)測(cè)指標(biāo)比較

圖5(a)展示的是3種算法推薦結(jié)果的準(zhǔn)確率。可以看出，在兩個(gè)數(shù)據(jù)集上PMF算法的準(zhǔn)確率最高，基于 NSGA-II 的推薦算法和本文算法的準(zhǔn)確率較低，這是由于PMF算法會(huì)推薦預(yù)測(cè)評(píng)分最高的10個(gè)項(xiàng)目，而另外兩種算法要在準(zhǔn)確率和多樣性之間進(jìn)行權(quán)衡，必然會(huì)導(dǎo)致準(zhǔn)確率的降低。但是本文算法的準(zhǔn)確率在兩個(gè)數(shù)據(jù)集上的準(zhǔn)確率要高于基于NSGA-II的推薦算法。

圖5(b)展示的是3種算法推薦結(jié)果的多樣性。由于本文采用推薦項(xiàng)目之間的相似度衡量推薦結(jié)果的多樣性，所以推薦結(jié)果的值越小，多樣性就越高。由圖中可以看出，在多樣性方面，無(wú)論是在Movielens數(shù)據(jù)集還是在Jester數(shù)據(jù)集上，本文算法都優(yōu)于另外兩種算法。基于NSGA-II的推薦算法在兩個(gè)數(shù)據(jù)集上相較于PMF算法在多樣性方面也有所提高。

圖5(c)展示的是3種算法推薦結(jié)果的新穎度。由實(shí)驗(yàn)結(jié)果可以看出，在Movielens數(shù)據(jù)集上PMF算法新穎度略好于其它兩種算法，但是在Jester數(shù)據(jù)集上PMF算法明顯比另外兩種算法差。本文算法比基于NSGA-II的推薦算法在新穎度方面略好。

實(shí)驗(yàn)結(jié)果表明，本文算法雖然在準(zhǔn)確率上相較于PMF算法略低，但是在準(zhǔn)確率和多樣性上都比基于NSGA-II的推薦算法表現(xiàn)好。因此對(duì)于大多數(shù)用戶來(lái)說(shuō)，本文算法能夠在不降低準(zhǔn)確率甚至有所提高的同時(shí)，有效地提高推薦的多樣性，從而驗(yàn)證了改進(jìn)算法的有效性。

6 結(jié)束語(yǔ)

針對(duì)傳統(tǒng)的推薦算法中單一追求推薦結(jié)果的準(zhǔn)確率而忽略多樣性的情況，本文提出了一種基于改進(jìn)NSGA-II的算法的推薦算法，通過一次推薦可以對(duì)目標(biāo)用戶產(chǎn)生一組推薦列表。實(shí)驗(yàn)結(jié)果表明，在不降低準(zhǔn)確率的同時(shí)，本文算法能有效提高推薦結(jié)果的多樣性。

本文實(shí)現(xiàn)的是推薦結(jié)果準(zhǔn)確率和多樣性兩個(gè)性能之間的權(quán)衡，在實(shí)際的推薦過程中往往要考慮到3個(gè)甚至更多的性能需求。在未來(lái)，我們的研究將擴(kuò)展到解決推薦問題的更多目標(biāo)上。