【doc】Web日志中用户频繁路径快速挖掘算法
Web日志中用户频繁路径快速挖掘算法
Web日志中用户频繁路径快速挖掘算法
杜家强韩其睿王科杜家兴z
(天津工业大学计算机应用与自动化学院,天津300160)
(人民日报社网络中心,北京100733)
E—mail:djqluck@peopledaily.com.ca
摘要Web访问志中舍有大量用户浏览信息,从中有效挖掘出用户频繁路径是建立自适用化网站的必要前提.该文在
Apriori算法和有向图存储结构的基础上,提出了会话矩阵和遍历矩阵的概念,设计了用户频繁路径快速挖掘算法:首先
利用会话矩阵筛选出满足一定阈值条件的频繁一项集,这样避免产生大量中间项;然后在相似客户群体内.对页面快速
聚类,得到相关联页面;最后根据遍历矩阵对相关联页面进行路径合并,得出频繁路径.实验
明此算法的准确性和快速
性.
关键词会话矩阵遍历矩阵相关联页面用户频繁路径快速挖掘算法
8331一(2005)22—0164—04文献标识码A中图分 文章编号1002—
类号TP393
AFastAlgorithmforMiningUserFrequentPathsfromWebLogs
DuJiaqiangHanQiruiWangKeDuJiaxing
(CollegeofComputerApllicationandAutomation,TianjinPolytechnicUniversity,Tianjin300160)
0(People?sDailyOnline,Beijing100733)
Abstract:Weblogscontainalotofuserbrowsinginformation,it?Snecessaryconditionforcreatingadaptivewebsites.
0ntheanalysisofApriorialgorithmandgraphicstorageorganization.ThispaperproposesSessionMatrixandTrace
Matrix,designsafastalgorithmformininguser~equentpaths:Firstly,Frequent1一ItemSetwhichmatchthecriteriaof
certainthresholdisfilteredouffromwebaccesslogsbySessionMatrix,whichavoidsgeneratingagreatdealof
intermediateitems;Thenwecangetrelativepagesbyclusteringpagesfastinsimilarcustomergroups;Finally,allthe
relativepagesiscombinedbyTraceMatrix,whichgeneratesFrequentPaths.Experimentsshowtheaccuracyandfastof
thealgorithm.
Keywords:sessionmatrix,tracematrix,relativepages,userfrequentpaths,fastminingalgorithm
1引言
Web技术迅猛发展,经营者要考虑如何吸引客户.网站每
天都可能有上百万次访问量,生成大量的
文件.对这些数
据进行
和挖掘,可以充分了解客户的行为模式.即用户的
频繁访问路径.目前,Web日志用户频繁路径挖掘中有多种.如
Apriori算法,最大向前序列法等,但其中个性较为鲜明的是利
用矩阵进行运算发掘,矩阵不仅能准确表示Web站点有向图.
而且能有效存储用户访问信息,矩阵可以进行压缩.节约大量
空间和时间.在Apriori算法中,把所有的项集元素在每个事务
中作统计和筛选,所以耗时很多,但结果精确.本文的路径快速
发掘算法综合考虑了以上算法的优点,即考虑了算法的快速
性,又考虑了发掘结果的准确性.
2算法逻辑流程相关定义
Web日志频繁路径快速挖掘算法由以下步骤组成:数据清
理,会话识别,相似客户群体相关页面聚类和频繁路径挖掘.如
图1所示.
定义1访问频度
图l快速挖掘算法流程图
所有会话中,页面为被访问次数的总和,称为此页面的
访问频度.
定义2连接强度
在所有会话中,由页面直接进入的次数总和,称为
作者简介:杜家强(1979一),男,硕士研究生,研究方向为计算机网络,数据挖掘.韩其睿(1957一),男,教授,硕士生导师,研究方向为计算机图形处
理,软件.王科(1978一),硕士研究生,研究方向为网络通讯,模式识别.
杜家兴(1976一),男,网络工程师,研究方向为网络安全.
1642005.22计算机工程与应用
,间的连接强度.我们通过遍历矩阵来记录,间的连接
强度即为遍历矩阵A中值.
定义3会话
用户会话(UserSession)S是一个二元组<userid,RS>,其
中userid是会话标识.RS是用户在一段时间内请求的Web页
面的集合.
定义4会话矩阵
我们以URL为行,会话标识为列便得到会话矩阵M.
fh…h1
肘=f?.;』
lh,…j
其中,h是次会话中客户访问第i个URL的次数;每一
行向量M[i,?]表示所有会话中页面i的访问情况;每一列向量
肘[??]表示客户对站点中的所有的页面访问情况,因此行
向量既代表了站点的结构.又蕴涵客户共同的访问模式:而列
向量既代表了客户类型,也构勒出客户的个性化访问子图,那
么度量行向量相似性.就能得到相关Web页面.进一步分析还
能获得客户访问模式,即频繁访问路径.
定义5遍历矩阵
以URL为行,以URL为列,建立URL—URL矩阵,元素
表示所有用户经过边<,,>的次数,即访问<,>的频度,我
们把它当作边<vj>上的权值.在矩阵的行列都要添加一个
空值NULL.在行向量里出现表示用户不通过网页链接而是通
过直接输入URL,用书签访问或从其他网站进入目的网页:在
列向量里出现表示用户在此页结束浏览或链接到其它网站网
页.如果网站有n个URL,那么矩阵是(n+1)方阵.如此建立的
矩阵我们称作遍历矩阵.
faIl】…a1.l1
lI
A产;;?.;1
Il
lc+1.1…an”.lJ
该矩阵有以下特点:
(1)矩阵的对角元素值为0(网页个体不可作为自身的引
用页).
(2)矩阵K行值总和等于K列值总和?=?aki,0si=Oi--O
n(进出平衡)
定义6页面间距离
从会话矩阵中抽取两行,?,.其中若(Y)>0,令(„,)=
1,
于是,Y?{0,1n1,那么,,?,间的页面间距离
IIxII
(,?,)定义为H(,?,)=?IX广YI(=1时).
3Web日志用户频繁路径快速挖掘算法(FPFMA)
如上图1所示.快速挖掘算法由4步组成:数据清理,会话
识别,相似客户群体相关页面聚类和频繁路径挖掘.
3.1数据清理
URL扩展名:一般信息网站中,只是Htm[文件与用户会话
有关
动作:GET动作是用户请求页面的动作.我们过滤GET以
外的其他动作.
状态码:状态码指示用户请求的结果:
(1)成功相应,以2开头;(2)被成功转向,以3开头;(3)出
错,以4开头;(4)产生服务器错误,以5开头.我们要过滤掉
(3)和(4)中的信息.经过这样的净化,我们可以进行会话识别
操作.
3.2会话识别
我们可以认为一次会话是用户的一次浏览行为,由一系列
页面组成,由访问时间决定页面次序.
我们把Web日志作为一个关系表.其中每条记录视为
一
个事务.由一系列属性定义A={A,,A:,…A}.一般的属性包
括IP地址,请求时间,方法(如GET.P0ST),被请求文件的
URL,HTI?P版本号,返回码,传输字节数.
假设不同用户产生的事务由A的子集S描述Sc.定义
为用户唯一标识的集合.定义F:S—为一函数,把S中不
同的组合值映射为中的用户标识Userid.A隹S为时间属
性.我们首先定义事务表上的两个基本操作.
(1)用函数F在中产生一个新的属性A.
(2)对在和排序.
经过这两步后事务表转换为.我们定义A(tj)为第
,个事务中的A属性值.
会话的识别:
一
次会话s就是有序的事务集,满足A(tj+,)(tj)且A
(,)-A()<7-,(?s且?r为一给定的阈值,一般定义为
30min,可以指定).
一
般用户的IP或域名可以标识一个用户.但是由于国内
公网IP资源匮乏.防火墙上作NAT地址转换和代理服务器的
使用.使得用IP来辨别用户变得不再准确.这便导致我们对会
话的识别困难.不过由于大量的事务和上述的判断规则,可以
较为准确地识别会话.
参照定义4.我们建立会话矩阵如下:
以URL为行,会话标识为列组成会话矩阵sessionMatrixD
『1,其中sessionMatrix[i]~]是会话中,访问第i个URL的次数.
行向量sessionMatrix[i][]表示所有会话对页面i的访问情况,列
向量sessionMatrixfl[1”]表示会话对所有页面的访问情况.会话
矩阵只是反映了会话的页面访问情况,并不反映访问次序,为
弥补这一不足.我们参照定义5,建立遍历矩阵如下:以0和所
有URL标识为行.以0和所有URL标识为列建立矩阵
traceMatr/x[][].traceMatrix[i][j]表示所有会话中.由页面i直接
进入页面的次数总和.首行表示用户不通过网页链接而是通
过直接输入URL,用书签访问或从其他网站进入目的网页,一
般表示会话开始.首列表示用户在此页结束浏览或链接到其它
网站网页.一般表示会话结束.由上面所述可知,遍历矩阵和会
话矩阵所占用的空间与URL数目成平方关系.若URL数目很
多.几万到几十万,会造成矩阵十分庞大.而每次会话访问的页
面不过几十个.造成矩阵中大多数元素为0,属于典型的稀疏
矩阵.这里采用了压缩算法来存储矩阵.用三元组表示法存储
所有的非0值.如C『0】存储行值,C【1】存储列值,C[2】存储元素
计算机工程与应用2005.22165
值.
为表达方便,算法描述清晰,下节描述中,暂且不考虑矩阵
的存储结构.
3.3相似客户群体访问页面聚类
在数据挖掘中,在不影响挖掘结果的前提下,中间项越少
算法就越快.
FPFMA算法采用了访问频度阈值sum—threshold和距离阈
值distance—threshold对页面进行初步筛选.根据指定的访问频
度阈值sum—threshold,我们筛选出频繁访问的页面到
Frequentj—Set中,然后在Frequent_1一Set中把距离低于
distance—threshold的页面聚合在一起.
3_3.1页面聚类算法描述
算法:相似客户群体相关联页面聚类
输入:会话矩阵sessionMatrix[][];访问频度阈值sum—
threshold;距
离阈值distance_
threshold:
输出:相关联页面集合page_Set:
//通过会话矩阵获得频繁访问页面集合
(1)Frequent一1一Set=get—Frequent一1一Set(sum—threshold,sessionMa—
trix);
//在频繁页面集合中
(2)for(i=0;/<Frequent_1_Set.size();j++){
//通过会话矩阵得到第i个行向量
(3)H0_Vector=get_row_Vector(i,sessionMatrix);
//行向量ff代表的页面page_
i加入到子集合sub_Set中
(4)SUb_Set.add(page_i);
(5)forQ?=i+1<Frequent一1一Set.size()++){
//得到第个行向量
(6)H1一Vector=get_mw_Vector(j,sessionMatrix);
//计算pagej,page_.j闻的页面距离
(7)d=distanceOfPages(H0_
Vector,H1一Vector)
//如果d在指定的距离阈值范围内.加入到SUbSet中
(8)if(d<=distance—threshold)
(9)sub—Set.add(pagej):
(10)l
//若页面数大等于2,在page_Set中没有重复,加sub—
Set
到Page—
Set
(11)if(sub—Set.size>=2){
(12)page_Set.add(sub_Set);
(13)Sub_Set.clear();
(14)f
(15)}
3_3.2举例说明
本算法举例如下:有会话矩阵sessionMatrix.行为url标识
(url_1,url_2,url_3,url_4,url_5,url_6),列会话标识为(s_l,
s一2,s3,s_4,s5,s.6).
10
10
12
12
00
31
00
00
10
11
13
13
1662o05.22计算机工程与应用
02
00
02
10
10
10
经过计算得到所有url的访问量分别为url_
1,urL6
(3,1,6,6,5,9),设sum_threshold=4,则频繁页面集为{url一3
url一
4,url一
5,url一
6},我们整理矩阵为:
(3)
(4)
(5)
(6)
11
11
00
11
10
11
11
11
01
10
10
10
我们计算频繁页面间的距离:
d(url一3,url一4)=1;d(url一3,url一5):3;d(url_
3,url一6):1;
d(url一4,url一5)=2;d(url4,url一6)=0;d(url一5,url一6)---0;
若distance—threshold=2;我们得到相关页面{url一3,url_4,
url一6},{url_4,url一5,url6},{url5,url一6}.
最后我们去除重复项{url一5,url_6{,得到两个页面聚类
{url_3,url_4,url一6},{url一4,url_5,url一6}即我们找到了两个客
户群体.
3.4频繁路径挖掘
在得到相关页面集合sub—Set后,就要进行路径挖掘工作.
假设SUb_Set={pagej,page_2,pagen},我们从遍历矩阵
traceMatrix中抽取page_1,page一2,page—n对应的行和列,组成
矩阵Sin儿n],在?中找出所有的,v【司们>=linK—threshold项,
若,vI们>=li兀K—threshold,则认为(page—i,pagej)为频繁路径,
我们把所有长度为2的频繁路径进行合并.得到长度为3的频
繁路径,直到不能合并为止,这样我们便得到了所有频繁路径.
3.4.1算法描述
算法:频繁路径挖掘
输入:遍历矩阵traceMatr/x[][],连接强度阈值link—threshold;相关
页面集合SUb_
Set:
输出:频繁路径集合path_
Set:
//从遍历矩阵中抽取和遍历矩阵页面对应的子矩阵,v:
(1)N【]f]=geI—subTraceMatrix(traceMatrix,SUb_Set);
//在,v中找出频度大等于link—
threshold,长度为2的路径
集合
(12)
(13)
path_
Set=get—
Frequent一
2_Set(N,SUb_Set,link—threshold):
k=2://指示当前合并的路径长度
do{
:+1://路径长度自动增1
flag=O://指示长度为k路径中发生合并标志
//在path—
Set中长度为k一1的所有路径中
for(i=0;i<sizeOfSet(path—Set,k-1);++){
//获取path—Set中长度为k一1的第i个路径
path一
0=getPathOfSet(path—Set,k-1,i);
combine=0://标志子循环是否合并标志
f0rU=O;j<sizeOfSet(path—Set,k-1)++){
//获取path_Set中长度为k-1的第个路径
path一1=getPathOfSet(path—Set,k-1?);
//判断path_
0的后k-2位是否等于path一1的前
k-2位
jf(pathMatch(path_0,path一1)==O){
//合并path一0,path一1成长度为k的path_2
path一2=pathLinked(path一0,path一1);
//把path一2加入pathSet中
“m?:;(;(
(14)
(15)
(16)
(17)
(18)
(19)
path—Set.add(path一2);
combine=l;//标志位赋值
flag=flaglcombine;
//在长度为k的路径中发生了合并则继续循环
(20)}while(flag==1)
3.4.2举例说明
假定4-3.2节中举例的会话矩阵sessionMatrix对应的遍
历矩阵traceMatrix如下:
f
10
traceMatrix=l2
ll
l0
19
30
0l
00
00
00
00
00
32
20
l0
04
00
00
00
22
00
00
00
32
05
00
根据4<url_
4,url一
5>,<url一
5,url一
6>},和并后为{<url_
4,url一
5,
url一6>}.于是我们得到的频繁路径为{<url一
3,url一
4>,<url_
4,
url一
5,url_6>}.
4试验结果
笔者用iava+mysq1分别实现了本文快速挖掘算法FPFMA
和Apfiofi算法.以人民网W1NW.people.COn1.cn的30M日志.分
别截取为:0.97M,1.95M,3.90M,5.85M,7.8lM,9.76M.11.7M.
19.5M8个测试用例,存lntel(R)Celeron(TM)CPU.l28MRAM.
Windows2OooProfessional环境下试验结果如图2所示,
由图2,nr以看相同条件F本文算法FPFMA和Apriori
算法耗时小同,本义算法FPFMA明显低于Apriori曲线而且
随日志文件数量增加,算法FPFMA比Aprinrl芹法曲线增长的
幅度要小,表明本文算法FPFMA具有良好的扩展性
500
400
300
200
100
0
0971.953.95.857.8l9.7611.7l9.5
巨三圈
横坐标表示文件大dx/MB
纵坐标表示分析用时/s
图2试验结果
由于本文采用了压缩算法,在空间具有很好的扩展性.使
用空问与读入的记录数目以及URL数目基本无关.由此可见
本文提出的用户频繁路径快速挖掘算法FPFMA优于Apriori
算法.在实际应用中反应良好.
5结束语
本文根据WEB结构特点和Apriori算法思想提出了会话
矩阵和遍历矩阵.设计了频繁路径快速挖掘算法.该算法处理
简单一致,易于实现,可扩展性好.试验结果在表明算法有效的
同时,也提出了一个重要问题,如何评价结果的准确度.这也是
我们的下一步工作.(收稿日期:2004年l2月)
参考文献
1.AnandSS.PatrickAR.HughesJG.AdataMiningmethodologyfor
cross-sales[J].KnowledgeBasedSystemsJourna1.1998;10(7):449—46l
2.MobasherB.SrivastavaJ.Datapreparationforminingworldwide
webbrowingpatterns[J].KnowledgeandInformationSystem.1999:
l(1):5~32
3.SrikantR,AgrawalR.Mininggeneralizedassociationrules[c].In:
Proceedingsofthe21stInternationalConferenceonVeryLarge
DataBase.Switzerland.1995:407,4l9
4.KarunapJoshi,NupamJoshi,ElenaYesha.OnUsingWarehouseto
AnalyzeWebLogs[J].DistributedandParallelDatabases,2003;13:
6l,l80
5.QiangYang,JoshuaZhexueHuang.MichaelNG.ADataCubeModel
forPrediction—BasedWebPrefetchingp[J].JournalofIntelligent
InformationSystems,2003;20(1):l1,3O
6.邢东山,沈钧毅,宋擒豹.从Web日志中挖掘用户浏览偏爱路径[J].
计算机,2003;l1(26):l5l8,1523
7.宋擒豹,沈钧毅.Web日志的高效多能挖掘算法[J].计算机研究与发
展.200l;3(38):328,333
8.JiaweiHan,MichelineKamber.DataMiningConceptsandTechniques
[M].Beijing:ChinaMachinePress,2003—09
计算机工程与应用2005.22167