融合用戶模糊聚類和相似度的加權(quán)Slope One優(yōu)化

石 朋,姚文明,王 祥

(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)行有針對的推薦，既能提高用戶體驗又能節(jié)約用戶時間，這對于消費(fèi)者來說是非常有價值的。于是，個性化推薦系統(tǒng)[1]應(yīng)運(yùn)而生。

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

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

1 相關(guān)工作

1.1 用戶項目評分矩陣

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

圖1 Slope One算法的思想

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

(1)

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

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

(2)

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

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

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

(3)

其中，Pu,i代表用戶u對項目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對用戶項目評分?jǐn)?shù)據(jù)集進(jìn)行預(yù)處理,生成用戶評分矩陣。

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

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

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

步驟5最后根據(jù)評分集合選擇最優(yōu)項目集推薦給目標(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)行計算前，先對數(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é)同過濾算法中，相似性的計算尤為重要，基于向量的相似性計算主要分為以下3種[16-21]:余弦相似度、修正的余弦相似度、皮爾遜相關(guān)系數(shù)。Herlocker等人[22]通過實(shí)驗發(fā)現(xiàn)皮爾遜相關(guān)系數(shù)比其他相關(guān)性度量方法更加精確。因此，本文采用皮爾遜相似度的方法計算用戶s和第i個聚類中心的相似度，計算公式如式(16)所示：

(16)

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

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

處理：

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

步驟2Repeat；

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

(17)

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

(18)

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

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

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

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

(19)

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

(20)

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

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

實(shí)驗環(huán)境：macOS系統(tǒng)。硬件配置參數(shù)：CPU為2.3 GHz 4核Intel Core i5，內(nèi)存為8 GB 2133 MHz，實(shí)驗語言環(huán)境為Python3.7；實(shí)驗數(shù)據(jù)集采用的是由明尼蘇達(dá)大學(xué)的GroupLens團(tuán)隊采集并匯聚完成的電影評分?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是通過計算用戶評分的預(yù)測值和用戶評分的實(shí)際值之間的偏差平均值來度量算法是否精確。例如，有n個項目預(yù)測的評分向量為(p1,p2,…,pn),實(shí)際評分向量為(t1,t2,…,tn),則算法表示如式(21)所示：

(21)

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

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

圖2 不同聚類簇數(shù)下的MAE值

實(shí)驗2在聚類數(shù)為8的情況下，將本文算法與傳統(tǒng)的Slope One算法(SO)、基于聚類的Weighted Slope One算法、融合用戶相似度的加權(quán)Slope One算法在不同數(shù)量的最近鄰進(jìn)行了對比實(shí)驗，來驗證本文算法模型的有效性和穩(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í)驗以及與其他算法的對比，驗證了本文算法的有效性和穩(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)推薦項目集合，最后通過實(shí)驗將本文算法模型與其他3種經(jīng)典算法模型進(jìn)行了對比和分析，驗證了本文算法模型在一定程度上提高了推薦效率，對推薦結(jié)果的精準(zhǔn)性和有效性起到了積極作用。