为了正常的体验网站,请在浏览器设置里面开启Javascript功能!

【doc】Web日志中用户频繁路径快速挖掘算法

2017-10-30 18页 doc 40KB 28阅读

用户头像

is_882336

暂无简介

举报
【doc】Web日志中用户频繁路径快速挖掘算法【doc】Web日志中用户频繁路径快速挖掘算法 Web日志中用户频繁路径快速挖掘算法 Web日志中用户频繁路径快速挖掘算法 杜家强韩其睿王科杜家兴z (天津工业大学计算机应用与自动化学院,天津300160) (人民日报社网络中心,北京100733) E—mail:djqluck@peopledaily.com.ca 摘要Web访问志中舍有大量用户浏览信息,从中有效挖掘出用户频繁路径是建立自适用化网站的必要前提.该文在 Apriori算法和有向图存储结构的基础上,提出了会话矩阵和遍历矩阵的概念,设计了用户频繁路径...
【doc】Web日志中用户频繁路径快速挖掘算法
【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
/
本文档为【【doc】Web日志中用户频繁路径快速挖掘算法】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑, 图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。 本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。 网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。

历史搜索

    清空历史搜索