協(xié)同過濾算法中冷啟動問題研究①

邵 煜,謝穎華

(東華大學(xué) 信息科學(xué)與技術(shù)學(xué)院,上海 201620)

互聯(lián)網(wǎng)的快速發(fā)展給人們的生活帶來了極大的便利,同時,海量的信息數(shù)據(jù)引發(fā)了“信息超載”問題[1].個性化推薦系統(tǒng)應(yīng)運而生,通過對用戶興趣建模,在海量的數(shù)據(jù)中找到合適的物品推薦給用戶,極大地提高了信息使用率[2].

推薦系統(tǒng)常用的推薦算法有: 基于內(nèi)容的推薦、基于關(guān)聯(lián)規(guī)則的推薦、基于知識的推薦以及協(xié)同過濾推薦[3-5].其中,協(xié)同過濾推薦算法是應(yīng)用最成功最廣泛的一種算法.

協(xié)同過濾算法依然面臨著諸多局限性,包括數(shù)據(jù)稀疏性、冷啟動、可擴展等問題,影響了系統(tǒng)的推薦結(jié)果和推薦質(zhì)量.

1 傳統(tǒng)的協(xié)同過濾算法

根據(jù)用戶行為數(shù)據(jù)設(shè)計的算法稱為協(xié)同過濾算法[6].協(xié)同過濾算法建立在數(shù)據(jù)挖掘的基礎(chǔ)上,算法的工作原理是: 根據(jù)用戶的歷史評分計算相似度,相似度高的判為目標(biāo)用戶的鄰居用戶,依據(jù)鄰居集用戶的歷史評分計算目標(biāo)用戶的可能評分值,將評分值高的前N項推薦給目標(biāo)用戶(Top-N推薦).

協(xié)同過濾算法可以分為基于用戶的協(xié)同過濾(user-based CF)和基于項目的協(xié)同過濾(item-based CF).

1.1 冷啟動問題

協(xié)同過濾的冷啟動問題分為新用戶冷啟動、新項目冷啟動和新系統(tǒng)冷啟動,協(xié)同過濾算法的核心是分析用戶-項目評分矩陣,計算相似度.當(dāng)系統(tǒng)中有新用戶加入時,該用戶在系統(tǒng)中不存在歷史評分?jǐn)?shù)據(jù),不能根據(jù)傳統(tǒng)算法計算用戶間的相似度,也就無法為其進(jìn)行推薦,這就是協(xié)同過濾算法的新用戶冷啟動問題[7];同樣地,當(dāng)系統(tǒng)中加入新項目時,由于沒有該項目的歷史評分記錄,推薦算法難以將該項目推薦給用戶,這就是新項目的冷啟動問題.

1.2 冷啟動問題的研究現(xiàn)狀

近年來,許多專家學(xué)者對冷啟動問題提出了一系列的解決辦法,比如眾數(shù)法、平均值法、相似度度量法等等[8],減少了冷啟動問題對推薦質(zhì)量的影響.

Xu JW,Yao Y等提出了一種新型的評分比較策略(RaPare)[9]學(xué)習(xí)冷啟動用戶/項目的潛在性能,通過尋找冷啟動用戶/項目和現(xiàn)有用戶/項目之間的差異,為冷啟動用戶/項目的潛在性能提供細(xì)粒度校準(zhǔn).Nguyen VD,Sriboonchitta S,Huynh VN引入了一種用戶社交網(wǎng)絡(luò)和軟評分相結(jié)合的協(xié)同過濾推薦系統(tǒng)[10],通過用戶社交網(wǎng)絡(luò)提取社區(qū)特征來解決冷啟動問題.Katarya R,Verma OP將計算相似性的不對稱方法與矩陣分解和基于典型性的協(xié)同過濾(Tyco)相結(jié)合[11],實現(xiàn)了一種改進(jìn)的電影推薦算法.改進(jìn)算法采用了Pearson相關(guān)系數(shù)計算相似度,用線性回歸進(jìn)行預(yù)測,得到更好的推薦結(jié)果.

2 相似度的計算方法

2.1 傳統(tǒng)的相似度算法

協(xié)同過濾算法根據(jù)相似度的計算結(jié)果找到目標(biāo)用戶/項目的鄰居集,因此相似度的計算方法很重要,目前常見的相似度計算方法有: 余弦相似度、歐幾里德距離和Pearson相關(guān)系數(shù)等等.

余弦相似度:

歐幾里德距離:

Pearson相關(guān)系數(shù):

其中,Ru,i,Rj,i分別代表用戶u和用戶j對項目i的評分,分別代表用戶u和j的評分平均值,Iu,j是用戶u,j的共同評分項目集合.

2.2 改進(jìn)后的算法

2.2.1 融合用戶信息模型的基于用戶的協(xié)同過濾算法

通常,各推薦網(wǎng)站的數(shù)據(jù)庫中會含有關(guān)于用戶屬性信息的數(shù)據(jù)集,常見的用戶屬性包括: 用戶ID,性別,年齡,職業(yè),個人偏好等等.某些網(wǎng)站在用戶注冊時會詢問其可能喜歡的類型,以此達(dá)到更優(yōu)的推薦效果.具有相同或者相近屬性的兩個用戶會表現(xiàn)出更相近的興趣愛好[12].因此,本文以用戶的個人信息屬性為切入點,為了解決新用戶的冷啟動問題,通過分析用戶的基本信息特征,設(shè)計了一種融合用戶信息模型的基于用戶的協(xié)同過濾算法.

新算法綜合考慮了用戶的k項基本信息值attri(i=1,2,3,…,k),分別給不同的屬性信息分配權(quán)重λi,計算用戶之間的特征差,用attr(u,v)表示,計算方法如式(5)所示.

其中,λi滿足:

求得用戶特征差值attr(u,v)后,利用Sigmoid函數(shù)(式(7)),計算用戶u和用戶v之間的用戶特征信息相似度simattr(u,v),如式(8)所示.

當(dāng)用戶間相同特征較多時,量化后的特征差值較小,attr(u,v)值較小,simattr(u,v)值較大,表現(xiàn)出用戶較高的相似性,并且由于attr(u,v)值恒為正,確保simattr(u,v)取值在0 ～1之 間.將simattr(u,v)值較小的前K個用戶判定為目標(biāo)用戶的鄰居用戶,預(yù)測新用戶的評分值:

融合用戶信息模型的基于用戶的協(xié)同過濾算法流程圖如圖1所示.

圖1 新用戶冷啟動算法

2.2.2 采用層次聚類的基于項目的協(xié)同過濾算法

協(xié)同過濾冷啟動問題的另一方面是新項目的冷啟動.推薦系統(tǒng)中的項目都有各自的內(nèi)容信息,比如書籍的書名、出版年份、類型、作者;食品的類別、成分;音樂的年份、流派、作曲者等等.在沒有項目歷史評分記錄數(shù)據(jù)的情況下,本文的新算法根據(jù)這些內(nèi)容信息,分析物品內(nèi)容之間的相關(guān)度獲取新項目和其他項目之間的相似度,提出了采用凝聚式層次聚類的新項目相似度算法.

凝聚式層次聚類的相似度計算主要分為三步進(jìn)行:

(1)數(shù)據(jù)初始化處理

對于數(shù)值類信息,可直接用于歐式距離計算.對非數(shù)值類信息,計算項目屬性信息的補集元素個數(shù),作為歐氏距離中某一維上的距離長度值.

比如書本A的出版年份是2015年,類別標(biāo)簽有:數(shù)據(jù)分析/Python編程/深度學(xué)習(xí),出版社是人民郵電出版社;書本B的出版年份是2018年,類別標(biāo)簽有: 數(shù)據(jù)分析/Matlab編程/深度學(xué)習(xí),出版社是人民郵電出版社.那么,A1-B1=3,A2-B2=1,A3-B3=0.這三個值用于計算A,B之間的歐式距離.

(2)計算歐式距離

假設(shè)項目有n種內(nèi)容信息,項目i對應(yīng)的第k種內(nèi)容信息記為ik,歐式距離的計算公式如式(10)所示.

以5本不同的書籍舉例,表1是這5本書對應(yīng)的歐氏距離初始矩陣.

表1 歐式距離初始矩陣

(3)凝聚式層次聚類

根據(jù)第(2)步得到的歐式距離矩陣,選擇距離最近的兩個簇b1,b5.合并b1,b5為簇{b1,b5},接著利用組平均準(zhǔn)則,選取其他簇與合并簇所有點之間距離的平均值作為下一步的鄰近值,更新歐式距離矩陣,如表2所示.

表2 迭代一次后的歐式距離矩陣

由表2合成新的合并簇{b2,b4},重復(fù)前面的步驟,繼續(xù)迭代更新矩陣.

由表3合成新的合并簇{b1,b5,b3},{b2,b4},最終聚類結(jié)果如圖2所示,可以直觀地找到目標(biāo)書籍的鄰近集(和目標(biāo)書籍在同一簇中的其他書籍),根據(jù)鄰近集書籍的評分預(yù)測目標(biāo)書籍的可能獲得的評分.

表3 迭代兩次后的歐式距離矩陣

圖2 書籍聚類結(jié)果樹圖示

評分預(yù)測:

采用凝聚式層次聚類的基于項目的協(xié)同過濾算法流程圖如圖3所示.

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

3.1 實驗數(shù)據(jù)集

本文選用GroupLens提供的網(wǎng)絡(luò)開源數(shù)據(jù)集MovieLens作為測試數(shù)據(jù)集[13],整個數(shù)據(jù)集包括了六千多個電影觀看者對3900多部電影的10萬多條評價.由三部分組成,包括用戶集,電影集和用戶-電影評分集.

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

本文采用Top-N推薦[14],對推薦結(jié)果的質(zhì)量用查準(zhǔn)率Precision、查全率Recall來衡量,計算方式如式(14)、(15).

其中,R(u)是訓(xùn)練集上基于用戶行為所給的推薦列表,T(u)是測試集上的用戶行為列表.

圖3 新項目冷啟動算法

3.3 實驗結(jié)果驗證

3.3.1 新用戶冷啟動算法驗證

本文實驗以MovieLens數(shù)據(jù)集為例,通過電影推薦驗證新算法的性能.將訓(xùn)練集和測試集的比例分為9:1,新用戶與老用戶的比例設(shè)為3:7,改變鄰居數(shù)K值在5～40之間,進(jìn)行多組實驗.

MovieLens的用戶集中包含了性別、年齡、職業(yè)三項用戶屬性,本文分析這三項特征信息,計算出用戶之間的特征差attr(u,v)如式(16).

本文的α、β、γ皆取1/3,滿足式(6)的條件.

對User.data的預(yù)處理:

(1)性別判定

MovieLens數(shù)據(jù)集中男性用戶性別表示為M,女性用戶性別表示為F.若兩用戶性別相同,sex取值為0,若不同,sex取值為1.

(2)年齡量化(表4)

(3)職業(yè)量化(表5)

表5 MovieLens用戶職業(yè)的量化

由此,式(14)中sex取值為0或1,age,occupation的取值為兩用戶特征值量化后差值的絕對值.

求得用戶特征差值attr(u,v)后,利用Sigmoid函數(shù),計算用戶u和用戶v之間的用戶特征信息相似度simattr(u,v),如式(8).

傳統(tǒng)協(xié)同過濾算法采用改進(jìn)的余弦相似度User-IIF算法[15],如式(17)所示,降低了用戶u和用戶v共同興趣列表中熱門物品對他們相似度的影響.

求得相似度后,計算預(yù)測評分,為用戶進(jìn)行推薦.進(jìn)行多次實驗,求得多組評估指標(biāo),并用Matlab進(jìn)行仿真,仿真結(jié)果如圖4、圖5所示.

圖4 改進(jìn)前后算法查全率隨K值的變化

圖4表示基于用戶的協(xié)同過濾算法在新用戶的情況下,新算法與傳統(tǒng)算法的查全率與鄰居數(shù)的變化關(guān)系圖.由圖可知,隨著鄰居數(shù)K值增加,系統(tǒng)的查全率呈上升趨勢,并且新算法的查全率高于傳統(tǒng)算法,說明新算法的檢索結(jié)果更有效.

圖5 改進(jìn)前后算法查準(zhǔn)率隨K值的變化

圖5表示基于用戶的協(xié)同過濾算法,在新用戶的情況下新算法與傳統(tǒng)算法查準(zhǔn)率與K值的關(guān)系.可以看出,新算法推薦結(jié)果的準(zhǔn)確率高于傳統(tǒng)算法.改進(jìn)后算法推薦精度更高,有效地改善了系統(tǒng)新用戶的冷啟動問題.

結(jié)合圖4、圖5發(fā)現(xiàn),在改進(jìn)后的User-based CF中,當(dāng)鄰居數(shù)取35時算法查全率最大,查準(zhǔn)率也比較高,算法推薦質(zhì)量較好.

3.3.2 新項目冷啟動算法驗證

本文提出的新項目的冷啟動算法采用了凝聚式層次聚類的思想,在MovieLens數(shù)據(jù)集上進(jìn)行實驗結(jié)果驗證,將訓(xùn)練集和測試集的比例分為9:1,新項目和老項目的比例為3:7.

Step 1.對movie.data的數(shù)據(jù)初始化處理.

(1)年份(year)關(guān)鍵詞: 直接表示為iy、jy.

(2)派別(genres)關(guān)鍵詞: 遍歷電影所屬的派別,若兩部電影有屬于一個相同的派別,則g值減1,否則,g值保持不變(g初始值為3),最后得到目標(biāo)電影和其他電影派別上的距離g值.

Step 2.歐式距離的計算.

在對電影的基本數(shù)據(jù)處理之后,計算電影之間的歐幾里德距離.歐式距離計算如式(10).

Step 3.層次聚類.

最后選取不同的鄰居數(shù)K值在5～40之間,進(jìn)行多次實驗比較加入新項目時,改進(jìn)前后基于項目的協(xié)同過濾算法在推薦精度上的變化,如圖6、圖7所示.

圖6 改進(jìn)前后ItemCF算法查全率隨K值的變化

圖7 改進(jìn)前后ItemCF算法查準(zhǔn)率隨K值的變化

傳統(tǒng)方法采用的相似度計算公式如式(18),減輕了熱門物品和其他眾多物品相似的可能性.

從圖6可以看出,采用了層次聚類的算法在查全率上優(yōu)于傳統(tǒng)算法,在鄰居數(shù)取10的時候,查全率達(dá)到最大值,在鄰居數(shù)取25～35之間時,查全率波動較大,并且呈下降趨勢.整體上看,改進(jìn)后的層次聚類算法推薦結(jié)果中被檢索到的更多,查全率更高.

圖7比較了采用凝聚式層次聚類的協(xié)同過濾和傳統(tǒng)基于項目的協(xié)同過濾算法在查準(zhǔn)率上的性能,由圖可見,算法的查準(zhǔn)率比較平穩(wěn),在加入了新項目后,改進(jìn)后算法的查準(zhǔn)率優(yōu)于傳統(tǒng)算法的值,表現(xiàn)出更好的推薦精度.

結(jié)合圖6、圖7,在改進(jìn)后的Item-based CF中,鄰居數(shù)取10時,算法的推薦性能較好.

4 結(jié)論

本文首先介紹了協(xié)同過濾算法以及算法的冷啟動問題,重點對新用戶和新項目的冷啟動問題進(jìn)行研究,提出了融合用戶信息模型的基于用戶的協(xié)同過濾算法和采用層次聚類的基于項目的協(xié)同過濾算法.具體研究工作如下:

(1)針對新用戶的冷啟動,算法提取了用戶個人特征信息,為用戶信息建模,調(diào)用Sigmoid函數(shù)求得基于用戶特征模型的相似度.

(2)對于新項目的冷啟動,算法提取項目的信息屬性,計算出歐式距離,采用凝聚式層次聚類的方法,找到目標(biāo)項目的鄰居項目,計算預(yù)測評分,完成推薦.

(3)選用網(wǎng)絡(luò)開源數(shù)據(jù)集MovieLens進(jìn)行實驗驗證,將新算法與傳統(tǒng)算法多次實驗對比.結(jié)果表明,在新用戶和新項目的情況下,新算法推薦結(jié)果的查全率、查準(zhǔn)率都有所提升,有效地緩解了傳統(tǒng)協(xié)同過濾算法的冷啟動問題,改善了推薦質(zhì)量.