基于極速學(xué)習(xí)機(jī)和最近鄰的回歸推薦算法

陳愛(ài)霞，李寧

(1.河北大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院，河北 保定 071002；2.中國(guó)科學(xué)院 信息工程研究所，北京 100093)

基于極速學(xué)習(xí)機(jī)和最近鄰的回歸推薦算法

陳愛(ài)霞1，李寧2

(1.河北大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院，河北 保定 071002；2.中國(guó)科學(xué)院 信息工程研究所，北京 100093)

提出了一種基于極速學(xué)習(xí)機(jī)和最近鄰的協(xié)同過(guò)濾回歸推薦算法.該算法首先采用k最近鄰法對(duì)評(píng)分矩陣的缺失值進(jìn)行填充，然后將極速學(xué)習(xí)機(jī)作為回歸器為用戶(hù)產(chǎn)生推薦.在推薦領(lǐng)域中的標(biāo)桿數(shù)據(jù)集上，將該算法與常用推薦算法- LRCF算法進(jìn)行了比較，驗(yàn)證了該算法的有效性.

k最近鄰；極速學(xué)習(xí)機(jī)；推薦系統(tǒng)

隨著信息技術(shù)和互聯(lián)網(wǎng)的飛快發(fā)展，信息量海量增長(zhǎng)，使得用戶(hù)在面對(duì)大量信息時(shí)無(wú)法從中獲得對(duì)自己真正有用的那些信息.此時(shí)，推薦系統(tǒng)[1]應(yīng)運(yùn)而生.對(duì)用戶(hù)而言，推薦系統(tǒng)不需要用戶(hù)提供明確的目標(biāo)，只需要提供一些建議性的條件，推薦系統(tǒng)會(huì)根據(jù)這些條件，結(jié)合相關(guān)信息，計(jì)算用戶(hù)的需求，最終給出合適的有用信息.推薦系統(tǒng)現(xiàn)在已經(jīng)廣泛應(yīng)用于很多領(lǐng)域，尤其在電子商務(wù)領(lǐng)域，推薦系統(tǒng)的價(jià)值更為突出.目前，幾乎所有的大型電子商務(wù)網(wǎng)站都有自己的推薦系統(tǒng)，如亞馬遜、淘寶、京東等.與此同時(shí)，推薦系統(tǒng)在理論方面也取得了豐碩的成果，推薦系統(tǒng)主要包含基于協(xié)同過(guò)濾的推薦系統(tǒng)[2]和基于內(nèi)容的推薦系統(tǒng)[3]2大類(lèi).協(xié)同過(guò)濾推薦是目前應(yīng)用最廣泛和最成功的推薦系統(tǒng)[4].協(xié)同過(guò)濾推薦算法中的關(guān)鍵問(wèn)題有相似性比較，數(shù)據(jù)稀疏性問(wèn)題，冷啟動(dòng)問(wèn)題，可擴(kuò)展性問(wèn)題，推薦的實(shí)時(shí)性，推薦策略，評(píng)估方法等[4].孫光福等[5]提出一種對(duì)用戶(hù)(產(chǎn)品)間的時(shí)序行為建模的方法，有效地提高了推薦精度.榮輝貴等[6]引入用戶(hù)相似度概念，定義了社交網(wǎng)絡(luò)中屬性相似度，以及相似度構(gòu)成與計(jì)算方法，提出了一種改進(jìn)的協(xié)同過(guò)濾推薦算法,有效地改善了社交網(wǎng)絡(luò)中的推薦準(zhǔn)確性.

極速學(xué)習(xí)機(jī)(extreme learning machine，ELM)是Huang等[7-8]于2004年針對(duì)單隱層前饋神經(jīng)網(wǎng)絡(luò)(single layer feed-forward neural networks，SLFNs)提出的一種快速學(xué)習(xí)算法.極速學(xué)習(xí)機(jī)算法克服了傳統(tǒng)神經(jīng)網(wǎng)絡(luò)算法易陷入局部極小、迭代次數(shù)多、學(xué)習(xí)時(shí)間長(zhǎng)等問(wèn)題，并具有學(xué)習(xí)速度快、泛化能力好、能逼近任何復(fù)雜函數(shù)等優(yōu)點(diǎn)，已經(jīng)廣泛應(yīng)用在數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)、圖像處理等領(lǐng)域.

本文首先采用k最近鄰法對(duì)數(shù)據(jù)的缺失值進(jìn)行填充，然后將極速學(xué)習(xí)機(jī)作為回歸器為用戶(hù)產(chǎn)生推薦，并在推薦領(lǐng)域中的3個(gè)標(biāo)桿數(shù)據(jù)集上，驗(yàn)證了該算法的有效性.

1 極速學(xué)習(xí)機(jī)概述

極速學(xué)習(xí)機(jī)是針對(duì)單隱層前饋神經(jīng)網(wǎng)絡(luò)提出的一種快速學(xué)習(xí)算法,該算法只需要設(shè)置網(wǎng)絡(luò)的隱層節(jié)點(diǎn)個(gè)數(shù)，其網(wǎng)絡(luò)輸入權(quán)值ai以及隱元偏置bi都是隨機(jī)生成的，然后由最小二乘法得到唯一的最優(yōu)解，即輸出權(quán)重βi,如圖1所示.其中，輸入向量xj=(xj1,xj2,…,xjn)T∈Rn，隱層元個(gè)數(shù)為L(zhǎng)，向量ai是輸入層到第i個(gè)隱層元的權(quán)重，數(shù)bi是第i個(gè)隱層元的偏置，向量βi是第i個(gè)隱層元和輸出向量之間的權(quán)重，輸出向量oj=(oj1，oj2,…,ojm)T∈Rm.

圖1 SLFNs極速學(xué)習(xí)機(jī)[7-8]Fig.1 SLFNs extreme learning machine[7-8]

假設(shè)有N個(gè)任意樣本(xj,tj)，j=1,2,…，N,其中xj=(xj1,xj2,…，xjn)T∈Rn，tj=(tj1,tj2,…，tjm)T∈Rm.對(duì)于一個(gè)有L個(gè)隱層節(jié)點(diǎn)的SLFNs極速學(xué)習(xí)機(jī)可以表示為

其中g(shù)(x)為激活函數(shù)，ai·xj表示ai和xj的內(nèi)積.

SLFNs極速學(xué)習(xí)機(jī)的學(xué)習(xí)目標(biāo)是使得輸出誤差最小，可表示為

oj-tj=0，

即存在βi、ai和bi使得

可以表示為

Hβ=T，

其中，H是隱層節(jié)點(diǎn)的輸出，β為輸出權(quán)重矩陣，T為期望輸出.

在SLFNs極速學(xué)習(xí)機(jī)中，輸入權(quán)重ai和隱層偏置bi一旦被隨機(jī)確定，就會(huì)唯一確定隱層的輸出權(quán)重矩陣β.因此，訓(xùn)練SLFNs極速學(xué)習(xí)機(jī)便轉(zhuǎn)化為求解線性矩陣方程Hβ=T，并且輸出權(quán)重矩陣β可由下式確定

2 協(xié)同過(guò)濾回歸推薦模型[10]

假設(shè)X∈RU×I為一個(gè)稀疏的用戶(hù)評(píng)分矩陣，回歸推薦模型首先采用機(jī)器學(xué)習(xí)算法對(duì)用戶(hù)評(píng)分矩陣X進(jìn)行缺失值填充，然后通過(guò)最小化目標(biāo)函數(shù)f(X)構(gòu)造回歸器fj(·)，如下公式所示：

其中，輸入樣本X通常是一個(gè)包含U個(gè)用戶(hù)和I個(gè)對(duì)象的稀疏的用戶(hù)評(píng)分矩陣，?表示Hadamard乘積，即矩陣中對(duì)應(yīng)元素之間分別相乘，·F表示Frobenius范數(shù)，簡(jiǎn)稱(chēng)F范數(shù)，fj(·)表示關(guān)于對(duì)象j的回歸器，fj(i)表示對(duì)象j的回歸模型關(guān)于用戶(hù)i的輸出值，矩陣F是由U×I個(gè)回歸值fj(i)構(gòu)成的矩陣，稀疏指示矩陣W其元素為1表示有值，元素為0表示缺值.

3 基于極速學(xué)習(xí)機(jī)和k最近鄰的協(xié)同過(guò)濾回歸推薦算法

當(dāng)回歸推薦模型中的回歸器是極速學(xué)習(xí)機(jī)時(shí)，稱(chēng)為基于極速學(xué)習(xí)機(jī)的協(xié)同過(guò)濾回歸推薦算法(ELMCF).詳細(xì)過(guò)程如下：假設(shè)Ds是一個(gè)稀疏的用戶(hù)評(píng)分矩陣(由于包含U個(gè)用戶(hù)和I個(gè)對(duì)象，所以Ds是一個(gè)U行I列的矩陣)，首先ELMCF算法采用機(jī)器學(xué)習(xí)算法將矩陣Ds的缺失值填充，得到一個(gè)滿(mǎn)值矩陣Df.本文中，缺失值填充采用k最近鄰算法，即找出這個(gè)樣本的k個(gè)最近鄰居，將這些鄰居的平均值賦給該樣本.

然后，對(duì)于滿(mǎn)值矩陣Df的每一列構(gòu)造一個(gè)基于極速學(xué)習(xí)機(jī)的回歸器.具體地，將矩陣Df的第i(i=1,2,…，I)列作為輸出矩陣，記作Ti，將剩余的I-1列作為輸入矩陣，記作Pi，如式(1)所示.

(1)

與標(biāo)準(zhǔn)的ELM算法類(lèi)似，ELMCF算法首先將輸入矩陣Pi映射到隱含層，得到矩陣Hi，然后對(duì)于未知的權(quán)重β和輸出矩陣Ti有下面矩陣方程成立：

Hiβ=Ti.

下面介紹基于極速學(xué)習(xí)機(jī)和最近鄰的回歸推薦算法的一般步驟.算法輸入為訓(xùn)練集{xi|xi∈RU,i=1,…，N}，并設(shè)隱含層節(jié)點(diǎn)數(shù)為L(zhǎng)，隱含層函數(shù)為g(aj,bj,xi),j=1,…，L.對(duì)于每個(gè)對(duì)象訓(xùn)練得到一個(gè)ELM回歸器，算法共輸出I個(gè)ELM回歸器.

1)用k最近鄰法填充評(píng)分矩陣Ds上的缺失值.

2)對(duì)于對(duì)象i(i=1,2,…，I)構(gòu)造輸入矩陣Pi和相應(yīng)的輸出向量Ti.

3)對(duì)于對(duì)象i(i=1,2,…，I)構(gòu)造ELM回歸器fi(·).

與傳統(tǒng)的“一對(duì)一”線性回歸推薦算法相比，本文提出的算法具有如下幾點(diǎn)優(yōu)勢(shì)：

①該方法中回歸器的個(gè)數(shù)大大減少.在傳統(tǒng)的算法中，對(duì)于每個(gè)對(duì)象需要構(gòu)造I-1個(gè)回歸器，因?yàn)楣灿蠭個(gè)對(duì)象，所以共需要構(gòu)造I(I-1)個(gè)回歸器.而本文的方法中，對(duì)于每個(gè)對(duì)象只需構(gòu)造1個(gè)回歸器，因此只需要構(gòu)造I個(gè)回歸器.

②該方法不需要對(duì)回歸器進(jìn)行集成，簡(jiǎn)單易行.在傳統(tǒng)的算法中，對(duì)某一對(duì)象i的評(píng)分預(yù)測(cè)值需由I-1個(gè)關(guān)于該對(duì)象的“一對(duì)一”回歸器的評(píng)分集成而得.本文的方法中，對(duì)某一對(duì)象的評(píng)分預(yù)測(cè)值直接由該對(duì)象的ELM回歸器fi(·)產(chǎn)生，而不需進(jìn)行集成.

③該方法中輸入自變量通常是多個(gè)對(duì)象，從而有效地避免了輸入相同而輸出不同的情況發(fā)生，使得回歸方式更加合理.

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

為了驗(yàn)證本文提出的基于極速學(xué)習(xí)機(jī)和最近鄰的回歸推薦算法的有效性，分別在推薦領(lǐng)域的3個(gè)標(biāo)桿數(shù)據(jù)集，Movielens數(shù)據(jù)集、Jester數(shù)據(jù)集及Tencent Weibo數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)，關(guān)于這3個(gè)數(shù)據(jù)集的描述見(jiàn)表1.

表1 實(shí)驗(yàn)中使用的數(shù)據(jù)集

首先對(duì)Jester數(shù)據(jù)集和Tencent Weibo數(shù)據(jù)集進(jìn)行一些預(yù)處理.對(duì)于Jester數(shù)據(jù)集，設(shè)定閾值為80，即保留至少對(duì)80則笑話(huà)進(jìn)行評(píng)分的用戶(hù)，于是得到一個(gè)含有6 916個(gè)用戶(hù)的評(píng)分矩陣，然后把每個(gè)評(píng)分值轉(zhuǎn)化到1到5之間.對(duì)于Tencent Weibo數(shù)據(jù)集，設(shè)定閾值為300，即保留至少存在300個(gè)關(guān)注者對(duì)其評(píng)分的被關(guān)注者和至少對(duì)300個(gè)被關(guān)注者進(jìn)行評(píng)分的關(guān)注者，于是得到一個(gè)含有6 806個(gè)關(guān)注者和1 274個(gè)被關(guān)注者的評(píng)分矩陣.

推薦系統(tǒng)中最常用的度量指標(biāo)之一是平均絕對(duì)誤差(mean absolute error，MAE).本文將采用MAE來(lái)度量推薦算法的性能優(yōu)劣.

將本文提出的基于極速學(xué)習(xí)機(jī)和最近鄰的回歸推薦算法與常用的LRCF推薦算法在基于對(duì)象的回歸推薦方式下進(jìn)行實(shí)驗(yàn)比較.隨機(jī)選擇70%的評(píng)分項(xiàng)作為訓(xùn)練數(shù)據(jù)集，剩余評(píng)分項(xiàng)作為測(cè)試數(shù)據(jù)集.訓(xùn)練集的構(gòu)造都獨(dú)立重復(fù)10次，取10次實(shí)驗(yàn)結(jié)果MAE的均值作為它們最終的性能指標(biāo)，如表2所示.實(shí)驗(yàn)中，采用k最近鄰法填充缺失值時(shí)，選用的是歐式距離，并且參數(shù)k首先選取較小的數(shù)，經(jīng)過(guò)反復(fù)實(shí)驗(yàn)，最終得到最優(yōu)的k值.極速學(xué)習(xí)機(jī)回歸器中的隱含層節(jié)點(diǎn)個(gè)數(shù)一般認(rèn)為越大越好，實(shí)驗(yàn)中選取節(jié)點(diǎn)個(gè)數(shù)為80.

表2 基于對(duì)象的回歸推薦方式下的平均絕對(duì)誤差比較

從表2可以看出，在3個(gè)標(biāo)桿數(shù)據(jù)集上，本文提出的算法和LRCF推薦算法相比，MAE較小，推薦效果更優(yōu)，尤其在Tencent Weibo數(shù)據(jù)集上，本文提出的ELMCF算法在訓(xùn)練集和測(cè)試集上的優(yōu)勢(shì)更為明顯，大大優(yōu)于LRCF算法的推薦結(jié)果.另外，大多數(shù)情況下，測(cè)試誤差都比訓(xùn)練誤差稍微大一些，這也容易理解，因?yàn)闇y(cè)試樣本分布與訓(xùn)練樣本的分布往往不完全一致，于是造成了在基于訓(xùn)練樣本建立的模型進(jìn)行測(cè)試時(shí)產(chǎn)生誤差較大.

5 結(jié)論

本文提出的基于極速學(xué)習(xí)機(jī)的回歸推薦算法具有回歸器個(gè)數(shù)少、不需要集成、回歸方式更加合理等優(yōu)點(diǎn).與常用的LRCF推薦算法相比，平均絕對(duì)誤差較小，推薦效果更優(yōu).但是，極速學(xué)習(xí)機(jī)回歸推薦算法中，需要確定隱含層節(jié)點(diǎn)的個(gè)數(shù)，本文中指定了該參數(shù)的值，該參數(shù)的取值對(duì)推薦效果有無(wú)影響以及有什么影響將是未來(lái)研究工作的一部分.

[1] RESNICK P，VARIAN H R.Recommender systems[J].Communications of the ACM，1997，40(3):56-58.

[2] BREESE J S，HECKERMAN D，KADIE C.Empirical analysis of predictive algorithms for collaborative filtering[Z].The 14th Conference on Uncertainty in Artificial Intelligence，Madison,wisconsin,USA,1998.

[3] BASU C，HIRSH H，COHEN W，et al.Recommendation as classification: Using social and content-based information in recommendation[Z].The 15th National Conference on Artificial Intelligence and and 10th Innovative Applications of Artificial Intelligence Conference,Madison,Wisconsin,USA,1998.

[4] 馬宏偉,張光衛(wèi),李鵬.協(xié)同過(guò)濾推薦算法綜述[J].小型微型計(jì)算機(jī)系統(tǒng),2009,30( 7) : 1282-1288.

[5] 孫光福，吳樂(lè)，劉淇，等.基于時(shí)序行為的協(xié)同過(guò)濾推薦算法[J].軟件學(xué)報(bào),2013，24(11):2721-2733.DOI:10.3724/SP.J.1001.2013.04478.

SUN G F，WU L，LI Q，et al.Recommendations based on collaborative filtering by exploiting sequential behaviors[J].Journal of Software,2013，24(11):2721-2733.DOI:10.3724/SP.J.1001.2013.04478.

[6] 榮輝桂，火生旭，胡春華，等.基于用戶(hù)相似度的協(xié)同過(guò)濾推薦算法[J].通信學(xué)報(bào),2014，35(2):16-24.DOI:10.3969/j.issn.1000-436x.2014.02.003.

[7] HUANG G B，ZHU Q Y，SIEW C K.Extreme learning machine: a new learning scheme of feedforward neural networks[C]//2004 IEEE International Joint Conference on Neural Networks.2004.DOI:10.1109/IJCNN.2004.1380068.

[8] HUANG G B,ZHU Q Y,SIEW C K.Extreme learning machine:Theory and applications[J].Neurocomputing,2006,70(1-3):489-501.DOI:10.1016/j.neucom.2005.12.126.

[9] 李純果，李海峰.無(wú)監(jiān)督排序?qū)W習(xí)算法的一致性比較 [J].河北大學(xué)學(xué)報(bào)(自然科學(xué)版)，2015，35 (2): 182-187.DOI: 10.3969/j.issn.10001565.2015.02.013.

LI C G，LI H F.Comparison analysis on ranking consensus[J].Journal of Hebei University: Naturnal Science Edition，2015，35(2): 182-187.DOI: 10.3969/j.issn.10001565.2015.02.013.

[10] 尚田豐.協(xié)同推薦關(guān)鍵技術(shù)研究[D].北京：中國(guó)科學(xué)院大學(xué)，2014.

SHANG T F. Research on critical technologies of collaborative recommendation[D].Bei jing:University of chinese Academy of sciences,2014.

Regressionrecommendationalgorithmbasedonextremelearningmachineandnearestneighbors

CHENAixia1，LINing2

(1.College of Mathematics and Information Science，Hebei University，Baoding 071002，China; 2.Institute of Information Engineering，Chinese Academy of Sciences，Beijing 100093，China)

This paper proposed a collaborative filtering regression recommendation algorithm based on extreme learning machine(ELM) and nearest neighbors.The algorithm firstly used theknearest neighbors method to fill the missing attribute value，then the ELM regression machine is used to produce recommendations for the user.On the benchmarking data sets in the field of recommendation，we compared our algorithm with the common recommend algorithm—LRCF algorithm，and verified the effectiveness of the proposed algorithm.

knearest neighbors; extreme learning machine; recommender systems

10.3969/j.issn.1000-1565.2017.06.014

2016-11-08

國(guó)家自然科學(xué)基金資助項(xiàng)目(61672205)

陳愛(ài)霞 (1982—)，女，河北寧晉人，河北大學(xué)講師，主要從事不確定信息處理方面研究. E-mail：aixia_chen@163.com

TP183

A

1000-1565(2017)06-0662-05

孟素蘭)