播存網(wǎng)絡(luò)環(huán)境下UCL推薦多樣性優(yōu)化算法

顧 梁 楊 鵬 董永強(qiáng)

(東南大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 南京 211189) (計(jì)算機(jī)網(wǎng)絡(luò)和信息集成教育部重點(diǎn)實(shí)驗(yàn)室(東南大學(xué)) 南京 211189) (guliang@seu.edu.cn)

播存網(wǎng)絡(luò)環(huán)境下UCL推薦多樣性優(yōu)化算法

顧 梁 楊 鵬 董永強(qiáng)

(東南大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 南京 211189) (計(jì)算機(jī)網(wǎng)絡(luò)和信息集成教育部重點(diǎn)實(shí)驗(yàn)室(東南大學(xué)) 南京 211189) (guliang@seu.edu.cn)

播存網(wǎng)絡(luò)將廣播分發(fā)模式引入現(xiàn)有互聯(lián)網(wǎng)體系結(jié)構(gòu)，極大地降低網(wǎng)絡(luò)共享過(guò)程中產(chǎn)生的冗余流量，可有效緩解信息過(guò)載問(wèn)題.播存網(wǎng)絡(luò)采用統(tǒng)一內(nèi)容標(biāo)簽(uniform content label, UCL)適配用戶興趣和推薦信息資源，在UCL個(gè)性化推薦過(guò)程中，如何結(jié)合播存網(wǎng)絡(luò)的富語(yǔ)義、高時(shí)效特征，有效地提高UCL推薦列表的多樣性，成為播存網(wǎng)絡(luò)中一個(gè)亟需解決的關(guān)鍵問(wèn)題.針對(duì)播存網(wǎng)絡(luò)環(huán)境的需求，提出了一種基于語(yǔ)義覆蓋樹(shù)的UCL推薦多樣性優(yōu)化算法UDSCT，將該問(wèn)題分為UCL語(yǔ)義覆蓋樹(shù)構(gòu)建和多樣化UCL列表查詢2個(gè)步驟.在UCL語(yǔ)義覆蓋樹(shù)構(gòu)建階段，基于語(yǔ)義覆蓋樹(shù)的若干約束條件，充分考慮UCL語(yǔ)義信息及非語(yǔ)義用戶評(píng)分信息，同時(shí)，較新的UCL具有較高的優(yōu)先權(quán)，以保證列表的時(shí)效性；在多樣化UCL列表查詢階段，采用簡(jiǎn)單樹(shù)查詢及啟發(fā)式列表補(bǔ)充操作，可快速高效地獲得多樣性優(yōu)化后的UCL推薦列表，并可進(jìn)一步根據(jù)用戶請(qǐng)求快速返回指定的UCL集合.通過(guò)理論分析及一系列仿真實(shí)驗(yàn)驗(yàn)證，結(jié)果證明：UDSCT算法相對(duì)于基準(zhǔn)算法能夠獲得更好的多樣性優(yōu)化效果及效率，可有效滿足播存網(wǎng)絡(luò)環(huán)境的需求.

播存網(wǎng)絡(luò)；統(tǒng)一內(nèi)容標(biāo)簽；推薦；多樣性；時(shí)效性

互聯(lián)網(wǎng)在給人們帶來(lái)豐富信息資源的同時(shí)，自身流量也與日俱增.造成互聯(lián)網(wǎng)協(xié)議流量激增的主要原因之一是互聯(lián)網(wǎng)的內(nèi)容訪問(wèn)日益呈現(xiàn)出冪律分布的特性，即大量用戶對(duì)熱門資源的重復(fù)性訪問(wèn)耗費(fèi)了大量的數(shù)據(jù)傳輸帶寬.現(xiàn)有互聯(lián)網(wǎng)架構(gòu)和內(nèi)容傳輸技術(shù)體系越來(lái)越難以為高效信息共享提供有效的支持.

為改變這種局面，播存網(wǎng)絡(luò)(Broadcast-Storage network, BSN)[1-2]把信息資源映射為互聯(lián)網(wǎng)中可拆可聚的活版基元，將廣播分發(fā)模式引入現(xiàn)有互聯(lián)網(wǎng)體系結(jié)構(gòu)，采用以“廣播+存儲(chǔ)”為特征的信息共享方式，通過(guò)物理廣播將熱門信息資源直接輻射分發(fā)到用戶終端附近的邊緣服務(wù)器供用戶訪問(wèn)，從而利用物理廣播的天然優(yōu)勢(shì)，突破傳統(tǒng)信息共享方式所面臨的寬帶資源制約，實(shí)現(xiàn)“共享不限人數(shù)”的新型高效信息共享途徑，極大地降低網(wǎng)絡(luò)中共享過(guò)程中產(chǎn)生的冗余流量，從而有效緩解“信息過(guò)載”問(wèn)題.

Fig. 1 The model of Broadcast-Storage network[3]圖1 播存網(wǎng)絡(luò)模型[3]

播存網(wǎng)絡(luò)模型如圖1所示[3].其中，統(tǒng)一內(nèi)容標(biāo)簽(uniform content label, UCL)[4]與信息資源一一對(duì)應(yīng)，包含信息資源的摘要信息，用戶通過(guò)其接收到的UCL判斷是否需要訪問(wèn)信息資源全文.同時(shí)，由于UCL數(shù)量巨大而用戶接收能力有限，播存網(wǎng)絡(luò)根據(jù)用戶特點(diǎn)建立用戶興趣模型，預(yù)測(cè)用戶對(duì)所有UCL的感興趣程度(量化為預(yù)測(cè)評(píng)分)，并采用主動(dòng)推薦的方式將感興趣程度較高的UCL推送給用戶，幫助用戶高效精確地尋找及訪問(wèn)其偏好的信息資源.而由于UCL種類繁雜、數(shù)量巨大，在推薦過(guò)程中，若僅依據(jù)用戶對(duì)UCL的預(yù)測(cè)評(píng)分，容易造成所推薦的UCL相似度過(guò)高、種類單一，難以全面地挖掘播存網(wǎng)絡(luò)中用戶的興趣.因此，如何在UCL個(gè)性化推薦過(guò)程中，在保證精度的基礎(chǔ)上，盡可能地提高所推薦UCL的類別多樣性，成為播存網(wǎng)絡(luò)中亟需解決的關(guān)鍵問(wèn)題.

本質(zhì)上而言，該問(wèn)題為信息獲取領(lǐng)域的結(jié)果集合多樣性優(yōu)化問(wèn)題，并已被證明為NP難問(wèn)題.目前已有的解決方法多為啟發(fā)式算法，可大致分為2條思路：置換啟發(fā)式(swap heuristics, SH)[5]和貪婪啟發(fā)式(greedy heuristics, GH)[6].假設(shè)最終的多樣化集合包含k個(gè)元素，前者首先從所有待選元素中隨機(jī)選出k個(gè)元素，然后遍歷所有剩余的待選元素，逐一與已選出的元素進(jìn)行替換比較，從而優(yōu)化最終的集合多樣性；后者采用k步篩選，每個(gè)篩選過(guò)程增加一個(gè)元素至集合，并保證當(dāng)前的集合多樣性最高，直至集合中包含k個(gè)元素.

然而，在播存網(wǎng)絡(luò)環(huán)境中，傳統(tǒng)結(jié)果集合多樣性優(yōu)化具有自身的一些局限性，具體表現(xiàn)在3個(gè)方面：

1) 難以有效確定加權(quán)參數(shù).傳統(tǒng)多樣性優(yōu)化方法往往需要設(shè)定加權(quán)參數(shù)以在精度及多樣性之間取得平衡.通常，數(shù)據(jù)集的特征對(duì)加權(quán)參數(shù)的確定有重要影響.而在播存網(wǎng)絡(luò)環(huán)境中，由于UCL分發(fā)較為頻繁，數(shù)據(jù)集不斷變化，很難確定一個(gè)恰當(dāng)?shù)募訖?quán)參數(shù)能夠持續(xù)保證UCL推薦的多樣性及精度.

2) 缺乏UCL時(shí)效性處理機(jī)制.播存網(wǎng)絡(luò)環(huán)境中UCL包含信息資源的摘要信息，與信息資源一一對(duì)應(yīng)，更新速度快，具有很強(qiáng)的時(shí)效性.傳統(tǒng)多樣性優(yōu)化方法很少考慮優(yōu)化對(duì)象的時(shí)效性，容易導(dǎo)致優(yōu)化后的集合中包含比較陳舊的UCL，降低用戶體驗(yàn).

3) 無(wú)法快速產(chǎn)生優(yōu)化結(jié)果.UCL數(shù)目巨大，在播存網(wǎng)絡(luò)持續(xù)動(dòng)態(tài)運(yùn)行時(shí)，如何基于大量的UCL數(shù)據(jù)快速及時(shí)地為用戶提供多樣性優(yōu)化結(jié)果尤為重要.傳統(tǒng)多樣性優(yōu)化方法通常需要大量的迭代運(yùn)算，收斂較為緩慢，無(wú)法高效滿足播存網(wǎng)絡(luò)的需求.

針對(duì)上述3個(gè)問(wèn)題，本文基于語(yǔ)義覆蓋樹(shù)提出了一種適用于播存網(wǎng)絡(luò)環(huán)境的UCL推薦多樣性優(yōu)化算法(UCL diversification based on semantic cover tree, UDSCT)，能夠克服傳統(tǒng)多樣性優(yōu)化方法在播存網(wǎng)絡(luò)環(huán)境中存在的不足，并可充分利用UCL語(yǔ)義信息及非語(yǔ)義用戶評(píng)分信息，在保證UCL推薦精度的前提下，優(yōu)化UCL推薦結(jié)果的多樣性.

1 相關(guān)工作

目前，播存網(wǎng)絡(luò)的相關(guān)研究主要圍繞互聯(lián)網(wǎng)訪問(wèn)特征、播存網(wǎng)絡(luò)的基本架構(gòu)、UCL的格式設(shè)計(jì)與標(biāo)引及播存網(wǎng)絡(luò)環(huán)境中的UCL個(gè)性化推薦機(jī)制等幾個(gè)方面展開(kāi).

文獻(xiàn)[7]提出用戶對(duì)Web網(wǎng)頁(yè)的訪問(wèn)是由用戶需求行為確定的一個(gè)隨時(shí)間演化的復(fù)雜雙模式二分網(wǎng)絡(luò)，并通過(guò)實(shí)證研究分析發(fā)現(xiàn)，其入度分布呈現(xiàn)出典型的無(wú)標(biāo)度特征和集聚現(xiàn)象.文獻(xiàn)[8]對(duì)互聯(lián)網(wǎng)中用戶訪問(wèn)Web網(wǎng)頁(yè)時(shí)所產(chǎn)生的路由跳數(shù)進(jìn)行了研究與測(cè)量，得到每條訪問(wèn)記錄所需的平均路由跳數(shù)為13.11.文獻(xiàn)[7-8]為播存網(wǎng)絡(luò)模型提供了理論基礎(chǔ)與數(shù)據(jù)支撐.

文獻(xiàn)[4]對(duì)播存網(wǎng)絡(luò)的原理與基本模型進(jìn)行了系統(tǒng)詳細(xì)的闡述.文獻(xiàn)[2]進(jìn)一步對(duì)播存網(wǎng)絡(luò)模型進(jìn)行了研究，給出了播存網(wǎng)絡(luò)的普適模型及其數(shù)學(xué)描述，并重點(diǎn)研究了4種實(shí)現(xiàn)模式，為播存網(wǎng)絡(luò)提供了嚴(yán)格的定義及規(guī)范.播存網(wǎng)絡(luò)中，用戶通過(guò)UCL判斷是否需要某條信息資源.文獻(xiàn)[3]針對(duì)播存網(wǎng)絡(luò)的特點(diǎn)，提出一種播存網(wǎng)絡(luò)環(huán)境下的UCL推薦方法，可根據(jù)用戶的歷史訪問(wèn)記錄建立用戶特征模型，精確預(yù)測(cè)用戶可能感興趣的UCL.然而，文獻(xiàn)[3]未考慮UCL推薦列表的多樣性，本文在文獻(xiàn)[3]的基礎(chǔ)上重點(diǎn)研究UCL推薦的多樣性優(yōu)化問(wèn)題.

結(jié)果集合多樣性優(yōu)化問(wèn)題已在信息獲取領(lǐng)域得到廣泛關(guān)注，研究人員已經(jīng)證明該問(wèn)題為NP難問(wèn)題，并提出了多種啟發(fā)式解決方法.Adomavicius等人在文獻(xiàn)[9]中指出，采用啟發(fā)式算法改變初始推薦列表中項(xiàng)目的排序可使得推薦性能，尤其是多樣性得到很大提高，并且啟發(fā)式優(yōu)化算法在邏輯上獨(dú)立于預(yù)測(cè)算法，算法可部署性較好.根據(jù)算法設(shè)計(jì)思路，現(xiàn)有基于啟發(fā)式思想的推薦列表多樣性優(yōu)化研究主要可以分為2條思路：置換啟發(fā)式(swap heuristics, SH)和貪婪啟發(fā)式(greedy heuristics, GH).

GH方法根據(jù)選定的效用函數(shù)依次從總集合中選出當(dāng)前最佳的項(xiàng)目加入子集合，其中效用函數(shù)可以采用相關(guān)性函數(shù)或者距離函數(shù)，不同的效用函數(shù)會(huì)帶來(lái)差異性的多樣性優(yōu)化效果.Carbonell等人[10]提出采用最大邊緣相關(guān)(maximal marginal relevance, MMR)作為效用函數(shù)的貪婪優(yōu)化方法，是該領(lǐng)域的先驅(qū)性研究之一.此后，研究人員進(jìn)一步針對(duì)效用函數(shù)進(jìn)行研究.文獻(xiàn)[11]提出多樣性效用函數(shù)所需滿足的一些公理，并指出目前沒(méi)有任何一種方法可以同時(shí)滿足這些公理.Ziegler等人[12]提出了一種基于推薦列表內(nèi)部相似度最小化思想的多樣性優(yōu)化效用函數(shù)，在每次進(jìn)行貪婪選擇時(shí)，最小化當(dāng)前推薦列表的內(nèi)部綜合相似度.Ashkan等人[6]提出一種DUM方法，將推薦列表多樣性優(yōu)化問(wèn)題轉(zhuǎn)化為子模函數(shù)約束條件下的模函數(shù)最大化問(wèn)題，該方法的特色在于僅需要最大化模函數(shù)，降低了問(wèn)題復(fù)雜度.

與GH方法不同的是，SH方法首先初始化一個(gè)待推薦項(xiàng)目子集合，然后逐步遍歷總集合中的其他元素，并與子集合中的某個(gè)元素交換，以提高子集合的多樣化.Erkut等人[13]分析了SH方法的特點(diǎn)，并將該方法劃分為2種：1)選出第1個(gè)能夠提高當(dāng)前子集合多樣性的項(xiàng)目并進(jìn)行置換；2)選出能夠最大幅度提高當(dāng)前子集合多樣性的項(xiàng)目并進(jìn)行置換.Erkut等人認(rèn)為通常情況下前者的效果更好.Vieira等人[5]進(jìn)一步研究SH方法發(fā)現(xiàn)，在置換過(guò)程中加入隨機(jī)性會(huì)取得更好的效果，針對(duì)這種現(xiàn)象，他們通過(guò)分析發(fā)現(xiàn)，在優(yōu)化過(guò)程中，一些對(duì)當(dāng)前集合多樣性沒(méi)有提高作用的項(xiàng)目在后續(xù)過(guò)程中可能會(huì)產(chǎn)生有益影響.Liu等人[14]提出一種多置換(multi-swap)策略，在一次置換過(guò)程中，考慮同時(shí)置換多個(gè)項(xiàng)目，加快了算法收斂速度.

除了SH和GH啟發(fā)式方法，也有研究人員嘗試從其他思路解決該問(wèn)題.文獻(xiàn)[15]利用多臂bandits模型學(xué)習(xí)優(yōu)化推薦集合多樣性，該方法基于用戶的點(diǎn)擊行為，可及時(shí)捕捉用戶興趣變化，及時(shí)調(diào)整優(yōu)化效果.但該方法忽略了優(yōu)化對(duì)象的語(yǔ)義信息，抑制了集合多樣性的提高.文獻(xiàn)[16]引入概率模型解決推薦系統(tǒng)中多樣性與相關(guān)性之間相對(duì)矛盾的問(wèn)題，并通過(guò)控制參數(shù)調(diào)整二者的重要性.雖然這種混合模型在很多場(chǎng)景下效果不錯(cuò)，但一般情況下很難獲得一個(gè)通用的算法控制參數(shù).Qin等人[17]提出利用規(guī)則熵提高多樣性，并證明了方法的有效性，但仍然需要提前設(shè)定算法控制參數(shù).Drosou等人[18]提出一種基于覆蓋樹(shù)的方法優(yōu)化集合多樣性，取得了不錯(cuò)的優(yōu)化效果，但該方法僅基于用戶的評(píng)分模式，同樣缺乏利用優(yōu)化對(duì)象語(yǔ)義信息的機(jī)制.

上述研究成果涉及到播存網(wǎng)絡(luò)及結(jié)果集合多樣性優(yōu)化2個(gè)方面，為本文研究提供了指引與啟發(fā).但是，綜合分析以上研究可知，已有多樣性優(yōu)化方法在播存網(wǎng)絡(luò)環(huán)境下存在不少問(wèn)題：一方面，播存網(wǎng)絡(luò)環(huán)境下UCL數(shù)量巨大，更新頻繁，而已有方法大多需要基于當(dāng)前已有數(shù)據(jù)通過(guò)預(yù)先運(yùn)算尋找合適的控制參數(shù)，以提高結(jié)果集合的多樣性，無(wú)法高效滿足播存網(wǎng)絡(luò)環(huán)境要求；另一方面，播存網(wǎng)絡(luò)環(huán)境下UCL對(duì)應(yīng)于信息資源，具有明顯的時(shí)效性，已有方法主要針對(duì)多樣性與相關(guān)性，缺乏對(duì)時(shí)效性的考慮，容易造成優(yōu)化后的結(jié)果集合“過(guò)時(shí)”，降低播存網(wǎng)絡(luò)環(huán)境中的用戶體驗(yàn)；此外，由于UCL的數(shù)量巨大，播存網(wǎng)絡(luò)環(huán)境下用戶對(duì)于UCL的反饋速度要求更為迫切，已有方法大多需要大量迭代運(yùn)算，效率有待提高完善.

基于以上分析，本文提出一種基于語(yǔ)義覆蓋樹(shù)的UCL推薦多樣性優(yōu)化算法UDSCT，克服已有方法在播存網(wǎng)絡(luò)環(huán)境中存在的不足.首先，本文在普通覆蓋樹(shù)基礎(chǔ)上，面向UCL設(shè)計(jì)了一種時(shí)間敏感的語(yǔ)義覆蓋樹(shù)，在構(gòu)造該樹(shù)的過(guò)程中同時(shí)考慮了用戶評(píng)分模式及UCL語(yǔ)義信息，且時(shí)效性較強(qiáng)的UCL優(yōu)先插入樹(shù)的頂端；其次，本文基于該樹(shù)提出了具體的多樣性優(yōu)化算法，包括1種子集合初步查詢算法及2種啟發(fā)式調(diào)整算法，本文還設(shè)計(jì)了用戶請(qǐng)求響應(yīng)機(jī)制，可快速反饋與用戶指定UCL高度相關(guān)的結(jié)果集合；最后，本文證明與分析了上述多樣性優(yōu)化算法及用戶請(qǐng)求響應(yīng)機(jī)制的正確性及有效性，仿真實(shí)驗(yàn)結(jié)果表明，該算法具有良好的優(yōu)化效果，可有效滿足播存網(wǎng)絡(luò)環(huán)境下UCL推薦多樣性優(yōu)化的需求.

2 UDSCT算法詳細(xì)描述

本節(jié)首先描述基于語(yǔ)義覆蓋樹(shù)的推薦列表多樣性優(yōu)化算法的總體流程，然后給出算法相關(guān)的形式化定義，最后詳細(xì)描述具體的UCL語(yǔ)義覆蓋樹(shù)構(gòu)造算法及UCL推薦多樣性優(yōu)化算法.

基于語(yǔ)義覆蓋樹(shù)的UCL推薦列表多樣性優(yōu)化算法的總體流程如圖2所示.該算法首先根據(jù)時(shí)間順序構(gòu)建時(shí)間敏感的UCL語(yǔ)義覆蓋樹(shù)，然后基于該樹(shù)通過(guò)查詢操作及補(bǔ)充算法獲得多樣化的UCL列表，最后將該UCL推薦給用戶并根據(jù)用戶請(qǐng)求響應(yīng)聚焦請(qǐng)求.

Fig. 2 The flow chart of UDSCT圖2 UDSCT算法流程圖

2.1UDSCT算法相關(guān)定義

為更清楚地描述該問(wèn)題及其解決算法，本節(jié)給出了相關(guān)定義.

定義1.k-UCL列表多樣性優(yōu)化.令I(lǐng)={i1,i2,…,im}為UCL列表，U為多樣性度量函數(shù)，k為正整數(shù)(k≤|I|)，k-UCL列表多樣性優(yōu)化目標(biāo)為尋找I的最優(yōu)化子列表S*，滿足條件：

(1)

在獲得當(dāng)前最優(yōu)UCL子列表后S*，系統(tǒng)將其呈現(xiàn)給用戶，用戶可能對(duì)其中的某一個(gè)UCL感興趣，并希望得到一個(gè)與該UCL相關(guān)度更高的子列表.本文將這個(gè)過(guò)程定義為聚焦，形式化描述如下：

定義2. UCL聚焦.在定義1的基礎(chǔ)上，聚焦操作根據(jù)用戶的反饋查詢當(dāng)前最優(yōu)UCL列表S*中更符合用戶興趣的子列表S′，使得：

(2)

以上定義均基于語(yǔ)義覆蓋樹(shù)實(shí)現(xiàn)，語(yǔ)義覆蓋樹(shù)由覆蓋樹(shù)發(fā)展演化而來(lái)，覆蓋樹(shù)最初由Beygelzimer等人在文獻(xiàn)[19]中提出，用以快速查找最近鄰.覆蓋樹(shù)為分層的樹(shù)數(shù)據(jù)結(jié)構(gòu)，樹(shù)中的每一層均覆蓋其下面所有的層，樹(shù)中的層數(shù)用整數(shù)l標(biāo)示，且l從上往下逐步減小.對(duì)于給定的一個(gè)項(xiàng)目(如UCL)列表S，S中的每個(gè)項(xiàng)目均對(duì)應(yīng)于覆蓋樹(shù)中的至少一個(gè)節(jié)點(diǎn).

定義3. 覆蓋樹(shù).令Cl表示第l層的節(jié)點(diǎn)列表，d(p,q)表示節(jié)點(diǎn)p和q之間的距離，覆蓋樹(shù)必須同時(shí)滿足3個(gè)約束條件：

1) 嵌套性.Cl-1?Cl，即如果p出現(xiàn)在第l層(p∈Cl)，則它必出現(xiàn)在第l層之下的所有層(p∈Cj,j>l).

2) 覆蓋性.對(duì)于每一個(gè)p∈Cl，有且僅有一個(gè)q∈Cl-1作為p的父節(jié)點(diǎn)，且q滿足d(p,q)≤1/2l-1.

3) 分離性.所有的p,q∈Cl，均滿足d(p,q)>1/2l.

基于覆蓋樹(shù)的以上特性，可以總結(jié)出其在UCL推薦多樣性優(yōu)化問(wèn)題方面所具有的獨(dú)特優(yōu)勢(shì).一方面，覆蓋樹(shù)由多層節(jié)點(diǎn)構(gòu)成，每一層都包含了不同數(shù)目的節(jié)點(diǎn)并且同層節(jié)點(diǎn)之間的距離均存在最低閾值，該閾值隨著樹(shù)高度的降低而逐步減小，即上層中的節(jié)點(diǎn)之間最小距離較大，而下層中的節(jié)點(diǎn)之間最小距離較小，這種特性保證了每一層以及整個(gè)覆蓋樹(shù)的節(jié)點(diǎn)多樣性.另一方面，覆蓋樹(shù)可以根據(jù)用戶的請(qǐng)求在覆蓋樹(shù)中的合適高度選取節(jié)點(diǎn)列表返回給用戶，查詢過(guò)程簡(jiǎn)單、運(yùn)算量小，可以保證UCL推薦多樣性優(yōu)化算法的高效性.

但是，覆蓋樹(shù)在解決播存網(wǎng)絡(luò)環(huán)境下UCL推薦多樣性優(yōu)化問(wèn)題時(shí)仍然存在著2個(gè)較為明顯的缺陷.1)覆蓋樹(shù)并不考慮節(jié)點(diǎn)的內(nèi)容語(yǔ)義信息，無(wú)法有效利用UCL所包含的豐富語(yǔ)義信息；2)在UCL推薦多樣性優(yōu)化過(guò)程中，UCL的時(shí)效性對(duì)用戶體驗(yàn)有著重要影響，覆蓋樹(shù)缺乏針對(duì)時(shí)效性的處理機(jī)制.

為此，本文對(duì)覆蓋樹(shù)進(jìn)行相應(yīng)擴(kuò)展，設(shè)計(jì)了一種時(shí)間敏感的UCL語(yǔ)義覆蓋樹(shù).

定義4. UCL語(yǔ)義覆蓋樹(shù).語(yǔ)義覆蓋樹(shù)為覆蓋樹(shù)的一種特例，在覆蓋樹(shù)的基礎(chǔ)上增加了時(shí)效性及語(yǔ)義信息等限制條件，UCL語(yǔ)義覆蓋樹(shù)需同時(shí)滿足3個(gè)約束條件：

1) 基本條件.覆蓋樹(shù)所滿足的3個(gè)約束條件：嵌套性、覆蓋性和分離性.

2) 時(shí)效性.對(duì)于所有的UCLp∈Ci，令UCLs為p在l-1層的父節(jié)點(diǎn)，則有ts≤tp，其中ts，tp分別表示UCLs和p的時(shí)間.

上述條件中，時(shí)效性保證了每個(gè)父節(jié)點(diǎn)均比其子節(jié)點(diǎn)更加新穎，從而使得從上往下遍歷樹(shù)尋找匹配用戶興趣時(shí)能夠優(yōu)先選擇時(shí)效性更高的UCL.而語(yǔ)義聚集性則確保了在構(gòu)建樹(shù)的過(guò)程中，父節(jié)點(diǎn)與子節(jié)點(diǎn)之間的語(yǔ)義相似度更高，間接地促進(jìn)了UCL列表的多樣性效果.

2.2UDSCT算法描述

在介紹完相關(guān)基本概念后，本節(jié)將繼續(xù)介紹如何完成UCL語(yǔ)義覆蓋樹(shù)的構(gòu)造、如何基于該樹(shù)完成UCL推薦多樣性優(yōu)化以及如何進(jìn)一步快速響應(yīng)用戶的聚焦請(qǐng)求.

2.2.1 UCL語(yǔ)義覆蓋樹(shù)構(gòu)造

UCL語(yǔ)義覆蓋樹(shù)采用自頂向下、逐個(gè)插入U(xiǎn)CL的方式構(gòu)造，首先選擇最新的UCL作為樹(shù)的根，然后遵循“新穎優(yōu)先”的原則插入其他UCL.需要說(shuō)明的是，在插入過(guò)程中，必須嚴(yán)格保證3個(gè)約束條件不被違背.構(gòu)造的詳細(xì)過(guò)程如算法1所示.

算法1. UCL語(yǔ)義覆蓋樹(shù)的構(gòu)造.

輸入: 待優(yōu)化UCL列表I；

輸出: 列表I對(duì)應(yīng)的UCL語(yǔ)義覆蓋樹(shù).

/*按照時(shí)間順序?qū)中的UCL進(jìn)行排序，依次調(diào)用函數(shù)Insert()*/

①I=reversedChronological(I)；

② ForeachiinI

③ IfindexOf(i)==0

④Troot=i；

⑤ Else

⑥Insert(i,Q0,0)；

⑦ EndIf

⑧ EndForeach

/*Insert(itemp,Ql,levell):將UCLp插入到T的第l層*/

⑨C={children of each node inQl}；

算法1中Insert()是基于文獻(xiàn)[19]中的插入算法，但由于該算法僅可用于構(gòu)建基本覆蓋樹(shù)，故需要對(duì)其進(jìn)行適當(dāng)改進(jìn)，在構(gòu)建過(guò)程中除了需要遵循定義3中的約束條件，還需兼顧定義4中的條件.具體而言，算法1首先根據(jù)時(shí)間順序?qū)⒁延蠻CL列表進(jìn)行排序，然后依次調(diào)用插入函數(shù)Insert(itemp,Ql,levell)(行①～⑧)，該操作保證了構(gòu)造過(guò)程滿足了時(shí)效性約束條件，最先插入的最新穎的節(jié)點(diǎn)作為樹(shù)的根.插入函數(shù)以待插入的UCL、待插入的層數(shù)以及該層已含有的UCL作為輸入?yún)?shù)，然后逐層遞歸地檢查直到發(fā)現(xiàn)滿足分離性約束條件的層數(shù)(行⑨～).在第一次找到該層之后，該函數(shù)將上一層中滿足覆蓋性條件的UCL節(jié)點(diǎn)識(shí)別出放入待插入節(jié)點(diǎn)的父節(jié)點(diǎn)候選節(jié)點(diǎn)集合(行).最終，該算法依次計(jì)算待插入U(xiǎn)CL的特征向量與父節(jié)點(diǎn)候選節(jié)點(diǎn)集合中的節(jié)點(diǎn)的特征向量的語(yǔ)義關(guān)聯(lián)程度，選出關(guān)聯(lián)度最高的UCL節(jié)點(diǎn)作為待插入節(jié)點(diǎn)的最終父節(jié)點(diǎn)(行).

在構(gòu)造UCL語(yǔ)義覆蓋樹(shù)的過(guò)程中，語(yǔ)義聚集條件使得UCL節(jié)點(diǎn)總是選擇與其語(yǔ)義最為相關(guān)的UCL節(jié)點(diǎn)作為父節(jié)點(diǎn)，這進(jìn)一步加強(qiáng)了同層節(jié)點(diǎn)之間的多樣性，并為之后的UCL聚焦操作提供了重要基礎(chǔ).

2.2.2 多樣化UCL結(jié)果集合查詢

UCL語(yǔ)義覆蓋樹(shù)中的每個(gè)節(jié)點(diǎn)都對(duì)應(yīng)了UCL推薦列表中的一個(gè)UCL，當(dāng)用戶確定想要獲取的UCL數(shù)目后，只需逐層遍歷樹(shù)的節(jié)點(diǎn)，獲得合適的UCL列表.具體而言，層數(shù)越低，該層的UCL之間距離越大，該層的多樣性便越高.下降搜索過(guò)程如算法2所示.

算法2. 多樣化列表初步查詢算法.

輸入: UCL列表I對(duì)應(yīng)的語(yǔ)義覆蓋樹(shù)T、結(jié)果子列表中UCL數(shù)目k；

輸出: 包含k個(gè)UCL多樣化的子列表S*.

①l=0；

② While (l

③ If |Ql|≥k

④ Break；

⑤ EndIf

⑥l=l+1；

⑦ EndWhile

⑧Sb=Ql-1；

⑨C=Ql-Ql-1；

⑩S*=supplement(Sb,C,k)；

對(duì)于UCL列表I對(duì)應(yīng)的UCL語(yǔ)義覆蓋樹(shù)以及用戶指定的子列表大小，算法2首先定位相鄰的兩層l和l-1，使得|Ql-1|

算法3. 貪婪補(bǔ)充算法.

輸入: 基礎(chǔ)子列表Sb、候選集合C、結(jié)果子集合中UCL數(shù)目k；

輸出: 包含k個(gè)UCL多樣化的子集合S*.

①S*=Sb；

② While (|S*|

④S*=S*∪{p}；

⑤ EndWhile

⑥ returnS*.

算法4. 置換補(bǔ)充算法.

輸入: 基礎(chǔ)子列表Sb、候選集合C、結(jié)果子集合中UCL數(shù)目k；

輸出: 包含k個(gè)UCL多樣化的子集合S*.

①S*=Sb,R=Randomk-|S*|(C)；

②S*=Sb∪R；

③θ=MAX；

④ While (θ>δ0) do

⑤ra=Random1(C-R),rb=Random1(S*)；

⑥θ=div(S*∪{ra}-{rb})-div(S*)；

⑦ Ifθ>δ0

⑧S*=S*∪{ra}-{rb}；

⑨ Else

⑩ Continue；

而在置換補(bǔ)充算法中，首先從候選集合中隨機(jī)選出k-|S*|個(gè)UCL節(jié)點(diǎn)并加入到初始子集合S*中，Randomm(S)函數(shù)負(fù)責(zé)隨機(jī)從S中選擇m個(gè)UCL.本質(zhì)上而言，S*由2部分組成：1)來(lái)自初始子集合Sb的已確定部分;2)來(lái)自候選集的待優(yōu)化部分.之后，分別隨機(jī)從剩余的候選集合C-R及待優(yōu)化部分R中取出2個(gè)UCL節(jié)點(diǎn)ra和rb，然后計(jì)算出是否ra比rb對(duì)已選出子集合的多樣性提高更大.該多樣性的提高被量化為變量θ，為了保證算法的效率，算法4設(shè)定了置換閾值δ0，當(dāng)且僅當(dāng)θ>δ0時(shí)，置換才會(huì)進(jìn)行，否則將忽略該對(duì)節(jié)點(diǎn)，繼續(xù)選出下一對(duì)進(jìn)行比較.置換補(bǔ)充算法不斷重復(fù)隨機(jī)選節(jié)點(diǎn)、多樣性比較等操作，直至子集合的多樣性幾乎保持不變，即θ<δ0.

2.2.3 UCL聚焦響應(yīng)算法

在將初步多樣性優(yōu)化后的UCL列表呈現(xiàn)給用戶后，用戶會(huì)對(duì)其進(jìn)行瀏覽并會(huì)根據(jù)自身興趣及偏好查找自己感興趣的UCL.假設(shè)該用戶對(duì)某個(gè)UCL感興趣，并想進(jìn)一步了解與該UCL更加相關(guān)的一些UCL，此時(shí)，此時(shí)將調(diào)用UCL聚焦響應(yīng)算法，算法的處理流程如算法5所示.

算法5. UCL聚焦響應(yīng)算法.

輸入: UCL列表I對(duì)應(yīng)的語(yǔ)義覆蓋樹(shù)T、用戶指定的UCLq、子列表中UCL數(shù)目k；

輸出: 包含k個(gè)UCL的子列表S′.

①l=0；

② While (l

③ Ifq∈Qlength && (?p∈q.children&&p≠q)

④ Break；

⑤ EndIf

⑥l=l+1；

⑦ EndWhile

⑧T′=new(T) &&q=T′.root；

⑨S′=Query(T′,k)；

⑩ returnS′.

算法5首先根據(jù)用戶請(qǐng)求，從已構(gòu)造的UCL語(yǔ)義覆蓋樹(shù)中逐層查詢用戶感興趣的UCLq(行①～⑦).需要注意的是，根據(jù)覆蓋樹(shù)的特性，相同的UCL可能會(huì)在樹(shù)中出現(xiàn)多次，為了找到恰當(dāng)?shù)墓?jié)點(diǎn)，算法需要找到第1個(gè)帶有非自身子節(jié)點(diǎn)的q(行③).一旦找到該節(jié)點(diǎn)，算法并對(duì)該覆蓋樹(shù)進(jìn)行剪枝處理，僅保留以q為根節(jié)點(diǎn)的子樹(shù)(行⑧).最終，基于該子樹(shù)，便可以調(diào)用子集合查詢算法(算法2)獲取與該UCL更加相關(guān)的UCL列表.

3 算法分析

本節(jié)將分析UDSCT算法復(fù)雜度并總結(jié)、證明其具有的相關(guān)性質(zhì).

3.1算法復(fù)雜度

本文所提UDSCT算法主要由構(gòu)造語(yǔ)義覆蓋樹(shù)及查詢2部分組成，其中查詢部分僅需定位層數(shù)及少量列表補(bǔ)充操作，所占時(shí)間、空間極少，因此本文將重點(diǎn)分析構(gòu)造語(yǔ)義覆蓋樹(shù)所需的時(shí)空復(fù)雜度.語(yǔ)義覆蓋樹(shù)是普通覆蓋樹(shù)的特例，普通覆蓋樹(shù)構(gòu)造的時(shí)間復(fù)雜度為O(nlogn)，空間復(fù)雜度為O(n)[19].對(duì)于語(yǔ)義覆蓋樹(shù)，其構(gòu)造的主要區(qū)別在于需要對(duì)UCL節(jié)點(diǎn)進(jìn)行排序并在構(gòu)建過(guò)程中進(jìn)行語(yǔ)義關(guān)聯(lián)度計(jì)算，前者(快速排序)的時(shí)間復(fù)雜度為O(nlogn)，空間復(fù)雜度為O(logn)，而后者時(shí)空復(fù)雜度均為O(1)，因此，語(yǔ)義覆蓋樹(shù)構(gòu)造的時(shí)間復(fù)雜度為：O(nlogn)+O(nlogn)+O(1)=O(nlogn)，空間復(fù)雜度為O(n)+O(logn)+O(1)=O(n)，由此可知，UDSCT算法復(fù)雜度較低.

3.2算法性質(zhì)

基于語(yǔ)義覆蓋樹(shù)具有3條重要性質(zhì).首先，對(duì)于待插入樹(shù)的UCLi而言，一旦其在樹(shù)中的所屬層數(shù)l確定，則在l-1層中必定有且僅有一個(gè)UCL可以當(dāng)作UCLi的父節(jié)點(diǎn).

證畢.

下面證明UCL語(yǔ)義覆蓋樹(shù)構(gòu)造算法的正確性.

定理2. UCL語(yǔ)義覆蓋樹(shù)構(gòu)造算法滿足定義4中的所有約束條件.

證明. UCL語(yǔ)義覆蓋樹(shù)共包含5個(gè)限制性約束條件，其中，嵌套性、覆蓋性和分離性為覆蓋樹(shù)的基本約束條件，由于UCL語(yǔ)義覆蓋樹(shù)為覆蓋樹(shù)的優(yōu)化數(shù)據(jù)結(jié)構(gòu)，本文不再贅述這3個(gè)約束條件的證明.在構(gòu)造過(guò)程中，算法1首先將待插入U(xiǎn)CL節(jié)點(diǎn)按照時(shí)間順序排序，然后在插入U(xiǎn)CL節(jié)點(diǎn)時(shí)檢查父節(jié)點(diǎn)是否比其子節(jié)點(diǎn)時(shí)效性更高(t.i>t.p)，因此，算法的時(shí)效性得以保證.而對(duì)于語(yǔ)義聚集性，算法在計(jì)算待插入U(xiǎn)CL節(jié)點(diǎn)的父節(jié)點(diǎn)時(shí)總會(huì)從候選集合中選出與其語(yǔ)義相似度最高的節(jié)點(diǎn)作為其父節(jié)點(diǎn)，如定理1所述，因此，語(yǔ)義聚集性得證.綜上所述，最終構(gòu)造出來(lái)的UCL語(yǔ)義覆蓋樹(shù)可同時(shí)滿足5個(gè)約束條件.

證畢.

最后，本文將繼續(xù)證明，采用聚焦操作得到的UCL覆蓋樹(shù)同樣滿足UCL語(yǔ)義覆蓋樹(shù)的約束條件.

定理3. 基于UCL語(yǔ)義覆蓋樹(shù)進(jìn)行聚焦操作，獲得的子樹(shù)同樣滿足5個(gè)限制性約束條件.

證明. 假設(shè)q為UCL語(yǔ)義覆蓋樹(shù)T中第m層的UCL節(jié)點(diǎn)，且聚焦操作返回的新語(yǔ)義覆蓋樹(shù)為T′，即，q為T′的根節(jié)點(diǎn).對(duì)于T′中的任意UCL節(jié)點(diǎn)，令L為其在樹(shù)T中的層數(shù)，那么，在樹(shù)T′中，其所在層數(shù)為：L′=L-m.顯然T′保留了嵌套性、時(shí)效性和語(yǔ)義聚集性.為了證明本定理，本文將論證T′同樣滿足分離性和覆蓋性.對(duì)于樹(shù)T中的任意層n，令m_dis為其中任意2個(gè)UCL節(jié)點(diǎn)的最小距離，則其必定滿足：

m_dis>1/2n=(1/2m)×(1/2n-m).

與此同時(shí)，在樹(shù)T′中，其新的層數(shù)為L(zhǎng)′=n-m，因此可得:

m_dis>1/2n=(1/2m)×1/2L′.

也就是說(shuō)剪枝后的子樹(shù)保留了分離性條件，其距離下界為(1/2m)×1/2L′，易知，該下界取決于新的層數(shù)L′及其根節(jié)點(diǎn)在原始樹(shù)T中的層數(shù).同理可證，算法生成的新樹(shù)L′同樣滿足覆蓋性條件.

證畢.

4 性能評(píng)估

4.1數(shù)據(jù)集及實(shí)驗(yàn)過(guò)程

為了展示基于UDSCT算法的性能優(yōu)勢(shì)并與其它算法進(jìn)行公平對(duì)比，本文在公開(kāi)數(shù)據(jù)集MovieLens*http://www.cs.umn.edu/Research/GroupLens/上進(jìn)行實(shí)驗(yàn)，重點(diǎn)測(cè)試該算法所生成的最終推薦列表在給定指標(biāo)上的性能.該數(shù)據(jù)集包含了943個(gè)用戶對(duì)1 682部電影的評(píng)分，評(píng)分區(qū)間為1～5分，每個(gè)用戶至少評(píng)價(jià)20部電影，每部電影還平均帶有17個(gè)語(yǔ)義標(biāo)簽，可用以代表UCL所包含的語(yǔ)義信息.此外，本文采用隨機(jī)打時(shí)間戳的方法標(biāo)記每個(gè)電影的時(shí)間(播存網(wǎng)絡(luò)中，當(dāng)UCL數(shù)量較大時(shí)，其時(shí)間戳可視為隨機(jī)方式生成)，以確定構(gòu)造UCL語(yǔ)義覆蓋樹(shù)時(shí)的插入順序及進(jìn)行時(shí)效性對(duì)比.

實(shí)驗(yàn)過(guò)程如下：實(shí)驗(yàn)隨機(jī)選擇100名用戶進(jìn)行測(cè)試，首先通過(guò)預(yù)測(cè)算法預(yù)測(cè)用戶的初步推薦列表，然后采用不同的推薦列表多樣性優(yōu)化算法優(yōu)化列表，最后統(tǒng)計(jì)測(cè)試不同算法所取得的相關(guān)性能指標(biāo)并進(jìn)行對(duì)比，針對(duì)對(duì)比結(jié)果給出相應(yīng)分析.為保證實(shí)驗(yàn)結(jié)果的穩(wěn)定性，上述過(guò)程均重復(fù)10組，本文所述結(jié)果為10組結(jié)果的平均值.另外，在實(shí)驗(yàn)過(guò)程中，本文采用PCC值度量基本距離，而對(duì)于語(yǔ)義距離，本文基于用戶對(duì)電影的語(yǔ)義標(biāo)簽信息進(jìn)行計(jì)算.

4.2評(píng)估標(biāo)準(zhǔn)

為全面測(cè)試UDSCT算法的性能，本文將圍繞UCL列表平均精度、列表多樣性(包括列表內(nèi)部元素差異度及列表類別多樣性)、列表時(shí)效性、算法運(yùn)行時(shí)間等指標(biāo)進(jìn)行測(cè)試.

UCL推薦列表平均精度(average list precision,ALP)計(jì)算公式為

(3)

其中,n表示列表中的UCL個(gè)數(shù)，rj表示第j個(gè)UCL的評(píng)分.

列表內(nèi)部元素的差異度(list internal difference,LID)計(jì)算公式為

(4)

其中，ui表示第i個(gè)UCL，sim表示相似度函數(shù)，LID值越高，說(shuō)明列表的多樣性越好.

UCL列表類別多樣性(list category diversity,LCD)的計(jì)算公式為

(5)

UCL列表時(shí)效性(list novelty,LN)的計(jì)算公式為

(6)

其中,ti為列表中第i個(gè)UCL的時(shí)間，tnewest為最新UCL的時(shí)間，toldest為最舊UCL的時(shí)間，LN值越小，UCL列表的時(shí)效性便越高.

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

本實(shí)驗(yàn)部分將根據(jù)第4.2節(jié)中所述評(píng)估標(biāo)準(zhǔn)，對(duì)比分析如下5個(gè)算法：基于貪婪策略的UDSCT算法(GUDSCT)、基于置換策略的UDSCT算法(SUDSCT)、基于普通覆蓋樹(shù)的UCL推薦多樣性優(yōu)化算法(UDCT)[18]、基于預(yù)測(cè)評(píng)分排序的無(wú)多樣性優(yōu)化初始排序算法(NODIV)、基于多置換策略的多樣性優(yōu)化算法(MSDIV)[14].其中，NODIV算法不包括任何多樣性優(yōu)化操作，用以作為其他方法的對(duì)比基準(zhǔn)；UDCT算法用以驗(yàn)證本文算法是否可利用UCL語(yǔ)義及時(shí)效有效地提高相應(yīng)的多樣性及時(shí)效性指標(biāo)；MSDIV算法用以驗(yàn)證本文算法是否可以快速取得多樣性優(yōu)化結(jié)果.

在實(shí)驗(yàn)過(guò)程中，本文首先對(duì)每個(gè)目標(biāo)用戶進(jìn)行評(píng)分預(yù)測(cè)，并從高到低排序，取前n個(gè)(n取值為15～50)UCL作為初始列表，然后采用以上算法對(duì)列表進(jìn)行多樣性優(yōu)化，取前k個(gè)(k≤n，本文取k=10或15)UCL作為最終推薦列表，并計(jì)算各項(xiàng)指標(biāo)，在不同算法之間進(jìn)行對(duì)比.另外，需要說(shuō)明的是，本文將SUDSCT算法與MSDIV算法中的置換閾值δ0=0.01.該參數(shù)對(duì)算法的多樣性及運(yùn)行速度會(huì)有一定影響，本文通過(guò)實(shí)驗(yàn)發(fā)現(xiàn)，當(dāng)δ0=0.01時(shí)，實(shí)驗(yàn)效果較好.而每次置換的元素個(gè)數(shù)會(huì)對(duì)MSDIV算法的運(yùn)行時(shí)間有一定影響，為保證MSDIV算法能夠取得較少的運(yùn)行時(shí)間，本文將其設(shè)置為5.

4.3.1 UCL推薦多樣性

本部分將根據(jù)UCL推薦列表內(nèi)部元素差異度LID及列表類別多樣性LCD兩個(gè)指標(biāo)測(cè)試不同算法的多樣性優(yōu)化效果.

圖3和圖4分別展示了k=10和k=15兩種情況下不同算法之間LID值的對(duì)比結(jié)果.需要指出的是，LID值介于0,1之間.

Fig. 3 LID comparison of different methods when k=10圖3 k=10時(shí)不同方法LID對(duì)比

Fig. 4 LID comparison of different methods when k=15圖4 k=15時(shí)不同方法LID對(duì)比

不難發(fā)現(xiàn)，在所有算法中NODIV算法的LID值最低，無(wú)論候選集合包含多少個(gè)UCL(從15～50)，其LID值始終維持在0.3以下.從圖中還可以發(fā)現(xiàn)GUDSCT與SUDSCT算法的LID值一直較為接近，均高于其他3種算法，也就是說(shuō)基于UCL語(yǔ)義覆蓋樹(shù)的UDSCT算法具有更好的多樣性優(yōu)化效果.而UDCT算法的曲線介于UDSCT算法與MSDIV之間，這表明基于覆蓋樹(shù)的算法所具有的多樣性優(yōu)化效果比典型的啟發(fā)式算法更好，但弱于基于UCL語(yǔ)義覆蓋樹(shù)的算法.本文認(rèn)為，UDCT算法與UDSCT算法之間存在的這種差異正是由于UDCT算法缺乏對(duì)UCL語(yǔ)義信息的考慮.此外，隨著候選集合的增大，所有多樣性優(yōu)化算法的LID值均逐漸升高，同時(shí)，GUDSCT與SUDSCT算法增幅較大.

圖5和圖6分別展示了最終推薦列表集合大小k=10和k=15兩種情況下不同算法之間LCD值的對(duì)比結(jié)果.

Fig. 5 LCD comparison of different methods when k=10圖5 k=10時(shí)不同方法LCD對(duì)比

k=10時(shí)，LCD的取值區(qū)間為[1.998,10].當(dāng)所有UCL屬于同一個(gè)類別時(shí)，LCD取值最小，根據(jù)式(5)可知，LCD=1+12+…+129≈1.998；當(dāng)所有UCL均屬于不同類別時(shí)，LCD取值最大，LCD=10.k=15時(shí)，計(jì)算過(guò)程同上.

整體上而言，圖5和圖6中數(shù)據(jù)的變化趨勢(shì)與圖3和圖4較為一致，與其他3種算法相比，基于UCL語(yǔ)義覆蓋樹(shù)的GUDSCT與SUDSCT算法仍然展示出明顯的性能優(yōu)勢(shì).在k=15，n=50時(shí)，與MSDIV方法相比，這2種方法的LCD值提高了將近10%.此外，需要說(shuō)明的是，當(dāng)候選集合與最終推薦結(jié)果集合含有相同的UCL數(shù)目時(shí)(即k=n)，所有算法的多樣性相同，因?yàn)榇藭r(shí)無(wú)需進(jìn)行多樣性優(yōu)化.

Fig. 6 LCD comparison of different methods when k=15圖6 k=15時(shí)不同方法LCD對(duì)比

4.3.2 UCL推薦精度

表1描述了不同算法對(duì)于UCL推薦精度ALP的影響.從表1可以觀察到，NODIV算法的ALP值保持不變，其他算法的ALP值隨著候選集合的變大而逐步降低.這是由于NODIV算法僅根據(jù)預(yù)測(cè)分?jǐn)?shù)對(duì)UCL列表排序，而候選集合的增大并不會(huì)對(duì)前k個(gè)UCL的預(yù)測(cè)分?jǐn)?shù)及排序產(chǎn)生影響，但在其他算法中，一些預(yù)測(cè)評(píng)分較低但會(huì)提高列表多樣性的UCL可能出現(xiàn)在前k個(gè)位置，從而使得ALP值下降.

Table 1 ALP Comparison of Different Methods表1 不同方法之間的ALP對(duì)比

從表1還可以發(fā)現(xiàn)，基于UCL語(yǔ)義覆蓋樹(shù)的2種算法在推薦精度方面均優(yōu)于UDCT和MSDIV算法，且候選集合愈大，優(yōu)勢(shì)愈明顯.此外總體上而言，所有優(yōu)化算法在k=15時(shí)取得的ALP值均低于k=10時(shí)，這是因?yàn)橥扑]結(jié)果集合較大時(shí)，若高預(yù)測(cè)評(píng)分?jǐn)?shù)量有限，一些低預(yù)測(cè)評(píng)分UCL將出現(xiàn)在推薦集合中，而當(dāng)播存網(wǎng)絡(luò)環(huán)境持續(xù)長(zhǎng)時(shí)間運(yùn)行后，高預(yù)測(cè)評(píng)分UCL數(shù)量會(huì)逐步增加，這種現(xiàn)象會(huì)得到有效緩解.

4.3.3 UCL推薦時(shí)效性

不同算法之間的UCL推薦時(shí)效性比較結(jié)果如表2所示.如4.2節(jié)所述，LN值越低，UCL推薦列表的時(shí)效性越強(qiáng).從表2可以發(fā)現(xiàn)，GUDSCT與SUDSCT算法具有較強(qiáng)的時(shí)效性，在n=50，k=15時(shí)，二者的LN值分別達(dá)到了0.356和0.359.與之形成鮮明對(duì)比的是，UDCT,NODIV,MSDIV等算法的LN值始終在0.57左右浮動(dòng)，無(wú)明顯變化.這種現(xiàn)象表明，在這些算法中，UCL在時(shí)間上是隨機(jī)分布的，顯然，本文所提基于UCL語(yǔ)義覆蓋樹(shù)的算法可顯著提高UCL推薦列表的時(shí)效性.

Table 2 LN Comparison of Different Methods表2 不同方法之間的LN對(duì)比

4.3.4 算法運(yùn)行時(shí)間

UDSCT算法基于語(yǔ)義覆蓋樹(shù)優(yōu)化UCL推薦列表的多樣性，在樹(shù)構(gòu)造完畢后，每次優(yōu)化僅需一次語(yǔ)義覆蓋樹(shù)查詢操作及少量的UCL列表調(diào)整操作，本實(shí)驗(yàn)部分將比較UDSCT算法與其他典型算法的運(yùn)行時(shí)間情況，實(shí)驗(yàn)結(jié)果分別如圖7、圖8所示:

Fig. 7 Running time comparison of different methods when k=10圖7 k=10時(shí)不同算法之間的運(yùn)行時(shí)間對(duì)比

Fig. 8 Running time comparison of different methods when k=15圖8 k=15時(shí)不同算法之間的運(yùn)行時(shí)間對(duì)比

需要指出的是，由于NODIV算法中無(wú)多樣性優(yōu)化操作，故不參加本部分實(shí)驗(yàn).

從圖7、圖8中首先可以發(fā)現(xiàn)，MSDIV算法比基于覆蓋樹(shù)的3種算法(GUDSCT,SUDSCT,UDCT)耗時(shí)更久.此外隨著候選集合的增大，MSDIV算法的耗時(shí)持續(xù)攀升，而基于覆蓋樹(shù)的算法則緩慢上升，后者在n=200時(shí)的耗時(shí)仍少于前者在n=20的耗時(shí)，這表明基于覆蓋樹(shù)的算法具有較好的可擴(kuò)展性.

從圖7、圖8還可以發(fā)現(xiàn)，基于普通覆蓋樹(shù)的UDCT算法比本文所提的UDSCT算法(包括GUDSCT,SUDSCT)耗時(shí)更少，深入分析可知，這是因?yàn)閁DCT算法在構(gòu)建樹(shù)的過(guò)程中無(wú)需排序操作及語(yǔ)義關(guān)聯(lián)運(yùn)算，節(jié)省了部分時(shí)間.同時(shí)SUDSCT算法耗時(shí)比GUDSCT稍久一點(diǎn)，這也不難理解，因?yàn)榍罢咴诓樵兒蟮纳倭空{(diào)整過(guò)程中仍需要較多的迭代置換嘗試.

4.3.5 UCL聚焦操作

在驗(yàn)證UCL聚焦操作性能時(shí)，由于該操作主要基于樹(shù)的裁剪操作，其多樣性、精度、時(shí)效性等指標(biāo)取決于當(dāng)前已構(gòu)建的UCL語(yǔ)義覆蓋樹(shù)，相關(guān)性能已在上述4個(gè)實(shí)驗(yàn)部分測(cè)試，本部分實(shí)驗(yàn)主要關(guān)注UCL聚焦操作的響應(yīng)時(shí)間，實(shí)驗(yàn)結(jié)果如圖9所示:

Fig. 9 Response time of UCL Focus圖9 UCL聚焦響應(yīng)時(shí)間

圖9主要包括了6組實(shí)驗(yàn)結(jié)果，橫坐標(biāo)為響應(yīng)時(shí)間，縱坐標(biāo)為待聚焦的UCL所包含的相關(guān)UCL數(shù)目，每組實(shí)驗(yàn)重復(fù)5次，圖9所展示的為5次的平均結(jié)果.觀察圖9可以發(fā)現(xiàn)，無(wú)論相關(guān)UCL數(shù)目多少，UCL聚焦操作的響應(yīng)時(shí)間總能保持在2.3 ms以內(nèi)，UCL數(shù)目對(duì)響應(yīng)時(shí)間僅有輕微影響.分析可知，這是因?yàn)樵诓煌臈l件下，算法需要進(jìn)行的定位、剪枝操作基本一致，耗時(shí)也差異不大.圖9結(jié)果表明UDSCT中基于樹(shù)查詢的UCL聚焦操作可快速響應(yīng)用戶的操作請(qǐng)求.

5 結(jié) 論

本文針對(duì)播存網(wǎng)絡(luò)環(huán)境的現(xiàn)實(shí)需求，基于語(yǔ)義覆蓋樹(shù)提出一種UCL推薦多樣性優(yōu)化算法UDSCT，可充分利用UCL語(yǔ)義信息及非語(yǔ)義用戶評(píng)分信息，在保證UCL推薦精度的前提下，優(yōu)化UCL推薦結(jié)果的多樣性.首先，在多樣性優(yōu)化過(guò)程中，無(wú)需設(shè)定或訓(xùn)練任何加權(quán)參數(shù)，可基于UCL語(yǔ)義信息及非語(yǔ)義用戶評(píng)分信息，取得穩(wěn)定可靠的多樣性優(yōu)化效果；其次，在優(yōu)化排序過(guò)程中，UCL越新，其處理優(yōu)先權(quán)就越高，從而有效提高UCL推薦列表的時(shí)效性；最后，UDSCT算法收斂速度較快，一旦該UCL語(yǔ)義覆蓋樹(shù)構(gòu)建完成，僅需要一次查詢操作及少量推薦列表調(diào)整操作，便可得到多樣化的UCL列表.實(shí)驗(yàn)結(jié)果證明，與基準(zhǔn)算法相比，UDSCT算法能夠獲得更好的效果，可有效滿足播存網(wǎng)絡(luò)環(huán)境的需求.

[1] Yang Peng, Li Youping. General architecture model of broadcast-storage network and its realization patterns[J]. Acta Electronica Sinica, 2015, 43(5): 974-979 (in Chinese)(楊鵬, 李幼平. 播存網(wǎng)絡(luò)體系結(jié)構(gòu)普適模型及實(shí)現(xiàn)模式[J]. 電子學(xué)報(bào), 2015, 43(5): 974-979)

[2] Li Youping, Yang Peng. New mechanism for sharing cultural big data[J]. Communications of the CCF, 2013, 5(5): 36-40 (in Chinese)(李幼平, 楊鵬. 共享文化大數(shù)據(jù)的新機(jī)制[J]. 中國(guó)計(jì)算機(jī)學(xué)會(huì)通訊, 2013, 5(5): 36-40)

[3] Gu Liang, Yang Peng, Luo Junzhou. A collaborative filtering recommendation method for UCL in broadcast-storage network[J]. Journal of Computer Research and Development, 2015, 52(2): 475-486 (in Chinese)(顧梁, 楊鵬, 羅軍舟. 一種播存網(wǎng)絡(luò)環(huán)境下的UCL協(xié)同過(guò)濾推薦方法[J]. 計(jì)算機(jī)研究與發(fā)展, 2015, 52(2): 475-486)

[4] Xing Ling, Ma Jianguo, Ma Weidong. Information Sharing Theory and Network Architecture[M]. Beijing: Science Press, 2011: 151-168 (in Chinese)(邢玲, 馬建國(guó), 馬衛(wèi)東. 信息共享理論與網(wǎng)絡(luò)體系結(jié)構(gòu)[M]. 北京: 科學(xué)出版社, 2011: 151-168)

[5] Vieira M R, Razente H L, Barioni M C, et al. On query result diversification[C] //Proc of the 27th IEEE Int Conf on Data Engineering (ICDE 2011). Piscataway, NJ: IEEE, 2011: 1163-1174

[6] Ashkan A, Kveton B, Berkovsky S, et al. Optimal greedy diversity for recommendation[C] //Proc of the 24th Int Conf on Artificial Intelligence. Menlo Park: AAAI, 2015: 1742-1748

[7] Ma Weidong, Li Youping, Ma Jianguo, et al. Empirical study of region user behaviors for Web pages[J]. Chinese Journal of Computers, 2008, 31(6): 960-967 (in Chinese)(馬衛(wèi)東, 李幼平, 馬建國(guó), 等. 面向Web網(wǎng)頁(yè)的區(qū)域用戶行為實(shí)證研究[J]. 計(jì)算機(jī)學(xué)報(bào), 2008, 31(6): 960-967)

[8] Begta?eviü F, Van Mieghem P. Measurements of the hopcount in Internet[C] //Proc of the 2nd Int Conf on Passive and Active Measurement. Berlin: Springer, 2001: 23-24

[9] Adomavicius G, Kwon Y. Improving aggregate recommenda-tion diversity using ranking-based techniques[J]. IEEE Trans on Knowledge and Data Engineering, 2012, 24(5): 896-911

[10] Carbonell J, Goldstein J. The use of MMR, diversity-based reranking for reordering documents and producing summaries[C] //Proc of the 21st Annual Int ACM SIGIR Conf on Research and Development in Information Retrieval. New York: ACM, 1998: 335-336

[11] Gollapudi S, Sharma A. An axiomatic approach for result diversification[C] //Proc of the 18th Int Conf on World Wide Web. New York: ACM, 2009: 381-390

[12] Ziegler C N, McNee S M, Konstan J A, et al. Improving recommendation lists through topic diversification[C] //Proc of the 14th Int Conf on World Wide Web. New York: ACM, 2005: 22-32

[13] Erkut E, Ulküsal Y, Yeni?eriog＇lu O. A comparison of p-dispersion heuristics[J]. Location Science, 1996, 21(10): 1103-1113

[14] Liu Ziyang, Sun Peng, Chen Yi. Structured search result differentiation[J]. Proceedings of the VLDB Endowment, 2009, 2(1): 313-324

[15] Radlinski F, Kleinberg R, Joachims T. Learning diverse rankings with multi-armed bandits[C] //Proc of the 25th Int Conf on Machine learning. New York: ACM, 2008: 784-791

[16] Javari A, Jalili M. A probabilistic model to resolve diversity-accuracy challenge of recommendation systems[J]. Knowledge and Information Systems, 2015, 44(3): 609-627

[17] Qin Lijing, Zhu Xiaoyang. Promoting diversity in recommendation by entropy regularizer[C] //Proc of the 23rd Int Joint Conf on Artificial Intelligence. Menlo Park: AAAI, 2013: 2698-2704

[18] Drosou M, Pitoura E. Dynamic diversification of continuous data[C] //Proc of the 15th Int Conf on Extending Database Technology. New York: ACM, 2012: 216-227

[19] Beygelzimer A, Kakade S, Langford J. Cover trees for nearest neighbor[C] //Proc of the 23rd Int Conf on Machine learning. New York: ACM, 2006: 97-104

ADiversifiedRecommendationMethodforUCLinBroadcast-StorageNetwork

Gu Liang, Yang Peng, and Dong Yongqiang

(SchoolofComputerScienceandEngineering,SoutheastUniversity,Nanjing211189)

(KeyLaboratoryofComputerNetworkandInformationIntegration(SoutheastUniversity),MinistryofEducation,Nanjing211189)

By introducing broadcast distribution into TCPIP, Broadcast-Storage network has clear advantages in reducing the redundant traffic in the Internet and remitting information overload problem. Uniform content label (UCL) is used to express the needs of users and help users obtain the information resources in Broadcast-Storage network. In the process of UCL recommendation, one key problem that needs to be solved is that how to improve the diversity of recommendation based on the features of Broadcast-Storage network, e.g., rich semantic information and high novelty. To solve this problem, this paper proposes a diversification method UDSCT for UCL recommendation based on semantic cover tree. UDSCT consists of two components. The first one is constructing the semantic cover tree for UCLs, which obeys some proposed invariants and considers the semantic information of UCL and the ratings from users. Besides that, new UCLs are given priority to improve the novelty of the whole UCL list. The second component is the query of diversified UCL list, which uses simple tree query and heuristic list supplement operation to obtain the diversified UCL list fast and returns specified UCL sets rapidly according to users’ need. Theoretical analysis and a series of experiments results show that, UDSCT outperforms some benchmark algorithms and is suitable for Broadcast-Storage network.

Broadcast-Storage network; uniform content label; recommendation; diversity; novelty

Gu Liang, born in 1989. PhD candidate. His main research interests include reco-mmendation systems, machine learning, and future network architecture.

Yang Peng, born in 1975. Associate professor at the School of Computer Science and Engineering, Southeast University, China. His main research interests include future network architecture, information-centric networking, distributed computing, formal theories and techniques, etc.

Dong Yongqiang, born in 1973. Associate professor at the School of Computer Science and Engineering, Southeast University, China. His main research interests include future network architecture, information-centric networking, wireless ad hoc networks, and delay-tolerant opportunistic networking (dongyq@seu.edu.cn).

2017-03-10；

：2017-05-15

國(guó)家自然科學(xué)基金項(xiàng)目(61472080，61672155)；中國(guó)工程院咨詢研究項(xiàng)目(2015-XY-04)；國(guó)家“八六三”高技術(shù)研究發(fā)展計(jì)劃基金項(xiàng)目(2013AA013503)；軟件新技術(shù)與產(chǎn)業(yè)化協(xié)同創(chuàng)新中心項(xiàng)目 This work was supported by the National Natural Science Foundation of China (61472080, 61672155), the Consulting Project of Chinese Academy of Engineering (2015-XY-04), the National High Technology Research and Development Program (863 Program) of China (2013AA013503), and the Project Funded by the Collaborative Innovation Center of Novel Software Technology and Industrialization.

楊鵬(pengyang@seu.edu.cn)

TP393；TP18