一種基于聚類預填充的SVD算法

魏浩， 張偉， 郭新明

(咸陽師范學院 計算機學院， 陜西 咸陽 712000)

0 引言

隨著電子商務的快速成長和網絡購物的迅速普及，如何使用戶在數量龐大的商品中快速、高效地找到他們感興趣的商品，是電子商務網站面臨的一個重大挑戰。推薦系統不需要用戶主動參與，能根據用戶以往的商品購買記錄，獲得用戶興趣，把用戶可能感興趣的商品進行推薦，滿足用戶的個性化需求[1-2]。

目前應用最廣泛的推薦算法包括基于內容的推薦算法和協同過濾(Collaborative Filtering，CF)算法，協同過濾算法使用用戶與商品的歷史交互數據，并通過分析其他人的興趣偏好，建立當前用戶偏好模型，這就是“協同”的體現，它基于存在一組興趣偏好相似的用戶群的假設。相比較基于內容的推薦算法，協同過濾算法對音頻、圖像等難以提取特征的非結構化對象有較好的推薦效果[3-4]。

1 數據稀疏性問題

協同過濾算法根據用戶群體社會化的特點，具有高度自動化、新興趣發現等優勢，并且能夠對非結構化對象進行推薦，因此在推薦系統中被廣泛使用，但它存在稀疏性、冷啟動和擴展性等問題[5-7]。在電子商務系統中，由于用戶和商品數量的急劇增加，加之用戶缺乏對商品評分的主動性，使得用戶評分的商品數量只占很少的一部分，用戶—商品評分矩陣(表)非常稀疏，用戶—商品矩陣的高度稀疏將造成相似計算的很大誤差，進而影響推薦系統的推薦質量和推薦性能[8-10]。

解決數據稀疏性問題的主要方法有：降維技術、評分矩陣預填充、多種特征融合、數據聚類和相似度改進算法[11-14]。文獻[15]采用奇異值分解技術和隨機梯度下降法填充稀疏矩陣，優化用戶相似度，提高了推薦算法的有效性。文獻[16]首先提取項目屬性特征，并利用余弦相似度對評分矩陣的缺失值進行填充，然后通過對填充的矩陣執行奇異值分解 (Singular Value Decomposition，SVD)算法，尋找隱性特征，建立隱語義模型。文獻[17]針對數據稀疏問題，選擇非精確拉格朗日乘子法對稀疏矩陣填充，對填充的矩陣使用SVD協同過濾算法進行推薦，提高了推薦質量。

2 改進的基于聚類預填充的SVD算法

大多數推薦系統中，用戶評過分的項目很少，項目之間的共同評分更少，會使得計算項目間的相似度誤差較大，得到的項目近鄰集合也有偏差[18-19]，SVD算法一般使用項目評分的平均值填充評分矩陣，平均值填充未考慮不同類別用戶對項目評分的差異性，因此會產生較大的誤差。針對這種情況本文提出了一種基于聚類預填充的SVD算法(Cluster Pre-filling SVD，CP-SVD)，算法基于聚類的稀疏數據預處理方法，首先由用戶歷史評分和項目特征生成用戶—項目興趣矩陣，再聚類用戶并填充用戶—評分矩陣，通過填充后的用戶-評分矩陣，再使用SVD算法預測用戶對未評分項目的評分，提高預測的精度和推薦的準確度。

在一個推薦系統中，一般包含的項目數量十分巨大，而項目特征的個數要遠遠小于項目數，例如Movielens-100k數據集，電影的數目有1 682部，而電影的類型只有19種，一部電影可以屬于一個或多個不同的類型，用戶—電影評分矩陣(用戶—項目評分矩陣)的數據稀疏度為0.937。改進的基于聚類的協同過濾推薦算法通過將用戶—電影評分矩陣轉化為用戶—電影類型興趣矩陣(用戶—項目特征興趣矩陣)，使用用戶—電影類型興趣矩陣聚類用戶,并填充用戶—電影評分矩陣，大幅降低用戶—電影評分矩陣稀疏度。假設一個推薦系統中，包括N個用戶和M個項目，R為用戶—項目評分矩陣記作[ru,i]N×M，其中ru,i表示用戶u對項目i的評分；M個項目、Q個項目特征以及項目—項目特征矩陣V=[vi,f]M×Q，算法生成N個用戶對Q個項目特征的用戶—項目特征興趣矩陣T=[tu,f]N×Q。以Movielens-100k數據集為例，算法步驟描述如下。

(1) 數據讀入和預處理：讀入用戶對電影的評分集合，把用戶對電影的評分集合分成訓練集train和測試集test兩部分，使用訓練集部分生成用戶—電影評分矩陣R=[ru,i]N×M，讀入電影的類型描述集合，生成電影—電影類型矩陣(項目—項目特征矩陣)V=[vi,f]M×Q。

(4) 使用用戶—電影類型興趣矩陣T對用戶聚類：將矩陣T的每一行作為一個用戶—電影類型興趣向量，選擇K-均值聚類，設定聚類的個數k，進行聚類運算。

(7) 計算推薦準確率和召回率：依據給定TOP-N的N值生成推薦給用戶的電影集合top-N，計算推薦準確率和召回率。

3 實驗描述及結果分析

實驗使用的編程語言是Python3.7，開發工具為Jupyter notebook，實驗程序還使用了兩個擴展程序庫NumPy和Pandas。NumPy是一個基礎性的Python科學計算庫，提供高維度數組與矩陣的計算能力，并提供大量方便用戶調用的函數庫[20]。Pandas是一個數據分析包，通過提供的標準數據結構以及快速、靈活的操作，成為了Python環境下高效而強大的數據分析工具[21]。

實驗所使用的數據集是Movielens-100k，由943名線上電影觀眾針對1 682部電影共10萬條評分記錄組成。該數據集包含電影的類型描述、用戶信息和用戶對電影的評分3個數據集文件，電影類型有19種，用戶對電影的評分是1到5的整數，每部電影至少被評價1次，每個用戶至少給20部電影評過分。原始數據隨機分成5份，每次將其中4份數據作為訓練數據，另一份作為測試數據，運行5次并將5次實驗結果的平均值作為最終的評測值。

實驗選擇3個推薦算法評價指標包括推薦精度(MAE)、準確率(Precision)以及召回率(Recall)，使用這3個評價指標，將改進的基于聚類預填充的SVD算法(CP-SVD)與SVD算法以及傳統的基于項目的協同過濾推薦算法(Item-based CF，ICF)進行比較。ICF算法需要確定的參數是用戶K最近鄰的K值，SVD和CP-SVD算法共同的參數是保留的信息量δ，CP-SVD算法還需要確定聚類的個數k。

(1) CP-SVD算法聚類的個數k值取5、10、20、30、40，保留的信息量δ取值由0.8至1.0，CP-SVD算法的MAE在k值一定的情況下，隨δ值變化趨勢如圖1所示。

圖1 K取值從5到40時CP-SVD算法MAE比較

當k=5時，MAE值隨K值的變化曲線位于k等于10、20、30、40四個曲線的下方，說明CP-SVD算法的聚類個數k取值在5附近時，預測精度較高。

(2) 保留的信息量δ取值由0.8至1.0，CP-SVD算法聚類的個數k值取2至6生成的5條MAE值變化曲線及SVD算法的MAE值變化曲線,如圖2所示。

圖2 在K取值從2到6時CP-SVD算法MAE比較

從總體來看，k等于5時的曲線位于k等于其他值的曲線下方，說明CP-SVD算法聚類的個數k值取5時，算法預測精度高。

(3) 最近鄰數目K值由10到200，且為10的整數倍，ICF算法的MAE值隨用戶最近鄰數目K變化曲線,如圖3所示。

圖3 ICF算法MAE隨N值變化曲線

當K=30時，MAE值最小，MAE=2.716。

(4) TOP-N推薦的N值取值由10到200，且為10的整數倍，ICF最近鄰數K值取30，SVD和CP-SVD算法保留的信息量(δ)為0.99，且CP-SVD聚類個數K等于5，ICF、SVD和CP-SVD三種算法的預測準確率曲線和預測召回率曲線，如圖4、圖5所示。

圖4 三種算法準確率比較

圖5 三種算法召回率比較

CP-SVD算法的推薦準確率和召回率遠高于CFAASP算法；CP-SVD準確率和召回率隨N值變化曲線始終位于ICF算法曲線的上方，在N取值相同時，CP-SVD算法的準確率和召回率高于ICF算法。

4 總結

本文使用Movielens-100k數據集，選擇了3個推薦算法評價指標，將改進的基于聚類預填充的SVD算法(CP-SVD)與SVD算法以及傳統的基于項目的協同過濾推薦算法(ICF)進行比較。由實驗得出聚類個數k=5時的CP-SVD算法的MAE值最小，且小于SVD算法；最近鄰K等于30時，ICF算法的MAE值最??；聚類個數k等于5、保留信息量(δ)等于0.99的CP-SVD算法的準確率和召回率，大于保留信息量(δ)等于0.99的SVD算法值及最近鄰K等于30的ICF算法。從總體來看，改進的基于聚類預填充的SVD算法(CP-SVD)預測精度、推薦準確率和召回率高于SVD算法以及傳統的基于項目的協同過濾推薦算法(ICF)。