歡迎光臨
每天分享高質量文章

【演算法】推薦演算法–協同過濾

筆者邀請您,先思考:

1 協同過濾演算法的原理?

2 協同過濾演算法如何預測?

什麼是協同過濾

協同過濾推薦(Collaborative Filtering recommendation)是在信息過濾和信息系統中正迅速成為一項很受歡迎的技術。與傳統的基於內容過濾直接分析內容進行推薦不同,協同過濾分析用戶興趣,在用戶群中找到指定用戶的相似(興趣)用戶,綜合這些相似用戶對某一信息的評價,形成系統對該指定用戶對此信息的喜好程度預測。

協同過濾是迄今為止最成功的推薦系統技術,被應用在很多成功的推薦系統中。電子商務推薦系統可根據其他用戶的評論信息,採用協同過濾技術給標的用戶推薦商品。

協同過濾演算法主要分為基於啟髮式基於模型式兩種。

其中,基於啟髮式的協同過濾演算法,又可以分為基於用戶的協同過濾演算法(User-Based)和基於專案的協同過濾演算法(Item-Based)。

  • 啟髮式協同過濾演算法主要包含3個步驟:
    1)收集用戶偏好信息;
    2)尋找相似的商品或者用戶;
    3)產生推薦。

“巧婦難為無米之炊”,協同過濾的輸入資料集主要是用戶評論資料集或者行為資料集。這些資料集主要又分為顯性資料隱性資料兩種型別。其中,顯性資料主要是用戶打分資料,譬如用戶對商品的打分,五分制的1分,2分等。

但是,顯性資料存在一定的問題,譬如用戶很少參與評論,從而造成顯性打分資料較為稀疏;用戶可能存在欺詐嫌疑或者僅給定了部分信息;用戶一旦評分,就不會去更新用戶評分分值等。

而隱性資料主要是指用戶點擊行為、購買行為和搜索行為等,這些資料隱性地揭示了用戶對商品的喜好。

隱性資料也存在一定的問題,譬如如何識別用戶是為自己購買商品,還是作為禮物贈送給朋友等。

1.基於用戶的協同過濾

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

1.1方法步驟:

1.收集用戶信息
收集可以代表用戶興趣的信息。一般的網站系統使用評分的方式或是給予評價,這種方式被稱為“主動評分”。另外一種是“被動評分”,是根據用戶的行為樣式由系統代替用戶完成評價,不需要用戶直接打分或輸入評價資料。電子商務網站在被動評分的資料獲取上有其優勢,用戶購買的商品記錄是相當有用的資料。
2.最近鄰搜索(Nearest neighbor search, NNS)
以用戶為基礎(User-based)的協同過濾的出發點是與用戶興趣愛好相同的另一組用戶,就是計算兩個用戶的相似度。例如:查找n個和A有相似興趣用戶,把他們對M的評分作為A對M的評分預測。一般會根據資料的不同選擇不同的演算法,目前較多使用的相似度演算法有Pearson Correlation Coefficient(皮爾遜相關係數)、Cosine-based Similarity(餘弦相似度)、Adjusted Cosine Similarity(調整後的餘弦相似度)。

基於用戶(User-Based)的協同過濾演算法首先要根據用戶歷史行為信息,尋找與新用戶相似的其他用戶;同時,根據這些相似用戶對其他項的評價信息預測當前新用戶可能喜歡的項。

給定用戶評分資料矩陣R,基於用戶的協同過濾演算法需要定義相似度函式s:U×U→R,以計算用戶之間的相似度,然後根據評分資料和相似矩陣計算推薦結果。

1.2如何選擇合適的相似度計算方法

在協同過濾中,一個重要的環節就是如何選擇合適的相似度計算方法,常用的兩種相似度計算方法包括皮爾遜相關係數和餘弦相似度等。皮爾遜相關係數的計算公式如下所示:

皮爾遜相關係數

其中,i表示項,例如商品;Iu表示用戶u評價的項集;Iv表示用戶v評價的項集;ru,i表示用戶u對項i的評分;rv,i表示用戶v對項i的評分;表示用戶u的平均評分;表示用戶v的平均評分。

另外,餘弦相似度的計算公式如下所示:

餘弦相似度

1.3計算用戶u對未評分商品的預測分值

另一個重要的環節就是計算用戶u對未評分商品的預測分值。首先根據上一步中的相似度計算,尋找用戶u的鄰居集N∈U,其中N表示鄰居集,U表示用戶集。然後,結合用戶評分資料集,預測用戶u對項i的評分,計算公式如下所示:

預測用戶u對項i的評分

其中,s(u,u’)表示用戶u和用戶u’的相似度。

1.4通過例子理解

假設有如下電子商務評分資料集,預測用戶C對商品4的評分。

電子商務評分資料集

表中?表示評分未知。根據基於用戶的協同過濾演算法步驟,計算用戶C對商品4的評分,其步驟如下所示。
(1)尋找用戶C的鄰居
從資料集中可以發現,只有用戶A和用戶D對商品4評過分,因此候選鄰居只有2個,分別為用戶A和用戶D。用戶A的平均評分為4,用戶C的平均評分為3.667,用戶D的平均評分為3。

image.png

根據皮爾遜相關係數公式:
紅色區域計算C用戶與A用戶,用戶C和用戶A的相似度為:

用戶C和用戶A的相似度

藍色區域計算C用戶與D 用戶的相似度為:

C用戶與D 用戶的相似度

(2)預測用戶C對商品4的評分
根據上述評分預測公式,計算用戶C對商品4的評分,如下所示:

用戶C對商品4的評分

依此類推,可以計算出其他未知的評分。

2.基於專案的協同過濾

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

2.1方法步驟:

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

基於專案(Item-Based)的協同過濾演算法是常見的另一種演算法。與User-Based協同過濾演算法不一樣的是,Item-Based協同過濾演算法計算Item之間的相似度,從而預測用戶評分。也就是說該演算法可以預先計算Item之間的相似度,這樣就可提高性能。Item-Based協同過濾演算法是通過用戶評分資料和計算的Item相似度矩陣,從而對標的Item進行預測的。

2.2相似度計算方法

和User-Based協同過濾演算法類似,需要先計算Item之間的相似度。並且,計算相似度的方法也可以採用皮爾遜關係繫數或者餘弦相似度,這裡給出一種電子商務系統常用的相似度計算方法,即基於物品的協同過濾演算法,其中相似度計算公式如下所示:

image.png

這裡,分母|N(i)|是喜歡物品i的用戶數,而分子|N(i)∩N(j)|是同時喜歡物品i和j的用戶,但是如果物品j很熱門,就會導致Wij很大接近於1。因此避免推薦出熱門的物品,我們使用下麵的公式:

基於物品的相似度

從上面的定義可以看出,在協同過濾中兩個物品產生相似度是因為他們共同被很多用戶喜歡,也就是說每個用戶都可以通過他們的歷史興趣串列給物品“貢獻”相似度。

計算物品相似度首先建立用戶-物品倒排表(即對每個用戶建立一個包含他喜歡的物品的串列),然後對每個用戶,將他物品串列中的物品兩兩在共現矩陣中加1。

代碼

圖例

根據矩陣計算每兩個物品之間的相似度wij。

2.3用戶u對於物品j的興趣

得到物品之間的相似度後,可以根據如下公式計算用戶u對於物品j的興趣:

用戶u對於物品j的興趣

這裡N(u)是用戶喜歡的物品的集合,S(j,K)是和物品j最相似的K個物品的集合,wji是物品j和i的相似度,rui是用戶u對物品i的興趣。(對於隱反饋資料集,如果用戶u對物品i有過行為,即可令rui=1。)該公式的含義是,和用戶歷史上感興趣的物品越相似的物品,越有可能在用戶的推薦串列中獲得比較高的排名。

當我們看到這裡的時候很可能由於自己功底不足,很難看懂公式中的i∈N(u)∩S(j,K)。

我們來看另外一種計算方式:

矩陣

其中,Pa為新用戶對已有產品的向量,T為物品的共現矩陣,得到的P`a為新用戶對每個產品的興趣度。

那麼就可以理解上述公式的i∈N(u)∩S(j,K),我們在下麵的例子中詳細講解。

2.4舉例

現有用戶的訪問的記錄如下圖所示:

用戶的訪問

他的共現矩陣為:

共現矩陣

通過公式計算相似度:

Wa,b

以此類推得到相似度的共現矩陣:

相似度的共現矩陣

此時若有新用戶E,訪問的a,b,d三個物品,那麼可以看做向量P:

向量P

那麼P`為矩陣相乘:

P`

此時得到了對於用戶E,c和e兩個物品的興趣度是相同的。

2.5理解公式i∈N(u)∩S(j,K)

那麼現在我們來理解公式i∈N(u)∩S(j,K):
對於用戶E,已經訪問了a,b,d,那麼,N(u)={a,b,d};還有兩個未訪問物品c,e,那麼j={c,e};
當j=c時,對於和物品j最相似的K個物品的集合為{a,d,e},那麼S(j,K)={a,d,e};得出N(u)∩S(j,K)={a,d},如下圖所示:

再來看矩陣相乘中的c行,乘以P,實際上就是上述N(u)∩S(j,K)={a,d}的相似度求和。

同理,當j=e時,對於和物品j最相似的K個物品的集合為{b,c,d},那麼S(j,K)={b,c,d};得出N(u)∩S(j,K)={b,d};如下圖所示:

再來看矩陣相乘中的e行,乘以P,實際上就是上述N(u)∩S(j,K)={b,d}的相似度求和。

鏈接:

https://www.jianshu.com/p/5463ab162a58

您有什麼見解,請留言。

文章推薦:

1 【應用】從業務資料分析到機器學習應用的一次經歷

加入資料人圈子或者商務合作,請添加筆者微信。

資料人網是資料人學習、交流和分享的平臺http://shujuren.org 。專註於從資料中學習到有用知識。
平臺的理念:人人投稿,知識共享;人人分析,洞見驅動;智慧聚合,普惠人人。
您在資料人網平臺,可以1)學習資料知識;2)創建資料博客;3)認識資料朋友;4)尋找資料工作;5)找到其它與資料相關的乾貨。
我們努力堅持做原創,聚合和分享優質的省時的資料知識!
我們都是資料人,資料是有價值的,堅定不移地實現從資料到商業價值的轉換!


點擊閱讀原文,進入資料人網,獲取資料知識。




公眾號推薦:

鏈達君,專註於分享區塊鏈內容

腳印英語,專註於分享英語口語內容



赞(0)

分享創造快樂

© 2021 知識星球   网站地图