播存網絡環境下UCL推薦多樣性優化算法

顧 梁 楊 鵬 董永強

(東南大學計算機科學與工程學院 南京 211189) (計算機網絡和信息集成教育部重點實驗室(東南大學) 南京 211189) (guliang@seu.edu.cn)

播存網絡環境下UCL推薦多樣性優化算法

顧 梁 楊 鵬 董永強

(東南大學計算機科學與工程學院 南京 211189) (計算機網絡和信息集成教育部重點實驗室(東南大學) 南京 211189) (guliang@seu.edu.cn)

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

播存網絡；統一內容標簽；推薦；多樣性；時效性

互聯網在給人們帶來豐富信息資源的同時，自身流量也與日俱增.造成互聯網協議流量激增的主要原因之一是互聯網的內容訪問日益呈現出冪律分布的特性，即大量用戶對熱門資源的重復性訪問耗費了大量的數據傳輸帶寬.現有互聯網架構和內容傳輸技術體系越來越難以為高效信息共享提供有效的支持.

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

Fig. 1 The model of Broadcast-Storage network[3]圖1 播存網絡模型[3]

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

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

然而，在播存網絡環境中，傳統結果集合多樣性優化具有自身的一些局限性，具體表現在3個方面：

1) 難以有效確定加權參數.傳統多樣性優化方法往往需要設定加權參數以在精度及多樣性之間取得平衡.通常，數據集的特征對加權參數的確定有重要影響.而在播存網絡環境中，由于UCL分發較為頻繁，數據集不斷變化，很難確定一個恰當的加權參數能夠持續保證UCL推薦的多樣性及精度.

2) 缺乏UCL時效性處理機制.播存網絡環境中UCL包含信息資源的摘要信息，與信息資源一一對應，更新速度快，具有很強的時效性.傳統多樣性優化方法很少考慮優化對象的時效性，容易導致優化后的集合中包含比較陳舊的UCL，降低用戶體驗.

3) 無法快速產生優化結果.UCL數目巨大，在播存網絡持續動態運行時，如何基于大量的UCL數據快速及時地為用戶提供多樣性優化結果尤為重要.傳統多樣性優化方法通常需要大量的迭代運算，收斂較為緩慢，無法高效滿足播存網絡的需求.

針對上述3個問題，本文基于語義覆蓋樹提出了一種適用于播存網絡環境的UCL推薦多樣性優化算法(UCL diversification based on semantic cover tree, UDSCT)，能夠克服傳統多樣性優化方法在播存網絡環境中存在的不足，并可充分利用UCL語義信息及非語義用戶評分信息，在保證UCL推薦精度的前提下，優化UCL推薦結果的多樣性.

1 相關工作

目前，播存網絡的相關研究主要圍繞互聯網訪問特征、播存網絡的基本架構、UCL的格式設計與標引及播存網絡環境中的UCL個性化推薦機制等幾個方面展開.

文獻[7]提出用戶對Web網頁的訪問是由用戶需求行為確定的一個隨時間演化的復雜雙模式二分網絡，并通過實證研究分析發現，其入度分布呈現出典型的無標度特征和集聚現象.文獻[8]對互聯網中用戶訪問Web網頁時所產生的路由跳數進行了研究與測量，得到每條訪問記錄所需的平均路由跳數為13.11.文獻[7-8]為播存網絡模型提供了理論基礎與數據支撐.

文獻[4]對播存網絡的原理與基本模型進行了系統詳細的闡述.文獻[2]進一步對播存網絡模型進行了研究，給出了播存網絡的普適模型及其數學描述，并重點研究了4種實現模式，為播存網絡提供了嚴格的定義及規范.播存網絡中，用戶通過UCL判斷是否需要某條信息資源.文獻[3]針對播存網絡的特點，提出一種播存網絡環境下的UCL推薦方法，可根據用戶的歷史訪問記錄建立用戶特征模型，精確預測用戶可能感興趣的UCL.然而，文獻[3]未考慮UCL推薦列表的多樣性，本文在文獻[3]的基礎上重點研究UCL推薦的多樣性優化問題.

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

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

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

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

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

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

2 UDSCT算法詳細描述

本節首先描述基于語義覆蓋樹的推薦列表多樣性優化算法的總體流程，然后給出算法相關的形式化定義，最后詳細描述具體的UCL語義覆蓋樹構造算法及UCL推薦多樣性優化算法.

基于語義覆蓋樹的UCL推薦列表多樣性優化算法的總體流程如圖2所示.該算法首先根據時間順序構建時間敏感的UCL語義覆蓋樹，然后基于該樹通過查詢操作及補充算法獲得多樣化的UCL列表，最后將該UCL推薦給用戶并根據用戶請求響應聚焦請求.

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

2.1UDSCT算法相關定義

為更清楚地描述該問題及其解決算法，本節給出了相關定義.

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

(1)

在獲得當前最優UCL子列表后S*，系統將其呈現給用戶，用戶可能對其中的某一個UCL感興趣，并希望得到一個與該UCL相關度更高的子列表.本文將這個過程定義為聚焦，形式化描述如下：

定義2. UCL聚焦.在定義1的基礎上，聚焦操作根據用戶的反饋查詢當前最優UCL列表S*中更符合用戶興趣的子列表S′，使得：

(2)

以上定義均基于語義覆蓋樹實現，語義覆蓋樹由覆蓋樹發展演化而來，覆蓋樹最初由Beygelzimer等人在文獻[19]中提出，用以快速查找最近鄰.覆蓋樹為分層的樹數據結構，樹中的每一層均覆蓋其下面所有的層，樹中的層數用整數l標示，且l從上往下逐步減小.對于給定的一個項目(如UCL)列表S，S中的每個項目均對應于覆蓋樹中的至少一個節點.

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

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

2) 覆蓋性.對于每一個p∈Cl，有且僅有一個q∈Cl-1作為p的父節點，且q滿足d(p,q)≤1/2l-1.

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

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

但是，覆蓋樹在解決播存網絡環境下UCL推薦多樣性優化問題時仍然存在著2個較為明顯的缺陷.1)覆蓋樹并不考慮節點的內容語義信息，無法有效利用UCL所包含的豐富語義信息；2)在UCL推薦多樣性優化過程中，UCL的時效性對用戶體驗有著重要影響，覆蓋樹缺乏針對時效性的處理機制.

為此，本文對覆蓋樹進行相應擴展，設計了一種時間敏感的UCL語義覆蓋樹.

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

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

2) 時效性.對于所有的UCLp∈Ci，令UCLs為p在l-1層的父節點，則有ts≤tp，其中ts，tp分別表示UCLs和p的時間.

上述條件中，時效性保證了每個父節點均比其子節點更加新穎，從而使得從上往下遍歷樹尋找匹配用戶興趣時能夠優先選擇時效性更高的UCL.而語義聚集性則確保了在構建樹的過程中，父節點與子節點之間的語義相似度更高，間接地促進了UCL列表的多樣性效果.

2.2UDSCT算法描述

在介紹完相關基本概念后，本節將繼續介紹如何完成UCL語義覆蓋樹的構造、如何基于該樹完成UCL推薦多樣性優化以及如何進一步快速響應用戶的聚焦請求.

2.2.1 UCL語義覆蓋樹構造

UCL語義覆蓋樹采用自頂向下、逐個插入UCL的方式構造，首先選擇最新的UCL作為樹的根，然后遵循“新穎優先”的原則插入其他UCL.需要說明的是，在插入過程中，必須嚴格保證3個約束條件不被違背.構造的詳細過程如算法1所示.

算法1. UCL語義覆蓋樹的構造.

輸入: 待優化UCL列表I；

輸出: 列表I對應的UCL語義覆蓋樹.

/*按照時間順序對I中的UCL進行排序，依次調用函數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()是基于文獻[19]中的插入算法，但由于該算法僅可用于構建基本覆蓋樹，故需要對其進行適當改進，在構建過程中除了需要遵循定義3中的約束條件，還需兼顧定義4中的條件.具體而言，算法1首先根據時間順序將已有UCL列表進行排序，然后依次調用插入函數Insert(itemp,Ql,levell)(行①～⑧)，該操作保證了構造過程滿足了時效性約束條件，最先插入的最新穎的節點作為樹的根.插入函數以待插入的UCL、待插入的層數以及該層已含有的UCL作為輸入參數，然后逐層遞歸地檢查直到發現滿足分離性約束條件的層數(行⑨～).在第一次找到該層之后，該函數將上一層中滿足覆蓋性條件的UCL節點識別出放入待插入節點的父節點候選節點集合(行).最終，該算法依次計算待插入UCL的特征向量與父節點候選節點集合中的節點的特征向量的語義關聯程度，選出關聯度最高的UCL節點作為待插入節點的最終父節點(行).

在構造UCL語義覆蓋樹的過程中，語義聚集條件使得UCL節點總是選擇與其語義最為相關的UCL節點作為父節點，這進一步加強了同層節點之間的多樣性，并為之后的UCL聚焦操作提供了重要基礎.

2.2.2 多樣化UCL結果集合查詢

UCL語義覆蓋樹中的每個節點都對應了UCL推薦列表中的一個UCL，當用戶確定想要獲取的UCL數目后，只需逐層遍歷樹的節點，獲得合適的UCL列表.具體而言，層數越低，該層的UCL之間距離越大，該層的多樣性便越高.下降搜索過程如算法2所示.

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

輸入: UCL列表I對應的語義覆蓋樹T、結果子列表中UCL數目k；

輸出: 包含k個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)；

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

算法3. 貪婪補充算法.

輸入: 基礎子列表Sb、候選集合C、結果子集合中UCL數目k；

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

①S*=Sb；

② While (|S*|

④S*=S*∪{p}；

⑤ EndWhile

⑥ returnS*.

算法4. 置換補充算法.

輸入: 基礎子列表Sb、候選集合C、結果子集合中UCL數目k；

輸出: 包含k個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；

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

2.2.3 UCL聚焦響應算法

在將初步多樣性優化后的UCL列表呈現給用戶后，用戶會對其進行瀏覽并會根據自身興趣及偏好查找自己感興趣的UCL.假設該用戶對某個UCL感興趣，并想進一步了解與該UCL更加相關的一些UCL，此時，此時將調用UCL聚焦響應算法，算法的處理流程如算法5所示.

算法5. UCL聚焦響應算法.

輸入: UCL列表I對應的語義覆蓋樹T、用戶指定的UCLq、子列表中UCL數目k；

輸出: 包含k個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首先根據用戶請求，從已構造的UCL語義覆蓋樹中逐層查詢用戶感興趣的UCLq(行①～⑦).需要注意的是，根據覆蓋樹的特性，相同的UCL可能會在樹中出現多次，為了找到恰當的節點，算法需要找到第1個帶有非自身子節點的q(行③).一旦找到該節點，算法并對該覆蓋樹進行剪枝處理，僅保留以q為根節點的子樹(行⑧).最終，基于該子樹，便可以調用子集合查詢算法(算法2)獲取與該UCL更加相關的UCL列表.

3 算法分析

本節將分析UDSCT算法復雜度并總結、證明其具有的相關性質.

3.1算法復雜度

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

3.2算法性質

基于語義覆蓋樹具有3條重要性質.首先，對于待插入樹的UCLi而言，一旦其在樹中的所屬層數l確定，則在l-1層中必定有且僅有一個UCL可以當作UCLi的父節點.

證畢.

下面證明UCL語義覆蓋樹構造算法的正確性.

定理2. UCL語義覆蓋樹構造算法滿足定義4中的所有約束條件.

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

證畢.

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

定理3. 基于UCL語義覆蓋樹進行聚焦操作，獲得的子樹同樣滿足5個限制性約束條件.

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

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

與此同時，在樹T′中，其新的層數為L′=n-m，因此可得:

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

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

證畢.

4 性能評估

4.1數據集及實驗過程

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

實驗過程如下：實驗隨機選擇100名用戶進行測試，首先通過預測算法預測用戶的初步推薦列表，然后采用不同的推薦列表多樣性優化算法優化列表，最后統計測試不同算法所取得的相關性能指標并進行對比，針對對比結果給出相應分析.為保證實驗結果的穩定性，上述過程均重復10組，本文所述結果為10組結果的平均值.另外，在實驗過程中，本文采用PCC值度量基本距離，而對于語義距離，本文基于用戶對電影的語義標簽信息進行計算.

4.2評估標準

為全面測試UDSCT算法的性能，本文將圍繞UCL列表平均精度、列表多樣性(包括列表內部元素差異度及列表類別多樣性)、列表時效性、算法運行時間等指標進行測試.

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

(3)

其中,n表示列表中的UCL個數，rj表示第j個UCL的評分.

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

(4)

其中，ui表示第i個UCL，sim表示相似度函數，LID值越高，說明列表的多樣性越好.

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

(5)

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

(6)

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

4.3實驗結果

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

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

4.3.1 UCL推薦多樣性

本部分將根據UCL推薦列表內部元素差異度LID及列表類別多樣性LCD兩個指標測試不同算法的多樣性優化效果.

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

Fig. 3 LID comparison of different methods when k=10圖3 k=10時不同方法LID對比

Fig. 4 LID comparison of different methods when k=15圖4 k=15時不同方法LID對比

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

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

Fig. 5 LCD comparison of different methods when k=10圖5 k=10時不同方法LCD對比

k=10時，LCD的取值區間為[1.998,10].當所有UCL屬于同一個類別時，LCD取值最小，根據式(5)可知，LCD=1+12+…+129≈1.998；當所有UCL均屬于不同類別時，LCD取值最大，LCD=10.k=15時，計算過程同上.

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

Fig. 6 LCD comparison of different methods when k=15圖6 k=15時不同方法LCD對比

4.3.2 UCL推薦精度

表1描述了不同算法對于UCL推薦精度ALP的影響.從表1可以觀察到，NODIV算法的ALP值保持不變，其他算法的ALP值隨著候選集合的變大而逐步降低.這是由于NODIV算法僅根據預測分數對UCL列表排序，而候選集合的增大并不會對前k個UCL的預測分數及排序產生影響，但在其他算法中，一些預測評分較低但會提高列表多樣性的UCL可能出現在前k個位置，從而使得ALP值下降.

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

從表1還可以發現，基于UCL語義覆蓋樹的2種算法在推薦精度方面均優于UDCT和MSDIV算法，且候選集合愈大，優勢愈明顯.此外總體上而言，所有優化算法在k=15時取得的ALP值均低于k=10時，這是因為推薦結果集合較大時，若高預測評分數量有限，一些低預測評分UCL將出現在推薦集合中，而當播存網絡環境持續長時間運行后，高預測評分UCL數量會逐步增加，這種現象會得到有效緩解.

4.3.3 UCL推薦時效性

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

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

4.3.4 算法運行時間

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

Fig. 7 Running time comparison of different methods when k=10圖7 k=10時不同算法之間的運行時間對比

Fig. 8 Running time comparison of different methods when k=15圖8 k=15時不同算法之間的運行時間對比

需要指出的是，由于NODIV算法中無多樣性優化操作，故不參加本部分實驗.

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

從圖7、圖8還可以發現，基于普通覆蓋樹的UDCT算法比本文所提的UDSCT算法(包括GUDSCT,SUDSCT)耗時更少，深入分析可知，這是因為UDCT算法在構建樹的過程中無需排序操作及語義關聯運算，節省了部分時間.同時SUDSCT算法耗時比GUDSCT稍久一點，這也不難理解，因為前者在查詢后的少量調整過程中仍需要較多的迭代置換嘗試.

4.3.5 UCL聚焦操作

在驗證UCL聚焦操作性能時，由于該操作主要基于樹的裁剪操作，其多樣性、精度、時效性等指標取決于當前已構建的UCL語義覆蓋樹，相關性能已在上述4個實驗部分測試，本部分實驗主要關注UCL聚焦操作的響應時間，實驗結果如圖9所示:

Fig. 9 Response time of UCL Focus圖9 UCL聚焦響應時間

圖9主要包括了6組實驗結果，橫坐標為響應時間，縱坐標為待聚焦的UCL所包含的相關UCL數目，每組實驗重復5次，圖9所展示的為5次的平均結果.觀察圖9可以發現，無論相關UCL數目多少，UCL聚焦操作的響應時間總能保持在2.3 ms以內，UCL數目對響應時間僅有輕微影響.分析可知，這是因為在不同的條件下，算法需要進行的定位、剪枝操作基本一致，耗時也差異不大.圖9結果表明UDSCT中基于樹查詢的UCL聚焦操作可快速響應用戶的操作請求.

5 結 論

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

[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)(楊鵬, 李幼平. 播存網絡體系結構普適模型及實現模式[J]. 電子學報, 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)(李幼平, 楊鵬. 共享文化大數據的新機制[J]. 中國計算機學會通訊, 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)(顧梁, 楊鵬, 羅軍舟. 一種播存網絡環境下的UCL協同過濾推薦方法[J]. 計算機研究與發展, 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)(邢玲, 馬建國, 馬衛東. 信息共享理論與網絡體系結構[M]. 北京: 科學出版社, 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)(馬衛東, 李幼平, 馬建國, 等. 面向Web網頁的區域用戶行為實證研究[J]. 計算機學報, 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

國家自然科學基金項目(61472080，61672155)；中國工程院咨詢研究項目(2015-XY-04)；國家“八六三”高技術研究發展計劃基金項目(2013AA013503)；軟件新技術與產業化協同創新中心項目 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