基于SVD與層次聚類的協同過濾推薦算法實現

徐澤兵　王忠

摘要：在如今這個信息爆炸的時代，我們要面對“信息過載”這一難題；以個性化推薦技術為核心的推薦系統有效的解決這一問題，其中協同過濾算法是目前應用最廣泛也是最成熟的個性化推薦技術。基于此，本文提出一種基于SVD與層次聚類中的BIRCH算法來實現協同過濾算法。該算法在MovieLens數據集上的實驗數據表明該算法有效的提高了推薦的質量。

關鍵詞：個性化推薦；SVD；BIRCH算法

中圖分類號：TP312 文獻標識碼：A 文章編號：1007-9416（2018）01-0130-02

最近幾年，協同過濾算法[1]是比較成功并具有代表性的推薦算法，目前協同過濾算法大致分為兩類：一是基于內存的協同過濾算法；二是基于模型的協同過濾算法。

本文針對數據的稀疏性、可擴展性等問題提出了基于奇異值分解與BIRCH層次聚類算法[2]的協同過濾算法。并且使用物理學上的能量守恒定律來確定SVD在降維時保存盡可能多的信息。使用BIRCH聚類算法縮小查詢最近鄰時的范圍。實驗表明，本文算法能夠提高推薦質量。

1 傳統的基于用戶的協同過濾算法

在傳統的基于用戶的協同過濾算法中，我們完成推薦的過程一般分為下面幾個步驟：第一：構建評分矩陣：第二：計算相似度，確定K個最近鄰；第三：完成預測評分，實現推薦。因此我們完成的推薦的第一步就是對數據進行初始化，構建評分矩陣。

1.1 數據初始化

將用戶集及評分項目集合構造出一個評分矩陣，其中代表有m個用戶，代表有n個項目，表示用戶對項目的評分值。

1.2 獲取最近鄰集合

基于用戶的協同過濾算法完成推薦功能的第二步是為目標用戶找到最近鄰的集合，最近鄰集合的確定是通過計算相似度來確認的，皮爾森相關系數在計算相似度時更加的準確，設來表示用戶u與v之間的相似度，公式如下：

2 基于SVD與BIRCH層次聚類的協同過濾算法

在本節中將對本文提出的改進算法進行詳細敘述，本算法的主要思想為：首先，通過奇異值分解對原始的用戶評分矩陣進行預處理：構造出用戶相關矩陣；其次，利用BIRCH算法進行歸類，形成K個用戶簇；之后根據目標用戶確定目標簇并確定最近鄰；最后實現top-N推薦。以下將詳細敘述該算法的過程：

2.1 構造用戶相關矩陣

在利用SVD進行降維時，所選擇的降維維數k很重要，在本文中我們將保存原始矩陣的多少能量定義為能量閾值s。我們確定了s的值之后，就可以反向確定維度值k。此能量閾值的值為對角矩陣的前k個奇異值的能量除以全部奇異值的能量的結果。

確定k值之后，我們就可以將對角矩陣只保留前k個奇異值形成新的對角矩陣，從中取前k列變成，從中取前k行變成，其中k遠遠小于m和n的值，這樣就達到了降維的目的。

經過上面的一系列矩陣分解降維處理之后，我們得到了用戶特征矩陣，后面的分析都是基于此矩陣。

2.2 使用BIRCH算法對用戶矩陣進行分類

在經過上一節的SVD處理之后我們得到用戶特征矩陣，為了更加高效的獲取到目標用戶的最近鄰，使用BIRCH算法對該矩陣進行聚類。主要思想是：利用樹結構幫助我們進行快速的聚類，一般把其稱作聚類特征樹（CFTree）。該樹的任一節點都是由若干個聚類特征（CF）組成的。流程如下為：

（1）在內存中構建CF樹；

（2）以CF樹葉元項對應的子簇為基礎，實現數據點的聚類；

2.3 改進算法的描述

綜合第二節的傳統協同過濾算法以及本節前面對SVD以及BIRCH算法的描述，我們可以對本文改進算法進行簡要描述：

輸入：用戶-項目評分矩陣，目標用戶；輸出：對目標用戶進行Top-N推薦。

（1）對用戶-項目矩陣進行SVD降維處理，根據公式得到用戶特征矩陣；

（2）對用戶特征矩陣進行BIRCH聚類，然后確定和目標用戶相似的簇；

（3）根據皮爾森相關系數確定最近鄰集合；

（4）對目標用戶未評分的項目進行評分；

（5）根據預測評分結果實現Top-N推薦。

3 實驗結果及分析

本文采用的數據實驗集為MovieLens數據集。該數據集中的信息包含了一共943個用戶對于1682部電影的十萬條評分。評分值是1至5的整數，數字越高代表評分越高。

3.1 算法推薦質量度量標準

平均絕對誤差（MAE）是常用的評判標準，其原理是計算用戶對項目的預測評分值與實際評分值之間的偏差。MAE的值越小，代表推薦的質量越高。設預測評分集合為，實際評分集合為，公式如4-2所示：

3.2 實驗結果及分析

在對用戶-項目矩陣進行奇異值分解時，選擇適當的降維維數很重要，過低會損失過多的信息量，過高的話失去降維的意義。通過實驗當選擇k為17時，MAE的值最低，推薦的性能最好。

為了驗證改進算法的性能，我們將該算法與knn算法以及基于SVD的推薦算法進行比較，在取不同的近鄰個數的情況下各算法的推薦性能：

由圖1所示，當我們的近鄰個數達到一定數目后，我們的改進算法推薦效果更加高效。

4 結語

本文提出的基于SVD與BIRCH層次聚類的協同過濾算法的優勢有：第一，SVD對原始矩陣進行降維處理，有效的解決了數據稀疏性的問題；第二，BIRCH算法在求目標用戶的最近鄰時，縮小了搜索范圍，有效提高算法運行時間。當然算法也有不足之處，例如當數據量過大時，SVD算法的效率會有所降低，這也是之后論文的研究改進方向。

參考文獻

[1]楊陽，向陽，熊磊.基于矩陣分解與用戶近鄰模型的協同過濾推薦算法[J].計算機應用，2012，32（2）：395-398.

[2]蔣盛益，李霞.一種改進的BIRCH聚類算法[J].計算機應用，2009，29（1）：293-296.