基于用戶興趣三維建模的個性化推薦算法

王冰怡,劉 楊,聶長新,田 萱

(北京林業大學信息學院,北京100083)

基于用戶興趣三維建模的個性化推薦算法

王冰怡,劉 楊,聶長新,田 萱

(北京林業大學信息學院,北京100083)

針對推薦系統中用戶的個性化需求,提出一種基于用戶興趣三維建模的個性化推薦算法。通過分析用戶行為數據,從興趣廣度、興趣深度和興趣時效3個角度分析用戶的興趣構成,對用戶興趣進行三維建模,并在此基礎上,逐步添加維度,設計用戶之間興趣相似度的三級計算方法。在真實推薦系統數據集上的實驗結果表明,用戶興趣三維模型比一維模型、二維模型更能準確地表征用戶興趣,基于用戶興趣三維建模的個性化推薦算法能夠提高個性化推薦的準確率。

個性化推薦;用戶興趣三維建模;興趣廣度;興趣深度;興趣時效;用戶興趣相似度

1 概述

隨著互聯網信息的爆炸性增長,信息超載目前已成為網絡用戶面臨的一個嚴重問題,用戶難以從海量的在線資源中獲取與用戶相關或感興趣的信息。個性化推薦系統是解決該問題的一個有力工具,個性化推薦系統[1]能夠根據用戶的歷史行為信息建立用戶興趣模型,利用系統中的推薦算法向用戶推薦其未曾產生過行為的物品。在個性化推薦系統中,用戶興趣建模是個性化推薦的基礎[2],很大程度上決定著推薦系統的質量。

當前用戶興趣模型的表示大致分為2類:基于關鍵詞的興趣模型[3]和基于語義的興趣模型[4]。基于關鍵詞的興趣模型以向量空間模型表示法[5]為主,利用用戶興趣數據的特征項及其所對應的權值來表示用戶興趣模型,例如,文獻[6]針對現有的用戶模型不能根據用戶自身興趣實現推薦的問題,通過建立用戶集、資源集,結合用戶的行為特點及權重,提出了基于用戶行為的興趣模型;文獻[7]通過用戶關于某個主題的生成概率來反映用戶對該主題的喜好程度,提出了基于主題模型的用戶興趣模型。基于語義的興趣模型往往建立在本體技術之上,使用戶興趣模型更加富有語義信息,加強了用戶模型表征力度,被認為是向量空間用戶模型的一種完善。例如,文獻[8]利用用戶訪問量,采用改進的相似度算法,實現用戶分類建立用戶興趣模型;文獻[9]基于用戶知識本體和概念向量構建興趣模型,實現了用戶興趣的個性化語義描述。

上述研究在用戶建模的過程中,對用戶興趣的描述大都只停留在一維上,如利用用戶對資源的訪問量來表征用戶興趣。雖然這些研究從不同角度提高了對用戶描述的精確度,但仍然缺乏對用戶興趣的深入分析和準確建模,系統需要收集更詳細、有效的用戶信息來描述用戶興趣[10]。例如用戶興趣范圍會隨著時間而變化,因此系統就要收集用戶搜索的相關時間信息。傳統的研究沒有將時間因素加入到用戶興趣模型的構建中,導致用戶特征描述的不準確性,最終影響了推薦效果。

為解決這一問題,本文通過從用戶的搜索行為中獲取用戶數據,從用戶興趣廣度、興趣深度、興趣時效這3個角度刻畫用戶興趣三維模型,設計用戶之間相似度的三級計算方法,提出基于用戶興趣三維建模的個性化推薦算法,并將該算法應用到個性化推薦系統中,找出目標用戶的最近鄰,根據最近鄰的興趣預測目標用戶的興趣,進而對目標用戶產生動態推薦。

2 個性化推薦中的用戶興趣三維建模方法

2.1 用戶興趣數據的獲取

要實現個性化推薦,系統必須知道用戶的個性化需求,這就需要獲取、分析用戶信息,建立合適的用戶興趣模型。用戶信息可以分為用戶背景信息和用戶訪問信息[11],用戶背景信息包括用戶職業、年齡、居住地等,可以有效解決個性化推薦初期用戶數據較少情況下無法做出精確推薦的“用戶冷啟動”問題;用戶訪問信息主要包括用戶瀏覽行為和用戶搜索行為,是建立用戶興趣模型的主要來源[12]。本文提出的用戶興趣三維模型主要從用戶的搜索行為中獲取用戶數據。因為在用戶的搜索行為中:

(1)用戶搜索的目標、搜索的時間、瀏覽的時間、拖動滾動條的次數等行為數據能夠體現不同年齡、性別、地區的用戶興趣;

(2)隨著時間變遷,用戶搜索目標的轉移往往意味著用戶興趣在動態變化;

(3)用戶對搜索目標的點擊和瀏覽頻度在一定程度上反映了用戶的興趣。

通過對用戶的搜索行為進行分析,就能描述出用戶在某一時間段內的興趣,進而更準確地建立用戶興趣模型。

本文主要依據推薦系統中的搜索日志來分析用戶興趣。一般來說,搜索日志中包括用戶的ID,用戶搜索的物品i,用戶每次搜索物品i時的時刻ti。用戶u對物品i的搜索日志Log(u,i)形式化定義為:

2.2 用戶興趣三維模型

心理學上認為,人類的興趣與其行為有著很大的關聯[13]。興趣可以由用戶的行為判斷出來。根據直覺可以得到用戶搜索行為和用戶興趣的3個基本結論:

(1)用戶對其搜索的物品感興趣:

(2)用戶搜索某一物品的次數越多,對該物品就越感興趣:

(3)隨著時間的推移,用戶對某物品的興趣會減少。

基于這3個結論,本文提出用戶興趣廣度、興趣深度、興趣時效的概念,從搜索日志中獲取體現用戶興趣的數據,并利用用戶興趣的廣度(X)、深度(Y)、時效(Z)來構建用戶興趣三維模型,如圖1所示。

圖1 用戶興趣三維模型

2.2.1 用戶興趣廣度

在用戶興趣三維模型中,本文用用戶興趣廣度來描述用戶的興趣范圍。在搜索日志Log(u,i)中可以統計出用戶u搜索的物品集合,這個集合在一定程度上描述了用戶感興趣的物品范圍,用它來標記用戶u的興趣廣度,記為Width(u)={i1,i2,…}。

直覺上,用戶u,v興趣廣度交集元素個數越多,即共同搜索的物品越多,用戶u,v的興趣相似度越高,在對目標用戶u進行個性化推薦時,更傾向利用用戶v的興趣來預測目標用戶u的興趣。

根據這一直覺,定義第1個啟發式規則:

啟發式規則1設用戶u,v,t的興趣廣度分別為Width(u),Width(v),Width(t),若|Width(u)∩Width(v)|＞|Width(u)∩Width(t)|,則用戶興趣相似度Wuv＞Wut。

2.2.2 用戶興趣深度

在用戶興趣三維模型中,本文用用戶興趣深度來表示用戶u對物品i的感興趣程度。在搜索日志Log(u,i)中,可以統計出用戶u對物品i的搜索次數,這個搜索次數在一定程度上反映了用戶u對物品i的感興趣程度。用這個搜索次數作為用戶u對物品i的興趣深度,記為Depthui。

直覺上,Depthui和Depthvi差距越小,即用戶u,v對物品i的搜索次數越接近,用戶u,v的興趣相似度越高,在對目標用戶u進行個性化推薦時,更傾向利用用戶v的興趣來預測目標用戶u的興趣。根據這一直覺,定義第2個啟發式規則:

啟發式規則2設用戶u,v,t對物品i的興趣深度分別為Depthui,Depthvi,Depthti,若|Depthui-Depthvi|＞|Depthui-Depthti|,則用戶興趣相似度Wuv＞Wut。

2.2.3 用戶興趣時效

在一般情況下,用戶的興趣會隨著時間而變化。事實上,隨著用戶u搜索物品i的時間推移,用戶u對物品i的興趣是衰減的[14]。在用戶興趣三維模型中,本文用用戶興趣時效來表示和時間有關的興趣衰減。在搜索日志Log(u,i)中,可以統計出用戶u搜索物品i的最后時間,記為Tui。直覺上,在當前時刻T,若用戶u剛剛不久前才搜索過物品i,即Tui距離當前時間T越近,用戶u對物品i的興趣時效就越大。將用戶u對物品i的興趣時效記為Timeui,Timeui可表示為:

其中,α為平衡參數。考慮到,如果用戶u經常搜索物品,對物品i來說,|T-Tui|偏小,但這只能說明用戶興趣變化得快,并不意味著用戶u對用戶i的興趣時效大,因此,本文定義了平衡參數α來消去這一差異。規定如果某用戶產生搜索行為的頻率很高、用戶較活躍,則選取較大的α,反之則選取較小的α。

直覺上,Timeui和Timevi差距越小,即用戶u,v搜索同一物品i的時間越接近,用戶u,v的興趣相似度越高,在對目標用戶u進行個性化推薦時,更傾向利用用戶v的興趣來預測目標用戶u的興趣。根據這一直覺,定義第3個啟發式規則:

啟發式規則3設用戶u,v,t對物品i的興趣時效分別為Timeui,Timevi,Timeti,若 |Timeui-Timevi|＞|Timeui-Timeti|,則用戶興趣相似度Wuv＞Wut。

3 用戶興趣相似度的三級計算方法

用戶之間相似性可以通過Jaccard公式度量,本文利用并改進Jaccard公式來計算用戶之間的相似度。Jaccard公式表示為:

其中,Wuv表示用戶u與用戶v之間的興趣相似程度;N(u)表示用戶u搜索過的物品集合;N(v)表示用戶v搜索過的物品集合。

上文從用戶興趣廣度、興趣深度、興趣時效這3個方面來構建用戶興趣三維模型,下文將根據用戶興趣三維模型的每一維來逐步改進計算用戶興趣相似度的Jaccard方法。

3.1 用戶興趣相似度的第1級計算方法

在式(2)的基礎上,本文引入用戶興趣三維模型中的第1維——興趣廣度來刻畫用戶興趣相似度,設用戶u,v的興趣廣度分別為Width(u),Width(v),根據中啟發式規則1,用戶u,v之間的興趣相似度可定義如下:

從式(3)可以看出,如果用戶u和用戶v共同產生過行為的物品數目越多,用戶u和用戶v之間的興趣相似度就越高。這個公式完全沿用了Jaccard方法。

3.2 用戶興趣相似度的第2級計算方法

在式(3)的基礎上,本文引入用戶興趣三維模型中的第2維——興趣深度來進一步分析用戶興趣相似度。設用戶u,v對物品i的興趣深度為Depthui,Depthvi,根據上文中啟發式規則2,用戶u和用戶v的興趣相似度Wu′v可改進為:

其中,i為用戶u和用戶v都搜索過的物品。從式(4)可以看出,用戶u和用戶v對物品i的搜索次數差別越小,用戶u和用戶v的興趣相似度就越大。

3.3 用戶興趣相似度的第3級計算方法

在式(4)的基礎上,本文引入用戶興趣三維模型中的第3維——用戶興趣時效來更進一步分析用戶興趣相似度。設用戶u,v對物品i的興趣時效分別為Timeui,Timevi,根據上文中啟發式規則3,用戶u和用戶v的興趣相似度Wu″v可改進為:

從式(5)可以看出,若用戶u和用戶v對物品i產生搜索行為的時間點越接近,用戶u,v之間的興趣相似度就越大。

在以上給出的三級算法中,第3級用戶興趣相似度在第2級用戶興趣相似度的基礎上增加了用戶興趣時效因素,能夠更準確地從不同角度分析用戶之間的相似性,幫助提高用戶個性化推薦效果。這將在本文的實驗部分進行驗證。

4 基于用戶興趣三維建模的個性化推薦

一般推薦系統預測目標用戶對某一物品感興趣程度的做法是:選取與目標用戶興趣最接近的用戶群體U,通過用戶群體U對該物品的感興趣程度來預測目標用戶對其感興趣程度。從物品中挑選出用戶感興趣程度Top(K)的K個物品推薦給目標用戶。

4.1 用戶對物品的感興趣程度計算

本文已經通過構建用戶興趣三維模型得出了用戶u和用戶v之間興趣相似度W?uv,那么,目標用戶u對未產生過行為的物品j的感興趣程度可表示為:

其中,S(u,K)表示與目標用戶u興趣最接近的K個用戶,可通過對W?uv進行top-N運算求得;M(j)表示對物品j產生過搜索行為的用戶集合;T為當前時間。由式(6)可知,在當前時間T,與用戶u興趣相似的用戶v對物品j的感興趣程度越高,用戶u對物品j的感興趣程度就越高。

4.2 算法描述

綜上,可以看到,基于用戶興趣三維建模的個性化推薦算法的過程可以分為2步:

(1)通過3.3節中第3級計算方法得到用戶u的最近鄰集合S(u,K);

(2)通過4.1節方法計算用戶u對物品j的感興趣程度P(u,j),最后向用戶u推薦P(u,j)排名Top(K)的物品j即可。

將本文算法分為2個階段來描述:

階段1求用戶u的最近鄰集合S(u,K)

輸入用戶u,用戶整體集合USERS

輸出用戶u的最近鄰集合S(u,K)

該階段算法的時間復雜度為O(mn)+O(mlbm),其中,m=|USERS|,是全部用戶的個數;n為用戶u與其他用戶共同搜索的物品的最大個數,即n=Max(|Width(u)∩Width(v)|)。時間復雜度的前一項O(mn)為計算用戶u和其他用戶興趣相似度的時間復雜度,事實上,由于用戶搜索的物品個數遠遠小于用戶個數,即n?m,因此該階段算法的時間復雜度可以簡化為O(m)。時間復雜度的后一項O(mlbm)為堆排序Wuv′′′的時間復雜度。

階段2求用戶u對物品感興趣程度Top(K)的物品集合J′

輸入用戶u的最近鄰集合S(u,K),物品集合J

輸出用戶u對物品感興趣程度Top(K)的物品集合J′

該階段算法的時間復雜度為O(x|K|)+O(xlbx),其中,x為用戶u未搜索過的物品個數,最大為整個物品集合的數目|J|;|K|是系統選取的最近鄰的數目。時間復雜度的前一項O(x×|K|)為計算用戶u對物品j的感興趣程度的時間復雜度,一般來說,系統選取的最近鄰數目遠遠小于用戶未搜索過的物品個數,即|K|?x,所以該階段算法的時間復雜度可以簡化為O(x)。時間復雜度的后一項O(xlbx)為堆排序P(u,j)的時間復雜度。

5 實驗結果與分析

5.1 實驗環境與數據集

個性化推薦中常用的公開數據集包括MovieLens, BookCrossing,Jester等,由于本文算法所需的數據來源于搜索日志,因此這些數據集并不適用于本文算法。目前沒有公開的推薦系統的搜索日志數據集,已有的公開搜索日志數據集如Sogou日志難以用在個性化推薦系統中,因此,本文實驗中采用北京林業大學數字標本館Web系統的用戶搜索日志,用以考察系統向用戶推薦標本的準確性。

經過對數據的處理和篩選后,選擇了包含467個用戶關于788個標本的4 783條搜索記錄,每個用戶至少有10次的搜索行為。這些數據可以比較充分地對本文提出的算法進行測試。實驗中按照本文第2節的部分來構建用戶興趣三維模型。在實驗過程中,將整個搜索日志數據集劃分為2個部分,80%用作訓練集,主要用于構建用戶興趣模型,剩下的20%用作測試集,用于驗證模型的實際效果。

5.2 評價標準

實驗比較了基于一維、二維、三維興趣模型的個性化推薦算法對用戶興趣描述的準確性。一維興趣模型只用用戶興趣廣度表征用戶興趣;二維興趣模型利用用戶興趣廣度和深度來表征用戶興趣,也就是常見的利用搜索次數和搜索范圍來描述用戶興趣,實驗以基于用戶興趣二維模型的推薦算法為參照,來驗證本文提出的基于用戶興趣三維模型的推薦算法的質量;三維興趣模型利用用戶興趣廣度、深度、時效來表征用戶興趣。分別根據用戶興趣的一維、二維、三維模型來計算用戶興趣相似度,產生最近鄰,預測用戶的興趣,產生推薦物品,比較推薦的準確性。

本文采用2種指標來評價實驗結果:平均絕對值誤差(Mean Absolute Error,MAE)[15]和推薦精度(Precision@N)[16]。

平均絕對值誤差方法通過計算預測的用戶感興趣物品與實際的用戶感興趣物品之間的誤差,來表示預測的準確性,如式(7)所示。MAE值越小,說明推薦越精確。MAE值計算公式如下:其中,N為測試集中物品的個數;Pi是對物品i的預測感興趣程度;Qi是實際感興趣程度。

Precision@N通過計算預測推薦物品與實際推薦物品的相關程度來反映推薦的精度,該值越大,精度越高,推薦的質量就越好,如式(8)所示。

其中,N為推薦給目標用戶的物品個數;Prediction(N)表示通過訓練集對目標用戶進行興趣預測后,推薦給目標用戶的物品集合;Data(test)表示測試集中實際應該推薦給目標用戶的物品集合。

5.3 結果分析

基于用戶的個性化協同過濾推薦算法中,最近鄰數目的選取通常會影響計算結果,最近鄰數目越多,精度越高。在最近鄰用戶數K分別取4,8,12, 16,20時,對基于3種用戶興趣模型的個性化推薦算法進行MAE值進行比較,實驗結果如圖2所示。

圖2 3種個性化推薦算法的MAE值對比

由圖2可見,首先,隨著最近鄰用戶數K的增加,基于3種不同興趣模型的推薦算法MAE值都降低,即推薦結果都更精確。這是因為隨著最近鄰數目的增加,能夠體現用戶興趣的數據增多,構建的用戶興趣模型就更精確。其次,在任意K值下,隨著建模興趣維度的增加,MAE值隨之降低,說明建模時每增加用戶興趣的一個維數,對用戶興趣的描述就更準確些,證明本文提出的用戶相似度三級計算方法是科學的,能夠逐步提高推薦精確度。并且在取同樣K值條件下,基于用戶興趣三維建模的推薦算法都取得了最低的MAE值,這是因為基于用戶興趣三維建模的個性化推薦算法從用戶的興趣廣度、深度、時效3個方面來構建用戶興趣模型,較另外兩種興趣模型而言,對用戶興趣的表征更精確。同時,也說明本文提出的算法推薦質量高于常見的基于用戶興趣二維模型算法的推薦質量。

基于3種不同興趣模型的個性化推薦推薦算法的Precision@N值的比較結果如圖3所示。可以看出,隨著推薦資源個數的增加,3種基于不同興趣模型推薦算法的推薦精度都在逐步增加,基于用戶興趣三維建模的算法始終比基于興趣一維和二維建模算法取得更大的推薦精度,在推薦精度為15時,與另外2種推薦算法差距達到最大。與常見的基于用戶興趣二維模型的推薦算法相比,用戶興趣三維模型更能夠準確地表征用戶興趣,在實際應用中,基于用戶興趣三維建模的個性化推薦算法具有更高的使用價值。

圖3 3種算法的推薦精度對比

6 結束語

個性化推薦系統的目的是在應用領域預測用戶需求興趣并向用戶推薦可用的信息。本文針對大多數推薦算法對用戶興趣描述不準確的問題,提出了一種基于用戶興趣三維建模的個性化推薦算法。通過分析用戶行為數據,從用戶興趣廣度、深度、時效3個維度來構建用戶興趣三維模型,使用戶興趣模型更能準確地表征用戶的興趣,基于此提出了用戶興趣相似度的三級計算方法。實驗結果證明,用戶興趣三維模型具有一定的科學性,能夠更準確地表征用戶興趣,與傳統基于用戶興趣二維模型的推薦算法相比,基于用戶興趣三維建模的個性化推薦算法能夠提高推薦的準確性,將其應用到推薦系統中,能夠有效地提高系統的推薦質量。

[1] Wei Chen,HsuW,LeeM L.ModelingUser’s Receptiveness over Time for Recommendation[C]// Proceedings of the 36th ACM SIGIR Conference.Dublin, Ireland:[s.n.],2013:373-382.

[2] 王巧容,趙海燕,曹 健.個性化服務中的用戶建模技術[J].小型微型計算機系統,2011,32(1):39-46.

[3] 陳文濤,張小明,李舟軍.構建微博用戶興趣模型的主題模型的分析[J].計算機科學,2013,40(4):127-135.

[4] 蒲國林,楊清平,王 剛,等.基于語義的個性化用戶興趣模型[J].計算機科學,2008,35(7):181-184.

[5] 石 林,徐 飛,徐守坤.基于用戶興趣建模的個性化推薦[J].計算機應用與軟件,2013,30(12):211-214.

[6] 王微微,夏秀峰,李曉明.一種基于用戶行為的興趣度模型[J].計算機工程與應用,2012,48(8):148-151.

[7] 邱云飛,王琳潁,邵良杉,等.基于微博短文本的用戶興趣建模方法[J].計算機工程,2014,40(2):275-279.

[8] 蔣秀林,謝 強,丁秋林.基于領域本體的用戶模型的研究[J].計算機應用研究,2012,29(2):606-608.

[9] 吳 蓉,丁二玉,駱 斌.基于加權本體的個性化語義搜索[J].計算機工程與設計,2008,29(19): 5051-5053.

[10] 陳 婷,韓偉力,楊 珉.基于隱私保護的個性化推薦系統的研究與實現[J].計算機工程,2009,35(8): 283-285.

[11] 劉濱強.移動環境下的個性化推薦用戶興趣建模研究[D].北京:北京郵電大學,2009.

[12] 楊繼萍,王 躍,高雪松.個性化流媒體服務中基于行為分析的用戶興趣建模[J].計算機應用與軟件, 2011,28(8):247-250.

[13] Li Jun,Zhang Peng.Mining Explainable User Interest from Scalable User Behavior Data[J].Procedia Computer Science,2013,17:789-796.

[14] 康雨潔.基于協同過濾的個性化社區推薦方法研究[D].合肥:中國科學技術大學,2001.

[15] 邸佳奇,王霓虹.一種基于GridGIS的增量式協同過濾算法[J].計算機科學,2013,40(12):219-222.

[16] Xu Guandong,Gu Yanhui,Zhang Yanchun.Toast:A Topicoriented Tag-base Recommender System[C]//Proceedings of the 12th International Conference on Web Information System Engineering.Sydney,Australia:[s.n.],2011: 158-171.

編輯 金胡考

Personalized Recommendation Algorithm Based on Three-dimensional User Interest Modeling

WANG Bingyi,LIU Yang,NIE Changxin,TIAN Xuan
(School of Information Science and Technology,Beijing Forestry University,Beijing 100083,China)

To realize the personalized recommendation,an algorithm based on three-dimensional user interest modeling is presented.First,by analyzing user’s behavior data,three aspects of user interest are analyzed for building threedimensional user interest model,including interest width,interest depth and user interest timeliness.Secondly,based on the three-dimensional user interest model,the dimension is gradually added and a method for calculating the interest similarity between two users is proposed.At last,a personalized recommendation algorithm is given.Experiment uses the data set derived from real recommendation system.The results show that,three-dimensional user interest model can describe user interest more accurately than two-dimensional and one-dimensional user interest model,and the proposed personalized recommendation algorithm can improve the accuracy rate of personalized recommendation.

personalized recommendation;three-dimensional user interest modeling;interest width;interest depth; interest timeliness;user interest similarity

1000-3428(2015)01-0065-06

A

TP312

10.3969/j.issn.1000-3428.2015.01.012

中央高校基本科研業務費專項基金資助項目(YX2014-19);北京林業大學國家級大學生創新基金資助項目(201310022050)。

王冰怡(1995-),女,本科生,主研方向:信息檢索,推薦系統;劉 楊、聶長新,本科生;田 萱(通訊作者),副教授、博士。

2014-04-28

2014-07-03 E-mail:tianxuan@ruc.edu.cn

中文引用格式:王冰怡,劉 楊,聶長新,等.基于用戶興趣三維建模的個性化推薦算法[J].計算機工程,2015, 41(1):65-70.

英文引用格式:Wang Bingyi,Liu Yang,Nie Changxin,et al.Personalized Recommendation Algorithm Based on Threedimensional User Interest Modeling[J].Computer Engineering,2015,41(1):65-70.