融合情境信息的非支配排序多目標(biāo)進(jìn)化推薦算法

朱 鑫，金友振，夏小云

(1.浙江師范大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，浙江金華 321004；2.嘉興學(xué)院 信息科學(xué)與工程學(xué)院，浙江嘉興 314001)

隨著移動(dòng)設(shè)備的普及，推薦系統(tǒng)可以很容易通過手機(jī)、手環(huán)、平板等感知設(shè)備獲取情境信息.情境信息又稱為上下文信息，是指在用戶產(chǎn)生行為數(shù)據(jù)過程中與情境相關(guān)的信息，如時(shí)間、地點(diǎn)和心情等，具有實(shí)時(shí)性和時(shí)間多樣性的優(yōu)點(diǎn).[1]因此，在推薦算法中融入情境信息，有助于提高算法的性能.情境信息在推薦算法中發(fā)揮著越來越重要的作用.旅游軟件可以利用地理位置信息為用戶推薦旅游景點(diǎn)和住宿信息，[2]餐飲軟件可以利用時(shí)間信息為用戶推薦菜品，[3]音樂軟件則是通過心情標(biāo)簽為用戶推薦歌曲.[4]本研究將融合情境信息降低系統(tǒng)對(duì)歷史行為數(shù)據(jù)的依賴，提升推薦精確度，并結(jié)合多目標(biāo)進(jìn)化算法對(duì)推薦列表進(jìn)行優(yōu)化.

1 相關(guān)研究

1.1 聚類技術(shù)

聚類方法屬于分類思想或者分簇思想，指把要分類的用戶按照用戶間的相似性進(jìn)行劃分.劃分后，同一類內(nèi)兩兩用戶的相似度最大，不同類間的用戶相似性最低.聚類方法包含劃分式聚類和計(jì)算密度聚類以及劃歸層次聚類.[5]本文采用的K-means++聚類方法是K-means算法的改進(jìn)，優(yōu)化了選擇初始質(zhì)心的方法，屬于劃分式聚類方法.[6]該方法初始化簇中心時(shí)，逐個(gè)選取各簇中心，且距離其他簇中心越遠(yuǎn)的樣本越有可能被選為下個(gè)簇中心.

1.2 協(xié)同過濾推薦算法

協(xié)同過濾推薦是在基于內(nèi)容過濾推薦技術(shù)之后發(fā)展起來的，已逐漸成為業(yè)界推薦系統(tǒng)中主流的種類，其應(yīng)用范圍廣泛、影響效果深遠(yuǎn).按照“物以類聚，人以群分”的思想，協(xié)同過濾推薦主要分為兩大類：基于物品的協(xié)同過濾推薦和基于用戶的協(xié)同過濾推薦(User Collaborative Filterting，User CF).[7-8]前者考慮的是在推薦過程中，推薦的內(nèi)容或者項(xiàng)目之間存在著一定的相似性，根據(jù)物品相似性來判斷用戶喜好進(jìn)行推薦；后者則是通過計(jì)算用戶之間的相似性來推薦，兩個(gè)用戶之間相似性越大，則他們喜好的內(nèi)容也越相似，根據(jù)用戶對(duì)物品的已評(píng)分項(xiàng)來為其相似用戶推薦評(píng)分較高的物品項(xiàng).[8]

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

多目標(biāo)優(yōu)化即在問題求解過程中，需要同時(shí)優(yōu)化多個(gè)目標(biāo)函數(shù).通常情況下，求得一個(gè)目標(biāo)函數(shù)的最優(yōu)解時(shí)往往是以損失其他目標(biāo)函數(shù)為代價(jià)的，但多目標(biāo)優(yōu)化模型可以很好地解決這類問題.[9]多目標(biāo)優(yōu)化問題的數(shù)學(xué)描述如下：

(1)

其中，x∈D表示解向量空間，x=(x1，x2，…，xi)，xi表示第i個(gè)解向量；F(x)為目標(biāo)函數(shù)集；gi(x)和hj(x)為等式或者不等式約束條件集合，p和q分別表示等式與不等式個(gè)數(shù).[10]

2 融合情境信息的聚類推薦

2.1 劃分簇類

利用K-means++算法對(duì)數(shù)據(jù)集進(jìn)行一次聚類，使得算法的收斂情況不再嚴(yán)重依賴于簇中心的初始化狀況，相較于K-means算法求得K個(gè)聚類中心再做聚類，K-means++算法的可解釋性更強(qiáng).[11]算法過程如下：

(i)從數(shù)據(jù)集X中無序地挑選某個(gè)數(shù)據(jù)點(diǎn)即某個(gè)用戶對(duì)所有物品評(píng)分來作為第一個(gè)劃分簇類的簇心點(diǎn)ci；

(ii)求出其余數(shù)據(jù)點(diǎn)與上一步選擇的簇心點(diǎn)之間的路徑長(zhǎng)度，用D(x)表示，并求出簇中心之外剩余數(shù)據(jù)點(diǎn)被挑選為下一個(gè)簇中心的概率P(x)，依概率賭盤選擇最大概率值所對(duì)應(yīng)的樣本點(diǎn)作為下一個(gè)簇中心：

(2)

(iii)重復(fù)第(ii)步，直到選擇出k個(gè)聚類中心.

基于選取的k個(gè)聚類中心，將數(shù)據(jù)集進(jìn)行聚類，使聚類后類內(nèi)數(shù)據(jù)相似性最大，而類間數(shù)據(jù)差異性最大.算法步驟如下：

(I)挑選出的簇心點(diǎn)當(dāng)作每一簇的簇心；

(II)求出所有數(shù)據(jù)點(diǎn)與挑選出的簇中心之間的差異性，再把這些數(shù)據(jù)點(diǎn)劃分到與之差異性最小即相似性最大的簇中心所對(duì)應(yīng)的簇中；

(III)通過上一步的劃分再次求出相應(yīng)的中心點(diǎn)；

(IV)將上述第(II)步和第(III)步重復(fù)運(yùn)行，直至滿足設(shè)置的退出條件.

2.2 改進(jìn)的余弦相似度計(jì)算

相似度的計(jì)算影響了聚類效果的好壞.基于改進(jìn)多目標(biāo)進(jìn)化推薦算法[12]中采用余弦相似性度量算法計(jì)算用戶之間的相似度，尚未將客戶的不同喜好程度融入到計(jì)算中.通俗來說，余弦相似度沒有將用戶的打分尺度考慮進(jìn)去，如有的用戶打分范圍在1～5之間，而有的用戶在2～4之間(即不太愿意給最高分和最低分).例如，有兩個(gè)用戶對(duì)兩個(gè)item打分，item的向量分別為(10，2)、(10，3).但用戶1習(xí)慣打高分，他認(rèn)為最差的item也能得到6分，而用戶2較嚴(yán)格，4分在他看來已經(jīng)足夠高.因此，通過用戶對(duì)項(xiàng)目的評(píng)分減去各個(gè)用戶的評(píng)分均值來消除不同用戶評(píng)分標(biāo)準(zhǔn)不同的問題，公式如下：

(3)

由式(1)可以看出，減去用戶的評(píng)分項(xiàng)平均值解決了余弦相似度僅考慮向量維度方向上相似的問題，在相似度計(jì)算中考慮到了用戶對(duì)評(píng)分項(xiàng)存在評(píng)分程度偏好的問題.

2.3 融入時(shí)間衰減系數(shù)的預(yù)測(cè)評(píng)分

用戶的興趣會(huì)隨著時(shí)間的增加而降低，即推薦過程中存在時(shí)效性較強(qiáng)的因素時(shí)，忽略時(shí)間會(huì)降低推薦的準(zhǔn)確度從而導(dǎo)致推薦效果差.例如：在影視推薦環(huán)境下，用戶對(duì)最新好評(píng)電影以及往年好評(píng)電影的選擇會(huì)更傾向于前者.在實(shí)際中，用戶的興趣偏好是處于動(dòng)態(tài)變化的.相對(duì)于早期的用戶行為，近期的用戶行為對(duì)于推薦更有時(shí)效性，能提升推薦性能.本文將時(shí)間情境信息融入對(duì)影視項(xiàng)的預(yù)測(cè)評(píng)分中來追蹤用戶興趣偏移.用戶u對(duì)項(xiàng)目i的預(yù)測(cè)評(píng)分公式如下：

(4)

其中，wuv表示簇內(nèi)用戶u和v之間的相似度，S(u，M)表示與評(píng)分用戶愛好最為相似的一組用戶集合，集合包含M個(gè)其他的用戶.若用戶v對(duì)某類型影視項(xiàng)有過觀看行為，令rvi=1；否則，令rvi=0.

融入時(shí)間衰減函數(shù)后，計(jì)算用戶對(duì)影視項(xiàng)的相似度時(shí)則需要進(jìn)行改進(jìn)，加入時(shí)間情境信息后的函數(shù)如下：

(5)

其中，t0表示當(dāng)前時(shí)間，tvi表示評(píng)分用戶v對(duì)評(píng)分項(xiàng)i的歷史行為時(shí)間.

3 非支配進(jìn)化的情境推薦

本節(jié)將介紹通過非支配排序的多目標(biāo)進(jìn)化算法對(duì)推薦項(xiàng)求均衡解，旨在平衡推薦列表的精確度和多樣性.

3.1 推薦列表優(yōu)化評(píng)測(cè)指標(biāo)

圖1 基于非支配排序的多目標(biāo)進(jìn)化算法流程

針對(duì)推薦列表的優(yōu)劣問題，有兩個(gè)沖突的評(píng)價(jià)指標(biāo)需要通過多目標(biāo)進(jìn)化算法進(jìn)行平衡.第一個(gè)平衡指標(biāo)是推薦列表的精確度.關(guān)于精確度計(jì)算是無法通過具體的參數(shù)計(jì)算用戶真實(shí)偏好的，因此，采用項(xiàng)目的預(yù)測(cè)評(píng)分進(jìn)行衡量.[15]用戶α對(duì)項(xiàng)目c的預(yù)測(cè)評(píng)分用Prαc表示，用戶簇群大小用M表示，公式定義如下：

(6)

其中|M|表示簇群M中的用戶數(shù)量，C表示推薦列表的長(zhǎng)度.

第二個(gè)指標(biāo)是評(píng)價(jià)推薦列表的多樣性.多樣性指標(biāo)可分為用戶間多樣性、用戶內(nèi)多樣性和覆蓋率.[16]為了降低計(jì)算復(fù)雜度，本文選用覆蓋率進(jìn)行評(píng)價(jià)，覆蓋率越大表示推薦列表的多樣性越好.具體公式如下：

(7)

其中，Ldif表示相同簇群中對(duì)于推薦用戶推薦列表的不同推薦項(xiàng)，L表示推薦用戶的所有推薦項(xiàng)目.

基于非支配排序多目標(biāo)進(jìn)化優(yōu)化利用了進(jìn)化思想，并對(duì)多個(gè)目標(biāo)函數(shù)同時(shí)求取最優(yōu)解.[17]本文中，將使用多目標(biāo)優(yōu)化來最大化以上兩個(gè)評(píng)測(cè)指標(biāo).最終的目標(biāo)函數(shù)如下：

(8)

3.2 基于非支配排序的多目標(biāo)進(jìn)化

結(jié)合具體多目標(biāo)進(jìn)化算法中的編碼策略、交叉策略和遺傳策略以及變異算子對(duì)相同簇群中的推薦列表求得均衡解，具體算法流程如圖1所示.

在算法輸入端，將觀影用戶對(duì)影視項(xiàng)的分?jǐn)?shù)進(jìn)行實(shí)數(shù)向量編碼，每個(gè)觀影用戶關(guān)于全部影視項(xiàng)的評(píng)分則表示為種群中的個(gè)體.將所有用戶進(jìn)行矩陣排列.假設(shè)簇群大小即用戶數(shù)量為n，評(píng)分項(xiàng)目數(shù)量為m，則矩陣的規(guī)模為n×m，如表1所示.

表1 用戶評(píng)分表

圖2 均勻交叉

其中，scoren，m記為用戶n對(duì)項(xiàng)目m的評(píng)分.種群中個(gè)體的等位基因不會(huì)重復(fù)，因此，將編碼后的染色體進(jìn)行均勻交叉操作.交叉算子的過程表述如下：挑選兩條父代染色體，對(duì)同一項(xiàng)目具有相同評(píng)分項(xiàng)的等位基因識(shí)別并遺傳給子代；剩余的等位基因通過[0，1]隨機(jī)數(shù)進(jìn)行選擇；若產(chǎn)生的隨機(jī)數(shù)大于0.5，則從第一條父代染色體處獲得相同的等位基因；否則，從第二條父代染色體處獲得等位基因.交叉操作如圖2所示.

關(guān)于變異算子的選擇，本文與其他多目標(biāo)優(yōu)化算法一樣，使用同樣的標(biāo)準(zhǔn)單點(diǎn)變異.單點(diǎn)變異是通過隨機(jī)選擇一個(gè)基因并生成一個(gè)隨機(jī)數(shù)：若隨機(jī)數(shù)大于0.5，則從推薦項(xiàng)目中隨機(jī)挑選一個(gè)未被評(píng)分的項(xiàng)目；否則，基因保持不變，從而保證了變異基因與推薦列表中基因的差異性.

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

采用開源的Movielens-1M影視數(shù)據(jù)集進(jìn)行驗(yàn)證，該數(shù)據(jù)集采集自20世紀(jì)90年代末到21世紀(jì)初，是由用戶提供的電影評(píng)分?jǐn)?shù)據(jù).數(shù)據(jù)集含有6000名用戶對(duì)4000部電影的100萬條評(píng)分?jǐn)?shù)據(jù)，分為用戶電影評(píng)分表、用戶信息表和電影信息表.

圖3 MAE實(shí)驗(yàn)圖

為了評(píng)估本文提出的KNSGAII-UserCF算法的性能和有效性，考慮從兩個(gè)方面驗(yàn)證推薦結(jié)果的有效性.

第一個(gè)是評(píng)分預(yù)測(cè)，預(yù)測(cè)指標(biāo)通常采用平均絕對(duì)誤差MAE預(yù)測(cè)用戶看到未評(píng)分的項(xiàng)目時(shí)對(duì)項(xiàng)目進(jìn)行多少評(píng)分.平均絕對(duì)誤差定義如下：

(9)

由圖3的實(shí)驗(yàn)結(jié)果可知，將鄰居用戶劃分范圍，當(dāng)鄰居用戶數(shù)目變大時(shí)，提出的模

圖4 精確度指標(biāo)評(píng)價(jià)

圖5 多樣性指標(biāo)評(píng)價(jià)

圖6 新穎度指標(biāo)評(píng)價(jià)

型平均絕對(duì)誤差慢慢地趨于穩(wěn)定值.若近鄰用戶數(shù)量為5時(shí)，絕對(duì)誤差最大.而本文提出的算法在近鄰用戶大于25時(shí)，相較于對(duì)比算法的性能略好.

第二個(gè)評(píng)測(cè)指標(biāo)是Top-N推薦.[20]預(yù)測(cè)評(píng)分項(xiàng)目的精確度、多樣性以及新穎度，實(shí)驗(yàn)數(shù)據(jù)仍采用同一個(gè)數(shù)據(jù)集.新穎度是指推薦列表中推薦項(xiàng)的流行度，如果推薦列表中的項(xiàng)目越受歡迎，則表示推薦列表的新穎度越高.新穎度定義公式如下：[21]

(10)

其中，U表示推薦系統(tǒng)中所有用戶的數(shù)量，L表示推薦列表的長(zhǎng)度，Ni表示對(duì)項(xiàng)目i的已評(píng)分?jǐn)?shù)量.從精確度、多樣性、新穎度等方面與其他算法比較，如基于二部圖網(wǎng)絡(luò)的推薦、[15]基于內(nèi)容和用戶的協(xié)同過濾推薦[14]和基于進(jìn)化算法的推薦[21].關(guān)于評(píng)價(jià)指標(biāo)精確度、多樣性和新穎度的實(shí)驗(yàn)結(jié)果如圖4、圖5、圖6所示.

從圖4中可以看出，本文算法在評(píng)價(jià)推薦列表的精確度方面略低于基于二部圖網(wǎng)絡(luò)的推薦、基于協(xié)同過濾的推薦和基于改進(jìn)的多目標(biāo)進(jìn)化推薦.圖5中則展示了在評(píng)價(jià)推薦列表多樣時(shí)，多樣性的指標(biāo)與對(duì)比算法基本持平.新穎度作為推薦列表的評(píng)價(jià)指標(biāo)也變得越來越重要，一個(gè)新穎度高的推薦列表會(huì)給用戶帶來驚喜，從圖6可以看出，本文算法比對(duì)比算法在新穎度方面略好.總的來說，本文通過非支配排序的多目標(biāo)進(jìn)化算法在平衡推薦列表精確度、多樣性、新穎度時(shí)，犧牲了一定程度的精確度來實(shí)現(xiàn)推薦列表更高的多樣性和新穎度.

表2是對(duì)比算法與本文算法在三個(gè)評(píng)價(jià)指標(biāo)方面的具體數(shù)值.

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

由表2可知，本文提出的方法在精確度方面略微低于對(duì)比算法，在多樣性方面效果與基于用戶的協(xié)同過濾推薦相同，而新穎度僅低于基于用戶的協(xié)同過濾，相較于基于項(xiàng)目的推薦和二分網(wǎng)絡(luò)的推薦新穎度數(shù)值都高出15%左右，故本文所提算法給出的推薦列表新穎度高.

5 結(jié)語

本文提出了一種基于非支配排序多目標(biāo)進(jìn)化的情境推薦算法，通過構(gòu)建k-means++融合情境時(shí)間推薦模型，減少計(jì)算時(shí)間復(fù)雜度和提高簇類用戶間相似性，最大化用戶對(duì)推薦列表的滿意度，并將推薦列表通過進(jìn)化算法特性同時(shí)優(yōu)化精確度和多樣性目標(biāo).實(shí)驗(yàn)結(jié)果表明，融合了情境信息的多目標(biāo)進(jìn)化推薦，在做評(píng)分預(yù)測(cè)時(shí)能夠降低預(yù)測(cè)的誤差，給出TopN推薦時(shí)，一定程度上提高了推薦項(xiàng)的精確度、多樣性和新穎度.由于本文提供的數(shù)據(jù)集稀疏程度較高，未做處理的數(shù)據(jù)會(huì)使實(shí)驗(yàn)存在不穩(wěn)定性，表明提出的算法魯棒性、穩(wěn)定性還有待提高.應(yīng)進(jìn)一步處理數(shù)據(jù)稀疏問題，以提升算法的效果，提高推薦效率.