一種改進用戶相似度的協(xié)同過濾推薦算法

魏 浩，劉小豫，張 偉

（咸陽師范學院計算機學院，陜西 咸陽 712000）

隨著互聯(lián)網的高速發(fā)展，社會進入了一個“信息爆炸”時代。尤其伴隨著電子商務的快速成長和網絡購物的迅速普及，如何使用戶在數量龐大的商品中快速、高效地找到感興趣的商品，是電子商務網站面臨的一個重大挑戰(zhàn)。雖然用戶能夠通過電子商務網站的搜索功能獲得商品信息，但要求用戶使用關鍵字確切描述自己的需求，在不能準確描述所想購買商品的情況下，搜索功能無法發(fā)揮應有的作用。推薦系統(tǒng)不需要用戶主動參與，就能根據用戶以往的商品購買記錄，推薦滿足用戶興趣的商品。推薦系統(tǒng)不但增強了用戶購物體驗，而且通過發(fā)現(xiàn)潛在購買者，有針對性地推薦商品，使銷售利潤最大化，達到了雙贏的效果。

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

1 基于用戶的協(xié)調過濾算法

協(xié)同過濾推薦算法主要包括基于用戶（Userbased CF，UCF）和基于項目（Item-based CF，ICF）兩種協(xié)同過濾算法[6]。基于用戶的協(xié)同過濾推薦算法包括以下3個階段：

1）相似度計算：相似度計算的方法主要有Person相關系數、Jaccard相關系數以及余弦相似度[7]。計算余弦相似度時，需計算用戶評分向量之間的余弦夾角，即為兩向量的點積與其模的乘積之商，用來衡量兩個用戶之間的相似度，設兩個用戶u和v的評分向量分別為和，則兩個用戶之間的相似度如式（1）所示：

2）用戶最近鄰搜尋：通常用戶最近鄰搜尋的辦法有兩種，基于閾值設定和基于K最近鄰搜尋。對于第一種方法，若相似度高于閾值即可進入最近鄰集合，反之則剔除。而第二種方法中，根據相似度將目標用戶的近鄰用戶進行排序后，選取前K個用戶進入最近鄰集合。兩種方法都會面對如何設計閾值和選取K值的問題，K值過大會導致在最近鄰集合中引入不相似或干擾用戶，從而影響最終的推薦效果；K值過小則可能導致最近鄰集合信息不全，同樣不利于推薦效果。

3）預測評分并生成top-N推薦：完成最近鄰搜尋后能夠獲得目標用戶的近鄰集，可用式（2）預測未評分項目的評分，將項目按照預測評分降序進行排序，把前N個項目推薦給目標用戶。

式中，用戶u的最近鄰集合為C，用戶u與鄰近用戶v之間的相似度為wuv，鄰近用戶v對項目j的評分為Rv,j，Pu,j為目標用戶u對未評分項目j的預測評分。

2 推薦算法的評價標準

推薦算法的準確度是衡量推薦算法優(yōu)劣的關鍵，推薦算法評價指標包括對預測評分準確度和top-N推薦準確度兩類評價指標，對top-N推薦準確度的評價指標主要有召回率（Recall）和準確率（Precision），對預測評分準確度的評價指標通常包括平均絕對誤差（Mean Absolute Error，MAE）和均方根誤差（Root Mean Square Error，RMSE）[8-9]。

平均絕對誤差與均方根誤差利用預測評分與真實評分間的誤差大小來衡量系統(tǒng)的預測精度。MAE和RMSE值越小說明推薦質量越高，預測的評分與實際評分誤差越小。MAE及RMSE的計算公式為：

其中，{p1,p2,…,pn}為預測的用戶評分集合，{q1,q2,…,qn}為實際的用戶評分集合，n為用戶評價的項目數量。

準確率（Precision）表示推薦列表中推薦的準確項目所占的比例，如式（5）所示：

召回率（Recall）是用戶推薦準確的項目在測試集中所占的比值，如式（6）所示：

其中，test為測試集，top-N為預測評分的前N個項目，|L|表示設定的推薦列表長度。

3 數據稀疏性問題

協(xié)同過濾算法具有用戶群體社會化的特點，且高度自動化、新興趣發(fā)現(xiàn)等優(yōu)勢，能夠推薦非結構化對象，因此在推薦系統(tǒng)中被廣泛使用，但其存在稀疏性、冷啟動和擴展性等問題[10-12]。

在電子商務系統(tǒng)中，由于用戶和商品數量的急劇增加，加之用戶缺乏對商品評分的主動性，使得用戶評分的商品數量只占很少的一部分，用戶與商品評分矩陣（表）非常稀疏，用戶-商品矩陣的高度稀疏將造成相似計算出現(xiàn)很大誤差，進而影響推薦系統(tǒng)的推薦質量和推薦性能。數據的稀疏性用稀疏度（Sparsity）表示，稀疏度是指評分矩陣中空值的數目與矩陣元素總數的比值，如式（7）所示：

其中，|R|表示評分數，|I|表示項目數或商品數，|U|表示評分者數，Sparsity是所得的稀疏度[13]。

解決數據稀疏性問題的主要方法有降維技術、評分矩陣預填充、多種特征融合、數據聚類、以及相似度改進算法[14]。相似度計算作為協(xié)同過濾算法的重要部分，但由于評分矩陣的稀疏性，使兩個用戶之間的共同評分項數量很小，因此，傳統(tǒng)計算相似度的方法會出現(xiàn)很大誤差。文獻[15]針對社交網絡，提出了屬性相似度及其構成與計算方法，有效地提高了推薦準確率。文獻[16]在數據高度稀疏的情況，建立了梯形模糊的評分模型，并使用該模型計算用戶之間的相似度。文獻[17]針對評分矩陣的稀疏性，提出了一種加權相似度算法，以減小評分矩陣稀疏性導致的相似度誤差。

4 改進用戶相似度的推薦算法

在大多數推薦系統(tǒng)中，用戶評過分的項目很少，計算用戶之間的相似性會產生很大的誤差，使得生成的用戶近鄰集合與實際的近鄰集合有較大差異。同理，基于項目的協(xié)同過濾算法項目之間的共同評價也很少，使得計算的項目間的相似度誤差較大，得到的項目近鄰集合也有偏差[18-19]。文中提出了一種改進用戶相似度的協(xié)同過濾推薦算法（Improved user similarity User-based CF，IUCF），該算法基于項目特征的稀疏數據預處理方法，結合用戶的已評分信息及項目的特征，生成用戶與項目特征興趣矩陣，使用用戶與項目特征興趣矩陣計算用戶的相似度，提升用戶相似度的準確率，最終提高推薦的精度和準確度。

在一個推薦系統(tǒng)中，一般包含的項目數量十分巨大，而項目特征的個數要遠遠小于項目數，例如Movielens-100k數據集，電影的數目有1 682部，而電影的類型只有19種，一部電影可以屬于一個或多個不同的類型。由用戶與項目評分矩陣（表）生成的用戶與項目特征興趣矩陣，將大幅降低數據稀疏度，例如，在Movielens-100k數據集中，觀眾與電影評分矩陣（用戶與項目評分矩陣）的數據稀疏度為0.937，生成的觀眾與電影類型興趣矩陣（用戶與項目特征興趣矩陣）的數據稀疏度為0.205。由于觀眾與電影類型興趣矩陣數據密度的提高，觀眾之間共同評分項數量增多，因此，使用觀眾與電影類型興趣矩陣計算得到的觀眾相似度更加準確，更能反映觀眾對不同類型電影的偏好。

假設在一個包括N個用戶和M個項目的推薦系統(tǒng)中，R為用戶與項目評分矩陣，記作[Ru,i]N×M，其中，Ru,i表示用戶u對項目i的評分。以Movielens-100k數據集為例，算法步驟描述如下：

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

2）由觀眾與電影評分矩陣R生成觀眾與電影興趣矩陣R′：對于觀眾與電影評分矩陣R中的每個評分項Ru,i，當評分項Ru,i≧1時，設定Ru,i=1，生成的觀眾與電影興趣矩陣為。

3）由觀眾與電影興趣矩陣R′和電影與電影類型矩陣V生成觀眾與電影類型興趣矩陣（用戶與項目特征興趣矩陣）T：觀眾與電影興趣矩陣和電影與電影類型矩陣相乘得到中間結果矩陣，然后求出T′每行的和，計算得到矩陣T的每個元素，生成觀眾與電影類型興趣矩陣T。

4）使用觀眾與電影類型興趣矩陣T生成觀眾間相似性矩陣S=[Su,v]N×N：選擇余弦相似度，計算每一個觀眾和其他觀眾的相似性，組成觀眾相似性矩陣S，通過式（1）計算可得到觀眾相似性矩陣S的元素Su,v，和是觀眾u和v在矩陣T中的觀眾與電影類型興趣向量。

5）搜索最近鄰：在不同數目的K最近鄰情況下，對測試集中的每個觀眾，在觀眾相似性矩陣S中搜索與該觀眾相似度最大的前K個觀眾組成最近鄰集合。

6）預測測試集中的觀眾對電影的評分：根據式（2）預測用戶對1 682部電影的評分，例如測試集中的觀眾u，對電影的實際評分集合為{q1,q2,…,qn}，對應電影的預測評分集合為{p1,p2,…,pn}{p1,p2,…,pn}，根據式（3）計算MAE。

7）計算推薦準確率和召回率：依據給定top-N的N值生成推薦給觀眾的電影集合top-N，test為測試集，按照式（5）計算推薦準確率，按照式（6）計算推薦召回率。

5 實驗描述及結果分析

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

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

實驗選擇了4個推薦算法評價指標包括推薦精度(MAE)、準確率（Precision）、召回率（Recall）以及預測耗時，使用這4個評價指標將IUCF算法與UCF進行比較。預測耗時是在同樣的條件下比較兩種推薦算法，計算推薦結果耗費的時間。該算法最主要的參數是用戶最近鄰的K值，選擇用戶不同的近鄰數目對算法的結果有重要影響。

1）用戶最近鄰K值的取值范圍為10～300，且為10的整數倍，UCF算法和IUCF算法的MAE值隨K值的變化趨勢如圖1所示。當K小于140時，IUCF算法的MAE值小于UCF算法，K值越小，兩種算法的MAE差值越大；隨著K值的增大，當K大于140時，兩種算法的MAE趨于相等。說明相比傳統(tǒng)的UCF算法，其在用戶最近鄰K值越小時，預測的評分與觀眾實際評分更接近，推薦精度更高；當K大于140時，兩種算法預測的評分基本相同，推薦精度也大致相等。

圖1 算法MAE比較

2）K的取值方法與上面相同，取值范圍為10～300，且為10的整數倍，兩種算法預測耗時隨K值的變化如圖2所示。當K小于140時，IUCF算法的預測耗時小于UCF算法，當K大于140時，兩種算法的預測耗時基本相等，并且隨著K值的增大，兩種算法預測耗時都趨于相同的值。從圖2可知，當K小于140時，IUCF算法比UCF算法效率更高，當K大于140時，兩種算法效率基本相同。

3）兼顧評分預測的準確率和算法執(zhí)行效率，最近鄰數目K值取為140，top-N推薦的N取值范圍為10～500、且為10的整數倍，兩種算法的準確率隨N值的變化如圖3所示。兩種算法準確率曲線的基本趨勢是隨著N值的增加，準確率提高，當N等于360時，UCF算法的準確率最高；當N等于380時，IUCF算法的準確率最高。IUCF算法的準確率曲線始終位于UCF算法的準確率曲線上方，IUCF算法相比UCF算法準確率平均提高了0.45%，說明IUCF算法的準確率總體優(yōu)于UCF算法。

圖3 算法準確率比較

4）同樣取K為140，兩種算法的召回率隨top-N推薦的N值變化如圖4所示。N值由10至500，且為10的整數倍，兩種算法的召回率都隨N值增大而提高，但IUCF算法召回率曲線始終位于UCF算法召回率上方，IUCF算法相比UCF算法召回率平均提高了5.2%，說明IUCF算法的召回率整體優(yōu)于UCF算法。

圖4 算法召回率比較

6 結論

文中使用Movielens-100k數據集，選擇了4個推薦算法評價指標，對比改進的用戶相似度協(xié)同過濾推薦算法（IUCF）和傳統(tǒng)的基于用戶的協(xié)同過濾算法（UCF）。在用戶最近鄰數目K小于140時，改進的用戶相似度協(xié)同過濾推薦算法推薦精度高，預測評分準確，推薦消耗的時間少，推薦效率高，而當用戶最近鄰數K大于140時，兩種算法的推薦精度和推薦消耗時間趨于相等。在用戶最近鄰數K=140并且top-N推薦的N取值范圍為10～500的條件下，IUCF算法的準確率及召回率從總體上看高于UCF算法。