融合FCM和TFNs的協(xié)同過濾推薦算法

徐新衛(wèi)，陶 飛，鄧佳佳，周 俊

(1.安徽工業(yè)大學(xué) 管理科學(xué)與工程學(xué)院，安徽 馬鞍山 243032;2.廣東科技學(xué)院，廣東 東莞 523073)

0 引 言

伴隨信息技術(shù)和互聯(lián)網(wǎng)的高速發(fā)展，數(shù)據(jù)量表現(xiàn)出幾何級(jí)穩(wěn)定增長(zhǎng)。而推薦系統(tǒng)(Recommendation Systems，RSs)是有效的信息處理手段之一。為了解決信息過載的問題，RSs主要采用信息過濾的技術(shù)，通過用戶的歷史行為信息提取出用戶偏好，減少用戶查找信息的時(shí)間，并將用戶與商品相互聯(lián)。協(xié)同過濾(Collaborative Filtering，CF)是推薦最成功的技術(shù)之一，根據(jù)相似度指數(shù)發(fā)現(xiàn)與當(dāng)前用戶相似的用戶，然后利用這些相似用戶對(duì)產(chǎn)品進(jìn)行評(píng)估。基于用戶的CF算法(User-Based CF，UBCF)和基于項(xiàng)目的CF算法(Item-Based CF，IBCF)是協(xié)同過濾推薦算法(Recommendation Algorithms，RAs)的兩種基本形式。算法主要是研究用戶行為定位相似的用戶。IBCF是利用項(xiàng)目間的相似性來提出與附近用戶感興趣的事物相似的東西。CF算法可以幫助客戶找到合適的物品或服務(wù)，但它們被諸如冷啟動(dòng)、數(shù)據(jù)稀少和可擴(kuò)展性等問題所困擾。

近年來，學(xué)者們利用聚類方法[1]來解決CF算法中數(shù)據(jù)系數(shù)以及推薦精度低等問題。賈俊杰等[2]利用了信任的傳遞性，先計(jì)算出顯隱式信任獲得綜合直接信任值，然后再獲得Jaccard全局信任值，最后將綜合直接信任值和Jaccard全局信任值結(jié)合得到綜合信任值，將其融入FCM中實(shí)現(xiàn)推薦；Tran C等[3]提出了一種新的基于聚類的CF方法，僅僅使用激勵(lì)/懲罰用戶模型(Incentivized/Penalized User，IPU)，只由用戶給出評(píng)級(jí)來對(duì)用戶進(jìn)行聚類，無需進(jìn)一步的事先信息從而進(jìn)行推薦；張建華等[4]針對(duì)知識(shí)RAs的語義缺失和精準(zhǔn)性低的問題，提出一種基于改進(jìn)的LDA-FCM的知識(shí)RAs，利用LDA模型挖掘用戶知識(shí)模型并用FCM聚類用戶，再結(jié)合JS散度代替歐氏距離以提高推薦精度；王永貴等[5]提出一種優(yōu)化聚類的CF算法，根據(jù)評(píng)分差異對(duì)原始評(píng)分矩陣進(jìn)行預(yù)處理得到用戶項(xiàng)目評(píng)分矩陣及項(xiàng)目類型矩陣，構(gòu)建用戶類型偏好矩陣，緩解了數(shù)據(jù)的稀疏性；趙學(xué)健等[6]利用遺傳算法(Genetic Algorithm，GA)改進(jìn)FCM，同時(shí)考慮用戶特征偏好矩陣和用戶項(xiàng)目評(píng)分矩陣計(jì)算相似度實(shí)現(xiàn)推薦；鄭鑫等[7]采用FCM篩選最近鄰居，結(jié)合奇異值分將用戶評(píng)分分解為不同特征以實(shí)現(xiàn)推薦。

通過上述分析，可以發(fā)現(xiàn)利用聚類方法對(duì)用戶進(jìn)行聚類時(shí)，一方面容易受到異常值和噪聲的干擾。另一方面，F(xiàn)CM算法的結(jié)果并不是很穩(wěn)定，因?yàn)樗钠鹗假|(zhì)心是隨意創(chuàng)建的。需要注意的是，基于協(xié)同過濾推薦算法(Collaborative Filtering Recommendation Algorithms，CFRAs)進(jìn)行相似性度量是至關(guān)重要的。UBCF和IBCF算法中最常用的相似度量是余弦(Cosine)、余弦修正(Adjusted Cosine，AC)和皮爾遜相關(guān)系數(shù)(Pearson Correlation Coefficient，PCC)。但在用戶行為復(fù)雜的情況下，PCC、AC和余弦作為相似度度量的基于CFRAs的性能上無法得到保證。因此，學(xué)者們?cè)谠O(shè)計(jì)更全面的相似度方面做出了巨大的努力，將用戶評(píng)分的信息量及模糊性考慮其中以計(jì)算相似度，提升推薦精度。

例如，王森等[8]利用梯形模糊數(shù)(Trapezoidal Fuzzy Numbers，TFNs)表示評(píng)分與滿意度的映射關(guān)系，融合基于模糊評(píng)分的項(xiàng)目相似性和基于標(biāo)簽隸屬度的相似性形成項(xiàng)目相似度，從而進(jìn)行推薦；Zhang等[9]為確定用戶的相似度，根據(jù)三角模糊數(shù)的相似度，將三角形面積和中點(diǎn)用來表達(dá)用戶對(duì)項(xiàng)目的整體評(píng)價(jià)，從而使相似度計(jì)算的準(zhǔn)確性得到提高；Yager[10]針對(duì)用戶分?jǐn)?shù)潛在的信息，采用模糊理論中的模糊子集并結(jié)合PCC算出評(píng)分的相似度，其后對(duì)兩部分加權(quán)獲得最終相似度；吳毅濤[11]考慮多數(shù)推薦系統(tǒng)使用離散評(píng)分，用戶只能在評(píng)分級(jí)別{1,2,3,4,5}中選擇相應(yīng)的分?jǐn)?shù)，提出了梯形模糊評(píng)分模型，將評(píng)分模糊化并考慮評(píng)分信息量和模糊性，用梯形模糊數(shù)來計(jì)算相似度以提高推薦質(zhì)量，并證明模糊相似度(Fuzzy Similarity，F(xiàn)S)是余弦在模糊域上的擴(kuò)展。

因此，該文提出了一種融合FCM和TFNs的協(xié)同過濾推薦算法(Genetic Algorithm Improved Fuzzy C-means And Trapezoidal Fuzzy Number Collaborative Filtering Algorithm，GAFCM-TFNCF)。首先，使FCM與GA相結(jié)合，然后，對(duì)用戶進(jìn)行聚類，最后，根據(jù)FS將離散分?jǐn)?shù)轉(zhuǎn)換成梯形模糊數(shù)用來計(jì)算用戶相似度，從而利用模糊分?jǐn)?shù)預(yù)測(cè)評(píng)分。此方法的優(yōu)點(diǎn)如下：

(1)將GA的搜索結(jié)果作為FCM的初始聚類中心，可以有效避免FCM在迭代過程中陷入局部最小值點(diǎn)；

(2)現(xiàn)有RSs下的評(píng)分只能片面地表達(dá)用戶的偏好，該文通過引入TFNs將評(píng)分模糊化，從而計(jì)算用戶的相似度，這樣更能合理表達(dá)用戶的觀點(diǎn)。

1 相關(guān)工作

1.1 FCM算法

在實(shí)際應(yīng)用中，基于FCM方法是使用最廣泛的模糊聚類技術(shù)。它允許數(shù)據(jù)項(xiàng)屬于隸屬度從0到1不等的集合，通過優(yōu)化目標(biāo)函數(shù)來定義樣本點(diǎn)的類別，以獲得每個(gè)樣本點(diǎn)對(duì)所有類中心的隸屬度，從而達(dá)到樣本數(shù)據(jù)自動(dòng)分類的目的?；救绻?1)所示：

(1)

其中，m是給定數(shù)據(jù)集中的數(shù)據(jù)向量總數(shù)；c為聚類數(shù)目；V={v1,v2,…,vi,…,vc}表示聚類中心；μik(μik∈[0,1])是用戶uk對(duì)聚類中心vi(i=1,2,…,c)的隸屬度；Hm×c=(μik)是一個(gè)模糊分區(qū)矩陣，也為聚類的結(jié)果；M是JFCM(H,V)中的一個(gè)參數(shù)，一般M∈[1.25,2.5]，通常稱為模糊器，用來控制成員等級(jí)影響的實(shí)數(shù)。

聚類中心vi和隸屬度矩陣H根據(jù)以下的公式來計(jì)算，使得JFCM(H,V)最小化。

dik=‖uk-vi‖2

(2)

(3)

(4)

(5)

式(2)中，dik(uk,vi)是數(shù)據(jù)對(duì)象uk和簇vi之間的距離值，歐幾里得度量來衡量距離值是常用方法之一。FCM算法旨在將方程中的準(zhǔn)則函數(shù)最小化，距離值dik是通過迭代更新式(3)中的聚類中心vi和式(4)中的隸屬度μik，迭代更新重復(fù)過程，直到達(dá)到條件即終止。

FCM算法流程可以如下表示[6]：

(1)輸入聚類數(shù)目c，模糊器M和距離函數(shù)‖·‖；

(2)初始化聚類中心vi(i=1,2,…,c)；

(3)根據(jù)公式(2)、(3)和(5)，計(jì)算uki(k=1,2,…,m;i=1,2,…,c)；

(7)停止。

1.2 模糊集和梯形模糊數(shù)的運(yùn)算

(6)

(7)

(8)

(9)

(10)

(11)

該文將利用上述公式改進(jìn)目前CFRAs中模糊相似度的計(jì)算，從而進(jìn)行評(píng)分預(yù)測(cè)。

2 基于改進(jìn)FCM和TFNs的協(xié)同過濾算法

針對(duì)模糊相似度的計(jì)算，目前CF算法僅采用常規(guī)距離和重心距離，存在一定的誤差。因此，該文考慮Ahmad S[13]提出的一種新的梯形相似性度量，它結(jié)合了幾何距離(Geometric Distance，GD)、重心距離(Center Of Gravity，COG)、Dice相似性系數(shù)(Dice Similarity Coefficient，DSC)和Hausdorff距離(Hausdorff Distance，HD)。CF算法常用的是PCC、Cosine等計(jì)算相似度，但未能考慮評(píng)分信息量，并不適用于模糊評(píng)分的相似度計(jì)算，所以本節(jié)采用梯形相似度結(jié)合評(píng)分信息來進(jìn)行推薦。

2.1 梯形模糊相似度

(12)

(13)

(14)

(15)

根據(jù)GD和COG可以看出兩個(gè)用戶對(duì)于一個(gè)項(xiàng)目的相似度，再通過加權(quán)所有項(xiàng)目相似度獲得用戶模糊相似度，公式如下：

(16)

由用戶u和v共同評(píng)價(jià)的項(xiàng)目集表示為U，數(shù)量表示為n(U)，項(xiàng)目i被用戶u評(píng)價(jià)的分?jǐn)?shù)為Ru,i，而用戶u評(píng)價(jià)的項(xiàng)目數(shù)是n。

2.2 GAFCM-TFNCF算法流程

因?yàn)檫z傳算法[16-17]在生成優(yōu)化和搜索問題方面有著較不錯(cuò)的解決方案，目前許多學(xué)者已將GA用于處理聚類問題或者將多種不同的方式用來集成GA和聚類方法[18-20]，且使用GA優(yōu)化初始聚類中心和聚類方法的參數(shù)[21-22]。所以在用FCM算法進(jìn)行聚類之前，先利用遺傳算法對(duì)其進(jìn)行改進(jìn)。所提出的模型步驟如下[23]：

(1)對(duì)原始數(shù)據(jù)集進(jìn)行預(yù)處理，搭建出用戶偏好矩陣，并將其進(jìn)行歸一化處理；

(2)將GAFCM算法的參數(shù)M(種群規(guī)模)、m(隸屬度因子)、c(聚類的簇?cái)?shù))、pc(交叉率)、pm(變異率)、tmax(最大迭代次數(shù))、ε(收斂的精度)進(jìn)行初始化；

(3)將從數(shù)據(jù)集中隨機(jī)選擇初始染色體；

(4)更新最佳染色體；

(5)選擇t染色體，利用輪盤賭選擇放入選擇池中，其輪盤賭是GA的一種選擇機(jī)制，公式如下所示：

(17)

其中，Pi為染色體i(1≤i≤t)的選擇概率，fi和fj分別是i和j的適應(yīng)值。

(6)隨機(jī)將兩條染色體作為雙親并檢查交叉概率，以用來核實(shí)是否進(jìn)行交叉步驟，在交叉過程中生成新染色體的概率定義如下：

(18)

(19)

(7)核實(shí)突變pm的概率，以確定是否繼續(xù)突變步驟，實(shí)施編碼遺傳突變概率定義如下：

(20)

ag=2-u·k

(21)

其中，sg和u為隨機(jī)數(shù)，且sg∈{-1,1}和u∈[0,1]，rg為變異的范圍，rg∈[10-6,0.1]；k∈{4,5,…,20}表示變異的精度。

(8)若滿足終止條件則結(jié)束，否則轉(zhuǎn)到步驟(3)；

(9)將GA的輸出結(jié)果作為FCM的初始聚類中心；

(10)利用(2)～(5)進(jìn)行計(jì)算獲得聚類中心和隸屬度矩陣，從而實(shí)現(xiàn)用戶聚類劃分。

在經(jīng)過上述操作后，利用梯形模糊評(píng)分來計(jì)算相似度并進(jìn)行推薦。

(1)相似度計(jì)算流程如下：

輸入：用戶項(xiàng)目評(píng)分矩陣R，鄰居數(shù)量k。

①根據(jù)(12)計(jì)算目標(biāo)用戶u和其他用戶v在一個(gè)任務(wù)的共同評(píng)價(jià)方面的相似度S(Ru,i,Rv,i)；

②利用式(16)計(jì)算模糊相似度sim(u,v)。

(2)產(chǎn)生推薦集。

①作為鄰居集，選擇相似度最高的k個(gè)用戶；

②如式(22)所示，采用平均加權(quán)方法對(duì)預(yù)測(cè)評(píng)分進(jìn)行加權(quán)。

(22)

輸出：目標(biāo)用戶u對(duì)未知任務(wù)的預(yù)測(cè)評(píng)分，獲得推薦結(jié)果。

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

3.1 實(shí)驗(yàn)環(huán)境及實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)的操作系統(tǒng)為Windows10，CPU為Intel(R) Core(TM) i5-1035G1@ 1.00 GHz 1.19 GHz，實(shí)驗(yàn)內(nèi)存為16 GB，主要實(shí)驗(yàn)平臺(tái)是Python 3.7。為驗(yàn)證GAFCM-TFNCF算法的性能，利用常見的數(shù)據(jù)集Movielens進(jìn)行實(shí)驗(yàn)，其數(shù)據(jù)集的描述如表1所示。

表1 實(shí)驗(yàn)數(shù)據(jù)集

3.2 評(píng)價(jià)指標(biāo)實(shí)驗(yàn)數(shù)據(jù)設(shè)置

將平均絕對(duì)誤差(Mean Absolute Error，MAE)、均方根誤差(Root Mean Squared Error，RMSE)作為實(shí)驗(yàn)的度量標(biāo)準(zhǔn)；MAE和RMSE的值越小，預(yù)測(cè)的估計(jì)值就越接近真實(shí)值，推薦的準(zhǔn)確性就越好。具體定義如公式(23)、(24)所示。

(23)

(24)

其中，用戶u對(duì)項(xiàng)目i的預(yù)測(cè)評(píng)分值為Pu,i；用戶u對(duì)項(xiàng)目i的真實(shí)評(píng)分值是Ru,i；T為測(cè)試集；|T|為測(cè)試集的數(shù)量。

相關(guān)參數(shù)設(shè)置如下：種群規(guī)模M=50，迭代數(shù)t=50，變異概率pm=0.05，交叉概率pc=0.85，收斂的精度ε=0.000 1，隸屬度因子m=2，聚類的簇?cái)?shù)c=8。

3.3 算法對(duì)比

為了驗(yàn)證算法GAFCM-TFNCF的有效性，對(duì)比算法有UBCF、基于用戶偏好和項(xiàng)目屬性的協(xié)同過濾推薦算法UPPPCF[24]、傳統(tǒng)基于FCM的協(xié)同過濾算法FCMCF[7]、基于項(xiàng)目模糊相似度的協(xié)同過濾推薦算法IFSCF[8]。

3.4 實(shí)驗(yàn)結(jié)果

將80%的數(shù)據(jù)集作為訓(xùn)練集，剩下的20%作為測(cè)試集。對(duì)比算法的參數(shù)均根據(jù)自身文獻(xiàn)設(shè)置為最優(yōu)并記錄下結(jié)果以進(jìn)行對(duì)比。使用MAE、RMSE來衡量預(yù)測(cè)評(píng)分的準(zhǔn)確性。為減小由于分割數(shù)據(jù)集所帶來的誤差，將10次實(shí)驗(yàn)的平均值作為結(jié)果。以鄰居數(shù)量當(dāng)作變量，間隔為5，比較文中算法(GAFCM-TFNCF)與其它四種算法的預(yù)測(cè)精度，實(shí)驗(yàn)結(jié)果如圖1所示。

圖1 五種算法在數(shù)據(jù)集100 K和1 M上的MAE和RMSE對(duì)比

由圖1可以看出，GAFCM-TFNCF算法在所有的對(duì)比算法中表現(xiàn)最佳。GAFCM-TFNCF算法相比其余四種算法MAE值要小很多。這表明融合GA和FCM進(jìn)行聚類，極大避免了在搜索過程中陷入極小值點(diǎn)，然后再將用戶評(píng)分模糊化能夠極大地提高推薦的精準(zhǔn)度。對(duì)比UPPPCF算法，當(dāng)鄰居數(shù)量不斷變大后，因?yàn)橛脩魧?duì)相同項(xiàng)目的評(píng)分變得很少，但GAFCM-TFNCF算法的MAE曲線相較于UPPPCF算法更平穩(wěn)，這表明文中算法在性能表現(xiàn)上更加穩(wěn)定，不易受到數(shù)據(jù)集大小的影響，而UPPPCF算法下降幅度較大，說明容易受到數(shù)據(jù)集大小的影響。

為了比較數(shù)據(jù)稀疏性對(duì)算法精度的影響，實(shí)驗(yàn)在Movielens-100 K數(shù)據(jù)集中進(jìn)行，核定用戶數(shù)和項(xiàng)目數(shù)不變的前提下，將評(píng)分?jǐn)?shù)逐步進(jìn)行減少，比較五種算法的MAE值，實(shí)驗(yàn)結(jié)果如圖2所示。

圖2 不同數(shù)據(jù)稀疏度下的五種算法對(duì)比

通過圖2發(fā)現(xiàn)，隨著稀疏度的不斷增加，可使用的數(shù)據(jù)不斷減少，五種算法的MAE值都不斷增長(zhǎng)，稀疏度在大于95%后增長(zhǎng)速度變快。GAFCM-TFNCF算法增長(zhǎng)幅度較其余四種算法小，推薦精度更高，表明該算法可以在數(shù)據(jù)稀疏中完成推薦，其中UBCF算法預(yù)測(cè)最差，這表明該算法對(duì)于稀疏度高的數(shù)據(jù)集并不適用。

4 結(jié)束語

針對(duì)推薦系統(tǒng)存在數(shù)據(jù)稀疏性、未考慮用戶評(píng)分信息量等問題，提出一種基于改進(jìn)FCM的用戶模糊相似度的協(xié)同過濾推薦算法。對(duì)于傳統(tǒng)FCM聚類對(duì)異常值和噪聲很敏感的問題，采用GA融合FCM，避免FCM在開始搜索時(shí)陷入局部最小值點(diǎn)。同時(shí)兼顧梯形模糊評(píng)分模型，將離散評(píng)分模糊化用來計(jì)算相似度，從而更合理地表達(dá)了用戶對(duì)項(xiàng)目的偏好。在推薦算法中采用常見數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)對(duì)比，表明算法具有更優(yōu)的推薦精準(zhǔn)度。在未來工作中，考慮在保證推薦準(zhǔn)確度的同時(shí)，如何同時(shí)保護(hù)用戶的隱私，這是今后的一個(gè)研究方向。