鄭天宇，吳愛(ài)華

（上海海事大學(xué)信息工程學(xué)院，上海 201306）

基于變長(zhǎng)馬爾科夫模型的用戶(hù)購(gòu)物行為分析

鄭天宇，吳愛(ài)華

（上海海事大學(xué)信息工程學(xué)院，上海 201306）

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

用戶(hù)購(gòu)物行為；概率后綴樹(shù)；變長(zhǎng)馬爾科夫；個(gè)性化推薦

0 引言

在電子商務(wù)領(lǐng)域，以用戶(hù)的瀏覽、收藏、加入購(gòu)物車(chē)和購(gòu)買(mǎi)為主要特征的用戶(hù)購(gòu)物行為是其主要的隱式用戶(hù)反饋［1］信息。隱式反饋信息因?yàn)椴恍枰脩?hù)主動(dòng)地進(jìn)行反饋操作，所以相對(duì)于顯式反饋數(shù)據(jù)［2］，隱式反饋數(shù)據(jù)有著收集成本低，數(shù)據(jù)規(guī)模大等特點(diǎn)。然而在當(dāng)前的個(gè)性化推薦系統(tǒng)的研究中大量的分析挖掘是基于顯式反饋信息，這不僅浪費(fèi)了海量的隱式數(shù)據(jù)資源，也限制了個(gè)性化推薦系統(tǒng)的研究與發(fā)展。因此利用用戶(hù)的購(gòu)物行為等隱式反饋數(shù)據(jù)進(jìn)行個(gè)性化推薦研究具有很高的現(xiàn)實(shí)意義。

在電商領(lǐng)域的用戶(hù)購(gòu)物行為除具有一般的序列數(shù)據(jù)的特點(diǎn)之外，其還有以下特征：

（1）用戶(hù)的行為序列是隨時(shí)間變化的動(dòng)態(tài)變量，并且這種動(dòng)態(tài)變量的發(fā)展總是承前啟后的，當(dāng)前變量的改變不一定馬上在下一步的轉(zhuǎn)移狀態(tài)中體現(xiàn)出來(lái)。未來(lái)的狀態(tài)也不單單與現(xiàn)在的狀態(tài)有關(guān)，其還受到過(guò)去的一個(gè)或者多個(gè)狀態(tài)的影響。即用戶(hù)行為序列數(shù)據(jù)中元素的狀態(tài)轉(zhuǎn)移不具有一階無(wú)后效性。

（2）用戶(hù)行為特征所代表的用戶(hù)購(gòu)買(mǎi)意愿具有時(shí)效性。即以往的行為特征記錄對(duì)用戶(hù)當(dāng)下的購(gòu)買(mǎi)決定的影響隨時(shí)間的推移逐漸減弱。

（3）用戶(hù)行為記錄中各行為特征之間的時(shí)間間隔對(duì)整個(gè)序列來(lái)說(shuō)也是一種重要影響因素。例如序列A＜瀏覽，瀏覽，?，瀏覽，瀏覽，加入購(gòu)物車(chē)＞（其中?代表序列存在的時(shí)間間隔）和序列B＜瀏覽，瀏覽，瀏覽，加入購(gòu)物車(chē)，購(gòu)買(mǎi)＞，如果將A中的時(shí)間間隔去掉，從表面上看A中的瀏覽次數(shù)大于B，即可以認(rèn)為A中數(shù)據(jù)具有的購(gòu)買(mǎi)可能性高于B。然而實(shí)際上A中的用戶(hù)行為對(duì)購(gòu)買(mǎi)行為的出現(xiàn)真正起到直接作用的可能僅僅是間隔之后的一系列行為。

基于以上對(duì)用戶(hù)購(gòu)物行為的分析，本文提出了將基于用戶(hù)購(gòu)物行為數(shù)據(jù)的個(gè)性化推薦研究問(wèn)題轉(zhuǎn)化為基于用戶(hù)購(gòu)物行為序列集的序列分類(lèi)問(wèn)題的思路，即根據(jù)用戶(hù)購(gòu)物行為所代表的用戶(hù)購(gòu)物興趣傾向程度來(lái)判斷用戶(hù)是否會(huì)產(chǎn)生購(gòu)買(mǎi)行為，并據(jù)此將用戶(hù)行為序列分為購(gòu)買(mǎi)類(lèi)和非購(gòu)買(mǎi)類(lèi)兩類(lèi)序列數(shù)據(jù)集?？紤]到用戶(hù)購(gòu)物行為序列無(wú)一階無(wú)后效性和時(shí)效性特點(diǎn)，本文提出了基于變長(zhǎng)馬爾科夫模型的序列分類(lèi)算法，并在此基礎(chǔ)上提出了用戶(hù)購(gòu)買(mǎi)興趣傾向度的概念和計(jì)算方式。本文的主要貢獻(xiàn)有：

（1）利用變長(zhǎng)馬爾可夫模型能夠模擬多個(gè)以往序列元素對(duì)未來(lái)元素的跳轉(zhuǎn)概率的影響來(lái)解決用戶(hù)購(gòu)物行為序列中元素跳轉(zhuǎn)的無(wú)一階無(wú)后效性的問(wèn)題。

（2）改進(jìn)了變長(zhǎng)馬爾可夫模型的相似度計(jì)算方式，提出了自適應(yīng)的相似度計(jì)算方法以解決用戶(hù)的行為序列元素的時(shí)效性要求。

（3）提出兩階段過(guò)濾法，使得每一次的預(yù)測(cè)結(jié)果都可以成為下一次預(yù)測(cè)模型的訓(xùn)練樣本集，能夠達(dá)到動(dòng)態(tài)地跟蹤用戶(hù)行為習(xí)慣的效果，解決了用戶(hù)行為特征數(shù)據(jù)因時(shí)間久遠(yuǎn)而與用戶(hù)當(dāng)前行為習(xí)慣相差太大的問(wèn)題。同時(shí)，也提高了模型構(gòu)建的效率和預(yù)測(cè)的準(zhǔn)確性。

1 相關(guān)工作

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

2 模型及相關(guān)概念的介紹

本節(jié)主要討論用戶(hù)購(gòu)物行為序列數(shù)據(jù)的相關(guān)定義并介紹分析若干的相關(guān)工作。首先說(shuō)明全文中使用到的相關(guān)概念及記號(hào)。

定義1用戶(hù)的購(gòu)買(mǎi)行為特征是指用戶(hù)在購(gòu)物網(wǎng)頁(yè)上的操作標(biāo)識(shí)，如瀏覽、收藏、加入購(gòu)物車(chē)、購(gòu)買(mǎi)等。設(shè)αi為用戶(hù)的一個(gè)行為特征，集合A=｛α1，α2，…，αi｝為用戶(hù)的所有可能的行為特征集.為了解決用戶(hù)行為序列中時(shí)間間隔被忽略的問(wèn)題，特別定義兩個(gè)特殊符號(hào)作為行為序列的間隔符，?代表一條行為序列中的短期間隔（以小時(shí)為單位），$代表一條行為序列的長(zhǎng)期間隔（以天為單位）。則最終的行為集合A=｛α1，α2，…，αi，$｝。

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

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

變長(zhǎng)馬爾可夫模型［8］是一個(gè)平穩(wěn)隨機(jī)過(guò)程｛Xn，n= 0，1，2，…，Xi∈Σ｝，其中Σ為有限狀態(tài)集｛xi｝，模型中的轉(zhuǎn)態(tài)轉(zhuǎn)移概率為：

其中，k是模型的階，有限序列（xn-k，…，xn-1）稱(chēng)為子序列。倘若將用戶(hù)行為序列集對(duì)應(yīng)于狀態(tài)集Σ，則用戶(hù)行為序列也可看成一個(gè)平穩(wěn)的隨機(jī)過(guò)程，相應(yīng)的用變長(zhǎng)馬爾可夫模型表示如下：

將用戶(hù)行為序列依據(jù)其是否產(chǎn)生購(gòu)買(mǎi)將其分為購(gòu)買(mǎi)類(lèi)和非購(gòu)買(mǎi)類(lèi)，利用訓(xùn)練算法為每一個(gè)類(lèi)別訓(xùn)練一個(gè)變長(zhǎng)馬爾可夫模型。然后對(duì)每一個(gè)新的未知序列s'= ｛s1，s2，…，sm｝，計(jì)算s'與每一個(gè)模型的相似度。序列與模型的相似度計(jì)算公式如下：

其中，pi（si）=p（si|si-k，…，si-1）（k＜i＜l，l是序列的長(zhǎng)度，k是馬爾科夫模型的階數(shù)）.當(dāng)i≤k時(shí)，有：

上式中的pi（si）又稱(chēng)為由以往的一段序列狀態(tài)si-k，…，si-1跳轉(zhuǎn)到下一個(gè)序列狀態(tài)si的跳轉(zhuǎn)概率，它的計(jì)算公式如下：

其中，N（si-k），…，si-1，si）表示在分類(lèi)訓(xùn)練模型Mj中序列si-k，…，si-1，si出現(xiàn)的次數(shù)。序列模型Mj由馬爾科夫模型訓(xùn)練得來(lái)，在3.2節(jié)中會(huì)詳細(xì)講解模型的構(gòu)建過(guò)程。

定義3用戶(hù)ui對(duì)商品ej做出購(gòu)買(mǎi)決定的傾向程度θij，是用戶(hù)的行為序列s'=｛s1，s2，…，sm｝與訓(xùn)練集中購(gòu)買(mǎi)行為序列特征類(lèi)M1的相似度和非購(gòu)買(mǎi)行為序列特征類(lèi)M2的相似度的比值。其計(jì)算公式如下：

通常當(dāng)P（s'|M1）＞P（s'|M2）時(shí)，判定序列s'屬于購(gòu)買(mǎi)類(lèi)M1。因此，設(shè)閾值δ（δ≥1），當(dāng)用戶(hù)ui對(duì)商品ej做出購(gòu)買(mǎi)決定的傾向度θij＞δ時(shí)，則由用戶(hù)ui對(duì)商品ej組成的二元＜ui，ej＞作為推薦數(shù)據(jù)集輸出。需要注意的是，當(dāng)θij等于無(wú)窮大時(shí)，將其設(shè)為一個(gè)足夠大的值，一般設(shè)為θij＞1值的均值。

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

性質(zhì)1設(shè)序列a，模型M1和PM1，PM1是M1的子類(lèi)，若序列a相似于PM1，則a一定相似于M1。即若序列a屬于類(lèi)PM1，則其也屬于類(lèi)M1。

性質(zhì)2若PM1是M1的子類(lèi)，子類(lèi)PM1的序列特征要高于M1。

3 變長(zhǎng)馬爾科夫模型的構(gòu)建與算法設(shè)計(jì)

在下面各個(gè)小節(jié)中，將一一介紹基于概率后綴樹(shù)的變長(zhǎng)馬爾可夫模型的構(gòu)建方法，相似度的自適應(yīng)計(jì)算方法以及兩階段模型的實(shí)現(xiàn)過(guò)程。

3.1 概率后綴樹(shù)（PST）的構(gòu)建

在實(shí)現(xiàn)變長(zhǎng)馬爾科夫模型的算法中概率后綴樹(shù)［9］算法要比一般的CA算法計(jì)算復(fù)雜度低，并且其可在線性時(shí)間與空間復(fù)雜度內(nèi)構(gòu)建［10］。因此本文采用概率后綴樹(shù)算法來(lái)構(gòu)建變長(zhǎng)馬爾科夫模型。本節(jié)主要是簡(jiǎn)要介紹一下概率后綴樹(shù)的結(jié)構(gòu)，并給出變長(zhǎng)馬爾可夫模型的概率后綴樹(shù)構(gòu)造過(guò)程。

概率后綴樹(shù)（PST）模型是基于后綴樹(shù)建立起來(lái)的，該模型樹(shù)是一棵非空樹(shù)。樹(shù)中每一個(gè)PST節(jié)點(diǎn)都代表一個(gè)行為序列元素，并且每個(gè)節(jié)點(diǎn)都包含一個(gè)|A|維概率分布向量（|A|是指用戶(hù)行為特征集的個(gè)數(shù)）。并且樹(shù)中的每個(gè)節(jié)點(diǎn)的出度在0到|A|之間，每條邊代表A中的一個(gè)符號(hào)標(biāo)記，每個(gè)節(jié)點(diǎn)的邊無(wú)重復(fù)標(biāo)記出現(xiàn)，每個(gè)節(jié)點(diǎn)序列是由根節(jié)點(diǎn)到該節(jié)點(diǎn)所經(jīng)過(guò)的邊的標(biāo)記構(gòu)成。根節(jié)點(diǎn)的概率向量是A集合中每個(gè)行為事件的無(wú)條件概率。其他節(jié)點(diǎn)的概率分布向量是該序列節(jié)點(diǎn)的下一個(gè)行為事件出現(xiàn)的條件概率組成。例如，有序列s，它的下一個(gè)事件α出現(xiàn)的概率為p（α|s）。p（α|s）等于序列｛s，α｝出現(xiàn)的次數(shù)/序列s出現(xiàn)的次數(shù)。

如圖1所示一個(gè)序列s=accactact

圖1

圖2 樹(shù)中的每條邊代表一個(gè)字符如a，c，t，每個(gè)節(jié)點(diǎn)存儲(chǔ)著有這個(gè)節(jié)點(diǎn)跳轉(zhuǎn)到下一個(gè)節(jié)點(diǎn)的條件概率向量，如［1/3，4/9，2/9］，［0，1/3，2/3］。如由行為特征序列a跳轉(zhuǎn)到狀態(tài)c的概率為P（c|a）=1，由行為特征序列ac跳轉(zhuǎn)到狀態(tài)c的概率為P（c|ac）=1/3。

本文的PST的構(gòu)造算法是基于Ukkonen法［11］構(gòu)建的，則本文的PST樹(shù)的構(gòu)建偽代碼介紹如下：

算法：Build-PST（S）：

輸入：訓(xùn)練數(shù)據(jù)集S，事件集合A

輸出：PST樹(shù)

Begin

初始化PST，根節(jié)點(diǎn)的概率向量值為每個(gè)符號(hào)在所有的符號(hào)序列中出現(xiàn)的相對(duì)頻率。

當(dāng)S≠?，取s∈S并從S中刪除s：利用Ukkonen方法將序列s中元素加入樹(shù)中

If?σ∈A：

計(jì)算p（σ|s）→proArray End

3.2 自適應(yīng)分類(lèi)部分

在變長(zhǎng)馬爾科夫模型中，高階馬爾科夫增強(qiáng)馬爾科夫模型的分類(lèi)預(yù)測(cè)能力，然而同時(shí)其也面臨究竟多少階的馬爾科夫模型合適的問(wèn)題。文獻(xiàn)［12］認(rèn)為高階模型可以減少預(yù)測(cè)的不確定性，但階數(shù)的高低有一個(gè)改善的極限，而這個(gè)極限可以通過(guò)歷史數(shù)據(jù)的最大相關(guān)性獲得。在預(yù)測(cè)用戶(hù)屬于哪個(gè)類(lèi)別（購(gòu)買(mǎi)類(lèi)/非購(gòu)買(mǎi)類(lèi)）時(shí)如果為預(yù)測(cè)模型確定一個(gè)相對(duì)高的階數(shù)，而用戶(hù)的序列數(shù)據(jù)不能支持這種階數(shù)，也即序列的深度過(guò)大出現(xiàn)跳轉(zhuǎn)概率為0的情況，這時(shí)有可能導(dǎo)致多個(gè)模型的預(yù)測(cè)數(shù)據(jù)都為0的情況，此時(shí)就無(wú)法對(duì)其進(jìn)行相關(guān)性分類(lèi)判定。針對(duì)這種情況，本文提出一個(gè)自適應(yīng)的k階馬爾科夫模型，使得模型可以根據(jù)用戶(hù)的歷史序列數(shù)據(jù)的相關(guān)性在1階到k階馬爾科夫模型中進(jìn)行適配，最終使用戶(hù)的序列數(shù)據(jù)與模型的相似性數(shù)據(jù)能夠達(dá)到最大值。即：

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

自適應(yīng)分類(lèi)算法AdaptiveVLMM（S，M）如下：

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

輸出：相似度Value Begin

For k in（1，length（s））

Value［k］=P（s'|M）//用戶(hù)序列與購(gòu)買(mǎi)模型M的相似度

Return Max（Value）End

3.3 兩階段過(guò)濾策略

用戶(hù)的瀏覽網(wǎng)頁(yè)的行為習(xí)慣會(huì)隨時(shí)間的變化而不斷的變化，所以用戶(hù)的購(gòu)物行為序列數(shù)據(jù)的時(shí)效性是個(gè)不能忽視的問(wèn)題。例如，在換季的時(shí)候，用戶(hù)的購(gòu)物行為可能就有別于以往。本文在自適應(yīng)的基礎(chǔ)上又采用了兩階段過(guò)濾的動(dòng)態(tài)跟蹤用戶(hù)行為變化的策略。將每次的推薦結(jié)果集按預(yù)測(cè)正確和預(yù)測(cè)不正確分類(lèi)，作為構(gòu)建下次預(yù)測(cè)模型的數(shù)據(jù)源。

根據(jù)性質(zhì)1，2可知，利用第二階段得到的準(zhǔn)確與不準(zhǔn)確數(shù)據(jù)集進(jìn)行下一次預(yù)測(cè)模型的建模，使得最后篩選出來(lái)的新行為序列所代表用戶(hù)的購(gòu)買(mǎi)傾向度要遠(yuǎn)遠(yuǎn)高于第一階段得到的用戶(hù)購(gòu)買(mǎi)傾向度。

利用兩階段過(guò)濾法，在保持足夠明顯的分類(lèi)特征的同時(shí)使得模型的構(gòu)建時(shí)間和后期的序列與模型的相似度計(jì)算時(shí)間大大減小，提高了算法運(yùn)行效率。下面給出兩階段算法的詳細(xì)介紹及相關(guān)流程圖例。

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

第一階段過(guò)濾算法如下：

輸入：訓(xùn)練數(shù)據(jù)集TrainingData，分類(lèi)標(biāo)記數(shù)據(jù)集C，測(cè)試數(shù)據(jù)集S，驗(yàn)證數(shù)據(jù)集W，閾值δ

輸出：分類(lèi)行為序列特征集S1'，S2'

瀏覽行為序列

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

Return S1'，S2'

End

圖2

圖2 其中訓(xùn)練數(shù)據(jù)，分類(lèi)數(shù)據(jù)，測(cè)試預(yù)測(cè)數(shù)據(jù)，驗(yàn)證數(shù)據(jù)是按時(shí)間先后順序排序

第二階段過(guò)濾算法如下：

輸入：第一階段得到的分類(lèi)行為序列數(shù)據(jù)集S1'，S2'，待預(yù)測(cè)數(shù)據(jù)集S，閾值δ

輸出：推薦數(shù)據(jù)集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

本實(shí)驗(yàn)的主要目標(biāo)利用“自適應(yīng)兩階段過(guò)濾法”處理12月18日之前的數(shù)據(jù)，根據(jù)得到用戶(hù)購(gòu)買(mǎi)傾向程度值預(yù)測(cè)12月19日這天用戶(hù)購(gòu)買(mǎi)決定，然后進(jìn)行相應(yīng)商品的推薦。

根據(jù)以上分析可知，在預(yù)測(cè)天的前兩天的行為數(shù)據(jù)轉(zhuǎn)化率最大。所以本文選用12月19日前兩天（17日～18日）的數(shù)據(jù)作為待預(yù)測(cè)數(shù)據(jù)，選用距離待預(yù)測(cè)數(shù)據(jù)前六天 （12月11日～12日數(shù)據(jù)作為訓(xùn)練數(shù)據(jù)集，13日作為分類(lèi)標(biāo)記數(shù)據(jù)集，14～15日數(shù)據(jù)作為測(cè)試數(shù)據(jù)集，16日作為驗(yàn)證數(shù)據(jù)集）的數(shù)據(jù)來(lái)構(gòu)建模型。

4 實(shí)驗(yàn)結(jié)果

本節(jié)首先介紹實(shí)驗(yàn)所用數(shù)據(jù)集以及相關(guān)數(shù)據(jù)的處理，之后在進(jìn)一步的說(shuō)要實(shí)驗(yàn)的設(shè)置、評(píng)價(jià)標(biāo)準(zhǔn)以及不同閾值直接的對(duì)比結(jié)果，最后給出同其他算法的對(duì)比實(shí)驗(yàn)結(jié)果并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行了相依的分析。

4.1 數(shù)據(jù)集

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

表1 生成的用戶(hù)瀏覽序列數(shù)據(jù)集

其中user_id表示用戶(hù)標(biāo)識(shí)，item_id指商品標(biāo)識(shí)，behavior_type指用戶(hù)對(duì)商品的行為類(lèi)型（其中1代表瀏覽，2代表收藏，3代表加入購(gòu)物車(chē)，4代表購(gòu)買(mǎi)）

同時(shí)，基于對(duì)樣本數(shù)據(jù)的分析發(fā)現(xiàn)，用戶(hù)的行為類(lèi)型數(shù)據(jù)所代表的用戶(hù)對(duì)商品的感興趣程度具有實(shí)效性，即用戶(hù)的各種行為類(lèi)型數(shù)據(jù)轉(zhuǎn)化為購(gòu)買(mǎi)行為的轉(zhuǎn)化率隨時(shí)間的推移逐漸遞減。如圖3所示。

圖3 在某一特定天之前的用戶(hù)行為轉(zhuǎn)化為購(gòu)買(mǎi)的比率

4.2 實(shí)驗(yàn)環(huán)境及分析

本節(jié)通過(guò)實(shí)驗(yàn)來(lái)驗(yàn)證本文提出的基于馬爾可夫模型的自適應(yīng)兩階段算法的有效性。本文算法的實(shí)驗(yàn)環(huán)境為酷睿i3 3.0GHz雙核CPU，4G內(nèi)存，500G硬盤(pán)。操作系統(tǒng)為Windows 10 64位操作系統(tǒng)，代碼全部使用Python編寫(xiě)并利用了Numpy等相關(guān)工具包做數(shù)據(jù)清洗的相關(guān)工作。本文對(duì)實(shí)驗(yàn)的評(píng)判主要是使用綜合評(píng)價(jià)指標(biāo)F1值。

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

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

5 結(jié)語(yǔ)

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

［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］王聰.基于用戶(hù)行為的個(gè)性化推薦算法研究［D］.哈爾濱工業(yè)大學(xué).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］許昕.基于用戶(hù)隱式反饋的個(gè)性化資訊推薦系統(tǒng)研究與實(shí)現(xiàn)［D］.北京工業(yè)大學(xué).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］阿里巴巴天池大數(shù)據(jù)平臺(tái)，https：//tianchi.aliyun.com/competition/information.htm？spm=5176.100067.5678.2.DG4xjr&raceId=1

［14］Rendle，Steffen，F(xiàn)reudenthaler，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-），男，河南信陽(yáng)人，碩士研究生，研究方向?yàn)閿?shù)據(jù)挖掘、個(gè)性化推薦系統(tǒng)

2016-05-04

2016-07-20

吳愛(ài)華（1976-），女，上海人，博士，副教授，研究方向數(shù)據(jù)挖掘、不一致數(shù)據(jù)庫(kù)對(duì)比