結(jié)合矩陣分解和延伸相似度的最近鄰算法

李儉兵，劉栗材

(1.重慶郵電大學(xué) 通信新技術(shù)應(yīng)用研究中心，重慶 400065；2.重慶信科設(shè)計(jì)有限公司，重慶 400021)

0 引 言

傳統(tǒng)推薦系統(tǒng)[1,2]主要有協(xié)同過(guò)濾推薦、基于內(nèi)容的推薦、混合推薦[3]。協(xié)同過(guò)濾算法在推薦領(lǐng)域?yàn)樽罨就扑]算法。傳統(tǒng)的協(xié)同過(guò)濾推薦算法可以分為基于用戶(hù)的協(xié)同過(guò)濾和基于產(chǎn)品的協(xié)同過(guò)濾[4]。目前在協(xié)同過(guò)濾推薦模型中使用得最廣泛的算法是最近鄰方法[5,6]。然而最近鄰方法有數(shù)據(jù)稀疏、個(gè)性化低和計(jì)算負(fù)荷量大等特點(diǎn)[7]，大大降低個(gè)性化推薦準(zhǔn)確性。最近鄰算法計(jì)算的對(duì)象是高維矩陣，需要大量的運(yùn)算時(shí)間且精確度低。文獻(xiàn)[3]中提出用一種聚類(lèi)算法優(yōu)化K近鄰協(xié)同過(guò)濾算法來(lái)提高精確度。文獻(xiàn)[8]利用矩陣分解技術(shù)和KNN算法提出了擴(kuò)展濾波算法，簡(jiǎn)化了矩陣，增強(qiáng)用戶(hù)影響力。當(dāng)然在推薦系統(tǒng)中，相似度也非常重要[9]。文獻(xiàn)[10]中提出一種基于加權(quán)雙邊網(wǎng)絡(luò)和協(xié)同過(guò)濾的資源分配原則來(lái)計(jì)算用戶(hù)相似度，從而提高推薦準(zhǔn)確度。

針對(duì)最近鄰算法依賴(lài)完全匹配，導(dǎo)致算法犧牲推薦系統(tǒng)的覆蓋率和準(zhǔn)確度。本文在KNN算法基礎(chǔ)上提出了結(jié)合降維的最近鄰算法(K nearest neighbor algorithm of dimensionality reduction，KNN-DR)來(lái)有效解決計(jì)算式復(fù)雜度高和推薦效果大眾化的特點(diǎn)。實(shí)驗(yàn)結(jié)果表明，KNN-DR算法與KNN算法相比可以更好地實(shí)現(xiàn)精確預(yù)測(cè)。

1 相關(guān)問(wèn)題和工作

1.1 相關(guān)問(wèn)題

本文以電影推薦網(wǎng)站為例，網(wǎng)站的用戶(hù)行為有數(shù)據(jù)復(fù)雜，需求多樣性等特點(diǎn)。在不知道具體的影片名的情況上，電影推薦網(wǎng)站傳統(tǒng)的推薦方法有如下幾種：第一種是通過(guò)用戶(hù)檢索出關(guān)鍵字，網(wǎng)站給出這系列所有電影名，然后用戶(hù)查詢(xún)自己喜歡的電影；第二種針對(duì)所有的用戶(hù)都推薦同一個(gè)熱門(mén)排行榜；另外一種是根據(jù)用戶(hù)觀(guān)影記錄，推薦之前觀(guān)看的類(lèi)似影片。

以上的推薦算法雖然取得不錯(cuò)的效果，但是效率低和個(gè)性化效果差。本文先用矩陣分解的方法降維,加快運(yùn)算效率。然后用相似度法將最近的鄰里的數(shù)據(jù)進(jìn)行加權(quán)計(jì)算。本文不僅考慮了運(yùn)算速度，且融合了更多隱式因子，使個(gè)性化推薦更加精準(zhǔn)。根據(jù)KNN-DR方法形成用戶(hù)鄰里關(guān)系如圖1如示。

圖1 用戶(hù)鄰里關(guān)系

1.2 相似性度量值

(1)皮爾遜相似度

協(xié)方差的概念反映出兩個(gè)隨機(jī)變量的相關(guān)程度，如果兩個(gè)變量同時(shí)變大或者變小，就說(shuō)明這兩個(gè)變量的協(xié)方差為正數(shù),相反為負(fù)數(shù)

(1)

式中：ρ(x,y)表示皮爾遜相關(guān)系數(shù)，分子為x和y的協(xié)方差，分母為x的標(biāo)準(zhǔn)差乘以y的標(biāo)準(zhǔn)差。μx和μy分別是用戶(hù)x和y評(píng)分的平均值。皮爾遜相關(guān)系數(shù)其實(shí)在幾何上可理解為夾角的余弦值。

(2)延伸相似度

用戶(hù)間差異對(duì)推薦也很重要,反映了電影推薦系統(tǒng)的質(zhì)量。針對(duì)同一部電影，在計(jì)算用戶(hù)間差異值的時(shí)候，引入了評(píng)分相對(duì)值，盡可能降低由于喜好風(fēng)格不同，使評(píng)分相差太大[11,12]。用戶(hù)可以從1到5的5個(gè)整數(shù)中選擇相應(yīng)的分?jǐn)?shù)表達(dá)對(duì)影片的喜愛(ài)程度。我們從數(shù)據(jù)集中可以看出，同一部電影,不同用戶(hù)給出的評(píng)分差距太懸殊。所以有式(2)

(2)

當(dāng)用戶(hù)x的評(píng)分Gx和用戶(hù)y的Gy不相等時(shí)使用上式，當(dāng)Gx和Gy相等時(shí)，M(x,y)等于1。相對(duì)值M(x,y)的范圍在[0.25,1]。在用戶(hù)間評(píng)分差值達(dá)到最大的4時(shí)(M為0.25)，認(rèn)為相對(duì)值最低；評(píng)分差值達(dá)到1時(shí)(M為1)，相對(duì)值最高。因此，在這范圍內(nèi)越大，相對(duì)值越高。不同用戶(hù)喜歡不同風(fēng)格的影片，為了計(jì)算他們間的相同觀(guān)影風(fēng)格，引入了相同性概念

(3)

式中：MS(x,y)表示用戶(hù)x和y的相同性。w(·)表示用戶(hù)觀(guān)看的影片。為了使指標(biāo)分布在(0,1)上，上式進(jìn)行了變化。公式如式(4)

(4)

把用戶(hù)間的這些隱式關(guān)系引入進(jìn)推薦系統(tǒng)中,使評(píng)分相對(duì)值和CMS(x,y)相加再與皮爾遜相似度結(jié)合，得出了用戶(hù)間的延伸相似度[13]

RS(x,y)=(M(x,y)+CMS(x,y))ρ(x,y)

(5)

在時(shí)間跨度比較大的情況下，時(shí)間可能改變興趣

(6)

又

(7)

sim(i,j)為產(chǎn)品的相似度，|N(·)|為喜歡產(chǎn)品i或j的用戶(hù)數(shù)，N(j)∩N(i)是同時(shí)喜歡產(chǎn)品i和j的用戶(hù)數(shù)，t(xj)是用戶(hù)x對(duì)物品j觀(guān)看的時(shí)間，t(0)是用戶(hù)x觀(guān)看物品j時(shí)距離當(dāng)前時(shí)間最近的一次，β是時(shí)間衰減參數(shù)，需要根據(jù)不同的數(shù)據(jù)集選擇合適的值。P(x,j)表示用戶(hù)x對(duì)產(chǎn)品j的興趣。最后通過(guò)加權(quán)計(jì)算得出[14]

(8)

2 KNN-DR算法流程

在大數(shù)據(jù)時(shí)代，我們可以獲得大量的數(shù)據(jù)，但是大部分都是冗余數(shù)據(jù)。融合了KNN協(xié)同過(guò)濾和矩陣分解技術(shù)。在運(yùn)算時(shí)降低搭建的特征空間維度，提高運(yùn)行效率和解決數(shù)據(jù)稀疏性。KNN-DR算法在傳統(tǒng)推薦算法上把多種隱式信息融合進(jìn)模型，進(jìn)一步提高推薦精度，形成了具有針對(duì)性的個(gè)性化推薦。

2.1 KNN協(xié)同過(guò)濾

KNN的主要思路是如果一個(gè)樣本在特征空間中的k個(gè)最相似樣本中大多數(shù)屬于某一個(gè)類(lèi)別,則該樣本也屬于這個(gè)樣本。大多數(shù)基于協(xié)同過(guò)濾的推薦系統(tǒng),通過(guò)選取相似度高的k個(gè)鄰居。根據(jù)它們來(lái)預(yù)測(cè)某一用戶(hù)對(duì)某產(chǎn)品的評(píng)分分?jǐn)?shù)。表達(dá)式如下

(9)

2.2 多特征融合型矩陣分解

又考慮網(wǎng)站給出用戶(hù)對(duì)影片的評(píng)分值，所以在構(gòu)造函數(shù)時(shí)需要增加幾項(xiàng)

(10)

μ是整個(gè)訓(xùn)練中全局評(píng)分均值，bi表示影片評(píng)分平均值，bu表示用戶(hù)u評(píng)分相對(duì)均值u的偏見(jiàn)值。

(11)

給用戶(hù)推薦主題，推薦系統(tǒng)會(huì)給出很多關(guān)鍵詞，通常用戶(hù)對(duì)排名靠前的更加關(guān)注。影片名里面包括了很多關(guān)鍵字，每一個(gè)關(guān)鍵字對(duì)應(yīng)一個(gè)(term frequency-inverse document frequency，TF-IDF)權(quán)重，關(guān)鍵字是對(duì)用戶(hù)自己的個(gè)性或興趣做出的描述[15]。對(duì)于影片名關(guān)鍵詞提取，由于影片名很短，使用TF-IDF存在稀疏性較大的問(wèn)題。為了提高推薦的準(zhǔn)確率，在上面的基礎(chǔ)上再對(duì)提取的標(biāo)簽集進(jìn)行擴(kuò)展，把一個(gè)標(biāo)簽的相似標(biāo)簽加入這一集合中。通過(guò)相似度計(jì)算公式計(jì)算各個(gè)標(biāo)簽的相似度，選取相關(guān)的標(biāo)簽為一個(gè)集合。這樣就解決了稀疏性。然后將這些標(biāo)簽集里分別進(jìn)行聚合排序，將排序結(jié)果中前面的標(biāo)簽作為某同一類(lèi)型電影,推薦給用戶(hù)

(12)

K(·)為用戶(hù)u的關(guān)鍵字，W(·,m)表示關(guān)鍵字m的權(quán)重，數(shù)值越大，表示u和m的相關(guān)度越高。y(m)為文檔總數(shù)與詞m所出現(xiàn)文件數(shù)比值的對(duì)數(shù)值。

所以，真實(shí)值和預(yù)測(cè)值的總誤差平方和為

(13)

為了防止過(guò)擬合，對(duì)M進(jìn)行正則化，添加處罰項(xiàng)，得

(14)

2.3 優(yōu) 化

通過(guò)以上的分解，可以分別得到P、Q矩陣。根據(jù)基矩陣P，計(jì)算得到目標(biāo)用戶(hù)評(píng)分向量G對(duì)基矩陣P的投影向量q。再計(jì)算出投影向量q與投影矩陣Q各行間的歐氏距離，并對(duì)其設(shè)定一個(gè)閾值，將其中距離最小的前k個(gè)用戶(hù)組成與目標(biāo)用戶(hù)的最近的鄰里集合。通過(guò)這種投影的方式，在損失一些精度情況下可以加快計(jì)算速度

(15)

dist(·)表示歐式距離。在歐式距離計(jì)算中，取值范圍會(huì)很大，一般通過(guò)如下方式歸一化

(16)

最后再用上文提到的Px,j將最近集合中的數(shù)據(jù)進(jìn)行加權(quán)計(jì)算，然后排序進(jìn)行推薦。

2.4 時(shí)間復(fù)雜度

在KNN訓(xùn)練中計(jì)算復(fù)雜度與訓(xùn)練集中的數(shù)據(jù)為正比，所以時(shí)間復(fù)雜度為O(n*m)，n為訓(xùn)練數(shù)據(jù)集的大小，m為維數(shù)[16]。KNN算法每次要計(jì)算目標(biāo)用戶(hù)與其它用戶(hù)的距離，所以增加了訓(xùn)練的時(shí)間復(fù)雜度。但是在KNN-DR算法中，可以通過(guò)對(duì)高維數(shù)據(jù)進(jìn)行降維，減小空間特征維數(shù)，從而提高計(jì)算速度。假設(shè)原始訓(xùn)練數(shù)據(jù)集中有n個(gè)m維向量，對(duì)k個(gè)m維向量進(jìn)行分類(lèi)。則傳統(tǒng)的KNN算法時(shí)間復(fù)雜度為O(k*m*n+k*n*lg(n))，但是KNN-DR為O(k*m*n1+k*n1*lg(n1)+n*lg(n)+m*n)，n1是通過(guò)多特征型矩陣分解得到的，其值小于原始訓(xùn)練集中n，所以傳統(tǒng)的KNN模型時(shí)間復(fù)雜度大于KNN-DR模型。

3 實(shí)驗(yàn)分析和仿真

本文首先將已有的算法和本文研究的算法對(duì)比，結(jié)合查全率和準(zhǔn)確率進(jìn)行效果比較。

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

本文數(shù)據(jù)集是來(lái)自Netflix(http://data-ju.cn/Dataju/web/datasetInstanceDetail/116)。文件“Train-set.ar”包含17 770個(gè)文件，分別代表順序?yàn)?到17770的MovieID。每一個(gè)MovieID后面跟著觀(guān)看且評(píng)分的客戶(hù)ID，等級(jí)[1,5]，評(píng)價(jià)日期。文件“movie-titles.txt”，格式如下：Mo-vie-ID，Year of Release，標(biāo)題。Year of Release對(duì)應(yīng)發(fā)行日期，從1890到2005。標(biāo)題是Netflix的電影標(biāo)題。

3.2 推薦評(píng)定指標(biāo)

3.2.1 RMSE評(píng)估準(zhǔn)則

RMSE全稱(chēng)為root-mean-square-error，均方根誤差。它是觀(guān)測(cè)值與真值的偏差的平方和觀(guān)測(cè)次數(shù)n比值的平方根。均方根誤差能很好反映出精密度

(17)

xobs,i表示用戶(hù)對(duì)產(chǎn)品i的真實(shí)評(píng)分，xmodel,i為用戶(hù)對(duì)i的預(yù)測(cè)評(píng)分。下面比較文中提到的幾種算法。橫軸train ration, X為選取的訓(xùn)練集大小與整個(gè)數(shù)據(jù)集大小的比值,如圖2所示。

圖2 RMSE和覆蓋率的變化(影片數(shù)據(jù))

train ration, X為選取的訓(xùn)練集大小與整個(gè)數(shù)據(jù)集的比值。部分算法出現(xiàn)相近的結(jié)果，所以一些研究人員提出了算法的準(zhǔn)確性存在限制。這個(gè)限制將與用戶(hù)的興趣變化有關(guān)。鑒于一個(gè)人在不同場(chǎng)合對(duì)某個(gè)產(chǎn)品的意見(jiàn)可以每次都能給出不同的評(píng)分，所以算法的預(yù)測(cè)總是會(huì)受到這個(gè)影響。雖然不否認(rèn)這個(gè)限制的存在，但在本實(shí)驗(yàn)3種算法結(jié)果相比之下，算法所遭受的最大限制是缺乏信息。預(yù)測(cè)的準(zhǔn)確性受到從評(píng)分矩陣(影片數(shù)據(jù)里含大量評(píng)分信息)可以獲得的信息量限制。而這進(jìn)一步受到矩陣中實(shí)際存在的信息(特征)的限制。其實(shí)如前所述,訓(xùn)練集中的評(píng)分比例越大(信息量的增加)，結(jié)果就會(huì)改善。實(shí)驗(yàn)結(jié)果表明，過(guò)程中融合了更多隱式因子來(lái)增強(qiáng)個(gè)性化的KNN-DR算法在實(shí)驗(yàn)中比其它算法效果好。

3.2.2 F1評(píng)定指標(biāo)

為了評(píng)估top-N推薦系統(tǒng)效果，經(jīng)常使用的兩個(gè)指標(biāo)是召回率(recall)和準(zhǔn)確率(precision)

(18)

(19)

然而，這兩個(gè)指標(biāo)經(jīng)常矛盾。增加N值，召回率增加，但是準(zhǔn)確率降低。實(shí)際中，使用F1值作為指標(biāo)平均值，表達(dá)式如式(20)

(20)

第二個(gè)實(shí)驗(yàn)選取KNN的高維度處理模型與KNN-DR算法的低維度模型進(jìn)行效果對(duì)比。首先選取合適的X值。需要注意的是，X的取值不同是用于確定不同模型對(duì)訓(xùn)練集稀疏度的敏感度。

運(yùn)行KNN和KNN-DR情況下實(shí)驗(yàn)，隨著不同的X值，計(jì)算出F1度量值。圖3橫軸代表X，縱軸代表F1值。通過(guò)圖3的實(shí)驗(yàn)結(jié)果，可以得出電影數(shù)據(jù)的最佳X值是取0.8。

圖3 最優(yōu)X的值確定(影片數(shù)據(jù))

我們通過(guò)算法得出top-N，N為10。且通過(guò)上面圖表確定了X為0.8時(shí)可以使推薦效果達(dá)到最佳。把KNN的高維度模型與KNN-DR算法的低維度模型進(jìn)行對(duì)比。

圖4的橫軸表示維度的數(shù)量，縱軸表示F1值。通過(guò)實(shí)驗(yàn)結(jié)果表明，KNN-DR算法在KNN的基礎(chǔ)上推薦效果有了明顯的提高。

圖4 Top-10推薦結(jié)果(影片數(shù)據(jù))

圖5的實(shí)驗(yàn)選取了訓(xùn)練集大小與整個(gè)數(shù)據(jù)集的比值分別為0.5，0.6，0.7，0.8，0.9進(jìn)行對(duì)比訓(xùn)練時(shí)間。隨著訓(xùn)練數(shù)據(jù)的增加，時(shí)間差也逐漸增加，說(shuō)明KNN-DR算法通過(guò)降維的方法對(duì)運(yùn)算速度有提高。

圖5 兩種算法訓(xùn)練時(shí)間對(duì)比

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

本文以電影網(wǎng)站中推薦系統(tǒng)為背景，將傳統(tǒng)的KNN算法與矩陣分解相結(jié)合，提出了KNN-DR算法。與傳統(tǒng)的KNN算法相比，KNN-DR算法通過(guò)降維的方法加快了運(yùn)算速度，然后在低維空間形成鄰里，專(zhuān)注分析給定鄰里用戶(hù)喜歡的產(chǎn)品。并且這種算法包含了對(duì)隱式因子的考慮，通過(guò)延伸相似度和皮爾遜相似度來(lái)加權(quán)計(jì)算得出相似度計(jì)算式，最后再排序推薦，提高推薦精確度。實(shí)驗(yàn)結(jié)果表明了這種算法的可行性和有效性。在不同的評(píng)分推薦系統(tǒng)背景下，我們可以替換計(jì)算式中的權(quán)重和關(guān)系系數(shù)的大小，來(lái)實(shí)現(xiàn)個(gè)性化推薦。在這里，我們學(xué)習(xí)潛在特征向量的同時(shí)考慮用從數(shù)據(jù)中學(xué)習(xí)的任意函數(shù)替換內(nèi)積。目前有很多高效的算法,如神經(jīng)網(wǎng)絡(luò)算法、GBDT(gradient boosting decision tree)等。如何利用神經(jīng)網(wǎng)絡(luò)來(lái)代替上文用戶(hù)鄰里關(guān)系網(wǎng)，通過(guò)優(yōu)化固定網(wǎng)絡(luò)的潛在特征來(lái)學(xué)習(xí)，是未來(lái)要研究的課題之一。