呂成戍，蓋 印，匡宇鵬

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

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

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

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

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

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

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

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

0 引 言

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

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

1 支持向量機(jī)回歸

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

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

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

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

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

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

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

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

2.1 項(xiàng)目的特征屬性

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

表1 項(xiàng)目屬性矩陣A

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

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

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

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

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

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

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

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

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

輸出：推薦集rec。

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

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

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

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

（5）根據(jù)相似鄰居預(yù)測(cè)用戶u對(duì)未評(píng)分項(xiàng)目l的評(píng)分，公式如下：

其中，Nl是項(xiàng)目l的鄰居集合，與指項(xiàng)目l和p的平均評(píng)分。

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

3 實(shí)驗(yàn)及分析

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

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

3.2 評(píng)價(jià)標(biāo)準(zhǔn)

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

3.3 實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)以傳統(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]為對(duì)照，檢驗(yàn)本文提出的算法的有效性，計(jì)算各種推薦算法的MAE。實(shí)驗(yàn)中最近鄰居個(gè)數(shù)k取30,推薦集元素個(gè)數(shù)r取10，項(xiàng)目相似性平衡參數(shù)α取0.6，實(shí)驗(yàn)結(jié)果見表2。

表2 MAE對(duì)比結(jié)果

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

4 結(jié)束語

本文提出了一種基于支持向量機(jī)回歸的協(xié)同過濾相似度優(yōu)化方法，該方法在計(jì)算項(xiàng)目屬性相似性時(shí)考慮了項(xiàng)目屬性之間的非線性關(guān)聯(lián)問題,使得項(xiàng)目屬性的計(jì)算更加合理。實(shí)驗(yàn)結(jié)果表明,本文提出的優(yōu)化方法能夠獲得更準(zhǔn)確的項(xiàng)目相似性,在一定程度上提高了系統(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］．計(jì)算機(jī)工程與應(yīng)用，2007，43(14):144-147．

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

[6]張忠平，郭獻(xiàn)麗．一種優(yōu)化的基于項(xiàng)目評(píng)分預(yù)測(cè)的協(xié)同過濾推薦算法［J］．計(jì)算機(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

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