王宇琛，王寶亮，侯永宏

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

1 引言

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

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

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

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

本文基于以上研究背景，提出了能有效解決用戶冷啟動的協(xié)同過濾線性多臂賭博機(jī)算法（collaborative filtering context linear Bandits,COLINBA），該算法與之前相關(guān)算法相比，在結(jié)合上下文的多臂賭博機(jī)算法基礎(chǔ)上，引入了更加精細(xì)的協(xié)同效果。當(dāng)為目標(biāo)用戶推薦商品時由用戶與其鄰居用戶共同決定，并且通過鄰居用戶相似度權(quán)重因子控制鄰居用戶對推薦的貢獻(xiàn)程度，從而保證目標(biāo)用戶自身特征起主導(dǎo)作用，且引入了協(xié)同效果，優(yōu)化推薦性能。此外，相比文獻(xiàn)[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章對本文進(jìn)行總結(jié)。

2 相關(guān)工作

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

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

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

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

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

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

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

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

3 本文提出的方法

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

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

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

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

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

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

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

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

3.2 提取商品潛在特征

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

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

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

本文認(rèn)為提取文本主題與提取商品潛在特征存在對應(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ìn)行多輪推薦的過程中，根據(jù)用戶對每次被推薦商品的反饋，即點擊與否，可用商品特征不斷修正新用戶的初始特征，進(jìn)而使用戶預(yù)測特征逐漸擬合用戶真實特征。

3.3 本文算法

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

為了便于描述該算法，本節(jié)重新定義部分模型中的參數(shù)。與文獻(xiàn)[3,8,18]相同，COLINBA采用預(yù)測特征向量ωi,t代表未知的用戶真實特征向量ui。在第t輪推薦中，當(dāng)為用戶it∈U進(jìn)行推薦時，系統(tǒng)可以得到其預(yù)測特征向量ωi,t，同時為該用戶隨機(jī)生成候選商品池Ci,t={xt,1,xt,2,…,xt,c}?I，商品池內(nèi)商品數(shù)目為c，商品特征是通過LDA模型從商品評價數(shù)據(jù)集中提取出的，特征維度為d。推薦系統(tǒng)將根據(jù)本文提出的算法，為用戶從候選商品集Ci,t中計算出用戶最可能點擊的商品并推薦，進(jìn)而得到用戶反饋值ri,t。向量ωi,t-1將根據(jù)反饋信息更新，算法的目標(biāo)就是通過多輪推薦，不斷將用戶i的預(yù)測特征向量ωi,t逼近用戶真實特征向量ui。具體而言，與文獻(xiàn)[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é)同的思想，進(jìn)而加快算法的收斂速度，提升推薦的準(zhǔn)確度。具體而言，在第t輪推薦中為了能夠從商品池Ci,t中為目標(biāo)用戶推薦出最佳商品it，本文通過余弦相似度（cosine similarity measure method,COS）[19]計算出目標(biāo)用戶it的h位最鄰近用戶Ni,t={ui,1,ui,2,…,ui,h}，由鄰居用戶與目標(biāo)用戶共同構(gòu)造出協(xié)同偏置向量，取代傳統(tǒng)算法中的向量ωi,t-1，向量代表目標(biāo)用戶it與其h位最鄰近用戶的加權(quán)平均偏好，這意味著COLINBA的推薦結(jié)果由目標(biāo)用戶與其h位鄰居用戶Ni,t共同決定。但與文獻(xiàn)[18]中僅簡單疊加用戶參數(shù)的方法不同，COLINBA算法中鄰居用戶的影響程度由鄰居用戶與目標(biāo)用戶的相似度權(quán)重系數(shù)qi,j決定，該系數(shù)為用戶it與鄰居用戶ui,j之間的余弦相似度：

相似度權(quán)重系數(shù)qi,j的取值在-1到1之間，qi,j的取值越靠近1，則鄰居用戶與目標(biāo)用戶越相近，其對推薦結(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，學(xué)習(xí)率為反饋值ri,t。用戶反饋形式采用用戶點擊反饋，即當(dāng)用戶點擊了推薦的商品，則ri,t=1，反之ri,t=0。在更新用戶參數(shù)時不考慮協(xié)同的影響，即只對本輪推薦的目標(biāo)用戶進(jìn)行更新，其他用戶不參與更新。

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

其中，與傳統(tǒng)多臂賭博機(jī)算法相同，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等算法進(jìn)行實驗評估。采用的評價指標(biāo)包括點擊率CTR和累計誤差CumReg，實驗表明本文算法較其他算法有一定提升。

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

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

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

4.2 離線模擬在線推薦

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

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

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

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

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

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

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

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

常用的商品特征提取方法還包括矩陣分解，如之前所述，該方法僅利用了用戶對商品的評分或0-1反饋，而引入自然語言處理中的主題模型可以挖掘商品評價信息進(jìn)而構(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能得到更高的點擊率，因為其利用了信息量更大的商品評價文本，能夠更加準(zhǔn)確地表征商品特征，其中LDA的效果更佳。此外，當(dāng)僅用一半的文本訓(xùn)練LDA模型時，CTR會急劇下降，因此在實際運用中，商品的評價信息越豐富，提取到的特征表征效果越好。

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

4.4 評價指標(biāo)

本文采用文獻(xiàn)[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é)所述，當(dāng)每一次為用戶推薦時，需要隨機(jī)生成候選商品池Ci,t={xt,1,xt,2,…,xt,c}?I，商品數(shù)c=20，其中第一件商品xt,1為隨機(jī)抽取一件原數(shù)據(jù)集中用戶it真實點擊的商品，其余19件從該用戶未點擊的商品中隨機(jī)抽取。如果算法為用戶推薦的商品恰為該用戶點擊過的商品，則認(rèn)為推薦成功，用戶反饋值ri,t=1，否則ri,t=0，從而模擬在線推薦和反饋的過程。

4.5 對比算法介紹

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

4.6 結(jié)果分析

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

首先以CTR作為指標(biāo)，衡量COLINBA算法的參數(shù)α的取值，以及鄰居用戶數(shù)m對推薦結(jié)果的影響。分別從Delicious數(shù)據(jù)集中的1 861名用戶和Last.fm數(shù)據(jù)集中的1 892名用戶中隨機(jī)選擇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ù)目標(biāo)用戶特征推薦時的用戶點擊率，直線B為50位鄰居用戶的權(quán)重因子全部設(shè)置為1，即用目標(biāo)用戶與50位鄰居用戶的平均特征代替目標(biāo)用戶特征時的點擊率，可等效為將相似用戶聚類后的類簇整體特征代替用戶特征的推薦結(jié)果?？梢?，COLINBA中引入帶有鄰居相似權(quán)重因子的鄰居協(xié)同能夠提高點擊率，并且鄰居用戶個數(shù)也會影響推薦準(zhǔn)確率，其中，當(dāng)鄰居數(shù)為20時，用戶的點擊率最高。并且繼續(xù)增加鄰居數(shù)時，點擊率開始小幅度下降，這是因為隨著鄰居數(shù)的增多，大量與目標(biāo)用戶相似度低的用戶也被當(dāng)作了鄰居用戶參與協(xié)同過濾，從而會對推薦結(jié)果產(chǎn)生錯誤的影響，但由于引入了相似度權(quán)重因子，從而控制這些用戶的影響程度較小，當(dāng)鄰居用戶增多時點擊率下降比較緩慢。此外，不采用協(xié)同過濾思想方法推薦結(jié)果較差，直接將鄰居用戶特征向量相加的方法的推薦結(jié)果更差，因為后者在為目標(biāo)用戶推薦時，大量不相關(guān)的用戶起到了很大的作用，從而導(dǎo)致推薦結(jié)果不是用戶真正感興趣的商品。

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

根據(jù)圖4可知，各算法性能均優(yōu)于隨機(jī)推薦。在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次時累計誤差達(dá)到最小值0.74和0.76。

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

可見，在Delicious和Last.fm數(shù)據(jù)集上，以點擊率作為評價指標(biāo)，仍然是COLINBA和COFIBA的性能最好，但在迭代至收斂時，COLINBA的點擊率更高。在Delicious數(shù)據(jù)集上，LinUCB算法迭代15 000次達(dá)到最優(yōu)值0.17，DynUCB算法迭代15 000次達(dá)到最優(yōu)值0.22，MFLinUCB算法迭代15 000次達(dá)到最優(yōu)值0.23。COFIBA算法的收斂速度最快，迭代10 000次達(dá)到最優(yōu)值0.24。COLINBA的點擊率最高，迭代20 000次達(dá)到最優(yōu)值0.27。在Last.fm數(shù)據(jù)集上Lin-UCB算法收斂速度最快，但是最優(yōu)值僅為0.19。Dyn-UCB算法迭代15 000次達(dá)到最優(yōu)值0.22。MFLin-UCB算法迭代20 000次達(dá)到最優(yōu)值0.23。COFIBA算法迭代20 000次達(dá)到最優(yōu)值0.24，COLINBA算法的點擊率最高，迭代25 000次達(dá)到最優(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ū)間上界算法對新用戶進(jìn)行推薦，并認(rèn)為回報和相關(guān)特征成線性關(guān)系，在算法迭代初期有很好的效果，但隨著迭代次數(shù)增加，其性能無法持續(xù)提升。該算法在較短時間內(nèi)可獲得較好推薦效果，因此適用于簡單并需要快速處理的應(yīng)用場景。

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

DynUCB算法在LinUCB的基礎(chǔ)上采用傳統(tǒng)的k-means算法對用戶進(jìn)行聚類，用聚類的整體特征代替類簇內(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ù)集情況選擇恰當(dāng)?shù)乃惴ā?/p>

5 結(jié)束語

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