基于改進余弦相似度的協(xié)同過濾推薦算法

李一野，鄧浩江

(1.中國科學(xué)院聲學(xué)研究所國家網(wǎng)絡(luò)新媒體工程技術(shù)研究中心，北京 100190； 2.中國科學(xué)院大學(xué)，北京 100049)

1 概 述

隨著互聯(lián)網(wǎng)的發(fā)展，電子商務(wù)、社交媒體網(wǎng)站等信息平臺上都出現(xiàn)了信息過載的問題，推薦系統(tǒng)在各種平臺上被廣泛使用，有效地緩解了信息過載的現(xiàn)象。在推薦系統(tǒng)中所使用到的推薦算法，主要分為基于內(nèi)容(content-based)的推薦算法[1]、協(xié)同過濾(collaborative filtering)算法[2]以及混合推薦算法[3]。其中，基于內(nèi)容的推薦算法是根據(jù)用戶的歷史評分行為數(shù)據(jù)做推薦[4]，在數(shù)據(jù)稀疏的情況下，算法需要根據(jù)少量的用戶歷史評分行為做推薦，但用戶行為數(shù)據(jù)的稀疏性使算法難以學(xué)習(xí)到用戶潛在的偏好，從而不能夠完整地獲取用戶的偏好，使得推薦的結(jié)果偏差過大。協(xié)同過濾推薦算法包含基于近鄰(nearest-neighbor)[5]的協(xié)同過濾推薦算法[6]、基于模型(model-based)的協(xié)同過濾推薦算法[7]。

基于近鄰的協(xié)同過濾推薦算法利用評分的相關(guān)性作為依據(jù)，若2個用戶對同一個物品評分，則將它們視作近鄰用戶，并推薦被該近鄰用戶所評價過的物品。這使得基于近鄰的協(xié)同過濾推薦算法在稀疏的數(shù)據(jù)中往往存在問題[8]，其中數(shù)據(jù)的稀疏性，一方面體現(xiàn)在用戶評價過的物品數(shù)量大多數(shù)是有限的，只占物品數(shù)量中的較小部分；另一方面體現(xiàn)在，只有少量的物品被大多數(shù)用戶評價過[9]。這就會造成正樣本(positive sample)的數(shù)量很少，而負樣本(negative sample)則占了大多數(shù)的情況，對推薦系統(tǒng)造成不好的影響。

而基于模型的協(xié)同過濾推薦算法，是通過對已有的數(shù)據(jù)進行學(xué)習(xí)，繼而得到用戶和物品的潛在特征，然后通過潛在特征構(gòu)建模型，利用模型來進行推薦。在對潛在特征的學(xué)習(xí)過程中，由于訓(xùn)練過程中所采用的訓(xùn)練樣本會對算法的結(jié)果產(chǎn)生影響，可能會造成過擬合。為了避免出現(xiàn)過擬合的現(xiàn)象，算法在訓(xùn)練過程中同時采用正樣本和負樣本進行訓(xùn)練。這就會導(dǎo)致一種情況的出現(xiàn)：每個用戶都具有較多的未知樣本和負樣本，當(dāng)2個基于正樣本原本不相似不互為近鄰的用戶[10]，在采用負樣本訓(xùn)練時有一定的概率出現(xiàn)因為負樣本產(chǎn)生了相似度的情況。在數(shù)據(jù)稀疏的情況下，大多數(shù)用戶的負樣本相互之間都有交集。這種情況下所產(chǎn)生的近鄰會導(dǎo)致在多次迭代后學(xué)習(xí)到的用戶的潛在特征越來越相似，從而導(dǎo)致難以區(qū)分出與用戶喜好真正相似的用戶。

在數(shù)據(jù)稀疏的情況下，基于模型的協(xié)同過濾推薦算法存在分類準(zhǔn)確性低的問題[11]，為了解決這一問題，本文提出一種基于改進余弦相似度[12]的協(xié)同過濾推薦算法，將數(shù)據(jù)經(jīng)嵌入層(embedding layer)轉(zhuǎn)換為特征矩陣[13]，對其計算后得到改進余弦相似度矩陣，將其和單位矩陣之間的均方誤差作為損失函數(shù)。這種方法可以有效地增加正樣本在訓(xùn)練過程中的影響，減小負樣本在訓(xùn)練過程中的影響，提高數(shù)據(jù)稀疏情況下分類的準(zhǔn)確性。

2 相關(guān)工作

基于模型的協(xié)同過濾推薦算法，主要是通過機器學(xué)習(xí)方法或概率統(tǒng)計模型來建立模型(例如貝葉斯模型、圖模型、潛在語義模型、決策樹模型等模型)[14]，然后通過模型預(yù)測目標(biāo)用戶的偏好。近年來，因子分解機(Factorization Machine， FM)模型和在其基礎(chǔ)上衍生的場感知因子分解機(Field-aware Factorization Machine， FFM)模型在實際場景中得到廣泛的應(yīng)用。FM模型可以在數(shù)據(jù)稀疏的情況下組合特征。常見的多項式模型如式(1)所示：

(1)

由二次多項式模型可知，組合特征相關(guān)參數(shù)共有n(n-1)/2個。在數(shù)據(jù)集較為稀疏的情況下，xi或xj為0的情況非常多，ωij很難經(jīng)過訓(xùn)練得出。

(2)

由ωij構(gòu)成的矩陣如下：

(3)

對于交叉項利用下式進行化簡，然后利用隨機梯度下降SGD求解：

(4)

FFM模型在FM模型的基礎(chǔ)上進行了優(yōu)化，引入了類別(field)的概念，假設(shè)樣本的f個類別共計存在n個特征，則對于FFM模型的二次項而言就有n×f個隱向量。當(dāng)FMM模型的所有特征都屬于一個類別時，F(xiàn)FM可以視作FM模型。FFM模型方程如下：

(5)

FFM的二次參數(shù)為n×f×k個，其中，n為特征數(shù)量，f為類別數(shù)量，k為隱向量維數(shù)。與FM模型相比，F(xiàn)FM模型中的特征都有幾個不同的隱向量，其在稀疏度較大的輸出處理上效果更好。而且FFM模型支持并行化處理，其運行時間較短。但這2種模型在處理高階特征和低階特征的交互信息方面存在不足。

目前，深度因子分解機(Deep Factorization Machine， DeepFM)模型在探索數(shù)據(jù)潛在特征[15]，同時學(xué)習(xí)高階特征和低階特征的交互信息方面有良好的效果。DeepFM模型通過融合因子分解機和深度神經(jīng)網(wǎng)絡(luò)，同時學(xué)習(xí)低階特征和高階特征之間的交互信息。DeepFM模型由深度神經(jīng)網(wǎng)絡(luò)部分(Deep component)和因子分解機部分(FM component)這2個部分組成。深度神經(jīng)網(wǎng)絡(luò)部分負責(zé)提取低階特征，因子分解機負責(zé)提取高階特征。這2個部分共享相同的輸入。DeepFM模型最終預(yù)測結(jié)果時將深度神經(jīng)網(wǎng)絡(luò)部分和因子分解機部分這2個部分的預(yù)測結(jié)果輸入激活函數(shù)：

(6)

圖1 因子分解機部分

圖1所示是因子分解機部分的結(jié)構(gòu)。因子分解機部分在學(xué)習(xí)特征的線性交互的同時也利用隱向量的內(nèi)積學(xué)習(xí)二階交互特征。該部分輸出如下：

(7)

深度神經(jīng)網(wǎng)絡(luò)部分的結(jié)構(gòu)如圖2所示，它是一種前饋神經(jīng)網(wǎng)絡(luò)，主要作用是學(xué)習(xí)高階特征的交互。首先引入一個嵌入層來將非常稀疏的輸入向量壓縮為較為稠密的低維向量。在嵌入層，每個特征都會被映射為低維向量，這些向量的長度相等，既可以作為隱向量在因子分解機部分中使用，也可以作為輸入在深度神經(jīng)網(wǎng)絡(luò)中使用。

圖2 深度神經(jīng)網(wǎng)絡(luò)部分

嵌入層[16]輸出公式如下：

a(0)=[e1,e2,…,em]

(8)

其中，輸入特征的個數(shù)為m，ei為輸出特征中第i個特征的嵌入值，該部分網(wǎng)絡(luò)前饋的過程可以表示如下：

a(l+1)=σ(W(l)·a(l)+b(l))

(9)

其中，l為神經(jīng)網(wǎng)絡(luò)層的深度，σ為激活函數(shù)，W(l)、a(l)、b(l)分別為權(quán)重、隱層輸出和第l層的偏置。深度神經(jīng)網(wǎng)絡(luò)隨后生成低維度的特征向量輸入激活函數(shù)，最終的輸出如下：

yDNN=σ(W|H|+1·a|H|+b|H|+1)

(10)

其中，|H|為隱藏層的數(shù)量。

嵌入層結(jié)構(gòu)如圖3所示，嵌入層產(chǎn)生的向量長度相同，從因子分解機得到的隱向量Rik是嵌入層網(wǎng)絡(luò)的權(quán)重。

圖3 嵌入層結(jié)構(gòu)

3 基于改進余弦相似度的協(xié)同過濾推薦算法

基于改進余弦相似度的協(xié)同過濾推薦算法，是將數(shù)據(jù)利用嵌入層進行映射從而轉(zhuǎn)換為特征矩陣，將對其計算后得到的改進余弦相似度矩陣和單位矩陣之間的均方誤差作為損失函數(shù)，以此來減小負樣本在訓(xùn)練過程中對學(xué)習(xí)潛在特征造成的不利影響，提高數(shù)據(jù)稀疏情況下分類的準(zhǔn)確性。

在實際的應(yīng)用場景中，數(shù)據(jù)的稀疏性是指由于數(shù)據(jù)規(guī)模非常大，使得用戶對物品的選擇之間存在的重疊非常少。大部分評分?jǐn)?shù)據(jù)都是未知的，以Movielens-10M數(shù)據(jù)集為例，評分?jǐn)?shù)據(jù)以0.5分為間隔在0.5～5分之間分布。

在實際場景中，不同的用戶在評分標(biāo)準(zhǔn)上存在一定程度的不同[17]，有的用戶評分標(biāo)準(zhǔn)比較嚴(yán)格，即使對偏好的物品也會給出偏低的評分，而有的用戶標(biāo)準(zhǔn)相對較低，對于偏好程度較低的物品給出的評分依然會很高，這種情況會影響到計算相似性。因此要對數(shù)據(jù)做歸一化處理。常用的歸一化方法有最小最大歸一化(Min-Max Normalization)[18]和1標(biāo)準(zhǔn)差歸一化(z-score Normalization)[19]。

最小最大歸一化是將數(shù)值線性變換到[0,1]之中。變換公式如下：

(11)

其中，max和min分別為數(shù)據(jù)樣本的最大值和最小值，在數(shù)據(jù)集引入新的數(shù)據(jù)時，會引起最大值和最小值產(chǎn)生變化，從而需要重新定義。

而1標(biāo)準(zhǔn)差歸一化是使數(shù)據(jù)變?yōu)?均值、1標(biāo)準(zhǔn)差，其公式如下：

(12)

其中，x是原始數(shù)據(jù)，z為歸一化后的數(shù)據(jù)，對于M×N的矩陣，M為樣本數(shù)，N為特征的個數(shù)，需要變換的均值和方差是矩陣的均值和方差。

在數(shù)據(jù)的處理過程中，對數(shù)據(jù)采用1標(biāo)準(zhǔn)差歸一化處理。

余弦相似度[18]的計算公式如下：

(13)

其中，x1k、x2k分別是2個向量在第k個維度上的值。當(dāng)2個向量越相似時，兩者之間的夾角越小，其相似度越大。當(dāng)相似度為負數(shù)時2個向量為負相關(guān)。

余弦相似度存在的問題是對數(shù)值不夠敏感，因其主要是區(qū)分向量間的方向差異，難以衡量向量不同維度在數(shù)值上的差異，這使得評價用戶相似度時出現(xiàn)偏差。以MovieLens數(shù)據(jù)集中用戶對電影的評分為例[20]，A和B這2個用戶對X和Y這2部電影的評分分別為(2，1)和(5，4)，二者的余弦相似度為0.98，從結(jié)果上看用戶A和B的偏好非常相似，但是從評分上看用戶A對X和Y這2部電影評價并不算高，而用戶B則十分偏好這2部電影，由于余弦相似度對數(shù)值不夠敏感，因此使用其作為計算用戶偏好相似度的依據(jù)時會出現(xiàn)一定的偏差。

為了修正這種偏差，本文采用改進余弦相似度來衡量[21]，即在向量的每個維度上都減去用戶對電影的評分均值，例如用戶A和用戶B對電影的評分均值為3，修正后為(-1，-2)和(2，1)，二者的改進余弦相似度為-0.8，這反映用戶A和用戶B的偏好存在差異，這個結(jié)果更符合實際情況。在實驗中對數(shù)據(jù)都是作歸一化處理。

(14)

將數(shù)據(jù)經(jīng)嵌入層轉(zhuǎn)換為特征矩陣，對其計算后得到改進余弦相似度矩陣，位于矩陣第i行j列的元素，代表的是第i個用戶與第j個用戶之間的改進余弦相似度。

在數(shù)據(jù)稀疏的場景下，推薦系統(tǒng)面臨的是復(fù)雜的非線性映射問題，所以本文使用的損失函數(shù)主要用于解決非線性問題。

使用均方誤差(Mean Square Error)作為損失函數(shù)，其公式如下：

(15)

在得到改進余弦相似度矩陣之后，進而計算它和單位矩陣之間的均方誤差，將其作為損失函數(shù)，并用該部分的損失函數(shù)結(jié)合基線模型的損失函數(shù)，而該部分的損失函數(shù)，在兩者中所占的權(quán)重較小。

這種基于改進余弦相似度的協(xié)同過濾推薦算法，通過加入改進余弦相似度進行約束的優(yōu)化問題的構(gòu)造，能夠令與目標(biāo)用戶偏好真正相似的用戶在對樣本進行訓(xùn)練的過程中，利用正樣本產(chǎn)生更大的相似度，使其從學(xué)習(xí)到的相似潛在特征中區(qū)分出來，提高數(shù)據(jù)稀疏情況下分類的準(zhǔn)確性。

4 實驗結(jié)果分析

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

本文的實驗數(shù)據(jù)采用MovieLens-10M數(shù)據(jù)集，在實驗中，該數(shù)據(jù)集被用于評價基于模型的協(xié)同過濾算法推薦效果，數(shù)據(jù)集中包含了10681部電影的信息、71567個用戶的信息和10×106條評分?jǐn)?shù)據(jù)。每條評分記錄有用戶ID、電影ID、評分、時間戳4個屬性。電影評分為0.5～5，以0.5為間隔，評分越低時，用戶對該電影的偏好度越低[22]。

在選取實驗數(shù)據(jù)時，選擇每個用戶的70%評分信息作為訓(xùn)練數(shù)據(jù)，選擇其余的30%作為測試數(shù)據(jù)。數(shù)據(jù)集評分密度為1.3%，評分密度是指平均每個用戶評價多少個項目，可見Movielens-10M數(shù)據(jù)集具有顯著的稀疏性。在實驗中對MovieLens-10M數(shù)據(jù)集采用五折交叉驗證(5-Fold Cross Validation)，共進行5次劃分，在每一折實驗中，基于訓(xùn)練集數(shù)據(jù)預(yù)測測試集數(shù)據(jù)，并通過比較預(yù)測評分與真實評分得出每一折的MSE值，最后取結(jié)果的平均值。

4.2 實驗環(huán)境和評價指標(biāo)

本文實驗所采用的環(huán)境為Linux版本Ubuntu 16.04，采用GPU進行訓(xùn)練，顯卡為Tesla K40。參數(shù)設(shè)置上DeepFM模型和在DeepFM模型基礎(chǔ)上改進的基于改進余弦相似度的協(xié)同過濾推薦算法均使用TensorFlow實現(xiàn)。對于基線算法和本文提出的優(yōu)化方法，F(xiàn)M隱向量的維數(shù)均為8，在深度神經(jīng)網(wǎng)絡(luò)部分的網(wǎng)絡(luò)層數(shù)分別為10和5，學(xué)習(xí)速率設(shè)置為0.01，批處理大小為100，基于改進余弦相似度的協(xié)同過濾推薦算法的損失函數(shù)與DeepFM模型的損失函數(shù)相比所占權(quán)重較小，實驗中設(shè)為0.0001。

本文采用AUC(Area Under the ROC Curve， ROC曲線下面積)和對數(shù)損失函數(shù)(Logloss)作為評價指標(biāo)來描述推薦效果。

受試者工作特性曲線 (Receiver Operator Characteristic Curve， ROC曲線)是反映二分類器的分類性能的指標(biāo)[23]。在常見的二分類預(yù)測問題中，當(dāng)分類預(yù)測的結(jié)果和實際結(jié)果同時為正類時，被稱作真陽性；當(dāng)分類預(yù)測的結(jié)果和實際結(jié)果同時為負類時，則稱作真陰性。在預(yù)測結(jié)果為負類，實際結(jié)果為正類時稱為假陰性。當(dāng)預(yù)測結(jié)果為正類，而實際結(jié)果則為負類時，稱為假陽性，這種情況下的樣例，其在實際結(jié)果為負類的全部樣例中的比率被稱作假陽率，而正確預(yù)測為正類的實例在所有實際結(jié)果為正例的實例中的比例被稱作真陽率。

假陽率和真陽率分別對應(yīng)著在ROC空間中的橫軸坐標(biāo)和縱軸坐標(biāo)。同樣一個二分類器，隨著閾值t的不斷改變，其對應(yīng)的坐標(biāo)點的連線即為該分類器的ROC曲線。在ROC空間中，曲線在左上方，其分類器性能較好，曲線在右下方，其分類器性能較差[24]，點(0，1)代表的分類器，是最完美的，點(1，0)代表的分類器是一個最糟糕的分類器。

ROC曲線下面積AUC是衡量分類器分類精度的重要評價指標(biāo)[25]，ROC曲線下的區(qū)域面積，被定義為AUC，其越大代表分類器分類能力越強。分類器在AUC=1時最完美，在AUC=0.5時，分類器沒有價值，因為其結(jié)果是隨機的。

當(dāng)分類器的輸出結(jié)果為樣本屬于正類的置信度時，AUC為隨機抽取一對樣本其中正樣本的置信度大于負樣本置信度的概率。AUC可以通過直接計算ROC曲線下的面積得到，也可以通過計算正樣本置信度大于負樣本置信度的概率得到，按照置信度從大到小排序，正樣本的置信度大于負樣本置信度的概率根據(jù)式(16)計算：

(16)

其中，M為正樣本數(shù)，N為負樣本數(shù)，置信度最大的樣本rank為n，次大的樣本rank為n-1，按照這個規(guī)律類推。實驗中，將正樣本定義為評分大于2.5的樣本，其他的樣本定義為負樣本。

AUC在評價分類器精度時被普遍地使用，AUC在類不平衡的情況下十分穩(wěn)定，能夠比較準(zhǔn)確地體現(xiàn)特征對于實例分布的區(qū)分程度。

對數(shù)損失函數(shù)Logloss，也被稱為交叉熵損失函數(shù)或者邏輯回歸損失函數(shù)，主要被當(dāng)作是評價二分類問題模型的準(zhǔn)確度的評價指標(biāo)，其定義如式(17)所示：

(17)

其中，N為樣本總數(shù)，yi為第i個樣本的標(biāo)簽，hi為模型預(yù)測點擊的概率。

AUC和對數(shù)損失函數(shù)Logloss是在評價基于模型的協(xié)同過濾推薦算法中常被用到的評價指標(biāo)。

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

本文對實驗結(jié)果從有效性和性能這2個方面對模型進行分析和對照。

為了容易在圖形上進行直觀展示，對于在FM模型、FFM模型和DeepFM模型方案上分別實現(xiàn)的基于改進余弦相似度的協(xié)同過濾推薦算法，記為“FM+”、“FFM+”和“DeepFM+”。模型的有效性對比如圖4～圖6所示。

圖4 各模型Logloss結(jié)果對比

圖5 各模型AUC結(jié)果對比

圖6 各模型與FM模型的訓(xùn)練時間比值

根據(jù)實驗結(jié)果，在Logloss和AUC指標(biāo)的表現(xiàn)上基于改進余弦相似度的協(xié)同過濾推薦算法均要好于基線算法，其中“FM+”模型比FM模型在AUC上提升8.32%，在Logloss上降低6.56%。“FFM+”模型比FFM模型在AUC上提升5.68%，在Logloss上降低7.2%?！癉eepFM+”模型比DeepFM模型在AUC上提升10.04%，在Logloss上降低8.1%。表明本文提出的算法有效地提高了分類的準(zhǔn)確性。

算法的運行效率在實際場景中也十分重要。本文以FM模型為基準(zhǔn)來衡量每個模型的訓(xùn)練時間。訓(xùn)練時間評價指標(biāo)如公式(18)所示：

(18)

在訓(xùn)練時間上，“FM+”模型比FM模型多5.2%，“FFM+”模型比FFM模型多6%，“DeepFM+”模型較DeepFM模型多3%。這組對照實驗表明，在可以明顯提高推薦效果的情況下，本文提出的基于改進余弦相似度的協(xié)同過濾推薦算法所增加的訓(xùn)練時間并不多。

5 結(jié)束語

在數(shù)據(jù)稀疏的情況下，2個基于正樣本原本不相似的用戶在傳統(tǒng)的協(xié)同過濾推薦算法中采用負樣本訓(xùn)練時，會有一定概率出現(xiàn)因為負樣本產(chǎn)生了相似度的情況，從而使算法在多次迭代后學(xué)習(xí)到的用戶的潛在特征越來越相似，導(dǎo)致難以區(qū)分出與用戶喜好真正相似的用戶、分類準(zhǔn)確性低的問題。

為了解決在數(shù)據(jù)稀疏的條件下，基于模型的協(xié)同過濾推薦算法存在的分類準(zhǔn)確性低的問題，本文提出了一種基于改進余弦相似度的協(xié)同過濾推薦算法，將數(shù)據(jù)經(jīng)嵌入層轉(zhuǎn)換為特征矩陣，將對其計算后得到的改進余弦相似度矩陣和單位矩陣之間的均方誤差作為損失函數(shù)。

實驗結(jié)果表明，在AUC和Logloss指標(biāo)的表現(xiàn)上，本文提出的基于改進余弦相似度的協(xié)同過濾推薦算法均優(yōu)于基線算法。而與此同時，基于改進余弦相似度的協(xié)同過濾推薦算法所產(chǎn)生的訓(xùn)練時間開銷也都是可以接受的。通過這種方法，可以有效地提高正樣本在訓(xùn)練過程中的影響，減小負樣本在訓(xùn)練過程中的影響，提高數(shù)據(jù)稀疏情況下分類的準(zhǔn)確性。在未來的工作中，將研究如何將更多的樣本信息也融入改進算法之中，以此來進一步地提高算法的推薦性能。