推薦演算法介紹

隨著網際網路日益普及,數位內容呈現指數成長趨勢,使人們淹沒在資訊洪流之中,例如:Netflix上有數萬部電影,Amazon上有數百萬本書籍,Del.icio.us上有超過十億的網頁收藏,這麼多的訊息,我們無法一一瀏覽,而傳統的搜尋引擎只能呈現給使用者一樣的排序清單,無法根據不同使用者偏好提供個性化服務,而個性化搜尋與推薦系統正是解決當前資訊超載的有效方法之一。

其中推薦系統是資訊過濾系統的子集,它試圖預測使用者將賦予他們還沒有考慮的項目(例如:書籍、音樂或電影)或社交元素(例如:個人或團體)評分或偏好。

在一個真實的推薦系統中需要考慮的項目可能會有成千上萬,甚至超過百萬,例如:Amazon、eBay和YouTube等,使用者數量也會非常龐大,因此我們需要準確且有效率的推薦系統。在激烈的競爭環境之下,現有推薦系統已經在電子商務領域取得卓越成果,但在不同領域之下,還需要各方先進和專家努力發展。

一個完整的推薦系統由三個部分組成,收集使用者資訊的行為紀錄模組,分析使用者偏好的模型分析模組與推薦演算法模組;行為紀錄模組負責記錄使用者行為,例如評分、購買或瀏覽等;模型分析模組負責分析使用者行為,以建立合適的模型來描述使用者偏好;推薦演算法模組負責即時從項目集合中篩選出使用者偏好項目進行推薦,此為推薦系統中最為核心的部分。

主要的推薦演算法可以分為協同過濾(Collaborative Filtering)、基於內容(Content-based)與混合法(Hybrid Approaches),接下來我將一一介紹,並進一步說明如何在協同過濾法中結合情境感知 ( Context-aware ) 。

協同過濾法(Collaborative Filtering Approaches)

協同過濾法是目前最成功的推薦演算法之一,通常的做法是搜尋一大群人,從中找到與我們品味相近的一小群人。演算法會針對這些人偏好的其他內容進行計算,產生一個有序的推薦清單。

Goldberg設計Tapestry是最早應用協同過濾法的系統,該系統允許人們根據自己對文件感興趣的程度添加標記,並利用此資訊為他人過濾文件。Konstan等人設計的GroupLens則是應用在新聞篩選上,幫助讀者過濾其偏好的新聞內容,使用者看過內容後給一個評分,系統會將分數記錄下來供日後參考,不同於Tapestry僅在同一個系統中過濾,GroupLens是跨系統的新聞過濾機制;除此之外,Tapestry不會將同項目的評分總合起來,GroupLens則會對同項目從不同使用者得到的評分加總。

協同過濾法可以分為兩類:基於記憶(Memory-based)和基於模型(Model-based)的演算法;基於記憶的演算法根據系統中所有被評分的項目進行預測;基於模型的演算法根據收集評分資料進行機器學習,得到使用者行為模型進行預測。

協同過濾法需要計算兩個使用者相似度, 常用的相似度測量法有Distance-based、Correlation-based、Cosine-based。

總結來說,協同過濾法有以下優點:具有推薦新資訊的能力,可以發現使用者潛在偏好;能夠推薦音樂、餐廳和電影等難以進行內容分析的項目。

雖然協同過濾法應用廣泛,但是也有許多問題,例如:如何對新使用者進行推薦或如何推薦新項目給使用者之冷啟動問題(Cold Start);在任何推薦系統中,已評分項目通常比需要推薦項目數量少很多,而導致精確度低落之稀疏性問題(Sparsity),面對日益增多的使用者,資料量急劇增加之可擴展性問題(Scalability)等。因此有的推薦系統採用基於項目相似度的協同過濾法,在項目數量相對穩定的系統,這種方法是很有效的。

基於內容法(Content-based Approaches)

最初基於內容法是協同過濾法的延續與發展,他不需要依賴使用者對項目的評價,而是依據使用者已經選擇的項目內容計算使用者之間的相似度,藉此推薦合適的項目;基於內容的推薦系統依賴資訊檢索與過濾,經由分析已經購買或瀏覽的內容,對使用者和項目建立配置文件(Profile),系統可以比較使用者和項目配置文件的相似度,直接向使用者推薦最相似的項目。

總結來說,基於內容法有以下優點:可以處理新使用者與新項目的冷啟動問題;不會受到評分稀疏性的限制;能夠推薦新項目和非流行項目,能夠發現隱藏的項目;可以透過配置文件列出推薦項目的特徵,深入了解為什麼推薦這些項目。

基於內容法也面臨常見的資訊檢索問題,例如:多媒體資料(圖片、音樂與影片)難以進行文本結構化,而受到了很大的限制。

混合法(Hybrid Approaches)

每一種演算法都存在著一些缺點,為了擇優汰劣,有些推薦系統結合了不同的方法,我們稱之為混合法。而目前最常見的混合推薦系統即是基於內容與協同過濾法的搭配,主要又可分為獨立系統相互結合、協同過濾系統加入基於內容法。

獨立系統相互結合是分別利用兩種以上的演算法產生推薦結果,然後將這些結果整合起來,利用預測評分的線性組合進行推薦。

而在協同過濾系統中加入基於內容法的Fab,即是使用者配置文件使用協同過濾法產生,使用者相似度則使用基於內容法,而非參考共同評分項目,這樣可以讓系統不僅能推薦擁有共同評分的使用者項目,也可以推薦與使用者配置文件相似的項目。

結合情境之協同過濾法

傳統協同過濾法可以被視為二維問題,其中一維是使用者,另外一維是項目,每個使用者與項目的交互是使用者對項目的評分,當我們加入情境到推薦問題上,它就變成了多維度問題。

傳統推薦演算法無法直接處理這類問題,然而許多研究人員試圖修改原有方法來支援情境感知;Adomavicius提出了一個相當著名的方法,其主要精神是在推薦時固定維度,也就是只考慮該情境下所有的評分,如此一來多維問題就變成了二維問題;然而這種方法會使得冷啟動問題變得更加棘手,因此Adomavicius等人還提出了一個擴展有等級屬性之情境的方法,為了增加準確度,他們還設計一種演算法將情境分段。

另外一個方法是測量不同情境的相似度去加權評分;由於使用者偏好項目會隨著情境改變,若在某些情境下使用者一致偏好此項目,Chen推論這個些情境即非常適合該項目。因此他使用Correlation-base相似度測量法去計算項目i在兩個情境xy下的相似度權重。

Chen還假設每個維度都是線性獨立的,如此一來兩個情境的相似度可以在每個維度中分別計算。