wordpress centos nginx Windows 云计算 php Ubuntu shell Python Firefox google 程序员 linux mysql apache java 编程 Android 微软 开源

互聯網推薦系統比較研究

互聯網規模和覆蓋面的迅速增長帶來了信息超載(information overload)的問題:過量信息同時呈現使得用戶無法從中獲取對自己有用的部分,信息使用效率反而降低。現有的很多網絡應用,比如門戶網站、搜索引擎和專業數據索引本質上都是幫助用戶過濾信息的手段。然而這些工具只滿足主流需求,沒有個性化的考慮,仍然無法很好地解決信息超載的問題。推薦系統(recommender system)作為一種信息過濾的重要手段,是當前解決信息超載問題的非常有潛力的方法。推薦系統與以搜索引擎為代表的信息檢索(information retrieval)系統最大的區別在於:

搜索註重結果(如網頁)之間的關系和排序,推薦還研究用戶模型(user profile)和用戶的喜好,基於社會網絡(social network)進行個性化的計算(personalization);
搜索的進行由用戶主導,包括輸入查詢詞和選擇結果,結果不好用戶會修改查詢再次搜索。而推薦是由系統主導用戶的瀏覽順序,引導用戶發現需要的結果。高質量的推薦系統會使用戶對該系統產生依賴。
因此,推薦系統不僅能夠為用戶提供個性化的服務,而且能夠與用戶建立長期穩定的關系,提高用戶忠誠度,防止用戶流失。

推薦系統最典型的應用是在B2C電子商務領域,具有良好的發展和應用前景,商家根據用戶的興趣、愛好推薦顧客可能感興趣或滿意的商品(如書籍、音像等)。顧客的需求通常是不明確的、模糊的,如果商家能夠把滿足用戶模糊需求的商品推薦給用戶,就可以把用戶的潛在需求轉化為現實需求,從而達到提高產品銷售量的目的。目前,幾乎所有的大型電子商務系統,如Amazon、eBay等,都不同程度地使用了各種形式的推薦系統。其中Amazon研究電子商務的推薦系統長達10年時間.各種提供個性化服務的Web站點,如電影、音樂網站,也需要推薦系統的大力支持。表1中按照應用領域分類列舉了一些典型的商用推薦系統。

在學術界,自20世紀90年代中期出現第一批關於協同過濾的文章[1−3]以來,推薦系統在電子商務、網絡經濟學和人類社會學等領域一直保持很高的研究熱度並逐漸成為一門獨立的學科。各種推薦算法涵蓋包括認知科學、近似性理論、信息檢索[4]、管理科學[5]、市場營銷建模[6]等在內的眾多研究領域[7].近幾年來,國際學術界針對計算機網絡信息整合的推薦相關的研究大量出現:

ACM設立推薦系統年會(ACM recommender systems);
計算機領域的人機交互、數據挖掘和機器學習頂級會議(SIGCHI、KDD、SIGIR、WWW等)中,推薦算法的文章逐年增加;
國際數據分析領域的高階期刊(如IEEE Trans. on Knowledge and Data Engineering,ACM Trans. on Information System等)刊載數篇推薦系統方面的文章。
信息領域做推薦系統領先的研究單位(學者)包括:紐約大學(Alexander Tuzhilin)、明尼蘇達州立大學的GroupLens研究小組(Joseph A. Konstan,John Riedl等)、美國密歇根大學(Paul Resnick)、卡內基梅隆大學(Jaime Callan)、微軟研究院(Ryen w. White)等。其中,美國密歇根大學在2006年開授了由Paul Resnick主講的推薦系統的課程。推薦系統,結合社會網絡和語義網絡的研究,面向互聯網發展中出現的新問題和新技術需求,具有廣泛的研究和應用前景。

本研究調研了推薦系統在計算機網絡和信息領域的主流研究與應用進展。本文第1節中給出推薦系統的形式化定義。第2節根據推薦算法的類別分類陳述最新的學術進展。第3節討論使用的數據集以及實驗評測方法,對當前推薦系統的研究難點進行歸納並對比各種推薦方法的優、缺點。第4節對推薦系統有待深入的研究點和發展趨勢進行初步預測。

1 推薦系統概念和形式化定義

目前被廣泛引用的推薦系統的非形式化概念是Resnick和Varian在1997年[8]給出的:“它是利用電子商務網站向客戶提供商品信息和建議,幫助用戶決定應該購買什麽產品,模擬銷售人員幫助客戶完成購買過程”。推薦有3個組成要素:推薦候選對象、用戶、推薦方法。通用的推薦系統模型流程如圖1所示。用戶可以向推薦系統主動提供個人偏好信息或推薦請求,或者用戶不提供,而是推薦系統主動采集。推薦系統可以使用不同的推薦策略進行推薦,如將采集到的個性化信息和對象數據進行計算得到推薦結果,或者直接基於已建模的知識數據庫進行推薦。推薦系統將推薦結果返回給用戶使用。

此外,文獻[7]給出了推薦系統的形式化定義:設C是所有用戶(user)的集合,S是所有可以推薦給用戶的對象(object)的集合。實際中,C和S集合的規模通常很大,如上百萬的顧客以及上億種歌曲等。設效用函數u()可以計算對象s對用戶c的推薦度(如提供商的可靠性(vendor reliability)和產品的可得性(product availability)等),即u: C×S→R,R是一定範圍內的全序的非負實數,推薦要研究的問題就是找到推薦度R最大的那些對象s*,如式(1)。

用戶和對象的度量與采樣可以使用不同的屬性和特征,這根據實際面對的問題不同而不同。推薦算法研究的中心問題是效用度u的計算,並非遍歷整個C×S的整個空間,而是分布到一個流形子空間(manifold)上。對於某個數據集而言,必須先對u進行外推(extrapolation),也就是說,對象必須具備用戶以前作的評分(rating),未評定(unrated)的對象的評分必須先根據已標註的對象進行標註外推後才可以使用。各類推薦算法在外推和評分預測(rating propagation)上采用了不同的策略,設計了不同的效用函數,這些將在下一節中分類介紹。

2 現有的推薦算法

推薦算法是整個推薦系統中最核心和關鍵的部分,在很大程度上決定了推薦系統類型和性能的優劣。目前,對推薦系統的分類並沒有統一的標準,很多學者從不同角度對推薦方法進行了不同的劃分[9−11]。但主流的推薦方法基本包括以下幾種:基於內容推薦、協同過濾推薦、基於知識推薦和組合推薦。本節我們將分類討論推薦算法的研究成果,下一節我們將討論這幾類推薦算法各自的優、缺點和推薦系統研究的重點、難點問題。

2.1 基於內容的推薦

基於內容的推薦(content-based recommendation)是指根據用戶選擇的對象,推薦其他類似屬性的對象作為推薦,屬於Schafer劃分中[10]的Item-to-Item Correlation方法。這類算法源於一般的信息檢索方法[4]。不需要依據用戶對對象的評價意見。對象使用通過特征提取方法得到的對象內容特征來表示,系統基於用戶所評價對象的特征,學習用戶的興趣,從而考察用戶資料與待預測項目相匹配的程度。對象內容特征(Content(s))的選取在目前的研究中以對象的文字描述為主,比如信息檢索中最經典的文本特征是詞頻-倒排文檔頻率(term frequency–inverse document frequency,簡稱TF-IDF)[8].。另一方面,用戶的資料模型ContentBasedProfile(c)取決於所用機器學習方法,常用的有決策樹、貝葉斯分類算法[12,13]、神經網絡、基於向量的表示方法等,數據挖掘領域的眾多算法都可以應用。結合對象內容特征和用戶資料模型,最終的效用函數可以定義為[7]

Score的計算有不同的方法,比如使用最簡單的向量夾角余弦的距離計算方法:

最後得到的u數值用於排序對象,將最靠前的若幹個對象作為推薦。基於內容推薦的其他研究還包括自適應過濾[14,15]和閾值設定[16,17]等,前者關註如何通過不斷到來的對象增量地計算ContentBasedProfile(c),使其更加準確;後者研究用戶查詢文字和對象特征的匹配方法,從而更精確地計算Content(c)。

2.2 協同過濾推薦

協同過濾推薦(collaborative filtering recommendation)技術是推薦系統中最為成功的技術之一,它於20世紀90年代開始研究並促進了整個推薦系統研究的繁榮。大量論文和研究都屬於這個類別。

協同過濾的基本思想是:找到與當前用戶ccur相似(比如興趣和口味相似)的其他用戶cj,計算對象s對於用戶的效用值u(cj,s),利用效用值對所有s進行排序或者加權等操作,找到最適合ccur的對象s*。其基本思想非常易於理解,在日常生活中,我們往往會利用好朋友的推薦來進行一些選擇。協同過濾正是把這一思想運用到推薦系統中來,即基於其他用戶對某一內容的評價向目標用戶進行推薦。

基於協同過濾的推薦系統可以說是從用戶的角度進行推薦的,並且是自動的,也就是說,用戶所獲得的推薦是系統從用戶購買或瀏覽等行為中隱式獲得的,不需要用戶主動去查找適合自己興趣的推薦信息,如填寫一些調查表格等。其另外一個優點是對推薦對象沒有特殊的要求(而基於內容的推薦需要對推薦對象進行特征分析),能夠處理非結構化的復雜對象,如音樂、電影等。同時,研究用戶之間的關系需要大量的用戶訪問行為的歷史數據,與社會網絡研究有交叉點,有豐富的研究基礎和廣闊的前景。對協同過濾最早的研究有Grundy system[18],後來的研究成果包括Tapestry system[19],GroupLens[20],Ringo[1],PHOAKS system[21],Jester system[22]等。總體而言,此類推薦算法可以分為兩類[7]:啟發式(heuristic-based or memory-based)方法和基於模型(model-based)的方法。

1) 啟發式方法

啟發式方法[23,24]的基本思想是使用與新用戶c相似的用戶c′對一個對象s的評價來預測s對新用戶c的效用,進而判斷是否推薦s給c。顯然,,啟發式方法的研究主要包括兩點:(1) 計算用戶之間的相似度;(2) 對所有與用戶c相似的用戶c′對對象s的評分進行聚合計算,以得到s對新用戶c的效用的統計預測方法。

在用戶相似度sim(c,c′)這個研究點上,主流的思路是根據用戶對同一對象的評分的差異來判斷用戶興趣的相似性。評分屬於用戶的瀏覽歷史行為,可以是打分、觀看次數、停留時間等。最基本的兩種計算sim(c,c′)的方法是基於關聯的(correlation-based)和基於余弦距離的(cosine-based)方法.基於關聯的方法研究用戶c和c′共同評分過的所有對象的評分相似度來計算關聯[1,3]。而基於余弦距離的方法直接把評分作為向量來計算余弦距離,進而得到用戶相似度[23,25]。

統計預測方法的計算公式可以形式化地表示如下[7]:

之前的研究設計了很多計算aggr的啟發式函數,幾個比較典型的例子是:

這3類aggr函數都是利用以前用戶的評價和用戶之間的相似度來啟發式地計算效用值。其中,式(5)是最簡單的形式;式(6)簡單地引入用戶相似度加權,是應用最廣的方法;考慮到不同的用戶在不同情況下作的評分可能有不同的尺度,式(7)提出進行平均歸一化的操作以消除這種尺度影響。

除了這兩個研究點之外,近年來一些學者同時也發展了其他啟發式方法,以提高啟發式推薦的性能,如缺省投票(default voting)、用戶倒排評分(inverse user frequency)、實例擴展(case amplification)[23]和主流加權預測(weighted-majority prediction)[24]等。

2) 基於模型的方法

這類方法利用用戶c對眾多對象的評分來學習一個c的模型(model)[26−30],然後使用概率方法對新的對象s的推薦效用進行預測。文獻[7]對這種方法的形式化描述如式(8)所示:

這樣,基於模型的方法把一個用戶歸類到一種模型下或者一個類型中。其他的算法還包括利用機器學習方法[26]和統計模型[30]、貝葉斯模型[31]、概率相關模型[27]、線性回歸模型[25]和最大熵模型[32]。Shani在文獻[33]中還把推薦選擇看作序列決策問題(sequential decision problem),使用馬爾可夫決策過程方法(Markov decision processes)加以解決。圖模型方法,包括概率隱形語義分析(probabilistic latent semantic analysis)[28]和LDA(latent dirichlet allocation)[29],也應用於協同過濾推薦算法的研究。

2.3 基於知識的推薦

基於知識的推薦(knowledge-based recommendation)[34]在某種程度上可以看成是一種推理(inference)技術。它不是建立在用戶需要和偏好基礎上推薦的,而是利用針對特定領域制定規則(rule)來進行基於規則和實例的推理(case-based reasoning)。例如,文獻[34]中利用飯店的菜式方面的效用知識,推薦飯店給顧客。效用知識(functional knowledge)是一種關於一個對象如何滿足某一特定用戶的知識,因而能夠解釋需求和推薦的關系,用於推薦系統。效用知識在推薦系統中必須以機器可讀的方式存在(ontology本體知識庫),例如quickstep and foxtrot systems[35]使用關於學術論文主題的ontology本體知識庫向讀者作推薦。

2.4 組合推薦

組合推薦(hybrid recommendation)的一個最重要原則就是通過組合後應能避免或彌補各自推薦技術的弱點(見第3.4節)。研究和應用最多的是內容推薦和協同過濾推薦的組合[9,36−38]。盡管從理論上有很多種推薦組合方法,但不同的組合思路適用於不同的應用場景。我們將研究人員提出的組合思路大致分為如下3類:

後融合:融合兩種或兩種以上的推薦方法各自產生的推薦結果。如使用基於內容的方法和協同過濾方法分別得到推薦列表,融合列表的結果決定最後推薦的對象。
中融合:以一種推薦方法為框架,融合另一種推薦方法。如以基於內容的方法為框架,融合協同過濾的方法,或者以協同過濾的方法為框架,融合基於內容的方法。
前融合:直接融合各種推薦方法。如將基於內容和協同過濾的方法整合到一個統一的框架模型下。
2.4.1 後融合組合推薦

在後融合組合推薦中,最簡單的做法就是分別用基於內容的方法和協同過濾推薦方法去產生一個推薦預測結果,然後用某種方法組合其結果。文獻[37]使用了評分結果的線性組合,而文獻[38]使用了投票機制來組合這些推薦結果。除此之外,也可以分別考察兩個推薦列表,判斷使用其中的哪個推薦結果。比如,Daily Learner system[39]計算推薦結果的可信度,然後選擇一個列表的結果。這種結果層次上的融合我們稱為後融合組合推薦。

2.4.2 中融合組合推薦

目前,中融合的組合推薦主要有兩種,以基於內容的方法為框架,融合協同過濾的方法和以協同過濾的方法為框架,融合基於內容的方法。前者利用降維技術把基於內容的對象特征進行精簡化。例如,文獻[40]使用了LSI(latent semantic indexing)算法,在基於內容的框架中使用精化的用戶特征向量。後者為了克服協同過濾的稀疏問題(詳見第3.3節),把用戶當作對象,使用基於內容的特征提取方法把用戶本身的特征(如年齡、工作情況等人口統計學特征(demographic features))使用到相似度計算中,而不是僅僅依賴用戶的點擊行為。Good等人在文獻[41]中引入多種不同的用戶描述符來歸類用戶,挖掘用戶的內在聯系,從而得到更好的推薦效果。文獻[42]使用獨立的基於內容的特征來補償用戶提供的簡單的rating,也屬於此類方法。

2.4.3 前融合組合推薦

近年來,這類推薦方法最受學者的關註。在文獻[36]中,研究者把用戶的年齡和電影的類型放到一個統一的分類器中訓練學習。另外一種方法[43]使用了貝葉斯混合效果回歸模型,,並通過馬爾可夫蒙特卡洛方法得到這個模型的參數。文獻[43]將用戶和對象的特征都放到一個統計模型下來計算效用函數,研究者使用用戶屬性z、對象屬性w及其交互關系(如選擇關系)x來計算效用r。對象j對於用戶i的效用值rij計算式可以表示為

這其中的3種正態分布的變量分別用於描述數據的噪聲、用戶屬性的異質性和對象屬性的異質性。式(9)表述效用值是由這幾個因素共同決定的。這3種分布的3個參數由馬爾可夫蒙特卡洛方法估算得到。

近年來,一些方法比較的工作[9,42,38]討論並實驗了各種方法與組合策略,得出結論:組合策略能夠取得比純基於內容或協同過濾方法更好的效果。這種在方法層次上融合的方法我們稱為前融合組合推薦。

3 推薦系統的重點、難點問題和主流算法對比

3.1 推薦系統的評測標準數據集

推薦系統學術研究常用的數據集包括:

MovieLens[44],MovieLens數據集中,用戶對自己看過的電影進行評分,分值為1~5。MovieLens包括兩個不同大小的庫,適用於不同規模的算法。小規模的庫是943個獨立用戶對1 682部電影作的10 000次評分的數據;大規模的庫是6 040個獨立用戶對3 900部電影作的大約100萬次評分。
EachMovie[45],HP/Compaq的DEC研究中心曾經在網上架設EachMovie電影推薦系統對公眾開放。之後,這個推薦系統關閉了一段時間,其數據作為研究用途對外公布,MovieLens的部分數據就是來自於這個數據集的。這個數據集有72 916個用戶對1 628部電影進行的2 811 983次評分。早期大量的協同過濾的研究工作都是基於這個數據集的。2004年HP重新開放EachMovie,這個數據集就不提供公開下載了。
BookCrossing[46],這個數據集是網上的Book-Crossing圖書社區的278 858個用戶對271 379本書進行的評分,包括顯式和隱式的評分。這些用戶的年齡等人口統計學屬性(demographic feature)都以匿名的形式保存並供分析。這個數據集是由Cai-Nicolas Ziegler使用爬蟲程序在2004年從Book-Crossing圖書社區上采集的。
Jester Joke[22],Jester Joke是一個網上推薦和分享笑話的網站。這個數據集有73 496個用戶對100個笑話作的410萬次評分。評分範圍是−10~10的連續實數。這些數據是由加州大學伯克利分校的Ken Goldberg公布的。
Netflix[47],這個數據集來自於電影租賃網址Netflix的數據庫。Netflix於2005年底公布此數據集並設立百萬美元的獎金(netflix prize[47]),征集能夠使其推薦系統性能上升10%的推薦算法和架構。這個數據集包含了480 189個匿名用戶對大約17 770部電影作的大約10億次評分。
Usenet Newsgroups[48],這個數據集包括20個新聞組的用戶瀏覽數據。最新的應用是在KDD 2007上的論文[49]。新聞組的內容和討論的話題包括計算機技術、摩托車、籃球、政治等。用戶們對這些話題進行評價和反饋。
UCI知識庫[50],UCI知識庫是Blake等人在1998年開放的一個用於機器學習和評測的數據庫,其中存儲大量用於模型訓練的標註樣本,在文獻[49]中被用於推薦系統的性能測試數據。
3.2 推薦系統的性能評測方法

推薦系統的性能指標一般有推薦的效果/精確度(effectiveness)和推薦的效率(efficiency),使用的指標有mean absolute error(MAE),root mean squared error(RMSE)和correlation。由於不同的研究工作針對不同的問題,使用不同的數據集,所以具體評測方法變化很大。比較普遍的評測方法來自於機器學習等領域的一般方法,比如數據集被分割為訓練集(probe set)和測試集(quiz set)。推薦算法的模型在訓練集上進行學習和參數調整,然後在測試集合上計算精確度和運行效率,從而達到評測目的。文獻[23]使用兩種評測方法來比較幾種協同過濾的算法性能,第1種評測得到每次推薦絕對誤差的平均值,第2種評測計算整個推薦列表的推薦精度。

3.3 推薦系統的重點、難點問題

隨著近年來對推薦系統研究的開展,很多研究中的重點、難點問題得到研究者的關註和共識[7],主要包括:

1)特征提取問題

雖然在信息檢索中,文本等對象特征的提取技術已經很成熟,但是推薦系統的對象不一定具有文本特征或者文本不足以作為描述[1],此時特征的選擇出現了問題。尤其是網絡上廣泛存在的多媒體數據如音樂、視頻、圖像等,自動化的特征提取方法需要結合多媒體內容分析領域的相關技術。另一個問題是特征的區分性問題,大規模數據情況下不同對象的特征錯配會影響系統性能。

2)模型過擬合問題(可擴展性問題)

推薦系統中推薦算法無法完全掌握用戶每個方面的興趣和需求,因為用戶之前沒有對足夠多類別的對象進行評價。過擬合現象是指系統推薦給用戶的對象與用戶剛剛看過的不是太相似,就是太不相關。模型過擬合(過學習)的問題本質上來自於數據的不完備性,這在實際應用中是無法完全避免的。在信息檢索領域這類問題廣泛存在,解決的主要方法是引入隨機性,使算法收斂到全局最優或者逼近全局最優。隨機方法包括遺傳算法[51]等。Daily Learner相關的文獻[15,39]針對這個問題考察了被推薦的對象的相關性(relevant)和冗余性(redundancy),認為被推薦的對象首先不能與用戶看過的對象重復(冗余),其次必須有相關性以相互聯系.推薦的多樣性是必不可缺的。

3)新用戶問題

系統沒有存儲或者存儲很少新用戶的信息,包括查看對象的歷史記錄和新用戶對對象的評分,基於模型的方法無法獲得訓練數據而基於規則的方法難以進行推理。近期一些研究特別針對這個問題提出了解決方法。文獻[52,53]利用對象熵(entropy)、受歡迎程度(popularity)、用戶個性屬性等來改進效果。

4)新對象問題

新用戶和新對象問題都屬於冷啟動問題。在推薦系統尤其是協同過濾系統中,新對象加入數據庫後必須等待一段時間才有用戶查看並進行評價(點擊、打分、評論等都是評價的手段)。在評價達到一定數量之前無法對此對象進行分析和推薦。不同於新用戶問題,這類問題一般考慮使用組合推薦的方法來應對。

5)稀疏問題

在任何大型的推薦系統中,對於一個用戶,總有大量的對象沒有經過用戶的評價或者查看,而且這類數據常常比已經有此用戶評價的數據量更大[7]。用戶之間由於選擇的差異性非常大造成稀疏情況,即任意兩個用戶的評分差別都非常大。文獻[38]提出初步的解決方法,將用戶的年齡、國籍、性別等個人信息增加作為用戶相似度計算的根據,稱為基於人口統計學的過濾方法(demographic filtering)。文獻[26,54]使用主分量分析(SVD)降維方法嘗試把稀疏的關系矩陣降維到低維,以得到用戶之間潛在的關系。

3.4 各類推薦方法的對比

各類推薦方法都有其各自的優、缺點,針對不同的數據集,效果也有所不同。每種方法因為算法本身的特征可能不適合在所有數據集上作推薦。如在基於內容的推薦方法中,自動化的特征提取方法很難應用於多媒體數據,即使在容易提取特征的文本數據的情況下,也無法僅僅通過詞頻統計的方式區分文檔質量[4]。除此之外,為用戶推薦的內容僅限於與該用戶曾經選擇的對象相似的對象,結果多樣性差。而對於沒有選擇過任何對象的新用戶,推薦尤其困難。協同過濾的方法從某種程度上克服了基於內容方法自動化程度低、推薦結果不豐富等弊端。但是,協同過濾是基於大量歷史數據集的,因而存在稀疏問題和冷啟動問題。在冷啟動方面,由於協同過濾是依靠人與人之間選擇內容的相似度進行推薦的,因此。與基於內容的方法相比,不但存在新用戶問題[53],而且還存在新對象問題,即剛剛加入的對象如果沒有被任何人選擇過,就很難被推薦[7]。基於知識的推薦是一種靜態的推薦方法,不存在冷啟動和稀疏問題,但知識很難建模。組合推薦策略由於組合方式不同,其性能特點差異很大,故不在此討論範圍內。幾種推薦方法的優、缺點具體比較見表2。

4 推薦系統研究發展的熱點方向

推薦系統的研究發展多年,曾經一度進入低潮期。近年來,機器學習、大規模網絡應用需求和高性能計算的發展推動了這個研究領域的新進展,可以深入並可能取得成果的方向很多,主要包括:

1)引入更精確適用的用戶和對象特征(new profiles of user and item)[7]

針對特定問題適用的用戶和對象特征通常可以作為模型訓練的樣本。典型的協同過濾方法[1−3]並沒有使用用戶和對象特征,而是利用用戶的評分。文獻[13,55]只是使用簡單的特征,如對象描述的關鍵詞和用戶的人口統計學特征等。而結合數據挖掘的高層特征一般是基於網絡上下文的分析的[56],比如發現用戶瀏覽網頁和對象的時序模式。這類方法需要精準的用戶瀏覽歷史數據和先進的數據挖掘算法,尚未在基於內容和協同過濾的研究中廣泛采用。

2)推薦的多維度研究[7]

當前的大部分研究都是基於對象-用戶的二維度量空間的,未考慮相關信息(contextual information)。然而,用戶對對象的評價和選擇常常由很多環境因素來決定,比如某個對象在特定時段很流行,用戶在某個地方瀏覽對象的時候偏向於選擇某類對象等。環境因素是無法從用戶和對象的自有特征得到的,正如文獻[57,58]所指出的,推薦使用的特征維度有必要根據具體問題來增加。文獻[57]提出在多維度量空間上來定義效用函數u(),以電影推薦為例:除了看電影的人的特性和電影本身的固有描述特征以外,還有環境因素d來決定如何計算效用函數u(),d包括:1) 是一個人看電影還是和其他人一起看;2) 是去電影院看還是在網上看等;3) 看電影的時間段。基於這種多維特征的思想,文獻[43]提出使用貝葉斯模型的方法進一步擴展了這個思路。問題在於,維度的擴展與應用場景相關,其可擴展性還有待進一步改進。

3)推薦系統安全問題

協同過濾類別的推薦算法必須使用用戶的行為歷史記錄,但用戶出於保護隱私的考慮常常無法提交完整而正確的信息給推薦系統。文獻[59,60]認為良好的隱私保護機制是推薦系統獲取優質數據和忠實用戶的關鍵之一,並提出了相應的算法。同時,用戶的信用度(reputation)也是推薦算法的重要參考數據。文獻[61]提出兩種信用計算模型並用於提高推薦精度。另外,熟悉推薦算法的攻擊者惡意利用捏造的評分和對象屬性等數據欺騙推薦系統,達到被頻繁推薦的目的。文獻[62,63]中定義這類行為為用戶欺詐(shilling attack),並設計算法監控評分的時序模式,去除不正常的對象與用戶。

4)相關反饋研究(relevance feedback)與侵襲性問題

一般的推薦系統大多需要用戶依據自身對推薦對象的喜好程度,提供適當的評比反饋信息,這種評比方式稱為相關反饋(relevance feedback)。相關反饋可以分為顯性反饋(explicit feedback)和隱性反饋(implicit feedback)。目前部分推薦系統主要使用顯性反饋的方式,即需要用戶每次查看對象都進行評分或者其他操作。一些研究[20,35,64]中使用的用戶反饋的方法也屬於顯性反饋。使用這種方式來取得評價的方法對於用戶不是很友好,具有很大的侵襲性。隱性反饋使用無須用戶評價的用戶數據采集方法。在文獻[65]的研究中列舉了12種用戶在網絡上的瀏覽行為,Oard和Kim[66]延伸了文獻[65]的研究,進一步將這些行為分為3類,並增加了一種新的行為類型。文獻[67]針對隱性反饋的可靠性進行了實驗,結果顯示“使用者的閱覽時間”和“使用者是否喜歡該文章”有正向潛在關系。解決侵襲性問題的另一個研究方向是研究用戶能夠接受的評價方式是什麽,比如能夠有耐心進行幾次評分。MovieLens系統[44]利用固定負擔模型這種最簡單的算法來計量用戶評價的負擔,將侵襲性問題轉化為最優化問題來研究。

5)推薦算法的評價準則[7]

有效性和時間消耗作為推薦系統的重要指標,其評價準則的設計一直是一個熱點,但是沒有統一的結論。文獻[55,68−70]都研究過評測推薦系統性能的準則,包括查全率(coverage)和查準率(accuracy)的評測。另外,信息檢索領域使用的F-measure和ROC(receiver operating characteristic)指標也可以用於評測。第4。2節給出了部分研究工作中使用過的推薦效果度量方法。然而這些基於用戶評分的數據和評測的方法存在固有的缺陷,比如用戶的評分常常是針對他喜歡的對象,而其他對象被訪問的概率則很小。評價準則必須考慮到人類行為的特點。同時,如果召集若幹誌願者來做實時的實驗,不僅樣本量小,而且耗費的時間、人力也很昂貴。這是一個很有研究意義的方向。

6)基於復雜網絡理論及圖方法的推薦系統

近年來,機器學習、理論物理和復雜網絡系統的研究者從圖和動態復雜網絡(graph and dynamic network)的視角,開始關註推薦系統中的大規模網絡智能挖掘。文獻[71]將網絡視頻推薦問題轉化為熱量散播平衡態網絡上的譜圖分割(spectral graph partitioning)問題,通過設計長尾發現(long tail discovering)的推薦策略引導用戶發現潛在的感興趣的網絡視頻。

7)社會分化和推薦邏輯空間的巴爾幹化現象(balkanization)

以Internet為代表的信息和通信技術消除了地理壁壘,即傳統的地理空間巴爾幹(即局域性限制)。然而卻不可避免地生成了邏輯空間巴爾幹[72]。在推薦系統中根據個體興趣、學科專業、社會地位以及觀點進行推薦時尤其容易導致這種局域性限制和社會分化的出現。本質上,個體偏好關系是導致生成邏輯空間巴爾幹的原因。推薦和個性化技術所產生的一系列社會學問題,也是很重要的一個研究方向。網絡推薦中體現的其他社會學問題還包括從眾心理和行為研究,推薦與主流興趣形成的相互作用等。

5 結論

在互聯網的迅猛發展下,隨著信息過載問題的逐年升溫,互聯網用戶對信息需求的日益膨脹,推薦系統在各個領域的數字化進程中扮演著越來越重要的角色。在過去的數十年中,推薦系統在學術研究、工業界各種應用上取得了長足的進步。然而,現有的推薦算法仍然存在特征提取、冷啟動、過擬合、稀疏問題,需要不斷完善和解決。同時,多維度推薦、相關反饋、評價準則、安全性以及推薦社會學等仍然是當前進行深入研究和擴展的熱點方向。伴隨著這些問題的逐漸解決,推薦系統將在互聯網領域為用戶提供更加便捷、有效的用戶信息獲取體驗。

References: 
[1]Shardanand U, Maes P. Social information filtering: Algorithms for automating “Word of Mouth”. In: Proc. of the Conf. on Human Factors in Computing Systems. New York: ACM Press, 1995. 210−217. 
[2]Hill W, Stead L, Rosenstein M, Furnas G. Recommending and evaluating choices in a virtual community of use. In: Proc. of the Conf. on Human Factors in Computing Systems. New York: ACM Press, 1995. 194−201. 
[3]Resnick P, Iakovou N, Sushak M, Bergstrom P, Riedl J. GroupLens: An open architecture for collaborative filtering of netnews. In: Proc. of the Computer Supported Cooperative Work Conf. New York: ACM Press, 1994. 175−186. 
[4]Baeza-Yates R, Ribeiro-Neto B. Modern Information Retrieval. New York: Addison-Wesley Publishing Co., 1999. 
[5]Murthi BPS, Sarkar S. The role of the management sciences in research on personalization. Management Science, 2003,49(10): 1344−1362. 
[6]Smith SM, Swinyard WR. Introduction to marketing models. 1999.http://marketing.byu.edu/htmlpages/courses/693r/modelsbook/preface.html 
[7]Adomavicius G, Tuzhilin A. Toward the next generation of recommender systems: A survey of the state-of-the-art and possible extensions. IEEE Trans. on Knowledge and Data Engineering, 2005,17(6):734−749. 
[8]Resnick P, Varian HR. Recommender systems. Communications of the ACM, 1997,40(3):56−58. 
[9]Balabanovic M, Shoham Y. Fab: Content-Based, collaborative recommendation. Communications of the ACM, 1997,40(3):66−72. 
[10]Schafer JB, Konstan J, Riedl J. Recommender systems in e-commerce. In: Proc. of the 1st ACM Conf. on Electronic Commerce. New York: ACM Press, 1999. 158−166. 
[11]Terveen L, Hill W. Beyond recommender systems: Helping people help each other. In: Carroll J, ed. HCI in The New Millennium. New York: Addison-Wesley Publishing Co., 2001. 1−21. 
[12]Mooney RJ, Bennett PN, Roy L. Book recommending using text categorization with extracted information. In: Proc. of the AAAI’98/ICML’98 Workshop on Learning for Text Categorization. Madison: AAAI Press, 1998. 49−54. 
[13]Pazzani M, Billsus D. Learning and revising user profiles: The identification of interesting Web sites. Machine Learning, 1997, 27(3):313−331. 
[14]Somlo G, Howe A. Adaptive lightweight text filtering. In: Proc. of the 4th Int’l Symp. on Intelligent Data Analysis. Berlin, Heidelberg: Springer-Verlag, 2001. 319−329. 
[15]Zhang Y, Callan J, Minka T. Novelty and redundancy detection in adaptive filtering. In: Proc. of the 25th Annual Int’l ACM SIGIR Conf. New York: ACM Press, 2002. 81−88. 
[16]Robertson S. Threshold setting and performance optimization in adaptive filtering. Information Retrieval, 2002,5(2-3):239−256. 
[17]Zhang Y, Callan J. Maximum likelihood estimation for filtering thresholds. In: Proc. of the 24th Annual Int’l ACM SIGIR Conf. New York: ACM Press, 2001. 294−302. 
[18]Rich E. User modeling via stereotypes. Cognitive Science, 1979,3(4):329−354. 
[19]Goldberg D, Nichols D, Oki BM, Terry D. Using collaborative filtering to weave an information tapestry. Communications of the ACM, 1992,35(12):61−70. 
[20]Konstan JA, Miller BN, Maltz D, Herlocker JL, Gordon LR, Riedl J. GroupLens: Applying collaborative filtering to usenet news. Communications of the ACM, 1997,40(3):77−87. 
[21]Terveen L, Hill W, Amento B, McDonald D, Creter J. PHOAKS: A system for sharing recommendations. Communications of the ACM, 1997,40(3):59−62. 
[22]Goldberg K, Roeder T, Gupta D, Perkins C. Eigentaste: A constant time collaborative filtering algorithm. Information Retrieval, 2001,4(2):133−151. 
[23]Breese JS, Heckerman D, Kadie C. Empirical analysis of predictive algorithms for collaborative filtering. Technical Report, MSR-tr-98-12, Redmond: Microsoft Research, 1998. 
[24]Delgado J, Ishii N. Memory-Based weighted-majority prediction for recommender systems. In: Proc. of the ACM SIGIR’99 Workshop Recommender Systems: Algorithms and Evaluation. New York: ACM Press, 1999. 
[25]Sarwar B, Karypis G, Konstan J, Riedl J. Item-Based collaborative filtering recommendation algorithms. In: Proc. of the 10th Int’l WWW Conf. New York: ACM Press, 2001. 285−295. 
[26]Billsus D, Pazzani M. Learning collaborative information filters. In: Proc. of Int’l Conf. on Machine Learning. San Francisco: Morgan Kaufmann Publishers Inc., 1998. 46−54. 
[27]Getoor L, Sahami M. Using probabilistic relational models for collaborative filtering. In: Proc. of the Workshop Web Usage Analysis and User Profiling. 1999. 
[28]Hofmann T. Collaborative filtering via Gaussian probabilistic latent semantic analysis. In: Proc. of the 26th Int’l ACM SIGIR Conf. New York: ACM Press, 2003. 259−266. 
[29]Marlin B. Modeling user rating profiles for collaborative filtering. In: Proc. of the 17th Annual Conf. on Neural Information Processing Systems. Cambridge: MIT Press, 2003. 627−634. 
[30]Ungar LH, Foster DP. Clustering methods for collaborative filtering. In: Proc. of the Workshop on Recommendation Systems. Menlo Park: AAAI Press, 1998. 112−125. 
[31]Chien YH, George EI. A Bayesian model for collaborative filtering. In: Proc. of the 7th Int’l Workshop on Artificial Intelligence and Statistics. San Francisco: Morgan Kaufmann, 1999. 
[32]Pavlov D, Pennock D. A maximum entropy approach to collaborative filtering in dynamic, sparse, high-dimensional domains. In: Proc. of the 16th Annual Conf. on Neural Information Processing Systems. 2002. 
[33]Shani G, Brafman R, Heckerman D. An MDP-based recommender system. The Journal of Machine Learning Research, 2005,6:1265−1295. 
[34]Burke R. Knowledge-Based recommender systems. Encyclopedia of Library and Information Systems, 2000,69(32):180−200. 
[35]Middleton SE, Shadbolt NR, de Roure DC. Ontological user profiling in recommender systems. ACM Trans. on Information Systems, 2004,22(1):54−88. 
[36]Basu C, Hirsh H, Cohen W. Recommendation as classification: Using social and content-based information in recommendation. In: Proc. of the AAAI’98. Menlo Park: AAAI Press. 1998. 714−720. 
[37]Claypool M, Gokhale A, Miranda T, Murnikov P, Netes D, Sartin M. Combining content-based and collaborative filters in an online newspaper. In: Proc. of the ACM SIGIR’99 Workshop Recommender Systems: Algorithms and Evaluation. New York: ACM Press, 1999. 
[38]Pazzani M. A framework for collaborative, content-based, and demographic filtering. Artificial Intelligence Review, 1999,13(5-6): 393−408. 
[39]Billsus D, Pazzani M. User modeling for adaptive news access. User Modeling and User-Adapted Interaction, 2000,10(2-3): 147−180. 
[40]Soboroff I, Nicholas C. Combining content and collaboration in text filtering. In: Proc. of the Int’l Joint Conf. on Artificial Intelligence Workshop: Machine Learning for Information Filtering. Stockholm, 1999. 86−91. 
[41]Good N, Schafer JB, Konstan JA, Borchers A, Sarwar B, Herlocker JL, Riedl J. Combining collaborative filtering with personal agents for better recommendations. In: Proc. of the 16th National Conf. on Artificial Intelligence. Menlo Park: AAAI Press, 1999. 439−446. 
[42]Melville P, Mooney RJ, Nagarajan R. Content-Boosted collaborative filtering for improved recommendations. In: Proc. of the 18th National Conf. on Artificial Intelligence. Menlo Park: American Association for Artificial Intelligence, 2002. 187−192. 
[43]Ansari A, Essegaier S, Kohli R. Internet recommendations systems. Journal of Marketing Research, 2000,37(3):363−375. 
[44]Miller BN, Albert I, Lam SK, Konstan JA, Riedl J. MovieLens unplugged: Experiences with an occasionally connected recommender system. In: Proc. of the Int’l Conf. on Intelligent User Interfaces. New York: ACM Press, 2003. 263−266. 
[45]EachMovie. EachMovie collaborative filtering data set. 1997. http://research.compaq.com/SRC/eachmovie 
[46]http://www.bookcrossing.com/

延伸阅读

    评论