用户浏览模式

2024-07-01

用户浏览模式（精选七篇）

用户浏览模式篇1

关键词：Web挖掘,Apriori算法,改进算法,防治技术,用户浏览网页模式

0 引言

随着计算机网络、电子商务的发展, 很多商业性网站中对于用户的关注越来越多, 因为了解用户的需求才能增高网站的收益, 因此了解用户浏览模式是一项重要的工作。如何从这些海量的访问信息中发现潜在的有用的信息, 确定用户浏览网页的顺序、频繁访问哪些网页, 从而为用户推荐网页、推荐商品成为了一个新的研究课题。Web数据挖掘应运而生, Web数据挖掘就是从与WWW相关的资源和用户浏览行为中抽取感兴趣的、有用的模式和隐含的信息。Web上各种形式的文档和用户访问信息就构成了Web数据挖掘的对象。

挖掘用户访问模式常用算法有Web数据挖掘特有的用户访问路径模式挖掘算法 (路径分析技术) 和数据挖掘传统算法, 如关联规则挖掘算法、序列模式挖掘算法等。而本文主要介绍如何利用Apriori算法来挖掘用户的浏览模式。

1 Apriori算法概述

Apriori算法是由R.Agrawal等人提出的一种快速挖掘算法, 是大多数关联规则算法的基础, 它是一种最有影响的挖掘布尔关联规则频繁项集的算法。Apriori算法采用逐层搜索的迭代方法来找出所有的频繁项目集, 在第k次迭代过程中找出所有的频繁k-项集Lk。该算法使用如下的Apriori性质:一个项目集是频繁项目集, 则此项目集的所有子集构成的项目集也一定是频繁项目集;一个项目集是非频繁项目集, 则此项目集的所有超集 (即包含此项目集的项目集) 一定是非频繁项目集。

Apriori算法的基本思想如下:C1=I, I为事务所包含的项目, 扫描数据库, 得到频繁1-项集L1, 将L1中的项目集两两合并, 产生C2, 扫描数据库, 得到L2, 此后在第k遍扫描中, 则是首先利用Lk-1来生成Ck, 若Ck=Φ, 则算法结束, 否则扫描数据库得到Lk。在第k遍扫描中, 第一步:连接步, 通过Lk-1与自己连接来产生Ck (即侯选k-项集的集合) ;第二步:剪枝步, Ck是Lk的超集, 扫描数据库, 确定Ck中每个候选的计数, 计数值大于等于最小支持度计数的所有候选项是频繁的, 从而属于Lk, 删除不满足条件的其候选项。

综上所述, 经典的Apriori算法描述如算法1.1所示。

算法1.1挖掘关联规则的Apriori算法

Apriori算法自身虽然进行了一定的优化, 但在实际应用中还是存在一些问题:

(1) 需多次扫描事务数据库, 通过模式匹配检查一个很大的侯选集合。由于挖掘的对象都是大型数据库或数据仓库, 这样势必影响算法的效率, 要提高效率关键是减少数据库遍历的次数和数据库的规模。

(2) 可能产生大量的候选项集, 不利于规则的产生。

为克服Apriori算法存在的问题、提高算法效率, 人们提出了许多Apriori算法的变形来优化Apriori算法, 如基于散列技术 (散列项集计数) 、事务压缩 (压所进一步选代扫描的事务数) 、划分 (为找候项集划分数据) 、选样 (在给定数据的一个子集挖掘) 、动态项集技数 (在扫描的不同点添加候选项集) 等, 这些算法从不同方面改善了Apriori算法的性能, 提高了效率。

2 改进的Apriori算法

通过分析经典的Apriori算法还有一些改进算法的分析, 可以看出, 存在以下两个问题:

(1) 更新支持度的时候, 需要扫描数据库, 而此时, 数据库中有些项目已经被证明是非频繁的, 可以不必扫描;有些事务根本不包括要寻找的项目, 可以删除。所以, 减少事务的数目和修剪每次交易里的项目数也是提高算法性能的关键。

(2) Aprior算法在从k-项目集生成候选k+1-项目集时, 采用的是连接操作, 该操作要判断是否前k-1项相同而第k项不同。这个操作占用了比较多的程序运行时间, 如果能减少比较次数, 也可以提高算法的性能。

2.1 连接步的改进

本文提出的连接步改进算法:设l1和l2是Lk-1中的项集, 项集中的项按它在整个数据库中出现的频率按升序排序, 执行连接Lk-1×Lk-1时, 若l1[k-2]≠l2[k-2], 则停止对l1和l2的连接操作, 因为此时产生的k-项集一定是冗余项集, 以此来减少计算量。

证明:将Lk-1中的项按它在整个数据库中出现的频率按升序排序后, 其中l1[k-2]出现的个数应该小于等于k-2, 若l1[k-2]≠l2[k-2], 则l1[k-2]出现的最大个数是k-2。而Apriori算法的性质有:如果 (k-1) -频繁项目集Lk-1中包含的单个项目I的个数小于k-1, 则I不可能包含在频繁k-项目集中。因此在Lk-1×Lk-1时, 若l1[k-2]≠l2[k-2], 则l1[k-2]不可能包含在频繁k-项目集中, 因此此时停止对l1和l2的连接操作。

因此对于算法1.1 (输入输出均相同) 我们可进行如下的改变:

算法1.2对于连接步的改进算法

2.2 剪枝步的改进

由算法1.1中我们可以看出剪枝步的思想是, Ck是Lk的超集, 扫描数据库, 确定Ck中每个候选的计数, 计数值大于等于最小支持度计数的所有候选项是频繁的, 从而属于Lk, 删除不满足条件的其候选项。修剪步的改进思想:先计算|Lk-1 (i) |, 其中, i∈I。即计算Lk-1中所有项目的频度, 再找出那些频度小于k-1的项目, 记为I/={i||Lk-1 (i) |<k-1}, 再在Lk-1中去掉所有包含I/中元素的频繁项目集而得到一个新的更小的 (k-1) -项频繁项目集的集合L/k-1, 再由L/k-1与自身相连接而直接生成候选k-项集的集合Ck。

证明:由Apriori算法的性质可知, 若k-项数据项目集I={i1, i2, …, ik}中, 存在一个i∈I使得|Lk-1 (i) |<k-1则I不是频繁项目集, 其中|Lk-1 (i) |表示 (k-1) -项频繁项目集的集合Lk-1中包含i的个数。假设I是k-项频繁项目集, 则 (下转第357页) (上接第221页) 它的k个 (k-1) -项子集均在Lk-1中。则在由I生成的k个 (k-1) -项子集中每一个项目i∈I共出现k-1次, 而|Lk-1 (i) |<k-1这与条件矛盾, 故I不是频繁项目集。

因此对于算法1.1 (输入输出均相同) 我们可进行如下的改变:

算法1.3对于剪枝步的改进算法

3 小结

本文详细介绍了Apriori算法, 并对Apriori算法的思想进行了分析, 在总结其不足后, 提出了改进的Apriori算法, 从连接步和剪枝步两部分提出了如何进行改进比给出了具体的设计思路。

参考文献

[1]范明, 孟小峰.数据挖掘概念与技术[M].北京:机械工业出版社, 2001.

[2]周祥, 郑应平, 王令群.基于Web的数据挖掘技术研究及其在电子商务中的应用[J].电脑知识与技术:学术交流, 2005 (11) .

基于用户浏览行为的文献链接分析篇2

〔关键词〕文献链接分析；用户浏览行为；引文分析；聚类

〔中图分类号〕G203 〔文献标识码〕B 〔文章编号〕1008-0821(2009)04-0150-03

Analysis of the Literature Links Based on Users Browsing BehaviorsWang Li

(Institute of Scientific & Technical Information of China，Beijing 100038，China)

〔Abstract〕Taking the literatures co-browsing phenomenon as the research object，analysis of literature links gives three basic assumptions，andtries to dig the objective relationship among literatures by using for reference from citation analysis.Analysis of literature links can be used widely and simply.Influenced by browse motivation，information ability and information environment，the credibility of analysis results depends on the accumulation of source data.Clustering technology used in analysis processes is very important.Only by adopting the appropriate means of mathematical statistics and analyzing a large amount of data，can we reduce errors effectively，and come to meaningful conclusions.

〔Key words〕analysis of the literature links；users browsing behaviors；citation analysis；clustering

人们在日常生活中经常根据朋友同事的推荐做出选择，这一思想运用到信息推荐中产生了协同过滤技术。协同过滤技术一经出现即在推荐系统中得到广泛应用，虽然面临若干不足，但其算法不断改进，迄今为止仍然是最成功的信息过滤技术之一。笔者认为这种成功主要源于协同过滤技术的基础思想，即人们在获取信息的过程中，人际关系可能是一个比数据库或其他信息资源更为重要的渠道。甚至有研究显示，“人们倾向于向朋友或同事求助的程度，比向其它信息资源如数据库或文件资料求助的程度要多出5倍。[1]”

从信息传播的角度看，协同过滤利用的是社会网络现象，然而人与人之间的这种行为上的相似性折射出信息之间的相似性。能否将社会网络转化为信息网络，进而研究信息之间的关系?基于这一想法，本文提出利用用户浏览行为建立文献链接网络，以文献间的“同浏览”现象为研究对象，借鉴引文分析的思想和方法，采用数理统计的手段挖掘文献之间的隐性关系。

1 基于用户浏览行为的文献链接网络

用户查找文献的过程代表用户一次比较完整的浏览行为，是由一组复杂而有序的操作构成的，本文借用计算机网络技术里的会话概念，称之为一个会话单元。对于一个典型的B/S结构的文献服务系统来说，一个会话单元产生的基本数据包括鼠标点击、键盘输入、页面停留时间、网页跳转等等，数量庞大，且杂乱无章。去繁就简，将文献作为最低层的数据节点，用户在多篇文献之间的浏览跳跃行为可以用网状图表示，如图1所示。

其中，每一个节点表示1篇文献，简单的连线则表示因“同浏览”而建立的文献链接关系，忽略了浏览过程中的先后顺序。

图1 一次用户浏览行为反映的文献链接关系表

每一个会话并不是孤立的，图1仅仅描述了一个会话单元。搜集多个会话数据，对若干个链接关系图进行叠加处理，可以形成一个复杂的文献链接网络，如图2所示。

图2展示了3个会话单元叠加形成的文献链接网络，直线上标注的数字表示2篇文献之间建立链接的次数，如文献D1与文献D2之间的连线标注“2”，表示2篇文献之间有2次因“同浏览”建立起来的联系。显然，该数字越大表示文献间的联系越密切。随着用户行为不断发生，这个文献链接网络将逐渐收敛，揭示利用率高的核心文献，并呈现出若干相对稳定的文献群落。图2 文献链接网络 2009年4月第29卷第4期现?代?情?报Journal of Modern InformationApr.，2009Vol.29 No.42009年4月第29卷第4期基于用户浏览行为的文献链接分析Apr.，2009Vol.29 No.42 文献链接分析

文献链接分析受协同过滤技术的启发，认为“人与人行为上的相似性折射出信息之间的相似性”，并且这种相似性在足够多的数据支持下将逐渐逼近文献间的客观关联。以此为基本思想，文献链接分析以文献间的“同浏览”现象为研究对象，希望利用数学及统计学的手段揭示文献间的内在规律。

基于用户浏览行为建立的文献链接网络与引文的链状结构极其相似，因而文献链接分析可以直接借鉴引文分析的理论和方法[2-4]。

2.1 文献链接分析的基本假设

将用户浏览文献的行为采用简单的“有/无”来描述，可以构造出一个m×n阶的关于用户——文献浏览情况的矩阵R(见图3)。R=r11r12…r1n

r21r22…r2n



rm1rm2…rmn图3 用户——文献浏览情况矩阵

其中，m行表示m个会话单元，n列表示n篇文献，矩阵中的每个元素rij表示在第i次会话中用户是否浏览了第j篇文献，取值为0或1。注意，这里采用“会话”的概念将同一用户的若干次浏览行为区分开，以一个会话单元为观察周期，只有在同一个观察周期内发生的浏览行为才称作“同浏览”。

基本假设一：文献之间的“同浏览”关系反映了文献内容上的相关性。

在图3所示的用户——文献浏览情况矩阵R中，行可以用文献集合D={d1，d2，…，dn}来表示，在某个具体会话单元中包含的文献集合则是D的子集，对于该集合中的任意一篇文献j(j∈Ds)，rsj=1。这时，可以用函数fs(i，j)表示集合Ds中任意2篇文献(i，j∈Ds)在内容上的相关性。

基本假设二：将每一次“同浏览”行为揭示出的文献耦合程度视为一样，并记为一个计量单位。

根据基本假设一，在某个具体会话单元中文献i和j之间的相关性用fs(i，j)表示。如果两篇文献在同一次会话单元中被用户浏览，则认为它们之间有一个由于有共同浏览者而存在的文献耦合联系，fs(i，j)=1；反之，fs(i，j)=0表示不存在同时浏览这2篇文献的用户。

基本假设三：文献之间的耦合度具有简单的可加性。

在图3所示的用户——文献浏览情况矩阵R中，列可以用会话集合S={s1，s2，…，sn}来表示。定义文献i的浏览集合为Si，则Si是S的子集，rki=1(k∈Si)。同理，定义文献j的浏览集合为Sj，如果Si、Sj集合间存在N个相同元素，则表示在N次会话单元中用户同时浏览了文献i和文献j，根据可加性，得到两篇文献的联系为N个单位。

如果将文献i和文献j之间的联系记为Cij，则Cij=∑ms=1fs(i，j)(s∈S)。经过简单加合得到的绝对数量结果可用来度量文献间的耦合强度。

通过3个基本假设，图3所示的用户——文献浏览情况矩阵R可以转化为表示文献关联的n阶方阵C(见图4)。C=c11c12…c1n

c21c22…c2n



cn1cn2…cnn图4 文献关联矩阵

其中，行与列都表示文献，矩阵中的每个元素Cij表示文献i和j之间的耦合强度，通过对用户浏览行为的汇总统计得到。

2.2 聚类

通过“同浏览”关系建立的文献耦合强度可以反映文献间的亲疏关系，这是文献聚类的基础。然而图4中展示的Cij是经过简单加合得到的绝对数量结果，是不稳定的，将随着用户行为的不断发生而变化，笔者采用欧氏距离算法对其进行处理。

首先，可以将给定的文献集合{d1，d2，…，dn}表示为n维空间，文献i和k间的耦合强度Cik可以看作文献i在第k维的坐标，同样，Cik也可以转化为文献j在第k维的坐标。利用欧氏算法公式，可以用∑nk=1(Cik-Cjk)2得到文献i和j之间的距离，记为sim(i，j)。如果sim(i，j)越小，那么文献i和j之间的相关度越高。

通过文献间的相关度计算，可以将给定文献集合进一步划分为若干个文献群，这是一个聚类的过程，相关算法很多[5-8]，本文不再赘述。聚类的结果可以采用可视化方式展示出来，直观描述各个文献群的分布情况，以及文献间的亲疏关系。

3 文献链接分析的特点

文献链接分析具有适用面广、简单易用的特点。

适用面广主要体现于统计素材的易获取性。文献链接分析观察用户浏览行为，研究“同浏览”这种普遍存在的现象。对于图书情报单位的传统文献服务来说，统计数据(如：读者借阅历史)主要来源于流通工作；对于一个典型的文献服务系统来说，用户查找文献的过程则详细记录在系统日志中，可以借用相关工具软件筛选出有用数据。可见，只要存在文献服务，就会记录下用户的浏览行为，进而展开文献链接分析。

文献链接分析借用了引文分析的研究方法，通过简单易懂的统计手段和比较成熟的聚类技术挖掘文献间隐含的客观关联，分析方法简单。通过文献链接分析发现的文献群不是根据图书情报人员对文献特征的判断来发现的，而是在使用过程中自然形成的，可直接应用于实际工作。分析结果通过统计数据的积累可能无限逼近文献的客观联系，同时也带有用户查找文献过程中的普遍特征，在资推荐源、优化搜索引擎、辅助知识挖掘等应用场合中具有较高的参考价值。

4 文献链接分析的局限

用户浏览行为是特定信息环境下用户自由心智的体现，由用户主观驱动，直接受当时的信息环境以及用户信息能力的制约。基于浏览行为建立的文献链接网络受这些因素的影响，必然难以完全准确的反应文献之间的客观联系。概括起来，影响分析结果准确度的主要因素包括浏览动机、信息能力，以及行为发生时所处的信息环境。

用户浏览动机复杂多样，当他抱有明确目的发起一次检索活动时，该过程中涉及的文献具有极强的内容相关性；如果用户只是漫无目的的浏览，在浏览过程中就很容易转换注意力，那么基于该过程建立的文献链接可能是虚假的，即在当前的浏览文献集合中，某篇文献被浏览的行为不一定反映着该文献与其他“同浏览”文献内容相关。文献浏览过程中存在的这种随机现象直接影响文献链接分析方法的应用和效果。

用户信息能力的差异表现为获取文献在质和量上能否满足需求。简单的说，即使2个用户有完全相同的信息需求，他们在查找文献的过程中，在判断哪些文献与需求相关时，也可能产生极大的差异。

同样，信息环境的差异直接影响着用户查找文献的效率。检索系统是信息环境中最重要的部分之一。显然，面对同样的文献集合，发出同样的查询指令，不同性能的检索系统可能带给用户不同的搜索结果。

5 结语

本文提出的文献链接分析以文献间的“同浏览”现象为研究对象，在3个基本假设的基础上展开，充分借鉴了引文分析法的思想和方法，希望利用数学及统计学的手段揭示文献间的内在规律，应用于信息服务的实际工作中。

需要注意的是，该分析方法对用户浏览过程中的随机现象不加区分，认为所有“同浏览”行为都是等价的，因而只是简单的赋予了一个相关度计量单位。这种单纯的计量方式虽然有效的简化了分析过程，但是在用户浏览动机、使用环境等多种因素的影响下，很难有效发掘文献之间的客观联系，一定程度上降低了分析结果的准确度。因此，文献链接分析结果的可信度主要取决于来源数据的积累量。同时，分析过程中采用的文献聚类技术也十分重要。只有采用合适的数理统计手段对足够多的数据进行处理分析，才能有效缩小误差，从而得出有意义的结论。

参考文献

[1]Rob Cross，Andrew Parker，Steve Borgatti.用社会网络分析(Social Network Analysis；SNA)改进知识的创新与共享[EB/OL].http：∥www-900.ibm.com/cn/services/strategy/estrategy/socialnetwork.html#analysis(Accessed Sep.25，2008)

[2]丁学东.文献计量学基础[M].北京：北京大学出版社，1993.

[3]陈光华，江玉婷，庄雅蓁，等.引文分析研究发展现况[EB/OL].http：∥www.lis.ntu.edu.tw/~khchen/writtings/pdf/bookshelf1997.pdf(Accessed Sep.25，2008)

[4]洪光宗.从引文分析看网络结构挖掘[J].图书馆学研究，2006，(12)：45-47，49.

[5]王剑辉，姜龙滨，杨姝.网页文献的快速模糊聚类[J].长安大学学报：自然科学版，2007，27(2)：107-110.

[6]钟伟金，李佳，杨兴菊.共词分析法研究(三)——共词聚类分析法的原理与特点[J].情报杂志，2008，(7)：118-120.

[7]李慧，刘东苏，任志纯.文献聚类技术及其评价函数[J].情报杂志，2004，(7)：17-18.

用户浏览模式篇3

了解用户的访问行为, 挖掘用户偏爱的浏览模式, 对于改善网站的系统设计 (如在相关主题间提供高效快速的访问方式等) , 进行合理的市场决策 (如在适当位置放置广告, 对用户分类等) 都具有十分重要的意义[1]。

许多用于发现人们感兴趣的浏览模式的Web使用挖掘算法已被提出[2,3,4,5,6,7]。文献[2]提出了从最大向前序列集中发现用户存取模式的方法。为了避免大量频繁项目集的产生, 文献[3]提出了建立包含所有用户浏览信息的WAP-树, 然后从该树中挖掘用户偏爱的浏览模式。文献[4]改变了以往单纯通过网页的访问频度挖掘用户兴趣模式的方法, 提出了利用网页的支持度和偏爱度挖掘用户偏爱模式的算法。文献[5]介绍了“软Web挖掘”的定义以及模糊方法在Web挖掘中的应用。文献[6,7]分别给出了使用模糊集理论挖掘用户浏览模式的算法。

由于网页上的浏览时间在一定程度上反映了用户的浏览兴趣, 因此本文通过把网页上的浏览时间刻画为模糊语言变量以反映用户对于偏爱网页的兴趣程度。同时, 为了避免重复扫描日志数据, 通过建立用于存储全部用户浏览信息的FLaAT结构, 可以从FLaAT中发现增量式的模糊的用户偏爱浏览模式。模糊的用户偏爱浏览模式形如{Url1 (ξ1) →Url2 (ξ2) →…Urll (ξl) }, 这里Urli (1≤i≤l) 表示一个用户偏爱的浏览网页, ξi是模糊语言变量, 表示停留在网页Urli (1≤i≤l) 上的模糊时间。

1 模糊变量及隶属函数的相关知识

假设ξ是从可能性空间 (Θ, P (Θ) , Pos) 到实直线R的函数, 则称ξ是一个模糊变量。它的隶属函数可根据它的可能性得到:

μ (x) =Pos{θ∈Θ|ξ (θ) =x} x∈R (1)

定义1[8] 模糊变量ξ的期望值可被定义成如下形式:

其中这两个积分中至少有一个是有限的。

文献[8]给出了模糊变量按照期望值进行比较的原则。

定义2[8]ξ>η当且仅当E[ξ]>E[η]。

2 刻画网页上的浏览时间为模糊语言变量

网页上停留的时间反映了用户对该网页的兴趣和偏爱程度。为了既能体现网页上的浏览时间, 也可以忽略时间上的细微差别, 每个网页上的浏览时间被刻画成一个相应的模糊语言变量来反映用户对该网页的兴趣程度。其刻画方法如下:

Step1 根据专家系统或模拟的方法得到网页浏览时间的隶属函数。一个隶属函数对应一个相应的模糊语言变量λj (1≤j≤s) 。

Step2 计算网页k上的浏览时间 (t1, t2, …, tm) 在每个模糊区域上的标量势Countj (1≤j≤s) :

其中u是网页k上的浏览时间ti (1≤i≤m) 在第j个模糊区域上的隶属度。

Step3 如果, 那么相应的模糊语言变量λt被用来刻画网页k上的浏览时间 (t1, t2, …, tm) 。

假如存在一个模糊的用户偏爱浏览路径A (λ1) →B (λ2) , 如果λ1>λ2, 也就是说A网页的浏览时间比B网页上浏览时间相对长, 我们认为虽然A网页和B网页同是人们偏爱的网页, 然而人们对A网页的兴趣显然要比对B网页的兴趣大。因此带有模糊语言变量的用户偏爱浏览路径更加能反映用户的兴趣程度。

3 基于FLaAT的带语义限定的加权浏览路径的挖掘

3.1 存储用户浏览信息的FLaAT

FLaAT是一种频繁链表加存取树的结构。存取树中记录了所有用户的浏览路径信息。如果若干个浏览序列的前缀相同, 则这些前缀共享一条子路径。但单独的存取树会导致相同URL的多个结点出现在该树中, 因此, 我们创建一个频繁链表把存取树中具有相同URL的结点链接起来, 避免了一些有用信息的丢失, 其结构类型如图1所示。

图1中support是节点的支持度, 它是当前节点的访问频度, preference是网页的偏爱度, 它是该节点的相对访问频度, fuzzy time是模糊语言变量, 刻画该节点的网页上的浏览时间。第k个节点的支持度和偏爱度的定义如下:

$s u p p o r t_{k} = \frac{C_{k}}{n} ‚ p r e f e r e n c e_{k} = \frac{l \times C_{k}}{\sum_{i = 1}^{l} C_{i}}$ (4)

其中Ck是访问第k个节点的次数, Ci是第k个节点的双亲节点访问第i个孩子节点的次数。

根据上述定义, 我们可把用户浏览信息存储在FLaAT中。

3.2 模糊用户偏爱浏览模式的增量挖掘

从存储了所有用户浏览信息的FLaAT中可挖掘出所有的用户浏览模式。在增加若干用户浏览模式后, 挖掘增量的模糊用户偏爱浏览模式算法描述如下。

算法1 增量式的模糊用户浏览模式的挖掘算法 (IDFUPP)

输入:FLaAT, 最小支持度Sthreshold和最小偏爱度Pthreshold。

输出:增量的模糊用户偏爱浏览路径集。

算法分析如下:

1) 网页上的浏览时间被刻画成模糊语言变量使得人们不仅看到浏览时间的不同 (反映用户的不同兴趣程度) , 也可以忽略时间值的细微差别。而且带模糊浏览时间的用户偏爱路径更能反映用户的兴趣和偏爱程度。

2) 搜索用户偏爱模糊路径时考虑到了不同前缀的相同子路径的合并问题, 使得挖掘信息更完整。

3) 由于FLaAT不需要重建, 而且不需要从FLaAT的根部重新搜索已满足条件的用户偏爱浏览模式, 只需要对于重新满足条件的结点进行部分存取树的搜索, 因此在时间上的花费会大大减少。

4 举例说明

假定经过预处理后的Web日志数据 (用户浏览信息) 如表1所示。

假定通过专家系统给定网页上浏览时间的隶属函数如图2所示。

图2 中, short (0, 0, 20, 50) 、middle (20, 50, 90, 120) 和long (90, 120, 140, 140) 是梯形的模糊语言变量, 用于刻画不同程度的浏览时间。例如, 网页A上的浏览时间为 (30, 42, 92, 10, 31, 17, 40) , 它在这三个模糊区域上的标量势分别为short:3.90, middle:3.03, long:0, 因此我们采用short来刻画网页A上的浏览时间。

首先对于表1中的数据建立包含所有用户浏览信息的FLaAT, 对于存取树中的每个节点对应网页的浏览时间均被刻画成相应的模糊语言变量 (short/middle/long) 。

假定最小支持度和最小偏爱度的阈值分别设为0.2和1, 则从FLaAT中直接挖掘出模糊的用户偏爱浏览模式为{A (short) →B (middle) →D (long) }, 经不同前缀的相同子路径合并后, {G (middle) →H (long) }也是一条模糊的偏爱浏览路径。

增加若干用户浏览路径, 如表2所示。

把表2中用户的浏览序列插入到根据表1所建的FLaAT, 修改后的存取树如图3所示。

假定最小支持度和最小偏爱度的阈值不变, 首先从频繁链表中找到第一个不小于最小支持度阈值的项, 根据它的first指针域找到它在存取树中的第一个节点A, 由于A的支持度为1, 偏爱度也为1, 则A是一个偏爱的节点, 它的浏览时间被刻画为short;继续访问它的孩子节点B, B也满足条件, 则B (short) 也是一个偏爱的节点;继续访问B的孩子节点, D (long) 也是一个偏爱节点, 由于D的孩子节点都不满足条件, 则{A (short) →B (short) →D (long) }是一条模糊的用户偏爱的浏览路径。接下来考虑B节点的其它孩子节点, 则{A (short) →B (short) →F (short) }也是一条模糊的用户偏爱的浏览路径。合并相同子路径, 则{G (middle) →H (long) }也是一条模糊的偏爱浏览路径。

5 实验分析

从某网站上下载一个用户存取日志文件进行实验研究。该网站具有20个网页。首先对Web日志数据进行用户识别、会话识别和事务识别等, 然后再对日志数据进行清洗, 删除Web日志中与数据挖掘不相关的信息, 如后缀为gif、jpeg的记录及请求方法、错误代码、传输协议等, 留下与用户浏览兴趣直接相关的一个IP地址下所进行过的一次浏览序列。

我们在Windows平台上用Microsoft VC++语言编程实现本文提出的算法, 使用相同数据与文献[2,4]的算法进行比较。让这三个算法在一定的阈值下挖掘出相同数目的偏爱浏览路径, 增加不同用户浏览模式之后, 这三个算法的运行时间比较如图4所示。由于FLaAT不需要重建, 我们只需要扫描相应的频繁链表, 从而在存取树中的相应子树中发现新增的用户偏爱模式即可, 因而速度大大高于文献[2,4]所提出的算法。然而随着增量数据的加大, 尤其是加大到一定程度时, 运行时间增长会很快, 这是我们进一步需要研究的工作。

6 结论

本文提出了基于FLaAT的增量式的模糊用户偏爱浏览路径的挖掘算法。存放所有用户的浏览信息的FLaAT结构保证了信息挖掘的完整性与增量信息挖掘的高效性。此外, 网页上的浏览时间被表示成相应的模糊语言变量, 这种方式更自然、更易被人理解。

参考文献

[1]金阳, 左万利.有序概念格与WWW用户访问模式的增量挖掘[J].计算机研究与发展, 2003, 40 (5) :675-683.

[2]Chen MS, Park J S, Yu P S.Efficient Data Mining for Path TraversalPatterns[J].IEEE Transactions on Knowledge and Data Engineering, 1998, 10:209-221.

[3]Pei J, Han J.Mining Access Patterns Efficiently fromWeb Logs[C]//Pro-ceedings of6th Pacific Area Conference on Knowledge Discovery and DataMining (PAKDD) .Boston, MA, USA:ACM, 2000:396-407.

[4]Xing D, Shen J.Efficient Data Mining for Web Navigation Patterns[J].Information and Software Technology, 2004, 46:55-63.

[5]Pal S, Talwar V.Web Mining in Soft Computing Framework:Relevance, State of the Art and Future Directions[J].IEEE Transactions on NeuralNetworks, 2002, 13 (5) :1163-1177.

[6]Hong T, Chiang M, Wang S.Mining from Quantitative Data with Lin-guistic Minimum Supports and Confidences[C]//The 2002 IEEE In-ternational Conference on Fuzzy Systems.Honolulu, HI, USA:IEEE, 2002:494-499.

[7]Lo W, Hong T, Wang S.A Top-down Fuzzy Cross-level Web-miningApproach[C]//The 2003 IEEE International Conference on Systems, Man and Cybernetics.Washington, DC, United States:Institute of Elec-trical and Electronics Engineers Inc, 2003:2684-2689.

用户浏览模式篇4

关键词：用户兴趣模型 Web挖掘个性化服务档案馆

中图分类号：TP311.13 文献标识码：A 文章编号：1673-8454（2008）19-0017-03

互联网以惊人的速度迅猛发展，使得设计与维护Web站点的工作变得尤为重要。摆在高校档案馆管理人员面前的新课题是如何管理高校档案馆网站上的大量信息，以满足高校档案馆用户不断增长的个性化的信息需求。所谓个性化服务是指对不同的用户采取不同的服务策略，提供不同的服务内容，其关键在于必须知道用户的兴趣，并准确地建立用户兴趣模型。

一、WEB挖掘

1.Web数据挖掘概述

Web数据挖掘，简称Web挖掘，是数据挖掘技术在Web环境下的应用，是集Web技术、数据挖掘、统计学、计算机网络、数据库与数据仓库、可视化、信息科学等众多领域的一项综合技术。Web数据挖掘是指在互联网上挖掘有趣的、潜在的、蕴藏的信息以及有用的模式的过程。Web挖掘不同于数据挖掘，主要区别在于数据挖掘面对的是结构规范化的数据库，而Web资源是异构的，多为半结构化或非结构化的文档、图形、图像、声音等。

2.Web挖掘的分类

Web信息的多样性决定了Web挖掘的多样性。根据挖掘对象的不同，Web挖掘可以分为Web内容挖掘、Web 结构挖掘、Web 使用记录挖掘。Web挖掘详细分类如图1所示。

二、Web挖掘的个性化研究

所谓Web个性化实质上就是一种以用户需求为中心的Web服务。图2描述了Web个性化的实质。首先，不同的Web用户通过各种途径访问Web资源；其次，系统学习用户的特性，创建用户访问模型；最后，系统根据得到的知识调整服务，以适应不同用户的个性化需求。

1.Web个性化信息服务中用户研究的目的

Web个性化信息服务为用户提供符合个人需要的服务。因此，要真正做好个性化服务,必须深入开展用户研究,了解服务的用户群类型、特征,分析用户的真正需求。

（１）创造适应个人心理和行为的信息活动环境,从而根据用户的知识结构、心理倾向、信息需求和行为方式等充分激励用户信息需求,支持用户习惯行为方式,促进用户有效检索和获取信息,促进用户对信息的利用和在此基础上的知识创新。

（２）凝聚与个人相关的信息资源。通过基于灵活分析的、可方便定制的个性化资源组织机制，形成针对个人或课题特殊需要和特殊应用要求的虚拟信息资源集合，从而在充分挖掘和利用广泛信息资源的同时保障用户信息检索利用的针对性和有效性。

（３）提供针对个人特点的检索与利用服务机制。用户的个性化行为贯穿于用户检索和利用信息的全过程，因此个性化服务必须能够探察用户在这个过程中的知识需求、行为习惯和决策方式，动态组织针对这种个性行为的辅导、辅助、检索和利用机制，为每一个用户过程提供“个人信息咨询助理”，提高用户信息检索与利用的效率。

（４）建立与个人信息系统的有机融合。用户个人积累、处理和传递信息的系统是用户信息环境的基石，信息服务系统通过有机融合和支持用户个人信息系统，将能帮助用户整合基于信息检索利用的知识传播与创新过程中的多个环节与系统、提高用户信息利用的整体能力和效力。因此，个性化信息服务还应致力于协助用户建立个人信息系统，甚至提供个人信息系统ＡＳＰ服务或平台设施，提供这类系统与其它相关资源的有机连接。

2.Web个性化服务系统的一般步骤

Ｗｅｂ个性化服务系统的一般步骤是：（1）收集用户的各种信息，如注册信息、访问历史等；（2）分析用户数据，创建符合用户特性的访问模式；（3）结合用户特性，向用户提供符合其特殊需求的个性化服务。用户对系统提供的服务做出反馈信息，系统根据反馈信息调整服务。通过用户与系统之间循环反复的交互，系统最终能够为用户提供个性化服务。从上面的分析可以看出，通过分析用户的各种信息建立用户访问模式是建立个性化系统的关键。Web挖掘是实现用户建模的基本要求。

3.目前Web个性化服务系统的研究现状

目前已经出现了多个应用Web挖掘技术创建的Web个性化服务系统。这些系统应用的Web挖掘类型包括使用挖掘、内容挖掘和结构挖掘；收集数据的方式有三种，即从客户端、代理或服务器得到原始数据。最后提供的服务有两类，即过虑服务和导航服务。

实现个性化服务的关键，就是对Web用户浏览信息进行正确的分析，准确地描述用户的兴趣。只有准确地把握用户的浏览兴趣，才能将用户感兴趣的资源推荐给用户，也才能在用户群之间进行准确地协作推荐。

准确地描述用户的兴趣主要包括两个方面：（１）从用户浏览信息中准确地挖掘出隐含的用户兴趣信息；（２）采用准确的表示方法来表示用户兴趣。在预先不知道用户兴趣类型的情况下，一般采用聚类算法对用户的浏览信息进行分析。有了聚类结果，怎样来表示用户的兴趣又是另一个重要方面，该表示方法应该满足准确、易于理解和易于更新的要求。

三、高校档案馆用户兴趣挖掘的建模过程概述

Web挖掘是数据挖掘方法在Web环境下的应用，它从数据挖掘发展而来。Web挖掘与传统的数据挖掘相比有许多独特之处。首先，Web挖掘的对象是海量、异构、分布的Web文档数据。通常认为以Web作为中间件对数据库进行挖掘，以及对Web服务器上的日志、用户信息等数据展开的挖掘工作，仍属于传统数据挖掘的范畴。其次，Web在逻辑上是一个由文档节点和超链接构成的图，因此Web挖掘所得到的模式可能是关于Web内容的，也可能是关于Web结构的。此外，由于Web文档本身是半结构化数据，并利用关系表格等存储结构来发现知识，因此有些数据挖掘技术并不适合于Web挖掘，即使可用也需要建立在对Web文档进行预处理的基础之上。

由于档案信息数据的特殊性，基于高校档案馆用户浏览页面内容的挖掘有别于一般的数据挖掘。通过采集用户浏览历史信息数据，然后对这些文本数据进行预处理，得到文本的向量空间模型表示，在此基础上可以对文本进行相似度计算并用于聚类分析。有了文本的基于不同主题的正确分类后，最后分析高校档案馆用户每一兴趣子类的权值，并采用二层树状结构模型来表示用户的兴趣。这就是整个高校档案馆用户兴趣挖掘过程模型，如图3所示。

从图3中可以看出，整个高校档案馆用户兴趣挖掘过程都不需要用户的参与，是完全的隐式创建。系统自动获取用户的浏览信息，经过分析处理后输出用户的兴趣模型。将所得的用户兴趣模型应用于个性化系统推荐服务中，根据用户的反馈信息可以对模型进行更新，符合高校档案馆用户兴趣动态变化的要求。

1.元数据获取

用于Web数据挖掘的数据很多，包括日志信息、用户行为数据、页面超链接信息、页面内容数据、用户注册信息、站点拓扑结构信息等，这些数据一般可以从高校档案馆的服务器端、客户端、代理服务器端获得。服务器端所提供的数据记录了所有高校档案馆用户访问服务器的详细资料；代理服务器记录了多个高校档案馆用户在多个Web站点间的浏览行为；而客户端数据则很直接地反映了某个个体的单一的浏览行为。所以三个不同的数据源分别反映了不同的研究对象群体。在获得用于数据挖掘的元数据后，将它们进行整理并以适当的格式进行保存，供聚类分析和用户兴趣模型建立使用。

本文中用于高校档案馆用户兴趣挖掘的元数据主要是用户浏览页面的内容信息，它被用于基于内容的聚类分析。这些页面的内容信息主要来源于Web服务器端，首先根据用户的浏览日志记录，得到单一用户的浏览历史页面URL，然后从数据库服务器中取出这些URL对应的Web页面另存于该用户的浏览页面文件夹中。

2.数据预处理

与数据库中的结构化数据相比，Web文档具有有限的结构，或者根本就没有结构。即使具有一些结构，也是着重于格式而非文档内容。不同类型文档的结构也不一致。此外，文档的内容是人类所使用的自然语言，计算机很难处理其语义。

Web文本信息源的这些特殊性使得现有的数据挖掘技术无法直接应用于其上。这就需要对文本进行预处理，抽取代表其特征的元数据，这些特征可以用结构化的形式保存作为文档的中间表示形式。文本特征指的是关于文本的元数据，分为描述性特征和语义性特征。描述性特征诸如文本的名称、日期、大小、类型等易于获得，而语义性特征较难得到，包括文本的作者、机构、标题、内容等。W3C近来制定的XML、RDF等规范提供了对Web文档资源进行描述的语言和框架。在此基础上，可以从半结构化的Web文档中抽取作者、机构等语义性特征。

3.文本聚类分析

对Web页面文本进行预处理后，得到文本的特征表示。基于这些结构化表示的数据，就可以采用现有的 Web知识发现方法进行知识挖掘，常用的方法有聚类、关联分析等。

文本分类是指按照预先定义的主题类别为文档集合中的每个文档确定一个类别，它是一种监督学习，对一系列训练样本的分析来预测未知页面的类别归属。与文本分类不同，文本聚类没有预先定义好的主题类别，它是一种无监督学习方法。它的目标是将文档集分为若干类，要求同一类内文档内容的相似度尽可能大，而不同类间相似度尽可能小。基于用户浏览内容来挖掘用户的兴趣是在预先不知道高校档案馆用户兴趣类型的基础之上进行的，所以采用聚类分析方法更适合。整个聚类分析以文本特征表示的页面集为输入，经过聚类后输出表示高校档案馆用户不同兴趣类型的多个兴趣页面集合，每一集合内的页面都与某一特定的主题类别相关。

4.高校档案馆用户兴趣建模

在利用正确的聚类分析方法得到准确性较好的用户兴趣类页面簇后，怎样准确地表示用户兴趣就成了整个用户兴趣挖掘的关键所在。

对高校档案馆网站访问者个人特性爱好的了解是 Web站点提供高效的个性化服务的重要手段。由于网站的设计者和管理者无法直接了解用户的特性，所以我们采用一种根据每个用户的浏览行为为用户兴趣建模的手段提供个性化服务。

用户兴趣建模（ＭｏｄｅｌｉｎｇＵｓｅｒＩｎｔｅｒｅｓｔｓ）是指根据访问者对一个Web站点上Web页面的访问情况，可以模型化用户的自身特性和兴趣爱好。在识别出用户的特性后就可以开展有针对性的个性化服务。用户兴趣建模的主要目的是识别用户的信念、目标和计划，以提供个性化的服务。用户兴趣建模的步骤一般包括以下几个：

（１）定义数据结构以满足系统需要；

（２）识别当前用户；

（３）加载当前的用户模型，如果不存在这样的模型就按照缺省方式新建一个；

（４）在用户与系统交互的基础上更新模型。

通常，用户兴趣建模主要有三种途径：

（１）推断匿名访问者的人口统计特性

由于Web访问者大都是匿名的，所以需要根据匿名访问者的访问内容推断访问者的特性。例如，可以根据已知访问者的统计特性（如：性别、年龄、收入、教育程度等）和对页面的访问内容来推断未知用户的人口统计特性。在得到访问者的人口统计特性后就可以提供个性化的、有针对性的服务。

（２）在不需要用户参与的情况下，得到用户兴趣描述文件

用户兴趣描述文件用于描述用户的基本兴趣特性。要想使Web站点自适应和个性化，一条重要的途径就是了解用户的基本特性，这样才能开展有针对的服务。在前面已经讨论到，用户兴趣描述文件就像一个人在某个Web站点的身份证，它唯一标识了该用户。

（３）根据高校档案馆用户的访问模式来得到用户群体兴趣

基于高校档案馆用户的公共访问特性而进行用户聚类，是Web访问信息挖掘的一个重要方面。用户的访问特性由用户的访问日志得到，聚类的结果可以被用于分类用户或给高校档案馆网站管理者提供参考价值。

四、总结与展望

高校档案馆个性化Web服务通过收集和分析高校档案馆用户信息来学习用户的兴趣和行为,从而实现主动推荐的目的。个性化服务技术能充分提高站点的服务质量和访问效率,从而吸引更多的档案信息访问者。实现高校档案馆个性化服务的关键就是对高校档案馆用户浏览信息进行正确的分析，准确地描述用户的兴趣。只有准确地把握用户的浏览兴趣，才能将用户感兴趣的资源推荐给用户，也才能在用户群之间进行协作推荐。?筅

参考文献：

[1]吉根林,孙志挥.Web挖掘技术研究[J].计算机工程, 2002 Vol.28 No.10 16-17.

[3]Magdalini Eirinaki,Michalis VazirgiannisWeb Mining for Web Personalization, ACM Transactions on Internet Technology,Vol.3,No.1,February 2003,Pages 1-27.

[4]史忠植著.知识发现[M].北京:清华大学出版社,2002.

基于浏览器的用户行为采集方法篇5

申请公布日:2016.05.18

申请人:中国银联股份有限公司

地址:200135上海市浦东新区含笑路36号银联大厦

发明人:王玉球;沈之春;解楠

Int.Cl:G06F11/30(2006.01)I

用户浏览模式篇6

随着信息技术的发展,网站设计和规划变得越来越难。客户的浏览信息被服务器收集起来并保持在日志中。网站的管理者可以通过对Web日志的挖掘发现用户的浏览模式与浏览偏爱路径来重构网站的结构,从而优化网站的拓扑结构,给用户带来更好的体验。

随着WWW技术的发展,互联网正前所未有地影响并改变着我们的生活。由于Internet数据的复杂性,大量非结构化的信息无法使用现有的数据库管理系统进行管理。用户群体的多样性与Internet本身非结构化、动态性、不完全性的特点,体现了巨大的、分层的、多维的方式支持用户有效地发现和利用信息网络上的资源,对信息系统的研究者提出了巨大的挑战。而解决这一方面需求的一个有力工具就是Web使用挖掘,加强对Web日志信息的挖掘,从而发现有用的知识和信息。Web日志挖掘就是在这样的需求下出现的。

Web日志是Web数据挖掘的重要数据来源,它记录了用户访问站点的数据,经过数据预处理可以将Web日志中的数据转换成用户访问路径组成的Web访问事务。浏览兴趣路径挖掘就是找出用户在超过一定阈值的概率下的浏览页面序列,挖掘浏览兴趣路径,有助于改善网站的拓扑结构,对商业决策有着重要指导意义。

1 研究现状

Web日志挖掘的研究在国外起步较早,成熟的系统有:(1)Web Miner 系统。该系统主要是通过处理Web日志,把数据转换为传统的关联规则发现算法所能处理的事务数据形式,然后利用传统算法自动提取Web日志中的关联规则和序列模式。(2)Speed Trace。基于用户会话挖掘出经常被访问的频繁路径和页面组。

相对于国外,国内的Web数据挖掘发展较晚,原因主要是国内对互联网业发展认识和意识较晚。其中比较成熟的技术有:(1)Web-IAM(网站智能分析系统)。(2)TAM模式,为评价网站的质量提供重要依据。(3)SWLMS以及日志挖掘实验系统。

目前,Web日志的挖掘算法主要是在用户浏览模式的获取上。MF算法[1]基于用户折返的特性形成若干浏览子序列。参考长度算法[2]根据用户在网页上的停留时间形成若干个浏览子序列;树形拓扑结构法把整个日志当做浏览子序列,利用关联规则对浏览子序列进行挖掘找出频繁访问路径。以上算法都单纯地考虑了浏览频度,简单地通过浏览频度反应用户的浏览兴趣。这些算法很不精确,比如用户可能将某个页面当成导航页面从而频繁访问。

因此有必要提出一种可正确挖掘用户浏览偏爱路径的算法。本文通过建立访问矩阵,结合海明距离与支持-兴趣度,在此基础上挖掘用户浏览偏爱路径,然后进行实验,提出需要进一步研究的问题。

本文所提出的算法现被上海旅游集散中心用于挖掘其官方网站的用户浏览偏爱路径,其结果表明该算法能有效地反应用户的浏览兴趣。

2 算法描述

首先基于预处理的Web日志建立用户访问矩阵,基于用户访问矩阵的行向量建立海明距离矩阵。通过相似度阈值过滤获得浏览偏爱路径2项子路径候选集。由于忽略了页面的访问频率,我们利用兴趣-支持度对浏览偏爱路径2项子路径候选集进行过滤,获得最终的浏览偏爱路径2项子路径集合,最后通过合并子路径获得最终的浏览偏爱路径集合。

2.1 用户访问矩阵

常见的的Web日志一般采用ECLM日志模式。它的大致结构如表1所示[3]。其中URL表示用户请求访问页面的URL地址。Referer是指引用页的URL。如果用户直接输入URL或利用书签进行访问则该栏为空。

原始Web日志需要进行预处理,传统的Web日志预处理有数据清洗、用户识别、会话识别和路径补充等过程。本文只需数据清洗和简单的会话划分。数据清洗是指删除Web日志中与挖掘算法无关的数据。因为我们只研究HTML文件,故删除如gif、jpeg、jpg、swf等后缀名的文件;会话划分是选取一个浏览时间的最大阈值,一旦页面的浏览时间超过了这个阈值,则认为在该页面终止了访问。

预处理完的日志可以表示为L=<URL_R,URL>的集合,其中URL_R代表引用页,URL代表请求页面。因此访问矩阵可以表示如图1所示形式。

矩阵以URL_R为行,URL为列,元素值为页面的访问频率。另外在矩阵的行列都要添加一个空(NULL)值。如果空值出现在行向量中,代表用户不从站内链接进入访问页,反之如果出现在列向量中代表用户在此页结束浏览或链接到其他网站。如果一个网站有n个URL则该矩阵为(n+1)方阵。

该矩阵有以下几个特点:

(1) 对角元素值为0(自身不能作为自己的引用页);

(2) K行值总和等于K列值总和(进出平衡)。

由上面的定义可知访问矩阵的空间复杂度和网站的URL数成平方关系。现实生活中网站的URL个数十分巨大,但每个网页的链接数不会超过几十个,这样矩阵中的大多数元素都为零。因此网站的访问矩阵是典型的稀疏矩阵,建议使用三元组表示法来存储网站访问矩阵。

2.2 建立海明距离矩阵

遍历网站访问矩阵,如果∀M[i,j]>0则M[i,j]=1得到矩阵M′,如图2所示。

基于式(1)计算M′行向量的相似度,得到海明距离矩阵Mr,同样海明距离矩阵的对角元素值为零,如图3所示。

$Η_{d} (x, y) = \sum_{i = 1}^{∥ x ∥} (x_{i} - y_{i})^{2} (1)$

其中Hd在本文中代表URLx与URLy的距离即相似度,‖x‖为URL的总数,xi代表用户是否通过URLx访问URLi,有则为1否则为0,yi则代表URLy相应的情况。因此我们可以知道Hd,即矩阵M′行向量URLx与行向量URLy的距离。

2.3 获取2项子路径候选集

建立海明距离矩阵的目的是为了比较各个URL之间的相似度。基于先验知识我们可以知道相似度高的页面被用户同时浏览的概率较高,因此将相似度高的页面作为浏览偏爱路径的2项子路径的候选项有助于提高挖掘结果的准确性。

根据式(2)得到相似度阈值∂,将其与矩阵Mr的元素做对比,从而获得浏览偏爱路径二项式。

$\partial = 2 \times \sum_{i = 1}^{n} \sum_{j = 1}^{n} d_{i j} / n^{2} (2)$

其中dij为矩阵Mr中i行j列的元素值即URLi与URLj的距离,n2为矩阵Mr的元素个数,因此我们可以知道式(2)代表的是网站所有URL的距离平均数。

为∂设定相应阈值,遍历矩阵Mr,如果∀dij≤∂则URLi和URLj列为一类,<URLi,URLj>将作为浏览偏爱路径的2项子路径的候选项。

由于通过海明距离矩阵与相似度阈值计算出来的浏览偏爱路径2项子路径忽略了页面的访问频率,因此我们需要对上面计算出来的2项子路径候选项进行进一步的确认,在这里我们提出兴趣-支持度概念,并在此基础上对候选2项子路径进行过滤。

2.4 兴趣-支持度

为了去除一些无意义的规则,我们利用一个适合网站浏览的相对访问率的概念:兴趣-支持度,充分考虑真正强度与平均强度之比。

定义1 选择兴趣度访问矩阵M第i行中非零元素的个数m代表用户在URLi上有m种不同的选择,每种选择的平均访问度如式(3)所示。

$\bar{s} = (\sum_{j = 0}^{n} A_{i j}) / m (3)$

其中Ai,j表示第j种选择的支持度,m代表非零元素的个数。则第j(j=0,1,2,…,n)种选择的的选择兴趣度可以定义为:

$Ρ = A_{i j} / \bar{s} (4)$

在挖掘浏览偏爱路径时不仅要考虑偏爱性而且要考虑支持率,我们将两者结合起来考虑。

定义2 兴趣-支持度假设在定义1种某种选择的支持度为S,而它的选择兴趣度为P,那么将它的兴趣-支持度定义为:

Ps=S×P (5)

2.5 利用兴趣-支持度过滤候选2项子路径

结合式(5),对于访问矩阵M,我们可以根据式(6)计算每个元素的兴趣-支持度。

$Ρ_{i j} = [A_{i}_{j} / [[\sum_{j = 0}^{n} A_{i j} / m]] \times Α_{i j} (6)$

定义兴趣-支持度阈值∂′,遍历访问矩阵M,如果∀Pij<∂′,且<URLi,URLj>是浏览偏爱路径2项子路径的候选项,则将<URLi,URLj>从候选集中删除,从而得到浏览偏爱路径2项子路径最终集合。

2.6 浏览偏爱路径挖掘

基于海明距离矩阵与兴趣-支持度我们获得了浏览偏爱路径的2项子路径集。通过对2项子路径进行合并得到浏览偏爱路径的完整集合。合并算法如下:

3 实例与分析

下面举例说明,在经过Web日志数据清洗后得到图4所示的访问矩阵。

从图4可以看出访问矩阵为稀疏矩阵,同时对角线元素为零。以下是基于访问矩阵M挖掘浏览偏爱路径的过程。

1) 遍历访问矩阵M,如果∀M[i,j]>0则M[i,j]=1 得到转化矩阵如图5所示。

2) 通过式(1)计算距离矩阵Mr如图6所示。

3) 根据式(2)得到相似度阈值∂=3。

4) 遍历矩阵Mr,如果∀dij≤∂则URLi和URLj列为一类,<URLi,URLj>将作为浏览偏爱路径的2项子路径的候选项。由此我们可以得到浏览偏爱路径2项子路径集:{<NULL,A>,<NULL,F>,<NULL,H>,<A,NULL>,<A,B>,<A,C>,<A,G>,<A,H>,<B,A>,<B,F>,<B,H>,<C,A>,<C,D>,<C,E>,<C,G>,<C,H>,<D,C>,<E,C>,<E,G>,<E,H>,<F,NULL>,<F,B>,<F,G>,<F,H>,<G,A>,<G,C>,<G,E>,<G,F>,<G,H>,<H,NULL>,<H,A>,<H,B>,<H,C>,<H,E>,<H,F>,<H,G>}。

5) 设定兴趣-支持度阈值为5,遍历浏览偏爱路径2项子路径候选集,根据式(6)计算每个候选项的兴趣-支持度P,如果P<5,则将该候选项删除,得到浏览偏爱路径的最终集合:{<NULL,A>,<A,C>,<C,E>,<E,H>,<H,NULL>,<B,F>}。

6) 合并浏览偏爱路径2项子路径得到最终的浏览偏爱路径集合:{<NULL,A,C,E,H, NULL>,<B,F,NULL>}。

4 实验结果和效率分析

我们在Windows XP SP2系统下,利用Visual Studio 2008平台开发语言为C++实现了本文的挖掘算法,同时实现了文献[1]中MF算法和文献[2]中的NPPMA算法,然后在内存为1G,CPU为Intel Core2 的计算机上对其准确性和CPU执行时间进行了对比。

本文的实验数据来至于上海旅游集散中心官方网站2010年12月1日至2011年1月20日的Web日志,其记录数总计137248条。

我们采用如表2所示的网站日志将本文算法与NPPM算法和MF算法进行了准确性实验比较。比较方法是在一定的阈值下挖掘出相同数量的浏览偏爱路径并与已知的网站经验兴趣路径作对比,得到准确性度量。结果如图7所示,我们可以看到本文的算法比NPPM算法和MF算法的准确性都要高,同时我们可以看到随着挖掘路径数的增加,三个算法的准确性都随之降低。这是因为当需要挖掘的路径数目越多相关的兴趣度量阈值越低,挖掘出的路径的可信度降低。

另外本文用两个服务器日志片段分别有300个网页和600个网页,我们将日志分行分割形成大小为1M、2M、3M、4M和5M的5个测试例通过执行时间得到曲线(如图8所示),从图中可以看出本文算法的CPU执行时间比NPPMA算法和MF算法要少,且随着日志日志数量的增加本文算法执行时间的增幅相对较小,说明本算法的可扩展性较好。

由上述实验可以证明本文提出的挖掘算法要优于NPPMA算法和MF算法。

5 结语

目前,在Internet电子商务中,如何准确地找出用户浏览偏爱路径,优化Web站点的拓扑结构,改进商务决策,是急需解决的难题。本文基于Web访问矩阵和海明距离,将相似度高的页面归为一类,并利用兴趣-支持度从而得到浏览偏爱路径2项子路径集,最后通过合并子路径获得最终的浏览偏爱路径全集。与频繁访问路径相比,它更能反映出用户的浏览兴趣与意图。而且算法本身对服务器日志的预处理要求低,只需要简单的数据清洗。实验表明该学方法能准确反映用户浏览兴趣,而且系统可扩展性也较好。

参考文献

[1]Mobashe B,Srivastava J.Data preparation for mining Word Wide Web browsing patterns[J].Knowledge and Information System,1999,1(1):5-32.

[2]Chen M S,Park J S,Yu P S.Data mining for path traversal patterns in a Web environment[C]//Proceedings of the16th International Con-ference on Distributed Computing Systems,Hong Kong,1966:385-392.

[3]Srikant R,Agrawal R.Mining generalized association rules[C]//Very Large Data Base,Proceedings of the21st International Conference Switzerland,1995:407-419.

[4]Yang D L,Yang S H,Hong M C.An efficient web mining for session path patterns[C]//Workshop on Software Eng.and Database Sys-tems,Proceeding of International Computer Symposium2000,Taiwan,2000:107-113.

[5]Xing Dong-shan,Shen Jun-yi.An efficient and multi-purpose algo-rithm for mining Web logs[J].Journal of Computer Research&Devel-opment,2001,38(3):328-333.

用户浏览模式篇7

用户兴趣模型是存储用户的兴趣偏好、存储和管理用户的行为历史、存储学习用户行为的知识和进行相关推导知识的功能集合[1]。近年来学者对个性化搜索引擎系统中的用户兴趣模型进行了广泛深入的研究, 林国[2]分析了现有用户兴趣模型的不足, 指出了用户兴趣模型的基本结构, 提出了个性化搜索引擎中用户兴趣模型的工作过程。刘东飞[3]提出了一种基于群用户兴趣模型的加权全局相关度查询排序算法, 改进了搜索引擎的排序结果, 为用户提供了较准确的搜索服务。王微微[4]提出了一种基于用户行为的兴趣度模型, 分析了用户的行为模式, 结合用户的浏览内容发现用户兴趣。刘文杏[5]根据用户的兴趣和喜好提出了一种挖掘用户兴趣的路径浏览模型和算法, 使Web服务器能更快地反馈信息, 能够为用户提供更好的信息服务。郝水龙[6]提出一种基于层次向量空间模型 (VSM) 的用户兴趣模型表示及更新处理机制, 采用基于用户浏览行为来计算用户对网页的兴趣度, 快速估计网页兴趣度。郭力军[7]改进了基于RSS数据源的用户兴趣模型, 模拟实验表明该改进的用户兴趣模型个性化程度较高, 对用户兴趣更新及时、准确。

1 改进用户浏览行为的用户兴趣模型

基于用户浏览行为的用户兴趣模型综合考虑了用户对页面的感兴趣程度和关键词在页面中的权重, 充分地反映了用户的个性化特点, 能够满足用户的实际需求[8]。然而, 用户的兴趣偏好是经常变换的, 不同时期内用户的兴趣点是各异的, 笔者在本文中建立的用户兴趣模型则全面考虑了用户对页面关键词感兴趣程度和对页面感兴趣的程度, 并同时兼顾到用户的长期和短期兴趣。

一般来说, 用户访问的页面都是自己感兴趣的页面, 用户可能在短期内对某些领域感兴趣而忽略了长期感兴趣的领域, 这样势必在一段时间内会影响到用户搜索的质量和效率[9,10]。因此, 在构建用户兴趣模型时, 需综合考虑到用户的长期和短期兴趣。

(1) 短期兴趣。假设用户当天共访问了L个页面, 我们可以用向量Ptoday表示用户当天的短期兴趣。故可把用户当天的短期兴趣模型表示为:

其中用户当天对于第j个关键词的兴趣度可表示为:

(2) 长期兴趣。对用户的长期兴趣, 我们使用用户N天以来的访问历史来构造。我们定义Lt为用户第t天浏览的页面数, 其中t=0表示当天, 所以, 我们可以通过N来构造用户的长期兴趣Pper。与用户短期兴趣Ptoday的构造方法相同, 可表示为:

其中:

公式 (4) 中Lt表示第t天用户浏览页面的总数 (t

(3) 最终兴趣模型。用户长期兴趣模型需要动态更新, 最终的用户兴趣模型表示如下:

x、y表示短期兴趣和长期兴趣对用户最终兴趣的影响权重, x、y的值是根据经验获得的, 我们通过对大量数据进行分析和观察对比以及对不同x、y值的比较, 最后确定y=0.4、x=0.6, 式 (5) 中c为常量。

2 基于改进用户兴趣模型的个性化搜索引擎

用户兴趣模型通过用户的交互过程中不断获取用户的兴趣偏好, 然后通过构建用户兴趣模型, 对用户兴趣模型进行更新优化, 将用户兴趣模型得到的信息传送给搜索引擎使搜索引擎能检索出用户感兴趣的信息, 同时通过对检索到的信息与用户兴趣模型进行对比, 来获取用户感兴趣页面的排名, 并按照用户对页面感兴趣的程度进行排序, 将页面个性化地显示出来[11]。

2.1 系统基本框架

基于用户兴趣模型的个性化搜索引擎的系统框架结构如图1所示, 该系统工作流程如下:首先访问用户接口模块, 当用户输入检索关键词后, 就进入检索模块;个性化用户兴趣模型会从用户接口模块中对用户个性化信息进行搜集;在检索模块用户可以直接输入需要检索的关键词进行查询, 同时检索模块会记录下用户检索历史;个性化用户模型会从检索模块中提取用户的检索历史, 然后通过对用户个性化信息的处理, 反馈到检索模块, 检索模块则搜索出用户感兴趣的网页文档, 同时过滤掉用户不感兴趣的网页文档或者和用户行为不相关的网页文档, 按相关度大小对搜索出的结果进行排序;最后将最终处理后的检索结果提交给用户。

从图1中可以看到, 用户兴趣模型的信息来源于两个方面:用户的浏览行为和用户的搜索历史。根据用户浏览行为和搜索历史, 来研究构建用户的短期兴趣模型和长期兴趣模型。通过建立动态用户兴趣模型, 将用户感兴趣的内容快速的检索出来, 同时过滤掉对用户无用的信息。把检索到的结果文档按相关度大小进行排序, 将用户最感兴趣的信息反馈给用户, 实现智能化、个性化的信息搜索。

2.2 系统基本功能模块

(1) 用户接口模块。用户接口模块提供用户注册/登录接口界面, 用户输入个人信息, 这些信息可以组成用户兴趣模型的默认信息, 即用户初始的用户兴趣向量。用户兴趣模型可以通过用户的浏览行为和用户在一段时间内的搜索历史来建立。

(2) 检索模块。用户在检索模块可以直接输入需要检索的关键词进行查询, 同时用户接口模块会记录用户的检索历史, 如检索关键词、访问的网址、用户的操作等。检索模块工作时首先从本地信息库中搜索用户的检索关键词, 如果本地信息库中没有相关信息, 则调用爬虫程序从互联网中搜集, 对搜集到的相关Web网页进行相关处理, 并把处理过的网页加入到本地信息库。另外检索模块根据用户的兴趣模型, 对搜索到的结果进行过滤, 对于用户感兴趣的文档页面, 与用户兴趣模型一起计算其相关度, 按照相关度大小排序后显示给用户。

(3) 用户兴趣模型模块。用户兴趣模型模块包括3个方面:搜集并记录用户的兴趣需求、建立个性化的用户兴趣模型、对检索到的结果进行过滤和排序并反馈给用户。用户兴趣模型主要用于搜集、记录、管理用户的兴趣偏好, 描述用户潜在兴趣需求。

(4) 本地信息收集模块。本地信息库的建立对于提高个性化搜索引擎的检索速度有极大的现实意义。当用户利用传统的搜索引擎进行检索时, 提交检索关键词后, 由搜索引擎的爬虫程序立即从Internet上进行Web信息搜集, 或者利用元搜索引擎的同时调用多个专业搜索引擎在Internet上进行搜索, 搜索到符合条件的记录后, 进行相关处理并把结果反馈给用户。

本地信息库建立后, 当用户利用该个性化系统进行信息检索时, 检索模块首先从本地信息库中进行查询, 这样查询范围大大减少, 检索速度也有了很大提高。当本地信息库中没有用户所检索的关键词信息时, 立即调用爬虫程序在互联网上进行搜索, 并把搜索结果放到本地信息库中, 检索模块对搜索到的结果进行相关处理并反馈给用户。如果本地信息库中没有用户所搜索的关键词信息, 就对本地信息库进行实时更新, 保证本地信息库中信息的完整性。为了保证用户搜索到时新性的信息, 还要定期利用爬虫程序对用户兴趣库中已存在的关键词库所对应的Web网页信息进行更新, 一般设定的更新频率为7天。

为简化算法, 文中的爬虫程序直接调用了Google的爬虫程序, 也就是说, 用户搜索个性化是在Google搜索引擎所搜索结果的基础上, 利用用户兴趣模型和用户兴趣挖掘算法进行个性化服务。

3 个性化搜索引擎实验

为了验证本文所建立的改进的用户兴趣模型的有效性, 我们在.NET平台下开发了一个个性化搜索引擎系统 (IUBPSES) , 我们把改进的用户兴趣模型嵌入该IUB-PSES系统中。

同时, 我们还把本文改进的IUBPSES系统的检索结果与周晓兰[11]的检索结果、刘建波[11]的检索结果以及Google搜索引擎的检索结果进行了比较分析。我们把8个关键词利用上述4种系统分别进行实验对比分析, 对每个关键词的检索结果均取前20个Web页面进行分析, 并分别计算8个关键词在各个系统下所对应的查准率, 图2是本文基于改进用户浏览行为的IUBPSES系统与文献[11]、文献[12]和Google搜索引擎的关键词查准率对比图。

从模拟实验结果来看, 使用IUBPSES系统进行信息搜索, 其检索效果明显优于上述提到的其它的搜索引擎系统。如图2所示, 当用户兴趣存在偏好时, 采用IUBPSES系统进行信息检索, 其搜索效率高于未采用IUBPSES系统的其它文献中的系统。

4 结语

虽然本文中实现的IUBPSES系统能够较准确地描述用户的兴趣偏好, 模拟实验结果也证实其搜索效果明显优于目前主流的搜索引擎, 但本文还有很多值得改进和进一步研究的地方。

(1) 在改进用户兴趣模型的基础上, 使用更有效的用户兴趣挖掘算法, 能够在用户兴趣挖掘更快、更准确, 从而建立更符合用户兴趣偏好和用户特征的用户兴趣模型。

(2) 在IUBPSES系统检索结果页面的个性化显示方面, 不仅考虑Web页面和用户兴趣模型的相似度, 而且可以引入更多的参数来综合考虑检索结果页面的排序, 从而能让检索结果更符合用户的需求。

(3) IUBPSES系统没有对用户进行聚类和分类, 对用户进行聚类和分类将会使需求相同或相似的用户划分到同一个类别里, 对于相同或相近的关键词检索可推荐其他用户的检索结果, 会更利于用户发现感兴趣的信息, 也利于提高信息的查全率和查准率。

参考文献

[1]MARTIN BAUTISTA M J, KRAFT D H, VILA M A.User profiles and fuzzy logic for web retrieval issues[J].Soft Computing, 2003 (6) :365-372.

[2]林国, 李伟超.个性化搜索引擎中用户兴趣模型研究[J].软件导刊, 2012 (8) :26-28.

[3]刘东飞, 白瑾.基于群用户兴趣模型的搜索结果排序研究[J].武汉理工大学学报, 2011 (6) .

[4]王微微, 夏秀峰, 李晓明.一种基于用户行为的兴趣度模型[J].计算机工程与应用, 2012 (8) :148-151.

[5]刘文杏, 张彬连.基于用户兴趣的路径发现模型的探究[J].信息系统工程, 2012 (6) :132-133.