協同過濾(collaborative filtering)是一種在推薦系統中廣泛使用的技術。該技術通過分析使用者或者事物之間的相似性(「協同」),來預測使用者可能感興趣的內容並將此內容推薦給使用者。這裡的相似性可以是人口特徵(性別、年齡、居住地等)的相似性,也可以是歷史瀏覽內容的相似性(比如都關注過和中餐相關的內容),還可以是個人通過一定機制給予某個事物的回應(比如一些教學網站會讓使用者對授課人進行評分)。比如,使用者A和B都是居住在北京的年齡在20-30歲的女性,並且都關注過化妝品和衣物相關的內容。這種情況下,協同過濾可能會認為,A和B相似程度很高。於是可能會把A關注B沒有關注的內容推薦給B,反之亦然。

發展簡史

編輯

以下就「協同過濾」發展歷史上幾個重要的里程碑做相關闡述:

Tapestry(1992)

編輯

這是最早應用協同過濾系統的設計,主要是解決Xerox公司帕羅奧多研究中心資訊過載的問題。這個研究中心的員工每天會收到非常多的電子郵件卻無從篩選分類,於是研究中心便發展這項實驗性的郵件系統來幫助員工解決這項問題。 其運作機制大致如下:

  • 個人決定自己的感興趣的郵件類型;
  • 個人隨機發出一項資訊需求,可預測的結果是會收到非常多相關的檔案;
  • 從這些檔案中個人選出至少三筆資料是其認為有用、會想要看的;
  • 系統便將之記錄起來成為個人郵件系統內的過濾器,從此以後經過過濾的檔案會最先送達信箱;

以上是協同過濾最早的應用,接下來的里程碑為GroupLens。

GroupLens(1994)

編輯

這個系統主要是應用在新聞的篩選上,幫助新聞的閱聽者過濾其感興趣的新聞內容,閱聽者看過內容後給一個評比的分數,系統會將分數記錄起來以備未來參考之用,假設前提是閱聽者以前感興趣的東西在未來也會有興趣閱聽,若閱聽者不願揭露自己的身分也可以匿名進行評分。 和Tapestry不同之處有兩點,首先,Tapestry專指一個點(如一個網站內、一個系統內)的過濾機制;GroupLens則是跨點跨系統的新聞過濾機制。再來,Tapestry不會將同一筆資料的評比總和起來;GroupLens會將同一筆資料從不同使用者得到的評比加總。 GroupLens具有以下特點:

  • 開放性:所有的新聞閱聽者皆可使用,雖然系統委託Better Bit Bureau設計給分的系統,但若有不同的評分機制也適用於GroupLens。
  • 方便性:給分並不是一件困難的事情且溝通上非常方便,評分結果容易詮釋。
  • 規模性:有可能發展成大規模的系統,一旦發展成大規模,儲存空間與計算成本問題顯得相當棘手。
  • 隱密性:如果使用者不想讓別人知道他是誰,別人就不會知道。

由此可以看出,現今網路各個推薦系統的雛形已然形成,在GroupLens之後還有性質相近的MovieLens,電影推薦系統;Ringo,音樂推薦系統;Video Recommender,影音推薦系統;以及Jster,笑話推薦系統等等。乃至於今日的YouTube、aNobii皆是相似性質的網路推薦平台,較不同的是經過時間推移,網路越來越發達,使用者越來越多,系統也發展得越來越嚴密。

電子商務的推薦系統

編輯

最著名的電子商務推薦系統應屬亞馬遜網路書店,顧客選擇一本自己感興趣的書籍,馬上會在底下看到一行「Customer Who Bought This Item Also Bought」,亞馬遜是在「對同樣一本書有興趣的讀者們興趣在某種程度上相近」的假設前提下提供這樣的推薦,此舉也成為亞馬遜網路書店為人所津津樂道的一項服務,各網路書店也跟進做這樣的推薦服務如台灣的博客來網路書店。 另外一個例子是Facebook的廣告,系統根據個人資料、週遭朋友感興趣的廣告等等對個人提供廣告推銷,也是一項協同過濾重要的里程碑,和前二者Tapestry、GroupLens不同的是在這裡雖然商業氣息濃厚同時還是帶給使用者很大的方便。 以上為三項協同過濾發展上重要的里程碑,從早期單一系統內的郵件、檔案過濾,到跨系統的新聞、電影、音樂過濾,乃至於今日橫行網際網路的電子商務,雖然目的不太相同,但帶給使用者的方便是大家都不能否定的。

分類應用

編輯

基於存量(Memory - based)的協同過濾

編輯

基於使用者(User-based)的協同過濾

編輯

相似統計的方法得到具有相似愛好或者興趣的相鄰使用者,所以稱之為基於使用者的協同過濾。方法步驟:

  1. 收集使用者資訊:收集可以代表使用者興趣的資訊。一般的網站系統使用評分的方式或是給予評價,這種方式被稱為「主動評分」。另外一種是「被動評分」,是根據使用者的行為模式由系統代替使用者完成評價,不需要使用者直接打分或輸入評價資料。電子商務網站在被動評分的資料獲取上有其優勢,使用者購買的商品記錄是相當有用的資料。
  2. 最近鄰搜尋(Nearest neighbor search, NNS):以使用者為基礎(User-based)的協同過濾的出發點是與使用者興趣愛好相同的另一組使用者,就是計算兩個使用者的相似度。例如:尋找n個和A有相似興趣使用者,把他們對M的評分作為A對M的評分預測。一般會根據資料的不同選擇不同的演算法,目前較多使用的相似度演算法有Pearson Correlation CoefficientCosine-based SimilarityAdjusted Cosine Similarity
  3. 產生推薦結果:有了最近鄰集合,就可以對目標使用者的興趣進行預測,產生推薦結果。依據推薦目的的不同進行不同形式的推薦,較常見的推薦結果有Top-N 推薦和關聯推薦。Top-N 推薦是針對個體使用者產生,對每個人產生不一樣的結果,例如:透過對A使用者的最近鄰使用者進行統計,選擇出現頻率高且在A使用者的評分項目中不存在的,作為推薦結果;關聯推薦是對最近鄰使用者的記錄進行關聯規則(association rules)挖掘。

基於專案(Item-based)的協同過濾

編輯

基於使用者的協同過濾在使用者總數較多的情況下會導致漫長的計算時間。在2001年,Sarwar提出了基於項目的協同過濾。該技術所依據的基本假設是「能夠引起使用者興趣的項目,必定與其之前評分高的項目相似」,即通過計算項目之間的相似性來代替計算使用者之間的相似性。方法步驟:

  1. 收集使用者資訊:同以使用者為基礎(User-based)的協同過濾。
  2. 針對項目的最近鄰搜尋:先計算已評價項目和待預測項目的相似度,並以相似度作為權重,加權各已評價項目的分數,得到待預測項目的預測值。例如:要對項目 A 和項目 B 進行相似性計算,要先找出同時對 A 和 B 打過分的組合,對這些組合進行相似度計算,常用的演算法同以使用者為基礎(User-based)的協同過濾。
  3. 產生推薦結果:以項目為基礎的協同過濾不用考慮使用者間的差別,所以精度比較差。但是卻不需要使用者的歷史資料,或是進行使用者識別。對於項目來講,它們之間的相似性要穩定很多,因此可以離線完成工作量最大的相似性計算步驟,從而降低了線上計算量,提高推薦效率,尤其是在使用者多於項目的情形下尤為顯著。

基於模型(Model- based)的協同過濾

編輯

以存量為基礎(Memory based)的協同過濾的缺點是資料稀疏,難以處理大資料量,這會影響即時結果。另一大類的協同過濾,即以模型為基礎的協同過濾,可以在一定程度上緩解這個問題。 以模型為基礎的協同過濾(Model-based Collaborative Filtering)是先用歷史資料得到一個模型,再用此模型進行預測。以模型為基礎的協同過濾廣泛使用的技術包括隱語意模型貝葉斯網路…等,根據對一個樣本的分析得到模型。

優缺點

編輯

優點

編輯

以使用者的角度來推薦的協同過濾系統有下列優點:

  • 能夠過濾機器難以自動內容分析的資訊,如藝術品,音樂等。
  • 共享其他人的經驗,避免了內容分析的不完全或不精確,並且能夠基於一些複雜的,難以表述的概念(如資訊品質、個人品味)進行過濾。
  • 有推薦新資訊的能力。可以發現內容上完全不相似的資訊,使用者對推薦資訊的內容事先是預料不到的。可以發現使用者潛在的但自己尚未發現的興趣偏好。
  • 推薦個性化、自動化程度高。能夠有效的利用其他相似使用者的回饋資訊。加快個性化學習的速度。

缺點

編輯

雖然協同過濾作為一推薦機制有其相當的應用,但協同過濾仍有許多的問題需要解決。整體而言,最典型的問題有

  • 新使用者問題(New User Problem) 系統開始時推薦品質較差
  • 新項目問題(New Item Problem) 品質取決於歷史資料集
  • 稀疏性問題(Sparsity)
  • 系統延伸性問題(Scalability)。

未來發展

編輯

Item-based的推薦演算法能解決User-based協同過濾的一些問題,但其仍有許多問題需要解決,最典型的有稀疏問題(Sparsity)和冷啟動問題(Cold-start),冷啟動時效果較差。此外還有新使用者問題和演算法健壯性等問題。協同過濾作為一種典型的推薦技術有相當的應用,目前很多技術都是圍繞協同過濾而展開研究的。在資訊種類、表達方式越來越多的時代,舊式的資訊分類過濾系統無法滿足的地方,期許未來能用協同過濾的方法來解決。

參考文獻

編輯
  • Paul Resnick, Neophytos Iacovou, Mitesh Suchak, Peter Bergstrom, John Riedl, GroupLens: an open architecture for collaborative filtering of netnews, Computer Supported Cooperative Work, pp175-186, Chapel Hill, North Carolina, 1994.
  • Balabanovic & Shoham, 1997; Mobasher et al., 2000; Yang et al., 2004
  • F. Heylighen, Collaborative Filtering, http:/pespmc1.vub.ac.be/COLLFILT.html
  • Breese, J.S., Heckerman, D., Kadie, C.: Empirical analysis of predictive algorithms for collaborative filtering. In: Fourteenth Conference on Uncertainty in Artificial Intelligence,Madison, WI (1998)
  • 鄭秀華、廖婉菁、吳肇銘,線上商品推薦系統之研究 -協同過濾機制之應用A Study for On-line Commodity Recommendation System:A Case of Collaborative Filtering,中原資管所
  • Jung, Seikyung, Designing and understanding information retrieval systems using collaborative filtering in an academic library environment, Oregon State University, 2007.
  • David Goldberg, David Nichols, Brian M. Oki, and Douglas Terry, Using collaborative filtering to weave an information tapestry, Communications of the ACM, Volume 35, Issue 12, pp61-70, 1992.
  • 韓雙福,應用協同過濾機制於商機撮合電子報之研究 - 以食品業電子市集為例,中原大學資訊管理學系碩士論文,民國92年7月。
  • 彭愷翔,以語音為基礎之情境認知虛擬行動設群,天主教輔仁大學資訊管理學系碩士論文,民國91年6月。
  • 馮文正,合作式網站推薦系統,國立交通大學資訊學研究所,民國89年。
  • 蔡登、盧增祥、李衍達,資訊協同過濾,電腦科學,第29期,頁1~頁4,2002年。