基于多核學(xué)習(xí)的協(xié)同濾波算法

宋愷濤 彭甫镕 陸建峰

(南京理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院, 南京, 210094)

引 言

隨著互聯(lián)網(wǎng)的普及，中國(guó)的互聯(lián)網(wǎng)用戶(hù)數(shù)量已經(jīng)在2015年超過(guò)了9.7億?；ヂ?lián)網(wǎng)的快速發(fā)展，促使了移動(dòng)端電子商務(wù)的快速發(fā)展。越來(lái)越多快捷方便的基于移動(dòng)端的O2O(Online to offline)電子商務(wù)應(yīng)用出現(xiàn)。個(gè)性化推薦系統(tǒng)的出現(xiàn)為移動(dòng)互聯(lián)網(wǎng)的信息過(guò)載提供了幫助。個(gè)性化推薦系統(tǒng)幫助移動(dòng)端用戶(hù)快速尋找并向其推薦感興趣的商品、服務(wù)。因此，對(duì)個(gè)性化推薦技術(shù)的研究，也成為了當(dāng)前的一個(gè)研究熱點(diǎn)。

協(xié)同濾波[1]是目前推薦系統(tǒng)中主流的一種個(gè)性化推薦算法。1992年，Xerox公司在針對(duì)Palo Alto研究中心的信息重載問(wèn)題中設(shè)計(jì)了Tapestry，該系統(tǒng)首次引入了協(xié)同濾波的概念。1994年，GroupLens提出后，協(xié)同濾波得到大幅度發(fā)展，許多電子商務(wù)網(wǎng)站都開(kāi)始采用協(xié)同濾波算法為用戶(hù)提供個(gè)性化推薦服務(wù)?；趨f(xié)同濾波的推薦算法，相比于常規(guī)的基于關(guān)聯(lián)規(guī)則、基于內(nèi)容等推薦算法而言，擁有自動(dòng)分析興趣的優(yōu)點(diǎn)，能夠體現(xiàn)個(gè)性化推薦的優(yōu)點(diǎn)，結(jié)果直觀，易解釋。協(xié)同濾波可以分為基于用戶(hù)(User-based)的協(xié)同濾波和基于物品(Item-based)的協(xié)同濾波?；谟脩?hù)的協(xié)同濾波通過(guò)分析不同用戶(hù)來(lái)進(jìn)行推薦，該算法能夠挖掘用戶(hù)的潛在興趣。但是在目前的應(yīng)用場(chǎng)景下，用戶(hù)的數(shù)量規(guī)模日益龐大，使得基于用戶(hù)分析興趣的性能逐漸下降。Item-based協(xié)同濾波算法是對(duì)用戶(hù)的評(píng)分?jǐn)?shù)據(jù)進(jìn)行分析。該算法通過(guò)采用常規(guī)相似性度量來(lái)分析項(xiàng)目的最近鄰居，向預(yù)測(cè)評(píng)分值較高的用戶(hù)推薦相似項(xiàng)。傳統(tǒng)的協(xié)同濾波推薦算法，只需要用戶(hù)對(duì)項(xiàng)目的評(píng)分表就可以進(jìn)行推薦。在基于移動(dòng)端的電子商務(wù)系統(tǒng)中，通常還能夠利用到用戶(hù)的地理位置信息。Item-based協(xié)同濾波算法能夠不需要其他用戶(hù)的行為特征就可以進(jìn)行個(gè)性化推薦。而且，對(duì)于多數(shù)數(shù)據(jù)集，用戶(hù)數(shù)量都是遠(yuǎn)大于項(xiàng)目的數(shù)量，這使得Item-based協(xié)同濾波具有時(shí)間上的優(yōu)勢(shì)。但該方法同樣存在采用傳統(tǒng)相似性度量的缺陷，其只能獲取傳統(tǒng)方法的特點(diǎn)，并且伴隨數(shù)據(jù)規(guī)模的變大，會(huì)面臨著數(shù)據(jù)稀疏性問(wèn)題、冷啟動(dòng)問(wèn)題、系統(tǒng)擴(kuò)展性差等問(wèn)題。因此，尋找一種適應(yīng)性更好的相似性度量也成為了協(xié)同濾波的一個(gè)研究熱點(diǎn)。

1 核函數(shù)原理與設(shè)計(jì)

1.1 核函數(shù)原理

假設(shè)X是一個(gè)非空集合，H為一個(gè)內(nèi)積空間，φ為X到X的映射。如果函數(shù)K：X×X→R，滿(mǎn)足對(duì)于?x,x′∈X有K(x,x′)=<φ(x),φ(x′)>，則稱(chēng)K為核函數(shù)。因此，核函數(shù)可以看作是內(nèi)積概念的一個(gè)推廣。根據(jù)Hilbert-Schmidt原理[5]，任何滿(mǎn)足Mercer條件[6]的運(yùn)算，都可以作為核函數(shù)的內(nèi)積。

?K(x,x′)φ(x)φ(x′)dxdx′>0

(1)

Mercer條件是幫助核函數(shù)檢驗(yàn)其是否定義了一個(gè)特征空間的充分條件。其中，滿(mǎn)足Mercer條件的核函數(shù)為容許核。容許核函數(shù)滿(mǎn)足部分閉包性質(zhì)。容許核的正系數(shù)線性組合同樣也是容許核。

1.2 核函數(shù)設(shè)計(jì)

在基于項(xiàng)目的協(xié)同過(guò)濾推薦算法中，首先要計(jì)算項(xiàng)與項(xiàng)之間的相似度來(lái)尋找目標(biāo)項(xiàng)的最相似的鄰居集合。通常，相似性度量方法[7]，需要保證其度量值越大，相似程度越高的性質(zhì)。核函數(shù)通?？梢宰鳛闃颖驹谔卣骺臻g的相似性度量，因此，可以作為協(xié)同濾波算法的相似性度量方法。利用協(xié)同濾波算法中常用的傳統(tǒng)相似性度量方法和項(xiàng)目的地理位置信息，分別設(shè)計(jì)了皮爾遜核、余弦核，Jaccard核和徑向基核。

皮爾遜相關(guān)系數(shù)(Pearson correlation coefficient，PCC)[8]常用于度量?jī)蓚€(gè)向量之間的線性相關(guān)性。假設(shè)項(xiàng)x和項(xiàng)y的共同評(píng)分項(xiàng)為I，使用皮爾遜相關(guān)系數(shù)分析項(xiàng)之間的相似度公式為

(2)

余弦相關(guān)性(Cosine similarity)[8]將兩個(gè)向量的夾角余弦值來(lái)衡量向量之間的相似性。把n用戶(hù)對(duì)于項(xiàng)的評(píng)分看做一個(gè)n維向量，使用余弦相似度的公式

(3)

式中rx和ry表示項(xiàng)x與項(xiàng)y的評(píng)分向量?！ぁ硎鞠蛄康哪?。

Jaccard[8]相關(guān)系數(shù)是兩項(xiàng)的交集與并集的比值，相似度公式為

(4)

式中X與Y分別表示項(xiàng)x與項(xiàng)y的評(píng)分集。

徑向基核[9，10](Radial basis function kernel)，又稱(chēng)為RBF核，是一種常用核函數(shù)，通常定義為空間中任一點(diǎn)x到某一點(diǎn)到某一中心xc之間歐氏距離的單調(diào)函數(shù)

(5)

式中‖x-x′‖2是兩個(gè)特征之間的歐拉距離平方根，σ是自由參數(shù)。

在帶有地理位置信息的數(shù)據(jù)集上，通常可以獲取項(xiàng)的經(jīng)緯度，項(xiàng)x與項(xiàng)y的直接地理位置距離[10]的公式如下

dis(x,y)=R×acos(sinxlatsinylat+

cosxlatcosylatcos(xlng-ylng))

(6)

式中xlat，xlng，ylat，ylng分別表示項(xiàng)x與項(xiàng)y的緯度與經(jīng)度。由于不滿(mǎn)足其度量值越大，相似度越高的性質(zhì)，將項(xiàng)與項(xiàng)之間的直接地理位置距離以徑向基核的形式表示

(7)

式中dis(x,y)是式(4)所描述的項(xiàng)x與項(xiàng)y的直接地理位置距離，l是自由參數(shù)。

2 多核學(xué)習(xí)方法

2.1 合成核方法

在多核學(xué)習(xí)中，最優(yōu)核通常是采用多個(gè)基本核函數(shù)的線性組合方式。圖1為一個(gè)多核線性組合的示意圖。

圖1 多核函數(shù)線性組合過(guò)程Fig.1 Linear combination of multiple kernel function

本文采用了加權(quán)求和核[11，12]的方法，將皮爾遜核、余弦核、Jaccard核和徑向基核等進(jìn)行線性組合。其形式如下

(8)

式中simi對(duì)應(yīng)某種類(lèi)型的核函數(shù)，wi分別對(duì)應(yīng)各個(gè)核函數(shù)的核系數(shù),并確保各個(gè)核系數(shù)之和等于1，且每個(gè)核系數(shù)都大于等于0。

2.2 合成核的學(xué)習(xí)方法

度量用戶(hù)偏好商品i的概率采用評(píng)分加權(quán)推薦公式[13]來(lái)計(jì)算。該方法考慮了相似鄰居集的評(píng)分尺度的影響。公式如下

(9)

式中：SNi表示項(xiàng)i的K個(gè)最近鄰居集合；sim(i,j)是式(8)所設(shè)計(jì)的多核線性組合模型；rj,u是用戶(hù)u在項(xiàng)目j上的評(píng)分值。

本文采用隨機(jī)梯度下降[14]作為學(xué)習(xí)方法。隨機(jī)梯度下降是一種常用的最小化損失函數(shù)方法。隨機(jī)梯度下降通過(guò)對(duì)單樣本的損失誤差求解梯度，從而更新參數(shù)。其一次梯度迭代下降的時(shí)間復(fù)雜度較低。評(píng)估協(xié)同濾波算法的損失函數(shù)可以使用最小二乘誤差[15]。在本文中，其最小二乘誤差表示如下

(10)

式中：P(v,u)為式(9)中的評(píng)分方式；y(v,u)為觀察值。

損失函數(shù)的梯度求解主要是對(duì)式(10)進(jìn)行梯度求解，其求解過(guò)程如下：

(4)對(duì)于向量w的求導(dǎo)結(jié)果為

(5)因此整體損失函數(shù)的梯度值為

本文所采用的隨機(jī)梯度下降的學(xué)習(xí)方法，梯度的求解采用了損失函數(shù)梯度求解方法。因此基于多核學(xué)習(xí)的推薦系統(tǒng)算法過(guò)程如下：

輸入：評(píng)分表，測(cè)試集和初始多核系數(shù)w

輸出：推薦用戶(hù)-項(xiàng)目對(duì)

(1) 遍歷項(xiàng)目-用戶(hù)對(duì)(v,u)，對(duì)于當(dāng)前項(xiàng)目v，確定其鄰居集SN

(2) 對(duì)于當(dāng)前的項(xiàng)目-用戶(hù)對(duì)。采用章節(jié)3.2.1中的方法，求解梯度η，采用隨機(jī)梯度的方法更新多核系數(shù)w。隨機(jī)梯度的更新公式為：w(n+1)=wn-αη，其中α為步長(zhǎng)。

(3) 重復(fù)迭代(1)～(2)，直到損失函數(shù)變化趨于穩(wěn)定，獲取多核系數(shù)w，換到第(4)步

(4)遍歷訓(xùn)練集，采用訓(xùn)練得到的多核方程，重新計(jì)算每個(gè)項(xiàng)目的鄰居集。

(5)對(duì)于當(dāng)前項(xiàng)目v，采用式(9)計(jì)算一定范圍內(nèi)的每個(gè)用戶(hù)的期望評(píng)分，并選出評(píng)分前N高個(gè)用戶(hù)，進(jìn)行推薦。

(6)將推薦集合與測(cè)試集合進(jìn)行比較，評(píng)測(cè)推薦系統(tǒng)的性能。

由于每次更新核系數(shù)后，項(xiàng)目的鄰居集都會(huì)變化，使得直接在整體集上求單個(gè)項(xiàng)目的鄰居集的時(shí)間復(fù)雜度大。因此，本文預(yù)先處理單個(gè)項(xiàng)目在多個(gè)常規(guī)相似性度量上的鄰居集，從而在新參數(shù)w下尋找項(xiàng)目的鄰居集時(shí)只需要在常規(guī)相似性度量上的鄰居集合中搜索。而計(jì)算各個(gè)核函數(shù)的過(guò)程同樣需要一定時(shí)間復(fù)雜度。因此，在搜索常規(guī)度量鄰居集合的同時(shí)，將項(xiàng)目與鄰居集的相似性度量值保存，方便在多核學(xué)習(xí)過(guò)程中直接使用，避免重復(fù)計(jì)算。

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

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

為了驗(yàn)證本文所提出的方法，實(shí)驗(yàn)中使用大眾點(diǎn)評(píng)數(shù)據(jù)集和Foursquare兩個(gè)真實(shí)數(shù)據(jù)集進(jìn)行驗(yàn)證。

大眾點(diǎn)評(píng)數(shù)據(jù)集選用了某地區(qū)店鋪的用戶(hù)評(píng)價(jià)信息以及店鋪地理位置。用戶(hù)對(duì)店鋪的喜好采用評(píng)分形式。數(shù)據(jù)集僅有0.148 9%的用戶(hù)-店鋪對(duì)有評(píng)分項(xiàng)。

表1 大眾點(diǎn)評(píng)數(shù)據(jù)集信息

Foursquare數(shù)據(jù)集選用了新加坡地區(qū)2010年8月到2011年7月用戶(hù)的簽到數(shù)據(jù)。將用戶(hù)是否有簽到行為作為評(píng)分項(xiàng)。由于Foursquare數(shù)據(jù)集是屬于二進(jìn)制數(shù)據(jù)集，因此，各個(gè)核的效果在Foursquare數(shù)據(jù)集上會(huì)出現(xiàn)較大波動(dòng)。

表2 Foursquare數(shù)據(jù)集信息

本文將數(shù)據(jù)集按照4∶1的比例劃分訓(xùn)練集和測(cè)試集，進(jìn)行5-折交叉驗(yàn)證。

3.2 推薦評(píng)分標(biāo)準(zhǔn)

在獲取最優(yōu)多核系數(shù)w后，將采用式(9)計(jì)算評(píng)分，進(jìn)行Top-N推薦。對(duì)于推薦性能的評(píng)價(jià)，在推薦系統(tǒng)中，通常會(huì)選用F1值(F1Score)[16]作為標(biāo)準(zhǔn)，因?yàn)镕1值可以同時(shí)顧及二分類(lèi)推薦模型中準(zhǔn)確率(Precision)和召回率(Recall)。

準(zhǔn)確率：推薦命中的個(gè)數(shù)占推薦商品總的個(gè)數(shù)比率。

(11)

召回率：用戶(hù)所喜歡的商品最終被推薦出來(lái)的比率。

(12)

F1值是準(zhǔn)確率和召回率的調(diào)和平均數(shù)，公式為

(13)

圖2 核系數(shù)目標(biāo)損失函數(shù)下降 Fig．2 Descent of kernel factor cost function

式中：TP表示推薦集合中正類(lèi)的個(gè)數(shù)，F(xiàn)P表示推薦集合中負(fù)類(lèi)的個(gè)數(shù)；FN表示沒(méi)有在推薦集合中的正類(lèi)個(gè)數(shù)。

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

在實(shí)驗(yàn)中，采用平均絕對(duì)誤差(Mean absolute difference, MAE)[17]來(lái)評(píng)估多核學(xué)習(xí)過(guò)程中的損失情況。平均絕對(duì)誤差是指所有單樣本的觀察值與算術(shù)預(yù)測(cè)值的絕對(duì)偏差之和的平均值,其公式為

(14)

式中：fi表示預(yù)測(cè)值，yi代表觀察值。

由于數(shù)據(jù)集的規(guī)模較大，計(jì)算整體損失函數(shù)的時(shí)間較多。因此，在核系數(shù)學(xué)習(xí)過(guò)程中，采用批次處理的方法，進(jìn)行梯度上的更新。在本文的實(shí)驗(yàn)中，設(shè)置迭代計(jì)算間隔次數(shù)為1 000次，步長(zhǎng)α為0.00 002。觀察圖2，在60次左右的損失函數(shù)計(jì)算后，即大約60 000次左右的學(xué)習(xí)迭代，整體損失函數(shù)下降逐漸趨于穩(wěn)定。將最后趨于穩(wěn)定的核系數(shù)作為多核方程進(jìn)行協(xié)同濾波推薦。

本文將基于多核學(xué)習(xí)的協(xié)同濾波算法與采用常規(guī)相似性度量方法，包括了Jaccard核、余弦核、徑向基核這3種方法，以及平均加權(quán)常規(guī)相似性度量方法的協(xié)同濾波算法進(jìn)行比較。進(jìn)行Top-N推薦時(shí)，選擇不同的Top-N系數(shù)，Top-N的范圍設(shè)置在10%～25%，采用式(11)的F1值作為評(píng)分標(biāo)準(zhǔn)。

圖3 大眾點(diǎn)評(píng)數(shù)據(jù)集實(shí)驗(yàn)結(jié)果 圖4 Foursquare實(shí)驗(yàn)結(jié)果

大眾點(diǎn)評(píng)的數(shù)據(jù)集的最近鄰個(gè)數(shù)設(shè)置為30,徑向基核的參數(shù)l設(shè)置為1。通過(guò)觀察圖3，在大眾點(diǎn)評(píng)數(shù)據(jù)集上，基于多核學(xué)習(xí)的協(xié)同濾波算法相比于采用傳統(tǒng)相似性度量方法的協(xié)同濾波算法，F(xiàn)1值提升了3.973%。觀察圖4，受限于Foursquare數(shù)據(jù)集的二進(jìn)制數(shù)據(jù)，使得在Top-N較小時(shí)，效果不是很明顯，在Top-N大于20%的時(shí)候，基于多核學(xué)習(xí)的協(xié)同濾波算法相比于采用傳統(tǒng)相似性度量方法的協(xié)同濾波算法的推薦性能有了整體的提升，平均F1值相比于采用傳統(tǒng)相似性度量方法的協(xié)同濾波算法提升了6.523%。說(shuō)明了基于多核學(xué)習(xí)的協(xié)同濾波算法擁有更好的推薦性能。

4 結(jié)束語(yǔ)

本文提出了一種基于多核學(xué)習(xí)的協(xié)同濾波算法，并給出學(xué)習(xí)方法的推導(dǎo)。該方法相比于采用傳統(tǒng)相似性度量的協(xié)同濾波算法而言，具有選擇最優(yōu)核的能力，能夠自動(dòng)學(xué)習(xí)核系數(shù)來(lái)提升性能，并體現(xiàn)各個(gè)核函數(shù)對(duì)實(shí)驗(yàn)結(jié)果的影響。在大眾點(diǎn)評(píng)數(shù)據(jù)集和Foursquare數(shù)據(jù)集上的實(shí)驗(yàn)表明，本文所提出的基于多核學(xué)習(xí)的協(xié)同濾波算法提升了推薦性能，具有有效性。但是，核系數(shù)的初始化選擇以及核函數(shù)的組合，對(duì)實(shí)驗(yàn)結(jié)果會(huì)有很大的影響。如何針對(duì)于數(shù)據(jù)集，選擇核系數(shù)與核函數(shù)，仍是多核學(xué)習(xí)中的難點(diǎn)。

參考文獻(xiàn):

[1] Badrul Sarwar． Item-based collaborative filtering recommendation algorithms[C]∥Proceedings of the 10thInternational Conference on World Wide Web. New York：WWW10, 2001:285-295．

[2] Suykens J K． Least squares support vector machine classifiers[J]. Neural Processing Letters,1993,9(3):293-300.

[3] 汪洪橋．多核學(xué)習(xí)方法[J].自動(dòng)化學(xué)報(bào),2010,36(8):1037-1050．

Wang Hongqiao. On multiple kernel learning methods[J].Acta Automatic Sinica,2010,36(8): 1037-1050．

[4] Meirom E A．Nuc-MKL:A convex approach to non linear multiple kernel learning[J]. AISTATS, 2016, 51:610-619．

[5] Li Liyan． Gene networks identification using independence measurement based on the Hilbert space[D].Hangzhou:Hangzhou Dianzi University, 2014．

[6] Lyu Siwei． Mercer kernels for object recognition with local features[J]. CVPR,2005,2:1063-6919．

[7] Liu Haifeng． A new user similarity model toimprove the accuracy of collaborative filtring[J]. Knowledge-Based Systems, 2014,56: 156-166．

[8] Ekstrand M D, Riedl J T, Konstan J A.Collaborative filtering recommender system [J]. Foundations and Trends in Human-Computer Interaction,2010,4(2):81-173．

[9] Chung Kai-Min． Radius margin bounds for support vector machines with the RBF kernel[J]. Neural Computation,2003,15(11):2643-2681．

[10] 奚吉,趙力,左加闊.基于改進(jìn)多核學(xué)習(xí)的語(yǔ)音情感識(shí)別算法[J].數(shù)據(jù)采集與處理,2014,29(5):730-734．

Xi Ji, Zhao Li, Zuo Jiahuo. Speech emotion recognition based on modified multiple kernel learning algorithm[J]. Journal of Data Acquisition and Processing, 2014, 29(5):730-734.

[11] 王國(guó)勝.核函數(shù)的性質(zhì)及其構(gòu)造方法[J].計(jì)算機(jī)科學(xué),2006,33(6):172-178．

Wang Guosheng. Properties and construction methods of kernel in support vector machine[J]. Computer Science,2006,33(6):172-178．

[12] Lu Yanting． Research and application of clustering and hierarchical classification algorithms based on multiple kernel learning[D]. Nanjing:Nanjing University of Science and Technology, 2013.

[13] 王付強(qiáng),基于位置的非對(duì)稱(chēng)相似性度量的協(xié)同過(guò)濾推薦算法[J].計(jì)算機(jī)應(yīng)用,2016,36(1):171-174．

Wang Fuqiang. Location-based asymmetric similarity for collaborative filtering recommendation algorithm[J]. Journal of Computer Applications, 2016, 36(1):171-174．

[14] Léon Bottou． Large-scale machine learning with stochastic gradient descent[C]∥19th International Conference on Computational Statistics.Paris: Proceedings of COMPSTAT,2010:177-186．

[15] York D． Least squares fitting of a straight line with correlated errors [J]. Earth and Planetary Science Letters,1968,5:320-324．

[16] Yang Yiming． A re-examination of text categorization methods[C]∥the 22nd Annual International ACM SIGIR Conference. USA:SIGIR，1999:42-49．

[17] Vassiliadis S. The sum-absolute-difference motion estimation accelerator[C]∥Proceedings of the 24thEuromicro Conference. Germany: Euromicro Conference,1998:559-566．