達觀數據：簡談馬爾可夫模型在個性化推薦中的應用

來自專欄挖掘數據背後的價值23 人贊了文章

隨著互聯網的飛速發展，個性化推薦已經成為各大網站、手機客戶端的必備服務。如何持續優化、進一步提高推薦的精準度是一項複雜又令人興奮的工程。

主流的推薦系統有協同過濾、基於內容的推薦、基於社交網路的推薦等。

很多推薦演算法沒有考慮到用戶的短期興趣，而用戶的興趣又是隨著時間動態變化的，所以有效地捕獲用戶的興趣偏好轉換對提高推薦的準確性有著很大的輔助作用。

馬爾可夫模型通過觀察用戶短期的行為數據，生成一個狀態轉移矩陣，根據該矩陣預測接下來一個時間點的用戶行為，有效地利用了用戶的短期興趣偏好信息。

概念

安德雷·安德耶維齊·馬爾可夫Андрей Андреевич Марков（1856.6.14－1922.7.20），俄國數學家。

1874年馬爾可夫入聖彼得堡大學，師從切比雪夫，畢業後留校任教。

1886年當選為聖彼得堡科學院院士。馬爾可夫的主要研究領域在概率和統計方面，他因提出馬爾可夫鏈的概念而享有盛名。

馬爾可夫鏈已經成功應用到物理、化學、語音識別、信息科學、金融等領域，谷歌所使用的網頁排序演算法就是由馬爾可夫鏈定義的。

馬爾可夫過程

對於一個隨機過程，如果其未來所處的狀態僅與其當前狀態有關，而與過去的狀態無關，則該隨機過程被稱為馬爾可夫過程。

馬爾可夫鏈

假設馬爾可夫過程 的參數集T是離散的時間集合，

則相應 取值集合空間是離散的狀態集

設有隨機過程 ,

若對於任意的整數 和任意 ，

條件概率滿足

則稱 為馬爾可夫鏈。

簡單點就是說，時間和狀態都是離散的馬爾可夫過程即為馬爾可夫鏈。

為馬爾可夫鏈 在時刻n的一步轉移概率，其中 ，簡稱為轉移概率。

轉移概率矩陣

設P表示一步轉移概率 所組成的矩陣，且狀態空間 ，則

稱為系統狀態的一步轉移概率矩陣，它具有的性質：

（1） ;

（2） .

n步轉移概率、轉移矩陣

為馬爾可夫鏈 的n步轉移概率，並稱 為馬爾可夫鏈的n步轉移矩陣。

舉個栗子

說到這裡，可能還會有人問「隨機過程是啥玩意兒」，「馬爾可夫鏈到底是什麼鬼」。

數學定義總是簡單、精準、嚴謹，幾乎沒有邏輯漏洞，但可能不是特別容易理解，那麼這個小節我們舉幾個栗子，更形象的解釋下這些概念。

隨機過程，就是一系列隨機變數的集合。

比如，每丟一次硬幣，便產生一個隨機變數X，那麼一次又一次的丟下去，便產生一系列的隨機變數X1,X2,…，Xi,…。隨機變數序列集合起來就是一個隨機過程。

那麼馬爾可夫鏈又是什麼呢？

它其實是隨機過程的一種，具體是什麼還是舉個例子吧。

無忌是達觀數據的員工，每天下午4點到5點有仨狀態：吃水果(公司免費提供的、各種管飽)、寫代碼、技術交流，這就是傳說中的狀態分布。那麼明天的這個時間段無忌會做什麼呢？後天呢？大後天呢？假如他的狀態轉移是有概率的，比如今天吃水果，那麼明天還吃水果的概率是0.3，寫代碼的概率是0.6，技術交流的概率是0.1。

直接看下錶：

左邊一列是今天的狀態，上面一行是明天的狀態。

圖中的0.1表示的是無忌今天吃水果，第二天技術交流的概率。

這就構成了一階轉移概率矩陣。

這個例子中，無忌明天的狀態僅僅與今天的狀態有關，與過去無關，同時三種狀態是離散的，構成了一個馬爾可夫鏈。

推薦應用

用戶行為分析

為了讓推薦結果符合用戶口味，我們需要深入了解用戶。如何才能了解一個人呢？

《論語 · 公冶長》中，

「 聽其言，觀其行。」

也就是說，可以通過用戶留下的文字和行為了解用戶的需求。

用戶行為數據最簡單的存在方式就是日誌，用戶的每次瀏覽、點擊、購買、收藏等都記錄在日誌中，這些行為數據對於接下來的構建轉移概率矩陣有著至關重要的作用。

假如在某購物網站中，對某物品的一次購買，稱作一個狀態。

某用戶在 時刻購買了物品a，這裡我們定義為狀態{a}；

在接下來時刻 該用戶又購買了物品b和c，則由狀態{a}轉移到了狀態{b}或{c}；

這時在 時刻購買了d，狀態轉移到了{d}，這樣的話用戶不停的購買，狀態也不停地轉移。

形成了一條購買鏈，如圖。

在這個例子中，我們僅僅討論了針對單個用戶如何構建購買鏈，對於所有用戶來說，道理一樣，只不過狀態集擴大了而已。

轉移矩陣的構建及使用

我們先討論下非個性化馬爾可夫模型，即假設每一個用戶的轉移矩陣是相同的，這樣的話個性化推薦只能體現在將轉移矩陣應用在用戶的最後一次行為操作。

繼續舉個例子，通過對某段時間內所有用戶行為進行分析，抽取出這些狀態轉移樣本數據：(a,b,c)->(b,c)、(b,c)->(a,b)，然後我們可以得到如下轉移矩陣M：

假如某個用戶當前的操作物品是a、c，那麼根據上面得出的轉移矩陣，我們就可以計算出接下來該用戶操作各個物品的程度，對這些結再進行標準化後就可以認為是接下來對各個物品進行操作的概率，

這個計算邏輯看起來可能不是特別容易理解，直接上公式，簡潔明了！

最後對

進行標準化即可得到接下來對a、b、c的操作概率。

，其中A是用戶當前的行為矩陣，M為計算出來的轉移矩陣，對結果F進行標準化後即可得到未來用戶行為的概率預測矩陣。有了當前行為以及概率預測矩陣，我們就可以根據概率大小進行排序，優先推出概率大的物品，達到個性化的目的。

而對於個性化馬爾可夫模型，可以怎麼處理呢？

這裡我們可以將對物品的偏好轉化為對特徵的偏好，假如某個物品的特徵是「娛樂、影視」，那麼對該物品的一次行為操作可以轉化為對「娛樂」、「影視」的操作。

這樣，通過對某個用戶的歷史行為日誌進行挖掘分析，就可以得出用戶在操作「娛樂」特徵的情況下，下個時間段操作「影視」的概率，也就構成了用戶的特徵喜好狀態轉移矩陣。

這樣的話，可以計算出每個用戶的特徵喜好狀態轉移矩陣，達到真正意義上的個性化。

多行為加權融合

上面提到的轉移矩陣的計算是基於用戶的某一種行為操作，即通過用戶的單一行為來得到用戶的偏好轉換。

為了能更好的表示用戶的喜好狀態轉換，可以通過多行為加權融合的方式來解決。

假如用戶的行為操作有點擊、購買、收藏、點贊，那麼可以對每種行為類型計算出特徵喜好狀態轉移矩陣，並得出用戶在下個時刻的操作列表，也就是推薦列表，最後將多個推薦列表進行加權融合得出最終的列表結果。

多階馬爾科夫融合

考慮到用戶操作行為的隨機性，用戶從狀態s1到狀態s5可能受到s2、s3或者其他因素的影響。並且在個性化推薦長尾現狀的部分影響下，單個用戶在極短時間內興趣偏好不會發生太大變化。

這裡可以通過採用多階馬爾可夫模型融合的方式進行對這種情況進行優化。比如一段時間內用戶從狀態s1到s2，再到s5，即s1->s2->s5，那麼這次的狀態轉移記為s1->s5的二階轉移次數。

通過計算用戶行為的多階狀態轉移矩陣，基於相關矩陣得出預測列表，最後加權融合即可得到我們需要的推薦列表。

這裡具體採用幾階模型，可以根據實際場景進行效果測試，階數越高，預測的結果更大的基於用戶長期的興趣偏好，階數約低，預測的結果更大的是基於用戶短時間內的興趣偏好。

總結

本文首先簡單介紹了馬爾可夫相關的數學概念，然後通過例子形象地解釋了隨機過程、馬爾可夫、轉移概率等實際含義。

在推薦系統的應用上，分析了如何通過用戶操作記錄進行構建狀態轉移矩陣以及轉移矩陣的使用。

考慮到推薦的效果，我們又進一步介紹了多行為加權融合以及多階馬爾可夫融合的兩個方案。

作者簡介

張可，達觀數據推薦演算法工程師，負責達觀數據個性化推薦引擎的研發、優化，以及推薦系統中機器學習演算法的具體應用。一直在路上。