基于加權Slope One填充的協同聚類推薦算法

陳嘉超 盧敏 丁偉健 陳志輝

收稿日期：2023-04-13

DOI：10.19850/j.cnki.2096-4706.2023.22.016

摘? 要：針對傳統協同過濾算法數據集稀疏性高、推薦性能差的問題，提出一種基于K-means聚類與加權Slope One填充的協同過濾推薦算法。首先以用戶特征為聚類依據，聚類生成K個用戶集群，其次通過加權Slope One算法預測并填充每個集群內部的評分矩陣，最后合并各類別的評分矩陣，設計融合Baseline算法和基于物品協同過濾算法的混合算法預測用戶評分。在MovieLens數據集上進行新算法與其他算法的對比實驗，實驗結果表明，該算法能有效緩解數據稀疏性，提高預測精度。

關鍵詞：協同過濾；用戶聚類；評分預測；個性化推薦

中圖分類號：TP391 文獻標識碼：A 文章編號：2096-4706（2023）22-0073-06

Co-Clustering Recommendation Algorithm Based on Weighted Slope One Filling

CHEN Jiachao1，2， LU Min1， DING Weijian1，2， CHEN Zhihui1，2

（1.College of Science， Jiangxi University of Science and Technology， Ganzhou? 341000， China;

2.College of Information Science and Engineering， Jiaxing University， Jiaxing? 314001， China）

Abstract： To solve the problem of high sparsity and poor recommendation performance of traditional collaborative filtering algorithms， a collaborative filtering recommendation algorithm based on K-means clustering and weighted Slope One filling is proposed. Firstly， K clusters of users are clustered based on user characteristics， secondly， the rating matrix within each cluster is predicted and populated by the weighted Slope One algorithm， and finally， the rating matrix of each category is merged and a hybrid algorithm combining Baseline algorithm and item-based collaborative filtering algorithm is designed to predict user ratings. The new algorithm was compared with other algorithms on the MovieLens dataset， and the experimental results showed that the algorithm can effectively alleviate data sparsity and improve prediction accuracy.

Keywords： collaborative filtering; user clustering; rating prediction; personalized recommendation

0? 引? 言

在互聯網時代，信息量呈指數增長，用戶難以從龐大的網絡信息中獲取有效的信息。推薦系統作為用戶獲取有效信息的主要手段之一，其核心思想是根據用戶的屬性、興趣、偏好等特征，識別用戶需求，為用戶生成個性化推薦。目前，推薦系統已被應用在Netflix、Amazon、阿里巴巴、騰訊等電子商務巨頭向消費者提供有價值的商品推薦，如食品、醫療保健、書籍、電子服務、音樂、電影等。

推薦算法是推薦系統的核心技術之一。其中，以用戶為單位和以物品為單位的協同過濾，是業界公認的二種經典推薦算法[1]。在以用戶為單位進行協同過濾時，基于用戶鄰居對目標用戶產生推薦[2]。通過比較用戶對同一件物品的評價，計算用戶間的相似度，根據相似度矩陣得到與目標用戶相似的用戶集合，通過用戶集合的偏好為目標用戶推薦物品。以物品為單位進行協同過濾時，依賴于物品的相似性而不是用戶鄰居產生預測，與行為偏好容易變化的用戶相比，物品相似度更加穩定[3]。二種算法的原理不同，但是均需對用戶或者物品之間進行相似性計算，均受到數據稀疏性限制，互聯網的迅速擴張，使得用戶與物品數量同步激增，數據集稀疏度急劇增加，直接造成推薦精度降低。

基于上述原因，提出一種協同聚類推薦算法：首先通過K-means聚類算法最小化同一族群中用戶的差異，然后將各個聚類中的評分數據生成稀疏用戶-項目評分矩陣并通過加權Slope One算法預測矩陣中未評分的部分，將其填充成非稀疏用戶-項目評分矩陣，最終合并各聚類中的數據作為訓練集，通過基于物品的協同過濾算法生成預測評分與推薦物品。

本文的主要貢獻包括2個方面：

1）引入加權Slope One算法以集群中用戶歷史評分和物品間評分差值為依據，預測填充稀疏評分矩陣，解決了傳統協同過濾推薦中數據稀疏的問題。

2）將用戶聚類算法與加權Slope One算法結合，彌補了加權Slope One算法特征提取不完整的不足。

1? 相關工作

協同過濾算法按照推薦方式不同可以分為基于模型的協同過濾算法和基于內存的協同過濾算法[4]。基于模型的協同過濾通過數據挖掘與機器學習技術訓練模型，預測實際數據。通常基于聚類或分類技術從訓練集中發現模型，常用的模型包括深度學習模型[5]、潛在語義分析模型[6]、貝葉斯模型[7]、矩陣分解模型[8]等。矩陣分解模型通過學習高維用戶物品評分矩陣，獲取用戶和物品的低維向量表達，通過該向量表達對推薦任務進行建模，預測用戶評分。文獻[9]提出了一種基于神經網絡的變分矩陣分解協同過濾方法，將神經網絡作為一個完整的貝葉斯概率框架，結合了深度學習和概率矩陣分解的優點，捕捉更細微的潛在表征和潛在表征的不確定性，從而緩解數據稀疏問題，有效地學習潛在表示。文獻[10]中提出了一種融合語義分析特征抽取的協同過濾。利用物品屬性特征和用戶行為特征修正評分矩陣，提升物品排序準確性。

基于內存的協同過濾算法通過計算物品或用戶之間的相似度實現，預測目標用戶對未打分物品所給予的打分情況產生推薦。然而，隨著大數據的出現，基于內存的協同過濾出現數據稀疏、冷啟動、可擴展性等問題[11]，限制了推薦算法的性能。為了緩解數據稀疏性對推薦性能的影響，聚類算法被應用到推薦系統中。文獻[12]提出了一種基于聚類的局部相似性（CBLS）模型，使用聚類分析方法來尋找相似對象集群。然后為每個聚類創建一個以用戶為中心的相似性模型，每個相似性模型都依賴于對分配給群集中包含的物品的評分敏感的分級規范化和資源分配技術。該方法能夠利用用戶之間的多個關聯結構，提高了預測精度的同時減輕了在對流行對象進行評分預測時引入低質量鄰居的影響。文獻[13]提出一種基于特征的協同聚類模型，通過評分信息提取用戶及物品的特征，利用提取的特征聚類以提高聚類精度最后在每個聚類中采用協同過濾算法生成推薦。文獻[14]提出一種基于生物啟發聚類集成的推薦算法，首先利用生物啟發算法對給定數據集的用戶聚類，通過統計集成模型產生最終的聚類。然后對目標用戶進行鄰域搜索，將該用戶納入高度匹配的聚類中并基于活動目標用戶在集群中的當前鄰居估計其評分，為目標用戶生成TOP-N推薦列表。文獻[15]提出了一種新的基于改進模糊自適應共振理論（ART）和相似性度量的雙聚類方法。首先采用所提出的雙聚類方法來獲得局部相似性和局部預測，雙聚類由用于聚類項目維度的標準模糊ART和用于聚類用戶維度的改進模糊ART兩個模糊ART神經網絡組成；然后采用基于項目的協同過濾生成全局預測，最后將兩個預測進行融合得到最終預測。

2? 基于聚類填充的協同過濾模型

提出的基于K-means和加權Slope One算法的協同聚類推薦算法框架如圖1所示。

1）通過聚類算法縮小個聚類中用戶的差異；

2）利用加權Slope One算法預測評分矩陣中未評分的部分并填充評分矩陣，將填充完的數據合并成新的非稀疏評分矩陣作為訓練集；

3）在訓練集上計算得到物品相似度，采用結合Baseline的基于物品的協同過濾推薦算法生成預測評分。

2.1? 相似度計算方法

通過圖1可以看到所提出模型需要計算物品間相似度。推薦系統中，常用的相似度計算方法是余弦相似度、修正余弦相似度和皮爾遜相關系數，當對物品i和物品j共同打分過的用戶集合Uij為空集時，這三種相似度都無法計算；同時，當對物品i和物品j共同打分過的用戶很少時甚至只有一個時，僅僅采用這些少量的數據計算物品之間的相似度，結果不夠準確。而對于推薦系統，數據集的高稀疏性恰恰是其一大特點。為了解決以上問題，提出一種先將用戶評分數據聚類，通過加權Slope one算法預測并填充各個評分數據子集中未打分的物品，然后將各個評分數據子集合并成新數據集，最后在新數據集上計算物品相似度的方法。

2.2? 聚類與填充數據集

2.2.1? K-means用戶聚類

將用戶和物品聚類數據挖掘算法與協同過濾算法結合可以有效減輕數據稀疏的影響和提高推薦性能[16]，采用K-means聚類算法進行用戶聚類，其具體步驟如下：

算法1基于K-means的用戶聚類算法

輸入：聚類數k，包含n個用戶的集合，及各個用戶對物品的評分

輸出：k個聚類

1）設n個用戶的集合為U = {u1， u2，…， un}。

2）從n個用戶的集合中任意選擇一個對象作為初始聚類中心cl1，記為CL = {cl1， cl2，…， clk}。

3）將k個聚類c1， c2，…， ck初始化為空。

4）for each ui ∈ U

for each clj ∈ CL

計算ui和clj的距離D（ui， clj）

end for

D（ui， clm） = min{D（ui， cl1）， D（ui， cl2），…， D（ui， clk）}

ci = ci ∪ ui

end for

for each cluster ci ∈ CL

for each user uj ∈ U

計算聚類ci中所有用戶的平均評分，生成新的聚類中心cli，repeat 4）

end for

end for

5）until聚類c1， c2，…， ck不再發生變化，算法停止。

其中，步驟4）的距離計算采用歐式距離。

定義1歐式距離。用戶u和用戶v之間的歐式距離D（u， v）定義為：

（1）

式中，ui，vi分別為用戶u和用戶v對物品i的評分，D（u， v）越小代表用戶u和用戶v越相似[1]。

2.2.2? 加權Slope One算法填充數據集

Slope One算法的核心思想是通過物品間評分差值和用戶歷史評分預測用戶打分。Slope One算法的優點是思想簡單且易于實現，時間和空間復雜度低，缺點是沒有考慮到用戶和物品間的相似性，于是通過將其與K-means聚類算法相結合，通過聚類確保在同一個集群中的用戶具有較高的相似性，然后在各聚類中使用Slope One算法。

Slope One算法其本質可以近似用f （x） = x + b這個函數式來表示，其中f （x）為用戶u對物品i的打分預測，x為目標用戶u除目標物品i以外的所有物品集合I的打分，b為物品集合I中各物品與目標物品i的平均得分偏差值為di， j，如式（2）所示。

（2）

式中，Ui， j為對物品i和物品j均有打分的用戶集合，rv， i和rv， j分別為用戶v對物品i和物品j的打分，N（X）為集合X中元素的數量。通過公式di， j + ru， j，可計算出用戶u對目標物品i的預測評分，從而得到預測評分計算公式為：

（3）

式中，I為用戶u除物品i評分過的所有物品集合。

Slope One算法的預測公式中，忽略了評分用戶個數的影響。加權Slope One算法在傳統Slope One算法基礎上進行了加權評分的改進，預測公式改為[17]：

（4）

在各集群使用加權Slope One算法填充數據集的具體步驟如算法2所示：

算法2加權Slope One算法填充數據集

輸入：集群用戶-項目評分矩陣Rn×k，集群用戶集合U = {u1， u2，…， un}，物品集合I = {i1， i2，…， ik}

輸出：填充后的集群用戶-項目評分矩陣Zn×k

對于任意用戶u及物品i

for u ∈ Udo

for i ∈ Ido

根據式（2）計算di， j；

根據式（4）計算pu， i；

更新用戶-項目評分矩陣Rn×k，

；

end for

end for

2.3? 結合Baseline的評分預測

預測階段，通過聚類填充預處理的用戶-項目評分矩陣，計算物品相似度，采用評分預測公式預測目標用戶打分，考慮到傳統預測評分公式由于用戶物品個體差異導致的不足，將Baseline算法融入了評分預測公式為：

（5）

式中， 為用戶u對物品i的預測打分，Nk（u）為與目標物品最相似的前k個物品集合，Sij為物品i和物品j的相似度，ruj為用戶u對物品j的打分，bui為示由Baseline算法預測的用戶u對物品i的預測評分[18]。Baseline算法的算法思想步驟如下：

1）計算所有物品的得分均值μ（全局平均評分）

2）計算每個用戶評分與平均評分的偏置值bu

3）計算每個物品的得分與平均評分的偏置值bi

4）用戶u對物品i的評分通過如下公式預測：

（6）

Baseline算法預測公式中的偏置值bu實際意義是用戶u的打分尺度，有些用戶偏向于給物品好評，他的評分會普遍高于其他用戶，偏置項bi為物品i的受歡迎程度。二者彌補了協同過濾算法評分預測公式的不足，則將Baseline算法預測值融入算法以提高準確率。

融合Baseline的評分預測的具體步驟如算法3所示：

算法3融合Baseline的評分預測算法

輸入：用戶-項目評分矩陣Gn×k，用戶集合U = {u1， u2，…， un}，物品集合I = {i1， i2，…， ik}，鄰居數K

輸出：預測評分

for u ∈ Udo

for i ∈ Ido

根據式（6）計算bui；

計算物品間相似度sim；

鄰居列表= ；

end for

end for

根據式（5）計算 。

3? 實驗與分析

3.1? 數據集

選用MovieLens-100K公開數據集，數據集的具體信息如表1所示，分別由rating、userid、itemid和timestamp字段表示。

表1? MovieLens-100k數據集相關信息

Item MovieLens-100k

Ratings 100 000

Users 943

Items 1682

Ranges {1，2，…，5}

Ratings per User 106.4

Ratings per Item 59.45

Sparsity/% 93.695 3

在評分中隨機選取80%作為訓練集，20%作為測試集測試最終算法預測準確度。

3.2? 評價指標

模型度量預測評分準確性的評價指標：平均絕對誤差（Mean Absolute Error， MAE）和均方根誤差（Root Mean Square Error， RMSE）[19]。

（7）

（8）

其中，rui為用戶u對物品i的實際評分值， 為用戶u對物品i的預測評分值，N為測試集元素數量。MAE和RMSE值越小，代表實驗預測的評分越接近真實值。

3.3? 結果及分析

3.3.1? 相似度對比實驗

物品相似度的計算方法的選取直接影響最終預測評分的準確度，算法選取了余弦相似度（cos）、調整余弦相似度（acos）和皮爾遜相關系數（cor）三種相似度計算方法在MovieLens-100K數據集上進行實驗，預測結果的MAE和RMSE值對比結果如圖2，圖3所示。

由圖2，圖3可知所提出算法使用皮爾遜相關系數的MAE和RMSE值都明顯優于其他2種相似度計算方法，因此在接下來的實驗中選擇皮爾遜相關系數。

3.3.2? 實驗結果及分析

為驗證算法有效性，將所提出結合K-means聚類填充數據集和Baseline算法的基于物品協同過濾（KIBBCF）算法分別與基于用戶（UBCF）[2]和基于物品的協同過濾（IBCF）[3]進行實驗對比，并將Baseline算法與以上二種算法結合分別得到UBBCF算法和IBBCF算法。將五種算法在MovieLens-100K數據集進行五折交叉驗證，以五次實驗的MAE和RMSE的平均值作為最終實驗結果，實驗結果如圖4，圖5所示。

實驗總結：

1）KIBBCF算法相比其他四種算法在MAE和RMSE值上均有明顯提高，證明算法可行有效，可以有效緩解數據集稀疏性對預測結果的影響以提升推薦系統準確性；

2）Baseline算法對于二種傳統的協同過濾算法準確性提升效果顯著，說明Baseline確實能夠緩解用戶打分尺度差異和物品受歡迎程度不同導致預測準確度降低的問題；

3）KIBBCF算法相比其他算法達到最佳推薦性能所需要的最近鄰居數更少，因此計算復雜度和時間復雜度也較低。原因可能是通過填充稀疏數據集，最近鄰居物品所能提供的公共評分更多，為最終預測評分所能提供的信息也就更多。

4? 結? 論

本文提出了一種基于K-means聚類和加權Slope One填充的協同過濾算法，通過用戶的所有評分計算用戶間的歐式距離聚類用戶，在各聚類中使用加權Slope One算法填充用戶物品評分矩陣并合并成新的非稀疏數據集，最后在新的數據集上計算物品相似度，并最后在基于物品的協同過濾算法預測評分公式結合Baseline算法彌補的傳統方法的不足。K-means聚類算法的引入提高了協同過濾算法的可擴展性，同時在填充數據集環節，解決了加權Slope One算法未能考慮到用戶間相似性的缺陷。K-means聚類算法與加權Slope One算法通過數據集進行實驗，結果表明，提出算法能夠有效增強預測性能，緩解推薦系統數據稀疏性較強問題。

在今后的工作中，考慮進一步優化用戶聚類環節，如融合用戶特征矩陣進行聚類，以提高所提出模型的預測準確性。

參考文獻：

[1] KHOJAMLI H，RAZMARA J. Survey of Similarity Functions on Neighborhood-Based Collaborative Filtering [J].Expert Systems with Applications，2021，185：1154821-11548228.

[2] HERLOCKER J L，KONSTAN J A，BORCHERS A，et al. An Algorithmic Framework for Performing Collaborative Filtering [J].ACM SIGIR forum，2017，51（2）：227-234.

[3] SARWAR B，KARYPIS G，KONSTAN J，et al. Item-based collaborative filtering recommendation algorithms [C]//Proceedings of the 10th international conference on World Wide Web.2001：285-295.[2023-03-18].https：//dl.acm.org/doi/10.1145/371920.372071.

[4] ZHANG Z P，DONG M X，OTA K，et al. LBCF：A Link-Based Collaborative Filtering for Overfitting Problem in Recommender System [J].IEEE Transactions on Computational Social Systems，2021，8（6）：1450-1464.

[5] FU M S，QU H，YI Z，et al. A novel deep learning-based collaborative filtering model for recommendation system [J].IEEE transactions on cybernetics，2019，49（3）：1084-1096.

[6] ALMUTAIRI F M，SIDIROPOULOS N D，KARYPIS G. Context-Aware Recommendation-Based Learning Analytics Using Tensor and Coupled Matrix Factorization [J].IEEE journal of selected topics in signal processing，2017，11（5）：729-741.

[7] WANG X C，GAO C，DING J T，et al. CMBPR： category-aided multi-channel bayesian personalized ranking for short video recommendation [J].IEEE Access，2019，7：48209-48223.

[8] GUO R X，ZHANG F，WANG L Z，et al. BaPa：A Novel Approach of Improving Load Balance in Parallel Matrix Factorization for Recommender Systems [J].IEEE Transactions on Computers，2020，70（5）：789-802.

[9] XIAO T，SHEN H. Neural variational matrix factorization for collaborative filtering in recommendation systems [J].Applied Intelligence，2019（10）：3558-3569.

[10] 陳嘉穎，于炯，楊興耀.一種融合語義分析特征提取的推薦算法 [J].計算機研究與發展，2020，57（3）：562-575.

[11] KOOHI H，KIANI K. A new method to find neighbor users that improves the performance of collaborative filtering [J].Expert Systems with Applications，2017，83：30-39.

[12] ROSA R E V D S，GUIMAR?ES F A S，MENDON?A R D S，et al. Improving Prediction Accuracy in Neighborhood-Based Collaborative Filtering by Using Local Similarity [J].IEEE Access，2020，8：142795-142809.

[13] 張飛，張立波，羅鐵堅，等.一種基于特征的協同聚類模型 [J].計算機研究與發展，2018，55（7）：1508-1524.

[14] LOGESH R，SUBRAMANIYASWAMY V，MALATHI D，et al. Enhancing recommendation stability of collaborative filtering recommender system through bio-inspired clustering ensemble method [J].Neural Computing and Applications，2020，32（7）：2141-2164.

[15] SUN J J，ZHANG Y. Recommendation System with Biclustering [J].Big Data Mining and Analytics，2022（4）：282-293.

[16] WANG Z H，CHEN J R，ROSAS F E，et al. A hyper graph-based framework for personalized recommendations via user preference and dynamics clustering [J].Expert Systems with Applications，2022，204：1175521-11755214.

[17] YAO D H，DENG X W，QING X Y. A Course Teacher Recommendation Method Based on an Improved Weighted Bipartite Graph and Slope One [J].IEEE Access，2022，10：129763-129780.

[18] FENG Q，XIAO G Y，LIANG Y. Proximal Policy Optimization for Explainable Recommended Systems [C]//2022 4th International Conference on Data-driven Optimization of Complex Systems （DOCS）.Chengdu：IEEE，2022：1-6.

[19] 張凱涵，梁吉業，趙興旺，等.一種基于社區專家信息的協同過濾推薦算法 [J].計算機研究與發展，2018，55（5）：968-976.

作者簡介：陳嘉超（1999—），男，漢族，安徽合肥人，碩士研究生在讀，主要研究方向：人工智能與推薦系統；盧敏（1964—），男，漢族，江西于都人，教授，博士，主要研究方向：推薦系統與機器學習等；丁偉健（1993—），男，漢族，安徽宿州人，碩士研究生在讀，主要研究方向：人工智能與推薦系統；陳志輝（1999—），男，漢族，江西撫州人，碩士研究生在讀，主要研究方向：數據挖掘與推薦系統。