基于變長馬爾科夫模型的用戶購物行為分析

鄭天宇，吳愛華

（上海海事大學信息工程學院，上海 201306）

基于變長馬爾科夫模型的用戶購物行為分析

鄭天宇，吳愛華

（上海海事大學信息工程學院，上海 201306）

用戶的行為序列具有的連續性特征能夠很好地反映用戶的購買習慣或者用戶的購物偏好，而這種特性在利用顯式反饋算法進行商品推薦時往往會被忽略。因此，根據用戶的購物行為等隱式反饋信息，提出一種基于變長馬爾科夫模型的“自適應兩階段過濾”推薦算法。該算法主要是利用概率后綴樹構建變長馬爾科夫模型，然后利用該模型對用戶行為序列數據集進行多次分類過濾，以判斷出用戶對商品的購買傾向，生成用戶的商品推薦列表。實驗表明所提出的推薦策略具有不錯的推薦效果。

用戶購物行為；概率后綴樹；變長馬爾科夫；個性化推薦

0 引言

在電子商務領域，以用戶的瀏覽、收藏、加入購物車和購買為主要特征的用戶購物行為是其主要的隱式用戶反饋［1］信息。隱式反饋信息因為不需要用戶主動地進行反饋操作，所以相對于顯式反饋數據［2］，隱式反饋數據有著收集成本低，數據規模大等特點。然而在當前的個性化推薦系統的研究中大量的分析挖掘是基于顯式反饋信息，這不僅浪費了海量的隱式數據資源，也限制了個性化推薦系統的研究與發展。因此利用用戶的購物行為等隱式反饋數據進行個性化推薦研究具有很高的現實意義。

在電商領域的用戶購物行為除具有一般的序列數據的特點之外，其還有以下特征：

（1）用戶的行為序列是隨時間變化的動態變量，并且這種動態變量的發展總是承前啟后的，當前變量的改變不一定馬上在下一步的轉移狀態中體現出來。未來的狀態也不單單與現在的狀態有關，其還受到過去的一個或者多個狀態的影響。即用戶行為序列數據中元素的狀態轉移不具有一階無后效性。

（2）用戶行為特征所代表的用戶購買意愿具有時效性。即以往的行為特征記錄對用戶當下的購買決定的影響隨時間的推移逐漸減弱。

（3）用戶行為記錄中各行為特征之間的時間間隔對整個序列來說也是一種重要影響因素。例如序列A＜瀏覽，瀏覽，?，瀏覽，瀏覽，加入購物車＞（其中?代表序列存在的時間間隔）和序列B＜瀏覽，瀏覽，瀏覽，加入購物車，購買＞，如果將A中的時間間隔去掉，從表面上看A中的瀏覽次數大于B，即可以認為A中數據具有的購買可能性高于B。然而實際上A中的用戶行為對購買行為的出現真正起到直接作用的可能僅僅是間隔之后的一系列行為。

基于以上對用戶購物行為的分析，本文提出了將基于用戶購物行為數據的個性化推薦研究問題轉化為基于用戶購物行為序列集的序列分類問題的思路，即根據用戶購物行為所代表的用戶購物興趣傾向程度來判斷用戶是否會產生購買行為，并據此將用戶行為序列分為購買類和非購買類兩類序列數據集。考慮到用戶購物行為序列無一階無后效性和時效性特點，本文提出了基于變長馬爾科夫模型的序列分類算法，并在此基礎上提出了用戶購買興趣傾向度的概念和計算方式。本文的主要貢獻有：

（1）利用變長馬爾可夫模型能夠模擬多個以往序列元素對未來元素的跳轉概率的影響來解決用戶購物行為序列中元素跳轉的無一階無后效性的問題。

（2）改進了變長馬爾可夫模型的相似度計算方式，提出了自適應的相似度計算方法以解決用戶的行為序列元素的時效性要求。

（3）提出兩階段過濾法，使得每一次的預測結果都可以成為下一次預測模型的訓練樣本集，能夠達到動態地跟蹤用戶行為習慣的效果，解決了用戶行為特征數據因時間久遠而與用戶當前行為習慣相差太大的問題。同時，也提高了模型構建的效率和預測的準確性。

1 相關工作

目前對用戶購物行為研究方法根據其利用隱式反饋數據的方法的不同可以將其分為兩類：直接利用隱式反饋數據法和將隱式反饋數據轉化為顯式評分 （間接利用）方法。間接的利用隱式反饋數據方法，先對各種隱式反饋特征賦予一定的權重，將其轉化為顯式的評分數據，然后再利用已有的顯式反饋算法加以處理。如文獻［3］中將隱式數據轉化為顯式數據之后再將其轉化為分類問題處理，文獻［4］中利用加權的序列模式挖掘方法。這類方法在對用戶的行為特征進行評分時確定其評分的權重太過隨意，而且這種直接的轉換方式會忽略掉用戶行為特征所具有的實效性的特點。如＜a，d，a，a，b，a，a，d＞，＜a，b，a，a，c，a，a，b＞（其中 a代表瀏覽，b代表收藏，c代表加入購物車，d代表購買），其中序列元素a，b，d在轉化為顯式數據時其所代表的行為權重是一樣的，然而因為序列具有的時效性特點，使得不同的位置的相同元素所代表的用戶對商品“感興趣”程度是不一樣的。相比間接利用方式，直接利用用戶的隱式反饋數據克服了“打分”的缺陷，如BPR（Bayesian Personalized Ranking）［5］，貝葉斯分類［6-7］，這兩種算法都為能考慮到用戶購物行為序列的時效性問題，當用戶行為序列數據變化很小的時效果明顯，但是當用戶行為序列數據變化很大時，其并不能及時地反映用戶興趣的變化。而本文提出的基于變長馬爾可夫模型克服了以上這些方法存在的不足。

2 模型及相關概念的介紹

本節主要討論用戶購物行為序列數據的相關定義并介紹分析若干的相關工作。首先說明全文中使用到的相關概念及記號。

定義1用戶的購買行為特征是指用戶在購物網頁上的操作標識，如瀏覽、收藏、加入購物車、購買等。設αi為用戶的一個行為特征，集合A=｛α1，α2，…，αi｝為用戶的所有可能的行為特征集.為了解決用戶行為序列中時間間隔被忽略的問題，特別定義兩個特殊符號作為行為序列的間隔符，?代表一條行為序列中的短期間隔（以小時為單位），$代表一條行為序列的長期間隔（以天為單位）。則最終的行為集合A=｛α1，α2，…，αi，$｝。

定義 2 給定一個用戶集U=｛u1，u2，u3，…，up｝，一個商品目錄集I=｛e1，e2，e3，…，eq｝，用戶ui對商品ej的一條瀏覽行為序列為 s'uiej=｛s1，s2，…，sl｝。

其中sl∈A，sl稱為序列 s'uiej的一個元素；l稱為序列 s'uiej'的長度，表示|s'uiej|；1～l之間的數字稱為序列的位置。由所有的用戶的行為序列組成的集合表示為S=｛sm'|sm'=s'uiej，ui∈U，ej∈I｝，m是序列集的個數。

變長馬爾可夫模型［8］是一個平穩隨機過程｛Xn，n= 0，1，2，…，Xi∈Σ｝，其中Σ為有限狀態集｛xi｝，模型中的轉態轉移概率為：

其中，k是模型的階，有限序列（xn-k，…，xn-1）稱為子序列。倘若將用戶行為序列集對應于狀態集Σ，則用戶行為序列也可看成一個平穩的隨機過程，相應的用變長馬爾可夫模型表示如下：

將用戶行為序列依據其是否產生購買將其分為購買類和非購買類，利用訓練算法為每一個類別訓練一個變長馬爾可夫模型。然后對每一個新的未知序列s'= ｛s1，s2，…，sm｝，計算s'與每一個模型的相似度。序列與模型的相似度計算公式如下：

其中，pi（si）=p（si|si-k，…，si-1）（k＜i＜l，l是序列的長度，k是馬爾科夫模型的階數）.當i≤k時，有：

上式中的pi（si）又稱為由以往的一段序列狀態si-k，…，si-1跳轉到下一個序列狀態si的跳轉概率，它的計算公式如下：

其中，N（si-k），…，si-1，si）表示在分類訓練模型Mj中序列si-k，…，si-1，si出現的次數。序列模型Mj由馬爾科夫模型訓練得來，在3.2節中會詳細講解模型的構建過程。

定義3用戶ui對商品ej做出購買決定的傾向程度θij，是用戶的行為序列s'=｛s1，s2，…，sm｝與訓練集中購買行為序列特征類M1的相似度和非購買行為序列特征類M2的相似度的比值。其計算公式如下：

通常當P（s'|M1）＞P（s'|M2）時，判定序列s'屬于購買類M1。因此，設閾值δ（δ≥1），當用戶ui對商品ej做出購買決定的傾向度θij＞δ時，則由用戶ui對商品ej組成的二元＜ui，ej＞作為推薦數據集輸出。需要注意的是，當θij等于無窮大時，將其設為一個足夠大的值，一般設為θij＞1值的均值。

定義4樣本集有若干個類別，每個類別都有模型Mi與之對應，對于任意序列s'，若序列s'與模型Mi的相似度P（s'|Mi）大于序列s'同其余模型的相似度，則稱序列s'相似于模型Mi，亦可稱序列s'屬于類別Mi。若有模型PMi中的每一條序列都相似于Mi，則稱PMi是Mi的子類。

性質1設序列a，模型M1和PM1，PM1是M1的子類，若序列a相似于PM1，則a一定相似于M1。即若序列a屬于類PM1，則其也屬于類M1。

性質2若PM1是M1的子類，子類PM1的序列特征要高于M1。

3 變長馬爾科夫模型的構建與算法設計

在下面各個小節中，將一一介紹基于概率后綴樹的變長馬爾可夫模型的構建方法，相似度的自適應計算方法以及兩階段模型的實現過程。

3.1 概率后綴樹（PST）的構建

在實現變長馬爾科夫模型的算法中概率后綴樹［9］算法要比一般的CA算法計算復雜度低，并且其可在線性時間與空間復雜度內構建［10］。因此本文采用概率后綴樹算法來構建變長馬爾科夫模型。本節主要是簡要介紹一下概率后綴樹的結構，并給出變長馬爾可夫模型的概率后綴樹構造過程。

概率后綴樹（PST）模型是基于后綴樹建立起來的，該模型樹是一棵非空樹。樹中每一個PST節點都代表一個行為序列元素，并且每個節點都包含一個|A|維概率分布向量（|A|是指用戶行為特征集的個數）。并且樹中的每個節點的出度在0到|A|之間，每條邊代表A中的一個符號標記，每個節點的邊無重復標記出現，每個節點序列是由根節點到該節點所經過的邊的標記構成。根節點的概率向量是A集合中每個行為事件的無條件概率。其他節點的概率分布向量是該序列節點的下一個行為事件出現的條件概率組成。例如，有序列s，它的下一個事件α出現的概率為p（α|s）。p（α|s）等于序列｛s，α｝出現的次數/序列s出現的次數。

如圖1所示一個序列s=accactact

圖1

圖2 樹中的每條邊代表一個字符如a，c，t，每個節點存儲著有這個節點跳轉到下一個節點的條件概率向量，如［1/3，4/9，2/9］，［0，1/3，2/3］。如由行為特征序列a跳轉到狀態c的概率為P（c|a）=1，由行為特征序列ac跳轉到狀態c的概率為P（c|ac）=1/3。

本文的PST的構造算法是基于Ukkonen法［11］構建的，則本文的PST樹的構建偽代碼介紹如下：

算法：Build-PST（S）：

輸入：訓練數據集S，事件集合A

輸出：PST樹

Begin

初始化PST，根節點的概率向量值為每個符號在所有的符號序列中出現的相對頻率。

當S≠?，取s∈S并從S中刪除s：利用Ukkonen方法將序列s中元素加入樹中

If?σ∈A：

計算p（σ|s）→proArray End

3.2 自適應分類部分

在變長馬爾科夫模型中，高階馬爾科夫增強馬爾科夫模型的分類預測能力，然而同時其也面臨究竟多少階的馬爾科夫模型合適的問題。文獻［12］認為高階模型可以減少預測的不確定性，但階數的高低有一個改善的極限，而這個極限可以通過歷史數據的最大相關性獲得。在預測用戶屬于哪個類別（購買類/非購買類）時如果為預測模型確定一個相對高的階數，而用戶的序列數據不能支持這種階數，也即序列的深度過大出現跳轉概率為0的情況，這時有可能導致多個模型的預測數據都為0的情況，此時就無法對其進行相關性分類判定。針對這種情況，本文提出一個自適應的k階馬爾科夫模型，使得模型可以根據用戶的歷史序列數據的相關性在1階到k階馬爾科夫模型中進行適配，最終使用戶的序列數據與模型的相似性數據能夠達到最大值。即：

其中，Sk=｛si-1，si-2，…，si-k｝表示序列元素si的前k個元素。

自適應分類算法AdaptiveVLMM（S，M）如下：

輸入：序列s，模型M=Build-PST（TrainingData）

輸出：相似度Value Begin

For k in（1，length（s））

Value［k］=P（s'|M）//用戶序列與購買模型M的相似度

Return Max（Value）End

3.3 兩階段過濾策略

用戶的瀏覽網頁的行為習慣會隨時間的變化而不斷的變化，所以用戶的購物行為序列數據的時效性是個不能忽視的問題。例如，在換季的時候，用戶的購物行為可能就有別于以往。本文在自適應的基礎上又采用了兩階段過濾的動態跟蹤用戶行為變化的策略。將每次的推薦結果集按預測正確和預測不正確分類，作為構建下次預測模型的數據源。

根據性質1，2可知，利用第二階段得到的準確與不準確數據集進行下一次預測模型的建模，使得最后篩選出來的新行為序列所代表用戶的購買傾向度要遠遠高于第一階段得到的用戶購買傾向度。

利用兩階段過濾法，在保持足夠明顯的分類特征的同時使得模型的構建時間和后期的序列與模型的相似度計算時間大大減小，提高了算法運行效率。下面給出兩階段算法的詳細介紹及相關流程圖例。

第一階段先將初始序列數據集分為購買類和非購買類兩類，并分別對兩類數據集進行PST建模，形成購買模型M1和非購買模型M2。之后利用公式（1）計算預測數據集中每一條序列記錄同模型M1，M2相似度，并根據公式（3）計算得到θij，選取θij值大于指定閾值δ的數據集作為新的候選推薦數據集S'。第二階段將推薦數據集S'與驗證數據集進行比對驗證得到準確數據集S1'和非準確數據集S2'。然后分別對S1'、S2'進行PST建模得到PM1和PM2。之后將新的待預測數據集同模型PM1和PM2進行相似度計算并得到θij，最后選取θij＞δ的數據集作為最終的推薦數據集。數據訓練、驗證各階段的篩選比對過程如圖2所示。

第一階段過濾算法如下：

輸入：訓練數據集TrainingData，分類標記數據集C，測試數據集S，驗證數據集W，閾值δ

輸出：分類行為序列特征集S1'，S2'

瀏覽行為序列

Compare（Candidate set，W）→S1'，S2'

Return S1'，S2'

End

圖2

圖2 其中訓練數據，分類數據，測試預測數據，驗證數據是按時間先后順序排序

第二階段過濾算法如下：

輸入：第一階段得到的分類行為序列數據集S1'，S2'，待預測數據集S，閾值δ

輸出：推薦數據集Set Begin

Build-PST（S1'）→PM1Build-PST（S2'）→PM2For siin S

AdaptiveVLMM（si，PM1）→Value_1

AdaptiveVLMM（si，PM2）→Value_2

θij=Value_1/Value_2

If θij≥δ：

＜ui，ej＞→Candidate set

Return Candidate set

End

本實驗的主要目標利用“自適應兩階段過濾法”處理12月18日之前的數據，根據得到用戶購買傾向程度值預測12月19日這天用戶購買決定，然后進行相應商品的推薦。

根據以上分析可知，在預測天的前兩天的行為數據轉化率最大。所以本文選用12月19日前兩天（17日～18日）的數據作為待預測數據，選用距離待預測數據前六天 （12月11日～12日數據作為訓練數據集，13日作為分類標記數據集，14～15日數據作為測試數據集，16日作為驗證數據集）的數據來構建模型。

4 實驗結果

本節首先介紹實驗所用數據集以及相關數據的處理，之后在進一步的說要實驗的設置、評價標準以及不同閾值直接的對比結果，最后給出同其他算法的對比實驗結果并對實驗結果進行了相依的分析。

4.1 數據集

本文實驗所采用的數據來自于2015年阿里巴巴的天池大數據平臺的移動推薦算法競賽［13］，該數據主要包含了一定量的用戶在2014年中的一個月時間（11.18～12.18）之內的移動端行為數據。這些行為數據主要的是指用戶對某一商品的“瀏覽，收藏，加入購物車，購買”等操作。總的數據量包含了144321條記錄。本文先將原數據集中的數據格式處理成以＜userid，itemid＞為主鍵的用戶瀏覽行為序列數據集。本文將不連續的數據（即在用戶行為在時間上有間隔的數據）進行插值，用0代表當天的數據瀏覽具有間隔，用5代表間隔了一天沒有瀏覽行為記錄。其數據格式如表1所示：

表1 生成的用戶瀏覽序列數據集

其中user_id表示用戶標識，item_id指商品標識，behavior_type指用戶對商品的行為類型（其中1代表瀏覽，2代表收藏，3代表加入購物車，4代表購買）

同時，基于對樣本數據的分析發現，用戶的行為類型數據所代表的用戶對商品的感興趣程度具有實效性，即用戶的各種行為類型數據轉化為購買行為的轉化率隨時間的推移逐漸遞減。如圖3所示。

圖3 在某一特定天之前的用戶行為轉化為購買的比率

4.2 實驗環境及分析

本節通過實驗來驗證本文提出的基于馬爾可夫模型的自適應兩階段算法的有效性。本文算法的實驗環境為酷睿i3 3.0GHz雙核CPU，4G內存，500G硬盤。操作系統為Windows 10 64位操作系統，代碼全部使用Python編寫并利用了Numpy等相關工具包做數據清洗的相關工作。本文對實驗的評判主要是使用綜合評價指標F1值。

為了有效的評估模型的優劣，本文選取文獻［3］中的邏輯回歸模型和BPR［14］加以比較。其中邏輯回歸是將隱式數據轉換為顯式數據的形式加以分類處理，BPR直接運用隱式數據的概率進行處理。本文算法與這兩種算法的F1值的平均值比較如表2所示，可知本文算法的F1值在總體上優于其他兩類算法：

表2 三種算法的準確率、召回率和F1值的平均值比較

5 結語

本文的提出的“自適應兩階段過濾法”是完全用戶的隱式反饋數據建立的，該方法是利用變長馬爾可夫模型對用戶的購買行為序列進行購買興趣傾向度計算，并依此為依據將那些購買興趣傾向度大于某一設定閾值的＜用戶，商品＞二元作為推薦商品輸出。這種方法避免了人為地對用戶行為進行打分，將隱式數據轉換為顯式數據后進行商品推薦的缺陷，更加準確地反映了用戶行為所代表的用戶的購買意愿。但是，該方法的不足之處，構建變長馬爾可夫模型的空間和時間開銷都非常大。鑒于此，后續的研究考慮利用分布式計算來解決這些問題。

［1］Bobadilla J，Ortega F，Hernando A，et al.Recommender Systems Survey［J］.Knowledge-Based Systems，2013，46（1）：109-132.

［2］Oard D W，Kim J.Implicit Feedback for Recommender System［C］.Massachusetts Institute of Technology，Department of Electrical Engineering and Computer.2010：81--83.

［3］王聰.基于用戶行為的個性化推薦算法研究［D］.哈爾濱工業大學.2015：17-31

［4］Duen-Ren Liu，Chin-Hui Lai，Wang-Jung Lee.A Hybrid of Sequential Rules and Collaborative Filtering for Product Recommendation［J］.Information Sciences，2009，179（20）：3505-3519.

［5］Lerche L，Jannach D.Using graded Implicit Feedback for Bayesian Personalized Ranking［C］.ACM Conference on Recommender Systems.ACM，2014：353-356.

［6］Liu D R，Lai C H，Lee W J.A Hybrid of Sequential Rules and Collaborative Filtering for Product Recommendation［J］.Information Sciences，2009，179（20）：3505-3519.

［7］許昕.基于用戶隱式反饋的個性化資訊推薦系統研究與實現［D］.北京工業大學.2012：22-50

［8］Leonardi F G.A generalization of the PST Algorithm：Modeling the Sparse Nature of Protein Sequences［J］.Bioinformatics，2006，22 （11）：1302-1307.

［9］Ron D，Singer Y，Tishby N.The Power of Amnesia：Learning Probabilistic Automata with Variable Memory Length［J］.Machine Learning，1996，25（2-3）：117-149.

［10］Schulz M H，Weese D，Rausch T，et al.Fast and Adaptive Variable Order Markov Chain Construction［M］.Algorithms in Bioinformatics.Springer Berlin Heidelberg，2008：306-317.

［11］Ukkonen E.Online construction of suffix trees［J］.Algorithmica，1995，14（3）：249-260.

［12］Bhattacharya A，Das S K.LeZi-update：an Information-Theoretic Approach to Track Mobile Users in PCS Networks［C］.Proceedings of the 5th Annual ACM/IEEE International Conference on Mobile Computing and Networking.ACM，1999：1-12.

［13］阿里巴巴天池大數據平臺，https：//tianchi.aliyun.com/competition/information.htm？spm=5176.100067.5678.2.DG4xjr&raceId=1

［14］Rendle，Steffen，Freudenthaler，Christoph，Gantner，Zeno，et al.BPR：Bayesian Personalized Ranking from Implicit Feedback［C］. Conference on Uncertainty in Artificial Intelligence.AUAI Press，2012：452-461.

Analysis of User's Shopping Behavior Based on Variable Length Markov Model

ZHENG Tian-yu，WU Ai-hua
（College of Information Engineering，Shanghai Maritime Univeristy，Shanghai 201306）

User behavior sequence with the continuity features can be a very good response to user's buying habits or the user's shopping p

，and this characteristic in the explicit feedback algorithm is recommended products tend to be ignored.Therefore，according to the user's shopping behavior and implicit feedback information，proposes a model based on variable length Markov“two stage adaptive filtering”recommendation algorithm.The algorithm is mainly using probabilistic suffix tree construction of variable length Markov model，and then uses the model of user behavior sequence data set several times of classification and filtering，to determine the user of the commodity purchase intention，user generated commodity recommendation list.Experiments show that the proposed recommended strategy has good recommendation effect.

User Shopping Behavior；Probabilistic Suffix Tree；Variable Length Markov；Personalized Recommendation

1007-1423（2016）21-0008-07

10.3969/j.issn.1007-1423.2016.21.002

鄭天宇（1989-），男，河南信陽人，碩士研究生，研究方向為數據挖掘、個性化推薦系統

2016-05-04

2016-07-20

吳愛華（1976-），女，上海人，博士，副教授，研究方向數據挖掘、不一致數據庫對比