閻紅燦，王子茹，李偉芳，谷建濤

(1.華北理工大學理學院，河北 唐山 063210;2.河北省數(shù)據(jù)科學與應用重點實驗室,河北 唐山 063000)

1 引言

隨著推薦技術(shù)在電子商務、社交網(wǎng)絡等互聯(lián)網(wǎng)領(lǐng)域的廣泛應用，面對海量的數(shù)據(jù)信息，如何除去冗余數(shù)據(jù)，為用戶(消費者)推薦最需要或合適的服務產(chǎn)品(商品)成為研究熱點。消費者試圖通過每天接觸的網(wǎng)頁瀏覽來選購符合自己要求的商品，如何又準又快地為消費者推薦更心儀的商品，這就使推薦算法的準確性成為關(guān)鍵性問題[1 - 3]。

Goldberg等[4]首次提出推薦系統(tǒng)，找出用戶評分數(shù)據(jù)中和目標用戶有相同偏好和取向特征的用戶，將這些用戶感興趣的商品推薦給目標用戶[5]，但存在運行效率不高的問題。許多研究者提出填充稀疏數(shù)據(jù)集[6]、矩陣分解[7]和聚類[8]等方法，汪軍等[9]提出了基于云模型熟悉相似度的鄰居用戶選擇方法;袁泉等[10]提出用知識圖譜進行推薦；Wu等[11]證明基于聚類的協(xié)同過濾可以明顯提高推薦的準確性；王衛(wèi)紅等[12]用聚類和Weighted Slope One算法填充未評分項，提高推薦準確性；李嫻等[13]用異質(zhì)信息網(wǎng)絡方法進行稀疏值填充；邢長征等[14]提出填充法和改進相似度相結(jié)合的協(xié)同過濾算法；文獻[15]采用構(gòu)建矩陣變換的形式增強了推薦的準確性和多樣性；蘇慶等[16]引入改進模糊劃分的GIFP-FCM算法，將屬性特征相似的項目聚成一類，構(gòu)造索引矩陣，尋找最近鄰居構(gòu)成推薦；鄧秀勤等[17]將用戶喜好問題加入推薦的過程中，降低計算復雜度；張艷紅等[18]提出對用戶的坐標象限模糊隸屬結(jié)果，提高推薦準確性。雖然加權(quán)斜率可以緩解稀疏性，沒有考慮項目之間的隱含信息，加入模糊聚類可以提高推薦準確性，但有時人們的興趣會隨時間的遷移發(fā)生變化，如何更好地緩解以上問題成為優(yōu)化算法的關(guān)鍵。

本文針對以上問題深入研究，提出伴隨時間因子的模糊聚類協(xié)同過濾推薦算法，首先建立用戶-項目評分矩陣，采用SMOTE(Synthetic Minority Oversampling TEchnique)過采樣技術(shù)填充未評分項和時間，引入模糊聚類確定相同興趣用戶集合，在降低計算復雜度的前提下提高推薦準確性；同時引入時間因子改進傳統(tǒng)評分過程，提高計算效率的同時保證了推薦算法的實時性。

2 相關(guān)理論

2.1 協(xié)同過濾推薦算法

協(xié)同過濾推薦算法通過用戶與產(chǎn)品之間的關(guān)系，利用已有選擇歷史或用戶間的相似關(guān)系，搜索用戶潛在的感興趣的項目，完成推薦。主要包括基于模型的協(xié)同過濾推薦算法和基于記憶的協(xié)同過濾推薦算法，而基于記憶的協(xié)同過濾算法又可以分為基于物品的協(xié)同過濾推薦算法和基于用戶的協(xié)同過濾推薦算法，但是目前傳統(tǒng)的協(xié)同過濾推薦算法大部分是基于矩陣運算，維度高、復雜性大，導致推薦準確度低，推薦效果較差。本文主要研究基于用戶的協(xié)同過濾推薦算法，引入模糊聚類降低計算復雜性，提高推薦效果；同時通過SMOTE過采樣技術(shù)改善數(shù)據(jù)的稀疏性，利用不同用戶的歷史數(shù)據(jù)構(gòu)建用戶-項目矩陣，通過對物品的評分計算用戶之間的相似性，根據(jù)用戶之間的相似性預測用戶對感興趣商品的評分，優(yōu)化時間因子，進而實現(xiàn)推薦。

2.2 用戶-項目評分矩陣和時間矩陣

表1所示為協(xié)同過濾推薦算法中的用戶-項目評分矩陣R，包含一個用戶的集合U=(u1,u2,…,um)和一個項目的集合I=(i1,i2,…,in)，m個用戶針對n個項目的評分形成m×n階評分矩陣，用戶uk對項目ij的評分記為rkj。

Table 1 User-item scoring matrix R表1 用戶-項目評分矩陣R

表2所示為協(xié)同過濾推薦算法中項目的評分-時間矩陣T，包含一個用戶的集合U=(u1,u2,…,um)和一個項目的集合I=(i1,i2,…,in)，m個用戶針對n個項目的評分時間形成m×n階評分時間矩陣，用戶uk對項目ij的評分時間表示為tkj。

Table 2 User-project time matrix T表2 用戶-項目時間矩陣T

2.3 相似性度量和相似矩陣

在用戶項目評分矩陣中，為每名用戶尋找“特性相同”即有相同評分項的用戶，計算用戶間的相似性。常用的相似度評價指標有杰卡德系數(shù)、歐氏距離、余弦相似度和皮爾遜相關(guān)系數(shù)等。杰卡德系數(shù)通常用于衡量集合間的相似性；歐氏距離注重計算絕對距離，不能體現(xiàn)數(shù)據(jù)的整體性；余弦相似度側(cè)重方向差異；皮爾遜相關(guān)系數(shù)解決了各維度量綱的差異性，計算相似度時更側(cè)重于考慮整體性，通過減去用戶的均值，實現(xiàn)了對于同一個用戶多維度的考察，計算公式如式(1)所示：

sim(uu,uv)=

(1)

表3所示為用戶-用戶相似矩陣S。本文應用皮爾遜相關(guān)系數(shù)法計算用戶之間的相似度。

Table 3 User-user similarity matrix S表3 用戶-用戶相似矩陣S

3 帶時間參數(shù)的協(xié)同過濾

“物以類聚，人以群分”，人們總是尋找和自己興趣相同的用戶，把用戶分成幾個類型。本文選擇使用一種基于模糊聚類FCCF(Fuzzy Clustering Collaborative Filtering)的算法，根據(jù)用戶對項目的評分把用戶分成不同的類，每類對應相同興趣愛好的用戶。但是，由于用戶評分數(shù)據(jù)存在嚴重的數(shù)據(jù)稀疏問題，使得模糊聚類效果很差。

本文應用SMOTE過采樣技術(shù)對原數(shù)據(jù)進行填充，有效解決了稀疏問題。在此基礎(chǔ)上提出伴隨時間因子的模糊聚類協(xié)同過濾推薦算法，首先構(gòu)造項目評分矩陣，并計算用戶相似矩陣，采用模糊聚類對用戶進行聚類操作；然后引入時間因子，對用戶感興趣的商品評分進行預測，使得推薦信息更具有實時性。伴隨時間因子的模糊聚類協(xié)同過濾推薦算法流程圖如圖1所示。

Figure 1 Fuzzy cluster collaborative filtering recommendation algorithm with time of SMOTE圖1 伴隨時間因子的模糊聚類協(xié)同過濾推薦算法

3.1 數(shù)據(jù)預處理-填充稀疏數(shù)據(jù)

不平衡數(shù)據(jù)集是指數(shù)據(jù)集中某些類樣本明顯少于其他類[18]。在實際問題中不平衡問題普遍存在，比如文本分類、醫(yī)療診斷和天氣預測等。SMOTE利用K近鄰和線性插值，在相距較近的2個少數(shù)類樣本間按照一定規(guī)則人工插入新樣本，使少數(shù)類樣本增加達到數(shù)據(jù)平衡,傳統(tǒng)的隨機采樣容易導致過擬合現(xiàn)象，SMOTE針對該現(xiàn)象有很好的改善作用。這種填補缺項數(shù)據(jù)的技術(shù)能夠很好地解決數(shù)據(jù)稀疏問題，同時不影響模糊聚類的分類性質(zhì)，所以本文應用SMOTE過采樣技術(shù)對原始數(shù)據(jù)集進行預處理，生成用戶-項目評分矩陣。

SMOTE處理數(shù)據(jù)的基本思想：數(shù)據(jù)預處理階段，為降低數(shù)據(jù)不平衡度，應用K近鄰合成新的數(shù)據(jù)加入到數(shù)據(jù)集中，以此填補空白缺項。推薦系統(tǒng)的原始用戶評分數(shù)據(jù)中，給定的評分數(shù)據(jù)很少，大部分評分缺項，造成嚴重的矩陣稀疏問題。為了便于討論，本文規(guī)定已評分樣本為少數(shù)類樣本，未評分樣本為多數(shù)類樣本，使用SMOTE過采樣技術(shù)填充稀疏數(shù)據(jù)的算法步驟如下所示：

(1)對于少數(shù)類樣本rui，以歐氏距離(式(2))計算K近鄰。針對某一用戶的項目ii，計算少數(shù)類樣本中和項目ii有公共評分的所有用戶間的距離，得到K近鄰，其中K值默認為5。

(2)

其中,i=1,2,…,n;uu,uv為2個不同的用戶

(2)根據(jù)項目評分中樣本的不平衡比確定采樣倍率。對于每一個少數(shù)類樣本rui,從其K近鄰中隨機選擇L條用戶交互記錄，并根據(jù)式(3)生成新樣本ruj：

ruj=rui+rand(0,1)*(rvi-rui)

(3)

其中,u,v=1,2,…,m;i=1,2,…,n;rand(0,1) 表示0～1的隨機數(shù)。

(3)將新生成的樣本全部加入原始數(shù)據(jù)集中，解決數(shù)據(jù)的稀疏問題。

3.2 用戶-項目評分矩陣的模糊聚類

模糊聚類是利用模糊等價關(guān)系將給定對象進行等價類劃分，和其他聚類方法不同的是其不需要提前確定聚類數(shù)目，通過對分類對象設(shè)置閾值進行對象的屬性劃分，該矩陣滿足自反性、對稱性和傳遞性。根據(jù)平方法合成傳遞閉包對元素進行編排，確定閾值，當劃分類的數(shù)目趨于穩(wěn)定時確定項目的最終分類。模糊聚類算法FCCF的聚類過程描述如算法1所示：

算法1模糊聚類算法FCCF

輸入：用戶評分矩陣R。

輸出：模糊聚類簇(C1,C2,…,Cx)。

步驟1建立用戶評分矩陣。

設(shè)用戶為論域U={u1,u2,…,um}，每個用戶對應n種類型電影的評分(表示其愛好)rui,i∈1,2,…,m，得到原始用戶有效評分矩陣R=(rui)m×n。

步驟2構(gòu)建模糊相似矩陣可以采用貼近度法、距離法和相似系數(shù)法，本文采用相似系數(shù)法中的皮爾遜相關(guān)系數(shù)建立模糊相似矩陣M，主對角線上的元素都為1，其他位置元素用皮爾遜相關(guān)系數(shù)計算得到，構(gòu)成的對角矩陣如式(4)所示：

u≠v

(4)

步驟3用平方法合成傳遞閉包，建立模糊等價矩陣t(M)，M°M=M2，M2°M2=M4,…，總能找到一個q使得Mq°Mq=M2q。

(5)

式(5)是M的傳遞閉包，并將t(M)中的元素從大到小編排為a1>a2>a3>…>ai，ai為傳遞閉包中的元素。

步驟4計算當閾值λ=a1,a2,…,ai時，對應不同的截集，即模糊聚類簇(C1,C2,…,Cx)。

3.3 伴隨時間因子的用戶評分預測

傳統(tǒng)的協(xié)同過濾推薦算法根據(jù)用戶的偏好，通過用戶的歷史記錄進行推薦，此過程離線進行[19]，忽略了人的興趣會受到時間影響，但現(xiàn)實生活中用戶對物品的喜愛會隨時間發(fā)生改變，歷史記錄與當前評分時間越近，越能代表最近的愛好[20,21]。用戶興趣不斷變化但在傳統(tǒng)的協(xié)同過濾推薦算法中不能體現(xiàn)出來，對用戶評分設(shè)置統(tǒng)一權(quán)重推薦的實時性問題在此時顯得尤為重要。根據(jù)用戶的評價歷史，對用戶進行實時推薦，王永貴等[22]根據(jù)不同的時間段用戶的興趣可能發(fā)生變化，引入時間因子TF1(Time Factor 1)(如式(6)所示)，提高了推薦效果。本文在此基礎(chǔ)上結(jié)合艾賓浩斯遺忘曲線，針對用戶歷史記錄間隔較長的問題，平衡評分時間差，模擬人類興趣變化改進式(6)，將時間因子TF1優(yōu)化為TF2(Time Factor 2)，如式(7)所示。使時間因子參與預測評分，不同的評分時刻將會被賦予不同的時間權(quán)重，這樣可以模擬用戶偏好變化，實現(xiàn)實時推薦，為了描述清晰，將公式中參數(shù)進行統(tǒng)一。

(6)

(7)

其中，Ti為用戶對項目ii評分時對應的時間，T0為用戶初次進行項目評分對應的時間，Tn表示用戶使用推薦系統(tǒng)的總時長,2種時間因子TF1和TF2都記為函數(shù)f(t)，取值為(0,1)。

式(8)所示為用戶評分預測計算式，其中加入了時間因子f(t)。

(8)

針對用戶ui，只要對ui所在的聚類簇利用式(8)，就可以計算出該用戶對感興趣商品的評分預測值，把預測值高的商品推薦給該用戶。可見，經(jīng)過聚類的協(xié)同過濾大大降低了計算量。

4 實驗

為了描述方便，將文獻[9]基于云模型相似度的用戶推薦算法改進記為CM-CF(Cloud Model Collaborative Filtering)算法;將文獻[16]改進模糊劃分聚類的協(xié)同過濾推薦算法記為FCCF算法;使用SMOTE過采樣技術(shù)預處理的模糊聚類協(xié)同過濾推薦算法記為SMOTE-FCCF算法；代入時間因子TF1的模糊聚類協(xié)同過濾推薦算法記為SMOTE-TF1-FCCF算法；使用SMOTE過采樣技術(shù)預處理，代入時間因子TF2的模糊聚類協(xié)同過濾推薦算法記為SMOTE-TF2-FCCF算法。下面通過實驗進行對比研究，以驗證模糊聚類和時間因子對推薦算法的效果。

通過平均絕對誤差MAE(Mean Absolute Error )和均方根誤差RMSE(Root Mean Square Error)指標，檢驗近鄰個數(shù)k和推薦個數(shù)N對推薦效果的影響?；谀：垲惔?C1,C2,…,Cx)，在聚類簇中確定近鄰個數(shù)的最優(yōu)值，進而確定推薦個數(shù)。

4.1 數(shù)據(jù)集

實驗使用的數(shù)據(jù)集是由美國明尼蘇達州大學GroupLens項目組創(chuàng)建，其中包括100 KB、1 MB、10 MB 3個規(guī)模的數(shù)據(jù)集。本文使用MovieLens-100k數(shù)據(jù)集驗證推薦效果。數(shù)據(jù)集包含943名用戶對1 682部電影的1 000 000條評分，且數(shù)據(jù)集的每個用戶對電影的評分都是1～5分。數(shù)據(jù)集上每個評分數(shù)據(jù)都帶有評分時的時間戳(時刻序列值)，用戶是初次評價即為T0，對第i個項目評價即為Ti，直接代入公式參與運算。本文構(gòu)建的數(shù)據(jù)集用戶項目評分矩陣稀疏度為93.7%。

4.2 推薦評價

本文采用檢驗推薦方法最常用的MAE(平均絕對誤差)、RMSE(均方根誤差)指標：

(9)

(10)

其中，pi表示預測評分，qi表示實際評分，N表示有N個項目。值越小說明算法性能越好。

為驗證SMOTE-TF2-FCCF算法的有效性，本文基于控制變量法設(shè)計了2組實驗進行測試，同時對過采樣倍率進行設(shè)置，如果過采樣倍率過大，新增樣本點的選取范圍也會增大，難以尋找真正的近鄰用戶；如果過采樣倍率過小，數(shù)據(jù)的稀疏度依然很大，難以起到數(shù)據(jù)填充的效果，因此設(shè)置過采樣倍率為500%。

4.3 復雜度分析

除了考慮算法的準確性，算法的時間效率也是不容忽視的衡量指標。5種算法計算相似度的時間復雜度都為Ο(m×m)，m為用戶數(shù)目，相差不大；但加入模糊聚類后評分過程的復雜度為Ο(nk)(n為項目數(shù)，k為用戶的近鄰個數(shù))，其余4種傳統(tǒng)的項目評分過程的復雜度為Ο(m×n)，一般地有m>>k，所以本文算法通過模糊聚類搜索近鄰用戶，大大縮短了推薦的時間，保證了推薦的效率。

4.4 實驗設(shè)計和結(jié)果分析

實驗環(huán)境為：

操作系統(tǒng)為Windows 10 x64,處理器為Intel(R) Core(TM) i5-8250U CPU @ 1.60 GHz 1.80 GHz,RAM為12 GB。

語言環(huán)境為gcc version 8.2.0, Python 3.7.5。

4.4.1 CM-CF算法、FCCF算法和SMOTE-FCCF算法的對比

A組實驗是CM-CF算法、FCCF算法和SMOTE-FCCF算法在MovieLens-100k數(shù)據(jù)集上測試模糊聚類的效果，分別通過云模型、模糊聚類和加入SMOTE過采樣技術(shù)填充的模糊聚類，以MAE和RMSE作為檢驗算法準確性的評價指標，進行3種算法的對比。

A組實驗結(jié)果如表4所示，設(shè)置聚類數(shù)的取值為1～500，間隔為1，在MAE值最低點時確定聚類數(shù)，求得RMSE值。觀察類簇中用戶的個數(shù)多集中于[20,60],以遞增間隔為2，此時3種算法的最近鄰k的最優(yōu)取值分別為40，50，26。推薦個數(shù)N的最優(yōu)取值分別為8，5，7。

Table 4 Experimental comparison of cloud model recommendation and fuzzy cluster recommendation表4 云模型推薦與模糊聚類推薦實驗對比

可以看出CM-CF算法的MAE值最小,為0.75，RMSE為0.96；FCCF算法在聚類數(shù)為20時，MAE值最小,為0.63，RMSE為0.91；FCCF算法較CM-CF算法的MAE、RMSE和聚類數(shù)均相對較小，表明模糊聚類確實可以提高推薦的準確性。SMOTE-FCCF算法在聚類數(shù)為30時，MAE值最小,為0.62，RMSE為0.89，SMOTE-FCCF算法的MAE、RMSE比FCCF算法的也小，說明SMOTE過采樣填充優(yōu)于平均值填充，本文提出的經(jīng)過數(shù)據(jù)預處理后的模糊聚類協(xié)同過濾推薦算法SMOTE-FCCF優(yōu)于文獻[9]和文獻[16]提出的算法。

4.4.2 SMOTE-FCCF算法、SMOTE-TF1-FCCF算法和SMOTE-TF2-FCCF算法對比

為了驗證加入時間因子和改進時間因子的有效性，將SMOTE-FCCF、SMOTE-TF1-FCCF和SMOTE-TF2-FCCF算法進行對比，采用MAE和RMSE檢驗算法準確性。B組實驗結(jié)果如表5所示。聚類數(shù)目通過數(shù)據(jù)預處理進行模糊聚類確定，與時間因子無關(guān)，所以B組實驗和A組實驗中SMOTE-TF2-FCCF的聚類數(shù)目相同，都為30，3種算法只是驗證時間因子的效果，故聚類數(shù)、最近鄰數(shù)k、推薦個數(shù)N的最優(yōu)取值都為30，26，7。

Table 5 Experimental comparison of influence of time factor表5 時間因子影響實驗對比

橫向比較，SMOTE-FCCF的MAE和RMSE分別為0.62和0.89。加入時間因子TF1，SMOTE-TF1-FCCF的MAE和RMSE分別為0.61和0.88,MAE和RMSE較SMOTE-FCCF算法明顯降低，可以發(fā)現(xiàn)，加入時間因子TF1可以提升推薦效果，而加入時間因子TF2后，SMOTE-TF2-FCCF算法的MAE和RMSE分別為0.60和0.76,該值優(yōu)于SMOTE-TF1-FCCF算法的，推薦效果大大提高。

縱向比較3種算法的MAE和RMSE值，SMOTE-TF1-FCCF和SMOTE-TF2-FCCF算法的結(jié)果都優(yōu)于SMOTE-FCCF算法的，說明人們的興趣會隨時間的遷移而發(fā)生變化，改進的時間因子TF2明顯優(yōu)于TF1,說明改進平衡時間因子有效，可進一步提高推薦算法的推薦性能。

5 結(jié)束語

協(xié)同過濾推薦算法最大的優(yōu)點是對推薦對象沒有特殊的要求，能夠有效地使用其他相似用戶的反饋信息?；谀：垲惖膮f(xié)同過濾推薦算法大大減少了運算量，但也帶來了數(shù)據(jù)稀疏問題。

本文提出伴隨時間的模糊聚類協(xié)同過濾推薦算法SMOTE-TF2-FCCF，根據(jù)用戶之間的評分差異，對數(shù)據(jù)進行預處理，采用SMOTE過采樣技術(shù)進行填充，有效解決了數(shù)據(jù)稀疏性問題；利用模糊聚類減小相似用戶集合，降低計算復雜度，同時在聚類簇上加入用戶評級項目的時間因子，考慮了推薦的實時性。實驗結(jié)果表明，經(jīng)過SMOTE過采樣預處理的模糊聚類協(xié)同過濾算法優(yōu)于其他數(shù)據(jù)預處理方法，伴隨時間的模糊聚類協(xié)同過濾算法優(yōu)于沒有時間因子的推薦算法，而本文改進的SMOTE-TF2-FCCF算法性能最好。

模糊聚類算法對數(shù)據(jù)稀疏性非常敏感，在未來的工作中，將對改進稀疏度的方法做進一步研究，或者使用對數(shù)據(jù)沒有限制的新的聚類方法，以進一步提高推薦算法的性能。