基于極速學習機和最近鄰的回歸推薦算法

陳愛霞，李寧

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

基于極速學習機和最近鄰的回歸推薦算法

陳愛霞1，李寧2

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

提出了一種基于極速學習機和最近鄰的協同過濾回歸推薦算法.該算法首先采用k最近鄰法對評分矩陣的缺失值進行填充，然后將極速學習機作為回歸器為用戶產生推薦.在推薦領域中的標桿數據集上，將該算法與常用推薦算法- LRCF算法進行了比較，驗證了該算法的有效性.

k最近鄰；極速學習機；推薦系統

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

極速學習機(extreme learning machine，ELM)是Huang等[7-8]于2004年針對單隱層前饋神經網絡(single layer feed-forward neural networks，SLFNs)提出的一種快速學習算法.極速學習機算法克服了傳統神經網絡算法易陷入局部極小、迭代次數多、學習時間長等問題，并具有學習速度快、泛化能力好、能逼近任何復雜函數等優點，已經廣泛應用在數據挖掘、機器學習、圖像處理等領域.

本文首先采用k最近鄰法對數據的缺失值進行填充，然后將極速學習機作為回歸器為用戶產生推薦，并在推薦領域中的3個標桿數據集上，驗證了該算法的有效性.

1 極速學習機概述

極速學習機是針對單隱層前饋神經網絡提出的一種快速學習算法,該算法只需要設置網絡的隱層節點個數，其網絡輸入權值ai以及隱元偏置bi都是隨機生成的，然后由最小二乘法得到唯一的最優解，即輸出權重βi,如圖1所示.其中，輸入向量xj=(xj1,xj2,…,xjn)T∈Rn，隱層元個數為L，向量ai是輸入層到第i個隱層元的權重，數bi是第i個隱層元的偏置，向量βi是第i個隱層元和輸出向量之間的權重，輸出向量oj=(oj1，oj2,…,ojm)T∈Rm.

圖1 SLFNs極速學習機[7-8]Fig.1 SLFNs extreme learning machine[7-8]

假設有N個任意樣本(xj,tj)，j=1,2,…，N,其中xj=(xj1,xj2,…，xjn)T∈Rn，tj=(tj1,tj2,…，tjm)T∈Rm.對于一個有L個隱層節點的SLFNs極速學習機可以表示為

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

SLFNs極速學習機的學習目標是使得輸出誤差最小，可表示為

oj-tj=0，

即存在βi、ai和bi使得

可以表示為

Hβ=T，

其中，H是隱層節點的輸出，β為輸出權重矩陣，T為期望輸出.

在SLFNs極速學習機中，輸入權重ai和隱層偏置bi一旦被隨機確定，就會唯一確定隱層的輸出權重矩陣β.因此，訓練SLFNs極速學習機便轉化為求解線性矩陣方程Hβ=T，并且輸出權重矩陣β可由下式確定

2 協同過濾回歸推薦模型[10]

假設X∈RU×I為一個稀疏的用戶評分矩陣，回歸推薦模型首先采用機器學習算法對用戶評分矩陣X進行缺失值填充，然后通過最小化目標函數f(X)構造回歸器fj(·)，如下公式所示：

其中，輸入樣本X通常是一個包含U個用戶和I個對象的稀疏的用戶評分矩陣，?表示Hadamard乘積，即矩陣中對應元素之間分別相乘，·F表示Frobenius范數，簡稱F范數，fj(·)表示關于對象j的回歸器，fj(i)表示對象j的回歸模型關于用戶i的輸出值，矩陣F是由U×I個回歸值fj(i)構成的矩陣，稀疏指示矩陣W其元素為1表示有值，元素為0表示缺值.

3 基于極速學習機和k最近鄰的協同過濾回歸推薦算法

當回歸推薦模型中的回歸器是極速學習機時，稱為基于極速學習機的協同過濾回歸推薦算法(ELMCF).詳細過程如下：假設Ds是一個稀疏的用戶評分矩陣(由于包含U個用戶和I個對象，所以Ds是一個U行I列的矩陣)，首先ELMCF算法采用機器學習算法將矩陣Ds的缺失值填充，得到一個滿值矩陣Df.本文中，缺失值填充采用k最近鄰算法，即找出這個樣本的k個最近鄰居，將這些鄰居的平均值賦給該樣本.

然后，對于滿值矩陣Df的每一列構造一個基于極速學習機的回歸器.具體地，將矩陣Df的第i(i=1,2,…，I)列作為輸出矩陣，記作Ti，將剩余的I-1列作為輸入矩陣，記作Pi，如式(1)所示.

(1)

與標準的ELM算法類似，ELMCF算法首先將輸入矩陣Pi映射到隱含層，得到矩陣Hi，然后對于未知的權重β和輸出矩陣Ti有下面矩陣方程成立：

Hiβ=Ti.

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

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

2)對于對象i(i=1,2,…，I)構造輸入矩陣Pi和相應的輸出向量Ti.

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

與傳統的“一對一”線性回歸推薦算法相比，本文提出的算法具有如下幾點優勢：

①該方法中回歸器的個數大大減少.在傳統的算法中，對于每個對象需要構造I-1個回歸器，因為共有I個對象，所以共需要構造I(I-1)個回歸器.而本文的方法中，對于每個對象只需構造1個回歸器，因此只需要構造I個回歸器.

②該方法不需要對回歸器進行集成，簡單易行.在傳統的算法中，對某一對象i的評分預測值需由I-1個關于該對象的“一對一”回歸器的評分集成而得.本文的方法中，對某一對象的評分預測值直接由該對象的ELM回歸器fi(·)產生，而不需進行集成.

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

4 實驗結果

為了驗證本文提出的基于極速學習機和最近鄰的回歸推薦算法的有效性，分別在推薦領域的3個標桿數據集，Movielens數據集、Jester數據集及Tencent Weibo數據集上進行了實驗，關于這3個數據集的描述見表1.

表1 實驗中使用的數據集

首先對Jester數據集和Tencent Weibo數據集進行一些預處理.對于Jester數據集，設定閾值為80，即保留至少對80則笑話進行評分的用戶，于是得到一個含有6 916個用戶的評分矩陣，然后把每個評分值轉化到1到5之間.對于Tencent Weibo數據集，設定閾值為300，即保留至少存在300個關注者對其評分的被關注者和至少對300個被關注者進行評分的關注者，于是得到一個含有6 806個關注者和1 274個被關注者的評分矩陣.

推薦系統中最常用的度量指標之一是平均絕對誤差(mean absolute error，MAE).本文將采用MAE來度量推薦算法的性能優劣.

將本文提出的基于極速學習機和最近鄰的回歸推薦算法與常用的LRCF推薦算法在基于對象的回歸推薦方式下進行實驗比較.隨機選擇70%的評分項作為訓練數據集，剩余評分項作為測試數據集.訓練集的構造都獨立重復10次，取10次實驗結果MAE的均值作為它們最終的性能指標，如表2所示.實驗中，采用k最近鄰法填充缺失值時，選用的是歐式距離，并且參數k首先選取較小的數，經過反復實驗，最終得到最優的k值.極速學習機回歸器中的隱含層節點個數一般認為越大越好，實驗中選取節點個數為80.

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

從表2可以看出，在3個標桿數據集上，本文提出的算法和LRCF推薦算法相比，MAE較小，推薦效果更優，尤其在Tencent Weibo數據集上，本文提出的ELMCF算法在訓練集和測試集上的優勢更為明顯，大大優于LRCF算法的推薦結果.另外，大多數情況下，測試誤差都比訓練誤差稍微大一些，這也容易理解，因為測試樣本分布與訓練樣本的分布往往不完全一致，于是造成了在基于訓練樣本建立的模型進行測試時產生誤差較大.

5 結論

本文提出的基于極速學習機的回歸推薦算法具有回歸器個數少、不需要集成、回歸方式更加合理等優點.與常用的LRCF推薦算法相比，平均絕對誤差較小，推薦效果更優.但是，極速學習機回歸推薦算法中，需要確定隱含層節點的個數，本文中指定了該參數的值，該參數的取值對推薦效果有無影響以及有什么影響將是未來研究工作的一部分.

[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] 馬宏偉,張光衛,李鵬.協同過濾推薦算法綜述[J].小型微型計算機系統,2009,30( 7) : 1282-1288.

[5] 孫光福，吳樂，劉淇，等.基于時序行為的協同過濾推薦算法[J].軟件學報,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] 榮輝桂，火生旭，胡春華，等.基于用戶相似度的協同過濾推薦算法[J].通信學報,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] 李純果，李海峰.無監督排序學習算法的一致性比較 [J].河北大學學報(自然科學版)，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] 尚田豐.協同推薦關鍵技術研究[D].北京：中國科學院大學，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

國家自然科學基金資助項目(61672205)

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

TP183

A

1000-1565(2017)06-0662-05

孟素蘭)