基于USDR模型的云推薦方法研究

,,,

(浙江工業大學 計算機科學與技術學院,杭州 310023)

0 引言

Web在科技的進步和信息的更新交替中進入了“2.0時代”，同時由于各種信息更新速度的加快，互聯網的數據資源也同步進入了大數據云時代，在某種程度上，網絡垃圾和無效資源也越來越多，當普通用戶想要尋找某種有用的資源時，如何在海量數據中篩選出特定的資源變成一個急需解決的問題。

搜索引擎作為人們獲取信息的渠道和關鍵，始終是各大互聯網公司的一個爭奪的熱點。當人們坐下來，打開電腦，面對龐大的互聯網世界時，第一件事情往往就是打開搜索引擎，輸入關鍵字，從而以最快的速度找到自己想要的信息。但是同樣存在明顯的缺陷，即對用戶的文化水平有一定程度的門檻，有一部分人不知道如何聯想到并精確的概括自己的目標信息，從而錯過很多實時信息；還有一些用戶并沒有絕對明確的目標，只是想瀏覽一些自己感興趣的話題，并不想要通過某些關鍵字使得信息狹隘化，因為有些關鍵字之間的共同信息領域很小；還有一些用戶對感興趣的話題并不能用幾個關鍵字去概括，因而無法定位到自己想要的數據資料。然而對數據信息的制造者而言，由于現在互聯網的競爭非常激烈，希望自己的信息被關注被采納、用戶量節節攀升也不是一件容易的事情。在這種情況背景下，數據推薦應需而生。對于用戶而言，數據推薦系統可通過云計算，在使用界面里主動跳出或許對用戶有價值的信息，從而使用戶達到自己的目的，得到更好地使用體驗；而對于制造者，數據推薦可以在一定程度上合理地把信息推銷給潛在用戶，從而增加自己的點擊量，這對于雙方而言是一個共贏的局面。

現如今，數據推薦引擎適用范圍非常廣泛，尤其值得關注的就是近幾年發展迅猛的電子商務平臺，以淘寶為例：當使用者搜索過某類商品以后，它就會儲存這個點擊數據同時進行某種用戶偏好的計算統計，結合商家的綜合排位和對淘寶平臺的廣告買位，在使用者平臺上進行個人化的反饋，使用者就會很容易的注意到自己感興趣的信息，同時商家獲取更多的點擊量和利潤，淘寶自身也獲得巨額利潤，這是一個“三贏”的結果。再如分享交互類的社交平臺，以新浪微博為例，建立推薦的機制，向用戶推薦好友的搜索熱點和關注人分享的內容，使得每一個使用者的界面都是獨特的個人化的，而且這都是使用者一手操辦，所以這些信息對于使用者而言是感興趣的有價值的。同時被關注者也可以利用這種關注量和影響力獲得經濟利益，平臺作為秩序的維持者和信息資料的擁有者也可以獲得巨大的利益。就目前而言，信息推薦系統在各大領域都產生了良好的效果和不可或缺的作用，用戶也逐漸習慣和信賴信息推薦系統，可以說這是一個成功的機制。

1 相關工作

國內外學者和研究機構從不同的視角對多源異構數據和推薦方法進行了研究。

從RSS推薦技術方向出發的代表性工作主要有：Hao Han等人[1]在RSS推送的基礎上構造網絡新聞文章內容自動提取系統，可以從新聞網頁中提取對用戶有價值的文章內容；陳鋒等人[6]對信息服務資源進行聚合需求分析，提出了一種基于RSS推送技術的信息服務內容聚合服務方式。

其次，協同過濾推送是目前主要使用的推送方式之一，協同過濾推送不僅可以實現信息的推送，而且可以根據用戶的興趣實現個性化推送。目前對協同過濾推送技術研究中具有代表性的有：郭艷紅等人[7]提出了一種基于稀疏矩陣的個性化改進策略，能夠避免用戶之間相似度不密切的關系，提高了矩陣在稀疏情況的預測準確度。李聰、梁昌勇等人[8]提出了基于領域最鄰近的協同過濾推薦算法，使數據的稀疏性得到了降低，提高了推薦準確性。

從數據傳輸方向出發的代表性工作主要是Menglan Hu等人[2]設計了一種分階段獲取云端分享數據的算法，能夠有效地控制數據的傳輸成本。國內的許富龍、劉明等人[9]進一步提出了一種基于相對距離感知的動態數據傳輸策略，采用傳感器節點到匯聚點的相對距離來計算節點傳輸概率的大小,并以此作為消息傳輸時選擇下一跳的依據。

在利用推送技術實現系統的研究中，中國科學院軟件研究所的劉鑫、陳偉[10]提出了一種基于AJAX和Server Push的web樹組件，為用戶提供了類似于在windows資源管理器中對目錄樹操作的基本功能和用戶體驗。

但以上方法均只是通過修改推送方式而實現對單一數據源進行推薦，并沒有過多考慮多源異構數據的個性化推薦問題，也沒能實現云推薦。本文提出的USDR模型面向多源異構數據，通過將用戶數據和系統數據分類來快速得到用戶和系統的不同推薦度，以實現數據的高效推薦。

2 USDR模型概念

在數據物流云推送平臺中，各類云數據數量龐大，種類繁多，根據系統服務種類大致可以分為成績查詢服務、工資數據服務、排隊服務、交通數據服務、購物信息服務、股票期貨服務、多媒體數據推送服務等。

由于是基于云推送的數據物流服務平臺，平臺中許多系統會提供類似的服務，比如3種股票軟件都通過本平臺為客戶提供金融數據推送，但是其中一款股票軟件是收費軟件，數據推送響應時間更快、推送的服務更多，但價格也是同類股票軟件中最高的。除了相同類型的服務中出現的情況，用戶數據信息之間也存在不同，用戶將會根據自己的基礎信息選擇不同的服務。比如交通數據服務中，有些用戶可能上班時間比較自由，那么他們可以選擇上下班高峰期過后的道路數據推送服務，而有些用戶需要準時到達單位，那么推送給他們當時的路況數據，可以使他們選擇在上下班高峰期避開一些擁堵路段；同樣，購物信息服務中，經濟條件好的用戶可能比較偏好奢侈品，而經濟條件一般的用戶則偏好于普通實用的商品，所以在推送數據時就會有一定的差異性，需要建立用戶和系統的關系數據模型。

當用戶請求獲取一種類型的服務時，數據物流服務平臺應該自動根據現平臺中相同類型的系統和用戶自身的數據，推送給用戶最合適的服務，這樣就既能滿足用戶的功能性需求，同時也滿足了用戶的個性化需求。

用戶數據主要可以分為用戶基礎數據、時間數據、地點數據、用戶偏好數據、歷史數據等。

系統數據主要可以分為服務類型數據(如成績查詢服務、金融股票服務等)、服務介紹以及這些服務的范圍(價格、位置)。這些系統中的數據結構多樣，類型復雜，并且有些數據是動態變化的。為了能夠有效的處理這些云數據，本文提出了USDR模型。

2.1 用戶數據模型建模

根據上文中的分析可以看出，用戶數據基本可以劃分為五類：

用戶基本數據(BasicData)：包括用戶姓名、性別、身份證、電話、出身日期、職業、畢業學校、愛好、出生地等。

時間數據(TimeData)：記錄用戶使用系統的日期和時間，同時也記錄用戶所在的時區。

地點數據(LocationData)：用于記錄用戶所在的位置，包括城市，住所和工作地。

環境數據(EnvironmentData)：記錄當日天氣情況，溫度等。

用戶偏好數據(PerferenceData)：記錄用戶的偏好情況，如運動、電影、理財、旅游、讀書等。

歷史數據(HistoryData)：記錄用戶曾經使用的系統服務，常用的理財，消費記錄以及日志數據等。

通過UML工具可以很清晰的看出用戶各類數據之間的關系，并且通過設置主鍵顯示出各條屬性的重要程度，具體如圖1所示。

圖1 用戶數據模型

系統數據服務有成績查詢服務、工資數據服務、銀行排隊服務、交通數據服務、酒店預訂服務、股票期貨服務、多媒體數據推送服務。這些系統都屬于不同的領域，這些系統的數據類型復雜程度高，數量大，若不進行建模將很難進行云推送，在對系統數據進行建模之后也更利于數據的個性化推薦，本章選擇具有代表性的成績查詢服務系統和多媒體數據服務系統進行系統數據模型建模。

2.2 系統數據模型建模

2.2.1 成績查詢服務系統

成績查詢服務系統主要為在校學生提供每個學期結束之后的成績查詢服務，首先最高層應該為用戶的類型，為本科生、碩士研究生還是博士研究生，確定了學生類型之后需要到各個學院中查詢數據，由于很多學院中的必修課是相同的，所以為了避免重復的查詢接下來模型中將分為必修課和選修課以及實踐活動。最終得到各門功課的成績。最后學生得到了該門課的成績之后，還需要對老師進行評價。

系統數據模型再結合用戶數據模型可以看出，在用戶數據模型中的用戶偏好，畢業院校就可以更加精確地給用戶推送推薦數據，同時這種分層的結構能使云推送更加高效。

2.2.2 多媒體數據服務系統

多媒體數據服務相對于成績查詢服務將會復雜很多，多媒體數據服務各種系統中，可以將數據的類型分為文字數據、音頻數據、視頻數據、圖文數據等。根據多媒體服務的不同類型和用戶的偏好將分為新聞，體育，娛樂，游戲，電影等，然后再對具體需要推送的數據進行分類。

系統數據模型主要元素包括基本數據、功能數據和其他數據：

基礎數據(SerBasicData)：主要是對系統服務的基本描述，包括服務提供商，服務類型，服務ID，服務名稱，服務簡介等數據。

功能數據(SerFunctionData)：主要對服務中的功能性參數進行描述，即服務輸入輸出參數，服務的接口參數，最終服務執行結果等。

其他數據：主要有些系統需要定位數據，天氣數據等其他因素。

3 基于USDR模型的云推薦算法

傳統的推薦算法有皮爾遜相關系數法、向量余弦法、斯皮爾曼相關系數法等等，在不同的領域中，需要選取不同的相似度計算方法。由于云數據的特殊性，本文重新設計了基于USDR的個性化云推送推薦算法，根據用戶、系統的相似值來計算推薦的系統數據。本章的模型中存在用戶數據和系統數據兩種數據類型，針對該模型設計了基于用戶的云推薦算法和基于系統的云推薦算法。

3.1 基于用戶的云推薦算法

基于用戶的云推薦算法主要目的在于計算兩個用戶的相似度，本算法中主要使用用戶行為相似度來計算用戶的類似喜好。本算法由兩部分組成：一部分采用用戶基礎屬性來決定用戶的相似程度，通過計算得出的基本屬性差異越小，則相似程度越高；第二部分是偏好、位置和服務記錄數據等，通過查看用戶的地理位置和歷史感興趣的系統的數值，該數值越大，則用戶之間的相似程度越高，最后計算總相似度。

3.1.1 基礎屬性相似度

基礎屬性一般都是數值類型，如性別，年齡，畢業院校等。對于數值型屬性，只需要計算絕對值之差|D|=|Attr1-Attr2|。對于名稱型的基礎數據，一般取值類型比較單一，就可以采用二進制編碼的方式來表示，比如性別：男、女，分別對應00、01。其他以此類推。最終將用戶全部名稱型數據編碼串聯起來，行成一個二進制串。

不同的數值型屬性的絕對值最大與最小的差距為[α1，αn]，然后把這個區間劃分為n-1個相等的區間{[α1，α2],[α2，α3],...,[αn-1，αn]}，對每個區間給予相應的數值{0,1,2,3...n}，當用戶的數值型屬性絕對值落在某個區間時，即可得出屬性間的距離Dbnum。對于名稱型屬性，通過確定編碼位數n，然后將每個取值通過格雷編碼，然后依次鏈接起來，最后通過計算海明距離，得到名稱型屬性距離DH。定義用戶A和B，每個基礎屬性的權重值為wi，則所有屬性權重值滿足：

(1)

對于數值型的屬性距離Dbnum，根據上面的解釋，定義不同的取值區間：

若α∈[α1，α2]，則dbnum=0；

若α∈[α2，α3]，則dbnum=1；

.......

若α∈[αn-1，αn]，則dbnum=n-1；

數值屬性的距離計算為：

(2)

對于名稱型的屬性距離Dbnum，則對不同的取值進行編碼。將用戶的全部名稱屬性編碼串聯起來，形成二進制串At；采用At的海明距離來計算用戶名稱屬性的距離。

DH=wDhm(DbnumA,DbnumB)

(3)

最終得到2個用戶A與B的基礎屬性距離：

(4)

通過差值DA-B可以看出，DA-B越小，相似度則越大，DA-B越大，則相似度越小。

3.1.2 用戶偏好相似度

若給定用戶A和B，N(A)表示用戶A的偏好相似度集合，N(B)表示用戶B的偏好相似度集合(如時間，位置，系統使用情況等)，運用余弦公式相似度計算公式：

(5)

表1 用戶偏好表

從表1的用戶偏好可以得出：用戶A對{成績，金融，酒店}方面的系統感興趣，用戶B對{成績，工資}方面的系統感興趣，所以可以計算出用戶A和用戶B的偏好相似度，如下所示：

用余弦公式計算用戶間兩兩的相似度之后，算法通過綜合分析基礎數據相似度和用戶偏好數據相似度后，再進行推薦，推薦度公式如6所示：

(6)

公式中，DA-B為基礎數據的差值，N(i)表示對項目i有偏好的用戶組，Re(u，k)表示存在與用戶A偏好類似的用戶組。Wab描述用戶A與用戶B的相似度，ybi表示用戶B對項目i的偏好程度。

3.2 基于系統的云推薦算法

基于系統的云推薦算法和基于用戶偏好的推薦算法有些類似，主要通過以下兩步完成：首先計算系統之間的相似程度，然后根據相似度生成系統推薦列表。

根據余弦公式可得系統的相似度：

(7)

(8)

假設有a,b,c,d,e5個系統，同時存在A,B,C,D,E5位用戶，對每位用戶偏好的項目用矩陣表示：

用戶A：偏好a，b，c系統，用矩陣表示為：

用戶B：偏好a，b，d系統，用矩陣表示為：

用戶C：偏好a，d系統，用矩陣表示為：

用戶D：偏好b，c，e系統，用矩陣表示為：

用戶E：偏好a,e系統，用矩陣表示為：

將A,B,C,D,E矩陣全部相加之后可得矩陣S，S[i][j]則表示同時對系統i和系統j都偏好的用戶數量。

得到相似度矩陣之后，通過公式(7)計算用戶a對系統i的推薦度：

Recommdsys(a,i)=∑i∈N(u)∩S(i,k)wij

(9)

公式(9)中表示當前用戶的偏好集合，S(i，k)表示與系統i比較相似的K個系統的集合，wij是系統i與系統j的相似度。將該推薦度從大到小排列，采用TOP-N的方式取前N個系統推薦給用戶。

3.3 基于USDR的云推薦算法運行過程

為了達到更好的用戶體驗，為用戶提供個性化的推薦服務，基于USDR模型運行過程如圖2所示，首先根據用戶注冊數據為用戶建模，其次為平臺中每個系統進行建模，當模型構建完成之后，分析用戶注冊數據中的基礎屬性數據，計算出基礎屬性相似度，再算出用戶偏好屬性相似度，最后同理算出基于系統的云推送推薦算法，最終為用戶推送推薦數據。

通過分別計算用戶和系統數據的推薦度會導致結果比較粗糙，為了使得云推薦算法更加精確，將用戶數據推薦度加入到系統數據推薦度中，得出綜合推薦度列表，將使推薦度的結果更加準確和方便，更加方便于下一步的云推送。如何使用基于USDR模型的云推薦算法得出用戶推薦度列表的具體流程如圖3所示。

圖2 基于USDR模型運行過程

圖3 基于USDR模型的云推薦算法運行流程

1)查看用戶歷史記錄數據表，若用戶的歷史數據為空，則說明為新注冊用戶，那么就執行步驟2)，否則執行步驟5)；

2)查看用戶基礎數據中的好友表，若有好友，則執行步驟3)，若無，則執行步驟4)；

3)使該用戶分別與每位好友分別用公式DA-B進行計算，得出相似度，查看相似度在設定的權重值內的用戶與該用戶關系最密切的好友，執行步驟4)；

4)使用公式(4)計算所有在權重值范圍內的好友的偏好推薦度Recommenduser,加入用戶推薦列表中，執行步驟5)；

5)使用公式(7)計算的歷史數據表中每個系統的推薦度RecommendSystem，將這些系統放入推薦列表，執行步驟6)；

6)將步驟4)和步驟5)中的Recommenduser和RecommendSystem分別平方，再求和開根號得出綜合推薦度：

Recommendgeneral=

(10)

7)根據綜合推薦度，加入到綜合推薦度列表。

4 案例分析與實驗

本文使用云推薦方法在安卓和iOS中進行了測試，云數據來源于成績系統，工資系統和微影視系統，采集到數據后將數據的主要權重值分為：用戶權限，用戶登錄時間，用戶發布/訂閱的模式(一對多/一對一)，用戶登錄數量，傳輸數據量。權重w是經過綜合考慮而確定的。目前數據物流云推送平臺中存在的系統如圖4所示。

圖4 用戶登錄平臺選擇偏好的系統

用戶在手機端進行注冊，主要需要將用戶基礎數據和偏好信息填寫完畢，方便接下來的云推薦系統給用戶推薦個性化內容。當用戶基礎數據、偏好數據和系統數據都進行綁定之后，得到如圖5所示的界面，此時平臺已經根據云推薦算法將推薦數據放入推薦列表中，等待下一步的云推送。

圖5 用戶功能頁面

5 算法有效性分析

為衡量本文提出的USDR云推薦算法的能力，從算法效率、系統數量、平均傳輸率，通信率，靜置時流量等方面來對算法有效性進行評估。

首先測試單機中的普通推薦算法和云推送平臺中的推薦算法進行比較，單機使用Windows8 64位操作系統，8GB內存，10臺虛擬機同樣使用Windows8 64位操作系統，8GB內存，分別計算虛擬數據量為10～100萬的數據量。

圖6 單機與云平臺中推薦算法效率對比

為了得到當在數據量相同時運算速度與虛擬機數據的關系，實驗中使用50萬的數據量，分別測試虛擬機數量為5～10臺時云推薦算法運行的效率。

圖7 虛擬機數量不同對推薦算法的影響

平均傳輸率是指數據傳輸平均的“倍速”數。單倍數傳輸時，即可記為1倍速，普通推送的平均傳輸率為10倍速，在數據量相同時，結果如表2所示。

表2 平均傳輸率數據表 %

通信率是指單位時間內用戶與云推送平臺的通信次數，測試用戶是否愿意使用該平臺進行數據推送,并同時測試了在通信次數高的時候會不會產生其他問題(結果如圖8所示)，普通的推薦算法通信率基本不變是由于在推送任務隊列消息的整個過程中一直都會向服務器發送請求，而本文提出的云推薦方法處于信息收集階段，隨著系統的運行，任務數量增多，優勢就逐漸顯示出來，在任務數越多時，花費的通信量反而變少。

圖8 通信率變化圖

靜置時流量是指在手機靜置時由于推送而產生的額外流量，測試云推送平臺是否會因為通信率的改善而產生大量流量，分別使用云推送平臺和傳統推送平臺進行測試(如表3所示)，實驗結果表明云推送平臺在移動設備靜置時間較長情況下流量消耗少于傳統推送平臺。

表3 靜置時流量對比

6 結束語

本文針對傳統的推送方式在推送多源異構數據時遇到的效率低，實時性差等問題，設計了面向多源異構數據的云推送平臺來滿足云推送環境，并通過USDR模型解決了多源異構數據推送問題，滿足了用戶需求。

然而，該平臺能否滿足所有的用戶需求，能否供海量用戶使用還需要進行驗證，云推送平臺本身的性能提升以及各種演化方式將是本文下一步的研究內容。相信隨著這些關鍵問題的攻破，面向多源異構數據的云推送平臺將為用戶帶來更好的推送體驗。