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

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

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

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

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

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

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

1 相關(guān)工作

1.1 FCM算法

在實際應(yīng)用中，基于FCM方法是使用最廣泛的模糊聚類技術(shù)。它允許數(shù)據(jù)項屬于隸屬度從0到1不等的集合，通過優(yōu)化目標(biāo)函數(shù)來定義樣本點的類別，以獲得每個樣本點對所有類中心的隸屬度，從而達到樣本數(shù)據(jù)自動分類的目的。基本如公式(1)所示：

(1)

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

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

dik=‖uk-vi‖2

(2)

(3)

(4)

(5)

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

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

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

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

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

(7)停止。

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

(6)

(7)

(8)

(9)

(10)

(11)

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

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

針對模糊相似度的計算，目前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等計算相似度，但未能考慮評分信息量，并不適用于模糊評分的相似度計算，所以本節(jié)采用梯形相似度結(jié)合評分信息來進行推薦。

2.1 梯形模糊相似度

(12)

(13)

(14)

(15)

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

(16)

由用戶u和v共同評價的項目集表示為U，數(shù)量表示為n(U)，項目i被用戶u評價的分數(shù)為Ru,i，而用戶u評價的項目數(shù)是n。

2.2 GAFCM-TFNCF算法流程

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

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

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

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

(4)更新最佳染色體；

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

(17)

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

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

(18)

(19)

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

(20)

ag=2-u·k

(21)

其中，sg和u為隨機數(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)進行計算獲得聚類中心和隸屬度矩陣，從而實現(xiàn)用戶聚類劃分。

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

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

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

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

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

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

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

②如式(22)所示，采用平均加權(quán)方法對預(yù)測評分進行加權(quán)。

(22)

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

3 實驗結(jié)果分析

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

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

表1 實驗數(shù)據(jù)集

3.2 評價指標(biāo)實驗數(shù)據(jù)設(shè)置

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

(23)

(24)

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

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

3.3 算法對比

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

3.4 實驗結(jié)果

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

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

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

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

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

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

4 結(jié)束語

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