/* syntax highlight */ /* end of syntax highlight */

2010年4月9日 星期五

[Data mining] 協同過濾法 (collaborative Filtering) 及相關概念

Bookmark and Share

我的 研究室 的指導教授是 劉敦仁教授

近期都在做論文,主要使用的是資料探勘(Data Mining當中的)  協同過濾(collaborative Filtering) 法

以下有時簡稱 CF,看似很簡單的原理…但還真的搞了很久還是很模糊,趁這個機會好好整理一下

 

Wiki 的文字定義 (連結)

協同過濾Collaborative Filtering)簡單來說是利用某興趣相投、擁有共同經驗之群體的喜好來推薦使用者感興趣的資訊,個人透過合作的機制給予資訊相當程度的回應(如評分)並記錄下來以達到過濾的目的進而幫助別人篩選資訊,回應不一定侷限於特別感興趣的,特別不感興趣資訊的紀錄也相當重要。協同過濾又可分為評比(rating)或者群體過濾(social filtering)。其後成為電子商務當中很重要的一環,即根據某顧客以往的購買行為以及從具有相似購買行為的顧客群的購買行為去推薦這個顧客其「可能喜歡的品項」,也就是藉由社群的喜好提供個人化的資訊、商品等的推薦服務。除了推薦之外,近年來也發展出數學運算讓系統自動計算喜好的強弱進而去蕪存菁使得過濾的內容更有依據,也許不是百分之百完全準確,但由於加入了強弱的評比讓這個概念的應用更為廣泛,除了電子商務之外尚有資訊檢索領域、網路個人影音櫃、個人書架等的應用等。

 

經典 Case:

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

 

協同過濾法的優點:

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

 

協同過濾法的缺點:

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

 

主流協同推薦法分類(3種):

有人會將 content-based 也算在 CF 法的範圍當中,但其實任務是要區分的,分述如下

 

(1) User-Based CF (from Wiki)

相似統計的方法得到具有相似愛好或者興趣的相鄰使用者,所以稱之為以使用者為基礎(User-based)的協同過濾或基於鄰居的協同過濾(Neighbor-based Collaborative Filtering)。

 

方法步驟如下:

 

1.收集使用者資訊

收集可以代表使用者興趣的資訊。一般的網站系統使用評分的方式或是給予評價,這種方式被稱為「主動評分」。另外一種是「被動評分」,是根據使用者的行為模式由系統代替使用者完成評價,不需要使用者直接打分或輸入評價資料。電子商務網站在被動評分的資料獲取上有其優勢,使用者購買的商品記錄是相當有用的資料。

 

2.最近鄰搜索(Nearest neighbor search, NNS)

以使用者為基礎(User-based)的協同過濾的出發點是與使用者興趣愛好相同的另一組使用者,就是計算兩個使用者的相似度。例如:尋找n個和A有相似興趣使用者,把他們對M的評分作為A對M的評分預測。一般會根據資料的不同選擇不同的演算法,目前較多使用的相似度演算法有Person Correlation CoefficientCosine-based SimilarityAdjusted Cosine Similarity

 

3.產生推薦結果

有了最近鄰集合,就可以對目標使用者的興趣進行預測,產生推薦結果。依據推薦目的的不同進行不同形式的推薦,較常見的推薦結果有Top-N 推薦和關聯推薦。Top-N 推薦是針對個體使用者產生,對每個人產生不一樣的結果,例如:透過對A使用者的最近鄰使用者進行統計,選擇出現頻率高且在A使用者的評分項目中不存在的,作為推薦結果。關聯推薦是對最近鄰使用者的記錄進行關聯規則(association rules)挖掘。

 

(2) Item-Based CF (from Wiki)

以使用者為基礎的協同推薦演算法隨著使用者數量的增多,計算的時間就會變長,所以在2001年Sarwar提出了基於項目的協同過濾推薦演算法(Item-based Collaborative Filtering Algorithms)。以項目為基礎的協同過濾方法有一個基本的假設」能夠引起使用者興趣的項目,必定與其之前評分高的項目相似」,透過計算項目之間的相似性來代替使用者之間的相似性。 方法步驟:

1.收集使用者資訊

同以使用者為基礎(User-based)的協同過濾。

 

2.針對項目的最近鄰搜索

先計算己評價項目和待預測項目的相似度,並以相似度作為權重,加權各已評價項目的分數,得到待預測項目的預測值。例如:要對項目 A 和項目 B 進行相似性計算,要先找出同時對 A 和 B 打過分的組合,對這些組合進行相似度計算,常用的演算法同以使用者為基礎(User-based)的協同過濾。

 

3.產生推薦結果

以項目為基礎的協同過濾不用考慮使用者間的差別,所以精度比較差。但是卻不需要使用者的歷史資料,或是進行使用者識別。對於項目來講,它們之間的相似性要穩定很多,因此可以離線完成工作量最大的相似性計算步驟,從而降低了線上計算量,提高推薦效率,尤其是在使用者多於項目的情形下尤為顯著。

 

(3) Content-Based Recommendation(CBF)    (定義來說,此非 CF 法)

Robin BurkeHybrid Recommender Systems: Survey and Experiments 一文中有定義如下:

A content-based recommender learns a profile of the user’s interests based on the features present in objects the user has rated

所以當使用者 profile 是經由分析文章所建立的時候,而 item 或 user 相似度是經由 cosine sim 算的時候,都算是用到了 content filtering 的概念

 

 

Collaborative Filtering  , Content-based filtering 優缺點比較

( Burke, 2002):

image

 

意思如下 (相關概念翻譯自論文)

A. 不太確定它的意思,應該是指 content-based 必須從同類別先去 training,所以其他類別的 item 就完全不可能被推薦,但是 CF 法的話,不同類別的 item 還是可能被推薦的

B. 完全從內容著手,不需要該領域的專業知識

C. 當資料越來越多時,推薦法也會越來越準確

D. 可以自行定義隱藏的變數,例如如果 user 停留在某個頁面很久,可以定義為它很喜歡 (rating ↑)

I. 新的 user 紀錄太少 (user 對所有 item 的 rating),造成推薦不準確的問題

J.新的 item 紀錄太少 ( user 對此 item 的 rating) ,造成推薦不準確的問題

K. 特立獨行者,沒有明顯喜好者,很難準確推薦

L. 歷史資料要夠大才可以分析,所以新系統似乎不適用

M. 指的是當分析完使用者的偏好後,如果使用者口味突然改變,很難再去預測,必須使用新的歷史資  料重新分析,推薦很僵化很麻煩

 

 

CF Case 案例說明:

(1) Case 背景

首先下面這張圖是協同過濾法的典範,一個網站可能有 48 萬個 user

並收錄了 18000 部電影,每個 user 對部份電影都有給予評分

第一列的 user A 對於 movie 2 的評價是 1 分,對於 movie 3 的評價也是 1 分

但是 user A 還沒有對於 movie1 和 movie 4 有評價

那我們要怎樣用這個方法去預測 user A 對 1,4 的評價呢 ?

 

image

 

(2) Case 概念說明

基礎共分為兩種概念解決,分述如下

 

(a) User-Based CF

第一種是 user-based CF ,圖示如下 (JUN WANG,2008)

 image

如果要預測 user A 對 4 的評價,因為 user B 對 4 的評價是 5 分, user F 對於 4 的評價是 1 ,則

user A → 4  分數從 4 * similarities (user A, user B)  加上  1 * similarities (user A, user F)

即 user A 可以從相似 user B 和 F 去看他們對於 item 4 的評價,再算回去 user A 的評價

 

(b) Item-Based CF

第二種是 item-based CF ,則正好相反,圖示如下 (JUN WANG,2008)

image

如果要預測 user A 對 4 的評價,因為 user A 對 2 和 3 的評價都是 1 ,則

user A = 1 * similarities (item 4, item 2)  加上  1 * similarities (item 4, item 3)

即 user A 可以從相似 item 2 和 item 3 去看他們與 item 4 的相似度,再算回去 user A 的評價

 

 

CF 公式說明

(a) user-based CF

image

要預測 user u 對於 item i 的分數的話

要考量所有行為像是 u 的其他 user v ( ex. 共同 rating 過 item i)

再除上所有相似度的加總,意義是將算出來的結果 mapping 到 user  u 平常的 rating 區間

 

(b) item-based CF

image

要預測 user u 對於 item i 的分數的話

要考量與 i 相似的其他 item j ,且 u 也對 j 有 rating ,並乘上 i 與 j 的相似度

再除上所有相似度的加總,意義是將算出來的結果 mapping 到 user  u 平常的 rating 區間

(the sum of the similarity terms to make sure the prediction is within the predefined range)

(Badrul Sarwar, 2001)

 

 

CF 之中有用到的相似度算法:

CF 用到的相似度算法也有很多種,分述如下:

 

(1) Jaccard similarites (需要分析 content 建立成 tag set) 

i,j 是 item 名稱

要算 item i 與 item j 的相似度,先把 i,j 分別建立成一個 tag set

例如 ( keyword1 , keyword 2 , keyword 3 , keyword 4 ….etc)

再用以下公式

image

分母為 item A 與 item B 所有有出現過的 tag 數

分子為 item A 與 item B 共同出現過的 tag 數

 

 

(2) Cosine similarities (需要分析 content 建立成 vector)

image

i,j 是 item 名稱

要算 item i 與 item j 的相似度,先把 i,j 建立成一個 vector (可以看成有權重的 tag set)

例如 ( keyword1 : 0.67 , keyword 2 : 0.88 …. keyword n : 0.32 )

如此一來就可以計算兩兩的相似度,如果 keyword 只有 2 個

則可以看成二維平面

 

example 如下

item A 有兩個 tag x1 與 y1 ,權重為 x1 : 0.22  , y1 : 0.33

item B 有兩個 tag x2 與 y2 ,權重要 x2 : 0.44  , y2 : 0.55

sim (item A , item B) 的圖示如下:

image

sim (item A , item B) = cos ( x , y )

= ( 0.22 * 0.44  +  0.33 * 0.55 )  / ( 0.22 ^ 2 + 0.44 ^ 2) ^ 0.5  + ( 0.33 ^ 2 + 0.55 ^ 2) ^ 0.5

 

 

(3) Pearson correlation-based similarity (需要有 user 對於某些 item 的 rating)

ps. 這公式是 item-based

image

R(u,i) 指 user i 對於 item i 的 rating 值,

U 指有對 item i co-rating 的 user

R(u) bar 是該 user 對於所有文章的平均值

 

針對 item i , 共同有 co-rating 的 U 們的 rating 減掉 item i 平均得到的 rating 數,不考慮 user 同時 rating 不同 item 的因素,只考慮 item 本身屬性,可以判斷這些 item 彼此是不是像的。

 

 

(3) Adjusted cosine similarities (需要有 user 對於某些 item 的 rating)

ps. 這公式是 item-based

image

Cosine similarities 可以針對內容相似度去做計算,但如果

 

R(u,i) 指 user i 對於 item i 的 rating 值,

U 指有對 item i co-rating 的 user

R(u) bar 是該 user 對於所有文章的平均值

 

針對同個 item,不同 user 所給予的不同分數,但是 adjusted cosine 為了考量 每個 user 的 scale 不同的問題 (ex. user A 平均都給 2 分 , user B 給 5 分 , 就不公平) 因此把每筆 rating 都扣掉一個該 user 給分的平均值,來避免此種情況發生。

 

 

相關概念1 - Hybrid Recommendation Systems :

Hybrid Recommendation Systems (Burke,2002)

image

 

中文解釋分述如下 (後面 3 個看起來差不多):

(1) Weighted:從不同推薦方法算出 item candiate 的偏好度,再用參數調教加起來

example: alpha = 0.3 用 user-based CF  加上  alpha = 0.7 用 Content-based

(2) Switching:在不同的情況用不同推薦方法

example:使用者沒有資料 → Content-based  , 使用者有資料 → 用 user-based CF

 

(3) Mixed:同時用不同的推薦方法計算

example:item 1 從 content-based 得到 0.8 分  , 從 user-based CF 得到 0.7 分

(4) Featre combination:不同的 data 來源但使用同一種推薦法

example:網站1與網站 2 都得到某 user 的 feature data,然後都用 content-based 計算

(5) Cascade (順序性推薦法) & Feature augmentation ( 特色放大) & meta-level

example:資料先經由 content-based 算完,再將結果丟到 user-based 計算

相關概念2 - 推薦實驗評估法 :

(1) Recall:從應該推薦的清單當中成功推薦的比例

image

 

(2) Precision:所有推薦的清單當中,推薦正確的比例

image

 

(3) F1:將以上兩個分數用調和平均的方式加總起來,都高才能有效

image

(4)  MAE:L是總測試的數目,可以看成 a 是 user , b 是 item ,加上 ^ 指的是預測值

                 實際值減到預測值再除上計算的筆數,就可以到得預測準確度

image

相關概念3 – TFIDF :

如果要找出一個關鍵字 i 在 item j 裡面的重要程度,可以透過以公式計算出

image

  • W(i,j) 是 i 在 item j 的重要程度
  • TF(i,j) 是 i 在 item j 出現的次數
  • idf (i) 是 i 在所有 item 裡面的相對重要程度
  • N 是所有的 item 數
  • n 是 i 有出現的 item 數

原文如下

where tfi,j is the frequency of term i in document j, idfi is measured
by (log2 N/n) + 1, N is the total number of documents in the collection,
and n is the number of documents in which term i occurs at
least once.  (Chin-Hui, 2009)

 

 

相關概念4 - 分群法 (wiki) :

維基資訊:http://en.wikipedia.org/wiki/Cluster_analysis

通常 filtering 待推薦的 item 數目都會太多 ( ex. 超過一百萬筆)

這時如果能夠先對 item 先做分群,可以讓整體的效率提升

 

以下內容整理摘錄自 國立清華大學資訊工程學系多媒體資訊檢索研究室資料

 

分群的流程大致有以下四個

a. 整理待分群的資料

b. 分群

c. 測試分群品質

d. 若品質不夠, 回到 b

 

分群法大致分為兩類

 

階層式分群法 : 必須先指定相似度門檻值,當 item 之間的相似度低於門檻值時,演算法就會停止

分割式分群法:先指定群數後,再用一套疊代的數學運算法,找出最佳的分群方式以及相關的群中心

 

(1) 階層式分群法 (Hierarchical algorithms) :

階層式分群法透過一種階層架構的方式,將資料層層反覆地進行分裂或聚合,整個階層式分群法可以的樹狀結構來表示。如果採用聚合的方式,階層式分群法可由樹狀結構的底部開始,將資料或群聚結合起來,一層一層的往上整合,相似的門檻值設定越低,則分群的群數會越少,圖示如下:

image

 

以下介紹階層式分群法的經典 :

 

階層式分裂演算法(hierarchical divisive algorithm)

由樹狀結構的底部開始層層聚合。一開始我們將每一筆資料視為一個群聚(cluster),假設我們現在擁有n筆資料,則將這n筆資料視為n個群聚,亦即每個群聚包含一筆資料:

1. 將每筆資料視為一個群聚C i
2. 找出所有群聚間,距離最接近的兩個群聚C、C ij
3. 合併C、C成為一個新的群聚 ij
4. 假如目前的群聚數目多於我們預期的群聚數目,則反覆重複步驟二至四,直到群聚數目已將降到我們所要求的數目。


步驟二 中,何謂「距離最接近的兩個群聚C、」呢?事實上在定義兩個群聚之間的距離,有各種不同的方式,每一種方式所得到的結果都不太相同。這些常用的群聚距離的定義可以說明如下。

 

單一連結聚合演算法(single-linkage agglomerative algorithm):群聚與群聚間的距離可以定義為不同群聚中最接近兩點間的距離:

image

 

完整連結聚合演算法(complete-linkage agglomerative algorithm):群聚間的距離定義為不同群聚中最遠兩點間的距離:

image

 

平均連結聚合演算法(average-linkage agglomerative algorithm):群聚間的距離則定義為不同群聚間各點與各點間距離總和的平均(其中,表示C的資料個數。):

image

 

 

沃德法(Ward's method):群聚間的距離定義為在將兩群合併後,各點到合併後的群中心的距離平方和(其中,μ表示C的平均值)

image

 

 

(2) 分割式分群法 (partitional clustering algorithms) :

以下介紹分割式分群法的經典 :K-means 分群法

在所有的分割式分群法(partitional clustering)之中,最基本的方法,就是所謂的 K-means algorithm,又稱為Forgy's algorithm [6]。其概念很簡單,就是使用一個反覆疊代的方式,讓目標函數越來越小。首先,我們知道我們的目標函數是由下列兩組參數所決定:

1. 群聚的分法
2. 群聚的中心點

 

我們可以經由下列步驟來進行 k-means 分群法:

1. 隨機選取c 個啟始點,將之分別視為c 個群聚的群中心。
2. 對每一個資料點x,尋找與之最接近的群中心,並將x加入該群聚。
3. 計算目標函數,如果保持不變,代表分群結果已經穩定不變,所以可以結束此疊代方法。
4. 計算新的群聚中心,等於該群聚中所有資料點的平均向量。並跳回步驟二。

 

K-means 更白話一點就是

假設現在有 1000 篇文章

 

第一步驟,你可能隨意選 10 個代表文章,他們都有各自的代表向量

接下來這 1000 篇文章就會算跟這 10 篇文章向量的相似度,最高的分為同一群

所以會得到 10 群文章,可能第一群 300 篇,第二群123篇等等 …然後有十群

 

第二步驟,這十群文章會算出群中心點,變成新的代表向量,這1000篇又再跟這新的代表相量算相似度,又會分成 10 群,但是第一群可能變成 235 篇之類,就是每一次 loop 的分群法都會洗牌一次

 

第三步驟,決定停止點,這樣一直分下去,當使用計算出的新的代表向量去分群之後,這一輪跟下一輪最後的分群結果相同時,例如第 7 次 loop 的第一群是 150 篇文章,第 8 次還是 150 篇文章,即代表整個分群到了終點,不會再變動了,演算法終止

 

這部份觀念還蠻難懂的,建議多閱讀一些文章

分群法延伸閱讀:

結合K-means及階層式分群法之二階段分群演算法

資料分群與向量量化

 

相關概念5 - 衡量分群品質 :

如果要衡量分群的品質是否良好,可以用下面的公式衡量 (Chin-Hui, 2009 )

重點是「讓群內相似度提升,群間相似度降低」

image

  • CQ(C) 是分群品質

  • │C│ 是 Cluster 的數目

  • Ci 都屬於同一群 (但有很多群)

  • 分子是群間相似度

  • 分母是群內相似度

     

    Reference

    • Wikipedia
    • GroupLens: An Open Architecture for Collaborative Filtering of Netnews, Paul Resnick,1994
    • Hybrid Recommendation Systems, Burke,2002
    • Unified Relevance Models for Rating Prediction in Collaborative Filtering, JUN WANG,2008
    • Integrating knowledge flow mining and collaborative filtering to support
      document recommendation, Chin-Hui, 2009

  • 0 意見:

    張貼留言

    Related Posts Plugin for WordPress, Blogger...