基于支持向量機回歸的協(xié)同過濾相似度優(yōu)化方法

呂成戍，蓋 印，匡宇鵬

（1.東北財經(jīng)大學(xué) 管理科學(xué)與工程學(xué)院，遼寧 大連 116025

2.內(nèi)蒙古中電物流路港有限責(zé)任公司赤峰鐵路分公司，內(nèi)蒙古赤峰 024000）

基于支持向量機回歸的協(xié)同過濾相似度優(yōu)化方法

呂成戍1，蓋 印1，匡宇鵬2

（1.東北財經(jīng)大學(xué) 管理科學(xué)與工程學(xué)院，遼寧 大連 116025

2.內(nèi)蒙古中電物流路港有限責(zé)任公司赤峰鐵路分公司，內(nèi)蒙古赤峰 024000）

在基于屬性相似性的協(xié)同過濾算法中，項目屬性之間相似性的度量是整個算法的關(guān)鍵?，F(xiàn)有算法在計算項目屬性相似度時忽略了項目屬性之間的非線性關(guān)系，導(dǎo)致相似性度量不準(zhǔn)確，無法保證項目推薦精度。針對這一問題，本文提出一種基于支持向量機回歸的協(xié)同過濾相似度優(yōu)化方法，該方法利用支持向量機回歸算法來構(gòu)建項目屬性相似度模型，解決項目屬性的非線性關(guān)聯(lián)問題，改善項目屬性相似度計算。實驗結(jié)果表明，優(yōu)化方法計算出的項目相似性更準(zhǔn)確，顯著提高了系統(tǒng)的推薦質(zhì)量。

支持向量機回歸；項目屬性相似性；協(xié)同過濾

0 引 言

協(xié)同過濾推薦是當(dāng)前最成功的推薦技術(shù)之一[1]，根據(jù)過濾操作對象的不同，協(xié)同過濾算法可以分為基于用戶(User-based)[2]和基于項目(Item-based)[3]的算法。User-based協(xié)同過濾算法隨著數(shù)據(jù)的不斷增多，要從大量用戶中尋找最近鄰居用戶的問題成為推薦系統(tǒng)發(fā)展的瓶頸，而Item-based協(xié)同過濾算法通過將計算用戶之間的相似性轉(zhuǎn)換為計算項之間的相似性的方法，有效地解決了這一問題。在Item-Based協(xié)同過濾算法中，項目之間相似性的度量是否準(zhǔn)確，直接關(guān)系到整個推薦系統(tǒng)的推薦質(zhì)量。而實際上，由于系統(tǒng)用戶評分?jǐn)?shù)據(jù)的極端稀疏性，傳統(tǒng)的相似性度量方法存在著一定的弊端，系統(tǒng)的推薦精度往往會很低。為了提高系統(tǒng)推薦精度，一些研究者們對項目相似性計算方法進(jìn)行了改進(jìn)。根據(jù)項目屬性相似度和用戶評價相似度，計算項目之間的綜合相似度，但項目屬性相似度的計算公式只簡單考慮兩個項目間相同的屬性數(shù)，未考慮項目屬性的重要性差異。因此將項目屬性相似度和項目評分相似度的線性組合作為最終鄰居相似度，在計算項目屬性向量的相似度時，使用加權(quán)計算來解決項目屬性的重要性差異問題。以上算法的核心就是用基于項目屬性的相似性來改進(jìn)傳統(tǒng)Item-Based協(xié)同過濾中目標(biāo)項目的最近鄰居項目集的查找，項目屬性相似度的計算是這類改進(jìn)方法的關(guān)鍵。但是，目前基于屬性相似性的Item-Based協(xié)同過濾算法將項目屬性之間的復(fù)雜關(guān)系進(jìn)行了簡單的線性化處理,忽略了項目屬性的非線性關(guān)系，在一定程度上影響了算法的效能。

Vapnik等人根據(jù)統(tǒng)計學(xué)習(xí)理論提出的支持向量機（Support Vector Machine,SVM）[7]方法具有諸多的優(yōu)良特性，近年來引起了廣泛的關(guān)注，SVM方法最早是針對模式識別問題提出的，Vapnik通過引入不敏感損失函數(shù)，得到了用于回歸估計的SVM方法，稱為支持向量機回歸(Support Vector Regression，SVR)[8]，SVR方法被引入非線性回歸領(lǐng)域，顯示了其巨大威力[9，10]。本文利用支持向量機回歸算法的回歸能力，解決項目屬性的非線性關(guān)聯(lián)問題。實驗結(jié)果表明，本文所提的算法大幅提高了推薦算法的精確度。

1 支持向量機回歸

一般的回歸問題可表述為：給定l個訓(xùn)練樣本，學(xué)習(xí)機從中學(xué)習(xí)出輸入、輸出變量之間的關(guān)系(依賴關(guān)系、映射關(guān)系、函數(shù)關(guān)系)f(x)?？紤]一個訓(xùn)練樣本數(shù)據(jù)集{(x1，y1)，…，（xl，yl）}。對于i=1，…，l其中xi∈Rn每個代表了樣本的輸入空間，存在一個目標(biāo)值yi∈R與其相對應(yīng)?；貧w問題的思想就是從中學(xué)習(xí)出一個函數(shù)，能夠精確地估計未來值。一般的SVR函數(shù)形式為：

其中，w∈Rn，b∈R，Φ代表了從Rn到高維空間的一個非線性變換。我們的目標(biāo)是找出w和b的值，使回歸風(fēng)險函數(shù)最小化。回歸風(fēng)險函數(shù)為：

其中，Γ(·)是損失函數(shù)，常數(shù)C＞0，表示對估計偏差的懲罰度。最常用的損失函數(shù)是Vapnik提出的ε-敏感度函數(shù)。解決回歸問題時，SVM是在n維特征空間中，使用ε-敏感度損失函數(shù)來求解一個線性回歸問題。同時，它要通過最小化‖w‖2來減小模型容量，以保證更好地擬合一般性。于是我們得到了Vapnik所描述的最優(yōu)化問題：

其中，ξi，ξ*i是代表輸出結(jié)果上下界的松弛變量。

經(jīng)過推導(dǎo)，可得到其對偶優(yōu)化問題為：

在解出以上的二次優(yōu)化問題后，一般公式可以改寫為：

在公式(5)中，點積可以用核函數(shù)k(xi，x)來代替。核函數(shù)能夠在不知道變換具體函數(shù)的情況下，使用低維空間的數(shù)據(jù)輸入來計算高維特征空間中的點積。通常使用的核函數(shù)包括線性函數(shù)、多項式函數(shù)以及RBF等。

2 基于支持向量機回歸的相似度優(yōu)化方法

2.1 項目的特征屬性

一般來說，推薦系統(tǒng)至少存在3個基本數(shù)據(jù)表，一個用來記錄注冊用戶信息，一個用來記錄項目信息，還有一個記錄用戶的評分信息(記為用戶評分表)。通過對記錄項目信息表的整理可以得到項目特征屬性矩陣A。假定接受評分的項目數(shù)是n，每個項目挑選k個具有代表性的屬性描述，在此將其抽象為 {Attr1，Attr2，…，Attrk}。見表1，項目屬性矩陣A(其中1表示某個項目具有某項屬性，0表示某個項目不具有某項屬性)，項目特征屬性的抽取可以從項目的簡介網(wǎng)頁中提取，或者從推薦系統(tǒng)中用來記錄項目信息的表中整理得到。

表1 項目屬性矩陣A

2.2 構(gòu)建項目屬性相似度模型

設(shè)任意兩個項目Itemx、Itemy在k維項目特征屬性空間上的屬性值分別看做向量Itemx={Attrx,1，Attrx,2，…，Attrx,k}和Itemy={Attry,1，Attry,2，…，Attry,k}，并且該向量元素的取值為二維數(shù)據(jù)(0或1)，則項目Itemx和項目Itemy之間的屬性相似性simAttr(Itemx，Itemy)的計算公式為[6]：

其中simAttr(Itemx，Itemy)為兩個物品的相似度，sim(Attrj(Itemx)，Attrj(Itemy))則是Itemx，Itemy關(guān)于屬性Attrj的相似度。wj是根據(jù)經(jīng)驗對每個屬性Attrj賦予一個權(quán)值，且相似度是對每種特征進(jìn)行線形加權(quán)，但是對于非線性相似度則會出現(xiàn)較大的誤差。例如用戶可能會覺得只要是導(dǎo)演A與演員B合作的影片，無論風(fēng)格以及年代的差距有多大，都是非常相似的。針對這個問題，本文使用支持向量機的方法來解決。兩個物品在項目屬性上的相似度修改為：

在構(gòu)建回歸模型時，線性回歸模型難以擬合復(fù)雜的項目屬性相似度，并不能得到好的回歸效果。如上所述，支持向量機回歸（SVR）能夠通過核函數(shù)，將只包含上述自變量的低維空間，轉(zhuǎn)化為一個包含了它們非線性組合的高維自變量空間。于是本文引入SVR方法來構(gòu)建此非線性回歸模型?；诠剑?），可構(gòu)建模型如下：

為了提高算法執(zhí)行效率，本文使用序貫最小優(yōu)化（Sequential Minimal Optimization，SMO）方法[10]，一種快速支持向量機訓(xùn)練算法來求解此模型。

2.3 優(yōu)化后的推薦算法

SVR相似度優(yōu)化方法僅僅是針對基于屬性相似性的Item-Based協(xié)同過濾算法提出的一種新的計算項目屬性之間相似性的方法，因此只需要將基于屬性相似性的Item-Based協(xié)同過濾算法中的項目屬性相似性度量方法轉(zhuǎn)換為SVR相似度優(yōu)化方法，就可以得到一種新的基于屬性相似性的Item-Based協(xié)同過濾推薦算法，稱之為基于SVR的協(xié)同過濾推薦算法，簡稱SVRBased CF。

算法1 基于SVR的協(xié)同過濾推薦算法

輸入：用戶—項目評分矩陣R，項目屬性矩陣A，最近鄰居個數(shù)k，推薦集元素個數(shù)r，項目相似性平衡參數(shù)α。

輸出：推薦集rec。

（1）基于用戶—項目評分矩陣R，采用相關(guān)相似性計算項目i和項目j之間的評分相似性simRate(i，j)。

（2）基于項目屬性矩陣A，按式(4)計算任意兩個項目間的屬性相似性simAttr(i，j)，并建立項目屬性相似性矩陣simAttr(i，j)。

（3）將simRate(i，j)與simAttr(i，j)進(jìn)行線性組合，計算最終的項目相似性矩陣sim(sim為n×n方陣，其元素的值以主對角線為軸對稱分布，即sim(i，j)=sim(j，i)，如下所示：

（4）搜索項目相似性矩陣sim將相似度最高的若干項目作為目標(biāo)項目l的鄰居集合Nl={i1,i2，…，ir}，并且l埸Nl

（5）根據(jù)相似鄰居預(yù)測用戶u對未評分項目l的評分，公式如下：

其中，Nl是項目l的鄰居集合，與指項目l和p的平均評分。

（6）對用戶u未評價過的項目預(yù)測評分從大到小進(jìn)行排序，取前r個值對應(yīng)的項組成推薦集rec={i1,i2，…，ir}進(jìn)行推薦。

3 實驗及分析

3.1 數(shù)據(jù)集

數(shù)據(jù)集取自MovieLens數(shù)據(jù)集[11]，該數(shù)據(jù)集由明尼蘇達(dá)大學(xué)GroupLens研究小組通過MovieLens網(wǎng)站（http://movielens.umn.edu）收集，包含了943位用戶對1 682部電影的100 000條評分?jǐn)?shù)據(jù)，每位用戶至少對20部電影進(jìn)行了評分，所有電影分屬于19種電影類別。為了分析實驗數(shù)據(jù)稀疏性對算法性能的影響，本文從MovieLens數(shù)據(jù)集上隨機抽取100、200、300位用戶的評分?jǐn)?shù)據(jù)組成3個數(shù)據(jù)集，分別記為TDS100、TDS200、TDS300。

3.2 評價標(biāo)準(zhǔn)

評價推薦系統(tǒng)推薦質(zhì)量的度量標(biāo)準(zhǔn)采用統(tǒng)計度量方法中的平均絕對偏差MAE(Mean Absolute Error)進(jìn)行度量。MAE通過計算預(yù)測的用戶評分與實際的用戶評分之間的偏差來度量預(yù)測的準(zhǔn)確性，MAE越小，推薦質(zhì)量越高。

3.3 實驗結(jié)果及分析

實驗以傳統(tǒng)Item-based協(xié)同過濾(Item-based CF)、基于屬性相似性的Item-based協(xié)同過濾(Item feature-based CF)[3]以及基于屬性線性加權(quán)的Item-based協(xié)同過濾 (Item feature weightedbased CF)[4]為對照，檢驗本文提出的算法的有效性，計算各種推薦算法的MAE。實驗中最近鄰居個數(shù)k取30,推薦集元素個數(shù)r取10，項目相似性平衡參數(shù)α取0.6，實驗結(jié)果見表2。

表2 MAE對比結(jié)果

由表2可知，Item feature-based CF方法優(yōu)于Item-based CF方法，說明在計算項目相似性的過程中考慮項目屬性相似性,可以有效改善傳統(tǒng)協(xié)同過濾算法中面臨的“稀疏性”問題,提高推薦算法的推薦質(zhì)量。Item feature weighted-based CF方法優(yōu)于Item feature-based CF方法的性能，說明通過加權(quán)計算可以解決項目屬性重要性不同的問題，能有效改善推薦方法的性能，而本文提出的方法的MAE值較Item feature weighted-based CF方法的MAE值有大幅度的降低，說明加入支持向量機后明顯優(yōu)于線性組合的特征加權(quán)，通過支持向量機回歸方法改善項目屬性相似性的計算，能使得項目的相似性計算更加準(zhǔn)確，進(jìn)一步提高方法的性能。

4 結(jié)束語

本文提出了一種基于支持向量機回歸的協(xié)同過濾相似度優(yōu)化方法，該方法在計算項目屬性相似性時考慮了項目屬性之間的非線性關(guān)聯(lián)問題,使得項目屬性的計算更加合理。實驗結(jié)果表明,本文提出的優(yōu)化方法能夠獲得更準(zhǔn)確的項目相似性,在一定程度上提高了系統(tǒng)的推薦質(zhì)量。

[1]D Goldberg,D Nichols,B M Oki,et al.Using Collaborative Filtering to Weave an Information Tapestry[J].Communications of the ACM,1992,35 (12):61-70.

[2]P Resnick,N Iacovou,M Suchak,et al.GroupLens:An Open Architecture for Collaborative Filtering of Netnews[C].Proc.of the ACM CSCW′94 Conference on Computer Supported Cooperative Work,ACM,1994：175-186.

[3]B Sarwar,G Karypis,J Konstan,et al.Item-based Collaborative Filtering Recommendation Algorithms[C]//Proceedings of the 10th International World Wide Web Conference,2001.

[4]彭玉，程小平．基于屬性相似性的Item-based協(xié)同過濾算法［J］．計算機工程與應(yīng)用，2007，43(14):144-147．

[5]莊永龍．基于項目特征模型的協(xié)同過濾推薦算法［J］．計算機應(yīng)用與軟件，2009，26(5):244-246．

[6]張忠平，郭獻(xiàn)麗．一種優(yōu)化的基于項目評分預(yù)測的協(xié)同過濾推薦算法［J］．計算機應(yīng)用研究，2008，25(9):2659-2683．

[7]V N Vapnik.Statistical Learning Theory[M].NeuYork,NY:Wiley,1998:35-53.

[8]V Vapnik.An Overview of Statistical Learning Theory[J].IEEE Transactions on Neural Networks,1999,10(5):988-999.

[9]Smola,Scholkopf.Learning with Kernels[M].Cambridge,MA:MIT Press, 2002.

[10]Smola,Scholkopf.A Tutorial on Support Vector Regression[J].Statistics and Computing,2004(14):199-222.

[10]Miller B N，Albert I，et al.Movie Lens Unplugged:Experiences with an Occasionally Connected Recommender System[C]//Proceedings of the International Conference on Intelligent User Interfaces,2003.

10.3969/j.issn.1673-0194.2015.05.109

TP311

A

1673-0194（2015）05-0227-04

2014-12-26

教育部基金項目（14YJC630036）；中央高校專項科研基金項目（DUFE2014126）。