邵 煜,謝穎華

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

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

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

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

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

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

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

1.1 冷啟動(dòng)問(wèn)題

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

1.2 冷啟動(dòng)問(wèn)題的研究現(xiàn)狀

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

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

2 相似度的計(jì)算方法

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

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

余弦相似度:

歐幾里德距離:

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

其中,Ru,i,Rj,i分別代表用戶u和用戶j對(duì)項(xiàng)目i的評(píng)分,分別代表用戶u和j的評(píng)分平均值,Iu,j是用戶u,j的共同評(píng)分項(xiàng)目集合.

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

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

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

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

其中,λi滿足:

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

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

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

圖1 新用戶冷啟動(dòng)算法

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

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

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

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

對(duì)于數(shù)值類信息,可直接用于歐式距離計(jì)算.對(duì)非數(shù)值類信息,計(jì)算項(xiàng)目屬性信息的補(bǔ)集元素個(gè)數(shù),作為歐氏距離中某一維上的距離長(zhǎng)度值.

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

(2)計(jì)算歐式距離

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

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

表1 歐式距離初始矩陣

(3)凝聚式層次聚類

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

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

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

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

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

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

評(píng)分預(yù)測(cè):

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

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

3.1 實(shí)驗(yàn)數(shù)據(jù)集

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

3.2 實(shí)驗(yàn)評(píng)價(jià)標(biāo)準(zhǔn)

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

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

圖3 新項(xiàng)目冷啟動(dòng)算法

3.3 實(shí)驗(yàn)結(jié)果驗(yàn)證

3.3.1 新用戶冷啟動(dòng)算法驗(yàn)證

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

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

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

對(duì)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的取值為兩用戶特征值量化后差值的絕對(duì)值.

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

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

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

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

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

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

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

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

3.3.2 新項(xiàng)目冷啟動(dòng)算法驗(yàn)證

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

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

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

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

Step 2.歐式距離的計(jì)算.

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

Step 3.層次聚類.

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

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

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

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

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

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

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

4 結(jié)論

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

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

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

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