武 美，丁怡彤，趙建立+

1.山東科技大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，山東 青島 266590

2.東北林業(yè)大學(xué) 信息與計(jì)算機(jī)工程學(xué)院，哈爾濱 150040

隨著科技的發(fā)展以及互聯(lián)網(wǎng)的普及，用戶可以在短時(shí)間內(nèi)獲得大量信息，但在這其中也包含了一大部分用戶可能不感興趣的信息，因此如何從海量的信息中快速對(duì)用戶建模并為其推薦感興趣的內(nèi)容是本文要解決的主要問(wèn)題。個(gè)性化推薦技術(shù)定位于目標(biāo)用戶的興趣，從用戶的歷史瀏覽路徑或操作信息中挖掘并識(shí)別出用戶的興趣所在，并主動(dòng)向用戶進(jìn)行資源與信息的推薦。推薦技術(shù)的出現(xiàn)可以給用戶節(jié)省出大量的時(shí)間與精力，而協(xié)同過(guò)濾是推薦系統(tǒng)所采用的最為重要的技術(shù)之一。其原理是根據(jù)相似用戶的興趣來(lái)推薦當(dāng)前用戶沒(méi)有看過(guò)但是可能會(huì)感興趣的信息，所基于的假設(shè)是：如果兩個(gè)用戶興趣類似，那么很有可能當(dāng)前用戶會(huì)喜歡另一個(gè)用戶所喜歡的內(nèi)容。其中矩陣分解是處理協(xié)同過(guò)濾中較常用的方法，矩陣分解具有較高的準(zhǔn)確性和擴(kuò)展性，本文也采用矩陣分解的方法來(lái)進(jìn)行評(píng)分的預(yù)測(cè)工作。在現(xiàn)實(shí)世界中，用戶的行為累計(jì)往往在短時(shí)間內(nèi)快速增長(zhǎng)，推薦系統(tǒng)應(yīng)能夠適應(yīng)這種變化，并在短時(shí)間內(nèi)根據(jù)用戶的實(shí)時(shí)數(shù)據(jù)更新推薦。因此，增量式設(shè)計(jì)在推薦系統(tǒng)中顯得尤為重要。一旦推薦系統(tǒng)能夠?qū)@種數(shù)據(jù)爆炸做出快速的響應(yīng)，相應(yīng)的用戶興趣模型的構(gòu)建就會(huì)更加靈活和具體，用戶的忠誠(chéng)度和滿意度也會(huì)得到進(jìn)一步的提高。本文的主要工作是在基于矩陣分解的基礎(chǔ)上通過(guò)添加過(guò)濾機(jī)制對(duì)預(yù)測(cè)過(guò)程進(jìn)行優(yōu)化，以達(dá)到減小計(jì)算量、節(jié)省運(yùn)算時(shí)間的目的，同時(shí)采取一種增量式靜態(tài)的方法確保在減小時(shí)間消耗的同時(shí)保證一定的精度。

本文的主要貢獻(xiàn)如下：

（1）將預(yù)測(cè)部分劃分為增量部分和靜態(tài)部分，保證精度的同時(shí)提高預(yù)測(cè)的效率。

（2）將訓(xùn)練數(shù)據(jù)按照一定標(biāo)準(zhǔn)劃分為不同的區(qū)域，對(duì)不同區(qū)域采取不同的計(jì)算方法，有效提高計(jì)算效率。

（3）對(duì)數(shù)據(jù)的訓(xùn)練過(guò)程采取過(guò)濾機(jī)制，有效提高計(jì)算效率。

1 相關(guān)工作

在增量計(jì)算的之前相關(guān)研究中，Luo 等人提出了一種I-KNN（incremental K nearest neighborhood）模型，在Miranda 等人提出的RS-KNN（random subspace K nearest neighborhood）模型的基礎(chǔ)上減少了存儲(chǔ)復(fù)雜性，同時(shí)采用廣義骰子系數(shù)保持了預(yù)測(cè)精度，但相應(yīng)的計(jì)算復(fù)雜度增加。

Wang 等人提出了將聚類技術(shù)和非負(fù)矩陣分解結(jié)合的方法來(lái)進(jìn)行評(píng)分的預(yù)測(cè)工作，通過(guò)一種快速聚類方法將聚類的個(gè)數(shù)作為矩陣的維度可以實(shí)時(shí)更新，避免設(shè)置的固定維度造成在數(shù)據(jù)量較小時(shí)造成的計(jì)算浪費(fèi)，但是將聚類的簇?cái)?shù)作為維度的定義缺乏可靠性，且跟隨數(shù)據(jù)集的不同在計(jì)算效率方面差別較大。

Vinagre 等人提出了一種基于正反饋的快速增量矩陣分解方法，通過(guò)隨機(jī)梯度下降的方法來(lái)訓(xùn)練模型，并在增量過(guò)程中通過(guò)直接用增量數(shù)據(jù)逐條訓(xùn)練模型來(lái)提高效率，但是隨著增量數(shù)據(jù)的累積，這種方法后期精度缺失較大。

Luo 等人提出了IR（incremental and static combined RMF-based recommender）算法。此算法可以適應(yīng)大量的新數(shù)據(jù)并且能做出較準(zhǔn)確的預(yù)測(cè)，但是在新數(shù)據(jù)進(jìn)入后的預(yù)測(cè)過(guò)程中，抽取數(shù)據(jù)花費(fèi)的時(shí)長(zhǎng)較長(zhǎng)，在時(shí)間方面有待于進(jìn)一步提高效率。

Sun 等人采用正則化矩陣分解IncRMF（incremental recommendation algorithm based on regularized matrix）的方法，此算法雖將運(yùn)算時(shí)間控制在較短范圍內(nèi)，但是在精度方面損失較大。

2 算法介紹

2.1 基礎(chǔ)矩陣分解算法介紹

傳統(tǒng)的矩陣分解算法是利用降維技術(shù)將用戶-物品評(píng)分矩陣分解為兩個(gè)低階的矩陣，通過(guò)對(duì)這兩個(gè)低階矩陣的連續(xù)優(yōu)化來(lái)減小預(yù)測(cè)值和真實(shí)值之間的誤差，無(wú)限逼近原始評(píng)分?jǐn)?shù)據(jù)，來(lái)達(dá)到預(yù)測(cè)用戶-物品評(píng)分矩陣中未知評(píng)分的目的。定義用戶-物品評(píng)分矩陣為∈R，特征維度為，用戶特征矩陣為∈R，物品特征矩陣為∈R，矩陣的分解公式如下：

式中，e定義為真實(shí)值與預(yù)測(cè)值之間的誤差，誤差函數(shù)的公式如下：

其中，||·||定義為標(biāo)準(zhǔn)歐幾里德范數(shù)，代表正則化項(xiàng)，加入正則化項(xiàng)的目的是為了防止過(guò)度擬合所帶來(lái)的誤差。其中各參數(shù)的訓(xùn)練公式如下（p、q采用以下公式來(lái)進(jìn)行更新）：

其中，代表學(xué)習(xí)的步長(zhǎng)，其控制改變的速率，表示學(xué)習(xí)率。

2.2 增量式靜態(tài)協(xié)同過(guò)濾推薦算法（Inc++算法）

本節(jié)基于IncRMF 算法提出了一種改進(jìn)的增量式動(dòng)靜結(jié)合的協(xié)同過(guò)濾算法（improved incremental static combined collaborative filtering method，Inc++），該算法的目標(biāo)是保證適應(yīng)增量更新的效率要求且可以提供高度可靠的預(yù)測(cè)。下面將分四個(gè)小節(jié)介紹本文的算法。

在真實(shí)世界中，用戶對(duì)物品的評(píng)分觀念會(huì)受到周圍環(huán)境或者自身性格改變的影響，不同性格的人群對(duì)相同的物品打分的標(biāo)準(zhǔn)也會(huì)有不同。例如：性格較樂(lè)觀的用戶通常對(duì)物品有較高的評(píng)分，性格較消極的用戶通常對(duì)物品的打分較低。同時(shí)，物品本身也可能會(huì)受到廣告效應(yīng)等外界的影響從而導(dǎo)致評(píng)分發(fā)生改變。因此，考慮到外界因素的影響，在模型訓(xùn)練過(guò)程中融入了物品的偏置、用戶的偏置以及全局偏置，分別定義為b、b、。其中，b為用戶的偏執(zhí)，是獨(dú)立于物品的因素，表示的是某一特定用戶的打分習(xí)慣，b為物品的偏執(zhí)，是獨(dú)立于用戶興趣的因素，表示某一特定物品得到的打分情況，為所有評(píng)分記錄中的全局平均值，表示訓(xùn)練數(shù)據(jù)的總體情況。至此，模型中評(píng)分的預(yù)測(cè)公式為：

相應(yīng)的用戶偏執(zhí)及物品偏執(zhí)更新公式為：

在數(shù)據(jù)更新過(guò)程中，隨著每次增量數(shù)據(jù)的增加，用戶和物品會(huì)在兩個(gè)維度上增加，并在每次增量過(guò)程中，增量的用戶數(shù)目和物品數(shù)目也會(huì)有所不同，為了可以在較短的時(shí)間內(nèi)達(dá)到更新模型的目的，本文提出了分區(qū)域更新策略以更快計(jì)算用戶特征和物品特征。如圖1 所示，將新評(píng)分?jǐn)?shù)據(jù)分為四個(gè)類別：A類評(píng)分，屬于新用戶、老物品的初始評(píng)分；B 類評(píng)分，屬于老用戶、新物品的初始評(píng)分；C 類評(píng)分，屬于新用戶、新物品的新評(píng)分；D 類評(píng)分，屬于老用戶、老物品的新評(píng)分。在初始訓(xùn)練階段首先利用初始數(shù)據(jù)集進(jìn)行訓(xùn)練，隨著增量數(shù)據(jù)的不斷加入，對(duì)增量數(shù)據(jù)進(jìn)行單獨(dú)訓(xùn)練，并非將所有的數(shù)據(jù)全部重新訓(xùn)練，相較于全部訓(xùn)練所有數(shù)據(jù)，此方法可以有效提高效率，節(jié)省時(shí)間。這里本文的增量策略將數(shù)據(jù)集中的用戶集合劃分為初始用戶集合U和增量用戶集合U，同樣也將物品集合劃分為初始物品集合I和增量物品集合I。其中：

圖1 分區(qū)域更新策略Fig.1 Regional update strategy

針對(duì)不同區(qū)域的新數(shù)據(jù)，在數(shù)據(jù)更新方面本文采用的更新策略也有所不同：

（1）當(dāng)一個(gè)新評(píng)分屬于A 類，即用戶是新用戶，在用戶特征矩陣中添加新的特征向量p，并且利用前面的式（5）進(jìn)行相應(yīng)的訓(xùn)練。

（2）當(dāng)一個(gè)新評(píng)分屬于B 類，即用戶是新物品，在物品特征矩陣中添加新的特征向量q，并且利用式（6）進(jìn)行相應(yīng)的訓(xùn)練。

（3）當(dāng)一個(gè)新評(píng)分屬于C 類，即用戶是新用戶且是新物品，分別在用戶特征矩陣和物品特征矩陣中添加新的特征向量p和q，并且利用式（5）、式（6）進(jìn)行相應(yīng)的訓(xùn)練。

（4）當(dāng)一個(gè)新評(píng)分屬于D 類，即用戶是老用戶且是老物品，對(duì)其進(jìn)行部分抽取得到相應(yīng)的動(dòng)態(tài)矩陣進(jìn)行訓(xùn)練，具體的抽取過(guò)程在2.2.4 小節(jié)中進(jìn)行介紹。

在對(duì)某一個(gè)用戶或物品評(píng)分預(yù)測(cè)訓(xùn)練過(guò)程中，用戶或物品的數(shù)據(jù)過(guò)于稀疏會(huì)導(dǎo)致數(shù)據(jù)預(yù)測(cè)的準(zhǔn)確性降低，但評(píng)分的數(shù)據(jù)過(guò)多時(shí)，又會(huì)造成不必要的計(jì)算浪費(fèi)。考慮到這點(diǎn)，本文在模型訓(xùn)練過(guò)程中，將用戶和物品特征的最大訓(xùn)練次數(shù)設(shè)置了一定的閾值，定義為、。當(dāng)某個(gè)用戶或物品的訓(xùn)練次數(shù)到達(dá)閾值后，此用戶或物品的相應(yīng)特征便不再被訓(xùn)練，該閾值是一個(gè)超參數(shù)，由實(shí)驗(yàn)得到最優(yōu)值，過(guò)濾機(jī)制的更多細(xì)節(jié)將在偽代碼中進(jìn)行介紹。

在迭代訓(xùn)練過(guò)程中，隨著數(shù)據(jù)的實(shí)時(shí)進(jìn)入，每個(gè)參數(shù)在訓(xùn)練過(guò)程中都會(huì)發(fā)生一定的改變，并且參數(shù)改變的影響是全局性的。在增量過(guò)程中，隨著新數(shù)據(jù)的進(jìn)入，為保證利用部分新數(shù)據(jù)來(lái)達(dá)到預(yù)測(cè)全局的目的，在提取動(dòng)態(tài)評(píng)分矩陣時(shí)，針對(duì)不同的數(shù)據(jù)區(qū)域，采取不同的數(shù)據(jù)處理方法。首先對(duì)于新加入的評(píng)分，讀取其相應(yīng)的用戶和物品id，在計(jì)算過(guò)程中通過(guò)初始評(píng)分矩陣上訓(xùn)練的用戶和物品特征向量命名為p和q,在新數(shù)據(jù)進(jìn)入過(guò)程中，抽取部分?jǐn)?shù)據(jù)形成新的動(dòng)態(tài)矩陣∈R，動(dòng)態(tài)矩陣中的每一行代表一個(gè)新用戶，每一列代表一個(gè)新物品。另外為了保證數(shù)據(jù)的相關(guān)性，將初始評(píng)分矩陣中和動(dòng)態(tài)矩陣中有交叉的數(shù)據(jù)也放入動(dòng)態(tài)矩陣中，這樣在動(dòng)態(tài)矩陣中，存在三種類型的數(shù)據(jù)：新加入的數(shù)據(jù)、初始評(píng)分?jǐn)?shù)據(jù)、空值。在動(dòng)態(tài)矩陣訓(xùn)練的用戶和物品特征矩陣稱之為p、q，在初始矩陣的用戶和物品特征矩陣稱之為p、q。提取動(dòng)態(tài)矩陣如圖2 所示。

圖2 提取動(dòng)態(tài)矩陣Fig.2 Extracting dynamic matrix

對(duì)現(xiàn)有數(shù)據(jù)集中的有關(guān)數(shù)據(jù)進(jìn)行提取之后，利用此矩陣進(jìn)行數(shù)據(jù)訓(xùn)練，p、q、p、q訓(xùn)練公式如下：

2.3 評(píng)分預(yù)測(cè)策略

本文將預(yù)測(cè)模塊分為兩部分，一個(gè)是初始訓(xùn)練的部分，一個(gè)是隨著數(shù)據(jù)的進(jìn)入的增量矩陣的預(yù)測(cè)部分，兩部分評(píng)分預(yù)測(cè)公式為：

兩個(gè)模塊的結(jié)合預(yù)測(cè)權(quán)重由實(shí)驗(yàn)來(lái)確定。

下面是Inc++算法的偽代碼部分：

參數(shù)：、、_、_、、。

3 實(shí)驗(yàn)

3.1 實(shí)驗(yàn)數(shù)據(jù)集及設(shè)置

實(shí)驗(yàn)采用的數(shù)據(jù)集為Movielens-100K和Movielens-1M，其中Movielens-100K 包含943 個(gè)用戶、1 682 個(gè)物品。Movielens-1M 包含6 040 個(gè)用戶、3 952 個(gè)物品。將數(shù)據(jù)集亂序劃分為三部分：初始數(shù)據(jù)集、增量數(shù)據(jù)集、測(cè)試集。初始數(shù)據(jù)集設(shè)置為整體數(shù)據(jù)的10%，測(cè)試集設(shè)置為整體數(shù)據(jù)的10%，增量數(shù)據(jù)集設(shè)置為整體數(shù)據(jù)的80%。用戶和電影的特征維度設(shè)置為10，學(xué)習(xí)步長(zhǎng)設(shè)置為0.02，學(xué)習(xí)率設(shè)置為0.3。Movielens-100K 數(shù)據(jù)集每次增量數(shù)據(jù)閾值設(shè)為500，Movielens-1M 數(shù)據(jù)集每次增量數(shù)據(jù)閾值為設(shè)為5 000，全局更新閾值設(shè)為50 000。評(píng)價(jià)標(biāo)準(zhǔn)為平方根誤差，公式如下：

該算法將IR算法和IncRMF 算法的精度和時(shí)間值作為對(duì)比來(lái)進(jìn)行對(duì)比實(shí)驗(yàn)。

本文的所有實(shí)驗(yàn)都是在同一硬件平臺(tái)上進(jìn)行的（Intel Core i5 CPU，8 GB 內(nèi)存，Win10 64OS）。

3.2 實(shí)驗(yàn)結(jié)果及分析

不同的權(quán)重系數(shù)和用戶、物品的更新閾值對(duì)實(shí)驗(yàn)結(jié)果的影響不同，為了突出主題，實(shí)驗(yàn)結(jié)果并沒(méi)有在這里進(jìn)行展示，經(jīng)3 次隨機(jī)實(shí)驗(yàn)測(cè)得當(dāng)權(quán)重系數(shù)為0.4 和更新閾值為16 時(shí)RMSE 達(dá)到最優(yōu)值，后續(xù)實(shí)驗(yàn)均在兩者取最優(yōu)值的情況下進(jìn)行。

圖3 和圖4 分別顯示了在數(shù)據(jù)集Movielens-100K和Movielens-1M 初始數(shù)據(jù)占10%的條件下RMSE 和時(shí)間對(duì)比實(shí)驗(yàn)結(jié)果。在兩個(gè)數(shù)據(jù)集下，算法表現(xiàn)是相似的。首先在精度方面：從實(shí)驗(yàn)結(jié)果可看出，在初始階段數(shù)據(jù)量較小時(shí)，Inc++算法具有良好的精度，這也表明該算法可以更好地適應(yīng)冷啟動(dòng)過(guò)程。隨著數(shù)據(jù)量的增加，IR算法和Inc++算法精度相差不大，精度差小于0.01，Inc 算法精度是表現(xiàn)最差的。但從時(shí)間方面可以看出，Inc 算法速度是最快的，Inc++算法比IR算法要快得多。

圖3 RMSE 和Time對(duì)比（Movielens-100K）Fig.3 Comparison of RMSE and Time（Movielens-100K）

圖4 RMSE 和Time對(duì)比（Movielens-1M）Fig.4 Comparison of RMSE and Time（Movielens-1M）

從實(shí)驗(yàn)結(jié)果綜合分析可得：首先在精度方面，IR、Inc++這兩個(gè)算法的精度高于Inc 算法，但在冷啟動(dòng)的情況下，Inc++算法能更好地發(fā)揮優(yōu)勢(shì)，較其他算法精度較高。其次在時(shí)間花銷方面，Inc++算法在時(shí)間花銷方面遠(yuǎn)遠(yuǎn)小于IR算法，相比于IR算法，Inc++由于每條新的特征訓(xùn)練都要達(dá)到擬合，在時(shí)間花銷方面是較大的，Inc 算法只針對(duì)新的用戶或新的物品，老用戶、老物品不進(jìn)行更新特征，因此精度的損失較大。Inc++集合了兩個(gè)算法的優(yōu)點(diǎn)，并且在訓(xùn)練過(guò)程中加入偏執(zhí)信息，使得在時(shí)間方面比IR算法大大節(jié)省時(shí)間花銷，但是相比Inc 算法精度又有了明顯的提高，達(dá)到了較好的效果。

4 總結(jié)與展望

綜合時(shí)間和精度兩方面來(lái)說(shuō)，Inc++算法表現(xiàn)最優(yōu)。本研究的算法具有較好的準(zhǔn)確度和實(shí)用性且總體時(shí)間花銷較小，但是相比Inc 算法仍然在時(shí)間復(fù)雜度方面相差較明顯。以后的工作方向?qū)⒗^續(xù)研究如何減少訓(xùn)練時(shí)間，提高算法訓(xùn)練的精度。其次，Inc++算法在數(shù)據(jù)量較小時(shí)表現(xiàn)優(yōu)異，之后的研究也會(huì)針對(duì)冷啟動(dòng)這個(gè)問(wèn)題繼續(xù)深究。