基于隱馬爾可夫模型的電子商務(wù)網(wǎng)站結(jié)構(gòu)優(yōu)化

(1.合肥工業(yè)大學(xué) 管理學(xué)院 電子商務(wù)研究所， 合肥 230009; 2.浙江工業(yè)大學(xué)， 杭州 310024)



摘 要：針對(duì)電子商務(wù)網(wǎng)站中部分商品頁(yè)面不處于用戶預(yù)期位置，導(dǎo)致用戶訪問(wèn)代價(jià)較大的情況，提出一種使用隱馬爾可夫模型對(duì)網(wǎng)站結(jié)構(gòu)進(jìn)行優(yōu)化建模的方法。首先建立一個(gè)隱馬爾可夫模型用于模擬用戶帶有目的(表現(xiàn)為某種目標(biāo)商品)的訪問(wèn)過(guò)程，再使用該模型挖掘出用戶隱藏在訪問(wèn)序列中的目的，最后通過(guò)新增超鏈接實(shí)現(xiàn)網(wǎng)站結(jié)構(gòu)優(yōu)化。實(shí)驗(yàn)證明用該方法解決網(wǎng)站結(jié)構(gòu)優(yōu)化問(wèn)題具備一定的可行性和有效性。

關(guān)鍵詞：隱馬爾可夫模型； 訪問(wèn)序列； 目標(biāo)商品； 網(wǎng)站結(jié)構(gòu)優(yōu)化

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：10013695(2009)03094603



Ecommerce website structure optimization

based on hidden Markov model



XI Dongqin1， LIN Wenlong1， ZHU Jionglin2



（1.Institute of ECommerce， School of Management， Hefei University of Technology， Hefei 230009， China; 2.Zhejiang University of Technology， Hangzhou 310024， China）



Abstract:Since some commodities pages of the ecommerce website were not located in the users’ anticipant position， the greater users’ access costs were spent. This paper proposed a website structure optimization method based on hidden Markov model to solve this problem. First built a hidden Markov model， which could model the users’ access actions with some intentions. Then used this model to mine the users’ hidden intentions (some target commodities) in the access sequences. Finally， done website structure optimization by adding some new hyperlinks. The experiment proves that this method can solve the website structure optimization problem effectively.

Key words：hidden Markov model(HMM); access sequences; target commodity; website structure optimization



0 引言

隨著Internet的發(fā)展，虛擬銷售如電子超市帶來(lái)了在線購(gòu)物的高潮，但合理地安排電子商務(wù)網(wǎng)站結(jié)構(gòu)卻是一件十分艱巨的工作。其主要原因是用戶與網(wǎng)站設(shè)計(jì)人員對(duì)網(wǎng)站結(jié)構(gòu)的理解存在差異：網(wǎng)站設(shè)計(jì)人員必須嚴(yán)格按照商品的分類結(jié)構(gòu)設(shè)計(jì)網(wǎng)站頁(yè)面的分類層次，因而一些商品頁(yè)面并不處于用戶所預(yù)期的位置，這就使得用戶需要訪問(wèn)眾多的無(wú)關(guān)頁(yè)面才能找到自己需要的商品，訪問(wèn)代價(jià)較大。用戶在這樣的網(wǎng)站上購(gòu)買商品非常不方便。

擁有一個(gè)結(jié)構(gòu)合理的網(wǎng)站是成功發(fā)展電子商務(wù)的基礎(chǔ)，因?yàn)榻Y(jié)構(gòu)合理的網(wǎng)站在給用戶帶來(lái)方便的同時(shí)最終也給經(jīng)營(yíng)者帶來(lái)了良好的聲譽(yù)和更多的利潤(rùn)。網(wǎng)站結(jié)構(gòu)優(yōu)化[1~3]技術(shù)正是一種可以提高網(wǎng)站結(jié)構(gòu)合理性的技術(shù)，它主要通過(guò)考慮優(yōu)化網(wǎng)站的超鏈接體系結(jié)構(gòu)來(lái)滿足用戶對(duì)網(wǎng)站便利性的要求。 

本文采用隱馬爾可夫模型解決網(wǎng)站結(jié)構(gòu)優(yōu)化問(wèn)題：用戶訪問(wèn)網(wǎng)站時(shí)是帶有某種目的性的，即他是為了某種商品而來(lái)，正是這種目的性決定了用戶的訪問(wèn)序列。隱馬爾可夫模型可以發(fā)現(xiàn)用戶隱藏 在訪問(wèn)序列中的目的性。因此本文首先根據(jù)用戶會(huì)話構(gòu)建一個(gè)隱馬爾可夫模型，再用該模型來(lái)挖掘出用戶的隱藏目的，最后通過(guò)新增超鏈接來(lái)實(shí)現(xiàn)網(wǎng)站結(jié)構(gòu)優(yōu)化。

1 相關(guān)定義

定義1 網(wǎng)站可以看成是以頁(yè)面為節(jié)點(diǎn)，超鏈接為弧而組成的有向圖，記為

WG=（P，L）

其中：P為網(wǎng)站的頁(yè)面集合；L為頁(yè)面之間的超鏈接集合。如圖1(a)所示。

定義2 用戶的目標(biāo)商品v。用戶訪問(wèn)網(wǎng)站時(shí)是帶有某種目的性的，這種目的性表現(xiàn)為用戶在網(wǎng)站上尋找的某種商品，如一件衣服、一雙鞋等。本文用v來(lái)表示用戶所尋找的目標(biāo)商品。

定義3 用戶的目標(biāo)商品集合V。它由所有用戶的目標(biāo)商品組成： 

V={v1，v2，…，vN}

網(wǎng)站設(shè)計(jì)人員一般會(huì)按照商品的分布模型來(lái)設(shè)計(jì)網(wǎng)站。因而可以從WG中抽象出網(wǎng)站的商品分布模型。

定義4 網(wǎng)站的商品分布模型CG=(P，L)。P、L的意義與定義1中相同。其中，每個(gè)頁(yè)面可以放置不同的商品，一個(gè)商品也可以分布在不同的頁(yè)面上。如圖1(b)所示。

定義5 用戶的訪問(wèn)序列。E=〈p1，p2，…，pt，…，pT〉表示用戶在同一會(huì)話期間的頁(yè)面請(qǐng)求序列。其中：pt為用戶在第t步所訪問(wèn)的頁(yè)面；T為序列的長(zhǎng)度。

定義6 用戶的目標(biāo)商品訪問(wèn)序列。給定一個(gè)用戶的訪問(wèn)序列，將這些序列中的每個(gè)頁(yè)面替換成它所對(duì)應(yīng)的商品，替換后所得到的序列就是用戶的目標(biāo)商品訪問(wèn)序列。

用戶訪問(wèn)過(guò)程中，若其訪問(wèn)目的從目標(biāo)商品vi(vi∈V)變化為vj(vj∈V)，則稱用戶的訪問(wèn)目的發(fā)生了轉(zhuǎn)移。假設(shè)用戶在多個(gè)目標(biāo)商品之間的轉(zhuǎn)移過(guò)程符合馬爾可夫性。

2 隱馬爾可夫模型

用戶對(duì)電子商務(wù)網(wǎng)站的訪問(wèn)是一種帶有目的性的行為。但這種目的性是不可見(jiàn)的，能觀察到的只是用戶在當(dāng)前目的驅(qū)動(dòng)下進(jìn)行的頁(yè)面點(diǎn)擊事件。例如用戶在網(wǎng)站的頁(yè)面間轉(zhuǎn)移以找到商品頁(yè)面，能觀測(cè)到只是他所請(qǐng)求的頁(yè)面而不是他所找的具體某些商品。由此，訪問(wèn)序列可以理解成用戶為了滿足其特定的目標(biāo)商品需求而提出的請(qǐng)求序列，而訪問(wèn)序列中所包含的頁(yè)面訪問(wèn)信息則蘊(yùn)涵了用戶對(duì)該頁(yè)面與其目標(biāo)商品之間的相關(guān)關(guān)系的評(píng)價(jià)。因而，可以建立隱馬爾可夫模型來(lái)模擬這種帶有隱藏目標(biāo)商品的用戶訪問(wèn)過(guò)程。

2.1 基本模型

隱馬爾可夫模型（HMM)[4]被廣泛應(yīng)用于語(yǔ)音識(shí)別[5]、人臉識(shí)別[6]和生物序列分析[7]等領(lǐng)域。本文中采用的是離散化輸出，一階隱馬爾可夫模型，可以用一個(gè)五元組λ=(X，Y，A，B，π)來(lái)表示，其中：

a)X是一個(gè)取值于用戶目標(biāo)商品集V={v1，v2，…，vl，…，vN}上的離散隨機(jī)變量，稱為狀態(tài)序列。其中vi對(duì)應(yīng)用戶的一個(gè)目標(biāo)商品，稱為模型的一個(gè)狀態(tài)。狀態(tài)序列對(duì)應(yīng)于用戶的目標(biāo)商品訪問(wèn)序列。

b)π為X的初始分布，每一項(xiàng)為πi=P(x1=vi)。

c)Y是一個(gè)取值于頁(yè)面集P={p1，p2，…，pT}上的離散隨機(jī)變量，稱為觀察序列。觀察序列對(duì)應(yīng)于用戶的訪問(wèn)序列。

d)A為狀態(tài)轉(zhuǎn)移概率矩陣，每一項(xiàng)aij=P[xt+1=vj｜xt=vi](1≤i≤N)表示由狀態(tài)vi轉(zhuǎn)移到狀態(tài)vj的概率，對(duì)應(yīng)于用戶訪問(wèn)過(guò)程中訪問(wèn)目的遷移（從一種目標(biāo)商品轉(zhuǎn)到另一種目標(biāo)商品）。

e)B為觀察值概率矩陣，每一項(xiàng)bjk=P[yt=pk｜xt=vj](1≤k≤T，1≤j≤N)表示在一個(gè)目標(biāo)商品上，用戶對(duì)頁(yè)面集P={p1，p2，…，pT}的觀察概率分布。bjk還反映了用戶對(duì)頁(yè)面pk與目標(biāo)商品vj的相關(guān)關(guān)系的評(píng)價(jià)。

2.2 模型的訓(xùn)練

通過(guò)對(duì)Web日志預(yù)處理，可以得到由L個(gè)用戶會(huì)話所構(gòu)成的學(xué)習(xí)數(shù)據(jù)集合S={s1，s2，…，sl，…，sL}。會(huì)話sl表示如下：sl={sl[1]，sl[2]，…，sl[t]，…，sl[Tl]}。其中：1≤l≤L，1≤t≤Tl；Tl為會(huì)話sl的長(zhǎng)度。

利用該學(xué)習(xí)數(shù)據(jù)集，可以采用基于EM算法的BaumWelch算法對(duì)隱馬爾可夫模型中的參數(shù)進(jìn)行訓(xùn)練：首先按照經(jīng)驗(yàn)給出初始值，使用學(xué)習(xí)數(shù)據(jù)集S不斷迭代訓(xùn)練更新初始模型，得到使P(S｜λ)最大的模型λ。P(S｜λ)的計(jì)算可以由P(S｜λ)=∑Ll=1P(sl｜λ)確定。其中：

P(sl｜λ)=π(x1)B(sl[1]｜x1)∏Tl-1tA(xt+1｜xt)B(sl[t+1]｜xt+1)

設(shè)給定模型λ和觀察序列sl，t時(shí)刻處于vi和t+1時(shí)刻處于vj的概率為

ξlt(i，j)=P(xt=vi，xt+1=vj｜sl，λ)

則給定模型λ和觀察序列sl，t時(shí)刻處于vi的概率為

γlt(i)=∑Nj=1ξlt(i，j)

迭代時(shí)，模型參數(shù)的更新公式如下：

初始狀態(tài)向量為

i=[∑Ll=1γlt(i)]/[∑Ll=1∑Ni=1γlt(i)]

狀態(tài)轉(zhuǎn)移概率矩陣為

ij=[∑Ll=1∑Tl-1t=1ξlt(i，j)]/[∑Ll=1∑Tl-1t=1γlt(i)]

觀察值概率矩陣為

jk=[∑Ll=1∑Tlt=1∧sl[t]=pkγlt(i)]/[∑Ll=1∑Tlt=1γlt(i)]

2.3 獲取隱藏的用戶目標(biāo)商品

訪問(wèn)序列是用戶為了滿足其目標(biāo)商品需求而提出的請(qǐng)求序列，因此可以根據(jù)已建立的隱馬爾可夫模型從用戶的訪問(wèn)序列中挖掘出用戶的目標(biāo)商品，然后通過(guò)新增超鏈接來(lái)優(yōu)化現(xiàn)有的網(wǎng)站結(jié)構(gòu)。

用Y=(y1，y2，…，yT)表示當(dāng)前用戶的訪問(wèn)序列，yT為用戶當(dāng)前訪問(wèn)頁(yè)面，T為訪問(wèn)序列的長(zhǎng)度，則給定隱馬爾可夫模型的參數(shù)A、B、π及觀察序列Y=(y1，y2，…，yT)時(shí)，可以通過(guò)Viterbi算法估計(jì)狀態(tài)X的最佳值，從而挖掘出隱藏在訪問(wèn)序列中的用戶目標(biāo)商品。設(shè)隱馬爾可夫模型中產(chǎn)生觀察序列Y=(y1，y2，…，yT)的最佳狀態(tài)轉(zhuǎn)移序列為(x1，x2，…，xT)，令在時(shí)刻t取到狀態(tài)vi的各個(gè)路徑的最大概率為

δt(i)=maxi1，i2，…，it-1P(xt=vi，…，x1=vi1，yt，…，y1｜λ)

求解最佳狀態(tài)轉(zhuǎn)移序列的算法如下：

a） 初始化：

δ1(i)=πibiy1，1≤i≤N；ψ1(i)=0，1≤i≤N

b） 用遞推公式：

δt(j)=bjytmax1≤i≤N[δt-1(i)aij]，2≤m≤M，1≤j≤N

ψt(j)=arg max1≤i≤N[δt-1(i)aij]，2≤t≤T，j∈{v1，v2，…，vN}

c） 計(jì)算終值：

T=arg max1≤i≤N[δT(i)]

d） 反向歸納：

t=ψt+1(t+1)，1≤t≤T-1

本文取最佳狀態(tài)轉(zhuǎn)移序列（1，2，…，T)中出現(xiàn)次數(shù)最多的狀態(tài)作為最可能的用戶目標(biāo)商品，再根據(jù)得到的用戶目標(biāo)商品進(jìn)行相應(yīng)的網(wǎng)站結(jié)構(gòu)優(yōu)化工作。

3 實(shí)驗(yàn)

本文在Windows XP professional平臺(tái)上用MATLAB 7.0來(lái)完成實(shí)驗(yàn)。筆者在實(shí)驗(yàn)室搭建了一個(gè)小型的電子超市網(wǎng)站，初始結(jié)構(gòu)如圖2所示。對(duì)該小型超市，本文用文獻(xiàn)[8]的會(huì)話仿真算法生成了800條會(huì)話，平均訪問(wèn)步長(zhǎng)為8.2。

會(huì)話仿真得到用戶會(huì)話集后，取其中75%的數(shù)據(jù)作為訓(xùn)練集。接著，本文采用基于EM算法的BaumWelch算法在訓(xùn)練集上訓(xùn)練隱馬爾可夫模型，訓(xùn)練結(jié)果分別如表1、2所示。

表1 目標(biāo)商品之間的轉(zhuǎn)移概率分布

C1C2C3C4C5

C10.128 30.135 50.274 00.295 20.167 0

C20.205 90.150 40.336 50.127 20.180 0

C30.103 50.092 00.464 00.270 50.070 0

C40.102 30.115 60.241 30.350 70.190 1

C50.158 60.164 50.268 70.165 30.242 9

表2 在每個(gè)目標(biāo)商品上對(duì)每個(gè)頁(yè)面的觀察概率分布

N1N2N3N4N5N6

C10.239 50.231 700.273 500

C20.256 30.221 1000.244 20

C30.131 40.164 90.136 80.139 200.130 2

C40.1570.185 80.165 9000.165 8

C50.258 400.250 7000

N7N8N9N10N11N12

C100.255 30000

C2000.278 4000

C30000.144 70.152 80

C40.175 80000.149 70

C50.25700000.233 9

用戶會(huì)話集中剩余的25%的數(shù)據(jù)為測(cè)試集。本文采用Viterbi算法來(lái)發(fā)現(xiàn)隱藏于用戶會(huì)話中的目標(biāo)商品，新增了指向目標(biāo)商品頁(yè)面的快捷超鏈接， 從而方便用戶訪問(wèn)目標(biāo)商品頁(yè)面，實(shí)現(xiàn)了網(wǎng)站結(jié)構(gòu)的優(yōu)化。結(jié)果分析如下：

a）測(cè)試集中有56%的用戶其目標(biāo)商品為C3，即一半以上用戶的訪問(wèn)目的是C3，因而可以推測(cè)出C3是一種熱門商品。但在該網(wǎng)站的現(xiàn)有結(jié)構(gòu)中，C3所處的位置并不能體現(xiàn)出它是熱門商品，因?yàn)檫@些用戶必須經(jīng)過(guò)眾多無(wú)關(guān)的頁(yè)面才能到達(dá)C3，訪問(wèn)代價(jià)較大。綜合考慮這類用戶對(duì)網(wǎng)站的重要意義以及網(wǎng)站原有導(dǎo)航系統(tǒng)對(duì)老用戶的重要性，可以在首頁(yè)上添加到達(dá)C3的快捷超鏈接(N1→N10)。從而在不影響老用戶訪問(wèn)網(wǎng)站的前提下，縮短這類用戶訪問(wèn)C3的路徑長(zhǎng)度，優(yōu)化了現(xiàn)有的網(wǎng)站結(jié)構(gòu)。

b）測(cè)試集中有很多用戶訪問(wèn)過(guò)C2后會(huì)接著訪問(wèn)C3(可信度為62.7%)，即用戶的訪問(wèn)目的發(fā)生了轉(zhuǎn)移，從目標(biāo)商品C2轉(zhuǎn)移到了C3。但是，用戶在現(xiàn)有網(wǎng)站結(jié)構(gòu)上訪問(wèn)過(guò)C2后要接著訪問(wèn)C3，就必須先從原路返回再接著訪問(wèn)才能到達(dá)C3，走了一些彎路。如果在頁(yè)面N5與N10之間添加一個(gè)快捷超鏈接N5→N10，用戶訪問(wèn)過(guò)C2之后就可以直接訪問(wèn)C3，從而使現(xiàn)有的網(wǎng)站結(jié)構(gòu)趨于合理化。

4 結(jié)束語(yǔ)

一個(gè)結(jié)構(gòu)合理的網(wǎng)站是成功運(yùn)營(yíng)電子商務(wù)的關(guān)鍵。本文針對(duì)電子商務(wù)網(wǎng)站中部分商品頁(yè)面并不處于用戶預(yù)期的位置，導(dǎo)致用戶訪問(wèn)代價(jià)較大的情況，提出使用隱馬爾可夫模型進(jìn)行網(wǎng)站結(jié)構(gòu)優(yōu)化。根據(jù)隱馬爾可夫模型發(fā)現(xiàn)用戶隱藏在訪問(wèn)序列中的目標(biāo)商品，最后通過(guò)新增超鏈接的方法完成網(wǎng)站結(jié)構(gòu)優(yōu)化。實(shí)驗(yàn)證明該方法能對(duì)網(wǎng)站結(jié)構(gòu)進(jìn)行一定的優(yōu)化。

該方法的優(yōu)點(diǎn)是從用戶隱藏的目的出發(fā)，充分反映用戶訪問(wèn)網(wǎng)站的實(shí)質(zhì)；用隱馬爾可夫模型模擬用戶帶有目的訪問(wèn)活動(dòng)具備良好的解釋性；新增超鏈接不會(huì)破壞網(wǎng)站原有的導(dǎo)航系統(tǒng)。但是，用戶的訪問(wèn)過(guò)程是受訪問(wèn)目的、文化背景及愛(ài)好等因素影響的，不同用戶的訪問(wèn)過(guò)程表現(xiàn)出不同的個(gè)性化。該方法采用單一的隱馬爾可夫模型來(lái)描述所有用戶的訪問(wèn)特征，模型過(guò)于簡(jiǎn)單而不能考慮到用戶的個(gè)性化。進(jìn)一步工作是根據(jù)訪問(wèn)特征的相似性將用戶分類，為不同類的用戶建立各自的隱馬爾可夫模型。所有用戶類型的隱馬爾可夫模型集合是一個(gè)混合隱馬爾可夫模型，用該混合隱馬爾可夫模型進(jìn)行網(wǎng)站結(jié)構(gòu)優(yōu)化將更具合理性。

參考文獻(xiàn)：

［1］LIU Yezheng， LIN Wenlong， JIAO Ning，et al. Website structure optimization based on simulation[J].Journal of System Simulation， 2007，19(20):46854688.

[2]WANG Youwei， WANG Dingwei. Commodity covariance based mathematical for link structure optimization of esupermarket website and algorithm analysis[J]. Journal of System Simulation， 2003， 15(2):191193.

[3]WANG Shi， GAO Wen， HUANG Tiejun， et al. Adaptive online retail Web site based on hidden Markov model[J].Journal of Software， 2001，12(4):599606.

[4]RABINER L. A tutorial on hidden Markov models and selected applications in speech recognition[J]. IEEE Trans on ASSP， 1999， 77(2):257286.

[5]WILPON G J. Automatic recognition of keywords in unconstrained speech using hidden Markov models[J]. IEEE Trans on ASSP， 1990，38(11):18781970.

[6]NEFIAN A V， HAYES M H. Hidden Markov models for face recognition[C]//Proc ofIEEE International Conference on Acoustics，Speech， and Signal Processing. 1998:27212724.

[7]DURBIN R， EDDY S， KROGH A，et al. Biological sequence analysis[M].New York:Cambridge University Press， 2002.

[8]YU Zhixue， LIN Wenlong. Web access session simulator based on Markov chain and PageRank algorithm[J]. Computer Technology and Development， 2008，18(5)：182184，187.