陳 宏,王麗萍,翁杭立,?？∫?郭海東

1(浙江工業(yè)大學(xué) 教育科學(xué)與技術(shù)學(xué)院,杭州 310014) 2(浙江工業(yè)大學(xué) 管理學(xué)院,杭州 310014) 3(浙江工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,杭州 310014)

0 引 言

推薦系統(tǒng)是利用統(tǒng)計(jì)學(xué)和知識(shí)發(fā)現(xiàn)等技術(shù)手段,通過(guò)挖掘和追蹤用戶(hù)行為和心理偏好,搜尋并定位滿(mǎn)足需求的資源、產(chǎn)品和信息,減少用戶(hù)在海量信息中的決策負(fù)荷,是應(yīng)對(duì)信息過(guò)載的重要技術(shù)手段和工具[1].在電子商務(wù)、影視娛樂(lè)、在線學(xué)習(xí)以及醫(yī)療健康等領(lǐng)域已有廣泛的研究和應(yīng)用[2].推薦算法是推薦系統(tǒng)的核心,通過(guò)整合歷史數(shù)據(jù)、挖掘用戶(hù)喜好以提高推薦的有效性.準(zhǔn)確性和多樣性是推薦算法研究的二個(gè)重要指標(biāo)[3],通過(guò)提高對(duì)用戶(hù)行為預(yù)測(cè)的準(zhǔn)確率[4]、優(yōu)化排序技術(shù)[5]、構(gòu)建推薦模型[6],最大程度地使推薦結(jié)果滿(mǎn)足用戶(hù)的需求.然而,基于準(zhǔn)確性的推薦算法將導(dǎo)致推薦結(jié)果過(guò)于集中在某類(lèi)特征上,使得多樣性降低,導(dǎo)致用戶(hù)選擇的廣度不足而整體效果不佳[7].因此,如何將推薦算法的準(zhǔn)確性和多樣性平衡以達(dá)到滿(mǎn)足用戶(hù)最大需求是推薦算法研究的重要關(guān)注點(diǎn).為此,研究者提出在推薦算法不同階段對(duì)不同目標(biāo)進(jìn)行優(yōu)化[8],也有研究通過(guò)建模來(lái)獲得兩者平衡[9],然而這些研究均需較豐富的先驗(yàn)知識(shí),故增加了推薦算法設(shè)計(jì)難度.有學(xué)者提出利用多目標(biāo)優(yōu)化思想來(lái)解決此類(lèi)問(wèn)題[10].其思想是在分析預(yù)測(cè)用戶(hù)興趣度基礎(chǔ)上,將準(zhǔn)確性和多樣性作為推薦的二維目標(biāo),利用多目標(biāo)優(yōu)化算法進(jìn)行推薦策略的搜索,最后得到最優(yōu)推薦方案.然而,正如文獻(xiàn)[10]所述,多目標(biāo)優(yōu)化得到的結(jié)果是目標(biāo)間各種平衡情況的帕累托解集,解集數(shù)量多且不可控是制約多目標(biāo)推薦算法實(shí)際應(yīng)用的因素之一,如何選擇最終滿(mǎn)足需求的推薦方案是研究者無(wú)法規(guī)避的問(wèn)題.

為了解決多目標(biāo)推薦算法優(yōu)化后有效方案選取問(wèn)題,Wang等人[11]選擇帕累托解集的極值點(diǎn)作為推薦方案,Chai等人[12]在得到帕累托解集后利用多屬性決策法對(duì)解集進(jìn)行二次排序選擇獲得最佳平衡解作為推薦方案.但此種方式實(shí)質(zhì)上是優(yōu)化過(guò)程和決策過(guò)程的分離,導(dǎo)致優(yōu)化過(guò)程在決策者不感興趣的區(qū)域浪費(fèi)算法資源,且決策者在做決策時(shí)相對(duì)復(fù)雜.在多目標(biāo)優(yōu)化領(lǐng)域,偏好多目標(biāo)優(yōu)化是實(shí)現(xiàn)決策和優(yōu)化相融合的技術(shù)[13],其通過(guò)事先給定偏好或優(yōu)化過(guò)程中動(dòng)態(tài)設(shè)置偏好的方式,將解集朝偏好區(qū)域收斂,最終獲得具有偏好特征的帕累托前沿.然而,多數(shù)偏好多目標(biāo)優(yōu)化算法要求決策者事先給出偏好信息.很多情況下,如本文的推薦準(zhǔn)確性和多樣性最大化問(wèn)題,決策者因缺乏足夠的先驗(yàn)知識(shí),無(wú)法給出明確的偏好信息,給偏好多目標(biāo)優(yōu)化算法在推薦領(lǐng)域的應(yīng)用帶來(lái)難題.

針對(duì)以上問(wèn)題,本文利用最大預(yù)測(cè)評(píng)分模型和最大相似度差異模型構(gòu)建二維目標(biāo)模型,設(shè)計(jì)了獲取隱式偏好的方法,提出一種基于隱式偏好的多目標(biāo)推薦算法,對(duì)推薦的準(zhǔn)確性和多樣性兼顧優(yōu)化.本算法首先通過(guò)基于領(lǐng)域算法預(yù)測(cè)興趣度以及興趣度排序產(chǎn)生推薦候選集;利用切比雪夫最小距離標(biāo)定隱式偏好點(diǎn),并在迭代過(guò)程中動(dòng)態(tài)更新偏好點(diǎn)和偏好區(qū)域;采用基于HP-NSGA-II[14]的3層排序準(zhǔn)則為進(jìn)化策略,將解集收斂于偏好區(qū)域;最后以最小切比雪夫距離為決策準(zhǔn)則,將非支配解進(jìn)行推薦偏好的劃分,生成具有不同目標(biāo)偏好的推薦方案集.實(shí)驗(yàn)表明,此算法能在確保準(zhǔn)確率的同時(shí)能提高推薦的多樣性和新穎度,且能有效降多目標(biāo)推薦算法的推薦方案的數(shù)量,提高算法的實(shí)際應(yīng)用能力.

1 相關(guān)工作

1.1 多目標(biāo)推薦

多目標(biāo)優(yōu)化問(wèn)題是多個(gè)目標(biāo)效用最大化的問(wèn)題,用數(shù)學(xué)公式(1)表示:

maxF(x)=(f1(x),f2(x),…,fn(x))

(1)

其中F(x)是具有互斥性的目標(biāo)集.x=[x1,x2,…,xd]∈Ω為策略集向量,Ω為策略向量空間.當(dāng)給定兩個(gè)向量xA和xB,存在fi(xA)≥fi(xB),i=1,2,…,n,且F(xA)≠F(xB),稱(chēng)之為xA支配xB(xA?xB),即xA更為優(yōu)秀.當(dāng)存在x∈Ω不被任何其他策略支配時(shí),x稱(chēng)為帕累托最優(yōu)解.所有帕累托最優(yōu)解組成的集合稱(chēng)為帕累托集PS.

PS={x∈Ω|┐?x′∈Ω,x′?x}

(2)

帕累托集映射到目標(biāo)空間形成的區(qū)域稱(chēng)為帕累托前沿(PF).

PF={F(x)|x∈PS}

(3)

如何有獲取帕累托最優(yōu)解是多目標(biāo)優(yōu)化算法的核心問(wèn)題,也是多目標(biāo)推薦最終能否提供有效推薦的關(guān)鍵.目前,多目標(biāo)優(yōu)化問(wèn)題的求解有眾多算法,如多目標(biāo)進(jìn)化算法、粒子群算法、免疫優(yōu)化算法、蟻群算法等.其中,多目標(biāo)進(jìn)化算法(multi-objective evolutionary algorithms,MOEA)應(yīng)用較為廣泛,其模擬生物自然選擇與進(jìn)化規(guī)律執(zhí)行隨機(jī)搜索,能適用于解決高復(fù)雜度的非線性問(wèn)題,且具有較好的通用性.根據(jù)進(jìn)化機(jī)制不同,一般可以分為:基于支配關(guān)系,如NSGA-II、SPEA2等算法;基于指標(biāo),如IBEA、HypE等算法;基于分解,如MOEA/D、NSGA-III等算法[15].當(dāng)引入決策者偏好信息時(shí),則稱(chēng)為偏好MOEA.根據(jù)偏好信息不同可分為:基于占優(yōu)關(guān)系,如g-NSGA-II;基于角度關(guān)系,如AD-NSGA-II;基于權(quán)重向量,如R-MEAD;以及基于偏好集,如iPICEA-g.

傳統(tǒng)推薦算法多聚焦解決單個(gè)目標(biāo)問(wèn)題,如用戶(hù)興趣度預(yù)測(cè)誤差的最小化[16],推薦結(jié)果評(píng)分最大化[17]等.近年來(lái),有學(xué)者將多目標(biāo)優(yōu)化技術(shù)與推薦系統(tǒng)結(jié)合,獲取滿(mǎn)足多個(gè)推薦目標(biāo)的最優(yōu)結(jié)果,此類(lèi)推薦技術(shù)稱(chēng)之為多目標(biāo)推薦(multi-objective recommender systems,MORS).由此衍生出諸多研究.如平衡推薦的性能指標(biāo)[18];緩解群組中個(gè)體和群體公平性矛盾[19];兼顧多利益相關(guān)者推薦[20]等.

推薦性能指標(biāo)的平衡是MORS典型的研究領(lǐng)域.在推薦系統(tǒng)中,除了推薦的準(zhǔn)確性外,新穎度、多樣性、偶然性和流行度等指標(biāo)也是衡量推薦系統(tǒng)質(zhì)量和性能的指標(biāo).然而,指標(biāo)間有可能存在互斥的情況,最大化其中一個(gè)指標(biāo)有會(huì)導(dǎo)致其他指標(biāo)性能的下降.因此,需要通過(guò)多目標(biāo)優(yōu)化技術(shù)來(lái)平衡相關(guān)指標(biāo)產(chǎn)生推薦.根據(jù)MORS工作機(jī)制,相關(guān)研究可分為基于多目標(biāo)優(yōu)化的用戶(hù)行為預(yù)測(cè)和推薦列表生成兩大類(lèi).在預(yù)測(cè)評(píng)分方面,Cai等人[21]構(gòu)建了一種混合模型,通過(guò)對(duì)多個(gè)推薦算法的預(yù)測(cè)值進(jìn)行加權(quán),利用MOEA學(xué)習(xí)權(quán)重值,加權(quán)后的結(jié)果為最終用戶(hù)興趣度預(yù)測(cè)值;Cao等人[22]在張量分解推薦算法中,利用MOEA進(jìn)行張量學(xué)習(xí),兼顧多個(gè)推薦性能;Xie[23]等人利用聯(lián)合學(xué)習(xí)模型,為用戶(hù)找到合適的多個(gè)目標(biāo)間權(quán)重,在損失函數(shù)中對(duì)多個(gè)目標(biāo)梯度加權(quán),以預(yù)測(cè)用戶(hù)興趣度.在推薦列表生成方面,通過(guò)MOEA中種群的基因編碼方式,可以對(duì)用戶(hù)的推薦列表進(jìn)行優(yōu)化.Zuo等人[24]在對(duì)用戶(hù)評(píng)分預(yù)測(cè)后,利用實(shí)數(shù)編碼結(jié)合MOEA生成滿(mǎn)足準(zhǔn)確性和多樣性目標(biāo)的推薦列表;Wang等人[11]利用協(xié)同過(guò)濾技術(shù)篩選推薦候選集后,利用MOEA生成滿(mǎn)足準(zhǔn)確性和新型性目標(biāo)的推薦列表;在此基礎(chǔ)上,Cai等人[12]融合多屬性決策,對(duì)MOEA產(chǎn)生的帕累托推薦列表集進(jìn)行排序后推薦,降低了推薦方案的規(guī)模.

盡管多目標(biāo)優(yōu)化解決了傳統(tǒng)推薦算法兼顧多個(gè)目標(biāo)的難題,但其輸出是數(shù)量眾多的帕累托最優(yōu)解,需依靠決策者篩選和確定最終推薦方案,而決策者偏好依賴(lài)先驗(yàn)知識(shí),通常無(wú)法明確給定,這為多目標(biāo)推薦算法效率和實(shí)際應(yīng)用帶來(lái)負(fù)擔(dān).基于此,本文算法聚焦推薦性能指標(biāo),其多目標(biāo)推薦步驟如下:

1)預(yù)測(cè)用戶(hù)興趣度,構(gòu)建擬推薦候選集;

2)根據(jù)推薦系統(tǒng)需求,建立目標(biāo)問(wèn)題模型;

3)利用多目標(biāo)優(yōu)化算法在候選集中搜尋最優(yōu)策略;

4)在帕累托解集中選擇最終推薦方案;

1.2 隱式偏好

多目標(biāo)優(yōu)化中膝點(diǎn)是天然的偏好點(diǎn)[25].而極值點(diǎn)則在某一目標(biāo)上擁有最佳性能,且能有效獲取前沿范圍,幫助構(gòu)建偏好[26].當(dāng)決策者因缺乏足夠先驗(yàn)知識(shí)而無(wú)法給出明確偏好信息時(shí),可將PF的膝區(qū)域(Knee Region)和極區(qū)域(Extreme Region)作為隱式偏好區(qū).膝區(qū)域的解在所有優(yōu)化目標(biāo)上具有最佳平衡性,而極區(qū)域則是某一目標(biāo)上最大性能.對(duì)于推薦系統(tǒng)而言,當(dāng)偏好信息未知時(shí),在隱式偏好區(qū)域選擇推薦方案可降低多目標(biāo)推薦系統(tǒng)的決策難度.

當(dāng)優(yōu)化目標(biāo)為最大化問(wèn)題時(shí),隱式偏好區(qū)域選擇方法如公式(4).本文采用圓形區(qū)域,S為偏好參考點(diǎn),r為區(qū)域半徑.

R=[S,r]

(4)

膝區(qū)域和極區(qū)域偏好點(diǎn)定義如公式(5)～公式(7)所示:

(5)

(6)

(7)

極值點(diǎn)Sextr為任一目標(biāo)值最大點(diǎn).膝點(diǎn)定義為與隱式理想?yún)⒖键c(diǎn)z*切比雪夫距離最小點(diǎn).隱式理想?yún)⒖键c(diǎn)z*為擁有所有目標(biāo)最高值的點(diǎn),其幾何意義圖1所示.

圖1 隱式偏好下的極值點(diǎn),膝蓋點(diǎn)和理想點(diǎn)Fig.1 Extreme point,knee point and ideal point based on implicit preference

1.3 切比雪夫距離

切比雪夫距離(Chebyshev distance)是一種評(píng)價(jià)候選決策向量與偏好目標(biāo)參考向量之間距離的效用函數(shù)[27].當(dāng)給定目標(biāo)空間中的偏好參考向量z,決策向量與其切比雪夫距離如公式(8)表示:

(8)

在一組策略集中,距離目標(biāo)參考向量的切比雪夫距離最小的解可以定義為在該目標(biāo)參考向量偏好下具有最佳平衡性能.

(9)

本文利用切比雪夫距離來(lái)獲取膝點(diǎn)進(jìn)而標(biāo)定膝區(qū)域.

2 算法設(shè)計(jì)

2.1 算法流程

本文基于隱式偏好的多目標(biāo)推薦算法(Implicit preference multi-objective algorithm for recommender systems,IP-MRS)總體流程框架包含推薦候選集生成、基于隱式偏好的多目標(biāo)優(yōu)化、推薦策略選擇3個(gè)階段.具體算法流程見(jiàn)圖2所示.

圖2 算法框架和流程Fig.2 Framework and process of the method

2.2 候選集生成策略

候選集是擬推薦給用戶(hù)的集合.本算法候選集生成策略包含兩個(gè)步驟:

1)對(duì)用戶(hù)未發(fā)生行為項(xiàng)目的興趣度預(yù)測(cè);

2)對(duì)項(xiàng)目根據(jù)興趣度大小排序.

對(duì)用戶(hù)興趣度預(yù)測(cè)采用基于領(lǐng)域算法(KNN),根據(jù)用戶(hù)行為計(jì)算項(xiàng)目間的相似度進(jìn)而推測(cè)用戶(hù)對(duì)未發(fā)生行的項(xiàng)目的興趣度.本文采用余弦相似度計(jì)算方法[28].

(10)

Pu,i=∑j∈nS(i,j)ru,j

(11)

其中i和j為兩個(gè)不同項(xiàng)目,u為用戶(hù),r為用戶(hù)評(píng)分矩陣,Pu,i為預(yù)測(cè)用戶(hù)u對(duì)項(xiàng)目i的興趣度.進(jìn)而篩選出興趣度最高的K個(gè)項(xiàng)目(top-K)作為給目標(biāo)用戶(hù)推薦的候選集,并對(duì)候選列表的興趣度進(jìn)行歸一化處理.

2.3 基于隱式偏好的多目標(biāo)優(yōu)化策略

2.3.1 目標(biāo)函數(shù)構(gòu)建

本文將采用基于預(yù)測(cè)評(píng)分最大化模型[24]和內(nèi)部相似度差異最大化模型[18]作為準(zhǔn)確性(accuracy)和多樣性(diversity)目標(biāo)構(gòu)建二維目標(biāo)模型.

(12)

(13)

maxF=(facc,fdiv)

(14)

其中u為目標(biāo)用戶(hù),R為推薦列表,i,j為推薦項(xiàng)目.Pr(u,i)是推薦列表中用戶(hù)u對(duì)項(xiàng)目i的興趣度,sim(i,j)是推薦列表中項(xiàng)目之間的相似度.facc越大表明提供給用戶(hù)的推薦列表越能滿(mǎn)足其喜好,fdiv越大表明提供給用戶(hù)的推薦列表中項(xiàng)目具有更好的多樣性.二維目標(biāo)最大化的含義是推薦方案既要滿(mǎn)足用戶(hù)的喜好又要保證足夠豐富.上述2個(gè)目標(biāo)間一定程度上是互斥的.

2.3.2 多目標(biāo)進(jìn)化策略

本算法多目標(biāo)進(jìn)化策略是基于HP-NSGA-Ⅱ算法思想[14].HP-NSGA-Ⅱ算法改進(jìn)了種群更新機(jī)制,在Pareto非支配排序確定的臨界層上以3層排序準(zhǔn)則引導(dǎo)算法收斂目標(biāo)區(qū)域,并且其在多個(gè)目標(biāo)區(qū)域采用并行計(jì)算的方式提升算法性能.

進(jìn)化策略描述如下:

Step1.公式(5)、公式(6)標(biāo)定偏好點(diǎn)(極值點(diǎn)、膝點(diǎn)),公式(4)確定目標(biāo)區(qū)域,目標(biāo)偏好點(diǎn)數(shù)量為M,種群數(shù)量為N;

Step2.種群進(jìn)化操作,確定臨界層;

Step3.利用3層排序機(jī)制選擇N/M個(gè)體進(jìn)入下一代;

Step3.1如臨界層在目標(biāo)區(qū)域個(gè)體等于N/M,選入;

Step3.2如臨界層在目標(biāo)區(qū)域個(gè)體大于N/M,擁擠度排序后選入;

Step3.3如臨界層在目標(biāo)區(qū)域個(gè)體小于N/M,目標(biāo)區(qū)域外個(gè)體與目標(biāo)偏好點(diǎn)C_dis排序后補(bǔ)足數(shù)量;

Step4.重復(fù)Step 2,直到所有目標(biāo)區(qū)域跟新完畢.

Step5.合并M個(gè)偏好區(qū)域的個(gè)體為子代種群.

2.3.3 遺傳變異策略

在遺傳變異操作上,采用均勻交叉機(jī)制(uniform crossover).考慮到給用戶(hù)推薦的項(xiàng)目不應(yīng)重復(fù)出現(xiàn),當(dāng)滿(mǎn)足遺傳條件時(shí),兩個(gè)父代中相同的項(xiàng)目遺傳給兩個(gè)子代,不同的項(xiàng)目以50%的概率隨機(jī)交叉給兩個(gè)子代.在變異操作上,當(dāng)個(gè)體滿(mǎn)足變異條件時(shí),在候選集中隨機(jī)選擇未在推薦列表中的項(xiàng)目替換對(duì)應(yīng)位置的項(xiàng)目,遺傳變異操作如圖3所示,其中數(shù)字代表推薦項(xiàng)目的編號(hào).具體步驟如下:

圖3 個(gè)體交叉變異操作Fig.3 Crossover and mutation operation

Step1.設(shè)置交叉概率、變異概率.

Step2.符合交叉條件進(jìn)入交叉操作;

Step2.1.采用錦標(biāo)賽機(jī)制選擇2個(gè)父代個(gè)體;

Step2.2.保留父代相同項(xiàng)目給子代,提取不同項(xiàng)目;

Step2.3.不同項(xiàng)目按0.5的概率分配給兩個(gè)子代,交叉過(guò)程結(jié)束;

Step3.個(gè)體中項(xiàng)目位置符合變異條件,進(jìn)入變異;

Step3.1.從候選集中隨機(jī)選擇項(xiàng)目,且該項(xiàng)目不在待變異個(gè)體中.

Step3.2.新項(xiàng)目替換變異個(gè)體對(duì)應(yīng)項(xiàng)目,變異過(guò)程結(jié)束.

2.4 推薦方案選擇策略

多目標(biāo)優(yōu)化過(guò)程結(jié)束得到PF后,進(jìn)一步采用選擇策略將Pareto解集劃分成不同偏好屬性的子集,從而降低推薦系統(tǒng)的決策負(fù)擔(dān).本算法利用隱式偏好,將推薦方案劃分成準(zhǔn)確性占優(yōu)(IP-MRS-a)、多樣性占優(yōu)(IP-MRS-d)和目標(biāo)平衡(IP-MRS-k)3個(gè)方案集.具體劃分步驟如下:

Step3.對(duì)每個(gè)個(gè)體的3個(gè)C_dis排序,最小C_dis對(duì)應(yīng)的區(qū)域即為該個(gè)體所屬集合;

Step4.輸出3個(gè)集合.

2.5 算法復(fù)雜度

算法包含3個(gè)階段,其復(fù)雜度從3方面分析.候選集產(chǎn)生階段,假設(shè)有m個(gè)用戶(hù)n個(gè)項(xiàng)目的評(píng)分矩陣,目標(biāo)用戶(hù)候選集長(zhǎng)度為K,算法時(shí)間復(fù)雜度為O(mn2)+O(clog2K);多目標(biāo)優(yōu)化階段,2個(gè)目標(biāo),3個(gè)隱式偏好,N個(gè)種群,g次迭代,算法時(shí)間復(fù)雜度為O(6N2g);推薦方案選擇階段,假設(shè)有d個(gè)PF個(gè)體,3個(gè)隱式偏好,算法時(shí)間復(fù)雜度為O(3dlog2d).算法總體時(shí)間復(fù)雜度為3個(gè)階段的總和.

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

3.1 實(shí)驗(yàn)準(zhǔn)備

本文算法采用Python語(yǔ)言編程實(shí)現(xiàn).實(shí)驗(yàn)運(yùn)行環(huán)境為macOS Big Sur,處理器CPU:Intel(R)Core(TM)i5 @2.7GHz,內(nèi)存8GB.本文采用Movielens 100K和Netflix兩個(gè)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn).Movielens 100K數(shù)據(jù)集包含了943個(gè)用戶(hù)對(duì)1682個(gè)電影共計(jì)10萬(wàn)條評(píng)分,評(píng)分區(qū)間為[1,5].Netflix數(shù)據(jù)集中隨機(jī)選擇10000名用戶(hù)對(duì)2700個(gè)電影的80萬(wàn)條評(píng)分,評(píng)分區(qū)間為[1,5].兩個(gè)數(shù)據(jù)集均隨機(jī)選擇80%的數(shù)據(jù)作為訓(xùn)練集,剩余20%作為測(cè)試集,并從測(cè)試集中隨機(jī)選擇20位目標(biāo)用戶(hù)進(jìn)行推薦.

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

本文實(shí)驗(yàn)參數(shù)設(shè)置見(jiàn)表1.

表1 實(shí)驗(yàn)參數(shù)設(shè)置Table 1 Parameters of experiment

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

針對(duì)推薦結(jié)果的評(píng)價(jià),本文采用準(zhǔn)確率(Precision)、新穎度(Novelty)以及優(yōu)化目標(biāo)中的多樣性(Diversity)3個(gè)指標(biāo)[2].準(zhǔn)確率表示推薦算法滿(mǎn)足用戶(hù)實(shí)際興趣的程度,是評(píng)價(jià)推薦準(zhǔn)確性常用指標(biāo).而新穎度則是評(píng)價(jià)推薦算法挖掘長(zhǎng)尾的能力.

(15)

(16)

其中,R(u)為用戶(hù)u的推薦列表;T(u)為測(cè)試集中該用戶(hù)有過(guò)行為的項(xiàng)目;k為項(xiàng)目的流行度,即測(cè)試數(shù)據(jù)集中有多少用戶(hù)對(duì)該項(xiàng)目發(fā)生了行為,U為測(cè)試數(shù)據(jù)集中用戶(hù)數(shù)量.上述指標(biāo)數(shù)值越大表明該項(xiàng)性能好.

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

3.4.1 推薦性能有效性

為驗(yàn)證算法性能及有效性,實(shí)驗(yàn)結(jié)果將本算法與Item-based協(xié)同過(guò)濾推薦算法(Item-based Collaborative Filtering,ItemCF)[28]和基于NSGA-II的多目標(biāo)推薦算法MOEA-RS[24]進(jìn)行對(duì)比.ItemCF算法與本文IP-MRS算法采用相同的基于項(xiàng)目相似度預(yù)測(cè)目標(biāo)用戶(hù)興趣度,以興趣度排序給用戶(hù)推薦TOP-10的項(xiàng)目.與其比較的目的是驗(yàn)證本文算法在同時(shí)優(yōu)化兩個(gè)推薦目標(biāo)上的性能.MOEA-RS算法是無(wú)偏好的多目標(biāo)推薦算法,其最終輸出的PF分布在整個(gè)目標(biāo)空間區(qū)域,與其比較驗(yàn)證IP-MRS能否有效降低推薦系統(tǒng)的決策負(fù)擔(dān).本文算法將推薦結(jié)果分為準(zhǔn)確性占優(yōu)(IP-MRS-a)、多樣性占優(yōu)(IP-MRS-d)和目標(biāo)平衡(IP-MRS-k)3個(gè)結(jié)果進(jìn)行呈現(xiàn).

實(shí)驗(yàn)結(jié)果分兩部分對(duì)推薦有效性進(jìn)行呈現(xiàn)和分析.首先兩個(gè)數(shù)據(jù)集各選擇6位目標(biāo)用戶(hù)對(duì)IP-MRS前沿圖和各算法推薦性能詳細(xì)情況進(jìn)行分析,然后對(duì)兩個(gè)數(shù)據(jù)集20位目標(biāo)用戶(hù)總體推薦性能進(jìn)行分析.

圖4和圖5分別展示了Movielens數(shù)據(jù)和Netflix數(shù)據(jù)集中6位目標(biāo)用戶(hù)IP-MRS算法最終推薦方案的PF分布情況.

圖4 Movielens數(shù)據(jù)集中6位目標(biāo)用戶(hù)IP-MS算法帕累托前沿圖Fig.4 Pareto front of six users in movielens dataset by IP-MS algorithm

圖5 Netflix數(shù)據(jù)集中6位目標(biāo)用戶(hù)IP-MS算法帕累托前沿圖Fig.5 Pareto front of six users in Netflix dataset by IP-MS algorithm

實(shí)心圓點(diǎn)為非支配解,虛線框?yàn)椴煌脜^(qū)域.從解集的分布情況可以看出,本算法可以有效地將推薦方案收斂于極值區(qū)域和膝區(qū)域.在決策者偏好未知的情況下,作為隱式偏好的此3區(qū)域可以為最終決策提供幫助.從各目標(biāo)用戶(hù)推薦結(jié)果分布來(lái)看,不同區(qū)域解的分布數(shù)量不均勻,形態(tài)不規(guī)則.這是由于推薦算法是根據(jù)用戶(hù)歷史行為進(jìn)行預(yù)測(cè)和決策,而用戶(hù)歷史行為信息的稀疏性和不規(guī)則性導(dǎo)致候選集中各項(xiàng)目間的相似度和預(yù)測(cè)評(píng)分差異性較大,這是最終解集分布不均勻的原因之一.同時(shí),候選集作為多目標(biāo)優(yōu)化的策略搜索依據(jù),其數(shù)量的限制,導(dǎo)致解的搜索空間有限,這也是造成上述問(wèn)題的原因.偏好區(qū)域范圍r的取值理論上可以影響解圍繞偏好點(diǎn)的聚集性,但據(jù)上述分析,在推薦問(wèn)題的實(shí)際場(chǎng)景中是否能達(dá)到同樣性能并不確定,且本文探討算法能否有效引導(dǎo)解集分布在偏好區(qū)域,故不對(duì)r的取值范圍進(jìn)行分析論證.

為進(jìn)一步驗(yàn)證在隱式偏好區(qū)域內(nèi)的推薦方案的有效性,表2～表7分別展示了不同算法兩個(gè)數(shù)據(jù)集中6位目標(biāo)用戶(hù)上的推薦性能,圖6、圖7展示了不同算法在兩個(gè)數(shù)據(jù)集20位用戶(hù)上的平均性能表現(xiàn).其中MOEA-RS的結(jié)果是所有PF個(gè)體性能的平均值,IP-MRS-a、IP-MRS-d、IP-MRS-k的結(jié)果是對(duì)應(yīng)偏好區(qū)內(nèi)PF個(gè)體性能的平均值.從圖6可見(jiàn),在Movielens數(shù)據(jù)集上,IP-MRS在推薦準(zhǔn)確度上略低于ItemCF算法(平均降低18.3%,最少降低8.4%),而多樣性指標(biāo)得到了較大提升(平均提升38.0%,最高提升47.2%),新穎度指標(biāo)表現(xiàn)也更好(平均提升58.6%,最高提升68.8%).從圖7可見(jiàn),在Netflix數(shù)據(jù)集上的表現(xiàn)與Movielens基本一致,IP-MRS在推薦準(zhǔn)確度上略低于ItemCF算法(平均降低15.1%,最少降低7.1%),多樣性指標(biāo)提升明顯(平均提升33.4%,最高提升49.1%),新穎度指標(biāo)表現(xiàn)更為顯著(平均提升125.4%,最高提升131.1%).這與ItemCF只關(guān)注準(zhǔn)確性這單一目標(biāo),而多目標(biāo)推薦算法同時(shí)兼顧準(zhǔn)確性和多樣性?xún)蓚€(gè)目標(biāo)有關(guān).說(shuō)明本文算法在保證推薦準(zhǔn)確性的同時(shí)提升推薦的多樣性和新穎度.在多目標(biāo)推薦算法中,IP-MRS在準(zhǔn)確率、多樣性和新穎度性能上均高于MOEA-RS.這是因?yàn)镮P-MRS將更多的搜索資源分配給了偏好區(qū)域,而MOEA-RS則在整個(gè)目標(biāo)區(qū)域進(jìn)行搜索,因此在實(shí)驗(yàn)中IP-MRS推薦性能表現(xiàn)更為優(yōu)異.從3個(gè)偏好區(qū)域的推薦性能對(duì)比看出,不同的偏好區(qū)域表現(xiàn)出了其應(yīng)有的特性.如IP-MRS-a推薦準(zhǔn)確率高,IP-MRS-d的多樣性和新穎度好,而IP-MRS-k具有最佳平衡性能.

表2 Movielens數(shù)據(jù)集中6位目標(biāo)用戶(hù)各算法推薦準(zhǔn)確率Table 2 Precision by different algorithms for six users in Movielens dataset

表3 Movielens數(shù)據(jù)集中6位目標(biāo)用戶(hù)各算法推薦多樣性Table 3 Diversity by different algorithms for six users in Movielens dataset

表4 Movielens數(shù)據(jù)集中6位目標(biāo)用戶(hù)各算法推薦新穎度Table 4 Novelty by different algorithms for six users in Movielens dataset

表5 Netflix數(shù)據(jù)集中6位目標(biāo)用戶(hù)各算法推薦準(zhǔn)確率Table 5 Precision by different algorithms for six users in Netflix dataset

表6 Netflix數(shù)據(jù)集中6位目標(biāo)用戶(hù)各算法推薦多樣性Table 6 Diversity by different algorithms for six users in Netflix dataset

表7 Netflix數(shù)據(jù)集中6位目標(biāo)用戶(hù)各算法推薦新穎度Table 7 Novelty by different algorithms for six users in Netflix dataset

圖6 Movielens數(shù)據(jù)集中20位目標(biāo)用戶(hù)各算法推薦性能Fig.6 Performance of different algorithms for 20 target users in Movielens dataset

圖7 Netflix數(shù)據(jù)集中20位目標(biāo)用戶(hù)各算法推薦性能Fig.7 Performance of different algorithms for 20 target users in Netflix dataset

3.4.2 降低決策負(fù)擔(dān)有效性

多目標(biāo)推薦算法雖能同時(shí)優(yōu)化準(zhǔn)確性和多樣性,但其輸出的解集數(shù)量較多,在決策偏好未知的情況下,不利于推薦系統(tǒng)最終選擇.表8、表9分別展示了兩個(gè)數(shù)據(jù)集中不同MORS算法最終提供給6位目標(biāo)用戶(hù)的推薦方案數(shù)量,在偏好區(qū)域內(nèi)的推薦方案數(shù)量較大程度低于MOEA-RS.降低推薦方案的數(shù)量對(duì)于推薦系統(tǒng)最終決策有一定優(yōu)勢(shì).例如當(dāng)給ID號(hào)328的用戶(hù)進(jìn)行推薦,MOEA-RS給用戶(hù)提供了29個(gè)推薦列表,而IP-MRS則是給用戶(hù)提供3大類(lèi)具有不同偏好屬性的推薦模式,每種模式各提供5～8個(gè)推薦列表.圖8展示了兩個(gè)數(shù)據(jù)集中不同MORS給20位用戶(hù)提供推薦方案數(shù)量的平均值,3個(gè)偏好區(qū)域的IP-MRS提供的推薦方案數(shù)量顯著低于MOEA-RS,由此降低了推薦系統(tǒng)的決策負(fù)擔(dān).

表8 Movielens數(shù)據(jù)集中6位目標(biāo)用戶(hù)推薦方案數(shù)量Table 8 Number of solutions from 6 users in Movielens dataset

表9 Netflix數(shù)據(jù)集中6位目標(biāo)用戶(hù)推薦方案數(shù)量Table 9 Number of solutions from 6 users in Netflix dataset

圖8 20位用戶(hù)推薦方案數(shù)量均值Fig.8 Average number of solutions from 20 users

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

針對(duì)傳統(tǒng)推薦算法無(wú)法兼顧推薦結(jié)果的準(zhǔn)確性和多樣性問(wèn)題.本文提出了一種基于隱式偏好的多目標(biāo)推薦算法,將極值點(diǎn)和膝點(diǎn)作為偏好點(diǎn),利用切比雪夫距離在迭代過(guò)程中對(duì)其動(dòng)態(tài)標(biāo)定,以引導(dǎo)個(gè)體收斂于隱式偏好區(qū)域,得到具有不同偏好的推薦方案.實(shí)驗(yàn)結(jié)果表明,本算法的推薦結(jié)果保證準(zhǔn)確率的同時(shí)多樣性和新穎度得到了有效提升,同時(shí)降低了多目標(biāo)推薦算法的決策復(fù)雜度,有效解決了實(shí)際應(yīng)用問(wèn)題.