結合LDA和用戶特征的協同過濾算法

梁 靜，葛 宇

(1.成都工業學院 計算機工程學院，四川 成都 611730；2.四川師范大學 計算機科學學院，四川 成都 610066)

0 引 言

基于用戶的協同過濾算法能根據用戶最近鄰居(文中簡稱最近鄰)的興趣偏好，向其推薦滿足需求的商品、信息和服務，近年來已被廣泛應用于電子商務和社交網絡中[1]。但是，傳統基于用戶的協同過濾算法對數據稀疏問題和用戶冷啟動問題的處理能力較差，導致用戶間相似性度量的準確度降低，從而影響推薦質量[1,2]。為此，不少學者進行了相關研究。例如，針對數據稀疏問題，文獻[3]利用基于項目的協同過濾結果填充評分矩陣空值，降低數據稀疏度后結合ALS矩陣分解算法進行預測，提高推薦質量。文獻[4]基于項目評分數據和項目類別數據構建用戶-項目-類別的三維張量，通過填補缺失數據建立用戶類別偏好矩陣和評分偏好矩陣，進行聯合推薦。文獻[5]在傳統算法中加入用戶和項目的標簽信息，嵌入LDA主題模型計算用戶和項目的余弦相似性，提高相似性計算的準確度。文獻[6]構造時間柱模型，根據用戶評分及時刻生成時間加權相似度進行預測評分，并對項目類型進行LDA聚類預測評分，最終通過調節因子確定兩種評分的權重生成結果，提高了推薦質量。針對新用戶冷啟動難題，文獻[7]從評分、興趣、置信度3個方面計算用戶評分相似性，結合用戶屬性相似性進行聯合預測推薦，并實現冷啟動到非冷啟動狀態用戶相似性計算的平滑過渡。文獻[8]在文獻[7]的平滑過渡方案上，基于用戶特征的動態變化進行分類，設計了結合用戶特征和評分數據的相似度計算方案，提高推薦的準確率。文獻[9]設計了適應于計算個性化用戶相似性的距離度量公式，并對用戶屬性評分量化，將其引入相似性計算公式中，既提高了推薦精度，也滿足了用戶的個性化需求。

不同于以上思路，本文為提高用戶相似性計算準確度，提出一種結合LDA和用戶特征的協同過濾算法。具體地，針對數據稀疏問題，利用基于吉布斯采樣的LDA主題模型，設計用戶對項目主題評分的相似性評價方案，并從理論角度論證該方案能有效降低數據稀疏性；針對用戶冷啟動問題，結合用戶特征設計相應的編碼，用海明距離計算用戶間相似度，作為冷啟動用戶尋找最近鄰的依據。在MovieLens數據集上的實驗結果表明，本文算法能有效預測用戶評分，提高推薦質量，在應對數據稀疏性問題和冷啟動用戶時也有較好的表現。

1 傳統基于用戶的協同過濾算法

傳統基于用戶的協同過濾根據鄰居用戶的偏好向目標用戶進行推薦[1],首先根據已知的用戶-項目評分矩陣，依據文獻[9]采用皮爾遜系數法由式(1)[9]評估用戶間的相似程度，然后根據相似性高低選取目標用戶的最近鄰Num(u)，找出與目標用戶偏好一致的鄰居用戶，最后根據式(2)預測目標用戶對項目的評分

(1)

(2)

2 結合LDA主題模型和用戶特征的協同過濾算法

文獻[1]指出，傳統基于用戶的協同過濾算法，用戶相似性評價會受到用戶-項目評分數據稀疏性問題和用戶冷啟動問題的影響，而用戶間相似性評價的準確程度又直接影響了算法最終推薦質量。為此，本文在傳統基于用戶的協同過濾算法基礎上，以提高用戶相似性評價準確性為出發點，對數據稀疏問題和用戶冷啟動問題的處理方案進行研究，具體思路為：

在傳統基于用戶的協同過濾算法基礎上，通過借助吉布斯采樣的LDA主題模型和矩陣運算，挖掘項目類型的隱含主題，生成項目-主題隸屬概率矩陣，構造用戶-主題評分數據，設計用戶相似性評價方案，并用概率方法分析方案對數據稀疏問題處理的有效性。同時，在改進相似性的基礎上分析用戶特征，設計基于海明距離編碼的冷啟動用戶相似性評價方案，用于提高冷啟動用戶的推薦質量。

2.1 基于LDA主題模型的用戶相似性評價

LDA主題模型是一種文檔主題生成模型，常用于挖掘大規模文檔集中潛藏的主題信息，利用隱藏主題優化文檔分類。如：文獻[10]針對TF-IDF模型，運用LDA模型挖掘出文本的潛在主題，以提高文檔聚類純度。本文受此思路啟發，借助LDA主題模型從項目類型關系中挖掘項目對應的潛在主題，將項目按主題進行聚類、構造項目-主題關系矩陣，以便更科學地反映數據規律。

2.1.1 基本吉布斯采樣的LDA主題模型

Blei提出的隱含狄利克雷分布(latent Dirichlet allocation，LDA)是一種經典的主題模型，常被用來推測文檔的隱含主題分布[10]，其對應的概率模型如圖1所示。

圖1 LDA概率圖模型

圖1中M為文檔總數，K為主題編號總數，Nm為第m篇文檔中包含的詞匯總數。zm,n(m∈[1,M]，n∈[1,Nm])是文檔m第n個詞匯所屬的主題編號，wm,n是文檔m中的第n個詞匯在詞典中的序號。θm、φk分別表示第m篇文檔下的主題分布和第k個主題下的詞匯分布。α和β為先驗參數。在給定文檔集合下，wm,n是可觀察的已知量，α和β是根據經驗所得先驗參數。按圖1所示概率模型，可通過變分貝葉斯推斷、吉布斯采樣和最大似然估計[11]等方式估計出θm和φk值。本文采用吉布斯采樣法估計LDA主題模型的θm主題分布，流程如圖2所示。

圖2 LDA吉布斯采樣算法流程

圖2對應的流程描述為：

(1)指定參數K(主題數)、α、β，和輸入數據wm,n。

(3)利用吉布斯公式p(zi|z-i,d,w)對每個詞匯進行采樣，求出它對應的主題編號，并更新zm,n狀態。

(4)重復(3)，直到吉布斯采樣收斂或達到迭代次數。

(5)輸出每篇文檔的主題分布θm。

2.1.2 挖掘項目-主題關系數據

針對項目數據(如本文實驗中MovieLens 100K數據集的u.item和u.genre信息)，將項目的類型看作詞匯，每個項目看作文檔，依據2.1.1節中的LDA主題模型挖掘項目隱含主題。設項目總數為M，將第m個項目記為itm(m∈[1,M])，如itm=(Action,Adventure,Thriller)，表示項目m對應的類型有Action,Adventure和Thriller。所有項目的類型集合IT={it1,it2,…itM}。

采用圖2流程，計算項目主題分布。輸入項目類型集合IT，超參數α、β和主題數K。經過吉布斯采樣算法，G次迭代(為保證算法收斂，G不宜過小)后輸出本文所需的項目主題分布Iθ(如圖3所示)。圖3中，行列分別代表項目和主題，如第1行第1列數值為0.025 64，表示第1個項目在第1個主題的概率。

圖3 項目主題分布Iθ

2.1.3 構造用戶-主題評分數據

為了處理用戶-項目評分矩陣RUM中的稀疏問題(即：用戶沒有對項目評分，造成矩陣中對應項為空)，本文結合2.1.2節中得出的項目主題分布Iθ，把RUM轉換為用戶-主題評分矩陣RUK。以下給出轉換方案，隨后從概率角度進行分析，以說明本方案的有效性。

(1)用戶-項目評分矩陣到用戶-主題評分矩陣的轉換方案。

(3)

(4)

(5)

(2)從概率角度分析轉換前后數據的稀疏性。

稀疏性和數據(矩陣)中存在空值(0值)成正比，為了說明以上方案所使用的用戶-主題評分矩陣RUK稀疏性小于傳統方法所使用的用戶-項目評分矩陣RUM，下文從概率角度進行論證。

RUM和RUK中各個元素不為空值的事件是等可能事件(即項目或主題被對應用戶作過評分事件)，設DM對應矩陣RUM中一個元素值不為空的隨機事件，其概率p(DM)記為λ1，λ1∈(0,1)；DK對應矩陣RUK中一個元素值不為空的隨機事件，其概率p(DK)記為λ2，λ2∈(0,1)。RUM(U×M)中所有元素值不為空的概率用p(RUM)表示；RUK(U×K)中所有元素值不為空的概率用p(RUK)表示。則矩陣RUM出現空值的概率

(6)

同理，矩陣RUK出現空值的概率為

(7)

以下用反證法證明λ1≤λ2。

證：假設λ1>λ2

(8)

根據假設λ1>λ2，則有

λ1>1-(1-λ1)Q?λ1-1>-(1-λ1)Q?

(1-λ1)<(1-λ1)Q

(9)

由指數函數的單調性可知

Q<1

(10)

與已知Q≥1矛盾，假設不成立。因此λ1≤λ2，證明完畢。

2.1.4 結合用戶-主題數據計算用戶相似性

根據以上結果，用戶-主題矩陣RUK中每一行記錄了每位用戶對各個主題的評分。參考文獻[5]，使用夾角余弦法計算矩陣RUK中用戶間的相似度。設用戶u、v對應主題評分數據RUK矩陣中兩行(記為向量ru和rv)，其相似度uksim(u,v)計算如式(11)所示

(11)

式中：向量ru=[ru,1,ru,2…,ru,K]，向量rv=[rv,1,rv,2…,rv,K]。

2.2 基于特征編碼的冷啟動用戶相似性評價

為了應對用戶冷啟動問題(即：缺少冷啟動用戶對項目的歷史評分數據，導致無法從用戶-項目數據中有效評價冷啟動用戶與其它用戶間相似性的問題)，本文參考文獻[7]、文獻[8]中利用特征作用戶相似性評價的思路，設計了一種用戶特征(如本文實驗中MovieLens 100K數據集的u.user、u.occupation信息)編碼方案，配合海明距離計算冷啟動用戶與其他用戶間的相似性。

2.2.1 用戶特征編碼方案

對于冷啟動和非冷啟動用戶，都已知其對應的性別、年齡和職業特征。定義用戶特征集合為UA，共U個用戶，UA={ua1,ua2,…uaU}，其中uau(u∈[1,U])為用戶u的特征。如uau=(24,M,Technician)，表示該用戶年齡24，性別男，職業為技術員。

為配合海明距離計算用戶間相似度，本文對3個用戶特征使用不同長度的二進制數進行分別編碼，以體現出不同特征對用戶相似性的影響程度。具體的編碼方案為：

(1)性別特征，用1位二進制進行編碼，將男女分別編碼為0和1。

(2)年齡特征，用7位二進制進行編碼。將年齡分為7組：(0-17)、(18-24)、(25-34)、(35-44)、(45-49)、(50-55)和56歲以上。考慮到要區別用戶年齡段之間的差異程度，比如年齡50和10，相比50和40的差異程度更大，故本文對年齡特征按分組進行多位置1編碼。每一位編碼代表一個年齡段，當用戶屬于某年齡段時，對應編碼位和它前面的每位均置1，后面均置0。如24歲編碼為“1100000”，47歲編碼為“1111100”。

(3)職業特征，用5位二進制進行編碼。依據二八定律[12]：任何一組東西，最重要的大約占20%，其余的占80%。本文將職業對應的用戶數量降序排列，前20%的職業單獨分類，其余職業歸為一類。對21個職業統計后，student、other、educator、administrator排在前4，對應前4位編碼，其余歸為一類對應第5位編碼。具體編碼時，所屬職業的對應位置1，其它位均置0。如educator編碼為“00100”，Technician編碼為“00001”。

依據以上編碼方案，最終構成13位二進制編碼。其格式如圖4所示。用戶特征編碼集合對應如圖5所示。

圖4 13位的用戶特征編碼格式

圖5 用戶特征編碼集合

2.2.2 結合海明距離計算冷啟動用戶相似性

在信息學中，海明距離[13]被用于衡量兩串代碼間的差異，是一種簡單高效的距離計算方法，本文基于海明距離設計了冷啟動用戶相似性計算策略，更準確地為冷啟動用戶尋找最近鄰居。根據以上思路，以下從用戶特征編碼中計算用戶間海明距離，以此評價冷啟動用戶與其他用戶間的相似性。冷啟動用戶u與非冷啟動用戶v對應的相似性uasim(u,v)，如式(12)所示

(12)

式中：dishamming(u,v)為u、v間的海明距離，即：統計兩位用戶的編碼在進行異或(xor)運算后1的個數，其結果與相似度成反比關系。特別說明的是：為了處理dishamming(u,v)為0的情況，分母中加入了調節項1。

2.3 算法描述

根據前文分析，以下在傳統基于用戶的協同過濾算法基礎上，加入了針對數據稀疏性問題和用戶冷啟動問題的相應機制，設計了結合LDA主題模型和用戶特征的協同過濾算法，算法流程描述如下(其中(1)-(3)、(4)、(5)分別對應文中2.1節和2.2節設計的方案，(6)即對應是否為冷啟動用戶分別采用不同的方案計算相似度并用于最終預測推薦)：

(1)對項目類型集合IT，按照2.1.1節中LDA吉布斯采樣算法流程(如圖2所示)，計算出項目主題分布Iθ。

(3)按2.1.4節中式(11)，利用夾角余弦法計算出用戶相似度uksim。

(4)對用戶特征集合UA按2.2.1節進行特征編碼。

(5)根據2.2.2節中式(12)計算出冷啟動用戶與非冷啟動用戶相似度uasim。

(7)輸出用戶預測評分數據。

3 實 驗

3.1 數據集與評價指標

本文實驗采用MovieLens 100K數據集[14]，抽取數據訓練集和測試集比例4∶1，實驗環境為Intel Core i5處理器、8 GB內存，Windows10(64 bit)操作系統。

參考文獻[4]、參考文獻[15]，實驗使用平均絕對誤差MAE[4](mean absolute error,MAE)和準確率Precision[15]對算法進行評價，分別如式(13)、式(14)

(13)

(14)

式中：TopN為算法向用戶所推薦的項目數，Hits為算法產生的正確推薦數，Precision值越高，表示推薦質量越高。

3.2 實驗結果及分析

參考文獻[6]，本文將算法中LDA主題數設置為15，為驗證本文算法(以下記為：UILCF)的有效性，實驗先討論UILCF在不同數據稀疏度、不同冷啟動用戶數量情況下的表現，然后將UILCF與4種具有代表性的算法進行性能對比，具體實驗如下：

(1)不同數據稀疏度下算法性能對比

本文算法是在傳統基于用戶的協同過濾算法基礎上加入了應對數據稀疏性的機制，為評估其有效性，實驗將UILCF與傳統協同過濾算法(以下簡記為UCF)進行對比。實驗隨機刪除測試集中部分評價數據，模擬不同的稀疏度(矩陣RUM中空值或0值的比例)環境，結果如圖6和表1所示。從圖6結果可以看出，隨著數據稀疏度的增長，兩種算法的MAE值都在增加，但UILCF的MAE值始終低于UCF。從變化率的角度看，UILCF也優于UCF，尤其在稀疏度值0.96以后，UILCF的優勢更加明顯。另外表1對比結果表明，在不同稀疏度下UILCF均具有更好的推薦準確率。這正是因為UILCF在計算用戶相似性時結合了LDA模型，讓算法在數據稀疏度不斷增大時仍然具有較好的預測效果。

圖6 UCF與UILCF在不同稀疏度下的對比

表1 UCF與UILCF在不同稀疏度下的準確率對比/%(TopN=2)

(2)不同冷啟動用戶數量下算法性能對比

UILCF在UCF的基礎上增加了冷啟動用戶處理機制，以下實驗從測試集中隨機選擇用戶，刪除其評分數據，模擬不同數量冷啟動用戶的情況，結果如圖7和表2所示。在冷啟動用戶數量為10-60時，圖7中UILCF的MAE值始終低于UCF。表2中UILCF的Precision值始終高于UCF，表明UILCF具有更高的推薦質量。以上結果說明，本文算法利用了用戶特征信息尋找鄰居用戶進行相似推薦，取得了更好的效果。

圖7 UCF與UILCF在不同冷啟動用戶下的對比

表2 UCF與UILCF在不同冷啟動用戶下的準確率對比/%(TopN=2)

(3)與文獻報道的算法性能對比

實驗選擇4種具有代表性的算法進行對比：傳統基于用戶的協同過濾算法(以下記為：UCF)、傳統基于項目的協同過濾算法(以下記為：ICF)、嵌入LDA主題模型的協同過濾推薦算法(以下記為：ULRCF)[5]、基于用戶屬性和評分的協同過濾算法(以下記為：UARCF)[7]，實驗結果如圖8和表3所示，其中表3給出了推薦數目TopN在不同取值下的準確率對比。圖8中，UCF、ICF、ULRCF對應數據來自文獻[6]，UARCF對應數據來自文獻[7]。表3中UCF、UARCF對應數據來自文獻[8]。

圖8 不同算法下的MAE值變化

表3 不同算法的準確率對比/%

表3結果說明，各算法隨推薦數目的增多，Precision值呈下降趨勢。但UILCF在不同的推薦數目下，Precision值均優于文獻中的另兩種算法，尤其在推薦數目較小時，UILCF的推薦準確率很高。從圖8不難看出，相比于UCF、UARCF、ULRCF和ICF，在最近鄰數量小于35時UILCF對應的MAE值更低，說明本文算法因為采取了針對數據稀疏問題和用戶冷啟動問題的對應策略，所以性能優于上述4種算法。需要說明的是，在最近鄰數量大于38時，UILCF的MAE值變化趨于平緩，且高于ULRCF，說明本文算法在最近鄰個數增大時效果不及ULRCF。但是結合實際考慮，算法在最近鄰個數較少時得到的推薦準確性更具有應用價值，由此說明，本文算法在最近鄰個數較少時相比4種算法推薦質量更高，更具有實用價值。

4 結束語

本文提出了結合LDA主題模型和用戶特征的協同過濾算法。在傳統基于用戶的協同過濾算法基礎上，利用LDA主題模型挖掘項目的隱含主題，和已有數據一起計算用戶-主題評分，從而將用戶相似度評價依據從稀疏度較高的用戶-項目評分矩陣，轉變成了稀疏度較低的用戶-主題評分矩陣，有效緩解了數據稀疏性問題對用戶相似度的影響。另外，本文還提出了基于用戶的特征編碼方案，并根據海明距離建立冷啟動用戶和其它用戶的特征相似性評價方法，以提高冷啟動用戶對應用戶相似度計算的準確性。實驗結果表明，本文算法在最近鄰數量較少的情況下能提高算法的推薦質量，具有較好的實用性。