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

李磊

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

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

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

文章編號：1009-3044（2022）10-0068-03

1 引言

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

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

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

2 相關(guān)研究

2.1 協(xié)同過濾算法

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

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

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

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

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

2.2 Slope One算法

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

[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]代表的是項目i被用戶u所標(biāo)注并給出了評分， [N（i）?N（j）] 代表的是針對項目i和j均存在共同標(biāo)注行為的用戶集合。

2.3 Weighted Slope One算法

Slope One算法簡單高效可擴(kuò)展性強(qiáng)。但是未考慮共同評分個數(shù)多的要比共同評分個數(shù)少的更加可靠，因此在進(jìn)行評分預(yù)測階段時應(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 相似性計算方法

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

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

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

2.5 評分生成

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

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

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

3 本文算法

3.1 用戶模糊聚類

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

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

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

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

[uixj]表示的含義是對于樣本集中的某個樣本[xj]其隸屬于第i個聚類中心的程度，m為加權(quán)指數(shù)，通常取2時效果最好。[xj-ci]代表的是樣本點[xj]到某一個固定的聚類中心[ci]之間第二范數(shù)，也被稱作歐幾里得距離。為了使得目標(biāo)損失函數(shù)（7） 能夠取得極小值，需要構(gòu)造并求解拉格朗日函數(shù)，對[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ù)集樣本和聚類個數(shù)c;

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

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

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

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

Step4：計算迭代得出各個簇的聚類中心;

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

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

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

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

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

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

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

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

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

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

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

輸出：待預(yù)測用戶對某個項目的最終評分預(yù)測值。

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

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

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

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

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

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

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

4 實驗結(jié)果分析

4.1 實驗數(shù)據(jù)

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

4.2 評測指標(biāo)

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

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

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

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

4.3 實驗設(shè)計與結(jié)果分析

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

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

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

從圖表中能夠清晰地看到，論文設(shè)計的算法的誤差均小于其余算法，MAE值對比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ù)測填充，影響了其推薦的精度。論文提出的算法不僅考慮到

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

5 結(jié)束語

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

參考文獻(xiàn)：

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

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

[3] 張艷菊，陸暢.數(shù)據(jù)缺失下的IFCM-Slope One協(xié)同過濾推薦算法[J].統(tǒng)計與決策，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] 馬浩，黃俊，孔麟，等.動態(tài)k近鄰輔助多權(quán)值Slope One算法[J].計算機(jī)工程與設(shè)計，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ī)工程，2021，47（6）：60-67.

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

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