劉 洋

(信陽職業(yè)技術(shù)學(xué)院 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，信陽 464000)

?

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

劉 洋

(信陽職業(yè)技術(shù)學(xué)院 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，信陽 464000)

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

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

0 前 言

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

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

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

(1)

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

(2)

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

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

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

2.1 SVD矩陣簡化

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

圖1 SVD矩陣變換

由圖可知，A=TSD，在A中，各行都對應(yīng)了相應(yīng)的用戶，而各列則對應(yīng)了相應(yīng)的項(xiàng)目.運(yùn)用SVD對關(guān)聯(lián)矩陣A進(jìn)行分解處理，則可得到下式：

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

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

算法1如下：

輸入：矩陣R0

輸出：相關(guān)矩陣T，S，D

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

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

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

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

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

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

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

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

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

算法2如下：

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

輸出：用戶i對項(xiàng)目j上的預(yù)測評分；

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

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

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

(4)提取kNN和RkNN列表中的前k個(gè)項(xiàng)；

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

(5)

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

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

算法3如下：

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

輸出：用戶i接收到的推薦項(xiàng)目序列；

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

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

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

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

(6)選擇適量參數(shù)，分別計(jì)算出用戶i在項(xiàng)目j上的預(yù)測評分，求解出與用戶相關(guān)的項(xiàng)目推薦序列.

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

采用計(jì)算機(jī)硬件系統(tǒng)PC作為實(shí)驗(yàn)平臺，配置為內(nèi)存2 G，CPU 2.8 GHz，Pentium Extreme，Windows XP.

為更好的驗(yàn)證基于SVD矩陣分解技術(shù)和RkNN算法的協(xié)同過濾推薦算法在實(shí)際運(yùn)用過程中的效果，本文采用了仿真實(shí)驗(yàn)和結(jié)果分析.召回率和準(zhǔn)確率是衡量網(wǎng)絡(luò)搜索引擎中的重要指標(biāo)，這里采用召回率和準(zhǔn)確率來檢驗(yàn)推薦質(zhì)量.

3.1 實(shí)驗(yàn)步驟

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

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

本文實(shí)驗(yàn)數(shù)為10萬條評價(jià)記錄，則10萬條評價(jià)記錄來自于4500個(gè)用戶對電影的評價(jià).將10萬份數(shù)據(jù)平均分為10組，每組數(shù)據(jù)為4500個(gè)用戶對電影的1萬條評價(jià)的原始數(shù)據(jù).

表1 每組數(shù)據(jù)所消耗的時(shí)間

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

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

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

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

[4] 方耀寧,郭云飛,扈紅超,蘭巨龍.一種基于Sigmoid函數(shù)的改進(jìn)協(xié)同過濾推薦算法[J].計(jì)算機(jī)應(yīng)用研究,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-)，男，碩士，講師，研究方向：高等數(shù)學(xué)、計(jì)算數(shù)學(xué).

TP18

A

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