融合協(xié)同過濾與上下文信息的Bandits推薦算法*

王宇琛，王寶亮，侯永宏

天津大學 電氣自動化與信息工程學院，天津 300072

1 引言

隨著互聯(lián)網(wǎng)的飛速發(fā)展，每天都有海量信息不斷產(chǎn)生和傳播，進而出現(xiàn)信息過載問題。因此在互聯(lián)網(wǎng)在線服務(wù)中，推薦系統(tǒng)應(yīng)運而生，并且因其能夠有效過濾信息，同時為用戶進行精確的個性化服務(wù)而成為研究熱點。尤其在電子商務(wù)、新聞、音頻、視頻、廣告投放等領(lǐng)域，起到越來越關(guān)鍵的作用。

傳統(tǒng)的推薦算法如協(xié)同過濾，基于內(nèi)容的過濾、混合推薦算法等，都非常依賴用戶的歷史行為信息[1]。但在現(xiàn)實的推薦場景中，用戶對商品的行為信息矩陣非常稀疏，并且每天都會產(chǎn)生新的用戶和商品，這將導(dǎo)致傳統(tǒng)的推薦算法無法為部分用戶進行準確的個性化推薦，這就是所謂的數(shù)據(jù)稀疏性和冷啟動問題。針對這些問題，往往希望通過獲取額外的信息對新用戶、新商品進行模型構(gòu)建，進而完成個性化推薦[2]，但事實上額外信息并不易獲取，并且用戶信息和商品信息是隨時間動態(tài)變化的。

針對以上問題，適應(yīng)稀疏、缺失的信息成為推薦算法的基本要求。在強化學習領(lǐng)域，多臂賭博機算法（Bandits）是解決冷啟動與動態(tài)推薦的有效方法，又名探索-開發(fā)策略（exploration-exploitation method）。探索（exploration）是指通過為用戶推薦新的商品，希望找到用戶反饋最佳的全局最優(yōu)商品，但是過度探索將會消耗大量的推薦機會，導(dǎo)致在有限的推薦次數(shù)內(nèi)無法獲得當前最優(yōu)推薦。開發(fā)（exploitation）是指基于當前用戶反饋信息，為用戶推薦當前已知商品中能夠得到用戶最優(yōu)反饋的商品，但是過度開發(fā)將會導(dǎo)致陷入局部最優(yōu)解，無法找到所有商品中用戶最感興趣的商品。因此，只有合理平衡探索與開發(fā)，才能得到最佳推薦結(jié)果。

傳統(tǒng)的多臂賭博機算法沒有充分利用用戶對商品的反饋信息，并且在推薦過程中沒有引入特征的概念。近年來結(jié)合上下文的多臂賭博機受到高度關(guān)注，應(yīng)對冷啟動問題有不錯的效果[3]。但是基本的結(jié)合上下文的多臂賭博機沒有考慮到協(xié)同信息的重要性，在很多推薦場景中，具有相似興趣的用戶對同一個物品的反饋可能是一樣的，因此在給目標用戶推薦商品時，參考鄰居用戶的選擇傾向，可以得到更好的推薦效果[4]。因此，文獻[5]提出為目標用戶推薦商品時，根據(jù)用戶偏好將用戶聚類，把目標用戶所在類簇的平均特征視為目標用戶特征，并基于多臂賭博機算法預(yù)測某一商品的可能收益，再實時觀察真實反饋更新目標用戶特征。但是聚類后同一類簇內(nèi)的用戶往往非常多，用整體特征代替類簇內(nèi)的某一用戶特征，雖然引入了用戶的協(xié)同作用，但是會導(dǎo)致用戶本身的特征起到的作用非常小，從而使得計算結(jié)果與用戶真實偏好相差很大，而且同一類簇內(nèi)所有用戶共享一個特征，會犧牲推薦的個性化。

本文基于以上研究背景，提出了能有效解決用戶冷啟動的協(xié)同過濾線性多臂賭博機算法（collaborative filtering context linear Bandits,COLINBA），該算法與之前相關(guān)算法相比，在結(jié)合上下文的多臂賭博機算法基礎(chǔ)上，引入了更加精細的協(xié)同效果。當為目標用戶推薦商品時由用戶與其鄰居用戶共同決定，并且通過鄰居用戶相似度權(quán)重因子控制鄰居用戶對推薦的貢獻程度，從而保證目標用戶自身特征起主導(dǎo)作用，且引入了協(xié)同效果，優(yōu)化推薦性能。此外，相比文獻[6]中提出的基于矩陣分解（matrix factorization,MF）提取特征的方法，本文將自然語言處理中的潛在狄利克雷分布（latent Dirichlet allocation,LDA）主題模型用于推薦系統(tǒng)中的商品特征提取，從而避免了現(xiàn)實數(shù)據(jù)中商品用戶矩陣極其稀疏導(dǎo)致矩陣分解不佳的問題。并且矩陣分解只能利用評分信息或0-1反饋信息，而無法利用含有更大信息量的文本評價信息，引入LDA主題模型恰好可解決該問題，并且從模型原理角度論證了該方法可行性。最后在實驗中，運用LDA模型從真實數(shù)據(jù)集提取商品潛在特征，并基于COLINBA算法用商品特征不斷擬合用戶特征，從累計誤差和點擊率的角度與其他算法對比推薦結(jié)果，驗證了本文算法的有效性。

本文剩余部分的結(jié)構(gòu)如下：第2章介紹相關(guān)工作；第3章介紹本文提出的方法，包括本文算法基于的推薦模型，引入LDA主題模型提取商品潛在特征的原理和過程，以及本文提出的COLINBA算法；第4章介紹實驗結(jié)果和對比分析；第5章對本文進行總結(jié)。

2 相關(guān)工作

近幾年，多臂賭博機算法因為能夠有效應(yīng)對冷啟動問題，提升推薦準確性，在推薦算法領(lǐng)域受到越來越多的關(guān)注。

將多臂賭博機運用于推薦，其基本思想是將n件商品視為n個臂的多臂賭博機，搖臂j對應(yīng)商品j，推薦出最優(yōu)商品等價于找到收益最大的搖臂。在第t輪推薦中，向用戶i推薦商品j，并且得到該用戶的反饋值。推薦系統(tǒng)的目的是在T輪推薦結(jié)束時，為每位用戶推薦的累積誤差最小，但對于新用戶而言無法預(yù)知商品的真實收益，推薦將會陷入探索開發(fā)困境，即在有限的推薦次數(shù)內(nèi)，根據(jù)當前對每件商品的預(yù)估收益，開發(fā)可獲得最大收益的商品；或者嘗試探索新商品，進而找到全部商品中收益更大的商品。

ε-greedy算法是一種基本的多臂賭博機算法。該算法在第t輪推薦中，以1-ε的概率選擇當前已知可獲得最大反饋的商品，以ε的概率隨機選擇一件新商品，最終根據(jù)用戶真實反饋更新被選中商品的期望與方差。ε-greedy算法將探索與開發(fā)分開考慮，每一次推薦都根據(jù)ε隨機選擇探索或開發(fā)，該算法的優(yōu)點是復(fù)雜度低，但預(yù)測準確度有待提升。

與簡單的隨機探索策略不同，另一類算法稱為置信區(qū)間算法，置信區(qū)間算法假設(shè)商品的實際收益μj與期望收益有很高的概率在置信區(qū)間ct,j內(nèi)，公式如下：

由此可知，置信區(qū)間是與迭代次數(shù)有關(guān)的函數(shù)，當某商品被選擇次數(shù)較少時其置信區(qū)間相對較大，算法傾向于選擇該商品，相當于探索；當商品被選擇多次，其置信區(qū)間不斷減小，算法會傾向于選擇期望反饋大的商品，相當于開發(fā)。隨著不斷地迭代，期望反饋將會越來越精確，置信區(qū)間ct,j越來越小，最終期望反饋將會與真實反饋μj相等。

在置信區(qū)間算法的基礎(chǔ)上，文獻[3]提出了LinUCB（linear upper confidence bound）算法，首次為傳統(tǒng)多臂賭博機算法引入特征的概念，認為用戶特征和用戶選擇的商品的特征之間存在線性關(guān)系，并且用置信區(qū)間衡量探索的收益可靠性，該算法成功運用到雅虎新聞的個性化推薦系統(tǒng)當中，能夠在較少的迭代次數(shù)下快速擬合到新用戶的特征?；谝胩卣鞯亩啾圪€博機思想，文獻[6]提出一種融合矩陣分解的MFLinUCB（linear upper confidence bound with matrix factorization）算法，該算法根據(jù)用戶對商品真實評價與預(yù)測評價的誤差，使用矩陣分解算法更新用戶和商品特征，再對新的特征使用多臂賭博機策略進行商品推薦，實驗結(jié)果表明在收斂速度和準確率等方面比LinUCB更好。

此外，用戶的社交關(guān)系中蘊含著豐富的信息，有助于提升推薦準確率[7]。文獻[5]提出了一種LinUCB算法的改進算法CLUB（cluster of Bandits），該算法認為用戶的相似性能夠體現(xiàn)在特征上，因此可以依據(jù)用戶特征對用戶進行聚類，并且用類簇內(nèi)用戶平均特征代表類內(nèi)所有用戶，從而在為目標用戶推薦時引入用戶協(xié)同，并且在每一輪推薦后根據(jù)目標用戶反饋對該用戶特征以及用戶類簇進行更新。文獻[8]在此基礎(chǔ)上提出同時對用戶與商品進行聚類的COFIBA（collaborative filtering Bandits）算法。文獻[9]提出了一種時間因子，認為用戶反饋與用戶特征會隨著時間而變化。以上算法都是對傳統(tǒng)多臂賭博機算法的改進算法。

根據(jù)上述的算法介紹可知，針對冷啟動問題，過去的算法基本都是先隨機初始化特征，或簡單地提取用戶和商品特征，將其作為算法的輸入，并采用Bandits算法思想進行預(yù)測，但是沒有合理利用上下文信息和相似用戶的協(xié)同作用。為此本文提出了一種結(jié)合上下文的用戶協(xié)同多臂賭博機推薦算法，和一種更加適用于推薦領(lǐng)域的基于文本評價信息提取特征的方法，可以很好地解決特征提取和特征更新問題，并在用戶冷啟動中更快地擬合用戶特征。

3 本文提出的方法

在這一章中，首先介紹了本文算法適用的推薦場景，以及基于的推薦系統(tǒng)模型和預(yù)備知識；然后提出了基于LDA生成模型提取商品潛在特征的方法原理和過程；最后介紹本文提出的COLINBA算法。

3.1 本文模型和預(yù)備知識

本文模型和算法在僅利用商品歷史文本評價的場景下，解決用戶冷啟動問題。由于被推薦對象為新用戶，因此用戶真實特征未知。對新用戶特征進行統(tǒng)一初始化后，希望在盡可能少的推薦次數(shù)內(nèi)，根據(jù)商品特征和新用戶對多輪推薦商品的反饋，即點擊與否，不斷修正用戶特征，使得推薦越來越準確，進而解決用戶冷啟動問題。

在每一輪推薦過程中t=1,2,…,T，針對目標用戶it∈U，系統(tǒng)會為之生成一份含有c件商品的候選商品集，商品集中商品對應(yīng)的潛在特征為Cit={xt,1,xt,2,…,xt,c}??d，特征采用LDA生成模型提取，具體方法會在下一節(jié)中詳細介紹，商品特征維數(shù)與用戶特征維數(shù)都為d。在本文模型中，認為用戶特征與商品特征之間存在線性關(guān)系，即用戶的特征與該用戶感興趣的商品特征之間有較高相似度。系統(tǒng)預(yù)測出用戶最感興趣的商品推薦給用戶，并獲得用戶的反饋結(jié)果。在第t輪推薦中，一方面，由于用戶特征隨著每一輪的推薦和反饋不斷更新，因此之前t-1輪的推薦商品以及用戶每次的反饋都會影響當前推薦。另一方面，在為目標用戶推薦時，引入了鄰居用戶協(xié)同，提升推薦性能。利用特征向量相似度計算方法，總是可以找到與被推薦用戶的特征最為相近的幾位用戶，稱之為鄰居用戶。當用戶特征準確時，目標用戶與鄰居用戶的行為偏好最為相近。但由于本文旨在解決用戶冷啟動問題，即在第一次推薦或推薦次數(shù)較少時，擬合到的用戶特征尚不準確，因此根據(jù)特征相似性計算到的鄰居用戶與被推薦用戶的行為偏好偏差較大，對推薦幫助不大，但隨著推薦次數(shù)增加，鄰居用戶協(xié)同的作用會越來越顯著。用戶特征更新細節(jié)以及鄰居用戶協(xié)同過程會在算法部分詳細介紹。

系統(tǒng)為用戶推薦之后，用戶會對推薦結(jié)果進行反饋，這代表推薦的成功與否。在經(jīng)典的結(jié)合上下文的多臂賭博機算法中[3,10]，用戶的偏好用用戶特征向量ui表示的，進而用戶i的反饋值可以由用戶特征ui與商品的潛在特征x計算出：

此外，累計誤差也常用于驗證算法性能。具體而言，在每一輪推薦中，系統(tǒng)都會計算推薦時預(yù)測的用戶反饋與用戶真實反饋之間的差值，定義第t輪學習過程中的誤差rt為：

可見，誤差越小，代表算法的推薦結(jié)果更加接近用戶的真實選擇。本文同樣采用基于點擊率的累計反饋誤差(cumulative regret,CumReg)衡量預(yù)測反饋與真實反饋之間的誤差，表達式為：

其中，j為最終推薦給用戶i的商品，為預(yù)測的反饋結(jié)果，rt為用戶真實的反饋結(jié)果。在本文中，將運用以上方法驗證本文算法在解決推薦問題的有效性。

3.2 提取商品潛在特征

在本節(jié)中，提出了運用LDA主題模型從用戶評價信息中提取商品潛在特征的方法。

文獻[6]提出運用矩陣分解的方法從商品用戶矩陣中提取特征并用于多臂賭博機算法，實驗證明相比LinUCB在收斂速度和準確率方面有所提升。但基于矩陣分解提取特征要求矩陣不能過分稀疏，而在現(xiàn)實場景中，某一用戶反饋過的商品相比于商品總數(shù)是極其稀少的，因此該方法需要剔除掉大量反饋較少的商品和不活躍用戶，從而降低矩陣稀疏性對矩陣分解的影響，但會導(dǎo)致在推薦時商品選擇多樣性降低。另一方面，矩陣分解只能利用評分信息或0-1反饋信息，而無法利用含有更大信息量的文本評價信息。采用本文提出的基于LDA模型提取特征的方法，只需去除少量被評論極少的商品，就可利用評價文本訓(xùn)練得到商品特征，極大地提升了信息利用率，并且保留了更多的候選商品。

LDA是一種非監(jiān)督概率生成模型，可以根據(jù)主題生成文檔，也可以用于提取文檔主題。LDA模型假設(shè)用戶在完成一篇文章時，首先會確定幾個主題，進而從主題對應(yīng)的詞語集中以一定概率選擇詞語。重復(fù)這兩步驟就可生成一篇文章。LDA模型最初由Blei等人在文獻[11]中提出，并應(yīng)用到許多領(lǐng)域，包括郵件分類[12]、社交網(wǎng)絡(luò)[13]、文本切割[14]等。近些年，LDA還被用于推薦系統(tǒng)中的文本推薦[15-16]。

本文認為提取文本主題與提取商品潛在特征存在對應(yīng)關(guān)系，即文章與商品文字評價信息對應(yīng)，文章主題與商品特征對應(yīng)，由此提出運用LDA從用戶評語中提取商品的潛在語義，即商品的潛在特征，因此需要計算LDA模型中的文章-主題多項式概率分布Θ，主題-單詞多項式概率分布Φ。為了便于表述，在下文中統(tǒng)一用文檔表示商品的文字評價信息。由此可以將每件商品在潛在特征空間用文檔-主題概率分布視為商品特征向量。吉布斯抽樣[17]是一種能夠根據(jù)語料庫有效估計LDA生成模型概率分布Θ和Φ的方法。本文采用吉布斯抽樣估計LDA模型的概率分布，通過多輪迭代，對在文檔d中的每個單詞w，根據(jù)條件概率分布P(w|d)為單詞抽樣出特征f，如下所示，直到LDA模型參數(shù)收斂。

由上述分析可知，概率分布Θ可等價于商品的文本評價的潛在主題分布，即商品特征向量。在為新用戶進行多輪推薦的過程中，根據(jù)用戶對每次被推薦商品的反饋，即點擊與否，可用商品特征不斷修正新用戶的初始特征，進而使用戶預(yù)測特征逐漸擬合用戶真實特征。

3.3 本文算法

本節(jié)將介紹本文提出的算法COLINBA的具體內(nèi)容。該算法基于強化學習中的多臂賭博機思想，將商品視為不同的臂，為用戶推薦時在探索與開發(fā)之間權(quán)衡。與傳統(tǒng)的多臂賭博機算法不同，COLINBA引入了鄰居用戶的協(xié)同作用，并基于用戶反饋不斷修正用戶特征。

為了便于描述該算法，本節(jié)重新定義部分模型中的參數(shù)。與文獻[3,8,18]相同，COLINBA采用預(yù)測特征向量ωi,t代表未知的用戶真實特征向量ui。在第t輪推薦中，當為用戶it∈U進行推薦時，系統(tǒng)可以得到其預(yù)測特征向量ωi,t，同時為該用戶隨機生成候選商品池Ci,t={xt,1,xt,2,…,xt,c}?I，商品池內(nèi)商品數(shù)目為c，商品特征是通過LDA模型從商品評價數(shù)據(jù)集中提取出的，特征維度為d。推薦系統(tǒng)將根據(jù)本文提出的算法，為用戶從候選商品集Ci,t中計算出用戶最可能點擊的商品并推薦，進而得到用戶反饋值ri,t。向量ωi,t-1將根據(jù)反饋信息更新，算法的目標就是通過多輪推薦，不斷將用戶i的預(yù)測特征向量ωi,t逼近用戶真實特征向量ui。具體而言，與文獻[3]中提出的LinUCB算法相同，用戶特征向量ωi,t-1由逆矩陣和向量bi,t-1共同決定。由于COLINBA算法主要針對用戶冷啟動問題，因此矩陣Mi,t初始化為d維單位矩陣，向量bi,t的初始化為d維零向量。Mi,t矩陣同時決定著預(yù)測特征向量ωi,t-1趨近于用戶實際向量ui的置信區(qū)間上限CBj?t,t(xt,k)的取值。

本文在為用戶從候選商品池中選擇商品推薦時，引入用戶協(xié)同的思想，進而加快算法的收斂速度，提升推薦的準確度。具體而言，在第t輪推薦中為了能夠從商品池Ci,t中為目標用戶推薦出最佳商品it，本文通過余弦相似度（cosine similarity measure method,COS）[19]計算出目標用戶it的h位最鄰近用戶Ni,t={ui,1,ui,2,…,ui,h}，由鄰居用戶與目標用戶共同構(gòu)造出協(xié)同偏置向量，取代傳統(tǒng)算法中的向量ωi,t-1，向量代表目標用戶it與其h位最鄰近用戶的加權(quán)平均偏好，這意味著COLINBA的推薦結(jié)果由目標用戶與其h位鄰居用戶Ni,t共同決定。但與文獻[18]中僅簡單疊加用戶參數(shù)的方法不同，COLINBA算法中鄰居用戶的影響程度由鄰居用戶與目標用戶的相似度權(quán)重系數(shù)qi,j決定，該系數(shù)為用戶it與鄰居用戶ui,j之間的余弦相似度：

相似度權(quán)重系數(shù)qi,j的取值在-1到1之間，qi,j的取值越靠近1，則鄰居用戶與目標用戶越相近，其對推薦結(jié)果的影響越大，qi,j的取值越靠近-1，則效果相反。與其他算法相似，向量同樣由逆相關(guān)矩陣與向量決定：

其中，參數(shù)α決定著算法在推薦中偏重于探索的程度。

在每一輪推薦完成后，系統(tǒng)將得到用戶it的反饋值ri,t，向量ωi,t-1基于反饋信息更新為ωi,t。本文算法基于為用戶推薦的商品特征更新Mi,t-1、bi,t-1為Mi,t、bi,t，學習率為反饋值ri,t。用戶反饋形式采用用戶點擊反饋，即當用戶點擊了推薦的商品，則ri,t=1，反之ri,t=0。在更新用戶參數(shù)時不考慮協(xié)同的影響，即只對本輪推薦的目標用戶進行更新，其他用戶不參與更新。

算法時間復(fù)雜度方面，基于LDA生成模型提取商品潛在特征是提前在離線條件下完成的，COLINBA算法在時間方面的消耗主要分為兩部分，包括計算用戶之間的相似矩陣，以及為當前用戶推薦時計算候選商品池中所有商品的分數(shù)。其中用戶相似矩陣在實際中通常采取離線計算的方式并周期性更新，而非實時更新。因此，在線推薦過程中只需實時計算用戶協(xié)同特征向量i,t-1和候選池中商品分數(shù)即可。其中，計算用戶協(xié)同特征向量i,t-1的時間復(fù)雜度為O(dj)，d表示用戶和商品特征維數(shù)，j表示用戶鄰居數(shù)，計算商品分數(shù)的時間復(fù)雜度為O(dc)，c表示商品

其中，與傳統(tǒng)多臂賭博機算法相同，CBi,t-1(xt,k)為向量近似于用戶真實向量ui的置信區(qū)間上界。池中的商品數(shù)。因此本文算法為一位用戶推薦一次的時間復(fù)雜度為O(d(j+c))，即時間復(fù)雜度與特征維數(shù)、鄰居數(shù)與商品池中商品數(shù)的和成正比，適合用于大規(guī)模數(shù)據(jù)集的推薦。

4 實驗部分

在本章中，將采用真實的數(shù)據(jù)集Delicious和Last.fm模擬在線推薦過程，基于LDA生成模型提取商品的潛在特征，對本文提出的COLINBA算法與作為對比的 LinUCB、MFLinUCB、DynUCB（dynamic clustering of contextual multi-armed Bandits）和COFIBA等算法進行實驗評估。采用的評價指標包括點擊率CTR和累計誤差CumReg，實驗表明本文算法較其他算法有一定提升。

4.1 數(shù)據(jù)集

Delicious數(shù)據(jù)集采集自社交書簽網(wǎng)站Delicious，其包含1 861位用戶和69 226件商品（URL），以及用戶對這些URL所打的文本評價標簽53 388種。本文基于被打標簽的URL來生成用戶反饋信息：如果某一用戶對某一URL打過標簽，則認為用戶對該URL的反饋為1，否則為0。Last.fm數(shù)據(jù)集采集自音樂流服務(wù)Last.fm，其包含1 892位用戶，17 632件商品（歌手），以及11 946種文本評價標簽。采用同樣的方式定義某用戶對某商品的反饋值。

Delicious和Last.fm數(shù)據(jù)集中存在部分商品僅有極少用戶對其打過標簽，將這些商品的標簽集合視為文章則意味著文章內(nèi)文本量極少，基于LDA主題模型從這樣的文章中提取到的主題向量將會存在大量0值和非常接近于0的數(shù)值，從而無法準確表征商品，在后續(xù)推薦過程中會對推薦準確率和用戶特征迭代產(chǎn)生誤導(dǎo)。因此，針對Delicious數(shù)據(jù)集，首先對商品按照評價數(shù)進行排序，剔除了評價數(shù)較少的部分噪聲商品，保留了熱度較高的3萬件商品，然后基于新構(gòu)建的數(shù)據(jù)集，對用戶活躍度進行排序，保留較為活躍的1 000名用戶。對于Last.fm數(shù)據(jù)集，同樣保留評價數(shù)較多的1萬件商品和較為活躍的1 000名用戶。

4.2 離線模擬在線推薦

在線推薦場景中，根據(jù)推薦算法可預(yù)測用戶點擊概率最大的前k件商品，展示給用戶，根據(jù)用戶真實的點擊反饋，更新模型和相應(yīng)參數(shù)并再次推薦，使得推薦準確性不斷提升。

本文基于Delicious和Last.fm數(shù)據(jù)集，采用離線模擬在線推薦的方法，仿真本文算法的推薦效果。具體而言，數(shù)據(jù)集中的信息為用戶對商品的評價信息，進而可理解為用戶對其評價過的商品是有過點擊行為的。本文算法希望解決用戶冷啟動問題，因此在實驗中用戶都為新用戶，即在預(yù)測推薦商品時，假設(shè)用戶在數(shù)據(jù)集中的點擊行為是未知的。根據(jù)本文算法預(yù)測得到用戶可能點擊的商品后，再參照該用戶在數(shù)據(jù)集中的真實點擊記錄，若預(yù)測商品恰為用戶點擊過的商品，則認為用戶反饋為1，推薦成功，反之用戶反饋為0，推薦失敗，即用數(shù)據(jù)集中的用戶點擊記錄模擬用戶對推薦商品的反饋行為。具體為每一位用戶推薦時，為更接近真實應(yīng)用場景，并未從所有商品中選擇，而是先構(gòu)建一個含有20件商品的商品集，其中一件從該用戶真實點擊過的商品中隨機生成，其他19件為用戶未點擊過的負例商品。若根據(jù)算法計算得分最高的商品恰為正例，則推薦成功；若預(yù)測結(jié)果為負例，則代表用戶不會點擊，推薦失敗。根據(jù)用戶反饋結(jié)果更新模型和相應(yīng)參數(shù)，并再次推薦。

4.3 構(gòu)建商品潛在特征

本文實驗在提取商品特征時，同樣基于Delicious和Last.fm數(shù)據(jù)集，即利用商品的歷史評價信息提取商品特征。在現(xiàn)實場景中僅需收集足夠多老用戶對某商品的文本評價，就可基于LDA主題模型生成該商品的潛在特征，并且評價越多，特征的表征準確性越高。

首先對數(shù)據(jù)集內(nèi)標簽單詞進行清洗，將每一個商品的所有標簽單詞裝入對應(yīng)的文檔中，從而構(gòu)建出每個商品的標簽單詞集。然后將其輸入LDA模型計算商品-潛在主題概率分布和單詞主題概率分布。具體而言，首先要設(shè)定LDA生成模型的狄利克雷概率分布參數(shù)α和β，以及主題數(shù)D。在文獻[17]中，提出了參數(shù)的最優(yōu)設(shè)定方法，β=0.1和α=50/D，本文采用該標準計算模型參數(shù)?？梢姡P(guān)鍵要選取合理的主題數(shù)D，文獻[11]提出了具有良好適應(yīng)性的Perplexity指標，可用來評價主題數(shù)對模型的影響：

該指標的值越小代表模型性能越好。因此，通過改變主題數(shù)，即商品特征的維度，觀察Perplexity的趨勢，在最低點時即為最佳值。得到圖1性能曲線。

Fig.1 Perplexity of LDA model on different number of topics圖1 LDA模型的困惑度隨主題數(shù)的變化

結(jié)果顯示當模型主題數(shù)為50時，Perplexity取得最小值，模型性能達到最優(yōu)。因此本文設(shè)定潛在主題數(shù)為50，即特征維度為50。

常用的商品特征提取方法還包括矩陣分解，如之前所述，該方法僅利用了用戶對商品的評分或0-1反饋，而引入自然語言處理中的主題模型可以挖掘商品評價信息進而構(gòu)建商品潛在特征，常用的方法有TF-IDF（term frequency-inverse document frequency）、LDA模型。表1對比了通過以上三種方法提取商品特征后，基于本文COFIBA算法推薦并迭代10 000次時的CTR，其中LDA_0.5代表僅利用50%的評價文本訓(xùn)練商品特征。實驗結(jié)果表明，在兩數(shù)據(jù)集上，基于文本主題提取方法TF-IDF、LDA能得到更高的點擊率，因為其利用了信息量更大的商品評價文本，能夠更加準確地表征商品特征，其中LDA的效果更佳。此外，當僅用一半的文本訓(xùn)練LDA模型時，CTR會急劇下降，因此在實際運用中，商品的評價信息越豐富，提取到的特征表征效果越好。

Table 1 CTR based on different feature extraction methods表1 基于不同特征提取方法的點擊率

4.4 評價指標

本文采用文獻[3]中的評價方法，使用離線數(shù)據(jù)集模擬在線推薦過程，不劃分訓(xùn)練集和驗證集，在整個數(shù)據(jù)集上計算CTR和CumReg隨迭代增加的變化情況，衡量算法性能。公式如下所述：

其中，ri,t為用戶i的真實反饋，為預(yù)測反饋值，n為用戶總數(shù)。CTR表示每一輪推薦的商品得到用戶反饋的次數(shù)占用戶總數(shù)n的比值，最大值為1。CumReg表示每一輪推薦n位用戶預(yù)測反饋與真實反饋的累計誤差。

如4.2節(jié)所述，當每一次為用戶推薦時，需要隨機生成候選商品池Ci,t={xt,1,xt,2,…,xt,c}?I，商品數(shù)c=20，其中第一件商品xt,1為隨機抽取一件原數(shù)據(jù)集中用戶it真實點擊的商品，其余19件從該用戶未點擊的商品中隨機抽取。如果算法為用戶推薦的商品恰為該用戶點擊過的商品，則認為推薦成功，用戶反饋值ri,t=1，否則ri,t=0，從而模擬在線推薦和反饋的過程。

4.5 對比算法介紹

本文提出的算法為引入?yún)f(xié)同過濾的多臂賭博機算法，因此對比算法分為兩大類：第一類為未引入?yún)f(xié)同的LinUCB算法[3]和MFLinUCB算法[6]，LinUCB默認用戶和商品的潛在特征與最終預(yù)測反饋值之間存在線性關(guān)系，進而提出了結(jié)合上下文語境的多臂賭博機算法，MFLinUCB在LinUCB的基礎(chǔ)上融入矩陣分解算法，提出使用矩陣分解算法更新用戶的特征。第二類為基于聚類方法進而引入鄰居用戶協(xié)同作用的多臂賭博機算法，DynUCB[18]和 COFIBA[8]，DynUCB基于傳統(tǒng)的k-means算法進行動態(tài)聚類。COFIBA則采用在用戶和商品兩方面同時動態(tài)聚類的方法引入?yún)f(xié)同的效果。

4.6 結(jié)果分析

為便于比較不同算法的性能，在計算累積誤差Cum Re g時以隨機推薦為基礎(chǔ)，計算各種算法測試結(jié)果與隨機推薦測試結(jié)果的比值，作為相對測試結(jié)果，下文中都以相對測試結(jié)果進行分析。并且所有算法用到的特征采用相同維度，都采用本文提出的LDA特征提取方法計算商品特征。

首先以CTR作為指標，衡量COLINBA算法的參數(shù)α的取值，以及鄰居用戶數(shù)m對推薦結(jié)果的影響。分別從Delicious數(shù)據(jù)集中的1 861名用戶和Last.fm數(shù)據(jù)集中的1 892名用戶中隨機選擇300名用戶作為測試推薦對象，測試在基于兩數(shù)據(jù)集迭代10 000次的條件下參數(shù)α對CTR的影響，以及鄰居用戶數(shù)m對CTR的影響。測試結(jié)果如圖2、圖3所示。

Fig.2 CTRof COLINBA on different values ofα圖2 α取不同值時COLINBA算法的CTR

根據(jù)圖2可知，參數(shù)α的取值變化會對推薦結(jié)果產(chǎn)生影響，且在不同數(shù)據(jù)集中的影響程度不同。具體而言，Delicious數(shù)據(jù)集的α最優(yōu)值為0.25；Last.fm數(shù)據(jù)集的α最優(yōu)值為0.35。在后續(xù)對比實驗中，對于COLINBA算法均采用上述α最優(yōu)值。

圖3中，柱狀圖表示COLINBA算法中鄰居用戶數(shù)m的取值變化對點擊率的影響，直線A代表鄰居用戶的權(quán)重因子設(shè)置為0的情況，即不采用鄰居用戶協(xié)同僅根據(jù)目標用戶特征推薦時的用戶點擊率，直線B為50位鄰居用戶的權(quán)重因子全部設(shè)置為1，即用目標用戶與50位鄰居用戶的平均特征代替目標用戶特征時的點擊率，可等效為將相似用戶聚類后的類簇整體特征代替用戶特征的推薦結(jié)果?？梢姡珻OLINBA中引入帶有鄰居相似權(quán)重因子的鄰居協(xié)同能夠提高點擊率，并且鄰居用戶個數(shù)也會影響推薦準確率，其中，當鄰居數(shù)為20時，用戶的點擊率最高。并且繼續(xù)增加鄰居數(shù)時，點擊率開始小幅度下降，這是因為隨著鄰居數(shù)的增多，大量與目標用戶相似度低的用戶也被當作了鄰居用戶參與協(xié)同過濾，從而會對推薦結(jié)果產(chǎn)生錯誤的影響，但由于引入了相似度權(quán)重因子，從而控制這些用戶的影響程度較小，當鄰居用戶增多時點擊率下降比較緩慢。此外，不采用協(xié)同過濾思想方法推薦結(jié)果較差，直接將鄰居用戶特征向量相加的方法的推薦結(jié)果更差，因為后者在為目標用戶推薦時，大量不相關(guān)的用戶起到了很大的作用，從而導(dǎo)致推薦結(jié)果不是用戶真正感興趣的商品。

在Delicious和Last.fm數(shù)據(jù)集上，以相對累計誤差CumReg作為評價指標，各種算法的結(jié)果如圖4所示。

根據(jù)圖4可知，各算法性能均優(yōu)于隨機推薦。在Delicious數(shù)據(jù)集上，LinUCB收斂速度最快，但其收斂后累積誤差最大。DynUCB算法和MFLinUCB算法性能有所提升。COLINBA和COFIBA的性能最好，COLINBA算法收斂后的累計誤差最小，為0.80，但其收斂速度比COFIBA稍慢。在Last.fm數(shù)據(jù)集上，LinUCB、DynUCB和MFLinUCB收斂速度較快，但是累積誤差最大，在迭代20 000次時收斂累計誤差為0.81、0.79和0.78。COLINBA和COFIBA性能最好，在迭代到25 000次時累計誤差達到最小值0.74和0.76。

以相對累積誤差作為評測指標時，在兩個數(shù)據(jù)集上測試結(jié)果都顯示本文提出的COLINBA算法在準確度上有一定的提升。以CTR作為評價指標，各算法的結(jié)果如圖5所示。

可見，在Delicious和Last.fm數(shù)據(jù)集上，以點擊率作為評價指標，仍然是COLINBA和COFIBA的性能最好，但在迭代至收斂時，COLINBA的點擊率更高。在Delicious數(shù)據(jù)集上，LinUCB算法迭代15 000次達到最優(yōu)值0.17，DynUCB算法迭代15 000次達到最優(yōu)值0.22，MFLinUCB算法迭代15 000次達到最優(yōu)值0.23。COFIBA算法的收斂速度最快，迭代10 000次達到最優(yōu)值0.24。COLINBA的點擊率最高，迭代20 000次達到最優(yōu)值0.27。在Last.fm數(shù)據(jù)集上Lin-UCB算法收斂速度最快，但是最優(yōu)值僅為0.19。Dyn-UCB算法迭代15 000次達到最優(yōu)值0.22。MFLin-UCB算法迭代20 000次達到最優(yōu)值0.23。COFIBA算法迭代20 000次達到最優(yōu)值0.24，COLINBA算法的點擊率最高，迭代25 000次達到最優(yōu)值0.25。

Fig.5 CTRof 5 algorithms varying with the number of iterations on 2 datasets圖5 在兩數(shù)據(jù)集上5種算法的CTR隨迭代次數(shù)的變化情況

由上面的結(jié)果分析，可以得到以下一般性結(jié)論：LinUCB算法為Bandits算法引入了特征的思想，采用置信區(qū)間上界算法對新用戶進行推薦，并認為回報和相關(guān)特征成線性關(guān)系，在算法迭代初期有很好的效果，但隨著迭代次數(shù)增加，其性能無法持續(xù)提升。該算法在較短時間內(nèi)可獲得較好推薦效果，因此適用于簡單并需要快速處理的應(yīng)用場景。

MFLinUCB算法在LinUCB的基礎(chǔ)上融合了矩陣分解算法，在推薦過程中根據(jù)用戶對商品真實評價與預(yù)測評價的誤差，使用矩陣分解算法更新用戶特征，再對新的特征使用多臂賭博機算法進行商品推薦。該算法相比LinUCB在性能上有所提升，并且更加適應(yīng)稀疏數(shù)據(jù)。

DynUCB算法在LinUCB的基礎(chǔ)上采用傳統(tǒng)的k-means算法對用戶進行聚類，用聚類的整體特征代替類簇內(nèi)用戶特征，從而引入了相似用戶的協(xié)同作用，在迭代初期效果不錯，但是隨著迭代次數(shù)的增加，用聚類整體特征與用戶實際特征偏差較大，無法獲得更好的推薦結(jié)果。

COFIBA算法和DynUCB算法相比，采用同時對用戶和商品聚類的方法，在用戶和商品兩方面同時引入了協(xié)同的效果，其推薦結(jié)果比DynUCB更好。

COLINBA算法引入了帶有相似度權(quán)重因子的鄰居用戶的協(xié)同作用，從而在鄰居用戶協(xié)同的同時保證了用戶本身行為偏好的重要性。實驗表明隨著迭代次數(shù)的增加，能夠取得更好的推薦效果。

根據(jù)實驗結(jié)果顯示，不同的算法在不同的數(shù)據(jù)集上表現(xiàn)略有不同。對于COLINBA算法，其在Delicious數(shù)據(jù)集的測試結(jié)果要好于Last.fm，故在實際推薦應(yīng)用中，要根據(jù)實際數(shù)據(jù)集情況選擇恰當?shù)乃惴ā?/p>

5 結(jié)束語

本文提出一種引入鄰居協(xié)同的多臂賭博機推薦算法COLINBA，基于LDA主題模型提取文本潛在主題的原理，提取商品特征，并根據(jù)用戶反饋不斷修正用戶特征向量。該算法具有很好的通用性，能深入挖掘商品評價信息，并利用用戶協(xié)同提升推薦性能。采用真實數(shù)據(jù)集進行測試并分析實驗結(jié)果，驗證了本文算法的有效性。下一步將會考慮同時利用用戶、商品之間的相似信息構(gòu)造協(xié)同過濾模型，進一步提高推薦精度。