融合社交關系與時間因素的主題模型推薦算法

2020-03-19 12:24:48高茂庭

計算機工程 2020年3期

高茂庭,王吉

(上海海事大學信息工程學院,上海 201306)

0 概述

在Web2.0時代,互聯網上的信息過載現象進一步加劇。推薦系統作為解決信息過載問題的一種有效手段,可以較好地過濾網上不斷產生的“噪聲”,方便人們獲取有用的信息。推薦系統的核心是推薦算法,目前,應用最廣泛的推薦算法是協同過濾算法,其主要分為基于近鄰的協同過濾和基于模型的協同過濾[1]。然而,協同過濾算法存在冷啟動、數據稀疏性等問題。為解決上述問題,研究人員提出基于多信息融合的社會化推薦算法,其已成為推薦算法的熱門研究領域之一[2-4]。

一方面,每個人都可以在網絡上表達自己的想法,其在社會化標簽系統(Social Tagging System,STS)中自由創建的關鍵詞被稱為標簽。社會標簽不僅在一定程度上反映了用戶的興趣行為偏好,也代表著物品本身所具有的特性。因此,許多學者開始將標簽信息融入到推薦系統中。結合社會化標簽信息的推薦系統主要有協同過濾、基于排序的推薦和基于內容的推薦。文獻[5]通過使用標簽信息來擴展用戶和物品的信息,提出基于標簽擴展的個性化推薦技術。文獻[6]提出基于標簽和協同過濾的算法,利用標簽信息計算用戶對資源的偏好程度和資源相似度,得到用戶偏好矩陣,根據排名產生推薦結果。文獻[7]通過用戶自身的反饋來更新標簽的權重,重新產生用戶的個性化推薦列表。上述算法雖然考慮了標簽信息,但是忽略了標簽本身的語義問題。潛在Dirichlet分布(Latent Dirichlet Allocation,LDA)[8]被證明是可以較好地建立標簽的主題模型。文獻[9]使用LDA主題模型挖掘標簽的語義特征,并根據物品的評分信息計算物品相似度,通過將兩者結合以有效地提高推薦的質量。

另一方面,人們在做選擇時往往會更依賴朋友的建議[10]。社交網絡的發展使得人們獲取其社交朋友關系數據變得更容易,社交網絡系統不僅有向用戶進行推薦的需要[11],而且在社會化標簽系統中利用社交關系也能有效提高推薦的質量。文獻[12]將用戶之間的信任和相似度融合在一起,增強了用戶領域的計算,通過矩陣分解方法處理后產生推薦結果。文獻[13]使用用戶的社交關系網絡計算信任關系矩陣,并結合用戶評分矩陣產生推薦結果。上述推薦算法在考慮用戶社交關系的影響后,有效提高了推薦的準確率。

此外,用戶的興趣是隨著時間一直變化的,用戶對物品打標簽的時間越近,表明該行為越能準確地反映用戶對該物品的喜好程度,而打標簽行為的時間越久遠,則其反映用戶對該物品的喜好程度就越低。因此,結合上下文時間信息構建用戶興趣模型也成為一個新的研究熱點[14-16]。文獻[17]采用每個用戶當前偏好的轉移速率來衡量時間對用戶的影響,并通過使用用戶的側面數據來提高基于矩陣分解的推薦準確性。文獻[18]基于近鄰的協同過濾算法考慮了評分的時間上下文影響,降低預測誤差。

上述推薦算法根據少數幾種信息來計算用戶或者物品的相似度,通過協同過濾思想產生推薦結果。由于標簽主題語義、朋友社交關系以及時間因素都會對用戶行為產生影響,因此對這3種因素綜合考慮可以更加全面地構建用戶的興趣偏好模型,提高推薦的質量。本文在上述研究的基礎上進行改進,提出一種結合用戶社交關系和時間加權的主題模型推薦算法。使用LDA主題模型發現標簽之間潛在的語義關系,得到用戶對物品的偏好概率,同時結合時間權重和用戶標簽行為計算用戶相似度,在此基礎上融合用戶社交關系對用戶偏好概率進行處理,從而更全面地反映用戶對物品的真實偏好。

1 相關工作

1.1 相似度計算

相似度的計算是傳統協同過濾算法的重要步驟,其結果直接影響推薦的準確性能[19]。常用的相似度計算方法有余弦相似度、改進的余弦相似度和皮爾遜相似度3種。

文獻[20]指出:在基于用戶的推薦系統中,皮爾遜相似度僅考慮了用戶評價物品交集的標準差,比其他相似度度量方法效果更好。

1.2 LDA主題模型

LDA模型[8]是一個具有3層結構的貝葉斯概率模型,它可以將文檔集中每篇文檔的主題以概率分布的形式表現,從而得到文檔的主題分布。在LDA建模過程中,使用條件概率p(z|d)表示一篇文檔d中的主題z分布概率,使用條件概率p(w|z)表示每個主題z中一個單詞w的分布概率,則單詞w在文檔d中的分布概率為:

(1)

其中,K表示主題的個數。不同的主題個數會對整個LDA模型產生影響。

2 結合用戶關系和時間加權的主題模型推薦

本文使用LDA主題模型對用戶-標簽-物品信息進行處理,得到基于標簽的主題模型,在考慮時間因素和用戶社交關系的基礎上,提出一種融合用戶社交關系和時間加權的主題模型推薦算法(UTLDA),其分為以下4個步驟:

1)將用戶類比為文檔,用戶使用過的標簽類比為文檔中的單詞,得到用戶-標簽矩陣。將標簽類比為文檔,標簽所標記的物品類比為文檔中的單詞,得到標簽-物品矩陣。使用LDA主題模型處理上述2個矩陣,挖掘標簽潛在的語義,分別得到用戶-標簽概率矩陣和標簽-物品概率矩陣,計算用戶-物品概率矩陣。

2)考慮時間對用戶興趣的影響。使用用戶-物品矩陣,結合時間因素計算用戶之間的相似度。

3)考慮用戶社交網絡關系。結合用戶的社交朋友關系對用戶相似度進行處理,得到用戶間的權重。

4)考慮每個用戶之間的潛在影響和用戶對每個物品的潛在偏好,結合用戶權重矩陣和概率矩陣,得到最終的用戶-物品偏好權重矩陣,并根據偏好矩陣產生Top-N推薦。

本文算法流程如圖1所示。其中,標簽、時間以及社交關系處理屬于數據處理部分,可以離線進行,推薦部分在線完成。

圖1 UTLDA推薦算法流程Fig.1 Flowchart of UTLDA recommendation algorithm

2.1 基于標簽信息的用戶-物品概率矩陣計算

在STS中,用戶使用的一種標簽代表用戶的一種行為,用戶使用標簽的頻率反映用戶對該標簽的喜愛程度,用戶對物品標注標簽的次數反映用戶對該物品的喜愛程度。使用四元組(U,I,T,TS)代表用戶對物品打標簽的行為,其中,U代表用戶,I代表物品,T代表標簽,TS代表用戶對物品打標簽的時間。假設用戶集合U=(u1,u2,…,un),物品集合I=(i1,i2,…,im),標簽集合T=(t1,t2,…,tl),n、m、l分別代表用戶、物品以及標簽的總數。用戶-標簽矩陣X是一個n×l的矩陣,第i行第j列的元素xij定義為:

(2)

其中,w代表用戶i使用過標簽j的次數。

標簽-物品矩陣Y是一個l×m的矩陣,第i行第j列的元素yij定義為:

(3)

其中,w代表標簽i標記過物品j的次數。

(4)

其中,l是標簽的總數量。

2.2 結合時間因素的用戶相似度矩陣計算

(5)

其中,τ表示權重參數。

在計算用戶相似度時考慮到用戶標注物品的時間權重,將會減少用戶相似度的誤差。用戶對物品的評分使用用戶對物品標注的次數來代替,根據皮爾遜相似度計算公式,結合時間因素的用戶相似度計算公式為:

(6)

2.3 結合社交關系和時間因素的用戶權重矩陣計算

使用社交關系可以計算每個用戶與其他用戶之間的親密度。若用戶之間是朋友關系,其親密度為1,否則使用用戶社交關系來計算用戶的余弦相似度,以相似度衡量用戶間的親密度。用戶親密度計算公式為:

(7)

其中,s表示用戶u和用戶v之間的余弦相似度,該相似度由用戶社交關系計算得到。

比起陌生人,自己朋友的建議讓人更愿意相信,基于朋友關系的推薦讓人更有可能接受,推薦結果也更具有解釋性。在本文算法中,若用戶有朋友,則優先考慮用戶朋友的影響,否則就將其當成普通用戶處理。結合用戶的社交關系矩陣以及用戶之間的相似度矩陣,得到用戶的權重矩陣Q,計算公式為:

qu,v=S(u,v)+I(u,v)

(8)

其中,S(u,v)表示用戶u和用戶v的相似度,I(u,v)表示用戶u和用戶v的親密度。

2.4 基于用戶-物品偏好矩陣的推薦

(9)

根據得到的用戶偏好矩陣,按用戶最終偏好值對物品進行排序,取排名靠前的N個物品推薦給用戶。考慮到冷啟動問題,對于推薦系統中的新用戶推薦熱門物品。

2.5 UTLDA算法時間復雜度分析

設用戶數為n,物品數為m,標簽數為l,LDA迭代次數為g,主題數為t,用戶對物品進行標記的行為數為h。

在算法處理標簽信息的階段,2次LDA建模的時間復雜度分別為O(nlgt)和O(mlgt),由于物品數一般是遠大于用戶數,因此LDA主題建模的時間復雜度為O(mlgt)。式(4)計算用戶的偏好概率矩陣主要是根據LDA模型得到的2個語義概率矩陣,相當于矩陣相乘,其時間復雜度為O(nmt)。因此,2.1節算法處理標簽信息的時間復雜度為O(mlgt+nmt)。

在算法處理時間信息的階段,根據時間信息計算用戶時間權值的時間復雜度為O(h),利用時間信息計算用戶相似度矩陣時間復雜度為O(n2m),因此,其時間復雜度為O(n2m+h)。

在算法處理用戶社交信息的階段,利用用戶社交關系計算用戶相似度的時間復雜度為O(n2m),計算用戶親密度矩陣的時間復雜度為O(n2),因此,其時間復雜度為O(n2m)。

綜上,離線數據處理的時間復雜度為O(lmgt+n2m+h)。

在線推薦根據偏好矩陣產生推薦,相當于先查找后排序,其時間復雜度為O(nmlbn)。

對比文獻[6]算法和文獻[9]算法,本文算法由于考慮的因素較多,因此在離線階段其時間復雜度較高,但在在線階段,3種算法都是在根據計算得到的偏好矩陣進行推薦,其時間復雜度相同。

3 實驗與結果分析

3.1 實驗數據與實驗環境

本文實驗采用Last.fm-2K數據集,其包含用戶雙向的朋友關系、用戶收聽藝術家(物品)信息、用戶對藝術家的標簽信息、藝術家標簽信息,具體數據如表1所示。

表1 Last.fm-2K數據集信息Table 1 Last.fm-2K dataset information

在進行實驗之前,先對數據進行預處理。為了減少噪聲數據對推薦結果的影響,首先刪除數據集中標注物品數小于20的用戶,然后根據時間對數據集進行排序,找到位于數據集前20%的時間點,將該時間點之前的數據作為測試集,在剩余數據中隨機選取80%的數據作為訓練集,進行多次實驗后計算平均值。

本文實驗環境為Windows 10操作系統,Intel Core i7處理器,16 GB內存,實驗主要用Python語言實現。

3.2 評估指標

文獻[21]給出準確度衡量標準,主要有分類準確率、預測準確度和排名準確性等。本文采用分類準確率,包括準確率、召回率和F1衡量指標。

準確率表示項目物品被成功推薦的比例,其計算公式為:

(10)

其中,Nhits(u)表示在推薦物品中用戶u標注過的物品總數,Nrecset(u)表示推薦給用戶u的物品集合的總數。

召回率表示命中物品數在理論上可達到的最大值中所占的比例,其計算公式為:

(11)

其中,Ntestset(u)表示用戶u在測試集中標注過的物品總數,也就是命中數理論上可以達到的最大值。

F1衡量指標能夠有效地平衡準確率和召回率之間的誤差,其計算公式為:

(12)

F1值越大,模型的效果越好。

3.3 參數選取

本文需要確定的參數包括LDA建模的主題數目和Top-N推薦時排名前N的物品數。根據實驗經驗,本文將LDA主題模型中的超參數α和η分別設置為0.1和0.01,迭代次數設置為500次。

3.3.1 最優的推薦物品數

為了確定合適的推薦物品數目N,分別將數目N設置為35,40,…,75進行實驗,并且為了消除LDA主題數對算法效果的影響,在實驗過程中將主題數目分別設置為20,30,…,90,共進行8組實驗,結果如圖2所示。

圖2 不同N值下F1值的變化Fig.2 Change of F1 value under different N values

從圖2可以看出,無論LDA模型的主題數是多少,UTLDA算法的F1衡量指標隨著N值變化的趨勢基本相同,隨著N值增加,F1值總體上呈現出先增后降的趨勢。當N=50或N=55時,UTLDA算法的F1衡量指標達到最大值。而隨著主題數目的增加,當N=55時,F1衡量指標達到最大值。因此,本文算法選擇N=55進行實驗。

3.3.2 LDA模型的主題數目

為了確定合適的LDA模型主題數目,將主題數目T分別設置為20,30,…,90,比較在不同N值情況下,算法的F1衡量指標隨著主題數目的變化情況,實驗結果如圖3所示。

圖3 不同主題數下F1值的變化Fig.3 Change of F1 value under different topic numbers

從圖3可以看出,隨著主題數目的變化,算法的F1衡量指標總體上升,但一直上下波動。F1衡量指標在主題數為80時基本達到最大值,但LDA模型的建模時間隨著主題數目的增長而增加。以Top-55為例,算法的運行時間如表2所示。考慮到建模時間,本文對比算法中使用LDA模型時采用的主題數目統一為60。

表2 N=55時算法的運行時間Table 2 Operation time of algorithm when N=55

3.4 對比實驗

為了驗證UTLDA算法的有效性,本文將與以下算法進行對比實驗:傳統基于用戶的協同過濾推薦算法(UCF),基于標簽的協同過濾推薦算法(TCF)[6],基于標簽主題的協同過濾推薦算法(ColLDA)[9],基于LDA模型推薦算法,本文算法在未考慮時間和社交因素的情況下得到的推薦結果PreLDA。

根據3.3.2節內容,本文使用LDA模型時采用的主題數目統一設置為60,參數α和η分別設置為0.1和0.01,迭代次數設置為500次。各對比算法在不同的推薦數目下的召回率和準確率結果如表3和表4所示。

表3 各算法在不同推薦數目下的召回率Table 3 Recall of each algorithm under differentrecommended numbers %

表4 各算法在不同推薦數目下的準確率Table 4 Precision of each algorithm under differentrecommended numbers %

從表3和表4可以看出,在Last.fm數據集上,各對比算法的召回率都是隨著推薦數目的增加而增大,而準確率則隨著推薦數目的增加而減小,并且本文算法在召回率和準確率上均高于其他對比算法。

由于召回率和準確率一定程度上相互制約,為了更好地衡量各個算法的效果,本文進一步使用F1值來衡量推薦的質量。各對比算法在不同的推薦數目下的F1值如圖4所示。從圖4可以看出,不同的算法在F1衡量指標上的趨勢基本一致。

圖4 各算法在不同推薦數目下的F1值Fig.4 F1 value of each algorithm under differentrecommended numbers

各對比算法在相同環境下的運行時間如表5所示。從表5可以看出,傳統的協同過濾算法產生推薦的時間較長,ColLDA和UTLDA因為使用了LDA模型,所以離線部分要比TCF算法的時間要長;ColLDA算法使用物品信息對模型進行處理,而物品信息遠大于用戶信息,所以在離線部分時間略高于UTLDA。但是在線部分,TCF、ColLDA和UTLDA 3種算法都是根據偏好矩陣產生推薦,所以產生推薦的時間基本一致。

表5 4種算法運行時間Table 5 Operation time of four algorithms s

對比不同的算法可知,本文算法在準確率、召回率以及F1值上均較優。LDA算法構建主題模型,挖掘了用戶-物品的潛在信息,相對于傳統的協同過濾推薦算法,提高了推薦的質量;TCF算法將用戶的標簽行為與推薦算法相結合,優化了推薦效果;ColLDA算法使用LDA算法挖掘標簽的語義信息,進一步提高了推薦質量。本文綜合使用用戶社交關系和時間因素來對主題模型得到的概率矩陣進行處理,可以更加全面地衡量用戶對物品的偏好程度,實驗結果表明,UTLDA算法能更有效地提高推薦的質量。

4 結束語

在社會標簽系統中,用戶的社交關系以及用戶隨時間變化的興趣偏好都會對推薦質量產生影響。本文提出一種融合社交關系和時間因素的主題模型推薦算法,將時間因素加入到用戶的相似度計算模型中,使用主題模型建立用戶的興趣偏好,同時考慮用戶朋友以及其他用戶的影響,從而提高推薦的質量和可解釋性。實驗結果表明,該算法的召回率、準確率以及F1值均高于對比算法。后續將采用自然語言處理技術對標簽進行聚類,減少標簽的數量,并結合用戶的評論提取情感關鍵詞,建立更準確的用戶興趣偏好模型,進一步提高推薦結果的質量。