基于SVD矩陣分解技術和RkNN算法的協(xié)同過濾推薦算法

劉 洋

(信陽職業(yè)技術學院 數學與計算機科學學院，信陽 464000)

?

基于SVD矩陣分解技術和RkNN算法的協(xié)同過濾推薦算法

劉 洋

(信陽職業(yè)技術學院 數學與計算機科學學院，信陽 464000)

針對現有協(xié)同過濾算法具有的可擴展性較低、數據稀疏和計算量較大缺點，提出一種基于SVD矩陣分解技術和RkNN算法的協(xié)同過濾推薦算法.本算法經SVD矩陣簡化處理和kNN和RkNN的協(xié)作過濾，增強了用戶的影響集，實現了測試集的未知預測評分功能.經仿真實驗表明，稀疏性、可擴展性和計算量都得到有效改善，系統(tǒng)預測評分與用戶實際評分接近，為用戶提供了良好的使用體驗.該算法獲得了更好的預測性能，同時具有良好的可擴展性.

SVD影響集；協(xié)作過濾；推薦算法；RkNN 影響集

0 前 言

在科技日益發(fā)達的今天，計算機網絡已經覆蓋于社會的每一個角落.以百度、搜狗為代表的搜索引擎開始出現在我國人民的視野之中，為中國人的日常生活和工作帶來了極大的便利.現階段我國搜索引擎具有個性化的特點，其推薦的系統(tǒng)多為基于用戶推薦、基于項目推薦、基于內容推薦，上述的這些協(xié)同過濾算法具有數據稀疏、可擴展性差和用戶相似性難分辨的特點，對推薦系統(tǒng)的質量產生負面影響.隨著科學技術的發(fā)展，越來越多的專家學者開始關注到推薦系統(tǒng)領域，針對傳統(tǒng)算法所存在的問題也做出了針對性改善，其中可擴展性差和系統(tǒng)數據稀疏的問題可通過矩陣分解方式來改善，例如PCA(主成分分析)、NMF(非負矩陣分解)、SVN(奇異值分解)等算法，都可用于降低數據的稀疏性和維度.

1 協(xié)同過濾算法基礎

解決資源和用戶的關系是推薦系統(tǒng)中的主要內容，這里用m×n表示用戶與資源之間的關系，其中m代表用戶，n代表項目，用戶i對項目j的評分用Ri,j表示，則得到下式：

(1)

傳統(tǒng)的協(xié)同過濾算法主要通過尋求目標用戶的最近領導實現，在尋求到若干個領導后獲取各個目標項目的評分，進而實現系統(tǒng)推薦.此類推薦方式是以用戶興趣資源為基礎的，可有效尋求到受用戶喜愛的網絡資源，但由于算法的局限性，導致其擴展性和稀疏性較差.其中稀疏性主要是指系統(tǒng)在未獲得足夠評價的時候，難以根據評價搜尋出符合要求的用戶.可擴展性是指在資源和用戶不斷增加的情況下，系統(tǒng)性能和質量越來越低.目標用戶可系統(tǒng)項目的評分可用下式表示：

(2)

在公式2中，用戶用u表示，項目由j表示，Rm,j代表用戶m對項目j的評分；sim(u,m) 用于表示用戶u與數值m之間的相似度.

2 基于SVD矩陣分解技術的用戶過濾推薦算法的優(yōu)化

從目前我國常用的搜索引擎技術來看，系統(tǒng)的稀疏性和可擴展性問題的解決亟不可待.本文基于推薦系統(tǒng)的稀疏性和擴展性，以影響集概念為出發(fā)點，通過RkNN、kNN、SVD等計算機技術，提出了一種以用戶過濾為基礎的推薦算法，勇于推薦系統(tǒng)質量的提高.

2.1 SVD矩陣簡化

SVD(奇異值分解)又叫單值分解，是一種基于網絡資源的矩陣分解技術，以m×n的矩陣R為例，SVD可將矩陣R變換為3個矩陣，分解過程如圖1所示.

圖1 SVD矩陣變換

由圖可知，A=TSD，在A中，各行都對應了相應的用戶，而各列則對應了相應的項目.運用SVD對關聯矩陣A進行分解處理，則可得到下式：

R0=T0S0D0,S0=diag(α1,…,αr) (3)

在公式3中，r×n與m×r的正交矩陣分別用D0、T0表示，矩陣R0的秩為r，r×r的對角矩陣用S0表示，α1≥…≥αr≥0被稱為單值.

算法1如下：

輸入：矩陣R0

輸出：相關矩陣T，S，D

(1)采用SVD對R0進行分解處理，得到T1，S1，D1；

(2)簡化處理S1，用0替代對角線上所有<1的值，刪除全為0的列或行，由此得到S，表示維數為s的對角矩陣；

(3)根據S的簡化處理，對T1，D1進行同等處理，得到簡化后的T、D，則有矩陣R=TSD，此時R≈R0.

經過對R0的單值分解，使其數據稀疏性得到大幅度的降低，由此可得出較為精準的top-N推薦集和最近鄰居集.

2.2 基于kNN和RkNN的協(xié)作過濾推薦算法

在對矩陣進行簡化處理后，相似用戶之間的精準性得到了有效解決.但在系統(tǒng)相似用戶缺乏的情況下，簡化矩陣后相似用戶量更為減少.本文為更好的解決此類問題，特意引入RkNN和kNN技術，使用戶影響集得以增強.

逆k最近鄰是指在設定的數據集S中，某點被周邊點視為最近鄰，這里特定點q為周邊點的最近鄰，從p點周圍選取影響最大的點，采用RkNN(kNN算法的逆算法)算法來進行計算.

假設數據集為S，p和q兩點之間的距離用D(p，q)表示，則得到RkNN計算公式：

RkNN(q)={q∈kNN(p)|p∈S} (4)

算法2如下：

輸入：用A(m，n)表示用戶項目評分矩陣，其中i為用戶，j為項目；

輸出：用戶i對項目j上的預測評分；

(1)計算A(m，n)中用戶i與周邊相關用戶之間的相似度，將所得結果存入距離矩陣D；

(2)從距離矩陣D中根據用戶i的位置，尋求i點的最近鄰序列，獲得最近鄰列表kNN；

(3)對距離矩陣D進行掃描處理，尋求到用戶i的逆最近鄰序列，獲得逆最近鄰列表RkNN；

(4)提取kNN和RkNN列表中的前k個項；

(5)運用公式(2)和公式(5)計算得出用戶i對項目j的預測評分，得出p，評分預測公式見下式：

(5)

2.3 基于SVD影響集的協(xié)作過濾推薦算法

經過矩陣簡化處理可以精確的得到相似用戶，而kNN和RkNN算法可有效增加用戶之間的影響集，現在SVD矩陣簡化和擴大kNN或RkNN影響集的基礎上，對相似用戶問題和矩陣稀疏性進行改善處理.

算法3如下：

輸入：用戶和項目評分矩陣R(m，n)與用戶i；

輸出：用戶i接收到的推薦項目序列；

(1)采用算法1中的單值分解方法處理矩陣R，可得到簡化后的T，S，D；

(3)計算A(m,k)中用戶之間相似度，將所得結果存入距離矩陣中；

(4)針對于用戶i，尋求到i點的kNN和RkNN值，保存處理；

(5)尋找用戶i在列表kNN中所對應的行，按照從上往下的順序分別取出前k個項，也就是{i1,i2,i3}，并取出RkNN中對應的k個項；

(6)選擇適量參數，分別計算出用戶i在項目j上的預測評分，求解出與用戶相關的項目推薦序列.

3 實驗仿真

采用計算機硬件系統(tǒng)PC作為實驗平臺，配置為內存2 G，CPU 2.8 GHz，Pentium Extreme，Windows XP.

為更好的驗證基于SVD矩陣分解技術和RkNN算法的協(xié)同過濾推薦算法在實際運用過程中的效果，本文采用了仿真實驗和結果分析.召回率和準確率是衡量網絡搜索引擎中的重要指標，這里采用召回率和準確率來檢驗推薦質量.

3.1 實驗步驟

①首先處理基礎矩陣，使得每列的平均值與列中為0的項等同，然后得到經處理后的初始矩陣，在對用戶資源矩陣進行SVD技術處理.②將處理得到的用戶矩陣和項目矩陣采用kNN，RkNN技術計算預算項目評分，獲得綜合推薦集.③選擇原始用戶資源矩陣中瀏覽次數相對較少的項目，然后得到確定的推薦集.④將參數k值確定后，求解出不同值情況下推薦的平均MAE.

3.2 實驗結果

本文實驗數為10萬條評價記錄，則10萬條評價記錄來自于4500個用戶對電影的評價.將10萬份數據平均分為10組，每組數據為4500個用戶對電影的1萬條評價的原始數據.

表1 每組數據所消耗的時間

由表1中可知，用戶在發(fā)出請求到實現推薦的時間大約為2000 ms左右，用戶的等待時間較短，易于用戶接受.當出現大量數據同時運算時，系統(tǒng)在同時完成大型數據時服務時間也相差較小，用戶不論在何種情況下的等待時間均為2000 ms左右.由于系統(tǒng)的時間計算可分為離線和在線兩個部分，其中在線推薦的復雜度為O(N*L)，在O(N*L)中，N代表新項目數，L代表協(xié)同過濾推薦集數，N與L均為常數，因此O(N*L)屬于常數級別，最終可知在線推薦的服務時間與數據量無顯著關聯，不受數據量變化的影響.上表中可知，數據的變化并不會影響到系統(tǒng)服務時間，所有系統(tǒng)的服務時間均在2000 ms左右.仿真實驗證明，系統(tǒng)推薦經SVD技術處理后，稀疏性、可擴展性和計算量都得到有效改善，系統(tǒng)預測評分與用戶實際評分接近，為用戶提供了良好的使用體驗.

[1] 陳彩云,李治國.一種基于SVD和Rough集的信息過濾方法[J].計算機工程與應用,2003,39(34):99-101.

[2] 徐 翔,王煦法.基于SVD的協(xié)同過濾算法的欺詐攻擊行為分析[J].計算機工程與應用,2009,45(20):92-95.

[3] 王 偉,楊 寧,李麗華,劉國強.基于SVD的K-means聚類協(xié)同過濾算法[J].微計算機信息,2012(8):139-141.

[4] 方耀寧,郭云飛,扈紅超,蘭巨龍.一種基于Sigmoid函數的改進協(xié)同過濾推薦算法[J].計算機應用研究,2013,30(6):1688-1691.

[5] XU Jing-ke,SUN Huan-liang,LIU Tian-bo,YU Ge.Location Algorithm Based on RKNN and Its Applications[J].Application Research of Computers,2014,31(3):789-791.

[6] LIU Jin-ling,YANG Feng-xia,LIU Guo-xiang.RkNN of a Group of Object are Queried in the Application of Spatial Database[J].Microelectronics & Computer,2012,29(1):18-22.

Research on Collaborative Filtering Recommendation Algorithm Based on SVD Matrix Decomposition Technique and RkNN Algorithm

LIU Yang

(College of Mathematics and Computer science,Xinyang Vocational and Technical College,Xinyang 464000,China)

Existing collaborative filtering algorithm has the disadvantage of low scalability, data sparsity and large amount of calculation.This paper proposes a collaborative filtering recommendation algorithm based on SVD matrix decomposition technique and RkNN algorithm. Collaborative filtering algorithm and simplifies the processing and kNN and RkNN through the SVD matrix. The algorithm enhances the user influence set and realizes the test set prediction score functionunknown. Simulation experiments show that sparse, cocoa extension and the calculation are effectively improved,system prediction score and actual score are closer to the user.It provides good experience for the user. This algorithm can get better prediction performance and has good scalability.

SVD effect set; collaborative filtering;recommendation algorithm; RkNN effect set

2014-10-20

劉 洋(1975-)，男，碩士，講師，研究方向：高等數學、計算數學.

TP18

A

1671-119X(2015)01-0044-04