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

李儉兵，劉栗材

(1.重慶郵電大學 通信新技術應用研究中心，重慶 400065；2.重慶信科設計有限公司，重慶 400021)

0 引 言

傳統推薦系統[1,2]主要有協同過濾推薦、基于內容的推薦、混合推薦[3]。協同過濾算法在推薦領域為最基本推薦算法。傳統的協同過濾推薦算法可以分為基于用戶的協同過濾和基于產品的協同過濾[4]。目前在協同過濾推薦模型中使用得最廣泛的算法是最近鄰方法[5,6]。然而最近鄰方法有數據稀疏、個性化低和計算負荷量大等特點[7]，大大降低個性化推薦準確性。最近鄰算法計算的對象是高維矩陣，需要大量的運算時間且精確度低。文獻[3]中提出用一種聚類算法優化K近鄰協同過濾算法來提高精確度。文獻[8]利用矩陣分解技術和KNN算法提出了擴展濾波算法，簡化了矩陣，增強用戶影響力。當然在推薦系統中，相似度也非常重要[9]。文獻[10]中提出一種基于加權雙邊網絡和協同過濾的資源分配原則來計算用戶相似度，從而提高推薦準確度。

針對最近鄰算法依賴完全匹配，導致算法犧牲推薦系統的覆蓋率和準確度。本文在KNN算法基礎上提出了結合降維的最近鄰算法(K nearest neighbor algorithm of dimensionality reduction，KNN-DR)來有效解決計算式復雜度高和推薦效果大眾化的特點。實驗結果表明，KNN-DR算法與KNN算法相比可以更好地實現精確預測。

1 相關問題和工作

1.1 相關問題

本文以電影推薦網站為例，網站的用戶行為有數據復雜，需求多樣性等特點。在不知道具體的影片名的情況上，電影推薦網站傳統的推薦方法有如下幾種：第一種是通過用戶檢索出關鍵字，網站給出這系列所有電影名，然后用戶查詢自己喜歡的電影；第二種針對所有的用戶都推薦同一個熱門排行榜；另外一種是根據用戶觀影記錄，推薦之前觀看的類似影片。

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

圖1 用戶鄰里關系

1.2 相似性度量值

(1)皮爾遜相似度

協方差的概念反映出兩個隨機變量的相關程度，如果兩個變量同時變大或者變小，就說明這兩個變量的協方差為正數,相反為負數

(1)

式中：ρ(x,y)表示皮爾遜相關系數，分子為x和y的協方差，分母為x的標準差乘以y的標準差。μx和μy分別是用戶x和y評分的平均值。皮爾遜相關系數其實在幾何上可理解為夾角的余弦值。

(2)延伸相似度

用戶間差異對推薦也很重要,反映了電影推薦系統的質量。針對同一部電影，在計算用戶間差異值的時候，引入了評分相對值，盡可能降低由于喜好風格不同，使評分相差太大[11,12]。用戶可以從1到5的5個整數中選擇相應的分數表達對影片的喜愛程度。我們從數據集中可以看出，同一部電影,不同用戶給出的評分差距太懸殊。所以有式(2)

(2)

當用戶x的評分Gx和用戶y的Gy不相等時使用上式，當Gx和Gy相等時，M(x,y)等于1。相對值M(x,y)的范圍在[0.25,1]。在用戶間評分差值達到最大的4時(M為0.25)，認為相對值最低；評分差值達到1時(M為1)，相對值最高。因此，在這范圍內越大，相對值越高。不同用戶喜歡不同風格的影片，為了計算他們間的相同觀影風格，引入了相同性概念

(3)

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

(4)

把用戶間的這些隱式關系引入進推薦系統中,使評分相對值和CMS(x,y)相加再與皮爾遜相似度結合，得出了用戶間的延伸相似度[13]

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

(5)

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

(6)

又

(7)

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

(8)

2 KNN-DR算法流程

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

2.1 KNN協同過濾

KNN的主要思路是如果一個樣本在特征空間中的k個最相似樣本中大多數屬于某一個類別,則該樣本也屬于這個樣本。大多數基于協同過濾的推薦系統,通過選取相似度高的k個鄰居。根據它們來預測某一用戶對某產品的評分分數。表達式如下

(9)

2.2 多特征融合型矩陣分解

又考慮網站給出用戶對影片的評分值，所以在構造函數時需要增加幾項

(10)

μ是整個訓練中全局評分均值，bi表示影片評分平均值，bu表示用戶u評分相對均值u的偏見值。

(11)

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

(12)

K(·)為用戶u的關鍵字，W(·,m)表示關鍵字m的權重，數值越大，表示u和m的相關度越高。y(m)為文檔總數與詞m所出現文件數比值的對數值。

所以，真實值和預測值的總誤差平方和為

(13)

為了防止過擬合，對M進行正則化，添加處罰項，得

(14)

2.3 優 化

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

(15)

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

(16)

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

2.4 時間復雜度

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

3 實驗分析和仿真

本文首先將已有的算法和本文研究的算法對比，結合查全率和準確率進行效果比較。

3.1 數據集

本文數據集是來自Netflix(http://data-ju.cn/Dataju/web/datasetInstanceDetail/116)。文件“Train-set.ar”包含17 770個文件，分別代表順序為1到17770的MovieID。每一個MovieID后面跟著觀看且評分的客戶ID，等級[1,5]，評價日期。文件“movie-titles.txt”，格式如下：Mo-vie-ID，Year of Release，標題。Year of Release對應發行日期，從1890到2005。標題是Netflix的電影標題。

3.2 推薦評定指標

3.2.1 RMSE評估準則

RMSE全稱為root-mean-square-error，均方根誤差。它是觀測值與真值的偏差的平方和觀測次數n比值的平方根。均方根誤差能很好反映出精密度

(17)

xobs,i表示用戶對產品i的真實評分，xmodel,i為用戶對i的預測評分。下面比較文中提到的幾種算法。橫軸train ration, X為選取的訓練集大小與整個數據集大小的比值,如圖2所示。

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

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

3.2.2 F1評定指標

為了評估top-N推薦系統效果，經常使用的兩個指標是召回率(recall)和準確率(precision)

(18)

(19)

然而，這兩個指標經常矛盾。增加N值，召回率增加，但是準確率降低。實際中，使用F1值作為指標平均值，表達式如式(20)

(20)

第二個實驗選取KNN的高維度處理模型與KNN-DR算法的低維度模型進行效果對比。首先選取合適的X值。需要注意的是，X的取值不同是用于確定不同模型對訓練集稀疏度的敏感度。

運行KNN和KNN-DR情況下實驗，隨著不同的X值，計算出F1度量值。圖3橫軸代表X，縱軸代表F1值。通過圖3的實驗結果，可以得出電影數據的最佳X值是取0.8。

圖3 最優X的值確定(影片數據)

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

圖4的橫軸表示維度的數量，縱軸表示F1值。通過實驗結果表明，KNN-DR算法在KNN的基礎上推薦效果有了明顯的提高。

圖4 Top-10推薦結果(影片數據)

圖5的實驗選取了訓練集大小與整個數據集的比值分別為0.5，0.6，0.7，0.8，0.9進行對比訓練時間。隨著訓練數據的增加，時間差也逐漸增加，說明KNN-DR算法通過降維的方法對運算速度有提高。

圖5 兩種算法訓練時間對比

4 結束語

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