改進的增量式動靜結合協同過濾方法

武 美，丁怡彤，趙建立+

1.山東科技大學 計算機科學與工程學院，山東 青島 266590

2.東北林業大學 信息與計算機工程學院，哈爾濱 150040

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

本文的主要貢獻如下：

（1）將預測部分劃分為增量部分和靜態部分，保證精度的同時提高預測的效率。

（2）將訓練數據按照一定標準劃分為不同的區域，對不同區域采取不同的計算方法，有效提高計算效率。

（3）對數據的訓練過程采取過濾機制，有效提高計算效率。

1 相關工作

在增量計算的之前相關研究中，Luo 等人提出了一種I-KNN（incremental K nearest neighborhood）模型，在Miranda 等人提出的RS-KNN（random subspace K nearest neighborhood）模型的基礎上減少了存儲復雜性，同時采用廣義骰子系數保持了預測精度，但相應的計算復雜度增加。

Wang 等人提出了將聚類技術和非負矩陣分解結合的方法來進行評分的預測工作，通過一種快速聚類方法將聚類的個數作為矩陣的維度可以實時更新，避免設置的固定維度造成在數據量較小時造成的計算浪費，但是將聚類的簇數作為維度的定義缺乏可靠性，且跟隨數據集的不同在計算效率方面差別較大。

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

Luo 等人提出了IR（incremental and static combined RMF-based recommender）算法。此算法可以適應大量的新數據并且能做出較準確的預測，但是在新數據進入后的預測過程中，抽取數據花費的時長較長，在時間方面有待于進一步提高效率。

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

2 算法介紹

2.1 基礎矩陣分解算法介紹

傳統的矩陣分解算法是利用降維技術將用戶-物品評分矩陣分解為兩個低階的矩陣，通過對這兩個低階矩陣的連續優化來減小預測值和真實值之間的誤差，無限逼近原始評分數據，來達到預測用戶-物品評分矩陣中未知評分的目的。定義用戶-物品評分矩陣為∈R，特征維度為，用戶特征矩陣為∈R，物品特征矩陣為∈R，矩陣的分解公式如下：

式中，e定義為真實值與預測值之間的誤差，誤差函數的公式如下：

其中，||·||定義為標準歐幾里德范數，代表正則化項，加入正則化項的目的是為了防止過度擬合所帶來的誤差。其中各參數的訓練公式如下（p、q采用以下公式來進行更新）：

其中，代表學習的步長，其控制改變的速率，表示學習率。

2.2 增量式靜態協同過濾推薦算法（Inc++算法）

本節基于IncRMF 算法提出了一種改進的增量式動靜結合的協同過濾算法（improved incremental static combined collaborative filtering method，Inc++），該算法的目標是保證適應增量更新的效率要求且可以提供高度可靠的預測。下面將分四個小節介紹本文的算法。

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

相應的用戶偏執及物品偏執更新公式為：

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

圖1 分區域更新策略Fig.1 Regional update strategy

針對不同區域的新數據，在數據更新方面本文采用的更新策略也有所不同：

（1）當一個新評分屬于A 類，即用戶是新用戶，在用戶特征矩陣中添加新的特征向量p，并且利用前面的式（5）進行相應的訓練。

（2）當一個新評分屬于B 類，即用戶是新物品，在物品特征矩陣中添加新的特征向量q，并且利用式（6）進行相應的訓練。

（3）當一個新評分屬于C 類，即用戶是新用戶且是新物品，分別在用戶特征矩陣和物品特征矩陣中添加新的特征向量p和q，并且利用式（5）、式（6）進行相應的訓練。

（4）當一個新評分屬于D 類，即用戶是老用戶且是老物品，對其進行部分抽取得到相應的動態矩陣進行訓練，具體的抽取過程在2.2.4 小節中進行介紹。

在對某一個用戶或物品評分預測訓練過程中，用戶或物品的數據過于稀疏會導致數據預測的準確性降低，但評分的數據過多時，又會造成不必要的計算浪費。考慮到這點，本文在模型訓練過程中，將用戶和物品特征的最大訓練次數設置了一定的閾值，定義為、。當某個用戶或物品的訓練次數到達閾值后，此用戶或物品的相應特征便不再被訓練，該閾值是一個超參數，由實驗得到最優值，過濾機制的更多細節將在偽代碼中進行介紹。

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

圖2 提取動態矩陣Fig.2 Extracting dynamic matrix

對現有數據集中的有關數據進行提取之后，利用此矩陣進行數據訓練，p、q、p、q訓練公式如下：

2.3 評分預測策略

本文將預測模塊分為兩部分，一個是初始訓練的部分，一個是隨著數據的進入的增量矩陣的預測部分，兩部分評分預測公式為：

兩個模塊的結合預測權重由實驗來確定。

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

參數：、、_、_、、。

3 實驗

3.1 實驗數據集及設置

實驗采用的數據集為Movielens-100K和Movielens-1M，其中Movielens-100K 包含943 個用戶、1 682 個物品。Movielens-1M 包含6 040 個用戶、3 952 個物品。將數據集亂序劃分為三部分：初始數據集、增量數據集、測試集。初始數據集設置為整體數據的10%，測試集設置為整體數據的10%，增量數據集設置為整體數據的80%。用戶和電影的特征維度設置為10，學習步長設置為0.02，學習率設置為0.3。Movielens-100K 數據集每次增量數據閾值設為500，Movielens-1M 數據集每次增量數據閾值為設為5 000，全局更新閾值設為50 000。評價標準為平方根誤差，公式如下：

該算法將IR算法和IncRMF 算法的精度和時間值作為對比來進行對比實驗。

本文的所有實驗都是在同一硬件平臺上進行的（Intel Core i5 CPU，8 GB 內存，Win10 64OS）。

3.2 實驗結果及分析

不同的權重系數和用戶、物品的更新閾值對實驗結果的影響不同，為了突出主題，實驗結果并沒有在這里進行展示，經3 次隨機實驗測得當權重系數為0.4 和更新閾值為16 時RMSE 達到最優值，后續實驗均在兩者取最優值的情況下進行。

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

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

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

從實驗結果綜合分析可得：首先在精度方面，IR、Inc++這兩個算法的精度高于Inc 算法，但在冷啟動的情況下，Inc++算法能更好地發揮優勢，較其他算法精度較高。其次在時間花銷方面，Inc++算法在時間花銷方面遠遠小于IR算法，相比于IR算法，Inc++由于每條新的特征訓練都要達到擬合，在時間花銷方面是較大的，Inc 算法只針對新的用戶或新的物品，老用戶、老物品不進行更新特征，因此精度的損失較大。Inc++集合了兩個算法的優點，并且在訓練過程中加入偏執信息，使得在時間方面比IR算法大大節省時間花銷，但是相比Inc 算法精度又有了明顯的提高，達到了較好的效果。

4 總結與展望

綜合時間和精度兩方面來說，Inc++算法表現最優。本研究的算法具有較好的準確度和實用性且總體時間花銷較小，但是相比Inc 算法仍然在時間復雜度方面相差較明顯。以后的工作方向將繼續研究如何減少訓練時間，提高算法訓練的精度。其次，Inc++算法在數據量較小時表現優異，之后的研究也會針對冷啟動這個問題繼續深究。