熊智，徐愷，蔡玲如，蔡偉鴻

（1.汕頭大學(xué)計算機(jī)科學(xué)與技術(shù)系，廣東 汕頭 515063；2.汕頭大學(xué)智能制造技術(shù)教育部重點實驗室，廣東 汕頭 515063）

1 引言

隨著計算機(jī)技術(shù)的發(fā)展與應(yīng)用，越來越多的用戶通過網(wǎng)絡(luò)獲取信息，使互聯(lián)網(wǎng)上的數(shù)據(jù)呈爆發(fā)式增長趨勢。如何在“信息超載”的時代為用戶進(jìn)行精準(zhǔn)推薦是目前眾多學(xué)者所關(guān)注的問題。推薦系統(tǒng)能夠根據(jù)用戶喜好過濾冗余的信息進(jìn)而為用戶自動推薦[1]。推薦系統(tǒng)使用戶能夠更加快速地獲取自己感興趣的信息，節(jié)省用戶的時間成本，增強(qiáng)產(chǎn)品的用戶體驗。近年來，推薦系統(tǒng)得到了廣泛應(yīng)用，推薦算法的種類也越來越多樣化[1-2]。

目前，主流的推薦算法主要包括基于協(xié)同過濾的推薦算法[3-5]、基于矩陣分解的推薦算法[6-7]、基于關(guān)系網(wǎng)絡(luò)的推薦算法[8]、基于機(jī)器學(xué)習(xí)的推薦算法[9-11]和混合推薦算法[12]等。基于協(xié)同過濾的推薦算法和基于矩陣分解的推薦算法往往只構(gòu)建用戶和項目之間的評分矩陣，根據(jù)相似用戶進(jìn)行推薦?；陉P(guān)系網(wǎng)絡(luò)的推薦算法挖掘用戶與用戶、項目與項目之間更深層次的聯(lián)系，利用圖或網(wǎng)的形式進(jìn)行推薦，它與基于機(jī)器學(xué)習(xí)的推薦算法一樣，當(dāng)用戶及項目數(shù)量較大時，算法的計算量較大，因此通常需要高性能硬件環(huán)境的支撐。在一個實際的推薦系統(tǒng)中，所能獲得的數(shù)據(jù)除了用戶對項目的評分，通常還包含項目的分類情況，例如，小說可以分成科幻、歷史等類別，電影可以分為喜劇、戰(zhàn)爭、動畫等類別。如果能很好地利用項目的類別信息，將有助于提升推薦質(zhì)量。然而，上述推薦算法僅依據(jù)評分?jǐn)?shù)據(jù)進(jìn)行推薦，忽略了項目的類別信息。

張量是矢量概念和矩陣概念的推廣，它可以表示更高維度的數(shù)據(jù)。近些年來，有些研究開始引入評分?jǐn)?shù)據(jù)之外的信息構(gòu)建三維張量，例如類別信息和時間信息等，進(jìn)而設(shè)計推薦算法。相對于二維的評分?jǐn)?shù)據(jù)，考慮了其他維度信息的三維張量更加稀疏和復(fù)雜。文獻(xiàn)[13]在電影推薦中將用戶?電影?類別組成的三維張量拆分為用戶?電影、電影?類別的雙邊關(guān)系，然后使用矩陣分解等算法進(jìn)行處理并推薦。文獻(xiàn)[14]構(gòu)建用戶?項目?時間的三維張量，提出一種基于審美的衣服推薦算法，但是也將三維張量轉(zhuǎn)化成多個二維矩陣進(jìn)行處理，雖然考慮了三維的數(shù)據(jù)信息，但丟失了數(shù)據(jù)之間整體的聯(lián)系性。文獻(xiàn)[15]構(gòu)建用戶?標(biāo)簽?項目的三維張量用于標(biāo)簽推薦，利用低階多項式改進(jìn)了用戶、項目和標(biāo)簽之間的統(tǒng)計信息，同時解決了數(shù)據(jù)稀疏性問題。盡管其相對于經(jīng)典的CP（CANDECOMP/PARAFAC）分解和Tuker分解[16]在時間和空間的復(fù)雜性上都有所改善，但是計算成本依然相對較高，因而只能用于小規(guī)模的三維張量。文獻(xiàn)[17]利用高階奇異值分解（HOSVD,high order singular value decomposition）進(jìn)行音樂推薦。并通過音樂之間的相似性來解決數(shù)據(jù)稀疏性問題。文獻(xiàn)[18]在標(biāo)簽推薦上采用了與文獻(xiàn)[17]類似的方式，但這2種方法都沒有采用迭代處理提升準(zhǔn)確度。

在一些大型系統(tǒng)中，項目和用戶的數(shù)量都很龐大，而用戶評分過的項目通常很少，2個用戶共同評分過的項目更少，解決數(shù)據(jù)稀疏問題是提高推薦質(zhì)量的關(guān)鍵。張量填補(bǔ)是解決數(shù)據(jù)稀疏性的一種常用方法。文獻(xiàn)[19]通過張量因式分解的形式填補(bǔ)張量中的缺失值，但它只適用于N×N×N的張量。文獻(xiàn)[20]提出利用黎曼流形和非線性梯度下降的方式來填補(bǔ)張量中的缺失值，雖然能處理更高維度的數(shù)據(jù)，但要求張量的秩已知或者可以被測量。

推薦算法要向用戶推薦其喜歡的項目，也就是說要“投其所好”。如果能從已有的數(shù)據(jù)中分析挖掘用戶的偏好信息，并在推薦算法中加以應(yīng)用，將會使推薦更加切合用戶的需求，有助于提高推薦效果[21]。因此，本文綜合考慮用戶的項目類別偏好和評分偏好，提出了一種基于張量填補(bǔ)和用戶偏好的聯(lián)合推薦（TCUP,tensor completion and user preference）算法。首先，基于評分矩陣和項目所屬類別矩陣構(gòu)建用戶?項目?類別的三維張量；然后，利用Frank-Wolfe算法進(jìn)行迭代計算，填補(bǔ)張量中的缺失數(shù)據(jù)，同時基于張量數(shù)據(jù)構(gòu)建用戶類別偏好矩陣和評分偏好矩陣；最后，基于填補(bǔ)后的三維張量以及2個偏好矩陣設(shè)計了聯(lián)合推薦算法，并采用差分進(jìn)化算法進(jìn)行參數(shù)調(diào)優(yōu)。為了驗證TCUP算法的有效性，本文使用MovieLens[22]數(shù)據(jù)集進(jìn)行測試。在4種不同規(guī)模數(shù)據(jù)集下的實驗結(jié)果表明，TCUP算法的數(shù)據(jù)填補(bǔ)效果和推薦效果優(yōu)于一些常用和新近提出的算法。

2 相關(guān)知識

2.1 張量的相關(guān)符號及計算式

本文中，向量和矩陣分別用小寫和大寫的加粗字母表示，張量用加粗的花體字母表示。文中涉及的相關(guān)符號和計算式如下。

A表示矩陣的張量化，它表示一個張量，其沿第d維的展開矩陣為A，即(X)=X。

為了便于理解張量的矩陣化和矩陣的張量化，下面給出一個三階張量的示例（文中所述張量皆為三階張量）。假設(shè)X為圖1所示的3×4×2的張量，即X∈R3×4×2。

圖1 張量示例

那么，張量X的矩陣化可表示為如式(1)～式(3)所示的形式。

2.2 FW算法

FW（Frank-Wolfe）算法是一種求解受限（帶約束）凸優(yōu)化問題的方法。它采用迭代計算的方式，將非線性優(yōu)化問題轉(zhuǎn)換成一系列線性優(yōu)化問題進(jìn)行求解。FW算法能夠應(yīng)用于矩陣分解，并能保證較好的收斂性[23]。假設(shè)有優(yōu)化問題，其中，f(x)是連續(xù)可微的凸函數(shù)，D為凸形緊集，即在集合D內(nèi)最小化f(x)的值。FW算法求解該問題的流程如算法1所示。

算法1Frank-Wolfe算法

1)設(shè)置最大迭代次數(shù)T。

2)初始化一個解x(0)，當(dāng)前迭代次數(shù)t=0。

5)進(jìn)行一次迭代，x(t+1)=x(t)+γ(t+1)?(s(t+1)-x(t))。

6)更新當(dāng)前迭代次數(shù)，t=t+1。

7)當(dāng)前迭代次數(shù)t是否達(dá)到最大迭代次數(shù)T，若是則停止迭代并輸出x(t)，否則重復(fù)步驟3)～步驟6)。

3 聯(lián)合推薦算法

基于張量填補(bǔ)和用戶偏好的聯(lián)合推薦算法包括以下4個步驟：張量構(gòu)建、張量填補(bǔ)、偏好構(gòu)建和聯(lián)合推薦，如圖2所示。下面分別介紹這4個步驟。

圖2 聯(lián)合推薦算法的步驟

3.1 張量構(gòu)建

根據(jù)用戶對項目的評分?jǐn)?shù)據(jù)和項目所屬的類別數(shù)據(jù)可分別構(gòu)建矩陣M和N。矩陣M中記錄用戶對項目的評分，如果某個用戶對某個項目有評分，則對應(yīng)的元素為該評分值，否則為0。矩陣N記錄項目所屬的類別，如果某個項目屬于某個類別，則對應(yīng)的元素為1，否則為0。一個項目可以屬于多個類別。

根據(jù)矩陣M和N可構(gòu)建2個三維張量A和B如式(4)和式(5)所示。

其中，u、i和c分別表示用戶、項目和類別的坐標(biāo)。此外，本文用U、I和C分別表示用戶、項目和類別的數(shù)量。

3.2 張量填補(bǔ)

張量A通常非常稀疏，本文利用張量填補(bǔ)的方式來填補(bǔ)其中缺失的數(shù)據(jù)。對于已知的D（這里D=3）維張量A，假設(shè)令A(yù)中元素不為0的坐標(biāo)構(gòu)成的集合為Ω，其張量填補(bǔ)可表述成如下優(yōu)化問題：尋找一個與A規(guī)模相同的張量X，使

其中，PΩ(X-A)是一個張量，當(dāng)（i1,i2,…iD）∈Ω時，，否則。該張量填補(bǔ)問題即為，找一個秩不超過τ的張量X，使在Ω范圍內(nèi)X同A盡可能接近。

在矩陣填補(bǔ)中，核范數(shù)（nuclear norm）常用來替代矩陣的秩。對于張量，也有一些核范數(shù)，例如overlapped核范數(shù)[24]和scaled-latent核范數(shù)[25]等，而scaled-latent核范數(shù)在低秩張量填補(bǔ)中優(yōu)于overlapped核范數(shù)[26]。因此本文用scaled-latent核范數(shù)來代替張量的秩。

X的scaled-latent核范數(shù)定義為

式(8)表示將X拆解成D個張量的和（D為X的維度），要找到一種拆解方式使最小，該最小值即為X的scaled-latent核范數(shù)。那么，可以將式(7)替換成

下面采用FW算法求解由式(6)和式(9)構(gòu)成的優(yōu)化問題。根據(jù)式(6)，F(xiàn)W算法中的步驟3)可寫為

雖然式(10)是一個線性優(yōu)化問題，但由于scaled-latent核范數(shù)的定義較為復(fù)雜，因而式(10)中的約束較為復(fù)雜，很難求得式(10)的最優(yōu)解，因此本文采用如下方法求其次優(yōu)解：首先構(gòu)造一批滿足約束條件的可行解，然后從這些可行解中挑選最優(yōu)解。

其中，σk>0為奇異值，uk和vk為對應(yīng)的左右奇異（列）向量。由于左奇異向量之間兩兩正交，右奇異向量之間兩兩正交，則

由于式(10)要求最小值，根據(jù)式(13)可知，S(t+1)為所構(gòu)造的張量Gg,k,l中使最小的那個，其l等于–1，σk為（PΩ(X(t)-A))的最大奇異值，d為使達(dá)到最大的值。σk可以通過冪法快速求得。

另外，根據(jù)上面的求解過程可知，采用FW算法進(jìn)行張量填補(bǔ)的計算開銷較小。

3.3 偏好構(gòu)建

一般的推薦算法都是直接依據(jù)張量（或矩陣）填補(bǔ)后的數(shù)據(jù)進(jìn)行推薦，然而本文認(rèn)為，張量填補(bǔ)雖然能夠填補(bǔ)缺失的數(shù)據(jù)，但并不能就此做出推薦，因為張量填補(bǔ)沒有很好地考慮到用戶的偏好信息。以書籍推薦為例，如果某用戶從未接觸過歷史類型的書籍，但在填補(bǔ)后的張量中，可能由于有一些與他相似的用戶給歷史類型書籍評了高分，導(dǎo)致某些歷史類型的書籍被該用戶評了高分（不是該用戶進(jìn)行的評分，而是被填補(bǔ)的）而被推薦，因此需要考慮用戶的類別偏好。如果某用戶特別偏愛歷史類型的書籍，對歷史類型書籍的評分明顯高于其他用戶，那么有可能因為其他用戶對歷史類型書籍的評分過低，導(dǎo)致歷史類型的書籍被該用戶評分（不是該用戶進(jìn)行的評分，而是被填補(bǔ)的）過低而不被推薦，因此需要考慮用戶的評分偏好。所以，在推薦中加入用戶的類別偏好和評分偏好將有助于提升推薦質(zhì)量。

根據(jù)張量A和B構(gòu)建用戶的類別偏好矩陣P和評分偏好矩陣Q。用戶u對類別c的偏好定義為，用戶u對類別c項目的評分次數(shù)除以用戶u對所有類別項目的總評分次數(shù)，其計算方法為

用戶u對類別c的評分偏好定義為，用戶u對類別c項目的平均評分減去其他用戶對類別c項目的平均評分，其計算方法為

用戶的類別偏好矩陣P和評分偏好矩陣Q分別表示為

3.4 聯(lián)合推薦

假設(shè)張量A填補(bǔ)后的張量為A'。為了進(jìn)行最后的推薦，需要根據(jù)三維張量'A，以及類別偏好矩陣P和評分偏好矩陣Q計算得到U行I列的推薦矩陣O，矩陣O的元素表示各個項目對各個用戶的推薦程度。下面給出矩陣O的計算方法。

在張量A'中，用戶u和項目i對應(yīng)一個類別向量；在矩陣P和Q中，用戶u分別對應(yīng)向量Pu*和Qu*；這3個向量的長度均為C。本文根據(jù)這3個向量來計算Oui的值（注意，如果用戶u已經(jīng)對項目i評過分，則不需要計算Oui的值），計算方法如圖3所示。首先對3個向量進(jìn)行加權(quán)求和得到一個向量，然后取該向量的最大元素作為最終Oui的值。

圖3 推薦程度值的計算

本文采用差分進(jìn)化算法來確定w=(wp,wq)的最優(yōu)值。差分進(jìn)化算法是基于種群的全局優(yōu)化方法，包括變異、交叉和選擇3種基本操作[27]。詳細(xì)步驟如算法2所示，其中w為個體，個體的適應(yīng)度函數(shù)為以該個體為權(quán)重時的推薦精度（精度的定義參見4.2節(jié)）。

算法2求最優(yōu)權(quán)重的差分進(jìn)化算法

1)設(shè)置種群大小NP、最大迭代次數(shù)G、縮放因子F和交叉概率CR。

2)隨機(jī)產(chǎn)生初始種群中的個體wi，i=1,2,…,NP，當(dāng)前代數(shù)g=0。

3)變異。種群內(nèi)個體的差分向量經(jīng)過縮放與種群內(nèi)相異的個體相加產(chǎn)生變異個體vi=wa+F(wbwc)，i≠a≠b≠c。

4)交叉。變異個體和原個體進(jìn)行交叉，產(chǎn)生試驗個體ui：如果rand(0,1)≤CR，那么ui,j=vi,j，否則ui,j=wi,j，j表示個體的分量，且保證ui至少包含變異個體vi的一個分量。

5)選擇。挑選原個體wi和試驗個體ui中適應(yīng)度函數(shù)值大的那個作為新的個體wi進(jìn)入下一代種群，更新當(dāng)前代數(shù)g=g+1。

6)如果g=G，則停止迭代并輸出種群中的最優(yōu)個體；否則重復(fù)步驟3)～步驟5)。

4 實驗結(jié)果及分析

4.1 數(shù)據(jù)集及實驗環(huán)境

實驗所用的數(shù)據(jù)來源于MovieLens[22]上最新的數(shù)據(jù)集，數(shù)據(jù)集中評分的范圍為0.5～5（包含0.5分和5分），且為0.5的倍數(shù)。為了驗證不同數(shù)據(jù)規(guī)模對實驗結(jié)果的影響，本文使用4種不同規(guī)模的數(shù)據(jù)集進(jìn)行測試，各數(shù)據(jù)集的相關(guān)信息如表1所示。

表1 4種不同規(guī)模的數(shù)據(jù)集

每個數(shù)據(jù)集被隨機(jī)分成80%的訓(xùn)練集和20%的測試集。實驗在配置為Intel Core i7 3.40 GHz CPU、24 GB內(nèi)存的Windows 7 PC機(jī)上進(jìn)行，運(yùn)行環(huán)境為Matlab R2014a。

4.2 評價指標(biāo)

從誤差和準(zhǔn)確性兩方面來評測推薦算法的性能。評價誤差的性能指標(biāo)包括平均絕對誤差（MAE，mean absolute error）和均方根誤差（RMSE，root mean square error），用來衡量在測試集中張量填補(bǔ)值與真實值之間的誤差，計算方法如下。

TP：項目推薦給用戶，且事實上用戶也對項目評過分。

TN：項目未推薦給用戶，且事實上用戶未對項目評過分。

FP：項目推薦給用戶，但事實上用戶未對項目評過分。

FN：項目未推薦給用戶，但事實上用戶對項目評過分。

4.3 對比算法及參數(shù)測定

本文將提出的基于張量填補(bǔ)和用戶偏好的聯(lián)合推薦算法TCUP與4種典型的以及2種新近的推薦算法進(jìn)行對比測試，對比算法及其用到的主要相關(guān)參數(shù)如表2所示。

由于LRML算法沒有依據(jù)具體的評分值進(jìn)行推薦，而只是將條目（用戶,項目）標(biāo)記為0或1，分別表示用戶是否對該項目評過分，因此對于該算法本文不進(jìn)行填補(bǔ)誤差的分析，而只進(jìn)行推薦準(zhǔn)確性的分析。結(jié)合文獻(xiàn)[3,6,9-11,17,20]中的參數(shù)設(shè)置，以及文獻(xiàn)[7]中對比測試時的參數(shù)設(shè)置，并通過多次實驗為各算法選擇最優(yōu)參數(shù)，結(jié)果如表3所示。在測試TCUP算法中的最優(yōu)權(quán)重wp和wq時，計算的是top@10下的最優(yōu)權(quán)重，并以此權(quán)重作為其他top@N推薦的權(quán)重。差分進(jìn)化算法的參數(shù)如下：種群大小NP為20，縮放因子F為0.2，交叉概率為CR為0.9，最大進(jìn)化代數(shù)G為20。以下所有測試均是在最優(yōu)參數(shù)下進(jìn)行的。

4.4 張量填補(bǔ)的誤差分析

誤差分析是用來評測各算法填補(bǔ)得到的評分值與測試集中真實值的偏差情況，結(jié)果如表4所示。由表4中的結(jié)果可知，在300u數(shù)據(jù)集下，ALS算法表現(xiàn)最差，SVD++算法表現(xiàn)最好。在其他更大規(guī)模的數(shù)據(jù)集下，HOSVD算法的誤差明顯高于其他算法；SVD++、Precon和TCUP算法表現(xiàn)較好，誤差明顯低于其他3種算法，其中TCUP算法略優(yōu)于SVD++和Precon算法。從總體上來看，TCUP算法的綜合表現(xiàn)最優(yōu)，尤其是當(dāng)應(yīng)用于較大規(guī)模的數(shù)據(jù)集時。

表2 對比算法及相關(guān)參數(shù)

表3 不同算法的參數(shù)設(shè)置

4.5 推薦算法的準(zhǔn)確性分析

圖4和圖5分別展示了不同數(shù)據(jù)集下各算法的精度和召回率的對比，其中top@N表示向每個用戶推薦項目的數(shù)量。圖4的結(jié)果表明，TCUP算法表現(xiàn)最佳，其推薦精度在不同數(shù)據(jù)集下均明顯高于其他算法；LRML算法的性能次之，精度可以保持一個較好的水平；UserCF、ALS、SVD++和Precon算法的精度則基本一直處于較低水平。相對于LRML算法，在300u數(shù)據(jù)集下推薦時，TCUP算法的精度平均提升幅度最小，為1.96%；在4000u數(shù)據(jù)集下進(jìn)行推薦時，TCUP算法的精度平均提升幅度最大，為3.44%。

表4 誤差分析比較

圖4 不同數(shù)據(jù)集下各算法的精度對比

圖5 不同數(shù)據(jù)集下各算法的召回率對比

從圖5可以看出，所有算法的召回率均隨著top@N的增大而增大，這是因為隨著推薦數(shù)量的增加，推薦給用戶且用戶評過分（即看過）的電影數(shù)量也在增加，而用戶評過分（即看過）的電影數(shù)量保持不變。TCUP算法表現(xiàn)最好，LRML算法的性能略低于TCUP；UserCF、ALS、SVD++和Precon算法的召回率則一直處于較低水平，性能較差。相對于LRML算法，在1200u數(shù)據(jù)集下進(jìn)行推薦時，TCUP算法的召回率平均提升幅度最小，為1.35%；在300u數(shù)據(jù)集下進(jìn)行推薦時，TCUP算法的召回率平均提升幅度最大，為2.40%。

表5～表8分別給出了不同數(shù)據(jù)集下各算法的負(fù)正率、F1分?jǐn)?shù)和準(zhǔn)確率。結(jié)果表明，所有算法的負(fù)正率都較低，這是因為評分非常稀疏，而且top@N也較小，所以大量的元素都屬于“項目未推薦給用戶，且事實上用戶也未對項目評過分”，即TN非常大，由式(23)可知負(fù)正率會非常小。在部分測試中由于保留小數(shù)位數(shù)的原因，有些算法的負(fù)正率會相同。但總體上TCUP算法的負(fù)正率相比于其他算法較低，性能最優(yōu)。在F1分?jǐn)?shù)的測試中，TCUP算法表現(xiàn)一直最優(yōu)，這是因為它的精度和召回率相比其他算法都有優(yōu)勢。另外，所有算法的準(zhǔn)確率都在97%以上，這是因為TN非常大，由式(23)可知準(zhǔn)確率會比較接近1。但相對而言，TCUP算法的準(zhǔn)確率一直都是最高的。

表5 300u下不同算法的性能對比

表6 1200u下不同算法的性能對比

表7 2400u下不同算法的性能對比

表8 4000u下不同算法的性能對比

整個實驗結(jié)果表明，相對于其他6種算法，TCUP算法呈現(xiàn)較低的誤差，在精度、召回率、負(fù)正率、F1分?jǐn)?shù)，以及準(zhǔn)確率上都有較明顯的優(yōu)勢，因此，本文提出的TCUP算法能取得更好的推薦效果。

5 結(jié)束語

本文提出了一種聯(lián)合張量填補(bǔ)和用戶偏好的推薦算法TCUP。該算法首先基于評分矩陣和項目所屬類別矩陣構(gòu)建用戶–項目–類別的三維張量。然后，將三維張量的填補(bǔ)描述成帶約束的非線性優(yōu)化問題，并借助scaled-latent核范數(shù)來代替對張量秩的約束，接著利用Frank-Wolfe算法將非線性優(yōu)化問題轉(zhuǎn)換成一系列線性優(yōu)化問題進(jìn)行求解，并為scaled-latent核范數(shù)約束下的線性優(yōu)化問題給出了一種計算量較小的求解方案。最后，基于張量數(shù)據(jù)構(gòu)建用戶類別偏好矩陣和評分偏好矩陣，聯(lián)合填補(bǔ)后的張量和2個偏好矩陣設(shè)計了推薦算法，并采用差分進(jìn)化算法進(jìn)行參數(shù)調(diào)優(yōu)。實驗結(jié)果表明，相對于其他6種推薦算法，TCUP算法在誤差分析上呈現(xiàn)一個較低的誤差；在準(zhǔn)確性分析上其精度和召回率等指標(biāo)均有明顯優(yōu)勢，其中，精度的平均提升幅度為1.96%～3.44%，召回率的平均提升幅度為1.35%～2.40%。由于高維張量各維度的重要程度不同，如何更好地考慮各維度的差別是接下來的研究方向。