融合情境信息的非支配排序多目標進化推薦算法

朱 鑫，金友振，夏小云

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

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

1 相關研究

1.1 聚類技術

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

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

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

1.3 多目標優(yōu)化

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

(1)

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

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

2.1 劃分簇類

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

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

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

(2)

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

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

(I)挑選出的簇心點當作每一簇的簇心；

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

(III)通過上一步的劃分再次求出相應的中心點；

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

2.2 改進的余弦相似度計算

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

(3)

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

2.3 融入時間衰減系數(shù)的預測評分

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

(4)

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

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

(5)

其中，t0表示當前時間，tvi表示評分用戶v對評分項i的歷史行為時間.

3 非支配進化的情境推薦

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

3.1 推薦列表優(yōu)化評測指標

圖1 基于非支配排序的多目標進化算法流程

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

(6)

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

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

(7)

其中，Ldif表示相同簇群中對于推薦用戶推薦列表的不同推薦項，L表示推薦用戶的所有推薦項目.

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

(8)

3.2 基于非支配排序的多目標進化

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

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

表1 用戶評分表

圖2 均勻交叉

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

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

4 實驗與分析

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

圖3 MAE實驗圖

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

第一個是評分預測，預測指標通常采用平均絕對誤差MAE預測用戶看到未評分的項目時對項目進行多少評分.平均絕對誤差定義如下：

(9)

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

圖4 精確度指標評價

圖5 多樣性指標評價

圖6 新穎度指標評價

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

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

(10)

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

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

表2是對比算法與本文算法在三個評價指標方面的具體數(shù)值.

表2 評價指標

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

5 結(jié)語

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