基于隐马尔可夫链模型的电子商务用户兴趣导航模式发现

朱志国

（1.东北财经大学管理科学与工程学院，辽宁大连 116023；2.大连理工大学系统工程研究所，辽宁大连 116024）

基于隐马尔可夫链模型的电子商务用户兴趣导航模式发现

朱志国1，2

（1.东北财经大学管理科学与工程学院，辽宁大连 116023；2.大连理工大学系统工程研究所，辽宁大连 116024）

用户智能导航模式发现已经成为电子商务领域中的一个研究热点。为此，结合电子商务站点用户网页访问时间与网页关键字信息对用户访问兴趣进行定义，借鉴经典隐马尔可夫链模型，建立用户兴趣导航模型。给出在此模型中用户兴趣导航路径的发现方法及算法描述。通过模拟数据、某B2C在线图书销售站点中的真实数据以及与经典方法的对比等方面的实验验证，结果表明：给出的模型方法能够准确、高效地找到带有用户访问兴趣的关联路径信息。这个方法可以作为一种应用于电子商务领域更为有效、实用的智能导航发现工具。

智能电子商务；隐马尔可夫模型；Web数据挖掘；兴趣导航模式

1 引言

基于互联网的电子商务极大地缓解了信息不对称等信息约束对传统商务活动的制约，这种前所未有的变化为经济行为最优化和资源配置高效率提供了难得的机遇［1-2］。但是随着电子商务广泛普及发展与深入发展，存储于电子商务站点服务器、代理服务器以及客户机程序插件等多源渠道中的商品信息、交易数据、浏览记录信息日益海量化［3］。以往电子商务企业所采用的“One-Size-Fits-All”的简单粗放服务［4］，已经越来越无法满足用户个性化的需求、偏好及行为特点，导致用户无法准确、高效率地搜寻到感兴趣的相关商品、服务信息；同时电子商务企业也很难根据用户的访问行为，动态优化网站页面结构，以便更加智能快速地响应用户的需求［5］。因此，依据用户兴趣的智能导航模式发现已经成为电子商务学界、业界中的一个热点问题。

国内外对于网络用户导航模式发现的经典研究成果主要有：＂Footprints＂［6］的思想是：访问者在访问一个Web站点时，会留下“足迹”（Footprints）。经过一段时间，最频繁访问的区域会形成路径，于是新的访问者会依据这些路径进行访问。WUM［7］则是对“Footprints＂方法的一种补充，其定义了G-Sequences用于挖掘用户导航模式，并给出了一种挖掘语言MINT。Kuo等人［8］强调用户的浏览行为，采用K-means算法并结合用户访问时间和访问次数来调整用户的兴趣度，从而使得发现的浏览路径模式更具个性化。王有为等［9］将用户的浏览历史抽象为带有时间顺序信息的访问序列，并使用聚类方法进行用户导航模式发现。马溪骏等［10］建立了一个Web站点模型，然后基于蚁群算法和Web日志数据给出了一种用户导航模型发现方法。Sarukkai等［11］基于传统马尔可夫模型对Web站点中链接结构与访问路径预测进行建模与实验分析。Borges等［12］用N阶马尔可夫模型来改进Web缓存的预取性能。Wang Youwei等［13］基于推荐系统构建浏览树图来帮助网络用户导航。

总结起来，上述这些方法大都没有深入考虑到用户对于站点的访问其实是对每个页面节点内部的某一主题信息感兴趣，因此挖掘的粒度相对较粗；此外现有成果也大都没有洞察到用户在每个页面节点的访问时间所能反映出的用户对于内容兴趣程度大小特性，只是根据用户的浏览序列进行了挖掘研究工作。

在本文的研究中，我们认为当用户对一个电子商务站点进行访问时，一定是对某些商品主题产生了兴趣。为此，我们结合电子商务站点中用户网页访问时间与网页关键字信息对用户访问兴趣进行定义，借鉴经典隐马尔可夫链模型，建立用户兴趣导航模型。本文研究成果将为电子商务经营方开展站点结构设计改进、智能网站广告营销等实践工作提供理论与方法支持。

2 网页关键字的提取

电子商务站点中一个页面往往含有多个关键字信息，这些信息可以对一个页面内容进行简要概括和描述。当用户访问一个电子商务站点时，其兴趣偏好恰好可以利用所访问的页面中所具有的关键字集合来表征。下面首先给出一个网页中关键字信息提取的有效方法。

2.1 网站服务器日志预处理

电子商务网站服务器中存储的日志文件记录了每个用户访问请求的如下一些属性：访问时间、用户IP地址、访问资源的文件名或脚本。在一段时间内用户连续提交的请求序列定义为用户会话。通过预处理，可以将这些日志文件整理成服务器会话集。预处理步骤为：

（1）首先，剔除访问多媒体文件、脚本文件的用户请求；

（2）按用户的IP地址，将日志文件分割成独立的访问记录集；

（3）将每个访问记录集的请求按时间排序，设立时间窗口阀值tw，分割访问记录集，时间间隔小于tw的相邻访问请求同属于一个用户会话，这时，每一个用户的每一次访问会话就构成了一个访问事务。

2.2 页面中关键字集合的提取

一个电子商务站点中的网页关键字集合可以通过下面两个过程提取出来：

（1）为了高效率地对网页关键字集合进行抽取工作，首先要对网页进行一些预处理，例如清除掉HTML、XML或SGML等标签；过滤掉网页中所有类似于逗号、句号、引号这样的标点符号；删除掉所有的空行；分词处理；剔除停用词等步骤。网页p在经过清理之后，就可以用一个特征词集T=｛t1，t2，..，tm｝来表示，其中ti表示网页中的一个特征词，m表示特征词的数量。

（2）需要指出的是，网页中的特征词并不一定在页面内容中有很高的出现频率，但是它们一定是常常出现在网页的一些重要标签中，例如title，anchor，text，url等等。因此可以对一个特征词ti的频率用式（1）来进行计算：

其中，A1，A2，A3和A4表示调整系数。在此基础上，可以给出在一个网页中，特征词的权重wp（ti）计算公式，如式（2）所示：

式中，tfmax是特征词出现的最大频率值。可以理解，权重值越大的特征词反映所在Web网页主题概念的能力越强。最终根据给定的阈值，选取权重值超过阈值的一部分特征词来组成网页的关键字集合K=｛k1，k2，…，kn｝，K⊂T。那么一个网页p最终可以简单地用式（3）的关键字集合来表征：

3 用户访问兴趣的相关定义

Web设计者一般会遵循一个站点的关键字分布模型进行设计。下面给出一个Web站点的关键字分布模型定义如下。

Web站点的关键字模型可以定义为：G=（W，E，K），G为一个有向图，如图1所示，其中W 为Web页面集合，E为页面之间的超链接集合，K为每个页面的关键字集的集合。其中每个页面可以放置不同的关键字，一个关键字也可以分布在不同的页面之中。

为了表征用户在一个电子商务站点中的访问兴趣，给出如下定义：

（1）一个用户u的访问事务Tu可以定义为其所访问的所有页面组成的集合，如式（4）所示：

其中，pi表示访问的第i个页面，m表示访问的页面数量。

（2）如式（4）所示，一个网页p可以简单地用一个关键字集合K来表示。这样一个用户u的访问关键字事务Tku又可以用式（5）来表示。

其中Ki表示根据2.2所给出的方法，从页面pi提取出的关键字集合。

图1 Web站点的关键字模型示例

（3）设pe是在Tu中访问的第e个页面。一个用户通过pe页面的访问事务Tu（pe）的定义如式（6）所示：

（4）根据式（5），Tu（pe）又可以转变为一个通过pe的用户u的访问关键字事务Tku（pe），定义如式（7）所示：

（5）对这个用户而言，如果他对某个主题感兴趣，那么他会访问具有该主题的页面，并且他会花费较长时间在这个页面上。下面用lengthu（pe，ki）来表示一个通过pe的用户u访问关键字的时长。设用户u对一个页面pe的时长为lengthu（pe），如果该页面具有f个关键字k1，k2，…kf，那么这个用户在pe页面上对关键字ki的访问时长定义如式（8）所示：

在此基础上，用户访问关键字事务tku中，一个通过pe的用户对关键字kj的访问总时长sumu（pe，kj）可以用式（9）来定义：

4 用户兴趣导航路径模型

本文结合电子商务用户的浏览特性以及用户访问兴趣的定义，基于经典隐马尔可夫模型建立一个用户兴趣导航路径模型INPM（Interest Navigational Path Model）。下面首先简单描述一下模型原型。

4.1 一阶隐马尔可夫链模型原型

隐马尔可夫模型（Hidden Markov Model，HMM）［14］作为一种统计分析模型，现已成功地用于语音识别，行为识别，文字识别以及故障诊断等领域。高阶隐马尔可夫模型的状态数随着模型序数呈指数增长，状态急剧增长使得模型中的状态—空间复杂性计算复杂性过高，并且高阶隐马尔可夫模型在进行预测时常常会出现匹配的序列过少，导致较低的预测覆盖率等问题［12］。因此，本文借鉴离散化输出的一阶隐马尔可夫模型来解决用户访问页面序列预测问题，也就是计算用户访问的前一个页面到当前页面的转移概率。一阶隐马尔可夫模型的原型具体描述如下：

（1）一个状态集合Q。具有指定的初始状态qs和最终状态qf。

（2）一个状态转移集，每个元素为（q→q′）。

（3）一个离散的输出符号集：∑ =σ1，σ2...σm。

从初始状态开始，转移到一个新的状态，观测到一个输出符号。如此反复，直到最终状态，于是就产生一个符号串：X=x1，x2，...，xl。每一个转移存在着一个转移概率P（q→q′）。在一个状态观测到一个特殊符号的概率为P（X|q）。那么一个隐马尔可夫模型M上，符号串X被观测的概率为在所有可能路径上求概率和，如式（10）所示：

这里q0和ql为初始状态qs和最终状态qf，xl+1为终止符号。

建立HMM的一个普遍目的是找到一个状态序列V（X|M），使其具有观察序列的最大概率：

4.2 INPM模型的建立

INPM是一个基于离散化的一阶隐马尔可夫链模型，可以应用于电子商务站点预测用户访问页面序列的模型，其具体定义如下：

（1）设站点中的每一个页面为HMM状态集合Q中相应的节点q。给定一个虚拟的初始状态qstart和一个虚拟的终止状态qend。所有的用户都是从初始状态开始访问，访问结束后到达终止状态。

（2）设站点中存在一个全体关键字集合Σ=｛k1，k2，…kM｝。

（3）两个节点q和q′之间存在一个转移概率P1（q→q′），其定义如式（12）所示：

其中q→q′表示页面节点q和页面节点q′之间有直接的链接存在，count（q→q′）是用户在访问站点的过程中，在事务集T中q和q′同时出现且q′紧随q的事务个数。count（q）是在事务集T中含有q的事务个数。

（4）在每一个节点q′上，用户对关键字集合Σ的兴趣都存在一个概率分布P2（ki|q′），如式（13）所示，这也就是标准HMM中状态节点的观测概率，在此称为兴趣概率：

另外，用户通过q′对关键字集Σ的兴趣概率还满足如下约束，如式（14）所示：

4.3 INPM模型中用户兴趣导航路径模式发现

在INPM模型中，我们借鉴HMM模型中对于某一观测值（兴趣关键字k）序列概率值的算法，如（10）所示。基于此，我们给出电子商务用户的兴趣导航路径发现计算方法，具体定义如下：

在INPM模型上，已知一个用户的访问序列Sl（l表示访问序列的长度）和用户访问兴趣—关键字k，那么兴趣关联模式R（k|Sl）可以定义为式（15）：

如果R（k|Sl）≥C（C为一个给定的可信度阈值）。那么则可以判定R（k|Sl）为一条符合兴趣导航模式的路径信息。

发现的兴趣导航路径信息反映了群体用户对一个网站关键字集合或是某个关键字感兴趣的页面间的转移关系。下面给出兴趣导航模式R（k|Sl）的发现算法描述。

5 实验验证和讨论

我们对提出的电子商务用户群导航模型INPM开展了三方面实验工作：在模拟数据上的兴趣导航路径模式R（k|Sl）发现；针对某B2C电子商务网站环境中真实用户的访问序列数据进行兴趣导航模式的发现实验，并且给出了一些实际结果；最后对算法进行了时间复杂性与比较实验分析。

5.1 模拟数据实验

图2 站点示例

给定一个简单的站点结构图，如图2所示。图中Ni表示当前站点中的页面。页面上方的大写字母表示从该页面中提取出的关键字集合。例如，N1页面上提取出四个关键字A，B，C，D。页面之间有向线段上的数字表示页面间的转移概率。

假设在这个站点中，有四个用户进行访问。每个用户访问的页面以及在页面上的停留时间信息如表1所示。

表1 用户对该站点的访问情况（时间以秒为单位）

根据表1中站点上每个用户的访问情况以及图2中每个页面上的关键字分布情况。利用本文给出的式（13），可以计算出站点内的每一个页面相对于每个关键字的兴趣概率，结果如表2所示。

表2 每一个页面相对于每个关键字的兴趣概率

以关键字B为例，在图2所示的站点中，可以得到对关键字B感兴趣的四条访问路径：｛（N1→N2）；（N1→N3）；（N1→N2→N4）；（N1→N3→N4）｝。根据本文所提出的兴趣关联模式发现方法R（k| Sl），设定可信度阈值为0.01，计算结果如表3所示。表3中S的上标表示导航路径中的所经历的页面节点个数；下标表示导航路径的序号。

根据表3中的计算结果：R（B|S21）＞R（B|S22）＞R（B|S33）＞R（B|S34），最终可以得出结论：R（B|S21）是前往兴趣点（关键字）B的最佳导航路径。

表3 对B关键字发生兴趣的4条兴趣关联路径

5.2 实际数据实验

我们选取了某B2C在线图书销售站点服务器上的日志记录作为实验对象。实验数据包括从2010年9月到2010年11月用户对该Web站点的访问数据。整个站点从包括227个html页面。用户访问日志的总量为105M，包括47，221项。经过事务识别算法，共识别出4843个用户访问事务。我们采用JAVA语言对本文提出的算法进行编程。

首先对站点中的主要关键字进行定义，集合为：Σ=｛经济，管理，传记，小说，少儿，计算机，工具书，历史，旅游｝；根据每个页面的内容，在各个页面上分别标注出Σ的子集。以该网站首页面为例，在该页上的兴趣分布结果如表4所示。

表4 站点首页用户群体兴趣分布

根据本文建立的INPM模型，以在线图书销售网站中 “管理”主题为例，开展用户群体兴趣导航模式R（管理|Sl）（设置信度阈值为10-6）发现的实验工作。实验结果如表5所示。

表5 五条R（管理|Sl）兴趣导航模式

5.3 算法的性能与比较实验

此外，本文还对兴趣导航模式发现算法的时间复杂性进行了实验分析。还是采用5.2节中的真实数据集，发现R（管理|Sl）模式为例。随着Sl的长度增加，模式产生的时间如图3所示。从图3可以看出，序列长度从1增加到5的过程中，由于计算的复杂度增加导致耗时也显著增加。随着访问序列长度从6增加到8时，Sl集合中的访问序列数量急剧减少，导致计算耗时增长趋缓。这说明算法具有良好的扩展性，可以较好适用于预测大型商务网站中具有较复杂链接结构与较长访问路径的情况。

图3 R（管理|Sl）模式发现时间复杂度实验

此外，我们还与文献［11］中提出经典的访问页面预测方法（基于马尔可夫模型）从预测的覆盖率及准确率两个方面进行比较实验分析。在实验开始之前，首先将5.2中采集到的数据集分割为两个部分：一部分作为训练集，一部分作为测试集验证计算结果的覆盖率和准确率。

图4和5中分别用Based MM表示基于马尔可夫模型的方法，Based HMM表示本文提出的基于隐马尔可夫模型的预测方法。从图4中可以看出，在从1×10-6到10-5的阈值条件下，本文提出的模型算法准确性要高于基于传统马尔可夫模型，特别是在低阈值的情况下，准确率提升更为明显。从图5可以看出，在预测覆盖率方面，本文提出的算法在各级设定阈值下的覆盖率均优于基于马尔可夫模型方法。

6 结语

图4 预测准确率比较

图5 预测覆盖率比较

目前，在智能电子商务研究领域中，对于群体用户的导航模式发现是一个紧迫而富有意义的问题。本文基于经典隐马尔可夫链模型，建立了用户群体兴趣浏览路径模型INPM，从中发现的导航模式不仅可以反映出用户在访问路径上的时间特性，而且更有价值的是找到了带有用户访问兴趣的最佳访问路径。从实验结果来看，本文提出的方法的确是一个使用、扩展性良好的反映全体用户兴趣的导航模式发现方法。今后的工作，我们将从两个方面着手：一是如何更加全面、准确地定义群体用户的访问兴趣；二是如何将这个模型方法更好地应用于个性化推荐等实际问题，并在实际应用中对算法的搜索效率和效果进行进一步的评价研究。

［1］杨德礼，胡祥培，张醒洲.电子商务环境下管理理论与方法研究回顾［J］.管理学报，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，Faulstich 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］王有为，许博，卫学启，等.基于用户访问序列聚类的网站导航系统［J］.系统工程理论与实践，2010，30（7）：1305-1311.

［10］马溪骏，凌海峰，刘业政，等.基于蚁群算法的群体用户兴趣导航路径发现［J］.中国管理科学，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

教育部人文社会科学研究青年基金项目（12YJCZH321，13YJC790061）；国家自然科学基金面上项目（70972059）；辽宁省社科联辽宁经济社会发展立项课题阶段研究成果（2014Lslktzitsg-01）

朱志国（1977-），男（汉族），辽宁大连人，东北财经大学管理科学与工程学院，副教授，博士，研究方向：智能电子商务、社会化商务、网络营销.