基于模糊處理和上下文敏感SVM的協同過濾推薦新方法

摘要:協同過濾系統是電子商務最重要的技術之一，用戶相似度算法的優劣直接決定推薦性能的準確程度。現有推薦方法忽略用戶上下文特征，因而用戶相似度判定較差。針對該問題，該文提出了FSVMCF方法，該方法采取模糊上下文數據及上下文敏感 SVM和協同過濾相結合方法，提高了推薦準確度。該文實驗以汽車、飛機、火車等交通工具圖像作為推薦對象，實驗結果驗證了該方法對于圖像推薦的性能有較大提高。

關鍵詞:圖像推薦;模糊處理;上下文敏感;支撐向量機

A New Image Recommendation Algorithm Based on Fuzzy and Context-aware SVM

MA Xiang1， LI Zhan2

(1.PianZhuan Group Information Center， Xianyang 712000， China; 2.Department of Information， Northwest University， Xi'an 710069， China)

Abstract: Recommendation system is one of the most important technologies applied in e-commerce. The Similarity measuring method is fundamental to recommendation system's performance. The Traditional methods ignore the context， so it brings poor similarity result. Based on fuzzy and context-aware SVM， a novel similarity measuring method FSVMCF has proposed to solve this problem. By using the images containing car， plane and train. the experimental results show that this method can efficiently improve the recommendation system's performance， and provide better recommendation results than traditional collaborative filtering algorithms.

Key words: image recommendation; fuzzy; context-aware; SVM

隨著Internet信息爆炸式發展，用戶主動方式獲取信息變得越來越困難[1]。網絡信息獲取方式經歷了信息檢索(IR)，信息過濾(IF)[2]到信息推薦(RS)[3]過程。針對Internet用戶，推薦系統利用用戶評價信息以幫助用戶迅速、快捷地獲取需要信息[3]。圖1是IR、IF和RS之間的關系。

推薦系統(RS)已成為電子商務領域一個重要的研究內容。目前幾乎所有的大型電子商務網站，如Amazon， eBay，阿里巴巴，豆瓣等都采用了各種形式的推薦系統。

Typestry[4]是最早提出基于協同過濾的推薦系統，當前目標用戶需要明確指出與自己行為比較類似的其他用戶。GroupLens[5]是基于用戶評分的自動化協同過濾推薦系統，用于推薦電影和新聞。Ringo推薦系統[6]和Video推薦系統通過電子郵件的方式分別推薦音樂和電影。Breese[7]等人對各種協同過濾推薦算法及其改進進行了深入分析。

傳統的協同過濾推薦通過用戶的最近鄰居產生最終的推薦，基于項目的協同過濾推薦首先計算項目之間的相關性，然后通過用戶對相關項目的評分預測用戶對未評分項目的評分[8]。Bayesian網絡技術利用訓練集創建相應的模型[9]，模型用決策樹表示，節點和邊表示用戶信息。訓練得到的模型非常小，所以對模型的應用非常快。這種方法適合于用戶的興趣愛好變化比較慢的場合。聚類技術將具有相似興趣愛好的用戶分配到相同的簇中[10-11]，聚類產生之后，根據簇中其他用戶對商品的評價預測目標用戶對該商品的評價。關聯規則挖掘可以發現不同商品在銷售過程中的相關性。基于關聯規則的推薦算法根據生成的關聯規則模型和用戶當前的購買行為向用戶產生推薦[12]。關聯規則模型的生成可以離線進行，因此可以保證有效地推薦系統的實時性要求。Horting圖技術是一種基于圖的方法[13]，節點代表用戶，邊代表兩個用戶之間的相似度。在圖中搜索近鄰節點，然后綜合近鄰節點的評分形成最后的推薦。Horting圖技術可以跳過中間節點尋找最近鄰居，考慮了節點之間的傳遞相似關系。

目標用戶對推薦信息接受與否，很大程度受上下文環境影響，因此忽略上下文信息會降低推薦的質量。本文提出了一種基于模糊處理和上下文敏感 SVM的協同過濾圖像推薦方法(FSVMCF)以提高圖像推薦系統的性能。為了驗證本文提出的方法，我們在LabelMe和Google搜索的圖像上進行實驗。

本文其余章節組織如下:第一部分為傳統相似性度量方法介紹及其分析;第二部分給出了上下文概念，同時提出模糊化上下文信息及上下文SVM和協同過濾結合的具體方法。第三部分針對汽車、飛機、火車等圖像進行實驗，將傳統協同過濾法和本方法進行了比較，最后給出了實驗結果。第四部分總結了本文的工作。

1 傳統相似性度量方法介紹及其分析

推薦系統通常采用協同過濾算法進行推薦。協同過濾算法根據鄰居用戶的評價對當前目標用戶生成推薦表。在這里存在一個假定[8]，認為任何人的興趣都不是孤立的，歸屬于某個群體所關心的興趣中。該算法使用統計算法尋找與目標用戶有相同愛好的鄰居，然后根據目標用戶多個鄰居的觀點向目標客戶進行推薦。

協同過濾推薦過程可分成三個步驟。

1)計算當前目標用戶和推薦系統所有用戶的相關性;

2)通過評估算法，選擇和當前目標用戶相似性較高的鄰居用戶;

3)基于選中鄰居用戶，提交推薦信息給當前目標用戶。

為了尋找當前目標用戶的鄰居，需度量用戶之間的相似性。根據相似性，選擇相似程度最高的若干個用戶作為當前目標用戶的鄰居。鄰居用戶的判斷準確與否將直接決定推薦系統的性能。用戶相似性判斷方法是整個協同推薦成功的關鍵。

用戶評分數據可以用一個m×n階矩陣x(m，n)表示，m行代表m個用戶，n列代表n個項目，第i行第j列的元素Xij代表用戶i對項目j的評分。用戶評分數據矩陣如圖2所示。

1.1 傳統相似性度量方法介紹及分析

度量用戶間相似性的方法有多種，主要包括如下3種方法:平均方差[14]、相關相似性[15]和余弦相似性[13]。

1)平均方差(MSD Mean squared difference):設m是用戶a和u都曾經評價過圖像的個數，ra，i是當前目標用戶a對項目i的評價，ru，i是用戶u對項目i的評價。則用戶a和用戶u之間的相似性sim(a，u)為:

如果用戶a和u對所有m個項目的評價完全相同，則msd值為0;如果用戶a和u對所有m個項目的評價完全相反， 則msd值為1。 Ringo音樂推薦系統使用了平均方差作為用戶a和μ的相似性判別方法。 [14]

2)相關相似性(correlation): 該方法通過計算兩個變量間的線性關系來判斷相似性。設ra，i是當前目標用戶a對項目i的評價，ru，i是用戶u對項目i的評價，ra和ru分別是和a和μ平均評價信息。 則用戶a和用戶u之間的相似性sim(a，u)為:

GroupLens則使用相關相似性作為用戶a和μ的相似性判別方法[15]。

3)余弦相似性(cosine): [13]用戶評分被看做是n維項目空間上的向量，如果用戶對項目沒有進行評分，則將用戶對該項目的評分設為0，用戶間的相似性通過向量間的余弦夾角度量。設用戶i和用戶j在n維項目空間上的評分分別表示為向量i和j， 則用戶a和用戶u之間的相似性sim(a，u)為:

2 上下文的模糊處理以及SVM和協同過濾結合方法

推薦系統中目標用戶的需求是和上下文環境密切相關的。上下文環境數據信息，如性別、年齡、所處行業、教育背景、天氣溫度、天氣濕度、天氣狀況、季節、時間、所處地點都會導致用戶對于推薦信息需求的差異。

Dey[16]在文章中將上下文環境看作用戶本身信息、用戶相關對象信息、地理位置、時間等特性的實體。

2.1 上下文模糊處理

上下文信息定義為:性別、年齡、所處行業、教育背景、天氣溫度、天氣濕度、天氣狀況、季節、時間、所處地點信息。上下文的數據信息可以通過傳感器、公共平臺網站和推薦服務系統本身提供。這些信息的獲取方法和數據類型如表1:

定義1:令Г表示上下文數據信息的集合，則Г=(Dj) j=1…m m為上下文信息的個數。令Z表示一維自然數空間，R表示一維實數空間，則?堝Dj?奐Z或?堝Dj?奐R。

定義2: 如果?堝Dj?奐Z，則Dj是離散數據，令Dj=(djk)lk=1 k為用戶個數。定義Dj歸一化操作為:

針對教育背景，規定djk=(1，2，3，4，5，6)分別對應教育程度為(小學，初中，高中，本科，碩士，博士)。針對所處行業，，規定djk=(1，2，3，4，5，6)分別對應行業(農業、工業、化工、政府、流通業、信息業)。

定義3: 如果?堝Dj?奐R，則Dj是連續數據， 且Dj=(djk)lk=1。定義Dj模糊化操作為:

通過以上模糊方法就解決了上下文數據連續信息的離散化與歸一化問題。離散歸一后的數據作為核特征向量就可應用SVM進行分類。

2.2 SVM和協同過濾

支撐向量機(SVM)是由Vapnik于1995年提出的統計學習理論，它在小樣本學習分類問題上具有優于傳統分類方法。SVM很好地解決了神經網絡分類存在的網絡結構參數選擇、以及局部極小點問題。

2.2.1 SVM介紹

在線性可分情況下，線性SVM分類器的目地就是尋找一個最優分割超平面。圖3是SVM線性可分情況。

圖3中H1和H2分別為過各類樣本中離分類線最近的點且平行于分類線的直線。H1和H2之間的距離稱為兩類分類間隙或分類間隔(margin)。尋找最優面的問題也就是要求分類面間的距離要最大化，同時最小化 || W || 2 / 2，且滿足:

yi(W·xi+b)-1≥0 i=1…l(6)

定義如下的拉格朗日函數:

如ai*為最優解，則W*=ai*yixi，得最優分類函數為f(x)=sgn{ai*yi(xi·x)+b*}。在引入核函數后，最優分類函數變為:

線性不可分的情況下，可引入容錯因子ζi≥0，懲罰因子C， K>0， 則以上問題變為:

滿足yi(W·xi+b)-(1-ζi)≥0 i=1…l，同時最小化 || W || 2/2+C(ζi)k。這樣線性不可分問題就轉變為線性可分情況。

2.2.2 上下文SVM方法論述

上下文SVM是常用SVM的擴展[17]。它將上下文信息加入SVM特征空間組成新的特征空間Λ。設樣本圖像集和其特征空間為Г和?準。定義如下:

Г={Ii}m i=1 m為圖像樣本的個數

?準={Xi i=1…k}k為特征空間的維數

上下文信息所組成的子空間規定為C={Xj j=1…l}，令新的特征空間Λ={Xt t=1…k+l}。 這樣Λ就變成了由?準和C組成的k+l維空間。其關系如圖5。

協同過濾推薦尋找當前目標用戶的鄰居，需度量用戶之間的相似性。上下文SVM方法對于用戶間相似性可以通過計算分割超平面間的相似性得到。圖6是用戶A上下文SVM模型。圖7是用戶B上下文SVM模型。

定義用戶A和用戶B的正例和反例特征為:

SAp={Xij，i=1…k+l，j=1…m1}SAn={Xij，i=1…k+l，j=1…m2}

SBp={Xij，i=1…k+l，j=1…n1}SBn={Xij，i=1…k+l，j=1…n2}

A的正例和反例特征為SAp，SAn，B的正例和反例特征為SBp，SBn。k+l是上下文信息和樣本圖像特征構成的空間維數。A的正例、反例個數分別為m1，m2。 B的正例、反例個數分為n1，n2

用戶A和用戶B相似性通過如下步驟進行計算:

1)將用戶B的訓練樣本映射到用戶A的SVM模型中，定義

Sbap=MAP(SAp) Sban=MAP(SAn)(9)

2)假定f1和f2分別為用戶A和用戶B的SVM分類函數。使用f1對Sbap和Sban進行分類，規定NAp為 映射集中分類結果仍為正例個數， NAn為Sban映射集中分類結果仍為反例個數。

3)計算用戶A相對于用戶B的相似度SimAtoB。

SimAtoB=(NAp+NAn)/(n1+n2)(n1+n2是B的樣本個數和) (10)

4)與此類似計算用戶B相對于用戶A的相似度。

SimBtoA=(MAp+MAn)/(m1+m2) (11)

MAp為用戶A的正例訓練樣本映射到用戶B的SVM模型中仍為正例的個數， MAn為用戶A的反例訓練樣本映射到用戶B的SVM模型中仍為反例的個數。

5)用戶A和B的相似性和用戶A相對于用戶B的相似度及用戶B相對于用戶A的相似度成線性關系，令

SimA-B=λSimAtoB+KSimBtoA (12)

其中:λ+K=1

2.2.3 上下文SVM和協同過濾結合方法

將上下文SVM計算的用戶相似結果與協同過濾度量用戶相似性的方法結合，可以很好的解決上下文信息對推薦性能的影響。協同過濾中度量用戶間相似性的傳統方法主要有3種方法:平均平方差、相關相似性和余弦相似性。這里協同過濾度量用戶相似性方法選擇相關相似性(correlation)計算，實踐表明GroupLens選用該計算公式取得了一定的成效。

定義SimAB為FSVMCF過濾下用戶A和用戶B的相似性，則

SimAB=αSimA-B+(1-α)sim(A，B) (13)

SimA-B為上下文SVM計算用戶A和用戶B相似性結果。sim(A，B)為相關相似性(correlation)，α為SimA-B的比例系數。

α的計算公式為:

α=Getc/2×TotalC (14)

TotalC為用戶A和用戶B上下文維數之和，Getc為用戶A獲取到上下文信息個數和用戶B獲取到上下文信息個數之和。顯然有0≤α≤0.5。無上下文信息時，FSVMCF過濾就變成了傳統的CF協同方法。

3 實驗結果及其分析

本文使用LabelMe(http://labelme.csail.mit.edu/)和Google搜索的圖像作為測試數據集。圖像集共2300張，LableMe圖像1300張，Google搜索圖像1000張。圖像中汽車圖像600張、飛機圖像900張、火車圖像800張。學習用例汽車圖像400張，飛機圖像500張，火車圖像600張。25個用戶分別對100張圖片進行評價。本文使用圖像的HSI顏色直方圖、一二三階顏色矩、Gabor小波和SIFT特征作為圖像的特征。 SVM使用Libsvm。圖8為圖像特征和部分程序界面。

推薦質量的評價標準主要有兩類:統計精度度量方法和決策支持精度度量方法[18-19]。統計精度度量方法中的平均絕對偏差MAE(mean absolute error)，是一種常用度量方法。

平均絕對偏差(MAE)通過計算預測的用戶評分與實際的用戶評分之間的偏差度量預測的準確性，MAE越小，推薦質量越高。假設預測的用戶評分集合為{p1，p2，…，pN}，對應的實際評分集合為{q1，q2，…，qN}，則MAE可由下式計算:

把本文的算法與傳統的基于平均方差法、相關相似性法和余弦法的協同過濾推薦算法進行比較。使用MAE為度量標準，得到如圖9所示的MAE隨最近鄰居數變化而變動的折線圖。可見，本文提出的算法有較好的性能表現。

4 結束語

本文首先深入分析了協同過濾相似性判別法， 平均方差、相關相似性和余弦相似性度量方法在計算目標用戶的最近鄰居時存在未考慮上下文信息問題。針對上述問題，提出了一種FSVMCF過濾推薦算法，這種方法可以有效地解決上述度量方法存在的不足，使得計算得到的目標用戶的最近鄰居比較準確。實驗結果表明，基于模糊處理和上下文敏感SVM的協同過濾算法可以有效地解決用戶推薦需求和上下文相關時，傳統的相似性度量方法存在的弊端，顯著地提高推薦系統的推薦質量。

參考文獻:

[1] Resnick P，Iacovou N，Suchak M，et al.GroupLens:An Open Architecture for Collaborative Filtering of Netnews[C].Proceedings of ACM Conference on Computer Supported Cooperative Work，1994:1-2.

[2] Resnick P，Varian H R.Recommender systems，volume 40[M].ACM Press，1997:1-8.

[3] Melville P，Mooney R，Nagarajan R.Content-boosted collaborative Filtering，volume 40[C].Proceedings of the 2001:1-2.

[4] Goldberg D，Nichols D，Oki B M，et al.Using collaborative filtering to weave an information tapestry[J].Communications of the ACM，1992，35(12):61-70.

[5] Resnick P，Iacovou N，Suchak M，et al.Grouplens:An open architecture for collaborative filtering of netnews[C].Proceedings of the ACM CSCW’94 Conference on Computer-Supported Cooperative Work，1994:175-186.

[6] Shardanand U，Maes P.Social information filtering:Algorithms for automating \"Word of Mouth\"[C].Proceedings of the ACM CHI’95 Conference on Human Factors in Computing Systems，1995:210-217.

[7] Hill W，Stead L，Rosenstein M，Furnas G.Recommending and evaluating choices in a virtual community of use[C].Proceedings of the CHI’95，1995:194-201.

[8] Sarwar B，Karypis G，Konstan J，et al.Item-Based collaborative filtering recommendation algorithms[C].Proceedings of the 10th International World Wide Web Conference，2001:285-295.

[9] Chickering D，Hecherman D.Efficient approximations for the marginal likelihood of Bayesian networks with hidden variables[J].Machine Learning，1997，29(2/3):181-212.

[10] Dempster A，Laird N，Rubin D.Maximum likelihood from incomplete data via the EM algorithm[J].Journal of the Royal Statistical Society，1977，B39:1-38.

[11] Thiesson B，Meek C，Chickering D，et al.Learning mixture of DAG models[R].Technical Report，MSR-TR-97-30，Redmond:Microsoft Research，1997.

[12] Sarwar B，Karypis G，Konstan J，et al.Analysis of recommendation algorithms for E-commerce[C].ACM Conference on Electronic Commerce.2000:158-167.

[13] Wolf J，Aggarwal C，Wu K-L，et al.Horting hatches an egg:A new graph-theoretic approach to collaborative filtering[C].San Diego:Proceedings of the ACM SIGMOD International Conference on Knowledge Discovery and Data Mining，1999:201-212.

[14] Shardanand U，Maes P.Social information Filtering:algorithms for automating word of mouth[M].ACM，1995:210-217.

[15] Resnick P，Iacovou N，Suchak M，et al.GroupLens:An Open Architecture for Collaborative Filtering of Netnews[C].Proceedings of ACM Conference on Computer Supported Cooperative Work，1994:1-37.

[16] Dey.Understanding and using context[J].Personal and Ubiquitous Computing，2001，5(1):18-20.

[17] Oku K.Context-Dependent Information Recommendation using SVM[Z].2006:109-113.

[18] Zhang B Q.A collaborative filtering recommendation algorithm based on domain knowledge[J].Computer Engineering，2005，31(21):7-9.

[19] Sarwar B，Karypis G，Konstan J，et al.Item-Based collaborative filtering recommendation algorithms[C]//Proc.of the 10th Int'l World Wide Web Conf.Hong Kong:ACM Press，2001:285-295.