基于马尔可夫混合模型的电子商务搜索引擎用户行为聚类

为您写电子商务毕业论文和职称论文提供关于电子商务方面开题报告范文,与基于马尔可夫混合模型的电子商务搜索引擎用户行为聚类相关论文例文,包括关于电子商务及模型及用户方面的论文题目、提纲、开题报告、文献综述、参考文献的大学硕士和本科毕业论文，是免费优秀的电子商务论文范文。

摘 要 :对搜索引擎用户行为进行聚类分析有利于为用户提供个性化的服务.为了能准确地刻画用户行为的动态性,提出利用马尔可夫混合模型,对电子商务搜索引擎的用户行为模式聚类.模型假设每一类用户行为可表示为一个马尔可夫模型,当用户使用搜索引擎时,每个用户以一定的概率属于某一聚类；该用户的行为序列,由对应的马尔可夫模型产生.同时,为了解决参数估计和模型自动选择的问题,将贝叶斯阴阳和谐学习理论应用于该混合模型,提出针对该模型的和谐度函数及自适应梯度算法.仿真实验结果表明,与传统的最大期望（EM）算法相比,基于贝叶斯阴阳机的自适应梯度算法能更高效和准确地同时进行参数学习和模型选择.最后,将所提出的聚类方法应用于真实的电子商务搜索引擎点击日志,初步验证了本模型的有效性.

关 键 词 :马尔可夫模型；最大期望算法；模型聚类；贝叶斯阴阳机；和谐度函数

中图分类号: TP391.省略merce search enginebased on the mixture of Markov models

Clustering user behior patterns of E.merce search enginebased on mixture of Markov models

QIN Jun1*,XIAO Rong2

1. School of Computer Science, South.Central University of Nationalities,Wuhan Hubei 430074, China,

2. Taobao (China) Software Company Limited,Hangzhou Zhejiang 310099, China

Abstract:

Clustering the behior patterns of the customers is helpful to provide more specific services for E-Commerce applications. A mixture model based on Markov models is proposed to solve this problem on the search engine of E-Commerce website. This model assumes that the behiors of every customer which uses the search engine can be represented by a Markov model and every user is assigned to a particular cluster randomly. Based on Bayesian Ying-Yang harmony learning theory,a corresponding harmony function and an adaptive gradient algorithm are designed to deal with the parameter-learning and model-selection tasks. The experimental result shows that this adaptive gradient algorithm can achieve the model-selection and the parameter-learning more automatically and efficiently when pared with EM algorithm. At last, this clustering approach is applied on real-world click-through logs of the search engine on .省略 and the result shows that this method can capture the nature of customers’ behiors effectively.省略merce applications. A mixture model based on Markov models was proposed to solve this problem on the search engine of E.Commerce website. This model assumed that the behiors of every customer who used the search engine can be represented by a Markov model and every user was assigned to a particular cluster randomly. Based on Bayesian Ying.Yang (BYY) harmony learning theory, a corresponding harmony function and an adaptive gradient algorithm were designed to deal with the parameter.learning and model.selection tasks. The experimental result shows that this adaptive gradient algorithm can achieve the model.selection and the parameter.learning more automatically and efficiently when pared with EM algorithm. At last, this clustering approach was applied on real.world click.through logs of the search engine on .省略 and the result shows that this method can capture the nature of customers behiors effectively.

Key words:

Markov model, Expectation.Maximization （EM) algorithm, model.based clustering, Bayesian Ying.Yang （BYY）, harmony function

0 引言

分析搜索引擎日志中用户行为模式能帮助我们深入了解用户与系统之间如何交互,并可应用于众多领域,比如：改善用户界面设计［1］, 提升搜索结果相关性［2-3］,个性化搜索结果［4-5］, 优化系统性能［6］等.对于通用搜索引擎日志分析,很多学者已做出许多研究工作［7-8］.随着电子商务的发展,越来越多的用户使用搜索引擎查找他们所需的商品.与通用搜索引擎相比,电子商务搜索引擎的用户的行为有许多不同.用户不仅会点击搜索结果,可能还会收藏或购买感兴趣的商品等.表1给出了一些来自.省略用户动作序列的例子.根据点击序列数据对用户行为模式聚类是对用户行为深入分析的基础.

基于距离的聚类方法,对静态的向量特征数据聚类具有良好效果,但是,由于本文研究的用户点击行为数据具有明显的动态性：用户连续地从一个动作跳至下一动作.如果考虑用向量表示序列,每个分量表示对应的动作出现次数,然后采用基于距离的方法,比如K.means,这有可能丢失掉用户行为的动态性而影响聚类效果.已有学者采用马尔可夫混合模型或隐马尔可夫混合模型［9］对用户网页浏览行为进行建模.受其启发,本文拟采用马尔可夫混合模型对用户使用电子商务搜索引擎的行为进行建模,并采用基于模型的聚类方法来体现用户动作的动态性.

对于基于模型的聚类方法,通常采用最大期望( Expectation.Maximization,EM)算法进行参数估计.但该方法存在一个前提条件：分量模型的数量K是已知的.而对于本

文这一关键信息是未知的,因此需解决模型选择问题.虽然已有学者提出很多关于模型选择标准,如赤池信息准则(Akaike Information Criterion,AIC)、贝叶斯信息准则(Bayesian Information Criterion,BIC)和最小描述长度(Minimum Description Length,MDL)等,但需要对不同的K值重复整个参数估计过程,耗费大量计算时间.Xu提出［10］的贝叶斯阴阳（Bayesian Ying.Yang,BYY）和谐学习系统和理论提供了一个通用的统计学习框架,它不仅可以用来解释现有的众多学习方法,而且对于有限样本集上混合模型学习问题提供了一种新机制,可用来在实现参数估计的同时进行模型选择,其核心是最大化和谐度函数(Harmony Function).Jinwen Ma等基于该理论,提出了针对高斯混合模型的和谐度函数,通过自适应梯度算法求解模型参数,并自动进行模型选择.本文拟将BYY理论应用于马尔可夫混合模型,提出适合该混合模型的和谐度函数,并推导出对应的梯度算法,以解决该模型在参数学习同时模型自动选择的问题.

1.用户行为建模

首先介绍如何从搜索引擎日志中重建用户的动作序列,然后采用马尔可夫混合模型对用户行为进行建模,及基于模型的聚类方法.

本文从.省略搜索引擎一天的点击序列日志中重建了用户动作序列,该日志包含了用户向搜索引擎请求的URL.处理这些数据有以下两个问题需要解决：

1)如何区分不同的用户动作.首先,根据用户使用搜索引擎时的不同意图定义了15种动作：new.search, page, sort, change.tab, location.filter, price.filter, prepay.filter, other.filter, pass, relative.search, change.category, change.mode, click, buy, other.文本采用一个集合来表示S等于{s},0≤s≤14,然后映射URL到这些动作.

2)如何区分不同的序列.IP地址不足以区分不同用户,而且一个用户在一天内可能会使用搜索引擎不止1次.在日志文件中记录了每个URL请求的cookie id.因此,本文假设cookie id和IP地址能唯一地识别一个用户动作序列,而且根据URL映射产生的动作按时间先后保持顺序.如果同一用户的两个动作时间间隔超过30m,则认为这是两个不同的序列.由此获得一个大约1800万个序列组成的数据集,表示为O等于{On|n等于1,等,N}.每个序列On由集合S中状态依次排列组成,例如：On等于0,1,2,12,13.

4.结语

为了分析电子商务网站的搜索引擎用户行为模式,本文提出了采用一阶马尔可夫混合模型用于对用户的动作序列进行建模,并采用基于模型的方法对用户行为进行聚类.该聚类方法与基于距离聚类算法相比,能更好地反映用户行为的动态特性.同时,对于基于模型的聚类方法,分量模型数量K是一个重要的先决条件.对于K的选择问题,通常选择多个不同K值分别训练不同的模型,根据AIC或BIC等准则选择K值,具有很高的计算成本.本文将贝叶斯阴阳和谐学习理论应用于马尔可夫混合模型,提出了针对该模型的和谐度函数及自适应梯度算法,可以较好地解决参数学习同时模型自动选择问题.在模拟数据上进行实验,结果表明：与EM算法相比,基于贝叶斯阴阳机的自适应梯度算法能更高效地进行参数学习和模型选择.最终将马尔可夫混合模型及自适应梯度算法,应用于电子商务搜索引擎用户行为模式聚类上,验证了本文提出方法的可行性.

下一步研究计划包括：首先,采用更高阶的马尔可夫模型作为分量模型,这使得可以对序列中更大范围的依赖关系建模；其次,可以对序列的持续时间建模.可以将多个持续期限模型(比如,指数衰减模型)作为混合模型的分量.这些改进将使得我们可以更加精准地分析用户的行为模式.另外,我们也将在此聚类结果上对用户行为做进一步分析,如：不同类型用户动作序列长度分析、搜索结果相关性分析、用户的高级检索行为等.

为您写电子商务毕业论文和职称论文提供关于电子商务方面开题报告范文,与基于马尔可夫混合模型的电子商务搜索引擎用户行为聚类相关论文例文,包括关于电子商务及模型及用户方面的论文题目、提纲、开题报告、文献综述、参考文献的大学硕士和本科毕业论文，是免费优秀的电子商务论文范文。

［6］

FAGNI T, PEREGO R, SILVESTRI F, et al. Boosting the performance of Web search engines: Caching and prefetching query results by exploiting historical usage data ［J］. ACM Transactions on Information Systems, 2006, 24(1):51-78.

［7］

ZHANG Y, MOFFAT A. Some observations on user search behior［C］// Proceedings of the 11th Australasian Document Computing Symposium. Australia: ACM Press, 2006: 1-8.

［8］

王继民, . 搜索引擎用户点击行为分析［J］. 情报学报, 2006, 25(2):154-162.

［9］

YPMA A, HESKES T. Categorization of Web pages and user clustering with mixtures of hidden Markov models［C］// WEBKDD02： Proceedings of Workshop Web Knowledge Discovery Data Mining. Edmonton, Alberta: ACM Press, 2002:31-43.

［10］

XU L. Bayesian Ying.Yang machine, clustering and number of clusters ［J］. Pattern Recognition Letters, 1997, 18(11/12/13):1167-1178.

［11］

CADEZ I, HECKERMAN D, MEEK C, et al. Visualization of nigation patterns on a Web site using model.based clustering ［C］// KDD00: Proceedings of the sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM,2000:280-284.