建構企業級推薦系統（09）：基于樸素ML思想的協同過濾推薦算法

👩‍💻作者：劉強

👩‍💻簡介：《建構企業級推薦系統》作者，公衆号「資料與智能」主理人，9年推薦系統實戰經驗，持續輸出推薦系統、大資料、機器學習、AI等硬核技術文章

《建構企業級推薦系統》新書已出版，強烈建議收藏加關注，文章免費看！

創作不易，點贊👍 關注💪 支援一下吧✌

《建構企業級推薦系統》往期文章回顧

第一篇：推薦系統介紹

第二篇：推薦系統産品概述

第三篇：推薦算法團隊介紹

第四篇：推薦算法概述

第五篇：從零開始入門推薦算法工程師

第六篇：基于内容的推薦算法

第七篇：協同過濾推薦算法

第八篇：矩陣分解推薦算法

持續更新中......

目錄

一、基于關聯規則的推薦算法

二、基于naive bayes的推薦算法

1. 類似極大似然的思路估計

2.采用權重平均來估計

三、基于聚類的推薦算法

1.基于使用者聚類的推薦

(1) 基于使用者的人口統計學特征對使用者聚類

(2) 基于使用者行為對使用者聚類

(3) 基于社交關系對使用者聚類

2.基于标的物聚類推薦

四、You Tube基于關聯規則思路的視訊推薦算法

1.計算兩個視訊的相似度（關聯度）

2.基于單個種子視訊生成候選視訊集

3.基于使用者行為為使用者生産推薦候選集

4.推薦結果排序

五、Goodle News基于貝葉斯架構推薦算法

1.基于使用者過去的行為來分析使用者的興趣點

2.利用貝葉斯架構來模組化使用者的興趣

(1) 預測使用者在某個時間周期内的真正興趣

(2) 結合使用者在不同時間周期的興趣，獲得使用者精确的與時間無關的真實興趣

(3) 結合使用者真實興趣和目前的新聞趨勢，預測使用者目前的興趣

3.為使用者做個性化推薦

六、Goodle News基于使用者聚類的推薦算法

1.基于MinHash聚類

2.基于聚類為使用者做推薦

總結

參考文獻

在《協同過濾推薦算法》、《矩陣分解推薦算法》兩篇文章中，作者介紹了幾種經典的協同過濾推薦算法。我們在本篇文章中會繼續介紹三種思路非常簡單樸素的協同過濾算法，這幾個算法的原理簡單，容易了解，也易于工程實作，非常适合我們快速搭建推薦算法原型，并快速上線到真實業務場景中，作為其他更複雜算法的baseline。

具體來說，我們在本篇文章中會介紹利用關聯規則、樸素貝葉斯(naive bayes)、聚類三類機器學習算法來做推薦的方法。并且還會介紹3個基于這三類算法核心思想的工業級推薦系統，這3個推薦系統被YouTube和Google分别用于視訊和新聞推薦中(其中會介紹Google News的兩個推薦算法)，在YouTube和Google News早期産品中得到采用，并且在當時情況下效果是非常不錯的，值得我們深入了解和學習。

一、基于關聯規則的推薦算法

關聯規則是資料挖掘領域非常經典的算法，該算法來源于一個真實的案例：“啤酒與尿布”的故事。該故事發生在20世紀90年代的美國沃爾瑪超市中，沃爾瑪的超市管理人員分析銷售資料時發現了一個令人難以置信的現象：在某些特定的情況下，“啤酒”與“尿布”兩件看上去毫無關系的商品會經常出現在同一個購物籃(使用者一次購物所買的所有商品形象地稱為一個購物籃)中，這種獨特的銷售現象引起了管理人員的注意，經過後續調查發現，這種現象出現在年輕的父親身上。

在美國有嬰兒的家庭中，一般是母親在家中照看嬰兒，年輕的父親前去超市購買尿布。父親在購買尿布的同時，往往會順便為自己購買啤酒，這樣就會出現啤酒與尿布這兩件看上去不相幹的商品經常會出現在同一個購物籃的現象。沃爾瑪發現了這一獨特的現象，開始在賣場嘗試将啤酒與尿布擺放在相同的區域，讓年輕的父親可以友善地同時找到這兩件商品，并很快地完成購物；這樣做沃爾瑪超市就讓這些客戶一次購買了兩件商品、而不是一件，進而獲得了很好的商品銷售收入，這就是“啤酒與尿布”故事的由來。

下面我們給出關聯規則的定義，假設

是所有标的物的集合(對于沃爾瑪超市來說，就是所有的商品集合)。關聯規則一般表示為

的形式，其中

是

的子集，并且

。關聯規則

表示如果

在使用者的購物籃中，那麼使用者有很大機率同時購買了

。通過定義關聯規則的度量名額，一些常用的關聯規則算法(如Apriori)能夠自動地發現所有關聯規則。關聯規則的度量名額主要有支援度(support)和置信度(confidence)兩個，支援度是指所有的購物籃中包含

的購物籃的比例(即

同時出現在一次交易中的機率)，而置信度是指包含

的購物籃中同時也包含

的比例(即在

給定的情況下，

出現的條件機率)。它們的定義如下：

支援度越大，包含

的交易樣本越多，說明關聯規則

有更多的樣本來支撐，“證據”更加充分。置信度越大，我們更有把握從包含

的交易中推斷出該交易也包含

。關聯規則挖掘中，我們需要挖掘出支援度和置信度大于某個門檻值的關聯規則，這樣的關聯規則才更可信，更有說服力，泛化能力也更強。

有了關聯規則的定義，下面我們來講解怎麼将關聯規則用于個性化推薦中。對于推薦系統來說，一個購物籃即是使用者操作過的所有标的物的集合。關聯規則 

 表示的意思是：如果使用者操作過 

 中的所有标的物，那麼使用者很可能喜歡 

 中的标的物。有了這些說明，那麼利用關聯規則為使用者

  生成推薦的算法流程如下(假設 

所有操作過的标的物集合為 

 )：

1. 挖掘出所有滿足一定支援度和置信度(支援度和置信度大于某個常數)的關聯規則

；

2. 從1中所有的關聯規則中篩選出所有滿足

 的關聯規則

；

3. 為使用者

生成推薦候選集，具體計算如下：

即将所有滿足2的關聯規則

中的

合并，并剔除掉使用者已經操作過的标的物，這些标的物就是待推薦給使用者

的。

4. 對于3中的候選推薦集

，可以按照該标的物所在關聯規則的置信度的大小降序排列，對于多個關聯規則生成同樣的候選推薦标的物的，可以使用者置信度最大的那個關聯規則的置信度。除了可以采用置信度外，也可以使用者支援度和置信度的乘積作為排序依據。

5. 對于4中排序好的标的物，可以取topN作為推薦給使用者

的推薦結果。

基于關聯規則的推薦算法思路非常簡單樸素，算法也易于實作，Spark Mllib中有關聯規則的兩種分布式實作FP-Growth和PrefixSpan，大家可以直接拿來使用(關于這兩個實作的具體細節，可以閱讀參考文獻10、11、12)。

關于關聯規則算法介紹及怎麼利用關聯規則用于個性化推薦，讀者還可以閱讀參考文獻4、5、6、7、8、9。利用關聯規則做推薦，是從使用者的過往行為中挖掘使用者的行為模式，并用于推薦，隻用到了使用者的行為資料，是以利用關聯規則做推薦也是一種協同過濾算法。

二、基于naive bayes的推薦算法

利用機率方法來建構算法模型為使用者做推薦，可以将預測評分問題看成一個分類問題，将可能的評分離散化為有限個離散值(比如1、2、3、4、5一共5個可行的分值)，那麼預測使用者對某個标的物的評分，就轉化為使用者在該标的物上的分類了(比如分為1、2、3、4、5個類别，這裡不考慮不同類之間的有序關系)。在本節我們就利用最簡單的貝葉斯分類器來進行個性化推薦。

假設一共有k個不同的預測評分，我們記為

，所有使用者對标的物的評分構成使用者行為矩陣

，該矩陣的

-元素記為

，即是使用者

對标的物

的評分，取值為評分集合

中的某個元素。下面我們來講解怎麼利用貝葉斯公式來為使用者

做推薦。

假設使用者

有過評分的所有标的物記為

，

。現在我們需要預測使用者

對未評分的标的物

的評分

(

)。我們可以将這個過程了解為在使用者已經有評分記錄

的條件下，使用者對新标的物

的評分

取集合

中某個值的條件機率：

條件機率

，表示的是在事件

發生的情況下事件

發生的機率，由著名的貝葉斯定理，條件機率可以通過如下公式來計算：

是以，回到我們的推薦問題，

，我們有

我們需要确定具體

值，讓上式左邊的

的值最大，這個最大的值

就可以作為使用者

對未評分的标的物

的評分(

=

)。我們注意到上式中右邊的分母的值與具體的

無關，是以右邊分子的值的大小才最終決定公式左邊的值的相對大小，基于該觀察，我們可以将上式記為：

現在的問題就是怎麼估計上式右邊項的值，實際上基于使用者評分矩陣，這些項的值是比較容易估計出來的，下面我們就來估計這些值。

• 估計

  

其實是

的先驗機率，我們可以用對标的物

評分為

的使用者的比例來估計該值，即

    這裡分母是所有對标的物

有過評分的使用者，而分子是對标的物

評分為

的使用者。

• 估計

  

要估計

，我們需要做一個樸素的假設，即條件無關性假設：使用者

所有的評分

是獨立無關的，也就是不同的評分之間是沒有關聯的，互不影響(該假設就是該算法叫做naive bayes的由來)。實際上，同一使用者對不同标的物評分可能是有一定關聯的，在這裡做這個假設是為了計算友善，在實際使用naive bayes做推薦時效果還是很不錯的，泛化能力也可以。有了條件無關性假設，

就可以用如下公式來估計了：

而

、可用所有對标的物

評分為

的使用者中對标的物

評分為

的比例來估計。即

有了上面的兩個估計，那麼我們利用naive bayes計算使用者對标的物的評分機率問題最終可以表示為 

公式1：使用者對标的物評分的機率估計

有了上式，一般來說，我們可以采用兩種方法來估計

的值。

1. 類似極大似然的思路估計

該方法就是用

，使得 

 取值最大的p對應的

作為

的估計值，即

該方法僅僅将使用者對标的物的評分看為類别變量而忽略具體評分的數值，而下面的方法則利用了評分的具體數值。

2.采用權重平均來估計

使用者

對标的物

的估計

可以取

中的任一值，基于上面的公式1，取每一個值都有一個機率估計

，那麼最自然的方式是可以用這個機率作為權重，利用權重平均來估計

，具體的估計公式如下：

有了使用者對标的物評分的估計，那麼推薦就是順其自然的事情了。具體來說，我們可以計算出使用者對所有未評分标的物的估計值，再按照估計值的大小降序取topK作為給使用者的推薦。這裡說明一下，對于采用極大似然思路的估計(即上面的第一種估計方法)，因為該方法是将評分看成類别變量，那麼肯定有很多标的物的估計值是一樣的，這時如果我們需要再差別這些評分一樣的标的物的話，可以采用估計該值時的機率大小再進行二次排序。

采用貝葉斯方法來做推薦會存在一些問題，具體來說，我們在估計

和估計

時，由于樣本資料稀疏，導緻無法進行估計或者估計值不夠魯棒性的問題。比如在估計

時，我們用公式

來估計，從該式可以看到，如果無使用者或者很少使用者對标的物

有評分(這種情況是存在的，如

是新加入的标的物或者是冷門标的物)，這時可能會出現用

 來估計的情況，即使不是 

，當分子分母都很小時，估計值波動會很大，不夠魯棒，對估計結果影響很大。一般我們可以采用拉普拉斯平滑(Laplacian smoothing)的方法來處理，得到更加穩定的估計值。

針對上面這個例子，我們來說下怎麼利用拉普拉斯平滑來處理：假設

是對标的物

評分分别為

的使用者數，那麼上面的估計就是

增加拉普拉斯平滑後的估計公式就是

從這個公式可以看出，當沒有使用者對标的物

評過分時，就用 

 來估計，這是在沒有已知資訊的情況下比較合理的估計。上式中

是光滑化因子，

值越大，估計越光滑(魯棒性越好)，這時公式對資料就不夠敏感。對于

的估計，也可以采用一樣的方法，這裡不再贅述。

到此為止，我們講完了怎麼利用naive bayes來為使用者做推薦的方法，該方法也是隻利用了使用者的操作行為矩陣，是以也是一種協同過濾算法。

naive bayes方法是一個非常簡單直覺的方法，工程實作也非常容易，也易于并行化。它對噪音有一定的“免疫力”，不太會受到個别評分不準的影響，并且也不易于過拟合(個人覺得前面介紹的條件無關性假設是泛化能力強的主要原因)，一般情況下預測效果還不錯，并且當使用者行為不多時，也可以使用(需要利用拉普拉斯平滑來處理)，而不像矩陣分解等算法，需要大量的使用者行為才能進行推薦。

讀者可以從從參考文獻13、14、15、16中了解更多關于怎麼利用貝葉斯及其他機率方法來做推薦的方案。

三、基于聚類的推薦算法

基于聚類來做推薦有兩種可行的方案，一種是将使用者聚類，另外一種是将标的物聚類。下面來簡單描述一下怎麼基于這兩種聚類來做推薦。

1.基于使用者聚類的推薦

如果我們将所有使用者聚類了，就可以将該使用者所在類别的其他使用者操作過的标的物(但是該使用者沒有操作行為)推薦給該使用者。具體計算公式如下，其中

是給使用者u的推薦，

是使用者所在的聚類，

、

分别是使用者

、

的操作曆史集合。

那麼怎麼對使用者聚類呢？可行的方案主要有如下幾類：

(1) 基于使用者的人口統計學特征對使用者聚類

使用者的年齡、性别、地域、家庭組成、學曆、收入等資訊都可以作為一個特征，類别特征可以采用one-hot編碼，所有特征最終都可以轉化為數值的，最終獲得使用者特征的向量表示，通過Kmeans聚類算法來對使用者聚類。 

(2) 基于使用者行為對使用者聚類

比如采用矩陣分解就可以獲得使用者的嵌入表示，使用者操作行為矩陣的行向量也是使用者的一種向量表示，再利用Kmeans對使用者進行聚類。

(3) 基于社交關系對使用者聚類

如果是社交産品，使用者之間的社交鍊條可以構成一個使用者關系圖，該社交圖中所有的聯通區域就形成了使用者的一種聚類。這種推薦其實就是将你的好友喜歡的标的物推薦給你。

2.基于标的物聚類推薦

如果有了标的物的聚類，推薦就好辦了。從使用者曆史行為中的标的物所在的類别挑選使用者有操作行為的标的物推薦給該使用者，這種推薦方式是非常直覺自然的。具體計算公式如下，其中

是給使用者

的推薦，

是使用者的曆史操作行為集合，

是标的物

所在的聚類。

同時，有了标的物聚類，我們還可以做标的物關聯标的物的關聯推薦，具體做法是将标的物A所在類别中的其他标的物作為關聯推薦結果。

那麼怎麼對标的物聚類呢？可行的方法有利用标的物的metadata資訊，采用TF-IDF、LDA、Word2vec等方式獲得标的物的向量表示，再利用Kmeans聚類。具體的實作細節這裡不介紹，感興趣的讀者可以自行搜尋相關材料做深入學習，作者在《基于内容的推薦算法》這篇文章中也做了比較詳細的介紹。另外，也可以基于使用者的曆史操作行為，獲得标的物的嵌入表示(矩陣分解、item2vec等算法)，使用者行為矩陣的列向量也是标的物的一種向量表示。

參考文獻17、18、19、20有更多關于怎麼用聚類來做推薦的算法，感興趣的讀者可以參考學習。

到此為止，我們講完了基于關聯規則、naive bayes、聚類做個性化推薦的方法。下面我們就基于這幾個方法的思想來介紹三個工業級的推薦引擎，供大家學習參考，同時也希望借助這幾個工業級推薦系統的介紹加深大家對這三個方法的思路的了解。

四、You Tube基于關聯規則思路的視訊推薦算法

該算法建立在一個基本假設基礎之上：如果使用者喜歡種子視訊

，那麼使用者喜歡與種子視訊  

相似的候選視訊

的機率一定很大，候選視訊

與

越相似，那麼使用者喜歡候選視訊

的機率也越大。那麼剩下就是怎麼解決這兩個問題了，一是怎麼計算兩個視訊的相似度，二是怎麼選擇種子視訊，下面我們來分别介紹。同時，我們也會介紹最終怎麼給使用者生成個性化推薦。

1.計算兩個視訊的相似度（關聯度）

該算法是利用關聯規則的思路，在一定時間内(比如24小時内)統計兩兩被使用者同時播放過的視訊對 

，将播放次數計為

，那麼候選視訊

與

的相似度可以表示如下：

其中

是一個歸一化常數，會綜合考慮種子視訊

與候選視訊

的“全局流行度”，如果我們分别記

、

為視訊

、

在上面的一段時間内總的播放次數。那麼我們可以定義

該歸一化函數是非常直覺簡單的，用其他歸一化函數也是可以的。如果用該歸一化函數的話，對所有候選視訊

來說，

是一樣的，是以可以忽略，其實我們是用候選視訊的“全局流行度”

來歸一化。

在分母中，這說明

越大的視訊，與種子視訊

的相似度會更小，該歸一化方法更加偏向于偏冷門的候選視訊。

上面隻是一個非常簡單的描述和計算公式，我們也可以将視訊的metadata、觀看時間等資訊整合進來計算相似度。另外，還需要處理髒的播放行為資料。

2.基于單個種子視訊生成候選視訊集

基于相似度計算公式

，我們可以選擇出種子視訊

的最相似的topN候選集

，一般我們會确定一個最小的門檻值，需要相似度大于該門檻值才會選出來，這也是為了避免選擇很多隻有很少播放量的視訊(這時種子視訊和候選視訊被同時播放的次數也很小)導緻推薦結果太差。

基于上述從種子視訊選擇候選視訊的規則可以看成将所有視訊集合形成了一個有向圖，對于任何一個視訊對

，如果

(候選視訊

在種子視訊

的相似視訊清單集中)，那麼存在一條從

到

的邊，邊的權重為

。

利用該方式為種子視訊生成的視訊候選集，可以作為視訊的關聯推薦，為種子視訊推薦相關的視訊。

3.基于使用者行為為使用者生産推薦候選集

上面講到了單個視訊怎麼生成候選集，那麼對于單個使用者也是很容易采用上面的方式生成推薦候選集的。我們可以将使用者播放過的視訊或者明确表示過喜歡的視訊作為初始種子視訊集。

對于初始種子集

，我們可以采用如下方式來生成候選集：

基于上面視訊的有向圖解釋，我們可以沿着集合

的有向邊向外拓展，對于任意的種子視訊

(

)，我們考慮它的相關視訊集

。我們将所有通過這種方式拓展出的視訊集記為

，那麼我們有

一般情況下，我們計算出

就足夠我們獲得比較多的、效果還可以的、有一定多樣性的推薦候選集了。但實際上，通過這種方式生成的推薦候選集種類比較狹窄，跟使用者的興趣太相似。這種方式雖然生成了使用者可能感興趣的視訊，但是可能使用者沒有太多驚喜，會讓使用者沉浸在比較小的視訊範圍内，就像進入了一個漩渦中，無法發現更大更精彩的世界。

為了拓展使用者的候選推薦集的空間，解決上述越推越窄的問題，我們可以沿着種子視訊集

所在的視訊有向圖進行n次向外拓展(用圖論的術語，就是n次傳遞閉包)，我們記

為通過種子集

中的某個種子視訊通過不超過n次路由可達的所有視訊組成的集合，那麼我們有

注意,

，上面的公式也跟前面提到的

的公式是相容的。那麼我們最終生成的推薦候選集就是

一般N很小(拓展很少的幾步)時就可以獲得非常多具備多樣性的推薦結果，即使對種子集很小的使用者也是如此。通過上述路徑拓展，我們可以為每個候選的推薦視訊關聯一個種子視訊(通過上述拓展，從某個種子視訊到候選視訊的路徑就将候選視訊關聯到了種子視訊)，該種子視訊既可用于後面的推薦結果排序，還可以作為推薦解釋(例如如果候選視訊

是通過種子視訊

獲得的，我們可以用“因為你喜歡/看過

”來作為推薦解釋語,

與

是通過多步相似連結在一起的，它們多少是有一些相似性的，使用者從這兩個視訊中是可以直接感覺到這種相似的，是以該推薦理由是有一定說服力的)。

4.推薦結果排序

通過上面3中的介紹，我們可以為使用者生成推薦候選集了，那麼這些候選集中的視訊怎麼推薦給使用者呢？也即我們怎麼排列這些候選視訊呢？我們需要将使用者更願意點選的排在前面。

我們可以從視訊品質、使用者對視訊的偏好度、多樣性等幾個次元來考慮。

視訊品質是指視訊本身的吸引力，比如視訊的海報清晰度、視訊播放次數、視訊被點贊的次數、視訊被轉載的次數、視訊被收藏的次數等。這些不同次元的視訊品質，我們可以通過打分獲得一個固定的品質得分，具體打分方式可以多種多樣，這裡不再細說。我們這裡記視訊

的品質為

。

通過前面的介紹我們知道每個候選視訊是通過某個種子沿着有向圖通過若幹步的拓展獲得的。如下圖，假設候選視訊

是通過種子視訊

經過k步獲得，下圖中箭頭上方的

是相鄰兩個視訊的相似度。

那麼使用者對視訊

的偏好度可以用如下公式來計算

其中，

是使用者對視訊

的偏好度及它自身的受歡迎程度，我們可以通過使用者播放

的時長或者

總播放量等數值來度量。

如果從

到

有多條路徑，可以選擇最短的路徑，這是因為我們是一步一步拓展擷取候選集的，當某個視訊被某一步拓展到了，後面再拓展到它時，前面已經計算了，所有在這一步就忽略掉。

有了上面介紹的候選視訊得分及使用者對視訊的偏好度，我們可以用下面公式來計算使用者

對視訊

最終的評分：

通過将所有候選視訊按照上述公式降序排列就可以得到候選視訊的排序了。利用上面公式，距離使用者種子視訊集

越遠，通過公式

的相似性連乘得到的值也越小，那麼就有可能排在後面了。那麼我們怎樣解決這個問題獲得多樣性呢？一般我們可以通過限制由同一種子視訊生成的候選視訊的數量來獲得多樣性(因為同一種子視訊生成的視訊多少是有一些相似度的)，或者限制由同一管道産生視訊數量(比如由同一個使用者上傳的視訊)。通過在上述排好序的推薦清單中，剔除掉部分由同一種子視訊生成的視訊或者同一管道産生的視訊，就可以獲得最終的推薦結果。

上面介紹的就是YouTube基于視訊被使用者共同觀看的次數獲得視訊之間的相似度，進而通過視訊相似度傳遞獲得最終推薦的方法。該方法本質上就是關聯規則的思路，隻用到了使用者的播放形式資訊，是以也是一種協同過濾算法。

五、Goodle News基于貝葉斯架構推薦算法

前面第二節簡單講了怎麼利用naive bayes算法來為使用者生成個性化推薦，在這一節我們講解Google News利用貝葉斯架構來做推薦的方法。Google的這篇文章(參考文獻2)采用另外的思路，基于使用者過去看新聞的曆史行為利用貝葉斯架構來預測使用者目前對新聞的興趣，再結合協同過濾來做推薦。下面我們來講解該篇文章的核心思想。

1.基于使用者過去的行為來分析使用者的興趣點

首先将所有新聞按照事先确定好的類别分成若幹類(主題)：

，如“世界”、“體育”、“娛樂”等類别。

首先計算某個使用者

在某段時間周期

(比如按照一個月一個周期等)内的點選行為在上述類别上的分布，記為

公式1：使用者u在時間周期t内的行為在新聞主題上的分布

這裡，

代表使用者

在時間周期

内點選主題類别 

的次數。

是該使用者在這段時間周期内點選新聞的總數量。

表示使用者

在時間周期

内在各個新聞主題類别上的時間花費分布，反映了使用者的興趣分布。

新聞是有地域差異性的，同樣地，類似單個使用者的興趣偏好分布，我們可以統計某個國家或者某個地區的所有使用者點選行為的整體在時間周期

内在上述新聞主題上的分布。我們将該分布記為

。計算方法和上面單個使用者一樣，将該國家或地區所有使用者當成一個整體來計算。

該文章通過大量的資料分析，最終得到如下4個結論，後面的貝葉斯架構也是基于這幾個結論來展開的。細節的分析讀者可以閱讀參考文獻2。

(1) 使用者的興趣确實随着時間變化；

(2) 公衆對新聞的點選分布反映了興趣的發展趨勢，并受到重大事件(如世界杯等)的影響；

(3) 不同國家/地區對新聞的偏好是不一樣的，存在不同的發展趨勢；

(4) 從某種程度上說，單個使用者的興趣變化趨勢是受到該使用者所在國家/地區的新聞趨勢變化影響的；

有了上面的基本概念和初步資料分析得到的結論作為基礎，下面我們來說明怎麼用貝葉斯架構來為使用者的興趣模組化。

2.利用貝葉斯架構來模組化使用者的興趣

我們可以将使用者的興趣分為兩種：一種是使用者的真實興趣，一種是會受到國家/地區大的興趣趨勢影響的臨時興趣。使用者的真實興趣是由使用者的性别、年齡、受教育程度、專業等決定的，它是相對穩定的，不太會随着時間而急劇變化。另一方面，當使用者覺得要讀什麼新聞時，是會受到使用者所在區域新聞趨勢的影響的，這種影響是短期的，是随着時間變化的。

基于使用者點選行為模式和使用者所在地群體的行為模型，可以通過貝葉斯架構可以很好地預測使用者目前對新聞的興趣，具體可以通過如下三個步驟來獲得使用者的目前興趣。

(1) 預測使用者在某個時間周期内的真正興趣

對于特定時間周期

内的某個使用者

，

是使用者對所有新聞主題上的點選分布，

是使用者所在地域整體使用者的興趣分布，代表的是興趣趨勢。我們期望學習使用者的從

呈現出的而不會受到

幹擾的真實興趣。

我們用

來表示使用者在新聞主題

上的真實興趣，它是一個條件機率，表示在新聞主題為

的條件下，使用者進行點選的機率。利用貝葉斯公式，我們可以采用下式來計算

。

公式2：使用者點選屬于主題

的文章的機率

上式中

是使用者點選的所有新聞中該新聞屬于主題

的機率，它可以從使用者的點選分布

中估算出(參見上面的公式1，可以用

的第i個分量來估算)。

而

是新聞屬于主題

的先驗機率，也就是在時間周期

内所有釋出的新聞屬于類别

的比例，它與使用者所在地域的新聞變化趨勢相關，如有有更多的有關主題

的新聞事件發生，那麼關于主題

的新聞就會越多。我們可以用整體分布

中的第i個分量來近似估計

。

是使用者點選任何一個類别的文章的先驗機率，與具體的文章主題無關。

從上面公式2知道，

表示使用者對主題

的感興趣程度，不同于該地區其他使用者的興趣。如果使用者讀了很多體育類的新聞，而很多其他使用者也讀了體育類新聞，這可能是有一些體育相關熱點事件引起的。相反，如果該使用者閱讀了大量體育新聞而該地區其他使用者很少讀體育新聞，這就代表的是使用者真的對體育感興趣。

(2) 結合使用者在不同時間周期的興趣，獲得使用者精确的與時間無關的真實興趣

上面(1)中計算了使用者在一個時間周期

内的興趣偏好，我們可以将使用者在過去統計周期内所有時間周期的興趣歸并起來獲得使用者綜合的對新聞類别的真實興趣偏好，具體參見下面公式的計算邏輯。

上式中

是使用者在時間周期

内總的新聞播放量。我們可以假設使用者在所有時間周期内點選一篇新聞的先驗機率是固定不變的，也即假設上式中的

與時間周期

無關，我們記為

。那麼上式可以改寫為下面的

公式3：使用者在過去統計周期内所有時間段的綜合興趣

上面的公式3就是使用者的真實興趣，該興趣其實是使用者在多個時間周期内的興趣的某種權重平均。

(3) 結合使用者真實興趣和目前的新聞趨勢，預測使用者目前的興趣

如前面所說，使用者的興趣可以分解為兩部分，一部分是使用者長期的的真實興趣，另外一部分是受到目前趨勢影響的短期興趣。(1)、(2)基于使用者過去的點選播放行為計算出了使用者的長期的真實興趣。為了度量使用者目前對新聞的短期興趣，我們用使用者所在地域的所有使用者在一個較短時間段(比如過去一個小時)的整體點選分布來刻畫(用

來表示)，由于所在地域有大量使用者，在這段較短時間内也有足夠多的資料來準确計算出哪些新聞主題是熱門的。

我們的最終目标是預測使用者在将來一段時間的點選分布，同樣地，我們可以用貝葉斯公式得到下面的計算公式：

我們用使用者的真實興趣

(公式3)來估計

     ，并且假設使用者點選任何一篇新聞的機率為常數，不受時間影響(即假設

=

)，那麼上式就可以表示為(将公式3代入進來)

我們可以在上式中加上一個虛拟點選項，它跟目前新聞趨勢的機率分布

同分布，那麼使用者在未來短時間内對新聞的興趣偏好機率最終變為

公式4：使用者目前對新聞主題的興趣偏好機率

上式中的

就是虛拟點選數(在參考文獻2中取值為10)，它可以看成是一個光滑化的因子，當某個使用者隻有非常少的點選曆史時，這時是使用者目前的新聞趨勢(

)來預估該使用者的點選機率，這在沒有太多該使用者曆史資料的情況下是一個合理的估計。當

遠遠大于

時，上式就可以忽略

，還原為使用者真實的點選分布預估。

上述預估使用者将來段時間内的興趣分布的方法的一個重要優點是，我們可以增量地計算使用者的點選分布。我們可以将過去每個時間周期

對應的

和

的值事先存起來，當更新使用者的興趣偏好機率時，隻需要将最近一個時間周期的值計算出，利用上面的公司4及預先存下來的過去時間段的值就可以得到使用者最新的興趣偏好分布。

3.為使用者做個性化推薦

為了對推薦候選集進行排序獲得最終的推薦結果，該推薦算法計算出兩個統計量：一個是

，稱之為資訊過濾得分，另外一個是

，即協同過濾得分(利用協同過濾算法預測的使用者對新聞的得分，可以利用參考文獻3中的方法得到)。其中

的計算過程是這樣的，先獲得該文章的類别

，再基于上面的公式4得到使用者對類别

的的偏好機率，該值作為

的值。我們将這兩個得分相乘，最終利用如下的公式來計算使用者對某個新聞的興趣得分。

最終基于上述公式計算出該使用者對所有新聞的得分，取得分最高的topN作為最終的推薦結果。該方法通過在Google news上驗證，比單獨采用協同過濾有更好的預測效果。

該方法利用使用者過去及使用者所在地區的點選行為來預測使用者目前對新聞的偏好機率，再與協同過濾結合進行最終的推薦。預測使用者興趣偏好機率的過程隻用到了使用者及使用者所在地域全體使用者對新聞的點選資料，是以也是一種協同過濾方法。細節的實作方案，讀者可以閱讀參考文獻2進行進一步了解。

六、Goodle News基于使用者聚類的推薦算法

參考文獻3中利用了3種模型來預估一個使用者對一個新聞的評分，最終通過權重平均獲得使用者對新聞的最終評分，其中第三種方法covisitation的思想我們在《協同過濾推薦算法》第六節“近實時協同過濾算法的工程實作“有詳細講解，本質上是一種關聯規則的思路，我們這裡不再介紹。另外兩種算法分别是基于MinHash和PLSI聚類的方法，在這裡我們隻介紹MinHash算法，PLSI算法讀者可以自行閱讀參考文獻3來了解。

1.基于MinHash聚類

對于使用者

，他的點選曆史記為

。那麼兩個使用者

的相似度可以用Jaccard系數來表示：

有了兩個使用者之間的相似度，我們可以非常形式化地将相似使用者點選過的新聞通過上面的相似度權重推薦給使用者

。但是使用者數和新聞數都是天文數字，無法在極短時間内為大量使用者完成計算。這時，我們可以采用LSH(Locality Sensitive Hashing)的思路來計算，大大減少計算複雜度。LSH的核心思想是，對于一組資料(對于我們這個場景來說，這一組資料就是使用者的曆史點選記錄

)，我們可以用一組哈希函數來獲得哈希值，如果兩組資料非常相似，那麼哈希值沖突的機率也越大，而沖突率是等于這兩組資料的相似度的。當我們用Jaccard系數來計算使用者點選曆史的相似度時，這時的LSH就叫做MinHash。

我們先來說明怎麼為一個使用者

計算hash值，所有新聞集為

，我們對集合

進行一次随機置換，置換後的有序集合記為

(

)，我們計算使用者

的哈希值為

可以證明(有興趣的讀者可以自行證明，或者參考相關參考文獻)，兩個使用者

 的哈希值沖突(值一樣)的機率就是

用Jaccard系數計算的相似度。是以我們可以将MinHash認為是一種機率聚類方法，對應的哈希值就是一個類：

，所有哈希值為

的使用者聚為一類

。

我們可以取

個置換(即

個哈希函數)，将這

個哈希函數得到的哈希值拼接起來，那麼兩個使用者

這

個拼接的哈希值一樣的機率就等于

。很顯然，通過将

個哈希值拼接起來得到的聚類更精細(

個哈希值都相等的使用者肯定更少，是以類

更小，更精細)，并且相似度也會更高。從找使用者最近的領域(最相似的使用者)的角度來看，将

個哈希值拼接起來的方法的精準度更高，但是召回率更低(聚類更小了，是以召回的新聞更少了，是以一般召回率就降低了)，為了提升召回率，獲得更多的相似使用者，我們可以将這個過程并行進行

次，最終每個使用者獲得

個聚類，相當于進行了

次召回，在論文中作者建議

取2到4，

取10到20。

在實際的工程實踐上，由于新聞數量太大，進行置換操作耗時很大，可以采用簡化的思路(精度會打折扣)，對于上面提到的

個哈希函數(置換)，我們事先取

個獨立的随機種子值與之一一對應，每個随機種子就是哈希函數的替代。對于每個新聞及每個種子值，我們利用該種子值和該新聞的Id(是整數值)，利用一個特定的哈希函數

計算出一個哈希值，該哈希值作為利用前面講的通過置換後該新聞的下标，那麼采用這種方法後使用者

的哈希計算公式如下：

該方法不需要對新聞集進行置換，會大大減少計算量，并且隻要這個特定哈希函數

的取值範圍在0到

之間，那麼沖突機率就會比較小，通過這種近似的MinHash值與真正的MinHash值性質近似。

上面講解了MinHash聚類的算法實作細節，具體工程實作時是可以用Hadoop或者Spark等分布式計算平台來并行計算的，這裡不細說。我們可以将每個使用者的聚類及每個聚類包含的使用者用反向索引表的格式存儲起來，友善後面做推薦時查閱。

2.基于聚類為使用者做推薦

有了使用者的聚類，我們可以采用如下步驟來為單個使用者生成個性化推薦，每個使用者的推薦政策是一樣的，是以可以采用分布式計算平台Spark等工具來并行化處理。

(1)  計算出使用者

對新聞

的評分

(2) 計算出使用者

對所有新聞的評分

(3) 将所有新聞評分降序排列，取topK作為該使用者的推薦

上面的(2)、(3)是非常簡單的處理，我們重點來說一下(1)，怎麼計算使用者

對新聞

的評分。首先我們可以得到使用者

所屬的所有類别

，對于每個類别

，取出該類别中所有的使用者對新聞

的點選次數之和(我們可以事先将每個類别中使用者點選過的新聞及次數存儲起來，友善查找)，再除以該類别所有點選之和，得到該類别對新聞

的評分，那麼使用者

所屬的類别對新聞

的總評分為：

這裡的

即是剛剛提到的類

中所有使用者對新聞

點選次數之和，

是類

所有使用者的所有點選次數之和。我們用上式計算出的

來表示使用者

對新聞

的評分。

至此，基于我自己的了解，簡單介紹完了Google News基于使用者聚類的推薦算法。該方法也隻用到了使用者及其他使用者的新聞點選行為，是以也是一種協同過濾算法，該算法的細節讀者可以閱讀參考文獻3。參考文獻17、18、19、20有更多關于怎麼用聚類來做推薦的算法，感興趣的讀者可以參考學習。

總結

本文講解了關聯規則、樸素貝葉斯、聚類等三類基礎機器學習算法怎麼用于個性化推薦的理論知識。同時從算法原理和工程實作的角度簡單總結了YouTube和Google News的三篇分别采用關聯規則、樸素貝葉斯、聚類思路來做推薦的論文。這幾篇論文有很強的工程指導意義，值得大家學習。

雖然這些算法原理簡單、容易了解，看起來不那麼高大上，但是這些算法卻在工業界有過非常好的應用，在當時算是非常優秀的算法。這些算法現在可能看起來太簡單了，也可能不會用在現在的推薦系統上，但它們樸素的思想下面蘊含的是深刻的道理，值得我們推薦從業者學習、思考、借鑒，希望讀者可以很好地了解它們，并吸收這些樸素思想背後的精華。

參考文獻

1.The YouTube Video Recommendation System

2.Personalized News Recommendation Based on Click Behavior 

3.Google news personalization: Scalable online collaborative flitering

4.Robustness of collaborative recommendation based on association rule mining

5.Analysis of recommendation algorithms for e-commerce

6.Fast algorithms for mining association rules

7.Efficient adaptive-support association rule mining for recommender systems

8.Mining navigation history for recommendation

9.Collaborative filtering by mining association rules from user acess sequences

10.Mining frequent patterns without candidate generation

11.Pfp: parallel fp-growth for query recommendation

12.Mining sequential patterns by pattern-growth: the PrefixSpan approach

13.Empirical analysis of predictive algorithms for collaborative filtering

14.A Bayesian model for collaborative filtering

15.Collaborative filtering with the simple Bayesian classifier

16.Probabilistic memory-based collaborative filtering

17.Clustering methods for collaborative filtering

18.Rectree: A efficient collaborative filtering method

19.Scalable collaborative filtering using cluster-based smoothing

20.Latent class models for collaborative filtering

關注「資料與智能」，支援強哥，優質好文持續更新中……✍