基于模糊聚類和Slope One填充的推薦算法

李磊

摘要：傳統(tǒng)的推薦算法受限于其數(shù)據(jù)密度低，矩陣規(guī)模大進(jìn)而導(dǎo)致的計(jì)算復(fù)雜、實(shí)時(shí)性差且推薦精度低。針對(duì)這一問題，設(shè)計(jì)了一種結(jié)合模糊聚類和Slope One填充的推薦方法。算法根據(jù)用戶的特征進(jìn)行模糊聚類，利用加權(quán)Slope One算法填充c個(gè)規(guī)模較小的用戶-項(xiàng)目矩陣中的缺失數(shù)據(jù)，并通過改進(jìn)的相似度計(jì)算方法計(jì)算出用戶間的相似度得出最近鄰結(jié)果集。仿真對(duì)比實(shí)驗(yàn)表明，設(shè)計(jì)的算法對(duì)比傳統(tǒng)的推薦算法在精度上有著很大提升，同時(shí)能緩解數(shù)據(jù)稀疏性，提升推薦質(zhì)量。

關(guān)鍵詞：協(xié)同過濾;模糊聚類;Slope One;相似度

中圖分類號(hào)：TP391? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2022）10-0068-03

1 引言

由于信息網(wǎng)絡(luò)的高速增長，世界各地的數(shù)據(jù)量也正瘋狂增加，據(jù)有關(guān)組織報(bào)告稱，估計(jì)到2025年，世界各地的數(shù)據(jù)量將會(huì)達(dá)到驚人的163ZB，是2016年16.1ZB的十倍[1]。面對(duì)如此龐大的數(shù)據(jù)量，我們已然陷入了“信息過載”的時(shí)代[2]。若是能夠使用一種方法能夠挖掘出用戶的歷史行為記錄并分析計(jì)算出用戶潛在的興趣，主動(dòng)地推薦感興趣的項(xiàng)目給用戶，則大概率可避免用戶大海撈針?biāo)频孬@取數(shù)據(jù)。推薦系統(tǒng)應(yīng)運(yùn)而生。

推薦系統(tǒng)的質(zhì)量好壞完全依賴于為該系統(tǒng)設(shè)計(jì)的推薦算法，作為最經(jīng)久不衰最為經(jīng)典的一種推薦算法——協(xié)同過濾算法，為緩解大數(shù)據(jù)環(huán)境下存在的“信息過載”問題做出了巨大的貢獻(xiàn)。通過構(gòu)建用戶-項(xiàng)目矩陣，通過分析用戶行為找出相似的用戶，然后根據(jù)相似用戶的行為做出推薦。但是可擴(kuò)展性差、數(shù)據(jù)密度低導(dǎo)致稀疏性高從始至終都是亟須解決的問題。究其原因是用戶和項(xiàng)目之間的不對(duì)稱性，導(dǎo)致大量的項(xiàng)目僅僅被極少比例的用戶所標(biāo)注[3]。

為了緩解由于數(shù)據(jù)密度低，矩陣規(guī)模龐大進(jìn)而導(dǎo)致推薦精度不高、可擴(kuò)展性差這一系列問題。論文設(shè)計(jì)了一種基于模糊聚類和Slope One填充的推薦算法。首先使用模糊c均值算法（FCM）按照用戶的特征進(jìn)行聚類，得到c個(gè)聚類中心進(jìn)而構(gòu)建c個(gè)用戶項(xiàng)目矩陣，然后使用加權(quán)Slope One算法計(jì)算出的結(jié)果值回填矩陣中的缺失項(xiàng)，最后和協(xié)同過濾算法相融合得出預(yù)測(cè)評(píng)分。實(shí)驗(yàn)表明，論文和設(shè)計(jì)出的算法在各項(xiàng)指標(biāo)中均優(yōu)于傳統(tǒng)的推薦算法。

2 相關(guān)研究

2.1 協(xié)同過濾算法

GlodBerg等人[4]在20世紀(jì)90年代開創(chuàng)性地提出了協(xié)同過濾算法。其基本假設(shè)是，“物理類聚，人以群分”。協(xié)同過濾技術(shù)主要包含以下三個(gè)步驟：

1） 建立用戶-項(xiàng)目矩陣。通過日志或其他方式對(duì)用戶的操作行為，包括顯示反饋或是隱式反饋進(jìn)行收集，得到用戶-項(xiàng)目評(píng)分矩陣[Rm×n]如公式（1）所示。

[Rm×n=r11…r1n???rm1…rmn]? ? ? ? ? ? ?（1）

2） 找到用戶最近鄰集合。描述兩個(gè)樣本特征的相似程度需要使用到相似性計(jì)算方法。構(gòu)建相似度矩陣隨后從中提取出與目標(biāo)樣本相似程度最高的前k個(gè)樣本作為最近鄰集合。

3） 產(chǎn)生推薦。通過近鄰結(jié)果集合加權(quán)得出預(yù)測(cè)評(píng)分結(jié)果進(jìn)而產(chǎn)生排序Top-N推薦列表給用戶進(jìn)行推薦。

2.2 Slope One算法

Slope One算法[5]其核心思想是利用一種線性回歸模型來對(duì)矩陣中存在的缺失值進(jìn)行預(yù)測(cè)。使用公式（2） 計(jì)算得出各個(gè)項(xiàng)目評(píng)分差均值[devij]，然后使用公式（3） 進(jìn)行目標(biāo)用戶對(duì)其項(xiàng)目的評(píng)分預(yù)測(cè)。

[devij=u∈N（i）?N（j）rui-rujN（i）?N（j）]? ? ? ? ? ? ? ? ? （2）

[pui=i∈N（u）|N（i）?N（j）|?ruj+deviji∈N（u）N（i）?N（j）]? ? ? ? ? ? ?（3）

[rui]代表的是項(xiàng)目i被用戶u所標(biāo)注并給出了評(píng)分， [N（i）?N（j）] 代表的是針對(duì)項(xiàng)目i和j均存在共同標(biāo)注行為的用戶集合。

2.3 Weighted Slope One算法

Slope One算法簡(jiǎn)單高效可擴(kuò)展性強(qiáng)。但是未考慮共同評(píng)分個(gè)數(shù)多的要比共同評(píng)分個(gè)數(shù)少的更加可靠，因此在進(jìn)行評(píng)分預(yù)測(cè)階段時(shí)應(yīng)當(dāng)賦予更高的權(quán)重比例[6]。加權(quán)Slope One算法如公式（4） 所示：

[preui=j∈I（u）（rui+devij）?Uijj∈I（u）Uij]? ? ? ? ? ? ? （4）

2.4 相似性計(jì)算方法

相似度計(jì)算是產(chǎn)生推薦的重要步驟之一，論文選取皮爾遜相關(guān)系數(shù)作為衡量相似與否的標(biāo)準(zhǔn)，如公式（5） 所示。

[Simu，v=i∈Iuvrui-rurvi-rvi∈Iuvrui-ru2i∈Iuvrvi-rv2]? ? ? （5）

其中，[Simu，v]的含義是兩個(gè)樣本u和v之間的相似度， [ru]和[rv]分別表示為各自對(duì)它們有過評(píng)分行為的項(xiàng)目的平均評(píng)分值。

2.5 評(píng)分生成

通過相似鄰居集合以及其評(píng)分信息聯(lián)合計(jì)算得出最終的預(yù)測(cè)評(píng)分，如公式（6） 所示：

[preui=ru+v∈N（u）rvi-rv?Simu，vv∈N（u）Simu，v]? ? ? ? ? ? ?（6）

[preui]表示的是用戶u對(duì)項(xiàng)目i計(jì)算得出的預(yù)測(cè)評(píng)分值， [N（u）]含義為對(duì)目標(biāo)用戶u所挑選出的最近鄰用戶集。

3 本文算法

3.1 用戶模糊聚類

在傳統(tǒng)的聚類算法中，每個(gè)目標(biāo)樣本都只能被劃分都一個(gè)固定的類別中去，沒有達(dá)到一種靈活的狀態(tài)。模糊聚類通過引入隸屬度這一特性提供了更有彈性更加靈活的聚類效果[7]，根據(jù)隸屬度的權(quán)重將一個(gè)目標(biāo)樣本劃分到不同的類簇中去。其中最被廣泛應(yīng)用的是模糊c-均值聚類（FCM）算法[8]。

在FCM算法中，將用戶特征屬性映射到n維向量u上，[u=r1，r2，…rn]，將數(shù)據(jù)集[X=x1，x2，…， xn]中各個(gè)樣本點(diǎn)根據(jù)自身的特征屬性按照相應(yīng)的隸屬度模糊劃分到不同的聚類簇中心，不斷迭代前后兩次的目標(biāo)函數(shù)之差直到比最初設(shè)置的最小值小或是已經(jīng)達(dá)到了最大的系統(tǒng)設(shè)置的迭代次數(shù)則終止，此時(shí)即可獲得相對(duì)最佳的聚類效果[9]。原問題可以看作求解拉格朗日條件極值問題，其目標(biāo)損失函數(shù)為公式（7） 所示，其約束條件為從各個(gè)樣本點(diǎn)出發(fā)最終到達(dá)所有的聚類中心必須滿足隸屬度權(quán)重總和為1，如公式（8） 所示。

[J（U，ci）=i=1cj=1nuixjmxj-ci]? ? ? ? ? ? ? ? ? ?（7）

[i=1cuixj=1，?j=1，2，…，n]? ? ? ? ? ? ? ? ? ?（8）

[uixj]表示的含義是對(duì)于樣本集中的某個(gè)樣本[xj]其隸屬于第i個(gè)聚類中心的程度，m為加權(quán)指數(shù)，通常取2時(shí)效果最好。[xj-ci]代表的是樣本點(diǎn)[xj]到某一個(gè)固定的聚類中心[ci]之間第二范數(shù)，也被稱作歐幾里得距離。為了使得目標(biāo)損失函數(shù)（7） 能夠取得極小值，需要構(gòu)造并求解拉格朗日函數(shù)，對(duì)[ci]與[uixj]求偏導(dǎo)數(shù)即可得到相應(yīng)的必要條件使得原目標(biāo)函數(shù)能夠取得極小值，如公式（9） 、公式（10） 所示。

[ci=j=1nuixjmxjj=1nuixjm]? ? ? ? ? ? ? ? ?（9）

[uixj=i=1kxj-cixj-ck2m-1-1]? ? ? ? ? ? ? （10）

FCM聚類算法步驟流程如下所示：

輸入：數(shù)據(jù)集樣本和聚類個(gè)數(shù)c;

輸出：使得公式（7） 取得極小值的聚類中心集合[ci]。

Step1：指定聚類個(gè)數(shù)c，初始化加權(quán)指數(shù)m;

Step2：使用隨機(jī)函數(shù)生成各個(gè)聚類中心;

Step3：求解出每個(gè)樣本點(diǎn)到達(dá)各個(gè)聚類簇中心的隸屬度，并構(gòu)建出相應(yīng)的隸屬度矩陣;

Step4：計(jì)算迭代得出各個(gè)簇的聚類中心;

Step5：不斷迭代前后兩次的目標(biāo)函數(shù)之差直到比最初設(shè)置的最小值小或是已經(jīng)達(dá)到了最大的迭代次數(shù)則終止，否則返回Step3;

Step6：得到聚類中心集合[ci]。

3.2 改進(jìn)的相似度計(jì)算方法

針對(duì)大多數(shù)行業(yè)中，如電商、影視等，越是熱門的項(xiàng)目越容易被曝光使得更多的人購買或觀看，相比之下，越是曝光度不高的項(xiàng)目越難被用戶所發(fā)現(xiàn)。這種現(xiàn)象也被稱作“馬太效應(yīng)”。所以引入項(xiàng)目流行度因子[λ]以此來降低熱門商品的所占的權(quán)重。

[λi=1-pi-pmin2pmax-pmin]? ? ? ? ? ? ? ? ? ? ?（11）

[pi]代表項(xiàng)目i的流行度，反映出的是項(xiàng)目i被標(biāo)注過的次數(shù)，[pmax]是所有項(xiàng)目中最大標(biāo)注數(shù)目，[pmin]為最小標(biāo)注數(shù)目。[λi]的取值范圍為[0，1]區(qū)間上。則改進(jìn)后的相似度計(jì)算方法為：

[Sim（u，v）=i∈Iuvrui-rurvi-rv?λii∈Iuvrui-ru2i∈Iuvrvi-rv2]? ? （12）

3.3 基于模糊聚類和Slope One填充的推薦算法

為了緩解協(xié)同過濾算法中一直以來存在的數(shù)據(jù)密度低致使在相似度計(jì)算時(shí)，未能抓到最相似的近鄰集合進(jìn)而導(dǎo)致推薦精度不高的問題，論文使用模糊聚類方法根據(jù)用戶特征進(jìn)行聚類，也即等價(jià)于對(duì)原始的用戶-項(xiàng)目矩陣進(jìn)行降維，降維后可得到c（c為聚類個(gè)數(shù)） 個(gè)小規(guī)模的矩陣。利用加權(quán)Slope One算法為每個(gè)矩陣進(jìn)行屬性填充，根據(jù)聚類的特性這就會(huì)使得在同一個(gè)聚類簇下的用戶相似程度顯然比非同一簇下的相似度要高。所以Slope One算法在填充矩陣時(shí)會(huì)盡可能避免到不相似用戶的干擾，從而可以提升推薦的精度，論文的算法流程圖如圖1。

算法執(zhí)行步驟如下：

輸入：數(shù)據(jù)集，聚類數(shù)c，最近鄰數(shù)量k;

輸出：待預(yù)測(cè)用戶對(duì)某個(gè)項(xiàng)目的最終評(píng)分預(yù)測(cè)值。

Step1：加載數(shù)據(jù)集，構(gòu)建用戶-評(píng)分矩陣D，使用公式（7） 、公式（8） 、公式（9） 、公式（10） 根據(jù)用戶屬性特征進(jìn)行聚類，形成c個(gè)聚類簇，并構(gòu)建c個(gè)規(guī)模較小的用戶-項(xiàng)目評(píng)分矩陣;

Step2：在這些小規(guī)模的用戶-項(xiàng)目矩陣當(dāng)中，使用公式（2）得出[devij];

Step3：在得到[devij]的基礎(chǔ)上通過公式（4）計(jì)算出[preui];

Step4：[preui]的值回填矩陣中空缺的數(shù)據(jù)，得到c個(gè)新的規(guī)模較小且稠密用戶-項(xiàng)目評(píng)分矩陣[Dβ];

Step5：在稠密的矩陣[Dβ]上使用公式（12） 構(gòu)建出相似度矩陣，挑選出最相近的k個(gè)用戶;

Step6：在測(cè)試集中根據(jù)上一步驟得出選出目標(biāo)用戶的最近鄰集合，借此來預(yù)測(cè)目標(biāo)用戶對(duì)某個(gè)項(xiàng)目的評(píng)分;

Step7：通過公式（6） 得到最終的評(píng)分預(yù)測(cè)結(jié)果。

4 實(shí)驗(yàn)結(jié)果分析

4.1 實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)選取由GroupLens研究小組發(fā)布的電影評(píng)分MovieLens數(shù)據(jù)集。這是個(gè)性化推薦算法中最為經(jīng)典的數(shù)據(jù)集，選取ml-100k來驗(yàn)證論文算法。數(shù)據(jù)集的評(píng)分范圍為1～5中的整數(shù)，評(píng)分的高低代表著用戶的喜歡或是不喜歡程度。

4.2 評(píng)測(cè)指標(biāo)

論文選取平均絕對(duì)誤差（Mean Absolute Error，MAE） 、均方根誤差（Root Mean Square Error，RMSE）作為實(shí)驗(yàn)的評(píng)測(cè)指標(biāo)。MAE和RMSE是在推薦系統(tǒng)中流傳最為經(jīng)典、使用頻率最高的評(píng)估指標(biāo)，得出的結(jié)果越小則可以充分反映出算法的誤差小準(zhǔn)確率高。

[MAE=i=1N|Pi-Ti|N]? ? ? ? ? （13）

[RMSE=i=1NPi-Ti2N]? ? ? ? ? ? ? ? ? ?（14）

其中[Pi]是論文提出算法得出的預(yù)測(cè)評(píng)分，[Ti]是樣本真實(shí)打分，N是在測(cè)試集中待預(yù)測(cè)樣本的總數(shù)。

4.3 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

實(shí)驗(yàn)一：驗(yàn)證聚類個(gè)數(shù)對(duì)算法實(shí)驗(yàn)結(jié)果的影響并根據(jù)實(shí)驗(yàn)結(jié)果挑選取最佳聚類個(gè)數(shù)。

設(shè)定聚類個(gè)數(shù)為[2，12]，每組的間隔為2進(jìn)行了多組實(shí)驗(yàn)，從圖中能夠明顯看出當(dāng)聚類個(gè)數(shù)達(dá)到8時(shí)，誤差最小效果最好。

實(shí)驗(yàn)二：對(duì)比傳統(tǒng)的基于用戶的協(xié)同過濾算法（UBCF） 、基于加權(quán)Slope One算法（weight-SO） 、基于k-means聚類的協(xié)同過濾算法。論文選取近鄰個(gè)數(shù)為60，聚類簇?cái)?shù)為8，實(shí)驗(yàn)結(jié)果如圖3和表1所示：

從圖表中能夠清晰地看到，論文設(shè)計(jì)的算法的誤差均小于其余算法，MAE值對(duì)比UBCF、K-meansUBCF、weight-SO算法分別降低了大約有7.58%、5.89%、3.56%，RMSE值降低了大約11.17%、8.07%、4.17%。相比于UBCF算法由于其數(shù)據(jù)密度低稀疏性高導(dǎo)致近鄰選擇不準(zhǔn)確影響了推薦結(jié)果。相比于WSO算法，由于其未考慮用戶之間的相似度，是在全局范圍內(nèi)進(jìn)行預(yù)測(cè)填充，影響了其推薦的精度。論文提出的算法不僅考慮到

了項(xiàng)目的流行性，優(yōu)化了相似度的計(jì)算方法，而且考慮到數(shù)據(jù)稀疏性帶來的負(fù)面影響，從而提升了推薦精度。

5 結(jié)束語

數(shù)據(jù)稀疏，可擴(kuò)展性一直以來都是傳統(tǒng)推薦算法面臨的問題，針對(duì)問題出發(fā)，在深入理解模糊聚類和Slope One算法理論模型的基礎(chǔ)上，設(shè)計(jì)了基于模糊聚類和Slope One填充的推薦算法，根據(jù)實(shí)驗(yàn)結(jié)果可以分析出設(shè)計(jì)的算法能夠緩解由于數(shù)據(jù)密度低，稀疏性高導(dǎo)致的推薦精度較低的問題，由于聚類都是離線完成的，在進(jìn)行評(píng)分預(yù)測(cè)時(shí)不需要遍歷整個(gè)用戶-評(píng)分矩陣，只需在屬于的簇中計(jì)算相似度即可，減少了計(jì)算時(shí)間，可擴(kuò)展性強(qiáng)。 在以后進(jìn)一步研究當(dāng)中將會(huì)考慮引入更多的輔助信息，如用戶偏好、興趣度、信任度、長短期興趣等模型并融入算法中并針對(duì)FCM算法其目標(biāo)函數(shù)是一種非凸函數(shù)導(dǎo)致其難以取得全局的最優(yōu)解 ，考慮引入智能優(yōu)化方法進(jìn)一步提升推薦質(zhì)量。

參考文獻(xiàn)：

[1] 李悅，謝珺，侯文麗，等.融合用戶偏好優(yōu)化聚類的協(xié)同過濾推薦算法[J].鄭州大學(xué)學(xué)報(bào)（理學(xué)版），2020，52（2）：29-35.

[2] 王巖，張杰，許合利.結(jié)合用戶興趣和改進(jìn)的協(xié)同過濾推薦算法[J].小型微型計(jì)算機(jī)系統(tǒng)，2020，41（8）：1665-1669.

[3] 張艷菊，陸暢.數(shù)據(jù)缺失下的IFCM-Slope One協(xié)同過濾推薦算法[J].統(tǒng)計(jì)與決策，2020，36（9）：185-188.

[4] Goldberg D，Nichols D，Oki B M，et al.Using collaborative filtering to weave an information tapestry[J].Communications of the ACM，1992，35（12）：61-70.

[5] Lemire D，Maclachlan A.Slope one predictors for online rating based collaborative filtering[C]∥Proceedings of the 2005 SIAM Data Mining Conference，2005：471-480.

[6] 馬浩，黃俊，孔麟，等.動(dòng)態(tài)k近鄰輔助多權(quán)值Slope One算法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2020，41（11）：3072-3077.

[7] Manochandar S，Punniyamoorthy M.A new user similarity measure in a new prediction model for collaborative filtering[J].Applied Intelligence，2021，51（1）：586-615.

[8] 賈俊杰，張玉超.基于用戶模糊聚類的綜合信任推薦算法[J].計(jì)算機(jī)工程，2021，47（6）：60-67.

[9] 李建軍，付佳，楊玉，等.基于混沌粒子群聚類優(yōu)化的協(xié)同過濾推薦[J].計(jì)算機(jī)工程與設(shè)計(jì)，2021，42（8）：2173-2179.

【通聯(lián)編輯：謝媛媛】