石 朋,姚文明,王 祥

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

0 引 言

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

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

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

1 相關(guān)工作

1.1 用戶項(xiàng)目評分矩陣

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

表1 用戶項(xiàng)目評分矩陣Ru,i

1.2 Slope One算法

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

圖1 Slope One算法的思想

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

(1)

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

通過以上的分析以及在式(1)已知的基礎(chǔ)上，利用Pu,i=Devi,j+ru,j即可通過式(2)計(jì)算出目標(biāo)用戶對目標(biāo)項(xiàng)目的預(yù)測評分：

(2)

其中，ri表示目標(biāo)用戶對所有項(xiàng)目評分的集合，Num(ri)表示目標(biāo)用戶評分項(xiàng)目數(shù)量。

1.3 加權(quán)Slope One算法

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

(3)

其中，Pu,i代表用戶u對項(xiàng)目i的評分預(yù)測，|Ci,j|為用戶的數(shù)量權(quán)重。

1.4 模糊C-均值聚類

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

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

(4)

(5)

把上面的條件極值問題轉(zhuǎn)化為無條件極值問題，引入n個拉格朗日因子，繼而利用拉格朗日乘數(shù)法把條件極值轉(zhuǎ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為權(quán)重，由式(11)和式(12)聯(lián)立得式(13)：

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

(14)

2 本文算法模型

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

步驟1對用戶項(xiàng)目評分?jǐn)?shù)據(jù)集進(jìn)行預(yù)處理,生成用戶評分矩陣。

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

步驟3在每個聚類內(nèi)部根據(jù)用戶評分矩陣計(jì)算用戶間相似度并構(gòu)建用戶相似度矩陣，依據(jù)用戶相似度矩陣尋找TopK個最近鄰。

步驟4將用戶相似度函數(shù)融入加權(quán)Slope One算法中，來計(jì)算項(xiàng)目間的偏差，并預(yù)測用戶對項(xiàng)目的評分。

步驟5最后根據(jù)評分集合選擇最優(yōu)項(xiàng)目集推薦給目標(biāo)用戶。

2.1 對用戶進(jìn)行模糊C-均值聚類

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

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

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

(15)

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

(16)

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

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

處理：

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

步驟2Repeat；

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

(17)

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

(18)

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

2.2 改進(jìn)的加權(quán)Slope One算法

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

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

(19)

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

(20)

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

3.1 實(shí)驗(yàn)環(huán)境和數(shù)據(jù)集的選取

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

表2 MovieLens數(shù)據(jù)集

3.2 評價標(biāo)準(zhǔn)

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

(21)

3.3 結(jié)果對比與分析

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

圖2 不同聚類簇?cái)?shù)下的MAE值

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

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

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

4 結(jié)束語

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