朱志國(guó)

（1.東北財(cái)經(jīng)大學(xué)管理科學(xué)與工程學(xué)院，遼寧大連 116023；2.大連理工大學(xué)系統(tǒng)工程研究所，遼寧大連 116024）

基于隱馬爾可夫鏈模型的電子商務(wù)用戶興趣導(dǎo)航模式發(fā)現(xiàn)

朱志國(guó)1，2

（1.東北財(cái)經(jīng)大學(xué)管理科學(xué)與工程學(xué)院，遼寧大連 116023；2.大連理工大學(xué)系統(tǒng)工程研究所，遼寧大連 116024）

用戶智能導(dǎo)航模式發(fā)現(xiàn)已經(jīng)成為電子商務(wù)領(lǐng)域中的一個(gè)研究熱點(diǎn)。為此，結(jié)合電子商務(wù)站點(diǎn)用戶網(wǎng)頁(yè)訪問(wèn)時(shí)間與網(wǎng)頁(yè)關(guān)鍵字信息對(duì)用戶訪問(wèn)興趣進(jìn)行定義，借鑒經(jīng)典隱馬爾可夫鏈模型，建立用戶興趣導(dǎo)航模型。給出在此模型中用戶興趣導(dǎo)航路徑的發(fā)現(xiàn)方法及算法描述。通過(guò)模擬數(shù)據(jù)、某B2C在線圖書銷售站點(diǎn)中的真實(shí)數(shù)據(jù)以及與經(jīng)典方法的對(duì)比等方面的實(shí)驗(yàn)驗(yàn)證，結(jié)果表明：給出的模型方法能夠準(zhǔn)確、高效地找到帶有用戶訪問(wèn)興趣的關(guān)聯(lián)路徑信息。這個(gè)方法可以作為一種應(yīng)用于電子商務(wù)領(lǐng)域更為有效、實(shí)用的智能導(dǎo)航發(fā)現(xiàn)工具。

智能電子商務(wù)；隱馬爾可夫模型；Web數(shù)據(jù)挖掘；興趣導(dǎo)航模式

1 引言

基于互聯(lián)網(wǎng)的電子商務(wù)極大地緩解了信息不對(duì)稱等信息約束對(duì)傳統(tǒng)商務(wù)活動(dòng)的制約，這種前所未有的變化為經(jīng)濟(jì)行為最優(yōu)化和資源配置高效率提供了難得的機(jī)遇［1-2］。但是隨著電子商務(wù)廣泛普及發(fā)展與深入發(fā)展，存儲(chǔ)于電子商務(wù)站點(diǎn)服務(wù)器、代理服務(wù)器以及客戶機(jī)程序插件等多源渠道中的商品信息、交易數(shù)據(jù)、瀏覽記錄信息日益海量化［3］。以往電子商務(wù)企業(yè)所采用的“One-Size-Fits-All”的簡(jiǎn)單粗放服務(wù)［4］，已經(jīng)越來(lái)越無(wú)法滿足用戶個(gè)性化的需求、偏好及行為特點(diǎn)，導(dǎo)致用戶無(wú)法準(zhǔn)確、高效率地搜尋到感興趣的相關(guān)商品、服務(wù)信息；同時(shí)電子商務(wù)企業(yè)也很難根據(jù)用戶的訪問(wèn)行為，動(dòng)態(tài)優(yōu)化網(wǎng)站頁(yè)面結(jié)構(gòu)，以便更加智能快速地響應(yīng)用戶的需求［5］。因此，依據(jù)用戶興趣的智能導(dǎo)航模式發(fā)現(xiàn)已經(jīng)成為電子商務(wù)學(xué)界、業(yè)界中的一個(gè)熱點(diǎn)問(wèn)題。

國(guó)內(nèi)外對(duì)于網(wǎng)絡(luò)用戶導(dǎo)航模式發(fā)現(xiàn)的經(jīng)典研究成果主要有：＂Footprints＂［6］的思想是：訪問(wèn)者在訪問(wèn)一個(gè)Web站點(diǎn)時(shí)，會(huì)留下“足跡”（Footprints）。經(jīng)過(guò)一段時(shí)間，最頻繁訪問(wèn)的區(qū)域會(huì)形成路徑，于是新的訪問(wèn)者會(huì)依據(jù)這些路徑進(jìn)行訪問(wèn)。WUM［7］則是對(duì)“Footprints＂方法的一種補(bǔ)充，其定義了G-Sequences用于挖掘用戶導(dǎo)航模式，并給出了一種挖掘語(yǔ)言MINT。Kuo等人［8］強(qiáng)調(diào)用戶的瀏覽行為，采用K-means算法并結(jié)合用戶訪問(wèn)時(shí)間和訪問(wèn)次數(shù)來(lái)調(diào)整用戶的興趣度，從而使得發(fā)現(xiàn)的瀏覽路徑模式更具個(gè)性化。王有為等［9］將用戶的瀏覽歷史抽象為帶有時(shí)間順序信息的訪問(wèn)序列，并使用聚類方法進(jìn)行用戶導(dǎo)航模式發(fā)現(xiàn)。馬溪駿等［10］建立了一個(gè)Web站點(diǎn)模型，然后基于蟻群算法和Web日志數(shù)據(jù)給出了一種用戶導(dǎo)航模型發(fā)現(xiàn)方法。Sarukkai等［11］基于傳統(tǒng)馬爾可夫模型對(duì)Web站點(diǎn)中鏈接結(jié)構(gòu)與訪問(wèn)路徑預(yù)測(cè)進(jìn)行建模與實(shí)驗(yàn)分析。Borges等［12］用N階馬爾可夫模型來(lái)改進(jìn)Web緩存的預(yù)取性能。Wang Youwei等［13］基于推薦系統(tǒng)構(gòu)建瀏覽樹圖來(lái)幫助網(wǎng)絡(luò)用戶導(dǎo)航。

總結(jié)起來(lái)，上述這些方法大都沒(méi)有深入考慮到用戶對(duì)于站點(diǎn)的訪問(wèn)其實(shí)是對(duì)每個(gè)頁(yè)面節(jié)點(diǎn)內(nèi)部的某一主題信息感興趣，因此挖掘的粒度相對(duì)較粗；此外現(xiàn)有成果也大都沒(méi)有洞察到用戶在每個(gè)頁(yè)面節(jié)點(diǎn)的訪問(wèn)時(shí)間所能反映出的用戶對(duì)于內(nèi)容興趣程度大小特性，只是根據(jù)用戶的瀏覽序列進(jìn)行了挖掘研究工作。

在本文的研究中，我們認(rèn)為當(dāng)用戶對(duì)一個(gè)電子商務(wù)站點(diǎn)進(jìn)行訪問(wèn)時(shí)，一定是對(duì)某些商品主題產(chǎn)生了興趣。為此，我們結(jié)合電子商務(wù)站點(diǎn)中用戶網(wǎng)頁(yè)訪問(wèn)時(shí)間與網(wǎng)頁(yè)關(guān)鍵字信息對(duì)用戶訪問(wèn)興趣進(jìn)行定義，借鑒經(jīng)典隱馬爾可夫鏈模型，建立用戶興趣導(dǎo)航模型。本文研究成果將為電子商務(wù)經(jīng)營(yíng)方開展站點(diǎn)結(jié)構(gòu)設(shè)計(jì)改進(jìn)、智能網(wǎng)站廣告營(yíng)銷等實(shí)踐工作提供理論與方法支持。

2 網(wǎng)頁(yè)關(guān)鍵字的提取

電子商務(wù)站點(diǎn)中一個(gè)頁(yè)面往往含有多個(gè)關(guān)鍵字信息，這些信息可以對(duì)一個(gè)頁(yè)面內(nèi)容進(jìn)行簡(jiǎn)要概括和描述。當(dāng)用戶訪問(wèn)一個(gè)電子商務(wù)站點(diǎn)時(shí)，其興趣偏好恰好可以利用所訪問(wèn)的頁(yè)面中所具有的關(guān)鍵字集合來(lái)表征。下面首先給出一個(gè)網(wǎng)頁(yè)中關(guān)鍵字信息提取的有效方法。

2.1 網(wǎng)站服務(wù)器日志預(yù)處理

電子商務(wù)網(wǎng)站服務(wù)器中存儲(chǔ)的日志文件記錄了每個(gè)用戶訪問(wèn)請(qǐng)求的如下一些屬性：訪問(wèn)時(shí)間、用戶IP地址、訪問(wèn)資源的文件名或腳本。在一段時(shí)間內(nèi)用戶連續(xù)提交的請(qǐng)求序列定義為用戶會(huì)話。通過(guò)預(yù)處理，可以將這些日志文件整理成服務(wù)器會(huì)話集。預(yù)處理步驟為：

（1）首先，剔除訪問(wèn)多媒體文件、腳本文件的用戶請(qǐng)求；

（2）按用戶的IP地址，將日志文件分割成獨(dú)立的訪問(wèn)記錄集；

（3）將每個(gè)訪問(wèn)記錄集的請(qǐng)求按時(shí)間排序，設(shè)立時(shí)間窗口閥值tw，分割訪問(wèn)記錄集，時(shí)間間隔小于tw的相鄰訪問(wèn)請(qǐng)求同屬于一個(gè)用戶會(huì)話，這時(shí)，每一個(gè)用戶的每一次訪問(wèn)會(huì)話就構(gòu)成了一個(gè)訪問(wèn)事務(wù)。

2.2 頁(yè)面中關(guān)鍵字集合的提取

一個(gè)電子商務(wù)站點(diǎn)中的網(wǎng)頁(yè)關(guān)鍵字集合可以通過(guò)下面兩個(gè)過(guò)程提取出來(lái)：

（1）為了高效率地對(duì)網(wǎng)頁(yè)關(guān)鍵字集合進(jìn)行抽取工作，首先要對(duì)網(wǎng)頁(yè)進(jìn)行一些預(yù)處理，例如清除掉HTML、XML或SGML等標(biāo)簽；過(guò)濾掉網(wǎng)頁(yè)中所有類似于逗號(hào)、句號(hào)、引號(hào)這樣的標(biāo)點(diǎn)符號(hào)；刪除掉所有的空行；分詞處理；剔除停用詞等步驟。網(wǎng)頁(yè)p在經(jīng)過(guò)清理之后，就可以用一個(gè)特征詞集T=｛t1，t2，..，tm｝來(lái)表示，其中ti表示網(wǎng)頁(yè)中的一個(gè)特征詞，m表示特征詞的數(shù)量。

（2）需要指出的是，網(wǎng)頁(yè)中的特征詞并不一定在頁(yè)面內(nèi)容中有很高的出現(xiàn)頻率，但是它們一定是常常出現(xiàn)在網(wǎng)頁(yè)的一些重要標(biāo)簽中，例如title，anchor，text，url等等。因此可以對(duì)一個(gè)特征詞ti的頻率用式（1）來(lái)進(jìn)行計(jì)算：

其中，A1，A2，A3和A4表示調(diào)整系數(shù)。在此基礎(chǔ)上，可以給出在一個(gè)網(wǎng)頁(yè)中，特征詞的權(quán)重wp（ti）計(jì)算公式，如式（2）所示：

式中，tfmax是特征詞出現(xiàn)的最大頻率值?？梢岳斫?，權(quán)重值越大的特征詞反映所在Web網(wǎng)頁(yè)主題概念的能力越強(qiáng)。最終根據(jù)給定的閾值，選取權(quán)重值超過(guò)閾值的一部分特征詞來(lái)組成網(wǎng)頁(yè)的關(guān)鍵字集合K=｛k1，k2，…，kn｝，K?T。那么一個(gè)網(wǎng)頁(yè)p最終可以簡(jiǎn)單地用式（3）的關(guān)鍵字集合來(lái)表征：

3 用戶訪問(wèn)興趣的相關(guān)定義

Web設(shè)計(jì)者一般會(huì)遵循一個(gè)站點(diǎn)的關(guān)鍵字分布模型進(jìn)行設(shè)計(jì)。下面給出一個(gè)Web站點(diǎn)的關(guān)鍵字分布模型定義如下。

Web站點(diǎn)的關(guān)鍵字模型可以定義為：G=（W，E，K），G為一個(gè)有向圖，如圖1所示，其中W 為Web頁(yè)面集合，E為頁(yè)面之間的超鏈接集合，K為每個(gè)頁(yè)面的關(guān)鍵字集的集合。其中每個(gè)頁(yè)面可以放置不同的關(guān)鍵字，一個(gè)關(guān)鍵字也可以分布在不同的頁(yè)面之中。

為了表征用戶在一個(gè)電子商務(wù)站點(diǎn)中的訪問(wèn)興趣，給出如下定義：

（1）一個(gè)用戶u的訪問(wèn)事務(wù)Tu可以定義為其所訪問(wèn)的所有頁(yè)面組成的集合，如式（4）所示：

其中，pi表示訪問(wèn)的第i個(gè)頁(yè)面，m表示訪問(wèn)的頁(yè)面數(shù)量。

（2）如式（4）所示，一個(gè)網(wǎng)頁(yè)p可以簡(jiǎn)單地用一個(gè)關(guān)鍵字集合K來(lái)表示。這樣一個(gè)用戶u的訪問(wèn)關(guān)鍵字事務(wù)Tku又可以用式（5）來(lái)表示。

其中Ki表示根據(jù)2.2所給出的方法，從頁(yè)面pi提取出的關(guān)鍵字集合。

圖1 Web站點(diǎn)的關(guān)鍵字模型示例

（3）設(shè)pe是在Tu中訪問(wèn)的第e個(gè)頁(yè)面。一個(gè)用戶通過(guò)pe頁(yè)面的訪問(wèn)事務(wù)Tu（pe）的定義如式（6）所示：

（4）根據(jù)式（5），Tu（pe）又可以轉(zhuǎn)變?yōu)橐粋€(gè)通過(guò)pe的用戶u的訪問(wèn)關(guān)鍵字事務(wù)Tku（pe），定義如式（7）所示：

（5）對(duì)這個(gè)用戶而言，如果他對(duì)某個(gè)主題感興趣，那么他會(huì)訪問(wèn)具有該主題的頁(yè)面，并且他會(huì)花費(fèi)較長(zhǎng)時(shí)間在這個(gè)頁(yè)面上。下面用lengthu（pe，ki）來(lái)表示一個(gè)通過(guò)pe的用戶u訪問(wèn)關(guān)鍵字的時(shí)長(zhǎng)。設(shè)用戶u對(duì)一個(gè)頁(yè)面pe的時(shí)長(zhǎng)為lengthu（pe），如果該頁(yè)面具有f個(gè)關(guān)鍵字k1，k2，…kf，那么這個(gè)用戶在pe頁(yè)面上對(duì)關(guān)鍵字ki的訪問(wèn)時(shí)長(zhǎng)定義如式（8）所示：

在此基礎(chǔ)上，用戶訪問(wèn)關(guān)鍵字事務(wù)tku中，一個(gè)通過(guò)pe的用戶對(duì)關(guān)鍵字kj的訪問(wèn)總時(shí)長(zhǎng)sumu（pe，kj）可以用式（9）來(lái)定義：

4 用戶興趣導(dǎo)航路徑模型

本文結(jié)合電子商務(wù)用戶的瀏覽特性以及用戶訪問(wèn)興趣的定義，基于經(jīng)典隱馬爾可夫模型建立一個(gè)用戶興趣導(dǎo)航路徑模型INPM（Interest Navigational Path Model）。下面首先簡(jiǎn)單描述一下模型原型。

4.1 一階隱馬爾可夫鏈模型原型

隱馬爾可夫模型（Hidden Markov Model，HMM）［14］作為一種統(tǒng)計(jì)分析模型，現(xiàn)已成功地用于語(yǔ)音識(shí)別，行為識(shí)別，文字識(shí)別以及故障診斷等領(lǐng)域。高階隱馬爾可夫模型的狀態(tài)數(shù)隨著模型序數(shù)呈指數(shù)增長(zhǎng)，狀態(tài)急劇增長(zhǎng)使得模型中的狀態(tài)—空間復(fù)雜性計(jì)算復(fù)雜性過(guò)高，并且高階隱馬爾可夫模型在進(jìn)行預(yù)測(cè)時(shí)常常會(huì)出現(xiàn)匹配的序列過(guò)少，導(dǎo)致較低的預(yù)測(cè)覆蓋率等問(wèn)題［12］。因此，本文借鑒離散化輸出的一階隱馬爾可夫模型來(lái)解決用戶訪問(wèn)頁(yè)面序列預(yù)測(cè)問(wèn)題，也就是計(jì)算用戶訪問(wèn)的前一個(gè)頁(yè)面到當(dāng)前頁(yè)面的轉(zhuǎn)移概率。一階隱馬爾可夫模型的原型具體描述如下：

（1）一個(gè)狀態(tài)集合Q。具有指定的初始狀態(tài)qs和最終狀態(tài)qf。

（2）一個(gè)狀態(tài)轉(zhuǎn)移集，每個(gè)元素為（q→q′）。

（3）一個(gè)離散的輸出符號(hào)集：∑ =σ1，σ2...σm。

從初始狀態(tài)開始，轉(zhuǎn)移到一個(gè)新的狀態(tài)，觀測(cè)到一個(gè)輸出符號(hào)。如此反復(fù)，直到最終狀態(tài)，于是就產(chǎn)生一個(gè)符號(hào)串：X=x1，x2，...，xl。每一個(gè)轉(zhuǎn)移存在著一個(gè)轉(zhuǎn)移概率P（q→q′）。在一個(gè)狀態(tài)觀測(cè)到一個(gè)特殊符號(hào)的概率為P（X|q）。那么一個(gè)隱馬爾可夫模型M上，符號(hào)串X被觀測(cè)的概率為在所有可能路徑上求概率和，如式（10）所示：

這里q0和ql為初始狀態(tài)qs和最終狀態(tài)qf，xl+1為終止符號(hào)。

建立HMM的一個(gè)普遍目的是找到一個(gè)狀態(tài)序列V（X|M），使其具有觀察序列的最大概率：

4.2 INPM模型的建立

INPM是一個(gè)基于離散化的一階隱馬爾可夫鏈模型，可以應(yīng)用于電子商務(wù)站點(diǎn)預(yù)測(cè)用戶訪問(wèn)頁(yè)面序列的模型，其具體定義如下：

（1）設(shè)站點(diǎn)中的每一個(gè)頁(yè)面為HMM狀態(tài)集合Q中相應(yīng)的節(jié)點(diǎn)q。給定一個(gè)虛擬的初始狀態(tài)qstart和一個(gè)虛擬的終止?fàn)顟B(tài)qend。所有的用戶都是從初始狀態(tài)開始訪問(wèn)，訪問(wèn)結(jié)束后到達(dá)終止?fàn)顟B(tài)。

（2）設(shè)站點(diǎn)中存在一個(gè)全體關(guān)鍵字集合Σ=｛k1，k2，…kM｝。

（3）兩個(gè)節(jié)點(diǎn)q和q′之間存在一個(gè)轉(zhuǎn)移概率P1（q→q′），其定義如式（12）所示：

其中q→q′表示頁(yè)面節(jié)點(diǎn)q和頁(yè)面節(jié)點(diǎn)q′之間有直接的鏈接存在，count（q→q′）是用戶在訪問(wèn)站點(diǎn)的過(guò)程中，在事務(wù)集T中q和q′同時(shí)出現(xiàn)且q′緊隨q的事務(wù)個(gè)數(shù)。count（q）是在事務(wù)集T中含有q的事務(wù)個(gè)數(shù)。

（4）在每一個(gè)節(jié)點(diǎn)q′上，用戶對(duì)關(guān)鍵字集合Σ的興趣都存在一個(gè)概率分布P2（ki|q′），如式（13）所示，這也就是標(biāo)準(zhǔn)HMM中狀態(tài)節(jié)點(diǎn)的觀測(cè)概率，在此稱為興趣概率：

另外，用戶通過(guò)q′對(duì)關(guān)鍵字集Σ的興趣概率還滿足如下約束，如式（14）所示：

4.3 INPM模型中用戶興趣導(dǎo)航路徑模式發(fā)現(xiàn)

在INPM模型中，我們借鑒HMM模型中對(duì)于某一觀測(cè)值（興趣關(guān)鍵字k）序列概率值的算法，如（10）所示?；诖耍覀兘o出電子商務(wù)用戶的興趣導(dǎo)航路徑發(fā)現(xiàn)計(jì)算方法，具體定義如下：

在INPM模型上，已知一個(gè)用戶的訪問(wèn)序列Sl（l表示訪問(wèn)序列的長(zhǎng)度）和用戶訪問(wèn)興趣—關(guān)鍵字k，那么興趣關(guān)聯(lián)模式R（k|Sl）可以定義為式（15）：

如果R（k|Sl）≥C（C為一個(gè)給定的可信度閾值）。那么則可以判定R（k|Sl）為一條符合興趣導(dǎo)航模式的路徑信息。

發(fā)現(xiàn)的興趣導(dǎo)航路徑信息反映了群體用戶對(duì)一個(gè)網(wǎng)站關(guān)鍵字集合或是某個(gè)關(guān)鍵字感興趣的頁(yè)面間的轉(zhuǎn)移關(guān)系。下面給出興趣導(dǎo)航模式R（k|Sl）的發(fā)現(xiàn)算法描述。

5 實(shí)驗(yàn)驗(yàn)證和討論

我們對(duì)提出的電子商務(wù)用戶群導(dǎo)航模型INPM開展了三方面實(shí)驗(yàn)工作：在模擬數(shù)據(jù)上的興趣導(dǎo)航路徑模式R（k|Sl）發(fā)現(xiàn)；針對(duì)某B2C電子商務(wù)網(wǎng)站環(huán)境中真實(shí)用戶的訪問(wèn)序列數(shù)據(jù)進(jìn)行興趣導(dǎo)航模式的發(fā)現(xiàn)實(shí)驗(yàn)，并且給出了一些實(shí)際結(jié)果；最后對(duì)算法進(jìn)行了時(shí)間復(fù)雜性與比較實(shí)驗(yàn)分析。

5.1 模擬數(shù)據(jù)實(shí)驗(yàn)

圖2 站點(diǎn)示例

給定一個(gè)簡(jiǎn)單的站點(diǎn)結(jié)構(gòu)圖，如圖2所示。圖中Ni表示當(dāng)前站點(diǎn)中的頁(yè)面。頁(yè)面上方的大寫字母表示從該頁(yè)面中提取出的關(guān)鍵字集合。例如，N1頁(yè)面上提取出四個(gè)關(guān)鍵字A，B，C，D。頁(yè)面之間有向線段上的數(shù)字表示頁(yè)面間的轉(zhuǎn)移概率。

假設(shè)在這個(gè)站點(diǎn)中，有四個(gè)用戶進(jìn)行訪問(wèn)。每個(gè)用戶訪問(wèn)的頁(yè)面以及在頁(yè)面上的停留時(shí)間信息如表1所示。

表1 用戶對(duì)該站點(diǎn)的訪問(wèn)情況（時(shí)間以秒為單位）

根據(jù)表1中站點(diǎn)上每個(gè)用戶的訪問(wèn)情況以及圖2中每個(gè)頁(yè)面上的關(guān)鍵字分布情況。利用本文給出的式（13），可以計(jì)算出站點(diǎn)內(nèi)的每一個(gè)頁(yè)面相對(duì)于每個(gè)關(guān)鍵字的興趣概率，結(jié)果如表2所示。

表2 每一個(gè)頁(yè)面相對(duì)于每個(gè)關(guān)鍵字的興趣概率

以關(guān)鍵字B為例，在圖2所示的站點(diǎn)中，可以得到對(duì)關(guān)鍵字B感興趣的四條訪問(wèn)路徑：｛（N1→N2）；（N1→N3）；（N1→N2→N4）；（N1→N3→N4）｝。根據(jù)本文所提出的興趣關(guān)聯(lián)模式發(fā)現(xiàn)方法R（k| Sl），設(shè)定可信度閾值為0.01，計(jì)算結(jié)果如表3所示。表3中S的上標(biāo)表示導(dǎo)航路徑中的所經(jīng)歷的頁(yè)面節(jié)點(diǎn)個(gè)數(shù)；下標(biāo)表示導(dǎo)航路徑的序號(hào)。

根據(jù)表3中的計(jì)算結(jié)果：R（B|S21）＞R（B|S22）＞R（B|S33）＞R（B|S34），最終可以得出結(jié)論：R（B|S21）是前往興趣點(diǎn)（關(guān)鍵字）B的最佳導(dǎo)航路徑。

表3 對(duì)B關(guān)鍵字發(fā)生興趣的4條興趣關(guān)聯(lián)路徑

5.2 實(shí)際數(shù)據(jù)實(shí)驗(yàn)

我們選取了某B2C在線圖書銷售站點(diǎn)服務(wù)器上的日志記錄作為實(shí)驗(yàn)對(duì)象。實(shí)驗(yàn)數(shù)據(jù)包括從2010年9月到2010年11月用戶對(duì)該Web站點(diǎn)的訪問(wèn)數(shù)據(jù)。整個(gè)站點(diǎn)從包括227個(gè)html頁(yè)面。用戶訪問(wèn)日志的總量為105M，包括47，221項(xiàng)。經(jīng)過(guò)事務(wù)識(shí)別算法，共識(shí)別出4843個(gè)用戶訪問(wèn)事務(wù)。我們采用JAVA語(yǔ)言對(duì)本文提出的算法進(jìn)行編程。

首先對(duì)站點(diǎn)中的主要關(guān)鍵字進(jìn)行定義，集合為：Σ=｛經(jīng)濟(jì)，管理，傳記，小說(shuō)，少兒，計(jì)算機(jī)，工具書，歷史，旅游｝；根據(jù)每個(gè)頁(yè)面的內(nèi)容，在各個(gè)頁(yè)面上分別標(biāo)注出Σ的子集。以該網(wǎng)站首頁(yè)面為例，在該頁(yè)上的興趣分布結(jié)果如表4所示。

表4 站點(diǎn)首頁(yè)用戶群體興趣分布

根據(jù)本文建立的INPM模型，以在線圖書銷售網(wǎng)站中 “管理”主題為例，開展用戶群體興趣導(dǎo)航模式R（管理|Sl）（設(shè)置信度閾值為10-6）發(fā)現(xiàn)的實(shí)驗(yàn)工作。實(shí)驗(yàn)結(jié)果如表5所示。

表5 五條R（管理|Sl）興趣導(dǎo)航模式

5.3 算法的性能與比較實(shí)驗(yàn)

此外，本文還對(duì)興趣導(dǎo)航模式發(fā)現(xiàn)算法的時(shí)間復(fù)雜性進(jìn)行了實(shí)驗(yàn)分析。還是采用5.2節(jié)中的真實(shí)數(shù)據(jù)集，發(fā)現(xiàn)R（管理|Sl）模式為例。隨著Sl的長(zhǎng)度增加，模式產(chǎn)生的時(shí)間如圖3所示。從圖3可以看出，序列長(zhǎng)度從1增加到5的過(guò)程中，由于計(jì)算的復(fù)雜度增加導(dǎo)致耗時(shí)也顯著增加。隨著訪問(wèn)序列長(zhǎng)度從6增加到8時(shí)，Sl集合中的訪問(wèn)序列數(shù)量急劇減少，導(dǎo)致計(jì)算耗時(shí)增長(zhǎng)趨緩。這說(shuō)明算法具有良好的擴(kuò)展性，可以較好適用于預(yù)測(cè)大型商務(wù)網(wǎng)站中具有較復(fù)雜鏈接結(jié)構(gòu)與較長(zhǎng)訪問(wèn)路徑的情況。

圖3 R（管理|Sl）模式發(fā)現(xiàn)時(shí)間復(fù)雜度實(shí)驗(yàn)

此外，我們還與文獻(xiàn)［11］中提出經(jīng)典的訪問(wèn)頁(yè)面預(yù)測(cè)方法（基于馬爾可夫模型）從預(yù)測(cè)的覆蓋率及準(zhǔn)確率兩個(gè)方面進(jìn)行比較實(shí)驗(yàn)分析。在實(shí)驗(yàn)開始之前，首先將5.2中采集到的數(shù)據(jù)集分割為兩個(gè)部分：一部分作為訓(xùn)練集，一部分作為測(cè)試集驗(yàn)證計(jì)算結(jié)果的覆蓋率和準(zhǔn)確率。

圖4和5中分別用Based MM表示基于馬爾可夫模型的方法，Based HMM表示本文提出的基于隱馬爾可夫模型的預(yù)測(cè)方法。從圖4中可以看出，在從1×10-6到10-5的閾值條件下，本文提出的模型算法準(zhǔn)確性要高于基于傳統(tǒng)馬爾可夫模型，特別是在低閾值的情況下，準(zhǔn)確率提升更為明顯。從圖5可以看出，在預(yù)測(cè)覆蓋率方面，本文提出的算法在各級(jí)設(shè)定閾值下的覆蓋率均優(yōu)于基于馬爾可夫模型方法。

6 結(jié)語(yǔ)

圖4 預(yù)測(cè)準(zhǔn)確率比較

圖5 預(yù)測(cè)覆蓋率比較

目前，在智能電子商務(wù)研究領(lǐng)域中，對(duì)于群體用戶的導(dǎo)航模式發(fā)現(xiàn)是一個(gè)緊迫而富有意義的問(wèn)題。本文基于經(jīng)典隱馬爾可夫鏈模型，建立了用戶群體興趣瀏覽路徑模型INPM，從中發(fā)現(xiàn)的導(dǎo)航模式不僅可以反映出用戶在訪問(wèn)路徑上的時(shí)間特性，而且更有價(jià)值的是找到了帶有用戶訪問(wèn)興趣的最佳訪問(wèn)路徑。從實(shí)驗(yàn)結(jié)果來(lái)看，本文提出的方法的確是一個(gè)使用、擴(kuò)展性良好的反映全體用戶興趣的導(dǎo)航模式發(fā)現(xiàn)方法。今后的工作，我們將從兩個(gè)方面著手：一是如何更加全面、準(zhǔn)確地定義群體用戶的訪問(wèn)興趣；二是如何將這個(gè)模型方法更好地應(yīng)用于個(gè)性化推薦等實(shí)際問(wèn)題，并在實(shí)際應(yīng)用中對(duì)算法的搜索效率和效果進(jìn)行進(jìn)一步的評(píng)價(jià)研究。

［1］楊德禮，胡祥培，張醒洲.電子商務(wù)環(huán)境下管理理論與方法研究回顧［J］.管理學(xué)報(bào)，2005，2（6）：631-636.

［2］Facca F M，Lanzi P L.Mining interesting knowledge from web logs：A survey［J］.Data&Knowledge Engineering，2005，53（3）：225-241.

［3］Geun-Sik J，Chae Y M.Intelligent electronic commerce［J］.Expert Systems with Applications，2006，24（2）：151-151.

［4］Cohen E，Krishnamurthy B，Rexford J.Improving endto-end performance of the web using server volumes and proxy filters［J］.Proceeding of ACM SIGCOMM.Computer Communication Review，1998，28（4）：241-253.

［5］Zhu Zhiguo.Discovering the influential users oriented to viral marketing based on online social networks［J］. Physica A，2013，392（16），3459-3469.

［6］Wexelblat A，Maes P.Footprints：History-rich webbrowsing［C］.Proceedings of the SIGCHI Conference on Human Factors in Computing Systems，Pittsburgh，May 15-20，1999.

［7］Spiliopoulou M，F(xiàn)aulstich L C.WUM：A web utilization miner［C］//Atzeni P，Mendelzon A O，Mecca G. Proceedings of EDBT Workshop WebDB98.USA：ACM Press，1998：125-133.

［8］Kuo R J，Liao J L，Tu C.Integration of ART2 neural network and genetic K-means algorithm for analyzing Web browsing paths in electronic commerce［J］Decision Support Systems，2005，40（2）：355-374.

［9］王有為，許博，衛(wèi)學(xué)啟，等.基于用戶訪問(wèn)序列聚類的網(wǎng)站導(dǎo)航系統(tǒng)［J］.系統(tǒng)工程理論與實(shí)踐，2010，30（7）：1305-1311.

［10］馬溪駿，凌海峰，劉業(yè)政，等.基于蟻群算法的群體用戶興趣導(dǎo)航路徑發(fā)現(xiàn)［J］.中國(guó)管理科學(xué)，2006，14（3）：55-59.

［11］Sarukkai R.Link prediction and path analysis using markov chains［J］.Computer Networks，2000，33（1-6）：377-386.

［12］Borges J，Levene M.Generating dynamic higher-order markov models in web usage mining［C］//Jorge A，Torgo L，Brazdil P，et al.Knowledge Discovery in Databases：PKDD 2005.Portugal：Porto，Springer，2005：34-45.

［13］Wang Youwei，Dai Weihui，Yuan Yufei.Website browsing aid：A navigation graph based recommendation system［J］.Decision Support Systems，2008，45（3）：387-400.

［14］Rabiner L R.A tutorial on hidden Markov models and selectedapplications in speech recognition［J］.Proceedings of the IEEE.USA：New York，1989，77（2）：257 -286.

Discovery of E-Commerce Users'Interest Navigation Patterns Based on Hidden Markov Chains Model

ZHU Zhi-guo1，2
（1.School of Management Science and engineering，Dongbei University of Finance and Economics，Dalian 116023，China；2.System Engineering Institute，Dalian University of Technology，Dalian 116024，China）

Intelligent discovery of users'navigation pattern has been a hot research issue in the E-Commerce field in recent years.In this paper，users'access interests are defined by combining the information of users'time duration on a page with the keywords on the pages in the E-Commerce Website.The Interest Navigational Path Model is constructed based on the classical Hidden Markov Chains Model.Next，the discovery method for user's interest navigational paths and corresponding mining algorithm are presented. Finally，the experiments are conducted with simulative data，real datasets collected from an online Bookselling B-to-C E-commerce site.Furthermore，the comparative experiment with a classical algorithm is conducted.The experimental results show that the presented model and algorithm can accurately and efficiently find the paths information associated with users'access interests.The method can be adopted as a more effective and practical tool for intelligent navigation discovery oriented to the E-Commerce field.

intelligent E-Commerce；HMM；web data mining；Interest Navigation Patterns

1003-207（2014）04-0067-07

C931

：A

2011-10-13；

2013-07-04

教育部人文社會(huì)科學(xué)研究青年基金項(xiàng)目（12YJCZH321，13YJC790061）；國(guó)家自然科學(xué)基金面上項(xiàng)目（70972059）；遼寧省社科聯(lián)遼寧經(jīng)濟(jì)社會(huì)發(fā)展立項(xiàng)課題階段研究成果（2014Lslktzitsg-01）

朱志國(guó)（1977-），男（漢族），遼寧大連人，東北財(cái)經(jīng)大學(xué)管理科學(xué)與工程學(xué)院，副教授，博士，研究方向：智能電子商務(wù)、社會(huì)化商務(wù)、網(wǎng)絡(luò)營(yíng)銷.