石 朋,姚文明,王 祥

(1.中國電子科技集團公司第十五研究所,北京 100083; 2.中國農業(yè)銀行研發(fā)中心,北京 100071)

0 引 言

面對大數據時代的到來，信息的提供者和消費者都遇到了很大的挑戰(zhàn)。對于信息提供者來說，由于不知道消費者的具體需求，可能會給消費者提供很多其實并不需要的信息，不但沒有給消費者帶來便利和幫助，反而變成了消費者眼中的垃圾信息。對于消費者來說，我們處在一個信息爆炸的時代，一方面，大量的信息使我們對于某一類型信息有了更多的選擇；另一方面，大量的信息也使我們在尋找意向信息的時候要花費大量的時間和精力，面對日益增長的PB級甚至TB級的數據，就像是大海撈針，力不從心。面對這種情況，信息檢索技術的出現大大緩解了“信息過載”的問題，人們通過關鍵詞和主題可以搜索到相關內容的信息，但是由于缺乏用戶針對的因素，搜索引擎把檢索到的所有信息全部提交給用戶，由于數據量巨大，對于用戶來說依舊要耗費大量的時間去人工尋找，即又一次出現了“信息過載”的問題。在這種情況下，如果能夠根據消費者的歷史行為數據分析出用戶特征、興趣度等有價值的信息進行有針對的推薦，既能提高用戶體驗又能節(jié)約用戶時間，這對于消費者來說是非常有價值的。于是，個性化推薦系統(tǒng)[1]應運而生。

當下應用范圍最廣的推薦算法是協(xié)同過濾算法[2]，它無須分析內部屬性，僅依靠用戶歷史行為信息就可以完成推薦。協(xié)同過濾算法基本可以分為基于用戶的協(xié)同過濾算法(UBCF)[3]和基于項目的協(xié)同過濾算法(IBCF)[4]。UBCF算法理念是將與當前用戶相似的人感興趣評分高的項目推薦給此用戶，而IBCF算法理念是將與當前項目相似的項目推薦給目標用戶,但存在冷啟動[5]和矩陣稀疏[6]時效果不理想的問題。而Slope One算法[7]是Lemire等人在2005年提出的一種基于項目的協(xié)同過濾算法，算法形式簡潔易懂，擴展性強，能夠在一定程度上緩解冷啟動的情況，有良好的推薦精度。但是，Slope One算法在計算項目之間的評分偏差的時候沒有考慮到用戶評價的項目數量而僅采用了均值計算，于是在文獻[7]中同時提出了一種加權Slope One算法；Gao等人[8]將Slope One算法與基于內容的推薦算法結合起來，提高了推薦的準確性，但是在數據矩陣稀疏的情況下效果不理想，擴展性差；文獻[9]研究表明，在用戶評分矩陣稠密的時候Slope One算法相比于矩陣稀疏時有更好的推薦效果；Zhang等人[10]通過利用加權Slope One算法來填充稀疏矩陣，從而在最近鄰集合中進行評分預測，相對緩解了矩陣稀疏的問題，提高了推薦準確性；Liu等人[11]利用項目相似性對稀疏矩陣填充，然后利用用戶相似性進行最近鄰尋找，有效緩解了矩陣稀疏性的問題；You等人[12]提出數據聚類的思想，減少了計算復雜度，在一定程度上提高了推薦算法的實時性。黃皓璇等人[13]將用戶隨著時間興趣變化函數融入到Slope One算法中，提高了推薦的精度。

本文在前人研究的基礎上，提出一種融合用戶模糊聚類和用戶相似度的加權Slope One算法，并通過實驗將本文算法模型與傳統(tǒng)的Slope One算法和加權Slope One算法進行對比，實驗表明，本文算法進一步提高了推薦效率，降低了推薦誤差。

1 相關工作

1.1 用戶項目評分矩陣

通過對數據庫中用戶對項目的評價數據進行格式化，轉化為m行n列的用戶項目評價矩陣Ru,i,如表1所示，其中用戶集U={u1,u2,…,um}由m個用戶組成，項目集I={i1,i2,…,in}由n個項目組成，ri,j表示用戶ui對項目ij的評分，若沒有用戶對項目評分則ri,j= 0，用戶對項目的評分區(qū)間為1～5分，評分越高，代表用戶對項目越喜歡。

表1 用戶項目評分矩陣Ru,i

1.2 Slope One算法

Slope One是一種基于評分的協(xié)同過濾算法，于2005年由丹尼爾等人提出，具有易于實現、計算速度快、可擴展性好等特點，同時對數據稀疏性有較好的適應性；與其他的個性化推薦算法相比，Slope One算法無須計算項目之間的相似度,而是用一種簡單的線性回歸模型w=f(v)+b進行預測，其中，w代表目標用戶對項目i的評分，f(v)代表目標用戶對該項目以外的項目評分，b為項目i相對于其他項目(用j表示其他項目)的平均偏差，用Devi,j表示，如圖1所示，有A用戶和B用戶2人，其中A用戶對項目1和項目2都進行了評價，B用戶僅對項目1進行了評價，通過以上條件來預測B用戶對項目2的評分。利用Slope One算法可知B用戶對項目2的評分為：2+(1.5-1)=2.5。

圖1 Slope One算法的思想

用Devi,j表示目標項目與其他項目的平均評分偏差，計算公式如式(1)所示：

(1)

其中，x表示訓練集,Si,j(x)表示對項目i以及其他項目(用j表示其他項目)都評分的用戶集合，Num(Si,j(x))表示在Si,j(x)集合中的用戶總數。

通過以上的分析以及在式(1)已知的基礎上，利用Pu,i=Devi,j+ru,j即可通過式(2)計算出目標用戶對目標項目的預測評分：

(2)

其中，ri表示目標用戶對所有項目評分的集合，Num(ri)表示目標用戶評分項目數量。

1.3 加權Slope One算法

在1.2節(jié)中的Slope One算法在計算2個項目的相對平均偏差Devi,j的時候，沒有考慮到用戶評價的項目數量而是進行了平均計算，缺乏合理性。例如一種情況為100人同時對項目i和項目j進行了評價，另一種情況為10人對項目j和項目k進行了評價，2種情形下得到的Devi,j和Devj,k有著不同的說服力。因此Lemire等人提出了Weighted Slope One算法，即加權Slope One算法，算法的思想是與目標商品共同評價的商品數量越多，給予更大的權值，該算法有效修正了評價偏差的計算，同時進一步提高了推薦的準確度，計算公式如式(3)所示：

(3)

其中，Pu,i代表用戶u對項目i的評分預測，|Ci,j|為用戶的數量權重。

1.4 模糊C-均值聚類

模糊C-均值聚類算法是一種基于劃分的算法，不同于K-means等硬聚類算法，硬聚類算法可以導出確定的聚類，即一個對象僅能屬于一個類，不存在重疊的情況。而模糊C-均值聚類的思想是一個對象在一定程度上屬于一個類，也可以同時以不同程度屬于幾個類，因此模糊C-均值聚類是一種柔性的聚類算法。定義在論域D中任意一個元素x，如果都有一個U(x)∈[0,1]與x相互對應，則稱U為D上的模糊集,U(x)稱為x對D的隸屬度。隸屬度函數是表示一個對象x隸屬于集合U的程度的函數，記為U(x)，取值范圍為[0,1],函數值越趨近于1，則隸屬度越高。

模糊C-均值聚類引入了模糊邏輯的概念，它用隸屬度矩陣U=[uis]表示每個對象隸屬于某個類的程度大小，模糊C-均值聚類的目標函數如式(4)所示：

(4)

(5)

把上面的條件極值問題轉化為無條件極值問題，引入n個拉格朗日因子，繼而利用拉格朗日乘數法把條件極值轉化為無條件極值問題，即可得到隸屬度矩陣U,過程如下：

(6)

由式(6)可得：

(7)

(8)

(9)

將式(9)代入式(7)得uis，如式(10)所示,從而得到隸屬度矩陣U：

(10)

聚類中心C的求解過程如下：

(11)

dist(ci,xs)2=‖ci-xs‖A=(ci-xs)TA(ci-xs)2

(12)

其中，A為權重，由式(11)和式(12)聯立得式(13)：

即可得聚類中心ci如式(14)所示：

(14)

2 本文算法模型

本文對傳統(tǒng)的加權Slope One算法按照如下步驟進行優(yōu)化：

步驟1對用戶項目評分數據集進行預處理,生成用戶評分矩陣。

步驟2使用模糊C-均值聚類算法，對所有用戶進行模糊聚類，將相似度高的用戶劃歸同一類中。

步驟3在每個聚類內部根據用戶評分矩陣計算用戶間相似度并構建用戶相似度矩陣，依據用戶相似度矩陣尋找TopK個最近鄰。

步驟4將用戶相似度函數融入加權Slope One算法中，來計算項目間的偏差，并預測用戶對項目的評分。

步驟5最后根據評分集合選擇最優(yōu)項目集推薦給目標用戶。

2.1 對用戶進行模糊C-均值聚類

聚類可以將有相似特征的用戶進行快速的分門別類，同一聚類中的用戶相似程度高，不同聚類之間的用戶相似程度低。在構建完成用戶簇后，可以根據同一類簇中用戶的特征均值來評估目標用戶。

當下處于大數據的時代，個性化推薦系統(tǒng)每天的數據以PB乃至TB量級的速度快速增長；當數據量越來越大，對系統(tǒng)的運算能力和效率產生了越來越大的挑戰(zhàn)。因此，在對大量的數據進行計算前，先對數據進行聚類是提高系統(tǒng)效率、降低運算復雜度的有效方式。用戶屬性較多、特征多樣，K-means算法[14]等一些硬聚類算法將用戶硬性地分在一個簇中，缺乏合理性，而模糊C-均值聚類算法[15]是一種軟聚類算法，可以利用數學理論定量地確定樣本的親疏關系，每個用戶可以屬于多個類簇，更加客觀合理。

設N為用戶集大小，K為聚類中心個數，UN×K={Us,i}為隸屬度矩陣,C={c1,c2,…,ck}為聚類中心列表，式(15)為對用戶模糊聚類的目標函數:

(15)

在協(xié)同過濾算法中，相似性的計算尤為重要，基于向量的相似性計算主要分為以下3種[16-21]:余弦相似度、修正的余弦相似度、皮爾遜相關系數。Herlocker等人[22]通過實驗發(fā)現皮爾遜相關系數比其他相關性度量方法更加精確。因此，本文采用皮爾遜相似度的方法計算用戶s和第i個聚類中心的相似度，計算公式如式(16)所示：

(16)

輸入：用戶向量表和終止條件簇的數目K;

輸出：達到終止條件規(guī)定簇的數目，得到各類聚類中心和各個樣本對于各類的隸屬矩陣。

處理：

步驟1初始化各聚類中心；

步驟2Repeat；

步驟3根據式(17)用當前的聚類中心計算隸屬度函數并更新隸屬度矩陣U：

(17)

步驟4根據式(18)用當前的隸屬度函數更新計算各聚類中心ci：

(18)

步驟5直到目標函數J(U,C)收斂，即完成了模糊聚類劃分。

2.2 改進的加權Slope One算法

加權Slope One算法考慮了在計算項目間相對平均偏差過程中共同評分用戶數量的權重因子，賦予共同評分用戶數量多的項目以更大的權重值，雖然在部分情況下提高了推薦的精確度，但是在有些情況下也容易出現較大的誤差，同時該算法也忽略了用戶的相似度能對推薦結果產生影響的因素；因此，將用戶的相似度函數融入到加權Slope One算法的偏差計算公式中進行優(yōu)化，可以進一步地提高推薦的精確率。

計算用戶或者項目間相似度常用的方法有杰卡德系數、余弦相似度和皮爾遜系數，其中皮爾遜系數去中心化和歸一化的特性，即在用戶對項目評分的基礎上去掉所有用戶對項目的平均評分，隱形地保留了用戶評分的偏好特征，更能反映出用戶間的線性相關性，因此在本次計算中，采用了皮爾遜相似度的計算方法來計算用戶間的相似度，用數學公式表示，皮爾森相關系數為2個變量的協(xié)方差除以2個變量的標準差，如式(19)所示：

(19)

結合皮爾遜系數對加權Slope One算法的偏差計算公式進行改進，式(20)為改進后的加權Slope One算法中項目i和項目j的偏差計算公式Devi,j，最后通過式(3)即可求出預測評分值Pu,i，進而列出topN個得到最佳預測值的項目推薦給目標用戶。

(20)

3 實驗與結果分析

3.1 實驗環(huán)境和數據集的選取

實驗環(huán)境：macOS系統(tǒng)。硬件配置參數：CPU為2.3 GHz 4核Intel Core i5，內存為8 GB 2133 MHz，實驗語言環(huán)境為Python3.7；實驗數據集采用的是由明尼蘇達大學的GroupLens團隊采集并匯聚完成的電影評分數據集MovieLens。如表2所示，本文選用ml-100k數據包，它由943個用戶創(chuàng)建，包含了對1682部電影的10萬條評分數據，評分形式是采用1～5分來對電影進行打分，用戶對電影的評分越高，表示當前用戶對該電影越喜歡。

表2 MovieLens數據集

3.2 評價標準

在對本文算法模型進行標準評價中，采用平均絕對誤差[23](Mean Absolute Error，MAE)來衡量推薦結果的有效性。平均絕對誤差MAE是通過計算用戶評分的預測值和用戶評分的實際值之間的偏差平均值來度量算法是否精確。例如，有n個項目預測的評分向量為(p1,p2,…,pn),實際評分向量為(t1,t2,…,tn),則算法表示如式(21)所示：

(21)

3.3 結果對比與分析

設置實驗1用來驗證模型在不同聚類數量下的準確度情況，聚類簇數在[0,30]區(qū)間內，以間隔為4來觀察聚類數量對實驗的影響，結果如圖2所示，在聚類簇數小于8時，MAE值呈下降狀態(tài)，在聚類簇數為8的時候達到最佳，在大于8時，MAE值又呈現緩慢上升的趨勢，說明在聚類數為8時,為本文算法模型的最佳狀態(tài)。

圖2 不同聚類簇數下的MAE值

實驗2在聚類數為8的情況下，將本文算法與傳統(tǒng)的Slope One算法(SO)、基于聚類的Weighted Slope One算法、融合用戶相似度的加權Slope One算法在不同數量的最近鄰進行了對比實驗，來驗證本文算法模型的有效性和穩(wěn)定性。從圖3可以看出，隨著最近鄰居個數的逐漸增加，Slope One算法由于不受最近鄰居的數量限制，所以其平均絕對誤差不變，本文算法和Weighted Slope One算法及融合用戶相似度的加權Slope One算法平均絕對誤差呈現下降的趨勢，然后又逐步趨近平緩狀態(tài)。說明最近鄰居并非越多越好，而是在達到最佳數量后，數量對最小平均誤差影響權重變小。

經過實驗以及與其他算法的對比，驗證了本文算法的有效性和穩(wěn)定性。最終通過圖4可了解到本文算法確實改進了推薦效果，在一定程度上較以往算法在推薦精確度上得到有效提升。

圖4 本文算法與其他算法MAE對比

4 結束語

本文通過分析傳統(tǒng)的Slope One算法的思想和缺陷，以及對學者關于這一研究做出了一些突破和成就進行了敘述和參考，針對傳統(tǒng)Slope One算法在預測和推薦中的準確度和穩(wěn)定性進行了進一步的優(yōu)化，首先引用模糊聚類算法對巨大復雜的用戶集中相似的用戶進行了聚類；同時對傳統(tǒng)的加權Slope One算法進行了改進，將用戶相似度融合進Weighted Slope One算法中，然后進行評分預測并尋找最優(yōu)推薦項目集合，最后通過實驗將本文算法模型與其他3種經典算法模型進行了對比和分析，驗證了本文算法模型在一定程度上提高了推薦效率，對推薦結果的精準性和有效性起到了積極作用。