李磊

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

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

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

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

1 引言

由于信息網(wǎng)絡(luò)的高速增長(zhǎng)，世界各地的數(shù)據(jù)量也正瘋狂增加，據(jù)有關(guān)組織報(bào)告稱(chēng)，估計(jì)到2025年，世界各地的數(shù)據(jù)量將會(huì)達(dá)到驚人的163ZB，是2016年16.1ZB的十倍[1]。面對(duì)如此龐大的數(shù)據(jù)量，我們已然陷入了“信息過(guò)載”的時(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é)同過(guò)濾算法，為緩解大數(shù)據(jù)環(huán)境下存在的“信息過(guò)載”問(wèn)題做出了巨大的貢獻(xiàn)。通過(guò)構(gòu)建用戶-項(xiàng)目矩陣，通過(guò)分析用戶行為找出相似的用戶，然后根據(jù)相似用戶的行為做出推薦。但是可擴(kuò)展性差、數(shù)據(jù)密度低導(dǎo)致稀疏性高從始至終都是亟須解決的問(wèn)題。究其原因是用戶和項(xiàng)目之間的不對(duì)稱(chēng)性，導(dǎo)致大量的項(xiàng)目?jī)H僅被極少比例的用戶所標(biāo)注[3]。

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

2 相關(guān)研究

2.1 協(xié)同過(guò)濾算法

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

1） 建立用戶-項(xiàng)目矩陣。通過(guò)日志或其他方式對(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)生推薦。通過(guò)近鄰結(jié)果集合加權(quán)得出預(yù)測(cè)評(píng)分結(jié)果進(jìn)而產(chǎn)生排序Top-N推薦列表給用戶進(jìn)行推薦。

2.2 Slope One算法

Slope One算法[5]其核心思想是利用一種線性回歸模型來(lái)對(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ì)它們有過(guò)評(píng)分行為的項(xiàng)目的平均評(píng)分值。

2.5 評(píng)分生成

通過(guò)相似鄰居集合以及其評(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 用戶模糊聚類(lèi)

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

在FCM算法中，將用戶特征屬性映射到n維向量u上，[u=r1，r2，…rn]，將數(shù)據(jù)集[X=x1，x2，…， xn]中各個(gè)樣本點(diǎn)根據(jù)自身的特征屬性按照相應(yīng)的隸屬度模糊劃分到不同的聚類(lèi)簇中心，不斷迭代前后兩次的目標(biāo)函數(shù)之差直到比最初設(shè)置的最小值小或是已經(jīng)達(dá)到了最大的系統(tǒng)設(shè)置的迭代次數(shù)則終止，此時(shí)即可獲得相對(duì)最佳的聚類(lèi)效果[9]。原問(wèn)題可以看作求解拉格朗日條件極值問(wèn)題，其目標(biāo)損失函數(shù)為公式（7） 所示，其約束條件為從各個(gè)樣本點(diǎn)出發(fā)最終到達(dá)所有的聚類(lèi)中心必須滿足隸屬度權(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è)聚類(lèi)中心的程度，m為加權(quán)指數(shù)，通常取2時(shí)效果最好。[xj-ci]代表的是樣本點(diǎn)[xj]到某一個(gè)固定的聚類(lèi)中心[ci]之間第二范數(shù)，也被稱(chēng)作歐幾里得距離。為了使得目標(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聚類(lèi)算法步驟流程如下所示：

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

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

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

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

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

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

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

Step6：得到聚類(lèi)中心集合[ci]。

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

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

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

[pi]代表項(xiàng)目i的流行度，反映出的是項(xiàng)目i被標(biāo)注過(guò)的次數(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 基于模糊聚類(lèi)和Slope One填充的推薦算法

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

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

輸入：數(shù)據(jù)集，聚類(lèi)數(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)行聚類(lèi)，形成c個(gè)聚類(lèi)簇，并構(gòu)建c個(gè)規(guī)模較小的用戶-項(xiàng)目評(píng)分矩陣;

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

Step3：在得到[devij]的基礎(chǔ)上通過(guò)公式（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)用戶的最近鄰集合，借此來(lái)預(yù)測(cè)目標(biāo)用戶對(duì)某個(gè)項(xiàng)目的評(píng)分;

Step7：通過(guò)公式（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來(lái)驗(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)證聚類(lèi)個(gè)數(shù)對(duì)算法實(shí)驗(yàn)結(jié)果的影響并根據(jù)實(shí)驗(yàn)結(jié)果挑選取最佳聚類(lèi)個(gè)數(shù)。

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

實(shí)驗(yàn)二：對(duì)比傳統(tǒng)的基于用戶的協(xié)同過(guò)濾算法（UBCF） 、基于加權(quán)Slope One算法（weight-SO） 、基于k-means聚類(lèi)的協(xié)同過(guò)濾算法。論文選取近鄰個(gè)數(shù)為60，聚類(lèi)簇?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ù)稀疏性帶來(lái)的負(fù)面影響，從而提升了推薦精度。

5 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

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

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

[3] 張艷菊，陸暢.數(shù)據(jù)缺失下的IFCM-Slope One協(xié)同過(guò)濾推薦算法[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] 賈俊杰，張玉超.基于用戶模糊聚類(lèi)的綜合信任推薦算法[J].計(jì)算機(jī)工程，2021，47（6）：60-67.

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

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